Peer-to-peer (P2P) file sharing has become increasingly popular,
accounting for as much as 70% of Internet traffic by some estimates. Recently,
we have been witnessing the emergence of a new class of popular P2P applications,
namely, P2P audio and video streaming. While traditional P2P file distribution
applications target elastic data transfers, P2P streaming focuses on the
efficient delivery of audio and video content under tight timing requirements.
Still in its infancy, both live and on-demand P2P streaming have the potential
of changing the way we watch TV, providing ubiquitous access to a vast
number of channels, personalizing your TV experience and enabling roaming
TV services. For a long time, traditional approaches that are client/server
based e.g., Akamai (Akamai) have been used for streaming multimedia applications
over the Internet.
Over the past few years, P2P networks have emerged as a promising approach
for distribution of multimedia content over a network. Some P2P network
related researches are by the following authors (Guo et al., 2003;
Hefeeda et al., 2003; Padmanabhan et al., 2003; Ye and Makedon,
2004; Zhang et al., 2005). One form of P2P network, the peer-to-peer
overlay, offers a promising approach to support one-to-many multimedia
streaming applications without any special support from the network, called
P2P streaming. The basic building blocks for P2P streaming, called nodes
or peers, are no longer passive receivers of data but instead can act
both as clients and servers at the same time. Stream data are simultaneously
received, played and passed to other connected peers. The goal of P2P
streaming mechanisms is to maximize delivered quality to individual peers
in a scalable fashion despite the heterogeneity and asymmetry of their
access link bandwidth. An effective P2P streaming mechanism depends on
the effective utilization of the outgoing bandwidth of most participating
In live P2P streaming, the media stream is a continuous flow of media
data encoded from the streaming server. Media content generated must be
delivered to participating nodes under a tight time constraint. Nodes
should be able to receive media content before the playout deadline or
the media content will be considered obsolete and discarded.
In this study, we propose and study the self-organizing, decentralized
protocol capable of building and maintaining two-layer super-peer based,
overlay topologies for P2P streaming live and non-interactive media streaming,
called PALMS-SP (P2P Super-Peer based Unstructured Live Media Streaming).
Similar to DONet (Zhang et al., 2005), PALMS-SP is based on data-driven
and receiver-based that is built on a super-peer based two-layer unstructured
overlay media streaming. PALMS-SP is designed to operate in conditions
where nodes have heterogeneous bandwidths and resources. PALMS-SP defines
the two layers network to simplify the complexity of streaming services.
The existence of super-peers makes the network to be more effective because
they combine the efficiency of the centralized client-server model with
the autonomy, load balancing and robustness of distributed search. They
also take advantage of the heterogeneity of capabilities across peers.
Generally, super-peers are nodes that are faster and/or more reliable
than ordinary nodes that take on server-like responsibilities and provide
services to a set of clients. Super-peers allow decentralized networks
to run more efficiently by exploiting heterogeneity and distributing load
to machines that can handle the burden. On the other hand, this architecture
does not inherit the flaws of the client/server model, as it allows multiple,
separate points of failure, increasing the health of the P2P network.
In comparison to DONet, which only employs pure pull method for packet
scheduling, PALMS-SP employs a combination of two methods for media streaming,
namely the pull method and push method.
OVERVIEW OF PALMS-SP
PALMS-SP is based on data-driven and receiver-based unstructured
two-layer super-peer based overlay media streaming. It is designed to
operate in scenarios where the nodes have heterogeneous and variable bandwidth
resources. For the ease of exposition, we refer to the media source as
the streaming server and receivers as ordinary peer. The term peers and
nodes are interchangeable and refer to the all the ordinary peers. We
consider a network consisting of a large collection of nodes. The network
is highly dynamic; new nodes may join at any time and existing nodes may
leave, either voluntarily or by crashing.
PALMS-SP consists of three major components: (i) overlay construction
mechanism, which organizes participating peers into a two-layer super-peer
based overlay; (ii) streaming scheduling mechanism, which determines the
delivery of content from the streaming source to individual nodes through
the overlay and (iii) super-peer management mechanism, which determines
which nodes may switch role at will from a ordinary peer to super-peer
status. In the following subsections, we describe these components in
OVERLAY CONSTRUCTION MECHANISM
In PALMS-SP, nodes are functionally identical. They are free to
exchange control information and media content data from the stream. Each
peer maintains a certain number of connected nodes that are known as neighbors.
Each node can potentially communicate with every other node in the network.
Each node receives media content from a certain number of neighbor nodes
and relays the content to a certain number of neighbor nodes. Nodes are
heterogeneous: they differ in their computational, storage capabilities
and bandwidth. Nodes may act as super-peers or ordinary nodes. Each super-peer
SP is associated with a capacity value max(SP) that represents the maximum
number of ordinary nodes associated to a super-peer SP.
The basic task of the overlay construction mechanism component for each
node is to be in charge of finding appropriate super-peer and neighbors
for each node through the gossip method so that the application layer
network can be successfully built up. To join the streaming session, a
new peer contacts the bootstrapping node, (streaming server in the case
of PALMS-SP) to learn about super-peers and other participating peers
upon arrival. Streaming server is selected as streaming server persists
during the lifetime of streaming and its identifier/address is universally
known. This could be regarded as the login/bootstrapping process. The
bootstrapping node returns a list of selected super-peers that can potentially
serve as parent nodes. The new peer contacts these potential super-peers
to determine whether they are able to accommodate a new child node. This
is by determining whether the super-peer still has enough allocation slots
on the outgoing degree. In the case of PALMS-SP, each peer is associated
to exactly one and only super-peer. The number of child nodes associated
to a super-peer is pre-determined. As shown in Fig. 1,
an overlay network consists of two layers, namely ordinary peerslayer
(lower) and super-peer (higher) layers. The ordinary peer and super-peer
layers are composed of a set of ordinary peers and a set of super-peers,
respectively. A collection of a super-peer SP and its ordinary peers OP1,
OP2, ..., OPn(n≥1) and it is referred to as a
cluster OPi. A super-peer SPj is connected with
another super-peer OPj at the super-peer layer.
The PALMS-SP topology can be summarized as the following:
||Each node is either super-peer or a normal peer
||Each ordinary peer OP is associated to exactly one super-peer SP
||The number of ordinary nodes associated to a super-peer SP does
not exceed max(SP).
In traditional super-peer networks shown in Fig. 2,
ordinary peers in a cluster cannot directly communicate with each other.
The ordinary peers have to communicate with each other through super-peer
in the cluster. It takes at least two hops to delivery message from an
ordinary peer to another ordinary peer. In this study, we assume each
ordinary peer can directly communicate with every neighbor peer in a cluster.
Because of this assumption, the number of communication between a super-peer
and its ordinary peers can be reduced and the super-peer has a lighter
||Traditional super-peer network
Each node has a member table that contains a list of neighbor nodes obtained
from the super-peer. The information in member tables is encapsulated
into a UDP packet and exchanged among neighbors periodically. Each node
updates its member table in accordance with the member table sent by its
neighbors. A super-peer SP holds all the information on service of every
ordinary peer in a cluster CSP. Each node sends a periodical
heartbeat message to update its super-peer. If a node does not update
its super-peer periodically, it will be removed from the member table.
Once a node leaves, super-peer will broadcast a leave message to all its
ordinary peers within its cluster. The nodes that receive this message
will delete the respective node from its member table as well. Therefore,
the failure of any neighbors can be detected by constantly monitoring
periodical messages from super-peer.
In order to locate a better neighbor, which has higher uplink, a peer
in PALMS-SP periodically replaces the neighbor with the least contribution
by selecting nodes with higher scores (the ratio of uploaded packets over
downloaded packets). This operation helps each node maintain a stable
number of partners in the presence of node departures and it also helps
to discourage the existence of free riders within the network.
PALMS-SP employs a swarm-like content delivery mechanism that is
similar to BitTorrent (Cohen, 2003). Nodes in the swarm protocol will
be attracted to nodes that possess newly generated content. The main advantages
of swarming content delivery is its ability to effectively utilize the
outgoing bandwidth of participating peers and its robustness against the
dynamics of peers arrival and departure, which is also known as churn.
The streaming scheduling mechanism of each node is responsible for exchanging
packets with all its neighbors. Swarm-like content delivery is incorporated
in PALMS-SP. Each peer periodically generates a report i.e., buffer map
of its newly received packets and sends it to its neighbor nodes. Each
peer periodically requests a subset of required packets from each neighbor
node based on the reports received. The pull method is deployed to fetch
absent packets from its neighbor nodes and in turn tries its best to deliver
packets requested by the neighbors. Packets requested by the pull method
are determined by the packet scheduling algorithm, which is much similar
to the data-driven approach in DONet (Zhang et al., 2005).
Every node maintains a window of interest, which is the set of sequence
packets that the node is interested in acquiring at the current time.
Figure 3 shows the fundamental concept of the sliding
window. A sliding window of availability contains the list of segments
available for each node. This is the information for the buffer map shared
with other neighbor nodes. The node slides its window of interest forward
over time as new packets stream in. If a packet has not been received
by the time it falls off the trailing edge of the window, the node will
consider that packet lost or obsolete and will no longer try to acquire
it. Figure 4 shows the buffer state of a node at a specific
To accommodate the bandwidth heterogeneity among peers, the content is
encoded with Multiple Description Coding (MDC). Generally, MDC organizes
the streaming content into several sub-streams where each sub-stream can
independently decoded. The use of MDC for video streaming has been widely
studied. Padmanabhan et al. (2003) propose that introducing redundancy
can provide robustness in media streaming (Padmanabhan et al.,
2003). The delivered quality to each peer is proportional to the number
of independent sub-streams it receives. With MDC coding, each peer is
able to receive the proper number of sub-streams that are delivered through
the combination push-pull streaming mechanism.
||Data buffer for PALMS-SP node
||Buffer state of a node
SUPER-PEER MANAGEMENT MECHANISM
At the super-peer layer, a super-peer is connected with other super-peers
in a flat unstructured overlay network. The ordinary peer and super-peer
layers are composed of a set of ordinary peers and a set of super-peers,
respectively. One of the main obstacles for super-peers network is the
super-peer selection. The super-peer selection problem is highly challenging
because in the peer-to-peer environment, a large number of super-peers
must be selected from a huge and dynamically changing network in which
neither the node characteristics nor the network topology is known priori.
Thus, simple strategies such as random selection don`t work. Super-peer
selection is more complex that classic dominating set and p-centers from
graph theory, known as the NP-hard problems, because it must respond to
the dynamicity of nodes join and leave (churn) and function in an environment
that is highly heterogeneous.
The best know example of super-peer selection in a peer-to-peer application
is the gnutella (Gnutella, 2003) protocol for selection of ultrapeers
- peers with sufficient bandwidth and processing power to serve as proxies
for other peers. The use of ultrapeers reduces network traffic and speeds
up content delivery. In gnutella, any peer can select itself as an ultrapeer
if it meets the following requirements: it has been up for at least 5
min, has high bandwidth, sufficient processing power, able to handle a
large number of simultaneous TCP connections and if not behind any firewall
or NAT. The ultrapeer selection protocol dynamically adjusts the number
of super-peers as follows: if a leaf peer cannot find an ultrapeer with
free slots, it can promote itself to be an ultrapeer. Ultrapeers also
can downgrade themselves when they are no longer serving as any leaf nodes,
or through negotiation with nearby peers. In term of cluster size, there
is a tradeoff between aggregate and individual load. It is good to choose
a cluster size that is small enough to keep a reasonable individual load
and provide reliability to the system, but large enough to avoid the knee
in aggregate load when cluster size is small. For PALMS-SP, we employ
a simple heuristic protocol for super-peer selection.
We adopt the super-peer selection protocol which is similar to the H2O
(Hierarchical 2-level Overlay) (Lo et al., 2005) protocol for super-peer
selection. H2O is an advertisement-based super-peer selection
protocol that is deployable in an unstructured overlay network. H2O
uses a classic advertisement-based protocol, in which super-peers advertise
super-peer information and ordinary peers cache these advertisements.
Ordinary peers can then choose to join the best super-peer using locally
cached information. This protocol gives full autonomy to both super-peer
and ordinary peers, allowing each to negotiate using its own local policy.
H2O is similar in many ways to the gnutella protocol, but allows
for finer-grained control over the super-peer selection process e.g.,
it can consider trust, secure paths and routing performance.
The basic idea behind super-peers management mechanism for PALMS-SP is
simple and intuitive. Ordinary peers with similar locality e.g., IP addresses
are connected to the same super-peer. At the initial stage, all nodes
start as ordinary peers. Nodes may switch role at will. The decision process
is completely decentralized. An ordinary peer selects one super-peer to
send queries and share resources. Since the ordinary peer depends on super-peer`s
capabilities, the ordinary peer should select the super-peer which can
provide it with the best service. There are many metrics that may be used
to select the best super-peer, such as average response time, bandwidth,
processing capabilities, storage and so on. These metrics may have different
weights depending on the objective. For PALMS-SP, we focus on response
time, bandwidth and processing capabilities. In order to be selected as
super-peer, ordinary peer must obtain reasonable scores for all the metrics.
A super-peer can switch back to ordinary peer role only when a super-peer
has lost all its clients due to nodes leaving or crashing. Super-peers
exchange connected ordinary peers information at the super-layer. Information
of connected ordinary peers is encapsulated into a UDP packet and exchanged
among super-peers periodically.
The algorithms presented in this section make up the core of the
PALMS-SP system. They determine how each node chooses its partner for
data exchange, how data packets to be sent are chosen and scheduled, which
data packets are to be requested from each connected neighbor and data
to be pushed by connected super-peers.
Given the buffer maps of a node and that of its partners, a schedule
is to be generated for the pull and push mechanisms for fetching the expected
packets from the partners, sending packets to connected neighbors and
re-transmission of lost packets. Simple heuristic algorithms are used
for both pull and push mechanisms.
The main algorithms used for peer selection for pull and push mechanisms
are an altruistic algorithm.
Pull mechanism: The algorithm for pull mechanism is similar to
the heuristic used in DONet (Zhang et al., 2005) and BitTorrent
(Cohen, 2003). The main purpose of the pull method is to request the rarest
packets among those that are locally available and to distribute the request
across different possible suppliers. The pull algorithm is shown in Fig.
Using the information gathered from the buffer mapexchanged among neighbor
sets, packets that are rarest across the neighborhood are requested with
higher priority than more common ones. Packets with the same number of
suppliers are randomly requested from one of the neighbors that can provide
them. This is to limit the load on any single peer.
||Pull method Heuristic algorithm
Pull mechanism: The push mechanism is the process of packet delivery
by a super-peers to connected clients. Inspired by the work conducted
by Banerjee et al. (2006), the push mechanism for PALMS-SP employs
two simple techniques too. In a nutshell, the push mechanism consists
of a proactivecomponent where data packets are pushed forward by super-peer
to connected clients and a reactivemechanism where packets are pushed
forward based NACKs information received.
In order to increase delivery ratio, each super-peer at the super-peers
layer, proactively send data packets to connected ordinary peers. The
priority of data packets to be pushed is based on the Least Frequently
Used (LFU) policy. Due to the unreliability of the network link or a neighbor
failure, some of the packets are lost during transmission. An overlay
node can detect missing packet using gaps in the packet sequence numbers.
This information is used to trigger NACK-based re-transmission through
the next interval of push mechanism for the super-peer. Thus, with the
help of the push mechanism, packets are pushed and received at the receiver
nodes at a second time interval. A good selection strategy is required
to distribute the packets. This is to ensure that each super-peer pushes
packets that are not too close to the playout deadline and helps to reduce
redundancy in push packets. Push packets also take into account the NACK
requests from connected nodes. The push algorithm is shown in Fig.
||Push method algorithm
For the push packet scheduling, in order to reduce redundancy, each super-peer
tries to allocate packets that are Least Frequently Used (LFU) into the
Super-Peer Packet Map, SPPm to be pushed. A Super-Peer Packet Map, SPPm
consists of node id and packet sequence number. A simple roulette wheel
selection scheme is applied for the next time interval for each super-peer
to push the available packets. Packets with the highest time-stamp or
least sent will be given higher priority to be allocated into the Super-Peer
Packet Map, SPPm. Each super-peer keeps a counter of how many times each
packet is sent. Packets with the least number of times sent will be chosen.
In addition to that, packets that required re-transmission based on NACKs
received will be allocated into the Super-peer Packet Map, SPPm.
Here, we perform extensive simulations to study the performance
of PALMS-SP. Simulations on the algorithms` behavior test for under different
user arrival/departure patterns, different network sizes, bandwidth distributions
and streaming rates using network simulator ns-2 (Network Simulator).
Video data: The length of the video is 120 min (a typical length
for a movie).
Video coding: We used a video stream that is MDC encoded with
5 descriptions. For simplicity, we assume that all descriptions have the
same constant bit rate of 100 Kbps. Therefore, the rate of the full quality
version of the stream is 500 Kbps.
Peer parameters: The incoming access link bandwidths for all peers
are set to 500 Kbps. The incoming access links of all peers are set to
500 Kbps so that each peer can easily receive the full quality playback
rate. The buffer length is set to 30 seconds. In all our experiments we
use a heartbeat period of 5 seconds for all simulated protocols.
The interval for the next round of push mechanism is set for every 5 sec.
Network topology: Topology is generated by using Georgia Tech
Internetwork Topology Models (GT-ITM) generator (Zegura, 1996). The delay
on the access links are randomly selected between 5 to 25 ms. Each super-peer
is connected to 10 ordinary peers in a cluster. A link between a super-peer
and a normal peer is symmetric. A link between super-peers may be asymmetric
because super-peers neighboring to a super-peer are randomly selected.
Performance metrics: We use three basic Quality of Service (QoS)
performance metrics, i.e., Average Delivery Ratio, Delivery Latency and
RESULTS AND DISCUSSION
We have examined the impact of heterogeneous bandwidths and different
nodes arrival/departure patterns on the performance of PALMS-SP streaming.
We also study the three metrics of interest: Delivery quality, Delivery
latency and Data overheads. We compare the push-pull protocol performance
of PALMS-SP with DONet (Zhang et al., 2005) and Chainsaw (Pai et
al., 2005). Both DONet and Chainsaw employ pure pull mechanism. DONet
employs a rarest-first strategy as the block scheduling method and select
suppliers with the most surplus bandwidth and enough available time first.
Chainsaw uses a purely random strategy to decide what blocks to request
Delivery quality: Figure 7a shows the average
delivery ratio for PALMS-SP in comparison to DONet and Chainsaw. We define
delivery ratio to represent the number of packets that arrive at each
node before playback deadline over the total of number of packets encoded.
We set the streaming rate as 500 kbps. From the result, we can observe
that the performances for PALMS-SP and DONet remain almost the same when
group size increases. This is an indication that the performance of swarming
based protocols or data-driven protocols is not affected by group size.
In other words, swarming protocols have a good scalability. However, Chainsaw
method decreases more in comparison to PALMS-SP and DONet. As shown in
Fig. 7a, PALMS-SP has 20% gains compared to DONet and
over 45% gains compared to Chainsaw.
||Delivery ratio as a function to group size
||Average delivery ratio as a function to on/off period, t (sec),
group size: 1000
We also tested the performances of PALMS-SP in comparison to DONet and
Chainsaw under dynamic network environment. We set all the nodes to join
in an initialization period of around 1 min and then we set each node
changes its status according the ON/OFF model. The node actively participates
the overlay during the ON period and leaves (or fails) during the OFF
period. Both ON and OFF periods are exponentially distributed. Figure
7b shows that a shorter ON/OFF period leads to a lower delivery ratio.
However, the overall delivery ratio for PALMS is higher in comparison
to DONet and Chainsaw because the additional push mechanism employed at
the super-peer layer is able to help to recover from a vast majority of
losses. Note that Chainsaw displays the poorest performance in term of
Delivery latency: In Fig. 8a we show the distribution
of latency experienced by data packets at the different overlay nodes.
In this experiment, we measure the average time for first packet arrival
for all simulated protocols. Note that all protocols suffer an increase
in average time of first packet arrival, stabilize, then stay relatively
constant with the number of nodes. The increase is well identified and
is due to the implementation of swarming protocols for PALMS-SP and DONet.
As compared to DONet, the existence of super-peers and push protocol in
PALMS-SP, packets have higher chances to be delivered to connected clients
in a shorter period of time.
Different streaming rate: Figure 8b shows that
as the streaming rate increases, the delivery ratio for PALM-SP remains
at a relatively high delivery ratio. Even when the streaming rate reaches
500 Kbps, its delivery ratio still remain above 80%. This reveals that
the network capacity of PALMS-SP is sufficient to support the streaming
session with streaming rate of 250-500 Kbps. As shown in Fig.
8b, PALMS-SP has 3% gains of delivery ratio compared to DONet and
over 13% gains compared to Chainsaw.
Data overheads: Here, we compare the overheads of PALMS-SP to
DONet. Table 1 shows that PALMS-SP incurs very low additional
data overheads in comparison to DONet. Control overhead is defined as
the ratio of control traffic over video traffic. The control overheads
at different overlay nodes increase log-arithmically with the increase
in group size. The control overheads for PALMS-SP are slightly higher
due to the additional messages such as Super-Peer Packet Map messages
and NACKs. However the amount of increase at each overlay node is essentially
minor, less than 3% of the total overall traffic. We believe the data
overheads for PALMS-SP can be further reduced by increasing the window
size. It can be observed that the control overhead has little relationship
with the group size because each node only communicates with its neighbors
and super-peer, which demonstrates the good scalability of our proposed
||Average time for arrival of first packet
||Average delivery ratio as a function to streaming rate. Group size:
||Comparison of control overheads and delivery ratio for PALMS-SP
and DONet with varying group sizes
These results confirm the expected advantages of the proposed model PALMS-SP
for P2P live media streaming.
In this study we presented PALMS-SP, a two-layer super-peer based P2P system
for live media streaming. Our system`s innovative and simple features are designed
with the usage of the combination push-pull protocol and the presence of two-layer
super-peer based overlay network that leverages on the heterogeneity of connected
On order to successfully deploy PALMS-SP streaming services, we proposed
push-pull mechanism to address the issue of delivery quality and delivery
latency. In this framework, the existence of super-peers improves delivered
video quality by incorporating the proactive and the reactive push packets
We evaluated the performance of PALMS-SP in comparison to DONet and Chainsaw.
Our simulations conducted over ns-2 demonstrated that PALMS-SP delivers
quite a good playback quality even under formidable network conditions
i.e., heterogeneity of network bandwidths, different user arrival/departure
patterns, different network sizes and different streaming rates.
As part of our future plans, we aim to evaluate our proposed model, PALMS-SP
in PlanetLab (PlanetLab), in order to further investigate the effectiveness
and the robustness of our streaming model in a larger network and real
network deployment. We are also keen in exploring various techniques to
improve the delivered streaming quality and delivery latency.
This work was supported by the by the Ministry of Education, Culture,
Sports, Science and Technology, Government of Japan and also by a grant
from the Hori Foundation Science Promotion Foundation, Japan.