Unveiling anomalies in large-scale networks via sparsity and low rank

Morteza Mardani, Gonzalo Mateos, Georgios B. Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

In the backbone of large-scale networks, traffic flows experience abrupt unusual changes which can result in congestion, and limit the extent to which end-user quality of service requirements are met. Diagnosing such traffic volume anomalies is a crucial task towards engineering the traffic in the network. This is challenging however, since the available data are the superposition of unobservable origin-to-destination (OD) flows per link. Leveraging the low intrinsic-dimensionality of OD flows and the sparse nature of anomalies, a convex program is formulated to unveil anomalies across flows and time. A centralized solver is developed using the proximal gradient algorithm, which offers provable iteration complexity guarantees. An equivalent nonconvex but separable criterion enables in-network processing of link-load measurements, when optimized via the alternating-direction method of multipliers. The novel distributed iterations entail reduced-complexity local tasks, and affordable message passing between neighboring nodes. Interestingly, under mild conditions the distributed algorithm approaches its centralized counterpart. Numerical tests with synthetic and real network data corroborate the effectiveness of the novel scheme.

Original languageEnglish (US)
Title of host publicationConference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
Pages403-407
Number of pages5
DOIs
StatePublished - Dec 1 2011
Event45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011 - Pacific Grove, CA, United States
Duration: Nov 6 2011Nov 9 2011

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393

Other

Other45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
CountryUnited States
CityPacific Grove, CA
Period11/6/1111/9/11

Fingerprint Dive into the research topics of 'Unveiling anomalies in large-scale networks via sparsity and low rank'. Together they form a unique fingerprint.

Cite this