A Distributed Data Streaming Algorithm for Network-wide Traffic Anomaly Detection

摘要

Nowadays, Internet has serious security problems and network failures that are hard to resolve, for example, bot-net attacks, polymorphic worm/virus spreading, DDoS, and flash crowds. To address many of these problems, we need to have a network-wide view of the traffic dynamics, and more importantly, be able to detect traffic anomaly in a timely manner. To our knowledge, Principle Component Analysis (PCA) is the best-known spatial detection method for the network-wide traffic anomaly. However, existing PCA-based solutions have scalability problems in that they require O(m~2n) running time and O(mn) space to analyze traffic measurements from m aggregated traffic flows within a sliding window of the length n. We propose a novel data streaming algorithm for PCA-based network-wide traffic anomaly detection in a distributed fashion. Our algorithm can archive O(wn log n) running time and O(wn) space at local monitors, and O(m~2 log n) running time and O(m log n) space at Network Operation Center (NOC), where w denotes the maximum number of traffic flows at a local monitor.