Method of and apparatus for rapid retrieval of data in a content distribution network

• US 6,826,626 B1
• Filed: 07/21/2000
• Issued: 11/30/2004
• Est. Priority Date: 07/21/2000
• Status: Expired due to Fees

• Current Assignee: ClearBlue Technologies Management, Inc.
• Original Assignee: Clear Blue Technologies Management Incorporated
• Inventors: McManus, Patrick Raymond
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Chang, Jungwon
• Application Number:
  US09/621,659
• Time in Patent Office: 1,593 Days
• Field of Search: 709/247, 709/219, 709/217, 709/201, 709/246, 711/100, 707/101
• US Class Current: 709/246
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of and apparatus for accelerating data retrieval on a widely dispersed content distribution network such as the World Wide Web. The system associates a concept URI with a resource which can then serve as a reference for a group of resources. When the system receives a request from a client calling for a resource in this group, it prepares a delta encoded responses based on the difference between the reference document and the response it has obtained from an origin server (the identity response). The system then sends the client the delta encoded response, an identification of the reference document used to prepare the delta encoded response, and an address where the reference document may be obtained if a client does not already have a copy. A client either decodes the information from the system by reconstituting the response using the delta encoded response and the reference if it already has a local copy, or, if it does not already have a local copy, using the address to retrieve a local copy and then carrying out the decoding. The selection of a reference is based on heuristics. The system also has the capability of changing which resource it will use as a reference based on the performance of the reference, i.e., whether the reference has continued to produce acceptably small deltas. The reference may be a version of an actual resource, or created by the system to serve the group of resources as a reference.

Claims

1. A method of retrieving data over a content distribution network, said method comprising:

a step, performed by a client, of sending a request for data for a resource, a step, performed by a server responsively connected to said client, of receiving said request for data sent by said client;

a step, performed by said server, of identifying a reference for an identity response to said request;

a step, performed by said server, of comparing said reference with said identity response to said request for data to generate a delta encoded response based on differences between said identity response and said reference;

a step, performed by said server, of sending said delta encoded response and an identification of said reference to said client;

a step, performed by said client, of reconstituting said identity response using said delta encoded response and a locally stored copy of said reference if said client has previously stored a copy of said reference, otherwise retrieving a copy of said reference and then reconstituting said identity response using said delta encoded response and the retrieved copy of said reference; and

a step, performed by said server, of tracking use of said reference and replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference.

2. A method as claimed in claim 1 wherein said step of identifying a reference for the identity response comprises the step of identifying a reference having a URI which when truncated matches a similarly truncated URI for the identity response.

3. A method as claimed in claim 1 wherein said step of tracking further comprises the steps, performed by said server, of:

storing an indication of a size of said delta encoded response generated by a given reference each time said comparing step is performed using said given reference to obtain a series of sizes of delta encoded responses generated by said given reference;

forming at least one weighted average using said series of sizes of delta encoded responses; and

substituting a new reference for the given reference based at least in part on said at least one weighted average.

4. The method as claimed in claim 3, wherein said step of forming at least one weighted average using said series of delta encoded responses further comprises the steps of:

forming a fast moving average using said series of sizes of delta encoded responses; and

forming a slow moving average using said series of sizes of delta encoded responses,

wherein said fast moving average weights a size of a most recent delta encoded response more than said slow moving average weights said size of said most recent delta encoded response.

5. The method of claim 4, wherein said step of replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference further comprises the step of:

replacing said reference when a difference between said fast moving average and said slow moving average is greater than twice a weighted average of said difference between said fast moving average and said slow moving average.

6. The method of claim 4 wherein said step of replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference further comprises the step of:

replacing said reference when said fast moving average is greater than twice said slow moving average.

7. A method as claimed in claim 1 wherein said delta encoded response is generated based on a string substitution using the reference as a dictionary for the delta encoded output and using variable length references to strings in the reference and raw echo includes of non-replicated information from the identity response.

8. A method as claimed in claim 1 wherein in said step of sending said delta encoded response and an identification of said reference to said client, said server also sends an address where said reference may be found and wherein said server keeps said reference available for a predetermined period of time after sending said identification of said reference and said address to said client.

9. A method as claimed in claim 1, wherein said step of identifying a reference for said identity response further comprises the step of:

selecting, as said reference, a document used to compute deltas relative to said identity response, wherein said identity response represents an original content document associated with said client'"'"'s request.

10. The method as claimed in claim 1, further comprising the step of:

a step, performed by said network, of returning an address of a proxy to said client.

11. The method of claim 1, further comprising the step of:

aborting said replacement of said reference if a size value associated an average of recent delta encoded responses is less than a predetermined threshold.

12. A method of retrieving data over a content distribution network, said method comprising:

a step, performed by a server after serving a resource in a previous transaction, of making a concept URI for that resource;

a step, performed by a client, of sending a request for data for a resource to said server,

a step, performed by said server, of receiving said request for data sent by said client;

a step, performed by said server, of comparing said concept URI with the URI of an identity response to said request for data and, if said concept URI and said URI of said identity response partially match, of generating a delta encoded response based on differences between said identity response and a reference identified by said concept URI;

a step, performed by said server, of sending said delta encoded response and a identification of said reference to said client;

a step, performed by said client, of reconstituting said identity response using said delta encoded response and a locally stored copy of said reference if said client has previously stored a copy of said reference, otherwise retrieving a copy of said reference and then reconstituting said identity response using said delta encoded response and the retrieved copy of said reference; and

a step, performed by said server, of tracking use of said reference and replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference.

13. A method as claimed in claim 12, wherein said step of comparing said concept URI and said URI of said identity response comprises comparing truncated versions of said concept URI and said URI of said identity response for a complete match.

14. A method as claimed in claim 12, wherein said step of tracking further comprises the steps, performed by said server, of:

storing an indication of a size of said delta encoded response generated by a given reference each time said comparing step is performed using said given reference to obtain a series of sizes of delta encoded responses generated by said given reference;

forming at least one weighted average using said series of sizes of delta encoded responses; and

substituting a new reference for the given reference based at least in part on said at least one weighted average.

15. A method as claimed in claim 12, wherein said delta encoded response is generated based on a string substitution using the reference as a dictionary for the delta encoded output and using variable length references to strings in the reference and raw echo includes of non-replicated information from the identity response.

16. A method as claimed in claim 12 wherein in said step of sending said delta encoded response and an identification of said reference to said client, said server also sends an address where said reference may be found and wherein said server keeps said reference available for a predetermined period of time after sending said identification of said reference and said address to said client.

17. A method as claimed in claim 12 wherein said step of tracking further comprises the steps, performed by said return engine, of:

storing an indication of a size of said delta encoded response generated by a given reference each time said comparing step is performed using said given reference to obtain a series of sizes of delta encoded responses generated by said given reference;

forming at least one weighted average using said series of sizes of delta encoded responses; and

substituting a new reference for the given reference based at least in part on said at least one weighted average.

18. The method as claimed in claim 12, further comprising the step of:

a step, performed by said network, of returning an address of a proxy to said client.

19. A method of retrieving data over a content distribution network, said method comprising:

a step, performed by a user agent, of sending a request for data for a resource,

a step, performed by an entry proxy arranged to receive said request from said user agent, of relaying said request to a return engine together with an indication that said entry proxy can perform an encoding;

a step, performed by said return engine, of obtaining an identity response to said request from an origin server;

a step, performed by said return engine, of identifying a reference for said identity response to said request;

a step, performed by said return engine, of comparing said reference with said identity response to said request for data to generate a delta encoded response based on differences between said identity response and said reference;

a step, performed by said return engine, of sending said delta encoded response and an identification of said reference to entry proxy;

a step, performed by said entry proxy, of reconstituting said identity response using said delta encoded response and a locally stored copy of said reference if said entry proxy has previously stored a copy of said reference, otherwise retrieving a copy of said reference from said return engine and then reconstituting said identity response using said delta encoded response and the retrieved copy of said reference;

a step, performed by said entry proxy, of sending the reconstituted response to the user agent which requested it; and

a step, performed by said return engine, of tracking use of said reference and replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference.

20. A method as claimed in claim 19 wherein said step of identifying a reference for the identity response comprises the step of identifying a reference having a URI which when truncated matches a similarly truncated URI for the identity response.

22. A method as claimed in claim 19 wherein in said step of sending said delta encoded response and an identification of said reference to said entry proxy said return engine also sends an address where said entry proxy may find said reference and wherein said return engine keeps said reference available for a predetermined period of time after sending said identification of said reference and said address to said entry proxy.

23. The method as claimed in claim 19, wherein said step of identifying a reference for said identity response further comprises the step of:

selecting, as said reference, a document used to compute deltas relative to said identity response, wherein said identity response represents an original content document associated with said client'"'"'s request.

24. The method as claimed in claim 19, further comprising the step of:

a step, performed by said network, of sending an address of said entry proxy to said user agent.

21. A method as claimed 19 in claim wherein said delta encoded response is generated based on a string substitution using the reference as a dictionary for the delta encoded response and using variable length references to strings in the reference and raw echo includes of non-replicated information from the identity response.

25. An apparatus for retrieving data over a content distribution network, said apparatus comprising:

a client adapted to send a request for data for a resource,

a server, responsively connected to said client, and arranged to receive said request for data sent by said client, said server including

means for identifying a reference for an identity response to said request;

means for comparing said reference with an identity response to said request for data to generate a delta encoded response based on differences between said identity response and said reference;

means for sending said delta encoded response and an identification of said reference to said client; and

means for tracking use of said reference and replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference;

wherein said client includes means for reconstituting said identity response using said delta encoded response and a locally stored copy of said reference if said client has previously stored a copy of said reference, otherwise for retrieving a copy of said reference and then reconstituting said identity response using said delta encoded response and the retrieved copy of said reference.

26. Apparatus as claimed in claim 25 wherein said reference identifying means includes means for identifying a reference having a URI which when truncated matches a similarly truncated URI for the identity response.

27. Apparatus as claimed in claim 25 wherein said means for tracking further comprises:

means for storing an indication of a size of said delta encoded response generated by a given reference each time said comparing step is performed using said given reference to obtain a series of sizes of delta encoded responses generated by said given reference;

means for forming at least one weighted aver age using said series of sizes of delta encoded responses; and

means for substituting a new reference for the given reference based at least in part on said at least one weighted average.

28. The apparatus as claimed in claim 27, wherein said means for forming at least one weighted average using said series of delta encoded responses further comprises:

means for forming a fast moving average using said series of sizes of delta encoded responses; and

means for forming a slow moving average using said series of sizes of delta encoded responses,

wherein said fast moving average weights a size of a most recent delta encoded response more than said slow moving average weights said size of said most recent delta encoded response.

29. The apparatus of claim 28, wherein said means for replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference further comprises:

means for replacing said reference when a difference between said fast moving average and said slow moving average is greater than twice a weighted average of said difference between said fast moving average and said slow moving average.

30. The apparatus of claim 28 wherein said step of means for replacing said reference when more than a predetermined number of delta encoded responses generated using said reference fall more than a predetermined number of standard deviations from a mean of a distribution of delta encoded responses generated using said reference further comprises:

means for replacing said reference when said fast moving average is greater than twice said slow moving average.

31. Apparatus as claimed in claim 25 wherein said delta encoded response is generated based on a string substitution using the reference as a dictionary for the delta encoded output and using variable length references to strings in the reference and raw echo includes of non-replicated information from the identity response.

32. Apparatus as claimed in claim 25 wherein said means for sending said delta encoded response and an identification of said reference to said client further includes means for sending an address where said reference may be found and wherein means for keeping said reference available for a predetermined period of time after sending said identification of said reference and said address to said client.

33. Apparatus as claimed in claim 25, wherein said means for identifying a reference for an identity response further comprises:

means for selecting, as said reference, a document used to compute deltas relative to said identity response, wherein said identity response represents an original content document associated with said client'"'"'s request.

34. The apparatus as claimed in claim 25, wherein said client connects to a proxy located on machine other than that on which said client is located.

35. The apparatus of claim 25, further comprising:

means for aborting said replacement of said reference if a size value associated an average of recent delta encoded responses is less than a predetermined threshold.