System and method for creating improved overlay network with an efficient distributed data structure
First Claim
Patent Images
1. A method for creating an overlay network from a set of networked nodes, the method comprising:
- assigning each node a different name;
assigning each node a different number, wherein each number is unique over the set of networked nodes and the distribution of numbers over nodes is probabilistically uniform;
creating a routing table for each node, wherein each table includes two or more pointers, wherein each pointer points to a particular node that is a different number of positions offset from the current node when the set of networked nodes are ordered lexicographically by name.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for using skip nets to build and maintain overlay networks for peer-to-peer systems. A skip net is a distributed data structure that can be used to avoid some of the disadvantages of distributed hash tables by organizing data by key ordering. Skip nets can use logarithmic state per node and probabilistically support searches, insertions and deletions in logarithmic time.
349 Citations
46 Claims
-
1. A method for creating an overlay network from a set of networked nodes, the method comprising:
-
assigning each node a different name;
assigning each node a different number, wherein each number is unique over the set of networked nodes and the distribution of numbers over nodes is probabilistically uniform;
creating a routing table for each node, wherein each table includes two or more pointers, wherein each pointer points to a particular node that is a different number of positions offset from the current node when the set of networked nodes are ordered lexicographically by name. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
20. A method for creating an overlay network from a set of networked nodes, wherein each node has an address, the method comprising:
-
assigning each node a different name;
assigning each node a different number; and
creating a table for each node, wherein the table has two or more levels having respective level numbers h, wherein the first level has a level number h=0 and includes the address of a lexicographically neighboring node, and wherein subsequent levels of the table respectively include the address of a node that is hk nodes away lexicographically, wherein k is a positive integer, wherein the lexicographical order of the nodes is determined by the nodes'"'"' names. - View Dependent Claims (21)
-
-
22. A method for organizing networked nodes in a manner suitable for a peer-to-peer application, the method comprising:
-
assigning a different lexicographical name to each node;
assigning a different number to each node;
creating a table for each node;
arranging the nodes into a logical ring lexicographically according to each node'"'"'s name, wherein each node'"'"'s table stores the address of one or more neighboring nodes on the ring;
dividing the nodes into two logical sub-rings, wherein a portion of the nodes are in each sub-ring, wherein each node'"'"'s table stores the address of one or more nodes on the sub-ring; and
repeating said dividing one or more times for each sub-ring having more than one node. - View Dependent Claims (23, 24, 25)
-
-
26. A method for storing a file on an overlay network, the method comprising:
-
determining whether the file is to be restricted to a set of nodes on the overlay network sharing a common name prefix;
hashing the file'"'"'s filename to produce a globally unique identifier (GUID);
searching the overlay network for the best matching node, wherein each node on the overlay network has an associated number, and wherein the best matching node is determined by comparing the GUID and the associated number, wherein only nodes sharing the common name prefix are considered if the file is to be restricted to the set of nodes on the overlay network sharing the common name prefix. - View Dependent Claims (27)
-
-
28. A data structure for creating an overlay network having a plurality of nodes, the data structure comprising:
a table of addresses, wherein the table is configured to be stored on a given node of the overlay network, wherein each address identifies a node at a different constant offset from the given node when the nodes are ordered lexicographically based on lexicographical node names. - View Dependent Claims (29, 30, 31)
-
32. A method for managing an overlay network when two or more nodes share a single physical location, the method comprising:
-
assigning each node a different lexicographical name;
storing only a partial routing table for some of the nodes;
storing a shared proximity table for the nodes, wherein each routing table includes two or more routing pointers, wherein each routing pointer points to a particular node that is a different number of positions offset from the current node when the set of networked nodes are ordered lexicographically by name, wherein each proximity table includes one or more proximity pointers, and wherein each proximity pointer points to a particular node that is a different number of network positions offset from the current node when the set of networked nodes are ordered according to their network distance from each other.
-
-
33. A method for creating an overlay network for a plurality of nodes, the method comprising:
-
assigning a different arbitrary string identifier to each node;
creating a pointer table for each node, wherein each table includes two or more pointers, wherein each pointer points to a particular node that is a different number of positions offset from the current node when the set of networked nodes are ordered lexicographically according to the arbitrary string identifiers. - View Dependent Claims (34)
-
-
43. A method for creating an overlay network from a set of networked nodes, the method comprising:
-
assigning each node a different name;
assigning each node a different number, wherein each number is unique over the set of networked nodes and the distribution of numbers over nodes is probabilistically uniform;
creating a routing table for each node, wherein each table includes one or more pointers, wherein each pointer points to a particular node that is a different number of positions offset from the current node when the set of networked nodes are ordered lexicographically by name. - View Dependent Claims (44, 45, 46)
-
Specification