Journal
IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 29, Issue 6, Pages 2386-2398Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2021.3061737
Keywords
Routing; Topology; Network topology; Monitoring; Approximation algorithms; Computer science; Weight measurement; Communication technology; communication systems; computer networks; Internet
Categories
Funding
- HPI Research School, Technion
- Eric and Wendy Schmidt Fund for Strategic Innovation
- Cyber Security Research Center
- Lynne and William Frankel Center for Computing Science at Ben-Gurion University
- Zuckerman Institute
- Technion Hiroshi Fujiwara Cyber Security Research Center
- Israel Cyber Directorate
- Cyber Security Authority in BGU
- Center for Research on Computation and Society at Harvard University
Ask authors/readers for more resources
Recent introduction of SDN enables the deployment of new centralized network algorithms that significantly enhance network operations. This research proposes novel algorithms for fundamental network-wide measurement problems without making assumptions on the topology and routing, or modifying the underlying traffic. An extensive evaluation on realistic network topologies and traces demonstrates that the proposed algorithms outperform existing works in terms of accuracy within reasonable space constraints.
The recent introduction of SDN allows deploying new centralized network algorithms that dramatically improve network operations. In such algorithms, the centralized controller obtains a network-wide view by merging measurement data from Network Measurement Points (NMPs). A fundamental challenge is that several NMPs may count the same packet, reducing the accuracy of the measurement. Existing solutions circumvent this problem by assuming that each packet traverses a single NMP or that the routing is fixed and known. This work suggests novel algorithms for three fundamental network-wide measurement problems without making any assumptions on the topology and routing and without modifying the underlying traffic. Specifically, this work introduces two algorithms for estimating the number of (distinct) packets or byte volume in the measurement, estimating per-flow packet and byte counts, and finding the heavy hitter flows. Our work includes formal accuracy guarantees and an extensive evaluation consisting of the realistic fat-tree topology and three real network traces. Our evaluation shows that our algorithms outperform existing works and provide accurate measurements within reasonable space parameters.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available