A Superpoints Detection Algorithm Based On Non-duplicated Sampling And Count-with-exponential-decay

During a measurement period,the cardinality of a source(destination)host is the number of distinct destinations(source).If the cardinality of a host exceeds a given threshold,then this host is called the superpoint.The emergence of superpioints is often a sign of some network attacks.For example,when DDoS attack happens,the attacker will use a number of computers to establish connections with the attacked,which will consume the system resources of the attacked and then paralyze it.So detecting superpints in real time is very crucial for network security and management.A superpoints algorithm is often set on a router as software/ hardware module,so the main challenge of designing a superpoint algorithm is how to process the current arriving packet quickly and efficiently before the next one arrives under the condition of limited memory.To address this issue,in this thesis,we propose an algorithm of detecting superpoints based on non-duplicate sampling and count-with-exponential-decay.The non-duplicate sampling(NDS)can filter duplicate packets during packets sampling with small memory consumption.We also designed a specific data structure EDS(Exponential-weakening Decay Snare)using count-with-exponential-decay to capture superpoints.The advantage of EDS is when two hosts hashed to same position,it can hold the information of superpoints with a high probability.In order to evaluate the performance of NDS-EDS,we first analyzes the error bound of the algorithm to estimate the host by theoretical analysis.We also perform experiments using three Traces collecting from different network environments and compare it with other four algorithms.Theoretical analysis and experimental results show that NDS-EDS has better performance for dectecting superpoints.