Simple Method to Passively Estimate theThroughput of a TCP Flow in IP Networks
Shan Zhu1, Satoru Ohta2
Department of Information Systems Engineering, Faculty of Engineering, Toyama Prefectural University
5180 Kurokawa, Imizu-shi, Toyama 939-0398, Japan1shanzhu06@hotmail.com, 2ohta@pu-toyama.ac.jp

Abstract— The throughput of a TCP (Transmission Control
Protocol) flow is significant for managing the quality of TCPbased services in IP (Internet Protocol) networks. This paper
presents a simple method that estimates the throughput of a
TCP flow.
The method uses two passive measurement
algorithms; one estimates the total bit rate for all flows, while
the other counts the number of TCP flows. With thesealgorithms, the throughput of a flow is easily computed by
dividing the total bit rate by the flow number. However, theexisting flow counting algorithm has two shortcomings:
computational time and overestimation of the flow number.
Thus, the paper proposes an improved flow counting algorithm
that decreases computational time and avoids overestimation.
The effectiveness of the proposed flow counting algorithm isconfirmed experimentally.
The paper also shows theimplementation of a program that estimates the throughput of aflow using the proposed flow-counting algorithm as well as thebit rate estimation algorithm reported in RFC 2859. The
correctness of the measured flow throughput is also certified by
an experiment.

I. INTRODUCTION
In IP networks, the throughput of a TCP flow is asignificant metric for evaluating the performance of TCPbased services. This is because the user’s experience (forexample, the download time for file transfer) is determinedby the throughput of a flow. Even if the total bit rate on alink is unchanged, the file download time may vary greatly
depending on the number of concurrent users. Thus, tomanage the quality of TCP services strictly and detect its
degradation, the throughput of a TCP flow is anindispensable metric.
The throughput of a TCP flow is estimated in several ways.
For example, it can be obtained by transferring a file with a
specified size through FTP (File Transfer Protocol) andmeasuring its transfer time. In addition, several softwaretools evaluate TCP throughput [1,2]. However, these arebased on active measurement and thus intrusive to network
resources. Since the measurement traffic affects network
conditions, it is difficult to know the true performance withthese methods.
When using flow analysis tools [3], it is possible tomeasure the throughput of a TCP flow. Unfortunately, sincethese tools analyse flows on the basis of complex procedures,
their scalability to bit rate is questionable because of highprocessing load. Thus, it becomes indispensable to develop amethod that measures the throughput of a flow throughsimple computation.
This paper examines a method that computes thethroughput of a TCP flow by dividing the total bit rate of all
TCP flows by the number of flows. The implementation andprocess of this approach is much simpler because it is notnecessary to trace every TCP connection. The method iscomposed of two measurement algorithms: a total bit rateestimation algorithm and a flow counting algorithm. The
total bit rate can be easily estimated through the algorithm
shown in RFC 2859 [4]. Therefore, it is important toestablish a method that evaluates the number of TCP flows
accurately in less computational time.
Previous studies have examined methods of counting thenumber of flows [5-8]. In reference [5], a real-time flow
counting algorithm called the timestamp-vector algorithm is
proposed. The algorithm has improved the bitmap-basedalgorithm of [6] by reducing underestimation. However, theexecution time of the timestamp-vector algorithm is not
sufficiently small because it needs to scan a large vector tocount flows. Another shortcoming of the algorithm is that it
overestimates the number of flows under a certain condition.
This study investigates why the timestamp-vector
algorithm overestimates the flow number and wastes a large
amount of computational time. Then, an improved flow
counting algorithm is proposed to address these problems.
The proposed algorithm reduces the time complexity byemploying multiple counters to estimate the number of flows.
The accuracy of the estimation is also improved using the
FIN flag of the TCP header. In comparison with thetimestamp-vector algorithm, the proposed algorithm reduces
the computational time greatly and more correctly estimates
the number of flows. These advantages were confirmed by
an experiment.
The study implemented a program that evaluates theaverage TCP throughput of a flow by combining the total bit
rate estimation of RFC 2859 and the proposed flow counting
algorithm. It is also experimentally confirmed that the
program computes TCP throughput correctly.
The proposed method has several important applications.
For example, the method is applicable to load-balancing for aserver cluster or a multi-homing environment. For thisapplication, suppose that the performance of a host or link ismore degraded than others. Then, the degraded host or link
can be successfully identified with using the proposedmethod through the decrease of the flow throughput. Then,the system can distribute lighter load to the identified host or
link so as to improve the performance. Another example isthe traffic restriction such as admission control, which avoids
excessive load given to the network. If the network isexcessively loaded, the throughput of a flow is reduced. Thissuggests that the occurrence of excessive load is easily
detected by the proposed method. Thus, the output of themethod can trigger the traffic restriction process. As shownin these applications, the proposed method is a promisingtechnique to achieve superior performance in IP networks.
This paper is organized as follows. Section Ⅱ discusses
the problems of the timestamp-vector algorithm and the
difficulty of estimating the average throughput per flow.
Section Ⅲ presents the improved flow counting andthroughput estimation algorithm. Experimental results areshown in Section Ⅳ to evaluate the effectiveness of the
proposed algorithm. Finally, Section Ⅴ concludes this study.
II. PROBLEM DESCRIPTIONA

Throughput per Flow
The average throughput of a flow is computable asfollows.
For
each
flow
identifier(protocol,
source/destination address, source/destination port), record
the start time of the flow and the number of data bytes
transferred. The start time must be stored at the first packet
arrival of the flow, while the amount of data bytes must be
updated at every packet’s arrival. Then, the throughput of aflow is computed by dividing the number of transferred bytes
by the elapsed time. The average throughput is obtained bysumming the throughput of each flow and dividing by the
number of flows.
The difficulty of this method is the computational timerequired.
The above procedure is composed of thecomputation per packet and that per flow. Because thenumber of existing flows can be very large, the computation
per flow can be very time consuming.
The total bit rate for all flows passing a link is easier toobtain than the throughput of a flow. By applying themethod of RFC 2859, the total bit rate is computed without
executing any computation associated with flows. Therefore,
if we can count the number of flows without performing
computation per flow, it becomes possible to estimate thethroughput of a flow with less computational time.
B. Timestamp-Vector Algorithm
Previous studies have examined methods of counting thenumber of flows [5-8]. Among these studies, several papers
examined a flow counting algorithm that utilizes a hashfunction and a bitmap [6, 8]. This approach is advantageousin point that it can estimate the number of flows with anextremely small amount of memory. However, it wasreported that the accuracy achieved by the bitmap approachis not very good and the number of flows is often
underestimated.

Reference [5] reports an algorithm for counting active
flows in IP packet traffic. This algorithm is based on two
mechanisms: a timestamp vector (v0, v1, ..., vb − 1) and a hashfunction that maps the flow identifier to integer 0, 1, ..., b − 1.
In the following, the Timestamp vector is abbreviated as TV.
Using these mechanisms, the algorithm is summarized asfollows.
1) TV update
For each packet arrival, compute the hash function output
h ( 0 ≤ h < b ) from the flow identifier. Then, set TV element
vh at the arrival time.
2) Flow countExecute the following periodically. Obtain value c, whichis the number of TV elements updated for the last To seconds(To: timeout period). Compute the number of active flows,denoted as n, byb.
(1)
n = b log eb−cWith the algorithm, a flow is judged to be active if apacket of the flow arrives during last To seconds. Equation(1) is derived as follows [5]. Assume that the hash function
distributes a given flow identifier to an integer uniformly.
Let p denote the probability that a TV element vh is updated
by a flow. Obviously,
p = 1/ b .
(2)
Next, let pz be the probability that an element is not
modified by any of n flows. Then,

{

}

n/b

p z = (1 − p ) n = (1 − 1 / b) b
(3)
It is known that
(1 − 1 / b)b → e −1 ( b → ∞ ).
(4)
Thus, for large b,
pz ≈ e−n / b(5)Therefore, the average number of vector elements
unchanged within To seconds is,
bp z ≈ be − n / b .
(6)
The above value is equal to b – c. From this relation, it is
not difficult to see that Eq.(1) is obtained.
In the algorithm, the computational time of the flow countprocess is more critical because it takes O(b) time to scan theTV, and b should be very large for accurate flow counting.
In addition, the timestamp-vector algorithm yields
incorrect results for short-term flows. Figure 1 shows theoverestimation of short-term flows using this algorithm. The
data for the figure were obtained by the configuration
described in Section IV. As the figure shows, the flow
number estimated by the timestamp-vector algorithm is about
three times larger than the actual number of flows in mosttime periods. This overestimation happens because thealgorithm must hold some terminated flows for the timeout
period To. Thus, the algorithm incorrectly counts many
terminated flows as active flows, resulting in overestimation.

m = ⎣wh / M ⎦ mod k .

160
Number of Flows

Actual Flows(10)

Timestamp-Vector Algorithm

2) Flow countAssume that c elements are updated in the TV while felements are updated in the FIN message table during To. If t
reaches time BM (B: integer), compute c and f by

120
80
40

∑ c,
f =∑ f .
c=

0
0

10

20

30
Time(sec)

40

50

60

Fig. 1. Overestimation of flows by the timestamp-vector algorithm.

III. PROPOSED METHODThis study combines the total bit rate evaluation and aflow counting algorithm.
Because the flow counting
algorithm has problems, the study improves the algorithm.
A. Improved Flow Counting Algorithm
The improved algorithm is based on timestamp-vector. It
also updates the TV upon packet arrivals. However, insteadof taking O(b) time to scan the b elements, we use anotherone-dimensional array, called the counter array, which
records the number of updated entries in M (seconds). By
employing the counter array, the algorithm greatly decreases
the computational time.
The improved algorithm solves the overestimation
problem using TCP FIN messages. At the end of a TCP flow,a host issues a TCP FIN message containing protocolspecific termination information. The algorithm employs a
FIN message counter array, which records the number ofterminated flows in M (seconds). Additionally, a FIN
message table (w0, w1, ..., wb − 1) is needed to store the FIN
message arrival time for the hash output of each flow
identifier.
The mechanism of the counter arrays and the proposed
algorithm are as follows. Assume that the interval ofcounting flows is M (seconds) and To = kM (seconds), where
k is a positive integer. Let t (seconds) be the current time.
The proposed method employs k counters c0, c1, ..., ck − 1 andFIN message counters f0, f1, ..., fk − 1. The counter ci and fi( 0 ≤ i < k ) are used to estimate the number of flows that
send packets for
ATo + iM ≤ t < ATo + (i + 1) M (A: integer). (7)The algorithm is1) TV update
For each packet arrival, obtain the hash value h, andcompute i and j from vh and t as follows:i = ⎣t / M ⎦ mod k ,(8)

j = ⎣vh / M ⎦ mod k .

(9)Then, increment ci by 1. If vh ≥ t − To , decrement cj by 1.
Set vh at the arrival time. If the FIN field is 1, increment fi by
1 and set wh at the arrival time. If wh ≥ t − To for a FIN
message, decrement fm by 1 for,

k −1

i =0
k −1

i

(11)

i =0

i

(12)

Then, calculate flow count n from
b
b
,
(13)
n = b log
− b logb−cb− fand reset cB mod k and fB mod k to 0. On the right side ofeq.(13), the second term is the number of flows terminatedduring To.
With this method, an O(1) time process is added for the
TV update, while the flow count is executed in O(k) time.
Since k is much smaller than b, the method is much fasterthan the original algorithm of [5]. Thus, the computationaltime of the flow count process greatly decreases using the
proposed method. Additionally, the FIN message array iseffective for correctly judging the number of flows because it
is used to omit the flows terminated in To.
B. Calculation of Throughput per Flow
Let btotal denote the total bit rate, and let bavg denote theaverage throughput of a flow. Then,bavg = btotal / n(14)where n is the number of flows estimated by eq. (13).
IV. EVALUATION
We conducted three experiments to answer the following
questions (1) How fast does the proposed flow counting
algorithm process the incoming packets and compute theflow number? (2) How accurate is the proposed flow
counting algorithm for short-term flows? (3) How accurate is
the approach of this study for estimating the throughput of aflow?
Namely, the first and second experiments were performed
to observe the improvement due to the proposed flow
counting method, while the correctness of flow throughput
estimation is checked by the third experiment.
A. Computational Time of Flow Counting
The first experiment compares computational time for the
proposed algorithm and the timestamp-vector algorithm. The
experiment was executed on two Linux PCs, denoted by PC1
and PC2, connected by 1 Gb/s Ethernet. The flow counting
algorithms were executed on PC1 while UDP (User
Datagram Protocol) traffic was sent from PC2 to PC1 withvarying packet rates. The computational times of the TV
update and the flow count processes were measured by the
gprof tool. The algorithms were executed for 60 min foreach packet rate. In the proposed algorithm, parameters b, To,k, and M were set at 100003, 7, 7, and 1, respectively.

The result is shown in Fig. 2, which demonstrates that the
proposed method successfully decreases the computationaltime of the flow count process.
Method of [2]: TV Update

Method of [2]: Flow Count

Proposed Method: TV Update

Proposed Method: Flow Count

160

100

Actual Flows
Proposed Method
Number of Flows

Computational Time (sec)1000

number of flows. Additionally, the accuracy of the result is
not significantly changed for either algorithm with different
request rates. These results demonstrate that the use of TCP
FIN is effective to avoid overestimating flows.

101

Timestamp-Vector Algorithm

120

80

40

0.1
0
0

10

20

30
Time (sec)

0.01
100

1000

10000

Packet Rate (pkts/sec)

Fig. 2. Computational time for TV update and flow count processes.

For the proposed method, the computational time of theflow count process is less than 0.1 s, which is about 1/170 ofthat for the method of [5]. Meanwhile, the computationaltime of the TV update process is slightly larger for the
proposed method due to additional counter handling.
However, the total computational time is smaller for the
proposed method, particularly for low packet rates.
Additionally, it is not difficult to reduce the computationaltime of the TV update process by packet sampling [9]. Thus,
by using the proposed method together with packet sampling,
we can decrease the total computational time for high packet
rates as well as for high packet rate.
B. Accuracy of Flow Counting
The second experiment was performed to observe how
effectively the proposed method eliminates flow number
overestimation. In this experiment, httperf [10] wasinstalled on PC1 to generate short-lived TCP connections,and a WWW server was prepared on PC2. The client
program httperf is a tool for measuring web server
performance. In this experiment, TCP connections weremade to transfer web objects from the WWW server in
response to requests issued by httperf.
The algorithm was executed while limiting the output bit
rate to 10 Mb/s by a token bucket filter on PC2 to control the
duration of a TCP connection. To compare the accuracy of
the two methods, the true flow count value is necessary. For
this purpose, the netstat (network statistics) [11]command was used to record the number of flows for eachreport period. This command is a command-line tool that
displays active TCP connections as well as ports on which
the computer is listening.
Figure 3 compares the two algorithms when the HTTP
request rate is 9.9 (req/s), and Fig. 4 compares them when
the HTTP request rate is 3.5 (req/s). These figures show thatthe proposed algorithm more correctly estimates the actual
number of flows than the timestamp-vector algorithm. Also,
the timestamp-vector algorithm clearly overestimates the50

60

Fig. 3. Comparison of number of flows (HTTP request rate = 9.9 req/s).

We have the algorithm report of the estimated flow
number every second and compare the distance between thealgorithms’ estimate and the actual number of flows. Table I
shows the results for the two algorithms during 100 seconds
at different HTTP request rates. As shown in the table, theproposed method reduces the distance by 99%. This result
also confirms the effectiveness of the proposed algorithm.
100
Actual Flows
Proposed Method

Timestamp-Vector Algorithm

80
Number of Flows

10

40

60
40
20
0
0

20

40

60
Time (sec)

80

100

Fig. 4. Comparison of number of flows (HTTP request rate = 3.5 req/s).
TABLE I DISTANCE TO THE REAL NUMBER OF FLOWS.
HTTP request
rate (req/s)
9.9

3.5

Algorithm
Timestampvector based
ProposedmethodTimestampvector based
ProposedmethodActualFlows

Numberof Flows

Distance

5217

3475

1717

25

5211

3357

1820

34

1742

1854

C. Estimation of Throughput
This experiment examines the accuracy of flow
throughput estimation. To perform this, a program thatcomputes the throughput of a flow is implemented. The
program executes the bit rate estimation algorithm of RFC
2859 and the proposed flow counting algorithm every 1
second and reports the throughput of a flow, the total bit rate,
and the number of flows.

This experiment was executed on three Linux PCs,
denoted by PC1, PC2, and PC3 as shown in Fig. 5. The
program was executed on PC2, while TCP traffic wasgenerated by running a WWW server on PC1 and httperf on
PC3. In the experiment, the output bit rate of PC1 waslimited to 10 Mb/s by a token bucket filter to create asituation where congestion is likely to occur.
Throughput Monitoring

Throughput per Flow (kb/s

WWW Client(httperf)

200

WWW Server(Apache)HTTP GET

Output of httperf (kb/s)
Proposed Method(kb/s)

160
120
80
40
0
0

PC3
1000Base-TX

Page Data

PC2

PC1
1000Base-TX

The accuracy of estimation was examined as follows. The
httperf tool reported the average size of data sent fromthe WWW server to httperf for a connection. It also
outputs the average data transfer time. Thus, the ratio of theaverage data size and the average transfer time is the flow
throughput averaged over all the connections created byhttperf. Meanwhile, the outputs of the implemented
program are instantaneous values estimated for a short time
period and change over time. Thus, it is not sufficient tocompare these output values with the value averaged over allconnections.
Therefore, the experiment employs theweighted average of the flow throughput reported by the
program as an approximation of the average over all theconnections. The weighted average is defined as follows.
Let ni denote the flow count reported at time i. Similarly, letbtotal,i and bavg,i denote the total bit rate and the flow
throughput reported at time i, respectively. Also, let bw be
the weighted average of flow throughput. Then,

∑ nb
∑n
i

i avg ,i

i

i

=

∑b .
∑n
i

total ,i

i

4
6
8
10
Request Rate (reqs/sec)

12

14

Fig. 6. Throughput comparison of httperf output and proposed method.

Fig. 5. Configuration for throughput estimation.

bw =

2

(15)

i

Figure 6 compares throughput obtained from thehttperf output and the weighted average of the outputs
reported by the proposed method. It shows that the weighted
average throughput estimated by the proposed method is
almost equal to the average throughput obtained from thehttperf output. Additionally, the accuracy improves
when the request rate increases. This result suggests that the
proposed approach correctly detects throughput degradation
caused by congestion. These results imply that the flow
counting and bit rate estimation algorithms work correctly,
and the obtained throughput of a flow shows an exact
instantaneous value.

V. CONCLUSION
This study presented a method to estimate the throughput
of a flow by passive measurement. To achieve small
computational time, the study examined an approach thatuses the total bit rate and the flow count. For this approach,the existing flow counting algorithm has problems with longcomputational time and overestimation. Thus, the study
proposed a flow counting algorithm that improves thecomputational time and the accuracy. The improvement
achieved by the proposed flow counting algorithm wasconfirmed experimentally. Finally, a program that estimates
the throughput of a flow was implemented by combining the
bit rate estimation algorithm of RFC 2859 and the proposed
flow counting algorithm. The experimental result shows thatthe flow throughput reported by the program is correct.
REFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]

[8]

[9]
[10]
[11]

Sourceforge.net: iperf, http://sourceforge.net/projects/iperf/.
Netperf Homepage, http://www.netperf.org/netperf/NetperfPage.html.
For example, Cisco NetFlow, http://www.cisco.com/go/netflow.
W. Fang, N. Seddigh and B. Nandy, “A time sliding window three
colour marker (TSWTCM),” IETF RFC2859, June 2000.
H.-a. Kim and D.R. O’Hallaron, “Counting network flows in realtime,” in proc. GLOBECOM 2003, pp.3888-3893, San Francisco,Dec. 2003.
C. Estan, G. Varghese and M. Fisk, “Bitmap algorithms for counting
active flows on high-speed links,” IEEE/ACM Trans. on Networking,14, pp.925-937, 2006.
K. Keys, D. Moore and C. Estan, "A robust system for accurate realtime summaries of Internet traffic," in proc. Joint International
Conference on Measurement and Modeling of Computer Systems,
pp.85-96, Banff, Canada, June 2005.
K. Keys, D. Moore, R. Koga, E. Lagache, M. Tesch and k claffy,"The architecture of CoralReef: an Internet traffic monitoring
software suite," in proc. PAM 2001, Session 6, Amsterdam, Apr.
2001.
S. Zhu and S. Ohta, "Computational time improvement in flow
counting through packet sampling," in proc. JHES 2009, E-41,
Ishikawa, Sept. 2009.
D. Mosberger and T. Jin. O’Hallaron, “httperf: A Tool for Measuring
Web Server Performance,” ACM SIGMETRICS Performance
Evaluation Review, 26, 3, pp.31-37, Dec. 1998.
O. Kirch and T. Dawson, Linux network administrator's guide,
O'Reilly and Associates, 2000.