Estimating Traffic and Anomaly Maps via Network Tomography

Morteza Mardani, Georgios B. Giannakis

Research output: Contribution to journalArticle

24 Scopus citations

Abstract

Mapping origin-destination (OD) network traffic is pivotal for network management and proactive security tasks. However, lack of sufficient flow-level measurements as well as potential anomalies pose major challenges towards this goal. Leveraging the spatiotemporal correlation of nominal traffic, and the sparse nature of anomalies, this paper brings forth a novel framework to map out nominal and anomalous traffic, which treats jointly important network monitoring tasks including traffic estimation, anomaly detection, and traffic interpolation. To this end, a convex program is first formulated with nuclear and ℓ1-norm regularization to effect sparsity and low rank for the nominal and anomalous traffic with only the link counts and a small subset of OD-flow counts. Analysis and simulations confirm that the proposed estimator can exactly recover sufficiently low-dimensional nominal traffic and sporadic anomalies so long as the routing paths are sufficiently "spread-out" across the network, and an adequate amount of flow counts are randomly sampled. The results offer valuable insights about data acquisition strategies and network scenaria giving rise to accurate traffic estimation. For practical networks where the aforementioned conditions are possibly violated, the inherent spatiotemporal traffic patterns are taken into account by adopting a Bayesian approach along with a bilinear characterization of the nuclear and ℓ1 norms. The resultant nonconvex program involves quadratic regularizers with correlation matrices, learned systematically from (cyclo)stationary historical data. Alternating-minimization based algorithms with provable convergence are also developed to procure the estimates. Insightful tests with synthetic and real Internet data corroborate the effectiveness of the novel schemes.

Original languageEnglish (US)
Article number7098434
Pages (from-to)1533-1547
Number of pages15
JournalIEEE/ACM Transactions on Networking
Volume24
Issue number3
DOIs
StatePublished - Jun 2016

    Fingerprint

Keywords

  • Convex optimization
  • low rank
  • nominal and anomalous traffic
  • sparsity
  • spatiotemporal correlation

Cite this