Differential provenance: Better network diagnostics with reference events

In this paper, we propose a new approach to diagnosing prob-lems in complex networks. Our approach is based on the insight that many of the trickiest problems are anomalies – they affect only a small fraction of the traffic (e.g., perhaps a certain subnet), or they only manifest infrequently. Thus, it is quite common for the network operator to have “exam-ples ” of both working and non-working traffic readily avail-able – perhaps a packet that was misrouted, and a similar packet that was routed correctly. In this case, the cause of the problem is likely to be wherever the two packets were treated differently by the network. We sketch the design of a network debugger that can lever-age this information using a novel concept that we call dif-ferential provenance. Like classical provenance, differen-tial provenance tracks the causal connections between net-work and configuration states and the packets that were af-fected by them; however, it can additionally reason about the causes of any discrepancies between different provenances. We have performed a case study in the context of software-defined networks, and our initial results are encouraging: they suggest that differential provenance can often identify the root cause of even very subtle network issues