ALTO Fabio Picconi
Internet-Draft Laurent Massoulie
Intended Status: Informational Technicolor
Expires: September 2, 2010 March 1, 2010
ISP-friendly peer-to-peer live streaming
draft-picconi-alto-p2p-streaming-00
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
Abstract
The Application-Layer Traffic Optimization (ALTO) service aims at
providing applications with information about the network to optimize
their traffic. Peer-to-peer (P2P) live streaming is one of such
Picconi Expires September 2, 2010 [Page 1]
Internet-Draft ISP-friendly P2P live streaming March 1, 2010
applications which can benefit from ALTO. We have recently designed a
new scheme to minimize inter-domain traffic in P2P live streaming
applications without impacting video quality. In this draft we
briefly describe our solution, and we discuss the implications of the
type of information provided by the ALTO service on overlay
construction.
Table of Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Generalized cost models . . . . . . . . . . . . . . . . . . . . 4
4 Security Considerations . . . . . . . . . . . . . . . . . . . . 5
5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Author's Addresses . . . . . . . . . . . . . . . . . . . . . . . . 6
1 Introduction
A lot of attention has been recently devoted to optimizing the
traffic generated by peer-to-peer applications. The Application-Layer
Traffic Optimization (ALTO) working group is defining a service that
will provide applications with information about the underlying
network. For instance, peer-to-peer applications will be able to
obtain a list of other peers located in the same Internet Service
Provider (ISP).
Recent research efforts have studied how such information can be used
by peer-to-peer algorithms to reduce cross-ISP traffic
[Aggarwal][Xie][Choffnes]. However, these studies have focused on
file download applications such as BitTorrent, with little or no
attention given to live video streaming [Huang]. In fact, reducing
cross-ISP traffic in live streaming is more difficult than in file
download due to the real-time constraints of video delivery. Care
make be taken so that locality optimizations do not increase
diffusion delay or decrease download rates beyond the levels required
for continuous playback.
We have recently proposed a new scheme that aims at minimizing cross-
ISP traffic in peer-to-peer live streaming without impacting video
quality. The scheme constructs a two-layer overlay (local and
global), and dynamically adjusts the download rate on costly links.
The algorithm is completely distributed: each peer makes decisions
based on its local state and peerwise exchanges with other peers. The
only global information are the network costs provided by an ISP-
controlled server (e.g., the ALTO service). We give more details of
our solution in the next section.
Picconi Expires September 2, 2010 [Page 2]
Internet-Draft ISP-friendly P2P live streaming March 1, 2010
Our scheme assumes that any two peers use the same cost for the path
between them, and that this cost is the same for traffic sent in
either direction. In practice, peers may use different costs (e.g.,
if they belong to different ISPs), and the cost may depend on the
direction of traffic. Moreover, peers may not have access to
numerical costs, but only to ordinal information (i.e., rankings or
preferences between peers). In this draft we also discuss how our
scheme can be extended to consider such generalized cost scenarios.
2 Design
We now provide a brief description of our scheme for ISP-friendly P2P
live streaming. More details on the algorithm as well as the
experimental evaluation can be found in our paper [Picconi].
2.1 Overlay construction
Each peer mantains two sets of overlay neighbors, with which it
exchanges video chunks. The primary neighbor set contains peers with
low network cost, while the secondary neighbor set contains peers
chosen at random. The cost of a neighbor corresponds to the cost of
the network path to it, which is a assumed to be the same for both
endpoints and both traffic directions.
A peer's primary set is further divided into two subsets: download
neighbors (from which chunks are received) and upload neighbors (to
whick chunks are sent). Both subsets are populated independently, so
they may contain different neighbors. Moreover, the maximum number of
primary upload neighbors is proportional to the local peer's upload
capacity. This gives fast peers a large out-degree, and ensures that
all primary connections throughout the overlay use roughly the same
bandwidth (assuming an equal-split allocation). The maximum number of
download neighbors is the same for every peer, and is given a low
value to minimize signaling overhead.
Primary neighbor sets are populated as follows. A peer periodically
attempts to establish an outgoing connection to a peer with low
network cost (picked from a list provided by a network-aware
tracker). If its upload neighbor set is already full, the peer
attempts to replace existing upload neighbors with lower-cost ones. A
peer accepts an incoming connection if its download neighbor set is
not full, or if the new neighbor would replace a higher-cost one.
The secondary neighbor set is handled in a much simpler fashion. A
peer connects to other peers chosen at random among the entire
overlay population. A distinction between upload and download peers
is not necessary.
Picconi Expires September 2, 2010 [Page 3]
Internet-Draft ISP-friendly P2P live streaming March 1, 2010
2.2 Dynamic secondary rate
The mechanism presented above constructs a highly localized overlay
(primary neighbors) augmented by random links (secondary neighbors)
that connect distant peers. While most traffic should go through
primary connections, a few chunks must still be sent through
secondary ones to ensure that each chunk reaches the entire overlay.
Our scheme uses a simple receiver-driven mechanism to limit the
traffic sent through secondary links. Each peer continuously adjusts
the maximum rate at which it accepts chunks from secondary neighbors.
This rate is modified according to the contents of the local chunk
buffer: whenever a chunk is close to the deadline and is still
missing in the buffer, the rate is increased; conversely, the rate is
periodically decreased while the buffer is full.
The intuition behind this scheme is that increasing the connectivity
between remote portions of the overlay decreases the average chunk
diffusion delay, and vice-versa. Therefore, a chunk received near the
deadline indicates that the diffusion delay may be too high, and that
connectivity between remote peers should be increased.
2.3 Discussion
The scheme presented above has several nice properties. First, the
algorithms are simple, and do not require strong synchronization
among peers. All decisions (overlay construction, chunk scheduling,
secondary download rate) are based on local or one-hop information.
Second, peers react before playback deadlines, when there is still
time to download missing chunks and avoid disruptions in video
playback. Third, it exhibits a trade-off between ISP-friendliness and
chunk diffusion delay (see paper for more details [Picconi]).
Our experimental evaluation shows that the primary overlay quickly
converges towards a near-optimal configuration: the sum of the cost
of all primary links is close to the achievable minimum (assuming all
download neighbor sets are full). Since all overlay connections use
roughly the same bandwidth, constructing a minimum-cost overlay
effectively minimizes the network cost of the system.
Moreover, experiments show that once the overlay stabilizes, most
traffic is sent through primary connections, thus achieving a
significant reduction of cross-ISP traffic compared to a network-
agnostic scheme. Finally, experiments under high churn also show that
keeping multiple secondary neighbors per peer increases robustness
compared to a highly localized overlay with few random connections.
3 Generalized cost models
Picconi Expires September 2, 2010 [Page 4]
Internet-Draft ISP-friendly P2P live streaming March 1, 2010
Our original scheme presented in our paper makes several assumptions
about network costs: 1) the cost on a given path is the same for both
traffic directions, 2) both endpoints agree on the path cost, 3) the
path's numerical cost is known. We now discuss how these assumptions
can be relaxed.
Relaxing the first assumption (bidirectional costs) requires no
modifications to our system, as we already construct a directed
overlay (i.e., peers can connect as uploaders, downloaders, or both).
Therefore, a peer will use the path cost corresponding to the
outgoing direction when it connects as an uploader, and the incoming
cost when it connects as a downloader.
The second assumption (peers agree on path cost) is also easily
relaxed. As described earlier, a new primary connection is created
when it is beneficial for both endpoints (i.e., each endpoint is
either still filling its neighbor set, or willing to replace an
existing higher-cost neighbor). Thus, each endpoint can use its own
path cost to determine whether it should accept the neighbor or not.
However, we need to define a new way to compute the global cost of
the primary overlay. One solution is to obtain the link cost as the
mean of the two costs (i.e., according to each endpoint), and to
proceed as in the single-cost case.
Relaxing the third assumption (numerical costs) means that peers only
obtain peer rankings from the tracker. Again, we can still use the
overlay construction described above: a peer replaces its neighbors
only if they are ranked higher in the preference list. However, the
absence of numerical costs means that we can no longer compute the
minimim-cost overlay and use it as a benchmark for our system.
If only ordinal costs are available, one approach would be to
converge to overlay configurations which are stable (assuming a
static peer population). In a stable configuration (or matching), all
peers are satisfied with their neighbors, i.e., there are no two
peers that would replace one of their neighbors with each other. This
is known in the research literature as the stable allocation problem
[Baiou]. Moreover, there exists a greedy algorithm thats find stable
matchings. The application of such algorithms to our a peer-to-peer
system, as well as their behavior under dynamic populations, could be
an interesting subject for future work.
4 Security Considerations
No security considerations are discussed in this memo.
5 References
Picconi Expires September 2, 2010 [Page 5]
Internet-Draft ISP-friendly P2P live streaming March 1, 2010
[Aggarwal] V. Aggarwal, A. Feldmann, and C. Scheideler. Can ISPs and
P2P systems cooperate for improved performance? ACM CCR,
July 2007.
[Choffnes] D.R. Choffnes and F. E. Bustamante. Taming the Torrent: A
Practical Approach to Reducing Cross-ISP Traffic in Peer-
to-peer Systems. In Proc. of SIGCOMM, 2008.
[Huang] G. Huang. Experiencies with PPLive. Keynote at ACM.
SIGCOMM P2P-TV, Aug. 2007.
[Picconi] F. Picconi and L. Massoulie. ISP-friend or foe? Making
P2P live streaming ISP-aware. In Proc. of ICDCS, 2009.
[Xie] H. Xie, Y. R. Yang, A. Krishnamurthy, Y. Liu, and A.
Silberschatz. P4P: Provider Portal for Applications. In
Proc. of SIGCOMM, 2008.
[Baiou] M. Baiou and M. Balinski. Erratum: The Stable Allocation
(or Ordinal Transportation) Problem. In Mathematics of
Operations Research, Vol. 27, N. 4, March - May, pp. 662-
680.
Author's Addresses
Fabio Picconi
Technicolor
1 rue Jeanne d'Arc
92130 Issy-les-moulineaux
France
EMail: fabio.picconi@technicolor.com
Laurent Massoulie
Technicolor
1 rue Jeanne d'Arc
92130 Issy-les-moulineaux
France
EMail: laurent.massoulie@technicolor.com
Picconi Expires September 2, 2010 [Page 6]