13-02-2013, 04:51 PM
Network Coding in Live Peer-to-Peer Streaming
Abstract—
In recent literature, network coding has emerged as
a promising information theoretic approach to improve the performance
of both peer-to-peer (P2P) and wireless networks. It has
been widely accepted and acknowledged that network coding can
theoretically improve network throughput of multicast sessions in
directed acyclic graphs, achieving their cut-set capacity bounds.
Recent studies have also supported the claim that network coding
is beneficial for large-scale P2P content distribution, as it solves
the problem of locating the last missing blocks to complete the
download.
We seek to perform a reality check of using network coding for
P2P live multimedia streaming.We start with the following critical
question: How helpful is network coding in P2P streaming? To
address this question, we first implement the decoding process
using Gauss-Jordan elimination, such that it can be performed
while coded blocks are progressively received.We then implement
a realistic testbed, called Lava, with actual network traffic to
meticulously evaluate the benefits and tradeoffs involved in using
network coding in P2P streaming. We present the architectural
design challenges in implementing network coding for the purpose
of streaming, along with a pull-based P2P live streaming protocol
in our comparison studies. Our experimental results show that
network coding makes it possible to perform streaming with a finer
granularity, which reduces the redundancy of bandwidth usage,
improves resilience to network dynamics, and is most instrumental
when the bandwidth supply barely meets the streaming demand.
Index Terms—Multimedia streaming, network coding, peer-topeer
networks.
I. INTRODUCTION
NETWORK coding has been originally proposed in information
theory [2]–[4], and has since emerged as one of
the most promising information theoretic approaches to improve
performance in peer-to-peer (P2P) and wireless networks. The
upshot of network coding is to allow coding at intermediate
nodes in a directed network, assuming that links are error-free.
The assumption of error-free links is made to avoid the most
perplexing challenges of interference in the field of network information
theory. It has been shown that random linear codes
using a Galois field of a limited size are sufficient to implement
network coding in a practical network setting. In some cases,
even exclusive-ORs—GF(2)—can improve throughput in wireless
mesh networks [5].
Avalanche [6], [7] has demonstrated—using both simulation
studies and realistic experiments—that network coding may im-
Manuscript received November 16, 2006; revised July 20, 2007. This work
was supported in part by the Natural Sciences and Engineering Research
Council of Canada and Bell Canada through its Bell University Laboratories
R&D program. A preliminary version of this work is to appear in Proc. IEEE
INFOCOM 2007 [1]. The associate editor coordinating the review of this
manuscript and approving it for publication was Dr. Hui Zhang.
The authors are with the Department of Electrical and Computer Engineering
prove the overall performance of P2P content distribution, up
to about a hundred peers. The intuition that supports such a
claim is that, with network coding, all blocks are treated equally,
without the need to distribute the “rarest block” first, or to find
them in the “end game” of the downloading process. While these
are noteworthy observations, we note that content distribution
applications deal with elastic traffic: one wishes to minimize
downloading times, but there are no required lower bounds with
respect to the instantaneous rate of a live session.
The requirements of P2P live multimedia streaming applications,
however, have marked a significant departure from traditional
applications of elastic content distribution. The most
critical requirement is that the streaming rate has to be maintained
for smooth playback. Each live streaming session may
involve a live media stream with a specific streaming rate, such
as 800 Kbps for a typical Standard-Definition stream, generated
with a modern codec such as H.264. The challenge of streaming
is that the demand for bandwidth at the streaming rate (which is
very similar to CBR traffic) must be satisfied at all peers, while
additional bandwidth is, in general, not required.
Existing successes with P2P streaming, such as Cool-
Streaming [8] and PPLive, have demonstrated that P2P live
streaming is not only feasible, but also practical at a large
scale. Observing the recent success of using network coding
in wireless mesh networks [5] and P2P content distribution
[6], it is natural to ask the following interesting question: Does
network coding help in P2P live streaming? In this paper,
we endeavor to explore the benefits and tradeoffs of applying
network coding in P2P live streaming, using an experimental
testbed with real traffic and a highly optimized implementation
of network coding. To implement the decoding process at each
peer with the highest performance possible, we propose to
use Gauss–Jordan elimination (rather than the usual Gaussian
elimination), which can be performed while coded blocks are
progressively received. To further optimize our implementation,
we have implemented network coding with full acceleration
using the x86 SSE2 instruction set.
In building our experimental testbed, henceforth referred to
as Lava, in a cluster of 44 dual-CPU servers, we have to address
a number of significant design and implementation challenges.
First, as live traffic is involved in all our experiments,
large volumes of live TCP connections and UDP traffic need to
be efficiently managed. Second, all experiments need to be both
realistic and controllable, with upload capacities on each peer
accurately emulated. Third, since we emulate a number of peers
in each cluster node, we wish to minimize the processing and
memory footprints of our implementation. Finally, to qualify as
a “reality check,” we wish to implement peer joins and departures
following specific probability distributions. This brings all
the challenges when dynamics are considered, including handling
broken and orphaned network connections, exchanging
availability, and maintaining updated peer lists.