（电工理论与新技术专业论文）通信网中基于mpls流量工程的路由研究.pdf

摘要 a b s t r a c t t o d a y , t h er a p i dp r o g r e s so fn e t w o r k st e c h n o l o g y , t h ee x p a n s i o no fn e t w o r k s d i m e n s i o n s ，t h ed i v e r s i f i c a t i o no fs e r v i c ek i n d sa n dt h ei n c r e a s eo fs e r v i c eq u a n t i t y , a r ea l lt h es t a t u so fn e t w o r k s d e v e l o p m e n t w i t l lt h ed e v e l o p m e n t m a n yp r o b l e m s h a v ea p p e a r e d ，s u c ha st h eq u a n t i t yo fs e r v i c ei m b a l a n c ei nn e t w o r k s ，n og u a r a n t e e f o rq u a l i t yo f s e r v i c e ( q o s ) i n19 9 0 s ，i ti sn 棚ce n g i n e e r i n g i nn e t w o r k st or e s o l v e t h e s ep r o b l e m s i nt h e s et e ny e a r s t r a m ce n g i n e e r i n gq u i c k l yh a sb e c o m eah o t s p o t f o rm a n yi n t e r n e ts e r v i c ep r o v i d e ra n dn e t w o r k s s t u d yg r o u p w i t ht h e d e e p l ys t u d y i n g a n dt h e t e c h n o l o g y sc o n s u m m a t i n g t h e t r a f f i c e n g i n e e r i n gb a s e d0 1 1 t h em u l t i p r o t o c o ll a b e ls w i t c h i n gb e c o m e st h ep r i m a r ym o d e lf o rl a r g e i n t e m e ts e r v i c ep r o v i d e r sn e t w o r k s ，w h i c hi st h et h i r ds t y l eo fn e t w o r k st h a ti s f u l l ym a d eu po f r o u t e r s t h et r a f f i ce n g i n e e r i n gb a s e do nt h em u l t i - p r o t o c o ll a b e ls w i t c h i n gi n v o l v e sf o u r f u n c t i o n a l c o m p o n e n t s ：p a c k e t - f o r w a r d i n gm o d e l ，r o u t i n g s e l e c t i o n m o d e l ， i n f o r m a t i o nd i s t r i b u t i o nm o d e l ，a n ds i g n a l i n gm o d e l e a c hf u n c t i o n a lc o m p o n e n ti s i n d i v i d u a la n di nc o m p a c tc o l l a b o r a t i v er e l a t i o n sw i t l lt h eo t h e r s i nw h i c hr o u t i n g s e l e c t i o nm o d u l ei so n eo f t h em o s ti m p o r t a n to n e s b a s i n go n t h ea n a l y s i st ot h ed e v e l o p i n go f m u t i n gr e s e a r c h ，t h ep a p e r p r e s e n t sa n e ws t a t i ca l g o r i t b m m u m - m e a s u r e m e n tc o n f i g u r i n gl s p a l g o r i t h mb a s e d o nc o n s t r a i n t s ( m u l t i - m e a s u r e m e n ta l g o r i t h m ) t h ea l g o r i t h mc o n s i d e r sa l l k i n d so fc o n s t r a i n t s ，w h i c hi n c l u d et h er e q u i r e m e n to fq o s d u r i n gt h er o u t i n g ，t h e c o n s t r a i n t so fn e t w o r k s r e s o u r c e ，a d m i n i s t r a n ts t r a t e g ya n ds oo n t h e s ec o n s t r a i n t s a r es a t i s f i e di nd i f f e r e n tp h a s e sd u r i n gt h er u n n i n g f i r s t l y , t h ea l g o r i t h mm a k e sa u n i t e do b j e c tb y a n a l y s e st h en e t w o r k s r u n n i n g s t a t u sa n dr e s o u r c e s t a t u s f o l l o w i n g t h e s e ，t h ea l g o r i t h mf i n d st h ee x p l i c a b l er o u t i n g ，i nw h i c he a c hr e q u i r e m e n to fq o si n t r a f f i c e n g i n e e r i n gi s f u l f i l l e da n dt h er e s o u r c eo fn e t w o r k si s f u l l yu s e d s ot h e a l g o r i t h md e c r e a s e st h ep o s s i b i l i t yo ft h ec o n g e s t i o na n di n c r e a s e st h en e t w o r k s c a p a b i l i t y f i n a l l yt h ep a p e rp r o v e st h a tt h ea l g o r i t h mi sf e a s i b l ea n dp r e f e r a b l eb y t h e o r e t i c a ld e d u c t i o na n d c o m p u t e r s i m u l a t i o n 2 糖要 a sn o wt h er e s e a r c ho ft r a f f i ce n g i n e e r i n gj u s to nt h es t a r ts p o t ，s ot h i ss t a t i c r o u t i n ga l g o r i t h mb a s e do nt h en e t w o r k s s t a t u sc a l lb ee s s e n t i a l l yi m p o r t a n tt o t h e r e s e a r c ho ft r a f f i ce n g i n e e r i n g ，a n di tc a ni m p r o v et h es c i e n t i f i cr e s e a r c ha n dt h e n e t w o r k e c o n o m i cd e v e l o p m e n t k e y w o r d s i c o m m u n i c a t i o nn e t w o r k 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 删p l s ，t r a f f i c e n g i n e e r i n g ，q u a l i t yo fs e r v i c e ，b a s e do nc o n s t r a i n t s ，m u l t i m e a s u r e m e n t ，s t a t i c r o u t i n ga l g o r i t h m 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨生盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：才勿乓裂签字日期：力加多年j 月跏日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权鑫洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：才多莲型一 导师签名： 弘韵耕 签字日期：枷年7 月矽日签字日期：2 一多年月，o 日 第一章绪论 第一章绪论 1 9 6 9 年世界第一个分组交换网a r p a r n e t 的问世标志着网络时代的到来。 现在计算机网络尤其是i n t e r n e t 的飞速发展已是有目共睹的，其应用领域已经涉 及技术、工程、应用等多方面，并对社会经济、文化、以及人们的工作方式、生 活方式都有着深远影响。可以毫不夸张地说，计算机网络己成为人类文明发展的 强劲推动力。 第一节计算机网络体系结构简述 首先需要清楚什么是计算机网络。计算机网络是地理上分散的多台独立自主 的计算机遵循约定的通信协议，通过软、硬件互连以实现交互通信、资源共享、 信息交换、协同工作以及在线处理等功能的系统吐 计算机网络的发展使得电子邮件、w e b 服务器、消息讨论组、网络电话以及 电子商务等各种网络应用不断涌现，并推动着社会各行业的变革。 计算机网络发展到现在经历了三个阶段：第一阶段是电路交换，以传统电信 网应用为代表；第二阶段是分组交换，1 9 7 6 年国际电报电话咨询委员会( c c i t t ) 制定了用于公用分组交换网的协议标准x 2 5 ：第三阶段是以网络协议一一 t c p i p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l i n t e m e tp r o t o c o l ，传输控制协议i n t e r n e t 协议) 地出现为标志，t c p i p 协议的广泛应用也正是计算机网络迅速发展的重 要原因之一。 i n t e r n e t 是全球最大的、开放的、由众多网络互连而成的计算机网络。i n t e m e t 的定义有狭义定义和广义定义两种【1 】： 1 狭义定义：由全球最大的、开放的、由众多网络互联而成的计算机网络中所 有采用i p 协议( i n t e m e t p r o t o c 0 1 ) 的网络互连而成的网络，即i p 网络。 2 广义定义：i p 网加上所有能通过路由选择至目的节点的网络，包括使用诸如 电子邮件这类应用层网关的网络，各类存储转发的网络以及采用非i p 协议 的网络。 i n t e m e t 核心是开放，且贯穿在整个体系结构中，i n t e m e t 体系结构如图1 1 所示： 1 第一章绪论 图1 1i n t e m e t 体系结构 在i n t e m e t 体系结构的最低层是物理传输导管，i n t e m e t 可建立在任何物理传 输网之上，包括租线、拨号电话网、x 2 5 、i s d n 网、以太网、f d d i 网、a t m 网、高速的h i p p i 接口以及无线网、卫星网等。 t c p i p 协议是实现互联网络连接性和互操作性的关键，它把成千上万 i n t e m e t 上的各种网络互联起来。 在高层，t c p i p 协议为i n t e m e t 用户提供了终端访问和客户服务器方式的服 务工具，诸如文件传输f t p 、虚拟终端t e l n e t 、电子邮件s m t p 等，用户可以根 据需要利用这些服务工具。而为管理整个网络，i n t e m e t 制定了简单网络管理协 议( s i m p l e n e t w o r k m a n a g e m e n t p r o t o c 0 1 s n m p ) 【2 1 。 从概念上讲，一个t c p i p 互联网提供 了三组服务。互联网服务的三个概念及其相 互的依赖关系如图1 2 所示。在最低层无连 接传送服务为其它层的服务提供了基础。在 第二层，一个可靠的传送服务为应用层提供 了一个高层平台。最高层是应用服务层。 应用服务 可靠的传送服务 无连接分组传送服务 图1 2 互联网服务的三概念层 i n t e m e t 软件是围绕着三个层次的概念化网络服务设计的。最基本的互联网 2 第一章绪论 服务是由一个分组传送系统组成。该服务被定义为不可靠的、尽最大努力传送的、 无连接分组传送系统。所谓不可靠，指的是不能保证正确传送，分组可能丢失、 重复、延迟或不按序传送，而且服务不检测这些情况，也不通知发送方和接受方。 这种不可靠的、无连接传送机制称为i n t e m e t 协议。i n t e r n e t 协议提供了三个 重要定义： 1 定义了在t c p i p 互联网上的数据传送的基本单元，规定了互联网上传送的 数据格式。 2 i n t e m e t 协议软件完成路由选择功能，选择数据传送的路径。 3 i n t e m e t 协议包含了一组不可靠分组传送的规则，指明了分组处理、差错信 息发生以及分组丢失等的规则。 i e m 上所述，t c p i p 协议的广泛应用真正的推动了i n t e m e t 网络的发展。 t c p i p 的工作原理是分层结构如图1 3 所示，它表示了两台主机上的应用程序 之间传输报文的过程。主机b 上的第n 层接收到的正是主机a 上的第n 层发送 出来的对象。 图1 3 t c p i p 分层工作原理 第二节流量工程的提出 计算机网络规模的急速膨胀无论从任何一个角度衡量，如主机的数量、 一3 第一章绪论 用户数、业务量、链路数、单条链路的带宽、或是服务提供商( i n t e r n e ts e r v i c e p r o v i d e r ，i s p ) 网络的增长率，其增长速度都是惊人的。这种膨胀不可避免地带 来了诸多问题： 现有的i n t e m e t 主干速率较低，尤其是各国的国际出口，更是显得车水马龙、 拥挤不堪； 现有的i n t e m e t 路由器工作方式( 依靠软件进行选路和数据包转发，速度难 以提高；随着i n t e m e t 的急剧膨胀，选路信息处理工作量越来越大，路由表 越来越复杂，路由信息占用大量的带宽等) 和吞吐量无法满足i n t e r n e t 日益 增长的需求； 各i s p 之间和其内部网络严重拥挤，忙时网络拥塞和数据包丢失非常严重， 极大地影响网络传输的效率； 现有i n t e m e t 没有带宽控制和流量控制功能，服务质量( q u a l i t y o fs e r v i c e ， q o s ) 难以得到保证。 因此，网络服务提供商必须面对i n t e r n e t 如此爆炸性的发展以及发展中出现 的问题，同时也要面对来自横向的激烈的竞争。更好地使他们的网络满足客户日 益增长的需求，并使网络稳定、快速、高效地运行，并且具有灵活性和可扩展性， 以适应将来网络发展的需求。这就要求i s p 必须有效地控制业务量在网络中的分 配，从而合理利用现有的网络资源，为客户提供优良的服务。 流量工程( t r a f f i ce n g i n e e r i n g ，t e ) 【2 】就是在这时期提出的一种用于解决 以上诸多问题的工具，它使i s p 能够在现有的网络资源条件下，在其路由域内对 流量的分布进行精确的控制：流量工程还可以在i s p 网络内将业务流转移到另一 条潜在的具有更小拥塞的物理路径上去，从而平衡网络中各种链路、路由器和交 换机上的负载，使其中任何一个组成部分都不会发生过载或者未充分利用。 i n t e r n e t 流量工程定义为i n t e m e t 网络工程的一部分。处理i p 网络操作中的 性能估价和性能优化【2 】。流量工程的核心是流量控制和资源管理。t e 的性能指标 分为流量导向和资源导向两方面。流量导向的性能决定网络对流量的处理能力和 服务能力，主要日标包括最小分组丢失率，最小传输延迟，最大吞吐量。服务水 平约定等；资源导向针对的是优化资源使用，目标是合理使用资源和优化资源配 置，尤其希望避免网络的一部分超负荷使用而另一部分未充分使用。带宽是关键 4 一 第一章绪论 和紧缺的资源，流量工程的中心管理对象是带宽。 现在，j u n i p e r 、c i s c o 等公司已经开始热点研究新型的骨干网路由器以及在 以新型的骨干网路由器为核心的网络中流量工程如何满足q o s 需求、如何应用 的问题。这些路由器用硬件进行路由查询和包转发，实现了选路和包转发的分离， 大大提高了路由器的转发速率，使下一代i n t e r n e t 网络的建立成为可能c 5 j 【7 j 。而 用流量工程作为工具则能够优化可用带宽和网络保留能力的需要：提供新的协 议、新的路由硬件、新的交换硬件和光纤设备：预留足够空间和适当能源的后勤 工作，配置设备以适应链路可用性和用户需要。因此是否能够提供功能强大的流 量工程机制是每一个i s p 吸引用户，在竞争中得到成功的决定因素。 第三节选题意义和内容安排 当今，i n t e r n e t 的发展可谓日新月异。伴随着i n t e m e t 的发展，其应用领域 也急速拓展。因此，网络传输业务量成指数形式增长( 如数据量巨大网络多媒体 传输) 。由此需要在新的服务体系下应用流量工程来优化网络性能。流量工程在 原有网络资源基础上可以精确控制业务量，并能提供服务质量保证。关于流量工 程的讨论是目前在i n t e m e t 业界、大型的i s p 、以及如因特网工程任务i f l ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ，i e t f ) 等研究组织的热点话题。薪一代i n t e r n e t 网络的 形成，并没有使旨在优化网络运行的流量工程的研究止步，正相反，新的网络运 营方式、新的服务要求，反而向这些研究提出了新的课题。无论是过去的、今天 的还是未来的网络，仅仅增加网络带宽，提高传输速度，没有流量工程的软件支 持，路由器就不能有效地对业务流进行有效的控制，从而造成网络资源的浪费或 者使用效率不高，从而不能从根本上解决网络拥塞和数据丢失，而且不能满足越 来越多的服务种类和服务质量的要求。所以，在网络研究的领域中，流量工程的 重要性对i s p 来说日益增长的。 路由选择是网络中路由器交换机应具备的最基本的功能，更是流量工程中 的最重要的组成部分之一；静态路由的配置影响网络对处理业务流时的最初策 略，决定网络资源的初始分配方案，对业务量的控制和动态路由的计算有着重要 的影响。在路由选择方面，目前对动态路由的研究比较多，对静态路由选择的研 s 第一章绪论 究比较少，目前普遍使用的静态路由配置方法采用传统的简单算法或者人工配 置，这种方法已经不能适应越来越大的网络规模和越来越复杂的网络状态。所以 对静态路由选择的研究在流量工程研究中的重要性也日益显著。 在已有研究成果的基础上，本文提出一种新的静态路由算法基于约束的 多量度配置l s p 算法( 简称多量度算法) 。算法考虑路由时要应用的q o s 需求、 网络的资源约束和管理属性等诸多约束；首先分阶段来处理各种约束条件，分析 网络运行状态和资源实用状况，随后由分析结论制定主次目标策略，在计算路由 中运用主次目标的方法来选择路由，从而满足配置的l s p 的多约束需求，并使 得网络资源得到充分的均衡的使用，减少潜在的网络拥塞可能性。在国内，关于 流量工程的研究刚刚开展，所以这种以网络赍源状况为立足点的基于约束静态路 由算法研究将会促进流量工程的发展，对我们的科研和网络经济的发展也具有重 要意义。 本文内容安排如下：第章为绪论，简述计算机网络体系结构，为了解决网 络发展带来的问题而提出解决方案流量工程，并给出本论文的选题意义和内 容安排；第二章详细论述通信网的流量工程，并讨论流量工程在不同的网络类型 中的应用，其中重点阐述在新一代路由器核心网络中的流量工程的实施方案 m p l s 技术；第三章阐述目前流量工程中使用的动态路由算法和静态路由算法， 以及基于约束的路由算法，并指出现行算法的不足；第四章讲述本文提出的一种 新的静态路由算法基于约束的多量度配置l s p 算法，解决现行算法的缺点， 并从理论上( 算法的时间复杂度) 论证多量度算法的有效性。第五章通过网络实 例对算法进行仿真验证，证明算法的较优性；最后对算法作出总结，指出算法的 优点。第六章回顾总结全文，并提出今后还需继续研究的相关问题。 - 6 第二章流量工程研究 第二章通信网的流量工程研究 第一节流量工程综述 2 0 世纪9 0 年代早期，网络规模较小，i s p 网络由专线链接起来的路由器组 成。这种传统路由器用软件对数据包进行分组和转发。当i n t e m e t 开始快速增长 的时候，路由器和带宽就不能满足应用的需求。i s p 为了解决这个问题，增加了 链路与路由器的数量。由于路由器与链路数量的增加，网络的拓扑变得复杂起来， 网络的连通度提高，同一点对问的路径数量也增加了。如果可以对业务量在网络 中传输的路径进行控制，则可以有效的利用网络中比较多的带宽资源。由此提出 了对流量工程的研究。 同时，随着客户对带宽及业务的需求越来越高、越来越多样化，i s p 们面临 的压力不但来自于如何有效的利用网络中宝贵的资源还来自如何使他们的网络 满足客户日益增长的需求，并使网络具有较高的灵活性和可扩展性，以适应将来 网络发展的需求。这便要求i s p 对客户业务在网络中的分配进行控制，从而充分、 有效地利用现有网络带宽，为客户提供优质服务。这种将业务流量映射到现有物 理拓扑上的任务称为流量工程【3 】 3 1 【3 3 】。 本节从流量工程实施的目的、具有的功能、实现要求以及其过程模型四个方 面阐述流量工程体系。 2 1 1 流量工程实施的目的 流量工程的目的是为i s p 网络提供精确的流量控制，具体地说是在流量沿 定路径传送时为底层结构提供附加信息，使网络运行更加有效、可靠、便利，同 时优化网络资源的使用。简单地说，流量工程就是将业务量映射到实际物理网络 拓扑上的过程【3 】【9 1 。 2 1 2 流量工程具有的功能 流量工程提供在主干网络路由域上的流量精确控制，希望卷入进程的人工干 7 - 第二章流量工程研究 预最小化，因此流量工程需要具有以下功能： 1 对主路径进行路由时，绕过网络中已知的瓶颈点和阻塞点。 2 当主路径发生一个或多个故障时，为业务如何进行重新路由提供明确控 制。 3 通过确保网络的附属设备不会被过度使用，同时，潜在的被选路径上的 网络附属设备未被充分使用，从而对这些可用的集成带宽和长距离光纤 进行有效的利用。 4 通过使包丢失最小化、使阻塞的保持时间最小化和使吞吐量最大化的方 法增强网络中以业务为导向的性能特性。 5 增强网络中将来用于支持多业务i n t e r a c t 的统计约束性能特性( 如，丢失 率、延迟变化、传输时延等) 。 6 为客户提供更多的选择，更低的费用和更好的服务。 2 1 3 流量工程的要求 流量工程应当看作是路由器中集成的一个网络功能，所以流量工程的要求也 是对路由器的要求。在流量工程环境中，网络条件和业务量的情况有了很大的变 化，路由和转发技术不同于传统i p 网络中的技术，路由器的功能有所差别，流 量工程对路由器的要求也就有其特殊的含义。 2 1 3 1 流量工程的一般要求 流量工程的一般要求包括以下八点【2 1 1 3 1 ： 可用性：流量工程系统可运行在现有的网络上，而且容易操作和维护； 自动性：流量工程系统能自动执行流量工程的功能而尽可能减少人工介入； 可扩展性：流量工程系统应该能随着网络的发展而扩展： 稳定性：系统对网络状态变化做出响应必须在快速反应性和稳定性之间折衷 处理： 灵活性：允许优化策略根据网络情况灵活地改变。 可观测性：具有从网络中收集数据和分析数据以决定网络性能好坏和判断优 化策略效果的机制，得到网络的统计数据以作为网络状态的指示。 8 第二章流量工程研究 简单性：流量工程系统在实现时应当尽量简单，对用户来说是不透明的。 拥塞管理：流量工程系统能够把流量合理地映射到网络上以避免或减小拥塞， 同时拥塞发生时可以迅速转移流量。 2 1 3 2 路由选择要求 路由控制机制是流量工程的一个最重要的方面，由于传统基于最短路算法的 内部网关协议( i n t e r i o r g a t e w a y p r o t o c o l ，i g p 协议) 的限制【3 】【2 7 1 1 3 8 】口9 1 ，需要新 的控制i p 网络中路由选择功能的能力，这些能力包括： 基于约束的路由( c o n s t r a i nb a s e dr o u t i n g ，c r ) 选择算法【1 4 】 1 6 】：计算出能 满足多个约束条件的路径。 扩展传统的链路状态i g p 能够传播c r 需要的多种拓扑状态信息； 多条路径上的负载分配可以配置，灵活控制流量分发； 在控制某部分流量的路由时，尽可能不影响其他部分流量的路由； 如果网络支持多种服务类型，路由子系统应当有为不同类型的流选择不同的 路的能力。 2 1 3 3 测量要求 为支持流量工程的功能，应提供设备从网络中测量和收集统计数据，并有能 力对收集的统计数据进行分析。这些设备的行为不能对收集的统计数据的精确性 和整体性产生不利影响。同时，收集统计数据的机制也应随着网络发展而改进。 流量统计可以根据时间长短分为长期的和短期的，长期的流量统计反应网络 周期性的负载，对长期的流量统计数据分析可得出如高峰时期特性、流量增长模 式、持续拥塞等热点问题，以及由于路由不合理引起链路使用不平衡等间接的统 计数据；在短期类型中，流量统计对网络当前状态提供合理和可靠的指示，反应 链路使用和链路、路径拥塞状态。发布这些信息的例子包括s n m p 、探测技术、 f t p 、内部网关协议、链路状态通告等。 2 1 3 4 ，生存性要求 网络生存性指网络中存在失败时网络维持服务的连续性的能力。要求网络有 第二章流量工程研究 能力快速地从失败中恢复并维持恢复后现存服务的q o s 要求。随着i n t e m e t 中关 键流量、实对流量、其他高优先级的流量传送任务需求的目益增长，生存性已经 成为i n t e r n e t 业界非常关心的一个问题。随着网络技术不断发展，失败的监测和 恢复能力已经可以在多层得到口儿5 6 1 。例如，第二层技术如异步传输模式 ( a s y n c h r o n o u st r a n s f e rm o d e 。a t m ) 用自动保护交换( a u t o m a t i cp r o t e c t i o n s w i t c h i n g ，a p s ) 和自愈环和自愈网( s e l f - h e a l i n gr i n ga n d m e s h ) 机制提供残存 能力，在i p 层使用重路由( r e r o m i n g ) 的方法在链路和节点中断后恢复服务的 连续性，i p 层的重路由在一段时间的路由收敛后发生，收敛需要几秒到几分钟 完成。 2 13 ，5 离线的流量工程支持系统的要求 如果希望得到最佳的链路效率，离线的集中的流量工程支持系统可能作为一 个整个流量工程系统中一个完整的部分提供。离线和集中的流量工程支持系统可 以用来计算流量簇的路径。考虑到流量簇的要求、链路属性和网络拓扑信息离 线的流量工程支持系统一般可以找到比在线的流量工程系统更好的流量簇配置， 在线系统的网络中每个路由器以分布方式基于它自己的信息找到路径。离线的流 量工程支持系统可以周期地计算流量簇的路径( 比如说每天) ，目的是再优化。 然后计算出的路径可以下载到路由器中。在线的流量工程系统仍然需要，以便路 由器可以迅速地适应变化。 2 。1 4 流量工程的过程模型 抛却流量工程的执行细节在网络与网络之间的不同，为描述大多数流量工程 过程普遍的行为，优化运行中的系统性能，按照运作流量工程的顺序或者更一般 的流量工程系统描述，流量工程实施过程可以分为四个阶段： 第一阶段是定义在网络中支配运行相关的控制策略。这些策略可能基于流行 的商业模型，网络开销的构成，网络运行约束，一个或多个最优化标准，还有其 他方面。 第二个阶段是一个从运行的网络中请求测量数据的反馈过程。综合工作负荷 可能用估算或使用以前的经验数据或者流量特征的数学模型做出推断，或使用其 。1 0 第二章流量工程研究 他手段。 第三阶段是分析网络状态来描述流量负荷。一般地，性能分析可能是主动的 或者是反应性的。主动的性能分析指明并不存在的潜在问题，但是可能会在将来 发生：而反应性的性能分析指明现存的问题，通过诊断程序确定原因，如果有必 要分析代替的方法做出补救。许多定性和定量的技术可能在分析过程中使用，包 括基于建模的分析和仿真。在过程模型的分析阶段，需要研究网络流量的分布情 况和负荷特征，指出流量瓶颈和网络异常。流量矩阵构造可能作为分析过程的一 部分。 第四个阶段关于网络性能的优化。性能优化阶段一般包括在可选行为中做出 一系列选择并执行。优化行为可能包括适当的技术用来控制流量及其分配，扩充 网络规模，增加网络设备，以系统的方式调整相关路由的参数如i g p 的量度和 b g p 的属性，调整流量管理属性，调整网络参数和网络元素的配置。 第二节i s p 网络发展及流量工程在其中的实现 因为流量工程最终是要应用到网络中，对其路由域内对流量的分布进行精确 的控制，所以流量工程的发展和i s p 网络类型的发展是一致的。网络类型的发展 大致经历三个阶段：传统的路由器核心的网络、p 覆盖模型网络( i p o v e r - a t m ) 、 新一代路由器核心网络【l 】【1 4 1 。以下章节分别讲述这些网络类型以及流量工程在其 中的实现。 2 2 1 传统的路由器核心网络及流量工程的实现 在2 0 世纪9 0 年代初期，i s p 的网络通过使用租用线- - t 1 ( 1 5 m b p s ) 和t 3 ( 4 5 m b p s ) 连接一将路由器互联丽组成网络。当i n t e r a c t 开始它的爆发性增长时， 对带宽需求的增长要比单条网络连接速率快得多。i s p 们对这一挑战的反应是提 供更多的链接以提供额外带宽。从这一点看，流量工程对i s p 变得越来越重要了， 因此，当存在多条并行或各选路径时，i s p 们可以有效地使用集成网络带宽。 在传统的路由器核心网络中，流量工程的实现基于简单的路由加权的流量控 - 1 1 - 第二章流量工程研究 制。基于加权量度控制的流量工程运行的原理如图2 1 所示。图中标出了各条链 路的权值。假定网络a 向网络c 和d 发送大量的信息，由于网络a 到网络c 和 网络a 到网络d 的流量都经过链路1 、链路2 ，会导致这两条链路拥塞。如果把 链路4 的权值改为2 ，a 到d 的流量就流经链路4 ，而a 到c 的流量仍然在链路 1 和链路2 上。这样，链路1 和链路2 上的负载减少，拥塞的问题就解决了1 2 j 。 路由器b t 2 r l c = 1 路由器c 图2 1 基于量度的流量工程 起初网络规模和业务流量都非常小，这种简单的方法直到九十年代中期还是 能够胜任的。随着i s p 网络的不断增大，而基于简单加权的流量处理方法可扩充 性能差，不能保证对网络某一部分的调整不会引起其他部分出现问题；传统路由 器的处理能力不能承担高负荷的处理任务；基于简单加权的拓扑驱动的i g p 路 由计算不考虑网络的负载情况，导致流量在网络链路中不能均衡分配，链路负载 不均，资源得不到有效利用，拥塞的可能性增大。 传统路由核心网在为流量工程提供可扩展的支持上存在的许多局限日益显 现： 由于传统路由器的汇集带宽和包处理能力有一定的局限性，因此，传统的、 基于软件的路由器在高负荷的情况下可能成为潜在的瓶颈。 基于量度处理的流量工程不具有可扩展性。当i s p 网络变的具有更多的链按 时( 即，更大、更密集的结网和更多的冗余) ，这种情况下很难保证对网络 某个部分量度的调整而不致在网络的其它部分引起问题。基于量度处理的流 量工程对于增加的复杂问题提供的是一跟踪- g q 错的鳃决方式，而不是一个 科学的解决方案。 i g p 计算是通过拓扑驱动的，它只基于一个简单的附加量度，如跳数或某个 管理值。i g p 不发布类似于带宽可用性和业务特征等信息。这样对于复杂连 1 2 第二章流量工程研究 接网络，不利于业务所使用的链路进行控制以确保链路的负荷均衡。 2 2 2 i p 覆盖模型网络( i p o v e r - a t m ) 及流量工程实现 2 0 世纪9 0 年代中期( 1 9 9 4 年1 9 9 5 年) ，i n t e m e t 业务量的增长要求i s p 是他们的网络支持t 3 ( 4 5 m b p s ) 以的速率，这时的o c 3a t m 接口技术可以使 路由器和交换机能够得到1 5 5 m b p s 的传输速率，因此产生了i p o v e r a t m 网 络，其典型结构如图2 2 所示【2 】 6 】 1 4 ： 0 c 3 a t mi o c 1 2 硝m 图2 2 典型的i po v i b z a t 蕞网络结构 在i p o v e r a t m 网络中，路由器围绕在a t m 网络边缘，每个路由器通过 一系列经由a t m 物理拓扑设置的永久虚电路( p e r p e t u i t y v i s u a lc i r c u i t ，p v c ) 与其他路由器相连。路由器不能直接控制虚电路连接的信息，它只知道单独的 p v c 就像简单的点对点链路那样连接着两个路由器。i p o v e r a t m 网络中物 理拓扑和逻辑拓扑的区别如图2 3 所示。 枞恻蛔p i a 付 一名堰吣 芬 u m , lb 事c 协印b 鲫 图2 3 i p o v e r a t m 网络中物理拓扑和逻辑拓扑 在此，永久虚电路覆盖的物理路径通常是通过离线配置计算获得的，它使用 基于需求的方式当网络中发生拥塞新增一条干线或配置一个新的接触点 1 3 第二章流量工程研究 ( p o i n to fp r e s e n c e ，p o p ) 。此外。一些a f m 提供上使用在线调整的方法来实 现流量工程。p v c 的实际路经和特性由一个全局优化和配置的功能依据链路的 带宽和历史流量时间表来提供。离线计算可以提供一些辅助的p v c 以备在发生 失败的时候使用。全局的优化和计算完成后，配置参数下载到路由器和a t m 交 换机上，这样便形成了一个全网络的逻辑拓扑。实际上，离线设置程序产生路由 和交换两部分配置。a t m 的p v c 可以映射为路由器的子接口，路由协议把i p 前缀( p r e f i x ) 与子接口对应起来。最后，a t m 的p v c 通过运行i g p 协议集成 到i p 网络中。 现在流量工程的典型做法是在i p o v e r a t m 网络上使用人工配置。这种 机制中，a t m 交换机提供的高速接口和明显提高的汇集带宽使网络性能得到明 显改善，链路资源得到比较均衡的利用，网络具有了在线调整p v c 路由的功能 和解决拥塞问题的功能，因此避免了在网络核心的部分因路由器引起的瓶颈的潜 在可能性，a t m 网络的速率和带宽为i s p 提供了确定的性能。并且，由a t m 交 换机提供的每条p v c 的统计信息，简化了监测用于优化p v c 布局及管理的业务 参数的过程。网络设计者最初为支持特定的流量工程目的而提供每条p v c ，然 后，他们连续监测每条p v c 上的业务负载。当一条特定的p v c 发生拥塞时，i s p 具有所需要的信息，使其能够通过修改虚拟或物理拓扑结构以适应便宜的业务负 荷，对发生的事件进行补救。 因此，一个基于a t m 的核心网完全支持流量工程，它可以对p v c 进行明确 的路由。p v c 的路由是通过在网络底层的物理拓扑上提供的随机的虚拟拓扑实 现的，而在网络底层的物理拓扑上，通过对p v c 进行路由以使业务分配到所有 链路上去，以致链路被平均便用。这种实现避免了、韭务全部忙集到的花销路由上 去，从而避免了链路的过分使用或未被充分使用。由a t m p v c 提供的流量工程 性能使i s p 在他们的市场范围内更具竞争性，允许他们为其客户提供低费用和确 保质量的服务。 但是，随着网络的迅速膨胀和用户服务要求的不断变亿，现有的i p o v e r a t m 机制的缺陷也日益明显。这种局限主要表现为： 必须对a t m 下层结构和逻辑上的i p 覆盖两个网络同时进行管理： a t m 的接口技术未能跟上光学带宽的最新发展，设备费用和管理费用高昂； 一1 4 - 第二章流量工程研究 转发包时必定要支付的a t m 信元税( c a l 卜t a x ) 导致不能对带宽充分利用； 网络扩充时的n 2 比例问题和故障处理链路更新时的n 3 比例问题。 网络的物理拓扑结构和逻辑结构不相匹配。 除了这些缺陷，混合媒体网络( 如光网络) 的增长和减少i p 光纤间的层数 的目的，要求流量工程在第3 层实现，但是，基于覆盖模型的流量工程要求支持 交换和p v c 的第二层技术存在，这使得难以提出一可行方案。 总之，i p o v e r a t m 网络模型的诸多不利随着i n t e r n e t 的发展，越来越显 现突出。高速接口、确定的性能、和使用p v c 的流量工程不再使a t m 交换机明 显区别于i n t e r a c t 骨干网路由器。而且，基于路由器的核心网的匹配问题解决了 a t m 模型的一些固有问题一一协议两个分离系统的负载性和较高的费用， a t m s a r 接口的带宽局限性，p v c 的“n “问题，i g p 压力，不能在混合媒体 结构中运行的局限性，和不能实现第2 层和第3 层之阗的无缝连接的不利因素等。 因此，i s p 必须考虑一种新的技术来取代现有机制。 2 2 3 新一代路由器核心网络 当i s p 开始计划转移到更高速的网络时，他们会仔细检查选择方案，使他们 过去的流量工程策略不会约束将来网络的增长和运行。对于运行在o c - - 4 8 速率 上的高性能骨干网，问题变化得非常快，以至于保持相同策略只采用辅助的( 或 主要的) 增强方式去修改或调整网络方案己不可能。当他们不能扩展时，网络设 计人员将重新考虑新的解决方案。 目前，c i s c o 、j u n i p e r 等大型的网络厂商和一些新兴的厂商都在致力于i n t e r n e t 骨干路由器的研究开发。新型的路由器集成了i n t e r a c t 可伸缩性、i n t e r a c t 控制和 从前只有在交换机上才有的高性能的转发，还兼顾路由软件的灵活性( 即可控制 性) 和稳定性( 即可靠性) 。 与此同时，厂商们和i e t f 开始研究路由器的路由功能和a t m 交换机的转发 功能相结合的多标记交换( m u l t i p r o t o c o l l a b e ls w i t c h i n g ，m p l s ) 技术【7 】【8 】【9 】。 m p l s 是多层交换机研究得最新进展和标准化产物。m p l s 为大型i s p 网络实施 流量工程提供了坚实的基础，使其成为在i n t e m e t 中实现流量工程得首