System and method for creating improved overlay network with an efficient distributed data structure

• US 7,613,796 B2
• Filed: 02/03/2003
• Issued: 11/03/2009
• Est. Priority Date: 09/11/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Saroiu, Stefan, Harvey, Nicholas J., Jones, Michael B., Theimer, Marvin M., Adya, Atul, Wolman, Alastair
• Primary Examiner(s): Pwu; Jeffrey
• Assistant Examiner(s): Baturay; Alicia
• Application Number:
  US10/356,961
• Publication Number:
  US 20040054807A1
• Time in Patent Office: 2,465 Days
• Field of Search: 709/239, 709/243, 709/220
• US Class Current: 709/220
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

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.

Claims

1. At least one computer storage medium storing instructions that, when executed on at least one processor, perform a method for creating an overlay network from a set of networked computers, the method comprising:

assigning each computer a different string name, the string name comprising at least one text string having at least one letter such that the string name can be ordered lexicographically;

assigning each computer a different number, wherein each number is unique over the set of networked computers and the distribution of numbers over computers is probabilistically uniform;

forming at least a base ring, the base ring having the set of networked computers as members, the set of networked computers in the base ring being logically ordered lexicographically by string name;

creating at least one routing table for each computer, wherein the at least one routing table includes two or more pointers, each of the two or more pointers pointing to a respective particular computer that is a different number of positions offset from the computer associated with the respective at least one routing table, a first pointer of the two or more pointers being based, at least in part, on a lexicographical distance between the computer and the respective particular computer to which the at least one pointer points such that the at least one routing table supports routing through a namespace comprising the string names of the set of networked computers;

wherein the first pointer in each computer'"'"'s at least one routing table points to an immediately following computer when the computers are ordered lexicographically by string name;

wherein a second pointer in each computer'"'"'s at least one routing table points to an immediately preceding computer when the computers are ordered lexicographically by string name;

wherein a third pointer in each computer'"'"'s at least one routing table points to a distant computer that is K positions ahead when the computers are ordered lexicographically by string name; and

wherein a fourth pointer in each computer'"'"'s at least one routing table points to a distant computer that is K positions behind when the computers are ordered lexicographically by string name.

2. The at least one computer storage medium of claim 1, wherein the string name is indicative of a domain of the respective computers such that computers that are on the same domain are adjacent to one another when ordered lexicographically by string name.

3. The at least one computer storage medium of claim 1, wherein the pointers are network addresses of computers.

4. The method of claim 3, wherein the network addresses are IP addresses, and wherein the overlay network comprises a subset of the computers connected to the Internet.

5. The at least one computer storage medium of claim 1, further comprising forming one or more subrings within the overlay network by adding additional addresses to each computer'"'"'s at least one routing table, wherein the additional addresses identify other computers belonging to the same subring, each of the one or more subrings having a respective subset of the set of networked computers.

6. The at least one computer storage medium of claim 1, wherein the computer string names are user email addresses.

7. The at least one computer storage medium of claim 1, wherein the computer string names are uniform resource locators (URLs).

8. The at least one computer storage medium of claim 1, wherein the computer string names are DNS (Domain Name Service) names.

9. The at least one computer storage medium of claim 1, further comprising creating a proximity table for each computer, wherein the proximity table stores one or more pointers to neighboring computers based on network location.

10. The at least one computer storage medium of claim 1, further comprising storing two or more leaf set pointers for each computer.

11. The at least one computer storage medium of claim 1, further comprising:

hashing a file'"'"'s name to obtain a globally unique identifier (GUID);

finding a computer on the overlay network with a closest number to the GUID; and

storing the file on that computer.

12. The at least one computer storage medium of claim 1, further comprising:

receiving a file name and identifying a computer on the overlay network whose string name most closely matches the file name; and

storing the file associated with the file name on the identified computer.

13. The at least one computer storage medium of claim 1, further comprising:

hashing a file'"'"'s name to obtain a globally unique identifier (GUID), wherein the file'"'"'s name includes a domain identifier prefix indicating which domain on the overlay network the file should be stored in;

finding the computer on the overlay network that has the closest number to the GUID of the computers on the overlay network with computer string names matching the domain identifier; and

storing the file on that computer.

14. The at least one computer storage medium of claim 1, further comprising receiving a file to store on the overlay network and performing constrained load balancing.

15. The at least one computer storage medium of claim 1, further comprising:

receiving a file to store on the overlay network; and

performing a constrained load balancing to store the file on a computer on the overlay network.

16. The at least one computer storage medium of claim 1, further comprising using the overlay network to implement a peer-to-peer network.

17. The at least one computer storage medium of claim 1, further comprising:

establishing intervals of the arbitrary string identifiers; and

choosing computers with desirable properties to fill those intervals.

18. The at least one computer storage medium of claim 17, wherein the desirable property is network proximity.

19. The at least one computer storage medium of claim 16, wherein the peer-to-peer network allows users to store data on a particular computer of the overlay network by specifying the particular computer using the particular computer'"'"'s string identifier.

20. The at least one computer storage medium of claim 1, wherein a network partition at an organizational boundary within the overlay network results in two disjoint, but internally connected and operationally smaller overlay networks.

21. The at least one computer storage medium of claim 20, further comprising updating the pointer table after the network partition is detected such that the local partition forms a complete overlay network.

22. The at least one computer storage medium of claim 20, further comprising updating the pointer table after the network partition is repaired and the individual partitioned overlay networks are rejoined.

23. The at least one computer storage medium method of claim 1, in which the computers'"'"' numbers are used to determine the pointers used in the routing table.

24. The at least one computer storage medium of claim 1, in which the computers'"'"' numbers are randomly generated.

25. The at least one computer storage medium of claim 1, in which prefixes of the computers'"'"' numbers are used to determine membership in a ring.

26. At least one computer storage medium storing instructions that when executed on at least one processor, perform a method for creating an overlay network from a set of networked computers, wherein each computer has an address, the method comprising:

assigning each computer a different string name, the string name comprising at least one text string having at least one letter such that the string name can be ordered lexicographically;

assigning each computer a different number; and

creating a table for each computer, wherein the table has two or more levels having respective level numbers h, wherein a first level has a level number h=0 and includes an address of an immediately following computer when the computers are ordered lexicographically by string name, wherein a second level includes an address of an immediately preceding computer when the computers are ordered lexicographically by string name, wherein a third level includes an address of a distant computer that is K positions ahead when the computers are ordered lexicographically by string name, wherein a fourth level includes an address of a distant computer that is K positions behind when the computers are ordered lexicographically by string name, and wherein subsequent levels of the table respectively include an address of a computer that is h^k computers away lexicographically, wherein k is a positive integer,

wherein the lexicographical order of the computers is determined by the computers'"'"' string names, and wherein the table supports routing through a namespace comprising the string names of the set of networked computers.

27. The at least one computer storage medium of claim 26, wherein the number associated with the computer is used to substantially evenly distribute computers into subrings, wherein each computer belonging to a particular subring has at least a pointer to the immediately neighboring computers in the subring when the computers in the subrings are ordered lexicographically according to computer string name.

28. The at least one computer storage medium of claim 26 further comprising:

determining whether a file is to be restricted to a set of computers on the overlay network sharing a common name prefix of the associated string name;

hashing a file'"'"'s filename to produce a globally unique identifier (GUID); and

searching the overlay network for the best matching computer, wherein each computer on the overlay network has an associated number, and wherein the best matching computer is determined by comparing the GUID and the associated number, wherein only computers sharing the common name prefix are considered if the file is to be restricted to the set of computers on the overlay network sharing the common name prefix.

29. The at least one computer storage medium of claim 28, wherein the method is implemented as an application level overlay network.

30. At least one computer storage medium storing instructions that, when executed on at least one processor, perform a method for managing an overlay network when two or more computers share a single physical location, the method comprising:

assigning each computer a different string name, the string name comprising at least one text string having at least one letter such that the string name can be ordered lexicographically;

storing only a partial routing table for some of the computers; and

storing a shared proximity table for the computers, wherein

each routing table includes two or more routing pointers,

each routing pointer points to a particular computer that is a different number of positions offset from the current computer when the set of networked computers is ordered lexicographically by string name,

each proximity table includes one or more proximity pointers, each of the one or more proximity pointers pointing to a particular computer that is a different number of network positions offset from the current computer when the set of networked computers is ordered according to their network distance from each other,

wherein the routing table supports routing through a namespace comprising the plurality of computer string names, and

wherein a first pointer in each computer'"'"'s at least one routing table points to an immediately following computer when the computers are ordered lexicographically by string name,

wherein a second pointer in each computer'"'"'s at least one routing table points to an immediately preceding computer when the computers are ordered lexicographically by string name,

wherein a third pointer in each computer'"'"'s at least one routing table points to a distant computer that is K positions ahead when the computers are ordered lexicographically by string name, and

wherein a fourth pointer in each computer'"'"'s at least one routing table points to a distant computer that is K positions behind when the computers are ordered lexicographically by string name.

31. A system including an overlay network comprising:

a plurality of computers interconnected via the overlay network in a plurality of ring levels ordered in a hierarchy, each ring at a successive level in the hierarchy including a subset of the plurality of computers included in a ring at a level higher up in the hierarchy, each of the plurality of computers having a respective string identifier comprising at least one text string having at least one letter such that the string identifier can be ordered lexicographically, the plurality of computers being ordered lexicographically within each of the plurality of ring levels,

wherein each of the plurality of computers comprises at least one memory device having stored thereon;

a proximity table to store pointers to other nodes connected via the overlay network such that routing may be performed in a namespace formed by the respective string identifiers, the proximity table storing the pointers based, at least in part, on a network distance between the computer associated with the proximity table and respective neighboring computers;

a routing table to store pointers to neighboring computers based, at least in part, on ring memberships and on a lexicographical distance between the computer associated with the routing table and respective neighboring computers;

wherein a first pointer in each computer'"'"'s at least one routing table points to an immediately following computer when the computers are ordered lexicographically by string name,

wherein a second pointer in each computer'"'"'s at least one routing table points to an immediately preceding computer when the computers are ordered lexicographically by string name,

wherein a third pointer in each computer'"'"'s at least one routing table points to a distant computer that is K positions ahead when the computers are ordered lexicographically by string name, and

wherein a fourth pointer in each computer'"'"'s at least one routing table points to a distant computer that is K positions behind when the computers are ordered lexicographically by string name.

32. The system of claim 31, further comprising maintaining the pointer tables for each computer in the overlay network as computers join or leave the overlay network.