（运筹学与控制论专业论文）网络通讯中的qos组播路由算法研究.pdf

火连理工大学硕士学位论文 摘要 组播路由算法属于网络优化的范畴，它是计算机网络的应用和发展中的核心问题。 组播路由算法对于减小计算机网络的流量和减轻服务器的负担都有着非常大的意义。随 着人们对网络服务质量的要求( q u a l i t y o fs e r v i c e ，简写为q o s ) 越来越高，在求 组播树的过程中就需要加入越来越多的限制条件，这也使得我们所求解的问题成为n p 完全问题。对于此类问题，我们只能设计出不同的策略来尽可能快的求解出尽可能逼近 最优解的结果。 本文的前两章，主要讨论了组播路由算法研究过程中要用到的一些基本知识，包括 图论中的一些基本概念和算法，主要为第三章和第四章的研究工作做准备。 在第三章和第四章中，介绍了本文所取得的主要结果，可概括如下： 1 在第三章中。首先对d i j k s 订a 算法进行了修正以适用于我们研究的主题，然后在虚 拟网图中运用我们所制订的策略，即按照带宽要求由大到小为节点排序，按照顺序 利用修正的d i j k s w a 算法为图中的每个节点寻找到可行的路。在此算法中，并不能 保证每一个节点最后都有可行路，但根据计算机网络的工作原理，可以将这些节点 并入下一次任务。 2 在第四章中，我们提出了种基于最小树算法的组播路由算法。首先构造一棵树， 使得所有的向服务器发送了请求的节点都被包含在树中。然后对树中的节点逐个进 行检查，看组播树为其提供的路是否满足该节点的要求。对于那些不满足要求的节 点，我们利用推广的d i j k s t r a 算法为其寻找新的符合其要求的最小费用路，直到所 有的节点都满足约束。 关键词：组播路由：最小树；d i j k s t r a 算法；s t e i n e r 树 旦塑望塑塑q ! ! ! ! 堡些皂蔓塑塞 s t u d yo n q o s m u l t i c a s tr o u n n ga l g o r i t h m i nn e i i w o r kc o m m u n i c a t i o n a b s t r a c t m u l t i c a s tr o u t i n ga l g o r i t h mb e l o n g st ot h ec a t e g o r yo fn e t w o r ko p t i m i z a t i o n ，a n di ti s t h ec o r e p r o b l e mo fc o m p u t e rn e t w o r ki na p p l i c a t i o na n dd e v e l o p m e n t i th a sg r e a t s i g n i f i c a n c ei nr e d u c i n g t h ef l o wo fc o m p u t e rn e t w o r ka n dl i g h t e n i n gb u r d e no fs e r v e r s a s p e o p l eh a v em o r e a n dm o r e h i g he x p e c t a t i o n sf o rq o s ，w e n e e dt oj o i nm o r ea n dm o r e l i m i t i n g c o n d i t i o n sd u r i n gt h ep r o c e s so f a s k i n gm u l t i c a s t t r e e ，w h i c hm a k e st h ep r o b l e m s t ob es o l v e db e c o m e n p - - c o m p l e t ep r o b l e m s t ot h i sk i n do fp r o b l e m 。w ec a no n l yd e s i g nd i f f e r e n tt a c t i c st os e e kt h ea p p r o x i m a t e o p t i m a ls o l u t i o na ss o o n a sp o s s i b l e i nt h ef i r s tt w o c h a p t e r so f t h i st e x t ，t h em a i nd i s c u s s i o ni ss o m eb a s i ck n o w l e d g et o b eu s e di nt h ec o u r s e ，i n c l u d i n gs o m eb a s i cc o n c e p t i o n sa n da l g o r i t h m si nt h eg r a p h t h e o r y i tm a i n l yp r e p a r e sf o r t h er e s e a r c hw o r k o f c h a p t e r 3a n d c h a p t e r 4 i n c h a p t e r3a n dc h a p t e r4 ，t h em a i nr e s u l t s t h i st e x th a v ei n t r o d u c e d ，c a nb e s u m m a r i z e da sf o l l o w ： 1 i nc h a p t e r3 ，w eh a v em o d i f i e dd i j k s t r aa l g o r i t h mi no r d e rt h a ti tc a nb es u i t a b l ef o rt h e t h e m et h a tw e s t u d ya tf i r s t t h e n ，u s et h et a c t i c st h a tw em a k ei nf i c t i t i o u sm e s hg r a p h ， n a m e l ya r r a n g ei na n o r d e rf o rt h en o d e sf r o mg r e a tt os m a l la tt h e r e q u e s to f b a n d w i d t h ： u t i l i z em o d i f i e dd i j k s t r aa l g o r i t h mt of i n dt h ef e a s i b l ep a t hf o re a c hn o d ei nt h em e s h g r a p ha c c o r d i n gt ot h eo r d e r i nt h i sa l g o r i t h m ，i tc a nn o tg u a r a n t e et h a te v e r yn o d eh a sa f e a s i b l ep a t hf i n a l l y ，b u ta c c o r d i n gt ot h eo p e r a t i o n p r i n c i p l eo ft h ec o m p u t e rn e t w o r k ，c a n i n c o p o r a t e t h e s en o d e si n t ot h en e x tt a s k 2 i nc h a p t e r4 ，w eh a v ep r o p o s e dam u l t i c a s tr o u t i n g a l g o r i t h mo nt h eb a s i so fm i n i m u m t r e ea l g o r i t h m c o n s t r u c tat r e ea tf i r s t ，m a k es u r et h a ta l ln o d e ss e n tr e q u e s t st os e r v e r i n c l u d e d t h e nc h e c kt h e mo n e b y o n et oo b s e r v ew h e t h e ri t sp a t ho f f e r e db yt h em u l t i c a s t t r e ec a ns a t i s f yi t sc o n s t r a i n t s a st on o d e sw h o s ec o n s t r a i n t sc a nn o tb es a t i s f i e d ，w e u t i l i z eg e n e r a l i z e dd i j k s t r aa l g o r i t h mt os e a r c ham i n i m u m - c o s tp a t hw h i c hi sn e wa n d s u i t a b l eu n t i lt h a ta l ln o d e s c o n s t r a i n t sb es a t i s f i e d k e y w o r d s ：m u l t i c a s t r o u t i n g ：m i n i m u mt r e e ：d u k s t r aa l g o r i t h m ：s t e i n e r t r e e 一一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：堑逝e t 期：作者签名：垡婴期： 大连理工大学硕士学位论文 1 绪论 本章首先介绍了计算机网络在现代经济生活中的重要作用和地位以及网 络协议在计算机网络中不可替代的作用。之后是路由算法的简要介绍及其分 类，组播路由算法的发展概况以及目前所取得的成果，并说明了q o s 组播路 由的重要 生 1 1 计算机网络在信息时代中的作用 2 l 世纪的一些主要特征就是数字化、网络化和信息化，它是一个以网络为核心的 信息时代。 当前世界经济正在从工业经济向知识经济转变。知识经济是相对于农业经济、工业 经济而出现的一种正在形成中的崭新的经济形态。知识经济就是指以知识为基础的经 济，并且经济的发展在很大程度上取决于对知识的发掘和积累。知识经济的诞生不仅对 人们的工作、学习、交往等各个方面起着非常大的作用，而且也影响了整个社会的发 展。知识经济已成为推动生产力发展的巨大动力。 知识经济中的两个重要特点就是信息化和全球化。要实现信息化和全球化，就必须 依靠完善的网络。因此，网络现在已经成为信息社会的命脉和发展知识经济的重要基 础。网络对社会生活的很多方面以及对社会经济的发展均产生了不可逆转的影响。 这里所说的网络是指“三网”，即电信网络( 主要的业务是电话，但也有其他业 务，如传真、数据等) 、有线电视网络和计算机网络。虽然这三种网络在信息化过程中 都起到了十分重要的作用，但其中发展最快的并起到核心作用的是计算机网络。 进入2 0 世纪9 0 年代以后，以因特网( i n t e r n e t ) 为代表的计算机网络得到了飞速 的发展，已从最初的教育科研网络逐步发展成为商业网络，并已成为仅次于全球电话网 的世界第二大网络。不少人认为现在已经是因特网的时代，这正是因为因特网芷在改变 着我们工作和生活的各个方面，它已经给很多国家( 尤其是因特网的发源地美国) 带来 了巨大的好处，并加速了全球信息革命的进程。可以毫不夸大的说，因特网是自印刷术 以来人类通信方面最大的变革。现在人们的生活、工作、学习和交往都已离不开因特 网。 1 9 9 3 年9 月1 5 日，美国政府发布了一个在全世界引起很大反响的文件，其标题是 “国家信息基础结构( n i i ) 行动计划”。n i i ，即n a t i o n a li n f o r m a t i o ni n f r a s t r u 网络通讯中的q o s 组播路由算法研究 c t u r e 的缩写，也可译为国家信息基础设施。这个文件提出，高速信息网是国家信息基 础结构的一个重要组成比分。为了更加生动而形象的说明这个“n i i 行动计划”，人们 常用“信息高速公路”这个词作为“国家信息基础结构”的通俗名称。 1 9 9 4 年9 月美国又提出了建立全球信息基础结构g i i ，建议将各国的n i i 互连起来 组成世界范围的信息基础结构。当前的因特网就是这种全球性的信息基础结构的雏形。 现在全世界的工业发达国家和很多的发展中国家都纷纷研究和制定本国建设信息基 础结构的计划。这就使得计算机网络的发展进入了一个新的历史阶段，并变成了几乎人 人都知道而且十分关心的热门学科。 1 2 网络协议在计算机网络中不可替代的作用 计算机网络是个非常复杂的系统。为了说明这点，可以设想一个最简单的情况： 连接在网络上的两台计算机要互相传送文件。 显然，在这两台计算机之间必须有一条传送数据的通路。但这还远远不够，至少还 有以下几件工作需要去完成： ( 1 ) 发起通信的计算机必须将数据通信的通路进行激活( a c t i v a t e ) 。所谓“激活” 就是要发出一些信令，保证要传送的计算机数据能在这条通路上正确发送和接收。 ( 2 ) 要告诉网络如何识别接收数据的计算机。 ( 3 ) 发起通信的计算机必须查明对方计算机是否已经准备好接收数据。 ( 4 ) 发起通信的计算机必须弄清楚，在对方计算机中的文件管理程序是否已做好文件 接收和存储文件的准备工作。 ( 5 ) 若计算机的文件格式不兼容，则至少其中的一个计算机应完成格式转换功能。 ( 6 ) 对出现的各种差错和意外事故，如数据传送错误、重复或丢失，网络中某个节点 交换机出故障等，应当有可靠的措旌保证对方计算机最终能够收到正确的文件。 还可以举出一些要做的其他工作。由此可见，相互通信的两个计算机系统必须高度 协调工作才行，而这种“协调”是相当复杂的。网络协议的作用就是完成这件复杂的工 作。没有网络协议的帮助，计算机之间是不能通信的。 在两台计算机实际进行通信的时候，它们之间可能有几条或者更多的通路可以进行 通信。那么我们选择其中的哪一条好呢? 毋庸置疑，首先，这条通路必须满足所进行的 通信要求的必要条件，例如最低带宽、最短时延等；然后，我们再从所有满足这些必要 条件的通路中选出所花费的费用最少，或者所用的时间最短，或者二者折中使得某指定 函数值最小的那条。显然，最好的结果就是我们所选的通路花费既是最少的，同时所用 一2 大连理： 大学硕士学位论文 的时间又最短。那么，我们如何找到这条路昵? 网络协议中的路由算法的功能就是完成 这项任务。 1 3 路由算法 1 3 1 路由算法简介及优化准则 路由算法的作用就是为网络传输的数据寻找合适的路由。所谓合适的路由，就是能 够满足用户的要求并且还要尽可能的减少数据传输过程中消耗的网络资源的通路，这里 的网络资源就是我们前面提到的带宽、费用等等。 在计算机网络中，从一个节点( 端) 到另一个节点( 端) 的路由称为单播路由 ( u n i c a s t ) ，从一个节点到多个节点，或者多个节点到多个节点的路由称为组播路由 ( m u l t i c a s t ) 。单播路由是从一个节点到另一个节点的一条通路，组播路由是由多条 路组成的一棵树。 简单地说，组播就是指点到多点，或多点到多点的通信形式，即多个信宿同时接收 一个信源发送的相同信息，这是网络中大量业务存在着点到多点通信需求的必然结果。 广播是指数据分组发给网络中所有成员，而组播是将一个分组发向所有节点中的某个确 定子集。实际上，单播、广播和点到多点通信方式可以看作是组播的特例。因此，我们 着重讨论组播路由算法。 下面我们介绍一下路由算法的优化准则。设计组播路由算法是件很复杂的工作，组 成员关系不断变化，网络拓扑也在变化，组播路由技术上要求如下： ( 1 )减少网络负载。优化网络资源包含两点：避免环路和避免资源在链路上的拥 塞。 ( 2 ) 对可靠传送的支持。理想状态下路由变化对组内剩下的成员数据流量没有边 缘影响。链路失效不应增加传送时延或减少资源可利用率。在同步应用中时 延限制显得非常关键。路由变化越快，系统可靠性就越差。 ( 3 ) 路由算法应当考虑到不同的代价函数，包括可利用资源、带宽、链路数目、 节点连续性、花费和端到端时延。如果说设计路由很复杂，那么在组和网络 变化时，维护优化路由就更加复杂的多。这个问题其实是在路由效率和组的 动态性之间寻找一个折中。 ( 4 ) 对某些应用来说，减少路由器上的存储信息至关重要。否则，当一个组播组 很大时，算法很难实现。 3 网络通讯中的o o s 组播路由算法研究 组播路由算法的出发点是：多点传送需要的是组播树而不是链路。理想的有效路由 算法应是设计一个只覆盖组内成员并具有如下特性的组播树： 包含组成员关系。路由算法应该能将数据只传送给特定的组成员。 减少节点的状态信息。 优化路由代价函数。 避免链路或节点的集中拥塞。 1 3 2q o s 组播路由算法产生的背景 在传统的点到点网络支持能力下，多点间通过分别寻址在信源到每个信宿之间分别 建立最短路由，对应复制数据分别发送，实现多点通信。许多情况下，组播树是多个单 播路径简单的叠加。由于过去很少的网络应用涉及多个用户，多数应用带宽要求较少， 而且一般业务仅需要提供最努力服务( b e s t e f f o r ts e r v i c e ) ，即网络只是尽快地将 数据传送到目的地，不对用户做服务质量保证。因此，上述简单的组播寻址方式足以使 网络满足多点业务的带宽要求。 然而，随着i n t e r a c t 向商业模式的迅速转变以及高速宽带网络的快速发展，多媒体 业务诸如流媒体、视频会议和视频点播等，正在成为信息传送的重要组成部分。这些应 用包括多媒体端到端时延要求很高的视频会议和一些要求可靠性的分布式控制应用，它 们用服务质量参数( q u a l i t y o f s e r v i c e ，简记为q o s ) 来描述应用的要求，如端到 端时延、时延抖动、数据包丢失率等指标。这样的服务要求端到端之间建立面向连接 ( c o n n e c t i o n o r i e n t e d ) 的通路。为了满足这种需要，有必要寻求网络层对多点通信 能力的支持，在新的路由算法下满足多媒体实时应用的要求。 分布式应用会利用下一代网络，而且在很多情况下会包含许多用户。这使得组的规 模，业务的特征和服务质量要求发生了很大的变化。所以，能有效控制网络资源和满足 q o s 要求的组播算法的重要性日益明显。带宽和处理能力上的进展为会议电视、分布式 处理等多点通信业务提供了有力的支持。点对点传输的单播方式不能适应这一类业务传 输特性单点发送多点接收，因为服务器必须为每一个接受者提供个相同内容的 i p 报文拷贝，同时网络上也重复地传输相同内容的报文，占用了大量资源。虽然i p 广 播允许一个主机把一个i p 报文发送给同一个网络的所有主机，但由于不是所有的主机 都需要这些报文，因而浪费了网络资源。在这种意义下，支持多点、多连接和多q o s 要 求的通信方式将是网络支持多媒体业务的体现形式。 4 - 人连理工大学硕士学位论文 在这样的背景下，q o s 组播路由( q o s m u l t i c a s t r o u t i n g ) 应运而生，它的出现 解决了一个主机向特定的多个接收者发送多媒体流的问题。作为支持网络多媒体业务的 关键技术之一，q o s 组播路由已经引起了广泛重视，它根据网络中可利用资源和网络业 务的q o s 要求，计算从一源节点到多个目的节点的业务传输路径。 q o s 限定了数据发送者和数据接收者之间的通路应该满足的要求。例如，单播路由 的带宽约束要求这条路中的所有的链路上的剩余带宽都要大于约束值。一棵组播树上的 约束就要求这棵树中所有的路都要满足约束条件。一棵有时延约束的组播树要求从发送 数据的端到树中任一个接收端的时延都要小于约束要求的时延上限。 1 3 3 组播路由算法 1 3 3 1 研究方法 i 网络模型方法 组播所涉及的网络通常可表示成一个赋权图g ；，e ) ，其中矿是节点组成的集 合，e 是链路组成的集合。g 的一条链路可表示为二元组以，y ) ，其中“，v y 。i 矿l 和 i e 1 分别表示节点数和链路数。 为了表示网络的状态，我们还要为每条链路赋予一些参数： 定义1 3 1 时延权函数存在链路集合e 到正实数集合r + 的映射d ：e r + ，对 e e e ，d ( e ) 表示链路e 上的时延，包括排队时延、传输时廷、传播时延我们称d ( e 1 是链路e 的时延权函数。 定义1 3 2 带宽权函数 存在链路集合e 到正实数集合r + 的映射w ：e r + ，对 e e e ，w ( 0 表示链路e 上的可用带宽。我们称w ( p ) 是链路p 的带宽权函数。 d ( p ) 和w ( p ) 反映链路的状态。 组模型方法 组模型( g r o u pm o d e l ) 也可称组播模型( m u l t i c a s tm o d e l ) ，它表达的是参与组 播通信的群组成员之间的关系特征，即群组特征。 定义1 - 3 3 群组给定一个网络g a ，e ) ，设肘是v 的任意子集，即m v ， m 包含如下两类节点： ( 1 ) 源节点，即连接源主机的路由器节点： ( 2 ) 接收者节点，即连接接收主机的路由器节点： 且m 满足下列条件： 有一个全局唯一标识符： 5 一 网络通讯中的q o s 组播路由算法研究 m 的成员节点可以在任意时刻加入或退出m ； 肘中的成员节点可以是另一个满足此定义的集合m 的成员； 则称m 是网络g 的一个群组。 在这里群组定义是一个网络层概念，它不失组播群组的基本特征，同时又便于网络 协议的设计表达。 1 3 3 2 组播路由问题描述 组播路由的核心问题是如何建立组播树。组播树又称转发树( f o r w a r d i n gt r e e ) 或交付树( d e l i v e r yt r e e ) 。 定义1 _ 3 4 组播树设t 是图ga 缈，e ) 的一个子图，m 是g 中的一个群组；如果 丁 不包含回路： r 的路径通过肘的全部成员； 则称r 为g 的一个纽播树。 显然，r 可以包含非m 成员节点，这些节点构成组播树的一部分。t 中非m 成员 节点位于从源端节点s 到接收者节点v m d 的传输路径上，可用p 0 ，v ) 表示该路 径，显然p ( s ，v ) c t 。 对于给定的网络g ，一个组播任务可描述为一个4 元组f - ( m ，a ，o ，t ) ，其中m 是组播群组；q 是任务f 的服务质量要求，即o o s 约束，一般包括端到端时延限制、最 低带宽要求、时延抖动限制和丢包率等；r 是完成任务r 所需要建立的组播树；o 是一 组对丁进行优化的目标函数，例如使丁的总费用为最小等。一个没有q o s 约束的组播可 以视为f 的一个特例。 组播路由问题可定义如下： 定义1 3 5 组播路由阅题 对于给定的网络g ，通过某种算法秘a 关协议，构造一 个可以完成组播任务_ r 的组播树丁，使r 伸展到肘的所有成员。 1 3 4 组播路由算法分类 1 3 4 1 集中算法和分布式算法 集中路由算法( c e n t r a l i z e dr o u t i n ga l g o r i t h m ) 也称为显式路由( e x p l i c i t r o u t i n g ) 或源路由( s o u t c er o u t i n g ) 算法。其特点是，源节点计算出从源端到目标 6 大连理工大学硕士学位论文 节点的整个组播树。为此，网络中的每个路由器都必须维护一个全局状态( g l o b a l s t a t e ) 信息库，并且周期性的对其进行更新。 分布式算法( d i s t r i b u t e dm u l t i c a s ta l g o r i t h m ) 的特点在于组播树计算是由位 于网络中的多个路由器协作完成的。例如，p i m s m 的算法是分布式的。分布式算法 的优点是计算负担被分散了，但容易导致环的出现。 1 3 4 2 确定性算法、近似算法与启发式算法 所谓确定性算法( e x a c ta l g o r i t h m ) 是指在一定条件下以确定的计算步骤求解问 题的算法。确定性算法的优点是简单，但不提供回溯能力。确定性算法往往具有较高的 多项式时间复杂度。 近似算法( a p p r o x i m a t ea l g o r i t h m ) 是指以多项式时间解决优化问题并保证能够 得到接近优化解的近似解的算法。 启发式算法( h e u r i s t i ca l g o r i t h m ) 采用某个启发式函数或启发式规则对计算步 骤进行限制，它不保证能够找到可行解。但是设计一个较好的启发式算法，往往能够得 到接近最优的解( n e a ro p t i m a ls o l u t i o n ) ，同时具有相对低的时间复杂度。由于很 多q o s 组播路由问题是n p 完全问题，例如有时延限制的s t e i n e r - t r e e 问题、有带宽限 制的s t e i n e r t r e e 问题等等，因此大部分这类问题都采用启发式算法。 1 _ 4 目前的研究现状及取得的成果 如前面所说，在计算机网络发展的初期，网络向用户提供的是尽最大努力的服务， 因此当时的算法主要是针对这种形式的服务方式来设计的。然而，随着多媒体服务在网 上的出现以及人们对多媒体服务的要求迅速的增加，如视频会议、视频点播、远程教 学、分布式交互仿真等，近年来q o s 组播路由算法研究引起了人们极大的兴趣，提出了 许多好的算法。 1 4 1s t e i n e r 树问题 q o s 组播路算法的目标就是要在一个有权图中建立一棵满足q o s 约束条件且花费最 少的组播树。在最简单的情况下，即无任何约束的情况下，在一图中经过给定节点集且 花费最少的树称为s t e i n e r 树。也就是说，s t e i n e r 树就是经过一给定节点集的最小费 用树。容易看出，我们要求的满足q o s 约束的组播树就是带有约束条件的s t e i n e r 7 旦塾塑塑主塑9 堕望塑堕旦墨塑塑 树，如带有时延约束的最小费用树等。我们就称这类树为有约束条件的s t e i n e r 树 ( c o n s t r a i n e ds t e i n e rt r e e ) 。有约束条件的s t e i n e r 树问题是n p 完全问题。 严格来讲，建立一棵s t e i n e r 树并不是一个q o s 组播路由问题。然而，建立一棵 s t e i n e r 树的启发式算法对于建立一棵有约束条件的s t e i n e r 树有着很直接的影响。因 此，我们有必要来研究s t e i n e r 树的求法。下面是两种常用的求s t e i n e r 树的算法，需 要声明的是，在下面的两种算法中，都是以费用作为图中边上的权，两节点间的最短路 指的是两节点间花费最少的路。 ( 1 ) t h ek o ue ta 1 a l g o r i t h m 1 9 9 3 年，k o m p e l l a 等人提出了k o m p e l l ae ta 1 算法”“。在该算法中，一个网络 被抽象成一个完全图，其中的节点代表源节点和终端节点，边代表两节点间的最短路。 利用p r i m 算法，可以求出这个完全图的最小支撑树。将最小支撑树中的边还原为其代 表的路后，就得到了s t e i n e r 树。 ( 2 ) t h et a k a h a s h i m a t s u y a m aa l g o r i t h m 1 9 8 0 年，h t a k a h a s h i 和a m a t s u y a m a 提出了t a k a h a s h i - m a t s u y a m a 算法”“。 该算法是利用就近原则来求s t e i n e r 树的。首先，找到距源节点最近的终端节点，则它 们之间的最短路也随即被确定。这样，在以后的每一步迭代中都从树外的节点中选出距 离当前树最近的节点加入树中，直到所有的节点都被加入到树中，就得到了s t e i n e r 树。 1 4 2 近年来一些好的q o s 组播路由算法 ( 1 ) t h ee o m p e l l ae ta 1 a l g o r i t h m 该算法是由k o m p e l l a 等人在1 9 9 3 年针对上述有约束条件的s t e i n e r 树问题提出 的一种启发式算法h 引。 第一步，建立一完全图，其中节点代表源主机和终端，边代表两节点间满足时延限 制的最短路。我们假设边上的时延总为整数，且时延限制总是有界的，则这样的一个完 全图总可以在多项式时间内建立起来。 第二步，建立上述完全图的有时延限制的支撑树。把源节点看作一棵最简单的树， 以这棵树为起点，每次向树中加入一条满足以下条件的边，直到所有的节点加入到树 中： 1 边的两端节点一个在树中，一个不在树中； 2 该边加入后不违反时延限制； 8 大连理工大学硕士学位论文 3 使选定函数的值最小。 一般可供我们选择的函数有两个： 第一个函数为费用函数c ( e ) ； 第二个函数为 a l c ( e ) + t f ( e ) ， 其中c ( e ) 为费用函数，f ( e ) 为时延函数， ，0 ， ：，0 。 ( 2 ) t h es u n l a n g e n d o e r f e ra l g o r i t h m 该算法由s u n 和l a n g e n d o e r f e r 在1 9 9 5 年提出，它利用d i j k s t r a 算法构造一近 似的有约束条件的s t e i n e r 树”。在该算法中，首先计算最小费用路，即找到每个终 端节点到源节点的最小费用路，这样便得到了一棵支撑树。然后，我们再对该树进行修 正使其满足时延限制。如果某终端节点到源节点的路违反了时延限制，我们就用这两节 点间的时延最小的路来代替它。该算法的优点是其时间复杂度低，为o ( v l o g v l 。 ( 3 ) t h e w i d y o n oa l g o r i t h m w i d y o n o 针对c o n s t r a i n e ds t e i n e r 树问题提出了几种启发式算法，其中j 眭能最好 的一个算法被称为t h ec o n s t r a i n e da d a p t i v eo r d e r i n gh e u r i s t i c ”1 。该算法的每 一步迭代中，利用c o n s t r a i n e db e l i m a n f o r d 算法，都可以求得从源节点到树外终端 节点的满足时延限制的最小费用路，将求得的路与该终端节点一块并入树中。树中的边 上的费用被设为0 。重复上述过程直到所有节点被加入到树中便得到了我们要求的有约 束条件的s t e i n e r 树。 ( 4 ) z h ue ta 1 a l g o r i t h m q z h u ，m p a r s a 和j j g a r c i a - l u n a - a c e v e s 在1 9 9 5 年提出了启发式的源路由组播 算法来建立有约束条件的s t e i n e r 树“。该算法允许终端节点有可变化的时延上限。 首先以时延作为边上的权利用d i j k s t r a 算法求出花费时间最少的树，只要树中有任意 一个终端节点违反时延限制，就必须重新来建立树。等所有的节点都满足时延的约束条 件以后，算法开始一步步迭代对树进行修正。在迭代过程中，对树中的一个终端节点， 如果可以找到一条路可以比当前的路花费的费用少，就用这条花费更少的路代替当前的 路。算法的基本思想就是用费用比较低的路来替代当前的路。算法总可以找到一棵满足 时延限制的树，只要这样的树存在。因为我们是从花费时间最少的路开始迭代的。 ( 5 ) t h ek o m p e l l ae t a 1 a l g o r i t h m k o m p e l l a 等人在1 9 9 3 年提出了一种分布式的启发式算法用来建立有约束条件的 s t e i n e r 树“。该算法要求每个节点维护一个距离向量，其中存储着该节点到其他节 点的最小时延。把源节点看作一棵树，以这棵树为初始树，利用迭代的方法，每迭代一 9 网络通讯中的o o s 组播路由算法研究 次向树中加入一条链路。算法的每次迭代包括三个阶段的信息传递：第一阶段，源节点 向当前树中节点广播寻找消息。一个节点接到消息后，它会寻找一个与其相邻的树外节 点，使得它们之间的链路不违反约束，且使得选择函数的值最小。第二阶段，选定链路 的信息被传回源节点，在这些链路中，取那条使得选择函数值最小的那个链接l 。第三 阶段，源节点向l 发送加入消息。 当所有的终端节点加入到树中后，算法结束。该算法需要密集的消息交换，在最坏 的情况下，消息交换的复杂度为o ( v 3 1 。 ( 6 ) c h e n n a h r s t e d ta l g o r i t h m 该算法是由c h e n 和n a h r s t e d t 在1 9 9 8 年通过扩展他们相应的单播路由算法而得到 的”。在该算法中，源节点向组播组中的每个终端节点发送令牌，令牌只沿着那些前 方至少有一个终端节点并且有足够的资源来满足q o s 要求的通路前进。当令牌到达一组 终端节点之后，一棵组播树就以分布式的方式建立起来。每个节点维持它自己的局部状 态信息。在最坏的情况下，建立这样一棵组播树的计算复杂度是0 f e 、。 c h e r t n a h r s t e d t 算法只适用于组播组的成员事先已确定的情况。在组播组成员可 以动态变化的情况下，我们可将上面的算法作以下修改。当一个新的终端节点加入到组 播组中时，它向组播树发送一个令牌，令牌只沿着那些满足q o s 要求和优化条件的路前 进。只要令牌到达组播树中的任意一个节点，一棵得到扩展的可行树就建立起来。在晟 坏的情况下，将一个新节点利用上述方法加入到可行树中的计算复杂度为d 伯) 。 1 0 大连理工大学硕士学位论文 2 基本理论和算法 妇播路由算法属于网络优化的研究范畴，我们一般是用图论的观点采研 究网络优化的。因此，有必要来介绍一下图论中的一些基本理论。在本章， 主要介绍了图论中的一些最基本的定义、定理和算法。为我们后面研究组播 路由算法做一些必要的准备。 2 1 有向图与有向网络的基本概念 定义2 1 1 有向图一个有向图( d i r e c t e dg r a p h 或d i g r a p h ) g 是由一个非空有限集 合y ( g ) 和y 【g ) 中某些元素的有序对集合4 ( g ) 构成的二元组，记为g 一缈( g ) ，4 ( g ) ) 其中v ( a ) 一 v l ，。2 i 一，叱 称为图g 的顶点集( v e r t e xs e t ) 或节点集( n o d es e t ) ， y ( g ) 中的每一个元素u ( f 。1 , 2 ，n ) 称为该图的一个顶点( v e r t e x ) 或节点( n o d e ) ； a c a ) ； 口1 ，a 2 ，称为图g 的弧集( a r es e t ) ，a ( g ) 中的每一个元素吒( 即v ( a ) 中某两个元素屹，p ，的有序对) 记为- 以，p f ) 或口。一v , v i ( k 一1 ，2 ，埘) ，被称为该图的 一条从u 到v ，的弧( a r c ) 。在不引起混淆的情况下，记号v ( g ) 和a ( g ) 中也可以省略 g ，即分别记顶点集、弧集为v 和a ，而记有向图g - ，锄。 如果对有向图g 中的每条弧赋予一个或多个实数，得到的有向图称为赋权有向图或 有向网络，简称为网络( n e t w o r k ) 。为了讨论方便，我们对图和网络不做严格区分， 因为任何图总是可以赋权的。 当弧吒一“，v j ) 时，称，vj 为弧气的端点( e n d p o i n t ) ，其中叶为尾( t a i l ) ， v f 为头( h e a d ) 并称v i 在g 中与q 相邻( a d j a c e n t ) 或y ，是h 的邻居( n e i g h b o r ) ； 弧a 称为与顶点u ，y f 关联( i n c i d e n t ) ，并称弧a t 为u 的出弧( o u t g o i n ga r c ) ，为 v ，的入弧( i n c o m i n ga r c ) 。如果某两条弧至少有一个公共点，则称这两条弧在图g 中相邻。 图的概念是现实生活中图形概念的数学抽象，因此一个图也可以用图形来直观表 示：用小圆圈表示顶点，用顶点间的带箭头的连线表示弧及其方向( 箭头从弧的尾指向 弧的头) 。例如，如图2 1 的图形表示的是有向图g 。，a ) ，其中顶点集y ； v 1 ， v 3 ，v 4 ，v 5 ，弧集a = 8 1 ，口2 ，如，d 4 ，d 5 ， ，弧o l 一( v 1 ，v 2 ) ，口2 一( v l ，v 2 ) ，口3 = 他，如) ， 口。= ( 屿，v 。) ，口5 ，p 。，u ) ，氏一( v 3 ，b ) 。在该图中，弧口1 ，吼都是从顶点h 指向顶点 也，这种弧称为多重弧( m u l t i a r c ) ，相应的图称为多重图( m u l t i g r a p h ) 。值得注 堕竺型生塑q 箜堡塑堕虫墨堕堑塑 意的是：这时弧集合a 也应当理解成多重集( m u l t i s e t ) ，即a 中可以包括多个相同 的元素，这与我们通常所说的普通集合的概念有所不同。在该图中，弧的头和尾都相 同( b ) ，这种弧称为环( 1 0 0 p ) 。在该图中，没有任何弧与顶点v 5 关联，这样的顶点称 为孤立点( i s o l a t e dv e r t e x ) 。 图2 1 有向图的一般例子 o h 图中顶点的个数称为图的阶( o r d e r ) 。通常用i v i 或肛表示顶点的个数( 即图的阶 数) ，用f a l 或m 表示弧的条数。特别地，我们称只有一个顶点的图为平凡图( t r i v a l g r a p h ) ；不包括任何弧的图为空图( n u l lg r a p h ) 。没有环，且没有多重弧的图称为 简单图( s i m p l eg r a p h ) 。例如，在图2 1 所示的图g 中，图的阶数为，l - i 矿i = 5 ，弧的 条数为m 叫a i s 6 ，图g 不是平凡图或空图，也不是简单图。 图中与一个顶点关联的出弧的数目称为该顶点的出度( o u t d e g r e e ) ，入弧的数目 称为该顶点的入度( i n d e g r e e ) ，而出度与入度之和称为该顶点的度( d e g r e e ) 。度数 为偶数的顶点称为偶点( e v e np o i n t ) ，否则称为奇点( o d dp o i n t ) 。例如，在图2 1 所示的图g 中，节点叱的度为3 ，一般记为如化) 一3 ；节点h 的出度为1 ，一般记为 d ；( 屹) 一1 ：节点也的入度为2 ，一般记为螺( 也) = 2 。在不引起混淆的情况下，也可以 省略g ，即分别记为d ( v 2 ) 一3 ：d + ( v ：) 一1 ；d ( 屿) = 2 。图2 1 所示的图g 中节v 1 、 为奇点，u 、v 。、k 为偶点。 1 2 大连理工大学硕士学位论文 假设g 。，a ) 和g 一，国是两个有向图，如果v _ c v ，a a ，则图g = ， 4 ) 称为图g 一，a ) 的子图( s u b g r a p h ) ，可简记为g g 。任给v c _ v ，以y 为顶 点集的g 的最大子图定义为：顶点集为，弧集为两个端点都在v 中的g 中所有弧的 集合。以v 为顶点集的g 的最大子图称为g 的由v 导出的子n q ( i n d u c e ds u b g r a p h ) ， 即如果y 量矿，爿一 ( 畸，v f ) c a iv j ，v f 矿) 。则图g = 彤，爿) 称为图g 一( v ，a ) 的由v 导出的子图( 简称顶点导出子图) ，记为g v 1 。类似的，可以定义弧子集a a 导出 的子图( 简称弧导出子图) c a 卜，爿) ，其中v 一p y i j v7 y ，使得( v ，y ) c a 或 ( p ，v ) c a 。由此可以看出，给定v 7 v ( 或a a ) ，图g 一缈，彳) 的导出子图是唯 一的a 例如，在图2 1 所示的图g 中，g 【“，k = ( 饥，如) ， 口。，a ： ) ，g 【 口。，a ，) 】一( v l ， 也，v ， ，如1 ，a 3 ) ，g 【 口l ，a 3 ，a 5