Giáo trình Mạng máy tính - Chương 8: Giải thuật định tuyến (Routing Algorithm) - Nguyễn Hồng Sơn

Giải thuật định tuyến 4-1 Chương 8 GIẢI THUẬT ĐỊNH TUYẾN (ROUTING ALGORITHM) Giải thuật định tuyến 4-2 NỘI DUNG
Tổng quan
Link state
Distance Vector
Hierarchical routing Giải thuật định tuyến 4-3 1 23 0111 Tham số trong header của gói đến routing algorithm local forwarding table header value output link 0100 0101 0111 1001 3 2 2 1 Tổng quan: Phối hợp giữa routing và forwarding Giải thuật định tuyến 4-4 u yx wv z 2 2 1 3 1 1 2 5 3 5 Graph: G = (N,E) N = tập các router = { u, v, w, x, y, z } E = tập các liên kết={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Tổng quan: Đồ thị mạng Đồ thị mạng cũng hữu dụng trong các ngữ cảnh mạng khác Ví dụ: P2P, với N là tâp các peer và E là tập các kết nối TCP Giải thuật định tuyến 4-5 Tổng quan: Chi phí liên kết (cost) u yx wv z 2 2 1 3 1 1 2 5 3 5 • c(x,x’) = chi phí của liên kết (x,x’) - ví dụ c(w,z) = 5 • chi phí được xác định tùy theo các yếu tố như băng thông, mức độ nghẽn... Chi phí của đường đi (x1, x2, x3,, xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) Câu hỏi: Đâu là đường đi có chi phí nhỏ nhất giữa u và z ? Giải thuật định tuyến sẽ xác định đường đi có chi phí nhỏ nhất Giải thuật định tuyến 4-6 Tổng quan: Phân loại giải thuật định tuyến Thông tin toàn cục hay phân tán? Toàn cục: r Tất cả các router biết toàn bộ topo với thông tin về chi phí r Các giải thuật “link state” Phân tán: r router biết các láng giềng và chi phí nối đến đó r Quá trình tính toán lặp lại, trao đổi thông tin với các láng giềng r Các giải thuật “distance vector” Tĩnh hay động? Tĩnh: r Các tuyến được xác lập và thay đổi bởi người quản trị Động: r Các tuyến thay đổi nhanh, tự động m Cập nhật theo thời gian m Thích ứng với các thay đổi của chi phí trên liên kết Giải thuật định tuyến 4-7 NỘI DUNG
Tổng quan
Link state
Distance Vector
Hierarchical routing Giải thuật định tuyến 4-8 Một giải thuật Link-State Giải thuật Dijkstra r Các node biết tất cả topo mạng m Có được qua "quảng bá trạng thái liên kết m Tất cả các node có cùng thông tin r Tính toán các đường đi có chi phí thấp nhất từ một node đến tất cả các node khác m Tạo forwarding table cho node đó r Lặp : sau k lần lặp, biết đường đi có chi phí thấp nhất đến k node đích Ký hiệu: r c(x,y): chi phí từ node x đến y; = ∞ nếu không nối trực tiếp r D(v): chi phí hiện hành từ nguồn đến node v r p(v): nút ngay trước nút v trên đường đi từ nguồn tới đích r N: Tập các nút mà đường đi ngắn nhất đã được xác định Giải thuật định tuyến 4-9 Giải thuật Dijsktra 1 Initialization: 2 N = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N' Giải thuật định tuyến 4-10 Ví dụ (1) 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 yx wv z 2 2 1 3 1 1 2 5 3 5 Giải thuật định tuyến 4-11 Ví dụ (2) u yx wv z Kết quả có cây SPT (shortest-path tree) từ u: v x y w z (u,v) (u,x) (u,x) (u,x) (u,x) đích link Xây dựng forwarding table cho u: Giải thuật định tuyến 4-12 NỘI DUNG
Tổng quan
Link state
Distance Vector
Hierarchical routing Giải thuật định tuyến 4-13 Giải thuật Distance Vector (1) Phương trình Bellman-Ford (qui hoạch động) Định nghĩa: If dx(y) := chi phí nhỏ nhất từ x đến y Then dx(y) = min {c(x,v) + dv(y) } Trong đó min lấy tất cả các láng giềng v của x để xét v Giải thuật định tuyến 4-14 Ví dụ Bellman-Ford u yx wv z 2 2 1 3 1 1 2 5 3 5 Đã biết, 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 đạt min là chặng kế tiếp trên đường đi ngắn nhất, dùng để lập bảng forwarding table Theo phương trình B-F: Giải thuật định tuyến 4-15 Giải thuật Distance Vector (2) r Dx(y) = ước lượng chi phí nhỏ nhất từ x đến y r Node x biết chi phí đến mỗi láng giềng v của nó: c(x,v) r Node x lưu giữ một distance vector: Dx = [Dx(y): y є N ] r Node x cũng lưu giữ các distance vector của các láng giềng m Đối với mỗi láng giềng v, x lưu giữ: Dv = [Dv(y): y є N ] Giải thuật định tuyến 4-16 Giải thuật Distance vector (3) Cơ sở: r Theo thời gian, mỗi node gửi ước lượng distance vector của nó đến các láng giềng r Bất đồng bộ r Khi node x nhận một ước lượng DV mới từ láng giềng, nó cập nhật DV của nó bằng phương trình B-F: Dx(y) ← minv{c(x,v) + Dv(y)} cho mỗi node y ∊ N r Dưới các điều kiện tự nhiên, ước lượng Dx(y) hội tụ dần về chi phí nhỏ nhất thực sự dx(y) Giải thuật định tuyến 4-17 Giải thuật Distance vector (4) Lặp, bất đồng bộ: mỗi hoạt động lặp cục bộ là do: r Thay đổi chi phí liên kết cục bộ r Thông điệp cập nhật (DV update message) từ láng giềng Phân tán: r Mỗi node chỉ thông báo cho láng giềng khi thay đổi DV của nó m Đến lượt các láng giềng thông báo cho các láng giềng của chúng nếu cần Mỗi node: Chờ (Thay đổi trong DV của nút bên cạnh) Tính lại ước lượng DV Nếu DV thay đổi, Báo cho nút bên cạnh Giải thuật định tuyến 4-18 x y z x y z 0 2 7 ∞∞ ∞ ∞∞ ∞ f r o m cost to f r o m f r o m x y z x y z 0 f r o m cost to x y z x y z ∞ ∞ ∞∞ ∞ cost to x y z x y z ∞∞ ∞ 7 1 0 cost to ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 time x z 12 7 y node x table node y table node z table 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 32 Giải thuật định tuyến 4-19 x y z x y z 0 2 7 ∞∞ ∞ ∞∞ ∞ f r o m cost to f r o m f r o m x y z x y z 0 2 3 f r o m cost to x y z x y z 0 2 3 f r o m cost to x y z x y z ∞ ∞ ∞∞ ∞ cost to x y z x y z 0 2 7 f r o m cost to x y z x y z 0 2 3 f r o m cost to x y z x y z 0 2 3 f r o m cost to x y z x y z 0 2 7 f r o m cost to x y z x y z ∞∞ ∞ 7 1 0 cost to ∞ 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 time x z 12 7 y node x table node y table node z table 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 Giải thuật định tuyến 4-20 Thay đổi chi phí liên kết Các thay đổi chi phí liên kết: r node phát hiện thay đổi chi phí liên kết nội bộ r Cập nhật thông tin định tuyến, tính toán lại distance vector r Nếu DV thay đổi, thông báo cho láng giềng x z 14 50 y 1 Tại t0, y phát hiện thay đổi link-cost, cập nhật DV của nó, và thông báo cho các láng giềng của nó. Tại t1, z nhận cập nhật từ y và cập nhật bảng của nó. Nó tính lại chi phí nhỏ nhất đến x và gửi DV mới cho các láng giềng. Tại t2, y nhận cập nhật từ z và cập nhật bảng của nó. Chi phí nhỏ nhất của y không thay đổi và do đó y không gửi bất kỳ thông điệp nào đến z Giải thuật định tuyến 4-21 NỘI DUNG
Tổng quan
Link state
Distance Vector
Hierarchical routing Giải thuật định tuyến 4-22 Hierarchical Routing Qui mô: với hàng trăm triệu đích: r Không thể lưu tất cả các đích trong bảng định tuyến! r Việc trao đổi bảng định tuyến sẽ làm tràn ngập các liên kết! Nhu cầu tự quản: r internet = mạng của các mạng r Mỗi quản trị mạng muốn kiểm soát định tuyến bên trong mạng của họ Định tuyến phân cấp Giải thuật định tuyến 4-23 Hierarchical Routing r Tập hợp các router vào các vùng, “autonomous systems” (AS) r Các router trong cùng AS m “intra-AS” routing protocol: giao thức định tuyến nội vùng m Các router trong AS khác nhau chạy các intra-AS routing protocol khác nhau Gateway router r Kết nối trực tiếp đến router trong AS khác Giải thuật định tuyến 4-24 3b 1d 3a 1c 2aAS3 AS1 AS2 1a 2c 2b 1b Intra-AS Routing algorithm Inter-AS Routing algorithm Forwarding table 3c Liên kết giữa các AS r forwarding table được xây dựng nhờ vào giao thức định tuyến nội vùng và liên vùng (intra-AS và inter-AS routing protocol) m intra-AS cài đặt các mục cho các đích nội vùng m inter-AS & intra-As cài đặt các mục cho các đích nằm bên ngoài Giải thuật định tuyến 4-25 3b 1d 3a 1c 2aAS3 AS1 AS2 1a 2c 2b 1b 3c Các tác vụ liên AS r Giả sử router trong AS1 nhận datagram có đích nằm ngoài AS1: m router nên chuyển gói đến gateway router, nhưng đến gateway nào? AS1 phải: 1. Học để biết các đích nào có thể đến được thông qua AS2, đích nào có thể đến được thông qua AS3 2. Phát tán thông tin về khả năng đến được này đến tất cả các router trong AS1 Đây là một nhiệm vụ của giao thức định tuyến inter-AS Giải thuật định tuyến 4-26 Ví dụ: thiết lập forwarding table trong router 1d r Giả sử AS1 học và biết được (thông qua giao thức inter-AS) subnet x có thể đến được thông qua AS3 (gateway 1c), không thể thông qua AS2. r Giao thức inter-AS phát tán thông tin này đến tất cả các router bên trong. r Từ giao thức intra-AS mà router 1d xác định được giao tiếp I của nó là tiếp tục con đường có chi phí nhỏ nhất đến 1c. m Ghi vào forwarding table một mục (x,I) 3b 1d 3a 1c 2aAS3 AS1 AS2 1a 2c 2b 1b 3c x Giải thuật định tuyến 4-27 Ví dụ: Chọn trong số nhiều AS r Giả sử từ giao thức inter-AS, AS1 học và biết subnet x có thể đến được từ AS3 và từ AS2. r Để cấu hình forwarding table, router 1d phải xác định gateway nào nó nên chuyển gói có đích là x. m Đây là một tác vụ nữa của giao thức định tuyến inter-AS 3b 1d 3a 1c 2aAS3 AS1 AS2 1a 2c 2b 1b 3c x Giải thuật định tuyến 4-28 Từ inter-AS protocol biết có thể đến subnet x bằng nhiều đường Dùng thông tin từ intra-AS protocol xác định đường đi có chi phí nhỏ nhất đến mỗi gateway Chọn gateway có chi phí đường đi nhỏ nhất Xác định giao tiếp I dẫn đến gateway đã chọn, nhập (x,I) vào forwarding table Ví dụ: Chọn trong số nhiều AS r Gửi gói đến router nào có chi phí thấp nhất.