Organizational locality in prefix-based structured peer-to-peer overlays

• US 7,539,771 B2
• Filed: 06/06/2003
• Issued: 05/26/2009
• Est. Priority Date: 06/06/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: de Castro, Miguel Oom Temudo, Rowstron, Antony
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): Bayard; Djenane M
• Application Number:
  US10/456,312
• Publication Number:
  US 20040249970A1
• Time in Patent Office: 2,181 Days
• Field of Search: 709/238, 709/220, 709/245, 709/241, 709/242, 709/239
• US Class Current: 709/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/50 Address allocation
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

Content and/or Path locality may be obtained using DHT protocols by assigning network nodes with individual node identifiers (IDs) in a hierarchical namespace. The hierarchical node IDs may be assigned to reflect organizational boundaries within the network. Therefore, with the structured overlay defined using these hierarchically assigned node IDs, a routing algorithm that uses prefix-matching can provide path locality. Furthermore, a domain prefix may be combined with data identifier derived from the data itself to create an enhanced data key. The use of the enhanced data key with a DHT protocol in this structured overlay can provide content locality.

Claims

1. A method to provide path locality when routing a message in a peer-to-peer network, comprising:

assigning a hierarchical node identifier to each of a plurality of peer-to-peer overlay nodes, wherein each hierarchical node identifier that corresponds to each of the plurality of peer-to-peer overlay nodes designates one or more organizational levels; and

routing a message between two overlay nodes of the plurality of peer-to-peer overlay nodes such that the message is routed only through nodes in the plurality of peer-to-peer overlay nodes, wherein the message stays within an organization level defined by the hierarchical node identifiers of the two overlay nodes, wherein the message is routed between the two overlay nodes by performing prefix-matching using the hierarchical node identifiers of at least one of the two overlay nodes, routing the message between two overlay nodes including, at each sending node along a path through which the message is routed between the two overlay nodes;

determining a data key of the message;

when the data key is within a range of nodes in a leaf set of the sending node,

determining a number of nodes of the leaf set having a longest prefix match with the data key,

when the number is one, routing the message to a first node of the leaf set having the longest prefix match with the data key, and

when the number is greater than one, determining, from a second set of nodes of the leaf set having the longest prefix match with the data key, a second node of the leaf set having a minimal numerical distance between the data key and a second node identifier of the second node, and routing the message to the second node of the leaf set; and

when the data key is not within the range of nodes in the leaf set,

determining a first shared prefix length shared by the data key and the sending node,

when a routing table associated with the sending node includes a potential receiving node having a second shared prefix length shared by the potential receiving node, the second shared prefix length being larger than the first shared prefix length, routing the message to the potential receiving node, and

when the routing table does not include the potential receiving node having the second shared prefix length, routing the message to a second potential receiving node, the second potential receiving node having a third shared prefix length shared by the data key and the second potential receiving node, the third shared prefix length being equal to the first shared prefix length, and the second potential receiving node having a second potential receiving node identifier that is numerically closer to the data key than a sending node identifier of the sending node.

2. The method of claim 1, wherein the node identifier is independent from an IP address of the peer-to-peer overlay node.

3. A method to provide content locality when routing a message in a peer-to-peer network, comprising:

assigning a hierarchical node identifier to each of a plurality of peer-to-peer overlay nodes, wherein each hierarchical node identifier that corresponds to each of the plurality of peer-to-peer overlay nodes designates one or more organizational levels; and

generating an enhanced data key by incorporating a domain prefix into a data key of the message; and

routing a message between two overlay nodes of the plurality of peer-to-peer overlay nodes such that the message is routed only through nodes in the plurality of peer-to-peer overlay nodes, wherein the message stays within an organization level defined by the hierarchical node identifiers of the two overlay nodes, wherein the message is routed between the two overlay nodes by looking up the domain prefix in the enhanced data key of the message, routing the message between two overlay nodes including, at each sending node along a path through which the message is routed between the two overlay nodes;

determining a data key of the message;

when the data key is within a range of nodes in a leaf set of the sending node, a first half of the leaf set including numerically closest larger node identifiers and a second half of the leaf set including numerically closest smaller node identifiers,

determining a number of nodes of the leaf set having a longest prefix match with the data key,

when the number is one, routing the message to a first node of the leaf set having the longest prefix match with the data key, and

when the number is greater than one, determining, from a second set of nodes of the leaf set having the longest prefix match with the data key, a second node of the leaf set having a minimal numerical distance between the data key and a second node identifier of the second node, and routing the message to the second node of the leaf set; and

when the data key is not within the range of nodes in the leaf set,

determining a first shared prefix length shared by the data key and the sending node,

when a routing table associated with the sending node includes a potential receiving node having a second shared prefix length shared by the potential receiving node, the second shared prefix length being larger than the first shared prefix length, routing the message to the potential receiving node, and

when the routing table does not include the potential receiving node having the second shared prefix length, routing the message to a second potential receiving node, the second potential receiving node having a third shared prefix length shared by the data key and the second potential receiving node, the third shared prefix length being equal to the first shared prefix length, and the second potential receiving node having a second potential receiving node identifier that is numerically closer to the data key than a sending node identifier of the sending node.

4. The method of claim 3, wherein the node identifier is independent from an IP address of the peer-to-peer overlay node.

5. The method of claim 3, wherein the enhanced data key is used to place objects within an organization.