（应用数学专业论文）时延敏感的多播路由算法研究.pdf

摘要 在计算机网络中，提供多种实时业务的多媒体通信是当前的研究热点。多播 是一个主机向多个主机发送信息( 但不是所有主机) 的通信方式，涉及多播的应 用很多，如多媒体会议、远程教学、数据分发等。 本文主要研究了通信网中的多播路由算法。首先介绍了常用的多播路由算法 和多播路由问题的理论基础。接着提出了一种实时的代价最小动态多播路由算法， 利用选择的变换函数使二维问题变为一维问题，这样就避免了传统的将代价和时 延分别考虑，大量回溯的弊端。然后给出了一种基于遗传算法的实时多播路由选 择方法，并用改进的遗传算法进行了求解，该算法采用包含源节点和目的节点的 树作为交叉和变异的空间的方法，通过加入混合选择、小范围竞争择优的交叉变 异操作。提高了全局搜索能力和收敛速度。此外，本论文还研究了点到点的多路 路由选择问题，并给出了一种求解q o s 路由问题的数学模型及算法，用半定规划 的方法进行了求解。最后，研究了w d m 光传送网中的多播路由问题，并总结了 现有的几种多播光网络中的路由和波长分配算法。 关键词：时延多播路由遗传算法s t e i n c r 树q o s 路由 a b s t r a c t i nc o m p u t e rn e t w o r k s ，p r o v i d i n gm u l t i c a s tf o rm u l t i m e d i ar e a l - t i m es e r v i c ei so n e o ft h eh o i s ti s s u e si nc u r r e n tr e s e a r c hf i e l d m u l t i e a s tr o u t i n gi sac o m m u n i c a t i o n m e a n s ，w h i c hi sf r o mah o s tc o m p u t e rt om a n yo t h e rh o s to n e s ，b u tn o tt oa 1 1 t h e r ea r e l o t so fa p p l i c a t i o n so fm u l t i c a s t ，s u c ha sm u l t i m e d i am e e t i n g ，l o n g - d i s t a n c et e a c h i n g , d a t ad i s t r i b u t i o ns oo na n ds of o r t h i nt h i s p a p e r , t h ee x i s t i n gh e u r i s t i ca l g o r i t h m s f o rs t e i n e rt r e ep j r o b l e ma r e s u m m a r i z e df i r s t l y s e c o n d l y ar e a l t i m el e a s t c o s td y n a m i cm u l t i c a s ta l g o r i t h mi s p r e s e n t e d ，w h i c hm a k e st h ep r o b l e mm u c he a s i e rb yu s i n gt h et r a n s p o s i t i o n a lf u n c t i o n i to v e r c o m e st h es h o r t c o m i n g so ft h et r a d i t i o n a la l g o r i t h m s ，w h i c hd e a lw i t ht h ec o s t a n dd e l a ys e p a r a t e l ya n dn e e dal o to fr e t r o s p e c ta n dm o r em u l t i m e d i as e r v i c e sn e e dt h e n e t w o r kg u a r a n t e et h er e a l t i m er e q u i r e m e n t s ，s ot h en e t w o r kr e s o u r c e sc a nb eu f i l m e d e f f i c i e n t l y t h e n ，a ni m p r o v e dg e n e t i ca l g o r i t h mi sp r o p o s e dt os o l v et h i sp r o b l e m t h i s a l g o r i t h mm a k e st r e e sw i t ht h es o u r c ea n da l ld e s t i n a t i o n sa r et h es p a c eo fo p e r a t i o na n d f i l t e ro p e r a t i o n w i t hh y b r i ds e l e c t i o no p e r a t o r , c o m p e t i t i o na m o n gb r o t h e r s ，g r e e d y o p e r a t i o n ，f i l t e ro p e r a t i o n i tc a ni m p r o v eg l o b a lc o n v e r g e n c ep r o p e r t ya n dc o n v e r g e n c e s p e e d f u r t h e r m o r e ，a na p p r o a c h o fo n ed e s t i n a t i o nt oa n o t h e ri ss t u d i e da n da m a t h e m a t i c a lm o d e la n dc o r r e s p o n d i n ga l g o r i t h mt os o l v et h ep r o b l e mo fq o sr o u t i n g i sg i v e n ，i nw h i c hs e m i d e f i n i t ep r o g r a m m i n gi su s e d t h eb a s i cp r o b l e mo fq o sr o u t i n g i sa no p t i m a lp r o b l e ms a t i s f y i n gm u l t i c o n s t r a i n e dc o n d i t i o n sf r o mas o u r c en o d et oo n e d e s t i n a t i o n a tl a s t ，t h em u l t i c a s tr o u t i n gi nw d mo p t i c a ln e t w o r k si sd i s c u s s e da n d r a w ( r o u t i n ga n da s s i g n m e n to fw a v e l e n g t h ) p r o b l e m sa r es u m m a r i z e d k e yw o r d s ：t i m e d e l a y m u l t i c a s tr o u t i n gg e n e t i ca l g o r i t h m s t e i n e rt r e e q o sr o u t i n g 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在 仑文巾做了l ：! | 确的说明井表示了谢意， 申请学位论文与资料糟确不实之处，本人承担一切棚关责任。 本人签名：墨垒塾 日期：丝! 摹! 塑净 关于论文使用授权的说明 本人完全了解晒炎f u 二j i 科技火学有关保留刺使川学位论文的规定，即：i i j f 究生 在校攻读学位j u j i i , j 论文：l 作的知识产权单位属蹲安电子科技火学。本人保证毕业 离校后，发表沧文或馊用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允1 1 ：采_ i = j 影印、缩印或其他复制手段傈存论文。( 保密的论文在 解密后遵守此规定) 本人签名 导师签名： 塑叠 缉泌一 i q j t j j ：堡i 纶! 塑 1 瓤2 空：竺：望 第一章绪论 第一章绪论 在本章中，介绍了路由算法的特点、设计路由算法的规则、多播路 由技术、多播路由的分类以及多播路由对网络性能的要求，最后给出了 本文的主要内容 1 1 路由算法概述 路由算法的主要功能是指引分组通过通信予网到达正确的目的节点。它包括 两个方面的功能；第一是为不同的源节点和目的节点对选择一条传输路径；二是 在路由选好以后，将用户的消息正确的送到目的节点。 路由算法是网络层具有的协议，路由算法即要试图使网络的通过量最大，又要 试图使网络的平均分组时延最小。路由算法通常很复杂，这主要表现在： 第一：路由算法要求子网中所有节点相互协调，而不像链路层和高层那样仅涉 及一对对等模块之间的协调。 第二：路由算法必须处理链路和节点的故障，要求对业务进行重新定向和对系 统维持的数据库进行更新。 第三；必须达到高的性能当网络部分区域拥塞时，路由算法必须能够修正路由。 对于一个理想的路由算法应具有如下的特点： 算法必须是正确的和完整的，即每一个节点( 交换机和路由器) 中的路由 表，必须都给出到所有可能的目的节点的下一站应怎样走，并且所给出的 走法应是正确的。这里正确的含义是：沿着各节点( 交换机或路由器) 中 路由表所指引的路由，分组一定能够到达目的节点。并且分组到达目的节 点后不会在向其它节点转发该分组。 算法在计算上应简单。由于每个节点上都要进行路由选择的计算，因此必 须要增加分组的时延。此外路由算法的计算不应使网络的通信量增加太多 的额外开销。若为计算合适的路由必须使用网络的其它节点发来的大量状 态信息时，额外开销就会增大。 算法应能适应通信量和网络拓扑的变换。这就是说要有自适应性。当网络 中的通信量发生变化时，算法能自适应的改变路由，以均衡各链路饷负载。 当某个或某些节点链路发生故障不能工作时，算法也能及时的改变路由。 有时称这种自适应性为“稳健性”或“鲁棒性”。 2 时延敏感的多播路由算法研究 算法应是公平的。算法应对所有用户( 除对少数高级的用户外) 都是平等 的。例如，若使某一对用户的端到端时延为最小，但却不考虑其它的用户， 这就明显的不符合公平性的要求。 算法应是最佳的。这里的“最佳”通常是指以最低的费用( 成本) 来实现 路由算法。这里特别需要注意的是在研究路由算法时，“费用”并不一 定就是“钱”。每条链路的费用通常由链路容量、节点缓冲区被占用的程 度、链路的差错率情况等因素综合决定。可以摄据用户的具体情况来设置 每一条链路的“费用”。 一个实际的路由算法，应尽可能的接近于理想的算法。在不同的应用条件下， 对以上提出的六个方面也可有不同的侧重。 路由算法在何时执行。取决于网络中采用的路由方式。如果采用数据报方式， 则对每一个分组都要进行一次选路。因此相同源和目的节点的分组可能会经过不 同的路径。如果采用虚电路方式，则在虚电路建立时要进行路由选择。 1 2 多播路由技术 随着人们对网络的需求由简单的数据传输向综合的多媒体业务发展，多播技术 作为一种可大大节省网络资源的技术在多媒体业务中有着广泛的应用从而也相 应的对多播技术提出了许多不同的需求。许多新兴的多媒体业务，不仅是设计多 用户的，而且是对对延敏感的。为了支持此类应用，需要寻求满足严格时延约束 的有效多播路由算法。网络的作用从简单的信息传送发展到远程教学、视频会议、 数据分发和网络游戏等。用户的数据要从一个终端发送到另一个终端，首先要确 定传输路由，不同的通信方式，其确定路由的方式也不同。如今网络的通信方式 主要有以下几种：蕈播、多播、汇播、群播、广播等。 现有的i n t e m e t 采用的是点到点的传送方式即单播方式，在这种方式下，发送 方和每一接收方需要一单独的数据通道，从台服务器送出的每个数据包只能传 送给一个客户机，如果另外的用户希望顺路获得这个数据包的拷贝是不可能的、 这种方式会极大加重服务器的负担及浪费大量带宽，解决的办法是构建一种具有 多播能力的网络，允许路由器一次将数据包复制到多个通道上，多播发送方只要 发送一个信息包而不是很多个，所有目的地将同时收到同一信息包，可以更及时、 更同步地把信息发送到任意不知名的目的地，减少网络上传输的信息包的总量， 网络成本变得相当低廉，达到从来有过的传送能力，实现多播技术要解决的关键 问题是多播路由问题。 对于单播而言，其实现一般采用d i j k s t r a 提出的最短路算法( s h o r t e s tp a t h 第一章绪论 a l g o r i t h m ) 1 , 2 1 或1 3 c l l m a n f o r d 算洲2 ，3 l 来建立点到点的路由当只有两个终端参与 同一进程时，一般采用单播。广播是网络中常用的方式，其涉及一节点向网络中 所有节点发送信息，广播通信方式在局域网中应用很广。而多播是一源节点向多 个目的节点发送信息( 但不是所有节点) 的通信方式，涉及多播技术的应用很多， 如多媒体会议、远程教育、数据分发等。多媒体会议是多播应用的一个典型例子， 数据分发是多播应用的另一个领域，这项技术允许公司每天夜里向他们韵远程商 店发布新的信息，比如价格和产品信息，以便在下个营业日有更新的信息。多播 应用的普及也导致了多播主干网( m b o n e ) 1 4 】的快速发展。汇播与多播有相同之处， 多播是一点到多点的通信方式，丽汇播是多点到多点的通信方式，例如远程数据 采集涉及汇播方式。至于群播的典型应用是网络即时游戏，在多方游戏中需要将 各自的状态互相同步发送。在多播、汇播和群播中，多播是目前研究的最多，也 是研究的最广的网络研究方式。 多播是一种允许向一组目的主机同时传送信息的通信方式，这种多点通信方 式正成为诸如多媒体通信和分布式计算等应用的基本需求。为支持大规模的多播 通信，在满足通信服务的前提下应尽可能减少网络资源的消耗，当前网络支持多 播通信的有效方法是构建连接源节点与所有群组节点的分发树，基于树的方法使 得数据在传往群组节点的过程中能共享某些链路，最低限度地降低重复数据的传 输，多播路由算法就是研究这种路由树的建立。 一般要求多播服务的业务对带宽和实时性要求较高涉及用户较多，占用的资 源也多，因此有必要优化多播路由。多播路由算法就是要寻求最优多播树，理想 有效的路由算法将设计一棵仅覆盖多播组成员的树，并体现如下特征：树随着组 成员变化动态更新；最小化节点需要保存的状态信息量；避免链路和节点的流量 集中；根据费用函数优化路由。 多播路由算法使用不同的优化目标来确定好的路由树。一个优化的目标是使 多播树保证源节点到各群组节点的时延尽可能小，这对多媒体应用如实时会议是 很关键的，另一优化目标从服务提供者或网络管理角度上则考虑尽可能降低网络 资源的消耗，如果使用代价来表示网络资源的耗费，这就变成寻找总体代价最小 的多播树问题，链路代价可用来表示信道带宽或缓冲空间，也可表示链路的拥挤 情况或差错率，还可表示网段数、链路费用等参数。实现多播通信可以通过三种 方式。第一种方式是让端节点简单的发送一个单独的分组到每一个目的端j 这种 方法不仅浪费带宽，而且还要求源端拥有全部目的端的完整清单。二是每个分组 含有一张目的节点清单，当分组到达路由器时，路由器检查所有目的节点，以确 定将要甩到的输出线路集合( 如果某线路是到达至少一个目的节点的最好路由， 则需要该线路) 。路由器为所使用的每一条输出线路复制一个新的分组，每个分组 中仅含有用此线路的那些目的节点。实际上，目的节点集合是划分在各条输出线 4 时延敏感的多播路由算法研究 路上的，经过足够多数量的站点后，每个分组将仅带有一个目的节点。这种路由 方式就像各自分组寻址一样，只有若干分组必须经过同一路由时，其中一个分组 负担全部费用，而其它的分组则不必承担费用【5 1 。由于过去网络应用很少涉及到多 个用户而且多数应用带宽要求较小因此上述简单的点到点的通信方式足以使 网络满足多点业务的带宽要求。然而多媒体实时应用业务的出现，使得多播组的 规模、业务的特征和要求发生了很大的变化，为了满足这种需求，有必要寻求网 络层对多播通信的支持，使多播技术满足多媒体实时应用的要求。为此有了第三 种实现多播的方式，即建立多播树( m u l t i c a s t i n gt r e e ) 。一棵多播树有两种类型 6 1 ， 一种是有源树，另一种是共享树。有源树是多播树最简单的一种形式，有源树的 根是多播信息流的来源，有源树的分枝形成了通过网络到达接受站点的分布树。 另一种形式的多播树是共享树和中心树( c b t ：c o r e b a s e dt r e e ) f 5 l f 6 1 这里，每个组 只计算一棵生成树，其树根( 核心) 靠近多播组的中间部位，要发一个多播消息， 主机先将它发往核心，再由核心沿着生成树发送消息，虽然这棵树并不是对于任 何源节点都是最优的，但它将每组m 棵树的存储开销降低到了一棵树，节省了大 量空间。 多播路由算法有q o s 。加】多播路由算法、静态和动态的多播路由算法、分层多 播路由算法【1 1 1 厶1 扪、s t e i n e r 树算法【1 ”3 】和c b t 算法【3 2 。7 l ( 确定中心有许多种方法) 、 集中式和分布式多播路由算法【3 m 。 1 3 多播路由问题的分类 由于许多原因，在多播路由中提供o o s 是很困难的，首先，诸如电视会议、 视频点播、网络电话和基于w e b 的应用，这些分布式的服务对延迟、延迟抖动、 带宽以及包丢失率都有不同的要求，大量约束使多播路由很难实现。其次，当路 中算法被多播路由协议采纳后，又存在很多实际问题( 例如：状态集合的更新， 动态拓扑结构的处理和成员变化，树的维护和可扩展性) 。q o s 的要求使协议设计 过程更加复杂化。此外，我们必须考虑如何用最小的代价收集维护与q o s 相关 的状态，如何在集合的不精确状态信息下构建一棵满足o o s 的路由树、如何维护 路由域之间的0 0 s 等。 给定一个多播组和一组可能的最优目标函数，多播路由就是在网络拓扑结 构和网络函数的基础上，构建一棵使目标函数达到最优的多播树的过程。在基于 约束的多播路由中，一组约束通常用点到点延迟、相互间延迟抖动限制、最小带 宽、包丢失率或者它们的组合形式出现、构建的多播树不仅要满足从源节点到接 收节点的可达性，而且要满足q o s 要求以满足约束条件。 第一章绪论 5 1 3 1 目标函数和约束 最优化目标通常定义为使多播树代价最小的形式，这里代价可能是使用的总 带宽或者网络应用中定义的函数，施加的约束可分为以下两类； 链路约束是进行链路选择时对链路使用的限制。例如，一条链路上带宽 和可用缓存大小。 树约束有以下两种 第一、多播树上从源端到接收端的每条路径上的综合性能的约束，如从源端 至所有接收端的点到点延迟。 第二、对从同一源端到任意两个接收端的路径上的性能差异的约束、如，从 源端到任意两个不同接收端的延迟抖动。 1 3 2 多播路由问题的分类 根据树约束链路约束和目标函数，多播路由问题可分为以下几类： 1 ) 单链路约束问题在构建可行的多播树时加以单个链路约束( 如带宽约束 路由问题) 。 2 ) 多链路约束问题在构建可行的多播树时加以多个链路约束( 如带宽及缓 存约束链路问题) 。 3 ) 单树约束问题在构建可行的多播树时加以单个树约束( 如延迟约束路由 问题) 。 4 ) 多树约束问题在构建可行的多播树时加以多个树约束( 如延迟及延迟抖 动路由闽题) 。 5 ) 链路及树约束问题在构建可行的多播树时加以一个链路约束及一个树约 束( 如延迟及带宽约束路由问题) 。 6 ) 链路最优化问题在构建一棵最优的多播树时使用链路最优化函数( 如要 求多播树上链路带宽最大) 。 7 ) 树最优化问题在构建一棵最优的多播树时使用树最优化函数( 如要求多 播树的总代价最小) ，这类问题也叫做s t e i n e r 树问题。 8 ) 链路约束链路最优化问题在构建一棵符合约束条件的最优化多播树时， 加以一个链路约束并使用链路最优化函数( 如带宽约束缓存最优化问题) 。 9 ) 链路约束树最优化问题在构建一棵符合约束条件的最优化多播树时，加 以一个链路约束并使用树最优化函数( 如带宽约束s t e i n e r 树问题) 。 1 0 ) 树约束链路最优化问题在构建一棵符合约束条件的最优化多播树时， 加以一个树约束并使用链路最优化函数( 如延迟约束带宽最优化问题) 。 6 时延敏感的多播路由算法研究 1 1 ) 树约束树最优化问题在构建一棵符合约束条件的最优化多播树时，加 以一个树约束并使用树最优化函数( 如延迟约束s t e i n e r 树问题) 。 1 2 ) 链路约束及树约束树最优化问题在构建一棵符合约束条件的最优化多 播树时，加以一个链路约束和一个树约束并使用树最优化函数( 如带宽及延迟约 束s t e i n e r 树问题) 。 第1 ) ，2 ) 类问题是容易处理的，因为我们可以通过从网络拓扑图中删去不合 要求的来满足约束条件。w 抽一3 9 l 己证明寻找一条路径使之满足两个或多个相 互独立的相加和或相乘的约束条件以及它们的任意组合是n p 完全的、因此问 题3 ) 、5 ) 、1 ) 在多项式时间内是可解的，而问题4 ) 则是n p 完全的、问题3 ) 的一个多项式复杂度的算法可见文献“0 3 、如果从网络拓扑结构中移去不满足约束 条件的链路，则问题8 ) 可转为问题3 ) ，因此问题3 ) 在多项式时间内也是可解的。 最后，问题7 ) ( s t e i n e r 树问题) 和问题9 ) 、1 1 ) 、1 2 ) ( 约束s t e i n e r 树问题) 己被证明是n p 完全的【4 l 】。 1 4 时延敏感的多播路由问题对网络性能的要求 基于i n t e m e t 的高带宽多媒体应用，譬如两络视频会议、网络音频视频广播、 a o d v o d 、股市行情发布、多媒体远程教育、c s c w 协同计算、远程会诊，带 来了带宽的急剧消耗和网络拥挤问题。为了缓解网络瓶颈，人们提出各种方案， 主要包括以下四种：增加互连带宽；服务器的分散与集群，以改变网络流量 结构，减轻主干网的瓶颈；应用q o s 机制，把带宽分配给一部分应用：采用 i pm u i t e a s t 技术。比较而言，i p 多播技术有其独特的优越性在多播网络中， 即使用户数里成倍增长，主干带宽不需要随之增加。这个优点使它成为当前的一 个研究热点。 多媒体数据主要有如下特点：一是数据量大，二是对数据传输的要求较高， 主要是要求满足数据流量指标，通常在信源编码中采用速率控制和数据缓冲来控 制数据的流量；三是数据处理的时间要求严格，编码、解码必须按照一定的时间 次序进行。因此，多媒体信息传输对网络要求的性能指标主要集中在以下几个方 面： 1 ) 吞吐量：即网络传送二进制信息的速率，有的多媒体应用所产生的数据速 率是恒定的，而有的应用是变比特率的，支持不同应用的网络应该满足他们在吞 吐量的不同要求。如m p e e 2 的数据率约在2 0 4 0 m b s ，m p e e 一1 的数据率 约为1 _ 4 m b s 。 2 ) 传输延时：对于交互视频应用来说，i u 标准建议最大的端到端总延迟不要 第一苹绪论 7 超过1 5 0 m s 其中信源的压缩打包需要3 0 m s 左右，信宿解包解码输出也要3 0 m s 左右，再加上捧l 炎缓冲也要3 0 m s 左右，因此实际网络传输延迟只能在6 0 m s 左右。 如果终端是存储设备或记录设备，对传输延时就没有严格要求了。 3 ) 延时抖动：网络的延时抖动对文字、日形、图像等静态媒体的传输不产生 什么影响，但在多媒体应用中，将破坏多媒体的同步，从而影响音频和视频信号 的播放质量例如，图像和声音不同步，或者图像( 声音) 有停顿或跳跃。 4 ) 错误率：主要指误码和数据包丢失，即使相对轻微的误码和包( 信元) 的 丢失对解码图像数据也会产生严重的影响。由于压缩算法消除了活动图像序列的 大部分内在相关性，因此误码可能会影响到解码序列中大部分空间质量的下降。 若采用运动补偿帧间预测这种误差不仅在空间上传播，而且也在时间上传播。 因此，图像通信中只能容许很有限的误码或信元丢失，以使质量的下降为不可见。 实时多媒体数据传输对延时抖动和错误率是相当敏感的。需要收发双方协调工 作。一方面，发送方不能发送过快而造成接收者的“淹没”。或者因网络阻塞而丢 失数据另一方面接收者不能因来不及处理而造成数据溢出，也不能因等待数据的 到来而暂停播放而且实时应用的实时性比可靠性要求高，通常情况下使用的应 答和重发机制，会因为重发数据的迟到而变得没有意义。另外为了给接收方足够 的时间进行处理，发送方应该要对数据的传输给一定的延时，这种延时不仅不会 降低系统的实时性，还会有助于提高媒体播放的连续性，使视频更平滑。 1 5 本文的主要研究内容 本文首先研究了时延敏感的多播路由算法，即如何建立满足时延约束的代价 最小多播树；其次对o o s 约束的路由问题进行了研究，给出了点到点的多路路由 问题的一般数学模型，并用数学规划的方法进行了求解，最后对w d m 光网络技 术作了简要的介绍。本文的研究包括以下几个方面： 介绍了时延敏感的多播路由问题，并给出了一般的数学模型，接着提出了 一种时延受限代价最小的动态多播路由算法：然后用遗传算法对一种多播 路由问题进行了求解。 对0 0 s 约束的路由问题进行了研究，提出了解决多播路由问题的一般数 学模型。然后对点到点的路由选择问题建立了一般的数学模型，并用规划 的方法进行了求解，提出了用半定规划的方法求解该问题。该算法有一定 的理论意义，仿真表明和用整数规划求解的问题相差不大。最后对光网络 中的一些问题进行了简要的介绍。 本文的内容安排如下： 8 时延敏感的多播路由算法研究 第二章主要介绍了单播和多播的基础算法即一些常用的路由算法，以及 s t c i n c r 树理论知识和路由仿真平台的建立。 第三章给出了一种时延受限代价最小的多播路由算法，接着给出了一种用遗 传算法求解多播路由问题的算法。 第四章对q o s 约束的多播路由问题给出了一般的数学模型，同时对点到点的 多播路由问题也给出了一般的数学模型，并用半定规划的方法对其进行了求解。 同时对w d m 光网络中的有关问题作了简要的介绍。 最后对全文进行了总结，并提出了几个研究方向。 墨三雯墨塑堕塑塑望塑墨堡薹型 第二章多播路由问题的理论基础 本章首先对常用的路由算法进行了介绍，然后介绍了有关s t e i n e r 树问 题的理论其中包括求解s t e i n e r 树问题的一些常用算法最后，我们介绍 了几种仿真网络模型，并提出了建立路由仿真平台的必要性。 2 。1 常用路由算法介绍 由于单播路由算法或者多播路由算法的基础是一些常用的路由算法，因此有必 要对常用的路由算法进行介绍。 常用的路由算法有多种分类方式，一种是按集中式和分布式来分类。集中式路 由算法是指网络的路由是由路由控制中心计算的，该中心周期性收集各链路的状 态，经过计算后周期性的向各网络节点提供路由表。分布式路由是指网络中所有 节点通过相互交换路由信息，独立的计算到达各节点的路由。 另一种分类方式是：静态路由和动态路由。动态路由是指随着网络拥塞情况和 拓扑的动态变化情况，网络中频繁执行网络路由算法，如每小时1 0 次甚至更多。 然而如果网络的路由通常是不变的，只有在节点或链路故障的情况下才改变。这 种方式称为静态路由 按照路由应用场合来分，可分为广域网中( 子网中) 的路由和互联网中的路由。 广域网中的路由，主要解决一个子网中的路由，而互联网中的路由要解决不同子 网中的路由。 2 1 1 广域网中的路由 广域网中的路由主要解决子网内分组传输问题，它包括三种路由算法：广播、 最短路由和最佳路由 广播常采用的路由算法常有多种方法：如泛洪( f l o o d i n g ) 路由、采用生 成树( s p a n n i n gt r e e ) 的广播方式等。当然也可以逐一地把要广播的分组 按照普通的路由算法发给每一个目的节点，这种方法将会浪费大量的网络 资源，并且广播节点需要知道全网的目的节点。 最短路由。假设链路( f ，j ) 的长度用d 。来表示，d ，是节点j 到达某给定的 节点的最短路由，则常用的b e l l m a n f o r d 算法是通过下列公式来寻求节点 1 0 时延敏贼的多播路由算法研究 f 到达目的节点的最短路由的，t i p d j 。呼n 【嘞+ q 】，它是通过寻找最佳的 临节点，并通过该临节点实现到达目的节点的最短路由。 最佳路由。采用最佳路由可以克服许多缺陷，它可以将一节点对之间的流 量分配在多条路径上，从而可使网络的通过量最大，时延最小。 2 1 2 互联网络的路由 为了实现网络之间的互联，通常采用三种设各：网关、网桥和路由器。实现局 域网和局域网之问在m a c 层互联的设备称为网桥( b r i d g e ) 。实现l a n 与w a n 或l a n 与l a n 之间互联的设备称为路由器( r o u t e r ) ，它提供高级的路由功能。 实现广域网和广域网之间的互联设备称为网桥( g a t e w a y ) 。可以通过上述设备进 行路由选择。 2 2 1 引言 2 2 多播路由算法的理论基础 在研究多播路由算法时，s t c i n c r 树阊题是其理论基础，为此本节主要介绍关 于s t e i n e r 树问题的一些基础知识和相关算法。 对s t e i n e r 树问题的研究早在6 0 年代就开始了，到现在为止，已经有很多这方 面的文献。s t e i n e r 树问题的应用不仅在通信方面，在电路图的自动布线、交通线 路的经济规划、车辆的调度和编组、通信线路的铺设等方面都有应用。s t e i n e r 树 问题有很多种类型，如网格( g r i d ) 上的s t e i n e r 树问题、e u c l i d e a n 平面上的s t e i n e r 树问题、一般连通图上的s t e i n e r 树问题。由于本文讨论计算机通信网络中的多播 路由问题，而计算机通信网一般用无向连通带权图表示【4 ”，为此我们主要研究无向 连通带权图中的s t e i n e r 树算法及其性能。首先给出无向带权连通图上s t e i n e r 树问 题的定义。 首先计算机网络可以抽象为无向连通图g = ，e ) ，其中v 为网络节点( 路由 器) 的集合，e 为边( 通信链路) 的集合，在每条边e e e 上定义一个权值函数 c ( ：e r + ，表示每条边的费用( 这里的费用是一个广义上的费用，它可以根据 链路的距离、信道带宽、平均通信量、通信开销、队列平均长度、测量到的时延 第二章多播路由问题的理论基础 和其它一些因素的函数而计算出来) ，给定一个节点子集q y ，这里q 对应为多 播组成员，s t e i n e r 树问题就是要寻找一棵覆盖给定节点集合q 且费用最小的最优 s t e i n e r 树- ( ，) ，其中q y ，色。用c ) 表示树的费用，即： c 伍，) 一xc 翘毛 从最优s t e i n e r 树的定义可知，最优s t e i n e r 树中的叶子节点都应是q 中的节点， 一般称q 中的节点为基本节点；最优s t e i n e r 树中除基本节点外的其它节点被称为 s t e i n e r 节点，图g 中所有可能成为s t e i n e r 节点的节点集合记为s ，易知 q n s - a ，v i q u s 。 最小生成树和最短路径问题都是s t e i n e r 树问题的特例，当q y 时，s t e i n e r 树问题就转化为最小生成树问题，当给定节点集合中只包古两个节点时，即| q i 一2 时，就变成最短路问题最小生成树问题和最短路问题都存在多项式时间的最优 解法。但s t e i n e r 树问题不存在多项式时间的最优解法，它是一个n p 完全问题。 我们知道，如果一个最优化问题是n p 问题，除非p = n p ，否则不能在多项式时间 内精确地求解该问题。一个合理的目标是寻找该问题的一个启发式算法，使我们 能在一个低阶多项式时间内得到一个“接近”最优的解。为此对s t e i n e r 树问题一 般是讨论解决它的启发式算法。启发式算法并不保证给出最优解，那么如何评价 启发式算法的好坏呢? 主要基于两个方面的考虑：首先是时间复杂度方面的要求， 即要求有一个多项式时间界；其次是性能方面的要求，即希望所求的近似解尽可 能“接近”最优解。可以从不同角度评价启发式算法的性能，大体上可分为三类： 第一类是以算法在最坏情况下的行为为标准，研究算法得到的近似解与最优解的 接近程度，越接近越好。第二类是以算法的平均行为为标准，研究算法得到的近 似解与最优解的概率。第三类是局部搜索法，寻找局部最优解，这种方法有时很 好，有时很差，只能实践加以评定。对于算法最坏情况下的性能比，可以从理论 上给出一个上界。但最坏情况下的性能不能说明算法的实际性能如何，因为在实 际应用中，算法体现出来的是平均性能，最后情况很少发生。而算法的平均性能 是较难从理论上给出的，为此要通过仿真实验来研究算法的平均性能。 2 2 2 相关算法 对于s t e i n e r 树问题有许多启发式算法，比如基于最短路径思想的、基于最小 1 2 时延敏感的多播路由算法研究 生成树思想的【4 3 l 、k m b 算法【瑚、s p h 算法【2 4 1 、a d h 算法 2 5 - 2 6 1 等。 2 3 1 引言 2 3 仿真平台的建立 计算机网络可以抽象为图论中的图。对于图g - ，e ，c ) ，v 表示g 中的节点 的集合，e 表示g 中有向边的集合。边的权值也称为边的费用( c o s t ) 。每条边对应 着两个节点越，v e v 。两个节点对应着两条边0 ，v ) 和( v ，) 。当 ，y ) 和( v ，h ) 的费用 相同时，我们就说图g 是对称的，也称无向图，否则称图g 为非对称的，也叫有 向图。对于计算机网络，y 是网络中路由器的集合。或者是某个子网的集合，e 是 所有链路的集合，c 则是链路上的带宽、时延、数据丢失率、时延抖动或它们的 组合的集合。图g 中的节点的度是指与节点v 关联的边的个数。在有向图中节点的 度还有入度与出度之分。节点v 的入度是指与y 关联的指向v 的边的个数；节点p 的 出度是指与v 关联的背离v 的边的个数。本文中，为了简化问题的讨论，我们将网 络表示为一个无向图。 在图论中有这样一个命题：图g 中所有顶点度的和等于边数的二倍。但这个 命题在计算机网络中是有条件的。熟悉计算机网络的人都知道，通信链路有时是 不对称的。比如西安到北京的光缆可以看成一条链路。光缆中每时每刻都有数据 在传输。但从西安到北京和从北京到西安的数据量是不对等的，因而光缆中的剩 余容量也是不对等的。如果以链路中的剩余容量为费用，则西安和北京之间就有 两条边。因此上面的命题推广到不对称网络中可以这样理解：当图g 不对称时， 图中所有顶点的入度出度的和等于边数。 在研究网络的路由算法时，一般要考虑算法的最差性能上界、算法的实际平 均性能和算法的计算效率，而且更关注算法的计算效率。在评价算法的实际性能 时。没有特别的方法。首先产生一个随机网络，运行要评估的算法。这样算多次 取平均值。这样得到的结果一般认为就代表算法的实际平均性能。因此算法的第 一步就是如何产生仿真用的随机网络，使得产生的网络既具有普遍性，又接近实 际的网络特性。 目前人们提出了多种网络模型，代表的有网格模型【删、r g l 、和r g 2 1 4 5 1 ，以及 r g l 的衍生模型1 4 “7 1 第二章多播路由问题的理论基础 1 3 2 3 2 相关的随机网络模型 一、网格网络模型 第一种模型是网格状的。节点放在网格的交点处m ，仿真时，在产生的网络 中随机选择源节点，即信息发送者，以及端节点，即信息接受者这种网络具有 随机性，但是网格的特征明显与实际罔络的拓扑结构不符。与此类似的还有环形 网络、树形网络和星形网络。局域网的网络结构多是这种形状的。 二、w a x m a n 网络模型及其衍生模型 为了产生随机网络w a x m a n 提出的两种网络产生模型1 4 5 l ：r g l 和r g 2 。其中 r g l 产生的网络节点是随机分布在矩形网格上的，节点的坐标是一致分布的随机 数，每两个节点之间的距离就是它们的e u c l i d 长度，最小矩形的长度为1 个单元。 r g 2 产生的网络节点中。每一对节点的距离值为( 0 ，) 之问一致分布的随机数。这 两种模型中，两个节点之间以某个概率决定是否将两个节点连接起来，而这个概 率取决于它们之间的距离。节点u ，v 之间的相通概率由以下的式子决定。 p ( u ，v ) - pe x p - d ( u ，v ) ( a l ) 】 上式中，d ( u ，v ) 是从节点h 到v 的距离，是节点之间的最大距离，参数口和卢 控制产生尉络图的特性，其值在( o ，1 之间。增大，图的平均点度也增大；口增 大，图中长边对短边的比也增大。调节口和口的值，就可以接近实际网络。 但w a x m a n 网络模型具有如下的缺点： 第一：无法保证每次都能生成连通的网络拓扑结构。 第二：对于恒定的a 和卢的值，每次生成的网络拓扑平均度数不恒定，而是随 着网络节点的度数的增加而增加。 d o a r - l e s i l 模型1 4 6 l 在模型r g l 的基础上，用肚n ( “是预期的平均点度，n 是网络的节点，k 是一个取决于d 和卢的常量) 调节概率p ( u ，v ) ，更直接地控制网 络的边数。指数模型和局域网模型1 4 7 1 都是更直接地将节点之间地距离和概率 p ，v ) 联系起来。指数模型生成的概率随节点之间距离的增加而成指数下降。局 1 4 时延敏感的多播路由算法研究 口d ( h ，v ) s p 以，d - 卢d 0 ，v ) r z0 r 2 l rd ，y ) 苫厂2 2 3 3 路由仿真平台 现有啦路由仿真平台一般分为两大类：1 ) 通用的网络平台。例如：m i l 3 公司 的o p n e t 、c a d e n c e 公司的b o n e sd e s i g n e r 、c a c i 公司的c o m n e t ? 和p r o p h e s y 公司的p r o p h e s y 等。这些商用软件虽然不是为路由仿真专门设计的，但其具有强 大的路由仿真功能。缺点是使用起来比较复杂。一般需要专门业务培训才能掌握， 且价格昂贵。2 ) 专用的路由仿真平台。此类路由仿真平台仅用于路由仿真，功能 较单纯、使用比较方便。例如：m a r s ( m a r y l a n dr o u t i n g s i m u l a t o r ) ，q r s ( q o sr o u t i n g s i m u l a t o r ) ，m c r s i m ( m u l t i c a s tr o u t i n gs i m u l a t o r ) ，m a s t ( m u l t i c a s t a n a l y s i st 0 0 1 ) 等 这些软件虽然功能强大，但在应用和功能方面却存在着这样或那样的不足之处。 如m a r s 只能仿真b e s t - - e f f o r t 路由算法或协议，不能仿真q o s 路由算法；m c r s i m 多播路由仿真平台不能仿真路由算法在邛网络上的性能，极大的限制了其应用范 围。 因此自行的开发一个能适应于我们试验要求的网络仿真平台是十分必要的。 这也是一个重要的研究方向。 第三章时延敏感的多播路由算法 第三章时延敏感的多播路由算法 本章研究了时延敏感的多播路由算法，即满足时延，时延及时延抖动 的多播路由算法对于时延受限多播路由问题给出了一种综合加权的求解 方法，数值实验表明该算法是有效的然后提出了一种用改进的遗传算法 求解时延及时延抖动的多播路由算法 3 1 满足时延约束的多播路由问题的数学模型 对于时延约束的多播路由问题，本节首先给出了其数学描述。 计算机通信网一般用无向图g t ，e ) 表示。其中v 是网络节点的集合，e 是 链路的集合，并且在每条链路m ，v ) 上具有两个参数：链路费用c 0 ，v ) 0 ，可以包 括价格、距离、带宽、占用量等；链路时延d “v ) 。s 表示源节点，d - d l ，d ：d 。) 表示目的节点集合，所有的目的节点时延约束规定为。则一个多播请求可定义为 r ( s ，d 。a ) ，5 为源节点，d 为目的节点集合，为上述的。s e v ，s q 6 _ d ， d e y 一臼 ，设最d , 3 播