ALTO Extension: A Routing State Abstraction Service Using Declarative Equivalence
draft-gao-alto-routing-state-abstraction-00

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]