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.

z 5 12 y 6 8 4 x 6 8 w

u t 4 V 3 4 2 1 s 9 1 Answer

Problem 22

Step N’

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)

0 x ∞ ∞ ∞ 8,x 6,x 1 xw ∞ ∞ 14,w 8,x 2 xwy ∞ 15,y 14,w 7,y 3 xwyv ∞ 11,v 10,v 4 xwyvu 14,u 11,v 5 xwyvut 12,t 6 xwyvuts 7 xwyvutsz y t z

x v s w u

6,x 6,x ∞ ∞ 18,y 18,y 18,y 16,t 16,t

Routing Table: DES x y w v t u z s COST 0 6 6 7 11 10 16 12 NEST HOP y w y y y y y

Consider the following network.With the indicated link costs, use Dijkstra's 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)

step N’ D(A),p(A) D(B),p(B) D(D),p(D) D(E),p(E) D(F),p(F) D(G),p(G) 0 C ∞ 5,C 1,C 2,C ∞ 9,C 1 CD ∞ 5,C 2,C ∞ 9,C 2 CDE ∞ 5,C 5,E 3,E 3 CDEG 6,G 4,G 4,G 4 CDEGB 6,G 4,G 5 CDEGBF 5,G 6 CDEGBFA Dest. A B C D E F G

Next hop E E --- D E E E

DV算法:

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.

a. Give x’s distance vector for destinations w, y, and u.

b. 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.

c. 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 executing the distance-vector algorithm.

w 2 x 5 y

Answer

Problem 25

a. Dx(y) = 5, Dx(w) = 2, Dx(u) = 7

b. First consider what happens if c(x,y) changes. If c(x,y) becomes larger or smaller (as long as c(x,y) > 0), the least cost path from x to u will still have cost at least 7. Thus a change in c(x,y) will not cause x to inform its neighbors of any changes. Now consider if c(x,w) changes. If c(x,w) =   1, then the least-cost path to u continues to pass through w and its cost changes to 5 + ; x will inform its neighbors of this new cost. If c(x,w) =  > 6, then the least cost path now passes through y and has cost 11; again x will inform its neighbors of this new cost.

c. Any change in link cost c(x,y) will not cause x to inform its neighbors of a new minimum-cost path to u .

The topology of a network shown as below. Using Link State routing algorithm to calculate the routing table in the node A. The vectors arrive to node C as bellow: B:( 4, 0, 8, 12, 6, 2 ); D:( 13, 10, 6, 0, 9, 10 ); E:( 7, 6, 3, 9, 0, 14 ). The delays measured from C to B, D, E are 4, 2, and 3 separately. Update router C’s route table please.

B C

A D E F

Answer:

dCB+dBA 4+4

dCA=min dCD+dDA =min 2+13 =8 sCA =B dCE+dEA 3+7

dCB+dBB 4+0

dCB=min dCD+dDB =min 2+10 =4 sCB =B dCE+dEB 3+6

dCB+dBD 4+12 dCD=min dCD+dDD =min 2+0 =2 sCD =D dCE+dED 3+9

dCB+dBE 4+6

dCE=min dCD+dDE =min 2+9 =3 sCE =E dCE+dEE 3+0

dCB+dBF 4+2

dCF=min dCD+dDF =min 2+10 =6 sCF =B dCE+dEF 3+14

router C’s route table Destination Network Dc Sc A 8 B B 4 B C 0 -- D 2 D E 3 E F 6 B