授课：XXX 2021/3/9
1、基本思想：每个结点周期性地从相邻的结 点获得网络状态信息，同时将本结点做出的决 定周期性地通知周围的结点，以使这些结点不 断地根据网络新的状态更新其路由选择决定。
2、基本算法：距离向量法和链路状态法
10
距离向量路由选择算法
授课：XXX 2021/3/9
距离向量路由选择算法是一种最基本的动 态路由选择算法。
22
授课：XXX 2021/3/9
网络上所有其他的路由器； (4)发送LSP给网络上所有其他的路由器，以便创建
网络拓扑结构数据库(即：SPF树)； (5)计算到每个其他路由器的最短路径； (6)路由器将计算出的最短路径以及所有的该路由器
的网络端口信息添加到路由表中。
Si
si2
s
iN
S kj i
使每个结点[dki dij]最小
14
授课：XXX 2021/3/9
如下图1所示网络，图2是更新前结点1的路由 表
15
授课：XXX 2021/3/9 16
授课：XXX 2021/3/9
1、路由表中给出了结点1的两个向量 D
和
i
S
i。
2、经128ms后，结点1收到3个相邻节点(2、3
得到了结点1的新的部分路由表
20
链路状态路由选择算法
授课：XXX 2021/3/9
链路状态算法，又称最短路径优先算法。 与距离向量算法不同 的是，由于这种算法需 要每一个路由器都保存一份最新的关于整个网 络的网络拓扑结构数据库，因此路由器不情况下，还可以选择出最 短的路径以及采用该路径将经过的路由器。链 路状态算法使用LSP(链路状态数据包)、网络 拓扑数据库、SPF路径选择算法、SPF树，最
、4)的时延向量 D、2 D、3 D，4 进行更新运算，得 到更新后的路由表。
d 21 2
d 22 0
D
2
d d
23 24
3
2
d
25
3
d 26 5
d 31 3
d 32 3
D
3
d d
33 34
0 2
d
35
1
d 36 3
原理：让每个路由器维护一张路由表，表 中给出了到每个目的地已知的最佳距离和路径 。通过与相邻路由器之间周期性地相互交换信 息，来更新表中的信息。当网络拓扑结构发生 变化时，路由器之间也将及时地相互通知有关 变更信息。
11
授课：XXX 2021/3/9
基本思想：每个结点保持两个向量 D i和 S i ； 每隔一段时间（如128ms）相邻节点交换时延 向量；根据收到的全部时延向量修改本结点时 延向量和后继结点时延向量。
5
几路发送
授课：XXX 2021/3/9
特点：通信量减小、可靠性降低
6
授课：XXX 2021/3/9
2、固定式（网中每一个结点存放一张事先确 定好的路由表（存放最佳路由）） 表中给出本结点到各目的结点的最短路径 例
一旦C和E之间的 网络断开，则A 、 B无法通信。
特点：简单、可靠性差（不能适应网络状态变 7
21
授课：XXX 2021/3/9
终计算出从该路由器到其他目标网络的最短路径 ，这些路径就构成了路由表。该算法要求每个路 由器具有唯一的名字或标识。
算法思想：链路状态算法的思想十分简单， 其具体工作过程如下。 每个路由器必须： (1)发现与它相邻的路由器，并知道其网络地址；
(2)测量它到达各相邻路由器的传输代价； (3)组装链路数据包(LSP),以便把它所知信息发送给
18
授课：XXX 2021/3/9
计算 d15 最小值
1 2 3 5 1 2 4 5 1 3 5 1 4 5
Mi nd1 52
d15 d12 d23 d35 6 d15 d12 d24 d 45 5 d15 d13 d35 6 d15 d14 d45 2
19
授课：XXX 2021/3/9
d 41 1
d 42 2
D
4
d d
43 44
2 0
d
45
1
d 46 317
授课：XXX 2021/3/9
例：计算d 13
1 2 3 1 3 1 4 4
d13 d12d23 235 d13 d13d33 50 5 d13 d14d43 12 3
Mi nd1 33
12
授课：XXX 2021/3/9
延迟向量 D i
d i1
D
i
d i2
d
1
N
其中：dii 0
d kjd k i d ijM i A[d k i in d i] j A为结点k的所有相邻节点
d ii 指结点到结点自身的延迟
13
授课：XXX 2021/3/9
后继结点向量 S i
s i1
2、根据源节点向外发送数据方式
全路发送（扩散式）
统称多路发送
几路发送（选择扩散式）
单路发送
3
授课：XXX 2021/3/9
固定式（静态路由）
单路发送 适应式（动态路由） 最短路法
分布式
局部延迟法
4
典型的路由选择算法
1、多路发送
授课：XXX 2021/3/9
特点：可靠性高、盲目性大（重复分路多）、 通信量大
授课：XXX 2021/3/9
3、适应式（动态路由选择）适用于中型网络 路由表动态设置（不需要人工干预） 实现方式：相邻结点（交换机或路由器）周期 性交换路由信息。
8
例：
授课：XXX 2021/3/9
一旦结点C与结点E之间断开，则结点C向结 点A反馈信息，通过其他路径进行通信。
9
分布式路由算法
1
授课：XXX 2021/3/9
路由（径）选择——根据一定的原则和算 法在所有传输通路中选择一条通往目的结点的 最佳路径。
路由选择算法——路由选择过程中采用的 策略。
2
路由选择算法分类
授课：XXX 2021/3/9
1、根据能否适应通信量和拓扑结构变化
非自适应（静态路由）：可靠性差、简单
自适应（动态路由）：实现复杂、可靠性高— —实用
路由选择及其算法
授课：XXX 2021/3/9
通信子网为网络源节点和目的节点提供了 多条传输路径的可能性。网络节点在收到一个 分组后，要确定向一下节点传送的路径，这就 是路由选择。在数据报方式中，网络节点要为 每个分组路由做出选择；而在虚电路方式中， 只需在连接建立时确定路由。确定路由选择的 策略称路由算法。