| dc.description.abstract | A communication network can be modeled as a directed connected graph with edge weights that characterize performance metrics such as loss and delay. Network tomography aims to infer these edge weights from their pathwise versions measured on a set of intersecting paths between a subset of boundary vertices, and even the underlying graph when this is not known. In particular, temporal correlations between path metrics have been used to infer composite weights on the subpath formed by the path intersection. We call these subpath weights the Path Correlation Data. In this manuscript we ask the following question: when can the underlying weighted graph be recovered knowing only the boundary vertices and the Path Correlation Data? We establish
necessary and sufficient conditions for a graph to be reconstructible from this information, and describe an algorithm to perform the reconstruction. Subject to fairly general conditions which will be elaborated in next Section, the results applies to directed graphs with asymmetric edge weights, and accommodates paths arising from asymmetric routing in the underlying communication network. We also describe the relationship between the graph produced by our algorithm and the true graph in the case that our conditions are not satisfied.
Establishing the conditions under which the underlying directed graph can be recovered exactly from the pairwise Path Correlation Data, algorithmically, this enables us to consistently fuse tree-based view of the set of network paths to and from each endpoint to reconstruct the underlying network. However, in practice the PCD is not consistently determined by path measurements. Statistical fluctuations give rise to inconsistent inferred weight of edges from measurement based on different endpoints, as do operational constraints on synchronization, and deviations from the underlying packet transmission model. Furthermore, ad hoc solutions to eliminate noise, such as pruning small weight inferred links, are hard to apply in a consistent manner that preserves known end-to end metric values. We further take a unified approach to the problem of inconsistent weight estimation. We formulate two types of inconsistency: intrinsic, when the weight set is internally inconsistent, and extrinsic, when they are inconsistent with a set of known end-to-end path metrics. In both cases we map inconsistent weights to consistent PCD within a least-squares framework.
Finally, we evaluate the performance of this mapping in composition with tree-based inference algorithms. | en |
