满足延迟约束的加速加权分布式动态Multicast算法.pdfVIP

满足延迟约束的加速加权分布式 动态!#$%’($ 算法 % % ! % 黄传河 陈莘萌 贾小华 张文涛 % （武汉大学计算机学院，武汉 $=! ） ! （香港城市大学电脑科学系，香港） ： 8?,*( @*,A+-#+*)B’#CD’#EF 摘 要 在计算机网络中高效实现具有延迟约束的’()*+,-) 功能，是计算机网络应该提供的一种基本功能，是保证视 频会议系统、多媒体教学系统、视频点播系统 （ ）等应用得以实现的基础。该文针对这一问题，提出了一种加速加权方 ./0 法，根据已经经过的部分路径的延迟和剩余延迟，将成本加速加权，利用加权成本构造 ’()*+,-) 树。利用该算法，可以在 计算机网络中以分布式方式建立接近最小成本、满足延迟约束条件、适于实时通信的动态 ’()*+,-) 连接，避免了传统方 法将成本和延迟分别考虑、大量回溯的弊端。 关键词 ’()*+,-) 算法 延迟约束 分布式算法 文章编号 （ ） 文献标识码 中图分类号 %!8G$$%8 !! !$8 %HG8 : I7$ % ) *%($+%,$-. )#/0+%$12 30+ *45’2% !#$%’($ 6’$%(34%5/ *-#’4 705. 8(%5/ )-#-+’$-. 9-%/1$ :’5/ ;1’51- ;1-5 =%52-5/ %’ =%’01’? @1’5/ 9-5$’0 % （ ， ， ） J2?K’)CL 3+E22( M’E,N ON*PCL-*)B M’E,N $=! ! （ ， ， ） 0CK,L)?CN) 2Q J2?K’)CL 3+*CN+C J*)B ON*PCL-*)B 2Q 92NR S2NR 92NR S2NR ： ， ),($+’$ QQ*+*CN) ?’()*+,-) Q’N+)*2N,(*)B -,)*-QB*NR DC(,B T2’ND *- Q’ND,?CN),( )2 ?2DCLN +2?K’)CL NC)U2LF- C-KC+*,((B ， ， Q2L -’+E ,KK(*+,)*2N- ,- P*DC2 +2NQCLCN+*NR -B-)C?- ?’()*?CD*, CD’+,)*2N -B-)C?- P*DC2 2N DC?,ND#IE*- K,KCL KLC-CN)- ,N ,++C(CL,)*NR UC*RE)CD +2-) ,(R2L*)E?#V) ,++C(CL,)C- )EC *N+LC,-C 2Q )EC UC*RE)CD +2-) ,++2LD*NR )2 )EC ,++’?’(,)CD