Patent ID: 8310931
Filing Date: 2012-11-13
Classification: H04L

Abstract:
1. A computer implemented method for inferring network link topology comprising: receiving an address of a seed node in a network of connected nodes; initializing a set of links of the network and a set of monitors of the network; refining, iteratively beginning at the seed node, the set of links and the set of monitors of the network, wherein each iteration comprises inferring at least one of a local topology link from routing information and distance information of a current node and a remote topology link from routing information of the set of monitors, wherein at least one local link (m, j) is inferred between nodes m and j, without querying either node m or j for connectivity information, upon determining that a next-hop (m, n)=j, such that a w(m, j)=d(m, j), wherein n is a node, w is a weight of the link, and d is a distance, and wherein at least one remote link (i, j) is inferred between nodes i and j, without querying either node i or j for connectivity information, upon determining that there exists no node k such that d(i, k)+d(k, j)=d(i, j), and updating the set of links to include the inferred links, and refining the set of monitors from the set of links, wherein the routing information includes less than every link in the network; and outputting the set of links as a topology of the network, wherein the set of links includes the inferred link.