Bài giảng Truyền số liệu 4

Ch

ươ

ng 4: Đi u khi n liên k t d ế ữ ể

ề

li uệ

ể

ữ ệ ồ

ữ ệ i ử ỗ

i ỗ

ể

ứ

1. Chia khung d li u 2. Ki m soát lu ng d li u 3. Phát hi n và s a l ệ 4. Ki m soát l 5. Giao th c HDLC ứ 6. Các giao th c khác 7. Bài t pậ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 1 ố ươ ế ữ ệ ề ể

ể

ế

ề  Truy n tín hi u trên liên k t ệ

ấ

c gi

t ng

ả

 Truy n d li u trên liên k t

ế

ữ ệ

ng 4

ươ

ế ữ ệ

ả  V n đ c n gi

ế ữ ệ i quy t ế

ể ể

ữ ệ

ứ ậ

ể ể

Đi u khi n liên k t d li u ế ữ ệ Ch a có v n đ nào ư ề đ i quy t ế ở ầ ượ v t lý ậ N i dung ch ộ  Chia khung  Ki m soát l i ỗ  Ki m soát lu ng d li u ữ ệ ồ  HDLC: Giao th c ki m ể soát d li u b c cao ữ ệ  Các giao th c khác

ứ

ị ữ ệ

ể

ộ

ề v t lýậ ề v t lýậ  Thi t l p liên k t d li u ế ậ  Truy n d li u ữ ệ ề  Gi i phóng liên k t d li u ả ề ầ ấ  Chia d li u thành khung  Ki m soát lu ng d li u ồ ữ ệ  Ki m soát l i ỗ  Đánh đ a ch ỉ  G p d li u đi u khi n và d ộ ữ ề li u trên cùng m t liên k t ế ệ  Qu n lí liên k t ế

ả

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 2 ố ươ ế ữ ệ ề ể

D li u c n chia thành t ng kh i đ

1. Chia khung ố ể

ừ

ầ ả

ệ

ể

i ử ỗ

ộ ậ ể

ề T ng v t lý truy n m t chu i bít không có c u trúc.

ấ

ỗ

ậ ể

t ệ

ặ

ộ ử ụ T ng liên k t d li u có th chia khung s d ng

ử ụ

ể

ả

ng b i nhi u

ộ ễ ị ả

ễ

ở

ữ ệ  đ m b o đ ng b v t lý ồ ả  B sung các bít ki m tra đ phát hi n và s a l ổ  B sung các thông tin đi u khi n ể ổ ề ầ  Có th chia khung s d ng các bít đ c bi ế ữ ệ ầ  Kho ng l ng gi a các khung d li u ặ ữ ệ ữ Không đ m b o đ ng b , d b nh h ả ưở ồ ả  S đ m ký t ự ố ế  Ký t đ c bi t ự ặ ệ  Chu i bít đ c bi ặ ỗ

t ệ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 3 ố ươ ế ữ ệ ề ể

Dùng s đ m ký t ố ế , m i ký t có t ỗ ự

ự 5-8 bít (giao ừ

ự

ề

ữ ệ th c h ứ  Ký t

ng ký t

c a

 D li u chia thành nhi u ký t ng ký t ) ự ủ

ữ ệ

ứ

ộ

ố ượ

ự ủ

ướ đ u tiên c a m t khung d li u ch a s l ự ầ khung d li u

ữ ệ

ạ

ứ

ớ

ị

i các khung i b t kỳ, m t đ ng b , không có kh năng tái l p l ậ ạ

ỗ ấ

ể ộ

ả

ệ

 Dùng đ h tr các ph

 T i đích, căn c vào s đ m đ xác đ ng ranh gi ố ế  Khi có 1 l ấ ồ k c khi phát hi n ra có l i ỗ ể ả ng pháp khác (phát hi n l ươ

ể ỗ ợ

ệ ỗ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 4 ố ươ ế ữ ệ ề ể

đ c bi

ự ặ

t ệ

đ c bi

 Dùng m t ký t

Dùng ký t t ệ ự ặ FLAG đ phân tách các khung d li u

ế

ệ ướ ế

ữ ệ ế

ộ

 T i đích: khi nh n khung d ữ

ậ

ớ ạ

i h n trong m t b ng ch ữ

ộ ả

•Gi cái

ộ ể ữ ệ  N u trong d li u có ký t ự ữ ệ đ c FLAG, chèn m t ký t ự ặ ộ t khác vào tr bi c (ESC), ướ c khi t o khung d li u tr ữ ệ ạ  N u trong d li u có ký t ự ESC, chèn ti p m t ký t ự ESC ạ li u, ệ  Căn c vào FLAG đ ng riêng

ứ

ể

ứ đ chia khung  Lo i b các ký t

chèn thêm

ự

•Dùng trong PPP cho liên k t ế quay số

ạ ỏ ESC FLAG=FLAG ESC ESC=ESC

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 5 ố ươ ế ữ ệ ề ể

ặ

t ệ

Dùng chu i bít đ c bi ỗ Dùng m t chu i bít đ c ộ

ỗ

ặ t đ phân chia các

ệ ể

ữ ệ

bi khung d li u  Ví d 01111110 ụ

ầ

ữ ệ ữ ệ

ề

Khi có chu i 01111110 ỗ trong d li u ữ ệ  N u có 5 bit 1 li n nhau,

ế

ề

i đích

ữ ệ ạ

(a) D li u ban đ u. (b) D li u truy n đi. .

c chuy n

ể

chèn 1 bít 0 vào sau T i đích ạ  Tách khung  111110 đ ượ thành 11111

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 6 ố ươ ế ữ ệ ề ể

ể

ồ

i tr m đích

2. Ki m soát lu ng d li u ữ ệ ả ạ ả

ạ

ồ

Đ m b o tr m ngu n không làm quá t ả Tr m đích ạ ư

ữ

ộ

c khi chuy n d li u lên t ng

 l u tr các khung d li u trong b nh đ m ớ ệ ữ ệ  Th c hi n m t s thao tác tr ể

ộ ố

ướ

ệ

ữ ệ

ầ

i m t khung d li u

ể ị ầ

ẫ ớ

ữ ệ

ấ

ự trên ộ ư

ớ ệ ặ ấ

ề ỗ

c truy n chính xác

ề

 B nh đ m có th b đ y, d n t Ch a đ t v n đ l i truy n tin ề  Các khung d li u luôn luôn đ ượ ữ ệ  Đ tr truy n tin không xác đ nh ị

ề

Gi

ả

ộ ễ i pháp ơ ơ

 C ch d ng và ch ờ ế ừ  C ch c a s tr t ổ ượ ế ử

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 7 ố ươ ế ữ ệ ề ể

C ch d ng và ch

ơ ế ừ

ờ

ồ

ữ ệ

ậ

ẵ ậ

ế

ằ

ộ

 Nguyên t cắ  Ngu n g i m t khung d li u ử ữ ệ ộ  Đích nh n khung d li u, x lí, sau đó thông báo s n sàng nh n các ậ ử khung d li u ti p theo b ng m t thông báo báo nh n ữ ệ (acknowledgement)

 Ngu n ch đ n khi nh n đ ờ ế

ậ

ượ

c báo nh n m i truy n ti p khung d li u ề

ữ ệ

ế

ậ

ớ

ồ ti p theo

t thích h p v i các khung d li u l n

ặ

ệ

ữ ệ ớ

ớ

ợ

 Nh

ế  u đi m Ư ể  Đ n gi n, đ c bi ả c đi m ể

ng truy n b lãng phí

ơ ượ ớ

ỏ

ữ ệ

ử ụ

ườ

ị

 V i các khung d li u nh , th i gian s d ng đ ề ờ  Không th s d ng các khung d li u l n m t cách ph bi n ổ ế

ữ ệ ớ

ộ

ỗ ớ

i l n ẻ ả ề ụ ế ạ

ể ử ụ B nh đ m có h n ạ ớ ệ Khung d li u dài kh năng l ữ ệ Trong môi tr ng truy n tin chia s , không cho phép tr m nào chi m d ng ườ ng truy n ề

lâu đ ườ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 8 ố ươ ế ữ ệ ề ể

t

C ch c a s tr ơ ế ử ổ ượ C ch d ng và ch : ch cho phép truy n m t khung ề ỉ

ế ừ

ờ

ộ

ổ ượ

t cho phép truy n nhi u khung d ữ

ề

ơ d li u ữ ệ C ch c a s tr ế ử ơ li u cùng m t lúc ệ

ộ

Xét hai tr m A, B k t n i b ng m t đ

ế ố ằ

ộ ườ

ạ

ng truy n song ề

ớ ệ

công  B có b nh đ m n khung d li u ữ ệ  Nh v y A có th g i cùng m t lúc n khung d li u mà ộ

ộ ư ậ

ữ ệ

ể ử không c n báo nh n ậ

 Đ ‘nh ’ các khung d li u đã báo nh n, c n đánh s các

ữ ệ

ậ

ầ

ố

ầ Báo nh nậ ớ ể khung d li u

 B báo nh n m t khung b ng cách báo s khung d li u mà

ữ ệ

ữ ệ ậ ờ

ộ ậ

ằ ị

ố t c các khung ậ ấ ả

ầ

B đang ch nh n, ng m đ nh đã nh n t tr

c đó

 M t báo nh n có th dùng cho nhi u khung d li u ữ ệ

ể

ề

ậ

ướ ộ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 9 ố ươ ế ữ ệ ề ể

C ch c a s tr

t

ơ ế ử ổ ượ

khung đ

 A qu n lý m t danh sách các s th t

ượ

ố ứ ự

ử

ổ ử

khung đang

C a sử ổ ả ề ả

ố ứ ự

ờ

ộ quy n g i đi (c a s g i) ộ ch nh n (c a s nh n) ử ế ử

i h n, do đó

ộ

 B qu n lý m t danh sách các s th t ậ ổ t ổ ượ khung d li u có đ dài gi ớ ạ ữ ệ c l y modulo. Vd 3 bít-> modulo 8

ượ ấ  C a s b gi ổ ị ớ ạ

ố ứ ự

ậ  -> c ch c a s tr ơ  S th t ố ứ ự c n đ ầ ử ụ

ở Ví d 3 bít, c a s g i = c a s nh n=8 ổ ử

i h n b i giá tr l n nh t c a s th t ử

ấ ủ ậ

ị ớ ử

ổ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 10 ố ươ ế ữ ệ ể ề

C ch c a s tr

t

ơ ế ử ổ ượ

 Hình trên

ử

i c a c a s tăng lên khi ổ

ữ ệ

ổ

ủ

ộ

g i m t (nhi u) khung d li u  C n trên c a c a s tăng lên khi ử nh n m t (nhi u) báo nh n ề

ậ

i c a c a s tăng lên khi ổ

ướ ủ ộ

ữ ệ

ử nh n m t (nhi u) khung d li u ề  C n trên c a c a s tăng lên khi ử

ủ

ổ

ậ

ộ

 Hình d

 T i ngu n ồ ạ  C n d ướ ủ ậ ề ộ ử ậ ậ  T i đích ạ  C n d ậ ậ ậ g i m t (nhi u) báo nh n ề ử iướ

 A có th g i 7 khung d li u cùng ữ ệ

F0 ể ử ừ ộ

 A g i F0,F1,F2, gi m c a s ổ ử ả

m t lúc t ử ố

xu ng còn 4 ậ ể

ậ ả

 B có th nh n 7 khung  B nh n F0,F1,F2 gi m CS còn 4  B x lí xong F0,F1,F2, RR 3, tăng ử

ử ả

 A g i F3,4,5,- gi m CS còn 3  B nh n F3, x lí, g i RR 4 ử ử ậ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 11 ố ươ ế ữ ệ ể ề

t

C ch c a s tr ơ ế ử ổ ượ ồ

ể

ữ ệ

 Khi tr m B không có kh năng nh n thêm khung d li u, CS

Ki m soát lu ng d li u ả

ạ

ậ

ữ ệ nh n tin=0, B g i thông báo RNR 5 Receive Not Ready

ử

ậ

ộ ố

ữ ệ

ộ

 Sau khi B x lí m t s các khung d li u trong b nh đ m, ớ ệ CS>0, B g i RR x Receive Ready, báo nh n và ch nh n ậ

ậ

ờ

ử ử ng h p truy n tin hai chi u

Trong tr

ườ

ề

ợ

 A và B cùng truy n tin  Khi B c n báo nh n và c n truy n s li u. B g i kèm báo

ầ

ề ậ

ử

ề

ầ

ậ ế

ử

ậ

ố ệ nh n trong khung d li u: Piggybacking ữ ệ  N u không, B g i m t khung báo nh n riêng ộ  Sau khi g i báo nh n, n u B truy n khung d li u, B v n

ữ ệ

ử

ế

ậ

ẫ

ặ ố

t hi u qu h n nhi u so v i d ng

ậ C ch c a s tr ổ ượ ế ử

đ t s báo nh n trong khung d li u ơ

ớ ừ

ệ

ề

ề ữ ệ ả ơ

và ch !ờ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 12 ố ươ ế ữ ệ ể ề

i ử ỗ

3. Phát hi n và s a l ệ  Vì sao ph i phát hi n và s a ử

ệ

ả

i c a m t bít t

ộ

ươ

 Xác su t m t khung d li u ộ

ữ ệ

iỗ l  Xác su t l ấ ỗ ủ đ i nh ố ỏ (P1=10-6) ấ 1000 bit không l

i ỗ (1-P1)1000~0,999

 Xác su t l

ấ ỗ ủ

i c a m t khung d ữ

ộ

li u ệ

ế

 M t khung d li u m bít, s d ng thêm r ử ụ ữ ệ 1- (1-P1)1000=10-3 Quá l n!ớ

ư ừ

c mã hóa b ng ượ ằ

ộ bít  M t t m t t

i: Mã Hamming

 Làm th nào? ổ ể ạ ế

 B sung m t s bít (d th a) ộ ố i ệ ỗ i các bít b sung ạ ị ằ

 Mã phát hi n l  Mã s a l

ệ ỗ i ử ỗ

không có l

đ phát hi n l  T i đích tính l ổ  N u hai giá tr b ng nhau: iỗ

 N u không, có l

ỗ

ứ

 Parity bit (bít ch n l ) ẵ ẻ  CRC (Cyclic Redundancy Check) mã vòng

k t qu đ phát hi n l

ả ể

i, căn c vào i ệ ỗ

ế ế

d li u m bít đ ộ ừ ữ ệ mã m+r bít ộ ừ  Hai lo i mã ạ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 13 ố ươ ế ữ ệ ể ề

Kho ng cách Hamming

ừ

ố

mã đ mã hóa 2

ể

mã không s d ng: t

m t ử ụ i: khi có l

ợ ệ mã thu đ

ả  Đ nh nghĩa: S các bít khác nhau gi a hai t ị  Có 2m+r t ừ  Có m t s t ộ ố ừ  Nguyên t c phát hi n l ắ

ữ d li u ừ ữ ệ ừ i x y ra, t ỗ ả

mã không h p l ừ

ệ ỗ

ượ

không h p lợ ệ

 Ví d : ụ

ữ ệ

ợ ệ

ệ

i x y ra, luôn luôn xác đ nh đ

ỗ ả

i ỗ ị

ượ

 Thêm m t bít ch n l vào sau d li u ẵ ẻ ộ  Có m t t p t mã v i kho ng cách =2 ả ớ ộ ậ ừ  Khi có 1 bit l i, có m t t mã không h p l -> phát hi n có l ỗ ộ ừ  Nguyên t c s a l i: khi có l ử ỗ ắ g n nh t. mã h p l ợ ệ ầ

ấ

ừ  Ví dụ

mã 0000000000, 0000011111,1111100000, 1111111111 d li u 2 bít 00,01,10,11

ừ i: khi có 2 l mã h p l t ượ ỗ mã 5 i, t ỗ ừ ợ ệ ươ ng ng có kho ng cách g n ả ứ ầ

Dùng 4 t ừ Mã hóa t ừ ữ ệ Kho ng cách gi a các t ữ ả S a đ c 2 l ử nh tấ

Vd khi nh n chu i bít 0000000111, mã h p l là 0000011111 (2 bít l i) ợ ệ ậ ỗ ỗ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 14 ố ươ ế ữ ệ ề ể

Mã hamming s a m t l

i ộ ỗ

ử

ằ mã có m+r bit i, có kh năng t o ra m+r t

mã không h p l

có

ừ

ợ ệ

ả

, m i t ỗ ừ ạ ả là 1 mã h p l ợ ệ mã không h p l

t o ra b i 2 t

mã h p l

khác

ợ ệ ạ

ậ

ợ

ở

ừ

ợ ệ

 Gi i h n lý thuy t ế ớ ạ  d li u có m bit, mã hóa b ng m+r bit t ừ ữ ệ  Có 2m t mã h p l ợ ệ ừ  Khi có m t bít l ỗ ộ kho ng cách đ n t ế ừ  T p h p c a các t ừ ủ nhau ph i r i nhau ả ờ

i h n trên

 Mã Hamming s a 1 l

c gi

ớ ạ

ử

ỗ

ử ụ

v trí 2

t c các bít có s th t

ở ị

ẽ

ố ứ ự

có v trí bít ị

 Do đó 2m(m+r+1)<=2m+r hay m+r+1<=2r i có th đ t đ ể ạ ượ v trí 1,2,4,8,16…. ở ị c a t ẵ ẻ ủ ấ ả ằ ị

K s là bít ch n l th k trong khai tri n nh phân b ng 1 ể

 M t bít s tham gia vào quá trình tính toán c a các checkbit t

ươ

ng ng ứ

ố ứ ự

ể

ị

ủ ủ

t c các bit 1 trong khai tri n nh phân c a s th t mã, ki m tra các checkbit ậ

ể

ế

ấ ả

ứ

ị ủ

ng ng v i 1 trong t c các checkbit t ớ ươ bít đó đ u b đ o d u, các checkbit ấ ị ả ề

ố ứ ự

ị nguy n

 T mã s d ng các checkbit ừ  Bít ứ ộ ẽ v i t ớ ấ ả  Khi nh n đ c t ượ ừ  N u có 1 bít nào đó b sai, thì t khai tri n nh phân c a s th t ể khác gi ề ữ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 15 ố ươ ế ữ ệ ề ể

Mã hamming s a m t l

ộ ỗ

ử

i-ví d ụ

S TTố

 T mã 15 bít, bít 1,2,4,8 là

ừ

0001

0010

0100

1000

ả

0001

0010

0011

 B t c bít nào b sai, các ng ng s b ẽ ị ươ

ị ứ

0100

checkbit (xem b ng). Mã hóa d li u 11 bit t ừ ữ ệ ấ ứ check bít t đ oả

0101

ứ

0110

 Căn c vào đó, đích s bi t ẽ ế c bít nào b đ o đ s a ể ử ị ả

0111

đ ượ iỗ l

1000

 Thu t toán s a l

i ử ỗ

1001

1010

1011

1100

1101

1110

ậ  T ng=0 ổ  Ki m tra l n l t các checkbit ể ầ ượ  N u checkbit b đ o, c ng s ố ộ ị ả ế th t c a checkbit đó vào ứ ự ủ t ngổ ế

1111

c a bít l

 K t thúc ki m tra, t ng=0: ể ổ không có l i, n u t ng<>0 là ế ổ ỗ i s th t ỗ ố ứ ự ủ ố

Ch 10/07/11 @Hà Qu c Trung 2004. ng 4: Đi u khi n liên k t d li u 16 ươ ế ữ ệ ề ể

ỗ ỗ

ộ

i liên ti p ế

ng các bit l

Mã hamming s a m t chu i l ử  Th i hay x y ra ả

ỗ

ườ liên ti pế

 Mã hamming ch s a đ

ỉ ử

ượ

m t l

ỗ



mã mã

i ộ ỗ  Đ s a k l ể ử ề

i liên t c ụ ộ

ừ

truy n cùng m t lúc k t hóa b ng mã hamming

ằ

c x p thành

 K t

ượ

ế

ừ

ượ

c truy n theo ề

mã này đ ma tr n bit ậ  Ma tr n này đ ậ t ng c t. ừ ạ

ượ

c nh n, ậ

ậ ừ

 Tr

tái t o l ườ

ấ ề ỗ

mã ch có đúng 1 bít

ỗ ừ

ỉ

i g m t i đa ộ ỗ ồ ố

 B ng mã Hamming, s a

ử

ộ  T i đích, ma tr n đ mã i các t ạ ạ ng h p x u nh t, khi có ấ ợ k bít liên ti p b truy n l ị ế m i t iỗ l ằ c l ượ ỗ

ỗ ừ

Dùng kr checkbit cho km bit d ữ li u, s a đ c m t l ượ ử ệ k bít liên ti pế

i cho m i t ố

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 17 ươ ế ữ ệ ề ể

i ệ ỗ

ị

t h n là truy n l

ỏ ổ i nh , các bít b sung đó b lãng phí ổ ỏ i nh , gi i pháp t ố ơ ỏ

ả

i c ề ạ ả

-6

i 10  Truy n 1Mb b ng khung d li u mã s a l

i hamming đ l n

Mã phát hi n l S a l i đòi h i m t s bít b sung ộ ố ử ỗ N u t l l ế ỷ ệ ỗ Khi t l l ỷ ệ ỗ khung d li u. ữ ệ Ví d : T su t l ấ ỗ ụ ỷ ằ ề

ử ỗ

ữ ệ

ộ ớ

C n 10 checkbit b sung cho m i khung d li u. T ng c ng

1000 bit ầ

ỗ

ữ ệ

ổ

ộ

cho 1000 bít, khi truy n 1Mb có 1 l

ề

i ỗ

ẵ ẻ ế T ng c ng dùng thêm 1x1000+1001=2001 bít

ổ

su t l

ỏ ử ụ

ấ ỗ

i ệ ỗ

ổ 10.000bit cho 1Mb  N u dùng 1 bít ch n l ộ Do đó khi t i nh , s d ng các mã phát hi n l ỷ  Parity check (bít ch n l ) ẵ ẻ  Mã vòng (Cyclic redundancy check-CRC)

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 18 ố ươ ế ữ ệ ề ể

Bít ch n l

(Parity checkbit)

ẵ ẻ

Thêm m t bít vào cu i khung d li u.

ữ ệ

ố

 Giá tr c a bit đ m b o s bít 1 trong khung d li u ố

ữ ệ

ả

ẵ

i, tính ch n l

b thay đ i, phát

ị ỗ

ẵ ẻ ị

ổ

ệ

N u có m t chu i bít liên ti p b l

i, xác su t

ộ ị ủ luôn là s ch n ố  Khi có m t bít b l ộ i ỗ ộ

hi n ra l ế

ị ỗ

ấ

ế

ỗ

Có th dùng k thu t ma tr n gi ng nh v i ư ớ

ố

phát hi n ra l ệ ể

ỗ i là 0.5 ậ ậ ỹ mã hamming đ phát hi n k l ể  Khi truy n l ề ạ ầ

ề

i liên ti p ế ỗ ệ i c n truy n c k kh i d li u ố ữ ệ ả

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 19 ố ươ ế ữ ệ ề ể

Mã vòng Nguyên t c: thêm r bít (FCS Frame Check Sequence)

ắ

ữ ệ

vào m bít d li u  s nh phân m+r bít chia h t cho m t s nguyên xác đ nh ế ị

ộ ố

ị

c khung d li u, chia cho s nguyên trên.

ố tr cướ Khi nh n đ ậ

ượ

ữ ệ

ố

ườ

ỗ

i ỗ i, giá tr c a d li u b sai l ch m t ữ ệ

ị ủ

ệ

ộ

ị

 L i luôn đ

N u không còn d t c là không có l ư ứ ế  Trong tr ng h p có l ợ s E nào đó ố ượ ỗ

c phát hi n, ch tr khi E chia h t cho s ố

ỉ ừ

ế

ệ

Gi

ị

nguyên trên (hi m)ế i thu t ậ ả  Mô t b ng phép toán nh phân ả ằ  Mô t b ng phép toán đa th c ứ ả ằ  Mô t b ng m ch logíc s ạ ả ằ

ố

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 20 ố ươ ế ữ ệ ề ể

Mã vòng b ng phép toán nh phân

ằ

ị

 Phép c ng, tr nh phân

ừ

ộ

ị

 Ví dụ

 Đ nh nghĩa

ầ

ữ ệ

ủ

 M=1010001101 (10 bít)  P=110101 (6 bít)  C n tính F (5 bít)  Thêm 5 s 0 sau M: Mx2 ố

ủ

ố

không nhớ  X+X=0, X-X=0 ị  T=khung d li u k+n bit  M: k bit đ u tiên (d li u) c a T ữ ệ ầ  F: n bit cu i cùng (FCS) c a T ố  P: S nh phân n+1 bít ị  T=M 2n+F

101000110100000  Chia giá tr thu đ

c cho P

 M c tiêu: Ch n F đ T/P

ụ

ể

ọ

ượ ị  R=01110, F=01110  T=101000110101110

ượ

không dư  Chia M 2n cho P đ c Q d R. ư  Vì các phép tr không nh nên ớ ừ

R có <=n bít  Ch n F=R. ọ

 T=M 2n+R=PQ+R+R=PQ chia

h t cho P

ế

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 21 ố ươ ế ữ ệ ề ể

4. Ki m soát l

 Các k thu t trên g i chung

ả

ậ đ ng truy n l

i ỗ ỹ ự ộ

ẩ

ể  Đ m b o truy n tin tin c y ề ậ ng truy n tin trên môi tr ề ườ không tin c yậ ệ

 Đi u ki n ề

ọ i (ARQ là t ề ạ automatic repeat request). Có 3 phiên b n chu n hóa ả  D ng và ch (Stop and ờ

ừ

ữ ệ

Wait)ARQ

ề

 Các khung d li u luôn luôn c truy n chính xác  Đ tr truy n tin không xác ề

ượ ộ ễ

 Quay l i N(Go Back N) ARQ ạ  Lo i b ch n l c (Selective ọ ọ ạ ỏ

đ nhị

Reject) ARQ

 Có hai lo i l ấ

i (đã h c)

i ạ ỗ M t khung d li u ữ ệ Khung d li u b l i ị ỗ ậ ử ụ ọ

 Các k thu t s d ng: ệ ỗ

ỹ  Phát hi n l  Báo nh nậ  Truy n l  Truy n l

i v i timeout i v i báo không nh n

ề ạ ớ ề ạ ớ

ậ

ữ ệ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 22 ố ươ ế ữ ệ ề ể

ờ

D ng và ch ừ  D a trên c ch KS lu ng ồ ơ

ế

ờ

 Ngu n ch có th truy n ti p

ự ữ ệ ồ

d li u d ng và ch ừ ỉ

ề

ể

ế

 Hai lo i l

khi có báo nh nậ i ạ ỗ ữ ệ

 Khung d li u b m t ho c b ị i: tr m ngu n c n có c ch ế ồ

ị ấ ầ

ặ ơ

l ạ ỗ timeout

 Báo nh n b m t: tr m ngu n ị ấ

ạ

ậ

ồ

ữ ệ

g i l ử ạ c n lo i khung d li u l p ầ

 Đánh s các khung b ng 0

i khung d li u, tr m đích ạ ố

ạ ữ ệ ặ ằ

và 1

ng ng cho

 Hai báo nh n t

ứ

ậ ươ

ả

c đi m: không hi u

0 và 1 Ư ể ượ

ể

ệ

 u đi m: đ n gi n  Nh quả

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 23 ố ươ ế ữ ệ ề ể

Go back-N ARQ

ế ử

Nguyên t cắ  D a trên c ch c a s tr ơ ự  Khi có m t khung d li u ch a đ

ộ

t c ấ ả

c nh n, t ậ ượ sau đ u b lo i b ị ạ ỏ

t ổ ượ ư ề t c các khung t

khung

ữ ệ các khung có s th t ố ứ ự  Tr m ngu n s truy n l ẽ ồ

i t ề ạ ấ ả

ừ

 S d ng m t khung d li u báo không nh n REJ ữ ệ

ậ

ộ

ạ i b l ị ỗ ử ụ

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 24 ố ươ ế ữ ệ ể ề

ữ ệ

ờ

ồ

ng h p sau x y ra

Ho t đ ng ạ ộ  A g i khung d li u cho B, kh i đ ng đ ng h và ch báo ở ộ ợ

ồ ả

ử ậ

ườ

nh n. Có th có các tr ể ữ ệ

ị ỗ

– A g i khung i. Khung i b l t khung i-1. B g i cho A REJ i và ử ị ỗ

Khung d li u b l ử lo i b t truy n l

ậ ố c sau đó. A khi nh n đ c REJ ậ ượ ạ ỏ ấ ả

– Khung i b m t. A đã g i khung i+1, …. B nh n đu c i+1 khi đang ch i. ậ ờ ợ

ử i t ề ạ ấ ả ử i ừ

i. B nh n t t c các khung nh n đ ậ ượ i t c các khung t i t ừ ề ạ ấ ả ị ấ B g i REJ i. A truy n l ị ấ t c khung t ử ữ

ặ i A. Sau t, đ ngh B ề ị

i ị ỗ

ờ i báo nh n cu i cùng. Sau đó A g i l i khung i ộ ử ạ ậ ố

c các báo nh n – Khung i b m t, A không g i thêm khung n a. B không tr l ả ờ m t th i gian, A timeout. A g i cho B m t khung RR đ c bi ộ ệ ử g i l ử ạ Báo nh n b l ậ ậ ị ấ ượ ử ể ậ ậ

– B nh n khung i và g i RR i+1 b m t. A có th nh n đ ậ

REJ b l

ệ t gi ng tr ố ườ ng h p trên ợ

ng h p trên ợ

ị ỗ

ườ

ti p theo bao g m báo nh n i ồ ế – A timeout, A g i khung RR đ c bi ặ ử i: gi ng tr ố

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 25 ố ươ ế ữ ệ ề ể

Go Back N: Ví dụ

ạ ỏ

ọ ọ

Lo i b ch n l c  Báo khung l ỗ ằ i: ch truy n l ỉ

ề ạ

ỗ

i b ng SREJ i i i khung l ầ

 Gi m s khung c n ố ả i truy n l ề ạ  Tăng s l ố ượ trong b nh đ m ộ

ầ

ng khung l u ớ ệ  C n logíc đ chèn khung ể i vào đúng v trí

truy n l

ề ạ

ị

10/07/11 @Hà Qu c Trung 2004. Ch ng 4: Đi u khi n liên k t d li u 26 ố ươ ế ữ ệ ề ể

ạ ộ

i chu n (NRM)

 3 lo i tr m ạ ạ  Tr m chính: ạ có trách nhi m ki m soát trao

dùng v i c u hình không cân

5. Giao th c HDLC ứ  3 ch đ ho t đ ng ế ộ  Ch đ tr l ế ộ ả ờ ẩ ớ ấ

ể

ổ

ệ đ i thông tin trên liên k t ế Khung g i b ng tr m chính ử ằ ạ b ngằ ạ

i cân b ng không

ằ

ọ ệ ủ Tr m chính ki m soát hoàn ạ

i s ki m soát ướ ự ể ể toàn vi c truy n tin c a tr m ề phụ  Ch đ tr l ế ộ ả ờ đ ng b (ABM) ộ g i là l nh ệ  Tr m ph ụ ạ Ho t đ ng d ạ ộ c a tr m chính ạ ủ

ồ Dùng v i kênh cân b ng Hai tr m h n h p truy n tin ề ỗ

ằ ớ Khung g i b ng tr m ph g i ụ ọ ử ằ ạ

ợ

ạ ợ

ằ

ạ ạ

ề

 Không cân b ng: n i 1 tr m ằ

ạ

ố

i không cân b ng ộ Dùng v i kênh không cân

ầ  Ch đ tr l là tr l iả ờ  Tr m h n h p ỗ  2 lo i kênh truy n không c n xin phép ế ộ ả ờ không đ ng b ồ