Title
Network-wide routing-oblivious heavy hitters.
Abstract
The recent introduction of SDN allows deploying new centralized network algorithms that dramatically improve the network operation. Many of these solutions rely on the assumption that the centralized controller merges data from different Network Monitoring Points (NMP) to obtain a network-wide view. This is far from trivial when the same packet may traverse through several NMPs. Therefore, existing solutions either assume that each packet is measured at exactly one NMP or that the routing of each packet is known. Another approach is to mark the sampled packets so that other NMPs are aware that the packet was already considered. We suggest the first network-wide and routing oblivious algorithms for three fundamental network monitoring problems. The suggested algorithms allow flexible NMP placement, require no control over edge routers, and are indifferent to network topology and routing. Moreover, they are based on passive measurements without modifying the traffic in any way. Formally, we provide a general, constant time framework that solves the distributed versions of the volume estimation, frequency estimation and heavy-hitters problems with provable guarantees. The evaluation of our scheme on real packet traces shows that we can achieve very accurate results using a very reasonable amount of memory. For example, using less than 60KB memory in each monitoring point we get a root square error of less than 0.01% of the packets for frequency estimation.
Year
DOI
Venue
2018
10.1145/3230718.3230729
ANCS
Field
DocType
ISBN
Control theory,Computer science,Network packet,Computer network,Network topology,Information-centric networking,Binary search algorithm,Network monitoring,Square root,Traverse
Conference
978-1-4503-5902-3
Citations 
PageRank 
References 
6
0.47
24
Authors
5
Name
Order
Citations
PageRank
Ran Ben-Basat1100.95
Gil Einziger215120.82
Shir Landau Feibish3375.78
Jalil Moraney461.14
Danny Raz51643152.24