Bài giảng Mạng máy tính - Chương 8: Giải thuật định tuyến (Routing Algorithm)

Chương 8<br /> <br /> GI I THU T<br /> NH TUY N<br /> (ROUTING ALGORITHM)<br /> <br /> Gi i thu t<br /> <br /> nh tuy n<br /> <br /> 4-1<br /> <br /> N I DUNG<br /> T ng quan<br /> Link state<br /> Distance Vector<br /> Hierarchical routing<br /> <br /> Gi i thu t<br /> <br /> nh tuy n<br /> <br /> 4-2<br /> <br /> T ng quan: Ph i h p gi a routing và<br /> forwarding<br /> routing algorithm<br /> <br /> local forwarding table<br /> header value output link<br /> 0100<br /> 0101<br /> 0111<br /> 1001<br /> <br /> Tham s trong<br /> header c a gói<br /> <br /> 3<br /> 2<br /> 2<br /> 1<br /> <br /> n<br /> 0111<br /> <br /> 1<br /> 3 2<br /> <br /> Gi i thu t<br /> <br /> nh tuy n<br /> <br /> 4-3<br /> <br /> T ng quan:<br /> <br /> th m ng<br /> 5<br /> 2<br /> <br /> u<br /> <br /> 2<br /> 1<br /> <br /> Graph: G = (N,E)<br /> <br /> v<br /> <br /> x<br /> <br /> 3<br /> <br /> w<br /> 3<br /> <br /> 1<br /> <br /> 5<br /> <br /> z<br /> <br /> 1<br /> <br /> y<br /> <br /> 2<br /> <br /> N = t p các router = { u, v, w, x, y, z }<br /> 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) }<br /> th m ng cũng h u d ng trong các ng c nh m ng khác<br /> Ví d : P2P, v i N là tâp các peer và E là t p các k t n i TCP<br /> Gi i thu t<br /> <br /> nh tuy n<br /> <br /> 4-4<br /> <br /> T ng quan: Chi phí liên k t (cost)<br /> 5<br /> 2<br /> <br /> u<br /> <br /> v<br /> 2<br /> <br /> 1<br /> <br /> x<br /> <br /> • c(x,x’) = chi phí c a liên k t (x,x’)<br /> 3<br /> <br /> w<br /> 3<br /> <br /> 1<br /> <br /> 5<br /> <br /> z<br /> <br /> 1<br /> <br /> y<br /> <br /> - ví d c(w,z) = 5<br /> <br /> 2<br /> <br /> • chi phí ư c xác nh tùy theo<br /> các y u t như băng thông, m c<br /> ngh n...<br /> <br /> Chi phí c a ư ng i (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)<br /> Câu h i:<br /> <br /> Gi i thu t<br /> <br /> âu là ư ng i có chi phí nh nh t gi a u và z ?<br /> <br /> nh tuy n s xác<br /> <br /> nh ư ng i có chi phí nh nh t<br /> Gi i thu t<br /> <br /> nh tuy n<br /> <br /> 4-5<br /> <br />