维普资讯 http://www.cqvip.com
７Ｏ 交通与计算机 ２００６年第１期 第２４卷（总第１２８期） 多ＱｏＳ约束的动态多播路由算法＊ 许红梅许毅 （武汉职业技术学院 武汉４３００７０） （武汉理工大学 武汉４３００７３） 摘要对具有延迟、带宽和低代价等多ＱｏＳ约束的多播路由算法进行研讨，描述了一种适 应于研究ＱｏＳ多播路由的网络模型，提出一种具有多ＱｏＳ约束的动态多播路由算法 （ＤＭＲＡＱ０Ｓ），ＤＭＲＡＱｏＳ试图有效地减少生成多ＱｏＳ约束的多播树的开销，使多播组成员能动 态地加入／退出多播会晤，且不干扰现有的多播树。仿真实验结果表明，与ＹＡＭ和ＱｏＳＭＩＣ比较， ＤＭＲＡＱｏＳ具有较小的延时和较少的代价。 关键词动态多播路由；算法；多ＱｏＳ约束 中图分类号：ＴＰ３９３ 文献标识码：Ａ Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｄｉｓｃｕｓｓｅｓ ｔｈｅ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ＱｏＳ ｃｏｎｓｔｒａｉｎｔｓ， ｗｈｉｃｈ ｍａｙ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｄｅｌａｙ，ｂａｎｄｗｉｄｔｈ ａｎｄ ＣＯＳｔ ｍｅｔｒｉｃｓ，ａｎｄ ｄｅｓｃｒｉｂｅｓ ａ ｎｅｔｗｏｒｋ ｍｏｄｅｌ ｆｏｒ ｒｅｓｅａｒｃｈｉｎｇ ｔｈｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ．Ｉｔ ｐｒｅｓｅｎｔｓ ａ ｄｙｎａｍｉｃ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ＱｏＳ ｃｏｎｓｔｒａｉｎｔｓ（ＤＭＲＡＱｏＳ）．Ｔｈｅ ＤＭＲＡＱｏＳ ａｔｔｅｍｐｔｓ ｔｏ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｒｅｄｕｃｅ ｔｈｅ ｏｖｅｒｈｅａｄ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ａ ｍｕｌｔｉｃａｓｔ ｔｒｅｅ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ＱｏＳ ｃｏｎｓｔｒａｉｎｔｓ．Ｉｎ ＤＭＲＡＱｏＳ，ａ ｍｕｌｔｉｃａｓｔ ｇｒｏｕｐ ｍｅｍｂｅｒ ｃａｎ ｊｏｉｎ ｏｒ ｌｅａｖｅ ａ ｍｕｌｔｉｃａｓｔ ｓｅｓｓｉｏｎ ｄｙｎａｍｉｃａｌｌｙ，ｗｈｉｃｈ ｓｈｏｕｌｄ ｎｏｔ ｄｉｓｒｕｐｔ ｔｈｅ ｍｕｌｔｉｃａｓｔ ｔｒｅｅ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ＤＭＲＡＱｏＳ ｉｓ ｌｅｓｓ ｉｎ ｄｅｌａｙ ａｎｄ ｃｏｓｔ ｔｈａｎ ＹＡＭ ａｎｄ ＱｏＳ ＭＩＣ． Ｋｅｙ ｗｏｒｄｓ：ｄｙｎａｍｉｃ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ；ａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉｐｌｅ ＱｏＳ ｃｏｎｓｔｒａｉｎｔｓ ０引 言 １ 网络模型 多播路由的目标是找到一种算法或策略，在 一般的ＱｏＳ多播路由问题包含多个约束条 给定的网络和多播需求的情况下，寻求一种链路 件，如延时、延时抖动、包丢失率、带宽和代价等。 连接方式，使网络资源能得到有效利用。许多学者 如果在设计具体的路由算法时考虑所有因素，算 已提出了一些支持ＱｏＳ的动态组播路由算法，这 法势必太复杂而不能实际应用，需结合实际情况 类算法有较好的分布性，便于实现。但普遍存在控 对其简化。在讨论的路由问题中，由于节点和链路 制信令开销和结点加入时延大的问题，可扩展性 具有等价性，为了简化，只考虑链路而不考虑结点 不好。分析这类算法可以发现，造成可扩展性不好 的特性，下面给出ＱｏＳ多播路由模型［１］。 的根本原因在于对可行的接人路径的盲目搜索。 就多播路由而论，一个网络可表示成一个加 笔者对延迟、带宽及低代价ＱｏＳ多播路由问题进 权图Ｇ＝（ ，Ｅ）。式中： 为节点集；Ｅ为连接节点 行了研讨，提出一种多约束Ｑｏｓ动态多播路由算 的通信链路集合。ｌ ｌ和ｌＥ１分别为该网络中的节 法（ＤＭＲＡＱｏＳ），避免以往算法中大部分的盲目 点数和链路数。不失一般性，该类网络中一对节点 路径搜索。该算法仅要求网络的局部状态信息，而 之间最多只有一条链路，链路旁的参数可用于描 不要求维护全局网络状态信息，ＤＭＲＡＱｏＳ算法 述该链路当前的状态。设Ｐ（ｓ， ）为从源节点ｓ到端 能有效地减少构造一棵具有多ＱｏＳ约束多播树 节点ｔ的路径，Ｔ（ｓ，Ｍ）为多播树。Ｓ∈Ｖ为一棵多 的开销，从而缩短了结点加入时延。在ＤＭＲＡＱｏＳ 播树的源节点，Ｍ ｛ 一｛Ｓ））为该多播树的端节 算法中，多播组成员能动态地加入／退出一个多播 点或叶节点的集。设Ｒ 为正实数集，对于任意一 会晤，该算法不必求解汇聚点，适应于多播节点的 链路ｅ∈Ｅ，可定义某些ＱｏＳ特征值（ｍｅｔｒｉｃｓ）；延 动态变化，是一种快速动态的多播路由算法。 迟函数ｄｅｌａｙ（Ｐ）；Ｅ—Ｒ ，代价函数ｃｏｓｔ（ ）：Ｅ— 收稿日期ｔ２００５－０９－０４ Ｒ ，带宽函数ｂａｎｄｗｉｄｔｈ（Ｐ）：Ｅ—Ｒ ，则有满足带 ＊国家自然科学基金资助项目（批准号：６０１７２０３５） 宽、延迟和代价最小的ＱｏＳ多播路由问题，其主 维普资讯 http://www.cqvip.com
多ＱｏＳ约束的动态多播路由算法——许红梅许教 要涉及以下元素；多播源节点Ｓ∈Ｖ，多播端节点 集Ｍ ｛Ｖ一｛Ｓ）），链路的延迟函数ｄｅｌａｙ（・）∈ Ｒ＋，代价函数ｃｏｓｔ（・）∈Ｒ 和带宽函数 ｂａｎｄｗｉｄｔｈ．（・）∈Ｒ ，寻找一棵多播树Ｔ（ｓ，Ｍ）满 足 延迟约束：ｄｅｌａｙ（ｐ（ｓ， ））≤Ｄ （１） 带宽约束：ｂａｎｄｗｉｄｔｈ（声（ ， ））≥Ｂ （２） 代价约束：在所有满足式（１），（２）条件的多播 中， ＣＯＳｔ（ （ｓ，Ｍ））一（ｍｉｎ） （３） 式（３）描述了优化目标：组播树的代价应达到 最小，式（１）、（２）描述了实时业务的ＱｏＳ要求。 Ｄ…为实时业务所要求延时的上限值；Ｂ 为业务 所需求带宽的下限；Ｐ （ｓ， ）为图Ｇ中从源节点Ｓ 经多播树到端节点ｔ的路径。 ２ ＤＭＲＡＱｏＳ算法 在动态路由中，网络的拓扑结构、链路状态 （时延、剩余带宽等）以及多播成员是动态变化的， 动态多播路由强调多播成员的自由加入和离开， 并且这些活动不能对多播产生不良的影响Ｌ２］。对 于一个动态的多播群组Ｇ，设Ｓ为多播源点（ ∈Ｇ ∈ ），假设Ｔ （ ）是源自 的覆盖Ｇ中所有成员的 多播树集，支持ＱｏＳ的动态多播路由的目标是： 结点自由加入和离开多播群组Ｇ的过程中，寻找 Ｔ （ｓ）中保证多播用户的ＱｏＳ需求（如最小带宽， 时延）而且多播树代价最小的一棵多播树，在 ＤＭＲＡＱｏＳ中，路由器或网络节点需保存一些特 定的信息在路由表中。 ＤＭＲＡＱｏＳ是一种满足带宽和时延约束的 算法，首先选择多播信源构成初始多播树，删除链 路中所有不满足带宽要求的链路，得到一个新的 网络拓扑图；其次用Ｄｉｊｋｓｔｒａ算法求最短路径树， 从加权图去除时延不满足约束多播节点，再求剩 余多播节点的最短路径树；然后根据最短路径树 的最短一条路径为初始多播树，将尚未连到多播 树的多播节点每次通过最短路径连到树上的任一 节点（这些节点是一些中间节点，源节点到中问节 点的最短路径加上中间节点到目的节点的最短路 径构成了源到目的节点的路径）。通过比较找出最 理想的路径并添加到树上，若通过树上的节点没 有找到合适的路径，则扩大中间节点的范围，把整 个网络的节点当作中间节点，再寻找最合适的路 径，当所有多播节点都添加上去，算法即终止。根 据多播成员的连接请求或退出请求，依照加入和 退出操作规则，动态地建立或切断连接。多播树的 形成过程就是多播成员的动态加入和退出过程， ＤＭＲＡＱｏＳ由加入请求、加入操作及退出操作３ 部分组成。 加入请求操作由申请加入多播的网络节点完 成，当Ｇ中某节点ｔ申请加入标识号为耐的多播 树 时，先使用ＤＭＲＡＱｏＳ算法找出由ｔ到多播 树 的路径Ｐ，然后沿尸及 向源节点请求加入 多播组。 加入操作，以Ｇ中任意节点ｕ为例，设此时多 播子树为Ｔ ， 到 的路由路径为Ｐ（ ，ｕ），Ｐ（ ，ｕ） 与 的连接点为 ，Ｔ 中Ｓ到 的路由路径为尸 ． （ ， ）。加入操作的过程即是节点连接多播子树的 过程，ＤＭＲＡＱｏＳ的加入过程的伪代码如下。 １）初始化 Ｆｏｒ Ｖ ｄＥＶ ｄｏ；／／ＤＭＲＡＱｏＳ（Ｇ， ，ｕ） ｉｆ Ｂ（Ｐ（ｓ， ））＜Ｂ ｔｈｅｎ ｄｅｌｅｔｅ链路（ ， ） ｉｆ ｌｄｅｌａｙ（Ｐ（ｓ， ））＞Ｄ ｔｈｅｎ ｄｅｌｅｔｅ链路（ｓ， ） ２）加入操作控制循环设置。 Ｌ＝Ｔｒｕｅ；以信源或当前多播树为初始多播树Ｔｉｄ ｗｈｉｌｅ Ｌ＝Ｔｒｕｅ ｄｏ；／／Ｌ为逻辑变量，用于控制循环 弹出具有最小费用路径Ｐ（ ， ）节点 ｉｆ（ｄｅｌａｙ（Ｐ（ ， ））＞Ｄ…ｔｈｅｎ ｄｅｌｅｔｅ加入请求消 息 ｅｌｓｅ计算每个与 相邻如的时延 ｉｆ Ｐ（ ， ）＋Ｐ（ｖｋ， ）是所有 相邻如路径满足最小 费用的约束条件 ｔｈｅｎ户 ］＝ ｉｆ 的状态为Ｅｓｔａｂｌｉｓｈ ｔｈｅｎ计算ｄｅｌａｙ（Ｐ＇ｒ（ｓ，口★）） ｅｌｓｅ发出加入请求消息 退出操作由退出请求、删除请求及链路删除３ 部分组成。退出操作时，节点ｄ先向源节点Ｓ发送 退出请求，Ｓ接收退出请求即从路由表中删除节 点ｄ。如果ｄ不是 的叶节点，ｄ先释放先前分配 的资源，然后沿路径Ｐ （ ， ）向其父节点，发送链 路删除消息Ｄｅｌｅｔｅ，父节点，接收到删除消息后， 如果，仅是ｄ的中继节点，删除链路（，， ）即可， 否则删除链路（，， ）后，继续沿路径Ｐ （ ， ）向父 节点发送删除消息。对于退出操作，非叶子节点的 节点退出时，多播树拓扑不作任何改变。叶子节 点，退出时，移去路径为Ｐ （，， ），新的多播树Ｔｉｄ ＝ 一Ｐ （，， ），其中／为ｄ在Ｔ ｄ上的断开节点。 维普资讯 http://www.cqvip.com
３性能分析 定理１ ＤＭＲＡＱｏＳ算法所构造的组播树 ＴＤＭＲＡＱｏＳ定能满足带宽和延时的要求。 证明 定理１等价于（１）对于Ｖ Ｐ（ ） ＴＤＭＲＡＱｏｓ，有ｂａｎｄｗｉｄｔｈ（户（ｓ， ））≥Ｂ ｉ ；（２）对于 Ｖ尸（ｓ， ） ＴＤＭＲＡＱＯｓ，ｄｅｌａｙ（户（ ，口））≤Ｄ一 证明（１） 通过ＤＭＲＡＱｏＳ算法知道，算法 是依据满足多播树的约束条件计算Ｄｅｌａｙ，对于 Ｖ ，￡，∈Ｖ，ｂａｎｄｗｉｄｔｈ（Ｐ（ ， ））≥Ｂ ｍｊ 。 证明（２） 通过ＤＭＲＡＱｏＳ算法知道，当且 仅当ｄｅｌａｙ（ｐ（ ， ））≤Ｄ ，算法才发出加入请求 消息，所以，对于Ｖ Ｐ（ ， ）ＴＤＭＲＡＱｏＳ，有Ｐ（ ， ） 定能满足延时约束要求。 结合证明（１）和（２）知，ＤＭＲＡＱｏＳ算法所构 造的组播树 ＤＭ ＡＱｏｓ定能满足带宽、延时约束。 定理２ ＤＭＲＡＱｏＳ算法的计算复杂度为Ｏ （１ １．１ ｌ。）。 ＤＭＲＡＱｏＳ算法的计算复杂度由加入请求、 加入和退出操作３部分组成，ｗｈｉｌｅ和ｆｏｒ循环分 别执行ｍ和 。次，而当算法找到的目标节点不满 足约束条件时，不论是否可以找到节点ｏ，在 。的 时间内都将找到一个目标节点，因此，算法在最坏 情况下其时间复杂度为Ｏ（１ １．１ ｌ ），ｌ ｌ为网 络节点数，ｌＭｌ是多播组的成员数。 ４仿真与结果讨论 仿真试验的硬件环境为Ｐ Ｎ ２．４ Ｇ／ １ ０２４ ＭＢ微机，软件环境为ＦｒｅｅＢＳＤ９．０操作系 统，网络仿真平台为Ｎｅｔｗｏｒｋ Ｓｉｍｕｌａｔｏｒ ２．０。实验 中的网络图，由Ｗａｘｍａｎ随机图模型生成［３］。每次 试验中，随机选择多播源结点和若干个请求点，每 种类型的试验重复５ｏ次，取各次结果的平均值， 以保证结果的可信度。 为进一步验证ＤＭＲＡＱｏＳ的有效性和可用 性，将ＤＭＲＡＱｏＳ、ＹＡＭ和ＱｏＳＭＩＣ进行了仿真 实验研究。图１表示多播树的代价随多播组数量 增加的变化曲线，在该仿真实验中网络节点数被 设为２５０，Ｄ— ＋３／８ｄ 。从图１中还可以看 出，当多播组数量增加时，ＤＭＲＡＱｏＳ、ＱｏＳＭＩＣ 和ＹＡＭ算法所产生的代价也增加，但 ＤＭＲＡＱｏＳ增加的程度最小，相同多播组 ＤＭＲＡＱｏＳ算法的代价最小。 交通与计算机 ２００６年第１期 第２４卷（总第１２８期） 图２表示平均加入延时随多播成员增加而变 化的曲线。图２中给出了５Ｏ个结点的随机网络，当 多播密度增大时结点平均加入时延的情况。当多 播密度增大，有许多请求点在加入组播树之前就 已经存在树上，其加入时延近似为０。无论哪种算 法，多播密度越大，结点的平均加入时延越小。在 多播密度低时，ＤＭＲＡＱｏＳ给请求点带来最低的 加入时延。此外，ＤＭＲＡＱｏＳ同样规模的多播组 所需延时比其它算法要小。从图１和图２可知， ＤＭＲＡＱｏＳ、ＹＡＭ和ＱｏＳＭＩＣ可生成代价相仿 的多播树，与ＹＡＭ和ＱｏＳＭＩＣ比较，笔者提出的 ＤＭＲＡＱｏＳ具有全分布方式、允许多播树渐近生 成，可动态实现新成员加入多播树等优点。 ２５０ ２００ 嚣１５０ 黎ｌ００ ５０ ０ ０ １０ １５ ２０ ２５ ３０ ３５ ４０ ４５ ５０ 多播成员数量 图１ ３种算法的多播树代价 ５００ ｛４００ 萎３０ｏ ２００ １ｏｏ Ｏ １０ １５ ２Ｏ ２５ ３０ ３５ ４０ ４５ ５０ 多播成员数量 图２多播组对平均加入延时的影响 ５结论 笔者主要讨论了延迟、带宽和代价约束的多 播路由问题，提出了一种具有多ＱｏＳ约束的动态 多播路由算法（ＤＭＲＡＱｏＳ），仿真实验结果表明， ＤＭＲＡＱｏＳ为多约束ＱｏＳ多播路由技术提供了 一种新的有效途径，能适用于各种网络规模和群 组规模，可扩展性良好，具有较好的应用前景。 参考文献 １ 王明中，谢剑英，张敬辕．时延及时延抖动的最小 代价多播路由策略．计算机学报，２００２，５（５）：５３４～５４１ ２石坚，董天临，石 漠．基于ＱｏＳ的动态组播路由算 法．通信学报，２００１，８（８）：１４～２２ ３ Ｗａｘｍａｎ Ｂ Ｗ．Ｒｏｕｔｉｎｇ ｏｆ ｍｕｌｔｉｐｏｉｎｔ ｃｏｎｎｅｃｔｉｏｎｓ． ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ ｓｅｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ， １９８８，６（９）：１ ６１７～１ ６２２
