22 

Evaluation of a Fast and Accurate Flow-Counting Algorithm
for IP Networks
 Shan Zhu, Satoru Ohta (Toyama Prefectural University)

2. Problem Description
The authors’ algorithm [1] is based on the timestamp
vector (TV) algorithm [2], which utilizes a TV and ahash function. The algorithm inputs the flow identifierof an arriving packet to the hash function. Thetimestamp is stored in the TV element, whose index is
the hash output. Then, the number of flows is
calculated by the recently updated elements. Based on
this procedure, the authors’ method achieves smaller
computational time by using the following techniques:- Multiple counters that eliminate the vector scanning
process, which is very time-consuming, and- Packet sampling.
In addition, the algorithm provides better accuracy byutilizing TCP FIN/RST messages.
The effectiveness of the algorithm was confirmed byartificially generating traffic on a small experimental
network. However, it is not known whether thealgorithm is fast enough to process the traffic of areal-world network.
It is also unclear how thealgorithm scales for high-speed links. The purpose ofthis study is to clarify these points.

3. Evaluation Method
The authors’ algorithm was implemented with theuse of the pcap library, which enables the program toread publicly available real-world network data. As
real-world data, this study employed the data set
distributed by the MAWI working group of the WIDE
project [3]. The data set includes files gathered atvarious times at six sample points. Among these files,
we examined the file of the traffic at 18:15, June 30,
2006 at sample point B, as well as the file of the traffic
at 14:00, July 28, 2010 at sample point F. Hereafter, theformer is referred to as file #1, while the latter isreferred to as file #2.
The computational times taken to process files #1
and #2 were measured. The program of the authors’algorithm was executed on a Linux PC (Intel Core 2,1.80GHz), and the time was measured by the GNU
time command. For comparison purposes, thecomputational time was also measured for the original

3
TV Algorithm

Proposed Method

20

Computational Time sec

An important aspect of IP network management is tocount the number of flows. For this purpose, theauthors have proposed a fast and accurate
flow-counting algorithm [1]. This paper reports theperformance of the algorithm for real-world network
data and estimates its scalability.

TV algorithm [2].
The computational time greatly depends on thechoice of the TV size. For many flows, the TV sizemust be large in order to decrease estimation errors. For
file #2, it was found that the maximum number ofconcurrent flows is greater than 3.5 × 10 4 . To estimate
these flows accurately, the TV size was set to 1000003.
The frequency of flow-number estimation also affects
the computational time. In this study, the flow number
was estimated every 1 s.
Figure 1 shows the computational time obtained by
the authors’ algorithm, as well as that obtained by theoriginal TV algorithm. The figure clearly shows theadvantage of the authors’ method. For file #1, thecomputation time taken by using the authors’ method is57% smaller than that by using the original TV
algorithm. For file #2, the authors’ method was lesseffective. Nevertheless, the computational time issmaller for the authors’ method than for the original TValgorithm, as well as for file #2.
Computational Time sec

1. Introduction

TV Algorithm

Proposed Method1521010(a) file #1

50(b) file #2

Figure 1: Comparison of computational times.
File #2 includes 36328883 packets. The algorithm
processes these packets in 16.31 s. Thus, a packet wasprocessed in 0.45 µ s. This is sufficiently small toprocess packets on 26 Gb/s link, if we assume that theaverage packet length is 1500 bytes. Therefore, theauthors’ algorithm will successfully count the numberof flows on recent high-speed links.

4. Conclusion
The flow-counting algorithm of [1] was examined forreal-world network traffic and was shown to work forhigh-capacity links whose bit rate exceeds 20 Gb/s.

References[1] S. Zhu and S. Ohta, “Fast and accurate flow counting
algorithm,” NOMS 2010, pp.918-921, Osaka, Apr. 2010.
[2] H.-A. Kim and D.R. O’Hallaron, “Counting network
flows in real time,” GLOBECOM 2003, pp.3888-3893,
2003.
[3] K. Cho, K. Mitsuya, and A. Kato, “Traffic data repository
at the WIDE project,” USENIX 2000 Annual TechnicalConference: FREENIX track, pp.263-270, Jun. 2000.