Chương 8 trình bày về "Giải thuật định tuyến". Nội dung cụ thể của chương này gồm có: Tổng quan phối hợp giữa routing và forwarding, đồ thị mạng, phân loại giải thuật định tuyến, giải thuật distance vector, | Chương 8 GI I THU T NH TUY N (ROUTING ALGORITHM) Gi i thu t nh tuy n 4-1 N I DUNG T ng quan Link state Distance Vector Hierarchical routing Gi i thu t nh tuy n 4-2 T ng quan: Ph i h p gi a routing và forwarding routing algorithm local forwarding table header value output link 0100 0101 0111 1001 Tham s trong header c a gói 3 2 2 1 n 0111 1 3 2 Gi i thu t nh tuy n 4-3 T ng quan: th m ng 5 2 u 2 1 Graph: G = (N,E) v x 3 w 3 1 5 z 1 y 2 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) } 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-4 T ng quan: Chi phí liên k t (cost) 5 2 u v 2 1 x • c(x,x’) = chi phí c a liên k t (x,x’) 3 w 3 1 5 z 1 y - ví d c(w,z) = 5 2 • 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: Gi i thu t âu là ư ng i có chi phí nh nh t gi a u và z ? nh tuy n s xác nh ư ng i có chi phí nh nh t Gi i thu t nh tuy .
