What’s new: Finding significant differences in network data streams

Abstract—Monitoring and analyzing network traffic usage pat-terns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about “what’s new. ” Specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. We introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. We present novel algorithms for finding the most significant del-toids in high-speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions ca-pable of working over the data with one pass, at network traffic speeds. Index Terms—Change detection, data streams, deltoids, network data analysis. I