idnits 2.17.1 draft-schwan-alto-incr-updates-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 353 has weird spacing: '...ostMode cos...' == Line 354 has weird spacing: '...ostType cos...' == Line 355 has weird spacing: '...sionTag map-v...' == Line 356 has weird spacing: '...sionTag cost-...' == Line 357 has weird spacing: '...NNumber updat...' == (1 more instance...) -- The document date (July 16, 2012) is 4301 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'TODO' is mentioned on line 573, but not defined == Outdated reference: A later version (-27) exists of draft-ietf-alto-protocol-10 == Outdated reference: A later version (-03) exists of draft-jenkins-alto-cdn-use-cases-01 ** Downref: Normative reference to an Informational draft: draft-jenkins-alto-cdn-use-cases (ref. 'I-D.jenkins-alto-cdn-use-cases') == Outdated reference: A later version (-04) exists of draft-pbryan-json-patch-02 ** Downref: Normative reference to an Informational draft: draft-pbryan-json-patch (ref. 'I-D.pbryan-json-patch') ** Downref: Normative reference to an Informational draft: draft-pbryan-zyp-json-pointer (ref. 'I-D.pbryan-zyp-json-pointer') ** Obsolete normative reference: RFC 2616 (Obsoleted by RFC 7230, RFC 7231, RFC 7232, RFC 7233, RFC 7234, RFC 7235) ** Downref: Normative reference to an Informational RFC: RFC 5693 Summary: 6 errors (**), 0 flaws (~~), 11 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ALTO N. Schwan 3 Internet-Draft W. Roome 4 Intended status: Standards Track Alcatel-Lucent Bell Labs 5 Expires: January 17, 2013 July 16, 2012 7 ALTO Incremental Updates 8 draft-schwan-alto-incr-updates-02 10 Abstract 12 The goal of Application-Layer Traffic Optimization (ALTO) is to 13 bridge the gap between network and applications by provisioning 14 network related information. This allows applications to make 15 informed decisions, for example when selecting a target host from a 16 set of candidates. 18 Therefore an ALTO server provides network and cost maps to its 19 clients. This draft discusses options on how to provide incremental 20 updates for these maps, with the goal of reducing the amount of data 21 needed for transmitting the maps and shortly evaluates the two most 22 promising options. 24 Requirements Language 26 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 27 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 28 document are to be interpreted as described in RFC 2119 [RFC2119]. 30 Status of this Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on January 17, 2013. 47 Copyright Notice 49 Copyright (c) 2012 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 2. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 6 66 3. Determine Client Map Version . . . . . . . . . . . . . . . . . 7 67 3.1. HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 68 3.1.1. If-Modified-Since HTTP Header . . . . . . . . . . . . 7 69 3.1.2. If-None-Match HTTP Header . . . . . . . . . . . . . . 9 70 3.2. Version-based incremental updates as ALTO extension . . . 10 71 3.2.1. CURRENT NETWORK MAP vtag . . . . . . . . . . . . . . . 10 72 3.2.2. Extensions to full cost-map response: . . . . . . . . 11 73 4. Incremental Update Options . . . . . . . . . . . . . . . . . . 12 74 4.1. Send entire map . . . . . . . . . . . . . . . . . . . . . 12 75 4.2. Patch map . . . . . . . . . . . . . . . . . . . . . . . . 12 76 4.3. Encode map . . . . . . . . . . . . . . . . . . . . . . . . 12 77 4.4. HTTP Range Retrieval . . . . . . . . . . . . . . . . . . . 12 78 4.5. JSON patch . . . . . . . . . . . . . . . . . . . . . . . . 13 79 4.6. ALTO Incremental Update service . . . . . . . . . . . . . 14 80 4.6.1. Incremental Update messages . . . . . . . . . . . . . 14 81 4.6.2. Incremental Update Capability . . . . . . . . . . . . 16 82 5. Numerical Evaluation . . . . . . . . . . . . . . . . . . . . . 18 83 5.1. Full Cost Map Size estimation . . . . . . . . . . . . . . 18 84 5.2. JSON Patch vs. ALTO extension . . . . . . . . . . . . . . 19 85 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 86 7. Security Considerations . . . . . . . . . . . . . . . . . . . 22 87 8. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 23 88 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 89 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . . 25 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26 92 1. Introduction 94 The goal of Application-Layer Traffic Optimization (ALTO) is to 95 bridge the gap between network and applications by provisioning 96 network related information. This allows applications to make 97 informed decisions, for example when selecting a target host from a 98 set of candidates. Typical applications are file sharing, real-time 99 communication and live streaming peer-to-peer networks [RFC5693] as 100 well as Content Distribution Networks 101 [I-D.jenkins-alto-cdn-use-cases]. 103 The ALTO protocol [I-D.ietf-alto-protocol] is specified as a client- 104 server protocol based on the HyperText Transfer Protocol (HTTP) and 105 encoded in JavaScript Object Notation (JSON). An ALTO server 106 provides services that guide ALTO clients in their decisions. The 107 Endpoint Property Service allows ALTO clients to look up properties 108 of endpoints, for example its Netwok Location. The Endpoint Cost 109 Service allows ALTO server to rank endpoints amongst each other with 110 respect to numerical or ordinal costs. The Map Service and the Map 111 Filtering Service allows ALTO client to retrieve full or partial 112 Network Maps and the associated Cost Maps that are provisioned by an 113 ALTO server. 115 The ALTO Network Map contains groupings of endpoints as defined by 116 the ALTO server. By aggregating multiple endpoints that are close to 117 one another with respect to their network connectivity a greater 118 scalability is achieved. Each group of endpoints is associated to a 119 Network Location identifier called a PID, for example by a list of IP 120 prefixes that belong to the PID. The ALTO Server then indicates 121 preferences amongst the PIDs in the Cost Map by defining Path Costs 122 amongst sets of Netwok Locations. 124 The size of the Network and Cost Maps depend on the granularity of 125 the map an ALTO server provides for its clients. While some use 126 cases allow operators to configure their servers to support only a 127 small numbers of PIDs, other use cases are expected to require a much 128 greater accuracy in terms of network locations. In order to avoid 129 the transmission of the same information in each client request, a 130 mechanism that allows a server to send incremental updates, in 131 particular for large Network and Cost Maps, is needed. 133 The goal of this draft is to list and discuss the different options 134 that allow such incremental updates of Network and Cost Maps. It is 135 focused on options that are compatible with the ALTO base protocol 136 and encoding, namely HTTP and JSON. The draft is structured as 137 follows: First it lists options that allow a server to validate the 138 cached version of a map a client has. Then it dicsusses several 139 options a server has to send incremental updates, including JSON 140 Patch and an ALTO extension. Finally it shortly evaluates two 141 promising options. 143 Comments and discussions about this memo should be directed to the 144 ALTO working group: alto@ietf.org. 146 2. Problem Statement 148 The ALTO protocol uses Network and Cost Maps to allow ALTO servers 149 the specification of its own aggregated network view. Essentially 150 the Network Map contains information on how the endpoints are grouped 151 together, which is typically done according to their proximity. The 152 Cost Map contains Path Costs between the network regions defined in 153 the Network Map. The size of these maps strongly depends on the 154 scenario an ALTO server is configured for by its operator. While in 155 some scenarios both maps might only comprise s small number of PIDs, 156 others need much greater accuracy. For large maps partial updates 157 might become necessary. 159 Both map types have slightly different characteristics. Network Maps 160 in general are expected to be smaller than Cost Maps. As an example, 161 a Network Map with 5,000 PIDs, each having 10 cidrs will result in a 162 map with the size of roughly 1.25 megabytes. A Cost Map in contrast 163 contains a n*n matrix for cost entries where n is the number of PIDs. 164 Even for short PID names a full cost map for 5,000 PIDs takes up to 165 417 megabytes. Network Maps are also seen to be less dynamic than 166 Cost Maps. This is due to the fact that the topology an ALTO server 167 sees changes slower than the path costs of the network. Another 168 characteristic is that changes to the Network Map will impact the 169 Cost Map, whereas vice versa this is presumably not the case. A 170 final discussion on whether partial updates are useful for both map 171 types is out of the scope of this document. 173 The remainder of this document discusses options to allow partial 174 updates of Network and Cost Maps. Therefore two sections focus on 175 two separate problems that need a solution. The first part 176 (Section 3) discusses how an ALTO client and an ALTO server can 177 synchronize their map state without transmitting the whole map. This 178 is needed to identify whether a partial update can be applied and 179 also to calculate the partial update itself. The second part 180 (Section 4) of the document discusses how partial updates can be 181 encoded and sent to the client. The final section gives a numerical 182 evaluation of proposed incremental update options. 184 3. Determine Client Map Version 186 To allow a server sending incremental updates to a client it first 187 needs to check the version of a cached map a client already has. In 188 this section we discuss options for this validation. We focus our 189 discussion on approaches where the client polls the ALTO server for 190 map changes and the server decides based on the client request. 191 Therefore we first discuss HTTP built-in options and follow-up with a 192 possible extension to ALTO network and cost maps themselves. 194 3.1. HTTP 196 HTTP [RFC2616] provides request-header fields to express conditional 197 requests. Typically these conditional requests are used by caches to 198 decide whether a copy of a resource they have can be served to a 199 requesting client directly or not. Responses to conditional HTTP 200 requests must be exactly the same as for normal HTTP GET requests. 201 Thus sending a modified map version (i.e. a partial update) violates 202 the HTTP standard. Conditional requests can still be used to avoid 203 transmitting an unchanged Map multiple times. The options are 204 discussed in the following. 206 3.1.1. If-Modified-Since HTTP Header 208 One possible option is to use the HTTP If-Modified-Since header in 209 the request if the client has previously contacted the ALTO service 210 and thus already has a version of the map. Therefore the server 211 includes date and time when the map was last modified into the Last- 212 Modified entity-header for a particular map, which is cached by the 213 client together with the map and sends it in new requests for the 214 same map in the If-Modified-Since header. 216 The following figure illustrates a GET request for a Network Map 217 Information Resource. Additionally the client indicates the time 218 when it retrieved the Network Map the last time in the If-Modified- 219 Since header field. 221 GET /networkmap HTTP/1.1 222 Host: alto.example.com 223 Accept: application/alto-networkmap+json,application/alto-error+json 224 If-Modified-Since: Sat, 24 Dec 2011 19:43:31 GMT 226 Figure 1: If-Modified-Since HTTP Header 228 A server retrieving this request uses the timestamp provided by the 229 client to decide whether to send a full map or no map at all in case 230 there were no changes. In case the Network Map has not been modified 231 since the time provided by the client in the request, the server 232 SHOULD reply with a 304 HTTP response. The client then caches the 233 updated value of the Last-Modified entity-header for future requests. 235 304 Not Modified 236 Last-Modified: Sun, 25 Dec 2011 09:33:31 GMT 238 Figure 2: HTTP Response 304 240 In case the server determines that the timestamp provided by the 241 client is out-of-date it must return the full Network Map, as defined 242 in the ALTO core protocol specification. The following figure shows 243 the Last-Modified entity-header in the HTTP response that is used as 244 a timestamp for the map as well as the ETag header for a If-None- 245 Match request, as explained in section Section 3.1.2. 247 HTTP/1.1 200 OK 248 Content-Length: [TODO] 249 Content-Type: application/alto-networkmap+json 250 Date: Sun, 25 Dec 2011 09:33:31 GMT 251 ETag: "nm000012" 253 { 254 "meta" : {}, 255 "data" : { 256 "map-vtag" : "1266506139", 257 "map" : { 258 "PID1" : { 259 "ipv4" : [ 260 "192.0.2.0/24", 261 "198.51.100.0/25" 262 ] 263 }, 264 "PID2" : { 265 "ipv4" : [ 266 "198.51.100.128/25" 267 ] 268 }, 269 "PID3" : { 270 "ipv4" : [ 271 "0.0.0.0/0" 272 ], 273 "ipv6" : [ 274 "::/0" 275 ] 276 } 277 } 278 } 279 } 281 Figure 3: Full Network Map HTTP Response 283 3.1.2. If-None-Match HTTP Header 285 A second HTTP based mechanism could employ ETags in combination with 286 the If-None-Match header. Here the server creates entity tags that 287 identify the version of a map. A client that caches a map includes 288 this identifier in every future request. The server can use this 289 ETag to identify whether a cached map version is up-to-date. 291 The following example illustrates a client GET request which includes 292 an ETag, identifying a network map. The example assumes the client 293 received the Network Map response in Figure 3. 295 GET /networkmap HTTP/1.1 296 Host: alto.example.com 297 Accept: application/alto-networkmap+json,application/alto-error+json 298 If-None-Match: "nm000012" 300 Figure 4: If-None-Match HTTP Header 302 3.2. Version-based incremental updates as ALTO extension 304 With this approach, clients poll the ALTO server for changes. The 305 server provides hints as to the polling frequency. We propose two 306 different mechanisms in the ALTO message format, one for network-map 307 changes, the other for cost-map changes. 309 For network-map changes, add a new GET-mode request, "CURRENT NETWORK 310 MAP VTAG." The response is short and simple: just the current map- 311 vtag and a hint about how often the network-map might change. Once a 312 client has the full network map, the client periodically sends that 313 CURRENT VTAG request to the server. If the map-vtag changes, the 314 client re-gets the network map. For cost-map changes, add two new 315 fields to the full cost-map response: a "cost-map-vtag" and a hint 316 about the how often the server updates the cost map. 318 Using these vtags both client and server can determine if it is 319 necessary to request or to send an updated map, a full map, or if the 320 current version is still up-to-date. 322 3.2.1. CURRENT NETWORK MAP vtag 324 This is a GET-mode request. The response is a simple json structure 325 with 327 o The current map-vtag for the network map. 329 o The average number of seconds between changes to the network map. 331 It needs a new media type, say application/alto-currentmapvtag+json 333 For example, 334 HTTP/1.1 200 OK 335 Content-Length: [TODO] 336 Content-Type: application/alto-currentmapvtag+json 338 { 339 "meta" : {}, 340 "data" : { 341 "map-vtag" : "123456", 342 "update-interval" : 86400 343 } 344 } 346 Figure 5: CURRENT NETWORK MAP vtag 348 3.2.2. Extensions to full cost-map response: 350 Add two new fields to the costmap response, as in: 352 object { 353 CostMode cost-mode; 354 CostType cost-type; 355 VersionTag map-vtag; 356 VersionTag cost-map-vtag; // Optional 357 JSONNumber update-interval; // Optional 358 CostMapData map; 359 } InfoResourceCostMap; 361 Figure 6: Extensions to full cost-map response 363 cost-map-vtag: A string that (together with the network map-vtag) 364 uniquely identifies this version of the cost map. 366 update-interval: Average time between cost-map updates, in seconds. 367 (A hint, not a guarantee). Perhaps required if cost-map-vtag is 368 present 370 These fields would only be in the full cost map response, not in a 371 filtered cost map response. 373 4. Incremental Update Options 375 Once a server has decided to send a partial update, there are several 376 ways to do so. This section discusses these response options. 378 4.1. Send entire map 380 One trivial option is always to send the entire map anyways. The 381 advantage of sending the whole map typically is that there is no 382 computational effort needed on the server side. Thus this can always 383 be a fallback in case the server is under load, or in case a partial 384 update appears to be inefficient. 386 4.2. Patch map 388 A server that knows the version of the map a client currently has can 389 use this information to calculate the contextual diff to the newest 390 version of the map. This can also be done in a batch process for all 391 previous versions once a new map is loaded on the server to avoid a 392 per request calculation. The diff output can then be sent in a 393 response to the client, which in turn can use it to patch its version 394 of the map. By doing this the newest version of the map can be 395 recreated. 397 4.3. Encode map 399 One major goal of applying partial updates is to reduce transmission 400 time by reducing the amount of data which is to be transferred to the 401 client. This goal can be achieved by applying compression 402 techniques, such as gzip, to the message content, both for partial 403 updates as well as for entire maps. 405 HTTP supports this by the Content-Encoding entity header field. The 406 advantage of using compression is that there is no need to change the 407 underlying media-type of the response. Typically not all ALTO 408 clients will support this optimization from the beginning, thus the 409 server will need to store two representations of the maps: One which 410 is compressed and one uncompressed. 412 4.4. HTTP Range Retrieval 414 The HTTP Range header allows a client to request only a subset of a 415 resource. This is useful for quick recovery of partially failed 416 transfers. Using this option for incremental updates of ALTO Maps 417 difficult. The Byte range is specified by the client, however the 418 diff is calculated by the server. Thus an additional mechanism would 419 be needed tell the client which byte sequences to request to. 420 Additionally the Byte offsets might change between Map versions, thus 421 this option appears to be error-prone. 423 4.5. JSON patch 425 JSON Patch [I-D.pbryan-json-patch] defines a JSON document structure 426 that allows partial modifications to a JSON document and defines the 427 associated media type "application/json-patch". Therefore JSON Patch 428 is a suitable option for incremental updates of the Network and Cost 429 Maps. JSON patch supports add, remove and replace operations that 430 can be used in combination with JSON Pointers 431 [I-D.pbryan-zyp-json-pointer] to modify values and arrays of the JSON 432 document members. 434 Typically JSON Patch is used in combination with the HTTP PATCH 435 method [RFC5789] to partially modify existing resources on a server. 436 As an ALTO client is not modifying a resource, but wants to be 437 updated if the resource has changed it needs to signal to the server 438 that it is able to receive and understand JSON Patch updates. This 439 can be done by including the media type "application/json-patch" in 440 the Accept header field of the HTTP request. 442 Although JSON Patch permits pointers to index individual array 443 elements, that's potentially ambiguous. "Add" and "delete" change 444 the array indexes; do subsequent updates to that array refer to the 445 original indexes or the revised indexes? And even if that's well- 446 specified, it's a potential source of error. Furthermore, some 447 clients may store the CIDRs in a PID as a set, rather than an array, 448 so they don't keep the original index numbers. 450 To avoid these problems, we recommend that when updating the CIDRs 451 for a PID, the server replaces the full array value for that PID, 452 rather than updating individual CIDRs by index. 454 This may also simplify the server, because it just has to flag the 455 PID as having changed; it doesn't have to remember the previous 456 sequence of CIDRs. 458 The following figure illustrates one example where the server decides 459 to send a partial update to the client using JSON Patch. The server 460 indicates this in the response Content-Type header. In the following 461 example the Network Map from the example in Figure 3 above has 462 changed. The map-vtag element has been incremented by 1, which 463 results in a replace operation for the respective element containing 464 the new value. Also two new subnets are added to the Network Map in 465 PID1 and PID2 by two replace operations on the ipv4 arrays. 467 HTTP/1.1 200 OK 468 Content-Length: [TODO] 469 Content-Type: application/json-patch 470 Date: Sun, 25 Dec 2011 09:33:31 GMT 472 { "replace": "/data/map-vtag", "value": "1266506140" }, 473 { "replace": "/data/map/PID1/ipv4", "value": 474 ["192.0.2.0/24", "198.51.200.0/25", "198.51.100.0/25"] }, 475 { "replace": "/data/map/PID2/ipv4", "value": 476 ["198.51.100.128/25", "198.51.200.128/25"] } 478 Figure 7: Partial update with JSON Patch 480 One benefit of using JSON Patch for partial updates would be if 481 standard JSON parsers would implement JSON Patch already. This would 482 allow ALTO protocol implementers to reuse existing functionality. 483 However to the knowledge of the authors there are only few 484 implementations supporting JSON Patch to date, and a widespread 485 adoption is still outstanding and will presumably take some time. 487 4.6. ALTO Incremental Update service 489 Another option is to offer a dedicated ALTO service for partial 490 updates. A client that determines that its current map is out-of- 491 date, for example by comparing cost-map-vtag values (see Section 3.2) 492 can then query this service to retrieve the partial update. This 493 section defines this service in the next section and an new 494 capability for the IRD in the following section 496 4.6.1. Incremental Update messages 498 This service can be implemented in new POST-mode requests, Get 499 Network Map Updates and Get Cost Map Updates. These partial update 500 messages use a new MIME type [RFC2046]: 502 "application/alto-update-param+json" 504 The client includes its current map version (i.e. the map-vtag or the 505 cost-map-vtag) to the post data of the request in a new reference tag 506 field. Based on this reference-tag a partial update response is 507 created. Or if the current (cost-)map-vtag is the same as the 508 reference-tag -- that is, if there are no changes -- the "map" entry 509 in the response has no entries. Or if it's sufficiently old that the 510 server no longer knows what changed since that version or if the tag 511 is invalid, the server returns a complete cost map. Thus the 512 response contains an optional field to allow clients to distinguish: 514 {"full-map": true} 516 Thus the response MUST have costs that changed since the specified 517 version, but MAY have other costs as well. 519 The partial update response essentially is a Filtered Network Map or 520 Filtered Cost Map message, where for a Network Map for each PID in 521 the message, previous CIDRs are replaced with new CIDRs in case they 522 have changed. To remove a PID from the Map the value "delete" or an 523 empty array is used. PIDs that are not in the message remain 524 unchanged. Similarly for Cost Maps, costs specified in the message 525 replace previous costs for the respective source/destination PIDs. 526 Again, to remove a cost the value "delete" (or "-1", or "NaN",...) is 527 used whereas costs that are not in the message stay the same. 529 The following figures give one example of a request/response 530 transaction of the proposed Partial Update ALTO extension service. 532 POST /partialupdate/costmap/rcost/incrementalupdate/costmap 533 Content-Type: application/alto-update-param+json 534 Accept: application/alto-costmap+json 535 { "reference-tag": "1266506140" } 537 Figure 8: Incremental update request 539 HTTP/1.1 200 OK 540 Content-Type: application/alto-costmap+json 541 { "meta": {}, 542 "data": { 543 "cost-mode": "numerical", 544 "cost-type": "routingcost", 545 "map-vtag": "314159", 546 "cost-vtag": "1266506141", 547 "full-map": false, 548 "map": { "PID1": { "PID2": 1, "PID3": 2 } } 549 } 550 } 552 Figure 9: Incremental update response 554 4.6.2. Incremental Update Capability 556 An ALTO server needs to advertise its ability of providing 557 incremental updates to a client. One option of doing this is by 558 including an ALTO information resource capability indicating the 559 partial update option. This can be done per ALTO service, which 560 allows a fine grained control over which URIs handle partial 561 requests. 563 The following Information Resource Directory illustrates one example 564 where network and costmaps are available with and without partial 565 update option respectively. This is expressed by the JSONBool 566 capability element "partial-update". 568 GET /directory HTTP/1.1 569 Host: alto.example.com 570 Accept: application/alto-directory+json,application/alto-error+json 572 HTTP/1.1 200 OK 573 Content-Length: [TODO] 574 Content-Type: application/alto-directory+json 576 { 577 "resources" : [ 578 { 579 "uri" : "http://alto.example.com/serverinfo", 580 "media-types" : [ "application/alto-serverinfo+json" ] 581 }, { 582 "uri" : "http://alto.example.com/networkmap", 583 "media-types" : [ "application/alto-networkmap+json" ] 584 }, { 585 "uri" : "http://alto.example.com/costmap/rcost", 586 "media-types" : [ "application/alto-costmap+json" ], 587 "capabilities" : { 588 "cost-modes" : [ "numerical" ], 589 "cost-types" : [ "routingcost" ] 590 } 591 }, { 592 "uri" : "http://alto.example.com/partialupdate/networkmap", 593 "media-types" : [ "application/alto-networkmap+json" ] 594 "accepts" : [ "application/alto-update-param+json" ], 595 "capabilities" : { 596 "incremental-update" : true, 597 } 598 }, { 599 "uri" : "http://alto.example.com/partialupdate/costmap/rcost", 600 "media-types" : [ "application/alto-costmap+json" ], 601 "accepts" : [ "application/alto-update-param+json" ], 602 "capabilities" : { 603 "incremental-update" : true, 604 "cost-modes" : [ "numerical" ], 605 "cost-types" : [ "routingcost" ] 606 } 607 } 608 } 609 ] 610 } 612 Figure 10: IRD With Partial Update Capability 614 5. Numerical Evaluation 616 In this section we provide a numerical evaluation of the efficiency 617 of incremental updates. We focus on the two most promising 618 approaches JSON patch (Section 4.5) and the ALTO incremental Updates 619 service (Section 4.6). For our calculations we use cost map formats 620 to conclude on the incremental update efficiency. 622 5.1. Full Cost Map Size estimation 624 In the following we estimate the size of full cost maps with respects 625 to the number of PIDs that are contained. Neglecting some fixed 626 overhead we find: 628 np^2 * (4 + pl + cl) + np * (6 + pl) 630 where 632 np: number of PIDS 634 pl: Average length of PID names 636 cl: Average number of digits in costs 638 If we assume PID names are 8 characters (pl = 8) and costs are 3 639 digits (cl = 3), we get: 641 np cost-map size 642 10 1,640 643 25 9,725 644 50 38,200 645 100 151,400 646 250 941,000 647 500 3,757,000 648 1000 15,014,000 649 2500 93,785,000 650 5000 375,070,000 652 Figure 11: Full Cost Map Sizes 654 As a conclusion we do think that for less than 100 PIDs incremental 655 updates are not needed. Instead the Full Cost Map can be sent. 656 However for Maps that require a greater accuracy and thus a higher 657 number of PIDs incremental updates are required. 659 5.2. JSON Patch vs. ALTO extension 661 In this section we estimate the performance of JSON Patch and the 662 proposed ALTO extension. We limit our estimation on the worst-case 663 scenario, which are replace operations. 665 For each changed cost a JSON Patch replace operation is represented 666 by the following encoding: 668 { "replace": "meta.data.map.SRC-PID.DEST-PID", "value": 123 }, 670 Whereas an Incremental Update ALTO Cost Map message as defined in 671 this document takes an encoding of (Note: This is actually the 672 encoding of the existing ALTO Cost Map response - it's just a matter 673 of interpretation): 675 "SRC-PID": {"DEST-PID": 123}, 677 Note that this is the worst case, it takes less space if several 678 updates share the same source PID: 680 "SRC-PID": {"DEST-1": 123, "DEST-2": 321, ....}, 682 The number of bytes per changed cost are: 684 JSON patch: 685 33 + 2*NameLength + CostLength 687 ALTO Cost Map Message (worst case): 688 8 + 2*NameLength + CostLength 690 We estimate the number of bytes for: 692 JSON patch: 693 cf * np * np * (33 + pl + cl) 695 ALTO Cost Map Message (worst case): 696 cf * np * np * (8 + pl + cl) 698 where 700 cf: Fraction of src-dest costs that changed (0 to 1) 702 np: Number of PIDS 704 pl: Average length of PID names 705 cl: Average number of digits in costs 707 If we assume PID names are 8 characters (pl = 8) and costs are 3 708 digits (cl = 3), and 5% of the costs change (cf = .05), we get: 710 JSON ALTO Cost 711 np patch Map message 712 10 220 95 713 50 5,500 2,375 714 100 22,000 9,500 715 250 137,500 59,375 716 500 550,000 237,500 717 1000 2,200,000 950,000 718 2500 13,750,000 5,937,500 719 5000 55,000,000 23,750,000 721 Figure 12: Results JSON Patch vs. ALTO extension 723 Clearly, the ALTO extension as proposed in this document has a higher 724 efficiency in terms of encoded bytes needed compared to JSON Patch. 726 6. IANA Considerations 728 The Incremental Update service as proposed introduces a new MIME type 729 "application/alto-update-param+json" which needs to be registered. 731 7. Security Considerations 733 To be done in later versions of this document. 735 8. Conclusion 737 This document describes different options that can be applied to 738 support incremental updates of ALTO Network and Cost maps. In 739 particular it comprises option for client and server to synchronize 740 themselves about their current map state, and further includes 741 options on how to encode partial updates. Finally it proposes an new 742 incremental update service and evaluates different options 743 numerically. 745 9. References 747 [I-D.ietf-alto-protocol] 748 Alimi, R., Penno, R., and Y. Yang, "ALTO Protocol", 749 draft-ietf-alto-protocol-10 (work in progress), 750 October 2011. 752 [I-D.jenkins-alto-cdn-use-cases] 753 Niven-Jenkins, B., Watson, G., Bitar, N., Medved, J., and 754 S. Previdi, "Use Cases for ALTO within CDNs", 755 draft-jenkins-alto-cdn-use-cases-01 (work in progress), 756 June 2011. 758 [I-D.pbryan-json-patch] 759 Bryan, P., "JSON Patch", draft-pbryan-json-patch-02 (work 760 in progress), October 2011. 762 [I-D.pbryan-zyp-json-pointer] 763 Bryan, P. and K. Zyp, "JSON Pointer", 764 draft-pbryan-zyp-json-pointer-02 (work in progress), 765 October 2011. 767 [RFC2046] Freed, N. and N. Borenstein, "Multipurpose Internet Mail 768 Extensions (MIME) Part Two: Media Types", RFC 2046, 769 November 1996. 771 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 772 Requirement Levels", BCP 14, RFC 2119, March 1997. 774 [RFC2616] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., 775 Masinter, L., Leach, P., and T. Berners-Lee, "Hypertext 776 Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999. 778 [RFC5693] Seedorf, J. and E. Burger, "Application-Layer Traffic 779 Optimization (ALTO) Problem Statement", RFC 5693, 780 October 2009. 782 [RFC5789] Dusseault, L. and J. Snell, "PATCH Method for HTTP", 783 RFC 5789, March 2010. 785 Appendix A. Acknowledgments 787 The authors would like to thank Vijay Gurbani for his valuable input 788 and excellent feedback to this document. 790 Nico Schwan is partially supported by the ENVISION project 791 (http://www.envision-project.org), a research project supported by 792 the European Commission under its 7th Framework Program (contract no. 793 248565). The views and conclusions contained herein are those of the 794 authors and should not be interpreted as necessarily representing the 795 official policies or endorsements, either expressed or implied, of 796 the ENVISION project or the European Commission. 798 Authors' Addresses 800 Nico Schwan 801 Alcatel-Lucent Bell Labs 802 Lorenzstrasse 10 803 Stuttgart 70435 804 Germany 806 Email: nico.schwan@alcatel-lucent.com 807 URI: www.alcatel-lucent.com/bell-labs 809 Bill Roome 810 Alcatel-Lucent Bell Labs 812 Email: w.roome@alcatel-lucent.com 813 URI: www.alcatel-lucent.com/bell-labs