What's New: Finding Significant Differences in Network Data Streams

Overview

Monitoring and analyzing network traffic usage patterns 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, the focus of this paper is on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. The paper introduces the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. It presents novel algorithms for finding the most significant deltoids in high speed traffic data, and proves that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy.