A Survey on Research on the Application-Layer Traffic Optimization (ALTO) Problem
draft-irtf-p2prg-alto-survey-05

Abstract

A significant part of the Internet traffic today is generated by Peer-to-peer (P2P) applications used traditionally for file-sharing, and more recently for real-time communications and live media streaming. Such applications discover a route to each other through an overlay network with little knowledge of the underlying network topology. As a result, they may choose peers based on information deduced from empirical measurements, which can lead to suboptimal choices. This document, a product of the P2P Research Group, presents a survey of existing literature on discovering and using network topology information for application-layer traffic optimization.

Status of this Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

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.”

This Internet-Draft will expire on December 30, 2010.

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 Simplified BSD License.

Table of Contents

1.  Introduction
    1.1.  Terminology
2.  Survey of Existing Literature
    2.1.  Application-Level Topology Estimation
    2.2.  Topology Estimation through Layer Cooperation
        2.2.1.  P4P Architecture
        2.2.2.  Oracle-based ISP-P2P Collaboration
        2.2.3.  ISP-Driven Informed Path Selection (IDIPS) Service
3.  Application-Level Topology Estimation and the ALTO Problem
4.  Open Issues
    4.1.  Coordinate estimation or path latencies?
    4.2.  Malicious nodes
    4.3.  Information integrity
    4.4.  Richness of topological information
    4.5.  Hybrid solutions
    4.6.  Negative impact of over-localization
5.  Security Considerations
6.  IANA Considerations
7.  Acknowledgments
8.  Informative References
§  Authors' Addresses

1.  Introduction

A significant part of today's Internet traffic is generated by Peer-to-peer (P2P) applications, used originally for file sharing, and more recently for realtime multimedia communications and live media streaming. P2P applications are posing serious challenges to the Internet infrastructure; by some estimates, P2P systems are so popular that they make up anywhere between 40% to 85% of the entire Internet traffic [Meeker] (Meeker, M. and D. Joseph, “The State of the Internet, Part 3,” .), [Karagiannis] (Karagiannis, T., Broido, A., Brownlee, N., Claffy, K., and M. Faloutsos, “Is P2P dying or just hiding?,” .), [LightReading] (LightReading, “Controlling P2P traffic,” .), [LinuxReviews] (linuxReviews.org, “Peer to peer network traffic may account for up to 85% of Internetâ??s bandwidth usage,” .), [Parker] (Parker, A., “The true picture of peer-to-peer filesharing,” .), [Glasner] (Glasner, J., “P2P fuels global bandwidth binge,” .).

P2P systems ensure that popular content is replicated at multiple instances in the overlay. But perhaps ironically, a peer searching for that content may ignore the topology of the latent overlay network and instead select among available instances based on information it deduces from empirical measurements, which, in some particular situations may lead to suboptimal choices. For example, a shorter round-trip time estimation is not indicative of the bandwidth and reliability of the underlying links, which have more of an influence than delay for large file transfer P2P applications.

Most Distributed Hash Tables (DHT) -- the data structure that imposes a specific ordering for P2P overlays -- use greedy forwarding algorithms to reach their destination, making locally optimal decisions that may not turn out to be globally optimized [Gummadi] (Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S., and I. Stoica, “The impact of DHT routing geometry on resilience and proximity,” .). This naturally leads to the Application-Layer Traffic Optimization (ALTO) problem [RFC5693] (Seedorf, J. and E. Burger, “Application-Layer Traffic Optimization (ALTO) Problem Statement,” October 2009.): how to best provide the topology of the underlying network while at the same time allowing the requesting node to use such information to effectively reach the node on which the content resides. Thus, it would appear that P2P networks with their application layer routing strategies based on overlay topologies are in direct competition against the Internet routing and topology.

One way to solve the ALTO problem is to build distributed application-level services for location and path selection [Francis] (Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and L. Zhang, “IDMaps: A global Internet host distance estimation service,” .), [Ng] (Ng, T. and H. Zhang, “Predicting internet network distance with coordinates-based approaches,” .), [Dabek] (Dabek, F., Cox, R., Kaashoek, F., and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” .), [Costa] (Costa, M., Castro, M., Rowstron, A., and P. Key, “PIC: Practical Internet coordinates for distance estimation,” .), [Wong] (Wong, B., Slivkins, A., and E. Sirer, “Meridian: A lightweight network location service without virtual coordinates,” .), [Madhyastha] (Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., Anderson, T., Krishnamurthy, A., and A. Venkataramani., “iPlane: an information plane for distributed services,” .), in order to enable peers to estimate their position in the network and to efficiently select their neighbors. Similar solutions have been embedded into P2P applications such as Azureus [Azureus] (, “Azureus BitTorrent Client,” .). A slightly different approach is to have the Internet Service Provider (ISP) take a pro-active role in the routing of P2P application traffic; the means by which this can be achieved have been proposed [Aggarwal] (Aggarwal, V., Feldmann, A., and C. Scheidler, “Can ISPs and P2P systems co-operate for improved performance?,” .), [Xie] (Xie, H., Yang, Y., Krishnamurthy, A., Liu, Y., and A. Silberschatz, “P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers,” .), [Saucez] (Saucez, D., Donnet, B., and O. Bonaventure, “Implementation and Preliminary Evaluation of an ISP-Driven Informed Path Selection,” .). There is an intrinsic struggle between the layers -- P2P overlay and network underlay -- when performing the same service (routing), however there are strategies to mitigate this dichotomy [Seetharaman] (Seetharaman, S., Hilt, V., Hofmann, M., and M. Ammar, “Preemptive Strategies to Improve Routing Performance of Native and Overlay Layers,” .).

This document, initially intended as a complement to RFC 5693 (Seedorf, J. and E. Burger, “Application-Layer Traffic Optimization (ALTO) Problem Statement,” October 2009.) [RFC5693] and discussed during the creation of the IETF ALTO Working Group, has been completed and refined in the IRTF P2P Research Group. Its goal is to summarize the contemporary research activities on the application layer traffic optimization problem as input to the ALTO working group protocol designers.

1.1.  Terminology

Terminology adopted in this document includes terms such as "ring geometry", "tree structure", "butterfly network" borrowed from P2P scientific literature. [RFC4981] (Risson, J. and T. Moors, “Survey of Research towards Robust Peer-to-Peer Networks: Search Methods,” September 2007.) provides an exaustive definition of such terminology.

Certain security-related terms are to be understood in the sense defined in [RFC4949] (Shirey, R., “Internet Security Glossary, Version 2,” August 2007.); such terms include, but are not limited to, "attack", "authentication", "confidentiality", "encryption", "identity", "integrity". Other security-related terms (for example, "denial of service") are to be understood in the sense defined in the referenced specifications.

2.  Survey of Existing Literature

Gummadi et al. [Gummadi] (Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S., and I. Stoica, “The impact of DHT routing geometry on resilience and proximity,” .) compare popular DHT algorithms and besides analyzing their resilience, provide an accurate evaluation of how well the logical overlay topology maps on the physical network layer. In their paper, relying only on measurements independently performed by overlay nodes without the support of additional location information provided by external entities, they demonstrate that the most efficient algorithms in terms of resilience and proximity performance are those based on the simplest geometric concept (i.e. the ring geometry, rather than tree structures, butterfly networks and hybrid geometries).

Regardless of the geometrical properties of the distributed data structures involved, interactions between application-layer overlays and the underlying networks are a rich area of investigation. The available literature in this field can be divided in two categories (Figure 1): using application-level techniques to estimate topology and through some kind of layer cooperation.

  Application-layer traffic optimization
    |
    +--> Application-level topology estimation
    |      |
    |      +--> Coordinates-based systems
    |      |      |
    |      |      +--> GNP
    |      |      |
    |      |      +--> Vivaldi
    |      |      |
    |      |      +--> PIC
    |      |
    |      +--> Path selection services
    |      |      |
    |      |      +--> IDMaps
    |      |      |
    |      |      +--> Meridian
    |      |      |
    |      |      +--> Ono
    |      |
    |      +--> Link-layer Internet maps
    |             |
    |             +--> iPlane
    |
    +--> Topology estimation through layer cooperation
           |
           +--> P4P: Provider portal for applications
           |
           +--> Oracle-based ISPs and P2P cooperation
           |
           +--> ISP-driven informed path selection

Taxonomy of solutions for the application-layer traffic optimization problem.

2.1.  Application-Level Topology Estimation

Estimating network topology information on the application layer has been an area of active research. Early systems used triangulation techniques to bound the distance between two hosts using a common landmark host. In such a technique, given a cost function C, a set of vertexes V and their corresponding edges, the triangle inequality holds if for any triple {a, b, c} in V, C(a, c) is always less than or equal to C(a, g) + C(b, c). The cost function C could be expressed in terms of desirable metrics such as bandwidth or latency.

We note that the techniques presented in this section are only representative of the sizable research in this area. Rather than trying to enumerate an exhaustive list, we have chosen certain techniques because they represent an advance in the area that further led to derivative works.

Francis et al. proposed IDMaps (Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and L. Zhang, “IDMaps: A global Internet host distance estimation service,” .) [Francis], a system where one or more special hosts called tracers are deployed near an autonomous system. The distance measured in Round Trip Time (RTT) between hosts A and B is estimated as the cumulative distance between A and its nearest tracer Ta, plus the distance between B and its nearest tracer Tb, plus the shortest distance from Ta to Tb. To aid in scalability beyond that provided by the client-server design of IDMaps, Ng et al. proposed a P2P-based Global Network Positioning (GNP) architecture (Ng, T. and H. Zhang, “Predicting internet network distance with coordinates-based approaches,” .) [Ng]. GNP was a network coordinate system based on absolute coordinates computed from modeling the Internet as a geometric space. It proposed a two-part architecture: in the first part, a small set of finite distributed hosts called landmarks compute their own coordinates in a fixed geometric space. In the second part, a host wishing to participate computes its own coordinates relative to those of the landmark hosts. Thus, armed with the computed coordinates, hosts can then determine interhost distance as soon as they discover each other.

Both IDMaps and GNP require fixed network infrastructure support in the form of tracers or landmark hosts; this often introduces a single point of failure and inhibits scalability. To combat this, new techniques were developed that embedded the network topology in a low-dimensional coordinate space to enable network distance estimation through vector analysis. Costa et al. introduced Practical Internet Coordinates (PIC) (Costa, M., Castro, M., Rowstron, A., and P. Key, “PIC: Practical Internet coordinates for distance estimation,” .) [Costa]. While PIC used the notion of landmark hosts, it did not require explicit network support to designate specific landmark hosts. Any node whose coordinates have been computed could act as a landmark host. When a node joined the system, it probed the network distance to some landmark hosts. Then, it obtained the coordinates of each landmark host and computed its own coordinates relative to the landmark host, subject to the constraint of minimizing the error in the predicted distance and computed distance.

Like PIC, Vivaldi (Dabek, F., Cox, R., Kaashoek, F., and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” .) [Dabek] proposed a fully distributed network coordinate systems without any distinguished hosts. Whenever a node A communicates with another node B, it measures the RTT to that node and learns that node's current coordinates. A subsequently adjusts its coordinates such that it is closer to, or further from B by computing new coordinates that minimize the squared error. A Vivaldi node is thus constantly adjusting it's position based on a simulation of interconnected mass springs. Vivaldi is now being used in the popular P2P application Azureus and studies indicate that it scales well to very large networks [Ledlie] (Ledlie, J., Gardner, P., and M. Seltzer, “Network Coordinates in the Wild,” .).

Network coordinate systems require the embedding of the Internet topology into a coordinate system. This is not always possible without errors, which impacts the accuracy of distance estimations. In particular, it has proved to be difficult to embed the triangular inequalities found in Internet path distances [Ledlie] (Ledlie, J., Gardner, P., and M. Seltzer, “Network Coordinates in the Wild,” .). Thus, Meridian (Wong, B., Slivkins, A., and E. Sirer, “Meridian: A lightweight network location service without virtual coordinates,” .) [Wong] abandons the generality of network coordinate systems and provides specific distance evaluation services. In Meridian, each node keeps track of small fixed number of neighbors and organizes them in concentric rings, ordered by distance from the node. Meridian locates the closest node by performing a multi-hop search where each hop exponentially reduces the distance to the target. Although less general than virtual coordinates, Meridian incurs significantly less error for closest node discovery.

The Ono project (, “Northwestern University Ono Project,” .) [Ono] takes a different approach and uses network measurements from Content Distribution Network (CDN) like Akamai to find nearby peers. Used as a plugin to the Azureus BitTorrent client, Ono provides 31% average download rate improvement [Su] (Su, A., Choffnes, D., Kuzmanovic, A., and F. Bustamante, “Drafting behind Akamai (travelocity-based detouring),” .).

Comparison of application-level topology estimation techniques, as reported in literature. Results in terms of number of (D)imensions and (L)andmarks, 90th percentile relative error.

(a) Does not use dimensions or landmarks. (b) Using results from the hybrid strategy for PIC.

Table 1 summarizes the application-level topology estimation techniques. The salient performance metric is the relative error. While all approaches define this metric a bit differently, it can be generalized as how close a predicted distance comes to the corresponding measured distance. A value of zero implies perfect prediction and a value of 1 implies that the predicted distance is in error by a factor of two. PIC, Vivaldi, and Meridian compare their results with that of GNP, while GNP itself compares its results with a precursor technique, IDMaps. Because each of the techniques uses a different Internet topology and a varying number of landmarks and dimensions to interpret the data set, it is impossible to normalize the relative error across all techniques uniformly. Thus we present the relative error data in pairs, as reported in the literature describing the specific technique. Readers are urged to compare the relative error performance in each column on its own and not draw any conclusions by comparing the data across columns.

Most of the work on estimating topology information focuses on predicting network distance in terms of latency and does not provide estimates for other metrics such as throughput or packet loss rate. However, for many P2P applications latency is not the most important performance metric and these applications could benefit from a richer information plane. Sophisticated methods of active network probing and passive traffic monitoring are generally very powerful and can generate network statistics indirectly related to performance measures of interest, such as delay and loss rate on link-level granularity. Extraction of these hidden attributes can be achieved by applying statistical inference techniques developed in the field of inferential network monitoring or network tomography subsequent to sampling of the network state. Thus, network tomography enables the extraction of a richer set of topology information, but at the same time inherently increasing complexity of a potential information plane and introducing estimation errors. For both active and passive methods statistical models for the measurement process need to be developed and the spatial and temporal dependence of the measurements should be assessed. Moreover, measurement methodology and statistical inference strategy must be considered jointly. For a deeper discussion of network tomography and recent developments in the field we refer the reader to [Coates] (Coates, M., Hero, A., Nowak, R., and B. Yu, “Internet Tomography,” .).

One system providing such a service is iPlane (Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., Anderson, T., Krishnamurthy, A., and A. Venkataramani., “iPlane: an information plane for distributed services,” .) [Madhyastha], which aims at creating a annotated atlas of the Internet that contains information about latency, bandwidth, capacity and loss rate. To determine features of the Internet topology, iPlane bridges and builds upon different ideas, such as active probing based on packet dispersion techniques to infer available bandwidth along path segments. These ideas are drawn from different fields, including network measurement as described by Dovrolis et al. in [Dovrolis] (Dovrolis, C., Ramanathan, P., and D. Moore, “What do packet dispersion techniques measure?,” .) and network tomography (Coates, M., Hero, A., Nowak, R., and B. Yu, “Internet Tomography,” .) [Coates].

2.2.  Topology Estimation through Layer Cooperation

Instead of estimating topology information on the application level through distributed measurements, this information could be provided by the entities running the physical networks -- usually ISPs or network operators. In fact, they have full knowledge of the topology of the networks they administer and, in order to avoid congestion on critical links, are interested in helping applications to optimize the traffic they generate. The remainder of this section briefly describes three recently proposed solutions that follow such an approach to address the ALTO problem.

2.2.1.  P4P Architecture

The architecture proposed by Xie et al. [Xie] (Xie, H., Yang, Y., Krishnamurthy, A., Liu, Y., and A. Silberschatz, “P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers,” .) has been adopted by the DCIA P4P working group [P4P] (, “DCIA P4P Working group,” .), an open group established by ISPs, P2P software distributors and technology researchers with the dual goal of defining mechanisms to accelerate content distribution and optimize utilization of network resources.

The main role in the P4P architecture is played by servers called "iTrackers", deployed by network providers and accessed by P2P applications (or, in general, by elements of the P2P system) in order to make optimal decisions when selecting a peer to connect. An iTracker may offer three interfaces:

1. Info: Allows P2P elements (e.g. peers or trackers) to get opaque information associated to an IP address. Such information is kept opaque to hide the actual network topology, but can be used to compute the network distance between IP addresses.
2. Policy: Allows P2P elements to obtain policies and guidelines of the network, which specify how a network provider would like its networks to be utilized at a high level, regardless of P2P applications.
3. Capability: Allows P2P elements to request network providers' capabilities.

The P4P architecture is under evaluation with simulations, experiments on the PlanetLab distributed testbed and in field tests with real users. Initial simulations and PlanetLab experiments results [P4P] (, “DCIA P4P Working group,” .) indicate that improvements in BitTorrent download completion time and link utilization in the range of 50-70% are possible. Results observed on Comcast's network during a field test trial conducted with a modified version of the software used by the Pando content delivery network (documented in RFC 5632 (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,” September 2009.) [RFC5632]) show average improvements in download rate in different scenarios varying between 57% and 85%, and a 34% to 80% drop in the cross-domain traffic generated by such an application.

2.2.2.  Oracle-based ISP-P2P Collaboration

In the general solution proposed by Aggarwal et al. [Aggarwal] (Aggarwal, V., Feldmann, A., and C. Scheidler, “Can ISPs and P2P systems co-operate for improved performance?,” .), network providers host servers, called "oracles", that help P2P users choose optimal neighbours.

The oracle concept uses the following mechanism: a P2P client sends the list of potential peers to the oracle hosted by its ISP and receives a re-arranged peer list, ordered according to the ISP's local routing policies and preferences. For instance, to keep the traffic local, the ISP may prefer peers within its network, or it may pick links with higher bandwidth or peers that are geographically closer to improve application performance. Once the client has obtained this ordered list, it has enough information to perform better-than-random initial peer selection.

Such a solution has been evaluated with simulations and experiments run on the PlanetLab testbed and the results show both improvements in content download time and a reduction of overall P2P traffic, even when only a subset of the applications actually query the oracle to make their decisions.

2.2.3.  ISP-Driven Informed Path Selection (IDIPS) Service

The solution proposed by Saucez et al. [Saucez] (Saucez, D., Donnet, B., and O. Bonaventure, “Implementation and Preliminary Evaluation of an ISP-Driven Informed Path Selection,” .) is essentially a modified version of the oracle-based approach described in Section 2.2.2 (Oracle-based ISP-P2P Collaboration), intended to provide a network-layer service for finding best source and destination addresses when establishing a connection between two endpoints in multi-homed environments (which are common in IPv6 networking). Peer selection optimization in P2P systems -- the ALTO problem in today's Internet -- can be addressed by the IDIPS solution as a specific sub-case where the options for the destination address consist of all the peers sharing a desired resource, while the choice of the source address is fixed. An evaluation performed on IDIPS shows that costs for both providing and accessing the service are negligible.

3.  Application-Level Topology Estimation and the ALTO Problem

The application-level techniques described in Section Section 2.1 (Application-Level Topology Estimation) provide tools for peer-to-peer applications to estimate parameters of the underlying network topology. Although these techniques can improve application performance, there are limitations of what can be achieved by operating only on the application level.

Topology estimation techniques use abstractions of the network topology which often hide features that would be of interest to the application. Network coordinate systems, for example, are unable to detect overlay paths shorter than the direct path in the Internet topology. However, these paths frequently exist in the Internet [Wang] (Wang, G., Zhang, B., and T. Ng, “Towards Network Triangle Inequality Violation Aware Distributed Systems,” .). Similarly, application-level techniques may not accurately estimate topologies with multipath routing.

When using network coordinates to estimate topology information the underlying assumption is that distance in terms of latency determines performance. However, for file sharing and content distribution applications there is more to performance than just the network latency between nodes. The utility of a long-lived data transfer is determined by the throughput of the underlying TCP protocol, which depends on the round-trip time as well as the loss rate experienced on the corresponding path [Padhye] (Padhye, J., Firoiu, V., Towsley, D., and J. Kurose, “Modeling TCP throughput: A simple model and its empirical validation,” .). Hence, these applications benefit from a richer set of topology information that goes beyond latency including loss rate, capacity and available bandwidth.

Some of the topology estimation techniques used by P2P applications need time to converge to a result. For example, current BitTorrent clients implement local, passive traffic measurements and a tit-for-tat bandwidth reciprocity mechanism to optimize peer selection at a local level. Peers eventually settle on a set of neighbors that maximizes their download rate but because peers cannot reason about the value of neighbors without actively exchanging data with them and the number of concurrent data transfers is limited (typically to 5-7), convergence is delayed and easily can be sub-optimal.

Skype's P2P Voice over IP (VoIP) application chooses a relay node in cases where two peers are behind NATs and cannot connect directly. Ren et al. [Ren] (Ren, S., Guo, L., and X. Zhang, “ASAP: An AS-aware peer-relay protocol for high quality VoIP,” .) measured that the relay selection mechanism of Skype is (1) not able to discover the best possible relay nodes in terms of minimum RTT, (2) requires a long setup and stabilization time which degrades the end user experience, and (3) is creating a non-negligible amount of overhead traffic due to probing a large number of nodes. They further showed that the quality of the relay paths could be improved when the underlying network Autonomous System (AS) topology is considered.

Some features of the network topology are hard to infer through application-level techniques and it may not be possible to infer them at all. An example for such a feature are service provider policies and preferences such as the state and cost associated with interdomain peering and transit links. Another example is the traffic engineering policy of a service provider, which may counteract the routing objective of the overlay network leading to a poor overall performance [Seetharaman] (Seetharaman, S., Hilt, V., Hofmann, M., and M. Ammar, “Preemptive Strategies to Improve Routing Performance of Native and Overlay Layers,” .).

Finally, application-level techniques often require applications to perform measurements on the topology. These measurements create traffic overhead, in particular, if measurements are performed individually by all applications interested in estimating topology.

4.  Open Issues

Beyond a significant amount of research work on the topic, we believe that there are sizable open issues to address in an infrastructure-based approach to traffic optimization. The following is not an exhaustive list, but a representative sample of the pertinent issues.

4.1.  Coordinate estimation or path latencies?

Despite the many solutions that have been proposed for providing applications with topology information in a fully distributed manner, there is currently an ongoing debate in the research community whether such solutions should focus on estimating nodes' coordinates or path latencies. Such a debate has recently been fed by studies showing that the triangle inequality on which coordinate systems are based is often proved false in the Internet [Ledlie] (Ledlie, J., Gardner, P., and M. Seltzer, “Network Coordinates in the Wild,” .). Proposed systems following both approaches -- in particular, Vivaldi [Dabek] (Dabek, F., Cox, R., Kaashoek, F., and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” .) and PIC [Costa] (Costa, M., Castro, M., Rowstron, A., and P. Key, “PIC: Practical Internet coordinates for distance estimation,” .) following the former, Meridian [Wong] (Wong, B., Slivkins, A., and E. Sirer, “Meridian: A lightweight network location service without virtual coordinates,” .) and iPlane [Madhyastha] (Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., Anderson, T., Krishnamurthy, A., and A. Venkataramani., “iPlane: an information plane for distributed services,” .) the latter -- have been simulated, implemented and studied in real-world trials, each one showing different points of strength and weaknesses. Concentrated work will be needed to determine which of the two solutions will be conducive to the {ALTO} problem.

4.2.  Malicious nodes

Another open issue common in most distributed environments consisting of a large number of peers is the resistance against malicious nodes. Security mechanisms to identify misbehavior are based on triangle inequality checks [Costa] (Costa, M., Castro, M., Rowstron, A., and P. Key, “PIC: Practical Internet coordinates for distance estimation,” .), which however tend to fail and thus return false positives in presence of measurement inaccuracies induced, for example, by traffic fluctuations that occur quite often in large networks [Ledlie] (Ledlie, J., Gardner, P., and M. Seltzer, “Network Coordinates in the Wild,” .). Beyond the issue of using triangle inequality checks, authoritatively authenticating the identity of an oracle, and preventing an oracle from attacks are also important. Exploration of existing techniques -- such as Public Key Infrastructure (PKI) (Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, “Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile,” May 2008.) [RFC5280] or identity-based encryption (Boneh, D. and M. Franklin, “Identity-Based Encryption from the Weil Pairing,” August 2001.) [Boneh] for authenticating the identity and the use of secure multi-party computation techniques to prevent an oracle from collusion attacks -- need to be studied for judicious use in ALTO-type of solutions.

4.3.  Information integrity

Similarly, even in controlled architectures deployed by network operators where system elements may be authenticated [Xie] (Xie, H., Yang, Y., Krishnamurthy, A., Liu, Y., and A. Silberschatz, “P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers,” .), [Aggarwal] (Aggarwal, V., Feldmann, A., and C. Scheidler, “Can ISPs and P2P systems co-operate for improved performance?,” .),[Saucez] (Saucez, D., Donnet, B., and O. Bonaventure, “Implementation and Preliminary Evaluation of an ISP-Driven Informed Path Selection,” .), it is still possible that the information returned to applications is deliberately altered, for example, assigning higher priority to financially inexpensive links instead of neutrally applying proximity criteria. What are the effects of such deliberate alterations if multiple peers collude to determine a different route to the target, one that is not provided by an oracle? Similarly, what are the consequences if an oracle targets a particular node in another AS by redirecting an inordinate number of querying peers to it causing, essentially, a Distributed Denial of Service (DDoS) (Handley, M., Rescorla, E., and IAB, “Internet Denial-of-Service Considerations,” December 2006.) [RFC4732] attack on the node? Furthermore, does an oracle broadcast or multicast a response to a query? If so, techniques to protect the confidentiality of the multi-cast stream will need to be investigated to thwart "free riding" peers.

4.4.  Richness of topological information

Many systems already use RTT to account for delay when establishing connections with peers (e.g., CAN (Ratnasamy, S., Francis, P., Handley, M., Karp, R., and S. Shenker, “A Scalable Content-Addressable Network,” January 2001.) [Ratnasamy], Bamboo (Rhea, S., Godfrey, B., Karp, B., Kubiatowicz, J., Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, “OpenDHT: a public DHT service and its uses,” August 2005.) [Rhea]). An operator can provide not only the delay metric but other metrics that the peer cannot figure out on its own. These metrics may include the characteristics of the access links to other peers, bandwidth available to peers (based on operator's engineering of its network), network policies, and preferences such as state and cost associated with intradomain peering links, and so on. Exactly what kinds of metrics can an operator provide to stabilize the network throughput will also need to be investigated.

4.5.  Hybrid solutions

It is conceivable that P2P users may not be comfortable with operator intervention to provide topology information. To eliminate this intervention, alternative schemes to estimate topological distance can be used. For instance, Ono uses client redirections generated by Akamai CDN servers as an approximation for estimating distance to peers; Vivaldi, GNP and PIC use synthetic coordinate systems. A neutral third-party can make available a hybrid layer cooperation service -- without the active participation of the ISP -- that uses alternative techniques discussed in Section 2.1 (Application-Level Topology Estimation) to create a topological map. This map can be subsequently used by a subset of users who may not trust the ISP.

4.6.  Negative impact of over-localization

The literature presented in Section 2 (Survey of Existing Literature) shows that a certain level of locality-awareness in the peer selection process of P2P algorithms is usually beneficial to the application performance. However, an excessive localization of the traffic might cause partitioning in the overlay interconnecting peers, which will negatively affect the performance experienced by the peers themselves.

Finding the right balance between localization and randomness in peer selection is an open issue. At the time of writing, it seems that different applications have different levels of tolerance and should be addressed separately. Le Blond et al. [LeBlond] (Le Blond, S., Legout, A., and W. Dabbous, “Pushing BitTorrent Locality to the Limit,” .) have studied the specific case of BitTorrent, proposing a simple mechanism to prevent partitioning in the overlay, yet reaching a high level of cross-domain traffic reduction without adversely impacting peers.

5.  Security Considerations

This draft is a survey of existing literature on topology estimation. As such, it does not introduce any new security considerations to be taken into account beyond what is already discussed in each paper surveyed.

6.  IANA Considerations

None.

7.  Acknowledgments

This document is a derivative work of a position paper submitted at the IETF RAI area/MIT workshop held on May 28th, 2008 on the topic of Peer-to-Peer Infrastructure (P2Pi) (Peterson, J. and A. Cooper, “Report from the IETF Workshop on Peer-to-Peer (P2P) Infrastructure, May 28, 2008,” July 2009.) [RFC5594]. The article on a similar topic from the same authors published in IEEE Communications (Gurbani, V., Hilt, V., Rimac, I., Tomsu, M., and E. Marocco, “A Survey of Research on the Application-Layer Traffic Optimization Problem and the Need for Layer Cooperation,” .) [Gurbani] was also partially derived from the same position paper. The authors thank profusely Arnaud Legout, Richard Yang, Richard Woundy, Stefano Previdi and the many people that have participated in discussions and provided insightful feedback at any stage of this work.

8. Informative References

Authors' Addresses