›
›

Mạng máy tính - Chương 04: Tầng mạng

pdf 34 trang vanle 2780
Download
Bạn đang xem 20 trang mẫu của tài liệu "Mạng máy tính - Chương 04: Tầng mạng", để 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:

  • pdfmang_may_tinh_chuong_04_tang_mang.pdf

Nội dung text: Mạng máy tính - Chương 04: Tầng mạng

  1. Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng Mạng máy tính ThS. NGUYỄN CAO ĐẠT E-mail:dat@cse.hcmut.edu.vn
  2. Bài giảng 9: Tầng Mạng(t.t) Tham khảo: Chương 4: “Computer Networking – A top-down approach” Kurose & Ross, 5th ed., Addison Wesley, 2010. Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 2
  3. Chương 4: Tầng Mạng  4.1 Giới thiệu  4.4 Các giải thuật định  4.2 Bên trong bộ định tuyến tuyến là gì?  Trạng thái liên kết  Véc-tơ Khoảng cách  4.3 IP: Internet Protocol  Định tuyến phân cấp  Định dạng gói tin   Đánh địa chỉ IPv4 4.5 Định tuyến trong  ICMP Internet   IPv6 RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 3
  4. ICMP: Giao thức thông điệp kiểm soát Internet  sử dụng bởi máy tính và bđt để liên lạc thông tin tầng-mạng Loại Mã Chú giải  báo cáo lỗi: máy, mạng, cổng, 0 0 phản hồi echo (ping) giao thức không liên lạc được 3 0 mạng đích ko liên lạc được 3 1 máy đích ko liên lạc được  yêu cầu/phản hồi gói echo (sử 3 2 g/thức đích ko liên lạc được dụng bởi ping) 3 3 cổng đích ko liên lạc được  nằm ở tầng “trên” IP: 3 6 mạng đích không biết  th/điệp ICMP được mang trong 3 7 máy đích không biết gói tin IP 4 0 giảm tốc độ nguồn (kstn –  thông điệp ICMP: loại, mã cùng với không dùng) 8 byte đầu của gói tin IP mà gây ra 8 0 truy vấn echo (ping) lỗi 9 0 quảng bá tuyến đường 10 0 tìm tuyến đường 11 0 TTL hết hạn 12 0 mào đầu IP bị lỗi Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 4
  5. Traceroute và ICMP  Nguồn gửi một loạt khúc UDP  Khi thông điệp ICMP tới, nguồn cho đích sẽ tính RTT  khúc đầu tiên có TTL =1  Traceroute thực hiện việc này 3  khúc thứ 2 có TTL=2, v.v. lần  số cổng không cố định Điều kiện để ngừng lại  Khi gói tin thứ n đến bđt n:  Khúc UDP đến được máy đích  BĐT loại bỏ gói tin  Máy trả về gói ICMP “máy đích  Và gửi lại nguồn một thông điệp không tới được” (loại 3, mã 3) ICMP (loại 11, mã 0)  Khi nguồn nhận được những  Thông điệp bao gồm cả tên và ICMP này, nó sẽ dừng lại. địa chỉ IP của bđt Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 5
  6. Chương 4: Tầng Mạng  4.1 Giới thiệu  4.4 Các giải thuật định  4.2 Bên trong bộ định tuyến tuyến là gì?  Trạng thái liên kết  Véc-tơ Khoảng cách  4.3 IP: Internet Protocol  Định tuyến phân cấp  Định dạng gói tin   Đánh địa chỉ IPv4 4.5 Định tuyến trong  ICMP Internet   IPv6 RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 6
  7. IPv6  Động lực ban đầu: không gian địa chỉ 32-bit sẽ được cấp phát hết trong t/g ngắn.  Động lực khác:  định dạng mào đầu sẽ giúp tăng tốc xử lý/chuyển tiếp gói tin  thay đổi mào đầu để hỗ trợ QoS Định dạng gói tin IPv6:  mào đầu có độ dài cố định 40 byte  không cho phép phân khúc Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 7
  8. Mào đầu IPv6 (tt) Mức ưu tiên: xác định mức ưu tiên giữa các gói tin Nhãn luồng: xác định các gói tin trong cùng “luồng”. (khái niệm “luồng” chưa thực sự chuẩn). Mào đầu tiếp theo: xác định dữ liệu của giao thức tầng trên Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 8
  9. Những thay đổi khác từ IPv4  Tổng kiểm tra: được loại bỏ hoàn toàn để giảm thời gian xử lý tại mỗi thiết bị  Tùy chọn: cho phép, nhưng nằm ngoài phần mào đầu, chỉ định bởi trường “Next Header”  ICMPv6: phiên bản mới của ICMP  những thông điệp bổ sung, vd: “Gói tin quá lớn”  những chức năng quản lý nhóm gửi-nhiều-đích (multicast) Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 9
  10. Chuyển tiếp Từ IPv4 Tới IPv6  Không thể nâng cấp tất cả bđt ngay một lúc được  Làm sao để mạng có thể làm việc với cả các bộ định tuyến IPv4 và IPv6?  Tạo đường hầm: IPv6 được mang như là dữ liệu của gói tin IPv4 giữa các bđt IPv4 Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 10
  11. Tạo đường hầm A B E F Góc nhìn luận lí: đường hầm IPv6 IPv6 IPv6 IPv6 A B E F Góc nhìn vật lí: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 11
  12. Tạo đường hầm A B E F Góc nhìn luận lí: đường hầm IPv6 IPv6 IPv6 IPv6 A B C D E F Góc nhìn vật lí: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Flow: X Src:B Src:B Flow: X Src: A Dest: E Dest: E Src: A Dest: F Dest: F Flow: X Flow: X Src: A Src: A data Dest: F Dest: F data data data A-tới-B: E-tới-F: B-tới-C: B-tới-C: IPv6 IPv6 IPv6 bên trong IPv6 bên trong Trường Đại Học Bách Khoa Tp.HCM IPv4 IPv4 MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 12
  13. Chương 4: Tầng Mạng  4.1 Giới thiệu  4.4 Các giải thuật định  4.2 Bên trong bộ định tuyến tuyến là gì?  Trạng thái liên kết  Véc-tơ Khoảng cách  4.3 IP: Internet Protocol  Định tuyến phân cấp  Định dạng gói tin   Đánh địa chỉ IPv4 4.5 Định tuyến trong  ICMP Internet   IPv6 RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 13
  14. Tương tác giữa định tuyến, chuyển tiếp giải thuật định tuyến bảng chuyển tiếp cục bộ gtrị mào đầu đầu ra 0100 3 0101 2 0111 2 1001 1 giá trị trong mào đầu của gói tới 0111 1 3 2 Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 14
  15. Trừu tượng hóa bằng đồ thị 5 v 3 w 2 5 u z 2 3 1 1 x y 2 Đồ thị: G = (N,E) 1 N = tập các bđt = { u, v, w, x, y, z } E = tập các đg liên kết ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Lưu ý: Trừu tượng hóa bằng đồ thị cũng hữu dụng trong những phạm trù mạng khác Ví dụ: P2P, với N là tập các thành viên và E là tập các kết nối TCP Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 15
  16. Trừu tượng hóa bằng đồ thị: chi phí 5 • c(x,x’) = chi phí của đường (x,x’) v 3 w 2 5 - vd: c(w,z) = 5 u z 2 3 1 • chi phí có thể luôn bằng 1, hoặc 1 nghịch đảo với băng thông, x y 2 1 hoặc nghịch đảo với tắc nghẽn chi phí của đường đi c(x1, x2, x3, , xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) Câu hỏi: Đường đi nào ít chi phí nhất giữa u và z ? Giải thuật định tuyến: tìm ra đường đi ít tốn kém nhất Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 16
  17. Phân loại giải thuật định tuyến Thông tin tổng quát hay phân Tĩnh hay động? tán? Tĩnh: Tổng quát:  tuyến đường chậm thay  tất cả bđt đều có thông tin đầy đổi theo t/gian đủ về đồ hình mạng và chi phí liên kết Động:  g/thuật “trang thái kết nối”  tuyến đường thay đổi Phân tán: nhanh hơn  bđt biết hàng xóm kết nối vật lý  cập nhật theo chu kì tới nó, chi phí tới họ  để phản ánh lại sự thay đổi  quá trình tính toán, trao đổi trong chi phí đường liên kết thông tin với hàng xóm được lặp đi lặp lại  g/thuật “véc tơ khoảng cách” Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 17
  18. Chương 4: Tầng Mạng  4.1 Giới thiệu  4.4 Các giải thuật định  4.2 Bên trong bộ định tuyến tuyến là gì?  Trạng thái liên kết  Véc-tơ Khoảng cách  4.3 IP: Internet Protocol  Định tuyến phân cấp  Định dạng gói tin   Đánh địa chỉ IPv4 4.5 Định tuyến trong  ICMP Internet   IPv6 RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 18
  19. Một g/thuật trạng thái-liên kết giải thuật Dijkstra Kí hiệu:  tất cả nốt đều biết đồ hình  c(x,y): chi phí từ nốt x tới y; mạng, chi phí liên kết = ∞ nếu không phải hàng xóm  thực hiện bởi “phát tán trạng trực tiếp thái liên kết”  D(v): giá trị hiện tại của chi phí  mọi nốt có cùng th/tin của tuyến đường từ nguồn tới  tính tuyến đường rẻ nhất từ 1 đích v nốt tới tất cả nốt khác  p(v): nốt liền trước trên đường  tạo bảng chuyển tiếp cho nốt đi từ nguồn tới v đó  N': tập các nốt mà đã biết  lặp: sau k lần lặp, biết được được đường đi xác định rẻ nhất tuyến đường rẻ nhất tới k đích tới chúng Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 19
  20. Giải thuật Dijsktra 1 Khởi tạo: 2 N' = {u} 3 với mọi nốt v 4 nếu v kề với u 5 thì D(v) = c(u,v) 6 ngoài ra D(v) = ∞ 7 8 Lặp 9 tìm w không thuộc N' sao cho D(w) là min 10 thêm w vào N' 11 cập nhật D(v) cho tất cả v kề với w và ko thuộc N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* chi phí mới tới v hoặc là chi phí cũ tới v hoặc là chi phí 14 tuyến ngắn nhất tới w cộng với chi phí từ w tới v */ 15 tới khi tất cả các nốt đều thuộc N' Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 20
  21. Giải thuật Dijkstra: Ví dụ Bước N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 2,u 3,y uxy 4,y 3 3,y uxyv 4,y 4 uxyvw 4,y 5 uxyvwz 5 v 3 w 2 5 u z 2 3 1 1 x y 2 1 Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 21
  22. Giải thuật Dijkstra: ví dụ (2) Kết quả cây đường đi ngắn nhất từ u: v w u z Kết quả bảng chuyển tiếp tại u: x y đích liên kết v (u,v) x (u,x) y (u,x) w (u,x) z (u,x) Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 22
  23. Giải thuật Dijkstra, thảo luận Độ phức tạp giải thuật: n nốt  mỗi lần lặp: phải kiểm tra tất cả n nốt, w, ko thuộc N 2  thực hiện n(n+1)/2 lần so sánh: O(n )  có khả năng hiện thực tốt hơn: O(nlogn) Dạng khác:  vd, chi phí liên kết = lượng lưu lượng sử dụng A 1 A A A 1+e 2+e 0 0 2+e 2+e 0 D B D B D B D 0 0 1+e 1 0 0 1+e 1 B 0 e 0 0 1 e C C C 1+e 0 C 1 1 e tính lại tính lại tính lại khởi đầu định tuyến Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 23
  24. Chương 4: Tầng Mạng  4.1 Giới thiệu  4.4 Các giải thuật định  4.2 Bên trong bộ định tuyến tuyến là gì?  Trạng thái liên kết  Véc-tơ Khoảng cách  4.3 IP: Internet Protocol  Định tuyến phân cấp  Định dạng gói tin   Đánh địa chỉ IPv4 4.5 Định tuyến trong  ICMP Internet   IPv6 RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 24
  25. Giải thuật Véc tơ-Khoảng cách Phương trình Bellman-Ford (lập trình động) Xác định dx(y) := chí phí của tuyến đường rẻ nhất từ x tới y Khi đó dx(y) = min {c(x,v) + dv(y) } v với min được lấy trên tất cả hàng xóm v của x Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 25
  26. Ví dụ Bellman-Ford 5 Rõ ràng, dv(z) = 5, dx(z) = 3, dw(z) = 3 v 3 w 2 5 u z phương trình B-F: 2 3 1 1 d (z) = min { c(u,v) + d (z), x y 2 u v 1 c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 node mà đạt được giá trị min sẽ là node tiếp theo trong tuyến đường ngắn nhất ➜ bảng chuyển tiếp Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 26
  27. Giải thuật Véc tơ-Khoảng cách  Dx(y) = chi phí thấp nhất từ x tới y  node x biết chi phí tới mỗi hàng xóm v: c(x,v)  node x duy trì véc tơ khoảng cách Dx = [Dx(y): y є N ]  node x cũng duy trì các véc tơ khoảng cách của hàng xóm  Cho mỗi hàng xóm v, x duy trì Dv = [Dv(y): y є N ] Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 27
  28. Giải thuật Véc tơ-Khoảng cách Ý tưởng căn bản:  Qua thời gian, mỗi node gửi đo đạc VTKC của nó tới các hàng xóm  Không đồng bộ  Khi một node x nhận được DV mới từ hàng xóm, nó cập nhật DV của nó sử dụng p/trình B-F: Dx(y) ← minv{c(x,v) + Dv(y)} với mọi node y ∊ N  Với vài điều kiện nhỏ, giá trị của Dx(y) sẽ hội tụ tới giá trị chi phí nhỏ nhất thực tế dx(y) Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 28
  29. Giải thuật Véc tơ-Khoảng cách (5) Lặp, không đồng bộ: mỗi Mỗi node: vòng lặp cục bộ gây ra bởi:  thay đổi chi phí liên kết cục bộ chờ cho (thay đổi trong chi phí của liên kết cục bộ hoặc  thông điệp cập nhật DV từ t/điệp từ hàng xóm) hàng xóm Phân tán:  mỗi node thông báo cho tính lại các đo đạc hàng xóm chỉ khi DV của nó thay đổi nếu DV tới bất kì đích nào  hàng xóm khi đó sẽ lại thông báo cho hàng xóm thay đổi, thông báo cho hàng của chúng, nếu cần xóm Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 29
  30. D (z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} x = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} bảng node x = min{2+1 , 7+0} = 3 c.phí tới c.phí tới x y z x y z x 0 2 7 x 0 2 3 từ y ∞ ∞ ∞ từ y 2 0 1 z ∞ ∞ ∞ z 7 1 0 bảng node y c.phí tới x y z y 2 1 x ∞ ∞ ∞ x z y 2 0 1 7 từ z ∞ ∞ ∞ bảng node z c.phí tới x y z x ∞ ∞ ∞ từ y ∞ ∞ ∞ z 7 1 0 Trường Đại Học Bách Khoa Tp.HCM t MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 30
  31. D (z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} x = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} bảng node x = min{2+1 , 7+0} = 3 c.phí tới c.phí tới c.phí tới x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 y y từ ∞ ∞ ∞ từ 2 0 1 y từ 2 0 1 z z 7 1 0 ∞ ∞ ∞ z 3 1 0 bảng node y c.phí tới c.phí tới c.phí tới x y z x y z y x y z 2 1 x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z y 2 0 1 y 7 từ 2 0 1 y từ từ 2 0 1 z ∞ ∞ ∞ z 7 1 0 z 3 1 0 bảng node z c.phí tới c.phí tới c.phí tới x y z x y z x y z x ∞ ∞ ∞ x 0 2 7 x 0 2 3 y y 2 0 1 từ y 2 0 1 từ từ ∞ ∞ ∞ z z z 7 1 0 3 1 0 3 1 0 Trường Đại Học Bách Khoa Tp.HCM t MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 31
  32. VTKC: chi phí liên kết thay đổi Chi phí liên kết thay đổi:  node nhận ra sự thay đổi chi phí trong liên 1 y kết cục bộ 4 1  cập nhật t/tin định tuyến, tính lại véc tơ KC x z 50  nếu DV thay đổi, thông báo hàng xóm tại t0, y phát hiện thay đổi chi phí lk, cập nhật DV của nó, và thông báo hàng xóm. “tin tại t , z nhận được cập nhật của y và cập nhật bảng của nó. Nó tính tốt 1 chi phí thấp nhất tới x và gửi cho hàng xóm DV của nó. truyền nhanh” tại t2, y nhận được cập nhật của z và cập nhật DV của nó. tuyến đường chi phí thấp nhất của y không đổi vì vậy nó không gửi thông điệp nào cho z. Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 32
  33. Véc tơ KC: chi phí liên kết thay đổi Chi phí liên kết thay đổi: . tin tốt truyền nhanh 60 y . tin xấu truyền chậm – vấn đề “đếm 4 1 tới vô cùng”! x z . 44 vòng lặp trước khi giải thuật ổn 50 định Sự nhiễm độc ngược: . Nếu Z đi qua Y để tới X: . Z nói Y khoảng cách của nó tới X là vô tận (vậy Y sẽ không đi qua Z để tới X) . liệu cách này có giải quyết hoàn toàn vấn đề đếm tới vô cùng không? Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 33
  34. So sánh các giải thuật LS và DV Sự phức tạp của th/điệp Sức chịu đựng: nếu bđt trục  LS: với n node, E liên kết, O(nE) trặc? th/đ được gửi LS:  DV: chỉ trao đổi giữa hàng xóm với  node có thể quảng bá chi nhau phí liên kết sai  t/gian hội tụ thay đổi  mỗi node chỉ tính toán Tốc độ hội tụ bảng của riêng nó 2  LS: O(n ) giải thuật cần O(nE) DV: thông điệp  node DV có thể quảng bá  có thể có dao động chi phí tuyến đường sai  DV: thời gian hội tụ thay đổi  mỗi bảng của node được dùng bởi các node khác  có thể có vòng lặp định tuyến  lỗi lan truyền trong mạng  vấn đề đếm-tới-vô-cùng Trường Đại Học Bách Khoa Tp.HCM MẠNG MÁY TÍNH CĂN BẢN Khoa Khoa Học và Kỹ Thuật Máy Tính Bài giảng 3 - Chương 4: Tầng Mạng © 2011 34