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.
The spread of a source is defined as the number of distinct destinations to which the source has sent packets during a measurement period. Spread estimation is essential in traffic monitoring, measurement, intrusion detection, to mention a few. To support high speed networking, recent research suggests implementing a spread estimator in fast but small on-chip memory such as SRAM. A state-of-the-art estimator can hold succinct information about 10 million distinct packets using 1 MB SRAM. This implies that a measurement period should restart whenever every 10 million distinct packets fill up the SRAM. Spread estimation is a challenging problem because two spread values from different measurement periods cannot be aggregated to derive the total value. Therefore, current spread estimators have a serious limitation concerning the length of the measurement period because SRAM is available a few megabytes at most. In this paper, we propose a spread estimator that utilizes a large memory space of a graphics processing unit on a commodity PC. The proposed estimator utilizes a 1 GB memory, a hundred times larger than those of current spread estimators, and its throughput is still around 160 Gbps. According to our experiments, the proposed scheme can cover a measurement period of a few dozen hours while the current state-of-the-art can cover only one hour. To the best of our knowledge, this has not been achieved by any spread estimators thus far.