ALTO WG K. Gao Internet-Draft Tsinghua University Intended status: Standards Track X. Wang Expires: January 7, 2016 Tongji University Y. Yang Yale University G. Chen Huawei July 6, 2015 ALTO Extension: A Routing State Abstraction Service Using Declarative Equivalence draft-gao-alto-routing-state-abstraction-00.txt Abstract The Application-Layer Traffic Optimization (ALTO) protocol has defined multiple services (e.g., network maps, cost maps, filtered maps, the endpoint cost service, and the endpoint property service) to provide network state information to network applications. In a higher-level view, both the cost maps and the endpoint cost service can be considered as providing views into the routing state of a network (i.e., the path properties). A drawback of these existing services, however, is that they are static, application-oblivious views, without guidance from network applications. This document designs a new ALTO service named Routing State Abstraction using Declarative Equivalence (RSADE). Allowing applications to provide declarative guidance on the intended use of the network routing state, RSADE allows a network to compute compact, customized routing state abstraction beyond the existing services. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Gao, et al. Expires January 7, 2016 [Page 1] Internet-Draft Routing State Abstraction July 2015 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 January 7, 2016. Copyright Notice Copyright (c) 2015 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 2. The Multi-flow Scheduling Use Case . . . . . . . . . . . . . 4 3. The RSADE Service . . . . . . . . . . . . . . . . . . . . . . 5 4. The RSADE Equivalence Condition . . . . . . . . . . . . . . . 6 5. Security Considerations . . . . . . . . . . . . . . . . . . . 8 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.1. Normative References . . . . . . . . . . . . . . . . . . 9 8.2. Informative References . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 1. Introduction The key services of the ALTO protocol [RFC7285] can be considered as information query services about the routing state of a network. Specifically, a cost map of an ALTO metric allows a network application to look up the end-to-end value of the given metric, for the routing path(s) from a given source to a given destination. The endpoint cost service provides a similar service. The recent advance of newer network architectures such as SDN, however, reveals that the existing services may have limitations. First, the existing services distinguish routing state at the host Gao, et al. Expires January 7, 2016 [Page 2] Internet-Draft Routing State Abstraction July 2015 level. This is reasonable in a traditional network such as a network using destination IP based routing. The emergence of new techniques such as SDN using OpenFlow may convert more networks to use more fine-grained routing, such as the 5-tuple (source and destination IPs, source and destination ports, and protocol) routing. In such a setting, revealing routing state (e.g., cost) at the granularity of endhosts may be too coarse. For example, for a network where port 80 HTTP traffic is routed differently from port 22 traffic, the existing services cannot provide the differentiation. Second, the existing (routing state query) ALTO services are designed for relatively simple network applications. More complex network applications, such as the multi-flow scheduling application [I-D.yang-alto-path-vector], may need more complex routing state information for better application-level coordination. Let f be the network application (or network component) and let view() be the function that constructs an abstract routing state view for f. One can see that view() may compute an on-demand, instead of static, view that will depend on f. The existing ALTO services do not provide this customization capability. A possibility to address the customization problem is that the network provides raw, complete routing state view. However, providing abstract views on top of raw network state, as ALTO does, can provide substantial benefits to both the network, which manages the network state, and the network applications, which consume the network state. First, a more compact abstract network state view can reduce the requirement on client scaling. The raw network state of a large network may consist of a large number of network devices. A consumer of such a large amount of information must be scalable. Second, an abstract network state view can better protect the privacy of the provider of the network. Third, an abstract network state view may substantially reduce the load of information updates. The objective of this document is to design an ALTO extension service named Routing State Abstraction using Declarative Equivalence (RSADE) to address the preceding two issues. Specifically, RSADE provides a simple, declarative API for a network application to specify its need (i.e., requirements) of routing and topology state, and the network computes a minimal, but equivalent routing state to the network application. For simplicity, this document focuses on extending the endpoint cost service, leaving the aggregation aspects of using network aggregation maps as future work. The organization of this document is organized as follows. Section 2 replicates the multi-flow scheduling example from [I-D.yang-alto-path-vector]. Section 3 gives an overview of the service, and Section 4 gives more details on specifying state Gao, et al. Expires January 7, 2016 [Page 3] Internet-Draft Routing State Abstraction July 2015 equivalence. Sections 5 and 6 discuss security and IANA considerations. 2. The Multi-flow Scheduling Use Case A foundation of the ALTO services is the routing cost value (for a given metric) for each pair of source and destination. Although simple, this foundation may not convey enough information to some applications. This document uses a simple use case in [I-D.yang-alto-path-vector] to illustrate the issue. See [I-D.lee-alto-app-net-info-exchange] for earlier, more comprehensive discussions. Consider a network as shown in Figure 1. The network has 7 switches (sw1 to sw7) forming a dumb-bell topology. Switches sw1/sw3 provide access on one side, s2/s4 provide access on the other side, and sw5-sw7 form the backbone. Endhosts eh1 to eh4 are connected to access switches sw1 to sw4 respectively. Assume that the bandwidth of each link is 100 Mbps. Assume that the network is abstracted with 4 PIDs, with each representing the hosts at one access switch. +------+ | | --+ sw6 +-- / | | \ PID1 +-----+ / +------+ \ +-----+ PID2 eh1__| |_ / \ ____| |__eh2 | sw1 | \ +--+---+ +---+--+ / | sw2 | +-----+ \ | | | |/ +-----+ \_| sw5 +---------+ sw7 | PID3 +-----+ / | | | |\ +-----+ PID4 eh3__| |__/ +------+ +------+ \____| |__eh4 | sw3 | | sw4 | +-----+ +-----+ Figure 1: Raw Network Topology. Consider an application overlay (e.g., a large data transfer system) which needs to schedule the traffic among a set of endhost source- destination pairs, say eh1 -> eh2, and eh3 -> eh4. The application can request a cost map (or endpoint cost service) providing end-to- end available bandwidth, using 'available bw' as cost-metric and 'numerical' as cost-mode, where the 'available bw' between two endhosts represents their available bandwidth, if no other applications use shared resources. Gao, et al. Expires January 7, 2016 [Page 4] Internet-Draft Routing State Abstraction July 2015 Assume that the application receives from the cost map that both eh1 -> eh2 and eh3 -> eh44 have bandwidth 100 Mbps. It cannot determine that if it schedules the two flows together, whether it will obtain a total of 100 Mbps or 200 Mbps. This depends on whether the routing of the two flows shares a bottleneck in the underlying topology: o Case 1: If the two flows use different paths in the current routing state, for example, when the first uses sw1 -> sw5 -> sw7 -> sw2, and the second uses sw3 -> sw5 -> sw6 -> sw7 -> sw4. Then the application will obtain 200 Mbps. o Case 2: If the two flows share a bottleneck in the current routing state, for example, when both use the direct link sw5 -> sw7, then the application will obtain only 100 Mbps. To allow applications to distinguish the two aforementioned cases, the network needs to provide more details on the routing state. A naive solution to this problem, then, is to return the two complete, detailed routes and the available bandwidth of each link on the routes. But this may not be desirable, as the application may not need the details and/or may not have the permission to see networks details. Now consider what route abstraction can achieve. Assuming case 2 (shared bottleneck), it is sufficient for the network to return a single abstract link for each flow: ane1(100Mbps), where ane stands for abstract network element, and the number in the number 100Mbps denotes its capacity. Consider a variation of the preceding case. Assume that the capacity of the link from sw1 to sw5 is 70 Mbps, while the rest are still at 100 Mbps. Then the abstract route from eh2 to eh4 becomes ane1(100Mbps) and ane2(70Mbps). 3. The RSADE Service The more the network knows about what a network application f needs regarding a routing state query, the more concise the network response can be. Hence, an extreme API is that the complete network application f (i.e., the code and related state) is sent to the network. This, however, can create substantial complexity in the routing-state query component, as even some simple program properties (e.g., halting) are already difficult to analyze. Also, in settings such as interdomain, the owner of the function f may not want to provide the complete f to the network. Another extreme API is that each routing state query provides only the most basic information (i.e., the source and the destination). Gao, et al. Expires January 7, 2016 [Page 5] Internet-Draft Routing State Abstraction July 2015 This, however, does not provide enough information for the routing- state service to compute efficient route abstraction/compression. Hence, the returned routes will be independent of individual functions, missing out opportunities on abstraction or compression. The RSADE service tries to strike a balance between the two extremes. Figure 1 gives the grammar to specify the query information that a network application sends to the network: rs-query := flow-list equiv-cond flow-list := flow [flow-list] flow := generic-match-condition Specifically, the first component of a RSADE query is a list of flows (flow-list). Each flow in the list is specified by a match condition, as in OpenFlow. The second component of the query input is the declared equivalence condition. A particular type of equivalence condition, in the context of routing-state query, is the equal range condition. We give the detailed specification of the condition in Section 4. After receiving an RSADE request, the network retrieves the route for each flow, and then computes the result after compression (abstraction). RSADE may allow a network application to specify an indicator, on whether it wants to receive incremental updates to the query results, achieving push notification. The push notification is implemented using HTTP SSE [Roome-SSE]. 4. The RSADE Equivalence Condition Let attr (e.g., delay) be a vector for a given link attribute. Let vector R[i] represent the result of route lookup for flow i, where R[i][e] is the fraction of traffic of flow i on link e, according to the current routing state. For example, the result of route lookup for the use case in Section 2 can be represented as the following: Gao, et al. Expires January 7, 2016 [Page 6] Internet-Draft Routing State Abstraction July 2015 R[0] R[1] avabw delay bg-tr link1 1 0 1G 2ms ... link2 1 0 100M 5ms ... link3 1 1 100M 5ms Link4 1 1 100M 5ms link5 0 1 100M 7ms link6 0 1 1G 4ms ... linkM Although a routing-state query without abstraction/compression will return all of the data shown above, route abstraction/compression will select only a subset link attributes (columns) and some links (rows). Elimination of links from the complete result achieves compression but may result in loss of information to the application. Hence, a specification on conditions whether the elimination of a set of links from the complete result leads to information loss or not is the key to the problem definition. Such a specification, however, can be provided only by the application itself. Specifically, in the general case, the result from the routing-state query will become the input parameters for the algorithms in the network application, to help the application to make decisions. Let x be the vector of the decision variables in the application. Then, one can identify that a generic structure of the application is to solve/optimize obj(x), subject to two types of constraints on x: (1) those do not involve the results from the routing state query; and (2) those do. Let the first type limit x in X0. Consider the second type. The state of art in algorithmic design typically handles only linear constraints, and hence the set S of constraints of this type will be of the format a_k x <= b_k, where a_k is a vector, and b_k a constant. Hence, it is in a_k or b_k where the result from the routing-state query appears. Let A x <= b as a matrix format to represent the whole set of constraints. Now, consider the case that a link appears in the complete result of a RSADE query, but its parameters do not appear in a boundary constraint among the aforementioned constraints, then the link may not need to appear in a compressed RSADE query. [Equivalence]: Two constraint sets S_1 and S_2 of a network function are equivalent if and only if they limit the decision variables in the same way: X_0 ^ {x: A_1 x <= b_1 } = X_0 ^ {x: A_2 x <= b_2 }. [Redundant]: A constraint s is redundant to a constraint set S if and only if s in S and the two sets S and S-{s} are equivalent. Gao, et al. Expires January 7, 2016 [Page 7] Internet-Draft Routing State Abstraction July 2015 [Minimal Constraint Set]: A constraint set S is minimal if and only if for any s in S, s is not redundant. [Equivalent Routing-State Query] A declarative equivalence based routing-state query is one where the querier (application) declares X_0 and a set of constraints S = {a_k x <= b_k}. If the attribute of a link does not appear in a minimal constraint set, the link can be eliminated from the routing-state result. A concern one may have is that the preceding definition may be limited. Consider the case of hierarchical networks, where the upper-layer network (i.e., the network application) conducts routing (traffic engineering) in its layer and uses RSADE to obtain the state of the lower layer. Let flows be the n(n-1) source-destination pairs in the upper layer network with n nodes. Let x be the set of decision variables controlling the routing in the upper-layer, where each element is the routing on each of the preceding flows. Let X_0 encode the constraints on traffic demand. We have the following result: [UTE Completeness] Any upper-layer routing (traffic engineering) algorithm where the goal of RSADE in the lower-layer network is to avoid congestion of shared links or shared risk groups can be implemented using the declarative equivalence based routing-state query. We refer to this as the upper-layer traffic engineering (UTE). Let A = R and b = cap. Then the RSADE query returns a link only if the link may become a bottleneck in the upper layer network. 5. Security Considerations This document has not conducted its security analysis. Gao, et al. Expires January 7, 2016 [Page 8] Internet-Draft Routing State Abstraction July 2015 6. IANA Considerations This document requires the definition of a new cost-mode named path- vector. 7. Acknowledgments The author thanks discussions with Jun Bi and Andreas Voellmy. 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 8.2. Informative References [I-D.lee-alto-app-net-info-exchange] Lee, Y., Bernstein, G., Choi, T., and D. Dhody, "ALTO Extensions to Support Application and Network Resource Information Exchange for High Bandwidth Applications", draft-lee-alto-app-net-info-exchange-02 (work in progress), July 2013. [I-D.yang-alto-path-vector] Bernstein, G., Lee, Y., Roome, W., Scharf, M., and Y. Yang, "ALTO Topology Extension: Path Vector as a Cost Mode", draft-yang-alto-path-vector-00 (work in progress), March 2015. [RFC7285] Alimi, R., Penno, R., Yang, Y., Kiesel, S., Previdi, S., Roome, W., Shalunov, S., and R. Woundy, "Application-Layer Traffic Optimization (ALTO) Protocol", RFC 7285, September 2014. Authors' Addresses Kai Gao Tsinghua University 30 Shuangqinglu Street Beijing 100084 China Gao, et al. Expires January 7, 2016 [Page 9] Internet-Draft Routing State Abstraction July 2015 Xing (Tony) Wang Tongji University 4800 CaoAn Road Shanghai 210000 Y. Richard Yang Yale University 51 Prospect St New Haven CT USA Email: yry@cs.yale.edu G. Robert Chen Huawei Nanjing China Email: chenguohai@huawei.com Gao, et al. Expires January 7, 2016 [Page 10]