  We study the problem of inferring the structure of a communication network
based only on network measurements made from a set of hosts situated at the
network periphery. Our novel approach called "OCCAM" is based on the principle
of occam's razor and finds the "simplest" network that explains the observed
network measurements. OCCAM infers the internal topology of a communication
network, including the internal nodes and links of the network that are not
amenable to direct measurement. In addition to network topology, OCCAM infers
the routing paths that packets take between the hosts. OCCAM uses path metrics
measurable from the hosts and expresses the observed measurements as
constraints of a mixed-integer bilinear optimization problem that can then be
feasibly solved to yield the network topology and the routing paths. We
empirically validate OCCAM on a wide variety of real-world ISP networks and
show that its inferences agree closely with the ground truth. Specifically,
OCCAM infers the topology with an average network similarity score of 93% and
infers routing paths with a path edit distance of 0.20. Further, OCCAM is
robust to error in its measured path metric inputs, producing high quality
inferences even when 20-30% of its inputs are erroneous. Our work is a
significant advance in network tomography as it proposes and empirically
evaluates the first method that infers the complete network topology, rather
than just logical routing trees from sources.
