（通信与信息系统专业论文）新标记交换体制的qos保证技术研究.pdf

摘要 随着因特网的迅速发展，包括实时业务在内的多种业务大量接入因特网。这时， 传统的i p v 4 体制不再适应网络发展的需要，如地址资源缺乏、路由表规模大、分 组转发速度慢、网络提供服务质量的能力不足等。为了使因特网体制更加适合未 来网络和业务发展的需要，新的网络体制不断出现，而新标记交换体制一区域标 记交换体制就是这种环境下提出的。 区域标记交换体制是在i p v 4 分组与数据链路层帧之间插入一个短的、长度 定的交换标记来实现分组转发。区域标记交换体制引入了区域编码的概念，区域 编码不仅可以唯一标识一个地理区域或管理域，而且能够将因特网本身具有的层 次特征充分地体现出来。本文主要研究了区域标记交换体制的地址分配，以及为 用户应用提供服务质量保证的技术，主要研究成果如下： 1 通过对全球大部分国家和地区的面积、人口、经济水平以及经济发展潜力 进行分析，并借鉴p v 4 、口v 6 地址以及电话号码分配的优点，本文首先提出了 套简单的、具有适应性和灵活性的层次化区域编码分配方案，它在充分体现冈特 网固有层次结构的基础上，不仅可以增加可分配的网络地址，而且能够最大限嫂 地利用编址空间。 2 在区域编码分配方案的基础上，研究了应用于此方案的路由表组织方式、 路由协议和路由算法。根据区域编码的特点，骨干路由器的路由表规模可以被大 规模地缩减，而且避免了最长前缀匹配路由查找方式。这些特点可以提升路山器 的分组转发速度，为保证服务质量提供良好的基础。同时，计算机仿真结果表明， 相对于传统路由协议，区域标记交换体制下的路由协议具有较短的路由收敛时叫i 和较少的路由开销，并具有良好的扩展性。 3 依据区域标记交换体制的特点，研究了一种以带宽为度量标准的分_ 式 q o s 路由算法，它根据输出链路可用带宽与带宽请求的关系选择下一跳链路。这 种算法不仅具有计算简单、链路开销小的优点，而且可以减少网络处于重负荷时 所产生的资源碎片，接纳更多的业务。同时，通过确定本算法的启动门限，可以 在保证算法性能的同时，大大降低路径建立对延。计算机仿真结果证明了这种辣 法的正确性和高效性。 4 如何在确保服务质量的前提下充分利用网络资源，这是i s p 关心的问题， 也体现了区域标记交换网络性能。从这个角度出发，首先根据优化理论提出了 种路径级资源分配算法。在其基础上，并结合链路拓扑位置及不同边缘结点汴入 流量等因素，又研究一种保证网络负载均衡的资源分配算法。它通过量化的路径 选择以及合理的资源调配，可以在保证服务质量的同时，实现网络资源的充分利 用。 5 研究了针对区分服务网络中时延敏感业务的接纳控制算法。根据区分服务 网络中用户业务的端到端时延上界，提出了接纳准则以及带宽分配算法。它不仅 保证用户业务的端到端时延不超过确定的上界，而且能够比较充分利用网络资源。 这个算法运算简单，并具有与区分服务一致的可扩展性。 6 研究了一种针对i e e e8 0 2 1 i e 标准中e d c f 机制的改进算法，它依据时间 限选择接入无线信道的m a c 帧并计算其竞争窗，不仅可以确保时延敏感业务的接 入时延，而且能够避免同一站点内不同接入类别的信道访问冲突。此外，该算法 还采取了以概率丢弃时间紧迫分组的措施，即使在网络处于较重负荷时，整个无 线信道的吞吐率也没有明显恶化。 关键词：区域标记交换体制 分布式q o s 路由q o s 划分区分服务接纳控制 a b s t r a c t a st h er a p i dg r o w t ho f t h ei n t e m e t ，a l lk i n d so f t r a f f i c ，i n c l u d i n gr e a lt i m es e l 。v i c e s g oi n t o t h en e t w o r k t h ep r o b l e m se x i s t i n gi nt h et r a d i t i o n a li p v 4a r c h i t e c t u r e m r e x a m p l et h es c a r c i t yo fn e t w o r ka d d r e s s e s ，t h el a r g es i z eo fr o u t i n gt a b l e ，t h el o ws p e e d o fp a c k e tf o r w a r d i n ga n dt h el e s sc a p a b i l i t i e so fp r o v i s i o n i n gq o s ，c a nn o ts a t i s f yt h e r e q u i r e m e n t s o ff u t u r ei n t e m e tf o rs o l v i n gt h e s ep r o b l e m s s o m en e wn e t 、o 、 a r c h i t e c t u r e sh a v eb e e nd e v e l o p e d ，i n c l u d i n gt h en e wl a b e ls w i t c h i n gs y s t e m r e g i , n c o d el a b e ls w i t c h i n g ( r c l s ) r c l si saf a s t f o r w a r d i n gm e c h a n i s ms i m i l a rt om p l s ( m u l t i p l ep r o t o c o ll a b e l s w i t c h i n g ) h o w e v e r , d i f f e r i n gf r o mm p l s ，i ti n t r o d u c e saw h o l en e wc o n c e p t ，r c g t o l l c o d e t h er e g i o nc o d ei san e t w o r ka d d r e s s ，w h i c hu n i q u e l yi d e n t i f i e ss o m ep o r t i o n ( 订 t h eh t e m e t ，ag e o g r a p h yd i s t r i c to ra na d m i n i s t r a t i o nd o m a i nm o s ti m p o r t a n t l y 。l r e g i o nc o d ei sa b l et oi l l u s t r a t et h ei n h e r e n th i e r a r c h i c a lc h a r a c t e r i s t i c so ft h eh l t e l1 1 c i nt h i sd i s s e r t a t i o n ，t h em e t h o df o rr e g i o nc o d ea l l o c a t i o na n dt h et e c h n i q u e si b , p r o v i d i n gq o sg u a r a n t e e s a r es t u d i e d t h em a i nr e s e a r c ha c h i e v e m e n t s0 1 1t h i s d i s s e r t a t i o na r ea sf e l l l o w s ： 1 b a s e do nt h ea n a l y s i so ft h ea r e a s ，p o p u l a t i o n s ，e c o n o m i e sa n dd e v e l o p m e n t p o t e n t i a l o fm o s tc o u n t r i e si nt h ew o r l da n dt h ea l l o c a t i o nf e a t u r e so fi p v 4 ip 、f 、 a d d r e s s e sa n dt e l e p h o n en u m b e r s an o v e lm e t h o df o rr e g i o nc o d ea l l o c a t i o n 、1 1 】1 a d a p t i v i t ya n df l e x i b i l i t yi sd e v e l o p e di nt h i sp a p e r , w h i c hc a ne f f i c i e n t l yu t i l i z ei h c a d d r e s ss p a c ew h i l er e p r e s e n t i n gt h ei n t e m e t h i e r a r c h y 2 o nt h eb a s i so ft h i sm e t h o df o rr e g i o nc o d ea l l o c a t i o n ，t h e c o r r e s p o n d i n g r o u t i n gt a b l es t r u c t u r e ，r o u t i n gp r o t o c o lm a da l g o r i t h ma r ea l ls t u d i e d b e c a u s eo ft h c h i e r a r c h i c a lp a r t i t i o no ft h ei n t e r n e t ，t h es i z eo fr o u t i n gt a b l ea tc o r er o u t e r sc a nb c g r e a t l yr e d u c e d ，a n dt h et r a d i t i o n a ll o n g e s tp r e f i xm a t c h i n gi nr o u t el o o k u pi sa l s o a v o i d e d a l lt h e s ea d v a n t a g e sa r e c a p a b l eo fa c c e l e r a t i n gp a c k e tf o r w a r d i n g ，w h i c h b e n e f i t st h eq o sp r o v i s i o n si nr c l sn e t w o r k s t h es i m u l a t i o nr e s u l t sa l s os h o wt l l u l d i f f e r i n gf o n nt r a d i t i o n a lr o u t i n gp r o t o c o l s ，t h eo n ei nr c l sn e t w o r k sc a nn o to n l 3 - s h o r t e nt h ep e r i o do fb e c o m i n gs t a b l ef o rr o u t i n gt a b l e sw h e nt h et o p o l o g yo ft h e n e t w o r kc h a n g e s ，b u tl a r g e l yl e s s e nl i n kb a n d w i d t ha n d p r o c e s s o ro v e r h e a d m a i n t a i n i n gt h e s ee n t f i e s ， 3an o v e ld i s t r i b u t e dq o sr o u t i n ga l g o r i t h mi nr c l sn e t w o r k s ，t h em e t r i co f w h i c hi sb a n d w i d t h ，i sd e v e l o p e d t h i sa l g o r i t h mf e a t u r e st h es e l e c t i o no fo u t p u tl i n k a c c o r d i n gt o t h e r e l a t i o n s h i p b e t w e e nt h eb a n d w i d t hr e q u e s ta n dt h ea v a i l a b l e b a n d w i d t ho no u t p u tl i n k s ，n o to n l yi tk e e p st h em e r i t so fs i m p l i c i t ya n dl o wl i n k o v e r h e a di nt r a d i t i o n a ld i s t r i b u t e dq o sr o u t i n ga l g o r i t h m s ，b u ta l s oc a r lr e d u c er e s o u r c e f r a g m e n t sa n da d m i tm o r es e r v i c e si n t oan e t w o r kw i t hh e a v yl o a d m o r e o v e r , t h es t a r t t h r e s h o l do ft h i sa l g o r i t h mc a ns h o r t e nt h ep a t he s t a b l i s h m e n td e l a yw h i l ek e e p i n g p e r f o r m a n c e t h ee x t e n s i v es i m u l a t i o nr e s u l t sa l s ov a l i d a t ei t sc o r r e c t n e s sa n d e f f i c i e n c y 4t h ei n t e r n e ts e r v i c ep r o v i d e r sf a c eas e v e r ec h a l l e n g et h a th o wm a x i m u m n u m b e ro fu s e r sc a nb ea d m i t t e di n t on e t w o r k sw i t hq o sg u a r a n t e e s ，w h i c ha l s o d e m o n s t r a t e st h ep e r f o r m a n c eo fr c l sn e t w o r k s f r o mt h i sp o i n t ，a na l g o r i t h mf o r p a t h l e v e lb a n d w i d t ha l l o c a t i o ni s p r o p o s e d f i r s t a c c o r d i n gt o t h e o p t i m i z a t i o n p r o g r a m m i n gt h e o r y t h e n ，o nt h eb a s i so f i ta n dw i t hs o m en e t w o r kf a c t o r s ，i n c l u d i n g l i n kt o p o l o g yp o s i t i o n sa n di n j e c t e dt r a f f i ca te d g en o d e s ，t a k e ni n t oc o n s i d e r a t i o n ， a n o t h e ra l g o r i t h mf o rn e t w o r kl e v e lb a n d w i d t ha l l o c a t i o nw i t hl o a d b a l a n c ei s d e v e l o p e dt o o t h i sa l g o r i t h mf e a t u r e sq u a n t i t a t i v e r o u t es e l e c t i o na n da d a p t i v e b a n d w i d t ha l l o c a t i o n ，a n di sa b l et op r o v i d ed e t e r m i n i s t i cq o sg u a r a n t e e sw h i l e u t i l i z i n gn e t w o r kb a n d w i d t he f f i c i e n t l y 5t h ea d m i s s i o nc o n t r o la l g o r i t t u n sa i m i n gt od e l a ys e n s i t i v es e r v i c e sa r es t u d i e d ， b a s e do nt h ee n d t o e n dd e l a yu p p e rb o u n do fau s e rf l o wi nd i f f s e r vn e t w o r k s ，t h e a d m i s s i o nc r i t e r i o na n di t sm e t h o df o rb a n d w i d t ha l l o c a t i o na ts e r v i c ec l a s sl e v e la r e d e v e l o p e d n o to n l yc a l li tp r e v e n tt h ee n d - t o e n dd e l a yo fa d m i t t e du s e rf l o w sf r o m v i o l a t i n gt h ea l l o w e du p p e rb o u n d ，b u tm a k ef u l l u s eo fn e t w o r kb a n d w i d t h m o r e o v e r ， t h i sa l g o r i t h mi sv e r ys i m p l ea n dp o s s e s s e st h es c a l a b i l i t yc o n s i s t e n tw i t hd i f f s e r v 6 t h ee d c fs c h e m ei ni e e e8 0 2 1 1 ew l a ns t a n d a r d si si m p r o v e d d i f f e r i n g f r o me d c f , t h em e n d e da l g o r i t h mc a r ld e t e r m i n i s t i c a l l ys e l e c ts o m ef l a m ea c c e s s i n g m e d i aa n dc o m p u t e si t sc o n t e n t i o nw i n d o wa c c o r d i n gi t sd e l a yd e a d l i n et h e r e f o r e ，t h e c o l l i s i o n sa m o n gd i f f e r e n ta c c e s sc a t e g o r i e si nt h es a l n ew l a ns t a t i o na r ea v o i d e d ，a n d t h ef r a m e st o t a la c c e s sd e l a yi sg u a r a n t e e d b yt h em e a n so fp r o b a b i l i s t i cd r o po ft i m e s t r i n g e n tf r a m e s ，t h et o t a lt h r o u g h p u to fw i r e l e s sc h a n n e li sn o td e g r a d e de v e nw h i l e h e a v i l yl o a d e d k e y w o r d s ：r c l s d i s t r i b u t e dq o sr o u t i n g q o sp a r t i t i o n d i f f s e r v a d m i s s i o nc o n t r o l q o s a r m m p l s v p i v c i a a l l d p l s p f e c r c l s i n t s e r v d i f f s e r v r s v p p h b e f i s p s l a d w d m v c w f q g p s p g p s w f q d e l a v e d d o s p f e a p a e s s l s s 缩略词 q u a l i t yo fs e r v i c e a s y n c h r o n o u st r a n s f e rm o d e 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 v i r t u a lp a t hi d e n t i f i e r v i r t u a lc h a n n e li d e n t i f i e r a t m a d a p t i v el a y e r l a b e ld i s t r i b u t i o np r o t o c 0 1 l a b e ls w i t c h i n gp a t h f o r w a r d i n ge q u i v a l e n c ec l a s s r e g i o nc o d el a b e ls w i t c h i n g i n t e g r a t e ds e r v i c e d i f f e r e n t i a t e ds e r v i c e r e s o u r e er e s e r v a t i o np r o t o c o l p e rh o pb e h a v i o r e x p e d i t e df o r w a r d i n g i n t e r n e ts e r v i c ep r o v i d e r s e r v i c el e v e la g r e e m e n t d e n s i t i v ew a v e l e n g t h d i v i s i o nm u l t i p l e x i n g v i r t u a lc l o c k w e i 曲t e df a i rq u e u e i n g g e n e r a lp r o c e s s o rs h a r i n g p a c k e t ( j p s w o r s t c a s ef a i rw f q d e l a ye a r l i e s td e a d l i n ed h e o p e ns h o r t e s tp a t hf i r s t e q u a la l l o c a t i o n p r o p o r t i o n a la l l o c a t i o n e q u a ls l a c ks h a r i n g l o a d - b a s e ds l a c ks h a r i n g 服务质量 异步转移模式 多协议标记交换 虚通道标谚 虚通路标识 a t m 适配层 标记分发协议 标记交换通路 转发等价类 区域标记交换 综合服务 区分服务 资源预留协议 每跳行为 加速转发业务类 因特网服务提供向 、【k 务级别协定 密集波分复用 虚时钟 加权公平排队 通用处理器共窖 分组化的g p s 最差情况公平的：l j 权公平排队 最短时问限优先 丌放最短路径优先 等均分配算法 比例分配算法 等松弛量其享算法 基于负载的松弛撤 【p b b w l a n m a c c s m a c d b t c w i f s n a t c ) r r i p b g p r c r p p e r a n e r a d n e r a e a b d s c p a c d s s s m e a s u r e dp r o b a b i l i t y b a n d w i d t hb r o k e r w i r e l e s sl o c a la t e an e t w o r k m e d i aa c c e s sc o n t r o l c a r r i e rs e n s em u l t i p l ea c c e s s c o l l i s i o na v o i d a n c e b a c k o f f t i m e c o n t e n t i o nw i n d o w i n t e r - f r a m es p a c e n e t w o r ka d d r e s st r a n s f o i t n c l a s s l e s si n t e r - d o m a i nr o u t i n g r o u t ei n f o r m a t i o np r o t o c o l b o r d e rg a t e w a yp r o t o c o l r e g i o nc o d er o u t i n gp r o t o c o l p a t hl e v e le q u a lr a t i o a l l o c a t i o n n e t w o r kl e v e le q u a lr a t i oa l l o c a t i o n d i s t r i b u t e dn e r a e q u i v a l e n ta v a i l a b l eb a n d w i d t h d i f f s e r vc o d ep o i n t a c c e s sc a t e g o r y d i r e c ts e q u e n c es p r e a ds p e c t r u m 共享算法 测量概率分配算法 带宽带理 无线局域网 媒质接入控制 具有冲突避免的载 波侦听多址接入 退避时间l i t 竞争窗 帧问间隔 网络地址转换 无类别域问路由 路由信息协议 边界网关协议 区域编码路由协议 路径级等比例分配 网络级等比例分配 分布式n e r a 算法 等效可用带宽 区分服务编码点 接入类别 直接序列扩频 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文巾 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名起垫同期w 。，争f 调咱 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证皆 业离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为 西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学 校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保 存论文。( 保密的论文在解密后遵守此规定) 本人签名：塾! 整 导师签名 日期丝豳谚国 趟遁叁日期兰翌! 垒! 卯2 多日 弟一章绪论 第一章绪论 随着因特网( i n t e r n e t ，又称互联网) 的迅速发展，因特网业务已经由单n 7 j 数据业务转向包括语音、视频和交互式数据在内的多种业务。传统的因特网l n ! 提供“尽力而为”服务，这主要体现在以下两个方面：1 ) 网络不限制进入删络的 业务量，而使用高层协议来保证分组的可靠传输：2 ) 各种类型业务的分组倒叫h 中以一种单一的、与其服务质量( q o s ：q u a l i t y o f s e r v i c e ) 要求无关的方式微处 理和转发。显然，这种简单的服务方式非常适合一般数据业务，它使用户以较低 的成本接入因特网，从而促进了因特网的发展。然而，“尽力而为”服务的优，r j i 址 建立在传统数据业务的服务质量要求不高，甚至无服务质量要求的基础上，_ j 1 5 n i 具有较高服务质量要求业务的不断增长就使传统因特网受到严峻的挑l 钱。测此， 如果未来互联网希望延续它现在的成功，必须有效地解决q o s 保证问题。 1 1 未来互联网研究现状 从上世纪8 0 年代丌始，为了从体系结构上克服传统凶特网在提供q o s 倮计 能力上的不足，许多新的网络体制被提出，这其中包括异步转移模式( a t m ： a s y n c h r o n o u st r a n s f e rm o d e ) ，多协议标记交换( m p l s ：m u l t i p r o t o c o ll a b e l s w i t c h i n g ) 技术以及p v 6 ( i n t e r n e t p r o t o c o lv e r s i o n6 ) 技术。 a t m 技术 传统因特网在q o s 保证方面的不足促进了a t m 技术的迅速发展。a t m 魁 种基于虚电路方式的定长分组( 信元) 交换技术。在用户数据被传输 ； ，必坝 首先使用a t m 信令在通信源结点和目的结点之问建立一条使用虚通道标识( v p i ： v i r t u a lp a t hi d e n t i f i e r ) 和虚通路标识( v c i ：v i r t u a lc h a n n e li d e n t i f i e r ) 来代表i r ，4 i ( 一j f ) c t ， v t 0( 1 2 ) 虽然d e l a y e d d 算法的可调度性检查比较复杂，但它在确保分组结点时延方 面是最佳的，而且在所有的调度算法中具有最大的可调度区i 自l t 6 2 】【6 3 1 。 在上述几种分组调度算法中。都需要根据某种规则计算分组的时间标签( v c 算法为虚发送时刻，w f q ( w f 2 q ) 算法为虚完成时刻，而d e d d 算法为时问限) ， 然后将分组插入优先级队列中。表1 2 表明了上述几种算法的时间标签的计算规 则，i 标识服务器号，_ ，为连接号，而k 是分组号。其中，口；，为连接，的第k 个分 组到达服务器i 的时刻，a u x g c , * i 为虚时钟，v t i c k i 为平均分组间隔，i ( d 7 ) 为分 组的虚到达时刻，只：为虚完成时刻，t 为分组长度，谚，为分配的平均服务速率， 殷d ；! ，为期望时延限，x m i n ；为最小分组问隔，d ；为本地时延界。 第一章绪论 表12 不同分组润度算法的时间标签计算 分组调度算法时间标签计算 v c y c ：i 七- m n ：r a u x v c ! i ；+ y ；酞、? w f q 雨1w 产o 甓卜m “吲嘲对n 箬 d e l a y e d d e x d j it m n x t c j i 十d 。，e x d j ? + x m i n j 可以看出，v c 算法、w f q 和w f 2 q 算法时间标签的计算非常相似闪此它 们被通称为w f q l i k e 算法 6 4 o w f q l i k e 算法时间标签的更新只需要一个参数( 、r 均分组间隔或平均服务速率) ，而d e d d 算法时间标签更新需要两个参数：最小 分组间隔和最大允许结点时延。这导致了两个现象：1 ) w f q l i k e 算法的端到? 前 时延与分配的链路带宽耦合。这使w f q 1 i k e 算法为给低吞吐率、高时延要求| | ：j 业务进行服务时会浪费一一定的网络带宽：2 ) d e d d 算法虽然存避免了卜述川题 但是它的可调度性检查要比w f q l i k e 算法复杂得多吲。 q o s 路由 作为一种网络层技术，q o s 路由可以在通信源结点和目的结点之问找到满， 某些q o s 指标( 包括带宽、时延、时延抖动、丢失率、诧费等) 的路径i ”j 。q o s 路由也称为约束路由，主要分为三类：源q o s 路由，分布式q o s 路由耵1j j ：次一t q o s 路由。 ( 1 ) 源q o s 路由 顾名思义，源q o s 路由是在业务的源结点( 一般指用户的接入路山器) ，j j j k 满足q o s 要求的路出计算【”】，因此业务源结点必须知道整个网络拓扑和最新的j t l 络状态信息。所以，在支持源q o s 路由的网络中，丌放最短路径优先( o s p f ： o p e ns h o t e s t p a t h f i r s t ) 【67 j 路由协议是一个很好的选择。 文献 6 8 1 1 6 9 中已经证明：在网络中找到+ 条受任意两个( 或两个以上) d i ( 时延、时延抖动、花费) 或乘性( 丢失率) 指标约束的路径是一个非确定多j | ，! 式时问完全( n p c o m p l e t e ：n o n d e t e r m i n i s t i e p o l y n o m i a l t i m e c o m p l e t e ) 的问越 这意味着，当网络规模比较大时，源q o s 路出路径计算的复杂度非常大刚，n 彬 虑到交互全网状态信息而带来的链路开销，可以认为源q o s 路由存在扩展性箍的 问题【7 “。因此，为了提升源q o s 路由的扩展性，许多算法被提出，主要就是解 儿 计算复杂度和链路，1 ：销问题。 ( a ) 减少链路状态信息的发送量 这类方法包括，基于跳数泛洪和反向路径更新算法 7 2 】。在基于跳数泛洪雏沙 新标记交换体制的q o s 保证技术研究 中，网络结点只向有限跳数范围内分发本地链路状态信息，这样可以减少网络中 发送的链路状态消息数目。此算法基于这样一个假设：在一个很大的网络中，用 户之间的距离越近，它们的通信越多，因此局部网络状态信息是最重要的。而在 反向路径更新算法中，网络结点将本地的链路状态信息只向当前使用该链路的其 它网络结点发送，这样也可以减少整网发送的链路状态消息数目。在这两种算法 中，网络结点仍然保存整个网络的拓扑。 f b l 降低状态信息更新频率 这类方法包括使用不同的链路状态更新触发机制和容忍非精确信息路由。为 了减少链路状态更新消息数目，可以采用基于变化或者基于定时器的路由更新触 发机制 7 3 【7 4 】，前者可以在检测到本地链路状态发生了重大改变后( 如町用带宽的 变化绝对值超过某一门限) 才将链路状态信息向其它网络结点分发：而后者可以 设定连续的链路状态更新消息问的最小时间间隔，确保链路状态更新消息不会频 繁的分发。这两种方式也可以结合起来使用。 降低链路状念消息的更新频率后，必然会导致其它网络结点保存不准确的网 络资源状态信息。基于可靠性的路由和多径路由 7 5 7 6 1 可以提高q o s 路由的成功概 率。虽然源结点没有准确的网络状态信息，但是它可以依据链路状态更新触发机 制计算出某条链路满足服务质量要求的概率。如果再假设各个链路的状态相互独 立，那么就可以计算出某条路径满足端到端服务质量要求的概率。显然，概率越 高的路径就越可靠，因此这种方法称为可靠性路由算法。而多径路由是让不同的 连接请求选择源宿结点f h j 的不同路径，这不仅可以提高q o s 路由的成功概率，而 且可以均衡网络流量。 ( c ) 路径预计算 路径预计算就是在连接请求到达前，计算并保存对应所有目的结点的路径， 这样就可以大大地简化连接请求到达时的操作。路径预计算方法的挑战是：必须 针对同一个目的结点计算多条路径，以便满足不同服务质量要求和实现流量均衡。 由于网络状态的变化会导致预计算的路径失效，在什么时候、如何更新这些预先 计算的路径是此方法的主要挑战 7 ”。文献7 7 中提出了一种基于类别的路径预计 算方法，它将用户的带宽要求划分成几个类别，然后针对每一个目的结点的每一 种带宽类别计算最短的最宽路径。文献 7 8 1 提出了一种粗粒度的链路代价度量标 准，可以有效地降低同一目的结点多条路径的计算复杂度。预计算的路径存储在 一个简单的数据结构中。当用户连接请求到达时，从数据结构中提取满足q o s 要 求的路径，而且使用最新的链路状态信息来验证该路径的可用性。上述两种方法 具有相似的性能。 ( d ) 缓存计算结果 缓存计算结果就是保存上次依据连接请求计算的路径，如果后续到达的连接 第一章绪论 请求具有相同的服务质量要求，就可以直接使用被缓存的路径，避免霞复汁银 在所有的缓存算法中，如果所有被缓存的计算结果都无法满足当前的连接消水 就必须计算新的路径。缓存计算结果方法的主要问题是确定合适的缓存策略。川 如什么时候、如何判断缓存结果失效并更新缓存结果，当缓存满后哪个计算结爪 应被首先删除。文献 7 9 通过比较不同的缓存策略得到下述的结论：结合选抒l ： 宽路径的周期性缓存更新策略可以在降低路径计算开销的同时保持路径计算附r l 能。 ( 2 ) 分布式q o s 路由 区别于源q o s 路由，分布式q o s 路由的路径计算不是在源结点完成， i 王 跳完成的，这与传统的i p 分组路由非常类似 8 ”。当业务源结点收到一个连接晰jj 、 后，它向所有通过可达性测试和q o s 测试的输出端口转发该连接请求。月? - f f 的j 间结点重复这个过程，直至该连接请求到达目的结点。当目的结正i 收到第个迎 接请求后，表明存在满足q o s 要求的路径，确认消息则沿着此路径的反阳蹄轮投 送给源结点。从这个过程可以看出，分布式q o s 路由避免了源q o s 路由z + f l 复j 的路径计算问题。其次，由于分布式q o s 路由只使用本地的链路状态信息，小“ 在链路状态信息不准确的问题，还能够避免了维护全网链路状态的山议外例 但是，分布式q o s 路由同样存在一些问题。首先，由于各个网络结点不“剐、! 全网的链路状态信息，就很难从全局的观点选择一条源宿结点问的最佳路符，件 易造成网络资源的浪费，这将最终导致用户业务服务质量的卜降。其次，相：分n - 式q o s 路由算法中，资源预留过程存在一个中间阶段，即从网络结点转发连拨孙 求消息丌始到其收到相应确认消息或请求失败消息为止。在这段时问内，j 间结点( 包括源结点) 不知道该连接请求是否成功，因此网络资源没有被i | j 。m 留。然而，为了保证确认消息到达时结点有足够的可用资源，部分资源义必铂 被预先保留。如果这段时间较长，就会影响整个网络的资源利用率。 ( a ) c m d r a 算法 文献 8 2 1 中提出了一种c m d r a ( c o n c a v e m e t r i c d y n a m i c r o u t i n g a l g o r i t h m l 算法。它的主要特点是：当源结点或中间结点转发连接请求时，依据输m 链踏的 资源状况进行一定的延时，这样可以使经过带宽最充足路径、或与带宽请求址拔 近路径的连接请求首先到达目的结点。尽管这种方法在一定程度上增加厂蹄仵业 立时延，但它确实可以提高网络资源的利用率。但是，c m d r a 算法只适用r 邶 些只包括带宽要求的q o s 连接请求，而对于那些具有端到端时延要求的连接消求 则无能为力。 ( b ) f l o o d a n d p r u n e 算法 文献 8 3 提出了一种以泛洪、快速剪枝为特点的分布式q o s 路由算法，j ，、 降低那些非路径链路上带宽的占用时问。当一个中间结点无法通过q o s 测试 新标记交换体制的q o s 保证技术研究 它就立即向它的上游结点( 向其首先转发连接请求的结点) 发送剪枝消息，上游 结点就立刻释放相应输出链路上的资源。如果此剪枝消息表明对应于此连接请求 的所有输出端口都收到了剪枝消息，这个上游结点立刻再向它的上游结点发送剪 枝消息。如果一个中间结点收到确认消息，它立刻向其它已发送过连接请求消息 的输出端口发送剪枝消息，并立刻释放输出链路上对应此连接请求的资源；如果 一个结点收到上游结点来的剪枝消息，它立刻向所有的下游结点转发此剪枝消息， 并释放所有资源。通过这种方式，可以缩短分布式q o s 路由的中间阶段，提高网 络资源的利用率。 f 3 1 层次化q o s 路由 层次化q o s 路由是针对源q o s 路由的扩展性问题应运而生的。层次化q o s 路由将一个