Abstract:
Many documents transmitted in a network environment contain substantial overlap with old versions of the same (or related) documents. For example, a “current news” web page may be updated hourly on a web site so that a new story is added and the oldest story is dropped. In such cases, it is inefficient to send the updated document in its entirety to a user requesting the new document but who had previously received the old web page. Instead, the new web document is first sent to a condenser, which replaces the unchanged portions of the new document with pointers to the old document. In this way, only the changed portions of the document need be transmitted to the user in their entirety. The condensed document is bound to the requesting user via a token such as a cookie generated by the condenser, and the condensed document and cookie are sent to the user. The user uses assembly software corresponding to the condensing process to reassemble the new document from the condensed document and the old document. The foregoing may be implemented on an individual user basis, as well as for classes of users.

Description:
FIELD OF THE INVENTION 
   The present invention teaches a method and apparatus for accelerating the delivery of content and reducing congestion in a networked environment. In particular, the present invention exploits the correlation between subsequent documents downloaded by one or more users. 
   BACKGROUND OF THE INVENTION 
   Consider a user who views a Web page at a news site at 10:00 a.m., and then visits it again at 11:00 a.m. Although there are some updates during this time, the Web page at 11:00 a.m. is largely the same as it is at 10:00 a.m. However, despite the common content between the pages at 11:00 a.m. and 10:00 a.m., in current implementations, the user&#39;s computer  100  downloads the entire page from the news site both times. This results in the inefficient utilization of network bandwidth between the user and the news site, creating network congestion and long download times. 
   The above situation is compounded by the fact that users often view the same page at the same site several times a day. To improve this situation, Internet Service Providers (ISPs) often deploy cache servers at various points in the network for storing frequently accessed content. For example, America Online (AOL) currently utilizes Inktomi&#39;s Traffic Server, a network caching platform, to speed up Web access for its users. When a user requests a Web page, the request is routed to the closet cache server in the network. If the requested Web page is located in the cache and is current, then the cache server delivers the page directly to the user without the need to access the Web server. By eliminating redundant network traffic between the cache server and the Web server, the cache server accelerates the delivery of content. 
   However, these cache servers suffer several limitations. First, cache servers do not reduce network delays between the cache server and the user. Additionally, cache servers are designed to exploit spatial correlation among multiple users. That is, a cache server is most effective when its contents are accessed by many users. As such, cache servers are not designed for and do not have the capacity to handle personalized content that is unique to every user. Finally, a cache server is only effective as long as its content remains current. Thus, cache servers cannot handle dynamically generated content that changes with time. It is not efficient to cache dynamically generated content since, by definition, such content will change upon subsequent retrievals. 
   The user&#39;s Web browser also employs a local cache for content that is repeatedly loaded in unchanged form into the browser. For example, browsers often cache image files, such as customized buttons, that make up part of a Web page. Both browser caches and network caches maintain the validity of their cached objects using hash and time-stamp verification. Specifically, when a cache receives a request for a cached object, the cache may verify the validity of the object by transmitting a binary time stamp of the cached object to the content server. The content server compares the transmitted value to that of its corresponding object. If the two values are equal, the content server signals the browser to load its own cached copy. If the two values are different, the content server sends a fresh copy of the object to the cache. Since transmission of a binary time-stamp of an object consumes significantly less bandwidth than transmission of the entire object, caches reduce network traffic between the cache and the content server. However, neither local caches nor cache servers can provide an adequate solution for access to the dynamically generated content that is so pervasive on modern networks. 
   Another technique to reduce network congestion is data compression. Files embedded in Web pages may be compressed using a data compression algorithm. For example, text files may be compressed using the Lempel-Ziv encoding algorithm, image files may be compressed using JPEG encoding, and digital audio and video files may be compressed using MPEG encoding. By transmitting files through the network in compressed form and decompressing them upon receipt by the user&#39;s browser, network bandwidth is efficiently utilized. Unfortunately, data compression as presently implemented only exploits the redundancies within a single web item, but not across multiple items that may be variations of the same item over time, or otherwise related to each other. 
   While data compression algorithms may not exploit redundancies between files, certain such algorithms do teach exploitation of redundancies between similar portions (for example, video frames or audio blocks) within a file. These compression algorithms use a variety of different techniques to exploit correlation within and across frames (or blocks) in order to reduce the number of bits required to represent an entire sequence of such frames. For example, in video compression, a predetermined sequence of video is decomposed into a series of frames, each frame comprising a still image. Digital audio is similarly processed, by breaking up the sequence into a series of blocks, each of which represents a predetermined time interval. The sequences must be predetermined because each frame is compressed by using information from its preceding or subsequent frames. These compression algorithms require frames to be reconstructed in the same order by all users. For this reason, such data compression algorithms cannot apply to the network situation where different users may demand different documents over randomly chosen time intervals and in random order. 
   Therefore, as discussed, caches do not offer an adequate solution to the problem of accelerating the delivery of dynamically generated and personalized content in a networked environment. Furthermore, data compression teachings for exploiting redundancies between frames or blocks in a single file do not apply well to exploiting redundancies between randomly accessed but similar (e.g. dynamically generated) files in a network. Thus, there remains a need for accelerating the delivery of content in a networked environment. 
   SUMMARY 
   The present invention allows for accelerating the delivery of content in a networked environment by storing a history of a sequence of documents and comparing the latest document in the sequence with the previous document(s) to enable the exploitation of correlation across these documents. However, as discussed earlier, unlike the prior art data compression solutions, the sequence of documents in the present invention need not be predetermined. Furthermore, unlike the prior art caching solutions, the present invention can handle documents that are dynamically generated. That is, caches are only effective when their content is current. Thus, caches cannot handle content that continually changes upon subsequent requests and is generated dynamically and personalized for each user. Examples of dynamically generated, personalized, and continually changing content are stock quotes, account information, personalized news feeds, etc. The benefits provided by the present invention include a substantial reduction in bandwidth usage, and/or a corresponding speed-up in the download performance of condensed documents for the user. 
   More particularly, various aspects of the present invention generate and transmit condensed documents that may be reconstructed (perhaps even automatically) upon reception by a user. Transmission of such condensed documents requires reduced use of network bandwidth, thereby freeing up bandwidth for other transmissions. Thus, an exemplary embodiment of the invention is directed to a so-called “condenser” disposed between a server and a user. The condenser receives a request for a first document from a user, receives the document from a content server, and binds the document to the user. Binding the document to the user may involve assigning and sending a token, such as a cookie, to the user, binding a copy of the token to the document, and then storing copies of the token and the document. The condenser then forwards the document to a memory accessible to the user. Such a memory may be a local user cache or a local network cache shared by a class of users. Later, the condenser receives a request for a second document from the user, receives the second document from the content server, retrieves the stored first document, and creates a condensed document by abbreviating redundant information in the second document relative to the first document. The condenser then transmits the condensed document to the user, who has access to corresponding software for reconstructing the second document using the first document. Such corresponding software may be included as a self-unwrapping program that is included in the transmission of the first or second document to the user. Such programs may be coded in languages such as Javascript, Java, Vbscript or other languages readily executed by popular content browsers. 
   In another aspect of the invention, the user is able to reassemble the second document using the condensed document and the first document. The user receives the condensed document and retrieves the first document from a locally accessible memory. As mentioned earlier, such a memory may be a local user cache or a network cache shared by a class of users. The user then uses assembly software corresponding to the condenser software to identify one or more reference(s) in the condensed document corresponding to sequence(s) in the first document, and to replace the reference(s) in the condensed document with the corresponding sequence(s) from the first document. Such assembly software may be transmitted from the condenser to the user&#39;s computer as a self-unwrapping program. 

   
     BRIEF DESCRIPTION OF THE FIGURES 
       FIG. 1  is a block diagram illustrating an exemplary computer system for accelerating the delivery of content in a networked environment. 
       FIG. 2A  is a flow chart illustrating an exemplary method from the perspective of the condenser. 
       FIG. 2B  is a flow chart illustrating an exemplary method from the perspective of the user&#39;s computer. 
       FIG. 3  is a flow chart illustrating an exemplary method for the condensation process. 
       FIG. 4  is a flow chart illustrating an exemplary method for the assembly process. 
       FIG. 5  is a block diagram illustrating an exemplary computer system for accelerating the delivery of content in a networked environment involving text documents. 
   

   DETAILED DESCRIPTION 
     FIG. 1  is a block diagram illustrating an exemplary computer system for accelerating the delivery of content in a networked environment. For convenience, the invention will be described herein with respect to “documents,” which should be understood to include any content-bearing items transmitted in a networked environment, including, without limitation, files, images, objects, programs, scripts, and other kinds of documents. 
   The system contemplates a network of computers and software running thereon including a user&#39;s computer  100 , a condenser  200 , and a content server  300 . The user&#39;s computer  100  further includes a content browser  110  and an assembly module  120 . The assembly module  120  may be implemented in many ways. In an exemplary embodiment, the condenser  200  ships the assembly module  120  as a self-unwrapping Javascript program to the user&#39;s computer  100  during an initial interaction between the condenser  200  and the user&#39;s computer  100 . In alternate embodiments, the assembly module  200  may be implemented, without limitation, as preinstalled programs or “browser plug-ins,” or with platform independent languages such as Java or scripting languages such as Javascript that are downloaded and executed on the fly. In this exemplary embodiment, the network is deployed over the Internet, although those skilled in the art will recognize that any public or private communication network including, without limitation, extranets, intranets, wireless networks and other telephonic or radio communications networks could also be used. Similarly, as used herein, the term computer refers to any device that processes information with an integrated circuit chip, including without limitation, mainframe computers, work stations, servers, desktop computers, portable computers, embedded computers, and hand-held computers. 
   In an exemplary embodiment of the invention, the condenser  200  may be operated by the same content provider that operates the content server or by a third party. The condenser  200  is configured transparently, as if it were a router so that all content to a content server  100  is directed through the condenser  200 . Such a transparent configuration does not require manual configuration of the content browser  110  to direct traffic to the condenser  200 . Those skilled in the art will recognize that nontransparent configurations, where manual configuration of the content browser  110  is necessary, may also be implemented in alternate embodiments. Additionally, this exemplary embodiment implements the condenser  200  as software running on a computer separate from any cache or content servers in the network. An exemplary embodiment situates the condenser  200  near content servers that may dynamically generate content such that network traffic between the condenser  200  and the user is minimized over a maximum length of network. Such a condenser  200  can serve multiple users by maintaining historic information about the pages most frequently requested by each user. However, those skilled in the art will recognize that the condenser  200  may be integrated into any cache or content server in the network. Those skilled in the art will also recognize that the condenser  200  may be also be implemented as various combination of software and/or hardware and integrated into lower level network connectivity devices, such as routers or switches. 
   Requesting and Retrieving Content 
   The process of requesting and receiving content, involving interactions among the content server, the condenser, and the user&#39;s computer, will now be described with reference to  FIG. 2A  (from the condenser&#39;s perspective) and  FIG. 2B  (from the user&#39;s perspective). 
   When a user&#39;s computer  100  initially requests a Web document from a content server  300  ( FIG. 2B , step  2 B 10 ), the request is transparently transmitted to the condenser  200  ( FIG. 2A , step  2 A 10 ) which recognizes that the request is the user&#39;s first request for such a Web document. The condenser  200  forwards the request to a content server  300  ( FIG. 2A , step  2 A 20 ), which may be the Web server itself or an associated cache server. Upon receiving the request, the content server  300  generates or retrieves the Web page and sends it back to the condenser  200  ( FIG. 2A , step  2 A 30 ). The condenser  200  stores a copy of the Web document (e.g. the HTML code) in its own cache ( FIG. 2A , step  2 A 50 ), binds the copy to that specific user ( FIG. 2A , step  2 A 40 ), and forwards a copy to the content browser  110  in the user&#39;s computer  100  ( FIG. 2A , step  2 A 60 ). Binding of the copy to the user may be implemented, for example and without limitation, through cookie technology. In such a binding implementation, the condenser  200  generates and assigns a unique identifier or token to the specific user, binds the token to the copy of the Web document, stores this binding ( FIG. 2A , step  2 A 50 ), and transmits the unique identifier in the form of a cookie (or other token or mechanism known to those skilled in the art) to the user&#39;s computer  100  ( FIG. 2A , step  2 A 60 ). In subsequent interactions with the condenser, the content browser  110  in the user&#39;s computer  100  will preferably automatically forward the cookie to the condenser  200 , enabling the condenser  200  recognize the user. In alternate embodiments, the condenser  200  may bind the copy to a class of users that share common characteristics. These common characteristics increase the chance that the users in the class will exhibit similar browsing behaviors and therefore request the same documents. 
   The content browser  110  receives the document ( FIG. 2B , step  2 B 20 ) and the cookie ( FIG. 2B , step  2 B 30 ), stores a copy of it in its local cache ( FIG. 2B , step  2 B 40 ) and displays the document ( FIG. 2B , step  2 B 50 ). In an embodiment implementing classes of users, network caches accessible to multiple users may choose to cache a copy of the document as well. 
   When the user&#39;s computer  100  subsequently requests the same Web document (which may since have slightly changed or updated) at a future time ( FIG. 2B , step  2 B 60 ) via the condenser  200  ( FIG. 2A , step  2 A 70 ), the condenser  200  recognizes (due to a cookie, or other form of binding, which may be received from the user if necessary ( FIG. 2B , step  2 B 70 )) that the user (or another user in the class) has received an earlier version of the document, retrieves the earlier version of the document ( FIG. 2A , step  2 A 100 ), retrieves the new updated version of the document from the content server ( FIG. 2A , steps  2 A 80  and  2 A 90 ), and performs a condensation process on the two Web documents ( FIG. 2A , step  2 A 110 ). The result of the condensation process is a condensed document that is sent back to the user&#39;s computer  100  ( FIG. 2A , step  2 A 120  and  FIG. 2B , step  2 B 80 ), assembled by the assembly module  120  ( FIG. 2B , step  2 B 100 ) using an earlier version of the document retrieved from memory ( FIG. 2B , step  2 B 90 ), locally cached in its uncondensed form ( FIG. 2B , step  2 B  110 ), and ultimately displayed by the content browser  110 . 
   The assembly module  120  accesses the local cache in the user&#39;s computer  100  (or the local network cache that is accessible to the entire class) in order to reassemble the condensed document. Preferably, the local cache still contains a copy of the first version of the Web document from the first request. If the local cache does not contain such a copy (e.g. the local cache has been flushed), the user&#39;s computer  100  may transmit a request for another copy of the first version of the document which is then received and used to reassemble the condensed document. 
   If the new version of the document has been updated or changed, its decomposition will produce new fragments that consist entirely of new material and old fragments that match certain fragments of the prior version. Because the prior version of the document is also locally cached at the user&#39;s computer  100 , the old fragments are already resident on the user&#39;s computer  100 . Therefore, the condenser  200  simply transmits the new fragments and a list of pointers to the old fragments to the user&#39;s computer  100 . The combination of new fragments and the list of pointers typically requires substantially fewer bits than the entire document. 
   Details of the Condensation Process 
   As discussed earlier, the condenser  200  performs the condensation process when it receives a second request for a document from the user&#39;s computer  100  ( FIG. 2A , step  2 A 70 ,  FIG. 2B , step  2 B 60 ). The condenser  200  retrieves ( FIG. 2A , step  2 A 90 ) and fragments ( FIG. 2A , step  2 A 110 ) this second version of the document (hereinafter, “document B”) by comparing it to the first version of the document (hereinafter, “document A”). This comparison results in a condensed document (hereinafter, “document C”) which is transmitted to the user&#39;s computer  100 . Note that the fragments are created to maximize network utilization, and thus need not necessarily be semantically meaningful or natural objects such as images, audio, or video. Further details of the condensation process (especially regarding fragmentation) are set forth below. 
   Referring to  FIG. 3 , at step  310 , document C is initialized to contain a pointer to document A. Such a pointer is typically a network address or a URL, but may include any other form of identifier known to those skilled in the art. At step  320 , the condenser  200  finds the longest prefix P, starting from the beginning of document B, that occurs in document A. Hashing methods such as popular implementations of Lempel-Ziv and other text compression algorithms will efficiently find the longest prefix P. Assume that there is a prefix P of document B that occurs in document A, and further suppose that prefix P is of length L characters. At step  330 , L is compared to a threshold parameter T of value at least 2. If L is not greater than T, then at step  340 , the entire string P is appended to C without alteration. Now suppose that L is greater than T. Suppose further that P occurs in document A at position S. Then, at step  350 , the string “(S,L)” is appended to document C in place of prefix P. When document C is ultimately transmitted to the assembly module  120 , the assembly module  120  knows that the two characters “(“ and ”)” are special characters used for parsing. As shown, the threshold parameter T may be selected so that very small prefixes are not replaced by strings of the form “(S,L)” which are longer than the prefix themselves, resulting in a net increase in the number of bits required to transmit document B. Thus, for efficiency reasons, T is often selected to be 4 or greater. The foregoing all assumes that there is some prefix P that occurs in both documents A and B. If there is no prefix P of document B that occurs in document A, then the first character in document B is simply appended to document C (the first character effectively serves as a prefix P of length 1). 
   At step  360 , the prefix string P is deleted from document B. At step  370 , it is determined whether document B is empty. If document B is empty, at step  380 , the process terminates and transmits document C to the assembly module  120  in the user&#39;s computer  100 . Otherwise, if document B is not empty, the process iterates, returning to step  320 . The foregoing describes a process for constructing a new document C from an initially blank state. More generally, document C could be constructed by replacing, within (e.g., in a copy of) document B, each string (above some threshold size) in document B that is also found in document A with that string&#39;s corresponding position and length from document A. 
   At the end of the above process for constructing document C, the condenser may optionally store and bind document B to the user. 
   The foregoing exemplifies the invention in terms of documents composed of characters. However, those skilled in the art will recognize that the invention also applies to documents composed of other primitives, such as pixels or blocks of pixels in the case of images. Specifically, in the case of images, images A and B are broken up into sequences of blocks of, for example, 4×4 pixels. The blocks in image B are examined in sequence, and if a block in image B is sufficiently close to a block in image A, the position of the block in image A is transmitted rather than the block itself. 
   Unlike traditional techniques for compressing images, such as vector quantization, the condensation process does not need to transmit a codebook to reconstruct image B. In a typical prior art scenario, vector quantization operates on an original reference image, selecting a set of blocks from the original reference image to form a codebook. Thenceforth, vector quantization replaces each block in a subsequent image by a block in the codebook that best approximates the block, thereby creating a compressed form of the image. A content server must transmit the entire codebook, together with the list of indices into the codebook that represents the sequence of blocks in the subsequent image, to ensure that the recipient can reconstruct the image. A disadvantage of the vector quantization is that the quality of the compression as well as the reconstructed image depends on the size of the codebook. That is, a small codebook will result in substantial compression but poor image quality, while a large codebook will provide good image quality but relatively little compression. In contrast to vector quantization, the condensation process operates on a pair of images, and reuses any possible block in the first image to approximate the blocks in the second image. Since the first image (image A) has already been transmitted and cached at the user&#39;s computer  100 , it is unnecessary to transmit a codebook. 
   Details of the Assembly Process 
   Once the assembly module  120  receives document C, it begins the assembly process to reconstruct document B. Referring to  FIG. 4 , at step  410 , document B begins as an empty (NULL) document. The assembly module  120  then retrieves a copy of document A from the local cache in the user&#39;s computer  100  (or the network cache accessible to a class of users) by referencing the pointer, provided by document C, to document A. If the local cache has already flushed document A, the user&#39;s computer  100  may request document A from the condenser. At step  420 , the assembly module  120  identifies the prefix P (if any) in document C prior to the first occurrence of a string of the form “(S,L)”. At step  430 , this prefix P is appended to document B. At step  440 , the assembly module  120  finds the string (let&#39;s call it Q) in document A starting at position S and continuing for length L and, at step  450 , appends the string Q to document B. At step  460 , the string P(S,L) (i.e., both prefix P and the pointer (S,L)) is deleted from document C. At step  470 , if document C is not empty, the assembly module  120  iterates the process, returning to step  420 . Otherwise, if document C is empty, the assembly module  120  sends document B, now fully reconstructed, to the content browser  110  to display to the user. At the end of the above process, the content browser  110  may optionally cache document B. Thus, when a third document C is condensed with respect to document B by the condenser  200 , the assembly module  120  can reassemble document C with respect to document B. 
   Example of Operation Involving Text Documents 
     FIG. 5  depicts a specific example of operation of the aforementioned embodiments where the documents are text documents. In this example, the original document  510  requested by the user initially contains the phrase, “pack my box with five dozen liquor jugs.” The condenser  200  caches a copy of the original document  510  in storage  530  before sending it to the user&#39;s computer  100 . Subsequently, the document is changed and the user makes a request for the changed document. As shown in  520 , the document has slightly changed and now contains the phrase, “pack my box with five dozen liquor mugs.” The condenser  200  retrieves the changed document  520  from the content server  300  and compares it with the cached original document  510  in its storage  530 . Using the condensation process described earlier, the condenser  200  determines that characters  1  through  35  and characters  37  through  40  of the original document  510  are same as those of the changed document  520 . The two documents differ only at character position  36 , where the character “m” occurs in the changed document  520  as compared to the character “j” in the original document. The condenser  200  constructs a (14-character) condensed message “(1,35)m(37,4)”  540  to represent the changed character surrounded by unchanged text, and transmits the condensed message  540  to the user&#39;s computer  100 . The assembly module  120  on the user&#39;s computer  100  interprets this message  540  by retrieving a copy of the original document  560  from its own cache  550 , and assembles the changed document  570  as the sequence of characters comprising the first 35 characters of the original document  560 , followed by the single character “m” and then the 4 characters starting at position  37  of the original document  560 . Taken together this sequence of characters forms the changed document  570  and is ultimately displayed on the user&#39;s content browser  110 . The condenser  200  has thus effectively transmitted the changed document  520  with substantially fewer characters (14 characters) than the changed document  520  actually contains (40 characters) itself. The process accelerates the delivery of the changed document  520  resulting in a substantial reduction in transmission time and network traffic. 
   The various embodiments described above should be considered as merely illustrative of the present invention. Those skilled in the art will realize that the present invention is applicable regardless of whether the user is a person at a computer, or a network device such as a cache or proxy agent. Those skilled in the art will realize that the present invention is also applicable to the full range of data forms transmitted on the Internet, including but not limited to text, images, video and audio. Thus the various embodiments described above are not intended to be exhaustive or to limit the invention to the forms disclosed. Those skilled in the art will readily appreciate that still other variations and modifications may be practiced without departing from the general spirit of the invention set forth herein. Therefore, it is intended that the present invention be defined by the claims that follow.