ALTO WG K. Gao Internet-Draft Tsinghua University Intended status: Standards Track X. Wang Expires: June 15, 2018 Tongji University Q. Xiang Tongji/Yale University C. Gu Tongji University Y. Yang Yale University G. Chen Huawei December 12, 2017 A Recommendation for Compressing ALTO Path Vectors draft-gao-alto-routing-state-abstraction-07.txt Abstract The path vector extension [I-D.ietf-alto-path-vector] has extended the original ALTO protocol [RFC7285] with the ability to represent a more detailed view of the network, containing not only end-to-end metrics 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 June 15, 2018 [Page 1] Internet-Draft Compressing Path Vectors December 2017 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 June 15, 2018. Copyright Notice Copyright (c) 2017 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 and -06 . . . . . . . . . 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 . . . . . . . . 10 5.3. Equivalent Decomposition . . . . . . . . . . . . . . . . 12 6. Encoding/Decoding Path Vectors . . . . . . . . . . . . . . . 14 6.1. Decoding Path Vectors . . . . . . . . . . . . . . . . . . 14 6.2. Encoding Path Vectors . . . . . . . . . . . . . . . . . . 17 6.3. Compatibility . . . . . . . . . . . . . . . . . . . . . . 20 7. Security Considerations . . . . . . . . . . . . . . . . . . . 21 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 21 Gao, et al. Expires June 15, 2018 [Page 2] Internet-Draft Compressing Path Vectors December 2017 10.1. Normative References . . . . . . . . . . . . . . . . . . 21 10.2. Informative References . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 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. This has enabled ALTO clients to query more sophisticated information such as shared bottlenecks, by which ALTO clients can schedule their flows properly to avoid congestion and to better utilize the network resources. However, 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 view, 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 the equivalent transformation algorithm that identifies redundant abstract network elements and reduces 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 June 15, 2018 [Page 3] Internet-Draft Compressing Path Vectors December 2017 decisions between efficiency and privacy. A reference implementation of redundancy check algorithm is also described in this document. Furthermore, the redundancy check algorithm can generate filters for incremental updates of path vector queries. It can also accept customized parameters from ALTO clients to achieve even better compression results. This document is organized as follows. Section 4 gives a concrete example to demonstrate the importance of compressing path vectors. Finally, Section 7 and Section 8 discuss security and IANA considerations. 2. Changes Since Version -03, -04, -05 and -06 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. 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. Switches sw1/sw3 provide access on one side, s2/s4 provide access on the other 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 June 15, 2018 [Page 4] Internet-Draft Compressing Path Vectors December 2017 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 June 15, 2018 [Page 5] Internet-Draft Compressing Path Vectors December 2017 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, it can be seen 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 June 15, 2018 [Page 6] Internet-Draft Compressing Path Vectors December 2017 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 routing are requested, as shown in Figure 6. 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 June 15, 2018 [Page 7] Internet-Draft Compressing Path Vectors December 2017 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 links 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 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 June 15, 2018 [Page 8] Internet-Draft Compressing Path Vectors December 2017 1. Equivalent aggregation (EQUIV_AGGR), which compresses the original path vectors by aggregating the network elements traversed by the same set of flows 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 pairs for each network element "{P_i}" and the corresponding set of metrics for each network element "{M_i}". 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". Specifically, each network element "v_i" contains the following attributes: Set of pairs P_i: "P_i" represents the set of (src, dst) pairs whose paths traverse "vi" in the original path vectors. Set of metrics M_i: "M_i" 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'" and the new attributes "P'_i" and "M'_i", i.e., "V', {P'_i}, {M'_i} = EQUIV_AGGR(V, {P_i}, {M_i})". 5.1.2. Algorithm Description 1. Set "V'" to an empty set. 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 June 15, 2018 [Page 9] Internet-Draft Compressing Path Vectors December 2017 4. For an 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. Add "v_i" to "V'" and set "P'_i = P_i", "M'_i = M_i". Go to step 2. 6. Return "V'" and "{P'_i}", "{M'_i}" The process of update "M_i" with "M_j" depends on the types of metrics. 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 See Section 4.1. 5.2. Redundant Network Element Identification 5.2.1. Parameters and Variables The redundant network element identification algorithm takes 3 parameters: the set of network elements "V", the corresponding set of host pairs for each network element "{P_i}" and the available bandwidth for each network element "{b_i}". "V", "v_i" and "{P_i}" are defined the same way as in Section 5.1.1. The available bandwidth b_i: It represents the available bandwidth for network element "v_i". The output of the IS_REDUNDANT function is a set of network element "V'", which represents those network elements whose bandwidth constraints are redundant, i.e., "V' = IS_REDUNDANT(V, {P_i}, {b_i})". Gao, et al. Expires June 15, 2018 [Page 10] Internet-Draft Compressing Path Vectors December 2017 In addition to the parameters and output values, the algorithm also maintains the following variables: Bandwidth constraint for i-th network element c_i: Each network element represents a linear bandwidth constraint on the flows between the end host pairs. The constraint "c_i" has the form of "a_ix <= b_i" where "a_i" is a vector of coefficients and "b_i" is the available bandwidth of "v_i". 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 j in P_i a_ij = 0 otherwise. Go to step 2. 2. For each "i", solve the following linear programming problem: y_i = max a_ix subject to: a_jx <= b_j, j = 1..n, i <> j Go to step 3. 3. For each "i", if "y_i <= b_i", "c_i" is redundant and thus "v_i" is redundant, "V' = V' U {v_i}". Go to step 4. 4. Return "V'". 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_l5 = { eh1->eh2, eh3->eh4 } b_1 = 100 Mbps b_2 = 100 Mbps b_l5 = 100 Mbps Gao, et al. Expires June 15, 2018 [Page 11] Internet-Draft Compressing Path Vectors December 2017 With that information, one can follow the algorithm and get: 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_l5 = 200 Mbps > b_l5 V' = IS_REDUNDANT(V, {P_i}, {b_i}) = { ane:1, ane: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 pairs for each network element "P_i", the set of metrics for each network element "M_i" and the set of redundant network elements "V'". "V", "{P_i}" and "{M_i}" are as defined as in Section 5.1.1 and "V'" is the output of the redundant network element identification procedure. The output of the function EQUIV_DECOMP is a new set of network elements "V''" and the new attributes "{P''_i}" and "{M''_i}", i.e., "V'', {P''_i}, {M''_i} = EQUIV_DECOMP(V, {P_i}, {M_i}, V')". 5.3.2. Algorithm Description 1. Set "V'' = V \ V'". 2. For each "i" such that "v_i" in "V'", go to step 3. After processing each "i", go to step 7. 3. For each "j" such that "v_j" in "V \ {v_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, let "V'' = V'' U {v_i}". Go to step 2. Gao, et al. Expires June 15, 2018 [Page 12] Internet-Draft Compressing Path Vectors December 2017 7. For each "i" such that "v_i" in "V''", set "P''_i = P_i" and "M''_i = M_i". Go to step 8. 8. Return "V''", "{P''_i}" and "{M''_i}". 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_l5 = { eh1->eh2, eh3->eh4 } M_1 = { bw: 100 Mbps, rc: 3} M_2 = { bw: 100 Mbps, rc: 2} M_l5 = { bw: 200 Mbps, rc: 1} V' = { ane:l5 } Since there is only one element in "V'", "v_i = ane:l5". After the first iteration of steps 3-6 with "v_j = ane:1": P_1 = { eh1->eh2 } P_2 = { eh3->eh4 } P_l5 = { eh3->eh4 } M_1 = { bw: 100 Mbps, rc: 4} M_2 = { bw: 100 Mbps, rc: 2} M_l5 = { bw: 200 Mbps, rc: 1} V'' = { ane:1, ane:2 } After the second iteration of steps 3-6 with "v_j = ane:2": P_1 = { eh1->eh2 } P_2 = { eh3->eh4 } P_l5 = { } M_1 = { bw: 100 Mbps, rc: 4} M_2 = { bw: 100 Mbps, rc: 3} M_l5 = { bw: 200 Mbps, rc: 1} V'' = { ane:1, ane:2 } Gao, et al. Expires June 15, 2018 [Page 13] Internet-Draft Compressing Path Vectors December 2017 So the final output of EQUIV_DECOMP is: V'' = { ane:1, ane:2 } P''_1 = P_1 = { eh1->eh2 } P''_2 = P_2 = { eh3->eh4 } M''_1 = M_1 = { bw: 100 Mbps, rc: 4 } M''_2 = M_2 = { bw: 100 Mbps, rc: 3 } V'', {P''_i}, {M''_i} = EQUIV_DECOMP(V, {P_i}, {M_i}, V') 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. 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 pairs "{P_i}", the set of metrics "{M_i}" and the available bandwidth "{b_i}", 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". Gao, et al. Expires June 15, 2018 [Page 14] Internet-Draft Compressing Path Vectors December 2017 6.1.2. Algorithm Description 1. Set "V = {}", "P = {P_i = {}}". Go to step 2. 2. For each "i IN PV", go to step 3. After processing each "i", go to step 6. 3. For each "j IN PV[i]", go to step 4. After processing each "j", go to step 2. 4. Update "V" as the union of "V" and "SET(PV[i][j])", e.g., "V = V U SET(PV[i][j])". For each "n" in "SET(PV[i][j])", go to step 5. After processing each "n", go to step 3. 5. Update "P_n" as the union of "P_n" and "i->j", e.g., "P_n = P_n U {i->j}". Go to step 4. 6. Set "M = {M_i = []}", "B = {b_i = +infinity}". Go to step 7. 7. For each "n" in "V", go to step 8. After processing each "n", go to step 10. 8. For each index "i" in [1, K], go to step 9. 9. If "NAME(i) = 'availbw'", "b_n = E[n][NAME(i)]". "M_n[i] = E[n][NAME(i)]". Go to step 7. 10. Return "V", "{P_i}", "{M_i}", "{b_i}". 6.1.3. Example Consider the following example: Gao, et al. Expires June 15, 2018 [Page 15] Internet-Draft Compressing Path Vectors December 2017 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:L001", "ane:L003", "ane:L004" ], "ipv4:203.0.113.45": [ "ane:L001", "ane:L004", "ane:L005" ] } } } --example-2 Content-Type: application/alto-propmap+json { "property-map": { "ane:L001": { "availbw": 50 }, "ane:L003": { "availbw": 48 }, "ane:L004": { "availbw": 55 }, "ane:L005": { "availbw": 60 }, "ane:L007": { "availbw": 35 } } } --example-2-- After the first iteration of Lines 2-5: V = { ane:L001, ane:L003, ane:L004 } P_L001 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } P_L003 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } P_L004 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } P_L005 = { }. After the second iteration of Lines 2-5: Gao, et al. Expires June 15, 2018 [Page 16] Internet-Draft Compressing Path Vectors December 2017 V = { ane:L001, ane:L003, ane:L004, ane:L005 } P_L001 = { ipv4:192.0.2.2->ipv4:192.0.2.89, ipv4:192.0.2.2->ipv4:203.0.113.45 } P_L003 = { ipv4:192.0.2.2->ipv4:192.0.2.89, ipv4:192.0.2.2->ipv4:203.0.113.45 } P_L004 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } P_L005 = { ipv4:192.0.2.2->ipv4:203.0.113.45 }. After the first iteration of Lines 6-9 with "n = ane:L001": M_L001 = [50] M_L003 = [] M_L004 = [] M_L005 = [] b_L001 = 50 b_L003 = +infinity b_L004 = +infinity b_L005 = +infinity After the fourth iteration of Lines 6-9: M_L001 = [50] M_L003 = [48] M_L004 = [55] M_L005 = [60] b_L001 = 50 b_L003 = 48 b_L004 = 55 b_L005 = 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_i}", "{M_i}" and constructs the path vector results. The parameters are defined as in Section 5.1.1 and Section 5.2.1. Gao, et al. Expires June 15, 2018 [Page 17] Internet-Draft Compressing Path Vectors December 2017 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_i[k]". Go to step 6. 8. Return "PV" and "E". 6.2.3. Example We consider the encoding of the decoded example in Section 6.1.3. V = { ane:L001, ane:L003, ane:L004, ane:L005 } P_L001 = { ipv4:192.0.2.2->ipv4:192.0.2.89, ipv4:192.0.2.2->ipv4:203.0.113.45 } P_L003 = { ipv4:192.0.2.2->ipv4:192.0.2.89, ipv4:192.0.2.2->ipv4:203.0.113.45 } P_L004 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } P_L005 = { ipv4:192.0.2.2->ipv4:203.0.113.45 }. M_L001 = [50] M_L003 = [48] M_L004 = [55] M_L005 = [60] Gao, et al. Expires June 15, 2018 [Page 18] Internet-Draft Compressing Path Vectors December 2017 After the first iteration: PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L001] PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L001] E[ane:L001]["availbw"] = 50 After the second iteration: PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L001, ane:L003] PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L001, ane:L003] E[ane:L001]["availbw"] = 50 E[ane:L003]["availbw"] = 48 After the third iteration: PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L001, ane:L003, ane:L004] PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L001, ane:L003] E[ane:L001]["availbw"] = 50 E[ane:L003]["availbw"] = 48 E[ane:L004]["availbw"] = 55 After the fourth iteration: PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L001, ane:L003, ane:L004] PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L001, ane:L003, ane:L005] E[ane:L001]["availbw"] = 50 E[ane:L003]["availbw"] = 48 E[ane:L004]["availbw"] = 55 E[ane:L005]["availbw"] = 60 Eventually, one can use the previous information to construct the endpoint cost service response. Gao, et al. Expires June 15, 2018 [Page 19] Internet-Draft Compressing Path Vectors December 2017 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:L001", "ane:L003", "ane:L004" ], "ipv4:203.0.113.45": [ "ane:L001", "ane:L004", "ane:L005" ] } } } --example-2 Content-Type: application/alto-propmap+json { "property-map": { "ane:L001": { "availbw": 50 }, "ane:L003": { "availbw": 48 }, "ane:L004": { "availbw": 55 }, "ane:L005": { "availbw": 60 }, } } --example-2-- 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. Gao, et al. Expires June 15, 2018 [Page 20] Internet-Draft Compressing Path Vectors December 2017 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, . 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. [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. Gao, et al. Expires June 15, 2018 [Page 21] Internet-Draft Compressing Path Vectors December 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, . 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 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 Gao, et al. Expires June 15, 2018 [Page 22] Internet-Draft Compressing Path Vectors December 2017 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 June 15, 2018 [Page 23]