Topology identification for traffic and configuration management in dynamic networks

The authors address the problem of identifying the topology of a network from data collected at a designated node (possibly one of the network nodes). The data considered are descriptions of the local neighborhood about each node, which specify the identities of the node and of its neighbors. These data are neither required to be correct nor complete. The authors propose a model that describes and relates the network topology and the data. They define costs associated with this model, and reduce the identification problem to a combinational optimization problem with and an objective function based on these costs. A pseudo-polynomial-time algorithm is derived, which yields a local minimum of the objective function. The local minimum appears to be a reasonable solution, as shown by a range of examples