The increasing complexity of data center networks has made it considerably more difficult to identify the source of a networking problem when something goes wrong. However, a set of new diagnostic tools can help diagnose subtle bugs that would be difficult to find with existing tools. One promising approach is based on data provenance, a concept that was originally developed by the database community but is now increasingly being applied in the networking domain. In this approach, the network keeps track of causality as data flows through the system -- for instance, by noting a router's configuration state that contributed to a particular forwarding decision. This information can then be used later to determine a comprehensive explanation of an observed networking problem.
This project will develop a quantitative equivalent of provenance for data networking that can be used to reason about properties such as time or probability. The key idea is to use this provenance to improve root-cause analysis of network events. The proposed effort will develop the scientific foundations of quantitative provenance, as well as practical techniques for capturing, storing, and reasoning about it. The investigators will add several quantitative metrics to provenance: temporal, probabilistic and influence; three research thrusts will be considered, one corresponding to each of these metrics. The project will explore efficient and reusable implementations of new diagnostic tools, which will be applied to several concrete case studies.
