Network routing

• US 20060039371A1
• Filed: 04/28/2005
• Published: 02/23/2006
• Est. Priority Date: 08/19/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Castro, Miguel, Caesar, Matthew, Rowstron, Antony Ian Taylor
• Granted Patent: US 7,715,396 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

To reduce the dependency of overlay networks on underlay networks to route messages, a virtual ring routing architecture may be formed that leverages the design of the overlay network to achieve their desirable scaling and robustness properties but also reduce the dependency on any underlay network to setup and maintain connectivity. More particularly, each node may have a single, fixed, location independent node identifier, to organize the nodes into a virtual ring. The connectivity between nodes through the actual network topology may be formed by a plurality of nodes in the virtual ring by maintaining connectivity to those nodes identified as virtual neighbor nodes within the virtual ring. The path segments defining communication connections between virtual neighbor nodes may be used to route messages between any pair of nodes in the network and may reduce route discovery overhead, reduce delay in transmission, and reduce or eliminate flooding to setup or maintain the path segments.

Claims

1. A method comprising:

a) assigning a fixed, location independent node identifier to each of a plurality of nodes in a physical network;

b) identifying virtual neighbor nodes of the plurality of nodes in a virtual ring based on the node identifiers;

c) maintaining at least one routing path in the physical network between at least two virtual neighbor nodes;

d) setting up a new routing path in the physical network between the at least two other virtual neighbor nodes using the at least one routing path between the at least two virtual neighbor nodes;

e) routing a message between any pair of the plurality nodes using the at least one routing path between virtual neighbor nodes; and

f) routing a message having a key to a receiving node having a node identifier closest to the key using the at least one routing path between virtual neighbor nodes.

2. The method of claim 1, wherein setting up new routing paths includes identifying a first physical neighbor node of a first virtual neighbor node, generating a setup request message, and sending the setup request message from the first virtual neighbor node to a second virtual neighbor node through the first physical neighbor node.

3. The method of claim 2, wherein generating the setup request message includes generating the setup request message to include a first node identifier of the first virtual neighbor node, a second node identifier for the second virtual neighbor node, and a virtual neighbor node set indicator including at least one other virtual neighbor node of the first virtual neighbor node.

4. The method of claim 2, wherein identifying a first physical neighbor node includes receiving a hello message from the first physical neighbor node.

5. The method of claim 4, wherein the hello message includes a first physical neighbor node set including the first node identifier of the first virtual neighbor node and a first state indicator indicating a state of the first virtual neighbor node determined by the first physical neighbor node.

6. The method of claim 5, wherein the first state indicator indicates a state selected from the group consisting of Linked, Failed, and Pending.

7. The method of claim 6, further comprising updating at the first neighbor node a second state indicator of the first physical neighbor node based on the first state indicator of the hello message.

8. The method of claim 7, wherein updating includes updating the second state indicator to Pending if a stored second state indicator is Missing and the first state indicator is Missing, if the first state indicator is Pending and a stored second state indicator is Failed, and if the first state indicator is Failed and a stored second state indicator is one of Pending and Failed;

wherein updating includes updating the second state indicator to Linked if the first state indicator is Pending and a stored second state indicator is one of Linked, Pending and Missing, if the first state indicator is Linked and a stored second state indicator is one of Linked and Pending; and

wherein updating includes updating the second state indicator to Failed if the first state indicator is Missing and a stored second state indicator is one of Linked and Failed, if the first state indicator is Failed and a stored second state indicator is one of Missing and Linked, and if the first state indicator is Linked and a stored second state indicator is one of Missing and Failed.

9. The method of claim 8, wherein the hello message includes a fourth node identifier of a fourth physical neighbor node of the first physical neighbor node, and a fourth state indicator indicating a state of the fourth node as determined by the first physical neighbor node, the first virtual neighbor node updating a fifth state of the fourth node as determined by the first virtual neighbor node based on the fourth state indicator and a stored fifth stat indicator of the fifth node.

10. The method of claim 9, further comprising storing the fourth node identifier as a near neighbor node associated with a node identifier of the first physical neighbor node.

11. The method of claim 1, wherein maintaining at least one routing path includes storing, the first virtual neighbor node, a next path segment indicator for each virtual neighbor node of the first virtual neighbor node.

12. The method of claim 1, wherein maintaining at least one routing path includes determining if at least a portion of the path between the first virtual neighbor node and the second virtual neighbor node has failed.

13. The method of claim 12, wherein maintaining at least one routing path includes sending a path tear down message to at least one of the first virtual neighbor node and the second virtual neighbor node through the first physical neighbor node to tear down the path.

14. A computer readable medium of a routing node having stored thereon a routing data structure comprising:

a) a first data field containing data representing a first node identifier of a virtual neighbor node of the routing node within a node identifier name space;

b) a second data field associated with the first data field and containing data representing a first next path segment identifier indicating a first path segment through a network topology for a message to be routed to the first node identifier;

c) a third data field containing data representing a second node identifier of a physical neighbor node of the routing node within the network topology;

d) a fourth data field containing data representing a third node identifier of an end-point node of a path through the network topology which includes the routing node as an intermediate node;

e) a fifth data field associated with the fourth data field and containing data representing a second next path segment identifier indicating a second path segment through the network topology for a message to be routed to the third node identifier, each of the first node identifier, the second node identifier, and the third node identifier being fixed and location-independent indications of an associated node.

15. The computer readable medium of claim 14, wherein the first path segment identifier and the second path segment identifier include a node identifier of a physical neighbor node of the routing node.

16. The computer readable medium of claim 14, further comprising a sixth data field associated with the fourth data field, the sixth data field containing data representing a fourth node identifier of another end-point of the path, and a seventh data field associated with the sixth data field, the seventh data field containing data representing a third next path segment identifier through the network topology for a message to be routed to the fourth node identifier.

17. The computer readable medium of claim 14, further comprising an eighth data field associated with the third data field, the eighth data field containing data representing a state of the physical neighbor node having the second node identifier.

18. The computer readable medium of claim 14, further comprising a ninth data field associated with the fourth data field, the ninth data field containing data representing a next next path segment identifier indicating a fourth path segment through the network topology which is immediately after the second path segment in routing a message to the third node identifier.

19. One or more computer readable media having computer-executable components comprising:

a) means for routing a message through a network topology based on a fixed and location independent node identifier;

b) means for routing a message through a virtual name space based on the fixed and location independent node identifier;

c) means for determining at least one physical neighbor node within the network topology;

d) means for determining a state of the at least one physical neighbor node within the network topology;

e) means for determining at least one virtual neighbor node within a name space of the node identifier; and

f) means for setting up a route between virtual neighbor nodes.

20. The computer readable media of claim 19, further comprising at least one of means for estimating a link quality of a link between two physical neighbor nodes, means for tearing down a path between two virtual neighbor nodes, means for locally repairing a failed link in the network topology, and means for storing the set up route, the state of the at least one physical neighbor node, a node identifier of the at least one physical neighbor node, and a node identifier of the at least one virtual neighbor node.