结合分布式与集中式特点的动态多播路由算法.pdf
需积分: 10 131 浏览量
2008-12-29
13:42:31
上传
评论 1
收藏 249KB PDF 举报
计 算 机 系 统 应 用 ２００８ 年 第 ６ 期
结合分布式与集 中式特点 的动态 多播路 由算法
Ｄｙｎａｍｉｃ Ｍｕｌｔｉｃａｓｔ Ｒｏｕｔｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ ａｎｄ Ｃｅｎｔｒａｌｉｚｅｄ Ａｌｇｏｒｉｔｈｍ
李 昌兵 杜茂康 （重庆邮 电大学 重庆 ４０００６５）
胡 华 （重庆 大学 重庆 ４０００４４）
摘 要 ：针对在 多播成 员动 态变化 的环境 中的 多播路 由树的建立和调整等问题，本文提 出结合分布式和集中式特点的
动态多播路 由算法，在新 节点加入多播会话时，采用分布式的方法搜索新节点到 当前多播树的满足 ＱｏＳ约束
的最优路径。而在成员节点离开多播会话时，根据其对 多播会话质量的影响程度 ，决定是否执行 多播树的重构
操作。与静态多播路 由算法比较 ，该算法具有更好的适应性和灵活性。仿真结果验证了算法的有效ｌ洼。
关键词 ：ＱｏＳ 动 态多播 路 由算法 集中式算法 分布式 算法
１ 引言
随着 网络 电视会议、远 程教育等业 务相继 出现 ，对
网络 资源 的优 化也提 出了新的要求 ，多播技术 就是为
了节约 网络资源而 提 出的。作为 多播技术研 究重点 的
多播路 由问题分为两种类型 ：一种是静态 多播路 由，即
在整个 多播会话 期间不允许 组成员动 态变化 ；另一种
是动态多播路 由，允 许组成 员随 时加 入或 离开 。在网
络 电视会议 、远程教育 等多媒体 业务 中常采 用动态 多
播路 由。研究人员对静态多播 ＱｏＳ路 由优化算 法进行
了广 泛的研 究。而对动态 多播路 由问题 ，已被 证 明是
ＮＰ完全 问题。 目前研 究较 多 的仍 旧只是 动态 Ｓｔｅｉｎｅｒ
问题 ，对于考 虑时延约束和 费 用优化 的动态 多播路 由
问题 ，目前研究得较少 ｊ。
本文针对动态 多播 路 由问题 ，提 出 了结 合分 布式
和集 中式特点的部分重构 动态 多播 ＱｏＳ路 由算 法 ，算
法仿真 表明 ，它比采用启发性 算法和 贪婪算法 具有更
低的代价。
２ 问题描述
网络 用加权有 向图 Ｇ（Ｖ，Ｅ）表 示。其 中，Ｖ是节 点
集 ，Ｅ是节点 问双 向链路 集 。（Ｖ Ｉ＿（Ｕ，Ｖ）Ｅ Ｅ，链 路 Ｉ
（Ｕ，Ｖ）的状态可 由其路 由跳 数 ｈ（Ｕ，Ｖ）＝ｈ（１），开 销 Ｃ
（Ｕ，Ｖ）＝Ｃ（１），延迟 ｄ（Ｕ，Ｖ）＝ｄ（１），延迟抖 动 ｉ（Ｕ，Ｖ），
可用带宽 ｂ（Ｕ，Ｖ），和包丢失率 ｌｏ（Ｕ，Ｖ）＝Ｉｏ（１）联合表
示。令 ＭｃＶ为 多播 组 ，Ｖ Ｅ Ｍ 为组成 员 ，则 多播树 Ｔ
６２ 研究开发 Ｒｅｓｅ＝ｒ￣ｈ ａｎｄ Ｄｅｖｅ］ｏ￣ ｅｎｔ
是 Ｇ的子图 ，ＰＴ（Ｖ。，Ｖ ）表示树 Ｔ中一条从源节点 Ｖ。到
目标节点 Ｖ ＥＭ 一｛Ｖ。｝的路径 。因此，基于路 由跳数 、
开销 、延迟 、抖动 、可 用带 宽和 包无损 传输率 的 多 ＱｏＳ
约束 动态 多播路 由问题可描述如下 ：
给定图 Ｇ（Ｖ，Ｅ）、多播信源 ＶＳ、动态 多播 组 ＭｃＶ，
确定 多 播最 短 路 径 （ＳＰＴ）树 Ｔ Ｇ，使 得 在 满足 下 列
Ｑ０ｓ约束条件
Ｖ Ｅ ，Ｄ（弓（ｖ ， ）） ｄ ，Ｖ） Ｄ～ （１）
‘，（弓（ ， ））＝ （ ） ‘，～ （２）
（ ．ｖ （ ， ’
Ｂ（弓（ ＇ ））＝
∑ｉｎ
帅
ｌｎ
） ‰
） Ｂ～ （３）
） ｄ（ ．ｖ） Ｄ Ｉ－）Ｊ
ｚ （弓（ ， ）） 兀 （１一 （ Ｖ）） ｚ ｆ４）
的前提 下实现如下优化 目标 ：
Ⅳ（弓（ ， ）） 荟…、 （“， ） ｍＪ“ （５） （ ． ｅ丹（ 。 ） ’
ｃ（弓（ ， ）） 磊 ｃ（“，ｖ）＿ｒｎｊ“ （６） （ ．ｙ ‘片（ ． １ ’
在 ＱＤｓ约束 条 件 中 ，Ｄｍｅｘ表 示 延 迟上 限 ，Ｊｍｅｘ
表示延迟抖动上限 ，Ｂｍｉｎ表示带 宽下 限，Ｚｍｉｎ表示 包
无损传输概 率下 限。若 优化 目标 ５和 目标 ６发 生 冲
突 ，优先考虑 目标 ６，即新节 点的路径应尽 量利 用已有
的多播 树 ，在 相 同 开 销 的 情 况 下 ，选 择 跳 数 较 小 的
路 径。
３ 算法 原理
本文 的目的是为动态环境设计 一个满足 ＱｏＳ约束
维普资讯 http://www.cqvip.com
评论0
最新资源