
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Optimal PullPush Scheduling Algorithm Based on Network Coding for Mesh PeertoPeer Live Streaming
Laizhong CUI Yong JIANG Jianping WU Shutao XIA
Publication
IEICE TRANSACTIONS on Communications
Vol.E95B
No.6
pp.20222033 Publication Date: 2012/06/01
Online ISSN: 17451345 Print ISSN: 09168516 Type of Manuscript: PAPER Category: Network Keyword: PeertoPeer live streaming, random network coding, pullpush scheduling algorithm, optimization problem,
Full Text: PDF(2MB) >>Buy this Article
Summary:
Most largescale PeertoPeer (P2P) live streaming systems are constructed as a mesh structure, which can provide robustness in the dynamic P2P environment. The pull scheduling algorithm is widely used in this mesh structure, which degrades the performance of the entire system. Recently, network coding was introduced in mesh P2P streaming systems to improve the performance, which makes the push strategy feasible. One of the most famous scheduling algorithms based on network coding is R^{2}, with a random push strategy. Although R^{2} has achieved some success, the push scheduling strategy still lacks a theoretical model and optimal solution. In this paper, we propose a novel optimal pullpush scheduling algorithm based on network coding, which consists of two stages: the initial pull stage and the push stage. The main contributions of this paper are: 1) we put forward a theoretical analysis model that considers the scarcity and timeliness of segments; 2) we formulate the push scheduling problem to be a global optimization problem and decompose it into local optimization problems on individual peers; 3) we introduce some rules to transform the local optimization problem into a classical mincost optimization problem for solving it; 4) We combine the pull strategy with the push strategy and systematically realize our scheduling algorithm. Simulation results demonstrate that decode delay, decode ratio and redundant fraction of the P2P streaming system with our algorithm can be significantly improved, without losing throughput and increasing overhead.

