A grand spread estimator using a graphics processing unit

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.