（通信与信息系统专业论文）基于多约束条件的qos路由算法研究.pdf

摘要 近几年的研究表明路由算法对实现网络服务质量( q 砌i 移o f s e 州c e ，q o s ) 起着至关重要的作用，q o s 路由算法已经成为网络研究的核心问题之一。由于 基于多约束条件建立的网络模型可以更准确地反映实际的q o s 路由选择问题， 对于这一类路由算法的研究有着十分重要的意义。其中，如何解决d c l c ( d e l a y c o n s t m i n e dl e a s t c o s t ) 问题是多约束条件路由算法的一个重要研究方 向。现有的解决d c l c 问题的路由算法都有着各自的优点，而如何解决算法的 可扩展性却是这些算法面临的共同难题。 本文主要针对在层次网络中解决d c l c 问题的q o s 路由算法进行了研究。 拓扑聚合( t 0 p o l o g ya g g r e g a t i o n ，t a ) 技术常用来对海量的网络状态信息进 行抽象压缩，应用压缩后的信息进行路由计算是q o s 路由算法解决可扩展性问 题的重要途径。因此，t a 算法压缩信息的精确度对q o s 路由算法的准确性和 可行性起着至关重要的作用，本文提出了一种新的t a 算法，并通过仿真验证 了算法的可行性和有效性。在此基础上，本文针对基于二维时间尺度马尔科夫 决策过程的q o s 路由算法，进行了大量仿真实验，证明该算法能够有效地解决 层次网络中的d c l c 问题，其性能优于现有的其他d c l c 路由算法。 关键词：服务质量、时延约束最小开销、路由算法、拓扑聚合 a b s t r a c t c l i 玎e n t l y ，l o t so f 、v o r k sh a v es h o 姗t h a tt 1 1 em u t i n ga 1 9 0 r i 廿1 n l sp l a y 勰 i m p o r t 锄t r o l ei na c h i e v i n gt h en e t w o r kq u a l i 哆o f 鸵n ，i c e ( q o s ) q o sr o u t i n g a l g o r i t h r ni so n eo ft h ek e yi s s u e si nn e t 、o r kr e s e a r c h e s a st h em u l t i 瑚r 啦f a i n t b a s e dn e t w o r km o d e ic a na c c u r a t e l yr e n e c tt h ea c 叫q o sr o u t i n gp r o b l e m s ，n l e r e s e a r c ho nr o u t i n ga l g o r i t h i n si so fag r e a ts i g n 谕c a l l c e i i la l l 也ei s s u e so f m u l t i - c o n s t m i n tr o u t i n ga l g o r i t h m s ，h o wt 0s o l v e 廿1 ed c l c ( d e l a y o 嗷r a i n e d l e 邪t c o s t ) p r o b l e mi s 锄i m p o r t 锄td i r e c t i o no f r e c e n tn e m o r kr e s e a r c h e s a nn l e e x i s t i n gr o u t i n ga l g o r i t h n l sh a v et h e i ro w na d v a n t a g e so ns o i v i n gd c l cp r o b l e m ， h o w e v e r h o wt os 0 l v et 1 1 es c a l a b i l i t ) ，o fr o u t i n ga l g o r i t h n l si saw e l i - k n o w np r o b l e m t h eq o sr o u t i n ga 1 9 0 r i t h m sf o rs o l v i n gt l l ed c l cp r o b l e mi nm e r a r c k c a l n e m o r k si sm a i n i yd i s c u s s e di n “st h e s i s t o p o l o g ) ra g g r e g a t i o n ( 1 i a ) t e c t l i l i q u ei s o r e nu s e dt oc o m p r e s st h ev 筋t 锄o u n t so fn e 似r o r k 蚴ei n f l o n n a t i o n i ti s 强 i m p o r t a n t 、a yt 0s o l v et h es c a l a b i l i t ) ，p r o b l e mo fq o sr o u t i n ga 1 9 0 t h m s 、访t ht h e 印p i i c a t i o no f t h es 眦吼撕z e di n f o m l a t i o nt oc o m p u t et h er o u t i n gp a t h s t h e r e f o r e ， t l ea c c u r a c yo ft l l et aa 1 9 0 一t h m st oa b s t r a c tt h ei n f l 0 肌a t i o np l a y s 觚i m p o r t 锄tr o l e t 0s o i v et h ea c c u r a c y 锄df e a s i b i l i t ) ，p r o b l e m so fq o s r o u t i n ga 1 9 0 r i t _ h m s an e wt a a l g o r i t h mi sp r e s e n t e di nt l l i st l l e s i s ，锄di th 弱b e e nv e r i f j e dt 0b ef e a l s i b l e 锄d e f r e c t i v eb yl o t so fs i m u l a t i o ne x p e r i m e n t s o nt ab 硒i s ，t l l r 0 u g he x t e n s i v e s i m u l a t i o ne x p e r i m e n t s ，t h em ot i m e - s c a l em a r k o vd e c i s i o np r o c e s sb a s e dq o s m u t i n ga 1 9 0 r i t l l mh 雒b e e np r 0 v e dt 0b ee f r e c t i v ei ns 0 l v i n gt 1 1 ed c l cp r o b l e mi i i l l i e m r c l l i c a ln 咖o r k s f u n h e r m o r e ，t h j sn e wq o sr o u t i n ga l g o r i t l l mi sa l s 0 觚 o u t p e 墒册i n gw a yi ns o l v i n gt h ed c l cp r o b i e mc o m p a r e dt 0o t h e re x i s t i n gq o s r o u t i n ga l g o r i t h m s k e y w o r d ：q o sd e l a y c o n s t r a i n e d l e a s t - c o s t r o u t i n ga l g o r i t h m t o p o l o 斟a 踞r e g a t i o n 第一索绪论 第一章绪论 1 1 引言 近年来i n t e m e t 正以惊人的速度在全球范围内发展，它已成为全球信息交流、 信息贮备的主要途径。随着计算机网络的发展和深入，计算机的性能增强，目前 基于存储转发机制的i n t e n l e t ( i p v 4 标准) 只为用户提供了“尽力而为 ( b e s t e 仃0 r t ) 的服务，而不能保证数据包传输的实时性、完整性以及到达的顺序性，并且不能 保证服务的质量，所以主要应用在文件传送和电子邮件服务。随着i n t e m e t 的飞速 发展，人们对于在1 1 1 t e m e t 上传输分布式多媒体应用的需求越来越大，一般说来， 用户对不同的分布式多媒体应用有着不同的服务质量要求。丢失率、带宽、端到 端时延、时延抖动等对于应用业务是至关重要的；文件传输业务要求分组的丢失 率尽可能低，而传输时延不是关键；实时多媒体业务则注重时延和时延抖动。这 就要求网络能区别对待各种业务，并对其提供所需的服务质量【l 】。 在传统的“尽力而为”( b e s t e 肋i t ) 转发机制中，网络层不区分业务，尽管i p 分组头包含指明优先级及服务类型的字段，但在路由器选择路由和处理分组时往 往被忽略，根本不予以处理，而将网络资源公平地提供给各类业务，在分组丢失、 时延等方面公平地对待各类业务。这种尽力发送的机制使网络层无法保证传输的 参数，这种体系结构是无连接、与状态无关的，它既不能支持资源预留，也不能 预测传输参数，甚至还可能产生多媒体实时业务不希望的乱序等。由此可以看出， 传统的“尽力而为”的服务已无法满足用户的要求，所以一种新的网络体系一面向服 务质量的网络体系结构应运而生。 网络服务质量( q u a l 时o fs e i c e ，q o s ) 是网络用户之间关于信息传输与共 享的质的约定，例如，传输时延允许时间、最小传输画面失真度以及声像同步等。 这就关系到如何在t c m p 体系结构中支持有多种q o s 要求的业务，我们当然可以 研究开发新的网络协议，如i p v 6 ，r s v p ( 资源预留协议) 、r t p ( 实时传送协议) ： 然而，最根本的解决方法还是改造路由器，使其具有处理q o s 请求的功能。这是 因为路由直接关系到网络性能，而q o s 路由是解决q o s 问题的一项关键技术。 2 基于多约束条件的q o s 路由算法研究 1 2 1 q o s 路由的研究概况 1 2 研究背景 目前对支持q o s 的研究侧重于调度、拥塞控制和资源预留几个方向，而多年 的研究表明网络路由算法对实现网络保证质量的服务起到了非常关键的作用，对 q o s 路由的研究已经成为q o s 研究领域中的一个非常重要的研究方向。 路由是在宏观层次上对网络资源进行管理的手段，它是交换机或者路由器中 不可缺少的基本配置之一，路由技术也是因特网中最复杂并且是要求最严格的内 容之一。路由有两方面的基本内容：收集网络状态信息并不断更新信息和根据己 有信息来为新的连接请求选择一条合适的路由。一个路由算法的好坏很大程度上 取决于信息收集的好坏，比如信息更新的频度、最终信息的准确度等，这些问题 和实际协议的实现方法关联程度更大。 路由选择问题一般可分为两大类：单播路由选择和组播路由选择。这两类路 由选择问题密切相关，组播路由选择可看作是单播路由选择在多种情况下的推广。 q o s r ( q o sr o u t i n g ) 是指根据网络上可利用的资源和流( f l o w ) 的q o s 需求 来决定流的路由机制并以此来保证网络和业务q o s 的优化路由。这种路由是以资 源预留( r s v p ) 为前提，依据网络的资源状态决定是否接纳该业务的连接请求， 若接纳，则为该连接在可以保证端到端时延要求的路径上的各个节点预留带宽， 实现对业务的接入控制。在尽量减少资源消耗的基础上，合理分配网络的流量负 荷，减少拥塞概率，同时有利于系统在建立此连接之后，能接入更多的业务。一 般有两种方案：一种是负载平衡( l 0 a d b a l 锄c i n g ) ，即将负载均匀地分布在各个 链路上。另一种是l o a d p a c h n g 的方法，即将带宽需求窄的呼口l l 合并到某些链路 上，使其它链路剩下足够的带宽以接入带宽需求大的连接，以来保证网络对带宽 连接和窄带连接接入的公平性。 1 2 2 q o s 路由算法及研究中的问题 在实施q o s 的过程中，要求路由器能够在通信端点间找到一条可以满足q o s 要求的传输路径。q o s 路由算法必须同时满足三个要求：一是为每个接受的q o s 业务流提供服务质量保证，二是使网络全局资源达到最佳利用，第三是对性能影 响尽可能小。前者要求在多约束条件下计算出可行路径，而后者则要求在多条可 行路径中进一步优化。优化的方式通常是首先设计目标开销( c o s t ) 函数，然后求 解函数值最优的可行路径，而多约束条件下求解( 优化的) 可行路径属于n p 完备 问题。 第一章绪论 目前研究成果表明，在一定区域内部通过合理地配置基于链路状态的q o s r 协议，用以支持q o s 所引入的开销是完全可以接受的，然而q o s r 领域在以下几 方面还有待进一步研究。 1 并不是所有的路由器都支持r s v p 协议 如果用户会话之间存在着不支持r s v p 的路由器，那么对于那些支持r s v p 协议的路由器，它能确保用户需要的q o s ，而对于不支持r s v p 协议的路由器来 讲，就只能依靠它们提供的服务来尽量保证q o s ，这时就不能确保网络中的各个 部分都能给用户会话提供所需的q o s 。 2 l o a d b a l 勰c i n g 和l o a d p a c 垴n g 方法的局限性 l o a d b a l 卸c i n g 方法可能会导致链路带宽碎片( 触g m e n t a t i o n ) 过多，造成宽 带连接的阻塞。而在l o a d p a c b n g 方法中并未给出关于如何对应用流量进行划分、 如何计算满足所划区间的带宽请求的可行路径以及如何将窄带业务合并到某些链 路上等等这些问题具体的算法。事实上，两种连接接入的公平性是难以实现的， 这也会造成某些链路的阻塞，从而导致整个系统不可用，降低网络效益。 3 可扩展性 通过网络状态聚合能够以对数级压缩信息量，相应的分层路由可以通过限制 每层内节点的数量并使用源路由方式，从而很好地解决可扩展性问题。但这同时 又引入了新的问题：如何聚合状态信息、如何基于聚合状态设计良好的启发式算 法。目前所设计的状态信息聚合方法往往会丢失大量的可用信息，会严重的影响 q o s r 算法的性能。同时，所设计的启发式算法也是基于全局状态源路由策略的。 此外，由于很多q o s r 问题的精确求解复杂度问题都是n p 难问题，因此需要设计 快速而有效的启发式算法。 4 信息的陈旧性 状态信息的陈旧性是实际网络中难以避免的，并且会影响q o s r 算法的性能 和有效性。然而对这种陈旧性的分析往往会涉及到复杂的随机数学模型，而相关 的讨论也往往是基于模拟试验数据，缺少定量的理论分析。此外，通常的算法只 是停留在理论设计和分析上，缺乏对信息陈旧情况下算法实际性能的考虑。因此， 为了解决以上问题我们可以考虑基于概率模型求解，寻找以最大概率满足q o s 约 束的可行路径，从而有效地减少由于建立连接失败对网络造成的额外负担。 5 多路路由与重路由 将网络所提供的多条从源到目的地的路径并行使用的方式，是多路复用的路 由方式。目前就如何将在多条可能的路径上同时进行可行路径探测的方法与资源 预留相结合还尚无定论。然而，其主要问题是多条路径之间如何同步，以及如何 避免分组的时延抖动、乱序等问题。由于网络资源和可行路径分配的不合理，因 而在某些情况下需要重路由。进行重路由能够在网络资源不足时有效地重新分配 基于多约束条件的q o s 路由算法研究 网络资源，但由于存在链路状态的保存、同步和开销等问题，使重路由变得十分 困难。 6 网络模型 不同的网络拓扑结构和q o s 业务流，往往会对q o s r 算法的性能造成很大的 影响。因此，q o s r 需要在以下两个方面与网络模型结合起来：( 1 ) 评价q o s r 算法和协议的性能及有效性：( 2 ) 针对实际网络设计高效的q o s r 算法和协议。 但由于i n t e m e t 缺乏“典型的”网络拓扑结构和业务流，因此，如何建立适当的网 络模型来指导q o s r 的研究，将是进一步研究的主要方向。 7 与其他网络组件结合 今后的网络应该是q o s r 和“b e s t e 筋r t ”相结合的【1 引，路由的目标是最大化 地利用有限的资源，这包括尽可能多地接纳的q o s 连接请求，同时尽可能的最大 化发送业务并提高网络吞吐量和相应速度。但由于这两者是矛盾的，因此在将二 者结合的过程中可能会产生很多问题。然而，q o s r 算法必须与其他网络组件结合 才能提供q o s 保证，这种结合过程可以简化q o s r 算法和其他网络组件。 1 3 本文主要内容和结构 论文共分四章： 第一章讨论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 c o n s t m i n e d p a ：t i l ， m c p ) 问题以及多受限优化路径( m u l t i c o 璐t m i n e d o p t i m a lp 抽，m c o p ) 问题，为本文后面关于q o s 单播路由算法的研究工作奠定 了理论基础。 第三章介绍了拓扑聚合( t o p o l o g ya g g r e g a t i o n ，t a ) 技术的研究背景以及 其在q o s 路由算法里的实际意义，对现有的t a 算法做了简要介绍和分析，对于 现有的t a 算法的局限性提出了一种优化聚合信息的不精确性问题的新算法。并在 o p n e t 网络仿真软件环境下进行了仿真，对仿真结果进行了详细分析和说明。 第四章研究q o s 路由中时延受限条件下最小开销( d e l a y c o n s t r a i n e d l e a s t c o s tp a t hp r o b l e m ，d c l c ) 的路由问题，并对相关算法进行了简单的分析 和问题描述，针对文献【1 6 】中提出的一种层次网络中解决d c l c 问题的q o s 路由 算法进行分析和讨论。该算法根据实时的链路信息结合上一跳的路由信息对最优 第一章绪论 解进行迭代运算，最后的仿真结果表明该算法可靠性高，开销较低，收敛快，优 于其他算法。 最后总结，对论文的研究工作进行总结，同时提出进一步的研究内容和工作 展望。 6基于多约束条件的q o s 路由算法研究 第二章q o s 路由基础理论 7 第二章q o s 路由基础理论 2 1 概述 传统的路由策略是无连接的，只根据单一链路特性，并根据最短路径算法查 找路由路径，并且不使用替代路径( 非最短的次优路径) 进行路由选择。这种尽 力传输的路由机制使网络层无法保证相应的传输参数，然而在实际使用中网络的 丢包率、带宽、端到端时延、时延抖动等对于应用业务往往却是至关重要的。这 就要求网络能够区别对待各种业务，并对它们提供不同的服务质量。q o s 路由的 主要目标是为接入的业务选择能够满足其服务质量要求的传输路径，同时保证网 络资源的有效利用。 q o s 路由是面向连接的，它根据多种q o s 参数约束来选择路由，同时q o s 路 由还可以选择次优路径，即当最佳路由路径不能接纳新的路由请求时，次优路径 可作为替代路径进行路由以达到优化网络资源的目的。 由于尚未出现能够实际应用的q o s 路由算法，而且现存的q o s 路由算法在对 路由协议的支持方面考虑很少。因此研究高质量、高效率的q o s 路由算法，并将 算法和路由协议有机的结合起来，是当今国际上研究的热点和难点之一。 2 1 1q o s 路由的基本概念 q o s 路由和基于q o s 的传输调度是当前i n t s e 领域研究的热点问题1 1 4 l 。q o s 路由需要在信息传输之前在源节点和目的节点之间寻找符合q o s 需求的传输路 径，并通过r s v p 协议为其预留资源。在基于i n t s e 瓜s v p 模型的q o s 路由算法 的研究中，多约束条件下的q o s 路由算法、q o s 组播路由算法、q o s 路由实现及 性能评测等是难度较大的问题，需要更深入地研究1 1 3 】1 1 4 】。 q o s 路由是一个十分复杂的问题。这是因为：首先，像网络电话和分布式游 戏等分布式应用在时延、时延抖动、丢失率和带宽等方面有着不同的q o s 要求。 而多约束条件经常使得路由问题变得更加复杂。例如，寻找一条具有两个独立路 径限制的可行路径是n p 完备的。其次，将来的集成服务网很可能既要传输q o s 数据流又要传输“尽力而为 的数据，这就使得性能优化问题更加复杂化。最后， 由于瞬间的负载波动使得网络状态是动态变化的，不断增长的网络规模大小使得 在动态环境中收集最新的状态信息变得更加困难。如果使用过时的状态信息，将 会严重的影响到q o s 路由算法的性能。所以为了能够进行q o s 路由，路由器需要 得到实时的可用网络资源的信息。 8基于多约束条件的q o s 路由算法研究 2 1 2 网络模型以及q o s 参数 网络的拓扑结构和资源容量可以抽象为一个赋权图g y ，e ) ，其中 y = ( k ，坎圪) 是由代表路由器的所有交换节点组成的集合，e = ( e ，e e 。) 是 所有连接路由器的链路的集合。如果传输线路是对称的，则对应的边是无向的。 因为对称线路对两个方向上的数据都有同样的特性。对于大多数实际的网络而言， 其链路一般都是非对称的，因而其每一条链路对应于模型中就是两条有向的加权 边。每一条链路都有一个对应于相关q o s 参数的状态。而每一个节点也有相应的 状态，它可以单独表示出来，或者也可以把它折算到与节点相连的链路状态中去。 图2 1 网络路径连接不慈图 在2 1 图中，置、尺，、r 分别是网络中的三个节点，p 协。，尺，) 是指从节点r ， 到节点尺，的传输路径。对于任何一个服务质量参数，q 尸忸，足，j 是指从节点足，到 节点足，的传输路径的一个函数。依据函数的不同特性，将q o s 参数分为三种类型： 可加性参数，例如：延时，跳数等。 q p 伍，也) = q p c r ，尺，) + q p c r ，r ) 式( 2 1 ) 性参数，例如：链路带宽等。 q 尸( r ，也) = m a x 忉忸一，l 妒( r ，r ) ) 式( 2 2 ) 或者： q p 似，心) = m i n ( q 尸忸，天，l q 尸忸，吼) ) 式( 2 3 ) 可乘性参数，例如：链路可靠性，安全性等。 q 尸( 尺，足i ) = q 尸忸，尺，) q _ 尸( 尺，尺t ) 式( 2 - 4 ) 从上面的定义知道，在一条路径上的时延等于该路径上每一个节点和每一条 边的时延之和，把具有这种相加性质的条件称为可加性条件。在q o s 的限制条件 中，有很多这种可加性条件。 2 1 3 常用路由算法 一、单播路由( u m c 弱tr o u t i n g ) 根据应用范围，q o s 网络路由可以分为q o s 单播路由和q o s 组播路由。下面 给出q o s 单播路由的定义。 可行路径( 可行树) ：可行路径( 可行树) 是网络中从源节点到( 所有) 目 的节点的一条路径( 组播树) ，并且该路径( 树) 具有足够的尚未分配的资源， 能够满足特定的q o s 需求。 第二章q o s 路由基础理论 9 q o s 单播路由：对于网络( y ，) ，指定路由源节点5 y ，路由目的节点f y ， q o s 约束集c 以及优化目标，q o s 单播路由就是找出满足给定q o s 约束条件c 的 s 到t 的最佳可行路径p ( s ，) 互 r 。 对于一部分服务质量的参数( 如剩余带宽、剩余缓存空间等) ，路径的状态 取决于瓶颈链路的状态。对于这些服务质量的参数，可以定义为两类基本的路由 选择问题，一类是链路优化路由选择( 如带宽优化路由选择) 是寻找在瓶颈链路 上具有最大带宽的一条路径，这样的一条路径被称为最优路径；另一类是链路约 束路由选择( 如带宽限制路由选择) 是寻找瓶颈带宽高于要求值的一条路径链路。 链路优化路由选择问题，可以通过将d i j k s 觚算法或b e l l m 锄一f o r d 算法稍作修改， 而得以解决。同时，链路约束路由选择问题可以相应地简化为链路优化问题。 对于其它服务质量的参数( 如时延差、开销等) ，路径状态取决于路径上所 有链路状态的组合。同样，根据这些服务质量的参数，可以定义两类基本的路由 选择问题，第一类是为路径优化路由选择( 如最小开销路由选择) 是寻找总开销 最小的一条路径。第二类是路径约束路由选择( 如时延约束路由选择) 是寻找时， 延局限于一个要求的值之内的一条路径。这两类问题可通过d i i k s 昀算法或 b e l l m a l l f 0 r d 算法直接解决。 综上所述，根据q o s 参数q o s 单播路由所涉及的四种基本q o s 路由问题分别 是链路约束路由问题( 1 i n k 叫c o n s 仃a i n e d u t i n g ) 、链路优化路由问题( 1 i n k 叼p t i 面z a t i o n r o u t i n g ) 、路径约束路由问题( p a t i l 枷l l s 砌n e dr o u t i i l 曲以及路径优化路由问题 ( p a t h - o p t i m i z a t i o nr o u t i n g ) 。 二、组播路由( m u l t i c a s tr o u t i n g ) 一个带权值的有向图可以表示为g = ( ，) ，源节点s 、目的节点集m 、q o s 约束集c 以及优化目标函数d 。q o s 组播路由就是以网络拓扑结构和网络状态为 基础，构建一棵组播树7 ，包含源节点和所有的目的节点，并且满足给定的约束条 件c 以及优化目标函数d 。 根据树约束、链路约束以及目标函数，即根据所需解决的问题，组播路由问 题可分为以下十二大类1 2 4 j ： 1 链路约束问题( 1 i 1 1 l ( c o n s 慨n c dp r o b l e m ) ：规定一个链路约束来构造可行 的组播树。例如，带宽约束路由。 2 多链路约束问题( m u l t i p l el i i l l ( c o n s t r a j n e dp r o b l e m ) ：规定两个或多个链 路约束来构造可行树。例如，带宽和缓冲约束路由。 3 树约束问题( t r e ec o n s 佩n e dp r o b l e m ) ：规定一个树约束来构造可行的组 播树。例如，时延约束路由。 4 多个树约束问题( m u i t i p l e 骶ec o n s 仃a i n e dp r o b l e m ) ：规定两个或多个树 约束来构造可行的组播树。例如，时延和时延抖动约束路由。 l o基于多约束条件的q o s 路由算法研究 5 链路及树约束问题( 1 i i l k 锄d 掀c 0 删n e dp r o b l 锄) ：规定一个链路约 束和一个树约束来构造可行的组播树。例如，时延和带宽约束路由。 6 链路优化问题( 1 i n ko 两捌o np m b l 锄) ：使用一个链路优化函数来构 造一个优化的组播树。例如，组播树中树链路上的带宽最大。 7 树优化问题( 嗽o p t i i i l i 刎0 np b l e m ) ：使用一个树优化函数来构造一个 优化的组播树。例如，组播树的总代价最小。这就是著名的s t e i n e r 树问 题。 8 链路约束链路优化问题( 1 i n kc 0 e dl i n ko p t i i i l i 盈：t i o np r o b l e m ) ：规定 一个链路约束并使用一个链路优化函数来构造一个优化的组播树并实现 约束。例如，带宽约束缓冲优化问题。 9 链路约束树优化问题( 1 i i l kc o n s n 面n c dn 优o p t i m i z a t i o np r o b l e m ) ：规定一 个链路约束并使用一个树优化函数来构造一个优化的组播树并实现约束。 例如，带宽约束s t e i i l c r 树问题。 1 0 树约束链路优化问题( 仃优c o i l s 廿面n e dl i i l l ( o p t i n l i z a t i o nr o u t i n gp r o b l e m ) ： 使用一个树约束和链路优化函数来构造一个优化的组播树。例如，时延约 束带宽优化问题。 11 树约束树优化问题( 眈ec 0 n s 砌n 酣t r e eo p t i l i l i z a t i o nr o u t i n gp r o b l e m ) ：使 用一个树约束和树优化函数来构造一个优化的组播树。例如，时延约束 s t e i n e r 树问题。 1 2 链路约束及树约束树优化问题( 1 i i l l ( 锄d 仃e ec o n s t r a i n e d 嗽o p t i m i z a t i o n r o u t i n gp r o b l e m ) ：使用链路和树约束和树优化函数来构造一个优化的组 播树。例如，带宽和时延约束的树优化问题。 第l 、2 类问题相对容易处理，因为我们可以通过从网络拓扑中删除那些不合 要求的链路来满足链路约束。w 锄g 和c r o w c r 0 r 己经证明寻找一条路径使之满足 两个或多个相互独立的可加性或可乘性的约束条件以及它们的任意组合是n p 完 备问趔2 5 l 。但只有凹性约束和其它可加性或可乘性约束的组合问题是容易处理的。 因此，问题3 和5 在多项式时间内是可解的，而问题4 是n p 完备问题。s h a c h 锄 提出了解决问题6 的一个多项式时间复杂度的算法。如果从网络拓扑中删除那些 不满足约束条件的链路，则问题8 和1 0 可转化为问题6 ，因此它们在多项式时间 内是可解的。同时问题7 ( s t e i n e r 树问题) 和问题9 、问题l l 以及问题1 2 ( 约束 的s t e i n e r 树问题) 己被证明是n p 完备问题。 第二章o o s 路由基础理论 2 2 多约束条件下q o s 路由算法研究 目前，人们正期待着宽带综合业务网可以支持各种各样的多媒体应用并满足 其不同q o s 要求。如何提供资源来满足每次连接的请求是宽带体系结构设计中的 一个关键问题。而建立有效的q o s 路由方案是该体系结构中的一个重要组成部分。 但如我们在2 1 3 中介绍的一样，q o s 路由是一个非常复杂的问题。 在q o s 的早期研究中，关于q o s 的研究主要着眼于调度、拥塞控制和资源预 留几个方面，而对于q o s 路由的研究很少。在当前i n t e m e t 中，路由算法主要用于 保证基本连通性，因此路由协议往往是基于单一参数( m e t r i c ) 优化的，难以满足 多样的q o s 需求。近几年的研究表明网络路由算法对于实现q o s 保证起到了至关 重要的作用，同时网络路由算法也是平衡网络负载以及充分利用网络资源的重要 保证。因此选择一个q o s 路由的优化策略显得格外重要，它也是实现q o s 保证的 关键因素之一，也是目前关于q o s 的一个重要的研究方向。由于基于多约束条件 建立的网络模型可以更准确地反映实际的q o s 路由选择问题，所以随着人们对于 q o s 要求的提高和网络规模的不断扩大，研究基于多条件约束的q o s 路由算法， 对于获得更好的网络服务质量和较高的网络资源利用率具有十分重要的研究意 义。 2 2 1 多约束条件下q o s 路由算法的分类 如2 1 3 中介绍，q o s 路由问题可以分为四种基本的q o s 路由问题，而有关 q o s 单播路由的一些组合路由问题都是由四种基本问题演化而来。如图2 1 所示， 图中列出了q o s 单播路由中的组合路由问题以及它们和基本路由问题之间的相互 关系。 1 2基于多约束条件的q o s 路由算法研究 基本qos 路由问题 单播路由：寻找可行路径 组合qos 路由问题 链路优化路由( 例 如，带宽优化路由) p 问题 链路约束路由( 例 如带宽约束路由) p 问题 路径优化路由( 例 如，最小代价路由) p 问题 路径约束路由( 例 如，时延约束路由) p 问题 。 - 、 链路约束链路优化路由 ( 例如带宽约束缓冲 优化路由) p 问题 链路约束路径优化路由 ( 例如。带宽约束最小 时延路由) p 问题 链路约束路径约束路由 ( 例如。带宽、时延约 束路由) p 问题 l 路径约束链路优化路由 j ( 例如。时延约束最小 7 i 代价路由) np 完全问题 路径约束路径优化问题 ( 例如，时延约束最小 代价路由) np 完全问题 多路径约束路由( 例 如。时延及时延抖动约 束路由) np 完全闯题 图2 1q o s 单播路由 由图2 i 可知，在q o s 单播路由中存在两类n p 完备的路由问题：路径约束路 径优化路由问题( p a t h c o n s t m i n e dp a t h o p t i m i z a t i o nr o u t i n g ，p c p o ) 和多路径 约束路由问题( m u l t i p a t l l c o n s 舰i n e dl b u t i n g ，m p c ) 。这两种n p 完备问题是 基于以下两个基本假设建立的：1 ) q o s 参数相互独立：2 ) q o s 参数值是实数或极 大整数。如果n 个q o s 参数中有n 1 个有界整数，则n p 完备问题可以通过扩展的 d i i k 咖或b e l l m 锄f o r d 算法转化为p 问题( 多项式问题) 。同时大量的文献也可 以证明，如果所有的q o s 参数与其中任何一个相关，算法也可以在多项式时间内 求解。例如，在使用加权公平排队( w e i g h t e df a i rq u e u i n g ，w f q ) 调度的函数中， 最差情况的时延和时延抖动是网络带宽的函数。根据上述原理，时延及时延抖动 约束的路由问题同样可在多项式时间内求解。 第二章q o s 路由基础理论 表2 1 列举了近几年提出的一些典型的q o s 单播路由算法( 表中路由算法用 作者姓名表示) 。同时表中也列举了算法解决的路由问题、路由策略以及计算的 时间复杂度和状态信息。 表2 1 典型的q o s 单播路由算法 路由策 算法解决的问题时间复杂度状态信息 略 带宽、代 c h e n - n a i u 妞e d t源路由 d ( 朋p ) 全局 价约束 带宽 源路由 l o g 刀+ p ) 全局 约束 m a s t e e r l k j s t e 多链路 约束 源路由 d 沏p ) 全局 带宽、时 w 雒g - c r o w c r o r 源路由 d ( 玎l o g n + p ) 全局 延约束 带宽全局 g u e r 证o “l a约束 源路由 l o g 刀+ p ) ( 不精确) 时延全局 约束 源路由多项式 ( 不精确) 时延约束 j u t t i l e r源路由 d ( p 2l 0 9 4 p ) 全局 最小开销 多路径约束 k o r l a z源路由多项式 全局 路径优化 n e v e多约束路径源路由 d l o g 汹+ k 3 砌) ) 全局 w a n g - c r o w c r o r 带宽优化分布式 p ) 全局 时延约束最小开 s a l a m a分布式 d 0 3 p ) 全局 销 s 眦 时延约束最小开 分布式d g )全局 销 多约束路 o r d a分布式多项式全局 径优化 时延约束 o r 妇分布式多项式全局 最小开销 1 4基于多约束条件的q o s 路由算法研究 表2 1 中n 表示网络节点，p 表示链路数，七为多约束路径的约束个数，k 为 第足条最短路径算法中的参数，p 为路径的个数。 2 2 2m c p 问题q o s 路由算法简述 分组交换网被越来越广泛地应用于传输视频和音频等多媒体信息。这些信息 的传输要求严格的q o s 保证，即对端到端的时延、时延抖动和数据丢失率等有严 格的限制。从网络用户的角度来看，基于q o s 的路由算法首先应保证能够满足用 户的q o s 请求，即寻找一条满足各种条件限制的从源节点到目的节点的传输路径。 从服务提供商的角度来看，基于q o s 的路由算法应能最大化地利用网络资源。同 时，从网络工程师的角度来看，基于q o s 的路由算法应能够有效地选择传输路径， 从而保证网络的最大吞吐量。 服务质量路由中的一个主要问题就是在多约束条件下的目标优化。多受限路 由算法的研究目标是找到一条满足所有独立限制条件的传输路径。最典型的例子 就是确立一个路径可以在一个或多约束条件( 如端到端时延) 下最小化一些目标 参数，比如说传输费用。由于q o s 的参数是实数或无边界的整数，因此这些问题 都是n p 完备的。 为解决这个n p 完备问题，可以从两个方向进行研究：一种是采用启发式算法， 该类型算法可以降低算法时间复杂度，但不能保证在存在多条传输路径的条件下 发现一条可行的传输路径。另一种是采用近似算法，该类型算法可以用伪多项式 或多项式的时间复杂度算法求最优化路径的近似解，但其时间复杂度较高，在实 际的网络应用中一般不采用。 另外，可以通过简化网络模型，仅考虑限制条件的一个子集，如带宽和延时。 众所周知，在一般情况下，如果q o s 路由至少包含两个限制时，它是一个n p 完 备问题【9 】。但在一些特殊情况下，该问题是可解的。例如： ( 1 ) 带宽限制与其他限制条件中的任何一个的组合问题不是n p 完备问题。通过删 除所有不满足请求所要求的传输带宽的传输链路获得一个新的网络拓扑结构， 在新的网络拓扑下，原来的问题转化为一个限制条件的问题。 ( 2 ) 在某些提供单个流传输性能保证的调度算法下的路由问题。在一些调度算法 下，例如：v c ( v i m 脚c 1 0 c k ) 、w f q ( w e i 曲t e df 面r q u e u i n g ) 、w p z q ( 、r o r s t c 嬲e w e i g h t e df a i rq u e u i n g ) 、s c f q ( s e l f c l o c k e df a i rq u e u i n g ) 等，传输时延、 时延抖动和丢失率等限制条件可以定义为带宽的函数，因此，该问题转化为最 短路径问题。 ( 3 ) 如果每条链路上的某个限制条件是一致的，则与任何一个其他限制条件下的最 优化问题可以用改进的b e l l m 觚f o r d 算法求解。 第二章q o s 路由基础理论 2 2 3m c o p 问题q o s 路由算法简述 新出现的分布式多媒体应用要求提供端到端的q o s 保证，同时它们在延时和 开销等方面有严格的限制。提供这种端到端的q o s 保证的一个关键问题就是q o s 路由。q o s 路由的任务就是找到一条可行路径使它满足一组限制条件的同时获得 较高的网络资源利用率。要实现后一个目标我们需要在现有的问题上增加一个优 化要求【i 引。一般而言，无论是否考虑优化，多受限的路径选择问题都是n p 完备问 题。时间复杂度为多项式或伪多项式的启发和近似算法常常被用来解决此类问题 w 。然而，现有的算法不是计算复杂度过高而不能用于实际应用，就是性能较差。 因此，这些算法仅仅处理了问题的某一个方面，例如：两个限制条件时不考虑优 化，一个限制条件的情况下考虑优化等等。 任何一个计算机网络的拓扑都可以抽象成为一个赋权值的图g = 缈，e ) 。其中 y = 化，圪) 是由代表路由器的所有交换节点组成的集合，e = 佤，b e ) 是 所有连接路由器的链路的集合。假设每条传输链路e 包含尺+ 1 个元素，即 = k ，w l ，w 2 毗) ，其中c 表示在传输链路e 上的传输费用 w 1 ，峨 = l ，2 k ，表示k 个可加性参数，所有参数是非负的。 这里用r = ( s ，d ，c l ，c ，c r ) 表示网络中的任意一个路由请求，其中s 表示路 由请求r 的源节点，d 表示路由请求r 的目的节点，c 1 ，c ，c 。任= l ，2 k ) 表示 给定的k 个限制条件。m c o p 问题就是为每一个请求r 在通信网络中寻找一条最 优的且能够满足所有限制条件的传输路径，问题可以如下具体描述为： m c o p 问题：对于一个给定的网络g = ( y ，) 和请求尺= ( s ，d ，c l ，c ：c r ) ， 计算一条从源节点s 到目的节点d 的传输路径p ，并使得路径尸满足以下要求： ( 1 ) 传输路径p 上的所有链路的每个可加