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

• US 7,562,125 B2
• Filed: 02/02/2005
• Issued: 07/14/2009
• Est. Priority Date: 02/02/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Walker, Douglas Jay, Turner, Bryan
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): RICHARDSON, THOMAS W
• Application Number:
  US11/049,559
• Publication Number:
  US 20060173855A1
• Time in Patent Office: 1,623 Days
• Field of Search: 709/203, 709/216, 709/219, 709/241, 707/10
• US Class Current: 709/216
• 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 in a node identifier space 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, wherein a granularity of a coordinate in node identifier space is much finer than a separation between node identifiers for any two nodes;

for a particular object that has a particular object identifier, determining an object coordinate in node identifier space based on the particular object identifier and determining a closest node among the plurality of nodes based on the object coordinate and a plurality of different values for the coordinate for node identifiers corresponding to the plurality of nodes;

locating the particular object through the closest node;

wherein determining a particular node identifier further comprises;

receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

determining whether the neighbor set includes more than one node, wherein 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 the particular node identifier for the particular node within the neighbor identifier interval; and

for the particular node in the neighbor identifier interval;

determining a first random position in the neighbor identifier interval and a first measure of smoothness for a first set including a first random position 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 a second random position 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 the measure of smoothness is a measure of how evenly a set of node identifiers is distributed within the neighbor identifier interval.

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, 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.

4. The method as recited in claim 1, 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.

5. 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.

6. 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.

7. The method as recited in claim 6, 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.

8. A computer-readable volatile or non-volatile medium, storing 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:

determining a node identifier comprising;

receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

determining whether the neighbor set includes more than one node, wherein 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; and

for the particular node in the neighbor identifier interval;

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

determining a second random number in the neighbor identifier interval and a second measure of smoothness for a second set including a 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 number, wherein a measure of smoothness is a measure of how evenly a set of node identifiers is distributed within the neighbor identifier interval;

for a particular object that has a particular object identifier, determining an object coordinate in node identifier space based on the particular object identifier and determining a closest node among a plurality of nodes based on the object coordinate and a plurality of different values for the coordinate for the particular node identifiers corresponding to the plurality of nodes; and

locating the particular object through the closest node.

9. The computer-readable medium as recited in claim 8, further comprising:

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

determining the node identifier in a node identifier space 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, wherein a granularity of a coordinate in node identifier space is much finer than a separation between node identifiers for any two nodes.

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

processing means for determining a node identifier comprising;

receiving means for receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

processing means for determining whether the neighbor set includes more than one node, wherein 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;

for the particular node in the neighbor identifier interval;

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

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

processing means for determining whether the first measure of smoothness is more optimal than the second measure of smoothness;

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 number, wherein a measure of smoothness is a measure of how evenly a set of node identifiers is distributed within the neighbor identifier interval;

for a particular object that has a particular object identifier, processing means for determining an object coordinate in node identifier space based on the particular object identifier and determining a closest node among a plurality of nodes based on the object coordinate and a plurality of different values for the coordinate for the particular node identifiers corresponding to the plurality of nodes; and

processing means for locating the particular object through the closest node.

11. 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 volatile or non-volatile 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 in a node identifier space 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, wherein a granularity of a coordinate in node identifier space is much finer than a separation between node identifiers for any two nodes;

for a particular object that has a particular object identifier, determining an object coordinate in node identifier space based on the particular object identifier and determining a closest node among the plurality of nodes based on the object coordinate and a plurality of different values for the coordinate for node identifiers corresponding to the plurality of nodes;

locating the particular object through the closest node;

wherein determining a particular node identifier further comprises;

receiving data that indicates that a particular node is directly connected to a neighbor set of one or more nodes;

determining whether the neighbor set includes more than one node, wherein 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 the particular node identifier for the particular node within the neighbor identifier interval; and

for the particular node in the neighbor identifier interval;

determining a first random position in the neighbor identifier interval and a first measure of smoothness for a first set including a 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 a 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.

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

13. The apparatus as recited in claim 11, 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.

14. The apparatus as recited in claim 11, 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.

15. The apparatus as recited in claim 11, 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.

16. The apparatus as recited in claim 15, 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.

17. 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 volatile or non-volatile 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;

determining a node identifier for a particular node, comprising;

receiving data that indicates that the particular node is directly connected to a neighbor set of one or more nodes;

determining whether the neighbor set includes more than one node, wherein if it is determined that the neighbor set includes more than one node, then determine a neighbor identifier interval between the nodes in the neighbor set and determine a particular node identifier for the particular node within the neighbor identifier interval;

determining a first random position in the neighbor identifier interval and a first measure of smoothness for a first set including a first random position 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 a second random position 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 determine 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;

for a particular object that has a particular object identifier, determining an object coordinate in node identifier space based on the particular object identifier and determine a closest node among a plurality of nodes based on the object coordinate and a plurality of different values for the coordinate for the particular node identifiers corresponding to the plurality of nodes; and

locating the particular object through the closest node.