Efficient Querying and Maintenance of Network Provenance at Internet-scale

Network accountability, forensic analysis, and failure diagnosis are becoming increasingly important for network management and se-curity. Such capabilities often utilize network provenance – the ability to issue queries over network meta-data. For example, net-work provenance may be used to trace the path a message traverses on the network as well as to determine how message data were de-rived and which parties were involved in its derivation. This paper presents the design and implementation of ExSPAN, a generic and extensible framework that achieves efficient network provenance in a distributed environment. We utilize the database notion of data provenance to “explain ” the existence of any net-work state, providing a versatile mechanism for network prove-nance. To achieve such flexibility at Internet-scale, ExSPAN uses declarative networking in which network protocols can be modeled as continuous queries over distributed streams and specified con-cisely in a declarative query language. We extend existing data models for provenance developed in database literature to enable distribution at Internet-scale, and investigate numerous optimiza-tion techniques to maintain and query distributed network prove-nance efficiently. The ExSPAN prototype is developed using Rapid-Net, a declarative networking platform based on the emerging ns-3 toolkit. Experiments over a simulated network and an actual de-ployment in a testbed environment demonstrate that our system supports a wide range of distributed provenance computations effi-ciently, resulting in significant reductions in bandwidth costs com-pared to traditional approaches