idnits 2.17.1 draft-xiang-alto-multidomain-analytics-03.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 == Line 592 has weird spacing: '...Queries v |...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (March 8, 2020) is 1510 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '11' on line 783 -- Looks like a reference, but probably isn't: '49' on line 783 -- Looks like a reference, but probably isn't: '95' on line 785 -- Looks like a reference, but probably isn't: '34' on line 783 -- Looks like a reference, but probably isn't: '58' on line 784 -- Looks like a reference, but probably isn't: '22' on line 784 -- Looks like a reference, but probably isn't: '75' on line 784 -- Looks like a reference, but probably isn't: '25' on line 784 -- Looks like a reference, but probably isn't: '50' on line 785 -- Looks like a reference, but probably isn't: '69' on line 785 -- Looks like a reference, but probably isn't: '89' on line 785 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ALTO WG Q. Xiang 3 Internet-Draft Yale University 4 Intended status: Informational J. Zhang 5 Expires: September 9, 2020 Tongji/Yale University 6 F. Le 7 IBM 8 Y. Yang 9 Yale University 10 H. Newman 11 California Institute of Technology 12 March 8, 2020 14 Resource Orchestration for Multi-Domain, Exascale, Geo-Distributed Data 15 Analytics 16 draft-xiang-alto-multidomain-analytics-03.txt 18 Abstract 20 As the data volume increases exponentially over time, data analytics 21 is transiting from a single-domain network to a multi-domain, geo- 22 distributed network, where different member networks contribute 23 various resources, e.g., computation, storage and networking 24 resources, to collaboratively collect, share and analyze extremely 25 large amounts of data. Such a network calls for a resource 26 orchestration framework that emphasizes the performance 27 predictability of data analytics jobs, the high utilization of 28 resources, and the autonomy and privacy of member networks. 30 This document presents the design of Unicorn, a unified resource 31 orchestration framework for multi-domain, geo-distributed data 32 analytics, which uses the Application-Layer Traffic Optimization 33 (ALTO) protocol as the key component for (1) allows member networks 34 to provide accurate information on different types of resources; (2) 35 keeps the private information of member networks; and (3) allows data 36 analytics jobs to accurately describe their requirements of different 37 types of resources. As a part of Unicorn, an ALTO extension for 38 privacy-preserving interdomain information aggregation is also 39 presented. 41 Status of This Memo 43 This Internet-Draft is submitted in full conformance with the 44 provisions of BCP 78 and BCP 79. 46 Internet-Drafts are working documents of the Internet Engineering 47 Task Force (IETF). Note that other groups may also distribute 48 working documents as Internet-Drafts. The list of current Internet- 49 Drafts is at https://datatracker.ietf.org/drafts/current/. 51 Internet-Drafts are draft documents valid for a maximum of six months 52 and may be updated, replaced, or obsoleted by other documents at any 53 time. It is inappropriate to use Internet-Drafts as reference 54 material or to cite them other than as "work in progress." 56 This Internet-Draft will expire on September 9, 2020. 58 Copyright Notice 60 Copyright (c) 2020 IETF Trust and the persons identified as the 61 document authors. All rights reserved. 63 This document is subject to BCP 78 and the IETF Trust's Legal 64 Provisions Relating to IETF Documents 65 (https://trustee.ietf.org/license-info) in effect on the date of 66 publication of this document. Please review these documents 67 carefully, as they describe your rights and restrictions with respect 68 to this document. Code Components extracted from this document must 69 include Simplified BSD License text as described in Section 4.e of 70 the Trust Legal Provisions and are provided without warranty as 71 described in the Simplified BSD License. 73 Table of Contents 75 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 76 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 4 77 3. Changes Since Version -02 . . . . . . . . . . . . . . . . . . 4 78 4. Characteristics of Multi-Domain, Geo-Distributed Data 79 Analytics . . . . . . . . . . . . . . . . . . . . . . . . . . 4 80 4.1. Dynamic Data Analytics Workload . . . . . . . . . . . . . 4 81 4.2. Dynamic Resource Availability . . . . . . . . . . . . . . 5 82 5. Design Requirements . . . . . . . . . . . . . . . . . . . . . 6 83 6. Review of Resource Orchestration Designs for Data Analytics . 6 84 6.1. Centralized resource-graph-based orchestration . . . . . 7 85 6.2. Centralized ClassAds-based orchestration . . . . . . . . 7 86 6.3. Distributed opportunistic orchestration . . . . . . . . . 7 87 6.4. Inadequacy of Existing Designs for Multi-Domain, Geo- 88 Distributed Data Analytics . . . . . . . . . . . . . . . 7 89 7. Unicorn Design . . . . . . . . . . . . . . . . . . . . . . . 8 90 7.1. Choosing ALTO as the Resource Information Model . . . . . 8 91 7.2. Architecture of Unicorn . . . . . . . . . . . . . . . . . 9 92 7.2.1. Three-Phase Resource Discovery . . . . . . . . . . . 11 93 7.2.2. Proactive Full-Mesh Resource Discovery . . . . . . . 15 94 7.3. Example . . . . . . . . . . . . . . . . . . . . . . . . . 15 95 8. ALTO Extension: Privacy-Preserving Interdomain Information 96 Aggregation for Resource Discovery . . . . . . . . . . . . . 16 97 8.1. Extension Specification . . . . . . . . . . . . . . . . . 16 98 8.2. Example . . . . . . . . . . . . . . . . . . . . . . . . . 18 99 9. Implementation and Demonstration Experience . . . . . . . . . 19 100 10. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 19 101 10.1. Discovering the Domain-Paths Using a New Interdomain 102 Routing Protocol . . . . . . . . . . . . . . . . . . . . 19 103 10.2. Comparison of the Efficiency to Achieve Optimal Resource 104 Orchestration using ALTO and without using ALTO . . . . 20 105 11. Security Considerations . . . . . . . . . . . . . . . . . . . 20 106 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 107 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 108 13.1. Normative References . . . . . . . . . . . . . . . . . . 20 109 13.2. Informative References . . . . . . . . . . . . . . . . . 21 110 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 112 1. Introduction 114 This document describes the design of Unicorn, a unified resource 115 orchestration framework for large-scale data analytics in multi- 116 domain, geo-distributed networks. An important use case for such 117 settings is the Large Hadron Collider (LHC) network, which consists 118 of over 180 member networks all over the world, to support scientists 119 to access multiple resources, e.g., computing, storage and networking 120 resources, distributed in the member networks to conduct large-scale 121 data analytics. With more and more data being generated and stored 122 in different geo-distributed member networks, network architects and 123 administrators are exploring different designs for efficient resource 124 orchestration in multi-domain, geo-distributed networks. 126 The design presented in this document is based on the development and 127 deployment experience of Unicorn in the CMS network, one of the 128 largest scientific experiments in the LHC network. The primary 129 requirements of resource orchestration in such a multi-domain, geo- 130 distributed environment are the performance predictability of various 131 data analytics jobs, the high utilization of different types of 132 resources, and the autonomy and privacy of resource owners, i.e., 133 member networks. 135 Pre-production development and extensive testing have shown that the 136 Application-Layer Traffic Optimization Protocol [RFC7285] is well 137 suited as a fundamental component in Unicorn for providing a generic 138 representation that (1) allows different types of data analytics jobs 139 to accurately describe their resource requirements and (2) allows 140 member networks to provide accurate information on different types of 141 resources they own and at the same time maintain their privacies. 142 This is in contrast with the state-of-the-art resource orchestration 143 frameworks, such as HTCondor and Mesos, which either do not provide 144 accurate networking information or expose all the private details of 145 member networks. This document elaborates on the design requirements 146 of resource orchestration in multi-domain, geo-distributed networks 147 that lead to this design choice and presents the details of Unicorn, 148 including an ALTO extension for privacy-preserving, interdomain 149 information aggregation. 151 This document first gives an overview of the characteristics of 152 multi-domain, geo-distributed data analytics. Then, the design 153 requirements for resource orchestration under such settings are 154 summarized. After reviewing existing designs and their limitations, 155 this document gives the arguments for using ALTO as the generic 156 representation for describing both resource requirements and the 157 resource information and describes the design details of Unicorn. 158 Finally, a privacy-preserving, interdomain extension of ALTO is 159 presented. 161 2. Requirements Language 163 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 164 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 165 document are to be interpreted as described in [RFC2119]. 167 3. Changes Since Version -02 169 o Add the comparison of the efficiency to achieve optimal resource 170 orchestration using ALTO and without using ALTO in Section 10.2. 172 o Add the pre-production demonstration and deployment experience at 173 the CMS network in Section 9. 175 4. Characteristics of Multi-Domain, Geo-Distributed Data Analytics 177 This section describes the characteristics of multi-domain, geo- 178 distributed data analytics. 180 4.1. Dynamic Data Analytics Workload 182 In multi-domain, geo-distributed data analytics, extremely large 183 amounts of data are generated and stored across different member 184 networks. Authorized users from different organizations can access 185 data and resources in member networks to conduct various data 186 analytics jobs using various data analytics applications. 188 An data analytics application usually provides an automated process 189 that decomposes a large data analytics job into a set of smaller 190 tasks, whose dependencies are expressed as a directed acyclic graph 191 (DAG). Tasks without any dependency can be executed in parallel to 192 improve the efficiency of the data analytics job they belong to. 193 This decomposition is highly user- and application-dependent. 195 Each task may have different requirements on different resources. 196 For instance, task T1 may require dataset A in storage node X as 197 input and 1 CPU as the computing resource, while task T2 may require 198 dataset B in storage node Y as input and 2 CPUs as the computing 199 resource. Furthermore, each task may require resources from 200 different member networks. In the previous example, T1 may require 201 its output to be stored in a storage node in another member network 202 for the purpose of secure storage. The resource requirements of 203 tasks are highly user- and application-dependent. 205 From the above description, it is observed that the workload of 206 multi-domain, geo-distributed data analytics is highly dynamic, in 207 terms of the number of users, the types of applications, the number 208 of jobs, the decomposition of jobs and the resource requirements of 209 tasks. 211 Though with such dynamism, it is the general consensus of users to 212 expect performance predictability of their analytics jobs (TODO: add 213 Mogul citation). Hence the resource orchestration for multi-domain, 214 geo-distributed data analytics must be able to achieve efficient 215 resource sharing among different data analytics jobs of different 216 applications from different users. To this end, a generic 217 representation of resource requirements for different tasks from 218 different analytics applications must be chosen. Furthermore, to 219 ensure maximal deployment, the resource orchestration framework must 220 be independent of and compatible with data analytics applications. 222 4.2. Dynamic Resource Availability 224 In the multi-domain, geo-distributed data analytics network, 225 different member networks belong to different administrative domains. 226 Each member network has its own resource management policies and can 227 choose to use different management software, such as HTCondor and 228 Mesos. 230 Each member network provides different types of resources with 231 different amounts. For example, transit networks such as ESNet and 232 Internet2 provide high-bandwidth networking resources. In contrast, 233 campus science networks provide abundant computation and storage 234 resources, but may provide limited networking bandwidths. And some 235 smaller science networks only provide limited computation and storage 236 resources. The availability of the resources in each member network 237 is subject to the autonomous control of the member network. 239 Furthermore, member networks are interconnected with high bandwidth- 240 delay-product links, where state-of-the-art networking resource 241 allocation mechanisms, such as TCP, become inefficient [XCP]. 243 From the above description, it is observed that the resource 244 availability of the multi-domain, geo-distributed data analytics 245 network is also highly dynamic, subject to the types of member 246 networks, the resources provided by member networks and the resource 247 management policies and management software used by member networks. 249 Though with such dynamism, it is the general consensus of member 250 networks that the resource orchestration for multi-domain, geo- 251 distributed data analytics must achieve high utilization of different 252 types of resources, following the autonomy and privacy of each member 253 network. To this end, a generic representation of resource 254 availabilities for different types of resources must be chosen. Such 255 a representation must be accurate and at the same time maintain the 256 privacy of member networks. Furthermore, to ensure maximal 257 deployment, the resource orchestration framework must be independent 258 of and compatible with the resource management systems used by member 259 networks. 261 5. Design Requirements 263 This section summarizes the design requirements for resource 264 orchestration for multi-domain, geo-distributed data analytics from 265 the previous section. 267 o REQ1: Provide performance predictability for data analytics jobs. 269 o REQ2: Achieve the efficient resource sharing among data analytics 270 jobs. 272 o REQ3: Achieve the high utilization of different types of resources 273 in member networks. 275 o REQ4: Maintain the autonomy and privacy of member networks. 277 o REQ5: Provide compatibility with different data analytics 278 applications and resource management systems to maximize the 279 deployment. 281 6. Review of Resource Orchestration Designs for Data Analytics 283 This section provides an overview of three general types of resource 284 orchestration designs for data analytics -- the centralized resource- 285 graph-based orchestration, the centralized ClassAds-based 286 orchestration and the distributed opportunistic orchestration. Then, 287 the key reason why these designs are inadequate for multi-domain, 288 geo-distributed data analytics is provided. 290 6.1. Centralized resource-graph-based orchestration 292 Systems such as Mesos [Mesos] and Borg [Borg] adopt a graph-based 293 abstraction to represent the resource availability of computing 294 clusters. Each node in the graph is a physical node representing 295 computation or storage resources and each edge between a pair of 296 nodes denotes the networking resource connecting two physical nodes. 297 This design is inadequate for multi-domain, geo-distributed data 298 analytics system because (1) it compromises the privacy of different 299 member networks by revealing all the details of resources; and (2) 300 the overhead to keep the resource availability graph up to date is 301 too expensive due to the heterogeneity and dynamicity of resources 302 from different member networks. 304 6.2. Centralized ClassAds-based orchestration 306 HTCondor [HTCondor] proposes a ClassAds programming model, which 307 allows different resource owners to advertise their resource supply 308 and the job owners to advertise the resource demand. However, this 309 programming model does not support the accurate discovery of 310 networking resources, but leave the orchestration of networking 311 resources completely to TCP, which has been known to behave poorly in 312 networks with high bandwidth-delay products [XCP]. 314 6.3. Distributed opportunistic orchestration 316 Some systems, such as Apollo [Apollo] and Sparrow [Sparrow], use a 317 distributed design. In this design, given a data analytics job, a 318 small number of computing and storage nodes are randomly selected as 319 candidates. Then a scheduling algorithm makes the decision to select 320 the best pair of computing and storage nodes within this small set of 321 candidates. Though it is shown in production that this design 322 achieves a performance very close to the theoretical optimal resource 323 allocation scheme, this design cannot be applied to multi-domain, 324 geo-distributed data analytics because (1) the pool of computing and 325 storage resources is much larger, and is distributed across the 326 world, and (2) it is hard to distributively orchestrate networking 327 resources in such a high bandwidth-delay product scenario. 329 6.4. Inadequacy of Existing Designs for Multi-Domain, Geo-Distributed 330 Data Analytics 332 Applying the designs reviewed in the preceding subsections for multi- 333 domain, geo-distributed data analytics only satisfies the design 334 requirement of compatibility (REQ5), but leaves all the other 335 requirements unfulfilled. The key reason is that they do not have an 336 information model that simultaneously 338 o allows member networks to provide accurate information on 339 different types of resources, e.g., the computing, storage and 340 networking resources, they own; 342 o keeps the private information of member networks, such as physical 343 topologies and policies, from the data analytics applications; and 345 o allows data analytics jobs to accurately describe their 346 requirements of different types of resources. 348 7. Unicorn Design 350 This section presents the design of the Unicorn framework. First, 351 the motivations of using ALTO as the information model of resource 352 orchestration for multi-domain, geo-distributed data analytics are 353 reviewed. Then the architecture of Unicorn is provided. 355 7.1. Choosing ALTO as the Resource Information Model 357 As reviewed in the preceding section, the commonly used resource- 358 graph-based information model and the ClassAds information model do 359 not support the accurate, yet privacy-preserving resource discovery 360 across different member networks. In contrast, the ALTO protocol 361 uses abstract maps of networks to provide network information with 362 the goal of modifying network resource consumption patterns while 363 maintaining or improving application performance [RFC7285]. This 364 document proposes the use of ALTO for providing information of 365 different types of resources, e.g., computing, storage and networking 366 resources. This design has the following advantages: 368 o ALTO provides the network information based on abstract maps of a 369 network. Additional services are built on top of the ALTO 370 abstract maps to provide information of other types of resources, 371 e.g., the computing and storage resources. These maps provide 372 accurate information of different types of resources for the 373 resource orchestration system to effectively utilize them for data 374 analytics applications. For example, the ALTO Endpoint Property 375 Service can provide information of computing nodes and storage 376 nodes. 378 o The ALTO abstract maps provide a simplified view of resources of 379 member networks, instead of the full details of their resource 380 availability. Thus ALTO allows member networks to keep their 381 private information, such as physical topologies and policies, 382 from the applications. For example, the ALTO Network Map service 383 provides a "one-big-switch" view that defines a grouping of 384 network endpoints. This view hides the details of the underlying 385 physical topology of the network and a network deploying the ALTO 386 server has the autonomy to adopt any endpoint grouping algorithm. 388 o ALTO uses a client-server model, in which applications can use 389 ALTO clients to accurately describe their requirements of 390 different types of resources and send these requirements to the 391 ALTO servers to retrieve the accurate information of resources 392 that suit their requirements. For example, the ALTO Multi-Cost 393 service [RFC8189] allows an ALTO client to specify a logic set of 394 tests in a query. Such tests are used by ALTO servers to filter 395 out the information of unqualified resources from the response 396 sent back to the ALTO client. 398 7.2. Architecture of Unicorn 400 This section describes the design details of Unicorn. Figure 1 401 presents the architecture of Unicorn for a multi-domain, geo- 402 distributed data analytics system with N member networks. In 403 particular, Unicorn consists of the following key components: 405 .-------------. .-------------. 406 |Application 1| ... |Application N| 407 '-------------' '-------------' 408 \ / 409 .- - - - - - - -\- - - - - - - - - - - -/- - - - - - - - - - - - - - -. 410 | Unicorn \ / | 411 | .-----------------------. | 412 | | Resource Orchestrator | .----------------------.| 413 | | | |Distributed Hash Table|| 414 | | .-----------. |---- | of Computing and || 415 | | |ALTO Client| | | Storage Resources || 416 | | '-----------' | '----------------------'| 417 | '-----------------------' | 418 | / | \ | 419 | / | \ | 420 | .-------------. .-----------. .-------------. | 421 | |ALTO Server 1| | Execution | |ALTO Server M| | 422 | '-------------' | Agents | '-------------' | 423 | | '-----------' | | 424 | | / \ | | 425 | .----------------./ \ .----------------. | 426 | | Site 1 | . . | Site N | | 427 | '----------------' '----------------' | 428 '- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -' 430 Figure 1: Architecture of Unicorn. 432 o ALTO Server: for each member network, one or more ALTO servers are 433 deployed to provide accurate, yet privacy-preserving information 434 of different types of resources owned by the corresponding 435 network. Examples of such information include the link bandwidth 436 between endpoints, the memory I/O bandwidth and the CPU 437 utilization at computing endpoints and the storage space at 438 storage endpoints. In addition to the basic ALTO services defined 439 in [RFC7285], The ALTO servers in Unicorn also provide ALTO 440 extension services such as the ALTO Multi-Cost Service [RFC8189], 441 the ALTO Server-Sent Event Service [DRAFT-SSE] and the ALTO 442 Multipart Cost Property Service [DRAFT-PV] to provide fine-grained 443 resource information. 445 o Distributed Hash Table (DHT) of Computing and Storage Resources: A 446 DHT system is deployed across member networks to lookup the 447 location of computing and storage resources. Compared with the 448 current centralized lookup services in the CMS network, i.e., 449 PhEDEx and HTCondor, a DHT system provides a significant 450 performance improvement for discovering the locations of computing 451 and storage resources in multi-domain, geo-distributed data 452 analytics systems. 454 o Resource Orchestrator: The orchestrator is a shim layer between 455 the data analytics jobs from different applications and the member 456 networks. It contains an ALTO client that communicates with the 457 ALTO servers at member networks to retrieve resource information. 458 Given a set of data analytics jobs, the orchestrator adopts a 459 three-phase discovery process, which will be elaborated in the 460 next section, to find the accurate information of all the 461 resources that can be used to execute these jobs. Then the 462 orchestrator runs a customized resource allocation algorithm to 463 compute the resource allocation decisions for these jobs, and send 464 the decisions to the execution agents at corresponding member 465 networks. 467 o Execution Agent: One or more execution agents are deployed at each 468 member network. They take the resource allocation decisions from 469 the resource orchestrator, and communicate with the underlying 470 resource management system deployed at the corresponding member 471 network to reserve the resources for the data analytics jobs and 472 execute them. 474 7.2.1. Three-Phase Resource Discovery 476 The preceding subsection describes the architecture and the key 477 components of Unicorn. One missing component is how to accurately 478 discover the information of different types of resources for a set of 479 data analytics jobs with the assistance of ALTO. This section 480 presents the three-phase resource discovery design in Unicorn. 482 7.2.1.1. Phase 1: Endpoint Property Discovery 484 Figure 2 shows the procedure of the endpoint property discovery 485 phase. Given a set of data analytics jobs, the resource orchestrator 486 communicates with the DHT lookup system to find the locations, i.e., 487 the endpoint addresses, of all candidate computing and storage 488 resources. With such information, the ALTO client then issues 489 Endpoint Property Service (EPS) queries to the ALTO servers deployed 490 at member networks to discover the information of all candidate 491 endpoints. 493 .-----------------------. 494 | Resource Orchestrator | Jobs' Resource 495 | | Requirements .------------. 496 | .-----------. | ---------------> | DHT Lookup | 497 | |ALTO Client| | <--------------- | System | 498 | '-----------' | Endpoint '------------' 499 '---------| ^-----------' Locations 500 EPS | | Endpoint 501 Queries | | Properties 502 v | 503 .-------------. 504 |ALTO Servers | 505 '-------------' 507 Figure 2: The Endpoint Property Discovery Phase. 509 7.2.1.2. Phase 2: Endpoint Path Discovery 511 Candidate computing and storage endpoints need to move data between 512 them before, during and after the execution of a data analytics job. 513 In multi-domain, geo-distributed data analytics, a pair of candidate 514 endpoints may not be in the same member network. In this case, the 515 orchestrator needs to find out the connectivity information between 516 such a pair of candidate endpoints. 518 Figure 3 shows the procedure of the endpoint path discovery phase. 519 Given a pair of candidate endpoints that are not in the same member 520 network, the ALTO client in the orchestrator adopts an iterative 521 process to find the interdomain connectivity information for this 522 pair. It starts by issuing an ALTO Endpoint Cost Service query or an 523 ALTO Flow-based Endpoint Cost Service [DRAFT-FCS] to the ALTO server 524 of the member network where the source endpoint locates. The cost 525 type of this query is a customized type called next-hop, with a 526 customized cost mode tuple and a customized cost metric next-network. 528 .-----------------------. 529 | Resource Orchestrator | 530 | | 531 | .-----------. | 532 | |ALTO Client| | 533 | '-----------' | 534 '---------| ^-----------' 535 Customized| | Endpoint 536 ECS | | Path 537 Queries | | Segments 538 v | 539 .-------------. 540 |ALTO Servers | 541 '-------------' 543 Figure 3: The Endpoint Path Discovery Phase. 545 The ALTO server returns a 2-tuple, where the first element is the 546 autonomous number (AS) of the next member network along the AS-path 547 from the source endpoint to the destination endpoint, and the second 548 element is the ingress of this next member network. In a member 549 network, the ALTO server can get such information from the underlying 550 interdomain routing protocol, e.g., BGP. Based on the received 551 response, the ALTO client then issues a similar query to the ALTO 552 server of the next member network. The process stops when the ALTO 553 server of the member network where the destination endpoint locates 554 receives such a query, who will return a null 2-tuple in response to 555 notify the ALTO client. By the end of this process, the ALTO client 556 can assemble a domain-path, in the form of a path vector of (ingress, 557 AS), of this pair of candidate endpoints. 559 7.2.1.3. Phase 3: Resource State Abstraction Discovery 561 After the second phase, the resource orchestrator has the 562 connectivity information of each candidate endpoint pair, i.e., the 563 domain-path. Equivalently, for each member network, it knows the set 564 of all candidate endpoint pairs that will enter this network. With 565 this information, the resource orchestrator can communicate with the 566 ALTO servers at member networks to discover the resource sharing 567 between all the candidate endpoint pairs. In particular, Unicorn 568 extends the routing state abstraction [DRAFT-RSA] to the more generic 569 resource state abstraction to represent such resource sharing. 571 Figure 4 shows the procedure of the resource state abstraction 572 discovery phase. For each member network, the ALTO client in the 573 orchestrator sends an ALTO Multipart Cost Property Service query 574 defined in [DRAFT-PV] by providing the set of candidate endpoint 575 pairs as input. The cost type of this query is path vector. Upon 576 receiving the query, the ALTO server in each member network computes 577 an ALTO cost map and an ATLO property map to the ALTO client. These 578 two maps represent a set of linear inequalities revealing the 579 resource sharing among the set of candidate endpoint pairs in the 580 member network. 582 .-----------------------. 583 | Resource Orchestrator | 584 | | 585 | .-----------. | 586 | |ALTO Client| | 587 | '-----------' | 588 '---------| ^-----------' 589 Multipart| | Resource 590 Cost | | State 591 Property | | Abstraction 592 Queries v | 593 .-------------. 594 |ALTO Servers | 595 '-------------' 597 Figure 4: The Resource State Abstraction Discovery Phase. 599 Unicorn provides two mechanisms for the ALTO servers to return the 600 computed cost maps and property maps to the ALTO client. The first 601 mechanism is to let each ALTO server independently sends its response 602 to the ALTO client. The second mechanism is a privacy-preserving 603 interdomain information aggregation process, in which the ALTO 604 servers in all member networks use a secure multi-party computation 605 (SMPC) protocol to collectively send the responses to the ALTO client 606 without revealing the source of any entry, i.e., the linear in 607 equality, in the cost maps and property maps. 609 The first mechanism has a higher security risk in that it exposes the 610 bottleneck resource information of each member network. In contrast, 611 the second mechanism provides a better protection of the private 612 information of each member network. The details of the privacy- 613 preserving interdomain information aggregation process will be 614 presented in the next section. 616 After receiving the responses sent back from the ALTO servers from 617 all the member networks, the orchestrator finishes the whole resource 618 discovery process and collects the accurate information of different 619 types of resources for data analytics jobs. 621 7.2.2. Proactive Full-Mesh Resource Discovery 623 To ensure the resource discovery process scales, a proactive full- 624 mesh resource discovery component is developed. The main idea of 625 this component consists in having the ALTO client periodically query 626 ALTO servers at all sites to discover the resource state abstraction 627 between every pair of source and destination sites. As such, when an 628 application submits a resource discovery request, the ALTO client 629 does not need to send any query to the ALTO servers. Instead, using 630 the site-level bandwidth sharing information, the ALTO client can 631 immediately perform projection operations to get the resource 632 information for the request. This mechanism substantially improves 633 the scalability of Unicorn. 635 7.3. Example 637 This subsection gives an example to illustrate the workflow of 638 Unicorn. Figure 5 gives a topology of three member networks, where 639 s1 and s2 are storage endpoints and d1 and d2 are computation 640 endpoints. Assume a data analytics job is composed of two parallel 641 tasks T1 and T2. T1 needs dataset X as input and T2 needs dataset Y 642 as input. 644 .------------. 645 | Network B | 646 .------------. ingB| | 647 | Network A |--------| d1 | 648 | | '------------' 649 | s1 | 650 | | .------------. 651 | s2 |--------| Network C | 652 '------------' ingC| | 653 | d2 | 654 '------------' 656 Figure 5: An Illustrating Example for Unicorn. 658 In the endpoint property discovery phase, the Unicorn resource 659 orchestrator finds that s1 stores X and s2 stores Y, and that the 660 locations of s1, s2, d1 and d2, from the DHT lookup system. It then 661 issues EPS queries to network A, B and C, respectively, to discover 662 that d1 satisfies the computing requirements of T1 and d2 satisfies 663 the computing requirements of T2. Hence there are only two candidate 664 endpoint pairs: (s1, d1) and (s2, d2). 666 In the endpoint path discovery phase, the ALTO client in the 667 orchestrator iteratively issues Endpoint Cost Service (ECS) query to 668 the ALTO servers in member networks, and finds that the domain-path 669 for pair (s1, d2) is [(null, A), (ingB, B)] and the domain-path for 670 pair (s2, d2) is [(null, A), (ingB, B)]. Hence both pairs will use 671 the networking resources of network A, while only (s1, d1) will use 672 network B and only (s2, d2) will use network C. 674 In the resource state abstraction discovery phase, the ALTO client in 675 the orchestrator issues Multipart Cost Property Service queries to 676 network A, B and C, respectively. Denote the available bandwidth 677 that can be assigned to T1 as x1 and that to T2 as x2. Assume the 678 linear inequalities computed by the three networks are: 680 A: x1 + x2 <= 10Mbps 681 B: x1 <= 3Mbps 682 C: x2 <= 3Mbps 684 If the ALTO servers use the first mechanism to directly return their 685 resource information to ALTO client, respectively, each of them will 686 send a cost map and a property map response encoding its own linear 687 inequality to the ALTO client. In this way, the orchestrator gets 688 the accurate information about networking resource sharing between 689 (s1, d1) and (s2, d2). It then can invoke a resource allocation 690 algorithm to allocate the resources to tasks T1 and T2. For example, 691 if the goal is to maximize the minimal bandwidth of two tasks, the 692 allocation decision will be to assign endpoints s1 and d1 to T1, with 693 a bandwidth of 3Mbps, and assign endpoints s2 and d2 to T2, with a 694 bandwidth of 3Mbps as well. 696 8. ALTO Extension: Privacy-Preserving Interdomain Information 697 Aggregation for Resource Discovery 699 This section describes a customized ALTO extension in Unicorn that 700 supports the privacy-preserving discovery of networking resource 701 sharing among a set of candidate endpoint pairs. 703 8.1. Extension Specification 705 Figure 6 presents the workflow of the proposed ALTO extension. 706 Assume a set of N member networks denoted as AS_1, AS_2, ... AS_N 707 and the number of all candidate endpoint pairs is F. The interdomain 708 information aggregation process works as follows: 710 .-----------------------. 711 | Resource Orchestrator | 712 | | 713 | .-----------. | 714 | |ALTO Client| | 715 | '-----------' | 716 >'-----------------------'< 717 /Disguised /|\ \ 718 Multipart Cost / Response | \ 719 Property Queries v | \ 720 .--------. .--------. .--------. 721 |ALTO | |ALTO | |ALTO | 722 |Server 1| <------->|Server 2|<--... -->|Server N| 723 '--------' Limitedly'--------' '--------' 724 Shared Secret 726 Figure 6: The Privacy-Preserving Interdomain Resource Information 727 Aggregation. 729 o Step 1: The ALTO client sends the Multipart Cost Property Service 730 request to and a homomorphic public key k_p to each member 731 network. 733 o Step 2: The ALTO server of each network AS_i computes its own set 734 of linear inequalities A_i x <= b_i. Denote the size of this set 735 as m_i. 737 o Step 3: The ALTO server of each network AS_i introduces m_i non- 738 negative slack variables to transform its set of linear 739 inequalities into a set of linear equations. 741 o Step 4: The ALTO servers of all member networks use a private 742 matrix SMPC summation protocol to collectively compute k=m_1 + m_2 743 + ... + m_N + 1. The value k is known to all the member networks. 745 o Step 5: The ALTO servers of each network AS_i selects a random k- 746 by-m_i matrix P_i, and computes the matrix P_iA_i and P_ib_i. 748 o Step 6: The ALTO server of each network then uses a few matrices, 749 which are only shared with a couple of other networks, to further 750 obfuscate P_iA_i and P_ib_i, and sends the obfuscated matrices to 751 the ALTO client via symmetric encryption. 753 o Step 7: the ALTO client decrypts the received responses from all 754 ALTO servers, and sums up the decrypted response to get a set of 755 linear equations sum P_iA_i x = sum P_ib_i. 757 This process ensures that the networking resource capacity region 758 derived from sum P_iA_i x = sum P_ib_i is the same as that derived 759 from A_1 x <= b_1, A_2 x <= b_2, ... A_N x <= b_N. More importantly, 760 the ALTO client has no knowledge on the information of network 761 resource sharing of a single member network. 763 8.2. Example 765 This subsection uses the same example in Figure 5 to illustrate the 766 privacy-preserving information aggregation process. The set of 767 linear inequalities computed by each network is as follows: 769 A: x1 + x2 <= 10 770 B: x1 <= 3 771 C: x2 <= 3 773 Then the networks collectively compute k=1+1+1+1=4. And then 774 introduces slack variables to transform the linear inequalities into 775 linear equations: 777 A: x1 + x2 + x3 <= 10 778 B: x1 + x4 <= 3 779 C: x2 + x5 <= 3 781 For each network, the random matrix it chooses as follows: 783 P_A: [11, 49, 95, 34] 784 P_B: [58, 22, 75, 25] 785 P_C: [50, 69, 89, 95] 787 After the obfuscating process in Step 5 and Step 6 in the previous 788 subsection, the decrypted set of linear equations the ALTO client 789 gets is 791 69 x1 + 61 x2 + 11 x3 + 58 x4_ + 50 x5 = 434 792 71 x1 + 118 x2 + 49 x3 + 22 x4_ + 69 x5 = 763 793 170 x1 + 184 x2 + 95 x3 + 75 x4_ + 89 x5 = 1442 794 59 x1 + 129 x2 + 34 x3 + 25 x4_ + 95 x5 = 700 796 Assume the goal is still to maximize the minimal bandwidth of two 797 tasks, the allocation decision made using this set of linear 798 equations will still be x1=3 and x2=3, i.e., assigning endpoints s1 799 and d1 to T1, with a bandwidth of 3 and assigning endpoints s2 and d2 800 to T2, with a bandwidth of 3 as well. 802 9. Implementation and Demonstration Experience 804 The authors build an ALTO server on top of the OpenDaylight Software 805 Defined Network controller. The ALTO server collects the network 806 state information from the OpenDaylight controller, e.g., topology, 807 policy and traffic statistics, processes the collected information 808 into resource abstraction, and sends the abstraction back to the ALTO 809 client at the resource orchestrator. 811 In the past few years, the Unicorn framework has been deployed and 812 demonstrated in small federation networks connecting Dallas, Texas, 813 Los Angles, California, and Denver, Colorado at different 814 conventions. For example, in 2018, the federation in the 815 demonstration is composed of three member networks. Network 1 is in 816 Dallas, Texas, and Network 2 and network 3 are in Los Angeles, 817 California. Network 1 is connected to network 2 through a layer-2 818 WAN circuit with a 100 Gbps bandwidth, provisioned by several 819 providers such as SCinet, CenturyLink and CENIC. Network 1 is a 820 temporal science network in the CMS experiment, while network 2 and 3 821 are long-running CMS Tier-2 sites. In this federation, users need to 822 reserve network resources to transfer large-scale science datasets 823 (e.g., with a size of hundreds of PB) between networks. 825 The authors evaluate the accuracy and latency of the framework for 826 discovering network resources in this network. During the 827 evaluation, the framework accurately discovers the network resource 828 information for a large amount of circuits reservation requests with 829 a very low discovery latency. Specifically, for all the reservation 830 requests, Unicorn always provides the accurate information of 831 available bandwidth sharing in the network (i.e., a 100% accuracy), 832 with an average discovery latency of 100 milliseconds, and a worst 833 latency of less than 1 second. With the discovered network resource 834 information, users can transmit large-scale science datasets at a 835 speed up to 100 Gbps, (i.e., the theoretical maximal throughput). 837 10. Discussion 839 10.1. Discovering the Domain-Paths Using a New Interdomain Routing 840 Protocol 842 The current design of the endpoint path discovery process in Unicorn 843 assumes that the underlying interdomain routing protocol is the 844 standard BGP, which only provides the path vector of ASes instead of 845 the path vector of (ingress, AS) tuples needed by Unicorn. If a 846 multi-domain, geo-distributed data analytics system uses an 847 interdomain routing protocol that provides the path vector of 848 (ingress, AS) pairs, the endpoint path discovery process in Unicorn 849 can be simplified to only send queries to the ALTO server of the 850 network where the source candidate endpoint locates. 852 10.2. Comparison of the Efficiency to Achieve Optimal Resource 853 Orchestration using ALTO and without using ALTO 855 The authors of this draft conduct a systematic investigation to 856 understand the efficiency differences to achieve optimal resource 857 orchestration between using ALTO and without using ALTO. 858 Specifically, the authors study the problem of computing the optimal 859 resource reservation without using ALTO, but only using the simple 860 reservation interface deployed in PCE-based network resource 861 reservation systems (e.g., OSCARS). Given a client's request, a 862 novel algorithm is developed to compute the optimal resource 863 reservation within O(n^3) times of queries on the simple reservation 864 interface, where n is the number of flows in the request. This is 865 the best known algorithm for this problem. Although the asymptotic 866 complexity appears efficient, the authors' experience to test this 867 design shows that it often takes tens of thousand queries on the 868 simple reservation interface to compute the optimal resource 869 orchestration, leading to substantial orchestration latencies. This 870 result has been published at AAAI 2019. 872 In contrast, by leveraging the capability of ALTO to expose accurate 873 network information to the client, the Unicorn framework can compute 874 the optimal resource reservation by querying an ALTO server only 875 once, resulting in orders of magnitude improvement on resource 876 orchestration latencies. 878 11. Security Considerations 880 This document does not introduce any privacy or security issue not 881 already present in the ALTO protocol. 883 12. IANA Considerations 885 This document does not define any new media type or introduce any new 886 IANA consideration. 888 13. References 890 13.1. Normative References 892 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 893 Requirement Levels", BCP 14, RFC 2119, 894 DOI 10.17487/RFC2119, March 1997, 895 . 897 13.2. Informative References 899 [Apollo] Boutin, E., Ekanayake, J., Lin, W., Shi, B., Zhou, J., 900 Qian, Z., Wu, M., and L. Zhou, "Apollo: Scalable and 901 Coordinated Scheduling for Cloud-Scale Computing", 2014, 902 . 905 [Borg] Verma, A., Pedrosa, L., Korupolu, M., Oppenheimer, D., 906 Tune, E., and J. Wilkes, "Large-scale cluster management 907 at Google with Borg", 2015, 908 . 910 [DRAFT-FCS] 911 Zhang, J., Gao, K., Wang, J., Xiang, Q., and Y. Yang, 912 "ALTO Extension: Flow-based Cost Query", 2017, 913 . 915 [DRAFT-PV] 916 Bernstein, G., Lee, Y., Roome, W., Scharf, M., and Y. 917 Yang, "ALTO Extension: Abstract Path Vector as a Cost 918 Mode", 2015, . 921 [DRAFT-RSA] 922 Gao, K., Wang, X., Xiang, Q., Gu, C., Yang, Y., and G. 923 Chen, "A Recommendation for Compressing ALTO Path 924 Vectors", 2017, . 927 [DRAFT-SSE] 928 Roome, W. and Y. Yang, "ALTO Incremental Updates Using 929 Server-Sent Events (SSE)", 2015, 930 . 933 [HTCondor] 934 Thain, D., Tannenbaum, T., and M. Livny, "Distributed 935 computing in practice: the Condor experience", 2005, 936 . 938 [Mesos] Hindman, B., Konwinski, A., Zaharia, M., Ghodsi, A., 939 Joseph, A., Katz, R., Shenker, S., and I. Stoica, "Mesos: 940 A Platform for Fine-Grained Resource Sharing in the Data 941 Center", 2011, 942 . 945 [RFC7285] Alimi, R., Ed., Penno, R., Ed., Yang, Y., Ed., Kiesel, S., 946 Previdi, S., Roome, W., Shalunov, S., and R. Woundy, 947 "Application-Layer Traffic Optimization (ALTO) Protocol", 948 RFC 7285, DOI 10.17487/RFC7285, September 2014, 949 . 951 [RFC8189] Randriamasy, S., Roome, W., and N. Schwan, "Multi-Cost 952 Application-Layer Traffic Optimization (ALTO)", RFC 8189, 953 DOI 10.17487/RFC8189, October 2017, 954 . 956 [Sparrow] Ousterhout, K., Wendell, P., Zaharia, M., and I. Stoica, 957 "Sparrow: Distributed, Low Latency Scheduling", 2013, 958 . 960 [XCP] Katabi, D., Handley, M., and C. Rohrs, "Internet 961 Congestion Control for Future High Bandwidth-Delay Product 962 Environments", 2002, 963 . 966 Authors' Addresses 968 Qiao Xiang 969 Yale University 970 51 Prospect Street 971 New Haven, CT 972 USA 974 Email: qiao.xiang@cs.yale.edu 976 J. Jensen Zhang 977 Tongji/Yale University 978 51 Prospect Street 979 New Haven, CT 980 USA 982 Email: jingxuan.zhang@yale.edu 984 Franck Le 985 IBM 986 Thomas J. Watson Research Center 987 Yorktown Heights, NY 988 USA 990 Email: fle@us.ibm.com 991 Y. Richard Yang 992 Yale University 993 51 Prospect Street 994 New Haven, CT 995 USA 997 Email: yry@cs.yale.edu 999 Harvey Newman 1000 California Institute of Technology 1001 1200 California Blvd. 1002 Pasadena, CA 1003 USA 1005 Email: newman@hep.caltech.edu