Inferring original traﬃc pattern from sampled flow statistics
Tatsuya Mori Ryoich Kawahara Noriaki Kamiyama Shigeaki Harada
NTT Service Integration Laboratories, NTT Corporation
3-9-11 Midoricho Musashino-shi Tokyo, Japantatsuya@nttlabs.com, {kawahara.ryoichi, noriaki.kamiyama, harada.shigeaki}@lab.ntt.co.jp
Abstract
Packet sampling has become a practical and indispensable means to measure flow statistics. Recent studies havedemonstrated that analyzing traﬃc patterns is crucial in
detecting network anomalies. We may not be able to infer the original traﬃc patterns correctly from the sampledflow statistics because sampling process wipes out a lot of
information about small flows, which play a vital role indetermining the characteristics of traﬃc patterns. In thispaper, we first show an example of how the sampling process wipes out the original statistics using measured data.
Then, we show empirical examples indicating that the original traﬃc pattern cannot be inferred correctly even if we use
a statistical inference method for incomplete data, i.e., theEM algorithm, for sampled flow statistics. Finally, we showthat additional information about the original flow statistics, the number of unsampled flows, is helpful in tracking
the change in original traﬃc patterns using sampled flow
statistics.

1. Introduction
With the recent growth in link speed, packet sampling
has attracted much attention as a scalable means to measure
network traﬃc from both industrial and research communities [1, 6]. The technique has been standardized in the IETF
psamp working group [2], and most major vendors have embedded packet sampling functions into their router products.
Most large ISPs, which are operating high-bandwidth links
such as OC192, are monitoring their network using packet
sampling techniques.
Many recent studies have demonstrated that analyzing
traﬃc patterns is crucial in detecting network anomalies[4, 7]. For example, a sharp increase in the number ofsmall flows, e.g., those with 1 – 3 packets, may be related
to an anomalous event such as SYN flooding or a worm
outbreak. Such events cannot be characterized by conventional volume-based statistics such as byte or packet counts.
Lakhina et al. [4] showed that the change in traﬃc pattern can be successfully characterized by information entropy, which can eﬀectively express the concentration ordispersion of the distributions of observed random vari-ables. However, we may not able to infer the original traﬃcpatterns correctly from the sampled flow statistics because
the sampling process wipes out a lot of information about
small flows, which play a vital role in determining the characteristics of traﬃc patterns (see [3] for a detailed analysis).
Therefore, studying how the sampling aﬀects the observed
traﬃc patterns is meaningful.
In this paper, first, we demonstrate that packet samplingwith a low sampling frequency, e.g, f = 10−3 , which is acommonly used parameter setting in backbone links, causes
the change in traﬃc patterns to be undetected. Then, weshow experimental examples in which even if we use thestatistical inference technique for the incomplete data, i.e.,the EM algorithm, the original traﬃc pattern cannot be reconstructed correctly. Finally, we show that the maximum
likelihood estimation with additional information about theoriginal flow statistics, the number of unsampled flows, iseﬀective in tracking the change in original traﬃc patterns.

2. Traﬃc pattern and packet samplingThis section shows how packet sampling aﬀects observed traﬃc patterns. Throughout this paper, we use thepublicly available packet traces obtained from [5]. The
traces used in this paper were measured on one of the International backbone links of the WIDE project January 7,
2005 from 19:00 to 23:00. The measurement bin was set to
5 minutes. Several time series of original and sampledflow
statistics with the sampling frequencies of f ∈ 10−2 , 10−3
are shown in Fig. 1. Here, we emulated random packet sampling. We focus on (1) the number of observed (sampled)
flows, (2) the ratio of one-packet flows (OPF ratio), and (3)entropy when analyzing flow statistics. Here, the OPF ratio is the ratio of the number of flows that comprise exactly
one packet divided by the total
 number of flows, and the entropy s is defined as s = − i p(i) log p(i), where p(i) is theprobability that a flow has i packets.
In the original flow statistics, we see that the numberof flows has a sharp spike around 21:20. Through the detailed analysis of measured data, we found that the spike is
due to a severe SYN flooding attack against several destination addresses from a number of possibly spoofed source
addresses. We can also see that the increase/decrease in#(sampled) flows
1.0

OPF ratio

entropy

0.9

2

2.0

6e+05

1.8

0.8

1.5

2e+05

0.6

1.0

0
15000

0.4
1.0

0.5

10000

0.9

1.0

5000

0.8

0.8

0
2000

0.7
1.0

0.6
0.8

original 4e+05

f=1/100

0.8

OPF ratio

1.6

entropy

0.7

0.6

1.2

1.4
1.2
1

0.5
0.8

1500

0.4
1e+05 2e+05 3e+05 4e+05 5e+05 6e+05

0.6
0.4

#flows

0.5

0.6

0.7

0.8

0.9

OPF ratio

0.7

f=1/1000 1000

0.9
0.6

500

0
0.8
0.5
19:00 20:00 21:00 22:00 23:00 19:00 20:00 21:00 22:00 23:00 19:00 20:00 21:00 22:00 23:00

Time

Time

Figure 2. Correlation among original flow
statistics.

Time

Figure 1. Time series of original and sampledflow statistics.

0

10

-2

CCD

10

-4

10

the OPF ratio roughly corresponds to the decrease/increasein entropy, which means that the concentration of the OPF
decreases the entropy. As shown in Fig. 2, the number offlows and OPF ratio are not well correlated while OPF ratio
and entropy are fairly well correlated negatively. Actually,
the correlation coeﬃcient between the number of flows and
OPF ratio is 0.795 while that between the OPF ratio andentropy is -0.958. Thus, entropy can eﬀectively reflect thechange in flow mix, i.e., increase in OPF ratio in this case,while the number of flows cannot always correctly reflect
the change in the flow mix. The increase in OPF is related tosome anomalous events such as SYN flooding, so network
scanning and port scanning, using entropy as a measure ofa traﬃc pattern are quite useful.
On the other hand, as the sampling frequency decreases,
we see that the changes in these statistics become totally undetectable because most OPFs are not sampled. This observation empirically suggests that detecting network anomalies from sampled flow statistics is a diﬃcult task. In thenext section, we describe how to infer original flow statistics from the sampled flow statistics.

3. Inferring original flow length distribution
3.1

Modeling flow length distributions

The flow length distribution in the Internet is well known
to be heavy-tailed, which is considered as one of the invariant characteristics of the Internet [6]. Here, flow lengthmeans the number of packets in a flow. The Pareto distribution is known to be the simplest model for characterizing heavy-tailed distributions. Thus, we adopt the Pareto
distribution for modeling flow-length distributions. Adopting more complex distribution models or nonparametric approaches is also possible [1]. However, as we shall see
below, the modeling of flow-length distributions with thePareto distribution is quite eﬀective in characterizing traﬃcpatterns in terms of entropy.
The probability density function of the Pareto distribution is given by f (x) = θaθ /xθ+1 , where x ≥ a. We model

-6

10

1

10

100

1000

10000 1e+05

Flow length

Figure 3. Flow length distribution approximated using Pareto distribution.

the flow length X with the Pareto distribution. The randomvariable X takes positive discrete values 1, 2, 3, . . ., so we
set the scale parameter to a = 1 and discretize the distribution with the following probability mass function p(k; θ).
 k+1
f (x)dx = k−θ − (k + 1)−θ (1)p(k; θ) = Pr[X = k] =kThe ML estimation of parameter θ can be obtained by numerically solving the following log-likelihood equation,
xmax

k=1

Nk

−k−θ log k + (k + 1)−θ log(k + 1)
= 0,
k−θ − (k + 1)−θwhere Nk is the number of flows that comprise k packets inthe original flows and xmax is the maximum flow length inthe original flows.
The log-log complementary distribution (LLCD) plots ofthe empirical distribution of the original flow lengths and its
Pareto approximation (dashed line) for one of the traces areshown in Fig. 3. We observe that the Pareto model fits theempirical distribution fairly well especially in the range ofsmall flow lengths. The comparison between the actual entropy and the estimated entropy obtained with the Pareto approximation for all the traces is shown in Fig. 4. We can seethat the actual entropy and the estimated entropy agree quite
well; the correlation coeﬃcient was 0.999. This comes fromthe fact that entropy is strongly aﬀected by the flow lengths
with high probabilities, i.e., small flow lengths, which are
well approximated by the Pareto distribution.

2

CC = 0.734

1.2

f=1/100

1.2

0.9

1.4

1

1.2

1.4

1.6

true entropy

1.8

2.5

r(i; θ)ni =1.0
1.0 1.2 1.4 1.6 1.8 2.0

original θ

2.0

CC = 0.499
1.1

ymax


ni log r(i; θ).

CC = 0.961

1.4
1.2

1.0

1.5

2.0

original θ

2.5

1.0
1.0 1.2 1.4 1.6 1.8 2.0

original θ

Figure 5. Original θ vs. estimated θ using EM
algorithm.

(2)

i=0

E-step: Let θ(0) be the initially specified value forθ.
The conditional expectation of log Lc (θ) given
n1 , . . . , nymax using θ(0) can be written as Q(θ; θ(0) ) =Eθ(0) log Lc (θ) | n1 , . . . , nm . We have log Lc (θ) as a linear
function of the unobservable data n0 , so the E-step is established by replacing n0 with its current conditional expectations given the observed data. Let the conditional expecta(0)tions of n0 be n(0)0 . We estimate n0 using the odds ratio,
i.e.,
ymax
r(0; θ(0) ) ni .
1 − r(0; θ(0) ) i=1

1.8
1.6

1.0

We aim to infer the original flow distribution from theincomplete observation, i.e., sampled flow statistics. Suppose N packets appear during a certain time period, andeach of them is sampled independently with probability f .
In other words, we consider random sampling from a population of N packets with sampling frequency f . We define X j and Y j ( j = 1, 2, . . . , M) as the original and sampled flow lengths of the j-th flow, respectively. By definition, N = X1 + X2 + · · · + X M . Let ni (i = 0, 1, . . . , ymax )denote the number of flows whose sampled flow lengthis equal to i, where ymax denotes the maximal sampledflow length. We consider random sampling, so the conditional probability that a sampled flow has i packets giventhat the flow originally has k packets
is given by the bi
nomial distribution, q(i | k) = ki f i (1 − f )k−i . Thus, theprobabilitythat a sampled flow has i packets is given byN
q (i | k) p (k; θ), where p (k; θ) is given byr(i; θ) = k=iEq. (1). We estimate parameter θ from the observed statistics n1 , n2 , . . . , nymax . Note that we cannot observe n0 , thenumber of flows with zero packets sampled. The completedata log likelihood for sampled flow statistics is given by

(0)
n(0)
0 = E θ (n0 | n1 , . . . , nymax ) =original θ

f=1/1000

Inferring with the EM algorithm

i=0

2.0

1.2

0.9

ymax


1.5

2

Figure 4. Actual entropy vs. the estimated entropy using Pareto approximation.

log Lc (θ) = log

1.2

1.0

Estimated θ

0.8

Estimated θ

0.6
0.6

Simulated data

1.8 CC = 0.997
1.6

1.1

1.0

1

2.0

Estimated θ

Estimated θestimated entropy

1.6
1.4

0.8

3.2

Measured data

1.3

1.8

(3)

M-step: The M-step is undertaken on the first iteration bychoosing θ = θ(1) that maximizes Q(θ; θ(0) ). Such a value)
can be obtained by numerically solving ∂Q(θ;θ= 0. Then,∂θ(1)the new θ is substituted into the right-hand side of Eq. (3)to produce an updated value of n(1)0 . In the same manner,
we repeat the E- and M-steps alternately until the estimatedparameter θ(k) on the kth iteration satisfies θ(k) − θ(k−1) <10−4 .
(0)

3.3

Validation of accuracy

We apply the inference technique proposed in the previous section to both measured and simulated data. The
simulated data produced by the ideal discrete Pareto distribution with the shape parameter of θ ∈ {1.2, 1.4, 1.6, 1.8},
where we produced 11 distinct data sets for each shape parameter using diﬀerent random seeds to generate the data.
In total, we examined 48 measured data sets and 44 simulated data sets. For both data sets, we emulated the randompacket-sampling
process with sampling frequencies of−2−3
f ∈ 10 , 10 . The results are shown in Fig. 5, where CC
means the correlation coeﬃcient. For the measured data, we
see that the estimation is not so good and the estimated values are underestimated compared to the actual values. This
trend becomes more severe as the sampling frequency decreases. We conjecture that the reason why the parameters
are not correctly estimated and underestimated is becauseof the approximation of the Pareto distribution. As shownin Fig. 3, the approximation is not so good for large flow
lengths. Moreover, most sampled-flow statistics come fromlarge flows. Therefore, a possible approach to improve theestimation accuracy may be to use the information about
the unsampled statistics, as we will see below. On the other
hand, for simulated data, the estimations are fairly good for
f = 10−2 . However, the estimations deviate for f = 10−3 ,especially for large θ.

4. Use of number of unsampled flows
From the sampled-flow statistics, we cannot observe n0 ,which is the number of flows that are not sampled. In this

f=1/100

Estimated θ

1.4

Measured data
CC=0.971

1.3

1.1
1.5

2.0

original θ

2.5

CC=0.947

1.2

EM algorithm
2.0

1.5

1.5

1.0

1.0

1.0
1.5

2.0

original θ

2.5

2.2

2.0

f=1/100
1.5

original θ

2.0

2.0

1.6
1.8

1.4
2.2
2.0

CC=0.998

f=1/1000 1.8
1.6

1.5

1.1

0.9
1.0

original

Presented method

1.8

1.0
1.0

Estimated θ

Estimated θ

f=1/1000

CC=0.999

2.0

1.4
1.3

2.0

1.5

1.2

1.0
1.0

Artificial data

2.0

Estimated θ

1.5

1.0
1.0

19:00

20:00

21:00

22:00

2.2
2.2
2.1
2.1
2.0
2.0
1.9
23:00 19:00

Time

1.5

original θ

2.0

Figure 6. Original θ vs. the estimated θ usingpresented method.

20:00

21:00

22:00

23:00

Time

Figure 7. Estimated entropy by presented
method (left) and EM algorithm (right). Top
is actual entropy.

mations using the EM algorithm fail.
section, we show an empirical study of how the information about n0 improves the inference. Meanwhile, to obtainsuch statistics, we have two possible solutions. One is to infer the number of original flows from the statistics of TCP
flags that are included in common flow records such as NetFlow. This idea was proposed by Duﬃeld et al. in [1]. Thatis, the number of TCP flows can be inferred using the number of sampled flows whose SYN flag is set. Assuming thatmost flows on the Internet are TCP flows and each flow has
one SYN packet, the number of original flows can be inferred as M = f −1 m s , where m s is the number of sampledflows with the SYN flag set. The disadvantage of this approach is that non-TCP flows such as UDP and ICMP are
not considered. Another approach is to measure the number of flows directly. We can adopt several techniques toachieve such measurement that can be achieved in highspeed networks with very small amount of memory, e.g.,
probabilistic counting or bloom filter. The disadvantage ofthis approach is that the addition of new measurement functions on routers is required.
We assume that we can obtain n0 through the above approaches. Then, we find the parameter θ that maximizes
the complete-data log likelihood defined in Eq. (2). That is,
we numerically solve the equation, ∂ log∂θLc (θ) = 0. Here, weused the actual value of n0 for each data set. The results
are shown in Fig. 6. Although the parameters are underestimated again, the correlations with the original parameters
are significantly improved. We conjecture that the reason
why the presented method, i.e., the MLE with the information about n0 , underestimates parameters is because we
do not have any information about the flow mix of the unsampled data, which cannot be obtained unless we know
the original distributions. To see the usefulness of the estimated parameters, we calculate entropy using the estimatedparameters (see Fig. 7). For comparison, we also plot theoriginal entropy. We see that the presented method tracks
the change in the original traﬃc pattern well while the esti-

5. Conclusion
We demonstrated that packet sampling causes the change
in traﬃc pattern to become undetected and the original traffic pattern cannot always be reconstructed even if we use
the EM algorithm for the sampled-flow statistics. We also
showed that additional information about the original flow
statistics, the number of unsampled flows, is eﬀective intracking the change in original traﬃc patterns. We believe that this approach is promising in establishing a scalable network operation scheme that can also detect network
anomalies.
Acknowledgments We are grateful to Professor Tetsuya
Takine for providing the idea of the parametric approach toinfer flow statistics. This work was supported by the Ministry of Internal Aﬀairs and Communications, Japan.

References[1] N. G. Duﬃeld, C. Lund, and M. Thorup. Estimating flow
distributions from sampled flow statistics. In Proc. ACM SIGCOMM, pages 325–336, August 2003.
[2] IETF Packet Sampling (psamp) Working Group.
http://www.ietf.org/html.charters/psamp-charter.html.
[3] R. Kawahara, T. Mori, N. Kamiyama, S. Harada, and
S. Asano. A study on detecting network anomalies using sampled flow statistics. Proc. SAINT Workshop.
[4] A. Lakhina, M. Crovella, and C. Diot. Mining anomalies using traﬃc feature distributions. In Proc. ACM SIGCOMM,
pages 217–228, September 2005.
[5] Measurement and Analysis on the WIDE Internet.
http://www.wide.ad.jp/wg/mawi/.
[6] T. Mori, M. Uchida, R. Kawahara, J. Pan, and S. Goto. Identifying elephant flows through periodically sampled packets.
In Proc. ACM IMC, pages 115–120, October 2004.
[7] K. Xu, Z. L. Zhang, and S. Bhattacharyya. Profiling internet
backbone traﬃc: Behavior models and applications. In Proc.
ACM SIGCOMM, pages 169–180, September 2005.