（通信与信息系统专业论文）基于mpls的流量工程实现算法研究.pdf

东北大学硕士学位论文 摘要 基于m p l s 的流量工程实现算法研究 摘要 随着互联网用户和业务的爆炸性增长，网络资源不足及网络拥塞问题 日趋明显，而各种新业务的出现又对网络的服务质量提出了新的要求。由 于网络设备的升级速度远远赶不上信息的增长速度，而且传统i p 网络存在 的固有缺点造成许多网络链路和网络设备没有得到充分利用，因此网络传 输过程中出现大量拥塞。如何提高网络资源的利用率，提高网络的整体性 能是当前网络发展中急需解决的问题，而流量工程正是为解决这一系列问 题两产生的。 进行流量工程研究主要有两方面的原因：一是为更有效地利用网络设 备以得到明显的经济效益；二是随着多协议标记交换( m p l s ) 技术的 n 现，使得在传统无连接i p 网络中提供面向连接的服务成为可能。然而，新 的网络通信技术的出现和发展迫切需要以一种新的技术取代基于覆盖模 型的流量工程技术，并克服其固有的管理复杂、难以扩展等局限。基于 m p l s 技术的流量工程是当前为业界所普遍推崇的下一代流量工程主流技 术。在流量工程的研究中，m p l s 所提供的最大的优点是能够将l p 分组路 由到一条标记交换路径( l s p ) 上，一对源一一目的地址之间可以建立多 条不同的l s p ，每条l s p 的路出可以独立指定。 本文研究目标是提出基于m p l s 的流量工程解决方案，研究目标就是 最大化地提高网络资源的利用率，或实现满足某些特定条件约束下流量的 最优负载平衡。本文通过在o s p f 算法上加入约束提出一种新的c s p f 路 由算法，以改进m p l s 网络中流量工程的性能。算法考虑到在执行和配需 过程中应具有最小风险，而尽可能地利用了现有技术和协议的简单扩展和 组合实现高效、可靠的流量工程。本文还提出了一种新的流量迁移策略， 通过该策略进行m p l s 网络l s p 的配置，再根据提出的算法进行选路，可 以在不扩大网络规模的情况下，提供更大的网络吞吐量，提高网络利用率， 满足各种新业务的q o s 需求。经分柝和实验仿真验证，该策略及算法特别 适合网络中业务流多为粗壮型的情况。而随着网络规模的扩大，越来越多 的新业务提出了严格的q o s 、高带宽的要求，该算法正适应了这一现实的 演进。可以预见，在业务流大多为粗壮型的未来，本文提出方案的优越性 将发挥到极致。 一u 一 东北大学硕士学位论文 摘要 关键词多协议标记交换流量工程限制路由标记交换协议显示路由标 记交换路径限制最短路径优先 东北大学硕士学位论文 a l g o r i t h mr e s e a r c ho ni m p l e m e n to ft r a f f i c e n g i n e e r i n gb a s e do nm p l s a b s t r a c t w i t ht h ee x p l o r i n gi n c r e a s eo ft h eu s e r sa n dt r a f f i co ni n t e r n e t ，t h e p r o b l e m o fn e t w o r kc o n g e s t i o na n di n s u f f i c i e n c yo fa v a i l a b l en e t w o r k r e s o u r c eh a sb e c o m em o r ea n dm o r eo b v i o u s ，a tt h es a m et i m e ，m a n yn e w a p p l i c a t i o n sr e q u i r ed i f f e r e n tq o s t h es p e e do fi n f o r m a t i o ne x p a n s i o ni s f a r b e y o n dt h a to fu p g r a d i n gn e t w o r kf a c i l i t i e s d u et o t h eg i v e nd r a w b a c k so f t h et r a d i t i o n a li pn e t w o r k m a n yn e t w o r k1 i n k sa n df a c i l i t i e sh a v en o tb e e n f u l l yu t i l i z e d a sar e s u l t ，i nt h ec o u r s eo fn e t w o r kt r a n s m i s s i o nb l o c ka r i s e s t h ep r o b l e mt h a tt r a f f i ce n g i n e e r i n gw i l ls o l v e ，i st oi m p r o v et h eu t i l i z a t i o no f n e t w o r kr e s o u r c e sa n di t sp e r f o r m a n c e t h e r ea r et w om a i nr e a s o n sw h yw ed or e s e a r c ho nt r a m ce n g i n e e r i n g o n o n eh a n d ，i ti sp o s s i b l et oo b t a i ne v i d e n te c o n o m i cb e n e f i t sb ye f f e c t i v e l y u t i l i z i n gn e t w o r kf a c i l i t i e s o nt h eo t h e r ，t h ee m e r g e n c eo fm u l t i - p r o t o c a l l a b e ls w i t c h i n g ( m p l s ) m a k e si tp o s s i b l et op r o v i d ec o n n e c t i o n o r i e n t e d s e r v i c ei nt r a d i t i o n a li pc o n n e c t i o n l e s sn e t w o r k d h et on e wn e t w o r k c o m m u n i c a t i o nt e c h n o l o g y sa p p e a r i n ga n dd e v e l o p i n g ，i ti se x i g e n tf o ri s p s t os e e kak i n do fn e wt e c h n o l o g yt or e p l a c ei t sc u r r e n tf u n c t i o n sb u i l t e do ni p o v e ra t mw i t h o u ti t si n h e r e n tc o m p l e x i t yt oa d m i n i s t r a t ea n de x t e n d m p l s i st h em o s tp r o m i s i n gt e c h n o l o g yt h a ti sc o m m e n d e db yt h ei n d u s t r y t h em o s t i m p o r t a n ta d v a n t a g e t h a tm p l sc a ns u p p l yi nt h er e s e a r c ho nt r a f f i c e n g i n e e r i n gi st h a ti tc a nr o u t ei pp a c k e t st oa nl s p ( l a b e ls w i t c h e dp a t h s ) s e v e r a ll s p sm a yb ee s t a b l i s h e db e t w e e nap a i ro fs o u r c e d e s t i n a t i o nn o d e s t h er o u t eo fe a c hl s pc a nb ei n d e p e n d e n t l ya s s i g n e d t h er e s e a r c ho b je c t i v eo ft h ep a p e ri st o p r o p o s es o l u t i o n st o t r a f f i c e n g i n e e r i n go v e rm 。p l sa n dt r a d i t i o n a li p t h ea i m sa r et om a x i m i z et h e u 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 ，o rt or e a c ht h eo b i e c t i v e so fo p t i m a l d i s t r i b u t i o nt r a f f i ci nc o n s t r a i n i n gc o n d i t i o n s b ya d d i n gc o n s t r a i n tc o n d i t i o n s o no s p f ，t h e p a p e rp r e s e n t san e w k i n do fc s p fr o u t i n ga l g o r i t h mt oi m p r o v e t h ep e r f o r m a n c eo ft r a f f i ce n g i n e e r i n gi nm p l sn e t w o r k c o n s i d e r i n gt o m i n i m i z i n gt h er i s ki nc o n f i g u r a t i o na n de x e c u t i o n ，t h ea l g o r i t h mt r y st om a k e f u l lu s eo fc u r r e n tt e c h n o l o g i e sa n dp r o t o c o lt oe x t e n da n dc o m b i n e t h e n ，a 东北大学硕士学位论文 a b s t r a c t n e wt r a f f i ct r a n s f e r s t r a t e g y i s p r e s e n t e d c o n f i g u r a t i o no ft h el s pa n r o u t i n gi nm p l sn e t w o r ki se x e c u t e db yt h es t r a t e g ya n da l g o r i t h mp r e s e n t e ( t h u su n d e ro r i g i n a ln e t w o r ks c a l e ，m o r en e t w o r kt h r o u g h p u ta n dh i g h t n e t w o r ku t i l i z a t i o ni sa v a i l a b l ea n dt h eq o so fa l lk i n d so fn e w a p p l i c a t i o n sj m e t w i t ht h ea n a l y s i sa n dv a l i d a t i o nb yt h es i m u l a t i o n ，t h en e ws t r a t e g ya n a l g o r i t h mh a se x c e l l e n tp e r f o r m a n c ei nt h ec o n d i t i o nt h a tm o s to ft r a f f i cf l o i nt h en e t w o r ka r et h i c k w i t ht h ee x t e n s i o no fn e t w o r k m o r ea n dm o r en e l a p p l i c a t i o n sp r e s e n ts t r i c tr e q u i r e m e n tf o rq o sa n db a n d w i d t h ，w h i c ht h a l g o r i t h mw i l lm e e t i nt h ef u t u r en e t w o r kw h e r em o s to ft r a f f i cf l o w sw i l lb t h i c k ，t h es c h e m ep r e s e n t e db yt h i sp a p e rw i l lt h o r o u g h l ys h o wi t sa d v a n t a g e , , k e yw o r d sm p l s ，t r a f f i ce n g i n e e r i n g ，c r l d p , e r - l s p , c s p f v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文 中取得的研究成果除加以标注和致谢的地方外，不包含其他人已 经发表或撰写过的研究成果，也不包括本人为获得其他学位而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示谢意。 学位论文作者签名：7 畅赫k 日期： 2 d d 5 牟旧 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使 用学位论文的规定：即学校有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权东北 大学可以将学位论文的全部或部分内容编入有关数据库进行检 索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不 同意。) 学位论文作者签名：导师签名： 签字目期： 签字日期： 东北大学硕士学位论文 第一聿引言 第一章引言 1 1i p 技术为核心的下一代网络 通信技术的革新和网络技术的飞速发展，极大地满足了人类沟通的需 要。目前信息产业已成为世界科技领域中最有活力、发展最快的高新技术， 成为很多国家经济发展的支柱产业，它改变着人类传统的生活方式和生活 质霆。当前世界各国都在大力发展网络技术、通信技术，以满足人民的生 活需要；构筑优秀的网络，将其与传统产业相结合，能有效提高本国的经 济竞争和军事保障能力，是各个国家、运营商、企业、校园用户的共同愿 望。从技术角度看，i p 技术简单、灵活，可建立在各种不同的物理网络技 术之上；在i p 技术为基础的网络上，实现各种应用业务简单、高效。目前 看来，网络发展的趋势相对明朗，实践也证明，无论是传统的电信运行商， 还是新兴的网络运营商，它们在新建或改造现有网络时，大多选择了构建 l p 技术为核心的可营运的多业务网络。将多种网络如电信网络、计算机网 络、广播电视网络融合，构建以i p 技术为核心的综合业务网络已在很多地 方丌展。在我国，数据网络与电信网络的融合过程正在迅速推进。多家运 营商中国电信、联通、网通、移动等公司都开展了利用i p 网络提供传统语 音通信的业务。 1 2 流量工程在下一代网络中的作用 传统的l p 技术采用“尽力而为”传送( b e s te f f o r t ) 机制，对i p 数据 分组依据目的地址与源地址简单地进行逐跳转发，不能针对不同的业务需 求提供不同的转发能力，尤其是在网络发生拥塞的时候。 随着网络技术的发展与融合，在i p 网络上提供数据、语音、视频流等 多种不同特性应用的需求越来越大。在网络资源非常充足时，传统的l p 技术尚能使得不同类型的业务需求基本能得到满足。但由于分组流量传送 的突发性，即使是美国这样的发达国家建设的带宽资源丰富的网络，在局 部范围、特定时间或特定条件下也会出现拥塞的现象。当网络中的部分节 点出现拥塞时，优先级高的重要业务的i p 分组必须得到优先传输，并能按 照用户与运营商之间的承诺的标准提供较好的服务质量保证。这是传统的 i p 技术难以解决的问题1 1 j 。 传统i p 网络中的路由协议通常采用纯粹的基于网络拓扑的选路算法， 在计算路径时不考虑网络上各节点和链路的资源利用情况；i p 数据分组依 东北大学硕士学位论文 第一章引言 据路由算法选中的最短路径进行转发。这就可能导致局部网络中部分较优 的链路资源被过度使用，而部分链路资源却被闲置浪费，使得i p 网络资源 的利用率低下。 网络规模、网络资源利用率和提供给用户的服务质量是构建下代可 运营i p 网络的关键。网络运营商建设网络需要巨大的投资，作为商业实体， 需要在收益和投入中取得平衡。因此在建设网络的喇候，必须充分考虑网 络的实际需求、运行效率与高收益。流量工程( t r a f f i ce n g i n e e r i n g ，简称 t e ) 正是在这种迫切需要的情况下应运而生的一种新型网络技术。流量工 程的主要任务是通过规划流量使之能够在现有的网络上有效地传输，其核 心是对流量进行转移，即将阻塞链路上的流量转移到那些尚未被充分利用 的链路上去，从而达到充分利用网络资源的目的。目前全球的电信运营商 对t e 技术展开了大量的研究，据统计，如果能够通过技术手段成功地实 现网络流量的宏观控制与调节，则仅仅使用现有网络总容量的6 0 就能够 以现有服务标准来提供现在所需的所有服务1 2 j 。这便意味着现有的网络容 量可以在不添加任何硬件设施的前提下提供近一倍的流量支持，这种技术 的研究必将为我国的国民经济提供新的增长点，从而带来巨大的经济效益 和社会效益。 流量工程是最大化地提高网络资源利用率的技术和方法。它的研究目 标就是尽可能提供最优网络性能。除了这些性能目标外，流量工程常用于 实现网络管理策略的目的。对于一个固定的网络拓扑，流量工程的目标是 使网络能够容纳更大的网络容量，或是在同样的流量水平下，使网络在链 路延迟、包丢失率、或抖动等指标方面有全面和较好的性能。流量工程也 用于满足约束的目标。例如，出于策略的原因某些数据流被限制于特定 的网络拓扑子集中，在这种情况下，流量工程的目标将会是如何组合约束 以满足需求。 1 3 论文组织结构 本文内容安排如下： 第一章引言。介绍课题研究的背景，包括新业务的需求和网络的发展 方向，以及应运而生的流量工程在下一代网络中存在的必要性。 第二章流量工程系统模型。首先介绍了流量工程产生的背景以及需要 达到的目标；其次对于流量工程发展的历史和现状进行了概述( 从基于度 量的流量工程到基于覆盖模型的流量工程) ；最后，对流量工程的体系结 构从几个不同的方面进行了系统的分析与阐述全局性地介绍了流量工程 的系统模型，并从局部各个方面介绍了流量工程的组成元素。 一2 - - 东北走举硕士学位论文 第一章引言 据路由算法选中的最短路径进行转发。这就可能导致局部网络中部分较优 的链路资源被过度使用，而部分链路资源却被闲鬣浪费，使得j p 网络资源 的利用率低下。 网络规模、网络资源利用率和提供给用户的服务质量是构建下一代可 运营i p 网络的关键。网络运营商建设网络需要巨大的投资，作为商业实体， 需要在收益和投入中取得平衡。因此在建设网络的时候，必须充分考虑网 络的实际需求、运行效率与高收益。流量工程( t r a f f i c e n g i n e e r i n g ，简称 t e ) 正是在这种迫切需要的情况下应运而生的一种新型网络技术。流量工 程的主要任务是通过规划流量使之能够在现有的网络上有效地传输其核 心是对流量进行转移，即将阻塞链路上的流量转移到那些尚未被充分利用 的链路上去，从而达到充分利用网络资源的目的。目前垒球的电信运营商 对t e 技术展开了火量的研究据统计，如果能够通过技术手段成功地实 现网络流量的宏观控制与调节，则仅仅使用现有网络总容量的6 0 就能够 以现有服务标准柬提供现在所需的所有服务”i 。遮便意味着现有的网络容 量可以在不添加任何硬件设施的前提下提供近一倍的流量支持，这种技术 的研究必将为我国的国民经济提供新的增长点，从而带来巨大的经济效益 和社会效益。 流量工程是最大化地提高网络资源利用率的技术和方法。它的珂f 究目 标就是尽可能提供最优网络性能。除了这些性能目标外，流量工程常用于 实现网络管理策略的目的。对于一个固定的网络拓扑，流量工程的目标是 使网络能够容纳更大的网络容量，或是在同样的流量水平下，使网络在链 路延迟、包丢失率、或抖动等指标方面有全面和较好的性能。流量工程也 用于满足约束的目标。例如，出于策略的原因，某些数据流被限制于特定 的网络拓扑子集中，在这种情况下，流量工程的目标将会是如何组合约束 以满足需求。 1 3 论文组织结构 本文内容安排如f ， 第一章引言。介绍课题研究的背景，包括新业务的需求和网络的发展 方向，以及应运而生的流量工程在下一代网络中存在的必要性。 第二章流量工程系统模型。首先介绍了流量工程产生的背景以及需要 达到的目标；其次对于流量工程发展的历史和现状进行了概述( 从基于度 量的流量工程到基于覆盖模型的流量工程) ；最后对流量工程韵体系结 构从几个不同的方面进行了系统的分析与阐述，全局性地介绍了流量工程 的系统模型并从局部各个方面介绍了流量工程的组成元素。 的系统模型，并从局部各个方面介绍了流量工程的组成元素 垒苎查兰塑主芏垒垒查 苎= 主! ! 童 第三章m p l s 技术框架分析。阐述了m p l s 技术特点及其工作过程、 系统框架及组成、核心技术以及主要应用。 第四章m p l s 流量工程实现机制。具体阐述了在m p l s 网络中如何实 现流量工程，m p l s 拥有哪些关键技术在实现流量工程中能够体现出巨大 的优势，流量工程与m p l s 的融合所需的条件以及实现方法。 第五章m p l s 流量工程算法研究。该部分是全文的重点所在，主要描 述了对于如何在m p l s 网络中实现流量工程问题所提出的具体策略和算 法，并对仿真结果进行分析，验证了这种新的流量工程路由的策略以及算 法的性能。 最后结束语部分对整篇论文的内容进行了系统阐述，在说明m p l s 网 络中实现流量工程的必要性和可行性之后，从两个方面总结了沦文所提出 的新的路出算法和新的路由策略在m p l s 流量工程中的应用过程中所解决 的问题，并通过仿真得出新路由策略及算法可行性和高效性结论。 东北大学硕士学位论文 第二章流量工程系统模型 第二章流量工程系统模型 2 1 流量工程产生背景及目标 2 1 1 流量工程产生背景 随着i n t e r n e t 的迅速发展，i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 面临着日益 激烈的商业竞争，他们必须向用户提供像电话一样可靠的服务：同时，还 存在着网络中提供不同服务的需求，这样i s p 就可以通过提供具有竞争力 的服务使他们获得最大的利润。对i s p 来说，商务效率和代价受如何能有 效利用基础设施，特别是可用带宽的影响。更加有效的使用带宽资源就意 味着i s p 能减少运营的整体费用，帮助i s p 获得超过其他竞争者的优势。 为了在网络中提供这样的能力，必须增强当前i p 网络中的基本流量转发机 制，也就是要实施流量工程【3 l 。将业务流合理映射到物理链路上的任务称 为流量工程，流量工程是一个强有力的工具，通过它可以平衡网络中不同 链路、路由器和交换机之间的业务负载，使所有这些网络设备既不会被过 度使用，也不会未被充分使用。这样就可以有效利用整个网络的资源。随 着信息社会的进一步发展，在未来的主干网络中，流量工程将成为路由结 构中的一个重要组成部分。 2 0 0 0 年9 月，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 r n e t 上实施流量工程的框架和目标。a t m ( a s y n c h r o n o u s t r a n s f e rm o d e ) 网络可以支持综合服务，并且在网络工程设计方面具有高 度的灵活性，提供流量管理和q o s ( q u a l i t yo fs e r v i c e ) 保证能力，支持 v p n ( v i r t u a lp r i v a t en e t w o r k s ) 和多重业务类型。但由于a t m 信令过于 复杂，给广泛应用带来了不利。而i p 技术的简单、高效使其得以广泛应用 并迅速成为网络的主导技术。其灵活的路由体系结构，面向无连接的“尽 力而为”的分组传送方式，特别适合于非实时数据信息的传输。但i p 技术 对流量的管理能力很弱，无法提供q o s 服务( 时延、带宽等) 保证；无法 满足语音、视频图像等实时信息的传输要求。因此，在实现流量工程的初 期，主要是利用a t m 的流量管理能力，在i n t e r n e t 网络中使用基于a t m 技术的覆盖模型i po v e ra t m 实现流量工程。随着覆盖模型各种局限性的 暴露及m p l s ( 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 实现流量工程在网络的扩展性、网络的管理等多个方面具有更好的可操作 性。 东北大学硕士学位论文 第二章流量工程系统模型 2 1 2 流量工程目标 当考虑流量工程的性能目标时【4 】，可以将流量分成两类：面向应用的性 能对象与面向网络的性能对象。面向应用的性能对象又可称之为面向业务 流的性能对象；面向网络的性能对象可称之为面向资源的性能对象。 2 1 2 1 面向业务流对象的性能目标 这是一种与每种特定应用服务流的流量特性相关的对象，它与o o s 相关，并试图从端到端的分组发送延迟、分组延迟抖动、服务响应时 间等几方面改善网络性能。负荷平衡是流量工程的主要功能之一。一 般说来，因特网的内部网关( i g p ) 路由只能确定一条到给定目的地的 路由，可以想象，当有多个数据流集中到这条路由上进行传输时，必 然会发生拥塞，这导致上面所述几项指标的等级下降，延迟敏感型应 用是无法容忍拥塞的。但是，如果能将去往同一出口的流量进行分割， 并放入不同的路径上进行传输，这就会减少拥塞的发生，从而满足分 组的传输性能要求。 面向业务流对象的性能目标包括了业务流q o s 的增强。对“尽力丽 为”的i n t e r n e t 服务模型来说，面向业务流的关键性能目标包括：分组 丢失的最小化、延迟最小化、吞吐量最大化及增强服务级的协定。在 单一的“尽力而为”服务类型下，分组丢失的最小化是面向业务流性 能对象的最重要目标之一。面向业务流的性能统计，如峰值、峰值分 组延迟、延迟抖动、丢失率和最大分组传输延迟等可能会对i n t e r n e t 差分服务十分有用。 i n t e r n e t 发展初期，其应用主要局限于数据通信领域，相应地，i p 网络的网络结构、支持的协议以及对服务质量的要求都是按照数据通 信的要求来设计的。而数据通信的特点是对时延或时延抖动的要求比 较宽松，对数据传输的可靠性则有严格的要求。i p 协议是无连接协议， i p 网络基于数据报传输模式，因此传统i p 网络中没有“服务质量”的 概念，i p 网络不能保证足够的吞吐量和符合要求的传送时延，网络只 是尽最大努力来满足客户的需要。从i s p 的角度来看，企业与商业用 户是十分重要的收益来源，然丽由于企业网与金融商务网络对服务质 量的苛刻要求，目前这些网络一般都还处于独立专用状态。如果能够 提供i p 网络服务质量，i p 网络将可以吸引大量的具有较高服务质量要 求的用户与业务。因此，未来的i n t e r n e t 网络需要能够提供多种不同服 务以支持多种不同的应用，特别是适应实时多媒体业务，如何实现这 种能够提供多种服务的集成服务一直是国内外研究的热点。解决l p 网 东北大学硕士学位论文 第二章流量工程系统模型 上存在的服务质量问题可通过下列两方面：是o o s 的直接实现；二 是流量工程。流量工程可以说是一种间接实现q o s 的技术。它将通过 资源的合理配置，对路由过程进行有效控制，最终使得网络资源能够 得到最优的利用，在网络的运行中使得标记交换路径能够自动地绕开 网络故障、网络拥塞与网络瓶颈。当网络资源得到了充分的利用时， 自然而然地，网络的各项o o s 指标也将随之大大改善。 2 1 2 2 面向网络资源对象的性能目标 这是一个与网络资源相关的对象。它试图改善网络资源利用率、网 络吞吐量等性能。预向资源对象的性能目标包括了资源使用优化的各 个方面。有效的网络资源管理是实现面向资源优化使用目标的手段。 特别是要确保网络各组成部分的均衡使用，不要有些部分过度使用而 。拥塞，而与此同时另一些部分却闲置不用。带宽是当今网络最重要的 资源之一，因此，流量工程的一个中心功能就是有效管理和使用带宽。 拥塞的最小化是面向业务流和面向资源对象流量工程的主要性能目 标。拥塞的发生有两种情况：一是当网络资源不充足或不能满足负荷 的需求时；二是业务流映射到实际物理通路时没能有效调度，造成部 分网络资源过使用，而另一些则欠使用。 对于前者造成的拥塞可以作如下解决：( 1 ) 扩展网络容量；( 2 ) 应 用分类拥塞控制算法；( 3 ) 上述两种方法同时使用。典型的拥塞控制 技术有：速率限制、窗口流控、路由器队列管理、基于控制的调度等。 对于后者则需要流量工程来解决。一般来说，由于网络负荷的不平 衡导致的拥塞可以通过流量调度来减少。其策略思想就是通过有效的 资源调配，最小化最大拥塞的发生和最小化最大资源的使用。当棚塞 最小化后，分组丢失会随之减小，传输延迟下降，网络吞吐量增加， 对每个端用户的服务质量也随之提高。 很显然，负荷均衡是重要的网络性能优化策略，不过，流显工程能 力的弹性应足够，这样网络管理员可以应用其他一些方法来成功实现 网络管理，提供有效的增值服务。 如前所述，流量工程的目标1 5 i 是避免拥塞问题以及由此引起的 o o s 服务等级下降闯题：另外它还要实现网络工程自动化。从网络流 量的观点来看，流量工程的功能可以看作是网络中业务流量分布的优 化。 现有的因特网i g p s 簇并没有提供流量工程的能力，因此，很难针 对网络的性能闯题实现有效的策略。事实上，基于最短路径算法的i g p , , 是造成a s 网络中拥塞的主要原因。最短路径算法是简单的基于附加值 东北大学顾士学位论文 第二章流量工程系统模型 的优化算法。这些协议都是拓扑驱动的，因此它们都不考虑网络可用 的带宽和流量的特征。当出现以下情况时，就会发生拥塞： 多个业务流的最短路径汇聚到一条特定的链路或路由器接口 上： 多条业务流的最短路径通过某条带宽不足以支持该业务的链路 或接口时。 在这两种情况下，即使存在着拥有充足带宽的其他路径，拥塞仍然 会发生。这种因资源未能合理分配而造成的拥塞问题正是流量工程所 要解决的。目前，解决i g p 协议簇上述缺陷的一般方式是使用覆盖模 型技术，例如i po v e ra t m ，i po v e tf r 等。覆盖模型在网络的物理拓 扑结构上提供了一个自由的虚拟拓扑结构，从而扩展了网络设计的空 间。这种虚拟拓扑结构由虚电路构成，在i g p 路由协议看来【酊，这些 虚电路就相当于过去的物理链路。覆盖模型还提供了许多其他重要的 功能来支持流量与资源控制，依靠这些功能可以实现许多流量工程策 略。关于覆盖模型将会在后面的2 2 2 节中具体介绍。 2 2 流量工程技术发展现状 2 2 1 基于度量的流量工程 在早期基于路由器的核心网络中，流量工程是通过简单地使用路出量 度值来实现的。因为那时无论从路由器数量、链路数及业务流量来讲， i n t o r n e t 骨干网都是非常小的。所以，基于度量的控制在那时是足以胜任的。 同时，在互联网普及之前，拓扑层次也强制业务通过网络中较为确定的j ! 径及事件，不会产生临时的“热点”。 图2 1 描述了基于开销的流量工程是如何运行的。假设子网a 发送了 大量业务给子网c 和子网d 。对于如图2 1 所示的开销，链路1 和链路2 可能发生阻塞，因为子网a 到子网c 与子网a 到予网d 的业务都将流过 这些链路。如果将链路4 的开销值设为“2 ”，子网a 到子网d 的流量将转 移至链路4 ，但子网a 到子网c 的业务将继续留在链路1 和链路2 上。这 样就在不中断网络中任何处理的情况下修正了“热点”。 一直到2 0 世纪9 0 年代中期，基于开销的流量控制都提供了充足的流 量工程能力。但从那以后，i s p 的网络规模越来越大，他们无法再通过使 用基于开销的流量控制和基于传统路由器的核心网络来继续发展自己的 网络。在一个实际的运营商网络里，用传统的简单向最方法很难很好地调 整整个网络的运行情况：而且。路由器硬件的发展已经不能满足i s p 发展 苎苎苎登翌生羔：竺坚 苎三主堕量三堡墨竺堡型 的需要了。它既不能提供更高速率端口，也不能提供更快的包转发率。 网络a 网络b 路由器a 链路4 路由器d 路由器b 链路2 e t r i c = 1 路由器c 网络d m e t r i c = 1 网络c 图2 1 基于度最的流最： 程 f i g 2 1t r a f f i ce n g i n e e r i n gb a s e do nm e t r i c 近年来，随着i p 网络规模的扩大，传统的路由核心弼在为流量工程提 供可扩展性支持上的局限性越来越明显，这主要体现在以下几个方面： ( 1 ) 由于传统路由器的汇集带宽和包处理能力有定的局限性，因此， 传统的、基于软件的路由器在高负荷的情况下可能成为潜在的瓶颈。 ( 2 ) 基于量度处理的流量工程不具有可扩展性。当i s p 网络变得具有 更多的链接时( 即更大、更密集的结网和更多的冗余) ，很难保证对网络 某个部分量度的调整而不致在网络的其他部分引起问题。基于量度处理的 流量工程对于后来出现的复杂问题提供的是种跟踪纠错的解决方式，而 不是一种科学的解决方案。 ( 3 ) i g p 计算是通过拓扑驱动的，它只基于一个简单附加量度，如跳 数或某个管理值。i g p 并不发布类似于带宽可用性和业务特征等信息。这 就意味着，当i g p 计算其转发表时并不考虑网络上的业务负载。结果，业 务不能在网络连接中平均分配，导致昂贵的资源未能得到有效使用。这种 情况在稀疏连接的网络中也许能满足客户的需求，但对于一些复杂连接网 络，对业务所使用的链路进行控制以确保链路的负荷均衡就变得非常必要 了。 传统的i p 路由未能解决流量工程问题的主要原因是，任何一种解决 这个问题的方案都必须建立这样的路由：就某个衡量尺度( 比如管理距离) 而言，这个路由不仅是最优的，而且这个路由还考虑到了各链路上的可用 带宽。传统的i p 路由提供前者但不能提供后者。 东北大学硕士学位论文 第二章流量工程系统模型 2 2 2 基于覆盖模型的流量工程 到了2 0 世纪9 0 年代中期，i n t e r n e t 业务量的不断增长要求i s p 主干网 络能够支持高于t 3 ( 4 5 m b p s ) 的速率【8 】。这时，出现了交换机和路由器 上o c - 3 ( 1 5 5 m b p s ) 速率的a t m 接口。为了获得所需的速率，i s p 被迫 重新设计他们的网络，以便能够使用由交换机( a t m 和帧中继) 核心网提 供的更高速率。一些i s p 将他们的网络从t 3 点到点连接变为在网络边缘 使用带有o c 一3 速率a t m 接口的路山器，而在网络核心部分使用o c 3 速 率的a t m 交换机的网络结构。之后，a t m 交换机之间的连接速率又升级 到o c 一1 2 ( 6 2 2 m b p s ) 。另一些i s p 歼始在他们的t 3 帧中继网络中增加节 点。当他们开始从帧中继转移至a t m 时，他们在网络边缘使用o c 3 链路， 但不久便在核心部分配置了o c 1 2 速率的交换机间的连接。图2 2 所示为 2 0 世纪9 0 年代中期典型的大型i s p 核心网络拓扑结构。 物理拓扑 图2 2i s p 核心网络拓扑结构 f i g 2 。2c o r en e t w o r kt o p o l o g yo fi s p 谬坦杯扑 2 2 2 1i p 覆盖型网络的运行 当i p 运行在a t m 网络上对，路由器环绕在a t m 网络的边缘。每个路 由器通过一系列由a t m 物理拓扑配置的永久虚电路( p v c ) 与其他路由 器通信。p v c 就像是逻辑电路一样工作，为边缘路由器提供连接。路出器 并不能直接访问a t m 结构中p v c 的具体物理拓扑信息，路由器只是了解 特定的p v c 就像出现在两个路由器之间简单的点到点电路对于大型i s p ， a t m 核心网由i s p 完全拥有，并用于支持i n t e r n e t 骨干网业务。这种核心 网的基础结构和其他专用数据业务完全分离。因为网络由i s p 完全拥有并 东北尢学硕士学位论文 第二章流量工程系统模型 专门用于i p 业务，所有业务通过a t m 核心时使用不确定比特率( u b r ) 。 这时的a t m 服务等级是没有策略的，即没有业务整形、峰值信元率、维 持信元率。i s p 只是简单地把a t m 交换结构作为一个高速传输系统，而不 依赖a t m 的业务和拥塞控制机制。对于i s p ，没有什么理由需要他们使用 这些先进的“特性”，因为每个i s p 都拥有自己的骨干网，他们不需要对 自己加以限制。p v c 覆盖的物理路径通常通过离线配置计算获得，它使用 基于需求的方式：当拥塞发生，新增一一条干线或配置一个新的p o p 。一些 a t m 交换机厂商在考虑流量工程时，会使用些专有的技术对p v c 进行 路由，但这些方案都不成熟，i s p 经常需要进行完整的离线状态路径计算 以达到预期的结果。p v c 路径和特性通过使用基于链路容薰和历史业务参 数配置而对其进行整体优化。离线状态配置的使用也可以帮助设定一组备 用p v c ，以便在故障条件下准备做出反应。最后，在完成p v c 结网的整 体优化计算后，配置将被下载到路由器和a t m 交换机以提供单个或两个 全闭合结网的逻辑拓扑。 当a t m 的p v c 被映射到路宙器的子端口对，分离的a t m 网络和i p 网络相遇。路由器予端口与a t m 网的p v c 互相协调，然后路由协议在子 端口上与i p 报头( 路由) 协调工作。实际上，离线配置的使用生成了路山 器和交换机的配置，确保p v c 号码的一致性，并且进行了适当的映射。最 后，通过p v c 中运行i g p 以建立对等关系并交换路由信息，使a t m 的p v c 集成到i p 网中去。对任何一对路由器间，主p v c 的i g p 度量配置要比备 用p v c 配置更为首选，这便保证了只有在主p v c 无效时才会使用备用 p v c 。同时，如果主p v c 在故障后重新恢复，业务也将从备用p v c 切换 回到主p v c 。 2 2 2 2i po v e r a t m 模型的局限性 在过去几年中，a t m 交换机扩大了i s p 的市场份额并增加了利润。9 0 年代中期，a t m 交换机因其独一无二的高速接口、确定的性能，和通过对 p v c 进行明确的路由以实现流量工程的性能而被选择。但是一度曾只为 a t m 交换机所拥有的一些特性，现在也同样能被i n t e r n e t 骨干路由器所支 持。路由技术的最新发展，使i s p 重新评价其是否要继续容忍覆盖模型在 管理费用、设备费用、运行可靠性和可扩展性等方面的局限性。 基于a t m 的核心网一个最根本的局限性是它霈要对两个不同的网络进 行管理：a t m 基础结构和逻辑的i p 覆盖。通过在a t m 网上运行i p 两络， i s p 不仅仅增加了网络的复杂性，而且加倍了开销。这是因为i s p 必须管 理和协调两个分离网络的运行。同时，路由和流量工程分别在不同的系统 上来完成一一路由在路由器上执行，流量工程则在a t m 交换机上完成， 东北大学硕士学位论文 第二章流量工程系统模型 因此，将流量工程完全与路由器集成在一起将是非常困难的。最近的新技 术发展使i n t e r n e t 骨干网路由器能够提供以往只能在a t m 交换机上才能发 现的高速连接和确定的性能。当考虑要升级至o c 4 8 速率时，1 s p 必须决 定是继续使用昂贵和复杂的设计，还是使用一套设备即可完成相同功能的 基于路由器的完全集成的核心网。a t m 路由器接口未能跟上光学带宽的最 新发展，己商品化的最快的a t m s a r 路由器接口是o c 。1 2 。现在，o c 4 8 的p o s 路由器接口己经实现。很快，o c 1 9 2 ( 1 0 g b p s ) 的p o s 路由器接 口会被推出，但是，o c 一1 9 2 的a t m 路由器接口可能永远也不会商品化， 因为在如此高的速率上实现s a r 功能是非常昂贵和复杂的。s a r 在扩展 性上的这些局限，意味着当i s p 试图使用i p o v e r a t m 模型提高网络速率 时，将必须定购大型a t m 交换机和带有大量较低速率的a t m 接口的路由 器。当i s p 今后考虑向o c 1 9 2