Method for making intelligent data placement decisions in a computer network

• US 8,886,804 B2
• Filed: 05/24/2010
• Issued: 11/11/2014
• Est. Priority Date: 05/26/2009
• Status: Expired due to Fees

• Current Assignee: Pi-Coral Incorporated
• Original Assignee: Pi-Coral Incorporated
• Inventors: Osmond, Roger Frederick
• Primary Examiner(s): Patel, Chirag R
• Assistant Examiner(s): KHAN, AFTAB N
• Application Number:
  US12/786,131
• Publication Number:
  US 20100306371A1
• Time in Patent Office: 1,632 Days
• Field of Search: 709/226, 709/224, 709/229, 709/232, 709/240, 709/249, 718/104, 707/626
• US Class Current: 709/226
• CPC Class Codes: G06F 11/1492 by run-time replication performed by the application software
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06N 5/027 Frames
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• 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: H04N 21/00 Selective content distribution, e.g. interactive television or video on demand [VOD] real-time bi-directional transmission of motion video data H04N7/14 ; broadcast or conference over packet switching networks H04L12/18
• CPC Class Codes: H04N 21/231 Content storage operation, e.g. caching movies for short term storage, replicating data over plural servers, prioritizing data for deletion

Abstract

A method for making data placement decisions in a computer network uses multiple factors comprising social rules (rules, factors and criteria common to all participating nodes and intended to benefit the community of nodes), as well as rules, factors and criteria driven by individual self-interest of the participating nodes. The method calls for each node to act in a semi-autonomous manner, without the need for a central coordinating node. By considering multiple factors fully, and not eliminating factors by a sequence of True/False decisions, the method may arrive at optimal decisions and may generate a ranked list of node candidates.

Claims

1. A computer-implemented method for making a data placement decisions in a computer network, the method comprising:

providing a plurality of self-interest criteria defined for each of a plurality of computer network nodes of the computer network;

wherein the plurality of self-interest criteria comprises at least two of the following;

a storage cost criterion calculated based on object size, a load criterion, a redirection density criterion, and an object-node affinity criterion;

providing a plurality of social criteria defined for each of the plurality of computer network nodes, wherein each of the plurality of network nodes is configured to act in a semi-autonomous manner, without the need for a central coordinating node;

assigning weights to the plurality of self-interest criteria and the plurality of social criteria;

generating the data placement decision responsive to a computer network event, wherein generating the data placement decision comprises selecting at least one target node based on the plurality of self-interest criteria and the plurality of social criteria;

communicating a request to the at least one target node based on the computer network event;

receiving the request for at least one data object at a first computer network node of the plurality of computer network nodes, the at least one data object being stored on at least one of the plurality of computer network nodes;

analyzing, via the first computer network node, the plurality of self-interest criteria for the first computer network node and a plurality of demand criteria associated with the at least one data object to determine whether to replicate the at least one data object by using a matrix of decision factors;

selecting, via the first computer network node, at least one target node with a highest points value in the matrix as preferred target node for storing the at least one replica based on the weighted plurality of self-interest criteria for the first computer network node and the weighted plurality of social criteria responsive to a determination to replicate the at least one data object;

generating at least one replica of the at least one data object; and

storing the at least one replica on the at least one target node into a container.

2. The computer-implemented method of claim 1, wherein the target node is selected from a plurality of nodes comprising peers of the at least one computer network node.

3. The computer-implemented method of claim 1, wherein the plurality of self-interest criteria comprises a storage cost criterion comprising at least one of the following:

a cost of at least one storage device and a cost of storing the at least one data object on at least one storage device.

4. The computer-implemented method of claim 1, wherein the plurality of self-interest criteria comprises a load criterion comprising a current load and a historical load of at least one of the plurality of computer network nodes.

5. The computer-implemented method of claim 1, wherein the plurality of self-interest criteria comprises a redirection density criterion comprising a recent frequency of redirection requests for the at least one data object and a historical frequency of redirection requests for the at least one data object.

6. The computer-implemented method of claim 1, wherein the plurality of self-interest criteria comprises an object-node affinity criterion comprising a measure of an object population of a container storing the at least one data object.

7. The computer-implemented method of claim 1, wherein the plurality of social criteria comprises two or more of the following:

a replica minimum/maximum rule, an object popularity rule and a movement cost rule.

8. The computer-implemented method of claim 7, wherein the plurality of social criteria comprises a replica minimum/maximum rule comprising a minimum replica count within the computer network and a maximum replica count within the computer network.

9. The computer-implemented method of claim 7, wherein the plurality of social criteria comprises an object popularity rule comprising at least one of the following:

a measured popularity of the at least one data object and a predicted popularity of the at least one data object.

10. The computer-implemented method of claim 7, wherein the plurality of social criteria comprises a movement cost rule comprising a cost of copying the at least one data object to the at least one target node.

11. A system for making data placement decisions in a computer network, the system comprising:

a plurality of computer network nodes;

a first computer network node of the plurality of computer network nodes, the first computer network node being operative to execute a data placement decision application, the data placement decision application being configured to;

access a plurality of self-interest criteria, the plurality of self-interest criteria being weighted and defined for each of the plurality of computer network nodes of the computer network, wherein the plurality of self-interest criteria comprises at least two of the following;

a storage cost criterion calculated based on object size, a load criterion, a redirection density criterion, and an object-node affinity criterion,

access a plurality of social criteria, the plurality of social criteria being weighted and defined for each of the plurality of computer network nodes, wherein each of the plurality of network nodes is configured to act in a semi-autonomous manner, without the need for a central coordinating node,

receive a request for at least one data object stored on at least one of the plurality of computer network nodes,

analyze the plurality of self-interest criteria for the first computer network node and the plurality of demand criteria associated with the at least one data object to determine whether to replicate the at least one data object by using a matrix of decision factors,

select at least one target node with a highest value in the matrix as preferred target node for storing the at least one replica based on the weighted plurality of self-interest criteria for the first computer network node and the weighted plurality of social criteria responsive to a determination to replicate the at least one data object,

generate the data placement decision responsive to a computer network event, wherein generating the data placement decision comprises selecting at least one target node based on a plurality of self-interest criteria and a plurality of social criteria,

communicate the request to the at least one target node based on the computer network event,

generate at least one replica of the at least one data object, and

store the at least one replica on the at least one target node into a container.

12. The computer-implemented method of claim 11, wherein the plurality of social criteria comprises two or more of the following:

a replica minimum/maximum rule, an object popularity rule, and a movement cost rule.