Recipient-centred proactive caching in a peer-to-peer system

• US 7,627,644 B2
• Filed: 11/22/2004
• Issued: 12/01/2009
• Est. Priority Date: 11/28/2003
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Slack-Smith, David Geoffrey
• Primary Examiner(s): Caldwell; Andrew
• Assistant Examiner(s): Survillo; Oleg
• Application Number:
  US10/992,721
• Publication Number:
  US 20050120133A1
• Time in Patent Office: 1,835 Days
• Field of Search: 709/234, 709/213, 709/201, 709/217
• US Class Current: 709/213
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A method (100) of caching data is disclosed. The method (100) optimises proactive caching of data by estimating future demand for particular data within a computer system (1900). The computer system (1900) is typically configured in accordance with the hybrid peer-to-peer model. The method (100) maintains the bandwidth cost of proactive caching in proportion to expected demand for particular data. The method (100) also determines the availability of a peer. The availability of a peer is defined herein as the probability of a peer being online, for example, when particular data is required by another peer.

Claims

1. A method of caching data over a network, said method comprising the steps of:

estimating capacities of each of a plurality of peers connected to said network, wherein for each said peer, multiple capacities are estimated at different points over time, and wherein each said estimate of capacity for each said peer is the product of the probability of the peer being on-line and the bandwidth available to said peer;

estimating a demand curve for said data from said plurality of peers connected to said network based at least partly on a sum of demand curves of demand for each peer at different points over time, wherein for each peer at each point in time, the demand is a product of one of the estimates of capacity of the peer, a probability of the peer wanting to download said data, and a desirability rating of an author of said data;

estimating a supply curve for the data from the plurality of peers connected to the network based at least partly on a sum of supply curves of supply for each peer at different points over time, wherein for each peer at each point in time, the supply is a product of one of the estimates of capacity of the peer, and a probability of the peer having said data;

selecting one or more of the peers so as to balance load on the peers, wherein the estimated capacities of the selected one or more peers vary with time in a similar manner to the demand curve and are utilized to reduce differences between the estimated demand and supply curves at said different points over time; and

proactively caching said data on the one or more selected peers.

2. A method according to claim 1, further comprising the step of deleting further data from at least one of the selected peers if said supply is greater than said demand.

3. A method according to claim 1, wherein estimates of any one or more of demand and capacity are executed on a central server connected to said network.

4. A method according to claim 1, further comprising the step of selecting a set of the peers connected to said network based on which of the peers are online when an amount of necessary storage capacity is at a maximum.

5. A method according to claim 4, wherein the selecting peers step comprises the step of allocating a weight to each peer in said set.

6. An apparatus for caching data over a network, said apparatus comprising:

a processor; and

a memory coupled to the processor comprising;

capacity estimation means for estimating capacities of each of a plurality of peers connected to said network, wherein for each peer, multiple capacities are estimated at different points over time, and wherein each said estimate of capacity for each said peer is the product of the probability of the peer being on-line and the bandwidth available to said peer;

demand estimation means for estimating a demand curve for said data from said plurality of peers connected to said network based at least partly on a sum of demand curves of demand for each peer at different points over time, wherein for each peer at each point in time, the demand is a product of one of the estimates of capacity of the peer, a probability of the peer wanting to download said data, and a desirability rating of an author of said data;

supply estimation means for estimating a supply curve for the data from the plurality of peers connected to the network based at least partly on a sum of supply curves of supply for each peer at different points over time, wherein for each peer at each point in time, the supply is a product of one of the estimates of capacity of the peer, and a probability of the peer having said data;

peer selection means for selecting one or more of the peers so as to balance load on the peers, wherein the estimated capacities of the selected one or more peers vary with time in a similar manner to the demand curve and are utilized to reduce differences between the estimated demand and supply curves at said different points over time; and

storage means for proactively caching said data on the one or more selected peers.

7. A computer readable storage medium storing a computer-executable program, said computer-executable program being executable by a computer so as to control the computer to execute a method for caching data over a network, said computer-executable program comprising:

code for estimating capacities of each of a plurality of peers connected to said network, wherein for each said peer, multiple capacities are estimated at different points over time, and wherein each said estimate of capacity for each said peer is the product of the probability of the peer being on-line and the bandwidth available to said peer;

code for estimating a demand curve for said data from said plurality of peers connected to said network based at least partly on a sum of demand curves of demand for each peer at different points over time, wherein for each peer at each point in time, the demand is a product of one of the estimates of capacity of the peer, a probability of the peer wanting to download said data, and a desirability rating of an author of said data;

code for estimating a supply curve for the data from the plurality of peers connected to the network based at least partly on a sum of supply curves of supply for each peer at different points over time, wherein for each peer at each point in time, the supply is a product of one of the estimates of capacity of the peer, and a probability of the peer having said data;

code for selecting one or more of the peers so as to balance load on the peers, wherein the estimated capacities of the selected one or more peers vary with time in a similar manner to the demand curve and are utilized to reduce differences between the estimated demand and supply curves at said different points over time; and

code for proactively caching said data on the one or more selected peers.