1、第 2 章 路由选择与流量控制 第 2 章 路由选择与流量控制 2.1 路由算法概论路由算法概论2.2 路径选择路径选择2.3 流量分配与控制流量分配与控制第 2 章 路由选择与流量控制 2.1 路由算法概论路由算法概论 2.1.1 2.1.1 对路由算法的要求对路由算法的要求路由算法是网络层的协议,路由算法既要试图使网络的通信量最大,又要试图使网络的平均分组时延最小。路由算法通常很复杂,这主要表现在:(1)路由算法要求子网中的所有节点相互协调,而不像链路层和高层那样仅涉及一对对等模块之间的协调。(2)路由算法必须处理链路和节点的故障,要求对业务进行重新定向和对系统维持的数据库进行更新。(3)
2、必须达到高的性能,当网络部分区域拥塞时,路由算法必须能够修正路由。第 2 章 路由选择与流量控制 一个理想的路由算法应具有如下一些特点:(1)最优性:指路由选择算法选择最优路径的能力。(2)简易性和低开销。(3)强壮性和稳定性。(4)快速收敛性:路由选择算法必须能够迅速收敛,收敛是所有路由器在最佳路径上取得一致的过程。当一个网络由于某种事件造成路由器停机或开通时,路由器就会发送修正的路由消息,该消息在网络上传播,引发路由器重新计算最佳路由,并最终促使所有路由器承认新的最佳路由。路由选择算法收敛过慢,会导致路由循环或网络发生故障。第 2 章 路由选择与流量控制(5)灵活性:表示路由选择算法必须迅
3、速准确地适应不同的网络环境。目前已有许多种路由选择算法,大致可分为确定型路由选择算法和适应型路由选择算法。适应型算法在确定路径时或多或少要用到网络状况的当前信息(通信量、网络拓扑结构等),从而得到路由匹配网络的实际状况。需要加以区分的是路由表和路径选择:路由表是一套确定信息传输路径的方法,这种路径的确定通常事先完成。路径选择是指信息传输前,在可能的路径中选择一条路径的方法。第 2 章 路由选择与流量控制 2.1.2 2.1.2 路由选择算法路由选择算法1.1.确定型路由选择算法确定型路由选择算法(1)静态路由法:网络管理员在路由选择开始前就已建立了路由映射表,如果网络管理员不改变它们,这些映射
4、将保持不变。此方法设计简单,并在路由信息流相对可以预见且网络设计相对简单的环境里运行较好。但它不能对网络的变化做出反应,不适应当今大型、易变的网络环境。第 2 章 路由选择与流量控制(2)泛洪法:源节点将消息以分组的形式发给其相邻的节点,相邻的节点再转发给它们的相邻节点,继续下去,直到分组到达网络的所有节点。为了限制分组的传输次数,需要以下两个附加规则。若节点B从A收到一个广播的分组,则B不会将该广播分组再转发给A。每个节点仅将相同的广播分组最多一次转发给邻节点。具体的实现方法是:源节点广播的每一个分组都有一个标识符(ID)和序号,每发送一个新的分组,序号加1。每个节点在中转时,记录该分组的序
5、号。每个节点仅中转大于记录中最大序号的分组,所有小于或等于记录序号的分组都被丢弃,而不会被中转,如图2.1所示。图中箭头上的标号表示该分组被中转的次数。图中A是广播的发起点。设L为网络的链路数,则该方法的分组传播次数在L2L之间。第 2 章 路由选择与流量控制 图 2.1 泛洪法路由 第 2 章 路由选择与流量控制 2.2.适应型路由选择算法适应型路由选择算法(1)集中式:网络的路由是由路由控制中心计算的,该中心周期性收集各链路的状态,经过计算后周期性地向各网络节点提供路由表。该算法存在的问题是网络状态信息的实时性差,抗故障能力低,会导致出现不稳定的现象。(2)分布式:网络中所有节点通过相互交
6、换路由信息,独立地计算到达各节点的路由。第 2 章 路由选择与流量控制(3)隔离式:仅仅把节点的本地信息用于路由,采用分布式方法。具体有“热土豆法(Hot Potato)”、替代路径法和回头认路法(Backward Learning)等。(4)混合式：采用混合式是很普遍的,例如可在不同的网络等级层面采用不同的路由方法;电话采用静态路由法加上适应型路由法;在数据网中有泛洪法与回头认路法的组合,当对网络缺少预先了解的情况下可采用泛洪法来进行路由,然后再采用回头认路法进行路由。第 2 章 路由选择与流量控制 2.2 路径选择路径选择 2.2.1 2.2.1 最小支撑树最小支撑树对于通信网络来说,利用
7、支撑树来实现广播是比较经济的,但每一条链路的成本或时延通常是不同的,这时就要考虑树中各链路的重量(成本或时延)。若连通图本身不是一棵树,则其支撑树不止一个，但满足一定条件的权值之和为最小的支撑树(MST)至少存在一个。寻找最小支撑树(MST)是一个常见的问题。可分为两种情况:一种是无限制条件的情况,另一种是有限制条件的情况。以下分别讨论两种情况的算法。第 2 章 路由选择与流量控制 1.无限制条件的情况无限制条件的情况(1)Kruskal方法。Kruskal方法简称K方法,具体步骤如下:K0:将连通图中所有的边按权值非递减次序排列。K1:取权值最小的边作树枝,再按K0的次序选边为树枝,使其不与
8、已选边形成回路。若形成回路,则删去这条边。K2:直到n个点的图选出n-1条边结束。第 2 章 路由选择与流量控制【例2.1】要建设连接如图2.2所示的六个城镇的线路网,图上所标权值为两城镇之间的距离,请用K方法找出连接这六个城镇线路费用最小的网路结构图(设线路费用与距离成正比)。第 2 章 路由选择与流量控制 图 2.2 六个城镇的地图 第 2 章 路由选择与流量控制 解解:这是一个求最小支撑树的问题。K0:将各城镇之间的距离按非减序排列,如表2.1所示。表表 2.1 各城镇之间的距离按非减序排列各城镇之间的距离按非减序排列 第 2 章 路由选择与流量控制 K1:按顺序选边。(V1,V2)距离
9、为1 km。(V1,V6)与已选边没有形成回路,故保留,距离为2 km。(V2,V6)与已选边形成回路,故舍去。(V4,V5)与已选边没有形成回路,故保留,距离为4 km。(V3,V4)与已选边没有形成回路,故保留,距离为5 km。(V2,V3)与已选边没有形成回路,故保留,距离为6 km。第 2 章 路由选择与流量控制 K3:至此已形成六个点、五条边的树,即为所求,如图2.3所示。图 2.3 最小费用网络结构图 第 2 章 路由选择与流量控制 网路总长度为:1+2+4+5+6=18 km(2)PrimDijkstra方法。PrimDijkstra方法简称P方法,具体方法为:选择任一个单节点作
10、为一个子树,然后每次选择一条具有最小权重的输出链路(输出链路指该链路的一个端点在子图内,另一个端点不在子图内)来扩展这个子图,最终即可生成MST。用P算法解【例2.1】中问题的过程如图2.4所示。图2.4中,我们先选择V3作为一个子树,得网路总长度为 5+4+6+1+2=18 km 有时用两种方法得到同一图的最小支撑树可能不同,但两棵最小支撑树的权值之和一定相同。第 2 章 路由选择与流量控制 图2.4P算法构造最小支撑树第 2 章 路由选择与流量控制 2.有限制条件的情况有限制条件的情况在设计通信网的网路结构时,经常会提出一些特殊要求,如两个交换中心之间通信时,转接次数不能太多;某条线路上的
11、话务量不能太大等。这类问题可归结为在限制条件下求最小支撑树。例如在图2.2中,假定任意两点间的转接次数不能超过3,那么可以将(V2,V5)连接,将(V3,V4)断开,则得到如图2.5(a)所示的有限制条件的最小支撑树T1,它的权值之和为20 km。又如(V1,V2)和(V2,V5)上话务量太大,则将(V2,V6)和(V2,V4)相连,将(V1,V6)和(V4,V5)断开,得到如图2.5(b)所示的最小支撑树T2,它的权值之和为25 km。第 2 章 路由选择与流量控制 图 2.5 有限条件的最小支撑树(a)T1;(b)T2 第 2 章 路由选择与流量控制 关于有限制条件的最小支撑树的算法,我们
12、这里简单介绍以下两种:(1)穷举法。其基本思想是把图中所有主树穷举出来,再根据限制条件筛选,求得最短主树。这是一种计算量较大的求解方法，仅适用于小容量的网络。(2)调整法。该算法采用启发式,不像穷举算法那样进行试探求树。它不能得出最小支撑树,只能得到最佳解。它先选定适当的求最小支撑树的准则来求树。但进行过程中,每一步要判断是否满足限制条件,否则进行调整,直至最后得到符合限制条件的最小树。第 2 章 路由选择与流量控制 2.2.2 2.2.2 点间最短路径算法点间最短路径算法1.1.指定点到其他各点的最短路径算法指定点到其他各点的最短路径算法通常我们采用Dijkstra(简称D算法)和Bellm
13、anFord算法(简称BF算法)。1)D算法D算法的基本思想是按照路径长度增加的顺序来寻找最短路径。假定所有链路的长度均为非负。显然有:到达目的节点的最短路径中最短的肯定是目的节点的最近的邻节点所对应的单条链路(由于链路长度非负,所以任何多条链路组成的路径的长度都不可能短于第一条链路的长度)。最短路径中下一个最短的肯定是目的节点的下一个最近的邻节点所对应的单条链路,或者是通过前面选定节点的最短的由两条链路组成的路径,依此类推。第 2 章 路由选择与流量控制 具体的D算法如下:设每个点都有权值wi,对已选定点,权值是目的节点vs到该点的最短路径长度;对未选定点,wi是暂时的,是vs经当前P中的点
14、到该点的最短路径长度。其中P是已选定点集,G-P是未选定点集。算法的步骤如下:D0:定vs,有P=vs,ws=0,wj=djs,js(如果(j,s)P,则djs=)。D1:(寻找下一个与目的节点最近的节点)求使下式成立的i,iP jPjwwi min置P=Pi。如果P包括了所有节点,则算法结束。第 2 章 路由选择与流量控制 D2:对所有,置 Pjijijjwdww,min返回D0。D算法的应用如图2.6(c)所示。第 2 章 路由选择与流量控制 图 2.6 D算法和BF算法应用举例(a)网络拓扑举例;(b)BF算法;(c)D算法 第 2 章 路由选择与流量控制 2)BF算法设表示具有下列约束
15、条件的、从给定节点i到目的节点s的最短路由:链路中最多包括h条链路。链路仅经过目的节点s一次。hiD第 2 章 路由选择与流量控制 为了表示方便,对所有的h,令=0,则BF算法实现的步骤是:B0:令Di0=(is)。B1:利用迭代公式(对所有的i1)依次迭代产生Di1,Di2,Dhi)。B2:依此类推。如果对所有i有:Dhi=Dh-1i(即继续迭代下去以后不会再有变化),则算法在h次迭代后结束。min1hjijjhiDdDhsD第 2 章 路由选择与流量控制 2.任意点之间的最短路径算法任意点之间的最短路径算法求任意点之间的最短路径,可以依次选择每个点为指定点,用D方法或BF方法做n次运算,但
16、这样算比较繁琐,这里介绍更为有效的算法Floyd算法,简称F算法。它的算法原理与D方法相同,只是使用矩阵形式进行运算,有利于在计算机中进行处理。对有n个点,各边权值为dij的图G,顺序计算图G的权值矩阵W和路由矩阵R,其步骤如下:第 2 章 路由选择与流量控制 F0:径长矩阵,路由矩阵,其中 nnijwW00nnijrR00,0,0ijijdwvi和vj间有边 vi和vj间无边 i=j 式中,dij为边(vi,vj)的权值。,0,0jrijj iwwijij或00第 2 章 路由选择与流量控制 F1:已得Wk-1和Rk-1矩阵,求Wk和Rk矩阵的元素为,1,),min(1111krrwwwwk
17、ijkijkkjkikkijkij11kijkijkijkijwwww由上述步骤可见,wk-1wk是计算经vk-1转接时是否能缩短路径长。如有缩短,更改wij并在R矩阵中记下转接的点,最后算得Wn和Rn,就可得到最短路径长和转接路由。第 2 章 路由选择与流量控制【例2.2】用F方法计算图2.7中任意两点间的最短路径。图 2.7 任意点之间的最短路径算法 第 2 章 路由选择与流量控制 解解:首先写出W0和R0，即 第 2 章 路由选择与流量控制 第 2 章 路由选择与流量控制 第 2 章 路由选择与流量控制 式中第 2 章 路由选择与流量控制 第 2 章 路由选择与流量控制 3.3.次短路径
18、的算法次短路径的算法在实际问题中,除求最短路径外,往往还需要求次短路径。例如当通信网中某两点之间的首选路由的业务量出现溢出或发生故障时,就需寻找次短路径或更次短路径作为首选路由的第一、第二迂回路由。业务量溢出或故障可能发生在某段或某几段电路或某个交换节点上,所以次短径可分为两类:一类是与最短路径的某些边分离的次短路径;一类是除起点和终点外,与最短路径某些点分离的次短路径。第 2 章 路由选择与流量控制 第一类次短路径的求法:用F或D算法得到最短路径后,从图中去掉这条路径的某条或某几条边,然后在剩下的图中用D算法求最短路径,就是所求的次短路径。再依此方法可求出第二、第三条次短路径。第二类次短路径
19、的求法是将最短路径中的某些点去掉,然后在剩下的图中求最短路径,同样,依此方法求出其他次短路径。第 2 章 路由选择与流量控制 2.3 流量分配与控制流量分配与控制 2.3.1 2.3.1 概述概述流量控制(Flow Control)是网络层的又一个主要功能。通信网运行的主要作用是使信息流沿不同的路径从源节点流到目的节点。由于用户终端发送信息时间和数量的随机性,且对于一个实际的通信系统,每一个节点的存储容量和处理能力以及每条链路的传输能力都是有限的,这样就可能会造成网内信息流的严重不均匀,不能达到应有的传输水平,致使有些节点和链路利用率低,或者超过节点的存储处理能力与链路传输能力而导致网络阻塞。
20、这就要求采用必要的流量分配和控制技术,从而保证网络的正常运行。流量分配的好坏,将直接关系到网的使用效率和相应的经济效率。可见,网中流量分配是网络运行的重要指标之一。第 2 章 路由选择与流量控制 网内流量控制是在给定网络的拓扑结构,以及已知节点和链路容量的条件下进行的。其仅涉及到给定发送节点之间的点对点业务流,任务是保证快速发送的节点不会连续发送速率高于接收节点可接收速率的数据。此时的流量控制实际上相当于在约束条件下的流量控制优化问题。通信网中的流量是指通信线路的信息容量或链路权值，具体指的就是网中能传输的电话路数及数据速率。通信流量具有随机特性,我们讨论的是平均流量分配问题。第 2 章 路由
21、选择与流量控制 2.3.2 流量控制的方法流量控制的方法我们已知,一个具有节点集V=v1,v2,vn和链路集E=e1,e2,en的通信网,可以用一个有向图G(V,E)来表示。设一条链路eij(或eji)上的流量为fij,容量(eij上的最大流量)为Cij,并称E的流量集合fij为网流或流。设从节点s到节点t的流量为fst,当其满足以下条件时，即(1),0,ststjjijijffffi=s i=t is,it 第 2 章 路由选择与流量控制(2)jjijijff定义fst为可行流。这里,我们认为网流是从s流到t的。因此,将节点s定义为源节点,节点t定义为汇节点,网中其他节点则定义为中间节点。第
22、 2 章 路由选择与流量控制 若定义流出节点i的网流为 jjijijff则流出源节点s的网流是fst,流入汇节点t的网流也是fst,而流出汇节点t的网流则为-fst,经由中间节点的网流恒等于零。因此,(1)中的方程称为流量守恒方程。确定最大可行的可行流(确定所谓最大流问题)也就是调整fij使网中可行流值fst最大。第 2 章 路由选择与流量控制 理论证明,网G(V,E)中,有),(minmax,iistxxCf式中,fst,max为节点s到t的最大流;X是V的子集,X=V-X;sX,tX;从s到t的边称为前向边,从t到s的边为后向边。其中有 中容量最小者为所有),(),(min),(),(),
23、(),(XXCxxCXXyxyxCXXCii求最大流的算法是在网中搜索每一条从s到t的可增流的路径前向边未饱和、反向边为非零流的路径。在不破坏有限性(超过容量)的原则下,正向边上增流,或在不破坏非负性(不低于零流)的原则下,反向边上减流,使总流量得以加大。第 2 章 路由选择与流量控制 实际的通信网中,除了每条链路有最大容量Cij规定外,尚有费用ij要求。这就出现了所谓的最佳流量问题。即调整每条链路上的流量fij,不仅要求获得最大流量,同时,还要求代价最低,以获得总费用最小，有 Eeijijijf式中,fij为链路eij上的流量,其最大值为容量Cij;ij为链路eij上单位流量的费用。不同分配
24、情况下(各链路上流量分配值不同)的同一可行流fst,其费用可以不同。寻找最佳流量的算法,就是在给定图G(V，E)中,保持可行流fst不变的情况下,只要在源宿之间存在有两条以上的路径,变更其上流量分配的方法,以使总费用最小。第 2 章 路由选择与流量控制 以上的最大流量、最佳流量算法基本都是线性规划问题。实际上的通信网,往往还存在其他一些约束条件,因此有了更一般的流量优化问题。即要在如下一些约束条件下来考虑总费用问题:(1)每条链路上的流量fij可调整,但是,每个转接节点上的最大容量Cii和每条链路上的最大容量Cij有限制。(2)网络的其他指标(如呼损,时延等)有限制。(3)有多个源、汇节点。第
25、 2 章 路由选择与流量控制 这样,总费用为 Eeijijijc式中,ij为链路eij上单位容量费用;ij为转接节点上单位容量费用;cij为链路eij的容量;cii为转接节点容量。因此,要从最小出发来获得最佳流。显然,这已经不是线性规则问题了。再考虑流的随机特性,问题就复杂了。第 2 章 路由选择与流量控制 常用的流量控制方法可列举如下:(1)缓冲器预约是在源到目的节点之间的控制方法。每个源节点发送一个“请求缓冲存储”分组来为每个报文预定空间。当目的节点收到这一请求分组之后,如果该节点有足够的存储空间,就返回一个“分配”分组。在目的节点收到所有的分组并装配以后,则返回一个“接收下一报文就绪”(
26、RFNM)的确认信号。如果节点具有给其他报文的缓冲存储空间的话,可以用RFNM捎带一个分组,如果源点无分组可送,则发出一个归还分组,以释放存储空间。第 2 章 路由选择与流量控制(2)许可证法是英国国家物理实验室提出的一个网络级流量控制方法。网络内的各个节点持有一定数量的许可证,分组必须占有许可证才能从主机进入网中。一旦占有许可证的一个分组进入网内,则网中的许可证数减1,当一个分组离开网络送交主机后,许可证的数目增加1。这样,就对进入网络的分组数量予以控制,从而避免了全网范围内的拥塞。(3)窗口控制是既可应用于相邻节点之间又可应用于两DTE(数据终端设备)之间的一种信息流的控制方法。在控制过程中,发送的上限被设定,随着数据单元的发送窗口逐渐缩小,在收到对端的接收确认信号以后,窗口又逐渐扩大,数据单元发送的数量受到控制,从而有效地控制了发送分组的数量,避免了局部拥塞。
