Computer Science

Randomized error removal for online spread estimation in high-speed networks

Document Type

Article

Abstract

Flow spread measurement provides fundamental statistics that can help network operators better understand flow characteristics and traffic patterns with applications in traffic engineering, cybersecurity and quality of service. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a packet stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, packet processing throughput, and online query throughput.

Publication Title

IEEE/ACM Transactions on Networking

Publication Date

2023

Volume

31

Issue

2

First Page

558

Last Page

573

ISSN

1063-6692

DOI

10.1109/TNET.2022.3197968

Keywords

flow spread, online, randomization, sketches, Traffic measurement

APA Citation

Wang, H., Ma, C., Odegbile, O. O., Chen, S., & Peir, J. K. (2022). Randomized error removal for online spread estimation in high-speed networks. IEEE/ACM Transactions on Networking.

Link to Full Text

Share

COinS