›
›

Bài giảng môn Kỹ thuật truyền số liệu (Bản đẹp)

pdf 244 trang ngocly 720
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Kỹ thuật truyền số liệu (Bản đẹp)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_mon_ky_thuat_truyen_so_lieu_ban_dep.pdf

Nội dung text: Bài giảng môn Kỹ thuật truyền số liệu (Bản đẹp)

  1. K THUT TRUYN S LIU V K2 1. Ni dung: 5 Chng I: Tng quan v truyn s liu 5 Chng II: K thut truyn s liu 5 Chng III: Các nghi thc c s và thc t 5 Chng IV: Mng truyn s liu 2. Thi lng: 5 Lý thuyt: 45 tit 5 Thc hành: 30 tit
  2. NHNG IU CN BIT 1. Ging viên: ThS. Phan Trn Th Uyên email: phanuyentt@gmail.com 2. Cách tính im: • Kim tra cui k: 60% • Kim tra gia k, thc hành, chuyên , im danh: 40%. • im thng: 0.5/ ln vào im KTCK. 3. 2
  3. TÀI LIU THAM KHO ' [1]- Trn Vn S, Truyn s liu và mng thông tin s, 2005, NXB H Quc Gia TP.HCM ' [2]- Nguyn Hng Sn, K thut truyn s liu, 2009, NXB Lao ng Xã hi ' [3]- James F.Kurose, Computer Networking, 2005, Pearson Education, Inc 3
  4. 1.1. MÔ HÌNH H THNG TRUYN TIN C BN 4
  5. 1.2. S KHI H THNG THÔNG TIN S LIU T CÁC NGUN KHÁC TO MÃ HÓA MÃ HÓA MÃ HÓA GHÉP X LÝ THÍCH MÁY KHUÔN NGUN MT KÊNH KÊNH NG MÔI PHÁT TRNG T 010 010 010 010 010 ~/ NGUN TIN KÊNH NG TRUYN B TO GII MÃ GII MÃ GII MÃ PHÂN X LÝ THÍCH MÁY N B KHUÔN NGUN MT KÊNH KÊNH NG MÔI THU NHN 010 010 010 010 010 TRNG TIN N CÁC ÍCH NHN TIN KHÁC 5
  6. 1.3. CÁC PHNG TIN TRUYN DN Hu tuyn: 1. Loi cáp không xon: • Tín hiu tham chiu gia hiu in th (cng dòng in) so vi dây ni t. • Khong cách 50m, tc 19,2 kbps. 6
  7. 1.3. CÁC PHNG TIN TRUYN DN Hu tuyn: 2. Cáp xon ôi (twisted pair cable): • Không bc giáp (UTP). • Bc giáp (STP). 7
  8. 1.3. CÁC PHNG TIN TRUYN DN Hu tuyn: 3. Cáp ng trc (coaxial cable): • Loi mng (thinnet) + u ni BNC; • Loi dy (thicknet) + u ni 15 chân. 8
  9. 1.3. CÁC PHNG TIN TRUYN DN Hu tuyn: 4. Cáp si quang (fiber optic cable): 9
  10. 1.3. CÁC PHNG TIN TRUYN DN Hu tuyn: Mt ct ngang cáp si quang 10
  11. 1.3. CÁC PHNG TIN TRUYN DN Hu tuyn: Mt ct dc cáp si quang 11
  12. 1.3. CÁC PHNG TIN TRUYN DN Vô tuyn 1. Vi ba mt t 2. Thông tin v tinh 3. in thoi t bào 12
  13. 1.3. CÁC PHNG TIN TRUYN DN Vô tuyn: • Ph sóng in t 13
  14. 1.3. CÁC PHNG TIN TRUYN DN Vô tuyn • Bng tn sóng vô tuyn 14
  15. 1.3. CÁC PHNG TIN TRUYN DN Lan truyn sóng b mt: Signal propagation Transmit Receive antenna Earth antenna Ground-wave propagation (below 2MHz) 15
  16. 1.3. CÁC PHNG TIN TRUYN DN Lan truyn sóng tri: 16
  17. 1.3. CÁC PHNG TIN TRUYN DN Lan truyn sóng thng: Signal propagation Transmit Receive antenna antenna Earth Line-of-sight (LOS) propagation (above 30MHz) 17
  18. 1.4. MT S KHÁI NIM C BN • Tín hiu: 18
  19. 1.4. MT S KHÁI NIM C BN • Tn s ca tín hiu: Min thi gian Min tn s v v t 0 f v v f t t f f v v 2f t 2f f 19
  20. 1.4. MT S KHÁI NIM C BN • Ph ca tín hiu: khong tn s có tín hiu f = 300 Hz f(Hz) 300 600 Hz f(Hz) 600 700 Hz f(Hz) 700 f(Hz) 20
  21. 1.4. MT S KHÁI NIM C BN • Bng tn: mt di tn s gii hn t tn s thp nht n tn s cao nht. • Bng thông: là bng tn c gán cho mt user truyn nhn d liu. v 500 550 6000 6500 f Bandwidth = 6000 – 1000 = 5000 Hz Bandwidth = 6500 – 500 = 6000 Hz 21
  22. 1.4. MT S KHÁI NIM C BN 22
  23. 1.4. MT S KHÁI NIM C BN • Tc truyn: Công thc Shannon xác nh tc ti a cho mt kênh truyn: S CBlog (1  ) 2 N C: tc ti a ca kênh (dung lng kênh) B: bng thông ca kênh S/N: tđ s tín hiu trên nhiáu 23
  24. 1.4. MT S KHÁI NIM C BN • Baud rate (Rs) và Bit rate (R): R = Rs x log2M = Rs x m R: tc bit (bit/s) Rs: tc baud (symbol/s) M: s mc thay i tín hiu m: s bit mã hóa cho mt tín hiu • Công thc Nyquist xác nh tc ti a ca kênh: C = 2B x log2M = 2B x m 24
  25. BÀI TP 1 ng dây in thoi có bng thông 3200Hz. Gi sĉ ng truyn không nhiáu, dung lng 19200 bps. Cho bit ti a có bao nhiêu symbol khác nhau có th c truyn trên ng truyn. 25
  26. BÀI TP 2 Cho mt ng truyn có bng thông 4000Hz. Tå l tín hiu trên nhiáu theo công sut là 18 dB. Xác nh tc có th t c trên lý thuyt. 26
  27. 1.4. MT S KHÁI NIM C BN 1s 0001111 0 • Tc bit = 8 b/s • Tc baud = 4 s/s 27
  28. 1.4. CÁC PHNG THC TRUYN DN 1. ƒn công (simplex) 2. Bán song công (hafl-duplex) 3. Song công (duplex) 28
  29. CHNG II: K THUT TRUYN S LIU 1. Truyn dÇn bng tn gc và bng thông di 2. Mã hóa 3. Ghép kênh và tách kênh 4. Phát hin và sĉa sai 5. Nén d liu 6. Mô hình OSI 29
  30. 2.1.TRUYN DN BNG GC VÀ BNG THÔNG DI (Baseband và Passband) 1. Truyn dÇn bng gc/ bng tn cƒ s: • Bng tn kênh phù hp vi bng tn tín hiu  có th truyn trc tip bn tin. • Tuy nhiên, phù hp vi các tính cht ca kênh truyn, bn tin phi c mã hóa thành tín hiu phát, géi là mã ng dây (transmission encoding/ line encoding) 30
  31. 2.1. TRUYN DN BNG GC VÀ BNG THÔNG DI 2. Truyn dÇn bng thông di: • Tn s trung tâm ca kênh ln hƒn nhiu tn s cao nht ca tín hiu. • Trc khi phát, tín hiu phi c chuyn lên bng tn ca kênh, géi là iu ch (modulation). 31
  32. 2.2. LINE CODING 32
  33. POLAR ENCODING 1. NRZ (NonReturn to Zero): chå có 2 mc tín hiu: âm hoc dƒng. • NRZ-L (NRZ-Level) • NRZ-I (NRZ-Invertered) 33
  34. POLAR ENCODING 2. RZ (Return to Zero): tín hiu có 3 mc: âm, dƒng và zero. +v -v 3. Biphase: Manchester và Manchester vi sai. 34
  35. BIPOLAR ENCODING 1.AMI (Alternate Mark Inversion) 2.B8ZS (Bipolar 8 Zero Subtitution) 3.HDB3 (High Density Bipolar 3). 35
  36. AMI và PSEUDOTERNARY AMI Amplitude 0 1 0 0 1 1 1 0 Time Pseudoternary The 0s are positive and negative alternately 36
  37. BIPOLAR ENCODING 37
  38. BIPOLAR ENCODING 38
  39. U NHC IM LO¼I „U IÞM NH„þC IÞM NRZ • ƒn gin • Có thành phn mt chiu • Bng thông dùng hiu qu • Thiu kh nng ïng b RZ • ïng b bit hiu qu • Tc mã ti a bÍng 2 ln so vi NRZ Manchester và • ïng b tt (self clocking) • Tc mã ti a bÍng 2 Manchester vi sai • Thành phn DC = 0 ln so vi NRZ • Phát hin c lói AMI • Thành phn DC = 0 • Tc mã ti a bÍng 2 ln so vi NRZ • Không ïng b c khi có chuói bit 0 kéo dài B8ZS và HDB3 • ïng b bit rt hiu qu •Tc mã ti a bÍng 2 ln ngay c i vi chuói bit 0 so vi NRZ kéo dài •Phát hin c lói 39
  40. BÀI TP 1 40
  41. ÁP ÁN BT1 41
  42. BÀI TP 2 10100001111010 NRZ-L NRZ-I AMI Pseudo-Ternary Manchester Differential Manchester 42
  43. ÁP ÁN BT2 10100001111010 NRZ-L NRZ-I AMI Pseudo-Ternary Manchester Differential Manchester 43
  44. BÀI TP 3 44
  45. ÁP ÁN BT2 45
  46. 2.3. CHUN GIAO TIP BNG TN GC 1. ïng b 2. Phát hin sai 3. Bng thông 4. Giao thoa gia các symbol 46
  47. 2.4. IU CH GII IU CH S (Modulation – Demodulation) 1. AM (Amplitude Modulation) 2. FM (Frequency Mod.) 3. PM (Phase Mod.) 4. iêu ch kt hp biên và pha. 47
  48. 2.5. MÃ HÓA 1. Baudot (Emile Baudot) ' 5 bit ' dùng 2 mã letter và figure tng s lng mã 2. ASCII (American Standard Code for Information Interchange) ' 7 bit ' Ph bin nht hin nay c sĉ dāng trong giao tip d liu tun t. 3. Unicode ' 16 hoc 32 bit ' ang c nghiên cu và sĉ dāng 48
  49. MÃ BAUDOT $ “JAMES BOND 007 SAYS HI!” 4949
  50. MA ASCII 50
  51. 2.6. GHÉP KÊNH (Multiplexing) 1. FDM (Frequency Division Multiplexing)  FDMA (FDM Access) 2. TDM (Time Division Multiplexing)  TDMA 3. CDM (Code Division Multiplexing)  CDMA 51
  52. FDM 52
  53. TDM f 1 frame = 125μs t 1 frame = 125μs 53
  54. TDM • 1 frame time (F) ghép n kênh thông tin, tƒng ng n time slot (TS) • 1TS ghép c 8 bit tín hiu kênh # i • Tc truyn dÇn ca h thng: Rb = 8n/125μs = n.64 kbps • Dung lng ca h thng phā thuc s kênh n • Có 2 chuÅn cƒ bn: Châu Âu n= 32 (E1), Châu M n = 24 (T1) 54
  55. CU TRÚC KHUNG PCM 32 55
  56. CU TRÚC A KHUNG PCM 32 CHANNEL 14 CHANNEL 29 15 30 56
  57. CU TRÚC A KHUNG PCM 24 A 57
  58. PDH (Plesiosynchronous Digital Hierachy) Phƒng pháp ghép kênh TDM géi là cn ïng b PDH • Ghép xen liên tāc tng byte ca kênh #i vào tng khe thi gian. • Tín hiu ïng b khung, a khung, báo hiu c ghép vào a khung. • Sau khi b trí các luïng s vào khung ghép, cn hiu chånh tc bÍng phƒng pháp chèn. 58
  59. PDH CP CAO Ghép kênh PDH có 5 cp và 3 tiêu chuÅn khác nhau: • ChuÅn ghép kênh PDH Châu Âu, ký hiu là Ei • ChuÅn ghép kênh PDH BËc M, ký hiu là Mi (DSi) • ChuÅn ghép kênh PDH Nht Bn, ký hiu là DS (JDS) 59
  60. PDH CP CAO 60
  61. BAI TÂP Analog B=4kHz, PCM 8bit R = ? Digital 3 x 200 kbps MUX 61
  62. 2.7. CU TRÚC KÊNH TRUYN 1. Truyn ni tip (serial) 2. Truyn song song (parallel) 62
  63. TRUYN DN NI TIP • Bt ïng b: ïng b theo bit start và bit stop • ïng b: ïng b bÍng c hiu hoc ký t iu khin -> Bit-oriented 63
  64. TRUYN DN NI TIP • ïng b: ïng b bÍng ký t iu khin -> Character-oriented SYN SYN STX DATA ETX BCC SYN: sychronous character STX: start of text ETX: end of text BCC: Block check count 64
  65. MA ASCII 65
  66. TRUYN NI TIP BT NG B • ïng b bit 66
  67. TRUYN NI TIP BT NG B • ïng b bit 67
  68. TRUYN NI TIP BT NG B • ïng b ký t 68
  69. TRUYN NI TIP BT NG B • ïng b khung STX FR L ETX STX Start bit Stop bit F Frame contents (printable characters) ETX DLE STX DLE ETX DLE STX DLE Inserted Frame contents DLE DLE (binary data) DLE ETX • STX: Start of Text ETX: End of Text • DLE: Data Link Escape 69
  70. TRUYÊN NÔI TIÊP BÂT ÔNG BÔ • Hiu sut kém • Thích hp cho d liu truyn ngËt quãng và ngÇu nhiên v thi gian. • Dùng cho ng truyn tc thp. 70
  71. BAI TÂP Mã hóa chuói d liu “TIGER 2010” bÍng mã ASCII, parity l×, 1 stop bit. 1. Tính tng s bit truyn trên ng truyn. 2. Tính hiu sut ng truyn. 3. VÙ chuói bit truyn 71
  72. BAI TÂP T I G E R 2 0 1 0 START PARITY STOP BIT BIT BIT 72
  73. TRUYN NI TIP NG B • Không cn bit start /stop. • Phi có tín hiu ïng b riêng. • Truyn các khi d liu hoàn chånh. • Dùng cho ng truyn tc cao. 73
  74. TRUYN NI TIP NG B 1. ïng b bit: ' Time stamp (Clock encoding and extraction)  Gán thông tin ïng b vào d liu truyn  RZ, Manchester, differential Manchester ' Digital Phase-Lock-Loop  Dùng ng tín hiu ïng b riêng  Mã hóa thông tin phi m bo có s thay i bit trong mt khong thi gian nguïn clock tái ïng b  AMI, HDB3, B8ZS  Thích hp khi truyn mt khong cách ngËn  Tín hiu ïng b dá b suy gim trên ng truyn ' Hybrib: kt hp hai phƒng pháp trên 74
  75. ÔNG BÔ D LIÊU Transmiter Receiver Clock TxD RxD TimeStamp encoder Clock extract SIPO Local PISO circuit clock Bit stream TxC Manchester encoded signal (TxD/RxD) Extracted clock (RxC) Received data 75
  76. ÔNG BÔ D LIÊU Transmiter Receiver Bit TxD RxD Bit DPLL encoder decoder DPLL SIPO Local PISO clock xN local clock Hybrid Transmiter Receiver Clock TxD RxD encoder DPLL SIPO Local PISO clock xN local clock 76
  77. TRUYN NI TIP NG B 1. Character-oriented  Dùng các ký t iu khin: SYN, STX, ETX, DLE  Nghi thc BSC (Binary Synchronous Communication) byte stuffing 77
  78. BSC % nh dng khung ' Khung d liu SYN: Synchronous SOH: Start Of Header Id: Identity STX: Start Of teXt BCC: Block Check Count ETX: End Of teXt 78
  79. BSC - KHUNG AIÊU KHIÊN Connection establishment S S E point point con. S S E Polling Poll primary Y Y N request Y Y N add. Poll N N Q N N Q secondary Select S S E Selecting primary S S positive response Y Y N add. to select/ ready to Select Y Y ACK N N Q receive data secondary N N negative response to S S select/ not ready to S S E negative response Y Y NAK receive data Y Y O to poll/ not ready to N N N N T send data EOT: end of transmission ENQ: request to response 79
  80. BSC - KHUNG AIÊU KHIÊN Flow and error control S S Positive ACK of even S S Positive ACK of odd Y Y ACK frames/ Y Y ACK frames/ N N 0 Frame number 0 received N N 1 Frame number 1 received S S Negative ACK of even S S Wait and ACK/ Y Y NAK frames/ Y Y WACK ACK of previous frame/ N N Error in frame received N N Not ready to receive more Reverse interrupt/ S S S S Temporary delay/ Y Y Request for interrupt/ RVI Y Y TTD Temporary delayed but N N Urgent data to sen N N not relinquish the line 80
  81. BSC – BYTE STUFFING • M rng nghi thc BSC cho truyn nhn bn tin nh phân bt k. DLE (Data Link Escape): data transparency marker 81
  82. BSC ' c im: IBM (ISO 1745, ANSI X3.28) Half-duplex Multipoint Truyn dÇn ïng b hoc bt ïng b iu khin lói “Idle RQ” ' Hn ch: Chå truyn half-duplex Phā thuc mã iu khin Không kim soát lói cho các trng iu khin Không có kh nng m rng 82
  83. TRUYN NI TIP NG B 2. Bit-orientered  Dùng các mÇu bit iu khin (flag) bit stuffing  Nghi thc HDLC (High-level Data Link Control)  Nghi thc SDLC (Synchronous Data Link Control) 83
  84. HDLC • Truyn dÇn ïng b • Truyn dÇn theo khung • nh dng khung chung cho vic trao i d liu và iu khin 84
  85. HDLC – C IU KHIN • C là chuói 8 bit: 01111110 • Kt thúc khung này và bËt u khung khác • Bên thu quét tìm c ïng b • K thut chèn thêm bit (bit stuffing) c dùng tránh lÇn ln d liu ging c và c ' 0 c chèn thêm vào mói khi chuói 5 s 1 liên tip xut hin ' Nu b thu phát hin 5 s 1, nó kim tra bit k tip  Nu bit ó là 0, nó xóa bit 0 ó  Nu bit là 1 và bit th 7 là 0, nó bit ây là c  Nu bit th 6 và 7 u là 1, d liu 85
  86. HDLC – C IU KHIN • Mt s lói trùng c: 86
  87. HDLC – TRNG AIA CHI • Dùng nhn din trm gi hoc nhn khung • Thng dài 8 bit • Có th m rng thành bi s ca 8 bit • a chå “11111111” là a chå broadcast 87
  88. HDLC -TRNG AIÊU KHIÊN 88
  89. HDLC -TRNG AIÊU KHIÊN • Khác nhau tùy thuc vào loi khung ' Thông tin – d liu cn truyn n ngi dùng ' Giám sát – dùng ARQ ' Không ánh s – hó tr cho vic iu khin liên kt • 1 hoc 2 bit u tiên ca trung iu khin dùng nhn dng loi khung • Bit Poll/Final: chå có ý ngha khi là 1 ' Là Poll khi c gi t primary n secondary ' Là Final khi c gi t secondary n primary 89
  90. HDLC – HOAT ÔNG • Trao i khung thông tin, khung giám sát và khung không ánh s • 3 giai on ' Khi to kt ni ' Trao i d liu ' NgËt kt ni 90
  91. BISYNC va HDLC Feature BISYNC HDLC Transmission technique Async/Sync Sync Transmission mode Half-duplex Half/Full duplex Framing Start SYN SYN Flag Stop Characters Flag Frame formats Numerous 1 (3 types) Control information Header, control frames Header (1-2 bytes) Addressing Contention or polling Header Error detection LRC, CRC-16, CRC-12 CRC-CCITT Error checking Transmission block only Entire frame Error control Stop-and-wait Go-back-N or selective repeat Flow control WACK Sliding window Window size 1 7 or 127 Transparency DLE Bit stuffing 91
  92. BAI TÂP 1. Tính li hiu sut ng truyn ïng b khi phát chuói bit “TIGER 2010” 2. So sánh vi hiu sut ng truyn bt ïng b 3. Gi sĉ cn truyn vn bn cha 100, 200 và 500 ký t. So sánh hiu sut ng truyn ïng b và bt ïng b. 92
  93. 2.8. PHÁT HIN VÀ SA SAI 93
  94. PHÁT HIN SAI 94
  95. KIÊM TRA PARITY ' Parity chÑn: tng s bit 1, k c bit parity là s chÑn ' Parity l×: tng s bit 1, k c bit parity là mt s l× D a t a D a t a Parity bit ( ASCII ) B 1 B 2 B 3 B 4 B 5 B 6 B 7 (odd ) h 1 0 0 0 0 1 1 0 e 1 0 0 0 0 0 1 1 95
  96. KIÊM TRA PARITY • Chå dò c lói vi s l× bit sai • Không sĉa c lói • Hiu sut truyn thông tin kém. 96
  97. BLOCK SUM CHECK Block Sum Check (BSC): kt hp parity hàng và ct • Phát hin c lói sai mt s l× bit. • Dò c các lói sai mt s chÑn bit, ngoi tr nhng lói xy ra ïng thi trên c hàng và ct. • Chå sĉa c sai mt bit ƒn. D a t a Start D a t a Parity Stop B 1 B 2 B 3 B 4 B 5 B 6 B 7 (even) H 1 0 0 0 0 0 0 1 1 0 E 1 1 0 0 0 0 0 1 0 0 L 1 0 1 0 0 0 0 1 0 0 L 1 0 1 0 0 0 0 1 0 0 O 1 1 1 0 0 0 0 1 1 0 BCC 1 1 0 1 1 1 1 0 1 0 (odd) 97
  98. BLOCK SUM CHECK MODEM5 6 KPH PV 98
  99. CYCLIC REDUNDANCY CHECK 1111 +1010 0101 11001 x11 11001 11001 101011 99
  100. CYCLIC REDUNDANCY CHECK 1. Tính FCS Tx 2n MF  R 2xn M R Q  P P • M: d liu cn truyn (k bit) • P: a thc sinh (n+1 bit) • F: FCS (n bit) • T: frame truyn i (k+n bit) 2. Kim tra: Tx 2nMR  T x2nMR R R  Q    Q P P P P 100
  101. CYCLIC REDUNDANCY CHECK • Cách khác xác nh FCS: a thc ' M = 111101 M(x) = X5 + X4 + X3 + X2 + 1 ' P = 1101 P = X3 + X2 + 1 ; FCS có 3 bits (n = 3) ' D liu dch trái n bits: x3M(x) = X8 + X7 + X6 + X5 + X3 X8 + X7 + X6 + X5 + X3 X3 + X2 + 1 X8 + X7 + X5 X6 + X3 X6 + X5 + X3 X5 X5 + X4 + X2 X4 + X2 T = 111101011 X4 + X3 + X X3 + X2 + X X3 + X2 + 1 FCS = 011 ; X + 1 101
  102. CYCLIC REDUNDANCY CHECK M P 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 T 1 1 1 0 1 1 0 1 FCS 111101011 0 1 1 102
  103. CYCLIC REDUNDANCY CHECK • Các lói phát hin c ' Tt c các lói bit ƒn ' Tt c các lói kép nu P có ít nht 3 toán hng ' Mt s l× lói bt k nu P cha 1 tha s (X+1) ' Bt k lói chùm nào mà chiu dài ca chùm nhë hƒn chiu dài FCS ' Hu ht các lói chùm ln hƒn 103
  104. CYCLIC REDUNDANCY CHECK • 4 P c sĉ dāng rng rãi ' CRC-12: X12 + X11 + X3 + X2 + X + 1 ' CRC-16 : X16 + X15 + X2 + 1 ' CRC-CCITT: X16 + X12 + X5 +1 ' CRC-32: X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1 104
  105. CYCLIC REDUNDANCY CHECK Message + FCS0 + FCS1 + FCS2 + FCSn-2 + FCSn-1 P1 P2 Pn-2 Pn-1 X X X X + + EE + DD CC + BB + AA EE DD P = 110101 P = 111011 + CC + EE + DD CC + BB AA BB P = 101011 + AA 105
  106. CYCLIC REDUNDANCY CHECK M=1010001101 A B C D E Input P=110101 Initial 00000 1010001101 Step 1 0 0 0 0 1 1 1 + Step 2 000100 Step 3 0 0 1 0 1 1 E E Step 4 010100 Step 5 1 0 1 0 0 0 DD Step 6 111010 Step 7 0 1 1 1 0 1 x2 + Step 8 111011 Step 9 0 1 1 1 1 0 CC Step 10 111111 BB Step 11 0 1 0 1 1 0 Step 12 101100 x4 + Step 13 1 1 0 0 1 0 Step 14 001110 x5 AA Step 15 0 1 1 1 0 0 FCS = 01110 106
  107. BÀI TP • M = 100101101 • P = 1001101 • VÙ sƒ ï mch và tính FCS 107
  108. CYCLIC REDUNDANCY CHECK M=100101101 A B C D E F Input P=1001101 Initial Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Step 9 Step 10 Step 11 Step 12 Step 13 Step 14 Step 15 Step 16 108
  109. 2.9. MT MÃ HÓA (cryptology) • Mt mã khóa bí mt • Mt mã khóa công khai 109
  110. MT MÃ KHÓA BÍ MT Thám mã (Oscar) Bn rõ Bn mã Nguïn tin B mã hóa Kênh m B gii mã Nhn tin (Alice) KD KD (Bob) Kênh an toàn Nguïn khóa 110
  111. MT MÃ KHÓA BÍ MT 1.Các h mt thay th: • H mã dch vòng: C = M + k mod n M = C - k mod n k: giá tr khóa n: giá tr mã Ký tABCDEFGHI J KLM Mã 0 1 2 3 4 5 6 7 8 9 10 11 12 Ký tNOPQRSTUVWXYZ Mã 13 14 15 16 17 18 19 20 21 22 23 24 25 111
  112. MT MÃ KHÓA BÍ MT • Mã Xeda k = 3 • M = meet me at sunset 12.44.19 • C = 15.7.7.22 112
  113. MT MÃ KHÓA BÍ MT • H mt dùng bng thay th:  Có 26! Các bng thay th  H mã dch vòng là trng hp riêng ca mã thay th. 113
  114. MT MÃ KHÓA BÍ MT • Các h mt thay th khác: ABC J. K. L. S W DEF M. N. O. T U X . . . z . GHI P. Q. R. V Y • Meet me at sunset 114
  115. MT MÃ KHÓA BÍ MT Vào 3. Các h mt hoán v: • H mt Spartang: ME E T vào theo quy lut Ra ME dòng, ra theo quy lut ct AT S C = M AUTEMTN UNSE T 115
  116. MÂT MA KHOA BI MÂT 4. Các b mã tích 5. Các h mt mã dòng 116
  117. MÂT MA KHOA CÔNG KHAI Thám mã (Oscar) Bn rõ Bn mã Nguïn tin B mã hóa Kênh m B gii mã Nhn tin (Alice) KEB KDB (Bob) KEB KEA • KE: khóa công khai (dùng mã hóa) • KD: khóa bí mt (dùng gii mã) • Mã hóa: C = EKE (M) -1 • Gii mã: M = E KD (C) 117
  118. MÂT MA KHOA CÔNG KHAI 1. H mt RSA (Rivest – Shannon – Adleman) 2. H mt xp balo 3. H mt McEliece 4. H mt ElGamal 5. H mt trên ng cong Elliptic QUY TRÌNH CHUNG: 1. To khóa 2. Trao i khóa 3. Mã hóa 4. Gii mã 118
  119. 2.10. NÉN D LIU 1. ƒn gin mã cho các ch s 2. Mã hóa tƒng i 3. Loi bë nhng ký t ging nhau 4. Mã hóa Huffman 5. Nén Fax 119
  120. NÉN D LIU 1. ƒn gin mã cho các ch s (Run-length encoding /packed decimal) • Dùng cho message gïm các ch s Thay 7 bit mã hóa ASCII bÍng 4 bit BCD • Mã BCD thay vì ASCII • Có th dùng 4 bit thp i vi các thông tin y STX Ctrl ‘2’ ‘6’ ETX BCC C m S ký t BCD C óng Báo hiu có packed decimal 120
  121. NÉN D LIU 2. Mã hóa tƒng i • Chå gi phn thay i so vi giá tr c: 121
  122. NÉN D LIU 3. Loi bë nhng ký t ging nhau • Nu có nhiu hƒn 3 ký t ging nhau STX Ctrl ‘A’ Length ‘B’ ‘C’ Ctrl ‘.’ Length ETX BCC ký t nén ký t không nén 122
  123. NÉN D LIU 4. Mã hóa Huffman: SINH VIÊN 123
  124. NÉN D LIU 5. FAX: SINH VIÊN 124
  125. 2.11. MÔ HÌNH OSI 125
  126. MÔ HÌNH OSI 126
  127. MÔ HÌNH OSI 127
  128. MÔ HÌNH OSI 128
  129. CHNG III: CÁC NGHI THC VÀ C Sú THČC T Data Link Control Flow Control Error Control 129
  130. 3.1. AIÊU KHIÊN DONG • Bo m bên phát không gi d liu quá nhanh • Ngn nga vic tràn b m • Khái nim thi gian: -Thi gian truyn (tframe): thi gian cn thit gi tt c các bit d liu lên ng truyn. - Thi gian lan truyn (tprop): thi gian cn thit 1 bit i t nguïn n ích. 130
  131. AIÊU KHIÊN DONG 131
  132. AIÊU KHIÊN DONG 132
  133. STOP AND WAIT IRQ 133
  134. STOP AND WAIT IRQ • Thi gian tng cng:   TD n(2tprop tframe ) • Hiu sut ng truyn: n t 1 U  frame   a TD 1 2 d t R d a prop V  t L LV frame R 134
  135. STOP AND WAIT IRQ 135
  136. STOP AND WAIT IRQ • c im ' c dùng ch yu trong các ng dāng character- oriented (byte-oriented) ' Sĉ dāng kênh truyn hot ng trong ch half- duplex • Cƒ ch hot ng ' Nguïn phát d liu (di dng các frame) ' ích nhn d liu và tr li bÍng ACK ' Nguïn i ACK trc khi phát tip d liu ' ích có th ngng bÍng cách không gi ACK ' Thích hp khi chå có vài frame có kích thc ln • D liu ln c chia thành các frame có kích thc nhë ' Kích thc b m có gii hn ' Lói c phát hin sm ' Khi có lói, chå cn truyn li frame nhë ' Ngn nga 1 trm chim ng truyn lâu 136
  137. SLIDING WINDOWS • Cƒ ch hot ng: ' Cho phép nhiu frame truyn ïng thi ' Bên thu có b m vi kích thc W ' Bên phát có th truyn ti a W frame mà không cn i ACK ' Cƒ ch ánh s th t cho các frame ' ACK có cha s ca frame k tip ang mong i ' S th t c quay vòng bi kích thc cĉa s (modulo 2k) 137
  138. SLIDING WINDOWS 138
  139. SLIDING WINDOWS 139
  140. 3.2. IU KHIN LòI Go Back N Selective repeat 140
  141. ARQ (Automatic Repeat Request) ' qun lý lói và yêu cu truyn li ' Phân loi:  Idle RQ (stop-and-wait) • Dùng vi cƒ ch iu khin dòng stop-wait • c dùng ch yu trong truyn d liu là ký t hay byte thông tin (character-oriented or byte-oriented)  Continuous RQ • Dùng vi cƒ ch iu khin dòng sliding-window • c dùng ch yu trong truyn d liu là bit thông tin (bit-oriented) • c chia làm hai loi tùy theo cách thc sĉa lói: selective reject và go-back-N 141
  142. ARQ • A gi mt I-Frame (Information Frame) n B • A i tr li: • ACK-Frame -> A gi tip d liu • NAK-Frame –> A gi li d liu • Không nhn c tr li – A gi li sau thi gian time-out • Lp li các bc trên. 142
  143. ARQ stop and wait Lói: • E1: I-Frame không n c ích; • E2: I-Frame n c ích nhng ni dung sai; • E3: ACK-Frame không n ích hay ACK-Frame n ích nhng ni dung ACK-Frame b sai. 143
  144. ARQ stop and wait • Sĉa lói E1 ' Sĉ dāng timer: nguïn sau khi gi i mt I-Frame thì khi ng b m, sau khong thi gian i T mà cha nhn c tín hiu ACK thì xem nh I- Frame cha ti và gi li frame này. 144
  145. ARQ stop and wait Sĉa lói E2: • Implicit retransmission: sĉ dāng timer • Explicit retransmission: NAK-Frame (negative ack frame) Primary (P) I(N) I(N) E2 I(N) NAK(N) I(N) ACK(N) I(N) I(N) Secondary (S) 145
  146. ARQ stop and wait Sĉa lói E3 ' Lói lp li frame (duplicated frame): dùng chå s tun t frame (sequential number) 146
  147. ARQ stop and wait • Hot ng tt 147
  148. Bài 1: Mã hóa chuói d liu “TIGER 2010” bÍng mã ASCII, parity l×, 1 stop bit. • Tính hiu sut ng truyn bt ïng b và ïng b khi phát d liu trên. So sánh. • Gi sĉ cn truyn vn bn cha 100, 200 và 500 ký t. So sánh hiu sut ng truyn ïng b và bt ïng b. Bài 2: Ngi ta dùng k thut PCM 16 bit lu tr âm nhc s. Tn s tín hiu âm nhc có th t n 20 kHz.Tính khong thi gian ti a có th lu tr nhc s trên USB 2G. Bài 3: Cho chuói d liu: 1010100111010100. VÙ dng sóng iu ch 16-PSK và 16-QAM. So sánh 2 phƒng pháp trên. 148
  149. Go back N-ARQ • RR = receive ready = ACK = acknowledge • REJ = reject = NAK = negative acknowledge • Da trên cƒ ch sliding window • A gi liên tāc các I-Frame n B • B chå nhn I-Frame theo úng chå s tun t • Truyn li tt c k t Frame sai u tiên. Primary (P) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) I(N) ACK(N) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) Secondary (S) 149
  150. Go back N-ARQ Kiu lói c:ng tƒng t nh trong Idle RQ • E1: I-Frame không n c ích • E2: I-Frame n c bên nhn, nhng ni dung I-Frame sai. • E3: ACK-Frame không n c ích, hay n c nhng ni dung ACK-frame b sai. Primary (P) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) E1 I(N) ACK(N) E1 E3 I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+5) Secondary (S) E2 150
  151. Go back N-ARQ • Sĉa lói E1: ' Sĉ dāng danh sách truyn li (Retransmission list) ' Sĉ dāng timer • Sĉa lói E2 ' Implicit Retransmission: dùng timer ' Explicit Retransmission: dùng NAK-Frame • Sĉa lói E3 ' Sĉ dāng chå s tun t frame (sequential number) 151
  152. Selective Repeat ARQ • Cƒ ch hot ng ' Tƒng t nh Go-Back-N, ngoi tr vic chå gi li các frame b NAK hoc time-out ' Bên nhn có th nhn frame thông tin không theo úng chå s tun t th t frame thông tin truyn không c bo m và bên nhn phi có buffer lu li các frame n không theo úng chå s tun t • Vn kích thc cĉa s 152
  153. Selective Repeat ARQ 153
  154. Selective Repeat ARQ Retransmitted I(N+2) I(N+3) I(N+4) mode I(N+1) I(N+1) I(N+2) I(N+3) I(N) I(N) I(N) I(N+1) I(N+2) I(N) I(N+1) I(N+2) I(N+3) I(N+4) I(N+2) I(N+5) I(N+6) Primary (P) E1 Timeout retransmitted I(N) ACK(N) V(s)=N+1 Secondary (S) I(N) I(N+1) I(N+3) I(N+4) I(N+2) I(N+5) I(N+6) I(N) I(N+1) I(N+3) I(N+3) I(N+3) I(N+5) I(N+6) I(N+4) I(N+4) I(N+2) Sĉa lói E1: •Sĉ dāng timer •Sĉ dāng danh sách truyn li 154
  155. Selective Repeat ARQ • Sĉa lói E2: ' Implicit Retransmission: dùng timer ' Explicit Retransmission: dùng NAK-Frame. • Sĉa lói E3: ' Sĉ dāng chå s tun t frame 155
  156. SO SÁNH 0 1 2 3 4 5 2 3 4 5 6 7 0 K1 2 K2 3 K4 5 K6 AC ACK NA ACK AC ACK AC 0 1 EDDD 2 3 4 5 6 Error Discarded frames Go-back-N protocol 0 1 2 3 4 5 2 6 7 0 K1 2 2 3 K4 5 2 AC ACK NAK ACK AC ACK ACK 0 1 E 3 4 5 2 6 Error Buffered frames frames 2-5 released Selective repeat 156
  157. HIÊU SUÂT KHI AIÊU KHIÊN LÔI 1 P • Stop-and-wait: U  1 2a I 1 P N 2a  1 L  • Go-back-N:  J 1 2aP U N(1- P) L N 2a  1 KL(2a 1)(1- P  NP) LI 1- P N 2a  1 • Selective repeat: U  JN(1 P) N 2a  1 KL 1 2a 157
  158. CHNG IV: MANG TRUYÊN SÔ LIÊU 1. K thut chuyn mch kênh 2. K thut chuyn mch gói 3. Mng LAN, WAN và MAN 4. Mng X.25 5. xDSL (chuyên ) 6. Mng NGN (chuyên ) 158
  159. 4.1. KY THUÂT CHUYÊN MACH KÊNH • nh hng thông tin • Chuyn tip thông tin 159
  160. KY THUÂT CHUYÊN MACH KÊNH (circuit switching) 1. c im: • Thit lp ng truyn: to kt ni, truyn d liu và ngËt kt ni. • Sĉ dāng phƒng pháp ghép kênh TDM. • ng truyn hoàn toàn b chim gi trong sut thi gian kt ni. • trá thp • ðn nh. 160
  161. CHUYÊN MACH KÊNH – BAO HIÊU 2. Báo hiu kênh chung (Common Channel Signaling) ' Các tín hiu iu khin truyn trên kênh truyn c lp vi kênh truyn thoi ' Mt kênh tín hiu iu khin chung cho mt s kênh thuê bao => H thng báo hiu s 7 (Signaling System Number 7 - SS7) 161
  162. CHUYÊN MACH KÊNH – BAO HIÊU 162
  163. CHUYÊN MACH KÊNH – BAO HIÊU • Các phn tĉ trong mng báo hiu: ' Signaling point - SP (im iu khin tín hiu) ' Signal transfer point – STP (im trao i tín hiu) ' Control plane ' Information plane 163
  164. CHUYÊN MACH KÊNH – BAO HIÊU 164
  165. CHUYÊN MACH KÊNH – BAO HIÊU Calling Originating Terminating Called customer Line central office Trunk central office Line customer On-hook On-hook On-hook Off-hook 1 Time Dial tone 2 Off-hook(Connect) 3 (Address) 9 Off-hook 10 "Wink" On-hook Address 11 Audio ringing tone 5a 4 Ringing(20 Hz) Off-hook(Answer) Off-hook(Address) 6 Audio ringing teeminated 7 Ringing Terminated Customer connected-Conversstion ensues On-hook 8 On-hook 8 Disconnect Signaling on a Typical Completed Call 165
  166. CHUYÊN MACH KÊNH – BAO HIÊU 166
  167. CHUYÊN MACH KHÔNG GIAN • c phát trin cho môi trng tƒng t • ng kt ni riêng bit mt cách vt lý • Chuyn mch ma trn im kt ni (crossbar matrix) ' S im kt ni tå l vi bình phƒng s trm ' Vic mt các im kt ni dÇn ti vic không có kh nng kt ni qua im ó ' Hiu sut sĉ dāng ca các im kt ni kém  Khi tt c các trm c kt ni, chå có vài im kt ni c dùng ' Non-blocking 167
  168. CHUYÊN MACH KHÔNG GIAN 1 TÂNG • N>M: concentration • N=M: distribution • N<M: expansion N inputs M outputs N inputs/ outputs Crossbar matrix Triangular switch 168
  169. CHUYÊN MACH KHÔNG GIAN AA TÂNG • Gim s im kt ni ' Gia tng hiu sut sĉ dāng • Nhiu ng kt ni qua mng gia 2 trm ' tin cy gia tng • iu khin phc tp ' Trì hoãn khi tín hiu truyn qua chuyn mch gia tng tđ l vi s tng ca chuyn mch • Có kh nng blocking ' Dùng vùng m u vào (input buffer), u ra (output buffer) hay bên trong chuyn mch (internal buffer) 169
  170. BÔ CHUYÊN MACH 3 TÂNG 170
  171. CHUYÊN MACH THI GIAN • Chia nhë các dòng d liu tc thp dùng chung mt ng truyn s liu tc cao • Các gói nhë c iu khin bi mt b iu khin logic truyn t input n output • Các loi chuyn mch theo thi gian ' Time-division Multiplexing BUS (TDM BUS) ' Time Slot Interchange (TSI) ' Time-multiplexed Switching 171
  172. CHUYÊN MACH THI GIAN-TDM BUS • Da trên nguyên lý ca TDM ïng b ' Tt c các ng truyn (I/O) c ni vào mt Bus chung ' Thi gian trên Bus c chia thành các time slots ' Mt kt ni c thit lp gia hai ng truyn (I/O) bÍng cách gán c nh mt time slot • Kích thc chuyn mch b gii hn bi tc d liu trên Bus • c sĉ dāng trong các chuyn mch va và nhë 172
  173. TIME SLOT INTERCHANGE 173
  174. TIME SLOT INTERCHANGE • Tt c các ng (I/O) c ni n mt b phân hp kênh (MUX/ DEMUX) theo k thut bt ïng b • Mt kt ni c thit lp bÍng cách hoán chuyn các time slot trong frame • Kích thc ca chuyn mch b gii hn bi tc ca b nh iu khin • Thng c dùng làm phn tĉ chuyn mch cƒ bn trong các cƒ ch chuyn mch theo thi gian a tng. 174
  175. TIME–MULTIPLEXED SWITCHING • Mt bin i ca phƒng pháp chuyn mch theo thi gian trong ó mói ngõ nhp là mt dòng TDM • Cu hình chuyn mch có th thay i trên mói time slot • Thng c sĉ dāng kt hp vi phƒng pháp TSI to ra các chuyn mch a tng • trách blocking, cu hình ti thiu là 3 tng • Cu hình thông thng ' TST ' TSSST ' STS ' SSTSS ' TSTST 175
  176. TIME–MULTIPLEXED SWITCHING 176
  177. CHUYÊN MACH KÊNH- TÌM NG (Routing) • Chc nng: ' Chå nh kt ni thông sut t thuê bao géi n thuê bao c géi. • Các yêu cu t ra trong vn tìm ng: ' tin cy ' Hiu qu ' Kh nng chu ng lói (kh nng co giãn) • Các phƒng pháp tìm ng: ' Trc tip (Direct Routing) ' Phân cp (Alternate Hierachical Routing) ' Tìm ng ng (Dynamic Routing) 177
  178. DYNAMIC ROUTING • ng i thit lp gia hai thuê bao thay i tùy theo kh nng ti và bng thông ca ng truyn ti thi im thit lp kt ni • Mt s phƒng pháp tìm ng ng: ' Da vào thng kê bin ng trong mng (ti, bng thông, ) theo thi gian, còn c géi là Alternate Routing ' Da vào bin ng trong mng c cp nht vào bng routing các node chuyn mch trong mng, còn c géi là Adaptive Routing ' Kt hp c hai phƒng pháp này 178
  179. ALTERNATE ROUTING • Các ng i có th gia 2 node c lit kê trc • B chuyn mch nguïn chén la các ng thích hp • ng i c lit kê theo th t u tiên, vi kt ni trc tip c u tiên hàng u. 179
  180. ADAPTIVE ROUTING • Cho phép các b chuyn mch phn hïi li vi tình hình lu thông trên mng • Chi phí ln hƒn cho vic qun tr • DTM (dynamic traffic management) ' Dùng b iu khin trung tâm tìm ng d phòng khi nghÙn mng ' Mói node chuyn mch A cp nht các thông tin sau cho b iu khin trung tâm  S trung k rnh i n các im lân cn A  Hiu sut sĉ dāng CPU ca A  o lu lng t A n các node khác không kt ni trc tip ' B chuyn mch trung tâm sÙ cho bit ng i “tt” khi các ng ni trc tip không còn kh nng 180
  181. 4.2. KY THUÂT CHUYÊN MACH GOI (packet switching) • D liu c truyn theo gói nhë cha d liu ca ngi dùng và các thông tin iu khin • Thông tin iu khin: cha thông tin cho vic tìm ng • Các gói c nhn, lu tm thi và chuyn cho node k tip • Gói c xĉ lý theo 2 hng: -Datagram - Virtual circuit 181
  182. KY THUÂT CHUYÊN MACH GOI 182
  183. CHUYÊN MACH GOI - DATAGRAM 183
  184. CHUYÊN MACH GOI - DATAGRAM • Gói c xĉ lý c lp • Các gói có th i theo bt c ng i nào thích hp • Các gói có th n ích không theo th t gi • Gói có th tht lc trên ng i • Bên nhn là sËp xp li các gói theo trt t và khôi phāc các gói tht lc 184
  185. CHUYÊN MACH GOI - VIRTUAL CIRCUIT 185
  186. CHUYÊN MACH GOI - VIRTUAL CIRCUIT • Khi to kt ni trc trc khi gi gói i • Gói cha thông tin v ng i “o” thay vì a chå ích • Không cn quyt nh tìm ng cho các gói • Kt thúc bÍng yêu cu hy kt ni • Mói ng i o c gán mt mã s riêng (Virtual Circuit Identifier – VCI) • Không phi là mt ng dành riêng 186
  187. CHUYÊN MACH GOI - VIRTUAL CIRCUIT 187
  188. VIRTUAL CIRCUIT - DATAGRAM • Virtual circuit ' Mng có th cung cp s tun t và iu khin lói ' Các gói c chuyn nhanh hƒn do không cn tìm ng ' tin cy kém hƒn: mt mt node sÙ làm hëng tt c các kt ni i qua node ó • Datagram ' Không cn giai on thit lp kt ni  Tt hƒn nu s gói nhë ' Linh ng hƒn  ng i c quyt nh sao cho tránh các phn mng ang nghÙn kÕt 188
  189. VIRTUAL CIRCUIT - DATAGRAM • External virtual circuit, internal virtual circuit ' ng dành riêng thông qua mng • External virtual circuit, internal datagram ' Mng xĉ lý mói gói riêng bit ' Các gói khác nhau cho cùng mt mch o bên ngoài có th i các ng bên trong khác nhau ' Mng lu tr các gói ti node ích sËp xp li th t • External datagram, internal datagram ' Các gói c i xĉ mt cách c lp bi c mng và user • External datagram, internal virtual circuit ' Ngi dùng ngoài không thy các kt ni ' Ngi dùng ngoài gi tng gói mt ' Mng thit lp kt ni lun lý 189
  190. EXTERNAL VIRTUAL CIRCUIT - DATAGRAM OPERATION 190
  191. INTERNAL VIRTUAL CIRCUIT - DATAGRAM OPERATION 191
  192. GIAO TIÊP GIA TRAM VA CAC NODE MANG ' nh hng kt ni (Connection oriented)  Trm yêu cu kt ni lun lý (virtual circuit)  Tt c các gói c ánh du thuc v kt ni ó và c ánh s th t  Mng phân phát các gói theo th t ' nh hng không kt ni (Connectionless)  Các gói c xĉ lý c lp  Phā thuc vào dch vā datagram 192
  193. TIM NG • Vn phc tp, quyt nh i vi mng chuyn mch gói • Các c tính yêu cu: ' Chính xác ' ƒn gin ' ðn nh ' Công bÍng ' Ti u ' Hiu qu 193
  194. YÊU TÔ QUYÊT AINH CHIÊN THUÂT TIM NG 1. Thi im quyt nh  Trên cƒ s VC hoc Datagram 2. Nƒi quyt nh  Phân tán: c thc hin ti các node Z Node sĉ dāng các thông tin cāc b Z Thông tin t các node k cn Z Thông tin t các node trên ng tim nng  Tp trung: Z Thu thp thông tin t tt c các node  Ti nguïn 194
  195. CHIÊN THUÂT TIM NG 1. Fixed routing 2. Flooding routing 3. Random routing 4. Adaptive routing 195
  196. FIXED ROUTING 196
  197. FIXED ROUTING • Mt l trình c nh cho mói ng i t nguïn n ích • Tt c các ng i qua mng u ã c thit lp t trc và không cp nht theo các bin i v các iu kin ti, trong mng • ng i c xác nh dùng gii thut ti thiu chi phí 197
  198. FLOODING ROUTING • Không cn thông tin mng • Mói node trên mng u có th gi gói n các node ni vi nó • Node nhn sÙ gi li gói lên tt c các kt ni ngoi tr kt ni va nhn gói này • Cui cùng mt s copy ca gói sÙ n ích • Gói c ánh s duy nht sao cho các copy trùng nhau sÙ b loi bë • Node có th ghi nh các gói ã i qua, giúp cho mng không quá ti nhiu • Gói có th cha thông tin v s chng ng, dùng gii hn hay kt thúc quá trình truyn. 198
  199. FLOODING ROUTING 199
  200. RANDOM ROUTING • Node sÙ chén mt ng truyn các gói nhn c • Vic chén la có th là ngÇu nhiên hoc xoay vòng • Có th chén da trên vic tính toán xác sut • Không cn thông tin mng • L trình tìm c thông thng không phi là ng có chi phí ti thiu hoc s chng nhë nht 200
  201. ADAPTIVE ROUTING • Quyt nh tìm ng thay i khi các iu kin trên mng thay i • Cn bit các thông tin v mng • Quyt nh là mt hàm phc tp • Cân i gia cht lng mng và chi phí • Phn ng quá nhanh có kh nng gây dao ng • Quá chm dÇn n không còn thích hp • „u im: ' Hiu sut c ci thin ' Tr giúp iu khin nghÙn mng ' H thng phc hp 201
  202. ADAPTIVE ROUTING • Distributed Adaptive Routing ' Thông tin mng c trao i nh k, sau ó c phân b v li các node làm nhim vā tìm ng cp nht li bng routing ti node ' áp ng c vi nhng thay i trng thái ca mng, nhng ïng thi c:ng làm tng lu lng thông tin trong mng • Centralized Adaptive Routing ' Thông tin mng c trao i nh k nhng c tp trung v mt máy ch trong mng làm nhim vā routing ' áp ng c vi nhng thay i tc thi trong mng, tuy nhiên hot ng ca toàn mng phā thuc máy ch. 202
  203. ADAPTIVE ROUTING • Isolated adaptive routing 'Mói node trên mng t ng cp nht bng routing da vào thông tin trao i 'Gi các gói trên các liên kt ra có hàng i ngËn nht 'Có th thêm các u tiên cho các ích 'Phù hp vi các mng có kích thc nhë và n nh 203
  204. SO SANH Circuit Switching Datagram Packets Virtual Circuit Packets ng truyn dÇn dành ng truyn dÇn ng truyn dÇn riêng không dành riêng không dành riêng D liu truyn liên tāc D liu truyn theo gói D liu truyn theo gói nhanh cho ng nhanh cho ng nhanh cho ng dāng tƒng tác dāng tƒng tác dāng tƒng tác Thông báo không c Thông báo có th c Thông báo c lu tr lu tr lu tr cho n khi cho n khi phân phát phân phát ng truyn dÇn ng i c thit lp ng i c thit lp c thit lp cho toàn cho mói gói cho toàn b quá trình b quá trình trao i trao i Trá do quá trình thit Trá truyn các gói Trá do quá trình thit lp lp + trá truyn các gói Tín hiu bn nu bên Ngi gi có th c Ngi gi c thông nhn không sÑn sàng thông báo nu các gói báo nu các gói không không c phân phát c phân phát 204
  205. Circuit Switching Datagram Packets Virtual Circuit Packets Quá ti sÙ khóa vic Quá ti sÙ tng thi Quá ti có th khóa thit lp gian trá ca gói vic thit lp và tng thi gian trá ca gói Chuyn mch cƒ in Node chuyn mch Node chuyn mch hoc c iu khin nhë nhë bi máy tính User chu trách nhim Mng có th sÙ chu Mng có th sÙ chu khi các thông báo b tht trách nhim cho các trách nhim cho chuói lc gói ƒn l× các gói Thng không cn Chuyn i tc và Chuyn i tc và chuyn i tc và bng mã bng mã bng mã Bng thông c nh Bng thông linh ng Bng thông linh ng Sau khi ã thit lp, Tn kém d liu iu Tn kém d liu iu không cn d liu iu khin cho mói gói khin cho mói gói khin cho gói 205
  206. 4.3. MANG TRUYÊN SÔ LIÊU X.25 • Giao tip gia máy ch và mng chuyn mch gói công cng • Ph bin trong các mng chuyn mch gói và chuyn mch gói ISDN • nh ngha 3 lp ' Vt lý ' Liên kt ' Gói X.25 Interface 206
  207. X.25 – 3 l÷p • Vt lý ' Giao tip gia trm và liên kt vi node ' DTE: user equipment ' DCE: node ' Dùng c t lp vt lý X.21 ' Cung cp vic truyn d liu tin cy thông qua liên kt vt lý ' D liu là chuói các frame • Liên kt ' Link Access Protocol Balanced (LAPB) • Gói ' External virtual circuits ' Kt ni lun lý (virtual circuits) gia các thuê bao 207
  208. X.25 – Virtual Circuit • Dch vā mch o ' Virtual Call (SVC – Switched Virtual Circuit)  Virtual circuit c to ng cho mói giao dch ' Permanent virtual circuit  Virtual circuit c gán trc c nh  Không cn thit lp và xóa kt ni ' Fast Select call  Dùng truyn thông báo/lnh nhë (<128 octet) trong quá trình thit lp/xóa kt ni 208
  209. X.25 – Açnh d½ng gói 209
  210. X.25 – Gói dċ liãu • S VC (12 bits) gïm 4 bit chå s nhóm + 8 bit chå s kênh. ' Thông thng 2 trng này c xem nh mt ' Dùng chå th loi kt ni hoc kênh gia các DTE ' Các loi kt ni khác nhau cho phép nhiu phiên giao dch gia cùng mt cp DTE ' Có th lên n 4095 kênh lun lý trên cùng mt ng giao tip vt lý • Q bit (Qualifier bit): không c nh ngha trong chuÅn, dùng phân bit gói (Q=0 là gói cha d liu ngi dùng, Q=1 là gói cha thông tin iu khin) • M bit (More bit): chå th nhiu gói sÙ tip theo. 210
  211. X.25 – Gói dċ liãu • Mng chuyn mch gói công cng có kích thc gii hn cho các gói (thông báo sÙ c phân thành nhiu gói) ' Ngoi tr gói cui cùng, các gói sÙ có bit M c bt (M=1) • D bit – bÍng 0 khi gói này là mt phn ca gói b phân mnh, bÍng 1 khi gói c tái hp ' C:ng c dùng iu khin dòng  Khi D=0, iu khin dòng c thc hin cāc b (gia DTE và cāc b DCE)  Khi D=1, iu khin dòng c thc hin gia DTE và DTE xa • P(R) – chå s nhn tun t • P(S) – chå s gi tun t 211
  212. X.25 – Gói 8iu khißn • 6 nhóm: thit lp kt ni, iu khin dòng, giám sát, xác nhn, chuÅn oán, ngËt quãng • Gói thit lp kt ni ' 4 loi: Call Request, Incoming Call, Call Accepted, và Call Connected ' c dùng trong giai on thit lp mch o • Gói iu khin dòng ' 3 loi: Receive Ready (RR), Receive Not Ready (RNR), và Reject (REJ) ' c dùng trong giai on truyn d liu (các gói u cha P(R)) 212
  213. X.25 – Gói 8iu khißn • Gói giám sát ' Bao gïm: Restart Request/Indication, Clear Request/Indication, Reset Request/Indication ' Restart Request c dùng trong tình hung xu (host crash) xóa VC do DTE này ang gi ' Clear Request dùng xóa VC (c chå ra trong VC number) ' Reset Request c dùng reset chå s nhn/gi tun t v 0 trong ch truyn d liu 213
  214. X.25 – Gói 8iu khißn • Gói xác nhn ' Dùng xác nhn các yêu cu trc ó (cho Restart, Clear, Reset, và Interrupt) • Gói chuÅn oán ' Do mng to ra cho māc ích chuÅn oán lói • Gói ngËt quãng ' c truyn xen trong quá trình truyn d liu, không cha chå s gi/nhn tun t. Ngha là gói ngËt quãng không là i tng ca quá trình iu khin dòng. 214
  215. X.25 - Multiplexing • DTE có th to 4095 mch o ïng thi vi các DTE khác trên mt kt ni DTC-DCE • Gói cha s mch o 12 bit • Cách ánh s mch o 215215
  216. X.25 – Set và Reset • Reset ' Khi to li virtual circuit ' S tun t c t bÍng 0 ' Các gói ang quá cnh b mt ' Tùy vào các protocol cp cao khôi phāc li các gói b mt ' Kích hot bi vic mt các gói, sai s tun t, nghÙn mch, mt internal virtual circuit • Restart ' Tƒng ƒng vi yêu cu xóa tt c các virtual circuit ' E.g. mt tm thi vic truy cp mng 216
  217. X.25 – Thă tāc thit lÉp kt níi • DTEa 8 DCEa 8 PSN 8 DCEb 8 DTEb (DTEa mun kt ni vi DTEb) ' DTEa nhn mt virtual circuit number (VCN) ' DTEa gi gói call-request cho DTEb (cha VCN, a chå DTEa, a chå DTEb) ' DCEa tìm ng i bng qua mng PSN cho gói này n DCEb ' DCEb nhn mt VCN mi và gi gói incoming-call n DTEb (gói cha VCN mi và các thông tin a chå nguïn/ích) ' DTEb chp nhn kt ni bÍng cách gi gói call- accepted qua DCEb n DCEa ' DCEa nhn c gói call-accepted và gi gói call- connected ti DTEa • Sau quá trình này, DTEa và DTEb có th gi các gói d liu qua li 217
  218. X.25 – Thă tāc gi¿i phóng kt níi • DTEa 8 DCEa 8 PSN 8 DCEb 8 DTEb (DTEa mun xóa kt ni vi DTEb) ' DTEa gi gói clear-request ti DCEa ' DCEa gi gói clear-indication ti DTEb (thông qua DCEb) ' DTEb gi clear-indication ti DTEa (thông qua các DCEb và DCEa) 218
  219. Virtual Call 219
  220. X.25 – Phân m¿nh (segmentation) • Xét tình hung các trm A, B, C, D kt ni vi nhau A - B - C - D. Các loi gói c nh ngha nh sau ' A – B: gói có kích thc 1500 bytes ' B – C: gói có kích thc 1000 bytes ' C – D: gói có kích thc 1500 bytes • A mun gi mt gói y n D, nó phi gi các gói 1500 bytes n B. B phi phân nhë các gói này hƒn na (segmentation/fragmentation) 220
  221. X.25 – Phân m¿nh (segmentation) • gii quyt vn này, C phi có kh nng nhn bit mt gói phân mnh và tái hp nó truyn cho D • X.25 cho phép quá trình phân mnh thông qua các bit M và D. Các bit này cho phép các trm nhn din các gói phân mnh và tái hp nó, và xác nhn nó (ack), ngha là không xác nhn các gói phân mnh, chå xác nhn khi các gói phân mnh ã c tái hp thành mt gói 221
  222. X.25 • iu khin dòng và iu khin sai ' HDLC • Chuói các gói ' Chuói y các gói ' Cho phép khi d liu ln c truyn qua mng vi kích thc gói nhë hƒn mà không mt tính toàn vÕn ca khi ' 2 loi gói  Các gói A • M bit 1, D bit 0 • Chiu dài gói ti a  Các gói B • Phn còn li ' Các gói A (có th là không có gói A nào) c theo sau bi gói B 222
  223. LOCAL AREA NETWORK (LAN) 1. c im: • Tc cao: vài chāc Mbps • Gii hn v khong cách: Không quá vài km • Mng riêng cāc b • Xây dng trên cƒ s chia s× môi trng: Broadcasting packets 2. Ąng dāng: • Office LANs • Backbone LAN: Kt ni các mng LAN tc thp • Storage area networks: Chia s× thit b lu tr trên mng tc cao 223
  224. CÂU TRUC CUA LAN  Môi trng truyn dÇn  Network Interface Card (NIC)  Mói NIC có a chå vt lý duy nht 224
  225. CÂU TRUC TRANSCEIVER 225
  226. ETHERNET 1. Lch sĉ phát trin • 1970: radio network ALOHA in Hawaii • 1973: Metcaff và Boggs phát minh Ethernet, random access, wired net • 1979: DIX (Digital, Intel và Xerox ) Ethernet II standard 10 Mbps • 1985: IEEE 802.3 LAN 10 Mbps • 1995: Fast Ethernet 100 Mbps • 1998: Gigabit Ethernet • 2002: 10 Gigabit Ethernet 226
  227. 2. IEEE 802.3 và Ethernet • 1-persistent CSMA-CD • Algorithm: • Nu ng truyn trng thái idle, bËt u truyn tin, Nu không, sang bc 2 • Nu ng truyn busy, tip tāc nghe cho n trng thái idle sÙ bËt u truyn tin • Nu phát hin xung t khi truyn tin, dng ngay quá trình truyn tin và truyn tính hiu jamming (random bit sequence) • Sau khi truyn jamming, i mt khong thi gian ngÇu nhiên (tbackoff), và tip tāc thĉ truyn tin 227
  228. 3. Flow chart 228
  229. 4. Original Ethernet và thông s • Tc : 10 Mbps • Chiu dài khung: 512 bits = 64 bytes • Time Slot: 512 bits / 10 Mbps = 51.2 μsec • Chiu dài tuyn: 2500 meters + 4 repeaters 229
  230. 5. IEEE 802.3 Ethernet và thông s hot ng • time Slot: 512 bits • InterFrameGap: 96 μsec • AttemptLimit: 16 • BackoffLimit: 10 • JamSize: 32 bits • MaxFrameSize: 1518 bytes • MinFrameSize: 512 bits (64 bytes) 6. IEEE 802.3 MAC Frame • Preamble: synchronization, 7 bytes of 10101010 • Start of Frame Delimiter (SFD): 10101011 230
  231. • IEEE 802.3 MAC Frame o Destination address  Single  Group  Broadcast: 11 11 o Source Addresses  Local or global o Global addresses (246 possible)  First 24 bits assigned to vendors (OUI)  Next 24 bits assigned by vendors  CISCO: 00-00-0C  3COM: 02-60-8C 231
  232. o Length: # of bytes in Information field  Max frame: 1518 excluding Preamble + FSD  Max information bytes: 1500 (Hexa: 05DC) o Pad: ensures min frame of 64 bytes o FCS: CCITT-32 CRC, calculated for addresses, length, information, and pad fields  NIC discards frames with improper lengths or failed FCS 232
  233. • DIX Ethernet frame format o DIX: Digital, Intel, Xerox: joint specification o Type: Identify protocol of PDU in information field, e.g. IP, ARP  0800: IP  0806: ARP  8137: Netware IPX  8160: NetBIOS 233
  234. • IEEE 802.3 Physical layer ` ` Thick coax: Stiff, hard to work with T-connection flatky 234
  235. • Ethernet hub & switch Twisted Pair: cheap, easy to work with Twisted Pair: cheap Reliable Bridging increase scalability Star-topology CSMA-CD Separable collision domains Full duplex operation 235
  236.  Bus & hub o Cu hình bus  Tt c các trm chia s× dung lng bus (ví du: 10 Mbps)  Chå 1 tram thc hin phiên truyn dÇn ti mt thi im o Hub ktnicáctrmtheohìnhsao  Méi phiên truyn dÇn u i qua hub  Chå 1 trm c truyn ti mt thi im  Full Duplex operation (FDX) o FDX, mt trm có th ïng thi nhn và gĉi tin o 100 Mbps Ethernet in FDX  200 Mbps transfer rate (lý thuyt) oCác trm kt ni phi có FDX adapter cards oPhicó switching hub o Ethernet truyn thng sĉ dāng Half Duplex (HDX) 236
  237. • Fast Ethernet: IEEE 802.3 100 Mbps •Gigabit Ethernet: IEEE 802.3 1 Gbps 237
  238. • 10 Gigabit Ethernet: IEEE 802.3 10 Gbps 238
  239. • Mt ví dā v trin khai mng ethernet 239
  240. • 802.11 Wireless LAN • c ißm: o Dá trin khai, giá thành thp oCó kh nng truy nhp thông tin mng méi nƒi o Hó tr các thit b cá nhân o Công sut tín hiu thay i theo không gian và thi gian o Tín hiu có th b truy nhp trái phép o Ph tín hiu b gii hn. 240
  241. Các tiêu chuÅn l÷p vÉt lý căa IEEE 802.11 241
  242. Mõt sí mô hình phát trißn m½ng WLAN 242
  243. Mõt sí mô hình phát trißn m½ng WLAN 1. Wireless Ethernet Bridge 2. Outdoor Antenna 3. PVC Thinnet Cable 7. Cat5 UTP Cable 4. Thin Ethernet Network Card 8. Cat5 Patch Cables 5. BNC T Connector 9. 10 Base-T Ethernet Hub 6. 50 Ohm Terminator 10. 10 Base-T Network Card 243
  244. TÔNG KÊT VÊ LAN • IEEE 802: LAN  802.1: DLL chia thành MAC và LLC  802.2: LLC  802.3: Ethernet LAN with CSMA-CD  802.4: Token bus  802.5: Token ring  802.11: Wi-Fi  802.16: WiMAX o Ethernet, fast ethernet o Wireless LAN 244