Overlay network with efficient routing and recovery

• US 7,570,600 B1
• Filed: 12/17/2003
• Issued: 08/04/2009
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Jorapurkar, Girish, Kwiatkowski, Mark P., Slaughter, Gregory L., Saulpaugh, Thomas E.
• Primary Examiner(s): Cho; Hong
• Assistant Examiner(s): SOL, ANTHONY M
• Application Number:
  US10/738,431
• Time in Patent Office: 2,057 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 12/282 based on user interaction within the home receiver circuitry for displaying additional information being controlled by a remote control apparatus H04N21/42204
• CPC Class Codes: H04L 12/2834 Switching of information between an external network and a home network access arrangements H04L12/2856
• CPC Class Codes: H04L 2012/2841 Wireless
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 67/1044 Group management mechanisms management of multicast group membership H04L12/185; reconfiguring of node membership in a computing system to eliminate errors G06F11/1425
• 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

A network having a plurality of nodes interconnected by links (virtual communication channels) is disclosed. In one embodiment, the nodes may communicate with each other in a decentralized or peer-to-peer manner. A method for establishing the links among the nodes is disclosed. The links may be established such that the system is able to operate efficiently. In particular, the manner in which the nodes are interconnected by links may enable the system to efficiently route messages and efficiently recover from network failures.

Claims

1. A computer-readable memory medium storing program instructions executable to implement a method comprising:

determining an ordering for a plurality of N nodes such that the nodes are circularly ordered as nodes D₀, D₁, D₂, . . . D<sub>N−

1</sub>;

each node D_i in the plurality of nodes establishing a link to X other nodes chosen as nodes D_i+1, D_i+2, . . . D_i+X, wrapping to D₀ if necessary; and

each node D_j in at least a subset of the plurality of nodes establishing a link with one or more additional chosen nodes not in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+x; and

for each node D_j in the at least the subset, each node in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+x establishing a link with the one or more additional nodes chosen by the node D_j.

2. The computer-readable memory medium of claim 1,

wherein said each node D_j in the at least the subset establishing a link:

with one or more additional chosen nodes not in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2 . . . D_j+X comprises each node D_j in the at least the subset establishing a link with one or more randomly chosen nodes not in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+X.

3. The computer-readable memory medium of claim 2, wherein said each node D_j in the at least the subset establishing a link with one or more randomly chosen nodes comprises each node D_j in the at least the subset establishing a link with exactly one randomly chosen node.

4. The computer-readable memory medium of claim 1, wherein the plurality of nodes utilize the established links to communicate in a peer-to-peer manner.

5. The computer-readable memory medium of claim 1, wherein the nodes are circularly ordered so that node D_N−

1 follows node D₀ in the ordering.

6. The computer-readable memory medium of claim 1, wherein the method implemented by the program instructions further comprises:

selecting the nodes for the at least the subset of the plurality of nodes such that the at least the subset includes nodes whose position in the ordering is a multiple of 2X.

7. The computer-readable memory medium of claim 1, wherein X is at least eighty percent smaller than N.

8. The computer-readable memory medium of claim 1,

wherein each node in the plurality of nodes has a unique node ill;

wherein said determining the ordering comprises determining an ordering based on the node IDs.

9. The computer-readable memory medium of claim 8, wherein the node IDs are capable of being ordered;

wherein said determining the ordering based on the node IDs comprises ordering the node IDs;

wherein the node with the first node ID in the ordering is selected as node D₀, wherein the node with the second node ID in the ordering is selected as node D₁ and so on, up to the node with the highest node ID in the ordering being selected as node D<sub>N−

1</sub>.

10. The computer-readable memory medium of claim 1, wherein each link between two nodes comprises a virtual communication channel between the two nodes.

11. The computer-readable memory medium of claim 1, wherein the established links comprise one or more TCP links and/or one or more UDP links.

12. The computer-readable memory medium of claim 1, wherein the plurality of nodes are interconnected in a local area network (LAN).

13. The computer-readable memory medium of claim 1, wherein the method implemented by the program instructions further comprises:

one or more nodes in the plurality of nodes establishing one or more additional links to one or more other nodes.

14. The computer-readable memory medium of claim 1, wherein the established links enable a message to be routed from any given first node to any given second node with an average efficiency on the order of log(N) message hops.

15. The computer-readable memory medium of claim 1, wherein the established links enable recovery operations to be performed in the event of node failures with an average efficiency on the order of 3 message hops or less.

16. A computer-readable memory medium storing program instructions executable to implement a method comprising:

determining an ordering for a plurality of N nodes such that the nodes are circularly ordered as nodes D₀, D₁, D₂ . . . D<sub>N−

1</sub>;

each node D_i in the plurality of nodes establishing a link to X other nodes chosen as D_i+1, D_i+2, . . . D_i+X, wrapping to D₀ if necessary; and

for each node D_j in at least a subset of the plurality of nodes;

the node Dj establishing a link with one or more randomly chosen nodes not in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+X;

each node in the set D<sub>j−

x</sub>, D<sub>j−

X+1</sub> . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+X establishing a link with the one or more nodes randomly chosen by the node D_j.

17. A computer-readable memory medium storing program instructions executable to implement a method comprising:

determining an ordering for a plurality of nodes such that the ordering has a first node, a second node, and so on, up to a last node, wherein the ordering is circular so that the first node follows the last node in the ordering;

each node establishing one or more links to one or more nodes immediately following the node in the ordering; and

for each respective node of at least a subset of the plurality of nodes, the respective node establishing one or more links to one or more randomly chosen nodes and each of the one or more nodes immediately following the respective node also establishing a link to each of the one or more nodes randomly chosen by the respective node.

18. A system comprising:

a plurality of N nodes;

wherein each node is operable to determine an ordering for the plurality of N nodes such that the nodes are circularly ordered as nodes D₀, D₁, D₂, . . . D<sub>N−

1</sub>;

wherein each node D_i in the plurality of nodes is operable to establish a link to X other nodes chosen as nodes D_i+1, D_i+2, . . . D_i+X, wrapping to D₀ if necessary; and

wherein each node D_j in at least a subset of the plurality of nodes is operable to establish a link with one or more additional chosen nodes not in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub> . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+x; and

wherein for each node D_j in the at least the subset each node in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+X is operable to establish a link with the one or more additional nodes chosen by the node D_j.

19. The system of claim 18,

wherein said each node D_j in the at least the subset establishing a link with one or more additional chosen nodes not in the set D_j−

X, D<sub>j−

X+1</sub>, . . . D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+X comprises each node D_j in the at least the subset establishing a link with one or more randomly chosen nodes not in the set D<sub>j−

X</sub>, D<sub>j−

X+1</sub>, . . . D<sub>j−

1</sub>, D_j+1, D_j+2, . . . D_j+X.

20. The system of claim 19,

wherein said each node D_j in the at least the subset establishing a link with one or more randomly chosen nodes comprises each node D_j in the at least the subset establishing a link with exactly one randomly chosen node.

21. The system of claim 18,

wherein the plurality of nodes are operable to utilize the established links to communicate in a peer-to-peer manner.

22. The system of claim 18,

wherein the at least the subset includes nodes whose position in the ordering is a multiple of 2X.

23. The system of claim 18,

wherein X is at least eighty percent smaller than N.

24. The system of claim 18,

wherein each node in the plurality of nodes has a unique node ID;

wherein said determining the ordering comprises determining an ordering based on the node IDs.

25. The system of claim 18,

wherein each link:

between two nodes comprises a virtual communication channel between the two nodes.

26. The system of claim 18,

wherein the network comprises a local area network (LAN), wherein the LAN interconnects the plurality of nodes.

27. The system of claim 18,

wherein one or more nodes in the plurality of nodes are operable to establish one or more additional links to one or more other nodes.