文档介绍：路由算法及分类
路由算法及分类:
1、非自适应算法，静态路由算法
不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择
算法。
特点：简单，开销少；灵活性差。
2、自适应算法，动态路由算法
可根ec)
Cj (kbps)
nCj (pkts/sec)
I, {msec)
Weight
1
AB
14
20
25
91
2
BC
12
20
25
77
3
CD
6
10
154
0 073
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
Fig. 5-9, Analysis of the subnet of Hg. 54 using a mean packet size of 800 bits. The reverse traffic (BA, CH, etej is the siime us the lUrwHnl Irafiic.
1/m = 800 bits
根据排队论，平均延迟T = 1/ (mC - l)
4、距离向量路由算法( Distance Vector Routing)
属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于 ARPANET , 被RIP协议采用。
1)基本思想
每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路
由器交换距离信息来更新表；
以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达
目的结点所需时间或距离；
每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个
邻居结点发来的距离表；
邻居结点X发来的表中，X到路由器i的距离为Xi,本路由器到X的距离为m,则路由器 经过X至ij i的距离为Xi + m。根据不同邻居发来的信息，计算 Xi + m ,并取最小值，更新 本路由器的路由表；
注意：本路由器中的老路由表在计算中不被使用
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
Fig. 5-10. (a) A subnet, (b) Input from A, I,H, K, and the new routing table for Jt
2)无限计算问题
算法的缺陷：对好消息反应迅速，对坏消息反应迟钝；
A
B
c
D E
A
B
C
D
E
*—
—*——•
*—
■
8
婚 c» Initially
1
2
3
4 Initially
1
g
g oo After 1 exchange
3
2
3
4 After 1 exchange
1
2
« 酬 After 2 exchanges
3
4
3
4 After 2 exchanges
1
2
38 After 3 exchanges
5
4
5
4 After 3 exchanges
1
2
34 After 4 exchanges
5
6
5
6 After 4 exchanges
7
6
7