路由选择算法

1、路由选择及其算法,通信子网为网络源节点和目的节点提供了多条传输路径的可能性。网络节点在收到一个分组后，要确定向一下节点传送的路径，这就是路由选择。在数据报方式中，网络节点要为每个分组路由做出选择；而在虚电路方式中，只需在连接建立时确定路由。确定路由选择的策略称路由算法。,路由（径）选择根据一定的原则和算法在所有传输通路中选择一条通往目的结点的最佳路径。 路由选择算法路由选择过程中采用的策略。,路由选择算法分类,1、根据能否适应通信量和拓扑结构变化 非自适应（静态路由）：可靠性差、简单 自适应（动态路由）：实现复杂、可靠性高实用 2、根据源节点向外发送数据方式 全路发送（扩散式） 统称多路发送

2、几路发送（选择扩散式） 单路发送,固定式（静态路由） 单路发送 适应式（动态路由） 最短路法 分布式 局部延迟法,典型的路由选择算法,1、多路发送 特点：可靠性高、盲目性大（重复分路多）、通信量大,几路发送 特点：通信量减小、可靠性降低,2、固定式（网中每一个结点存放一张事先确定好的路由表（存放最佳路由） 表中给出本结点到各目的结点的最短路径 例 一旦C和E之间的 网络断开，则A、 B无法通信。 特点：简单、可靠性差（不能适应网络状态变化），适用于小型网络，（人工维护路由表）,3、适应式（动态路由选择）适用于中型网络 路由表动态设置（不需要人工干预） 实现方式：相邻结点（交换机或路由器）周期性

3、交换路由信息。,例： 一旦结点C与结点E之间断开，则结点C向结点A反馈信息，通过其他路径进行通信。,分布式路由算法,1、基本思想：每个结点周期性地从相邻的结点获得网络状态信息，同时将本结点做出的决定周期性地通知周围的结点，以使这些结点不断地根据网络新的状态更新其路由选择决定。 2、基本算法：距离向量法和链路状态法,距离向量路由选择算法,距离向量路由选择算法是一种最基本的动态路由选择算法。 原理：让每个路由器维护一张路由表，表中给出了到每个目的地已知的最佳距离和路径。通过与相邻路由器之间周期性地相互交换信息，来更新表中的信息。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。,

4、基本思想：每个结点保持两个向量 和 ；每隔一段时间（如128ms）相邻节点交换时延向量；根据收到的全部时延向量修改本结点时延向量和后继结点时延向量。,延迟向量 其中： A为结点 的所有相邻节点 指结点到结点自身的延迟,后继结点向量 使每个结点 最小,如下图1所示网络，图2是更新前结点1的路由表,1、路由表中给出了结点1的两个向量 和 。 2、经128ms后，结点1收到3个相邻节点(2、3、4)的时延向量 、 、 ，进行更新运算，得到更新后的路由表。,例：计算,计算 最小值,得到了结点1的新的部分路由表,链路状态路由选择算法,链路状态算法，又称最短路径优先算法。与距离向量算法不同 的是，由于这种

5、算法需要每一个路由器都保存一份最新的关于整个网络的网络拓扑结构数据库，因此路由器不仅清楚地知道从本路由器出发能否到达某一指定网络，而且能够到达的情况下，还可以选择出最短的路径以及采用该路径将经过的路由器。链路状态算法使用LSP(链路状态数据包)、网络拓扑数据库、SPF路径选择算法、SPF树，最,终计算出从该路由器到其他目标网络的最短路径，这些路径就构成了路由表。该算法要求每个路由器具有唯一的名字或标识。 算法思想：链路状态算法的思想十分简单，其具体工作过程如下。 每个路由器必须： (1)发现与它相邻的路由器，并知道其网络地址； (2)测量它到达各相邻路由器的传输代价； (3)组装链路数据包(L

6、SP),以便把它所知信息发送给,网络上所有其他的路由器； (4)发送LSP给网络上所有其他的路由器，以便创建网络拓扑结构数据库(即：SPF树)； (5)计算到每个其他路由器的最短路径； (6)路由器将计算出的最短路径以及所有的该路由器的网络端口信息添加到路由表中。,由于链路状态算法要求各路由器的网络拓扑结构数据库相互一致；因此，当链路状态发生变化时，最先检测到这一变化的路由器需要将变化的情况发送给其他的路由器。每当路由器收到新的LSP，它都会重新计算最短路径并更新路由表，保证各路由器在网络拓扑结构方面重新达成一致；当网络拓扑结构数据库创建后变化时，每个路由器使用最短路径算法来找出到其他路由器的

7、最短路径。,具体步骤： （1）构造链路状态信息每个结点收集与其相邻的结点及其延迟信息。 通过:HELLO分组确认相邻节点。 ECHO分组收集该结点到相邻结点的延迟（要求对方立即响应）。 通过上述信息来构造链路状态分组（反映与某结点相邻的所有结点的状态）。,例：,2、发送链路状态分组（采用扩散式） 3、计算新路由（采用Dijstra算法） 当一个结点获得了一整套的链路状态分组后，便可以用Dijstra算法找出它到所有可能目的结点的最短路径，并更新路由表。,最短路径算法,在路由选择算法中都要用到求最短路径算法。其中最出名的求最短路径的算法有两个，即Bellman-Ford算法和Dijkstra算法

8、。这两种算法的思路不同，但得出的结果是相同的。我们下面只介绍Dijkstra算法。它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改造为链路时延或费用，这就相当于求任意两节点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。,下面就以图1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便起见，设源结点为结点1.然后一步一步寻找，每次找一个结点到源结点的最短路径直到把所有的点都找到为止。,令D(v)为源结点（记为结点1）到某个结点v的距离，它就是从结点1沿某一路径到结点v的所有链路的长度之和。再令 为结点 至结点 之间

9、的距离。整个算法只有以下两个部分： （1）初始化： 令N表示网络结点的集合。先令 .对所有不在N中的结点v，写出,若结点v与结点1直接相连 若结点v与结点1不直接相连 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替 。对于上述例子，可以使用 。 （2）寻找一个不在N中的结点 ，其中 的值为最小。把 加入到N中。然后对所有不在N中的结点v，用 中较小的值去,更新原有的 值，即： (1) （3）重复步骤(2)，直到所有的网络结点都在N中为止。 下表1是对图1的网络进行求解的详细步骤。,现在我们对以上的最短路径树的找出过程进行一些解释。,距离向量算法与最短路径算法的比较,距离向量算法和链路状态算法各有千秋，两种算法的差别基本上可以归纳为表2中的几点，我们可以以此作为集体应用中选择路由选择协议的技术依据。,需要注意的一个问题,收敛是路由算法选择时所遇到的一个重要问题。一个理想的路由选择算法其收敛时间应越短越好，收敛时间是指从网络的拓扑结构发生变化到网络上所有的相关路由器都得知这一变化，并且相应地做出改变所需要的时间。这一时间越短，网络变化对全网的扰动就越小。收敛时间过长会导致路由环路的出现。 距离向量路由选择算法的收敛时间就相对较长。特别当网络出现故障时，要经过很长的时间