多播路由中的问题及算法_徐征
多播路由中的问题及算法
徐征,黄传河,吴小兵
(武汉大学软件工程国家重点实验室,湖北武汉430072)
摘要:根据多点广播服务的最优化函数和限制条件对多播路由中的问题进行了分类,对每类问题提出了基本的路由算法,并讨论了它们的优缺点。
关键词:多播;服务质量保证;路由算法;多播分类
中图分类号:TP393文献标识码:A文章编号:1001-3695(2001)12-0010-04
Problems and Algorithms in Multicast Rou ting
XU Zheng,HUANG Chuan-he,WU Xiao-bing
(State Ke y Lab1o f So ftware Engineering,Wuhan Universit y,Wuhan Hube i430072,China)
Abs tract:This paper provided a comprehensive overview of existing multicas t routing algori thms.In particular,we classi fy multicas t routing problems according to thei r opti miz ati on functi on and performance constrai ns,present basic routing al gori thm in each problem class and discuss thei r s trengths and weaknes s.
K ey words:Multicast;QoS;Routing Algorithm;Cl as sification
1引言
现有的Internet采用的是点到点的传送方式即单播方式。在这种方式下,发送方和每一接收方需要一单独的数据通道,从一台服务器送出的每个数据包只能传送给一个客户机,如果有另外的用户希望顺路获得这个数据包的拷贝是不可能的。这种方式会极大加重服务器的负担并浪费大量带宽。解决的办法是构建一种具有多播能力的网络,允许路由器一次将数据包复制到多个通道上。多播发送方只要发送一个信息包而不是很多个,所有目的地将同时收到同一信息包,可以更及时、更同步把信息发送到任意不知名的目的地,减少网络上传输的信息包的总量,网络成本变得相当低廉,达到从未有过的传送能力。实现多播技术要解决的关键问题是多播路由问题。
由于大量原因,在多播路由中提供QoS是很困难的。首先,诸如电视会议、视频点播、网络电话和基于Web的应用这些分布式的服务对延迟、延迟抖动、带宽以及包丢失率都有不同的要求,大量约束使多播路由很难实现。其次,当路由算法被多播路由协议采纳后,又存在很多实际问题(例如;状态集合的更新,动态拓扑结构的处理和会员变化,树的维护和可扩展性)。QoS的要求使协议设计过程更加复杂化。此外,我们必须考虑如何用最小的代价收集/维护与QoS相关的状态,如何在集合的不精确状态信息下构建一棵满足QoS的路由树,如何维护路由域之间的QoS等。
在这篇论文中,我们对最新的多播路由算法的进展进行了概述,特别强调了QoS问题。我们首先概述了多播路由问题,然后根据它们的目标函数以及树约束和链路约束在多播路由中的问题进行了分类,对每类路由问题给出了多播路由算法。最后对这篇论文进行了总结。
2多播路由中的问题
2.1网络模型
在多播路由中,网络通常表示成一个带权图G= (V,E),其中V代表节点集合,E代表连接节点的链路集合。|V|和|E|分别代表节点和链路数目。不失一般性,这里的带权图中每对节点间至少存在一条链路相连;每条链路上的参数代表链路的当前状态。例如,我们定义链路延迟函数d:E y R+,它为每条链路赋予一个非负的权重。d(l)表示一个包经过链路l I E时所产生的延迟;它包括队列延迟,传送时间和复制延迟。同样,与每个节点相关的参数代表节点的当前状态(例如可用缓存大小等),这些参数称为节点状态。由网络维护的本地状态和链路状态的集合统称为网络状态。
假设M 收稿日期:2001-03-29 能包括传送节点即一条路径上的非成员节点。我们用P T(v s,v d)表示树T中从源节点v s到接收节点v d的路径。 2.2多播路由问题的分类 给定一个多播组M和一组可能的最优目标函数0,多播路由就是在网络拓扑结构和网络函数的基础上,构建一棵使目标函数达到最优的多播树的过程。在基于约束的多播路由中,一组约束通常用点到点延迟、相互间延迟抖动限制、最小带宽、包丢失率或者它们的组合形式出现。构建的多播树不仅要满足从源节点到接收节点的可达性,而且要满足QoS要求以满足约束条件。 2.211目标函数和约束 最优化目标通常定义为使多播树代价最小的形式,这里代价可能是使用的总带宽或者网络应用中定义的函数。施加的约束可分为以下两类: p链路约束是进行链路选择时对链路使用的限制。例如,一条链路上带宽和可用缓存大小。 p树约束有以下两种: 1对多播树上从源端到接收端的每条路径上的综合性能的约束。如,从源端到所有接收端的点到点延迟。 o对从同一源端到任意两个接收端的路径上的性能差异的约束。如,从源端到任意两个不同接收端的延迟抖动。 根据树约束与相应的链路值的关系,树约束可以被细分为以下三类(其中m(l)代表链路值): p相加树约束对任意路径P T(u,v)=(u,i,j, ,,k,v),如果 m(u,v)=m(u,i)+m(i,j)+,+m(k,v)(1) 则我们说树约束是相加的。 例如,从节点u到节点v的点到点延迟d(u,v)是相加的,它等于路径P T(u,v)上每个单独链路值d(i,j)的和。 p相乘树约束对任意路径P T(u,v)=(u,i,j, ,,k,v),如果 m(u,v)=m(u,i)@m(i,j)@,@m(k,v)(2) 则我们说树约束是相乘的。 例如,从节点u经路径P T(u,v)到节点v的包丢失率1-P L(u,v)是相乘的,它等于路径P T(u,v)上每个单独链路上包丢失率1-P L(i,j)的积。 p凹型树约束对任意路径P T(u,v)=(u,i,j, ,,k,v),如果 m(u,v)=min[m(u,i),m(i,j),,,m(k,v)](3) 则我们说树约束是凹型的。 例如,从节点u到节点v的带宽是凹型的,它等于路径P T(u,v)上每个单独链路的带宽b(i,j)中的最小值。 2.212多播路由问题的分类 根据树约束/链路约束和目标函数,多播路由问题可分为以下几类: 1单链路约束问题在构建可行的多播树时加以单个链路约束(如带宽约束路由问题)。 o多链路约束问题在构建可行的多播树时加以多个链路约束(如带宽及缓存约束链路问题)。 ?单树约束问题在构建可行的多播树时加以单个树约束(如延迟约束路由问题)。 ?多树约束问题在构建可行的多播树时加以多个树约束(如延迟及延迟抖动路由问题)。 ?链路及树约束问题在构建可行的多播树时加以一个链路约束及一个树约束(如延迟及带宽约束路由问题)。 ?链路最优化问题在构建一棵最优的多播树时使用链路最优化函数(如要求多播树上链路带宽最大)。 ?树最优化问题在构建一棵最优的多播树时使用树最优化函数(如要求多播树的总代价最小),这类问题也叫做Steiner树问题。 à链路约束链路最优化问题在构建一棵符合约束条件的最优化多播树时,加以一个链路约束并使用链路最优化函数(如带宽约束缓存最优化问题)。 á链路约束树最优化问题在构建一棵符合约束条件的最优化多播树时,加以一个链路约束并使用树最优化函数(如带宽约束Steiner树问题)。 l u树约束链路最优化问题在构建一棵符合约束条件的最优化多播树时,加以一个树约束并使用链路最优化函数(如延迟约束带宽最优化问题)。 l v树约束树最优化问题在构建一棵符合约束条件的最优化多播树时,加以一个树约束并使用树最优化函数(如延迟约束Steiner树问题)。 l w链路约束及树约束树最优化问题:在构建一棵符合约束条件的最优化多播树时,加以一个链路约束和一个树约束并使用树最优化函数(如带宽及延迟约束Stei ner树问题)。 第1,o类问题是容易处理的,因为我们可以通过从网络拓扑图中删去不合要求的来满足约束条件。Wang[2]已证明寻找一条路径使之满足两个或多个相互独立的相加和/或相乘的约束条件以及它们的任意组合是NP完全的。因此问题?,?, l u在多项式时间内是可解的,而问题?则是NP完全的。问题?的一个多项式复杂度的算法可见文献[3]。如果从网络拓扑结构中移去不满足约束条件的链路,则问题8可转化为问题?,因此问题à在多项式时间内也是可解的。最后,问题?(Steiner树问题)和问题á, l v, l w(约束Steiner树问题)已被证明是NP完全的[4]。 3多播路由算法 在这部分中,我们归纳了几种解决以上几类问题的多播路由算法。 3.1最短路径树 最短路径算法使多播树上从源节点到接收节点的 每条路径上链路权重之和最小。如果所有链路的权重都为1,结果树就是最小跳树。如果权重代表链路延迟,结果树就是一棵最小延迟树。Bellman-Ford和Dijk-stra算法是两个最著名的最短路径算法,它们都是多项式复杂度的。最短路径算法可用来解决树约束问题(例如,延迟约束)。 3.2最小生成树 最小生成树是一棵覆盖所有组成员并且树权重最小的树。著名的集中式最小生成树算法是Pri m算法,而Gallager则提出了解决最小生成树问题的一个分布式算法。在Prim算法中,从任意一个根节点开始构建整棵树,直到其扩展到网络中所有节点。在每一步中,连接已选择节点与未选择节点的权重最小的边被加入到树中。算法采用了贪心策略,因为在树的增长过程中,每次选择的边都是使树权重增加最少的边。最小扩展树算法可用来解决树最优化问题。 3.3Steiner树 基于Steiner树的问题致力于使多播树的总代价最小,并且已知是NP完全问题,如果多播树包含了树中所有节点,Steiner树问题便转化为最小扩展树问题。无约束条件的Steiner树算法可用来解决树最优化问题,然而它们却无法满足端到端基础上的约束条件,因此它们不能很好满足带有此类要求的应用。Winter[5]和Hwang[6]深入研究了启发式Steiner树算法。崔烽等人提出了解决Steiner树的遗传算法[26]。Bauer[7]和Salana[8]对最新的解决Steiner树问题的算法进行了很好的总结。我们将在下面给出一个有代表性的解决方案。 3.311启发式KMB 启发式KMB算法由Kou,Markowski和Berman提出[9]。其思想是:先求出图G的最小生成树T,然后不停地搜索树,若发现T中的叶子节点不属于M(必须连接节点集合),则删去该叶子节点及其相连的边,直到所有叶子节点都属于M。启发式KMB算法所得到的树代价是Steiner树代价的两倍。 3.4约束Steiner树 Steiner树问题可以扩展为包括其它的链路约束。例如,延迟、延迟抖动或者它们的组合。这些问题也是NP完全的,它们的解决也需要采用启发式算法。 3.4.1Zhu算法 Zhu[12]提出了一种解决延迟约束树最优化问题的启发式算法,叫做Bounded Shoetest Multicast Algori thm (BS MA)。它定义了链路代价作为链路应用函数。它也定义了树的超边(Superled ge)作为最长简单路径。它的内部节点是延迟节点,每个内部节点刚好连接两条边。算法首先构建一棵以给定源节点为根节点,并且覆盖所有组成员的最小延迟树,然后反复用不在树上的代价更小的边替换树中的超边,同时不违反延迟约束条件,直到再也找不出代价更小的边。代价更小的边通过使用K-度最短路径算法(Kth Shortest Path Algo-ri thm)得到。如果存在的话,BS MA总能找到一个延迟约束多播树,因为它起始于一棵最小延迟扩展树。314.2Kompella集中式算法 Kompella提出了一种启发式算法[13],叫做KPP启发式算法。他们假设链路l(u,v)的链路延迟d(u,v)和延迟函数D是整数,那么链路(u,v)的链路代价c(u,v)就是任何正实数。他们定义: p节点u和v间的约束最小代价路径是节点u和v间的延迟小于D的最小代价路径。 p图G=(V,E)的闭包图G c是一个完全图,它包括V中所有节点,边代表约束最小代价路径。 给定源节点S和多播组M,KPP首先得到一个覆盖{S}G M的延迟约束闭包图G c,然后确定出从节点u 到节点v的延迟最小代价路径。接着,KPP使用Pri m 算法[14]得到闭包图G c的一个最小扩展树。然后从源节点开始,一次增加一条选定的边,直到整棵树包含所有接收节点。每次选择的是满足下列条件的边: p连接树节点和非树节点 p该边符合延迟约束 p使选择函数最小 KPP提出了两种选择函数:一是链路代价;另一个则强调最小代价与最小延迟之间的平衡。最后,KPP 用图中的路径替换最小扩展树中的边。如果有必要,循环以上步骤直到问题得到解决。 314.3Kopella分布式算法 Kopella等人提出了一种分布式启发算法来构建延迟约束Stei ner树[16]。算法要求每个节点维护一个到网络中所有其它节点的最小延迟距离矢量。它所构建的树最初只包括源节点,然后向树中每次增加一个接收节点,直到该树包含了所有接收节点。算法使用以下方法选择每次增加的接收节点。源节点通过已构建的部分多播树多播一个find消息。在收到fi nd消息后,节点确定一个连接树非接收者的发送链路,该链路不违反延迟约束条件并且使选择函数最小。接着,节点向源节点回送一个response消息,它包含了候选链路的标识。当收到所有的response消息后,节点s决定一条使选择函数最小的最好链路l,并把该链路加入到树中。该算法要求控制信息可多播传送。 3.5最大带宽树 Shacham提出了最大带宽树算法[3]。它使用Dijk-stra算法来计算到所有目的节点的最大单向带宽。算法步骤如下:首先,计算从源节点到所有接收节点的最大可用带宽路径,由此构建一棵最大带宽树。然后根据接收节点的接收能力将接收节点分成不同的类别。一个质量值被赋予数据的每一层。通过相加已收到的所有数据层的质量值来确定满意程度。于是便可以确定每个接收者的接收率,以使全部接收者的满意程度 最大。这种优化过程为每个接收者给出它从源节点收到数据的预期接收率,链路带宽便可在最大带宽树上进行相应分配。最大带宽树解决了链路最优化问题。 3.6其它树 Rouskas等人研究并提出了构建基于源节点的多播树以满足延迟和延迟抖动约束问题的启发式算法[19]。Chen等人提出了一种由接收者初始化的基于探索的分布式多播路由算法来构建满足QoS要求的多播树。 3.611组成员加入/退出时树的重构问题 多播组成员可以动态地加入或退出一个多播会话。因此,我们需要在组成员加入或退出时不中断正在进行的多播会话,同时多播树仍要保持接近最优化并对树中所有接收者满足QoS要求。如果每个成员加入或退出时都重新构建多播树,原有节点就不可能同时转移到新树上,于是无缝传送就不可能实现。我们可以通过逐步改变多播树来处理动态成员的加入或退出问题。当一个新成员要加入多播树时,增加一个连接新节点和最近树节点的树枝;当一个节点要退出多播树时,只需剪掉相应的树枝。因为重建一棵树的开销可能会大于这种方法所引起的开销,所以我们采用了这种方法。 许多研究者都提出了多播树的重组问题,其中比较著名的有Edge-bounded算法(FB A)[20],Bauer和Var-ma算法[21],Narvaez算法[22]和Sriram算法[23]。其主要思想是:当多播组成员加入或离开时,定义并监视这棵树的损坏因子,当损坏因子超过某个值后就触发树重构过程。 4小结 本文给出了多播网络的模型,在此模型的基础上对多播路由中存在的问题进行了分类和小结,对每类问题给出了相应的路由算法,并讨论了它们的优缺点。这些算法对实际Internet中的多播路由选择有着重要的指导意义。 参考文献: [1]K Nic hols,V Jacobson,L Zhang.A Two-Bit Differenti ated Ser- vices Architecture for Internet[J].Internet Draft,1997,(11), Work in Progress. [2]Z Wang,et al.QoS Routing for Supporting Res ource Reservation [J].IEEE JSAC,1996,(9)1 [3]N Shacham.Mutipoint Communication by Hierarchically Encod- ed Data[C].Proc.IEEE INFOCOM c92,1992:2107-2114. [4]M R Carey,https://www.sodocs.net/doc/0811537055.html,puters and Intractability[M]. Ne w York:Freeman,1979. [5]P Winter.Steiner Problem in Net works:A Survey[J].Net- Works,1987:129-167. [6]F K Hwang.Steiner Tree Proble ms[J].Networks,1992:55-89. [7]F Bauer.Muticas t R outi ng in Poin-t to-Point Networks Under Cons traints[D].Ph.D dissertation,UC Santa Cruz,1996. [8]H F Salana.Muticas t R outi ng for Rea-l ti me Communication on High Speed Networks[D].Ph.D di ssertation,NC State Uni v. Relei gh,1996. [9]Integrated Services Worki ng Group[R].1998. [10]H Takahashi,A M ats uyama.An Approximate Solution for the Steiner Problem in Graphs[J].Math Japonica,1980:573-577. [11]F Bauer,A Vorma.Distri buted Al gori thm for Multicast Path Set- up in Data Networks[J].Comp.Eng.Dept.,UC Santa Cruz, UCSC-CRL-95-10,1995,(8). [12]Q Zhu,M Parsa,J Garcia-Luna-Aceves.A Sourse-based Algo- rithm for Delay-c onstrained M inimal Cost M ulticas ti ng[C]. https://www.sodocs.net/doc/0811537055.html,COM c95,1995.377-384. [13]V P Kopella,J C Pasavale,G C Polyzo.Multicas t Routing for Multi medi a Communication[J].IEEE/ACM https://www.sodocs.net/doc/0811537055.html,.,1993: 286-292. [14]T H Cormen,C E Leisers on,R L Ri ves t.Introduction to Algo- rithm[M].MIT Press,1997. [15]B K Haberman,G Rous kas.Cos t,Delay,and Delay Variati on Conscious Multicast R outi ng[R].Tec.rep.TR-97-03,NC State Uni v.,1997. [16]V P Kopell a,J C Pasavale,G C Polyzo.Two Dis tributed Algo- rithms for Multicas ti ng Mul ti media Information[C].Proc.ICC-CN c93,1993:343-349. [17]X Jia.A Dis tributed Algori thms of Del ay-Bounded Multicas t Routing for Multimedia Applications in Wide Area Net works [J].IEEE/ACM https://www.sodocs.net/doc/0811537055.html,,.1998,(12):828-837. [18]F Bauer,A Vorma.Degree-Cons trained M ulticas ti ng in Poin-t to- Point Networks[C].Proc.IEEE INFOCOM c95,1995. [19]R N Raus kas,I Baldine.Mul ticast Routi ng with End-to-End Delay and Delay Variati on Constraints[J].IEEE.JSAC.1997, (4):346-356. [20]M Imase,B Wa xman.Dynamic Steiner Tree Proble m[J]. SIAMJ,Disc.M ath.1991,(8):369-384. [21]F Bauer,A Vorma.ARISE:A Rearrangeable Inexpens ive Edge- Based On-Li ne Steiner Algorithm[J].IEEE,JSAC,1997,(4): 382-397. [22]P Narvaez,K Siu,H Tzeng.New Dynamic STP Algorithm Based on a Bal-l and-Stri ng Models[C].IEEE INFOCOM c99,Ne w York,1999. [23]R Sriram,G Mani maran,C Murthy.A Rearrangeable Algori thm for the Constructi on of Delay-Constrained Dyna mic Multicas t Trees[C].New York:IEEE INFOCO M c99,19991 [24]B Wang,J C Hou.Multicas t Routi ng and Its QoS Extension: Problem,Algorithm,and Protoc ols[J].IEEE Network,2000, (2):22-36. [25]刘玉明.IP多播技术[J].电信科学,1999,(2):18-20. [26]崔烽,吴新余,等.Internet中的多播路由选择算法[J]. 南京邮电学院学报,19(2)1 作者简介: 徐征,男,硕士研究生,主要研究方向为计算机网络与新一代计算机技术;黄传河,男,副教授,主要研究方向为计算机网络与分布并行技术;吴小兵,男,硕士研究生,主要研究方向为计算机网络与分布并行技术。 12.7 IPX路由选择协议 IPX中使用的两个主要的路由选择协议是RIP（IPX的距离向量协议，IPX’s distance vector protocol）和NLSP（IPX的链路状态协议，IPX’s link state protocol）。维持IPX路径的所有路由选择协议也会维持SAP列表，这样它才能跟踪服务。 IPX RIP与TCP/IP有许多相似之处。它们都可以使用水平分割或毒性逆转来帮助防止路由选择循环和加快会聚时间。它们也都有15个跳数限制，并且都定期发送完整的路由选择表更新，使用60秒钟而不是30秒钟的更新间隔，而且IPX RIP会发送SAP信息以及路由选择信息。IPX RIP公布的额外SAP信息是更新间隔较长的原因所在。 注意：不要混淆TCP/IP RIP和IPX RIP。虽然它们有许多相似之处，但是它们属于两个不同的协议。 直到最近几年，Novell才开始将NLSP作为默认的路由选择协议，而且默认情况下，在支持RIP兼容性的NetWare服务器上也支持NLSP。NLSP是一个链路状态协议，它允许在大型网络上构建分层的区域，就像OSPF和BGP那样。你也可以使用EIGRP来分配IPX路由选择信息，但是因为EIGRP是Cisco专用的，所以你只有在Cisco路由器之间、支持NetWare 服务器的网段之间、或者支持RIP或NLSP的NetWare资源之间使用它才能正常工作。NLSP路由器交换诸如连接状态、路由成本、吞吐量、最大数据包（MTU大小）以及通过RIP（外部网络号）了解的网络之类的信息。这种信息在LSP（链路状态数据包）中携带。通过与它的对等路由器交换信息，每一个NLSP路由器都可以构建和维护整个互联网络的逻辑图。因为NLSP是链路状态路由选择协议，所以只有当路由或服务中出现变化时，或者每隔两个小时，哪一个首先出现变化时，NLSP才传输路由选择信息。 5.3.4 附录E 最短路径算法——Dijkstra算法 在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman-Ford算法和Dijkstra算法。这两种算法的思路不同，但得出的结果是相同的。我们在下面只介绍Dijkstra算法，它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。 下面以图E-1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便起见，设源结点为结点1。然后一步一步地寻找，每次找一个结点到源结点的最短路径，直到把所有 点1, j)为结点i (1) 初始化 令N表示网络结点的集合。先令N = {1}。对所有不在N中的结点v，写出 不直接相连与结点若结点直接相连 与结点若结点 1 1 ),1()(v v v l v D ? ? ?∞= 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子，可以使D (v ) = 99。 (2) 寻找一个不在N 中的结点w ，其D (w )值为最小。把w 加入到N 中。然后对所有不在N 中的结点v ，用[D (v ), D (w ) + l (w , v )]中的较小的值去更新原有的D (v )值，即： D (v )←Min[D (v ), D (w ) + l (w , v )] (E-1) (3) 重复步骤(2)，直到所有的网络结点都在N 中为止。 表E-1是对图E-1的网络进行求解的详细步骤。可以看出，上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D (w ) 值。当第5次执行步骤(2)并得出了结果后，所有网络结点都已包含在N 之中，整个算法即告结束。 表E-1 计算图E-1的网络的最短路径 路由算法及分类 路由算法及分类： 1、非自适应算法，静态路由算法 不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。 特点：简单，开销少；灵活性差。 2、自适应算法，动态路由算法 可根据网络流量和拓扑结构的变化更新路由表。 特点：开销大；健壮性和灵活性好。 3、最优化原则（optimality principle） 如果路由器J 在路由器I 到K 的最优路由上，那么从J 到K 的最优路由会落在同一路由上。 4、汇集树（sink tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； 路由算法的目的是找出并使用汇集树。 几种典型的路由选择算法： 1、最短路径路由算法（Shortest Path Routing） 1）基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。 2）测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数 3）Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； 2、洪泛及选择洪泛算法 1）洪泛算法（Flooding） 属于静态路由算法 a)基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。 IP多播技术的分析与研究 【摘要】随着高性能网络技术的不断发展, IP 多播路由技术已经成为网络领域的一个重要研究课题, 对未来网络发展有重要意义。本文论述了IP 多播路由技术的研究情况及IP 多播路由技术的发展现状, 介绍了几种重要的IP 多播路由协议并简单进行了对比, 同时介绍了几种IP 多播路由算法及其分类, 最后给出了IP 多播路由技术的应用领域和待研究的问题。 【关键词】计算机网络; IP 多播路由; 多播树; 1.IP多播技术简介 多播技术是TCP/IP传输方式的一种。TCP/IP有三种传输方式：单播、多播、广播。多播是由源点发送单个分组，然后一路上有各个路由器复制这个分组。所有分组副本的目的地址都是一样的。在多个单播中，从源点开始就发出多个分组。例如，如果有四个终点，那么源点就发送四个分组，且每个分组具有不同的单播终点。例如，向一组人放一份电子邮件报文时，就是使用了多个单播。电子邮件软件把报文复制多分，给每一份写入不同的目标地址。 传统的IP通信是在一个源IP主机和一个目标IP主机之间（单播）或者一个源IP主机和网络中所有的IP主机之间（广播）进行的。要将信息发送给网络中的多个而非所有的IP主机，采用传统的IP通信技术只有两种方法可以选择: 采用广播方式或者由源IP 主机分别向网络中的多个目标IP主机单播发送IP包。广播方式会将信息发送给不需要的IP主机而浪费带宽，而且可能的路由回环会引起广播风暴。单播方式由于IP包的重复发送会浪费大量的带宽，同时也增加了服务器的负载。可见，传统的IP通信技术不能有效地解决单点发送多点接收的问题。而IP多播却很好地解决了这个问题。 实现多播技术要解决的关键问题是多播路由问题。在IP 层上实现多播需要网络设备( 路由器) 的支持, 这样才能在主机上运行多播应用程序, 这大大限制了多播技术的发展。同时, 为了测试和研究新的多播协议和多播应用程序, 有必要找到一种方法, 使得无需将整个因特网上的设备都转换成支持多播的设备, 就可以运行多播应用程序, 这导致了多播主干实验网“MBone ”的诞生。实际上对Internet 的多播技术的研究始于80 年代后期S.Deering 的工作, 由他提出了IP 多播模型, 随着MBone 的出现, 且IETF 利用它在1992 年 3 月成功举行了第一次网络会议以来, 多播已经引起了广泛的重视, 对它的各方面进行了深入的研究。比如多播路由协议和算法, 基于QoS 的多播路由, 基于分布式的多播路由, 移动Internet中的IP 多播等等。 2 IP 多播路由协议 实现IP 多播路由一般方式是在多播组成员之间构造一棵多播树。多播树是根为源节点, 且覆盖所有多播成员的一棵生成树, 不同的IP 多播路由协议使用不同的技术来构造这些多播生成树, 一旦这个树构造完成, 所有的多播流量都将通过它来传播。 多播路由协议用来生成和维护多播生成树, 使用多播路由协议, 路由器可建立起从多播源节点到所有目的节点的多播路由表, 从而实现在子网间转发多播数据包。根据多播生成树实现方式, 可将域内多播路由协议分为两类: 基于源的多播生成树路由协议如DVMRP 、MO 2SPF 、PIM-DM 和基于核的 关于路由协议试题以及参考答案 1、解决路由环问题的方法有(ABD) A. 水平分割 B. 路由保持法 C. 路由器重启 D. 定义路由权的最大值 2、下面哪一项正确描述了路由协议(C) A. 允许数据包在主机间传送的一种协议 B. 定义数据包中域的格式和用法的一种方式 C. 通过执行一个算法来完成路由选择的一种协议 D. 指定MAC地址和IP地址捆绑的方式和时间的一种协议 3、以下哪些内容是路由信息中所不包含的(A) A. 源地址 B. 下一跳 C. 目标网络 D. 路由权值 4、以下说法那些是正确的(BD) A. 路由优先级与路由权值的计算是一致的 B. 路由权的计算可能基于路径某单一特性计算，也可能基于路径多种属性 C. 如果几个动态路由协议都找到了到达同一目标网络的最佳路由，这几条路由都会被加入路由表中 D. 动态路由协议是按照路由的路由权值来判断路由的好坏，并且每一种路由协议的判断方法都是不一样的 5、IGP的作用范围是(C) A. 区域内 B. 局域网内 C. 自治系统内 D. 自然子网范围内 6、距离矢量协议包括(AB) A. RIP B. BGP C. IS-IS D. OSPF 7、关于矢量距离算法以下那些说法是错误的(A) A. 矢量距离算法不会产生路由环路问题 B. 矢量距离算法是靠传递路由信息来实现的 C. 路由信息的矢量表示法是(目标网络，metric) D. 使用矢量距离算法的协议只从自己的邻居获得信息 8、如果一个内部网络对外的出口只有一个，那么最好配置(A) A. 缺省路由 B. 主机路由 C. 动态路由 9、BGP是在(D)之间传播路由的协议 本技术提供了一种动态路由最短路径选择方法，通过路由动态更新以实时更新路由信息，然后通过执行Dijkstra算法计算pc到各个路由器的最短路径；路由动态更新实现的步骤包括：发现邻居，设置链路成本，构造链路状态包，分发链路状态包，计算新路由关系。本技术用于解决主控电脑及终端(路由器)之间动态组网及数据交互的问题。 权利要求书 1.一种动态路由最短路径选择方法，其特征在于，通过路由动态更新以实时更新路由信息，然后通过执行Dijkstra算法计算pc到各个路由器的最短路径；路由动态更新实现的步骤包括：发现邻居，设置链路成本，构造链路状态包，分发链路状态包，计算新路由关系。 2.根据权利要求1所述的一种动态路由最短路径选择方法，其特征在于，路由器发现邻居是利用自检报文及hello和helloback报文的交互来发现邻居，在每一条点到点线路上发送一个特殊的HELLO数据包，然后线路的另外一个路由器做出一个helloback的回复，这样路由器收集完所有该路由器所有的helloback报文后，就就能够确认该路由器所有的邻居信息，pc收到相邻路由器的hello报文后，返回pc端发送的helloback报文，同时构建路由器节点，并将该路由器信息加入到路由器数据表中，在此过程中，将pc也作为一个路由器来对待。 3.根据权利要求1所述的一种动态路由最短路径选择方法，其特征在于，链路状态包中包括的信息有路由器与相邻路由器相连的端口号，相邻路由器序列号，相邻路由器与路由器相连的端口号。 4.根据权利要求2所述的一种动态路由最短路径选择方法，其特征在于，路由器会进行记录，如果是个新的数据包，那么就转发它，如果是个重复的数据包，就丢弃，当pc收到来自某一路由器的链路报文后，将该路由器的信息加入到路由器数据表中，如果当前路由器数据表中已经存在相同的路由器信息，则将原来的路由器信息删除，更新为最新的路由器信息。 5.根据权利要求4所述的一种动态路由最短路径选择方法，其特征在于，通过执行Dijkstra算法寻找出pc到各个路由器的最短路径 的具体步骤为：对路由器数据表中的各个路由器进行重新标号，pc标号为0，其余路由器标号为从1开始自然数编号，对路由器 路由选择协议和配置的详细步骤 静态路由的配置： router(config)ip route +非直连网段+子网掩码+下一跳地址 router(config)#exit 动态路由按照是否在一个自治系统内使用又可以分为内部网关协议(igp)和外部网关协议(bgp)常见的内部网关协议有rip、ospf等，外部网关协议有bgp、bgp-4，这里主要说下内部网关路由选择协议：rip(routing information protocol)是一种距离矢量选择路由协议，由于它的简单、可靠、便于配置，所以使用比较广泛，但是由于它最多支持的跳数为15，16为不可达所以只适合小型的网络，而且它每隔30s一次的路由信息广播也是造成网络广播风暴的重要原因之一。 rip的配置： router(config)#router rip router(config-router)#network network-number network_number为路由器的直连网段 由于rip的局限性，一种新的路由选择协议应运而生：igrp，igrp(interoor gateway routing protocol)igrp由于突破了15跳的限制，成为了当时大型cisco网络的首选协议 rip与igrp 的工作机制，均是从所有配置接口上定期发出路由更新。但是， rip是以跳数为度量单位;igrp以多种因素来建立路由最佳路径;带宽(bandwidth)，延迟(delay)，可靠性(reliability)，负载(load)等因素但是它的缺点就是不支持vlsm和不连续的子网。 igrp的配置： router(config)#router igrp 100(100为自治系统号) router(config-router)#network network-number router(config-router)#exit 注意： 1)编号的有效范围为1-65535，编号用确定一组区域编号相同的路由器和接口; 2)不同的编号的路由器不参与路由更新。 eigrp(enhanced interoor gateway routing protocol)eigrp 是最典型的平衡混合路由选择协议，它融合了距离矢量和链路状态两种路由选择协议的优点，使用散射更新算法，可实现很高的路由性能。eigrp特点是采用不定期更新，即只在路由器改变计量标准或拓扑出现变化时发送部分更新路由。支持可变长子网掩码vslm，具有相同的自治系统号的eigrp和igrp之间，可无缝交换路由信息。eigrp的配置和igrp的大致相同： router(config)#router eigrp(100为自治系统号) router(config-router)#network network-number router(config-router)#exit ospf： ospf是一种链路状态路由选择协议所谓链路状态是指路由器接口的状态，如up，down，ip及网络类型等链路状态信息通过链 数据通信与计算机网络大作业 Dijkstra 最 短 路 径 算 法 【摘要】 摘要:最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用, 对其进行优化很有必要。本文分析了传统 的最短路径算法(即Dijkstra 算法)的优化途径及现有的优化算法, 然后在Dijkstra 算法的基础上, 采用配对堆结构来实现路 径计算过程中优先级队列的一系列操作, 经理论分析与实验测试结果对比, 可以大大提高该算法的效率和性能。 【关键词】 最短路径; Dijkstra 算法; 【正文】 随着计算机网络技术和地理信息科学的发展, 最短路径问题无论是在交通运输, 还是在城市规划、物流管理、网络通讯等方面, 它都发挥了重要的作用。因此, 对它的研究不但具有重要的理论价值, 而且具有重要的应用价值。研究最短路径问题通常将它们抽象为图论意义下的网络问题, 问题的核心就变成了网络图中的最短路径问题。此时的最短路径不单指“纯距离”意义上的最短路径, 它可以是“经济距离”意义上的最短路径, “时间”意义上的最短路径, “网络”意义上的最短路径。关于最短路径问题, 目前所公认的最好的求解方法, 是由F.W.Dijkstra 提出的标号法, 即Dijkstra 算法。 1 Dijkstra 算法 Dijkstra 算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点(源点)到其余各节点的最短路径时, 经典Dijkstra 算法将网络中的节点分成三部分: 未标记节点、临时标记节点和最短路径节点(永久标记节点)。算法开始时源点初始化为最短路径节点, 其余为未标记节点, 算法执行过程中, 每次从最短路径节点往相邻节点扩展, 非最短路径节点的相邻节点修改为临时标记节点, 判断权值是否更新后, 在所有临时标记节点中提取权值最小的节点, 修改为最短路径节点后作为下一次的扩展源, 再重复前面的步骤, 当所有节点都做过扩展源后算法结束。具体算法描述如下: 设在一非负权简单连通无向图G= WDM网络中多约束动态多播路由算法研究 摘要：如何在WDM光网络中实现对多播业务的支持成了近年来光网络研究的热点之一。文章设计了两种基于通用分层辅助图波长路由算法：最小代价控制算法MCCA-G和最小时延控制算法MDCA-G。两种算法在辅助图中建立多播树时都引入了MPH算法思想和最小波长层代价率进入思想，而后者对业务时延的控制要好于前者。另外，由于稀疏的分光节点和波长转换节点的放置对于网络的性能影响很大，为此文章还提出了一个SNPA算法，即稀疏节点位置放置算法。在仿真中，MCCA-G和MDCA-G的稀疏分光节点的位置采用了SNPA 的计算结果，仿真结果表明，与传统的RRS算法相比，MDCA-G在阻塞率方面可降低15.34%，而MCCA-G与Member-only和VS_based 相比，分别在阻塞率上降低了32%和15.6%。可以看出，在同等的网络状态和环境下，MCCA-G和MDCA-G的表现要优于传统算法。 关键词：WDM网络多播路由稀疏配置波长变换 Abstract：How to support multicasting in WDM networks has a research topic in recent years.This paper design tow routing and wavelength assignment algorithms based on generic layer auxiliary graph model:MCCA-G minimum cost controls algorithms-graph and MDCA-G minimum delay dontrol algriths-graph.The two algorithms both adhibit MPH and the thought of entering the wavelength layer with minimum cost rates,And the latter should be better than the former to the control the 计算机网络原理最短路径路由 在路由选择方法中，我们经常采用的算法是：求给定网络中任意两个节点间的最短路径。即求任意两个节点间的最小时延或最小费用的路径。这里已知的是整个网络拓扑和各链路的长度。 求最短路径的方法有许多种，下面我们以图6-4所示的网络为例来讨论一种由Dijkstra 提出的求最短路径的算法，即寻找从源节点到网络中其他各节点的最短路径。在本例中，设节点A为源节点，然后逐步寻找其最短路径，每次找一个节点到源节点的最短路径，直到把所有的点都找到为止。 图6-4 求最短路径算法的网络举例 令D(V)为源节点(节点A)到节点v的距离,它就是沿着某一通路的所有链路的长度之和。再令l(i,l)为节点i至节点j之间的距离。整个算法有以下部分： （1）初始化。令N表示网络节点的集合。先令N={A}，对所有不在N中的节点v，写出： λ(A,ν)若节点ν与节点A直接相连； D(ν)= { ∞若节点ν与节点A不直接相连； 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞，可以使D （v）=99。 （2）寻找一个不在N中的节点w，其D（w）值为最小。把w加入到N中，然后对所有不在N中的节点，用D（v）与[D（w）+λ(w,ν)]中较小的值去更新原有的D（v）值，即：D（v）←min[D（v）,D（w）+λ(w,ν)] （3）重得步骤（2），直到所有的网络节点都在N中为止。 6-2所示 是对图 6-4的网 络进行求 解的详细 步骤。可 以看出，上述的步骤（2）共执行了5次，表中带圆圈的数字是在每一次执行步骤（2）时所寻找的具有最小值的D（w）值。当第5次执行步骤（2）并得出了结果后，所有网络节点都已包含在N之中，整个算法即告结束。 Dijkstra最短路径算法 摘要 OSPF 是由 IETF 的 IGP 工作组为 IP 网开发的一种能适应大型网络需要的典型的链路状态路由协议，它可以迅速地检测 AS 内的拓扑变化，经过一个 比较短的收敛期后，重新计算出无环路由。在 OSPF 中采用的是 Dijkstra 算法来实现最短路径的计算，做到了选路的高效、可靠。不同的算法在时间上的开销是不一样的，可能会有很大的差别，而对于一个大型的网络来讲，选路的效率往往就是网络的生命，算法的重要性不言而喻。 关键词 OSPF 最短路径Dijkstra 第1章绪论 最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛． 1.1 国内外最短路径算法的发展及其概况 最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究．但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra（迪杰斯特拉）的荷兰计算机科学家，他不仅给出了求解 的基本思想，还给出了算法．他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题．后来这个算法被誉为一代经典，被称作Dijkstra 算法．后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下．确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法[1]．而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度随机变化的最短路径问题，Hall、LiPing Fu、L.R.Rilett、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表．其中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”． 1.2 传统Dijkstra算法仍然存在的一些问题 原始Dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义N 的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将N 占用大量的计算机内存． 原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型．网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法．根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率． 第2章 Dijkstra经典算法 2.1 引言 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径．主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止．Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多， 第八章 第八章 路由协议原理 Network Protocol Destinati on Network Connected RIP IGRP 10.120.2.0172.16.1.0172.17.3.0Exit Interface E0S0S1被动路由协议: IP ，IP IPX X ，APPLETalk 主动路由协议: RIP ，E IGR IGRP P ，OSPF 172.17.3.0 172.16.1.0 10.120.2.0E0S0 在TCP/IP 协议栈中，Rout Routing ing ing Protocol Protocol 工作在网络层，而Rout Routed ed ed Protocol Protocol 工作在传输层或者应用层 ，他们之间的关系为：Routing Protocol 负责学习最佳路径，而Routed Protocol 根据最佳路径将来 自上层的信息封装在IP 包里传输 路由协议和被路由协议的区别 路由器是如何进行选路？ ?路由器转发数据包的关键是路由表。 ?每个路由器中都保存着一张路由表，表中每条路由项都指明数据包到某子网或某主机应通过路由器的哪个物理端口发送，然后就可到达该路径的下一个路由器，或者不再经过别的路由器而传送到直接相连的网络中的目的主机。 要实现路由要实现路由，路由器，路由器，路由器必须知道必须知道必须知道::目的地址所有可能的路由路径最佳路由路径管理路由信息172.16.1.010.120.2.0 管理距离 Administrative Distances ?管理距离主要用于不同路由协议之间的可信度。 ?可信度的范围是：0 到255 之间,它表示一条路由选择信息源的可信性值.该值越小,可信度越高.0 为最信任,255 为最不信任. 《通信网理论基础》 实 验 指 导 书 适用专业—信息工程 实验三：端间最短路径算法 一、实验目的 通信网络中为传输信息，需要求网络中端点之间的最短距离和路由。此时网络可以用图,)G V E ＝（来表示，每条边(,)i j 的权,i j w 可为该边的距离、成本或容 量等物理意义。端间最短径问题主要分为两种情况：寻找指定端至其它端的最短距离和路由，可以使用Dijkstra 算法解决；寻找任意两端之间的最短距离和路由, 使用Floyd 算法解决。 Dijkstra 算法为标号置定法，通过依次置定指定端与当前端的最短距离和回溯路由来实现；Floyd 算法为标号修正法，通过初始化图的距离矩阵和路由矩阵、并在转接过程中不断刷新，直至算法结束才能求出任意两点间的最短距离矩阵和前向或反向路由矩阵。 本次实验要求利用MATLAB 分别实现Dijkstra 算法和Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 2.1 Dijkstra 算法可描述如下： D 算法的每个端点i v 的标号为(,)i l λ，其中i λ表示1v 到i v 的距离，而l 为端点是1v 到i v 最短路径的最后一个端点。 图G V E =（，）的每一边上有一个权()0w e ≥。 D0：初始(0)1{}X v =，记10λ=，设1v 的标号为1(,1)λ。 D1：对任一边()()()(,)()(,)k k k i l i l X v X v X ∈Φ∈?反圈，计算i il w λ+的值。在()()k X Φ中选一边，设为00()()00(,)(,)k k i l i l v X v X ∈?。使000()(,)()()min k i i l i il i l X w w λλ∈Φ+= +，并令 0000l i i l w λλ=+，并且0l v 的标号为00,l i λ（）。 D2：当出现下面情况之一时停止。 1）()k j v X ∈；2）()k j v X ?但()(k X Φ=Φ） 2.2 Floyd 算法可描述如下： 给定图G 及其边(,)i j 的权,(1,1)i j w i n j n ≤≤≤≤ F0：初始化距离矩阵(0)W 和路由矩阵(0)R 。其中： (0) 0ij ij ij ij w e E w e E i j ∈??=∞???=? 若 若 若 (0)(0)w 0, ij ij j r ?≠∞=?? 若 其它 F1：已求得(-1)k W 和(-1)k R ，依据下面的迭代求()k W 和()k R ()(1)(1)(-1),,,,min(,)k k k k i j i j i k k j w w w w --=+ (1)()(1),,,(),(1)()(1),,,k k k i k i j i j k i j k k k i j i j i j r w w r r w w ----?，终止。 三、实验内容 用MATLAB 仿真工具实现D 算法和F 算法：给定图G 及其边(,)i j 的权 ,(1,1) i j w i n j n ≤≤≤≤，可用D 算法和F 算法分别求出其各个端点之间的最小距离以及路由。 个人资料整理仅限学习使用 动态路由优化中的最短路径并行计算方法研究进展 杨忠明秦勇 茂名学院广东茂名 525000 摘要:本文总结了国内外一些最短路径并行计算算法目前的主要研究结果，并从QoS路由选择目标中的一些方法特点对动态路由优化算法进行改进，使用最短路径并行计算是解决动态路由优化的计算量问题的方法之一，并提出了最短路径并行计算算法优化路由策略的实验方法。 关键词: 最短路径；并行计算；动态路由优化；QoS路由；Pareto子集； 中图分类号：TP391 文献标识码：A 1 引言 网络中流量的特点是影响网络路由设计的主要因素，对于路由算法设计则必须基于流量，但对于大多数AS(Autonomous System>，基于目前的算法，网络中大部分时间内的流量是相当稳定的，但是通常会存在一些时段，网络中的流量会突然变化，对于现有的路由算法基于性能和复杂度考虑没有进行重新计算或调整。已经许多研究者对AS中高突发流量究，通过这些高突发流量的调查报告发现，导致网络高突发流量的原因有诸如病毒的爆发、ISP 路由变动、拒绝服务攻击等原因，另外基于多媒体的UDP流量日益增多，使得突发流量往往影响到网络中的关键业务[1-4]。如果路由算法没有考虑到网络中的突发流量的负载均衡，通常会导致网络链路和路由不必要的过载，延迟加大，丢包率增加，网络的吞吐量降低，甚至威胁路由器安全。传统的路由算法通常是基于数据传输对网络情况的预测[5]。而基于算法性能和复杂度不考虑网络突发流量的实际，算法通常是根据采集到网络流量的部分度量样本，基于采样对网络性能优化，而这些采样并不能反映网络的真实情况[6]。Zhang C.等提及算法考虑多个具有代表性的流量矩阵，然后找到一组优化路由使得代表性的流量矩阵的最差代价达到最小，但是这里的最差代价并非全局仅限于网络流量的采样[7, 8]。Kandula S.等提及算法对实际网络上流量进行管理，以响应瞬时流量的需求做出优化[9]。这些动态适应算法的优点在于如果它们能够迅速收敛，则不需要过多的采样或者做出预测。近年来在网络流量领域值得关注的是域内的流量工程与域间的路由和流量间交互作用，研究发现一个AS域内的流量会导致AS出口处流量的变化这种流量变化会触发相邻AS路由的变化，导致网络的不稳定[10,11]。COPE(Common-case Optimization with Penalty Envelope>算法被提出来解决这种情况[6]。要应对网络中突发流量，有效的办法就是开发出简单快速的路由算法并进行路由优化。 最短路径算法介绍 据Drew 所知最短路经算法现在重要的应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*（D Star）算法。 最短路经计算分静态最短路计算和动态最短路计算。 静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*（A St ar）算法。 动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。如在游戏中敌人或障碍物不断移动的情况下。典型的有D*算法。 这是Drew程序实现的10000个节点的随机路网三条互不相交最短路 真实路网计算K条路径示例：节点5696到节点3006，三条最快速路，可以看出路径基本上走环线或主干路。黑线为第一条，兰线为第二条，红线为第三条。约束条件系数为1.2。共享部分路段。显示计算部分完全由Drew自己开发的程序完成。 参见K条路算法测试程序 Dijkstra算法求最短路径： Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE 表方式，Drew为了和下面要介绍的A* 算法和D* 算法表述一致，这里均采用OPEN,CLOS E表的方式。 路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。 路由器使用路由算法来找到到达目的地的最佳路由。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。 收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。 各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。 链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。 也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。 metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。 路由信息协议实验报告【实验目的】 1．掌握路由协议的分类，理解静态路由和动态路由 2．掌握动态路由协议RIP的报文格式，工作原理及工作过程3．掌握RIP计时器的作用 4．理解RIP的稳定性 【网络结构】 主机A：172.16.0.2 主机B：172.16.0.1 192.168.0.2 主机C：192.168.0.3 主机D：192.168.0.4 主机E：192.168.0.1 172.16.1.1 主机F：172.16.1.2 【实验内容】 练习1： 各主机打开协议分析器，进入相应的网络结构并验证网络拓扑的正确性，如果通过拓扑验证，关闭协议分析器继续进行实验，如果没有通过拓扑验证，请检查网络连接。 本练习将主机A、B、C、D、E、F作为一组进行实验。 1.主机A、B、C、D、E、F在命令行下运行“route print”命令，察看路由表，并回答以下 问题： ● 路由表由哪几项组成？ 2. 从主机A依次ping 主机B（192.168.0.2）、主机C、主机E（192.168.0.1）、主机E （172.16.1.1），观察现象，记录结果。通过在命令行下运行route print命令，察看主机B 和主机E路由表，结合路由信息回答问题： ● 主机A的默认网关在本次练习中起到什么作用？ ● 记录并分析实验结果，简述为什么会产生这样的结果？ 3. 主机B和主机E启动静态路由。 （1）主机B与主机E在命令行下使用“staticroute_config”命令来启动静态路由。（2）在主机B上，通过在命令行下运行route add命令手工添加静态路由（“route add 172.16.1.0 mask 255.255.255.0 192.168.0.1 metric 2”）。 （3）在主机E上，也添加一条静态路由（“route add 172.16.0.0 mask 255.255.255.0 192.168.0.2 metric 2”）。 （4）从主机A依次ping主机B（192.168.0.2）、主机E（192.168.0.1）、主机E（172.16.1.1），观察现象，记录结果。 （5）通过在命令行下运行route print命令，察看主机B和主机E路由表，结合路由信息回答问题： ● 记录并分析实验结果，简述手工添加静态路由在此次通信中所起的作用。 Dijkstra(迪杰斯特拉算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S 中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。 例如，对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。 Dijkstra算法的迭代过程： 主题好好理解上图！ 以下是具体的实现(C/C++: 1. /*************************************** 2. * About: 有向图的Dijkstra算法实现 3. * Author: Tanky Woo 4. * Blog: https://www.sodocs.net/doc/0811537055.html, 5. ***************************************/ 6. 7. #include 8. using namespace std; 9. 10. const int maxnum = 100; 11. const int maxint = 999999; 12. 13. 14. void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum] 15. { 16. bool s[maxnum]; // 判断是否已存入该点到S集合中 17. for(int i=1; i<=n; ++i 18. { 19. dist[i] = c[v][i]; 20. s[i] = 0; // 初始都未用过该点 21. if(dist[i] == maxint 22. prev[i] = 0; 23. else 24. prev[i] = v; 25. } 26. dist[v] = 0; 27. s[v] = 1; 28. 29. // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中多播路由选择协议
Dijkstra最短路径算法
路由算法分类
IP多播路由选择协议的分析与研究
路由协议试题以及参考答案
动态路由最短路径选择方法与设计方案
路由选择协议和配置的详细步骤
dijkstra最短路径算法
WDM网络中多约束动态多播路由算法研究
计算机网络原理 最短路径路由
Dijkstra最短路径算法
路由协议原理
3-最短路径算法
动态路由优化中最短路径并行计算方法研究报告进展
最短路径算法介绍
路由算法分类比较
路由信息协议实验报告
最短路径算法―Dijkstra(迪杰斯特拉)算法分析与实现(