Mapping origin-destination (OD) network traffic is pivotal for networkmanagement and proactive security tasks. However, lack of sufficient flow-levelmeasurements as well as potential anomalies pose major challenges towards thisgoal. Leveraging the spatiotemporal correlation of nominal traffic, and thesparse nature of anomalies, this paper brings forth a novel framework to mapout nominal and anomalous traffic, which treats jointly important networkmonitoring tasks including traffic estimation, anomaly detection, and trafficinterpolation. To this end, a convex program is first formulated with nuclearand $ell_1$-norm regularization to effect sparsity and low rank for thenominal and anomalous traffic with only the link counts and a {it small}subset of OD-flow counts. Analysis and simulations confirm that the proposedestimator can {em exactly} recover sufficiently low-dimensional nominaltraffic and sporadic anomalies so long as the routing paths are sufficiently"spread-out" across the network, and an adequate amount of flow counts arerandomly sampled. The results offer valuable insights about data acquisitionstrategies and network scenaria giving rise to accurate traffic estimation. Forpractical networks where the aforementioned conditions are possibly violated,the inherent spatiotemporal traffic patterns are taken into account by adoptinga Bayesian approach along with a bilinear characterization of the nuclear and$ell_1$ norms. The resultant nonconvex program involves quadratic regularizerswith correlation matrices, learned systematically from (cyclo)stationaryhistorical data. Alternating-minimization based algorithms with provableconvergence are also developed to procure the estimates. Insightful tests withsynthetic and real Internet data corroborate the effectiveness of the novelschemes.
展开▼
