LS算法与DV算法.doc

LS:Link-StateRoutingAlgorithm(链路状态路由算法)DV:DistanceVectorAlgorithm(距离向量算法)对于RIP协议、OSPF协议、BGP协议RIP、BGP使用DV算法,OSPF协议使用LS算法;RIP、OSPF属于自治系统内部(Intra-ASRouting),BGP属于自治系统之间(inter-ASrouting)LS算法:P450-22:,useDijkstra’sshortest-’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,t7xwyvutszytzxvswuRoutingTable:,useDijkstra',theshortestspantreeandforwardingtable.(10points)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,---DDEEFEGEDV算法:P451-25:,-costpathtodestinationuof5,andyhasaminimum-(andbetweenwandy)’sdistancevectorfordestinationsw,y,-costchangeforeitherc(x,w)orc(x,y)suchthatxwillinformitsneighborsofanewminimum-costpathtouasaresultofexecutingthedistance--costchangeforeitherc(x,w)orc(x,y)suchthatxwillnotinformitsneighborsofanewminimum-costpathtouasaresultofexecutingthedistance-