A hybrid local and distributed sketching design for accurate and scalable heavy key detection in network data streams
Publication in refereed journal


Times Cited
Web of Science8WOS source URL (as at 09/01/2021) Click here for the latest count
Altmetrics Information
.

Other information
AbstractReal-time characterization of network traffic anomalies, such as heavy hitters and heavy changers, is critical for the robustness of operational networks, but its accuracy and scalability are challenged by the ever-increasing volume and diversity of network traffic. We address this problem by leveraging parallelization. We propose LD-Sketch, a data structure designed for accurate and scalable traffic anomaly detection using distributed architectures. LD-Sketch combines the classical counter-based and sketch-based techniques, and performs detection in two phases: local detection, which guarantees zero false negatives, and distributed detection, which reduces false positives by aggregating multiple detection results. We derive the error bounds and the space and time complexity for LD-Sketch. We further analyze the impact of ordering of data items on the memory usage and accuracy of LD-Sketch. We compare LD-Sketch with state-of-the-art sketch-based techniques by conducting experiments on traffic traces from a real-life 3G cellular data network. Our results demonstrate the accuracy and scalability of LD-Sketch over prior approaches. (C) 2015 Elsevier B.V. All rights reserved.
All Author(s) ListHuang Q, Lee PPC
Journal nameComputer Networks
Year2015
Month11
Day14
Volume Number91
PublisherELSEVIER SCIENCE BV
Pages298 - 315
ISSN1389-1286
eISSN1872-7069
LanguagesEnglish-United Kingdom
KeywordsHeavy hitter/changer detection; Network monitoring; Sketches; Streaming architectures
Web of Science Subject CategoriesComputer Science; Computer Science, Hardware & Architecture; Computer Science, Information Systems; Engineering; Engineering, Electrical & Electronic; Telecommunications

Last updated on 2021-10-01 at 01:30