Dynamic anomalography: Tracking network anomalies via sparsity and low rank

Morteza Mardani, Gonzalo Mateos, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

106 Scopus citations

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.

Original languageEnglish (US)
Article number6376091
Pages (from-to)50-66
Number of pages17
JournalIEEE Journal on Selected Topics in Signal Processing
Volume7
Issue number1
DOIs
StatePublished - 2013

Keywords

  • Traffic volume anomalies
  • low rank
  • network cartography
  • online optimization
  • sparsity

Fingerprint

Dive into the research topics of 'Dynamic anomalography: Tracking network anomalies via sparsity and low rank'. Together they form a unique fingerprint.

Cite this