（运筹学与控制论专业论文）基于遗传算法的qos组播路由研究.pdf

东北大学硕士学位论文 摘要 基于遗传算法的o o s 组播路由研究 摘要 i n t e r a c t 的高速发展和多媒体技术日益广泛的应用给路由算法提出了更多的 挑战和越来越高的要求。各类应用程序需要不同的q o s 保证，但各q o s 目标往 往是相关联或相矛盾的，增加了路由优化的复杂性。同时，非精确的网络状态信 息也会影响路由算法的性能。因此研究优化多个目标和能处理网络非精确状态信 息的路由算法成为路由算法研究的核心问题之一。 本文共分五部分。第一部分介绍了q o s 组播路由的背景。第二部分对路由 算法进行了分类，主要分析了单播和组播路由，弗总结了相关的经典算法，给组 播路由研究提供了比较好的理论基础。第三部分提出了基于遗传算法的维播路由 多目标优化算法，在遗传进化过程中分别使用了四种方法：适应性权重方法利用 神群中的有用信息调整权重，加快算法收敛速度：随机权重方法随机生成权重， 使算法具有可变搜索方向，沿p a r e t o 前沿面均匀采样，增加算法成功率；p a r e t o 排序方法合理分配适应值，使p a r e t o 解具有相同的适应值，并能调整选择压力； p a r e t o 竞争方法通过适应值共享维持种群多样性，提高遗传算法的性能。第四部 分提出基于遗传算法的含非精确网络信息的路由算法，通过概率选路使算法能处 理网络中的非精确路由信息，并设计了新的交叉变异算子，增大算法收敛速度和 成功率。第五部分对全文进行总结，并指出了今后q o s 组播路由研究的方向。 本文对提出的算法进行了实验仿真，在不同网络规模下研究了算法的遗传进 化过程、成功率、收敛速度和可扩展性，并与相关算法进行了比较。多次实验证 明，本文提出的算法是可行的、有效的。 关键词：组播路由；遗传算法；服务质量；多目标优化；p a r e t o 最优解；非精确 信息 垒! ! 垄兰堡主兰堡笙墨 竺! ! 翌璺 r e s e a r c ho nq o sm u l t i c a s t r o u t i n g b a s e do ng e n e t i c a l g o r i t h m a b s t r a c t t h er a p i dd e v e l o p m e n to fi n t e m e ta n dt h ew i d e l yu s e d a p p l i c a t i o n so f m u l t i m e d i at e c h n o l o g i e sb r i n gm o r ea n dm o r ec h a l l e n g e st or o u t i n ga l g o r i t h m sa n d n e e dm o r ea n dm o r es t r i c tr e q u i r e m e n t s d i f f e r e n tk i n d so fa p p l i c a t i o n sn e e dd i f f e r e n t q o sg u a r a n t e e s ，a n dt h e r em a yb es o m er e l a t i o n s h i po re v e nc o n t r a d i c t i o nb e t w e e n q o so b j e c t i v e s ，a l lo ft h e s ei n c r e a s et h ec o m p l e x i t yo fr o u t i n go p t i m i z a t i o n i n a d d i t i o n ，t h ei n a c c u r a c yo fn e t w o r ks t a t ei n f o r m a t i o nw i l lh a v eu n e x p e c t e di m p a c to n t h ep e r f o r m a n c eo fr o u t i n ga l g o r i t h m s t h e r e f o r et h er e s e a r c h e so nr o u t i n ga l g o r i t h m t h a tc a no p t i m i z eo n eo rm o r eo b j e c t i v e ss i m u l t a n e o u s l yo rc a nd e a lw i t ht h e u n c e r t a i nn e t w o r ks t a t ei n f o r m a t i o nb e c o m eas i g n i f i c a n ta s p e c to ft h es t u d yo f r o u t i n ga l g o r i t h m s t h et h e s i si sc o m p o s e do ff i v ep a r t s t h ef l i n tp a r ti n t r o d u c e st h eb a c k g r o u n do f q o sm u l t i c a s tr o u t i n g t h e nt h es e c o n dp a r tc l a s s i f i e st h er o u t i n ga l g o r i t h m s ，m a i n l y a n a l y z e s u n i c a s tm u t i n ga n dm u l t i c a s tr o u t i n g ，s u m m a r i z e sa s s o c i a t e dc l a s s i c a l g o r i t h m s ，a n dp r o v i d e sag o o dt h e o r yf o u n d a t i o no fm u l t i c a s tr o u t i n g i nt h et h i r d p a r t ，m u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m so fq o sm u l t i c a s tr o u t i n ga r ep r o p o s e d ， a n df o u rm e t h o d sa r eu s e di nt h ep r o c e s so fe v o l u t i o n ：t h ea d a p t i v ew e i g h ta p p r o a c h u s e st h eu s e f u li n f o r m a t i o ni nt h ec u l t e n tp o p u l a t i o nt or e a d j u s tt h ew e i g h t sa n d i n c r e a s e st h es p e e do fc o n v e r g e n c e t h er a n d o mw e i g h ta p p r o a c hc r e a t e sw e i g h t s r a n d o m l y , m a k e st h ea l g o r i t h ms e a r c hi na l t e r a b l ed i r e c t i o n s ，s a m p l i n g su n i f o r m l y a l o n gp a r e t o o p t i m a lf r o n t ，a n di n c r e a s e st h e s u c c e s sr a t e t h ep a r e t or a n k i n g a p p r o a c ha s s i g n st h ef i t n e s s e si n ar e a s o n a b l ew a y , m a k e st h ep a r e t os o l u t i o nh a v e s a m ef i t n e s s e s ，a n dc a na d j u s tt h ep r e s s u r eo fs e l e c t i o n t h ep a r e t ot o u m a m e n t a p p r o a c hm a i n t a i n st h ed i v e r s i t yo ft h ep o p u l a t i o nb yf i t n e s ss h a r i n g ，a n di m p r o v e s t h ep e r f o r m a n c eo ft h eg e n e t i ca l g o r i t h m i nt h ef o u r t hp a r t ，ag e n e t i ca l g o r i t h mb a s e d n 1 东北大学硕士学位论文a b s t t a c t r o u t i n ga l g o r i t h mi nn e t w o r k sw i t hu n c e r t a i np a r a m e t e r si sp r o p o s e d t h ea l g o r i t h m c a nd e a lw i t ht h ei n a c c u r a t ei n f o r m a t i o ni nn e t w o r k s ，a n dn e wc r o s s o v e ra n dm u t a t i o n o p e r a t o r sa r ed e s i g n e dt oi n c r e a s et h es p e e do fc o n v e r g e n c ea n dt h es u c c e s sr a t e t h e f i f t hp a r ts u m m a r i z e st h et h e s i s ，a n dp o i n t so u tt h ed i r e c t i o no fr e s e a r c ho nq o s m u l t i c a s tr o u t i n gi nt h ef u t u r e t h ep r o c e s so fg e n e t i ce v o l u t i o n ，s u c c e s sr a t e ，s p e e do fc o n v e r g e n c ea n d s c a l a b i l i t yo ft h ea l g o r i t h ma r es t u d i e du n d e rd i f f e r e n tn e t w o r ks i z eb ys i m u l a t i o n s a n dc o m p a r e dw i t ha s s o c i a t e da l g o r i t h m s ag r e a td e a lo fs i m u l a t i o nr e s u l t ss h o wt h a t t h ea l g o r i t h m sw ep r o p o s e da l ef e a s i b l ea n de f f e c t i v e k e yw o r d s ：m u l t i c a s tr o u t i n g ；g e n e t i ca l g o r i t h m ；q o s ( o u a l i t yo fs e r v i c e ) ； 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 ；p a r e t oo p t i m a ls o l u t i o n ；i n a c c u r a t ei n f o r m a t i o n 1 v - 东北大学硕士学位论文 缩略词表 缩略词 b b r b f s b s m a c d k s d i f f s e r v d v m a e b f e d s p f e c i e t f i n t s e r v l d l d p l e r l s p l s r m p c m p l s n p o p o s p f p c p o p n n i q o s o o s d r q o s r q o s s r 缩略词表 英文解释 b y p a s sb a s e dr o u t i n g b r e a d t h f i r s ts e a r c h b o u n d e ds h o r t e s tm u l t i c a s t a l g o r i t h m c o n s t r a i n e dd i j k s t r ah e u r i s t i c d i f f e r e n t i a ls e r v i c e s d e l a yv a r i a t i o nm u l t i c a s ta l g o r i t h m t h ee x t e n d e db e l l m a n f o r da l g o r i t h m t h ee x t e n d e dd i j k s t r a ss h o r t e s tp a t h a l g o r i t h m f o r w a r d i n ge q u i v a l e n c ec l a s s i n t e m e te n g i n e e r i n gt a s kf o r c e i n t e g r a t e ds e r v i c e s l e a s t - d e l a y a l g o r i t h m l a b e ld i s t r i b u t i n np r o t o c o l l a b e le d g er o u t e r l a b e ls w i t c h e dp a t l l l a b e ls w i t c h i n gr o u t e r m u l t i - p a t h c o n s t r a i n e dm u t i n g m u l t i p r o t o c o ll a b e ls w i t c h i n g n o n d e t e r m i n i s t i cp o l y n o m i a l o p t i m a lp a r t i t i o n o p e ns h o r t e s tp a t hf i r s t p a t h - c o n s t r a i n e dp a t h - o p t i m i z a t i o nm u t i n g p r i v a t en e t w o r k - n e t w o r ki n t e r r a c e q u a l i t yo fs e r v i c e q o sd a t ar o u t i n g q o s - b a s e dr o u t i n g o o ss e r v i c er o u t i n g 中文解释 基于旁路路由 广度优先搜索 受限最短路组播算法 约束d i j k s t r a 启发式算法 区分服务 时延抖动组播算法 扩展b e l l m a n f o r d 算法 扩展d i j k s t r a 最短路算法 转发等价类 i n t e m e t 工程特别工作组 综合服务 最小时延算法 标记分配协议 标记边缘路由器 标记交换路径 标记交换路由器 多路径约束路由 多协议标签交换 非确定多项式 最优分割 开放最短路径优先协议 路径约束一路径优化路 由 网络一网络专用接口 服务质量 q o s 数据路由 q o s 路由 q o s 服务路由 东北大学硕士学位论文 缩略词表 r i p r o u t i n gi n f o r m a t i o np r o t o c o l r s v pr e s o u r c er e s e r v a t i o np r o t o c o l r t pr e a l - t i m et r a n s p o r tp r o t o c o l s a m c r as e l f - a d a p t i v em u l t i p l ec o n s t r a i n t sr o u t i n g a l g o r i t h m t a m c r at u n a b l ea c c u r a c ym u l t i p l e c o n s t r a i n t s r o u t i n ga l g o r i t h m w f qw e i g h t e df a i rq u e u e i n g 路由信息协议 资源预留协议 实时传送协议 自适应多约束路由算法 可调精确度多约束路由 算法 加权公平队列 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表 或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了 明确的说明并表示谢意。 学位论文作者签名：a 1f 辛 日期：州；，1 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着高速网络技术和多媒体技术的飞速发展，人们提出了越来越多的包括多 媒体通信在内的综合服务要求。传统的分组交换网络，如i n t e m e t ，是面向非实 时的数据通信而设计的，采用的t c p i p 协议主要是为了优化整个网络的数据吞 吐量并保证数据通信的可靠性，传输时延不是关键。而当今分布式多媒体应用， 如视频会议、视频点播、i p 可视电话、远程教育、虚拟现实等，不仅包括文本 数据信息，还包括语音、图形、图像、视频、动画等多媒体信息。这些多媒体应 用不但对网络有很高的带宽要求，而且要求信息传输的低延迟和低抖动等指标， 但大都能容忍一定程度的信息丢失和错误。这就对网络提出了不同于数据应用的 服务质量要求，需要提供端到端的q o s 控制和保证。 在传统的t c p i p 协议的尽最大努力( b e s t - e f f o r t ) 转发机制中，网络层不区分 业务，尽管i p v 4 的分组包头中设计了指明优先级和服务类型的字段，但在路由 器选择路由和处理分组时往往被忽略，不加以处理，雨将网络资源公平地提供给 各类业务，在分组丢失和时延等方面公平地处理各类业务。这种服务易受分组丢 失、分组重复、路由器缓冲区队列延迟等的影响，缺少必要的q o s 控制和保证； 信息传输控制一般不依赖于网络状态，带宽分配可以动态地改变，但需要流控制； 典型应用包括文件传输旧r p ) 和e - m a i l 传输。而多媒体应用至少含有三方面的不 同：设备容量、网络连接性和用户需求。这不是“尽力而为”服务所能提供的， 它已不能满足当今各种网络应用的需要。由此，以提高网络资源利用率、为用户 提供更高服务质量为目标的q o s 控制技术应运而生，并且已经成为下一代网络 的核心技术之一。 为了使多媒体应用程序在网络上得到广泛应用，一种方法是研究开发新的网 络协议，如i p v 6 、r s v p ( 资源预留协议) 、m y ( 实时传送协议) ；然而最根本的方 法是改造路由器，使其具有处理q o s 请求的功能。由于路由算法直接关系到网 络性能，q o s 路由成为解决q o s 问题的一项关键技术。i n t e m e t 工程特别工作组 i e t f 在这方面作了大量工作，设计了新的面向服务质量的网络体系结构以支持 东北大学硕士学位论文 第一章绪论 实时q o s ，先后提出综合服务资源预留模型( i n c s e r v 瓜s v p ) 、区分服务模型 ( d i f f s e n ，) 以及多协议标签交换( m p l s ) 。q o s 路由在这些网络体系中的应用是当 前计算机网络研究的一个热点问题。 1 2o o s 路由研究现状 m ，r f 提出的n t s e r v 体系结构在文献 2 中给出，将其框架划分为综合服务模 型和参考实现框架两大部分。在服务层次上，除了原来的尽力而为服务外，i n t s e r v 还以每个流为基础，提供了两种端到端的面向实时传输的服务：质量保证服务和 可控负载型服务。i n t s e r v 依靠资源预留协议r s v p 提供q o s 协商机制，逐节点 地建立或拆除每个数据流的路径状态和资源预留软状态( s o ns t a t e ) ；依靠接纳控 匍j ( a d m i s s i o nc o n t r 0 1 ) 决定链路或节点是否有足够的资源满足用户的资源预留请 求；依靠传输控制( t r a m cc o n t r o 驴陌口分组分成不同的传输流，并根据每个流的 状态对分组的传输实施q o s 路由、传输调度( s c h e d u l i n 曲等控制。i n t s e r v 是基于 流的( 单独的或聚集的) 状态相关的体系结构，依赖于每个流( f l a w ) 的状态和对每 个流的管理。这种实现机制一方面是i n t s e r v 能够提供较状态无关的体系结构， 具有更高的灵活性和更好的服务级别保证服务，但同时也导致了i n t s e r v 的可扩 展性问题和鲁棒性问题，后果是实现复杂，难以应用。另外，i n t s e r v 的实现必 须依赖r s v p ，而目前只有少量的主机产生r s v p 信令，虽然其数量预计会大幅 度增长，但许多应用却从不产生r s v p 信令，这也更增大了实现的难度。 区分服务体系结构d i f f s e r v 是在i n t s e r v 发展遭遇巨大障碍时产生的，其目 标在于简单有效，以满足实际应用对可扩展性的要求，实现途径是： n ) 简化网络内部节点的服务机制。在内部节点只进行简单的调度转发，而 流状态信息的保存与流监控机制的实现等只在边界节点进行，内部节点是状态无 关的。 ( 简化网络内部节点的服务对象。采用聚集传输控制，服务对象是流聚集 f s t r e a ma g g r e g a t e ) 觥n ，单流信息只在网络边界保存和处理p 1 。 具体而言，边界节点根据用户的流规定( p m f i l e ) 和资源预留信息将进入网络 的单流分类、整形、聚合为不同的流聚集，这种聚集信息存储在每个i p 包头的 d s ( d i f f e r e n t i a t e ds e r v i c e s ) j 际记域e l d ) 中，称为d s 标记, ( d i f f e r e n t i a t e d s e r v i c e s 东北大学硕士学位论文 第一章绪论 c o d e p o i n t ，d s c p ) ；内部节点在调度转发i p 包时根据包头的d s c p 选择特定质量 的调度转发服务，其外特性称为逐点行为( p e r - b o p - b e h a v i o r , p h b ) 。网络边界对单 流作分类聚合，网络内部对聚集流提供特定质量的调度转发服务，这两个过程通 过i p 包头内的d s c p 协同起来。 d i f f s e r v 提供的是相对粗糙的q o s 划分，没有处理单个流( p e r - f l o w ) 的复杂 性，有很好的可扩展性。但是d i f f s e r v 注重的是如何划分业务量和快速传输，它 运行的仍然是传统的尽最大努力服务的路由算法，不能保证端到端的q o s 需求。 r f c 3 0 3 1 2 e l 定义了m p l s 多协议标签交换体系。m p l s 是对第二层a t m 标 记交换和第三层路由选择的有机结合，工作在网络层和数据链路层之间i z 3 。 m p l s 既实现了a t m 的面向连接、简单高速交换、q o s 保证、流量管理、流量 工程，又实现了i p 的灵活性、有效性和可扩展性等优点。 m p l s 分离了传统选路的“控制”和“转发”两个部分的功能。m p l s 域中 标记边缘路由器l e r 将进入m p l s 域的分组进行快速分类，并映射到转发等价 类f e c 。核心标记交换路由器l s r ，能迅速处理分组上的标记，并对已打上标 记的分组进行快速转发。从f e c 得到的标记通过标记分配协议l d p 在m p l s 网 络中建立条标记交换路径l s p 。打上标记的分组就沿着路径l s p 传送。与a t m p v p v c 一样，标记只具有本地意义，多个标记可以嵌套构成标记栈，可以实现 现实路由和层次化路由。由于使用基于标记的转发，不仅省去了每到个节点都 要到第三层查找路由表的过程，使分组转发的速率大大加快，而且还能使网络上 的通信量负载更加平衡。 如何将q o s 路n b ( q o s b a s e dr o u t i n g ，q o s r ) 应用到d i f f s e r v 和m p l s 等体系 结构也是一个热门的研究领域。为了更好地保证服务质量，最近又提出了一种新 的路由机制，称为q o s 服务路由( q o ss e r v i c er o u t i n g ，q o s s r ) 。这样，传统的 q o s 路由被归类为q o s 数据路e h ( q o s d a t ar o u t i n g ，q o s d r ) 。 q o s s r 主要基于以下两个假设： ( 1 ) 大多数多媒体服务由一些更小的子服务组成，即服务是可组合的。这样， 可以按一定顺序依次应用多个服务来完成传送一个复杂服务的目的f 4 1 ： 多媒体服务可以由网络的某个特定的地点提供。这样就可以在网络的一 东北大学硕士学位论文 第一章绪论 些特定的地点设置代理，每个代理都有自己的容量和带宽限制，从而构造一个覆 盖多媒体服务的代理服务网络。于是问题就变成寻找一条路径，这条路径包含按 一定顺序排列的所有必须的服务。 文献【5 】提出了q o s s r 的关键步骤：( 1 ) 详述服务需求：( 2 ) 构造覆盖代理网 络；( 3 ) 将服务需求映射到代理网络；( 4 ) 设计路由算法。 q o s s r 不同于q o s d r ，q o s d r 主要描述网络层的q o s 路由，而q o s s r 则 工作在应用层，是服务传送网络( s e r v i c ed e l i v e r yn e t w o r k ，s d m 的重要组件。二 者都能被应用到i e t f 提出韵i n t s e r v 、d i f f s e r v 、m p l s 等网络体系结构中。 q o s d r 是本文研究的主要问题，其详细研究情况将在第二章给出。 1 30 0 s 路由研究面临的问题 q o s 路由的主要目标有： n ) 动态选择可行路径，为每个可按受的q o s 业务流提供服务质量保证。q o s 路由能从多个可能的选择中，选出最可能满足数据流需求的路径。 f 2 ) 最优化全局资源利用率。q o s 路由策略通过增大网络吞吐量，有效提高 网络资源利用率，这也是网络优化管理的基本目的。 ( 3 ) 对性能影响尽量小。在网络负载过重等情况下，路由算法应有较强的鲁 棒性保证网络的怠好性能，提供较高的吞吐量。 当前i n t e m e t 路由协议，如o s p f 、r i p ，都使用最短路径路由，只优化一个 度量，如时延或跳数。这些路由协议使用当前的最短路径发送数据到目的地，被 称为“机会主义”路由协议哪。而那些具有可接受但非最优代价的可选路径却不 能用来传输通信业务。q o s 路由必须从三个基本方面改进当前的路由模式： ( 1 ) 为了使用综合服务业务支持通信传输，必须能计算节点对之间的多条路 由。这里的综合服务( i n t e g r a t e ds e r v i c e s ，i s ) 在文献【2 】中定义，包括最大努力服 务，实时服务和控制链路共享服务。 ( 2 ) 在当前的机会主义路由协议工作模式下，即使原来的路径满足当前业务 的服务需求，一旦找至4 更好的路径，通信业务就改变传输路径，在新的当前最优 路径上传输业务。如果路由算法的计算与网络资源( 如可用带宽) 之问有很大联 系，则当网络状态变化比较频繁时，传输路由就会产生很大的振动，在可选路径 东北走学硕士学位论文 第一章绪论 之间来回变换。另外，这样也会增大终端用户之间的时延抖动。 ( 3 ) 当前最优路径路由算法不支持可选路由，如果最优路径不能满足一个数 据流的传输要求，即使存在一条更合适的路径，算法也不会选择这条路径来传输。 因此o o s 路由算法的设计是一个很复杂的问题，一个有效的o o s 路由算法 必须考虑诸多因素，具体体现在以下几个方面： ( 1 ) 算法的复杂度。复杂度涉及到解决一个问题或执行个算法所需的最少 资源，包括时间复杂度和空间复杂度。时间复杂度是q o s r 首先要面对的最重要 问题。由于多约束o o s 路由问题具有n p 性质，传统的最优算法无法在多项式时 间内求得最优解，其时间复杂度往往随问题规模的增加而以指数速度增加，因此 解决q o s 路由问题多用启发式算法。启发式算法是一种技术，这种技术使得在 可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优 性，甚至在多数情况下，无法阐述所得解同最优解的近似程度”j 。在获得解的最 优程度和计算时间、占用空间之间有一个权衡，目的是要花费尽量少的时间和空 间获得尽量优的解。 ( 2 1 算法的可扩展性。现有的路由算法大多不具备很好的可扩展性，计算时 间往往随着网络规模的增大而以指数速度增加，不能应用到实际的大规模网络 中。通过网络状态聚集能够以对数缩减信息量，相应的分层路由可以通过限制每 层内节点的数量使用源路由方式，从而很好地解决可扩展性问题。但这同时又引 入了新的问题：如何聚集状态信息、如何基于聚集状态设计良好的启发式算法。 目前所设计的状态信息聚集方法会丢失大量可用信息，严重影响了q o s r 算法的 性能；同时，所设计的启发式算法也往往是基于全局状态源路由策略的。此外， 由于很多o o s 问题的精确求解复杂度都是n p c 的，因此需要设计快速、有效的 启发式算法。 f 3 ) 非精确路由信息问题。网络状态的不断变化、网络的分层体系结构和网 络信息聚合都会导致路由信息的非精确性。非精确路由信息可能会使路由选择失 败，重新进行路由计算和发送预约信令，从而增大网络开销和业务时延。分布式 路由中，不准确的路由信息还可能导致环路。一种解决方案是合理设计路由信息 更新方法。路由信息的更新直接关系到每个节点保留信息的准确性。信息更新越 频繁，节点获得的信息准确性越高，但同时引入的信息开销也越大。合理的路由 东北大学硕士学位论文 第一章绪论 信息更新策略能够有效均衡信息准确性与路由开销，同时也可以为路由算法性能 与算法可实现性找到合适的折中点 1 1 , 1 2 1 。另外一种方法是概率模型求解。按照度 量参数取值的概率选择一条具有最大可能性的路径，可以克服信息不准确性为选 路带来的影响1 9 1 。 ( 4 ) q o s 路由与尽最大努力服务路由的共存问题。文献 1 4 】对这个问题进行 了讨论。将q o s r 融入到当前这种尽力发送的路由体系结构中，原有的尽力发送 业务将受到巨大冲击。今后的网络应该是q o s r 和尽力发送相结合的【1 6 】。网络 的路由目标是最大化资源效用，这包括尽可能地接纳更多的q o s 连接请求，同 时最大化尽力发送业务的吞吐量和相应速度。由于这两者是矛盾的，因此二者融 入的过程会产生很多问题。例如，在有资源预留的链路空闲时，没有资源预留的 链路却可能由于尽力发送业务而造成拥塞。这种拥塞的链路仍然有可能因为尚未 预留资源而接受q o s 请求。此外，q o s r 算法必须与其他网络组件结合才能提供 q o s 保证，包括状态收集、资源预留、分组调度等，因此可以考虑这种结合过程 对q o s r 算法和其他网络组件的简化。 ( 5 ) 多路路由与重路由。多路路由有两种解释：第一，在多条可能的路径上 同时探测可行路径，如何与资源预留相结合尚无定论1 2 0 】。第二，网络提供多条 从源到目的的路径，并将这些路径并行复用起来( 如增加带宽) 而对用户业务透 明，这是一种多路复用的路由方式。然而，其主要问题是多条路径之间如何同步， 以及如何避免分组的延迟抖动、乱序等【2 1 l 。由于网络资源和可行路径分配的不 合理，因而在某些情况下需要重新路由。重路由在网络资源不足时进行，能够有 效地重新分配网络资源，但由于存在状态保存、同步和开销等问题，使重路由变 得困难。 ( 6 ) 算法实现问题。假定我们已经解决了算法的复杂度问题，仍然有两点需 要考虑：第一，不同的通信业务有不同的度量，所以路由器对每一个新接入的通 信业务必须能应用相应的算法；第二，大多数的路由算法都假定在计算之前已经 获得了足够的路由信息，即假定路由协议已经获得了这些信息。但在实际时络中， 对多约束路由，频繁的在网络中传输多个度量的路由信息将会极大地增加网络负 荷。 东北大学硕士学位论文 第一章绪论 1 4 本文的主要工作 本文所做的主要工作有： ( 1 ) 讨论q o s 路由技术的发展背景，归纳和分析当前q o s 路由算法研究和 面临的情况，指明了其中一些有待进一步研究的问题； ( 2 1 将适应性权重方法、随机权重方法、p a r e t o 排序方法和p a r e t o 竞争方法 与遗传算法结合，解决q o s 组播路由多目标优化问题，处理一个或多个q o s 约 束条件。利用四种算法各自的优点加快算法的收敛速度，提高算法成功率。在遗 传进化的每一代，搜索组播路由树的p a r e t o 解集，通过不断更新这个解集，最终 获得满足约束条件的多个非支配组播路由树，各路由树都有其较优的一面，用户 可根据需要选择自己满意的路由； ( 3 ) 提出基于遗传算法的带不确定参数网络的路由算法，并设计了新的交叉 变异算子处理非精确信息路由问题。 1 5 本文的主要结构 本文的具体内容安排如下： 第一章介绍了q o s 组播路由问题的研究背景、研究现状和面临的问题，列 出了本文的主要研究内容和组织结构。 第二章给出q o s 路由的网络模型和q o s 度量的定义，对q o s 路由问题进行 了分类，主要分析了单播和组播路由，总结了相关的经典算法，为本文q o s 组 播路由算法的研究奠定了基础。 第三章提出了分别基于适应性权重方法、随机权重方法、p a r e t o 排序方法和 p a r e t o 竞争方法的四种遗传算法，解决多目标优化问题。给出了各算法的详细实 现步骤，对算法进行了复杂度分析，并通过实验仿真实现了算法，验证了算法获 得最优解的成功率、收敛速度、可扩展性等性能指标。 第四章针对网络中含有非精确信息的问题，提出了一种能处理非精确网络信 息的遗传算法，设计了新的交叉变异算子，解决时延带宽约束组播路由问题，同 时优化代价和剩余带宽利用率。 第五章对论文的研究工作进行总结，并提出进一步的研究内容和方向。 东北大学硕士学位论文 第二章o o s 路由算法研究综述 2 1 网络模型 第二章( ；l o s 路由算法 网络由交换节点、链路和主机组成，在路由算法研究中将其抽象为有权图 g ，e ) 。下面介绍一些相关的概念 1 7 , 2 7 l 。 定义2 1 1 有向图有向图g 是由一个非空有限集合矿和其中某些元素的有 序对集合构成的二元组，记为g = ，e ) ，其中v 称为图g 的节点集，矿中元 素p 称为图g 的一个顶点或节点；e 称为图g 的边集，e 中每个元素与y 中两 个元素u ，匕关联，记为e 以，v ，) ，为矿中元素的有序对，称为图g 的一条从b 到v ，的边( 弧) 。m 表示节点数，吲表示链路数。 定义2 1 2 邻接节点关联于同一条边的两个节点称为邻接节点。 定义2 1 3 环环是指一条除了第一个顶点和最后一个顶点相同外其余顶点 均不相同的链路。 定义2 1 4 度一个节点v 的度是指节点v 的邻接节点的个数。 定义2 1 5 有权图在有权图g 一，e ) 中，令元素e e e 具有一组有序数组 ( m ，w 2 ，) 作为e 的属性，则称g 为有权图，其中( w 1 ，心) 称为弧e 的度 量( 权值) 。 定义2 1 6 路径在图g 中，如果对i = 1 ，2 ，七一1 有e 化，h + ，) e ，则 p 一( v l ，v 2 ，k ) 为图g 的一条从v 1 到h 的路径。 定义2 1 7 对称网络在网络g ，e ) 中取任意链路 ，y ) ，对于链路的所有属 性有w ；似，v ) t w 。( v ，“) ，i t l 2 ，l ，l 则称该网络为对称网络。 定义2 1 8 非对称网络在网络g ，e ) 中，如果存在一条链路 ，v ) 满足对至 少一个1s fs m 有w j ，v ) ，w ；( v ，醒) ，则称该网络为非对称网络。 网络为有向图g ，e ) ，其中矿是一组节点集，代表网络中的交换机、路由 r 一 东北大学硕士学位论文 第二章q o s 路由算法研究综述 器和主机，e 代表连接这些节点的链路集。e 中的边只有当通信链路对称时才是 无向的。对称链路在两个方向上都有相同的属性( 如容量、传播时延等) 和相同的 通信量。对大多数实际网络来说，通信链路并不对称，因此每条链路都由方向相 反的两条有向边表示。网络中每个节点也有自己的状态，并可以独立度量。本文 将节点状态组合到其邻接边上进行处理。这样，剩余带宽指最小链路带宽和c p u 带宽，其中c p u 带宽定义为节点将数据发送到链路的最大速率；链路时延指链 路的传播时延与数据在节点的排队时延之和；链路代价指发送数据占用的链路和 节点的资源总和。如图2 1 是一个网络图，链路状态由带宽、时延和代价三元组 构成。 链蹋歌惫= t 带懿，州延，代价) 2 2q o s 路由 图2 1 网络状态 f i g 2 1n e t w o r ks t a t e q o s 即服务质量( q u a l n yo f s e r v i c e ) ，有多种定义。q o s 论坛给出的定义为： 服务质量是一个网络元素保证其通信量和服务需求获得满足的能力。 r f c 2 2 1 6 t 2 4 1 定义为：用带宽、分组延迟和分组丢失率等参数描述的关于分组传 输的质量。r f c 2 3 8 6 t 1 1 的定义为：服务质量( q o s ) 是网络在传输业务流时，业务 东北大学硕士学位论文 第二章q o s 路由算法研究综述 流对网络服务的需求的集合，其中业务流是指与特定q o s 相关的从源到目的地 的分组流。 q o s 需求要通过可测量的q o s 度量来实现。常见的几种q o s 度量主要包括 可用带宽、端到端延迟、分组丢失率、抖动和花费，不同的度量具有不同的性质。 按照这些性质，q o s 度量可以分为可加性度量、可乘性度量和最大最小性度量三 类。对于图g 中的路径p = ( ，k ，“，v ) ，( ”， 1 7 ) 表示链路( ，v ) 的第i 个度量， 整个路径尸的第f 个属性记为( p ) ，则以上三类度量的定义如下： 定义2 2 1 可加性度量若w f ( p ) = m ( - ，七) + w j ( t ，f ) 十+ ( “，则称路径p 的第f 个属性为可加性度量。 可加性度量包括延迟、抖动、花费、转发跳数( h o pc o u n t ) 等。例如，一条路 径p 的延迟为从源到目的地的所有链路延迟的总和。如图2 1 中路径0 ，b ，d ，f ，f ) 的延迟总和为1 1 ，代价和为2 0 。 定义2 2 2 可乘性度量若( p ) = ( ，i ) w f ( a ，) “( “，v ) ，则称路径p 的第i 个属性为可乘性度量。 例如，分组丢失率为可乘性度量，其中链路丢失率0 ( m ，v ) t 。在求解有 关可乘性度量问题时，可取其对数将其化为可加性度量。 定义2 2 3 最大最小性度量若m ( p ) = m 埘( ，t ) ，心( 七，耽，w f ( 甜，v ) 】或 w ( p ) = m a x w ，( j ，哥) ，心( j | ，) ，w i ( 甜，v ) 】，则称路径p 的第f 个属性为最大最小性 度量。 例如，带宽为最大最小性度量，即路径带宽为路径上瓶颈链路的带宽。如图 2 1 中路径( 口，b ，d ，f ，d 的带宽为2 ，其中( 6 ，d ) ，( i ) 为带宽瓶颈。对于求解 嵋( d = m a x w , ( j ，| ) ，( 七，耽，w j ( 甜，例的问题可转化为求解一嵋( p