第五章路由算法课件

第五章路由算法5.1路由算法概述1.路由算法的功能2.面临的问题3.路由选择的目的和要求例5.1网络中有两个源节点和一个目的节点。所有链路的容量为10个单位，两个源节点1和2的输入业务量分别为λ1

和λ2，试讨论（1）λ1=λ2=5单位时（2）λ1=5单位，λ2=15单位时，路由选择对网络性能的影响（1）如果节点1选择1-3-6，节点2选择2-5-6，则由于每条链路的业务量只有信道容量的一半，因而时延很小。如果节点1选择1-4-6，节点2选择2-4-6，则链路4-6运载的业务量为10个单位，达到了链路的最大容量，因而时延会很大。（2）节点2的输入业务量为15个单位，由于媒体链路容量仅为10个单位，在仅使用一条路径情况下，节点2至少要丢掉5个单位的业务量。如果节点2将输入业务量在2-4-6和2-5-6之间分摊，节点1选择1-3-6，则每条链路上的业务流量都不超过链路容量的75%，因而实验较小。4.路由选择算法的分类4.路由选择算法分类5.对路由选择算法的要求6.路由算法的实现——路由表7.路由算法和流量控制的关系5.2电路交换网络中的路由静态路由方式网络交换机被组织成树形结构或层次结构路由选择机制无法适应条件的变化动态路由方式：选择路由时受当前通信量条件的影响。电路交换节点之间是同级关系，而不是层次关系路由选择更加复杂、灵活交替路由交替路由选择机制的基础：两个端局之间能够使用的路由是预先定义好的。由主呼交换机负责为每次呼叫选择合适的路由所有的交换机都有为各目的站点预定好的路由作为参考路由选择序列反映了根据历史通信量模式做出的分析，并在设计时优化了网络资源的利用从端局X到端局Y的交替路由5.3分组交换网络中的路由选择1.性能评估标准Minimumhop（最小跳数）Leastcost（最小成本）链路长度数据率链路容量传输时延节点缓冲区被占用的程度链路的差错率分组的丢失率ExamplePacketSwitchedNetwork2.路由选择策略固定式路由选择（Fixed）洪泛式路由选择（Flooding）随机路由选择（Random）自适应路由选择（Adaptive）固定式路由选择固定式路由选择为网络中的每一对源节点和目的节点选择一条永久的路由。这些路由是固定的，只有在网络拓扑结构发生改变时，它们才有可能改变因此，在设计路由时所使用的链路代价不可能是基于通信量的动态改变需要创建一个中心路由选择矩阵，它可能保存在网络的控制中心。该矩阵指出每一对源节点和目的节点的路由途中的下一个节点标识每一个节点只需要保存路由表的一列固定

路由

选择使用固定路由选择，数据报和虚电路在路由选择时没有区别。从指定源节点到指定目的节点的所有分组都沿相同的路由前进。固定路由选择的优点是它的简洁性，并且在一个具有稳定负荷的可靠网络中表现良好。其缺点在于缺乏灵活性，无法对网络拥塞或故障做出反应。洪泛式路由选择这种技术不需要任何网络信息，其工作过程如下：一个分组由源节点发送到与其相邻的每一个节点上在各个节点上，收到的分组再次被传输到除分组到达时所经过的链路外的所有输出链路。最终会有几分这个分组的副本到达目的节点这个分组必须具有某种唯一性的标识（如源节点和序号，或许电路号和序号）以便目的节点保留所收到的第一份副本，而丢弃其他副本。为防止分组在网络中无穷无尽地传输，也可以让节点记住所重传过的那些分组的标识，当该分组的副本再到达时被丢弃；或者在每个分组中包含一个跳数计数器字段，每次节点向前传输一个分组时，将该分组计数器值减一，当计数器值为零时，该分组被丢弃。洪泛式路由选择洪泛式技术的特点洪泛式技术具有三个重要属性：在源点和终点之间的所有路由都被尝试过非常稳健可用于发送紧急报文因为所有路由都被尝试过，因此分组至少有一个副本使用的是最小跳数路由到达终点可用于虚电路路由的最初建立所有直接或间接与源节点相连的节点全部被访问到对于某些向所有节点散播的重要信息来说十分有用，被用于某些路由选择策略的信息发布机制中随机路由选择使用随机路由选择时，为了重传收到的分组，节点只选择一条输出链路。这条链路是从除了分组到达时所经过的那条链路之外的其他链路中随机选取的。如果所有链路被选中的可能性都相等，那么节点可能会简单地以轮流方式使用输出链路。改良方法是为每条链路分配一个概率，并根据概率来选择链路。这个概率可以基于数据率或固定链路代价的。与洪泛式一样，随机路由选择不需要使用网络信息。因为采取什么路由是随机决定的，所以实际的路由往往既不是最小代价路由也不是最小跳数路由自适应路由事实上，所有分组交换网络中，都使用了某种形式的自适应路由选择技术。即路由选择的判决随网络条件的变化而改变。影响路由选择判决的主要条件有：Failure（故障）Congestion（拥塞）要使自适应路由选择成为可能，就必须在节点和节点之间交换有关网络状态的信息。与固定式路由选择相比，自适应路由选择的缺点：路由选择的判决更加复杂，因而增加了网络节点的处理负担大多情况下，自适应策略所依据的状态信息是从一个地点收集却在另一个地点使用。此时，需要在信息质量和额外开销之间寻求平衡。交换的信息越多，且交换频率越快，则每个节点所做的路由判决越好，但另一方面，这个信息本身就是网络的负荷，它会导致性能下降。自适应策略可能反应过快，导致拥塞发生震荡。如果反应太慢，那这个策略又没有什么实际的用处AdaptiveRouting-Advantages目前为止，自适应路由选择仍是使用最普遍的：从网络用户的角度来看，能提高网络性能有助于拥塞控制自适应路由选择策略的分类以信息源为依据，分为三类：本地的（独立的）网络中的节点在为每个分组选择路由时会选择队列长度Q最短的输出链路。它具有平衡输出链路负荷的效果，但有些输出链路所指的大方向可能不正确。加上对首选方向的考虑，就能改善上述缺陷。从节点出发到每个目的站点的各条链路具有一个偏移值仅根据本地信息的自适应机制很少使用相邻节点的所有节点的IsolatedAdaptiveRouting（独立的自适应选择）5.4

最小代价算法所有分组交换网络的路由选择判决都是基于某种形式的最小代价标准如果这个标准取得是最小跳数，那么每条链路具有的值都是1更常见的情况是链路的值与链路容量成反比，与链路当前负荷成正比，或是这两者的结合。最小代价算法可描述如下：假设一个网络节点由双向链路连接，其中每条链路的各个方向上都有一个相关的代价，并且定义两个节点之间的路径代价为途径的链路代价的总和。对于每一对节点找出具有最小代价的路径。需要注意的是：一条链路在两个方向上的代价可能不同。5.4.1Dijkstra算法Dijkstra算法思路如下：通过拓展路径以不断增加这条路径的长度，从而寻找给定源节点到所有其他节点之间的路径。该算法分阶段进行：在第k阶段，已经判断出k个离源节点最近的（它们之间的代价最小）节点具有的最短路径，这些节点在集合T中。在第k+1阶段，不在T中但具有到源节点最短路径的节点被加入到T中。当每个节点加入T时，就定义了它与源节点之间的路径。算法中变量N

：网络中的节点集合s：源节点T

：目前由算法合并的节点集合w(i,j)

：节点i到j之间的链路代价w(i,i)=0w(i,j)=

如果两节点之间不是直接连接的w(i,j)

0如果两节点之间是直接连接的L(n)

：算法目前所知从节点s到节点n的最小代价路径的代价算法结束时，就是从节点s到节点n的最小代价路径的代价Dijkstra算法Step1初始化T={s}

目前的节点集合只有源节点L(n)=w(s,n)forn≠s相邻节点的初始路径代价就是链路代价Step2

找到下一个节点从不属于T的相邻节点中找到到源节点路径代价最小的节点x将该节点x合并到T中向T加入一条边，这条边恰好在x上，且在L(x)中加入最小代价元素Step3

更新最小代价路径L(n)=min[L(n),L(x)+w(x,n)]

foralln

ÏT如果后一项较小，则从s到n的路径变为从s到x的路径与从x到n的链路衔接） 循环step2-step3，当所有节点都已经加入T后算法终止Dijkstra’sAlgorithmNotes结束时，与各节点x相关的值L(x)是从s到x的最小代价路径的代价）T定义了从s到各节点的最小代价路径第2步和第3步每循环一次就向T中加入一个新节点并定义了从s到该节点的最小代价路径

ExampleofDijkstra’sAlgorithmResultsofExampleDijkstra’sAlgorithmIterationTL(2)PathL(3)PathL(4)PathL(5)PathL(6)Path1{1}21–251-311–4

-

-2{1,4}21–241-4-311–421-4–5

-3{1,2,4}21–241-4-311–421-4–5

-4{1,2,4,5}21–231-4-5–311–421-4–541-4-5–65{1,2,3,4,5}21–231-4-5–311–421-4–541-4-5–66{1,2,3,4,5,6}21-231-4-5-311-421-4–541-4-5-65.4.2Bellman-Ford算法B-F算法可叙述如下：从给定的源节点找出一条最短路径，该最短路径是从所有最多只含一条链路的路径中选择出来的；接着再找出条件为所有路径最多只含两条链路的最短路径，以此类推。

算法也是分阶段进行。定义变量如下：s：源节点w(i,j)

：节点i到节点j之间的链路代价w(i,i)=0w(i,j)=

如果两节点不是直接连接的w(i,j)

0如果两节点是直接连接的h：算法当前阶段中的路径具有的最大链路数Lh(n)

：在不多于h条链路的条件下，从节点s到节点n的最小代价路径的代价Bellman-Ford算法Step1初始化L0(n)=

,foralln

sLh(s)=0,forallhStep2更新对每个后继的h

0对每个n≠s,计算Lh+1(n)=minj[Lh(j)+w(j,n)]将n与前一次处理的节点j相连接，以获取最小值删除在以前循环时形成的n与任何其他前次处理节点之间的连接从s到n的路径以从j到n的链路结束Bellman-FordAlgorithmNotes第二步中当h=K，并且对每个目的节点n，算法将从s到n的长度为K+1的可能路径与前一次循环结束时得到的路径相比较如果前次更短路径具有较小代价，则仍保持前次路径否则，从s到n之间定义一条长度为k+1的新路径ExampleofBellman-FordAlgorithmResultsofBellman-FordExamplehLh(2)PathLh(3)PathLh(4)PathLh(5)PathLh(6)Path0

-

-

-

-

-121-251-311-4

-

-221-241-4-311-421-4-5101-3-6321-231-4-5-311-421-4-541-4-5-6421-231-4-5-311-421-4-541-4-5-65.4.3Comparison这两种方法得到的结果一致从需要搜集的信息方面比较Bellman-Ford对节点n的计算涉及到节点n与所有相邻节点之间的链路代价再加上从某个特定源节点s到这些相邻节点之中每个节点的路径总代价，每个节点可以维护一个代价集合，以及与网络中的其他节点相关的路径，并能在直接相邻的节点之间经常交换这些信息。这样每个节点都能够使用第2步的表达式，且仅需要根据从它的相邻节点处得到的信息，以及它自己的链路代价信息来更新它的代价和路径。Dijkstra第3步要求每个节点必须知道网