(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0088376 A1
`McCanne et al.
`(43) Pub. Date:
`May 6, 2004
`
`US 20040088376A1
`
`(54)
`
`(75)
`
`TRANSACTION ACCELERATOR FOR
`CLIENT-SERVER COMMUNICATION
`SYSTEMS
`
`Inventors: Steven McCanne, Berkeley, CA (US);
`Michael J. Demmer, San Francisco,
`CA (US)
`
`Correspondence Address:
`TOWNSEND AND TOWNSEND AND CREW,
`LLP
`TWO EMBARCADERO CENTER
`EIGHTH FLOOR
`
`SAN FRANCISCO, CA 94111-3834 (US)
`
`(73)
`
`Assignee: NBT Technology, Inc., San Francisco,
`CA
`
`(21)
`
`Appl. No.:
`
`10/285,315
`
`(22)
`
`Filed:
`
`Oct. 30, 2002
`
`Publication Classification
`
`(51)
`(52)
`
`Int. Cl.7 ................................................... .. G06F 15/16
`U.S. Cl.
`.......................................... .. 709/219; 709/203
`
`ABSTRACT
`(57)
`In a network having transaction acceleration, for an accel-
`erated transaction, a client directs a request to a client-side
`transaction handler that forwards the request to a server-side
`transaction handler, which in turn provides the request, or a
`representation thereof,
`to a server for responding to the
`request. The server sends the response to the server-side
`transaction handler, which forwards the response to the
`client-side transaction handler, which in turn provides the
`response to the client. Transactions are accelerated by the
`transaction handlers by storing segments of data used in the
`transactions in persistent segment storage accessible to the
`server-side transaction handler and in persistent segment
`storage accessible to the client-side transaction handler.
`When data is to be sent between the transaction handlers, the
`sending transaction handler compares the segments of the
`data to be sent with segments stored in its persistent segment
`storage and replaces segments of data with references to
`entries in its persistent segment storage that match or closely
`match the segments of data to be replaced. The receiving
`transaction store reconstructs the data sent by replacing
`segment references with corresponding segment data from
`its persistent segment storage, requesting missing segments
`from the sender as needed. The transaction accelerators
`
`could handle multiple clients and/or multiple servers and the
`segments stored in the persistent segment stores can relate to
`different transactions, different clients and/or different serv-
`ers. Persistent segment stores can be prepopulated with
`segment data from other transaction accelerators.
`
`:57
`
`C;.~\..~umcAfi'\N(,
`P0.ILCSStS
`
`RIV-1003 - Page 1 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 1 of 11
`
`US 2004/0088376 A1
`
`‘mu~..mudQ\,I«.m@
`
`M7QL.v.¢.w}.}~\..\.
`
`JE¢&u3m3+\
`itQ.
`
`\.._
`
`SnimmN.
`..noNN3£vE.z5:.J.M\@
`
`nL-1um__JU
`
`{VSQ
`
`RIV-1003 - Page 2 of 29
`
`
`

`
`Patent Application Publication May 6, 2004 Sheet 2 of 11
`
`US 2004/0088376 A1
`
`km
`3;‘?Q
`
`(\\
`:35’
`
`KL?
`
`i 1 Z 3 1
`
`‘;
`if
`H
`
`0;;
`nil
`$53
`
`RIV-1003 - Page 3 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 3 of 11
`
`US 2004/0088376 A1
`
`T\M€ Shae in
`
`
`
`lH‘7—-
`
`"'
`
`W
`
`r~’
`
`”\
`
`LL[_
`
`P
`
`gnaw-M‘\‘$
`~QuCcALF ff: aACDAflA (J8/+1
`‘
`/Y
`( Fefiajovxcrzs; ‘HamsM‘,He<£
`b\v\d\v‘\3S,
`€ncA&A3
`0«~"-oC- bag
`C25-'cL«a\
`Cg-/| kg‘
`‘"4: I M150-“
`‘gjmmkrs
`'ffilifrzab
`
`Fla.
`
`5‘
`
`RIV-1003 - Page 4 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 4 of 11
`
`US 2004/0088376 A1
`
`19°
`
`RIV-1003 - Page 5 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 5 of 11
`
`US 2004/0088376 A1
`
`F1677
`
`RIV-1003 - Page 6 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 6 of 11
`
`US 2004/0088376 A1
`
`P
`
`2'5‘UL-TE2!!)
`
`pS9"loC.or4’N.c\.L.c'Y_ I(e
`
`¢0
`
`$0
`
`RIV-1003 - Page 7 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 7 of 11
`
`US 2004/0088376 A1
`
`@E30
`
`iQ.
`
`RIV-1003 - Page 8 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 8 of 11
`
`US 2004/0088376 A1
`
`Flaw
`
`C¢.~\..;wmcAfi'\N(.
`IORJLCSSES
`
`RIV-1003 - Page 9 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 9 of 11
`
`US 2004/0088376 A1
`
`RIV-1003 - Page 10 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 10 of 11
`
`US 2004/0088376 A1
`
`s°‘f
`
`
`
`CT“ "4'
`$5
`
`?
`
`‘
`
`/J
`
`L/3
`
`‘NAM L
`5'08
`
`Wk
`
`;m(2)
`
`Cuaefir
`
`99%
`
`(,JA.J
`
`
`
`.~/-«¢.LL(
`
`RIV-1003 - Page 11 of 29
`
`

`
`Patent Application Publication May 6, 2004 Sheet 11 of 11
`
`US 2004/0088376 A1
`
`€\Q_M5
`
`RIV-1003 - Page 12 of 29
`
`

`
`US 2004/0088376 A1
`
`May 6, 2004
`
`TRANSACTION ACCELERATOR FOR
`CLIENT-SERVER COMMUNICATION SYSTEMS
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`entitled
`[0001] U.S. patent application Ser. No. 10/
`“Content-Based Segmentation Scheme for Data Compres-
`sion in Storage and Transmission Including Hierarchical
`Segment Representation”[Attorney Docket No: 021647-
`000200US] (hereinafter “McCanne II”) was filed of even
`date with this application and is incorporated by reference
`herein for all purposes.
`
`BACKGROUND OF THE INVENTION
`
`[0002] The present invention relates generally to systems
`for moving data through limited bandwidth channels efli-
`ciently and more particularly to having data available in
`response to a request for data over a limited channel faster
`than if the data were sent unprocessed in response to the
`request.
`
`[0003] Many applications and systems that operate well
`over high-speed connections need to be adapted to run on
`slower speed connections. For example, operating a file
`system over a local area network (LAN) works well, but
`often files need to be accessed where a high-speed link, such
`as a LAN, is not available along the entire path from the
`client needing access to the file and the file server serving the
`file. Similar design problems exist for other network ser-
`vices, such as e-mail services, computational services, mul-
`timedia, video conferencing, database querying, office col-
`laboration, etc.
`
`In a networked file system, for example, files used
`[0004]
`by applications in one place might be stored in another
`place. In a typical scenario, a number of users operating at
`computers networked throughout an organization and/or a
`geographic region share a file or sets of files that are stored
`in a file system. The file system might be near one of the
`users, but typically it is remote from most of the users, but
`the users often expect the files to appear to be near their sites.
`
`[0005] As used herein, “client” generally refers to a com-
`puter, computing device, peripheral, electronics, or the like,
`that makes a request for data or an action, while “server”
`generally refers to a computer, computing device, periph-
`eral, electronics, or the like, that operates in response to
`requests for data or action made by one or more clients.
`
`[0006] A request can be for operation of the computer,
`computing device, peripheral, electronics, or the like, and/or
`for an application being executed or controlled by the client.
`One example is a computer running a word processing
`program that needs a document stored externally to the
`computer and uses a network file system client to make a
`request over a network to a file server. Another example is
`a request for an action directed at a server that
`itself
`performs the action, such as a print server, a processing
`server, a control server, an equipment interface server, and
`I/O (input/output) server, etc.
`
`[0007] A request is often satisfied by a response message
`supplying the data requested or performing the action
`requested, or a response message indicating an inability to
`service the request, such as an error message or an alert to
`a monitoring system of a failed or improper request. Aserver
`
`might also block a request, forward a request, transform a
`request, or the like, and then respond to the request or not
`respond to the request.
`
`In some instances, an object normally thought of as
`[0008]
`a server can act as a client and make requests and an object
`normally thought of as a client can act as a server and
`respond to requests. Furthermore, a single object might be
`both a server and a client, for other servers/clients or for
`itself. For example, a desktop computer might be running a
`database client and a user interface for the database client.
`
`If the desktop computer user manipulated the database client
`to cause it to make a request for data, the database client
`would issue a request, presumably to a database server. If the
`database server were running on the same desktop computer,
`the desktop computer would be, in effect, making a request
`to itself. It should be understood that, as used herein, clients
`and servers are often distinct and separated by a network,
`physical distance, security measures and other barriers, but
`those are not required characteristics of clients and servers.
`
`In some cases, clients and servers are not neces-
`[0009]
`sarily exclusive. For example, in a peer-to-peer network, one
`peer might a request of another peer but might also serve
`responses to that peer. Therefore, it should be understood
`that while the terms “client” and “server” are typically used
`herein as the actors making “requests” and providing
`“responses”, respectively,
`those elements might
`take on
`other roles not clearly delineated by the client-server para-
`digm.
`
`[0010] Generally, a request-response cycle can be referred
`to as a “transaction” and for a given transaction, some object
`(physical,
`logical and/or virtual) can be said to be the
`“client” for that transaction and some other object (physical,
`logical and/or virtual) can be said to be the “server” for that
`transaction.
`
`flow directly
`transactions
`[0011] Often client-server
`between the client and the server across a packet network,
`but in some environments these transactions can be inter-
`
`cepted and forwarded through transport-level or application-
`level devices called “proxies”. In this case, a proxy is the
`terminus for the client connection and initiates another
`connection to the server on behalf of the client. Alterna-
`
`tively, the proxy connects to one or more other proxies that
`in turn 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.
`
`[0012] As used herein, the terms “near”, “far”, “local” and
`“remote” might refer to physical distance, but more typically
`they refer
`to effective distance. The effective distance
`between two computers, computing devices, servers, clients,
`peripherals, etc. is, at least approximately, a measure of the
`difficulty of getting data between the two computers. For
`example, where file data is stored on a hard drive connected
`directly to a computer processor using that file data, and the
`connection is through a dedicated high-speed bus, the hard
`drive and the computer processor are effectively “near” each
`other, but where the traffic between the hard drive and the
`computer processor is over a slow bus, with more interven-
`
`RIV-1003 - Page 13 of 29
`
`

`
`US 2004/0088376 A1
`
`May 6, 2004
`
`ing events possible to waylay the data, the hard drive and the
`computer processor are said to be farther apart.
`
`[0013] Greater and lesser physical distances need not
`correspond with greater and lesser effective distances. For
`example, a file server and a desktop computer separated by
`miles of high-quality and high-bandwidth fiber optics might
`have a smaller effective distance compared with a file server
`and a desktop computer separated by a few feet and coupled
`via a wireless connection in a noisy environment.
`
`In general, where the effective distances are great,
`[0014]
`more effort is needed to create the impression of a shorter
`effective distance. Much has been developed to create this
`impression. For example, when the effective distance is
`increased due to limited bandwidth, that limitation can be
`ameliorated using compression or by caching. Compression
`is a process of representing a number of bits of data using
`fewer bits and doing so in a way that the original bits or at
`least a sufficient approximation of the original bits can be
`recovered from an inverse of the compression process in
`most cases. Caching is the process 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.
`
`[0015] Compression allows for more efficient use of a
`limited bandwidth and might result in less latency, but in
`some cases, no latency improvement occurs. Latency, with
`respect to client-server transactions,
`is a measure of the
`delay between when a request for data is made and the
`requested data is received.
`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
`if the 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.
`
`[0016] Caching also provides some help in reducing effec-
`tive distance, but in some 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.
`In a typical cache arrangement, a requestor requests data
`from some memory, device or the like and the results are
`provided to the requestor and stored in a cache having a
`faster response time than the original device supplying the
`data. Then, when the requestor requests that data again, if it
`is still in the cache, the cache can return the data in response
`to the request before the original device could have returned
`it and the request is satisfied that much sooner.
`
`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.
`
`[0018] Additionally, the mechanism underlying Web cach-
`ing provides only a loose model for consistency between the
`origin data and the cached data. Generally, Web data is
`cached for a period of time based on heuristics or hints in the
`transactions independent of changes to the origin data. This
`means that cached Web data can occasionally become incon-
`sistent with the origin server and such inconsistencies are
`simply tolerated by Web site operators, service providers,
`and users as a reasonable performance trade-off. Unfortu-
`nately, this model of loose consistency is entirely inappro-
`priate for general client-server communication like net-
`worked file systems. When a client interacts with a file
`server, the consistency model must be wholly correct and
`accurate to ensure proper operation of the application using
`the file system.
`
`[0019] Some solutions to network responsiveness deal
`with the problem at the file system or at network layers. One
`proposed solution is the use of a low-bandwidth network file
`system, such as that described in Muthitacharoen, A., et al.,
`“A Law-Bandwidth Network File System”, in Proceedings of
`the 18th ACM Symposium on Operating Systems Principles
`(SOSP ’01), pp. 174-187 (Chateau Lake Louise, Banff,
`Canada, October 2001) (in Vol. 35, 5 of ACM SIGOPS
`Operating Systems Review, ACM Press). In that system,
`called LBFS, clients employ “whole file” caching whereby
`upon a file open operation, the client fetches all the data in
`the file from the server, then operates on the locally cached
`copy of the file data. If the client makes changes to the file,
`those changes are propagated back to the server when the
`client closes the file. To optimize these transfers, LBFS
`replaces pieces of the file with hashes, and the recipient uses
`the hashes in conjunction with a local file store to resolve the
`hashes to the original portions of the file. Such systems have
`limitations in that they are tied to file systems and generally
`require modification of the clients and servers between
`which responsiveness is to be improved. Furthermore, the
`hashing scheme operates over blocks of relatively large
`(average) size, which works poorly when files are subject to
`fine-grained changes over time. Finally, LBFS is by design
`intimately tied to a network file system protocol. It is not
`able to optimize or accelerate other types of client-server
`transactions, e.g., e-mail, Web, streaming media, and so
`forth.
`
`[0017] 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 requester. This is the “cache
`consistency” problem. 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
`
`[0020] Another proposed solution is suggested by Spring,
`N., et al., “A Protocol-Independent Technique for Eliminat-
`ing Redundant Network Traffic”, in Proceedings of ACM
`SIGCOMM (August 2000). As described in that reference,
`network packets that are similar to recently transmitted
`packets can be reduced in size by identifying repeated
`strings and replacing the repeated strings with tokens to be
`resolved from a shared packet cache at either end of a
`network link. This approach, while beneficial, has a number
`of shortcomings. Because it operates solely on individual
`
`RIV-1003 - Page 14 of 29
`
`

`
`US 2004/0088376 A1
`
`May 6, 2004
`
`packets, the performance gains that accrue are limited by the
`ratio of the packet payload size to the packet header (since
`the packet header is generally not compressible using the
`described technique). Also, because the mechanism is imple-
`mented at the packet level, it only applies to regions of the
`network where two ends of a communicating path have been
`configured with the device. This configuration can be diffi-
`cult to achieve, and may be impractical in certain environ-
`ments. Also, by caching network packets using a relatively
`small memory-based cache with a first-in first-out replace-
`ment policy (without the aid of, for instance, a large disk-
`based backing store), the efficacy of the approach is limited
`to detecting and exploiting communication redundancies
`that are fairly localized in time. Finally, because this
`approach has no ties into the applications or servers that
`generate the (redundant) network traffic, there is no ability to
`anticipate where data might be used and pre-stage that data
`in the far-end cache providing potential further acceleration
`and optimization of network traffic.
`
`In a business that spans operations over wide area
`[0021]
`networks, a number of less than ideal patches have been
`done in response to the problems described above. For
`example, some businesses resort to buying more and more
`bandwidth to keep responsiveness up. Individuals in the
`organization will attempt local solutions by turning to ad hoc
`e-mail collaboration (which might make one file more
`readily accessible by one user, but adds version control
`problems and adds to the overall network load). Other
`attempts to solve the problem might
`involve manually
`creating copies of data to operate on or pushing read-only
`replicas to remote servers.
`
`In view of the above problems and the limitations
`[0022]
`with existing solutions, improvements can be made in how
`data is transported for transactions over a network.
`
`BRIEF SUMMARY OF THE INVENTION
`
`In embodiments of a network having transaction
`[0023]
`acceleration, for an accelerated transaction, a client directs a
`request to a client-side transaction handler that forwards the
`request to a server-side transaction handler, which in turn
`provides the request, or a representation thereof, to a server
`for responding to the request. The server sends the response
`to the server-side transaction handler, which forwards the
`response to the client-side transaction handler, which in turn
`provides the response to the client. Transactions are accel-
`erated by the transaction handlers by storing segments of
`data used in the transactions in persistent segment storage
`accessible to the server-side transaction handler and in
`
`persistent segment storage accessible to the client-side trans-
`action handler. When data is to be sent between the trans-
`
`action handlers, the sending transaction handler compares
`the segments of the data to be sent with segments stored in
`its persistent segment storage and replaces segments of data
`with references to entries in its persistent segment storage
`that match or closely match the segments of data to be
`replaced. The data to be sent might be sent from a client to
`a server, from a server to a client, from a peer to a peer, etc.
`The receiving transaction store then reconstructs the data
`sent by replacing the segment references with corresponding
`segment data from its persistent segment storage. If seg-
`ments are referred to but do not exist in the receiver’s
`
`persistent segment store, the receiver can issue requests for
`the missing segments from the sender via a side channel or
`
`via the link used to send the references to the segments.
`Where the persistent segment storage at each end is popu-
`lated with segments likely to be repeated, such replacement
`of segments will occur often, resulting in much less band-
`width use over the network, thus accelerating transactions.
`
`[0024] The transaction accelerators could be dedicated,
`such that the client-side transaction accelerator interacts
`
`with only one client and the server-side transaction accel-
`erator interacts with only one server, but the transaction
`accelerators might also handle more than one client and/or
`more than one server. Where multiple transactions are
`handled, either for the same clients and servers, or over
`possibly different clients and possibly different servers, the
`segments stored in the persistent segment stores can relate to
`different transactions, different clients and/or different serv-
`ers. For example, if a transaction accelerator encounters a
`segment of data and stores it in its persistent segment store
`in handling a given transaction, a reference to that segment
`of data might be used again in a different
`transaction,
`relating to a different client or the same client and a different
`server or the same server, or relating to an entirely different
`client-server application.
`
`transaction accelerators’
`In some embodiments,
`[0025]
`persistent segment stores are pre-populated with segment
`data from other transaction accelerators, so that when a
`transaction occurs, more segments are available at the sender
`end for replacement with references and more segments are
`available at the receiving end for reconstruction from the
`references.
`
`[0026] Other features and advantages of the invention will
`be apparent in view of the following detailed description and
`preferred embodiments.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0027] FIG. 1 is a block diagram of a networked client-
`server system according to embodiments of the present
`invention.
`
`[0028] FIG. 2 is a block diagram of the system of FIG. 1,
`showing a client-side transaction accelerator (“CT ”) and a
`server-side transaction accelerator (“STA”) in greater detail
`and, for space considerations, showing less detail of the
`overall system.
`
`[0029] FIG. 3 is an illustration of data organization in
`embodiments of a persistent segment store (“PSS”) as might
`be used with the system shown in FIG. 1.
`
`[0030] FIG. 4 is a block diagram of an encoder as might
`be used in the transaction transformers (“TT”) of FIG. 2.
`
`[0031] FIG. 5 is a block diagram of a decoder as might be
`used in the inverse transaction transformers (“TT-1”) of
`FIG. 2.
`
`[0032] FIG. 6 is an illustration of an encoding process
`wherein input data is segmented and represented by refer-
`ences to data segments.
`
`[0033] FIG. 7 is a flowchart illustrating a process for
`decoding data as might be output by the encoder of FIG. 4.
`
`[0034] FIG. 8 is a block diagram of a networked system
`wherein transaction acceleration is implemented and uses a
`proactive segment distributor (“PSD”).
`
`RIV-1003 - Page 15 of 29
`
`

`
`US 2004/0088376 A1
`
`May 6, 2004
`
`[0035] FIG. 9 is a block diagram of a networked peer-to-
`peer system according to embodiments of the present inven-
`tion.
`
`[0036] FIG. 10 is a block diagram of a networked system
`wherein transaction acceleration is implemented and the
`client-side transaction accelerator is integrated in with the
`client.
`
`[0037] FIG. 11 is a block diagram of a networked system
`wherein transaction acceleration is implemented and the
`server-side transaction accelerator is integrated in with the
`server.
`
`[0038] FIG. 12 is a block diagram of a networked system
`wherein transaction acceleration is implemented and a PSS
`is shared among a plurality of transaction accelerators.
`
`[0039] FIG. 13 is a block diagram showing a multicast
`implementation of the system of FIG. 12, wherein multicast
`communications are used for updating and reading a shared
`PSS.
`
`[0040] FIG. 14 is a block diagram showing a multicast
`implementation of a plurality of clients coupled locally
`through a LAN and to a WAN.
`
`[0041] FIG. 15 is a block diagram of a networked system
`wherein transaction acceleration is implemented and the
`network handles a variety of protocols and services.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`[0042] The present invention has many applications, as
`will be apparent after reading this disclosure. In describing
`an embodiment of a transaction acceleration system accord-
`ing to the present invention, only a few of the possible
`variations are described. Other applications and variations
`will be apparent to one of ordinary skill in the art, so the
`invention should not be construed as narrowly as the
`examples, but rather in accordance with the appended
`claims.
`
`[0043] Atransaction, as the term is used herein, is a logical
`set of steps that result in data moving from one place to
`another. In some cases, the data being moved exists at its
`origin independent of the transaction, such as a file read
`transaction where the file exists on the disk of the server. In
`
`other cases, the data is generated for the transaction at the
`origin, such as in response to a request for computation,
`lookup, etc. Typically, the computer, computer device, etc.
`initiating the transaction is referred to as the “client” and the
`computer, computer device, etc. that responds, or is expected
`to respond, is referred to as the “server”. Data can flow in
`either direction. For example, a file system client might
`initiate a transaction by requesting a file read. The corre-
`sponding data will be returned from the server responding to
`the request, so in that case, the bulk of the data flows from
`the server to the client. However, where a client initiates a
`file write transaction, the bulk of the data flows from the
`client to the server, either as part of the initial request or as
`subsequent messages. Atransaction can be in multiple parts,
`but in a simple transaction, a client sends a request (data, a
`message, a signal, etc., explicitly being the request or
`indicative of or representing of the request) to a server and
`the server responds with a response (data, a message, a
`signal, etc., explicitly being the response or indicative of or
`
`representing of the response) to the client. More complex
`transactions, for example, might
`involve some back and
`forth, as might be needed for a server to clarify a request,
`verify the authority of the client to receive a response to the
`request, get additional information needed for preparing the
`response, etc.
`
`a connection
`the typical example of
`[0044] Herein,
`between a client and a server is a packet network, but other
`connection means can also be used, such as a point-to-point
`wired or wireless channel. These elements will be general-
`ized and referred to here as “nodes” with a channel assumed
`for communication between the nodes.
`
`[0045] Atransaction might begin with a client at one node
`making a request for file data directed to a server at another
`node, followed by a delivery of a response containing the
`requested file data. Other transactions might be a request for
`a specific part of a file, all the file, all or some of another data
`construct, or a transaction might relate to data flowing from
`the requester or relate to a command. Examples of transac-
`tions include “read a bloc ”, “read a file”, “read a stream”,
`:7
`44
`“write a block with this data” (an example of data flowing
`from the requestor), “open a file , perform a calculation on
`this data”, “get an e-mail with these characteristics”, “send
`an e-mail”, “check for new emails”, “list directory contents”,
`etc.
`
`[0046] Some transactions might involve large amounts of
`data flowing in one direction or both directions. Some
`transactions might even involve interactions having more
`than one requestor and/or more than one receiver. For clarity
`of description, these many transaction types are described in
`terms of a typical simple transaction, where one client makes
`a request of one server and that one server responds to the
`request in a manner expected by the client. However, upon
`reading this disclosure, a person of ordinary skill will be able
`to apply these concepts to one-to-many and many-to-many
`transactions between client(s) and server(s) or more gener-
`ally between two nodes. Where data flow is described in one
`direction, it should be understood that data might flow in the
`other direction and/or information might flow in only one
`direction, but data and/or signals flow in both directions to
`accomplish the movement of information.
`
`[0047] Using some of the systems described herein, client
`access to a server (and vice versa where needed), can be
`“tunneled” through transaction accelerators that map trans-
`actions onto sequences of variable-length segments with
`content-induced segment cut points. The segments can be
`stored at various places, typically within high-speed access
`of both the clients and the servers, with the segments stored
`using a scalable, persistent naming system. The segments
`can be decoupled from file-system and other system data
`blocks and structures, so that a matching segment might be
`found in multiple contexts. Instead of caching files, blocks,
`or other system dependent constructs, segments can be
`stored and bound to references that are used to represent the
`segment contents.
`
`[0048] FIG. 1 is a block diagram of a networked client-
`server system 10 according to embodiments of the present
`invention, where such transactions might occur. As shown
`there, clients 12 are coupled to servers 14 over a network 16,
`via client-side transaction accelerators (“CTA’s”) 20 and
`server-side transaction accelerators (“STA’s”) 22. Where the
`location of a transaction accelerator is not specific, it is
`
`RIV-1003 - Page 16 of 29
`
`

`
`US 2004/0088376 A1
`
`May 6, 2004
`
`referred to herein as a “TA”, indicating that it could be
`referring to a client-side transaction accelerator, a server-
`side transaction accelerator, a peer transaction accelerator, or
`possibly even a transaction accelerator that is used by clients
`and servers (and possibly also peers).
`
`[0049] Although not shown in FIG. 1, additional paths
`between clients and servers (also possibly between clients
`and clients and between servers and servers) might be
`present and bypass the TA’s. Such additional paths could be
`used to carry conventional traffic, such as transactions that
`are not likely to benefit from transaction acceleration. By
`routing such transactions around the TA’s, the state of the
`TA’s can remain focused on the accelerated transaction, for
`example, by not having the persistent segment storage
`(described below) of a TA storing segments from transac-
`tions not likely to benefit from transaction acceleration.
`
`[0050] As shown, a CTA 20 might serve one or more
`clients and multiple CTA’s 20 might be implemented on a
`network. As used herein and unless otherwise indicated, the
`index “n” refers to