Method for scalable routing with greedy embedding

A network comprising:

• a plurality of nodes that route packets between each other using coordinates in a router table, the router table being stored within a non-transitory machine readable medium, wherein the coordinates in the routing table are generated by constructing a greedy embedding that embeds a graph topology depicting connections between n nodes of a network into a geometric space so as to use greedy forwarding, using a method comprising
• generating a spanning tree out of a connection graph representing the connections between the n nodes of the network,
• decomposing the tree into at most n branches,
• assigning a set of geometric coordinates to vertices in the tree in an n-dimensional space,
• projecting the set of geometric coordinates onto a k-dimensional space, where k is less than n, to create the log(n) coordinates;
• and
• wherein the spanning tree is generated by each node attempting to generate the tree routed in itself, and further comprising announcing the tree to its neighbors using a tree message to have the neighbors join the tree or discard the message from the node.

A method comprising:

• constructing a greedy embedding in a polylogarhythmic dimensional Euclidian space to achieve routing through geometric routing, including embedding a topological graph of nodes in a network into a metric space in a way to preserve the connectivity property of nodes in the graph;
• using a routing table at each node in the network to route packets between nodes in the network using coordinates from the greedy embedding, the routing table being stored within a non-transitory machine readable medium;
• and
• wherein a spanning tree is generated by each node attempting to generate the tree routed in itself, and further comprising announcing the tree to its neighbors using a tree message to have the neighbors join the tree or discard the message from the node.

An article of manufacture having one or more non-transitory computer readable storage media storing instructions thereon which when executed by a system cause the system to perform a method comprising:

• storing log(n) coordinates in a routing table, where n is the number of nodes in a network, and further wherein the log(n) coordinates are generated by constructing a greedy embedding that embeds a graph topology depicting connections between n nodes of a network into a geometric space so as to use greedy forwarding by
• generating a spanning tree out of a connection graph representing the connections between the n nodes of the network,
• decomposing the tree into at most n branches,
• assigning a set of geometric coordinates to vertices in the tree in an n-dimensional space, and
• projecting the set of geometric coordinates onto a k-dimensional space, where k is less than n, to create the log(n) coordinates;
• routing packets via nodes of the network using the log(n) coordinates in the routing table;
• and
• wherein the spanning tree is generated by each node attempting to generate the tree routed in itself, and further comprising announcing the tree to its neighbors using a tree message to have the neighbors join the tree or discard the message from the node.

An article of manufacture having one or more non-transitory computer readable storage media storing instructions thereon which when executed by a system cause the system to perform a method comprising:

• constructing a greedy embedding in a polylogarhythmic dimensional Euclidian space to achieve routing through geometric routing, including embedding a topological graph of nodes in a network into a metric space in a way to preserve the connectivity property of nodes in the graph;
• using a routing table at each node in the network to route packets between nodes in the network using coordinates from the greedy embedding;
• and
• wherein a spanning tree is generated by each node attempting to generate the tree routed in itself, and further comprising announcing the tree to its neighbors using a tree message to have the neighbors join the tree or discard the message from the node.