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

• US 20040249970A1
• Filed: 06/06/2003
• Published: 12/09/2004
• Est. Priority Date: 06/06/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rowstron, Antony, Castro, Miguel Oom Temudo de
• Granted Patent: US 7,539,771 B2
• Time in Patent Office: Days
• 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 comprising:

assigning a peer-to-peer overlay node a node identifier defined in a hierarchical namespace designating one or more organizational levels, wherein an organizational boundary in the node identifier is aligned with a routing boundary of the node identifier.

2. The method of claim 1 wherein the organizational boundary of the node identifier is aligned with the routing boundary of digits in the node identifier in a base used for prefix-matching routing.

3. The method of claim 1 wherein the node identifier is one of a plurality of node identifiers defined in the hierarchical namespace and further comprising:

defining a structured peer-to-peer overlay referencing the plurality of node identifiers defined in the hierarchical namespace.

4. The method of claim 1 wherein the node identifier is one of a plurality of node identifiers defined in the hierarchical namespace and further comprising:

defining a structured peer-to-peer overlay referencing the plurality of node identifiers defined in the hierarchical namespace and using prefix-matching to route between overlay nodes.

5. The method of claim 1 wherein the node identifier includes a sequence of characters, each character includes e bits, prefix-matching routing is performed in base 2^b, and e is a multiple of b.

6. The method of claim 1 further comprising:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace.

7. The method of claim 1 further comprising:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers include a domain prefix and a random string.

8. The method of claim 1 further comprising:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers include a domain prefix, a special marker character, and a random string.

9. The method of claim 1 further comprising:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers includes a domain prefix, a special marker character, and a random string, the special marker character being ineligible for use in a node identifier.

10. The method of claim 1 further comprising:

creating a routing table for the peer-to-peer overlay node that includes one or more node identifiers defined in the hierarchical namespace.

11. The method of claim 1 further comprising:

informing other peer-to-peer overlay nodes of the node identifier of the peer-to-peer overlay node.

12. A computer program product encoding a computer program for executing on a computer system a computer process, the computer process comprising:

assigning a peer-to-peer overlay node a node identifier defined in a hierarchical namespace designating one or more organizational levels, wherein an organizational boundary in the node identifier is aligned with a routing boundary of the node identifier.

13. The computer program product of claim 12 wherein the organizational boundary of the node identifier is aligned with the routing boundary of digits in the node identifier in a base used for prefix-matching routing.

14. The computer program product of claim 12 wherein the node identifier is one of a plurality of node identifiers defined in the hierarchical namespace and wherein the computer process further comprises:

defining a structured peer-to-peer overlay referencing the plurality of node identifiers defined in the hierarchical namespace.

15. The computer program product of claim 12 wherein the node identifier is one of a plurality of node identifiers defined in the hierarchical namespace and wherein the computer process further comprises:

defining a structured peer-to-peer overlay referencing the plurality of node identifiers defined in the hierarchical namespace and using prefix-matching to route between overlay nodes.

16. The computer program product of claim 12 wherein the node identifier includes a sequence of characters, each character includes e bits, prefix-matching routing is performed in base 2^b, and e is a multiple of b.

17. The computer program product of claim 12 wherein the computer process further comprises:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace.

18. The computer program product of claim 12 wherein the computer process further comprises:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers include a domain prefix and a random string.

19. The computer program product of claim 12 wherein the computer process further comprises:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers include a domain prefix, a special marker character, and a random string.

20. The computer program product of claim 12 wherein the computer process further comprises:

assigning the peer-to-peer overlay node one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers includes a domain prefix, a special marker character, and a random string, the special marker character being ineligible for use in a node identifier.

21. The computer program product of claim 12 wherein the computer process further comprises:

creating a routing table for the peer-to-peer overlay node that includes one or more node identifiers defined in the hierarchical namespace.

22. The computer program product of claim 12 wherein the computer process further comprises:

informing other peer-to-peer overlay nodes of the node identifier of the peer-to-peer overlay node.

23. A structured peer-to-peer overlay referencing a plurality of peer-to-peer overlay nodes, each peer-to-peer overlay node being associated with a node identifier defined in a hierarchical namespace designating one or more organizational levels, wherein an organizational boundary in the node identifier is aligned with a routing boundary of the node identifier.

24. The structured peer-to-peer overlay of claim 23 wherein the organizational boundary of the node identifier is aligned with the routing boundary of digits in the node identifier in a base used for prefix-matching routing.

25. The structured peer-to-peer overlay of claim 23 wherein the node identifier includes a sequence of characters, each character includes e bits, prefix-matching routing is performed in base 2^b, and e is a multiple of b.

26. The structured peer-to-peer overlay of claim 23 wherein each peer-to-peer overlay node is further associated with one or more virtual node identifiers defined in the hierarchical namespace.

27. The structured peer-to-peer overlay of claim 23 wherein each peer-to-peer overlay node is further associated with one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers includes a domain prefix and a random string.

28. The structured peer-to-peer overlay of claim 23 wherein each peer-to-peer overlay node is further associated with one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers includes a domain prefix, a special marker character, and a random string.

29. The structured peer-to-peer overlay of claim 23 wherein each peer-to-peer overlay node is further associated with one or more virtual node identifiers defined in the hierarchical namespace, wherein the one or more virtual node identifiers includes a domain prefix, a special marker character, and a random string, the special marker character being ineligible for use in a node identifier.

30. A method comprising:

generating a data key incorporating a domain prefix designating at least one organizational level in a peer-to-peer overlay; and

routing data associated with the data key through the peer-to-peer overlay toward a network node having a node identifier that has the longest prefix match in the peer-to-peer overlay to the data key, the node identifier being defined in a hierarchical namespace designating one or more organizational levels.

31. The method of claim 30 wherein the data key further incorporates a data identifier derived from content of the data.

32. The method of claim 30 wherein the data key further incorporates a data identifier derived from a descriptor of the data.

33. The method of claim 30 wherein the data key further incorporates a data identifier generated by hashing content of the data.

34. The method of claim 30 wherein the data key further incorporates a data identifier generated by hashing a descriptor of the data.

35. The method of claim 30 wherein the data key is generated by concatenating the domain prefix to the data identifier.

36. The method of claim 30 wherein the data key further incorporates a special marker character ineligible for use in the node identifier of the network node.

37. The method of claim 30 wherein the node identifier includes a sequence of characters, each character includes e bits, prefix-matching routing is performed in base 2^b, and e is a multiple of b.

38. A computer program product encoding a computer program for executing on a computer system a computer process, the computer process comprising:

generating a data key incorporating a domain prefix designating at least one organizational level in a peer-to-peer overlay; and

routing data associated with the data key through the peer-to-peer overlay toward a network node having a node identifier that has the longest prefix match in the peer-to-peer overlay to the data key, the node identifier being defined in a hierarchical namespace designating one or more organizational levels.

39. The computer program product of claim 38 wherein the data key further incorporates a data identifier derived from content of the data.

40. The computer program product of claim 38 wherein the data key further incorporates a data identifier derived from a descriptor of the data.

41. The computer program product of claim 38 wherein the data key further incorporates a data identifier generated by hashing content of the data.

42. The computer program product of claim 38 wherein the data key further incorporates a data identifier generated by hashing a descriptor of the data.

43. The computer program product of claim 38 wherein the data key is generated by concatenating the domain prefix to the data identifier.

44. The computer program product of claim 38 wherein the data key further incorporates a special marker character ineligible for use in the node identifier of the network node.

45. The computer program product of claim 38 wherein the node identifier includes a sequence of characters, each character includes e bits, prefix-matching routing is performed in base 2^b, and e is a multiple of b.

46. A peer-to-peer overlay node comprising:

a data key generator creating a data key incorporating a domain prefix designating at least one organizational level in a peer-to-peer overlay; and

a routing module routing data associated with the data key through the peer-to-peer overlay toward a network node having a node identifier that has the longest prefix match in the peer-to-peer overlay to the data key, the node identifier being defined in a hierarchical namespace designating one or more organizational levels.

47. The peer-to-peer overlay node of claim 46 wherein the data key further incorporates a data identifier derived from content of the data.

48. The peer-to-peer overlay node of claim 46 wherein the data key further incorporates a data identifier derived from a descriptor of the data.

49. The peer-to-peer overlay node of claim 46 wherein the data key further incorporates a data identifier generated by hashing content of the data.

50. The peer-to-peer overlay node of claim 46 wherein the data key further incorporates a data identifier generated by hashing a descriptor of the data.

51. The peer-to-peer overlay node of claim 46 wherein the data key is generated by concatenating the domain prefix to the data identifier.

52. The peer-to-peer overlay node of claim 46 wherein the data key further incorporates a special marker character ineligible for use in the node identifier of the network node.

53. The peer-to-peer overlay node of claim 46 wherein the node identifier includes a sequence of characters, each character includes e bits, prefix-matching routing is performed in base 2^b, and e is a multiple of b.