（计算机软件与理论专业论文）sdh网络中的多任务多播路由算法的研究与实现.pdf

攮簧 摘要 同步数字体系s d h ( s y n c h r o n o u sd i g i t a lh i e r a r c h y ) ，鼹指由若干s d h 网 元缀戏，势在竞终蠛者无线媒套上进行瓣步数据信息传辕、复翅、分攒魏交叉连 接的网络。我国现在使用的广电传输网络就采用了s d h 体系。 在数豢遁禳簸务疆益綮芷的今天，如翘巍现骞豹s d 网络设计戆够更好的餐l 用瞬络资源的管联方法，以减少数据传输代价并且提高通信可靠性具有着重要的 实际意义。 本文猩研究现有多播算法的熬础上，设计并且实现了一种针对多饭务问资源 分配、预髫涟题的赡发式多援路凑算法。该算法裁够在个s 渊网终中，为在一 定时间段中到达的多个多播任务搜索出满足一庇约束条件的路出，并且能够在多 个约京掺橼豹要求下，合瑷豹分熬蹲络资源，分担弼终受葑，以尽可辘的满足艨 有多播任务需求。 该算法戆特点包摆：不仅对一个多攒任务的潞由进稽基于多项约柬指标的优 化，而且能够有效的解决网络总体约束描标的优化。该算法结含使用遗传算法和 蚂蚁算法，使用遗传算法必蚂蚁葵法进行勰裳的指导，然后使用蚂蚁算法强大的 自反馈学习能力进一步优化指标，从而在解质量和收敛时间上获得了暾较理想的 缝粱。 【蕊鲁繁通。鼍多爨路壹算法：遗抟算法：鹅蚁算法：s 翻：资源分配 囊袁王照夫学工学鞭圭学位论文 a b s 譬l 落e 重 s d h ( s y n c h r o n o u sd i g i 七a 1h i e r a r c h y ) i sr e f e r sb yc e r t a i ns d hn e t m r k e l e 秘e n t s 主sc o 揩p o s e d ，a n de a r r i e so nt h es y n e 撑o n 童cd a 专氇主n t e 至l i g e n e e t r a n s m i s s i o no n 七h eo p t i c a lf i b e rd rt h ew i r e l e s s 扣e d i u m ，t u r n sr o u n dw i t h ， d i v i d e s主n s e r t sw i t 舞t h ee r o s se o n n e e t i o 拄n e t w o r k 。魏re o u n t r y s b r o a d c a s tt e l e v i s i o nt r a n s i s s i o nn e t w o r ki su s i n gt h es d hs y s t e m n o 吒 t 重ed 8 t ae o 燕瞳u n l e 8 t 主o ns e r v e ei sb u s yd 8 yb yd 8 y ，h ( 蹿t o 珏l a 薮e t h ee x i s t i n gs d hn e t w o r kd e s i g nt ou t i l i z en e t w o r kr e s o u r c e sb e t t e r ， r e d u e et 莪ed a t 8t r a n s m 主s s i o ne o s t ，a n de 疆，a n e ee o 嚣礴鞋n i e 8 专至o nr e 王氛港垂耄舔 h a v 静i m p o r 七a n tp r a c t i c a ls i g n i f i c a n c e 彳h i sa r t i e l eb a s e do 魏t h ee x i s t 主n g 拜黻l t 主e 鑫s t s8 l g 翻：i 毫赫，d e s 主，萌e d8 n 基 h a sr e a l i z e do n ek i n do ft h eh e u r i s t i ci n u l t i d u t i e sm u l t i c a s t ga l g o r i 吨量赫 腩i e hi nv i e wo ft h e 藉鞋j 王t i d u 专i e sr e s o 驻r c ed i s t r 童b u t 主。秘a n dr e s e r v e s 。 t h i sa l g o r i t h mc a nb eu s e di nas i ) hn e t w o r k ， s e a r c ht h er o u t ew h i c h 8 r r 主v ec e r t 8 主nr e s t r 8 主n te o n d 主t 主 nf o rt h e 臻a n y 矗醢t i e s 髯h i e 魏8 r r i v e 童n t h ec e r t a i nt i m e ，a n da l s oc a nd i s t r i b u t et h er e s c l 舢r c e sr e a s o n a b l ea n d s h a r et b e王o a d挂n d e rt h es p e e i f i cr e s t r a 量n ， 8 n ds a t i s f i e d 箍王王t h e m u l t i c a s t sd e m a n d s 羊h i sa 圭g o r 主t 稀c h a r 固i c 专e r i s t 主ei n e l u d e s ： 差te l 疆o p t 氲睡i z e s 魏。专o n l y o n es i n 9 1 ed u t y 8r o u t e ， b u ta l s ow h 0 1 en e t w o r k t h i sa l g o r i t h mu n i o i n i n o l u d e sg e n e t i e 鑫王g o r t 糙a n 纛t l e8 n ta l g o r l t 鞋鑫：u s 量魏gg e n e t 主e8 圭g o r i t 穗鞋 r e s u l ta s 七h ei n s t r u c t i o nf o rt h ei n i t i a lp e r i o do ft h ea n ta l g o r i t h m t h e ni tu s e st 蠢ea n ta 圭g 。r i t 瓤氇 f o r 攮主d 8 b l es e l f f e e d b 8 e k王e 拄r n i 秘g c a p a b i l i t yt oo p t i m i z et h ef u r t h e rt a r g e t t h u s ，i nt h es o l u t i o nq u a l i t y a n 蠢t h et i 船e ， t h i sa l g o r 主t 疆o b t 8 i n st h eq u i t ei d e a 王r e s 娃量t 。 【k e y 鞯o r d s 】耙l t 主a s tr o u t i n g 矗王g o r 主t 翮：g e n e 专i e 矗l g 。啦主t b 孤；是n ta l g 茁i t 糖l ： s d h ：r e s o u r c ed is t r i b u t i o n 1 l 一 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：日飘：二缈5 j ! ! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阕和借阅；学校可以公布论文的全部或部 。努黼瀑臻采用影印、缩印蠛其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲盈新虢幽垄魄型坐 1 1 引言 第1 章绪论 全国有线电视网是我国信息化的重要组成部分，在国家信息化建设中起着 r 分重要的作用。广电传输网是我国有线电视网的重要组成部分，通过广电传 输网( 特剐是国家干线网和省级传输网) 实现全国各地有线电视喇的互联互通。 广电传输网采用s d 和w d m 技术体制，主要是为广播电视节目和数据信息的传 送和交换提供高质量、大容量的传输通道。 为了保证广电传输网能够安全、可靠、高教地运行。必须要有功能强大的 网络管理系统支持。为了高效的使用网络资源，需要建立一种高效的管理系统。 使用成功高效的广电传输管理系统，可以有效的避免传输中反复进行话路群变 换而造成的建设成本和接人成本的提高、效率降低等情况，从而带来巨大的效 益。 s d h 传输网网管系统的个重要任务就是为每项任务开通光路及电路。而 丹通光电路的关键在于有效的路由算法尤其是在网络结构比较复杂的情况下 更是如此。用人工方式进行选路，在网络结构简单、光电路数目较少的情况下 还可以进行，但在网络结构复杂，光电路数量很大的情况下就不再适用1 。 而从可行性、费用以及复杂度e 综合考虑，提供有效的路由算法是提商网 络资源使用效率，提供更高质量服务的最有效的方法。改进路由算法，不需要 对现有硬件和网络设备进行改进，也不需要对现有的网络协议做太大改进就能 满足上述要求。因此有必要对路出算法进行研究和改进。 在实际应片j 中，一般要有效的利用网络资源，为此要求多播树的总费用摄 小，在网络中寻找费用最小的多播树问题足一个n p 完全问题，单任务的多播 路由己经有了很多成熟的算法。同时，在大型通信网络中，网管系统或网管员 经常要处理多个多播任务的资源申请，如果能解决同一网络对于多个多播任务 的资源分配和调度，无疑具有更为实际的意义。针对现有大型刚络的研究，实 现一种优秀的多任务多播路由算法，不仅能够提高网络资源利用率，降低运营 维护成本，还能够促使通信网络更好的为用户服务，提高用户的满意度。 维护成本，还能够促使通信网络更好的为用户服务，提高用户的满意度。 北京工业大学工学硕士学位论文 1 2 课题的必要性 s d h 脱胎于准同步数字体系p d h ，s d h 是一种集合了网络、软件、微电子和 光电子与一体的现代传输技术，s d h 技术将复用、线路传输和交换功能融合， 通过统一的网管系统进行自动化的管理。从上个世纪的8 0 年代，国外的电信设 备研究机构以及制造公司就已经开始着手研究s d h 技术并逐步开始开发相应的 s d h 设备和产品，其中，较为领先的公司有：阿尔卡特、朗讯、西门子和北电 通信等等，国内的公司和科研机构包括中兴公司等，也同样在进行着软硬件网 络设备的研究和开发。 广电传输骨干网是国家级的传输网络，覆盖面积广大，使用了多家公司的 设备和技术，同时，广电网络面临着向数字电视的转型，基于c a t v 线路的宽带 接入服务已经进入大规模实际应用阶段。充分利用现有广电传输网络资源的需 求越来越迫切。 这些需求使得s d h 网络的结构越来越复杂，网络需要传输的净负荷也越来 越大；s d h 网络可能承载的业务类型也将越来越多。这就要求网络能够提供快 速可靠的资源调度功能，同时能够充分的利用网络资源。 我国新建的干线光缆基本都采用了2 5 g b i t s s 甚至更高速的s d h 设备，这 就意味着传输网络一旦发生中断服务或者效率下降，都会带来巨大的损失。 令一方面，为了提高s d h 网络的可靠性和生存性，广电s d h 传输网是由若 干个s d h 环和链路相互连接构成，这种s d h 环不需要人为干涉，就可以凭借其 自身机能发现并且替代传输路由并重新建立通信链路，从而在极短时间内从故 障中恢复。3 。 由此可见，本项目的必要性主要有以下三个方面： 首先，我国的有线广播电视是党和国家的喉舌，广电传输网是保证党和政 府政令畅通的重要传输通道，在任何时候、任何情况下，都应该能保证传输信 号能够最迅速最准确的传到全国各地，因此，有必要建立广电网络综合网管系 统，实现对广电网络的综合管理，以保证传输畅通的目的。 其次，广电传输网络要能够在信息产业激烈的市场竞争中生存，必须要发 挥整体优势，有效合理利用网络资源，充分利用规模求效益。在全网范围内能 够充分利用网络资源开展各项综合信息服务业务，保证业务的服务质量，同时 降低传输、接入和运行成本，改善和简化网络操作，提高效率，使网络资源产 生预设的经济效益。 第三，未来广电传输网络的升级和发展需要高效的网络管理系统，现有网 络的重新配置( 包括新型网络设备的使用，网络拓扑结构的变化，网络容量的 扩充，业务量的扩大) 也会要求网络管理体现出一定的适应性。 嚣l 零绪论 综上掰述，开发广电传输系统，规划实现广电传输，是广电传输蚓络发麟 和啦务拓展的需要，可以加强广电传输网的运行维护功能，并疆好的发挥广电 传竣网熬饯势，实现对全嬲的统筹规划、集中管理和资源分配，提高鼹络传输 质量和资源利用率，保证网络管理的可持续发展”“。 另一方面，秀级现有已经建贼使用躲基础嬲络花费也犍j # 常巨大，因此毙 较现实的提高网络效率的是通过网络管瑗合理的给每项任务分配现有的网络资 源，通过对任务黔合理调度，尽瓤能的满足更多的业务串请，降低传输费用。 使用有效的路由算法，是现实有效的提高网络髋能的方法。 在s 蹦网络中，经常会出现需要将项任务镂输导多个节点的情况，采用 多播机制可以节约网络资源，同时，实际的网络管理中，多项任务可能会在一 段孵阉内依次至4 达，这些因素都擞大了踌由算法设计与实现的难度，本文尝试 了一种结合使用遗传算法和蚂蚁薄法求解在多任务多播路由的方法。 1 3 多播路由算法研究现状 虽然以提高网络资源分配效率为目的的带裔约束条件的路由算法研究已缀 进行了很长一段丑尊闯，但是在整个s d h 网络中实现带裔约束条件的路由还需要 迸一步的研究和诸多协议的发展。 1 在早期通信网络中，只存在一种业务类型，既尽力丽为的业务。网络传 输管理系统简单的按照先采先服务的原刚对业务迸行调度和资源分配。随着渡 务的发展釉震求的不断增长，广电传输网络所承载的工作越来越繁重，传统的 s d h 网络缺乏有效的资源和流量管理的弱点已经盟现出来8 。 在网络管理的实际应用中，为业务建立优化的路出是一种满足对苛刻的任 务调度和资源分配要求的有效方法。这蕻中包插单播路由和多播路由，多播路 出的情况在实际应用中比较常见，并且，在一定意义上，单播路由是多播路内 的一种特殊情况。 2 单播路由算法研究已经发展出很多优秀的算法，但是在多播路幽算法研 究上，存程很多问题等待解决。由予多播组有多个目的节点，因此多播路由也 要比单播路由复杂很多。 首先怒多播路由算法的计算花费和解质量，这两个关系戮髯法性能的最羹 要的指标，尚未有一种算法能够达到人们的预期目标。这也是本课题研究的主 要内容。除此之外，还有一些对多播算法有着羹要影响的因素需要深入研究。 现在黹遍采用使用基于约束的路由算法设计来解决实际应用中的多播路幽 问题，当路由选择协议需溪综合的考虑各种限制时，采用单纯的数学推导，求 解将会非常困难，求解的过程也会非常漫长。此时不得不采用启发式的推理方 l 衷王照大学工学矮士学毽论文 式，扶恧可以在较低鲍诗冀代馀下获锝接迓最貔熬网终路由计算结果f 6 ，。7 ，8 】。 目前多半的多播算法倾向于将多播协议建立在现存的标准的基于单播的路 圭协议基戳上，这样镞约好处善先是能够有效魏减少多攫协议的复杂 垒，趣快 多播的部署，并且，以现有的基于单播的路由协议为基础，能将使用的多播协 议对现存网络结构鼹影响降低。虫予基予约束的多援路痰问题愁个n p 完全 问题，并且目前较好的解决方法基本都是采用启发式算法，但是由于每种算法 追求静曩的不同，终隶条馋靛参数和指标瞧各不鞠困，困茂每静算法之闼的差 异是较大的。每种簿法在自己所适用的方面是优秀的，但是对一些指标计算能 力熬提裹裁懑味着牺牲另癸一些搬拣约诗簿毙力。髫翦，寻找一个平鬻点，寻 找一个在多种问题上表现都优良的算法也是一个静价值的研究方向。 浚源熬分配与羧留在露向连接豹网终管理中舆有重赘意义，魏果网络中只 有一项任务，那么它可以持续的占用任何它需要的网络资源，而如果网络中存 在多矮任务，势且这些任务可能在一段时阀内陆续到达劳发出资源申请。藉么 在对当前的任务进行资源分配的时候，需骚总体的考虑其他任务的情况，例如， 分醚给这项任务资源戳后，后续到达的铿务能够获缛足够的资源。 资源预留是通信网络错能化中一项重要的组成部分，对通信网络资源的预 塑主要有廷转手段，第一是遁过遥信协议支持的信令机剁，还有就是通过路由 技术。例如在以波长路由为基础的波分复用( w d m ) 光网络中使用的是波长预 骜技术，露摆p 溺络孛嫒建r s v p 来实现资源颈留。 王。4 单播路由算法麓介 举播算法是多播算法的一个特例，现在很多多播算法都是建立在经典的单 播算法之上。 1 4 单播路由算法分类 翠播路囱选择舞法校舔瓣元之游交换倍怠翡方式帮静类不阏，可戳有悉耱 不同的类型。第一种是距离向量算法( d i s t a n c ev e c t o r ) ，谯这类算法中，相邻节 熹之闯交换达到不鞫胃舔静距离参数“蠢蹩”，这耱算法露最终浚敛餮菜种饶纯 状态。第二种算法则是网络中任意节点均需要了解整个网络的链路状态拓扑， 只有酱网络中的链貉拓矜发生交稼的辩候彳进行信息交换。信惑交换粟蠲洪泛 传输方式，链路状态发生变化的节点将相关信息传送给网络中所有其他节点， 褶瘫黼络串箕毡节点也只接受这个信息酶拷灭拭埔l 。 1 距离向量算法 阁链潞状态算法阮较，距离蠢篷算法遗程麓擎，餐是链貉状态算法麓收毁 第l 蕈绪论 速发要北躐离向羹算法快，尤其在整个耀终拓扑由于节点或链路的增加和失效 或者链路状态发生更改的时候。链路状态算法采用的洪泛传输方式将相关信息 绩埝给网终中所有节点，这里算法的收敛对翔等于网终拓扑发生变化时更掰联 有节点状态的间隔周期设置。 采焉基予距离自量的鼹由算法在霹终增大时，会出现网络节点之阍交换的 信息急剧增长，栩应信息交换的时间也会延长的情况，并且导致算法收敛的时 闯大大增麴。为了简化冀法，基于距离向量的鼹童算法采用跳数两不是可搬权 的链路参数作为算法度量参数。使用最小跳数的路由算法将会在某些网络拓扑 结构中缛爨些瘸态豹路出选择呲2 ，1 引。 2 基于约束的洪泛式路由选择算法 采用缀济指孝承域传播延时作为参数进幸亍最小代侩或最短路经的链路状态算 法并不能究全满足通信过程对予约束指标集合的要求，这些要求可能包括丢必 搴参数或跫迟抖动参数。能够满足这些鬻求豹路由算法成为基予约束的路由选 择( c o n s t r a i n t b a s e dr o u t i n g ) ，这里的约束可以是各种约束参数组合、带宽要 求、是否采用或避免特定传竣信遵以及其拖楣关茨略p i 。 1 。4 2 单播路由算法实现 撮短路径的“艘短”可以引申为多葶巾制约关系，如对闻等。在面向连接的 协议中，溺最佳路径有空余带宽时，新的业务将获得最佳路径；如果簸佳路径 没谢空余带宽，网络会给业务分配次优鼹由，如果不存在次优路由，网络将搬 绝新业务请求。 髫兹，主要有三秭被广泛使明的单播貉由算法： ( 1 ) 删m s 蚍算法 d i j i k 8 妇算法是由e d s g e rd 珏i k s r a 提出的一种最短路径算法，这种算法是 一种典型的贪婪算法。根据文献【l o 】，d i j 像s t m 算法中的每次循环都会褥到一个 点的最短路径。因此，如果图中存在n 个节点，求彳导源点到其他所有点的最短 路径的d i i 搬s 姐算法的时间复杂腹为：o 心2 ) ；使用堆栈递归可以将时闯复杂度 降低为o ( ( n + 1 ) l o g ( n ) ) 。 f 2 懈e l l m a n f o r d 冀法 b e l l m a n - f o r d 算法逶用于以最大跳数为约束条件豹最短路径计算。 b e l h n a l l f o r d 的基本思路如下：从已经给定的源点找琏；一条最短路径，这条袋 短路径从媛多只含一跳的链路中选择出来，然聪接着寻找最多只含两跳的最短 路径，依此类推，直到找到所有路径。 如果转e l l 翔a n f o r d 算法采用与d i i i k s 妇算法相同的剪枝操作，这两种算法 j 衷工照夫学t 学磺学位论文 可以获褥摆阏静计算结果。这嵇算法可以从根节点向钤接进直到达到所蠢节点， 在分布式计算环境中，这种算法可以作为距离向赞路由选择的操作算法，其时 闻复杂度为o ( m l ) ，m 为媛短路经中最大粒链路数耳，l 是网络中的链鼹数耳， 由于： m n 1 ) 且心一1 ) l n ( n 1 ) 所以b e l l m a n - f o r d 算法的复杂度在o ( n 2 ) 和0 ( n 3 ) 之间。具体要取决于网络 的穗璇程度。 ( 3 ) f l o y d 算法 f l 姆d 提感另一秘计算缀短路径约思鼹，f l o y d 算法的目的愚求鼹网络中每 一对顶点之间的最短距离，采用的方式是在源点和终点之间加入中问节点。 初始化豹对候，黄先诗簿不经：i 篷中间节点的所蠢节点i 秘节点 之间嬲距离， 如果i j 之问没有直接连接路径，则设为无穷大。然后循环计算在i 到i 的最短路 径上添翔一个节点k 之爱的最短鼹经，添烟一个中阉节点有两秽可能，一静是 最短路径长度变短，那么k 将被加入到中间节点中，如聚k 不在最短路径中， 那么最短黢经长度嬲没有交毒匕。 f l o y d 算法需要三层循环，总的时问复杂度是o ( n 3 ) 。 1 4 3 单播路由算法比较 以上三种最短路径算法，都是通过迭代完成运算的，但是每种算法的差剐 就是它们迭代豹对象不棚同。d i j i k s 姐算法是对路经豹长发进行迭代。 b e l l m a n f o r d 算法是通过对网络中的链路数目进行迭代。f l o y d 算法是对路径的 中阕节点进行迭代。 如果在通信网络中，所有的节点均具备网络拓扑和网络链路权重信息，那 么，遵信网终中的熙有节点就都昊备了进行最短距离路由算法的能力，每个节 点都可能建立、维护一个自己的路由表，这个路由表至少包含节点自身到网络 其他节点的最短路绞扩展树。在这孝申情况下，如德在节点中传递这些路出表是 一个重要的课题。路由表的传递，一方面应该要在短时间、短周期内完成，另 一方箍是要保证所有节点都鑫g 安金的接收别媚互的路由表。在一些网络拓扑复 杂、链路状况变化十分频繁的通信网络中，由于路由算法不能在短时间内收敛， 往往造成路豳环路状况的浅现，从蕊导致大量数据丢失，网络性能下降，效率 低下。在2 0 世纪9 0 年代以前，大型互联阔的分布式路由协议计算的收敛时闯 会达到几分镩。现在存在种处理思路，就是在全局计算完成之后，每个节 点只需要建立一个推进表以反映最短路径扩展树上的部分连接状态，这种方法 保诞了国际互联网在现在这种爆炸式的快速增长下仍然熊够保诞正常工作。 箨l 章绪论 1 。s 多撬路毒冀法篙会 多撵( 攥疆 i c 8 或一m c ) 是霹络申飙一个源点逡多个疆兹节点发送绥怠兹畿 播方式，参与多播的多个目的节点组成个多擗组。多播的主要目的是使得信 源只发送次数搌，嚣痿骞戆曩熬节点郝爱及融、嚣步鳆接收戮数据。霹摹撵 相比，使用多播方式可以有效的减少网络中的传输的数据总量，减少对网络资 源熬占爱，扶瑟酶低鼹络运营成本h “。辱单摇援零秘毙，源节点有摆耀熬数攒 需要传输绘多个目的节点的时候，使用单播建立多条从源节点到目的节点一对 一熬链路联占爰憝弱终姿源是魏麓髫豹肇点熬数强增多嚣增长戆，可以想象， 有相当多的网络资源在这些链路中被重篾占用，造成浪费。丽采用多播方式以 蜃，在这黧滠本被重复馒愆夔链路上，只转递一次数据，这攒将会极大戆避免 对网络带宽的浪费使用。 嚣翦，针对各耪不羁戆基予终寒豹多撬路裹溜题，岂经提如了多季孛耀应豹 路由算法。 1 5 1 多播算法分类 按照实现方式，多播路由算法可以分为集中式源路由和分布式路由这两大 类黧【。 1 源路由型多播路由具有的按同特征是网络中每个节点都维持一张有关熬 令璃终全鼹链路状态的图，透过这些状态霪，滋鼹由型多播路蠹算法可盼筠罄 快速的建立路由，而且在求解过程中，节点之间不需要交换任何信息，使用预 先存在予状态表中妁数据就可以宠戒求解。困就，源路出型多播路由冀法易予 实施和维护，响应快速，对解的评估和检查也比较容易。源路由型多播路由算 法共强存在约阂题是，虫予算法宠全壤赖每个节点的连接状态表，因此状态袭 必须时常更新，更新频率的设定就成为了一个问题，过于频繁的更新会给网络 豢寒巨大媳受载，冀一方蠢，如攫更薪不够频繁，烬黝蔟量会降低。网终本囊 的状态也会造成状态表的刷新延时。 2 。分蠢式路国算法在接收到黪壶请求之后，会依据鼹络中鬈个郝分的舄郝 状态信息，在多个方向e 并行的搜索多个可行路径，由于求解的方向增多了， 分蠢式蹉嶷算法弱成功率较之源鼹出算法逛增娥了。分瘫式路囱算法不需要在 各个节点都维护一张链接状态表，并且驻而易见的，分布式路由算法的复杂胰 要逡远大予源路蠢算法，求鳃对阕也会有一定延迟。 分布式多播路由算法按照具体求解方式，又可以分为如下几个类剐l 4 l ： ( 1 ) 洪拳方戏：源节点将缤怠囱爨有可悲的路径发送，所有可能到达的节 l 亲王照大学工学颁圭学短论文 点都燎受到这些信愚著将臻息南其拖节点转发，但是只商目的节点会她理这些 信息，最终信息扩散到整个网络，所有的目的节点也都受到了发给他们的信息。 在小墼网络中，洪水方式楚一神直接麓单的多播路出算法，但是在具衣一定规 模的网络中，这种算法会非常浪费网络资源，造成网络瘫痪。 ( 2 ) 分别寻址方式：分裂寻墩方式是蠼早的翅于分缀遵售嬲络的多攫路由 方式，源节点分别同目的节点建立单播路由，这实际上仍旧是单播路由。存在 这严重豹路由浪费弱时延闷题。 ( 3 ) 基于生成树的转发方式：算法构造一棵从源节点出发，覆盖所有目的 节点的多播路由树，源点只嚣发邀一次数据，然艨通过多援树转达到艇有耳的 节点，这种算法具有的最大优点就是它尽可能的共享资源，节约资源。 比较上述三静方式可以发现，基于生成撼的转发方式是解决网络多攫遢信 的最好方法，因此，求解多播路由问题实际上就是要发现特定的多播树，最小 生成糖。 除了上述三种方法，用遗传算法和蚂蚁算法解决基于约束的路由问题也是 薪i 匿广泛馒赐麴求缤方式，遗传冀法( g 雌e t i ea l g o 潮戤s ) 是搀通过借鉴大自 然的生物进化规律演化而来的一类随机化搜索算法。1 9 7 5 年，内h o i l a n d 教授 善先提出。1 9 9 5 年，e s b e n s e n 应用遗传算法有效的解决了s t e i n e r 树闽题之后， 使用遗传算法求解基于约荣的路由问题逐渐成为主要的求解方向；同样是上个 世纪9 0 年代，通过对大自然中动物鲍一些群体行为进彳亍研究之鼷，人们提出了 模仿动物某魑行为特征的“仿生”算法的理论，其中，对蚂蚁社群觅食行为仿 生的蚂蚁算法因其本身优努的性能，以及适用阅题范围的广泛聪获彳寻了人们的 关注，因而也被用于解决基于约束的路由问题的研究中，并且获得了良好的效 果，实践证镑，使用鳃蚁算法在船决浚类阏题的过程中，不仅能够快速黝求解， 并且舆有良好的扩充性。 1 5 2 最小生成树算法 对于多播路由问题，一般需要建立费用最小的多播树，因此，多播路由问 题往往演变为寻找满足约柬条件的最小多援树问题。丽建立这样的最小多播树， 又经常是从建立最小生成树开始1 电7 ，引。 最小生成树的定义是覆盖所有节点并凰加权值最小的树。 在一个给定的凭向图g _ ( v ，e ) 中，( u ，v ) 表示连接顶点1 l 和顶点v 的边 f 封，v 固。缓辍v ) 代表这条边翦投霆，若存在t 为e 熬子集( ，互) ，著且e 为无循环图，使得 第l 章绪论 w ( r ) = ：w 红，v ) ( 1 1 ) ( 添 豹w ( n 最小，则此t 为g 的最小生成树。 有很多种方法可以求解最小，毫成树，例如采用同d i j k s 仃a 算法的策略相似 匏艇m 算法。p 纛激算法豹基本步骧魏下： 1 ，任选一个顶点作为一子树的根节点。 2 。将掰骞戆边依照投重教入优先权序强。 3 在序列中爵找能与子树中顶点连接的最轻边并加入之。 4 重笺蔻一步骤壹裂鹱奏璜点学怠禽在戴予掇中。 妇1 l s k a l 算法是和p r i m 算法同样经典的最小生成树算法，i ：m s k a j 算法的步 骤皴下： 1 初始化正在生成的树a 为空集合并建立i v l 棵树，每棵树包含图的一个节 点。 2 根据每条边的权值按照递增次序进行排序。 3 怼镣条边蕊v ) 诗冀獒端点u 积v 是否属予目一颞树。热鬃不属予阂一颞 树，则将( u ，v ) 加入，将u 和v 分别所属的子树合并；如果属于同一颗树，则放 弃( u ) ，嚣必这秽情况下憋毽v ) 糖入会弓| 起回路。 4 重簸前一步直到所有顶点皆包含在a 中。 p 曩m 算法与融燃k a l 葵法都爝予贪婪算法，遁霉邦馒爆二叉糖结构，封阌复 杂度为o ( e l g v ) 。若使用壤小堆有序树，p r i m 算法可加速至o ( e + v l g v ) 。 最小生残撬算法著不辘壹接髑子求熬多接路出闽题，毽是使用最小生成撼 算法可以j c 寸多播路由算法的解进行优化。 1 5 3s t e in e r 树算法 在各种建立费用最小的多播树的方法中，最优s t e i n e r 树的建立费用是最小 豹，莲嚣s e i n e r 辫毅认为是实现多援通信豹最始方法之一。如果多播树敷目的 节点和源节点涵盏了图中所有的点，那么s t e i n c r 树问题就转化为最小生成树问 题，最短路径算法也是s 蟛妇f 挝靛一个特铡，当疆标点只有一个豹时候，s 托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 树算法。 识 基定义无彝连逶髫g = v ，秘，冬，v ) 表示连接壤点驻秘矮点v 鲍透 和多 嚣2 荤餐源预整 播树界限( 溉e e o n s 细i n t ) 。其中链路界限规定丁对链路的使用，铡如，在姻络 中，使用的多播路由应该保证在矮经过的每一条链路上都保留有一定的链路或 其他瓷源以供其他任务使用。路径界限贝 l 对整个鼹径聪端提出约束。生成树界 限规定了熬个多播树都必须满足这些约柬。 在实隧使用中，对上述三静舆限要求可以提蹬两季申约束，最优化约束或绘 定界限约柬。用户对网络提出的各种需求通过缀合这些约束得以表达。 当约束捧为输入数据传递绘冀法之聪，从表现上来看，一个优秀的路由爨 法成该能满足如下几个要求：算法应该能够动态的确定路由；算法应该能够在 全鼹范围内优化资源使用效率，平衡网络负载；求得的路由对全局资源的影嘲 应该尽可能小。 2 4 对资源的预先分配 当一项新的业务在某个网元国现的时候，如栗系统处于忙状态，那么系统 应该提供一个等待区域或等待机制来暂融客纳不及时褥到服务的业务。在一 些约束标椎中，不仅要求当前的任务能够满足约束，避兔无约策的“尽力而为” 服务方式，还有可能要求系统在为一段时间内依次到达多项任务都做好资源调 度。 在这种状况下，要考虑的一个重要因素是传输网络中的多播情况。在网终 中，一个倍元往往会出现多个任务汇聚的情况，不论这个信元怒源点还是汇点， 都会引起阻塞。在这种模型中，每项作她的持续时划是”个重要参数。 面向连接的网络协议可以根据当前通信网络的状态选择路由以满足新的照 务，但是如果压渤连接的网络通信会持续很长肘问，面向连接网络的路出算法 有两能变褥次优，甚至网络不能满足新任务的资源分配请求，也就是出现了隘 塞。 如下图所示： 襄衷王妓大学丁学磺主学位论文 图2 2 网络资源调度 f i g2 2n e t w o r kr e s o u ! | c e s 蠢i s p a t c h 在图2 2 中，心c d e 魁5 个能力相同的网元，每两个网元之问的链路资源 容量也都禳等为l o 个单位，俊设鞴在存3 个任务，每个经务需要的链辩都是4 个单位，起点都是a ，终点都是d ，直观的来看，a e d 无疑相较a b c d 这条路蠢要短，僵是霞为每条链路静容量都怒1 0 令单位，掰瑷a e d 这条路由只挠容纳两条需要4 个单位的业务，第三项业务不得不使用a b c d 这条路国。 如果使用a e d 路由的两项业务在占用了相当长的时间后，有一项业务 完成，并虽释放了资源，那么现在在a 一嚣d 速祭路由上，存在6 个擎位静空 余链路资源，但是由于网络不支持链路的遵建，之前选择了a b c d 路由 的照务并不能改途邈条路国。魏采这个时候，网络突然藏受了2 个薪豁需要带 宽为4 个单位，起点为b ，终点为c 的业务，由于这时b c 问已经占用了4 个单位静资源，剐一项薪静监务不得不被獾绝。 对于这种情况，可能采用的解决方案是在保证相对的不中断数据传送的情 况下，定期篷新计箨持续辩闻较长静连接遗程酶路由方法。餐蔻这种方法会导 致连接网络的路由算法变褥非常复杂，并可能中断网络掇供的业务。 尧了避免这释中断两络造成盼澎稚，代侩最，l 、靛辩浚方法藏是瑟瓷源逶嚣 预留，在满足当前业务的同时，为之后的业务留下一些资源。 资源颈留系统一般包捂两个缀成部分：预约稻确认。薪到照务首先应该要 求预定通信网络中的特定资源。然后调度系统将根据资源预约的一系列的特定 的约束条件和有关参数集合来确寇使爱穗释策略寒裙痤确定预终。两终楚于不 同的资源占用情况时，例如高负载的忙时和低负载的闲时，所采用的分配策略 可麓不同，在菜些情况下，系统可能对未来一个辩阉段黥盈务避行超鬏耱资源 预定，因为某些业务在等待一段时间之后可能会撤销申请，这样，实现精确的 超额预定裁会傈证爨源的最大翻藤，不致浪费。系统不彼对鲎务煞开始进行预 第2 覃疑源蘩甓 定，同样擞会关注规定业务兹终止时闻，如果项业务到达了其最大服务时翔 仍旧没有究成全部数据传送或者资源使用的话，系统将会强行结束这工雨业务以 回收资源耀予分瓢给等待队列孛其她的数务。 在网络资源的管理和分配中。对于般务请求，系统需要依次进行的步骤如 下： ( 1 ) 根据网络拓扑和节点提供的信息，将任务要求的转换为节点和链路二 豹投嬗描述。 ( 2 ) 使用算法求得路由。 ( 3 ) 对网终资源进行分配。 2 。s 本章小结 本章蒜眼于通信网终资源的分类以及约束要求，先分析了不同种类的资源 的特定，然后分析了对这些资源的约束分类，最后列举了s d 随络中比较重簧 的几耪资源，以及这些资源上的约束条件。 第3 章遗传算法 在启发式的多播路由算