idnits 2.17.1 draft-gao-alto-routing-state-abstraction-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([I-D.ietf-alto-path-vector], [I-D.ietf-alto-incr-update-sse], [RFC7285]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The exact meaning of the all-uppercase expression 'MAY NOT' is not defined in RFC 2119. If it is intended as a requirements expression, it should be rewritten using one of the combinations defined in RFC 2119; otherwise it should not be all-uppercase. == The expression 'MAY NOT', while looking like RFC 2119 requirements text, is not defined in RFC 2119, and should not be used. Consider using 'MUST NOT' instead (if that is what you mean). Found 'MAY NOT' in this paragraph: 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. -- The document date (March 2, 2018) is 2240 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 904 == Missing Reference: 'K' is mentioned on line 904, but not defined == Missing Reference: 'TBD' is mentioned on line 967, but not defined -- Looks like a reference, but probably isn't: '50' on line 924 -- Looks like a reference, but probably isn't: '48' on line 925 -- Looks like a reference, but probably isn't: '55' on line 926 -- Looks like a reference, but probably isn't: '60' on line 927 == Outdated reference: A later version (-21) exists of draft-ietf-alto-cost-calendar-01 == Outdated reference: A later version (-22) exists of draft-ietf-alto-incr-update-sse-02 == Outdated reference: A later version (-25) exists of draft-ietf-alto-path-vector-00 Summary: 1 error (**), 0 flaws (~~), 7 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ALTO WG K. Gao 3 Internet-Draft Tsinghua University 4 Intended status: Standards Track X. Wang 5 Expires: September 3, 2018 Tongji University 6 Q. Xiang 7 Tongji/Yale University 8 C. Gu 9 Tongji University 10 Y. Yang 11 Yale University 12 G. Chen 13 Huawei 14 March 2, 2018 16 Compressing ALTO Path Vectors 17 draft-gao-alto-routing-state-abstraction-08.txt 19 Abstract 21 The path vector extension [I-D.ietf-alto-path-vector] has extended 22 the base ALTO protocol [RFC7285] with the ability to represent a more 23 detailed view of the network which contains not only end-to-end costs 24 but also information about shared bottlenecks. 26 However, the view computed by straw man algorithms can contain 27 redundant information and result in unnecessary communication 28 overhead. The situation gets even worse when certain ALTO extensions 29 are enabled, for example, the incremental update extension 30 [I-D.ietf-alto-incr-update-sse] which continuously pushes data 31 changes to ALTO clients. Redundant information can trigger 32 unnecessary updates. 34 In this document, several algorithms are described which can 35 effectively reduce the redundancy in the network view while still 36 providing the same information as in the original path vectors. 38 Requirements Language 40 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 41 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 42 document are to be interpreted as described in RFC 2119 [RFC2119]. 44 Status of This Memo 46 This Internet-Draft is submitted in full conformance with the 47 provisions of BCP 78 and BCP 79. 49 Internet-Drafts are working documents of the Internet Engineering 50 Task Force (IETF). Note that other groups may also distribute 51 working documents as Internet-Drafts. The list of current Internet- 52 Drafts is at http://datatracker.ietf.org/drafts/current/. 54 Internet-Drafts are draft documents valid for a maximum of six months 55 and may be updated, replaced, or obsoleted by other documents at any 56 time. It is inappropriate to use Internet-Drafts as reference 57 material or to cite them other than as "work in progress." 59 This Internet-Draft will expire on September 3, 2018. 61 Copyright Notice 63 Copyright (c) 2018 IETF Trust and the persons identified as the 64 document authors. All rights reserved. 66 This document is subject to BCP 78 and the IETF Trust's Legal 67 Provisions Relating to IETF Documents 68 (http://trustee.ietf.org/license-info) in effect on the date of 69 publication of this document. Please review these documents 70 carefully, as they describe your rights and restrictions with respect 71 to this document. Code Components extracted from this document must 72 include Simplified BSD License text as described in Section 4.e of 73 the Trust Legal Provisions and are provided without warranty as 74 described in the Simplified BSD License. 76 Table of Contents 78 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 79 2. Changes Since Version -03, -04, -05, -06 and -07 . . . . . . 4 80 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 81 4. Compressing Path Vectors . . . . . . . . . . . . . . . . . . 4 82 4.1. Equivalent Aggregation . . . . . . . . . . . . . . . . . 5 83 4.2. Redundant Network Elements . . . . . . . . . . . . . . . 6 84 4.3. Equivalent Decomposition . . . . . . . . . . . . . . . . 7 85 5. Compression Algorithms . . . . . . . . . . . . . . . . . . . 8 86 5.1. Equivalent Aggregation . . . . . . . . . . . . . . . . . 9 87 5.2. Redundant Network Element Identification . . . . . . . . 11 88 5.3. Equivalent Decomposition . . . . . . . . . . . . . . . . 13 89 5.4. Execution Order . . . . . . . . . . . . . . . . . . . . . 16 90 6. Encoding/Decoding Path Vectors . . . . . . . . . . . . . . . 16 91 6.1. Decoding Path Vectors . . . . . . . . . . . . . . . . . . 17 92 6.2. Encoding Path Vectors . . . . . . . . . . . . . . . . . . 20 93 6.3. Compatibility . . . . . . . . . . . . . . . . . . . . . . 23 94 7. Security Considerations . . . . . . . . . . . . . . . . . . . 23 95 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 96 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 23 97 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 98 10.1. Normative References . . . . . . . . . . . . . . . . . . 23 99 10.2. Informative References . . . . . . . . . . . . . . . . . 23 100 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24 102 1. Introduction 104 The path vector extension [I-D.ietf-alto-path-vector] has extended 105 the base ALTO protocol [RFC7285] with the ability to present more 106 complex network views than the simple abstraction used by Cost Map or 107 Endpoint Cost Service. ALTO clients can query more sophisticated 108 information such as shared bottlenecks, and schedule their flows 109 properly to avoid congestion and to better utilize network resources. 111 Meanwhile, the extension itself does not specify how an ALTO server 112 should respond to a path-vector query. A straw man approach, as in 113 the context of Software Defined Networking (SDN) where network 114 providers have a global view, can compute the path vectors by 115 retrieving the paths for all requested flows and returning the links 116 on those paths as abstract network elements. However, this approach 117 has several drawbacks: 119 o The resultant network view may lead to privacy leaks. Since the 120 paths constitute a sub-graph of the global network topology, they 121 may contain sensitive information without further processing. 123 o The resultant network view may contain redundant information. The 124 path vector information is primarily used to avoid network 125 bottlenecks. Thus, if a link cannot become the bottleneck, as 126 demonstrated in Section 4, it is considered as redundant. 127 Redundant links not only increase the communication overhead of 128 the path vector extension, but also trigger false-positive data 129 change events when the incremental update extension 130 [I-D.ietf-alto-incr-update-sse] is activated. 132 To overcome these limitations, this document describes equivalent 133 transformation algorithms that identify redundant abstract network 134 elements and reduce them as much as possible. The algorithm can be 135 integrated with any implementation of the path vector extension as a 136 post-processing step. As the name suggests, this algorithm conducts 137 equivalent transformations on the original path vectors, removes 138 redundant information and obtains a more compact view. 140 This document is a supplement to the path vector extension and can be 141 optionally turned on and off without affecting the correctness of 142 responses. A crucial part of the equivalent transformation algorithm 143 is how to find redundant abstract network elements. By tuning the 144 redundancy check algorithm, one can make different trade-off 145 decisions between efficiency and privacy. A reference implementation 146 of redundancy check algorithm is also described in this document. 148 This document is organized as follows. Section 4 gives a concrete 149 example to demonstrate the importance of compressing path vectors. 150 The compression algorithms are specified in Section 5 and Section 6 151 discusses how one can use these algorithms on existing path vector 152 responses. Finally, Section 7 and Section 8 discuss security and 153 IANA considerations. 155 2. Changes Since Version -03, -04, -05, -06 and -07 157 In early versions of this draft, a lot of contents are shared with 158 the path vector draft. From version -04, the authors have adjusted 159 the structure and target this document as a supplement of the path 160 vector extension with 162 o practical compression algorithms which can effectively reduce the 163 leaked information and the communication overhead; and 165 o detailed instructions on how an original path vector response can 166 be processed by these algorithms. 168 The -06 version fixed some minor issues in -04 and -05. The -07 169 version has focused on improving the clarity of the algorithms with 170 more examples. The -08 version has improved the overall quality of 171 the draft, especially the clarity of the algorithms using simpler 172 symbols. 174 3. Terminology 176 This document uses the same terms as in [I-D.ietf-alto-path-vector]. 178 4. Compressing Path Vectors 180 We use the example shown in Figure 1 to demonstrate the importance of 181 compressing path vectors. The network has 6 switches (sw1 to sw6) 182 forming a dumbbell topology where switches sw1/sw3 provide access on 183 the left hand side, s2/s4 provide access on the right hand side, and 184 sw5/sw6 form the backbone. End hosts eh1 to eh4 are connected to 185 access switches sw1 to sw4 respectively. Assume that the bandwidth 186 of each link is 100 Mbps, and that the network is abstracted with 4 187 PIDs each representing a host at one access switch. 189 PID1 +-----+ +-----+ PID2 190 eh1__| |_ ____| |__eh2 191 | sw1 | \ +------+ +------+ / | sw2 | 192 +-----+ \ | | | |/ +-----+ 193 \_| sw5 +---------+ sw6 | 194 PID3 +-----+ / | | | |\ +-----+ PID4 195 eh3__| |__/ +------+ +------+ \____| |__eh4 196 | sw3 | | sw4 | 197 +-----+ +-----+ 199 Figure 1: Raw Network Topology 201 +--------+---------------+ 202 | Link | Description | 203 +--------+---------------+ 204 | link1 | sw1 <==> sw5 | 205 | link2 | sw2 <==> sw6 | 206 | link3 | sw3 <==> sw5 | 207 | link4 | sw4 <==> sw6 | 208 | link5 | sw5 <==> sw6 | 209 +--------+---------------+ 211 Table 1: Description of the Links 213 Three cases are identified when path vectors can be further 214 compressed and an example is provided for each case. 216 4.1. Equivalent Aggregation 218 Consider an application which schedules the traffic consisting of two 219 flows, eh1 -> eh2 and eh3 -> eh4. The application can query the path 220 vectors and a straw man implementation will return all 5 links 221 (abstract network elements) as shown in Figure 2. 223 path vectors: 224 eh1: [ eh2: [ane:l1, ane:l5, ane:l2]] 225 eh3: [ eh4: [ane:l3, ane:l5, ane:l4]] 227 abstract network element property map: 228 ane:l1 : 100 Mbps 229 ane:l2 : 100 Mbps 230 ane:l3 : 100 Mbps 231 ane:l4 : 100 Mbps 232 ane:l5 : 100 Mbps 234 Figure 2: Path Vectors Returned by a Straw Man Implementation 236 The resultant path vectors represent the following linear constraints 237 on the available bandwidth for the two flows: 239 bw(eh1->eh2) <= 100 Mbps (ane:l1) 240 bw(eh1->eh2) <= 100 Mbps (ane:l2) 241 bw(eh3->eh4) <= 100 Mbps (ane:l3) 242 bw(eh3->eh4) <= 100 Mbps (ane:l4) 243 bw(eh1->eh2) + bw(eh3->eh4) <= 100 Mbps (ane:l5) 245 Figure 3: Linear Constraints Represented by the Path Vectors 247 It can be seen that the constraints of ane:l1 and ane:l2 are exactly 248 the same, and so are those of ane:l3 and ane:l4. Intuitively, we can 249 replace ane:l1 and ane:l2 with a new abstract network element ane:1, 250 and similarly replace ane:l3 and ane:l4 with ane:2. The new path 251 vectors are shown in Figure 4. 253 path vectors: 254 eh1: [ eh2: [ane:1, ane:l5]] 255 eh3: [ eh4: [ane:2, ane:l5]] 257 abstract network element property map: 258 ane:1 : 100 Mbps 259 ane:2 : 100 Mbps 260 ane:l5 : 100 Mbps 262 Figure 4: Path Vectors after Merging ane:l1/ane:l2 and ane:l3/ane:l4 264 4.2. Redundant Network Elements 266 Consider the same case as in Section 4.1. Taking a deeper look at 267 Figure 3, one can conclude that constraints of ane:1 (ane:l1/ane:l2) 268 and ane:2 (ane:l3/ane:l4) can be implicitly derived from that of 269 ane:l5. Thus, these constraints are considered _redundant_ and the 270 path vectors in Figure 4 can be further reduced. We replace ane:l5 271 with a new ane:3 and the new path vectors are shown in Figure 5. 273 path vectors: 274 eh1: [ eh2: [ane:3]] 275 eh3: [ eh4: [ane:3]] 277 abstract network element property map: 278 ane:3 : 100 Mbps 280 Figure 5: Path Vectors after Removing Redundant Elements 282 It is clear that the new path vectors (Figure 5) are much more 283 compact than the original path vectors (Figure 2) but they contain 284 just as much information. Meanwhile, the application can hardly 285 infer anything about the original topology with the compact path 286 vectors. 288 4.3. Equivalent Decomposition 290 However, it is not always possible to directly remove all redundant 291 network elements. For example, consider the case when both bandwidth 292 and routingcost are requested, and the values are as shown in 293 Figure 6. Note that we have changed the bandwidth for ane:l5 for 294 demonstration purpose. 296 path vectors: 297 eh1: [ eh2: [ane:l1, ane:l5, ane:l2]] 298 eh3: [ eh4: [ane:l3, ane:l5, ane:l4]] 300 abstract network element property map: 301 ane:l1 : 100 Mbps, 1 302 ane:l2 : 100 Mbps, 2 303 ane:l3 : 100 Mbps, 1 304 ane:l4 : 100 Mbps, 1 305 ane:l5 : 200 Mbps, 1 307 Figure 6: Path Vectors Returned by a Straw Man Implementation 309 bw(eh1->eh2) <= 100 Mbps (ane:l1) 310 bw(eh1->eh2) <= 100 Mbps (ane:l2) 311 bw(eh3->eh4) <= 100 Mbps (ane:l3) 312 bw(eh3->eh4) <= 100 Mbps (ane:l4) 313 bw(eh1->eh2) + bw(eh3->eh4) <= 200 Mbps (ane:l5) 315 Figure 7: Bandwidth Constraints in the Original Path Vectors 317 rc(eh1->eh2) = rc(ane:l1) + rc(ane:l2) + rc(ane:l5) = 4 318 rc(eh3->eh4) = rc(ane:l3) + rc(ane:l4) + rc(ane:l5) = 3 320 Figure 8: Routingcost Information in the Original Path Vectors 322 Figure 7 and Figure 8 demonstrate the bandwidth and routingcost 323 information one can obtain from the original path vector. Again, 324 ane:l1/ane:l2 and ane:l3/ane:l4 can still be aggregated in a similar 325 way as in Figure 4 by setting the routingcost of ane:1 and ane:2 to 3 326 and 2 respectively. However, we cannot remove the redundant network 327 element (ane:l5 in this case) directly because the resultant path 328 vectors (Figure 9) would not provide the same routingcost information 329 as in the original path vector. 331 path vectors: 332 eh1: [ eh2: [ane:1]] 333 eh3: [ eh4: [ane:2]] 335 abstract network element property map: 336 ane:1 : 100 Mbps, 3 337 ane:2 : 100 Mbps, 2 339 Figure 9: Path Vectors after Removing Redundant Network Element 341 A further observation is that since the bandwidth constraint of 342 ane:l5 is redundant, it can be equally represented as two abstract 343 network elements ane:a5 and ane:b5, as shown in Figure 10. 345 path vectors: 346 eh1: [ eh2: [ane:1, ane:a5]] 347 eh3: [ eh4: [ane:2, ane:b5]] 349 abstract network element property map: 350 ane:1 : 100 Mbps, 3 351 ane:2 : 100 Mbps, 2 352 ane:a5 : 200 Mbps, 1 353 ane:b5 : 200 Mbps, 1 355 Figure 10: Path Vectors after Decomposing ane:l5 357 Since ane:1/ane:a5 and ane:2/ane:b5 can be aggregated as ane:3 and 358 ane:4 respectively, the final path vectors only contain two network 359 elements, as shown in Figure 11. 361 path vectors: 362 eh1: [ eh2: [ane:1]] 363 eh3: [ eh4: [ane:2]] 365 abstract network element property map: 366 ane:1 : 100 Mbps, 4 367 ane:2 : 100 Mbps, 3 369 Figure 11: Path Vectors after Merging ane:1/ane:a5 and ane:2/ane:b5 371 One can verify that this path vector response has just the same 372 information as in Figure 6 but contains much less contents. 374 5. Compression Algorithms 376 To provide a guideline on how path vectors MIGHT be compressed, this 377 section describes the details of the algorithms for the three 378 aforementioned cases: 380 1. Equivalent aggregation (EQUIV_AGGR), which compresses the 381 original path vectors by aggregating the network elements with 382 the same set of pairs as shown in Section 4.1; 384 2. Identification of redundant constraints (IS_REDUNDANT), which 385 compresses the original path vectors by removing the network 386 elements that provide only redundant information as shown in 387 Section 4.2; 389 3. Equivalent decomposition (EQUIV_DECOMP), which compresses the 390 original path vectors by decomposing redundant network elements 391 to obtain the same end-to-end routing metrics as shown in 392 Section 4.3. 394 5.1. Equivalent Aggregation 396 5.1.1. Parameters and Variables 398 The equivalent aggregation algorithm takes 3 parameters: the set of 399 network elements "V", the set of relevant host pairs "P" and the set 400 of metrics "M". 402 Set of network elements V: The set of network elements consists of 403 all the network elements that exists in the original path vectors. 404 The "i"-th network element in "V" is denoted as "v_i". 406 Set of relevant host pairs P: The "i"-th element in "P" is denoted 407 as "p_i". It represents the set of (src, dst) pairs whose paths 408 traverse "v_i" in the original path vectors. 410 Set of metrics M: The "i-th" element in "M" is denoted as "m_i". It 411 represents the set of metrics associated with network element 412 "v_i". 414 The output of the equivalent aggregation algorithm is a new set of 415 network elements "V'", a new set of relevant host pairs "P'" and a 416 new set of metrics "M'", i.e., "V', P', M' = EQUIV_AGGR(V, P, M)". 418 5.1.2. Algorithm Description 420 1. Set "V'", "P'", "M'" to empty sets. Set "k" to 0. Go to step 2. 422 2. If "V" is empty, go to step 6. Otherwise, go to step 3. 424 3. Select an arbitrary element "v_i" from "V", remove "v_i" from "V" 425 and go to step 4. 427 4. For any element "v_j" in "V", if "p_i = p_j", remove "v_j" from 428 "V" and update "m_i" with "m_j", i.e., "m_i = UPDATE(m_i, m_j)" 429 (which will be explained later). Go to step 5. 431 5. Increment "k" by 1, let "v'_k = v_i", "p'_k = p_i" and "m'_k = 432 m_i". Go to step 2. 434 6. Return "V'", "P'", and "M'" 436 The process of update "m_i" with "m_j" depends on the metric types. 437 For example, for routingcost and hopcount, the update is numerical 438 addition, while for bandwidth, the update is calculating the minimum. 439 The UPDATE function for some common metrics are listed in Table 2. 441 +--------------+------------------------+------------+ 442 | metric | UPDATE(x, y) | default | 443 +--------------+------------------------+------------+ 444 | hopcount | x + y | 0 | 445 | routingcost | x + y | 0 | 446 | bandwidth | min(x, y) | +infinity | 447 | loss rate | 1 - (1 - x) * (1 - y) | 0 | 448 +--------------+------------------------+------------+ 450 Table 2: UPDATE Function of Different Metrics 452 5.1.3. Example 454 Consider the path vectors in Figure 2 which can be represented as: 456 V = { ane:l1, ane:l2, ane:l3, ane:l4, ane:l5 } 458 p_1 = { eh1->eh2 } 459 p_2 = { eh1->eh2 } 460 p_3 = { eh3->eh4 } 461 p_4 = { eh3->eh4 } 462 p_5 = { eh1->eh2, eh3->eh4 } 464 m_1 = 100 Mbps 465 m_2 = 100 Mbps 466 m_3 = 100 Mbps 467 m_4 = 100 Mbps 468 m_5 = 100 Mbps 470 As "p_1 = p_2" and "p_3 = p_4", the resultant attributes after the 471 aggregation become: 473 V' = { ane:1, ane:2, ane:l5 } 475 p'_1 = { eh1->eh2 } = p_1 = p_2 476 p'_2 = { eh3->eh4 } = p_3 = p_4 477 p'_3 = { eh1->eh2, eh3->eh4 } = p_5 479 m'_1 = 100 Mbps = UPDATE(m_1, m_2) 480 m'_2 = 100 Mbps = UPDATE(m_3, m_4) 481 m'_3 = 100 Mbps = m_5 483 5.2. Redundant Network Element Identification 485 5.2.1. Parameters and Variables 487 The redundant network element identification algorithm is based on 488 the algorithm introduced by Telgen [TELGEN83]. It takes 3 489 parameters: the set of network elements "V", the set of relevant host 490 pairs "P" and the set of available bandwidth values "B". 492 "V", "v_i", "P" and "p_i" are defined the same way as in 493 Section 5.1.1. 495 Set of available bandwidth values B: The "i"-th element in "B" is 496 denoted as "b_i". It represents the available bandwidth for 497 network element "v_i". 499 The output of the IS_REDUNDANT function is a set of indices "R", 500 which represents the indices of network elements whose bandwidth 501 constraints are redundant, i.e., "R = IS_REDUNDANT(V, P, B)". 503 In addition to the parameters and output values, the algorithm also 504 maintains the following variables: 506 Set of host pairs H: The "i"-th element of "H" is denoted as "h_i". 507 It represents a (src, dst) pair ever appeared in the path vector 508 query. "H" is the union of all "p_i" in "P". 510 Set of bandwidth constraints C: The "i"-th element of "C" is denoted 511 as "c_i". It represents a linear bandwidth constraint on the 512 flows between the end host pairs. The constraint "c_i" has the 513 form of "a_i x <= b_i" where "a_i" is a row vector of 0-1 514 coefficients derived from "p_i", "x" is a column vector 515 representing the bandwidth of all the host pairs, and "b_i" is the 516 available bandwidth of "v_i". 518 5.2.2. Algorithm Description 520 1. The first step is to convert a network element to its bandwidth 521 constraint "c_i". The bound "b_i" is directly obtained as the 522 available bandwidth and the coefficients "a_i" are computed as: 524 1 if h_j in p_i 525 a_ij = 526 0 otherwise. 528 Set "R" to an empty set. Go to step 2. 530 2. For each "i", solve the following linear programming problem: 532 y_i = max a_i x 533 subject to: 534 a_j x <= b_j, j = 1..|V|, i <> j 536 Go to step 3. 538 3. For each "i", if "y_i <= b_i", "c_i" is redundant and we say 539 "v_i" is redundant, "R = UNION(R, {i})". Go to step 4. 541 4. Return "R". 543 5.2.3. Example 545 Consider the path vectors in Figure 4 such that the input to the 546 IS_REDUNDANT algorithm is as follows. 548 V = { ane:1, ane:2, ane:l5 } 550 p_1 = { eh1->eh2 } 551 p_2 = { eh3->eh4 } 552 p_3 = { eh1->eh2, eh3->eh4 } 554 b_1 = 100 Mbps 555 b_2 = 100 Mbps 556 b_3 = 100 Mbps 558 With that information, one can follow the algorithm and get: 560 c_1: x1 <= 100 561 c_2: x2 <= 100 562 c_3: x1 + x2 <= 100 564 y_1 = 100 Mbps <= b_1 565 y_2 = 100 Mbps <= b_2 566 y_3 = 200 Mbps > b_3 568 R = IS_REDUNDANT(V, P, B) = { 1, 2 } 570 5.3. Equivalent Decomposition 572 5.3.1. Parameters and Variables 574 The equivalent decomposition algorithm takes 4 parameters: the set of 575 network elements "V", the set of relevant host pairs "P", the set of 576 metrics "M" and the set of redundant network elements "R". 578 "V", "P" and "M" are as defined as in Section 5.1.1. If the "j"-th 579 metric is bandwidth, we can construct the set of available bandwidth 580 values "B" as "b_i = m_ij" and "R" is the output of the redundant 581 network element identification procedure, i.e. "R = IS_REDUNDANT(V, 582 P, B)". Otherwise, if bandwidth is not included in the metrics, "R" 583 is {1, ..., |V|}. 585 The output of the function EQUIV_DECOMP is a new set of network 586 elements "V'", a new set of relevant host pairs "P'", and a new set 587 of metrics "M'", i.e., "V', P', M' = EQUIV_DECOMP(V, P, M, R)". 589 5.3.2. Algorithm Description 591 1. Set "V'", "P'", "M'" to empty sets. Set "k" to 0. Go to step 2. 593 2. For each "i" such that "i" in "R", go to step 3. After 594 processing each "i", go to step 7. 596 3. For each "j" such that "j <> i", go to step 4. After processing 597 each "j", go to step 6. 599 4. If "p_j" is a subset of "p_i", go to step 5. Otherwise go to 600 step 3. 602 5. Let "p_i = p_i \ p_j" and "m_j = UPDATE(m_j, m_i)". Go to step 603 3. 605 6. If "p_i" is not empty, increment "k" by 1 and let "v'_k = v_i", 606 "p'_k = p_i" and "m'_k = m_i". Go to step 2. 608 7. For each "i" such that "i" is not in "R", go to step 8. After 609 processing each "i", go to step 9. 611 8. Increment "k" by 1 and let "v'_k = v_i", "p'_k = p_i", "m'_k = 612 m_i". Go to step 7. 614 9. Return "V'", "P'" and "M'". 616 5.3.3. Example 618 Consider the case in Section 4.3. Before the decomposition, the 619 input to the algorithm is as follows: 621 V = { ane:1, ane:2, ane:l5 } 623 p_1 = { eh1->eh2 } 624 p_2 = { eh3->eh4 } 625 p_3 = { eh1->eh2, eh3->eh4 } 627 m_1 = { bw: 100 Mbps, rc: 3 } 628 m_2 = { bw: 100 Mbps, rc: 2 } 629 m_3 = { bw: 200 Mbps, rc: 1 } 631 R = { 3 } 633 Since there is only one element in "R", "v_i = ane:l5". 635 After the first iteration of steps 3-5 with "v_j = ane:1": 637 V = { ane:1, ane:2, ane:l5 } 639 p_1 = { eh1->eh2 } 640 p_2 = { eh3->eh4 } 641 p_3 = { eh3->eh4 } 643 m_1 = { bw: 100 Mbps, rc: 4 } 644 m_2 = { bw: 100 Mbps, rc: 2 } 645 m_3 = { bw: 200 Mbps, rc: 1 } 647 V' = { } 648 k = 0 650 After the second iteration of steps 3-5 with "v_j = ane:2": 652 V = { ane:1, ane:2, ane:l5 } 654 p_1 = { eh1->eh2 } 655 p_2 = { eh3->eh4 } 656 p_3 = { } 658 m_1 = { bw: 100 Mbps, rc: 4 } 659 m_2 = { bw: 100 Mbps, rc: 3 } 660 m_3 = { bw: 200 Mbps, rc: 1 } 662 V' = { } 663 k = 0 665 After step 6, since "p_3" is now empty, it just goes back to step 2. 666 At step 2, since all indices in "R" has been processed, it goes to 667 step 7. 669 After the first iteration of steps 7-8 with "i = 1": 671 V = { ane:1, ane:2, ane:l5 } 673 p_1 = { eh1->eh2 } 674 p_2 = { eh3->eh4 } 675 p_3 = { } 677 m_1 = { bw: 100 Mbps, rc: 4 } 678 m_2 = { bw: 100 Mbps, rc: 3 } 679 m_3 = { bw: 200 Mbps, rc: 1 } 681 V' = { ane:1 } 682 k = 1 684 p'_1 = { eh1->eh2 } = p_1 686 m'_1 = { bw: 100 Mbps, rc: 4 } = m_1 688 After the second iteration of steps 7-8 with "i = 2": 690 V = { ane:1, ane:2, ane:l5 } 692 p_1 = { eh1->eh2 } 693 p_2 = { eh3->eh4 } 694 p_3 = { } 696 m_1 = { bw: 100 Mbps, rc: 4 } 697 m_2 = { bw: 100 Mbps, rc: 3 } 698 m_3 = { bw: 200 Mbps, rc: 1 } 700 V' = { ane:1, ane:2 } 701 k = 2 703 p'_1 = { eh1->eh2 } 704 p'_2 = { eh3->eh4 } = p_2 706 m'_1 = { bw: 100 Mbps, rc: 4 } 707 m'_2 = { bw: 100 Mbps, rc: 3 } = m_2 709 So the final output of EQUIV_DECOMP is: 711 V' = { ane:1, ane:2 } 713 p'_1 = { eh1->eh2 } 714 p'_2 = { eh3->eh4 } 716 m'_1 = { bw: 100 Mbps, rc: 4 } 717 m'_2 = { bw: 100 Mbps, rc: 3 } 719 5.4. Execution Order 721 As the examples demonstrate, the three algorithms MUST be executed in 722 the same order as they are introduced, i.e., one MUST conduct 723 "EQUIV_AGGR" before "IS_REDUNDANT" or "EQUIV_DECOMP", and conduct 724 "IS_REDUNDANT" before "EQUIV_DECOMP". Otherwise, the results of the 725 compressed path vectors MAY NOT be correct. 727 6. Encoding/Decoding Path Vectors 729 The three algorithms work mostly with network elements. Existing 730 path vectors must be decoded before they can be passed on to the 731 algorithms and the compressed results must be encoded as path vectors 732 before they are sent to the clients. The decoding and encoding 733 processes are specified as below. 735 6.1. Decoding Path Vectors 737 6.1.1. Parameters and Variables 739 The decoding algorithm DECODE takes a path vector response, which 740 consists of the path vector part "PV" and the element property part 741 "E". 743 Path vectors PV: The path vector part has a format of a CostMap 744 (EndpointCostMap) where the cost value is a list of abstract 745 network element names. We say a PID (endpoint address) "i" is IN 746 "PV" if and only if there is an entry "i" in the cost-map 747 (endpoint-cost-map), and denote the entry value as "PV[i]". 748 Similarly, we say a PID (endpoint address) "j" is IN "PV[i]" if 749 and only if there is an entry "j" in the DstCosts of "i", whose 750 value is denoted as "PV[i][j]". 752 Element property map E: The element property map "E" maps an 753 abstract network element name to its properties. We denote "E[n]" 754 as the properties of element with name "n" and "E[n][pn]" as the 755 value of property "pn". 757 The algorithm returns the set of elements "V", the set of relevant 758 host pairs "P", the set of metrics "M" and the available bandwidth 759 "B", as defined in Section 5.1.1 and Section 5.2.1. The algorithm 760 uses a "SET" function which transforms a list into a set, and uses a 761 "NAME" function which maps an integer in [1, K] to a unique property 762 name where there are K properties in "E". 764 6.1.2. Algorithm Description 766 1. Set "V", "P", "M" and "B" to empty sets. Set "k" to 0. Go to 767 step 2. 769 2. For each "i IN PV", go to step 3. After processing each "i", go 770 to step 8. 772 3. For each "j IN PV[i]", go to step 4. After processing each "j", 773 go to step 2. 775 4. For each "n" in "SET(PV[i][j])", go to step 5. After processing 776 each "n", go to step 3. 778 5. If "n" is not in "V", go to step 6. Otherwise, go to step 7. 780 6. Increment "k" by 1 and let "v_k = n", "p_k = { i->j }". Go to 781 step 4. 783 7. Find the index of "n" in "V" denoted as "a", let "p_a = 784 UNION(p_a, {i->j})". Go to step 4. 786 8. For each "i" from 1 to |V|, go to step 9. After processing all 787 "i", go to step 11. 789 9. For each "j" from 1 to K, go to step 10. After processing all 790 "j", go back to step 8. 792 10. If "NAME(j) = 'availbw'", let "b_i = E[v_i][NAME(j)]". Let 793 "m_ij = E[v_i][NAME(j)]". 795 11. Return "V", "P", "M" and "B". 797 6.1.3. Example 799 Consider the following example: 801 HTTP/1.1 200 OK 802 Content-Length: [TBD] 803 Content-Type: multipart/related; boundary=example-2 805 --example-2 806 Content-Type: application/alto-endpointcost+json 808 { 809 "meta": { 810 "cost-types": [ 811 {"cost-mode": "array", "cost-metric": "ane-path"} 812 ] 813 } 814 "endpoint-cost-map": { 815 "ipv4:192.0.2.2": { 816 "ipv4:192.0.2.89": [ "ane:L1", "ane:L3", "ane:L4" ], 817 "ipv4:203.0.113.45": [ "ane:L1", "ane:L4", "ane:L5" ] 818 } 819 } 820 } 821 --example-2 822 Content-Type: application/alto-propmap+json 824 { 825 "property-map": { 826 "ane:L1": { "availbw": 50 }, 827 "ane:L3": { "availbw": 48 }, 828 "ane:L4": { "availbw": 55 }, 829 "ane:L5": { "availbw": 60 }, 830 "ane:L7": { "availbw": 35 } 831 } 832 } 834 --example-2-- 836 After the first iteration of Lines 2-5: 838 V = { ane:L1, ane:L3, ane:L4 } 840 p_1 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } 841 p_2 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } 842 p_3 = { ipv4:192.0.2.2->ipv4:192.0.2.89 }. 844 After the second iteration of Lines 2-5: 846 V = { ane:L1, ane:L3, ane:L4, ane:L5 } 848 p_1 = { ipv4:192.0.2.2->ipv4:192.0.2.89, 849 ipv4:192.0.2.2->ipv4:203.0.113.45 } 850 p_2 = { ipv4:192.0.2.2->ipv4:192.0.2.89, 851 ipv4:192.0.2.2->ipv4:203.0.113.45 } 852 p_3 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } 853 p_4 = { ipv4:192.0.2.2->ipv4:203.0.113.45 }. 855 After the first iteration of Lines 6-9 with "i = 1": 857 m_1 = [50] 859 b_1 = 50 861 After all four iterations of Lines 6-9: 863 m_1 = [50] 864 m_2 = [48] 865 m_3 = [55] 866 m_4 = [60] 868 b_1 = 50 869 b_2 = 48 870 b_3 = 55 871 b_4 = 60 873 The decoded information can be passed on to "EQUIV_AGGR", 874 "IS_REDUNDANT" and "EQUIV_DECOMP" for compression. 876 6.2. Encoding Path Vectors 878 6.2.1. Parameters and Variables 880 The algorithm ENCODE is the reverse process of DECODE. It takes the 881 parameters "V", "P", "M" and constructs the path vector results. 883 The parameters are defined as in Section 5.1.1 and Section 5.2.1. 885 The algorithm also uses the NAME function in Section 6.1.1 which MUST 886 return the same results in a paired ENCODE/DECODE process, and the 887 "APPEND(L, e)" function which adds element "e" to list "L". 889 6.2.2. Algorithm Description 891 1. Set "PV={}", "E = {}". Go to step 2. 893 2. For each "v_i" in "V", go to step 3. If all "v_i" is processed, 894 go to step XX. 896 3. For each "a->b" in "p_i", go to step 4. If all such "a->b" is 897 processed, go to step 6. 899 4. If "a" is not in "PV", let "PV[a] = {}". Go to step 5. 901 5. If "b" is not in "PV[a]", let "PV[a][b] = [v_i]". Otherwise, let 902 "PV[a][b] = APPEND(PV[a][b], v_i)". Go to step 2. 904 6. For each index "k" in [1, K], go to step 7. If all "k" is 905 processed, go to step 1. 907 7. Set "E[v_i][NAME(k)] = m_ik". Go to step 6. 909 8. Return "PV" and "E". 911 6.2.3. Example 913 We consider the encoding of the decoded example in Section 6.1.3. 915 V = { ane:L1, ane:L3, ane:L4, ane:L5 } 917 p_1 = { ipv4:192.0.2.2->ipv4:192.0.2.89, 918 ipv4:192.0.2.2->ipv4:203.0.113.45 } 919 p_2 = { ipv4:192.0.2.2->ipv4:192.0.2.89, 920 ipv4:192.0.2.2->ipv4:203.0.113.45 } 921 p_3 = { ipv4:192.0.2.2->ipv4:192.0.2.89 } 922 p_4 = { ipv4:192.0.2.2->ipv4:203.0.113.45 } 924 m_1 = [50] 925 m_2 = [48] 926 m_3 = [55] 927 m_4 = [60] 929 After the first iteration of steps 2-7: 931 PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1] 932 PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1] 934 E[ane:L1]["availbw"] = 50 936 After the second iteration: 938 PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1, ane:L3] 939 PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3] 941 E[ane:L1]["availbw"] = 50 942 E[ane:L3]["availbw"] = 48 944 After the third iteration: 946 PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1, ane:L3, ane:L4] 947 PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3] 949 E[ane:L1]["availbw"] = 50 950 E[ane:L3]["availbw"] = 48 951 E[ane:L4]["availbw"] = 55 953 After the fourth iteration: 955 PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1, ane:L3, ane:L4] 956 PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3, ane:L5] 958 E[ane:L1]["availbw"] = 50 959 E[ane:L3]["availbw"] = 48 960 E[ane:L4]["availbw"] = 55 961 E[ane:L5]["availbw"] = 60 963 Eventually, one can use the previous information to construct the 964 endpoint cost service response. 966 HTTP/1.1 200 OK 967 Content-Length: [TBD] 968 Content-Type: multipart/related; boundary=example-2 970 --example-2 971 Content-Type: application/alto-endpointcost+json 973 { 974 "meta": { 975 "cost-types": [ 976 {"cost-mode": "array", "cost-metric": "ane-path"} 977 ] 978 } 979 "endpoint-cost-map": { 980 "ipv4:192.0.2.2": { 981 "ipv4:192.0.2.89": [ "ane:L1", "ane:L3", "ane:L4" ], 982 "ipv4:203.0.113.45": [ "ane:L1", "ane:L4", "ane:L5" ] 983 } 984 } 985 } 987 --example-2 988 Content-Type: application/alto-propmap+json 990 { 991 "property-map": { 992 "ane:L1": { "availbw": 50 }, 993 "ane:L3": { "availbw": 48 }, 994 "ane:L4": { "availbw": 55 }, 995 "ane:L5": { "availbw": 60 }, 996 } 997 } 999 --example-2-- 1001 6.3. Compatibility 1003 When the path vector extension is used with other extensions, such as 1004 [I-D.ietf-alto-cost-calendar] and [I-D.ietf-alto-multi-cost], the 1005 decoding and the encoding MUST only apply on the path vector part and 1006 leave the other attributes as they are. 1008 Hence, this extension does not change the compatibility between the 1009 original path vector extension and other extensions. 1011 7. Security Considerations 1013 This document does not introduce any privacy or security issue on 1014 ALTO servers not already present in the base ALTO protocol or in the 1015 path vector extension. 1017 The algorithms specified in this document can even help protect the 1018 privacy of network providers by conducting irreversible 1019 transformations on the original path vector. 1021 8. IANA Considerations 1023 This document does not define any new media type or introduce any new 1024 IANA consideration. 1026 9. Acknowledgments 1028 The authors would like to thank Dr. Qiao Xiang, Mr. Jingxuan Zhang 1029 (Tongji University), Prof. Jun Bi (Tsinghua University) and 1030 Dr. Andreas Voellmy (Yale University) for their early engagement and 1031 discussions. 1033 10. References 1035 10.1. Normative References 1037 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1038 Requirement Levels", BCP 14, RFC 2119, 1039 DOI 10.17487/RFC2119, March 1997, 1040 . 1042 10.2. Informative References 1044 [I-D.ietf-alto-cost-calendar] 1045 Randriamasy, S., Yang, Y., Wu, Q., Lingli, D., and N. 1046 Schwan, "ALTO Cost Calendar", draft-ietf-alto-cost- 1047 calendar-01 (work in progress), February 2017. 1049 [I-D.ietf-alto-incr-update-sse] 1050 Roome, W. and Y. Yang, "ALTO Incremental Updates Using 1051 Server-Sent Events (SSE)", draft-ietf-alto-incr-update- 1052 sse-02 (work in progress), April 2016. 1054 [I-D.ietf-alto-multi-cost] 1055 Randriamasy, S., Roome, W., and N. Schwan, "Multi-Cost 1056 ALTO", draft-ietf-alto-multi-cost-10 (work in progress), 1057 April 2017. 1059 [I-D.ietf-alto-path-vector] 1060 Bernstein, G., Chen, S., Gao, K., Lee, Y., Roome, W., 1061 Scharf, M., Yang, Y., and J. Zhang, "ALTO Extension: Path 1062 Vector Cost Mode", draft-ietf-alto-path-vector-00 (work in 1063 progress), May 2017. 1065 [RFC7285] Alimi, R., Ed., Penno, R., Ed., Yang, Y., Ed., Kiesel, S., 1066 Previdi, S., Roome, W., Shalunov, S., and R. Woundy, 1067 "Application-Layer Traffic Optimization (ALTO) Protocol", 1068 RFC 7285, DOI 10.17487/RFC7285, September 2014, 1069 . 1071 [TELGEN83] 1072 Telgen, J., "Identifying Redundant Constraints and 1073 Implicit Equalities in Systems of Linear Constraints", 1074 Management Science , Volume 29, Issue 10, 1075 DOI 10.1287/mnsc.29.10.1209, 1983, 1076 . 1079 Authors' Addresses 1081 Kai Gao 1082 Tsinghua University 1083 30 Shuangqinglu Street 1084 Beijing 100084 1085 China 1087 Email: gaok12@mails.tsinghua.edu.cn 1089 Xin (Tony) Wang 1090 Tongji University 1091 4800 CaoAn Road 1092 Shanghai 210000 1093 China 1095 Email: xinwang2014@hotmail.com 1096 Qiao Xiang 1097 Tongji/Yale University 1098 51 Prospect Street 1099 New Haven, CT 1100 USA 1102 Email: qiao.xiang@cs.yale.edu 1104 Chen Gu 1105 Tongji University 1106 4800 CaoAn Road 1107 Shanghai 210000 1108 China 1110 Email: gc19931011jy@gmail.com 1112 Y. Richard Yang 1113 Yale University 1114 51 Prospect St 1115 New Haven CT 1116 USA 1118 Email: yry@cs.yale.edu 1120 G. Robert Chen 1121 Huawei 1122 Nanjing 1123 China 1125 Email: chenguohai@huawei.com