  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 infer composite
weights on the subpath formed by the path intersection. We call these subpath
weights the Path Correlation Data. In this paper 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 our conditions,
the result 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.
