Techniques for locating distributed objects on a network based on physical communication costs

• US 20060173855A1
• Filed: 02/02/2005
• Published: 08/03/2006
• Est. Priority Date: 02/02/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Walker, Douglas Jay, Turner, Bryan
• Granted Patent: US 7,562,125 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

Techniques for locating an object such as a data item or service on a node in a distributed system on a computer network include receiving communication cost data that indicates a cost of physically transferring data among nodes in a computer network. A node identifier for a node is determined based on the communication cost data such that a distance between two node identifiers for a pair of nodes is based on a cost of physically transferring data between the pair of nodes. For a particular object that has a particular object identifier, a closest node is determined among the plurality of nodes based on the particular object identifier and node identifiers corresponding to the nodes. The object is located through the closest node, such as by retrieving it or a pointer or an identifier for another node that is still closer to the object.

Claims

1. A method for locating an object on a node in a computer network, comprising the steps of:

receiving communication cost data that indicates a cost of physically transferring data among a plurality of nodes in a computer network;

determining a node identifier for a node of the plurality of nodes based on the communication cost data such that a distance between two node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes;

for a particular object that has a particular object identifier, determining a closest node among the plurality of nodes based on the particular object identifier and a plurality of node identifiers corresponding to the plurality of nodes; and

locating the particular object through the closest node.

2. The method as recited in claim 1, said step of determining the node identifier further comprising the step of determining the node identifier that includes a plurality of dimensions.

3. The method as recited in claim 1, wherein.

said step of receiving communication cost data further comprises the step of receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

said step of determining the node identifier further comprises the steps of determining whether the neighbor set includes more than one node; and

if it is determined that the neighbor set includes more than one node, then

determining a neighbor identifier interval between a largest node identifier of nodes in the neighbor set and a smallest node identifier of the nodes in the neighbor set for each dimension of a node identifier, and

determining a particular node identifier for the particular node within the neighbor identifier interval.

4. The method as recited in claim 3, said step of determining the node identifier further comprising the steps of, if it is determined that the neighbor set includes only one node, then performing the steps of:

determining a neighbor identifier interval that includes a neighbor node identifier of the one node in the neighbor set for each dimension of a node identifier, and

determining the particular node identifier for the particular node in the neighbor identifier interval.

5. The method as recited in claim 3, said step of determining the particular node identifier for the particular node in the neighbor identifier interval further comprising the step of determining the particular node identifier as a first random position in the neighbor identifier interval.

6. The method as recited in claim 3, said step of determining the particular node identifier for the particular node in the neighbor identifier interval further comprising the steps of:

determining a first random position in the neighbor identifier interval and a first measure of smoothness for a first set including the first random number and the neighbor set;

determining a second random position in the neighbor identifier interval and a second measure of smoothness for a second set including the second random number and the neighbor set;

determining whether the first measure of smoothness is more optimal than the second measure of smoothness; and

if it is determined that the first measure of smoothness is more optimal than the second measure of smoothness, then determining the particular node identifier is the first random position,

wherein a measure of smoothness is a measure of how evenly a set of node identifiers is distributed within the neighbor identifier interval.

7. The method as recited in claim 1, said step determining the closest node for a particular object that has a particular object identifier further comprising the steps of:

for each node identifier of the plurality of node identifiers, inputting the particular object identifier and the node identifier into a distance function that produces a distance between the node identifier and the object identifier;

determining a closest node identifier among the plurality of node identifiers which produces from the distance function a smallest distance to the object identifier; and

determining the closest node as a node that corresponds to the closest node identifier.

8. The method as recited in claim 1, further comprising the steps of:

receiving, from a generator node among the plurality of nodes, object data indicating a new distributed object without an object identifier, and

determining a user node set of one or more nodes of the plurality of nodes most likely to retrieve the new distributed object; and

assigning a new object identifier to the new distributed object based on a user identifier set of one or more node identifiers corresponding to the user node set.

9. The method as recited in claim 8, wherein:

said step of determining the user node set further comprises the step of including in the user node set the generator node, and

said step of assigning the new object identifier further comprises the steps of determining a particular distance and determining the object identifier so that a distance between the object identifier and the user identifier set is no greater than the particular distance.

10. A method for locating an object on a node in a computer network comprising the steps of:

receiving data that indicates a plurality of node identifiers that uniquely identify a plurality of nodes on a network;

receiving an object request message that includes data that indicates a particular object identifier that uniquely identifies a particular object among a plurality of objects distributed among the plurality of nodes;

determining, based on the particular object identifier and the plurality of node identifiers, a closest node among the plurality of nodes, wherein a closest node is used to locate the particular object;

determining whether the closest node is available for communication; and

if it is determined that the closest node is not available for communication, then sending a response message, wherein

the response message includes data that indicates that the particular object is not available, and

the response message does not include data that indicates that the particular object does not exist.

11. The method as recited in claim 10, further comprising, if it is determined that the closest node is not available for communication, then not performing the step of determining a different node than the closest node from among the plurality of nodes, which different node is determined to be a new closest node which is used to locate the particular object.

12. The method as recited in claim 10, wherein the plurality of node identifiers for the plurality of nodes are based on communication cost data such that a distance between node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes.

13. A computer-readable medium carrying one or more sequences of instructions for locating an object on a node in a computer network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving communication cost data that indicates a cost of physically transferring data among a plurality of nodes in a computer network;

determining a node identifier for a node of the plurality of nodes based on the communication cost data such that a distance between two node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes;

for a particular object that has a particular object identifier, determining a closest node among the plurality of nodes based on the particular object identifier and a plurality of node identifiers corresponding to the plurality of nodes; and

locating the particular object through the closest node.

14. The computer-readable medium as recited in claim 13, wherein.

said step of receiving communication cost data further comprises the step of receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

said step of determining the node identifier further comprises the steps of determining whether the neighbor set includes more than one node; and

if it is determined that the neighbor set includes more than one node, then

determining a neighbor identifier interval between a largest node identifier of nodes in the neighbor set and a smallest node identifier of the nodes in the neighbor set for each dimension of a node identifier, and

determining a particular node identifier for the particular node within the neighbor identifier interval.

15. A computer-readable medium carrying one or more sequences of instructions for locating an object on a node in a computer network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving data that indicates a plurality of node identifiers that uniquely identify a plurality of nodes on a network;

receiving an object request message that includes data that indicates a particular object identifier that uniquely identifies a particular object among a plurality of objects distributed among the plurality of nodes;

determining, based on the particular object identifier and the plurality of node identifiers, a closest node among the plurality of nodes, wherein a closest node is used to locate the particular object;

determining whether the closest node is available for communication; and

if it is determined that the closest node is not available for communication, then sending a response message, wherein

the response message includes data that indicates that the particular object is not available, and

the response message does not include data that indicates that the particular object does not exist.

16. An apparatus for locating an object on a node in a computer network, comprising:

means for receiving communication cost data that indicates a cost of physically transferring data among a plurality of nodes in a computer network;

means for determining a node identifier for a node of the plurality of nodes based on the communication cost data such that a distance between two node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes;

means for determining a closest node among the plurality of nodes, for a particular object that has a particular object identifier, based on the particular object identifier and a plurality of node identifiers corresponding to the plurality of nodes; and

means for locating the particular object through the closest node.

17. An apparatus for locating an object on a node in a computer network, comprising:

means for receiving data that indicates a plurality of node identifiers that uniquely identify a plurality of nodes on a network;

means for receiving an object request message that includes data that indicates a particular object identifier that uniquely identifies a particular object among a plurality of objects distributed among the plurality of nodes;

means for determining, based on the particular object identifier and the plurality of node identifiers, a closest node among the plurality of nodes, wherein a closest node is used to locate the particular object;

means for determining whether the closest node is available for communication; and

means for sending a response message if it is determined that the closest node is not available for communication, wherein

the response message includes data that indicates that the particular object is not available, and

the response message does not include data that indicates that the particular object does not exist.

18. An apparatus for locating an object on a node in a computer network, comprising:

a network interface that is coupled to a network for communicating therewith a data packet;

one or more processors;

a computer-readable medium; and

one or more sequences of instructions stored in the computer-readable medium, which, when executed by the one or more processors, causes the one or more processors to carry out the steps of;

receiving communication cost data that indicates a cost of physically transferring data among a plurality of nodes in a computer network;

determining a node identifier for a node of the plurality of nodes based on the communication cost data such that a distance between two node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes;

for a particular object that has a particular object identifier, determining a closest node among the plurality of nodes based on the particular object identifier and a plurality of node identifiers corresponding to the plurality of nodes; and

locating the particular object through the closest node.

19. The apparatus as recited in claim 18, said step of determining the node identifier further comprising the step of determining the node identifier that includes a plurality of dimensions.

20. The apparatus as recited in claim 18, wherein.

said step of receiving communication cost data further comprises the step of receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

said step of determining the node identifier further comprises the steps of determining whether the neighbor set includes more than one node; and

if it is determined that the neighbor set includes more than one node, then

determining a neighbor identifier interval between a largest node identifier of nodes in the neighbor set and a smallest node identifier of the nodes in the neighbor set for each dimension of a node identifier, and

determining a particular node identifier for the particular node within the neighbor identifier interval.

21. The apparatus as recited in claim 20, said step of determining the node identifier further comprising the steps of, if it is determined that the neighbor set includes only one node, then performing the steps of:

determining a neighbor identifier interval that includes a neighbor node identifier of the one node in the neighbor set for each dimension of a node identifier, and

determining the particular node identifier for the particular node in the neighbor identifier interval.

22. The apparatus as recited in claim 20, said step of determining the particular node identifier for the particular node in the neighbor identifier interval further comprising the step of determining the particular node identifier as a first random position in the neighbor identifier interval.

23. The apparatus as recited in claim 20, said step of determining the particular node identifier for the particular node in the neighbor identifier interval further comprising the steps of:

determining a first random position in the neighbor identifier interval and a first measure of smoothness for a first set including the first random number and the neighbor set;

determining a second random position in the neighbor identifier interval and a second measure of smoothness for a second set including the second random number and the neighbor set;

determining whether the first measure of smoothness is more optimal than the second measure of smoothness; and

if it is determined that the first measure of smoothness is more optimal than the second measure of smoothness, then determining the particular node identifier is the first random position,

wherein a measure of smoothness is a measure of how evenly a set of node identifiers is distributed within the neighbor identifier interval.

24. The apparatus as recited in claim 18, said step determining the closest node for a particular object that has a particular object identifier further comprising the steps of:

for each node identifier of the plurality of node identifiers, inputting the particular object identifier and the node identifier into a distance function that produces a distance between the node identifier and the object identifier;

determining a closest node identifier among the plurality of node identifiers which produces from the distance function a smallest distance to the object identifier; and

determining the closest node as a node that corresponds to the closest node identifier.

25. The apparatus as recited in claim 18, wherein execution of the one or more sequences of instructions further causes the one or more processors to carry out the steps of:

receiving, from a generator node among the plurality of nodes, object data indicating a new distributed object without an object identifier, and

determining a user node set of one or more nodes of the plurality of nodes most likely to retrieve the new distributed object; and

assigning a new object identifier to the new distributed object based on a user identifier set of one or more node identifiers corresponding to the user node set.

26. The apparatus as recited in claim 25, wherein:

said step of determining the user node set further comprises the step of including in the user node set the generator node, and

said step of assigning the new object identifier further comprises the steps of determining a particular distance and determining the object identifier so that a distance between the object identifier and the user identifier set is no greater than the particular distance.

27. An apparatus for locating an object on a node in a computer network, comprising:

a network interface that is coupled to a network for communicating therewith a data packet;

one or more processors;

a computer-readable medium; and

one or more sequences of instructions stored in the computer-readable medium, which, when executed by the one or more processors, causes the one or more processors to carry out the steps of;

receiving data that indicates a plurality of node identifiers that uniquely identify a plurality of nodes on a network;

receiving an object request message that includes data that indicates a particular object identifier that uniquely identifies a particular object among a plurality of objects distributed among the plurality of nodes;

determining, based on the particular object identifier and the plurality of node identifiers, a closest node among the plurality of nodes, wherein a closest node is used to locate the particular object;

determining whether the closest node is available for communication; and

if it is determined that the closest node is not available for communication, then sending a response message, wherein

the response message includes data that indicates that the particular object is not available, and

the response message does not include data that indicates that the particular object does not exist.

28. The apparatus as recited in claim 27, wherein execution of the one or more sequences of instructions further causes the one or more processors to not perform the step of determining a different node than the closest node from among the plurality of nodes, which different node is determined to be a new closest node which is used to locate the particular object, if it is determined that the closest node is not available for communication.

29. The apparatus as recited in claim 27, wherein the plurality of node identifiers for the plurality of nodes are based on communication cost data such that a distance between node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes.

30. An apparatus for locating an object on a node in a computer network, comprising:

a network interface that is coupled to a network for communicating therewith a data packet;

one or more processors;

a computer-readable medium; and

one or more sequences of instructions stored in the computer-readable medium, which, when executed by the one or more processors, causes the one or more processors to carry out the steps of;

receiving node identifier data that indicates a plurality of node identifiers for a corresponding plurality of nodes in a computer network, wherein a distance between two node identifiers for a pair of nodes of the plurality of nodes is based on a cost of physically transferring data between the pair of nodes;

receiving object identifier data that indicates a particular object identifier that uniquely identifies a particular object;

determining a closest node among the plurality of nodes based on the particular object identifier and the plurality of node identifiers; and

locating the particular object through the closest node.

31. The apparatus as recited in claim 30, said step determining the closest node for a particular object that has a particular object identifier further comprising the steps of:

for each node identifier of the plurality of node identifiers, inputting the particular object identifier and the node identifier into a distance function that produces a distance between the node identifier and the object identifier;

determining a closest node identifier among the plurality of node identifiers which produces from the distance function a smallest distance to the object identifier; and

determining the closest node as a node that corresponds to the closest node identifier.

32. The apparatus as recited in claim 30, wherein execution of the one or more sequences of instructions further causes the one or more processors to carry out the steps of:

receiving, from a generator node among the plurality of nodes, object data indicating a new distributed object without an object identifier, and

determining a user node set of one or more nodes of the plurality of nodes most likely to retrieve the new distributed object; and

assigning a new object identifier to the new distributed object based on a user identifier set of one or more node identifiers corresponding to the user node set.

33. The apparatus as recited in claim 32, wherein:

said step of determining the user node set further comprises the step of including in the user node set the generator node, and

said step of assigning the new object identifier further comprises the steps of determining a particular distance and determining the object identifier so that a distance between the object identifier and the user identifier set is no greater than the particular distance.