（计算机系统结构专业论文）多约束qos组播路由优化与仿真.pdf

山东大学硕十学位论文 摘要 随着视频会议、视频点播、远程教育等分布式实时业务的广泛应用，作为其 核心技术的q o s 组播技术引起了人们的高度重视。组播是一种有效的支持多点通 信的机制，它采用树转发结构，每一个数据包只在节点处被复制，在每一条链路 上只发送一次。这种方法使i p 组播能有效的同时向组内的成员发送数据，并支 持大量的组播组。q o s 组播是在满足带宽、延迟、丢包率等多个o o s 约束条件下 进行的组播。q o s 组播路由技术是i n t e r n e t 上流媒体、视频会议等高带宽、共 享型应用的重要基础。 近几年的研究表明，组播路由算法对组播应用的q o s 保障起到了非常关键的 作用，对q o s 组播路由算法的研究已经成为网络研究领域中的一个非常重要研究 方向。在以往的研究中，q o s 组播路由问题常归结为最小费用的约束斯坦立树 ( s t e i n e rt r e e ) 问题，该问题已经被证明是一个n p - c 问题，不存在多项式时 间的解法。随着网络规模的不断扩大和人们对网络服务质量要求的不断提高，研 究新的基于多约束的q o s 组播路由算法，以获得良好的网络服务质量和高的网络 资源利用率，具有十分重要的意义。 本文在对蚁群优化算法和组播问题作深入研究的基础上，提出了可以解决 a dh o c 网络上的q o s 组播路由问题的带方向因子的蚁群算法、基于树的蚁群算 法及其改进算法： ( 1 ) 目前，a dh o c 网络因其优异的特性和特殊的应用，受到越来越广泛的重 视。本文综合考虑了a dh o c 网络的特性、已有的g f s 定位技术以及蚁群算法本 身的特点，在此基础上提出了“方向因子”这个启发式函数，并将方向因子跟蚁 群算法相结合，设计了带方向因子的蚁群算法a c a - o ( a n tc o l o n y a l g o r i t h mc o n s i d e r i n go r i e n t a t i o n ) ，用以解决a dh o c 网络上的o o s 组播问 题。该算法使用方向因子来诱导蚂蚁的搜索行为，使蚂蚁能更加迅速地到达目的 地，从而保证搜索的快速有效性，避免陷入局部最优解。仿真实验结果表明，该 算法提高了执行速度，减少了信息包的发送量，节省了能量开销。 ( 2 ) 本文提出了一种基于树的蚁群算法a c a t ( a n tc o l o n ya l g o r i t h m 山东大学硕士学位论文 b a s e do nt r e e ) 。与传统蚁群算法的先寻找路再合成树的模式不同，a c a t 采用 了以树生长的方式直接寻找组播树的模式。基于树的蚁群算法简化了寻树的机 制，算法的效率得到了提高。仿真实验结果表明，跟传统蚁群算法相比，a c a t 算法能以更快的速度收敛到近似最优解，组成员数目越多，这种优点越明显。 ( 3 ) 专门针对a dh o e 网络，我们对基于树的蚁群算法作了改进，在原算法 基础上添加了重新定义的方向因子。在a dh o e 网络拓扑，改进后的算法能通过 方向因子的诱导作用，使树呈放射状生长，减少树生长过程中的“折回生长”现 象，提高了算法的效率。仿真实验结果表明，跟原算法相比，改进后的算法在 a dh o e 网络上收敛速度更快，效率更高。 关键词：组播；多约束：服务质量( q o s ) ；蚁群优化；方向因子；生长树 i i 山东大学硕士学位论文 a b s t r a c t w i t ht h ee x p a n s i o no ft h ei n t e m e tr e a l t i m ed i s t r i b u t e ds t r e a mm e d i aa n dv i d e o a p p l i c a t i o ns u c ha sv i d e oc o n f e r e n c e ，v i d e oo nd e m a n da n dr e m o t ee d u c a t i o n ，t h e q o sm u l t i c a s tt e c h n o l o g yh a sb e e ng e t t i n gm o r ea n dm o r ea t t e n t i o n i pm u l t i c a s ti sa m e c h a n i s mw h i c hc a r ls u p p o r t sm u l t i - p o i n tc o m m u n i c a t i o ne f f i c i e n t l y i tu t i l i z e sa t r e ed e l i v e r ys t r u c t u r e ，o nw h i c hd a t a p a c k e t sa r ed u p l i c a t e do n l ya tf o r kn o d e sa n d a r ef o r w a r d e do n l yo n c eo v e re a c hl i n k t h i s a p p r o a c hm a k e si pm u l t i c a s t r e s o u r c e e f f i c i e n ti nd e l i v e r i n gd a t at oag r o u po fm e m b e r ss i m u l t a n e o u s l ya n d s c a l a b l ei ns u p p o r t i n gv e r yl a r g em u l t i c a s tg r o u p s t h eq o sm u l t i c a s ti st h es p e c i a l m u l t i c a s tw h i c hs h o u l dg u a r a n t e es o m eq o sc o n s t r a i n t ss u c ha sb a n d w i d t h ，d e l a ya n d p a c k e tl o s sr a t e ，e ta 1 s oq o sm u l t i c a s ti st h ei m p o r t a n tb a s i so fh i g h - b a n d w i d t ha n d s h a r e di n t e r n e ta p p l i c a t i o n s ，s u c ha ss t r e a mm e s aa n dv i d e o r e c e n tr e s e a r c hs h o w e st h a tt h em u l t i c a s tr o u t i n ga l g o r i t h mp l a y sav e r y i m p o r t a n tr o l ei nt h en e t w o r kq u a l i t yo fs e r v i c eg u a r a n t e ea n dt h a tt h er e s e a r c ho n q o sm u l t i c a s tr o u t i n ga l g o r i t h mh a sb e c o m eah o t s p o ti nt h en e t w o r kr e s e a r c ha r e a i nt h ep r e v i o u sr e s e a r c h ，q o sm u l t i c a s tr o u t i n gp r o b l e mi su s u a l l ya t t r i b u t e dt ot h e m i n i m u mc o s ts t e i n e rt r e ep r o b l e mw i t hs o m ec o n s t r a i n t sw h i c hh a sb e e np r o v e dt ob e n p c o m p l e t e s ot h eq o sm u l t i c a s tr o u t i n gp r o b l e mh a sn os o l u t i o nm e t h o dw i t h i n p o l y n o m i a lt i m ea n do f t e nb e e ns o l v e dw i t hh e u r i s t i ca l g o r i t h m s w i mt h ei n c r e a s i n g d e m a n df o rt h en e t w o r kq o sa n dt h ei n c r e a s i n gn e t w o r ks c a l e ，i ti sv e r yi m p o r t a n t a n da l s os i g n i f i c a t i v et h a tw ed os o m er e s e a r c h e so nt h eq o sm u l t i c a s tr o u t i n g a l g o r i t h m 、 ，i t hm u l t i c o n s t r a i n t si no r d e rt oa t t a i nn i c eq u a l i t yo fn e t w o r ks e r v i c ea n d b e t t e ru t i l i z a t i o no ft h en e t w o r kr e s o u r c e i nt h i sp a p e r , t h r e ed i f f e r e n ta l g o r i t h m sa r ep r o p o s e dt os o l v et h eq o sm u l t i c a s t r o u t i n gp r o b l e ma f t e ra c h i e v i n ge x t e n s i v ea n di n t e n s i v er 懿e a r c ho nt h ea r e ao f s o l v i n gm u l t i c a s tr o u t i n gp r o b l e mu s i n ga n tc o l o n ya l g o r i t h m 1 1 l e ya r ec a l l e da c a 0 ， a c a ta n da c a t - o s e p e r a t e l y ： ( 1 ) a dh o cn e t w o r ka r eo b t a i n i n gm o r ea n dm o r ea t t e n t i o nd u et oi t se x c e l l e n t c h a r a c t e r i s t i c sa n ds p e c i a la p p l i c a t i o n 1 1 1 i sp a p e rp r o p o s e st h ec o n c e p to f “o r i e n t a t i o n f a c t o r o nt h eb a s i so fa n a l y z i n gt h es t a t i s t i cc h a r a c t e r i s t i co ft h ea dh o en e t w o r k ，t h e i i i 山东大学硕七学位论文 w i d ea p p l i c a t i o no fg p s t e c h n o l o g ya n dt h ee s s e n t i a l i t yo fa n tc o l o n ya l g o r i t h m t h e n an e wa l g o r i t h mc a l l e da c a 一0 ( a n tc o l o n ya l g o r i t h mc o n s i d e r i n go r i e n t a t i o n ) i s d e s i g n e da n dr e a l i z e db ya p p l y i n go r i e n t a t i o nf a c t o rt oa n tc o l o n ya l g o r i t h m , w h i c hi s a i m e dt os o l v et h eq o sm u l t i c a s tm u t i n gp r o b l e mi nt h ea dh o cn e t w o r k i nt h e a l g o r i t h mo fa c a o ，o r i e n t a t i o nf a c t o ra f f e c t st h es e a r c h i n gb e h a v i o ro ft h ea n t s ， l e a d st h ea n t st or e a c ht h ed e s t i n a t i o nm o r er a p i d l ya n dm a k et h ea l g o r i t h m c o n v e r g e r a p i d l y t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h ma c a 一0c a ng e tb e t t e r s o l u t i o n 谢t hl e s st i m e ，l e s sp a c k e t sa n dl e s se n e r g y ( 2 ) a n o t h e ra l g o r i t h mc a l l e da c a t ( a n tc o l o n ya l g o r i t h mb a s e do nt r e e ) i s p r o p o s e dt os o l v em u l t i c a s tr o u t i n gp r o b l e m c o m p a r i n gt h et r a d i t i o n a lf a s h i o no f c o m b i n i n gt h ep a t h si n t oat r e e ，a c a tg e n e r a t e st h et r e eu s i n gt h ef a s h i o no fg r o w i n g t r e ed i r e c t l y , s i m p l i f i e st h ep r o c e s so fs e a r c h i n gf o rm u l t i c a s tt r e ea n di m p r o v e st h e e f f i c i e n c yo fa l g o r i t h m ( 3 ) c o n s i d e r i n gt h em u l t i c a s tm u t i n gc h a r a c t e r i s t i ci nt h ea dh o en e t w o r k ，w e p r o p o s e san e wa l g o r i t h mc a l l e da c a t - o ( a c a tc o n s i d e r i n go r i e n t a t i o n ) b ya d d i n g n e wv e r s i o no ft h eo r i e n t a t i o nf a c t o rt oa c a t t h en e wo r i e n t a t i o nf a c t o rc a nl c a d s t h et r e et o “g r o w i nt h es h a p eo fr a d i a t i o n ，r e s t r a i n st h e “r e v e r s eg r o w i n g o ft r e ea n d i m p r o v e st h ee f f i c i e n c yo fa l g o r i t h mf u r t h e r l y s i m u l a t i o nr e s u l t sp r o v e st h a t c o m p a r i n gw i t ha c a t , a c a t - oc a nc o n v e r g em o r er a p i d l y w i t hag o o ds o l u t i o ni n t e r m so ft h ea dh o cn e t w o r kt o p o l o g y k e yw o r d s ：m u l t i c a s t ；m u l t i - c o n s t r a i n t s ；q u a l i t yo fs e r v i c e ( q o s ) ；a n t c o l o n yo p t i m i z a t i o n ；o r i e n t a t i o nf a c t o r ；g r o w i n gt r e e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：石钊 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：圣鱼 导师签名：二曼豸 日期：兰塑：! ! 兰 山东大学硕士学位论文 第一章绪论 1 1 课题提出的背景和意义 目前的i n t e r n e t 仅提供尽力而为( b e s t - e f f o r ts e r v i c e ) 的传送服务，业务 量尽快传送，没有明确的时间和可靠性保障。随着网络多媒体技术的飞速发展， i n t e r n e t 上的多媒体应用层出不穷，如i p 电话、视频会议、视频点播( v o d ) 、 远程教育等多媒体实时业务、电子商务在i n t e r n e t 上传送等。i n t e r n e t 已逐步 从单一的数据传送网向数据、语音、图像等多媒体信息的综合传输网演化。这些 不同的应用需要有不同的q o s ( q u a l i t yo fs e r v i c e ) 要求【1 ，2 1 ，o o s 通常用带宽、 时延、时延抖动和分组丢失率来衡量。各种应用对服务质量的需求在迅速增长。 显然，现有的尽力传送服务已无法满足各种应用对网络传输质量的不同要 求，需要i n t e r n e t 提供多种服务质量类型的业务，而尽力而为的服务仍将提供给 那些只需要连通性的应用。 q o s 的研究有多个方面，包括流量整形( t r a f f i cs h a p i n g ) 1 3 、包调度算法 ( p a c k e ts c h e d u l i n g ) 1 4 、路由算法( o o sr o u t i n g ) 5 1 、资源预留( r e s o u r c e r e s e r v a t i o n ) 吲、接入控制( c a l la d m i s s i o nc o n t r 0 1 ) 川等的研究。 组播( m u l t i c a s t ) 【8 ，9 1 是一种有效的支持多点通信的机制，它采用树转发结 构，每一个数据包只在节点处被复制，在每一条链路上只发送一次。这种方法使 i p 组播能有效的同时向组内的成员发送数据，节约链路资源，并支持大量的组 播组。组播技术，在网络拥塞现象日益严重的今天，具有更加重要的意义。 为了保证组播应用的q o s ，网络必须实施资源预约和资源控制。组播路由可 以看作是资源预约的第一步，即采用o o s 组播路由算法首先找到满足应用资源要 求的路由，而后实施资源预约过程。预约请求的成功与否在一定程度上取决于路 由算法能否找到合适的路径。因此，组播路由算法是o o s 组播的核心部分，对实 现网络组播提供保证质量的服务起到了非常关键的作用，同时组播路由算法也是 平衡网络负载和充分利用网络资源的重要保证【l 们。 山东大学硕士学位论文 1 2 国内外研究现状 i e t f 已经提出了多种服务模型和机制来满足各种o o s 组播的需求，q o s 组播 路由是网络分布式多媒体实时信息传输的关键之一，在这方面已有不少的研究 成果e l l - 1 3 】。实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价等多个 参数同时提出性能要求。这些参数相互独立时，选择满足多个参数限制的最优组 播路由就成为n p 完全问趔1 4 1 。 目前，在q o s 组播路由的研究领域中，研究人员已经提出了一些用于解决多 约束q o s 组播路由问题的算法。这些算法大体上可分为启发式算法、近似算法和 基于某种调度策略的多受限q o s 组播路由算法这三类。近年来，国内外许多学者 利用神经网络1 5 】、蚁群算法【1 6 】、遗传算法等启发式智能算法来解决约束o o s 组 播路由问题，并且取得了一定的成果。各算法都有各自的优缺点，其中蚁群优化 算法以其健壮性并行性、灵活性、搜寻过程不需要人工干预以及求解精度高的特 点，得到了广泛应用。 但蚁群算法在进行大规模优化时，初期收敛速度慢、收敛时间过长、易陷入 局部最优解【l 引。这是蚁群优化算法的最为突出的缺陷。针对这些缺陷，近年来众 多国内外学者在蚁群算法的改进方面做了大量的研究工作【1 9 1 。如，基于理性的自 适应蚁群算法【2 0 1 ，采用变异和动态信息素更新策略的蚁群算法【2 1 1 ，最大最小蚁 群算法【2 2 1 等。但许多改进都是基于t s p i 口 题，由于网络环境的复杂特性，并不适用 于多约束o o s 的组播路由优化问题。如何利用网络现有条件对蚁群算法进行改进， 用于解决多约束q o s 组播路由问题是一个值得研究的课题。 1 3 主要研究内容 使新一代i n t e r n e t 网络能够提供有服务质量保证的传输业务是目前计算机 网络研究的主要课题。在实际的多媒体和实时应用中，对延迟、延迟抖动、丢失 率和带宽等方面有许多不同的o o s 限制。因此基于多个约束条件建立的网络模型 可以更准确地反映实际的q o s 组播路由选择问题，随着人们对网络服务质量要求 的提高和网络规模的不断扩大，研究基于多条件约束的q o s 组播路由算法，以获 得良好的网络服务质量和高的网络资源利用率具有十分重要的研究意义。本课题 2 山东大学硕十学位论文 m_lj ! 量曼曼曼曼曼! 曼曼曼曼曼曼舅舅曼皇量 的主要研究目标是研究基于多个限制条件的o o s 组播路由算法及有关技术。主要 研究内容包括： j 一，a dh o e 网络中基于方向因子的组播路由蚁群算法。随着g p s 技术的发 展，在移动结点中实现低成本的g p s 接收机成为可能，这样节点就可以知道自己 的地理位置基于该现实和趋势，本文在传统蚁群算法的基础上，提出了一种新颖 的基于方向因子的蚁群算法a c a 一0 ，并对算法进行了深入的研究、分析和仿真实 验，实验结果证明了a c a o 算法的有效性。 二，基于树的q o s 组播路由蚁群优化算法及其改进算法。以往学者提出的解 组播问题的蚁群算法，通常都要借助于蚂蚁对端到端路径的寻找。这种方式虽然 具有并行性和分布式实现的优点，但重复性的工作太多，效率不高。为了提高蚁 群算法解组播问题的速度，本文提出了一种新的蚁群组播路由算法a c a t ，并对 算法进行了理论分析和仿真实验，实验结果证明了a c a t 算法的可行性和有效性。 本文又对a c a t 算法作了进一步的改进，在a c a t 算法中添加了方向因子，对蚂蚁 的搜索行为进行诱导。将改进后的算法应用于a dh o e 网络，仿真实验结果证明， 对a c a t 算法的改进进一步提高了算法的运行速度。 1 4 论文组织框架 本论文的其余部分可以分为五章。 第二章对网络的q o s 做详细介绍。其中，2 1 分析了o o s 在网络上的应用 需求；2 2 描述q o s 的概念；2 3 介绍了q o s 的发展过程；2 4 介绍了i e t f 对o o s 下的定义；2 5 介绍了q o s 的体系结构。 第三章介绍了网络组播问题。其中，3 1 对现有的组播技术进行了简介； 3 2 讲解了五种组播路由算法；3 3 介绍了现有的组播路由协议。 第四章介绍了q o s 组播路由问题及其解决方法。其中，4 1 描述了o o s 组 播路由问题；4 2 介绍了q o s 组播路由的策略；4 3 详细介绍了q o s 组播路 由的算法研究情况。 第五章介绍了蚁群算法。其中，5 1 描述了蚁群算法的原理；5 2 介绍 了蚁群算法的发展；5 3 介绍了蚁群算法的应用。 第六章介绍了带方向因子的蚁群算法及其a d h o e 网络组播中的应用。其中， 3 山东大学硕士学位论文 6 1 描述了算法的应用背景，介绍了a dh o c 网络的特点以及g p s 定位系统在 h dh o a 网络的应用；6 2 介绍了提出方向因子的原因；6 3 详细介绍了方向 因子的概念、定义和计算公式；6 4 给出了方向因子用到的角度的精确定义和 获取方法；6 5 提出了一种加载了方向因子且适合a dh o c 网络的分布式蚁群 组播算法。6 5 通过仿真实验，分析了该算法对h dh o c 组播路由的优化程度。 第七章介绍了蚁群算法。其中，7 1 介绍了基于树的蚁群算法，包括提出 基于树的蚁群算法的原因、算法的基本操作、算法具体步骤、以及仿真实验和数 据分析；7 2 给出了基于树的蚁群算法的改进算法，包括改进的思想、改进的 具体措施、新方向因子的角度的定义、仿真实验以及数据分析。 最后一章是对所做工作的总结和对下一步研究工作的展望。 4 山东大学硕士学位论文 第二章网络的q o s q o s 的英文全称为“q u a l i t yo fs e r v i c e ”，中文名为“服务质量。q o s 是 网络的一种安全机制，是用来解决网络延迟和阻塞等问题的一种技术。在正常情 况下，如果网络只用于特定的无时间限制的应用系统，并不需要q o s ，比如w e b 应用，或e - m a i l 设置等。但是对关键应用和多媒体应用就十分必要。当网络过 载或拥塞时，q o s 能确保重要业务量不受延迟或丢弃，同时保证网络的高效运行。 2 1q o s 的应用需求 服务质量是日常生活中人们再熟悉不过的字眼。顾名思义，服务质量往往体 现了消费者对服务者所提供服务的满意程度，是对服务者服务水平的一种度量和 评价。计算机系统，特别是计算机网络系统，作为计算和信息等服务的提供者， 同样存在服务质量( q o s ) 优劣的问题。事实上，从计算机系统诞生伊始，人们就 一直孜孜不倦地致力于提高系统的服务性能和服务质量，因此，q o s 问题实际上 由来己久。目前，计算机网络的q o s 问题己经成为国际上网络研究领域最重要、 最富有魅力的研究领域之一，并且和网络安全等问题一道被称为下一代计算机网 络最重要的研究领域之一，对未来网络技术的研究、应用和发展具有举足轻重的 意义。 随着高速网络技术和多媒体技术的飞速发展，人们越来越多地提出了包括多 媒体通信在内的综合服务要求。传统的分组交换网络，如i n t e r n e t ，是面向非 实时的数据通信( 如f t p 和e - m a i l 的传输) 而设计的，采用的t c p i p 协议主要 是为了优化整个网络的数据吞吐量并保证数据通信的可靠性。而当今分布式多媒 体应用( 如视频会议、视频点播、i p 可视电话、远程教育) 不仅包括文本数据信 息，还包括语音、图形、图像、视频、动画这些类型的多媒体信息。分布式多媒 体应用不但对网络有很高的带宽要求，而且要求信息传输的低延迟和低抖动等， 同时，这些应用大都能够容忍一定程度的信息丢失和错误。 表2 - 1 给出了一些典型应用的q o s 需求。由此可见，当今高速网络中的多媒 体应用对网络提出了不同于数据应用的服务质量要求，需要提供端到端的q o s 控 山东大学硕士学位论文 制和保证。目前，在高速网络中按照用户的要求提供q o s 控制是一个普遍的要 求，也是i n t e r n e t 发展的重要挑战。多媒体信息传输与管理的q o s 控制技术作 为下一代网络的核心技术之一，是当前计算机网络中研究与开发的热点问题。 表2 - 1 一些应用的q o s 需求 应用类型 q o s 要求参数范围 f t p 带宽 0 2 l o m b p s t e l n e t 相应延迟8 0 0 m s 带宽 1 6 k b p s 端到端延迟o 1 5 0 m s 电话 端到端抖动 l m s 分组丢失率l o 。2 带宽1 8 6 m b p s 端到端延迟 2 5 0 m s 肝e g 一1 端到端抖动l m s 1 0 。2 ( 未压缩的视频) 分组丢失率 1 0 q 1 ( 压缩视频) 1 g b p s ( 未压缩) 带宽5 0 0 m b p s ( 无损压缩) 2 0 m b p s ( 有损压缩) h d t v 端到端延迟 2 5 0 m s 端到端抖动l m s 1 0 。2 ( 未压缩的视频) 分组丢失率 1 0 。1 1 ( 压缩视频) 2 2q o s 的概念 q o s 是网络在传输数据流时要求满足的系列服务请求，具体可以量化为带 宽、延迟、延迟抖动、丢失率、吞吐量、传输服务的可靠性等。q o s 反映了网络 元素在保证信息传输和满足服务要求方面的能力。q o s 与用户以及网络系统的关 6 山东大学硕七学位论文 系如图2 1 所示。从图2 1 中可以看出，q o s 不是网络中某个个体或元素的行 为描述，它涉及到用户与用户、用户与网络以及网络内部节点( 或元素) 的整体 行为。例如，图2 1 中当用户1 与用户2 之间要相互通信时，事先必须相互协 商通信时的服务类型以及相应的性能参数。如果不事先进行协商，若用户2 接收 来自于用户1 的实时图像时，用户1 每秒按3 0 帧发送，而用户2 只有每秒接收 2 0 帧的能力的话，则尽管i n t e n e t 提供了每秒3 0 帧的传输服务，信息仍会由于 用户2 的接受能力不够而丢失，从而也无法进行满意的实时通信。相反地，如果 事先经过协商，用户l 放慢速度，使其满足用户2 的接收能力，则用户2 会获得 较好的q o s ，而且网络的负载也会相应减轻。除了用户与用户间的协商之外，用 户与网络，网络中的各个元素之间也存在着g o s 协商和管理的问题。当用户的 o o s 要求太高、网络无法提供相应的服务时，将要求用户降低其q o s 要求，甚至 为了保证其他用户的q o s 而拒绝某用户的o o s 要求。在网络内部的路由器，交换 机的端口以及端主机系统中，为了保证用户要求的q o s ，必须进行资源预留，并 采用相应的资源调度算法，这就需要相应的资源预留协议和资源调度算法。 o o s 协商( 服务类型、性能参数) 2 3q o s 的发展 图2 - 1o o s 与用户以及网络系统的关系 自从计算机系统诞生开始，就一直存在提高系统的服务性能和服务质量的问 7 【l i 东大学硕士学位论文 题。因此，可以说计算机系统的q o s 问题由来己久。对计算机网络q o s 的研究可 以追溯到2 0 世纪8 0 年代初期。那时，尽管网络的性能还比较低，提供的服务种 类也比较少，但些有远见的研究者己经认识到服务质量的重要性。s e i t z 和 w o r t e n d y k e 等人在研究a r p an e t 中的x 2 5 通信时已提出基于用户的性能评价 问题，这也许是关于计算机网络q o s 研究的最早文献。在早期的o s i 协议制定中， 也为服务质量的一些参数留有相应的表示手段，但一直空缺未用。很长的一段时 间，由于计算机网络的性能所限，人们对q o s 的关注只停留在数据流传输中的正 确率、吞吐量和延迟等单一服务质量的评价与控制上。直到2 0 世纪8 0 年代末期， 随着b - i s d n 技术以及a t m 交换网的出现和分布式多媒体应用的急剧增加，人们 才开始系统地对q o s 管理和控制进行较为深入的研究。一些实验性系统也应运而 生，代表性的有英国兰开斯特大学的q o s - a 工程，美国哥伦比亚大学的扩展的集 成化参考模型( x r m ) 系统、国际合作项目t i n a - c 工程、美国加州伯克利大学的 t e n e t 工程、i b m 公司黑森伯格欧洲网络中心的h e i p r o j e e 工程等等。 随着i n t e r n e t 商业化的巨大成功，网上传输的多媒体信息迅速增多，网络 拥塞现象日益严重，i n t e r n e t 的q o s 问题研究也随之开始深入。i e t f 于1 9 9 7 年 9 月开始制定了有关o o s 定义与服务的一系列r f c 标准，典型的工作是提出了两 种不同的i n t e r n e to 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 ) 和区分服务( 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 ) 。截至目前，q o s 控制技术 的研究和开发都进展得非常迅速，并且己经取得了许多基本的成果。国内也于近 些年开始了有关q o s 控制方面的研究。 2 4i e t f 的q o s 定义 如何在i n t e r n e t 上提供综合服务的关键是o o s 控制。早期在a t m 交换机及 其协议中开展的q o s 支持工作为后来i p 网络中的q o s 问题研究奠定了基础。进 一步地，对于i n t e r n e t ，目前人们正在研究新的方法来实现o o s 控制和传输管 理，以迎接由于i n t e r n e t 规模日益扩展和业务流爆炸式增长而带来的挑战。 在r f c 2 2 1 6 中，q o s 定义为“用带宽、分组延迟和分组丢失率等参数描述的 关于分组传输的质量”。传统的i n t e r n e t 只提供单一的服务质量，即“尽力而为” ( b e s t - e f f o r t ) 服务。在该服务中，可利用的带宽以及相应的延迟特性取决于网 山东大学硕士学位论文 络中的负载状况。为了进一步描述o o s 控制过程，服务模型与实现框架，r f c 2 2 1 6 还定义了网络元素( n e t w o r ke l e m e n t ) 、流( f l o w ) 、服务( s e r v i c e ) 、行为 ( b e h a v i o r ) 、特性化( c h a r a c t e r i z a t i o n ) 及相应的流量规范( t r a f f i c s p e c i f i c a t i o n ，t s p e c ) 、服务要求规范( ( r e q u e s ts p e c i f i c a t i o n ，r s p e c ) 以及 o o s 控制相关的其他词语定义。i e t f 规定，“网络元素 是指任何一个可在 i n t e r n e t 网络中处理数据分组的构件，它具有在数据通过时进行q o s 控制的能 力。网络元素包括路由器、子网、端主机系统的操作系统等。“流”则指具有相 同o o s 要求和服从同一q o s 控制方法的通过某个网络元素的分组集合。在一个给 定的网络元素中，一个流的分组可以来自于某个单一的应用，也可以来自于不同 的应用。“服务 与o o s 控制服务具有相同的意义。它描述网络元素的q o s 控制 能力。服务包括规范和功能两大部分。“行为 是指与o o s 相关的端到端性能。 行为是应用直接可见的由服务提供的最终结果。t s p e c 是要求服务提供的流量描 述。t s p e c 实际上是一份数据流和网络元素提供的服务之间的合同。r s p e c 则是 用户对网络元素的o o s 要求。t s p e c 和r s p e c 都被资源预留协议r s v p 规定了相 应的格式和定义。 基于上述定义，i e t f 把o o s 定义为一个两维空间：( 服务类型，参数类型) 。 服务类型与参数类型两者都用整数表示。 服务类型的取值范围为 1 ，2 5 4 。该取值范围被进一步划分为三个区。即： 1 ， 2 ，1 2 7 ， 1 2 8 ，2 5 4 。服务类型1 被保留下来用于指定通用参数。即当服 务类型值为1 时，参数类型中给出的任何参数都可以被所有服务所使用。服务类 型 2 ，1 2 7 表示i e t f 定义的各种服务。i e t f 的i n t s e r v 工作小组负责定义各种 服务的编号。例如，保证型服务的编号为2 ，可控负载型服务的编号为5 。目前， i e t f 还未定义更多的服务类型。如果研究人员开发和定义了新的服务类型，并 准备提交给公众使用的话，应从i e t f 的i n t s e r v 工作小组获得相应的服务编号。 服务类型 1 2 8 ，2 5 4 是专为实验开发保留的。研究人员在实验阶段可任意选取服 务号在本地使用。 与服务类型相同，参数类型的取值范围也是 1 ，2 5 4 。区间 1 ，1 2 7 是保留 区间，专门用于指定那些供所有服务公用和共享的参数，例如，当前可利用的带 宽等。该区间的参数值与服务类型值1 一起组成公用共享参数，例如( 1 ，5 ) 表 9 【l l 东大学硕十学位论文 皇曼i!一i i i 鼍曼鼍! 曼皇曼曼曼鲁詈鼍曼曼曼量舅舅曼曼曼曼皇曼曼笪曼鲁量 示一个可供各种服务共享的o o s 参数。 1 2 8 ，2 5 4 由服务规范的设计人员给定， 它们不是共享的，只针对相应的服务类型。 2 5q o s 的体系结构 为了解决i p 网络的q o s 问题，i e t f 已经提出了几种服务模型和机带l j t 2 3 , 2 4 ， 主要有： 综合服务和资源预留协议i n t s e r v r s v p ：以r s v p 信令向网络提出业务流传 输规格( f l o w s p e c ) ，并建立和拆除传输路径上的业务流状态。主机和路由器节 点建立和保持业务流状态信息。尽管r s v p 经常用于单个流，但也用于聚流的资 源预留。 区分服务：在区分服务网络中，边界路由器根据用户的流规格( s t r e a m p r o f i l e ) 将用户流划分为不同的级别，再聚合成流聚集，聚集信息存放在i p 包 头的d s 标记域，称为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 e p o i n t ，d s g p ) 。 内部节点则根据d s c p 提供不同质量的调度转发服务。 2 6 本章小结 本章对i p 网络的服务质量( o o s ) 做了详尽的论述。首先，介绍了q o s 的应 用需求，阐述了当前i n t e r n e t 中存在的业务，以及它们的q 0 s 需求；其次，给 出了q o s 的相关概念，以举例的方式形象地讲解了q o s 的概念；然后，介绍了 q o s 的发展过程，详细的讲解了人们对q o s 的认识和研究历史；进而，描述了i e t f 对o o s 的定义，以严格而准确的语言诠释了i p 网络o o s 的内涵；最后，给出了 q o s 的体系结构，简单的介绍了i e t f 已经提出的几种服务模型和机制。 山东大学硕士学位论文 第三章网络的组播 传统的网络数据传输可以通过两种方式进行：单播传输和广播传输。对不断 增长的数据传输业务，这两种传输方式已显出自身的缺陷。广播只能局限在本地 子网中，而不能跨越路由器。而同时向大量不同的用户单播相同的数据包时，需 要建立多条数据通道，将耗费大量的网络带宽。为了更好的传输数据，组播技术 诞生了。 3 1 组播技术 组播是在发送者和多个接收者之间实现点对多点网络连接。如果一台发送者 同时给多个的接收者传输相同的数据，也只需复制一份的相同数据包。它提高了 数据传送效率，减少了骨干网络出现拥塞的可能性，从而有效的利用网络资源。 组播的优点： ( 1 ) 需要相同数据流的客户端加入相同的组共享一条数据流，节省了服务器 的负载。具备广播所具备的优点。 ( 2 ) 由于组播协议是根据接收者的需要对数据流进行复制转发，所以服务端 的服务总带宽不受客户接入端带宽的限制，其提供的服务可以非常丰富。 ( 3 ) 组播协议和单播协议一样允许在i n t e r n e t 宽带网上传输。 组播应用大致可分为三大类：实时交互型应用，如视频会议系统：实时非交 互型应用，如数据报广播；非实时型应用，如电子文档分发