（通信与信息系统专业论文）非确定环境下分布式qos组播路由算法的研究.pdf

、，07 ；0l 、k ot e m 洒伽嬲嫩 s y s t e m s r e s e a r c ho nt h ea l g o r i t h mf o rd i s t r i b u t e d q o sm u l t i c a s tr o u t i n gw i t hu n c e r t a i n c o n d i t i o n b yl i u y u t a o s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rd u l i n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 ijk，1 i11l】j| r 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 l 工的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示 谢意。 学位论文作者签名：刘玉增 签字日期：洲缉l z 日勿a 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：驯玉谤 签字日期： 导师签名： 签字日期： i 上 东北大学硕士论文摘要 非确定环境下分布式q o s 组播路由算法的研究 摘要 当前通信网络带宽和处理能力的提高不仅使网络能够提供更多的多媒体业务，也 使得支持“点到多点或“多点到多点 的组播通信方式成为网络支持多媒体业务的 必要形式。组播路由是网络层具备的功能，组播问题的关键在于组播路由的确定。寻 找简单、高效、健壮的组播路由算法一直是网络界致力于研究但尚未完全解决的问题。 而许多分布式的多媒体应用对延迟、延迟抖动、带宽以及包丢失率有着不同的要求， 这就需要当前网络能够传送具有这些q o s 要求的实时多媒体信息。因此，作为q o s 网络体系结构中不可或缺的组成部分，对基于q o s 约束的组播路由算法的研究便成为 网络研究领域的重要内容和热点。 目前已有的路由算法大多数都假设网络中的每个节点能够通过距离矢量协议或者 链路状态协议获得并保持网络全局的精确状态。然而，在实际的动态网络环境下，节 点所能获得的网络全局状态并不是精确的，而这种网络信息的非精确性严重地影响着 路由算法的实际性能。 本文首先简要介绍了网络状态信息非精确性的来源，简单列举和分析了集中式路 由和分布式路由算法的特点；然后对q o s 路由理论及d i f f s e r v 体系结构进行了详尽 分析，提出了d i f f s e r v 体系下q o s 组播路由算法的数学模型；对近几年国外研究人 员提出的多种分布式路由算法进行了重点研究和分析，在详细分析这些算法优点和所 存在问题的基础上，提出了一种新的更为合理的q o s 组播路由算法，旨在提高网络性 能的同时减少非确定性对算法的影响。本文提出的新算法r d q m r 是一种基于t i c k e t 的多路路由算法，其中利用分布式路由选择的优点，仅使用与之相连链路的状态信息， 通过利用t i c k e t 有效减少分布式路由算法在选路过程中所引起的盲目性，同时利用多 路选择提高链路建立的成功率，并使用“软预约的方法消除网络资源信息动态变化 的影响。r d q m r 的创新之处在于研究了组播路由算法在d i f f s e r v 体系下和非确定环 境中的特性，并解决了资源的“过预约问题。r d q m r 能克服网络信息的动态变化 对路由算法的影响，从而提高算法的成功率。最后，通过使用c 语言代码对提出的新 算法进行实现和模拟。模拟结果表明，r d q m r 提高了组成员加入的成功率，优化了 平均路径的代价值和平均路径长度值。 关键词：非确定环境；q o s ；组播；分布式路由；区分服务 1 1 名 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho nt h ea l g o r i t h mf o rd i s t r i b u t e dq o sm u l t i c a s t r o u t i n gw i t hu n c e r t a i nc o n d i t i o n a b s t r a c t a tp r e s e n t ，t h ei n c r e a s eo fn e t w o r k b a n d w i d t ha n dp r o c e s s i n gp o w e rm a k e st h e n e t w o r k p r o v i d e m o r em u l t i m e d i a a p p l i c a t i o n s ，a n d a l s om a k e st h em u l t i c a s t c o m m u n i c a t i o nt h a ts u p p o r t s ”o n e - t o - m a n y ”o r ”m a n y - t o - m a n y ”b e c o m ean e c e s s a r ym o d e o fm u l t i m e d i as e r v i c e s af u n d a m e n t a li s s u ei nm u l t i c a s tc o m m u n i c a t i o ni sh o wt o d e t e r m i n ea ne f f i c i e n tm u l t i c a s tr o u t i n g ，a n df i n d i n gs i m p l e ，e f f e c t i v ea n dr o b u s tm u l t i c a s t r o u t i n ga l g o r i t h m si su n s o l v e dp r o b l e mi nn e t w o r kf i e l d s i na d d i t i o n ，m a n yd i s t r i b u t e d m u l t i m e d i aa p p l i c a t i o n sh a v ev a r i o u sd e m a n d so nd e l a y , d e l a yv a r i a t i o n ，b a n d w i d t ha n d p a c k e tl o s s ，w h i c hr e q u i r e sc u r r e n tn e t w o r kt ot r a n s m i tr e a l t i m em u l t i m e d i ai n f o r m a t i o n w i t ht h e s eq u a l i t y o f - s e r v i c e ( q o s ) c o n s t r a i n t s s o ，a sa ni n d i s p e n s a b l ec o m p o n e n ti na q o s - c e n t r i cn e t w o r ka r c h i t e c t u r e ，r e s e a r c ho nm u l t i c a s tr o u t i n ga l g o r i t h m sb a s e do nq o s c o n s t r a i n tb e c o m e sa l li m p o r t a n tp a r ta n dh o t s p o ti s s u eo fn e t w o r kr e s e a r c hf i e l d s m o s to ft h er o u t i n ga l g o r i t h mh a sb e e np u b l i s h e dh a sa s s u m e dt h a te a c hn o d ei nt h e n e t w m kc a na c c 咚sa n dm a i n t a i nt h ea c c u r a t es t a t eo ft h en e t w o r kt h r o u g hd i s t a n c ev e c t o r p r o t o c o lo rl i n ks t a t ep r o t o c 0 1 h o w e v e r , i nt h ea c t u a ld y n a m i cn e t w o r ke n v i r o n m e n t , t h e s t a t eo ft h en e t w o r kw h i c ht h en o d e sc a na c c e s si sn o ta c c u r a t e t h i sn o n - a c c u r a c yo ft h e i n f o r m a t i o no ft h en e t w o r ks e r i o u s l ya f f e c t e dt h ep e r f o r m a n c eo fr o u t i n ga l g o r i t h m t h i sp a p e rb r i e f l yi n t r o d u c e ds o m es o u r c e so fn o n a c c u r a c yo ft h es t a t ei n f o r m a t i o no f t h en e t w o r k , s i m p l yl i s ta n da n a l y z e dt h ec h a r a c t e r i s t i c so ft h ec e n t r a l i z e dr o u t i n ga l g o r i t h m a n dd i s t r i b u t e dr o u t i n ga l g o r i t h m ；t h e nm a d ead e t a i l e da n a l y s i sf o rd i f f s e r va r c h i t e c t u r e a n dt h ep r i n c i p l ea n dt h e o r yo fq o s r o u t i n g a n dp u tf o r w a r da m a t h e m a t i c a lm o d e lf o rt h e a l g o r i t h mo fo o sm u l t i c a s tr o u t i n gi nd i f f s e r vn e t w o r k s ；t h e ne x p a t i a t et h ec h a r a c t e r i s t i c s o fs o u r c er o u t i n ga n dd i s t r i b u t e dr o u t i n gi ng e n e r a l l a t e rw ee n u m e r a t ea n da n a l y z es e v e r a l d i s t r i b u t e dq o sr o u t i n gi ng r e a td e t a i l s a f t e rf i n d i n gd e f e c t so ft h e s ea l g o r i t h m s ，w e p r o p o s e dan e wt i c k e t - b a s e dm u l t i p a t hd i s t r i b u t e dq o sr o u t i n ga l g o r i t h mn a m e dr - d q m r t oi m p r o v et h en e t w o r kp e r f o r m a n c ec a na l s or e d u c et h ei m p a c to fn o n a c c u r a c yo nt h e r o u t i n ga l g o r i t h m i n t h e a l g o r i t h m ，e v e r yn o d eo n l yn e e dt o m a i n t a i nl o c a ls t a t e i n f o r m a t i o no fi t sl i n k s ，t i c k e ti su s e dt od e c r e a s et h ee x t e n s i o no ff l o o d i n g ，w h i l e m u f t i - p a t hc a ni n c r e a s et h ep r o b a b i l i t yo ff i n d i n gt h ef e a s i b l ep a t h s w eu s e dt h em e t h o do f “s o f t - s t a t e ”t oe l i m i n a t et h e i m p a c to fd y n a m i cc h a n g eo fr e s o u r c ei n f o r m a t i o n t h e 1 l t 东北大学硕士学位论文 a b s t r a c t i n n o v a t i o ni st h a tw ea n a l y z e dt h ec h a r a c t e r i s t i c so fm u l t i c a s tr o u t i n gi nd i f f s e r vn e t w o r k s u n d e ru n c e r t a i nc o n d i t i o n ，a n ds o l v e dt h ep r o b l e mo f “o v e r - r e s e r v a t i o n ”r d q m rc a n e l i m i n a t e dt h ei m p a c to fd y n a m i cc h a n g eo fr e s o u r c ei n f o r m a t i o n ，s ot h a ti m p r o v e dt h e s u c c e s sr a t i o i nt h ee n d ，w er e a l i z e dr d q m ri nv i r t u a ln e t w o r ke n v i r o n m e n tw h i c h e s t a b l i s h e dw i t hcl a n g u a g e s i m u l a t i o nr e s u l t sr e v e a l e dt h a tr - d q m ri m p r o v e dt h e s u c c e s s r a t i o ，o p t i m i z e dt h ea v e r a g ec o s ta n da d d e dl e n g t ho fp e re s t a b l i s h e dp a t h k e yw o r d s ：u n c e r t a i nc o n d i t i o n ；q o s ；m u l t i c a s t ；d i s t m b u t e dr o u t i n g ；d i f f e r e n t i a t e ds e r v i c e s i i v 东北大学硕士学位论文目录 目录 独创性声明一 摘要i i a b s t r a c t m 第一章绪论1 1 1 课题背景1 1 1 1q o s 组播问题1 1 1 2 网络信息的非精确性2 1 2 国内外相关领域技术研究现状3 1 3 论文组织结构3 第二章d i 由s e 体系下q o s 路由算法的特点分析5 2 1d i 五f s e r y 模型特点5 2 1 1d i f f s e r v 模型概述5 2 1 2d i f f s e r v 体系结构。6 2 1 3d i f f s e r v 模型的工作过程7 2 1 4d i f f s e r v 模型的特点总结。8 2 2 流量整形技术8 2 3 流量控制技术9 2 3 1 队列管理的功能及其意义：一1 0 2 3 2 分组调度的功能及其意义1 1 2 4 面向区分服务体系的队列管理与分组调度算法分析1 1 2 4 1j o b s 算法描述1 2 2 4 2j o b s 算法对带宽、延迟、丢失率的保证方法1 3 2 5 本章小结。1 4 第三章d i 鼬体系下的q o s 组播路由算法 3 1 组播路由基本理论1 5 3 1 1 路由算法1 5 3 1 2 组播路由问题的q o s 约束1 8 3 1 3 组播路由问题的分类1 9 3 2 集中式路由算法与分布式路由算法。2 0 3 3 网络模型与q o s 组播路由问题数学描述2 1 3 4d i f f s e r v 体系下q o s 组播路由算法模型2 1 3 5 本章小结2 2 v 东北大学硕士学位论文 目录 第四章基于t i c k e t 的分布式多路径o o s 组播路由算法2 3 4 1 分布式路由算法特性分析2 3 4 1 1 通用的分布式q o s 路由算法2 3 4 1 2 分布式o o s 多路路由算法2 4 4 2 一种新的多路组播路由算法r d q m r 2 6 4 2 1 新算法r d q m r 基本思想2 6 4 2 2 算法r d q m r 具体描述2 7 4 3r d q m r 算法时间复杂度分析2 9 4 4 本章小结3 0 第五章r d q m r 算法模拟实验设计与实现3 1 5 1 实验的总体设计3 1 5 2 网络仿真环境的构建3 1 5 2 1 随机网络拓扑的建立“3 1 5 2 2 网络基本功能实现3 3 5 2 3 网络环境仿真方法流程。3 4 5 3r d q m r 算法的实现3 4 5 4 分组并行处理的实现3 9 5 5 源节点的随机选取和组播组的随机构造3 9 5 6 实验设计及结果分析3 9 5 6 1 实验设计。3 9 5 6 2 程序流程j 4 0 5 6 3 实验结果与分析4 2 5 7 本章小结4 6 结束语 参考文献 致谢 v i 4 7 4 9 5 1 l 东北大学硕士学位论文第一章绪论 1 1 课题背景 1 1 1q o s 组播问题 第一章绪论 众所周知，传统的尽力而为m e s t e f f o r t ) 网络无法向多媒体通信应用提供带宽、 延迟、丢失率、抖动等方面的有保证的服务。发展面向连接的、有服务质量保证的传 输结构是下一代网络的必然趋势。q o s 这个概念描述了发送和接收信息的用户之间以 及用户与传输信息的网络之间达成的关于服务质量的约定。为了获得有保证的服务， 用户必须对其请求的通信量的q o s 进行描述，将其转变为一系列的约束条件，包括带 宽、延迟、丢失率、抖动等指标的大小限制。另一方面，提供服务的网络有一个接纳 控制机制，这个机制根据事先确定好的接纳控制准则对每一个o o s 请求作出接纳判 决。如果当前网络的资源足以满足这个请求，则接纳成功；否则，接纳失败，需要再 次协商以调整0 0 s 请求并再次进行接纳控制，或者拒绝请求。 具有q o s 保证业务的实施必须在面向连接的网络体系中进行。现今最著名的q o s 网络体系结构是在上个世纪9 0 年代由i e t f 提出的集成服务( i n t e g r a t e ds e r v i c e s ， i n t 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 ，d i f f s e r v ) 模型。i n t s e r v 通过维护每 个数据流的状态来实现绝对的q o s 保证，但这却导致i n t s e r v 的可扩展性和稳健性都 比较差，不适合在大型网络中实施l ，d i f f s e r v 通过将复杂的计算放在边缘节点完成 以减轻核心节点的负担、服务对象为流聚集( s t r e a ma g g r e g a t e ) 而非单个流等措施又克 服了i n t s e r v 模型的主要缺点，并能对q o s 提供比较好的保证。而与近些年兴起的m p l s 技术的结合进一步使d i f f s e r v 模型具有更强的优势。因此，d i f f s e r v 是目前最适合承 载q o s 业务的网络体系结构。 组播( m u l t i c a s t ) 技术是在2 0 世纪8 0 年代由美国斯坦福大学的s t e v e nd e e r i n g 博 士提出的。组播是实现点到多点通信的一种方式。在发送数据之前先建立一棵以源节 点为根、包含所有目的节点的树型路径。发送端只发送一份数据，数据沿树的主干传 输，在分叉处复制，向各个分枝传送，最终到达目的节点。利用组播实现点到多点通 信与单播和广播方式相比能节省大量的带宽资源，减轻网络的负担。组播的有效性已 经得到了越来越多的理论和实践的支持。组播路由的作用就是建立传输数据的树型路 径组播树。 组播技术在未来的网络中将占有十分重要的地位。随着网络技术的不断发展和多 媒体技术的广泛应用，用户对网络服务质量( q o s ) 不断提出更高的要求。所以，能够 】 ，j 东北大学硕士学位论文 第一章绪论 实现q 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 组播路由技术的研究对于将来多媒体应用在互联网上的开展具有极其重要的意义。 1 1 2 网络信息的非精确性 当前q o s 路由研究的主要难点有：n p 完全问题、多业务并存、节点状态信息存 储量大、网络状态信息不精确【2 j 。这些问题无论在单播路由还是组播路由中都存在， 本文研究的主要问题就是如何减少网络状态信息的非精确性对组播路由算法的影响。 大多数已提出的路由算法都假设网络中的每个节点能够通过距离矢量协议或者链 路状态协议获得并保持网络全局的精确状态。然而在实际的动态网络环境中，节点所 能获得的网络个局状态并不是精确的。造成所获状态不精确的原因主要有【3 】： 1 ) 网络信息的动态变化：由路由信息协议完成的对网络资源信息的更新可能基于 网络的平均状态或最坏情况。无论是哪种情况，发布的参数都是不精确的。这种不精 确性可以通过快速地发布当前最新的、精确的状态信息来消除。不幸的是，当网络处 于高度动态中且变化频繁时，上述策略是不切实际的。因此，所发布的值应该被认为 是不确定的。每个值所服从的精确的概率分布函数依赖于关于信息更新的频率和网络 的动态性的先验知识； 2 ) 大型网络的分层机制：在互联网中，随着信息快速增长，使得维持关于所有节 点和链路的精确信息变得在实践上不可行。可获得参数的语义取决于所使用的收集信 息的方法，例如，可以考虑在平均、最好、最坏的情况下的参数值。一些信息收集机 制可能为每个参数公布一个可能的范围，参数可以被看作是在这个范围内服从均匀分 布的随机变量。其它的机制可能设定不同的概率分布，并公布与这些分布有关联的特 定参数，如均值和方差。 3 ) 信息的隐藏：互联网可能包含隐藏其部分或全部信息的私有网络。这样做的原 因之一是隐藏网络内部的私有机制。这些网络通常会发布一些不精确的信息或公布一 些特定参数的范围。我们可以利用这些信息，并根据由这些网络提供的参数或经验构 建概率分布。在子网中隐藏信息的第二个原因可能是保持内部路由选择的一些自由度。 对于每一个请求，子网可以自由地选择任何满足o o s 要求的内部路径。网络可以公布 路径满足q o s 要求的可能性，这种情况下q o s 参数可看作是随机变量。 计算的近似性：即使“精确的”节点和链路参数也不能认为是真正准确的，通 常它们只是真实的参数和数值的近似，因为它们所依赖的模型无法完全描述设备的复 2 l 东北大学硕士学位论文第一章绪论 杂性。那些计算出来的参数通常是些不精确的假设的上限或拟合。所以计算的近似 性是公布参数的非精确性的另一个来源。 本文将仅存在特性1 ) 的网络环境称之为非确定环境。 1 2 国内外相关领域技术研究现状 1 9 9 7 年，g u e r i n 和o r d a 等人首次提出了网络状态信息非精确的概念和基本研究 模型【4 j 。他们又研究了在非确定环境下带宽受限和延迟受限的路由问题，提出了基于 概率分布的非精确信息模型和路由算法【列。带宽受限算法的目标是找到一个满足请求 带宽概率最高的路径，延迟受限路由算法的目标是找到一个满足端倒端延迟需求概率 最高的传输路径，这是一个n p - h a r d 问题，这两种算法都是集中式路由算法。在组播 路由方面，l o r e n z 和o r d a 采用将所有源一目的节点对的端到端延迟需求分解到组 播树中的每条链路的方法，以提高组播路径建立的成功率1 6 l 。 国内关于非精确网络状态信息的研究刚刚起步。文献f 7 1 指出研究在链路状态不精 确的情况下多路径q o s 路由是未来的重要工作之一。文献【8 1 用概率模型描述网络非确 定特性，并基于该模型提出了一种q o s 路由算法。文献【9 】描述了非确定环境下的路由 问题。随着网络规模的增长，网络元素的非确定性也会自然地增长。选路必须依赖近 似的信息，使所选择的路径仍能满足q o s 。提供必要信息的有效参数语义依赖于所使 用的描述方法，可使用均匀分布、正态分布的一个可能范围或最佳值。路径选择过程 的目标之一就是选择一条满足q o s 的路径，与链路状态值相联系的概率分布取决于未 来修改和网络动态行为的知识。对于广泛的概率分布，这个问题的求解是不可能的。 在实施非精确信息选路时，可以考虑将端到端延迟限制分解为局部限制，以便建立有 效的算法，然后结合链路状态值的概率分布来考虑路由的综合优化问题。文献f 1 0 1 提 出了一种基于t i c k e t 的q o s 单播路由算法，该算法使用资源预约方法来消除非确定环 境对q o s 路由算法的影响。 以上分析说明多数现有的非确定环境下的路由算法旨在“削弱 非精确信息对算 法的影响，它们都无法消除这种影响。另外，这些算法的目标都是保证所建立路径的 端到端q o s ，仔细分析之下会发现，它们的应用背景都是集成服务( i n t s e r v ) 网络， 因为只有i n t s e r v 网络才能建立这些算法得出的q o s 路径。而i n t s e r v 网络已经被证 实不适用于中大型网络，当前性能最好的q o s 实现模型是区分服务( d i f f s e r v ) 模型。 目前尚未见到d i f f s e r v 体系下适用于非确定环境的路由算法。 1 3 论文组织结构 本文内容安排如下： 3 东北大学硕士学位论文第一章绪论 第一章绪论。阐述课题意义、研究现状、面临的问题及路由方法的一些选择。 第二章d i f f s e r v 体系下q o s 路由算法的特点分析。介绍d i f f s e r v 体系的结构、特 点以及面向区分服务的缓存管理和分组调度算法，并以此算法为例分析了d i f f s e r v 体 系下q o s 路由算法的特点。 第三章d i f f s e r v 体系下的q o s 组播路由算法。形式化描述q o s 组播路由问题， 介绍q o s 组播路由的模型。 第四章基于t i c k e t 的分布式多路径q o s 组播路由算法。描述了本文提出的 r d q m r 算法的原理与实现方法，分析了该算法的时间复杂度。 第五章r d q m r 算法模拟实验设计与实现。阐述了实验原理，设计了四个实验， 在模拟的非确定网络环境下测试r d q m r 算法的成功率等性能，并对结果数据进行 分析。 最后为结束语。对论文工作进行总结，说明新算法的创新点及优越性，并对今后 工作给予展望。 4 东北大学硕士学位论文第二章d i f f s e r v 体系下q o s 路由算法的特点分析 第二章d i f f s e r v 体系下q o s 路由算法的特点 分析 2 1d i f f s e r v 模型特点 2 1 1d i f f s e r v 模型概述 针对1 1 q o s 问题的解决，匝t f 提出了两种基本模型，即集成服务模型1 1 1 】和区分 服务模型1 1 2 j 。i n t s e r v 模型以每个流( 单独的或聚集的) 为基础，除了原来的“尽力而 为 型服务以外，提供了两种端到端的面向实时传输的服务类型：质量保证型服务 ( g u a r a n t e e ds e r v i c e ) i 1 3 j 和可控负载型服务( c o n t r o l l e d 1 0 a ds e r v i c e ) 1 1 4 l 。其原理是对于 每一个需要进行q o s 处理的数据流，通过一定的信令机制( 通常使用r s v p 信令【”1 ) ， 在其经由的每一个路由器上进行资源预留，以便实现端到端的q o s 业务。但是这种模 型存在可扩展性，对网络中所有路由器有信令协议的限制，以及信令系统复杂等问题。 目前业界已经取得了比较一致的意见，即i n t s e r v 模型应当应用于网络规模较小、业务 质量要求较高的边缘网络，如企业网、校园网等。 为了克服i n t s e r v 模型的不足，进一步解决骨干网络上的q o s 问题，业界提出了 d i f f s e r v 模型，目的是在因特网上为流量提供有区别的业务级别，其基本实现方法是 将所有复杂功能都布置在网络边界，而在核心节点仅仅实现快速转发功能【1 6 1 。与 i n t s e r v 模型不同，d i f f s e r v 模型中并不在网络节点中为每个数据流预留资源，它将所 有的数据流区分成数量有限的几个汇聚流，并在网络核心节点只保存汇聚流的状态信 息，而不是单流的状态信息，从而克服了可扩展性问题。可以看出，d i f f s e r v 模型是 一种适合于大型路由器网络的集中式通信量处理机制，提供的是一种粗粒度的q o s 保 证。 d i f f s e r v 将流量分成少量等级并按每个等级分配网络资源，从而解决o o s 问题。 为了避免采用信令协议，d i f f s e r v 模型利用了i p v 4 头中的服务类型( t y p eo fs e r v i c e ， r o s ) 字段或i p v 6 头中的业务量类型( t r a f f i cc l a s s ) 字段。以i p v 4 为例，d i f f s e r v 将 t o s 字段改名为d s 字段，其中6 b i t 有效，作为区分服务编码点( d i f f e r e n t i a t e ds e r v i c e s c o d ep o i n t ，d s c p ) 字段，直接在数据包上标记等级。d s 字段的编码如图2 1 所示。 d s c p 决定网络中特定节点上数据包的q o s 行为，称之为逐跳行为( p e r - h o p b e h a v i o r ，p h b ) ，按照数据包的调度和丢弃优先级来表示。从实施的角度看，p h b 可看成是用于转发的数据包队列、当队列超出限制条件时的丢弃可能性、分配给每个 5 东北大学硕士学位论文 第二章d i f f s e r v 体系下q o s 路由算法的特点分析 队列的资源( 缓冲和带宽) 、以及为一个队列服务的频率。除了“尽力而为”的服务 类型外，d i f f s e r v 模型还定义了另外两种服务类型：确保服务( a s s u r e ds e r v i c e ，a s ) 和 奖赏服务( p r e m i u ms e r v i c e ，is ) 。对应各种服务级别，目前m t f 已经定义了1 4 个 p h b ，包括快速转发( e x p e d i t e df o r w a r d i n g ，e f ) p h b 1 7 1 ，确保转发( a s s u r e d f o r w a r d i n g ，a f ) p h b 1 8 】和尽力而为( b e ) p h b ，同时也允许i s p 自行定义具有本地意 义的映射关系。 、 f 0l2345 67 1 一 一一一 一 _ 一+ l d s c p l c u i - - - 一i iiiiiii 2 1 2d i f f s e r v 体系结构 图2 1 d s 字段编码格式 f i g 2 1d sf i e l de n c o d i n gf o r m a t 区分服务体系结构【1 9 l 一般由3 个元素组成：分类单元( p a c k e tc l a s s i f i e r ) 、流量 调节单元( t r a f f i cc o n d i t i o n e r ) 、每跳转发行为p h b ，一般分类单元和业务调节单元 位于区分服务域的边界，而p h b 位于核心路由器中。 图2 2 区分服务边缘路由器分类调节功能模块 f i g 2 2t r a f f i cc o n d i t i o n e ra n dp a c k e tc l a s s i f i e rf u c t i o ni nb o u n d a r ym u t e r 分类单元：分类单元一般位于区分服务网络的边界，根据输入数据包头部的某些 域对数据包进行分类。目前有两种分类单元：行为聚合( b e h a v i o r a g g r e g a t e ，b a ) 分 类单元以及多字段( m u l t i f i e l d ，m f ) 分类单元。前者只根据数据包中的d s c p 字段 进行分类，而后者可根据数据包头部中多个域( 如源地址、目标地址、协议标识、源 端口号以及目标端口号等) 的组合来进行分类。 流量调节单元：业务调节单元根据预先定义的t c a 对己分类的分组进行调节， 一般包括如下四部分： 计量单元：度量数据流的时间属性； 标记单元：设置分组头的d s c p ，并将标记了的报文添加到特定的d s 行为聚 集中； 6 东北大学硕士学位论文 第二章d i f f s e r v 体系下q o s 路由算法的特点分析 调整单元：延时一个业务流的分组，使其符合预先定义的数据流规范； 丢弃单元：基于预先定义的规则丢失不符合数据流规范的分组。 通过在上游网络和下游d s 区域之间建立服务等级协议( s e r v i c el e v e l a g r e e m e n t ，s 或流量调节协议( t r a f f i cc o n d i t i o n i n ga g r e e m e n t ，t c a ) ，区分服 务可以扩展到多个d s 区域。边界节点根据t c a 对入域流或出域流进行调节，以确保 入域流或出域流符合t c a 中所规范的要求，标记数据流的d s c p 值，并将其加入相 应的行为聚集b a 。 2 1 3d i f f s e r v 模型的工作过程 进入d i f f s e r v 区域的数据流在网络边界节点首先被分类和调节，并归入到不同的 行为聚集中。每个行为聚集用一个d s c p 值来标明。内部核心路由器在调度转发妒包 时以汇聚流为服务对象，报文以与d s c p 相对应的p h b 进行转发。 为了从i s p 那里获得区分服务，并说明希望得到的性能和特性，客户必须和i s p ( i n t e r a c ts e r v i c ep r o v i d e r ) 签订s l a ，而i s p 之间也必须建立t c a 。s l a 规范了i s p 对客户网络所支持的业务类别以及每种类别的数据流数量，t c a 则规范了i s p 之间的 数据流应该满足的一些约定。以图2 - 3 示例来说明d i f f s e r v 实现的基本过程，假设客 户网络己经和i s p 签订了相应的s l a ，i s p 之间也建立了t c a 。某个时刻，客户网络 a 中的某台主机想要向客户网络b 中的某台主机发送数据流，则客户网络中的主机发 送数据包，数据包在客户网络中路由到达与它直接相连的i s p 网络n l ，边界路由器 e 1 根据客户网络与i s p 之间的s l a 通过查看数据包的头部信息对它进行分类、监控、 标记以及整形，以使它符合s l a 。被标记了d s c p 的数据包在n 1 中传输，直到到达 n 1 的出口节点。在n 1 的出口节点，边界路由器根据n 1 与n 2 之间的t c a 对数据流 进行整形，使它符合n 1 与n 2 网络之间的t c a 。数据流依次通过中间的每个i s p ，最 边界路由器对数据包进 行分类并对业务流进行 标记，监控以及整形 图2 3 区分服务网络 f i g 2 3d i f f s e r vn e t w o r k 7 东北大学硕士学位论文第二章d i f f s e r v 体系下q o s 路由算法的特点分析 后到达接收端客户网络。 总的来说，d i f f s e r v 为流量提供不同的转发处理，从而为不同的流量执行特定的 q o s ，是一种可扩展的解决方案，不需要在网络核心基于流信令和状态进行维护。但 d i f f