Bài giảng Mạng máy tính - Chương 4: Giao thức tầng mạng (network layer) - Trần Quang Hải Bằng

a toàn bộ mạng.  cho phép tìm đường đi từ một nút tới tất cả các nút còn lại.
Ký hiệu: c(i,j): chi phí phải trả để đi từ i tới j (trực tiếp) D(v): giá trị hiện tại của chi phí phải trả để đi từ đỉnh xuất phát tới đỉnh v. p(v): đỉnh trước đỉnh v trên đường đi ngắn nhất N: tập hợp đỉnh mà đường đi ngắn nhất đã được xác định. Chương 4. Giao thức tầng mạng 5323/08 - 10/10/2010 Dijsktra’s Algorithm 1 Initialization: 2 N = {A} 3 for all nodes v 4 if v kề với A 5 then D(v) = c(A,v) 6 else D(v) = ∞ 7 8 Loop 9 Tìm w không thuộc N sao cho D(w) nhỏ nhất 10 N = N + w 11 for all v kề với w và không thuộc N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 until tất cả nút thuộc N Chương 4. Giao thức tầng mạng 5423/08 - 10/10/2010 Dijkstra’s algorithm: example Step 0 1 2 3 4 5 N A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) ∞ 2,D D(F),p(F) ∞ ∞ 4,E 4,E 4,E A ED CB F 2 2 1 3 1 1 2 5 3 5 Chương 4. Giao thức tầng mạng 5523/08 - 10/10/2010 Distance Vector Routing Algorithm Distance Table data structure
mỗi nút mạng có một bảng khoảng cách.
hàng dành cho các đích có thể đến được.
cột dành cho các nút có thể đến trực tiếp (hàng xóm)
Ví dụ: tại nút X, với đích Y đến qua nút Z: D (Y,Z) X chi phí cho đường đi (XZ*Y) Z là nút kế tiếp cần đi tới c(X,Z) + min {D (Y,w)} Z w = = Chương 4. Giao thức tầng mạng 5623/08 - 10/10/2010 Distance Table: example A E D CB 7 8 1 2 1 2 D () A B C D A 1 7 6 4 B 14 8 9 11 D 5 5 4 2 E cost to destination via d e st i n a tio n D (C,D) E c(E,D) + min {D (C,w)} D w= = 2+2 = 4 D (A,D) E c(E,D) + min {D (A,w)} D w= = 2+3 = 5 D (A,B) E c(E,B) + min {D (A,w)} B w= = 8+6 = 14 loop! loop! Chương 4. Giao thức tầng mạng 5723/08 - 10/10/2010 Distance table  routing table D () A B C D A 1 7 6 4 B 14 8 9 11 D 5 5 4 2 E cost to destination via d e st i n a tio n A B C D A,1 D,5 D,4 D,4 Outgoing link to use, cost d e st i n a tio n Distance table Routing table Chương 4. Giao thức tầng mạng 5823/08 - 10/10/2010 DV Algorithm: Initialization 1 Initialization: 2 for all adjacent nodes v: 3 D (*,v) = infinity /* the * operator means "for all rows" */ 4 D (v,v) = c(X,v) 5 for all destinations, y 6 send min D (y,w) to each neighbor /* w over all X's neighbors */ X X X w At all nodes, X: Chương 4. Giao thức tầng mạng 5923/08 - 10/10/2010 DV Algorithm: Loop 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 12 if (c(X,V) changes by d) 13 /* change cost to all dest's via neighbor v by d */ 14 /* note: d could be positive or negative */ 15 for all destinations y: D (y,V) = D (y,V) + d 16 17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min DV(Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: D (Y,V) = c(X,V) + newval 22 23 if we have a new min D (Y,w)for any destination Y 24 send new value of min D (Y,w) to all neighbors 26 forever w XX X X X w w Chương 4. Giao thức tầng mạng 6023/08 - 10/10/2010 DV Algorithm: example X Z 12 7 Y D (Y,Z) X c(X,Z) + min {D (Y,w)} w= = 7+1 = 8 Z D (Z,Y) X c(X,Y) + min {D (Z,w)} w= = 2+1 = 3 Y Chương 4. Giao thức tầng mạng 6123/08 - 10/10/2010 DV Algorithm: example X Z 12 7 Y Chương 4. Giao thức tầng mạng 6223/08 - 10/10/2010 Một vài so sánh (LS và DV) Link-State
Cần nắm được thông tin toàn bộ mạng
n nút, E links, nE msgs được gửi mỗi lần
O(n2), nE msgs
Mỗi nút chỉ tính toán bảng dẫn đường cho riêng mình. Distance Vector
Chỉ nắm giữ thông tin liên quan tới các nút “hàng xóm”
msgs chỉ được gửi cho các nút “hàng xóm”.
tốc độ hội tụ có thể khác nhau tuỳ từng tình huống, đôi khi rơi vào trạng thái lặp vô hạn.
Thông tin dẫn đường của nút này được sử dụng bởi nút khác.  Một nút gặp sự cố có thể gây ảnh hưởng tới các nút khác. Chương 4. Giao thức tầng mạng 6323/08 - 10/10/2010 Hierarchical Routing Dẫn đường theo từng mức mạng, do:
Quy mô mạng Internet là rất lớn: một nút không thể chứa tất cả các bản ghi cho mọi đích! việc cập nhật bảng dẫn đường tốn kém!
Nhu cầu mạng tự trị  Internet = network of networks người quản trị mạng muốn điều khiển việc dẫn đường (routing) trong mạng họ quản lý. Chương 4. Giao thức tầng mạng 6423/08 - 10/10/2010 Hierarchical Routing (cont)
Phân vùng routers, tạo thành các “autonomous systems” (AS)
routers trong cùng AS sử dụng chung giao thức tìm đường, gọi là “intra-AS” routing protocol.  routers tại các AS khác nhau có thể sử dụng intra-AS routing protocol khác nhau.
Gateway router:  router đặc biệt trong AS  sử dụng intra-AS routing protocol với các routers khác trong AS sử dụng inter-AS routing protocol với các gateway routers khác. Chương 4. Giao thức tầng mạng 6523/08 - 10/10/2010 Hierarchical Routing (cont) Gateways: •perform inter-AS routing amongst themselves •perform intra-AS routers with other routers in their AS inter-AS, intra-AS routing in gateway A.c network layer link layer physical layer a b b a aC A B d A.a A.c C.b B.a c b c Chương 4. Giao thức tầng mạng 6623/08 - 10/10/2010 Hierarchical Routing (cont) Host h2 a b b a aC A B d c A.a A.c C.b B.a c b Host h1 Intra-AS routing within AS A Inter-AS routing between A and B Intra-AS routing within AS B Chương 4. Giao thức tầng mạng 6723/08 - 10/10/2010 Ch4. The Network Layer 4.1 - Giới thiệu và chức năng của tầng mạng. 4.2 - Network service model (VC and Datagram). 4.3 - Thiết bị tầng mạng - Bộ định tuyến (router). 4.4 - Giao thức IP (Internet Protocol). 4.5 - Giải thuật chọn đường (Routing Algorithms). 4.6 - Chọn đường trong mạng Internet. Chương 4. Giao thức tầng mạng 6823/08 - 10/10/2010 Routing in the Internet
Internet = nhiều Autonomous Systems (AS) : Stub AS: các công ty nhỏ: một kết nối với AS khác. Multihomed AS: công ty lớn: nhiều liên kết tới AS khác. Transit AS: nhà cung cấp (móc nối các AS với nhau).
Two-level routing: Intra-AS: người quản trị có quyền chọn giải thuật cho riêng mạng của mình Inter-AS: giải thuật duy nhất (inter-AS routing: BGP) Chương 4. Giao thức tầng mạng 6923/08 - 10/10/2010 Internet AS Hierarchy Inter-AS border (exterior gateway) routers Intra-AS interior (gateway) routers Chương 4. Giao thức tầng mạng 7023/08 - 10/10/2010 Intra-AS Routing
Tên gọi khác: Interior Gateway Protocols (IGP)
Các giao thức chính: RIP: Routing Information Protocol OSPF: Open Shortest Path First  IGRP: Interior Gateway Routing Protocol (Cisco proprietary) Chương 4. Giao thức tầng mạng 7123/08 - 10/10/2010 RIP ( Routing Information Protocol)
Sử dụng Distance vector algorithm
Included in BSD-UNIX Distribution in 1982
Đơn vị đo khoảng cách: số lượng chặng (hop, tối đa = 15 hops)
Routing table được trao đổi 30 giây một lần thông qua RIP response msg (RIP advertisement), mỗi msg chứa tối đa 25 bản ghi.
v1: RFC 1058; v2: RFC 1723 DC BA u v w x y z destination hops u 1 v 2 w 2 x 3 y 3 z 2 Chương 4. Giao thức tầng mạng 7223/08 - 10/10/2010 RIP: Example Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x -- 1 . . .... w x y z A C D B Routing table in D Chương 4. Giao thức tầng mạng 7323/08 - 10/10/2010 RIP Table processing
RIP routing tables managed by application-level process called route-d (daemon)
advertisements được gửi định kỳ, qua UDP packets. Chương 4. Giao thức tầng mạng 7423/08 - 10/10/2010 RIP Table example
Three attached class C networks (LANs)
Router only knows routes to attached LANs
Default router used to “go up”
Route multicast address: 224.0.0.0
Loopback interface (for debugging) Destination Gateway Flags Ref Use Interface -------------------- -------------------- ----- ----- ------ --------- 127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 UG 0 143454 Chương 4. Giao thức tầng mạng 7523/08 - 10/10/2010 OSPF (Open Shortest Path First)
“open”: publicly available; RFC 2178
Uses Link State algorithm  LS packet dissemination  Topology map at each node  Route computation using Dijkstra’s algorithm
OSPF advertisement carries one entry per neighbor router
Advertisements disseminated to entire AS (via flooding)  Carried in OSPF messages directly over IP (rather than TCP or UDP Chương 4. Giao thức tầng mạng 7623/08 - 10/10/2010 OSPF “advanced” features (not in RIP)
Security: các OSPF msgs đều chứa thông tin chứng thực (authenticated).
Multiple same-cost paths: Cho phép truyền tin theo nhiều đường có cùng chi phí với cùng một phiên truyền tin.
Diff. cost metrics for diff. TOS: Cho phép nhiều đơn vị đo khác nhau cho từng loại dịch vụ (e.g., satellite link cost set “low” for best effort; high for real time)
Integrated unicast and multicast support: Multicast OSPF (MOSPF) uses same topology data base as OSPF
Hierarchical OSPF in large domains. Chương 4. Giao thức tầng mạng 7723/08 - 10/10/2010 Hierarchical OSPF
Two-level hierarchy: local area, backbone.  Link-state advertisements only in area  each nodes has detailed area topology; only know direction (shortest path) to nets in other areas.
Area border routers: “summarize” distances to nets in own area, advertise to other Area Border routers.
Backbone routers: run OSPF routing limited to backbone.
Boundary routers: connect to other AS’s. Chương 4. Giao thức tầng mạng 7823/08 - 10/10/2010 Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): RFC 1771; RFC 1772; RFC 1773 AS2 (OSPF intra-AS routing) AS1 (RIP intra-AS routing) BGP AS3 (OSPF intra-AS routing) BGP R1 R2 R3 R4 R5