IMC '05, 2005 Internet Measurement Conference Abstract
Pp. 317330 of the Proceedings
Yin Zhang, University of Texas at Austin; Zihui Ge and Albert Greenberg, AT&T LabsResearch; Matthew Roughan, University of Adelaide
Anomaly detection is a first and important step needed to respond to
unexpected problems and to assure high performance and security in IP
networks. We introduce a framework and a powerful class of algorithms
for network anomography, the problem of inferring network-level
anomalies from widely available data aggregates. The framework
contains novel algorithms, as well as a recently published approach
based on Principal Component Analysis (PCA). Moreover, owing to its
clear separation of inference and anomaly detection, the framework
opens the door to the creation of whole families of new algorithms.
We introduce several such algorithms here, based on ARIMA modeling,
the Fourier transform, Wavelets, and Principal Component Analysis. We
introduce a new dynamic anomography algorithm, which effectively
tracks routing and traffic change, so as to alert with high fidelity
on intrinsic changes in network-level traffic, yet not on internal
routing changes. An additional benefit of dynamic anomography is that
it is robust to missing data, an important operational reality. To the
best of our knowledge, this is the first anomography algorithm that
can handle routing changes and missing data. To evaluate these
algorithms, we used several months of traffic data collected from the
Abilene network and from a large Tier-1 ISP network. To compare
performance, we use the methodology put forward earlier for the
Abilene data set. The findings are encouraging. Among the new
algorithms introduced here, we see: high accuracy in detection (few
false negatives and few false positives), and high robustness (little
performance degradation in the presence of measurement noise, missing
data and routing changes).
- View the full text of this paper in HTML and PDF.
The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.