Xem mẫu

  1. Chương 5: T ng Liên k t d li u M c tiêu: S h c gì: Các nguyên lý cung c p d ch Các d ch v t ng Liên k t d li u v c a t ng Liên k t d li u: Phát hi n, S a l i Phát hi n và S a l i ða truy c p và m ng LAN Chia s kênh truy n dùng ð a ch t ng Liên k t d li u và chung: ña truy c p ARP ð a ch t ng link M t vài công ngh Liên k t d li u Truy n tin c y, ði u khi n lưu lư ng: ñã h c ! c th : Ethernet Cài ñ t trên các công ngh Liên k t d li u khác nhau hubs, bridges, switches (r t nhi u) IEEE 802.11 LANs PPP 5: Liên k t d li u 5a-1
  2. Liên k t d li u: V trí trong Mô hình 5: Liên k t d li u 5a-2
  3. Liên k t d li u: B i c nh Hai thi t b có k t n i v m t V t lý: host-router, router-router, host-host ðơn v trao ñ i d li u : frame M application Ht M transport Hn Ht M network data link network protocol Hl Hn Ht M link link Hl Hn Ht M physical physical frame phys. link Card m ng 5: Liên k t d li u 5a-3
  4. Liên k t d li u : D ch v T o frame, Truy c p môi trư ng: ð t các datagram trong các frame, b sung thêm header, trailer N u môi trư ng truy n dùng chung, cài ñ t ch c năng ña truy c p “ñ a ch V t lý” trong tiêu ñ c a frame xác ñ nh ð a ch G i/ Nh n • Khác ñ a ch IP ! Truy n tin c y gi a hai thi t b có k t n i V t lý tr c ti p: Nguyên lý ñã ñư c gi i quy t (chương 3)! Ít khi ñư c dùng trên kênh truy n có t l l i th p (cáp quang, m t s cáp ñ ng tr c) ðư ng truy n không dây: T l l i cao • V n ñ : T i sao ñ t Tính tin c y c hai t ng ? 5: Liên k t d li u 5a-4
  5. Liên k t d li u : D ch v (ti p) ði u khi n lưu lư ng: Phù h p T c ñ G i và Nh n Phát hi n l i: L i do nhi u. Phía Nh n xác ñ nh ñư c có l i: • Yêu c u bên G i truy n l i ho c lo i b Frame S a l i: Phía Nh n xác ñ nh và s a ñư c các bit b l i mà không yêu c u truy n l i 5: Liên k t d li u 5a-5
  6. Liên k t d li u: Cài ñ t ñâu Cài ñ t trên các “adapter” Ví d PCMCIA card, Ethernet card Thư ng có: RAM, DSP chips, host bus interface, và link interface M application Ht M transport Hn Ht M network data link network protocol Hl Hn Ht M link link Hl Hn Ht M physical physical frame phys. link adapter card 5: Liên k t d li u 5a-6
  7. Phát hi n L i EDC = Error Detection and Correction bit (Dư th a) D = D li u c n ñư c b o v (có th thêm ph n Tiêu ñ ) • Phát hi n l i Không hoàn toàn ñáng tin c y ! • Giao th c có th ñ “l t” m t s l i (hi m khi) • Trư ng EDC l n giúp Phát hi n và S a l i t t hơn 5: Liên k t d li u 5a-7
  8. Ki m tra Ch n l M t Bit Ch n L : Bit Ch n L hai chi u: Phát hi n M t l i Phát hi n và S a ñư c m t L i 0 0 5: Liên k t d li u 5a-8
  9. Internet checksum M c tiêu: phát hi n “l i” (bit b ñ i) trong segment ñư c truy n (chú ý: ch ñư c s d ng T ng Giao v n) Phía G i: Phía Nh n: Xem n i dung segment như Tính checksum c a segment nh n các chu i s nguyên 16 bit. ñư c checksum: T ng bù 1 c a t t Ki m tra checksum v a tính ñư c c các t v i giá tr Trư ng checksum: Phía G i ñ t giá tr checksum KHÔNG TRÙNG – Phát hi n có L i trong trư ng checksum c a UDP TRÙNG – Không phát hi n ñư c L i. Nhưng v n có th có L i? 5: Liên k t d li u 5a-9
  10. Mã s a l i Hamming ð ng l c : Mu n có mã s a l i c n ít dư th a hơn ki u mã ma tr n ch n l hai chi u Mã Hamming : v i log(M) bit dư th a S a t t c l i m t bit Phát hi n các l i hai bit ð t các bit ch n l ki m tra xen k Richard W. Hamming 5: Liên k t d li u 5a-10
  11. Xác ñ nh mã Hamming Th t c: ð t các bit d li u th c s (thông ñi p) t i các v trí Không ph i là lũy th a c a hai. Xây d ng b ng li t kê bi u di n nh phân cho m i v trí c a bit d li u Tính giá tr các bit ki m tra 5: Liên k t d li u 5a-11
  12. Ví d v mã Hamming Thông ñi p c n g i: 1 0 1 1 1 0 1 1 V trí 1 2 3 4 5 6 7 2n: Bit ki m tra 20 21 22 5: Liên k t d li u 5a-12
  13. Ví d v mã Hamming Thông ñi p c n g i 1 0 1 1 1 0 1 1 V trí 1 2 3 4 5 6 7 2n: Bit ki m tra 20 21 22 Tính toán các bit ki m tra: 3 = 21 + 20 = 0 1 1 5 = 22 + 20 = 1 0 1 6 = 22 + 21 + = 1 1 0 7 = 22 + 21 + 20 = 1 1 1 5: Liên k t d li u 5a-13
  14. Ví d v mã Hamming Thông ñi p c n g i 1 0 1 1 1 1 0 1 1 B t ñ u t v trí 20 : V trí 1 2 3 4 5 6 7 Ki m tra t t c các v trí có giá tr 2n: Bit ki m tra 20 21 22 1 t i v trí 20 Tính toán các bit ki m tra : ð m s lư ng s 1 trong các bit 3 = 21 + 20 = 0 1 1 thông ñi p tương ng 5 = 22 + 20 = 1 0 1 6 = 22 + 21 + = 1 1 0 N u CH N, ñ t 1 v trí bit ki m 7 = 22 + 21 + 20 = 1 1 1 tra 20 (S d ng bit ch n l l ) N uL ,ñ ts 0 5: Liên k t d li u 5a-14
  15. Ví d v mã Hamming Message to be sent: 1 0 1 1 1 0 1 0 1 1 B t ñ u t v trí 21 : Position 1 2 3 4 5 6 7 Ki m tra t t c các v trí có giá tr 2n: check bits 20 21 22 1 t i v trí 21 Calculate check bits: ð m s lư ng s 1 trong các bit 3 = 21 + 20 = 0 1 1 thông ñi p tương ng 5 = 22 + 20 = 1 0 1 6 = 22 + 21 + = 1 1 0 N u CH N, ñ t 1 v trí bit ki m 7 = 22 + 21 + 20 = 1 1 1 tra 21 (S d ng bit ch n l l ) N uL ,ñ ts 0 5: Liên k t d li u 5a-15
  16. Ví d v mã Hamming Thông ñi p ñ g i 1 0 1 1 1 0 1 1 0 1 1 B t ñ u t v trí 22 : V trí 1 2 3 4 5 6 7 Ki m tra t t c các v trí có giá tr 2n: Bit ki m tra 20 21 22 1 t i v trí 22 Tính giá tr bit ki m tra : ð m s lư ng s 1 trong các bit 3 = 21 + 20 = 0 1 1 thông ñi p tương ng 5 = 22 + 20 = 1 0 1 6 = 22 + 21 + = 1 1 0 N u CH N, ñ t 1 v trí bit ki m 7 = 22 + 21 + 20 = 1 1 1 tra 22 (S d ng bit ch n l l ) N uL ,ñ ts 0 5: Liên k t d li u 5a-16
  17. Ví d v mã Hamming Thông ñi p ban ñ u = 1011 Thông ñi p g i ñi = 1011011 V y làm th nào ñ có th xác ñ nh v trí bit b l i trong thông ñi p b ng cách s d ng mã Hamming ? 5: Liên k t d li u 5a-17
  18. S d ng mã Hamming ñ s a l i 1 bit Thông ñi p nh n ñư c: 1 0 1 1 0 0 1 1 0 1 1 0 0 1 V trí 1 2 3 4 5 6 7 2n: Bit ki m tra 20 21 22 Tính các bit ki m tra: 3 = 21 + 20 = 0 1 1 5 = 22 + 20 = 1 0 1 6 = 22 + 21 = 1 1 0 7 = 22 + 21 + 20 = 1 1 1 5: Liên k t d li u 5a-18
  19. S d ng mã Hamming ñ S a l i 1 bit Thông ñi p nh n ñư c 1 0 1 1 0 0 1 1 0 1 1 0 0 1 B t ñ u t v trí 20: V trí 1 2 3 4 5 6 7 Ki m tra t t c các v trí có giá tr 2n: Bit ki m tra 20 21 22 1 t i 20 Tính toán các bit ki m tra ð m s s 1 trong t t c các bit 3 = 21 + 20 = 0 1 1 tương ng c a thông ñi p và 5 = 22 + 20 = 1 0 1 v trí 20 và Giá tr ch n l c a s 6 = 22 + 21 = 1 1 0 ñ m này. 7 = 22 + 21 + 20 = 1 1 1 N u s ñ m này là m t s ch n, ch c ch n có m t trong b n bit Ch n l l : Không có l i các bit 1, 3, 5, 7 ñư c ki m tra b l i. 5: Liên k t d li u 5a-19
  20. S d ng mã Hamming ñ S a l i 1 bit Received message: 1 0 1 1 0 0 1 1 0 1 1 0 0 1 Ti p t c v i v trí 21 : Position 1 2 3 4 5 6 7 Ki m tra t t c các v trí có giá tr 2n: check bits 20 21 22 1 Calculate check bits: ð m s s 1 trong t t c các bit 3 = 21 + 20 = 0 1 1 tương ng c a thông ñi p và 5 = 22 + 20 = 1 0 1 v trí 21 và Giá tr ch n l c a s 6 = 22 + 21 = 1 1 0 ñ m này. 7 = 22 + 21 + 20 = 1 1 1 N u s ñ m này là m t s ch n, ch c ch n có m t trong b n bit Ch n l Ch n: L I trong các bit 2, 3, 6 ho c 7! ñư c ki m tra b l i. 5: Liên k t d li u 5a-20