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