Internet DRAFT - draft-gao-alto-routing-state-abstraction
draft-gao-alto-routing-state-abstraction
ALTO WG K. Gao
Internet-Draft Tsinghua University
Intended status: Standards Track X. Wang
Expires: September 3, 2018 Tongji University
Q. Xiang
Tongji/Yale University
C. Gu
Tongji University
Y. Yang
Yale University
G. Chen
Huawei
March 2, 2018
Compressing ALTO Path Vectors
draft-gao-alto-routing-state-abstraction-08.txt
Abstract
The path vector extension [I-D.ietf-alto-path-vector] has extended
the base ALTO protocol [RFC7285] with the ability to represent a more
detailed view of the network which contains not only end-to-end costs
but also information about shared bottlenecks.
However, the view computed by straw man algorithms can contain
redundant information and result in unnecessary communication
overhead. The situation gets even worse when certain ALTO extensions
are enabled, for example, the incremental update extension
[I-D.ietf-alto-incr-update-sse] which continuously pushes data
changes to ALTO clients. Redundant information can trigger
unnecessary updates.
In this document, several algorithms are described which can
effectively reduce the redundancy in the network view while still
providing the same information as in the original path vectors.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Gao, et al. Expires September 3, 2018 [Page 1]
Internet-Draft Compressing Path Vectors March 2018
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 3, 2018.
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Changes Since Version -03, -04, -05, -06 and -07 . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Compressing Path Vectors . . . . . . . . . . . . . . . . . . 4
4.1. Equivalent Aggregation . . . . . . . . . . . . . . . . . 5
4.2. Redundant Network Elements . . . . . . . . . . . . . . . 6
4.3. Equivalent Decomposition . . . . . . . . . . . . . . . . 7
5. Compression Algorithms . . . . . . . . . . . . . . . . . . . 8
5.1. Equivalent Aggregation . . . . . . . . . . . . . . . . . 9
5.2. Redundant Network Element Identification . . . . . . . . 11
5.3. Equivalent Decomposition . . . . . . . . . . . . . . . . 13
5.4. Execution Order . . . . . . . . . . . . . . . . . . . . . 16
6. Encoding/Decoding Path Vectors . . . . . . . . . . . . . . . 16
6.1. Decoding Path Vectors . . . . . . . . . . . . . . . . . . 17
6.2. Encoding Path Vectors . . . . . . . . . . . . . . . . . . 20
6.3. Compatibility . . . . . . . . . . . . . . . . . . . . . . 23
7. Security Considerations . . . . . . . . . . . . . . . . . . . 23
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 23
Gao, et al. Expires September 3, 2018 [Page 2]
Internet-Draft Compressing Path Vectors March 2018
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 23
10.1. Normative References . . . . . . . . . . . . . . . . . . 23
10.2. Informative References . . . . . . . . . . . . . . . . . 23
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
1. Introduction
The path vector extension [I-D.ietf-alto-path-vector] has extended
the base ALTO protocol [RFC7285] with the ability to present more
complex network views than the simple abstraction used by Cost Map or
Endpoint Cost Service. ALTO clients can query more sophisticated
information such as shared bottlenecks, and schedule their flows
properly to avoid congestion and to better utilize network resources.
Meanwhile, the extension itself does not specify how an ALTO server
should respond to a path-vector query. A straw man approach, as in
the context of Software Defined Networking (SDN) where network
providers have a global view, can compute the path vectors by
retrieving the paths for all requested flows and returning the links
on those paths as abstract network elements. However, this approach
has several drawbacks:
o The resultant network view may lead to privacy leaks. Since the
paths constitute a sub-graph of the global network topology, they
may contain sensitive information without further processing.
o The resultant network view may contain redundant information. The
path vector information is primarily used to avoid network
bottlenecks. Thus, if a link cannot become the bottleneck, as
demonstrated in Section 4, it is considered as redundant.
Redundant links not only increase the communication overhead of
the path vector extension, but also trigger false-positive data
change events when the incremental update extension
[I-D.ietf-alto-incr-update-sse] is activated.
To overcome these limitations, this document describes equivalent
transformation algorithms that identify redundant abstract network
elements and reduce them as much as possible. The algorithm can be
integrated with any implementation of the path vector extension as a
post-processing step. As the name suggests, this algorithm conducts
equivalent transformations on the original path vectors, removes
redundant information and obtains a more compact view.
This document is a supplement to the path vector extension and can be
optionally turned on and off without affecting the correctness of
responses. A crucial part of the equivalent transformation algorithm
is how to find redundant abstract network elements. By tuning the
redundancy check algorithm, one can make different trade-off
Gao, et al. Expires September 3, 2018 [Page 3]
Internet-Draft Compressing Path Vectors March 2018
decisions between efficiency and privacy. A reference implementation
of redundancy check algorithm is also described in this document.
This document is organized as follows. Section 4 gives a concrete
example to demonstrate the importance of compressing path vectors.
The compression algorithms are specified in Section 5 and Section 6
discusses how one can use these algorithms on existing path vector
responses. Finally, Section 7 and Section 8 discuss security and
IANA considerations.
2. Changes Since Version -03, -04, -05, -06 and -07
In early versions of this draft, a lot of contents are shared with
the path vector draft. From version -04, the authors have adjusted
the structure and target this document as a supplement of the path
vector extension with
o practical compression algorithms which can effectively reduce the
leaked information and the communication overhead; and
o detailed instructions on how an original path vector response can
be processed by these algorithms.
The -06 version fixed some minor issues in -04 and -05. The -07
version has focused on improving the clarity of the algorithms with
more examples. The -08 version has improved the overall quality of
the draft, especially the clarity of the algorithms using simpler
symbols.
3. Terminology
This document uses the same terms as in [I-D.ietf-alto-path-vector].
4. Compressing Path Vectors
We use the example shown in Figure 1 to demonstrate the importance of
compressing path vectors. The network has 6 switches (sw1 to sw6)
forming a dumbbell topology where switches sw1/sw3 provide access on
the left hand side, s2/s4 provide access on the right hand side, and
sw5/sw6 form the backbone. End hosts eh1 to eh4 are connected to
access switches sw1 to sw4 respectively. Assume that the bandwidth
of each link is 100 Mbps, and that the network is abstracted with 4
PIDs each representing a host at one access switch.
Gao, et al. Expires September 3, 2018 [Page 4]
Internet-Draft Compressing Path Vectors March 2018
PID1 +-----+ +-----+ PID2
eh1__| |_ ____| |__eh2
| sw1 | \ +------+ +------+ / | sw2 |
+-----+ \ | | | |/ +-----+
\_| sw5 +---------+ sw6 |
PID3 +-----+ / | | | |\ +-----+ PID4
eh3__| |__/ +------+ +------+ \____| |__eh4
| sw3 | | sw4 |
+-----+ +-----+
Figure 1: Raw Network Topology
+--------+---------------+
| Link | Description |
+--------+---------------+
| link1 | sw1 <==> sw5 |
| link2 | sw2 <==> sw6 |
| link3 | sw3 <==> sw5 |
| link4 | sw4 <==> sw6 |
| link5 | sw5 <==> sw6 |
+--------+---------------+
Table 1: Description of the Links
Three cases are identified when path vectors can be further
compressed and an example is provided for each case.
4.1. Equivalent Aggregation
Consider an application which schedules the traffic consisting of two
flows, eh1 -> eh2 and eh3 -> eh4. The application can query the path
vectors and a straw man implementation will return all 5 links
(abstract network elements) as shown in Figure 2.
path vectors:
eh1: [ eh2: [ane:l1, ane:l5, ane:l2]]
eh3: [ eh4: [ane:l3, ane:l5, ane:l4]]
abstract network element property map:
ane:l1 : 100 Mbps
ane:l2 : 100 Mbps
ane:l3 : 100 Mbps
ane:l4 : 100 Mbps
ane:l5 : 100 Mbps
Figure 2: Path Vectors Returned by a Straw Man Implementation
Gao, et al. Expires September 3, 2018 [Page 5]
Internet-Draft Compressing Path Vectors March 2018
The resultant path vectors represent the following linear constraints
on the available bandwidth for the two flows:
bw(eh1->eh2) <= 100 Mbps (ane:l1)
bw(eh1->eh2) <= 100 Mbps (ane:l2)
bw(eh3->eh4) <= 100 Mbps (ane:l3)
bw(eh3->eh4) <= 100 Mbps (ane:l4)
bw(eh1->eh2) + bw(eh3->eh4) <= 100 Mbps (ane:l5)
Figure 3: Linear Constraints Represented by the Path Vectors
It can be seen that the constraints of ane:l1 and ane:l2 are exactly
the same, and so are those of ane:l3 and ane:l4. Intuitively, we can
replace ane:l1 and ane:l2 with a new abstract network element ane:1,
and similarly replace ane:l3 and ane:l4 with ane:2. The new path
vectors are shown in Figure 4.
path vectors:
eh1: [ eh2: [ane:1, ane:l5]]
eh3: [ eh4: [ane:2, ane:l5]]
abstract network element property map:
ane:1 : 100 Mbps
ane:2 : 100 Mbps
ane:l5 : 100 Mbps
Figure 4: Path Vectors after Merging ane:l1/ane:l2 and ane:l3/ane:l4
4.2. Redundant Network Elements
Consider the same case as in Section 4.1. Taking a deeper look at
Figure 3, one can conclude that constraints of ane:1 (ane:l1/ane:l2)
and ane:2 (ane:l3/ane:l4) can be implicitly derived from that of
ane:l5. Thus, these constraints are considered _redundant_ and the
path vectors in Figure 4 can be further reduced. We replace ane:l5
with a new ane:3 and the new path vectors are shown in Figure 5.
path vectors:
eh1: [ eh2: [ane:3]]
eh3: [ eh4: [ane:3]]
abstract network element property map:
ane:3 : 100 Mbps
Figure 5: Path Vectors after Removing Redundant Elements
It is clear that the new path vectors (Figure 5) are much more
compact than the original path vectors (Figure 2) but they contain
Gao, et al. Expires September 3, 2018 [Page 6]
Internet-Draft Compressing Path Vectors March 2018
just as much information. Meanwhile, the application can hardly
infer anything about the original topology with the compact path
vectors.
4.3. Equivalent Decomposition
However, it is not always possible to directly remove all redundant
network elements. For example, consider the case when both bandwidth
and routingcost are requested, and the values are as shown in
Figure 6. Note that we have changed the bandwidth for ane:l5 for
demonstration purpose.
path vectors:
eh1: [ eh2: [ane:l1, ane:l5, ane:l2]]
eh3: [ eh4: [ane:l3, ane:l5, ane:l4]]
abstract network element property map:
ane:l1 : 100 Mbps, 1
ane:l2 : 100 Mbps, 2
ane:l3 : 100 Mbps, 1
ane:l4 : 100 Mbps, 1
ane:l5 : 200 Mbps, 1
Figure 6: Path Vectors Returned by a Straw Man Implementation
bw(eh1->eh2) <= 100 Mbps (ane:l1)
bw(eh1->eh2) <= 100 Mbps (ane:l2)
bw(eh3->eh4) <= 100 Mbps (ane:l3)
bw(eh3->eh4) <= 100 Mbps (ane:l4)
bw(eh1->eh2) + bw(eh3->eh4) <= 200 Mbps (ane:l5)
Figure 7: Bandwidth Constraints in the Original Path Vectors
rc(eh1->eh2) = rc(ane:l1) + rc(ane:l2) + rc(ane:l5) = 4
rc(eh3->eh4) = rc(ane:l3) + rc(ane:l4) + rc(ane:l5) = 3
Figure 8: Routingcost Information in the Original Path Vectors
Figure 7 and Figure 8 demonstrate the bandwidth and routingcost
information one can obtain from the original path vector. Again,
ane:l1/ane:l2 and ane:l3/ane:l4 can still be aggregated in a similar
way as in Figure 4 by setting the routingcost of ane:1 and ane:2 to 3
and 2 respectively. However, we cannot remove the redundant network
element (ane:l5 in this case) directly because the resultant path
vectors (Figure 9) would not provide the same routingcost information
as in the original path vector.
Gao, et al. Expires September 3, 2018 [Page 7]
Internet-Draft Compressing Path Vectors March 2018
path vectors:
eh1: [ eh2: [ane:1]]
eh3: [ eh4: [ane:2]]
abstract network element property map:
ane:1 : 100 Mbps, 3
ane:2 : 100 Mbps, 2
Figure 9: Path Vectors after Removing Redundant Network Element
A further observation is that since the bandwidth constraint of
ane:l5 is redundant, it can be equally represented as two abstract
network elements ane:a5 and ane:b5, as shown in Figure 10.
path vectors:
eh1: [ eh2: [ane:1, ane:a5]]
eh3: [ eh4: [ane:2, ane:b5]]
abstract network element property map:
ane:1 : 100 Mbps, 3
ane:2 : 100 Mbps, 2
ane:a5 : 200 Mbps, 1
ane:b5 : 200 Mbps, 1
Figure 10: Path Vectors after Decomposing ane:l5
Since ane:1/ane:a5 and ane:2/ane:b5 can be aggregated as ane:3 and
ane:4 respectively, the final path vectors only contain two network
elements, as shown in Figure 11.
path vectors:
eh1: [ eh2: [ane:1]]
eh3: [ eh4: [ane:2]]
abstract network element property map:
ane:1 : 100 Mbps, 4
ane:2 : 100 Mbps, 3
Figure 11: Path Vectors after Merging ane:1/ane:a5 and ane:2/ane:b5
One can verify that this path vector response has just the same
information as in Figure 6 but contains much less contents.
5. Compression Algorithms
To provide a guideline on how path vectors MIGHT be compressed, this
section describes the details of the algorithms for the three
aforementioned cases:
Gao, et al. Expires September 3, 2018 [Page 8]
Internet-Draft Compressing Path Vectors March 2018
1. Equivalent aggregation (EQUIV_AGGR), which compresses the
original path vectors by aggregating the network elements with
the same set of pairs as shown in Section 4.1;
2. Identification of redundant constraints (IS_REDUNDANT), which
compresses the original path vectors by removing the network
elements that provide only redundant information as shown in
Section 4.2;
3. Equivalent decomposition (EQUIV_DECOMP), which compresses the
original path vectors by decomposing redundant network elements
to obtain the same end-to-end routing metrics as shown in
Section 4.3.
5.1. Equivalent Aggregation
5.1.1. Parameters and Variables
The equivalent aggregation algorithm takes 3 parameters: the set of
network elements "V", the set of relevant host pairs "P" and the set
of metrics "M".
Set of network elements V: The set of network elements consists of
all the network elements that exists in the original path vectors.
The "i"-th network element in "V" is denoted as "v_i".
Set of relevant host pairs P: The "i"-th element in "P" is denoted
as "p_i". It represents the set of (src, dst) pairs whose paths
traverse "v_i" in the original path vectors.
Set of metrics M: The "i-th" element in "M" is denoted as "m_i". It
represents the set of metrics associated with network element
"v_i".
The output of the equivalent aggregation algorithm is a new set of
network elements "V'", a new set of relevant host pairs "P'" and a
new set of metrics "M'", i.e., "V', P', M' = EQUIV_AGGR(V, P, M)".
5.1.2. Algorithm Description
1. Set "V'", "P'", "M'" to empty sets. Set "k" to 0. Go to step 2.
2. If "V" is empty, go to step 6. Otherwise, go to step 3.
3. Select an arbitrary element "v_i" from "V", remove "v_i" from "V"
and go to step 4.
Gao, et al. Expires September 3, 2018 [Page 9]
Internet-Draft Compressing Path Vectors March 2018
4. For any element "v_j" in "V", if "p_i = p_j", remove "v_j" from
"V" and update "m_i" with "m_j", i.e., "m_i = UPDATE(m_i, m_j)"
(which will be explained later). Go to step 5.
5. Increment "k" by 1, let "v'_k = v_i", "p'_k = p_i" and "m'_k =
m_i". Go to step 2.
6. Return "V'", "P'", and "M'"
The process of update "m_i" with "m_j" depends on the metric types.
For example, for routingcost and hopcount, the update is numerical
addition, while for bandwidth, the update is calculating the minimum.
The UPDATE function for some common metrics are listed in Table 2.
+--------------+------------------------+------------+
| metric | UPDATE(x, y) | default |
+--------------+------------------------+------------+
| hopcount | x + y | 0 |
| routingcost | x + y | 0 |
| bandwidth | min(x, y) | +infinity |
| loss rate | 1 - (1 - x) * (1 - y) | 0 |
+--------------+------------------------+------------+
Table 2: UPDATE Function of Different Metrics
5.1.3. Example
Consider the path vectors in Figure 2 which can be represented as:
V = { ane:l1, ane:l2, ane:l3, ane:l4, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh1->eh2 }
p_3 = { eh3->eh4 }
p_4 = { eh3->eh4 }
p_5 = { eh1->eh2, eh3->eh4 }
m_1 = 100 Mbps
m_2 = 100 Mbps
m_3 = 100 Mbps
m_4 = 100 Mbps
m_5 = 100 Mbps
As "p_1 = p_2" and "p_3 = p_4", the resultant attributes after the
aggregation become:
Gao, et al. Expires September 3, 2018 [Page 10]
Internet-Draft Compressing Path Vectors March 2018
V' = { ane:1, ane:2, ane:l5 }
p'_1 = { eh1->eh2 } = p_1 = p_2
p'_2 = { eh3->eh4 } = p_3 = p_4
p'_3 = { eh1->eh2, eh3->eh4 } = p_5
m'_1 = 100 Mbps = UPDATE(m_1, m_2)
m'_2 = 100 Mbps = UPDATE(m_3, m_4)
m'_3 = 100 Mbps = m_5
5.2. Redundant Network Element Identification
5.2.1. Parameters and Variables
The redundant network element identification algorithm is based on
the algorithm introduced by Telgen [TELGEN83]. It takes 3
parameters: the set of network elements "V", the set of relevant host
pairs "P" and the set of available bandwidth values "B".
"V", "v_i", "P" and "p_i" are defined the same way as in
Section 5.1.1.
Set of available bandwidth values B: The "i"-th element in "B" is
denoted as "b_i". It represents the available bandwidth for
network element "v_i".
The output of the IS_REDUNDANT function is a set of indices "R",
which represents the indices of network elements whose bandwidth
constraints are redundant, i.e., "R = IS_REDUNDANT(V, P, B)".
In addition to the parameters and output values, the algorithm also
maintains the following variables:
Set of host pairs H: The "i"-th element of "H" is denoted as "h_i".
It represents a (src, dst) pair ever appeared in the path vector
query. "H" is the union of all "p_i" in "P".
Set of bandwidth constraints C: The "i"-th element of "C" is denoted
as "c_i". It represents a linear bandwidth constraint on the
flows between the end host pairs. The constraint "c_i" has the
form of "a_i x <= b_i" where "a_i" is a row vector of 0-1
coefficients derived from "p_i", "x" is a column vector
representing the bandwidth of all the host pairs, and "b_i" is the
available bandwidth of "v_i".
Gao, et al. Expires September 3, 2018 [Page 11]
Internet-Draft Compressing Path Vectors March 2018
5.2.2. Algorithm Description
1. The first step is to convert a network element to its bandwidth
constraint "c_i". The bound "b_i" is directly obtained as the
available bandwidth and the coefficients "a_i" are computed as:
1 if h_j in p_i
a_ij =
0 otherwise.
Set "R" to an empty set. Go to step 2.
2. For each "i", solve the following linear programming problem:
y_i = max a_i x
subject to:
a_j x <= b_j, j = 1..|V|, i <> j
Go to step 3.
3. For each "i", if "y_i <= b_i", "c_i" is redundant and we say
"v_i" is redundant, "R = UNION(R, {i})". Go to step 4.
4. Return "R".
5.2.3. Example
Consider the path vectors in Figure 4 such that the input to the
IS_REDUNDANT algorithm is as follows.
V = { ane:1, ane:2, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh3->eh4 }
p_3 = { eh1->eh2, eh3->eh4 }
b_1 = 100 Mbps
b_2 = 100 Mbps
b_3 = 100 Mbps
With that information, one can follow the algorithm and get:
Gao, et al. Expires September 3, 2018 [Page 12]
Internet-Draft Compressing Path Vectors March 2018
c_1: x1 <= 100
c_2: x2 <= 100
c_3: x1 + x2 <= 100
y_1 = 100 Mbps <= b_1
y_2 = 100 Mbps <= b_2
y_3 = 200 Mbps > b_3
R = IS_REDUNDANT(V, P, B) = { 1, 2 }
5.3. Equivalent Decomposition
5.3.1. Parameters and Variables
The equivalent decomposition algorithm takes 4 parameters: the set of
network elements "V", the set of relevant host pairs "P", the set of
metrics "M" and the set of redundant network elements "R".
"V", "P" and "M" are as defined as in Section 5.1.1. If the "j"-th
metric is bandwidth, we can construct the set of available bandwidth
values "B" as "b_i = m_ij" and "R" is the output of the redundant
network element identification procedure, i.e. "R = IS_REDUNDANT(V,
P, B)". Otherwise, if bandwidth is not included in the metrics, "R"
is {1, ..., |V|}.
The output of the function EQUIV_DECOMP is a new set of network
elements "V'", a new set of relevant host pairs "P'", and a new set
of metrics "M'", i.e., "V', P', M' = EQUIV_DECOMP(V, P, M, R)".
5.3.2. Algorithm Description
1. Set "V'", "P'", "M'" to empty sets. Set "k" to 0. Go to step 2.
2. For each "i" such that "i" in "R", go to step 3. After
processing each "i", go to step 7.
3. For each "j" such that "j <> i", go to step 4. After processing
each "j", go to step 6.
4. If "p_j" is a subset of "p_i", go to step 5. Otherwise go to
step 3.
5. Let "p_i = p_i \ p_j" and "m_j = UPDATE(m_j, m_i)". Go to step
3.
6. If "p_i" is not empty, increment "k" by 1 and let "v'_k = v_i",
"p'_k = p_i" and "m'_k = m_i". Go to step 2.
Gao, et al. Expires September 3, 2018 [Page 13]
Internet-Draft Compressing Path Vectors March 2018
7. For each "i" such that "i" is not in "R", go to step 8. After
processing each "i", go to step 9.
8. Increment "k" by 1 and let "v'_k = v_i", "p'_k = p_i", "m'_k =
m_i". Go to step 7.
9. Return "V'", "P'" and "M'".
5.3.3. Example
Consider the case in Section 4.3. Before the decomposition, the
input to the algorithm is as follows:
V = { ane:1, ane:2, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh3->eh4 }
p_3 = { eh1->eh2, eh3->eh4 }
m_1 = { bw: 100 Mbps, rc: 3 }
m_2 = { bw: 100 Mbps, rc: 2 }
m_3 = { bw: 200 Mbps, rc: 1 }
R = { 3 }
Since there is only one element in "R", "v_i = ane:l5".
After the first iteration of steps 3-5 with "v_j = ane:1":
V = { ane:1, ane:2, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh3->eh4 }
p_3 = { eh3->eh4 }
m_1 = { bw: 100 Mbps, rc: 4 }
m_2 = { bw: 100 Mbps, rc: 2 }
m_3 = { bw: 200 Mbps, rc: 1 }
V' = { }
k = 0
After the second iteration of steps 3-5 with "v_j = ane:2":
Gao, et al. Expires September 3, 2018 [Page 14]
Internet-Draft Compressing Path Vectors March 2018
V = { ane:1, ane:2, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh3->eh4 }
p_3 = { }
m_1 = { bw: 100 Mbps, rc: 4 }
m_2 = { bw: 100 Mbps, rc: 3 }
m_3 = { bw: 200 Mbps, rc: 1 }
V' = { }
k = 0
After step 6, since "p_3" is now empty, it just goes back to step 2.
At step 2, since all indices in "R" has been processed, it goes to
step 7.
After the first iteration of steps 7-8 with "i = 1":
V = { ane:1, ane:2, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh3->eh4 }
p_3 = { }
m_1 = { bw: 100 Mbps, rc: 4 }
m_2 = { bw: 100 Mbps, rc: 3 }
m_3 = { bw: 200 Mbps, rc: 1 }
V' = { ane:1 }
k = 1
p'_1 = { eh1->eh2 } = p_1
m'_1 = { bw: 100 Mbps, rc: 4 } = m_1
After the second iteration of steps 7-8 with "i = 2":
Gao, et al. Expires September 3, 2018 [Page 15]
Internet-Draft Compressing Path Vectors March 2018
V = { ane:1, ane:2, ane:l5 }
p_1 = { eh1->eh2 }
p_2 = { eh3->eh4 }
p_3 = { }
m_1 = { bw: 100 Mbps, rc: 4 }
m_2 = { bw: 100 Mbps, rc: 3 }
m_3 = { bw: 200 Mbps, rc: 1 }
V' = { ane:1, ane:2 }
k = 2
p'_1 = { eh1->eh2 }
p'_2 = { eh3->eh4 } = p_2
m'_1 = { bw: 100 Mbps, rc: 4 }
m'_2 = { bw: 100 Mbps, rc: 3 } = m_2
So the final output of EQUIV_DECOMP is:
V' = { ane:1, ane:2 }
p'_1 = { eh1->eh2 }
p'_2 = { eh3->eh4 }
m'_1 = { bw: 100 Mbps, rc: 4 }
m'_2 = { bw: 100 Mbps, rc: 3 }
5.4. Execution Order
As the examples demonstrate, the three algorithms MUST be executed in
the same order as they are introduced, i.e., one MUST conduct
"EQUIV_AGGR" before "IS_REDUNDANT" or "EQUIV_DECOMP", and conduct
"IS_REDUNDANT" before "EQUIV_DECOMP". Otherwise, the results of the
compressed path vectors MAY NOT be correct.
6. Encoding/Decoding Path Vectors
The three algorithms work mostly with network elements. Existing
path vectors must be decoded before they can be passed on to the
algorithms and the compressed results must be encoded as path vectors
before they are sent to the clients. The decoding and encoding
processes are specified as below.
Gao, et al. Expires September 3, 2018 [Page 16]
Internet-Draft Compressing Path Vectors March 2018
6.1. Decoding Path Vectors
6.1.1. Parameters and Variables
The decoding algorithm DECODE takes a path vector response, which
consists of the path vector part "PV" and the element property part
"E".
Path vectors PV: The path vector part has a format of a CostMap
(EndpointCostMap) where the cost value is a list of abstract
network element names. We say a PID (endpoint address) "i" is IN
"PV" if and only if there is an entry "i" in the cost-map
(endpoint-cost-map), and denote the entry value as "PV[i]".
Similarly, we say a PID (endpoint address) "j" is IN "PV[i]" if
and only if there is an entry "j" in the DstCosts of "i", whose
value is denoted as "PV[i][j]".
Element property map E: The element property map "E" maps an
abstract network element name to its properties. We denote "E[n]"
as the properties of element with name "n" and "E[n][pn]" as the
value of property "pn".
The algorithm returns the set of elements "V", the set of relevant
host pairs "P", the set of metrics "M" and the available bandwidth
"B", as defined in Section 5.1.1 and Section 5.2.1. The algorithm
uses a "SET" function which transforms a list into a set, and uses a
"NAME" function which maps an integer in [1, K] to a unique property
name where there are K properties in "E".
6.1.2. Algorithm Description
1. Set "V", "P", "M" and "B" to empty sets. Set "k" to 0. Go to
step 2.
2. For each "i IN PV", go to step 3. After processing each "i", go
to step 8.
3. For each "j IN PV[i]", go to step 4. After processing each "j",
go to step 2.
4. For each "n" in "SET(PV[i][j])", go to step 5. After processing
each "n", go to step 3.
5. If "n" is not in "V", go to step 6. Otherwise, go to step 7.
6. Increment "k" by 1 and let "v_k = n", "p_k = { i->j }". Go to
step 4.
Gao, et al. Expires September 3, 2018 [Page 17]
Internet-Draft Compressing Path Vectors March 2018
7. Find the index of "n" in "V" denoted as "a", let "p_a =
UNION(p_a, {i->j})". Go to step 4.
8. For each "i" from 1 to |V|, go to step 9. After processing all
"i", go to step 11.
9. For each "j" from 1 to K, go to step 10. After processing all
"j", go back to step 8.
10. If "NAME(j) = 'availbw'", let "b_i = E[v_i][NAME(j)]". Let
"m_ij = E[v_i][NAME(j)]".
11. Return "V", "P", "M" and "B".
6.1.3. Example
Consider the following example:
HTTP/1.1 200 OK
Content-Length: [TBD]
Content-Type: multipart/related; boundary=example-2
--example-2
Content-Type: application/alto-endpointcost+json
{
"meta": {
"cost-types": [
{"cost-mode": "array", "cost-metric": "ane-path"}
]
}
"endpoint-cost-map": {
"ipv4:192.0.2.2": {
"ipv4:192.0.2.89": [ "ane:L1", "ane:L3", "ane:L4" ],
"ipv4:203.0.113.45": [ "ane:L1", "ane:L4", "ane:L5" ]
}
}
}
Gao, et al. Expires September 3, 2018 [Page 18]
Internet-Draft Compressing Path Vectors March 2018
--example-2
Content-Type: application/alto-propmap+json
{
"property-map": {
"ane:L1": { "availbw": 50 },
"ane:L3": { "availbw": 48 },
"ane:L4": { "availbw": 55 },
"ane:L5": { "availbw": 60 },
"ane:L7": { "availbw": 35 }
}
}
--example-2--
After the first iteration of Lines 2-5:
V = { ane:L1, ane:L3, ane:L4 }
p_1 = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
p_2 = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
p_3 = { ipv4:192.0.2.2->ipv4:192.0.2.89 }.
After the second iteration of Lines 2-5:
V = { ane:L1, ane:L3, ane:L4, ane:L5 }
p_1 = { ipv4:192.0.2.2->ipv4:192.0.2.89,
ipv4:192.0.2.2->ipv4:203.0.113.45 }
p_2 = { ipv4:192.0.2.2->ipv4:192.0.2.89,
ipv4:192.0.2.2->ipv4:203.0.113.45 }
p_3 = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
p_4 = { ipv4:192.0.2.2->ipv4:203.0.113.45 }.
After the first iteration of Lines 6-9 with "i = 1":
m_1 = [50]
b_1 = 50
After all four iterations of Lines 6-9:
Gao, et al. Expires September 3, 2018 [Page 19]
Internet-Draft Compressing Path Vectors March 2018
m_1 = [50]
m_2 = [48]
m_3 = [55]
m_4 = [60]
b_1 = 50
b_2 = 48
b_3 = 55
b_4 = 60
The decoded information can be passed on to "EQUIV_AGGR",
"IS_REDUNDANT" and "EQUIV_DECOMP" for compression.
6.2. Encoding Path Vectors
6.2.1. Parameters and Variables
The algorithm ENCODE is the reverse process of DECODE. It takes the
parameters "V", "P", "M" and constructs the path vector results.
The parameters are defined as in Section 5.1.1 and Section 5.2.1.
The algorithm also uses the NAME function in Section 6.1.1 which MUST
return the same results in a paired ENCODE/DECODE process, and the
"APPEND(L, e)" function which adds element "e" to list "L".
6.2.2. Algorithm Description
1. Set "PV={}", "E = {}". Go to step 2.
2. For each "v_i" in "V", go to step 3. If all "v_i" is processed,
go to step XX.
3. For each "a->b" in "p_i", go to step 4. If all such "a->b" is
processed, go to step 6.
4. If "a" is not in "PV", let "PV[a] = {}". Go to step 5.
5. If "b" is not in "PV[a]", let "PV[a][b] = [v_i]". Otherwise, let
"PV[a][b] = APPEND(PV[a][b], v_i)". Go to step 2.
6. For each index "k" in [1, K], go to step 7. If all "k" is
processed, go to step 1.
7. Set "E[v_i][NAME(k)] = m_ik". Go to step 6.
8. Return "PV" and "E".
Gao, et al. Expires September 3, 2018 [Page 20]
Internet-Draft Compressing Path Vectors March 2018
6.2.3. Example
We consider the encoding of the decoded example in Section 6.1.3.
V = { ane:L1, ane:L3, ane:L4, ane:L5 }
p_1 = { ipv4:192.0.2.2->ipv4:192.0.2.89,
ipv4:192.0.2.2->ipv4:203.0.113.45 }
p_2 = { ipv4:192.0.2.2->ipv4:192.0.2.89,
ipv4:192.0.2.2->ipv4:203.0.113.45 }
p_3 = { ipv4:192.0.2.2->ipv4:192.0.2.89 }
p_4 = { ipv4:192.0.2.2->ipv4:203.0.113.45 }
m_1 = [50]
m_2 = [48]
m_3 = [55]
m_4 = [60]
After the first iteration of steps 2-7:
PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1]
PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1]
E[ane:L1]["availbw"] = 50
After the second iteration:
PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1, ane:L3]
PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3]
E[ane:L1]["availbw"] = 50
E[ane:L3]["availbw"] = 48
After the third iteration:
PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1, ane:L3, ane:L4]
PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3]
E[ane:L1]["availbw"] = 50
E[ane:L3]["availbw"] = 48
E[ane:L4]["availbw"] = 55
After the fourth iteration:
Gao, et al. Expires September 3, 2018 [Page 21]
Internet-Draft Compressing Path Vectors March 2018
PV[ipv4:192.0.2.2][ipv4:192.0.2.89 ] = [ane:L1, ane:L3, ane:L4]
PV[ipv4:192.0.2.2][ipv4:203.0.113.45] = [ane:L1, ane:L3, ane:L5]
E[ane:L1]["availbw"] = 50
E[ane:L3]["availbw"] = 48
E[ane:L4]["availbw"] = 55
E[ane:L5]["availbw"] = 60
Eventually, one can use the previous information to construct the
endpoint cost service response.
HTTP/1.1 200 OK
Content-Length: [TBD]
Content-Type: multipart/related; boundary=example-2
--example-2
Content-Type: application/alto-endpointcost+json
{
"meta": {
"cost-types": [
{"cost-mode": "array", "cost-metric": "ane-path"}
]
}
"endpoint-cost-map": {
"ipv4:192.0.2.2": {
"ipv4:192.0.2.89": [ "ane:L1", "ane:L3", "ane:L4" ],
"ipv4:203.0.113.45": [ "ane:L1", "ane:L4", "ane:L5" ]
}
}
}
--example-2
Content-Type: application/alto-propmap+json
{
"property-map": {
"ane:L1": { "availbw": 50 },
"ane:L3": { "availbw": 48 },
"ane:L4": { "availbw": 55 },
"ane:L5": { "availbw": 60 },
}
}
--example-2--
Gao, et al. Expires September 3, 2018 [Page 22]
Internet-Draft Compressing Path Vectors March 2018
6.3. Compatibility
When the path vector extension is used with other extensions, such as
[I-D.ietf-alto-cost-calendar] and [I-D.ietf-alto-multi-cost], the
decoding and the encoding MUST only apply on the path vector part and
leave the other attributes as they are.
Hence, this extension does not change the compatibility between the
original path vector extension and other extensions.
7. Security Considerations
This document does not introduce any privacy or security issue on
ALTO servers not already present in the base ALTO protocol or in the
path vector extension.
The algorithms specified in this document can even help protect the
privacy of network providers by conducting irreversible
transformations on the original path vector.
8. IANA Considerations
This document does not define any new media type or introduce any new
IANA consideration.
9. Acknowledgments
The authors would like to thank Dr. Qiao Xiang, Mr. Jingxuan Zhang
(Tongji University), Prof. Jun Bi (Tsinghua University) and
Dr. Andreas Voellmy (Yale University) for their early engagement and
discussions.
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
10.2. Informative References
[I-D.ietf-alto-cost-calendar]
Randriamasy, S., Yang, Y., Wu, Q., Lingli, D., and N.
Schwan, "ALTO Cost Calendar", draft-ietf-alto-cost-
calendar-01 (work in progress), February 2017.
Gao, et al. Expires September 3, 2018 [Page 23]
Internet-Draft Compressing Path Vectors March 2018
[I-D.ietf-alto-incr-update-sse]
Roome, W. and Y. Yang, "ALTO Incremental Updates Using
Server-Sent Events (SSE)", draft-ietf-alto-incr-update-
sse-02 (work in progress), April 2016.
[I-D.ietf-alto-multi-cost]
Randriamasy, S., Roome, W., and N. Schwan, "Multi-Cost
ALTO", draft-ietf-alto-multi-cost-10 (work in progress),
April 2017.
[I-D.ietf-alto-path-vector]
Bernstein, G., Chen, S., Gao, K., Lee, Y., Roome, W.,
Scharf, M., Yang, Y., and J. Zhang, "ALTO Extension: Path
Vector Cost Mode", draft-ietf-alto-path-vector-00 (work in
progress), May 2017.
[RFC7285] Alimi, R., Ed., Penno, R., Ed., Yang, Y., Ed., Kiesel, S.,
Previdi, S., Roome, W., Shalunov, S., and R. Woundy,
"Application-Layer Traffic Optimization (ALTO) Protocol",
RFC 7285, DOI 10.17487/RFC7285, September 2014,
<http://www.rfc-editor.org/info/rfc7285>.
[TELGEN83]
Telgen, J., "Identifying Redundant Constraints and
Implicit Equalities in Systems of Linear Constraints",
Management Science , Volume 29, Issue 10,
DOI 10.1287/mnsc.29.10.1209, 1983,
<http://pubsonline.informs.org/doi/abs/10.1287/
mnsc.29.10.1209>.
Authors' Addresses
Kai Gao
Tsinghua University
30 Shuangqinglu Street
Beijing 100084
China
Email: gaok12@mails.tsinghua.edu.cn
Xin (Tony) Wang
Tongji University
4800 CaoAn Road
Shanghai 210000
China
Email: xinwang2014@hotmail.com
Gao, et al. Expires September 3, 2018 [Page 24]
Internet-Draft Compressing Path Vectors March 2018
Qiao Xiang
Tongji/Yale University
51 Prospect Street
New Haven, CT
USA
Email: qiao.xiang@cs.yale.edu
Chen Gu
Tongji University
4800 CaoAn Road
Shanghai 210000
China
Email: gc19931011jy@gmail.com
Y. Richard Yang
Yale University
51 Prospect St
New Haven CT
USA
Email: yry@cs.yale.edu
G. Robert Chen
Huawei
Nanjing
China
Email: chenguohai@huawei.com
Gao, et al. Expires September 3, 2018 [Page 25]
