idnits 2.17.1
draft-irtf-p2prg-alto-survey-05.txt:
Checking boilerplate required by RFC 5378 and the IETF Trust (see
https://trustee.ietf.org/license-info):
----------------------------------------------------------------------------
No issues found here.
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 :
----------------------------------------------------------------------------
No issues found here.
Miscellaneous warnings:
----------------------------------------------------------------------------
== The copyright year in the IETF Trust and authors Copyright Line does not
match the current year
-- The document date (June 28, 2010) is 5050 days in the past. Is this
intentional?
Checking references for intended status: Informational
----------------------------------------------------------------------------
No issues found here.
Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 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: December 30, 2010 V. Gurbani
6 Bell Labs, Alcatel-Lucent
7 E. Marocco
8 Telecom Italia
9 June 28, 2010
11 A Survey on Research on the Application-Layer Traffic Optimization
12 (ALTO) Problem
13 draft-irtf-p2prg-alto-survey-05
15 Abstract
17 A significant part of the Internet traffic today is generated by
18 Peer-to-peer (P2P) applications used traditionally for file-sharing,
19 and more recently for real-time communications and live media
20 streaming. Such applications discover a route to each other through
21 an overlay network with little knowledge of the underlying network
22 topology. As a result, they may choose peers based on information
23 deduced from empirical measurements, which can lead to suboptimal
24 choices. This document, a product of the P2P Research Group,
25 presents a survey of existing literature on discovering and using
26 network topology information for application-layer traffic
27 optimization.
29 Status of this Memo
31 This Internet-Draft is submitted in full conformance with the
32 provisions of BCP 78 and BCP 79.
34 Internet-Drafts are working documents of the Internet Engineering
35 Task Force (IETF). Note that other groups may also distribute
36 working documents as Internet-Drafts. The list of current Internet-
37 Drafts is at http://datatracker.ietf.org/drafts/current/.
39 Internet-Drafts are draft documents valid for a maximum of six months
40 and may be updated, replaced, or obsoleted by other documents at any
41 time. It is inappropriate to use Internet-Drafts as reference
42 material or to cite them other than as "work in progress."
44 This Internet-Draft will expire on December 30, 2010.
46 Copyright Notice
48 Copyright (c) 2010 IETF Trust and the persons identified as the
49 document authors. All rights reserved.
51 This document is subject to BCP 78 and the IETF Trust's Legal
52 Provisions Relating to IETF Documents
53 (http://trustee.ietf.org/license-info) in effect on the date of
54 publication of this document. Please review these documents
55 carefully, as they describe your rights and restrictions with respect
56 to this document. Code Components extracted from this document must
57 include Simplified BSD License text as described in Section 4.e of
58 the Trust Legal Provisions and are provided without warranty as
59 described in the Simplified BSD License.
61 Table of Contents
63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
64 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
65 2. Survey of Existing Literature . . . . . . . . . . . . . . . . 4
66 2.1. Application-Level Topology Estimation . . . . . . . . . . 5
67 2.2. Topology Estimation through Layer Cooperation . . . . . . 8
68 2.2.1. P4P Architecture . . . . . . . . . . . . . . . . . . . 9
69 2.2.2. Oracle-based ISP-P2P Collaboration . . . . . . . . . . 9
70 2.2.3. ISP-Driven Informed Path Selection (IDIPS) Service . . 10
71 3. Application-Level Topology Estimation and the ALTO Problem . . 10
72 4. Open Issues . . . . . . . . . . . . . . . . . . . . . . . . . 12
73 4.1. Coordinate estimation or path latencies? . . . . . . . . . 12
74 4.2. Malicious nodes . . . . . . . . . . . . . . . . . . . . . 12
75 4.3. Information integrity . . . . . . . . . . . . . . . . . . 12
76 4.4. Richness of topological information . . . . . . . . . . . 13
77 4.5. Hybrid solutions . . . . . . . . . . . . . . . . . . . . . 13
78 4.6. Negative impact of over-localization . . . . . . . . . . . 13
79 5. Security Considerations . . . . . . . . . . . . . . . . . . . 14
80 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14
81 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 14
82 8. Informative References . . . . . . . . . . . . . . . . . . . . 14
83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18
85 1. Introduction
87 A significant part of today's Internet traffic is generated by Peer-
88 to-peer (P2P) applications, used originally for file sharing, and
89 more recently for realtime multimedia communications and live media
90 streaming. P2P applications are posing serious challenges to the
91 Internet infrastructure; by some estimates, P2P systems are so
92 popular that they make up anywhere between 40% to 85% of the entire
93 Internet traffic [Meeker], [Karagiannis], [LightReading],
94 [LinuxReviews], [Parker], [Glasner].
96 P2P systems ensure that popular content is replicated at multiple
97 instances in the overlay. But perhaps ironically, a peer searching
98 for that content may ignore the topology of the latent overlay
99 network and instead select among available instances based on
100 information it deduces from empirical measurements, which, in some
101 particular situations may lead to suboptimal choices. For example, a
102 shorter round-trip time estimation is not indicative of the bandwidth
103 and reliability of the underlying links, which have more of an
104 influence than delay for large file transfer P2P applications.
106 Most Distributed Hash Tables (DHT) -- the data structure that imposes
107 a specific ordering for P2P overlays -- use greedy forwarding
108 algorithms to reach their destination, making locally optimal
109 decisions that may not turn out to be globally optimized [Gummadi].
110 This naturally leads to the Application-Layer Traffic Optimization
111 (ALTO) problem [RFC5693]: how to best provide the topology of the
112 underlying network while at the same time allowing the requesting
113 node to use such information to effectively reach the node on which
114 the content resides. Thus, it would appear that P2P networks with
115 their application layer routing strategies based on overlay
116 topologies are in direct competition against the Internet routing and
117 topology.
119 One way to solve the ALTO problem is to build distributed
120 application-level services for location and path selection [Francis],
121 [Ng], [Dabek], [Costa], [Wong], [Madhyastha], in order to enable
122 peers to estimate their position in the network and to efficiently
123 select their neighbors. Similar solutions have been embedded into
124 P2P applications such as Azureus [Azureus]. A slightly different
125 approach is to have the Internet Service Provider (ISP) take a pro-
126 active role in the routing of P2P application traffic; the means by
127 which this can be achieved have been proposed [Aggarwal], [Xie],
128 [Saucez]. There is an intrinsic struggle between the layers -- P2P
129 overlay and network underlay -- when performing the same service
130 (routing), however there are strategies to mitigate this dichotomy
131 [Seetharaman].
133 This document, initially intended as a complement to RFC 5693
134 [RFC5693] and discussed during the creation of the IETF ALTO Working
135 Group, has been completed and refined in the IRTF P2P Research Group.
136 Its goal is to summarize the contemporary research activities on the
137 application layer traffic optimization problem as input to the ALTO
138 working group protocol designers.
140 1.1. Terminology
142 Terminology adopted in this document includes terms such as "ring
143 geometry", "tree structure", "butterfly network" borrowed from P2P
144 scientific literature. [RFC4981] provides an exaustive definition of
145 such terminology.
147 Certain security-related terms are to be understood in the sense
148 defined in [RFC4949]; such terms include, but are not limited to,
149 "attack", "authentication", "confidentiality", "encryption",
150 "identity", "integrity". Other security-related terms (for example,
151 "denial of service") are to be understood in the sense defined in the
152 referenced specifications.
154 2. Survey of Existing Literature
156 Gummadi et al. [Gummadi] compare popular DHT algorithms and besides
157 analyzing their resilience, provide an accurate evaluation of how
158 well the logical overlay topology maps on the physical network layer.
159 In their paper, relying only on measurements independently performed
160 by overlay nodes without the support of additional location
161 information provided by external entities, they demonstrate that the
162 most efficient algorithms in terms of resilience and proximity
163 performance are those based on the simplest geometric concept (i.e.
164 the ring geometry, rather than tree structures, butterfly networks
165 and hybrid geometries).
167 Regardless of the geometrical properties of the distributed data
168 structures involved, interactions between application-layer overlays
169 and the underlying networks are a rich area of investigation. The
170 available literature in this field can be divided in two categories
171 (Figure 1): using application-level techniques to estimate topology
172 and through some kind of layer cooperation.
174 Application-layer traffic optimization
175 |
176 +--> Application-level topology estimation
177 | |
178 | +--> Coordinates-based systems
179 | | |
180 | | +--> GNP
181 | | |
182 | | +--> Vivaldi
183 | | |
184 | | +--> PIC
185 | |
186 | +--> Path selection services
187 | | |
188 | | +--> IDMaps
189 | | |
190 | | +--> Meridian
191 | | |
192 | | +--> Ono
193 | |
194 | +--> Link-layer Internet maps
195 | |
196 | +--> iPlane
197 |
198 +--> Topology estimation through layer cooperation
199 |
200 +--> P4P: Provider portal for applications
201 |
202 +--> Oracle-based ISPs and P2P cooperation
203 |
204 +--> ISP-driven informed path selection
206 Taxonomy of solutions for the application-layer traffic optimization
207 problem.
209 Figure 1
211 2.1. Application-Level Topology Estimation
213 Estimating network topology information on the application layer has
214 been an area of active research. Early systems used triangulation
215 techniques to bound the distance between two hosts using a common
216 landmark host. In such a technique, given a cost function C, a set
217 of vertexes V and their corresponding edges, the triangle inequality
218 holds if for any triple {a, b, c} in V, C(a, c) is always less than
219 or equal to C(a, g) + C(b, c). The cost function C could be
220 expressed in terms of desirable metrics such as bandwidth or latency.
222 We note that the techniques presented in this section are only
223 representative of the sizable research in this area. Rather than
224 trying to enumerate an exhaustive list, we have chosen certain
225 techniques because they represent an advance in the area that further
226 led to derivative works.
228 Francis et al. proposed IDMaps [Francis], a system where one or more
229 special hosts called tracers are deployed near an autonomous system.
230 The distance measured in Round Trip Time (RTT) between hosts A and B
231 is estimated as the cumulative distance between A and its nearest
232 tracer Ta, plus the distance between B and its nearest tracer Tb,
233 plus the shortest distance from Ta to Tb. To aid in scalability
234 beyond that provided by the client-server design of IDMaps, Ng et al.
235 proposed a P2P-based Global Network Positioning (GNP) architecture
236 [Ng]. GNP was a network coordinate system based on absolute
237 coordinates computed from modeling the Internet as a geometric space.
238 It proposed a two-part architecture: in the first part, a small set
239 of finite distributed hosts called landmarks compute their own
240 coordinates in a fixed geometric space. In the second part, a host
241 wishing to participate computes its own coordinates relative to those
242 of the landmark hosts. Thus, armed with the computed coordinates,
243 hosts can then determine interhost distance as soon as they discover
244 each other.
246 Both IDMaps and GNP require fixed network infrastructure support in
247 the form of tracers or landmark hosts; this often introduces a single
248 point of failure and inhibits scalability. To combat this, new
249 techniques were developed that embedded the network topology in a
250 low-dimensional coordinate space to enable network distance
251 estimation through vector analysis. Costa et al. introduced
252 Practical Internet Coordinates (PIC) [Costa]. While PIC used the
253 notion of landmark hosts, it did not require explicit network support
254 to designate specific landmark hosts. Any node whose coordinates
255 have been computed could act as a landmark host. When a node joined
256 the system, it probed the network distance to some landmark hosts.
257 Then, it obtained the coordinates of each landmark host and computed
258 its own coordinates relative to the landmark host, subject to the
259 constraint of minimizing the error in the predicted distance and
260 computed distance.
262 Like PIC, Vivaldi [Dabek] proposed a fully distributed network
263 coordinate systems without any distinguished hosts. Whenever a node
264 A communicates with another node B, it measures the RTT to that node
265 and learns that node's current coordinates. A subsequently adjusts
266 its coordinates such that it is closer to, or further from B by
267 computing new coordinates that minimize the squared error. A Vivaldi
268 node is thus constantly adjusting it's position based on a simulation
269 of interconnected mass springs. Vivaldi is now being used in the
270 popular P2P application Azureus and studies indicate that it scales
271 well to very large networks [Ledlie].
273 Network coordinate systems require the embedding of the Internet
274 topology into a coordinate system. This is not always possible
275 without errors, which impacts the accuracy of distance estimations.
276 In particular, it has proved to be difficult to embed the triangular
277 inequalities found in Internet path distances [Ledlie]. Thus,
278 Meridian [Wong] abandons the generality of network coordinate systems
279 and provides specific distance evaluation services. In Meridian,
280 each node keeps track of small fixed number of neighbors and
281 organizes them in concentric rings, ordered by distance from the
282 node. Meridian locates the closest node by performing a multi-hop
283 search where each hop exponentially reduces the distance to the
284 target. Although less general than virtual coordinates, Meridian
285 incurs significantly less error for closest node discovery.
287 The Ono project [Ono] takes a different approach and uses network
288 measurements from Content Distribution Network (CDN) like Akamai to
289 find nearby peers. Used as a plugin to the Azureus BitTorrent
290 client, Ono provides 31% average download rate improvement [Su].
292 Comparison of application-level topology estimation techniques, as
293 reported in literature. Results in terms of number of (D)imensions
294 and (L)andmarks, 90th percentile relative error.
296 +----------------+---------------+----------------+-----------------+
297 | GNP vs. | PIC(b) vs. | Vivaldi vs. | Meridian vs. |
298 | IDMaps(a) (7D, | GNP (8D, 16L) | GNP (2D, 32L) | GNP (8D, 15L) |
299 | 15L) | | | |
300 +----------------+---------------+----------------+-----------------+
301 | GNP: 0.50, | PIC: 0.38, | Vivaldi: 0.65, | Meridian: 0.78, |
302 | IDMaps: 0.97 | GNP: 0.37 | GNP: 0.65 | GNP: 1.18 |
303 +----------------+---------------+----------------+-----------------+
305 (a) Does not use dimensions or landmarks. (b) Using results from the
306 hybrid strategy for PIC.
308 Table 1
310 Table 1 summarizes the application-level topology estimation
311 techniques. The salient performance metric is the relative error.
312 While all approaches define this metric a bit differently, it can be
313 generalized as how close a predicted distance comes to the
314 corresponding measured distance. A value of zero implies perfect
315 prediction and a value of 1 implies that the predicted distance is in
316 error by a factor of two. PIC, Vivaldi, and Meridian compare their
317 results with that of GNP, while GNP itself compares its results with
318 a precursor technique, IDMaps. Because each of the techniques uses a
319 different Internet topology and a varying number of landmarks and
320 dimensions to interpret the data set, it is impossible to normalize
321 the relative error across all techniques uniformly. Thus we present
322 the relative error data in pairs, as reported in the literature
323 describing the specific technique. Readers are urged to compare the
324 relative error performance in each column on its own and not draw any
325 conclusions by comparing the data across columns.
327 Most of the work on estimating topology information focuses on
328 predicting network distance in terms of latency and does not provide
329 estimates for other metrics such as throughput or packet loss rate.
330 However, for many P2P applications latency is not the most important
331 performance metric and these applications could benefit from a richer
332 information plane. Sophisticated methods of active network probing
333 and passive traffic monitoring are generally very powerful and can
334 generate network statistics indirectly related to performance
335 measures of interest, such as delay and loss rate on link-level
336 granularity. Extraction of these hidden attributes can be achieved
337 by applying statistical inference techniques developed in the field
338 of inferential network monitoring or network tomography subsequent to
339 sampling of the network state. Thus, network tomography enables the
340 extraction of a richer set of topology information, but at the same
341 time inherently increasing complexity of a potential information
342 plane and introducing estimation errors. For both active and passive
343 methods statistical models for the measurement process need to be
344 developed and the spatial and temporal dependence of the measurements
345 should be assessed. Moreover, measurement methodology and
346 statistical inference strategy must be considered jointly. For a
347 deeper discussion of network tomography and recent developments in
348 the field we refer the reader to [Coates].
350 One system providing such a service is iPlane [Madhyastha], which
351 aims at creating a annotated atlas of the Internet that contains
352 information about latency, bandwidth, capacity and loss rate. To
353 determine features of the Internet topology, iPlane bridges and
354 builds upon different ideas, such as active probing based on packet
355 dispersion techniques to infer available bandwidth along path
356 segments. These ideas are drawn from different fields, including
357 network measurement as described by Dovrolis et al. in [Dovrolis] and
358 network tomography [Coates].
360 2.2. Topology Estimation through Layer Cooperation
362 Instead of estimating topology information on the application level
363 through distributed measurements, this information could be provided
364 by the entities running the physical networks -- usually ISPs or
365 network operators. In fact, they have full knowledge of the topology
366 of the networks they administer and, in order to avoid congestion on
367 critical links, are interested in helping applications to optimize
368 the traffic they generate. The remainder of this section briefly
369 describes three recently proposed solutions that follow such an
370 approach to address the ALTO problem.
372 2.2.1. P4P Architecture
374 The architecture proposed by Xie et al. [Xie] has been adopted by
375 the DCIA P4P working group [P4P], an open group established by ISPs,
376 P2P software distributors and technology researchers with the dual
377 goal of defining mechanisms to accelerate content distribution and
378 optimize utilization of network resources.
380 The main role in the P4P architecture is played by servers called
381 "iTrackers", deployed by network providers and accessed by P2P
382 applications (or, in general, by elements of the P2P system) in order
383 to make optimal decisions when selecting a peer to connect. An
384 iTracker may offer three interfaces:
386 1. Info: Allows P2P elements (e.g. peers or trackers) to get opaque
387 information associated to an IP address. Such information is
388 kept opaque to hide the actual network topology, but can be used
389 to compute the network distance between IP addresses.
390 2. Policy: Allows P2P elements to obtain policies and guidelines of
391 the network, which specify how a network provider would like its
392 networks to be utilized at a high level, regardless of P2P
393 applications.
394 3. Capability: Allows P2P elements to request network providers'
395 capabilities.
397 The P4P architecture is under evaluation with simulations,
398 experiments on the PlanetLab distributed testbed and in field tests
399 with real users. Initial simulations and PlanetLab experiments
400 results [P4P] indicate that improvements in BitTorrent download
401 completion time and link utilization in the range of 50-70% are
402 possible. Results observed on Comcast's network during a field test
403 trial conducted with a modified version of the software used by the
404 Pando content delivery network (documented in RFC 5632 [RFC5632])
405 show average improvements in download rate in different scenarios
406 varying between 57% and 85%, and a 34% to 80% drop in the cross-
407 domain traffic generated by such an application.
409 2.2.2. Oracle-based ISP-P2P Collaboration
411 In the general solution proposed by Aggarwal et al. [Aggarwal],
412 network providers host servers, called "oracles", that help P2P users
413 choose optimal neighbours.
415 The oracle concept uses the following mechanism: a P2P client sends
416 the list of potential peers to the oracle hosted by its ISP and
417 receives a re-arranged peer list, ordered according to the ISP's
418 local routing policies and preferences. For instance, to keep the
419 traffic local, the ISP may prefer peers within its network, or it may
420 pick links with higher bandwidth or peers that are geographically
421 closer to improve application performance. Once the client has
422 obtained this ordered list, it has enough information to perform
423 better-than-random initial peer selection.
425 Such a solution has been evaluated with simulations and experiments
426 run on the PlanetLab testbed and the results show both improvements
427 in content download time and a reduction of overall P2P traffic, even
428 when only a subset of the applications actually query the oracle to
429 make their decisions.
431 2.2.3. ISP-Driven Informed Path Selection (IDIPS) Service
433 The solution proposed by Saucez et al. [Saucez] is essentially a
434 modified version of the oracle-based approach described in
435 Section 2.2.2, intended to provide a network-layer service for
436 finding best source and destination addresses when establishing a
437 connection between two endpoints in multi-homed environments (which
438 are common in IPv6 networking). Peer selection optimization in P2P
439 systems -- the ALTO problem in today's Internet -- can be addressed
440 by the IDIPS solution as a specific sub-case where the options for
441 the destination address consist of all the peers sharing a desired
442 resource, while the choice of the source address is fixed. An
443 evaluation performed on IDIPS shows that costs for both providing and
444 accessing the service are negligible.
446 3. Application-Level Topology Estimation and the ALTO Problem
448 The application-level techniques described in Section Section 2.1
449 provide tools for peer-to-peer applications to estimate parameters of
450 the underlying network topology. Although these techniques can
451 improve application performance, there are limitations of what can be
452 achieved by operating only on the application level.
454 Topology estimation techniques use abstractions of the network
455 topology which often hide features that would be of interest to the
456 application. Network coordinate systems, for example, are unable to
457 detect overlay paths shorter than the direct path in the Internet
458 topology. However, these paths frequently exist in the Internet
459 [Wang]. Similarly, application-level techniques may not accurately
460 estimate topologies with multipath routing.
462 When using network coordinates to estimate topology information the
463 underlying assumption is that distance in terms of latency determines
464 performance. However, for file sharing and content distribution
465 applications there is more to performance than just the network
466 latency between nodes. The utility of a long-lived data transfer is
467 determined by the throughput of the underlying TCP protocol, which
468 depends on the round-trip time as well as the loss rate experienced
469 on the corresponding path [Padhye]. Hence, these applications
470 benefit from a richer set of topology information that goes beyond
471 latency including loss rate, capacity and available bandwidth.
473 Some of the topology estimation techniques used by P2P applications
474 need time to converge to a result. For example, current BitTorrent
475 clients implement local, passive traffic measurements and a tit-for-
476 tat bandwidth reciprocity mechanism to optimize peer selection at a
477 local level. Peers eventually settle on a set of neighbors that
478 maximizes their download rate but because peers cannot reason about
479 the value of neighbors without actively exchanging data with them and
480 the number of concurrent data transfers is limited (typically to
481 5-7), convergence is delayed and easily can be sub-optimal.
483 Skype's P2P Voice over IP (VoIP) application chooses a relay node in
484 cases where two peers are behind NATs and cannot connect directly.
485 Ren et al. [Ren] measured that the relay selection mechanism of
486 Skype is (1) not able to discover the best possible relay nodes in
487 terms of minimum RTT, (2) requires a long setup and stabilization
488 time which degrades the end user experience, and (3) is creating a
489 non-negligible amount of overhead traffic due to probing a large
490 number of nodes. They further showed that the quality of the relay
491 paths could be improved when the underlying network Autonomous System
492 (AS) topology is considered.
494 Some features of the network topology are hard to infer through
495 application-level techniques and it may not be possible to infer them
496 at all. An example for such a feature are service provider policies
497 and preferences such as the state and cost associated with
498 interdomain peering and transit links. Another example is the
499 traffic engineering policy of a service provider, which may
500 counteract the routing objective of the overlay network leading to a
501 poor overall performance [Seetharaman].
503 Finally, application-level techniques often require applications to
504 perform measurements on the topology. These measurements create
505 traffic overhead, in particular, if measurements are performed
506 individually by all applications interested in estimating topology.
508 4. Open Issues
510 Beyond a significant amount of research work on the topic, we believe
511 that there are sizable open issues to address in an infrastructure-
512 based approach to traffic optimization. The following is not an
513 exhaustive list, but a representative sample of the pertinent issues.
515 4.1. Coordinate estimation or path latencies?
517 Despite the many solutions that have been proposed for providing
518 applications with topology information in a fully distributed manner,
519 there is currently an ongoing debate in the research community
520 whether such solutions should focus on estimating nodes' coordinates
521 or path latencies. Such a debate has recently been fed by studies
522 showing that the triangle inequality on which coordinate systems are
523 based is often proved false in the Internet [Ledlie]. Proposed
524 systems following both approaches -- in particular, Vivaldi [Dabek]
525 and PIC [Costa] following the former, Meridian [Wong] and iPlane
526 [Madhyastha] the latter -- have been simulated, implemented and
527 studied in real-world trials, each one showing different points of
528 strength and weaknesses. Concentrated work will be needed to
529 determine which of the two solutions will be conducive to the {ALTO}
530 problem.
532 4.2. Malicious nodes
534 Another open issue common in most distributed environments consisting
535 of a large number of peers is the resistance against malicious nodes.
536 Security mechanisms to identify misbehavior are based on triangle
537 inequality checks [Costa], which however tend to fail and thus return
538 false positives in presence of measurement inaccuracies induced, for
539 example, by traffic fluctuations that occur quite often in large
540 networks [Ledlie]. Beyond the issue of using triangle inequality
541 checks, authoritatively authenticating the identity of an oracle, and
542 preventing an oracle from attacks are also important. Exploration of
543 existing techniques -- such as Public Key Infrastructure (PKI)
544 [RFC5280] or identity-based encryption [Boneh] for authenticating the
545 identity and the use of secure multi-party computation techniques to
546 prevent an oracle from collusion attacks -- need to be studied for
547 judicious use in ALTO-type of solutions.
549 4.3. Information integrity
551 Similarly, even in controlled architectures deployed by network
552 operators where system elements may be authenticated [Xie],
553 [Aggarwal],[Saucez], it is still possible that the information
554 returned to applications is deliberately altered, for example,
555 assigning higher priority to financially inexpensive links instead of
556 neutrally applying proximity criteria. What are the effects of such
557 deliberate alterations if multiple peers collude to determine a
558 different route to the target, one that is not provided by an oracle?
559 Similarly, what are the consequences if an oracle targets a
560 particular node in another AS by redirecting an inordinate number of
561 querying peers to it causing, essentially, a Distributed Denial of
562 Service (DDoS) [RFC4732] attack on the node? Furthermore, does an
563 oracle broadcast or multicast a response to a query? If so,
564 techniques to protect the confidentiality of the multi-cast stream
565 will need to be investigated to thwart "free riding" peers.
567 4.4. Richness of topological information
569 Many systems already use RTT to account for delay when establishing
570 connections with peers (e.g., CAN [Ratnasamy], Bamboo [Rhea]). An
571 operator can provide not only the delay metric but other metrics that
572 the peer cannot figure out on its own. These metrics may include the
573 characteristics of the access links to other peers, bandwidth
574 available to peers (based on operator's engineering of its network),
575 network policies, and preferences such as state and cost associated
576 with intradomain peering links, and so on. Exactly what kinds of
577 metrics can an operator provide to stabilize the network throughput
578 will also need to be investigated.
580 4.5. Hybrid solutions
582 It is conceivable that P2P users may not be comfortable with operator
583 intervention to provide topology information. To eliminate this
584 intervention, alternative schemes to estimate topological distance
585 can be used. For instance, Ono uses client redirections generated by
586 Akamai CDN servers as an approximation for estimating distance to
587 peers; Vivaldi, GNP and PIC use synthetic coordinate systems. A
588 neutral third-party can make available a hybrid layer cooperation
589 service -- without the active participation of the ISP -- that uses
590 alternative techniques discussed in Section 2.1 to create a
591 topological map. This map can be subsequently used by a subset of
592 users who may not trust the ISP.
594 4.6. Negative impact of over-localization
596 The literature presented in Section 2 shows that a certain level of
597 locality-awareness in the peer selection process of P2P algorithms is
598 usually beneficial to the application performance. However, an
599 excessive localization of the traffic might cause partitioning in the
600 overlay interconnecting peers, which will negatively affect the
601 performance experienced by the peers themselves.
603 Finding the right balance between localization and randomness in peer
604 selection is an open issue. At the time of writing, it seems that
605 different applications have different levels of tolerance and should
606 be addressed separately. Le Blond et al. [LeBlond] have studied the
607 specific case of BitTorrent, proposing a simple mechanism to prevent
608 partitioning in the overlay, yet reaching a high level of cross-
609 domain traffic reduction without adversely impacting peers.
611 5. Security Considerations
613 This draft is a survey of existing literature on topology estimation.
614 As such, it does not introduce any new security considerations to be
615 taken into account beyond what is already discussed in each paper
616 surveyed.
618 6. IANA Considerations
620 None.
622 7. Acknowledgments
624 This document is a derivative work of a position paper submitted at
625 the IETF RAI area/MIT workshop held on May 28th, 2008 on the topic of
626 Peer-to-Peer Infrastructure (P2Pi) [RFC5594]. The article on a
627 similar topic from the same authors published in IEEE Communications
628 [Gurbani] was also partially derived from the same position paper.
629 The authors thank profusely Arnaud Legout, Richard Yang, Richard
630 Woundy, Stefano Previdi and the many people that have participated in
631 discussions and provided insightful feedback at any stage of this
632 work.
634 8. Informative References
636 [Aggarwal]
637 Aggarwal, V., Feldmann, A., and C. Scheidler, "Can ISPs
638 and P2P systems co-operate for improved performance?",
639 in ACM SIGCOMM Computer Communications Review, vol. 37,
640 no. 3.
642 [Azureus] "Azureus BitTorrent Client", .
644 [Boneh] Boneh, D. and M. Franklin, "Identity-Based Encryption from
645 the Weil Pairing", in proceedings of the 21st Annual
646 International Cryptology Conference on Advances in
647 Cryptology, August 2001.
649 [Coates] Coates, M., Hero, A., Nowak, R., and B. Yu, "Internet
650 Tomography", in IEEE Signal Processing Magazine, vol. 19,
651 no. 3.
653 [Costa] Costa, M., Castro, M., Rowstron, A., and P. Key, "PIC:
654 Practical Internet coordinates for distance estimation",
655 in proceedings of International Conference on Distributed
656 Systems 2003.
658 [Dabek] Dabek, F., Cox, R., Kaashoek, F., and R. Morris, "Vivaldi:
659 A Decentralized Network Coordinate System", in ACM
660 SIGCOMM: Proceedings of the 2004 conference on
661 Applications, technologies, architectures, and protocols
662 for computer communications, vol. 34, no. 4.
664 [Dovrolis]
665 Dovrolis, C., Ramanathan, P., and D. Moore, "What do
666 packet dispersion techniques measure?", in proceedings of
667 IEEE INFOCOM 2001.
669 [Francis] Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D.,
670 Shavitt, Y., and L. Zhang, "IDMaps: A global Internet host
671 distance estimation service", in proceedings of IEEE
672 INFOCOM 2001.
674 [Glasner] Glasner, J., "P2P fuels global bandwidth binge", available
675 from http://www.wired.com/.
677 [Gummadi] Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S.,
678 Shenker, S., and I. Stoica, "The impact of DHT routing
679 geometry on resilience and proximity", in ACM SIGCOMM:
680 Proceedings of the 2003 conference on Applications,
681 technologies, architectures, and protocols for computer
682 communications.
684 [Gurbani] Gurbani, V., Hilt, V., Rimac, I., Tomsu, M., and E.
685 Marocco, "A Survey of Research on the Application-Layer
686 Traffic Optimization Problem and the Need for Layer
687 Cooperation", in IEEE Communications, vol. 47, no. 8.
689 [Karagiannis]
690 Karagiannis, T., Broido, A., Brownlee, N., Claffy, K., and
691 M. Faloutsos, "Is P2P dying or just hiding?",
692 in proceedings of IEEE GLOBECOM 2004 Conference.
694 [LeBlond] Le Blond, S., Legout, A., and W. Dabbous, "Pushing
695 BitTorrent Locality to the Limit", available
696 at http://hal.inria.fr/.
698 [Ledlie] Ledlie, J., Gardner, P., and M. Seltzer, "Network
699 Coordinates in the Wild", in USENIX: Proceedings of NSDI
700 2007.
702 [LightReading]
703 LightReading, "Controlling P2P traffic", available
704 from http://www.lightreading.com/.
706 [LinuxReviews]
707 linuxReviews.org, "Peer to peer network traffic may
708 account for up to 85% of Interneta??s bandwidth usage",
709 available from http://linuxreviews.org/.
711 [Madhyastha]
712 Madhyastha, H., Isdal, T., Piatek, M., Dixon, C.,
713 Anderson, T., Krishnamurthy, A., and A. Venkataramani.,
714 "iPlane: an information plane for distributed services",
715 in USENIX: Proceedings of the 7th symposium on Operating
716 systems design and implementation.
718 [Meeker] Meeker, M. and D. Joseph, "The State of the Internet, Part
719 3", available from http://www.morganstanley.com/.
721 [Ng] Ng, T. and H. Zhang, "Predicting internet network distance
722 with coordinates-based approaches", in proceedings of
723 INFOCOM 2002.
725 [Ono] "Northwestern University Ono Project",
726 .
729 [P4P] "DCIA P4P Working group",
730 .
732 [Padhye] Padhye, J., Firoiu, V., Towsley, D., and J. Kurose,
733 "Modeling TCP throughput: A simple model and its empirical
734 validation", in Technical Report UM-CS-1998-008,
735 University of Massachusetts 1998.
737 [Parker] Parker, A., "The true picture of peer-to-peer
738 filesharing", available from http://www.cachelogic.com/.
740 [RFC4732] Handley, M., Rescorla, E., and IAB, "Internet Denial-of-
741 Service Considerations", RFC 4732, December 2006.
743 [RFC4949] Shirey, R., "Internet Security Glossary, Version 2",
744 RFC 4949, August 2007.
746 [RFC4981] Risson, J. and T. Moors, "Survey of Research towards
747 Robust Peer-to-Peer Networks: Search Methods", RFC 4981,
748 September 2007.
750 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
751 Housley, R., and W. Polk, "Internet X.509 Public Key
752 Infrastructure Certificate and Certificate Revocation List
753 (CRL) Profile", RFC 5280, May 2008.
755 [RFC5594] Peterson, J. and A. Cooper, "Report from the IETF Workshop
756 on Peer-to-Peer (P2P) Infrastructure, May 28, 2008",
757 RFC 5594, July 2009.
759 [RFC5632] Griffiths, C., Livingood, J., Popkin, L., Woundy, R., and
760 Y. Yang, "Comcast's ISP Experiences in a Proactive Network
761 Provider Participation for P2P (P4P) Technical Trial",
762 RFC 5632, September 2009.
764 [RFC5693] Seedorf, J. and E. Burger, "Application-Layer Traffic
765 Optimization (ALTO) Problem Statement", RFC 5693,
766 October 2009.
768 [Ratnasamy]
769 Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S.
770 Shenker, "A Scalable Content-Addressable Network", in ACM
771 SIGCOMM: Proceedings of the 2001 conference on
772 Applications, technologies, architectures, and protocols
773 for computer communications, January 2001.
775 [Ren] Ren, S., Guo, L., and X. Zhang, "ASAP: An AS-aware peer-
776 relay protocol for high quality VoIP", in proceedings of
777 IEEE ICDCS 2006.
779 [Rhea] Rhea, S., Godfrey, B., Karp, B., Kubiatowicz, J.,
780 Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu,
781 "OpenDHT: a public DHT service and its uses", in ACM
782 SIGCOMM: Proceedings of the 2005 conference on
783 Applications, technologies, architectures, and protocols
784 for computer communications, August 2005.
786 [Saucez] Saucez, D., Donnet, B., and O. Bonaventure,
787 "Implementation and Preliminary Evaluation of an ISP-
788 Driven Informed Path Selection", in proceedings of ACM
789 CoNEXT 2007.
791 [Seetharaman]
792 Seetharaman, S., Hilt, V., Hofmann, M., and M. Ammar,
793 "Preemptive Strategies to Improve Routing Performance of
794 Native and Overlay Layers", in proceedings of IEEE INFOCOM
795 2007.
797 [Su] Su, A., Choffnes, D., Kuzmanovic, A., and F. Bustamante,
798 "Drafting behind Akamai (travelocity-based detouring)",
799 in ACM SIGCOMM: Proceedings of the 2006 conference on
800 Applications, technologies, architectures, and protocols
801 for computer communications.
803 [Wang] Wang, G., Zhang, B., and T. Ng, "Towards Network Triangle
804 Inequality Violation Aware Distributed Systems", in ACM
805 SIGCOMM: Proceedings of the 7th conference on Internet
806 measurement.
808 [Wong] Wong, B., Slivkins, A., and E. Sirer, "Meridian: A
809 lightweight network location service without virtual
810 coordinates", in ACM SIGCOMM: Proceedings of the 2005
811 conference on Applications, technologies, architectures,
812 and protocols for computer communications.
814 [Xie] Xie, H., Yang, Y., Krishnamurthy, A., Liu, Y., and A.
815 Silberschatz, "P4P: Explicit Communications for
816 Cooperative Control Between P2P and Network Providers",
817 in ACM SIGCOMM Computer Communication Review, vol. 38, no.
818 4.
820 Authors' Addresses
822 Ivica Rimac
823 Bell Labs, Alcatel-Lucent
825 Email: rimac@bell-labs.com
827 Volker Hilt
828 Bell Labs, Alcatel-Lucent
830 Email: volkerh@bell-labs.com
832 Marco Tomsu
833 Bell Labs, Alcatel-Lucent
835 Email: marco.tomsu@alcatel-lucent.com
836 Vijay K. Gurbani
837 Bell Labs, Alcatel-Lucent
839 Email: vkg@bell-labs.com
841 Enrico Marocco
842 Telecom Italia
844 Email: enrico.marocco@telecomitalia.it