×

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
First Claim
Patent Images

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

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×