文档介绍：1
路由算法及分类
11
路由算法及分类:
1、非自适应算法，静态路由算法
不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择
算法。
特点：简单，开销少；灵活性差。
2、自msec)
Weight
1
AB
14
20
25
91
2
BC
12
20
25
77
3
CD
6
10
154
0073
4
AE
11
20
25
71
5
EF
13
50
20
6
FD
8
10
125
222
0098
?
BF
10
20
25
67
0,122
8
EC
8
20
25
59
0098
tig,5・,5-(BA,CRfetc.)isdiesiimeusIheforwardIrailie.
1/m=800bits
根据排队论，平均延迟T=1/(mC-l)4、距离向量路由算法(DistanceVectorRouting)
属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET,被RIP协议采用。
1)基本思想
每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路
由器交换距离信息来更新表；
以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达
目的结点所需时间或距离；
每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个
邻居结点发来的距离表；
邻居结点X发来的表中，X到路由器i的距离为Xi,本路由器到X的距离为m,则路由器经过X至iji的距离为Xi+m。根据不同邻居发来的信息，计算Xi+m,并取最小值，更新本路由器的路由表；
注意：本路由器中的老路由表在计算中不被使用
9
delay from J
Tc A I H K j linR
A B C n
E 卜 G H 1
J K L
0
24
20
21
8
A
12
36
31
28
20
A
25
18
19
36
28
I
40
27
8
24
20
H
14
23
/
20
30
19
40
17
30
I
I
18
17
31
20
6
0
31
19
18
12
H
H
21
0
14
22
10
I
9
11
7
10
0
—
24
22
22
0
6
K
29
33
9
9
15
K
JA JI JH JK
delay delay de ay delay is is is is
8 10 12 6
V 」
、v /
New routing tabic for J
New cat mated
Vserors received from
tJ's four neighbors
-10.(a)Asubnet,(b)InputfromA,I,H,K,andthenewroutingtableforJt
2)无限计算问题
算法的缺陷：对好消息反应迅速，对坏消息反应迟钝；
A
B
c
DE
A
B
C
D
E
*—
—*——•
*—
■
8
婚c»Initially
1
2
3
4Initially
1
g
gooAfter1exchange
3
2
3
4After1exchange
1
2
«酬After2exchanges
3
4
3
4After2exchanges
1
2
38After3exchanges
5
4
5
4After3exchanges
1
2
34After4exchanges
5
6
5
6After4exchanges
7
6
7
6After5exchanges
1
B
7
8After6exchange;
00M00M
陶
-to-infiniiyproblem.
3）水平分裂算法
工作过程与距离向量算法相同，