Identifying Elephant Flows Through
Periodically Sampled Packets
Tatsuya Mori

Masato Uchida

Ryoichi Kawahara

NTT Service Integration Labs
Waseda University
mori.tatsuya@lab.ntt.co.jp

NTT Service Integration Labs
uchida.masato@lab.ntt.co.jp

NTT Service Integration Labs
kawahara.ryoichi@lab.ntt.co.jp

Jianping Pan

Shigeki Goto

NTT MCLpanjianping@acm.org

Waseda University
goto@goto.info.waseda.ac.jp

ABSTRACT
Identifying elephant ﬂows is very important in developing
eﬀective and eﬃcient traﬃc engineering schemes. In addition, obtaining the statistics of these ﬂows is also very usefulfor network operation and management. On the other hand,with the rapid growth of link speed in recent years, packet
sampling has become a very attractive and scalable means
to measure ﬂow statistics; however, it also makes identifying elephant ﬂows become much more diﬃcult. Based on
Bayes’ theorem, this paper develops techniques and schemes
to identify elephant ﬂows in periodically sampled packets.
We show that our basic framework is very ﬂexible in making appropriate trade-oﬀs between false positives (misidentiﬁed ﬂows) and false negatives (missed elephant ﬂows) withregard to a given sampling frequency. We further validate
and evaluate our approach by using some publicly available
traces. Our schemes are generic and require no per-packet
processing; hence, they allow a very cost-eﬀective implementation for being deployed in large-scale high-speed networks.
Categories and Subject Descriptors: C.2.3 [ComputerCommunication Networks]: Network Operations—Network
monitoring
General Terms: Measurement, Theory, Veriﬁcation
Keywords: measurement, ﬂow statistics, packet sampling,
Bayes’ theorem, the elephant and mice phenomenon

1.

INTRODUCTION

As many measurement-based studies have revealed, ﬂow
statistics exhibit strong heavy-tail behaviors in various networks (including the Internet) [5, 8, 12, 15, 16]. This characteristic is often referred to as the elephant and mice phenomenon (a.k.a. the vital few and trivial many rule); i.e.,most ﬂows (mice ﬂows) only have a small number of pack-

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
IMC’04, October 25–27, 2004, Taormina, Sicily, Italy.
Copyright 2004 ACM 1-58113-821-0/04/0010 ...$5.00.

ets, while a very few ﬂows (elephant ﬂows) have a large
number of packets. A noticeable attribute of elephant ﬂows
is that they contribute a large portion of the total traﬃcvolume despite being relatively few in the number of ﬂows.
For example, for one trace used in this study, about 0.02%
of all ﬂows contributed more than 59.3% of the total traﬃcvolume.
Thus, the impact of elephant ﬂows on network performance is signiﬁcant. This fact makes identifying these ﬂows
very important in developing traﬃc engineering schemes.
In addition, knowing the statistics of such ﬂows is also very
useful for network operation and management. By quickly
identifying elephant ﬂows that are overwhelmingly consuming network resources, network operators can immediately
take appropriate actions against individual hosts or networks generating these ﬂows.
To identify elephant ﬂows, traditionally we have to collect
all packets in the concerned network, and then extract theirﬂow statistics. As many previous studies have indicated,
however, such an approach lacks of scalability [1–4, 7]. Forvery high-speed links (say, OC-192+), directly measuring all
ﬂows is beyond the capability of measurement equipments(i.e., the requirements for CPU power, memory/storage capacity and access speed are overwhelming). As a solution
to this problem, recently packet sampling techniques haveattracted much attention from both the industry and the research community. For instance, some modern routers havethese functions embedded, e.g., NetFlow [11] and sFlow [14].
The Packet Sampling (psamp) Working Group [13] in IETF
has been standardizing techniques related to packet sampling.
In this paper, we are particularly interested in the following problem: “How can we identify elephant flows in sampled packets?” When answering this question, we adopt thesimplest form of packet sampling; i.e., the sampling process
is completely ﬂow-state independent, and per-packet processing such as ﬂow lookup and packet hashing is totally
unnecessary. This form of packet sampling can be easily
achieved by using a very simple technique — periodic sampling. The purpose of adopting this approach is to reduce theimplementation cost and the operation overhead. For ISPs
operating large-scale networks with a variety of measurement equipments, a cost-eﬀective implementation is considered crucial in practice.
The main contribution of our work is developing a frame-

2.

RELATED WORK

The problem addressed in this paper has also been discussed by Estan and Varghese [4]. The main idea of theirapproach is to focus on elephant ﬂows and neglect numerous mice ﬂows, which is quite similar to ours. They proposed two novel techniques, referred to as sample-and-holdand multistage filters, respectively. Both techniques improve
the process of extracting statistics of elephant ﬂows in highspeed networks, while still keeping the memory consumption
reasonably low. The main diﬀerence of their approach fromours is its requirement for complex per-packet processing,which may increase its implementation cost and operation
overhead. On the other hand, the advantage of our approachis due to its simplicity; since it has no requirement for perpacket processing, the implementation cost of our schemes
will be much lower.
In another related work, Duﬃeld et al. [3] investigated
how to infer unsampled ﬂow statistics (instead of identifying elephant ﬂows) from sampled ﬂow statistics. Their key
idea is to use a scaling approach, which is based on the number of sampled SYN packets in TCP ﬂows. Kumar et al. [7]proposed a new technique referred to as space-code Bloom
ﬁlter (SCBF) for extracting per-ﬂow statistics of traﬃc inhigh-speed networks. The key points of their approach areextending the traditional Bloom ﬁlter with multiple sets ofhash functions and using multi-resolution sampling. Theirapproach can capture most ﬂow statistics very well, while
only requiring a small amount of memory resources. However, identifying elephant ﬂows through their approach requires the identities (e.g., source IP addresses) of potential
elephant ﬂows; i.e., it requires a priori knowledge of theelephant ﬂows ﬁrst. Papagiannaki et al. [12] proposed ascheme to classify elephant ﬂows based on both ﬂow volume
and time persistence. Their approach successfully isolates
1
In this paper, unsampled and sampled packets refer to thepacket trace before and after the packet sampling process.

0

10

-2

10

Pr[Xj = x]work to ﬁnd the threshold of sampled packets for a single
ﬂow, which can determine whether the ﬂow is an elephant
ﬂow in unsampled packets1 . We show that such a threshold can be calculated by using Bayes’ theorem. To do so,
we introduce an a priori distribution of the number of perﬂow packets (i.e., the distribution of the number of per-ﬂow
packets in unsampled packets). This approach is very ﬂexible in making appropriate trade-oﬀs between false positives(misidentiﬁed ﬂows) and false negatives (missed elephantﬂows) with regard to a given sampling frequency. Based on
our approach, we ﬁnd, somehow to our surprise, that thethresholds calculated for a variety of a priori distributions
are quite similar. This observation suggests that a calculated threshold for a network in a certain period can be applicable to the network and other networks for a long run,which also reduces the operation overhead of our schemes.
The remainder of the paper is organized as follows. Section 2 reviews some related work and compares with ourwork. Section 3 gives the deﬁnition of elephant ﬂows. In
Section 4, we describe how to identify elephant ﬂows in periodically sampled packets. We also validate and evaluate
our approach by using some public packet traces. Section 5
discusses the way of obtaining such an a priori distribution.
The eﬀectiveness of our approach in other networks is also
discussed. In Section 6, we conclude this paper with a briefsummary.

-4

10

-6

10

0

10

1

10

2

10

3

x

10

4

10

5

10

Figure 1: Probability density of Xj for the IPCL
trace.
elephant ﬂows that exhibit considerable persistence in time
domain. Since their scheme assumes the direct measurement of all ﬂows, some extensions will be required to obtain
per-ﬂow statistics in very high-speed networks. Golab etal. [6] proposed a deterministic algorithm to identify frequent items (similar to elephant ﬂows in our context) using
a memory-limited sliding window model. Although the algorithm can fulﬁll its objective with limited memory resources,
it still requires per-packet processing, which we want to completely avoid in our context.

3. DEFINITION OF ELEPHANT FLOWS
A qualitative characterization of elephant ﬂows is thatthey represent the majority of total traﬃc volume (in thenumber of packets or bytes) while being relatively few inthe number of ﬂows. The quantitative deﬁnition of an elephant ﬂow can be arbitrarily determined by network operators according to their own criteria. In this paper, we deﬁneelephant ﬂow as a ﬂow that contributes more than 0.1% of
all unsampled packets.
For illustration purpose, here we use a packet trace of Internet traﬃc measured at an OC-48c backbone link by the
PMA project of NLANR2 . In this trace, we considered theﬁrst 107 packets, referred to as the unsampled IPCL traceor simply trace when the context is clear, which correspondto about 137 seconds of observed traﬃc. The choice of 107
packets is considered reasonable for calculation convenience;
the number of packets still allows us to obtain suﬃcient data
for statistical analysis. Moreover, since the trace lasts about
137 seconds (with an average throughput of about 1 Gbps),
the identiﬁed elephant ﬂows within this time window cangive meaningful information for the purpose of traﬃc engineering and network operation3 . Throughout this paper, wedeﬁne a ﬂow by the 5-tuple identity (i.e., source/destination
IP addresses, source/destination port numbers, and protocol identiﬁer). Since the session time of some elephant ﬂows
can be very long (say, more than 3 hours), we include all partial ﬂows in the time window (e.g., TCP ﬂows with missing
SYN or FIN packets) for analysis purpose. Our objective
2
More precisely, we use the trace IPLS-CLEV-20020814090000-0 [9].
3
We conﬁrmed that in many cases, elephant ﬂows did exceed
this time window; i.e., an identiﬁed elephant ﬂow within theﬁrst time window will be recognized as an elephant ﬂow
again in the following time windows with high probability.
That result is omitted due to space limit.

f=0.001

1

FPR(y’), FNR(y’)

is to identify elephant ﬂows by using packets sampled fromthe unsampled trace as quick and accurate as possible.
Figure 1 shows the probability density Pr [Xj = i] (i =1, 2, ...) of the IPCL trace, where Xj is the number of packets of the j-th ﬂow. The probability density of Xj clearly
decays in an approximate power-law fashion. As many previous measurement-based studies [5, 8, 12, 15, 16] have revealed, this characteristic seems to be intrinsic to Internet
traﬃc. The IPCL trace contains 737, 780 ﬂows in the observed time window. Since an elephant ﬂow by our deﬁnition is the one that contributes more than 0.1% of the total
107 packets, any ﬂow j for which Xj ≥ 104 is considered
as an elephant ﬂow in this paper. Under this deﬁnition, we
have 167 elephant ﬂows in the unsampled IPCL trace; theseﬂows account for more than 59.3% of the total traﬃc volume(in the number of bytes).

FPR(y’)FNR(y’)

0.8

0.6

0.4

0.4

0.2

0.2

5

10

y’

15

FPR(y’)FNR(y’)

0.8

0.6

0
0

f=0.0001

1

20

0
0

2

4

y’

6

8

10

Figure 2: Trade-oﬀ between FPR(y  ) and FNR(y  )for the IPCL trace.

In this section, we propose an approach to identify elephant ﬂows by counting the number of sampled packets forindividual ﬂows. Our task is to ﬁnd a threshold determining
whether a sampled ﬂow represents an elephant ﬂow in unsampled packets. Our approach is based on Bayes’ theorem.
Here, we assume that an a priori distribution Pr [Xj = i] is
known in advance. How to obtain such a Pr [Xj = i] will be
discussed in the next section. We ﬁrst describe a frameworkfor our approach. Then, we discuss the trade-oﬀ between
false positives and false negatives with regard to a given
sampling frequency. Based on these results, we give a procedure of identifying elephant ﬂows in sampled packets. Finally, we present numerical results to validate and evaluate
our approach.

Equation (2) means: given a priori distribution Pr [Xj = i],we can use y, the number of sampled packets for a ﬂow,
to calculate the probability with which the ﬂow has morethan x packets in the population. Let a ﬂow j be an elephant ﬂow if the number of unsampled packets Xj ≥ x̂;i.e., x̂ is the threshold identifying an elephant ﬂow (e.g.,x̂ = 104 for the example in the previous section). Then, if
Pr [Xj ≥ x̂|Yj ≥ ŷ] is close enough to 1 for a given y = ŷ, theﬂow j is very likely to have more than x̂ packets in the population. In other words, if the number of sampled packets
Yj for a ﬂow j is greater than ŷ, there is a high probability
that the ﬂow represented by the sampled packets is indeed
an elephant ﬂow in unsampled packets.
Intuitively, Pr [Xj ≥ x̂|Yj ≥ ŷ] will increase with ŷ. However, there is an intrinsic trade-oﬀ between false positives
and false negatives, which prevents us from choosing an arbitrary ŷ. Our framework allows us to quantify this trade-oﬀ
and make proper choices, as we shall see shortly.

4.1 A framework for our approach

4.2 Trade-off between false probabilities

Let n packets be randomly sampled from a population of
N packets4 . The sampling frequency f is deﬁned as f =n/N . Let Yj be the number of sampled packets for a ﬂow
j, which has Xj packets in the population (i.e., unsampled
packets). Given Xj = x, the probability with which Yj
satisﬁes Yj = y is
 
 
x
N −x
N
Pr [Yj = y|Xj = x] =
,
(1)
y
n−y
n

If we assume that a ﬂow for which Yj satisﬁes Yj ≥ y 
is an elephant ﬂow, then the false positive ratio (FPR) andthe false negative rate (FNR) can be deﬁned as follows.

4.

IDENTIFYING ELEPHANT FLOWS

which is a hyper-geometric distribution5 .
According to Bayes’ theorem, given Yj ≥ y, the probability with which Xj satisﬁes Xj ≥ x can be calculated asfollows.
Pr [Xj ≥ x|Yj ≥ y]

Pr [Yj ≥ y|Xj = k] Pr [Xj = k]= k=x,(2)
Pr[Yj ≥ y|Xj = k] Pr [Xj = k]k=1
y−1
Pr [Yj = i|Xj = x],where Pr [Yj ≥ y|Xj = x] = 1 − i=0
and Pr [Xj = i] is the probability density of Xj shown in
Fig. 1.
4
Precisely speaking, periodic sampling, which will be
adopted in our scheme, is diﬀerent from random sampling.
However, since there is a large number of concurrent ﬂows
coexisting in a high-speed link, successive packets of a given
ﬂow will be interleaved by packets of many other ﬂows,
which eﬀectively randomizes the selection of packets of thegiven ﬂow [3].
5
To calculate (1), we use its binomial approximation.

FPR(y  ) = Pr [detected ﬂows are not elephant ﬂows]
(3)= 1 − Pr Xj ≥ x̂|Yj ≥ y 
def

FNR(y  ) = Pr [elephant ﬂows are not detected]= 1 − Pr Yj ≥ y  |Xj ≥ x̂
Pr [Yj ≥ y  |Xj = k] Pr [Xj = k](4)
= 1 − k=x̂
k=x̂ Pr [Xj = k]def

These equations can be calculated by using (2). Ideally,
we should ﬁnd y  = ŷ such that both FPR(ŷ) and FNR(ŷ)
are minimized. However, as shown below, there is a trade-oﬀ
between the two metrics. The trade-oﬀ becomes particularly
critical when the sampling frequency f is very low. Again,
we illustrate this trade-oﬀ by using the IPCL trace.
Figure 2 shows FPR(y  ) and FNR(y  ) (y  = 1, 2, ...) calculated by using (3) and (4). Here, the number of unsampled
packets is N = 107 , and the threshold to identify an elephant ﬂow is x̂ = 104 . Sampling frequency f is 10−3 and10−4 , respectively. For Pr [Xj = i], we used the one fromthe IPCL trace, i.e., the distribution shown in Fig. 1. In
both cases, an increase in y  leads to a decrease in FPR(y  )and an increase in FNR(y  ); i.e., there is an unavoidable
trade-oﬀ between the two metrics. We can also see that thetrade-oﬀ is more critical at the lower sampling frequency(i.e., f = 10−4 ).

Table 1: ŷ, FPR(ŷ), and FNR(ŷ) for the IPCL trace
by calculationfŷ FPR(ŷ) FNR(ŷ)
−3
10
13
0.045
0.250
4
0.030
0.774
10−4

Table 2: FPR and FNR through packet sampling of
the IPCL tracefnˆene
FPR FNR10−3 134 127 0.053 0.240
10−4
38
38 0.000 0.772

4.3 Flow identification procedure

population, (ii) a sampling frequency f , (iii) a thresholdx̂ determining an elephant ﬂow in unsampled packets, (iv)an a priori distribution of Xj of unsampled packets (i.e.,
Pr [Xj = i]), and (v) a threshold  that FPR should satisfy.
Step 2: Calculate ŷ by using the above (i) – (v) and (5).
Step 3: Conduct periodic packet sampling, and meanwhile count the number of per-ﬂow packets.
Step 4: If the number of sampled packets for a ﬂow isgreater than ŷ, the ﬂow is identiﬁed as an elephant ﬂow.

According to the result shown in the previous subsection,
we have to make appropriate trade-oﬀs between false positives and false negatives when identifying elephant ﬂows.
This subsection presents such a ﬂow identiﬁcation procedure
designed with these observations kept in mind.
We consider the following policy as a guideline, i.e., thefalse positive ratio should be reasonably low while reducing
the false negative rate for a given sampling frequency. According to this policy, we should keep the false positive ratio
low enough without sacriﬁcing the false negative rate toomuch, which is the consequence of the trade-oﬀ. Nevertheless, identifying elephant ﬂows with a suﬃciently low false
positive ratio still provides very useful information for trafﬁc engineering and network operation. First, we can avoid
mistreating non-elephant ﬂows (e.g., shaping their packetrate) when the false positive ratio is suﬃciently low. Second, although keeping a low false positive ratio may cause
a higher false negative rate, the amount of traﬃc generated
by the identiﬁed ﬂows is already signiﬁcant. For example, in
the IPCL trace, the 10 heaviest elephant ﬂows account for
about 10% of the total traﬃc volume.
According to the policy, our goal is to ﬁnd y  = ŷ suchthat FPR(ŷ) becomes reasonably low. However, merely increasing ŷ will lead to an increase in FNR(ŷ), due to therevealed trade-oﬀ. So, we obtain the threshold ŷ with thefollowing constraint

 
(5)
ŷ = miny | FPR(y  ) ≤  ,ywhere  speciﬁes a tolerable false positive ratio. Equation(5) guarantees an FPR is lower than  (say, 0.05), while
keeping the corresponding FNR as low as possible.
Table 1 lists ŷ, FPR(ŷ), and FNR(ŷ) as calculated byfollowing (5) for the examples shown in Fig. 2. Here, wehave  = 0.05. When f = 10−3 , if ŷ, the number of sampled
packets for a ﬂow, is greater than 13, the ﬂow is very likely
to be an elephant ﬂow, since FPR(ŷ) ≤  = 0.05. Due tothe fact that FNR(ŷ) ≈ 0.25, about 25% of elephant ﬂows
in unsampled packets will be missed on average.
When f = 10−4 , FNR(ŷ) becomes much higher if ŷ = 4;
i.e., more elephant ﬂows in unsampled packets will be missed
due to an ultra-low sampling frequency and a bounded false
positive ratio. However, the identiﬁed elephant ﬂows are
more likely to be elephant ﬂows, which is also meaningful
for traﬃc engineering and network operation. The result
also suggests that for such a low f , it is advisable to allow ahigher tolerable FPR, or to have a higher f when aﬀordable,
if false negatives have greater impact on network operation
than false positives. Since the number of elephant ﬂows
in the IPCL trace is 167, we can expect that on average
about 38 (i.e., 167 × (1 − 0.774)) heavy elephant ﬂows willbe identiﬁed according to our approach.
In a summary, the procedure for identifying elephant ﬂows
in sampled packets is enumerated as follows.
Step 1: Determine (i) the number of packets N in the

4.4 Performance evaluation
In this subsection, we evaluate our approach through anactual packet sampling process for the IPCL trace. Following the procedure described in the previous subsection,
we ﬁrst determine the following parameters (ref. Step 1):
N = 107 , f ∈ {10−3 , 10−4 }, and x̂ = 104 . We again use the
distribution of the IPCL trace shown in Fig. 1 as the a priori
distribution of Xj . Second, we use the calculated ŷ listed
in Table 1 (Step 2). We then conduct the actual packet
sampling for the IPCL trace and count the number of perﬂow packets (Step 3). We use periodic sampling, which isthe simplest form to implement; i.e., we periodically sample
every (N/n)-th packet. Finally, we investigate the ﬂows forwhich the sampled packets satisfy Yj ≥ ŷ (Step 4). The
number of identiﬁed elephant ﬂows in sampled packets isdenoted as n̂e . Among these n̂e ﬂows, there are ne actual
elephant ﬂows by our deﬁnition. We use Ne to denote thenumber of total elephant ﬂows in unsampled packets (recall
that Ne = 167 for the IPCL trace, as stated in Section 4).
Here, the false positive ratio FPR and false negative rate
FNR can be approximated by FPR = 1 − ne /n̂e , FNR =1 − ne /Ne .
FPR and FNR through packet sampling of the IPCL trace
are listed in Table 2. As we can see, they are in good agreement with those listed in Table 1, which were calculated
from (3) and (4), respectively. This result conﬁrms that ourapproach can eﬀectively identify elephant ﬂows in sampled
packets. With a periodic sampling, such an approach is also
very eﬃcient.

5. A PRIORI DISTRIBUTION OF Xj
Identifying elephant ﬂows accurately requires an appropriately chosen ŷ. We have shown that such a ŷ can beobtained by following (5). To do so, we need know N , f ,and x̂, and Pr [Xj = i]; i.e., we have to obtain the distribution of Xj in unsampled packets. There are three possible
approaches: A) use the distribution measured previously at
the same link; B) infer the unsampled ﬂow statistics (e.g.,
per-ﬂow packet distribution) from sampled ﬂow statistics;C) utilize the power-law characteristic of Internet traﬃc.
Approach A assumes that the distribution is similar if
measured at the same link in similar periods (say, in daily
busy hours). However, this approach lacks scalability, since
it requires the direct measurement of ﬂow characteristics.
Approach B uses the result given by Duﬃeld et al. [3]; i.e.,with the estimated number of original ﬂows, the unsam-

Table 3: ŷ for the three traces by calculationtraceŷ (f = 10−3 ) ŷ (f = 10−4 )
IPCL
13
4
14
4
IPKS
CESCA
15
5

0

10

-1

IPCL
IPKS
CESCA

10

-2

Pr[Xj > k]

10

-3

10

0

10
-4

10

-5

-2

10

10

0

1

10

2

10

3

10

4

10

5

10

10

Pr[Xj > k]

-6

10

6

10

k

1

1

0.8

0.8
FNR(y’)FPR(y’)

Figure 3: Complementary cumulative distributionsof Xj for the three traces.

0.6
0.4
0.2
0

10
y’

5

15

1

1

0.8

0.8

0.6
0.4
0.2
0

0

10
y’

5

15

2

4

6
y’

8

10

IPCL
IPKS
CESCA

-6

10

β = 1.25
β = 1.5

-8

10

0

10

1

10

2

3

10

10

4

10

5

10

k

20

0.6
0.4
0.2

0

β = 1.0

Figure 5: Complementary cumulative distributionsof Xj for the Pareto distributions.

0.4

0

20

β = 0.75

-4

10

0.6

0.2

FNR(y’)FPR(y’)

0

IPCL
IPKS
CESCA

β = 0.5

0

0

2

4

6

8

10

y’

Figure 4: FPR(y  ) and FNR(y  ) for the three traces:f = 10−3 (top) and f = 10−4 (bottom).
pled per-ﬂow packet distribution Pr [Xj = i] can be inferredfrom the observation of sampled per-ﬂow packet distribution Pr [Yj = i]. Approach C utilizes the observation thatthe distribution of the number of per-ﬂow packets for Internet traﬃc seems to decay in an approximately power-law
fashion.
In the following, we focus on Approach C. We investigate
how Pr [Xj = i] aﬀects ŷ. First, we look into several empirical distributions obtained from packet traces measured in
diﬀerent networks. We then augment our investigation withthe case of a family of theoretical Pareto distributions. We
ﬁnd, somehow to our surprise, that the calculated thresholds ŷ are similar for these empirical and theoretical distributions. This result suggests that a threshold obtained for
one network can be used as an approximation for other networks as long as their ﬂow statistics also exhibit heavy-tailcharacteristics.

lis and Kansas City [9]. We refer to this trace as the IPKS
trace6 . The second one was measured at a Gigabit Ethernet
link connecting the Anella Cientiﬁca to the global Internet
via RedIRIS [10]. We refer to this trace as CESCA7 . Eachlink had an adequate volume of traﬃc during the measurement period.
Figure 3 shows complementary
cumulative distributions
Pr [Xj > k] = 1 − ki=1 Pr [Xj = i] for these three traces.
Although their distributions are diﬀerent, they all exhibit
heavy-tail behaviors and decay in an approximately powerlaw fashion. Then, we use the distribution Pr [Xj = i] foreach trace to calculate FPR(y  ) and FNR(y  ) (see Fig. 4),
with N = 107 , f ∈ {10−3 , 10−4 }, and x̂ = 104 ; four subﬁgures show similar tendencies of FPR(y  ) and FNR(y  ) for
all these three traces. Next, we use (5) to calculate ŷ, with
 = 0.05. Table 3 lists the calculated thresholds of identifying elephant ﬂows in sampled packets. As we can see, thesethresholds (ŷ) are very similar for traces with diﬀerent perﬂow packet distributions.

5.2 Theoretical distributions

5.1 Empirical distributions

We use the Pareto distribution as a theoretical distribution, since it is appropriate for evaluating behaviors forwhich the complementary cumulative distribution decays ina power-law fashion. This distribution is often referred to as
the basis of the elephant and mice phenomenon. The Pareto
distribution is deﬁned by Pr [Xj ≤ x] = 1 − (α/x)β (x ≥ α),
where α > 0 is a location parameter, and β > 0 is a shapeparameter. With the above notation, the probability density
function is deﬁned as Pr [Xj = x] = βαβ /xβ+1 . Figure 5 illustrates the complementary cumulative distribution of thePareto distributions (α ≤ x ≤ 105 ). Here, α = 1.0, andβ ∈ {0.5, 0.75, 1.0, 1.25, 1.5}. The empirical distributions

To supplement the IPCL trace, we used two more unidirectional packet traces of Internet traﬃc. The ﬁrst one wasmeasured at the same location as the IPCL trace, but atother OC-48c backbone links, i.e., those between Indianapo-

6
We use the ﬁrst 107 packets (corresponding to about 124
seconds) in the trace IPLS-KSCY-20020814-105000-1 [9].
7
We use the ﬁrst 107 packets (corresponding to about 85
seconds) in the trace 20040219-120000-a [10].

1

1
0.8
FNR(y’)FPR(y’)

0.8
0.6
0.4
0.2
0

0

5

10
y’

15

0.4

0

20

0

5

10
y’

15

20

1
0.8
FNR(y’)

0.8
FPR(y’)

0.6

0.2

1

0.6
0.4
0.2
0

β = 0.5
β = 0.75
β = 1.0
β = 1.25
β = 1.5

0.6
0.4
0.2

0

5
y’

10

0

0

5
y’

10

Figure 6: FPR(y  ) and FNR(y  ) for the Pareto distributions: f = 10−3 (top) and f = 10−4 (bottom).
Table 4: ŷ for the Pareto distributions by calculationβŷ (f = 10−3 ) ŷ (f = 10−4 )
0.5
13
4
0.75
13
4
1.0
14
4
1.25
14
4
1.5
15
5
are also plotted for comparison purpose.
For each of the above Pareto distributions, we calculate
FPR and FNR by using (3) and (4) (see Fig. 6), and ŷ byusing (5) (see Table 4). Here, N = 107 , f ∈ {10−3 , 10−4 },x̂ = 104 , and  = 0.05. Both FPR(y  ) and FNR(y  ) show
very similar tendencies for all distributions. The calculated
thresholds (ŷ) are similar for the Pareto distributions overa relatively wide range of β, and are similar to those for theempirical distributions.
As shown in Fig. 5, the empirical distributions of Xj forthe three traces roughly follow Pr [Xj > x] ∼ x−β , whereβ is close to 1. Other measurement-based studies have reported that ﬂow statistics exhibit such characteristics [5, 8,
12, 15, 16] in many diﬀerent networks (including the Internet). Therefore, we may conclude that the value of ŷ calculated by using the Pareto distribution (say, with β = 1.0)
can be used as approximations for a wide range of other networks as long as their per-ﬂow packet statistics also follow
heavy-tail distributions.

6.

CONCLUSION

In this paper, we have described how to identify elephantﬂows through counting periodically sampled packets. The
key is to ﬁnd the threshold of per-ﬂow packets in sampled
packets which can reliably indicate whether or not a ﬂow
is actually an elephant ﬂow in unsampled packets. We haveshown that such a threshold can be obtained based on Bayes’
theorem, with a proper trade-oﬀ of false positives and false
negatives. Moreover, we have found that for various a priori distributions, the calculated thresholds are quite similar. This observation suggests that a threshold obtained for
one network will be applicable to other networks exhibiting

similar per-ﬂow packet distributions. Although our current
scheme only focus on identifying elephant ﬂows instead ofexacting detailed ﬂow statistics, we believe that identifying
elephant ﬂows is an important step toward the goal of thelatter during network operation and traﬃc engineering.
The advantage of our approach is due to its simplicity. Periodic sampling and stateless ﬂow identiﬁcation without perpacket processing can be easily implemented in any contemporary high-end PC, which is of course a very cost-eﬀective
solution. In addition, our analytical framework quantiﬁes
the intrinsic trade-oﬀ in ﬂow identiﬁcation and can provide
insights on how to choose appropriate parameters. For ISPs
operating large-scale networks with a variety of measurement equipments, these features are considered very crucial
in practice.

Acknowledgments
The authors would like to acknowledge the people of the
PMA project for making their packet traces publicly available to the networking research community. We also wish
to thank anonymous reviewers, who have provided valuablecomments on an early version of this paper.

7. REFERENCES[1] N. Duﬃeld, C. Lund, and M. Thorup, “Charging from
Sampled Network Usage,” ACM SIGCOMM Internet
Measurement Workshop, California, November, 2001.
[2] N. Duﬃeld, C. Lund, and M. Thorup, “Properties andPrediction of Flow Statistics from Sampled Packet Streams,”
ACM SIGCOMM Internet Measurement Workshop, Marseille,
France, November, 2002.
[3] N. Duﬃeld, C. Lund, and M. Thorup, “Estimating FlowDistributions from Sampled Flow Statistics,” In Proceedings of
ACM SIGCOMM, pp. 325–336, August 2003.
[4] C. Estan and G. Varghese, “New Directions in Traﬃc
Measurement and Accounting,” In Proceedings of ACM
SIGCOMM, pp. 323–336, August 2002.
[5] S. Ben Fredj, T. Bonald, A. Proutiere, G. Regnie, andJ. Roberts, “Statistical bandwidth sharing: a study ofcongestion at ﬂow level,” In Proceedings of ACM SIGCOMM,
pp. 111–122, August 2001.
[6] L. Golab, D. DeHaan, E. Demaine, and A. Lopez-Ortiz,“Identifying Frequent Items in Sliding Windows over On-Line
Packet Streams,” ACM SIGCOMM Internet Measurement
Conference, Florida, October, 2003.
[7] A. Kumar, J. Xu, J. Wang, O. Spatschek, and L. Li,“Space-Code Bloom Filter for Eﬃcient Per-Flow Traﬃc
Measurement,” In proceedings of IEEE INFOCOM, Hong
Kong, China, March 2004.
[8] T. Mori, R. Kawahara, S. Naito, and S. Goto, “On thecharacteristics of Internet Traﬃc variability: Spikes andElephants,” In Proceedings of IEEE/IPSJ SAINT, pp. 99–106,
Tokyo, Japan, Jan 2004
[9] NLANR: Abilene-I data set,
http://pma.nlanr.net/Traces/long/ipls1.html[10] NLANR: CESCA-I data set,
http://pma.nlanr.net/Special/cesc1.html[11] Cisco NetFlow,
http://www.cisco.com/warp/public/732/netﬂow/index.html[12] K. Papagiannaki, N. Taft, S. Bhattacharya, P. Thiran,
K. Salamatian, and C. Diot, “On the feasibility of identifying
elephants in internet backbone traﬃc. Sprint ATL Technical
Report TR01-ATL-110918,” Sprint Labs, November 2001.
[13] IETF Packet Sampling (psamp) Working Group,
http://www.ietf.org/html.charters/psamp-charter.html[14] InMon sFlow Probe,
http://www.inmon.com/products/probes.php[15] K. Thompson, G. J. Miller, and R. Wilder, “Wide-areainternet traﬃc patterns and characteristics,” IEEE Network,
vol. 11, no. 6, pp. 10–23, November/December 1997.
[16] Y. Zhang, L. Breslau, V. Paxson, and S. Shenker, “On the
Characteristics and Origins of Internet Flow Rates,” In
Proceedings of ACM SIGCOMM, pp. 309–322, August 2002.