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]