idnits 2.17.1 draft-rimac-p2prg-alto-survey-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 06, 2009) is 5408 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-05) exists of draft-marocco-alto-problem-statement-00 == Outdated reference: A later version (-01) exists of draft-saucez-idips-00 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group I. Rimac 3 Internet-Draft V. Hilt 4 Intended status: Informational M. Tomsu 5 Expires: January 7, 2010 V. Gurbani 6 Bell Labs, Alcatel-Lucent 7 E. Marocco 8 Telecom Italia 9 July 06, 2009 11 A Survey on Research on the Application-Layer Traffic Optimization 12 (ALTO) Problem 13 draft-rimac-p2prg-alto-survey-00 15 Status of this Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt. 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft will expire on January 7, 2010. 38 Copyright Notice 40 Copyright (c) 2009 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents in effect on the date of 45 publication of this document (http://trustee.ietf.org/license-info). 46 Please review these documents carefully, as they describe your rights 47 and restrictions with respect to this document. 49 Abstract 51 A significant part of the Internet traffic today is generated by 52 peer-to-peer (P2P) applications used traditionally for file-sharing, 53 and more recently for real-time communications and live media 54 streaming. Such applications discover a route to each other through 55 an overlay network with little knowledge of the underlying network 56 topology. As a result, they may choose peers based on information 57 deduced from empirical measurements, which can lead to suboptimal 58 choices. We refer to this as the Application Layer Traffic 59 Optimization (ALTO) problem. In this draft we present a survey of 60 existing literature on discovering topology characteristics. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Survey of Existing Literature . . . . . . . . . . . . . . . . 4 66 2.1. Application-Level Topology Estimation . . . . . . . . . . 4 67 2.2. Topology Estimation through Layer Cooperation . . . . . . 5 68 2.2.1. P4P Architecture . . . . . . . . . . . . . . . . . . . 5 69 2.2.2. Oracle-based ISP-P2P Collaboration . . . . . . . . . . 6 70 2.2.3. ISP-Driven Informed Path Selection (IDIPS) Service . . 7 71 3. Application-Level Topology Estimation and the ALTO Problem . . 7 72 4. Security Considerations . . . . . . . . . . . . . . . . . . . 8 73 5. Informative References . . . . . . . . . . . . . . . . . . . . 8 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 76 1. Introduction 78 A significant part of today's Internet traffic is generated by peer- 79 to-peer (P2P) applications, used originally for file sharing, and 80 more recently for realtime multimedia communications and live media 81 streaming. P2P applications are posing serious challenges to the 82 Internet infrastructure; by some estimates, P2P systems are so 83 popular that they make up anywhere between 40% to 85% of the entire 84 Internet traffic [Meeker], [Karag], [Light], [Linux], [Parker], 85 [Glasner]. 87 P2P systems ensure that popular content is replicated at multiple 88 instances in the overlay. But perhaps ironically, a peer searching 89 for that content may ignore the topology of the latent overlay 90 network and instead select among available instances based on 91 information it deduces from empirical measurements, which, in some 92 particular situations may lead to suboptimal choices. For example, a 93 shorter round-trip time estimation is not indicative of the bandwidth 94 and reliability of the underlying links, which have more of an 95 influence than delay for large file transfer P2P applications. 97 Most distributed hash tables (DHT) -- the data structure that imposes 98 a specific ordering for P2P overlays -- use greedy forwarding 99 algorithms to reach their destination, making locally optimal 100 decisions that may not turn to be globally optimized [Gummadi-1]. 101 This naturally leads to the Application-Layer Traffic Optimization 102 (ALTO) problem [I-D.marocco-alto-problem-statement]: how to best 103 provide the topology of the underlying network while at the same time 104 allowing the requesting node to use such information to effectively 105 reach the node on which the content resides. Thus, it would appear 106 that P2P networks with their application layer routing strategies 107 based on overlay topologies are in direct competition against the 108 Internet routing and topology. 110 One way to solve the ALTO problem is to build distributed 111 application-level services for location and path selection 112 [Francis-1], [Ng-1], [Dabek-1], [Costa-1], [Wong-1], [Madhyastha-1], 113 in order to enable peers to estimate their position in the network 114 and to efficiently select their neighbors. Similar solutions have 115 been embedded into P2P applications such as Azureus [Azureus]. A 116 slightly different approach is to have the Internet service provider 117 (ISP) take a pro-active role in the routing of P2P application 118 traffic; the means by which this can be achieved have been proposed 119 [Aggarwal-1], [Xie-1], [I-D.saucez-idips]. There is an intrinsic 120 struggle between the layers -- P2P overlay and network underlay -- 121 when performing the same service (routing), however there are 122 strategies to mitigate this dichotomy [Seetharaman-1]. 124 2. Survey of Existing Literature 126 Gummadi et al. [Gummadi-1] compare popular DHT algorithms and 127 besides analyzing their resilience, provide an accurate evaluation of 128 how well the logical overlay topology maps on the physical network 129 layer. In their paper, relying only on measurements independently 130 performed by overlay nodes without the support of additional location 131 information provided by external entities, they demonstrate that the 132 most efficient algorithms in terms of resilience and proximity 133 performance are those based on the simplest geometric concept (i.e. 134 the ring geometry, rather than hypercubes, tree structures and 135 butterfly networks). 137 Regardless of the geometrical properties of the DHTs involved, 138 interactions between application-layer overlays and the underlying 139 networks are a rich area of investigation. The available literature 140 in this field can be taxonomixed in two categories: using 141 application-level techniques to estimate topology and using an 142 infrastructure of some sort. 144 2.1. Application-Level Topology Estimation 146 In order to provide P2P overlays with topology information essential 147 for optimizing node selection, different systems have been proposed. 149 Estimating network topology information on the application level has 150 been an area of active research. Early work on network distance 151 estimation based on clustering by Francis et al. [Francis-1] was 152 followed by the introduction of network coordinate systems such as 153 GNP by Ng et al. [Ng-1]. Network coordinate systems embed the 154 network topology in a low-dimensional coordinate space and enable 155 network distance estimations based on vector distance. Vivaldi 156 [Dabek-1] and PIC [Costa-1] propose distributed network coordinate 157 systems that do not need landmarks for coordinate calculation. 158 Vivaldi is now being used in the popular P2P application Azureus 159 [Azureus] and studies indicate that it scales well to very large 160 networks [Ledlie-1]. 162 Coordinate systems require the embedding of the Internet topology 163 into a coordinate system. This is not always possible without 164 errors, which impacts the accuracy of distance estimations. For 165 example, it has proved to be difficult to embed the triangular 166 inequalities found in Internet path distances [Wang-07]. Thus, 167 Meridian [Wong-1] abandons the generality of network coordinate 168 systems and provides specific distance evaluation services. The Ono 169 project [Ono] take a different approach and uses network measurements 170 from content-distribution network (CDN) like Akamai to find nearby 171 peers [Su06]. Used as a plugin to the Azureus BitTorrent client, Ono 172 provides 31% average download rate improvement. 174 Most of the work on estimating topology information focuses on 175 predicting network distance in terms of latency and does not provide 176 estimates for other metrics such as throughput. However, for many 177 P2P applications throughput is often more important than latency. 178 iPlane [Madhyastha-1] aims at creating an atlas of the Internet using 179 measurements that contains information about latency, bandwidth, 180 capacity and loss rates. 182 To determine features of the topology, network measurement tools, 183 e.g., based on packet dispersion techniques (packet pairs and packet 184 trains) as described by Dovrolis et al. in [DRM01] can be used. 185 Moreover, methods of active network probing or passive traffic 186 monitoring can also generate network statistics relating indirectly 187 to performance attributes that cannot be directly measured but need 188 to be inferred. An extensive study of such techniques that are 189 summarized under the notion of network tomography has been provided 190 by Coates et al. [CHNY02]. 192 The Joost Video-on-Demand Service uses P2P technology to distribute 193 streaming video at a bit rate of about 600 kbit/s and higher. In 194 their experimental analysis, Lei et al. [LEI-07] conclude that the 195 system is heavily based on a media server infrastructure -- in 196 particular for channels with lower popularity -- and that a 197 geographical distance based on address prefix analysis is considered 198 during the server selection. They show that the peer selection 199 process today is unlikely based on topology locality. Instead the 200 peer's capacity influences the the creation of the peer lists similar 201 to BitTorrent: low capacity peers connect mostly with other low 202 capacity peers to avoid wasting the high capacity peers bandwidth. 204 2.2. Topology Estimation through Layer Cooperation 206 Instead of estimating topology information on the application level 207 through distributed measurements, this information could be provided 208 by the entities running the physical networks -- usually ISPs or 209 network operators. In fact, they have full knowledge of the topology 210 of the networks they administer and, in order to avoid congestion on 211 critical links, are interested in helping applications to optimize 212 the traffic they generate. The remainder of this section briefly 213 describes three recently proposed solutions that follow such an 214 approach to address the ALTO problem. 216 2.2.1. P4P Architecture 218 The architecture proposed by Xie et al. [Xie-1] have been adopted by 219 the DCIA P4P working group [P4P-1], an open group established by 220 ISPs, P2P software distributors and technology researchers with the 221 dual goal of defining mechanisms to accelerate content distribution 222 and optimize utilization of network resources. 224 The main role in the P4P architecture is played by servers called 225 ``iTrackers'', deployed by network providers and accessed by P2P 226 applications (or, in general, by elements of the P2P system) in order 227 to make optimal decisions when selecting a peer to connect. An 228 iTracker may offer three interfaces: 230 1. Info: Allows P2P elements (e.g. peers or trackers) to get opaque 231 information associated to an IP address. Such information is 232 kept opaque to hide the actual network topology, but can be used 233 to compute the network distance between IP addresses. 234 2. Policy: Allows P2P elements to obtain policies and guidelines of 235 the network, which specify how a network provider would like its 236 networks to be utilized at a high level, regardless of P2P 237 applications. 238 3. Capability: Allows P2P elements to request network providers' 239 capabilities. 241 The P4P architecture is under evaluation with simulations, 242 experiments on the PlanetLab distributed testbed and with field tests 243 with real users. Initial simulations and PlanetLab experiments 244 results [P4P-1] indicate that improvements in BitTorrent download 245 completion time and link utilization in the range of 50-70\% are 246 possible. Results observed in field tests conducted with a modified 247 version of the software used by the Pando content delivery network 248 [OpenP4P-1] show improvements in download rate by 23\% and a 249 significant drop in data delivery average hop count (from 5.5 to 250 0.89) in certain scenarios. 252 2.2.2. Oracle-based ISP-P2P Collaboration 254 The mechanism is fairly simple: a P2P user sends the list of 255 potential peers to the oracle hosted by its ISP, which ranks such a 256 list based on its local policies. For instance, the ISP can prefer 257 peers within its network, to prevent traffic from leaving its 258 network; further, it can pick higher bandwidth links, or peers that 259 are geographically closer. Once the application has obtained an 260 ordered list, it is up to it to establish connections with a number 261 of peers it can individually choose, but it has enough information to 262 perform an optimal choice. 264 Such a solution has been evaluated with simulations and experiments 265 run on the PlanetLab testbed and the results show both improvements 266 in content download time and a reduction of overall P2P traffic, even 267 when only a subset of the applications actually query the oracle to 268 make their decisions. 270 2.2.3. ISP-Driven Informed Path Selection (IDIPS) Service 272 The IDIPS solution [I-D.saucez-idips] was presented during the SHIM6 273 session of the 71st IETF meeting. It is essentially a modified 274 version of the solution described in section Section 2.2.2, extended 275 to accept lists of source addresses other than destinations in order 276 to function also as a back end for protocols like SHIM6 and LISP 277 (which aim at optimizing path selection at the network layer). An 278 evaluation performed on IDIPS shows that costs for both providing and 279 accessing the service are negligible [Saucez-2]. 281 3. Application-Level Topology Estimation and the ALTO Problem 283 The application-level techniques described in Section Section 2.1 284 provide tools for peer-to-peer applications to estimate parameters of 285 the underlying network topology. Although these techniques can 286 improve application performance, there are limitations of what can be 287 achieved by operating only on the application level. 289 Topology estimation techniques use abstractions of the network 290 topology which often hide features that would be of interest to the 291 application. Network coordinate systems, for example, are unable to 292 detect overlay paths shorter than the direct path in the Internet 293 topology. However, these paths frequently exist in the Internet 294 [Wang-07]. Similarly, application-level techniques may not 295 accurately estimate topologies with multipath routing. 297 When using network coordinates to estimate topology information the 298 underlying assumption is that distance in terms of latency determines 299 performance. However, for file sharing and content distribution 300 applications there is more to performance than just the network 301 latency between nodes. The utility of a long-lived data transfer is 302 determined by the throughput of the underlying TCP protocol, which 303 depends on the round-trip time as well as the loss rate experienced 304 on the corresponding path [PFTK98]. Hence, these applications 305 benefit from a richer set of topology information that goes beyond 306 latency including loss rate, capacity, available bandwidth. 308 Some of the topology estimation techniques used by peer-to-peer 309 applications need time to converge to a result. For example, current 310 BitTorrent clients implement local, passive traffic measurements and 311 a tit-for-tat bandwidth reciprocity mechanism to optimize peering 312 selection at a local level. Peers eventually settle on a set of 313 neighbors that maximizes their download rate but because peers cannot 314 reason about the value of neighbors without actively exchanging data 315 with them and the number of concurrent data transfers is limited 316 (typically to 5-7), convergence is delayed and easily can be sub- 317 optimal. 319 Skype's P2P VoIP application chooses a relay node in cases where two 320 peers are behind NATs and cannot connect directly. Ren et al. 321 [REN-06] measured that the relay selection mechanism of Skype is (1) 322 not able to discover the best possible relay nodes in terms of 323 minimum RTT (2) requires a long setup and stabilization time, which 324 degrades the end user experience (3) is creating a non-negligible 325 amount of overhead traffic due to probing a large number of nodes. 326 They further showed that the quality of the relay paths could be 327 improved when the underlying network AS topology is considered. 329 Some features of the network topology are hard to infer through 330 application-level techniques and it may not be possible to infer them 331 at all. An example for such a features are service provider policies 332 and preferences such as the state and cost associated with 333 interdomain peering and transit links. Another example is the 334 traffic engineering policy of a service provider, which may 335 counteract the routing objective of the overlay network leading to a 336 poor overall performance [Seetharaman-1]. 338 Finally, application-level techniques often require applications to 339 perform measurements on the topology. These measurements create 340 traffic overhead, in particular, if measurements are performed 341 individually by all applications interested in estimating topology. 343 4. Security Considerations 345 This draft is a survey of existing literature on topology estimation. 346 As such, it does not introduce any new security considerations to be 347 taken in account beyond what is already discussed in each paper 348 surveyed. 350 5. Informative References 352 [Aggarwal-1] 353 Aggarwal, V., Feldmann, A., and C. Scheidler, "Can ISPs 354 and P2P systems co-operate for improved performance?". 356 [Azureus] "Azureus BitTorrent Client", . 358 [CHNY02] Coates, M., Hero, A., Nowak, R., and B. Yu, "Internet 359 Tomography". 361 [Costa-1] Costa, M., Castro, M., Rowstron, A., and P. Key, "PIC: 362 Practical Internet coordinates for distance estimation". 364 [DRM01] Dovrolis, C., Ramanathan, P., and D. Moore, "What do 365 packet dispersion techniques measure?". 367 [Dabek-1] Dabek, F., Cox, R., Kaashoek, F., and R. Morris, "Vivaldi: 368 A Decentralized Network Coordinate System". 370 [Francis-1] 371 Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., 372 Shavitt, Y., and L. Zhang, "IDMaps: A global Internet host 373 distance estimation service". 375 [Glasner] Glasner, J., "P2P fuels global bandwidth binge", 376 . 378 [Gummadi-1] 379 Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., 380 Shenker, S., and I. Stoica, "The impact of DHT routing 381 geometry on resilience and proximity". 383 [I-D.marocco-alto-problem-statement] 384 Marocco, E. and V. Gurbani, "Application-Layer Traffic 385 Optimization (ALTO) Problem Statement", 386 draft-marocco-alto-problem-statement-00 (work in 387 progress), April 2008. 389 [I-D.saucez-idips] 390 Saucez, D., Donnet, B., and O. Bonaventure, "IDIPS : ISP- 391 Driven Informed Path Selection", draft-saucez-idips-00 392 (work in progress), February 2008. 394 [Karag] Karagiannis, T., Broido, A., Brownlee, N., Claffy, K., and 395 M. Faloutsos, "Is P2P dying or just hiding?". 397 [LEI-07] Lei, J., Shi, L., and X. Fu, "An experimental analysis of 398 Joost peer-topeer VoD service". 400 [Ledlie-1] 401 Ledlie, J., Gardner, P., and M. Seltzer, "Network 402 Coordinates in the Wild". 404 [Light] Lightreading, "Controlling P2P traffic", . 408 [Linux] linuxReviews.org, "Peer to peer network traffic may 409 account for up to 85% of Interneta??s bandwidth usage", 410 . 412 [Madhyastha-1] 413 Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., 414 Anderson, T., Krishnamurthy, A., and A. Venkataramani., 415 "iPlane: an information plane for distributed services". 417 [Meeker] Meeker, M. and D. Joseph, "The State of the Internet, Part 418 3", . 421 [Ng-1] Ng, T. and H. Zhang, "Predicting internet network distance 422 with coordinates-based approaches". 424 [Ono] "Northwestern University Ono Project", 425 . 428 [OpenP4P-1] 429 "OpenP4P Web Page", . 431 [P4P-1] "DCIA P4P Working group", 432 . 434 [PFTK98] Padhye, J., Firoiu, V., Towsley, D., and J. Kurose, 435 "Modeling TCP throughput: A simple model and its empirical 436 validation". 438 [Parker] Parker, A., "The true picture of peer-to-peer 439 filesharing", . 441 [REN-06] Ren, S., Guo, L., and X. Zhang, "ASAP: An AS-aware peer- 442 relay protocol for high quality VoIP". 444 [Saucez-2] 445 Saucez, D., Donnet, B., and O. Bonaventure, 446 "Implementation and Preliminary Evaluation of an ISP- 447 Driven Informed Path Selection". 449 [Seetharaman-1] 450 Seetharaman, S., Hilt, V., Hofmann, M., and M. Ammar, 451 "Preemptive Strategies to Improve Routing Performance of 452 Native and Overlay Layers". 454 [Su06] Su, A., Choffnes, D., Kuzmanovic, A., and F. Bustamante, 455 "Drafting behind Akamai (travelocity-based detouring)". 457 [Wang-07] Wang, G., Zhang, B., and T. Ng, "Towards Network Triangle 458 Inequality Violation Aware Distributed Systems". 460 [Wong-1] Wong, B., Slivkins, A., and E. Sirer, "Meridian: A 461 lightweight network location service without virtual 462 coordinates". 464 [Xie-1] Xie, H., Krishnamurthy, A., Silberschatz, A., and Y. Yang, 465 "P4P: Explicit Communications for Cooperative Control 466 Between P2P and Network Providers", 467 . 469 Authors' Addresses 471 Ivica Rimac 472 Bell Labs, Alcatel-Lucent 474 Email: rimac@bell-labs.com 476 Volker Hilt 477 Bell Labs, Alcatel-Lucent 479 Email: volkerh@bell-labs.com 481 Marco Tomsu 482 Bell Labs, Alcatel-Lucent 484 Email: marco.tomsu@alcatel-lucent.com 486 Vijay K. Gurbani 487 Bell Labs, Alcatel-Lucent 489 Email: vkg@bell-labs.com 491 Enrico Marocco 492 Telecom Italia 494 Email: enrico.marocco@telecomitalia.it