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]