2014/07/07 by Morteza Mardani, Georgios B. Giannakis, Mardani, Morteza +1 · 1 citation
Computer Science · Engineering · #Anomaly Detection Techniques and Applications #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Networking and Internet Architecture (cs.NI) #Sparse and Compressive Sensing Techniques #cs.NI
paper · pdf · doi:10.48550/arxiv.1407.1660
16 pages, 9 Figures, submitted to IEEE/ACM Transactions on Networking
arxiv created 2014/07/07 · openalex publication_date 2014/07/07 · arxiv updated 2014/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 \it small subset of OD-flow counts. Analysis and simulations confirm that the proposed estimator can \em 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.