Internet Engineering Task Force H. Asai
Internet-Draft H. Esaki
Intended status: Informational U. Tokyo
Expires: December 17, 2010 T. Momose
Cisco Systems
June 15, 2010
A Solution Approach for AS Relationships-aware Overlay Routing
draft-asai-cross-domain-overlay-00
Abstract
This document provides an idea of cross-domain cost estimation to
control cross-domain traffic in overlay routing and to reduce transit
traffic, which costs more for Internet service providers.
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 17, 2010.
Copyright Notice
Copyright (c) 2010 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 17, 2010 [Page 1]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1. AS . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2. AS Relationships . . . . . . . . . . . . . . . . . . . 3
1.1.3. Transit . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4. Peering . . . . . . . . . . . . . . . . . . . . . . . 3
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 ALTO Approach . . . . . . . . . . . . . 8
3. Solution Approach . . . . . . . . . . . . . . . . . . . . . . 9
3.1. AS Path Provision Service . . . . . . . . . . . . . . . . 10
3.2. AS Relationships Estimation Service . . . . . . . . . . . 11
3.3. Cost Computation Service . . . . . . . . . . . . . . . . . 12
4. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
6. Security Considerations . . . . . . . . . . . . . . . . . . . 16
7. Informative References . . . . . . . . . . . . . . . . . . . . 17
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19
Asai, et al. Expires December 17, 2010 [Page 2]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
1. Introduction
Peer-to-peer (P2P) technologies have been introduced in many systems
such as content delivery networks and video streaming systems. These
P2P technologies have enabled to avoid excessive server load and to
achieve effective and high-quality communication (e.g., high
throughput, fault tolerance). Today, the traffic generated by P2P
applications become a significant amount of the Internet
traffic [RFC5693]. Since P2P applications construct their own
network topologies over the Internet without taking into account the
network layer topology (i.e., layer 3 topology), these P2P
applications frequently utilize a larger amount of network resources
than network providers expect.
This document provides an idea of cross-domain cost estimation to
control cross-domain traffic in overlay routing and to reduce transit
traffic which costs more for network providers by taking into account
the economical relationships among autonomous
systems (ASes) [RFC1930], 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
1.1.2. AS Relationships
AS relationships represent the economical 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. Customer ASes purchase
Internet access from their 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.
Asai, et al. Expires December 17, 2010 [Page 3]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
1.1.5. Overlay Network
Overlay networks are constructed by application-layer nodes. We
refer to not only P2P networks but also client-server content
delivery networks whose servers are located at multiple points as
overlay networks.
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 17, 2010 [Page 4]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
2. Problem Statement
The Internet consists of thousands of ASes which are operated by
distinct network providers such as commercial Internet service
providers (ISPs), companies and universities. Each AS normally
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 economical
viewpoint, network providers want to reduce the traffic volume
exchanged with transit providers as much as possible, and
consequently, they manage the routing policies as explained in
[Wang03].
However, overlay networks sometimes break the routing policies and
cause problems about the 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.
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 traffic is controlled by algorithms of each application such
as peer/neighbor/path selection algorithms.
Asai, et al. Expires December 17, 2010 [Page 5]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
+------+ 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 operators.
Figure 1: An example of the relationships among ASes
We show an example of the problem of cross-domain traffic of overlay
networks. An example of interconnections of ASes and their
relationships is shown in Figure 1. Suppose mirror servers exist in
both AS 3 and AS and a client in AS 2 is retrieving a file from one
of these mirror servers, the client should select a mirror server in
AS 3 to reduce transit charge for both the client-side and server-
side ASes, but current clients which are unaware to AS relationships
often select other servers.
Moreover, on P2P overlay networks, the connectivity 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 the problem of the cross-domain traffic in
terms of transit cost as well as congestion in intra-domain networks.
2.2. Cross-Domain Cooperation
+------+ 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
Asai, et al. Expires December 17, 2010 [Page 6]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
The ALTO Working Group has worked on application-layer traffic
optimization, and it has proposed a protocol to provide end-to-end
cost between peers [I-D.ietf-alto-protocol]. Cost computation of
this protocol is based on P4P [Xie08] which is an oracle-based
approach of application-layer traffic optimization and has achieved
the fair utilization of network resources by setting up priorities
which are 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 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 achieve AS relationships-aware overlay routing, applications
should take into account AS relationships or charging policies among
ASes. So, cross-domain cost is required to be unveiled or estimated,
and provided. The ALTO protocol [I-D.ietf-alto-protocol] provides
end-to-end cost based on P4P [Xie08], but it does not mention how to
cooperate with each AS.
Interconnections between ASes are established by commercial
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 of cross-domain
cooperation described in Section 2.2 still exists.
Asai, et al. Expires December 17, 2010 [Page 7]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
2.4. Problems with the ALTO Approach
+-------------+-----------------------------------------------------+
| | Problems |
+-------------+-----------------------------------------------------+
| Cooperation | Require to set coordinated cost onto inter-AS |
| | links, but each AS is autonomously operated |
| | |
| Security | Require to exchange the cross-domain cost among |
| | ALTO services, i.e., require to disclose AS |
| | relationships, though AS relationships are |
| | non-disclosure ones |
+-------------+-----------------------------------------------------+
Table 1: Problems with the ALTO approach
We summarize the problems with the ALTO approach in Table 1.
Asai, et al. Expires December 17, 2010 [Page 8]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
3. Solution Approach
This section describes an approach to solve the problems which have
been figured out in Section 2, and the requirements. 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, 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. 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. 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 be implemented. A method for
providing AS path to applications is described in Section 3.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
provide one possible estimation method and the detailed description
follows in Section 3.2.
Cost for a path which would be used for the traffic optimization is
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 3.3.
Asai, et al. Expires December 17, 2010 [Page 9]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
+------------------------+--------------------------+---------------+
| Service | Service provider | Requirement |
| | | level |
+------------------------+--------------------------+---------------+
| * AS path provision | Each AS | RECOMMENDED |
| | | |
| * AS relationships | Volunteer service | REQUIRED |
| estimation | providers etc. | |
| | | |
| * Cost computation | Each application | REQUIRED |
+------------------------+--------------------------+---------------+
Table 2: Requirements
These services and the requirements of this approach are summarized
in Table 2. 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.
3.1. AS Path Provision Service
+--------------+
| Applications |
+--------------+
| ^ <at customer's network>
AS paths request | | AS paths response
(src X, dst Y) | | (AS path from X to Y)
- -- -- -- -- -- | -- | -- -- -- -- -- -- -- -- -- -- -- -- -- -
v | <at ISP>
+---------------------------+
| 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
Asai, et al. Expires December 17, 2010 [Page 10]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
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: A mechanism which enables
applications to discover AS path provision servers is required.
(This document does not define this service discovery protocol.)
o AS path provision service: 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). (This
document does not define the protocol.)
o Filter: AS path provision services can deny some requests by a
filter to hide their information.
3.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 [Asai09].
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
Asai, et al. Expires December 17, 2010 [Page 11]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
estimated from publicly available information. Note that [Asai09]
has improved the accuracy of this estimation.
+--------------+
| Applications |
+--------------+
| ^ <at customer's network>
AS relationships request | | AS relationships response
(AS X, AS Y) | | (AS relationships of X--Y)
- -- -- -- -- -- -- -- -- | -- | -- -- -- -- -- -- -- -- -- -- -
v | <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 [Asai09].
3.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.
+------+ +------+ +------+ +------+
| 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.
Asai, et al. Expires December 17, 2010 [Page 12]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
Figure 5: AS path and a cost computation algorithm
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]. In [Asai10], 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 3.2.
[Asai10] 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 17, 2010 [Page 13]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
4. Discussion
This section discusses the cooperation with the ALTO approach. The
proposed solution approach in this document is applicable only for
cross-domain cost estimation. In another word, The proposed solution
approach does not mention the intra-domain traffic optimization.
This document figured out the problem with the ALTO approach for
cross-domain cost estimation in Section 2. Hence, the proposed
solution approach can be used as a complementary element of the ALTO
approach to compute cross-domain cost.
Asai, et al. Expires December 17, 2010 [Page 14]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
5. IANA Considerations
No need to describe any request regarding number assignment.
Asai, et al. Expires December 17, 2010 [Page 15]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
6. 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 17, 2010 [Page 16]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
7. 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-04 (work in progress), May 2010.
[Asai09] Asai, H. and H. Esaki, "A Methodology for Magnitude-based
Inter-AS Distance Estimation", The Tenth Workshop on
Internet Technology - WIT2009, 2009.
[Asai10] Asai, H. and H. Esaki, "Towards Interdomain Transit
Traffic Reduction in Peer-assisted Content Delivery
Networks", 14th International Telecommunications Network
Strategy and Planning Symposium, 2010 (to appear).
[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/>.
[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
Asai, et al. Expires December 17, 2010 [Page 17]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
conference on Data communication, pp. 351-362, 2008.
Asai, et al. Expires December 17, 2010 [Page 18]
Internet-Draft AS Relationships-aware Overlay Routing June 2010
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 17, 2010 [Page 19]