Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank

Abstract

In the backbone of large-scale networks, origin-to-destination (OD) traffic flows experience abrupt unusual changes known as traffic volume anomalies, which can result in congestion and limit the extent to which end-user quality of service requirements are met. As a means of maintaining seamless end-user experience in dynamic environments, as well as for ensuring network security, this paper deals with a crucial network monitoring task termed dynamic anomalography. Given link traffic measurements (noisy superpositions of unobserved OD flows) periodically acquired by backbone routers, the goal is to construct an estimated map of anomalies in real time, and thus summarize the network `health state' along both the flow and time dimensions. Leveraging the low intrinsic-dimensionality of OD flows and the sparse nature of anomalies, a novel online estimator is proposed based on an exponentially-weighted least-squares criterion regularized with the sparsity-promoting ${\ell }_1$-norm of the anomalies, and the nuclear norm of the nominal traffic matrix. After recasting the non-separable nuclear norm into a form amenable to online optimization, a real-time algorithm for dynamic anomalography is developed and its convergence established under simplifying technical assumptions. For operational conditions where computational complexity reductions are at a premium, a lightweight stochastic gradient algorithm based on Nesterov's acceleration technique is developed as well. Comprehensive numerical tests with both synthetic and real network data corroborate the effectiveness of the proposed online algorithms and their tracking capabilities, and demonstrate that they outperform state-of-the-art approaches developed to diagnose traffic anomalies.

33 pages, 7 figures, submitted to the IEEE Journal of Selected Topics in Signal Processing - Special issue on `Anomalous pattern discovery for spatial, temporal, networked, and high-dimensional signals'

References in corpus (2)

• A Singular Value Thresholding Algorithm for Matrix Completion
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies

Cited by in corpus (27)

• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
• Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization
• Network Volume Anomaly Detection and Identification in Large-scale Networks based on Online Time-structured Traffic Tensor Tracking
• Static and Dynamic Robust PCA and Matrix Completion: A Review
• Adaptive-Rate Compressive Sensing Using Side Information
• Anomaly Detection in Road Networks Using Sliding-Window Tensor Factorization
• Load curve data cleansing and imputation via sparsity and low rank
• Successive Convex Approximation Algorithms for Sparse Signal Estimation with Nonconvex Regularizations
• Joint community and anomaly tracking in dynamic networks
• Dynamic Network Cartography
• Robust PCA for Anomaly Detection in Cyber Networks
• Online Categorical Subspace Learning for Sketching Big Data with Misses
• On the Adversarial Robustness of Subspace Learning
• Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection
• Big Data Analytics in Future Internet of Things
• Online (and Offline) Robust PCA: Novel Algorithms and Performance Guarantees
• Tracking Tensor Subspaces with Informative Random Sampling for Real-Time MR Imaging
• F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams
• Cognitive Internet of Things: A New Paradigm beyond Connection
• Adaptive Anomaly Detection in Network Flows with Low-Rank Tensor Decompositions and Deep Unrolling
• Low-Rank Methods in Event Detection and Subsampled Point-to-Subspace Proximity Tests
• Large-scale Kernel-based Feature Extraction via Budgeted Nonlinear Subspace Tracking
• Proximal Dogleg Opportunistic Majorization for Nonconvex and Nonsmooth Optimization
• A Parallel Best-Response Algorithm with Exact Line Search for Nonconvex Sparsity-Regularized Rank Minimization