（通信与信息系统专业论文）多目标最优化在网络路由中的应用.pdf

摘要 摘要 蓬勃发展的网络多媒体应用和提供更多增值服务的业务需求使传统网络技术 面临极大挑战。就目前而言，传统的路由算法只考虑单个目标的性能优化，辅之 以多个约束条件。即使是现有的多目标最优化路由算法，其求解方法通常也是将 多个目标减少为一个，然后用数学规划工具求解问题，这样得到解缺少稳定性和 可靠性，往往并不是我们实际所需要的结果。本文在总结、分析前人研究的基础 上，围绕网络路由问题，对多目标最优化单播和多播路由、区分服务模型、遗传 算法、多播可扩展性等多个方面进行研究，提出了一些新方法和新思路。 首先，本文针对如何为不同等级的数据提供不同质量的传输服务，如何提高 网络资源利用率，优化网络配置等问题，在分析和对比常见的两种q o s 服务模型： 综合服务模型和区分服务模型的基础上，提出了基于区分服务模型的多目标最优 化单播路由算法。有效地提高了网络资源利用率，平衡了网络负载，减少了网络 拥塞。 第二，针对现有多播可扩展性方法的不足( 现有的方法大都在已有多播路由 的基础上进行改进，效率较低) ，将多播可扩展性作为一个最优化目标引入到多播 路由算法的设计中，有效地提高了多种多播可扩展性方法的效率，是多播可扩展 性研究的一个新思路。 第三，研究了如何利用遗传算法来求解多目标最优化单播q o s 路由，仿真实 验验证了算法能够快速有效地找到路径，并能为不同等级的数据提供不同质量的 传输服务，有效地提高了网络资源利用率，平衡了网络负载，减少了网络拥塞。 第四，研究了如何利用遗传算法来求解多目标最优化多播路由，并将其应用 于求解多播可扩展路由的生成，取得了较好的效果。 关键词：单播q o s ，多播可扩展性，多目标最优化，遗传算法，区分服务 a b s t r a c t a b s t r a c t t h er a p i dg r o w t ho fm u l t i m e d i aa p p l i c a t i o na n dt h ei n c r e a s i n gd e m a n do nb u i l d i n g v a l u e a d d e d s e r v i c eg e n e r a t em o r er e q u e s t so i lp r e d i c a b l es e r v i c eo v e ri n t e r u e t t h i s l e a d st og r e a tc h a l l e n g et oc u l t e n tn e t w o r kt e c h n o l o g y u s u a l l y , c u r r e n t r o u t i n g a l g o r i t h mj u s ta i ma ts i n g l eo b j e c t w i t hs e v e r a lr e s t r i c t i o n s a n dm u l t i o b j e c t i v e o p t i m i z a t i o nr o u t i n ga l g o r i t h mc u s t o m a r i l yc o m ed o w nt os i n g l eo b j e c t t h er e s u l ti s n o ts t e a d ya n dc r e d i b l e nt h ep a p e r , w ed i s c u s st h em u l t i o b j e c t i v eo p t i m i z a t i o n s i n g l e c a s ta n dm u l t i c a s tr o u t i n ga l g o l i t h m ，t h em o d e lo fd i f f e r e n t i a t e ds e r v i c e ，g e n e t i c a l g o r i t h ma n dm u l t i c a s ts c a l a b i l i t yb a s e do nt h ep r e d e c e s s o r s a tl a s t ，w ew i l lp r o p o s e s o m en e wm e t h o d sa n di d e a s f i r s t l y , a i m i n ga tt h ei m p r o v i n go ft h er a t i oo fi n t e r n e t r e s o u r c ea n do p t i m i z a t i o no f i n t e r n e ts c h e m e ，w ep r o p o s em u l t i o b j e c t i v eo p t i m i z a t i o ns i n g l e c a s tr o u t i n ga l g o r i t h m b a s e do nt h ed i f f e r e n t i a t e ds e r v i c e ，w h i c hc a np r o v i d ed i f f e r e n tq u a l i t yt r a n s m i s s i o n s e r v i c e sf o rd i f f e r e n tr a n kn e t w o r kd a t a t h em o d e lc a nb a l a n c et h en e t w o r kl o a da n d r e d u c et h en e t w o r kc o n g e s t i o ne f f e c t i v e l y s e c o n d l y ，u n l i k ep r e v i o u sa p p r o a c h e st h a tc o n c e n t r a t e do nr e d u c i n gf o r w a r d i n gs t a t e st o i m p r o v em u l t i c a s ts c a l a b i l i t ya f t e rc o n s t r u c t i n gm u l t i c a s tt r e e s ，o u ra p p r o a c h i st o i n c l u d ef o r w a r d i n gs t a t es c a l a b i l i t ya so n eo ft h eo p t i m a lo b j e c t i v e sw h e nc o n s t r u c t i n g n e wm u l t i c a s tt r e e s t h a ti s ，w em a k et h eu n d e r l y i n gr o u t i n ga l g o r i t h m sa w a r eo ft h e s c a l a b i l i t yr e q u i r e m e n t t h i si ss c a l a b i l i t y a w a r ea p p r o a c hc a nb ea p p l i e dt om a n y e x i t i n gm u l t i c a s ts t a t er e d u c t i o nm e t h o d s t h i si s an e wi d e af o rm u l t i c a s ts c a l a b i l i t y p r o b l e m t h i r d l y , w es t u d y h o wt ou s et h e g e n e t i ca l g o r i t h ms o l v et h em u l t i - o b j e c t i v e o p t i m i z a t i o ns i n g l e c a s tq o sr o u t i n ga l g o r i t h m t h es i m u l a t i o nr e s u l ts h o w st h a tt h e m e t h o dc a nf i n ds i n 百e c a s tr o u t eq u i c k l ya n de f f e c t i v e l y i ta l s os h o w st h a tt h em o d e l c a bp r o v i d ed i f f e r e n ts e r v i c et od i f f e r e mr a n kn e t w o r kd a t a ，b a l a n c et h en e t w o r kl o a d a n dr e d u c et h en e t w o r kc o n g e s t i o ne f f e c t i v e l y l a s t l y , w es t u d yh o w t ou s et h eg e n e t i ca l g o r i t h ms o l v et h em u l t i o b j e c t i v eo p t i m i z a t i o n a b s t r a c t m u l t i c a s tr o u t i n ga l g o r i t h m a n du s e o u rm e t h o d st of i n ds c a l a b l em u l t i c a s tr o u t i n g k e yw o r d s ：s i n g l e c a s tq o s ，m u l t i c a s ts c a l a b i l i t y , m u l t i o b j e c t i v eo p t i m i z a t i o n ，g e n e t i c a l g o r i t h m ，d i f f e r e n t i a t e ds e r v i c e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：整盈日期：蛔6 年主月p s 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：三二正 导师签名：盈妊么l 日期：灿年钼出日 第一章绪论 1 1 研究背景 第一章绪论 在过去的十年里，计算机网络飞速发展，网络用户急速增长，网络功能日益 强大，网络的作用从简单的信息传递发展到远程教学、视频会议、数据分发和网 络游戏等。这些变化虽然对传统的网络应用影响不大，但是，越来越多的实时服 务对网络提出了新的要求，导致了互联网业务量特性的变化和对网络服务质量要 求的变化，从而对网络路由提出了更高的要求。如今，不管是单播还是多播路由， 仅仅只考虑单个网络性能指标的优化已经不能很好的解决问题，很多网络实际问 题要求路由算法进行多目标最优化的研究。 1 1 1 单播q o s 路由 互联网必须能够在提供可靠业务量传输能力的前提下针对不同的用户要求提 供不同质量的传输服务，但是，互联网的基本传输机制却没有发生变化，所有的 数据报都被以“尽力而为”的方式发往目的地，网络既不因为数据报所属应用类 型的差异而进行区别处理，也不确保其传输可靠性。而现有的大部分i g p 协议( 内 部网关路由协议) 在建立转发表时，并未将带宽的可用性和业务特点等因素考虑 进去，在一些情况下会使网络出现阻塞，这时就需要流量工程来解决问题。流量 工程是一个强有力的工具，通过它可以平衡网络中不同的链路、路由器和交换机 之间业务负荷，使所有这些设备既不会过度使用，也不会未被充分使用。这样就 可以有效利用整个网络的资源，流量工程成为路由结构中一个重要的辅助部分， 而路由优化就是实现流量工程目标的重要策略之。由此，有必要在现有的互联 网技术体系中引入新的控制机制和传输机制，从业务量本身特性和服务质量控制 角度出发，进行高效路由技术的研究。 针对这些需求，研究人员已经在服务质量控制和q o s 路由方面开展了大量的 研究工作，但仍然存在系列的问题： 服务质量 由于多媒体应用数量的日益增长和商业应用对网络可用性和传输带宽方面的 电子科技大学硕士学位论文 严格要求，网络必须在确保对关键应用的服务质量的同时保证对普通用户的支 持，然而现有的网络资源提供机制和拥塞控制机制基本上只采用以单个数据流 为基础的精细模型和以流聚集为基础的统计模型两种研究方法。当用户数量在 短期内迅速增长或网络内出现局部资源竞争时，网络无法确保对用户的服务质 量。 网络性能和资源利用率 互联网业务量在整个网络中是非均匀分布的；现有i p 路由方法仅以静态链路 度量为基础计算端到端的最短路径作为传输路径，因此i s p 不得不依靠过度供 给方法来实现对用户的服务承诺。其结果是：当网络的某一部分会因为负载不 断增加和突发负载发生拥塞，而还有大量链路处于空闲状态，网络资源得不到 充分的利用。 链路带宽分配策略的不公平性 当网络重载或接受高等级( p r e m i u m ) 服务的业务量比例较高时，网络对其它 等级业务量的服务质量就会严重下降，即产生“类间效应”。受限于目前使 用的单路径路由技术，无论所属服务等级如何，数据流都沿着从数据源到目的 节点的最短路径传输，由此当网络中某一方向存在大量的p r e m i u m 类型数据负 载时，某一路由节点的队列可能溢出，从而导致不满意的传输服务。 目前网络中采用的路由算法，采用的都是基于s p f ( 最短路径优先算法) 或者 c s p f ( 约束最短路径优先算法) 来计算传输路径的，就算基于流量工程方面的考虑 进行了改进，例如e c m p ( 平均费用多路选择) 和e b ( 相同带宽) 多路约束算法， 将流量平均分配到多条最短路径上，但是仅以单个目标为主，加诸约束条件来考 虑，得到的路径并非实际上最优的路径，未必满足网络的实际需求。 1 1 2 多播路由 随着i n t e m e t 的迅速普及和发展，大量的应用譬如网络视频会议、网络音频 视频广播、多媒体远程教育、远程会诊，分布式并行处理和分布式交互仿真等都 要求网络本身提供多播服务。与多个接收者有关的网络通信，使用i p 多播的优点 ( 相对于口单播来说) 集中体现在节约网络带宽、降低网络( 路由器和交换机) 负载、 降低服务器( 源i p 主机) 的负载三个方面。与几乎同时代产生的w w w 技术相比， i p 多播在八十年代和九十年代初期的发展速度相对较慢，九十年代中期以来随着 网络业务量尤其是多媒体会议、数据分发、分布式并行处理和分布式交互仿真等 2 第一章绪论 多播业务量的增长，i p 多播技术受到人们的广泛重视，在理论和实际应用上均取 得了长足的进展。多播路由选择的最终目标是要在满足应用需求的条件下，使用 最少的网络资源，最大限度的优化网络资源配置。它直接关系到网络效率、传输 延迟和吞吐量等通信网络的主要技术性能指标。可以说网络最终能提供什么品质 的多播服务，能在多大程度上满足用户的多播服务需求，在很大程度上取决于路 由算法的设计。多播路由算法根据多播应用的要求，确定路由选择的最优化目标 和约束条件，并最终生成满足最优化目标和约束条件的一棵多播树来连接多播源 和所有的多播组成员。 随着多播应用在网络中的进一步普及，人们希望多播路出算法能对多播应用提 供更多更好的支持，提高整个网络的资源利用率，降低多播应用的通信成本，主 要的研究方向集中在以下几个方面：( 1 ) 进一步提高多播路由选择算法本身的计 算效率，降低多播服务本身的系统开销；( 2 ) 多播路由选择算法要为新的网络服 务( 如o o s 、成组多播等) 提供有效的支持；( 3 ) 多播路由算法为网络资源的优 化配置( 如多播的可扩展性、流量工程等) 提供有效的支持，使网络的运行效率 得到进一步提高。 1 1 3 将多目标最优化应用于路由算法 目前网络中广泛应用的单播路由算法大多是单目标路由算法，算法通常只针对 单个目标进行优化，比如时延、带宽等等。即使是上面提到的e c m p 和e b 算法， 也不是多目标最优化算法，而是多约束单播路由算法，多约束路由算法应用的结 果并不能得到多个网络参数的最优解。 九十年代中期以来，随着网络业务量尤其是多媒体会议、数据分发、分布式并 行处理和分布式交互仿真等多播业务量的增长，更多的研究工作者开始研究多播 路由算法，从而使得多播路由算法的理论和应用都得到了长足进步。网络的巨大 发展和多播的广泛应用对多播路由算法提出了更高的要求，单目标多播路由算法 能提供的支持已经渐渐力不从心了，多约束的单目标多播路由算法毕竟不能满足 网络应用的需要。 路由算法中的多约束和多目标算法有着本质的区别：约束是指在路由算法中需 要满足的条件，在算法中只需要达到要求即可，以时延为例，当算法要求时延小 于2 m s 时，就没有必要要求时延小于l m s ；而目标则是在路由算法中最优的解， 算法的要求是目标解越优秀越好，同样以时延为例，我们就要求时延越小越好。 电子科技大学硕士学位论文 最近几年来，网络结构越来越复杂，随着网络速度的提高，网络的应用也越来 越广泛，而且网络应用日益向高速、实时方向发展，对路由算法的要求也越来越 高。这就决定了现有的多约束路由算法不能很好的满足需要，因为在网络研究的 领域中，我们所求解的目标往往超过一个，并且需要同时处理，将多目标最优化 引入路由算法可以解决这个问题。 传统的多目标优化问题的主要解决方法是由设计人员通过向领域专家给出各 目标的重要程度或偏好排序，或加权使之化为单目标优化问题，主要缺点是：( 1 ) 决策者往往希望提供不只种方案供选择，而此类方法只能提供唯一解( 2 ) 该方 法需要决策者对问题有全面而充分的知识才能给出合理的权值，而这一点往往很 困难，影响了解的可靠性，另外对权值参数的过分敏感，也影响了解的稳定性。 过去的2 0 年中，遗传算法作为多目标优化问题的新求解方法受到了相当程度 的关注，这就诞生了遗传多目标化。利用遗传算法来求解多目标最优化问题可以 得到一组最优解，决策者可以从这一组解中选出最适合实际情况的一个最优解。 1 2 相关概念和理论 1 2 1 流量工程和服务质量 流量工程 i s p 所面临的最基本挑战是如何增强客户满意度的同时扩展和优化自己的网 络以保持高速的增长。i s p 必须配置一个物理拓扑以满足客户的需求，同时还要提 供不同的带宽链路。在配置完网络之后。i s p 必须将用户的业务流映射到物理拓扑 上去。流量工程是可靠而经济地进行业务流映射的主流技术。 导致网络拥塞的原因可能是网络资源不足或业务流量分布不均匀。在第一种 情况下，所有路由器和链路都会过载，唯一的解决办法是升级基础设施，提供更多 的资源。在第二种情况下，网络中一些地方过载而其他地方的负载却较轻。当前广 泛使用的动态路由协议，如r i p 、o s p f 和i s i s 等，都会导致不均匀的流量分布。 因为它们总是选择最短的路径来转发数据包，结果造成两个结点之间最短路径上 的路由器和链路可能发生拥塞，而较长路径的路由器和链路却是空闲的。对于简单 网络，通过网络管理员手工配置链路，均匀地分配流量是可行的。但对于复杂网络， 则几乎不可能。流量工程就是针对第二种情况提出的，与流量工程相关的性能指 标主要有： 4 第一章绪论 ( 1 ) 面向业务的性能指标 面向业务的性能指标包括了增强业务q o s 性能的各个方面，在单一q o s 等级， 尽力而为的的业务模型中，面向业务的性能指标包括：通过使包丢失率最小化、 使阻塞持续时间最小化和吞吐量最大化，增强业务的性能；增强支持多种业务所需 的统计性能参数( 如丢包率，传输延迟) 。 ( 2 ) 面向资源的性能指标 面向资源的性能指标包括了优化资源利用的各个方面。流量工程试图改善网 络资源的利用率和网络的吞吐量，堵塞的最小化是面向业务和面向资源的主要性 能指标。网络堵塞一般发生在以下两种情况：网络资源不足或不能满足负载的要 求；业务流映射到实际物理通信通道时没有有效的调度，造成一部分网络资源使 用过度，而另一部分欠使用。 服务质量 从用户角度看，网络的服务质量是指用户能感受到的网络应用的性能度量， 这些性能度量不仅仅取决于网络传输的服务质量而且取决于终端系统的负载程度 和操作系统的调度策略。因此，在剔除终端系统的影响因素之后，网络的服务质 量是指以一系列性能参数刻画的端到端通信特性，这主要包括以下参数集合： 传输服务的可靠性( s e r v i c ea v a i l a b i l i t y ) 指端到端网络连接的可靠性 延时 指两个参考点之间数据的传输延时 延时抖动 指采用相同路由的数据报流在穿过相同的测量间隔时表现出来的延 时差异 吞吐量 指数据在网络中的传输速率，可以用平均速率或峰值速率来表达 丢包率 指在传输过程中数据丢失的最大比率 在目前已经商业化的互联网条件下，高质量的网络服务并不意味着以上所有 参数的极优化，而是指网络服务提供商根据与用户签定的服务协议提供满足要求 的传输服务。因此，基本的网络提供机制是：从具体的商业服务策略出发，在不 同价格水平商提供具有不同性能参数的传输服务。这不仅意味着满足不断提高的 用户通信要求，而且意味着最大限度的利用已有网络资源，降低服务成本。 电子科技大学硕士学位论文 1 2 2 多播可扩展性 i p 多播是一种以多播生成树为核心的技术，路由算法参照某些最优化目标和 约束条件生成一颗多播树，多播源生成的信息沿着多播树遍历传送，每一个多播 路由器将为每一颗多播树保留以路由转发信息为核心的相关信息。随着i p 多播应 用的进一步普及，人们发现在传统的多播路由技术中，路由器需要为每一个多播 组的每一个多播会话保留一个路由转发信息和状态，随着多播会话的增加，这会 耗费大量的存储空间，同时降低i p 路由查找的速度( 这一点对i p v 6 影响更大) ， 从而严重影响i p 包在网络中的传送速度，降低了网络本身的效率。也就是既，当 多播会话增加到一定程度时，现行的1 p 多播技术在可扩展性方面存在一些不足， 为此我们需要采用一些技术来提高口多播的可扩展性，使网络能同时支持更多地 i p 多播会话。 为提高i p 多播的可扩展性，近年来人们进行了大量的研究，提出了许多改善 多播的可扩展性的方案，为讨论方便我们将其分为三类： 组内状态消去方法 他利用现有多播树本身的结构特点，直接消去一些多播状态，如d t mf d y n a m i c t u n n e lm u l t i c a s t ) 技术利用p 隧道直接跨过多播树中那些只有一个子节点而 本身又不是多播成员的节点；r e u n i t e 不建立多播隧道，而是对多播树中那 些只有一个子节点而本身又不是多播成员的节点采用单播技术代替多播技术， 己达到减少多播状态的目的。这类方法的一个共同特点是所有的措施在一个多 播组内实施，一个多播组的状态消去不影响另一个多播组，因而方法相对简单。 组间状态汇聚方法 他利用现有两颗多播树本身的结构特点，消去一些相同的多播状态。如两颗多 播树在同一个节点上具有相同的输入节点和输出节点，就可以将两个多播组在 这一个节点的状态汇聚( 通常汇聚在一颗子树上实施) ，已达到减少多播状态 的目的。通常两颗多播树在同一个节点上具有完全相同输入节点和输出节点的 情况并不多，为进一步提高方法的效率，人们又提出了一种可渗漏的汇聚方案， 即允许属于不同多播组的两颗子树不完全相同得子树汇聚，汇聚后的子树覆盖 两颗子树的所有节点，因此多播信息有可能进入被“渗漏”到多播树以外，在 提高多播可扩展性的同时，增加了一些传输负担。 同时利用组内状态消去、组间状态汇聚两种方式，使用一颗多播树来传送多个 第一章绪论 多播组的信息，该类方法的典型代表是：汇聚多播a m ( a g g r e g a t e dm u l t i c a s t ) ， 该方法假设网络中存在个节点知道整个网络的拓扑结构和所有多播会话采 用的多播树，由它来将所有相似的多播树组成一个多播群，使用一颗多播树( 称 为汇聚多播树) 来传送所有多播群的信息。由于两颗多播树完全相同的可能性 很小，因此相似的多播树之间也必然有不完全相同的地方，汇聚多播树必须覆 盖多播群内绝大部分节点，与第二类方法类似，多播信息有可能进入被“渗漏” 到原多播树以外，在提高多播可扩展性的同时，也增加了一些传输负担。同时 有一些节点可能不包含在多播树中，对于这些节点通常为他们建立一个专用的 隧道传送多播数据包。 1 3 研究现状 1 3 1 单播o o s 路由算法 目前在网络中使用的单播路由技术，无论所属服务等级如何，数据流都沿着 从数据源到目的节点的最短路径传输，由此当网络重载或接受最高等级业务量较 高时候，网络对其它等级业务量的服务质量下降，而且易于造成链路拥塞。产生 这种现象的根源在于单一化的网络路由机制和带宽共享策略的不公平性。因此， 有必要在建立合理节点资源共享机制基础上研究区分服务网络中的高效路由方 法。 针对多类网络负载竞争使用带宽资源的问题，i b r a h i mm a t t a 等人在文献【2 3 j 中 使用不同的链路度量计算每类负载的传输路径，并在延时敏感类负载仅占较小比 例时获得较高的网络性能，但是随着这类负载所占比例的逐渐增大，网络性能迅 速下降。 路由选择中，高等级业务流的路由选择会影响低等级业务流的可用资源，易 于造成拥塞，针对这种情况，卡内基梅隆大学的q i n g m i n gm a 和p e t e rs t e e n k i s t e 在文献【2 4 】中提出了一种动态类间资源共享的多类q o s 路由算法，该算法将低优先 级的业务流量的状况考虑在内，建立“虚拟剩余带宽”。通过评价链路代价，高等 级业务流的选路基于b e s t e f f o r t 业务量的链路拥塞度，虚拟剩余带宽= 剩余带宽+ 信用带宽，当链路轻载的时候，信用带宽为正，当链路重载的时候，信用带宽为 负，高等级业务流的路由选择基于虚拟剩余带宽。模拟结果显示：当网络重载或 数据负载在网络中非均匀分布时，多类q o s 路由能够有效的提高b e s t e f f o n 业务 7 电子科技大学硕士学位论文 量的服务质量，而且这种改进效果在“尽力而为”式数据负载加重、网络负载非 均匀分布及有大量带宽可供预留的情况下更为明显。但是该算法采用的是高等级 负载规避低等级负载的方式，而且在算法中也仅仅是考虑了带宽资源目标，没有 很好的考虑各等级的差别。 在文献【冽中，伊利诺斯州立大学的j u nw a n g ，k l a r an a h r s t e d t 提出了一种区分 服务模型下的逐跳路由算法e b s p ( e n h a n c e db a n d w i d t h i n v e r s i o ns h o r t e s t p a t h ) ， 设定了b s 参数来为高等级业务流寻找一条优化路径，既能保证高等级业务流的高 效工作，又能减少对其他等级业务流的负面影响。相对于b s p 路由算法来说，e b s p 算法对跳数的增加加入了惩罚度，能够获得较好的结果，尤其是在更加复杂的层 次化网络中。e b s p 算法虽然以类间效应为基础，但是从节点调度角度来看，仅仅 使用具有最大可预留带宽的p r e m i u m 负载路由优化也不能消除类间效应和资源利 用率之间的矛盾。 在文献【2 6 j 中，芬兰大学网络实验室的p e n gz h a n g 等提出了m c r ( m u l t i c l a s s r o u t i n g ) 的理念来减少类间效应，保障不同类别的业务流得到相应的服务。由于i p 网络中多媒体业务的应用，各种服务类承载在区分服务网络中，类间效应不可避 免，利用m c r ，目的是为了使得网络中的各种类都得到最大程度的优化。 而将多目标的理念应用于网络应用中的相关文献并不多，多数是关于多播路 由方面的。对端到端的路由而言，北京邮电大学宽带通信网络实验室的刘红等提 出了一种多目标的i n t e m e t 路由优化控制算法【1 9 】。算法中同时考虑了网络拥塞最小 化和路径时延最小化。但是没有考虑区分服务下的问题。 1 3 2 多播路由算法 近年来i p 多播技术以其独特的优越性备为缓解i p 网络拥挤问题提供了一种简 单有效的技术手段，并且可以在现有网络设施的基础上部署更多增值服务，因而 备受网络运营商和研究开发人员的关注，多播路由算法作为实现多播通信的一个 关键技术，也吸引了越来越多的学者的注意，得到了比较多的研究，取得了一系 列进展。不过，目前的多播路由算法基本上停留在单目标最优化的求解上，可以 分为单目标无约束多播路由算法和单目标约束多播路由算法。 单目标无约束多播路由 单目标无约束多播路由是一种最常用的多播路由算法，也是其他路由算法的 基础。其基本特征是只有一个最优化目标，无约束条件。常见的单目标无约束多 第一章绪论 播路由算法包括最短路径算法和最小代价算法，分别用于不同的应用需求。在一 些实时交互型应用，如视频会议系统等，最优先考虑的应是尽量缩小端到端的传 输时延，对于实时非交互型应用或非实时型应用，如数据报广播，电子文档分发 等应用，在传输延迟的要求得到满足的前提下，尽量减少对网络资源的占用是这 一类应用最主要考虑的性能。在实际应用中，最短路径和最小代价的涵义可以被 延伸表述为不同的函数，如最小代价可以表述为使用缓冲区的数量、占用信道的 带宽；最短路径可以表述为传输、处理、排队时延的结合，如果所有链路的权值 都为1 ，最短路径树也就是在距离向量协议中被广泛应用的最小跳树。 最短路径算法和最小代价算法等同于图论中构建最短路径树和最小生成树， 数学上用极小代数方法也可以解决这类问题，但是这些方法一般要求求解图的存 储矩阵的n 次方0 为图的结点数) 和矩阵的逆，在实际的网络中网络的结点数通常 比较多，计算网络图存储矩阵的，1 次方和逆一般是不可实现的，因此极小代数方 法在多播生成树问题上一般不能直接应用。 构建最短路径树和最小生成树在图论中最经典的算法是d i j k s l r a 算法和p r i m 算法，这两个经典算法几乎是所有其他单约束的单树多播算法的源泉和理论基础。 这两种经典算法都是需要一个数组来存放结点到源结点的距离或结点到己存在的 生成树的距离，实现简单，稳定性好，时间复杂度都是o 白2 ) ( 门为网络中结点数) 。 构建最小代价树问题可形式化为图论中的s t e i n e r 树问题。s t e i n e r 树问题的求解已 经证明是一个n p 完全问题，不可能在多项式时间内求得其精确解。在可接受的的 计算时间内，我们只能计算得到一棵近似的最优多播树，而不可能获得真正意义 上的最优多播树。 单目标约束多播路由 为确保通信网络能够提供( o o s ) 服务质量保证、必须研究有效的基于o o s 的 路由机制以提供高质量信息传输。一般地，基于o o s 的路由要达到两个目标：一 是要满足用户的q o s 要求，如必须提供足够的带宽、足够小的延时和延时抖动等； 二是要优化网络的利用率及代价。即多播路又要满足两个评测标准：( 1 ) 是否满 足优化网络配置和资源利用率的要求通常用最优化目标表示；( 2 ) 是否满足 实际网络应用的q o s 要求通常用约束条件表示。这样多播路由问题就变成了 一个多目标多约束问题，其中最常见的是单目标多约束路由：即在满足用户的q o s 要求前提下，多播路由的代价最小。 单目标约束多播路由问题，采用构建有核树( c b t ) 的方法实现也是一个重要 的思路，受到日益广泛的关注。对于有核树( c b t ) ，一个重要的问题是c o r e 结点 电子科技大学硕士学位论文 的定位( c o r ep l a c e m e n t ) 问题，选取不同位置的c o r e 结点必定生成不同的c b t 必 定具有不同的性能指标。当前针对c o r ep l a c e m e n t 问题已经进行了广泛的研究，比 较成熟的方法有随机算法( r a n d o ms c h e m e ) 、基于拓扑结构( t o p o l o g y b a s e d ) 的 算法和基于多播组结构( g r o u p b a s e d ) 的算法，但是上述算法都没有对多约束情 况下的c o r ep l a c e m e n t 问题进行讨。在文献【3 7 】中，王明中等人提出了q o c p 算法 在这方面作了非常有益的探索。q o c p 算法的主要思想是将网络中的所有结点所建 立的c b t 的性能抽象为参数平面上的一个点集，然后找出距离最优性能指标点最 近的参数顶点，并以生成此参数顶点的多播树根结点作为c o r e 结点，进而实现满 足构建满足多越束的多播生成树的目的。q o c p 算法虽然在选择c o r e 结点时所需 要做的预处理的工作量很大，计算比较复杂，但是这种算法把数学中点集的概念 引入到多播生成树问题的领域，并成功实践，获得了e b 较好的效果。 随着网络应用的不断发展，多播生成树有时还必须满足其它的服务质量请求， 例如还要考虑端到端的时延抖动、结点多播能力受限等等，针对这些不同的实际 情况，研究者提出了相应的算法。 多目标最优化多播路由 随着多播应用的进步扩展，人们对多播路由算法的研究提出了更高的要求， 如要求多播路由不仅要满足代价最小或时延最小，而且要最能满足多播扩展性的 要求；或者要求多播路由不仅要满足代价最小或时延最小，而且要最能满足流量 工程的要求。这些新加的要求通常是个最优化目标而不是约束条件，这就产生 了多目标最优化多播路由。 目前国内外对于多目标最优化多播路由的研究尚处于起步阶段，相关的文献 不多，除a b h i s h e dr o y , n i l a n j a i lb a n e r j e ea n ds a j a lk d a s 在2 0 0 2 年为适应无线多 播的q o s 需求，首先提出了多目标最优化多播路由问题外，尚无对该问题的详细 讨论。 1 4 研究内容及成果 本文主要工作如下： 提出了多目标最优化单播路由算法 以r d m 带宽分配模型为基础，在保证各个等级服务的基础上，确保关键服务。 以多个目标建立数学模型，给出路由选择算法，以求得到负载均衡的通路，提 高服务质量，减轻网络拥塞。 1 0 第一章绪论 将遗传算法应用于多目标最优化路由 通过对近年来的多种遗传算法进行分析比较，选用n s g a 的遗传算法思想， 以求获得收敛较好分布均匀的解。针对网络模型的实际情况，提出多目标最优 化单播q o s 路由算法，得到较好结果。 采用遗传算法求解多目标最优化问题，并将其应用于求解多播可扩展路由的生 成，取得了较好的效果。 改进多播路由，提高多播可扩展性 针对现有多播可扩展性方法的不足( 现有的方法大都在已有多播路由的基础上 进行改进，效率较低) ，将多播可扩展性作为一个最优化目标引入到多播路由 算法的设计中，有效地提高了多种多播可扩展性方法的效率，在可扩展多播路 由的基础上，对现有的一些多播可扩展性方法进行了改进，提高了方法的效率 和实用性。 1 5 论文结构安排 本文的结构安排如下： 第一章：绪论，分析论文的研究背景；接下来对本文涉及的一些知识和理论 进行介绍；然后，阐述了本论文的研究内容和研究成果；最后简述论文的总体结 构。 第二章：介绍了关于多目标最优化路由算法的基本概念和多目标最优化中各 种解的基本含义。然后重点介绍了求解多目标问题常用的方法。 第三章：提出一种多目标最优化单播q o s 路由算法，以求得到负载均衡的通 路，提高服务质量，减轻网络拥塞。 第四章：在可扩展多播路由的基础上，对现有的一些多播可扩展性方法进行 了改进，提高了方法的效率和实用性。 第五章：总结本文所做的工作。 1 1 电子科技大学硕士学位论文 第二章多目标最优化理论 最优化处理的是在一堆可能的选择中搜索对于某些目标来说是最优解的问 题。如果仅考虑一个目标，就成为单目标优化问题，如果存在的目标超过一个并需 要同时处理，就成为多目标优化问题。多目标优化问题起源于许多实际复杂系统 的设计、建模和规划问题，几乎每个重要的现实生活中的决策问题都要考虑不同 约束的同时处理若干相互冲突的目标，这些问题大大增加了问题的复杂程度。自 2 0 世纪6 0 年代以来，多目标优化问题吸引了越来越多不同背景研究人员的注意力。 早在1 9 世纪末，法国经济学家p a r e t o 就从政治经济学的角度提出了多目标最优化 的思想。本世纪4 0 年代，v o nn e u m a n n 和m o r g e n s t e m 又从对策论的角度提出了 多目标决策问题。5 0 年代初，k o o p m a n s 在生产和分配的活动分析中对多目标优化 问题进行了研究，并引入“p a r e t o 最优”的概念。与此同时，k u h n 和t u c k e r 从数 学规划角度提出向量极值问题，并给出了一些重要的理论结果。6 0 年代，z a d e h 又从控制理论的角度提出多准则问题。进入7 0 年代以后，多目标问题的研究日益 受到人们的重视，在理论的方法上都有了较大发展。目前，多目标最优化仍然是 一个十分活跃的研究领域。遗传算法作为解决多目标优化问题的新方法受到了广 泛的关注，这导致了一类新的研究和应用，称作遗传多目标优化。 2 1 基本概念 多目标数学最优化问题可以写成如下标准形式 y m i n f ，l ，丘 ) 】7 ( 2 - 1 ) g f ) 0i = 1 ，m 其中x ；k ，x j 7 e r “，p 22 。符号v r a i n 表示对向量形式的p 个目标 【，1 ) ，凡 ) 】7 求最小，以区别于单目标问题。为方便起见，记 f ) 垒【，l ) ，厶o ) r d a = x l g ； ) 芑o ，i = l ， ( 2 2 ) ( 2 3 ) 第二章多目标最优化理论 则得到多目标最优化模型的向量形式： v m i n f ( x ) 1 x d 2 2 多目标最优化问题各种解的定义 ( 2 4 ) 由于含有多个目标函数，而这些目标函数之间又往往相互冲突，从而使得多 目标规划问题最优解的概念比单目标规划问题要复杂得多。下面考虑多目标最优 化问题在各种意义下解的定义。 定义1 设孑d = 缸l g 。0 ) o ，i = 1 ，) ，若对任意的x d 均有 ，( x ) 2 ，( i ) j = 1 ，p ( 2 5 ) 则称i 为最优化问题的绝对最优解。 对于多目标最优化问题的解，绝对意义的最优解实际并不存在，因此有必要 对多目标最优化问题的解给出新的定义。为此，首先就向量不等式的符号作一些 约定。设 f 1 = u j ，f j ，f ：f r p ， f 2 = i f ：，f ；，一，f ：y r p ( 1 ) “ ” f 1cf 2 当且仅当疗c 疗对所有，= 1 ，2 ，p 成立，即f 1 的每个分量都严格小 于f 2 的相应分量。 ( 2 ) “三” f 1 兰f 2 当且仅当疗疗对所有，= 1 ，2 ，p 成立，即f 1 的每个分量都 小于或等于f 2 的相应分量。 ( 3 ) “” f 1 f 2 当且仅当f 1 三f 2 但f 1 f 2 ，也就是说，1 的每个分量都小于或等 电子科技大学硕士学位论文 于f 2 的相应分量，而且至少有一个f 1 的分量严格小于f 2 的相应分量。 定义2 设i d ，若不存在x d ，使得 f ) g f ) 则称i 是多目标最优化问题的有效解( 或称为非劣解，m a r e t o 解) 。 由此定义可知，对于有效解i 来说，在“”意义下不可能找到另一个使向量 目标函数f 的值进步改进的可行解。 定义3 设i d ，若不存在z d ，使得 f ) c f 何) ， 则称i 为多目标最优化问题的弱有效解( 或称弱非劣解弱p a r e t o 解) 。 由此定义可知，对于弱有效解i 来说，在“ ”意义下不可能找到另一个使向 量目标函数f 的值进一步改进的可行解。 2 3 多目标规划问题的求解途径 通过前面讲讨论可知，多目标最优化问题的绝对最优解一般并不存在，于是， 在处理问题时，不得不考虑在“”或“ ”意义下能进行比较可行解。d 中的非 有效解( 也称为劣解) 在一般情况下显然应该被淘汰，因为根据定义2 可知，对 于非有效解来说，总可能找到另一个可行解，在“”意义下将向量目标函数f 的值进一步改进。至于非弱有效解更是不可取，因为由定义3 可知，对非弱有效 解来说，总存在另一个可行解，在“ ”意义下使向量目标函数f 的值进一步改进。 因此，一般情况下应考虑选择有效解( 或者弱有效解) 。 有效解的个数往往不止一个，甚至有无穷多个。而对于一个决策问题来说， 最终需要提供的解只是一个，因此，必须在所有的有效解中选择一个，选出的解 称为最佳调和解( 或称选用解，选好解) 。 但是，由于含有向量目标函数，多目标规划的可行解集合不是完全有序集， 在d 上只能定义偏序关系，于是在多个有效解之间无法直接再作