J. Parallel Distrib. Comput. 70 (2010) 537–546
Contents lists available at ScienceDirect
J. Parallel Distrib. Comput.
journal homepage: www.elsevier.com/locate/jpdc
On the source switching problem of Peer-to-Peer streaming
Zhenhua Li
a
, Jiannong Cao
b,∗
, Guihai Chen
c
, Yan Liu
b
a
Department of Computer Science and Technology, Peking University, China
b
Internet and Mobile Computing Lab, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
c
Department of Computer Science and Engineering, Shanghai Jiaotong University, China
a r t i c l e i n f o
Article history:
Received 24 May 2009
Received in revised form
9 September 2009
Accepted 18 January 2010
Available online 2 February 2010
Keywords:
Peer-to-Peer
Multimedia streaming
Source switching
a b s t r a c t
Peer-to-Peer(P2P) streaming has been proved a popular and efficient paradigm of Internet media
streaming. In some applications, such as an Internet video distance education system, there are multiple
media sources which work alternately. A fundamental problem in designing such kind of P2P streaming
system is how to achieve fast source switching so that the startup delay of the new source can be
minimized. In this paper, we propose an efficient solution to this problem. We model the source switch
process, formulate it into an optimization problem and derive its theoretical optimal solution. Then
we propose a practical greedy algorithm, named fast source switch algorithm, which approximates the
optimal solution by properly interleaving the data delivery of different media sources. The algorithm can
adapt to the dynamics and heterogeneity of real Internet environments. We have carried out extensive
simulations on various real-trace P2P overlay topologies to demonstrate the effectiveness of our model
and algorithm. The simulation results show that our proposed algorithm outperforms the normal source
switch algorithm by reducing the source switch time by 20%–30% without bringing extra communication
overhead. The reduction in source switching time is more obvious as the network scale increases.
© 2010 Elsevier Inc. All rights reserved.
1. Introduction
1.1. P2P streaming
The application level Peer-to-Peer(P2P) streaming has been
proved a popular and efficient decentralized paradigm of Inter-
net media streaming in recent years, e.g. P2P voice systems like
Skype [23] and UUCall [26], and P2P video systems like Joost [9],
PPLive [18], PPStream [19], UUSee [27] and so on.
Existing P2P streaming systems can be generally classified into
three categories: tree-based, gossip-based, and the hybrid. Tree-
based systems, e.g. Bayeux [34], SCRIBE [6], NICE [4], and ZIGZAG
[24], organize nodes into a multicast tree. The root of the tree is
the media source and data segments are always delivered from
parent to sons. Tree-based method can minimize redundancy of
data delivery and ensure full coverage of data dissemination, but
cannot well adapt to network dynamics because even the failure
of a single node will partition the tree to a forest. Besides, in the
multicast tree all leaf nodes are just consumers and contribute little
to other nodes. Taking these into consideration, SplitStream [5],
∗
Corresponding author.
E-mail addresses: lzh@net.pku.edu.cn (Z. Li), csjcao@comp.polyu.edu.hk
(J. Cao), gchen@nju.edu.cn (G. Chen), csyliu@comp.polyu.edu.hk (Y. Liu).
CoopNet [15] and Chunkyspread [28] use multiple trees to increase
the resilience and balance the load. However, multiple trees bring
much higher maintenance overhead.
Gossip-based systems, also referred to as mesh-based systems,
have been proved to be effective and resilient especially in dynamic
and heterogeneous network environments. In a typical gossip
algorithm [8], every node maintains a limited number of neighbors
and sends a newly generated or received data segment to a random
subset of its neighbors. The random choice of data forwarding
targets achieves high resilience to random failures and enables
distributed operations. However, direct use of gossip for streaming
is ineffective because its random push may cause significant data
redundancy. As a result, existing gossip-based P2P streaming
systems, e.g. CoolStreaming [32], PeerStreaming [10], PALS [20],
AnySee [11] and PRIME [14], adopt a smart pull-based gossip
algorithm: every node periodically exchanges data availability
information with its neighbors and then retrieves required data
segments from a subset of its neighbors.
Recently, a hybrid architecture for P2P streaming has been
proposed to integrate the merits of multicast tree and gossip mesh,
e.g. Climber [16], mTreebone [29] and CliqueStream [3]. In these
systems, usually the stable nodes are organized into one or several
multicast tree(s), while the unstable nodes form a gossip mesh.
Nevertheless, there has been no practical P2P streaming system
which utilizes the hybrid method till now.
0743-7315/$ – see front matter © 2010 Elsevier Inc. All rights reserved.
doi:10.1016/j.jpdc.2010.01.005