Protocol for distributing fresh content among networked cache servers

• US 6,205,481 B1
• Filed: 03/17/1998
• Issued: 03/20/2001
• Est. Priority Date: 03/17/1998
• Status: Expired due to Term

• Current Assignee: Array Networks Incorporated (Hitachi, Ltd.)
• Original Assignee: InfoLibria, Inc. (Hitachi, Ltd.)
• Inventors: Heddaya, Abdelsalam A., Mirdad, Sulaiman A., Yates, Ian C., Yates, David J.
• Primary Examiner(s): Rinehart, Mark
• Assistant Examiner(s): Cardone, Jason D.
• Application Number:
  US09/040,520
• Time in Patent Office: 1,099 Days
• Field of Search: 709/216, 709/218, 709/226, 709/230, 709/238, 709/202, 709/223, 709/104, 709/105, 711/141, 340/825.06, 707/10, 707/201, 707/203, 345/329, 345/330, 345/331
• US Class Current: 709/226
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A technique for automatic, transparent, distributed, scalable and robust replication of document copies in a computer network wherein request messages for a particular document follow paths from the clients to a home server that form a routing graph. Client request messages are routed up the graph towards the home server as would normally occur in the absence of caching. However, cache servers are located along the route, and may intercept requests if they can be serviced. In order to be able to service requests in this manner without departing from standard network protocols, the cache server needs to be able to insert a packet filter into the router associated with it, and needs also to proxy for the home server from the perspective of the client. Cache servers cooperate to update cache content by communicating with neighboring caches whenever information is received about invalid cache copies.

Claims

1. In a system containing a plurality of computers which communicate over a network using communication protocols, with the computers at certain nodes in the network acting as home servers, for storing information in the form of documents, and with certain other computers acting as clients that send document request messages to the servers at an application layer, the document request messages being requests for documents stored at the servers, a method of maintaining copies of documents at the intermediate nodes comprising the steps of:

(a) storing local cache copies of documents at a plurality of intermediate node locations in the network;

(b) in response to a particular one of the clients generating a particular document request message intended to be sent to a particular one of the home servers, fulfilling the document request message at one of the intermediate node locations by intercepting the document request message and returning one of the local cache copies to the client;

(c) determining the identity of at least one neighboring intermediate node that stores local cache copies; and

(d) determining if a local cache copy of a requested document is different from a copy of the requested document at the home server;

wherein step (d) further comprises the steps of;

i) forwarding a hit report to a home server after fulfilling the document request message at one of the intermediate node locations; and

ii) receiving a reply from the home server indicating a time of last modification of the requested document.

2. A method as in claim 1 wherein step (d) further comprises the step of:

iii) if the time of last modification of the requested document indicates that the cache copy is no longer current, adding an identifier for the document to a list of modified documents.

3. A method as in claim 2 additionally comprising the step of:

(e) sending a status message to at least one neighboring intermediate node, the status message including the list of modified documents.

4. A method as in claim 3 additionally comprising the step of:

(f) before sending the list of modified documents to the neighboring intermediate node, removing any duplicate document identifiers corresponding to document information which has already been received from the particular neighboring intermediate node.

5. A method as in claim 2 additionally comprising the step of, at the neighboring intermediate node:

(j) merging the list of modified documents received from the intermediate node with a list of modified documents maintained at the neighboring node.

6. A method as in claim 5 additionally comprising the step of, at the neighboring intermediate node:

(k) maintaining a copy of the list of modified documents received from the intermediate node, in order to avoid returning duplicate document identifier information to the intermediate node when it is time for the neighboring intermediate node to send a status message to the intermediate node concerning the neighboring intermediate nodes'"'"' own information concerning document modifications.

7. A method as in claim 2 wherein step (c) further comprises the step of:

sending status messages to the other intermediate nodes to determine the identity of neighboring cache servers.

8. A method as in claim 2 additionally comprising the step of:

(g) deleting a document identifier from the list of modified documents once the document identifier has been sent to all neighboring cache servers.

9. A method as in claim 2 additionally comprising the step of, at the neighboring intermediate node:

(h) upon receiving a list of modified documents, invalidating any cache copies corresponding to document identifiers on the list.

10. A method as in claim 1 wherein the clients send document request messages to the servers at an application layer level, and the document request messages are fulfilled by transparent proxying.

11. A method as in claim 10 wherein step (b) additionally comprises:

fulfilling the particular application layer document request message at one of the intermediate node locations by intercepting the document request message and returning one of the local cache copies to the application layer at the client, such that the application layer request message is intercepted at the intermediate node and such that a network connection is not established with the application layer on the server.

12. A method as in claim 1 additionally comprising the steps of:

at the home server, attaching a document modification time stamp to the document.

13. A method as in claim 1 wherein the document request messages are fulfilled at node locations through which the document request messages travel, and wherein step (b) additionally comprises the steps of:

(i) determining a path for the particular document request message to travel from the particular client to the particular server along a path of nodes located in the network between the particular client and the particular server, the path comprising a plurality of the intermediate node locations; and

(ii) fulfilling the particular document request message at one of the plurality of intermediate node locations in the determined path of nodes by, in response to receipt of the particular document request message, returning one of the local cache copies corresponding to a document specified in the particular document request message.