Distance Realization Problems with Applications to Internet Tomography

摘要

In recent years, a variety of graph optimization problems have arisen in which the graphs involved are much too large for the usual algorithms to be effective. In these cases, even though we are not able to examine the entire graph (which may be changing dynamically), we would still like to deduce various properties of it, such as the size of a connected component, the set of neighbors of a subset of vertices, etc. In this paper, we study a class of problems, called distance realization problems, which arise in the study of Internet data traffic models. Suppose we are given a set S of terminal nodes, taken from some (unknown) weighted graph. A basic problem is to reconstruct a weighted graph G including S, with possibly additional vertices, that realizes the given distance matrix for S. We will first show that this problem is not only difficult bu the solution is often unstable in the sense that even if all distances between nodes in S decrease, the solution can increase by a factor proportional to the size of S in the worst case. We then proceed to consider a weaker version of the realization problem that only requires the distances in G to upper bound the given distances. We will show that this weak realization problem is NP-complete and that its optimum solutions can be approximated to within a factor of 2. We also consider several variants of these problems and a number of heuristics are presented. These problems are of interest for monitoring large-scale networks and for supplementing network management techniques.