Effect of sampling rate and monitoring granularity
on anomaly detectability
Keisuke Ishibashi ∗ , Ryoichi Kawahara † , Mori Tatsuya† , Tsuyoshi Kondoh∗ and Shoichiro Asano ‡∗ Information Sharing Platform Labs. NTT Corporation 3-9-11 Midoricho Musashino-shi Tokyo, Japan† Service Integration Labs. NTT Corporation 3-9-11 Midoricho Musashino-shi Tokyo, Japan‡ National Institute of Informatics 2-1-2 Hitotsubashi Chiyoda-ku Tokyo, Japan

Abstract—In this paper, we quantitatively evaluate how sampling decreases the detectability of anomalous traffic. We build
equations to calculate the false positive ratio (FPR) and false negative ratio (FNR) for given values of the sampling rate, statistics
of normal traffic, and volume of anomalies to be detected. We
show that by changing the measurement granularity, we candetect anomalies even with a low sampling rate and give theequation to derive optimal granularity by using the relationshipbetween the mean and variance of aggregated flows. With thoseequations, we can answer for the practical questions that arisein actual network operations; what sampling rate to set in order
to find the given volume of anomaly, or, if the sampling is toohigh for actual operation, then what granularity is optimal tofind the anomaly for a given lower limit of sampling rate.

I. I NTRODUCTION
With threats against Internet security increasing, monitoring
Internet traffic and detecting anomalous traffic, such as DDoS
(distributed denial of service) attacks has become a criticaltask in network operations.
Monitoring techniques range from counting the volume oftraffic on a link by using an SNMP MIB [1] to capturing
packets transferred through networks by applying mirroringat switches and/or routers or tapping the link. The former
method has a drawback in that it provides only the traffic
volume and no information about the source and victim ofthe detected anomaly. On the other hand, the latter method
gives rich information but lacks scalability because capturing
a large volume of packets is still difficult and installing capturing devices throughout the whole network is prohibitively
expensive.
Recently, because of its easy implementation and rich information for identifying and diagnosing anomalous traffic, flow
monitoring at routers has been used for these purposes [2],[3]. This method mainly provides 5-tuple of flow information
through the routers. There have been many studies on detecting and diagnosing anomalous traffic using flow monitoring
results [4], [5]. However, in a high-traffic-rate environment,
flow monitoring increases the load on the router. To decrease
this load, sampling has been introduced for flow monitoring. It
is naturally expected that sampling will introduce uncertainty
into the measurement results, so it is necessary to determine
how the detectability of anomalous traffic will be affected bysampling.
Two recent studies reported the effect of sampling on
anomaly detection [6], [7]. While they comprehensively stud-

ied various sampling methods and anomaly detection methods
using actual anomalies in their data, they don’t give explicit
equations for the relationship between detectability and sampling rate. Thus, there was still no answer for the simple
question, “to detect a 10-Kpps anomaly in normal traffic whosebaseline is 200-Kpps, what is the maximum sampling rate?”
This is important for network operators. In [8], Kawahara
quantitatively evaluate how sampling decrease the detectabilityof anomaly in the number of flows. However, to the best of ourknowledge, there have been no studies that provide an answer
to the above question for the anomalies with large number ofpackets, which is required for actual network operation.
In this paper, we simply focus on packet-volume based
anomaly, and evaluate the effect of sampling on anomaly
detection. We then derive the relationship among the size ofanomalies to be detected, the statistics of normal traffic, andthe sampling rate. By using the relationship, we provide theoptimal sampling rate or maximum detectable anomaly withgiven parameters such as normal traffic statistics. In addition,
we show that by changing the measurement granularity, we
can detect anomalies even with sampled traffic.
The rest of the paper is organized as follows. In section II,
the effect of sampling on anomaly detection is derived theoretically and an evaluation of actual traffic data is given.
Then, in section III, under the sampling, which granularityof traffic monitoring is optimal with given evaluated to detect
give volume of anomalies.
II. E FFECT OF S AMPLING
A. False Negative/Positive Ratio with Packet Sampling
By definition, anomalous traffic is detected by its deviationfrom normal traffic behavior or statistics. If sampling changes
the statistics of normal and anomalous traffic flows equally,
then detectability does not depend on the sampling rate.
However, as shown below, while the mean rates of normal
and anomalous traffic decrease linearly as the sampling rate
decreases, the variance of the normal traffic does not decreaseas fast for a very small sampling rate. This is because, sampling itself introduces deviations into sampled traffic. Thus,
sampling increases the relative variance of normal traffic, and
it is possible that the detectability of anomalous traffic is
decreased. Thus, we derive the relationship for this effect.
In the following of the paper, we assume that packets
are sampled using a random packet sampling method, wherepackets passing through a certain router are sampled with afixed probability independently of other packets being sampled. There is also a representative sampling method such assystematic sampling, in which packets are sampled from apacket stream at a fixed interval [9]. However, the results for
random sampling is easily applicable for systematic sampling
and the effect of systematic sampling is smaller than that ofrandom sampling.
Here, we define the notation.
• Pt : Number of packets in the t-th measurement interval• P nt : Number of normal packets in the t-th measurement
interval• P at : Number of anomalous packets in the t-th measurement interval. (P t = P nt + P at .)• m: Mean of P n t .
2• σ : Variance of P n t .
• a: Mean of P a t . (We focus on to detect an anomaly that
occurs in a measurement interval. Thus the variance of
anomalous traffic in multiple measurement intervals is notconsidered.)• p: Sampling rate.
• Pt (p): Number of packets sampled in the t-th measurement interval with sampling probability p.
• P nt (p): Number of packets of normal traffic in themeasurement interval.
• P at (p): Number of packets of anomalous traffic sampled
in the measurement interval with sampling probability p.
2• σ(p) : Variance of P n t (p).
• m(p): Mean of P n t (p).
In this paper, we focus on the volume-based anomaly andanomalous traffic is judged to occur if the traffic volume
exceeds a threshold based on normal traffic statistics; that is:Pt>

m + cth σ,(1)

where cth determines the degree of deviation from which we
judge that traffic is anomalous.
With this definition, the false negative ratio (FNR) and false
positive ratio (FPR) are expressed as follows (Fig. 1).
FNR =
FPR =

Pr[P nt + P at < m + cth σ]
Pr[P nt > m + cth σ]

(2)
(3)

If the distribution function of normal traffic and the size ofthe anomalous traffic are given, then both F N R and F P R
can be calculated using the parameter c th . For example, if we
can assume that the normal traffic has a Gaussian distribution 1
and that cth = 2.33, then F P R will be 1.0% independently of
the anomalous traffic. As for F N R, if we fix the anomalous
traffic volume to be detected, such as a = 6σ, then F N R is
also determined, such as 0.012%.
Next, we evaluate how F N R and F P R change whensampling is introduced. First, we define F N R(p) and F P R(p)for the sampled traffic as follows.
F N R(p) :=F P R(p) :=Pr[P nt (p) + P at (p) < m(p) + cth σ(p)](4)(5)
Pr[P nt (p) > m(p) + cth σ(p)]1 We give the evaluation on this assumption later.

Fig. 1. Probability distribution functions of traffic for normal andanomalous periods. Sampled traffic has lower means, but its variances
are not so much lower. Thus, F N R and/or F P R can increase.

By the same explanation as for Eq. (3), F P R(p) is determined by only the choice of c th . Thus, we focus on F N R(p)hereafter and evaluate each term of Eq. (4). As for the righthand side of Eq. (4), m(p) is simply the scaled-down value ofthe packet rate for original traffic, mp. On the other hand, σ(p)is not only the scaled-down variance of the original traffic,
σ 2 p2 , but also includes the variance introduced by sampling.
The latter term is obtained as mp(1 − p) as the variance of m
Bernoulli trials with probability p. Thus, σ(p) is obtained as 2

σ(p)

=

!
σ 2 p2 + mp(1 − p).

(6)

Next, we evaluate the left side of Eq. (4). If we assume
that P nt is distributed in a Gaussian manner, then P n t ∼N (mp, σ 2 p2 + mp(1 − p)). P at is also the result of a
Bernoulli trials and follows a binomial distribution, which canbe approximated by a Gaussian distribution. Thus, with thesame calculation as for Eq. (6), P a t ∼ N (ap, ap(1 − p)).
Therefore, P n t + P at is the convolution of two Gaussian
distributions, andP nt + P at ∼ N ((a + m)p, σ 2 p2 + (a + m)p(1 − p).

(7)

Therefore, F N R(p) can be written using the cumulative
distribution function for the Gaussian distribution of Eq. (7),Fa,n (x) as
F N R(p)=Fa,n ((a + m)p+cth (σ 2 p2+(a+m)p(1 − p)). (8)Here, for the given target F N R ∗ , the minimum sampling
rate p∗ is obtained by solving the following equation:
Fa,n ((a + m)p∗+cth (σ 2 p∗ 2+(a + m)p(1 − p))=F N R∗ . (9)2 Equation (7) is also mentioned in [7] as the variance of the number ofsampled flows as an assumption. But it can be strictly derived and we show
the derivation in the appendix.

Fig. 2. Fitting the empirical distributions of normal traffic with Gaussian
distributions. X axis is normalized with maximum number of packets.

For example, if F N R ∗ is the same as F P R, which isdetermined by c th , then by solving Eq. (9), we getp∗=

B. Evaluation

c2
! th
+ 1.
a + 2m − 2 am + m2 + σ 2 c2th

(10)

We evaluated the results given in previous section bysimulations using actual traffic data.
We used the following two sets of data:
1G: Data measured on a 1-Gbps link with an average utilization ratio of 95%. The mean packet rate was 169 kpps
and the standard deviation was 137,313 measured at
1 min. intervals. We used 2 hours of data during working
hours, which can be regarded as being stationary.
• 100M: Data measured on a 100-Mbps link with an average utilization ratio of 85%. The mean packet rate was
16 kpps and the standard deviation was 62,210 measured
at 1 min. intervals. We used 4 hours of working-hour data,
which can be regarded as being stationary. (Actually, weremove some apparent spikes to obtain stationary data,
as same as in [6].)•First, we evaluate the assumption of Gaussian distribution
for normal traffic. Fig. 2 shows the results of fitting theempirical distributions ([Actual]) of two normal traffic with
Gaussian distributions ([Normal]). It can be seen that Gaussian
assumption can be applied for those high-volume traffic asreported as [10]. It is worthful to mention that the discussion
given in this paper can be easily extended to heavy-tailed
distributions while some equations are not explicitly solved
but numerical calculation is required.
We then evaluated F N Rs for various sampling rates. To
verify the detectability Eq. (4), we inserted the synthesizedanomalous traffic whose size was 6σ into the observed trafficand checked whether the total traffic exceeded the threshold:m(p)+cth σ(p), where cth = 2.33, so that F P R will be to 1 %(Hereafter, we fix c th = 2.33 unless specifically mentioned
otherwise). By changing the bin into which the anomalous

Fig. 3.

Comparison of calculated and simulated false negative ratio

traffic was inserted, we counted the number of misdetections
and calculated the ratio, F N R.
The simulated ([sim] in the figure) and calculated ([calc] inthe figure) F N Rs are compared in Fig. 3. Because the data
was 2- and 4-hour data and the total numbers of bins were
120 and 240, respectively, we could not accurately evaluate the
F N Rs below about 1 %. However, for the range above 1%,
the F N Rs calculated using Eq. (4) accurately predict thoseobtained through simulation. We also observed that when thesampling rates decreased to 1/100, F N R started to degrade
and when the rates were under 1/1000 for 1G data and 1/2000
for 100M data, F N R exceeded 1%. Thus even if anomaly
whose size is 6σ, it can be difficult to detect it with small
sampling rate, while it can be easily detected by eyeballing
the time series data when sampling is not applied,
The reason that the F N R of 1G data was more sensitive tothe sampling rate can be explained using Eq. (7) as follows.
Detectability mainly depends on the ratio of the standard deviation of the normal traffic to the size of the anomalous traffic.
The standard deviation of sampled normal traffic consists of
two terms as shown in Eq. (7). As the sampling rate decreased,
the second term on the right side of Eq. (7), which is the mean
rate of normal traffic, increased relative to the first term. Thus,
the smaller the ratio of the traffic’s variance to its mean, which
is known as the index of dispersion for count (IDC) [11], thegreater the sensitivity of F N R to low sampling rate. Because
1G data has smaller IDC than that of 100M data, FNR can be
relatively degraded with larger sampling rate.
We also ran the simulation by changing the anomaly size fora fixed sampling rate, p = 1/1000, and found the relationshipbetween the anomaly size and F N R (Fig. 4). It can be seenthat to achieve an F N R of under 1% with a sampling rate of
1000, the anomaly size should be larger than 5 or 6 times σ,
the standard deviation of normal traffic.
Then, we evaluated the relationship between anomaly sizeand sampling rate to achieve F N R=1%. The minimum
anomaly that can be detected with F N R=1% for a given
sampling rate is shown in Fig. 5. Like Fig.4, the anomaly size
was normalized by the standard deviation of normal traffic.

Fig. 4. False negative ratio vs. anomaly size for sampling rate 1/1000

prefixes). Here, there is a trade-off between detectability andthe aggregation level or the monitoring granularity. In thissection, we evaluate the optimal monitoring granularity interms of the mean rate of counters, with given anomaly size
to be detected and sampling rate. Through the evaluation,
we derive some rules, such as “to detect an anomaly of
10 kpps with a sampling rate 1/10000, we must measure thetraffic with granularity of x pps”, which is useful for network
operators.
In determining the granularity in terms of mean packet
rate, we need to have the relationship between the mean andstandard deviation of normal traffic because the detectability
equation, Eq. (4), is based on both the mean and standard
deviation. Here, we assume that the standard deviation of acounter σm can be written with mean rate m asσm = cmφ ,Fig. 5. Anomaly size that can be detected with given sampling rate.

With a sampling rate of 1, the minimum anomaly size was
4.66(= 2×2.33)σ. The same as for the result shown in Fig. 3,
when the sampling rate decreased under 1/100, the minimum
anomaly size started to increase, and when the sampling rate
was 1/10000, the minimum anomaly sizes were 10σ for 100M
data and 12σ for 1G data.
III. M ONITORING GRANULARITY(11)

where where 0 ≤ φ ≤ 1 and c is a constant.
As for φ, If the time series of non-aggregated traffic (e.g.,time-series for each destination IP address) are mutuallyindependent, then the variance of the aggregated traffic is thesum of the individual traffic variances and φ = 0.5. On theother hand, if time series are highly correlated, then phi can benearly one. There have been some studies of the relationshipfor actual Internet traffic. Gunnar et al. analyzed the relationship shown in Eq. (11) for each cell of the real traffic matrix
and found that φ = 0.7 ∼ 0.8 [12]. When various aggregate
levels for web traffic were measured, φ = 0.5 was found to
fit the actual data [13]. To evaluate the relationship with thetwo datasets that we used, we divided the traffic according
to its destination IP address with various prefix lengths andcalculated its mean and standard deviation. A scatter plot of themean and standard deviation of each address prefix is shownin Fig. 6. We also plotted the standard deviations that follow
the relationship in Eq. 11, where c was determined so thatwhen m was equal to the total traffic, σ m coincided with thestandard deviation of the total traffic. Most of the points fall
into the region between φ = 0.5 and φ = 1.0. Here, because
as the standard deviation is large, detectability is low, so weused φ = 0.5 for an evaluation that is mostly on the safe side.

A. Mean and variance of classified traffic and its detectability
In the previous section, we considered only a single timeseries of traffic data (packet volume) and detected an anomaly
as a deviation of the time series. In many types of anomalous
traffic, the values of some packet header fields are concentrated
in specific ranges. For example, in DDoS attacks, the destination IP addresses are, and in scans, the source IP addresses are.
Thus, by counting the number of packets with each particularfield value and making a multiple time series, we shouldbe able to detect anomalies that we failed to find when wetreated the entire traffic deviation. However, counting traffic
for each source/destination IP address requires a large numberof counters and is impossible in backbone monitoring. Thus,
it usual to aggregate some ranges of the field values andmeasure traffic for each aggregated value (e.g., IP address

We first evaluated how the spatial granularity affects thedetectability for a given anomaly size and sampling ratio. We
compared the calculated F N R obtained by substituting σ m
in Eq. (11) into Eq.(4) with the simulated F N Rs for eachdivided traffic time series using the same method as in theprevious section. The results are shown in Fig. 7. While there
are some discrepancies between the simulation results and thecalculated results for 1G data, which are expected becauseof the negatively correlated traffic, most of the plots coincidewith each other.
Next, we investigated which granularity is optimal in thesense the granularity is maximum (number of time series isminimum) while the F N R(p) is above the threshold for agiven sampling rate and anomaly size.

Fig. 6.

Scatter plot of mean and sigma of number of packets

Fig. 8. Maximum granularity to detect 10 Kpps anomaly for each samplingrate
Prefixlength28bit (hash)
28bit
29bit (hash)
29bit

Granularity(max/avg/min) [Kpps]
21.3/10.5/7.5
86.3/10.6/0.00
30.9/21.1/17.2
106.1/21.2/0.27

FNR(max/avg/min)[%]2.5/1.3/0.0
60.8/5.0/0.0
3.3/1.5/0.0
58.3/12.4/0.0

TABLE IFNR S WITH PARTITIONED TRAFFIC WITH HASHED IP ADDRESSES

B. Classifying packets to achieve target granularity
In this subsection, we discuss how to realize the granularity
calculated with Eqn.(13), e.g. how to classify packet so
Fig. 7. Comparison of calculated and simulated FNR for each partitioned that counters for those classified packets will be the given
traffic
granularity. Here, we describe two classifications, based on IP
address and based on DDoS type.
As for the former classification, we must consider the effectHere, for the given target F N R ∗ , the maximum monitoring
granularity m ∗ is obtained as the solution for the following of high spatial locality in the Internet traffic [14]. That is theequation in terms of m, in a similar manner to finding the concentration of large number of packets to a small numberof IP address space. Thus, only by classifying the aggregated
optimal sampling rate p ∗ .
IP address range, there will be large bias among the counters
Fa,n ((a + m)p+cth ((cmφ ))2 p2+(a + m)p(1 − p))=F N R∗ (12) as shown in Fig. 7. In that case, increasing the number ofHere, by setting F N R ∗ to be the same as F P R, we get counters may not improve the detectability. By hashing theIP addresses, it is expected that the effect of locality can be
the explicit solution as
avoided and the number of packets among the counters will(a/cth )2 + 2a + c2th − 2a/p − 2c2 /p + c2 /p2
be balanced.
.
(13)
m∗ =
4(1/p − 1 + c2 )For example, to achieve the granularity of 19.3 Kpps for
The optimal granularity in terms of the mean packet rate 1G data to detect 10 Kpps anomaly with 1/10000 sampling as
for various sampling rates is shown in Fig. 8. We set the shown in the previous subsection, we should divide into about
target F N R∗ as 1%, anomaly size as 10 kpps, φ = 0.5, and nine counters of whole 170 Kpps traffic. That is achieved by
two values of c corresponding to 1G and 100M data. It can using first 28 or 29 bits of hashed IP addresses. Table I shows
be seen that the monitored granularity of the two parameters the results. It can be seen that by using hashed IP address, thediffered for a high sampling rate because the major factor objective FNR is almost achieved, while with non-hashed IP
in the sampling rate is the standard deviation of the original addresses, FNR can be 60% even with classified traffic.
traffic, that is, the first term of Eq. (7). On the other hand,
Next, we evaluate the classification based on DDoS type.
when the sampling rate was very low, the second term become We classified ICMP, UDP, and TCP SYN packets, each of
dominant and the two optimal granularity approached the same which is used for typical DDoS attacks [15]. We found that it
value, about 20 kpps (19.3 Kpps for 1G data and 16.5 Kpps consists of 12%, 8%, and 2% of total packets, respectively forfor 100M data) with sampling rate 1/10000.
both 1G and 100M data, except that in 1G data, only 0.3% of

Fig. 9. Scatter plot of mean and sigma of number of packets for classified
packets

icmp packets, where filtering is suspected. As shown in Fig. 9,with this classification, standard deviations almost fall into theregion of 0.5 ≤ φ ≤ 1 in Eqn. (11), so we can apply results
provided in the previous section. For example, the mean packet
rate of UDP traffic in 1Gdata is 20.7 Kpps, which is almost thesame as the maximum granularity to detect 10 Kpps anomaly
with sampling rate 1/10000 and FNR = 1 %. Through thesimulation for UDP packets with the above condition, we canachieve FNR = 2.5 %, which is nearly to the target FNR
IV. C ONCLUSION
In this paper, we showed how sampling decreases thedetectability of anomalous traffic. We derived equations for
F N R and F P R when the random packet sampling method isused. Using the equations, we derived the minimum sampling
rate to achieve the target values of F N R and F P R. The
results were evaluated through simulations using actual traffic
data. Especially, we showed that when sampling rate decrease
under a value such as 1/100, the FNR rapidly degrade andthe degradation depends on IDC of the normal traffic. Then
we found that by changing the measurement granularity, we
could detect anomalies even with sampled traffic. In addition,
how to realize the optimal granularity to detect anomalies withgiven volume to be detected. For example, by counting only
UDP traffic, FNR can be improved from 48 % to 2.5 % fordetecting UDP Flooding attack.
ACKNOWLEDGMENT
We would like to thank Kenjiro Cho, who to admit the useof MAWI data [16]. This study was supported in part by the
Ministry of Internal Affairs and Communications of Japan.
R EFERENCES[1] P. Barford, J. Kline, D. Plonka, and A. Ron, “A signal analysis of
network traffic anomalies,” in Proc. 2nd ACM SIGCOMM Workshop
in Internet Measurement (IMW2002), Marseille, France, October 2002.
[2] B. Claise, “Cisco Systems NetFlow Services Export Version 9,” RFC
3954, October 2004.
[3] P. Phaal, S. Panchen, and N. McKee, “InMon Corporation’s sFlow: A
Method for Monitoring Traffic in Switched and Routed Networks,” RFC
3176, September 2001.

[4] P. Barford and D. Plonka, “Characteristics of Network Traffic Flow
Anomalies,”in Proc. 1st ACM SIGCOMM Workshop in Internet Measurement (IMW2001), San Francisco, USA, November 2001.
[5] A. Lakhina, M. Crovella and C. Diot, “ Characterization of NetworkWide Anomalies in Traffic Flows,” in Proc. 4th ACM SIGCOMM
Conference on Internet Measurement (IMC 2004), Taormina, Italy,
October 2004.
[6] D. Brauckhoff, B. Tellenbach, A. Wagner, M. May, and A. Lakhina,“Impact of Packet Sampling on Anomaly Detection Metrics,” in Proc.
6th ACM SIGCOMM Conference on Internet Measurement (IMC 2006),
Rio de Janeiro, Brazil, October 2006.
[7] J. Mai. C.-N. Chuah, A. Sridharan, T. Ye, and H. Zang, “Is Sampled
Data Sufficient for Anomaly Detection?” in Proc. 6th ACM SIGCOMM
Conference on Internet Measurement (IMC 2006), Rio de Janeiro, Brazil,
October 2006.
[8] Ryoichi Kawahara, Tatsuya Mori, Noriaki Kamiyama, Shigeaki Harada,and Shoichiro Asano, “A study on detecting network anomalies using
sampled flow statistics,” in Proc. IEEE SAINT 2007 Workshop on
Internet Measurement Technology and its Applications to Building Next
Generation Internet, Hiroshima, Japan, January 2007.
[9] T. Zseby, M. Molina, N. Duffield, S. Niccolini, and F. Raspall, “Sampling and filtering techniques for IP packet selection,” Internet-Draft,
draft-ietf-psamp-sample-tech-07.txt, July 2005.
[10] J. Cao, W. S. Cleveland, D. Lin, and D. X. Sun, “Internet Traffic Tends
Toward Poisson and Independent as the Load Increases,” in Nonlinear
Estimation and Classification, Springer Verlag, Dec. 2002.
[11] R. Gustella, “Characterizing the variability of arrival processes withindexes of dispersion,” IEEE Journal on Selected Areas in Communications, vol. 9, no. 2, pp. 203–211, February 1991.
[12] A. Gunnar, M. Johansson, and T. Telkamp, “Traffic Matrix Estimation
on a Large IP Backbone: a Comparison on Real Data,” in Proc. 4th ACM
SIGCOMM Conference on Internet Measurement (IMC 2004), Taormina,
Italy, October 2004.
[13] R. Morris and D. Lin, “Variance of aggregated web traffic,” in Proc.
IEEE INFOCOM 2000, Tel Aviv, March 2000. n[14] K. Ishibashi, M. Aida and M. Imase, “Characteristics of Temporal andSpatial Locality of Internet Access Patterns,” in Proc. IFIP Networking
2002 Workshop on Web Engineering, Pisa, Italy, May 2002.
[15] J. Mirkovic and P. Reiher, “A taxonomy of DDoS attack and DDoS
defense mechanisms,” ACM SIGCOMM Computer Communication Review, vol.34, no.2, April 2004.
[16] MAWI Working Group Traffic Archive,
available at http://tracer.csl.sony.co.jp/mawi/.

A PPENDIX
Let f (n) := Pr[Pt = n] and fp (n) := Pr[P nt (p) = n].
Then,
σ 2 (p)"=n2 fp (n) − [m(p)]2" "=n2Pr[P nt (p) = n|P nt = m]f (m) − (mp)2
=

n

m

"

∞
"

n2

n

=
=
=

m=1 n=1∞"(1 − p)m−n f (m) − (mp)2n2 [m Cn pn (1 − p)m−n ]f (m) − (mp)2

f (m)

m=1

n

m=n

∞ "
m
"

m=1
∞
"

m Cn pm"n=1n2 [m Cn pn (1 − p)m−n ] − (mp)2

f (m)[mp(1 − p) + (mp)2 ] − (mp)2= p(1 − p)m + p2 [σ 2 − m2 ] − (mp)2= p(1 − p)m + p2 σ 2(14)