文档介绍：路由算法及分类
路由算法及分类:
1、 非自适应算法，静态路由算法
不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择 算法。
特点：简单，开销少；灵活性差。
2、 自适应算法，动态路由算法
可根据C
8
20
25
59
0 098
Fig. 5-9. Analysis of the subnet of Fig. 5-8 using a mean packet size cif 800 hits. The reverse traffic (BA, CH, etc.) is the same cis the forward lialTic,
1/m = 800 bits
根据排队论，平均延迟T = 1/ (mC - l)
4、距离向量路由算法(Distance Vector Routing)
属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET,
被RIP协议采用。
基本思想
每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路 由器交换距离信息来更新表；
以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达 目的结点所需时间或距离；
每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个 邻居结点发来的距离表；
邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器 经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新 本路由器的路由表；
注意：本路由器中的老路由表在计算中不被使用
ow csti mated delay from J
1 H
K
24
20
21
36
31
28
18
19
36
27
8
24
看
30
19
22
40
31
20
6
31
19
0
14
22
11
7
10
22
22
0
33
9
9
JI JH
delay dela>
is is
10 12
JK delay is
J s tfour neighbors
8
A
20
A
26
I
20
H
I
18
12
H
10
I
0
6
K
15
K
routung
table
routing tabic for J.
2）无限计算问题
算法的缺陷：对好消息反应迅速，对坏消息反应迟钝;
A ■
B ■
c ■
D ■
E
A
.
8
8
66 Initially
1
OQ
OO
□a After 1 exchange
1
2
8
* After 2 exchanges
1
2
3
8 After 3 exchanges
1
2
3
4 After 4 exchanges
(a)
A
B
c
D
E
.
.
2
3
4 Initially
3
2
3
4 After 1 exchange