LS算法和DV算法.docVIP

LS算法与DV算法LS: Link-State Routing Algorithm（链路状态路由算法）DV:Distance Vector Algorithm（距离向量算法）对于RIP协议、OSPF协议、BGP协议RIP、BGP使用DV算法，OSPF协议使用LS算法；RIP、OSPF属于自治系统内部(Intra-AS Routing)，BGP属于自治系统之间(Internet inter-AS routing)LS算法：P450-22: Consider the following network. With the indicated link costs, use Dijkstra’s shortest-path algorithm to compute the shortest path from x to all network nodes. Show how the algorithm works by computing a table.zxyzxyVwtus126681483425914AnswerProblem 22StepN’D(s),p(s) D(t),p(t)D(u),p(u)D(v),p(v)D(w),p(w)D(y),p(y)D(z),p(z)0x∞∞∞8,x6,x6,x∞1xw∞∞14,w8,x6,x∞2xwy∞15,y14,w7,y18,y3xwyv∞11,v10,v18,y4xwyvu14,u11,v18,y5xwyvut12,t16,t6xwyvuts16,t7xwyvutsz y t zx v s w uRouting Table:DESCOSTNEST HOPx0y6yw6wv7yt11yu10yz16ys12yConsider the following network.With the indicated link costs, use Dijkstras shortest path algorithm to compute the shortest path from C to all network nodes. Give step table ,the shortest span tree and forwarding table. (10 points)stepN’D(A),p(A)D(B),p(B)D(D),p(D)D(E),p(E)D(F),p(F)D(G),p(G)0C∞5,C1,C2,C∞9,C1CD∞5,C2,C∞9,C2CDE∞5,C5,E3,E3CDEG6,G4,G4,G4CDEGB6,G4,G5CDEGBF5,G6CDEGBFADest.Next hopAEBEC---DDEEFEGEDV算法:P451-25: Consider the network fragment shown below. x has only two attached neighbors, w and y. w has a minimum-cost path to destination u of 5, and y has a minimum-cost path to u of 6. The complete paths from w and y to u (and between w and y) are not shown. All link costs in the network have strictly positive integer values.Give x’s distance vector for destinations w, y, and u.Give a link-cost change for either c(x,w) or c(x,y) such that x will inform its neighbors of a new minimum-cost path to u as a result of executing the distance-vector algorithm.Give a link-cost change for either c(x,w) or c(x,y) such that x will not inform its neighbors of a new minimum-cost path to u as a result of executin