idnits 2.17.1 draft-ietf-tcpm-fastopen-07.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 : ---------------------------------------------------------------------------- ** There are 7 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** The abstract seems to contain references ([RFC2119]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 14, 2014) is 3724 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'RFC2119' is mentioned on line 67, but not defined == Missing Reference: 'RFC 1323' is mentioned on line 655, but not defined ** Obsolete undefined reference: RFC 1323 (Obsoleted by RFC 7323) == Missing Reference: 'BELSHE11' is mentioned on line 761, but not defined == Unused Reference: 'RFC6928' is defined on line 949, but no explicit reference was found in the text == Unused Reference: 'QWGMSS11' is defined on line 991, but no explicit reference was found in the text == Unused Reference: 'BELSHE12' is defined on line 1018, but no explicit reference was found in the text ** Obsolete normative reference: RFC 793 (Obsoleted by RFC 9293) -- Obsolete informational reference (is this intentional?): RFC 1644 (Obsoleted by RFC 6247) -- Obsolete informational reference (is this intentional?): RFC 6013 (Obsoleted by RFC 7805) == Outdated reference: A later version (-10) exists of draft-ietf-tcpm-fastopen-01 Summary: 4 errors (**), 0 flaws (~~), 8 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft Y. Cheng 3 draft-ietf-tcpm-fastopen-07.txt J. Chu 4 Intended status: Experimental S. Radhakrishnan 5 Expiration date: August, 2014 A. Jain 6 Google, Inc. 7 February 14, 2014 9 TCP Fast Open 11 Status of this Memo 13 Distribution of this memo is unlimited. 15 This Internet-Draft is submitted in full conformance with the 16 provisions of BCP 78 and BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that other 20 groups may also distribute working documents as Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/1id-abstracts.html 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html 33 Copyright Notice 35 Copyright (c) 2014 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Abstract 49 This document describes an experimental TCP mechanism TCP Fast Open 50 (TFO). TFO allows data to be carried in the SYN and SYN-ACK packets 51 and consumed by the receiving end during the initial connection 52 handshake, thus saving up to one full round trip time (RTT) compared 53 to the standard TCP, which requires a three-way handshake (3WHS) to 54 complete before data can be exchanged. However TFO deviates from the 55 standard TCP semantics the data in the SYN could be replayed to an 56 application in some rare circumstances. Applications should not use 57 TFO unless they can tolerate this issue detailed in the Applicability 58 section. 60 Terminology 62 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 63 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 64 document are to be interpreted as described in RFC 2119 [RFC2119]. 65 TFO refers to TCP Fast Open. Client refers to the TCP's active open 66 side and server refers to the TCP's passive open side. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 71 2. Data In SYN . . . . . . . . . . . . . . . . . . . . . . . . . . 4 72 2.1 Relaxing TCP Semantics on Duplicated SYNs . . . . . . . . . 4 73 2.2. SYNs with Spoofed IP Addresses . . . . . . . . . . . . . . 4 74 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 5 75 4. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7 76 4.1. Fast Open Cookie . . . . . . . . . . . . . . . . . . . . . 7 77 4.1.1. TCP Options . . . . . . . . . . . . . . . . . . . . . . 7 78 4.1.2. Server Cookie Handling . . . . . . . . . . . . . . . . 8 79 4.1.3. Client Cookie Handling . . . . . . . . . . . . . . . . 9 80 4.1.3.1 Client Caching Negative Responses . . . . . . . . . 9 81 4.2. Fast Open Protocol . . . . . . . . . . . . . . . . . . . . 10 82 4.2.1. Fast Open Cookie Request . . . . . . . . . . . . . . . 10 83 4.2.2. TCP Fast Open . . . . . . . . . . . . . . . . . . . . . 11 84 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 13 85 5.1. Resource Exhaustion Attack by SYN Flood with Valid 86 Cookies . . . . . . . . . . . . . . . . . . . . . . . . . . 13 87 5.1.1 Attacks from behind Shared Public IPs (NATs) . . . . . . 14 88 5.2. Amplified Reflection Attack to Random Host . . . . . . . . 15 89 6. TFO's Applicability . . . . . . . . . . . . . . . . . . . . . . 16 90 6.1 Duplicate Data in SYNs . . . . . . . . . . . . . . . . . . . 16 91 6.2 Potential Performance Improvement . . . . . . . . . . . . . 16 92 6.3. Example: Web Clients and Servers . . . . . . . . . . . . . 17 93 6.3.1. HTTP Request Replay . . . . . . . . . . . . . . . . . . 17 94 6.3.2. Speculative Connections by the Applications . . . . . . 17 95 6.3.3. HTTP over TLS (HTTPS) . . . . . . . . . . . . . . . . . 17 96 6.3.4. Comparison with HTTP Persistent Connections . . . . . . 17 98 7. Open Areas for Experimentation . . . . . . . . . . . . . . . . 18 99 7.1. Performance impact due to middle-boxes and NAT . . . . . . 18 100 7.2. Cookie-less Fast Open . . . . . . . . . . . . . . . . . . . 19 101 7.3 Impact on congestion control . . . . . . . . . . . . . . . . 19 102 8. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 20 103 8.1. T/TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 104 8.2. Common Defenses Against SYN Flood Attacks . . . . . . . . . 20 105 8.3. TCP Cookie Transaction (TCPCT) . . . . . . . . . . . . . . 20 106 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 20 107 10. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 21 108 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 109 11.1. Normative References . . . . . . . . . . . . . . . . . . . 21 110 11.2. Informative References . . . . . . . . . . . . . . . . . . 21 111 Appendix A. Example Socket API Changes to support TFO . . . . . . 23 112 A.1 Active Open . . . . . . . . . . . . . . . . . . . . . . . . 23 113 A.2 Passive Open . . . . . . . . . . . . . . . . . . . . . . . . 23 114 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 116 1. Introduction 118 TCP Fast Open (TFO) is an experimental update to TCP that enables 119 data to be exchanged safely during TCP's connection handshake. This 120 document describes a design that enables applications to save a round 121 trip while avoiding severe security ramifications. At the core of TFO 122 is a security cookie used by the server side to authenticate a client 123 initiating a TFO connection. This document covers the details of 124 exchanging data during TCP's initial handshake, the protocol for TFO 125 cookies, potential new security vulnerabilities and their mitigation, 126 and the new socket API. 128 TFO is motivated by the performance needs of today's Web 129 applications. Current TCP only permits data exchange after the 3-way 130 handshake (3WHS)[RFC793], which adds one RTT to network latency. For 131 short Web transfers this additional RTT is a significant portion of 132 overall network latency, even when HTTP persistent connection is 133 widely used. For example, the Chrome browser keeps TCP connections 134 idle for up to 5 minutes but 35% of Chrome HTTP requests are made on 135 new TCP connections [RCCJR11]. For such Web and Web-like applications 136 placing data in the SYN can yield significant latency improvements. 137 Next we describe how we resolve the challenges that arise upon doing 138 so. 140 2. Data In SYN 142 Standard TCP already allows data to be carried in SYN packets 143 ([RFC793], section 3.4) but forbids the receiver from delivering it 144 to the application until 3WHS is completed. This is because TCP's 145 initial handshake serves to capture old or duplicate SYNs. 147 To enable applications exchange data in TCP handshake, TFO removes 148 the constraint and allows data in SYN packets to be delivered to 149 application. This change of TCP semantic raises two issues discussed 150 in the following subsections, making TFO unsuitable for certain 151 applications. 153 Therefore TCP implementations MUST NOT use TFO by default, but only 154 use TFO if requested explicitly by the application on a per service 155 port basis. Applications need to evaluate TFO applicability described 156 in Section 6 before using TFO. 158 2.1 Relaxing TCP Semantics on Duplicated SYNs 160 TFO allows data to be delivered to application before the 3WHS is 161 completed, thus opening itself to a data integrity issue in either of 162 the two cases below: 164 a) the receiver host receives data in a duplicate SYN after it has 165 forgotten it received the original SYN (e.g. due to a reboot); 167 b) the duplicate is received after the connection created by the 168 original SYN has been closed and the close was initiated by the 169 sender (so the receiver will not be protected by the 2MSL TIMEWAIT 170 state). 172 The now obsoleted T/TCP [RFC1644] attempted to address these issues. 173 It was not successful and not deployed due to various vulnerabilities 174 as described in the Related Work section. Rather than trying to 175 capture all dubious SYN packets to make TFO 100% compatible with TCP 176 semantics, we made a design decision early on to accept old SYN 177 packets with data, i.e., to restrict TFO use to a class of 178 applications (Section 6) that are tolerant of duplicate SYN packets 179 with data. We believe this is the right design trade-off balancing 180 complexity with usefulness. 182 2.2. SYNs with Spoofed IP Addresses 184 Standard TCP suffers from the SYN flood attack [RFC4987] because SYN 185 packets with spoofed source IP addresses can easily fill up a 186 listener's small queue, causing a service port to be blocked 187 completely until timeouts. 189 TFO goes one step further to allow server-side TCP to send up data to 190 the application layer before 3WHS is completed. This opens up serious 191 new vulnerabilities. Applications serving ports that have TFO enabled 192 may waste lots of CPU and memory resources processing the requests 193 and producing the responses. If the response is much larger than the 194 request, the attacker can further mount an amplified reflection 195 attack against victims of choice beyond the TFO server itself. 197 Numerous mitigation techniques against regular SYN flood attacks 198 exist and have been well documented [RFC4987]. Unfortunately none are 199 applicable to TFO. We propose a server-supplied cookie to mitigate 200 these new vulnerabilities in Section 3 and evaluate the effectiveness 201 of the defense in Section 7. 203 3. Protocol Overview 205 The key component of TFO is the Fast Open Cookie (cookie), a message 206 authentication code (MAC) tag generated by the server. The client 207 requests a cookie in one regular TCP connection, then uses it for 208 future TCP connections to exchange data during 3WHS: 210 Requesting a Fast Open Cookie: 212 1. The client sends a SYN with a Fast Open Cookie Request option. 214 2. The server generates a cookie and sends it through the Fast Open 215 Cookie option of a SYN-ACK packet. 217 3. The client caches the cookie for future TCP Fast Open connections 218 (see below). 220 Performing TCP Fast Open: 222 1. The client sends a SYN with Fast Open Cookie option and data. 224 2. The server validates the cookie: 225 a. If the cookie is valid, the server sends a SYN-ACK 226 acknowledging both the SYN and the data. The server then 227 delivers the data to the application. 229 b. Otherwise, the server drops the data and sends a SYN-ACK 230 acknowledging only the SYN sequence number. 232 3. If the server accepts the data in the SYN packet, it may send the 233 response data before the handshake finishes. The max amount is 234 governed by the TCP's congestion control [RFC5681]. 236 4. The client sends an ACK acknowledging the SYN and the server data. 238 If the client's data is not acknowledged, the client retransmits 239 the data in the ACK packet. 241 5. The rest of the connection proceeds like a normal TCP connection. 242 The client can repeat many Fast Open operations once it acquires a 243 cookie (until the cookie is expired by the server). Thus TFO is 244 useful for applications that have temporal locality on client and 245 server connections. 247 Requesting Fast Open Cookie in connection 1: 249 TCP A (Client) TCP B(Server) 250 ______________ _____________ 251 CLOSED LISTEN 253 #1 SYN-SENT ----- ----------> SYN-RCVD 255 #2 ESTABLISHED <---- ---------- SYN-RCVD 256 (caches cookie C) 258 Performing TCP Fast Open in connection 2: 260 TCP A (Client) TCP B(Server) 261 ______________ _____________ 262 CLOSED LISTEN 264 #1 SYN-SENT ----- ----> SYN-RCVD 266 #2 ESTABLISHED <---- ---- SYN-RCVD 268 #3 ESTABLISHED <---- ---- SYN-RCVD 270 #4 ESTABLISHED ----- --------------------> ESTABLISHED 272 #5 ESTABLISHED --- ----------> ESTABLISHED 274 4. Protocol Details 276 4.1. Fast Open Cookie 278 The Fast Open Cookie is designed to mitigate new security 279 vulnerabilities in order to enable data exchange during handshake. 280 The cookie is a message authentication code tag generated by the 281 server and is opaque to the client; the client simply caches the 282 cookie and passes it back on subsequent SYN packets to open new 283 connections. The server can expire the cookie at any time to enhance 284 security. 286 4.1.1. TCP Options 288 Fast Open Cookie Option 290 The server uses this option to grant a cookie to the client in the 291 SYN-ACK packet; the client uses it to pass the cookie back to the 292 server in subsequent SYN packets. 294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 295 | Kind | Length | 296 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 297 | | 298 ~ Cookie ~ 299 | | 300 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 302 Kind 1 byte: constant TBD (assigned by IANA) 303 Length 1 byte: range 6 to 18 (bytes); limited by 304 remaining space in the options field. 305 The number MUST be even. 306 Cookie 4 to 16 bytes (Length - 2) 307 Options with invalid Length values or without SYN flag set MUST be 308 ignored. The minimum Cookie size is 4 bytes. Although the diagram 309 shows a cookie aligned on 32-bit boundaries, alignment is not 310 required. 312 Fast Open Cookie Request Option 314 The client uses this option in the SYN packet to request a cookie 315 from a TFO-enabled server 316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 317 | Kind | Length | 318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 320 Kind 1 byte: same as the Fast Open Cookie option 321 Length 1 byte: constant 2. This distinguishes the option 322 from the Fast Open cookie option. 323 Options with invalid Length values, without SYN flag set, or with ACK 324 flag set MUST be ignored. 326 4.1.2. Server Cookie Handling 328 The server is in charge of cookie generation and authentication. The 329 cookie SHOULD be a message authentication code tag with the following 330 properties: 331 1. The cookie authenticates the client's (source) IP address of the 332 SYN packet. The IP address may be an IPv4 or IPv6 address. 334 2. The cookie can only be generated by the server and can not be 335 fabricated by any other parties including the client. 337 3. The generation and verification are fast relative to the rest of 338 SYN and SYN-ACK processing. 340 4. A server may encode other information in the cookie, and accept 341 more than one valid cookie per client at any given time. But this 342 is server implementation dependent and transparent to the 343 client. 345 5. The cookie expires after a certain amount of time. The reason for 346 cookie expiration is detailed in the "Security Consideration" 347 section. This can be done by either periodically changing the 348 server key used to generate cookies or including a timestamp when 349 generating the cookie. 351 To gradually invalidate cookies over time, the server can 352 implement key rotation to generate and verify cookies using 353 multiple keys. This approach is useful for large-scale servers to 354 retain Fast Open rolling key updates. We do not specify a 355 particular mechanism because the implementation is server 356 specific. 358 The server supports the cookie generation and verification 359 operations: 361 - GetCookie(IP_Address): returns a (new) cookie 363 - IsCookieValid(IP_Address, Cookie): checks if the cookie is valid, 364 i.e., it has not expired and it authenticates the client IP address. 366 Example Implementation: a simple implementation is to use AES_128 to 367 encrypt the IPv4 (with padding) or IPv6 address and truncate to 64 368 bits. The server can periodically update the key to expire the 369 cookies. AES encryption on recent processors is fast and takes only a 370 few hundred nanoseconds [RCCJR11]. 372 If only one valid cookie is allowed per-IP and the server can 373 regenerate the cookie independently, the best validation process is 374 to simply regenerate a valid cookie and compare it against the 375 incoming cookie. In that case if the incoming cookie fails the check, 376 a valid cookie is readily available to be sent to the client. 378 4.1.3. Client Cookie Handling 380 The client MUST cache cookies from servers for later Fast Open 381 connections. For a multi-homed client, the cookies are both client 382 and server IP dependent. Beside the cookie we RECOMMEND that the 383 client caches the MSS to the server to enhance performance. 385 The MSS advertised by the server is stored in the cache to determine 386 the maximum amount of data that can be supported in the SYN packet. 387 This information is needed because data is sent before the server 388 announces its MSS in the SYN-ACK packet. Without this information, 389 the data size in the SYN packet is limited to the default MSS of 536 390 bytes [RFC1122]. In particular it's known IPv4 receiver advertised 391 MSS less than 536 bytes would result in transmission of an unexpected 392 large segment. If the cache MSS is larger than the typical 1460 393 bytes, the extra large data in SYN segment may have issues that 394 offsets the performance benefit of Fast Open. For examples, the 395 super-size SYN may trigger IP fragmentation and may confuse firewall 396 or middle-boxes, causing SYN retransmission and other side-effects. 397 Therefore the client MAY limit the cached MSS to 1460 bytes. 399 4.1.3.1 Client Caching Negative Responses 401 The client MUST cache negative responses from the server in order to 402 avoid potential connection failures. Negative responses include 403 server not acknowledging the data in SYN, ICMP error messages, and 404 most importantly no response (SYN/ACK) from the server at all, i.e., 405 connection timeout. The last case is likely due to incompatible 406 middle-boxes or firewall blocking the connection completely after it 407 sees data in SYN. If the client does not react to these negative 408 responses and continue to retry Fast Open, the client may never be 409 able to connect to the specific server. 411 For any negative responses, the client SHOULD disable Fast Open on 412 the specific path and port, at least temporarily. Since TFO is 413 enabled on a per-service port basis but cookies are independent of 414 service ports, clients' cache should include remote port numbers too. 416 4.2. Fast Open Protocol 418 One predominant requirement of TFO is to be fully compatible with 419 existing TCP implementations, both on the client and the server 420 sides. 422 The server keeps two variables per listening port: 424 FastOpenEnabled: default is off. It MUST be turned on explicitly by 425 the application. When this flag is off, the server does not perform 426 any TFO related operations and MUST ignore all cookie options. 428 PendingFastOpenRequests: tracks number of TFO connections in SYN-RCVD 429 state. If this variable goes over a preset system limit, the server 430 MUST disable TFO for all new connection requests until 431 PendingFastOpenRequests drops below the system limit. This variable 432 is used for defending some vulnerabilities discussed in the "Security 433 Considerations" section. 435 The server keeps a FastOpened flag per TCB to mark if a connection 436 has successfully performed a TFO. 438 4.2.1. Fast Open Cookie Request 440 Any client attempting TFO MUST first request a cookie from the server 441 with the following steps: 443 1. The client sends a SYN packet with a Fast Open Cookie Request 444 option. 446 2. The server SHOULD respond with a SYN-ACK based on the procedures 447 in the "Server Cookie Handling" section. This SYN-ACK SHOULD 448 contain a Fast Open Cookie option if the server currently supports 449 TFO for this listener port. 451 3. If the SYN-ACK contains a Fast Open Cookie option, the client 452 replaces the cookie and other information as described in the 453 "Client Cookie Handling" section. Otherwise, if the SYN-ACK is 454 first seen, i.e.,not a (spurious) retransmission, the client MAY 455 remove the server information from the cookie cache. If the SYN- 456 ACK is a spurious retransmission without valid Fast Open Cookie 457 Option, the client does nothing to the cookie cache for the 458 reasons below. 460 The network or servers may drop the SYN or SYN-ACK packets with the 461 new cookie options, which will cause SYN or SYN-ACK timeouts. We 462 RECOMMEND both the client and the server to retransmit SYN and SYN- 463 ACK without the cookie options on timeouts. This ensures the 464 connections of cookie requests will go through and lowers the latency 465 penalty (of dropped SYN/SYN-ACK packets). The obvious downside for 466 maximum compatibility is that any regular SYN drop will fail the 467 cookie (although one can argue the delay in the data transmission 468 till after 3WHS is justified if the SYN drop is due to network 469 congestion). Next section describes a heuristic to detect such drops 470 when the client receives the SYN-ACK. 472 We also RECOMMEND the client to record the set of servers that failed 473 to respond to cookie requests and only attempt another cookie request 474 after certain period. 476 An alternate proposal is to request cookie in FIN instead since FIN- 477 drop by incompatible middle-box does not affect latency. However such 478 paths are likely to drop SYN packet with data later, and many 479 applications close the connections with RST instead, so the actual 480 benefit of this approach is not clear. 482 4.2.2. TCP Fast Open 484 Once the client obtains the cookie from the target server, it can 485 perform subsequent TFO connections until the cookie is expired by the 486 server. 488 Client: Sending SYN 490 To open a TFO connection, the client MUST have obtained a cookie from 491 the server: 493 1. Send a SYN packet. 495 a. If the SYN packet does not have enough option space for the 496 Fast Open Cookie option, abort TFO and fall back to regular 3WHS. 498 b. Otherwise, include the Fast Open Cookie option with the cookie 499 of the server. Include any data up to the cached server MSS or 500 default 536 bytes. 502 2. Advance to SYN-SENT state and update SND.NXT to include the data 503 accordingly. 505 3. If RTT is available from the cache, seed SYN timer according to 506 [RFC6298]. 508 To deal with network or servers dropping SYN packets with payload or 509 unknown options, when the SYN timer fires, the client SHOULD 510 retransmit a SYN packet without data and Fast Open Cookie options. 512 Server: Receiving SYN and responding with SYN-ACK 514 Upon receiving the SYN packet with Fast Open Cookie option: 516 1. Initialize and reset a local FastOpened flag. If FastOpenEnabled 517 is false, go to step 5. 519 2. If PendingFastOpenRequests is over the system limit, go to step 5. 521 3. If IsCookieValid() in section 4.1.2 returns false, go to step 5. 523 4. Buffer the data and notify the application. Set FastOpened flag 524 and increment PendingFastOpenRequests. 526 5. Send the SYN-ACK packet. The packet MAY include a Fast Open 527 Option. If FastOpened flag is set, the packet acknowledges the SYN 528 and data sequence. Otherwise it acknowledges only the SYN 529 sequence. The server MAY include data in the SYN-ACK packet if the 530 response data is readily available. Some application may favor 531 delaying the SYN-ACK, allowing the application to process the 532 request in order to produce a response, but this is left up to the 533 implementation. 535 6. Advance to the SYN-RCVD state. If the FastOpened flag is set, the 536 server MUST follow the congestion control [RFC5681] to set the 537 initial congestion window [RFC3390], to send more data packets. 539 If the SYN-ACK timer fires, the server SHOULD retransmit a SYN-ACK 540 segment with neither data nor Fast Open Cookie options for 541 compatibility reasons. 543 A special case is simultaneous open where the SYN receiver is a 544 client in SYN-SENT state. The protocol remains the same because 545 [RFC793] already supports both data in SYN and simultaneous open. But 546 the client's socket may have data available to read before it's 547 connected. This document does not cover the corresponding API change. 549 Client: Receiving SYN-ACK 551 The client SHOULD perform the following steps upon receiving the SYN- 552 ACK: 554 1. Update the cookie cache if the SYN-ACK has a Fast Open Cookie 555 Option or MSS option or both. 557 2. Send an ACK packet. Set acknowledgment number to RCV.NXT and 558 include the data after SND.UNA if data is available. 560 3. Advance to the ESTABLISHED state. 562 Note there is no latency penalty if the server does not acknowledge 563 the data in the original SYN packet. The client SHOULD retransmit any 564 unacknowledged data in the first ACK packet in step 2. The data 565 exchange will start after the handshake like a regular TCP 566 connection. 568 If the client has timed out and retransmitted only regular SYN 569 packets, it can heuristically detect paths that intentionally drop 570 SYN with Fast Open option or data. If the SYN-ACK acknowledges only 571 the initial sequence and does not carry a Fast Open cookie option, 572 presumably it is triggered by a retransmitted (regular) SYN and the 573 original SYN or the corresponding SYN-ACK was lost. 575 Server: Receiving ACK 577 Upon receiving an ACK acknowledging the SYN sequence, the server 578 decrements PendingFastOpenRequests and advances to the ESTABLISHED 579 state. No special handling is required further. 581 5. Security Considerations 583 The Fast Open cookie stops an attacker from trivially flooding 584 spoofed SYN packets with data to burn server resources or to mount an 585 amplified reflection attack on random hosts. The server can defend 586 against spoofed SYN floods with invalid cookies using existing 587 techniques [RFC4987]. We note that although generating bogus cookies 588 is cost-free, the cost of validating the cookies, inherent to any 589 authentication scheme, may be substantial compared to processing a 590 regular SYN packet. 592 5.1. Resource Exhaustion Attack by SYN Flood with Valid Cookies 594 An attacker may still obtain cookies from some compromised hosts, 595 then flood spoofed SYN with data and "valid" cookies (from these 596 hosts or other vantage points). With DHCP, it's possible to obtain 597 cookies of past IP addresses without compromising any host. Below we 598 identify new vulnerabilities of TFO and describe the countermeasures. 600 Like regular TCP handshakes, TFO is vulnerable to such an attack. But 601 the potential damage can be much more severe. Besides causing 602 temporary disruption to service ports under attack, it may exhaust 603 server CPU and memory resources. Such an attack will show up on 604 application server logs as a application level DoS from Bot-nets, 605 triggering other defenses and alerts. 607 To protect the server it is important to limit the maximum number of 608 total pending TFO connection requests, i.e., PendingFastOpenRequests 609 (Section 4.2). When the limit is exceeded, the server temporarily 610 disables TFO entirely as described in "Server Cookie Handling". Then 611 subsequent TFO requests will be downgraded to regular connection 612 requests, i.e., with the data dropped and only SYN acknowledged. This 613 allows regular SYN flood defense techniques [RFC4987] like SYN- 614 cookies to kick in and prevent further service disruption. 616 The main impact of SYN floods against the standard TCP stack is not 617 directly from the floods themselves costing TCP processing overhead 618 or host memory, but rather from the spoofed SYN packets filling up 619 the often small listener's queue. 621 On the other hand, TFO SYN floods can cause damage directly if 622 admitted without limit into the stack. The RST packets from the 623 spoofed host will fuel rather than defeat the SYN floods as compared 624 to the non-TFO case, because the attacker can flood more SYNs with 625 data to cost more data processing resources. For this reason, a TFO 626 server needs to monitor the connections in SYN-RCVD being reset in 627 addition to imposing a reasonable max queue length. Implementations 628 may combine the two, e.g., by continuing to account for those 629 connection requests that have just been reset against the listener's 630 PendingFastOpenRequests until a timeout period has passed. 632 Limiting the maximum number of pending TFO connection requests does 633 make it easy for an attacker to overflow the queue, causing TFO to be 634 disabled. We argue that causing TFO to be disabled is unlikely to be 635 of interest to attackers because the service will remain intact 636 without TFO hence there is hardly any real damage. 638 5.1.1 Attacks from behind Shared Public IPs (NATs) 640 An attacker behind a NAT can easily obtain valid cookies to launch 641 the above attack to hurt other clients that share the path. 642 [BRISCOE12] suggested that the server can extend cookie generation to 643 include the TCP timestamp---GetCookie(IP_Address, Timestamp)---and 644 implement it by encrypting the concatenation of the two values to 645 generate the cookie. The client stores both the cookie and its 646 corresponding timestamp, and echoes both in the SYN. The server then 647 implements IsCookieValid(IP_Address, Timestamp, Cookie) by encrypting 648 the IP and timestamp data and comparing it with the cookie value. 650 This enables the server to issue different cookies to clients that 651 share the same IP address, hence can selectively discard those 652 misused cookies from the attacker. However the attacker can simply 653 repeat the attack with new cookies. The server would eventually need 654 to throttle all requests from the IP address just like the current 655 approach. Moreover this approach requires modifying [RFC 1323] to 656 send non-zero Timestamp Echo Reply in SYN, potentially cause firewall 657 issues. Therefore we believe the benefit does not outweigh the 658 drawbacks. 660 5.2. Amplified Reflection Attack to Random Host 662 Limiting PendingFastOpenRequests with a system limit can be done 663 without Fast Open Cookies and would protect the server from resource 664 exhaustion. It would also limit how much damage an attacker can cause 665 through an amplified reflection attack from that server. However, it 666 would still be vulnerable to an amplified reflection attack from a 667 large number of servers. An attacker can easily cause damage by 668 tricking many servers to respond with data packets at once to any 669 spoofed victim IP address of choice. 671 With the use of Fast Open Cookies, the attacker would first have to 672 steal a valid cookie from its target victim. This likely requires the 673 attacker to compromise the victim host or network first. 675 The attacker here has little interest in mounting an attack on the 676 victim host that has already been compromised. But it may be 677 motivated to disrupt the victim's network. Since a stolen cookie is 678 only valid for a single server, it has to steal valid cookies from a 679 large number of servers and use them before they expire to cause 680 sufficient damage without triggering the defense. 682 One can argue that if the attacker has compromised the target network 683 or hosts, it could perform a similar but simpler attack by injecting 684 bits directly. The degree of damage will be identical, but TFO- 685 specific attack allows the attacker to remain anonymous and disguises 686 the attack as from other servers. 688 The best defense is for the server not to respond with data until 689 handshake finishes. In this case the risk of amplification reflection 690 attack is completely eliminated. But the potential latency saving 691 from TFO may diminish if the server application produces responses 692 earlier before the handshake completes. 694 6. TFO's Applicability 696 This section is to help applications considering TFO to evaluate 697 TFO's benefits and drawbacks using the Web client and server 698 applications as an example throughout. Applications here refer 699 specifically to the process that writes data into the socket, i.e., a 700 java script process that sends data to the server. A proposed socket 701 API change is in the Appendix. 703 6.1 Duplicate Data in SYNs 705 It is possible that using TFO results in the first data written to a 706 socket to be delivered more than once to the application on the 707 remote host(Section 2.1). This replay potential only applies to data 708 in the SYN but not subsequent data exchanges. 710 Empirically [JIDKT07] showed the packet duplication on a Tier-1 711 network is rare. Since the replay only happens specifically when the 712 SYN data packet is duplicated and also the duplicate arrives after 713 the receiver has cleared the original SYN's connection state, the 714 replay is thought to be uncommon in practice. Neverthless a client 715 that cannot handle receiving the same SYN data more than once MUST 716 NOT enable TFO to send data in a SYN. Similarly a server that cannot 717 accept receiving the same SYN data more than once MUST NOT enable TFO 718 to receive data in a SYN. 720 6.2 Potential Performance Improvement 722 TFO is designed for latency-conscious applications that are sensitive 723 to TCP's initial connection setup delay. To benefit from TFO, the 724 first application data unit (e.g., an HTTP request) needs to be no 725 more than TCP's maximum segment size (minus options used in SYN). 726 Otherwise the remote server can only process the client's application 727 data unit once the rest of it is delivered after the initial 728 handshake, diminishing TFO's benefit. 730 To the extent possible, applications SHOULD reuse the connection to 731 take advantage of TCP's built-in congestion control and reduce 732 connection setup overhead. An application that employs too many 733 short-lived connections will negatively impact network stability, as 734 these connections often exit before TCP's congestion control 735 algorithm takes effect. 737 6.3. Example: Web Clients and Servers 739 6.3.1. HTTP Request Replay 741 While TFO is motivated by Web applications, the browser should not 742 use TFO to send requests in SYNs if those requests cannot tolerate 743 replays. One example is POST requests without application-layer 744 transaction protection (e.g., a unique identifier in the request 745 header). 747 On the other hand, TFO is particularly useful for GET requests. 748 Although not all GET requests are idem-potent, GETs are frequently 749 replayed today across striped TCP connections: after a server 750 receives an HTTP request but before the ACKs of the requests reach 751 the browser, the browser may timeout and retry the same request on 752 another (possibly new) TCP connection. This differs from a TFO replay 753 only in that the replay is initiated by the browser, not by the TCP 754 stack. 756 6.3.2. Speculative Connections by the Applications 758 Some Web browsers maintain a history of the domains for frequently 759 visited web pages. The browsers then speculatively pre-open TCP 760 connections to these domains before the user initiates any requests 761 for them [BELSHE11]. While this technique also saves the handshake 762 latency, it wastes server and network resources by initiating and 763 maintaining idle connections. 765 6.3.3. HTTP over TLS (HTTPS) 767 For TLS over TCP, it is safe and useful to include TLS CLIENT_HELLO 768 in the SYN packet to save 1-RTT in TLS handshake. There is no concern 769 about violating idem-potency. In particular it can be used alone with 770 the speculative connection above. 772 6.3.4. Comparison with HTTP Persistent Connections 774 Is TFO useful given the wide deployment of HTTP persistent 775 connections? The short answer is yes. Studies [RCCJR11][AERG11] show 776 that the average number of transactions per connection is between 2 777 and 4, based on large-scale measurements from both servers and 778 clients. In these studies, the servers and clients both kept idle 779 connections up to several minutes, well into "human think" time. 781 Keeping connections open and idle even longer risks a greater 782 performance penalty. [HNESSK10][MQXMZ11] show that the majority of 783 home routers and ISPs fail to meet the the 124-minute idle timeout 784 mandated in [RFC5382]. In [MQXMZ11], 35% of mobile ISPs silently 785 timeout idle connections within 30 minutes. End hosts, unaware of 786 silent middle-box timeouts, suffer multi-minute TCP timeouts upon 787 using those long-idle connections. 789 To circumvent this problem, some applications send frequent TCP keep- 790 alive probes. However, this technique drains power on mobile devices 791 [MQXMZ11]. In fact, power has become such a prominent issue in modern 792 LTE devices that mobile browsers close HTTP connections within 793 seconds or even immediately [SOUDERS11]. 795 [RCCJR11] studied Chrome browser performance based on 28 days of 796 global statistics. The Chrome browser keeps idle HTTP persistent 797 connections for 5 to 10 minutes. However the average number of the 798 transactions per connection is only 3.3 and TCP 3WHS accounts for up 799 to 25% of the HTTP transaction network latency. The authors estimated 800 that TFO improves page load time by 10% to 40% on selected popular 801 Web sites. 803 7. Open Areas for Experimentation 805 We now outline some areas that need experimentation in the Internet 806 and under different network scenarios. These experiments should help 807 the community evaluate Fast Open benefits and risks towards further 808 standardization and implementation of Fast Open and its related 809 protocols. 811 7.1. Performance impact due to middle-boxes and NAT 813 [MAF04] found that some middle-boxes and end-hosts may drop packets 814 with unknown TCP options. Studies [LANGLEY06, HNRGHT11] both found 815 that 6% of the probed paths on the Internet drop SYN packets with 816 data or with unknown TCP options. The TFO protocol deals with this 817 problem by falling back to regular TCP handshake and re-transmitting 818 SYN without data or cookie options after the initial SYN timeout. 819 Moreover the implementation is recommended to negatively cache such 820 incidents to avoid recurring timeouts. Further study is required to 821 evaluate the performance impact of these malicious drop behaviors. 823 Another interesting study is the (loss of) TFO performance benefit 824 behind certain carrier-grade NAT. Typically hosts behind a NAT 825 sharing the same IP address will get the same cookie for the same 826 server. This will not prevent TFO from working. But on some carrier- 827 grade NAT configurations where every new TCP connection from the same 828 physical host uses a different public IP address, TFO does not 829 provide latency benefits. However, there is no performance penalty 830 either, as described in Section "Client: Receiving SYN-ACK". 832 7.2. Cookie-less Fast Open 834 The cookie mechanism mitigates resource exhaustion and amplification 835 attacks. However cookies are not necessary if the server has 836 application-level protection or is immune to these attacks. For 837 example a Web server that only replies with a simple HTTP redirect 838 response that fits in the SYN-ACK packet may not care about resource 839 exhaustion. For such an application, the server could decide to 840 disable TFO cookie checks. 842 Disabling cookies simplifies both the client and the server, as the 843 client no longer needs to request a cookie and the server no longer 844 needs to check or generate cookies. Disabling cookies also 845 potentially simplifies configuration, as the server no longer needs a 846 key. It may be preferable to enable SYN cookies and disable TFO 847 [RFC4987] when a server is overloaded by a large-scale Bot-net 848 attack. 850 Careful experimentation is necessary to evaluate if cookie-less TFO 851 is practical. The implementation can provide an experimental feature 852 to allow zero length, or null, cookies as opposed to the minimum 4 853 bytes cookies. Thus the server may return a null cookie and the 854 client will send data in SYN with it subsequently. If the server 855 believes it's under a DoS attack through other defense mechanisms, it 856 can switch to regular Fast Open for listener sockets. 858 7.3 Impact on congestion control 860 Although TFO does not directly change the congestion control, there 861 are subtle cases that it may. When SYN-ACK times out, regular TCP 862 reduces the initial congestion window before sending any data 863 [RFC5681]. However in TFO the server may have already sent up to an 864 initial window of data. 866 If the server serves mostly short connections then the losses of SYN- 867 ACKs are not as effective as regular TCP on reducing the congestion 868 window. This could result in an unstable network condition. The 869 connections that experience losses may attempt again and add more 870 load under congestion. A potential solution is to temporarily disable 871 Fast Open if the server observes many SYN-ACK or data losses during 872 the handshake across connections. Further experimentation regarding 873 the congestion control impact are useful. 875 8. Related Work 877 8.1. T/TCP 879 TCP Extensions for Transactions [RFC1644] attempted to bypass the 880 three-way handshake, among other things, hence shared the same goal 881 but also the same set of issues as TFO. It focused most of its effort 882 battling old or duplicate SYNs, but paid no attention to security 883 vulnerabilities it introduced when bypassing 3WHS [PHRACK98]. 885 As stated earlier, we take a practical approach to focus TFO on the 886 security aspect, while allowing old, duplicate SYN packets with data 887 after recognizing that 100% TCP semantics is likely infeasible. We 888 believe this approach strikes the right tradeoff, and makes TFO much 889 simpler and more appealing to TCP implementers and users. 891 8.2. Common Defenses Against SYN Flood Attacks 893 [RFC4987] studies on mitigating attacks from regular SYN flood, i.e., 894 SYN without data . But from the stateless SYN-cookies to the stateful 895 SYN Cache, none can preserve data sent with SYN safely while still 896 providing an effective defense. 898 The best defense may be to simply disable TFO when a host is 899 suspected to be under a SYN flood attack, e.g., the SYN backlog is 900 filled. Once TFO is disabled, normal SYN flood defenses can be 901 applied. The "Security Consideration" section contains a thorough 902 discussion on this topic. 904 8.3. TCP Cookie Transaction (TCPCT) 906 TCPCT [RFC6013] eliminates server state during initial handshake and 907 defends spoofing DoS attacks. Like TFO, TCPCT allows SYN and SYN-ACK 908 packets to carry data. But the server can only send up to MSS bytes 909 of data during the handshake instead of the initial congestion window 910 unlike TFO. Therefore applications like Web may not receive the 911 latency benefit as TFO. 913 9. IANA Considerations 915 The Fast Open Cookie Option and Fast Open Cookie Request Option 916 define no new namespace. The options require IANA to allocate one 917 value from the TCP option Kind namespace. Early implementation before 918 the IANA allocation SHOULD follow [RFC6994] and use experimental 919 option 254 and magic number 0xF989 (16 bits), then migrate to the new 920 option after the allocation accordingly. 922 10. Acknowledgement 924 We thank Bob Briscoe, Michael Scharf, Gorry Fairhurst, Rick Jones, 925 Roberto Peon, William Chan, Adam Langley, Neal Cardwell, Eric 926 Dumazet, and Matt Mathis for their feedbacks. We especially thank 927 Barath Raghavan for his contribution on the security design of Fast 928 Open and proofreading this draft numerous times. 930 11. References 932 11.1. Normative References 934 [RFC793] Postel, J. "Transmission Control Protocol", RFC 793, 935 September 1981. 937 [RFC1122] Braden, R., Ed., "Requirements for Internet Hosts - 938 Communication Layers", STD 3, RFC 1122, October 1989. 940 [RFC5382] S. Guha, Ed., Biswas, K., Ford B., Sivakumar S., Srisuresh, 941 P., "NAT Behavioral Requirements for TCP", RFC 5382 943 [RFC5681] Allman, M., Paxson, V. and E. Blanton, "TCP Congestion 944 Control", RFC 5681, September 2009. 946 [RFC6298] Paxson, V., Allman, M., Chu, J. and M. Sargent, "Computing 947 TCP's Retransmission Timer", RFC 6298, June 2011. 949 [RFC6928] Chu, J., Dukkipati, N., Cheng, Y. and M. Mathis, 950 "Increasing TCP's Initial Window", RFC 6928, April 2013. 952 [RFC6994] Touch, Joe, "Shared Use of Experimental TCP Options", 953 RFC6994, August 2013. 955 [RFC3390] Allman, M., Floyd, S., and C. Partridge, "Increasing TCP's 956 Initial Window", RFC 3390, October 2002. 958 11.2. Informative References 960 [AERG11] M. Al-Fares, K. Elmeleegy, B. Reed, and I. Gashinsky, 961 "Overclocking the Yahoo! CDN for Faster Web Page Loads". In 962 Proceedings of Internet Measurement Conference, November 963 2011. 965 [HNESSK10] S. Haetoenen, A. Nyrhinen, L. Eggert, S. Strowes, P. 966 Sarolahti, M. Kojo., "An Experimental Study of Home Gateway 967 Characteristics". In Proceedings of Internet Measurement 968 Conference. Octobor 2010 970 [HNRGHT11] M. Honda, Y. Nishida, C. Raiciu, A. Greenhalgh, M. 971 Handley, H. Tokuda, "Is it Still Possible to Extend TCP?". 972 In Proceedings of Internet Measurement Conference. November 973 2011. 975 [LANGLEY06] Langley, A, "Probing the viability of TCP extensions", 976 URL http://www.imperialviolet.org/binary/ecntest.pdf 978 [MAF04] Medina, A., Allman, M., and S. Floyd, "Measuring 979 Interactions Between Transport Protocols and Middleboxes", 980 In Proceedings of Internet Measurement Conference, October 981 2004. 983 [MQXMZ11] Z. Mao, Z. Qian, Q. Xu, Z. Mao, M. Zhang. "An Untold Story 984 of Middleboxes in Cellular Networks", In Proceedings of 985 SIGCOMM. August 2011. 987 [PHRACK98] "T/TCP vulnerabilities", Phrack Magazine, Volume 8, Issue 988 53 artical 6. July 8, 1998. URL 989 http://www.phrack.com/issues.html?issue=53&id=6 991 [QWGMSS11] F. Qian, Z. Wang, A. Gerber, Z. Mao, S. Sen, O. 992 Spatscheck. "Profiling Resource Usage for Mobile 993 Applications: A Cross-layer Approach", In Proceedings of 994 International Conference on Mobile Systems. April 2011. 996 [RCCJR11] Radhakrishnan, S., Cheng, Y., Chu, J., Jain, A. and 997 Raghavan, B., "TCP Fast Open". In Proceedings of 7th ACM 998 CoNEXT Conference, December 2011. 1000 [RFC1644] Braden, R., "T/TCP -- TCP Extensions for Transactions 1001 Functional Specification", RFC 1644, July 1994. 1003 [RFC4987] Eddy, W., "TCP SYN Flooding Attacks and Common 1004 Mitigations", RFC 4987, August 2007. 1006 [RFC6013] Simpson, W., "TCP Cookie Transactions (TCPCT)", RFC6013, 1007 January 2011. 1009 [SOUDERS11] S. Souders. "Making A Mobile Connection". 1010 http://www.stevesouders.com/blog/2011/09/21/making-a- 1011 mobile-connection/ 1013 [BRISCOE12] Briscoe, B., "Some ideas building on draft-ietf-tcpm- 1014 fastopen-01", tcpm list, 1015 http://www.ietf.org/mail-archive/web/tcpm/current/ 1016 January 16, 2014msg07192.html 1018 [BELSHE12] Belshe, M., "The era of browser preconnect.", 1019 http://www.belshe.com/2011/02/10/ 1020 the-era-of-browser-preconnect/ 1022 [JIDKT07] Jaiswal, S., Iannaccone, G., Diot, C., Kurose, J., and 1023 Towsley, D. "Measurement and classification of 1024 out-of-sequence packets in a tier-1 IP backbone.", 1025 IEEE/ACM Transactions on Networking (TON), 15(1), 54-66. 1027 Appendix A. Example Socket API Changes to support TFO 1029 A.1 Active Open 1031 The active open side involves changing or replacing the connect() 1032 call, which does not take a user data buffer argument. We recommend 1033 replacing connect() call to minimize API changes and hence 1034 applications to reduce the deployment hurdle. 1036 One solution implemented in Linux 3.7 is introducing a new flag 1037 MSG_FASTOPEN for sendto() or sendmsg(). MSG_FASTOPEN marks the 1038 attempt to send data in SYN like a combination of connect() and 1039 sendto(), by performing an implicit connect() operation. It blocks 1040 until the handshake has completed and the data is buffered. 1042 For non-blocking socket it returns the number of bytes buffered and 1043 sent in the SYN packet. If the cookie is not available locally, it 1044 returns -1 with errno EINPROGRESS, and sends a SYN with TFO cookie 1045 request automatically. The caller needs to write the data again when 1046 the socket is connected. On errors, it returns the same errno as 1047 connect() if the handshake fails. 1049 An implementation may prefer not to change the sendmsg() because TFO 1050 is a TCP specific feature. A solution is to add a new socket option 1051 TCP_FASTOPEN for TCP sockets. When the option is enabled before a 1052 connect operation, sendmsg() or sendto() will perform Fast Open 1053 operation similar to the MSG_FASTOPEN flag described above. This 1054 approach however requires an extra setsockopt() system call. 1056 A.2 Passive Open 1058 The passive open side change is simpler compared to active open side. 1059 The application only needs to enable the reception of Fast Open 1060 requests via a new TCP_FASTOPEN setsockopt() socket option before 1061 listen(). 1063 The option enables Fast Open on the listener socket. The option value 1064 specifies the PendingFastOpenRequests threshold, i.e., the maximum 1065 length of pending SYNs with data payload. Once enabled, the TCP 1066 implementation will respond with TFO cookies per request. 1068 Traditionally accept() returns only after a socket is connected. But 1069 for a Fast Open connection, accept() returns upon receiving a SYN 1070 with a valid Fast Open cookie and data, and the data is available to 1071 be read through, e.g., recvmsg(), read(). 1073 Authors' Addresses 1075 Yuchung Cheng 1076 Google, Inc. 1077 1600 Amphitheatre Parkway 1078 Mountain View, CA 94043, USA 1079 EMail: ycheng@google.com 1081 Jerry Chu 1082 Google, Inc. 1083 1600 Amphitheatre Parkway 1084 Mountain View, CA 94043, USA 1085 EMail: hkchu@google.com 1087 Sivasankar Radhakrishnan 1088 Department of Computer Science and Engineering 1089 University of California, San Diego 1090 9500 Gilman Dr 1091 La Jolla, CA 92093-0404 1092 EMail: sivasankar@cs.ucsd.edu 1094 Arvind Jain 1095 Google, Inc. 1096 1600 Amphitheatre Parkway 1097 Mountain View, CA 94043, USA 1098 EMail: arvind@google.com