A Survey on Research on the Application-Layer Traffic Optimization (ALTO) Problem
draft-hilt-alto-survey-00

Status of this Memo

By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

This Internet-Draft will expire on January 5, 2009.

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. We refer to this as the Application Layer Traffic Optimization (ALTO) problem. In this draft we present a survey of existing literature on discovering topology characteristics.

Table of Contents

1.  Introduction
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.  Security Considerations
5.  Informative References
§  Authors' Addresses
§  Intellectual Property and Copyright Statements

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,” .), [Karag] (Karagiannis, T., Broido, A., Brownlee, N., Claffy, K., and M. Faloutsos, “Is P2P dying or just hiding?,” .), [Light] (Lightreading, “Controlling P2P traffic,” .), [Linux] (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 to be globally optimized [Gummadi‑1] (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 [I‑D.marocco‑alto‑problem‑statement] (Marocco, E. and V. Gurbani, “Application-Layer Traffic Optimization (ALTO) Problem Statement,” April 2008.): 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‑1] (Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and L. Zhang, “IDMaps: A global Internet host distance estimation service,” .), [Ng‑1] (Ng, T. and H. Zhang, “Predicting internet network distance with coordinates-based approaches,” .), [Dabek‑1] (Dabek, F., Cox, R., Kaashoek, F., and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” .), [Costa‑1] (Costa, M., Castro, M., Rowstron, A., and P. Key, “PIC: Practical Internet coordinates for distance estimation,” .), [Wong‑1] (Wong, B., Slivkins, A., and E. Sirer, “Meridian: A lightweight network location service without virtual coordinates,” .), [Madhyastha‑1] (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‑1] (Aggarwal, V., Feldmann, A., and C. Scheidler, “Can ISPs and P2P systems co-operate for improved performance?,” .), [Xie‑1] (Xie, H., Krishnamurthy, A., Silberschatz, A., and Y. Yang, “P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers,” .), [I‑D.saucez‑idips] (Saucez, D., Donnet, B., and O. Bonaventure, “IDIPS : ISP-Driven Informed Path Selection,” February 2008.). 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‑1] (Seetharaman, S., Hilt, V., Hofmann, M., and M. Ammar, “Preemptive Strategies to Improve Routing Performance of Native and Overlay Layers,” .).

2.  Survey of Existing Literature

Gummadi et al. [Gummadi‑1] (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 hypercubes, tree structures and butterfly networks).

Regardless of the geometrical properties of the DHTs involved, interactions between application-layer overlays and the underlying networks are a rich area of investigation. The available literature in this field can be taxonomixed in two categories: using application-level techniques to estimate topology and using an infrastructure of some sort.

2.1.  Application-Level Topology Estimation

In order to provide P2P overlays with topology information essential for optimizing node selection, different systems have been proposed.

Estimating network topology information on the application level has been an area of active research. Early work on network distance estimation based on clustering by Francis et al. [Francis‑1] (Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and L. Zhang, “IDMaps: A global Internet host distance estimation service,” .) was followed by the introduction of network coordinate systems such as GNP by Ng et al. [Ng‑1] (Ng, T. and H. Zhang, “Predicting internet network distance with coordinates-based approaches,” .). Network coordinate systems embed the network topology in a low-dimensional coordinate space and enable network distance estimations based on vector distance. Vivaldi [Dabek‑1] (Dabek, F., Cox, R., Kaashoek, F., and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” .) and PIC [Costa‑1] (Costa, M., Castro, M., Rowstron, A., and P. Key, “PIC: Practical Internet coordinates for distance estimation,” .) propose distributed network coordinate systems that do not need landmarks for coordinate calculation. Vivaldi is now being used in the popular P2P application Azureus [Azureus] (, “Azureus BitTorrent Client,” .) and studies indicate that it scales well to very large networks [Ledlie‑1] (Ledlie, J., Gardner, P., and M. Seltzer, “Network Coordinates in the Wild,” .).

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. For example, it has proved to be difficult to embed the triangular inequalities found in Internet path distances [Wang‑07] (Wang, G., Zhang, B., and T. Ng, “Towards Network Triangle Inequality Violation Aware Distributed Systems,” .). Thus, Meridian [Wong‑1] (Wong, B., Slivkins, A., and E. Sirer, “Meridian: A lightweight network location service without virtual coordinates,” .) abandons the generality of network coordinate systems and provides specific distance evaluation services. The Ono project [Ono] (, “Northwestern University Ono Project,” .) take a different approach and uses network measurements from content-distribution network (CDN) like Akamai to find nearby peers [Su06] (Su, A., Choffnes, D., Kuzmanovic, A., and F. Bustamante, “Drafting behind Akamai (travelocity-based detouring),” .). Used as a plugin to the Azureus BitTorrent client, Ono provides 31% average download rate improvement.

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. However, for many P2P applications throughput is often more important than latency. iPlane [Madhyastha‑1] (Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., Anderson, T., Krishnamurthy, A., and A. Venkataramani., “iPlane: an information plane for distributed services,” .) aims at creating an atlas of the Internet using measurements that contains information about latency, bandwidth, capacity and loss rates.

To determine features of the topology, network measurement tools, e.g., based on packet dispersion techniques (packet pairs and packet trains) as described by Dovrolis et al. in [DRM01] (Dovrolis, C., Ramanathan, P., and D. Moore, “What do packet dispersion techniques measure?,” .) can be used. Moreover, methods of active network probing or passive traffic monitoring can also generate network statistics relating indirectly to performance attributes that cannot be directly measured but need to be inferred. An extensive study of such techniques that are summarized under the notion of network tomography has been provided by Coates et al. [CHNY02] (Coates, M., Hero, A., Nowak, R., and B. Yu, “Internet Tomography,” .).

The Joost Video-on-Demand Service uses P2P technology to distribute streaming video at a bit rate of about 600 kbit/s and higher. In their experimental analysis, Lei et al. [LEI‑07] (Lei, J., Shi, L., and X. Fu, “An experimental analysis of Joost peer-topeer VoD service,” .) conclude that the system is heavily based on a media server infrastructure -- in particular for channels with lower popularity -- and that a geographical distance based on address prefix analysis is considered during the server selection. They show that the peer selection process today is unlikely based on topology locality. Instead the peer's capacity influences the the creation of the peer lists similar to BitTorrent: low capacity peers connect mostly with other low capacity peers to avoid wasting the high capacity peers bandwidth.

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‑1] (Xie, H., Krishnamurthy, A., Silberschatz, A., and Y. Yang, “P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers,” .) have been adopted by the DCIA P4P working group [P4P‑1] (, “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 with field tests with real users. Initial simulations and PlanetLab experiments results [P4P‑1] (, “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 in field tests conducted with a modified version of the software used by the Pando content delivery network [OpenP4P‑1] (, “OpenP4P Web Page,” .) show improvements in download rate by 23\% and a significant drop in data delivery average hop count (from 5.5 to 0.89) in certain scenarios.

2.2.2.  Oracle-based ISP-P2P Collaboration

The mechanism is fairly simple: a P2P user sends the list of potential peers to the oracle hosted by its ISP, which ranks such a list based on its local policies. For instance, the ISP can prefer peers within its network, to prevent traffic from leaving its network; further, it can pick higher bandwidth links, or peers that are geographically closer. Once the application has obtained an ordered list, it is up to it to establish connections with a number of peers it can individually choose, but it has enough information to perform an optimal choice.

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 IDIPS solution [I‑D.saucez‑idips] (Saucez, D., Donnet, B., and O. Bonaventure, “IDIPS : ISP-Driven Informed Path Selection,” February 2008.) was presented during the SHIM6 session of the 71st IETF meeting. It is essentially a modified version of the solution described in section Section 2.2.2 (Oracle-based ISP-P2P Collaboration), extended to accept lists of source addresses other than destinations in order to function also as a back end for protocols like SHIM6 and LISP (which aim at optimizing path selection at the network layer). An evaluation performed on IDIPS shows that costs for both providing and accessing the service are negligible [Saucez‑2] (Saucez, D., Donnet, B., and O. Bonaventure, “Implementation and Preliminary Evaluation of an ISP-Driven Informed Path Selection,” .).

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‑07] (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 [PFTK98] (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, available bandwidth.

Some of the topology estimation techniques used by peer-to-peer 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 peering 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 VoIP application chooses a relay node in cases where two peers are behind NATs and cannot connect directly. Ren et al. [REN‑06] (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 (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 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 features 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‑1] (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.  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 in account beyond what is already discussed in each paper surveyed.

5. Informative References

Authors' Addresses

Full Copyright Statement

Copyright © The IETF Trust (2008).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an “AS IS” basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.