Inference of computer network properties: a linear algebra approach

David Bindel
Cornell University
Computer science

Because it is extremely difficult to broadly deploy new functionality to the routers used in the Internet, many modern Internet services rely on overlay and peer-to-peer architectures.
These systems benefit from knowledge of properties of the underlying network, such as latency and loss rates of paths between hosts, or the location of congested links. We discuss methods of computer network tomography that allow us to infer such network properties by discovering and exploiting the inter-relationships between end-to-end routing paths. We describe how these relationships can be coached in terms of a sparse factorization of a low-rank matrix describing network paths, and how this factorization can be used to discover properties of links and paths in the network. We also describe our ongoing work on inferring structural information about computer network based solely on correlations between measurements of routing paths between end hosts.

Back to Machine Reasoning Workshops I & II: Mission-Focused Representation & Understanding of Complex Real-World Data