（微电子学与固体电子学专业论文）基于pareto最优的多约束qos路由算法研究.pdf

一 q 2 j u 一 _ ， 1 p ； ， 基于p a r e t o 最优的多约束o o s 路由算法研究 基于p a r e t o 最优的多约束o o s 路由算法研究 摘要 近年来，由于i p 网络独立于上层应用和下层承载网的通用特性， 构建以i p 技术为基础的融合网络成为下一代高速宽带网络的基础。 同时，日益丰富的各种网络业务对带宽、延迟、延迟抖动和分组丢失 率等性能参数有不同需求，因此要求网络能对各种不同业务加以区 分，并根据用户要求分配资源提供不同服务质量( q o s ) 。i pq o s 研究 框架中的q o s 路由问题，特别是基于多个度量约束构建的多约束q o s 路由问题，因其可更精确地反映实际路由选择过程成为业界研究热 点。多约束q o s 路由问题的研究重点在于解决其中的n p 完全问题， 可通过将其转化为多目标优化问题( m o o p ) 解决。利用p a r e t o 最优化 理论，通过搜索p a r e t o 最优点完成q o s 度量空间划分，从而通过路 由请求信息判断路径可行性，得出满足多约束条件的可行解。 本文通过分析线性搜索和非线性搜索的几何意义，提出了一种基 于d i j k s t r a 算法搜索p a r e t o 最优点的方法，将线性搜索与非线性搜索、 预计算与在线计算相结合的q o s 路由算法：线性预计算非线性在线 计算路由算法( l p n o a 算法) 。l p n o a 算法在线性预计算阶段选取最 佳线性搜索方向，在非线性在线计算阶段定义一种新的非线性路径代 价函数。本文在仿真平台上实现了l p n o a 算法，并分别从算法复杂 度、响应速度和路径搜索成功率等性能方面，与现有同样基于p a r e t o 最优的q o s 度量空间的划分进行求解的p o d w c a 算法进行了仿真比 较。仿真验证l p n o a 算法在同等计算复杂度下剩余n p 完全区域面 积所占比例比p o d w c a 算法低l o 1 5 ，且响应速度略高于 p o d w c a 算法，算法成功率最多比p o d w c a 算法高o 6 。 随着网络规模的扩大和复杂化，精确网络状态信息的获取越来越 难，而非精确的动态网络参数可能导致网络性能极度恶化。本文提出 了一种基于非精确网络状态信息的预计算与在线计算结合的q o s 路 由算法( p o c q r a i n s i 算法) 。该算法采用蚁群算法作为基本搜索算 法，分为预计算和在线计算阶段，不同阶段对信息素进行不同定义。 本文通过对l p n o a 算法在动态网络中的算法性能进行仿真比较，验 证了动态网络参数的非精确性对算法性能产生的负面影响，l p n o a 北京邮电人学硕i - q ：位论文 基- - f p a r e t o 最优的多约束o o s 路由算法研究 算法在动态网络中路径搜索成功率比一般网络环境的情况降低约4 左右，搜索效率降低约l5 左右，而p o c q r a i n s i 算法却基本保持 在一般网络环境下的情况。 另外，本文还研究了基于带宽代理的接纳控制机制，完成了四种 接纳控制算法的仿真建模，并选取接纳率、网络利用率和平均等待时 间作为算法性能的评价指标进行仿真比较。 文章最后概括的总结了所取得的研究成果，并对进一步深入研究 q o s 路由算法的研究方向进行了展望。 关键词多约束q o s 路由多目标优化问题q o s 度量空间 p a r e t o 最优带宽代理 ， _ 一 北京邮l 乜人学硕i ：学位论文堆十p a r e t o 最优的多约束q o s 路由算法研究 i i e s e a r c ho nm i t i c o n s t r a i n e dq o sr o u t i n g a l g o r i t h mb a s e do np a r e t 0o p t i m a i 。i t y a bs t r a c t a si pn e t w o r k sg e n e r a lc h a r a c t e r i s t i co fi n d e p e n d e n to fh ig hl a y e r a p p l i c a t i o n s a n d l o w l a y e r c a r r i e rn e t w o r k s ，t h ec o n s t r u c t i o no f c o n v e r g e dn e t w o r kb a s e do ni pt e c h n o l o g yb e c o m e st h eb a s i co fn e x t g e n e r a t i o nh i g hs p e e db r o a d b a n dn e t w o r kr e c e n t l y m e a n w h i l e ，v a r i e t i e s o fi n c r e a s i n g l yr i c ht r a f f i c sh a v ed i f f e r e n tr e q u i r e m e n t si np e r f o r m a n c e p a r a m e t e r ss u c ha sb a n d w i d t h ，d e l a y , d e l a yji t t e ra n dp a c k e tl o s sr a t e ， w h i c hr e q u i r e sn e t w o r kd i f f e r e n t i a t et r a f f i c s ，a n da l l o c a t e sr e s o u r c e s a c c o r d i n gt ou s e r s r e q u i r e m e n t st op r o v i d ed i f f e r e n tq u a l i t yo fs e r v i c e s ( q o s ) f o rt r a f f i c s q o sr o u t i n gp r o b l e mi nq o sr e s e a r c hf r a m e w o r k , e s p e c i a l l ym u l t i - c o n s t r a i n e dq o sr o u t i n gp r o b l e mc o n s t r u c to fm u l t i p l e m e t r i cc o n s t r a i n sb e c o m e sar e s e a r c hf o c u si nt h ei n d u s t r yb e c a u s ei tc a n r e f l e c tp r a c t i c a lq o sr o u t i n gs e l e c t i o np r o b l e mm o r ee x a c t l y t h e r e s e a r c he m p h a s i so fm u l t i - c o n s t r a i n e dq o sr o u t i n gp r o b l e mi sr e s o l v i n g an pc o m p l e t ep r o b l e m ，a n da ne f f e c t i v es o l u t i o n i st oc o n v e r ti tt o m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ( m o o p ) i nt h es e a r c h i n go f p a r e t oo p t i m a l i t yp o i n tw i t hp a r e t oo p t i m a l i t yt h e o r y , t h ep a r t i t i o no fq o s m e t r i cs p a c ec a nb ea c c o m p l i s h e d ，a n dt h ef e a s i b i l i t yo ft h ep a t hc a nb e j u d g e db yt h er o u t i n gr e q u e s ti n f o r m a t i o nw h i c ha c q u i r e dt h ef e a s i b l e s o l u t i o nt h a tm e e tq o sr o u t i n g sm u l t i - c o n s t r a i n e dc o n d i t i o n s aq o sr o u t i n ga l g o r i t h mn a m e dl i n e a rp r e c o m p u t en o n l i n e a r o n l i n e - c o m p u t ea l g o r i t h m ( l p n o a ) o nt h eb a s i so fs e a r c h i n gp a r e t o o p t i m a l i t yp o i n tw i t hd i j k s t r aa l g o r i t h mi sp r o p o e di n t h i sp a p e rb y a n a l y z i n gg e o m e t r i c a lm e a n i n g o fl i n e a r s e a r c h i n g a n dn o n - l i n e a r s e a r c h i n g t h ea l g o r i t h mn o to n l y c o m b i n e sl i n e a r s e a r c h i n gw i t h n o n l i n e a r s e a r c h i n g ， b u ta l s oc o m b i n e s p r e c o m p u t e w i t h o n l i n e c o m p u t e i ts e l e c t sa no p t i m a ls e a r c h i n gd i r e c t i o ni np r e - c o m p u t e 1 1 1 北京邮l 【i 人学硕i j 学位论文堆于p a r c t o 最优的多约束q o s 路由算法研究 s t a g e a n dd e f i n e san e wn o n 1 i n e a rp a t hc o s tf u n c t i o ni no n 1 i n e - c o m p u t e s t a g e l p n o aa l g o r i t h mi si m p l e m e n t e di nt h es i m u l a t i o np l a t f o r m ，a n d i sc o m p a r e dw i t hp o d w c a a l g o r i t h m ，w h i c ha l s oa d o p t e dt h ep a r t i t i o n o fq o sm e t r i cs p a c eb a s e do np a r e t oo p t i m a l i t y , i nt h ea l g o r i t h m p e r f o r m a n c es u c h a s c o m p l e x i t y , r e s p o n ds p e e da n dp a t hs e a r c h i n g s u c c e s sr a t e i ti sv e r i f i e dt h ep r o p o r t i o no fr e m a i n i n gn pc o m p l e t ea r e a o fl p n o aa l g o r i t h mw i t ht h es a m ec o m p l e x i t yi sl o w e rt h a nt h a to f p o d w c a a l g o r i t h m10 t o15 ，t h er e s p o n ds p e e ds l i g h t l yh i g h e r , a n d 、， t h es u c c e s sr a t ei sh i g h e rt h a nt h a to fp o d w c a a l g o r i t h mu p t oo 6 w i t ht h ei n t e n s ea n dc o m p l i c a t i o no fn e t w o r ks c a l e t h ea c q u i s i t i o n o fa c c u r a t en e t w o r ki n f o r m a t i o nb e c o m e sm o r ea n dm o r ed i 衔c u l t w h i l e i n a c c u r a t en e t w o r ks t a t ei n f o r m a t i o nm a yl c a dt on e t w o r kp e r f o r m a n c e s e x t r e m e l yd e t e r i o r a t i o n aq o sr o u t i n ga l g o r i t h mn a m e dp r e - c o m p u t e a n do n - l i n e - - c o m p u t ec o m b i n e dq o sr o u t i n ga l g o r i t h mw i t hi n a c c u r a t e n e t w o r ks t a t ei n f o r m a t i o n ( p o c q r a i n s i ) i sp u tf o r w a r di nt h ep a p e r t h ea l g o r i t h ma d o p t sa n tc o l o n ya l g o r i t h ma sab a s i cs e a r c h i n ga l g o r i t h m , a n dc o m p r i s e sp r e c o m p u t es t a g ea n do n l i n e c o m p u t es t a g e ，a n dh a v e d i f f e r e n ti n f o r m a t i o nv o l u m ed e f i n e si nd i f f e r e n ts t a g e t h es i m u l a t i o n v e r i f i e st h en e g a t i v ee f f e c to fi n a c c u r a t yo fn e t w o r ks t a t ei n f e l r m a t i o nb y c o m p a r i n gw i t hl p n o aa l g o r i t h m sp e r f o r m a n c e si ni n a c c u r a t en e t w o r k t h ep a t hs e a r c h i n gs u c c e s sr a t eo fl p n o aa l g o r i t h mi ni n a c c u r a t e n e t w o r kd e c r e a s e da b o u t4 t h a ni ng e n e r a ln e t w o r ke n v i r o n m e n t a n d s e a r c h i n ge f f i c i e n c ya b o u t15 ，w h i l ep o c q r a - s ia l g o r i t h ma l m o s t r e m a i n st h es a m ea st h ec a s ei ng e n e r a ln e t w o r ke n v i r o n m e n t b e s i d e s ar e s e a r c ho nq o sa d m i s s i o nc o n t r o lm e c h a n i s mb a s e do n b a n d w i d t hb r o k e ri sa l s om a d ei nt h ep a p e r f o u ra d m i s s i o nc o n t r o l a l g o r i t h m ss i m u l a t i o nm o d e l i n ga r eb u i l t ，w h i c hc h o o s ea c c e p t a n c er a t e ， n e t w o r ku t i l i z a t i o na n da v e r a g ew a i t i n gt i m ea se v a l u a t es t a n d a r d t h ep a p e rs u m m a r i z e st h ea c h i e v e dr e s u l t ，a n di n d i c a t e sf u r t h e r r e s e a r c hd i r e c t i o ni nq o sr o u t i n ga l g o r i t h mi nt h ee n d 一 k e yw o r d sm u l t i c o n s t r a i n e dq o sr o u t i n g q o sm e t r i cs p a c e m o o pp a r e t oo p t i m a l i t yb a n d w i d t hb r o k e r 一 北京邮i 【1 人学硕i ? 学位论文 慕十p a r e t o 最优的多约束q o s 路由算法研究 目录 摘要i a b s t r a c t i i i 目录v 第一章绪论1 1 1 课题背景及研究意义1 1 2 1 3 第二章 2 1 2 2 2 3 2 4 第三章 3 1 3 2 3 3 1 1 1 q o s 概述1 1 1 2 q o s 的主要研究内容3 1 1 3 q o s 路由的研究意义及研究现状5 1 1 4d i f f s e r v 网络架构中的接纳控制机制6 研究内容及所做工作8 论文的组织结构9 多约束q o s 路由技术1 l q o s 路由的基本问题1 1 2 1 1q o s 路由的网络模型1 l 2 1 2q o s 的度量1 2 2 1 3q o s 路由中基本问题的分类1 2 2 1 4 三类n p 完全问题1 4 基于p a r e t o 最优的q o s 度量空间的划分1 5 2 2 1p a r e t o 最优化理论及其应用1 5 2 2 2 基于p a r e t o 最优的q o s 度量空间划分1 6 几种q o s 路由研究方法1 9 2 3 1 线性搜索与非线性搜索1 9 2 3 2 预计算与在线计算2 0 本章小结2 1 一般网络环境中的q o s 路由算法研究2 2 算法基础2 2 3 1 1 两加性度量约束q o s 路由问题的特性分析2 2 3 1 2 当前算法存在问题及解决方法2 2 l p n o a 算法的设计与实现2 4 3 2 1l p n o a 算法的基本流程2 4 3 2 2 预计算阶段的算法设计2 5 3 2 3 在线计算阶段的算法设计2 9 l p n o a 算法的仿真分析3 2 3 3 1 仿真设计3 2 3 3 2 算法的计算复杂度分析3 4 3 3 3 算法的响应速度分析3 5 3 3 4 算法的路径搜索成功率分析3 6 v 北京邮f 乜人学硕l ：学位论文 幕- j = p a r e t o 最优的多约束q o s 路由算法研究 3 4 本章小结3 6 第四章基于动态网络参数的q o s 路由算法研究3 8 4 1 研究背景3 8 4 1 1 动态网络中网络参数的非精确性3 8 4 1 2 蚁群算法简介3 9 4 2 基于概率的两加性度量q o s 路由问题建模4 0 4 3 p o c q r a i n s i 算法的设计与实现4 l 4 3 1p o c q r a 1 n s i 算法的基本流程4 1 4 3 2 预计算阶段的具体设计4 3 4 3 3 在线计算阶段的具体设计4 6 4 4p o c q r a i n s i 算法的仿真分析4 8 4 4 1 仿真设计4 8 4 4 2 算法的路径搜索成功率分析5 0 4 4 3 算法受动态网络参数的影响分析5 0 4 5 本章小结5 l 第五章q o s 接纳控制机制的仿真研究5 2 5 1 基于带宽代理的接纳控制机制5 2 5 1 1 带宽代理( b b ) 的功能结构5 2 5 1 2 集中式和分层b b 的结构5 3 5 1 3b b 进行接纳控制的基本工作流程5 5 5 2 q o s 接纳控制算法的设计5 5 5 2 1 算法中的基本功能实体5 5 5 2 2s a c 算法的消息处理流程5 6 5 2 3 四种算法的流程设计5 7 5 2 4 算法的具体实现6 0 5 3o o s 接纳控制算法的仿真设计6 2 5 3 1 仿真场景设置及网络参数6 2 5 3 2 仿真结果分析6 3 5 4 本章小结6 5 第六章全文总结与展望6 6 6 1 研究工作总结6 6 6 2 研究展望6 7 参考文献6 8 附录7 l 致谢7 2 攻读学位期间发表的学术论文7 3 v l 北京邮i 乜人学硕i ：学位论文皋十p a r e t o 最优的多约束q o s 路由算法研究 第一章绪论 近年来，由于口技术独立于上层应用和下层承载网络的通用特性，i p 网络 的实用化进程遍及到了以i n t e r n e t 为代表的各大通信网络，构建以m 网络技术为 基础的融合网络成为下一代高速宽带网络的基础。特别是随着实时多媒体等宽带 网络应用业务的蓬勃发展，要求包括数据、音频、视频和多媒体等在内的多种业 务在同一个融合网络中传输。不同业务对通信带宽、延迟、延迟抖动和分组丢失 率等性能参数有不同需求，这就要求网络能对各种不同业务加以区分，并根据用 户要求分配和调度资源，提供不同的业务服务质量( q u a l i t yo fs o r v i c e ，q o s ) t 1 1 。然 而，由于口网络设计上在服务质量保证方面考虑的欠缺，导致传统的“尽力而 为 的网络机制不能满足日益增长的通信服务质量需求【2 】。因此，以提高网络 资源利用率、为用户提供更高服务质量为目标，提供端到端q o s 保证的相关技 术成为业界在关于下一代异构融合网络研究领域中的一个热点问题【3 j 。 1 1 课题背景及研究意义 本论文的研究内容来源于国家8 6 3 计划“支撑新一代异构网络融合的协同管 理新技术中“统一的q o s 保证和管理技术一子课题。课题在q o s 方面的研究 内容涵盖了q o s 研究框架中控制平面的三大主要议题：接纳控制机制、资源预 留协议和q o s 路由问题。近几年研究表明：路由选择是网络运行的核心问题， 合理高效的路由选择方式不仅可保障全网正常运行，还能提高网络接通率，从而 既可尽量避免交换机不堪重负的情况，又能降低网络运营成本。而提高网络接通 率很大程度上依赖于路由选择策略的改变，因此m 网络的动态路由选择问题变 得越来越重要，特别是q o s 路由对实现网络资源的合理分配和利用，保证网络 服务质量具有非常重要的作用，因此q o s 路由算法的研究已日益成为网络研究 的核心问题之一【4 】。本文主要针对多约束q o s 路由算法这一融合网络研究领域的 热点课题展开深入研究，并给出作者在此项研究前对接纳控制机制的研究成果。 1 1 1q o s 概述 q o s 即服务质量，是一个宽泛的概念，是一种网络与用户之间以及网络上互 相通信的用户之间关于信息传输的约定，是网络为保证通信的质量而提供的一种 端到端的处理机制。q o s 的定义最初是由c c i t t 给出的，其内容是：q o s 是一 个综合指标，用于衡量用户对网络所提供的服务的满意程度【5 1 。随后，众多的国 际标准化组织、研究机构也都开始投入了极大的热情研究网络中的q o s 问题， 第l 页 北京邮i 乜人学硕i j 学位论文 皋- t ：p a r e t o 最优的多约束q o s 路由算法研究 并相应给出了自己的定义方法： ( 1 ) i t u t 更关注于下一代融合网络，综合考虑了移动网络与固定网络，及多 网络融合场景下的服务质量，它给出的定义为：决定用户满意度的服务性能的整 体表现。关于分组网络中的q o s 问题，i t u t 对i pq o s 从具体的音频、视频和 数据业务等的各种应用业务角度进行了分类，并针对不同业务分别提供了详细的 性能目标参数。i t u ts g l 3 组的y 1 2 9 1 建议草案中提出了一个划分为控制平面、 数据平面和管理平面的三个逻辑层面的q o s 的研究框架 6 1 ，关于这个研究框架的 具体内容将在下一节中进行介绍。 ( 2 ) i e t f 则更多的把焦点对准了计算机网络中的服务质量管理以及实现这些 机制的具体协议和算法，它在文献 7 1 中对q o s 做出了如下定义：q o s 是网络在传 输数据流时要求满足的一系列服务请求，具体可以量化为带宽、时延、抖动、分 组丢失率、吞吐量等性能指标。另外，i e t f 还提出了i n t s c r v 和d i f f s e r v 两种 q o s 的体系结构模型及其与多协议标签交换m p l s 、流量工程等技术相结合实现 端到端q o s 的框架方案，用于解决i n t e r a c t 网络的q o s 控制和管理。在q o s 分 类方面，其对于d i f f s e r v 定义的不同等级的p h b 针对性更强，主要侧重于d i f f s e r v 中的转发等级，并对每个转发等级的q o s 性能进行的要求。 ( 3 ) a t m 论坛给出的定义为：网络组件为业务和服务需求提供一定级别保障 的能力。它们提出了q o s 控制的策略和实现，a t m 控制是“连接预定 型，其 核心内容是在服务建立前，通过接纳控制和资源预留提供服务的q o s 保证，而 在服务交互过程中，用户进程和网络要严格按照约定的q o s 实现服务质量保证。 迄今为止，q o s 还没有一个标准化的统一定义，但是上述组织给出的所有这 些定义在本质上却都是大同小异的。简言之，q o s 是网络在传输各种应用业务流 时，业务流对网络传输服务提出的一组可度量的服务需求的集合，其中业务流是 指与特定q o s 相关的从源到目的地的分组流，这些服务需求主要包括带宽、时 延、丢包率、时延抖动、费用等。网络在传输相应的数据业务时，必须满足其对 应的需求。q o s 需求可以通过一个约束集来描述，包括链路约束、路径约束和树 约束【8 1 。链路约束定义了从源到目的地的每一条链路的约束，如带宽约束；路径 约束定义了从源到目的地的一条路径上端到端q o s 需求，如时延；树约束定义 了对组播中整个组播树的约束，例如对组播树延迟的约束是对树中从源到所有目 的地的路径中最大时延的约束。 总之，q o s 问题纵向上包括物理层到应用层，横向上跨越端到端之间的各个 节点设备、各种底层网络技术，并不是网络中某一个设备或者某一方面能力的体 现，而是反映出了网络元素在保证信息传输和满足服务要求方面的综合能力。因 此，对q o s 问题的研究方法也应该采取一些更加宏观的手段，需要综合考虑进 行通信的各个没备所构成的网络，以及连接网络与网络之间的互联网络的整体资 第2 页 北京邮i 乜人学顾l ：学位论文 甚于p a r e t o 最优的多约束o o s 路由算法研究 源分布和性能需求进行分析，是一个涉及用户终端和通信网络的端到端的问题。 1 1 2q o s 的主要研究内容 一般而言，现有的q o s 技术主要涉及以下三个方面的问题： 1 q o s 识别和标志技术：主要是调整网络单元之间终端到终端的服务质量， 这是通过数据包流量分类和预留带宽完成的。识别流量的一般方法包括访问控制 列表( a c l ) 、策略路由技术、承诺访问速率( c a r ) 及基于网络应用的识别( n b a r ) 。 2 单一网络单元中的q o s ：包括拥塞控制、队列管理、链接效率等技术和 分层流量监管工具。 3 q o s 策略、管理和计费功能：主要控制和管理终端到终端的网络流量，包 括配置网络设备。当获取网络流量及目标应用程序时，需要采用o o s 技术来提 高服务质量。通过测试目标应用程序的响应可以知道该过程是否达到o o s 标准。 i t u t 针对上述q o s 技术中所涉及的基本问题进行了逻辑划分，提出了关 于p 网络中q o s 的研究框架，如图1 1 所示。q o s 问题在逻辑上可以分为三个 部分，即控制平面，数据平面以及管理平面。 圈圈圈圈 数据平面 际网 i 协议( s l a ) i r 。1 l 流量测量l i 和记录l 圈 圈 管理平面 一 图1 1i po o s 研究框架中的三个逻辑组成部分 数据平面主要是关于直接处理业务数据的各种机制，包括例如缓冲区管理、 拥塞避免、分组标记队列和调度以及流量分类、流量策略及流量整形等机制。以 上各种机制，一直以来都是大家讨论较多的对象，目前已经研究的比较成熟了， 无论具体网络是怎样的，数据平面的机制基本上是相似的。因此，数据平面并不 是未来研究的重点。 管理平面的主要功能是操作、监督和管理数据流的各个方面，包括负责s l a 、 流量测量和记录、流量恢复和策略管理的机制。管理平面和控制平面在某种程度 上 兑是比较相似的，二者都实现控制的功能，其实质是相同的。只是管理平面的 第3 页 北京邮电人学硕i ：学位论文 基于p a r e t o 最优的多约束q o s 路由算法研究 q o s 管理时间周期较长，其机制与具体运营过程中的策略、政府行为有关，目前 看来较难统一控制，因此各大标准化组织还是把研究关注点放在了控制平面。 控制平面主要是处理与传送业务的路径相关的问题，时间周期较短，主要包 括接纳控制、资源预留和q o s 路由等机制。接纳控制机制的主要内容是通过综合 分析当前的网络业务状态和新进业务流的通信量特征和资源需求做出业务接纳判 决，在保证新接纳的业务不会使网络过载、影响当前正在传送业务的性能的前提 下，判定当前网络的可用资源是否能够满足新进业务流的q o s 需求。 资源预留机制方面的研究大致可以划分为两个阶段，早期i e t f 首先提出了 通过为特定类的数据流预留相应的网络资源，以实现在i n t e m e t 中提供q o s 保证 的资源预留协议( r 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 s v p ) t 9 ，但是r s v p 在安全性、 灵活性和扩展性等方面都存在着诸多问题，如不支持移动性，只支持接收端发起 的资源预留等。为满足网络信令多样化的要求，需要一种更为灵活、统一的口 信令协议体系。2 0 0 1 年1 1 月i e t f 成立了n s i s ( n e x ts t e p si ns i g n a l i n g ) 工作组， 致力于研究下一代信令的需求、体系结构以及协议实现等问题【1 0 1 。n s i s 工作组 提出通用的控制i p 包传递的信令框架，并为网络实体提供模型，主要解决沿着 数据路径的网络控制状态建立问题。n s i s 的基本设计思想是把信令传输与信令 应用相分离，并根据模块化要求将信令协议分成了两层：信令传输层( n s i s t r a n s p o r tl a y e rp r o t o c o l ，n t l p ) 和信令应用层( n s i ss i g n a l i n gl a y e rp r o t o c o l ， n s l p ) ，这种体系结构在很大程度上决定了n s i s 的灵活性和扩展性。 q o s 路f 1 ( q o sr o u t i n g ，q o s r ) i 司题是主要研究满足某业务流的q o s 需求的路 径选择问题，是一种基于数据流的q o s 请求和网络可用资源进行路由的机制【_ 7 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 路由算法。 第4 页 换中的一些基本思想。例如上文中提到的q o s 控制平面中的接纳控制机制和资 源预留机制，在具体实现过程很多方面就采用了类似电路交换中采用的技术。 而与上述机制不同的o o s 路由问题则是立足于分组网络，更多的考虑了p 网络所特有的一些性质，在进行路径选择的过程中综合考虑了业务流的需求和特 性、当前可用的网络资源等一些关于网络状态的参数，并且能够很好的与流量工 程、m p l s 技术等当前最热门的技术实现完美结合，共同提供在各种不同的网络 类型中的端到端q o s 保证。由此看来，q o s 路由选择策略显得格外重要，它是 整个o o s 研究框架中的重要组成部分【l3 1 ，是实现q o s 保证的关键技术之一，也 是目前关于q o s 的一个重要的研究方向。可以说，关于q o s 路由算法的研究， 对于基于i p 技术的下一代异构融合网络中的端到端q o s 保证问题的研究和实 现，都具有极其深远的理论指导意义和现实意义。 目前的q o s 路由算法按网络状态信息的存储位置和做出路由选择判断的节 点范围分类，主要包括以下三类：源路由算法、分布式路由算法和分级路由算法。 在源路由策略中，每个节点都需要保存全网状态信息，包括网络拓扑和到达其他 节点的路径的度量值等。当业务请求到达时，源节点根据网络状念信息和业务度 量参数要求独立完成可行路径计算和路由选择。分布式算法则要求网络中的节点 仅保存与其相邻的节点及链路的信息，并通过路由协议与邻近节点交换节点的相 关网络信息，路由选择是通过多个节点协同合作逐跳计算完成的。分级路由算法 一般是针对大型网络，首先按照一定层次将大型网络进行分组，每组由若干在距 离上比较接近的节点构成一级，并在每组中选出一个逻辑节点。逻辑节点中集中 第5 页 北京邮i 1 人学硕i ：学位论文 基- f p a r e t o 最优的多约束q o s 路由算法研究 保存整个组内的网络状态信息，并据此代表该组完成与其他组之间传送数据时的 路由选择。组内则运用源路由算法求解最优路径，并通过边界点形成最终路径。 针对上述几类q o s 路由问题研究人员也相应提出了很多类算法作为解决方 法。这些算法大体上可分为【1 4 】：启发式算法、近似算法、探测类算法、路径子空 间搜索的算法、基于某种调度策略的多约束q o s 路由算法和仿生类算法。其中 启发式算法可降低算法时间复杂度，但不能保证在即使存在传输路径条件下发现 一条可行传输路径；近似算法可分为多项式近似算法和伪多项式近似算法，两者 区别在于伪多项式近似算法的计算复杂度不仅仅同网络大小有关，还取决与网络 链路参数大小，采用近似算法可求最优化路径的近似解，但这类算法的时间复杂 度往往比启发式算法高；基于探测类的算法路由时间长、通信开销大，还可能阻 塞其他业务，中间节点需要保存大量状态；路径子空间搜索算法需要较好的启发 函数，以增大路由失败概率和降低路由性能为代价，减小了计算开销；基于某种 调度策略的多约束q o s 路由算法能够较好的解决多约束q o s 路由问题，但由于 它要求某种特殊的调度策略，这使得这些算法在使用上具有一些局限性；仿生类 算法则是采用某种仿生类的算法求解q o s 路由中的n p 完全问题的最优解，例如， 基于遗传算法、基于蚁群算法、基于模拟退火和基于神经网络等的路由算法。 文献【1 5 l 中首先提出了将p a r e t o 最优化理论引入q o s 路由算法中用于解决多 约束路由问题的作法，并给出了基于p a r c t o 最优的q o s 度量空间的划分框架。 本文就是基于上述划分框架，针对基本q o s 路由问题提出了一种将线性搜索方 法和非线性搜索方法结合，及预计算算法和在线计算算法结合的q o s 路由算法。 另外，随着网络规模的扩大，出现了动态网络参数非精确的问题，而这个概 念最早是由g u e r i n 和o r d a 等人在文献【l6 】中首次提出的，他们给出了基本的研究 模型，研究了基于非精确网络状态信息的带宽受限和时延受限的路由问题，并提 出了基于概率分布的非精确信息模型和路由算法。近年来，基于动态网络参数的 q o s 路由算法得到了广泛研究，本文第四章就研究了上述问题，并提出了一种基 于蚁群算法的预计算与在线计算结合的基于动态网络参数的q o s 路由算法。 1 1 4d i f f s e r v 网络架构中的接纳控制机制 为了解决提供端到端q o s 保证的问题，i e t f 先后提出了两种q o s 体系架构： 综合服务( i n t s e r v ) 模型和区分服务( d i f f s e ) 模型【1 7 j ，并基于上述两模型提出了很 多网络资源管理分配等方面的技术，接纳控制机制就是其中一项技术。 d i f