LS算法与DV算法.doc

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属于自治系统之间( inter-AS routing)
LS算法:
P450-22: Consider the work. With the indicated link costs, use Dijkstra’s shortest-path algorithm pute the shortest path from x to work nodes. Show how the algorithm works puting a table.
z
x
y
V
w
t
u
s
12
6
6
8
1
4
8
3
4
2
5
9
1
4
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
6,x
∞
1
xw
∞
∞
14,w
8,x
6,x
∞
2
xwy
∞
15,y
14,w
7,y
18,y
3
xwyv
∞
11,v
10,v
18,y
4
xwyvu
14,u
11,v
18,y
5
xwyvut
12,t
16,t
6
xwyvuts
16,t
7
xwyvutsz
y t z
x v s
w u
Routing Table:
DES
COST
NEST HOP
x
0
y
6
y
w
6
w
v
7
y
t
11
y
u
10
y
z
16
y
s
12
y
Consider the the indicated link costs, use Dijkstra's shortest path algorithm pute the shortest path from C to work 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.
Next hop
A
E
B
E
C
---