Super point is a special host in network which communicates with lots of other hosts in a certain time period. The number of hosts contacting with a super point is called as its cardinality. Cardinality estimating plays important roles in network management and security. This paper devises a novel algorithm SRLA to estimate the cardinality of super point over sliding time window. SRLA records host cardinality by a novel structure which could be updated incrementally. In order to reduce the cardinality estimating time at the end of every sliding time window, SRLA generates a super point candidate list while scanning packets and calculates the cardinality of host in the candidate list only. It also has the ability to run parallel to deal with high speed network in line speed. This paper gives the way to deploy SRLA on a common GPU. Experiments on real world traffics which have 40 GB s bandwidth show that SRLA successfully estimates super point's cardinality in real time under sliding time window.
Super point detection is a hot topic in network research field. @cite_11 proposed an algorithm that did not keep the state of every host so this algorithm can scale very well. @cite_4 used a pair-based sampling method to eliminate the majority of low opposite number hosts and reserved more resource to estimate the opposite number of the resting hosts. @cite_14 proposed two bits map algorithms based on sampling flows. Several hosts could share a bit of this map to reduce memory consumption. All of these methods were based on sampling flows which limited its accuracy.
@cite_14 @cite_4 @cite_11
2111678491 2150399692 1601184934
This paper presents a family of bitmap algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high-speed link. Such counting can be used to detect DoS attacks and port scans and to solve measurement problems. Counting is especially hard when processing must be done within a packet arrival time (8 ns at OC-768 speeds) and, hence, may perform only a small number of accesses to limited, fast memory. A naive solution that maintains a hash table requires several megabytes because the number of flows can be above a million. By contrast, our new probabilistic algorithms use little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we replaced the port-scan detection component of the popular intrusion detection system Snort with one of our new algorithms. This reduced memory usage on a ten minute trace from 50 to 5.6 MB while maintaining a 99.77 probability of alarming on a scan within 6 s of when the large-memory algorithm would. The best known prior algorithm (probabilistic counting) takes four times more memory on port scan detection and eight times more on a measurement application. This is possible because our algorithms can be customized to take advantage of special features such as a large number of instances that have very small counts or prior knowledge of the likely range of the count. The Internet host cardinality, defined as the number of distinct peers that an Internet host communicates with, is an important metric for profiling Internet hosts. Some example applications include behavior based network intrusion detection, p2p hosts identification, and server identification. However, due to the tremendous number of hosts in the Internet and high speed links, tracking the exact cardinality of each host is not feasible due to the limited memory and computation resource. Existing approaches on host cardinality counting have primarily focused on hosts of extremely high cardinalities. These methods do not work well with hosts of moderately large cardinalities that are needed for certain host behavior profiling such as detection of p2p hosts or port scanners. In this paper, we propose an online sampling approach for identifying hosts whose cardinality exceeds some moderate prescribed threshold, e.g. 50, or within specific ranges. The main advantage of our approach is that it can filter out the majority of low cardinality hosts while preserving the hosts of interest, and hence minimize the memory resources wasted by tracking irrelevant hosts. Our approach consists of three components: 1) two-phase filtering for eliminating low cardinality hosts, 2) thresholded bitmap for counting cardinalities, and 3) bias correction. Through both theoretical analysis and experiments using real Internet traces, we demonstrate that our approach requires much less memory than existing approaches do whereas yields more accurate estimates. Abstract : High-speed monitoring of Internet traffic is an important and challenging problem, with applications to real-time attack detection and mitigation, traffic engineering, etc. However, packet-level monitoring requires fast streaming algorithms that use very little memory space and little communication among collaborating network monitoring points. In this paper, we consider the problem of detecting superspreaders, which are sources that connect to a large number of distinct destinations. We propose several new streaming algorithms for detecting superspreaders, and prove guarantees on their accuracy and memory requirements. We also show experimental results on real network traces. Our algorithms are substantially more efficient (both theoretically and experimentally) than previous approaches. We also provide several extensions to our algorithms -- we show how to identify superspreaders in a distributed setting, with sliding windows, and when deletions are allowed in the stream. More generally, our algorithms are applicable to any problem that can be formulated as follows: given a stream of (x,y) pairs, find all the x's that are paired with a large number of distinct y's. We call this the heavy distinct-hitters problem. There are many network security applications of this general problem. This paper discusses these and other applications, and for concreteness, focuses on the superspreader problem.