idnits 2.17.1 draft-asai-cross-domain-overlay-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (June 3, 2012) is 4344 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-27) exists of draft-ietf-alto-protocol-11 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force H. Asai 3 Internet-Draft H. Esaki 4 Intended status: Informational The University of Tokyo 5 Expires: December 5, 2012 T. Momose 6 Cisco Systems 7 June 3, 2012 9 Considerations on the AS-Level Application-Layer Traffic Optimization 10 draft-asai-cross-domain-overlay-04 12 Abstract 14 Overlay routing technologies (a.k.a. peer-to-peer technologies) have 15 been introduced to various distributed systems, such as content 16 delivery networks and live media streaming systems. However, these 17 systems cannot always utilize optimal network resources from the 18 viewpoint of layer 3 network providers and operators of layer 3 19 network providers have difficulties in controlling and optimizing the 20 traffic of these systems because these systems construct their own 21 networks (i.e., overlay networks) over the layer 3 network without 22 taking into account layer 3 network's routing policies. The ALTO 23 Working Group has worked on application-layer traffic optimization to 24 fill the gaps in routing policies between the layer 3 network and 25 overlay networks by providing the underlay network topology and cost 26 information to applications that build overlay networks. However, 27 since ASes are operated under different policies and cost metrics for 28 application-layer traffic optimization are assumed to be autonomously 29 configured by each AS, there are considerations in applying 30 application-layer traffic optimization techniques to cross-domain 31 (inter-AS) traffic. This document summarizes general problems with 32 cross-domain traffic of overlay networks and considerations on the 33 AS-level application-layer traffic optimization from the viewpoint of 34 inter-AS economics. This document also discusses the conceivable 35 approaches to solve the problems and considerations. 37 Status of this Memo 39 This Internet-Draft is submitted in full conformance with the 40 provisions of BCP 78 and BCP 79. 42 Internet-Drafts are working documents of the Internet Engineering 43 Task Force (IETF). Note that other groups may also distribute 44 working documents as Internet-Drafts. The list of current Internet- 45 Drafts is at http://datatracker.ietf.org/drafts/current/. 47 Internet-Drafts are draft documents valid for a maximum of six months 48 and may be updated, replaced, or obsoleted by other documents at any 49 time. It is inappropriate to use Internet-Drafts as reference 50 material or to cite them other than as "work in progress." 52 This Internet-Draft will expire on December 5, 2012. 54 Copyright Notice 56 Copyright (c) 2012 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents 61 (http://trustee.ietf.org/license-info) in effect on the date of 62 publication of this document. Please review these documents 63 carefully, as they describe your rights and restrictions with respect 64 to this document. Code Components extracted from this document must 65 include Simplified BSD License text as described in Section 4.e of 66 the Trust Legal Provisions and are provided without warranty as 67 described in the Simplified BSD License. 69 Table of Contents 71 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 72 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 73 1.1.1. AS Relationships . . . . . . . . . . . . . . . . . . . 5 74 1.1.2. Transit . . . . . . . . . . . . . . . . . . . . . . . 5 75 1.1.3. Peering . . . . . . . . . . . . . . . . . . . . . . . 5 76 1.1.4. Cross-Domain Links and Traffic . . . . . . . . . . . . 5 77 1.1.5. Overlay Network . . . . . . . . . . . . . . . . . . . 5 78 1.2. Requirements Language . . . . . . . . . . . . . . . . . . 5 79 2. Cross-Domain Traffic Optimization Problems and 80 Considerations . . . . . . . . . . . . . . . . . . . . . . . . 6 81 2.1. General Problems with Cross-Domain Traffic of Overlay 82 Networks . . . . . . . . . . . . . . . . . . . . . . . . . 6 83 2.2. Considerations on AS-Level Application-Layer Traffic 84 Optimization . . . . . . . . . . . . . . . . . . . . . . . 8 85 2.2.1. Uneven policy configuration . . . . . . . . . . . . . 9 86 2.2.2. Asymmetric economic policies . . . . . . . . . . . . . 10 87 2.2.3. Uncertain ingress routes . . . . . . . . . . . . . . . 11 88 2.3. Summary of the Problems and Considerations . . . . . . . . 13 89 3. Conceivable Solution Approaches and Discussion . . . . . . . . 14 90 3.1. A1. ALTO servers without interconnection at local ASes . . 14 91 3.2. A2. ALTO servers without interconnection at local and 92 remote ASes . . . . . . . . . . . . . . . . . . . . . . . 15 93 3.3. A3. ALTO servers with mesh interconnection . . . . . . . . 16 94 3.4. A4. ALTO servers with mesh interconnection and reverse 95 path probes . . . . . . . . . . . . . . . . . . . . . . . 17 96 3.5. A5. ALTO servers with hop-by-hop interconnection by 97 using a path vector algorithm . . . . . . . . . . . . . . 18 98 3.6. Summary of the Conceivable Solution Approaches . . . . . . 19 99 3.7. Discussion on uneven policy configuration . . . . . . . . 19 100 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 101 5. Security Considerations . . . . . . . . . . . . . . . . . . . 22 102 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23 103 7. Informative References . . . . . . . . . . . . . . . . . . . . 24 104 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26 106 1. Introduction 108 Many distributed systems, such as content delivery networks (CDNs) 109 and live media streaming systems, have introduced application-layer 110 overlay routing as represented by peer-to-peer technologies for their 111 communication scheme to avoid excessive server load and to achieve 112 effective and high-quality communication (e.g., high throughput, 113 fault tolerance). Today, the traffic generated by these applications 114 using application-layer overlay routing becomes a significant amount 115 of the Internet traffic [RFC5693]. Since these applications 116 construct their own network topology (a.k.a. overlay network) over 117 the Internet, generally without taking into account the layer 3 118 network topology, these applications frequently utilize a larger 119 amount of network resources than layer 3 network providers expect. 120 Moreover, they may utilize a detoured path that is disallowed or 121 unexpected by layer 3 network providers [Ho09]. 123 The ALTO Working Group has worked on application-layer traffic 124 optimization to fill the gaps between the layer 3 network and 125 applications by providing the underlay network topology and cost 126 information to these applications for their overlay network 127 construction. However, there exist considerations on inter-AS policy 128 conflicts when we deploy the AS-level application-layer traffic 129 optimization because ASes are operated under different policies and 130 cost metrics are assumed to be autonomously configured by each AS. 132 This document summarizes general problems with cross-domain 133 (inter-AS) traffic generated by overlay networks and considerations 134 on the AS-level application-layer traffic optimization from the 135 viewpoint of inter-AS economics, which are not discussed 136 in [RFC5693]. The main concerns on the AS-level application-layer 137 traffic optimization are categorized to three groups; 1) uneven 138 policy configuration between distinct layer 3 network domains (i.e., 139 ASes), 2) asymmetric economic policies on transit links, and 3) 140 uncertain ingress routes in BGP routing. The underlying problem 141 inducing these concerns is that the detailed economic policies 142 between interconnected ASes are non-disclosure information due to 143 commercial contracts although these policies are important metrics 144 for inter-AS traffic optimization. This document also discusses the 145 conceivable approaches to solve the problems and considerations. 147 1.1. Terminology 149 We use the following terms in this document. 151 1.1.1. AS Relationships 153 AS relationships represent commercial relationships between 154 interconnected ASes. AS relationships are categorized into two major 155 types: transit and peering. There are typical inter-AS routing 156 policies by each type of AS relationships [Wang03]. 158 1.1.2. Transit 160 Transit is a type of AS relationships, in which a customer AS 161 purchases Internet access from its transit provider(s) over transit 162 link(s) by paying some amount of money according to the actual 163 bandwidth usage. The Transit relationship is also called provider- 164 customer relationship. 166 1.1.3. Peering 168 Peering is a type of AS relationships, in which two peering ASes are 169 equal. Traffic exchanged over peering links is free of charge. 171 1.1.4. Cross-Domain Links and Traffic 173 Domains correspond to ASes in this document. Cross-domain links and 174 traffic denote inter-AS links and traffic, respectively. 176 1.1.5. Overlay Network 178 Overlay networks are constructed by application-layer nodes such as 179 peer-to-peer application nodes over the layer 3 network (i.e., IP 180 network) that is operated by network providers. The topology and 181 routing of an overlay network are controlled by applications that 182 build the overlay network but not by the layer 3 network providers. 184 1.2. Requirements Language 186 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 187 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 188 document are to be interpreted as described in RFC 2119 [RFC2119]. 190 2. Cross-Domain Traffic Optimization Problems and Considerations 192 This section discusses general problems with cross-domain traffic of 193 overlay networks and considerations on the AS-level application-layer 194 traffic optimization in terms of cross-domain traffic and its 195 economics. First, we point out the general problems that the overlay 196 networks do not take into account the layer 3 network economics and 197 routing policies, and consequently, they cannot always utilize 198 optimal network resources from the viewpoint of layer 3 network 199 providers. Then, we present the considerations on the AS-level 200 application-layer traffic optimization that are not discussed well 201 in [RFC5693]. Since ASes are operated under different policies and 202 cost metrics are assumed to be autonomously configured by each AS, 203 the method for intra-domain optimization cannot be directly used and 204 cross-domain concerns, such as uneven policy configuration between 205 distinct ASes, asymmetric policies on transit links, and asymmetric 206 underlay paths, must be solved to achieve the AS-level application- 207 layer traffic optimization. 209 2.1. General Problems with Cross-Domain Traffic of Overlay Networks 211 The Internet consists of thousands of ASes operated by distinct 212 network providers such as commercial ISPs, companies and 213 universities. Each AS generally connects with multiple ASes, and 214 there are distinct charging policies for each inter-AS link. These 215 charging policies are roughly categorized into two major types of 216 relationships; transit (with charge) and peering (without any 217 charge). From the economic viewpoint, network providers want to 218 reduce the traffic volume exchanged with transit providers as much as 219 possible, and consequently, they manage BGP routing policies as 220 explained in [Wang03]. Thus, the layer 3 paths are determined by 221 network providers as intended. 223 However, overlay networks are not sometimes aware of these routing 224 policies and generate more expensive cross-domain traffic. On the 225 other hand, network providers cannot optimize the cross-domain 226 traffic generated by applications on overlay networks. This is 227 because the traffic is controlled by a set of application-specific 228 algorithms that determines the overlay network topology and traffic 229 delivery paths, such as peer, neighbor, or path selection algorithms. 231 +------+ provider 232 | AS 1 |----------------------+ 233 provider +------+ | transit 234 | transit | 235 v v 236 customer +------+ peering +------+ +------+ customer 237 | AS 2 |<------->| AS 3 | | AS 4 | 238 +------+ +------+ +------+ 240 AS 2 purchases Internet access from AS 1 via a transit link. On the 241 contrary, the link between AS 2 and AS 3 is peering, which is a lower 242 cost link from the viewpoint of AS 2 network operators. 244 Figure 1: An example of AS-level topology with AS relationships 246 We show an example of the problem with the unawareness of the layer 3 247 network economics and cross-domain traffic generated by overlay 248 networks. An example of interconnections of ASes and their 249 relationships is shown in Figure 1. Suppose remote nodes of a peer- 250 to-peer content delivery network that provide a certain content file 251 exist in both AS 3 and AS 4, and a local node that downloads the file 252 in AS 2 is to retrieve the file from one of these remote nodes, a 253 remote node in AS 3 should be selected to reduce transit charge for 254 both ASes of the local node and the remote node, but today's peer-to- 255 peer content delivery networks that are unaware of AS relationships 256 often select other remote nodes. 258 Thus, overlay networks cannot always utilize optimal network 259 resources but high-cost ones (i.e., transit links from/to transit 260 providers) from the economic viewpoint of network providers. 261 Moreover, especially on peer-to-peer overlay networks, the 262 connectivity of most of end-point nodes (i.e., peers) is provided by 263 residential ISPs, and most of residential ISPs are not transit 264 providers but transit customers, and consequently, it is 265 significantly important to control the transit traffic not to 266 increase their charge to their providers though these kinds of 267 application-layer traffic are hardly controlled by network providers. 268 [RFC5693] also claims this problem with cross-domain traffic in terms 269 of transit cost as well as congestion in intra-domain networks. 271 +------+ provider 272 | AS 1 |-----------------------------+ 273 provider +------+ | transit 274 | transit | 275 v v 276 customer +------+ peering +------+ peering +------+ customer 277 | AS 2 |<------->| AS 3 |<------->| AS 4 | 278 +------+ +------+ +------+ 279 Node <=========> Node <=========> Node 280 detoured path 282 According to the typical BGP routing policies, the path from AS 2 to 283 AS 4 is to be AS 2->AS 1->AS 4. The path AS 2->AS 3->AS 4 is not 284 usually allowed because AS 3 relays traffic from AS 2 to AS 4 without 285 any charge if this path is allowed. 287 Figure 2: An example of AS-level detouring by overlay networks 289 Another problem with overlay networks is that overlay networks may 290 create a detoured path that is disallowed or unexpected by layer 3 291 network providers [Ho09]. For example, in Figure 2, the traffic from 292 AS 2 to AS 4 can pass through AS 3 if a node of an overlay network 293 exists in AS 3 and relays the traffic, but this is usually disallowed 294 by the routing policy of AS 3 to avoid free-riding. 296 In summary, overlay networks have following problems from the cross- 297 domain economic viewpoint of network providers. 299 o Overlay networks usually do not take into account the layer 3 300 network economics to construct their network topology and to 301 exchange traffic between end-point nodes. Therefore, they cannot 302 always utilize optimal cross-domain network resources from the 303 economic viewpoint of network providers. 305 o Overlay networks may enable AS-level traffic detouring that is 306 disallowed by the layer 3 network routing policies. This problem 307 possibly increases transit expenses or induces free-riding. 309 2.2. Considerations on AS-Level Application-Layer Traffic Optimization 311 The ALTO Working Group has worked on application-layer traffic 312 optimization to fill the gaps in routing policies between the layer 3 313 network and overlay networks. It has worked on solving the problems 314 stated in [RFC5693], but [RFC5693] misses some considerations on the 315 AS-level (cross-domain) application-layer traffic optimization. We 316 summarize the missing considerations as follows. 318 o Uneven policy configuration between distinct administrative 319 domains: ASes hardly cooperate with each other in fairly 320 regulating uneven policies of distinct ASes because each AS 321 operates its network under its own policy and inter-AS policies 322 are complicated to achieve total optimization. 324 o Asymmetric economic policies on transit links: It is difficult to 325 regulate the asymmetric economic policies on transit links because 326 transit customers' policies run counter to transit providers; 327 i.e., customers want to reduce the traffic exchanged with their 328 providers to reduce their expense though providers want to 329 increase the traffic exchanged with their customers to increase 330 their income. 332 o Uncertain ingress routes in BGP routing: In addition to the 333 asymmetric economic policies on transit links, the policy-based 334 routing of BGP often creates asymmetric paths. Local ASes hold 335 their egress routes (i.e., next hop AS for a remote end-point 336 node), but they do not know ingress routes (i.e., previous hop AS 337 from a remote end-point node). Therefore, it is difficult to 338 configure ingress cost for remote end-point nodes/networks because 339 the layer 3 network providers do not have the ingress routes to 340 determine which AS becomes the previous hop for the remote end- 341 point nodes/networks. 343 The details of these considerations are described in the following 344 sections. 346 2.2.1. Uneven policy configuration 348 The ALTO Working Group has proposed a protocol to distribute end-to- 349 end network cost between peers to 350 applications [I-D.ietf-alto-protocol]. This protocol does not intend 351 to define the cost computation algorithm, but it assumes that the 352 cost is computed by network providers. Two oracle-based cost 353 computation algorithms, [Aggarwal07] and [Xie08], have been proposed 354 and evaluated in the research area. [Aggarwal07] computes the AS- 355 level cost according to AS hop count between two end-point nodes. 356 So, it ignores the information on AS relationships (i.e., transit 357 cost). [Xie08] computes the AS-level cost according to the 358 configured parameters (e.g., `local preference' in BGP) in routers. 359 This takes into account AS relationships. However, there is a 360 problem with this algorithm when it is applied to the real Internet. 361 Charging policies for exchanged inter-AS traffic volume are so 362 complicated that different ASes hardly cooperate with each other in 363 computing and fairly balancing cost. Even in the BGP routing managed 364 by network providers, the hot potato problem stated in [RFC4277] 365 shows the difficulty in regulating policies of distinct ASes. 367 +------+ provider 368 | AS 1 |----------------------+ 369 provider +------+ 3 | transit 370 5 | transit (1$/Mbps) | (2$/Mbps) 371 30 v v 10 372 customer +------+ +------+ customer 373 | AS 2 | | AS 3 | 374 +------+ +------+ 376 Each number represents egress cost. Transit charge on each transit 377 link is noted in a set of parentheses. 379 Figure 3: An example of uneven cost configuration 381 For example, suppose egress cost of each inter-AS link is configured 382 autonomously (i.e., each AS sets cost according to its own policies) 383 as shown in Figure 3, then the cost of the path from AS 2 to AS 1 384 becomes larger than that of the path from AS 3 to AS 1 though the 385 path from AS 2 to AS 1 seems to be a cheaper link than the other. 386 Thus, oracle-based approaches are exposed to a fairness or evenness 387 issue among multiple autonomous domains. 389 In summary, inter-AS policies are so complex that ASes cooperate with 390 each other in fairly regulating policies of distinct ASes in terms of 391 cross-domain cost configuration. 393 2.2.2. Asymmetric economic policies 395 There is a difficulty in regulating the asymmetric economic policies 396 on inter-AS links, especially between transit customers and 397 providers. One of the causes of this difficulty is same as that of 398 the issue on the uneven policy configuration; i.e., because each AS 399 configures its own desired policy. Another cause of this difficulty 400 is that the policies on the transit links are not symmetric. So, one 401 party's policy does not match the other's. The same asymmetric 402 nature is also found in the BGP routing, but the policy regulation on 403 transit links becomes more complex in the overlay routing than the 404 BGP routing. This is because overlay network nodes that have the 405 same functionality or contents possibly exist in multiple ASes while 406 the functionality (i.e., end-to-end connectivity to the destination) 407 of the BGP routing is mapped to a single AS. The BGP path-vector 408 routing is performed under the control of the layer 3 network 409 providers by route import and export policies, and consequently, the 410 computed paths in the BGP routing are based on the benefit principle. 411 However, the overlay routing might destroy the control and the 412 principle. 414 +------+ 415 | AS 1 | Remote node 416 provider +------+ ^ 417 5 | transit | Good for AS 1 418 30 v | Not good for AS 2 419 customer +------+ v 420 | AS 2 | Local node 421 provider +------+ ^ 422 5 | transit | Good for AS 2 423 30 v | Not good for AS 3 424 customer +------+ v 425 | AS 3 | Remote node 426 +------+ 428 Each number in this figure represents cost. Note that cost for each 429 type of AS relationships is already simplified and regulated here; 5 430 for provider to customer and 30 for customer to provider. This 431 asymmetric cost regulation follows the typical import policy in the 432 BGP routing (i.e., local preference) although it is quite difficult 433 to achieve this regulation between distinct ASes. 435 Figure 4: An example of asymmetric cost configuration 437 For example, suppose the cost of each inter-AS link configured as 438 shown in Figure 4 is egress cost, then the end-to-end cost from AS 1 439 to AS 2 becomes smaller than that from AS 3 to AS 2. On the other 440 hand, suppose the cost of each inter-AS link configured as shown in 441 Figure 4 is ingress cost, then the end-to-end cost from AS 1 to AS 2 442 becomes larger than that from AS 3 to AS 2. This means that the path 443 from AS 3 to AS 2 is preferred than the other from the viewpoint of 444 AS 2 but the path from AS 1 to AS 2 is preferred than the other from 445 the viewpoint of AS 1 and AS 3. Unlike the BGP routing, overlay 446 networks may have the same functionality or contents at their nodes 447 both in AS 1 and AS 3, and consequently, it is required to consider 448 the conflicts of asymmetric economic policies on transit links 449 between multiple ASes. 451 In summary, the existence of identical functionality at multiple ASes 452 in overlay networks raises the problem with asymmetric economic 453 policies on transit links. 455 2.2.3. Uncertain ingress routes 457 In case that cost between end-point nodes or networks is configured 458 by each AS, underlay paths must also be considered to compute the 459 cost. Since local ASes hold their egress routes (i.e., next hop AS 460 for a remote end-point node/network), egress cost can be configured 461 by looking at the cost of the link to the next hop AS. However, 462 ingress cost is difficult to be computed because local ASes do not 463 have ingress routes to determine which AS becomes the previous hop 464 for a remote end-point node/network. Note that the ingress routes 465 are difficult to be expected from the egress routes because the 466 policy-based routing of BGP often creates asymmetric paths. BGP 467 operators usually work on traffic engineering with reactive methods 468 for the ingress traffic. 470 provider +------+ provider 471 +------| AS 1 |------------------+ 472 transit | +------+ | transit 473 v | 474 customer +------+ peering +------+ | 475 | AS 2 |<------->| AS 3 | | 476 +------+ +------+ provider | 477 Routing table @AS 2 transit | | 478 +--------------------+ v | 479 | Destination | Next | +------+ customer | 480 +--------------------+ | AS 4 | | 481 | AS 1 | AS 1 | +------+ provider | 482 | AS 3, 4, 5 | AS 3 | transit | | 483 +--------------------+ | +------------+ 484 v v 485 Routing table @AS 5 +------+ customer 486 +--------------------+ | AS 5 | 487 | Destination | Next | +------+ 488 +--------------------+ 489 | AS 1, 2 | AS 1 | 490 | AS 3, 4 | AS 4 | 491 +--------------------+ 493 The underlay path between AS 2 and AS 5 is asymmetric. From AS 2 to 494 AS 5, the path goes through AS 3 and AS 4 as the routes from peering 495 are generally preferred to those from transit providers. On the 496 other hand, from AS 5 to AS 2, the path goes through AS 1 as the 497 shortest paths are generally selected as the best when both exits are 498 transit. Routing tables at AS 2 and AS 5 are also represented in 499 this figure to point out the uncertainness of ingress routes. 501 Figure 5: An example of uncertain ingress routes with asymmetric 502 paths in the BGP routing 504 For example, the BGP routing often creates asymmetric paths as shown 505 in Figure 5. Suppose that AS 2 is the local AS and AS 5 is one of 506 the remote ASes and the network provider of AS 2 tries to configure 507 ingress cost from AS 5, AS 2 holds an egress route to AS 5 that goes 508 to AS 3 over a peering link in its routing table but AS 2 does not 509 have any ingress routes, and consequently, AS 2 cannot determine 510 which AS (AS 1 or AS 3) is the previous hop from AS 5 because the 511 reverse path is determined by routing tables of other ASes. In this 512 figure, the path between AS 2 and AS 5 is asymmetric, and 513 consequently, the next hop AS to AS 5 (AS 3) becomes different from 514 the previous hop AS to AS 5 (AS 1). 516 2.3. Summary of the Problems and Considerations 518 This section summarizes the general problems with cross-domain 519 traffic of overlay networks pointed out in Section 2.1 and 520 considerations on the AS-level application-layer traffic optimization 521 described in Section 2.2. These problems and considerations of 522 overlay networks towards the AS-level application-layer traffic 523 optimization are summarized into the following five categories. 525 o C1. AS relationships unawareness of overlay networks 527 o C2. AS-level detouring by overlay networks 529 o C3. Uneven policy configuration of distinct ASes 531 o C4. Asymmetric economic policy on transit links 533 o C5. Uncertain ingress routes in determining ingress cost 535 3. Conceivable Solution Approaches and Discussion 537 This section discusses the conceivable approaches to solve the 538 problems and considerations, C1 to C5, summarized in Section 2.3. 539 This document does not intend to define specifications and protocols, 540 and consequently, this section shows the overview of each approach to 541 open up further discussion. We assume that the cost or policy 542 information is provided to applications via ALTO servers defined in 543 [RFC5693]. The conceivable solution approaches are listed as 544 follows. 546 o A1. ALTO servers without interconnection at local ASes 548 o A2. ALTO servers without interconnection at local and remote ASes 550 o A3. ALTO servers with mesh interconnection 552 o A4. ALTO servers with mesh interconnection and reverse path 553 probes 555 o A5. ALTO servers with hop-by-hop interconnection by using a path 556 vector algorithm 558 The detail and points to be solved of each approach are given in the 559 following sections. 561 3.1. A1. ALTO servers without interconnection at local ASes 563 The simplest way to take into account the AS relationships in overlay 564 networks is that network providers configure cost information for 565 end-point nodes in other ASes as well as end-point nodes in a local 566 AS using ALTO servers. In this approach, a local end-point node 567 discovers and uses ALTO servers in the local AS. . A local AS can 568 configure egress cost for end-point nodes in other ASes to its ALTO 569 servers by looking at its routing table and the inter-AS policy to 570 the next hop AS, but cannot configure ingress cost because of the 571 same reason as C5. The ALTO servers in the local AS do not have 572 ingress and egress cost of remote ASes. 574 This approach does not require new specifications in comparison with 575 intra-domain application-layer traffic optimization. This approach 576 does not completely solve any of C1-C5, but this is ``better than 577 nothing'' for C1. The inter-AS traffic from the local AS to other 578 ASes can be optimized by looking at the egress cost configured in the 579 local AS' ALTO servers. 581 +---------------------------+ +---------------------------+ 582 | Local AS | | Remote AS | 583 | +-------------+ ___ ___ | 584 | | ALTO server | / \ / \ | 585 | +-------------+ | R |===| R | | 586 | * egress cost \___/ \___/ | 587 | | | | 588 | +------------+ | | +-------------+ | 589 | | Local node |>===== Optimized for Local AS ===>| Remote node | | 590 | +------------+ | | +-------------+ | 591 +---------------------------+ +---------------------------+ 593 Figure 6: ALTO servers without interconnection at local ASes 595 The system overview of this approach is shown in Figure 6. 597 3.2. A2. ALTO servers without interconnection at local and remote ASes 599 To extend the optimization to remote ASes from A1, a local end-point 600 node can look up ALTO servers in remote ASes in addition to those in 601 the local AS. In this approach, a local end-point node discovers and 602 uses ALTO servers both in the local and remote ASes. Both local and 603 remote ASes can configure their egress cost by the same way as A1. 605 This approach requires a new specification, in comparison with intra- 606 domain application-layer traffic optimization, to discover ALTO 607 servers in remote ASes. To simplify the specification and the 608 discovery procedure, this discovery may be proxied by remote end- 609 point nodes. This approach does not completely solve any of C1-C5, 610 but this is also ``better than nothing'' and better than A1 for C1. 611 The inter-AS traffic from a remote AS to other ASes as well as the 612 inter-AS traffic from the local AS to other ASes can be optimized by 613 looking at the egress cost configured in both ASes' ALTO servers. 615 +---------------------------+ +---------------------------+ 616 | Local AS | | Remote AS | 617 | +-------------+ ___ ___ +-------------+ | 618 | +->| ALTO server | / \ / \ +->| ALTO server | | 619 | | +-------------+ | R |===| R | | +-------------+ | 620 | | * egress cost \___/ \___/ | * egress cost | 621 | | | | | | 622 | | +-------------------------------+ | 623 | | | | | | 624 | +------------+>===== Optimized for Local AS ===>+-------------+ | 625 | | Local node | | | | Remote node | | 626 | +------------+<===== Optimized for Remote AS ==<+-------------+ | 627 +---------------------------+ +---------------------------+ 629 Figure 7: ALTO servers without interconnection at local and remote 630 ASes 632 The system overview of this approach is shown in Figure 7. 634 3.3. A3. ALTO servers with mesh interconnection 636 A1 and A2 do not completely solve any of C1-C5. Moreover, A2 637 requires a specification to discover ALTO servers of remote ASes. 638 This approach adds a specification to exchange egress cost between 639 ALTO servers of local and remote ASes to provide egress cost of both 640 ASes to overlay networks, instead of the discovery of ALTO servers of 641 remote ASes. The inter-AS traffic from the local AS to others and 642 the inter-AS traffic from a remote AS to other ASes are optimized by 643 this approach. 645 One problem with this approach is scalability that the ALTO servers 646 of the local AS must establish the interconnection with ALTO servers 647 of remote ASes to exchange egress cost configuration. 649 +---------------------------+ +---------------------------+ 650 | Local AS +-- exchange egress cost --+ Remote AS | 651 | | | | | | 652 | v | | v | 653 | +-------------+ ___ ___ +-------------+ | 654 | +->| ALTO server | / \ / \ | ALTO server | | 655 | | +-------------+ | R |===| R | +-------------+ | 656 | | * egress cost \___/ \___/ * egress cost | 657 | | | | | 658 | +------------+>===== Optimized for Local AS ===>+-------------+ | 659 | | Local node | | | | Remote node | | 660 | +------------+<===== Optimized for Remote AS ==<+-------------+ | 661 +---------------------------+ +---------------------------+ 662 Figure 8: ALTO servers with mesh interconnection 664 The system overview of this approach is shown in Figure 8. 666 3.4. A4. ALTO servers with mesh interconnection and reverse path probes 668 Any of A1, A2, and A3 cannot achieve the optimization of ingress 669 inter-AS traffic (i.e., cannot solve C5) because these approaches 670 cannot determine the ingress routes. In this approach, ALTO servers 671 resolve ingress routes with reverse path probes between these 672 interconnected ALTO servers. This approach requires a specification 673 to resolve the ingress routes in addition to A3's specification, 674 which is to exchange egress cost between ALTO servers of local and 675 remote ASes. Thus, this approach provides four types of cost to 676 applications; 1) the ingress cost of a local AS, 2) the egress cost 677 of a local AS, 3) the ingress cost of a remote AS, and 4) the egress 678 cost of a remote AS. Applications can optimize the inter-AS traffic 679 for both local and remote ASes using these four types of cost 680 according to benefit principle; for example, attaching weight to the 681 ingress and egress cost of a local AS and detaching weight on the 682 ingress and egress cost of a remote AS if a end-point node in the 683 remote AS is the beneficiary, vice versa. In summary, this approach 684 solves C1, C4, and C5. Note that this approach has the same 685 scalability problem as A3. 687 +---------------------------+ +---------------------------+ 688 | Local AS +----- exchange cost ------+ Remote AS | 689 | | | | | | 690 | v v | 691 | +-------------+ ___ ___ +-------------+ | 692 | +->| ALTO server | / \ / \ | ALTO server | | 693 | | +-------------+ | R |===| R | +-------------+ | 694 | | * egress cost \___/ \___/ * egress cost | 695 | | * ingress cost | | * ingress cost | 696 | | | | | 697 | +------------+>======= Optimized for both =====>+-------------+ | 698 | | Local node | | | | Remote node | | 699 | +------------+<======= Optimized for both =====<+-------------+ | 700 +---------------------------+ +---------------------------+ 702 Figure 9: ALTO servers with mesh interconnection and reverse path 703 probes 705 The system overview of this approach is shown in Figure 9. 707 3.5. A5. ALTO servers with hop-by-hop interconnection by using a path 708 vector algorithm 710 A1-A4 cannot solve C2 because these simple cost-based approaches have 711 limitations to reflect inter-AS policies in the BGP routing while BGP 712 is a path-vector routing protocol that is one of policy-based routing 713 protocols. A solution approach to solve C2 is to introduce a path- 714 vector algorithm that propagates policies hop-by-hop between 715 interconnected ALTO servers like the BGP routing, and to provide cost 716 for detoured paths. This approach enables flexible policy 717 propagation, but requires many new specifications, protocols, and 718 algorithms to propagate policies and to compute a cost map that is 719 provided to applications. 721 provider +-------------+ provider 722 transit +-------------| Remote AS 1 |-------------+ transit 723 | | | | 724 | ++===========ALTO Server===========++ | 725 | || +-------------+ || | 726 customer v || || v customer 727 +----------||-+peering+-------------+peering+-||-------------+ 728 | Local AS || |<----->| Remote AS 2 |<----->| || Remote AS 3 | 729 | || | | | | || | 730 | ALTO Server===========ALTO Server===========ALTO Server | 731 +-------------+ +-------------+ +----------------+ 732 <===== Cost/Policy for AS 2 733 <===== Cost/Policy for AS 3 734 <===== Cost/Policy for AS 3 via AS 2 735 (e.g., policy: detouring allowed 736 at small additional cost) 738 Cost map @Local AS 739 +-------------------------------------------------------+ 740 | Source/Destination | Next/Previous | Cost of Local AS | 741 | (Detoured Path) | hop AS (BGP) | Ingress | Egress | 742 +-------------------------------------------------------+ 743 | AS 1 | AS 1 | 20 | 20 | 744 | AS 2 | AS 2 | 10 | 10 | 745 | AS 3 | AS 1 | 40 | 40 | 746 | AS 3 via AS 2 | (AS 2) | 30 | 30 | 747 +-------------------------------------------------------+ 749 Figure 10: ALTO servers with hop-by-hop interconnection by using a 750 path vector algorithm 752 An example of topology and a cost map adopting this approach is shown 753 in Figure 10. ALTO servers of each AS establish interconnection, and 754 then they exchange and propagate policies with each other by a path- 755 vector algorithm. The ALTO server of the local AS then computes a 756 cost map for sources/destinations and detoured paths from all the 757 received policies. Thus, this approach can provide the cost for 758 detoured paths as well as the layer 3 network paths. In this 759 example, the cost of the detoured path from/to AS 3 via AS 2 becomes 760 lower than that of the end-to-end path from/to AS 3 via AS 1. This 761 means that the AS 2 does not disallow the detoured path. If AS 2 762 does not prefer detouring, the cost of the detoured path becomes 763 higher than the others according to the propagated policies. Note 764 that the sources/destination and detoured paths are aggregated by 765 per-AS in this example, but they may be per-prefix. 767 3.6. Summary of the Conceivable Solution Approaches 769 +----------+----+----+----+----+----+ 770 | Approach | C1 | C2 | C3 | C4 | C5 | 771 +----------+----+----+----+----+----+ 772 | A1 | x | | | | | 773 | | | | | | | 774 | A2 | x | | * | | | 775 | | | | | | | 776 | A3 | x | | * | | | 777 | | | | | | | 778 | A4 | x | | * | x | x | 779 | | | | | | | 780 | A5 | x | x | * | x | x | 781 +----------+----+----+----+----+----+ 783 x: Solved or better than nothing; *: Solved or better than nothing 784 with additional methods discussed in Section 3.7 786 Table 1: Summary of the conceivable solution approaches 788 3.7. Discussion on uneven policy configuration 790 Any of A1 A5 do not provide a method to solve C3. This section 791 discusses possible methods to solve C3. We first note that A1 never 792 achieves to solve C3 because it only provides the egress cost from 793 the local AS. The possible methods to solve C3 are listed and 794 summarized as follows. 796 o Global regulation: This method is to define global regulation for 797 cost configuration, and to provide a cost computation function; 798 for example, cost X for X$/Mbps, or more simply cost 2, 1, and 0 799 for transit (from/to provider), peering, and transit (from/to 800 customer), respectively. However, it is not realistic because the 801 inter-AS policy is too complex to define the global regulation. 802 Moreover, the economic policies between interconnected ASes cannot 803 be disclosed by each network provider due to commercial contracts. 805 o Hop-by-hop regulation: In A3 A5, ALTO servers of each AS establish 806 interconnection. In these cases, the interconnected ALTO servers 807 can introduce a regulation algorithm for the exchanged cost. The 808 cost will be regulated among interconnected ALTO servers and this 809 might be ``better than nothing'', but C3 still exists among ALTO 810 servers that are not interconnected. 812 o Inference-based regulation: AS relationships inference can be one 813 of the methods to regulate the complex economic policies. This is 814 an alternative to the global regulation method to solve the 815 problem with non-disclosure AS relationships. AS relationships 816 inference algorithms have been proposed in the research field, 817 such as [Asai10], [Dimitropoulos07], and [Gao01]. Global 818 regulation is achieved by using these inference algorithms. The 819 inferred AS relationships for some links may not be accurate, but 820 this might also be ``better than nothing''. 822 In summary, within the interconnected ALTO servers, the hop-by-hop 823 regulation is the best. The inference-based regulation can be used 824 to assist in regulating uneven policy configuration in the other 825 cases or finding anomalous cost configurations. 827 4. IANA Considerations 829 No need to describe any request regarding number assignment. 831 5. Security Considerations 833 This document is neither a requirements document nor a protocol 834 specification. However, since the solution approaches exchange the 835 inter-AS economic policies with ALTO servers operated by other ASes 836 (i.e., external network domains), two security considerations are 837 discussed as follows. 839 o The ALTO servers operated by other ASes may falsify the received 840 cost map or policies. The protocol specifications of the solution 841 approaches must include anti-falsification and verification 842 mechanisms (e.g., digital signing) for the exchanged cost map or 843 policies. 845 o The exchanged cost map or policies may contain the non-disclosure 846 inter-AS information. The protocol specifications of the solution 847 approaches should consider the schemes to aggregate and filter the 848 exchanged cost map or policies in order not to reveal the non- 849 disclosure information. 851 6. Acknowledgements 853 Moritz Steiner (Bell-Labs), Piotr Wydrych (AGH University of Science 854 and Technology), Russ White (Cisco Systems), Stefano Previdi (Cisco 855 Systems), Volker Hilt (Alcatel-Lucent Bell-Labs), and many others 856 provided informative discussions and valuable comments. 858 7. Informative References 860 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 861 Requirement Levels", BCP 14, RFC 2119, March 1997. 863 [RFC4277] McPherson, D. and K. Patel, "Experience with the BGP-4 864 Protocol", RFC 4277, January 2006. 866 [RFC5693] Seedorf, J. and E. Burger, "Application-Layer Traffic 867 Optimization (ALTO) Problem Statement", RFC 5693, 868 October 2009. 870 [I-D.ietf-alto-protocol] 871 Alimi, R., Penno, R., and Y. Yang, "ALTO Protocol", 872 draft-ietf-alto-protocol-11 (work in progress), 873 March 2012. 875 [Aggarwal07] 876 Aggarwal, V., Feldmann, A., and C. Scheideler, "Can ISPs 877 and P2P users cooperate for improved performance?", 878 SIGCOMM Comput. Commun. Rev., vol. 37, no. 3, pp. 29-40, 879 2007. 881 [Asai10] Asai, H. and H. Esaki, "Estimating AS Relationships for 882 Application-Layer Traffic Optimization", 3rd Workshop on 883 Economic Traffic Management, LNCS Vol. 6236, pp. 51-63, 884 2010. 886 [Dimitropoulos07] 887 Dimitropoulos, X., Krioukov, D., Fomenkov, M., Huffaker, 888 B., Hyun, Y., claffy, k., and G. Riley, "AS Relationships: 889 Inference and Validation", ACM SIGCOMM Comput. Commun. 890 Rev., Vol. 37, No. 1, pp. 29-40, 2001. 892 [Gao01] Gao, L., "On inferring autonomous system relationships in 893 the Internet", IEEE/ACM Transactions on Networking, 894 Vol. 9, No. 6, pp. 733-745, 2001. 896 [Ho09] Ho, Haddow, T., Ledlie, J., Draief, D., and P. Pietzuch, 897 "Deconstructing internet paths: an approach for AS-level 898 detour route discovery", Proceedings of the 8th 899 international conference on Peer-to-peer systems, p. 6, 900 2009. 902 [Wang03] Wang, F. and L. Gao, "On Inferring and Characterizing 903 Internet Routing Policies", IMC '03: Proceedings of the 904 3rd ACM SIGCOMM conference on Internet measurement, 905 pp. 15-26, 2003. 907 [Xie08] Xie, H., Yang, Krishnamurthy, A., Liu, and A. 908 Silberschatz, "P4P: provider portal for applications", 909 SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 910 conference on Data communication, pp. 351-362, 2008. 912 Authors' Addresses 914 Hirochika Asai 915 The University of Tokyo 916 7-3-1 Hongo 917 Bunkyo-ku, Tokyo 113-8656 918 JP 920 Phone: +81 3 5841 6748 921 Email: panda@hongo.wide.ad.jp 923 Hiroshi Esaki 924 The University of Tokyo 925 7-3-1 Hongo 926 Bunkyo-ku, Tokyo 113-8656 927 JP 929 Phone: +81 3 5841 6748 930 Email: hiroshi@wide.ad.jp 932 Tsuyoshi Momose 933 Cisco Systems G.K. 934 2-1-1 Nishi-Shinjuku 935 Shinjuku-ku, Tokyo 163-0409 936 JP 938 Phone: +81 3 5324 4154 939 Email: tmomose@cisco.com