（计算机应用技术专业论文）面向流量工程的约束路由的研究和实现.pdfVIP

摘要 随着w e b 和多媒体应用的迅速增长，网络业务流量呈几何趋势递增，这对传统的尽力 而为的路由转发机制提出了严峻的挑战。当前的路由协议仅基于最短路径或最小跳数来为业 务流选择传输通路，不考虑应用需求以及网络的动态特性，导致网络资源利用率低，且网络 拥塞频繁。因此如何保证服务质量以及优化网络性能成为一个关键课题。为了提高网络资源 利用率，减少网络拥塞以及增强网络性能流量工程应运而生。它通过将业务流合理地映射 网络的物理拓扑上，从而满足业务流需求、最大化网络吞吐量以及优化网络性能。运用约束 路由技术的选路控制是实现流量工程的关键手段之一。 本论文着重研究了约束路由、流量工程以及相关技术。通过扩展o s p f 协议、结合约束 路由、m p l s 和r s v p 技术实现流量工程。我们设计和实现了原型系统，并进行了有针剥性 的测试和分析。本论文主要包括以下几个方面： 分析当前路由交换系统的问题所在，引入流量工程和约束路由。探讨了流量工程相关机 制和技术的发展，并分析了现有支持流量工程的路由技术，将它们划分为基于i p 网络和 基于m p l s 网络两大类。在阐述这些路由技术本身机制的基础上，对各自特点进行分析、 比较和总结。 对约束路由的内涵进行了探讨，深入研究了q o s 路由和策略路由两个组成部分以及两者 的关系。为使约束路由实现流量工程，我们提出了动态调整链路代价、g m s p 算法和“最 小化链路最大利用率”数学规划模型，并设计了面向流量工程约束路由的实现模型。 探讨了o s p f 协议的内部机制，在此基础上实现了o s p f t e ，其中包括t e l s a 的生成、 分发和解析以及流量工程数据库，这是约束路由的信息来源。运用动态调整链路代价和 g m s p 算法，扩展最小生成树算法实现在线约束路由；运用“最小化链路虽大利用率”数 学规划模型，实现离线约束路由；运用l i n u x 策略路由机制，实现策略路由。在线约束 路由、离线约束路由和策略路由三者的结合构成约束路由。 深入研究了m p l s 协议机制和r s v p 技术，并实现了两者的结合，从而运用r s v p 进行 标记分发，将约束路由计算的路径映射为l s p 隧道，并沿l s p 隧道传输数据流。 4 - 设计和实现了面向流量工程的约束路由的原型系统，并从系统开销、功能和性能三个方 面对系统进行了有针对性的测试，结果表明原型系统的功能和性能均优于传统路由交换 系统，实现了流壁工程，达到了设计目标。 本论文研究内容来源于江苏省自然科学基金重点资助项目“高性能网络路由交换系统 的算法与协议研究”，2 0 0 1 1 2 2 0 0 4 1 0 ( 编号b k 2 0 0 1 2 0 5 ) 。 关键词：约束路由，流量工程，o s p f ，l s a ，m p l s ，资源预留 分类号tt e 3 9 3 a b s t r a c t w i t ht h er a p i dg r o w t ho f w e ba p p l i c a t i o n s ，m u l t i m e d i aa p p l i c a t i o n sa n dd a t af l o w s ，t h et r a d i t i o n a l b e s t - e f f o r tr o u t i n gm e c h a n i s mf a c e sg r e a tc h a l l e n g e c u r r e n ti g p , s u c ha so s p fo ri s i sp r o t o c o l ， i sr o u t i n go v e rs h o r t e s tp a t h s m o r e o v e r , i td o e sn o tt a k et h er e q u i r e m e n to ft r a f f i ca n dp r e s e n t u t i l i z a t i o no fn e t w o r kr e s o u r c ei n t oa c c o u n t t h u st h et r a f f i cc a nn o tb ed i s t r i b u t e do p t i m a l l ya n d t h e c o n g e s t i o nr a t ei sh i g h ，a sar e s u l t ，h o wt op r o v i d eq o sg u a r a n t e e sa n do p t i m i z et h e p e r f o r m a n c eo f t h en e t w o r kh a sb e c o m eak e yi s s u ei nr e s e a r c h i no r d e rt oi m p r o v et h eu t i l i z a t i o n o fn e t w o r kr e s o u r c e ，m i n i m i z ec o n g e s t i o na n de n h a n c et h ec a p a b i l i t yo ft h en e t w o r k ，i e t fh a s p r o p o s e dt h m ce n g i n e e r i n g t h ep r i m a r yo b j e c t i v eo fn a m ce n g i n e e r i n gi s t oc o n t r o lt h e m a p p i n ga n dd i s t r i b u t i o no ft r a f f i co v e rt h ee x i s t i n gn e t w o r ki n f r a s t r u c t u r et oa s s u r es a t i s f a c t o r y s e r v i c ed e l i v e r y , t om a x i m i z et h r o u g h o u t p u to fn e t w o r k ，a n dt oo p t i m i z er e s o u r c eu t i l i z a t i o n c o n s t r a i n t - b a s e dr o u t i n gi so n eo f t h ek e ym e c h a n i s m st oa c h i e v et r a f i l ee n g i n e e r i n g t h i st h e s i se m p h a s i z e sc o n s t r a i n t - b a s e dr o u t i n g t m f n ce n g i n e e r i n ga n dr e l a t i n gt e c h n o l o g i e s b yc o m b i n i n gt h ee x t e n s i o no fo s p fp r o t o c o l ，c o n s t r a i n t - b a s e dr o n t i n g ，m p l sa n dr s v p , w e d e s i g na n di m p l e m e n tt h ep r o t o t y p e t h em a i nc o n t e n t so f t h et h e s i sa ea sf o l l o w s ： a f t e ra n a l y z i n gt h ee x i s t i n gp r o b l e m so ft r a d i t i o n a lr o u t i n g s w i t c h i n gs y s t e m w ei n t r o d u c e t r a 币c e n g i n e e r i n g a n dc o n s t r a i n t - b a s e d r o u t i n g d i s c u s s t h et r a f f i c e n g i n e e r i n g m e c h a n i s m sa sw e l la sr e l a t i n gt e c h n o l o g i e s ，a n ds u r v e yt h ei m p o r t a n tr o u t i n ga l g o r i t h m sf o r t r a f f i c e n g i n e e r i n g a l la l g o r i t h m s a r ec l a s s i f i e di n t ot w oc a t e g o r i e s ：1 p - b a s e da n d m p l s b a s e d w h a t sm o l e ，t h ee s s e n c eo f a l g o r i t h n l sa n dc o m p a r i s o n sa m o n gt h e ma r eg i v e n w e r e s e a r c hc o n s t r a i n t - b a s e d r o u t i n g a n di t st w oc o m p o n e n t s ：q o s r o u t i n ga n d p o l i c y r o u t i n g m o r e o v e r , i no r d e rt o i m p l e m e n tt r a m c - e n g l n e e r i n g o r i e n t e d c o n s t r a i n t - b a s e dr o u t i n g ，w ep r o p o s e d y n a m i cl i n kc o s tt u n i n g ”m e c h a n i s m ，g m s p ( g r e e d ym u l t i s h o r t e s tp a t h ) a l g o r i t h ma n d “m i n i m i z i n gm a x i m u ml i n ku t i l i z a t i o n ”l i n e a r p r o g r a m m i n gm o d e l 。a f t e rt h a t ，w ed e s i g nt h em o d e lo fc o n s t r a i n t - b a s e dr o u t i n ga n di t sk e y c o m p o n e n t s b a s e do ni n - d e p t ha n a l y s i so fo s p fp r o t o c o l ，w ei m p l e m e n to s p f t e ，w h i c hc o n s t r a i n st h e d i s t r i b u t i o na n dp a r s i n gm e c h a n i s mo ft e - l s aa n dt r a f f i ce n g i n e e r i n gd a t a b a s e i tp r o v i d e s c o n s t r a i n t - b a s e dr o u t i n gw i t hn e c e s s a r yi n f o r m a t i o n t h e n b yu s i n g “d y n a m i cl i n kc o s t t u n i n g ”m e c h a n i s m ，g m s pa l g o r i t h m ，m i n i m i z i n gm a x i m u ml i n ku t i l i z a t i o n m o d e la n d l i n u xp o l i c y - r o u t i n g ，w ed e v e l o po 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 ，o f f l i n ec o n s t r a i n t b a s e d r o u t i n ga n dp o l i c y r o u t i n g t h e s et h r e ec o m p o n e n t sc o n s t i t u t ec o n s t r a i n t b a s e dr o u t i n g f u r t h e r m o r e w es t u d ym p l sa n dr 5 v pt h o r o u g h l y a l s ow em a k eu s eo fr s v pt od i s t r i b u t e t h el a b e lo fm p l si no r d e rt om a p p i n gr o u t ec o m p u t e db yc o n s t r a i n t - b a s e dr o u t i n gt ol s p t u n n e l ，w h i c hi su s e dt ot r a n s f e rt r a f i l eo f n e t w o r k w ed e s i g na n di m p l e m e n tt h ep r o t o t y p e i na d d i t i o n t h ef e a s i b i l i t ya n dt h ee f f e c t i v e n e s so ft h e p r o t o t y p ea r ep r o v e dt h r o u g hw e l l c h o s e ne x p e r i m e n t s t h er e s u l t ss h o wt h a tt h ep r o t o t y p e w o r k sm u c hm o r ee f f i c i e n tt h a nt r a d i t i o n a lr o u t i n g s w i t c h i n gs y s t e m t h er e s e a r c hw o r ki nt h i st h e s i si s s u p p o r t e db ys c i e n c ef o u n d a t i o no fj i a n g s up r o v i n c ep r o j e c t “h i g h p e r f o r m a n c en e t w o r k i n g r o u t i n g s w i t c h i n gs y s t e mw i t ha l g o r i t h ma n dp r o t o c o l r e s e a r c h ”，2 0 0 1 1 2 2 0 0 4 1 0 ( b k 2 0 0 1 2 0 5 ) k e y w o r d s ：c o n s t r a i n t - b a s e dr o u t i n g ，t r a f f i ce n g i n e e r i n g ，o s p f ，l s a ，m p l s ，r s v p i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：尘垦熊日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：生查盎导师签 期 面向流量工程的约束路由的研究和实现东南大学硕士学位论文 1 1 研究背景 第一章绪论 i n t e m e t 最初产生的目的只是在计算机之间传递文件，以及提供对计算机的远程访问。 这些任务对时间的要求都比较宽松，因此i n t e m e t 构建的原则就是简单，提供的服务质量也 非常简单，即尽力而为的数据传输。这种服务模式把复杂的处理放在端系统，因而具有良好 的端到端扩展性。这也正是二十年来i n t e m e t 飞速发展的一个要素。 随着w e b 和多媒体应用的迅速增长，网络业务流量呈几何趋势递增，传统路由协议仅基 于最短路径或最小跳数来为业务流选择传输通路，不考虑应用需求以及网络的动态特性，导 致网络性能下降，网络拥塞频繁。运用最短路径算法来进行路由选择存在本质缺陷：首先， 如果从一个源点到终点的流量超过了最短路径的容量，最短路径将变得拥塞，但同时这两点之 间可能有一条更长的路径没有被充分使用：其次，来自不同源点的最短路径在一条链路上重 叠的情况下，如果通过该链路的总流量超过了该链路的容量，那么就会发生拥塞。图1 - 1 所示的 “鱼型问题”( f i s hp r o b l e m ) 是传统路由协议造成的一个典型问题。由于从c n g 的最短路径是 c 寸d j g ，因此a 到g 以及b 到g 的业务流都沿c _ d 寸g 路径传输，造成该路径的拥塞。而传 统路由协议不能主动将业务流分配到c 斗e 斗f _ + g 路径上，使该路径的资源得不到利用。因 此如何保证服务质量，如何优化网络性能，尤其是骨干网的性能成为一个关键课题。为了实 现网络流量的合理分配，消除网络瓶颈、减少拥塞以及增强网络的可扩展性和灵活性，流量 工程( t r a f f i ce n g i n e e r i n g ，简称t e ) 应运而生。它通过将业务流合理地映射网络的物理拓 扑上，实现优化网络资源利用和性能、满足用户需求，同时提供高效可靠的服务，从而为各 类网络应用提供更好的保障。 9 0 年代初期的流量工程是通过简单地设置路由测度值来实现的，即给每条链路规定一 个量度值，两点之间的路由是在确定链路测度值后计算出来的。这种基于量度的流量控制仅 适用于小型的口网络无法适应网络规模的扩大。 9 0 年代中期在网络核心部分使用a t m 交换机作为中继链路，m 网络运行于a t m 网络 之上，这就是i p o v e r a t m 。路由器设置在a t m 网络的边缘，通过一系列由a t m 物理拓扑 配置的永久虚电路( p v c ) 与其它路由器互连。由于a t m 网络具有更高的传输速率，因此 降低了在网络核心部分因路由器引起瓶颈的潜在可能性。在i p o v e r a t m 模型中，流量工程 以a t m 网络为依托，通过调控和优化p v c 以及相关参数来实现。此时路由选择和流量工程 在不同层次上实现，前者位于i p 逻辑网络，后者则位于a t m 物理网络。这种结构不仅增加 了网络的复杂性，增加了管理和协调的开销，而且很难将路由选择和流量工程集成到一起。 具备高速链路接口和优良交互性能路由器的出现从根本上解决了i p o v e r a t m 的固有问 题和局限性，为实现基于路由器的流量工程创造了条件。然而，现今的各种i g p 路由协议( 如 o s p f ) 仅以拓扑驱动为基础，基于最短路径算法来为业务流选择传输路径，在建立转发表 第1 页 面向流量工程的约束路由的研究和实现 东南大学硕士学位论文 时，并未将网络资源的使用状况和业务流需求等因素考虑进去。实际上，最短路径算法时常 导致网络拥塞，比如：当多条路径共同包含某些链路即具有重合链路：或者路由协议所选择 的路径并不能满足业务流的带宽要求。因此，单靠目前的路由协议无法实现流量工程，我们 需要新型的路由协议来达到这一目的。 a b g 图1 1 鱼型问题 约束路由( c o n s t r a i n t - b a s e d r o u t i n g ，简称c b r ) 与传统i g p 不同之处在于：它在进行 路由选择时不仅要考虑网络拓扑，并要满足一系列约束条件( 包括带宽、跳数、时延和资源 类别属性等管理策略) ，在寻求最小代价路径的同时优化整个网络的性能。约束路由分为两 个子类：q o s 路由( q o s - r o u t i n g ) 和策略路由( p o l i c y - r o u t i n g ) 。q o s 路由是面向服务，确 保各q o s 需求( 带宽、跳数、时延等) 能够得到满足。策略路由则是面向管理的，它根据 网络管理员设置的规则以及服务协议( s e r v i c el e v e l a g r e e m e n t s ，简称s l a s ) 来进行路由选 择。策略路由使得选路不仅仅取决于目标节点，且取决于 l o s 字段、应用类型、协议类型、 数据包大小甚至数据包的负载部分内容等信息。策略路由不仅方便了管理，且使不同性质或 者不同服务质量需求的业务流沿不同的路径传输。约束路由将两者结合起来，是实现流量工 程强有力的手段。 本论文研究的重点在于提出并实现面向流量工程的约束路由。通过控制路由计算，使路 由选择基于网络状态、业务流需求和策略信息，从而平衡网络负载、从全局角度优化网络资 源使用，实现流量工程的目标。 1 2 国内外研究现状 有关流量工程和约束路由的研究在国际上已经有了长足的发展，已经形成了许多规范、 r f c 或者草案。在流量工程方面，d a w d u c e 等人于1 9 9 9 年9 月发表了第一篇研究流量工 程的r f c “r e q u i r e m e n t sf o rt r a f f i ce n g i n e e r i n go v e rm p l s ” r f c 2 7 0 2 。同年1 1 月，流量工 程工作组( t e w g ) 在华盛顿成立，随后出现一系列的r f c 和草案，分别阐述了实现流量 工程的必要条件、流量工程通用方法、对象和数据集以及可用于实现流量工程的技术和方法 学，如约束路由。 约束路由是在q o s 路由的基础上发展起来的，1 9 9 6 年m i t 的w c l e e 在i e e e n e t w o r k m a g z i n e 上发表了针对虚电路网络中路由选择综述文章和伦敦大学的c w a n g 的j s a c 上发 表的关于路由算法研究的文章标志着q o s 路由成为研究热点。随之涌现了许多q o s 路由算 法，比如多项式非启发类、伪多项式非启发类、探测类、花费函数类和概率求解类等等。 第2 页 面向流量工程的约束路由的研究和实现 东南大学硕士学位论文 d d c l a r k 于1 9 8 9 年提出了i p 网络中的策略路由( r f c n 0 2 ，m ，s t e e n s t r u p 于1 9 9 3 年首次给 出了域内策略路由规范 r f c l 4 7 9 。约束路由是在综合q o s 路由和策略路由两者基础上发展 起来的。目前有一些约束路由和m p l s 技术结合的r f c 和草案，如“c o n s t r a i n t b a s e dl s p s e t u p u s i n g l d p ”r f c 3 2 1 2 ，但约束路由还没有形成一个广泛被接收的规范。 著名厂商、大学和研究机构也加入了这些方面的研究，提出了一些通过扩展路由协议、 改进路由算法、结合m p l s 及其它技术而实现流量工程的原型系统或体系结构，如b e l l 实 验室和l u c e n t 的m a t e t ”、r a t e s t z l 和m i r a p l 。c i s c o 、j u n i p e r 、n o r t e l 、3 c o m 等公司也相 继推出支持流量工程和约束路由的产品。国内方面，华为生产的面向业务的第五代路由器， 有效地将约束路由、流量工程和m p l s 等诸多技术融合在一起；中和华为3 c o m 也都推出 具备同种功能的新产品。 除此之外，i e t f 还成立了专门工作组，在流量工程和约束路由等相关领域展开积极的 研究，比如集成服务( i n t s e r v ) 、资源预留协议( r s v p ) 、区分服务( d i t i s e r v ) 、m p l s 、i p p m ( i p p e r f o r m a n c e m e t r i c s ) 等等。这些技术为流量工程提供了强有力的支持。 当前对约束路由的研究集中在三大方面：其一，解决多约束n p 问题，提出高效且适用 的路由算法；其二，扩展现有的路由协议实现约束路由，并保证信息的准确性：其三，与流 量工程、m p l s 等网络技术相结合，从各个层面实现优化网络资源利用和性能这一最终目标。 1 3 论文的研究目标和关键内容 结合江苏省重大自然科学基金项目( b k 2 0 0 1 2 0 5 ) “高性能网络路由器交换系统的算法与 协议研究”，在考察了国内外研究现状的基础上，本论文的研究目标是通过对现有的路由协 议和算法进行深入研究，提出一种面向流量工程的约束路由算法，它在路由计算时能综合网 络状态、业务流需求和策略等一系列约束条件，从全局角度优化网络资源的使用。 根据论文的研究目标，并针对当前约束路由研究的发展状况和不足之处，本论文从以下 六个方面展开研究和实现的工作： ( 1 ) 深入研究流量工程技术和现有实现流量工程的路由技术，分析其主要特点及不足之处； ( 2 ) 深入研究约束路由的原理和构成，并围绕流量工程，分析实现要点，提出实现模型； ( 3 ) 分析o s p f 路由协议机制，针对约束路由和流量工程的要求，提出扩展方案； ( 4 ) 提出面向流量工程的约束路由，将它划分为三个模块：在线约束路由在选路时基于网络 状态、业务流需求等信息；离线约束路由不仅使路由满足业务流的多约束需求，且从全 局角度确定传输路径，使业务流分布更为合理，提高网络资源利用率；运用l i n u x 策略 机制实现策略路由，使选路满足策略要求。 ( 5 ) 研究m p l s 和r s v p 技术，将两者与约束路由相结合，运用r s v p 建立l s p 隧道： ( 6 ) 设计面向流量工程约束路由的原型系统框架，实现原型系统中的核心部分，并对原型系 统进行测试、分析和总结。 第3 页 面向流量工程的约束路由的研究和实现东南大学硕士学位论文 第二章流量工程及相关技术探讨 2 1 流量工程的内涵和目标 流量工程是因特网网络工程的一部分，主要用来处理网络运行时的性能优化问题，它包 括对网络流量的测量、建模、分析和控制等方面。它通过有效的使用网络资源、规划网络容 量、合理地将业务流分配到物理网络上，从而达到优化网络资源利用和性能以及提供高效可 靠的服务。从性能而言，流量工程的目标涉及到两方面 4 1 ：流量和资源。 面向流量的性能目标是增强和满足流量的q o s 需求，包括最大吞吐量、最小延时和最 小报文丢失率等等。 面向资源的性能目标主要是优化资源利用率。高效管理网络资源是达到资源性能目标的 途径。通常要保证不出现网络资源的部分子集过分利用而发生拥塞，而网络的另一些在 可行路径上的资源子集却没有得到充分利用。目前网络带宽是至关重要的资源，因此有 效管理带宽资源是流量工程的中心任务。 2 2 分组交换网络中流量工程机制的演化 从a r p a n e t 诞生开始，如何使网络性能最优化就成为人们关注的问冠。从业务流管理 的角度而言，当今的因特网仍然遵循“尽力而为”的模式。因特网使用了分布式的路由协议， 这些协议具有很好的可扩展性。然而，它们在选路时仅仅依赖于简单的算法，以至无法对路 由选择进行灵活控制。下面将对分组交换网络流量工程机制的演化嘲进行探讨： 2 2 1a r p a n e t 适应性路由 a r p a n e t ( a d a p t i v e r o u t i n g i n t h e a r p a n e t ) 的路由选择依赖于网络的当前状态，网络 各节点都要维护一张定期更新的网络最小延时表，该表记录了到达目的网络延时最小的路 由。通过查询最小延时表，数据报将沿延时最小的路径传输。这种方式会产生”t r a f f i c m a g n e t s ”效应，网络拥塞会在网络不同部分之间发生迁移，使得网络振荡、缺乏稳定性。 2 2 2因特网的动态路由 动态路由运用了最短路径算法，其中链路代价可以是静态的，比如由管理员指定：也可 以是动态的。比如代价是与网络延时或丢包率相关的函数。静态链路测度的一个重要缺陷在 于它没有将业务流矩阵考虑在内。同样，路由协议在选路时没有考虑业务流属性和容量约束。 因此会造成某些链路拥塞，某些链路空闲。动态链路测度虽然考虑了业务流矩阵，但由于网 络资源部署不合理、对业务流量和分部预测的不准确等原因，也会造成网络负载分布不均衡。 正是由于动态路由存在上述问题，引发了显示路由和约束路由的研究。 第4 页 面向流量工程的约束路由的研究和实现 东南大学硕士学位论文 2 2 31 b s t o s ( t y p eo fs e r v i c e ，服务类型) 指的是i p 封包在传送过程中要求的服务类型，一共 有8 个比特位，不同比特位的组合分别表示不同的意思。t o s 路 r f c 2 4 7 4 j j 指在选路时 不仅依据目的地址，还依据i p 报文中的t o s 字段。但通过t o s 来定义优先级是有限的，而 且在i p v 6 中将t o s 字段移除。 2 2 4e c m p e c m p ( e q u a lc o s tm u l t i p a t h ) 是运用多条等价路径传输数据分组的一项路由技术，它 旨在解决最短路径优先( s h o r t e s tp a t hf i r s t ) r f c 2 3 2 8 算法的不足。在传统s p f 算法中， 当通往目的网络存在两条或者两条以上最短路径时，算法将选择其中的一条。在e c m p 中， 这些路径都被保存在路由表中，传输业务流将在多条路径中进行分配。分配方式一般有两种： ( 1 ) 将报文以r o u n dr o b i n 方式分配到各路径上。这种方式明显会造成报文乱序； ( 2 ) 以流为单位，根据源目的地址、i p 报文头中的其它域，运用散列法进行分配。这种方 式依赖于业务流本身的特性，若传输业务流的特性相似，散列法的有效性大大降低。 2 3 流量工程机制分类【6 】 2 3 1基于时间、基于状态和基于事件 母基于时间( t i m e d e p e n d e n t ) 时间依赖型流量工程算法依据业务流的周期变化规则来进行路由选择，周期跨度一般较 长，比如以“日”为单位。此类算法不能适应业务流的突发性变化以及网络环境的改变。 专基于状态( s t a t e d e p e n d e n t ) 该类算法依据网络的当前状态选路。它能综合考虑网络或业务流的突发性变化，而这一 点是时间依赖型流量工程系统无法实现的。网络状态参数包括利用率、延时、丢包率等等。 网络状态参数可以通过如下几种方式获得： ( 1 ) 各路由器通过泛洪协议进行周期性扩散； ( 2 ) 某一路由器发送探测报文以搜集某路径的状态； ( 3 ) 运用单独的管理系统来搜集网络状态信息。约束路由属于状态依赖型。 状态依赖型算法有利于增强网络的效率和可伸缩性，时间依赖型算法则适用于业务流规 律性强的网络。 基于事件( e v e n t d e p e n d e n t ) 基于状态的流量工程算法需要借助a l b ( a v a i l a b l el i n kb a n d w i d t h ) 泛洪来传递网络状态 信息，而a l b 泛洪会消耗网络带宽、处理器等资源，并且限制了域的范围。基于事件的流量 工程算法则用自学习模型替代了a l b 泛洪，从根本上克服了基于状态流量工程算法的不足。 第5 页 面向流量工程的约束路由的研究和实现 东南大学硕士学位论文 2 3 2 离线和在线 根据路由计算时间的不同，可将流量工程算法分为离线和在线两类： 离线( o f f l i n e ) 以一定周期或者受特定条件触发( 如网络管理员的指令或网络出现拥塞) 情况下参与路由选择，它是非实时的； 在线( o n l i n e ) 则需要对网络的变化做出响应，它以实时的方式运行。与离线相比，在线 算法简单、执行效率高。 2 3 3集中式和分布式 集中式( c e n t r a l i z e d ) 方式下有一个中心控制节点，它负责收集网络中所有路由器及链路 状态信息，计算出路由，并将结果反馈给各路由器。这种方式能更有效地选路。但由于 很难得到完整的网络状态信息，导致性能和可行性较差。同时，中心控制节点需要高速 处理器和高带宽控制通道。 分布式( d i s t r i b u t e d ) 方式下需要借助泛洪协议扩散网络状态，各路由器收集到网络拓扑 和状态信息后，自行计算到达其它网络的路由。相对集中式而言，它有更好的性能和可 扩展性。 2 3 4基于本地信息和基于全局信息 寺本地( l o c a l ) 信息是指域内某部分网络的状态信息，如某条路径的带宽和丢包率。一般 分布式流量工程算法依据本地信息来进行路由决策。 + 全局( g l o b a l ) 信息是指整个网络域的状态信息，如全局业务流矩阵、所有链路的负载信 息。集中控制流量工程算法需要全局信息，分布式流量工程算法在某些情况下也需要全 局信息。 2 3 5 开环和闭环 夸开环( o p e nl o o p ) 流量工程系统仅依据本地信息作出控制决策，与反馈信息无关； 闭环( c l o s e dl o o p ) 流量工程系统依赖于反馈信息，反馈信息可以是历史的，也可以是 当前测量所得。 2 3 6战术型和战略型 母战术( t a c t i c a l ) 型流量工程系统是从局部角度丽非全局角度解决网络性能问题； 啼战略( s t r a t e g i c ) 型流量工程系统则从系统、全局的角度来提高网络性能，它不仅考虑实 施策略的短期影响，也考虑长期影响。 2 4 流量工程相关技术 i e t f 开展了一些与流量工程息息相关领域的研究：集成服务、r s v p 、区分服务、m p l s 、 i p p m 。这些技术产生的动机是使因特网支持新的服务类型，同时为流量工程的实现提供了 第6 页 面向流量工程的约束路由的研究和实现 东南大学硕士学位论文 有力的支持。 2 4 1 集成服务 随着多媒体应用以及各种应用正在不断被引入到网络中，它们具有不同网络需求，“尽 力而为”服务已不能继续满足这些需求。为了解决该问题，并提高网络容量、优化网络和资 源的使用，i e t f 提出了集成服务口1 ( i n t s e r v ) 体系结构，它是对现有i p 网络模型的一个增强 结构。r f c l 6 3 3 是第一个描述i n t s e r v 滇型的需求和基本组成的文献。i e t f 最终成立了集成服 务工作组，该工作组与r s v p q - 作组协同进行工作。i n t s e r v 除了传统的尽力而为服务之外， 还能够同时支持实时服务。它以每个业务流为基础，提供两种端到端的面向实时传输的服务 嗍：质量保证服务( g u a r a n t e e ds e r v i c e ) r f c 2 2 1 2 和可控载服务( c o n t r o l l e d - l o a ds e r v i c e ) r f c 2 2 11 】。图2 1 给出了集成服务的模型，该模型有以下几个组成部分； f 1 ) 设置协议( s e t u pp r o t o c 0 1 ) ：设置协议使主机或路由器能够动态地保留网络中的资源， 以便满足特殊业务流的服务需求，r s v p 就是设置协议的一个例子。 ( 2 ) 流量说明( f l o ws p e c i f i c a t i o n ) ：用于定义提供给一个特定业务流的q o s 。在i n t s e r v 模 型的上下文中所定义的流( f l o w ) 是指具有相同q o s 的、从某个源到目的端的一个分组流 的序列。从概念上不太严格地说，流量说明可以被看作是一个保留的网络资源的集合( 如最 小带宽等) ，这些资源是网络支持该业务流q o s 所必需保留的。 ( 3 ) 流量控制：在网络设备( 如主机、路由器或交换机) 中存在一些组件能够控制和管理为 支持特定q o s 所必需的网络资源。流量控制组件的配置可以采用某种信令控制协议，如 r s v p ，也可以采用人工配置。 图2 - 1 集成服务模型 路由器 2 4 2r s v p r s v p 7 l 是i n t s e r v 模型中的一个设置协议成员，它是一个信令协议，用于点到点通信和 点到多点通信中多媒体用户对网络资源的预留，也就是说r s v p 可以被用来向数据流途经的 所有节点发送服务质量请求，建立并维护所请求服务的状态。r s v p 给予实际应用一种从网 第7 页 面向流量工程的约束路由的研究和实现东南大学硕士学位论文 络中动态请求、接收和调整q o s 需求的能力，以适应网络变化。r s v p 具有如下重要特征： ( 1 ) 预留请求由接收方负责初始化以及向网络发送资源预留请求，而不是发送者。接收方根 据自身系统的特定环境和接收愿望指定不同的资源预留，然后生成合适的资源预留请求。这 种接收方启动的模式支持系统的异构性。 ( 2 ) 既支持单播的资源预留，又支持多点间的群组通信资源预留，并且允许预留的资源被多 个发送者共享或对同一个发送者的预留进行合作。 ( 3 ) 资源预留的建立在转发数据之前完成，且是单向的。 ( 4 ) r s v p 是软状态( s o i ls t a t e ) 协议，需要周期性刷新，从而支持动态的成员和路由变化。 ( 5 ) r s v p 支持几种预留模式，以适应各种应用，同时对不支持r s v p 的路由器提供旁路作用。 ( 6 ) r s v p 不是一个路由协议，它可以与其他的任何路由协议共同工作，如r p 、o s p f 或b g p ， 并用这些协议为r s v p 消息选择一条从源点到终点的路由。r s v p 具有很大的灵活性，其操作 不必依赖于某个特定的路由协议。 图2 - 2 的概念框图示意了r s v p 在组播环境中的工作过程。 _ ：p a t h p a t h t e a r , r e s v e i t , r e s v c o n f _ 一 ：r e s v , r e s v t e a r , p a t h e r r 图2 - 2r s v p 消息流向示意图 2 4 3区分服务 集成服务模型必须维护每个流的状态和信令，这样使得这种模型不利于扩展。因此， i e t f 在传统的尽力而为服务与i n t s e r v r s v p 所提供的针对每个业务流的复杂机制之间提出 了一种折衷方案，称之为区分服务”( d i f f s e r v ) 。区分服务并不是为数据流提供一个显式 的端到端的保证，而只是对不同的服务保证提供了不同的处理级别。比如在一个拥塞的网络 中，它无法保证数据流可以按照想要的资源进行传输，但是它可保证优先级更高的服务能被 优先传输。这样，即使在一个网络资源有限的网络中，也可比较公平的安排数据流的传输， 而当数据的传输有序的时候，许多拥塞等网络问题便易于解决。d i f f s e r v 的基本思想包括以 下几点： ( 1 ) 定义一组数量较小的服务类型和优先级。例如简单地定义低、中和高三个优先级别，或 者简单地定义尽力而为和实时两种服务类型。每一种服务类型都可以有一个与之相关的业务 流特性描述文件( p r o f i l e ) ，其中包含最大和晟小允许带宽以及突发长度和持续时间等信息。 ( 2 ) 在网络的边缘对所有分组进行分类，并标记每个分组所属的服务类型。该过程将检测每 个分组中的i p 报头或传输报头中的一个或多个字段。每个分组报头中都可能有一个或多个比 第8 页 面向流量工程的约束路由的研究和实现 东南大学硕士学位论文 特被标记，用来反映出该分组的服务类型以及某些每个跳( p e r - h o p ) 的行为如丢弃优先选项 ( d r o pp r e f e r e n c e ) 等。 ( 3 ) 核心网络交换机和路由器依据分组头中标记比特的内容来对分组进行处理，对不同类型 或级别的服务给予不同的处理方式，这也是区分服务的来源。 d i f f s e r v 为网络服务提供者所支持的各种服务提供很大灵活性和自由度。分组头中的服 务比特只被用于对分组进行分类的用途。定义和提供什么种类的服务完全由服务提供者来决 定。一些服务提供者可能会为高优先级的业务流提供带宽和时延的保证：而其他提供者可能 只能保证最小带宽。唯一的要求就是对这些比特语义的理解必须保持一致，以便使众多i s p 的网