Cyber Journals: Multidisciplinary Journals in Science and Technology, Journal of Selected Areas in Telecommunications (JSAT), February Edition, 2012

Real-Time Flow Counting in IP Networks:
Strict Analysis and Design Issues
Shan Zhu and Satoru Ohta

offline. Their real-time nature makes the number of flows aparticularly useful performance metric.
Flow counting is essential to determine the number of
unique values in a large data set. This is efficiently achievedby an algorithm called linear counting, which wascomprehensively studied from the viewpoint of databaseapplications [9]. The flow counting methods reported in theliterature [4]-[7] are based on this algorithm.
The linear counting algorithm is based on a vector and ahash function. To successfully apply the algorithm to an
actual problem, the vector size must be appropriately
determined by considering the statistical nature of thealgorithm. Several formulas that show the statistical nature of
the linear counting algorithm have been presented [9].
However, the formulas are derived using approximation, andthus, are not strictly exact. There have been no studies thatassess the accuracy of the approximation sufficiently.
Therefore, it is necessary and interesting to evaluate theformulas using a strict analysis. In addition, the algorithm
was developed for a database application. Thus, for the flow
counting application, the practical design issues of thealgorithm must be addressed to satisfy the requirements
inherent to IP networks. It is also necessary to evaluate theperformance of the algorithm for flow counting in IP
networks.
This study investigates the above issues using the flow
counting method based on the linear counting algorithm. The
first purpose of this study is to strictly analyze the linear
counting algorithm and assess the accuracy of the previous
approximate formulas. Secondly, the study also focuses on
the problems inherent to the flow counting application.
For the first purpose, the paper strictly analyzes thestatistical nature of the linear counting algorithm. The
analysis is done in a completely different way from theprevious study. The accuracy of the analysis is confirmed
through a computer simulation. It is also shown that theprevious approximate formulas are not always exact
depending on conditions such as the problem size. Using
strict analysis, it is possible to design the vector size, exactly
and independently, for the condition.
To accomplish the second purpose, the paper proposes a
new method to deal with the case when the elements of thevector used in the algorithm are exhausted during thecounting process. It is confirmed that the proposed method
provides an accurate estimation with a simple computational
procedure. The paper assesses the upper bound for thenumber of measured flows. This bound is essential to design
the vector size. The flow counting method based on the linear
counting algorithm is also tested for real-world network data.
Additionally, the paper evaluates the effectiveness of the

Abstract—Real-time flow counting is significant for Internet
Protocol (IP)network management because it enables operators
to take appropriate action against anomalies or performancedegradation. Most flow counting methods proposed in theliterature are based on the linear counting algorithm, which was
originally developed for database system applications.
This paper first strictly analyzes the statistical nature of thelinear counting algorithm. The correctness of the analysis isconfirmed through a computer simulation. The strict analysis isalso compared with an approximate analysis reported in aprevious study. The result clarifies the conditions where theprevious approximate analysis did not provide good accuracy.
The linear counting algorithm is based on a hash function
and a vector. To apply this algorithm to flow counting, twodesign issues arise. One is the method that handles the case of
exhausting all vector elements, while the other is theappropriate vector size. The paper presents a simple andeffective method for the former. For the latter issue, the upperbound for the flow number is derived as a basis for determining
the vector size.
The algorithm is examined for two distinct measurement
scenarios: the “active flow scenario” and the “open socket
scenario.” For each scenario, the estimated accuracy is assessedusing real-world network data. As a result, it is shown that theaccurate measurement is more difficult for the open socket
scenario than for the active flow scenario.
Index Terms—IP networks,
performance measurement, traffic

networkmanagement,

I. INTRODUCTION
Flow measurement in Internet Protocol(IP) networks has
been studied using various metrics such as flow byte volume,
flow packet volume, flow duration, flow timeout, andheavy-hitter flows[1]−[3]. Among these metrics, the numberof flows is significant in several useful applications,
including port scan detection, denial-of-service attack
detection, general measurement in traffic analysis, and theestimation of a TCP connection’s throughput[4]−[8].
In IP networks, a flow is identified by a flow identifier,which is defined as a set of fields in the packet header [4], [7].
Flow counting is defined as a procedure that determines how
many different flow identifiers exist in a packet stream. The
number of flows is measurable in a real-time, online manner,
whereas some other flow metrics [1]−[3]must be analyzed
Manuscript received January15, 2012.
S. Zhu is with the Department of Information Systems Engineering, theFaculty of Engineering, Toyama Prefectural University, 5180 Kurokawa,Imizu-shi, Toyama 939-0398, Japan (e-mail: shanzhu06@hotmail.com).
S. Ohta is with the Department of Information Systems Engineering, theFaculty of Engineering, Toyama Prefectural University, 5180 Kurokawa,Imizu-shi, Toyama 939-0398, Japan (phone: +81-768-56-7500; fax:
+81-768-56-6172; e-mail: ohta@pu-toyama.ac.jp)...

7

Because of this difference, it is trivial to estimate that themethod of [4] is smaller than the method of [7]. Therefore, weshould not easily conclude that the method of [4] is inferior tothat of [7]. This paper strictly distinguishes this difference inthe flow class.

accuracy improvement techniques reported in the literature[7], [10][12]. By employing these results, it becomes
possible to design the algorithm optimally for the flow
counting application.
This paper is organized as follows. First, the studies related
to this paper are reviewed in Section II. Section III strictly
analyzes the statistical nature of the linear counting algorithm.
The proposed strict analysis is compared with theapproximate formulas of the previous study in Section IV.
Section V discusses the design issues when the linear
counting algorithm is applied to the flow counting. In Section
VI, the flow counting based on the linear counting algorithm
is examined for real network data. Finally, Section VII states
the conclusion.

B. Linear Counting Technique
The flow counting problem is equivalent to counting thenumber of unique values found in a data set. A practicalalgorithm for doing this is called the “linear counting
algorithm,” which is comprehensively analyzed in [9].
The linear counting algorithm is described as follows. The
algorithm employs a bit vector of size m. First, all elements ofthe bit vector are initialized to 0. Each data value is theninputted to a hash function, which maps the input value to an
integer from 0 to m – 1. The bit vector element whose index
is the hash output is turned to 1. Therefore, the value 0 meansthat the element was untouched during the hash computations.
After all data values are processed, the number of uniquevalues is estimated from the number of untouched elements.
Reference [9] derives the following important results byanalyzing the linear counting algorithm.
Assume that there are n unique values in the data set. Let
Un be the number of untouched bit vector elements for n
unique values. Un is a random variable. The expected value ofUn, denoted by E(Un), isE(Un) ≅ me – n/m for m >> 1.
(1)
Let n̂ be the expected number of the unique values. Then,from (1),

II. RELATED WORK
A. Flow-Related Measurement
In IP networks, a flow is identified by a flow identifier,which is defined as a set of packet header fields [4], [7]. This
paper defines a flow identifier as a quintuple of source
address, destination address, protocol, source port, anddestination port, as commonly found in the literature[2], [7].
This definition means that a flow is associated with an open
TCP or UDP socket across the monitored link.
Since a flow is a basic unit of communication between
application processes, it is important to measure thecharacteristics of flows for management purposes. Therefore,various flow measurement techniques have been studied[1]−[7]. Reference [1] investigated several flow
characteristics including the flow volume and duration. In
addition, [1] introduced the concept of an active flow; that is,a flow which is active as long as the packets observed areseparated in time by less than a specified timeout value.
Reference [2] investigates the relationship between the flow
characteristics and its applications. In [3], the method of
identifying heavy-hitter flows, which issue many packets, isinvestigated to find the dominant traffic from sampled data.
References [4]−[7] report the flow counting techniques,
which estimate the number of flows during a specified time
period. While the studies of [1]−[3] present offline
approaches, these flow counting techniques are able toprovide real-time, online measurements. Because of thereal-time nature, the flow counting techniques are importantfor network operators to take immediate action against
anomalies or degradation. In [4], [5], flow counting
algorithms based on a bit vector are explored. A similar
technique is used in the traffic measurement systemdescribed in [6]. Meanwhile, Reference [7] suggests that themethod of [4] uses a discrete measurement interval andunderestimates the number of flows. To avoid thisunderestimation, a method called the timestamp vector
algorithm is proposed in [7].
It is inadequate to say that the method of [4]underestimates the flow number because the class of counted
flows is different between the methods presented in [4] and[7]. The method of [4] exactly estimates the number of active
flows, which conforms to the definition found in [1]. By
contrast, the method of [7] tries to count all existing flows,which include inactive flows in addition to active flows.

nˆ = − m log e

Un
.
m

(2)

We can estimate the number of unique values by n̂ . Since Un
is a random variable, n̂ varies for a fixed value of n andincludes an error.
Reference [9] also derived the variance of Un as follows:{}

Var(U n ) ≅ me− n / m 1 − (1 + n / m)e − n / m .

(3)

ˆ n is estimated
Based on (3), the standard error of the ratio n/
as follows: nˆ 
StdError  ≅nm (e n / m − n / m − 1)1 / 2
,
n

(4)

where the standard error is defined as the square root of thevariance.
The linear count algorithm does not work if all of thevector elements are filled up by 1. If this happens, since
Un = 0,the right side of (2) does not have a valid value. Thus,
it becomes impossible to estimate n. For the avoidance of thisproblem, it is essential to considerably decrease theprobability that all the elements are filled up by 1. Reference[9] derives this “fill-up” probability by utilizing the fact thatthe distribution of Un approaches the Poisson distribution forlarge values of m and n. That is,()

P{U n = k} → λk / k! e −λ for m, n → ∞ ,

(5)

where
λ = me − n / m .

Thus, the fill-up probability is:(6)
P{U n = 0} ≅ e − λ .
Equations (4) and (6) are particularly important to assess
the reliability of the algorithm and to determine the vector
8

size. It must be noted that these equations are approximations
obtained assuming that m and n are large. Thus, the equations
may not be sufficiently accurate depending on the values of mand n. Reference [9] compares their approximations with asimulation result to evaluate the accuracy from m = 100 to m
= 100,000. However, since the number of trials in theirsimulation is not large (100 trials), the result is not very
reliable. Moreover, the target of their simulation is limited tothe estimated value n̂ and the standard error. That is, they did
not show any results for the fill-up probability. Thus, a morecomprehensive study is needed to assess the accuracy of theapproximation. In Section IV, the accuracy of theseapproximate formulas is evaluated using strict analysis.

estimated. Assuming that flows are repeatedly counted attimes t1, t2,… Then, the open sockets that exist at ti (i = 2,3,…) must be counted even if they do not issue any packets
during the interval [ti – 1, ti]. Fig. 2 illustrates the flows to be
counted in this scenario. The open socket scenario is as
significant as the active flow scenario because themeasurement result will include the information about low
rate flows.
: Packets

Flows Counted at ti

Flow #1
Flow #2
Flow #3

C. Flow Counting Scenarios
As shown above, flow counting techniques that measuredifferent classes of flows have been reported. This study
categorizes these techniques into the “active flow scenario”
and the “open socket scenario.” Both of these scenarios
provide useful information for network management. Eachscenario is specified as follows:(1) Active Flow Scenario
In this scenario, the algorithm counts the number of flow
identifiers seen in a specified time period, which starts at time
t1 and ends at time t2. In other words, only active flows arecounted for this scenario. The algorithm does not count theflow that starts before t1 and stops after t2, if no packets are
betweent1andt2. Therefore, low rate flows may be dropped
from the measurement. Though low rate flows may beignored, this scenario is still useful because it provides theinformation on active flows, which are influential to the
network performance. The flows counted by this scenario are
depicted in Fig. 1.
: Packets

Flow #4
Flow #5
Flow #6
ti – 1
Flows Not Counted at ti

Fig. 2.

Flows Counted at t2 (Active Flows)

Flow #2
Flow #3
Flow #4
Flow #5

Fig. 1.

Flows Not Counted at t2

Flows counted in the open sockets scenario.

To perform this scenario, the algorithm must continuously
monitor the packet stream and decide how many flows are
generated and not terminated before ti. Thus, it is important todetect flow termination. Reference [7] presents a method that
detects the flow termination through timeouts. This method isbased on the linear counting algorithm. However, the method
employs a vector of timestamps instead of a bit vector.
Because of this, the method is called the timestamp vector(TV) algorithm. When a packet arrives, the method firstobtains the hash output from its flow identifier. Then, its
arrival time is written to the vector element whose index is
the hash output. At measurement time ti, Un is obtained as thenumber of vector elements which are not updated within thetimeout period. The number of existing flows is thenestimated by (2).
Actually, the termination detection by timeouts is not very
accurate. As a method to avoid this inaccuracy, [7] suggests
the usage of the TCP FIN field and adapting the timeout
period. The effectiveness of employing the TCP FIN was
confirmed in [10]. Additional improvement techniques were
examined in [11], [12].

Flow #1

t1

ti

t2

Flows counted in the active flow scenario.

III. STRICT ANALYSISThis section strictly analyzes the statistical nature of thelinear counting algorithm. The analysis derives the exact
probability distribution for the number of bit vector elements
turned to 1. This probability distribution is expressed in arecurring form and obtained by iterative computation. Using
probability distribution makes computing the standard error
and the fill-up probability possible.
Our assumption is that n flows do exist having identifiers,
suchasf1, f2,…,fn. These flow identifiers are mapped to hashvalues h1, h2,…,hn. Amongsth1, h2,…,hn, some values may be
identical because of a hash collision.
Let pn be the probability for a set of n flow identifiers thatare mapped to a particular hash value vector (h1,h2,…,hn).Since a flow identifier is mapped to a particularhash value with probability p = 1 / m,

The linear counting algorithm is applied to this scenario ina straightforward manner. The bit vector elements are firstinitialized to 0 at t1. Then, the flow identifier of an arrived
packet is inputted to a hash function, and the vector element
indexed by the hash output is turned to 1. At t2, the number ofactive flows can be obtained by counting Un and using (2).
The methods of [4], [5] fall into this scenario. The methodof [4] is basically identical to the above linear counting
algorithm. The method also employs a number of ideas suchas the virtual bitmap, the multi resolution bitmap etc, toreduce the memory space.
(2) Open Socket Scenario
In this scenario, the algorithm counts the number of flowsthat exist on the monitored link at a specified time period.
Namely, the number of concurrently open sockets is9pn = pn = 1 / mn.
(7)
Hereafter, set {( f1 , h1 ), ( f 2 , h2 ),K, ( f n , hn )} is referred toas a mapping set. Assume that there existk( 1 ≤ k ≤ min(n, m) ) distinct values H1, H2,…,Hk among h1,h2,…, hn. We define Nn, k as the number of possible mapping
sets between the n flow identifiers and these k distinct hashvalues. Using Nn, k, Nn, k pn is the probability that the hashvalues H1, H2,…,Hk are generated from n flows f1, f2,…, fn.
Let Mb, k be the number of sets {H1 , H 2 ,..., H k } formed bychoosing k distinct numbers from 0, 1,…,m – 1. Trivially,
Mb, k is expressed by binomial coefficients,m
M b, k =   .
k

for 1 < k ≤ min(n − 1, m) .
n Flow Identifiersh(fi)k Distinct Hash Values

f1
f2
f3
f4

H1
H2
H3
Hk − 1Hk

fn − 1fn

fn & fi (i < n): Collision
(a)

(8)

n Flow Identifiersh(fi)k Distinct Hash Values

f1
f2
f3
f4

Let pn, k be the probability that k elements of the bit vector
are set to 1 by n flows. Using (7) and (8), pn, k is obtained asfollows.
 m
1
p n , k = M b, k N n , k p n =   N n , k n .
m
k

(12)

(9)

H1
H2
H3
Hk − 1Hk

fn − 1fn

Equation (9) gives the strict probability that k vector
elements are touched by n flows.
Next, let us investigate the characteristics of Nn, k. First, it isobvious that(10)
Nn, 1 = 1.
This is because all the n flow identifiers generate the samehash value H1 for k = 1. If, k = n,
Nn, n = n!.
(11)
In this case, the flow identifier f1 may generate one of the nhash values H1, H2, …,Hn as h1, and f2 may then generate oneof the n – 1 values other than h1. By repeating thisobservation,(11) is easily derived.
To compute Nn, k for 1 < k ≤ min(n − 1, m) , let us consider
the following two cases:
Case A) The hash value hn generated by the flow identifier
fn colliding with one or more hash values generated by someof f1, f2,…,fn – 1.
Case B) The hash value hn does not collide with any of thehash values generated by f1, f2,…, fn – 1.
These two cases are illustrated in Fig. 3.There are no othercases in which k distinct hash values are obtained from n flow
identifiers. Thus, we can obtain Nn, k by summing the numberof mapping sets for these cases.
For Case A, k distinct hash values are generated from then – 1flow identifiers f1, f2,…,fn – 1. Otherwise, k distinct hashvalues will not be generated because hn collides with some ofthe h1, h2, …,hn – 1 values. The number of mapping sets
between n – 1 flows and k hash values is Nn – 1, k. For each ofthese mapping sets, hn may take one of the kvalues, H1,
H2,…,Hk. Thus, the number of possible mapping sets is
k Nn – 1, k for this case.
In Case B, k – 1 distinct hash values other than hn are
generated from the n – 1 flow identifiers f1, f2,…, fn – 1because
hn does not collide with any of the h1, h2,…,hn – 1 values. The
hash value hn may take one of the k values, H1, H2,…, Hk. For
each of these k values, the number of mapping sets between
other n – 1 flow identifiers and the k – 1 hash values is
Nn – 1, k – 1. Therefore, the number of possible mapping sets is
k Nn – 1, k – 1 in this case.
From the above consideration, we derive:Nn, k = k (Nn – 1, k + Nn – 1, k – 1)

f1, f2, …, fn − 1: k − 1 Hash Values
fn: the Remaining Value without Collision(b)

Fig. 3. Possible mappings from n flows to k distinct hash values: (a) Case
A and (b) Case B.

The following recurrence formulas are derived using (8),(9),(11), and (12).
1pn −1, 1 for n > 1.
m
m − n +1
pn, n =
pn−1, n−1 for n > 1.
mk
m − k +1
pn, k = pn −1, k +pn−1, k −1mm
For n > 2, 1 < k ≤ min(n − 1, m) .
pn, 1 =

(13)
(14)

(15)

Thus, for arbitrary n and k ( 1 ≤ k ≤ min(n, m) ), we cancalculate the probability pn, k by beginning the computation
with p1, 1 and iteratively applying (13)−(15) while
incrementing n. From (9), the initial value of the iteration ism 1
p1, 1 =   = 1 .
1m

(16)

If pn, k is known, the standard error and the fill-up
probability are immediately obtained. The iterative
computation of (13)−(15) is not as fast as the approximate
formulas derived in [9]. However, the computational time isless than a few seconds on a PC with a Core2Quad2.83GHz
CPU for n< 20000. Thus, this method is considerably
practical for a moderate size problem.
To validate the above analysis, a computer simulation was
performed. In this simulation, flow identifiers composed of
5-tuples were randomly generated and fed to a hash function
on the basis of a prime modulo. The hash function maps aflow identifier to an integer in [0, m – 1]. The employed hashfunction is detailed in Appendix A. For the hash output
obtained from a flow identifier, the corresponding vector
element vh is set to 1. After executing this procedure for n
flow identifiers, the number of untouched vector elements
was counted. Repeat in g this procedure yielded the
distribution of Un. The number of repetitions was 106 and the10wherevector size m was a prime number 10007. The distribution of
Un was tested for n = 5000 and n = 30000. That is, thecharacteristic is assessed for the cases of n < m and n > m.
The simulation result is compared to the theoretical value
obtained from (13)−(16) by setting k = m – Un.
Figs. 4 and 5 show the simulation results. In these figures,the x-axis is Un, while the y-axis is the frequency of obtaining
each Un value during 106 trials. The figure also plots 106 pn, k(k = m – Un) as the theoretical value. Fig. 4 shows thecharacteristic for n = 5000, while Fig. 5 shows thecharacteristic for n = 30000. The figures show that thesimulation result is very close to the theoretical value forn < m as well as for n > m. This confirms the correctness ofthe proposed analysis.

m−k)nk = −m loge.
m

The probability pn, k is calculated by (13)−(16). The fill-up
probability by strict analysis is:(18)
P{U n = 0} = p n ,m .
In addition, a computer simulation was performed on theanalysis. In the simulation, n flow identifiers were randomly
generated and the linear counting was executed in each trial.
For standard error evaluation, the squared error of nˆ / n wascomputed from the estimated value n̂ . If the vector was filled
up, the data of the trial was not used. The trial was repeated
106 times and then the standard error was obtained from theaverage of the squared errors. For the fill-up probability, thesimulation procedure is similar. In this evaluation, thenumber of vector fill-up events was summed up for 106 trials.
Thus, the fill-up probability is estimated by dividing the total
number of fill-up events by 106.
Figs. 6 and 7 show the standard error for a small vector
size (m = 101) and a moderate vector size (m = 10007). In the
figures, the x-axis is n, while the y-axis is the standard error ofnˆ / n . In Fig. 6, the proposed strict analysis agrees well withthe simulation result. This supports the accuracy of the
proposed analysis. The given figure shows that the formula of[9] considerably underestimates the error for a larger value ofn. This is predictable because the formula is valid only forlarge values of m. That is, the method is not very accurate if m
is as small as 101.In Fig. 7, the method of [9], the proposed
analysis and the simulation result show almost the same
standard error values. This clearly shows that the formuladeveloped in [9] provides a very good approximation if m is
as large as 10007.

2.0E+04
Theory1.8E+04

Simulation

1.6E+04

Frequency

1.4E+04
1.2E+04
1.0E+048.0E+03
6.0E+03
4.0E+03
2.0E+03
0.0E+00
6000

Fig. 4.

6050
6100
Number of Untouched Elements

6150

Distribution of Un for n = 5000.

2.5E+04
TheorySimulation
2.0E+04

0.16
Strict Analysis

1.5E+040.14

1.0E+04

Standard Error

Frequency

Method of [9]5.0E+03

Simulation

0.12

0.1

0.0E+00
440

460

480
500
520
540
Number of Untouched Elements

Fig. 5.

Distribution of Un for n = 30000.

560

0.08

0.06
0

IV. COMPARISON BETWEEN STRICT ANALYSIS AND
APPROXIMATION

Fig. 6.

This section compares the proposed strict analysis with theapproximate formulas derived in [9]. The comparison is
performed for the standard error of nˆ / n as well as the fill-up
probability. For the method of [9], the values are obtained by(4) and (6). For the strict analysis, the standard error of nˆ / n
is computed by: nˆ 
StdError  =nmin(m −1, n) nˆ k



n,k ,

100
150
200
Number of Flows

250

300

Standard error for a small vector size: m = 101.

However, for m = 10007, the accuracy of theapproximation, depending on the number of flows, is notalways as good as in Fig. 7.Fig.8 plots the standard error
obtained for larger values of n by keeping m to 10007. For
this region of n, the method of [9] substantially
underestimates the standard error. This may cause a problem
in designing the vector size. Suppose that the standard error
should be smaller than 5% and there exist 71500 flows. Then,the method of [9] will set m at 10007 to achieve the target2∑  n − 1 p

50

(17)

k =1

11

through the simulation. The figure shows that theapproximation overestimates the fill-up probability. Thismeans that the error by the approximation is on the safe side.
That is, if m is determined for a target fill-up probability byusing the formula of [9], the actual fill-up probability will besmaller.

standard error because the error value obtained by (4) is0.0497. However, the actual error value will be larger than
5%; the value is computed as 0.0567using the proposed strict
analysis. Fortunately, the approximation does not greatly
differ from the strict value. Thus, the problem caused byunderestimation is avoidable by setting m to a slightly larger
value than that obtained by (4).

1.0E+00

0.014
Method of [9]0.013

1.0E-01

Strict Analysis
Fill-Up Probability

Simulation
Standard Error

0.012
0.011
0.01

1.0E-02

1.0E-03
Method of [9]1.0E-04

0.009

Strict Analysis
Simulation

0.008
1.0E-05
240

0.007
0

Fig. 7.

5000

10000
15000
20000
Number of Flows

25000

260

280

30000

Fig. 9.

300 320 340
Number of Flows

360

380

400

Fill-up probability for a small vector size: m = 101.

Standard error for a moderate vector size: m = 10007.
1.0E+00

7.0E-02
1.0E-01

Fill-Up Probability

Standard Error

6.5E-02

6.0E-02

5.5E-02

1.0E-02

1.0E-035.0E-02

4.5E-02

Strict Analysis

Strict Analysis

Simulation

Simulation
4.0E-02
70000

Method of [9]1.0E-04

Method of [9]

72000
74000
Number of Flows

1.0E-05
68000

72000

76000

76000
80000
Number of Flows

84000

Fig. 10. Fill-up probability for a moderate vector size: m = 10007.

Fig. 8. Standard error for m = 10007 in the region where the method of [9]is not accurate.

1.0E-14

Fill-Up Probability

Figs. 9 and 10 compare the proposed strict analysis withthe method of [9] and the simulation result for the fill-up
probability. Fig. 9 shows the characteristic for m = 101 while
Fig. 10 shows that m = 10007. Fig. 9 shows, if m = 101, themethod of [9] considerably overestimates the fill-up
probability in comparison with the strict analysis and thesimulation result. In contrast, Fig. 10 confirms that theapproximation is in tandem with the strict analysis and thesimulation result if m is as large as 10007.
For m = 10007, the approximate value of the fill-up
probability is not very accurate if the fill-up probability is
low.This is shown in Fig. 11, which compares theapproximation with the strict analysis for the region where
the fill up probability is less than 10−14. In this figure, thesimulation result is omitted because it is difficult to obtainreliable data with a sufficient number of fill-up events

1.0E-15

1.0E-16
Method of [9]Strict Analysis

1.0E-17
56000

56200

56400
56600
Number of Flows

56800

57000

Fig. 11. Fill-up probability for m = 10007 in the region where the method of[9] is not accurate.

12

For practical flow counting, the expected flow number nwill be considerably large. To estimate such a flow number
accurately, the vector size m should also be large. Thus, theabove results imply that the approximate formulas of [9] areconsiderably reliable for flow counting applications in real
networks.

very large. For n > 88000, the error becomes smaller for the
proposed method. This characteristic shows that the accuracyof the proposed method is not inferior to the method
mentioned in [9].
8.0E-02
7.0E-02

V. DESIGN ISSUES IN THE FLOW COUNTING APPLICATION

6.0E-02

Standard Error

To apply the linear counting algorithm to flow counting,two design issues must be addressed. These are strategies forhandling the vector fill-up problem and determining theappropriate vector size.
A. Vector Fill-Up Problem
If all vector elements are updated during the measurement
period, Un becomes 0. Thus, (2) does not yield any valid
estimation. Therefore, it is necessary to establish a method todeal with this case. As such a method, [9] recommends
rerunning the linear counting algorithm with a different hashfunction. This may be a practical solution for a databasesystem, where the data is stored in a hard disk. Unfortunately,
this method is inadequate for flow counting. To perform thismethod for flow counting, the flow identifiers of all arrived
packets must be stored in the memory to prepare for possible
re-execution of the algorithm. This requires an excessively
large memory space. Moreover, if the algorithm is rerun,
additional computational time is required to re-compute hashvalues and evaluate Un. However, if a large memory space isavailable to store the flow identifiers, it is advisable toincrease the vector size with the available memory space thanto store the flow identifiers. Since a large vector size will
make the fill-up probability negligibly small, it becomes
unnecessary to store the flow identifier and rerun thealgorithm.
This study proposes a very simple alternative method. Thatis, if the vector is filled up, the estimated flow number n̂ is
set to a constant,nˆ = nmax ,(19)
where nmax is the maximum number that the algorithm canevaluate with the vector size m. Understandably from (2),nmax is the estimated flow number when Un = 1. Thus,(20)
nmax = m log e m .
With this method, it is unnecessary to store all the flow
identifiers seen in the measurement period and rerun thealgorithm with different hash functions. Thus, this method isvery practical for real-time flow counting from the viewpointof storage consumption as well as computational time. The
method obviously outputs the most accurate estimation for
n > nmax. The method of [9] does not yield a solution that islarger than nmax. This means that the estimation by themethod of [9] is not better than the proposed method. Forn < nmax, the proposed method may overestimate the flow
number. However, the expected error caused by thisoverestimation is not large. This is confirmed in Fig. 12.
Fig. 12 plots the simulation result that compares thestandard error obtained by the proposed method with themethod of [9]. The vector size m is 10007 in this figure. The
figure shows that the error of the proposed method is slightly
larger for 70000 < n < 86000. However, the difference is not

5.0E-02
4.0E-02
3.0E-02
Method of [9]2.0E-02

Proposed Method

1.0E-02
0.0E+00
60000

70000

80000
90000
Number of Flows

100000Fig. 12. Comparison between the methods that handle the vector fill-up
problem.

B. Vector Size
The vector size should be determined to achieve a
sufficiently low error and a negligibly small fill-up
probability for the maximum number of flows. Thus, it
becomes necessary to forecast the maximum number of flows
observed in the measurement period.
The number of flows is bounded by the number of packets
arriving in measured time. The number of packets is
estimated by the product of the packet rate and time. The
packet rate is bounded by the ratio of the link bit rate to thepacket size. Therefore, for time T (s), the link bit rate r (b/s),
and the minimum packet length lmin, the flow number n isbounded as follows:
n≤

rT
.
lmin

(21)

This upper bound is often not tight. However, it can betight for extreme cases, for example, when the monitored link
is under a UDP flood or a TCP SYN flood attack with aspoofed source address [13]. For these attacks, the link
capacity may be fully used by short attack packets, each ofwhich have a different source address and source port. Thus,
the number of observed flow identifiers may approach that of
the arrived attack packets.
For the open socket scenario, Un is the number of vector
elements untouched during the timeout period. Thus, thevector should not be fully used by the packets that arrive
during the timeout period. This means that the right side of(21) must be evaluated by setting T to the timeout period. It
should be noted that the timeout period may be larger than themeasurement interval. For the active flow scenario, T issimply the interval from the start time t1 to the stop time t2.
For example, assuming that the number of flows is estimatedevery 1 s, r is 1 Gb/s and lmin is 42 octets. Then, (21)concludes that n is not larger than 2.97 × 106. This requires
the vector size m to be 3.84 × 105 if the standard error is lessthan 0.01.
13

error decreases by increasing the value of m. In Addition, theerror of the linear counting algorithm is very close to thetheoretical standard error, which is obtained assumingn = 2445. This characteristic implies that the error is almost
determined by the statistical nature of the algorithm for theactive flow scenario. Thus, it is easy to exactly estimate theerror for the vector size and the average flow number byusing (4) or (13)−(16).

VI. EVALUATION BY NETWORK DATA
The effectiveness of flow counting, which is based on thelinear counting algorithm, is evaluated by using real-world
network data. The evaluation is performed for two different
scenarios. It is shown that the error characteristic is very
different depending on the scenario.
A. Active Flow Scenario
The linear counting algorithm is implemented as aprogram that calculates the number of flows for the active
flow scenario. The program can read a live packet stream aswell as a tcpdump-format file through the pcap library[14]. The program is written in C language and runs on aLinux OS.
The program was executed for real-world network data,
which is available from the MAWI database supported by the
WIDE project [15]. From the files provided by the database, a
1 hour file was created by combining four 15-minute files
taken on April 13, 2011 at sample point F. The input data file
was then created by extracting IP version 4 TCP packets fromthis 1 hour file. The input data file was fed to the program,which estimated the number of flows with an interval of 1 s.
For comparison purposes, the true number of flows was also
obtained by the method described in Appendix B by using the
tcpslice [14] and tcptrace [16] programs.
The input data was taken for a 150 Mb/s bidirectional link.
From this bit rate, the upper bound of n is calculated as
8.9 × 105by using (20). The actual number of flows was muchsmaller than this bound. Fig. 13 shows the output of the linear
counting algorithm for m = 10007 in comparison with thetrue value. The output of the linear counting algorithm is very
close to the true value. Fig. 14 depicts the close-up of thecharacteristics for m = 50021 and m = 3001. The figure
indicates that the estimation for m = 50021 is very accurate.
By contrast, a substantial error is observed for m = 3001. Thisshows that the statistical error of the algorithm is larger for asmaller value of m.
35000

Number of Active Flows

30000

3200

Number of Flows

3000

2600
2400
True Valuem = 50021
m = 3001

2200
2000
0:04:00

0:04:10
0:04:20
Time (hh:mm:ss)

0:04:30

Fig. 14. Estimation by the linear counting algorithm for m = 50021 andm = 3001.
0.02
Experimental Value
Theoretical Value (n = 2445)

Standard Error

0.015

0.01

0.005

True Value

01000

Linear Counting
Algorithm

25000

10000
Vector Size, m

100000Fig. 15. Relationship between the standard error and the vector size for theactive flow counting scenario.

20000

The above results conclude that the number of flows isexactly estimated by the linear counting algorithm for theactive flow scenario. Additionally, the actual estimation error
is easily forecasted by the theory. Therefore, it is not difficult
to determine the vector size for a given standard error, thefill-up probability, and an expected flow number for this
scenario.

15000
10000
5000
0
0:00:002800

0:15:00

0:30:00
Time (hh:mm:ss)

0:45:00

1:00:00

B. Open Socket Scenario
The linear counting algorithm was also examined for the
open socket scenario. A program was implemented for thispurpose as well. The program basically detects thetermination of a flow by detecting timeouts. Thus, theprogram employs a timestamp vector (TV), which wasintroduced by [7]. However, the termination detection isbased on a timeout, thus not very accurate. This means that alarge estimation error is unavoidable. Thus, the program

Fig. 13. Flow number evaluated by the linear counting algorithm in theactive flow counting scenario.

To clarify the relationship between m and the statisticalerror, the standard error was evaluated for the linear counting
algorithm by changing the value of m. This result is depicted
in Fig. 15. The figure also shows the theoretical value of thestandard error computed for n = 2445, which is the average
flow number of the 1hour data file. Fig. 15 shows that the14

employs three improvement techniques, which are suggested
or examined in the literature [7], [10]−[12]. These techniques
are referred to as T1, T2, and T3 hereafter and are describedas follows.
T1) FIN/RST message utilization [7], [10]This mechanism avoids the overestimation introduced byconsidering terminated flows to exist during the timeout
period. Since a TCP flow is terminated with a FIN or RST
message in a regular operation, its termination is basicallydiscovered by watching a FIN or RST message. On the basisof this concept, the overestimation is eliminated bysubtracting the number of flows that issued FIN/RST
messages for the timeout period from the estimated flow
number. The number of flows that issued the FIN/RST
messages is easily counted by using another TV, whose
elements are updated at arrivals of FIN/RST messages. Thisadditional TV is referred as the FIN vector hereafter.
T2) Short timeout for one-packet flows [11], [12]In real-world network data, there are many one-packet
flows, each issuing only one packet (for example, a TCP
SYN message). For one-packet flows, the termination cannot
be detected by the FIN/RST messages and thus must be foundby analyzing timeouts. Unfortunately, the timeout based
method considers a one-packet flow to exist for the timeout
period though it is actually terminated in a very shorttransmission time, causing excessive overestimation. Thisoverestimation decreases by counting how many times each
TV element is updated. Suppose that the update count of anelement is 1. For this case, the element is obviously updated
by one flow and only one packet has been issued from theflow. Then, it is likely that this flow is a one-packet flow.
Thus, the overestimation is reduced by applying a smaller
timeout period to such a vector element. Let uh denote how
many times the h-th vector element ( 0 ≤ h ≤ m − 1 ) was
updated. In the following, let To, 1denote the timeout period
for the TV element having uh = 1. Similarly, the timeout
period is denoted by To, 2 for the element having uh = 2.
Timeout period for other elements is To. The value uh is reset
to 0 when the measurement starts or the element is not
updated for To.
T3) FIN/RST message count [11]The accuracy of termination detection is improved bychecking FIN/RST messages. However, a host may transmit
multiple FIN messages repeatedly, if the peer host does not
respond. In this case, the program considers the flow to beterminated by the first FIN message, though it is actuallyended with the last FIN (or RST) message. If this happens,the flow number is underestimated because the flow is
considered to end earlier than its actual termination. This
underestimation is improved by counting the number of the
FIN messages associated with the h-th vector element. Let vh
denote the number of FIN messages. Then, if vh> 2, the h-th
FIN vector element is not used to count the terminated flows.
That is, the program considers that the flow associated withthis element is repeatedly issuing multiple FIN messages andis not terminated. The counter vh is reset to 0 when themeasurement starts or the TV element is not updated for To.
For an RST message arrival, vh is set to 1 and thus theassociated FIN vector element is utilized to count theterminated flows.
The improved version of the TV algorithm that employs

the above techniques T1, T2, and T3 was implemented as aprogram, which was written in C language and runs on aLinux OS. It uses the pcap library to read live traffic as wellas the tcpdump format files.
The program was executed for the same 1hour file that wasused in the Section VI.A. Fig. 16 shows the result. In Fig. 16,
m was set to 4000037. The timeout periods To, To, 1, andTo, 2were set at 96 s, 1 s, and 10 s, respectively. These timeout
values were chosen to achieve the best result.
By comparing Fig. 16 and Fig. 13, it is noticeable that the
number of flows greatly differs for the two scenarios. The
average flow number was 2445 for the active flow scenario
while it was 7313 for the open socket scenario. This showsthat the real-world network holds many low-rate inactive
flows, which are not counted for the active flow scenario.
This difference suggests that these two scenarios arecompletely different and should not be confused.
In Fig. 16, the output of the improved TV algorithm isconsiderably close to the true value. The standard error of
estimation by the program was 0.046. Meanwhile, thetheoretical error value of the linear counting algorithm is
3.5×10 – 4 form = 4000037 and n = 7313. Therefore, theobserved error is much greater than the theoretical value,
computed by the statistical nature of the linear counting
algorithm. In Addition, the error for the open socket scenario
greatly depends on the parameters used in the termination
detection. For example, if To increases to 110 s, the error
increases to 0.076. Similarly, if To decreases to 80 s, the error
increases to 0.088. Judging from these characteristics, it isconcluded that the termination detection mechanism is themain cause of the estimation error for the open socket
scenario.
40000

Number of Flows

35000
30000

True Value
Improved TV
Algorithm

25000
20000
15000
10000
5000
0
0:00:00

0:15:00

0:30:00
Time (hh:mm:ss)

0:45:00

1:00:00

Fig. 16. Flow number evaluated by the improved TV algorithm in the open
socket scenario.

The improvement techniques are essential to achieve good
estimation accuracy. Fig. 17 shows the effectiveness of thetechnique T2. The timeout period was 4 s for the original TV
algorithm, while To, To, 1, and To, 2were 11 s, 1 s, and 10 s,
respectively, for the method improved with T2.These timeout
values were chosen to minimize the standard error. In thegiven figure, the number of flows exhibits a peak from
0:28:41 to 0:28:42 because of temporally increased
one-packet flows. For this period, the output of the originalTV algorithm greatly overestimates the flow number. In
contrast, the overestimation is completely removed by
employing the technique T2. Fig. 18 compares the case of15

improvement techniques T1, T2, and T3 are employed.
However, the vector size m must be large to obtain theaccurate estimation with these techniques. This means thatthe required memory consumption is large for the open
socket scenario.

employing only T2 with that of employing T1, T2, and T3.
The figure shows that the accuracy is further improved byusing T1 and T3 in addition to T2.
70000
60000

40000
True Value

35000

Original TV Algorithm
Improved with T2

40000
30000
20000
10000

m = 4000037
m = 500011

25000
20000
15000
10000

0
0:28:30

0:28:40
0:28:50
Time (hh:mm:ss)

0:29:00

5000
0
0:28:30

Fig. 17. Effectiveness of the improvement technique T2.
8500

0:28:40
0:28:50
Time (hh:mm:ss)

0:29:00

Fig. 19. Characteristic of the improved TV algorithm for m = 4000037 andm = 500011.

True Value
8000

True Value

30000
Number of Flows

Number of Flows

50000

T2

Number of Flows

T1 + T2 + T3
7500

VII. CONCLUSION
This paper discusses the real-time flow counting techniquebased on the linear counting algorithm, which is based on ahash function and a vector. First, the paper proposed a strict
analysis to clarify the exact statistical nature of the algorithm.
The accuracy of the proposed analysis was confirmed
through a computer simulation. Thereafter, strict analysis
was compared with the approximate analysis derived in [9].
As a result, it was shown that the approximations were
accurate with a few exceptions.
Next, the paper investigated how to treat the vector fill-up
problem in flow counting. It was shown in the method of [9]that re-executes the algorithm with a different hash function
is not adequate for flow counting. Instead, the paper reviewed
a very simple method, which uses the maximum output value
for the vector fill-up case. The simulation results confirmed
the extensiveness of the method. The upper bound of the flow
number was also investigated as a basis for determining theappropriate vector size.
This paper strictly distinguishes between two different
measurement scenarios of flow counting: the active flow
scenario and the open socket scenario. The algorithm wastested for these scenarios using real-world network data. As aresult, for the active flow scenario, it was found that theestimation is accurate and the error is caused by the statisticalnature of the algorithm. It is more difficult to accurately
estimate the flow number for the open socket scenario. For
this scenario, the estimation error is larger because of the
difficulty in finding flow termination. It was also found that alarge vector size is necessary for an open socket scenario.
Estimating the flow number accurately with a small memory
space remains to be an open problem.

7000
6500
6000
5500
0:35:00

0:40:00
Time (hh:mm:ss)

0:45:00

Fig. 18. Effectiveness of the improvement techniques T1 and T3.

The estimated accuracy of the improved TV algorithm
greatly depends on the vector size m. For example, thestandard error increases from 0.046 to 0.35 by reducing mfrom 4000037 to 500011. Fig. 19 compares the outputs form = 4000037 and m = 500011. The figure shows that theflow number is overestimated for m = 500011. Thisoverestimation is caused by T2 and T3. For these techniques,
the counter values uh and vh exactly show the number ofpackets issued by a flow only if there is no collision for a hashvalue h. For T2, if two or more one-packet flows generate thesame hash value, uh will be greater than 1. Thus, the shorttimeout period To, 1 is not applied to these one-packet flows.
This causes overestimation. Similarly, for T3, if three flows
generate the same hash value, vh becomes larger than 2. Thus,
the algorithm considers these flows to be retransmitting FIN
messages. If this happens, the termination is not detected by
the FIN messages. This also causes overestimation.
Therefore, the collision probability among hash outputs must
be negligibly small, for techniques T2 and T3 to work
correctly. This requires a large vector size.
In conclusion, it is more difficult to accurately count theflow in the open socket scenario compared to the active flow
scenario. This is because the error is caused by the detectionof flow termination. Nevertheless, the estimation isconsiderably accurate as shown in Fig. 16, if the

APPENDIX
A. Hash Function
This study employs a prime-modulo-based hash function.
16

[12] S. Ohta and S. Zhu, “Real-time measurement of flows classified
according to their application,” in Proc. APNOMS 2011, Taipei,
Taiwan, 2011, paper TS3-2.
[13] T. Peng, C. Leckie, and K. Ramamohanarao, “Survey of
network-based defense mechanisms countering the DoS and DDoS
problems, ”ACM Computing Surveys, 39, 1, Article 3, 2007.
[14] TCPDUMP/LIBPCAP Repository, Available:
http://www.tcpdump.org/[15] Wide: Working Group MAWI, Available:
http://www.wide.ad.jp/project/wg/mawi.html[16] tcptrace - Official Home Page, Available: http://www.tcptrace.org/

Assume that we are monitoring an IP version 4 packet stream.
Let is and id denote the source and destination addresses, andjs and jd denote the source and destination port numbers,
respectively. In addition, let p be the protocol field value.
Then, for the flow identifier x = (p, is, id, js, jd), the function
h(x) ish( x) = {a (216 p ⊕ is ⊕ id ) + b ( js ⊕ jd )} mod m ,(a.1)
Where a and b are constants and m is a prime number. In thesimulations, a and b were set at 1. In Fig. 12, for the methodof [9], b was changed to 1, 2, … to obtain different hashfunctions. For the evaluation that uses real-world network
data, a and b were set to 253 and 31, respectively to obtainbetter results.

Shan Zhu received the B.E. degree from the Liaoning University of China in2005 and the M.E degree from the Northeastern University of China in 2008.
She entered Toyama Prefectural University in 2008 and is now adoctorate student.
Ms. Zhu is a student member of the IEICE.

B. True Number of Flows
For active flow and open socket scenarios, the true numberof flows was estimated as follows.
To obtain the number of active flows, the packet dump file
was first sliced into 1 s files by the tcpslice [14] program.
Each 1 s file is inputted into the tcptrace program. The
output shows how many flows issued packets during a 1 s
period.
For the open socket scenario, the packet dump file is firstentered in the tcptrace program. The output of the
program is stored in a text file. This output file contains thearrival times of the first and last packets in a flow. Assume
that the flows are repeatedly counted at times t1, t2, …. Then,the true number of flows at ti (i = 1, 2 …) are obtained bycounting the flows of the first packet arriving before ti and thelast packet arriving after ti − 1. A Perl script was written to
extract time information from the tcptrace output file andcount the number of flows to be measured at ti.

Satoru Ohta received the B.E., M.E., and Dr. Eng. degrees from the Tokyo
Institute of Technology, Tokyo, Japan, in 1981, 1983, and 1996,
respectively.
In 1983, he joined NTT, where he worked on the research anddevelopment of cross-connect systems, broadband ISDN, network
management, and telecommunication network planning. Since 2006, he has
been a professor in the Department of Information Systems at Toyama
Prefectural University, Imizu, Japan. His current research interests are
network performance evaluation and power management of network
systems.
Dr. Ohtais a member of the IEEE, IEICE, and ECTI. He received the
Excellent Paper Award in 1991 from IEICE.

REFERENCES[1]

K. C. Claffy and H. W. Braun, “A parameterizable methodology forInternet traffic flow profiling,”IEEE J. on Selected Areas in Communs.,
SAC-13, 8, 1995, pp. 1481-1494.
[2] M.-S. Kim, Y. J. Won, H.-J. Lee, J. W. Hong, and R. Boutaba,“Flow-based characteristic analysis of Internet application traffic,” inProc. E2EMON, San Diego, California, USA, 2004, pp. 62-67.
[3] T. Mori, T. Takine, J. Pan, R. Kawahara, M. Uchida, and S. Goto,“Identifying heavy-hitter flows from sampled flow statistics, ”IEICE
Trans. on Commun., E90-B, 11, 2007, pp. 3061-3072.
[4] C. Estan, G. Varghese, and M. Fisk, “Bitmap algorithms for counting
active flows on high speed links,” in Proc. IMC '03 Miami Beach, FL,
USA, 2003, pp. 153-166.
[5] C. Estan, G. Varghese, and M. Fisk, “Bitmap algorithms for counting
active flows on high-speed links, ”IEEE/ACM Trans. on Networking,14, 2006, pp. 925-937.
[6] K. Keys, D. Moore, and C. Estan, “A robust system for accurate
real-time summaries of Internet traffic,” in Proc. SIGMETRICS '05,
Banff, Alberta, Canada, 2005, pp. 85-96.
[7] H.-A. Kim and D. R. O’Hallaron, “Counting network flows in realtime,” in Proc. GLOBECOM 2003, San Francisco, 2003, pp.
3888-3893.
[8] S. Zhu and S. Ohta, “Simple method to passively estimate thethroughput of a TCP flow in IP networks,” in Proc. ICOIN 2010,
Busan, Korea, 2010, paper 5B-3.
[9] K.-Y. Whang, B. T. Vander-Zanden, and H. M. Taylor, “A linear-time
probabilistic counting algorithm for database applications, ”ACM
Transactions on Database Systems, 15, 2, 1990, pp. 208-229.
[10] S. Zhu and S. Ohta, “Fast and accurate flow counting algorithm for the
management of IP networks,” in Proc. NOMS 2010, Osaka, Japan,
2010, pp. 918-921.
[11] S. Zhu and S. Ohta, “Real-time measurement of flows classified
according to their application for IP networks, ”Cyber Journals:
Multidisciplinary Journals in Science and Technology, Journal of
Selected Areas in Telecommunications (JSAT), 2, 12, December
Edition, 2011.

17