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]