Xem mẫu

  1. Chương 4: T ng M ng M c tiêu H c cái gì: Nguyên t c tri n khai d ch v Các d ch v c a t ng M ng c a t ng M ng: Nguyên t c ñ nh tuy n: l a ch n ð nh tuy n (L a ch n ñư ng ñi ñư ng ñi) ð nh tuy n phân c p M r ng Ph m vi Giao th c IP Cách th c router ho t ñ ng Giao th c ñ nh tuy n trên Internet Nâng cao: IPv6, multicast N i mi n Liên mi n Cài ñ t nh ng d ch v này trên Internet như th nào Ki n trúc Router IPv6 NAT, PAT multicast routing 4: Network Layer 4a-1
  2. Ch c năng c a t ng M ng Chuy n gói tin t máy tính g i application ñ n máy tính nh n transport network data link Giao th c t ng M ng có m t trên physical network network data link network t t c máy tính, router data link physical data link physical physical Ba ch c năng cơ b n: network data link physical network L a ch n tuy n ñư ng: Tuy n data link ñư ng gói tin ñi t ngu n ñ n physical ñích. Thu t toán ñ nh tuy n network network data link data link physical Chuy n m ch: Router chuy n gói physical tin t m t ñ u vào này ra ñ u ra network data link application thích h p physical transport network Thi t l p tuy n ñư ng: m t s data link physical ki n trúc m ng ñòi h i tuy n ñư ng gói tin ñi qua ph i ñư c thi t l p trư c 4: Network Layer 4a-2
  3. Mô hình D ch v t ng M ng ?: Ch n Mô hình d ch v nào c a “kênh truy n” ñ V n ñ quan tr ng nh t chuy n gói d li u t nơi mà t ng M ng ph i tr l i g i ñ n nơi nh n ? : Tr u tư ng hóa d ch v ð m b o băng thông không? ð m b o t c ñ nh n ñ u không (không có hi n tư ng jitter)? Không m t mát ? ? ?M ch o hay ð m b o th t ? Có thông báo v tình tr ng t c ngh n cho bên g i không ? ?M ch gói? 4: Network Layer 4a-3
  4. Chuy n m ch o Tuy n ñư ng t ñích ñ n ngu n gi ng như m ch trong m ng ñi n tho i Quan tr ng : Hi u su t Thi t l p k t n i d c theo tuy n ñư ng Thi t l p và ðóng k t n i trư c khi truy n d li u M i packet mang ñ nh danh m ch o là VC identifier (Không ph i ñ a ch máy ñích) T t c router trên tuy n ñư ng duy trì tr ng thái c a k t n i ñi qua Kênh truy n t ng giao v n ch liên quan ñ n hai th c th ñ u cu i Tài nguyên c a ñư ng truy n (Băng thông, B ñ m) ph i ñư c c p phát cho m i m ch o ð ñ t ñư c hi u su t như m ng ñi n tho i. 4: Network Layer 4a-4
  5. M ch o: Giao th c báo hi u (Signal) ð Thi t l p và ðóng m ch o (VC) Có trong ATM, Frame-relay, X.25 Không ñư c s d ng trên Internet ngày nay application 6. Nh n d li u application transport 5. Chuy n d li u network 4. Thi t l p k t n i 3. Ch p nh n transport data link 1. Kh i t o 2. Cu c g i ñ n network data link physical physical 4: Network Layer 4a-5
  6. M ng chuy n m ch gói: Mô hình Internet Không c n thi t l p ñư ng truy n t ng M ng routers: Không duy trì tr ng thái các k t n i ñi qua no network-level concept of “connection” Gói tin ñư c ñ nh tuy n d a trên ñ a ch gói nh n Các gói tin có th ñi theo nh ng tuy n ñư ng khác nhau application application transport transport network data link 1. G i d li u 2. Nh n d li u network data link physical physical 4: Network Layer 4a-6
  7. Mô hình D ch v t ng M ng Có ñ m b o ? Ki n trúc Mô hình Ph n h i M ng D ch v Băng thông M t Th t Th i gian T c ngh n Internet best effort none no no no no (inferred via loss) ATM CBR constant yes yes yes no rate congestion ATM VBR guaranteed yes yes yes no rate congestion ATM ABR guaranteed no yes no yes minimum ATM UBR none no yes no no Mô hình d ch v trên Internet : Intserv, Diffserv Chương 6 4: Network Layer 4a-7
  8. Chuy n M ch hay Chuy n Gói? Internet ATM D li u trao ñ i gi a máy tính Phát tri n t M ng ñi n tho i D ch v mang tính “co giãn”, H i tho i c a con ngư i: không ñòi h i ch t ch th i Yêu c u nghiêm ng t v gian. Th i gian và ð tin c y Thi t b ñ u cu i “thông minh” ð m b o ch t lư ng d ch Có th thích nghi, Ki m soát, v Kh c ph c l i Thi t b ñ u cu i ñơn gi n “Lõi” m ng ñơn gi n, Ph c Máy ñi n tho i t p ñ t “Rìa” Ph c t p ñ t bên trong Nhi u ki u môi trư ng truy n d n M ng Các ñ c ñi m khác nhau Không th có chung ch t lư ng d ch v 4: Network Layer 4a-8
  9. S d ng M ch o ñ cài ñ t D ch v t ng M ng ð cung c p thêm m t s ch c năng, có th l a ch n công ngh m ch o – ví d Virtual Private Network (VPN) 4: Network Layer 4a-9
  10. Chuy n m ch gói : Cài ñ t các ch c năng M ng cơ b n nh t Thư ng ch cung c p d ch v cơ b n nh t: chuy n gói tin ñi t nơi G i ñ n nơi Nh n. T p trung vào mô hình Internet theo ki u “c g ng t i ña” này 4: Network Layer 4a-10
  11. ð nh tuy n ð nh tuy n M c tiêu: xác ñ nh tuy n ñư ng “t t” (dãy các router) trên m ng t nút g i ñ n nút nh n. ð th ñ xây d ng thu t toán ñ nh tuy n: 5 ð nh là Router B 3 C C nh là các ñư ng k t n i 2 5 tr c ti p A 2 1 F 3 Giá c a c nh: ð tr , Chi 1 2 phí, hay M c ñ T c ngh n D E 1 4: Network Layer 4a-11
  12. ð nh tuy n : Các Yêu c u khác M t vài Yêu c u khác M nh và Tin c y T i ưu và có Hi u qu Phân tán, T qu n, Không có ñi m h ng duy nh t ðơn gi n ð nh tuy n Công b ng M c tiêu: xác ñ nh tuy n ñư ng “t t” (dãy các router) trên m ng t nút g i ñ n nút nh n. 4: Network Layer 4a-12
  13. Minh h a Ch c năng T ng M ng routing and call setup 4: Network Layer 4a-13
  14. Không gian ð nh tuy n ð nh tuy n Ai quy t ñ nh tuy n ñư ng? • Nút g i quy t ñ nh • M ng quy t ñ nh Có bao nhiêu tuy n ñư ng t nút G i s ñ n nút Nh n d? • ð nh tuy n nhi u ch ng • ð nh tuy n nhi u ch ng Tuy n ñư ng có thay ñ i theo t i c a m ng không? • ð nh tuy n thích nghi • ð nh tuy n tĩnh … 4: Network Layer 4a-14
  15. Phân lo i Thu t toán ð nh tuy n Thông tin Toàn c c hay ð ng hay Tĩnh? Phân tán ? Tĩnh (Static): Toàn c c (Global): Router r t ít thay ñ i M i router ñ u bi t v toàn b topo c a ñ th ð ng (Dynamic): Thu t toán “link state” Router thay ñ i thư ng xuyên Phân tán (Decentralized): C p nh t ñ nh kỳ M i router ch bi t v router và Ch y l i thu t toán khi có 1 giá ñ n các router hàng xóm giá ñư ng ñi thay ñ i Th c hi n quá trình trao ñ i thông tin v i các “hàng xóm” Thu t toán “distance vector” 4: Network Layer 4a-15
  16. Thu t toán ð nh tuy n Link-State Thu t toán Dijkstra Ký hi u: T t c các nút ñ u bi t ñư c v c(i,j): Giá ñư ng ñi t i t i j. topo c a toàn m ng Có giá tr vô cùng n u i và j Bi t ñư c do các thông ñi p không có ñư ng tr c ti p qu ng cáo ñư c g i qu ng D(v): Giá hi n t i c a ñư ng bá ñi t i ñích V T t c các nút có thông tin gi ng nhau p(v): Nút k trư c V trong tuy n ñư ng ñ n V Tính toán ñư ng ñi t t nh t ñ n t t c các nút khác N: T p h p các ñ nh ñã xác T o ra B ng ð nh tuy n ñ nh ñư c ñư ng ñi ng n nh t Sau k bư c tính toán, xác ñ nh ñư c ñư ng ng n nh t tói k ñích 4: Network Layer 4a-16
  17. Thu t toán Dijsktra 1 Kh i t o: 2 N = {A} 3 V i t t c các nút v 4 N uvk v iA 5 thì D(v) = c(A,v) 6 n u không D(v) = infty 7 8 L p 9 Tìm w không trong N sao cho D(w) nh nh t 10 B sung w vào N 11 C p nh t D(v) cho t t c v k v i w và không trong N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* Giá m i t i v ho c là giá cũ ñ n v ho c ñư ng ñi ng n nh t 14 ñ n w c ng thêm kho ng cách t w t i v */ 15 Cho ñ n khi t t c các nút ñ u n m trong N 4: Network Layer 4a-17
  18. Ví d v Thu t toán Dijsktra Bư c T pN D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) 0 A 2,A 5,A 1,A vô cùng vô cùng 1 AD 2,A 4,D 2,D vô cùng 2 ADE 2,A 3,E 4,E 3 ADEB 3,E 4,E 4 ADEBC 4,E 5 ADEBCF 5 3 B C 5 2 A 2 1 F 3 1 2 D E 1 4: Network Layer 4a-18
  19. Th o lu n v Thu t toán Dijsktra ð ph c t p Thu t toán: n nút M i vòng l p: C n ki m tra t t c các nút w không trong N n*(n+1)/2 : O(n**2) B ng thu t toán “m n” hơn: O(nlogn) Tình hu ng Dao ñ ng: Ví d khi Chi phí kênh truy n = kh i lư ng d li u truy n qua 1 A A A A 1+e 2+e 0 0 2+e 2+e 0 D 0 0 B D 1+e 1 B D B D 1+e 1 B 0 0 0 e 0 0 1 1+e 0 e 1 C C C C 1 e … Tính l i ð nh tuy n … Tính l i … Tính l i Ban ñ u 4: Network Layer 4a-19
  20. Thu t toán ð nh tuy n Distance Vector L p: C u trúc D li u B ng Distance Liên t c di n ra cho ñ n khi không còn thông ñi p M i nút có m t B ng riêng trao ñ i. M i hàng ng v i m t ñích c th T k t thúc: Không có “tín M i c t ng v i m t hàng xóm có hi u” ñ d ng l i ñư ng k t n i tr c tiêp Không ñ ng b : Ví d : trong nút X, v i ñích Y qua hàng xóm Z: Các nút sau khi g i/ nh n thông ñi p không b phong t a! Kho ng cách t X t i X = Y, qua Z là ch ng ti p Phân tán: D (Y,Z) M i nút ch truy n thông Z = c(X,Z) + minw{D (Y,w)} v i hàng xóm 4: Network Layer 4a-20