TY - GEN
T1 - Unveiling anomalies in large-scale networks via sparsity and low rank
AU - Mardani, Morteza
AU - Mateos, Gonzalo
AU - Giannakis, Georgios B.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84861315051&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861315051&partnerID=8YFLogxK
U2 - 10.1109/ACSSC.2011.6190029
DO - 10.1109/ACSSC.2011.6190029
M3 - Conference contribution
AN - SCOPUS:84861315051
SN - 9781467303231
T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers
SP - 403
EP - 407
BT - Conference Record of the 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
T2 - 45th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2011
Y2 - 6 November 2011 through 9 November 2011
ER -