（计算机应用技术专业论文）基于蚁群原理的qos多约束单播路由算法研究.pdf

南京邮电学院硕上学位论文 基于蚁群原理的q o s 多约束单播路由算法研究 摘要 本文在第一章首先介绍了q o s 问题的提出、基本概念、度量、0 0 s 的几个关 键问题：第二章分析了i pq o s 的一般解决途径及其实现机制；第三章给出了i p 路由概念，以及几种常见的路由算法：第四章介绍了蚁群系统基本原理，详细给 出了蚂蚁算法的应用；第五章先给出了改进前的基于蚁群系统原理的q o s 多约束 单播路由算法，然后对该算法进行改进，给出了改进的几个地方：最后一章先介 绍了o p e r f 网络仿真软件，再基于o p e t 构造了一个简单的网络模型，对改进前 后的算法进行了仿真、验证，对仿真结果进行分析，比较，最后，由仿真结果可 以表明，改进算法具有更好更快的收敛性，可以有效提高网络数据包的传输质量。 此外，改进算法仍然保留了蚁群算法所具有的可扩展性，并不改变复杂度。 关键词 服务质量，蚂蚁算法，多约束单播路由，o p e t 南京邮电学院硕士学位论文 r e s e a r c ho nq o sm u l t i p l ec o n s t r a i n t su n i c a s tr o u t i n g 削g o r i t h mb a s e do t h ep r i c i p l eo f a ts y s t e m a b s t r a c t i nt t l i sp a p e r ，s o m eb a s i cc o n c 印t sa r ei n t r o d u c e di i lf l r s tt h r e ec h a p t e r s ， i n c l l l d i n gt h ep r e s e n t a t i o no fq o sp r o b l e m s ；t h ec o n c 印t ，t h em e a s u r e m e n ta 1 1 ds o m e c f u c i a lp r o b l e m so fq o s ；s o m ec o i 啪o ns o l 砒i o nm e t h o d sa n di m p l e m e n t a t i o n m e c h a n i s mo fpq o s ；t h ec o n c 印t so fpr o u t i n ga 1 1 ds e v e r a lc o m m o nr o u t i n g a l g o r i t h m ；i nm ef o n hc h a p t e r ，t h eb a s i cp r i n c i p l eo f a n ts y s t 锄i si n t r o d u c e da n dm e d e t a i l e d 印p l i c a t i o no fa n ta 1 9 0 r i t h mi sa l s oa 1 1 a l y z e di nt 1 1 i sc h 印t e r 1 1 1t 1 1 e 矗肋 c h a p t e lw e 行r s t 印p l yt h ea n ts y s t e mt os o l v et h ep m b l e mo fm u l t i c o n s t r a i n e dq o s r o u t i n ga n do nep r i m i t i v ea l g o r i t mi si n h d d u c e d ，b a s e dt h a t ，t h e nw eo f 矗玎o n e m o d i n e da l g o r i t i nt h e1 a s tc h a p te r o n en e 研o r ks i m u l a t i o nt 0 0 1 一o p n e ti s i 1 1 t r 。d u c e df i r s t ly t h e nw e 丘a i i l e sas i m p l en e t w o f km o d e li no p n e t d os i m u l a t i o n a n dv e r i f yo nt h eu n i m p r o v e da 1 1 di m p r o v e da l g o r i t l l i l l ，a i l a i y z ea n dc o m p a r et h e i r d i f 诧r e n tr e s u l t s f i n a l ly ，t h er e s u l t ss i g n i f yt h ei m p r o v e da l g o r i t h mh a sb e t t e r c o n v e r g e n c ea n di s a b l et oi m p r 0 v et h eq u a l i t yo fp a c k e tt r a i l s m i s s i o ne f 绝c t i v e l y m e a n w h i l e ，t h ei m p r o v e da l g o r i t 址ns t i l lr e t a i n sa 1 1 ta l g o r i m m se x p a i l s i b 订i t y - k e y w o r d s ： q u a l i t yo f s e r v i c e ( q o s ) ，a _ i l t a l g o r i t h m ，m u l t i p l ec o n s t r a i n t su n j c a s tr d u t i n g o p n e t 2 南京邮电学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：注蝴考日期：盘雌生 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名：红缸导师签名：屋! 至日期：2 q n 生牟 南京邮屯学院硕士学位论文 引言 随着i n t e r n e t 业务的不断发展，各种新的业务对网络服务质量( q u a l i t yo f s e r v i c e ，q o s ) 提出了不同的需求，如何在i n t e r n e t 上提供各种业务所需的q o s ， 是当前业界一个新的研究热点。为了解决在i n t e r n e t 等计算机网上高质量地传 输多媒体信息的问题，美国于1 9 9 6 年底，开始了以提高网络服务质量( q o s ) 研 究为核心的i n t e r n e t 】i 以及n g i 等研究项目。i e t f 也成立了专门的工作小组来 研究多媒体服务质量的定义和相关的标准。 目前很多支持q o s 的研究侧重于调度、拥塞控制和资源预留，而对q o s 路由 的研究相对较少。q o s 路由选择的任务就是从源端到目的端找到一条具有足够资 源的路径来满足端到端服务质量，包括收集网络状态信息并不断更新信息，以及 根据已有信息为新的连接请求选择一条合适的路由。一个路由算法的性能主要取 决于信息收集的好坏。一个优化的q o s 路由选择策略是实现q o s 保证的关键之一， 也是目前关于q o s 的一个重要的研究方向。 蚁群算法是新近提出的一种新型的模拟进化算法，研究表明该算法比遗传算 法、模拟退火算法等早期进化计算方法具有更强的鲁棒性、求解时间短、易于计 算机实现等优点，是解决n p 一完全问题的有效方法。我们所要解决的q o s 路由问 题是个多约束受限单播路由问题，这里的多约束受限表现在带宽、时延和丢包率 三个条件，该问题是个n p 一完全问题“1 ，因此，我们可以用蚁群算法来解决。 本文针对q o s 路由问题，应用新近提出的蚁群算法来求解，并对该算法提出 了改进，用网络仿真软件0 p n e t 对改进前后的算法进行了仿真、验证，通过对仿 真结果进行分析、比较，可以表明，改进后的算法具有更好的收敛性，加快了蚂 蚁在全局范围内搜索到最优路径的速度，可以有效提高网络数据包的传输质量。 此外，改进算法仍然保留了蚁群算法所具有的可扩展性，且不改变原有复杂度。 南京邮电学院硕士学位论文 第一章q o s 基本概念 1 1q o s 问题的提出 一般来说，基于存储转发机制的i n t e r n e t ( i p v 4 标准) 只为用户提供了“尽 力而为( b e s te f f o r t ) ”的服务，不能保证数据包传输的实时性、完整性以及到 达的顺序性，不能保证服务的质量，所以主要应用在文件传送和电子邮件服务。 随着i n t e r n e t 的飞速发展，人们对于在i n t e r n e t 上传输多媒体应用的需求越来 越大。一般来说，用户对不同的多媒体应用有着不同的服务质量要求，这就要求 网络应能根据用户的要求分配和调度资源。因此，传统的所采用的“尽力而为” 转发机制，已经不能满足用户的要求。 解决这些问题的最简单的方法当然是增大带宽，但是，由于这种方法代价高 昂，所以并不十分可行。这就要求网络管理者对不同的服务区别管理，而不能对 所有数据包一视同仁。于是，各种q o s 技术应运而生。最简单的说，0 0 s 能够对 数掘包进行合理的排队，对含有内容标志的数据包进行优化，并对其中特定的数 据包赋以较高的优先级，从而加速传输的进程，并实现实时交互。由于每种应用 系统对网络的要求有所不同，这使得带宽本身并不能解决网络拥塞的问题。q o s 所追求的传输质量在于：数据包不仅要到达其欲传输的目的地址，而且还要保证 数据包的顺序性、完整性和实时性。通过q o s ，网络可以按照业务量的类型或级 别加以区分，并能够依次对各级别进行处理。优秀的q o s 可以提供创建业务量级 另q 的方法，把应用系统或用户的邮件分配到某一级别中作系统管理。 1 2q o s 的定义 为了解决在i n t e r n e t 等计算机网上高质量地传输多媒体信息的问题，美国 于1 9 9 6 年底，开始了以提高网络服务质量研究为核心的i n t e r n e t i i 以及n g i ( 下 一代i n t e r n e t ) 等研究项目。i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 也成立 了专门的工作小组来研究多媒体服务质量的定义和相关的标准。 网络服务质量( q u a l i t yo fs e r v i c e ，简称q o s ) 是网络于用户之间以及网络 上相互通信的用户之间关于信息传输与共享的质的约定，是i p 数据流通过网络 2 南京邮电学院硕士学位论文 时的性能。它的目的就是向用户提供端到端的服务质量保证。它有一套度量指标， 包括业务可靠性、延迟、可变延迟、吞吐量和丢包率： 业务可靠性：用户到i p 业务之间连接的可靠性。 延迟：也称为时延( l a t e n c y ) ，指两个参照点之间发送和接收数据包的 时削i 目隔。 可变延迟：也称为抖动( j i t t e r ) ，指在同一条路径上发送的一组数据流 中数据包之间的时间差异。 吞吐量：网络中发送数据包的速率，可用平均速率或峰值速率表示。 丢包率：在网络中传输数据包时丢弃数据包的最高比率。数据包丢失一 般是由网络拥塞引起的。 根据q o s 的概念，我们可以定义q o s 的几种度量特性： 对于路径p = ( v ，：，v ，v 。v 。) ，用d ( v 。，v 。) 表示对应链路( v 。，v ) 的度量， 则q o s 度量可以按性质分为以下三类： ( 1 )单性q o s 度量 如果d ( v ，v 。) = m i n d ( v ，v 。) ，d ( v ：，v 。) ，d ( v “v 。) d ( v 。一，v 。) ) ，习b 么度量由传输链路中的瓶颈决定，即此度量仅与路径上的某个瓶颈链路的q o s 度量有关，如剩余带宽、剩余缓存区、链路速率等。 ( 2 ) 加性q o s 度量 如果d ( v 。，v 。) = d ( v ，v ：) + d ( v 。v 。) + d ( v 。v 。) ，那么度量由通道中 所有链路的特性共同决定，如时延、时延抖动、费用等。 ( 3 ) 乘性q o s 度量 如果d ( v 。，v 。) = d ( v l ，v ：) d ( v ：，v 。) d ( v 。+ v 。) ，即度量为所有 链路对应度量的乘积，如连接可靠性等。如取d ( v 。，v 。) = l n d ( v 。v 。) ，其中 l n ( ) 为以e 为底的对数，则乘性度量就转换为加性度量。 1 3 几个关键问题 当前对q o s 技术和q o s 体系结构的研究是一个开放的课题，同时，支持q o s 也是一个非常复杂的问题，主要原因如下： 南京邮电学院硕士学位论文 ( 1 ) q o s 是一个端到端的要求，涉及源端至目的地通路上的所有设备，是 由业务流经过的每个域所提供的边缘到边缘的服务质量级联构成的，而且有可能 跨越多个行政管理域： ( 2 ) q o s 涉及传输平面的每一层，需要传输、控制和管理平面相互协调； ( 3 ) 计费度量标准问题很难解决，是简单地用分组技术、突发性、峰值或 平均带宽还是采用对传输延迟及抖动的某种复杂的测量，当前还未形成一致的意 见； ( 4 ) 当确定了一个认为消费者能理解的度量标准以后，还面临着如何在网 络中对其进行准确测量，可靠地与特定用户联起来的问题，并且需要保证对用户 定义的每一个不同的业务类型的每一个实例进行处理； ( 5 ) 对用户申请和使用的特定服务级别进行鉴权； ( 6 ) q o s 管理问题。 此外，i p 协议的无连接特性也使得支持i p 网络的q o s 变得更加复杂。 目前主要的研究热点和难点是以下一些关键问题： ( 1 ) 面向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 支持，而不需 要修改应用本身。这种方法使得应用本身与q o s 管理无关，独立性较强，但缺点 是应用程序无法和网络策略控制系统即与q o s 相关的信息进行交互。 ( 2 ) 综合服务i n t s e r v r s v p 和差分服务d i f f s e r v 的综合应用 在p 网络q o s 问题的研究过程中，人们提出了两种不同的q o s 服务模型： i n t e r s e r s v p 和d i f r s e r v ，这两种口网络的0 0 s 控制都不能完全满足网络业 务的0 0 s 需求，存在各自的长处和局限。r s v p 由于面向单一流，实现比较复杂， 丌销大，而且存在扩展性的问题，因而在主干网络中实现r s v p 有一定困难，但 它能提供明确的q o s 保证，适于用来在用户主机到主干网络之间支持q o s 业务。 4 南京邮电学院硕士学位论文 d i f 俗e r v 面向流聚集，因而不能为特定的会话提供明确的0 0 s 保证，但实现较为 简单，适于在主干网络上应用该技术提供q o s 支持。为了更好地支持端到端的 0 0 s ，人们提出将h l t e r s e 瓜s v p 和d i 腮e n ，看作相互补充的技术，相互结合， 仂、同工作为实现端到端的q o s 提供机制，最终达到既能提供类似与状态相关网 络的强有力的服务，又能达到与状态无关网络近似的可扩展性和鲁棒性。 ( 3 ) q o s 技术中的组播问题； 传统口网络的组播问题由于存在地址分配问题、对目的节点的无知性以及 可扩展性问题等阻碍了组播技术在广域范围内的推广应用。q o s 业务中的组播对 网络技术添加了新的要求，设计和实现提供0 0 s 保证的组播路由算法一直是人 们研究的热点问题之一，r s v p 和d i 行s e n ，中都对组播问题做了专门的探讨。 ( 4 ) 策略控制和网络资源管理； 山于不同的q o s 要求的数据流对网络资源的要求不同，因此，q o s 体系结 构中必须提供一个良好的可操作的策略控制机制以及公平、高效的资源管理方 法。同前，基于q o s 的策略控制机制尚处于研究发展阶段。 ( 5 ) 约束路由和流量工程。 当前，i p 网络q o s 的体系结构中，约束路由和流量工程也是研究热点之一。 流量工程就是安排传输流如何通过网络，以避免不均匀地使用网络而导致拥塞的 过程。为使流量工程自动化，约束路由是一种重要的工具。在流量工程和约束路 由的研究过程中，人们提出了很多新的算法和技术，但这些技术需要得到进一步 的完善并付诸于实际应用中进行检验。 南京邮电学院硕士学位论文 第二章q o s 解决途径及其实现机制 为了在因特网中实现对延迟敏感的多媒体应用程序，给现有的因特网体系结 构中加入新的成分，以使应用程序避免拥塞，使得高质量的网络多媒体应用程序 成为可能，目前，许多有关支持q o s 问题的研究主要着眼于队列管理、队列调度、 拥塞控制和资源预留，而近几年对q o s 路由的研究也逐渐成为更大的热点。 2 1队列管理机制( q u e u em a n a g e m e n tm e c h a n i s m ) 网络拥塞时，路由器必须丢弃一些分组，这个问题的解决首先必须实施有效 的队列管理机制( 或缓冲区管理策略) 。 目前，已经出现的队列管理机制有：p p d ( p a r t i a lp a c k e td i s c a r d ) 、 卜p d ( e a r l vp a c k e td i s c a r d ) 、r e d ( r a n d o me a r l yd i s c a r d ) 、f r e d ( f l o wr e d ) 、 r 1 0 ( r 印w i t hi na n do u t ) 、b l u e 算法。比较起来，r e d 算法具有较低的排队时 延、较高的分组通过度和较好的公平性，其主要思想是：路由器计算平均排队长 度，当平均排队长度超过某一门限时，路由器按照一丢弃概率丢弃到达的分组， 而这个丢弃概率是与平均排队长度成正比的函数。r e d 算法允许短时的分组突 发，因而可以避免因为网络负荷变化造成的分组丢失；r e d 算法能避免多个t c p 连接同时的超时重传，从而保持高的带宽利用率：此外，r e d 算法还能较好的支 持突发业务，且确定哪些连接使用了更大的带宽，并可以采取措施予以惩罚。 r r e d 和r i o 都是在r e d 上的改进或者变种，f r e d 对每一个业务流( 或连接) 都实施单独的一个r e d 算法，这样能保证更好的公平性；r 1 0 在r e d 的基础上又 增加了一个门限值，在对d i f f s e r va f 业务的研究中采用此算法。 b 【j u e 算法是i b m 公司的研究人员最近才提出的另一种较新的队列管理机制， 与其他算法不同的是：b l u e 算法以“分组丢失率”和“链路有效利用率”作为 判别拥塞是否发生的标准，而之前的算法都是以路由器中的“平均分组长度”作 为拥塞是否发生的判别标准o 。 2 2队列调度机制( q u e u es c h e d u l i n gm e c h a n i s m ) 不论在i n t s e r v 还是在d i f f s e r v 里，都涉及到队列调度问题。简言之，队 6 南京邮电学院硕士学位论文 列调度的功能就是路由器如何从多个( 一个) 队列中选择下一个待转发的分组， 这与队列管理机制有着本质的区别。根据不同的服务规则，队列调度算法可以分 为以下几种：先到先服务( f c f s ) ，循环调度( r o u n dr o b i n ) ，处理机共享 ( p r o c e s s o rs h a r i n g ) ，优先级服务，随机服务等。 目前已出现的队列调度算法主要有：基于循环调度的算法，基于 g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ，广义处理器共享) 的算法两大类。一个有 效的队列调度算法应能达到的性能指标主要有：公平性、时延特性、对恶意业务 流的隔离能力、链路带宽的利用率、复杂性等，前四个指标与q o s 密切相关。基 于循环调度的算法是轮流对每个队列进行服务，其实现简单，但不能对业务提供 时延保证，目前主要有w e i g h t e dr r ，d e f i c i tr r 等。基于g p s 的调度算法目前 主要有：加权公平排队( w f q ) ，自时钟公平排队( s c f q ) ，v c ( v i r t u a lc l o c k ) 等，它们( 尤其是w f q ) 能提供较好的公平性，时延特性以及对恶意业务流的隔 离能力，但当队列数量较多时，其实现复杂度较大。 2 3 业务量工程( t r a f f i ce n g i n e e r i n g ) 随着i n t e r n e t 的快速发展，网络拥塞问题变得越来越严重。业务量工程是 对运营中网络的业务流量进行控制的过程，它包括对业务流量的测量、建模、描 述以及为达到特定的性能指标所使用的各种技术”1 ，其目标是使资源利用和网 络性能达到最优化，减少网络拥塞的发生。另外，业务量工程通过对资源的合理 配置和对路由过程的有效控制使网络资源能够褥到最优的利用，从而可以大大改 善网络的各项q 。s 指标。所以，业务量工程为i p 网络的q o s 实现提供了有力保 障。网络拥塞发生的原因可能有：网络资源( 如链路带宽、缓冲区等) 的不足， 以及网络中业务的不均匀分布。现在的动态路由协议都会导致不均匀的通信分 布，因为它们总是选择最短路径转发包。结果是，在两个节点之间顺着最短路径 上的路由器和链路可能发生了拥塞，而沿较长路径的路由器和链路却是空闲的。 因此，无法指望升级改造目前的路由协议来达到流量工程的目标。 当业务量不均匀分布时，则有的链路处于过载状态，而有的链路可能处于负 载状态，此时，如果我们能够对网络中的业务流进行适当引导，则不必增加网络 资源也可能消除拥塞。业务量工程的目的就在于：如何有效地引导业务流通过网 7 南京邮电学院硕士学位论文 络以便消除由于业务量不均匀分布而造成的网络拥塞。多协议标记交换( m p l s ) 和基于受限的路由都是业务量工程的有用工具，也是目前有待进一步研究的课 题。 i pq o s 流量管理从一个业务数据包进入网络到退出网络，可以分为几个过 程，即业务的分类、业务的监管、业务的调节和业务的过虑。 ( 1 ) 业务的分类 对进入网络的业务进行分类，以便在网络中得到相应的适当处理，业务必须 由客户预先标记或在运营商网络一端与客户最临近的路由器进行标记。 ( 2 ) 业务的监管 业务的监管( t r a f f i cp o l i c i n g ) 是为了监督用户是否根据s l a ( s e r v i c e l e v e la g r e e m e n t ) 中所赋予的权利来使用运营商网络。一方面是保证运营商自 己的利益不受侵害，另一方面也从间接上保证了其他用户在网络中的权利。常见 的令牌桶算法( t o k e nb u c k e t 算法) 就是应用于业务的监管。 ( 3 ) 业务的调节 实际上，业务的分类和业务的监管都发生在运营商网络的边缘，而业务的调 节阶段则是完全的网络行为。它的好坏直接决定了i pq o s 能否实现的问题。 一般来说，业务的调节主要有两个手段，一个是预防拥塞的排队和调节机制， 另一个就是遇到拥塞时的丢弃机制。 ( 4 ) 业务的过虑 业务的过虑一般用于退出一个域的行为，方面是出于安全性考虑而进行过 虑，而另一方面也是防止低优先级业务接入链路而进行过虑。过虑是在运营商一 端的边缘路由器上进行的。 2 4q o s 路由 q o s 路由可以定义为一种根据网络上可利用资源和流( f l o w ) 的q o s 需求来 决定流的路由的机制。目前很多支持q o s 的研究侧重于调度、拥塞控制和资源预 留，而对q o s 路由的研究相对较少。q o s 路由选择的任务就是从源端到目的端找 到一条具有足够资源的路径来满足端到端服务质量，包括收集网络状态信息并不 断更新信息，以及根据已有信息来为新的连接请求选择一条合适的路由。一个优 南京邮电学院硕士学位论文 化的q o s 路由选择策略是实现q o s 保证的关键之一，也是目前关于q o s 的一个重 要的研究方向。q o s 路由应能达到以下目标： ( 1 ) 动态确定可行路径 ( 2 ) 优化资源利用 ( 3 ) 对性能影响尽可能小 q o s 路由目前需要研究的主要问题包括路由参数的选取、网络状态信息的收 集和聚合、q o s 的度量、路由策略和路由算法、q o s 路由的实现细节和实现开销 等。 2 4 1 增强型链路状态e i g p 为了能够计算q o s 路由，路由器需要知道网络拓扑信息和资源可用性信息。 分发资源可用性信息的一种方法是使用增强型链路状态协议e i g p ( e n h a n c e d i n t e r i o rg a t e w a yp r o t o c 0 1 ) ，对现有的链路状态i g p 协议的链路状态广告加以 扩展。由于链路的剩余带宽是经常变化的，因此必须在信息的准确度和链路状态 广告的扩敖频繁度之间做出折衷。为了降低链路状态广告的频率，可以只有当拓 扑发生变化或带宽有显著变化时( 如超过5 0 或多于1 0 m b p s ) 才分发这些信息。 通常使用保持定时器( h o l d d o w nt i m e r ) 的方法来限制这些链路状态广告的频 率。 2 4 2 约束条件选择 q o s 约束路由中的路由算法以及这类算法的复杂度取决于为这些路由算法 所选择的尺度。在q o s 路由中通常使用的尺度包括费用、跳数、带宽、可靠性、 延迟和抖动等。它们按性质可分为单性q o s 尺度( 包括可用带宽、剩余缓冲区空 间、链路速率等) 、加性q o s 尺度( 包括时延、时延抖动、跳数、费用等) 和乘 性q o s 尺度( 如可靠性等) 三类。 受两个或多个加性和或乘性尺度约束的最优路径问题是一个n p c o m p l e t e ( n o np 0 1 y n o m i a lt i m ec o m p l e t e ) 问题。也就是说，使用延迟、抖动、 跳数、可靠性中的两个或两个以上的参数作为尺度，并将它们同时优化的算法是 冲完全的。计算上可行的尺度的组合是将带宽与上述的几种尺度之一进行组合。 南京邮电学院硕士学位论文 2 4 3q o s 路由算法 q o s 路由选择算法可以按照下面的路由选择准则之来进行路由选择： ( 1 ) 最宽最短( w i d e s t s h o r t e s t ) 路径：即一条有最少跳数的路径，并且 如果有多条这样的路径时，选择其中可用带宽最大的那一条路径。 ( 2 ) 最短最宽( s h o r t e s t w i d e s t ) 路径：即一条有最大可用带宽的路径， 并且如果有多条这样的路径时，选择其中跳数最少的那一条路径。 不使用最短路径会消耗更多资源，在网络负载比较重时，这样做的效率比较 低，因此必须在节约网络资源与负载平衡之间做出折衷。上面提到的第一条准则 与现在正在使用的传统路由中的选路原则基本上是一致的，它强调通过选择最短 路径来节省网络资源。第二条准则则强调通过选择最宽路径来进行负载平衡。 2 4 4q o s 连接的建立 当自口大部分支持q o s 的连接建立时，一般的执行步骤如图2 1 所示。 五 栅 选 路 源节点中问节点目的节点 图2 一1 支持q o s 的会话建立阶段的描述模型 图2 一l 所示模型假定通信实体间的路由初始时是已知的。当源与目的节点之 问只有一条路由时，这种假设是合理的，但是当存在多条路由可供选择时，它的 缺点就明显地暴露出来：由于在建立连接时必须进行多次重复操作，将导致阻塞 概率的上升，成功建立新连接概率的下降，而从性能和代价方面来考查，建立的 连接也不是最优连接。因此，应将对q o s 的支持与路由选择相关联，在建立连接 时降低重试的次数或建立时间，同时合适的路由选择机制将使高速网络的资源利 l o 南京邮电学豌硕士学位论文 用率最大化，并降低每一网络中冲突的产生。q o s 路由算法不能成功地找到符合 服务要求的路径的可能性是存在的，原因也许是根本没有这样的路径存在，或者 是出于算法的解空间没有覆盖可行的路径。当这种情况发生时，系统既可以拒绝 连接请求，也可以与应用进行协商，寻求在一个较宽松的q o s 限制下再次寻找可 能的路由。q o s 路由能够提供可按受的q o s 限制及在该限制下最佳的可行路径， 如果防商成功，q o s 路由所提供的路径马上就可以得到应用。 2 5 当前i p 网络引入q o s 的主要模型 i e t f 提出了若干满足i pq o s 需求的服务模型，包括综合服务( i n t s e r v ) 模型、区分服务( d i f f s e r v ) 模型、多协议标记交换( m p l s ) 等。 2 5 i 综合服务模型 i n t s e r v 模型以i p 协议为其网络层统一平台，首先对网络中的共享链路资 源( 如网络带宽和缓冲区) 进行一定的控制，然后将网络应用按q o s 需求分为不 同的种类，并将其统一实现在对上层应用的服务接口中。i n t s e r v 模型采用资源 预留协议( r s v p ) 信令，建立一条从源端到目的端的数据传输通道，并在该通道 的各个节点上进行资源预留，以满足沿该通道传输的业务流的q o s 要求，从而实 现端到端的q o s 服务。i n t s e r v 模型为应用程序提供了选择多个、可控制的服务 等级的能力。它规定了3 种不同等级的服务类别：保证服务( g u a r a n t e e d s e r v i c e ) 、可控负载服务( c o n t r o l l e dl o a ds e r v i c e ) 、“尽力而为”服务 ( b e s t e f f o r ts e r v i c e ) 。保证服务能够提供定量的带宽和端到端排队延迟，而 且确保合法的数据包不会被丢弃：可控负载服务给用户提供一种类似网络欠载情 况下的服务，它是一种定性的指标，比传统的b e s t e f f o r t 服务好，但没有提供 严格界定的服务质量，不能保证确定的排队延时和避免数据包丢失。 为了实现i n t s e r v ，网络中的每个路由器皆需要包含信令协议( 即r s v p ) 、 接纳控制模块、分类模块和分组调度模块4 个组成部分。需要保证服务或可控负 载服务的业务流在发送数据前必须在沿途路由器上通过r s v p 信令协议预留资 源；路由器的接纳控制模块根据所剩资源情况决定是否接受资源预留请求：当一 个路由器接受了资源预留请求时，分类模块根据预置的一些规则，对进入路由器 南京邮电学院硕士学位论文 的每一个分组进行多字段分类，并将分类后的分组放到相应的调度队列中；分组 调度模块根据分组预留的资源和一定的调度算法对分类后的分组队列进行调度 服务。 i n t s e r v r s v p 有以下一些主要特点： ( 1 ) r s v p 面向接收方，为单一数据流预留资源，即数据流的接收方初始化 并维护用于该数据流的资源预留； ( 2 ) r s v p 用“软”状态的方法动态维护主机和路由器上的状态，适应动态 组成员变化和路由变化： ( 3 ) r s v p 既可以为单播业务，也可以为组播业务进行资源预留； ( 4 ) r s v p 并不是路由协议，但是依赖于路由协议。 因为r s v p 是面向单一预留资源，并且明确描述q o s 请求，所以能够提供比 较明确的q o s 僳证。但同时，i n t s e r v r s v p 也存在很多缺陷和有待研究的问题： ( 1 ) r s v p 是依赖于路由协议的，现有的路由协议和路由算法不能真正确保 数据流在预留了资源的路径上传输，基于q o s 的路由有待进一步研究： ( 2 ) r s v p 比较复杂，且由于面向单一流和动态维护预留状态，网络开销很 火，对于大型网络存在可扩展性较差的问题； ( ：3 ) 许多应用需要某种形式的q o s ，但无法用i n t s e r v 模型来表达q o s 请 求； ( 4 ) r s v p 需要应用主机支持r s v p 信令，但目前面向q o s 的应用还有待迸 一步研究： ( j ) 必要的策略控制和价格机制目前尚处于发展阶段，无法付诸应用。 总之，i n t s e r v 的优点在于能够提供严格的端到端q o s 保证，并且r s v p 协 议支持组播环境，为多媒体实时业务提供了资源共享手段。但是，i n t s e r v 存在 扩展性较差、对路由器要求较高、不适合短生存期数据流等问题，目前难于在骨 干网上实施，只适用于规模较小、业务质量要求较高的边缘网络。 2 5 2 区分服务模型 为了解决i n t s e r v 的缺点，i e t f 提出了d i f f s e r v 模型，旨在定义一种可实 施i pq o s 且更容易扩展的方式。d i f f s e r v 中实现这一目标的重要途径是简化网 南京邮电学院硕士学位论文 络内部节点的服务机制和服务对象，即内部节点只进行简单的调度转发，而流状 态信息的保存与流监控机制的实现等只在边界进行，内部节点是状态无关的；采 用聚集传输控制，传输的对象是流聚集，单流信息只在网络边界节点保存和处理。 d i f f s e r v 简化了信令，对业务流的分类颗粒度较粗。它通过汇聚和每跳行 为( p h b ) 的方式来提供一定程度上的q o s 保证。d i f f s e r v 重新利用了i p 数据 包头中的服务类型( t o s ) 字段( 改为d s 域) ，将其扩展到6 b i t ，称之为区分服 务码点( d s c p ) ，每个d s c p 对应一种转发处理行为一p h b 。d i f f s e r v 主要由边缘 路由器、核心路由器、资源控制器组成。边缘路由器对每个分组进行分类，标记 d s 域，用d s 域来携带i p 分组对服务的需求信息。核心路由器根据分组头上的 d s 码点对分组进行相应的转发处理。资源控制器配置了管理规则，为客户分配 资源，它可以通过服务等级协议( s l a ) 与客户进行服务质量协调。d i f f s e r v 通 过在网络边界多分组设置d s 域以及接纳控制功能，可以实现加速转发服务、确 定型转发服务和优先级服务。各个运营商的网络形成一个个d i f f s e r v 域，不同 运营商网络之间的互通需要在边界节点对业务类型定义的差别进行协商。 d i f r s e r v 并不提供端到端的全程q o s ，而是将q o s 限制在不同的域内加以实现， 不同域之间应该有一定的翻译机制。 d i f f s e r v 服务体系的主要特点是简化了网络内部节点的服务机制和服务对 象，因而实现简单，具有较强的扩展性，这也是d i f f s e r v 的主要设计目标之一。 除此之外，d if f s e r v 还具有以下一些特点： ( 1 ) 与i n t s e r v 的分布式控制相对照，d i f f s e r v 采用总体集中控制策略 网络资源的分配是由总体服务提供策略( s e r v i c ep r o v i s i o n i n gp o l i c i e s ) 决定，其中包括边界节点如何分类聚集流，在内部如何调度转发聚集流等。 ( 2 ) 利用面向对象的模块化思想和封装思想，增强了灵活性和通用性 d i f f s e r v 中，各逻辑模块相对独立，并有多种组合，少量模块可组合实现 多种服务，并在发展过程中保持了模块的可重用性。 ( 3 ) d i f f s e r v 与路由无关 与一些虚电路方式实现q o s 的方案( 如a t m ，m p l s ) 以及服务类型标记方案 不同，d i f f s e r v 网络节点处提供q o s 服务的手段仅限于队列调度和缓冲管理， 不涉及网络的路由选择机制。 南京邮电学院硕士学位论文 同时，d i f f s e r v 对o o s 业务的支持方面还有以下一些问题需要进行进一步 研究： ( 1 ) 由于d i f f s e r v 的服务对象是聚集流，而不是每个会话的业务流，因而 无法明确保证每个会话的服务质量，d i f f s e r v 提供的服务质量只是面向某一类 业务聚集流的统计结果。因而，面向网络最终用户提供d i f f s e r v 网络的服务还 无法完全达到目前i n t e r n e t 新业务对网络服务质量的要求，这是d i f f s e r v 存在 的主要不足之处，也是d i f f s e r v 结构本身难以解决的问题； ( 2 ) d i f f s e r v 结构的简化同时带来了组播问题复杂化，例如被忽视的预留 子树n r s ( n e g l e c t e dr e s e r v a t i o ns u b t r e e ) 、异构组播组以及发送方任意改变 等问题。解决d i f f s e r v 网络区支持组播存在的固有缺陷，并最终实现在d i f f s e r v 网络区支持具有端到端q o s 保证的组播传输，是目前研究的难点问题之一； ( ：j ) 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 内部，同一聚集流内部的微流之间实际上是共享资 源，在网络发生拥塞时各微流之间发生资源竞争，因此，只有确保d i f f s e r v 区 域内部不发生拥塞，才能从根本上保证公平性，也能为每一个会话业务流提供更 好的q o s 保证。 2 5 3 多协议标记交换 m p l s 是一个前向转发策略，由思科公司的标记路由发展而来。在o s i 的七 层模型中，它位于第2 层和第3 层之间。与d i f f s e r v 相似，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 e c l a s s e s ) 概念，所有需要做相同转发处理且转发到相同下一中继点的分组属于 同一转发类。每个m p l s 都有一个头标，其中包括2 0 b i t 的标记、3 b i t 的服务级 别( c o s ) 字段、1 b i t 的标记栈指示器和8 b i t 的t t l 字段。m p l s 头标封装在第 南京邮电学院硕士学位论文 2 层头标和i p 头标之间。 m p l s 对业务流的处理也是尽可能的由边缘路由器来完成，让核心路由器不 再进行繁琐而低效的路由查找和转发，以高速、高效进行交换并提供高质量的 q o s 保证。m p l s 网络传输i p 数据的通路称为标记交换路径( l s p ) 。建立l s p 通 常有两种方法：数据驱动( 又称流驱动) 和拓扑驱动( 又称控制驱动) 。数据驱 动对一个数据流是“一个路由，随后交换”，允许为数据建立显式路由，能很好 地为每个数据流提供一致的q o s 保证：但对于i p 数据流量大的网络，数据驱动 的时延较大，对标记的消耗也很大，扩展性较差。拓扑驱动在扩展性上则优于数 据驱动，只有在拓扑变化或控制业务流到达时才重新建立交换路径。因此，拓扑 驱动方式的效率较高，传输几乎没有时延，但它在没有数据交换时也要消耗标记 资源，而且在q o s 保证上不如数据交换，会受拓扑结构变化的影响。在实际的 m p l s 网络中，两种驱动方式是相互配合使用的。 m h s 技术与d i f f s e r v 在很多方面相似，但m p l s 技术引入了新的标记结构， 对i p 网络的改动较大。m p l s 的优点在于提供了更快的分组分类和转发速度，并 提供了一种有效的隧道机制。 2 6 利用基于网络的应用识别( n b a r ) 技术实现q o s 基于网络的应用识别( n b a r ) 技术是c i s c o 公司内容网络结构的重要组成部 分，它为解决网络q o s 问题提供了一种途径。识别应用流听起来是很容易实现的 技