An Algorithm For Detecting Heavy Hitters Based On Light Flow Eviction

Heavy hitters are flows that contains more than the threshold number of packets in a measurement period.As network scale has become larger and the network infrastructures become more complex,heavy hitter detection is being used in a wide range of applications,both for congestion control and network capacity planning to improve network quality of service,and for identifying DDo S attacks and worm attacks to maintain network security.In order to catch up with the high line rates in today’s network,per-packet processing speed of heavy hitter detection algorithms should be fast enough.As on-chip memory(such as SRAM)has the fastest processing speed,these algorithms today are deployed on SRAM.However,the capacity of SRAM is very limited,so how to detect heavy hitters more accurately in compact memory has become the main research direction.The existing algorithms can not balance their performance and memory consumption well.In this thesis,we designed a new sketch based on “Light flow Eviction”,called “LE Sketch”,and proposed a new detection algorithm called “LES Algorithm” based on this structure.LE Sketch processes heavy hitters and light flows separately,light flows are evicted from sketch by “decay and evict” strategy,and ensures that as many heavy hitters as possible are stored in sketch by “replace” strategy,which reduces the influence of light flows on candidate heavy hitters in sketch,so the detection accuracy of LES Algorithm is improved.At the same time,LE Sketch stores different candidate heavy hitters in each bucket.So,with the same memory capacity,LE Sketch can store more heavy hitters.Therefore,LES Algorithm achieves a good trade-off between memory consumption and detection accuracy.In addition,LE Sketch incurs small processing overhead for each incoming packet because most packets update only part of fields in a bucket,and only very few packets update all fields in the bucket,therefore,LES Algorithm has high throughput and supports high line speed.In this thesis,the LES Algorithm has been analyzed in many aspects.This algorithm is also compared with other algorithms on three different Traces from different metrics.The experimental results show that compared with other algorithms,LES Algorithm performs better in many aspects,such as detection accuracy and average relative error.Moreover,LES Algorithm also maintains good detection performance when the available memory is small.