ALTO WG Y. Yang Internet-Draft Yale University Intended status: Experimental R. Alimi Expires: April 20, 2011 Google Y. Wang Yale University D. Zhang PPLive K. Lee China Telecom October 17, 2010 Tracker-Based Peer Selection using ALTO Map Information draft-yang-tracker-peer-selection-00.txt Abstract As ALTO core information starts to become available from some ISPs, how to effectively utilize such information by P2P applications has become a major issue. In this document, we discuss some techniques that a P2P application tracker can incorporate ALTO information in initial peer selection. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [1]. 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/ietf/1id-abstracts.txt. Yang, et al. Expires April 20, 2011 [Page 1] Internet-Draft Tracker Peer Selection October 2010 The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on April 20, 2011. 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. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. Yang, et al. Expires April 20, 2011 [Page 2] Internet-Draft Tracker Peer Selection October 2010 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Peer Classification Data Structures . . . . . . . . . . . . . 5 3.1. One-Level Key Partitioning . . . . . . . . . . . . . . . . 6 3.2. Hierarchical Partitioning . . . . . . . . . . . . . . . . 6 3.3. Comments . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Peer Selection Using Peer Classification . . . . . . . . . . . 7 4.1. Overview of Scheme . . . . . . . . . . . . . . . . . . . . 7 4.2. Extensions and Issues . . . . . . . . . . . . . . . . . . 8 5. Peering Matrix . . . . . . . . . . . . . . . . . . . . . . . . 9 5.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 9 5.2. Partition Tree . . . . . . . . . . . . . . . . . . . . . . 9 5.3. Computing the Peering Matrix: Bandwidth Matching . . . . . 10 5.4. Computing the Peering Matrix: Generic . . . . . . . . . . 11 5.5. Live Streaming Results Using Planetlab . . . . . . . . . . 11 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 8.1. Normative References . . . . . . . . . . . . . . . . . . . 11 8.2. Informative References . . . . . . . . . . . . . . . . . . 11 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Yang, et al. Expires April 20, 2011 [Page 3] Internet-Draft Tracker Peer Selection October 2010 1. Introduction ALTO provides information to network applications to improve network efficiency [2]. There are many ways that a network application can utilize ALTO information. For example, an application may choose to utilize only the Network Map, another may use both the Network Map and the Cost Map, and yet another may use the Endpoint ranking. It can be either a more centralized entity such as a tracker in a P2P application or the P2P clients that utilize ALTO information. One P2P application may choose to use the information at the P2P clients during piece selection or rate scheduling, while another P2P application may use it during peer selection. How to effectively utilize ALTO information is a challenge that P2P applications considering integrating with ALTO need to address. In this document, we present example techniques of how to integrate ALTO information into the peer selection process at a P2P tracker. We first present some key challenges. We then present some techniques used in real trial examples that address the challenges. 2. Challenges A P2P tracker selects a set of peers upon receiving a LISTING request of a peer. Since a tracker may receive a large number of such LISTING requests, it is important that the tracker can handle each request with high efficiency while achieving effectiveness in utilizing available information. The design of the data structures and algorithms at the tracker for peer selection is challenging and can have a major impact on the efficiency and effectiveness of peer selection. Specifically, there are two challenges in integrating ALTO information into the peer selection of a P2P tracker. o Scalability: A P2P developer may have a small number of trackers to handle a large number of channels (files) each with multiple peers. The peers might be distributed across multiple ISPs that provide ALTO information. Thus, the storage and processing overhead caused by using ALTO information must be considered in order to scale to the increasingly larger P2P applications. In addition, it may be necessary to scale the tracker of a particularly popular channel from a single machine to multiple machines. In practice, many P2P applications may use multiple physical P2P trackers for a single channel for fault tolerance (e.g., when one tracker crashes) and/or connectivity reasons (e.g., poor connectivity between networks). Yang, et al. Expires April 20, 2011 [Page 4] Internet-Draft Tracker Peer Selection October 2010 o Application-Network Information Fusion: When selecting peers, a tracker should consider not only ALTO information, but also peer properties known only to the application (e.g., instantaneous peer upload capacity) as well as application requirements. In particular, a key concern of a P2P application is that solely considering ALTO information may lead to degraded application performance (e.g., slower download rate in a P2P file sharing application.) One of the simplest ways to implement peer selection is random peer selection using a single array storing all current peers. Upon receiving a LISTING request, the tracker picks a random position in the array, and returns a set of peers starting from the chosen position. A slightly different random peer selection algorithm is to repeatedly pick random numbers in the range of the size of the array to pick multiple random peers. An advantage of the preceding algorithm is scalability. But it is lacking in network-application information fusion. It does not consider peer properties during peer selection. On the other hand, many P2P trackers already select peers considering peer properties. For example, one type of peer property often considered is peer upload capabilities. Another type of peer property is the playpoint of a peer, in particular, in an VoD setting. Also, in addition to using ALTO information, some existing P2P trackers already consider network location properties such as the ASN, the IP prefix, the geo location (e.g., city, country or latitude/longitude), or the set of nearest landmarks of a peer. 3. Peer Classification Data Structures When peers are annotated with properties, we might envision that the peers are stored at a tracker in a table similar in format to Figure 1: ----------------------------------------------------------------- | peer_id | IP | upld_cap | play_point | ASN | country | cty | .. | ----------------------------------------------------------------- | ... |... | ... | ... | ... | ... | ... | .. | ------------------------------------------------------------------ Figure 1: Using a Table to Store Peers A problem of a flat table is that it does not support peer classification to find peers with given properties. Just as many databases build indices, many P2P trackers build inverted data structures such as map/hash in order to index to the pool of peers Yang, et al. Expires April 20, 2011 [Page 5] Internet-Draft Tracker Peer Selection October 2010 with a given property. In an abstract formulation, for each peer A requesting LISTING, the peer selection algorithm at the tracker determines a probability that any peer B will be returned to A, where the probability depends on the relative "match" between the properties of A and B. However, too much fine-grained tuning of the probabilities (there are O(N^2) such values, where N is number of peers) may not be necessary or feasible. Peer classification is a technique to aggregate peers into equivalent classes before peer selection to improve scalability. 3.1. One-Level Key Partitioning Multiple examples exist in this category. In one example, the key is a category of the uploading capacity of a peer. For example, the tracker may classify peers as having high upload capacity, medium upload capacity, or low upload capacity. Then according to the property of the peer issuing the LISTING request, the tracker selects fractions of peers from each category. In another example, the key can be the ASN or ISP name. When the tracker receives a LISTING request from a peer, the tracker looks up the ASN/ISP of the peer, and indexes to the ASN/ISP to select peers. To avoid partition of the P2P topology or when there are not sufficient numbers of peers in the ASN/ISP, the tracker may select peers from other ASNs/ISPs. 3.2. Hierarchical Partitioning In addition to a single level flat map, some trackers classify peers using multiple attributes and/or build multiple levels of indexing, utilizing a hierarchical partitioning of peers according to peer properties. One example is to use the hierarchical geo partitioning of peers first into country, then state/province, and then city. Utilizing the Network Map of ALTO, the tracker can classify each peer into the PID of each ISP providing ALTO Network Map. Extending the preceding examples of using one type of peer property, the partition keys at different levels can be from different categories. For example, at the first level, the tracker might use peer upload capacity, the next level uses ISP as the key, and the third level uses PID. Yang, et al. Expires April 20, 2011 [Page 6] Internet-Draft Tracker Peer Selection October 2010 3.3. Comments There are several comments. First, a tracker may partition peers from multiple perspectives. For example, each ISP providing ALTO Network Map provides a classification of peers into its set of PIDs. Thus, a single IP address may belong to different PIDs from different Network Maps of different ISPs. The tracker may build a classification tree for each ISP. It is possible that these multiple trees can be merged into a single tree with a dummy ROOT. We use a single classification tree as an example. Second, the nodes of different non-overlapping branches may overlap regarding the sets of peers contained in them. Second, it may not be straightforward or necessary to partition peers using certain properties. For example, landmarks may not lead to easy partitioning of peers. 4. Peer Selection Using Peer Classification 4.1. Overview of Scheme We now look at a class of tracker peer selection techniques that utilize peer classification. Each peer is located at a leaf node of a classification tree. We consider the set of algorithms where the peer selection depends on the properties of the peer issuing the request. We introduce a concept called the "home" node of a peer issuing the LIST request. The home node is identified first before peer selection. The peer selection is specified in the following way. Associated with each "home" leaf node of the classification tree is an ordered list, where each element in the list contains two fields: the first is a pointer to a node in a peer classification tree, and the second indicates how and how much to select peers from the node. It is important to notice that the list is ordered as the tracker picks peers in order. It is straightforward to extend that the nodes may come from multiple classification trees. Figure 2 is an example. We refer to the data structure containing the selected peers as the bucket. The example specifies that when a peer A with "home" leaf node at n4 (high capacity peers from ISP1) issues a LISTING request, first fill 50% of the bucket containing peers to be returned to A from n4 (high capacity peers from same ISP) or no more peers available from n4, then continue to fill the bucket Yang, et al. Expires April 20, 2011 [Page 7] Internet-Draft Tracker Peer Selection October 2010 by choosing peers from n5 (low capacity peers from same ISP) until the bucket is 80% full or no peers available from n5, then continue to fill the bucket by picking peers from n2 (peers from ISP2) so that the bucket can be 95% full, and finally fill the remaining of the bucket from n3. Note that the scheme intends that for n4, to pick more from the same ISP (80%), then ISP2 (15%), and then ISP3. It also tries to pair high capacity peers more with high capacity peers. ROOT / | \ / | \ ISP1 / ISP2 | ISP3 \ / | \ n1 n2 n3 / | / \ / \ / | | \ | \ HC LC HC LC HC LC n4 n5 n6 n7 n8 n9 leaf n4: [n4, 50%] [n5, 80%] [n2, 95%] [n3, 100%] leaf n5: [n4, 20%] [n5, 60%] [n2, 95%] [n3, 100%] ... leaf n9: ... Figure 2: Example: Peer Selection using Classification Tree. 4.2. Extensions and Issues The preceding peer selection scheme is simple and flexible. It can be efficiently implemented. There can be multiple ways to extend the scheme. There are two remaining issues: o First, how to design the classification tree? o Second, how to create the traversal list of each leaf node? In addition to addressing the two preceding issues, this scheme may not be a general representation of some existing peer selection schemes. For example, when the network location of a peer is represented by its set of close-by landmarks, a straightforward partition tree may not exist. Instead, some other data structures and algorithms may be needed to pick the peers that are the closest measured by a special metric space measured by "closeness" of landmark sets. Yang, et al. Expires April 20, 2011 [Page 8] Internet-Draft Tracker Peer Selection October 2010 5. Peering Matrix 5.1. Overview The Peering Matrix approach is an instance of the scheme of Peer Selection Using Partition Tree. It has been used in several trials, including the Pando/Comcast trial [3]. The scheme has also been evaluated in the context of P2P Live Streaming. Below, we present more details on Peering Matrix. We also briefly summarize a set of results applying Peering Matrix to P2P Live streaming on the Planetlab. 5.2. Partition Tree Recall that we name the peer issuing the LISTING request as A. There is a unique path Path(A) going up from the leaf node containing A to ROOT in the partition tree. We consider the class of tracker peer selection algorithms that specify a (upper bound) target fraction of peers to be selected at each node n along Path(A). The peer selection algorithm goes up along Path(A). To be consistent, the fraction value at a node n should be no larger than that of the parent of n named Parent(n). Also, at each node n along Path(A), for each child c of n, the peer selection algorithm specifies how peers are distributed among the siblings of c. Consider an example in Figure 3: ISP1 / | \ \ / | \ \ / | \ \ / | \ \ PID1 PID2 PID3 ... PIDn Figure 3: Example: Using ALTO Network Map for building a Classification Tree. Specifically, Figure 3 is a two level classification tree for an ISP, and each second level node represents a PID of the ISP. Each PID is labeled with Fraction = 75%. The ROOT has a fraction of 100%. The sibling distribution of node PID1 node is 50%, 30%, 20% to PID2, PID3, and PID4 respectively. This means that when a peer A from PID1 asks for a list of peers, the tracker selects up to 75% peers at PID1, and fills the remaining (25%) at PID2 (up to 25% * 50%), PID3 (25% * 30%), and PID4 (25% * 20%). Yang, et al. Expires April 20, 2011 [Page 9] Internet-Draft Tracker Peer Selection October 2010 During P4P trials, we used a three level partition tree for each ISP. ROOT / | \ \ / | \ \ / | \ \ / | \ \ intra ePID1 ePID2 ... ePIDn / | \ / | \ iPID1 iPID2 ...iPID Figure 4: Three-Level Peer Classification. One nice property of using per ISP classification tree is to implement a distributed tracker, where a tracker is responsible for the peers within a set of ISPs. A peer may request LISTING from multiple trackers (e.g., located at different ISPs) that together are responsible for the channel. The tracker hosting the "home" leaf of the peer uses peering matrix, while the other trackers return a small number of random peers for robustness. 5.3. Computing the Peering Matrix: Bandwidth Matching To compute the sibling distribution at node intra and ROOT, the tracker estimates the aggregated upload capacity (a seed can use full upload capacity and a leecher achieves 70%) and demand of each PID and then conducts bandwidth matching as specified in [4]. Specifically, The following diagram shows how the information flow as well as how to transform ALTO Network Maps and Cost Maps into peering matrix, considering application states. Network [App-specific .----------. Map .-------------. state] .-------------. | ALTO | <----- | Peering | <--------- | | | Services | | Matrix | | Application | | | -----> | Computation | ---------> | | `----------' Cost `-------------'App-specific`-------------' Map or generic guidance Figure 5: Information Flow to Compute Peering Matrix. The interface to the Peering Matrix Computation Component, for a BitTorrent like file sharing application can be: Yang, et al. Expires April 20, 2011 [Page 10] Internet-Draft Tracker Peer Selection October 2010 GetPeeringWeights: The request optionally includes swarm state information as a list of PIDs, and for each PID, the number of seeds and leechers and the aggregated download and upload capacity of clients within the PID. The response is a matrix of peering weights amongst the PIDs included in the request, as computed from the set of Costs currently pulled from the ALTO Server. If the request included swarm information, the returned weight matrix is tailored for the current state of the swarm. 5.4. Computing the Peering Matrix: Generic Similar to the preceding, but instead of using estimated capacity and demand, it assumes that each PID has one peer. 5.5. Live Streaming Results Using Planetlab 6. IANA Considerations This document makes no request of IANA. Note to RFC Editor: this section may be removed on publication as an RFC. 7. Security Considerations This document does not evaluate security considerations. Multiple other documents in the ALTO working group considers the security perspective of using ALTO information. 8. References 8.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 8.2. Informative References [2] Alimi, R., Penno, R., and Y. Yang, "ALTO Protocol", draft-ietf-alto-protocol-03 (work in progress), March 2010. [3] Griffiths, C., Livingood, J., Popkin, L., Woundy, R., and Y. Yang, "Comcast's ISP Experiences in a Proactive Network Provider Participation for P2P (P4P) Technical Trial", RFC 5632, September 2009. Yang, et al. Expires April 20, 2011 [Page 11] Internet-Draft Tracker Peer Selection October 2010 [4] H. Xie, Y.R. Yang, A. Krishnamurthy, Y. Liu, and A. Silberschatz., "P4P:", In SIGCOMM 2008. Appendix A. Acknowledgments This document benefits substantially from trials and designs involving P2P applications Pando (Laird Pasko), PPLive (David Zhang), Digimeld (Gene Qin), and Xunlei. The data structure designs and algorithms include the contributions of Hao Wang, Ye Wang, and Harry Liu. We appreciate their contributions. The design is quite similar to that of Xunlei, whose more details will be included in the updated China Telecom trial document. Authors' Addresses Y. Richard Yang Yale University Email: yry@cs.yale.edu Richard Alimi Google Email: ralimi@google.com Ye Wang Yale University Email: ye.wang@yale.edu David Zhang PPLive Email: davidzhang@pplive.com Kai Lee China Telecom Email: leek4u@gmail.com Yang, et al. Expires April 20, 2011 [Page 12]