（计算机应用技术专业论文）supanet的流量工程技术研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 在关于下一代网络的研究工作中，四川i 省网络通信重点实验室针对i n t e r n e t 面临的 高速交换、服务质量保障、安全性和移动性等问题，提出了单物理层用户数据交换平台 体系结构网络s u p a n e t ( s i n g l e 1 a y e r u s e r - d a t as w i t c h i n g p l a t f o r m a r c h i t e c t u r e n e t w o r k ) 。 迄今为止，实验室有关s u p a n e t 的工作主要集中在高速交换和服务质量保障体系的研 究，对关系到网络性能优化和提高网络通信与交换资源的利用率等方面的研究甚少。流 量工程是一种通过控制流量在网络链路上的分布，从服务质量和通信资源利用两方面优 化网络性能的技术。本硕士论文研究的主题就是s u p a n e t 中的流量工程技术。 在研究了现有的i n t e m e t 流量工程技术和s u p a n e t 中与流量工程相关的工作的基 础上，本文初步探讨了s u p a n e t 流量工程的实现框架。框架由信息发布与接收单元、 信令单元、优化控制单元和分组转发单元四部分组成，文中阐述了各个单元的功能和相 互之间的关系。 在优化控制方面，目前流量工程优化网络性能的方式主要有两种：路由算法和负载 均衡算法。s i7 p ! a n e t 提供面向连接的虚通路服务，流量通过虚通路最终映射到物理链 路上，因此，流量通过网络的路径决定于虚通路的路径，所以本文重点研究了连接建立 阶段的选径算法。鉴于s u p a n e t 是基于d w d m 通信环境，路径选择实际上是对波长 路径的选择。选径过程分为两步，端口选择和满足服务质量需求的最佳波长选择，本文 主要针对其端口选择过程。在分析现有的几种典型的流量工程路由算法的优缺点的基础 上，针对s u p a n e t 的特点，提出了基于业务流分类的路由算法( s c b rs e r v i c ec l a s s b a s e dr o u t i n g ) 。该算法分为配额分配和动态路由两部分。配额是指业务流占用链路的最 大传输能力，配额分配阶段根据业务流的流量特征，基于多商品流原理求解在给定的网 络资源条件下满足各种流需求的最优配额分配方案；动态路由算法在配额分配的基础上 为各类连接请求进行路由计算。动态路由算法中，以链路上各类业务配额的剩余量的函数 作为权重，反映链路在网络中的关键度，使当前连接尽可能避开关键链路，避免造成网 络拥塞。最后编程实现s c b r 算法，并与现有的两种典型算法m h a 、p b r 进行对比。 实验结果表明，该算法能够增加网络接纳的连接请求数，提高链路的利用率，同时使链 路负载更为均衡，改善了网络的整体性能。 关键词：单物理层用户数据传输与交换平台体系结构网络：流量工程；基于业务流分类 的路由算法；负载均衡 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t t h i st h e s i si sd e d i c a t e dt ot r a f f i ce n g i n e e r i n gt e c h n i q u e si ns u p a n e t , a l le x p e r i m e n t a l n g i ( n e x tg e n e r a t i o ni n t e r n c t ) d e v e l o p e da ts i c h u a nn e t w o r kc o m m u n i c a t i o nt e c h n o l o g y k e yl a b o r a t o r y s u p a n e ti sc h a r a c t e r i z e db yas i n g l e l a y e ru s e r - d a t as w i t c h i n gp l a t f o r m a r c h i t e c t u r et om e e tt h ec h a l l e n g e sf a c e d 、析me x i s t i n gi n t e r n e t , i e h i g h s p e e ds w i t c h i n g q o s p r o v i s i o n i n g ，s e c u r i t y , m o b i l i t y , a n d e t c t r a f f i ce n g i n e e r i n g ( t e ) i sat e c h n i q u e c o n c e r n e dw i t hn e t w o r k o p e r a t i o no p t i m i z a t i o n b o t hi ns e r v i c e p r o v i s i o n i n g a n di n c o m m u n i c a t i o n r e s o u r c eu t i l i z a t i o nb yd i s t r i b u t i n gt r a f f i cl o a d sa c r o s sn e t w o r kl i n k s t h i st h e s i sf i r s ti n t r o d u c e st h ea r c h i t e c t u r ea n dw o r k i n gp r i n c i p l eo fs u p a n e t , b a s e do n t h ea n a l y s i so ft h en e c e s s a r yo fs u p a n e tt r a f f i ce n g i n e e r i n ga n dt h el i m i to fi pt r a f f i c e n g i n e e r i n g ，s t u d i e st h eb a s i cf i a m e w o r ka n dm a i nc o m p o n e n t so fs u p a n e tt r a f f i c e n g i n e e r i n ga n dd i s c u s s e st h er e l a t i o n s h i pb e t w e e nt h e m t h e r ea r et w om a i na p p r o a c h e st o w a r d st e ，i e t oi m p r o v er o u t i n gp r o t o c o l sd y n a m i c a l l y a c c o r d i n gt r a f f i cm o n i t o r i n gr e s u l t sa n dt ou s eo fl o a d - b a l a n c i n ga l g o r i t h m st ol e a dt ob e t t e r c o m m u n i c a t i o nr e s o u r c eu t i l i z a t i o n c o n s i d e r i n gt h a ts u p a n e tp r o v i d e sq o s i n s u r e d , c o n n e c t i o n o r i e n t e dv n t u a lp a t hs e r v i c e p s ) t h ev pd e t e r m i n e st h ed i s t r i b u t i o no ft r a f f i c i nt h es u b n e t ，s ot h i st h e s i sf o c u so nt h ed y n a m i cr o u t i n ga l g o r i t h mb a s e do nt r a f f i cm o n i t o r i n g r e s u l t sc o l l e c t e di nu s e r - d a t ap l a t f o r mi ns u p a n e ta n dd i s t r i b u t e dv i at h et r a f f i cm e s s a g e e x c h a n g ep r o t o c o l ( t m e p ) ，b u tw i l ln o td i s c u s st r a f f i ci n f o r m a t i o nc o l l e c t i o na n de x c h a n g e p r o c e s sf u r t h e ra n da s s u l t i e st h a ts u c hi n f o r m a t i o ni sa v a i l a b l ea ti n d i v i d u a ln o d e s t h es u p a n e t a d o p t sat w o s t e pr o u t i n gp o l i c y , i e p o r tr o u t i n gt od e c i d eaf i b e rp a t hf o r ag i v e ns o u r c e - d e s t i n a t i o np a i ra n dl a m b d ar o u t i n gt os e l e c tal a m b d ab e s ts u i t a b l ef o rt h e r e q u i r e dq o sf o rt h a td a t as t r e a m b a s e do nr e s e a r c ho ft y p i c a la l g o r i t h m s ，t h ea u t h o rp r o p o s e s s e r v i c ec l a s sb a s e dr o u t i n ga l g o r i t h m ( s c b r ) f o rt h ep o r tr o u t i n g s c b ra l g o r i t h mh a st w o p h a s e s ：aq u o t ap r e p r o c e s s i n gp h a s e ，w h e r et op r e - a l l o c a t el i n kc a p a c i t i e sf o rv a r i o u st r a f f i c c l a s s e sb a s e do nt h em u l t i c o m m o d i t yf l o wp r o b l e m ；a n da no n l i n er o u t i n gp h a s ec o m p u t e dt h e r e a s o n a b l ep a t hf o ra ni n d i v i d u a lf l o wr e q u e s t t h eo n l i n ep h a s et a k e st h ef u n c t i o no ft h e a v a i l a b l eq u o t aa sl i n k sw e i g h t s i m u l a t i o nr e s u l t si n d i c a t et h a tt h ea l g o r i t h mp e r f o r m sb e t t e r t h a nt h et r a d i t i o n a la l g o r i t h m si na s p e c t so f n e t w o r kl o a db a l a n c ea n dr e q u e s tr e j e c t i o nr a t i o k e yw o r d s ：s i n g l ep h y s i c a ll a y e r u s e r - d a t as w i t c h i n gp l a t f o r ma r c h i t e c t u r e ( s u p a n e t ) ； t r a f f i ce n g i n e e r i n g ( t e ) ；s u p a n e ts e r v i c ec l a s sr o u t i n g ( s c b r ) ；l o a d b a l a n c e ； 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西 南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书： 2 不保密囹，使用本授权书。 ( 请在以上方框内打“”) 学位论文作者签名：主1 这少 日期：2 0 1 0 年月7 多日 指导老师躲嗜 日期：2 0 1 0 年6 月1 3 日 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 在研究现有的流量工程模型的基础上，结合s u p a n e t 本身的特点，探讨了 s u p a n t 的流量工程实现框架，论述了构成框架的各个模块的基本功能和模块之间的关 系。 ( 2 ) 对s u p a n e t 流量工程中的路由算法进行了重点研究。借鉴p b r 算法对带宽进 行离线预分配的思想，研究了一种基于业务流分类的流量工程路由算法( s e r v i c ec l a s s b a s e dr o u t i n g ，s c b r ) 。实验结果表明，s c b r 算法能够较好的均衡各链路之间的流量负 载，避免了网络拥塞，从而接纳更多的连接请求，优化了网络资源的利用率，改善了网 络的性能。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。 除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的 研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。本人完全 了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名：纠运矩 日期：叼哆 西南交通大学硕士研究生学位论文、第1 页 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 第1 章绪论 1 1 项目背景和研究对象 本硕士论文的大背景是下一代网络( n e x tg e n e r a t i o ni n t e r n e t ) 体系结构，具体研究 背景是四川省网络通信技术重点实验室进行的有关n g i 体系结构的研究，即以“面向以 太网的物理帧时槽交换技术”( e t h e m e t - o r i e n t e dp h y s i c a lf r a m et i m e s l o ts w i t c h i n g ， e p f t s ) 1 】为基础的“单物理层用户数据传输与交换平台体系结构网络 ( s u p a n e t - s i n g l e 1 a y e r u s e r - d a t at r a n s p o r ta n ds w i t c h i n gp l a t f o r ma r c h i t e c t u r en e t w o r k ) 1 2 。 i n t e m e t 规模的膨胀、多媒体应用需求的增加以及通信技术的发展，使 n t e r n c t 面临 着高速交换、服务质量保障、网络安全和移动性等多方面的挑战【1 】。人们开始研究能够 迎接上述挑战的下一代网络( n g n n e x tg e n e r a t i o nn e t w o r k ) 和下一代i n t e m e t c n g i ) 4 5 6 。s u p a n e t 正是在此背景下提出的。 考虑到未来通信技术在传输速率与误码率方面的巨大差异，实验室对n g i 的研发思 路是：首先以d w d m 为底层的数据传输技术( 多波长、高单波长速率、低误码率) ，采 用带外信令思想，将通信网络分为信令控制与管理平m 7 ( s i g n a lc o n t r o la n dm a n a g e m e n t p l a t f o r m ，s & mp l a t f o r m ) 和用户数据传输与交换平台( u s e rd a t at r a n s p o r ta n ds w i t c h i n g p l a t f o m ，u - p l a t f o r m ) ，实现控制与转发的分离，从而将传统数据链路层与物理层的基本 传输功能与通信子网的分组交换功能相集成，形成高速、高效、服务质量可保障的骨干 通信子网交换平台。在此基础上，逐步将s u p a 体系结构向外扩展到通信误码率较低的 接入网络，实现广大范围的s u p a n e t 。对于误码率高的接入网可以保留多层网络平台 实现与骨干s u p a n e t 的接入。这就是我们提出的“骨干通信子网优先，外延次之” ( b s f o e s ) 的n g i 研发策略【。 迄今为止，有关s u p a n e t 的研究工作的重点在于构建高速、高效、服务质量可保 障的骨干通信子网。特别是在交换平台上的相关工作在一定程度上与网络节点的交换性 能有关。如单层用户数据传输与交换平台和超前交换技术【8 加快了中间节点的处理过程； 基于开关交换矩阵( c r o s s b a r ) 的交换结构【9 】和基于时槽加权的公平调度算法( t i m e s l o t w e i g h t e df a i rs c h e d u l i n ga l g o r i t h m ，简称t w f s ) 【1 0 】提高了交换节点的吞吐率，保证了 s u p a n e t 的高速交换。另一些研究工作与本项研究有着更为密切联系、有助于流量工 程的实现，它们既涉及控制管理平台( s & m 平台) ，也涉及用户平台( u 平台) 。如： 信控管理平台( s & m 平台) 的呼叫准入控制 1 1 c a c ( c a l la d m i s s i o nc o n t r 0 1 ) 通过限制新 呼叫的接入避免网络过载；流量管理信息交换协议t m e p ( t r a f f i cm a n a g e m e n ti n f o r m a t i o n e x c h a n g ep r o t o c 0 1 ) 1 2 】作为流量信息交换载体协议，可实现相关应用层实体间可用信息 西南交通大学硕士研究生学位论文第2 页 的交换；波长配额约束机审j j ( q u o t ac o n s t r a i n t ) 分配与动态配额调整机制等都是静、动态 网络性能调整( t u n i n g ) 的可用机制等等，各类路径信息选择协议也是可施加影响改变 网络流量的手段等等。用户数据平台( u 平台) 上的基于服务质量协商的入网控制 q u a c f l l j ( q o s - b a s e du s e r - d a m a d m i s s i o nc o n t r 0 1 ) ，能根据网络拥塞状况，在s u p a n e t 入网边界路由器上，基于服务质量协商的结果按照相应的入网控制策略对用户数据进行 入网速率控制也是重要的减缓拥塞的手段和有利于流量工程实施的手段。但是，在宏观 上调整、优化网络性能以及如何利用上述机制实现网络性能优化方面的研究尚未进行， 这就是本论文的研究对象一s u p a n e t 的流量工程技术，以期实现在保障服务质量的前提 下，减少拥塞和合理有效利用网络资源。可见，本项工作对s u p a n e t 的研究具有重要 的意义。 1 2 流量工程概述 近年来，i n t e m e t 上的各种应用以及新业务层出不穷，如v o i p 和网络电视等，使得 网络上的信息与日俱增。网络新业务在带动i n t e r n e t 迅速发展的同时，也给网络造成极 大的压力。这要求网络运营商必须有效地提高现有网络资源的利用率以满足日益增长的 业务量需求，并实现利益的最大化。i n t e m e t 流量工程就是在这种背景下提出的一种用来 预测网络状况，控制网络资源，提高网络性能，满足业务要求的网络技术。 i e t f ( t h ei n t e r n e te n g i n e e r i n gt a s kf o r c e ) 对i n t e m e t 流量工程的定义别1 3 】：对p 网络 实施性能评估和优化的行为，研究的范围包括流量的测量，分析，建模和控制等方面， 旨在从流量、资源和网络规划等方面解决网络的拥塞问题、负载均衡问题和服务质量等 问题。 作为一种通用的实现方案，流量工程可以在各种网络中实施【l4 1 ，如在以路由器为核 心的网络 1 5 , 1 6 ，i po v e ra t m f r 等重叠网络【1 刀和m p l s 网络 1 8 , 1 9 等。尤其是m p l s 技 术在解决流量工程问题方面具有的独特优势使它成为流量工程研究的热点 2 0 - 2 3 。目前对 流量工程的研究主要集中在三个方面：路由控制、负载均衡和网络测量。路由控制是研 究各种路由算法和各种路由策略，目前这方面的研究己经取得大量成果。负载均衡的重 点是在多条并行的链路上，依据一定的策略，实现对流量的最优化分配。随着用户对业 务服务质量要求的提高，这种技术还必须能够支持业务的q o s ，即在实现负载均衡的同 时，也要考虑业务的q o s 需求。网络测量在流量工程中占据着重要的地位，尤其对整个 流量工程系统的实现【2 引。网络测量主要指对网络各种性能参数的测量，如对时延、带宽、 丢包率以及吞吐率等性能参数的测量。流量工程的控制策略大多是根据网络测量的结果 作出相应的判断，进而保证整个网络的健康运行，优化网络性能。 流量工程的性能指标可以分为两种：面向流量的和面向资源的。面向流量的性能指 标包括了增强流量q o s 功能的各个方面。包括：对分组丢失的最小化、对时延及时延抖 动的最小化、对吞吐量的最大化等。面向资源的性能指标包括了优化资源利用的各个方 西南交通大学硕士研究生学位论文第3 页 面。包括链路利用率提高、网络负载均衡、拥塞避免等。针对不同的网络和不同的业务 类型，对各项指标有不同的要求。 1 3 本论文研究内容及章节安排 1 3 1 本论文研究内容 本论文的研究对象是未来s u p a n e t 的流量工程技术，s u p a n e t 流量工程与现有 流量工程技术的应用基础不同。s u p a n e t 致力于为用户提供有服务质量保障的面向连 接的高速交换服务，其流量工程所解决的问题主要是：当建立连接的请求不可预料地不 断地到达时，如何在网络中合理配置这些连接使得整个网络的资源利用率达到最优，同 时必须考虑不同数据流的服务质量问题。连接通常就是一条通过信令在网络中建立起来 的软通道，该通道在经过的各个节点预留了所需的网络资源。具体研究内容主要包括： ( 1 )分析现有的流量工程实施方式和基于流量工程的路由技术，探讨能否为 s i7 p ! a n e t 的流量工程所借鉴。 ( 2 ) 针对s u p a n e t 体系结构特点和工作原理，参考现有的流量工程机制，探讨 适合s u p a n e t 的流量工程实施方式。 ( 3 )在建立s i 用a n e t 流量工程模型的基础上，提出s u p a n e t 连接建立阶段基 于流量工程的选径算法，并验证其性能。 1 3 2 本论文章节安排 本文的主要内容共分为五章。 第1 章：绪论。阐明本文选题的研究背景及意义，并对题目相关领域的研究现状进 行了综述，引出论文的研究内容和论文的结构安排。 第2 章：i n t e m e t 流量工程研究。研究现有的流量工程实施模型和一些用于实现流量 工程的典型路由算法，分析其优势和不足，并探讨能否为s u p a n e t 流量工程所借鉴。 第3 章：s u p a n e t 流量工程相关研究。首先介绍s u p a n e t 体系结构、工作原理 以及实验室现有与s u p a n e t 流量工程相关的研究工作，在此基础上，提出s u p a n e t 的流量工程实施框架，并阐述了构成框架的各模块的功能和相互之间的关系。 第4 章：s u p a n e t 流量工程的路由算法。分析s u p a n e t 现有的波长选择算法的 不足，研究了一种适用于s u p a n e t 的基于业务流分类的路由算法，并详细论述了算法 的原理和实现过程。 第5 章：模拟实验。编程实现基于业务流分类的路由算法，选择适当的网络拓扑结 构，与两种现有的典型算法m h a 和p b r 算法进行比较，分析其性能。 最后对论文进行总结并对今后有待进一步研究的问题进行展望。 西南交通大学硕士研究生学位论文第4 页 第2 章i n t e m e t 流量工程研究 流量工程的主要应用目的是从资源和流量两个层面上优化网络性能，它不是特定于 某一个网络的产物，而是一种通用的实现方案。本章分析了流量工程在不同网络上的实 施方式和几种支持流量工程的路由算法，作为s u p a n e t 实施流量工程的参考。 2 1 流量工程在不同网络中的实施 流量工程的技术发展可以划分为三个重要的时期，即以路由器为核心的网络，p 与 a t m “重叠的网络以及以m p l s 为核心的网络。下面将分别对三中不同网络中流量工 程的实施方式进行研究。 2 1 1 以路由器为核心的网络中的流量工程 在基于路由器的核心网中，通过传统路由协议的扩展实施流量工程。己经形成的 r f c 标准有：r f c 3 6 3 0 和r f c 3 7 8 4 。其中，r f c 3 6 3 0 是在第二版开放式最短路径优先 协议( o s p f ) 上实施流量工程扩展的标准，而r f c 3 7 8 4 则是在中间系统( i s i s ) 协议上实施 流量工程的标准。 o s p f 将实际网络、路由器抽象成有向网络图来工作。网络图存放在一个数据库中， 该库用一条记录代表网络的一条链路，描述相应链路的状态信息。每个路由器维护相同 的数据库。当链路状态信息发生变化时，通过链路状态广播( l s a ) 数据包传递网络的 状态信息，保持各路由器中数据库的一致，可以看出流量工程数据库是整个流量工程的 关键，它是依靠流量工程l s a 建立的。路由器根据这个数据库计算出路由表。 i g p 路由计算是拓扑驱动的，其计算基于简单的度量，比如跳数或管理员赋予的值， 不考虑网络上的业务负载。结果，业务不能在网络连接中平均分配，导致昂贵的网络资 源未能被有效使用。一些链路可能发生阻塞的同时，另一些链路未被充分使用。而且， 传统的基于软件的路由器所能聚合的带宽和分组处理能力是有限的，在负荷较大时有着 潜在的流量瓶颈，随着口网络规模越来越大，基于量度的流量控制就越来越显出它的局 限性。 2 1 2 重叠网络中的流量工程 为了克服上述阶段流量工程实现技术的缺陷，人们提出了使用“重叠”模型，例如 口o v e ra t m 、口o v e rf r 等实现流量工程的技术方案。 当口运行在a t m 网络上时，基本思想为：路由器通过a t m 网络的p v c ( p e r m a n e n t v i r t u a lc i r c u i t ) 与其它路由器进行通信。p v c 的功能就是一条逻辑电路，通过它实现任 西南交通大学硕士研究生学位论文第5 页 i 意两个路由器间的相连，但路由器并不知道提供p v c 的基本物理拓扑信息如何。这些虚 电路对口路由协议来说，表现为真实的物理链路一样。 a t m 核心网通过p v c 的配置对网络实施明确的流量工程控制。网络管理人员通过 对p v c 进行路由将业务分配到所有链路上去，使链路被平均使用。a t m 交换机提供每 条p v c 的统计信息，简化了对用于优化p v c 布局及管理的业务参数进行监测的过程。 通过对p v c 进行配置的流量工程在一段时间内满足了i s p 对流量工程功能的需求， 但是以a t m 为核心的口网络配置全闭合的a t mp v c 将产生传统的n 平方问题，扩展 性较差；口分组要转换为a t m 信元传输，将引入大约2 0 的信元开销；路由和流量工 程分别在不同的系统上来完成，增加了网络的复杂性。以上各种问题的存在使这种流量 工程的方案经受着严峻的挑战。 2 1 3m p l s 流量工程 m p l s 技术的出现解决了重叠模型的复杂性和难以扩展的问题。其核心思想是将分 组转发与控制相分离，基于标签对分组进行转发。入口标签交换路由器( l a b e ls w i t c h i n g r o u t e rl s r ) 将具有相同转发路径需求的分组划分为一个转发等价类( f o r w a r d i n g e q u i v a l e n tc l a s s ，f e c ) ，并为其分配“标签”。当分组第一次进入m p l s 网络时，路由器 为其建立标签交换路径( l a b e ls w i t c h e dp a t h sl s p ) 。在数据传输时，根据标签将分组数据 流分配到预先定义的l s p 上，完成数据的转发。m p l s 实际上提供的是一个“面向连接 的交换”，主要通过对l s p 的控制和管理实现流量工程。 基于m p l s 的流量工程主要由以下几个功能模块构成： 1 扩展的i g p 流量工程需要一些有关网络状态和网络属性的动态信息，如最大链路带宽、链路可 用带宽和链路属性等。这些信息的获取是通过i g p 的扩展特性来实现。 每个l s r 通过一个特殊的流量工程数据库( t r a f f i ce n g i n e e r i n gd a t a b a s e ，t e d ) 对网络 链接特性和拓扑信息进行管理1 2 5 , 2 6 。t e d 专门用于计算l s p 通过物理拓扑时的路径。一 个分离的数据库被维护以使并发的流量工程计算与i g p 和i g p 链接状态数据库独立开 来，同时，i g p 无改变地继续运行，通过路由器链路状态数据库所包含的信息进行传统 的最短路径计算。 2 显式路由 在m p l s 网络中，流量工程的基本元素是l s p ，通过对l s p 的操作和管理，进行控 制网络流量的分布。l s p 建立有两种方式：逐跳选择和显式路由机制。逐跳选择使用传 统的动态路由算法来决定l s p 的下一跳，每个节点独立的为f e c 选择下一跳，对于下 一跳的改变由本地决定。显式路由使用流量工程技术或者手动制定路由，不受动态路由 影响，路由计算可以中可以考虑各种约束条件，由l s p 的入口路由器选定路径。由于预 西南交通大学硕士研究生学位论文第6 页 定义了路径，数据分组在中间节点交换，不需要在每一节点上作出路由选择决定。m p l s 主要通过显式路由来支持流量工程。 由于m p l s 的基本思想是将路由控制与数据转发相分离，为采用约束路由算法进行 路径计算，提供了足够的灵活性，计算得到的路径可以由信令模块实现自动配置。 3 信令协议 信令协议主要用于建立和拆除l s p ，协调和管理l s p 的各种操作，维护l s p 紧邻间 的通讯，并负责环路检测和各种消息的处理。因为存储在起始l s r 的t e d 中关于网络 状态的信息在任何时候都是过期的，因此路由算法计算出的路径只是被认为是可以接受 的。只有在l s p 被信令部分真正建立之后，才能知道这条路径是否真正可以工作。负责 建立l s p 状态和标记分配的信令部分依赖于资源预定协议( r s v p ) 的一些扩展参数，如外 在路由对象、标记请求对象、标记对象等。 m p l s 主要是通过显式路由方式建立l s p ，确定转发途径，在需建立大量l s p 时， 势必造成运营管理的极大压力，而且当网络业务流由于突发而出现瞬间拥塞时，m p l s 流量工程就无能为力了，这时就需要有微观的机制去控制业务流，以更好地保证业务的 q o s 。 区分服务( d i f f s e r v ) 模型提供了基于类别的q o s ，具有良好的可扩展性，但缺乏 有效的端到端的部署机制；m p l s t e 通过有效地管理带宽资源，间接改善了网络q o s ， 但其带宽管理以及l s p 都无法做到基于业务类别。如果既能够保留d i f f s e r v 针对不同业 务提供不同等级q o s 的特点，又能基于每个d i f f s e r v 业务类采用m p l s 流量工程，则 可能结合二者的优点来改善网络的q o s 性能。正是基于此，业界提出m p l s d i f f s e r v a w a r et e 的解决方案。m p l sd i l t s e r v a w a r et e 在原来m p l s t e 的基础上增 加了基于类别的资源管理，既能为业务提供不同等级的q o s 保证，又能充分利用网络 资源，还能利用l s p 保护切换实现故障恢复，充分保证高优先级业务的q o s 。然而， 由于现有口承载网端到端路由的不确定性，m p l sd i f f s e r v - a w a r et e 无法绕过m p l s 的不足，其本身的实现非常复杂，目前亦没有较理想的基于类别的资源管理的实现机制， 因而难以解决q o s 问题【2 7 j 。 应当指出：尽管在无连接的i n t e m e t 通信子网中和在l s 、a t m 等面向连接的通 信子网中已有大量有关流量工程技术的研究，但是，s u p a n e t 的大容量、高速率和服 务质量可保障的通信子网中，我们必须重新审视已有的流量工程技术，研究其利弊和可 用性，必要时应探讨新的技术。 2 2 流量工程路由算法研究 2 2 1 路由算法概述 从上述分析可以看出，无论对那种实现方式，动态路由都有着重要作用。好的路由 西南交通大学硕士研究生学位论文第7 页 算法在满足流量请求的同时，能够利用网络流量及资源信息，为流量请求合理选径，将 流量较为均匀的分布在网络中，避免发生拥塞。 通过图2 1 的示例可以看出路由算法的重要性。在图2 1 中，( s 1 ，d 1 ) ，( s 2 ，d 2 ) ，( s 3 ，d 3 ) 是可能的“源端目的端”对，设所有链路均只剩1 个单位的带宽。当有用户请求s 3 n d 3 的1 个单位带宽的流量通道时，基于跳数考虑的简单算法会选择1 7 8 5 ，那么当( s 2 ，d 2 ) ( s 3 ，d 3 ) 间有流量请求到达时就会被拒绝。但如果一开始选择的是1 2 3 _ 4 5 n 网络还可以 容纳新的流量请求，从而网络利用率更高。 sl s 2 s 3 di d 2 d 3 图2 - l 全局优化路由算法的例子 目前这一领域已有了一些研究成果，下面将概述已有各种典型算法的技术关键和特 点。在这些算法中都存在一个“可用链路”的概念，其含义是如果某链路带宽扣除已预 定带宽后的剩余带宽比到达的流量请求大，则称该链路相对于当前流量请求是一条“可 用链路”。 2 2 2 典型算法分析 ( 1 ) m h a m h a ( m mh o p 舢g o 删m ) 算法是最简单也是也是使用最普遍的一种算法【2 8 】。该算法 找一条从源端到目的端跳数最少的由可用链路组成的路径，属于贪婪算法。m i - i a 没有 将源端和目的端的分布信息考虑在内，容易导致多条最短路径都选用同一条链路而发生 拥塞。如o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 和c s p f ( c o n s t r a i n t ss h o r t e s tp a t hf i r s t ) ，都是基 于最小跳数思想。 ( 2 ) w s p 和s w p w s p ( w i d e s ts h o r t e s tp a t h ) 年ns w p ( s h o r t e s tw i d e s tp a t h ) 是在m h a 基础上的改进【2 9 】。 w s p 的思想是在所有从源、目的端口间跳数相等的m i n - h o p 路径中寻找一条“剩余带宽” 最大的通路。s w p 则正好与之相反，是在所有从源端到目的端剩余带宽相等的路中寻找 一条“跳数最小”的通路。这些算法的简单性保证了其实现上比较容易，但是对于类似 西南交通大学硕士研究生学位论文第8 页 于图2 1 中的网络都存在利用率不高的问题。 ( 3 ) 最小干扰算法( m i r ) 随着路由器处理能力的增加，可以采用适当复杂些的路由算法，以达到更优化地 使用网络资源的目的。在这方面的研究中，最有影响力的是k o d i a l a m 等提出的一种基于 最大网络流理论的最小干扰路由模型m i r ( m i n i m u mi n t e r f e r e n c er o u t i n g ) 【3 0 1 ，并应用于 m p l s 流量工程服务器r a t e s 中【3 1 | 。 m m 算法基于最大网络流理论，引入了s d ( s o u r c e d e s t i n a t i o n ) 节点对( 以下简称节 点对) 的概念。在m 瓜模型中，虽然以后的路由请求是未知的，但所有流量进入网络的 源节点和流出网络的目的节点对却是能够事先确定的。节点对是m 承算法的一个创新， 是一个很重要的概念。m r 算法所需要的信息包括：网络拓扑结构，链路可用带宽以及 节点对信息。由于一条链路可以同时承载不同节点对的传输流量，因此计算得到的路径很 可能会阻塞以后到达的请求。m 瓜算法利用节点对信息，很好地解决了这个问题。 m 瓜算法的关键思想是：在进行路由计算时，着重选取那些对其他各个节点对的未 来流量请求干扰最小的链路。这里的“干扰”是指在一条q o s 路径预留带宽资源后，可 供其他s d 对间的最大流量就会减小。m 瓜的优化目标就是在选择一条路径时最大化其 他s d 对的加权最大流的和。 文献 3 0 中给出了算法的数学模型。设网络g ( n ，l ，b ) 为双向网络。其中n 和l 分别 表示节点和为链路的集合，b 表示链路的带宽。令f i 和m 分别表示网络中节点和链路的 数目。假设链路带宽和连接请求的带宽都为整数。p 表示网络中的s d 对的集合，即 ( s ，d ) p ，s 表示源节点，d 表示目的节点。假定所有的连接请求的源、目的节点对都在p 中。矩阵m 表示节点集n 和链路集l 的关系，矩阵的行对应于网络中的节点，列对应 于网络的链路。在链路( u ，v ) 所在的列中，第u 行元素值为1 ，第v 行元素值为一1 ，其他 行元素为0 ，且假定链路的编号是随意的。x 鲥表示对应于( s ，d ) p 的m 维向量，如表 示当前网络中节点对( s ，d ) 间可通过的的最大流量。r 表示网络中当前链路的剩余容量矩 阵，初始化时为b 。e 耐表示i 1 维的向量，在目的节点处为1 ，源节点处为1 ，其余节点 处取0 。假定每次到达一个连接请求，请求的源、目的节点对为( 口，b ) p ，请求带宽为 d 。建立l s p 请求( 4 b ，d ) 的路由的优化目标是最大化除节点对( a ，b ) p b 的所有s d 对之间 最大流量。 优化的目标函数可以表示为： m a x 乙 口耐铭 ( 2 1 ) 一 一 ( j dj e p 、( 口6 ) 同时满足如下约束： m x 耐= 钆p 耐v ( s ，d ) p ( 口，6 ) m x ”：一d e 4 6 ( 2 2 ) ( 2 3 ) 西南交通大学硕士研究生学位论文第9 页 x 埘+ x 曲r v ( s ，d ) p ( 口，6 )( 2 - 4 ) x 删0 v ( s ，d ) p( 2 5 ) x 曲 o ，d ”( 2 6 ) 式( 2 1 ) 是目标函数，口耐表示节点对( s ，d ) 的权值，标识其在网络中的关键度。式( 2 2 ) 表示所有的节点对( s ，d ) p ( 口，b ) 之间的最大流量的和。式( 2 3 ) 保证d 单位流量从节点 a 流向节点b 。式( 2 _ 4 ) 是链路的带宽约束，表示网络中的最大流量不能超过网络中的剩余 流量。式( 2 5 ) 和式( 2 6 ) 表示所有请求的带宽是从单一的路径上路由的，没有进行流量的 分拆。 在生成具体算法的过程中，将目标函数式进行求导计算转化为各个链路的权值，然 后利用d i j k s t r a 算法计算最短加权路径。链路的权值计算公式为： w ( ，) = 口埘 ( 2 - 7 ) s d1 ：l c d 巳表示节点对( s ，d ) 的关键链路，当路由通过此链路时，加权最大网络流之和会减小。 与目前可用的其它常用算法比较，最小干涉算法具有突出优点，但是实验证明，最