The next NEO Internal Meeting will take place on Wednesday 10 July, 14h30. Anirudh Sabnis will make a presentation about “OCCAM: An Optimization-Based Approach to Network Inference”.
________
Abstract:
OCCAM: An Optimization-Based Approach to Network Inference
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.
Abstract:
OCCAM: An Optimization-Based Approach to Network Inference
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.
