| ALTO | W. Roome |
| Internet-Draft | Alcatel-Lucent |
| Intended status: Standards Track | N. Schwan |
| Expires: August 17, 2014 | Thales Deutschland |
| February 13, 2014 |
ALTO Incremental Updates
draft-roome-alto-incr-updates-00
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. However, those maps can be very large, and portions of those maps may change frequently (the cost map in particular).
This draft presents a method to provide incremental updates for these maps. The goal is to reduce the load on the ALTO client and server by transmitting just the updated portions of those maps.
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].
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 August 17, 2014.
Copyright (c) 2014 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.
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 a client-server protocol based on the HyperText Transfer Protocol (HTTP) and encoded in JavaScript Object Notation (JSON). An ALTO server provides several services, two of which are relavent to this draft.
The ALTO Network Map Service makes the large space of endpoint addresses manageable by partitioning them into a small set of equivalence classes, called Provider-defined Identifiers, or PIDs. Each PID is defined by a set of endpoint address prefixes, or CIDRs [RFC4632]. The ALTO Server defines PIDs it sees fit. Some servers might define a fine-grained Network Map with thousands of PIDs, while others might define a course-grained Map with tens of PIDs. The only requirement is that the network costs for all endpoints in a PID are similar.
The ALTO Cost Map Service presents the unidirectional network cost between each pair of PIDs. Costs are numeric and non-negative, but an ALTO Server may omit unknown costs. Essentially a Cost Map is a sparse NxN matrix, where N is the number of PIDs in the Network Map.
The size of these maps depends primarily on the number of PIDs the ALTO Server choses to define. Because they go with the square of the number of PIDs, Cost Maps in particular can become very large. As an example, a Network Map with 5,000 PIDs, each with 10 CIDRs, is roughly 1.25 megabytes. A fully specified Cost Map for 5,000 PIDs takes up to 417 megabytes.
These maps may change at any time. Although not a protocol requirement, we expect that for many ALTO Servers, the Cost Map will change much more frequently than the Network Map. For example, the Cost Map might change every few minutes, as opposed to hours, if not days, between changes to the Network Map. However, we expect that only a small portion of these maps will change at any given time.
Thus with the base ALTO protocol, if a client wishes to maintain an up-to-date copy of the Network and Cost Maps, it must fetch a large amount of data very frequently, even though only a small fraction of that data will have changed. This puts additional load on the ALTO Server, the ALTO Client and the network. This draft presents an extension to the ALTO protocol to allow a client to fetch just the updated portion of those maps.
Comments and discussions about this memo should be directed to the ALTO working group: alto@ietf.org.
There are several issues involved in extending ALTO to allow incremental updates:
The issue is how does the server send incremental updates to the client? The two basic approaches are "server push", where the server sends updates to the client when they become available, versus "client pull", where the client periodically asks the server to send any changes.
In general, "server-push" is more efficient than "client-pull". However, ALTO is an HTTP-based protocol, and HTTP is a "client-pull" protocol. While there have been proposals to extend HTTP with push-like features, they tend to be fragile. Hence we will only consider solutions in which the client periodically polls the server via simple HTTP requests.
The next issue is how often should a client check the server for updates? The simplest solution is to use the HTTP Expires header ([RFC2616]). The full Network Map and Cost Map services return that header in the response, as a guideline for the client as to when to check for updates.
An alternative would be to add an "expires" field to the "meta" section of the response message, so the expiration date stays with the message body instead of being in the HTTP headers.
When requesting incremental updates, the client must tell the server what version the client has. Rather than inventing a new mechanism for that, we propose extending the ALTO protocol's "version tag" concept. The base protocol requires an ALTO Server to assign a unique id ("tag") to the Network Map, and update the tag every time the Network Map changes. We will extend that concept to Cost Maps as well.
The final question is how to represent an incremental update. Fortunately the ALTO Network Map and Cost Map response messages work very nicely to describe incremental updates; the client can update the PIDs and cost pairs in the message, and leave the other data as is.
JSON Patch ([RFC6902]) can also represent incremental changes. However, as described in Section 6.2, the existing Network and Cost Map messages are more appropriate.
Incremental update involves two new services, and extensions to the base protocol's Network Map and Cost Map services.
If an ALTO Server supports incremental update for a Network Map or Cost Map Service, the server SHOULD return the HTTP Date and Expires headers with the response for those services, as a suggestion to the ALTO Client as to when to poll the ALTO Server for an incremental update. If the server does not provide those headers, the client SHOULD make a reasonable guess.
If an ALTO Server supports incremental update for a Cost Map Service, the server MUST assign a "version tag" ("vtag") to each version of the Cost Map. As with Network Map vtags, the server MUST change the tag whenever any cost in the map changes. The ALTO Server puts the tag in the "meta" section of the response message, just as it does for a Network Map response.
When the Network Map changes -- that is, when the ALTO Server assigns a new tag to the Network Map -- the ALTO Server MUST assign a new tag to the Cost Map, even if no costs change.
For example, a Cost Map response would look something like this:
This addition is only required for Cost Map resources for which the ALTO Server chooses to offer incremental updates.
The Filtered Cost Map Service MUST not return the Cost Map vtag. If the client maintains a copy of the Full Cost Map, the client MUST NOT save the Filtered Cost Map costs in that table.
The reason is that Full and Filtered Cost Map Services may return inconsistent costs. For example, the costs returned by the Filtered Cost Map Service map be the may be more up-to-date than the costs returned by the Full Cost Map Service (see Section 5). This inconsistency is inherent in the base ALTO protocol, because an ALTO Server may update costs at any time. We do not believe this inconsistency will be a problem, because very few clients will use both the Full and Filtered Cost Map Services. That is, some clients, especially high-volume clients, will fetch and save the Full Cost Map, and use that to calculate costs as needed. These clients will use the incremental update service we describe to get changes to the full Cost Map. Other clients will use the Filtered Cost Map Service whenever they need to evaluate costs. These clients will not bother to fetch and save the Full Cost Map.
This new service returns the changes between current Network Map and a version previously retrieved by the client.
The media type is "application/alto-networkmap+json", the same as for a Full or Filtered Network Map.
An Incremental Network Map Update is requested using the HTTP POST method.
An ALTO Client supplies the vtag of the previous version by specifying media type "application/alto-vtag+json" with an HTTP POST body containing a JSON object of type VersionTag, as defined in Section 10.3 of [I-D.ietf-alto-protocol]:
None.
The Resource ID of the Network Map for which this resource supplies incremental updates.
The "meta" field of an Incremental Network Map Update response MUST include the "vtag" key with the latest version of the Network Map. The "resource-id" is for the Full Network Map Service, not the Incremental Update Service. In other words, the Incremental Update Service returns the same "vtag" that the Full Network Map Service would return.
The "meta" field MUST also include a "dependent-vtags" key with the "resource-id" of the Full Network Map Service and the "tag" of the client's current version. Thus the body of the response contains the changes from the "dependent-vtags" version to the "vtag" version.
The body of the response has the new definition of every PID that changed between the old version and the current version. PIDs not mentioned in the body keep the same set of prefixes as before. Note there is no provision for partial update of a PID; if a prefix is added to a PID, the Incremental Update response MUST include all prefixes for that PID.
There is no provision for deleting a PID. However, Incremental Update can give zero-length array of prefixes for a PID, which essentially deletes it.
If the version supplied by the client is still current, the "network-map" body will be empty, and the "tag" in "vtag" will be the same as the tag supplied by the client.
If the client's tag is invalid, or if it is so old that the ALTO Server is unable to provide incremental updates relative to that version, the ALTO Server MUST return an E_INVALID_FIELD_VALUE error response. The client SHOULD then use the Full Network Map Service to retrieve the latest version.
As with the Full Cost Map service, the Incremental Cost Map Update response SHOULD include the HTTP Date and Expires headers, as a hint to the client as to when to request another incremental update.
In this example, the Incremental Network Map Update Service reports that PID1 now has one prefix, and PID2 is no longer in use.
A client can discover the Incremental Update Service for a given Network Map by looking for a resource that uses the desired Network Map resource, returns the media type "application/alto-networkmap+json", and accepts the media type "application/alto-vtag+json".
This new service returns the changes between the current Cost Map and a version previously retrieved by the client.
The media type is "application/alto-costmap+json", the same as for a Full or Filtered Cost Map.
An Incremental Cost Map Update is requested using the HTTP POST method.
An ALTO Client supplies the vtag of the previous version by specifying media type "application/alto-vtag+json" with an HTTP POST body containing a JSON object of type VersionTag, as defined in Section 10.3 of [I-D.ietf-alto-protocol]:
None.
The Resource ID of the Cost Map for which this resource supplies incremental updates. An Incremental Cost Map Update resource MUST NOT list a Network Map resource. The Network Map is implicit in the "uses" list of the Cost Map resource.
The "meta" field of an Incremental Cost Map Update response MUST include the "vtag" key with the latest version of the Cost Map. The "resource-id" is for the Full Cost Map Service, not the Incremental Update Service; the Incremental Update Service returns the same "vtag" that the Full Cost Map Service would return.
The "meta" field MUST also include a "dependent-vtags" key with the vtag of the client's version of the Cost Map, to indicate that the body of the response contains the changes from the "dependent-vtags" version to the "vtag" version.
"dependent-vtags" must also include the vtag of the version of the Network Map resource that defines the PIDs in this Cost Map.
The body of the response has the cost points that changed between the old version and the current version. Costs not mentioned in the body keep the same values as before. The ALTO Server may set a cost to -1, to indicate that the cost for that source/destination pair is no longer known.
If the version supplied by the client is still current, the "network-map" body will be empty, and the "tag" in "vtag" will be the same as the tag supplied by the client.
If the client's tag is invalid, or if it is so old that the ALTO Server is unable to provide incremental updates relative to that version, the ALTO Server MUST return an E_INVALID_FIELD_VALUE error response. The client MUST use the Full Cost Map Service to retrieve the latest version.
As with the Full Network Map service, the Incremental Network Map Update response SHOULD include the HTTP Date and Expires headers, as a hint to the client as to when to request another incremental update.
In this example, the Incremental Cost Map Update Service reports that the cost from PID1 to PID2 is 10, and the cost from PID1 to PID99 is no longer available. All other costs remain the same as before.
A client can discover the Incremental Update Service for a given Cost Map by looking for a resource that uses the desired Cost Map resource, returns the media type "application/alto-costmap+json", and accepts the media type "application/alto-vtag+json".
The Incremental Cost Map Update Service is independent of the Incremental Network Map Update Service. An ALTO Server can implement one without the other.
The incremental update services do not affect clients who are not aware of this extension. According to the ALTO protocol, clients are required to ignore fields that are not defined in the base protocol, so existing clients should ignore the new version tag in the Cost Map response. Similarly, clients who are not aware of the new incremental update services will simply ignore those resources in the Information Resource Directory.
While this extension does not dictate how an ALTO Server would implement incremental updates, it is useful to outline one possible strategy.
First we will consider cost map updates. We start by assuming updates arrive individually rather than en masse. That is, if there are 1,000 PIDs, cost updates trickle in a few at a time, rather than all 1,000,000 costs arriving in one batch.
The server keeps two copies of the Cost Map: a "frozen" version and a "latest" version. The server also keeps a "change log" with the differences. The frozen version has a tag, the latest version does not. The Full Cost Map Service uses the frozen map, while the Filtered Cost Map Service uses the latest map.
As cost updates arrive, the server immediately applies them to the latest version, and saves the updated cost points in the change log. When the change log becomes large enough, the server applies all the logged updates to the frozen version, and assigns it a new tag.
Thus the frozen version of the Cost Map is updated in well defined steps. Each step has a tag as the version id, and the change logs contain the incremental changes between each version.
The server keeps the old change logs in a FIFO list indexed by the Cost Map version tags. That is, if tags are "1", "2", etc, then the change log for version "1" has the changes from "1" to "2", the change log for version "2" has the changes from "2" to "3", etc. When these logs take up too much space, the server deletes the oldest change logs. When a client requests an incremental update, the server finds the change log for the client's tag, and returns all cost updates in that log and all subsequent logs. If the server cannot find the client's tag in the change log table, the server returns an "invalid field" error code, and the client must retrieve the full Cost Map to get the updated costs. This covers the error cases of the tag being totally invalid as well as being too old.
We divide network map updates into two categories. Minor updates move some prefixes from one PID to another, perhaps to reflect temporary rerouting, but do not change the PID names. Major updates change PID names, add or delete PIDs, etc.
An ALTO Server can handle minor updates by keeping change logs with the prefixes for the updated PIDs, as described above for cost maps. When a client requests an incremental update, logically concatenate the logs from the client's tag to the current version.
For major network map changes, the server could just refuse to provide incremental updates. That is, when there is a major network map change, the server would simply discard all the old change logs.
Also, note that the Incremental Network Map Update Service is independent of the Incremental Cost Map Update Service. An ALTO Server may choose to provide Incremental Cost Map Updates without providing Incremental Network Map Updates.
This section presents several alternative approaches, and explains why we do not think they are appropriate.
The HTTP Protocol ([RFC2616]) defines several conditional-retrieval mechanisms, such as the If-Modified-Since and If-None-Match headers. These allow a client to retrieve a new version of a map only if the resource has changed since the client's last access.
However, these mechanisms do not allow incremental update. If only a few costs changed, the server would still have to send the entire map. Because we expect that parts of the maps will change frequently, we do not think these approaches are satisfactory.
A more promising alternative is JSON Patch ([RFC6902]). This is a standardized method of describing the changes between two versions of a JSON data structure. As such, it is ideally suited for incremental update. When a client requests an incremental update from the server, the server would return a JSON Patch description of the changes. Presumably JSON libraries will provide procedures to apply a patch to an previously retrieved JSON data structure, and to create a patch describing the differences between two versions of a JSON data structure. Clients can use the former methods to apply patches, and servers can use the latter to create them, so little additional programming is required.
Despite those advantages, we do not believe JSON Patch is a good solution for incremental update for ALTO. First, note that the existing ALTO Network and Cost Map response messages are, for all practical purposes, "patch" structures. All that is needed is the semantics that they represent changes to an existing map, rather than a completely new map. It is true that JSON Patch can represent a wider class of changes, but it is not clear that power is necessary for the incremental changes that an ALTO Server will make.
Next, JSON Patch is less efficient than our proposal. For example, suppose the cost for SRC-PID to DEST-PID changes to 123. Our proposal represents that as:
JSON Patch represents that change as:
Also, JSON Patch does not solve the "what version?" problem. Thus we still need to assign version tags to cost maps, and we would still need new services similar to our Incremental Network and Cost Map Update Services. The difference would be that the body of the responses would have JSON Patch data instead of the Network and Cost Map structures.
Finally, we have serious doubts as to whether JSON Patch can handle maps of the size we expect. To see the problem, realize that incremental update is only important for large maps. For small maps, a client can just retrieve the full version.
For a client to take advantage of an "apply patch" method in a JSON library, the client would almost certainly have to store the Cost Map using a Document Object Model (DOM) representation provided by that library. However, a DOM representation of a Cost Map with (say) 1,000 PIDs requires 1,000 associative tables, each of which has 1,000 entries. That takes a considerable amount of space.
However, there are far more efficient ways to represent an ALTO Cost Map. For example, an implicit assumption is that costs change more frequently than network maps. So a client can assign numbers to the PID names by sorting, and then store the costs in a 1,000x1,000 (possibly sparse) matrix. Furthermore, the client can use single precision floating point values; it is difficult to believe that the ALTO costs are accurate enough to require double precision. The resulting matrix takes much less space than a DOM representation, and can be searched much faster.
Therefore if we used JSON Patch, a client might be forced to use a very inefficient representation of a Cost Map.
JSON Patch causes similar problems for the ALTO Server. To take full advantage of JSON Patch, a server would have to present two DOM versions of the Cost Map to a "calculate patch" method. Those representations would take a lot of space. Furthermore, calculating the difference between two DOMs of that size will tax most computers. And finally, as we outlined above, we expect the ALTO Server will know the difference anyway.
To summarize, we believe that for ALTO incremental update, JSON Patch is an overly general approach that would be far too expensive.
The Incremental Update service as proposed introduces a new MIME type "application/alto-vtag+json" which needs to be registered.
This extension does not introduce any security issues that are not present in the base ALTO protocol.
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.
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.