Dynamic cache replication in a internet environment through routers and servers utilizing a reverse tree generation

• US 6,189,043 B1
• Filed: 06/09/1997
• Issued: 02/13/2001
• Est. Priority Date: 06/09/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Eckberg, Adrian Emmanuel Jr., Johri, Pravin Kumar, Liu, Danielle, Buyukkoc, Cagatay
• Primary Examiner(s): Geckil, Mehmet B.
• Assistant Examiner(s): Vaughn, Jr., William C.
• Application Number:
  US08/871,106
• Time in Patent Office: 1,345 Days
• Field of Search: 395/200.68, 395/200.72, 395/674, 395/675, 395/200.53, 711/133, 711/136, 711/137, 364/468.03, 345/327, 709/238, 709/224, 709/242, 709/223, 709/203, 709/105, 709/104, 709/241, 709/202, 709/240, 709/239, 370/351, 370/254, 370/255, 370/256
• US Class Current: 709/241
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

The distribution of replica caches of information is dynamically optimized among the regions of a network, based upon the changing usage patterns. Initially, a single server in a first region stores the primary copy of information. A router in the first region receives service request messages from the plurality of users throughout network, directed to the server storing the primary copy. To determine if it is justified to deploy a replica cache, the router transmits a monitor request message to other routers in other regions of the network, requesting them to monitor all service requests in their respective regions, being directed to the primary copy in the first server. The first router then computes an optimum assignment of a replica copy of the information, for storage in at least one newly assigned server in the network. The first router transmits a replication message to the newly assigned server, to enable it to store the replica copy of the information and provide service to user terminals in a newly assigned set of regions of the network. The first router also transmits an assignment message to the other routers in the network, to enable them to redirect traffic from their respective regions to either the newly assigned server or to the first server.

Claims

1. In a network including a plurality of regions, each region including a router, a server, and a plurality of user terminals, the router coupling the server and the plurality of user terminals to the network, a method for distributing replica caches of information among the regions, comprising the steps of:

transmitting a monitor request message from a first router in a first region of the network to a plurality of routers in a second region of the network, requesting from the plurality of routers a measure of a plurality of service requests being directed to a first server in the first region storing a primary copy of information;

ascertaining with a processor associated with said first router, said measure of requests made by a plurality of user terminals in the network for said primary copy of information; and

responsive to said measure of requests, said processor computing an optimum assignment to another server in another region of the network, to store a replica copy of said information and transmitting a message to a router in said another region to store said replica copy of said information as a replica cache, said router in said another region being selected by means of a cost/benefit analysis that calculates a total cost of a distribution of caches in the network;

wherein said optimum assignment is a distribution of replicas of said primary copy of information that minimizes a bandwidth cost of messages exchanged between said plurality of user terminals and an existing distribution of caches.

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

responsive to said measure of requests, said processor in said first region transmitting a message to a router in at least one other region to redirect said requests made by user terminals to said replica cache.

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

responsive to said measure of requests said processor in said first region selecting said router in at least one other region by means of a cost/benefit analysis.

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

responsive to said measure of requests said processor in said first region selecting said router in at least one other region by means of a cost/benefit analysis that calculates a lost opportunity cost of not having a replica cache.

5. In a network including a plurality of regions, each region including a router, a server, and a plurality of user terminals, the router coupling the server and the plurality of user terminals to the network, a method for distributing cache replicas of information among the regions, comprising the steps of:

transmitting from a first router in a first region a monitor request message to a plurality of routers in other regions, requesting said other routers to monitor a plurality of requests from a plurality of user terminals directed to a first server in said first region, to deliver said information;

receiving monitor response messages from said other routers indicating a measure of requests made by a plurality of user terminals in the network for said information; and

responsive to said response messages, transmitting a message to at least one of said other routers to store a copy of said information as an optimum distribution of said information that minimizes a bandwidth cost of messages exchanged between said plurality of user terminals and an existing distribution of the information, said one of said other routers being selected by means of a cost/benefits analysis that calculates a total cost of a distribution of caches in the network.

6. The method of claim 5, further comprising the step of:

responsive to said response messages, transmitting a message to a router in at least one other region to redirect said requests to said first server, to said replica cache.

7. The method of claim 5, further comprising the step of:

responsive to said response messages, selecting said first server by means of a cost/benefit analysis.

8. The method of claim 5, further comprising the step of:

responsive to said response messages, selecting said first server by means of a cost/benefit analysis that calculates a lost opportunity cost of not having a replica cache.

9. In a network including a plurality of regions, each region including a router, a server, and a plurality of user terminals, the router coupling the server and the plurality of user terminals to the network, a method for optimizing the distribution of replica caches of information among the regions, comprising the steps of:

receiving service request messages at a first router in a first region of the network, from a plurality of users in the network, the service requests being directed to a first server in the first region storing a primary copy of information;

transmitting a monitor request message from said first router to a second router in a second region of the network, requesting the second router to monitor service requests being directed to said first server from a plurality of user terminals;

receiving a monitor response message at said first router from said second router, providing a count of service requests being directed to said first server;

computing at said first router, an optimum assignment of a replica copy of said information for storage at another server in another region of the network; and

transmitting an assignment message from said first router to said another server, to enable said another server to store said replica copy of said information and provide service to user terminals in an assigned subplurality of regions of the network, said another server being selected by means of a cost/benefit analysis that calculates a total cost of a distribution of caches in the network;

wherein said optimum assignment is a distribution of replicas of said primary copy of information that minimizes a bandwidth cost of messages exchanged between said plurality of user terminals and an existing distribution of caches.

10. The method of claim 9, further comprising the step of:

said computing step including selecting said another server by means of a cost/benefit analysis.

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

said computing step including selecting said another server by means of a cost/benefit analysis that calculates a lost opportunity cost of not having a replica cache.

12. In a network including a plurality of regions, each region including a router, a server, and a plurality of user terminals, the router coupling the server and the plurality of user terminals to the network, a method for optimizing the distribution of replica caches of information among the regions, comprising the steps of:

forwarding service request messages from a plurality of users in the network, to a first server in the first region storing a primary copy of information;

receiving at a second router in a second region of the network, a monitor request message from said first router requesting the second router to monitor service requests being directed to said first server;

monitoring at said second router, service requests being directed to said first server;

transmitting a monitor response message from said second router to said first router, providing a count of service requests being directed to said first server;

receiving an assignment message at said second router from said first router, including an optimum assignment of a replica copy of said information for storage at a second server in said second region of the network; and

enabling said second server to store said replica copy of said information and provide service to user terminals in an assigned subplurality of regions of the network.

13. In a network including a plurality of regions, each region including a router, a server, and a plurality of user terminals, the router coupling the server and the plurality of user terminals to the network, a system for distributing replica caches of information among the regions, comprising:

a router in a first region;

a processor coupled to said router, for ascertaining a measure of requests made by user terminals in the network for said information;

said router transmitting a message to a router in at least one other region to store a copy of said information as a replica cache, in response to said measure of requests.

14. The system of claim 13, further comprising:

responsive to said measure of requests, said router in said first region transmitting a message to a router in at least one other region to redirect said requests made by user terminals to said replica cache.

15. The system of claim 13 further comprising:

responsive to said measure of requests said processor selecting said router in at least one other region by means of a cost/benefit analysis.

16. The system of claim 13, further comprising:

responsive to said measure of requests said processor selecting said router in at least one other region by means of a cost/benefit analysis that calculates the total cost of a distribution of caches in the network.

17. The system of claim 13, further comprising:

responsive to said measure of requests said processor selecting said router in at least one other region by means of a cost/benefit analysis that calculates a lost opportunity cost of not having a replica cache.

18. In a network including a plurality of regions, each region including a router, a server, and a plurality of user terminals, the router coupling the server and the plurality of user terminals to the network, a method for optimizing the distribution of replica caches of information among the regions, comprising the steps of:

receiving service request messages at a first router in a first region of the network, from a plurality of users in the network, the service requests being directed to a first server in the first region storing a primary copy of information;

transmitting a monitor request message from said first router to a second router in a second region of the network, requesting the second router to monitor service requests from said plurality of user terminals being directed to said first server;

receiving a monitor response message at said first router from said second router, providing a count of service requests being directed to said first server;

computing at said first router, an optimum assignment of a replica copy of said information for storage at another server in another region of the network; and

transmitting an assignment message from said first router to said another server, to enable said another server to store said replica copy of said information and provide service to user terminals in an assigned subplurality of regions of the network;

wherein said optimum assignment is a distribution of replicas of said primary copy of information that minimizes a total cost of an existing distribution of caches; and

wherein the total cost is the sum of a bandwidth cost, a storage cost at a base location, a replication cost in a single server, an opportunity cost, and an update cost associated with updating replicated copies.