（通信与信息系统专业论文）多业务量矩阵下te算法性能研究.pdf

摘要 摘要 近十年来，i n t e m e t 得到了引人注目的发展。随着i n t e r n e t 的快速发展，网络规 模和业务量急速增长，用户对网络性能的要求也越来越高，这对网络服务商提出 了严峻的挑战，如何满足客户的需求迫在眉睫。流量工程应运而生。流量工程是 一种具有重要价值的网络优化技术，它通过优化网络资源的利用率来避免网络拥 塞。传统的流量工程算法针对的均为精确的业务量矩阵，通过多商品流问题就可 以解决。实际上要想精确的获取业务量信息是很困难的，对于规模巨大的i n t e r n e t ， 其业务又时常改变，在动态改变的业务量矩阵或不确定业务量矩阵的环境中寻找 一组有效的，鲁棒的路由方案是很多大型i s p 网络运营商不得不关注的问题。这 种动态性或不确定性可以用多个业务量矩阵来表示，也即多业务量矩阵下流量工 程的求解。 一 本文主要研究的是多业务量矩阵中t e 算法相关问题。第二章主要讨论了多业 务量矩阵t e 算法中性能指标问题，主要包含了最差性能，平均性能以及它们之间 的折中性能，通过设计平均性能与最差性能权重和因子来控制折中性能，并发现 利用该因子获得的最优化问题具有某些特殊的特性，即平均性能是折中因子的非 递减连续函数，最差性能是折中因子的非递增连续函数。并强调了后面章节考虑 的性能指标是最差性能。第三章为基于o s p f i s i s 多业务量矩阵下t e 算法的研 究，首先讨论了单业务量矩阵下的基于o s p f i s i s 路由优化的问题，传统算法均 为n p h a r d 问题，然后扩展到多业务量矩阵下的路由优化，设计了多套不同的启发 式算法来求解。并着重分析了其中一种算法的性能因子，并发现该算法中k 最短 路算法k 的取值，迭代次数对算法性能有很大的影响。第四章讨论了采用e c m p 分流机制下多业务量矩阵算法的研究。也是从单业务量矩阵最优化扩展而来，设 计了多套算法，并着重分析其中一种算法的性能因子。第五章首先讨论了多业务 量矩阵下如何求解满足运营商性能要求的路由方案，通过设计一种启发式算法用 于求解一套满足要求的方案。当一套路由不能满足要求时，则需使用多套路由方 案，然后着重分析了在多套路由下如何通过监控最少的链路信息最快的切换路由。 最后，本文还考虑了多业务量矩阵的合并算法。 关键词：流量工程，多业务量矩阵，启发式算法，k 最短路 i a b s t r a c t a b s t r a c t t h ei n t e r a c th a sg o w nd r a m a t i c a l l yo v e rt h ep a s t10y e a r s w i t ht h ef a s t d e v e l o p m e n to fi n t e r n e ta sw e l la sa b u n d a n c eo fn e t w o r kt r a f f i ca n dh i g hr e q u i r 锄e n t o fn e t w o r kp e r f o r m a n c e ，i tc h a l l e n g e dt h en e t w o r ki s pv e r ym u c h t r a f f i ce n g i n e e r i n g i sc o m i n g t ei so n eo ft h em o s ti m p o r t a n tn e t w o r ko p t i m i z a t i o nt e c h n i q u e sw h i c ha r e m a i n l yd e a l tw i 也o p t i m i z a t i o nf o rn e t w o r kr e s o u r c e st o a v o i dn e t w o r kc o n g e s t i o n t h e o r e t i c a l l y , i ft h et mi sk n o w ne x a c t l y , t h e na r lo p t i m a lr o u t i n gf o ri tc a r lb eo b t a i n e d b ys o l v i n gt h ec o r r e s p o n d i n gm u l t i c o m m o d i t yf l o wp r o b l e mi n s t a n c e u n f o r t u n a t e l y , m e a s u r i n ga n dp r e d i c t i n gt r a f f i cd e m a n d s a r ei l l u s i v ep r o b l e m s f l o wm e a s u r e m e n t sa r e r a r e l ya v a i l a b l e0 1 1a l ll i n k s f o ral a r g e s c a l e i n t e r n e tw i t hb u r s t yd e m a n d s ，i ti s i m p o r t a n tf o rl a r g ei s p n e t w o r ko p e r a t o r st of i n das i n g l er o b u s to rf i x e ds e to fr o u t e st o o p t i m i z et h ep e r f o r m a n c eo v e rm u l t i p l et m s m u l t i p l et m s c a nb eu s e dt oc h a r a c t e r i z e t h ec h a n g eo ft r a f f i co rt r a f f i cu n c e r t a i n t yi ne x o g e n o u st r a f f i c t h i sp a p e rc o n c e n t r a t e so nt h et o p i co ft r a f f i ce n g i n e e r i n gb a s e do nm u l t i p l et r a f f i c m a t r i c e s i nc h a p t e r2 ，w em a i n l yd i s c u s st h ep r o b l e mo fp e r f o r m a n c em e t r i cw h i c h m c l u d ea v e r a g ec a s ep e r f o r m a n c e , w o r s tc a s ep e r f o r m a n c ea n dt h e i rt r a d e o f fi nt r a f f i c e n g i n e e r i n gb a s e do nm u l t i p l et r a f f i cm a t r i c e s w ep r o p o s ean o wm e t r i c 。aw e i g h t e d s u mo ft h ea v e r a g ec a s ea n dt h ew o r s tc a s ep e r f o r m a n c e - t oc o n t r o l 血et r a d e o f fb e t w e e n t h e s et w oc o n s i d e r a t i o n s w ep r o v et h a to p t i m i z i n gr o u t i n gu s i n gt h i sm e t r i ch a s d e s i r a b l ep r o p e r t i e s ，s u c ha st h ea v e r a g ec a s ep e r f o r m a n c eb e i n gad e c r e a s i l l g ，c ( ) i l v e x f u n c t i o nt ot h ew o r s tc a s ep e r f o r m a n c e t h e nw ed i s c u s st h em e t r i ci no u rr e m a i n i n g c h a p t e r sa r ea l la b o u tt h ew o r s tc a s ep e r f o r m a n c e i nc h a p t e r3 ，t h et o p i ci sa b o u t t r a f f i c e n g i n e e r i n gb a s e d o no s p f i s i sr o u t i n gp r o t o c o lf o rm u l t i p l et m s w ef i r s tp r o v et h a t t h et r a d i t i o n a lt ea l g o r i t h m sf o rs i n g l ea c c u r a t et ma r en p h a r dp r o b l e m sn o tt o m e n t i o nt ea l g o r i t h m sd e a l i n gw i t hm u l t i p l et m s w et h e np r o v i d es e v e r a lh e u r i s t i c a l g o r i t h m sf o rm u l t i p l et m s a n dw cs t r e s so no n ep a r t i c u l a ra l g o r i t h mt od i s c u s sw i t h e l e m e n t so ft h a ta l g o r i t h mh a v eg r e a ti m p a c to no u rp e r f o r m a n c e a n dw ef i n dt h e p a r a m e t e rkf r o mks h o r t e s tp a t ha l g o r i t h ma n di t e r a t i v ec y c l e sh a v ed e e pr e l a t i o nw i t h t h el a s tp e r f o r m a n c e i nc h a p t e r4 ，w es u p p o s es e v e r a lh e u r i s t i ca l g o r i t h m sf o rt r a f f i c i i a b s t r a c t e n g i n e e r i n gf o rm u l t i p l et r a f f i cm a t r i c e s ，w h i c ha r es i m i l a rt ot h ea l g o r i t h m si nc h a p t e r 3b u tn o tt h es a m e a n dt h e nw ed i s c u s sf a c t o r st h a ti n f l u e n c et h ef i n a ln e t w o r k p e r f o r m a n c e i nc h a p t e r5 ，w em a i n l yd i s c u s st h ep r o b l e mo ff i n d i n gar o u t i n gf o ri s p u n d e rc e r t a i nn e t w o r kp e r f o r c e f i r s tw ed e s i g nah e u r i s t i ca l g o r i t h mt of i n das i n g l e r o u t i n gt h a tm e e t st h ei s pd e m a n d i fw ec a nn o tf i n dt h es i n g l er o u t i n g ，w eu s e m u l t i p l er o u t i n g s t h e nw ed i s c u s sh o we f f e c t i v e l yt om o n i t o rt h el e a s tl i n k st oc h a n g e r o u t i n gu n d e rc o n g e s t i o n a n df i n a l l yw ed i s c u s st h ep r o b l e mo fm e r g i n gal o to ft r a f f i c m a t r i c e si n t os e v e r a lc r i t i c a l b u tw i t hl e a s tn u m b e ro ft r a f f i cm a t r i c e s k e y w o r d s ：t r a f f i ce n g i n e e r i n g ，m u l t i p l et r a f f i cm a t r i c e s ，h e u r i s t i ca l g o r i t h m ，ks h o r t e s t p a t h i i i 图目录 图目录 图1 1i n t e r n e t 全球人数增长图3 图1 2 全球各地区业务增长图4 图1 3 业务量工程功能模块。5 图1 4 流量工程整体框图6 图2 1 平均性能与最差性能测试拓扑图1 2 图2 2 链路代价函数1 2 图2 3 平均最优性能1 3 图2 4 最优最差性能1 3 图2 5 折中性能测试拓扑图1 5 图2 6 网络层次性能1 7 图2 7 链路层次性能1 7 图3 1 基于o s p f i s i s 流量工程实例2 0 图3 2o s p f i s i s 启发式算法二链路权重调整实例图2 3 图3 3o s p f i s i s 启发式算法三流程图2 4 图3 4o s p f i s i s 启发式算法三链路权重调整实例图2 5 图3 5o s p f i s i s 启发式算法测试网络拓扑图2 6 图3 - 6o s p f i s i s6 节点拓扑图2 6 图3 7o s p f i s i s9 节点拓扑图2 6 图3 8o s p f i s i s1 5 节点拓扑图2 7 图3 96 节点下o s p f i s i sk 取值与最大链路利用率关系图2 7 图3 1 09 节点下o s p f i s i sk 取值与最大链路利用率关系图2 7 图3 1 11 5 节点下o s p f i s i sk 取值与最大链路利用率关系图2 8 图3 1 29 节点下o s p f i s i s 迭代次数与性能关系图2 8 图3 1 31 5 节点下o s p f i s i s 迭代次数与性能关系图2 9 图3 1 4o s p f i s i s 平均业务量大小与性能关系图2 9 图4 1e c m p 启发式算法二链路权重调整图3 4 图4 2e c m p 启发式算法三链路权重调整图3 5 图4 3e c m p 启发式算法三流程图3 6 图4 4e c m p 等价多路径路由分流示意图3 7 图4 5e c m p 简单测试网络拓扑图3 8 图4 6e c m p6 节点拓扑图3 9 图4 7e c m p9 节点拓扑图3 9 图4 8e c m p15 节点拓扑图3 9 图4 96 节点下e c m p 网络各种算法性能比较3 9 图4 1 09 节点下e c m p 网络各种算法性能比较4 0 图4 1 11 5 节点下e c m p 网络各种算法性能比较4 0 v i i 图目录 图4 1 26 节点下e c m p 网络k 取值与最大链路利用率关系图4 l 图4 1 39 节点下e c m p 网络k 取值与最大链路利用率关系图4 l 图4 1 41 5 节点下e c m p 网络k 取值与最大链路利用率关系图4 l 图4 1 59 节点下e c m p 迭代次数与最大链路利用率关系图。4 2 图4 1 61 5 节点下e c m p 迭代次数与最大链路利用率关系图4 2 图4 1 7e c m p 平均业务量大小与性能关系图4 3 图5 1 满足性能要求的测试网络拓扑图4 6 图5 2 多路由方案切换网络拓扑图5 1 图6 1c l u s t e r 算法简单实例图5 8 图6 2 利用c l u s t e r 算法抽取多业务量矩阵示意图。5 9 图6 3 多业务量矩阵抽取算法网络拓扑图5 9 图6 4 不同抽取算法与最差性能关系图6 2 图6 5 不同抽取算法与平均最差性能关系图6 3 图6 6 不同抽取算法与最差平均性能关系图6 3 v i 筒略字表 t e o s p f i s i s e c m p t m m p l s i p a m p l i g p q o s 简略字表 t r a f f i ce n g i n e e r i n g o p e ns h o r t e s tp a t hf i r s t 流量工程，业务量工程 开放式最短路径优先 i n t e r m e d i a t es y s t e m i n t e r m e d i a t es y s t e m h 中间系统到中间系统 e q u a lc o s tm u l t i p a t h t m 伍cm a t r i x 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 i n t e r n e tp r o t o c o l 等价多路径 业务量矩阵 多协议标签交换 网际互连协议 am o d e l i n gl a n g u a g ef o rm a t h e m a t i c a l 数学规划建模语言 p r o g r a m m i n g i n t e r i o rg a t e w a yp r o t o c o l q u a l i t yo fs e r v i c e i x 内部网关协议 服务质量 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 虢翌芦盘嗍汕年易月日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：沙 第一章引言 近十年来随着i n t e m e t 的高速发展和快速普及，网络同人们之间的关系已经日 趋紧密。特别在现在的这个信息大爆炸时代，没有i n t e m e t 就没有资源，没有i n t e r n e t 就没有信息。i n t e r n e t 在人们的日常生活中已经逐渐取代了传统的日常活动，移动 办公就是一个很好的体现。由于i n t e m e t 上大多是基于d 的业务，而基于口业务 的网络特点是无法保证服务质量的，因为它只能提供尽力而为的服务，传统的话 音业务在i n t e r n e t 上无法得到保证q o s ( q u a l i t yo fs e r v i c e ) 的服务。随着多媒体 业务的日益兴起，人们希望i n t e r n e t 也能提供电信网络一样的服务质量，这对 i n t e m e t 网络也就提出了很高的要求。不仅如此，由于网民数目的急剧增加，网络 上需传输的数据日益增大，尽管现在网络设施得到很大的改善，但比起业务的增 长速度只是杯水车薪。实际上，i n t e r n e t 目前所遇到的问题不是网络资源不足，仅 仅是网络部分地方比较拥塞，而大部分资源还是剩余的。流量工程的提出就是为 了解决此类问题的，它是为了解决网络资源的合理利用，提高全网整体性能的有 效措施。由于业务在变化，不可能实时的知晓当前的业务，如何在不确定的业务 环境下优化路由就成为当前i n t e r n e t 一个很重要的问题。事实上，这种不确定性可 以用多个业务量矩阵来描述，通过对多个业务量矩阵进行路由来达到对不确定业 务量矩阵优化的目的，这也就是本文所要研究的目的。 本章简单讲述了本论文的研究背景，以及产生这些背景的事实，同时还简单介 绍了当前国内外的最新研究进展，最后为本文所做的工作和论文结构。 1 1 课题研究背景 路由优化是用来找出一组路由方案的，如找出一组路径的集合，使得数据包在 该路径中转发能优化预先定义的目标函数( 延时或链路利用率) 。业务量矩阵 t m ( t r a f f i c m a t r i x ) 规定了每对入口出口节点对之间的数据传输速率。很多方法【l 卅 均是用于计算单业务量矩阵下的最优路由。对于给定的t m ，这些工作都是考虑最 小化链路代价之和，而其中的每条链路的代价均是该链路数据率的递增凸函数。 因此，该问题可以利用优化理论来解决。对于单个t m ，解决该问题的流路由与目 的地址路由是相似的，最优代价值也是相等的。为了更有效的解决该问题，链路 代价可以被近似成分段线性函数，然后可以通过线性规划来解决。 电子科技大学硕士学位论文 理论上讲，如果能精确的知晓业务量矩阵，那么可以通过多商品流问题来求解 得到最优的路由解决方案【5 】；而对于最常用的域内路由协议o s p f i s i s ，根据确定 的业务量矩阵也能获得最接近最优解的路由方案。然而，测量和预测业务量非常 困难。对网络中所有的链路以及入i z l 出口节点采用流方式来测量几乎是不可能的， 要预测出源目节点对流汇集更是难上加难。并且，业务量会随着时间的改变而改 变，这是由于网络内部或外部原因导致的失效造成的。这些问题近年来可以通过 建模和测量工具来解决，主要是通过预测推断出业务量需求。然而，这仅仅是一 个近似的业务量需求，也不是当前的业务量需求。即使当前的业务是已知的，由 于业务的天性是动态的：一方面，我们需要路由方案对于当前的业务需求有效， 当业务改变时能调整路由方案。另一方面，我们又希望对路由方案的调整尽量小， 这是由于改变路由方案会导致服务的中断，这是由于选路的改变以及全网达到收 敛需要一定的时间。 对于规模巨大的i n t e m e t ，而其业务又时常改变，对于多业务量矩阵下的路由 优化是一个很重要的课题，主要原因如下：首先，估计t m 本身就是一个不容易 的事情，而如果网络规模比较大要想准确的预测出t m 则更困难。不用准确的估计 出t m ，对多个t m 进行的优化计算出的路由集合比估计出错误的单个t m 的优化 路由更鲁棒。其次，即使当前的t m 是已知的，但由于i n t e m e t 业务天性是动态的， 要随时跟踪最新的业务并根据最新的业务算出最优路由代价太高( 路由收敛通常 也需要花费几秒钟，在这段时间内数据包会丢失或出现乱序，频繁的路由更新会 加剧这种现象的发生) 。由于要求路由更新的速率要比业务改变的速率慢，我们很 好理解为什么要设计一套鲁棒的路由方案来适合多t m s 的需求，这样路由更新的 次数就会减少很多。 因此，好的系统工程师需要一种设计方案能鲁棒于一系列条件。也就是说要设 计一套路由方案使得该路由方案能在一系列业务需求下能获得近似最优的网络性 能。本文需要研究这种路由方案的灵敏性或鲁棒性，也就是说求解出来的路由方 案是否敏感于不确定的业务量需求。当业务量改变时，怎样的改变是在性能保证 之内允许的改变。对于特定的业务量矩阵而言，为其设计的最优路由方案去路由 偏离了原业务量矩阵后性能表现又如何呢? 在本文中所考虑的问题是在动态改变 的业务量矩阵或不确定业务量矩阵的环境中寻找一组有效的，鲁棒的路由集合。 这种动态性或不确定性可以用多个业务量矩阵来表示。 本文的工作是提出一种方法为多个t m s 找出一套使得全网最大链路利用率最 小的最优路由方案，并在此基础上进行扩充，包括特定性能下的路由方案求解， 2 第一章引言 多路由方案的最优切换，多t m s 的合并算法研究等。本论文的课题研究是基于多 业务量矩阵下t e 算法的性能研究，研究内容包括基于o s p f 1 s i s t e 算法的性能 研究，基于e c m p t e 算法的性能研究，然后通过对不同算法性能的研究，分析出 该算法中影响网络性能的因子，从而为更好的规划网络提高参考价值。同时，本 文中我们还求解了满足特定性能要求的单路由方案，多路由方案下如何最优切换， 不仅如此，我们还考虑了如何从大量的业务量矩阵中抽取出少量的关键的业务量 矩阵通过对这少量的业务量矩阵进行网络规划就能达到对所有的业务量矩阵进 行优化的目的。 由于课题背景的缘故，有必要从下面几个问题来说明课题的背景2 t 1 分别为 i p 网络中的问题，多业务量矩阵的提出原因，业务量工程咀及鲁棒路由等相关问 题。 ( 一) 现有口网络中的问题 由于i n t e m e t 的发展规模日益扩大，网络设计初期时的提供尽力而为的服务已 经越来越不能满足当今各种不同业务的需求了。传统的语音业务，当今的视频业 务，多媒体业务，电话视频等等兴起业务的发展更是推动了i n t c n a c t 需要向新的服 务转型。与此同时，网络硬件基础设施也在发生很大的改变，可利用的带宽资源 与以往已不可同日而语，路由器性能等的改善对网络的发展也起到了提速作用， i n t e r n e t 的费用得到了大幅度的降低，许多日常的业务都可以在i n t e m o t 上得以实 现，如此一来网络上数据传输量急剧增加，必然导致网络拥塞的发生。 i n t tu i n t h ew o r l d f m9 5 t 0 1 0 l 训 彳。y 一 ，z 0 9 3 甜 “3 磊”1 1 4 7 一 ，7 0 llllll ；lill ；lll 图1 - 1i n t e r a c t 全球人数增长图 3 0 电子科技大学硕士学位论文 a v e r a g ea n dp e a kt r a f f i cg r o w t hb yr e g i o n2 0 0 5 2 0 0 9 00 0 52 00 0 * 4 00 0 6 00 0 8 00 0 1 0 00 0 1 2 00 0 1 4 00 0 图1 - 2 全球各地区业务增长图 由图1 - 1 以及1 - 2 所示嘲，当前i n t e r n e t 中= 赜突出的问题是用户基数大，并且还 有巨大的增长空间，导致业务流量巨大。同时，业务的类型也呈现多样化，用户 对特定业务类型的q o s 要求也不一样。很明显网络性能会随着用户数的增大，业 务的增多而变差。如何提出合理有效的办法来解决目前i n t e r n e t 的问题就成了网络 规划者必须考虑的问题。如何充分利用网络资源获得最大的经济效益是他们的终 极目标。流量工程”】，也叫业务量工程的提出就是为了解决此类问题的，其目标是 优化网络资源，使得全网达到负载均衡的目的。 ( 二) 鲁棒路由的提出 通常情况下的业务量工程都是在考虑网络中的业务负载是己知的，可咀测量得 到的，对业务量矩阵己知的情况下有很多优化的方案。然而，在实际中，节点对 之间的业务需求是连续动态改变的。随着高带宽业务的增多( 网络视频等等) ，流 量的模式变得越来越不可预知。凼此，对于那些在业务量需求己知下的晟优路由 策略要想继续使用该策略，必须要动态的监视网络的流量，肖业务改变后及时更 新路由策略。采取这种策略一会增加操作的复杂性，二来使得网络的性能也不稳 定。因此有必要采取一种固定的路由方式，该策略不随业务的改变而改变。 实际上，很多实际运营中的删络都是采用这种策略的。这就是鲁棒路由【”的 由来。鲁棒路由在实际的网络规划中起到了很大的作用，这是由于业务是不确定 第一章引言 的，如何利用不确定的业务信息来规划设计网络就是一个问题。鲁棒路由就是解 决此类问题的。 ( 三) 多业务量矩阵的产生背景 业务量矩阵规定了每对入口出口节点对之间的数据传输速率。节点对( s ，t ) 之间 的业务定义为从8 节点发出流向t 节点的流量大小。 由于网络业务流量的动态波动性，确定出固定的业务量矩阵通常是不可能的， 而t e 算法的实施通常要依赖于特定的业务量。由于网络业务的不确定性，如何去 描述这种不确定性，就提出了多业务量矩阵这个概念，通过对某段时间内业务模 拟成多个不同的业务量矩阵来表征。通过对这多个业务量矩阵进行网络性能优化。 ( 四) 业务量工程的提出 业务量工程在r f c 文档中是这样定义的：流量工程是用于网络性能评估，网 络性能优化的工具。因此，t e 的本质是一个用于有效增强网络的服务能力而不会 导致网络拥塞的路由优化问题。为了达到上述目标，传统的t e 目标包括负载均衡 和最小化带宽消耗。流量工程包含i n t e m e t 业务的测量，特征，建模以及控制。流 量工程的主要目的是提高网络的性能，实现全网性能的最佳化。主要包括两个方 面，业务层面上和资源层面。业务量工程是一种能将业务量映射到实际物理通路 上，同时又可以自动优化网络资源以实现特定应用程序服务性能要求的、具有宏 观调节和微观控制能力的网络工程技术。它由网络拓扑信息、资源使用情况、业 务流量测量功能模块、业务量分布情况、算法模块、调度控制模块等组成，他们 的关系如图1 3 所示。 图1 3 业务量工程功能模块 5 电子科技大学硕士学位论文 其基本工作原理为：首先根据当前的网络拓扑结构获得网络的基本信息，如各 条链路的容量，可用带宽，负载程度；然后根据测量模块测量出业务的具体分布 情况，继而知晓全网的瓶颈处，通过t e 算法模块将瓶颈处的业务调度到非过载链 路上。 流量工程的主要设计目标是既要能保证网络高效，可靠运行的同时，还要对网 络资源利用与流量的性能加以优化。要有效的实现业务量工程，网络必须具有下 面一些基本属性：简单性、可靠性、可扩展性、互通性。网络的性能优化本质上 是一个控制的问题。 业务量工程中的性能指标主要体现在两个方面 9 - 1 0 】： ( 1 ) 面向应用的性能指标 该指标与某种特定的应用服务的流量特性相关。面向应用的性能指标包含了增 强业务q o s 性能的各个方面。 ( 2 ) 面向网络的性能指标 在本节中，我们根据四个不同的侧面对t e 路由方案进行归类【l i 】： 从流量优化的角度来看，t e 可以分为域内t e 和域间t e ； 从路由的实现机制上，t e 可以被划分为基于m p l s 的和基于口的； 从业务需求的可用性或操作的时间来看，t e 可以被划分成离线t e 和在线式 的t e ； 从业务的类型来看，t e 可以被划分成单播t e 和多播t e 图1 _ 4 流量工程整体框图 6 第一章引言 1 2 国内外研究进展 b e r n a r df o r t z 在文章【2 3 】中提出了传统口网络中t e 算法的一些问题，如链路 权重的设计，利用传统o s p f i s i s 协议设计t e 的好处等等，作者在该文中分析 了采用基于o s p f i s i s 的t e 算法求最小最大链路利用率是n p h a r d 问题【12 1 ，进 一步提出了一种启发式的算法用于求解单业务量矩阵下的最小最大链路利用率， 证明了该算法性能与m p l s 下性能旗鼓相当，然而作者在该文中采取的是e c m p 的分流机制，并且该算法针对的是单业务量矩阵。文献 1 3 - 1 5 】中作者针对的是多业 务量矩阵下的t e 算法求解，作者仅仅指出了m p l s 下最优解的求解，而对于 o s p f i s i s 下指出该问题是n p 完全问题，并没有给出实际的好算法。通常为了解 决t e 算法需要确定业务量矩阵，参考文献【l6 】中作者专门研究了在业务量矩阵不确 定下，通过预估业务量矩阵的方式来求解，并比较了预估的结果与真实业务量矩 阵下的结果，但即使如此，预测的值与真实的值也是有差别的。 1 7 - 1 9 】文章均是为 了解决鲁棒路由而提出的方法，而本文中的多业务量矩阵是已知确定的。这是由 于通常情况网络业务的不确定性，即使能估计出业务量矩阵也不能保证估计值万 无一失，因此采用多个业务量矩阵来表示更为准确，本文中考虑是多个己知的确 定业务量矩阵下的t e 算法。 不同于前面的工作，本文研究的重点在于多业务量矩阵下t e 算法性能的分析。 然后在此基础上扩充了多业务量矩阵下的其他相关问题。首先提出了一种启发式 的算法用于解决多业务量矩阵下的优化问题，我们优化的目标是多业务量矩阵下 的b e s tw o r s tc a s e ，具体来说是最小最大链路利用率，使得用该套权重去跑所有的 业务量矩阵得到的最差的性能是最好的，通过分析该算法中的不同因子为算法更 好的使用提供了很好的参考价值。在本文中我们分别考虑了o s p f i s i s ，e c m p 等目前使用的最广的路由协议下的路由优化问题。然后讨论了在满足特定性能下 如何求解单套路由方案，当单套路由方案不能满足要求时，如何在多套路由方案 下最有效的进行路由切换。同时，为了解决多业务量矩阵个数过大的问题，本文 还讨论了从大量的业务量矩阵中抽取出少量的关键的业务量矩阵来表征，使得只 需对这少量的业务量矩阵进行优化就能达到对所有的业务量矩阵进行优化的目 的。 7 电子科技大学硕士学位论文 1 3 本文中的工作以及论文结构 查阅和研究了现有各种单业务量矩阵下t e 算法的基本原理，然后扩展到多业 务量矩阵情景下t e 算法的求解，并发现适用于传统单业务量矩阵下的t e 算法在 处理多业务量矩阵时会出现问题，提出新的算法，并分析了新算法中影响算法性 能的因子。本文中使用了c p l e x 2 0 1 软件来建模，使用了a m p l 2 1 】语言来求解网络 最小最大链路利用率。在v s 2 0 0 5 平台下用卅语言分别编写了基于o s p f i s i s ， e c m pt e 的算法，并进行了大量的仿真。 本论文共包括七章，第一章为引言，主要介绍了一些关键的术语，业务量工程 的基本知识，课题提出的背景，国内外相关的研究进展，以及本文中所做的工作； 第二章讲述了多业务量矩阵下业务量工程算法的关键问题，即路由优化中的性能 指标，包括最差性能，平均性能以及两者之间的折中性能研究；第三章讲述了基 于o s p f i s i s 的t e 算法设计，实验仿真，结果验证以及分析结论；第四章则讲 述了基于e c m p 分流机制下的t e 算法设计，相关的实验仿真，结果验证和分析 结论；第五章主要是讨论了如何求解满足网络运营商特定性能要求的路由方案， 当满足特定性能要求的路由方案不止一套时，即出现多套路由时，如何通过检测 网络中链路状态来切换路由方案；第六章我们研究了多业务量矩阵的合并算法， 通过为多个业务量矩阵抽取出少量的关键的业务量矩阵，使得只需对这少量的业 务量矩阵进行优化就能达到对所有的业务量矩阵进行优化的目的，简化了处理大 量业务量矩阵所带来的困扰；第七章是全文的结论和总结，以及对未来工作的展 望。 8 第二章多业务量矩阵t e 算法性能指标研究 2 1 简介 第二章多业务量矩阵t e 算法性能指标研究 业务量工程中两个很重要的部分是：业务量和路由协议。这两者之间是相互关 联的，通常人们的观点是只有精确的知晓业务量才能最优的配置路由达到全网性 能最优化。而对于规模巨大的i n t e r n e t ，而其业务又时常改变，对于多业务量矩阵 下的路由优化是一个很重要的课题。 路由优化是用来找出一组路由方案的，如找出一组路径的集合，使得数据包在 该路径中转发能优化预先定义的目标函数( 延时或链路利用率) 。路由方案通常可以 分为两类：基于源目节点地址的路由( 基于流的路由) 以及基于目的地址的路由。 当数据包在网络中穿越时，流路由方法如m p l s e 2 2 - 2 5 就是基于其源地址和目的地址 的。基于目的地址的路由方法如o s p f 2 6 】转发数据包只看目的地址。很明显，目的 地址路由没有流路由能提供很好的路由控制，因为它使用的网络信息比流路由要 少。 本文考虑的问题是在动态改变的业务量矩阵或不确定业务量矩阵的环境中寻 找一套有效的，鲁棒的路由。这种动态性或不确定性可以用多个业务量矩阵来表 示。优化目标是找出一套最优的路由方案，使得在该套路由方案下能获得最好的 性能，也即对于任何一个业务量矩阵而言其最大链路利用率是最小的。 本章主要讨论了多业务量矩阵下路由优化问题中的性能指标，具体包括最坏性 能，平均性能以及两者之间的折中性能。并着重研究了折中性能的一些性质。在 本章中主要考虑的是基于流的折中性能研究。 2 2 多业务量矩阵t e 算法中性能指标研究 本章主要考虑的是多业务量矩阵t e 算法中的性能指标，具体为最差性能，平 均性能以及两者之间的折中性能。首先分别给出最差性能，平均性能的数学描述， 然后提出了两者之间的性能折中，并通过实例说明了对于一组给定的业务量矩阵， 不同的路由方案提供的平均性能与最差性能之间的折中也不同。并在网络层次和 9 电子科技大学硕十学位论文 链路层次上定量化路由配置性能。本文采用了一种简单的指标平均性能和最差性 能加权和来控制两者之间的折中。 对于链路层次，本文使用了链路代价来定量化平均性能，使用最差链路代价性 能来定量化最差性能。对于网络层次，使用网络代价来定量化平均性能，而用最 差网络代价来定量化最差性能。最后本文分析了不同性能指标应用的环境，并设 定本文将要考虑的性能均为最差性能。 2 2 1 控制变量 网络拓扑：网络g = ( y ，e ) 是由两部分构成，节点集合v 和有向链路集合e 构 成。节点集合v 中的节点用1 2 i v i 来表示。链路集合中的有向链路表示成 ( 后，) v 2 。 链路容量c = c u ) ，其中 0 表示链路( 后，) v 2 的链路容量。 业务量矩阵r = r i ，垦，咒) 表示一组n 个业务量矩阵，每个业务量矩阵都有 一个正的权值w = w l ，w 2 ，) ，w y = 1 。对于业务量矩阵髟= b ( f ，纠， y f ，y ，y l ，2 ，n ) ，r 。( f ，j ) 表示节点对( f ，) 之间的业务流大小。 r a t i ov a r i a b l e s ：b = 民( f ，) ) ，i ，j v ，( 尼，) e ，吼( f ，j ) 0 表示节点对( f ，) 在 链路( 后，) 上传输的业务大小与节点对“，j ) 要传送的业务流大小的比值。r a t i o v a r i a b l e s 集合b 应该满足如下的流量守恒定律： f1 ，k = 吃。( f ，) 一吃( f ，j f ) - - t - 1 ，k = f ( 2 - 1 ) 。 lo ，其他 链路权重：形= w 材) ， 0 ，表示链路( 后，) 上的权重。 链路数