Internet DRAFT - draft-hilt-alto-survey

draft-hilt-alto-survey






Network Working Group                                            V. Hilt
Internet-Draft                                                  I. Rimac
Intended status: Informational                                  M. Tomsu
Expires: January 4, 2009                                      V. Gurbani
                                               Bell Labs, Alcatel-Lucent
                                                              E. Marocco
                                                          Telecom Italia
                                                            July 3, 2008


   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 4, 2009.

Copyright Notice

   Copyright (C) The IETF Trust (2008).

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



Hilt, et al.             Expires January 4, 2009                [Page 1]

Internet-Draft                 ALTO Survey                     July 2008


   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 . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Survey of Existing Literature  . . . . . . . . . . . . . . . .  4
     2.1.  Application-Level Topology Estimation  . . . . . . . . . .  4
     2.2.  Topology Estimation through Layer Cooperation  . . . . . .  5
       2.2.1.  P4P Architecture . . . . . . . . . . . . . . . . . . .  5
       2.2.2.  Oracle-based ISP-P2P Collaboration . . . . . . . . . .  6
       2.2.3.  ISP-Driven Informed Path Selection (IDIPS) Service . .  7
   3.  Application-Level Topology Estimation and the ALTO Problem . .  7
   4.  Security Considerations  . . . . . . . . . . . . . . . . . . .  8
   5.  Informative References . . . . . . . . . . . . . . . . . . . .  8
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
   Intellectual Property and Copyright Statements . . . . . . . . . . 12




























Hilt, et al.             Expires January 4, 2009                [Page 2]

Internet-Draft                 ALTO Survey                     July 2008


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], [Karag], [Light], [Linux], [Parker],
   [Glasner].

   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].
   This naturally leads to the Application-Layer Traffic Optimization
   (ALTO) problem [I-D.marocco-alto-problem-statement]: 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], [Ng-1], [Dabek-1], [Costa-1], [Wong-1], [Madhyastha-1],
   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].  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], [Xie-1], [I-D.saucez-idips].  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].




Hilt, et al.             Expires January 4, 2009                [Page 3]

Internet-Draft                 ALTO Survey                     July 2008


2.  Survey of Existing Literature

   Gummadi et al.  [Gummadi-1] 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] was
   followed by the introduction of network coordinate systems such as
   GNP by Ng et al.  [Ng-1].  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] and PIC [Costa-1] 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] and studies indicate that it scales well to very large
   networks [Ledlie-1].

   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].  Thus,
   Meridian [Wong-1] abandons the generality of network coordinate
   systems and provides specific distance evaluation services.  The Ono
   project [Ono] take a different approach and uses network measurements
   from content-distribution network (CDN) like Akamai to find nearby
   peers [Su06].  Used as a plugin to the Azureus BitTorrent client, Ono



Hilt, et al.             Expires January 4, 2009                [Page 4]

Internet-Draft                 ALTO Survey                     July 2008


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

   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] 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] have been adopted by
   the DCIA P4P working group [P4P-1], an open group established by



Hilt, et al.             Expires January 4, 2009                [Page 5]

Internet-Draft                 ALTO Survey                     July 2008


   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] 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] 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



Hilt, et al.             Expires January 4, 2009                [Page 6]

Internet-Draft                 ALTO Survey                     July 2008


   make their decisions.

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

   The IDIPS solution [I-D.saucez-idips] 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, 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].


3.  Application-Level Topology Estimation and the ALTO Problem

   The application-level techniques described in Section Section 2.1
   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].  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].  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



Hilt, et al.             Expires January 4, 2009                [Page 7]

Internet-Draft                 ALTO Survey                     July 2008


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

   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

   [Aggarwal-1]
              Aggarwal, V., Feldmann, A., and C. Scheidler, "Can ISPs
              and P2P systems co-operate for improved performance?".

   [Azureus]  "Azureus BitTorrent Client", <http://www.azureus.com/>.

   [CHNY02]   Coates, M., Hero, A., Nowak, R., and B. Yu, "Internet
              Tomography".




Hilt, et al.             Expires January 4, 2009                [Page 8]

Internet-Draft                 ALTO Survey                     July 2008


   [Costa-1]  Costa, M., Castro, M., Rowstron, A., and P. Key, "PIC:
              Practical Internet coordinates for distance estimation".

   [DRM01]    Dovrolis, C., Ramanathan, P., and D. Moore, "What do
              packet dispersion techniques measure?".

   [Dabek-1]  Dabek, F., Cox, R., Kaashoek, F., and R. Morris, "Vivaldi:
              A Decentralized Network Coordinate System".

   [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".

   [Glasner]  Glasner, J., "P2P fuels global bandwidth binge",
              <http://www.wired.com/techbiz/media/news/2005/04/67202>.

   [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".

   [I-D.marocco-alto-problem-statement]
              Marocco, E. and V. Gurbani, "Application-Layer Traffic
              Optimization (ALTO) Problem Statement",
              draft-marocco-alto-problem-statement-00 (work in
              progress), April 2008.

   [I-D.saucez-idips]
              Saucez, D., Donnet, B., and O. Bonaventure, "IDIPS : ISP-
              Driven Informed Path Selection", draft-saucez-idips-00
              (work in progress), February 2008.

   [Karag]    Karagiannis, T., Broido, A., Brownlee, N., Claffy, K., and
              M. Faloutsos, "Is P2P dying or just hiding?".

   [LEI-07]   Lei, J., Shi, L., and X. Fu, "An experimental analysis of
              Joost peer-topeer VoD service".

   [Ledlie-1]
              Ledlie, J., Gardner, P., and M. Seltzer, "Network
              Coordinates in the Wild".

   [Light]    Lightreading, "Controlling P2P traffic", <http://
              www.lightreading.com/document.asp?site=lightreading&doc
              id=44435&page number=3>.

   [Linux]    linuxReviews.org, "Peer to peer network traffic may



Hilt, et al.             Expires January 4, 2009                [Page 9]

Internet-Draft                 ALTO Survey                     July 2008


              account for up to 85% of Interneta??s bandwidth usage",
              <http://linuxreviews.org/news/2004/11/05 p2p/>.

   [Madhyastha-1]
              Madhyastha, H., Isdal, T., Piatek, M., Dixon, C.,
              Anderson, T., Krishnamurthy, A., and A. Venkataramani.,
              "iPlane: an information plane for distributed services".

   [Meeker]   Meeker, M. and D. Joseph, "The State of the Internet, Part
              3", <http://www.morganstanley.com/institutional/
              techresearch/pdfs/ Webtwopto2006.pdf>.

   [Ng-1]     Ng, T. and H. Zhang, "Predicting internet network distance
              with coordinates-based approaches".

   [Ono]      "Northwestern University Ono Project",
              <http://www.aqualab.cs.northwestern.edu/projects/
              Ono.html>.

   [OpenP4P-1]
              "OpenP4P Web Page", <http://openp4p.net/front/fieldtests>.

   [P4P-1]    "DCIA P4P Working group",
              <http://www.dcia.info/activities/#P4P.>.

   [PFTK98]   Padhye, J., Firoiu, V., Towsley, D., and J. Kurose,
              "Modeling TCP throughput: A simple model and its empirical
              validation".

   [Parker]   Parker, A., "The true picture of peer-to-peer
              filesharing", <http://www.cachelogic.com>.

   [REN-06]   Ren, S., Guo, L., and X. Zhang, "ASAP: An AS-aware peer-
              relay protocol for high quality VoIP".

   [Saucez-2]
              Saucez, D., Donnet, B., and O. Bonaventure,
              "Implementation and Preliminary Evaluation of an ISP-
              Driven Informed Path Selection".

   [Seetharaman-1]
              Seetharaman, S., Hilt, V., Hofmann, M., and M. Ammar,
              "Preemptive Strategies to Improve Routing Performance of
              Native and Overlay Layers".

   [Su06]     Su, A., Choffnes, D., Kuzmanovic, A., and F. Bustamante,
              "Drafting behind Akamai (travelocity-based detouring)".




Hilt, et al.             Expires January 4, 2009               [Page 10]

Internet-Draft                 ALTO Survey                     July 2008


   [Wang-07]  Wang, G., Zhang, B., and T. Ng, "Towards Network Triangle
              Inequality Violation Aware Distributed Systems".

   [Wong-1]   Wong, B., Slivkins, A., and E. Sirer, "Meridian: A
              lightweight network location service without virtual
              coordinates".

   [Xie-1]    Xie, H., Krishnamurthy, A., Silberschatz, A., and Y. Yang,
              "P4P: Explicit Communications for Cooperative Control
              Between P2P and Network Providers",
              <http://www.dcia.info/documents/P4P Overview.pdf.>.


Authors' Addresses

   Volker Hilt
   Bell Labs, Alcatel-Lucent

   Email: volkerh@bell-labs.com


   Ivica Rimac
   Bell Labs, Alcatel-Lucent

   Email: rimac@bell-labs.com


   Marco Tomsu
   Bell Labs, Alcatel-Lucent

   Email: marco.tomsu@alcatel-lucent.com


   Vijay K. Gurbani
   Bell Labs, Alcatel-Lucent

   Email: vkg@bell-labs.com


   Enrico Marocco
   Telecom Italia

   Email: enrico.marocco@telecomitalia.it








Hilt, et al.             Expires January 4, 2009               [Page 11]

Internet-Draft                 ALTO Survey                     July 2008


Full Copyright Statement

   Copyright (C) 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.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Hilt, et al.             Expires January 4, 2009               [Page 12]