（计算机应用技术专业论文）基于单播的选播qos路由选择算法.pdf

t 于单播- 的茸灌o o s 路由避择算法 基于单播的选播0 0 s 路由选择算法 摘要 随着互联网的高速发展，为了解决目前网络中存在的一些问题，把l p v 6 作为下一代的i p 网络协议。l p v 6 下的0 0 s 问题受也到了人们的广泛关注， 要解决好ip v 6 网络下的0 0 s 问题，就要单播、组播、选播的共同配合。目 前对单播与组播已经展开广泛而深入的研究，并取得了一定的成果，但是 对选播的研究才刚刚起步，还有很多的问题需要我们去解决。 通过对选播通信服务的研究与分析，针对时延约束与多0 0 s 约束下的 选播路由问题，提出了两个改进的遗传算法算法。 随着时实业务不断发展的今天，时延约束成为目前q o s 路由选择的热 点之一。本文中使用p a u ils t o 仟a 提出的模拟退火遗传算法来求解该问 题。该算法利用模拟退火的思想弥补了遗传算法局部收敛较弱，收敛较慢 的缺陷。 有些网络业务除了要考虑时延约束的问题外，还要考虑其他的因素， 例如带宽，时延抖动，包丢失率等。在求解该问题时，主要是在基本的遗 传算法上加入自适应遗传算法与适应度尺度变换。使用自适应遗传算法来 解决基本遗传算法需要烦琐的交叉率与变异率的设定问题，使用适应度尺 度变换解决基本遗传算法的未成熟收敛保持种群的多样性。 除了使用改进的遗传算法来弥补基本遗传算法中的缺陷，在本论文中 还使用单播技术来获取遗传算法的初始种群，使用单播技术结合了网络层 ! 查竺竺竺! 堕一兰三兰苎竺兰竺! 塑! 竺苎竺 选播与应用层选播。使本文中的遗传算法更具有实际的价值，同时也提高 了初始种群的“起点”，加速遗传算法的收敛。 为了验证算法的有效性与收敛性，我们建立了选播路由算法的仿真平 台。仿真结果表明我们的算法是有效且切实可行的。 关键字：选播q o s 路由遗传算法多q o s 参数约束时延约束 广西大掌司n b 裁”屯l 于簟播的琏播0 0 s 路由避择 q o sa n y c a s t r o u t i n gp r o b l e m b a s e do nu n i c a s t a b s t r a c t w i n lt h ef h s t 孕仃mo f t h eh l e m e ti nr e c e n ty e a r s ，m o r e 锄dm o r ep e o p l ep a ya t 旧m o n t om ep r o b l 锄o f q o si i li p v 6 i fw e 啪n tt os o l v em eq o sp r o b l 锄，w en e e dm es k i l lt 0 m m m g eu n i c 硒蝴洲c a s t 趾da i i y c a s t a t1 h ep r e s e n t ，n l o a t 嘣。璐h a v eb e e np a i do n l l i l i c a s t 觚di n l 蚯c 矾l e s sm s e a r c hh a v cb e e nl a 吼c h e do n 缸y c 硒t s ot h e r eh a v el o t so f p i d b l e m o n 柚y c a s t q o sn c c d l l s t or c 鲫c h ht 1 1 i sp a p c r ，w em a | 【eas n l d yi nt l l ef i e l do fa l l y c a s ts e n r i c ea n da c c o r d i n gt ov a r i o l l s q o sp a r a m e t e r sd e 丘1 1 e 锄y c 嬲tq o sr o u t i n gm o d e l i i lo r d e rt os o l v ed i f f b m n tr c q u i r e m e 蝇t h a t i sd e l a y - c o n s 由阻i m 锄dm l l l t i - q o sr o u t i n g ，p m p o s e db yc l i e n t ，w ed e s i g n e dd i 丘b r e n tg ai n t l l i s t l l e s i s n o w ，m i ) r ea n dm o r er e a l - t i l i l e 蚓哳c ea p p e a r e d ，d e l a y - c o n s t r a j i l t 跹dl e s sc o s ti sah o t t o p i ci nr o u t i n gr e s e a r d h a i n l i n ga tt l l i sp r o b l e m ，w eu s a g a op r o p o db yp a u ll s t 0 如 t os o l v et l l i sp r o b l e m n l i sa l g o 打i h mc a nm 酞eu pn l cs h o r t i n go fg a e x c 印to fd e l a y - c o 璐t r a i n t ，t l l e r c a r el o t so fs e r v i c en e e dt 0m i l l l 【a b o r to t l l e r c o n d m o n s ，s u c h 勰b a n 捌d m ，d e l a y j i t t e re t c i nt l l i st 1 1 e s i s ，w ec o i l s i d e rt l l l 优q o sp 盯锄e 雠 t o g c m e r ，t l l a ti sd e l a y ，d e l a y - j i t t c r ，p k - l o s se t c w ec a t l e dm c s ep r o b l e m 鹊m l l l t i - q o s r 0 1 m n gp r o b l e m mt h i sa l g o r i m ，w ea d da d 印t i v eg a 跹d f i 廿l e s ss c a l i n gt os o l v et 1 1 i s p r o b l 锄a d a 州v eg a 锄s i m p l et h ep r o c e s so fd e s i 印j i l g c r o s s o v e ra n dm u 伽o n s p r o b a b i l 姆f i 恤e s ss c a l i i l gc 趾k e 印t h e 谢o l l so f p o p l d 缅n ht l l i sp 印e r ，w ea l s od e v e l o pt h e 叩e r a t i o no fi i l i t i a t i n gp o p u l a t i o n w el l s eu i l i c a s t i n s t e a d0 fd e p t h - f i r s t a r c h b e c a 吣el l i l i c 硒tc a nk e 印n e t w o r k - l ，c r 趾da p p l i c a t i o n - l a y 盯 t o 掣：i h 札u 1 1 i c a s ta l s 0c 姐d e v e l o pi i l i t i a lp o p i l l a t i o n i no r d e rt 0v e m 匆t l 地v a l i d 时o fo i l ra l g o r i t h m s ，w eb u i l du pa 咖r k a n y c a s tr o u t i i l g s i m l l l a t o r s i m l l l a t o r s i l l t ss h o wt h a tt h ea l g o r i t l l mh 舔ab c 仕盯p e r f b n n a n c e k e yw o r d s ：锄y c a s tq o sr o u t i n g ；g e n e t i ca l g o r i t l l i n ；删卸l eq o sp a 珊嘶吨c 璐 c 彻s 缸面n e d ；d d a y - c o i l s 缸n e d 3 i i 于单播的造撸q o s 路由麓l 辑算法 1 1 课题的研究背景及意义 第一章绪论 i p v 6 是下一代的网际通信协议，它是为了解决i p v 4 所存在的问题和不足提出来的， 主要是地址枯竭和路由表急剧膨胀的问题。从目前的发展趋势看，i p v 6 会完全取代i p v 4 在互联网上占统治地位。在m v 6 中出现了一个新的通信模式，具有很高的市场价值。 然而目前国内对选播的研究还没广泛地展开。研究和实现口v 6 选播功能具有重要研究 和使用价值。 并且随着网络的快速发展，人们发现传统的“尽力而为”的数据传输服务已经无法 满足网络的正常运行，一些音频、视频等流媒体业务对网络服务质量( q o s ) 提出了更 高的要求【l 】，所以如何解决网络通信的q o s 问题受到了广大研究者的关注。因为a n y c a s t 的特殊定义为解决网络q o s 问题带来了一些便利条件，如a n y c 嬲t 地址对应多个目标结 点，这就为q o s 资源预留提供了更多的选择余地【2 】。但是到目前为止，对多q o s 约束 的选播路由问题的研究才刚刚起步，还有不少问题需要解决。 本文的研究将针对选播模式中的多q o s 约束的路由问题进行了研究，重点考虑带宽， 时延等约束问题。这些研究将是对选播q o s 路由问题研究的一次有益的尝试。 1 2 国内外研究现状 目前对选播的研究主要是从两个方向展开的，一是应用层选播【4 羽，另一是网络层 选播【7 。1 ”，形成这两种研究趋势的原因主要是由于研究者对这两层为选播提供的基础支 持的取舍不同造成的。 应用层选播主要集中在复制服务器的选择上【1 2 1 3 】。应用层选播易于部署，不需要 底层硬件提供新支持，无需占用网络层地址的空间，还可以支持成员负载，磁盘空间等 应用层距离指标。但是由于应用层收集成员性能和网络距离信息的成本较高，且受用户 数、成员数的影响，因此可扩展性不好。应用层选播的重用性比较差，而且缺乏白举功 能，用户必须预先知道一个能够进行成员选择的服务器地址。 网络层选播，主要集中在路由协议、无状态服务问题、组管理协议、地址结构，安 全问题以及可扩展性等方面：网络层选播比较容易获得网络延迟，带宽等底层的距离信 7 基于单播的避播q o s 路由选择 息。网络层选播的重用性非常好，无论什么样一组节点只要申请一个选播地址，就可以 得到选播服务，而且，网络层选播成员为支持选播路由付出的代价只是周期性汇报状态 的开销，与用户以及成员的数量无关。用户在连接选播成员之前，不用进行距离的探测， 也不用向任何做选择的服务器查询。对于用户来说，使用一个选播地址就像使用一个普 通的网络地址一样，用户甚至不必知道该地址对应于多个成员。网络层选播探测距离的 网络开销要比应用层小，但是网络层选播实现方法简单，但是需要修改路由器配置，在 选择标准方面缺乏灵活性。 目前，多q o s 约束的选播路由大都是基于网络层选播研究，路由选择是完成网络业 务的一个重要组成部分。研究表明【1 4 1 ，多q o s 约束的路由选择是n _ p 完全问题，人们常 用启发式算法或人工智能的方法来解决。很多的研究者用遗传算法来解决多q o s 约束的 选播路由选择问题【1 5 。6 】，因为遗传算法能从全局高度求出问题的最优解。但是用遗传算 法来求解多q o s 约束的选播路由选择存在下面一些问题： ( 1 ) 使用的基本遗传算法本身存在一些缺陷，比如容易局部收敛等问题。而且遗传 算法中初始种群的构造，适应值函数的设计还有改进的空间。 ( 2 ) 目前使用的路由选择的算法只考虑了q o s 问题，但是现实的网络中还需要考虑 其他的一些因素，所以目前的基于遗传算法的路由选择算法存在实用性欠缺的问题。 1 3 本文研究内容 本课题的研究内容主要包括以下几个方面： ( 1 ) 研究选播通信服务及其实现的主要技术，了解选播的各种具体应用，分析网络 选播研究现状，并指出尚待解决的问题。 ( 2 ) 根据选播业务的q o s 要求定义选播q o s 路由网络模型，建立相应的选播q o s 路 由优化目标函数； ( 3 ) 研究下一代网络的通信模型，使用单播的技术获取遗传算法的初始种群。 ( 4 ) 针对不同的优化目标及标准的遗传算法存在的缺陷。对以前使用的基于遗传算 法的多q o s 选播路由算法进行了改进。 ( 5 ) 建立选播路由算法仿真模型，对算法进行仿真实现，分析评价算法的性能。 广西大尊q 曩士论丈童i 于单播的捆l 播0 0 s 路由避择 1 4 本文的组织结构 本文其余各章的组织结构安排如下： 第二章对本文涉及到的选播通信服务、遗传算法、网络服务质量做简单的介绍， 定义选播服务的网络模型，分析其路由问题。 第三章描述受时延约束的选播q o s 路由问题，结合模拟退火遗传算法提出相应的 求解算法，最后通过仿真实验对算法的有效性进行分析。 第四章描述网络的多个参数约束的问题，结合自适应遗传算法与适应度尺度变换 的算法给出多q o s 选播路由问题的求解算法，并通过仿真实验对算法的有效性进行分析。 第五章对整个论文研究的工作总结，指出研究工作中存在的问题以及进一步研究 的工作方向。 广西大学硬士掌位谶 乞 囊i 于单捆的琏播o o s 路由琏择算法 第二章相关理论介绍 本文所做的研究主要是把遗传算法应用于求解多约束下选播路由选择问题。本章主 要介绍选播通信服务、遗传算法、q o s 路由等与研究内容相关的基础理论。 2 1 选播服务 选播( a n y c a s t ) 是一种新型的网络服务“”，与单播和组播一样成为i p v 6 下的三大通 信模式。选播实现从一台主机向一组目的主机中离用户“最近”的一台目的主机进行通 信。通常选播组的成员是一组能够提供相同服务的复制主机( 或网络节点，如路由器) 。 例如，多个w w w 镜像服务器可共享一个选播地址，为了得到所需信息( 如天气情况、股 票数据等) ，用户通过选播服务机制可获得这些服务器中“最近”的一个提供服务。选 播对于改善网络和服务器的负载平衡、简化某些网络应用有着广泛的前景。 随着网络的高速发展，研究者利用复制服务器等方法来分摊网络上的流量等压力。 这也是选播产生的最初的目的之一。利用选播技术，用户只需关心他们需要得到的是什 么服务，而不必知道这个服务是从什么地方来的。例如当用户主机需要获取某类数据报 时，他提供该选播服务的网络地址，然后网络自动为该主机找一个合适的服务器来接受 这些数据报。这种无须用户参与的服务器的选择方式，可以减少用户的盲目参与，提高 网络的利用率。 ( 1 ) r f c l 5 4 6 “7 1 选播中的定义 文献 1 7 为i p v 6 定义了一种选播服务主机向一个选播地址发送数据报，网络 负责尽力将数据报传递到至少一个，最好也是一个，按选播地址接收数据的服务器上。 根据r f c l 5 4 6 的说明，i p v 4 的选播地址不同于i p v 4 的单播地址，它建议从i p v 4 的地 址空间分配出一块独立的地址空间作为选播地址空间。r f c l 5 4 6 定义的这种选播没有得 到广泛的使用。 ( 2 ) r f c 2 3 7 3 “”i p v 6 选播中的定义 1 9 9 8 年的r f c 2 3 7 3 提出了i p v 6 寻址体系结构在这个文档中选播的定义是发送到一 个选播地址的报文被传送到由该地址标识的接口之一( 最近的一个，根据路由协议的距 离量度标准) 。 1 0 基于单磐的琏播q o s 路由选择 r f c 2 3 7 3 定义的i p v 6 的选播模型没有限制路由选择的下部结构，也没有限制可使用 该服务的上部协议，但鉴于选播技术尚不成熟。r f c 2 3 7 3 对i p v 6 的选播模型增加了几项 限制。 2 1 1 其他的通信模式 ( 1 ) 单播( u n i c a s t ) ”1 单播是一种一对一的通信方式。在单播的通信方式下，从一台主机发送出的每个数 据报只能传送给一个目的主机，而目的主机由数据报中的i p 目标地址决定。单播通信 要求在发送方和接收方之间有单独的数据通道，如果有另外的多个用户希望同时获得这 个数据报的拷贝，发送方主机必须向每个希望接收此数据报的用户发送一份单独的数据 报拷贝。 ( 2 ) 组播( 叫l t i c a s t ) 刘 组播是指i p 分组由源端向目的端集中的每一个节点传送。分组被发送到特定的 组播组。只有属于该组播组的目的端才能接收此数据。该组以外的其他目的地( 客户端 用户) 均接收不到。组成员是动态的，它可以在任何时候加入或离开一个组，组的大小 与位置没有限制，一个主机可以是多个组的成员。采用组播方式发送数据，单台服务器 可以对几十万台客户机同时发送连续数据而无延时。媒体服务器只需要发送一个数据 报，而不是多个，所有发出请求的客户端都能共享同一信息包。 ( 3 ) 广播( b r o a d c a s t ) o ” 广播是源主机向一个网段中的所有i p 主机发送数据信息，该网段中的所有主机 都可以接收这个数据信息。广播存在着一些问题，即同一网络链路上的大量广播意味着 该链路上的所有每个结点都必须处理所有广播，其中绝大部分结点最终都将忽略该广 播，因为该信息与自己无关。把广播在子网之间进行转发将导致更多的问题，因为路由 器上将充斥着这种业务流。所以在i p v 6 中取消了广播通信模式。使用一个“所有结点” 组播地址来替代那些必须使用广播的情况，同时，对那些原来使用了广播地址的场合， 则使用一些更加有限的组播地址。 2 1 2 选播的服务系统框架 a n y c a s t 是一种新型的网络服务，是点对多点中一点的通信，是i p v 6 的一个新 l 于单播的造播q o s 路由选择 特性。与组播类似，a n y c a s t 也是多个节点共享同一地址，不同的是组播中同一组播地 址的每个节点都期待接收发给该组播地址的数据报，而a n y c a s t 数据报将被投递到离 这组主机中最近的任意一台。传统的单播通信也可以看作是接收组大小为一的a n y c a s t 通信的一个特例。 为了更好地说明选播的含义，我们借助图2 1 进行说明。假设有三个配置了选播地 址的m 的服务器，分别放置在网络中不同的位置，如图2 1 所示，客户机1 发出的请求 将由路由系统转发到离各用户最近的服务器，假如服务器1 离客户机1 最近，则客户1 由服务器1 来提供服务。 2 1 4 选播目前研究的现状 图2 1 选播服务示意图 f i g i l 2 - 1s c h e m a t i co f 卸y c a s ts e r v i c e 选播作为下一代网际协议i p v 6 三大通信模式之一，其重要性是显而易见的，但是 选播的研究才刚刚起步，还存在不少的问题，需要我们去解决，下面对选播的应用范围 及现在存在的一些问题进行简要的介绍。1 。 2 1 4 1 选播的应用范围 1 最优服务器的选择 从选播的语义中，我们可以看出选播的最基本的功能是在一组服务器为用户选择一 个“最优”服务器。一组服务器使用同一个a n y c a s t 地址，用户应用程序则只要直接连 接这个地址，就可以得到性能最好的服务器。这样即方便用户的使用，又可以提高服务 器的性能，并且能避免用户的直接参与的盲目选择所带来的效率损失。 2 主机的自动配置 1 2 广西大孽q 肚论文l 于单播的避播q o s 路由琏择 主机的自动配置是提出选播服务的另一个主要目的o ”1 。这主要针对d n s 及其类似 服务。有了选播服务，用户在进行d n s 解析时，只需要向全球惟一的某个代表d n s 服务的 知名选播地址发送查询请求即可得到地址解析的结果。这样，即使主机移动到一个新的 网络也不需要重新配置本地d n s 服务器地址。 3 分摊网络上的负载 因特网呈指数级的增长。分布式服务面临服务器严重超载，带宽浪费和延迟增加严 重。由于选播的目的组是有一组服务器形成的，这些服务器被放在了不同的地理位置， 对不同的用户，选播组提供不同的服务器为他们提供服务，从而有可能解决平衡服务器 和网络负载。 2 1 4 2 选播研究存在的问题 1 路由协议 对于选播路由协议的研究主要有两个方向。一个方向是在i p v 6 中使用与u n i c a s t 地 址相同的a n y c a s t 地址，另一个方向定义类似于m u l t i c a s t 的独立路由算法和协议。但是 使用与u n i c a s t 相同的地址则意味着一个地址对应多台主机，这对现有的路由协议来说 还是一个问题。如果是定义一个新的路由协议将是一个十分浩大的工程，因为路由问题 不是一个单一的问题，它与服务体系结构的各个方面，如地址结构、组管理、安全管理 形式等紧密相关。因此，研究a n y c a s t 路由除了需要考虑对服务可用性的支持外，还必 须考虑其他方面的支持和制约，还要兼顾对网络性能、网络设备性能的影响以及同原有 路由协议的兼容性。 2 无状态服务问题 所谓无状态的连接服务，就是将a n y c a s t 数据报投递到最近的服务器，而路由过程不 依赖于以前的数据报，这是哪c a s t 的自然属性，正是这种属性使a 叫c a s t 能够平衡网络 的负载但是，数据报被分段或者属于基于连接的应用程序，这种无状态服务会引起意 想不到的问题，同一个客户的前后两个数据报被投递到不同的a n y c a s t 服务器，除非这 两个数据报是独立的请求，互相之间没有关联，否则这些投递对a n y c a s t 就失去了实际 的意义。 3 组管理协议 如果任意一个实体都通告自己为a n y c a s t 服务器，那么，一台恶意主机就可以利用 | i 于单翔。的琏翱 o o s 鬓 由避摔 这个机会向客户提供虚假信息，恶意主机还可以通过广播虚假服务器地址创造“黑洞”， 使路由到这台假主机的a n y c a s t 请求到达一台不能应答的欺骗主机，所以我们必须有一 种机制控制a n y c a s t 组成员关系的操作。 4 地址问题 目前主要存在着两种地址模型。一种地址模型是在r f c l 9 3 5 中提出的，其思路是在 u n i c a s t 地址空间中分配a n y c a s t 地址，这样u n i c a s t 和a n y c a s t 地址从结构上没有任何 区别，可以缓解a n y c a s t 带来的路由表规模扩张问题，同时使路由简单。但是也增加了识 别a n y c a s t 数据报的难度。另一种是i p v 6 的模型，它建议给a n y c a s t 分配独立的地址 空间。其实，i p v 6 使用u n i c a s t 地址空间并不能够从根本上解决a n y c a s t 的可扩展性限 制，例如全球a n y c a s t 地址仍然需要作为独立的路由表项。究竟采用哪一种a n y c a s t 的 地址模型更有利于a n y c a s t 服务的开展还有待于相关研究的进一步论证。 5 q o s 问题 q o s 问题已经得到受到人们极大的关注，但是，这个领域中仍然有许多问题等待解 决。a n y c a s t 一经提出，它的q o s 保证也引起了研究者的兴趣。a n y c a s t 的特殊语义为q o s 的研究提出了挑战，但同时也给这个问题带来了一些便利条件。a n y c a s t 的q o s 的保证是 q o s 领域的一个分支，现有q o s 领域的一些问题在这个分支中同样存在，同时，它自身的 特性也会引起一些特殊的问题，当然，也可能会带来一些方便。 6 可扩展性 单播路由协议通过把同一前缀的目标地址汇聚为一条路由项达到减小路由表规模 的目的。但是，a n y c a s t 并不遵从这种层次汇聚规则。一个a n y c a s t 地址表示的是共享某 个特性的结点组，这些结点可能分散在互联网的各个地方。如果用单播路由协议实现 a n y c a s t 路由，则每个全球a n y c a s t 地址必须作为独立的路由表项处理。这种要求使路由 表会随全球a n y c a s t 组数成比例增长，形成了a n y c a s t 的可扩展性问题。 i p v 6 规定从单播地址空间分配a n y c a s t 地址，这种分配方法使a n y c a s t 地址无法同单 播地址区分开。i p v 6 将每个a n y c a s t 组成员限制在共享一个地址前缀的特殊拓扑区内， 在这个拓扑区域中，a n y c a s t 地址在单播路由系统中是独立的表项，在该拓扑区域外， a n y c a s t 地址被汇聚到其所在区域的地址前缀的路由项中传播。通过把a n y c a s t 组限制在 一个预定义的区域内，i p v 6 减轻了a n y c a s t 的可扩展性问题，但是并没有完全解决它， 因为全球a n y c a s t 地址仍然必须作为独立的路由项在互联网中传播。而对某些应用来说， 全球a n y c a s t 地址是必需的。 1 4 l 于单糟的t 播q o s 路由选择 2 2q o s 技术 2 2 1q o s 提出的原因 早期的i n t e r n e t 应用主要是电子邮件，文件传输和远程登录等。这些应用对于数据 丢失很敏感，但对数据传输的实时性不敏感。由于可靠的数据传输( 如t c p ) 可以建立 在不可靠的网络( 如i p ) 上，所以对网络传输的差错率并没有太高的要求。随着i p 网络 应用的发展，人们已不满足于网络所提供的最小功能，而是要求在i n t e r n e t 上开展各种 音频和视频等流媒体业务。流媒体业务在实时的多媒体业务( 例如应用于i p 电话，视频 点播，视频会议等) 各种流媒体业务的引入，对数据的传输不仅要保证足够的带宽，还 要满足低延迟，匀时性等要求。为了提供足够的网络服务，必需增加一些定量或定性i p 服务，服务质量通过管理网络资源来改善网络服务和满足更多不同需求的网络应用。 2 2 2q o s 的定义 从一个源到一个目标的分组流( s t r e a ) 称为一个流( f l o w ) 。在面向连接的网络中， 属于同一个流的所有分组将会走同样的路由路径；而在无连接的网络中，它们可能会走 不同的路径。我们可以用4 个参数来描述每个流的需求特征：可靠性、延迟、抖动和带 宽。这4 个特征合起来决定了一个流所要求的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 。 2 2 3q o s 的体系结构 目前互联网工程任务组i e t f 建议了多种服务模型和机制以满足q o s 的需求，其中比较 有名的三大体系结构；综合服务，区分服务，m p l s 汹3 ； ( 1 ) 综合服务( i n t s e r v ，i n t e g r a t e ds e r v i c e sa r c h i t e c t u r e ) 综合服务由i e t f 的i n t s e r v 工作组于1 9 9 4 年提出，其目的在于建立一个能同时提供实 时和非实时业务的包交换网络。 在综合服务的体系结构中，主要的i e t f 协议是资源预留协议( r s v p ) 。利用该协议 可以完成资源预留工作；若要发送数据则还需要使用其他的协议。r s v p 允许多个发送方 给多个接收组传送数据，也允许接收方单独自由地切换信道，并且在优化使用带宽的同 时消除拥塞的发生。 在进行资源预留的时候，接收方可以( 有选择地) 指定一个或者多个期望的数据源， 广西，o 缸硕士论文童i 于单捆 的选捆- q o s 路由避辟 它也可以指定“在预留期间这些选择可以固定不变”，或者指定“它是否希望以后还可 以改变数据源”。路由器利用这些信息来优化带宽的使用计划。尤其是，如果两个接收 方都同意以后不再改变数据源的话，那么它们只需共享一条路径即可。 综合服务的缺陷是扩展性比较差，为了建立数据流，这些算法也牵涉到路由器之间 复杂的信息交换。因此r s v p 几乎没有具体实现。正是由于i n t s e r v 的发展遇到了难以逾 越的障碍，人们的研究目标便逐渐转向为一种更为简单有效的方法一一d i f f s e r v ( 2 ) 区分服务( 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 sa r c h i t e c t u r e ) d i f f s e r v 提供一种对各种应用的服务级别进行划分的简单的、比较粗糙的方法。它 在核心路由器中仅仅保存少量的流聚集的信息，而大量的业务流的状态信息则保存在端 系统中，核心路由器则专注于数据报的转发，从而也就提高了网络的可扩展性。 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 ，p s ) 。对于每种服务级别，i e t f 定义了相应的p h b ，确保服务和奖 赏服务分别对应快速转发( e x p e d i t e df o r w a r d i n g ，e f ) 和确保转发( a s s u r e d f o r w a r d i n g ，a f ) 。 我们把服务类型分为两种：常规的和快速的，大多数的通信流量属于常规流量，但 是有一小部分属于快速类别。快速类别的分组可以直接通过子网，好象不存在其他任何 分组一样。 确保型服务是一种更为精细的服务，它分为4 种优先级别，每种级别都有它自己的资 源，而且，对于正在经历拥塞条件的分组，它定义了三种丢弃概率：低，中，高，将两 者结合起来，共有1 2 种服务类别。 ( 3 ) 肝l s 当i e t f 完成综合服务与区分服务时候，有些路由器厂商还在努力提出更好的转发方 法。其工作思路是，在每个分组的前端增加一个标签，然后根据这个标签而不是根据目 的地址进行路由。 一个m p l s 网络由标签边缘路由器( l e r ，l a b e le d g er c 懒) 和标签交换路由器( l s r ， l a b e ls 州t c h i n gi b u t c r ) 组成。通过标签发布协议( l d p ，l 舭ld i s t r i b 砸o np m 妣0 1 ) 在节 点间完成标签信息的发布。l e r 与l s r 、l s r 与l s r 之间依然需要运行路由协议，它们通过 路由协议来获取网络拓扑信息，并根据这些信息决定数据报的下一跳( 在第三层转发时) 或交换路径如何建立( 在第二层转发) 。m p l s 入口路由器( 也称l e r ) 不是将f e c 映射到下一 跳路由器，而是在分组上添加表示分组归属f e c 的一个标签。 1 6 墓于单撸的选揞0 0 s 路由选择 2 30 0 s 路由算法 2 3 10 0 s 路由的研究目标 q o s 路由的提出是为了获取在服务提供者和用户之间的质量与数量上的行为保证。 在q o s 路由下，报文流的路径将被网络中的资源可用性和流的q o s 需求所决定，当前q o s 路由问题的研究的主要目标是： ( 1 ) 动态决定合理的路径。q o s 路由能动态地从所有可能的选择中挑出一条满足流 的q o s 需求的路径，这个路径是由一些度量值决定的，如链路代价，带宽等。 ( 2 ) 优化资源的利用率。如果一个网络的状态由q o s 路由所决定的话，能从整体上 来提高网络的有效利用率。 ( 3 ) 支持资源预留。对报文流提供端到端的确保( 延迟，延迟抖动等) 。在确定 了报文流的q o s 路径后，要对该路径上所需要的资源进行预留。 2 3 20 0 s 参数度量 对于服务质量选路算法，只知道网络连通性是不够的，还需要知道网络的当前可用 资源情况，即可用带宽、链路时延等度量参数。度量是路由选择算法在选择路径时所要 依据的重要参数。q o s 是需要通过可测量的q o s 度量来实现的。常用的几种q o s 度量参数 主要包括：可用带宽、端到端时延、分组丢失率、转发跳数( h o pc o u n t ) ，( 数据) 抖动 和成本等，不同的度量具有不同的性质。q o s 度量根据性质的不同可以分为相加性度量、 相乘性度量和凹性度量3 类。对于图g 中的路径p = ( v ，v 。，v s ) ，若e 。，p ，将e 。的第j 个 属性记为m ( v 。，v ，) ，整个路径p 的属性记为m ( v ：，v 。) ，则以上3 类度量的定义如下。”： ( 1 ) 相加性度量 若对任意路径路径p = ( v 。，v 。，v ；) ，如果 m ( v lv 0 = m ( v 1 ，v 2 ) + m ( v 2 ，v 3 ) + + m ( v k ，v s ) ， ( 2 1 ) 则称路径p 的这个属性为相加性度量。相加性度量就是该路径的度量值是该路径所经过 的各链路相应加性度量参数之和。相加性度量包括延迟、抖动、花费、转发跳数( h o pc o u n t ) 等。例如，一条路径p 的延迟为从源到目的地的所有链路延迟的总和。 ( 2 ) 相乘性度量 若对任意路径路径p = ( v 。v 。，v 。) ，如果 1 7 基于单播的遣播0 0 s 路由琏择 m ( v 1v 。) = m ( v i ，v 2 ) 棚( v 2 ，v 3 ) 丰栅( v bv 。) ， ( 2 2 ) 则称路径p 的这个属性为相乘性度量。相乘性度量就是路径的度量值是该路径所经过的 各链路的相乘性度量参数之积。例如，分组丢失率为相乘性度量，其中链路丢失率在求 解有关相乘性度量的过程中，可以类比参照相加性度量的有关求解方法。 ( 3 ) 凹性度量 若对任意路径路径p = ( v ，v 2 ，”，v 。) ，如果 m ( v i ，v s ) = m i n m ( v lv 2 ) ，m ( v 2 ，v 3 ) ，m ( v bv 。) ( 2 3 ) 或者 m ( v lv s ) = m a x m ( v lv 2 ) ，m ( v 幻v 3 ) ，m ( v k ，v 。) ( 2 4 ) 则称路径p 的这个属性为凹性度量。凹性度量意味着该路径的度量值为所经过链路中的 最大或者最小凹性度量参数值，例如，带宽为凹性度量，即路径带宽为路径上瓶颈链路 的带宽。例如，求解多重凹性度量的组合可以在多项式时间内完成，而多重相加性度量 的组合通常不能在多项式时间内完成。 本论文中使用的q o s 参数如下所示： ( 1 ) 带宽( b a n d w i d t h ) ：是网络发送数据能力的一种度量，是指单位时间内传送的 i p 包数量。 ( 2 ) 时延( d e l a y ) ：端到端的时间延迟，即两个参照点之间发送和接收数据报的 时间间隔。 ( 3 ) 时延抖动( d e l a y _ j i t t e r ) ：抖动是指时延的变化，即相邻两个数据报到达接 收者的时间间隔与发送者发送这两个数据报的时间间隔之间的差异。 ( 4 ) 包丢失率( p a c k e tl o s sj i t t e r ) ：是指网络中传输数据报时丢弃数据报占全 部传输包的比率。丢包主要是由于网络拥塞引起的。 ( 5 ) 代价( c o s t ) ：可以是链路使用的价格或链路上某些网络资源使用状态的测度。 当路由选择的约束条件包含两个或两个以上的加法型度量，如延迟，代价等，或包 含加法型度量与乘法型度量的组合时，该路由选择问题为n p - 难解问题。 2 3 30 0 s 路由策略 q o s 路由功能负责为业务流量选择能够满足其q o s 需求的一条路径，被选择的路径通 常不是传统的最短路径。根据所含q o s 参数的细节和数量，路径选择所需计算的开销会 1 8 墓于单播的选播q o s 路由选择 随着网络规模的增加而急剧增大。因此，实用的q o s 路由方案主要考虑采用一个q o s 参数 ( 如带宽或时延) 或两个q o s 参数( 如成本一时延，成本一带宽和带宽一时延) 的实现方法， 为了进一步降低路径计算的复杂性，人们提出了多种类型的路由策略。根据状态信息如 何维护和如何实施搜索可行路径，可以将q o s 路由方法分为源路由、分布式路由和分层 路由三种。 ( 1 ) 源路由策略 每个节点都需要保留全网的状态信息，包括网络拓扑，到达其他节点的路径的度量 参数值等。用户的业务请求到达时，源节点根据网络状态信息和业务度量参数要求计算 路径，如果存在合适的路径，则由源节点沿所选路径发送资源预约信令建立路径 源端路由方法实现起来简单灵活，源节点可以独立选择路由算法计算路由，不需要 多节点协同进行路由选择，可以避免分布式路由中死锁和环路等现象。在基于源的发送 策略中，更容易设计出可实现的低复杂度路由算法，但源路由的路由开销大，状态信息 准确性不高，网络扩展受限，这几个问题都与节点需要保留全网络状态信息有关。 ( 2 ) 分布式路由 路由选择由多个节点协同完成，每个节点存到所有目的节点的下一跳列表，当收到 一个数据报时，路由节点仅查表确定下一跳节点，然后发送数据报。这样，数据报经由 每一个节点一跳接一跳地前向发送。分布式路由一般是通过分布式地发送信令过程实现 的。每个节点通过信令了解本节点对应于到达某个节点的某种业务的前一段节点和后继 节点。 分布式路由存在两个问题，一是环路问题，网络中各个节点保留的其他节点状态信 息不一致或者节点路由信息不准确都可能引起环路；另一个问题是多个路由节点如何有 效协同。 ( 3 ) 层次路由 在层次路由选择中，节点簇集成组，并把一组网络节点“浓缩”成一个逻辑节点： 然后组又簇集成更高一级的组，产生一个多级的层次节点。每个组内节点都维护一个汇 聚的全局状态信息，最上层的逻辑节点间采用源端路由找到一条可行逻辑路径，随后沿 该路径发送控制信息。当路径上逻辑节点所代表的组边界节点( 即下层逻辑节点) 收到 信息后，该节点在组内仍采用源端路由选择路径至整个组。递归这样的过程，直到路由 到目的节点。 层次路由的每个节点只需维护部分的全局信息，因此可扩展性较好；在每一层的逻 1 9 广西大掣h 曩鼍斗套文l 于单播的选播q o s 路由琏择 辑节点依据汇聚信息直接采用源端路由，因而继承了源端路由的优点；同时路由计算是 由路径上的各个节点共同分担，因而也继承了分布计算的优点。层次路由对大型网络而 言是最有前途的路由策略。但是，由于汇聚信息引入的不精确性，层次路由在一些情况 下也可能导致选路失败。 2 3 4 现有路由算法存在的问题 目前q o s 路由算法的研究还存在一些问题嘲： ( 1 ) 多孤立考虑q o s 约束，没有兼顾考虑q o s 的其他网络要素。 目前提出的q o s 路由算法多是孤立的考虑所需要满足的q o s 约束条件，没有考虑多媒 体传输必须要的其他网络要素，如：调度策略，资源预留策略以及接入控制策略等等， 如何协调个很重要素以及有效的解决他们之间的相互制约关系是一项重要的研究内容， 没有考虑爵络负载平衡，碍络韵整体性能和网络状态非精确性带来的影响。 ( 2 ) 分级路由仍是一个没有能解决的问题。 分级路由由于具有很好的扩展性能，倍受网络界的关注，但算法需要收集多个网络 结点的状态信息，增加了结点状态的不精确性。且对于多约束路由问题，如何有效地收 集网络结点地状态信息，至今仍然是技术难题。有调地分级路由算法目前尚未出现。 ( 3 ) 没有出现有效的重路由策略 算法都只保证找到一条路由路径即可，路由失败，也仅仅给出失败消息，这样的算 法对于q o s 要求的业务是不完全的，一个实用的q o s 路由算法在网络不存在满足约束条件 的路由路径时，应与应用协商q o s 路由而不只是简单地给出路由信息，且协商后能更具 应用给出地约束条件再次进行路由计算。另一种情况，路由选择也仅根据路由请求时网 络状态进行，作为分布式网络环境，网络状态时刻变化( 如主机的连接加入和退出等) ， 不断变化的网络状态可能导致原来选择的路由路径不是最佳，特别对于具有优先级的网 络，高优先级路由请求应能抢占低优先级的路由会话，被抢占的路由会话不能简单的终 止会话，而应进行重路由。当然，重路由在实际中不能使用太多，过多的重路由容易引 起网络的震荡，这就设计到协调优化的问题。 ( 4 ) 没有考虑q o s 路由与传统路由融合 算法只是孤立的考虑q o s 路由计算，没能兼顾考虑q o s 路由同传统尽力而为路由融合 问题，下一代网络除了传输q o s 业务，还要考虑传输传统尽力而为传输业务。因此，在 基于单捆 的坷l 播0 0 s 路由选择 设计q o s 路由算法时，应综合考虑q o s 路山与传统极力而为路山的融合问题，两种路由技 术应互相协调，互不千涉。 ( 5 ) 没有有效的动态路由算法 动态性时网络的固有特性：例如，网络结点无规律的加入或者退出，多媒体应用的 随机产生和结束，链路传输报文的大小时常改变等，网络运行环境的复杂性决定了网络 状态具有动态性，这木质上也要求路由算法具有动态性，以适应网络状态的动态变化。 特别时对于多数组播应用而言，组播成员也多是不确定的，组播成员可能随时随机加入 和退出。具有动态变化特性的组播应用要求相应的组播路由算法也具有动态性，以支持 组播成员动态变化，但是考虑网络动态特性的q o s 路由算法很少。 ( 6 ) 多局限于单纯的的启发式搜索思想，没有提出新的搜索方法 尽管启发式搜索算法是一种简单有效的