首页 | 本学科首页   官方微博 | 高级检索  
     

P2P分层流媒体中源服务器参与的数据层分配算法
引用本文:刘亚杰,窦文华.P2P分层流媒体中源服务器参与的数据层分配算法[J].计算机研究与发展,2005,42(9):1472-1477.
作者姓名:刘亚杰  窦文华
作者单位:国防科学技术大学并行与分布处理国家重点实验室,长沙,410073
基金项目:国家自然科学基金项目(90104001,60433040);国家“九七三”重大基础研究发展规划基金项目(2003CB314002)
摘    要:P2P流媒体是一种性价比良好的流媒体服务体系.由于Peer节点的服务能力有限,在大规模的系统应用中,源服务器的带宽等资源仍可能成为系统的瓶颈.基于P2P分层流媒体,研究如何在Peer节点之间对数据层进行优化分配,以减少对源服务器带宽的占用,该优化问题属NP难问题.提出了两种算法:一种是基于多目标优化的近似算法,分析了该算法的近似比;另一种是基于分枝定界的精确算法,它利用计算二分图中的最大流值来确定分枝上界及被裁剪的分枝.仿真实验表明两种算法都有较大的性能改进,且精确算法中的分枝定界策略有较高的效率.

关 键 词:P2P  分层流媒体  数据层分配  NP难  算法
收稿时间:2004-09-29
修稿时间:2004-09-292005-01-06

Layer Allocation Algorithms in Layered Peer-to-Peer Streaming with Source Server's Participation
Liu Yajie,Dou Wenhua.Layer Allocation Algorithms in Layered Peer-to-Peer Streaming with Source Server''''s Participation[J].Journal of Computer Research and Development,2005,42(9):1472-1477.
Authors:Liu Yajie  Dou Wenhua
Abstract:Peer-to-peer streaming is cost-effective for it can capitalize the resources of peer nodes to provide service to other receivers. But in peer-to-peer streaming, as the outbound bandwidths of supplying peers or the bandwidths they willing to contribute are normally constrained and limited, the source media server can still become overloaded when the system's scale is very large. Considering layered peer-to-peer media streaming, it is needed to optimally allocate layers among peers to maximally save the source server's bandwidth consumption, and the optimal allocation problem is NP-hard. Two algorithms are analyzed for this optimization problem: the first one is an approximation algorithm which is based on the principle of multiple objective optimization, and the algorithm's approximation ratio is also analyzed; The second one is a branch and bound accurate algorithm, and by calculating a constructed bigraph's maximum flow it can identify the corresponding branch's upper bound and can thus decide whether to prune this branch or not. Performance study based on simulation is carried out. The results show that the two proposed algorithms have better performance than the related algorithm, and the accurate algorithm's branch and cut principle is high-efficient.
Keywords:P2P  layered streaming  data allocation  NP hard  algorithms
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号