（计算机系统结构专业论文）基于mpls的流量工程.pdf

基于m p l s 的流量工程 提要： 本文的主要工作是建立基于m p 竖的通量王摆搓型，m p l s 作为下一代网络的主要技术， 在很多方面表现出了优异的特性。对于流量工程的支持就是一个重要方向。”+ 流量工程的概念来源于通过对网络资源和流量的综合管理，优化网络的性能，提高网络 的可用性和费效比，网络的资源得到最大化的利用，网络的运行得到最大的可靠性和有效性。 f 在商业运行的网络中，通过对已投资设施的充分利用获取竞争优势和商业回报的要求使得流 、 量 程日益成为网络运营中不可缺少的手段。7 比较了基rt c p 的遁管理机制和a t m 中的通行量管理机制之后，我们通过借鉴两者 的优点，发挥面向连接和面向非连接两种处理方法的长处，建立一种基于m p l s 支持的流量 ， 管理模型。f 该模型的特点是：管理功能模块边缘化，运输功能模块平面化，在高速，简单的 运载核心上运行一个可管理的流量承载平台。t 7 一 模型的有效性通过两个方法得到评估。一是从形式上的证明了模型运行状态的稳定性， 完备性和对于时间轴的收敛性。二是使用n e t w o r ks i m u l a t e r 建立模拟的旦终环境验证对网 络运行状态的优化结果。主要的工作是算法设计和算法的形式化证明。 i 在本文中我们使用了几个关键性的概念：基于聚集的流量、流聚集、流量聚集点和流量 分解点、扩充( 承载能力占用率) 链路耗费参数、分布式公平队列等。 在理论结果的基础上我们将进一步开发实际系统来实现该模型，包括仿真系统中实现流 量管理模块和在8 6 3 项目( c a i n o n e t m p l s 在光网上的应用研究) 中研究并开发核心路 由器和光交换机上的流量管理与m p l s 模块的工作；。 关键词：m p l s t r a f f i ce n g i n e e r i n g ，i ps w i t c h ，l a b e l ，l d p , o s p f , i po v e rd w d m 啡耀蠢y 7 4 基于m p l s 的流量工程 a b s t r a c t i nt h i sp a p e r w ed i s c u s s e dat r a f f i ce n g i n e e d n gm o d e lo ft c p i pn e t w o r k s te s p e c i a l l y i nt h ec o n t e x to fc u r r e n ti n t e r n e ta p p l i c a t i o n s t h i sm o d e li s b a s e do nt h ei d e ao ft r a f f i c a g g r e s s i v ea n di s a na l t e r a t i v ev i e wo ft h eb l a c kb o xm o d e lo ft c p i pn e t w o r k - m p l sw i l l p r o v i d e t h i sm o d e la g o o dp l a t f o r mt ob u i l du p a na u t o m a t i s me n a b l e dn e t w o r ki n f r a s t r u c t u r e w i t hm i n i m i z e dt u n i n go p e r a t i o n s w h or u n n i n ga ni n t e r n e tb a c k b o n eo ra c o r en e t w o r ko f a nj s pc a ns a v et h e i rc o s to nb a n d w i d t ht h ee v a l u a t i o no ft h i sm o d e lw a s u n d e rn e t w o r k s i m u l a t o rr u n n i n go nl i n u x t h i sm o d ef o c u s e so nt h ef a i r l yt r a f f i cf o r w a r d i n gc a p a b i l i t yd i s t r i b u t i o n w ew a n tt ot a k e c a r eo ft h et r a f f i c sf e di n t ot h en e t w o r ka n dt a k ea c t i o n sb e f o r es o m el i n k sb e i n gc o n g e s t e d d u et oo v e r l o a d i n g b a s e do nad i s t r i b u t e da l g o r i t h mw eb u i l du pan e t w o r ko nw h i c ht h et r a f f i ci sc a r r i e db y v i r t u a lt r u n k s t h i si san a m ef o rt h ea g g r e s s i v eo ft r a f f i c w ep r o v e dt h em o d e lw o r k s t h e p r o v i d e n ti sb o t hf o r m a l l ya n de x p e d i e n t l y t h ef u t u r ew o r k si n c l u d e si m p l e m e n t a t i o ni nn e t w o r ks i m u l a t o ra n da c t u a lo p e r a t i o n a l n e t w o r kd e v i c e se s p e c i a l l yw ea r ew o r k i n go nc a i n o n e t , a8 6 3p r o j e c tw h i c hl e a d i n gt o b u i l du dam p l so v e rd w d mn e t w o r ki nc h i n a k e y w o r d s ：m p l s ，t r a f f i ce n g i n e e r i n g ，i ps w i t c h l a b e l l d p , o s p f , i po v e rd w d m 5 墓于m p l s 的流量工程 第一章问题的提出与背景 1 1 网络流量特性的演化 网络的应用环境在过去的几年中有了深刻的变化，大量的互动性应用( i n t e r a c t i v e a 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 s ) 占据了网络流量的主导地位，由 此引发的网络运行状态的变化是长期的和决定性的( 见【1 5 】【1 6 】) ，这也是本文工作的出发点。 在此我们必须对现有的网络流量特性做一个简要的概括。 在经过最近十年的互联网发展之后，网络上的应用集合已经有了根本的转变，主要的特 征是流量要求的两极分化和接入端系统的复杂化。 流量要求的两极分化是指：一方面流式媒体( s t e a m i n gm e d i a ) 的广泛应用要求计算机 网络支持许多电信网的流量特征，另一方面万维网( w o r l dw i d ew e b ) 的流行又决定了计算 机网络的灵活传送机制的必要性。在面向服务和面向资源两个相互制约的要求中，网络的运 行策略和管理模型处于两难的境地。 接入端系统的复杂化是指：端系统的内部处理能力不断得到强化，从而对流量服务的要 求也不断上升，许多的连接多个端系统而组成的应用系统必须依赖于网络才能正常工作，如 分布式文件系统，群件系统，电子商务系统等。网络的运行状态与应用系统的运行状态的联 系越来越紧密，由此带来的问题是端系统对网络的可控制性要求越来越高，端系统常常通过 合法或不合法的手段企图影响网络的运行，获取对自身比较有利的地位。 计算机网络建立的初期，专业用户的使用占了绝大部分，所以协议的简洁，高效成为设 计者的首要目标，t c p i i p 协议是顺应这一要求的成功代表，当计算机网络用户对服务的要求 提高之后，另一个发展方向曾经风光一时，这就是a t m 的出现。这一代表了计算机网络电 信化趋势的体系结构最终没能满足计算机网络的低价格，高效用要求，只能局限于高端市场 的有限使用。 当前的实际状况是：主干网使用a t m 作为流量的预配置通道，在这些逻辑链路之上运 行着基于l p 的互联网络( 见【1 】) 。a t m 的各种优良特性没有得到相应的发挥，反而让a t m 与l p 之间的天然鸿沟浪费了大量的网络资源。 6 基于l s 的流量工程 1 。2 最近的互联网业务发展及其对网络流量特性的影响 互联网在近期的主要应用向两个方向发展，一是高交互性的信息查询与电子商务应用 二是大数据量的多媒体与协同工作应用。 作为信息服务提供者而言，每个用户请求所返回的数据量正在被降低，如对网站首页的 访问只需返回( 往往也只能返回) 不多于5 0 k 的数据流这是当前的接入网数据速率所决定的， 用户无法忍受过长的下载时间等待。同时，网站设计者为了符合用户的心理，将页面分解为 多个元素，分几次h t t p 请求下载，这也加剧了短而集中的数据流量，可以预见到的是x m l 和x s l 在w w w 中的广泛使用将进一步带来此类流量的增加，因为x m l 所支持的数据交换 将时下一代基于i c e 的服务器群间流量的主体，服务器之问的信息交换反应速度是用户与服 务器间信息交换速度的05 0 ”倍，由此对互联网运行状态产生的影响是不可忽视的。 同时多媒体在，w w 中的广泛使用使另一个极端的数据流量也充斥了网络，长时间的持 续流量特征使多媒体与协同应用成为网络带宽的主要消耗者，这一应用领域包括了流式媒体 如f l a s h ，r e a la u d i o ，q u i c kt i m e 等，同时还有如n e t m e e t i n g 的远程协同工作系统，这 一类应用的共同特征是对正向数据流的损失有强的抵抗力，但对控制信息的丢失则非常敏 感。 另外，一些正在试验中还未广泛使用的应用模式将给网络流量带来一些影响，如v p n 服务，将需要高的数据递交可靠性和流量安全策略，如分布式数据库服务，将要求高可靠性 和高突发性。这些应用在实现时往往要求网络提供可估计的服务质量。 1 3 流量工程问题的历史和已有成果 1 3 1 流量工程 流量工程的概念来源于通过对网络资源和流量的综合管理，优化网络的性能，提高网络 的可用性和费效比，网络的资源得到最大化的利用，网络的运行得到最大的可靠性和有效性。 在商业运行的网络中，通过对己投资设施的充分利用获取竞争优势和商业回报的要求使得流 量工程日益成为网络运营中不可缺少的手段。 流量工程的目标是优化系统的性能，这一! g l 标的具体表现由两种方式： 面向资源的 7 基于m p l s 的流量工程 面向流量的 面向资源的优化目标包含了充分利用资源的各种方面，主要的目标是防止以下的情况： - 资源的不正常空闲，如几条并行信道中某个特定信道的空闲 一资源的拥塞， 面向流量的优化目标则包含了以下要点： 降低数据包丢失率 - 降低延迟 _ 增加吞吐量 提高服务等级 不论是面向资源的还是面向流量的流量工程目标拥塞控制都是一个基本的要求。在原有的 协议，如t c p 中处理的是由于网络的正反馈特性而引起的网络控制系统的发散，即网络在 没有达到满负荷时发生的拥塞。与之相反的，流量工程所关注的拥塞是由于网络承载能力不 足或承载能力分配不合理而发生的拥塞。前者可以通过增加承载能力或限制用户使用加以解 决，后者则是流量工程研究的重点所在，通过对流量和承载能力的测量，估算，分配和审计， 最大限度的利用资源，防止和解决拥塞问题。 1 4 m p l s 的历史 m p l s 是在一系列技术的发展和推动下不断发展起来的。 1 4 。1 i po v e ra t m 的产生 虽然m p l s 的应用已经不仅仅限于i p o a a t m 的标准化工作从1 9 8 0 年就已经开始了， 的研究。i e t f 的几个工作组解决了这一问题， 文件r f c1 4 8 3 与r f c1 5 7 7 。 但对i p o a 的改进却是m p l s 产生的源动力， 很快，l p 界便开始了对如何将i p 实现于a t m 并且于1 9 9 3 ，1 9 9 4 形成了两份著名的r f c r f c l 4 8 3 描述了如何将i p 报文封装于a t m 信元之中，而r f c l 5 7 7 ( c l a s s i c a li po v e r a t m 即经典i p o a ) 和a t m a r p ( a t m 地址解析协议) 。 c i p o a 将a t m 网络设计成一种子网( l o g i c a li ps u b n e t ) 技术，即： i p 路由器分别处于不同的子网( l i s ) 之中，当通信双方同处一个子网时， 信，如若不然，二者之间的通信需要牵涉到一个或更多的中间路由器。 则定义了c t p o a 网络上的主机与 二者可以直接通 8 基于m p l s 的流量工程 由于c i p o a 存在着前面提到过的种种不足之处，在它得到广泛应用的同时，各国、各 公司的研究人员已经在努力寻找一种更为高效的i p o a 技术了。 1 4 。2 t o s h i b a 的信元交换路由器技术( c s r ) 东芝公司首先具体描述了一种标记交换的方案，即c s r ( c e l ls w i t c h i n gr o u t e r ) 技术。 该方案首先提出了将a t m 交换结构置于l p 协议( 如l p 路由协议和r s v p 协议) 而不是a t m 协议( 如q 2 9 3 1 ) 的控制之下的思想。籍此，该方案将可以完全取消a t m 信令与复杂的地 址映射过程，而且c s r 声称c s r 网络中可以同时包容a t m 交换机与c s r 交换机，而c s r 将可以取代c l p o a 中连接在l i s 之间的路由器，从而摆脱了对n h r p 的需求。 c s r 方案虽然开创了标记交换的先河，1 9 9 4 年底1 9 9 5 年初，s c r 被提交到了i e t f b o f 会议。然而，对该方案的研究工作并不深入该技术的定义也尚不清楚完善，而且至今仍未 形成实际的产品。 1 4 3 i p s i l o n 公司的i ps w i t c h i n g 虽然i p s i o n 的j ps w i t c h i n g 技术与c s r 在技术上有许多相似之处，但不同的是，它形 成了产品并进行了有效的市场推广。该方案产生于1 9 9 6 年，该技术产生的动机是： 在一部设备上实现a t m 交换机的性能与路由器的功能。 l p 是居于统治地位的第三层协议，而目前的问题主要是路由器速度太慢，我们所需要的 实际上是更快的路由器而不是a t m 交换机。 a t m 与i p 之间的映射过于繁索，故而最好是完全不用a t m 的控制协议。 该技术已经形成了r f c 文件，但未形成标准。该方案的突出贡献是描述了种简单的 交换控制协议( g s m p ) 。该协议只要对交换机加上一个外部控制器，就可以将任何a t m 交 换机变为l p 交换机。 1 4 4 c i s c o 公司的t a gs w i t c h i n g i p s i l o n 公司宣布其i ps w i t c h i n g 技术仅仅几个月之后，c i s c o 公司就公布了它的标记交 换技术即t a gs w i t c h i n g 技术。该方案与前两种技术有很大的差别。例如，它不是使用流驱 动而是控制( 拓扑) 驱动方式来建立交换机中的转发表，而且该技术将不仅限于在a t m 交 换机之上使用。 9 基于y , p l s 的流量工程 该技术亦形成了r f c 文件，然而，与i p s i l o n 公司不同，c i s c o 公司致力于将该技术形 成国际标准。接着，该技术在各方面的问题都形成了r f c 文件t c i s c o 公司的努力最终导致 了i e t fm p l s 工作组的形成。 1 4 5 i b m 公司的a r i s 与n o r t e l 公司的v n s 在c i s c o 公司宣布其技术之后，很快i b m 公司也推出了它们的标记交换技术a r i s ( a g g r e g a t e r o u t e b a s e di ps w i t c h i n g ) ，并且也形成了r f c 文件。a r i s 与t a gs w i t c h i n g 十分相似，但也有很多重要区别。 n o r t e l 也推出了它的标记交换产品v n s 。 1 4 6 m p l s 标准化工作 在上述几个公司的支持下，1 9 9 6 年，i e t f 就m p l s 召开了b o f ( b i r do faf e a t h e r ) 会议，该会议是i e t f 有史以来开得最成功的会议之一。接下来，顺理成章地，m p l s 进入 了标准化进程，虽然有人主张若有了足够快的路由器，该技术就没有必要了，但现实毕竞是 还没有令人足够满意的路由器出现，而且，目前存在的几种不同的标记交换技术也是迫切需 要进行标准化的。 1 9 9 7 年初，m p l s 的章程( c h a r t e r ) 得以通过。 1 9 9 7 年4 月，m p l s 工作组召开了第一次会议。 1 9 9 7 年1 1 月，形成了m p l s 的框架( f r a m e w o r k ) 文件。 1 9 9 8 年7 月，形成m p l s 结构( a r c h i t e c t u r e ) 文件。 1 9 9 8 年8 月，9 月间，形成关于m p l s 标记分布协议( l d p ) ，标记编码，a t m 应用等 等十几个i n t e m e t 文件，m p l s 已经基本成形。 预计1 9 9 9 年内将最终形成i e t f 关于m p l s 的标准，并提出r f c 文件。 1 0 基于m p l s 的流量工程 第二章m p l s 的框架结构与特性 2 1 关于交换和路由 交换和路由的概念定义大概来源于计算机网和电信网的差异，路油器最初被定义为在网 络层完成互联的，承担协议转换任务的主机，交换机则不做协议转换工作，而仅仅是转发同 一协议中的数据包。现实的问题是大部分计算机网络现在都运行t c p i p 协议，这对于交换 机来说是不成问题的，但路由器能否继续此定义就需要考虑了。一个在网络层运行纯l p ，在 以下层使用多种数据链路和物理协议的路由器是否能被称为j p 交换机? 这只是一个命名问 题，一般地说，能完成线速转发任务的设备可称交换机。以次标准衡量，a t m 交换机就是名 副其实的第三层交换机，而高速i p 路由器也可称为l p 交换机。 2 。2 m p l s 的基本原理 m p l s 是下一代网络处理流量传送和控制的基本结构。基于一个简单的思想，将路由和 转发两个动作在时间和空间上分离，m p l s 实现了对i p ( 包括其他网络层协议，在此不予讨 论) 的线速递交，这一能力在当前的硬件设计一制造水平上若基于传统的路由一转发一次完 成机制是昂贵甚至无法实现的。探究m p l s 的起源和运行机制是一件有趣的工作，在此我无 法放弃这种乐趣。 在计算机网络的历史上，不可靠的信道和低速的路由主机是一个默认的前提，从而分布 式，高冗余度的网络通信协议占据了主导地位，当信道越来越快，路由主机的处理能力也越 来越快时，历史的成功反而成为一种负担。同时，处理能力以摩尔定律增长，每1 8 个月翻 一番，而信道带宽的增长速度确是以1 0 位底的。t b 级主干信道即将成为现实。我们面临的 问题是无法有效地利用廉价的带宽】，或者说网络的成本大部分花费在了路由，接口和转发上。 m p l s 的出现无疑是网络史上的又一次革命，再次证明了简单，高效，低成本是计算机 科学的决定因素。同时m p l s 模糊了连接于无连接两种数据转发模式的界限，试图综合两者 的优点来实现性能晟优，成本最低的网络。在此，形式化地分析一下m p l s 的原理是非常有 必要的。 1 1 基于m p l s 的流量工程 首先，m p l s 起源于c i s c o 的t a gs w i t c h i p s i l i o n 的i ps w i t c h ，i b m 的t o s h i b a 的等多 种第三层交换协议试验。其最初的目的是为其公司的路由一交换机提供第三层线速交换能 力。其技术路线是利用标记方法为l p 包确定其路由器间的路由，。从而实现高速率交换。当 试验性技术日益成熟，标准化的要求也就提上了日程，其结果就是m p l s 。但m p l s 也许不 仅仅是一个巧妙的手段而已，以全局的观点来看，m p l s 改变了整个计算机网络的基础。 计算机网络是以相连的计算机为雏形开始出现的，这一思路在整个网络中仍像幽灵一般 存在着。以主机为核心，将信道视为主机间连线的概念直接导致了网络的黑箱模型，许许多 多的研究努力花费在向黑箱提供输出，分析其输出从而得到结论。与之相对应的，电信网络 则是以网络及其连接其上的终端设备为基本构架，两种不同的思维方式往往决定了许同结论 的不同解释。 m p l s 也许是计算机网络与电信网络结合的产物。通过标记这一创造性的思想，许多相 矛盾的要求在这一体系上得以实现。 2 。2 1 简单地描述一下m p l s 的工作原理 标记交换转发机制在a t m 中已经有了成功的应用，但是服务于一个面向连接的网络层 服务访问点。更进一步地，将标记交换转发应用于以i p 为代表的第三层转发一路由，就有了 m p l s ，标记交换转发是实现高性能，价格比的必然途径，同时也为网络层带来了充分的可扩 展性和灵活性，无论是更大规模的路由选择还是更新的路由算法，都可以在已有的网络结构 中方便地加以扩展，从而实现下一代互联网的基本要求运行一个比现有网络大1 0 0 倍， 复杂1 0 0 0 倍的网络。 2 2 2 m p l s 的核心机制： 1 )对于语义明确的流标记，即是将特定的数据流用标记加以识别，数据流( 注 意不是连接) 总是与一定的标记相联系的，标记决定了对该数据流的处理方式。 2 )转发是基于标记的，标记可以起到索引的作用，简单地完成定位出口的功 能。同时将标记切换为下一跳的标记，完成下一次转发的准备工作。 3 )标记分配与传播实限于相邻( 物理或逻辑) 的路由主机之间的，完全是分 布式的运行机制。 1 2 基于 l p l s 的流量工程 2 2 3 形式化地表述一个运行m p l s 和运行传统i p 路 由以及a t m 的网络之间的区别， 对于单一数据流s ，s = ( p 1 ，p 2 ，p 3 p n ) ， p 为单个数据包，p = a d ，a s l 】，a d 为目的地址，a s 为源地址，l 为有效负载 假设s 通过网络n 传送之目的主机h d 其起始主机为h s ，则有以下三种情况 2 2 3 1 通过传统i p 网 s 是不可见的集合，每个独立数据包p i 以代价c i 通过n c i = c i l - i - c i 24 - c i 3 + c 拥c 拥为每一跳代价 c i m c r , 4 - c f , m 所以c = c i + c 2 + a + c n = c i j 近似地，c i = c j ( i ，j = i kn ) mm c = ”g zn ( c k + c r ) g 为对某特定p i 的代价取样 j t lj = l 2 2 。3 2 通过a t m 网， s 是可见的数据集，或称虚连接 c = d + c i + c d c ，是建立连接的代价，c d 是撤除连接的代价 c ia c ， c d z c o c i 。c r ：+ c f c o c s 动作的传播) c f c j ? f m c * ( c r t + c f ，) + o l + o ( 假设交换机是线速的，即内部操作不影响 1 3 基 3 pm p l s 的流量工程 2 2 3 3 通过m p l s s 是可见的数据集，或称等价转发类 c = c f c i = c f i = i c z d ， i t i 由此可见，m p l s 的效率大大高于( 就单个数据流来说) 传统j p 路由和a t m 网，当然 这里只考虑单个数据流的情况，从网络的整体运行代价来看，有以下分析： 2 2 3 4 通过传统i p 网 若s 以p ( s ) 的概率被传送，则网络总代价c f z s i p ( s i ) + c r c k 是路由协议开销 2 2 3 5 通过a t m 和m p l s 同样s 以p ( s ) 的概率被传送 则c n z s f p ( s o + c r + c l c r 是路由协议开销 ， c c 是标记分配和传播开销 以上( ，c l 式与网络复杂度的二次方成正比的，即是在大范围，低数量的网络结构中， 传统i p 的效率是高的，如i po v e rx 2 5 然而，现代的互联网络是以多层次，高效率为特征， 在这样的环境中，以一定的代价建立标记表是非常节省数据包的转发代价的，自然m p l s 成 为下一代网络的核心机制。 2 3 m p l s 提供了以下优异的特性( 【1 】) 2 3 1 简单，高速，低成本的转发 定长的标记为简化转发硬件逻辑，快速查找标记表以得到下一跳出口和后继标记提供了 1 4 基于m p l s 的流量工程 可能，传统的i p 路由器基于最长可能匹配来决定路由表的入口，难以建立有效的索引和查找 机制，限制了转发速度的提高，现有的超级路由器可以支持o c 4 8 机制的线速转发，但其使 用仅限于主干网的边界上，基于标记技术可以构建更为便宜但高性能的路由设备 2 3 2 有效的可控显式路由 现有的l p 协议虽然规定了显式路由( 或称源端路由) ，但运行中的网络是不支持此功能 的。m p l s 对路由的预定义和发布使显式路由成为可能。 q o s 要求在满足资源限制的前提下决定数据流的接受和转发，这样数据流的路由就由网 络资源可用性，当前网络负载分布和对将来负载的预测等多个因素所决定，这一机制需要源 端获取关于该解的路由并规定所接受数据流严格按照已选定的路由转发。m p l s 同样为q o s 提供了可能。 2 3 3 提供负载与信道间灵活的分配机制 m p l s 可以将i p 数据包以不同的方式分配至等价转发类上，从而提供了对逻辑信道的控 制能力，由此可以提供如区别服务，q o s 等细分服务方式，丰富了i s p 的营运手段和产品。 2 3 4 功能分解 m p l s 将路由与转发相分离的机制为网络设备的功能模块化，分布化打下了基础，通过 将复杂的路由信息搜集，路由分配，服务能力计算，分配，服务请求评估，决策等功能防置 于靠近用户的地名，将网络核心交换能力最大限度地发挥。我们可以构造一个以信道资源最 大价值化为目标的主干网络，即信道不仅仅是承载尽可能多的数据，同时要选择价值尽可能 高的数据，网络的承载能力得以清晰地被测量和监控，位于边界的服务分配设备通过标记来 定义相互间的多层次，多参数的逻辑信道，从而满足信道利用和分配合理，高效的要求。 2 3 5 流量工程支持 m p l s 的显式路由和多流量映射机制为流量工程提供了良好的支持。在现在运行的基于 a t m 的主干网上，人工配置的p v c 作为路由器问的信道并且人手调速p v c 的路由以平衡各 物理信道上的负载是惯用的做法。基于m p l s 的流量工程将可以标记网络中任何一条数据流， 1 5 i k - ；q fm p l s 的流量工程 并以显式的管理手段控制其路由，从而以更方便的手段实现以往基于i p 转发无法完成的流量 工程操作。 流量工程的实现方式也有多种，本文以下将讨论一种基于边界流量聚集，集中控制，分 布动作的流量工程模型 1 6 基于m p l s 的流量工程 第三章基于m p l s 的流量工程模型 3 。1 流量工程对m p l s 功能的要求 在讨论了现阶段的互联网上的流量工程之后，我们可以讨论一下在互联网的核心机 制转换为m p l s 之后，继续实施流量工程对m p l s 的设计所提出的要求。两个讨论的假设前 提是大范围的网络分布和手工与自动相结合的流量工程调节手段。 3 1 1 对流量聚集的一系列概念的支持 对于流量工程来说，从最基本的数据流到物理信道之间有一系列的中间层次，通过中间 层次的映射组合来完成调节流量的工作。 主豇( 数据流) 是简单地对于端系统可见的数据包集台 流聚集是对于流量工程实体可见的多个流组合成的集合 l s p 是对于m p l s 路由实体可见的通过一系列l a b e lc h a i n 所标识的数据转发路径 信道是对于数据链路实体可见的点到点的数据通道 物理信道是对于物理实体可见的点到点的光媒质连接 它们之间的关系如下图所示： 司) 对于m p l s 的设计来说要支持流量工程就是对上述的层次关系在其控制信息中有所表 达，或者说有一组属性来描述这些层次，其中，流，流聚集，l s p 是m p l s 以上的实体，信 1 7 基于m p l s 的流量工程 道和物理信道是m p l s 以下的实体，两个不同的方向需要不同的处理方法。 应用系统 流 流聚集 l s r 信道 物理信道 可见，支持流量工程的m p l s 设计需要至少在流聚集这层次上分配f e c ，赋以相应的 a b e l 。 3 。1 2 m p l s 对流量聚集的数据结构的支持 m p l s 上实现流量工程时至少需要以下属性的存储 对于流聚集而言： 流量特性参数 路由选择参数 优先权参数 抢占权参数 故障恢复参数 流量策略参数 对于信道而言： 最大运载能力参数 可复用能力参数 资源分配策略下的分类参数 有了对流聚集和信道资源两方面的参数描述，m p l s 才可以通过分配l s r 和f e c 的 方式来调节不同资源上的负载情况 1 8 , l - 3 p 押l s 的流量工程 由上图中，m p l s 对网络负载的动态调节是改变f e c 到l s r 的映射来实现的，这就提 出了一个关键的特性要求 2 m p l s 路由动态调整与实时响应 m p l s 可以在对网络拓扑和各信道承载能力估计的基础上，按照网络运行策略顸制多个 流量映射方案，当网络运行状态的改变触发了某个条件时，在流量聚集点处改变f e c 到l s r 的映射，将一部分流聚集实时地重路由到新的信道上去，可以主动，实时地优化网络的负载 分配情况，例如以下的动作序列： 1 9 基于m p l s 的濂量工程 e f 上图是一个常见的网络拓扑，在流量聚集点a 和流量分解点h 之间通过网络相连， m p l s 预置了l s ra b c g h 和a b e f g h ，在正常运行时，a 点有一个流聚集t 路由经过 a b c d g h ，此时的操作是 l p 数据包p 被a 接收 a 分析其目的地址，可以通过b 点 a 找出a 到b 的流聚集t a 找出t 所对应的f e cf 1 ，及其l a b e ll 1 a 将l 1 压入p 的l a b e l 栈中 转发p 至b c d g h h 转发p 至其目的地址 若c d 段被外来流量占用，使c d 段过载，流量管理系统向所有通过c d 段的流聚集发 出通知 t 获知此通知 a 将t 重映射至l s r ，a b e f g h a 找出对应l a b e ll 2 a 继续以l 2 压入p 进行转发 可见流量调整的工作在分布，实时的前提下以极小的代价完成了 3 1 3 m p l s 必须支持扩充条件限制下的路由算法 对r - m p l s 体系来说，l s r 的建立需要路由信息，流聚集的建立也需要路由信息，在一 个网络上同时运行两个路由协议和算法时不经济的，理想的情况是对原有的完全基于拓扑的 2 0 基于m p l s 的流量工程 路由协议进行扩充，以支持新的流量特征。o s p f 就是一个很好的平台，这里我们将集中于 i g p 协议类型的讨论。 在路由算法中加上流量限制，以禁止那些已经或可能过载的信道参加路竞争，是建立条 件路由算法的基本思路，在运行传统的o s p f 算法之前对网络拓扑信息进行一次过滤，可以 完成上述的功能，但不得不为了l s r 和流聚集运行两次同样的算法，基于不同的输入集。这 里，我们将会提出一种同时给出两个结果的路由算法。 3 1 4 o s p f 简述 o s p f 的路由主机向整个网络拓扑中的其它全部主机发送自己的链路信息，包括连同性， 相邻主机名。耗费参数等，这一操作在主机初始化，复位，连接状态发生变化时都会发生。 每台运行o s p f 的主机都可以获取整个自治域a s 的配置拓扑，并且在本地计算全部目 标的最短路径，这里所使用的算法是不必统一的，但d i j k s t r a 算法及他们的改进常常被使用。 算法的结果可以用来构造路由表，列出对任一目标的下跳转发接口。 o s p f 使用f l o o d i n g 技术来分发路由信息，保证分组能最快地到达所有连通的路由主机 o s p f 路由器的本地数据库存贮了已知的拓扑信息，很容易想到是一个由向图，图的顶 点包含两类： 路由器 网络，由分为中间网络和终端网络，中间网络可以传送非本网络内部生成或接受的流量， 而终端网络则不能。 点对点链路链接了两个路由器 路由器连接到网络的链路 到其它a s 的连接用终端网络来表示 下是一个典型的o s p f 自治系统的表示，链路的耗费以弧上的数字来表示 2 1 基于m p l s 的流量工程 n 7 n 2 卜n 8 显然，由于路由器与网络的相连是直接的，从网络到路由器的耗费为零。 通过d i j k s t r a 算法得到的路由表可以计算出最小耗费路经，o s p f 已经定义的不同t o s 耗费路径包括： t o s 0 ：正常，一般是以h o p 数确定的 t o s 2 ：最小经济成本 t o s 4 ：最大可靠性 t o s 8 ：最大吞吐率，以接口速率的倒数为耗费 t o s l 6 ：最小延迟，以信道传输延时加上排队延时为耗费 o s p f 运行的结果是五个不同的路由表，由i p 数据报的t o s 性质来决定使用哪一个路 由表进行转发。 通过对o s p f 进一步扩充，使流量参数也成为路由运算的因素之一，可以完成对流聚集 的路由任务 基于m p l s 的流量工程 3 1 5 对耗费的扩充定义： 定义链路的即时占用率y 即时流量s y2 丽丽 s 是由配置决定的，为某信道的额定数据流量 f = t ( t ) - t ( t - a t ) ，t ( 1 ) 是对通过此信道，的流量积分 ， 简单地计算最小链路占用率路由是不合适的，即是对路径r i ，r 2 r n 计算其总占用率 毫无意义，我们在此引入参数k ， k ：上 7 m 、 其中7 是链路的平均占用率 z 是一常数，1 z 2 ， y m a x y ，y ：，k 。) ，即所经链路的最大占有率值，k 的有效性取决于对2 的取 值，这是一个在网络运行实验中取的经验值 3 2 m p l s 为流量工程提供工具 1 显式源路由 2 对同一路由上流量的可区分性 3 动态路由调整的低开销 3 3 建立的模型概述 3 3 1 术语与缩写 1 )流量聚集点：网络上的节点v 由两个或更多的数据流在v 合并，数据流合 并后流经同样的路由，称为流聚集。 2 )数据流：一组数据包，由于具有某些共同的性质而被看作同一处理类，如 2 3 墓于m p l s 的流量工程 具有相同的源目的地址，相同的拥护，相同的应用系统类型。 3 )流量分解点：网络上的节点v ，一个流聚集在v 分解为其包含的数据流， 并转发至不同的子网。 4 )流聚集：一组数据包，包含了组成该聚集的数据流的全部数据包，并作为 在m p l s 交换层中的基本单位被传送，流聚集从流量聚集点开始，到流量分解点结 束。 5 1流量聚集边缘化：将关于流量的控制逻辑集中于主干网边缘的核心路由器 上，使交换核心的任务局限于高速递交数据和控制信息。 3 3 2 模型分为两个部分 3 3 2 1 服务接口 服务接口完成对用户流量的聚集过程，将用户流量按以下标准分类，并标记为相应的流 聚集分类标识。分类的标准是根据服务提供商的商业策略来制订的，在此抽象为映射函数f s ， 常见的分类标准可以是： 目标地址：显然，发往同一目的地的数据可以在一个流聚集中传送，在此地址信息的分 解粒度可根据主干网的拓扑来决定。 用户等级：不同的用户等级可以得到不同的服务质量，对于服务产品的丰富化言，各种 性价比因素都会影响映射的方法。 应用系统：对于短时突发流量的应用和长时平稳流量的应用系统可以分离其传送信道， 从而避免不良影响，对于其协议数据包和控制信息包也可以分开传送。 服务接口：将流量分类并映射至流聚集上之后，对各个流聚集的实时流量统计数值进行 计算，得到关于此流量聚集的特性参数，参数一般应包括以下量： 平均流量速率 最大突发速率 最大突发数据量 最大突发间隔 通过这些参数可以估计用户流量的实时要求。 服务接e 1 预定义了每种用户服务类的流量参数，同时根据应用协议类别对流量规定了附 2 4 基于m p l s 的采 工程 加特征量 3 3 2 2 运载核心 运载核心是流量工程的关键部分，它将流聚集映射至m p l s 的l a b e l 集上，同时根据流量 负载情况调整已定义的l s p ，增减某些通路上的运载能力，达到调节网络运行状态的功能。 1 流聚集的建立 2 l s r 的建立 3 l s r 的占用率实时计算，算法 4 流聚集到l s r 的映射算法 3 3 2 2 1 在流量聚集点和流量分解点之间建立流聚集的步骤 流量分解点发起流聚集的建立 流量分解点计算可接受的输入流 流量分解点基于o s p f 计算到流量聚集点的路径 流量分解点通知流量分解点准备此流聚集 流量分解点根据扩充的o s p f 计算可用l s r 流量分解点绑定本地l a b e l 表，在此l s r 上送出流聚集建立确认信息 在建立好流聚集之后，流量聚集点就可以将符合流量分解点要求的数据映射至此流聚集 上发送 流聚集是与网络向应用系统提供的服务种类紧密相关的，服务接口预定义的流类型直接 作用于流聚集的定义，至少以下的区分是必需的： 1 连接与非连接类 2 时间敏感与可靠敏感类 3 拥塞敏感类与不敏感类 等等 流聚集在流量聚集点和流量分解点上登记。流聚集所需记的信息由流聚集属性定义决 定，见第节 基于m p l s 的流量工程 3 。3 2 2 2 l s r 的建立 为了支持流量工程，要求l s r 的建立是m p l s 所支持的各种l s r 建立方法中基于拓扑 的l s r 预置方法。 在i p 层运行着b g p 或o s p f 的网络中，建立其i p 路由表的同时也就获取了其整个网络 的拓扑结构，在此拓扑结构上由流量输入点或网络出口发起建立基于最小生成树的l s r 预置 路径，为进一步的信道使用管理做好准备。 这里使用的最小生成树算法是基于静态拓扑的，由于现代网络的可靠性大大提高，静态 路由可以完成最佳性能消耗比的选路功能。 这一生成树算法可以基于b f s b f s 先处理完同层次上的所有顶点再处理下一层次的顶点，处理过程中，图中的顶点被 划为不同的层次。我仍需要的根结点即网络出口结点设为层次0 ，相邻于层次0 ( 只有个 根结点r ) 的所有节点都计为层次1 ，把它们计为v 1 1 , v 1 2 ，以此类推将第1 层的结点计 为v i i ，v i 2 ，v i r 。在处理完第1 层结点后，则处理与之相邻但不属于第0 i 1 层的节点，这些 结点按下式定义： 3 v 。f j 昙，使屿矿。相邻，而且v f ，v 茌第”层 反复以上过程直至不再有满足条件的节点存在，此的 表示了此生成树的最长分支。 以下面的有向图为例，讨论b f s 的运行过程： 45 6 b f s 算法的形式化定义是： 输入连通图g ，顶点序次为1 ，2 ，3 ，输出生成树t 1 s = t 1 ) tt = 0 2 对s 中每个顶点x ，对s 的g 中相邻点排序，每个相邻点y a ) 检查边r , x y ) 是否在t 中 - 基 - 3 pm p l s 的流量- r 莉j b )检查加入边( x ，y ) 是否会在t 中造成回路 若否，则将( x ，y ) 加入t 中， 若所有的y 都没有完成b 操作，则算法结束 3 将新加入到t 中的顶点附加于s 中顶点之后，转2 这个算法产生以1 位根的生成树，对于i - i 季1 的操作在六步之后结束，六步的中间结果分 别是： 1 s = 1 )t