覆盖多播网络中代理服务器的部署算法

doi:10.3969/j.issn.1001-2400.2013.03.021

J4 ›› 2013, Vol. 40 ›› Issue (3): 139-144.doi: 10.3969/j.issn.1001-2400.2013.03.021

覆盖多播网络中代理服务器的部署算法

徐剑^1,2;倪宏²;邓浩江²;刘磊²

(1. 中国科学院大学，北京 100049；
2. 中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190)

收稿日期:2012-06-18 出版日期:2013-06-20 发布日期:2013-07-29
通讯作者: 徐剑
作者简介:徐剑(1985-)，男，中国科学院博士研究生，E-mail: xuj@dsp.ac.cn．
基金资助:
国家高技术研究发展计划(863)资助项目(2011AA01A102);国家科技支撑计划资助项目(2011BAH11B04);中国科学院战略性先导科技专项子课题资助项目(XDA06010302)

Proxy placement algorithm for the overlay multicast network

XU Jian^1,2;NI Hong²;DENG Haojiang²;LIU Lei²

(1. Univ. of Chinese Academy of Sciences, Beijing 100049， China;
2. National Network New Media Engineering Research Center, Institute of Acoustics Chinese Academy of Sciences, Beijing 100190， China)

Received:2012-06-18 Online:2013-06-20 Published:2013-07-29
Contact: XU Jian

摘要/Abstract

摘要：

针对覆盖多播网络中现有代理服务器部署算法组播传输时延较高、代理服务器利用不均衡以及可扩展性差的问题，提出了一种优化的度约束最小延迟代理服务器部署问题模型．该模型在网络中值问题的基础上，为了优化组播端到端传输延迟，改进了目标函数; 为了合理利用代理服务器，引入度约束以反映代理服务器处理能力．证明了该模型属于NP完全问题，提出了一种贪婪启发式算法．实验结果表明，所提出模型能够减少组播平均端到端传输延迟，并在不同网络规模和组规模下均有较好的性能表现．

关键词: 覆盖网络, 组播, 代理服务器部署, 启发式算法

Abstract:

The existing proxy placement algorithms for the overlay multicast network usually lead to a number of problems, such as high multicast delay, unbalanced proxy load and lack of scalability. Focusing on these problems, an optimized degree constrained minimum delay proxy placement problem model is proposed based on the network median problem. In order to optimize multicast end-to-end delay, the model improves the object function. In order to utilize server resources rationally, the model abstracts the degree constraint to reflect the proxy processing capacity. In this model the problem is shown to be NP-Complete, and a greedy heuristic algorithm is proposed. Experimental results show that the model can decrease average end-to-end delay and have a good performance in different network sizes and multicast group sizes.

Key words: overlay network, multicasting, proxy placement, heuristic algorithms

中图分类号:

TP393

徐剑;倪宏;邓浩江;刘磊. 覆盖多播网络中代理服务器的部署算法[J]. J4, 2013, 40(3): 139-144.

XU Jian;NI Hong;DENG Haojiang;LIU Lei. Proxy placement algorithm for the overlay multicast network[J]. J4, 2013, 40(3): 139-144.

参考文献

［1］ Diot C, Levine B N, Lyles B, et al. Deployment Issues for the IP Multicast Service and Architecture ［J］. IEEE Network, 2000, 14(1): 78-88.
［2］ Shi Y S, Turner J S. Multicast Routing and Bandwidth Dimensioning in Overlay Networks ［J］. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1444-1455.
［3］ Banerjee S, Kommareddy C, Kar K, et al. Construction of an Efficient Overlay Multicast Infrastructure for Real-time Applications ［C］//IEEE International Conference on Computer Communications. San Francisco: IEEE, 2003: 1521-1531.
［4］ Li Z, Mohapatra P. The Impact of Topology on Overlay Routing Service ［C］//IEEE International Conference on Computer Communications. Hong Kong: IEEE, 2004: 408-418.
［5］吴家皋, 叶晓国, 姜爱全. 一种异构环境下覆盖多播网络路由算法［J］. 软件学报, 2005, 16(6): 1112-1119.
Wu Jiagao, Ye Xiaoguo, Jiang Aiquan. A Routing Algorithm in Heterogeneous Overlay Multicast Networks ［J］. Journal of Software, 2005, 16(6): 1112-1119.
［6］张晓瑜, 张光昭. 在overlay网络上的负载平衡多播路由算法［J］. 通信学报, 2009, 30(4): 86-92.
Zhang Xiaoyu, Zhang Guangzhao. Load Balance Multicast Routing Algorithms on Overlay Network ［J］. Journal on Communications, 2009, 30(4): 86-92.
［7］ Guo J, Jha S. Placing Multicast Proxies for Internet Live Media Streaming ［C］//IEEE Conference on Local Computer Networks. Dublin: IEEE, 2007: 149-156.
［8］ Wu M Y, Zhu Y, Shu W. Placement of Proxy-based Multicast Overlays ［J］. Computer Networks, 2005, 48(4): 627-655.
［9］ Yang S Y, Kim Y A, Wang B. Designing Infrastructure-Based Overlay Networks for Delay-sensitive Group Communications ［C］//Global Telecommunications Conference. Washington: IEEE, 2007: 565-570.
［10］ Lao Li, Cui Junhun, Gerla M, et al. A Scalable Overlay Multicast Architecture for Large-Scale Applications ［J］. IEEE Trans on Parallel and Distributed Systems, 2007, 18(4): 449-459.
［11］ Khare V, Zhang B. Towards Economically Viable Infrastructure-based Overlay Multicast Network ［C］//IEEE International Conference on Computer Communications. Rio de Janeiro: IEEE, 2009: 1989-1997.
［12］杨丰梅, 华国伟, 邓猛, 等.选址问题研究的若干进展［J］. 运筹与管理, 2005, 14(6): 1-7.
Yang Fengmei, Hua Guowei, Deng Meng, et al. Some Advances of the Researches on Location Problems ［J］. Operations Research and Management Science, 2005, 14(6): 1-7.

[1]	脱立恒;倪宏;李满天;刘学. 覆盖网络中多服务静态部署算法[J]. J4, 2014, 41(4): 137-143.
[2]	刘占军;朱志超;周诗妍;张祖凡. C-RAN架构无线接入网组播中的协作RRU选择算法[J]. J4, 2013, 40(6): 168-173.
[3]	高雅;邱智亮;张茂森;黎军. 一种支持单组播混合交换的Clos网络及调度算法[J]. J4, 2013, 40(1): 48-52.
[4]	妥艳君;刘云;刘永健. LEO卫星星座系统组播报文扩散算法[J]. J4, 2010, 37(2): 380-384.
[5]	赵俊;孙小菡. 异步光分组交换型高性能计算机系统架构及性能分析 [J]. J4, 2007, 34(7): 193-196.
[6]	徐瑞;李伟华;陈华胜. 基于树的按需Ad Hoc组播路由协议性能比较和分析 [J]. J4, 2007, 34(4): 664-668.
[7]	张冰;刘增基;原冰. 一种基于窗口的多速率组播拥塞控制算法 [J]. J4, 2006, 33(5): 768-772.
[8]	张冰;徐雅嫣;刘增基;李振. 接收端驱动的流媒体组播拥塞控制协议[J]. J4, 2005, 32(3): 362-366.
[9]	胡辽林;刘增基. 具有组播能力的OXC的串扰研究[J]. J4, 2003, 30(2): 197-200.
[10]	暂时无作者信息. 两阶段混合流程调度问题研究[J]. J4, 2002, 29(3): 305-310.
[11]	王斌;刘增基;李红滨. 主动可靠组播传输往返行程时间估算策略[J]. J4, 2002, 29(1): 62-67.
[12]	王斌;刘增基;李红滨. 空间相关丢包条件下基本可靠组播传输协议研究[J]. J4, 2001, 28(5): 557-562.

覆盖多播网络中代理服务器的部署算法

Proxy placement algorithm for the overlay multicast network

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

Metrics

本文评价

推荐阅读 0