A distributed data streaming algorithm for network-wide traffic anomaly detection
Yang Liu, Linfeng Zhang, Yong Guan · ACM SIGMETRICS Performance Evaluation Review · 2009
Nowadays, Internet has serious security problems and network failures that are hard to resolve, for example, botnet 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 2 n )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.