31-05-2012, 05:20 PM
Live Streaming with Receiver-based Peer-division Multiplexing
live streaming with receiver-based peer-division multiplexing.pdf (Size: 1.1 MB / Downloads: 30)
Abstract
A number of commercial peer-to-peer systems for
live streaming have been introduced in recent years. The behavior
of these popular systems has been extensively studied in several
measurement papers. Due to the proprietary nature of these
commercial systems, however, these studies have to rely on a
“black-box” approach, where packet traces are collected from
a single or a limited number of measurement points, to infer
various properties of traffic on the control and data planes.
Although such studies are useful to compare different systems
from end-user’s perspective, it is difficult to intuitively understand
the observed properties without fully reverse-engineering
the underlying systems. In this paper we describe the network
architecture of Zattoo, one of the largest production live streaming
providers in Europe at the time of writing, and present a
large-scale measurement study of Zattoo using data collected by
the provider. To highlight, we found that even when the Zattoo
system was heavily loaded with as high as 20,000 concurrent
users on a single overlay, the median channel join delay remained
less than 2 to 5 seconds, and that, for a majority of users, the
streamed signal lags over-the-air broadcast signal by no more
than 3 seconds.
Index Terms—Peer-to-peer system, live streaming, network
architecture
I. INTRODUCTION
THERE is an emerging market for IPTV. Numerous commercial
systems now offer services over the Internet that
are similar to traditional over-the-air, cable, or satellite TV.
Live television, time-shifted programming, and content-ondemand
are all presently available over the Internet. Increased
broadband speed, growth of broadband subscription base, and
improved video compression technologies have contributed to
the emergence of these IPTV services.
We draw a distinction between three uses of peer-to-peer
(P2P) networks: delay tolerant file download of archival material,
delay sensitive progressive download (or streaming) of
archival material, and real-time live streaming. In the first
case, the completion of download is elastic, depending on
available bandwidth in the P2P network. The application
buffer receives data as it trickles in and informs the user
upon the completion of download. The user can then start
playing back the file for viewing in the case of a video
file. Bittorrent and variants are example of delay-tolerant file
download systems. In the second case, video playback starts as
H. Chang is with Alcatel-Lucent Bell Labs, Holmdel, NJ 07733 USA (email:
hyunseok.chang[at]alcatel-lucent.com).
S. Jamin is with EECS Department, University of Michigan, Ann Arbor,
MI 48109 USA (e-mail: jamin[at]eecs.umich.edu).
W. Wang is with IBM Ressearch, CRL, Beijing 100193, China (e-mail:
wenjwang[at]cn.ibm.com).
This work was done when authors Chang and Wang were at Zattoo Inc.
soon as the application assesses it has sufficient data buffered
that, given the estimated download rate and the playback rate,
it will not deplete the buffer before the end of file. If this
assessment is wrong, the application would have to either
pause playback and rebuffer, or slow down playback. While
users would like playback to start as soon as possible, the
application has some degree of freedom in trading off playback
start time against estimated network capacity. Most video-ondemand
systems are examples of delay-sensitive progressivedownload
application. The third case, real-time live streaming,
has the most stringent delay requirement. While progressive
download may tolerate initial buffering of tens of seconds or
even minutes, live streaming generally cannot tolerate more
than a few seconds of buffering. Taking into account the
delay introduced by signal ingest and encoding, and network
transmission and propagation, the live streaming system can
introduce only a few seconds of buffering time end-to-end and
still be considered “live” [1].
The Zattoo peer-to-peer live streaming system was a freeto-
use network serving over 3 million registered users in eight
European countries at the time of study, with a maximum
of over 60,000 concurrent users on a single channel. The
system delivers live streams using a receiver-based, peerdivision
multiplexing scheme as described in Section II. To
ensure real-time performance when peer uplink capacity is
below requirement, Zattoo subsidizes the network’s bandwidth
requirement, as described in Section III. After delving into
Zattoo’s architecture in detail, we study in Sections IV and V
large-scale measurements collected during the live broadcast
of the UEFA European Football Championship, one of the
most popular one-time events in Europe, in June, 2008 [2].
During the course of the month of June 2008, Zattoo served
more than 35 million sessions to more than one million distinct
users. Drawing from these measurements, we report on the
operational scalability of Zattoo’s live streaming system along
several key issues:
1) How does the system scale in terms of overlay size and
its effectiveness in utilizing peers’ uplink bandwidth?
2) How responsive is the system during channel switching,
for example, when compared to the 3-second channel
switch time of satellite TV?
3) How effective is the packet retransmission scheme in
allowing a peer to recover from transient congestion?
4) How effective is the receiver-based peer-division multiplexing
scheme in delivering synchronized sub-streams?
5) How effective is the global bandwidth subsidy system
in provisioning for flash crowd scenarios?
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEB 2011
http://www.blogspot.com
http://www.ieeexploreprojects.blogspot.com
2
6) Would a peer further away from the stream source
experience adversely long lag compared to a peer closer
to the stream source?
7) How effective is error-correcting code in isolating packet
losses on the overlay?
We also discuss in Section VI several challenges in increasing
the bandwidth contribution of Zattoo peers. Finally,
we describe related works in Section VII and conclude in
Section VIII.
II. SYSTEM ARCHITECTURE
The Zattoo system rebroadcasts live TV, captured from
satellites, onto the Internet. The system carries each TV
channel on a separate peer-to-peer delivery network and is not
limited in the number of TV channels it can carry. Although
a peer can freely switch from one TV channel to another, and
thereby departing and joining different peer-to-peer networks,
it can only join one peer-to-peer network at any one time.
We henceforth limit our description of the Zattoo delivery
network as it pertains to carrying one TV channel. Fig. 1
shows a typical setup of a single TV channel carried on the
Zattoo network. TV signal captured from satellite is encoded
into H.264/AAC streams, encrypted, and sent onto the Zattoo
network. The encoding server may be physically separated
from the server delivering the encoded content onto the Zattoo
network. For ease of exposition, we will consider the two as
logically co-located on an Encoding Server. Users are required
to register themselves at the Zattoo website to download a free
copy of the Zattoo player application. To receive the signal
of a channel, the user first authenticates itself to the Zattoo
Authentication Server. Upon authentication, the user is granted
a ticket with limited lifetime. The user then presents this ticket,
along with the identity of the TV channel of interest, to the
Zattoo Rendezvous Server. If the ticket specifies that the user
is authorized to receive signal of the said TV channel, the
Rendezvous Server returns to the user a list of peers currently
joined to the P2P network carrying the channel, together with
a signed channel ticket. If the user is the first peer to join a
channel, the list of peers it receives contain only the Encoding
Server. The user joins the channel by contacting the peers
returned by the Rendezvous Server, presenting its channel
ticket, and obtaining the live stream of the channel from them
(see Section II-A for details).
Each live stream is sent out by the Encoding Server as
n logical sub-streams. The signal received from satellite is
encoded into a variable-bit rate stream. During periods of
source quiescence, no data is generated. During source busy
periods, generated data is packetized into a packet stream,
with each packet limited to a maximum size. The Encoding
Server multiplexes this packet stream onto the Zattoo network
as n logical sub-streams. Thus the first packet generated is
considered part of the first sub-stream, the second packet that
of the second sub-stream, the n-th packet that of the n-th substream.
The n+1-th packet cycles back to the first sub-stream,
etc. such that the i-th sub-stream carries the mn+i-th packets,
where m 0, 1 i n, and n a user-defined constant.
We call a set of n packets with the same index multiplier m
Rendezvous Server
Authentication Server
Feedback Server
other admin servers
Demultiplexer
Encoding
Servers
Fig. 1. Zattoo delivery network architecture.
a “segment.” Thus m serves as the segment index, while i
serves as the packet index within a segment. Each segment
is of size n packets. Being the packet index, i also serves as
the sub-stream index. The number mn + i is carried in each
packet as its sequence number.
Zattoo uses the Reed-Solomon (RS) error correcting code
(ECC) for forward error correction. The RS code is a systematic
code: of the n packets sent per segment, k < n
packets carry the live stream data while the remainder carries
the redundant data [3, Section 7.3]. Due to the variable-bit
rate nature of the data stream, the time period covered by a
segment is variable, and a packet may be of size less than the
maximum packet size. A packet smaller than the maximum
packet size is zero-padded to the maximum packet size for
the purposes of computing the (shortened) RS code, but is
transmitted in its original size. Once a peer has received k
packets per segment, it can reconstruct the remaining n − k
packets. We do not differentiate between streaming data and
redundant data in our discussion in the remainder of this paper.
When a new peer requests to join an existing peer, it
specifies the sub-stream(s) it would like to receive from the
existing peer. These sub-streams do not have to be consecutive.
Contingent upon availability of bandwidth at existing peers,
the receiving peer decides how to multiplex a stream onto
its set of neighboring peers, giving rise to our description of
the Zattoo live streaming protocol as a receiver-based, peerdivision
multiplexing protocol. The details of peer-division
multiplexing is described in Section II-A while the details of
how a peer manages sub-stream forwarding and stream reconstruction
is described in Section II-B. Receiver-based peerdivision
multiplexing has also been used by the latest version
of CoolStreaming peer-to-peer protocol though it differs from
Zattoo in its stream management (Section II-B) and adaptive
behavior (Section II-C) [4].
A. Peer-Division Multiplexing
To minimize per-packet processing time of a stream, the
Zattoo protocol sets up a virtual circuit with multiple fan outs
at each peer. When a peer joins a TV channel, it establishes
a peer-division multiplexing (PDM) scheme amongst a set of
neighboring peers, by building a virtual circuit to each of the
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEB 2011
http://www.blogspot.com
http://www.ieeexploreprojects.blogspot.com
3
neighboring peers. Baring departure or performance degradation
of a neighbor peer, the virtual circuits are maintained
until the joining peer switches to another TV channel.With the
virtual circuits set up, each packet is forwarded without further
per-packet handshaking between peers. We describe the PDM
boot strapping mechanism in this section and the adaptive
PDM mechanism to handle peer departure and performance
degradation in Section II-C.
The PDM establishment process consists of two phases:
the search phase and the join phase. In the search phase, the
new, joining peer determines its set of potential neighbors. In
the join phase, the joining peer requests peering relationships
with a subset of its potential neighbors. Upon acceptance of a
peering relationship request, the peers become neighbors and
a virtual circuit is formed between them.
Search phase. To obtain a list of potential neighbors, a
joining peer sends out a SEARCH message to a random subset
of the existing peers returned by the Rendezvous Server. The
SEARCH message contains the sub-stream indices for which
this joining peer is looking for peering relationships. The substream
indices is usually represented as a bitmask of n bits,
where n is the number of sub-streams defined for the TV
channel. In the beginning, the joining peer will be looking for
peering relationships for all sub-streams and have all the bits
in the bitmask turned on. In response to a SEARCH message,
an existing peer replies with the number of sub-streams it can
forward. From the returning SEARCH replies, the joining peer
constructs a set of potential neighbors that covers the full set of
sub-streams comprising the live stream of the TV channel. The
joining peer continues to wait for SEARCH replies until the
set of potential neighbors contains at least a minimum number
of peers, or until all SEARCH replies have been received.
With each SEARCH reply, the existing peer also returns a
random subset of its known peers. If a joining peer cannot
form a set of potential neighbors that covers all of the substreams
of the TV channel, it initiates another SEARCH round,
sending SEARCH messages to peers newly learned from the
previous round. The joining peer gives up if it cannot obtain
the full stream after two SEARCH rounds. To help the joining
peer synchronize the sub-streams it receives from multiple
peers, each existing peer also indicates for each sub-stream
the latest sequence number it has received for that sub-stream,
and the existence of any quality problem. The joining peer can
then choose sub-streams with good quality that are closely
synchronized.
Join phase. Once the set of potential neighbors is established,
the joining peer sends JOIN requests to each potential
neighbor. The JOIN request lists the sub-streams for which
the joining peer would like to construct virtual circuit with the
potential neighbor. If a joining peer has l potential neighbors,
each willing to forward it the full stream of a TV channel, it
would typically choose to have each forward only 1/l-th of the
stream, to spread out the load amongst the peers and to speed
up error recovery, as described in Section II-C. In selecting
which of the potential neighbors to peer with, the joining
peer gives highest preference to topologically close-by peers,
even if these peers have less capacity or carry lower quality
sub-streams. The “topological” location of a peer is defined
Zattoo
Peer and
Player
Application
PDM
Fig. 2. Zattoo peer with IOB.
to be its subnet number, autonomous system (AS) number,
and country code, in that order of precedence. A joining
peer obtains its own topological location from the Zattoo
Authentication Server as part of its authentication process.
The list of peers returned by both the Rendezvous Server
and potential neighbors all come attached with topological
locations. A topology-aware overlay not only allows us to
be “ISP-friendly,” by minimizing inter-domain traffic and
thus save on transit bandwidth cost, but also helps reduce
the number of physical links and metro hops traversed in
the overlay network, potentially resulting in enhanced userperceived
stream quality.
B. Stream Management
We represent a peer as a packet buffer, called the IOB,
fed by sub-streams incoming from the PDM constructed as
described in Section II-A.1 The IOB drains to (1) a local
media player if one is running, (2) a local file if recording
is supported, and (3) potentially other peers. Fig. 2 depicts
a Zattoo player application with virtual circuits established to
four peers. As packets from each sub-stream arrive at the peer,
they are stored in the IOB for reassembly to reconstruct the
full stream. Portions of the stream that have been reconstructed
are then played back to the user. In addition to providing
a reassembly area, the IOB also allows a peer to absorb
some variabilities in available network bandwidth and network
delay.
The IOB is referenced by an input pointer, a repair pointer,
and one or more output pointers. The input pointer points
to the slot in the IOB where the next incoming packet with
sequence number higher than the highest sequence number
1In the case of the Encoding Server, which we also consider a peer on the
Zattoo network, the buffer is fed by the encoding process.
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEB 2011
http://www.blogspot.com
http://www.ieeexploreprojects.blogspot.com
4
received so far will be stored. The repair pointer always
points one slot beyond the last packet received in order and is
used to regulate packet retransmission and adaptive PDM as
described later. We assign an output pointer to each forwarding
destination. The output pointer of a destination indicates the
destination’s current forwarding horizon on the IOB. In accordance
to the three types of possible forwarding destinations
listed above, we have three types of output pointers: player
pointer, file pointer, and peer pointer. One would typically
have at most one player pointer and one file pointer but
potentially multiple concurrent peer pointers, referencing an
IOB. The Zattoo player application does not currently support
recording.
Since we maintain the IOB as a circular buffer, if the
incoming packet rate is higher than the forwarding rate of a
particular destination, the input pointer will overrun the output
pointer of that destination. We could move the output pointer
to match the input pointer so that we consistently forward the
oldest packet in the IOB to the destination. Doing so, however,
requires checking the input pointer against all output pointers
on every packet arrival. Instead, we have implemented the IOB
as a double buffer. With the double buffer, the positions of the
output pointers are checked against that of the input pointer
only when the input pointer moves from one sub-buffer to the
other. When the input pointer moves from sub-buffer a to subbuffer
b, all the output pointers still pointing to sub-buffer b are
moved to the start of sub-buffer a and sub-buffer b is flushed,
ready to accept new packets. When a sub-buffer is flushed
while there are still output pointers referencing it, packets that
have not been forwarded to the destinations associate with
those pointers are lost to them, resulting in quality degradation.
To minimize packet lost due to sub-buffer flushing, we would
like to use large sub-buffers. However, the real-time delay
requirement of live streaming limits the usefulness of late
arriving packets and effectively puts a cap on the maximum
size of the sub-buffers.
Different peers may request for different numbers of, possibly
non-consecutive, sub-streams. To accommodate the different
forwarding rates and regimes required by the destinations,
we associate a packet map and forwarding discipline with each
output pointer. Fig. 3 shows the packet map associated with an
output peer pointer where the peer has requested sub-streams
1, 4, 9, and 14. Every time a peer pointer is repositioned
to the beginning of a sub-buffer of the IOB, all the packet
slots of the requested sub-streams are marked NEEDed and
all the slots of the sub-streams not requested by the peer are
marked SKIP. When a NEEDed packet arrives and is stored
in the IOB, its state in the packet map is changed to READY.
As the peer pointer moves along its associated packet map,
READY packets are forwarded to the peer and their states
changed to SENT. A slot marked NEEDed but not READY,
such as slot n + 4 in Fig. 3, indicates that the packet is lost
or will arrive out-of-order and is bypassed. When an out-oforder
packet arrives, its slot is changed to READY and the
peer pointer is reset to point to this slot. Once the out-of-order
packet has been sent to the peer, the peer pointer will move
forward, bypassing all SKIP, NEED, and SENT slots until it
reaches the next READY slot, where it can resume sending.
SKIP NEED
SENT READY
1 n
segment 0
4 9 14
segment m-1
Fig. 3. Packet map associated with a peer pointer.
Peer0
Peer1
Player
File
input
pointer
...
...
Packet
Map
Packet
Map
Packet
Map
segment 0
segment m-1
segment size: n
sub-buffer 0
sub-buffer 1
received packet empty slot
segment 0
segment m-1
IOB
Packet
Map
repair
pointer
Fig. 4. IOB, input/output pointers and packet maps.
The player pointer behaves the same as a peer pointer except
that all packets in its packet map will always start out marked
NEEDed.
Fig. 4 shows an IOB consisting of a double buffer, with an
input pointer, a repair pointer, and an output file pointer, an
output player pointer, and two output peer pointers referencing
the IOB. Each output pointer has a packet map associated
with it. For the scenario depicted in the figure, the player
pointer tracks the input pointer and has skipped over some
lost packets. Both peer pointers are lagging the input pointer,
indicating that the forwarding rates to the peers are bandwidth
limited. The file pointer is pointing at the first lost packet.
Archiving a live stream to file does not impose real-time delay
bound on packet arrivals. To achieve the best quality recording
possible, a recording peer always waits for retransmission of
lost packets that cannot be recovered by error correction.
In addition to achieving lossless recording, we use retransmission
to let a peer recover from transient network
congestion. A peer sends out a retransmission request when
the distance between the repair pointer and the input pointer
has reached a threshold of R packet slots, usually spanning
multiple segments. A retransmission request consists of an R-
bit packet mask, with each bit representing a packet, and the
sequence number of the packet corresponding to the first bit.
Marked bits in the packet mask indicate that the corresponding
packets need to be retransmitted. When a packet loss is
detected, it could be caused by congestion on the virtual
circuits forming the current PDM or congestion on the path
beyond the neighboring peers. In either case, current neighbor
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEB 2011
http://www.blogspot.com
http://www.ieeexploreprojects.blogspot.com
5
peers will not be good sources of retransmitted packets. Hence
we send our retransmission requests to r random peers that are
not neighbor peers. A peer receiving a retransmission request
will honor the request only if the requested packets are still
in its IOB and it has sufficient left-over capacity, after serving
its current peers, to transmit all the requested packets. Once a
retransmission request is accepted, the peer will retransmit all
the requested packets to completion.
C. Adaptive PDM
While we rely on packet retransmission to recover from
transient congestions, we have two channel capacity adjustment
mechanisms to handle longer-term bandwidth fluctuations.
The first mechanism allows a forwarding peer to adapt
the number of sub-streams it will forward given its current
available bandwidth, while the second allows the receiving
peer to switch provider at the sub-stream level.
Peers on the Zattoo network can redistribute a highly
variable number of sub-streams, reflecting the high variability
in uplink bandwidth of different access network technologies.
For a full-stream consisting of sixteen constant-bit rate substreams,
our prior study show that based on realistic peer
characteristics measured from the Zattoo network, half of the
peers can support less than half of a stream, 82% of peers can
support less than a full-stream, and the remainder can support
up to ten full streams (peers that can redistribute more than
a full stream is conventionally known as supernodes in the
literature) [5]. With variable-bit rate streams, the bandwidth
carried by each sub-stream is also variable. To increase peer
bandwidth usage, without undue degradation of service, we
instituted measurement-based admission control at each peer.
In addition to controlling resource commitment, another goal
of the measurement-based admission control module is to
continually estimate the amount of available uplink bandwidth
at a peer.
The amount of available uplink bandwidth at a peer is
initially estimated by the peer sending a pair of probe packets
to Zattoo’s Bandwidth Estimation Server. Once a peer starts
forwarding sub-streams to other peers, it will receive from
those peers quality-of-service feedbacks that inform its update
of available uplink bandwidth estimate. A peer sends qualityof-
service feedback only if the quality of a sub-stream drops
below a certain threshold.2 Upon receiving quality feedback
from multiple peers, a peer first determines if the identified
sub-streams are arriving in low quality. If so, the low quality of
service may not be caused by limit on its own available uplink
bandwidth; in which case, it ignores the low quality feedbacks.
Otherwise, the peer decrements its estimate of available uplink
bandwidth. If the new estimate is below the bandwidth needed
to support existing number of virtual circuits, the peer closes
2Depending on a peer’s NAT and/or firewall configuration, Zattoo uses
either UDP or TCP as the underlying transport protocol. The quality of a substream
is measured differently for UDP and TCP. A packet is considered lost
under UDP if it doesn’t arrive within a fixed threshold. The quality measure
for UDP is computed as a function of both the packet lost rate and the burst
error rate (number of contiguous packet losses). The quality measure for TCP
is defined to be how far behind a peer is, relative to other peers, in serving
its sub-streams.
a virtual circuit. To reduce the instability introduced into the
network, a peer closes first the virtual circuit carrying the
smallest number of sub-streams.
A peer attempts to increase its available uplink bandwidth
estimate periodically: if it has fully utilized its current estimate
of available uplink bandwidth without triggering any bad
quality feedback from neighboring peers. A peer doubles the
estimated available uplink bandwidth if current estimate is
below a threshold, switching to linear increase above the
threshold, similar to how TCP maintains its congestion window
size. A peer also increases its estimate of available uplink
bandwidth if a neighbor peer departs the network without any
bad quality feedback.
When the repair pointer lags behind the input pointer by R
packet slots, in addition to initiating a retransmission request,
a peer also computes a loss rate over the R packets. If the
loss rate is above a threshold, the peer considers the neighbor
slow and attempts to reconfigure its PDM. In reconfiguring
its PDM, a peer attempts to shift half of the sub-streams
currently forwarded by the slow neighbor to other existing
neighbors. At the same time, it searches for new peer(s) to
forward these sub-streams. If new peer(s) are found, the load
will be shifted from existing neighbors to the new peer(s).
If sub-streams from the slow neighbor continues to suffer
after the reconfiguration of the PDM, the peer will drop the
neighbor completely and initiate another reconfiguration of the
PDM. When a peer loses a neighbor due to reduced available
uplink bandwidth at the neighbor or due to neighbor departure,
it also initiates a PDM reconfiguration. A peer may also
initiate a PDM reconfiguration to switch to a topologically
closer peer. Similar to the PDM establishment process, PDM
reconfiguration is accomplished by peers exchanging substream
bitmasks in a request/response handshake, with each
bit of the bitmask representing a sub-stream. During and after
a PDM reconfiguration, slow neighbor detection is disabled
for a short period of time to allow for the system to stabilize.
III. GLOBAL BANDWIDTH SUBSIDY SYSTEM
Each peer on the Zattoo network is assumed to serve a
user through a media player, which means that each peer
must receive, and can potentially forward, all n sub-streams
of the TV channel the user is watching. The limited redistribution
capacity of peers on the Zattoo network means that
a typical client can contribute only a fraction of the substreams
that make up a channel. This shortage of bandwidth
leads to a global bandwidth deficit in the peer-to-peer network.
Whereas bittorrent-like delay-tolerant file downloads or
the delay-sensitive progressive download of video-on-demand
applications can mitigate such global bandwidth shortage by
increasing download time, a live streaming system such as
Zattoo’s must subsidize the bandwidth shortfall to provide
real-time delivery guarantee.
Zattoo’s Global Bandwidth Subsidy System (or simply, the
Subsidy System), consists of a global bandwidth monitoring
subsystem, a global bandwidth forecasting and provisioning
subsystem, and a pool of Repeater nodes. The monitoring
subsystem continuously monitors the global bandwidth requirement
of a channel. The forecasting and provisioning
IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 19, NO. 1, FEB 2011
http://www.blogspot.com
http://www.ieeexploreprojects.blogspot.com
6
subsytem projects global bandwidth requirement based on
measured history and allocates Repeater nodes to the channel
as needed. The monitoring and provisioning of global
bandwidth is complicated by two highly varying parameters
over time, client population size and peak streaming rate, and
one varying parameter over space, available uplink bandwidth,
which is network-service provider dependent. Forecasting of
bandwidth requirement is a vast subject in itself. Zattoo
adopted a very simple mechanism, described in Section III-B
which has performed adequately in provisioning the network
for both daily demand fluctuations and flash crowds scenarios
(see Section IV-C).
When a bandwidth shortage is projected for a channel, the
Subsidy System assigns one or more Repeater nodes to the
channel. Repeater nodes function as bandwidth multiplier, to
amplify the amount of available bandwidth in the network.
Each Repeater node serves at most one channel at a time;
it joins and leaves a given channel at the behest of the
Subsidy System. Repeater nodes receive and serve all n
sub-streams of the channel they join, run the same PDM
protocol, and are treated by actual peers like any other peers
on the network; however, as bandwidth amplifiers, they are
usually provisioned to contribute more uplink bandwidth than
the download bandwidth they consume. The use of Repeater
nodes makes the Zattoo network a hybrid P2P and content
distribution network.
We next describe the bandwidth monitoring subsystem of
the Subsidy System, followed by design of the simple bandwidth
projection and Repeater node assignment subsystem.
A. Global Bandwidth Measurement
The capacity metric of a channel is the tuple (D,C),
where D is the aggregate download rates required by all
users on the channel, and C is the aggregate upload capacity
of those users. Usually C < D and the difference between
the two is the global bandwidth deficit of the channel. Since
channel viewership changes over time as users join or leave
the channel, we need a scalable means to measure and update
the capacity metric. We rely on aggregating the capacity
metric up the peer division multiplexing tree. Each peer in the
overlay periodically aggregates the capacity metric reported
by all its downstream receiver peers, adds its own capacity
measure (D,C) to the aggregate, and forwards the resulting
capacity metric upstream to its forwarding peers. By the time
the capacity metric percolates up to the Encoding Server, it
contains the total download and upload rate aggregates of the
whole streaming overlay. The Encoding Server then simply
forwards the obtained (D,C) to the Subsidy Server.
B. Global Bandwidth Projection and Provisioning
For each channel, the Subsidy Server keeps a history of the
capacity metric (D,C) reports received from the channel’s
Encoding Server. The channel utilization ratio (U) is the ratio
D over C. Based on recent movements of the ratio U, we
classify the capacity trend of each channel into the following
four categories.
• Stable: the ratio U has remained within [S-, S+] for
the past Ts reporting periods.
• Exploding: the ratio U increased by at least E between
Te (e.g., Te = 2) reporting periods.
• Increasing: the ratio U has steadily increased by I (I
E) over the past Ti reporting periods.
• Falling: the ratio U has decreased by F over the past Tf
reporting periods.
Orthogonal to the capacity-trend based classification above,
each channel is further categorized in terms of its capacity
utilization ratio as follows.
• Under-utilized: the ratio U is below the low threshold
L, e.g., U 0.5.
• Near Capacity: the ratio U is almost 1.0, e.g., U 0.9.
If the capacity trend of a channel has been “Exploding,” one
or more Repeater nodes will be assigned to it immediately. If
the channel’s capacity trend has been “Increasing,” it will be
assigned a Repeater node with a smaller capacity. The goal
of the Subsidy System is to keep a channel below “Near
Capacity.” If a channel’s capacity trend is “Stable” and the
channel is “Under-utilized,” the Subsidy System attempts to
free Repeater nodes (if any) assigned to the channel. If a
channel’s capacity utilization is “Falling,” the Subsidy System
waits for the utilization to stabilize before reassigning any
Repeater nodes.
Each Repeater node periodically sends a keep-alive message
to the Subsidy System. The keep-live message tells the Subsidy
System which channel the Repeater node is serving, plus
its CPU and capacity utilization ratio. This allows the Subsidy
System to monitor the health of Repeater nodes and to increase
the stability of the overlay during Repeater reassignment.
When reassigning Repeater nodes from a channel, the Subsidy
System will start from the Repeater node with the lowest
utilization ratio. It will notify the selected Repeater node to
stop accepting new peers and then to leave the channel after
a specified time.
In addition to Repeater nodes, the Subsidy System may
recognize extra capacity from idle peers whose owners are
not actively watching a channel. However, our previous study
shows that a large number of idle peers are required to make
any discernible impact on the global bandwidth deficit of a
channel [5]. Our current Subsidy System therefore does not
solicit bandwidth contribution from idle peers.