ALTO N. Schwan
Internet-Draft W. Roome
Intended status: Standards Track Alcatel-Lucent Bell Labs
Expires: January 17, 2013 July 16, 2012
ALTO Incremental Updates
draft-schwan-alto-incr-updates-02
Abstract
The goal of Application-Layer Traffic Optimization (ALTO) is to
bridge the gap between network and applications by provisioning
network related information. This allows applications to make
informed decisions, for example when selecting a target host from a
set of candidates.
Therefore an ALTO server provides network and cost maps to its
clients. This draft discusses options on how to provide incremental
updates for these maps, with the goal of reducing the amount of data
needed for transmitting the maps and shortly evaluates the two most
promising options.
Schwan & Roome Expires January 17, 2013 [Page 1]
Internet-Draft ALTO Incremental Updates July 2012
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.
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 17, 2013.
Copyright Notice
Copyright (c) 2012 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.
Schwan & Roome Expires January 17, 2013 [Page 2]
Internet-Draft ALTO Incremental Updates July 2012
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 6
3. Determine Client Map Version . . . . . . . . . . . . . . . . . 7
3.1. HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1. If-Modified-Since HTTP Header . . . . . . . . . . . . 7
3.1.2. If-None-Match HTTP Header . . . . . . . . . . . . . . 9
3.2. Version-based incremental updates as ALTO extension . . . 10
3.2.1. CURRENT NETWORK MAP vtag . . . . . . . . . . . . . . . 10
3.2.2. Extensions to full cost-map response: . . . . . . . . 11
4. Incremental Update Options . . . . . . . . . . . . . . . . . . 12
4.1. Send entire map . . . . . . . . . . . . . . . . . . . . . 12
4.2. Patch map . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3. Encode map . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4. HTTP Range Retrieval . . . . . . . . . . . . . . . . . . . 12
4.5. JSON patch . . . . . . . . . . . . . . . . . . . . . . . . 13
4.6. ALTO Incremental Update service . . . . . . . . . . . . . 14
4.6.1. Incremental Update messages . . . . . . . . . . . . . 14
4.6.2. Incremental Update Capability . . . . . . . . . . . . 16
5. Numerical Evaluation . . . . . . . . . . . . . . . . . . . . . 18
5.1. Full Cost Map Size estimation . . . . . . . . . . . . . . 18
5.2. JSON Patch vs. ALTO extension . . . . . . . . . . . . . . 19
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21
7. Security Considerations . . . . . . . . . . . . . . . . . . . 22
8. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 23
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26
Schwan & Roome Expires January 17, 2013 [Page 3]
Internet-Draft ALTO Incremental Updates July 2012
1. Introduction
The goal of Application-Layer Traffic Optimization (ALTO) is to
bridge the gap between network and applications by provisioning
network related information. This allows applications to make
informed decisions, for example when selecting a target host from a
set of candidates. Typical applications are file sharing, real-time
communication and live streaming peer-to-peer networks [RFC5693] as
well as Content Distribution Networks
[I-D.jenkins-alto-cdn-use-cases].
The ALTO protocol [I-D.ietf-alto-protocol] is specified as a client-
server protocol based on the HyperText Transfer Protocol (HTTP) and
encoded in JavaScript Object Notation (JSON). An ALTO server
provides services that guide ALTO clients in their decisions. The
Endpoint Property Service allows ALTO clients to look up properties
of endpoints, for example its Netwok Location. The Endpoint Cost
Service allows ALTO server to rank endpoints amongst each other with
respect to numerical or ordinal costs. The Map Service and the Map
Filtering Service allows ALTO client to retrieve full or partial
Network Maps and the associated Cost Maps that are provisioned by an
ALTO server.
The ALTO Network Map contains groupings of endpoints as defined by
the ALTO server. By aggregating multiple endpoints that are close to
one another with respect to their network connectivity a greater
scalability is achieved. Each group of endpoints is associated to a
Network Location identifier called a PID, for example by a list of IP
prefixes that belong to the PID. The ALTO Server then indicates
preferences amongst the PIDs in the Cost Map by defining Path Costs
amongst sets of Netwok Locations.
The size of the Network and Cost Maps depend on the granularity of
the map an ALTO server provides for its clients. While some use
cases allow operators to configure their servers to support only a
small numbers of PIDs, other use cases are expected to require a much
greater accuracy in terms of network locations. In order to avoid
the transmission of the same information in each client request, a
mechanism that allows a server to send incremental updates, in
particular for large Network and Cost Maps, is needed.
The goal of this draft is to list and discuss the different options
that allow such incremental updates of Network and Cost Maps. It is
focused on options that are compatible with the ALTO base protocol
and encoding, namely HTTP and JSON. The draft is structured as
follows: First it lists options that allow a server to validate the
cached version of a map a client has. Then it dicsusses several
options a server has to send incremental updates, including JSON
Schwan & Roome Expires January 17, 2013 [Page 4]
Internet-Draft ALTO Incremental Updates July 2012
Patch and an ALTO extension. Finally it shortly evaluates two
promising options.
Comments and discussions about this memo should be directed to the
ALTO working group: alto@ietf.org.
Schwan & Roome Expires January 17, 2013 [Page 5]
Internet-Draft ALTO Incremental Updates July 2012
2. Problem Statement
The ALTO protocol uses Network and Cost Maps to allow ALTO servers
the specification of its own aggregated network view. Essentially
the Network Map contains information on how the endpoints are grouped
together, which is typically done according to their proximity. The
Cost Map contains Path Costs between the network regions defined in
the Network Map. The size of these maps strongly depends on the
scenario an ALTO server is configured for by its operator. While in
some scenarios both maps might only comprise s small number of PIDs,
others need much greater accuracy. For large maps partial updates
might become necessary.
Both map types have slightly different characteristics. Network Maps
in general are expected to be smaller than Cost Maps. As an example,
a Network Map with 5,000 PIDs, each having 10 cidrs will result in a
map with the size of roughly 1.25 megabytes. A Cost Map in contrast
contains a n*n matrix for cost entries where n is the number of PIDs.
Even for short PID names a full cost map for 5,000 PIDs takes up to
417 megabytes. Network Maps are also seen to be less dynamic than
Cost Maps. This is due to the fact that the topology an ALTO server
sees changes slower than the path costs of the network. Another
characteristic is that changes to the Network Map will impact the
Cost Map, whereas vice versa this is presumably not the case. A
final discussion on whether partial updates are useful for both map
types is out of the scope of this document.
The remainder of this document discusses options to allow partial
updates of Network and Cost Maps. Therefore two sections focus on
two separate problems that need a solution. The first part
(Section 3) discusses how an ALTO client and an ALTO server can
synchronize their map state without transmitting the whole map. This
is needed to identify whether a partial update can be applied and
also to calculate the partial update itself. The second part
(Section 4) of the document discusses how partial updates can be
encoded and sent to the client. The final section gives a numerical
evaluation of proposed incremental update options.
Schwan & Roome Expires January 17, 2013 [Page 6]
Internet-Draft ALTO Incremental Updates July 2012
3. Determine Client Map Version
To allow a server sending incremental updates to a client it first
needs to check the version of a cached map a client already has. In
this section we discuss options for this validation. We focus our
discussion on approaches where the client polls the ALTO server for
map changes and the server decides based on the client request.
Therefore we first discuss HTTP built-in options and follow-up with a
possible extension to ALTO network and cost maps themselves.
3.1. HTTP
HTTP [RFC2616] provides request-header fields to express conditional
requests. Typically these conditional requests are used by caches to
decide whether a copy of a resource they have can be served to a
requesting client directly or not. Responses to conditional HTTP
requests must be exactly the same as for normal HTTP GET requests.
Thus sending a modified map version (i.e. a partial update) violates
the HTTP standard. Conditional requests can still be used to avoid
transmitting an unchanged Map multiple times. The options are
discussed in the following.
3.1.1. If-Modified-Since HTTP Header
One possible option is to use the HTTP If-Modified-Since header in
the request if the client has previously contacted the ALTO service
and thus already has a version of the map. Therefore the server
includes date and time when the map was last modified into the Last-
Modified entity-header for a particular map, which is cached by the
client together with the map and sends it in new requests for the
same map in the If-Modified-Since header.
The following figure illustrates a GET request for a Network Map
Information Resource. Additionally the client indicates the time
when it retrieved the Network Map the last time in the If-Modified-
Since header field.
GET /networkmap HTTP/1.1
Host: alto.example.com
Accept: application/alto-networkmap+json,application/alto-error+json
If-Modified-Since: Sat, 24 Dec 2011 19:43:31 GMT
Figure 1: If-Modified-Since HTTP Header
A server retrieving this request uses the timestamp provided by the
client to decide whether to send a full map or no map at all in case
there were no changes. In case the Network Map has not been modified
since the time provided by the client in the request, the server
Schwan & Roome Expires January 17, 2013 [Page 7]
Internet-Draft ALTO Incremental Updates July 2012
SHOULD reply with a 304 HTTP response. The client then caches the
updated value of the Last-Modified entity-header for future requests.
304 Not Modified
Last-Modified: Sun, 25 Dec 2011 09:33:31 GMT
Figure 2: HTTP Response 304
In case the server determines that the timestamp provided by the
client is out-of-date it must return the full Network Map, as defined
in the ALTO core protocol specification. The following figure shows
the Last-Modified entity-header in the HTTP response that is used as
a timestamp for the map as well as the ETag header for a If-None-
Match request, as explained in section Section 3.1.2.
Schwan & Roome Expires January 17, 2013 [Page 8]
Internet-Draft ALTO Incremental Updates July 2012
HTTP/1.1 200 OK
Content-Length: [TODO]
Content-Type: application/alto-networkmap+json
Date: Sun, 25 Dec 2011 09:33:31 GMT
ETag: "nm000012"
{
"meta" : {},
"data" : {
"map-vtag" : "1266506139",
"map" : {
"PID1" : {
"ipv4" : [
"192.0.2.0/24",
"198.51.100.0/25"
]
},
"PID2" : {
"ipv4" : [
"198.51.100.128/25"
]
},
"PID3" : {
"ipv4" : [
"0.0.0.0/0"
],
"ipv6" : [
"::/0"
]
}
}
}
}
Figure 3: Full Network Map HTTP Response
3.1.2. If-None-Match HTTP Header
A second HTTP based mechanism could employ ETags in combination with
the If-None-Match header. Here the server creates entity tags that
identify the version of a map. A client that caches a map includes
this identifier in every future request. The server can use this
ETag to identify whether a cached map version is up-to-date.
The following example illustrates a client GET request which includes
an ETag, identifying a network map. The example assumes the client
received the Network Map response in Figure 3.
Schwan & Roome Expires January 17, 2013 [Page 9]
Internet-Draft ALTO Incremental Updates July 2012
GET /networkmap HTTP/1.1
Host: alto.example.com
Accept: application/alto-networkmap+json,application/alto-error+json
If-None-Match: "nm000012"
Figure 4: If-None-Match HTTP Header
3.2. Version-based incremental updates as ALTO extension
With this approach, clients poll the ALTO server for changes. The
server provides hints as to the polling frequency. We propose two
different mechanisms in the ALTO message format, one for network-map
changes, the other for cost-map changes.
For network-map changes, add a new GET-mode request, "CURRENT NETWORK
MAP VTAG." The response is short and simple: just the current map-
vtag and a hint about how often the network-map might change. Once a
client has the full network map, the client periodically sends that
CURRENT VTAG request to the server. If the map-vtag changes, the
client re-gets the network map. For cost-map changes, add two new
fields to the full cost-map response: a "cost-map-vtag" and a hint
about the how often the server updates the cost map.
Using these vtags both client and server can determine if it is
necessary to request or to send an updated map, a full map, or if the
current version is still up-to-date.
3.2.1. CURRENT NETWORK MAP vtag
This is a GET-mode request. The response is a simple json structure
with
o The current map-vtag for the network map.
o The average number of seconds between changes to the network map.
It needs a new media type, say application/alto-currentmapvtag+json
For example,
Schwan & Roome Expires January 17, 2013 [Page 10]
Internet-Draft ALTO Incremental Updates July 2012
HTTP/1.1 200 OK
Content-Length: [TODO]
Content-Type: application/alto-currentmapvtag+json
{
"meta" : {},
"data" : {
"map-vtag" : "123456",
"update-interval" : 86400
}
}
Figure 5: CURRENT NETWORK MAP vtag
3.2.2. Extensions to full cost-map response:
Add two new fields to the costmap response, as in:
object {
CostMode cost-mode;
CostType cost-type;
VersionTag map-vtag;
VersionTag cost-map-vtag; // Optional
JSONNumber update-interval; // Optional
CostMapData map;
} InfoResourceCostMap;
Figure 6: Extensions to full cost-map response
cost-map-vtag: A string that (together with the network map-vtag)
uniquely identifies this version of the cost map.
update-interval: Average time between cost-map updates, in seconds.
(A hint, not a guarantee). Perhaps required if cost-map-vtag is
present
These fields would only be in the full cost map response, not in a
filtered cost map response.
Schwan & Roome Expires January 17, 2013 [Page 11]
Internet-Draft ALTO Incremental Updates July 2012
4. Incremental Update Options
Once a server has decided to send a partial update, there are several
ways to do so. This section discusses these response options.
4.1. Send entire map
One trivial option is always to send the entire map anyways. The
advantage of sending the whole map typically is that there is no
computational effort needed on the server side. Thus this can always
be a fallback in case the server is under load, or in case a partial
update appears to be inefficient.
4.2. Patch map
A server that knows the version of the map a client currently has can
use this information to calculate the contextual diff to the newest
version of the map. This can also be done in a batch process for all
previous versions once a new map is loaded on the server to avoid a
per request calculation. The diff output can then be sent in a
response to the client, which in turn can use it to patch its version
of the map. By doing this the newest version of the map can be
recreated.
4.3. Encode map
One major goal of applying partial updates is to reduce transmission
time by reducing the amount of data which is to be transferred to the
client. This goal can be achieved by applying compression
techniques, such as gzip, to the message content, both for partial
updates as well as for entire maps.
HTTP supports this by the Content-Encoding entity header field. The
advantage of using compression is that there is no need to change the
underlying media-type of the response. Typically not all ALTO
clients will support this optimization from the beginning, thus the
server will need to store two representations of the maps: One which
is compressed and one uncompressed.
4.4. HTTP Range Retrieval
The HTTP Range header allows a client to request only a subset of a
resource. This is useful for quick recovery of partially failed
transfers. Using this option for incremental updates of ALTO Maps
difficult. The Byte range is specified by the client, however the
diff is calculated by the server. Thus an additional mechanism would
be needed tell the client which byte sequences to request to.
Additionally the Byte offsets might change between Map versions, thus
Schwan & Roome Expires January 17, 2013 [Page 12]
Internet-Draft ALTO Incremental Updates July 2012
this option appears to be error-prone.
4.5. JSON patch
JSON Patch [I-D.pbryan-json-patch] defines a JSON document structure
that allows partial modifications to a JSON document and defines the
associated media type "application/json-patch". Therefore JSON Patch
is a suitable option for incremental updates of the Network and Cost
Maps. JSON patch supports add, remove and replace operations that
can be used in combination with JSON Pointers
[I-D.pbryan-zyp-json-pointer] to modify values and arrays of the JSON
document members.
Typically JSON Patch is used in combination with the HTTP PATCH
method [RFC5789] to partially modify existing resources on a server.
As an ALTO client is not modifying a resource, but wants to be
updated if the resource has changed it needs to signal to the server
that it is able to receive and understand JSON Patch updates. This
can be done by including the media type "application/json-patch" in
the Accept header field of the HTTP request.
Although JSON Patch permits pointers to index individual array
elements, that's potentially ambiguous. "Add" and "delete" change
the array indexes; do subsequent updates to that array refer to the
original indexes or the revised indexes? And even if that's well-
specified, it's a potential source of error. Furthermore, some
clients may store the CIDRs in a PID as a set, rather than an array,
so they don't keep the original index numbers.
To avoid these problems, we recommend that when updating the CIDRs
for a PID, the server replaces the full array value for that PID,
rather than updating individual CIDRs by index.
This may also simplify the server, because it just has to flag the
PID as having changed; it doesn't have to remember the previous
sequence of CIDRs.
The following figure illustrates one example where the server decides
to send a partial update to the client using JSON Patch. The server
indicates this in the response Content-Type header. In the following
example the Network Map from the example in Figure 3 above has
changed. The map-vtag element has been incremented by 1, which
results in a replace operation for the respective element containing
the new value. Also two new subnets are added to the Network Map in
PID1 and PID2 by two replace operations on the ipv4 arrays.
Schwan & Roome Expires January 17, 2013 [Page 13]
Internet-Draft ALTO Incremental Updates July 2012
HTTP/1.1 200 OK
Content-Length: [TODO]
Content-Type: application/json-patch
Date: Sun, 25 Dec 2011 09:33:31 GMT
{ "replace": "/data/map-vtag", "value": "1266506140" },
{ "replace": "/data/map/PID1/ipv4", "value":
["192.0.2.0/24", "198.51.200.0/25", "198.51.100.0/25"] },
{ "replace": "/data/map/PID2/ipv4", "value":
["198.51.100.128/25", "198.51.200.128/25"] }
Figure 7: Partial update with JSON Patch
One benefit of using JSON Patch for partial updates would be if
standard JSON parsers would implement JSON Patch already. This would
allow ALTO protocol implementers to reuse existing functionality.
However to the knowledge of the authors there are only few
implementations supporting JSON Patch to date, and a widespread
adoption is still outstanding and will presumably take some time.
4.6. ALTO Incremental Update service
Another option is to offer a dedicated ALTO service for partial
updates. A client that determines that its current map is out-of-
date, for example by comparing cost-map-vtag values (see Section 3.2)
can then query this service to retrieve the partial update. This
section defines this service in the next section and an new
capability for the IRD in the following section
4.6.1. Incremental Update messages
This service can be implemented in new POST-mode requests, Get
Network Map Updates and Get Cost Map Updates. These partial update
messages use a new MIME type [RFC2046]:
"application/alto-update-param+json"
The client includes its current map version (i.e. the map-vtag or the
cost-map-vtag) to the post data of the request in a new reference tag
field. Based on this reference-tag a partial update response is
created. Or if the current (cost-)map-vtag is the same as the
reference-tag -- that is, if there are no changes -- the "map" entry
in the response has no entries. Or if it's sufficiently old that the
server no longer knows what changed since that version or if the tag
is invalid, the server returns a complete cost map. Thus the
response contains an optional field to allow clients to distinguish:
Schwan & Roome Expires January 17, 2013 [Page 14]
Internet-Draft ALTO Incremental Updates July 2012
{"full-map": true}
Thus the response MUST have costs that changed since the specified
version, but MAY have other costs as well.
The partial update response essentially is a Filtered Network Map or
Filtered Cost Map message, where for a Network Map for each PID in
the message, previous CIDRs are replaced with new CIDRs in case they
have changed. To remove a PID from the Map the value "delete" or an
empty array is used. PIDs that are not in the message remain
unchanged. Similarly for Cost Maps, costs specified in the message
replace previous costs for the respective source/destination PIDs.
Again, to remove a cost the value "delete" (or "-1", or "NaN",...) is
used whereas costs that are not in the message stay the same.
The following figures give one example of a request/response
transaction of the proposed Partial Update ALTO extension service.
POST /partialupdate/costmap/rcost/incrementalupdate/costmap
Content-Type: application/alto-update-param+json
Accept: application/alto-costmap+json
{ "reference-tag": "1266506140" }
Figure 8: Incremental update request
HTTP/1.1 200 OK
Content-Type: application/alto-costmap+json
{ "meta": {},
"data": {
"cost-mode": "numerical",
"cost-type": "routingcost",
"map-vtag": "314159",
"cost-vtag": "1266506141",
"full-map": false,
"map": { "PID1": { "PID2": 1, "PID3": 2 } }
}
}
Figure 9: Incremental update response
Schwan & Roome Expires January 17, 2013 [Page 15]
Internet-Draft ALTO Incremental Updates July 2012
4.6.2. Incremental Update Capability
An ALTO server needs to advertise its ability of providing
incremental updates to a client. One option of doing this is by
including an ALTO information resource capability indicating the
partial update option. This can be done per ALTO service, which
allows a fine grained control over which URIs handle partial
requests.
The following Information Resource Directory illustrates one example
where network and costmaps are available with and without partial
update option respectively. This is expressed by the JSONBool
capability element "partial-update".
Schwan & Roome Expires January 17, 2013 [Page 16]
Internet-Draft ALTO Incremental Updates July 2012
GET /directory HTTP/1.1
Host: alto.example.com
Accept: application/alto-directory+json,application/alto-error+json
HTTP/1.1 200 OK
Content-Length: [TODO]
Content-Type: application/alto-directory+json
{
"resources" : [
{
"uri" : "http://alto.example.com/serverinfo",
"media-types" : [ "application/alto-serverinfo+json" ]
}, {
"uri" : "http://alto.example.com/networkmap",
"media-types" : [ "application/alto-networkmap+json" ]
}, {
"uri" : "http://alto.example.com/costmap/rcost",
"media-types" : [ "application/alto-costmap+json" ],
"capabilities" : {
"cost-modes" : [ "numerical" ],
"cost-types" : [ "routingcost" ]
}
}, {
"uri" : "http://alto.example.com/partialupdate/networkmap",
"media-types" : [ "application/alto-networkmap+json" ]
"accepts" : [ "application/alto-update-param+json" ],
"capabilities" : {
"incremental-update" : true,
}
}, {
"uri" : "http://alto.example.com/partialupdate/costmap/rcost",
"media-types" : [ "application/alto-costmap+json" ],
"accepts" : [ "application/alto-update-param+json" ],
"capabilities" : {
"incremental-update" : true,
"cost-modes" : [ "numerical" ],
"cost-types" : [ "routingcost" ]
}
}
}
]
}
Figure 10: IRD With Partial Update Capability
Schwan & Roome Expires January 17, 2013 [Page 17]
Internet-Draft ALTO Incremental Updates July 2012
5. Numerical Evaluation
In this section we provide a numerical evaluation of the efficiency
of incremental updates. We focus on the two most promising
approaches JSON patch (Section 4.5) and the ALTO incremental Updates
service (Section 4.6). For our calculations we use cost map formats
to conclude on the incremental update efficiency.
5.1. Full Cost Map Size estimation
In the following we estimate the size of full cost maps with respects
to the number of PIDs that are contained. Neglecting some fixed
overhead we find:
np^2 * (4 + pl + cl) + np * (6 + pl)
where
np: number of PIDS
pl: Average length of PID names
cl: Average number of digits in costs
If we assume PID names are 8 characters (pl = 8) and costs are 3
digits (cl = 3), we get:
np cost-map size
10 1,640
25 9,725
50 38,200
100 151,400
250 941,000
500 3,757,000
1000 15,014,000
2500 93,785,000
5000 375,070,000
Figure 11: Full Cost Map Sizes
As a conclusion we do think that for less than 100 PIDs incremental
updates are not needed. Instead the Full Cost Map can be sent.
However for Maps that require a greater accuracy and thus a higher
number of PIDs incremental updates are required.
Schwan & Roome Expires January 17, 2013 [Page 18]
Internet-Draft ALTO Incremental Updates July 2012
5.2. JSON Patch vs. ALTO extension
In this section we estimate the performance of JSON Patch and the
proposed ALTO extension. We limit our estimation on the worst-case
scenario, which are replace operations.
For each changed cost a JSON Patch replace operation is represented
by the following encoding:
{ "replace": "meta.data.map.SRC-PID.DEST-PID", "value": 123 },
Whereas an Incremental Update ALTO Cost Map message as defined in
this document takes an encoding of (Note: This is actually the
encoding of the existing ALTO Cost Map response - it's just a matter
of interpretation):
"SRC-PID": {"DEST-PID": 123},
Note that this is the worst case, it takes less space if several
updates share the same source PID:
"SRC-PID": {"DEST-1": 123, "DEST-2": 321, ....},
The number of bytes per changed cost are:
JSON patch:
33 + 2*NameLength + CostLength
ALTO Cost Map Message (worst case):
8 + 2*NameLength + CostLength
We estimate the number of bytes for:
JSON patch:
cf * np * np * (33 + pl + cl)
ALTO Cost Map Message (worst case):
cf * np * np * (8 + pl + cl)
where
cf: Fraction of src-dest costs that changed (0 to 1)
np: Number of PIDS
pl: Average length of PID names
Schwan & Roome Expires January 17, 2013 [Page 19]
Internet-Draft ALTO Incremental Updates July 2012
cl: Average number of digits in costs
If we assume PID names are 8 characters (pl = 8) and costs are 3
digits (cl = 3), and 5% of the costs change (cf = .05), we get:
JSON ALTO Cost
np patch Map message
10 220 95
50 5,500 2,375
100 22,000 9,500
250 137,500 59,375
500 550,000 237,500
1000 2,200,000 950,000
2500 13,750,000 5,937,500
5000 55,000,000 23,750,000
Figure 12: Results JSON Patch vs. ALTO extension
Clearly, the ALTO extension as proposed in this document has a higher
efficiency in terms of encoded bytes needed compared to JSON Patch.
Schwan & Roome Expires January 17, 2013 [Page 20]
Internet-Draft ALTO Incremental Updates July 2012
6. IANA Considerations
The Incremental Update service as proposed introduces a new MIME type
"application/alto-update-param+json" which needs to be registered.
Schwan & Roome Expires January 17, 2013 [Page 21]
Internet-Draft ALTO Incremental Updates July 2012
7. Security Considerations
To be done in later versions of this document.
Schwan & Roome Expires January 17, 2013 [Page 22]
Internet-Draft ALTO Incremental Updates July 2012
8. Conclusion
This document describes different options that can be applied to
support incremental updates of ALTO Network and Cost maps. In
particular it comprises option for client and server to synchronize
themselves about their current map state, and further includes
options on how to encode partial updates. Finally it proposes an new
incremental update service and evaluates different options
numerically.
Schwan & Roome Expires January 17, 2013 [Page 23]
Internet-Draft ALTO Incremental Updates July 2012
9. References
[I-D.ietf-alto-protocol]
Alimi, R., Penno, R., and Y. Yang, "ALTO Protocol",
draft-ietf-alto-protocol-10 (work in progress),
October 2011.
[I-D.jenkins-alto-cdn-use-cases]
Niven-Jenkins, B., Watson, G., Bitar, N., Medved, J., and
S. Previdi, "Use Cases for ALTO within CDNs",
draft-jenkins-alto-cdn-use-cases-01 (work in progress),
June 2011.
[I-D.pbryan-json-patch]
Bryan, P., "JSON Patch", draft-pbryan-json-patch-02 (work
in progress), October 2011.
[I-D.pbryan-zyp-json-pointer]
Bryan, P. and K. Zyp, "JSON Pointer",
draft-pbryan-zyp-json-pointer-02 (work in progress),
October 2011.
[RFC2046] Freed, N. and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part Two: Media Types", RFC 2046,
November 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2616] Fielding, R., Gettys, J., Mogul, J., Frystyk, H.,
Masinter, L., Leach, P., and T. Berners-Lee, "Hypertext
Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999.
[RFC5693] Seedorf, J. and E. Burger, "Application-Layer Traffic
Optimization (ALTO) Problem Statement", RFC 5693,
October 2009.
[RFC5789] Dusseault, L. and J. Snell, "PATCH Method for HTTP",
RFC 5789, March 2010.
Schwan & Roome Expires January 17, 2013 [Page 24]
Internet-Draft ALTO Incremental Updates July 2012
Appendix A. Acknowledgments
The authors would like to thank Vijay Gurbani for his valuable input
and excellent feedback to this document.
Nico Schwan is partially supported by the ENVISION project
(http://www.envision-project.org), a research project supported by
the European Commission under its 7th Framework Program (contract no.
248565). The views and conclusions contained herein are those of the
authors and should not be interpreted as necessarily representing the
official policies or endorsements, either expressed or implied, of
the ENVISION project or the European Commission.
Schwan & Roome Expires January 17, 2013 [Page 25]
Internet-Draft ALTO Incremental Updates July 2012
Authors' Addresses
Nico Schwan
Alcatel-Lucent Bell Labs
Lorenzstrasse 10
Stuttgart 70435
Germany
Email: nico.schwan@alcatel-lucent.com
URI: www.alcatel-lucent.com/bell-labs
Bill Roome
Alcatel-Lucent Bell Labs
Email: w.roome@alcatel-lucent.com
URI: www.alcatel-lucent.com/bell-labs
Schwan & Roome Expires January 17, 2013 [Page 26]