（计算机科学与技术专业论文）面向流量工程优化的约束路由算法研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 互联网中传统的尽力而为传送机制和最短路径路由算法实质上存在导致拥塞 的可能。随着互联网规模的日益扩大和用户端接入带宽的不断增加，骨干网发生 拥塞的几率也日益提高。网络拥塞不仅会降低网络性能，而且会使得服务提供商 难以完成对客户的服务水平的承诺。因此该问题引起了研究者们的广泛关注。 流量工程是一种具有重要价值的网络优化技术，它通过优化网络资源的利用 效率来避免网络拥塞。多协议标签交换提供的约束路由技术是流量工程的重要工 具之一。约束路由机制能够显式地指定数据传输路径，使得路由选择算法能够根 据q o s 约束和流量工程优化目标进行路径选择。在路由选择阶段结合流量工程优 化目标，能够从根本上克服当前互联网所使用的最短路径路由带来的拥塞问题， 有效提高网络资源利用率，具有重要的理论意义和应用价值。 本文主要针对流量工程中的最小干涉、负载均衡、最小化网络资源耗费等优 化目标，对单路径的在线和预计算型约束路由算法，多路径约束路由算法这三类 算法进行了研究，取得的主要成绩有： 1 面向流量工程优化的在线约束路由算法 针对m i r a 算法的一个变种1 - m i r a 算法单纯考虑是否存在干涉的特点，提出 了结合负载均衡原则的改进算法i m i r a l b ；针对m i r a 的关键链路划分过于简单 化的特点，提出了反映干涉程度的链路干涉关键度函数和相应的路由算法m i n c f ； 并提出了综合考虑最小干涉、负载均衡和最小化网络资源耗费( 最短路径) 三个 要素，易于动态调节的混合算法h o r a 。上述三种算i 去在路由请求成功率上较之 n e w m i r a 等算法而言都有明显提高。i m i r a l b 算法在k l 或者i s p n e t 等含有常 数个入出口对的拓扑中，性能表现较好。但若入出口对数目快速增长时，甚至所 有结点都可能是入出口结点时，干涉过于复杂，i m i r a l b 和n e w m i r a 等算法性 能下降的比较明显，甚至下降到最短路径算法的水平。而m i n c f 和h o r a 算法 在这种情况下通过参数设置实现对算法行为的调节，可以达到较好的性能水平， 表现出对不同的网络拓扑和请求序列更强的适应性。 2 面向流量工程优化的预计算型约束路由算法 针对在线算法对复杂度有严格限制，良好的优化效果和低复杂度往往难以兼 顾的问题分别提出了两种预计算算法：预计算链路关键度函数的p r e m i n c f 算法 和预计算k 条路径的p r e k m i p 算法。p r e m i n c f 算法具有适用范围广的优点，通 过预计算链路关键度使得算法在具有良好优化效果的前提下，在线复杂度降低， 执行时间较一般在线算法大为缩短。p r e k m i p 算法则预计算k 条路径，然后输入 真实请求序列，按照在各路径上增加该流量负载后网络入出口对最大流之和的变 第i 页 国防科学技术大学研究生院博士学位论文 化情况打分排序。p r e k m i p 算法以运行时间作为折衷，在请求成功率等性能指标 上取得了进一步的提高。 3 面向流量工程优化的多路径约束路由算法 针对现有多路径路由算法大多以负载均衡为目的，较少考虑最小干涉这一问 题，提出了两种考虑了最小干涉的启发式多路径约束路由算法。一种是最小化路 径数目及干涉算法m p n m i ，该算法能够寻找极小数量的最小干涉路径，从而减 轻多路径之间的干涉，以及减轻过多路径带来的信令消息负载压力。另一种算法 最大k 路径最小干涉多路径路由算法m k p m i t s 则更好的兼顾了负载均衡，并能 够在分配路径流量时按照最小干涉和负载均衡目标进行流量分配的优化。 论文对面向流量工程进行优化的约束路由技术进行了深入细致的研究和探 索。所提出的几种约束路由算法在保证请求带宽的前提下，能够根据最小干涉、 负载均衡、最小化网络资源占用等优化目标对路由选择进行优化，从而提高请求 成功率和吞吐量，并实现均衡负载，提高网络资源的使用效率。其研究成果对于 下一代互联网具有良好的理论价值和应用前景。 主题词：流量工程约束路由m p k $ 最小干涉 负载均衡 最小化网络资源占用路由优化 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t t h ei n t e r a c t st r a d i t i o n a lb e s te f f o r ta r e h i t e c t u r ea n ds h o r t e s tp a t hf i r s tr o u t i n g a l g o r i t h mt a k et h er i s ko fc o n g e s t i o ni nn a t u r e w i t ht h ef a s tg r o w t ho ft h ei n t e m e ta n d t h er a p i di n c r e a s eo fa c c e s sb a n d w i d t h ，t h er i s ko fc o n g e s t i o na l s oi n c r e a s e s d r a m a t i c a l l y c o n g e s t i o n sw i l ln o to n l yd o w n g r a d et h en e t w o r k sp e r f o r m a n c e ，b u ta l s o b r e a kt h ei s p sq o s g u a r a n t e e s t i l i si s s u eh a st h e r e f o r ec a u s e dw i d e s p r e a dc o n c e r n t r a f f i ce n g i n e e r i n gi san e t w o r ko p t i m i z i n gt e c h n o l o g yo fg r e a tv a l u e i ta v o i d s c o n g e s t i o nb yo p t i m i z i n gt h eu t i l i z a t i o no fn e t w o r kr e s o u r c e s c o n s t r a i n t - b a s e dr o u t i n g ( c b r ) i s a ni m p o r t a n tt e c h n o l o g yf o rt r a f f i ce n g i n e e r i n gp r o v i d e db ym u l t i p r o t o c o l l a b e ls w i t c h i n g c b rc a ns e l e c tap a t ha c c o r d i n gt oq o sc o n s t r a i n t sa n dt r a f f i c e n g i n e e r i n go b j e c t i v e s b yc o m b i n i n gt r a f f i ce n g i n e e r i n go b j e c t i v e si nt h eq o sr o u t e s e l e c t i o np h a s e ，w ec a nb a l a n c et h et r a f f i c ，r e d u c et h er i s ko fc o n g e s t i o n ，a n di m p r o v e t h eu t i l i z a t i o no fn e t w o r kr e s o u r c e s t h u s ，i th a sg r e a tt h e o r e t i ca n da p p l i c a t i o nv a l u e s i nt h i sp a p e r ，w em a i n l ys t u d i e ds i n g l ep a t ho n l i n ec o n s t r a i n t - b a s e dr o u t i n g a l g o r i t h m s ，p r e c o m p u t i n ga l g o r i t h m s ，a n dm u l t i p a t ha l g o r i t h m st o w a r d sp r i m a r yt r a f f i c e n g i n e e r i n go b j e c t i v e s ，s u c ha sm i n i m u mi n t e r f e r e n c e ，l o a db a l a n c i n g ，a n dm i n i m u m u s a g eo fn e t w o r kr e s o u r c e s o u rw o r kc o n c e n t r a t e so n ； 1 s i n g l ep a t ho n l i n er o u t i n ga l g o r i t h m s i nl i g h to ft h ei m i r aa l g o r i t h m sc h a r a c t e r i s t i co fo n l yc o n s i d e r i n gi n t e r f e r e n c e 嘶n i m i z i n g ，w ep r o p o s e da ni m p r o v e dv e r s i o nn a m e di m i r a l bw h i c hh a sab e t t e r l o a db a l a n c i n g i nl i g h to ft h ep r o b l e mw h e r e i nm i r a sj u d g m e n to nac r i t i c a ll i n km a y b et o os i m p l e ，w ep r o p o s e dan e wl i n kc r i t i c a l i t yf u n c t i o na n dac o r r e s p o n d i n g a l g o r i t h mn a m e dm i n c f o nt h e s eb a s e s ，w ep r o p o s e da na l g o r i t h mn a m e dh o r a w h i c hc a nc o n s i d e ra l lt h et h r e eo b j e c t i v e s ( m i n i m u mi n t e r f e r e n c e ，l o a db a l a n c i n g ，a n d m i n i m u m u s a g e o fn e t w o r kr e s o u r c e s ) a n dc a nb ee a s i l ya d j u s t e db yt h ea d m i n i s t r a t o r s a l lt h e s et h r e ea l g o r i t h m sh a v eb e t t e rr e q u e s ts u c c e s sr a t e st h a nt h en e w m i r aa n d s o m eo t h e rf o r m e ra l g o r i t h m s t h ei m i r a l ba l g o r i t h mp e r f o r m sb e t t e ri nt o p o l o g i e s w h i c hh a v eac e r t a i nn u m b e ro fi n g r e s s e g r e s sp a i r s h o w e v e r , i ft h en u m b e ro f i n g r e s s e g r e s sp a i r si sv e r yb i g ，t h ei n t e r f e r e n c ew i l lb ev e r yc o m p l e xa n dt h e p e r f o r m a n c eo fi m i r a l ba n dn e w m i r aw i l lb es i g n i f i c a n t l yd o w n g r a d e d m i n c f a n dh o r aa l g o r i t h m sc a l lb ea d j u s t e db yt h ea d m i n i s t r a t o r ss ot h e yc a na c h i e v eb e t t e r p e r f o r m a n c e t h e ys h o wb e t t e ra d a p t i v ea b i l i t yt od i f f e r e n tt o p o l o g i e sa n dr e q u e s t s 2 s i n g l ep a t hp r e c o m p u t i n ga l g o r i t h m sf o rt r a f f i ce n g i n e e r i n g i nl i g h to ft h ef a c tt h a ta l lo n l i n ea l g o r i t h mh a ss t r i c tl i m i t a t i o n so nc o m p l e x i t y ，w e p r o p o s e dt w od i f f e r e n tp r e c o m p u t i n ga l g o r i t h m s o n ei st h ep r e m i n c fa l g o r i t h m ， w h i c hp r e c o m p u t e st h el i n kc r i t i c a l i t yf u n c t i o n ，a n dt h eo t h e ri st h ep r e k m i pa l g o r i t h m , w h i c hp r e c o m p u t e sk p a t h s t h ep r e m i n c fa l g o r i t h mh a sb e t t e ra d a p t i v ea b i l i t y i t 第i i i 页 国防科学技术大学研究生院博士学位论文 c u t sd o w no p e r a t i o nt i m ew i t h o u tl o s i n gm u c ho ft h eo p t i m i z a t i o ne f f e c tt h r o u g h p r e c o m p u t i n g t h ep r e k m i pa l g o r i t h mo b t a i n sab e t t e rp e r f o r m a n c ei nr e q u e s ts u c c e s s r a t e sa n dt h r o u g h p u tw i t hac e r t a i ni n c r e a s ei no p e r a t i o nt i m e 3 m u l t i p a t ht r a f f i ce n g i n e e r i n ga l g o r i t h m i nl i g h to ft h ef a c tt h a tm o s to ft h ec u r r e n tm u l t i p a t ha l g o r i t h m sf o c u so nl o a d b a l a n c i n g ，f e wh a v ed o n es oi n i n t e r f e r e n c e m i n i m i z i n g w et h u sp r o p o s e dt w o m u l t i p a t hr o u t i n ga l g o r i t h m s ，n a m e l y ，m p n m ia l g o r i t h ma n dm k p m i t sa l g o r i t h m m p n - m ia l g o r i t h ma t t e m p t st om i n i m i z ep a t hn u m b e ra n di n t e r f e r e n c e i tc a ns e l e c ta m i n i m u mn u m b e ro fm i m m u mi n t e r f e r e n c e p a t h s w h i l e s a t i s f y i n g t h e r e q u e s t b a n d w i d t h ，t h e r e b yr e d u c i n gt h ei n t e r f e r e n c ea n de x t r ac o n t r o lo v e r h e a df o r t h e m u l t i p a t h t h em k p m i t sa l g o r i t h mm i n i m i z e st h ei n t e r f e r e n c ea tm o s tkp a t h s t h i s a l g o r i t h md o e sb e t t e rl o a db a l a n c i n ga n da l s oc o n s i d e r si n t e r f e r e n c em i n i m i z i n gw h i l e s p l i t t i n gt h et r a f f i ca l o n gm u l t i p a t h s t os u mu p ，w et h o r o u g h l yc o n d u c t e dr e s e a r c ho nt r a f f i ce n g i n e e r i n gr o u t i n g t h e a l g o r i t h m sp r o p o s e d i n t h i sd i s s e r t a t i o nc a n o p t i m i z e r o u t es e l e c t i o n ，s u c ha s i n t e r f e r e n c em i n i m i z i n g ，l o a db a l a n c i n g ，a n dm i n i m i z i n go fr e s o u r c eu s a g e t h e r e f o r e ， o u r p r o p o s e da l g o r i t h m sc a ni m p r o v es u c c e s sr a t ea n dt h r o u g h p u tw h i l es a t i s f y i n gt h e r e q u e s tb a n d w i d t h w eb e l i e v et h a to u rc o n t r i b u t i o n sp r o v i d eas o l i dg r o u n d w o r kf o r f u t u r er e s e a r c ha n de n g i n e e r i n gi nn e x tg e n e r a t i o ni n t e m e tb o t hi n t h e o r ya n di n p r a c t i c e k e yw o r d s ：t r a f f i ce n g i n e e r i n g c o n s t r a i n t - b a s e dr o u t i n gm p l s i n t e r f e r e n c em i n i m i z i n gl o a db a l a n c i n g n e t w o r kr e s o u r c eu s a g em i n i m i z i n g r o u t i n go p t i m i z a t i o n 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 在线最小干涉类流量工程路由算法1 8 表2 2 智能型优化算法2 1 表2 3 预计算型流量工程路由算法2 3 表3 1k l 5 s d 拓扑下接受的带宽总量5 3 表3 2k l 5 s d 拓扑下接受的请求总数5 3 表3 3i s p n e t 5 s d 拓扑下接受的带宽总量5 3 表3 4i s p n e t 5 s d 拓扑下接受的请求总数5 3 表4 1k l 5 s d 拓扑下计算8 0 0 0 个请求所需的时间6 6 表4 2i s p n e t 7 s d 拓扑下计算8 0 0 0 个请求所需的时间6 7 表4 3r a n d o m 5 s d 随机拓扑下计算8 0 0 0 个请求所需的时间6 8 表4 4k l 5 s d 拓扑中计算8 0 0 0 个请求所需的时间7 2 表4 5i s p n e t - 7 s d 拓扑下计算8 0 0 0 个请求所需的时间7 3 表4 6r a n d o m 5 s d 随机拓扑下计算8 0 0 0 个请求所需的时间7 4 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 论文结构5 图3 1 最小干涉路径示例3 2 图3 2 具有7 个入出口对的i s p n e t7 s d 拓扑3 6 图3 3i s p n e t 7 s d 拓扑下接受的请求数3 7 图3 4i s p n e t 7 s d 拓扑下接受的带宽总量3 7 图3 5i s p n e t 7 s d 拓扑下链路带宽利用率的标准差3 8 图3 6k l 1 0 s d 拓扑3 8 图3 7k l 1 0 s d 拓扑下接受的请求数3 9 图3 8k l 1 0 s d 拓扑下接受的带宽总量3 9 图3 9k l 1 0 s d 拓扑下链路带宽利用率的标准差4 0 图3 1 0p a r k i n g 1 0 t 拓扑。4 0 图3 1 1c o n c e n t r a t o r 拓扑4 l 图3 1 2d i s t r i b u t o r 拓扑4 1 图3 1 3 具有5 个入出口对的k l 5 s d 拓扑。4 6 图3 1 4k l 5 s d 拓扑下接受的请求数4 6 图3 1 5k l 5 s d 拓扑下接受的带宽总量4 7 图3 1 6k l 5 s d 拓扑下所有入出口对的最大流之和4 7 图3 1 7k l 5 s d 拓扑下链路带宽利用率的标准差4 8 图3 1 8k le d g e 拓扑下接受的请求数4 8 图3 1 9k le d g e 拓扑下接受的带宽总量4 9 图3 2 0k l 5 s d 拓扑下接受的请求数5 1 图3 2 1k l 5 s d 拓扑下接受的带宽总量5 l 图3 2 2 具有5 个入出口对的i s p n e t - 5 s d 拓扑5 l 图3 2 3i s p n e t - 5 s d 拓扑下成功接受的请求数一5 2 图3 2 4i s p n e t 5 s d 拓扑下接受的带宽总量5 2 图3 2 5 场景l 下成功接受的请求数5 5 图3 2 6 场景2 下成功接受的请求数5 5 图3 2 7 场景3 下成功接受的请求数5 6 图3 2 8 场景1 下链路带宽利用率的均值5 6 图3 2 9 场景2 下链路带宽利用率的均值5 7 图3 3 0 场景3 下链路带宽利用率的均值5 7 图3 3 l 场景l 下链路带宽利用率的标准差5 7 第v i i 页 国防科学技术大学研究生院博士学位论文 图3 3 2 场景2 下链路带宽利用率的标准差5 8 图3 3 3 场景3 下链路带宽利用率的标准差。5 8 图4 1k l 5 s d 拓扑下各算法接受的请求数。6 4 图4 2k l 5 s d 拓扑下各算法接受的带宽量。6 5 图4 3k l 一5 s d 拓扑下链路带宽利用率均值6 5 图4 4k l 5 s d 拓扑下链路带宽利用率标准差。6 5 图4 5i s p n e t 7 s d 拓扑下接受的请求数6 6 图4 6i s p n e t 7 s d 拓扑下接受的带宽总量6 6 图4 7r a n d o m 5 s d 拓扑下接受的请求数6 7 图4 8r a n d o m 5 s d 拓扑下接受的带宽总量。6 7 图4 9k l 5 s d 拓扑中各算法接受的请求数。7 0 图4 1 0k l 5 s d 拓扑中各算法接受的带宽量7 0 图4 1 lk l 5 s d 拓扑中链路带宽利用率均值7 l 图4 1 2k l 5 s d 拓扑中链路带宽利用率标准差7 l 图4 1 3i s p n e t 7 s d 拓扑下接受的请求数一7 2 图4 1 4i s p n e t 7 s d 拓扑下接受的带宽总量7 2 图4 1 5r a n d o m 5 s d 拓扑下接受的请求数7 3 图4 1 6r a n d o m 5 s d 拓扑下接受的带宽总量7 3 图5 1k l 5 s d 拓扑下接受的请求数。8 0 图5 2k l 5 s d 拓扑下接受的带宽总量8 1 图5 - 3 k l 5 s d 拓扑下所有入出口对的最大流总量8 1 图5 4k l 5 s d 拓扑下链路带宽利用率均值8 l 图5 5k l 5 s d 拓扑下链路带宽利用率标准差。8 2 图5 6k l 5 s d 拓扑下接受的请求数。8 5 图5 7k l 5 s d 拓扑下接受的带宽总量。8 6 图5 8k l 5 s d 拓扑下所有入出口对的最大流总量8 6 图5 9k l 5 s d 拓扑下链路带宽利用率均值。8 7 图5 1 0k l 5 s d 拓扑下链路带宽利用率标准差8 8 图5 1 1i s p n e t 7 s d 拓扑下接受的请求数一8 9 图5 1 2i s p n e t 7 s d 拓扑下接受的带宽总量一8 9 图5 1 3i s p n e t 7 s d 拓扑下所有入出口对的最大流总量。8 9 图5 1 4i s p n e t 7 s d 拓扑下链路带宽利用率均值9 0 图5 1 5i s p n e t 7 s d 拓扑下链路带宽利用率标准差。9 0 图5 1 6r a n d o m 5 s d 随机拓扑下接受的请求数9 l 第v i i i 页 国防科学技术大学研究生院博士学位论文 图5 1 7r a n d o m - 5 s d 随机拓扑下接受的带宽总量9 1 图5 1 8r a n d o m 5 s d 随机拓扑下所有入出口对的最大流总量9 2 图5 1 9r a n d o m 5 s d 随机拓扑下链路带宽利用率均值9 2 图5 2 0r a n d o m - 5 s d 随机拓扑下链路带宽利用率标准差9 3 第1 x 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除。了文中特别加以标注和致谢的地方外，论文中不包含其他入已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 耍囱逸量王蕉选i 丝数约塞整由篡羹班窒 学位论文作者签名： 墨查聋 日期：加。7 年，p 月1 1 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；g r , , z 将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 叁! 鱼生 作者指导教师獭：勤爷梦 日期：加d 7 年，d 月1 1 日 日期：幽一月，日 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 研究背景 1 1 1 网络拥塞的危害及流量工程技术的重要意义 近年来，互联网产业得到了快速发展，网络规模日益扩大，用户人数不断增 多，接入带宽不断增长，p 2 p 、视频点播等新兴业务不断涌现。这些因素推进了互 联网的发展。视频点播等新兴业务的不断涌现，同时也对网络的延时、丢包率等 服务质量性能提出了更高的要求。拥塞的发生，很容易使得网络对客户的延时等 参数的保证无法实现。但是互联网中传统的尽力而为传送机制和最短路径路由算 法本质上存在导致拥塞的可能。而用户终端接入带宽的增长、用户规模的不断扩 大、p 2 p 等长持续时间大数据量的业务对骨干网造成的压力，诸多因素使得互联网 拥塞的风险越来越大。因此这个问题引起了研究者们的广泛关注。固然上述拥塞 问题的解决需要网络服务提供商升级他们的基础设施。但硬件升级需要昂贵的代 价，且需要时间来完成。而且很多时候网络硬件设施能够满足需要，只是由于资 源利用不均衡造成瓶颈现象。典型的有两种原因：一是负载分配不均衡，有的链 路负载水平很高，导致在局部形成瓶颈，同时有的链路却负载少，利用率较低。 第二个原因就是在m p l s 核心网入出口对确定的情况下，不同入出口对之间存在 不必要的竞争某些链路，从而堵塞其它入出口对之间通路的现象。流量工程( t r a f ! f i c e n g i n e e r i n g ，t e ) 通过对现有网络资源利用的优化调节，达到网络资源的优化利 用，降低网络拥塞几率，是一种非常有价值的网络优化技术。 r f c 3 7 0 2 指出，流量工程是关于性能评估和性能优化的网络工程技术。包括 对互联网流量的测量、特征化、建模和控制技术【1 1 。流量工程研究开展以来，一直 分为两大方向，即无连接的流量工程和面向连接的流量工程，各有优缺点。无连 接的流量工程的实施，基于现有的无连接的、无服务质量保证的、尽力而为的i p 网络和i p 路由协议。其仍然基于逐跳路由模型。每个结点独立的决定下一跳的走 向。因而无连接的流量工程，继承了来自i p 等无连接技术的简单性和灵活性。但 是无连接的流量工程，对路由的控制能力是有限的，也容易引起路由的振荡。相 关研究中对于路由的优化很多采用动态设置o s p f 等协议中的链路权值来实现。而 面向连接的流量工程的实施，通常基于a t m 、m p l s 这样的面向连接的、支持q o s 的多业务网络技术。面向连接的方式，使得对网络路由的管理和控制更加精确和 容易。使得流量工程的实施更加方便。 1 1 2m p l s 及其约束路由技术 第l 页 国防科学技术大学研究生院博士学位论文 近年来多协议标签交换( 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 ，m p l s ) 的兴起，为流 量工程提供了实施手段上的有效支持，促进了流量工程技术的发展。m p l s 技术是 新一代互联网骨干网络的核心技术。它是由思科等网络设备厂商提出，由互联网 工程任务组( i e t f ) 批准的一个业界标准。 m p l s 的原理是为每个进入m p l s 网络的数据包加上一个标签，并根据标签 来决定数据包的路径及优先级，也根据标签进行转发。m p l s 兼容的路由器在把数 据包转送到其路径前，仅读取数据包标签，无需读取每个数据包的i p 地址及包头。 m p l s 通过l d p 和r s v p t e 、o s p f t e 等信令协议，提供了约束路由机制。 按照r f c3 7 0 2 的定义，“约束路由是一类在选路时考虑流量属性、网络约束和策 略约束的路由协议。约束路由不仅可应用于流，也可以应用于流聚集。它是q o s 路由的一般化”。m p l s 的约束路由机制，能够显式地指定数据传输路径，使得路 由选择算法能够根据q o s 约束和流量工程优化目标的要求进行路径选择，因而也 进一步推进了面向流量工程的约束路由算法的研究。i e t f 推出了大量基于m p l s 实施互联网流量工程的r f c 和d r a f t 。r f c 2 7 0 2 描述了在m p l s 网络中实施流量 工程的总体要求。r f c 3 3 4 6 描述了m p l s 流量工程的适用性。r f c 3 2 7 2 总结了互 联网流量工程的架构和基本原理。大量规范的制定推动了m p l s 对流量工程的支 持不断完善。 1 1 3 面向流量工程优化的约束路由 流量工程是为了优化网络资源的使用效率，提高网络处理性能而对流经网络 的业务流量进行控制的过程。现今互联网中广泛使用的路由协议普遍使用最短路 径算法( s h o r t e s tp a t hf i r s t ，s p f ) 来路由网络业务流量。这一算法简单并且容易 部署，速度较快，并且最短路径原则使其有利于节省网络资源。这一原则也符合 人们在口常生活中出门取最短路线的生活常识，在互联网中一直被广泛应用。但 这一选路算法常会导致流量在个别链路或某些区域的链路上拥塞，形成瓶颈。降 低了整个网络的资源使用效率。 面向流量工程优化的约束路由技术，本文后面也简写为流量工程约束路由技 术，是指在路由选择阶段结合流量工程优化目标，按照有利于提高网络资源利用 效率的原则优化路由安排，合理的引导业务流的走向。流量工程约束路由技术能 够从根本上克服当前互联网所使用的最短路径路由带来的拥塞问题，有效提高网 络资源利用率，具有重要的理论意义和应用价值。近年来在m p l s 和光网络等技 术兴起的背景下，这一研究领域受到学术界和产业界口益广泛的关注，不少研究 者在这方面做出了有价值的探索。i e t f 也专门成立了路径计算组件( p a t h c o m p u t i n ge l e m e n t ) 工作组，专门研究m p l s g m p l s 流量工程l s p 的计算问题。 第2 页 国防科学技术大学研究生院博士学位论文 r f c4 6 5 5 、4 6 5 7 、4 6 7 4 、4 9 2 7 等规范对路径计算组件的架构和若干协议进行了规 定。c i s c o 、j u n i p e r 等很多路由器厂商也实现了对m p l s 流量工程约束路由能力的 支持。相关规范的不断完善和路由器厂商的支持，使得流量工程约束路由技术不 断成熟和走向实用，为流量工程约束路由研究提供了良好的实践基础。但是流量 工程约束路由技术也还面临着不少问题。有待研究者们的进一步深入研究。 1 。2 论文的研究内容和主要贡献 在国家自然科学基金重大研究计划项目“下一代高速网络关键技术的研究 ( 9 0 1 0 4 0 0 1 ) 和国家8 6 3 计划重点项目“新一代互联网技术综合实验环境 ( 2 0 0 1 a a l1 2 1 2 0 ) 支持下，针对面向流量工程优化的约束路由算法面临的主要问 题展开研究。 主要的研究内容包括： 1 面向流量工程优化的在线约束路由算法 分析目前已有文献中提出的流量工程路由算法的优缺点，特别是最小干涉算 法的主要不足；设计新的反映干涉程度的链路干涉关键度函数以及相应算法，算 法应该能够综合考虑主要的流量工程优化目标，包括最小干涉、负载均衡和最小 化网络资源占用等。 2 面向流量工程优化的预计算型约束路由算法 研究如何设计基于预计算模式的流量工程约束路由算法，通过在预计算阶段 的预先处理，能够加快算法的在线运行时间或者得到更优的选路结果。 3 面向流量工程优化的多路径约束路由算法 研究如何设计面向流量工程优化的多路径约束路由算法，包括如何根据最小 干涉、负载均衡、最小化资源占用等相应优化目标的需要，确定路径数目，设计 候选路径选择算法以及候选路径间的流量分配算法。 本文的主要贡献包括： ( 1 ) 面向流量工程优化的在线约束路由算法 针对m i r a 算法的一个变种i - m i r a 算法单纯考虑是否存在干涉的特点，提出 了结合负载均衡原则的改进算法i m i r a l b ；针对m i r a 的关键链路划分过于简单 化的特定，提出了反映干涉程度的链路干涉关键度函数和相应的路由算法m i n c f ； 在此基础上，提出了综合考虑最小干涉、负载均衡和最小化网络资源耗费( 最短 路径) 三个要素，易于动态调节的混合算法h o r a 。上述三种算法在路由请求成 功率上较之n e w m i r a 等算法而言都有明显提高。i m i r a l b 算法在k l 或者 i s p n e t 等含有常数个入出口对的拓扑中，性能表现较好。但若入出口对数目快速 增长时，甚至所有结点都可能是入出口结点时，干涉过于复杂，i m i r a l b 和 第3 页 国防科学技术大学研究生院博士学位论文 n e w m i r a 等算法性能下降的比较明显，甚至下降到最短路径算法的水平。而 m i n c f 和h o r a 算法在这种情况下通过参数设置实现对算法行为的调节，可以达 到较好的性能水平，表现出对不同的网络拓扑和请求序列更强的适应性。 ( 2 ) 面向流量工程优化的预计算型约束路由算法 针对在线算法对复杂度有严格限制，良好的优化效果和低复杂度往往难以兼 顾的问题分别提出了两种预计算算法：预计算链路关键度函数的p r e m i n c f 算法 和预计算k 条路径的p r e k m i p 算法。p r e m i n c f 算法具有适用范围广的优点，通 过预计算链路关键度使得算法在具有良好优化效果的前提下，在线复杂度降低， 执行时间较一般在线算法大为缩短。p r e k m i p 算法则预计算k 条路径，然后输入 真实请求序列，按照在各路径上增加该流量负载后网络入出口对最大流之和的变 化情况打分排序。p r e k m i p 算法以运行时间作为折衷，在请求成功率等性能指标 上取得了进一步的提高。 ( 3 ) 面向流量工程优化的多路径约束路由算法 针对现有多路径路由算法大多以负载均衡为目的，较少考虑