（计算机应用技术专业论文）分布式qos路由算法的研究.pdf

中南太学硕士学位论支 摘要 随着网络规模的迅速增长和网络技术的不断成熟、完善，现代网络中对 多媒体信息的应用越来越广泛，人们对网络服务的要求越来越高，这就对网 络服务质量( q o s ，q u a l i t yo fs e r v i c e ) 提出了更为严格的要求。这其中包 含对诸如网络延迟、延迟抖动、带宽、代价等综合因素的考虑。如何在满足 q o s 要求的情况下进行路由选择，并且有效地将q o s 路由选择与资源预留结 合在一起已经成为路由算法研究的一个重要方向。 在路由算法的研究中，国内外的学者提出很多具有创造性和实用价值的 q o s 路由算法，这些算法大体可分为：源路由算法和分布式路由算法两大 类，也有人在综合这两种算法的特点后提出局部范围内使用源路由算法，全 局范围内使用分稚式路出算法鹊新方法。尽管这些算法各有缺陷和局限性， 但它们的提出不仅给出了网络路由的优化解决方案，并且将路出算法的研究 不断向前推进，只要在具体的应用中根据网络的实际情况对各种算法的特点 台理地加以利用，就能取得最佳的路由结果。 本文首先对q o s 路由的原理和理论进行详细的阐述和证明，简单列举和 分析源路由和分布式路由算法的特点。然后对近几年国外研究人员提出的几 种分布式路由算法进行了重点说明和分析，在详细分析这些算法中的优点和 存在的问题的基础上，对原有的算法进行改进，提出新的更合理的算法，从 而在提高网络性能的同时也提高路由算法的效率。新算法是一种基于t i c k e t 的多路路由算法，其中利用分布式路由选择的优点，仅使用相邻节点的状态 信息，通过利用t i c k e t 有效减少分布式路由算法在选路过程中所引起的盲目 性，并利用多路选择提高链路建立的成功率。最后，通过使用公认的优秀网 络仿真软件o p n e t 对提出的新算法进行模拟实现，在对模拟结果认真分析之 后，证明新的算法能在保证网络通信量不增加的基础上提高链路建立的成功 率，改善网络性能，进一步得出该算法是合理并且高效的结论。 关键词：q o s ，多路路由算法。源路由，分布式路由 中南大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w n ht h er a p i dd e v e l o p m e n to ft h en e t w o r kt e c h n o l o g y m o f e 趾dm o r em u l t i m e d i a 印p l i c a t i o n ss u c ha sd i g i t a lv i d e oa f l da u d i oa r e a p p l i e do ni m e m e t ，i na d d i t i o n ，也eq u a l i t yo f s e r v i c ea r e 职e d e dm u c l lh i g l l e r t l l a nb e f o r e i no f d e rt o p r o v i d eh i g hq u a l i t yo fs e r v i c eo nt h en e t w o f kt o s a t i s f ya l lt h er e q u i r e m e n t s ，q o s ( q u a l 哆o f s e r v i c e ) h a sb e e np r o p o s e d i nr e c e n t y e a r s t h e r ea r es e v e r a lm e t r i c so fq o s ，s u c ha sb a n d w i d t h ，d e l a 弘d e l a yj i t i c r a n dc o s t a l lo fm e s em e t r i c sa r ev e r yi m p o n a l l te l e m e n i so nm u l t i m e d i a t e a p p l i c a t i o n s t h e r e f o f e ，h o wt oc h o o s e ap a t ht os a t i s f yt l eq o s r e q u i r e m e n t s a n dh o wt oc o m b i n eq o sr o u t i n g 、v i t hr e s o u r c er c s e r v a t i o nb e c o m ea 1 1 e s s e n t i a lp a r to f n c t w o r kr e s e a r c h e s r e s e 盯c h e r s 趾de x p e r t sp m p o s em a n yc r e a t i v ea n dp r a c t i c a b l eq o s r o u t i n ga l g o i i m m s ，w h i c hc a nb ed i v i d e di n t ot w od i r e c t i o n s ：s o u r c er o u t i n g a l g o r i m m sa n dd i s t r i b u t e dr o u t i n ga l g o r i t i 瑚s t h e r ea r ca l s os o m ea l g o r i t h r n t h a tu s es o u r c er o u t i n gi nl o c a la r e a ，a n du s ed i s t r i b u t e da l g o r i t l l mi ng l o b a l a f e a t 沁u g hh a v i n gs o m ed e f c c t s ，t l l e s ca l g o r i m m sc o n t r m u t ea l o tt qn e t w o r k r e s e a r c h e s ，a i l dw i i lb ev e r ye 蕊c i e n ti f t h e ya r eu s c dc o r r e c t l y i nm i sp a p e r w e f i r s t l ys h o wm e o r e m sa n dp m o f so fm et h e o r yo nq o s t h e ne x p a t i a t em ec h a r a c t e r i s t i c so fs o l l r c er o u t i n ga i l dd i s 耐b u t i 觅r o u t i n gi n g e n e r a l l a _ e rw ee n u m e r a t ea n da l i a l y z cs e v e r a ld i s t r i b u t e dq o sr o u 6 n gi n g r e a td e t a i l s a r e rf i n d i n gd e f e c t so ft l l e s ea j g o r i t l i m s ，w ep r o p o s ean e w l i c k e t - b a s e dm u m 。p a c hd i s 埘b u t c dq o sr o u t i n g a i g o r i t h m t o i m p r o v e t i l e p e r f o r m a n c e a r i de m c i e n c yo fa l g o r i m mi ns 啪ee x t e n d i nm en e w a l g o r i 伽n ， e v e r yn o d eo n l yn e e d t om a i n t a i nl o c a ls t a t ei n f o r m a t i o no fi t sa d j a c e n tn o d e s ， t i c k e ti su s e dt od e c r e a s et 1 1 ee x t c n s i o no fn o o d i n g ，w h i l em u l t i p a t l lc 8 i l 访c r e 船et h ep r o b a b i l i t yo f f i n d i n gt h ef e a s i b l ep a t h s a tl a s t ，、v cu s e0 p n e 玎a s t h es i m u i a t o rt or e a l i z et | l en e wa l g o r i m mi nv i r t u a ln e t w o r ke n v i m n m e n t s i m d i a l i o nf e s 山t si n d i c a t e 廿l a tn e w a 1 9 0 r i t h i nc a ni m p r o v em ep e r f b h n a n c eo f n e “v o r kw i t l l o u ti n c r e a s em eo v e d l c a d s o w ec a nd r a wac o n c l u s i o nm a tm i s n e w a l g o f i 妇n i sf e a s i b l ea n de 甩c i e n t i 【e yw o r d s ：q o s ，m u l t i 巾a ma l g o r i 恤1 ，s o i l r c er o u t i n g ，d i s t n i b u l e dr 0 u t i n g i l 中南大学硕i ：学位论文 第一章绪论 随着网络技术的不断发展，多媒体信息的广泛应用，用户对网络服务质 量不断提出更高的要求，因此如何在满足服务质量的同时高效的进行路由选 择成为路由算法研究的发展方向私重点所在。 本章包括q o s 路由问题研究的意义与现状、研究的内容以及论文的组织 等内容。 1 1q o s 路由简介 q o s 路由的目的是在网络中需要相互通信的两点间寻找到一条路径以满 足其在通信方面的某些特定要求，这包括在带宽、延迟、延迟辩动和路由代 价等方面的要求。在宽带综合业务数字网( b i s d n ，b r o a d b a n di n t e g r a t e d s e r v i c e sd i g i t a l t w o r k s ) 中，端到端服务质量的应用在学术和工业领域 都受到越来越多的重视，同时也得到了越来越广泛的应用。尤其在多媒体信 息的应用中对q o s 更是提出了多方砸的要求。 下面。通过图1 1 简单描述q o s 路由选择过程。图1 1 所示的是一个简 单的网络结构，由路由器、主机、客户机和连接各种网络设备的链路组成。 源节点( 客户机或服务器) 发起q o s 的请求，并发送给路由器，路由器根据 当前网络的状况判断网络是否能提供满足q o s 请求的资源，并通过一定的路 径计算进行路由选择。q o s 路由选择可以分为两大步骤：q o s 路由和资源预 留。其中q o s 路由和其它路由算法一样，路由器利用路由表内的网络状态信 息，确认当前网络是否能保证服务质量，并通过计算选择一条最优的路径， 然后将请求包转发到下一跳的路由器，依次转发直到目的节点。目的节点在 收到q o s 请求后，逆方向发送确认信息回源节点，并在沿途进行资源预留。 以前提出的算法是将q o s 路由同资源预留分开，即在q o s 路由完成后再进行 资源预留工作，这种方法有一个缺陷，即当确认信息返回源节点的途中有可 能因为网络状态的变化使原来能用的资源变为不可用。为克服这种方法的缺 陷，现在提出的q o s 路由算法大都将q o s 路由和资源预留结合在一起，即在 q o s 路由的同时将所需的网络资源保留下来。但这种方法也有缺点，在多路 路由( m u l t i p a t hr o u t i n g ) 算法中，因为选路过程中每个节点都要保留资 源，所以会出现同一个q o s 请求的资源被重复预留的情况，造成网络资源的 浪费，这种情况被成为o v e rr e s e r v a t i o n 问题”。 在近期的有关q o s 路由的研究主要分为两个方向：源路由和分布式路 出。在源路由中，每个节点( 如路由器，交换规等) 都保存一个网络全局状 态信息的映像，由源节点在这个映像的基础上对路由路径进行集中式的计 算。在分布式路由中，路径的计算是分布在网络中的各个节点上。在路径计 算过程中使用节点问互换的控制信息和每个节点上保存的状态信息来共同完 中南大学预十学位论文 成寻找路径的工作。近几年，在提出q o s 路由的思想之后，进行了很多关于 源路由和分布式路由的研究，也提出了大量的算法。 图1 1 路由选择过程示意图 源路由算法中每个路由器都要保存整个网络中的全局信息。这就要求网 络的每个节点( 路由器) 保存一张包含全局状态信息的路由表，因此路由表 很庞大，也要求路由器有较大的缓冲区空间以供路由选择计算时使用。因为 每个节点都掌握网络的全部信息，所以在路山选择过程中，源路山器通过一 定量的计算就能够找到最为优化的路径，使得路由选择的目的性较强。另 外，如果抛除路由计算的时间，源路由算法能在较短时间内找到一条最优的 路径，使用源路由的路由器还可以根据连接请求的需要和网络的具体情况选 择适用的路由算法。但是，源路由算法的编写和实现较为复杂，其时间复杂 度较大。由于所有的路由计算都放在源路由器上进行，就会增加传输延迟。 同时，路由表的定时更薪需要在全局范围内传输链路状态更新信息，就会增 加网络的通信量负载，造成网络拥塞，使得路由信息的更新量成为网络的瓶 颈。另外，信息传输的延迟使得路由器收到的更新信息可能已经过失。 分布式路由算法的特性恰与源路由网络相反。分布式路由算法与源路由 算法最大的不同在于分布式路由算法是将路出计算和路由选择分散在网络中 的各个路由器上进行，而源路由算法则是将路由算法集中在源路由器一端进 行。在一些分布武路由算法中，要求网络中的每个节点( 鼹由器) 只甓保存 其相邻节点的状态信息，因此路由器的路由表项很小，对路由器缓冲区空间 的要求也较小。更新信息仅在相邻节点间传输，所以路由器总能在第一时间 得到最新的状态信息，及时更新路由表项，增加了算法的准确性和可靠性。 也有一些分布式算法需要保存一定量的全局信息。分布式算法一般通过距离 2 中南大学硕七学位论文 矢量和链路状态两种方法进行路出信息的更新。分布式路由算法还在时间复 杂度方面有较好的表现，实现也较为简单。但是，由于每个节点掌握的网络 状态信息有限，而且路由计算分布在各个路由器中进行，各路由器所使用的 路由算法又不尽相同，这给路由选择带来一些不便，从而导致所选择的路径 并非最佳路径。为保证通路建立的成功率就只能通过泛洪( f l o o d i n g ) 或类 似的方法同时在多个方向上寻找到达目的端的可能路径。这就在无形中增加 了网络通信量负载，使得网络性能下降。目的端在收到的多个q o s 请求中选 择最优的路径建立通路。由于网络中存在的各种问题使目的端选择的路径有 可能仅是次最优而不是最优的路径。 从以上的分析中可以看到，无论是源路由q o s 算法还是分布式q o s 路由 算法都有其独特的优势和自身难以克服的缺陷。在网络的实际应用中具体使 用哪种算法要根据网络的实际情况和对网络性能的要求，以及对服务质量的 要求丽定。 q o s 路由算法是在当前网络资源需求目益增加的情况下提出的，它的应 用为网络中多媒体的应用和多媒体信息的传输提供了服务质量的保证。也为 网络应用的进一步发展提供了技术上的支持。 1 2q o s 路由问题研究的意义与现状 q o s 路由算法为当前和未来的网络多媒体应用提供一个高效、安全、合 理的锵决方案。由于网络应用和技术的快速发展，短短几年时间，q o s 路由 经历了从无到有，再到广泛应用的过程。目前，研究、开发和应用q o s 路由 算法已经得到越来越多的重视，并成为网络技术研究和网络应用中非常重要 的组成部分。因此，关于网络中q o s 路由算法的研究、开发和应用不仅在理 论研究中具有较高的价值，也在实践中具有较高的实用价值。 近些年来，为支持诸如数字图像和音频等网络多媒体的应用，各种网络 新结构和新技术应运而生。q o s 路由算法就是其中之一，它在保证满足服务 质量要求的情况下为多媒体信息的传输提供了高效的路由选择方案。一般来 讲，多媒体应用当中对服务质量都有很严格的要求，而且不同的应用会对服 务质量有不同的要求。1 。比如说，在网络上收看实时电影时，就对传输视频 信号的网络延迟时间有严格的限制，以保证接收端收到的电影画面的连续 性。而在传输普通的文本信息时更关注的可能是选路过程中的路由代价，即 在路由的过程中总是选择代价最小的链路建立连接。如果一个网络要保证服 务质量就必须进行资源预留和网络控制。 从最初提出q o s 到现在q o s 路由算法不断发展完善，几年时问里，在资 源预留、接入控制和包整流等方面已经进行了大量的研究和探讨，也相继提 出许多算法。目前，对q o s 路由算法的研究仍分为源路由算法和分布式路由 算法两个方向，各自都提出了不同的路由算法“1 1 。其中s h i g a n gc h e n 提出通 过预测网络延迟最在动态变化的网络中利用t i c k e t 来控制路由算法的扩散范 围”，y z h o n g 等也提出利用t i c k e t 的多路路由方法进行路由选择。因这 中南人学硕二i 。学位论文 两种分布式算法中都使用了全局信息作为路由选择的依据，所以并没有克服 源路由算法的缺点。j u ns o n g 提出的算法r j 用f l o o d i n g 算法进行路由”，虽 使用了一定的优化策略但仍无法解决算法扩散范围大的问题。而源路由算法 则是将路由选择集中在一台路由器上，路由器利用全局信息通过计算找到一 条能满足q o s 的最佳路径。 由于两种路由选择算法其各自的优缺点，使无论是源路由算法还是分布 式路由算法都在某些方面有优异的表现，而在另外的方面有难以克服的缺 陷。因此提出一种在保证服务质量的前提条件下，能够既使用局部信息又有 效减少算法扩散度，减少网络拥塞的路由算法成为未来q o s 路由算法发展的 必然趋势。 另外，将q o s 路由算法和资源预留结合在一起也是算法研究的一个方 向。传统的q o s 路出算法是将q o s 路由同资源预留分开进行，这样会因为网 络拓扑结构的变化引起资源预留失败。现在普遍使用将q o s 路由和资源预留 结合在一起的方法克服由于网络拓扑结构变化而引起的通路建立失败。但在 进行多路路由时也会引起o v e rr e s e r v a t i o n 的问题。因此，如何将q o s 路l 妇 和资源预留有效结合的同时避免o v e rr e s e r v a l i o n 问题成为路由算法研究的 另一个重要方向。 1 3 研究内容与本文所做的工作 分布式q o s 路由算法是q o s 路由算法中非常重要的一个研究方向。分布 式路由算法和源路由算法相比有很多优越性使分布式路由算法有着广阔的 发展空间。随着网络分布式计算的不断完善，分布式路由算法将得到更为广 泛的应用。目前国内外学者提出的分布式算法有很多。这些算法具有分布 式路由算法的共性是将路由选择的计算分布在网络中的相关路由器上进行， 每个路由器承担相同的计算量和责任，但他们之间在一些细节方面有一定的 区别。有的算法在路由计算过程中使用到了全局性的状态信息作为计算的变 量和选路的依据；有的则完全使用f 1 0 0 d i n g 方法进行路由选择，并使用某种 “剪切”技术来控制算法的扩散范围。这些算法充分利用了已有的源路由和 分布式路由算法的选路方法，取得了一定的成功，但仍没有解决源路由和分 布式路由的问题。因此，如何充分利用分布式路由算法的优点，同时又能有 效控制算法的扩散范围成为研究的重点。 文章的主要研究内容是在大量查阅国内外有关网络路由算法的文献后， 深入、详细的分析了各种算法的优缺点和特性，并在此基础上结合自己的新 观点提出新的算法最后通过网络仿真实验验证算法的合理性和有效性。在 课题的研究过程中，资料的收集、新算法的提出和最后的验证工作是关键的 三步。通过前期的资料查阅和整理，在前人已经提出的基予t i c k e t 的分布式 路由算法上进行改进，提出自己的一种基于l i c k e t 的分布式多路路由算法。 这种算法用于对带宽和延迟有要求的情况，通过将q o s 路由和资源预留结合 在一起减少网络开销，还避免了由于网络拓扑结构的变化引起的资源预留问 中南大学硕i ：学位论文 题。该算法既保留了分布式路由算法的优点，同时利用t i c k e t 控制算法的扩 散范围，而且还提出了合理丢弃和重传请求包的策略，有效减少网络通信量 负载，在算法的有限扩散范围内提高通路建立的成功率。理论上讲，这个算 法较传统的源路由算法和分布式算法相比都有较大的优越性。为验证算法的 有效性和实用性，最后使用o p n e t 7 o b 商用网络仿真软件模拟网络中的真实 情况，并对算法进行仿真实验，实验的分析结果证明，该算法是有效并且实 用的。 1 4 论文的组织 论文全文共5 章。在论述q o s 路由算法的研究时，首先通过分析其他算 法提出问题，针对具体问题在已有算法的基础上提出新的算法模型。通过与 其它算法模型的比较来验证新算法的有效性，并进行实验验证，最后给出结 论。 第一章为绪论，介绍了q o s 路由选择问题的研究背景和意义，并对当前 课题的研究现状和研究内容以及本文的主要工作进行了论述。 第二章首先简要介绍路由的基本概念，然后在基本原理的基础上详细系 统地阐述q o s 路由选择理论，根据网络进行q o s 路由时所使用不同性质的量 度( m e t r i c ) 分列出五个定理，并对每个定理都进行了详尽的分析和证明。 以此得出结论，在多种量度限制的情况下进行q o s 路由是n p 完全问题。 第三章在概述部分简单介绍分布式q o s 路出算法和源路由算法的一些特 性，分列出分布式算法和源路由算法各自的优缺点。并结合具体的几种分布 式q o s 路由算法详细地阐述和分析这几种分布式q o s 路由算法的特点。通过 分析各种算法的特性和各自的优缺点，并在综合几种分布式路由算法的优点 之后，提出一种新的分布式算法，在充分利用分布式算法优越性的同时通过 采取不同的方法和策略尽量克服分布式算法的缺陷。本章的最后部分简要介 绍了几种用于网络模拟的仿真软件，在比较这几种软件的功能和性能之后， 选择0 p n e t 作为验证算法的模拟工具。另外，还以o p n e t 为模拟环境说明网 络模型建立的过程和算法实现的方法。 第四章主要介绍一种新的分布式q o s 路由算法，该算法是在分析以往几 种分布式和源路由算法的优缺点后提出的，它在充分利用分布式算法优点的 基础上进行了一定的改进，从而在定程度上克服了分布式路由算法进行路 由选择的盲目性，在不增加网络通信量负载的同时有效提高了通路建立的效 率和成功率。算法提出后，使用世界公认的商用网络仿真软件0 p n e t 进行算 法的模拟实现，实验结果证明新提出这种算法是有效的。 第五章是总结。对本文所做的工作进行了总结。并阐述了进一步的研究 工作。 中南大学硕士学位论文 第二章q o s 路由协议的分析 本帝王要对q o s 炼 “l 办议进行详细分析，从而在了解q o si ! 山算法具体 运作细节的基础上，为路【j | 选择问题研究提供依据。茸先介绍在多限制条件 下进行路径选择的复杂度，以及q o s 路由中量度的选择：然后介绍三种适合 于源路由和分布式路由的路径计算算法。 2 1q o s 路由基本原理和理论 在具体介绍q o s 路由之前，首先筒要介绍路出的基本概念和组成，以及 当前使用的各种路由算法。 2 1 1 什么是路由 路由是把信息从源端穿过礴络传递到目的端的行为，在传递的路径中至 少遇到一个中间( i n t e r m e d i a t en o d e ) 节点。路由通常与桥接来对比，在表 面看柬，它们具有相同的功能，究成相同的任务。但从木质来讲，路由和桥 接有一定的区别，其主要区别在于桥接发生在o s i 参考协议的第二层( 链接 层) ，而路由发生在第三层( 网络层) 。这一区别便二者在传递信息的过程 中使用不同的信息，从而以不同的方式来完成其任务。 路由的话题早已在计算机界出现，但直到八十年代中期才获得商业成 功，这一时间延迟的主要原因是七十年代的网络很简单，后来大型的网络才 较为瞽遍。在传统的数据网络中，路由选择主要内容是在源端和目的端建立 一条通路。路由协议通常只对网络的特性进行某一方面的量度，如源端和目 的端之间的跳数、延迟等。随着网络的不断发展，多媒体信息在网络中的应 用越加广泛，对网络所能提供的服务质量也提出了更商的要求。因此满足服 务质量的路由协议也随之出现，并迅速发展起来。为了支持更多的q o s 请 求路由协议需要通过更为复杂的模型使用多个量度( m u l t i p l em e t r i c s ) 来表示网络特性，如在带宽、延迟和丢失率三个方面表现网络特性。因此， q o s 路由最基本的问题就是如何找到一条能满足多个限制的路径。出予以往 路由协议的复杂度已经接近可能的极限，所以q o s 路由协议设计中一个很重 要的方面就是如何使由于支持q o s 而引入的复杂度不削弱路由协议的可测量 性“”。 对网络进行研究首先要对网络建模，在这个网络仿真模型的基础上研究 网络的性能和特性。一个具体的网络可以用两个集合的模型表示，这两个集 合分别是n 和a ，即g = ( n ，a ) 。其中g 代表网络，n 代表网络中节点的集合， a 代表连接网络中各节点的链路集合。集合n 中的每个节点都保存一张路由 表，路由表的构造基于网络的拓扑结构，表内保存的是网络中其它节点的实 体。路由衷中保存的状态信息为路由器进行路由选择计算提供了所需的信 壹点兰堡! ：堂堡堡墨一 息。为保证路由表内的信息能够真实地反映网络的实时状态，表内的各鬏项 要进行定时更新。每当网络拓扑结构或其它状态发生变化时，就要发送路由 表更新信息，路由器在收到该信息后要对路由表项立即进行更新，以保证表 中的实体与实际网络相符。 2 1 2 路由的组成 路由包含两个基本的动作：确定最佳路径和通过网络传输信息。在路由 的过程中，后者也称为( 数据) 交换。交换相对来说比较简单，而选择路径 很复杂。 l 、路径选择 量度是路由算法用以确定到达目的地的最佳路径的汁量标准，如路径长 度，这将在本章的后面具体介绍。为了帮助选路，路由算法初始化并维护包 含路径信息的路由表，路径信息根据使用的路由算法不同而不同。 路由算法根据许多信息来填充路由表。目的下一跳地址对告知路由器到 达该目的最佳方式是把分组发送给代表“下一跳”的路由器，当路由器收到 个分组，它就检查其目标地址，尝试将此地址与其“下一跳”枢联系。下 表为一个目的下一跳路由表的例子。 表2 1 目的下一眺对应表决定数据的最佳路径 t o 嘲c h 糖m 憎k ： s 舯d i o ： 2 7n o d b a 5 rn o d e b 1 7 a e c 2 n o d e 5 2n o 抽a b n o d e 8 2 6 n o 噎j 路由表还可以包括其它信息。路由表比较量度以确定最佳路径，这些量 度根据所用的路由算法而不同。路由器彼此通信，通过交换路由信息维护其 路由表，路由更新信息通常包含全部或部分路由表，通过分析来自其它路由 器的路由更新信息，该路由器可以建立网络拓扑细图。路由器闯发送的另一 个信息例子是链接状态广播信息，它通知其它路由器发送者的链接状态，链 接信息用于建立完整的拓扑图使路由器可以确定最佳路径。 2 、交换 中南大学硕七学位论文 交换算法相对而言较简单。对大多数路由协议而言是相同的，多数情况 下，某主机决定向另一个主机发送数据，通过某些方法获得路由器的地址 后，源主机发送指向该路由器的物理( m a c ) 地址的数据包，其协议地址是指 向目的主机的。 路由器查看了数据包的目的协议地址后，确定是否知道如何转发该包， 如果路由器不知道如何转发，通常就将之丢弃。如果路由器知道如何转发， 就把目的物理地址变成下一跳的物理地址并向之发送。下一跳可能就是最终 的目的主机，如果不是，通常为另一个路由器，它将执行同样的步骤。当分 组在网络中流动时，它的物理地址在改变，但其协议地址始终不变，如图 2 1 所示。 图2 1 数据包转发示意图 上面描述了源系统与目的系统间的交换，i s o 定义了用于描述此过程的 分层的术语。在该术语中，没有转发分组能力的网络设备称为端系统( e s e n ds y s t e m ) ，有此能力的称为中介系统( i s i n t e r m e d i a t es v s t e m ) 。i s 又进一步分成可在路由域内通信的域内i s ( n t r a d o m a i ni s ) 和既可在路出 域内又可在域间通信的域间i s ( i n t e r d o m a i nt s ) 。路由域通常被认为是统 一管理下的一部分网络，遵守特定的一组管理规则，也称为自治系统 ( a u t o n o m o u s8 y s t e m ) 。在某些协议中，路由域可以分为路由区闻，但是域 内路由协议仍可用于在区间内和区间之间交换数据。 中南夫学硕十学位论文 2 1 3 路由算法 路由算法可以根据多个特性来加以区分。首先，算法设计者的特定目标 影响了该路由协议的操作：其次，存在着多神路出算法，每种算法对网络和 路由器资源的影响都不同；最后，路由算法使用多种量度，影响到最佳路径 的计算。本章的后半部分和第三章将埘路由算法的特性进行详细的分析。 1 、设计目标 路由算法通常具有下列设计目标的一个或多个： 优化 简单、低耗 健壮、稳定 快速聚合 灵活性 优化指路由算法选择最佳路径的能力，根据量度的值和权值来计算。例 如有一种路由算法可能使用跳数和延迟，但可能延迟的权值要大些。当然， 路由泓泌必须严格定义计算量度的算法。 路由算法也可以设计得尽量简单。换句话说，路由协议必须高效地提供 其功能，尽量减少软件和应用的丌销。当实现路出算法的软件必须运行在物 理资源有限的计算机上时高效尤其重要。 路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能 正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的 连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过 了时间考验，证实在各种网络条件下都很稳定的算法。 此外，路由算法必须能快速聚合，聚合是所有路由器对最佳路径达成一 致的过程。当菜网络事件使路径断掉或不可用时，路由器通过网络分发路由 更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很 慢的路由算法可能会产生路由环或网路中断。 在图2 2 的路由环中，某分组在时间t l 到达路由器l ，路由器1 已经更 新并知道到达目的的最佳路径是以路由器2 为下一跳，于是就把该分组转发 给路由器2 。但是路由器2 还没有更新，它认为最佳的下一跳是路由器l ，于 是把该分组发回给路由器l ，结果分组在两个路由器问来回传递直到路由器2 收到路由更新信息或分组超过了生存期。 图2 2 路由环示意图 9 中南太学硕j ：学位论文 路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网络环 境。例如，假定某网段断掉了，当知道问题后，很多路出算法对通常使用该 网段的路径将迅速选择次佳的路径。路由算法可以设计得可适应网络带宽、 路出器队列大小和网络延迟。 2 、路由的量度 路出表中含有出交换软件用以选择最佳路径的信息。但是路由表是怎样 建立的呢? 它们包含信息的本质是什么? 路由算法怎样根据这些信息决定哪 条路径更好呢? 路由算法使用了许多不同的量度以确定最佳路径。复杂的路由算法可以 基于多个量度选择路由，并把它们结合成一个复合的：蟹度。常用的量度如 下： 路径长度 可靠性 延迟 带宽 负载 路由代价 路径长度是最常用韵路由量度。一些路由协议允许网管给每个网络链接 人工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。其 它路出协议定义了跳数，即分组在从源到目的的路途中必须经过的网络产 品，如路由器的个数。 可靠性，在路由算法中指网络链接的可依赖性( 通常以位误率描述) ， 有些网络链接可能比其它的失效更多，网路失效后，些网络链接可能比其 它的更易或更快修复。任何可靠性因素都可以在给可靠率赋值时计算在内， 通常是由网管给网络链接赋以量度值。 路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延 迟，包括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间 网络链接的拥塞程度以及物理距离。因为延迟是多个重要变量的混合体，它 是个比较常用且有效的量度。 带宽指链接可用的流通容量。在其它所有条件都相等时，l o m b p s 的以太 网链接比6 4 k b p s 的专线更可取。虽然带宽是链接可获得的最大吞吐量，但是 通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好。例如，如 果一条快速链路很忙，分组到达目的所花时间可能要更长。 负载指网络资源，如路由器的繁忙程度。负载可以用很多方面计算，包 括c p u 使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资 源的。 通信代价是另一种重要的量度，尤其是有一些公司可能关系运作费用甚 于性能。即使线路延迟可能较氏，他们也宁愿通过自己的线路发送数据而不 采用昂贵的公用线路。 1 0 中南大学倾i 。学位论文 3 、网络协议 可被路由的协议( r o u t e dp r 0 l o c 0 1 ) 由路山协议( r o u l i n gp r o t o c 0 1 ) 传输，前者亦称为网络协议。这些网络协议执行在源与目的设备的用户应用 间通信所需的各种功能，不同的协议中这些功能可能差异很大。网络协议发 生在o s i 参考模型的上四层：传输层、会话层、表示层和应用层。 术语r o u t e dp r o t o c o l ( 可被路由的协淡) 和i o u gp r o t o c 0 1 ( 路出 协议) 经常被混淆。r o u t e dp r o l o c 。1 在网络中被路由，例如i p 、d e c n el 、 a p p l e t a l k 、n o v e l ln e t w a r e 、0 sl 、b a n y a nv l n e s 和x e r o xn e t w o r k s y s l e m ( x n s ) 。而路由协议是实现路由算法的协议，简单地说，它给网络协议 傲导向。路由协议如：i g r p 、e i ( m p 、o s f f 、巳g 1 1 、b ( 1 p 、1 s i s 及r i p 等。我 们将陆续介绍上述的各种协议。 2 2 路由协议复杂度分析和量度的选择 新的路由枷议的提出，无论是源路由还是分砟式路由要遵循一定的量 度，下面将对这些量度详细的介绍和分析。这节，首先介绍在多限制条件 下进行选择路径问题上取得的一些成果，然后在分析的基础上讨论量度的选 择【”。 2 2 1 标准的选取( s e 】e c t i o nc r i t e r i o n ) 在路由过程中路由量度就代表了网络，路由量度本身的含义不仅仅是路 径计算的复杂度，还表示刚络能够支持的0 0 s 请求的范f 同。这里有一些需要 考虑的情况； 1 ) 无论选取什么量度，必须要有有效的算法进行路径计算，从而保证是路 由协议能够度量象i n l e r n e t 鄂样的大型鼹绍。q o s 路由算法中路径计算的复 杂度应该和现有的路由算法的计算复杂度相当。而且，所有的算法最好在集 中式和分布式的环境中都能够适用。 2 ) 量度必须能够反映网络的基本特征。量度中包古的信息必须能够满足最 基本的q o s 请求。所有的q o s 请求都要通过网络量度映射为对某条路径的限 制，因此，在一定程度上量度就决定了网络所能提供的q o s 种类。比如说， 如某路由代价和带宽是网络量度，那所有的q o s 请求就必须映射到路由代价 和带宽上。 3 ) 量度之间应该是两两正交的，这样在量度之间就不会有冗余信息存在。 冗余信息会使各量度相交，使得无法对各量度无法进行独立的评估。 2 2 2 单一的混合型量废( s i i l g l em i x e dm e t r i c ) 单一量度的路径计算算法已纷广为人知，井在网络t p 得到了广泛的应 用，如针对延迟、跳数规则的算法。这就产生了一个问题：单一的规则是否 能满足用户的q o s 请求。 一种可能的办法是定义一个函数井从多个参数中产生个单一的量度。 这种方法的思想是将4 i 同的信息混合成一个量度并且在这个量度的基础上进 中南太学颂i 学位论文 行路由选择。比如说，一个混合的量度m 可以由带宽b 、延迟d 和丢失率l 利用 一个函数产生，该函数为f ( p ) = b ( p ) d ( p ) 虬( p ) 。就带宽、延迟和丢失 率而言，使函数值较大的路径是较好的选择。 然而，由于单一的混合型量度提供的信息不足以判断用户所需的q o s 请求 是否能被满足，所以最多只能用来作为一个指标。另一个问题与混合参数有 关，这些混合参数利用不同的合成规则合成在一起。比如说，假设一条路径 分为a b 和b c 两段。如果度量函数f ( p ) 代表延迟，则合成规则就是： f ( a b + b c )= f ( a b ) + f ( b c ) 。 如果度量函数f ( p ) 代表带宽，则合成规则就是： f ( a b c ) = m i n f ( a b ) ，f ( b c ) 。 但是，当f ( p ) = b ( p ) d ( p ) 乩( p ) 时，以上的所有等式就都不成立了。事实 上，其实没有一种简单的合成娥则。 虽然混合的度量只能作为路径选择的一个指标，但这种方法是一个有益 的启发。 2 z 3 多项量度 为解决单一的混合量度所面临的问题，提出了多量度的概念，多项量度 作为网络的模型较单一的量度更为准确。然而，问题在于在满足多限制条件 下寻找路径非常困难。在多项式时间内( p 0 1 y n o m i a 卜一t i m e ) 根本找不到一 种有效的算法进行路由选择。现在已经证明使算法同时满足多个量度是n p 难 问题。 由于在q o s 路由中对网络资源的要求多变，并且是根据具体应用而定， 就使得q o s 路由的问题更为复杂。路径计算的复杂度主要由多种量度的合并 规则丽定。以下介绍三个最基本的合并规则： 定义：令d ( i ，j ) 是链路( i ，j ) 的度量。对于任何路径p = ( i ，j ，k ，l ，m ) ，如果d 满足下面的条件： d ( p ) = d ( i ，j ) + d ( j k ) + d ( 1 ，m ) ，我们说量度d 是加性的； 如果d 满足下面的条件： d ( p ) = d ( i ，j ) d ( j ，k ) d ( 1 ，m ) ，我们说量度d 是乘性的； 如果d 满足下面的条件： d ( p ) = m i n d ( i ，j ) ，d ( j ，k ) ，d ( 1 ，m ) ，我们说度量d 是凸的。 现在我们来看看一些被当做路由量度的变量：延迟、延迟抖动、代价、 丢失率和带宽。很明显，延迟、延迟抖动和代价遵从加性的合并规则，丽带 宽则符合凸性的合并规则。而丢失率的合并规则比较复杂，可以表示为： d ( p ) = 1 一( ( 1 一d ( i ，j ) ) ( 1 一d ( j ，k ) ) ( 1 一d ( 1 m ) ) ) 丢失率量度可以转换为另一个等价的量度( 即传输成功率) ，传输成功率是 符合乘性合并规则的。 下面将就加性和乘性量度描述三种通用的n p 完全问题的定理，这些定理 是进行量度选择的基础。 1 2 中南丈学硬1 。学位论文 定理1 ：给定一个网络g = ( n ，a ) ，n 个加性量度的d ，( a ) ，也( a ) ，文( a ) ， 其中a a ，定义两个网络中的节点i ，m 和n 个正整数d 。，d ：，d 。，( n 2 ，d i ( a ) 0 ，d o ，i = 1 ，2 ，n ) ，判断是否有一条简单路径能满足限制d ，( p ) 阢 ( i = l ，2 ，n ) 是n p 完全问题( 即n 加性量度问题，na d d i t i v em e r i c s p r o b l e m ) 。 图2 3 节点问两条链路的分配 证明：使用归纳法汪明。首先证明2 加性量度问题( 2a d d i t i v e m e t r i c sp r o b l e m ) 为n p 完全问题。即2 加性量度问题n p 。因为分割问题 是n p 完全问题，因此要证明的是分割问题o c 2 加性量度问题，从而证明2 加 性度量问题是忡完全的。 举一个分割问题的例子，假设一个由数字a 。a 。，砜组成的集合，构成 了一个有n + 1 个节点、2 n 条链路的网络节点i 到节点i + 1 之间有两条链 路连接( 如图2 1 所示) 。令s = a 。m = 2 n s 。令d 。( i ，i + 1 ) 为从节点i 到节 点i + 1 的量度，其值分别为m 和m - a 。，再令d z ( i ，i + 1 ) 的值