Network routing
First Claim
1. A method comprising:
- assigning a fixed, location independent node identifier to each of a plurality of nodes in a physical network;
identifying virtual neighbor nodes of the plurality of nodes in a virtual ring based on the node identifiers;
maintaining at least one routing path in the physical network between at least two virtual neighbor nodes;
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;
routing a message between any pair of the plurality nodes using the at least one routing path between virtual neighbor nodes;
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;
wherein setting up the 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.
1 Assignment
0 Petitions
Accused Products
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.
26 Citations
19 Claims
-
1. A method comprising:
-
assigning a fixed, location independent node identifier to each of a plurality of nodes in a physical network; identifying virtual neighbor nodes of the plurality of nodes in a virtual ring based on the node identifiers; maintaining at least one routing path in the physical network between at least two virtual neighbor nodes; 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; routing a message between any pair of the plurality nodes using the at least one routing path between virtual neighbor nodes; 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; wherein setting up the 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer readable storage medium or volatile or non-volatile memory storing computer instructions which when executed by a computer, having stored thereon a routing data structure, the structure comprising:
-
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; 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; a third data field containing data representing a second node identifier of a physical neighbor node of the routing node within the network topology; 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; 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. - View Dependent Claims (14, 15, 16, 17)
-
-
18. One or more computer readable storage media or volatile or non-volatile memory devices storing computer instructions, the computer instructions which when executed by a computer comprising:
-
means for routing a message through a network topology based on a fixed and location independent node identifier; means for routing a message through a virtual name space based on the fixed and location independent node identifier; means for determining at least one physical neighbor node within the network topology; means for determining a state of the at least one physical neighbor node within the network topology; means for determining at least one virtual neighbor node within a name space of the node identifier; means for estimating a link quality of a link between two physical neighbor nodes, such that the means for estimating a link quality includes a link quality indicator which may be a numerical indicator of the quality of the link between the two physical neighbor nodes; and means for setting up a route between virtual neighbor nodes. - View Dependent Claims (19)
-
Specification