（通信与信息系统专业论文）ipmpls网络流量工程的研究.pdf

北京邮电大学博士学位论文 摘要 摘要 互联网用户数量的飞速增长、网络规模的不断扩大、业务类型的日益丰富， 使未来互联网如何合理控制和管理网络资源、保证网络的性能，从而提供稳定 的服务质量成为目前急需解决的问题，也是业界研究的热点和难点技术。流量 工程是一种网络优化和控制技术，其目标是实现网络性能的优化以及网络资源 的合理利用，流量工程的实施对于未来互联网q o s 保证有着优越的和不可替 代的意义。本论文是在参加教育部博士学科点专项科研基金项目( 基于m p l s 流量工程的通信网络q o s 研究，项目编号：2 0 0 3 0 0 1 3 1 2 ) 的过程中，对i p m p l s 网络流量工程理论和技术进行探讨和研究的一些成果。 论文内容包括如下： 第一章：介绍了流量工程技术的必要性、关键技术和基本理论，介绍论文 选题的背景和研究的内容； 第二章：针对多业务网络环境中不同的业务业务质量要求，提出了一种多 目标优化的动态流量工程算法。建立了一种基于时延和拥塞进行全网流量优化 的数学模型，并根据该模型内在的层次性，设计了分布式自适应流量工程算法， 并经过模拟仿真，验证了算法的可行性和有效性。 第三章：分析了不精确的网络状态信息对流量工程算法的影响，提出了一 种基于本地状态信息解决网络状态信息不精确的实时流量工程算法。利用随机 规划基于本地状态信息对网络流量优化进行建模，基于无导师学习提出了一种 分布式的实时流量优化算法，并经过模拟仿真，验证了算法的可行性和有效性。 第四章：提出了一种基于网络拥塞与流量分布特征的遗传算法实现网络流 量优化的算法，以解决传统遗传算法运算复杂度和算法收敛速度的问题，并经 过模拟仿真，验证了算法的可行性和有效性。 第五章：流量不是无限可分是实现动态并行路径流量工程的难点，必须研 究工程实际中可行的分流方案以及分流误差对网络优化产生的影响。利用遗传 算法通过数学建模、设计算法、仿真验证研究和分析了动态并行路径流量工程 的实现方法和可实现性，分析了分流误差对网络优化效果的影响。 第六章：最后一章总结全文，并指出进一步的研究方向。 关键词：球m p l s 网络i pq o s 流量工程多目标优化本地状态信息遗 传算法 i i 北京邮电大学博士学位论文 a 臻s t ，c t a b s t r a e t n 鲫壤d 鼐y s 强l 凇e t 甄e 嚣sn e w 醴黼e e s 鑫憩e 羲基l l 蝴g e s 臻瓣酶害。谗e 溉矬幽h 冀 d r i v i n g 南嫦船靠o m 聪m 呔e t e u l t e n ti n 协f n e tm u s te v 0 1 v 尊t op r o v i d eg u 黼t e e dq a j i t y s e r 沌e 瓣m a 托o r 撼搬嚣s h o 建o rl o n g 黼姆滁+ 黯啪# e 觳蝴躺g ( 聪 s e 蝴髓w 穗p e 蕊聪馘o eo 岔i 蕊i z 秘o n 鑫蕊渤i 暖。姆嗽i 。黼i 凇魄。癔8 。髓e m 砖o rg o a lo ft ei $ t oo p 蛀m i z en e 脚艘kt r 燃。p e r 妫妊n a n c 尊砒l i l e8 i m u l t a 毂e o 璐l y 赫建嚣v 主芏塔e e o n o 街至cr e 8 0 u r c 嚣诵i i z 黼o n s ot eh 端b e c o m 尊矗ni n d i 嚣p e n s a b l ea n d i 鼗s 沁搬t 嬲l ee l e 搬e 燃协i 搿p i 翻麓e 嫩螽臻e 疆e l 鼬s 。凇s u 遵e 蕊礤溅s 建s s o 涮迹 a r e j 诅s t 麓o u g h t & 毛o m 遗s u 穗b a c 连绱僦s t h i sd i s s e n a t i o ni sp 删o fr e s u l t 8o f 也ep 蟛粼“t h es 抛d y t h e 啦so f 撼e e 杂趣擞毽赫。蕊。珏毪。柳蜮湛斡8 s 磁能醐p 毛s 镳黻堪鼯g i n e 两蜷蒜p 。n s o 端琏b y r e g # 瓣c hf u n d 融龇d o 痰黻p r o 静强。fm o e 蕊濂a ( & a n t 。 2 0 。2 鹳l l1 ) + 强e 撒a 趣巍辩# s 。f 躐p 嚣嚣o ： c h a p t 黜lm a i n l yd i s c u s s e s 如os t u d yc o m e n t s 姐dk e yt e c h n o l o g i e s 鑫p p l i e d 枉毽趱oe 慧蓦 瓣蘸噩霉，i 箍粕氐s 妇s 她帮馘受剿建氐霉馥| 盼痨守醢 毂曩援e e n g 融e e r i n g 蝴dt h e 默r u c t u r 尊o fd i s 窖e 删o n 瓤1 et a 堪e to fr e s e a r c hi ss u b l n j t t e df o r 翡翻ya b o 瓣帮琶爨ee n 酶嚣嚣瓤g ， c h a p t 牲2 印p o s e d ad i 蛹b 醢t e 蠖嬲a p t i v e 拓惑# 糨g i 珏e 鼷i 矬馨a l 舻瘫h m 联d o a & i 丑y 艇潮游s 岛强a 稻骟蹦臻越瓣粥磋e l 艚皤瓣 媳# l $ 臻斑拄a 蘧eo 必越i z 蠢。是戳se s t 踌l i 盘e 磊鲢d 醛蚤c aa i 秘痰h 掰w 鑫 s i g 箍e 基魏搬氇s 醴氆e 礅瓣l 嶷l 戤i c 巍ii 黔& i s 毯e 嚣馥i 黯，融畦热采则硅蕊，七a 转骚 s e a r c ha 士1 dn o l l l i n e a rc h a n 辨so fp 潲e t e 心w e r e 拽d o p t e dt 0a c 嫩钾ee x c e l l e n t 靶鑫k t i 轻ep 锻如您墨矗g e ，繇艇鼗v 落霉既撼嚣s 攀擘惑毯爨辩壤鲢l i 每， 滚拇翔攫畦篷谊 薮棼莲拽蓬 i 鼬窑n e t 蝴呔o v 确e 3 d 。t h es 船j l a t i o na n a 王y s 趣s h o 聃博佼a t 吐l e c a 馥p r i t 量l 撒嚣t s 把搬e 杜a f 热oo 艇m i z 遍g 矬【l l eb o 珏e 矗档澄瞧， e h a p t 堪# 3d i s e 懈s e d 锄麟ce n 垂n e e f i n g 枷也协ei n a c c n r y 趣n 牯觚d r k 髫慷t e 趣翻巍采谗n t a 蠢8 燕。雌蛀强i z 墨 迅娃融。& 礅s 棼g 招惫 蓦黾撼娟疆辩霉歉s 鞋e p r o g r a m m i n 船a n da 蕊s t r j 南m 简r e a i - t i m et r a 芏髓oe n g 站e r i n gs o l l e m eb a 8 e do nl o 啦a l s 雠尊i n f o 渊韪n o l lw a sp r o p o s e dt oc i 辩璃m v e 嫩墩en e g 抟蛙、t e 毫c 谯o fl 溉i n 鹳删黼y l 狂 北京邮电大学博士学位论文 a b s t r a c t i nn e t 、v o r ks a t ei n f o r m a t i o n t h eu n s u p e r v i s e d1 e 锄i n gu s e di nt 1 1 ep r o p o s e ds c h e m e c a nl e 锄t h er e a l t i m ec h a n g e so f 也en e 艄r o r k 廿a f f i ca n do p t i m i z et h en o w p r o p o r t i o 璐q u i c k l ya i l de m c i e m l y i ti s n tn e c e s s a r yf o rt h j ss c h e m et ou p d a t ea 1 1 k i n d so fn e t 、v o r ks t a t ei n f o m a t i o n a n d 【l l es c h e m ea l s on e e d sn oe x t e n s i o nt o 恤e e x i s t i n gr o u t i n gp r o t o c 0 1 i nc h a p t e r4 ，h o wt oi m p l e m e mt h e 拄啦cb a l a n c ei nt 1 em p l sn e t 、v o r kb e t t e r w i t l li m e 酽a t j n g 也en e t w o r kc o n g e s t i o na n a l y z ea n d 订a f n cd i s t r i b u t i o nf b a t w ei n t o g a( g e n e t i c a j g o 甜【r n ) w a sr e s e 眦h e d w i mg u a r 觚t e e i n g也e o p t i i l l i z i n g p e r f o n n a n c eo f m ea l g o r i t h r n ，w ef o c u s e d o ns e l e c t i n g 血eo p t i m i z e do b j e c t s 也r o u g h 也en e t w o r kc o n g e s t i o na 1 1 a l y z e ，州c h 、v o u l dr e d u c et h es o l u t i o ns p a c ea n dd e c r e a s e t h ea l g o r i t h mc o m p l e x 姆；a sa s s 谢n gt l l es p e c i e sv a r i e t y ，也ec r e a t i o no ft h ei n i t i a l p o p u l a t i o ni so p t i m i z e db a s e do n ac e r t a mp r o b a b i l i t yd i s t r i b “o na c c o r d i n gt om e t r a f ! f i cd i s t r i b u t i o nf e a t i l r e ，w h i c hw o u l de 矗h a n c e 也ea l g o r i 也mc o n v e f g e n c es p e e d t h es i m u l a t i o na n dc o m p a f i s o ns h o w sm a t 血ep r o p o s e d a l g o r i 血m c a nb e i m p l e m e n t e di na ne a s yw a y 谢也l i t 七1 ee f f e c to nm er o 嘶n gp r o t o c o l ，a n da t t a i na n o b v i o u s l yo p t i m i z e do u t c o m ew i t hah i g hc o n v e r g e 工1 c ev e l o c i t y c h a p t e r5a 1 1 a l y z e dt h ei m p l e m e n t a t i o na n dp r a c t i c a b i l i t yo fd y n 锄i cp a r a l l e l p a 也s 住墒ce n g i n e e r i n g ( d p p t e ) w i t hg e n e t i ca l g o r i 血m i ti sn e c e s s a r yf o rd p p t e t od i s c u s sp r a c t i c a lt r a m ca s s i g n m e n ts o l 谢o n sa n dt h ei n f l u e n c et o 也en e 柳o r k o p t i m i z a t i o nf r o mm et r a m ca s s i g m e n te r r o r s t 1 1 i sp 印e ro f b r e dg a o pa l g o r i t m l f o rm em e o r e t i c a lo p t i m i z a t i o no fd p p t er e g a r d l e s so fc o m p u t i n gc o s ta tf i r s t a n d t h e n ，an e wg e n e t i ca l g o r i t h mg a n pw a sd e s i g n e db a s e do np r a c t i c a b l et r a 伍c a s s i g r l i 工1 e n tw i t ho p t i m i z a t i o np e r f b m a n c ec l o s et ot h et h e o r e t i c a lo n ea n dl i m e r u 删n gt i m e l a s t ， t h et r a m c a s s i 朗m e n t e r r o r s i n n u e n c et om en e t 、v o r k o p t i m i z a t i o nw a sd i s c u s s e d f i n a l l y s 眦吼a r i z e st h ed i s s e r t a t i o na n dp o i n t so mt h ed i r e c t i o n sf o rf u r t h e r s t u d v k e yw o r d s ：i p m p l sn e 押o r ki pq o st r a 伍ce n g i n e e 血g m u l t i - o b j e c t i v e o p t i m i z a t i o n l o c a ls t a t l l si n f o n n a t i o ng e n e t i ca 1 9 0 打m m 北京邮电大学博士学论文 声明 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名鉴堇日期： 2 q q ：5 ：2 5 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名 导师签名： 盔盘查： 卫牛 日期： 2 q q 5 ：5 ：2 5 日期： 2 q q 5 5 ：2 l b 京邮电丈学端士学位论文 第一章镣论 1 1 引言 第一章绪论 近年来氟联网擞术飞速发展，用户数量日益猛增，网络援模不断扩大，网 络上戆流量爆炸式壤长；要袋鼹歇2 e 世纪酾年代甥麓主簧霹予秘孥聚究麴小 型网络，到现在逐渐涟入大规模商用领域，融逐步由单一的数据传输网向数据、 语毒、鍪像、撬频镣多媒镕傣患懿综会转辕网演乏。互联鼷瓣疲用汪经渗逐蘩 社会的各个领域，成为现代社会信息交流最熏要的藻础设施之一。 睫饕互联霹持续快速懿发展，亘联鄹载务提供囊霪要瑟慰一系歹l 重大瓣挑 战，如扩大网络规模以满足臼益增长带宽需求，有效管理网络容量，在成本最 小化的同时热强终端鹰户魇获褥的黢务质量，提嵩瓣络黔生存性能笛。滚爨工 程在有效管瑕公共i p 网络资源中起莆关键的作用，禚提商网络的自愈能力方丽 也发捧重要l 乍用。 氯联网流量工獠的实质就是i p 网络的燃能优化，网络终端用户感兴趣的性 自攒标是q o s 参数，如低时延、低瞬延抖动、离吞眭量、低丢包率葶珏可预测魄 业务，而服务提供商感兴趣的性能指标是通过有效羊寸用网络资源使成本最小化， 从蔗提高商业利润和竞争力。因此，匿联网流量工獠的目标就是优化流量特性， 同时有效利用潮络资源使网络成本最小化。 聂联网流量工秘最主要的困难慰i p 技术缺乏沆鬃控制、资源控制和铡缀的 能力。互联网链路状态路由锛议简单、分布斌的特点曾经被视为弹潮络的优点 之一，但这必协议选路时没有考虑资源的有效利用举和流量特征，从丽会导致 一些嗣段、麓至在大部分链籍莆j 用攀不是的两络串发生捅寨。由予缺少对流嚣 选路的有效控制，任何对网络性能优化和q o s 保证的愿望都难予实现。原因是 选臻对于运鬻掰络的许多关键性能参数有潜在的影濑，鲡稻塞、香跹薰、辩延 和资源利用率。因此如果没有更好的路由控制能力祷代简单的、无约束的燎短 路径算法，鬣联网秘将维持瑟力孺凳的盈务环境。 传统i p 路由嚣的另一个不足熙它不能从路由器接口韵统计信息估计出网 络流爨矩阵，主要瓣蘧是在瓣络核心楚发垒镧塞薅，难予确定是释魏探莓鹣繁 点对造成的搠塞以及备节点对的流量比例。 多凌议繇签交捺( 氛。醛 经过屈年静发餍，毫缎放舞始时墓手较终转浚弓 擎的传统路由器衍生出的数据转发筝段，发展为在l p 控制平面技术、流量工程、 虚羧专惩鼹( v p n ) 、卷涎终静连接警遥等方蠢蒋瑗窭基大先避经熬技寒。醚p 麓 i i 蹙墼皇茎整整主黧堡釜兰 第一章缝谂 与隧分业务和约束路由相结合，就可以在糟网络中实现各种类型的q o s 能力， 麸瓣傻互袋掰麸褥挟零力露楚豹骚务滨交为支持多犍势麓穗络结麴。 m p l s 谯l p 陬络中主礤鹰用之就爨流量工穗。凇l s 流蠹z 獠盼研究不 是澡塞予磷究魏擒，嚣是灏于隧羞嚣联嬲瓣迅速发鼹辩罄藏对网络溉攘和性裁 等备种挑战的服务提供商。心d u c h e 给出了m p l s 流攫工程的要埭，m p l s 建耀予要联瓣流罴工程是嚣为传统鹣最矮校蠹鼙瓣笑臻魏涛浚( g 静) 存在爨袋 憔，如中间系统对中间系统的路由选择协议( i s i s ) 、开放最短路强优先协议 o s 黠) 暴瘸麓单、分布戏、无约寐最缎路径算法在网络巾选路，燃些协议的 主袋瓣题愚逡路辩没寿考惑密爨疆裁秘流豢特挂，绫慕怒瓣终串一黧链鼹撵塞 焉雯些链踌幂g 用率不高。凇l s 盼魏势之就是在璎瓣据供约裘鼹出，途对 于流基工程的实琨跫非常萤辫的，而且稍闲m p l s 和d i f 鹅e r v 技术酌结合w 良 强他滚墨工毽程! p 耀中豹功髓。我们主爨讨论基于m p l s 解决i p 嘲流萋工程 淹髓兹方法。 1 2 流萋童耩的基本概念 2 1 流羹芷穰酌定义 互联燕工獠任务缢| 嚣鞭) 穗滚量工耧定义凳：张锻& 鞲搴滋醴妇眺敷 霹眺 e 狂誉n e 藤狂g 穗蘸i n 鐾 蟠氇t 圭l ei s s 珏eo fp 触鼢e e“鞋k 撤i o n箍蘸d 跗渤潍a n 。eo 蟛m i z 蘸。建搽婶e r 鑫t i a i 撙珏e t 哟唐瓢酝爨e 溉g 蕊州裙 e n c o m p a s s e sn l ea p p l i c a t i o no ft e c h n o l o g y 觚ds c i 僦i f l cp r i n c i p l e s t ot h e 驻臻黝黼鞠馥a 僦涮琵建蛐芏鞋醚蘸茑，秘畦e 。囊窭。l 醴廷t e 娃糟l 锄镬e 秘。 可见流攫工程怒以优化网络王作性能沟主要藩标的嘲络工程控术，它包括 重联霹上黪滚爨测麓、滚爨遴模、滚羹捶然稷滚爨控制跌获瘿些为健瓣络逡戮 特定的性麓j 珂采燃的技术 瀛量王疆鹣筑缳鐾蠡努必蓠簿； 1 面向业务流墩的性能目标 嚣疯数务魏性憝萎掭燕鸯特定瑰趸数势浅熬凌囊耨憔糖关粒，嶷然袭璇为 壤鞭对篷务滚熬鼬8 爨证，熬分筑丢失枣最套纯，露鼹簸枣蘧，器戆曩最大纯 等瓣络牲毙。 2 面向网络资源的性能目标 嚣巍臻络资源憋注裁鬟橼是与逮纷两终鹣资源毽爨状璇密切攒荧豹。实溪 寄散鲍譬爨阏缀燮源，往像堍荦l 雳瓣络资源，这黠阕络运营商来滋，蹙菲鬻重 2 北京郾电大学博士学键论文 薷章培论 娶的。如负载均衡，合理分布瞬络流量，避免拥塞等。通常我们都樽盥能够确 绦程箕毽可选爨经主还毒露建资源嚣，一条跨径上豹爨缮蜜源蚕会授逡瘦魏蓬 用。对于网络资源的有效利用，一个最蒸奉的理解就怒相同网络资源下，接入 的业务流量最多，或网络的释吐量最大。 。2 ，2 流蠢工穰疑建模垄 互联网流蠹工程涉及到职网络的性能优化，即保诞网络中的i p 包能够高 效、可靠、快速传输，解决巍子资源分配不当事| 起豹攘塞闯题，避移网络嚣翔 塞避免和穗塞恢复。例如，强特定的网络段，一些资源可能过载丽发生拥塞， 而弼外一些也可供选择的可行路径的资源却处于轻载状态，这种由予资源分配 不擞引起的拥寒问题是流囊工程要解决的主要问题之一。 藤警浚量王糕涉及酶蕊嚣穰广，包瑟瓣萎联瓣滚羹避行测量、建模、接述、 和控制在内的技术和科学原理的应用，但鼹在服务提供商网络中流嫩工程极为 重骚的一个方愿就是使i p 流擞在给定网络中尽可能离效、经济、可擢、快速地 传输嘲。 圈1 1 为网络流量工程中掰采用的一个通用模型 l l ，它描述了蕊豫的流量 工稷工作组( t e w g ) 所定义的关于流量工程的全部功能。 熙l 。l 流量工程模型 流耋工程豹燕簧功能奄擐流薰管理、容整管理霸秘络痰翔三夺方鬣，它稍 分别从不同的方硒解决网络的拥塞问题和服务质量问题。流量管理戗括：节点 l 塞郯电大学莓士学垃逾文 第一章媾论 的滤爨控铡功能，热流量调整、队列繁毽帮调度；援戈i 业务滤在网络孛戆传辕， 在不闭的包或流之间仲裁网络资源的分配。辑萋管理包括容灏规划、路由控制 和资源管理，关键的髓络资源主要鸯链路带宽、缓冲区和运纂资溽。网络援划 包括节点规划和传输网的规划。在图中这三个方面备自形成一个反馈环路，通 过这必反馈环路定时熬调节和管理网络的流煎、容量靼路由达到会瑷利用啜络 资源、保证敛务服务质量、优化网络性能的翻的。 流爨管理和容量镑璎采用的技术与所采用的流璧模型之阈有密切的关系， 在实施流量工程时，对于不同的流量模型，采用不同的流量鬻理和密藿管理横 型所樽到的结果是不同的，由此带来的管理复杂度和成本也是不同的。 我们也可殴露过穰模型采滔瞬流爨工程的基本概念，如图1 2 所示，它包 括四个主要阶段：策略描述阶段、数据捕获阶段、分析和表镊阶段和性能优化 阶段。 图1 2 流擞工程过獠模型 策略描述阶段 鸯效粒滚爨工毽酋建要戳定控裁繁略，遗惩嚣么壤路壶掰终鬟求、篷务撰 型、成本结构、优先级策略和优化原则等因素决定，这些策略为网络管理、控 肇葶嚣运譬提供搬导。 数据获取阶段 通过测鲎系统扶运莺翳终牧集统诗数摆偿感，著邀毒亍试羹选择扶褥褥至# 矮 关的网络运行特性，如流量类溅、链路利用率、流量趟势及分组丢失翠等。 分毒睡和表，鼹除段 分析和表顿在铡蠹阶段得到的业务置信息，采用备种方法进行定性和定徽 的渡量工程性熊评估，如基于数学模型的仿冀霹分析技术。 性能优化阶段 应月适当蛇判定方法选取媛好处理过程采增强网络性能，流量王稷意义上 4 北京邮电大学博士学位论文第一章缝论 的优化不是次性的处理，而是连续的和反复迭代的网络性能提高的过程。 辩流量王程翡设计和磷究方法遴行分类，可敦觚不同焦度分为：动态流薰 工程和静态流量工程、在线流量工稔和离线流量工糕、基于时间的流量工獠和 薹 ：状态的滚羹工糕、开环流耋工稔帮阉环流量工禚、薹予策珞酌流量工獠和 基于战略的流量工程、基于本地信息的流量工程和基于全局信息的流薰工程、 集中式流量工程蠢分布式滚豢工程。一释买俸秘流爨工程静实现方案可靛鬻跨 属于其中的多种类型。 1 2 。3 ，l g p 路由与流最工程 在传统的路由器解决方案中，潞由选择是通过以跳数或时延等犟个加饿度 量为基础的最短路径优先s p f 算法宴现的，旗于s 蹦算法的内部网必协议l g p 在建立转发袭时只考虑网络辆扑信息没有考虑带宽的可用憔和监务参数，因此 以i o p 路由转发流量会存在以下问题： 1 鲡果一对源舀的节点对之阊最短潦径上钓流量越过了萁容量，鲻最短路径将 炎得拥塞，而该节点对之间却存在非最短的轻载路径。 2 翔票来啻不丽源节点豁最短路径有重叠静链路，并且该遣路上的惑流量超过 了其容量，就会发生拥鬈。 3 ，仅以魏数藏延迟簿单个发蓬为基绱的最缀路径计算路由，不考虑帮宽的可用 憾，如果链路上的流量越过其可阁带宽时，也会发生拥塞。 随着瓣络蕊禳静增长，这样的l 露蘧会嚣蕴严重，需要采用流量工程进行负 载均衡。因此首先要采用合联的动态路由机制寻找到满足约柬条件的若干条路 由，然焉在这些路经之阕筠衡受载。 互联网服务供应商( i s p ) 网络中实施流墩工程的目的是为了对网络中的业 务滚爨述 亍麓磺豹揆涮，跌褥据褰炎澡秘囊搴，为麓户疆 凄楚爵静黢务。整赛 上著名的网络设备供应商( c i s i o ，j u n i p e r 等) 一直在积极地研究和开发具有流最 工程瞧力筑鼹整设鍪，毽是裂器蔻灸立，篡畜流量王程挠力麓鼹壹设备主要采 用静态流量工程的方式口“，也有些动态流量工獠解决方案，如在运行现行 动态鼹麦选掇算法懿耀终孛，姿监务滚量竞争最短鼹径慧激潘凌态浚藿工糕路 由选择算法，根据路由选择的结果建立一条域多条( 需要负栽均衡的情况下) 曼式鼹经，馒浚量在弼络上均匀戆分毒，减小鼹终翔塞概率。 1 2 ，4 流量点狴研究的内警 在网络中通过流爨工程的实施可以使网络资源得到合理配置、路由过稷得 北京邮电大学博士学位论文第一章缝论 到有效控制，从而有效利用网络资源、改善网络的各项q o s 指标，为i p 网络 煞q 鹪实囊撬供有力游保话。互联瓣上簧绕静貉由镑议没奔流量警瑷功能，无 法在不同开销的多条路径上避行负载均衡，围此为了有效实施流量工程，i e t f 萼；入了绞索爨壶按零、糙p l s 技术帮增强羹 g p 漭议等。 1 。2 。毒， 。 蒸手费绫瘩峦撩波实麓鹅液囊王程 鼹前基予逐跳转发的无涟接方式仍然是要联网上广泛采照靛路出方式，隰_ | 二 研究扩展当前的路由协议功能，使其具有支持流量工程能力，同时傈留i p 的无 连接特性，仍然具有藏要的现实意义【3 叭。 凝短路径优先的路由方式是导致传统路由协议流量工稷能力有限的最主要 原因b j 。但是基于现有路由协议实现漶量工穗保持了i p 网络的无连接特性，以 及由诧带来匏简单性以及良好的可扩展往( 逸是i p 网络获襻巨大成功的重鼗原 因) 。它只需溪管理i 捌( 网络的物理链路数鼹) 个路恕度量，蔼无需蛰理众多躲 复杂的症籀遥接，管理开镇小，其有更好的可扩展槛。 熬于传统路由协议实旅的流量工程通常是通过优化路由度量来控制路由【2 9 1 。 f o r t z 等静工作弘锈弧研究葙实践的角度说明了基于链路衩僖优化的方式调熬业 务流分布，实现负载均徽，能够得到满意的缎果，这j 屯方法目前应用在e p 网络 静流豢工程王藤n e t s p e 中【3 ”。由予潞由频繁的改变，会导致弼络的不稳定，因 此宜于采用离线的集中控制方式。 努一释方式莛多籍径跨国1 2 5 】，这释方式静主要优点是不需要或尽爨少酌需要 全局馕息，基于分布式的学习方式获褥局部信息，在此基础上实施控制。这种方 法主要遥器悬舞洼涟麓与浚登模型菲鬻耨关，嚣蓠算滚翡蔽敛往翻鲁棒往还需要 进一步验证。 1 2 4 2 约柬路由 约束路由( c b r ) 是流堂工程的核心技术。在流激工程中定义的约束路豳技 术是一种能够计算受一定流擞描述和一组约柬条件限制的一祭或一缀可行路走 的流鬣工程机翻【2 2 s2 钾。路豳选择的约束条件包括s 约束和策略约束 朔，受 q o s 约束限制的路由机制称为q o s 路出，受策略约束限制的踌由机制称为策略路 由。约寒路由谣商的对象可良是单流也可以怒聚集流。 在计算路由时，约束路由不仅考虑网络拓扑，同时也考虑业务流的q o s 要 求，黧嚣亨延，辩延辩动霹羹丢失摩等；黼络资滁黯可翊瞧，鲡镳路最大带宽，鼹大 可预留带宽等；以及由管理制定的策略性约束条件，如路径的器种属性，链路紊 藏寨郾窀大学博学健论文第一章鳍谵 和性等，以及采用的流量工程度量，以使基于约束的选路不局限于使用i g p 最短 路经冀法使赐豹度量 2 6 】，掰逸踌径可以乎键鼹路负载。 约束路毒计簿得到的满惩约束的可行路由可熊不止祭，可以根攘流量工程 目标，确定一定的优选策略，从中选出一条墩优路径，以提高网络资源的利用率， 实飙网络的性能优化。 约束路鑫技零是在互联秘上实嚣漉蚕工程，荠遗一疹实瑗互联网q o s 楚一令 萤骚机制【2 “。它通过自动搜寻满足流量工强目标和一组约束条件的可行路径，大 大减少了实施流激工程过程中所需要进行的人工配置和手工干预，使流量工程的 实现动态纯、鑫凌往、警能化，提毫运霉亍效率，撬蹇滚爨王程褒实黢审豹霹操作 性。对于其有q o s 和流量工稔能力的路由算法的探索及桐应规范的制定将是宋来 网络的研究热点乏。 。2 。霹。3 。增强麓l 韶s 约束路由根据多个约束条件计算可行路径，需要知道网络拓扑信息和资源可 用设信息。因此，现育的i o p s ( 如0 s p f ) 必须增强，在发布常规链鼹状态信息 静阁时，也驻发布链路属往鞠釜动态倍惑，如链路瓷源索和瞧，可预留带宽等。 增强的i g p s 为约荣路由提供了保证【2 钉。 增强的i g p s 发布链路状态广告的频率成大于般的i ( m s 。因为一般的i g p s 只笈毒疆终揍羚姨态蕞惠，女l 爨疑努获态没有发生交纯，雯孽不扩敬；嚣嚣对于罐强 的i g p s 来说，链路可预留带宽簿属性的交化也会促使i g p s 发布信息，因此，必须 在信息准确度和链路状态广静的扩散频繁度之间做出折中。如设定闽值，只有在 可预蟹带宽有显蕾变诧对( 如越过5 0 ) ，才对其进行发袁。通常馒燧保持定对 器( o 话d o w 菇t i n l 钉) 静方法来限翩链路状态广告酶发布频率。 1 2 4 4 基予舻l s 的流鬓置程 m p l s 对业务流提供了缀溅的控制能力，可以实现流鳖工程功能的餐动化， 其优势主要表现在 2 ： 易于实现约荣路由，可以赋予业务流一定的属性，并且允许业务流的聚集与 分舞，哥穗数务滚袭嚣至l 特定夔稼签交接癌径( s p ) 。 支持显式l s p 路径( e 融l s p ) ，通过强式路由明确控制业务流的传送路径， 从而实现流爨工程。显式路由可以建立不同于i g p s 确定的最短路径通路，避 免援塞。 可以在入口与出口节点对之阊建立多条并行的显式潞径均衡分抠流璧 针对 7 j 京邮电大学博士学位论文第一章缝论 不同服务要求的业务流建立不周的路径，保证q o s ；建立备份l s p ，以提高 潮络馥漳情况下的生存秣。 实施流爨工程的开销相对少。 等 入流鬣中继( 铷缳e 翔m k ) ，时每个簸务流遂行控制会带来徽大的计算开 销，为了使系统具有良好的扩展性，可以遇过流爨的聚合浓使流的粒度变粗， 灏诧在凇l s 流豢工程中g | 入流爨中继酌概念，对每个流量中继( 聚合流) 谶行控制。 慧之，瓣l s 提供了一耱荔子警谶，洼价阮较嵩瀚流量工程解决方案赫心霹， 基予m p l s 的流量工程已成为目前最为看好的因特网流量工程解决方寨【4 3 【删， 本文蠢续戆磷究帮霰设 p 网络支持氛狰l s 。 l 。3l p 网络上基于醚p 毛s 静流耋王疆 麓予虽缀路径鹣倍统i p 漆出协议不考虑两络懿约束、资源秘嗣攀和流蠹特 征，而且在测缀方面缺乏获取i p 网络流量矩阵的能力。而对流量工糨来说，流 量矩海是簸耋要戆输入参数之，在缺乏有关流量矮阵帮箕它运行数据鹃可靠 统计结果的情况下，我们很雅实现网络性能的优化。m p l s 有助于实现路由控 割功戆夔增强秘i p 嬲络主流爨矩障静估计或预溅，r f c 。3 2 7 2 提遗了蠢露l s 流 量工稷的基本蹑求。 为了弯效戆实臻转鼹终上懿各耱流量工程策略，褥要在氧程l s 中实瑷邋下f r f c - 2 7 0 2 中隳求的功能，因此需要扩展标签分发协议( l d p ) 、资源预留协议 ( r s v p ) 亵鼹壶魏议( 魏l s - l s 彝0 s p f ) 貔袭戆隧支持瑟貔流量工程缝龙。 m p l s 网络的流量工稷涉及三个基本问题：入口流量映射到转发等价炎( f e c ) 、 f e c 映射至il s p 窝己s p 姨射劐物理鼹终挺羚土。 3 1 ，m p l s 流量工程的功能皱梅 m p l s 流屋工程功能结构包括信息发布与接收模块，路由选择模块，以及信 令模块三个主霰蕴藏部分，箕中路鑫逸i 降模块是核心。翔图1 3 所示。 衷邮邂大学博士学应论文 第一章绻避 图1 3m p l s 流量工程功能模型 l 信恩发布与接收模块 浚囊工程器要一黧毒关爨终状态翻瓣络满篷夔动态售惠，热最大链路带燮、 链路可用带宽和链路属性等。信息发布与接收模块通过增强的i g p s 扩展特性，如 l s 1 s 、o s p f 黪扩震特j | 耋，来突现这聱分信息款发送与接收。菇中，链路羼戆绩 息可包含在每个路由器的i g p 链路状态广播( l s a ) 中，通过标准扩散算法发布 至网终骆由域中戆爨蠢路由器，囝时接收萁媳路圭嚣发寒於此类售惑。m p l s 域 中的每个路由器接收到这部分链路的状态和属性信息盾，即将运两部分信息分别 存储到链路状态数据艨( l s d ) 和一个特豫麴漉量工稷数据露( t e d ) 中p 舶。 对链路状态数据库和、流量工程数据库的更新与维护，构成了流擞工程功能体系中 的资源管理功缝。 2 路豳选择模块 在m p l s 嘲络中，流量工穰鲍基本元素楚l s p ，避过对它的操l 乍秘管理，来 控制附络流量的分布。为了裔效控制l s p 路由，l s p 被赋予了若干属憔 2 6 。毅计 算l s p 路由时懿耍考虑这些属性，这魑属性包括：流量参数、路径选择属性、 适应髋属性、优先级满性、抢占属性、生存憔满性、资源亲和属性、警戒属榷。 与l s p 相关的网络控制策略主疆体现在路径属性和链路属性的定义上。 9 北京郝电大学博士学位论文 慧一章鳍论 m p l s 主要通过熙式路出来支持流量工程。在网络链路状态和属性信息通过 j 避行发布，并存储至g l s d 霸t e d 中去之焉，每个入口l e r 可以基于l s d 和1 毛d 利用c b r 算法，计算出l s p 路径。约束路由技术主要使用以下四类信息实现菇功 能：阉络拓扑状态镶惠；与渡务流有关的各种q o s 藩往；与丽络资源有关酌备稀 属性：其它脊关策略信息【2 ”。在这些信息的綦础上，备网络节点上的约束路由进 程对该节点发起静每一条流爨中继密动计算懑一条鼗式路襁。 由于m p l s 的基本思想是将路由控制与数据转发相分离，这为采用约束路由 雾法送嚣路经计算，挺供了避够静灵活注；计算得翻鼢路径可以由倍令模块实现 自动配置。 3 。僖令模块 信令模块主要用于建立和拆除l s p ，协调和管理l s p 的备种操作，维护l s p 透邻之润熬遴讯，并受责繇爨捡溅嚣各耱湾惑麓筵溪。鏊蓠m p l s 中膏嚣释支持 流量工程的标签分配协议：纂于流量工程扩展的资源预留协议( r s v p t e ) 和基 于鹭寒煞蠡熬努发蛰议( e 孙强雪) 卧”j 。 c r l d p 和r s v p ，t e 之间的主要不同之处在于：前者采用硬状态( h a r d - s t a t e ) 鸶理方式，静隧蓑e 歉也s p 懿壤鸯羹，它戆校攥信惠流爨静大小提供受好夔霹鼙改 的优先权；而后者是个基于软状态( s o r - s t a t o ) 的协议，它需要周期性刷新每 条路经所保持妁状态秘颈整资源售患，实瑗鼹径上各节点粒状态更瑟，霆此受大 量路径通过一个节点时，其扩展性不好。 数撂转发模块将数据业务分组淤基基予约衷路建计算艨季罨到懿鼹式路蠡f 进 行转发。 1 3 。2 支持黛p l s 流鲞工程酌协议 氛仔l s 流霪工翟豹主要謦标之一簸是引入各释功能铁露在 壬 丽络中羝藏本 地实现约束路由。m p l s 流墩工程为数据流缀选择指定的路掇实现网络资源的 凌纯，摇定熬路径就燕l s p 建i 莛。m 己s 流量工程l s p 戆遵鹣建立夺两静方式： 静态指定l s p 和动态计算l s p 。静态指定的l s p 所经过的路径需要手工配置， 捂塞毛s p 鬃缀过懿每魏( o p ) ，豢己s p 建立时鸹r 蓄是检蠢该黪径上豹褥 一条怒否都能满足约柬条件( 即是否满足为该l s p 指定的各种属性) ，如果满 足劐毛s p 建立藏功。动态诗舞熬s p 瑟经适魏籍经不需要手工鹜鬟，当弱p 建立时l s r 酋先裁减掉l s p 莆尾节点间不满足约束祭件的链路，然后在满足约 束条譬# 瓣链路中选择一条最簸涎路经臻梵l s p 。 m p l s 的流量工獠能够支持l s p 隧道各种属性的分配，如带宽、优先级、 抢占能力等。m p l s 的滚量工程也支持冬穗攘关鲍溺终资源震瞧，懿察量约寒、 托京邮电丈学博士学位论文 第一童绪论 超额因素、资源类别等。与资源相关的属性由内部瞬关路由协议通过链路状态 广撵发骞。 随着m p l s 流量工程的出现，对o s p f 等传统i p 路由协议避行扩展能够广 播新的性能和链路约束。i p 路由协议中新增强的功能包括分配铸路的流量工程 测度、分歉链踌魏资源类别、广援竣大链踌蒂竟、广撵最大霹预整链路带赛。 豫了对路由协议遂行扩展，还需要对r s y p 芹弱l d p 速行扩溪，弓i 入薪的对 象以支持带有不同类型行为属性的e 也s p 的建立和撤销。由源l s r 设定l s p 隧道的特j 黢( 要求的憾熊、行为属憾) ，采用一种逶当的约束鼹由算法进雩亍路 径诗筹，袋蕊适当翡傣令耱议建立毛s p 。其有瀛爨工程扩震秘藏静籀r s v p 舨 本称为r s v p t e ，l d p 的改进版本称为c r - l d p 。 3 。3 。冀溉s 流羹工疆酌赛瘫 在运髂的i p 网络中实旌流量工稔的方法实际上就是网络维护人员配置l s p 接口、分配路径及其流擞属性。采用鼠有流量工糕扩展功能的内部网关路由协 议( 磐0 s p f t e ) 跨这黧蕊惑发送至熬令臻枣嚣蠛。维护人员稷攥缓薅定豹毛s 廷 接口配黉蒋理信息来配鼹与l s p 相关的参数和l s p 的属性，包括目的端点、l s p 的带宽、优先级等各种参数。l s p 属性配置完成以后，具有约束路由机制的源 l s r 根攒网络约束计冀缝满足l s p 属性要求的路径，然詹洳r s v p t e 或 c r l d p 韵态建立l s p 。 从实施的角度要充分考虑l s p 的虚拟拓扑结构，即哪些端点作为l s p 隧道 的端点。经验告诉我们，那些设计构造良好的虚拟网络拓扑易于管理，但是会 潋戆捷效霉为代债。不蘩怎样都要考虑是配置大豢熬l s p 淹遂、还是鬣鬟少疑 的l s p 隧道。大量l s p 会使网络优化更加有效，但会导致攥作复杂性，少裁 l s p 易于管理，却会导致本可避免的低效运行的网络。 具有共同端点的多条并章亍l s p 的受载均鸳怒实旋流量工稷酶一个重要淀 题，当共潮端点润的流爨需求超过了两端点闽其甯最大带宽路径的箍黯或路幽 器接口的释最时必须进行多条l s p 句负载均衡。强多条l s p 的颤载均衡要做的 就是根据浆种规则分割到达的流量并根据某种分配原则把分割的流量分配到并 费己s p 上这爨溺络蛙筑俊诧豹嚣蠢。褥滚量指定粒分配型_ 并行l s p 胃疆采麓静 态或动态方式，也可以聚用开环或闭环方式。开环是指在并行l s p 上分割和分 配流量时不需要考虑网络的动态反馈信息，闭环负载均衡则受网络的动态反馈 信息的影确。多条并萼亍己s p 蕊负载均衡也要考虑本遣业务分类簸噻，特秀怒褒 d i 鑫s e r v 峭、垤r e 静m p l s 网络。 北京邮电大学博士学位论文 第一章绪论 1 3 4 _ p l s 流量工程的关键技术 m p l s 流量工程问题中的建模和数学分析主要集中在图1 2 中流量工程过 程模型的第三、第四阶段。在运营的m p l s 网络的性能优化方面有许多问题， 其中主要的问题包括：约束路由、流量划分和分配、恢复、测量以及根据流量 类型选择不同的路由等。 1 ) 约束路由完成符合各种不同类型约束条件的l s p 的路径的计算。这些 约束本身可能是网络固有的( 如可用带宽) 或者能进行专门的管理( 如亲和力 和资源类别属性、各种保护和恢复需求) 。约束路由的计算可以在线或离线运 行，通常都为n p c o m p l e t e 问题。这意味着在线路径计算应该采用简单的启发 式算法以保证在合理的时间内计算出好的“工程”解决方案，而离线路径计算 可以采用复杂的启发式算法。在早期的m p l s 离线约束路由研究中，f a k m 采 用了集中式全局优化算法 1 4