（计算机科学与技术专业论文）因特网qos路由算法研究.pdf

国防科技大学研究生院学位论文 摘要 日益增多的网络应用，使得因特网正从尽力而为的网络，进化到对不同网络应用 提供不同等级服务质量的网络。因而，网络学术界对网络能否提供q o s 能力非常关注， 并提出了包括i n t s e r v , d i f l s e r v , m p l s 等在内的几个支持q o s 的网络模型。然而，目前 因特网提供q o s 的能力仍然不能满足不同应用的要求，其中重要原因之一是缺乏既有 效又实用的解决手段，因而对支持q o s 的网络的研究是计算机网络的一个研究热点。 q o s 路由( q o s r ) 是支持q o s 的网络体系结构中的重要组成部分。设计有效的q o s 路由算法是q o s 路由面临的关键问题之一，旨在利用q o s 路由协议提供的网络状态信 息，为不同网络应用寻找满足q o s 需求的可行路径。论文针对q o s 路由算法设计问题 进行了深入研究，并提出了有效的q o s 路由算法。 在q o s 路由算法研究过程中，形成了三类重要子问题：约束最短路径问题( r s p ) ； 多约束路径问题( m c p ) ：多约束优化路径问题( m c o p ) 。论文研究发现，这三类子问 题都可以通过转化为一个特殊的多目标优化问题而获得解决，考虑至l j p a r e t o 最优是多 目标优化问题中的重要概念，论文首次把p a r e t o 最优的相关概念引入到o o s 路由中， 并根据这些重要概念，研究t q o s 度量空间划分问题，建立了基于p a r e t o 最优的q o s 度 量空间区分框架p o p f 。在p o p f 中，q o s 度量空间被划分成三个部分：可行区域、不 可行区域以及n p 完全区域，这些区域具有明确的实际意义。论文着重讨论了两可加 约束q o s 路由问题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 最优点的方法。p o p f 不但为在q o s 路由中运用p a r e t o 最优概念提供了理论 基础。而且从算法采用的搜索方式，到算法的终止条件，甚至路由请求的生成方式等 方面，都对q o s 路由算法的设计和评估具有一定的指导作用。 论文首先提出了用来解决两可加约束的q o s 路由算法。算法充分利用了p o p f 中 的重要结论，因此具有良好的前瞻特性，避免了大量冗余计算。然后，论文定义了基 于法线测量的非线性路径长度方程n 1 上e n ，并基于n m s l e n 提出了解决m c p 问题 的n m _ m c p 算法。n m _ m c p 算法分为两个阶段：预计算阶段和在线计算阶段。在预计算 阶段，算法具有较小的执行周期，在一定程度上减d , - f 不精确网络状态信息对算法的影 响。另一方面，即使需要在线计算，n m a v l c p 算法也只调用一次d i j k s t r a 算法。由于预计 算阶段采用线性搜索方法，而在线计算阶段则采用非线性搜索方法，因而n m _ m c p 算 法成功结合了预计算和在线计算，线性搜索和非线性搜索的优点。仿真实验表明。与 第1 页 国防科技大学研究生院学位论文 同类算法相比，n m j 讧c p 算法在达到更快的响应速度同时，还实现了更高的找到可行 路径的成功率。 目前，绝大多数q o s 路由算法都假定路由选择时采用的网络状态信息精确地反映 了网络的当前状态。然而有多种原因，如网络的动态特性等，可以导致这些信息不能 真实地反映网络的当前状态。因此，论文进一步研究了不精确网络状态信息下q o s 度 量空间的划分问题，并给出了一些重要结论。在此基础上，论文着重研究了不精确网 络状态信息下两可加约束路径选择问题，把该问题建模为最大概率两可加约束路径问 题，并提出了解决该问题的m p t a c p a 算法。m p t a c p a 算法同样结合了预计算和在 线计算，线性搜索和非线性搜索的优点，并通过对链路上的状态信息施加特定的界，以 及引入覆盖概率的概念，使得算法具有良好的前瞻特性。仿真实验表明，m p t a c p a 算 法具有成功率高，平均计算代价低和响应速度快的特点，能够有效解决不精确网络状 态信息下的q o s 路由问题。 论文对q o s 路由算法设计问题进行了深入细致的研究，提出的p o p f 框架为q o s 路 由算法的设计和评估提供了重要的理论基础。基于p o p f 提出的q o s 路由算法具有成功 率高，响应速度快等优点。因此，论文的研究成果在下一代互联网中具有良好的应用 前景。 关键字：服务质量路由，p a r e t o 最优，q o s 度量空间，p o p f ，约束最短路径，多约 束路径，多约束优化路径，法线测量，覆盖概率，前瞻 第1 1 页 国防科技大学研究生院学位论文 a b s t r a c t t h e r ei sac o n f i n u o u sd e m a n df o rt h ee v o l u t i o no f t h ei n t e m e tf r o ma s i m p l eb e s t 。e t f o r t n e t w o r kt o w a r d st h eo n et h a tc a np r o v i d ev a r i o u sl e v e l so f q u a l i t y o f - s e r v i c e ( q o s ) g u a r a n t e e st on e t w o r ka p p l i c a t i o n s r e s e a r c h e r si na c a d e m i ah a v eb e e np a y i n gs i g n ic a n ta t t e n t i o n t oe n a b l i n gq o s - b a s e dn e t w o r k i n gi nt h ei n t e r n e t a l t h o u g hm u c hw o r kh a sa l r e a d yb e e n d o n ea n ds e v e r a lq o sb a s e dn e t w o r k i n gf r a m e w o r k s ( e g ，i n t s e r v , d i f f s e r v , m p l s ) a r ep r o p o s e d q o s b a s e dn e t w o r k i n gi ss t i l ln o ti np l a c e ，m o s t l yd u et ot h el a c ko fe f f i c i e n ta n d p r a c t i c a l l yd e p l o y a b l es o l u t i o n s ，c a l l i n gf o rf a r t h e rr e s e a r c h q o sr o u t i n g ( q o s r ) i so n eo f b u i l d i n gb l o c k si nt h ea r c h i t e c t u r a lf r a m e w o r kf o rq o s b a s e dn e t w o r k s ak e yi s s u ei nq o s ri sd e s i g n i n gq o sr o u t i n ga l g o r i t h m s ，n a m e l yh o w t on df e a s i b l ep a t h st h a ts a t i s f yq o sr e q u i r e m e n t so fv a r i o u sn e t w o r ka p p l i c a t i o n sb a s e d o ns t a t ei n f o r m a t i o np r o v i d e db yq o s r p r o t o c o l s t h ed i s s e r t a t i o ns t u d i e st h o r o u g h l yt h e p r o b l e mo f d e s i g n i n gq o s ra l g o r i t h m sa n dg i v e ss o m ee f f i c i e n tp r o p o s a l s t h e r ea r et h r e eg r e a tc h a l l e n g e st h a tq o s rf a c e s ，n a m e l yr e s t r i c t e ds h o r t e s tp a t h ( r s p ) p r o b l e m s ，m u l t i - c o n s t r a i n t sp a t h ( m c p ) p r o b l e m sa n dm u l t i - c o n s t r a i n t so p t i m a lp a t h ( m c o p ) p r o b l e m s t h e s et h r e ep r o b l e m sa r ec o n s i s t e n ti nt h em e a n i n go fp a r e t oo p t i m a l ， w h i c hi saf u n d a m e n t a lc o n c e p ti nm 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 s ( m o o p ) c o n c e r n i n gt h a tp a r e t oo p t i m a li sak e yc o n c e p ti nm o o p , w ei n 订o d u e e sp a r e t oo p - t i m a lr e l e v a n tc o n c e p t si n t oq o s rp r o b l e m s b a s e do nt h e s ec o n c e p t s ，ap a r e t oo p t i m a l b a s e dp a r t i t i o nf r a m e w o r k ( p o p f ) i se s t a b l i s h e d ，i nw h i c hq o sm e t r i cs p a c ei sp a r t i t i o n e d i n t ot h r e ep a r t s ，n a m e l yf e a s i b l e ，u n f e a s i b l ea n dn p - c o m p l e t ea r e a s w ea l s od i s c u s st h e p a r e t of r o n to f t w oa d d i t i v ec o n s t r a i n t sq o s rp r o b l e m sa n dp o i n tt h a tt h en u m b e ra n dd i s t r i b u t i o no fp a r e t oo p t i m a lp o i n t sa r ev e r yi m p o r t a n tt ot h ep a r t i t i o no fq o sm e t r i cs p a c e w et h e ng i v eam e t h o dt og e n e r a t ep a m t oo p t i m a lp o i n t s p o p fo n l yn o t p r o v i d e sat h e o r y b a s i sf o ra p p l y i n gp a r e t oo p t i m a lr e l e v a n tc o n c e p t si nq o s rp r o b l e m s ，b u ta l s oa c t sa sa g u i d et od e t e r m i n i n gs e a r c hd i r e c t i o n s ，t h et e r m i n a t i o nc o n d i t i o n so f t h ea l g o r i t h ma n de v e n h o wt og e n e r a t er o u t i n gr e q u e s t st oe v a l u a t ea l g o r i t h m s w er s tp r o p o s et w oq o s ra l g o r i t h m st h a ta d d r e s st w oa d d i t i v ec o n s t r a i n t sp a t hs e l e c t i o np r o b l e m s t h e s et w oa l g o r i t h m st a k ef u l l ya d v a n t a g e so fp a r e t oo p t i m a la n dh a v e l o o k a h e a da b i l i t y t h e n ，b yd e s i g n i n gan o v e ln o n l i n e a rp a t hl e n g t hf u n c t i o n ，w ep r o p o s e 第1 i l 页 国防科技大学研究生院学位论文 a l le f f i c i e n tq o s ra l g o r i t h mn m m c pt h a td e a l sw i t hm c pp r o b l e m s n m m c pm a i n l y c o n s i s t so f t w op h a s e s ：p r e c o m p u t a t i o na n do n - d e m a n dc o m p u t a t i o n b e c a u s eo f t h es h o r t p e r i o do fp r e c o m p u t a t i o n n m m c ps u f f e r sl e s sf r o mi n a c c u r a t es t a t ei n f o r m a t i o nw h i l e h a v i n gaf a s tr e s p o n s ea tt h es a m e t i m e o n et h eo t h e rh a n d n m m c pe x e c u t e sam o d ie d v e r s i o no f d i j k s t r aa l g o r i t h ma tm o s to n c eo n d e m a n da l o n gw i t ht h en e w l yd en e dn o n l i n e a rp a t hl e n g t hf u n c t i o n t h e r e f o r e ，n m _ m c pm a k e sag o o dt r a d e o f fn o to n l yb e t w e e np r e c o m p u t a t i o na n do n - d e m a n dc o m p u t a t i o n ，b u ta l s ob e t w e e nn o n l i n e a ra n d l i n e a rc o s t b a s e d p a t h ss e l e c t i o na l g o r i t h m s u s i n ge x t e n s i v es i m u l a t i o n s ，w ed e m o n s t r a t et h eh i g hs u c c e s s r a t ea n dr e s p o n s i v e n e s so f n m _ m c pw h e nc o m p a r e dt ot h ee x i s t i n gq o s rs o l u t i o n s w i t hf e we x c e p t i o n s m o s to fp r e v i o u sq o sr o u t i n gs o l u t i o n sh a v eb e e nd e v e l o p e d u n d e rt h ea s s u m p t i o nt h a tal i n k s t a t er o u t i n gp r o t o c o li su s e dt om a i n t a i nt h eg l o b a ln e t w o r k s t a t ei n f o r m a t i o na te a c hn o d e ，a n dt h a tt h i sg l o b a li n f o r m a t i o ni sa c c u r a t e i np r a c t i c e ， h o w e v e r , t h en e t w o r ks t a t ei n f o r m a t i o nm i g h tn o tb ea c c u r a t ed u et os e v e r a lr e a s o n s w er e c o n s i d e rt h ec o n c l u s i o n si np o p fa n ds t u d yc a r e f u l l yt w oa d d i t i v e - c o n s t r a i n e d p a t hp r o b l e m ，i nt h ep r e s e n c eo fi n a c c u r a t es t a t ei n f o r m a t i o n w ef o r m u l a t et h i sp r o b l e m a sm o s t p r o b a b l et w o - a d d i t i v e c o n s t r a i n e dp a t h ( m e r i = a c p ) p r o b l e m t os o l v ei t ，w e f o l l o wap r o b a b i l i s t i ca p p r o a c ha n dp r o p o s ea l la l g o r i t h mc a l l e dm p t a c p a i ng e n e r a l ， m p t a c p au s e sp r e - a n do n - d e m a n dc o m p u t a t i o na l o n gw i mb o t l ll i n e a ra n dn o n l i n e a r s e a r c ht e c h n i q u e s i nc o n t r a s tt op r e v i o u sa l g o r i t h m su s i n gs i m i l a rt e c h n i q u e s ，m e t a c p a t a k e si n t oa c c o u n tt h ei n a c c u r a c i e sa l o n gw i t l ln e wb o u n d sa n dh e u r i s t i c si n c l u d i n gl o o k a h e a d ，d o m i n a n c ep r o b a b i l i t yt h a tc o n t r i b u t et h el o wa v e r a g ec o m p u t a t i o nc o s t e x t e n s i v e s i m u l a t i o n ss h o wt h a tm p t a c p ab e h a v e sw e l li nt h ep r e s e n c eo f i n a c c u r a t es t a t ei n f o r m a - t i o n i ti sv e r ye f f i c i e n tw h e na v e r a g ec o m p u t a t i o nc o s t ，r e s p o n s es p e e da n ds u c c e s sr a t eo f n d i n gaf e a s i b l ep a t ha r et a k e ni n t oc o n s i d e r a t i o n 1 1 1 ed i s s e r t a t i o ns t u d i e st h o r o u g h l yt h ep r o b l e m so fd e s i g n i n ge f f i c i e n tq o s ra l g o - r i t h m s p o p fp r o p o s e di nt h i sd i s s e r t a t i o np r o v i d e st h e o r e t i c a lf o u n d a t i o nt oe v a l u a t i n g a n dg u i d i n gt h ed e s i g no f r o u t i n ga l g o r i t h m st h a ts u p p o r tq o s q o s ra l g o r i t h m sp r o v i d e d i nt h i sp a p e rh e l pt og i v i n go n l yn o th i g h e rs u c c e s sr a t ei nn d i n gf e a s i b l ep a t h sb u ta l s o s h o r t e rr e s p o n s et i m e t h er e s u l t so fo u rs t u d ys h o wt h a tt h e s ea l g o r i t h m sc a nb eu s e di n n e x tg e n e r a t i o nn e t w o r k si nv a r i o u sc a s e s k e y w o r d s ：q o s r ，p a r e t oo p t i m a l ，q o sm e t r i cs p a c e ，p o p er s p , m c p , m c o p , n o r - m a lm e a s u r e ，c o v e rp r o b a b i l i t y , l o o ka h e a d 第页 国防科技大学研究生院学位论文 插图目录 1 1i pq o s 研究框架中的三个逻辑组成部分 1 2 论文的组织结构示意图 2 1 路径p 和路由请求c 都对应q o s 度量空间中的点 2 2 向量v 的覆盖区域和支配区域。 2 3 p 和g 确定的可行区域 2 4 p 和q 确定的不可行区域。， 2 5 部分p a r e t o 最优点不能对q o s 度量空间进行完全划分 2 6 基于两个p a r e t o 最优点的q o s 度量空间划分 2 7 基于两个边界p a r e t o 最优点的q o s 度量空间划分 2 8 路由请求落在n p 完全区域时可行性的不确定性 2 9 部分p a r e t o 层的分布 2 1 0 n p 完全区域大小随m 位置变化情况 2 1 1 凸p a r e t o 最优点 2 1 2p a r e t o 最优点的分布范围 2 1 3 线性搜索方法找到的p a r e t o 最优点的可能分布范围 2 1 4 假定d i j k s t r a 算法在搜索方向7 上找到t p 3 时的情况 2 1 5 不同方向上的搜索可能发现同一条路径 2 1 6 非线性搜索可以找到非凸的p a r e t o 最优点 2 1 7 非线性搜索可能带来的冗余计算 2 18 p a r e t o 摄优点的位置对q o s 度量空间重新划分的影响。 3 1m e f p a 算法执行了大量的冗余计算， 3 2 定理3 1 的直观解释 3 3d m c p 算法描述 3 4d m c a 算法的搜索过程 3 5d m c a 算法描述， 3 6d m c a 算法在不同贪婪系数下的绝对性能 3 7d m c a 算法在g c = 0 5 , 0 6 ，0 7 时的绝对性能 3 8d m c a 与m e f p a 算法绝对性能的比较 第v 页 ： 加拍甜筋拍打勰凹如孔粥粥”弛弼扣 舛非铂卯钙n钉铊 ， ， ， ， ， ， ， ， ， ， ， ， ， 国防科技大学研究生院学位论文 3 9 路由请求在q o s 度量空间中的大致分布范围 5 3 3 1 0 算法相对计算复杂性比较 5 4 3 1 l h d s a 算法搜索结果的记录策略 5 5 3 1 2h d s a 算法的搜索策略5 5 3 1 3h d s a 算法描述5 7 3 1 4c h c c k _ b p s 函数5 8 3 1 5 算法绝对性能比较 5 9 3 1 6 算法相对计算复杂性比较， 6 0 4 1 n b i 口通过改变卢的值，可以生成不同的近似p a r e t o 最优点 6 6 4 2 二维q o s 度量空间中 的直观意义 6 7 4 3 路径长度随法线的变化情况6 8 4 4n m 埘c p 算法，7 0 4 ，5 p r o _ c o m p u t a t i o n 函数。，。， 7 1 4 6c h e c k _ f e a s i b i l i t y 函数7 1 4 7 p r e p a r a t i o n 函数7 2 4 8 经过路由请求c 自钞= 一x - 1 - 1 的法线搜索范围 7 2 4 9 n m _ d i j k s t r a 算法的松弛过程7 3 4 。l o 经过路由请求c 的法线的搜索范围。，。 7 4 4 1 l 基于n m 上e n 和m i i 心v i a x 长度的非线性搜索7 5 4 1 2 酽中宽松路由请求和严格路由请求的大致分布范围 7 7 4 1 3 两约束下采用w a x m a n 随机网络图时，算法成功率比较 7 8 4 1 4 两约束下采用l a t t i c e 网络图时，算法成功率比较 7 8 4 1 53 、4 约束下采用w a x m a n 随机网络图时，算法成功率比较。7 9 4 1 6 3 、4 约束下采用l a t t i c e 网络图时，算法成功率比较， 7 9 4 1 7 采用w a x m a n 随机网络图时的p a r e t o 前瞻特性评估 8 0 4 1 8 采用l a t t i c e 网络图时的p a r e t o 前瞻特性评估 8 l 4 1 9 n m m c p 算法的响应时间和在线计算代价评估( w a x m a n ) 8 2 4 2 0 n m j a c p 算法的响应时间和在线计算代价评估( l a t t i c e ) 8 2 5 1 精确网络状态信息下q o s 度量空间的划分 5 2 不精确网络状态信g t q o s 度量空间的划分 5 3 不精确网络状态信息t q o s 度量空间的划分 8 7 8 7 8 8 第v i 页 国防科技大学研究生院学位论文 5 4 q o s 度量的实际值在均值周围的近似分布范围 8 9 5 5m p t a c p a - l l c a 及m p t a c p a n l p l f 的第一阶段搜索过程 9 4 5 6m p t a c 队h d s a 第二阶段的搜索过程。9 4 5 7 m p 1 a c p a 算法描述 9 6 5 8 p r e c o m p u t e 函数9 7 5 9 h a n d l e p r e c o m p u t e 函数9 8 5 1 0o e t _ p r o b 函数9 9 5 1 1 c r r 和l r r 的大致分布范围。，1 0 1 5 1 2 采用w a x m a n 随机网络图时的算法成功率比较1 0 2 5 1 3 采用w a x m a n 随机网络图时，信息不精确度对算法的影响1 0 3 5 1 4 采用l a t t i c e 网络图时的算法成功率比较1 0 4 5 1 5 采用l a t t i c e 网络图时，信息不精确度对算法的影响1 0 5 5 1 6 采用w a x m a n 随机网络图时，算法平均计算代价的评估，1 0 6 5 1 7 采用l a t t i c e 网络图时，算法平均计算代价的评估1 0 6 5 1 8 采用w a x m a n 随机网络图时，界约束对平均计算代价的影响1 0 7 5 1 9 采用w a x m a n 随机网络图时，信息不精确度对界有效率的影响1 0 7 5 2 0 采用l a t t i c e 网络图时，界约束对平均计算代价的影响1 0 8 5 2 l 采用l a t t i c e 网络图时，信息不精确度对界有效率的影响，。1 0 8 5 2 2 路径p 、g 及路由请求在q o s 度量空间中的位置关系，1 1 0 5 2 3 d d 、c ( 功、d ( 咖以及c ( 咖的分布状况1 1 0 第v i i 页 国防科技大学研究生院学位论文 第i x 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一圊工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 固挂旦q 煎堕直簦鎏盟查 学位论交作者签名：捡当兰日期：7 矿叮年砂月中日 学位论文版权使用授权书 本人完全i 解国防科学技求大学有关保留使扁学位论文的规定。本人授权 囤防稃学技术大学可以儇留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借闻：可以将学位论交的全部或部分内容编入有关数据 库进行检索可以采用影印、缩印或扫描等蔓斟手段t 寰存、汇编学位论文。 f 深密学位论文在解密后适用本授权书。) 学位论文题目：旦拉里q 鳗整由簋造壁盈 学位论文作者签名 作者指导教师签名 日期： 矿哆夺p 月尹日 日期：列r 年4 月z 日 国防科技大学研究生院学位论文 第一章绪论 大量网络服务，尤其是交互式网络多媒体应用的出现，要求因特网提供一定级别 的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 保证。迄今为止，q o s 还没有标准定义，相关的研究 组织和机构都给出了自己的定义方法，但是这些定义在本质上大同小异。比如，q o s 论 坛给出的定义为：网络组件为业务和服务需求提供一定级别保障的能力。国际电信联 盟( i n t e r n a t i o n a l t e l e c o m m u n i c a t i o n s u n i o n ) 给出的定义为：决定用户满意度的服务性 能的整体表现。在r f c 2 3 8 6 1 1 中则描述为：q o s 是网络在传输数据流时要求满足的一 系列服务请求，具体可量化为带宽、时延、时延抖动等。目前的i p 网络仅仅提供尽力而 为( b e s t e f f o r t ) 服务。这种服务对各种业务不加任何区分，不能保证报文到达目的节 点，即使到达也不能保证报文的到达顺序。为了提供q o s 保证，研究者在网络的不同层 次进行了研究。q o s 路由为q o s 研究框架中的重要组成部分，旨在提高网络层的q o s 能 力。 1 - 1 课题研究的背景及意义 本课题的研究计划来源于国家自然科学基金项目“下一代网络体系结构模型及具 超高速网络交换路由研究”和国家9 7 3 重大基础研究项目“新一代互连网路由与交换 研究”以及“十五”国防预先研究项目。 1 1 1q o s 研究框架 日益增多的语音交流、视频会议、网络游戏以及其它多媒体应用，使得因特网正 从尽力而为的网络，进化到更加注重任务的、以一致方式为音频、视频及数据应用提供 不同等级服务质量的整合网络。特别是有严格q o s 要求业务的h 现，如交互式实时多 媒体业务，为q o s 的研究提供了极大的动力。因而，学术及工业上的研究者对网络能否 提供q o s 能力非常关注，并为此作了大量的研究囝【3 1 。然而，目前因特网提供q o s 的能 力仍然有限，其中重要原因之一是缺乏既有效又实用的解决手段。另外，q o s 供给既涉 及到技术上的因素，也涉及到规范上的因素【1 。在研究q o s 体系结构、机制以及协议的 过程中，发现了一些颇具挑战性的问题，如q o s 路由问题。为了能够提供良好的q o s j j l i 务，同时避免对挑战性问题的研究，一些学者提出在目前尽力而为机制的基础上，通 过提供大量带宽来实现q o s 保证。这种想法在某种程度上似乎可行，然而，实际应用 中的高代价及低效益使得它不可能被广法采用。2 0 0 4 年s i g c o m m 奖获得者s i m o n s l a m 第1 页 国防科技大学研究生院学位论文 在s i g c o m m 0 4 的k e y n o t es p e e c h 5 l 中指出，这种过度供给c o v e r - p r o v i s i o n s i n g ) 的做法 只能用于暂时缓解对q o s 网络的需求，而不能成为问题最终的解决手段。 目前，对因特网q o s 的研究框架在逻辑上可以分为三个部分，即控制平面，数据 平面以及管理平面嘲，见图1 1 。 图1 1i pq o s 研究框架中的三个逻辑组成部分 控制平面主要处理与传送业务的路径相关的问题，主要包括准入控制、q o s 路由 和资源预约等机制。准入控制的主要目标是新业务不能使网络过载，也不能影响当前 正在传送业务的性能。q o s 路由主要关注满足业务需求的路径选择问题，它仅仅提供 选择可能满足业务需求路径的手段。为了保证被选择的路径提供要求的性能，q o s 路 由往往与资源预约一起使用【孙。数据平面包含直接处理业务数据的各种机制，如缓冲 区管理、拥塞避免、报文标记以及排队与调度等。管理平面的主要功能是操作、监督 和管理数据流的各个方面。 可以看出，q o s 路由是整个q o s 研究框架中的重要组成部分【8 1 ，它主要研究满足某 个流q o s 需求的路径选择问题。路径选择过程需要了解业务流需求和特性，以及可用的 网络资源。这些信息的获得和发布需要借助于一些信令协议，如资源预约协议可用来 传播业务流的需求和特性；因特网工程任务组( i e t f ) 对开放最短路径优先( o s p f ) 协议的扩展 9 d 0 l ，可用来获得可用的网络资源信息。在较长时间内网络流量模式变化 比较缓慢时，q o s 路由可以用来实现各种流量工程甘标。此时，q o s 路由还需要考虑流 第2 页 国防科技大学研究生院学位论文 量特性以及策略约束1 等条件，这种广义的q o s 路由也被称为约束路由t 6 1 t 1 2 】。 1 1 2q o s 蹯由 q o s 路由包含两个实体【b 1 1 4 ：即路由协议和路由算法。 路由协议主要承担网络状态信息的捕获、当前可用的网络资源以及用户业务信 息，并把这些信息向整个网络发布，即负责收集与发布网络及业务信息。此实体主要考 虑的问题有：信息的发布机制，路由协议给网络带来的额外负担，路由器所维护信息的 不精确性等。由于存在各种各样的q o s 度量指标，使得上述问题变得更加复杂1 1 5 1 6 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 路由协议提供的网络状态信息，选择一条最适合传送业务的路径，另外， 最大化网络资源利用率也是其重要目标之一。 1 1 3 i pq o s 体系结构对q o s 路由的需求 i pq o s 是在当前i p 协议的基础上，在不影响其相关特性的情况下，通过修改i p 协 议或补充其它机制在i p 层实现q o s 。一般来讲，i pq o s 的目的是为因特网应用提供不 同质量的服务，并根据应用要求保证服务性能【1 7 】。为实现i pq o s ，i e t f 提出了多种i p q o s 体系结构，主要包括：( 1 ) 集成服务体系结构( i n t s e r v ) 0 8 1 ；( 2 ) 区分服务体系结构 ( d i f f s e r v ) 1 9 1 ；( 3 ) 多协议标签交换( m p l s ) 2 0 】【2 1 1 。 i n t s e r v 是较早出现的i p 网q o s 体系结构之一。i n t s e r v 体系结构在流的等级上区分 业务，在流等级上预约资源。为了保证严格的服务性能，i n t