Internet Engineering Task Force H. Asai
Internet-Draft H. Esaki
Intended status: Informational The University of Tokyo
Expires: June 3, 2012 T. Momose
Cisco Systems
Dec 2011
Considerations on the AS-Level Application-Layer Traffic Optimization
draft-asai-cross-domain-overlay-03
Abstract
Application-layer or overlay routing has been applied to various
distributed systems such as content delivery networks and live media
streaming systems. The problems with these systems for the layer 3
network providers, such as Internet service providers, are that these
systems utilize higher-cost network resources (e.g., transit links)
from the viewpoint of the layer 3 network providers but the operators
have difficulties in controlling and optimizing the traffic of these
systems because these systems construct their own networks over the
layer 3 network. The ALTO Working Group has worked on application-
layer traffic optimization to fill the gaps in routing policies
between the layer 3 network and applications by providing the
underlay network topology and cost information to these systems.
However, there are considerations on applying application-layer
traffic optimization techniques to cross-domain traffic because the
cost is assumed to be configured by each AS although ASes are
autonomously operated. This document summarizes general problems
with overlay networks and considerations on the AS-level application-
layer traffic optimization from the viewpoint of inter-AS economics.
The main concerns on the AS-level application-layer traffic
optimization are unfair policy configuration between distinct
administrative domains and asymmetric economic policies on transit
links. The underlying problem inducing these concerns is that the
economic policies between interconnected ASes are non-disclosure due
to commercial contracts. 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/.
Asai, et al. Expires June 3, 2012 [Page 1]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
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 June 3, 2012.
Copyright Notice
Copyright (c) 2011 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 June 3, 2012 [Page 2]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1. AS Relationships . . . . . . . . . . . . . . . . . . . 4
1.1.2. Transit . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3. Peering . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4. Overlay Network . . . . . . . . . . . . . . . . . . . 5
2. Cross-Domain Traffic Optimization Problems and
Considerations . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Problems with Overlay Networks . . . . . . . . . . . . . . 6
2.2. Considerations on AS-Level Application-Layer Traffic
Optimization . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1. Unfair policy configuration . . . . . . . . . . . . . 8
2.2.2. Asymmetric economic policies . . . . . . . . . . . . . 9
3. Solution Approaches . . . . . . . . . . . . . . . . . . . . . 12
3.1. Inference-based Global Policy Map . . . . . . . . . . . . 12
3.2. End-to-End Cost Map Exchange . . . . . . . . . . . . . . . 13
3.3. Path-Vector Policy Advertisement . . . . . . . . . . . . . 14
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
5. Security Considerations . . . . . . . . . . . . . . . . . . . 17
6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 18
7. Informative References . . . . . . . . . . . . . . . . . . . . 19
Appendix A. The Impact of Cross-domain Policy Conflicts . . . . . 21
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24
Asai, et al. Expires June 3, 2012 [Page 3]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
1. Introduction
Many distributed systems, such as content delivery networks (CDNs)
and live media streaming systems, have introduced application-layer
overlay routing for their communication scheme to avoid excessive
server load and to achieve effective and high-quality communication
(e.g., high throughput, fault tolerance). Server-client type
distributed systems as well as peer-to-peer applications have also
introduced application-layer overlay routing on their back-end.
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 network providers expect. Moreover, they may utilize
a detoured path that cannot be expected 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
economic policy conflicts when we focus on the AS-level application-
layer traffic optimization.
This document summarizes general problems with 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 unfair policy configuration between distinct
layer 3 network domains (i.e., ASes) and asymmetric economic policies
on transit links. The underlying problem inducing these concerns is
that the economic policies between interconnected ASes are non-
disclosure information due to commercial contracts. This document
also discusses the conceivable approaches to solve the problems and
considerations.
1.1. Terminology
We use the following terms in this document.
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
Asai, et al. Expires June 3, 2012 [Page 4]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
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. Transit relationships are also called provider-
customer relationships.
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. 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 overlay networks are controlled by applications that
construct overlay networks but not by the layer 3 network providers.
Asai, et al. Expires June 3, 2012 [Page 5]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
2. Cross-Domain Traffic Optimization Problems and Considerations
This section discusses the general problems with overlay networks and
considerations on the AS-level application-layer traffic optimization
in terms of cross-domain traffic and economics. They are categorized
into two; 1) problems with overlay networks, and 2) considerations on
AS-level application-layer traffic optimization. The former category
presents the general problems that overlay networks do not take into
account the layer 3 network economics and routing policies. The
latter category presents the considerations that the AS-level
application-layer traffic optimization has difficulties in applying
it to the real Internet because of conflicts of cross-domain policies
that are autonomously determined or configured by each administrative
domain (i.e., AS).
2.1. Problems with 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].
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 overlay network topology and traffic
delivery paths, such as peer, neighbor, or path selection algorithms.
+------+ 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.
Asai, et al. Expires June 3, 2012 [Page 6]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
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 often utilize higher-cost network resources
(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. 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 network providers.
[RFC5693] also claims this problem with cross-domain traffic in terms
of transit cost as well as congestion in intra-domain networks.
+------+ provider
| AS 1 |-----------------------------+
provider +------+ | transit
| transit |
v v
customer +------+ peering +------+ peering +------+ customer
| AS 2 |<------->| AS 3 |<------->| AS 4 |
+------+ +------+ +------+
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
utilize a detoured path that cannot be expected 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.
Asai, et al. Expires June 3, 2012 [Page 7]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
In summary, overlay networks have following problems from the
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 utilize
higher-cost 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.
o Unfair policy configuration between distinct administrative
domains: ASes hardly cooperate with each other in fairly
regulating policies of distinct ASes because inter-AS policies are
complicated and each AS operates its network under its own policy.
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.
The details of these problems are explained in the following
sections.
2.2.1. Unfair policy configuration
The ALTO Working Group has proposed a protocol to distribute end-to-
end network cost between peers [I-D.ietf-alto-protocol] to
applications. 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
Asai, et al. Expires June 3, 2012 [Page 8]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
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 Internet (i.e., multi-domain
system). 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. The hot potato problem
stated in [RFC4277] shows the difficulty in regulating policies of
distinct ASes.
+------+ provider
| AS 1 |----------------------+
provider +------+ 5 | transit
5 | transit (1$/Mbps) | (2$/Mbps)
30 v v 10
customer +------+ +------+ customer
| AS 2 | | AS 3 |
+------+ +------+
Each number represents egress cost.
Figure 3: An example of unfair 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 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
between transit customers and providers. One of the causes of this
difficulty is same as that of the issue on the unfair 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 asymmetric. So, one party's policy does not match
the other's. The same asymmetric nature is also found in BGP
routing. However, the asymmetric policy regulation on transit links
becomes more complex in the overlay routing than BGP routing. This
is because overlay network nodes that have the same functionality or
Asai, et al. Expires June 3, 2012 [Page 9]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
contents possibly exist in multiple ASes although the functionality
(i.e., connectivity to the destination) of BGP routing is mapped to a
single AS. Moreover, BGP path-vector routing is performed under the
control of the layer 3 network providers by route import and export
policies. Consequently, the computed paths in BGP routing are based
on the benefit principle with avoiding free-riding.
+------+
| AS 1 |
provider +------+
5 | transit
30 v
customer +------+
| AS 2 |
provider +------+
5 | transit
30 v
customer +------+
| AS 3 |
+------+
Each number in this figure represents cost. Note that cost for each
type of AS relationships is already regulated here; 5 for provider to
customer and 30 for customer to provider. This asymmetric cost
configuration is also found in the typical import policy in BGP
routing (i.e., local preference).
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 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.
Although the conflicts of asymmetric economic policies on transit
links may develop, the AS-level application-layer traffic
optimization can be performed by looking at the ALTO servers operated
by the local AS without any regulation. However, the global view
with regulation possibly optimizes the cross-domain traffic in terms
Asai, et al. Expires June 3, 2012 [Page 10]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
of transit charge more than the local view based one as shown in
Appendix A. Moreover, Appendix A points out the problem that the
local view based application-layer traffic optimization increases
transit traffic to providers for some transit customers.
Asai, et al. Expires June 3, 2012 [Page 11]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
3. Solution Approaches
This section discusses the conceivable approaches to solve the
problems and considerations described in Section 2. We assume that
the cost or policy information is provided via ALTO servers defined
in [RFC5693]. The solution approaches are listed as follows.
o Inference-based Global Policy Map
o End-to-End Cost Map Exchange
o Accumulated Cost Map with Path-Vector Policy Advertisement
The details of each solution approach are given in the following
sections.
3.1. Inference-based Global Policy Map
Since the underlying problem inducing the considerations on the
policy conflicts between distinct ASes is that the economic policies
between interconnected ASes cannot be disclosed by each network
provider due to commercial contracts, AS relationships inference can
be one of the solution approaches to disclose the economic policies.
AS relationships inference algorithms have been proposed in the
research field, such as [Asai10-2], [Dimitropoulos07], and [Gao01].
The end-to-end (AS-to-AS) cost can be computed from the AS
relationships inferred by these algorithms although this document
does not define the cost computation algorithm. By providing the
computed cost to applications through ALTO servers, overlay networks
can be aware of the inter-AS economics. This approach is based on
the better-than-random principle because the inferred AS
relationships for some links may not be accurate. Note that the
inaccurate inference can be overwritten by combining other solution
approaches. The advantage of this approach is that this approach can
be deployed at third-party ALTO servers because this does not require
the information provided by network providers.
This approach solves the problems and considerations described in
Section 2 as follows.
o Unawareness of the layer 3 network economics: Overlay networks can
be aware of the layer 3 network economics by providing the end-to-
end cost computed from the inferred AS relationships to
applications through ALTO servers.
o AS-level traffic detouring: In this approach, ALTO servers have
the information on the inferred AS relationships, so the ALTO
servers can provide the information to check whether the detoured
Asai, et al. Expires June 3, 2012 [Page 12]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
path is acceptable to network providers as well as the end-to-end
cost. Note that the inferred AS relationships may not exactly
match the policies and preference of network providers.
o Unfair policy configuration: The end-to-end cost is fairly
computed from the inferred AS relationships at a centralized
server. Note that there still exists an issue that the same type
of AS relationships may not present the same economic policy in
terms of transit charge.
o Asymmetric economic policies: The cost computation servers can
regulate the asymmetric policies when they compute end-to-end
cost. Note that the symmetric policies may not always match the
preference of network providers.
3.2. End-to-End Cost Map Exchange
A simple solution approach is to establish a cost exchange regulation
for inter-AS economic policies among ALTO servers of other ASes
(i.e., the cost exchange regulation will be established by creating
full mesh). ALTO servers exchange the inter-AS cost (perhaps the
cost is aggregated per-prefix or per-AS) to other ALTO servers, while
regulating the cost by a certain algorithm. Note that this document
does not define the cost regulation algorithm. ALTO servers in each
AS provide the end-to-end cost according to the computed end-to-end
cost map. This approach is simple but does not solve the problem
with AS-level traffic detouring. Moreover, there is an issue that
ALTO servers are required to establish the cost exchange regulation
with the other ASes' ALTO servers to exchange the inter-AS cost
although this approach works better-than-random if only a part of
ALTO servers establishes the cost exchange regulation.
This approach solves the problems and considerations described in
Section 2 as follows.
o Unawareness of the layer 3 network economics: ALTO servers can
provide the end-to-end cost to applications, then overlay networks
can be aware of the layer 3 network economics.
o AS-level traffic detouring: This problem is not solved by this
approach because the end-to-end cost does not contain the policies
of the paths that are disallowed by ASes.
o Unfair policy configuration: Since ALTO servers among multiple
ASes establish a regulation for the exchanged inter-AS economic
policies, the issue on unfair policy configuration is solved.
Asai, et al. Expires June 3, 2012 [Page 13]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
o Asymmetric economic policies: The regulation between ALTO servers
also solves the issue on asymmetric economic policies.
3.3. Path-Vector Policy Advertisement
The cost-based approaches have limitations to reflect the inter-AS
policies in BGP routing because BGP is a path-vector routing protocol
that is one of the policy-based routing protocols. A solution
approach to achieve the inter-AS application-layer traffic
optimization while following the BGP routing policies is to introduce
path-vector policy advertisement like BGP routing. According to a
path-vector protocol for the inter-AS application-layer traffic
optimization, the ALTO servers operated by an AS establish
interconnections with the ALTO servers operated by other ASes such as
BGP neighbors, and exchange inter-AS policies over the
interconnections; perhaps the path-vectors are aggregated per-prefix
or per-AS. In this way, each ALTO server obtains the path-vectors
with inter-AS policies. Here, note that this document does not
specify the protocol to exchange inter-AS policies over the
interconnections nor the algorithm to convert the path-vectors with
inter-AS policies into the information (e.g., cost) that is provided
from ALTO servers to applications.
The advantage of this approach is that it can emulate BGP routing
policies between interconnected ASes, and consequently, ALTO servers
can provide the preference of the layer 3 network providers to
applications. In addition to the BGP emulation (i.e., advertising
the best paths), ALTO servers can also exchange and advertise n-th
best paths or negative paths (not preferred or disallowed in BGP)
that are also informative in converting the received path-vectors to
preference of end-to-end paths. However, this approach requires to
interconnect ALTO servers operated by multiple ASes, and they
propagate the policies to the ALTO servers operated by other ASes.
Therefore, a protocol specification and a policy regulation algorithm
are essential for this approach.
This approach solves the problems and considerations described in
Section 2 as follows.
o Unawareness of the layer 3 network economics: ALTO servers can
provide the layer 3 network information converted from the
received path-vectors to applications, then overlay networks can
be aware of the layer 3 network economics.
o AS-level traffic detouring: When ALTO servers advertise n-th best
paths and negative paths, they can provide the preference
information on detoured paths whether the detoured paths are
acceptable for network providers (i.e., n-th best paths) or not
Asai, et al. Expires June 3, 2012 [Page 14]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
(i.e., negative paths).
o Unfair policy configuration: Since neighboring ALTO servers
establish a regulation for the exchanged inter-AS economic
policies, the issue on unfair policy configuration is regressed.
However, since ALTO servers exchange path-vectors with policies
through hop-by-hop, a common regulation algorithm is required to
be defined and used at every ALTO server.
o Asymmetric economic policies: The regulation algorithm shared
among ALTO servers also solves the issue on asymmetric economic
policies.
Asai, et al. Expires June 3, 2012 [Page 15]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
4. IANA Considerations
No need to describe any request regarding number assignment.
Asai, et al. Expires June 3, 2012 [Page 16]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
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 should include anti-falsification and verification
mechanisms (e.g., 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 June 3, 2012 [Page 17]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
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 June 3, 2012 [Page 18]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
7. Informative References
[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-10 (work in progress),
October 2011.
[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-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.
[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.
Asai, et al. Expires June 3, 2012 [Page 19]
Internet-Draft Considerations on AS-Level ALTO Dec 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 June 3, 2012 [Page 20]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
Appendix A. The Impact of Cross-domain Policy Conflicts
To illustrate the impact of cross-domain policy conflicts for the AS-
level application-layer traffic optimization, we evaluate the cross-
domain traffic of a P2P CDN with trace-driven simulation.
For the peer distribution, we had collected lists of peers from a
tracker (http://bttracker.debian.org:6969/announce) every minute from
31/10/2009 to 30/11/2009 (JST) for the content: Debian Linux DVD
image; debian-503-i386-DVD-1.iso (4.4GB). The collected lists
contain sets of peer's IP address and port number. The number of
unique IP addresses of the collected peers is 48844, and these peers
are distributed to 2569 ASes which has a power law distribution.
From this peer distribution, we generated a trace for the trace-
driven simulation according to the method described in [Asai10-1].
By using this trace and a trace-driven simulator used in [Asai10-1],
we computed the exchanged cross-domain traffic volume of ASes
providing the Internet connectivity to peers. Note that the piece
size was set to 4.4GB (i.e., whole file) in this simulation and other
parameters follow [Asai10-1].
We evaluated five oracle-based peer selection algorithms in the P2P
CDN; 1) Random, 2) AS hops, 3) Local view, 4) Remote view, and 5)
Global view. ``Random'' and ``AS hops'' are algorithms to randomly
select a peer and to select a peer minimizing AS hops between source
and destination, respectively. ``Local view'' is an algorithm to
select a peer minimizing expense of ASes accommodating local peers
downloading the file from other peers; i.e., ``intra-domain'' is the
highest priority, followed by ``from customer'', ``from peer'' and
``from provider''. ``Remote view'' is an algorithm to select a peer
maximizing profit of ASes accommodating remote peers transferring the
file to local peers; i.e., ``intra-domain'' is the highest priority,
followed by ``to customer'', ``to peer'' and ``to provider''.
``Global view'' is the intermediate between ``Local view'' and
``Remote view''; i.e., to select a peer minimizing the summation of
cost of both local and remote 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 June 3, 2012 [Page 21]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
+-------------+----------------+----------------+------------+
| Algorithm | From providers | From customers | From peers |
+-------------+----------------+----------------+------------+
| Random | 96.8% | 0.4% | 2.7% |
| | | | |
| AS hops | 90.2% | 4.9% | 4.9% |
| | | | |
| Local view | 89.3% | 8.8% | 1.9% |
| | | | |
| Remote view | 96.5% | 0.0% | 3.4% |
| | | | |
| Global view | 88.9% | 5.6% | 5.5% |
+-------------+----------------+----------------+------------+
Table 1: Simulation Results: Breakdown of total exchanged cross-
domain traffic volume of ASes accommodating peers by types of AS
relationships (incoming traffic)
+-------------+--------------+--------------+----------+
| Algorithm | To providers | To customers | To peers |
+-------------+--------------+--------------+----------+
| Random | 61.0% | 24.8% | 14.2% |
| | | | |
| AS hops | 62.0% | 19.7% | 18.3% |
| | | | |
| Local view | 63.6% | 12.8% | 23.6% |
| | | | |
| Remote view | 7.4% | 83.2% | 9.4% |
| | | | |
| Global view | 11.4% | 79.4% | 9.3% |
+-------------+--------------+--------------+----------+
Table 2: Simulation Results: Breakdown of total exchanged cross-
domain traffic volume of ASes accommodating peers by types of AS
relationships (outgoing traffic)
Table 1 and Table 2 show the breakdown of total exchanged cross-
domain traffic volume of ASes accommodating peers by types of AS
relationships. These results show that each algorithm did not
achieve to reduce incoming transit traffic from providers much. On
the other hand, for outgoing traffic, ``Remote view'' and ``Global
view'' algorithms significantly reduced outgoing transit traffic to
providers. The reason why the impact on the incoming transit traffic
from providers is small is that the ASes accommodating local peers
are generally transit customers, and consequently, the number of the
paths that these ASes become transit providers or peering ASes are
small. On the contrary, the impact on the outgoing transit traffic
to providers is larger than the incoming transit traffic because the
Asai, et al. Expires June 3, 2012 [Page 22]
Internet-Draft Considerations on AS-Level ALTO Dec 2011
number of the paths that the ASes accommodating remote peers become
transit providers or peering ASes are not small. The breakdown of
the edge types of AS relationships for possible delivery paths is
discussed in [Asai10-1].
Moreover, this simulation points out the problem that ``Local view''
algorithm increases transit traffic to providers for some transit
customers. In this simulation, when ``Local view'' algorithm is
used, transit traffic to providers was increased for 23% of ASes
accommodating peers while it was decreased for 13% of them, compared
to ``AS hop'' algorithm. This exhibits the policy conflicts have
developed between local and remote ASes at ``Local view'' algorithm.
Note that these simulation results intend to indicate that the AS-
level application-layer traffic optimization based on local view
increases transit traffic to providers for some transit customers,
and the global view based one with the policy regulation among
multiple ASes can reduce high-cost transit traffic. For other traces
and applications, further evaluation should be performed.
Asai, et al. Expires June 3, 2012 [Page 23]
Internet-Draft Considerations on AS-Level ALTO Dec 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 June 3, 2012 [Page 24]