ALTO WG K. Gao
Internet-Draft Tsinghua University
Intended status: Standards Track X. Wang
Expires: January 5, 2018 Tongji University
Q. Xiang
Tongji/Yale University
C. Gu
Tongji University
Y. Yang
Yale University
G. Chen
Huawei
July 4, 2017
A Recommendation for Compressing ALTO Path Vectors
draft-gao-alto-routing-state-abstraction-06.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, an algorithm is described which can effectively
reduce the redundancy in the network view while still providing the
same information as in the original path vectors. The algorithm is
fully compatible with the path vector extension and has several by-
products which can be leveraged by other extensions to achieve better
performances.
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].
Gao, et al. Expires January 5, 2018 [Page 1]
Internet-Draft Compressing Path Vectors July 2017
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
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 January 5, 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 and -05 . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Compressing Path Vectors . . . . . . . . . . . . . . . . . . 5
5. Equivalent Transformation Algorithm . . . . . . . . . . . . . 7
5.1. Parameters and Variables . . . . . . . . . . . . . . . . 7
5.2. Algorithm Description . . . . . . . . . . . . . . . . . . 8
6. Recommended Redundancy Check Algorithm . . . . . . . . . . . 9
6.1. Parameters and Variables . . . . . . . . . . . . . . . . 10
6.2. Algorithm Description . . . . . . . . . . . . . . . . . . 10
7. Reducing Unnecessary Incremental Updates . . . . . . . . . . 11
8. Extension for Customized Input Parameters . . . . . . . . . . 11
8.1. Parameters and Variables . . . . . . . . . . . . . . . . 11
8.2. Algorithm Description . . . . . . . . . . . . . . . . . . 12
Gao, et al. Expires January 5, 2018 [Page 2]
Internet-Draft Compressing Path Vectors July 2017
8.3. ALTO Extension for Client Constraint Map . . . . . . . . 12
8.4. Examples . . . . . . . . . . . . . . . . . . . . . . . . 14
8.5. Compatibility . . . . . . . . . . . . . . . . . . . . . . 20
9. Security Considerations . . . . . . . . . . . . . . . . . . . 20
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
12.1. Normative References . . . . . . . . . . . . . . . . . . 21
12.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.
A straw man approach, especially 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 is activated.
This document describes an algorithm that identifies redundant
abstract network elements and reduces them as much as possible. The
algorithm, namely the "equivalent transformation" algorithm, can be
integrated with any implementation of the path vector extension as a
post-processing step. As the name suggests, this algorithm
essentially conducts "equivalent" transformations on the original
path vectors, removes redundant information and obtains a more
compact view.
Gao, et al. Expires January 5, 2018 [Page 3]
Internet-Draft Compressing Path Vectors July 2017
This extension is fully compatible with 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 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.
Section 5 gives the equivalent transformation algorithm and Section 6
introduces a reference implementation of redundancy check algorithm.
Section 7 discusses how to generate filters for ALTO incremental
update services and Section 8 introduces an optional extension which
allows ALTO clients to share certain information and further improves
the performance of equivalent transformation. Finally, Section 9 and
Section 10 discuss security and IANA considerations.
2. Changes Since Version -03, -04 and -05
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
1. the equivalent transformation algorithm which compresses original
the path vectors to provide a more compact network view,
2. a reference implementation of the redundancy check algorithm
which provides near-optimal results, and
3. the client constraint map extension which allows ALTO clients to
optionally provide additional client-side information to help
further reduce the communication overhead.
The document also discusses how the algorithms and extension
introduced here can cooperate with existing working group drafts,
such as Incremental Updates, Multi-Cost and Cost Calendar.
The latest version (-06) also fixed some minor issues in -04 and -05.
Gao, et al. Expires January 5, 2018 [Page 4]
Internet-Draft Compressing Path Vectors July 2017
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.
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
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.
Gao, et al. Expires January 5, 2018 [Page 5]
Internet-Draft Compressing Path Vectors July 2017
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 Straw Man Implementation
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 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
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.
Gao, et al. Expires January 5, 2018 [Page 6]
Internet-Draft Compressing Path Vectors July 2017
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
just as much information. Meanwhile, the application can hardly
infer anything about the original topology with the compact path
vectors.
To reduce the communication overhead and improve the privacy
protection of the path vector extension, an algorithm is described in
this document to efficiently compute the compact path vectors.
5. Equivalent Transformation Algorithm
This section describes the path vector compression algorithm, namely
the "equivalent transformation" algorithm.
5.1. Parameters and Variables
The equivalent transformation algorithm accepts 3 parameters: the
original path vectors P, the corresponding abstract network element
property map M, and a redundancy check algorithm R(P, M).
Original path vectors P: The original path vectors P MUST have the
format of a cost map or an endpoint cost map, where each cost
value is a JSONArray of abstract network element names, as defined
in [I-D.ietf-alto-path-vector].
Abstract network element property map M: The abstract network
element property map M MUST contain all the abstract network
elements whose names are included in the original path vectors P.
It MUST contain at least one valid ALTO cost type which is
supported by the corresponding path vector service, but MUST NOT
contain ordinal values. Unless it is specifically defined in
another extension, the cost values MUST follow the associative
addition rule, e.g. cost(ane1) + cost(ane2) = cost(ane1 o ane2) =
cost(ane2) + cost(ane1) where ne1 o ne2 represents a virtual "ane-
path" consisting of ane1 and ane2. One exception is bandwidth,
where the "addition" is actually a "minimum" function.
Gao, et al. Expires January 5, 2018 [Page 7]
Internet-Draft Compressing Path Vectors July 2017
Redundancy check algorithm R(P, M): The redundancy check algorithm
R(P, M) MUST accept the two parameters P and M as specified above.
It MUST return a list of abstract network element names,
representing those whose corresponding constraints are redundant.
In addition to the parameters mentioned above, the algorithm also
maintains the following variables.
Temporary path vectors P0: P0 store the temporary values after each
step of equivalent transformation.
Temporary abstract network element property map M0: M0 stores the
temporary value of an abstract network element property map after
each step of equivalent transformation.
Reverse abstract network element map RM: RM is a map whose key is an
abstract network element name with the value being a set of
endpoint/PID pairs.
Redundant abstract network element set S: S contains the result of
the redundancy check algorithm R(P, M).
5.2. Algorithm Description
The equivalent transformation consists of the following steps:
1. When the algorithm starts execution, it sets P0 = P and M0 = M
2. For each abstract network element name "n", find the set of
endpoint/PID pairs {(a, b)} where "n" appears in the path vector
of a -> b in P0. Put the resultant set of endpoint/PID pairs in
RM with "n" as the key.
3. Group RM by the value sets, e.g. put all (n, v) which have the
same set of endpoint/PID pairs in the same group. It is
guaranteed that each abstract network element name only appears
once in one group. Now use the groups to construct a partition
of all abstract network element names, where each partition
contains all the abstract network element names from a single
group. Each partition is associated with a unique ID, which
follows the format of an abstract network element name as
defined in [I-D.ietf-alto-path-vector].
4. For each endpoint/PID pair in P0, replace the abstract network
element names with their group IDs. Construct an empty abstract
network element property map M1. For each group, create an
abstract network element property entry "e" where each abstract
network element property is the "sum" of the abstract network
Gao, et al. Expires January 5, 2018 [Page 8]
Internet-Draft Compressing Path Vectors July 2017
element property values in M0 of all abstract network elements
in the group. Put "e" in M1 with the group ID as the key and
also the abstract network element name. Replace M0 with M1.
5. Pass P0 and M0 to redundancy check algorithm R(P,M), and store
the result in S.
6. If only bandwidth is contained in M0, go to 7. Otherwise, go to
8.
7. For each endpoint/PID pair, remove the abstract network element
names in S from the path vectors. Remove the entries in M0
whose keys are in S. Go to 10.
8. Construct an empty abstract network element property map M1.
For each abstract network element property entry in M0, if the
abstract network element name is not in S, put the entry in M1.
For each abstract network element name "n" in S, find the
corresponding set of endpoint/PID pairs in RM. For each pair,
replace "n" in the corresponding path vector to a new unique
abstract network element name and put an entry in M1 whose key
is the new abstract network element name while the value being
the value of "n" in M0. Replace M0 with M1.
9. Repeat steps 2-4 and go to 10.
10. Create a virtual abstract network element "n" with a unique
abstract network element name and sufficiently large bandwidth
value. For each endpoint/PID pair in P, if the path vector is
an empty set (this only happens when only bandwidth is
requested), put the name of "n" in the path vector and add "n"
to M0.
11. Return P0 as the path vector response and M0 as the
corresponding abstract network element property map.
The term "sum" in step 4 is in quotes because the exact meaning
depends on the property types. As stated earlier, the values MUST
NOT be ordinal and MUST follow the associative addition rule unless
specifically defined in a later extension. This document defines one
exception -- bandwidth -- whose addition operator is the "minimum"
function, which satisfies the associative addition rule.
6. Recommended Redundancy Check Algorithm
In this section, an algorithm is described as a reference
implementation of the redundancy check algorithm R(P, M).
Gao, et al. Expires January 5, 2018 [Page 9]
Internet-Draft Compressing Path Vectors July 2017
6.1. Parameters and Variables
The algorithm takes two parameters: the path vectors P and the
corresponding abstract network element property map M.
Path vectors P: As specified in Section 5.1.
Abstract network element property map M: As specified in
Section 5.1.
In addition to the parameters, this algorithm also maintains the
following variable.
Set of linear constraints C: The set of linear constraints which can
be derived from P and M.
6.2. Algorithm Description
The algorithm consists of the following steps:
1. If the abstract network element properties in M do not include
bandwidth, return the set of all abstract network elements.
2. Construct the set of linear constraints, C. For each endpoint/
PID pair, define a variable "x_i" with a unique ID "i".
Construct RM as specified in step 3 of Section 5.2. For each
abstract network element "n", find the corresponding set of
endpoint/PID pairs "p_n" in RM. Construct a linear constraint
"c_n: A_n X <= b_n". The left hand side is the sum of all the
variables "{x_i}" whose coefficient "a_i" is 1 if the associated
pair is in "p_n" and otherwise 0. The right hand side is the
bandwidth of "n". Put "c_n" in C.
3. For each "c_i: A_i X <= b_i" in C, construct a new linear
programming problem:
max A_i X,
where A_j X <= b_j, j is not equal to i.
4. Solve this linear programming problem, let the maximum value be
"z". If "z <= b_i", this constraint is redundant. Otherwise the
constraint is NOT redundant.
5. Repeat steps 3-4 until the redundancy of all abstract network
elements in the original path vectors has been identified.
Return the set of abstract network elements whose corresponding
linear constraints are redundant.
Gao, et al. Expires January 5, 2018 [Page 10]
Internet-Draft Compressing Path Vectors July 2017
7. Reducing Unnecessary Incremental Updates
This section describes how an ALTO server implementation can use the
results in the redundancy check algorithm described in Section 6 to
filter unnecessary incremental updates.
Consider the example in Section 4 where the bandwidth of link1
(s1<=>s5) has increased from 100 Mbps to 150 Mbps. Straw man
approaches may push incremental updates to ALTO clients without
considering how the value changes. On the other hand, this link is
not included in the path vectors after equivalent transformation, and
one can conclude from the redundancy check algorithm Section 6.2 that
it can only be non-redundant if "b_i < z <= 100 Mbps". Since the new
"b_i" is 150 Mbps, this condition does not hold, i.e., link1 is still
redundant in the updated path vector. In that case, ALTO server MAY
NOT push the incremental updates.
However, this filter only works for redundant abstract network
elements, e.g. "z <= b_i". In all other cases, the path vectors have
to be recomputed to guarantee equivalence.
8. Extension for Customized Input Parameters
This section introduces an optional extension which can be leveraged
by ALTO clients to help reduce the communication overhead of path
vector services. In order to do so, a revised version of Section 6
must be introduced.
8.1. Parameters and Variables
The algorithm takes three parameters: the path vectors P, the
corresponding abstract network element property map M, and client
constraint map CM.
Path vectors P: Same as in Section 6.1.
Abstract network element property map M: Same as in Section 6.1.
Client constraint map CM: Client constraint map CM has the same
format as a cost map, where the first key represents the source
endpoint address/PID name, the second key represents the
destination endpoint address/PID name, and the value is a non-
negative float number representing the upper bound bandwidth value
for the given endpoint/PID pair.
The algorithm also maintains the following variables:
Set of linear constraints C: The same as C in Section 6.1.
Gao, et al. Expires January 5, 2018 [Page 11]
Internet-Draft Compressing Path Vectors July 2017
Set of client constraints CC: The set of linear constraints which
can be derived from CM.
8.2. Algorithm Description
The algorithm consists of the following steps:
1. The same as step 1 in Section 6.2.
2. The same as step 2 in Section 6.2.
3. For each endpoint/PID pair in CM, assume the value is a non-
negative number "u". If the pair is also in the original path
vector, construct a linear constraint "cc: x_i <= u" and add it
to CC where "x_i" is the variable associated with the same pair
in step 2.
4. For each "c_i: A_i X <= b_i" in C, construct a linear programming
problem:
max A_i X
where A_j X <= b_j in C, j is not equal to i
x_j <= u_j in CC
5. The same as step 4 in Section 6.2.
6. The same as step 5 in Section 6.2.
Clearly, the feasible region for each linear programming problem in
step 4 is smaller or equal to the one in Section 6.2. Thus, each
abstract network element has a higher chance of being redundant.
8.3. ALTO Extension for Client Constraint Map
This section describes the extensions needed to enable client
constraint map.
Any ALTO resource/service that supports client constraint map MUST
also support the path vector extension and accept the cost type whose
cost mode is "array" and cost metric "ane-path". This extension does
not change the specifications on "media types", "HTTP methods",
"uses", and "response".
8.3.1. Capabilities
The client constraint map extension requires a new capability field
"client-constraint-map" in the IRD.
Gao, et al. Expires January 5, 2018 [Page 12]
Internet-Draft Compressing Path Vectors July 2017
object {
JSONString cost-type-names<1..*>;
[JSONBool client-constraint-map;]
... capabilities defined by other extensions
} ClientConstraintMapCapabilities;
cost-type-names: As defined in Section 11.3.2.4 of [RFC7285].
client-constraint-map: If present and the value is "true", it means
the resource/service accepts client constraint map in the
parameters. Otherwise, the client MUST assume the server does not
support this extension and MUST NOT include client constraint map
in input parameters.
8.3.2. Accept Input Parameters
For filtered cost map with client constraint map extension, it MUST
accept the following parameters:
object {
[CostType cost-type;]
[PIDFilter pids;]
[ClientConstraintPIDMap client-constraint-map;]
... input parameters defined by other extensions
} ReqFilteredCostMap;
object {
PIDName -> ClientConstraintPIDGroup;
} ClientConstriantPIDMap;
object {
PIDName -> JSONNumber;
} ClientConstraintPIDGroup;
cost-type: As defined in Section 11.3.2.3 in [RFC7285]. It MUST
have the cost mode "array" and cost metric "ane-path" if the field
"client-constraint-map" is present. Otherwise, the ALTO server
MUST return an error with error code "E_INVALID_FIELD_VALUE".
pids: As defined in Section 11.3.2.3 in [RFC7285].
client-constraint-map: The client constraint map MUST have the
format as a JSON object "ClientConstraintPIDMap". All the PID
names in the client constraint map MUST also be included in
"pids", otherwise the ALTO server MUST return an error with error
code "E_INVALID_FIELD_VALUE". If the value for a given PID pair
is 0, ALTO server MUST not included this pair in the path vector.
Gao, et al. Expires January 5, 2018 [Page 13]
Internet-Draft Compressing Path Vectors July 2017
Similarly, the input parameters for endpoint cost services with
client constraint map MUST have the following format:
object {
[CostType cost-type;]
EndpointFilter endpoints;
[ClientConstraintEndpointMap client-constraint-map;]
... input parameters defined by other extensions
} ReqEndpointCostMap;
object {
TypedEndpointAddr -> ClientConstraintEndpointGroup;
} ClientConstriantEndpointMap;
object {
TypedEndpointAddr -> JSONNumber;
} ClientConstraintEndpointGroup;
cost-type: Same as above.
endpoints: As defined in Section 11.5.1.3 of [RFC7285].
client-constraint-map: The client constraint map contained in the
parameter MUST have the format of a JSON object
"ClientConstriantEndpointMap". All the endpoint addresses MUST
also appear in the "endpoints", otherwise the ALTO server MUST
return an error with an error code "E_INVALID_FIELD_VALUE". If
the value for a given endpoint pair is 0, ALTO server MUST NOT
included this pair in the path vector.
8.4. Examples
This section contains a series of examples for the client constraint
map extension.
8.4.1. Information Resource Directory Example
Gao, et al. Expires January 5, 2018 [Page 14]
Internet-Draft Compressing Path Vectors July 2017
{
"meta": {
"cost-types": {
"pv-ane": {
"cost-mode": "array",
"cost-metric": "ane-path"
}
}
},
"resource": {
"default-network-map": {
"uri": "http://alto.example.com/networkmap",
"media-type": "application/alto-networkmap+json"
},
"filtered-multi-cost-map": {
"uri": "http://alto.example.com/costmap/filtered",
"media-type": "application/alto-costmap+json",
"accepts": "application/alto-costmapfilter+json",
"uses": ["default-network-map"],
"capabilities": {
"cost-type-names": ["pv-ane"],
"property-map": "default-prop-map",
"client-constraint-map": true
}
},
"default-endpoint-cost-map": {
"uri": "http://alto.example.com/endpointcost/lookup",
"media-type": "application/alto-endpointcostmap+json",
"accepts": "application/alto-endpointcostparams+json",
"capabilities": {
"cost-type-names": ["pv-ane"],
"client-constraint-map": true
}
},
"default-prop-map": {
"uri": "http://alto.example.com/default-prop-map",
"media-type": "application/alto-propmap+json",
"accepts": "application/alto-propmapparams+json",
"capabilities": {
"domain-types": ["ane"],
"prop-types": [ "availbw" ]
}
}
}
}
Gao, et al. Expires January 5, 2018 [Page 15]
Internet-Draft Compressing Path Vectors July 2017
8.4.2. Filtered Cost Map Example
Assume we use the example in Section 4 and PID1-PID4 are mapped to
eh1-eh4 respectively.
POST /costmap/filtered HTTP/1.1
Host: alto.example.com
Accept: multipart/related, application/alto-costmap+json,
application/alto-propmap+json, application/alto-error+json
Content-Length: [TBD]
Content-Type: application/alto-costmapfilter+json
{
"cost-type": {
"cost-mode": "array",
"cost-metric": "ane-path"
},
"pids": {
"srcs": ["PID1", "PID3"],
"dsts": ["PID2", "PID4"]
},
"client-constraint-map": {
"PID1": { "PID2": 40, "PID4": 0 },
"PID3": { "PID2": 50, "PID4": 50 }
}
}
HTTP/1.1 200 OK
Content-Length: [TBD]
Content-Type: multipart/related; boundary=31415926
Gao, et al. Expires January 5, 2018 [Page 16]
Internet-Draft Compressing Path Vectors July 2017
--31415926
Content-Type: application/alto-costmap+json
{
"meta": {
"dependent-vtags": [
{
"resource-id": "default-network-map",
"tag": "75ed013b3cb58f896e839582504f622838ce670f"
}
],
"vtag": {
"resource-id": "cost-map-pv",
"tag": "27612897acf278ffu3287c284dd28841da78213",
"query-id": "query-cost-map-pv-276128"
},
"cost-type": {
"cost-mode": "array",
"cost-metric": "ane-path"
}
},
"cost-map": {
"PID1": {
"PID2": [ "ane:1" ]
},
"PID3": {
"PID2": [ "ane:1" ],
"PID4": [ "ane:1" ]
}
}
}
--31415926
Content-Type: application/alto-propmap+json
{
"property-map": {
"ane:1": { "availbw": 100 }
}
}
--31415926--
Since the bandwidth of all links is 100 Mbps, it can be easily
concluded that only link5 can potentially become a bottleneck with
the given client constraints. Thus, only one abstract network
element is returned.
Gao, et al. Expires January 5, 2018 [Page 17]
Internet-Draft Compressing Path Vectors July 2017
8.4.3. Endpoint Cost Service Example
Assume we use the example in Section 4 and eh1-eh4 are associated
with IP addresses 192.0.2.1-192.0.2.4 respectively.
POST /endpointcost/lookup HTTP/1.1
Host: alto.example.com
Accept: application/alto-endpointcost+json,
application/alto-error+json
Content-Length: [TBD]
Content-Type: application/alto-endpointcostparams+json
{
"cost-type": {
"cost-mode": "array",
"cost-metric": "ane-path"
},
"endpoints": {
"srcs": ["ipv4:192.0.2.1", "ipv4:192.0.2.3"],
"dsts": ["ipv4:192.0.2.2", "ipv4:192.0.2.4"]
},
"client-constraint-map": {
"ipv4:192.0.2.1": { "ipv4:192.0.2.2": 40, "ipv4:192.0.2.4": 0 },
"ipv4:192.0.2.3": { "ipv4:192.0.2.2": 50, "ipv4:192.0.2.4": 50 }
}
}
HTTP/1.1 200 OK
Content-Length: [TBD]
Content-Type: application/alto-endpointcost+json
Gao, et al. Expires January 5, 2018 [Page 18]
Internet-Draft Compressing Path Vectors July 2017
{
"meta": {
"vtag": {
"resource-id": "default-prop-map",
"tag": "a911354dfd1ef6555bfe7af07d3af0bfebe7c8a9",
"query-id": "query-ecs-a91135"
},
"cost-type": {
"cost-mode": "array",
"cost-metric": "ane-path"
}
},
"endpoint-cost-map": {
"ipv4:192.0.2.1": {
"ipv4:192.0.2.2": [ "ane:1" ]
},
"ipv4:192.0.2.3": {
"ipv4:192.0.2.2": [ "ane:1" ],
"ipv4:192.0.2.4": [ "ane:1" ]
}
}
}
Since the bandwidth for all links is 100 Mbps, it can be easily
concluded that only link5 can potentially become a bottleneck with
the given client constraints. Thus, only one abstract network
element is returned.
In this example, the abstract network element property map is not
attached so the client SHOULD send another request to fetch the
details about the abstract network elements.
POST /default-prop-map HTTP/1.1
Host: alto.example.com
Accept: application/alto-propmap+json, application/alto-error+json
Content-Length: [TBD]
Content-Type: application/alto-propmapparams+json
{
"query-id": "query-ecs-a91135",
"entities": [ "ane:1" ],
"properties": [ "availbw" ]
}
Gao, et al. Expires January 5, 2018 [Page 19]
Internet-Draft Compressing Path Vectors July 2017
HTTP/1.1 200 OK
Content-Length: [TBD]
Content-Type: application/alto-propmap+json
{
"property-map": {
"ane:1": { "availbw": 100 }
}
}
8.5. Compatibility
The client constraint map is fully compatible with the path vector
extension. For other extensions such as multi-cost
[I-D.ietf-alto-multi-cost] and cost calendar
[I-D.ietf-alto-cost-calendar], the input parameters MUST still follow
the definition of "client-constraint-map" but can adjust the
requirements for other fields.
Since the client constraint map extension is fully compatible with
the path vector extension, it does not alter the compatibility with
other extensions such as multi-cost and cost calendar.
9. 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.
The client constraint map extension defined in Section 8.3 can
potentially leak client-side information to ALTO servers. ALTO
client implementations MUST take information security into
consideration when using this extension, for example, only activating
this extension when the ALTO server is considered a trusted party.
ALTO clients can also obfuscate the information contained in a
request, for example, providing larger values than actual upper
bounds. Such obfuscation will not affect the correctness of the
response, but can potentially affect the reduction effect of client
constraint map.
Gao, et al. Expires January 5, 2018 [Page 20]
Internet-Draft Compressing Path Vectors July 2017
10. IANA Considerations
This document does not define any new media type or introduce any new
IANA consideration.
11. 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.
12. References
12.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>.
12.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.
[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.
Gao, et al. Expires January 5, 2018 [Page 21]
Internet-Draft Compressing Path Vectors July 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>.
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 January 5, 2018 [Page 22]
Internet-Draft Compressing Path Vectors July 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 January 5, 2018 [Page 23]