Research On Heavy-Hitter Detection And Anomaly Detection In High-Speed Networks

Heavy-hitter detection is a fundamental task in high-speed network traffic measurement because it can provide critical traffic statistics for network management activities such as traffic engineering,congestion control,and anomaly detection.As the line rates and the traffic volume keep increasing in today’s networks,networking devices(e.g.,routers)rely more on the high-speed on-chip memory resources(e.g.,static random-access memory,SRAM)to meet the requirements of real-time packet processing.However,on-chip resources are limited due to manufacturing technology(usually less than 10MB)and are shared by some essential network functions such as routing,firewall,and resource scheduling.The space that can be allocated for module of heavy-hitter detection is usually less than 1MB.Therefore,the current high-speed network heavy-hitter detection faces the challenge of extremely limited on-chip resources not matching the massive high-speed network traffic.To address the above challenges,a feasible solution is to use sketch technology.Sketch is an efficient and compact data structure that compresses and stores traffic statistics.By using hash functions and related maintenance strategies,sketch can efficiently store a large number of traffic statistics in a limited memory space.It can achieve accurate heavy-hitter detection in high-speed networks.However,high-speed network traffic is generated and collected continuously in an unpredictable order.Its flow distribution is highly skewed-a small number of heavy hitters and a large number of small flows,bringing additional challenges to sketch-based heavy-hitter detection:First,since each flow’s final frequency is unpredictable,it is necessary to allocate the fixed storage resources for each flow in advance,resulting in a waste of on-chip resources.Second,many small flows will introduce significant noise to heavy-hitter detection.Designing an accurate and efficient sketch-based algorithm for heavy-hitter detection in high-speed networks is meaningful,providing essential statistics for various network management activities.The optimization of sketch technology is mainly divided into two directions:the innovation of related maintenance strategies and the innovation of its data structure.Meanwhile,many researchers have focused on applying sketch to practical network functions such as anomaly detection.With a thorough investigation of existing works,this dissertation proposes two efficient algorithms for heavy-hitter detection in high-speed networks:the HeavyTracker with a novel count-with-threshold strategy and the SwitchSketch with a multi-level dynamic memory allocation data structure.Based on these two algorithms,this dissertation also constructs a sketch-based network anomaly detection system.The specific dissertation’s contents are as follows:(1)HeavyTracker:An efficient algorithm for heavy-hitter detection in high-speed networks based on the count-with-threshold strategy.This dissertation proposes a novel countwith-threshold strategy,including an efficient update method:exponential expulsion.The algorithm will ensure that each flow recorded in the sketch can be expelled with a reasonable probability and keep large flows accurately recorded in the final sketch.Based on the genetic algorithm,this dissertation also gives more reasonable parameter settings to optimize the expulsion probability further.(2)SwitchSketch:An efficient algorithm for heavy-hitter detection in high-speed networks based on the multi-level dynamic memory allocation data structure.This dissertation designs a multi-level dynamic memory allocation data structure.The algorithm can flexibly allocate different memory space to different-size flows in the dynamic and imbalanced network traffic.It can effectively capture the heavy hitters’ statistics in the limited memory space.This dissertation also gives the error boundary of the algorithm through rigorous mathematical analysis,which further verifies the effectiveness of the algorithm.(3)The sketch-based network anomaly detection system.Based on the above two algorithms,this dissertation constructs a sketch-based network anomaly detection system.Through the compressed storage of sketch technology to filter out most of the small flows’noise,the system can achieve efficient network anomaly detection combined with traditional machine learning classification methods at the cost of a tiny amount of memory.The above three research have been verified by simulation experiments on real Internet traces(e.g.,CAIDA-2016 dataset,CAIDA-2019 dataset,CAIDA-DDoS dataset).Experimental results show that the proposed two algorithms can achieve high precision in both heavy-hitter detection and frequency estimation compared to the state-of-the-art.Meanwhile,the anomaly detection system can efficiently detect anomaly traffic as well.