ALTO WG Q. Xiang Internet-Draft Tongji/Yale University Intended status: Informational F. Le Expires: September 6, 2018 IBM Y. Yang Tongji/Yale University H. Newman California Institute of Technology H. Du Tongji University March 5, 2018 Unicorn: Resource Orchestration for Multi-Domain, Geo-Distributed Data Analytics draft-xiang-alto-multidomain-analytics-01.txt Abstract As the data volume increases exponentially over time, data analytics is transiting from a single-domain network to a multi-domain, geo- distributed network, where different member networks contribute various resources, e.g., computation, storage and networking resources, to collaboratively collect, share and analyze extremely large amounts of data. Such a network calls for a resource orchestration framework that emphasizes the performance predictability of data analytics jobs, the high utilization of resources, and the autonomy and privacy of member networks. This document presents the design of Unicorn, a unified resource orchestration framework for multi-domain, geo-distributed data analytics, which uses the Application-Layer Traffic Optimization (ALTO) protocol as the key component for (1) allows member networks to provide accurate information on different types of resources; (2) keeps the private information of member networks; and (3) allows data analytics jobs to accurately describe their requirements of different types of resources. As a part of Unicorn, an ALTO extension for privacy-preserving interdomain information aggregation is also presented. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute Xiang, et al. Expires September 6, 2018 [Page 1] Internet-Draft Unicorn Design March 2018 working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on September 6, 2018. Copyright Notice Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 4 3. Changes Since Version -00 . . . . . . . . . . . . . . . . . . 4 4. Characteristics of Multi-Domain, Geo-Distributed Data Analytics . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.1. Dynamic Data Analytics Workload . . . . . . . . . . . . . 5 4.2. Dynamic Resource Availability . . . . . . . . . . . . . . 5 5. Design Requirements . . . . . . . . . . . . . . . . . . . . . 6 6. Review of Resource Orchestration Designs for Data Analytics . 7 6.1. Centralized resource-graph-based orchestration . . . . . 7 6.2. Centralized ClassAds-based orchestration . . . . . . . . 7 6.3. Distributed opportunistic orchestration . . . . . . . . . 7 6.4. Inadequacy of Existing Designs for Multi-Domain, Geo- Distributed Data Analytics . . . . . . . . . . . . . . . 8 7. Unicorn Design . . . . . . . . . . . . . . . . . . . . . . . 8 7.1. Choosing ALTO as the Resource Information Model . . . . . 8 7.2. Architecture of Unicorn . . . . . . . . . . . . . . . . . 9 7.2.1. Three-Phase Resource Discovery . . . . . . . . . . . 11 7.3. Example . . . . . . . . . . . . . . . . . . . . . . . . . 15 8. ALTO Extension: Privacy-Preserving Interdomain Information Aggregation for Resource Discovery . . . . . . . . . . . . . 16 Xiang, et al. Expires September 6, 2018 [Page 2] Internet-Draft Unicorn Design March 2018 8.1. Extension Specification . . . . . . . . . . . . . . . . . 16 8.2. Example . . . . . . . . . . . . . . . . . . . . . . . . . 17 9. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 18 9.1. Discovering the Domain-Paths Using a New Interdomain Routing Protocol . . . . . . . . . . . . . . . . . . . . 18 10. Security Considerations . . . . . . . . . . . . . . . . . . . 18 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 12.1. Normative References . . . . . . . . . . . . . . . . . . 19 12.2. Informative References . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 1. Introduction This document describes the design of Unicorn, a unified resource orchestration framework for large-scale data analytics in multi- domain, geo-distributed networks. An important use case for such settings is the Large Hadron Collider (LHC) network, which consists of over 180 member networks all over the world, to support scientists to access multiple resources, e.g., computing, storage and networking resources, distributed in the member networks to conduct large-scale data analytics. With more and more data being generated and stored in different geo-distributed member networks, network architects and administrators are exploring different designs for efficient resource orchestration in multi-domain, geo-distributed networks. The design presented in this document is based on the development and deployment experience of Unicorn in the CMS network, one of the largest scientific experiments in the LHC network. The primary requirements of resource orchestration in such a multi-domain, geo- distributed environment are the performance predictability of various data analytics jobs, the high utilization of different types of resources, and the autonomy and privacy of resource owners, i.e., member networks. Pre-production development and extensive testing have shown that the Application-Layer Traffic Optimization Protocol [RFC7285] is well suited as a fundamental component in Unicorn for providing a generic representation that (1) allows different types of data analytics jobs to accurately describe their resource requirements and (2) allows member networks to provide accurate information on different types of resources they own and at the same time maintain their privacies. This is in contrast with the state-of-the-art resource orchestration frameworks, such as HTCondor and Mesos, which either do not provide accurate networking information or expose all the private details of member networks. This document elaborates on the design requirements of resource orchestration in multi-domain, geo-distributed networks that lead to this design choice and presents the details of Unicorn, Xiang, et al. Expires September 6, 2018 [Page 3] Internet-Draft Unicorn Design March 2018 including an ALTO extension for privacy-preserving, interdomain information aggregation. This document first gives an overview of the characteristics of multi-domain, geo-distributed data analytics. Then, the design requirements for resource orchestration under such settings are summarized. After reviewing existing designs and their limitations, this document gives the arguments for using ALTO as the generic representation for describing both resource requirements and the resource information and describes the design details of Unicorn. Finally, a privacy-preserving, interdomain extension of ALTO is presented. 2. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 3. Changes Since Version -00 o Add an overview of the characteristics of multi-domain, geo- distributed data analytics. o Based on the above characteristics, add the design requirements of the resource orchestration for multi-domain, geo-distributed data analytics. o Add a review of existing resource orchestration system designs for data analytics systems. o Update the architecture of the Unicorn system. o Update the motivation of using ALTO as the key information model in Unicorn. o Give the design details of the three-phase resource discovery in Unicorn. o Design an ALTO extension for privacy-preserving interdomain resource information aggregation. 4. Characteristics of Multi-Domain, Geo-Distributed Data Analytics This section describes the characteristics of multi-domain, geo- distributed data analytics. Xiang, et al. Expires September 6, 2018 [Page 4] Internet-Draft Unicorn Design March 2018 4.1. Dynamic Data Analytics Workload In multi-domain, geo-distributed data analytics, extremely large amounts of data are generated and stored across different member networks. Authorized users from different organizations can access data and resources in member networks to conduct various data analytics jobs using various data analytics applications. An data analytics application usually provides an automated process that decomposes a large data analytics job into a set of smaller tasks, whose dependencies are expressed as a directed acyclic graph (DAG). Tasks without any dependency can be executed in parallel to improve the efficiency of the data analytics job they belong to. This decomposition is highly user- and application-dependent. Each task may have different requirements on different resources. For instance, task T1 may require dataset A in storage node X as input and 1 CPU as the computing resource, while task T2 may require dataset B in storage node Y as input and 2 CPUs as the computing resource. Furthermore, each task may require resources from different member networks. In the previous example, T1 may require its output to be stored in a storage node in another member network for the purpose of secure storage. The resource requirements of tasks are highly user- and application-dependent. From the above description, it is observed that the workload of multi-domain, geo-distributed data analytics is highly dynamic, in terms of the number of users, the types of applications, the number of jobs, the decomposition of jobs and the resource requirements of tasks. Though with such dynamism, it is the general consensus of users to expect performance predictability of their analytics jobs (TODO: add Mogul citation). Hence the resource orchestration for multi-domain, geo-distributed data analytics must be able to achieve efficient resource sharing among different data analytics jobs of different applications from different users. To this end, a generic representation of resource requirements for different tasks from different analytics applications must be chosen. Furthermore, to ensure maximal deployment, the resource orchestration framework must be independent of and compatible with data analytics applications. 4.2. Dynamic Resource Availability In the multi-domain, geo-distributed data analytics network, different member networks belong to different administrative domains. Each member network has its own resource management policies and can Xiang, et al. Expires September 6, 2018 [Page 5] Internet-Draft Unicorn Design March 2018 choose to use different management software, such as HTCondor and Mesos. Each member network provides different types of resources with different amounts. For example, transit networks such as ESNet and Internet2 provide high-bandwidth networking resources. In contrast, campus science networks provide abundant computation and storage resources, but may provide limited networking bandwidths. And some smaller science networks only provide limited computation and storage resources. The availability of the resources in each member network is subject to the autonomous control of the member network. Furthermore, member networks are interconnected with high bandwidth- delay-product links, where state-of-the-art networking resource allocation mechanisms, such as TCP, become inefficient [XCP]. From the above description, it is observed that the resource availability of the multi-domain, geo-distributed data analytics network is also highly dynamic, subject to the types of member networks, the resources provided by member networks and the resource management policies and management software used by member networks. Though with such dynamism, it is the general consensus of member networks that the resource orchestration for multi-domain, geo- distributed data analytics must achieve high utilization of different types of resources, following the autonomy and privacy of each member network. To this end, a generic representation of resource availabilities for different types of resources must be chosen. Such a representation must be accurate and at the same time maintain the privacy of member networks. Furthermore, to ensure maximal deployment, the resource orchestration framework must be independent of and compatible with the resource management systems used by member networks. 5. Design Requirements This section summarizes the design requirements for resource orchestration for multi-domain, geo-distributed data analytics from the previous section. o REQ1: Provide performance predictability for data analytics jobs. o REQ2: Achieve the efficient resource sharing among data analytics jobs. o REQ3: Achieve the high utilization of different types of resources in member networks. Xiang, et al. Expires September 6, 2018 [Page 6] Internet-Draft Unicorn Design March 2018 o REQ4: Maintain the autonomy and privacy of member networks. o REQ5: Provide compatibility with different data analytics applications and resource management systems to maximize the deployment. 6. Review of Resource Orchestration Designs for Data Analytics This section provides an overview of three general types of resource orchestration designs for data analytics -- the centralized resource- graph-based orchestration, the centralized ClassAds-based orchestration and the distributed opportunistic orchestration. Then, the key reason why these designs are inadequate for multi-domain, geo-distributed data analytics is provided. 6.1. Centralized resource-graph-based orchestration Systems such as Mesos [Mesos] and Borg [Borg] adopt a graph-based abstraction to represent the resource availability of computing clusters. Each node in the graph is a physical node representing computation or storage resources and each edge between a pair of nodes denotes the networking resource connecting two physical nodes. This design is inadequate for multi-domain, geo-distributed data analytics system because (1) it compromises the privacy of different member networks by revealing all the details of resources; and (2) the overhead to keep the resource availability graph up to date is too expensive due to the heterogeneity and dynamicity of resources from different member networks. 6.2. Centralized ClassAds-based orchestration HTCondor [HTCondor] proposes a ClassAds programming model, which allows different resource owners to advertise their resource supply and the job owners to advertise the resource demand. However, this programming model does not support the accurate discovery of networking resources, but leave the orchestration of networking resources completely to TCP, which has been known to behave poorly in networks with high bandwidth-delay products [XCP]. 6.3. Distributed opportunistic orchestration Some systems, such as Apollo [Apollo] and Sparrow [Sparrow], use a distributed design. In this design, given a data analytics job, a small number of computing and storage nodes are randomly selected as candidates. Then a scheduling algorithm makes the decision to select the best pair of computing and storage nodes within this small set of candidates. Though it is shown in production that this design achieves a performance very close to the theoretical optimal resource Xiang, et al. Expires September 6, 2018 [Page 7] Internet-Draft Unicorn Design March 2018 allocation scheme, this design cannot be applied to multi-domain, geo-distributed data analytics because (1) the pool of computing and storage resources is much larger, and is distributed across the world, and (2) it is hard to distributively orchestrate networking resources in such a high bandwidth-delay product scenario. 6.4. Inadequacy of Existing Designs for Multi-Domain, Geo-Distributed Data Analytics Applying the designs reviewed in the preceding subsections for multi- domain, geo-distributed data analytics only satisfies the design requirement of compatibility (REQ5), but leaves all the other requirements unfulfilled. The key reason is that they do not have an information model that simultaneously o allows member networks to provide accurate information on different types of resources, e.g., the computing, storage and networking resources, they own; o keeps the private information of member networks, such as physical topologies and policies, from the data analytics applications; and o allows data analytics jobs to accurately describe their requirements of different types of resources. 7. Unicorn Design This section presents the design of the Unicorn framework. First, the motivations of using ALTO as the information model of resource orchestration for multi-domain, geo-distributed data analytics are reviewed. Then the architecture of Unicorn is provided. 7.1. Choosing ALTO as the Resource Information Model As reviewed in the preceding section, the commonly used resource- graph-based information model and the ClassAds information model do not support the accurate, yet privacy-preserving resource discovery across different member networks. In contrast, the ALTO protocol uses abstract maps of networks to provide network information with the goal of modifying network resource consumption patterns while maintaining or improving application performance [RFC7285]. This document proposes the use of ALTO for providing information of different types of resources, e.g., computing, storage and networking resources. This design has the following advantages: o ALTO provides the network information based on abstract maps of a network. Additional services are built on top of the ALTO abstract maps to provide information of other types of resources, Xiang, et al. Expires September 6, 2018 [Page 8] Internet-Draft Unicorn Design March 2018 e.g., the computing and storage resources. These maps provide accurate information of different types of resources for the resource orchestration system to effectively utilize them for data analytics applications. For example, the ALTO Endpoint Property Service can provide information of computing nodes and storage nodes. o The ALTO abstract maps provide a simplified view of resources of member networks, instead of the full details of their resource availability. Thus ALTO allows member networks to keep their private information, such as physical topologies and policies, from the applications. For example, the ALTO Network Map service provides a "one-big-switch" view that defines a grouping of network endpoints. This view hides the details of the underlying physical topology of the network and a network deploying the ALTO server has the autonomy to adopt any endpoint grouping algorithm. o ALTO uses a client-server model, in which applications can use ALTO clients to accurately describe their requirements of different types of resources and send these requirements to the ALTO servers to retrieve the accurate information of resources that suit their requirements. For example, the ALTO Multi-Cost service [RFC8189] allows an ALTO client to specify a logic set of tests in a query. Such tests are used by ALTO servers to filter out the information of unqualified resources from the response sent back to the ALTO client. 7.2. Architecture of Unicorn This section describes the design details of Unicorn. Figure 1 presents the architecture of Unicorn for a multi-domain, geo- distributed data analytics system with N member networks. In particular, Unicorn consists of the following key components: Xiang, et al. Expires September 6, 2018 [Page 9] Internet-Draft Unicorn Design March 2018 .-------------. .-------------. |Application 1| ... |Application N| '-------------' '-------------' \ / .- - - - - - - -\- - - - - - - - - - - -/- - - - - - - - - - - - - - -. | Unicorn \ / | | .-----------------------. | | | Resource Orchestrator | .----------------------.| | | | |Distributed Hash Table|| | | .-----------. |---- | of Computing and || | | |ALTO Client| | | Storage Resources || | | '-----------' | '----------------------'| | '-----------------------' | | / | \ | | / | \ | | .-------------. .-----------. .-------------. | | |ALTO Server 1| | Execution | |ALTO Server M| | | '-------------' | Agents | '-------------' | | | '-----------' | | | | / \ | | | .----------------./ \ .----------------. | | | Site 1 | . . | Site N | | | '----------------' '----------------' | '- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -' Figure 1: Architecture of Unicorn. o ALTO Server: for each member network, one or more ALTO servers are deployed to provide accurate, yet privacy-preserving information of different types of resources owned by the corresponding network. Examples of such information include the link bandwidth between endpoints, the memory I/O bandwidth and the CPU utilization at computing endpoints and the storage space at storage endpoints. In addition to the basic ALTO services defined in [RFC7285], The ALTO servers in Unicorn also provide ALTO extension services such as the ALTO Multi-Cost Service [RFC8189], the ALTO Server-Sent Event Service [DRAFT-SSE] and the ALTO Multipart Cost Property Service [DRAFT-PV] to provide fine-grained resource information. o Distributed Hash Table (DHT) of Computing and Storage Resources: A DHT system is deployed across member networks to lookup the location of computing and storage resources. Compared with the current centralized lookup services in the CMS network, i.e., PhEDEx and HTCondor, a DHT system provides a significant performance improvement for discovering the locations of computing Xiang, et al. Expires September 6, 2018 [Page 10] Internet-Draft Unicorn Design March 2018 and storage resources in multi-domain, geo-distributed data analytics systems. o Resource Orchestrator: The orchestrator is a shim layer between the data analytics jobs from different applications and the member networks. It contains an ALTO client that communicates with the ALTO servers at member networks to retrieve resource information. Given a set of data analytics jobs, the orchestrator adopts a three-phase discovery process, which will be elaborated in the next section, to find the accurate information of all the resources that can be used to execute these jobs. Then the orchestrator runs a customized resource allocation algorithm to compute the resource allocation decisions for these jobs, and send the decisions to the execution agents at corresponding member networks. o Execution Agent: One or more execution agents are deployed at each member network. They take the resource allocation decisions from the resource orchestrator, and communicate with the underlying resource management system deployed at the corresponding member network to reserve the resources for the data analytics jobs and execute them. 7.2.1. Three-Phase Resource Discovery The preceding subsection describes the architecture and the key components of Unicorn. One missing component is how to accurately discover the information of different types of resources for a set of data analytics jobs with the assistance of ALTO. This section presents the three-phase resource discovery design in Unicorn. 7.2.1.1. Phase 1: Endpoint Property Discovery Figure 2 shows the procedure of the endpoint property discovery phase. Given a set of data analytics jobs, the resource orchestrator communicates with the DHT lookup system to find the locations, i.e., the endpoint addresses, of all candidate computing and storage resources. With such information, the ALTO client then issues Endpoint Property Service (EPS) queries to the ALTO servers deployed at member networks to discover the information of all candidate endpoints. Xiang, et al. Expires September 6, 2018 [Page 11] Internet-Draft Unicorn Design March 2018 .-----------------------. | Resource Orchestrator | Jobs' Resource | | Requirements .------------. | .-----------. | ---------------> | DHT Lookup | | |ALTO Client| | <--------------- | System | | '-----------' | Endpoint '------------' '---------| ^-----------' Locations EPS | | Endpoint Queries | | Properties v | .-------------. |ALTO Servers | '-------------' Figure 2: The Endpoint Property Discovery Phase. 7.2.1.2. Phase 2: Endpoint Path Discovery Candidate computing and storage endpoints need to move data between them before, during and after the execution of a data analytics job. In multi-domain, geo-distributed data analytics, a pair of candidate endpoints may not be in the same member network. In this case, the orchestrator needs to find out the connectivity information between such a pair of candidate endpoints. Figure 3 shows the procedure of the endpoint path discovery phase. Given a pair of candidate endpoints that are not in the same member network, the ALTO client in the orchestrator adopts an iterative process to find the interdomain connectivity information for this pair. It starts by issuing an ALTO Endpoint Cost Service query or an ALTO Flow-based Endpoint Cost Service [DRAFT-FCS] to the ALTO server of the member network where the source endpoint locates. The cost type of this query is a customized type called next-hop, with a customized cost mode tuple and a customized cost metric next-network. Xiang, et al. Expires September 6, 2018 [Page 12] Internet-Draft Unicorn Design March 2018 .-----------------------. | Resource Orchestrator | | | | .-----------. | | |ALTO Client| | | '-----------' | '---------| ^-----------' Customized| | Endpoint ECS | | Path Queries | | Segments v | .-------------. |ALTO Servers | '-------------' Figure 3: The Endpoint Path Discovery Phase. The ALTO server returns a 2-tuple, where the first element is the autonomous number (AS) of the next member network along the AS-path from the source endpoint to the destination endpoint, and the second element is the ingress of this next member network. In a member network, the ALTO server can get such information from the underlying interdomain routing protocol, e.g., BGP. Based on the received response, the ALTO client then issues a similar query to the ALTO server of the next member network. The process stops when the ALTO server of the member network where the destination endpoint locates receives such a query, who will return a null 2-tuple in response to notify the ALTO client. By the end of this process, the ALTO client can assemble a domain-path, in the form of a path vector of (ingress, AS), of this pair of candidate endpoints. 7.2.1.3. Phase 3: Resource State Abstraction Discovery After the second phase, the resource orchestrator has the connectivity information of each candidate endpoint pair, i.e., the domain-path. Equivalently, for each member network, it knows the set of all candidate endpoint pairs that will enter this network. With this information, the resource orchestrator can communicate with the ALTO servers at member networks to discover the resource sharing between all the candidate endpoint pairs. In particular, Unicorn extends the routing state abstraction [DRAFT-RSA] to the more generic resource state abstraction to represent such resource sharing. Figure 4 shows the procedure of the resource state abstraction discovery phase. For each member network, the ALTO client in the orchestrator sends an ALTO Multipart Cost Property Service query defined in [DRAFT-PV] by providing the set of candidate endpoint Xiang, et al. Expires September 6, 2018 [Page 13] Internet-Draft Unicorn Design March 2018 pairs as input. The cost type of this query is path vector. Upon receiving the query, the ALTO server in each member network computes an ALTO cost map and an ATLO property map to the ALTO client. These two maps represent a set of linear inequalities revealing the resource sharing among the set of candidate endpoint pairs in the member network. .-----------------------. | Resource Orchestrator | | | | .-----------. | | |ALTO Client| | | '-----------' | '---------| ^-----------' Multipart| | Resource Cost | | State Property | | Abstraction Queries v | .-------------. |ALTO Servers | '-------------' Figure 4: The Resource State Abstraction Discovery Phase. Unicorn provides two mechanisms for the ALTO servers to return the computed cost maps and property maps to the ALTO client. The first mechanism is to let each ALTO server independently sends its response to the ALTO client. The second mechanism is a privacy-preserving interdomain information aggregation process, in which the ALTO servers in all member networks use a secure multi-party computation (SMPC) protocol to collectively send the responses to the ALTO client without revealing the source of any entry, i.e., the linear in equality, in the cost maps and property maps. The first mechanism has a higher security risk in that it exposes the bottleneck resource information of each member network. In contrast, the second mechanism provides a better protection of the private information of each member network. The details of the privacy- preserving interdomain information aggregation process will be presented in the next section. After receiving the responses sent back from the ALTO servers from all the member networks, the orchestrator finishes the whole resource discovery process and collects the accurate information of different types of resources for data analytics jobs. Xiang, et al. Expires September 6, 2018 [Page 14] Internet-Draft Unicorn Design March 2018 7.3. Example This subsection gives an example to illustrate the workflow of Unicorn. Figure 5 gives a topology of three member networks, where s1 and s2 are storage endpoints and d1 and d2 are computation endpoints. Assume a data analytics job is composed of two parallel tasks T1 and T2. T1 needs dataset X as input and T2 needs dataset Y as input. .------------. | Network B | .------------. ingB| | | Network A |--------| d1 | | | '------------' | s1 | | | .------------. | s2 |--------| Network C | '------------' ingC| | | d2 | '------------' Figure 5: An Illustrating Example for Unicorn. In the endpoint property discovery phase, the Unicorn resource orchestrator finds that s1 stores X and s2 stores Y, and that the locations of s1, s2, d1 and d2, from the DHT lookup system. It then issues EPS queries to network A, B and C, respectively, to discover that d1 satisfies the computing requirements of T1 and d2 satisfies the computing requirements of T2. Hence there are only two candidate endpoint pairs: (s1, d1) and (s2, d2). In the endpoint path discovery phase, the ALTO client in the orchestrator iteratively issues Endpoint Cost Service (ECS) query to the ALTO servers in member networks, and finds that the domain-path for pair (s1, d2) is [(null, A), (ingB, B)] and the domain-path for pair (s2, d2) is [(null, A), (ingB, B)]. Hence both pairs will use the networking resources of network A, while only (s1, d1) will use network B and only (s2, d2) will use network C. In the resource state abstraction discovery phase, the ALTO client in the orchestrator issues Multipart Cost Property Service queries to network A, B and C, respectively. Denote the available bandwidth that can be assigned to T1 as x1 and that to T2 as x2. Assume the linear inequalities computed by the three networks are: Xiang, et al. Expires September 6, 2018 [Page 15] Internet-Draft Unicorn Design March 2018 A: x1 + x2 <= 10Mbps B: x1 <= 3Mbps C: x2 <= 3Mbps If the ALTO servers use the first mechanism to directly return their resource information to ALTO client, respectively, each of them will send a cost map and a property map response encoding its own linear inequality to the ALTO client. In this way, the orchestrator gets the accurate information about networking resource sharing between (s1, d1) and (s2, d2). It then can invoke a resource allocation algorithm to allocate the resources to tasks T1 and T2. For example, if the goal is to maximize the minimal bandwidth of two tasks, the allocation decision will be to assign endpoints s1 and d1 to T1, with a bandwidth of 3Mbps, and assign endpoints s2 and d2 to T2, with a bandwidth of 3Mbps as well. 8. ALTO Extension: Privacy-Preserving Interdomain Information Aggregation for Resource Discovery This section describes a customized ALTO extension in Unicorn that supports the privacy-preserving discovery of networking resource sharing among a set of candidate endpoint pairs. 8.1. Extension Specification Figure 6 presents the workflow of the proposed ALTO extension. Assume a set of N member networks denoted as AS_1, AS_2, ... AS_N and the number of all candidate endpoint pairs is F. The interdomain information aggregation process works as follows: .-----------------------. | Resource Orchestrator | | | | .-----------. | | |ALTO Client| | | '-----------' | '-----------------------'< Encryption Key and / \ Ciphered MCP Multipart Cost / \ Response Property Queries v Key, Ciphertext \ .--------. and MCP .--------. .--------. |ALTO | Queries |ALTO | |ALTO | |Server 1| -------> |Server 2|-- ... -->|Server N| '--------' '--------' '--------' Figure 6: The Privacy-Preserving Interdomain Resource Information Aggregation. Xiang, et al. Expires September 6, 2018 [Page 16] Internet-Draft Unicorn Design March 2018 o Step 1: The ALTO client sends the Multipart Cost Property Service request to and a homomorphic public key k_p to each member network. o Step 2: The ALTO server of each network AS_i computes its own set of linear inequalities A_i x <= b_i. Denote the size of this set as m_i. o Step 3: The ALTO server of each network AS_i introduces m_i non- negative slack variables to transform its set of linear inequalities into a set of linear equations. o Step 4: The ALTO servers of all member networks use an SMPC summation protocol to collectively compute k=m_1 + m_2 + ... + m_N + 1. The value k is known to all the member networks. o Step 5: The ALTO servers of each network AS_i selects a random k- by-m_i matrix P_i, and compute the matrix P_iA_i and P_ib_i. o Step 6: The ALTO servers of all member networks use an SMPC summation protocol to collectively compute the summation of P_iA_i and the summation of P_ib_i using the public key k_p. Then the final result is returned to the ALTO client. o Step 7: the ALTO client uses its own private key to decrypt the result and get a set of linear equations sum P_iA_i x = sum P_ib_i. This process ensures that the networking resource capacity region derived from sum P_iA_i x = sum P_ib_i is the same as that derived from A_1 x <= b_1, A_2 x <= b_2, ... A_N x <= b_N. More importantly, the ALTO client has no knowledge on the information of network resource sharing of a single member network. 8.2. Example This subsection uses the same example in Figure 5 to illustrate the privacy-preserving information aggregation process. The set of linear inequalities computed by each network is as follows: A: x1 + x2 <= 10 B: x1 <= 3 C: x2 <= 3 Then the networks collectively compute k=1+1+1+1=4. And then introduces slack variables to transform the linear inequalities into linear equations: Xiang, et al. Expires September 6, 2018 [Page 17] Internet-Draft Unicorn Design March 2018 A: x1 + x2 + x3 <= 10 B: x1 + x4 <= 3 C: x2 + x5 <= 3 For each network, the random matrix it chooses as follows: P_A: [11, 49, 95, 34] P_B: [58, 22, 75, 25] P_C: [50, 69, 89, 95] After the SMPC summation process, the decrypted set of linear equations the ALTO client gets is 69 x1 + 61 x2 + 11 x3 + 58 x4_ + 50 x5 = 434 71 x1 + 118 x2 + 49 x3 + 22 x4_ + 69 x5 = 763 170 x1 + 184 x2 + 95 x3 + 75 x4_ + 89 x5 = 1442 59 x1 + 129 x2 + 34 x3 + 25 x4_ + 95 x5 = 700 Assume the goal is still to maximize the minimal bandwidth of two tasks, the allocation decision made using this set of linear equations will still be x1=3 and x2=3, i.e., assigning endpoints s1 and d1 to T1, with a bandwidth of 3 and assigning endpoints s2 and d2 to T2, with a bandwidth of 3 as well. 9. Discussion 9.1. Discovering the Domain-Paths Using a New Interdomain Routing Protocol The current design of the endpoint path discovery process in Unicorn assumes that the underlying interdomain routing protocol is the standard BGP, which only provides the path vector of ASes instead of the path vector of (ingress, AS) tuples needed by Unicorn. If a multi-domain, geo-distributed data analytics system uses an interdomain routing protocol that provides the path vector of (ingress, AS) pairs, the endpoint path discovery process in Unicorn can be simplified to only send queries to the ALTO server of the network where the source candidate endpoint locates. 10. Security Considerations This document does not introduce any privacy or security issue not already present in the ALTO protocol. Xiang, et al. Expires September 6, 2018 [Page 18] Internet-Draft Unicorn Design March 2018 11. IANA Considerations This document does not define any new media type or introduce any new IANA consideration. 12. References 12.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . 12.2. Informative References [Apollo] Boutin, E., Ekanayake, J., Lin, W., Shi, B., Zhou, J., Qian, Z., Wu, M., and L. Zhou, "Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing", 2014, . [Borg] Verma, A., Pedrosa, L., Korupolu, M., Oppenheimer, D., Tune, E., and J. Wilkes, "Large-scale cluster management at Google with Borg", 2015, . [DRAFT-FCS] Zhang, J., Gao, K., Wang, J., Xiang, Q., and Y. Yang, "ALTO Extension: Flow-based Cost Query", 2017, . [DRAFT-PV] Bernstein, G., Lee, Y., Roome, W., Scharf, M., and Y. Yang, "ALTO Extension: Abstract Path Vector as a Cost Mode", 2015, . [DRAFT-RSA] Gao, K., Wang, X., Xiang, Q., Gu, C., Yang, Y., and G. Chen, "A Recommendation for Compressing ALTO Path Vectors", 2017, . Xiang, et al. Expires September 6, 2018 [Page 19] Internet-Draft Unicorn Design March 2018 [DRAFT-SSE] Roome, W. and Y. Yang, "ALTO Incremental Updates Using Server-Sent Events (SSE)", 2015, . [HTCondor] Thain, D., Tannenbaum, T., and M. Livny, "Distributed computing in practice: the Condor experience", 2005, . [Mesos] Hindman, B., Konwinski, A., Zaharia, M., Ghodsi, A., Joseph, A., Katz, R., Shenker, S., and I. Stoica, "Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center", 2011, . [RFC7285] Alimi, R., Ed., Penno, R., Ed., Yang, Y., Ed., Kiesel, S., Previdi, S., Roome, W., Shalunov, S., and R. Woundy, "Application-Layer Traffic Optimization (ALTO) Protocol", RFC 7285, DOI 10.17487/RFC7285, September 2014, . [RFC8189] Randriamasy, S., Roome, W., and N. Schwan, "Multi-Cost Application-Layer Traffic Optimization (ALTO)", RFC 8189, DOI 10.17487/RFC8189, October 2017, . [Sparrow] Ousterhout, K., Wendell, P., Zaharia, M., and I. Stoica, "Sparrow: Distributed, Low Latency Scheduling", 2013, . [XCP] Katabi, D., Handley, M., and C. Rohrs, "Internet Congestion Control for Future High Bandwidth-Delay Product Environments", 2002, . Authors' Addresses Qiao Xiang Tongji/Yale University 51 Prospect Street New Haven, CT USA Email: qiao.xiang@cs.yale.edu Xiang, et al. Expires September 6, 2018 [Page 20] Internet-Draft Unicorn Design March 2018 Franck Le IBM Thomas J. Watson Research Center Yorktown Heights, NY USA Email: fle@us.ibm.com Y. Richard Yang Tongji/Yale University 51 Prospect Street New Haven, CT USA Email: yry@cs.yale.edu Harvey Newman California Institute of Technology 1200 California Blvd. Pasadena, CA USA Email: newman@hep.caltech.edu Haizhou Du Tongji University 4800 Cao'an Hwy Shanghai 201804 China Email: duhaizhou@gmail.com Xiang, et al. Expires September 6, 2018 [Page 21]