（通信与信息系统专业论文）动态qos控制架构下的路由算法研究与仿真分析.pdf

摘要 动态q o s 控制架构下的路由算法研究与仿真分析 通信与信息系统 徐萌 胡乐明教授 摘要 随着i n t c r n c t 的高速发展，各种各样的实时多媒体业务呈爆炸性增长。各种新业 务对网络提出了低时延、低抖动、低丢包率等服务质量( q o s ) 要求。最迫切需要 解决的问题是如何保障i n t e r n e t 的服务质量。 为了满足服务质量的要求，因特网工程任务组提出了一些体系结构和机制，如 综合业务模型，区分业务模型、多协议标签交换、流量工程以及q o s 路由。单独某 一种体系结构或机制并不能有效地满足q o s 的需要，因此我们设计了一个动态q o s 控制的架构，它融合了各模型的优点，基于d i f f s g r v 和m p l s 网络，设置一个q o s 服务器集中控制和管理网络资源的分配，能够为业务提供有效的q o s 保证。本文中 给出了该体系结构的设计思想和工作流程，并在仿真环境下编程实现了q o ss e r v e r 架构。 q o s 路由是解决q o s 问题的一项关键技术，而且o o ss e r v e r 中最核心的部分是 路由计算，所以选择合适的q o s 路由算法很重要。本文对q o s 路由算法进行了研究， 分析了现有的o o s 单播路由算法存在的问题，重点研究了一种单混合参数度量的路 由算法m r b h p ，并在它的基础上提出了改进，给出了改进的m r b h p p l u s 算法的具 体描述和性能分析。改进后的m r b h p p l u s 算法使用链路的可用带宽和传播时延进行 路由计算，能够根据网络资源的变化动态计算路由，适合动态o o s 控制的需要，并 且能够反映出路由器之间物理距离对传输的影响，对实际应用很有意义。 在c 语言环境下分析和比较了d i j k s t r a 算法与m r b h p p l u s 算法的异同之后，我 将几种算法嵌入到q o ss e r v e r 架构的路由计算模块中，通过设置不同的流量模型和 网络模型，对m r b h p 算法和m r b h p p l u s 算法进行了大量的仿真分析与研究。结果 衷明，m r b h p p l u s 算法具有动态计算路由和计算复杂度低的优点，并且在q o ss e r v e r 的d i f f s e r v 架构下能够为业务提供分级的带宽保证，是一个实用的q o s 路由算法。 通过仿真分析，还对m r b h p p l u s 算法的进一步完善提出了改进方向。 关键词：d i f f s e r v ，m p l s ，q o s 路由，动态q o s 控制，m r b h p p l u s 算法 a b s t r a c t r e s e a r c ha n ds i m u l a t i o n - b a s e da n a l y s i so fr o u t i n ga l g o r i t h m u n d e rd y n a m i cq o sc o n t r o la r c h i t e c t u r e c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m x u m e n g p r o f e s s o rh ul e m i n g a bs t r a c t w i t ht h ef a s td e v e l o p m e n to f n t e r n e t ，v a r i o u sr e a l t i m em u l t i m e d i aa p p l i c a t i o n sg r o w e x p l o s i v e l y v a r i o u sk i n d so f e ws e r v i c e sb r i n g f o r w a r dt h ed e m a n d sf o rq u a l i t yo f s e r v i c e ( q o s ) ，w h i c hi n c l u d e sl o wd e l a y , l o wj i t t e ra n dl o wp a c k e tl o s sr a t i o ，e t c t h em o s t u r g e n tp r o b l e mt ob es o l v e di sh o w t og u a r a n t e et h e0 0 so fi n t e r n e t i no r d e rt om e e tt h ed e m a n d sf o rq o s ，i e t fh a sp r o p o s e ds e v e r a la r c h i t e c t u r e sa n d m e c h a n i s m ，s u c ha si n t e g r a t e ds e r v i c e sa r c h i t e c t u r e ，d i f f e r e n t i a t e ds e r v i c e sa r c h i t e c t u r e ， m u l t i - p r o t o c o l l a b e l s w i t c h i n g ，t r a f f i ce n g i n e e r i n g a n d0 0 sr o u t i n g a n yo ft h e s e a r c h i t e c t u r e so rm e c h a n i s ma l o r ec a l l tm e e tt h ed e m a n d so fq o se f f e c t i v e l y , t h u sw e d e s i g na na r c h i t e c t u r et oi m p l e m e n td y n a m i cq o sc o n t r o l , w h i c hm e r g e st h ea d v a n t a g e so f a l lt h em e c h a n i s m t h ea r c h i t e c t u r eb a s e do nd i f - i s c r ya n dm p l sn e t w o r k b ys e t t i n gu pa q o ss e r v e rt oc e n t r a l i z e dc o n t r o la n dm a n a g et h en e t w o r kr e s o u r c e s ，i tc a no f f e re f f e c t i v e q o sg u a r a n t e ef o rs e r v i c e s i nt h et h e s i s ，w ep r o v i d et h ed e s i g np h i l o s o p h ya n dw o r kf l o w o ft h i sa r c h i t e c t u r e 。a n di m p l e m e n tt h eq o ss e r v e ra r c h i t e c t u r eb yp r o g r a m m i n gi nt h e o p n e ts i m u l a t i o ne n v i r o n m e n t 0 0 s b a s e dr o u t i n gi sak e yt e c h n o l o g yo fs o l v i n gq o sp r o b l e m , a n di t st h en u c l e a r p a r to fq o ss e r v e r , s oi t sv e r yi m p o r t a n tt oc h o o s eas u i t a b l er o u t i n ga l g o r i t h m t h i st h e s i s h a sd o n er e s e a r c ho nq o sr o u t i n ga l g o r i t h m s i th a sa n a l y s e dt h ep r o b l e mo ft h ee x i s t i n g q o su n i c a s tr o u t i n ga l g o r i t h m ，a n dh a sf o c u s e do n ar o u t i n g a l g o r i t h m b a s e do n s i n g l e - m i x e dm e t r i c ，w h i c hn a m ei sm r b h p w eh a v ee n h a n c e dt h em r b h pa l g o r i t h m ， a n d h a v eg i v e no u tt h ec o n c r e t ed e s c r i p t i o na n dp e r f o r m a n c ea n a l y s i so ft h ee n h a n c e d a l g o r i t h mm r b h p p l u s t h em r b h p p l u sa l g o r i t h mu s e st h ea v a i l a b l eb a n d w i d t ho ft h e l i n ka n dt h ep r o p a g a t i o nd e l a yt oc a l c u l a t et h er o u t e ，a n dc a nc a l c u l a t er o u t ed y n a m i c a l l y a c c o r d i n gt ot h ec h a n g e so f t h en e t w o r kr e s o u r c e s ，s oi t ss u i t a b l ef o rt h en e e do fd y n a m i c o o sc o n t r 0 1 a st h ea l g o r i t h mc a nr e f l e c tt h ei n f l u e n c eo ft h ed i s t a n c eb e t w e e nt o u t e r st o t r a n s m i s s i o n ，i t sv e r ym e a n i n g f u lf o rp r a c t i c a la p p l i c a t i o n a f t e ra n a l y s i n ga n dc o m p a r i n gt h es i m i l a r i t i e sa n dd i f f e r e n c e sb e t w e e nd i j k s t r a r n 中山大学硕士学位论文 动态q o s 控制架构下的路由算法研究与仿真分析 a l g o r i t h ma n dm r b h p p l u sa l g o r i t h mu n d e rt h ee n v k o n m e mo fcl a n g u a g e ，w ei m b e d s e v e r a lk i n d so fa l g o r i t h m st ot h er o u t i n gc a l c u l a t i o nm o d u l eo ft h eq o ss e r v e ra r c h i t e c t u r e t h r o u g hs e t t i n gu pd i f f e r e n tt r a f f i cm o d e la n dn e t w o r km o d e l ，w ed oal o to fs i m u l a t i o na n d r e s e a r c ho nm r b h pa l g o r i t h ma n dm r b h p p l u sa l g o r i t h m t h er e s u l ti n d i c a t e st h a tt h e m r b h p p l u sa l g o r i t h mh a st h ea d v a n t a g e so fc a l c u l a t i n gr o u t ed y n a m i c a l l ya n dl o w c o m p l e x i t yi nc a l c u l a t i o n ，a n dc a no f f e rg r a d e db a n d w i d t hg u a r a n t e ef o rs e r v i c e su n d e r d i f t s e r va r c h i t e c t u r eo fq o ss e r v e r , s oi ti sap r a c t i c a lq o sr o u t i n ga l g o r i t h m t h r o u g h s i m u l a t i o na n da n a l y s i s ，w eh a v ea l s op r o p o s e dt h ep o s s i b l ew a y sf o rf u r t h e re n h a n c e m e n t o ft h em r b h p p l u sa l g o r i t h m k e yw o r d s ：d i f f e r e n t i a t e ds e r v i c e s ，m p l s ，q o sr o u t i n g ，d y n a m i cq o sc o n t r o l ， m r b h p p l u sa l g o r i t h m 图表目录 图2 - l 图2 2 图3 - 1 表3 - 1 图3 2 图3 3 图3 4 图3 5 图3 - 6 图3 7 图3 8 图3 9 图4 ，1 图4 - 2 图4 3 图4 4 图4 5 图4 _ 6 图禾7 图乖8 图4 - 9 图4 - 1 0 图4 1 1 图4 - 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 - 1 7 图4 - 1 8 图表目录 o o ss e r v e r 模型8 o o s 控制工作流程9 三个节点的示例网络2 5 不同业务优先级的带宽2 5 5 个节点的网络拓扑2 6 m r b h p 算法运行结果2 7 4 个节点的网络拓扑2 8 d i j k s t r a 算法计算的路由。2 8 m r b h p 算法计算的路由2 8 6 个节点的网络拓扑2 9 d i j k s t r a 算法计算的路由2 9 m r b h p 算法计算的路由- 3 0 o p n e t1 0 0 a 界面3 3 q o ss e r v e r 的进程模型3 5 r s v p 进程模型3 6 o o ss e r v e r 配置窗口3 6 视频会议业务的属性设置” 业务特性的配置3 8 f e c 的设置3 9 t r a f f i ct r u n k 的设置3 9 入口边缘路由器上m p l s 参数的设置4 0 在o o sc o i l f i g 模块中配置队列4 0 4 个节点鱼形网模型4 2 输入的阶梯状流量4 2 输出流量对比4 3 业务端到端时延对比“ 时延局部放大对比“ 4 个节点的全连接网络4 5 输入流量：3 2 m 4 5 输出流量对比4 6 中山大学硕士学位论文 动态o o s 控制架构下的路由算法研究与仿真分析 图4 - 1 9 流量较大情况下端到端时延对比。4 6 图4 2 0 负载较轻时的时延对比4 7 图4 2 18 个节点的网络模型4 8 表4 - 1q o ss e r v e r 采集的链路时延4 9 图4 2 2 输入的阶梯流量4 9 图4 - 2 3 流量传输的路径和顺序5 0 图4 2 4 输出的流量5 0 图4 2 5 端到端时延5 1 图4 - 2 6 进行准入控制后的流量5 1 图4 2 7 进行准入控制后的端到端时延。5 2 图4 2 8 6 个节点网络模型5 3 图4 - 2 9 输入的阶梯状流量5 3 图4 - 3 0 3 种算法输出流量的大小5 4 图4 - 3 1 端到端时延及局部放大对比一5 4 图4 3 2 输入的流量( 阶梯状) 5 6 图4 - 3 3 用带宽和带宽平方分别进行计算后选择的路由5 6 图4 - 3 4 b e i j i n g - - t i a n j i n 链路的流量5 7 图4 3 5m r b i - i p p l u s 算法和带宽加权后的算法时延对比5 8 v i 第1 章绪论 第1 章绪论 1 1 论文研究的背景和意义 近年来，随着i n t e r n e t 的高速增长和快速普及，网络同人们的生活和工作已经 密切相关。与此同时，i p 业务也得到了快速增长和多样化，新业务层出不穷。i p 电 话、视频会议、远程教学、网上电子商务、可视电话及未来3 g 的无线应用等的开 展，对业务流的传输提出了低时延、低抖动、低丢包率等技术要求。同时，用户对 不同的分布式多媒体应用有着不同的服务质量要求。丢失率、带宽、端到端时延、 时延抖动等对于应用业务是至关重要的；文件传输业务要求分组的丢失率尽可能低， 而传输时延不是关键；实时多媒体业务则注重时延和时延抖动。这就要求网络能区 别对待各种业务，并对其提供不同的服务质量【1 1 。 由于各种应用具有各自的流量参数特性和不同的服务质量要求，i p 协议固有的 无连接特性和传统i p 网络尽力而为的传递方式已远远不能适应新的需要。传统互联 网不但无法向用户提供有效的服务质量保障，也不能实现网络资源的有效监控和管 理，这种状况严重阻碍了互联网向纵深方向发展。另一方面，对于众多网络服务提 供商和运营商而言，单一雷同的服务产品使得竞争日益激烈并大大影响了其利润率。 因此，最迫切需要解决的问题是如何保障i n t e r n e t 的服务质量( q u a l i t yo f s e r v i c e s ，q o s ) ，它的实现有三个主要的意义： 1 满足对q o s 有严格要求的业务和用户的需求； 2 通过q o s 研究，有助于提高网络效率，降低网络成本； 3 运营商可以通过q o s 机制，按照不同用户对服务质量的不同要求，提供多 种有区别的服务，提高用户的满意度，同时提高网络运营商的收益l 2 1 。 i pq o s 意指i p 分组流通过一个或多个网络时所表现出来的性能属性，它通常 可以用如下这些可度量的参数来描述： 业务可用性：指用户能够使用业务的时间占业务全部工作时间的百分数。在 连续5 分钟内，如果一个i p 网所提供业务的丢包率5 ，则认为该时间段 是可用的，否则是不可用的。 时延( l a t e n c y ) ：也称为延迟，指数据包从源端到达目的端所经过的时间。 该项指标对于语音等实时业务影响较大。 1 中山大学硕士学位论文 动态q o s 控制架构下的路由算法研究与仿真分析 时延抖动( j i t t e r ) ：其定义有多种，其中之一是在一个测量周期之内，分组 时延的最大值减去最小值。 吞吐量：指单位时间内传送的分组或b i t 数。 丢包率：丢弃的分组数占总分组的百分比。丢包主要是由网络拥塞引起的， 会造成语音断续不清楚，图像失真、出现马赛克。严重的丢包会造成传输中 断。 本论文的研究和仿真结果将对这些q o s 参数进行分析和比较。 服务质量的研究重点是如何提高网络提供q o s 保证的能力，而最终研究的目标 是保证用户对q o s 的要求。本论文中的q o s 是指网络在传输业务流时，为业务分 组提供的一系列服务，并通过这些服务满足流量传送的质量要求。 近十年来，针对i p 服务质量，研究人员提出了一系列理论和解决方案，包括流 量工程、m p l s 、i n t s e r v 、d i f f s e r v 、q o s 路由等各种q o s 技术和机制。各种方案都 有各自的优缺点。各设备厂商也已实现了一系列q o s 机制。但是目前的实现还存在 一些缺陷。这些缺陷表现在： 各种q o s 机制只能实现静态配置，无法适应网络流量的动态变化； 现有的q o s 机制还无法充分利用已有的网络信息，比如网络拓扑、链路状 态和链路利用率等信息； 现有网络基本上采用i s - i s 、o s p f 、b g p 等路由协议，进行路由计算时没 有考虑流量传送的时延、丢包率等性能要求。q o s 路由算法还处于研究过程中， 实用的q o s 路由算法还不多见。 1 2 论文研究的目标 针对前面提到的这些问题，本论文的珏标在于设计一种能有效实现动态q o s 控 制的体系结构，在该架构下研究q o s 路由算法的特征，分析现有的各种算法，选择 合适的算法，使该算法能够动态采集网络状态信息( 如链路的可用带宽等) 并引入 路由计算：并且在o p n e t 仿真环境下实现q o ss e r v e r 架构，嵌入q o s 路由算法， 建立网络模型和流量模型，进行细致的仿真分析，验证算法的性能并加以改进。 这些功能的实现对于网络运营商是很有意义的，通过对q o s 的改善，能够更好 的满足用户和业务的需求，从而提高运营商的核心竞争力，在激烈的数据业务市场 上立于不败之地。 1 3 论文的组织结构 第1 苹绪论 全文由五章组成，具体内容安排如下： 第1 章为绪论，阐述了论文选题的背景和意义及论文的目标，列出了论文的组 织结构； 第2 章详细介绍了在现有q o s 实现机制基础上提出的动态q o s 控制体系结构， 它是基于d i f f s e r v 和m p l s 的，通过集中式控制实现q o s 保证。详细介绍了该架构 的基本框架和工作流程，提出了实现此架构的核心技术是q o s 路由。 第3 章详细介绍了q o s 路由算法。先概述了q o s 路由研究中的难点和问题， 然后介绍了q o s 路由的分类：单播、多播路由和3 种路由策略。重点研究了现有的 一些单播源路由算法，对其选择参数的问题进行了分析比较，并选择了一种以单混 合参数为路由度量的算法m r b h p 进行了研究。分析了该算法的优缺点之后，在其 基础上进行了改进，给出了改进的m r b h p p l u s 算法的流程和分析。最后比较了 m r b h p 算法和d i j k s t r a 算法异同。 第4 章为算法的仿真和分析。首先概述了o p n e t 仿真关键技术和仿真建模方 法，然后介绍了算法的仿真环境，在此基础上进行了大量的仿真研究，分析比较了 m r b h p 算法和d i j k s t r a 算法的性能，重点分析了改进的m r b h p p l u s 算法的运行结 果和性能，并将它与m r b h p 算法和d i j k s t r a 算法进行对比，总结了采用动态参数 作为度量的q o s 路由算法的优势。最后对m r b h p p l u s 算法提出了一点改进思想。 第5 章为结论部分，对论文研究工作的总结和展望。 1 4 本章小结 随着i n t e r n e t 的高速增长和快速普及，如何保障q o s 成为最迫切需要解决的问 题，在众多技术方案中，d i f f s e r v 、m p l s 与q o s 路由算法的融合是目前关于q o s 的一个重要研究方向。 本章阐述了论文选题的背景和意义，列出了论文的目标和组织结构。 第2 章动态q o s 控制的体系结构 第2 章动态q o s 控制的体系结构 2 1 现有的实现q o s 的机制 因特网工程任务组( i e t f ) 已经针对q o s 的需求提出了几个服务模型和机制， 包括综合业务模型( i n t s e r v ，i n t e g r a t e ds e r v i c e sa r c h i t e c t u r e ) r s v p 、区分业务模 型( d i f f s e r v ，d i f f e r e n t i a t e ds e r v i c e sa r c h i t e c t u r e ) 、多协议标签交换( 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 ) 、流量工程( t e ，t r a f f i ce n g i n e e r i n g ) 和q o s 路由 ( q o s r ，q o s b a s e dr o u t i n g ) 。这些解决方案都有着不同的适用范围和优缺点，以 下分别对它们做简要的介绍。 2 1 1 综合业务( i n t s e r v ) 模型 i n t s e r v 由i e t f 的i n t s e r v 工作组于1 9 9 4 年在r f c l 6 3 3 1 3 1 中提出。综合业务模 型的主要思想是模拟面向连接的电路交换提供端到端的服务质量。为此，综合业务 模型通常采用面向流的资源预留协议( r s v p ) 在流传输路径上的每个节点为流预留 并维护资源。从这个意义上说，r s v p 在i n t s e r v 架构里面是一种q o s 信令和资源管 理的协议。 综合业务模型的最大优点是能够提供端到端的服务质量保证。但是，由于i p 网 络本身是无连接的，在一个无连接网络上维护一个面向连接而且要求资源保证的通 道，不可避免的带来了很大的复杂性。因此，综合业务模型可扩展性很差，难以在 i n t e r n e t 核心网络实施，一般认为综合业务模型有可能会应用在网络的边缘上。 2 1 2 区分业务( d i f f s e r v ) 模型 为了解决i n t s e r v 的一些缺点，i e t f 在r f c 2 4 7 5 4 】中提出d i f f s e r v 体系结构， 旨在定义一种能实施i pq o s 且更易扩展的方式，以解决i n t s e r v 扩展性差的缺点。 在d i f f s e r v 里，引入了d i f f s e r v 域( d o m a i n ) 的概念，一个d i f f s e r v 域可以认 为是一个能提供d i f f s e r v 业务的予网。d i f f s e r v 域主要由一些路由器组成，并对这 些路由器进行了区分，把位于d i f f s e r v 域边缘的称为边缘路由器( e d g er o u t e r ) ， 而把d i f f s e r v 域内部的称为核心路由器( c o r e r o u t e r ) 。边缘路由器需要具有的功能 s 中山大学硕士学位论文动态q o s 控制架构下的路由算法研究与仿真分析 有：对业务流的分类( c l a s s i f y ) 、整形( s h a p i n g ) 、标记( m a r k i n g ) 和调度( s c h e d u l i n g ) 。 内部路由器需要具有的功能有分类和调度。d i f f s e r v 通过对业务流的分类、整形、 标记、调度来实现对业务q o s 一定程度上的保证。 在区分业务模型下，用户和网络管理部门之间需要预先商定服务水平协定 ( s l a ，s e r v i c el e v e la g r e e m e n t ) ，根据s l a ，用户的数据流被赋予一个特定的优 先级，当数据流通过网络时，路由器会采用相应的方式( 称为每跳行为p h b ) 来处 理流内的分组。 区分业务模型完全不同于综合业务模型，它的优点是：在区分业务模型中，业 务由特定的字段进行了分类。这样状态信息不再与业务流的数量成正比，而是与业 务分类的粒度成正比，从而大大减少了预留状态信息的数量；网络的扩展性比较好； 复杂的业务分类、策略管理以及流量整形等工作都仅限于边缘路由器加以实现。而 骨干传送网中的核心路由器只需进行简单的分类和判断工作，从而减轻了核心路由 器的负荷，易于在大吞吐量的i p 网络上实现：区分业务模型使用与目前i p 网络协 议相结合的方式来实现“域”内的q o s 保证，比使用端到端q o s 控制的综合业务 模型简单，网络额外负担也较小。其主要缺点是不能绝对保证质量，而且服务质量 提供不是端到端的，而是限于一个区分业务域。但是，区分业务模型能够很好的与 i p 网络相适应，其可扩展性、实现的简单性、可操作性和可部署能力使得区分业务 模型逐渐成为目前主流的i po o s 体系结构。目前，区分业务模型是业界认同的i p 骨干网的o o s 解决方案，但是由于标准还不够详尽，不同运营商的d i f f s e r v 网络之 间的互通还存在困难【5 1 。 2 1 3 多协议标签交换( m p l s ) 多协议标签交换( 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 ) 技术是将第二层交换 和第三层路由结合起来的一种l 2 l 3 集成数据传输技术。m p l s 首先在入口边缘路 由器( i n g r e s sl e r ) 判断l p 数据包的转发等价类( f e c ) ，然后根据不同的类别绑 定固定长度的标签，位于m p l s 网络中间节点的标签交换路由器( l s r ) 根据数据 包的标签进行交换转发。在出口边缘路由器( e n g r e s sl e r ) 去掉i p 数据包的标签， 按三层路由转发至目的地。m p l s 主要目的是进行i p 网络流量管理和加速路由器转 发过程，但标签交换路由器( l s r ) 根据标签不仅可以选择下跳路由，而且可以 选择不同的丢弃策略和调度优先级，因此m p l s 也是一个支持q o s 管理的协议【6 】。 m p l s 的主要技术特点有：1 ) 流量工程；2 ) 负载均衡；3 ) 路径备份；4 ) 故障 恢复；5 1 路径优先级及碰撞。 现在，m p l s 已成为实现t e ( t r a f f i ce n g i n e e r i n g ) 的重要手段，并且与d i f f s e r v 6 第2 章动态q o s 控制的体系结构 结合成为提供q o s 的重要手段。 2 1 4 流量工程( t e ) 导致网络拥塞的原因可能会是网络资源不足或通信分布不均匀。在前一种情况 下，所有路由器和链路都会过载，唯一的解决办法是升级基础设施，提供更多的资 源。在第二种情况下，网络的一些地方过载而其他地方的负载却较轻。现在的动态 路由协议r i p 、o s p f 和i s i s 都会导致不均匀的通信分布，因为他们总是选择最短 路径转发包。结果是，在两个结点之间顺着最短路径上的路由器和链路可能发生了 拥塞，而沿较长路径的路由器和链路却是空闲的。流量工程就是安排传输流如何通 过网络，以避免不均匀地使用网络而导致拥塞的过程。它通过为拥塞节点或重载节 点提供替代路由来平衡网络流量，使网络负荷均匀。 流量工程的目标有两个：一是提高资源的利用效率；第二是要优化流量的性能。 流量工程并不为某个特定流提供q o s 支持，它仅是通过对聚合后的流的操作来提高 整个网络的性能，从而使流量获得更好的服务质量。 2 1 5q o s 路由( q o s r ) 现在的i n t c r n e t 路由协议( o s p f 、r i p 等) 都采用单个计量单位( 如跳数、成 本) 来计算最短路由，没有考虑多个q o s 参数的要求。q o s 路由的定义是：根据网 络中已知的一些资源可用信息，以及业务流的q o s 要求，来为业务流进行选路的机 制。q o s 路由根据多种不同的计量参数( 如带宽、成本、每一跳开销、时延、可靠 性等) 来选择路由。q o s 路由的目标是：动态确定可行路径；优化网络整体的资源 利用；对网络中现有业务的性能影响尽可能小。 q o s 路由能够满足业务的q o s 要求，同时提高网络的资源利用率。但是q o s 路由的计算十分复杂，网络开销大，目前实用的q o s 路由算法还不多见。在第3 章 中将对q o s 路由算法做详细探讨。 以上几种服务模型和机制都有着各自的优缺点：综合业务模型的可扩展性差； 区分业务模型虽然实现简单，扩展性较好，但是不能保证端到端的服务质量，而且 缺少控制手段，只能静态手工控制和加载特性；m p l s 技术实现上还存在问题，不 够稳定；流量工程目前实施一般都是静态手工或者半静态实施，由于缺乏动态实时 地进行部署的工具，因此很难对短期突发行为进行调节，这个缺点已在广东电信骨 干网上得到验证：q o s 路由由于需要考虑的参数很多，计算十分复杂，网络开销大， 7 中山大学硕士学位论文动态q o s 控制架构下的路由算法研究与仿真分析 实用的q o s 路由算法还不多见。所以单独采用某一种模型或机制都不能很好地满足 q o s 需要，只有将多种实现机制进一步改进和相互融合，才能实现对i pq o s 的良好 支持。为此，我们设计了一个融合了多个模型和机制的功能和优点的体系结构，下 面进行介绍。 2 2 动态q o s 控制模型基本思想 本文提出了一种能够实现动态q o s 控制的体系结构，其基本思想是基于m p l s 网络，配置一个q o s 服务器集中控制和分配资源。该模型如下： 图2 - 1q o ss e r v e r 模型 为了在全网范围内最大限度地合理分配网络资源，需要一种能够根据网络状态 和应用的q o s 请求计算和分配所需资源的机制。如图2 1 所示，在m p l s 网络里设 置一个q o s 服务器( q o ss e r v e r ) ，它是整个q o s 控制体系的核心，根据应用或管 理员对q o s 资源的请求，在整个网络范围内，集中控制和使用网络资源，规划和设 计流量的路径，决定负载的分布和执行服务水平协定( s l a ) 等，然后下发命令给 边缘路由器( e r ) ；入口边缘路由器支持d i f f s e r v 和m p l s ，当接收到q o ss e r v e r 发出的控制信息后，使用r s v p 协议，在入口和出口边缘路由器之间建立l s p ( 如 图2 - 1 中蓝色虚线所示) ，等待流量进入并标记其优先级。在整个体系结构下， d i f f s e r v 提供分类、整形、标记和调度，m p l s 则提供封装和转发服务。核心路由 器( c r ) 用多协议标签交换在l s p 上转发包。使用e l s p 做d i f f s e r vo v e rm p l s ， 用m p l s 的e x p 域来标示传送分组的t o s ，数据包的服务质量类型由t o s 等参数 8 第2 苹动态o o s 控制的体系结构 来决定，边缘路由器则根据t o s 来决定输出队列和丢包优先级，调度包的转发。 我们根据需要定义了三种业务类型：最优的业务( p r e m i u m ) ，对带宽和时延提 供保证：金牌服务( g o l d ) ，只保证带宽：尽力而为的业务( b e s t e f f o r t ) 。在图2 - 1 的例子中，物理上是由一个网络组成，但因为我们的系统架构基于d i f f s e r v 模型， 对o o ss e r v e r 而言就不是一个网络，而是多个针对各业务类型的虚拟网络，在虚拟 网络中迸行路由计算，相应地选择满足q o s 需要的路由，实现分级的q o s 保证。 2 3 动态q o s 控制工作流程 图2 - 20 0 s 控制工作流程 1 信息采集 网络状态初始化时，由网络管理系统采集网络的各种统计量，如节点标识( i d ) 、 链路标识、链路带宽、链路状态和拓扑信息等，建立数据库。用户或者网络管理员 的q o s 请求( 如对带宽和时延的要求) ，通过用户接口发送给管理系统。 2 q o ss e r v e r 制订决策 q o s 控制是整个q o ss e r v e r 体系结构的核心部分。q o s 控制执行以下操作： 根据用户的s l a ( 其中定义了时延和带宽) 和其他协议来判断用户权限，并 反馈信息给管理系统； 判定用户对应的入口边缘路由器，对用户流量的优先级进行设置： 根据用户需求和从数据库中获取的网络信息，调用o o s 路由算法，执行路 由计算，检验请求是否应被接纳，并决定流量对应的显式路由； 当已有的流量结束或者新的流量进入时，根据已接纳的流量的带宽和路由信 息来更新数据库。 3 决策下发 9 中山大学硕士学位论文动态q o s 控制架构下的路由算法研究与仿真分析 q o ss e r v e r 制订的决策被下发到对应的入口边缘路由器上( 如图2 - 1 中红色的 路由器e r ) ，以完成所请求的任务。 4 控制的执行 入1 3 边缘路由器在收到q o ss e r v e r 下发的控制信息后，基于这些命令进行动态 配置。动态配置包括了四个部分：1 ) 准入控制( a d m i s s i o nc o n t r 0 1 ) ；2 ) 流量监管 ( t r a f f i cp o l i c i n g ) ；3 1l s p 的建立：根据q o ss e r v e r 规定的显式路由，通过r s v p 协议建立新的l s p ；4 ) 流量映射：根据流量的特征( 如源目的地址、源目的端口 或应用对应的协议) ，输入流被动态映射到l s p 上，随后数据包沿着相应的l s p 发 送到目的节点。 整个系统架构是以m p l s 网络为基础的，之所以选择m p l s 网络，是因为它在 数据驱动方式下具有建立显式路由的能力，可以在源节点就确定一条端到端的显式 路由的l s p ( e l s p ) ，而非传统的逐跳路由机制，这样有利于部署源路由方式的 q o s 路由算法，确定合适的路由后进行数据包的快速转发。 我们在o p n e t 仿真环境下开发了一个仿真平台，实现了此架构。通过仿真验 证，在q o ss e r v e r 的集中式控制下，能够实现动态q o s 保证。具体实现将在第4 章中进行介绍。 这个集中式控制架构的优点是：能够在全局范围内合理管理和调配网络资源， 实现分级的动态q o s 控制。但是集中控制方式必然面临扩展性的问题，一旦网络规 模很大和业务大量增加的情况下，q o s 服务器的处理速度和处理能力必然会成为网 络的瓶颈。解决此问题的方法可以通过对用户进行限制，比如只允许签约用户对q o s s e r v e r 发出请求，其余用户的请求则不被受理。 2 4 q o ss e r v e r 架构的核心技术 在q o ss e r v e r 架构的核心是q o s 控制模块，而q o s 路由计算是控制功能中最 关键的一部分，因为q o s 路由能实现以下功能： q o s 路由能够根据采集的网络状态信息和用户请求，从多个可能的选择中 动态决定可用路径来满足给定流的需求： 优化资源利用。基于网络状态的q o s 路由可以有效地利用网络资源并提高 网络的整体吞吐率； 平缓的性能降低。q o s 路由将对网络中出现的短暂的不足和缺陷( 比如在 业务过载集中发生时) 进行补偿。与对网络状态不敏感的路由机制相比， 可以获得更好的吞吐率和较平缓的性能降低； 1 n 第2 章动态o o