（计算机应用技术专业论文）基于簇的组播接收端分组算法研究.pdf

taj 乙! ，+。”。强璧嚣艘”霉重摹一 at h e s i sf o rt h ed e g r e eo fm a s t e r i nc o m p u t e r a p p l i c a t i o n st e c h n o l o g y s t u d yo fm u l t i c a s tr e c e i v e r sg r o u p i n g a l g o r i t h mb a s e d o nc l u s t e r b yl i uy a n g q i a n 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 rx i al i n o r t h e a s t e r n u n i v e r s i t y d e c e m b e r2 0 0 7 ，l卜一吁，一 i，t-r， ，、0、 啼一毛、一一- 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：；，1 i 匀色 签- 7 日期：砷万7 ，2 7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位敝储签名：亨1 f 也导师签名：慰7 签字1 9期 ：u 加矛7 t2 签字日期： 2 卯8 立 走“1小，嚣 东北大学硕士学位论文摘要 基于簇的组播接收端分组算法研究 摘要 随着网络技术的发展，如视频点播，远程教育等多媒体业务大量涌现。此类业务占 用带宽较高，并具有“点对多点 或“多点对多点 的特征。采用组播技术，可以有效 的利用带宽，满足实时多媒体业务的需求。为了提高组播的效率，在一个组播会话内通 常有多个组播组。如何对接收端进行分组，并设定各个组播组的带宽是个重要的问题。 本文主要讨论组播分组的公平性问题。 本文介绍了个体接收端公平性评价函数，阐述了评价一个组播会话公平性的两个标 准社会福利和最大最小会话内公平性。采用簇的思想，根据数据接收能力对会话内 的接收端进行分组，将接收能力接近的接收端划分为一个组播组。通过比较接收端之间 的数据接收能力，通过一定的策略，对接收端进行合并，从而减少接收端的总数量。当 剩余接收端的数量与所设定的分组数量相同时，分组完成。此算法的优势在于合并过程 中有多个可以根据实际情况灵活调整的部分，可以更好的适应业务的要求。接收端的合 并也可以作为其他分组算法的预处理过程，减少参与算法的接收端数量，提高执行效率。 在与实际网络拓扑结合的过程中，本文提出的算法采用了一种逐层递进的方式，解决了 现有一些算法与拓扑脱节的问题。 本文首先介绍了服务质量和组播相关内容及公平性评价标准；其次，提出了一种基 于簇的组播接收端分组算法，并对一种现有的接收端分组算法的执行效率进行改进；最 后，使用m a t l a b 对上述三种接收端分组算法进行仿真与分析。 关键词：组播；公平性；接收端分组算法 i i 1馨箩、，】何 盘覆i 飞， t s t u d yo fm u l t i c a s tr e c e i v e r sg r o u p i n g a l g o r i t h mb a s e do n c l u s t e r a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to ft h en e t w o r kt e c h n o l o g y , s o r e e n e wt ) ，p em u l t i i i l e d i a t r a f f i c sc o m ei n t ob e i n g ，s u c ha sv i d e o - o n - d e m a n da n dd i s t a n c ee m l c a t i o n t h e s e 由r a l 所c s u s 砸l l yh a v et h ec h a r a c t e r so f ”p o i n tt om u l t i p o i n t ”o r ”m u l t i p o i n tt om u l t i p o 硫”a n dn e e d 1 1 i 曲- b a n d 、析拙m u l t i c a s tc o m m u n i c a t i o na c h i e v e ss c a l a b i l i t yb ys e n d i n gd a t at 0 姐d t i p l e r e c e l v e r sa tt h es a m et i m e i no r d e rt oi m p r o v e e f f i c i e n c y , t h e s ea r em o r et h a no n e 毋? o u pi 1 1a m u l t i c a s ts e s s l o n i t s i m p o r t a n tt h a th o wt od i v i d er e c e i v e r si n t o g r o u p se x a c f l ya n ds e t a p p r o p r i a t eg r o u pr a t e s t h i sp a p e rm a i n l yd i s c u s s e df a i r n e s so ft h e m u l t i c a s tg r o u p i n g p r o b l e m 。 t w of a i r n e s se v a l u a t i o nc r i t e r i aa r ei n t r o d u c e d ，s o c i a lw e l f a r ea n dm a x m i i l i 玎仃a s e s s i o n 协m e s s an e wg r o u p i n gm e t h o di s p r o p o s e d ，c a l l e dr e c e i v e r sm e r g i n gm 础o d ，r m mf o r s h o r t b a s e do nc l u s t e rr e c e i v e r sa r ed i v i d e di n t o g r o u p sb yt h ec a p a b i l i t yt or e c e i v ed a t a u n d e rs o m es t r a t e g i e s ，t h et o t a lo fr e c e i v e r s d e c r e a s e sb ym e r g i n gp r o c e s s g r o u p i n gi s f i m s h e dw h e nt h en u m b e ro fr e c e i v e r si s e q u a lt ot h en u m b e ro ft h ei n t e n d i n gg r o u p s s o m c t r a c h e ao ft h er m mi s f l e x i b l e ，s oi tc a na d a p tt h ea c t u a ls i t u a t i o nb e t t e r r m mc a nb e u t l l l z e d 舔p r e p r o c e s s i n gp r o c e s sf o ro t h e rg r o u p i n gm e t h o d s i tc a nr e d u c et h en u l l l b e ro f r e c e l v e r sd i s p o s e db ya l g o r i t h m r e c u r s i o ni sa d o p t e d t od e a lw i t ht h ei s s u ew h e nt h er m m i su s e di nn e t w o r k t o p o l o g y i nt h i sp a p e r , q o s ，m u l t i c a s ta n df a i r n e s se v a l u a t i o nc r i t e r i aa r ei 廊o d u c e da tf i r s t t h e l l - an e w g r o u p l n ga l g o r i t h mi sp r o p o s e db a s e do nc l u s t e r s o m ei m p r o v e m e n t sl 娜eb e e nd o n e t oa ne x l s t m gg r o u p i n gm e t h o d a tl a s t ，t h r e eg r o u p i n gm e t h o d sa r ec o m p a r e da i l da 1 1 a l v z e d b y m a t l a b k e y w o r d s ：m u l t i c a s t ，f a i m e s s ，r e c e i v e r sg r o u p i n ga l g o r i t h m i i i 1；藿-枣，l【rr 东北大学硕士学位论文 目录 目录 独创性声明i 摘要 a b s t r a c t i i i 第一章绪论1 1 1 研究背景1 1 2 国内外现状1 1 3 本文研究的主要问题3 1 4 论文组织结构3 第二章服务质量与组播概述及相关工作5 2 1 服务质量5 2 1 1 概述5 2 1 2 体系结构。7 2 1 3 实现机制：l l 2 2 组播技术1 2 2 2 1 概述1 2 2 2 2 组播地址一1 4 2 2 3 组播路由算法1 4 2 2 4 组播路由协议l6 2 3 相关研究工作1 6 2 3 1 最大最小公平性1 6 2 3 2 多速率最大最小公平性1 6 2 3 3 多组播组1 7 2 3 4 接收端间公平性17 2 3 5 最大最小会话内公平性1 7 2 3 6 多条件服务质量组播路由算法：1 7 第三章公平性评价标准19 3 1 个体接收端性能度量1 9 3 2 社会福利21 3 2 1 概述2 1 3 2 2 评价函数2 2 3 3 最大最小会话内公平性2 3 一一 东北大学硕士学位论文 目录 3 3 1 概述2 3 3 3 2 评价函数一2 3 第四章组播接收端分组算法2 5 4 1 接收端合并方法。2 5 4 1 1 核心思路2 5 4 1 2 合并策略2 6 4 1 3 合并算法2 9 4 1 4 拓扑应用3 3 4 1 5 j 、结3 6 4 2 现有分组方法改进3 6 4 2 1 最大最小会话内公平性算法简介3 6 4 2 2 效率改进3 8 第五章仿真及结果分析4 3 5 1m a t l a b 简介4 3 5 2 公平性比较4 5 5 2 1 均匀分布4 6 5 2 2 指数分布j 4 8 5 3 拓扑比较5 0 5 4 效率比较5 l 第六章结论5 3 参考文献5 5 致 射。5 9 一v 一 。童，l【lld 东北大学硕士学位论文第一章绪论 第一章绪论弟一早瑁v 匕 本章首先描述课题的来源、研究背景、国内外现状，并简要概括本文研究的主要问 题，最后介绍全文的内容安排。 1 1 研究背景 1 9 6 9 年，i n t e m e t 的前身a r p a n e t 投入使用，标志着现代计算机网络的诞生【1 1 。在 以后的几十年时间里，互联网以越来越快的速度不断向前发展。网络的规模和用户数量 持续增长，新的网络技术和网络设备陆续投入使用。随着互联网的发展，产生了诸如视 频会议、视频点播、i p 可视电话、远程教育、大型多人在线网络游戏等新型的分布式多 媒体应用。这些新的应用大多具有“点到多点 或“多点到多点”的特征，不但对网络 有带宽有很高的要求，而且要求信息传输的低延迟和低抖动，同时，这些应用大都能容 忍一定程度的信息丢失和错误。传统的分组交换网络，是面向如f t p 和e m a i l 等的“点 对点”非实时数据通讯而设计的，采用的t c p i p 协议，主要是为了优化整个网络的数据 吞吐量并保证数据通信的可靠性。t c p i p 协议族是一种无连接的、基于数据分组的传 输模式，所提供的是一种“尽力而为( b e s t - - e f f o r t ) ”的服务，不能保证数据传输的实 时性、完整性以及到达的顺序，无法保证吞吐量和传送时延等服务质量要求。为了满足 新型分布式多媒体应用对带宽、延迟、抖动和分组丢失率的要求，提出了网络服务质量 ( q u a l i t yo f s e r v i c e ，简称q o s ) 技术【2 】。采用资源预留、设定优先级和流量工程( t r a f f i c e n g i n e e r i n g ，简称t e ) 等方式实现q o s ，提供端到端的服务质量控制和保证，使网络应 能够区分出不同的通信并为之提供相应的服务，根据用户要求分配和调度资源 3 1 。根据 新型分布式多媒体应用“点到多点或“多点到多点”的特征，采用i p 组播( m u l t i c a s t ) 技术，能够有效利用现有带宽资源，在不改变当前网络结构的前提下，即使集群用户大 量增加，主干网络的带宽需求也没有大的增长。服务质量技术与口组播技术相结合， 在使用组播的同时，满足服务质量参数要求，实现流量工程，是现阶段处理新型分布式 多媒体应用较好的办法吲。 1 2 国内外现状 2 0 世纪8 0 年代初期，尽管网络的性能还比较低，提供的服务种类也比较少，但计 一1 一 东北大学硕士学位论文第一章绪论 算机网络q o s 的研究已经开始了。受到计算机网络性能限制，早期的q o s 研究集中在 数据流传输的正确率、吞吐量和延迟等单一服务质量评价与控制方面。直到宽带网络的 出现和分布式多媒体应用的急速增加，才开始系统地对q o s 管理和控制进行深入研究 2 1 。从1 9 9 7 年开始i e t f ( t h ei n t e m e te n g i n e e r i n gt a s kf o r c e 互联网工程任务组) 制定 了有关q o s 的一系列r f c ( r e q u e s tf o rc o m m e n t s ) 标准，提出了多种服务模型和机制 来满足对q o s 的需求，其中比较典型的有：有保证的q o s 规范【5 】、综合服务资源预留 ( i n t s e r v r s v p ) 【6 8 1 、区分服务( d i f f s e r v ) 【9 1 、多协议标记交换流量工程( m p l s t e ) 【1 0 1 1 1 、子网带宽管理( s u b n e tb a n d w i d t hm a n a g e ，简称s b m ) 1 2 1 和约束路由技术 ( c o n s u a i n t b a s e dr o u t i n g ，简称c b r ) 1 1 1 等，均用于解决i n t e m e t 网络的q o s 控制和 管理。在众多的解决机制中，d i f f s e r v 和m p l s 是目前业界普遍看好的解决未来碑骨干 网络中q o s 问题的基本技术，但是i pq o s 的实现本身需要多层次和多平面的结合，各 种机制的结合成为现今i pq o s 实现和研究的重点。 1 9 8 9 年，i e t f 通过r f c l l l 2 ，定义了i n t e m e t 上的组播方式【1 3 】。历经2 0 多年的研 究和发展，p 组播已经形成了较为完整的组播协议体系，包括组播主机和网络的交互协 议、组播路由协议、组播的地址管理协议等。组播路由协议是i p 组播协议体系中最核 心的功能。p 组播路由协议的发展分成域内( i n t r a - d o m a i n ) 和域间( i n t e r - d o m a i n ) 两 个阶段：最初的m 组播路由协议将网络看成没有层次结构的平面网络，组播路由算法 采用广播方式交互协议消息，因而只能应用在婵网络的路由自治域内，称为域内路由 协议：域问路由协议的出现是为了解决在大型的、分层的p 网络中组播路由问题，大 型i p 网络采用自治域结构形式组织网络，域问路由协议解决了分层结构网络的组播路 由问题【1 4 1 。 组播服务质量的研究集中在其实现方式和公平性评价方面。目前实现组播的服务质 量主要有两种方法。一是使用q o s 组播路由【i5 1 ，主要是指在网络中寻找最优路径，要 求在源和目的节点之间，找到一条代价最小同时能够满足多个约束条件的路径。二是在 i p 网络的组播应用中采用综合服务( i n t s e r v ) 、区分服务( d i f f s e r v ) 和多协议标记交换 技术( m p l s ) 等q o s 控制技术【1 6 2 0 1 。组播公平性评价是按照一定的标准，对组播的性 能进行评价。常见的标准有社会福利( s o c i a lw e l f a r e ) 、最大最小公平性( m a x m i n f a i r n e s s ) 等【2 1 1 。对应于上述两个评价标准，存在相应的接收端分组算法，可以得出最 佳的分组方案。组播公平性的研究是一个不断发展的过程，最早提出的最大最小公平性 2 2 1 针对组播和单播之间的资源分配，之后的多速率最大最小公平性( m u l t i r a t em a x m i n 一2 一 、，j一，气llf， 东北大学硕士学位论文第一章绪论 f a i r ) 瞄】和多组播组( m u l t i p l em u l f i c a s tg r o u p s ) 【2 4 1 等在一定程度上解决了接收端之间 接收能力存在差异的问题，接收端之间公平性( i n t e r - r e c e i v e r f a i r n e s s ) 【2 5 1 和会话内公平 性( m a x m i ni n t r a s e s s i o nf a i r n e s s ) 2 1 1 关注各个接收端的性能，多条件服务质量路由 ( m u l t i c o n s t r a i n e dq o sm u l t i c a s tr o u t i n g ) t 2 6 贝i j 是将经济学原理应用到了组播领域。 1 3 本文研究的主要问题 在组播通讯中，属于同一个组播会话的多个接收端在同一时刻接收数据。各个接收 端接收能力之间的差别可能很大，并且由发送端到接收端之间的链路状况也相差很远。 若一个组播会话内只有一个组播组，则属于此会话的所有接收端只能以一个相同的速率 接收数据。如果发送端按接收能力最差接收端的标准发送数据，显然，这对接收能力强 的接收端很不公平。在类似视频点播等多媒体应用中，接收端可以承受一定程度的丢包 率，如果将发送端的数据发送速率设定得比接收能力最差接收端的数据接收速率高一 些，可以提高接收能力强接收端的满意度。在一个组播会话内建立多个组播组，发送端 按照不同的速率向各个组播组发送数据，在一定程度上可以解决组播会话内各个接收端 数据接收能力差别过大的问题。但是，只要分组的数量少于接收端的数量，一定存在如 何将接收端分组，并设定组内数据发送速率的问题。这也正是本文研究的主要问题 在一定的公平性评价标准下，对会话内的接收端进行分组。 1 4 论文组织结构 本文组织结构如下： 第一章绪论。简要描述了研究背景及国内外现状。并明确了研究的主要问题。最后 介绍了全文组织结构。 ，第二章服务质量与组播概述及相关研究工作。介绍了服务质量和组播的相关内容， 为进一步的研究奠定基础。按照时间顺序，介绍了现有的组播分组算法。 7 第三章公平性评价标准。首先介绍个体接收端的性能评价函数，根据实际应用需求 的不同，评价函数有四种不同的形式。其次，阐述评价整个组播会话公平性的两个标准， 社会福利和最大最小会话内公平性标准，并给出相关评价函数及比较规则。 第四章接收端合并方法。本章前半部分提出一种新的组播接收端分组算法接收 端合并方法，详细阐述此方法的核心思路，合并策略，组速率确定等内容，给出算法流 程图与主要函数介绍，并且介绍接收端合并方法与网络拓扑相结合的方式。本章后半部 一3 一 东北大学硕士学位论文第一章绪论 分对现有的会话内公平性分组算法方法进行了改进。通过在算法执行前加入预处理过 程，调整算法内部结构，提高了算法执行效率。 第五章仿真及结果分析。首先介绍仿真工具m a t l a b 概况、历史及特点。然后使 用m a t l a b 7 0 对接收端合并方法，会话内公平性，社会福利等方法进行最小公平性，公 平性和【2 1 】及执行效率等方面的比较与分析。 第六章结论。对整个论文的工作进行总结并展望下一步工作，指出工作中有待改进 的地方，同时指明进一步的研究方向。 4 一 ， -丫，lf曩f，一 东北大学硕士学位论文第二章服务质量与组播概述及相关工作 第二章服务质量与组播概述及相关工作 本章首先介绍了服务质量相关概念、体系结构及实现机制；其次介绍了组播地址、 路由算法及协议；最后介绍了组播分组相关研究工作。 2 1 服务质量 2 1 1 概述 2 1 1 1 定义 q o s ( q u a l i t yo f s e r v i c e ) 即服务质量，在r f c 2 3 6 8 t 2 7 】中描述为：q o s 是网络在传输 数据流时要求满足的一系列服务请求，具体可以量化为带宽、延迟、延迟抖动、丢失率、 吞吐量等性能指标。强调端到端( e n dt oe n d ) 或网络边界到边界的整体性，反应了网络 元素在保证信息传输和满足服务要求方面的能力。 2 1 1 2 分类 为了适应不同的应用对q o s 的不同需求，系统能提供的q o s 服务总体上分3 类【2 8 1 。 ( 1 ) 确定型( d e t e r m i n i s t i c ) q o s 提供“硬 的q o s 保证，确保q o s 要求，不允许有任何的违背，否则可能会造成 严重后果。例如，远程数据医疗中的x 光照片数据传输，必须满足实时，高可靠性的要 求。 ( 2 ) 统计型( s t a t i s t i c a l ) q o s 提供“软”的q o s 保证，允许对q o s 要求有一定的违背，适合准实时系统。例如， 网络多媒体视频点播服务，用户可以容忍一定的误比特率和帧丢失。 ( 3 ) 尽力型( b e s t e f f o r t ) q o s 不提供任何q o s 保证，网络性能将随着负载的增加而明显下降。由于带宽的限制， ， 广域网中的网络化多媒体服务属于此类。 2 1 1 3 参数 不同的多媒体应用，有不同的q o s 描述方法，包含定量( 如吞吐量、容错率、传输 延时和延迟抖动等) 和定性描述( 如服务等级等) 。还可以从不同层次描述q o s ，如基 于应用层的帧率和同步质量等。比较典型的q o s 参数为吞吐量、容错率、传输延时和延 时抖动【2 9 】。 一5 一 东北大学硕士学位论文 第二章服务质量与组播概述及相关工作 容错率( e r r o rr a t e ) ；反映了网络传输的可靠性，可用3 种方法定义：1 位差错率 ( b i tr a t ee r r o r ) ，定义为出错的位数与所传输的总位数之比；2 帧差错率( f r a m er a t e e r r o r ) ，定义为出错的帧数与所传输的总帧数之比；3 分组差错率( p a c k e te r r o rr a t e ) ， 定义为出错的分组数与所传输的总分组数之比。分别用于不同的网络协议层次上计算差 错率。 传输延时( t r a n s m i s s i o nd e l a y ) ：定义为信源发送出第1 个比特信号到信宿接收到 第1 个比特之间的时间差，其中包含信号传播延时和处理延时。另外一个常用的表示延 时的参数是端到端延时，即一组数据在信源终端上准备好发送的时刻，到信宿收到这组 数据的时刻之间的时间差，包括网络接收这组数据的时延( a c c e s sd e l a y ) 、传送这组数 据的时间和网络传输延时3 部分。 延迟抖动( d e l a yj i t t e r ) ：指在一条链接上分组延迟的最大变化量，即端到端延迟的 最大值与最小值之差。抖动产生的原因可能是介质访问时间的变化、流量控制的等待时 间和存储转发机制中的排队时间等。理想情况的端到端延迟是一个恒定值( 零抖动) ， 但是由于网络故障、传输错误以及网络拥塞等原因延迟抖动总是不能避免的。通常，在 接收端设置足够的缓冲区容量可以缓和延迟抖动问题。 吞吐量( t h r o u g h p u t ) ：指有效的网络带宽，定义为物理链路的传输速率减去各种传 输开销，如物理传输开销以及网络冲突、瓶颈、拥塞和差错控制等开销，反应了网络的 最大极限容量。网络的吞吐量是随时间变化而变化的。影响网络吞吐量的因素主要有网 络故障、网络拥塞、瓶颈、缓冲区容量和流量控制等。常见的网络应用对服务质量要求 的严格程度如表2 1 所示。 表2 1 服务质量需求的严格程度 t a b l e2 1h o w s t r i n g e n tt h eq u a l i t y o f - s e r v i c er e q u i r e m e n t sa r e 一6 一 v卜tj-，；， t，；ll乎d 东北大学硕士学位论文 第二章服务质量与组播概述及相关工作 2 1 2 体系结构 q o s 研究的目标是提供有效的端到端的服务质量控制或保证。i e t f 提出了两种不 同的i n t e m e tq o s 体系结构：综合服务( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 【6 1 和区分服务 ( d i f f e r e n t i a t e ds e r v i c e s ，d i 船e r y ) 【9 1 。 2 1 2 1 综合服务 ( 1 ) 概述 i e t f 在1 9 9 4 年提出了i n t s e r v 体系结构，其基本思想是预留资源，如带宽和缓冲 器以及满足业务流所要求的q o s 的优先级 6 1 。在发送数据前需要向网络申请特定的服 务，通知网络它需要的流量参数和特定服务质量请求，包括带宽、时延等。对于每一个 需要进行q o s 处理的数据流，通过一定的信令机制如资源预留协议在其经过的每一个路 由器上进行资源预留，以便实现端到端的q o s 保证。应用程序一般在收到网络的确认信 息才开始发送，并且应用程序的发送速率应该控制在流量参数描述的范围以内。 网络在收到应用程序的资源请求后执行准入控制( a d m i s s i o nc o n t r 0 1 ) 3 0 l ，即基于 应用程序的资源申请和网络现有的资源情况，判断是否为应用程序分配资源。一旦网络 确认为应用程序分配了资源，则只要应用程序的发送速率控制在流量参数描述的范围 内，网络将承诺满足应用程序的q o s 需求。网络根据数据分组中的口地址、端口号和 协议号等信息为进行分类、业务流策略、排队和调度，以实现对应用程序的承诺。 在i n t s e r v 服务模型中，负责传送q o s 请求的信令是r s v p 3 1 1 ，它通知网络应用程 序的q o s 需求。r s v p 是在应用程序开始发送报文之前为该应用申请网络资源的，所以 称作带外( o u t - b i n d ) 信令。r s v p 消息跨越整个网络，假定从接收方到发送方之间沿途 的每个路由器都要为每一个数据流预留资源。沿途的路由器必须为r s v p 数据流维护软 状态。r s v p 在源和目的节点之间可以使用现有的路由协议决定流的通路。r s v p 利用 i p 包承载，采用“软状态 概念，通过周期性的传送p a t h 和r e s v 消息对网络拓扑的 变化做出反映。如果没有了这些消息，r s v p 协议将会释放与之关联的资源。 目前，i n t s e r v 定义的服务类别除了尽力而为服务，还支持2 种类型的服务：有保证 服务( g u a r a n t e e ds e r v i c e ) 3 2 】和负载可控服务( c o n t r o l l e d l o a ds e r v i c e ) 3 3 】。 ( 2 ) i n t s e r v 体系结构 为了实现上面的服务，i n t s e r v 定义了四个功能部件资源预留协议、准入控制、 分类器和调度器。网络中的每个路由器皆需要实现这四个部件。 ( a ) 资源预留协议( r s v p ) 一7 一 东北大学硕士学位论文第二章服务质量与组播概述及相关工作 r s v p 是i n t e m e t 上用于预留资源的信令协议【3 1 1 。通过r s v p ，用户可以给每个业务 流( 或连接) 申请资源预留，要预留的资源可包括缓冲区及带宽的大小。在进行资源预 留时，发送端给接收端发送二个p a t h 消息，说明业务流的特性以及需预留资源的数量。 p a t h 消息同其它d 分组一样，路径上的每个路由器通过路由协议将该消息转发到下一 跳节点，直至终点。接收端在收到p a t h 消息后返回一个r e s v 消息，发起一个逆向资 源预留过程，为该业务流请求所要求的资源。同时，每一个路由器也可以拒绝该r e s v 消息的请求。如果资源预留消息成功返回发送端，则资源预留成功，同时在路由器中建 立相关的流状态信息。否则路由器会给接收端发送一个e r r o r 消息，并终止该信令过 程。 ( b ) 准入控制( a d m i s s i o nc o n t r 0 1 ) 它基于用户和网络达成的服务协议，对用户的访问进行一定的监视和控制。在路由 器上准入控制通过一个算法来判断是否允许一个新的业务流进入网络，而且不会对前 面的业务流的q o s 保证有任何影响。当一个主机请求沿i n t e m e t 中的某个路径进行业务 流数据传输的服务时，每个节点上的准入控制功能都要进行接受拒绝( a c c e p t r e j e c t ) 判断【3 0 1 。 ( c ) 分类器( p a c k e tc l a s s i f i e r ) 根据预置的一些规则，分类器对进入路由器的每一个分组进行分类。这可能需要查 看i p 分组中的某些域m f ( m u l t i f i e l d ) ，如i p 源地址、口目的地址、上层协议类型、 源端口号、目的端口号。7 分类后将每个分组进行标记。分组经过分类和标记以后被放到 不同的队列中等待接受服务【3 4 】。 ( d ) 调度器( p a c k e ts c h e d u l e r ) 它主要是基于一定的调度算法对分类后的分组队列进行调度服务，即负责不同分组 流的转发。属于同一类的所有分组在调度器中将获得相同的服务口5 1 。 ( 3 ) i n t s e r v 的局限性 i n t s e r v 是基于流的、状态相关的体系结构，依赖于每个流的状态和对每个流的管理。 这种实现机制一方面使i n t s e r v 能够提供比状态无关的体系结构具有更高的灵活性和更 好的服务级别保证的服务，但同时也导致了i n t s e r v 的可扩展性问题和鲁棒性问题，后 果是实现复杂，难于应用 2 1 。 目前，只有少量的主机产生r s v p 信令，虽然其数量预计会大幅度增长，当许多应 用却从不产生r s v p 信令，因而实现上修改应用程序的阻力较大。许多应用需要某种形 一8 一 i j 1 ； j jl，i，j 东北大学硕士学位论文第二章服务质量与组播概述及相关工作 式的q o s ，但却无法使用i n t s e r v 模型来表达q o s 请求。必要的策略控制和价格机制尚 处于发展阶段，无法付诸应用。 2 1 2 2 区分服务 ( 1 ) 概述 随着i n t e r a c t 业务的不断扩展，网络资源日益紧张，越来越多的i s p 希望能够在它 们与客户之间建立以服务质量为衡量标准的业务等级协定( s e r v i c el e v e la g r e e m e n t ，简 称s l a ) ，可以根据不同的业务等级提供不同的服务以及收取不同的费用。如对电子医 疗应用而言，传送的精确性比延时和抖动更重要；对于口电话应用而言，抖动和延迟 至关重要，应被尽力减少。因此，在9 0 年代末提出了区分服务( d i f f s e r v 或d s ) 模型 的概念【9 】。 d i f ! 瞎e n ，不需要r s v p 协议，即应用程序在发出报文前不需要预留资源。网络也不 需要为每个流维护状态，而是根据每个分组指定的q o s 来提供特定的服务。可以用不同 的方法来指定分组的q o s ，如口头部的优先级位( i pp r e c e d e n c e ) 、i p 源地址和目的地 址等，网络通过这些信息来进行分组的分类、流量整形、流量监管和队列调度。 在区分服务中区分核心路由器和边缘路由器，在边缘路由器上执行大部分的q o s 实现机制，在核心网内不再考虑复杂的q o s 机制。因为随着网络规模的增加，在核心路 由器上存储转发的任务很重，而边缘路由器的流量小得多。其基本实现方法是：将用户 的数据流按照服务质量要求来划分等级，边缘路由器把q o s 要求相近的流归属于一类 ( p e r - c l a s s ) ，并赋予不同的“行为聚集”( b e h a v i o ra g g r e g a t e ，简称b a ) ，然后利用 i p 分组中的d s 字段( 原t o s 字段) 唯一地标识这类业务，在核心路由器中，以流聚集 为服务对象，根据i p 头部d s 字段中不同的d s c p ( d i f f s e r vc o d i n gp o i n t ) 值提供不同 服务质量的转发处理，这种对不同类型的业务流进行转发的方式，称为p h b ，这样可以 减轻核心路由器的处理量。当网络出现拥塞时，级别高的数据流在排队和占用资源时比 级别低的数据流有更高的优先权，队列溢出时，按照丢弃优先级根据相应的算法进行丢 弃。区分服务只包含有限数量的业务级别，状态信息数量少，实现简单，扩展性较好。 目前，区分服务是业界普遍认同的i p 骨干网的服务质量解决方案团。 ( 2 ) d i f f s e r v 体系结构 虽然d i f f s e r v 仍在不断的发展，一些标准仍在制定、完善之中，但经过几年的发展， d i 髑e r v 的相关概念及模型已经比较成熟，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 sc o d e p o i n t ，d s c p ) 、p h b ( p e r - h o p b e h a v i o r ) 一9 一 东北大学硕士学位论文 第二章服务质量与组播概述及相关工作 服务的定义等已逐步完善。 ( a ) d s 区域( d i f f e r e n t i a t e ds e r v i c e sd o m a i n ) 与d s 区( d sr e g i o n ) d s 区域是有一些相连的d s 节点构成的集合，它们遵循同一的服务提供策略并实 现一直的p h b 组。d s 区域有明确定义的边界，边界有边界节点构成。边界节点连通 d s 区域和非d s 区域【3 8 】。 连续的d s 区域构成d s 区，区内支持跨越若干区域的区分服务。区内的各个区域 可能支持不同的p h b 组，并且在各自区域的d s c p 到p h b 的映射函数也可能不同；如 果有不同的d s 区域，则区域之间必须有s l a 与t c a ( 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 ) 定义域间的调节规则，协调彼此的服务语义。域间边界节点分别对出域与入域流进行调 节以保证其符合s l a 和t c a 的规定。 ( b ) 区分服务标记域与区分服务标记d s c p i p 包头的区分服务标记域是d s 区域的边界节点与内部节点间传递流聚集信息的媒 介。d s 标记域定义为口v 4 包的t o s 字节或i p v 6 包头的流类型字节( t r a f f i cc l a s so c t e t ) 。的前六位。d s c p 是区分服务标记域中的具体值，用来标识数据包所属的流聚集，供数 据包经过d s 节点时选择特定的p h b 。d s 节点上d s c p 到p h b 的映射在具体实现中必 须是可配置的。在定义p h b 时，应同时指定对应d s c p 的推荐值。 ( c ) p h b 在核心路由器中，以流聚集为服务对象，根据口头部d s 字段中不同的d s c p ( d i f f s e r vc o d i n gp o i n t ) 值提供不同服务质量的转发处理，这种对不同类型的业务流进 行转发的方式，称为p h b 。 除了默认的尽力而为服务，i e t f 目前已经定义的p h b 有加速型转发p h b l 3 6 1 和可靠 型转发p h b 组【3 7 1 。 ( 3 ) d i f f s e r v