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

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.

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.

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.

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.