《基于“树”结构的多优先级ａｍｔ自愈算法》由会员分享，可在线阅读，更多相关《基于“树”结构的多优先级ａｍｔ自愈算法（9页珍藏版）》请在金锄头文库上搜索。
1、一 勺补 ; t j I q 基于“ 树” 结构的多 优先级 A M T 自 愈算 法 (孙立 宏 冬艳玲 张顺颐 南京峥电学院信息网络技术研究 所方京 2 1 0 00 3 E m a i 1 :Y 9 6 8 9 (gy u p t. e d u .c n 幼 要 A T M ( A s y n c h r o n o u s T r a n s f e r M o d e ) 网络有许多特点适合多挤伽 u l t i c a s t ) 通信， 常用方法就是构造A T M 多播树 ( A M T - -A T M M u l t i c a s t T r e e).为保U多.服务质#,
2、 A M T 必须其备 一 定的自 愈能 力. 本文 在综 述了 荃于 链路的 侧T 自 T a 算法 及其 存在问翅的 基袖上， 提出了一 种断型 的 基于 ” 多播树” 结构的A N T 自 愈算法，并对两种葬法的性能进行了比 较. A U* A T M 多 括( M w F r i e a s t ) A M T 自 T a 恢复率 恢复时廷 R e s e a r c h O f S e lf - h e a l in g o n A T M m u lt ic a s t t re e S u n l i h o n g L u y a rd in g Z h a n g s h u
3、 n y i In f o rm a tio n N e t w o r k T e c h n o lo g y In s tit u e , N a n j in g In st itu te o f P o s ts a n d T e l e c o m m u n i c a t i o n s , 2 1 0 0 3 , N a n j i n g , P R C A b a t r a e tN a n y f e a t u r e s o f a n A T M ( a s y n c h r o n o u s t r a n s f e r mo d e ) s w i
4、tc h e n v ir o n me n t c a n加 e x p lo i t e d in t h e d e s ig n o f m u l ti c a s t c o m m u n i c a d o n .T h e c o m m o n m e ws i s t o c o n s t r u c t A M T ( A T M mu lt i c a s t t r e e ) . I n o r d e r t o e n s u re t h e q u a l ity o f m u l t ic a s t s e r v imAMT m u s t h
5、a v e t h e c a p a lit y o f s e l f- 刚耐咖 h e a li n g .t n t h is p a p e r ,w e f ir s t s u m m a r i z e l in k - b a s e d s e lf - h e a l i n g s t ra t e g y o n人 M T a n d p o in t s h o rt c o m i n g o f t h is s c h e m e . .t h e n , p u t f o r w a r d a n e w s e l f h e a l in g s c
6、 h e m e o n A M T w h i c h is T r e e - b a s e d w i th m u l ti p le p r io r ity .B y c o m p u t e r s im u la t io n , w e v e r i fy ,w e c o m p a re t h e p e r f o r m a n c e b a s e d o n s c h e me s . K e y w a r d f : A T M Mu l t ic a s t A MT S e l f - h e a l吨R e s to r a t i o n
7、r a te R e s to r a t io n la t e n c y 1 ， 引言 随着多媒体、 分布式计 算、 协同 操作、 群组通信等技 术的日 趋完善， 视频会议、分布式 数据库、网络游戏、V O D 、 远程教学等多播业务的应用变得日 趋广泛。 A T M 网 络面向 连接、 基于交换、输入轴出通路在物理上 独立、可 预留 带宽、预 先建立虚通路 V C等特点使之 适合 于 多播通信。 在 A T M网络中实现多播 通信的 常用方式 就是利 用 “ 多 播树” ( 即A MT -A T M M u lt ic a s t T t r e e ) 将数 据信息从 发送方 送至
8、群组中的 所有结点。 为降 低因 链路或结点失败带来 的危害， 保证多播 业务的 服务 质量， A M T 必须具备一定的自 愈能力。 所 谓自 愈， 是指网络发 生故障时， 不需要人工干预，就能很快地恢复所 涉及的业务。 目 前， 在A T M网 络中， 主要采用两类差错恢复 机制来提高网 络的自 愈能力: 静态恢复机 制 ( 即预先设定机制) 和动态恢复 机制。在静态 恢复 机制中，每条正 在工 作的 V P通道都存 在一条预先设定的备份V P 2 j ; 在动态恢复机制中。 检测到失败的结点I 播 ( B r o a d c a s t ) 查询消 息( S e a r c h M e
9、s s a g e ) 以期找到一条具有足够带宽资 源的可替代路由用于恢复失 败业务 3 ) . 鉴于 静态恢复机制存在的诸多I M 有缺陷，在实际应用中，一般采用动态恢复机制。 1 4 8 将 A T M 网 络中 采用的 差错恢复机制进行推广可形成了 多种 A M T恢复 机制 ( 即自 愈机 制) ， 其中应用较为广 泛的是基于链 路 ( L i n k - b a s e d )的 A M T 自 愈 策略。 采用这种策略，当 A M T 失败时， 与失败链路直 接相邻的下 连结点 成为查 询消息 发送方( S e n d e r 一 简称“ 发送方” ) ， 与 失 败 链 路 直
10、接 相 邻的 上 连 结 点 成 为 选 择 重 发 方( C h o o s e r - 简 称 “ 选 择 方 ” ) ， 通 过p o i n t - t o - p o i n t 的通信方式完 成失 败链路的 恢复， 原理如图 ( 1 ) 所示: 5 : 发送 方 :C :选择 为 在s e n d e r - C h o o s e r 对 中 仅存在个 C h w s e r 力 图1 基于链路( L i n k - b a s e d ) 的 A M T 恢复机制原理示 采用动态恢复机制， 传送查询消息 ( S e a r c h M e s s a g e )的同 时要在其所
11、经链路上预留恢复 失 败业务所需的 带宽资 源， 一q 在某处得不到差错恢复 所需的带宽资 源，该路由 将不能成为 一 条满足条件的 可替代路由。 从图 ( 1 )可以 看出: 在基于 链路 ( L i n k - b a s e d )的 A M T恢复 机制中，S e n d e r方与 C h o o s e r 方形成了一对一的关系，也就是说，当一棵 A MT失败时，在 S e n d e r - C h o o s e r ( s ) 对中 仅存在一 个C h o o s e r 方， 这样在S e n d e : 与C h o o o s e r ( s ) 间 用于 差错恢复的
12、可选路由数目 较少， 在带宽资 源竞争( 如同时存在多棵A MT ) 较为激烈的情况下， 恢复率 主 要指恢复的可靠度， 其定义为: 得到恢复的A MT 数目 / 因 链路或结点失 败而需要恢复的A M T 总数) 将大大折扣;另一方面，在基于链路的恢复机制中，无论A MT的结构如何，恢复任务 均由固定的 C h o o s e r 方来完成. 而在选定的可替代路由 匕 可能存在己经成功地接收到了S e n d e r 方 未接收到的 数据信息的中间结点，如果用与S e n d e r 距离更近的中间结点 代替C h o o s e r 方完 成差错 恢复， 恢复时 延将降低。上 述两点正是基
13、于 链路恢复机制的主要缺陷，而造成这些缺 陷的关 键因素 在于: 基于 链路的A M T 恢复 机制根本 不考虑多 播树的 结构， 差错恢复 后， A M T 结构根本不发生变 化。 为解决上 述问题， 我们自 然而 然地想到:为 提高恢 复率 ( 可靠度) ，当A M T失败时，可 以 允许存在多个C h o o s e r 方， 即 一个S e n d e r 对应着多个C h o o s e r ， 形成一对多的关系， 且任何 一 个 C h o o s e r 均可完成恢复 任务;另 一方面， 为降 低恢复 时延， 可选择代价最小 ( 如:距离 最近、 时延最小或链路负载最轻等等)的
14、C h o o s e r 来恢复 失败的 业务。 要实现这两点，就必 须获得 A MT的拓扑结构信息。最后，在 A T M网络中，不同的 A MT可能携带不同类型的多 播业务，不同业务 对传输的实时 性和可靠性要求不尽相同 7 1 0鉴于上 述几点， 我们提出了 基 于“ 树” ( T r e e - b a s e d ) 结 构、 具 有多 优先 级的A M T自 愈 机制， 该机制充分考虑A M T 的结构， 为 S e n d e r 选择多个 C h o o s e r 方，多对 S e n d e r - C h o o s e r 组协同 i _ 作完成失败业务的恢复。基于 “
15、 树”的混合优先级恢复机制的原理如图 ( 2 )所示: 1 4 9 C1 SC2一 协、 or C 3 0 t: 0 O O Iu v L4 廊or A廊 5 : 发送 方:C :选择方) 在S e n d e r - C h m s e r 对中存在多个 h o o s e r 方， 本例中存在3 个) 图 2 基于 “ 树”( T r e e - b a s e d ) 的 A M I 、 恢复 机制原 理示意图 正如图 ( 2 ) 所 示， 连接B , C , D均可用来恢复失 败的 链路A 。注意: 在基于“ 树” 的 恢复 机制中， 不 管A M T 结构如何变化， 新构建的多播树必
16、须能够提 供与原多 播树完全相同的 多播业务。 本文组织如下: 第二节 概述了 基于“ 树” 的 混合优先级A M T自 愈策略的原理及实现过 程; 第三i y 论述了 新机制的 协议映射与实现;第四节通过计算机仿真对两种机制的 性能进行了比 较; 最后给出了 结论。 2 . 基于 “ 树” 结构的 A M T 自 愈策略 实现基于“ 树” 的棍合优先级自愈 机制的 关键是如何选择多个合适的 结点 作为 C h o o s e r ( s ) 。 当 链路失 败时， 原 有的A M T 被分成两棵子树: P 子树( P 甲 S u b t r e e ) 和C子树( C - S u b t r e e ) , 如图 ( 3 )所示: P 子 树C 子树 ( P 子树中共有3 个选择 方) ( S e n d e r 与P 子 树 中 的个C h o o s e r 相连) 图 3 P 子树和C 子 树划分示 意图 |11. 从图( 3 ) 可以 看出: P子 树以 原A M T 的根结点作为自己 的根结点: 而C 子
