Patent ID: 8284788
Filing Date: 2012-10-09
Classification: H04L

Abstract:
1. A method comprising: storing log(n) coordinates in a routing table within a non-transitory machine readable medium, 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.