ALTO N. Schwan Internet-Draft B. Roome Intended status: Standards Track Alcatel-Lucent Bell Labs Expires: June 3, 2012 December 1, 2011 ALTO Incremental Updates draft-schwan-alto-incr-updates-00 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. 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 June 3, 2012. Copyright Notice Copyright (c) 2011 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 Schwan & Roome Expires June 3, 2012 [Page 1] Internet-Draft ALTO Incremental Updates December 2011 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. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5 3. Determine Client Map Version . . . . . . . . . . . . . . . . . 6 3.1. If-Modified-Since HTTP Header . . . . . . . . . . . . . . 6 3.2. Version-based incremental updates . . . . . . . . . . . . 7 3.2.1. CURRENT NETWORK MAP vtag . . . . . . . . . . . . . . . 8 3.2.2. Extensions to full cost-map response: . . . . . . . . 8 4. Incremental Update Options . . . . . . . . . . . . . . . . . . 10 4.1. Send entire map . . . . . . . . . . . . . . . . . . . . . 10 4.2. Patch map . . . . . . . . . . . . . . . . . . . . . . . . 10 4.3. Encode map . . . . . . . . . . . . . . . . . . . . . . . . 10 4.4. JSON patch . . . . . . . . . . . . . . . . . . . . . . . . 10 4.5. Send only changed values . . . . . . . . . . . . . . . . . 11 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 6. Security Considerations . . . . . . . . . . . . . . . . . . . 14 7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 15 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . . 17 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 Schwan & Roome Expires June 3, 2012 [Page 2] Internet-Draft ALTO Incremental Updates December 2011 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. We divide the discussion in two larger parts. The first part lists options that allow a server to anticipate the map a client has without the transmission of the whole map. The second part then disusses the options a server has to send incremental updates. Schwan & Roome Expires June 3, 2012 [Page 3] Internet-Draft ALTO Incremental Updates December 2011 Comments and discussions about this memo should be directed to the ALTO working group: alto@ietf.org. Schwan & Roome Expires June 3, 2012 [Page 4] Internet-Draft ALTO Incremental Updates December 2011 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 m*n matrix for cost entries. 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 seperate 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. Schwan & Roome Expires June 3, 2012 [Page 5] Internet-Draft ALTO Incremental Updates December 2011 3. Determine Client Map Version To allow a server sending incremental updates to a client it first needs to know what version of the map a client already has. In this section we discuss options that allow a server to do so without having a client to send the whole map to the server. 3.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 it caches both, the map as well as the value of the Date header field of the HTTP response that contained the map. A server can then use the value of the If-Modified-Since header to compare if the clients current map is still up-to-date. 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, only partial updates of the 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 SHOULD reply with a 304 HTTP response. The client can then cache the updated value of the Date header field for future requests. 304 Not Modified Date: 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 and cannot be reused for a partial update it returns the full Network Map, as defined in the ALTO core protocol specification. The following figure shows the mandatory Date header field in the HTTP response that is used as a timestamp for the map. Schwan & Roome Expires June 3, 2012 [Page 6] Internet-Draft ALTO Incremental Updates December 2011 HTTP/1.1 200 OK Content-Length: [TODO] Content-Type: application/alto-networkmap+json Date: Sun, 25 Dec 2011 09:33:31 GMT { "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 In case the server determines that there was a change to the Network Map the server MAY choose not to send the full map, but a partial update only. Options for sending these partial updates are discussed in Section 4. 3.2. Version-based incremental updates 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 Schwan & Roome Expires June 3, 2012 [Page 7] Internet-Draft ALTO Incremental Updates December 2011 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, HTTP/1.1 200 OK Content-Length: [TODO] Content-Type: application/alto-currentmapvtag+json { "meta" : {}, "data" : { "map-vtag" : "123456", update-interval: 86400 } } Figure 4: CURRENT NETWORK MAP vtag 3.2.2. Extensions to full cost-map response: Add two new fields to the costmap response, as in: Schwan & Roome Expires June 3, 2012 [Page 8] Internet-Draft ALTO Incremental Updates December 2011 object { CostMode cost-mode; CostType cost-type; VersionTag map-vtag; VersionTag cost-map-vtag; // Optional JSONNumber update-interval; // Optional CostMapData map; } InfoResourceCostMap; Figure 5: 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 June 3, 2012 [Page 9] Internet-Draft ALTO Incremental Updates December 2011 4. Incremental Update Options Once a server has decided to send a partial update only there are several ways to do so. These 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 not 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 reponse. 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. 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 udates of the Network and Cost Maps. JSON patch supports add, remove and replace operations that can be used in combination with JSON Pointers Schwan & Roome Expires June 3, 2012 [Page 10] Internet-Draft ALTO Incremental Updates December 2011 [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. 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 reponse 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 add operations at the indexes 1 and 0 of the ipv4 arrays. 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" }, { "add": "/data/map/PID1/ipv4/1", "value": "198.51.200.0/25" }, { "add": "/data/map/PID2/ipv4/0", "value": "198.51.200.128/25" } Figure 6: Partial update with JSON Patch 4.5. Send only changed values Another option is to offer a dedicated ALTO service for partial updates. A client that detemines that its current map is out-of- date, for example by comparing cost-map-vtag values can then query this service to retrieve the partial update. This service can be implemented in a new POST-mode request, "GET COST-MAP CHANGES". The POST data would have a cost-map-vtag from a previous cost-map response. The response would be the same as for a full costmap request, except that it only has costs that have changed since the specified cost-map-vtag. The response would contain the current cost-map-vtag and update-interval. If the current cost-map-vtag is the same as the specified one -- that Schwan & Roome Expires June 3, 2012 [Page 11] Internet-Draft ALTO Incremental Updates December 2011 is, if there are no changes -- the "map" entry in the response has no cost entries. If the specified cost-map-vtag is invalid, or if it's sufficiently old that the server no longer knows what changed since that version, the server returns a complete cost map. Thus the response MUST have costs that changed since the specified version, but MAY have other costs as well. A possible implementation strategy for this service is to maintain at the server for each cost type an "instantaneous" cost map and the last N "numbered versions" of those costs. For a full-map requests without a version number, the server returns the most recent numbered-version map. For a COST-MAP CHANGES request, the server finds the client's version number in its stack of saved versions, and returns the diffs between that version and the most recent numbered version. If the server doesn't have the old version any more, the server returns the full latest version. Then periodically the server copies the instantaneous map to the last-stable map, assigns it a new version number, shuffles the list down, and discards the oldest version. The server could cache diffs and discard old ones. For filtered cost-map requests, the server could use either the "instantaneous" cost map or the most recent "versioned" cost map. Schwan & Roome Expires June 3, 2012 [Page 12] Internet-Draft ALTO Incremental Updates December 2011 5. IANA Considerations None. Schwan & Roome Expires June 3, 2012 [Page 13] Internet-Draft ALTO Incremental Updates December 2011 6. Security Considerations To be done in later versions of this document. Schwan & Roome Expires June 3, 2012 [Page 14] Internet-Draft ALTO Incremental Updates December 2011 7. 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. Schwan & Roome Expires June 3, 2012 [Page 15] Internet-Draft ALTO Incremental Updates December 2011 8. 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. [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 June 3, 2012 [Page 16] Internet-Draft ALTO Incremental Updates December 2011 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 June 3, 2012 [Page 17] Internet-Draft ALTO Incremental Updates December 2011 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 June 3, 2012 [Page 18]