Internet Engineering Task Force H. Asai
Internet-Draft H. Esaki
Intended status: Informational U. Tokyo
Expires: December 18, 2011 T. Momose
Cisco Systems
June 16, 2011
Global Cost Mapping for AS-Level Application-Layer Traffic Optimization
draft-asai-cross-domain-overlay-02
Abstract
This document provides an approach of cross-domain traffic control in
application-layer or overlay routing, such as content delivery
networks and live media streaming systems, to reduce inter-domain
traffic and transit traffic that costs more for Internet service
providers (ISPs). This approach utilizes global cost map to regulate
policy conflicts between distinct ISPs. The approach and the
simulation results in this document suggest to use global cost map in
application-layer routing and highlight the advantage of cross-domain
cooperation with the global cost map. To distribute the global cost
map, the ALTO protocol is the best way today, and consequently, this
document defines a usage of the ALTO protocol. This document also
defines a solution approach to compute global cost map that takes
into account commercial relationships between autonomous systems,
with hiding confidential information as much as possible.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on December 18, 2011.
Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the
Asai, et al. Expires December 18, 2011 [Page 1]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1. AS . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2. AS Relationships . . . . . . . . . . . . . . . . . . . 4
1.1.3. Transit . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.4. Peering . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5. Overlay Network . . . . . . . . . . . . . . . . . . . 4
1.2. Requirements Language . . . . . . . . . . . . . . . . . . 4
2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Cross-Domain Traffic of Overlay Networks . . . . . . . . . 5
2.2. Cross-Domain Cooperation . . . . . . . . . . . . . . . . . 6
2.3. Non-disclosure AS Relationships . . . . . . . . . . . . . 7
2.4. Problems with the P4P-based Cost Computation . . . . . . . 8
3. Simulation Results: Cross-domain Policy Conflicts . . . . . . 9
4. Solution Approach . . . . . . . . . . . . . . . . . . . . . . 12
4.1. AS Path Provision Service . . . . . . . . . . . . . . . . 14
4.2. AS Relationships Estimation Service . . . . . . . . . . . 15
4.3. Cost Computation Service . . . . . . . . . . . . . . . . . 16
5. ALTO Protocol for Cost Distribution . . . . . . . . . . . . . 18
5.1. Deployment Consideration . . . . . . . . . . . . . . . . . 18
5.2. AS Path Provision Service Consideration . . . . . . . . . 19
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
7. Security Considerations . . . . . . . . . . . . . . . . . . . 22
8. Informative References . . . . . . . . . . . . . . . . . . . . 23
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25
Asai, et al. Expires December 18, 2011 [Page 2]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
1. Introduction
Many systems, such as content delivery networks (CDNs) and live media
streaming systems, have introduced application-layer routing for
their communication scheme to avoid excessive server load and to
achieve effective and high-quality communication (e.g., high
throughput, fault tolerance). The advanced application-layer
routing, so-called overlay routing, has been widely used in peer-to-
peer (P2P) technologies, and some CDNs and live media streaming
systems have adopted P2P technologies. Today, the traffic generated
by these applications become a significant amount of the Internet
traffic [RFC5693]. Since these applications construct their own
network topology over the Internet, generally without taking into
account the network layer topology (i.e., layer 3 topology), these
applications frequently utilize a larger amount of network resources
than network providers expect. Since inter-domain links, especially
transit links, are generally expensive than intra-domain links, this
document focuses on inter-domain traffic.
This document provides an approach of cross-domain traffic control in
application-layer or overlay routing to reduce inter-domain traffic
and transit traffic that costs more for network providers, such as
Internet service providers (ISPs). Our simulation results show that
CDNs using P2P technologies that are unaware of commercial
relationships between autonomous systems (ASes) [RFC1930] utilize
transit links more, and consequently, taking into account the
commercial relationships between ASes is essential for commercial
ISPs. The simulation results also suggest to use global cost map to
regulate policy conflicts between distinct ISPs, and highlight the
advantage of cross-domain cooperation with the global cost map.
Since the ALTO protocol [I-D.ietf-alto-protocol] is the best way to
distribute the global cost map today, this document defines a usage
of the ALTO protocol. This document also provides an approach to
compute global cost map that takes into commercial relationships
between ASes, with hiding confidential information as much as
possible.
1.1. Terminology
We use the following terms in this document.
1.1.1. AS
Autonomous System
Asai, et al. Expires December 18, 2011 [Page 3]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
1.1.2. AS Relationships
AS relationships represent commercial relationships between
interconnected ASes. AS relationships are categorized into two major
types: transit and peering.
1.1.3. Transit
Transit is a type of AS relationships. Transit relationships are
also called provider-customer relationships. A customer AS purchases
Internet access from its transit providers over transit links by
paying some amount of money according to the actual bandwidth usage.
1.1.4. Peering
Peering is a type of AS relationships, and the relationships between
two peering ASes are equal relationships. Traffic exchanged over
peering links is free of charge.
1.1.5. Overlay Network
Overlay networks are constructed by application-layer nodes such as
P2P application nodes over the Internet (i.e., IP network) that is
operated by network providers. The topology and routing of overlay
networks are controlled by applications that construct overlay
networks but not by 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 18, 2011 [Page 4]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
2. Problem Statement
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].
However, overlay networks sometimes break these routing policies and
cause problems with cross-domain traffic. We summarize the problems
with overlay networks as follows.
o The cross-domain traffic generated by applications are neither
controlled nor optimized on overlay networks from the viewpoint of
network providers.
o ASes hardly cooperate with each other in computing and fairly
balancing cost when ASes provide some cost information to
applications as a traffic optimization metric because charging
policies are complicated and each AS operates its network
autonomously.
o Neither AS relationships nor charging policies for transit traffic
can be disclosed.
2.1. Cross-Domain Traffic of Overlay Networks
Network providers cannot control nor 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 overlay network topology and traffic
delivery paths, such as peer, neighbor, or path selection algorithms.
Asai, et al. Expires December 18, 2011 [Page 5]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
+------+ 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 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 cross-domain traffic of
overlay networks. An example of interconnections of ASes and their
relationships is shown in Figure 1. Suppose server nodes, nodes that
provide a certain content file, exist in both AS 3 and AS 4 and a
client node, a node that downloads the file, in AS 2 is to retrieve
the file from one of these server nodes, the client node should
select a server node in AS 3 to reduce transit charge for both the
client-node-side and server-node-side ASes, but today's client nodes
that are unaware of AS relationships often select other server nodes.
Moreover, on overlay networks, the connectivity of most of end-point
nodes (i.e., peers) is provided by residential ISPs, and most of them
are not transit providers but transit customers. Therefore, 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 ISPs.
[RFC5693] also claims this problem with cross-domain traffic in terms
of transit cost as well as congestion in intra-domain networks.
2.2. Cross-Domain Cooperation
Asai, et al. Expires December 18, 2011 [Page 6]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
+------+ provider
| AS 1 |----------------------+
provider +------+ 1 | transit
5 | transit |
30 v v 10
customer +------+ peering +------+ +------+ customer
| AS 2 |<------->| AS 3 | | AS 4 |
+------+ 10 20 +------+ +------+
Each number represents egress cost.
Figure 2: An example of unfair cost setting
The ALTO Working Group has worked on application-layer traffic
optimization, and it has proposed a protocol to distribute end-to-end
cost between peers [I-D.ietf-alto-protocol]. Cost distributed by
this protocol is assumed to compute based on P4P [Xie08] that is an
oracle-based approach of application-layer traffic optimization. The
P4P approach has achieved fair utilization of network resources by
setting up priorities automatically computed from the configuration
(e.g., `cost' in OSPF) in routers to links.
However, there is a problem with these oracle-based approaches when
they are applied to the Internet (i.e., multi-domain system).
Charging policies for inter-AS links and exchanged traffic volume are
so complicated that different ASes hardly cooperate with each other
in computing and fairly balancing cost. This is because each AS aims
to maximize its income and minimize its expense. This problem is
similar to so-called hot-potato problems. 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 2, then the accumulated cost of the path from AS 4 to AS 2
becomes larger than that of the path from AS 3 to AS 2 though the
path from AS 3 to AS 2 seems to be better than the other. On the
other hand, when we consider ingress cost setting, cost on the source
is ignored. Thus, oracle-based approaches are exposed to policy
conflicts between distinct ASes, and hardly achieve fair traffic
optimization among multiple autonomous domains because the Internet
is autonomously operated by each AS.
2.3. Non-disclosure AS Relationships
To enable AS relationships-aware application-layer or overlay
routing, applications are required to take into account AS
relationships or charging policies among ASes. So, cross-domain cost
is required to be disclosed or estimated, and provided.
However, interconnections between ASes are established by commercial
Asai, et al. Expires December 18, 2011 [Page 7]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
contracts, and consequently, most ISPs cannot disclose their
commercial relationships. Hence, there is a difficulty in applying
the approach of cross-domain cost computation in P4P to the real
Internet because issues on disclosing topology information, such as
confidential commercial contracts, lie upon it. Even though ASes can
exchange the cost of cross-domain links, the problem with cross-
domain cooperation described in Section 2.2 still exists.
2.4. Problems with the P4P-based Cost Computation
+-------------+-----------------------------------------------------+
| | Problems |
+-------------+-----------------------------------------------------+
| Cooperation | Require to set coordinated cost onto inter-AS links |
| | to regulate policy conflicts between interconnected |
| | ASes, but each AS is autonomously operated |
| | |
| Security | Require to distribute the cost to the public or an |
| | ALTO server to compute cost for communication |
| | paths, i.e., require to disclose AS relationships, |
| | even though AS relationships are non-disclosure |
| | ones |
+-------------+-----------------------------------------------------+
Table 1: Problems with the P4P-based Cost Computation
The P4P approach mainly defines intra-domain traffic optimization,
and consequently, it does not focus on the cross-domain cooperation.
We summarize problems with the P4P-based cost computation in Table 1.
Asai, et al. Expires December 18, 2011 [Page 8]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
3. Simulation Results: Cross-domain Policy Conflicts
To point out the problems with cross-domain traffic and cooperation
against cross-domain policy conflicts, we evaluate cross-domain
traffic of a P2P CDN with a trace-driven simulation.
We had collected a list of peers from a tracker
(http://bttracker.debian.org:6969/announce) every minute from 23/10/
2009 to 19/12/2009 for the content: Debian Linux DVD image; debian-
503-i386-DVD-1.iso (4.4GB). The collected list contains sets of
peer's IP address and port number. We generated a trace for the
trace-driven simulation according to the method described in
[Asai10-1]. By using a trace-driven simulator [Asai10-1] with this
trace, we compute exchanged cross-domain traffic volume of ASes
providing the Internet connectivity to peers. Note that the piece
size is set to 1 in this simulation and other parameters follow
[Asai10-1].
We evaluate five oracle-based peer selection algorithms in the P2P
CDN; 1) Random, 2) AS hops, 3) Selfish, 4) Gentle, and 5)
Cooperative. ``Random'' and ``AS hops'' are algorithms to randomly
select a peer and to select a peer minimizing AS hops between source
and destination, respectively. ``Selfish'' is an algorithm to select
a peer minimizing expense of ASes accommodating download peers (based
on a download-side policy or referring to a download-side ALTO
server); i.e., ``intra-domain'' is the highest priority, followed by
``from customer'', ``from peer'' and ``from provider''. ``Gentle'' is
an algorithm to select a peer maximizing profit of ASes accommodating
upload peers (based on an upload-side policy or referring to an
upload-side ALTO server); i.e., ``intra-domain'' is the highest
priority, followed by ``to customer'', ``to peer'' and ``to
provider''. ``Cooperative'' is the intermediate between ``Selfish''
and ``Gentle''; i.e., to select a peer minimizing the summation of
cost of both download- and upload-sides where the cost values of
intra-domain, from/to provider, from/to peer, and from/to customer
are 0, 3, 2, 1, respectively.
Asai, et al. Expires December 18, 2011 [Page 9]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
+-------------+----------------+----------------+------------+
| Algorithm | From providers | From customers | From peers |
+-------------+----------------+----------------+------------+
| Random | 96.8% | 0.4% | 2.7% |
| | | | |
| AS hops | 90.2% | 4.9% | 4.9% |
| | | | |
| Selfish | 89.3% | 8.8% | 1.9% |
| | | | |
| Gentle | 96.5% | 0.0% | 3.4% |
| | | | |
| Cooperative | 88.9% | 5.6% | 5.5% |
+-------------+----------------+----------------+------------+
Table 2: Simulation Results: Breakdown of total exchanged cross-
domain traffic volume of ASes accommodating peers by types of AS
relationships (Download traffic)
+-------------+--------------+--------------+----------+
| Algorithm | To providers | To customers | To peers |
+-------------+--------------+--------------+----------+
| Random | 61.0% | 24.8% | 14.2% |
| | | | |
| AS hops | 62.0% | 19.7% | 18.3% |
| | | | |
| Selfish | 63.6% | 12.8% | 23.6% |
| | | | |
| Gentle | 7.4% | 83.2% | 9.4% |
| | | | |
| Cooperative | 11.4% | 79.4% | 9.3% |
+-------------+--------------+--------------+----------+
Table 3: Simulation Results: Breakdown of total exchanged cross-
domain traffic volume of ASes accommodating peers by types of AS
relationships (Upload traffic)
We show the breakdown of total exchanged cross-domain traffic volume
of ASes accommodating peers by types of AS relationships in Table 2
and Table 3. These results show that even the algorithm Selfish did
not achieve to reduce transit traffic from providers much, and
consequently, it is difficult to reduce much download transit
traffic. On the other hand, for upload traffic, algorithms Gentle
and Cooperative significantly reduced transit traffic to providers.
These results also indicate that the algorithm Cooperative worked
quite well for both download and upload traffic though algorithms
Selfish and Gentle were not good for either download or upload
traffic. Therefore, traffic control with cooperation between
download- and upload-sides is required for transit traffic reduction.
Asai, et al. Expires December 18, 2011 [Page 10]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
Note that further evaluation and results (e.g., with other traces and
evaluation parameters) should be given in future.
Asai, et al. Expires December 18, 2011 [Page 11]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
4. Solution Approach
This section describes an approach to solve the problems that have
been figured out in Section 2 and Section 3. In this approach, the
cost computation for AS paths between any two ASes consists of three
services, as follows.
1. AS path provision service: This service provides AS paths between
two arbitrary nodes (IP addresses) to applications or cost
computation servers (e.g., ALTO servers), and it is provided by
each AS.
2. AS relationships estimation service: This service provides AS
relationships (i.e., cross-domain cost) of any specified inter-AS
links to applications or cost computation servers. This service
is provided by its service providers which may not be ISPs but
some other volunteer service providers.
3. Cost computation service: This service computes cost for an AS
path according to an algorithm, and it is installed into each
application or cost computation servers on the Internet. The
cost is computed as a globally unique value on the Internet when
the algorithm is identical. Here, a set of the computed cost is
denoted as ``global cost map''. The computed cost for the AS
path would be used for traffic optimization.
It is true that AS paths can be resolved from IP address-based paths,
which can be retrieved by network management tools (e.g.,
traceroute). Hence, ASes do not have to provide AS paths because
applications can resolve AS paths without support of ASes. However,
it is an ongoing work to assign appropriate AS numbers to
routers [Huffaker10]. Moreover, some ISPs block ICMP packets
including ICMP time exceed messages, and consequently, IP address-
based paths are not always resolved. Therefore, provision of AS
paths by ASes is enough helpful to resolve AS paths and use them for
AS relationships-aware application-layer traffic optimization. Thus,
it is recommended for each AS to implement this service. A method
for providing AS path to applications or cost computation servers
(e.g., ALTO servers) is described in Section 4.1.
This approach aims to hide information on AS relationships as much as
possible; i.e., not to disclose AS relationships. So, it uses AS
relationships estimated from publicly available information instead
of AS relationships which are to be disclosed by ASes. This document
provides one possible estimation method and the detailed description
follows in Section 4.2.
Cost for a path which would be used for the traffic optimization is
Asai, et al. Expires December 18, 2011 [Page 12]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
computed from the estimated AS relationships by a certain algorithm.
This document does not define any specific algorithms but provides an
example as an idea in Section 4.3.
+------------------+----------------------------------+-------------+
| Service | Service provider | Requirement |
| | | level |
+------------------+----------------------------------+-------------+
| * AS path | Each AS | RECOMMENDED |
| provision | | |
| | | |
| * AS | Volunteer service providers etc. | REQUIRED |
| relationships | | |
| estimation | | |
| | | |
| * Cost | Each application or cost | REQUIRED |
| computation | computation servers (e.g., ALTO | |
| | servers) | |
+------------------+----------------------------------+-------------+
Table 4: Requirements
These services and the requirements of this approach are summarized
in Table 4. AS relationships estimation and cost computation
services are REQUIRED ones for taking into account AS relationships.
AS path provision service is not mandatory but recommended one
because this function can be alternated by other mechanisms.
Asai, et al. Expires December 18, 2011 [Page 13]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
4.1. AS Path Provision Service
+-----------------------------------------+
| Applications / Cost computation servers |
+-----------------------------------------+
| ^
AS paths request | | AS paths response
(src X, dst Y) | | (AS path from X to Y)
- -- -- -- -- -- | -- | -- -- -- -- -- -- -- -- -- -- -- -- -- -
| | <at ISP>
+----------|----|-----------+
| v | [AS path provision service]
| +---------------------+ |
| | Interface w/ filter | |
| +---------------------+ |
| | ^ |
| | | |
| v | | ______
| +-----------------+ | routing table / \
| | AS paths table |<---------------------* BGP *
| | lookup function | | w/ AS paths * router *
| +-----------------+ | \______/
+---------------------------+
Figure 3: System overview of AS path provision service
As described above, AS path provision by ASes helps applications to
resolve AS paths. Here, note that AS paths can be easily retrieved
from BGP routing tables at ASes' BGP routers. The overview of the AS
path provision system is shown in Figure 3. The requirements of AS
path provision are listed below.
o AS path provision service discovery protocol: A mechanism which
enables applications to discover AS path provision servers is
required. Note that This document does not define this service
discovery protocol.
o AS path provision protocol: A mechanism which enables applications
to resolve AS path from an IP address belonging to the AS which
provides the AS path provision service to another IP address
belonging to an arbitrary AS via a certain protocol is required.
Here, note that the source IP address of the request must belong
to the AS providing the service because AS paths are retrieved
from routing tables in BGP routers and a routing table has a
spanning tree from the AS as root (i.e., the source AS). Note
that this document does not define the protocol.
Asai, et al. Expires December 18, 2011 [Page 14]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
o Filter: AS path provision services can deny some requests by a
filter to hide their information.
4.2. AS Relationships Estimation Service
Several AS relationships inference or estimation algorithms have been
proposed in the research field. There are two types of these
algorithms; one is based on paths analysis [Gao01] and the other is
based on differences in AS' network size [Asai10-2].
The algorithms based on paths analysis have a difficulty in applying
the inferred AS relationships to the cost computation because there
are lots of missing links, which have not been inferred. The
algorithms based on differences in AS' network size first quantify
the network size, then estimate the relationships. Therefore, the
relationships can be estimated for almost all links because one BGP
routing table contains almost all ASes though there exist lots of
missing links, which are not contained in the routing table but would
be possibly observed at other points. Thus, this document uses the
algorithms based on differences in AS' network size.
Here, we provide a possible estimation method. Degree, the number of
neighboring ASes, has been commonly used as an indicator which
represents AS' network size. Degree for each AS is approximately
counted from publicly available datasets such as public BGP routing
tables (e.g., Route Views Project [RouteViews]) and Internet routing
registries. If the degree of AS X is larger than that of AS Y, AS X
is considered to be transit provider of AS Y. If the degree of AS X
is nearly equal to that of AS Y, the link between AS X and AS Y is
considered to be peering. Thus, the relationships (i.e., cost) are
estimated from publicly available information. Note that [Asai10-2]
has improved the accuracy of this estimation.
Asai, et al. Expires December 18, 2011 [Page 15]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
+-----------------------------------------+
| Applications / Cost computation servers |
+-----------------------------------------+
| ^
AS relationships request | | AS relationships response
(AS X, AS Y) | | (AS relationships of X--Y)
- -- -- -- -- -- -- -- - | -- | -- -- -- -- -- -- -- -- -- -- -
| | <at ISP>
+-----------------|----|--------------+
| | | [AS relationships estimation service]
| +---------------------+ |
| | Interface | |
| +---------------------+ |
| | ^ |
| | | |
| v | |
| +----------------------+ | +----------------+
| | AS relationships |<-------| datasets |
| | estimation algorithm | | | (AS adjacency) |
| +----------------------+ | +----------------+
+-------------------------------------+
Figure 4: System overview of AS relationships estimation service
Figure 4 shows the system overview of AS relationships estimation
service. In this figure, the AS relationships estimation service
calculates degree from AS adjacency datasets, which can be
approximated from public BGP routing tables etc., and then it
provides the estimated AS relationships from degree. Note that
degree can be replaced by the magnitude defined in [Asai10-2].
4.3. Cost Computation Service
Cost for a path is computed from the estimated AS relationships by a
certain cost computation algorithm. Cost computation services on
applications compute the cost. Note that a set of the computed cost
is called ``global cost map''.
+------+ +------+ +------+ +------+
| AS S |-->| AS X |--> ... -->| AS Y |-->| AS T |
+------+ +------+ +------+ +------+
Suppose AS S and AS T are the source AS and the destination AS,
respectively, on this AS path. The cost computation algorithm takes
into account only edge relationships, i.e., the relationships between
AS S and AS X, and AS Y and AS T.
Figure 5: AS path and a cost computation algorithm
Asai, et al. Expires December 18, 2011 [Page 16]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
This document provides an example of cost computation algorithms with
a paper in research field. There is a research on application-layer
traffic optimization in content delivery networks for reducing
transit traffic by taking into account the AS relationships with
degree [Asai10-1]. In [Asai10-1], only the relationships between
edge (i.e., source and destination) AS and their neighbors are
considered for the cost computation. The cost for the AS path shown
in Figure 5 can be computed in the following equation: cost =
{log(degree-of(S)) - log(degree-of(X))} + {log(degree-of(T)) -
log(degree-of(Y))}. Here, function ``degree-of(X)'' returns the
degree of AS X, and AS relationships (i.e., cross-domain cost) for
each inter-AS link (e.g., {log(degree-of(S)) - log(degree-of(X))} and
{log(degree-of(T)) - log(degree-of(Y))} in Figure 5) are resolved via
AS relationships estimation services described in Section 4.2.
[Asai10-1] has shown from a simulation that their method has reduced
the percentage of high-cost transit traffic (i.e., traffic from/to
provider) in inter-domain traffic on residential ASes by 8.46
percentage point compared to minimum AS hop selection though the
total amount of inter-domain traffic has not been changed.
Cost computation services run on not any servers but applications, so
the algorithms can be modified by applications. Note that
application service providers can provide the cost computation
service if they need to control the computation algorithm.
Asai, et al. Expires December 18, 2011 [Page 17]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
5. ALTO Protocol for Cost Distribution
Global cost map is computed by cost computation services, and the
ALTO protocol can be used to distribute the cost. This section
provides a way of applying the ALTO protocol to cost distribution.
+=============================+
|| AS path provision service ||
+=============================+
^
| (1) Get AS paths corresponding to sets of PIDs
+=====v==========================+
|| ALTO server || Get Cost Map
|| +--------------------------+ || (PID denotes AS number)
|| | Cost computation service | ||<---------------+
|| +--------------------------+ || |
|| ^ (3) Compute Cost Map || v
+=====|==========================+ +===============+
| (2) Get AS relationships || ALTO client ||
v +===============+
+======================+
|| AS relationships ||
|| estimation service ||
+======================+
Figure 6: Usage of ALTO protocol for cost distribution
ALTO clients get cost map from ALTO servers by a request with source
and destination PIDs, which is aggregated from end-point networks.
AS numbers can be represented as PIDs, and consequently, we use this
representation for PIDs (or PIDs with more fine granularity) because
the global cost map consists of AS-to-AS cost. Figure 6 shows the
overview scheme to get cost map from ALTO servers. An ALTO client
sends a request to an ALTO server to get cost map. After receiving
the request, the ALTO server first gets AS paths corresponding to the
requested source and destination PID sets from an AS path provision
service. The ALTO server then gets AS relationships for inter-AS
links on the AS paths. Finally, the cost map is computed from these
AS paths and AS relationships, and replied to the ALTO client.
This ALTO server providing global cost map is deployed and operated
by some volunteer service providers or neutral organizations to avoid
injecting ISP's policies that can lead conflicts between other ISPs.
5.1. Deployment Consideration
The global cost map provides cross-domain one, but it cannot be used
to optimize intra-domain traffic because it does not provide intra-
Asai, et al. Expires December 18, 2011 [Page 18]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
domain cost map. Moreover, the global cost map is not fully reliable
cost map because it is based on estimation of AS relationships; i.e.,
it might be the cost map that is not preferred by ISPs. In another
word, cost map provided by ISP-operated ALTO servers is ISP-intended
one.
+----------------------------------+
| ALTO Server with Global Cost Map |
+----------------------------------+
^
(2) Request global |
cost map | (If any conflicts are detected)
v
+-------------+
| ALTO Client | (3) Selection phase
+-------------+
^ ^
(1-1) | | (1-2)
+------+ +------+
| |
Cost map A <= conflicts? => Cost map B
| |
v v
+---------------------+ +---------------------+
| ALTO Server (ISP A) | | ALTO Server (ISP B) |
+---------------------+ +---------------------+
Figure 7: Hierarchical ALTO Architecture
To utilize intra-domain cost map and to reflect cost map provided by
ISP-operated ALTO servers, a hierarchical ALTO architecture like the
architecture experimented in Japan [I-D.kamei-p2p-experiments-japan]
suits the requirement. Figure 7 shows the overview of the
hierarchical ALTO architecture. ALTO clients can refer to ISP-
operated (or equivalent) ALTO servers unless the obtained cost map
has no conflicts. If the ALTO clients detect policy conflicts
between these ALTO servers, they fall back and request global cost
map to ALTO servers that manage the global cost map. After
retrieving the global cost map, ALTO clients go into selection phase
using both global cost map for cross-domain communication and ISPs'
cost map for intra-domain communication.
5.2. AS Path Provision Service Consideration
When we use the ALTO protocol to distribute the global cost map, AS
path provision service is required to be deployed into every ASes as
shown in Figure 6 although applications can resolve paths. This is
because the current ALTO protocol does not allow to request cost map
Asai, et al. Expires December 18, 2011 [Page 19]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
with AS path or IP-level path. In case that AS path provision
service does not deployed and AS paths are not obtained by any other
methods, ALTO servers cannot compute global cost map, or just reply a
configured default value. The hierarchical architecture described in
Section 5.1 regresses this problem because global cost map (i.e., AS
paths) are not required unless policy conflicts are detected.
Asai, et al. Expires December 18, 2011 [Page 20]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
6. IANA Considerations
No need to describe any request regarding number assignment.
Asai, et al. Expires December 18, 2011 [Page 21]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
7. Security Considerations
This document requests that all residential ISPs should provide AS
paths in their routing tables. Some ISPs do not want to reveal the
information on the AS paths because they consider that it can cause
security problems. On the other hand, AS paths are probably resolved
by network management tools such as ``traceroute'' though they
sometimes fail. Therefore, AS path provision service can be
OPTIONAL.
The requirement level of AS path provision should be discussed in
greater detail by considering the trade-off between security and
accuracy.
Asai, et al. Expires December 18, 2011 [Page 22]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
8. Informative References
[RFC1930] Hawkinson, J. and T. Bates, "Guidelines for creation,
selection, and registration of an Autonomous System (AS)",
BCP 6, RFC 1930, March 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[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-08 (work in progress), May 2011.
[I-D.kamei-p2p-experiments-japan]
Kamei, S., Momose, T., and T. Inoue, "ALTO-Like Activities
and Experiments in P2P Network Experiment Council",
draft-kamei-p2p-experiments-japan-05 (work in progress),
March 2011.
[Asai10-1]
Asai, H. and H. Esaki, "Towards Interdomain Transit
Traffic Reduction in Peer-assisted Content Delivery
Networks", 14th International Telecommunications Network
Strategy and Planning Symposium, pp. 95-100, 2010.
[Asai10-2]
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.
[Gao01] Gao, L., "On inferring autonomous system relationships in
the Internet", IEEE/ACM Transactions on Networking,
Vol. 9, No. 6, pp. 733-745, 2001.
[Huffaker10]
Huffaker, B., Dhamdhere, A., and Fomenkov, M., "Toward
Topology Dualism: Improving the Accuracy of AS Annotations
for Routers", Passive and Active Measurement: 11th
International Conference, PAM 2010, pp. 101-110, 2010.
[RouteViews]
University of Oregon, "University of Oregon Route Views
Project", <http://www.routeviews.org/>.
Asai, et al. Expires December 18, 2011 [Page 23]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
[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.
[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 18, 2011 [Page 24]
Internet-Draft Global Cost Mapping for AS-Level ALTO June 2011
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 18, 2011 [Page 25]