Patent ID: 8902755

Claim:
A 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 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 a local link (m, j) is inferred between nodes m and j, without querying either node m or j for connectivity information, upon determining that k=argmin {k′} {d(m, k′)−d(m, j)} where next-hop(m, k′)=j, then there exists a link (j, k) such that w(j, k)=d(m, k)−d(m, j), wherein k is a destination node in the network, w is a weight of the link, and d is a distance, and updating the set of links to include the inferred link; refining the set of monitors based on a refined set of links including the inferred link; and outputting the refined set of links as a topology of the network.