P2P分层流媒体中源服务器参与的数据层分配算法  

Layer Allocation Algorithms in Layered Peer-to-Peer Streaming with Source Server's Participation

作　　者：刘亚杰[1] 窦文华[1] 

机构地区：[1]国防科学技术大学并行与分布处理国家重点实验室,长沙410073

出　　处：《计算机研究与发展》2005年第9期1472-1477,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(90104001;60433040);国家"九七三"重大基础研究发展规划基金项目(2003CB314002)

摘　　要：P2P流媒体是一种性价比良好的流媒体服务体系.由于Peer节点的服务能力有限,在大规模的系统应用中,源服务器的带宽等资源仍可能成为系统的瓶颈.基于P2P分层流媒体,研究如何在Peer节点之间对数据层进行优化分配,以减少对源服务器带宽的占用,该优化问题属NP难问题.提出了两种算法:一种是基于多目标优化的近似算法,分析了该算法的近似比;另一种是基于分枝定界的精确算法,它利用计算二分图中的最大流值来确定分枝上界及被裁剪的分枝.仿真实验表明两种算法都有较大的性能改进,且精确算法中的分枝定界策略有较高的效率.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.

关 键 词：P2P 分层流媒体 数据层分配 NP难 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]