路由选择算法(1)

通信方面的

路由选择及其算法通信子网为网络源节点和目的节点提供了 多条传输路径的可能性。网络节点在收到一个 分组后，要确定向一下节点传送的路径，这就 是路由选择。在数据报方式中，网络节点要为 每个分组路由做出选择；而在虚电路方式中， 只需在连接建立时确定路由。确定路由选择的 策略称路由算法。

通信方面的

路由(径)选择——根据一定的原则和算 法在所有传输通路中选择一条通往目的结点的 最佳路径。 路由选择算法——路由选择过程中采用的 策略。

通信方面的

路由选择算法分类1、根据能否适应通信量和拓扑结构变化 非自适应(静态路由):可靠性差、简单 自适应(动态路由):实现复杂、可靠性高—— 实用 2、根据源节点向外发送数据方式 全路发送(扩散式) 统称多路发送 几路发送(选择扩散式) 单路发送

通信方面的

固定式(静态路由) 单路发送 适应式(动态路由) 最短路法 分布式 局部延迟法

通信方面的

典型的路由选择算法1、多路发送

特点：可靠性高、盲目性大(重复分路多)、 通信量大

通信方面的

几路发送

特点：通信量减小、可靠性降低

通信方面的

2、固定式(网中每一个结点存放一张事先确 定好的路由表(存放最佳路由)) 表中给出本结点到各目的结点的最短路径 例 一旦C和E之间的 网络断开，则A、 B无法通信。 特点：简单、可靠性差(不能适应网络状态变 化),适用于小型网络，(人工维护路由表)

通信方面的

3、适应式(动态路由选择)适用于中型网络 路由表动态设臵(不需要人工干预) 实现方式：相邻结点(交换机或路由器)周期 性交换路由信息。

通信方面的

例：

一旦结点C与结点E之间断开，则结点C向结 点A反馈信息，通过其他路径进行通信。

通信方面的

分布式路由算法1、基本思想：每个结点周期性地从相邻的结 点获得网络状态信息，同时将本结点做出的决 定周期性地通知周围的结点，以使这些结点不 断地根据网络新的状态更新其路由选择决定。 2、基本算法：距离向量法和链路状态法

通信方面的

距离向量路由选择算法距离向量路由选择算法是一种最基本的动 态路由选择算法。 原理：让每个路由器维护一张路由表，表 中给出了到每个目的地已知的最佳距离和路径 。通过与相邻路由器之间周期性地相互交换信 息，来更新表中的信息。当网络拓扑结构发生 变化时，路由器之间也将及时地相互通知有关 变更信息。

通信方面的

基本思想：每个结点保持两个向量 Di和 Si ; 每隔一段时间(如128ms)相邻节点交换时延 向量；根据收到的全部时延向量修改本结点时 延向量和后继结点时延向量。

通信方面的

延迟向量 Di d i1 di 2 Di d 1N

其中

:d 0 iid kj d ki d ij Min[d ki d ij ]i A

A为结点 k 的所有相邻节点

dii 指结点到结点自身的延迟

通信方面的

后继结点向量 Si s i1 si 2 Si s iN Skj i 使每个结点[dki dij ] 最小

通信方面的

如下图1所示网络，图2是更新前结点1的路由 表

通信方面的

通信方面的

1、路由表中给出了结点1的两个向量Di 和 Si 。 2、经128ms后，结点1收到3个相邻节点(2、 3、4)的时延向量 D2 、 3、 4 ,进行更新运算， D D 得到更新后的路由表。 d 21 2 d 31 3 d 41 1 d 22 0 d 32 3 d 42 2 d 3 d 0 d 2 23 D3 33 D4 43 D2 d 24 2 d 34 2 d 44 0 d 35 1 d 25 3 d 45 1 d 5 d 3 d 3 26 36 46

通信方面的

例：计算 d13

1 2 3 1 3 1 4 4Min d13 3

d13 d12 d 23 2 3 5 d13 d13 d33 5 0 5 d13 d14 d 43 1 2 3

通信方面的

计算 d15 最小值

1 2 3 5 1 2 4 5 1 3 5 1 4 5

d15 d12 d 23 d 35 6 d15 d12 d 24 d 45 5 d15 d13 d 35 6 d15 d14 d 45 2

Min d15 2

本文来源：https://www.bwwdw.com/article/dnoi.html