（计算机应用技术专业论文）基于满意优化的qos路由优化方法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 在新的网络服务模式中，大多数业务的路由选择存在多个q o s 约束条件， 传统的路由策略不一定能满足用户所提出的多个q o s 要求。近年来，多约束o o s 路由优化问题逐渐受到研究者的关注但是，他们大都把目光集中在多q o s 约 束下的最优路由，即进行q o s 路由的最优化。通常的做法是将某些服务质量参 数作为路由选择的约束条件或者惩罚函数，将多个q o s 参数加权聚合成单目标， 结果产生符合约束条件的“最优解”。这些研究忽略了以下问题：首先，各个优 化目标之间的不可公度性和矛盾性导致我们难以把多个优化目标简单归并为单 个目标；其次，多约束q o s 路由是一个n p 完全问题f 1 4 】，在许多情况下最优解 难以找到，有时甚至根本不存在；另外，这些路由研究在讨论q o s 路由寻优时， 很少涉及q o s 参数指标的具体计算方法。 本文认真分析和讨论了网络多约束q o s 路由选择的相关原理及技术，提出 了基于满意优化原理的q o s 路由解决方案，可以很好的解决上述问题。本文的 研究工作主要有以下几个方面： 1 ) 研究o o s 基本体系结构，通过分析排队调度、流量整形等o o s 保障方法， 归纳和推导基于m m 1 排队模型、q o s 控制机制、网络演算等不同业务环 境下o o s 参数的计算方法。 建立q o s 路由多目标满意优化求解模型。该模型基本思想是用“满意解” 代替“最优解”，提出了q o s 路由各个性能指标满意度函数以及综合满意度 函数的选取与设计方法，将没有统一度量的各个优化目标转化成一种性能指 标的形式，不仅很好的解决了各个优化目标之间不可公度性的问题，而且使 得建立更简单更合理的路由尺度成为可能，达到同时优化多个q o s 参数的 目的。 3 1 对o o s 路由多目标满意优化算法进行网络单播和组播路由的仿真，分析和 验证算法在o o s 路由寻优问题上的可行性和有效性。 关键词：q o s 路由，单播路由，组播路由，满意优化，满意度函数，遗传算法 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t f o rn e wn e t w o r ks e r v i c em o d e l s , m o s to fr o u t i n g sh a v e m u l t i p l eq o s c o n s t r a i n t sa n dt r a d i t i o n a lr o u t i n ga l g o r i t h mc a n tm e e tt h eu s e r sq o sr e q u i r e m e n t i nr e c e n ty e a r s ，m u l t i p l ec o n s t r a i n e dq o s r o u t i n gp r o b l e mh a sc a u g h tr e s e a r c h e r s e y e sg r a d u a l l h o w e v e r , m o s tr e s e a r c h e r sf o c u so n b e s t p a t hw i t hm u l t i - q o s c o n s t r a i n t s t h e yu s u a l l yt r e a ts o m eq o sp a r a m e t e r sa sc o n s t r a i n t so rp u n i s h m e n t f u n c t i o n so fr o u t i n g , s ot h a tm u l t i - q o sp a r a m e t e r s 锄b ec o n v e r t e di n t oas i n g l e o b j e c t i v e t h e r e f o r et h e yc a np i c ku pt h e b e s t ”p a t ha c c o r d i n gt ot h ec o n s t r a i n t s t h e s er e s e a r c h e sn e g l e c ts o m ep r o b l e m sa sf o l l o w s ：f i r s t l y , i t sd i f f i c u l tt oc o n v e r t m u l t i p l eo b j e c t i v e si n t os i n g l eo b j e c t i v eb e 虻a u s c o fu n m e a s u r e da n dc o n t r a d i c t o r y c h a r a c t e r i s t i ct h a ti sc o n s i s t e di nd i f f e r e n t o p t i m i z a t i o np a r a m e t e r s s e c o n d l y , m u l t i p l ec o n s t r a i n e dq o sr o u t i n gp r o b l e mi sa l ln p - e o m p l e t ep r o b l e m u s u a l l y , i t s h a r dt of i n dt h e “b e s t ”p a t ha n de v e ns o m e t i m e st h e r ei s n ta n y “b e s 广p a t h t h i r d l y , w h e nd e a l i n gw i t hq o sr o u t i n gp r o b l e m s , r e s e a r c h e r sr a r e l yr e f e rt oc a l c u l a t i o n a l m e t h o d so fq o sp a r a m e t e r s t h i sp a p e ra n a l y z e sa n dd i s c u s s e st h et h e o r ya n dt e c h n o l o g yo fm u l t i p l e c o n s t r a i n e dq o sr o u t i n ga n dt h e nb r i n g sf o r w a r dan e wq o s r o u t i n gs o l u t i o nb a s e d o ns a t i s f a c t o r yo p t i m i z a t i o nw h i c hc a l ls o l v et h ep r o b l e m sm e n t i o n e da b o v e n c m a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： 1 ) s t u d yq o s a r c h i t e c t u r e sa n da n a l y z et h em e t h o d sf o rg u a r a n t e e i n gq o ss u c ha s p a c k e ts c h e d u l i n g , t r a f f i cs h a p i n ga n ds oo n , t h e nd e d u c ec a l c u l a t i o n a lm e t h o d s o fq o sp a r a m e t e r sb a s e do nm 懋嗄1q u e u i n gm o d e l ，q o sc o n t r o lm e c h a n i s m s , n e t w o r kc a l c u l a t i o n e s t a b l i s hm u l t i - o b j e c t i v es a t i s f a c t o r yo p t i m i z a t i o nm o d e lf o rq o sr o u t i n gt o s o l v et h ep r o b l e m so ft r a d i t i o n a lr o u t i n ga l g o r i t h m t h ee s s e n c eo ft h i sm o d e li s “s a t i s f a c t o r y p a t hi n s t e a do f “b e s t ”p a t h h o wt od e s i g ns a t i s f a c t o r yf u n c t i o n a n ds y n t h e t i c a ls a t i s f a c t o r yr a t ef u n c t i o nf o rq o sp a r a m e t e r si sd i s s c u s s e d t h e r e f o r ee a c ho p t i m i z a t i o no b j e c t i v ew i t h o u tc o n s i s t e n tm e a s u r e m e n tc a nb c c o n v e r t e di n t oaf o r mo fp e r f o r m a n c es p e c i f i c a t i o n , w h i c hn o to n l ys e t t l e st h e p r o b l e mo fu n m e a s u r e dc h a r a c t e r i s t i ce x i s t e di nd i f f e r e n tq o sp a r a m e t e r s , b u t a l s om a k e si tp o s s i b l et ob u i l du pa l le a s i e ra n dm o r er e a s o n a b l er o u t i n gc r i t e r i o n 西南交通大学硕士研究生学位论文第1 i i 页 t oo p t i m i z em u l t i p l eo o s p a r a m e t e r ss i m u l t a n e o u s l y 3 1s i m u l a t i o n sa l em a d eo l ln e t w o r ku n i - c a s ta n dm u l t i - c a s tm u t i n gf o r t h e a l g o r i t h mp r o p o s e da b o v e r e s u l t so fs i m u l a t i o nd e m o n s t r a t et h a ti ti se f f e c t i v e a n df e a s i b l ef o rq o s r o u t i n g k e y w o r d s ：q o sr o u t i n g , u n i - c a s tr o u t i n g , m u l t i - c a s tr o u t i n g , s a t i s f a c t o r y o p t i m i z a t i o n ，s a t i s f a c t o r yr a t ef u n c t i o n , g e n e t i c a l g o r i t h 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景 第1 章绪论 近几年来，i n t e m e t 在各方面飞速发展，如传输带宽的增加、地址空间的扩 大、用户数目的激增等，带来的是应用和业务的不断推陈出新和网络吞吐量的 急剧增加。i n t e m e t 逐步由单一的数据传输网向数据、语音、图像、视频等多媒 体信息的综合传输网演进为实现多种业务共存，服务质量( q u a l i t y - o f - s e r v i c e ， q o s ) 控制机制是必需的。但是，目前i n t e m e t 中的信息传输模式仍然是单一的“尽 力而为( b e s te f f o r t ) ”服务，无法满足多媒体应用和各种用户对网络传输质量的不 同要求。因此，以提高网络资源利用效率、为用户提供高质量服务作为目标的 q o s 研究成为当前i n t e m e t 领域的热点之一 o o s 研究的目标是使网络能够有效地实现端到端的服务质量控制和保证 目前主要通过两种方法来实现o o s 保证一种是节点控制；另一种是全网或局 部网络的o o s 控制。节点控制在单节点完成，主要策略包括：流量整形与监管 ( t r a f f i cs h a p i n ga n dp o l i c i n g ) 1 1 、分组调度( p a c k e ts c h e d u l i n g ) 2 - 3 1 、队列缓冲管理 ( b u f f e rs h a r i n g ) a - s 等。而全网和局部网络的o o s 控制通过对路由、信令的控制， 实现对业务流和网络资源利用的控制，包括端到端的拥塞控制、o o s 路由等。 目前，i e t f 已经提出了多种服务模型来满足网络业务的各种o o s 需求，如 集成服务模型o n t s e r v ，i n t e g r a t e ds e r v i c c s ) i ”j ，区分业务模型( 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 s ) 8 1 ，多协议标签交换( m p i _ s ，m u l t i - p r o t o c o ll a b e l s w i t c h i n g ) 9 - l o 。在实现这些服务机制时，首先要在进行通信的双方之间找到一 条可行的路径，然后才能在网络资源满足要求的路径上进行资源预留、接纳控 制或按流标签转发数据流等。而o o s 路由的主要任务就是在网络中寻找一条满 足用户o o s 请求的网络路径。因此，o o s 路由被认为是保证网络服务质量的一 项不可缺少的路由技术。 作为o o s 体系的重要组成之一，o o s 路由有两种应用背景1 1 1 l ，其一是流量 工程，其二是动态请求。对于前者来说，其操作主要以长程的通信量变化为基 础，以聚集流为路由对象，考虑粗粒度的性能需求，因此路由选择通常要考虑 流量特性、网络约束和策略约束等因素。对于后者，q o s 路由是为每个请求而 西南交通大学硕士研究生学位论文第2 页 计算的，路由计算更加频繁，资源分配粒度更小，这种细粒度的路由策略机制 可以为网络提供更有力的o o s 保证，但是在更新网络状态、路由计算以及信令 上需要付出更大的开销。 q o s 路由能够对业务的多种服务需求提供弹性支持，通过提高整个网络吞 吐量达到网络资源的有效利用，并且通过路由优化达到网络负载均衡的目的1 1 2 1 。 显然，o o s 路由的优化设计对保证网络服务质量起到了非常关键的作用。 1 2q o s 路由的研究现状与问题 1 2 1 国内外研究现状 目前，在对多约束q o s 路径选择的研究过程中，主要形成了两大类典型的 q o s 路径选择问趔1 3 】：( 1 ) 受限最短路径( r e s t r i c t e ds h o r t e s tp a t h ，r s p ) 选择问 题；( 2 ) 多约束路径( m u l t i c o n s t r a i n e dp a t h ，m c p ) 选择问题。 受限最短路径选择问题的目标是在源节点到目的节点之间的所有路径中选 择一条满足时延约束并且代价最小的路径。通常这个代价可以定义为带宽、跳 数等度量的函数，时延约束也可以变为其它的约束参数。文献【1 4 】提出首先删除 所有不满足带宽要求的链路，然后采用d i j k s t r a 算法找到一条时延最小的路径。 a p o s t o l o p o u l o s 等人提出了一种基于带宽和跳数的q o s 路由选择算法i 划，其准 则是在满足带宽要求的所有路由中选择跳数最少的路径，如果这样的路径多于 一条，再从中选取可用带宽最大的那一条这些算法在本质上与约束最短路径 选择问题是相同的。布达佩斯大学的j u t u l e r 1 6 】研究了基于拉格朗日松弛的线性 组合算法，链路l 的度量w q ) 被线性组合成一个值h ，( f ) - 谢( f ) + 肛( f ) ，d ( f ) 、c q ) 分别表示链路l 的时延和代价，系数口、口被称为拉格朗日乘子 多约束路径选择问题要求路径满足多个约束条件。通常能够同时满足所有 给定约束的路径称为可行路径。在源节点和目的节点之间可能存在多条可行路 径，研究人员希望从这些可行路径中找到“长度最短的路径”。这个问题就是所 谓多约束最优路径问题( m u l t i - c o n s t r a i n e do p t i m a lp a t h ，m c o p ) ，多约束最优路 径不仅要满足多个约束条件，而且它的路径长度函数值是可行路径集中最小的。 约束最短路径选择问题可看成多约束最优路径问题的特例。 1 w a t a 1 7 】提出了解决m c p 问题的多项式时间算法。该算法首先搜索基于某个 单一度量的最短路径，如果这条最短路径同样能满足其它约束，则该最短路径 西南交通大学硕士研究生学位论文第3 页 即为可行路径；如果不能满足其它约束，则搜索基于其它度量值的最短路径， 并检查路径的可行性。该过程一直持续到找到可行路径，或者基于每个o o s 度 量的最短路径都搜索完为止。c h e n 1 8 】提出了一种解决m c p 问题的启发式算法。 该算法首先通过产生一个新的加权函数将n p 较难的m c p 问题转化为一个能够 在多项式时间内求解的简单问题，然后利用改进的d i j k s t r a 算法或 b e l l m a n - f o r d 算法来求解最佳路径。n e v e 和v a nm i e g h e m l l 9 1 提出了一种在多个 加性约束条件下求解o o s 路由的算法。该算法将多个加性度量参数合成为一个 综合度量参数：g 。【p ) 拦萼吗- + 拦琴吗- + 一硝- ，其中形 ) 是 路径p 的第i 个度量参数，厶是路径的第i 个约束，最后再用最短路径算法求 得q o s 路由。 国内方面，西安电子科技大学张军英刚将多约束o o s 路由选择问题转化为 一个多约束的赋权图最短路径问题，建立了点火耦合神经网络，在自动波的传 播过程中随时监督约束的满足情况，及时取消不满足约束的自动波，从而最先 到达目的节点的自动波所走过的路径即为多约束q o s 的最优路径东南大学冯 径【2 1 】等提出用混合法解决q o s 路由的多目标规划问题，每次选取目标函数的两 个尺度，按照不同的权值求得一组路径，在这些路径集中首先标定共同的链路， 然后再根据偏好选取满足需要的其他链路。南京理工大学杨云【碉将m c p 问题转 化为带约束条件的多目标优化问题，采用遗传算法的智能进化理论来解决多目 标q o s 路由问题。 1 2 2 存在问题 目前进行的多约束q o s 路由研究中，通常的做法一般可分为两种：( 1 ) 根 据业务对不同参数要求的不同，从多个参数中选择出一个主要的参数，首先根 据此参数进行路由选择。当有多条路径满足约束时，再按照一定的规则从这些 路径中选择出满足次主要的度量参数约束的路径，直至只剩一条路径为止。( 2 ) 根据q o s 应用需求，设计一个“路径长度函数”，将多个q o s 参数加权聚合成 单目标，用传统单尺度路由选择算法进行选路。 第一种方法的算法大都局限在两个尺度的组合上，并且假定应用严格绑定 某个延迟或带宽要求，要求网络状态信息是准确的。而第二种方法，可以满足 较松弛的q o s 绑定，对网络状态信息的准确性要求相对低一些，为我们解决两 西南交通大学硕士研究生学位论文第4 页 个以上度量约束的路由选择问题提供了可行的思路。但是，我们必须注意到以 下问题的存在： 首先，o o s 路由问题是典型的多目标优化问题，多目标优化与单目标优化 不同，其最显著特点是优化目标之间的不可公度性和矛盾性。不可公度性是指 各个优化目标之间没有统一的度量，如多媒体通信要求端到端时延最小，时延 抖动最小，丢包率最低，带宽最大，费用最低，资源消耗率最低等。时延和时 延抖动的度量单位是时间( m s ) ，费用是元，丢包率无量纲，带宽的单位是用b i t s 。 因此，从物理意义上讲，难以把多个优化目标简单归并为单个目标。 其次，人们在设计“路径长度函数”的时候，为了计算方便，通常将某些 服务质量参数作为限定范围的约束条件或者惩罚函数加权聚合成单目标，在限 定范围内运行最短路径算法进行求解。这种对约束参数的处理方法很容易忽略 一些重要的服务参数，优化的意义不能得到充分体现。例如：将网络中所有剩 余带宽比o o s 要求带宽小的链路去掉，在剩下的链路中考虑在其他( 1 0 s 度量下的 最优路由，而不再考虑带宽，带宽这个度量参数实际上并没有得到优化。如果 有两条路径，它们的其他0 0 s 度量大致相同，但是其中一条路径的剩余带宽较 多，而另一条的剩余带宽较少，尽管它们都满足了最低带宽的要求，但是显然 我们应该优先考虑剩余带宽较多的那条路径，而原先进行的o o s 路由研究都将 这一点忽略了应该注意到，将剩余带宽的问题考虑进去后，还有另外两个不 明显但是却很重要的好处就是：能够将流量优先分配到那些有较多剩余带宽 的路径上，起到平衡网络流量的作用；提高网络资源预留成功的可能性 第三，人们在进行多约束( 1 0 s 路由研究时，大都把目光集中在多q o s 约束下 的最优路由，即进行0 0 s 路由的最优化。如前面所述，某些o o s 参数在满足约束 条件后就被忽略掉了，他们求解所得的其实只是某个服务参数的“最优解”，并 非传统意义下的“最优解”实际上，o o s 路由多个目标之间不可避免存在着矛 盾性，目标之间的矛盾性使得强调改善某个目标，可能使另一个目标变差。所 以，在网络q o s 路由的多目标优化中，一般不存在传统意义下的最优路由而 且，多约束q o s 路由的求解为n p 完全或n p 难【1 4 1 ，在这种情况下，盲目的追求最 优解显然是不切实际的。 第四，许多文献在研究0 0 s 路由时，往往用瓶颈带宽、时延、时延抖动、 丢包率等反映网络结点或链路的特征。问题是这些q o s 参数该如何计算? 这些 在算法描述中并未说明，只是设置一些假设数据来描述算法，因此，还是没有 从根本上解决问题。 西南交通大学硕士研究生学位论文第5 页 综上所述，以往提出的q o s 路由算法存在诸多问题，需要引入新的优化方 法来求解网络的多约束q o s 路由问题。本文通过对满意优化原理进行了较深入 的研究，提出了基于满意优化原理的q o s 路由解决方案，使之更适合解决q o s 路由选择问题。 1 3q o s 路由满意优化方法 传统优化方法寻求优化问题的最优解，然而实际优化问题往往因多种复杂 因素难以建模，或根本不存在传统意义上的最优解或获得最优解的代价太大 寻求“满意解”以代替“最优解”自然成为解决这类优化问题时普遍采取的策 略t 2 3 - 2 5 l 。 目前，以“满意解”输出为原则的满意优化方法已经成功的应用于不少领 域。西南交通大学的金炜东教捌2 3 l 研究了评价满意解性能的满意度函数，针对 优化问题的较复杂的情况提出一种多目标满意优化模型，并将它们应用于控制 器参数设计以及列车操纵优化方法研究中。靳蕃教授1 2 4 l 在研究人工神经网络过 程中，首先提出了“神经计算的满意解原理姚新胜【2 5 l 等人研究了满意优化原 理及其在机械工程领域中的应用。 本文针对q o s 路由选择的实际情况，设计出了个基于满意优化原理的多 约束q o s 路由求解模型，可以有效的解决1 2 2 节存在的问题。该模型的基本 思想是用。满意解”代替“最优解”，在优化多个服务性能指标，找到满意路径 的同时，隐性的实现网络负载均衡，提高网络资源的利用效率 本文提出的q o s 路由多目标满意优化方法首先通过研究流量整形、排队以 及分组调度等q o s 控制技术，分析q o s 参数在不同业务环境下的计算方法。这 样就可以根据q o s 请求的业务特性和网络资源使用情况，选择相应的公式动态 的计算所需要的网络结点或链路的q o s 度量值，而并非只是假设一些数据来说 明，从网络更深层的角度保证q o s 路由算法的合理性和有效性，而且从一定程 度上可以降低网络状态信息的非精确性造成的影响。 其次，本文提出的q o s 路由多目标满意优化方法引入了各q o s 度量参数的 满意度函数。简单但是合理的满意度函数将没有统一度量的各个优化目标转化 成用户对该性能指标的满意程度，可以很好的解决各个优化目标之间的不可公 度性。 第三，在对约束参数的处理上，满意度函数的引入使得我们不必再为了简 西南交通大学硕士研究生学位论文第6 页 化而省略重要的q o s 参数，而且综合满意度函数可以作为路径性能的客观评价， 使得建立更简单更合理的“路径长度函数”成为可能，最终产生的是多个服务 质量参数同时优化的满意解。 1 4 论文的研究内容与组织结构 本论文深入研究了网络多约束o o s 路由问题，在分析网络q o s 的体系结 构及控制技术的基础上，以满意优化理论为基础，讨论了在多约束情况下的网 络o o s 路由优化问题。 本文的主要研究工作有：深入研究流量整形、调度策略等q o s 保障方法， 分析q o s 参数在不同业务环境下的计算方法：研究满意优化的基本理论，分析 q o s 路由各性能指标的满意度函数、综合满意度函数等一些关键技术问题；针 对传统q o s 路由优化存在的问题，提出q o s 路由多目标满意优化解决方案，并 通过仿真实验，验证了算法的可行性和有效性。 论文主要内容分为五章，分别如下： 第一章为引言，简要介绍了网络q o s 路由优化的研究背景和问题，提出了 基于满意优化原理的q o s 路由算法，并对当前课题的研究内容以及主要工作进 行了论述。 第二章介绍i p q o s 路由的相关技术，首先阐述了q o s 的基本概念，服务模 型和基本控制技术，然后详尽描述了q o s 路由的相关问题，如q o s 路由的度量 参数和数学模型等。 第三章简要介绍了满意优化的基本理论，给出了满意解与满意度函数的定 义，并介绍了综合满意度函数，最后给出了多目标满意优化模型的一般形式。 第四章详细介绍了基于满意优化原理的q o s 路由方法，讨论了q o s 性能指 标的计算方法，建立了多约束o o s 路由的满意优化求解模型，并给出了o o s 路 由多目标满意优化的一般步骤。最后着重分析了如何建立q o s 性能指标的满意 度函数和综合满意度函数。 第五章运行q o s 路由多目标满意优化算法对单播和组播路由进行了仿真， 并对仿真结果进行了分析和讨论，验证了算法在网络路由问题上的可行性和有 效性。 西南交通大学硕士研究生学位论文第7 页 第2 章i pq o s 路由相关技术 传统的i n t e r a c t 只提供“尽力而为”服务。随着i n t e r n c t 网络流量的迅猛增 长，以及一些具有实时要求的新兴业务如视频会议、多媒体传输等的不断涌现， 需要在i n t c r n c t 中引入一些新的控制机制来有效地提供端到端服务质量的控制 和保证本章系统地描述o o s 相关技术，并着重介绍q o s 路由的度量参数、数 学模型等。 2 1i pq o s 体系结构 q o s ( q u a l i t yo fs e r v i c e ) ，即服务质量，在r f c 2 3 8 6 1 2 】中用来刻画网络在传 输数据流时要求满足的一系列服务需求，具体可以量化为带宽、延迟、延迟抖 动、丢包率、吞吐量等性能指标。此处的服务具体是指数据包( 流) 经过若干网络 节点所接受的传输服务，强调端到端( e n d t o - e n d ) 或网络边界到边界的整体性。 o o s 反映了网络元素在保证信息传输和满足服务要求方面的能力1 1 1 】 到目前为止， e t f 主要提出了3 种服务模型用于在m 网上提供o o s 服务： 集成服务0 n t s e r v ) 、区分服务( d i f l s e r v ) 、多协议标签交换( m p l s ) 。 ( 1 ) 集成服务( i n t s e r v ) 为了满足i n t e r a c t 多媒体应用实时传输的要求，i e t f 定义了i n t s e r v 模型1 6 】， 主要且的是在i n t c r n c t 中同时为非实时的应用和实时的多媒体应用提供服务。在 集成服务模型中，实时应用被看成一个个流( f l o w ) 。所谓流是指源于某一用户的 特定行为的一串彼此相关的口数据包，这些数据包具有相同的q o s 要求，且可 能有多个接受者。 ， 集成服务的基本思想是；对网络所有的共享链路进行一定的资源控制，同 时考虑将网络应用( 流) 统一实现在对上层应用的服务接口中。所有的路由器在控 制路径上处理每个流的信令消息并维护每个流的路径状态和资源预留状态，并 且在数据路径上执行流的调度和缓冲区管理等。集成服务的一个重要特点是引 入了资源预留协议限s v p ) 【7 。r s v p 本身并不是一个路由选择协议，它与路由协 议结合使用，沿着选定的路径预留资源的信令协议。r s v p 采用单方向预留方式， 通过接纳控f l ；j j ( c a c ) 判断链路或网络节点是否有足够的资源满足用户的资源预 西南交通大学硕士研究生学位论文第8 页 留请求，如果满足则由数据流的接收端向数据源沿路径进行预留。r s v p 的引入 使得口网络为应用提供所要求的端到端的0 0 s 保证成为可能。 i n t s e r v r s v p 尽管提供o o s 保证，但其并不具备支持大型网络所需要的可 扩展性。因为其工作方式是基于每个数据流的，这就需要保存大量的与分组队 列数成正比的状态信息。此外，r s v p 的有效实施还必须依赖于分组所经过路径 上的每个路由器。在大型骨干网上，业务流的数目可能很大，因此要求路由器 的转发速率很高，这使得集成服务难以在骨干网上得到实旌。 ( 2 ) 区分服务0 m f l s e r v ) i e t f 于1 9 9 8 年提出了i n t e m e t 区分服务( d i 丘s c f v ) l s l 模型，旨在定义一种能 实施i po o s 且更易扩展的方式，以解决集成服务模型扩展性差的缺点。区分服 务的设计目标是提供一种简单的、容易实现并且是低成本的工具来支持一系列 的网络服务。 区分服务模型基本思想是重新利用口数据包头中的服务类型( t o s ) 字段( 改 为d s 域) ，边界节点将进入网络的单流分类、整形、聚合为不同的流聚集，这 种聚集信息存储在每个口包头的d s ( d i f f e r e n t i a t c ds e r v i c e s ) 标记域( f i e m ) 中，称 为d s 编码点( d i f f e r e n t i a t e ds e r v i c e sc o d ep o i n t ，d s c p ) ，服务对象就是聚集流 ( f l o wa g g r e g a t e ) 而非单流。流状态信息的保存与流监控机制的实现等也只在边界 节点进行，简化了网络内部节点的服务机制。内部节点是状态无关的，只是根 据包头的d s c p 字段判断业务的类别进行简单的调度转发，其特性称为每跳行 为( p e r - h o p - b e h a v i o r ，p t m ) ，从而为不同的业务提供不同的0 0 s 保证策略。 区分服务模型根据聚集流来分类，这样无论流的数目如何增加，区分服务 模型只提供有限的几类服务，因而具有较好的可扩展性。但由于内部路由器对 流是不加区分的，所以区分服务模型无法保证一个类中每个流都能满足服务质 量的要求。 ( 3 ) 多协议标签交换协议o 讧p i 固 多协议标签交换技术( m p l s ) 【9 1 0 l 是一种基于短标签交换的数据转发方式， 它不同于传统的基于目的地址的逐跳寻径方式。在传统的口路由中，每个节点 都要独立分析口包头。而在m p l s 中，只是在分组进入网络的边缘节点处对口 包头进行分析，后续节点不再分析包头，简化了数据包的转发过程，大大提高 了路由器转发速率。 在m p l s 中，所有进入网络的分组都被指定到某个特定的转发等价类 f e c ( f o r w a r d i n ge q u i v a l e n c ec l a s s ) ，然后再将f e c 映射到特定的满足f e c 要求 西南交通大学硕士研究生学位论文第9 页 的标签交换路径i s p ( i a b c ls w i t c h i n gp a t h ) ，从而实现对数据流的控制。f e c 的 指定可以根据多种策略进行配置，例如源目的地址、数据包头的c o s 字段等。 而l s p 的选路也可以配置为满足不同应用的需要，例如l s p 可以设计为经过的 跳数最少、满足特定的带宽要求、支持一定的性能要求、避开潜在的拥塞点等 等。 m p l s 的一个重要特点是控制与转发完全分离，控制部分完成路由和标记 映射的作用，转发部分完成数据转发的作用。与区分服务模型有点类似的是， m p l s 也是在网络的入口处给数据包打上标记，而在出口处除去标记，但与前 者的不同点在于m p l s 中标记决定了如何转发包，它决定了包的转发路径；而 区分服务模型中标记的作用是标记包的转发特性，即包的服务的优先权m p l s 目前被业界普遍认为是解决o o s 和流量工程的一项较好的技术。 2 2q o s 基本控制技术 为了提供服务质量保障，网络节点( 路由器) 必须同时从控制平面和数据平面 两个方面提供必要的控制手段，如图2 1 所示。其中，控制平面通过信令协议来 协商服务等级( s l a ) ，进行接纳控制、预留资源和拥塞控制为了优化资源的利 用率，可能还需要流量工程( t r a f f i ce n g i n e e r i n g ) 。在数据平面，需要在输入端首 先对进入的流量进行制约( c o n d i t i o n i n g ：监管、整形，打标记) ，根据服务等级要 求对流量进行分析，然后通过交换机构将报文转到相应的输出端，在输出端对 报文进行缓存和调度。 图2 1 服务质量保障体系中的控制平面和数据平面 西南交通大学硕士研究生学位论文第1 0 页 2 2 1 接纳控制 u 一拍l 对接纳控制( c a c ) 作了如下的定义：“c a c 是网络在呼叫建立( 或重 协商) 阶段所采取的一系列行为，以确定一个连接建立请求是否被接受”。一旦 c a c 决定接纳该连接建立请求，则给这一新的连接分配相应的资源( 包括带宽、 缓冲区等) 。 一个连接请求被接受的条件是该连接经历的所有交换结点满足如下两个条 件：( 1 ) 网络具有足够的资源( 如带宽和缓冲区) 满足该连接所要求的o o s ：( 2 ) 能 够保证已建立连接的o o s 不被影响。 在呼叫连接建立阶段，下列参数( 包含在流量合同中) 需要在用户和网络之间 进行协商并取得一致，以使c a c 对连接接受鹿绝做出正确的决定。 业务源流量描述：业务源流量描述是用来描述业务源业务特性的一组流量参 数，如峰值速率、平均速率和突发长度等。 所要求的o o s 类型：如数据包丢失率、数据包传送时延等。 一致性定义。一致性定义是指根据什么方法来判断用户的业务流量符合所协 商的流量合同。 在网络o o s 服务模型中，除了保留了原有的传统的“尽力而为”服务之外， 还提供了确保型服务和部分确保型服务。 在确保型服务中，用户应用向网络提交其流量特性参数和服务性能参数， 网络通过c a c 机制来确定是否允许用户使用其所需的服务。一旦达成约定，则 这种合约关系一直维持到用户应用的数据传输结束为止。 对于部分确保型服务而言，其所对应的c a c 算法使用的参数不是事先确定 的特征值，而是依赖于对参数的观测值，这样当网络负载发生变化时，这些观 测值也会发生改变。因此部分确保型服务的接入控制允许不是完全可靠的服务 约定。 2 2 2 流量整形 流量整形【1 ( t r a f f i cs h a p i n g ) 也称速率整形、流量控制等。流量整形首先用在 信源数据流整形，尽管信源产生数据流总体速率可能不变或有规律，但短时无 序性使得数据流速率起伏很大，不适合直接进入网络，需先进行流量整形再进 入网络。其次，流量整形也常用于平滑网络传输中的业务流，从而控制拥塞。 目前常用漏桶( 1 e a k yb u c k e t ) 或令牌桶( t o k e nb u c k c i ) 对网络流量进行整形。一 西南交通大学硕士研究生学位论文第1 1 页 个漏桶由一个最多持有6 个令牌的桶构成，并且令牌以速率，匀速产生。在这 种模型下，一个分组被传送到网络之前，它必须获得令牌。此时，该令牌也从 令牌桶中移出。若桶内无令牌，则分组必须等待至新令牌产生。由于桶中只用b 个令牌，所以漏桶管理的最大突发量为b 个分组。由于令牌的产生速率为r ，所 以在任何长度为t 的时间间隔能够进入网络的最大分组数目为，t + 6 个。这样， 令牌产生速率r 被用来限制分组进入网络的长期平均速率。 在实际的网络环境中，网络设备对q o s 流进行流量整形后，数据包在结点 内部的延迟、延迟抖动等q o s 度量会发生不同程度的改变，相应地影响到路径 的端到端时延、时延抖动等q o s 指标。流量整形改善了q o s 的性能，同时也改 变了q o s 度量的计算方式。 2 2 3 分组调度 分组调度 2 - s 是在网络的各中继结点中实现对不同流所属分组进行调度的 机制，使得各流的分组之间不会相互干扰，获得与其 o s 要求相适应的分组转 发性能，避免网络性能和分组转发性能因网络拥塞而造成的下降。它影响的主 要性能参数包括带宽分配、时延和时延抖动等，是实现网络服务质量控制的核 心技术之 根据服务器的工作状态，通常把调度算法分成持续工作( w o r k - c o n s e r v i n g ) 和非持续工作0 妯n w o r k c o n s e r v i n g ) 两大类。当服务器在持续工作状态调度时， 只要缓冲区有等待调度的分组，则必须调度；而非持续工作状态则可能由于算 法决定而不加以调度。持续工作状态具有较高的链路利用率，而非持续工作状 态能对端到端的时延及抖动进行控制。 目前的分组调度算法有很多种，设计的出发点和最终性能也不一样。其中， w f q ( w e i g h t e df a i rq u e u i n g ) 算法被i e t f 指定为有保证业务o o s 性能的参考捧 队算法，本文后面章节也涉及到该算法，因此下面详细介绍w f q 算法的基本思 想。其它算法由于论文篇幅的原因在此不再一一赘述。 w f q 算法试图模拟一种理想化的流量公平队列( f l u i df a i rq u e u i n g ，f r o ) 工作模型，其核心是公平排队和虚拟时钟。在这种工作模型里，所有参与调度 的工作流各自组成缓冲队列。在任意的时段内，各非空队列中的工作流都按照 其分得的处理服务器服务配额，公平地共享处理服务器的服务。f f q 为每一流 排队以提供流量级隔离，但它自己不能解决更普通的网络问题，即执行任意的 相对优先级以提供不同业务类的链路带宽共享。 西南交通大学硕士研究生学位论文第1 2 页 w f q 改进了f f q ，它可以对单个业务流所获得的服务实行细粒度控制， 允许对单个队列分配不同的权值。如果出现有n 个数据发送的队列，任一队列 i 以给定链路速率( 带宽) 的分数破被服务( 这里， 善谚- 1 k 谚依赖于队列i 的优先级，优先级的数值越小，破越小，所获得的带宽越少；优先级的数值越 大，噍越大，所获得的带宽越多。这样就保证了相同优先级业务之间的公平， 体现了不同优先级业务之间的权值。当一些队列为空时，剩余的链路带宽可根 据相应的权值在其他的队列中分配，即能以公平的方式分配剩余的服务能力 在w f q 算法中，调度服务器在选择下一个分组进行服务时，根据所有非空流的 缓冲队列队头分组中的结束时间标记进行，即以结束时间标记作为全局优先级 变量进行调度。 总之，网络链路使用的流量整形和分组调度机制是o o s 框架中不可或缺的 一环，根据调度算法及流量特性可以计算业务流的一些性能指标，网络可以根 据这些指标为业务流提供端到端的q o s 保证。 2 2 4 缓冲区管理 分组调度策略在提供q o s 保证上起到了重要作用，然而这一切均是基于有 足够的缓冲区来存储进入的分组越来越快的链路速度对路由器在拥塞瞬间对 流量进行缓冲的能力要求越来越高，如果路由器缓冲能力达不到要求，则在拥 塞瞬间到达的业务流分组将会被丢弃。缓冲区管理机制的基本内容是当链路出 现拥塞时丢弃分组的策略。分组丢弃策略主要涉及：何时丢弃分组；依据 何种信息做出丢弃分组的决定。 r e d ( r a n d o me a r l yd r o p ) 4 是- 种在拥塞出现前