Bài giảng Mạng máy tính - Bài giảng 9: Tầng mạng (Tiếp theo)

Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính ThS. NGUYỄN CAO ĐẠT E-mail:dat@cse.hcmut.edu.vn Bài giảng Mạng máy tính Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 3 Chương 4: Tầng Mạng  4.1 Giới thiệu  4.2 Bên trong bộ định tuyến là gì?  4.3 IP: Internet Protocol  Định dạng gói tin  Đánh địa chỉ IPv4  ICMP  IPv6  4.4 Các giải thuật định tuyến  Trạng thái liên kết  Véc-tơ Khoảng cách  Định tuyến phân cấp  4.5 Định tuyến trong Internet  RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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  báo cáo lỗi: máy, mạng, cổng, giao thức không liên lạc được  yêu cầu/phản hồi gói echo (sử dụng bởi ping)  nằm ở tầng “trên” IP:  th/điệp ICMP được mang trong gói tin IP  thông điệp ICMP: loại, mã cùng với 8 byte đầu của gói tin IP mà gây ra lỗi Loại Mã Chú giải 0 0 phản hồi echo (ping) 3 0 mạng đích ko liên lạc được 3 1 máy đích ko liên lạc được 3 2 g/thức đích ko liên lạc được 3 3 cổng đích ko liên lạc được 3 6 mạng đích không biết 3 7 máy đích không biết 4 0 giảm tốc độ nguồn (kstn – không dùng) 8 0 truy vấn echo (ping) 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 5 Traceroute và ICMP  Nguồn gửi một loạt khúc UDP cho đích  khúc đầu tiên có TTL =1  khúc thứ 2 có TTL=2, v.v.  số cổng không cố định  Khi gói tin thứ n đến bđt n:  BĐT loại bỏ gói tin  Và gửi lại nguồn một thông điệp ICMP (loại 11, mã 0)  Thông điệp bao gồm cả tên và địa chỉ IP của bđt  Khi thông điệp ICMP tới, nguồn sẽ tính RTT  Traceroute thực hiện việc này 3 lần Điều kiện để ngừng lại  Khúc UDP đến được máy đích  Máy trả về gói ICMP “máy đích không tới được” (loại 3, mã 3)  Khi nguồn nhận được những ICMP này, nó sẽ dừng lại. Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 6 Chương 4: Tầng Mạng  4.1 Giới thiệu  4.2 Bên trong bộ định tuyến là gì?  4.3 IP: Internet Protocol  Định dạng gói tin  Đánh địa chỉ IPv4  ICMP  IPv6  4.4 Các giải thuật định tuyến  Trạng thái liên kết  Véc-tơ Khoảng cách  Định tuyến phân cấp  4.5 Định tuyến trong Internet  RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 11 Tạo đường hầm A B E F IPv6 IPv6 IPv6 IPv6 đường hầm Góc nhìn luận lí: Góc nhìn vật lí: A B E F IPv6 IPv6 IPv6 IPv6 IPv4 IPv4 Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 12 Tạo đường hầm A B E F IPv6 IPv6 IPv6 IPv6 đường hầm Góc nhìn luận lí: Góc nhìn vật lí: A B E F IPv6 IPv6 IPv6 IPv6 C D IPv4 IPv4 Flow: X Src: A Dest: F data Flow: X Src: A Dest: F data Flow: X Src: A Dest: F data Src:B Dest: E Flow: X Src: A Dest: F data Src:B Dest: E A-tới-B: IPv6 E-tới-F: IPv6 B-tới-C: IPv6 bên trong IPv4 B-tới-C: IPv6 bên trong IPv4 Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 13 Chương 4: Tầng Mạng  4.1 Giới thiệu  4.2 Bên trong bộ định tuyến là gì?  4.3 IP: Internet Protocol  Định dạng gói tin  Đánh địa chỉ IPv4  ICMP  IPv6  4.4 Các giải thuật định tuyến  Trạng thái liên kết  Véc-tơ Khoảng cách  Định tuyến phân cấp  4.5 Định tuyến trong Internet  RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 14 1 2 3 0111 giá trị trong mào đầu của gói tới giải thuật định tuyến bảng chuyển tiếp cục bộ gtrị mào đầu đầu ra 0100 0101 0111 1001 3 2 2 1 Tương tác giữa định tuyến, chuyển tiếp Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 15 u y x w v z 2 2 1 3 1 1 2 5 3 5 Đồ thị: G = (N,E) 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) } Trừu tượng hóa bằng đồ thị 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 16 Trừu tượng hóa bằng đồ thị: chi phí u y x w v z 2 2 1 3 1 1 2 5 3 5 • c(x,x’) = chi phí của đường (x,x’) - vd: c(w,z) = 5 • chi phí có thể luôn bằng 1, hoặc nghịch đảo với băng thông, 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 17 Phân loại giải thuật định tuyến Thông tin tổng quát hay phân tán? Tổng quát:  tất cả bđt đều có thông tin đầy đủ về đồ hình mạng và chi phí liên kết  g/thuật “trang thái kết nối” Phân tán:  bđt biết hàng xóm kết nối vật lý tới nó, chi phí tới họ  quá trình tính toán, trao đổi 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” Tĩnh hay động? Tĩnh:  tuyến đường chậm thay đổi theo t/gian Động:  tuyến đường thay đổi nhanh hơn  cập nhật theo chu kì  để phản ánh lại sự thay đổi trong chi phí đường liên kết Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 18 Chương 4: Tầng Mạng  4.1 Giới thiệu  4.2 Bên trong bộ định tuyến là gì?  4.3 IP: Internet Protocol  Định dạng gói tin  Đánh địa chỉ IPv4  ICMP  IPv6  4.4 Các giải thuật định tuyến  Trạng thái liên kết  Véc-tơ Khoảng cách  Định tuyến phân cấp  4.5 Định tuyến trong Internet  RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 19 Một g/thuật trạng thái-liên kết giải thuật Dijkstra  tất cả nốt đều biết đồ hình mạng, chi phí liên kết  thực hiện bởi “phát tán trạng thái liên kết”  mọi nốt có cùng th/tin  tính tuyến đường rẻ nhất từ 1 nốt tới tất cả nốt khác  tạo bảng chuyển tiếp cho nốt đó  lặp: sau k lần lặp, biết được tuyến đường rẻ nhất tới k đích Kí hiệu:  c(x,y): chi phí từ nốt x tới y; = ∞ nếu không phải hàng xóm trực tiếp  D(v): giá trị hiện tại của chi phí của tuyến đường từ nguồn tới đích v  p(v): nốt liền trước trên đường đi từ nguồn tới v  N': tập các nốt mà đã biết được đường đi xác định rẻ nhất tới chúng Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 21 Giải thuật Dijkstra: Ví dụ Bước 0 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u 2,u 2,u D(w),p(w) 5,u 4,x 3,y 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ ∞ 4,y 4,y 4,y u y x w v z 2 2 1 3 1 1 2 5 3 5 Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 22 Giải thuật Dijkstra: ví dụ (2) u y x w v z Kết quả cây đường đi ngắn nhất từ u: v x y w z (u,v) (u,x) (u,x) (u,x) (u,x) đích liên kết Kết quả bảng chuyển tiếp tại u: Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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  thực hiện n(n+1)/2 lần so sánh: O(n2)  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 D C B 1 1+e e 0 e 1 1 0 0 A D C B 2+e 0 0 0 1+e 1 A D C B 0 2+e 1+e 1 0 0 A D C B 2+e 0 e 0 1+e 1 khởi đầu … tính lại định tuyến … tính lại … tính lại Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 24 Chương 4: Tầng Mạng  4.1 Giới thiệu  4.2 Bên trong bộ định tuyến là gì?  4.3 IP: Internet Protocol  Định dạng gói tin  Đánh địa chỉ IPv4  ICMP  IPv6  4.4 Các giải thuật định tuyến  Trạng thái liên kết  Véc-tơ Khoảng cách  Định tuyến phân cấp  4.5 Định tuyến trong Internet  RIP  OSPF  BGP Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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ới min được lấy trên tất cả hàng xóm v của x v Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 26 Ví dụ Bellman-Ford u y x w v z 2 2 1 3 1 1 2 5 3 5 Rõ ràng, dv(z) = 5, dx(z) = 3, dw(z) = 3 du(z) = min { c(u,v) + dv(z), 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 phương trình B-F: Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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:  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) Dx(y) ← minv{c(x,v) + Dv(y)} với mọi node y ∊ N Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 29 Giải thuật Véc tơ-Khoảng cách (5) Lặp, không đồng bộ: mỗi vòng lặp cục bộ gây ra bởi:  thay đổi chi phí liên kết cục bộ  thông điệp cập nhật DV từ hàng xóm Phân tán:  mỗi node thông báo cho hàng xóm chỉ khi DV của nó thay đổi  hàng xóm khi đó sẽ lại thông báo cho hàng xóm của chúng, nếu cần chờ cho (thay đổi trong chi phí của liên kết cục bộ hoặc t/điệp từ hàng xóm) tính lại các đo đạc nếu DV tới bất kì đích nào thay đổi, thông báo cho hàng xóm Mỗi node: Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 30 x y z x y z 0 2 7 ∞ ∞ ∞ ∞ ∞ ∞ từ c.phí tới từ từ x y z x y z 0 từ c.phí tới x y z x y z ∞ ∞ ∞ ∞ ∞ c.phí tới x y z x y z ∞ ∞ ∞ 7 1 0 c.phí tới ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 t x z 1 2 7 y bảng node x bảng node y bảng node z Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 3 2 Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 31 x y z x y z 0 2 7 ∞ ∞ ∞ ∞ ∞ ∞ từ c.phí tới từ từ x y z x y z 0 2 3 từ c.phí tới x y z x y z 0 2 3 từ c.phí tới x y z x y z ∞ ∞ ∞ ∞ ∞ c.phí tới x y z x y z 0 2 7 từ c.phí tới x y z x y z 0 2 3 từ c.phí tới x y z x y z 0 2 3 từ c.phí tới x y z x y z 0 2 7 từ c.phí tới x y z x y z ∞ ∞ ∞ 7 1 0 c.phí tới ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 2 0 1 7 1 0 2 0 1 3 1 0 2 0 1 3 1 0 2 0 1 3 1 0 2 0 1 3 1 0 t x z 1 2 7 y bảng node x bảng node y bảng node z Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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 kết cục bộ  cập nhật t/tin định tuyến, tính lại véc tơ KC  nếu DV thay đổi, thông báo hàng xóm “tin tốt truyền nhanh” x z 1 4 50 y 1 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. tại t1, z nhận được cập nhật của y và cập nhật bảng của nó. Nó tính chi phí thấp nhất tới x và gửi cho hàng xóm DV của nó. 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 Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 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  tin xấu truyền chậm – vấn đề “đếm tới vô cùng”!  44 vòng lặp trước khi giải thuật ổn đị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? x z 1 4 50 y 60 Trường Đại Học Bách Khoa Tp.HCM Khoa Khoa Học và Kỹ Thuật Máy Tính © 2011 MẠNG MÁY TÍNH CĂN BẢN Bài giảng 3 - Chương 4: Tầng Mạng 34 So sánh các giải thuật LS và DV Sự phức tạp của th/điệp  LS: với n node, E liên kết, O(nE) th/đ được gửi  DV: chỉ trao đổi giữa hàng xóm với nhau  t/gian hội tụ thay đổi Tốc độ hội tụ  LS: O(n2) giải thuật cần O(nE) thông điệp  có thể có dao động  DV: thời gian hội tụ thay đổi  có thể có vòng lặp định tuyến  vấn đề đếm-tới-vô-cùng Sức chịu đựng: nếu bđt trục trặc? LS:  node có thể quảng bá chi phí liên kết sai  mỗi node chỉ tính toán bảng của riêng nó DV:  node DV có thể quảng bá chi phí tuyến đường sai  mỗi bảng của node được dùng bởi các node khác  lỗi lan truyền trong mạng