（运筹学与控制论专业论文）基于qos约束的选播路由算法研究.pdf

东北大学硕士学位论文 摘要 基于q o s 约束的选播路由算法研究 摘要 随着计算机和网络技术的迅猛发展，网络服务需求已超过了网络的服务容量，对具 有q o s 服务的应用产生了严重的影响。为了增强服务的可用性和改善网络的流量分布， 通常的方法是在网络中复制服务器。为研究此类网络通信，近年来，人们提出了“选播” 的通信模型，选播使得用户通过一个选播地址就能访问到该地址所表示的一组服务器中 对用户来说“最近的”一个，由于越来越多的应用需要选播服务，因此选播通信已被规 定为i p v 6 中的一种标准通信模型。 本文首先介绍了选播通信服务的研究现状以及q o s 路由的基础理论，然后在分析基 本q o s 选播路由算法的基础上，提出了两个算法：一是基于时延、带宽和费用约束的选 播路由算法，该算法以s s p ( s h o r t e s ts h o r t e s tp a t h ) 算法为基础，以各条路径的瓶颈带宽 与最小时延和费用乘积的比值作为选路的依据，均衡网络负载，同时减小网络费用；二 是基于遗传算法的选播路由算法，该算法考虑了时延和费用，采用了一个新的适应度函 数，可以根据网络的实际需求通过调整参数来选择路径，从而达到网络的时延和费用折 衷。该算法充分体现遗传算法所具有的鲁棒性强、并行搜索、群体寻优的特点。 为了验证两种算法的可行性，我们进行了仿真实验。仿真结果表明，第一种算法所 用时延与s s p 算法相差不多，但费用明显降低：第二种算法利用节点序列编码使得遗传 操作更加容易、有效，提出的路径选择算子能够避免路由计算陷于局部最优解，采用的 适应度函数使时延和代价能在较小的进化代数内收敛到全局最优解。因此，这两种算法 是可行的，同时具有很好的性能。 关键词：选播；服务质量；路由算法；遗传算法 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho nq o s - b a s e d a n y c a s tr o u t i n ga l g o r i t h m s a b s t r a c t w i t ht h er a p i dp r o g r e s so ft h en e t w o r ka n dc o m p u t e rt e c h n o l o g i e s ，n e t w o r ks e r v i c e r e q u i r e m e n t se x c e e dt h ec a p a b i l i t i e so ft h en e t w o r k ，w h i c hc a u s e sag r e a ti n f l u e n c et o a p p l i c a t i o no fq u l i t yo fs e r v i c e ( q o s ) ho r d e rt oe n h a n c et h es e r v i c ea b i l i t ya n di m p r o v e n e t w o r kf l o wd i s t r i b u t i o n ，w eu s u a l l yd u p l i c a t es e r v e r si nt h en e t w o r k i nr e c e n ty e a r s ，p e o p l e r a i s e d t h ec o m m u n i c a t i o nm o d e lo f “a n y c a s t t or e s e a r c ht h i sk i n do fn e t w o r ks e r v i c e a n y c a s th a sn u m e r o u sp o t e n t i a la p p l i c a t i o n s ，a n di sr e c o g n i z e da sau s e f u ls e r v i c e m o r ea n d m o r ea p p l i c a t i o n sa r er e l a t e dt oa n y c a s t ，s oa n y c a s ti sas t a n d a r ds e r v i c em o d e ld e f i n e db y i p v 6 i nt h i sd i s s e r t a t i o nw ef i r s tg e n e r a l i z et h ed e v e l o p m e n to ft h ea n y c a s tc o m m u n i c a t i o n s e r v i c e ，a n di n t r o d u c et h eb a s i ct h e o r yo fq o sr o u t e a n da l s ow ep r o p o s et w oa l g o r i t h m so n b a s e do fc u r r e n ta l g o r i t h mo fq o sa n y c a s tr o u t e ：f i r s t ，t h ea n y c a s tr o u t ea l g o r i t h mw h i c hi s b a s e do nt h eb a s i so fs s p ( s h o r t e s ts h o r t e s tp a t h ) w i t ht h ec o n s t r a i n to ft h ed e l a y , b a n d w i d t h a n di t sc o s t ；s e c o n d ，t h ea n y c a s tr o u t e a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m i nt h ef i r s t a l g o r i t h m ，w es e l e c tt h er o u t ea c c o r d i n gt ot h er a t i oo fb o t t l e n e c kb a n d w i d t ho fe a c hr o u t et o t h ep r o d u c to ft h em i n i m u mt i m ed e l a ya n dt h ec o s tt om a k et h en e t w o r kl o a ds t a t u e s q u ea n d r e d u c et h ec o s to fn e t w o r k i nt h es e c o n do n e ，w ec o n s i d e rt h ed e l a ya n dt h ec o s t ，a n du t i l i z ea n e wf i t n e s sf u n c t i o nt ot h ec o m p r o m i s eo ft h ed e l a ya n dt h ec o s to fs e r v i c eb ya d j u s t i n g p a r a m e t e r sa n ds e l e c t i n gt h er o u t ea c c o r d i n gt ot h er e q u e s t t h es e c o n da l g o r i t h mh a st h e p r o p e r t i e so fg e n e t i ca l g o r i t h ms u c ha sg o o dr o b u s t n e s s ，p a r a l l e ls e a r c ha n dp o p u l a t i o n o p t i m i z a t i o n i no r d e rt od e m o n s t r a t et h ea l g o r i t h m s f e a s i b i l i t y , w eg i v eo u tt w os i m u l a t i o n s t h e r e s u l t so ft h ee x p e r i m e n t ss h o w ：t h ed e l a yi sc l o s et ot h es s pa l g o r i t h m a n dt h ec o s ti nt h e f i r s ta l g o r i t h mi sl o w e rt h a ns s pa l g o r i t h m a p p a r e n t l y ；i nt h es e c o n da l g o r i t h m ，w ep r o p o s e r o u t ec h o o s i n go p e r a t o rt oa v o i db e i n gi m m e r s e di n t ol o c a ls o l u t i o na n du s en o d es e q u e n t i a l c o d i n gt om a k et h eg e n e t i co p e r a t i o ne a s i e ra n dm o r ee f f e c t i v e a n da l s ot h ep r o p o s e df i t n e s s i i i 东北大学硕士学位论文a b s t r a c t f u n c t i o nc a ng u a r a n t e et h ed e l a ya n dt h ec o s tc o n v e r 舀n gt oag l o b a lo p t i m a ls o l u t i o n a sa r e s u l t ，t h et w oa l g o r i t h m sa b o v ea r eb o t hf e a s i b i l i t ya n dh a v eg o o dp e r f o r m a n c e s k e yw o r d s ：a n y c a s t ；q o s ( q u a l i t yo fs e r v i c e ) ；r o u t i n ga l g o r i t h m ；g e n e t i ca l g o r i t h m 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ：t 目。 学位论文作者签名：阔建峰 日期：卅、；、1 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意 学位论文作者签名： 签字日期： 导师签名： 签字曰期： 东北大学硕士学位论文 第一章绪论 1 ，1 网络的通讯方式 第一章绪论弟一早三百下匕 i n t e r a c t 是当今应用最广泛，发展最迅速的i p 数据分组交换通信网络，它的迅猛发 展使传统的电路交换通信网络及其通信方式面临严重的挑战和冲击，在1 9 9 9 年，每1 0 秒就有一个新的p c 连接到因特网上去【”。基于i p 的数据、音频和视频等多媒体业务以 其低廉的费用、随处可按入性等优点越来越引人注目。 采用计算机网络通信，不仅大大提高了通信线路的利用率，改善了通信质量，而且 为实现多媒体信息的高速传输以及计算机、电视和电话的三合一奠定了基础。这种相互 连接的计算机信息网络，使距离和时间大大缩小，人们的生活、学习和工作方式也因此 发生了巨大的改变。随着计算机网络的发展，各种新的通讯方式应运而生。 用户的数据从一个终端发送到另一个终端，首先要确定传输路由，不同的通信方式， 其确定路由的方式也不同，网络的通信方式主要有以下几种： 单播f u n i c a s t ：p o i n tt op o i n t ) ：点到点的通信方式。即给定一源节点s 、一目的节点 t 、一组服务质量约束c 和一个可能的最佳化目标，寻找从s 到t 满足c 的最可行路径。 广播( b r o a d c a s t ：p o i n tt oa l lp o i n t s ) ：点到所有点的通信方式。即给定一源节点s 、 一组约束c 以及可能的最佳化目标，寻找从s 出发覆盖网络中所有其它节点且满足c 的最可行的传播树。 组播( m u l t i c a s t ：p o i n tt om u l t i p o i n t ) ：点到多点的通信方式。即给定一源节点s 、一 组目的节点集r 、一组约束c 以及可能的最佳化目标，寻找从s 出发覆盖r 中所有目 的节点且满足c 的最可行的树。 选播f a n y c a s t ：p o i n tt oa n y o n eo f m u l t i p o i n t ) 点到多点中的任一成员的通信方式。 即给定一源节点s 、一组目的节点集a 、一组约束c 以及可能的最佳化目标，寻找从 s 出发到目的节点集a 中任意一个节点且满足c 的最可行传输路径。 单播的实现一般采用d i j k s t r a 提出的最短路径算法( s h o r t e s tp a t ha l g o r i t h m ) 4 1 来建立 点到点的路由。当只有两个终端参与同一进程时，一般采用单播方式。采用单播技术实 现多点通信是一种效率很低的方法，它会导致网络中传送了许多冗余分组，从而浪费带 宽资源。但由于过去只有很少的网络应用涉及到多个用户，而且多数应用带宽要求较小， 东北大学硕士学位论文 第一章绪论 因此传统的点到点通信方式足以使网络满足多点通信业务的带宽要求。 广播是局域网络中常用的通信方式，用于一个节点向网络中所有节点发送信息。在 i p 子网内广播数据包，所有在子网内部的主机都将收到这些数据包。广播意味着网络向 子网中每一个主机都投递份数据包，不论这些主机是否乐于接收该数据包。所以广播 的主要缺点是每个广播都要发送数据至所有机器，消耗了所有枫器的资源，另外广播的 使用范围非常小，只在本地子网内有效。 组播是一个源节点向多个目的节点发送信息( 但不是所有节点) 的通信方式，如果一 台主机发送者同时给多个接收者传输相同的数据，也只需复制一份相同的数据包，它提 高了数据传送效率，减少了骨干网络出现拥塞的可能性。它的应用很多，如多媒体会议、 远程教育等。 组播是目前研究得最多，也是应用最广的网络连接方式。文献【5 】根据链路约束、树 约束和目标函数，把组播路由问题分为以下十二大类： ( 1 ) 链路约束f n ；匿( 1 i n kc o n s t r a i n e dp r o b l e m ) ：规定一个链路约束构造可行的组播树。 例如，带宽约束路由。 ( 2 ) 多链路约束问题( m u l t i p l el i n kc o n s t r a i n e dp r o b l e m ) ：规定两个或多个链路约束来构 造可行的组播树。例如，带宽和缓冲约束路由。 ( 3 ) 树约束问题( t r e ec o n s t r a i n e dp r o b l e m ) ：规定一个树约束来构造可行的组播树。例 如，时延约束路由。 ( 4 ) 多个树约束i , a 题( m u l t i p l et r e ec o n s t r a i n e dp r o b l e m ) ：规定两个或多个树约束来构造 可行的组播树。例如，时延和时延抖动约束路由。 ( 5 ) 链路及树约束问题( 1 i n ka n d t r e ec o n s t r a i n e dp r o b l e m ) ：规定一个链路约束和一个树 约束来构造可行的组播树。例如，时延和带宽约束路由。 ( 6 ) 链路优化问题( 1 i n ko p t i m i z a t i o np r o b l e m ) ：使用一个链路优化函数来构造一个优化 的组播树。例如，组播树中树链路上的带宽最大。 ( 7 ) 树优化问题( t r e eo p t i m i z a t i o np r o b l e m ) , 使用一个树优化函数来构造一个优化的组 播树。例如，组播树的总代价最小。这就是著名的s t e i n e r 树问题。 ( 8 ) 链路约束链路优化问题( 1 i n kc o n s t r a i n e dl i n ko p t i m i z a t i o np r o b l e m ) ：规定一个链路 约束并使用一个链路优化函数来构造一个优化的组播树并实现约束。例如，带宽约束缓 冲优化问题。 ( 9 ) 链路约束树优化问题( 1 i n kc o n s t r a i n e dt r e eo p t i m i z a t i o np r o b l e m ) ：规定个链路约 2 东北大学硕士学位论文第一章绪论 束并使用一个树优化函数来构造一个优化的组播树并实现约束。例如，带宽约束s t e i n e r 树问题。 f l o ) 树约束链路优化问题( t r e ec o n s t r a i n e dl i n ko p t i m i z a t i o np r o b l e m ) ：使用一个树约束 和链路优化函数来构造一个优化的组播树。例如，时延约束带宽优化问题。 ( 1 1 ) 树约束树优化闽题( t r e ec o n s t r a i n e dt r e eo p t i m i z a t i o np r o b l e m ) ：使用一个树约束和 树优化函数来构造一个优化的组播树。例如，时延约束s t e i n e r 树问题。 ( 1 2 ) 链路约束及树约束树优化问题( 1 i n ka n dt r e e c o n s t r a i n e dt r e e o p t i m i z a t i o n p r o b l e m ) ：使用链路和树约束及树优化函数来构造一个优化的组播树。例如，带宽和时 延约束的树优化问题。表1 1 是对以上1 2 类问题的总结。 表1 1 组播路由的十二类问题 t a b l e1 1t w e l v ek i n d so fp r o b l e m sa b o u tm u l t i c a s t 无优化 链路优化 树优化 无约束 6 ，链路优化 7 树优化 多项式时间复杂度n p 完全问题 1 链路约束 链路约束 多项式时间复杂度 8 链路约束链路优化9 链路约束树优化 2 多链路约束多项式时间复杂度 n p 完全问题 多项式时间复杂度 3 树约束 树约束多项式时间复杂度1 0 + 树约束链路优化1 1 ，树约束树优化 4 多个树约束 多项式时间复杂度n p 完全问题 n p 完全问题 链路和树约束 5 链路及树约束 1 2 链路及树约束树优化 多项式时间复杂度 n p 完全问题 选播是点对多点中的一点的通信，选播与组播不同之处在于，组播中每个节点都期 待接受发给组播地址的数据报，而选播的数据报将被投递到离这组主机中最近的任意一 台。 选播是近年来为满足网络服务质量要求而提出的一种新的通讯方式。使用选播服务 可以大大简化一些应用，选播队列可用来从一组可行服务器中找出最合适的一个服务 3 东北大学硕士学位论文 第一章绪论 器，以提高多传送队列的有效性。比如，多镜像网址可共享单个的选播地址，这样，用 户只需要发送一个请求就可取得所需要的信息( 如天气，股市报价等) 。 1 2 选播技术产生的背景 在传统的i n t e m e t 中，i p 业务主要集中在h r r p 、f t p 、e m a i l 等数据业务，在这 些业务类型中，服务器采用单播的方式向每个客户机提供服务。然而，随着i n t e m e t 的 网络规模和用户数量的迅速发展，i n t e m e t 上的业务种类也与日俱增，各种实时和多媒 体业务，如：视频点播、视频会议、远程教学、新闻发布、实时信息公告、分布式网络 游戏、网络电视等业务正在成为信息传送的重要组成部分。 随着更多的网络主机相连，网络服务需求已超过了网络的服务容量，导致了网络服 务质量下降。虽然不影响一些经典的网络应用，比如电子邮件、文件传输等，但对需要 实时服务的应用产生了严重的影响，如视频点播、i p 电话等。 如何在网络中实现多种服务质量是全世界计算机、电子与通讯领域竟相研究的前沿 课题。为提高网络的服务质量和提供网络的负载平衡，通常应用的方法是在网络中复制 服务器吼如w w w 的m i r r o r 站点、s o c k 服务器、股票服务器、计算服务器和代理服 务器等都属于此类结构。复制服务器技术分为两类：本地复制和分布式复制。本地复制 主要采用服务器组群技术，这些服务器都在同一个子网内。分布式复制是将服务器放置 在不同的地理位置，通过i n t e r n e t 连接提供服务。这样对网络用户提出的服务要求，网 络可以通过其中任一个服务器来满足其服务。为研究此类网络通信，近年来，人们提出 了“选播f a n y c a s t ) ”的通信模型，即给定n 络中一源点和一组目标点，寻求从源点到任 一目标点的路由路径，选播通信已被规定为i p v 6 中的一种标准通信模型【3 。一个选播地 址可分配给一组接口( 这些接口通常属于不同的节点) ；发送到一个选播地址的数据包将 根据路由协议对距离的量度转发至拥有此地址的“最近的”接口。 选播与传统的单播和组播通信方式不同，它是实现从一台主机向一组目的主机中的 任何一台进行通信；选播的一组目的主机地址由一个选播地址表示，提供相同服务的不 同服务器拥有相同的选播地址。例如：多个w w w 镜像服务器可共享个选播地址， 为了得到所需信息，用户可通过选播服务机制获得这些服务器中“最近”的一个提供服 务。 东北大学硕士学位论文第一章绪论 1 3 研究选播的实际意义 虽然选播在许多应用领域起着非常重要的作用，但目前对它的研究才刚刚起步，在 许多方面还存在着制约这种服务实旆的问题。 ( 1 1 选播服务及相关技术日趋规范，越来越多的操作系统提供了对i p v 6 相关技术的 支持。随着网络技术和i n t e m e t 的迅速发展，i p v 4 暴露出越来越多的缺点和局限，严重 地制约了网络技术的进一步发展。因此，作为下一代因特网协议的i p v 6 吸引了许多网 络研究者的目光。近年来，许多基于i p v 6 的研究成果和产品相继问世，i p v 6 已得到越 来越多的网络操作系统和厂商的支持。路由器生产厂商，如c i s c o 等都在自己的产品 中增加了对i p v 6 的支持，i p v 6 的地址为1 2 8 位，可以与i p v 4 地址兼容，这些都为研究 和应用选播服务奠定了基础。 ( 2 ) 在许多应用领域，选播为最佳选择。i n t e m e t 的规模成指数级增长，分布式服务 面临服务器严重超载、带宽浪费和延迟增加的问题。服务器复制和缓存的技术虽然可以 有效地改善服务的性能，但是关键的问题是客户机如何找到性能最好的服务器。选播是 解决此类问题的最好办法；选播被广泛应用在最优服务器的选择和针对域名系统( o n s ) 及类似服务提出的主机自动配置上，从一组服务器中选择一台“最优”的服务器是选播 最基本的功能：在主机的自动配置上，比较典型的应用是域名服务器的解析，域名服务 器不管距离远近，只要能够完成名字的解析即可，选播通信还在提高网络资源的利用率， 提供多媒体通信的端到端q o s 保证等多方面具有独特作用。 ( 3 ) 路由问题是选播服务最根本的问题，选播路由协议的好坏直接决定选播服务的可 用性和效率。随着选播在许多领域的广泛应用，研究一种针对选播的高效的路由算法， 显得非常重要。 综上所述，随着用户对网络服务要求的提高和网络技术的发展，加强对选播的研究 具有非常重要的实际意义。 1 4 选播路由的研究状况 早期对予选播应用的设想，比较多的是面向服务的。对于服务定位上的应用，主要 是在用户需要某种服务时，由网络本身发现，指定提供这种服务的服务器，而不是让用 户在一张长长的服务器列表中手工地指定一个感觉比较好的服务器。设想有一组提供相 东北大学硕士学位论文第一章绪论 同服务的主机，当用户需要这种服务时，只需要为这种服务指定一个公认的选播地址， 客户机就会通过网络本身自动地找到最近的和最好的服务器进行通讯。又如主机自动配 置，最典型的例子就是域名系统( d n s ) ，客户机不再需要用户手工配置本地域名服务器， 而是在实现协议的软件中给出公认的域名服务全域选播地址，就可以实现无需人工干涉 的自动域名服务器查询和域名服务。 1 4 1 选播地址分配的设想 选播地址空间的分配是实现选播服务的一个最基本的问题，只有确定了在i p 网络上 如何分配选播地址，如何确定服务主枫属于哪一个选播组，其他所有基于选播的服务才 有可能实现。 当前在i p 地址空间中选播地址分配的解决方案可能有如下三种： 解决方案一：i p 地址空间中的每一个地址都可以作为选播地址被分配给特定的选播 组，而不需要特别的选播地址通告。 所谓的选播地址通告，就是当一个地址被分配给一个选播组后，需要向网络上所有 的路由器，甚至是所有的主机通告这个地址是一个选播地址，即它代表的只是一个虚拟 主机，实际上并不存在一个主机的i p 地址是这个选播地址。 这个方案的缺点是：一、要使面向连接的网络协议如t c p 识别出一个地址是主机地 址还是选搔地址比较困难：二、支持一个全域的选播地址就变得更加困难，选播服务提 出的初衷就完全得不到实现。 解决方案二：类似组播服务，设置专门用于选播服务的地址类。例如将现在保留未 用的地址( 如e 类地址) 全部或部分分离出来作为选播地址空间。 这个方案克服了方案一的两个缺点。但是，由于需要对于新的地址空间进行路由选 择，在很大程度上需要对现有路由协议进行修改，以便保证更多更好地追踪选播路由。 但这给实现提出了巨大的挑战。而且这个方案也告诉攻击者，这是一个选播地址空间。 对待这种攻击的办法就是让每个与保留地址相关的服务更健壮。 解决方案三：用当前已定义的地址空间中的一部分( 如2 5 6 个c 类地址) 作为选播地址 空间。显然，这是对前两个方案的一个折衷。虽然这个方案使得对选播服务的路由变得 容易了，坦是由于分配的地址空问小，碾制了选播服务的发展，这与选播服务可能的需 求是不适应的。 东北大学硕士学位论文 第一章绪论 1 4 2 选播实现的功能 在i p v 6 中，选播地址是国际互联网通信协议规范定义的一种新地址类型。它是一组 接口中距离源点最近的一个，节点间的传输路径通常因网络环境的变化而变化。选播能 实现以下功能： f 1 ) 最优的服务器选择 2 4 】：客户机能与拥有选播地址的最近的服务器连接； ( 2 ) 抽象服务：选播地址可以作为唯一的服务标识符，如果网络上的每项服务都使用 一个唯一的选播地址来标识，用户就可以通过该选播地址在任何地方获得最好的服务。 若再能得到d n s 对选播地址的支持，只需通过对服务名称的访问，即可获得服务； ( 3 ) 可靠性：若一个服务器失效，其它服务器仍然能提供服务。因为会将使用选播地 址的分组发送到另一个最近的服务器，使用选播地址的分布式服务器能提供可靠和冗余 的服务； ( 4 ) 有利于网络的负载平衡：将选播和单播、组播比较，不难发现单播和组播在路由 过程中多个点选择同一段路由的可能性很大，这样使得网络负载不平衡，容易造成拥塞， 而选播在很大程度减轻了这种不平衡【1 4 l 。 国内外对路由算法的研究工作多为单播或组播路由算法( 如文献 6 1 1 ) ，对选播路由 算法的研究还处于初始阶段。选播技术目前主要有两个发展方向：一个是在应用层利用 选播概念，通过管理手段实现选播服务，优化网络应用：另一个是在网络层利用选播路 由技术实现选播服务，提高网络通信的效率和鲁棒性【1 2 1 。 在选择“最优”服务器时，选择的标准依赖于网络的拓扑结构，例如路由器最小的 跳数、最小的花费，是基于网络层的选播：如果所选择的标准依赖于服务器或者应用的 尺度，如可以获得的容量、可以测量的响应时间以及激活连接的数量等就是基于应用层 的选播。两者关键的区别在于网络层选播仅仅依靠网络自身来选择合适的服务器；而应 用层选播则依赖于外部的实体来选择连接性能最好的服务器。仅仅依靠网络自身来选择 服务器的问题是客户机不一定能选择到性能最好的服务器，而应用层选播则能带来更多 的灵活性和可规划性。早期的选播研究大部分是面向应用层的，如提出将选播作为服务 定位和主机自动配置的解决方法等。网络层选播的实现很大程度上取决于对路由的选 择，目前对网络层选播的研究才刚刚起步，主要有对选播路由通讯中的路由表构造及路 由算法的研究。 由于基于多个不相关可加度量的q o s 路由问题是一个n p ( n o n d e t e m i n i s i t i c 东北大学硕士学位论文 第一章绪论 p o l y n o m i a lt i m e ) 完全问题 1 3 】，目前采用的方法多为启发式算法。现有的启发式算法存在 着算法复杂，难以求解等问题，还不能应用于实际。如何解决选播通讯方面的路由问题， 目前仍然没有一种非常有效的路由算法，许多技术仍处于实验室研究之中。 1 。5 选播通信的特征 ( 1 ) 选播组。在选播通信中，提供相同服务的一组服务器形成选播组，每个选播组有 多个成员； ( 2 ) 通信模式。从通信模式上看，选播与单播和组播是有区别的。单播是单点对单点 通信，组播是单点对多点通信，而选播则是单点对特定组中的单点通信。组播要求数据 到达组中的每一个成员，而选播没有此限制，只要求到达至少一个成员，而且通常情况 下，最好只到达一个成员； ( 3 ) 最优路由。网络为选播分组提供最优路由，包含两层意思：第一，选播的实现是 由网络而不是端系统来完成的：第二，网络要为选播分组找到一个“最优的”服务器来 处理该分组，“最优的”服务器的定义与具体的应用和目标相关，比如距离最近的服务 器或者负载最小的服务器。 1 6 本文研究的主要内容 本文主要研究了基于q o s 约束的选播路由算法，提出了两个选播算法：一是基于时 延、带宽和费用约束的选播路由算法：二是基于遗传算法的选播路由算法，并对这两种 算法进行了仿真实验。具体内容主要安排如下： 第一章作为整个论文的绪论，介绍了网络的通讯方式、选播技术产生的背景和研究 现状以及选播通信的的特征： 第二章对网络服务质量、q o s 路由算法以及路由策略作了简单的介绍： 第三章提出了基于时延、带宽和费用约束的选播路由算法，利用瓶颈带宽与时延和 费用乘积的比值最大者为标准进行路由选择，并进行了仿真实验： 第四章提出了基于遗传算法的选播路由算法，并进行了仿真实验： 第五章是结束语。 8 东北大学硕士学位论文第二章q o s 路由的理论基础 第二章0 0 s 路由的理论基础 2 10 0 s 的定义 随着网络传输速度的不断提高，人们对基于分组交换通信方式的分布式多媒体应 用的需求越来越大。口电话在电信业务中所占的比例越来越大就说明了人们对这种业务 的需求在高速增长。但目前的i n t e m e t 技术采用灵活的无连接技术实现网络互连，只能 提供“尽力而为”( b e s t e f f o r t ) 的服务质量保证，在保障分布式多媒体业务的服务质量方 面存在严重不足。 一般说来，用户对不同的分布式多媒体应用有着不同的服务质量要求。q o s 需求可 以通过一个约束集来描述，包括链路约束、路径约束和树约束【1 5 】。链路约束定义了从源 节点到目的节点的每一条链路的约束，如带宽约束；路径约束定义了从源节点到目的节 点的一条路径上端到端故q o s 需求，如时延；树约束定义了对组播中整个组播树的约束， 例如对组播树时延的约束是对树中从源节点到所有目的节点的路径中最大时延的约束。 丢失率、带宽、端到端时延、时延抖动等对于应用业务是至关重要的，文件传输业务要 求分组的丢失率尽可能低，而传输时延不是关键；实时多媒体业务则注重时延和时延抖 动，这就要求网络能区别对待各种业务，并对其提供不同的服务质量要求。 q o s 路由已经被认为是i n t e r n e t 中支持服务质量的关键。o o s 路由的基本思路是找 到一条( 棵) 可行路径( 树) ，该路径( 树) 在有足够的剩余资源能满足业务分组的q o s 要求的 同时，能够提高网络资源利用率、改善整个网络的性能。o o s 路由正受到越来越多的重 视。 q o s 即服务质量( q u a l i t y o fs e r v i c e ) 是指网络在传输数据流时必须满足的一系列服 务需求1 1 8 1 。q o s 包括用户要求和网络服务提供者的行为两个方面。用户要求指用户在 i n t e r n e t 网络上进行多媒体通信时所要求的服务类型以及相应的传输性能和质量。网络 服务提供者的行为指服务商所能提供的服务类型和质量等。 2 20 0 s 度量 q o s 主要包括以下一些参数 东北大学项士学位论文第二章q o s 路由的理论基础 ( 1 ) 带宽( b a n d w i d t h ) ：单位时间内传送的i p 包数量。多媒体业务的数据传输量往往 较大，因此需要网络为其分配最小带宽，如标准电话为6 4 k b i t s ，压缩过的h d t v 为 2 5 3 4 m b i t s ，视频会议为0 1 2 m b i t s 。 尽管带宽表示链路可达到的最大传输能力，但并不意味着通过高带宽连接的路由一 定比通过较慢连接的路由要好。例如业务都去使用高带宽的链路，使之比较忙碌，则实 际传送包所用的时间可能比较慢的链路要长。 ( 2 ) 时延( d e l a y ) ：指i p 包从发送到接收之间的时间间隔。它包括终端设备的编码 解码时间、口包在传播介质的传播时间、i p 包在交换机或路由器中被处理的时间以及 i p 包在交换机或路由器的等待队列中的排队时间。 实时业务往往是对时延敏感的，比如在虚拟现实应用中，由于语音输入的响应时间 被限制在l o o m s 之内，所以端到端的时延在4 0 m s 左右，而有些非实时业务，如e m a i l 等，却对时延不敏感，因此网络不需要对这类业务提供时延保证。 ( 3 ) 时延抖动( d e l a y - j i t t e r ) ：当坤包到达交换设备时，如果等待队列中没有别的口包， 则它将以固定时延被转发出去。但是，如果等待队列中还有别的包，则它可能就需要等 待，这时口包被交换的时延就等于固定时延加上在队列中等待的时间，以上两种情况 下时延的变化程度就是时延抖动。 时延抖动会对实时通信中连续媒体的同步造成不利影响。发送连续信息流的回放应 用程序( 如视频点播) 往往通过添加一个称为回放缓冲区的接收缓冲区来消除时延抖动的 影响。但是，如果抖动太大，则会造成以下情况：当数据到达太慢时，回放缓冲区变空， 视频播发程序无数据可用，从而画面中断；当数据到达太快，数据又会从回放缓冲区溢 出。因此，实时多媒体对时延抖动有一定的要求，电话语音和视频会议要求时延抖动不 超过4 0 0 m s ，广播电视不超过l o o m s ，h d t v 不超过5 0 m s 。 ( 4 ) 包丢失率( p a c k e tl o s sr a t e ) ：是指特定的时间段丢失的包占传输包总数的比例。丢 包主要是由于网络拥塞引起的。某些应用程序在包丢失后无法正常工作，因此要求网络 提供传输保障。丽某些多媒体业务如i p 电话，个别包的丢失虽然会影响声音的质量， 但用户往往可以容忍这种质量的暂时下降。因此，只要包丢失率在一定的范围内，就不 会影响业务的正常进行。 ( 5 ) 路径长度( p a t hl e n g t h ) ：是最常用的路由度量标准。通常，路由协议允许网络管 理员给网络连接赋以任意的耗散值，则路径长度为传输路径上各连接耗散值之和。有的 路由协议定义路径长度为节点计数，即包从源到达目的地途中经过的网络设备( 比如路 1 0 东北大学硕士学位论文第二章q o s 路由的理论基础 由器1 的数目。 q o s 度量一般可分为三种类型【17 】： ( 1 ) 可加性q o s 。总q o s 等于构成这条路径的所有链路q o s 值之和( 如跳数、时延、 费用等1 ： ( 2 ) 可乘性o o s ，总q o s 等于构成这条路径的所有链路q o s 值之积( 如误差率、丢包 率等) ： ( 3 ) 最大最小性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 3q o s 的三个推动力量 网络中，服务质量( o o s ) 的研究有三个主要的推动力量【1 6 1 。一是对q o s 有严格要求 的业务的出现，如交互式实时媒体业务、i p 电话等；二是通过q o s 研究，有助于提高 网络服务效率，降低网络成本；三是运营商可以通过q o s 机制，按照不同用户对服务质 量的不同要求，提供多种有区别的服务，提高用户的满意度，同时提高网络运营商的收 益。用户对有质量保证的分布式多媒体服务的需求以及这种需求的快速增长极大地推动 了q o s 和相关技术的发展。 2 4q o s 实现的步骤 在t n t e r n e t 中，实现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 会话阶段。具体 东北大学硕士学位论文第二章q o s 路由的理论基础 的q o s 参数用来测算资源和q o s 计算，最终导致会话成功或拒绝。当会话阶段成功结 束后，第四步骤( q o s 保证) 就在数据传输阶段，根据预留的资源调度资源以处理用户数 据，并维持此连接。 如果用面向连接的方法来保障在数据传输阶段的q o s ，q o s 会话阶段就是典型的连 接建立过程。 2 50 0 s 路由和尽力而为路由的区别 在传统的数据网络中，路由主要关心的是接通性。目前的路由协议有基于链路状态 的o s p f 和基于距离矢量的r i p 等。通常通过一个简单的度量标准如路径跳数或时延， 采用最短路径算法来计算选择路径。 q o s 路由和传统的尽力而为( b e s t e f f o r t ) n 油不同，q o s 路由支持不同业务，采用更 全面的路由度量标准，如时延、可用带宽、跳数等，同时q o s 路由通常是面向连接、有 资源预留功能，并且能够提供有质量保证的服务：而尽力而为路由可能是面向连接的， 也可能是无连接的，根据当前可获得的资源的不同，服务质量方面也有所不同。 q o s 路由过程涉及到两方面的问题：一是依据哪些度量参数作为寻路标准，我们称 之为度量参数选择问题，另一个是在寻路标准设定后，如何找到满足业务需求的路径， 并保证数据包经由选定路径传输至目的节点，我们称此为寻路问题。 2 60 0 s 路由算法介绍 2 。6 1 服务质量路由 服务质量路由( o o s r ) 是一种基于数据流q o s 请求和网络可用资源进行路由的机制， 或者，q o s r 是一种动态路由协议，并且在其路径选择标准里可能包含可用带宽、链路 和端到端路径利用率、资源消费量、时延、跳数以及时延抖动等q o s 参数1 1 。 服务质量路由( q o s 础是未来互联网络的一个核心功能，其主要目标包括两个【1 叫： ( 1 ) 为每个接受的q o s 业务流提供服务质量保证； f 2 ) 达成网络全局资源的最佳利用。 前者要求在多约束条件下计算可行路径，后者则要求在多条可行路径中进一步优 化。优化的方式通常是首先设计费用函数，然后求解函数值最优的可行路径。而多约束 1 2 东北大学硕士学位论文 第二章q o s 路由的理论基础 下求解( 优化的) 可行路径属于n p 完全问题，不能在多项式时间内精确求解，为此研究 者们设计了很多启发式算法或近似算法。 这些算法还具有以下三个方面的不足： ( 1 ) 计算复杂度过高而不能在网络中实际应用； ( 2 ) 算法性能过低而找不到实际存在的可行路径： ( 3 ) 大部分算法只是针对q o s r 问题中某些特殊情况的。 2 6 2 路由算法的设计目标 n ) 最优化。指路由算法选择最佳路径位置的能力。不同的优化目标及其权值大小 决定了选择不同的最佳路径，例如路由算法可能考虑节点数和预留带宽，路由协议必须 严格地定义它们待优化的度量标准。 f 2 ) 简单性。路由算法应被设计成尽可能地简单，即必须以最少的开销和使用费用获 得高效的功能。当路由算法由软件实现、并在物理资源受限制的计算机上运行时，效率 显得特别重要。 ( 3 ) 鲁棒性。路由算法必须是健壮的，在异常的或者无法