Network routing
First Claim
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.
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.
214 Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18)
-
-
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. - View Dependent Claims (20)
-
Specification