Internet Engineering Task Force                                  H. Asai
Internet-Draft                                                  H. Esaki
Intended status: Informational                   The University of Tokyo
Expires: December 5, 2012                                      T. Momose
                                                           Cisco Systems
                                                            June 3, 2012


 Considerations on the AS-Level Application-Layer Traffic Optimization
                   draft-asai-cross-domain-overlay-04

Abstract

   Overlay routing technologies (a.k.a. peer-to-peer technologies) have
   been introduced to various distributed systems, such as content
   delivery networks and live media streaming systems.  However, these
   systems cannot always utilize optimal network resources from the
   viewpoint of layer 3 network providers and operators of layer 3
   network providers have difficulties in controlling and optimizing the
   traffic of these systems because these systems construct their own
   networks (i.e., overlay networks) over the layer 3 network without
   taking into account layer 3 network's routing policies.  The ALTO
   Working Group has worked on application-layer traffic optimization to
   fill the gaps in routing policies between the layer 3 network and
   overlay networks by providing the underlay network topology and cost
   information to applications that build overlay networks.  However,
   since ASes are operated under different policies and cost metrics for
   application-layer traffic optimization are assumed to be autonomously
   configured by each AS, there are considerations in applying
   application-layer traffic optimization techniques to cross-domain
   (inter-AS) traffic.  This document summarizes general problems with
   cross-domain traffic of overlay networks and considerations on the
   AS-level application-layer traffic optimization from the viewpoint of
   inter-AS economics.  This document also discusses the conceivable
   approaches to solve the problems and considerations.

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



Asai, et al.            Expires December 5, 2012                [Page 1]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


   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 5, 2012.

Copyright Notice

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
































Asai, et al.            Expires December 5, 2012                [Page 2]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  4
       1.1.1.  AS Relationships . . . . . . . . . . . . . . . . . . .  5
       1.1.2.  Transit  . . . . . . . . . . . . . . . . . . . . . . .  5
       1.1.3.  Peering  . . . . . . . . . . . . . . . . . . . . . . .  5
       1.1.4.  Cross-Domain Links and Traffic . . . . . . . . . . . .  5
       1.1.5.  Overlay Network  . . . . . . . . . . . . . . . . . . .  5
     1.2.  Requirements Language  . . . . . . . . . . . . . . . . . .  5
   2.  Cross-Domain Traffic Optimization Problems and
       Considerations . . . . . . . . . . . . . . . . . . . . . . . .  6
     2.1.  General Problems with Cross-Domain Traffic of Overlay
           Networks . . . . . . . . . . . . . . . . . . . . . . . . .  6
     2.2.  Considerations on AS-Level Application-Layer Traffic
           Optimization . . . . . . . . . . . . . . . . . . . . . . .  8
       2.2.1.  Uneven policy configuration  . . . . . . . . . . . . .  9
       2.2.2.  Asymmetric economic policies . . . . . . . . . . . . . 10
       2.2.3.  Uncertain ingress routes . . . . . . . . . . . . . . . 11
     2.3.  Summary of the Problems and Considerations . . . . . . . . 13
   3.  Conceivable Solution Approaches and Discussion . . . . . . . . 14
     3.1.  A1. ALTO servers without interconnection at local ASes . . 14
     3.2.  A2. ALTO servers without interconnection at local and
           remote ASes  . . . . . . . . . . . . . . . . . . . . . . . 15
     3.3.  A3. ALTO servers with mesh interconnection . . . . . . . . 16
     3.4.  A4. ALTO servers with mesh interconnection and reverse
           path probes  . . . . . . . . . . . . . . . . . . . . . . . 17
     3.5.  A5. ALTO servers with hop-by-hop interconnection by
           using a path vector algorithm  . . . . . . . . . . . . . . 18
     3.6.  Summary of the Conceivable Solution Approaches . . . . . . 19
     3.7.  Discussion on uneven policy configuration  . . . . . . . . 19
   4.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 21
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . . 22
   6.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23
   7.  Informative References . . . . . . . . . . . . . . . . . . . . 24
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26















Asai, et al.            Expires December 5, 2012                [Page 3]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


1.  Introduction

   Many distributed systems, such as content delivery networks (CDNs)
   and live media streaming systems, have introduced application-layer
   overlay routing as represented by peer-to-peer technologies for their
   communication scheme to avoid excessive server load and to achieve
   effective and high-quality communication (e.g., high throughput,
   fault tolerance).  Today, the traffic generated by these applications
   using application-layer overlay routing becomes a significant amount
   of the Internet traffic [RFC5693].  Since these applications
   construct their own network topology (a.k.a. overlay network) over
   the Internet, generally without taking into account the layer 3
   network topology, these applications frequently utilize a larger
   amount of network resources than layer 3 network providers expect.
   Moreover, they may utilize a detoured path that is disallowed or
   unexpected by layer 3 network providers [Ho09].

   The ALTO Working Group has worked on application-layer traffic
   optimization to fill the gaps between the layer 3 network and
   applications by providing the underlay network topology and cost
   information to these applications for their overlay network
   construction.  However, there exist considerations on inter-AS policy
   conflicts when we deploy the AS-level application-layer traffic
   optimization because ASes are operated under different policies and
   cost metrics are assumed to be autonomously configured by each AS.

   This document summarizes general problems with cross-domain
   (inter-AS) traffic generated by overlay networks and considerations
   on the AS-level application-layer traffic optimization from the
   viewpoint of inter-AS economics, which are not discussed
   in [RFC5693].  The main concerns on the AS-level application-layer
   traffic optimization are categorized to three groups; 1) uneven
   policy configuration between distinct layer 3 network domains (i.e.,
   ASes), 2) asymmetric economic policies on transit links, and 3)
   uncertain ingress routes in BGP routing.  The underlying problem
   inducing these concerns is that the detailed economic policies
   between interconnected ASes are non-disclosure information due to
   commercial contracts although these policies are important metrics
   for inter-AS traffic optimization.  This document also discusses the
   conceivable approaches to solve the problems and considerations.

1.1.  Terminology

   We use the following terms in this document.







Asai, et al.            Expires December 5, 2012                [Page 4]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


1.1.1.  AS Relationships

   AS relationships represent commercial relationships between
   interconnected ASes.  AS relationships are categorized into two major
   types: transit and peering.  There are typical inter-AS routing
   policies by each type of AS relationships [Wang03].

1.1.2.  Transit

   Transit is a type of AS relationships, in which a customer AS
   purchases Internet access from its transit provider(s) over transit
   link(s) by paying some amount of money according to the actual
   bandwidth usage.  The Transit relationship is also called provider-
   customer relationship.

1.1.3.  Peering

   Peering is a type of AS relationships, in which two peering ASes are
   equal.  Traffic exchanged over peering links is free of charge.

1.1.4.  Cross-Domain Links and Traffic

   Domains correspond to ASes in this document.  Cross-domain links and
   traffic denote inter-AS links and traffic, respectively.

1.1.5.  Overlay Network

   Overlay networks are constructed by application-layer nodes such as
   peer-to-peer application nodes over the layer 3 network (i.e., IP
   network) that is operated by network providers.  The topology and
   routing of an overlay network are controlled by applications that
   build the overlay network but not by the layer 3 network providers.

1.2.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].













Asai, et al.            Expires December 5, 2012                [Page 5]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


2.  Cross-Domain Traffic Optimization Problems and Considerations

   This section discusses general problems with cross-domain traffic of
   overlay networks and considerations on the AS-level application-layer
   traffic optimization in terms of cross-domain traffic and its
   economics.  First, we point out the general problems that the overlay
   networks do not take into account the layer 3 network economics and
   routing policies, and consequently, they cannot always utilize
   optimal network resources from the viewpoint of layer 3 network
   providers.  Then, we present the considerations on the AS-level
   application-layer traffic optimization that are not discussed well
   in [RFC5693].  Since ASes are operated under different policies and
   cost metrics are assumed to be autonomously configured by each AS,
   the method for intra-domain optimization cannot be directly used and
   cross-domain concerns, such as uneven policy configuration between
   distinct ASes, asymmetric policies on transit links, and asymmetric
   underlay paths, must be solved to achieve the AS-level application-
   layer traffic optimization.

2.1.  General Problems with Cross-Domain Traffic of Overlay Networks

   The Internet consists of thousands of ASes operated by distinct
   network providers such as commercial ISPs, companies and
   universities.  Each AS generally connects with multiple ASes, and
   there are distinct charging policies for each inter-AS link.  These
   charging policies are roughly categorized into two major types of
   relationships; transit (with charge) and peering (without any
   charge).  From the economic viewpoint, network providers want to
   reduce the traffic volume exchanged with transit providers as much as
   possible, and consequently, they manage BGP routing policies as
   explained in [Wang03].  Thus, the layer 3 paths are determined by
   network providers as intended.

   However, overlay networks are not sometimes aware of these routing
   policies and generate more expensive cross-domain traffic.  On the
   other hand, network providers cannot optimize the cross-domain
   traffic generated by applications on overlay networks.  This is
   because the traffic is controlled by a set of application-specific
   algorithms that determines the overlay network topology and traffic
   delivery paths, such as peer, neighbor, or path selection algorithms.











Asai, et al.            Expires December 5, 2012                [Page 6]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


                    +------+ provider
                    | AS 1 |----------------------+
           provider +------+                      | transit
                       | transit                  |
                       v                          v
           customer +------+ peering +------+  +------+ customer
                    | AS 2 |<------->| AS 3 |  | AS 4 |
                    +------+         +------+  +------+

   AS 2 purchases Internet access from AS 1 via a transit link.  On the
   contrary, the link between AS 2 and AS 3 is peering, which is a lower
          cost link from the viewpoint of AS 2 network operators.

      Figure 1: An example of AS-level topology with AS relationships

   We show an example of the problem with the unawareness of the layer 3
   network economics and cross-domain traffic generated by overlay
   networks.  An example of interconnections of ASes and their
   relationships is shown in Figure 1.  Suppose remote nodes of a peer-
   to-peer content delivery network that provide a certain content file
   exist in both AS 3 and AS 4, and a local node that downloads the file
   in AS 2 is to retrieve the file from one of these remote nodes, a
   remote node in AS 3 should be selected to reduce transit charge for
   both ASes of the local node and the remote node, but today's peer-to-
   peer content delivery networks that are unaware of AS relationships
   often select other remote nodes.

   Thus, overlay networks cannot always utilize optimal network
   resources but high-cost ones (i.e., transit links from/to transit
   providers) from the economic viewpoint of network providers.
   Moreover, especially on peer-to-peer overlay networks, the
   connectivity of most of end-point nodes (i.e., peers) is provided by
   residential ISPs, and most of residential ISPs are not transit
   providers but transit customers, and consequently, it is
   significantly important to control the transit traffic not to
   increase their charge to their providers though these kinds of
   application-layer traffic are hardly controlled by network providers.
   [RFC5693] also claims this problem with cross-domain traffic in terms
   of transit cost as well as congestion in intra-domain networks.












Asai, et al.            Expires December 5, 2012                [Page 7]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


                 +------+ provider
                 | AS 1 |-----------------------------+
        provider +------+                             | transit
                    | transit                         |
                    v                                 v
        customer +------+ peering +------+ peering +------+ customer
                 | AS 2 |<------->| AS 3 |<------->| AS 4 |
                 +------+         +------+         +------+
                   Node <=========> Node <=========> Node
                               detoured path

   According to the typical BGP routing policies, the path from AS 2 to
     AS 4 is to be AS 2->AS 1->AS 4.  The path AS 2->AS 3->AS 4 is not
   usually allowed because AS 3 relays traffic from AS 2 to AS 4 without
                    any charge if this path is allowed.

      Figure 2: An example of AS-level detouring by overlay networks

   Another problem with overlay networks is that overlay networks may
   create a detoured path that is disallowed or unexpected by layer 3
   network providers [Ho09].  For example, in Figure 2, the traffic from
   AS 2 to AS 4 can pass through AS 3 if a node of an overlay network
   exists in AS 3 and relays the traffic, but this is usually disallowed
   by the routing policy of AS 3 to avoid free-riding.

   In summary, overlay networks have following problems from the cross-
   domain economic viewpoint of network providers.

   o  Overlay networks usually do not take into account the layer 3
      network economics to construct their network topology and to
      exchange traffic between end-point nodes.  Therefore, they cannot
      always utilize optimal cross-domain network resources from the
      economic viewpoint of network providers.

   o  Overlay networks may enable AS-level traffic detouring that is
      disallowed by the layer 3 network routing policies.  This problem
      possibly increases transit expenses or induces free-riding.

2.2.  Considerations on AS-Level Application-Layer Traffic Optimization

   The ALTO Working Group has worked on application-layer traffic
   optimization to fill the gaps in routing policies between the layer 3
   network and overlay networks.  It has worked on solving the problems
   stated in [RFC5693], but [RFC5693] misses some considerations on the
   AS-level (cross-domain) application-layer traffic optimization.  We
   summarize the missing considerations as follows.





Asai, et al.            Expires December 5, 2012                [Page 8]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


   o  Uneven policy configuration between distinct administrative
      domains: ASes hardly cooperate with each other in fairly
      regulating uneven policies of distinct ASes because each AS
      operates its network under its own policy and inter-AS policies
      are complicated to achieve total optimization.

   o  Asymmetric economic policies on transit links: It is difficult to
      regulate the asymmetric economic policies on transit links because
      transit customers' policies run counter to transit providers;
      i.e., customers want to reduce the traffic exchanged with their
      providers to reduce their expense though providers want to
      increase the traffic exchanged with their customers to increase
      their income.

   o  Uncertain ingress routes in BGP routing: In addition to the
      asymmetric economic policies on transit links, the policy-based
      routing of BGP often creates asymmetric paths.  Local ASes hold
      their egress routes (i.e., next hop AS for a remote end-point
      node), but they do not know ingress routes (i.e., previous hop AS
      from a remote end-point node).  Therefore, it is difficult to
      configure ingress cost for remote end-point nodes/networks because
      the layer 3 network providers do not have the ingress routes to
      determine which AS becomes the previous hop for the remote end-
      point nodes/networks.

   The details of these considerations are described in the following
   sections.

2.2.1.  Uneven policy configuration

   The ALTO Working Group has proposed a protocol to distribute end-to-
   end network cost between peers to
   applications [I-D.ietf-alto-protocol].  This protocol does not intend
   to define the cost computation algorithm, but it assumes that the
   cost is computed by network providers.  Two oracle-based cost
   computation algorithms, [Aggarwal07] and [Xie08], have been proposed
   and evaluated in the research area.  [Aggarwal07] computes the AS-
   level cost according to AS hop count between two end-point nodes.
   So, it ignores the information on AS relationships (i.e., transit
   cost).  [Xie08] computes the AS-level cost according to the
   configured parameters (e.g., `local preference' in BGP) in routers.
   This takes into account AS relationships.  However, there is a
   problem with this algorithm when it is applied to the real Internet.
   Charging policies for exchanged inter-AS traffic volume are so
   complicated that different ASes hardly cooperate with each other in
   computing and fairly balancing cost.  Even in the BGP routing managed
   by network providers, the hot potato problem stated in [RFC4277]
   shows the difficulty in regulating policies of distinct ASes.



Asai, et al.            Expires December 5, 2012                [Page 9]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


                    +------+ provider
                    | AS 1 |----------------------+
           provider +------+ 3                    | transit
                     5 | transit (1$/Mbps)        |  (2$/Mbps)
                    30 v                          v 10
           customer +------+                   +------+ customer
                    | AS 2 |                   | AS 3 |
                    +------+                   +------+

    Each number represents egress cost.  Transit charge on each transit
                  link is noted in a set of parentheses.

             Figure 3: An example of uneven cost configuration

   For example, suppose egress cost of each inter-AS link is configured
   autonomously (i.e., each AS sets cost according to its own policies)
   as shown in Figure 3, then the cost of the path from AS 2 to AS 1
   becomes larger than that of the path from AS 3 to AS 1 though the
   path from AS 2 to AS 1 seems to be a cheaper link than the other.
   Thus, oracle-based approaches are exposed to a fairness or evenness
   issue among multiple autonomous domains.

   In summary, inter-AS policies are so complex that ASes cooperate with
   each other in fairly regulating policies of distinct ASes in terms of
   cross-domain cost configuration.

2.2.2.  Asymmetric economic policies

   There is a difficulty in regulating the asymmetric economic policies
   on inter-AS links, especially between transit customers and
   providers.  One of the causes of this difficulty is same as that of
   the issue on the uneven policy configuration; i.e., because each AS
   configures its own desired policy.  Another cause of this difficulty
   is that the policies on the transit links are not symmetric.  So, one
   party's policy does not match the other's.  The same asymmetric
   nature is also found in the BGP routing, but the policy regulation on
   transit links becomes more complex in the overlay routing than the
   BGP routing.  This is because overlay network nodes that have the
   same functionality or contents possibly exist in multiple ASes while
   the functionality (i.e., end-to-end connectivity to the destination)
   of the BGP routing is mapped to a single AS.  The BGP path-vector
   routing is performed under the control of the layer 3 network
   providers by route import and export policies, and consequently, the
   computed paths in the BGP routing are based on the benefit principle.
   However, the overlay routing might destroy the control and the
   principle.





Asai, et al.            Expires December 5, 2012               [Page 10]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


                         +------+
                         | AS 1 |     Remote node
                provider +------+       ^
                          5 | transit   | Good for AS 1
                         30 v           | Not good for AS 2
                customer +------+       v
                         | AS 2 |     Local node
                provider +------+       ^
                          5 | transit   | Good for AS 2
                         30 v           | Not good for AS 3
                customer +------+       v
                         | AS 3 |     Remote node
                         +------+

   Each number in this figure represents cost.  Note that cost for each
   type of AS relationships is already simplified and regulated here; 5
      for provider to customer and 30 for customer to provider.  This
    asymmetric cost regulation follows the typical import policy in the
    BGP routing (i.e., local preference) although it is quite difficult
             to achieve this regulation between distinct ASes.

           Figure 4: An example of asymmetric cost configuration

   For example, suppose the cost of each inter-AS link configured as
   shown in Figure 4 is egress cost, then the end-to-end cost from AS 1
   to AS 2 becomes smaller than that from AS 3 to AS 2.  On the other
   hand, suppose the cost of each inter-AS link configured as shown in
   Figure 4 is ingress cost, then the end-to-end cost from AS 1 to AS 2
   becomes larger than that from AS 3 to AS 2.  This means that the path
   from AS 3 to AS 2 is preferred than the other from the viewpoint of
   AS 2 but the path from AS 1 to AS 2 is preferred than the other from
   the viewpoint of AS 1 and AS 3.  Unlike the BGP routing, overlay
   networks may have the same functionality or contents at their nodes
   both in AS 1 and AS 3, and consequently, it is required to consider
   the conflicts of asymmetric economic policies on transit links
   between multiple ASes.

   In summary, the existence of identical functionality at multiple ASes
   in overlay networks raises the problem with asymmetric economic
   policies on transit links.

2.2.3.  Uncertain ingress routes

   In case that cost between end-point nodes or networks is configured
   by each AS, underlay paths must also be considered to compute the
   cost.  Since local ASes hold their egress routes (i.e., next hop AS
   for a remote end-point node/network), egress cost can be configured
   by looking at the cost of the link to the next hop AS.  However,



Asai, et al.            Expires December 5, 2012               [Page 11]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


   ingress cost is difficult to be computed because local ASes do not
   have ingress routes to determine which AS becomes the previous hop
   for a remote end-point node/network.  Note that the ingress routes
   are difficult to be expected from the egress routes because the
   policy-based routing of BGP often creates asymmetric paths.  BGP
   operators usually work on traffic engineering with reactive methods
   for the ingress traffic.

                       provider +------+ provider
                         +------| AS 1 |------------------+
                 transit |      +------+                  | transit
                         v                                |
             customer +------+ peering +------+           |
                      | AS 2 |<------->| AS 3 |           |
                      +------+         +------+ provider  |
          Routing table @AS 2     transit |               |
         +--------------------+           v               |
         | Destination | Next |        +------+ customer  |
         +--------------------+        | AS 4 |           |
         | AS 1        | AS 1 |        +------+ provider  |
         | AS 3, 4, 5  | AS 3 |   transit |               |
         +--------------------+           |  +------------+
                                          v  v
                 Routing table @AS 5    +------+ customer
                +--------------------+  | AS 5 |
                | Destination | Next |  +------+
                +--------------------+
                | AS 1, 2     | AS 1 |
                | AS 3, 4     | AS 4 |
                +--------------------+

   The underlay path between AS 2 and AS 5 is asymmetric.  From AS 2 to
   AS 5, the path goes through AS 3 and AS 4 as the routes from peering
     are generally preferred to those from transit providers.  On the
     other hand, from AS 5 to AS 2, the path goes through AS 1 as the
   shortest paths are generally selected as the best when both exits are
     transit.  Routing tables at AS 2 and AS 5 are also represented in
       this figure to point out the uncertainness of ingress routes.

     Figure 5: An example of uncertain ingress routes with asymmetric
                         paths in the BGP routing

   For example, the BGP routing often creates asymmetric paths as shown
   in Figure 5.  Suppose that AS 2 is the local AS and AS 5 is one of
   the remote ASes and the network provider of AS 2 tries to configure
   ingress cost from AS 5, AS 2 holds an egress route to AS 5 that goes
   to AS 3 over a peering link in its routing table but AS 2 does not
   have any ingress routes, and consequently, AS 2 cannot determine



Asai, et al.            Expires December 5, 2012               [Page 12]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


   which AS (AS 1 or AS 3) is the previous hop from AS 5 because the
   reverse path is determined by routing tables of other ASes.  In this
   figure, the path between AS 2 and AS 5 is asymmetric, and
   consequently, the next hop AS to AS 5 (AS 3) becomes different from
   the previous hop AS to AS 5 (AS 1).

2.3.  Summary of the Problems and Considerations

   This section summarizes the general problems with cross-domain
   traffic of overlay networks pointed out in Section 2.1 and
   considerations on the AS-level application-layer traffic optimization
   described in Section 2.2.  These problems and considerations of
   overlay networks towards the AS-level application-layer traffic
   optimization are summarized into the following five categories.

   o  C1.  AS relationships unawareness of overlay networks

   o  C2.  AS-level detouring by overlay networks

   o  C3.  Uneven policy configuration of distinct ASes

   o  C4.  Asymmetric economic policy on transit links

   o  C5.  Uncertain ingress routes in determining ingress cost



























Asai, et al.            Expires December 5, 2012               [Page 13]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


3.  Conceivable Solution Approaches and Discussion

   This section discusses the conceivable approaches to solve the
   problems and considerations, C1 to C5, summarized in Section 2.3.
   This document does not intend to define specifications and protocols,
   and consequently, this section shows the overview of each approach to
   open up further discussion.  We assume that the cost or policy
   information is provided to applications via ALTO servers defined in
   [RFC5693].  The conceivable solution approaches are listed as
   follows.

   o  A1.  ALTO servers without interconnection at local ASes

   o  A2.  ALTO servers without interconnection at local and remote ASes

   o  A3.  ALTO servers with mesh interconnection

   o  A4.  ALTO servers with mesh interconnection and reverse path
      probes

   o  A5.  ALTO servers with hop-by-hop interconnection by using a path
      vector algorithm

   The detail and points to be solved of each approach are given in the
   following sections.

3.1.  A1. ALTO servers without interconnection at local ASes

   The simplest way to take into account the AS relationships in overlay
   networks is that network providers configure cost information for
   end-point nodes in other ASes as well as end-point nodes in a local
   AS using ALTO servers.  In this approach, a local end-point node
   discovers and uses ALTO servers in the local AS. .  A local AS can
   configure egress cost for end-point nodes in other ASes to its ALTO
   servers by looking at its routing table and the inter-AS policy to
   the next hop AS, but cannot configure ingress cost because of the
   same reason as C5.  The ALTO servers in the local AS do not have
   ingress and egress cost of remote ASes.

   This approach does not require new specifications in comparison with
   intra-domain application-layer traffic optimization.  This approach
   does not completely solve any of C1-C5, but this is ``better than
   nothing'' for C1.  The inter-AS traffic from the local AS to other
   ASes can be optimized by looking at the egress cost configured in the
   local AS' ALTO servers.






Asai, et al.            Expires December 5, 2012               [Page 14]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


    +---------------------------+         +---------------------------+
    | Local AS                  |         |                 Remote AS |
    |        +-------------+   ___       ___                          |
    |        | ALTO server |  /   \     /   \                         |
    |        +-------------+ |  R  |===|  R  |                        |
    |          * egress cost  \___/     \___/                         |
    |                           |         |                           |
    | +------------+            |         |           +-------------+ |
    | | Local node |>===== Optimized for Local AS ===>| Remote node | |
    | +------------+            |         |           +-------------+ |
    +---------------------------+         +---------------------------+

       Figure 6: ALTO servers without interconnection at local ASes

   The system overview of this approach is shown in Figure 6.

3.2.  A2. ALTO servers without interconnection at local and remote ASes

   To extend the optimization to remote ASes from A1, a local end-point
   node can look up ALTO servers in remote ASes in addition to those in
   the local AS.  In this approach, a local end-point node discovers and
   uses ALTO servers both in the local and remote ASes.  Both local and
   remote ASes can configure their egress cost by the same way as A1.

   This approach requires a new specification, in comparison with intra-
   domain application-layer traffic optimization, to discover ALTO
   servers in remote ASes.  To simplify the specification and the
   discovery procedure, this discovery may be proxied by remote end-
   point nodes.  This approach does not completely solve any of C1-C5,
   but this is also ``better than nothing'' and better than A1 for C1.
   The inter-AS traffic from a remote AS to other ASes as well as the
   inter-AS traffic from the local AS to other ASes can be optimized by
   looking at the egress cost configured in both ASes' ALTO servers.


















Asai, et al.            Expires December 5, 2012               [Page 15]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


    +---------------------------+         +---------------------------+
    | Local AS                  |         |                 Remote AS |
    |        +-------------+   ___       ___      +-------------+     |
    |     +->| ALTO server |  /   \     /   \  +->| ALTO server |     |
    |     |  +-------------+ |  R  |===|  R  | |  +-------------+     |
    |     |    * egress cost  \___/     \___/  |   * egress cost      |
    |     |                     |         |    |                      |
    |     |    +-------------------------------+                      |
    |     |    |                |         |                           |
    | +------------+>===== Optimized for Local AS ===>+-------------+ |
    | | Local node |            |         |           | Remote node | |
    | +------------+<===== Optimized for Remote AS ==<+-------------+ |
    +---------------------------+         +---------------------------+

    Figure 7: ALTO servers without interconnection at local and remote
                                   ASes

   The system overview of this approach is shown in Figure 7.

3.3.  A3. ALTO servers with mesh interconnection

   A1 and A2 do not completely solve any of C1-C5.  Moreover, A2
   requires a specification to discover ALTO servers of remote ASes.
   This approach adds a specification to exchange egress cost between
   ALTO servers of local and remote ASes to provide egress cost of both
   ASes to overlay networks, instead of the discovery of ALTO servers of
   remote ASes.  The inter-AS traffic from the local AS to others and
   the inter-AS traffic from a remote AS to other ASes are optimized by
   this approach.

   One problem with this approach is scalability that the ALTO servers
   of the local AS must establish the interconnection with ALTO servers
   of remote ASes to exchange egress cost configuration.

    +---------------------------+         +---------------------------+
    | Local AS         +-- exchange egress cost --+         Remote AS |
    |                  |        |         |       |                   |
    |                  v        |         |       v                   |
    |        +-------------+   ___       ___   +-------------+        |
    |     +->| ALTO server |  /   \     /   \  | ALTO server |        |
    |     |  +-------------+ |  R  |===|  R  | +-------------+        |
    |     |    * egress cost  \___/     \___/    * egress cost        |
    |     |                     |         |                           |
    | +------------+>===== Optimized for Local AS ===>+-------------+ |
    | | Local node |            |         |           | Remote node | |
    | +------------+<===== Optimized for Remote AS ==<+-------------+ |
    +---------------------------+         +---------------------------+




Asai, et al.            Expires December 5, 2012               [Page 16]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


             Figure 8: ALTO servers with mesh interconnection

   The system overview of this approach is shown in Figure 8.

3.4.  A4. ALTO servers with mesh interconnection and reverse path probes

   Any of A1, A2, and A3 cannot achieve the optimization of ingress
   inter-AS traffic (i.e., cannot solve C5) because these approaches
   cannot determine the ingress routes.  In this approach, ALTO servers
   resolve ingress routes with reverse path probes between these
   interconnected ALTO servers.  This approach requires a specification
   to resolve the ingress routes in addition to A3's specification,
   which is to exchange egress cost between ALTO servers of local and
   remote ASes.  Thus, this approach provides four types of cost to
   applications; 1) the ingress cost of a local AS, 2) the egress cost
   of a local AS, 3) the ingress cost of a remote AS, and 4) the egress
   cost of a remote AS.  Applications can optimize the inter-AS traffic
   for both local and remote ASes using these four types of cost
   according to benefit principle; for example, attaching weight to the
   ingress and egress cost of a local AS and detaching weight on the
   ingress and egress cost of a remote AS if a end-point node in the
   remote AS is the beneficiary, vice versa.  In summary, this approach
   solves C1, C4, and C5.  Note that this approach has the same
   scalability problem as A3.

    +---------------------------+         +---------------------------+
    | Local AS         +----- exchange cost ------+         Remote AS |
    |                  |        |         |       |                   |
    |                  v  <path discovery probe>  v                   |
    |        +-------------+   ___       ___   +-------------+        |
    |     +->| ALTO server |  /   \     /   \  | ALTO server |        |
    |     |  +-------------+ |  R  |===|  R  | +-------------+        |
    |     |    * egress cost  \___/     \___/    * egress cost        |
    |     |    * ingress cost   |         |      * ingress cost       |
    |     |                     |         |                           |
    | +------------+>======= Optimized for both =====>+-------------+ |
    | | Local node |            |         |           | Remote node | |
    | +------------+<======= Optimized for both =====<+-------------+ |
    +---------------------------+         +---------------------------+

     Figure 9: ALTO servers with mesh interconnection and reverse path
                                  probes

   The system overview of this approach is shown in Figure 9.







Asai, et al.            Expires December 5, 2012               [Page 17]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


3.5.  A5. ALTO servers with hop-by-hop interconnection by using a path
      vector algorithm

   A1-A4 cannot solve C2 because these simple cost-based approaches have
   limitations to reflect inter-AS policies in the BGP routing while BGP
   is a path-vector routing protocol that is one of policy-based routing
   protocols.  A solution approach to solve C2 is to introduce a path-
   vector algorithm that propagates policies hop-by-hop between
   interconnected ALTO servers like the BGP routing, and to provide cost
   for detoured paths.  This approach enables flexible policy
   propagation, but requires many new specifications, protocols, and
   algorithms to propagate policies and to compute a cost map that is
   provided to applications.

                     provider +-------------+ provider
        transit +-------------| Remote AS 1 |-------------+ transit
                |             |             |             |
                |  ++===========ALTO Server===========++  |
                |  ||         +-------------+         ||  |
       customer v  ||                                 ||  v customer
        +----------||-+peering+-------------+peering+-||-------------+
        | Local AS || |<----->| Remote AS 2 |<----->| || Remote AS 3 |
        |          || |       |             |       | ||             |
        | ALTO Server===========ALTO Server===========ALTO Server    |
        +-------------+       +-------------+       +----------------+
                    <===== Cost/Policy for AS 2
                                          <===== Cost/Policy for AS 3
                    <===== Cost/Policy for AS 3 via AS 2
                             (e.g., policy: detouring allowed
                                    at small additional cost)

      Cost map @Local AS
     +-------------------------------------------------------+
     | Source/Destination | Next/Previous | Cost of Local AS |
     | (Detoured Path)    |  hop AS (BGP) | Ingress | Egress |
     +-------------------------------------------------------+
     | AS 1               | AS 1          |      20 |     20 |
     | AS 2               | AS 2          |      10 |     10 |
     | AS 3               | AS 1          |      40 |     40 |
     | AS 3 via AS 2      | (AS 2)        |      30 |     30 |
     +-------------------------------------------------------+

    Figure 10: ALTO servers with hop-by-hop interconnection by using a
                           path vector algorithm

   An example of topology and a cost map adopting this approach is shown
   in Figure 10.  ALTO servers of each AS establish interconnection, and
   then they exchange and propagate policies with each other by a path-



Asai, et al.            Expires December 5, 2012               [Page 18]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


   vector algorithm.  The ALTO server of the local AS then computes a
   cost map for sources/destinations and detoured paths from all the
   received policies.  Thus, this approach can provide the cost for
   detoured paths as well as the layer 3 network paths.  In this
   example, the cost of the detoured path from/to AS 3 via AS 2 becomes
   lower than that of the end-to-end path from/to AS 3 via AS 1.  This
   means that the AS 2 does not disallow the detoured path.  If AS 2
   does not prefer detouring, the cost of the detoured path becomes
   higher than the others according to the propagated policies.  Note
   that the sources/destination and detoured paths are aggregated by
   per-AS in this example, but they may be per-prefix.

3.6.  Summary of the Conceivable Solution Approaches

                   +----------+----+----+----+----+----+
                   | Approach | C1 | C2 | C3 | C4 | C5 |
                   +----------+----+----+----+----+----+
                   | A1       |  x |    |    |    |    |
                   |          |    |    |    |    |    |
                   | A2       |  x |    |  * |    |    |
                   |          |    |    |    |    |    |
                   | A3       |  x |    |  * |    |    |
                   |          |    |    |    |    |    |
                   | A4       |  x |    |  * |  x |  x |
                   |          |    |    |    |    |    |
                   | A5       |  x |  x |  * |  x |  x |
                   +----------+----+----+----+----+----+

    x: Solved or better than nothing; *: Solved or better than nothing
             with additional methods discussed in Section 3.7

          Table 1: Summary of the conceivable solution approaches

3.7.  Discussion on uneven policy configuration

   Any of A1 A5 do not provide a method to solve C3.  This section
   discusses possible methods to solve C3.  We first note that A1 never
   achieves to solve C3 because it only provides the egress cost from
   the local AS.  The possible methods to solve C3 are listed and
   summarized as follows.

   o  Global regulation: This method is to define global regulation for
      cost configuration, and to provide a cost computation function;
      for example, cost X for X$/Mbps, or more simply cost 2, 1, and 0
      for transit (from/to provider), peering, and transit (from/to
      customer), respectively.  However, it is not realistic because the
      inter-AS policy is too complex to define the global regulation.
      Moreover, the economic policies between interconnected ASes cannot



Asai, et al.            Expires December 5, 2012               [Page 19]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


      be disclosed by each network provider due to commercial contracts.

   o  Hop-by-hop regulation: In A3 A5, ALTO servers of each AS establish
      interconnection.  In these cases, the interconnected ALTO servers
      can introduce a regulation algorithm for the exchanged cost.  The
      cost will be regulated among interconnected ALTO servers and this
      might be ``better than nothing'', but C3 still exists among ALTO
      servers that are not interconnected.

   o  Inference-based regulation: AS relationships inference can be one
      of the methods to regulate the complex economic policies.  This is
      an alternative to the global regulation method to solve the
      problem with non-disclosure AS relationships.  AS relationships
      inference algorithms have been proposed in the research field,
      such as [Asai10], [Dimitropoulos07], and [Gao01].  Global
      regulation is achieved by using these inference algorithms.  The
      inferred AS relationships for some links may not be accurate, but
      this might also be ``better than nothing''.

   In summary, within the interconnected ALTO servers, the hop-by-hop
   regulation is the best.  The inference-based regulation can be used
   to assist in regulating uneven policy configuration in the other
   cases or finding anomalous cost configurations.




























Asai, et al.            Expires December 5, 2012               [Page 20]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


4.  IANA Considerations

   No need to describe any request regarding number assignment.
















































Asai, et al.            Expires December 5, 2012               [Page 21]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


5.  Security Considerations

   This document is neither a requirements document nor a protocol
   specification.  However, since the solution approaches exchange the
   inter-AS economic policies with ALTO servers operated by other ASes
   (i.e., external network domains), two security considerations are
   discussed as follows.

   o  The ALTO servers operated by other ASes may falsify the received
      cost map or policies.  The protocol specifications of the solution
      approaches must include anti-falsification and verification
      mechanisms (e.g., digital signing) for the exchanged cost map or
      policies.

   o  The exchanged cost map or policies may contain the non-disclosure
      inter-AS information.  The protocol specifications of the solution
      approaches should consider the schemes to aggregate and filter the
      exchanged cost map or policies in order not to reveal the non-
      disclosure information.
































Asai, et al.            Expires December 5, 2012               [Page 22]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


6.  Acknowledgements

   Moritz Steiner (Bell-Labs), Piotr Wydrych (AGH University of Science
   and Technology), Russ White (Cisco Systems), Stefano Previdi (Cisco
   Systems), Volker Hilt (Alcatel-Lucent Bell-Labs), and many others
   provided informative discussions and valuable comments.













































Asai, et al.            Expires December 5, 2012               [Page 23]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


7.  Informative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC4277]  McPherson, D. and K. Patel, "Experience with the BGP-4
              Protocol", RFC 4277, January 2006.

   [RFC5693]  Seedorf, J. and E. Burger, "Application-Layer Traffic
              Optimization (ALTO) Problem Statement", RFC 5693,
              October 2009.

   [I-D.ietf-alto-protocol]
              Alimi, R., Penno, R., and Y. Yang, "ALTO Protocol",
              draft-ietf-alto-protocol-11 (work in progress),
              March 2012.

   [Aggarwal07]
              Aggarwal, V., Feldmann, A., and C. Scheideler, "Can ISPs
              and P2P users cooperate for improved performance?",
               SIGCOMM Comput. Commun. Rev., vol. 37, no. 3, pp. 29-40,
              2007.

   [Asai10]   Asai, H. and H. Esaki, "Estimating AS Relationships for
              Application-Layer Traffic Optimization",  3rd Workshop on
              Economic Traffic Management, LNCS Vol. 6236, pp. 51-63,
              2010.

   [Dimitropoulos07]
              Dimitropoulos, X., Krioukov, D., Fomenkov, M., Huffaker,
              B., Hyun, Y., claffy, k., and G. Riley, "AS Relationships:
              Inference and Validation",  ACM SIGCOMM Comput. Commun.
              Rev., Vol. 37, No. 1, pp. 29-40, 2001.

   [Gao01]    Gao, L., "On inferring autonomous system relationships in
              the Internet",  IEEE/ACM Transactions on Networking,
              Vol. 9, No. 6, pp. 733-745, 2001.

   [Ho09]     Ho, Haddow, T., Ledlie, J., Draief, D., and P. Pietzuch,
              "Deconstructing internet paths: an approach for AS-level
              detour route discovery",  Proceedings of the 8th
              international conference on Peer-to-peer systems, p. 6,
              2009.

   [Wang03]   Wang, F. and L. Gao, "On Inferring and Characterizing
              Internet Routing Policies",  IMC '03: Proceedings of the
              3rd ACM SIGCOMM conference on Internet measurement,
              pp. 15-26, 2003.



Asai, et al.            Expires December 5, 2012               [Page 24]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


   [Xie08]    Xie, H., Yang, Krishnamurthy, A., Liu, and A.
              Silberschatz, "P4P: provider portal for applications",
               SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008
              conference on Data communication, pp. 351-362, 2008.















































Asai, et al.            Expires December 5, 2012               [Page 25]


Internet-Draft       Considerations on AS-Level ALTO           June 2012


Authors' Addresses

   Hirochika Asai
   The University of Tokyo
   7-3-1 Hongo
   Bunkyo-ku, Tokyo  113-8656
   JP

   Phone: +81 3 5841 6748
   Email: panda@hongo.wide.ad.jp


   Hiroshi Esaki
   The University of Tokyo
   7-3-1 Hongo
   Bunkyo-ku, Tokyo  113-8656
   JP

   Phone: +81 3 5841 6748
   Email: hiroshi@wide.ad.jp


   Tsuyoshi Momose
   Cisco Systems G.K.
   2-1-1 Nishi-Shinjuku
   Shinjuku-ku, Tokyo  163-0409
   JP

   Phone: +81 3 5324 4154
   Email: tmomose@cisco.com





















Asai, et al.            Expires December 5, 2012               [Page 26]