（计算机软件与理论专业论文）多目标进化算法在网络qos路由优化中的应用研究.pdf

独创性声明 螂删删f f f | y 18 2 4 8 6 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重迭 由e 电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者弛参父 签字日期：俨了叫月；旧 学位论文版权使用授权书 本学位论文作者完全了解重庞邮电太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重麽查电太堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 童良 毫 导师虢d 1 乒乞 料嗍：r 刖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 路由 通用模型及其形式化描述；以此为基础，设计一种新型多目标进化算法， 着重对该算法的复杂度和算法收敛性展开分析讨论，并通过实例测试来验 证算法的有效性与合理性；然后依据所提算法，研究、探讨在m a n e t 网 络环境下的应用，明确其实现细节；最后，通过o p n e t 仿真平台对所提 算法进行多角度实验验证和性能评估，并得到结论：论文所提算法较相关 同类算法在求解时间与求解质量两方面均占优。 通过以上研究，论文为宽带网络q o s 保障机制及多目标进化理论在工 程实践中的应用探索了一条具有实际参考价值的新途径。 关键词：宽带网络，服务质量，路由，多目标优化，进化算法 a bs t r a c t t h er a p i dd e v e l o p m e n to fw i d e - b a n dn e t w o r kt e c h n i q u et h a tm a k e st h e g r o w t h o fm u l t i m e d i as e r v i c e sc o n f r o n t s ag r e a to fo p p o r t u n l t l e sa n d c h a l l e n g e s r e c e n t l y ，t h es u r v e yi n d i c a t e dt h a t t h er a t i oo fm u l t i m e d i at r a f f i c w a si n c r e a s i n g ；t h es t r e a m i n gm e d i ab e c a m eaf a s td e v e l o p i n ga n df i e r c e l y c o m p e t i n gf i e l d a so n eo ft h em o s ti m p o r t a n ti s s u e so fw i d e b a n dn e t w o r k t e c h n i q u e ，q o s ( q u a l i t yo fs e r v i c e ) r o u t i n gh a sd r a w n al o to fa t t e n t i o n ，a n d i th a sb e c o m i n gar e s e a r c hf o c u sa tp r e s e n t h o w e r v e r t h et r a d i t i o n a lb e s t e f 如r tr o u t i n gs c h e m eo n l yc o n c e r n sa b o u t t h em e a np e r f o r m a n c eo ft h ee n t i r en e t w o r k ，e a c hf l o ws h a r et h e r e s o u r c e e qu a ny ，a n dt h ep r o t o c o lh a sn o td e n n i t et h eq o s t h e r e f b r e ，i ti ss i g n i n c a n t i nt h e o r ya n dr e a l i t yt o s e tu pa ne f n c i e n tq o sm e c h a n i s mf o r d i f 诧r e n t s e r v i c e s t h ep a p e rt a k e sa d v a n t a g eo ft h ev i e w p o i n tc a l l e d “g e n e r a lt op a t i c u l a r ” t od i s c u s st h ep r o p o s e dm e t h o dt h a th o wt oa p p l yi t i n t ot h er e a ln e t w o r k s f i r s t ly t h el a t e s tq o sr o u t i n ga l g o r i t h m sa r es u m m a r i z e da n da n a l y z e d t h e n aq o sr o u t i n gm o d e li sg i v e na c c o r d i n gt ot h ea p p l i c a t i o n s r e q u i r e m e n t s o n t h eb a s i so fa b o v es t u d i e s ，an o v e lm u l t i o b j e c t i v ee v o l u t i o n a r ya l g o r i t h mf o r q o sr o u t i n gi sp r o p o s e d ，b o t ho f t h em a i n t a n c eo fp o p u l a t i o n s d i v e r s i t ya n d c o n v e r g e n c eo ft h ea l g o r i t h ma r ea l s os t u d i e d ，a n do n eo ft h es i m p l et e s t i n s t a n c e si sc o n d u c t e dt oa d j u s tt h ep e r f 0 r m a n c eo ft h ep r o p o s e da l g o r i t h m m o r e o v e r ，s o m ed e t a i l so fp r o p o s e dm e t h o dt h a th o wt 0a p p l yt h ep r o p o s e d a l g o r i t h mi n t ot h em a n e t i sg i v e n f i n a l l y ，t h ep r o p o s e dm e t h o di sv e r i f i e d ， a n di t sp e r f o r m a n c ei se v a l u a t e db yt h eo p n e t t h es i m u l a t i o nr e s u l t ss h o w t h a tt h ep r o p o s e dm e t h o di sm o r ep r e f e r a b l ei nb o t ho fr u n n i n gt i m ea n dt h e q u a l i t yo ft h es o l u t i o nc o n l p a r e dw i t ho t h e ra l g o r i t h m s a c c o r d i n gt ot h i ss t u d y ，t h ep a p e re x p l o r e san e ww a y f 0 rq o sr o u t i n gi n w i d e b a n dn e t w o r ka n da p p l i c a t i o no fm u l i t i - o b je c t i v ee v l o t i o n a r ya l g o r i t h m k e y w o r d s ： w i d e b a n dn e t w o r k ， q u a l i t y o fs e r v i c e ， r o u t i n g ， m u l t i o b je c t i v eo p t i m i z a t i o n ，e v o l u t i o n a r ya l g o r i t h m i i 重庆邮电大学硕士论文目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景1 1 2 研究现状2 1 3 论文研究内容与意义5 1 4 论文结构6 第二章q o s 路由机制与模型7 2 1q o s 路由的概念及其关键技术7 2 1 1q o s 路由的概念7 2 1 2q o s 路由状态信息的分类和更新8 2 1 3q o s 路由计算1 0 2 2q o s 路由策略1 6 2 3q o s 路由理论计算模型1 9 2 4 本章小结2 1 第三章基于多q o s 参数的一种新型多目标进化算法2 2 3 1 多目标进化算法简介2 2 3 2 基于多q o s 参数的多目标进化算法设计2 3 3 2 1 编码2 4 3 2 2 适应度计算2 5 3 2 3 多样性保持策略2 5 3 2 4 算子设计2 8 3 2 5 算法实现3 0 3 3 算法分析3 0 3 3 1 复杂度分析3 1 3 3 2 收敛性分析3 1 3 4 算法测试3 3 3 5 本章小结3 5 第四章多目标进化算法在网络q o s 路由中的应用研究3 6 4 1m a n e t 中的实现研究3 6 i 重庆邮电大学硕士论文 目录 4 1 1m a n e t 及其特点3 6 4 1 2 基于q m o e a 的q o s 路由协议设计准则3 8 4 2 基于q m o e a 的m a n e tq o s 路由体系结构3 9 4 3 协议实现4 0 4 3 1 基于q m o e a 的无线链路状态协议4 0 4 3 2 改进的核心树协议i c b t 4 3 4 3 3 核节点选择4 4 4 4 本章小节4 5 第五章仿真与分析4 6 5 1o p n e t 简介4 6 5 2 仿真与性能评估4 7 5 2 1 实验参数设置4 7 5 2 2 实验仿真结果4 9 5 2 3 性能分析5l 5 3 实验结论5 6 5 4 本章小结5 6 第六章总结与未来工作5 7 6 1 论文总结5 7 6 2 未来的工作5 7 致 谢5 9 攻读硕士学位期间从事的科研工作及发表的论文6 0 参考文献6 l 重庆邮电大学硕十论文第一章绪论 1 1 研究背景 第一章绪论 宽带网络技术的迅猛发展与多媒体应用的快速普及，使网络应用服务 类型与网络用户数量呈爆炸性增长。据2 0 0 9 年1 月第2 3 次中国互联网络 发展状况统计报告【l 】显示，以宽带网络技术为主导的多媒体数据通信在通 信业务总量中的比重迅速上升，流媒体业务正成为多媒体通信业务中发展 最为迅速、竞争最为激烈的领域。与传统业务相比，网络上的视频点播、 可视电话、视频会议、网络协同工作、分布式应用等多媒体数据业务具有 数据量大、数据传输质量敏感性强、持续时间长等特点，这对网络本身提 出了更高的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 要求。然而，现有网络并 不能对用户q o s 需求提供良好的保障机制，以致成为宽带网络技术发展的 主要障碍之一。因此，建立一套高效的q o s 控制机制与策略，为不同类型 的用户或请求提供性能保证和服务区分，这是目前网络服务提供商( i s p ) 所迫切需要解决的问题，也是当前学术界与工业界关注的焦点。 网络q o s 路由是宽带网络技术研究与应用的重要支撑技术，也是多媒 体实时业务应用的重要载体；以q o s 路由技术为应用导向正朝着宽带无线 移动通信领域进一步拓展。新一代移动通信技术i m t - a d v a n c e d 将不仅具 有更高的数据传输率，而且对q o s 控制机制提出了全新的设计要求【2 1 。然 而，传统路由传输模式只关心网络的平均性能，各种数据流在网络中平等 地共享网络带宽资源，并未对服务质量进行规范。随着移动通信技术的发 展与演进，q o s 路由机制设计势必掀起新一轮的研究热潮【3 4 1 。 一般意义下，q o s 是指网络在传输数据流时要求满足的一系列服务请 求，它强调端到端( e n d t o e n d ) 或网络边界到边界的整体性，具体可量 化为带宽、延迟、延迟抖动、丢失率、吞吐量等性能指标；路由则是把信 息从源穿过网络传递到目的的行为，是决定网络传输性能的主要因素之 一。对于单一度量( m e t r i c ) 约束的q o s 路由，可通过修改传统的路由算 法实现，但在实际的实时多媒体业务中往往存在多个约束条件，为使多媒 体业务得到更为广泛的应用，路由协议需要一个更加复杂的模型来描述网 络特征。此外，对于路由中的转发机制而言，需要使用不同于传统单播、 广播机制的转发技术及q o s 服务保证机制来实现，组播技术正是解决这些 重庆邮电大学硕士论文第一章绪论 问题的关键。组播技术是一种一台或多台主机发送数据包到多台主机的网 络技术；作为点对多点的通信，它是节省网络带宽等资源和提高传输效率 的有效方法；为了能准确、有效地将信息送到组播组，必须为其事先确定 路由，使信息按所选路由进行传送。 鉴于在高速网络中对用户提供q o s 保证的需求已极为普遍，现有组播 路由机制已成为严重制约网络发展的瓶颈因素，国内外研究机构相继启动 q o s 路由机制相关研究项目【5 。12 1 ，对宽带网络q o s 组播路由技术展开了积 极的研究和广泛的合作，并获得相当的研究成果。由于宽带网络q o s 组播 路由机制研究尚处于探索阶段，其设计既是当前研究的重点，也是难点。 因此，设计合理高效的网络q o s 组播路由机制在当前具有重要的理论价值 与广阔的应用前景。 1 2 研究现状 由于组播技术在宽带网络多媒体应用中的地位日趋上升，更多的专家 学者把眼光投向了网络q o s 组播路由。首先，组播路由算法可根据不同角 度、不同准则来分类，按网络拓扑动态性分为静态路由和动态路由。在静 态组播路由中，组播组成员是固定的，路由计算一次性完成，并且在一次 连接过程中组播成员和路由树均不发生改变；动态组播路由则允许组成员 动态加入或离开，组播树在一次连接中一般会发生改变；按节点运算方式 又可分为集中式和分布式路由。集中式路由是由节点在掌握整个网络的拓 扑结构后，确定组播路由，集中式组播路由算法也称为源路由算法( s o u r c e r o u t i n g ) ，即源节点通过某个链路协议获得完整的网络拓扑信息，进行路 由计算。集中式算法往往简单快速，但需要一个节点来维护整个网络的状 态，其开销较大，并且当网络较大时，搜集整个网络的状态会相对困难。 在分布式算法中，网络的每个节点都参与运算，这些节点只掌握网络的部 分信息，通过节点间相互交换信息来计算路由。分布式算法相对于集中式 算法较复杂且路由信息收敛速度慢，但无须每个节点维护整个网络的状 态。 按照所解决问题，组播路由算法又可以分成十二大类，论文将在第2 章中给予详细介绍。总体来说，目前对静态的组播源路由算法己有大量研 究，而分布式组播路由算法、动态组播路由算法的研究成果较少，且目前 大部分算法的复杂度较高，无法应用于实际网络。 2 重庆邮电大学硕士论文 第章绪论 常规组播源路由算法有最短路径树算法( d i j k s t r a 算法和b e l l m a n f o r d 算法) 和最小生成树算法( p r i m 算法) 。最短路径算法使组播树上从源节 点到目的节点的每条路径上链路权重( 、i 曲t ) 之和最小。如果所有链路 的权重均为1 ，其结果就是最小跳树，如果权重代表链路时延，则结果就 是一棵最小时延树；最小生成树算法采用贪心策略( 在树的增长过程中， 每次选择的边都是使树权重增加最少的边) ，可求碍一棵覆盖所有组成员 且树权重最小的树。s t e i n e r 树问题研究的目标是如何使组播树的整体代价 最小，属于n p 完全问题，无约束s t e i n e r 树问题可以解决组播树优化问题， 但不能解决点对点的约束问题。s a l a m a 等人在文献【13 中对近年来的几种 s t e i n e r 树问题解决方案的性能进行了评估和比较。 分布式算法本身要比集中式算法复杂得多，关于此方面研究也相对较 少。典型的分布式算法有b a u e r 等人提出的s p h 算法和k s p h 算法【1 4 】、 k o m p e l l a 等人提出的d m c t c 算法和d m c t c d 算法【1 6 1 ，这两种算法是他们 提出的k p p 算法 15 】的分布式版本，然而该算法的通信开销很大。文 1 7 】 设计了另一种分布式组播路由算法，能达到近似最优的时延约束组播树。 对以上不同类型的算法还可用不同的方法来计算【3 。2 1 ，但大多求解时 间过长、无法快速适应网络变化。研究人员针对q o s 组播路由问题的复杂 性，引入了一些智能优化算法以寻求最优解。文献 18 2 0 对m a n e t 中 q o s 路由解决方案进行了综述，并指出，利用不同的启发式算法来计算多 q o s 参数约束路由问题中的“最优”路径仍然是未来对该问题研究的重要方 向之一；文献 2 1 】中对遗传算法、模拟退火以及禁忌搜索三种典型的智能 计算方法建立q o s 多播树作出深入的分析与讨论，并以端到端时延和网络 资源需求为约束条件，通过在小规模现实网络及大规模随机网络中的测试 与实验，得到遗传算法性能最优的结论。 从现有研究成果看，虽出现利用蚁群算法【22 1 、粒子群算法【2 ”、量子算 法【2 4 】等新的计算模式来解决网络q o s 组播路由问题，但其一般效果较差， 以遗传进化算法作为计算手段仍然是当前研究该问题的主流。 文献【2 5 2 6 在应用遗传算法之前先通过对数模拟退火( l o g a r i t h m i c s i m u l a t e da n n e a l i n g ) 机制将问题作预处理，并引入部分匹配交叉和精英 保留策略分别作为遗传算法的交叉与选择算子，最终给出算法景观分析 ( l a n d s c a p ea n a l y s i s ) 以估计局部最优解的深度。尽管在大规模随机网络 中的测试结果显示该算法能够找到“最优”路径，但其复杂度较高，算法收 敛速度慢，并不适合拓扑频繁变化的网络。 文献 2 7 从流量工程( t r a 伍ce n g i n e e r i n g ) 的视角对大规模m p l s 覆 重庆邮电大学硕士论文 第一章绪论 盖网中“最优”路由展开研究。利用遗传算法对协议独立稀疏多播模式 ( p r o t o c o li n d e p e n d e n tm u l t i c a s t s p a r s em o d e ，p i m s m ) 下多拓扑结构的 链路权重进行优化，并通过与传统i p 方法对比发现，基于遗传算法的多播 流量工程方法在保证多媒体正常传输的前提下将花费更少的带宽资源。然 而在该文中，仅从一个网络度量参数( 带宽) 去概括全部多媒体应用的需 求的观点是不准确的。文 2 8 也从另一侧面验证了多q o s 参数模型将更加 符合现有网络的流量行为特征。 文 2 9 】与文 3 0 基于“树结构”编码方式提出一种遗传算法，该算法利用 随机点交叉，随机“树成员”变异及精英保留策略分别作为其交叉、变异和 选择算子，并通过在中、小规模的随机网络下的测试验证了算法快速收敛 特性。虽然该算法可在理想时间内找到满足q o s 参数的路径，但其编码解 码过程复杂，交叉和变异等遗传操作受限，算子执行效率低，不能适应网 络拓扑快速的变化。 文 31 】与文 3 2 分别通过引入免疫算子与克隆算子对标准遗传算法进 行改进，对带宽延时受限，费用最小的q o s 组播路由问题进行了研究。改 进后的算法能较好地保持群体多样性，并能在小规模网络中找到一个极为 接近真实最优解的近似解，然而正是由于其解精度细微的提高而导致算法 运行时间增加，牺牲了算法的收敛速度。 文 3 3 】针对多个q o s 度量参数的网络提出一种多目标遗传算法，其算 法中首次引入了p a r e t o 与信息熵的概念，利用个体在群体中的p a r e t o 等级 和个体与个体之间的信息熵之积来确定个体适应度。由于个体信息熵中包 含有个体在解空间的密度函数，因此，适应度的计算方式能很好的将个体 空间中的每个个体区分开来，即算法在迭代过程中能较好地保持群体多样 性。尽管该算法提出了在遗传优化过程中多目标优化问题应作为向量优化 问题处理，但文中方法从本质上来讲，仍将多目标通过系数聚合成单目标 来计算。 异于上述算法的协议工作模式，文 3 4 与文 3 5 】在核心树( c b t ， c o r e - b a s e dt r e e ) 协议下针对无线网络提出了遗传优化算法，算法采用单 点交叉、随机点变异以及精英选择，对大规模网络中的q o s 组播路由提供 了一条全新的思路，但该算法未对其收敛速度慢和群体易“早熟”采取任何 有效的措施，从实验结果看，算法运行需要较长时间而且极易陷入局部最 优。 从上述研究现状可知，在近两年的时间内对这一问题的研究已有相当 的研究成果，提出了不同类型的遗传算法，但大多或多或少存在一些缺陷 4 重庆邮电大学硕士论文第一章绪论 与不足，主要包括将多个不可公度甚至冲突的优化目标聚合成单个目标， 算法运行时间长、收敛速度慢以及群体多样性得不到保证，易“早熟”等。 因此，本文将以上述缺陷为研究的出发点，研究设计出一种全新的多目标 进化算法与网络体系结构，使其更加适合现实多媒体应用需求。 1 3 论文研究内容与意义 论文在以围绕重庆市自然科学基金项目( c s t c ，2 0 0 5 b b 2 0 6 0 ) 支持 4 g 的无线网络资源预分配及优化技术研究，及重庆市自然科学基金计划 重点项目( c s t c ，2 0 0 8 b a 2 0 4 4 ) 宽带无线网络q o s 接入机制与算法研究 为背景下，对网络q o s 组播路由问题展开深入研究。着重围绕将不可公度 的多个参数抽象提取为多目标优化模型、论文基于遗传进化的多目标优化 方法及其应用技术展开了深入的分析与讨论，其主要工作如下： ( 1 ) 分析当前求解q o s 路由方法，指出存在的问题和面临的挑战；并 对现有q o s 路由算法给予分析评价； ( 2 ) 以网络需求为背景，结合网络q o s 具体特征，给出一种网络q o s 路由模型及其形式化描述； ( 3 ) 针对求解q o s 路由方法中存在的不足，提出一种新的多目标进化 算法，并通过对算法简单实例测试，调整完善算法性能； ( 4 ) 依据所提算法，研究探讨在m a n e t 网络环境下的应用场景，描 述其详细实现细节； ( 5 ) 利用o p n e t 仿真平台对所提算法进行多角度实验验证，对实验 结果进行对比、分析和评估。 现有的求解方法在处理多目标优化问题时只是片面强调问题的某一 方面( 比如：费用、时延等) 。而对多个q o s 参数的综合优化研究尚需迸 一步深入，因此如何将不可公度的多目标转化为一个多目标优化模型成为 亟待解决的问题之一；另外，对基于遗传进化的多目标优化方法及其应用 技术在网络环境下进一步展开也是当前的研究热点和难点。本文力争在网 络q o s 路由及智能优化算法应用等问题上探索一条新途径，其研究意义主 要体现在： ( 1 ) 提高网络路由计算速度，实现快速路由和快速适应网络拓扑结 构变化，从而提高网络的效率和整体性能，增加网络健壮性； ( 2 ) 推动后续理论发展，为现有宽带网络中的路由器和高层交换设 重庆邮电大学硕士论文第一章绪论 备的生产制造提供实践参考依据，促进智能算法的在多目标优化领域的进 一步推广应用； ( 3 ) 为下一代宽带无线网络的q o s 路由技术的研究与应用提供重要 的理论基础。 1 4 论文结构 本文共分六章，各章内容安排如下： 第一章，介绍论文研究背景，归纳和分析当前路由算法最新研究成果， 明确论文的研究内容与意义。 第二章，阐述q o s 路由机制及q o s 路由的网络模型和q o s 度量的定 义，总结q o s 路由的典型问题及相关经典算法，为论文q o s 路由算法的 研究工作奠定理论基础。 第三章，设计一种基于多q o s 参数的多目标新进化算法，描述算法的 详细设计过程，着重对进化算法的多样性保持策略和算法收敛性进行讨 论，并通过实例测试来验证算法的有效性与合理性。 第四章，针对m a n e t 网络场景，研究探讨论文所提算法在现实网络 中的应用，给出具体协议实现细节。 第五章，通过配置不同业务，对所提算法进行多角度仿真验证，并对 仿真结果给予分析，评价，得到相应结论。 第六章，总结论文所做工作，并探讨未来进一步的工作设想和研究方 向。 6 重庆邮电大学硕士论文 第二章q o s 路由机制与模型 第二章q o s 路由机制与模型 2 1q o s 路由的概念及其关键技术 正在承载多种业务、服务与多类用户的宽带网络对网络服务质量保障 能力提出了全新的技术要求，由于传统网络所使用的路由机制主要侧重于 网络的连通性，一般只支持尽力而为的服务级别，网络资源分配方式也只 是遵循“公平”地依照先来先服务的机制提供给各类业务应用，且尽力而为 的传送机制是面向无连接的，其性能极易受到当前网络资源状态的影响， 出现网络性能瓶颈，因此无法满足宽带网技术发展要求。同时，目前普遍 使用的路由协议大都采用一维约束参数进行网络路由计算，比如“最短路 径算法”，并没有考虑业务应用或用户的差异性需求。而各种不同属性的 业务流依据同样的路由原则进行转发，使得网络传输无法实现业务的q o s 保证。基于上述问题，在网络技术领域出现了多种q o s 技术，q o s 路由 ( q o sr o u t i n g ) 便是其中颇受研究人员关注的一种技术。q o s 路由技术的 核心思想就是依据网络上可利用的实际资源和业务的q o s 需求参数，采用 多维约束参数进行满足业务q o s 要求的路由选择，这些参数可以是端到端 时延要求、可用带宽、资源占用量、链路利用率以及跳数等q o s 参数。 2 1 1q o s 路由的概念 一般的网络路由过程由两部分组成，一个是依据某种约束参数为到达 的业务分组流选择合适的路由进行数据分组的转发，另一个则是为了维护 结点间的路由转发信息进行的信息交互。q o s 路由同样也是由这样的过程 构成。 q o s 路由的定义 i e t f 在r f c 2 3 8 6 中对q o s 路由进行了如下定义【3 6 】：q o s 路由是一种 能够依据网络可用资源和业务流q o s 需求进行路径计算的路由机制。 由上述i e t f 描述可以看出，相比尽力而为的路由选择模式，q o s 路 由不仅关心网络的连通性，而更关心路由是否能够满足业务所提出的q o s 要求和网络资源的有效配置。q o s 路由须从以下三方面扩展尽力而为的路 由模型：首先，为了支持多种服务类型，q o s 路由需要支持i n t s e r v 模型， 7 重庆邮电人学硕十论文 第二章q o s 路由机制与模型 支持业务类别( t o s ) 应用需要以及源宿结点间的多重路径计算，些新 型服务应用的路由计算可能需要不同的路由度量参数，如带宽、成本、每 一跳开销、时延、可靠性等；第二，在提供“较好”服务性能路由的同时， 需要防止业务流频繁地从一条路由跳转到另一条“更好”的路由，避免由于 路由“振荡”给端用户业务带来不必要的时延和抖动；第三，支持可选路由， 虽然这条路径不一定是最优或者最短的路由。 q o s 路由的目标 q o s 路由过程是通过资源和路由的计算，选择可用路径以满足各种业 务应用提出的q o s 要求的一个过程。选路时需要考虑的因素有：网络拓扑 结构、业务的q o s 参数要求、链路上的可用资源和网络管理层面所规定的 其他策略。 q o s 路由将传统的最短路径变为一条可适应其体业务流属性需求的 “更好”路径，实施q o s 路由的主要目标主要包括以下几点： 1 ) 能够动态地选择可行路径。为每一个接纳的q o s 业务连接请求，找 到能够满足其q o s 参数需求的可行路径； 2 ) 优化资源配置，平衡网络负载，实现网络全局资源利用率的优化， 从而最大化网络接受其他q o s 请求的能力； 3 ) 与传统的路由机制相比，能够改善网络吞吐量和网络性能退化。 q o s 路由的功能组成 q o s 路由主要包括q o s 路由协议和q o s 路由算法两个基本内容。q o s 路由协议用于完成网络结点之间收集和发布网络状态信息的功能，q o s 路 由算法则是根据已有的状态信息来为新的用户业务的连接请求选择一条 合适路由。 为了提供q o s 保证，与i n t s e r v 类似，q o s 路由通常在用户业务流转 发前需要q o s 路由算法计算好相应的传送路径，从源端向宿端传播一个消 息，用来通知路径上的所有结点为这个q o s 业务保留相应的资源( 如带宽、 缓存等) ，而后续的用户业务数据流则沿着这条已经预留了资源的路径进 行传输。由此可见，q o s 路由也是一种具有面向连接特性的路由机制。而 网络因此而产生的可用资源变化则可以通过q o s 路由协议通知网络中的 各个结点。 2 1 2q o s 路由状态信息的分类和更新 如前所述，q o s 路由的主要内容包括q o s 路由协议和q o s 路由算法 重庆邮电大学硕士论文 第二章q o s 路由机制与模型 两部分。q o s 路由协议实现测量、收集和维护网络状态信息，完成状态信 息的获取和传播功能；q o s 路由计算则依据网络结点维护的网络状态信息 和业务流的q o s 需求计算获得一条优化的可行路径。 状态信息 按照网络信息所处的物理位置，可以有3 种状态信息：本地状态信 息、全局状态信息和汇聚局部的全局状态信息。 1 ) 本地状态信息：结点以及与其直接连接的链路所具有的状态信息称 为本地状态信息。本地状态信息具体包括可用带宽、时延、抖动、分组丢 失率、结点处理器占用率和链路开销等信息，这些本地状态信息是其他状 态信息的基础，也是q o s 路由技术的基础信息。 2 ) 全局状态信息：网络中全部结点的本地状态信息的组合称为全局状 态信息。基于全局状态信息，可以比较容易设计启发式路由算法。虽然许 多q o s 路由研究均基于全局状态信息，但随着网络规模的不断扩大，网络 全局信息数量急剧增加，要求一个结点保存如此大量的全局状态信息，并 通过它计算可行路径，在空间和时间上几乎不可能。 3 ) 汇聚局部的全局状态信息：为了减小网络全局状态信息的信息量，