[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 08

ALTO WG                                                           K. Gao
Internet-Draft                                       Tsinghua University
Intended status: Standards Track                                 X. Wang
Expires: September 3, 2018                             Tongji University
                                                                Q. Xiang
                                                  Tongji/Yale University
                                                                   C. Gu
                                                       Tongji University
                                                                 Y. Yang
                                                         Yale University
                                                                 G. Chen
                                                                  Huawei
                                                           March 2, 2018


                     Compressing ALTO Path Vectors
            draft-gao-alto-routing-state-abstraction-08.txt

Abstract

   The path vector extension [I-D.ietf-alto-path-vector] has extended
   the base ALTO protocol [RFC7285] with the ability to represent a more
   detailed view of the network which contains not only end-to-end costs
   but also information about shared bottlenecks.

   However, the view computed by straw man algorithms can contain
   redundant information and result in unnecessary communication
   overhead.  The situation gets even worse when certain ALTO extensions
   are enabled, for example, the incremental update extension
   [I-D.ietf-alto-incr-update-sse] which continuously pushes data
   changes to ALTO clients.  Redundant information can trigger
   unnecessary updates.

   In this document, several algorithms are described which can
   effectively reduce the redundancy in the network view while still
   providing the same information as in the original path vectors.

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.




Gao, et al.             Expires September 3, 2018               [Page 1]


Internet-Draft          Compressing Path Vectors              March 2018


   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/.

   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 3, 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.  Changes Since Version -03, -04, -05, -06 and -07  . . . . . .   4
   3.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Compressing Path Vectors  . . . . . . . . . . . . . . . . . .   4
     4.1.  Equivalent Aggregation  . . . . . . . . . . . . . . . . .   5
     4.2.  Redundant Network Elements  . . . . . . . . . . . . . . .   6
     4.3.  Equivalent Decomposition  . . . . . . . . . . . . . . . .   7
   5.  Compression Algorithms  . . . . . . . . . . . . . . . . . . .   8
     5.1.  Equivalent Aggregation  . . . . . . . . . . . . . . . . .   9
     5.2.  Redundant Network Element Identification  . . . . . . . .  11
     5.3.  Equivalent Decomposition  . . . . . . . . . . . . . . . .  13
     5.4.  Execution Order . . . . . . . . . . . . . . . . . . . . .  16
   6.  Encoding/Decoding Path Vectors  . . . . . . . . . . . . . . .  16
     6.1.  Decoding Path Vectors . . . . . . . . . . . . . . . . . .  17
     6.2.  Encoding Path Vectors . . . . . . . . . . . . . . . . . .  20
     6.3.  Compatibility . . . . . . . . . . . . . . . . . . . . . .  23
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  23
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  23
   9.  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .  23



Gao, et al.             Expires September 3, 2018               [Page 2]


Internet-Draft          Compressing Path Vectors              March 2018


   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  23
     10.1.  Normative References . . . . . . . . . . . . . . . . . .  23
     10.2.  Informative References . . . . . . . . . . . . . . . . .  23
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  24

1.  Introduction

   The path vector extension [I-D.ietf-alto-path-vector] has extended
   the base ALTO protocol [RFC7285] with the ability to present more
   complex network views than the simple abstraction used by Cost Map or
   Endpoint Cost Service.  ALTO clients can query more sophisticated
   information such as shared bottlenecks, and schedule their flows
   properly to avoid congestion and to better utilize network resources.

   Meanwhile, the extension itself does not specify how an ALTO server
   should respond to a path-vector query.  A straw man approach, as in
   the context of Software Defined Networking (SDN) where network
   providers have a global view, can compute the path vectors by
   retrieving the paths for all requested flows and returning the links
   on those paths as abstract network elements.  However, this approach
   has several drawbacks:

   o  The resultant network view may lead to privacy leaks.  Since the
      paths constitute a sub-graph of the global network topology, they
      may contain sensitive information without further processing.

   o  The resultant network view may contain redundant information.  The
      path vector information is primarily used to avoid network
      bottlenecks.  Thus, if a link cannot become the bottleneck, as
      demonstrated in Section 4, it is considered as redundant.
      Redundant links not only increase the communication overhead of
      the path vector extension, but also trigger false-positive data
      change events when the incremental update extension
      [I-D.ietf-alto-incr-update-sse] is activated.

   To overcome these limitations, this document describes equivalent
   transformation algorithms that identify redundant abstract network
   elements and reduce them as much as possible.  The algorithm can be
   integrated with any implementation of the path vector extension as a
   post-processing step.  As the name suggests, this algorithm conducts
   equivalent transformations on the original path vectors, removes
   redundant information and obtains a more compact view.

   This document is a supplement to the path vector extension and can be
   optionally turned on and off without affecting the correctness of
   responses.  A crucial part of the equivalent transformation algorithm
   is how to find redundant abstract network elements.  By tuning the
   redundancy check algorithm, one can make different trade-off



Gao, et al.             Expires September 3, 2018               [Page 3]


Internet-Draft          Compressing Path Vectors              March 2018


   decisions between efficiency and privacy.  A reference implementation
   of redundancy check algorithm is also described in this document.

   This document is organized as follows.  Section 4 gives a concrete
   example to demonstrate the importance of compressing path vectors.
   The compression algorithms are specified in Section 5 and Section 6
   discusses how one can use these algorithms on existing path vector
   responses.  Finally, Section 7 and Section 8 discuss security and
   IANA considerations.

2.  Changes Since Version -03, -04, -05, -06 and -07

   In early versions of this draft, a lot of contents are shared with
   the path vector draft.  From version -04, the authors have adjusted
   the structure and target this document as a supplement of the path
   vector extension with

   o  practical compression algorithms which can effectively reduce the
      leaked information and the communication overhead; and

   o  detailed instructions on how an original path vector response can
      be processed by these algorithms.

   The -06 version fixed some minor issues in -04 and -05.  The -07
   version has focused on improving the clarity of the algorithms with
   more examples.  The -08 version has improved the overall quality of
   the draft, especially the clarity of the algorithms using simpler
   symbols.

3.  Terminology

   This document uses the same terms as in [I-D.ietf-alto-path-vector].

4.  Compressing Path Vectors

   We use the example shown in Figure 1 to demonstrate the importance of
   compressing path vectors.  The network has 6 switches (sw1 to sw6)
   forming a dumbbell topology where switches sw1/sw3 provide access on
   the left hand side, s2/s4 provide access on the right hand side, and
   sw5/sw6 form the backbone.  End hosts eh1 to eh4 are connected to
   access switches sw1 to sw4 respectively.  Assume that the bandwidth
   of each link is 100 Mbps, and that the network is abstracted with 4
   PIDs each representing a host at one access switch.








Gao, et al.             Expires September 3, 2018               [Page 4]


Internet-Draft          Compressing Path Vectors              March 2018


       PID1 +-----+                                    +-----+  PID2
       eh1__|     |_                               ____|     |__eh2
            | sw1 | \   +------+         +------+ /    | sw2 |
            +-----+  \  |      |         |      |/     +-----+
                      \_| sw5  +---------+ sw6  |
       PID3 +-----+   / |      |         |      |\     +-----+  PID4
       eh3__|     |__/  +------+         +------+ \____|     |__eh4
            | sw3 |                                    | sw4 |
            +-----+                                    +-----+

                      Figure 1: Raw Network Topology

                        +--------+---------------+
                        | Link   | Description   |
                        +--------+---------------+
                        | link1  | sw1 <==> sw5  |
                        | link2  | sw2 <==> sw6  |
                        | link3  | sw3 <==> sw5  |
                        | link4  | sw4 <==> sw6  |
                        | link5  | sw5 <==> sw6  |
                        +--------+---------------+

                     Table 1: Description of the Links

   Three cases are identified when path vectors can be further
   compressed and an example is provided for each case.

4.1.  Equivalent Aggregation

   Consider an application which schedules the traffic consisting of two
   flows, eh1 -> eh2 and eh3 -> eh4.  The application can query the path
   vectors and a straw man implementation will return all 5 links
   (abstract network elements) as shown in Figure 2.

                 path vectors:
                     eh1: [ eh2: [ane:l1, ane:l5, ane:l2]]
                     eh3: [ eh4: [ane:l3, ane:l5, ane:l4]]

                 abstract network element property map:
                     ane:l1 : 100 Mbps
                     ane:l2 : 100 Mbps
                     ane:l3 : 100 Mbps
                     ane:l4 : 100 Mbps
                     ane:l5 : 100 Mbps

       Figure 2: Path Vectors Returned by a Straw Man Implementation





Gao, et al.             Expires September 3, 2018               [Page 5]


Internet-Draft          Compressing Path Vectors              March 2018


   The resultant path vectors represent the following linear constraints
   on the available bandwidth for the two flows:

               bw(eh1->eh2)                <= 100 Mbps (ane:l1)
               bw(eh1->eh2)                <= 100 Mbps (ane:l2)
                              bw(eh3->eh4) <= 100 Mbps (ane:l3)
                              bw(eh3->eh4) <= 100 Mbps (ane:l4)
               bw(eh1->eh2) + bw(eh3->eh4) <= 100 Mbps (ane:l5)

       Figure 3: Linear Constraints Represented by the Path Vectors

   It can be seen that the constraints of ane:l1 and ane:l2 are exactly
   the same, and so are those of ane:l3 and ane:l4.  Intuitively, we can
   replace ane:l1 and ane:l2 with a new abstract network element ane:1,
   and similarly replace ane:l3 and ane:l4 with ane:2.  The new path
   vectors are shown in Figure 4.

                  path vectors:
                      eh1: [ eh2: [ane:1, ane:l5]]
                      eh3: [ eh4: [ane:2, ane:l5]]

                  abstract network element property map:
                      ane:1  : 100 Mbps
                      ane:2  : 100 Mbps
                      ane:l5 : 100 Mbps

   Figure 4: Path Vectors after Merging ane:l1/ane:l2 and ane:l3/ane:l4

4.2.  Redundant Network Elements

   Consider the same case as in Section 4.1.  Taking a deeper look at
   Figure 3, one can conclude that constraints of ane:1 (ane:l1/ane:l2)
   and ane:2 (ane:l3/ane:l4) can be implicitly derived from that of
   ane:l5.  Thus, these constraints are considered _redundant_ and the
   path vectors in Figure 4 can be further reduced.  We replace ane:l5
   with a new ane:3 and the new path vectors are shown in Figure 5.

                  path vectors:
                      eh1: [ eh2: [ane:3]]
                      eh3: [ eh4: [ane:3]]

                  abstract network element property map:
                      ane:3 : 100 Mbps

         Figure 5: Path Vectors after Removing Redundant Elements

   It is clear that the new path vectors (Figure 5) are much more
   compact than the original path vectors (Figure 2) but they contain



Gao, et al.             Expires September 3, 2018               [Page 6]


Internet-Draft          Compressing Path Vectors              March 2018


   just as much information.  Meanwhile, the application can hardly
   infer anything about the original topology with the compact path
   vectors.

4.3.  Equivalent Decomposition

   However, it is not always possible to directly remove all redundant
   network elements.  For example, consider the case when both bandwidth
   and routingcost are requested, and the values are as shown in
   Figure 6.  Note that we have changed the bandwidth for ane:l5 for
   demonstration purpose.

                 path vectors:
                     eh1: [ eh2: [ane:l1, ane:l5, ane:l2]]
                     eh3: [ eh4: [ane:l3, ane:l5, ane:l4]]

                 abstract network element property map:
                     ane:l1 : 100 Mbps, 1
                     ane:l2 : 100 Mbps, 2
                     ane:l3 : 100 Mbps, 1
                     ane:l4 : 100 Mbps, 1
                     ane:l5 : 200 Mbps, 1

       Figure 6: Path Vectors Returned by a Straw Man Implementation

               bw(eh1->eh2)                <= 100 Mbps (ane:l1)
               bw(eh1->eh2)                <= 100 Mbps (ane:l2)
                              bw(eh3->eh4) <= 100 Mbps (ane:l3)
                              bw(eh3->eh4) <= 100 Mbps (ane:l4)
               bw(eh1->eh2) + bw(eh3->eh4) <= 200 Mbps (ane:l5)

       Figure 7: Bandwidth Constraints in the Original Path Vectors

          rc(eh1->eh2) = rc(ane:l1) + rc(ane:l2) + rc(ane:l5) = 4
          rc(eh3->eh4) = rc(ane:l3) + rc(ane:l4) + rc(ane:l5) = 3

      Figure 8: Routingcost Information in the Original Path Vectors

   Figure 7 and Figure 8 demonstrate the bandwidth and routingcost
   information one can obtain from the original path vector.  Again,
   ane:l1/ane:l2 and ane:l3/ane:l4 can still be aggregated in a similar
   way as in Figure 4 by setting the routingcost of ane:1 and ane:2 to 3
   and 2 respectively.  However, we cannot remove the redundant network
   element (ane:l5 in this case) directly because the resultant path
   vectors (Figure 9) would not provide the same routingcost information
   as in the original path vector.





Gao, et al.             Expires September 3, 2018               [Page 7]


Internet-Draft          Compressing Path Vectors              March 2018


                  path vectors:
                      eh1: [ eh2: [ane:1]]
                      eh3: [ eh4: [ane:2]]

                  abstract network element property map:
                      ane:1  : 100 Mbps, 3
                      ane:2  : 100 Mbps, 2

      Figure 9: Path Vectors after Removing Redundant Network Element

   A further observation is that since the bandwidth constraint of
   ane:l5 is redundant, it can be equally represented as two abstract
   network elements ane:a5 and ane:b5, as shown in Figure 10.

                  path vectors:
                      eh1: [ eh2: [ane:1, ane:a5]]
                      eh3: [ eh4: [ane:2, ane:b5]]

                  abstract network element property map:
                      ane:1  : 100 Mbps, 3
                      ane:2  : 100 Mbps, 2
                      ane:a5 : 200 Mbps, 1
                      ane:b5 : 200 Mbps, 1

             Figure 10: Path Vectors after Decomposing ane:l5

   Since ane:1/ane:a5 and ane:2/ane:b5 can be aggregated as ane:3 and
   ane:4 respectively, the final path vectors only contain two network
   elements, as shown in Figure 11.

                  path vectors:
                      eh1: [ eh2: [ane:1]]
                      eh3: [ eh4: [ane:2]]

                  abstract network element property map:
                      ane:1  : 100 Mbps, 4
                      ane:2  : 100 Mbps, 3

    Figure 11: Path Vectors after Merging ane:1/ane:a5 and ane:2/ane:b5

   One can verify that this path vector response has just the same
   information as in Figure 6 but contains much less contents.

5.  Compression Algorithms

   To provide a guideline on how path vectors MIGHT be compressed, this
   section describes the details of the algorithms for the three
   aforementioned cases:



Gao, et al.             Expires September 3, 2018               [Page 8]


Internet-Draft          Compressing Path Vectors              March 2018


   1.  Equivalent aggregation (EQUIV_AGGR), which compresses the
       original path vectors by aggregating the network elements with
       the same set of pairs as shown in Section 4.1;

   2.  Identification of redundant constraints (IS_REDUNDANT), which
       compresses the original path vectors by removing the network
       elements that provide only redundant information as shown in
       Section 4.2;

   3.  Equivalent decomposition (EQUIV_DECOMP), which compresses the
       original path vectors by decomposing redundant network elements
       to obtain the same end-to-end routing metrics as shown in
       Section 4.3.

5.1.  Equivalent Aggregation

5.1.1.  Parameters and Variables

   The equivalent aggregation algorithm takes 3 parameters: the set of
   network elements "V", the set of relevant host pairs "P" and the set
   of metrics "M".

   Set of network elements V:  The set of network elements consists of
      all the network elements that exists in the original path vectors.
      The "i"-th network element in "V" is denoted as "v_i".

   Set of relevant host pairs P:  The "i"-th element in "P" is denoted
      as "p_i".  It represents the set of (src, dst) pairs whose paths
      traverse "v_i" in the original path vectors.

   Set of metrics M:  The "i-th" element in "M" is denoted as "m_i".  It
      represents the set of metrics associated with network element
      "v_i".

   The output of the equivalent aggregation algorithm is a new set of
   network elements "V'", a new set of relevant host pairs "P'" and a
   new set of metrics "M'", i.e., "V', P', M' = EQUIV_AGGR(V, P, M)".

5.1.2.  Algorithm Description

   1.  Set "V'", "P'", "M'" to empty sets.  Set "k" to 0.  Go to step 2.

   2.  If "V" is empty, go to step 6.  Otherwise, go to step 3.

   3.  Select an arbitrary element "v_i" from "V", remove "v_i" from "V"
       and go to step 4.





Gao, et al.             Expires September 3, 2018               [Page 9]


Internet-Draft          Compressing Path Vectors              March 2018


   4.  For any element "v_j" in "V", if "p_i = p_j", remove "v_j" from
       "V" and update "m_i" with "m_j", i.e., "m_i = UPDATE(m_i, m_j)"
       (which will be explained later).  Go to step 5.

   5.  Increment "k" by 1, let "v'_k = v_i", "p'_k = p_i" and "m'_k =
       m_i".  Go to step 2.

   6.  Return "V'", "P'", and "M'"

   The process of update "m_i" with "m_j" depends on the metric types.
   For example, for routingcost and hopcount, the update is numerical
   addition, while for bandwidth, the update is calculating the minimum.
   The UPDATE function for some common metrics are listed in Table 2.

          +--------------+------------------------+------------+
          | metric       | UPDATE(x, y)           | default    |
          +--------------+------------------------+------------+
          | hopcount     | x + y                  | 0          |
          | routingcost  | x + y                  | 0          |
          | bandwidth    | min(x, y)              | +infinity  |
          | loss rate    | 1 - (1 - x) * (1 - y)  | 0          |
          +--------------+------------------------+------------+

               Table 2: UPDATE Function of Different Metrics

5.1.3.  Example

   Consider the path vectors in Figure 2 which can be represented as:

   V     = { ane:l1, ane:l2, ane:l3, ane:l4, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh1->eh2 }
   p_3   = { eh3->eh4 }
   p_4   = { eh3->eh4 }
   p_5   = { eh1->eh2, eh3->eh4 }

   m_1   = 100 Mbps
   m_2   = 100 Mbps
   m_3   = 100 Mbps
   m_4   = 100 Mbps
   m_5   = 100 Mbps

   As "p_1 = p_2" and "p_3 = p_4", the resultant attributes after the
   aggregation become:






Gao, et al.             Expires September 3, 2018              [Page 10]


Internet-Draft          Compressing Path Vectors              March 2018


   V'    = { ane:1, ane:2, ane:l5 }

   p'_1  = { eh1->eh2 } = p_1 = p_2
   p'_2  = { eh3->eh4 } = p_3 = p_4
   p'_3  = { eh1->eh2, eh3->eh4 } = p_5

   m'_1  = 100 Mbps = UPDATE(m_1, m_2)
   m'_2  = 100 Mbps = UPDATE(m_3, m_4)
   m'_3  = 100 Mbps = m_5

5.2.  Redundant Network Element Identification

5.2.1.  Parameters and Variables

   The redundant network element identification algorithm is based on
   the algorithm introduced by Telgen [TELGEN83].  It takes 3
   parameters: the set of network elements "V", the set of relevant host
   pairs "P" and the set of available bandwidth values "B".

   "V", "v_i", "P" and "p_i" are defined the same way as in
   Section 5.1.1.

   Set of available bandwidth values B:  The "i"-th element in "B" is
      denoted as "b_i".  It represents the available bandwidth for
      network element "v_i".

   The output of the IS_REDUNDANT function is a set of indices "R",
   which represents the indices of network elements whose bandwidth
   constraints are redundant, i.e., "R = IS_REDUNDANT(V, P, B)".

   In addition to the parameters and output values, the algorithm also
   maintains the following variables:

   Set of host pairs H:  The "i"-th element of "H" is denoted as "h_i".
      It represents a (src, dst) pair ever appeared in the path vector
      query.  "H" is the union of all "p_i" in "P".

   Set of bandwidth constraints C:  The "i"-th element of "C" is denoted
      as "c_i".  It represents a linear bandwidth constraint on the
      flows between the end host pairs.  The constraint "c_i" has the
      form of "a_i x <= b_i" where "a_i" is a row vector of 0-1
      coefficients derived from "p_i", "x" is a column vector
      representing the bandwidth of all the host pairs, and "b_i" is the
      available bandwidth of "v_i".







Gao, et al.             Expires September 3, 2018              [Page 11]


Internet-Draft          Compressing Path Vectors              March 2018


5.2.2.  Algorithm Description

   1.  The first step is to convert a network element to its bandwidth
       constraint "c_i".  The bound "b_i" is directly obtained as the
       available bandwidth and the coefficients "a_i" are computed as:

               1  if h_j in p_i
       a_ij =
               0  otherwise.

       Set "R" to an empty set.  Go to step 2.

   2.  For each "i", solve the following linear programming problem:

                   y_i = max a_i x
       subject to:
           a_j x <= b_j, j = 1..|V|, i <> j

       Go to step 3.

   3.  For each "i", if "y_i <= b_i", "c_i" is redundant and we say
       "v_i" is redundant, "R = UNION(R, {i})".  Go to step 4.

   4.  Return "R".

5.2.3.  Example

   Consider the path vectors in Figure 4 such that the input to the
   IS_REDUNDANT algorithm is as follows.

   V     = { ane:1, ane:2, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh3->eh4 }
   p_3   = { eh1->eh2, eh3->eh4 }

   b_1   = 100 Mbps
   b_2   = 100 Mbps
   b_3   = 100 Mbps

   With that information, one can follow the algorithm and get:










Gao, et al.             Expires September 3, 2018              [Page 12]


Internet-Draft          Compressing Path Vectors              March 2018


   c_1:   x1       <= 100
   c_2:        x2  <= 100
   c_3:   x1 + x2  <= 100

   y_1  = 100 Mbps <= b_1
   y_2  = 100 Mbps <= b_2
   y_3  = 200 Mbps >  b_3

   R    = IS_REDUNDANT(V, P, B) = { 1, 2 }

5.3.  Equivalent Decomposition

5.3.1.  Parameters and Variables

   The equivalent decomposition algorithm takes 4 parameters: the set of
   network elements "V", the set of relevant host pairs "P", the set of
   metrics "M" and the set of redundant network elements "R".

   "V", "P" and "M" are as defined as in Section 5.1.1.  If the "j"-th
   metric is bandwidth, we can construct the set of available bandwidth
   values "B" as "b_i = m_ij" and "R" is the output of the redundant
   network element identification procedure, i.e. "R = IS_REDUNDANT(V,
   P, B)".  Otherwise, if bandwidth is not included in the metrics, "R"
   is {1, ..., |V|}.

   The output of the function EQUIV_DECOMP is a new set of network
   elements "V'", a new set of relevant host pairs "P'", and a new set
   of metrics "M'", i.e., "V', P', M' = EQUIV_DECOMP(V, P, M, R)".

5.3.2.  Algorithm Description

   1.  Set "V'", "P'", "M'" to empty sets.  Set "k" to 0.  Go to step 2.

   2.  For each "i" such that "i" in "R", go to step 3.  After
       processing each "i", go to step 7.

   3.  For each "j" such that "j <> i", go to step 4.  After processing
       each "j", go to step 6.

   4.  If "p_j" is a subset of "p_i", go to step 5.  Otherwise go to
       step 3.

   5.  Let "p_i = p_i \ p_j" and "m_j = UPDATE(m_j, m_i)".  Go to step
       3.

   6.  If "p_i" is not empty, increment "k" by 1 and let "v'_k = v_i",
       "p'_k = p_i" and "m'_k = m_i".  Go to step 2.




Gao, et al.             Expires September 3, 2018              [Page 13]


Internet-Draft          Compressing Path Vectors              March 2018


   7.  For each "i" such that "i" is not in "R", go to step 8.  After
       processing each "i", go to step 9.

   8.  Increment "k" by 1 and let "v'_k = v_i", "p'_k = p_i", "m'_k =
       m_i".  Go to step 7.

   9.  Return "V'", "P'" and "M'".

5.3.3.  Example

   Consider the case in Section 4.3.  Before the decomposition, the
   input to the algorithm is as follows:

   V     = { ane:1, ane:2, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh3->eh4 }
   p_3   = { eh1->eh2, eh3->eh4 }

   m_1   = { bw: 100 Mbps, rc: 3 }
   m_2   = { bw: 100 Mbps, rc: 2 }
   m_3   = { bw: 200 Mbps, rc: 1 }

   R     = { 3 }

   Since there is only one element in "R", "v_i = ane:l5".

   After the first iteration of steps 3-5 with "v_j = ane:1":

   V     = { ane:1, ane:2, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh3->eh4 }
   p_3   = { eh3->eh4 }

   m_1   = { bw: 100 Mbps, rc: 4 }
   m_2   = { bw: 100 Mbps, rc: 2 }
   m_3   = { bw: 200 Mbps, rc: 1 }

   V'    = { }
   k     = 0

   After the second iteration of steps 3-5 with "v_j = ane:2":








Gao, et al.             Expires September 3, 2018              [Page 14]


Internet-Draft          Compressing Path Vectors              March 2018


   V     = { ane:1, ane:2, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh3->eh4 }
   p_3   = { }

   m_1   = { bw: 100 Mbps, rc: 4 }
   m_2   = { bw: 100 Mbps, rc: 3 }
   m_3   = { bw: 200 Mbps, rc: 1 }

   V'    = { }
   k     = 0

   After step 6, since "p_3" is now empty, it just goes back to step 2.
   At step 2, since all indices in "R" has been processed, it goes to
   step 7.

   After the first iteration of steps 7-8 with "i = 1":

   V     = { ane:1, ane:2, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh3->eh4 }
   p_3   = { }

   m_1   = { bw: 100 Mbps, rc: 4 }
   m_2   = { bw: 100 Mbps, rc: 3 }
   m_3   = { bw: 200 Mbps, rc: 1 }

   V'    = { ane:1 }
   k     = 1

   p'_1  = { eh1->eh2 } = p_1

   m'_1  = { bw: 100 Mbps, rc: 4 } = m_1

   After the second iteration of steps 7-8 with "i = 2":














Gao, et al.             Expires September 3, 2018              [Page 15]


Internet-Draft          Compressing Path Vectors              March 2018


   V     = { ane:1, ane:2, ane:l5 }

   p_1   = { eh1->eh2 }
   p_2   = { eh3->eh4 }
   p_3   = { }

   m_1   = { bw: 100 Mbps, rc: 4 }
   m_2   = { bw: 100 Mbps, rc: 3 }
   m_3   = { bw: 200 Mbps, rc: 1 }

   V'    = { ane:1, ane:2 }
   k     = 2

   p'_1  = { eh1->eh2 }
   p'_2  = { eh3->eh4 } = p_2

   m'_1  = { bw: 100 Mbps, rc: 4 }
   m'_2  = { bw: 100 Mbps, rc: 3 } = m_2

   So the final output of EQUIV_DECOMP is:

   V'    = { ane:1, ane:2 }

   p'_1  = { eh1->eh2 }
   p'_2  = { eh3->eh4 }

   m'_1  = { bw: 100 Mbps, rc: 4 }
   m'_2  = { bw: 100 Mbps, rc: 3 }

5.4.  Execution Order

   As the examples demonstrate, the three algorithms MUST be executed in
   the same order as they are introduced, i.e., one MUST conduct
   "EQUIV_AGGR" before "IS_REDUNDANT" or "EQUIV_DECOMP", and conduct
   "IS_REDUNDANT" before "EQUIV_DECOMP".  Otherwise, the results of the
   compressed path vectors MAY NOT be correct.

6.  Encoding/Decoding Path Vectors

   The three algorithms work mostly with network elements.  Existing
   path vectors must be decoded before they can be passed on to the
   algorithms and the compressed results must be encoded as path vectors
   before they are sent to the clients.  The decoding and encoding
   processes are specified as below.







Gao, et al.             Expires September 3, 2018              [Page 16]


Internet-Draft          Compressing Path Vectors              March 2018


6.1.  Decoding Path Vectors

6.1.1.  Parameters and Variables

   The decoding algorithm DECODE takes a path vector response, which
   consists of the path vector part "PV" and the element property part
   "E".

   Path vectors PV:  The path vector part has a format of a CostMap
      (EndpointCostMap) where the cost value is a list of abstract
      network element names.  We say a PID (endpoint address) "i" is IN
      "PV" if and only if there is an entry "i" in the cost-map
      (endpoint-cost-map), and denote the entry value as "PV[i]".
      Similarly, we say a PID (endpoint address) "j" is IN "PV[i]" if
      and only if there is an entry "j" in the DstCosts of "i", whose
      value is denoted as "PV[i][j]".

   Element property map E:  The element property map "E" maps an
      abstract network element name to its properties.  We denote "E[n]"
      as the properties of element with name "n" and "E[n][pn]" as the
      value of property "pn".

   The algorithm returns the set of elements "V", the set of relevant
   host pairs "P", the set of metrics "M" and the available bandwidth
   "B", as defined in Section 5.1.1 and Section 5.2.1.  The algorithm
   uses a "SET" function which transforms a list into a set, and uses a
   "NAME" function which maps an integer in [1, K] to a unique property
   name where there are K properties in "E".

6.1.2.  Algorithm Description

   1.   Set "V", "P", "M" and "B" to empty sets.  Set "k" to 0.  Go to
        step 2.

   2.   For each "i IN PV", go to step 3.  After processing each "i", go
        to step 8.

   3.   For each "j IN PV[i]", go to step 4.  After processing each "j",
        go to step 2.

   4.   For each "n" in "SET(PV[i][j])", go to step 5.  After processing
        each "n", go to step 3.

   5.   If "n" is not in "V", go to step 6.  Otherwise, go to step 7.

   6.   Increment "k" by 1 and let "v_k = n", "p_k = { i->j }".  Go to
        step 4.




Gao, et al.             Expires September 3, 2018              [Page 17]


Internet-Draft          Compressing Path Vectors              March 2018


   7.   Find the index of "n" in "V" denoted as "a", let "p_a =
        UNION(p_a, {i->j})".  Go to step 4.

   8.   For each "i" from 1 to |V|, go to step 9.  After processing all
        "i", go to step 11.

   9.   For each "j" from 1 to K, go to step 10.  After processing all
        "j", go back to step 8.

   10.  If "NAME(j) = 'availbw'", let "b_i = E[v_i][NAME(j)]".  Let
        "m_ij = E[v_i][NAME(j)]".

   11.  Return "V", "P", "M" and "B".

6.1.3.  Example

   Consider the following example:

   HTTP/1.1 200 OK
   Content-Length: [TBD]
   Content-Type: multipart/related; boundary=example-2

   --example-2
   Content-Type: application/alto-endpointcost+json

   {
     "meta": {
       "cost-types": [
         {"cost-mode": "array", "cost-metric": "ane-path"}
       ]
     }
     "endpoint-cost-map": {
       "ipv4:192.0.2.2": {
         "ipv4:192.0.2.89": [ "ane:L1", "ane:L3", "ane:L4" ],
         "ipv4:203.0.113.45": [ "ane:L1", "ane:L4", "ane:L5" ]
       }
     }
   }













Gao, et al.             Expires September 3, 2018              [Page 18]


Internet-Draft          Compressing Path Vectors              March 2018


   --example-2
   Content-Type: application/alto-propmap+json

   {
     "property-map": {
       "ane:L1": { "availbw": 50 },
       "ane:L3": { "availbw": 48 },
       "ane:L4": { "availbw": 55 },
       "ane:L5": { "availbw": 60 },
       "ane:L7": { "availbw": 35 }
     }
   }

   --example-2--

   After the first iteration of Lines 2-5:

   V      = { ane:L1, ane:L3, ane:L4 }

   p_1    = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
   p_2    = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
   p_3    = { ipv4:192.0.2.2->ipv4:192.0.2.89 }.

   After the second iteration of Lines 2-5:

   V      = { ane:L1, ane:L3, ane:L4, ane:L5 }

   p_1    = { ipv4:192.0.2.2->ipv4:192.0.2.89,
              ipv4:192.0.2.2->ipv4:203.0.113.45 }
   p_2    = { ipv4:192.0.2.2->ipv4:192.0.2.89,
              ipv4:192.0.2.2->ipv4:203.0.113.45 }
   p_3    = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
   p_4    = { ipv4:192.0.2.2->ipv4:203.0.113.45 }.

   After the first iteration of Lines 6-9 with "i = 1":

   m_1    = [50]

   b_1    = 50

   After all four iterations of Lines 6-9:










Gao, et al.             Expires September 3, 2018              [Page 19]


Internet-Draft          Compressing Path Vectors              March 2018


   m_1    = [50]
   m_2    = [48]
   m_3    = [55]
   m_4    = [60]

   b_1    = 50
   b_2    = 48
   b_3    = 55
   b_4    = 60

   The decoded information can be passed on to "EQUIV_AGGR",
   "IS_REDUNDANT" and "EQUIV_DECOMP" for compression.

6.2.  Encoding Path Vectors

6.2.1.  Parameters and Variables

   The algorithm ENCODE is the reverse process of DECODE.  It takes the
   parameters "V", "P", "M" and constructs the path vector results.

   The parameters are defined as in Section 5.1.1 and Section 5.2.1.

   The algorithm also uses the NAME function in Section 6.1.1 which MUST
   return the same results in a paired ENCODE/DECODE process, and the
   "APPEND(L, e)" function which adds element "e" to list "L".

6.2.2.  Algorithm Description

   1.  Set "PV={}", "E = {}".  Go to step 2.

   2.  For each "v_i" in "V", go to step 3.  If all "v_i" is processed,
       go to step XX.

   3.  For each "a->b" in "p_i", go to step 4.  If all such "a->b" is
       processed, go to step 6.

   4.  If "a" is not in "PV", let "PV[a] = {}".  Go to step 5.

   5.  If "b" is not in "PV[a]", let "PV[a][b] = [v_i]".  Otherwise, let
       "PV[a][b] = APPEND(PV[a][b], v_i)".  Go to step 2.

   6.  For each index "k" in [1, K], go to step 7.  If all "k" is
       processed, go to step 1.

   7.  Set "E[v_i][NAME(k)] = m_ik".  Go to step 6.

   8.  Return "PV" and "E".




Gao, et al.             Expires September 3, 2018              [Page 20]


Internet-Draft          Compressing Path Vectors              March 2018


6.2.3.  Example

   We consider the encoding of the decoded example in Section 6.1.3.

   V      = { ane:L1, ane:L3, ane:L4, ane:L5 }

   p_1    = { ipv4:192.0.2.2->ipv4:192.0.2.89,
              ipv4:192.0.2.2->ipv4:203.0.113.45 }
   p_2    = { ipv4:192.0.2.2->ipv4:192.0.2.89,
              ipv4:192.0.2.2->ipv4:203.0.113.45 }
   p_3    = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
   p_4    = { ipv4:192.0.2.2->ipv4:203.0.113.45 }

   m_1    = [50]
   m_2    = [48]
   m_3    = [55]
   m_4    = [60]

   After the first iteration of steps 2-7:

   PV[ipv4:192.0.2.2][ipv4:192.0.2.89  ] = [ane:L1]
   PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1]

   E[ane:L1]["availbw"]                = 50

   After the second iteration:

   PV[ipv4:192.0.2.2][ipv4:192.0.2.89  ] = [ane:L1, ane:L3]
   PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3]

   E[ane:L1]["availbw"]                = 50
   E[ane:L3]["availbw"]                = 48

   After the third iteration:

   PV[ipv4:192.0.2.2][ipv4:192.0.2.89  ] = [ane:L1, ane:L3, ane:L4]
   PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3]

   E[ane:L1]["availbw"]                = 50
   E[ane:L3]["availbw"]                = 48
   E[ane:L4]["availbw"]                = 55

   After the fourth iteration:








Gao, et al.             Expires September 3, 2018              [Page 21]


Internet-Draft          Compressing Path Vectors              March 2018


   PV[ipv4:192.0.2.2][ipv4:192.0.2.89  ] = [ane:L1, ane:L3, ane:L4]
   PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3, ane:L5]

   E[ane:L1]["availbw"]                = 50
   E[ane:L3]["availbw"]                = 48
   E[ane:L4]["availbw"]                = 55
   E[ane:L5]["availbw"]                = 60

   Eventually, one can use the previous information to construct the
   endpoint cost service response.

   HTTP/1.1 200 OK
   Content-Length: [TBD]
   Content-Type: multipart/related; boundary=example-2

   --example-2
   Content-Type: application/alto-endpointcost+json

   {
     "meta": {
       "cost-types": [
         {"cost-mode": "array", "cost-metric": "ane-path"}
       ]
     }
     "endpoint-cost-map": {
       "ipv4:192.0.2.2": {
         "ipv4:192.0.2.89": [ "ane:L1", "ane:L3", "ane:L4" ],
         "ipv4:203.0.113.45": [ "ane:L1", "ane:L4", "ane:L5" ]
       }
     }
   }

   --example-2
   Content-Type: application/alto-propmap+json

   {
     "property-map": {
       "ane:L1": { "availbw": 50 },
       "ane:L3": { "availbw": 48 },
       "ane:L4": { "availbw": 55 },
       "ane:L5": { "availbw": 60 },
     }
   }

   --example-2--






Gao, et al.             Expires September 3, 2018              [Page 22]


Internet-Draft          Compressing Path Vectors              March 2018


6.3.  Compatibility

   When the path vector extension is used with other extensions, such as
   [I-D.ietf-alto-cost-calendar] and [I-D.ietf-alto-multi-cost], the
   decoding and the encoding MUST only apply on the path vector part and
   leave the other attributes as they are.

   Hence, this extension does not change the compatibility between the
   original path vector extension and other extensions.

7.  Security Considerations

   This document does not introduce any privacy or security issue on
   ALTO servers not already present in the base ALTO protocol or in the
   path vector extension.

   The algorithms specified in this document can even help protect the
   privacy of network providers by conducting irreversible
   transformations on the original path vector.

8.  IANA Considerations

   This document does not define any new media type or introduce any new
   IANA consideration.

9.  Acknowledgments

   The authors would like to thank Dr. Qiao Xiang, Mr. Jingxuan Zhang
   (Tongji University), Prof. Jun Bi (Tsinghua University) and
   Dr. Andreas Voellmy (Yale University) for their early engagement and
   discussions.

10.  References

10.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,
              <http://www.rfc-editor.org/info/rfc2119>.

10.2.  Informative References

   [I-D.ietf-alto-cost-calendar]
              Randriamasy, S., Yang, Y., Wu, Q., Lingli, D., and N.
              Schwan, "ALTO Cost Calendar", draft-ietf-alto-cost-
              calendar-01 (work in progress), February 2017.




Gao, et al.             Expires September 3, 2018              [Page 23]


Internet-Draft          Compressing Path Vectors              March 2018


   [I-D.ietf-alto-incr-update-sse]
              Roome, W. and Y. Yang, "ALTO Incremental Updates Using
              Server-Sent Events (SSE)", draft-ietf-alto-incr-update-
              sse-02 (work in progress), April 2016.

   [I-D.ietf-alto-multi-cost]
              Randriamasy, S., Roome, W., and N. Schwan, "Multi-Cost
              ALTO", draft-ietf-alto-multi-cost-10 (work in progress),
              April 2017.

   [I-D.ietf-alto-path-vector]
              Bernstein, G., Chen, S., Gao, K., Lee, Y., Roome, W.,
              Scharf, M., Yang, Y., and J. Zhang, "ALTO Extension: Path
              Vector Cost Mode", draft-ietf-alto-path-vector-00 (work in
              progress), May 2017.

   [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,
              <http://www.rfc-editor.org/info/rfc7285>.

   [TELGEN83]
              Telgen, J., "Identifying Redundant Constraints and
              Implicit Equalities in Systems of Linear Constraints",
              Management Science , Volume 29, Issue 10,
              DOI 10.1287/mnsc.29.10.1209, 1983,
              <http://pubsonline.informs.org/doi/abs/10.1287/
              mnsc.29.10.1209>.

Authors' Addresses

   Kai Gao
   Tsinghua University
   30 Shuangqinglu Street
   Beijing  100084
   China

   Email: gaok12@mails.tsinghua.edu.cn


   Xin (Tony) Wang
   Tongji University
   4800 CaoAn Road
   Shanghai  210000
   China

   Email: xinwang2014@hotmail.com



Gao, et al.             Expires September 3, 2018              [Page 24]


Internet-Draft          Compressing Path Vectors              March 2018


   Qiao Xiang
   Tongji/Yale University
   51 Prospect Street
   New Haven, CT
   USA

   Email: qiao.xiang@cs.yale.edu


   Chen Gu
   Tongji University
   4800 CaoAn Road
   Shanghai  210000
   China

   Email: gc19931011jy@gmail.com


   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 September 3, 2018              [Page 25]


Html markup produced by rfcmarkup 1.127, available from https://tools.ietf.org/tools/rfcmarkup/