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]