USOO8069225B2
`
`(12) United States Patent
`US 8,069,225 B2
`McCanne et a1.
`
`Nov. 29, 201](45) Date of Patent:
`
`(10) Patent No.:
`
`(54)
`
`(75)
`
`TRANSPARENT CLIENT-SERVER
`TRANSACTION ACCELERATOR
`
`6,415,329 B1
`6.519.5’16 Bl *
`
`7t’2002 Gelmanetal.
`2.-"2003 Freeman ......................... 706(21
`
`Inventors: Steven McCanne, Berkeley, CA (US);
`Michael J. Demmer, San Francisco, CA
`(US); Arvind Jain, Santa Clara, CA
`(US); David Tze-Si Wu. Fremont. CA
`(US)
`
`(Continued)
`
`EP
`
`FOREIGN PATENT DOCUMENTS
`0 813 326 A2
`12t19'97-r
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`(73)
`
`Assignee: Riverbed Technology, Inc._. San
`Francisco. CA (US)
`
`Knutsson. Bjorn et al; “Transparent Proxy Signalling"; Journal of
`Cbmmwu’catt’on Network. Mar. 2001. pp. 1-1 1.
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 2039 days.
`
`(21)
`
`Appl. No.: 1011540305
`
`(22)
`
`Filed:
`
`Aug. 12, 2003
`
`(65)
`
`(50)
`
`(51)
`
`(52)
`(53)
`
`(56)
`
`Prior Publication Data
`
`US 2004t0215746 Al
`
`Oct. 28, 2004
`
`Related U.S. Application Data
`
`Provisional application No. 601462390, filed on Apr.
`14, 2003.
`
`Int. Cl.
`(2006.01)
`GMF 15/16
`U.S. Cl.
`.......................................... 70911219; 7062]
`Field of Classification Search .................. 711/153;
`7170169; 704(456; 7091223, 219, 236. 238,
`709(231, 250, 203. 228; 707i]; 706121
`See application file for complete search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,754,??4 A
`6,173,461 B1
`6,219,642 B1 "'
`
`5(1998 Bittingcr ct al.
`152001 Chan et a1.
`452001 ASgthr et a1.
`
`.............. 704:? 56.3
`
`(Continued)
`
`Primary Examiner — Dustin Nguyen
`(74) Attorney. Agent, orFI‘nn — Philip H. Albert; Kilpatrick
`Townsend & Stockton LLP
`
`ABSTRACT
`(57)
`In a network that conveys requests from clients to servers and
`responses from servers to clients, a network transaction accel-
`erator for accelerating transactions involving data transfer
`between at least one client and at least one server over a
`network comprising a client-side engine, a server-side engine
`and a transaction predictor configured to predict, based on
`past transactions, which transactions are likely to occur in the
`future between the client and server. The transaction predictor
`might be in the server-side engine, the client-side engine, or
`both. The client-side engine receives indications of requests
`from the client. a transaction buffer for storing results of
`predicted transactions received from the server or the server-
`side engine ahead of receipt ofa corresponding request, and a
`collator for collating the requests from the client with the
`stored results or received results. wherein a request and a
`response that are matched by the collator are identified and
`the matched response is provided to the client in response to
`the matched request. The server-side engine receives indica-
`tions of transactions including requests and responses and
`conveys requests to the server in response to actual transac-
`tions or predicted transactions.
`
`33 Claims, 10 Drawing Sheets
`
`. Inllial Ielerlcir delay could be optimized war as wel
`
`L100? L4559 L3?“
`
`Flies 1.2 153
`
`oTI'ansacIlans ale mediated based on past behavior. than Mined
`IAII transemione still go beck to Ihe server
`.Any data that is sent is optimized uslng the hlerarchinal cloning system
`*Adual amount oldala sent is a small fraction of orlginal size
`
`RlV-1005 - Page 1 of 29
`
`

`

`US 8,069,225 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6,546,428 B2
`6,563,517 B1 "‘
`6,574,618 B2 "‘
`6,578,073 B1 “’
`6,622,168 B1 "'
`6,789,255 B1 "'
`6,820,133 B1 "'
`6,839,682 Bl "‘
`6,874,017 Bl
`7,082,456 B2 "‘
`7,149,817 B2 "‘
`7,224,839 B2 "'
`7,619,545 B2
`7,809,818 BZ
`7,827,237 BZ
`7,865,585 BZ
`7,916,047 BZ
`200270013853 Al
`200270023145 Al "'
`200270029326 Al "'
`200270087547 Al
`200270107971 Al "‘
`200270138511 Al
`200270147895 Al "'
`200270194382 Al
`200370009583 Al “'
`200470088376 Al
`200470215746 Al
`
`472003 Baberetai.
`.............. 7157735
`572003 Bhagwat et a].
`672003 Eylon et al.
`....................... 70771
`672003 Starnes et al.
`7097219
`7097219
`972003 Datla ..............
`
`972004 Pedrizetti et al.
`7177169
`
`1 172004 Grove et a1.
`7097238
`.................... ”705710
`172005 Blume et al.
`372005 Inoue eta].
`709.7203
`”772006 Mani-Meitav et al.
`
`7097250
`1272006 Pettey
`572007 Zeineh .......................... 3827232
`1172009 Samuels et a1.
`1072010 Plamondon
`1 172010 Plamondon
`172011 Samuels et al.
`372011 Samuels et al.
`172002 Baber etal.
`272002 Orr et a1.
`....................... 7097219
`372002 Renter et a1.
`.................. 7117206
`772002 Kausik et al.
`872002 Bailey et al.
`972002 Psounis et a].
`1072002 Glance et al.
`1272002 Kausik et al.
`172003 Chan et a1.
`.................... 7097236
`572004 McCanne et a].
`1072004 McCanne et a].
`
`.................. 709.7231
`................. 7117158
`
`W0
`
`FOREIGN PATENT DOCUMENTS
`WO 01763420 A1
`872001
`
`OTHER PUBLICATIONS
`
`Amer et al.. “File Access Prediction with Adjustable Accuracy.”
`Corrf Proc. of 2002 {EEE 7777. Performance, Computing med Com—
`munications. 21 :131-140, conference heldApr. 3-5, 2002 in Phoenix,
`AZ.
`
`Padmanabhan et al.. “Using Predictive Prefetching to Improve World
`Wide Web Latency,” iEEE ii‘arrmciiom on Antennas and Propaga—
`tion. 26(3):22-36 (1996).
`Cacer'es, Ramon et al.. "Webb Proxy Caching: The Devil Is In the
`Details.” Jun. 1998. Proceedings ofrhe Works-hop on inremei Ser'mr‘
`Perfor'rrionce, Madison. Wisconsin, pp. 1 11-1 18.
`Deshpande. Mukund et al.. “Selective Markov Models for Predicting
`Web-Page Accesses.” 2004. ACM fi‘mrsacriom on imerrrei Tecirrroi—
`ogy. vol. 4, Issue 2, pp. 163-184.
`Fan, Li et al., “Summary Cache: A Scalable Wide Area Web Cache
`Sharing Protocol.” Jun. 2000. Proceedings ofrne [EEE/HCirf ii'ans-
`actions on Networking, vol. 8, No. 3, pp. 281-293.
`Feldmeier', D.C. et al.. “Protocol Boosters.” Apr'. 1998. IEEE JSAC.
`vol. 16. Issue No. 3. pp. 437-444.
`Gr'iffioen, James et al.. ”Automatic Prefetching in aWAN.” Oct. 1993.
`Proceedings of tire [EEE ii’or'fisnop on Advances in Paraiiei and
`Distributed Systems. Technical Report 77 CS243-93. pp. 8- 12.
`Gr'iffioen, James et al., “Reducing File System Latency using a Pre-
`dictive Approach.” Jun. 1994. Proceedings ofiire USENLYSummer‘
`799-7 iiecnnicoi Conference on {x'SENiX Technical Conference, vol.
`1.
`Lei. Hui et al., “An Analytical Approach to File Prefetching.” Jan.
`1997. Proceedings of tire Anniiai Conference on USENIXAnnuai
`Technicoi Conference. Anaheim, California. pp. 1-12.
`01y. James et al.. “Markov Model Prediction of 170 Requests for
`Scientific Applications.” Jun. 2002. Proceedings ofthe 76:7: interim—
`tionai Confluence on Snpercompming. pp. 147-155.
`Rhea. Sean C. et al., "Value—Based Web Caching.” May 2003, Pro-
`ceedings ofrhe i 277: irrier‘rraiioriai Conference or: Worid Wide Web.
`Budapest. Hungary. pp. 619628.
`Tolia, Niraj, et a1 ., “An Architecture for Internet Data Transfer.” May
`2006. Third S}mposiam on Networked Systems Design and impie—
`meniaiiorr.
`Yang, Qiang et al., “Mining Web Logs for Prediction Models in
`WW Caching and Prefetching.” Aug. 2001, Proceedings of tire
`Sevenr‘nACMSiGKDDinr‘er'nar‘ionai Cbrrferenceon KnowiedgeDis-
`cover}' and Data Mining KDD’Or‘. San Francisco, California, pp,
`473-4778,
`Office Action in US. Appl. No. 127191.15 14 dated May 17, 2011.
`
`* cited by examiner
`
`RIV-1005 - Page 2 of 29
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet 1 0f 10
`
`US 8,069,225 132
`
`
`
`
`
`$35:329325
`
`3322
`
`5050
`
`o T
`1
`+T3
`
`.
`
`
`
`
`
`5
`
`——-a..___,,____m___fl
`
`
`10
`
`20
`
`30
`
`40
`
`50
`
`60
`
`70
`
`8O
`
`90
`
`100
`
`Latency (ms)
`
`
`
`szocuzuiAEEE
`
`
`
`
`
`RIV-1005 - Page 3 of 29
`
`

`

`US. Patent
`
`,0\.
`
`U
`
`8S
`
`2B522.,
`
`_iH_i
`
`9|la_m92:x_
`
`
`
`wmzawEU
`
`5.50m
`
`cork
`
`m.0.,mGE
`
`UE281:muzxwua
`..
`s_m2
`
`
`
`._.._F“I£2253IIIN_Mn_Ir_W.Lx
`
`N?/x_ix
`
`wEazo
`
`RIV-1005 - Page 4 of 29
`
`
`
`
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet 3. one
`
`US 8,069,225 132
`
`200
`
`HostMemory
`
`
`
`
`
` DualPortNiC
`
`
`
`
`
`LinuxInterceptModule
`
`EngineProcess
`
`
`
`L2Switch
`
`FIG.4
`
`RIV-1005 - Page 5 of 29
`
`

`

`US. Patent
`
`m.__V.mmmnEmDwmmomgmo_6569;
`
`
`36691___Zdj
`
`
`
`E9299“.EmEmLmQ
`
`
`
`99mEmEmmm9onE9535
`
`m_
`
`2E96_
`
`
`
`59:0Encowo625$59:E55W_09m$5_.
`
`
`
`
`
`M
`
`6
`
`2B5n
`
`22899259396hgH8559:mcacmgmAhS52mm
`
`
`4AVm53:9toamcmFtoamcmt.BMWPWL
`
`
`
`
`
`233029322
`
`9.,m.O_n_
`
`
`.UeEmcmmEmEm_mew62%EmE96_3%:$33tOchmF
`m,__SZdj__253
`
`EmmEsz_
`
`RIV-1005 - Page 6 of 29
`
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet
`
`SOHO
`
`US 8,069,225 132
`
`
`
`mwNuFmo__n_
`
`Em"NJummm
`
`
`
`Emmimmmfljmoo_‘._
`
`...m”Nu_.
`umwm
`
`52mm
`
`IIII
`IIII
`
`EEO
`
`
`
`09onE08958on:6mm
`
`E
`
`
`
`umzzmafi:9:.5338Ema:3Emma53.285Em95:20.95;.
`
`mwmnrmmzn—
`
`
`
`
`
`
`
`
`
`E936mchEEUEEEmE9:mafiaBHEEOm_Emmm_E:Emu2%.
`
`
`
`523m«E.2xomp0m__=wmcgommcmz__<-
`
`
`
`
`
`36$5955cozomc:mEmmm_:56EmuhoEzoEmEEO/x.
`
`w.0E
`
`:95mm33mumflEEoma2:00>m_muBEEEEE.
`
`RIV-1005 - Page 7 of 29
`
`

`

`US. Patent
`
`m\
`
`1m
`
`6mh
`
`.U
`
`Q“
`
`,00.,
`
`n,
`
`522.,
`
`mwowwSUoEMmEEmE
`
`1'
`
`mmmcogme
`
`S\mmmcoammL
`
`,mgmcafitmmbmq:9_E0.9a5.m862mm0$57_LohmbmeH.U#__DH;
`
`
`
`mfimzcmgmfimzcmg
`
`5E5ormc9585
`
`V/oow
`
`80%
`
`2IBk0t
`
`RIV-1005 - Page 8 of 29
`
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet 7 one
`
`US 8,069,225 132
`
`
`
`FIG. 8 (Prior Art)
`
`RIV-1005 - Page 9 of 29
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet 8 one
`
`US 8,069,225 132
`
`
`
`FIG. 9
`
`RIV—1005 - Page 10 of 29
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet 9 one
`
`US 8,069,225 132
`
`
`
`FIG. 10
`
`RIV—1005 - Page 11 of 29
`
`

`

`US. Patent
`
`Nov. 29, 2011
`
`Sheet 10 0f 10
`
`US 8,069,225 132
`
`09009
`
`FIG. 11A
`
`o'eri'oi‘o‘e
`
`FIG. 11B
`
`
`
`FIG. 12
`
`RIV—1005 - Page 12 of 29
`
`

`

`US 8,069,225 82
`
`l
`TRANSPARENT C LIENT—SERVER
`TRANSACTION ACCELERATOR
`
`CROSS—REFERENCES TO RELATED
`APPLICATIONS
`
`5
`
`2
`demand for “more bandwidth” to remote sites in an
`
`effort to improve the performance for distributed users.
`Causes of Poor WAN Throughput
`The two primary causes of the slow throughput on WANs
`are well known: high delay (or latency) and limited band-
`width. The “bandwidth” of a network of channel refers to
`measure of the number of bits that can be transmitted over a
`link or path per unit of time. “Latency" refers to a measure of
`the amount of time that transpires while the bits traverse the
`network, e. g. _. the time it takes a given bit transmitted from the
`sender to reach the destination. “Round-trip time” refers to
`the sum of the “source-to-destination" latency and the “des-
`tination-to-source" latency. Ifthe underlying paths are asym-
`metric, the round-trip latency might be different than twice a
`one-way latency. The term “throughput” is sometimes oon-
`fused with bandwidth but refers to a measure of an attained
`
`transfer rate that a client-server application, protocol. etc.
`achieves over a network path. Throughput is typically less
`than the available network bandwidth.
`The speed of light, a fundamental and fixed constant,
`implies that information transmitted across a network always
`incurs some nonzero latency as it travels from the source to
`the destination. In practical terms, this means that sending a
`packet from Silicon Valley to New York and back could never
`occur faster than about 30 milliseconds (ms )_. the time infor-
`mation in an electromagnetic signal would take to travel that
`distance in a direct path cross-country. In reality. this cross-
`country round trip time is more in the range of 100 ms or so,
`as signals in fiber or copper do not always travel at the speed
`of light in a vacuum and packets incur processing delays
`through each switch and router. This amount of latency is
`quite significant as it is at least two orders of magnitude
`higher than typical sub-millisecond LAN latencies.
`Other round-trips might have more latency. Round trips
`from the West Coast of the US. to Europe can be in the range
`of 100-200 ms, and some links using geo-stationary satellites
`into remote sites can have latencies in the 500-800 ms range.
`With latencies higher than about 50 ms, many client-server
`protocols and applications will filnction poorly relative to a
`LAN as those protocols and applications expect very low
`latency.
`While many employees routinely depend upon Fast Ether-
`net (100 Mbps) or Gigabit Ethernet (1 Gbps) within most
`corporate sites and headquarters facilities,
`the bandwidth
`intercomrecting many corporate and industrial sites in the
`world is much lower. Even with DSL. Frame Relay or other
`broadband technologies, WAN connections are slow relative
`to a LAN. For example, 1 Mbps DSL service offers only V100“
`the bandwidth ofFast Ethernet and 1/1000“ ofwhat is available
`using Gigabit Ethernet.
`While some places might have high bandwidth backbone
`networks, such as the Metro Ethernet available in South
`Korea and Japan, the latency and bandwidth issues persist
`whenever data needs to travel outside areas with such net-
`
`works. For example. a Japanese manufacturer with plants in
`Japan and the US. might needs to send CAD/CAM files back
`and forth between plants. The latency from Japan to the East
`Coast of the US. might be as high as 200 ms and trans-Pacific
`bandwidth can be expensive and limited.
`WAN network bandwidth limits almost always impact cli-
`ent-server application throughput across the WAN, but more
`bandwidth can be bought. With latency, lower latency cannot
`be bought if it would require faster than light communica-
`tions. In some cases, network latency is the bottleneck on
`perfonnance or throughput. This is often the case with win-
`dow-based transport protocols such as TCP or a request-
`response protocol such as the Common Internet File System
`
`RIV—1005 - Page 13 of 29
`
`10
`
`15
`
`This application claims priority from US. Provisional
`Patent Application No. 60t462,990 entitled “Transport-Level
`Network Accelerator" filedApr. 14, 2003 and is incorporated
`by reference herein for all purposes.
`The present disclosure is related to the following corn-
`1nonly assigned co-pending US. patent applications:
`U.S. patent application Ser. No. 10t285,315 entitled
`“Transaction Accelerator for Client-Server Communi-
`cation Systems” (hereinafter “McCanne I”) filed on Oct.
`30, 2002 and is incorporated by reference herein for all
`purposes;
`U.S. patent application Ser. No. 10285330 entitled “Con-
`tent-Based Segmentation Scheme for Data Compres-
`sion in Storage and Transmission Including Hierarchical
`Segment Representation” (hereinafier “McCanne II”)
`filed on Oct. 30. 2002 and is incorporated by reference
`herein for all purposes; and
`US. patent application Ser. No. 10/640,562 know US. Pat.
`No. 7,318,100) entitled “Cooperative Proxy Auto-Dis- 35
`covery and Connection Interception"
`(hereinafter
`“McCanne IV") filed concurrently herewith and is incor-
`porated by reference herein for all purposes.
`
`30
`
`FIELD OF THE INVENTION
`
`The present invention relates to data transport over net-
`works in general and more particularly may relate to improve-
`ments in data transport at the transport level between a client
`and a server.
`
`BACKGROUND OF THE INVENTION
`
`30
`
`35
`
`Local Area Network (LAN) communication is character-
`ized by generous bandwidths. low latencies and considerable 40
`enterprise control over the network. By contrast. Wide Area
`Networks (WANs) often ltave lower bandwidths and higher
`latencies than LANs and often have a measure of network
`
`control that is outside the enterprise for which the WAN is
`being used.
`“ride-area client-server applications are a critical part of
`almost any large enterprise. A WAN might be used to provide
`access to widely used and critical infrastructure. such as file
`servers. mail servers and networked storage. This access most
`often has very poor throughput when compared to the perfor- 50
`mance across a LAN. Whether an enterprise is taking a cen-
`tralized approach or a distributed approach, high performance
`communication across the WAN is essential in order to mini-
`
`45
`
`mize costs and maximize productivity. Enterprise IT manag-
`ers today typically take one oftwo approaches to compensate 55
`for the performance challenges inherent in WANs:
`l . Ifthe IT infrastructure is decentralized and they intend to
`keep it that way, corporate network and server managers
`typically have to deploy local file servers. data storage,
`mail servers, and backup systems with some redundancy 60
`iii each remote office to ensure fast and reliable access to
`critical data and applications at each office. They also
`may maintain over-provisioned WAN links in order to
`enable reasonable levels ofperforlnance for file transfers
`and similar data-intensive tasks.
`2. If the IT infrastructure is already centralized or semi-
`centralized, the enterprise will be faced with a constant
`
`65
`
`

`

`US 8,069,225 B2
`
`3
`(CIFS) protocol or the Network File System (NFS) protocol.
`High network latency particularly slows down “chatty" appli-
`cations. even ifthe actual alnounts ofdata transmitted in each
`transaction are not large. “Chatty” applications are those in
`which client-server interactions involve many back-and-forth
`steps that might not even depend on each other. Adding band-
`width (or compressing data) does not improve the throughput
`of these protocolsfapplications when the round-trip time
`exceeds some critical point and once the latency reaches that
`critical point, throughput decays quickly.
`This phenomenon can be understood intuitively: the rate of
`work that can be performed by a client-server application that
`executes serialized steps to accomplish its tasks is inversely
`proportional to the round-trip time between the client and the
`server. If the client-server application is bottlenecked in a
`serialized computation (i.e.. it is “chatty"), then increasing
`the round-trip by a factor of two causes the throughput to
`decrease by a factor of two because it takes twice as long to
`perform each step (while the client waits for the server and
`vice versa).
`More generally. the throughput of client-server applica-
`tions that are not necessarily chatty but run over a window-
`based protocol (such as TCP) can also suffer from a similar
`fate. This can be modeled with a simple equation that
`accotmts for the round-trip time (RTT) and the protocol win-
`dow (W). The window defines how much data the sender can
`transmit before requiring receipt of an acknowledgement
`from the receiver. Once a window’s worth of data is sent. the
`sender must wait until it hears from the receiver. Since it takes
`
`a round-trip time to receive the acknowledgement from the
`receiver. the rate at which data can be sent is simply the
`window size divided by the round trip time:
`T= W/RTT
`
`The optimal choice ofwindow size depends on a number of
`factors. To perform well across a range ofnetwcrk conditions,
`a TCP device attempts to adapt its window to the underlying
`capacity of the network. So, if the underlying bottleneck
`bandwidth (or the TCP sender’s share of the bandwidth) is
`roughly B bits per second, then a TCP device attempts to set
`its window to BxR'I—I', and the throughput, T, would be:
`r=(serrerr=3
`
`In other words, the throughput would be equal to the avail-
`able rate. Unfortunately. there are often other constraints.
`Many protocols, such as TCP and CIFS. have an upper bound
`on the window size that is built into the protocol. For example.
`the maximum request size in CIFS is 64 KB and in the
`original TCP protocol. the maximum window size was lim-
`ited by the fact that the advertised window field in the protocol
`header is 16 bits. limiting the window also to 64 KB. While
`modern TCP stacks implement the window scaling method in
`RFC 1323 to overcome this problem, there are still many
`legacy TCP implementations that do not negotiate scaled
`windows. and there are more protocols such as CIFS that have
`application-level limits on top of the TCP window limit. So.
`in practice, the throughput is actually limited by the maxi-
`mum window size (MWS)
`T=min(BxRTT.-MWS)-"R IT< =3
`
`Even worse. there is an additional constraint on throughput
`that
`is fiJndamental
`to the congestion control algorithm
`designed into TCP. This flaw turns out to be non-negligible in
`wide-area networks where bandwidth is above a few megabits
`and is probably the key reason why enterprises often fail to
`see marked performance improvements of individual appli-
`cations after substantial bandwidth upgrades.
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Essentially, this problem stems from conflicting goals of
`the TCP congestion control algoritlun that are exacerbated in
`a high-delay enviromnent. Namely. upon detecting packet
`loss, a TCP device reacts quickly and significantly to err on
`the side of safety (i.e., to prevent a set of TCP connections
`from overloading and congesting the network). Yet, to probe
`for available bandwidth, a TCP device will dynamically
`adjust its sending rate and continually push the network into
`momentary periods of congestion that cause packet loss to
`detect bandwidth limits. In short. a TCP device continually
`sends the network into congestion then aggressively backs
`off. In a high-latency environment, the slow reaction time
`results in throughput limitations.
`An equation was derived in the late 1990’s that models the
`behaviorof a network as a function ofthe packet loss rate that
`TCP induces and that equation is:
`Cuis=1.2x.s.-sqrrtp)
`
`As indicated by that equation. the average congestion win-
`dow size (CWS) is roughly determined by the packet size (S)
`and the loss rate (p). Taking this into account. the actual
`throughput ofa client-server application rumting over TCP is;
`T: WKR TT=min(MW.S', C WSfixR TWR TT
`
`FIG. 1 is a graph that illustrates this problem from a very
`practical perspective. That graph shows the perfonnance of a
`TCP data transfer when the network is experiencing a low
`degree ofnetwork loss (less than 1/10 of 1 percent) for increas-
`ing amotmts of latency. The bottom curve represents the TCP
`throughput achievable from a T1 line. which is roughly equal
`to the available bandwidth (1 .544 Mbr's) all the way up to 100
`ms latencies. The top curve. on the other hand. illustrates the
`performance impact of the protocol window at higher band-
`widths. With a T3 line, the TCP throughput starts out at the
`available line rate (45 bes) at low latencies. but at higher
`latencies the throughput begins to decay rapidly (in fact.
`hyperbolically). This effect is so dramatic that at a 100 ms
`delay (i.e.. a typical cross-country link). TC P throughput is
`only 4.5 Mb/s of the 45 bes link.
`Under such conditions, application performance does not
`always increase when additional bandwidth is added. As FIG.
`1 shows, ifthe round trip time (RTT) is greater than a critical
`point (just 15 111s or so in this example) then increasing the
`bandwidth of the link will only marginally improve through-
`put at higher latency and at even higher latencies. throughput
`is not increased at all with increases in bandwidth.
`FIG. 2 graphs a surface ofthroughput model derived above,
`presuming a TCP transfer over a 45 Mb/s T3 link. The surface
`plots throughput as a function of both round-trip times and
`loss rates. This graph shows that both increasing loss and
`increasing latency impair performance. While latency has the
`more dramatic impact. they combine to severely impact per-
`formance. In environments with relatively low loss rates and
`normal WAN latencies, throughput can be dramatically lim-
`ited.
`Existing Approaches to Overcoming WAN Throughput Prob-
`lems
`Given the high costs and performance challenges ofWAN-
`based enterprise computing and communication. many
`approaches have been proposed for dealing with these prob-
`lems.
`Perhaps the simplest approach to dealing with performance
`is to simply upgrade the available bandwidth in the network.
`Of course this is the most direct solution. but it is not always
`the most effective approach. First of all. contrary to popular
`belief, bandwidth is not free and the costs add up quickly for
`large enterprises that may have hundreds of offices. Second,
`
`RIV—1005 - Page 14 of 29
`
`

`

`US 8,069,225 B2
`
`5
`as discussed earlier, adding bandwidth does not necessarily
`improve throughput. Third,
`in some places adding more
`bandwidth is not possible, especially across international
`sites, in remote areas, or where it is simply too expensive to
`justify.
`Another approach is to embed intelligence in the applica-
`tions themselves, e.g., to exploit that fact that data often
`changes in incremental ways so that the application can be
`designed to send just incremental updates to between clients
`and servers. Usually, this type ofapproach employs some sort
`of versioning system to keep track of version numbers of files
`(or data objects) so that differences between versioned data
`can be sent between application components across the net-
`work. For example, some content management systems have
`this capability and storage backup software generally
`employs this basic approach. However, these systems do not
`deal with scenarios where data is manipulated outside oftheir
`domain. For example. when a file is renamed and re-entered
`into the system the changes between the old and new versions
`are not captured. Likewise, when data flows between distinct
`applications (e.g., a file is copied out ofa content manage-
`ment system and into a file system), versioning cannot be
`carried out between the different components.
`This approach of managing versions and communicating
`updates can be viewed as one specific (and application-spe-
`cific) approach to compression. More generally. data com-
`pression systems can be utilized to ameliorate network band-
`width bottlenecks. Compression is a process of representing
`one set of data with another set of data wherein the second set
`
`of data is. on average. a smaller number of bits than the first
`set ofdata, such that the first set of data. or at least a sufficient
`approximation of the first set of data, can be recovered from
`an inverse of the compression process in most cases. Corn-
`pression allows for more efficient use of a limited bandwidth
`and might result in less latency. but in some cases. no latency
`improvement occurs. In some cases, compression might add
`to the latency. if time is needed to compress data after the
`request is made and time is needed to decompress the data
`after it is received. This may be able to be improved ifthe data
`can be compressed ahead of time, before the request is made,
`but that may not be feasible if the data is not necessarily
`available ahead of time for compression, or if the volume of
`data from which the request will be served is too large relative
`to the amount of data likely to be used.
`One way to deploy compression is to embed it in applica-
`tions. For example. a Web server can compress the HTML
`pages it returns before delivering them across the network to
`end clients. Another approach is to deploy compression in the
`network without having to modify the applications. For many
`years, network devices have included compression options as
`features (e.g..
`in routers. modems, dedicated compression
`devices, etc) [D. Rand, “The PPP Compression Control Pm-
`toco] (CCP)”_. Request-for-Comments 1962,June 1996]. This
`is a reasonable thing to do. but the effectiveness is limited.
`Most methods of lossless data compression typically reduce
`the amount of data (i.e., bandwidth) by a factor of 1.5 to 4,
`depending on the inherent redundancy present. While helpful,
`it is not enough to dramatically change performance if the
`amount of data being sent is large or similar data is sent
`repeatedly. perhaps over longer time scales. Also. when per-
`formance is limited by network latency. compressing the
`underlying data will have little or no impact.
`Rather than compress the data. another approach to work-
`ing around WAN bottlenecks is to replicate servers and server
`data in local servers for quick access. This approach in par-
`ticular addresses the network latency problem because a cli-
`ent in a remote site can now interact with a local server rather
`
`10
`
`IS
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`than a remote server. There are several methods available to
`
`enterprises to store redundant copies of data in replicated file
`systems, redundant or local storage servers. or by using any
`number of distributed file systems. The challenge with this
`kind of approach is the basic problem of managing the ever-
`exploding amount of data, which requires scaling 11p storage,
`application and file servers in many places. and trying to make
`sure that the files people need are indeed available where and
`when they are needed. Moreover, these approaches are gen-
`erally non-transparent, meaning the clients and servers must
`be modified to implement and interact with the agents andi'or
`devices that perform the replication function. For example, if
`a file server is replicated to a remote branch, the server must
`be configured to send updates to the replica and certain clients
`must be configured to interact with the replica while others
`need to be configured to interact with the original server.
`Rather than replicate servers, another approach is to deploy
`transport-level or application-level devices called “proxies".
`which function as performance-enhancing intermediaries
`between the client and the server. In this case, a proxy is the
`tenninus for the client connection and initiates another con-
`
`nection to the server on behalfof the client. Alternatively, the
`proxy connects to one or more other proxies that in tum
`connect to the server. Each proxy may forward. modify, or
`otherwise transform the transactions as they flow from the
`client to the server and vice versa. Examples of proxies
`include (1) Web proxies that enhance performance through
`caching or enhance security by controlling access to servers,
`(2) mail relays that forward mail from a client to another mail
`server. (3) DNS relays that cache DNS name resolutions. and
`so forth.
`
`With a proxy situated between the client and server, the
`performance impairments of network latency can be
`addressed by having the proxy cache data. Caching is a pro-
`cess of storing previously transmitted results in the hopes that
`the user will request the results again and receive a response
`more quickly from the cache than if the results had to come
`from the original provider. Caching also provides some help
`in mitigating both latency and bandwidth bottlenecks, but in
`solne situations it does not help much. For example. where a
`single processor is retrieving data from memory it controls
`and does so in a repetitive fashion, as might be the case when
`reading processor instructions from memory, caching can
`greatly speed a processor’s tasks. Similarly, file systems have
`employed caching mechanisms to store recently accessed
`disk blocks in host memory so that subsequent accesses to
`cached blocks are completed much faster than reading them
`in from disk again as in BSD Fast File System [McKusick_. et
`al., “A Fast File System for BSD". ACM Transactions on
`Computer Systems, Vol. 2(3). 1984]. the Log-based File Sys-
`teln [Rosenblum and Ousterhout, “The Design and Imple—
`mentation of a Log-structured File System”, ACM Transac-
`tions on Computer Systems, Vol. 10(1), 1992], etc. In a
`typical cache arrangement. a requestor requests data froln
`solne memory. device or the like and the results are provided
`to the requestor and stored ina cache having a faster response
`time than the original device supplying the data. Then, when
`the requestor requests that data again, ifit is still in the cache,
`the cache can return the data in response to the request before
`the original device could have retumed it and the request is
`satisfied that much sooner.
`Caching has its difficulties, one of which is that the data
`might change at the source and the cache would then be
`supplying “stale" data to the requestor. This is the “cache
`consistency" problem. Because ofthis, caches are often “read
`only” requiring that changes to data be transmitted through
`the cache back to the source in a “write-through” fashion.
`
`RIV—1005 - Page 15 of 29
`
`

`

`US 8,069,225 82
`
`7
`Another problem with caching is that the original source of
`the data might want to track usage of data and would not be
`aware of uses that were served from the cache as opposed to
`from the original source. For example, where a Web server is
`remote from a number of computers running Web browsers
`that are “pointed to“ that Web server, the Web browsers might
`cache Web pages from that site as they are viewed. to avoid
`delays that might occur in downloading the Web page again.
`While this would improve performance in many cases, and
`reduce the load on the Web server, the Web server operator
`might try to track the total number of “page views” but would
`be ignorant of those served by the cache. In some cases, an
`Internet service provider might operate the cache remote
`from the browsers and provide cached content for a large
`number of browsers, so a Web server operator might even
`miss unique users entirely.
`Where loose consistency can be tolerated, caching can
`work remarkably well. For example, the Domain Name Sys-
`tem (DNS )_. dating back to the early 1980’s, employs caching
`extensively to pr