The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Sketch-based change detection: methods, evaluation, and applications
Abstract
Traffic anomalies such as failures and attacks are commonplace in today's network, and identifying them rapidly and accurately is critical for large network operators. The detection typically treats the traffic as a collection of flows that need to be examined for significant changes in traffic pattern (eg, volume, number of connections). However, as link speeds and the number of flows increase, keeping per-flow state is either too expensive or too slow. We propose building compact summaries of the traffic data using the notion of sketches. We have designed a variant of the sketch data structure, k-ary sketch, which uses a constant, small amount of memory, and has constant per-record update and reconstruction cost. Its linearity property enables us to summarize traffic at various levels. We then implement a variety of time series forecast models (ARIMA, Holt-Winters, etc.) on top of such summaries and detect significant changes by looking for flows with large forecast errors. We also present heuristics for automatically configuring the model parameters.Using a large amount of real Internet traffic data from an operational tier-1 ISP, we demonstrate that our sketch-based change detection method is highly accurate, and can be implemented at low computation and memory costs. Our preliminary results are promising and hint at the possibility of using our method as a building block for network anomaly detection and traffic measurement.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Time Series Analysis: Forecasting and Control
Geurts, M., Box, G. E. P., & Jenkins, G. M. (1977) · Journal of Marketing Research · doi:10.2307/3150485 · Cited by 19,186
Addelman, S. (1979) · Technometrics · doi:10.1080/00401706.1979.10489788 · Cited by 6,750
Introduction to Time Series and Forecasting
(2002) · Springer Texts in Statistics · doi:10.1007/b97391 · Cited by 3,807
Snort - Lightweight Intrusion Detection for Networks
Roesch, M. (1999) · Cited by 3,163
Bro: a system for detecting network intruders in real-time
Paxson, V. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00112-7 · Cited by 2,636
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,433
Equation-based congestion control for unicast applications
Floyd, S., Handley, M., Padhye, J., & Widmer, J. (2000) · ACM SIGCOMM Computer Communication Review · doi:10.1145/347057.347397 · Cited by 1,414
New hash functions and their use in authentication and set equality
Wegman, M. N., & Carter, J. L. (1981) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(81)90033-7 · Cited by 1,402
A fast two-dimensional median filtering algorithm
Huang, T., Yang, G., & Tang, G. (1979) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1979.1163188 · Cited by 1,390
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
The Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
Inferring Internet Denial-of-Service Activity
Moore, D., Voelker, G. M., & Savage, S. (2001) · doi:10.21236/ada400003 · Cited by 863
A signal analysis of network traffic anomalies
Barford, P., Kline, J., Plonka, D., & Ron, A. (2002) · Proceedings of the second ACM SIGCOMM Workshop on Internet measurment - IMW '02 · doi:10.1145/637201.637210 · Cited by 787
Joint Estimation of Model Parameters and Outlier Effects in Time Series
Chen, C., & Liu, L.-M. (1993) · Journal of the American Statistical Association · doi:10.1080/01621459.1993.10594321 · Cited by 777
New directions in traffic measurement and accounting
Estan, C., & Varghese, G. (2001) · doi:10.1145/505202.505212 · Cited by 734
Outliers, level shifts, and variance changes in time series
Tsay, R. S. (1988) · Journal of Forecasting · doi:10.1002/for.3980070102 · Cited by 722
Flash crowds and denial of service attacks
Jung, J., Krishnamurthy, B., & Rabinovich, M. (2002) · International World Wide Web Conference (WWW) · doi:10.1145/511446.511485 · Cited by 638
Self-citationWhat's hot and what's not: tracking most frequent items dynamically
Cormode, G., & Muthukrishnan, S. (2005) · ACM Transactions on Database Systems · doi:10.1145/1061318.1061325 · Cited by 533
Time Series Model Specification in the Presence of Outliers
Tsay, R. S. (1986) · Journal of the American Statistical Association · doi:10.1080/01621459.1986.10478250 · Cited by 363
Aberrant Behavior Detection in Time Series for Network Monitoring
Brutlag, J. D. (2000) · USENIX Large Installation Systems Administration Conference · Cited by 296
Schemes for fault identification in communication networks
Katzela, I., & Schwartz, M. (1995) · IEEE/ACM Transactions on Networking · doi:10.1109/90.477721 · Cited by 268
A Markov Chain Model of Temporal Behavior for Anomaly Detection
Ye, N. (2000) · Cited by 256
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Characteristics of network traffic flow anomalies
Barford, P., & Plonka, D. (2001) · Proceedings of the First ACM SIGCOMM Workshop on Internet Measurement - IMW '01 · doi:10.1145/505202.505211 · Cited by 200
Proactive network fault detection
Hood, C. S., & Ji, C. (2002) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.1997.631137 · Cited by 158
Internet service performance failure detection
Ward, A. R., Glynn, P. W., & Richardson, K. J. (1998) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/306225.306237 · Cited by 43
Cited by
Mining anomalies using traffic feature distributions
Lakhina, A., Crovella, M., & Diot, C. (2005) · Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1080091.1080118 · Cited by 1,054
Diagnosing network-wide traffic anomalies
Lakhina, A., Crovella, M., & Diot, C. (2004) · Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1015467.1015492 · Cited by 1,039
Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications
Xu, H., Feng, Y., Chen, J., Wang, Z., Qiao, H., Chen, W., Zhao, N., Li, Z., Bu, J., Li, Z., et al. (2018) · Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18 · doi:10.1145/3178876.3185996 · Cited by 808
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
Structural analysis of network traffic flows
Lakhina, A., Papagiannaki, K., Crovella, M., Diot, C., Kolaczyk, E. D., & Taft, N. (2004) · Proceedings of the joint international conference on Measurement and modeling of computer systems · doi:10.1145/1005686.1005697 · Cited by 451
Metadata
- Authors
- Krishnamurthy, B., Sen, S., Zhang, Y., & Chen, Y.
- Venue
- Proceedings of the 2003 ACM SIGCOMM conference on Internet measurement - IMC '03
- Publisher
- ACM Press
- Published
- 2003
- Pages
- 234
- OpenAlex
- W2102481563
- Cited by
- 528
- References
- 27
- FWCI
- 10.62
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.