IEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 2013

3028

PAPER

On Optimal Magnitude of Fluctuations in Probe Packet Arrival
Intervals∗
Kohei WATABE†a) , Student Member and Masaki AIDA††b) , Member

SUMMARY
Active measurement is an end-to-end measurement technique that can estimate network performance. The active measurement
techniques of PASTA-based probing and periodic-probing are widely used.
However, for the active measurement of delay and loss, Baccelli et al. reported that there are many other probing policies that can achieve appropriate estimation if we can assume the non-intrusive context (the load of
the probe packets is ignored in the non-intrusive context). While the bestpolicy in terms of accuracy is periodic-probing with fixed interval, it suﬀers
from the phase-lock phenomenon created by synchronization with network
congestion. The important point in avoiding the phase-lock phenomenon
is to shift the cycle of the probe packet injection by adding fluctuations. In
this paper, we analyse the optimal magnitude of fluctuations corresponding to the given autocovariance function of the target process. Moreover,
we introduce some evaluation examples to provide guidance on designing
experiments to network researchers and practitioners. The examples yieldinsights on the relationships among measurement parameters, network parameters, and the optimal fluctuation magnitude.
key words: active measurement, fluctuation, probe packet, periodicity

1.

Introduction

Packet loss rate and delay are important factors that decideservice performance since high values can trigger the dropping of audio and video frames, particularly in real timecommunication services like video conferencing. Consequently, a detailed analysis of the loss and delay generated in
actual networks has obvious benefits for the design of loss
and delay sensitive applications, and it is useful also fromthe viewpoint of traﬃc management. However, it is inherently diﬃcult to gather information related to loss and delay,
because the Internet is composed of multiple networks thatare managed by diﬀerent Internet Service Providers (ISP) orother organizations. Therefore, we need a way that oﬀers
end-to-end measurements of the Quality of Service (QoS),
which includes delay and loss.
Active measurement is an end-to-end measurement
technique that can estimate the QoS of a network path. Active measurement derives the QoS from information obManuscript received February 13, 2013.
Manuscript revised July 7, 2013.
†
The author is with the Graduate School of Information
Science and Technology, Osaka University, Suita-shi, 565-0871
Japan.
††
The author is with the Graduate School of System Design,
Tokyo Metropolitan University, Hino-shi, 191-0065 Japan.
∗
The earlier version of this paper was presented at the 30th
IEEE international Conference on Computer Communication (INFOCOM 2011) Mini-Conference.
a) E-mail: k-watabe@ist.osaka-u.ac.jpb) E-mail: maida@sd.tmu.ac.jp
DOI: 10.1587/transcom.E96.B.3028

tained by injecting probe packets into the target network
path [1]–[5]. From the delay/loss experienced by probe
packets, active measurement can estimate one-way delay,
Round-Trip Time (RTT), and loss rate on the network path.
It can also estimate link capacity [6], [7] and available bandwidth [8], [9] from changes in the delay or interval of theprobe packets.
Active measurement is easy for the end user to perform
but it is not trouble free due to the tradeoﬀ between accuracy
and the number of probe packets. The load of the probe
packets aﬀects the path’s performance. We cannot estimate
the true performance since that state occurs only without theprobe stream. If we inject a lot of probe packets to increase
the probing rate, the estimation accuracy would suﬀer since
the extra traﬃc becomes appreciable. We do not deal herewith the overheads imposed by the probe stream, but westate that a high probing rate does not necessarily provide
accurate measurement. A detailed discussion of overheads
is given in reference [10]. Moreover, active measurements
have great diﬃculty in determining the average loss rate because packet loss is a rare event and the rate is low in mostcurrent networks, especially in the Internet core. Long delay events are as rare as packet loss, and require many probe
packets for detection.
Therefore, it is important to be able to achieve highly
accurate measurements with a limited number of probe
packets. Then many prior works focus on the optimizationof the operation to provide more accurate estimation [11]–[17].
Work by Baccelli et al. [11], [12] gave an importantsuggestion on the accuracy of active measurement in assessing delay and loss. Two methods are now popular for
determining probe timing in active measurement: PASTAbased probing and periodic-probing. PASTA-based probing
is the probing policy that follows the well-known PASTA(Poisson Arrivals See Time Averages) property [18], i.e. thepacket injection is a Poisson process (arrival intervals follow
an exponential distribution), and periodic-probing is basedon fixed probe packet intervals. A comparison of PASTAbased probing and periodic-probing was discussed in RFC[19] and prior work [20]. The works showed that periodicprobing might achieve more accurate measurement compared with PASTA-based probing though it can become synchronized with the target. The above discussions consider,however, only two alternatives. In recent work [11], Baccelli et al. indicated that there might be many other probing
policies that can estimate true performance values given thec 2013 The Institute of Electronics, Information and Communication Engineers
Copyright WATABE and AIDA: ON OPTIMAL MAGNITUDE OF FLUCTUATIONS IN PROBE PACKET ARRIVAL INTERVALS

3029

assumption of a non-intrusive context (the extra traﬃc ofprobe packets can be ignored). Moreover, according to theresult in reference [12], the best policy in terms of accuracy
is periodic-probing under the general condition. However,it may not be best overall because of the synchronization
problem (the problem is referred to as the phase-lock phenomenon). To solve this problem, Baccelli et al. [12] proposed a probing policy that makes the probe packet intervals
follow a parameterized Gamma distribution.
That is, Baccelli et al. provided multiple selections
other than traditional PASTA-based probing and periodicprobing, and they suggested that the optimal probing policy might be one of the selections. The work has a serious
problem with regard to practical measurements even though
it represents a great advance in network measurement. Its
weakness was that it failed to specify the optimal parameterof the Gamma distribution. Therefore, Gamma-probing has
been unable to establish optimal probing policies.
In this paper, to provide guidance to researchers andpractitioners regarding how they should inject probe packets, we analyse the fluctuation magnitude of optimal probing policy and clarify the relationships between the optimal
fluctuation magnitude and the properties of the target process. The important point in avoiding synchronization is to
shift probe packet periodicity by fluctuations. Baccelli et al.
shift the periodicity by using a Gamma distribution to determine probe packet intervals. In our study, we introduce
a probing policy that fluctuates the probe intervals by using
a normal distribution and determine the optimal fluctuation
magnitude for the target process. Our analysis is composedof the following three steps.
1. To define the optimal magnitude of fluctuations that areadded to the timing of probe packets, we define an evaluation function that takes the phase-lock phenomenon
into consideration.
2. We show our evaluation function is determined by the
autocovariance function (ACF) of the target process
and the probing policy. Moreover, we clarify the relationships between the optimal magnitude of fluctuations and ACF of target process.
3. We show some evaluation examples in which wechange ACF, measurement period, and the number ofprobe packets variously. We provide some insights
by clarifying the dependency of the optimal fluctuation magnitude on network/measurement parameters.
These insights are useful for network researchers andpractitioners in order to design experiments. Especially, for a situation where it is hard obtaining theknowledge of ACF on real measurement, we present
the design criteria on the safe side in order to avoid thephase-lock phenomenon for various ACF.
We provide a detailed mathematical proof and simulation results on the validity of our method. We used some approximations to simplify the derivation of the optimal probing
policy. Mathematical and simulation-based analyses showthat the approximations are valid.

The rest of the paper is organized as follows. Section 2
introduces some prior works regarding probing strategies.
Next, in Sect. 3, we verify the cause of the phase-lock phenomenon and describe a method to assess it. Section 4 explains probing policy with fluctuated probe intervals. Section 5 analyzes the relationships between fluctuation magnitude and the accuracy of active measurement, and provides
a method to specify the optimal fluctuation magnitude. We
confirm the validity of our approximations that we use toderive the optimal probing, through M/M/1 simulation, andshow evaluation examples in Sect. 6. In Sect. 7, we discuss
the generality of our results. We conclude the paper in
Sect. 8.
2.

Probing Policy and Accuracy of the Estimator

In this section, we overview the current state-of-the-art byintroducing some prior works on probing strategies for active measurement.
PASTA-based probing and periodic-probing have been
widely used as the probing policies for active measurement.
These probing policies are described in RFCs [3], [19], respectively, and Roughan’s work provided a comparison of
the two policies [20] (periodic-probing is called uniform
sampling in this). The key features of the PASTA-based
probing and periodic-probing are as follows.
• PASTA-based probing; The probe packet intervals
follow an exponential distribution, i.e. the probe packet
arrivals process follows a Poisson arrival. It can provide bias-free measurement because of the PASTA
property [18] but may be inferior in terms of estimation accuracy.
• Periodic-probing; This probing policy uses fixedprobe packet intervals. It is easier to manipulate, and it
may be superior to PASTA-based probing in terms ofaccuracy in many cases. However, it can suﬀer fromthe problem of synchronization with the target being
measured.
It is unknown to this author how prevalent periodicities arein the modern Internet. However, some works reported theoretical grounds for their existence [21], [22]. Hence, there is
the tradeoﬀ between the two policies, and we cannot judge
which probing policy is better.
Baccelli et al. investigated alternatives to the above two
probing policies, and suggested that there are better policies
than these two probing policies. They indicate that there
are many distributions other than PASTA-based probing thatcan provide bias-free measurements if a non-intrusive context (the load of probe packets is insignificant) can be assumed [11]. This property is named Non-Intrusive Mixing
Arrivals See Time Averages (NIMASTA). NIMASTA contains the following three assumptions.
1. The stochastic process that expresses the network state
we are interested in (e.g. virtual delay and loss/no-loss
indication) is stationary and ergodic. This process is

IEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 2013

3030

called the ground truth process.
2. The point process of probe packet arrivals {T i } (i =1, 2, . . . , m) is stationary and mixing. Mixing is the requirement that guarantees joint ergodicity between theprobe and ground truth processes (see reference [11]for details).
3. The last assumption is the non-intrusive context, i.e.
we can ignore the impact of probe packet overhead.
Namely, the ratio of the probe stream (extra traﬃc) toall streams is very small.
Under the above assumptions, it was proved that thefollowing equation holds:
lim

m
1

m→∞ m

h(X(T i )) = E[h(X(0))]

a.s.,

i=1

1
X(T i ).
m i=1
m

Thus the variance of P̂ is
⎡ m
⎤
⎢⎢⎢
⎥⎥
1
⎢
Var[P̂] = 2 Var ⎢⎣X(T i )⎥⎥⎥⎦
m
i=1
m

1 
m2 i=1 j=1
m

=

m

∞
−∞

r(τ) fi− j (τ)dτ,−∞r(τ) fk (τ)dτ ≥ r(2)

where fi− j is the probability density function (pdf) of T i −T j ,r(τ) = Cov (X(t), X(t + τ)) is the ACF of the ground truth
process X(t) (we can express r(τ) by τ alone, because X(t) is
stationary) and the last equality follows from the stationary∞−∞t fk (t)dt= r(kd)=∞−∞r(τ)δ(τ − kd)dτ,(3)where δ(·) denote Dirac δ function, k is a integer, and thefirst equality follows from the average inter-probe time dof probing. Therefore, fi− j (τ) = δ(τ − (i − j)d) minimizes (2), and it corresponds to periodic-probing. Estimator variance is associated with accuracy, lower is better, so periodic-probing is the best probing process if we
focus only on variance. On the other hand, periodic-probing
does not satisfy the assumptions of (1) due to non-mixing,
so periodic-probing is not necessarily the best. This is because the phase-lock phenomenon may occur and the estimator may converge on a false value when the cycle of theground truth process is synchronized with that of the probing process. For instance, if we inject the probe packets
at time {0, d, 2d, . . . } by periodic-probing with inter-probe
time d to measure a process X(t) = sin(2π(t − S )/d) where
S denotes random variable that follows a uniform distribution U(0, d), the observed values take the same value
X(0) = X(d) = X(2d) = . . . , and the estimator P̂ does notconverge on E[X(0)] = 0. Namely, periodic-probing can become biased. Therefore, we cannot conclude that periodicprobing is always the optimal probing process.
To tune the tradeoﬀ between PASTA-based probing
and periodic-probing (which has bias but superior variance),
Baccelli et al. proposed a probing process whose inter-probe
time follows a parameterized Gamma distribution [12]. The
pdf that is used as the interval between probe packets isgiven byg(x) =1 
Cov X(T i ), X(T j )= 2
m i=1 j=1
m

∞

(1)

where X(t) and h are the ground truth process and an arbitrary positive function, respectively. If we can obtain X(T i )(e.g. the delay of the probe packet or loss/no-loss of probe
packet) from a probe packet injected at time T i , (1) meansthat we can estimate E[h(X(0))] without bias by the injection of m probe packets. The only requirements placed on
the point process of probe packet arrival {T i } (i = 1, 2, . . . )are that it be stationary and mixing. Therefore, there aremany point processes that can achieve unbiased estimationof ensemble mean E[h(X(0))] besides PASTA-based probing, inter-probe time follows an exponential distribution.
Such mixing point processes include those whose intervals
follow a Gamma distribution and a uniform distribution.
Note that periodic-probing with fixed interval is not a mixing process, and does not satisfy (1).
Recent work [12] investigated how to select the optimal
probing process. We can select the optimal (in terms of accuracy) probing process under a specific assumption by using the inter-probe time given by the parameterized Gamma
distribution.
If we estimate the mean of X(0) by using active measurement, the estimator P̂ isP̂ =property of X(t) and the probe packet process.
It was proved that no other probing process with anaverage interval d has a variance that is lower than that ofperiodic-probing [12]. Convexity of r(τ) in real network isevidenced by the network measurement [12] and if r(τ) isconvex on the interval [0, ∞) and the average of the interprobe time is d, the following inequality can be proven byusing Jensen’s inequality [23].

xβ−1  β β −xβ/de
Γ(β) d(x > 0),(4)

where g(x) is the Gamma distribution whose shape and scaleparameters are β and d/β, respectively. d (> 0) denotes themean, and β (> 0) is the parameter. When β = 1, g(x) reduces to the exponential distribution with mean d. Whenβ → ∞, the probing process reduces to periodic-probing because g(x) converges on δ(x − d). If ACF of X(t) is convex,
it has been proven that the variance of estimator P̂ sampled
by intervals that follow (4) monotonically decreases as β increases. We can achieve small variance (it approaches thevariance of periodic-probing) by setting β to a large value
since (4) converges on periodic-probing towards the limit

WATABE and AIDA: ON OPTIMAL MAGNITUDE OF FLUCTUATIONS IN PROBE PACKET ARRIVAL INTERVALS

3031

β → ∞. The problem of bias due to the phase-lock phenomenon can be avoided if we tune β to a limited value(the probing process that has intervals set by (4) is mixing). We can resolve the tradeoﬀ between PASTA-based
probing and periodic-probing if we give β an appropriate
value. This Gamma-probing provides multiple selections lying between traditional PASTA-based probing and periodicprobing through parameter β, and it is a great advance innetwork measurement techniques.
However, since Ref. [12] did not indicate how to decideupon the optimal β, it has remained a problem with no solution. To solve this problem, we introduce in this paper a
method that can specify the optimal probing policy.
3.

Evaluation of Phase-Lock Phenomenon

This study examines the phase-lock phenomenon in detailbecause our goal, specifying the optimal probing process,demands avoidance of this phenomenon. Reference [12]did not mention this cause of the phase-lock phenomenon
in detail because it was not main topic. Accordingly, thissection investigates the cause and eﬀect of the phase-lockphenomenon and introduces an evaluation function that canassess this phenomenon appropriately.
The convex ACF r(τ) of the ground truth process
X(t) means X(t) has no special periodicity (see Fig. 1).
The phase-lock phenomenon occurs when the cycle of theground truth process synchronizes to that of the probing
process. Hence, the phase-lock phenomenon will not occur if the ACF is strictly convex. (3) showed that variance isminimized with periodic probing, and it means that it will
not realize large variance (inaccuracy) due to phase-lockphenomenon, under the strictly convex ACF. However, theexperiments in Ref. [12] demonstrated that there are multiple instances in which the accuracy of the estimator of
periodic-probing was worse than that of other probing processes (periodic-probing is not always inaccurate).
We consider that the phase-lock phenomenon is causedby accidental periodicity that is realized by using finite measurement periods. Even if the ground truth process has no
special periodicity (in terms of long-time average), accidental periodicity is possible. Thus, there is a possibility that a
specific frequency component will be present by chance if
the measurement period is limited. Even if ACF in terms ofensemble mean (namely long-time average)

Fig. 1 Convexity of ACF and special periodicity of the ground truth
process.

r(τ) = E[X(t)X(t + τ)] − {E[X(t)]}2
is strictly convex, ACF in terms of a time average on finite
period (0, l]
R(τ) =

1
l−τ
−

l−τ

X(t)X(t + τ)dt

01
(l − τ)2l−τ

l−τ

X(t)dt0

X(t + τ)dt

(5)0

is not necessarily convex. Note that R(τ) is a stochastic process that depends on X(t). If we measure the X(t) on limited measurement period (0, l], we should consider (5) thatis generated by X(t) on (0, l]. In Fig. 2, we display the ACF
of M/M/1 queue length. The arrival rate and the service
rate are 0.75 and 1.0, respectively. The line of time average in Fig. 2 represents the time average on a finite period(0, 10000] for a single sample path generated by simulation.
According to the figure, we can confirm that the ACF in
terms of a time average is not a convex function though the
ACF exhibits, in terms of ensemble mean, convexity. In a
sample path we show in the figure, we can find accidental
periodicity at τ  250, and the estimator is inaccurate dueto the phase-lock phenomenon if we set a probe interval to250.
Unpredictability is what distinguishes accidental periodicity from special periodicity in terms of long-time average. Special periodicity continues into the future constantly
since it reflects the structure of the target, and hence we canpredict the cycle using knowledge of the past ground truth
process. On the other hand, we cannot predict accidental
periodicity, no matter what knowledge of past ground truth
process we may use. Because the unexpected behavior thatis the diﬀerence between the behavior of the real sample
path and the expected behavior (that is expressed by ACF)
yields accidental periodicity. If we can obtain knowledgeof past ground truth process before a measurement, we can
avoid synchronization with special periodicity by changing
the cycle of the probing process. However, accidental periodicity cannot be predicted and can be generated on any
cycle, and hence we cannot avoid synchronization with accidental periodicity by changing the cycle of the probing process.
Therefore, accuracy will fall if a sample path of theground truth process contains a lot of frequency components to which the probing process can become synchro-Fig. 2

ACF in terms of time average and ensemble mean.

IEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 2013

3032

nized. Conversely, if it contains few such frequency component, the accuracy will be remarkably high. The accuracy of
periodic-probing may become extremely bad for the specificsample path though it is reasonable on average.
Accordingly, to assess the phase-lock phenomenon appropriately we must consider the accuracy that corresponding to the target sample path. We assume the metric that welwant to measure is the time average X l = 0 X(t)/l dt on themeasurement period (0, l] and E[P̂|X(t)] = X l holds (namely
we can achieve bias-free measurement and the assumption
suits our probing method which we will mention in Sect. 4).
Note that our target X l is not ensemble mean E[X(0)] but
empirical average, and it is random variables. By using a
conditional variance, we can express the accuracy for thetarget sample path as
Var[P̂|X(t)].

(6)

Note that the conditional variance (6) is random variable
that depends on stochastic process X(t). We discriminate
between accuracy regarding a time average and accuracy regarding an ensemble mean. The former is expressed by (6),and the latter is expressed by normal variance Var[P̂]. Reference [12] proved that periodic-probing gives Var[P̂] theminimal value (we introduced this in Sect. 2), and we canunderstand that Var[P̂] corresponds to the expectation of the(6) according to the following equation:
E[Var[P̂|X(t)]] = Var[P̂] − Var[X l ].

(7)

Note that the second term on the right-hand side of (7)does not depend on the probing policy. Therefore, by using(7), we can assess the average accuracy (in which periodicprobing is superior). On the other hand, the eﬀect of thephase-lock phenomenon is that (6) is varied with the intensity of the frequency component (which is synchronizedwith the probing process). The eﬀect of the phase-lock phenomenon can be assessed by the following:
Var[Var[P̂|X(t)]].

(8)This paper looks for a probing process that can avoid theextreme drops in accuracy created by the phase-lock phenomenon. In addition, the probing process should alsoachieve a small (7) (In other words, it should also be accurate in terms of average accuracy).
To find a probing policy that satisfies the above two requirements (which are assessed by (7) and (8), respectively),
we introduce the following evaluation function:
2
E[Var[P̂|X(t)]] + Var[Var[P̂|X(t)]]2 = E Var[P̂|X(t)] .
(9)
Our evaluation function is defined by the square of l2 -normof (8), and it is equivalent to Mean Square Error (MSE) withestimated parameter θ = 0. We define the probing processthat minimizes evaluation function (9) as the optimal probing process, and we investigate the optimal probing process

as determined by the property of the target network.
4.

Probing Method with Fluctuations

In this section, to analyse the optimal probing policy, we will
introduce the probing process with fluctuated intervals thatavoids the phase-lock phenomenon. As we mentioned in
Sect. 3, the cause of the phase-lock phenomenon is accidental periodicity. We cannot avoid the phase-lock phenomenon
by changing the cycle of the probing process (i.e. the average probe interval), since accidental periodicity can be generated on any cycle. Therefore, to avoid the phase-lock phenomenon, we use a random variable to fluctuate the probe
intervals. In other words, we force the probing process to
exhibit multiple cycles (i.e. variable intervals). Actually, theGamma-probing proposed by Baccelli et al. in Ref. [12] is
one approach to adding fluctuations. The method we introduce in this section takes three parameters into consideration: measurement period, number of probe packets, andfluctuation magnitude. It is expected that measurement period has a critical aﬀect on the intensity of accidental periodicity. In terms of avoiding the phase-lock phenomenon,
there is no essential diﬀerence between our approach andGamma-probing, but our approach simplifies the analysis of
the relationship between the evaluation function and the parameters of the probing policy.
We add fluctuations that obey a normal distribution to
the timing of probe packet arrivals, while specifying themeasurement period. We assume that the interval (0, l] isthe measurement period and m is the number of probe packets sent in the measurement period. Our probing method
gives the point process of probe packet arrivals {T i } (i =1, 2, . . . , m) as follows.
T i = S + Gi − lS + G 
i

l

,

(10)

where S and Gi denote the random variables that follow
a uniform distribution U(0, l/m) and a normal distribution
N((i − 1)l/m, σ2 ), respectively, · denotes a floor function and σ denotes the magnitude parameter of the fluctuations. To prevent {T i } from taking a value outside the measurement period (0, l], we add the third term. The second
term contributes to the fluctuation of probe packet interval.
The first term determines a phase, and does not aﬀect theprobe packet interval (note that the first term does not depend on i). Note that the order of packet injection could
be changed when the point process of probe packet arrivals
is given by (10). The packets are injected in random order if the fluctuation magnitude is suﬃciently large. It iseasy to prove that the probability that at least one packet
of m probe packets injects in [t, t + Δt) is (mΔt)/l for anyt (0 ≤ t < l) since all of the phases are mixed uniformly
by the random variable S if we inject the probe packets atgiven by (10) (see Appendix). There{T i } (i = 1, 2, . . . , m) fore, estimator P̂ = m
i=1 X(T i )/m is an unbiased estimatorfor our target X l .

WATABE and AIDA: ON OPTIMAL MAGNITUDE OF FLUCTUATIONS IN PROBE PACKET ARRIVAL INTERVALS

3033

Our probing process provides multiple selections lying between traditional PASTA-based probing and periodicprobing as well as Gamma-probing. If σ = 0 (namely there
is no fluctuation), {T i } corresponds to periodic-probing. On
the other hand, if σ → ∞, T i follows a uniform distribution
U(0, l). Therefore, intervals between T i follow an exponential distribution for suﬃciently large l.

even function R̃l (τ). Note that {Kn } (n = 1, 2, . . . ) are
random variables that depend on X(t); they represent theintensity of each frequency component of X(t). SinceT̃ i − T̃ j = Gi − G j (i  j) follows a normal distribution,
N((i − j)l/m, 2σ2 ), the following equation holds:
∞
−∞

5.

Fluctuation Magnitude and Accuracy

m
m
1
1 
X(T i ) =X̃l (T̃ i ).
m i=1
m i=1

l
Therefore, by using ACF R̃l (τ) = 0 X̃l (t)X̃l (t + τ)/l dt −l
{ 0 X̃l (t)/l dt}2 in terms of time average, (6) can be expressed
as follows (as well as (2)).
⎡ m
⎤

⎢⎢⎢
⎥⎥
1

Var[P̂|X(t)] = 2 Var ⎢⎢⎣X̃l (T̃ i )  X(t)⎥⎥⎥⎦
m
i=1
=

m m
1 

∞

m2 i=1 j=1−∞R̃l (τ) fi− j (τ)dτ,

where fi− j is the pdf of T i − T j , and it obeys the normal
distribution N((i − j)l/m, 2σ2 ) when i  j. Note that R̃l (τ) isa stochastic process that depends on X(t).
Furthermore, when we expand R̃l (τ) in Fourier series,
we find that
Var[P̂|X(t)]

⎧
⎪
m m
⎪
⎪
⎨ 
Kn ⎪
= 2
⎪
⎪
m n=1
⎩ i=1 j=1
∞
1 

⎫
⎪
⎪
⎪
2πn
⎬
τ fi− j (τ)dτ⎪
cos
,
⎪
⎪
l
⎭
−∞
∞

(11)
Kn =

2
l

l

cos
0

−∞

cos

2πn
τ fm−k (τ)dτ.
l

Therefore, we obtainIn this section, we will clarify the relationship between fluctuation magnitude imposed on probe timing and the evaluation function (9), and we will detail a method that specifies the optimal fluctuation magnitude, theoretically. As we
mentioned in Sect. 3, periodic-probing is the optimal probing process if we consider only average accuracy. It is important to specify the minimal fluctuation magnitude that
can avoid the phase-lock phenomenon, because large fluctuations cause the probing process to deviate too far fromperiodic-probing.
Our evaluation function (9) is composed of the averageand variance of (6). Therefore, we first address the stochastic behavior of (6). We define X̃l (t) = X(t − lt/l ) which
depends on stochastic process X(t) in measurement period(0, l]. In addition, we define T̃ i = S +Gi , which is composedof a simple uniform and normal random variable. Since X(t)observed at the timing of {T i } is equal to X̃l (t) observed at thetiming of {T̃ i }, the following equation holds:
P̂ =

∞

2πn
τ fk (τ)dτ =
l

cos

2πn
τ R̃l (τ)dτ,lwhere the second equality follows from the periodic and

m
m 


∞
−∞

i=1 j=1=m

2πn
τ fi− j (τ)dτ
l

cos
m−1


∞

i=0

−∞

=m+m

2πn
τ fi (τ)dτ
l

cos

∞
−∞

2
2πn  1− (τ−il/m)τ√ e 4σ2 dτ
l
2σ π
i=1

m−1

cos

∞

2
2πn
1
− τ
τ
√ e 4σ2 dτ
l
2σ π
−∞
m−1
∞

2
2πn
1
− (τ−il/m)
τ+mcos√ e 4σ2 dτ
l
2σ π
−∞
i=0
⎧

τ2
∞
⎪
1√ − 4σ2⎪dτ, n = m j
m + (m2 − m) 0 cos 2πn⎪⎪l τ σ πe⎪⎪⎨=⎪( j = 1, 2, . . . )
⎪
⎪
⎪
∞
τ2
⎪
−
⎪
2πn
1
⎩m − mcos l τ σ √π e 4σ2 dτ,otherwise
0
⎧
2
2πn
2
⎪
⎪
⎨m + (m2 − m)e−( l ) σ , n = m j ( j = 1, 2, . . . )=⎪,2⎪⎩m−m e−( 2πnl ) σ2 ,otherwise

=m−m

cos

(12)

where the last equality follows from the following integral(see Ref. [24]).
∞e−ax cos bx dx =
2

0

1
2

π − b2e 4a ,awhere a and b denote an arbitrary positive real number andan arbitrary real number, respectively.
Substituting (12) for (11), the accuracy achieved fortarget sample path Var[P̂|X(t)] is expressed as follows using the intensity of each frequency component {Kn } (n =1, 2, . . . ).
Var[P̂|X(t)] =∞wi K i ,

(13)

i=1

⎧
2 2
−( 2πi⎪l ) σ⎪⎪⎪ 1+(m−1)em,⎨
wi = ⎪⎪
2πi 2 σ2⎪−⎪⎩ 1−e ( l ) ,m

i = m j ( j = 1, 2, . . . ).

otherwiselNote that K0 = 0 because 0 R̃l (τ)dτ = 0.
To clarify the average and standard deviation of
Var[P̂|X(t)], we must investigate the stochastic behavior of{Kn } (n = 1, 2, . . . ). Since Fourier transformation of autocor2
relation function R̃l (t) + X l of the stochastic process yields

IEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 20133034

a power spectrum (Wiener-Khintchin theorem [25]), the following equation holds for any sample path x(t) of X(t),"!
F r̃l (t) + x2l = |F [ x̃l (t)]|2 ,where r̃l (t) + x2l and x̃l (t) represent the sample paths of2R̃l (t) + X l and X̃l (t) that correspond to the sample path x(t).
Consequently, Kn relates to the Fourier coeﬃcients of X(t)as follows.
Kn =Cn 2 + S n 2
,
2

(14)

where

that obey the same distribution. Note that they are not independent of each other. Suppose that random variables
Xk (k = 0, 1, . . . , n) are stationary and α-mixing with O(k−5 ),and these expectation and the 12th moments are 0 and finite, respectively. The central limit theorem for dependent casesguarantees that the distribution of the summationn= nk=1 Xk can approximate normal distribution for
Xsum
suﬃciently large n [26]. The condition that is required for
Xk is a suﬃcient condition, and the actual restriction is morerelaxed (see Ref. [26] for details). The variance is given by
⎛
⎞
n−1

⎜⎜⎜
⎟⎟⎟
n
2
⎜
E[X1 X1+l ]⎟⎟⎠⎟ .
Var[Xsum ] = n ⎜⎝⎜E[X1 ] + 2
l=1

Cn =

2
l

2
Sn =
l

l

cos
0

Therefore, if we assume

2πnt
X(t)dt,ll(k+1)/i

Xk =

l

2πnt
sin
X(t)dt.
l0Note that Fourier coeﬃcients Cn and S n are random variables because they depend on X(t).
Hence, by using (13) and (14), we can express the evaluation function (9) by the covariance of Ci or S i . (7) which
composes our evaluation function is given as follows.
# 2
$
∞
!
" 
Ci + S i 2
E Var[P̂|X(t)] =
wi E
2
i=1
1
wi {Cov(Ci , Ci ) + Cov(S i , S i )} .
2 i=1
∞

=

∞ ∞

1 
wi w j Cov Ci 2 , C j 2
4 i=1 j=1

+ 2 Cov Ci 2 , S j 2 + Cov S i 2 , S j 2 .

We assume that Ci and S i follow normal distributions
since it is diﬃcult to treat covariance between the squaresof random variables. We can provide the rationale of theapproximation that Ci and S i follow normal distributions.
By separating the integrals, we get the following equations:
2
l k=0
i−1

Ci =

2
Si =
l k=0
i−1

l(k+1)/icos

2πit
X(t)dt,
l

(16)

sin

2πit
X(t)dt.
l

(17)

lk/i
l(k+1)/i
lk/i

2
l k=0
h−1

Ci =

Similarly, the other component (8) forming the evaluation
function is as follows.
!
"
Var Var[P̂|X(t)]∞∞ Ci 2 + S i 2 C j 2 + S j 2=,
wi w j Cov
2
2
i=1 j=1(16) and (17) are the summation of the i random variables

2πit
X(t)dt,l

we can guarantee that the (16) follows a normal distribution
for suﬃciently large i (we can also guarantee the (17) follows a normal distribution similarly). Suﬃcient conditions
for target process X(t) are as follows: (1) the target process
X(t) is stationary process; (2) Variance of X(t) is finit; (3) theabsolute value of ACF of X(t) is O(t−5 ). Though we can not
apply the above approximation for small i, we can consider
that the (16) and (17) are summations of non-identically distributed h random variables with mean 0 by separating the
integrals as follows.

(15)

=

cos
lk/i

Si =

h−1


2
l k=0

l(k+1)/hcos

2πit
X(t)dt,
l

sin

2πit
X(t)dt.
llk/hl(k+1)/hlk/hThe central limit theorem for non-identically distributed andindependent random variables guarantees that the summation of random variables Xk follows a normal distribution
when the following equation hold for some δ > 0 [26].
n
E[|Xk − μk |2+δ ]lim k=0+n
,
2+δ
n→∞
k=0 νkwhere μk and νk represent mean and variance of Xk . The
above central limit theorems for dependent (but identically distributed ) random variables and non-identically distributed (but independent) random variables motivate us toconsider that (16) and (17) follow a normal distribution eventhough the explicit conditions to hold the central limit theorem for dependent and non-identically distributed randomvariables are not provided. Moreover, in Sect. 6, we will
supplement the rationale of the assumption through the simulation result.
By using the approximation, we can derive Var[Varˆ[P|X(t)]]as follows.
∞
∞ 

!
" 1
wi w j Cov Ci 2 , C j 2
Var Var[P̂|X(t)] =4 i=1 j=1

WATABE and AIDA: ON OPTIMAL MAGNITUDE OF FLUCTUATIONS IN PROBE PACKET ARRIVAL INTERVALS

3035+ 2 Cov Ci 2 , S j 2 + Cov S i 2 , S j 2
=



∞
∞ 


 
2
1
wi w j 2 Cov Ci , C j
4 i=1 j=1


2
2 
+ 4 Cov Ci , S j + 2 Cov S i , S j,

where the second equality follows from the property of the
moment of bivariate normal distributions.
Finally, if we can relate Cov(Ci , S j ), Cov(Ci , C j ) andCov(S i , S j ) to r(τ), our evaluation function can evaluate any
probing method. Calculating Cov(Ci , S j ), we have
Cov(Ci , S j )
4
= 2
l
4
= 2
l
4
= 2
l
2
= 2
l

l

l

2π j
2πi
t sin
s E [X(t)X(s)] dsdtll
− E[Ci ]E[S j ]

cos
0

0

l

l

2π j
2πi
t sin
s r(s − t)dsdt
l
l

cos
0

0
l

l−t

l

−t
−τ ,

cos

0

0

−l

2π j
2πi
t sin
(τ − t) r(τ)dτdtll

2π( j + i)
2π j
t+
τ
l
l
2π( j − i)
2π j + sint+τ dt r(τ)dτll
2π( j + i)
2 0 l,
2π j
+ 2
t+
τ
sin
l
l
l −l −τ
2π( j − i)
2π j + sint+τ dt r(τ)dτ.
llsin

Moreover, by creating two cases i = j and i  j and integrating the result, we get Cov(Ci , S j ) = 0. Similarly, we cancalculate Cov(Ci , C j ) and Cov(S i , S j ) as follows.
⎧
2
4
⎪
⎪
(i = j)⎨− ilπ rS ,i + l rC,i ,,Cov(Ci , C j ) = ⎪⎪⎩ lπ( j24−i2 ) irS ,i − jrS , j , (i  j)
⎧
2
4
⎪
⎪
(i = j)⎨ ilπ rS ,i + l rC,i ,,Cov(S i , S j ) = ⎪⎪⎩ lπ( j24−i2 ) jrS ,i − irS , j , (i  j)l

2πi
rS ,i =sin
τ r(τ)dτ,
l
0
l
2πi
τ
τ r(τ)dτ.
1 − cos
rC,i =ll
0
Substituting them into (15), we have
∞
!
" 
4
wi rC,i ,E Var[P̂|X(t)] =
l
i=1
!
"
Var Var[P̂|X(t)]
(18)
.
/
.
/
∞
∞
2
2


4
2
wi rC,i +wi rS ,i
=
l
liπ
i=1
i=1



(i2 + j2 ) rS ,i 2 + rS , j 2 − 4i jrS ,i rS , j+
16wi w j. (19)
l2 π2 (i2 − j2 )2i jHowever, the second and the third terms on the righthand side of (18) are trivial compared with the first term if
we give actual parameters to r(τ), l and m. Hence, (18) isapproximated as
/2
∞ .
!
" 
4
wi rC,i .
Var Var[P̂|X(t)] li=1
In Sect. 6, we will confirm the validity of the approximation.
Thus, the evaluation function e(σ) that corresponds to(9) is given by the following:⎧∞⎫2 ∞ .
/2
⎪
⎪
⎪
⎪
⎨ 4
⎬  4
e(σ) = ⎪
w
w
r
+
r
.
(20)
⎪
i C,i ⎪
i C,i
⎪
⎩
⎭
l
l
i=1
i=1
We can plot evaluation function e(σ) if we specify the following: measurement period l, number of probe packets m,
the ACF r(τ) of X(t), and fluctuation magnitude σ (whichis added to the timing of probe packets). This means that
we can obtain the optimal fluctuation magnitude to suit theproperties of the target network.
6.

Approximation Validity and an Evaluation Examples

In this section, we confirm the validity of our approximations through simulation, and we will show an evaluation
example. We should check the approximations that wereused to derive (20). Moreover, at the end of this section, weshow some examples of our evaluation function for the caseof M/M/1 queue measurement.
We use the queue length (i.e. the number in the system)of M/M/1 as X(t). The behavior of the M/M/1 queue is very
well studied. The mean and variance of the queue length ofan M/M/1 system are
ρ
,
1−ρ
ρ
Var[X(t)] =.
(1 − ρ)2

E[X(t)] =(21)

The ACF of the queue length of an M/M/1 system is as follows [27].
r(τ) =(μ − λ)3π

2πsin2 θ

0e−w|τ|
dθ,
w3

where

+
w = λ + μ − 2 λμ cos θ.

Furthermore, if μ = 1, we can approximate the normalized
ACF by the following simple form (see (3.7) in Ref. [28]).
r (τ) 1  −A|τ|+ e−B|τ| ,
e
2

where
A=

(1 − λ)2√ ,1+λ+ λB=(1 − λ)2√ .
1+λ− λIEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 2013

3036

Fig. 4
Fig. 3rates.

CDF of the C1 calculated through the simulation.

Normalized ACFs of M/M/1 queue process for various arrival

Therefore, by using (21), we can get the ACF of the M/M/1
queue as follows.
r(τ) 

ρr (τ).
(1 − ρ)2(22)

We show the normalized ACF for various arrival rates λ in
Fig. 3. Generally, the most important parameter that characterizes each ACF is the rate that r(t) approaches to 0.
On active measurement of delay, the probe packets obtain information of the waiting time, not the number in thesystem. Compared to the queue length case, the correlation structure of the waiting time on the M/M/1 system is
extremely complicated, and does not provide any additional
insight for our study. Thus we choose the queue length process as the target in our verification, though it does not correspond to actual measurements completely.
We discuss the validity of our approximations by using
the ACFs that are obtained from a M/M/1 queue length. To
derive (20), we used two approximations. One is a Fouriercoeﬃcient, which obeys a normal distribution, and the otheris negligible terms on the right-hand side of (18).
First, we confirm that Fourier coeﬃcients Cn and S nobey normal distributions. We already showed the analytical rationale by using the extended central limit theorem in Sect. 5. We executed an M/M/1 simulation 3000
times and calculated the CDF of the C1 through the simulation. The CDF calculated through the simulation and
the CDF of a normal distribution are displayed in Fig. 4.
The parameters we used in the simulations are as follows.
The arrival rate λ is 0.75, the service rate μ is 1.0, andthe simulation time is 50000. According to the figure, we
confirm that these distributions are corresponding to eachother. We gained similar results for Cn (n = 1, 2, . . . ). In
Sect. 5, we used the property of moment of bivariate normal distributions with the approximation, i.e. we considered Cov(Ci 2 , C j 2 ) = 2{Cov(Ci , C j )}2 and the other version of the combination of Ci and S i . To verify the approximation accuracy, we executed an M/M/1 simulation
3000 times, and computed Var[Cn 2 ] and 2{Var[Cn ]}2 directly. Note that Var[Cn 2 ] and 2{Var[Cn ]}2 are special casesof Cov(Ci 2 , C j 2 ) and 2{Cov(Ci , C j )}2 , respectively. Figure 5 displays Var[Cn 2 ] and 2{Var[Cn ]}2 through the"! simulations. From Fig. 5, we can confirm that Var Cn 2 isFig. 5

Fig. 6(18).

Comparison of Var[Cn 2 ] and 2{Var[Cn ]}2 .

Comparison of first term and other terms on the right-hand side ofclose to 2{Var[Cn ]}2 , for every n. We plotted Var[S n 2 ] and2{Var[S n ]}2 , and gained similar results.
Furthermore, we show that the second and the thirdterms on the right-hand side of (18) are negligible. By using (22), we computed the first term and other terms on theright-hand side of (18) separately. Figure 6 represents thefirst term and other terms. The parameters we used are as
follows. The arrival rate λ is 0.75, the service rate μ is 1.0,
the measurement period l is 50000, and the probing rate m/l
is 0.01. Note that the horizontal axis represents the fluctuation magnitude σ. According to the figure, it is clear thatthe eﬀects of the second and the third term are much lessthat those of the first term.
Next, we show the complementary cumulative distribution function (CDF) of the accuracy that is expressed by (6)in the case of the M/M/1 queue measurement in Fig. 7. The
parameters we used are as follows. The arrival rate λ is 0.75,
the service rate μ is 1.0, the measurement period l is 1000,
and the probing rate m/l is 0.01. We plotted for three diﬀer-

WATABE and AIDA: ON OPTIMAL MAGNITUDE OF FLUCTUATIONS IN PROBE PACKET ARRIVAL INTERVALS

3037

Fig. 7

Distribution of (6) in the case of the M/M/1 queue measurement.

Fig. 8(20).

Comparison of first term and other terms on the right-hand side ofent probing policies: periodic-probing, our probing methodwith σ = 20 and PASTA-based probing. According to thefigure, we can find that the variance Var[P̂|X(t)] in the caseof PASTA-besed probing is so large (i.e. inaccurate), andlarger variance in the case of periodic-probing occurs more
frequently compared with that in the case of σ = 20 (butthe mean of the variance in the case of periodic-probing issmaller than that of σ = 20). The result is consistent with
our discussion in Sect. 3.
Finally, we show some examples of our evaluation
function by using the ACFs that are obtained from a M/M/1
queue length. Please note that, in the rest of this section, we
will not execute any simulation. We use the ACF that is derived from a M/M/1 queue process, but our result does notdepend on any properties of M/M/1 except the ACF. Therefore, the result can be generalized to the processes that have
similar ACF structure. These examples can provide us someinsights for tuning the optimal fluctuation magnitude in actual measurements.
In Fig. 8, we display the evaluation function (20) withparameters of λ = 0.75, μ = 1.0, l = 50000, and m = 500.
We also plotted the first term of (20) (shown in the figure
as crosses) in Fig. 8. Note that the horizontal axis represents
the fluctuation magnitude σ. The first term of (20) expresses
the square of the expectation of Var[P|X(t)] (it means the expectation of accuracy). According to Fig. 8, the first term isthe smallest when σ = 0 (i.e. the case of periodic-probing).
On the other hand, our evaluation function is not the smallest because it assesses the phase-lock phenomenon by thesecond term. The evaluation function shows that the optimal value of σ is about 20 in this case.

Fig. 9 Relationship between the optimal fluctuation magnitude andprobing rate.

Fig. 10 Relationship between the optimal fluctuation magnitude andmeasurement period.

In addition, we verified the dependence of the evaluation function on each measurement parameter. First, we
confirmed the relationship between the evaluation function
and the probing rate m/l. We plot the evaluation functionof each probing rate while changing m in Fig. 9. Parameters
except m are as follows. λ = 0.75, μ = 1, and l = 50000.
We can confirm that the optimal fluctuation magnitude decreases as the probing rate increases. Since the averageprobe packet intervals decrease with increase of the probing rate, the timing of probe packet injection is randomized
with slight fluctuations when a probing rate is high. Adding
fluctuations with magnitude σ to the probe packets with arate m/l has a randomized eﬀect equivalent to adding fluctuations with magnitude σ/2 to the probe packets with arate (2m)/l. Therefore, we can avoid the phase-lock phenomenon by adding slight fluctuations when a probing rate
is high. Second, we confirmed the relation between theevaluation function and measurement period l with fixed
probing rate. Figure 10 plots the evaluation function of eachmeasurement period. Parameters except l are as follows.
λ = 0.75, μ = 1, and the probing rate is 0.01. We canconfirm that the optimal fluctuation magnitude holds steadyeven as the measurement period changes (if probing rate is
fixed).
We show the dependence of the optimal fluctuation
magnitude on traﬃc intensity to help network researchersand practitioners in designing experiments. As we mentioned above, the measurement period has no critical effect on the optimal fluctuation magnitude. Therefore, we
can cover all cases if we consider the arrival rate and the

IEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 2013

3038

Fig. 11 Ratio of the optimal fluctuation magnitude to the average probe
intervals is less than 20%.

probing rate. In Fig. 11, we display the ratio of the optimal
fluctuation magnitude to the average probe intervals l/m foreach arrival rate. Namely, we plot mσ∗ /l where σ∗ is the
optimal fluctuation magnitude. Note that the probing ratemeans the ratio of probe packet traﬃc to the regular traﬃc,since the service rate is fixed at 1 in our example. We plotted a wide variety of values of arrival rate in terms of the
speed that ACF r(τ) approaches to 0 (in Fig. 3, we showed
the ACFs that correspond to the values of arrival rate wedisplayed). According to the Fig. 11, we can find that allof points are less than 20% though ACFs r(τ) are extremely
various. Practically, it is diﬃcult to gain the exact knowledge of the ACF without a measurement. However, ourresult suggests that fluctuation magnitude corresponding to
20% is enough to avoid phase-lock phenomenon for a wide
variety of ACFs.
We should take into account intrusiveness when wechoose the probing rate m/l. High probing rate leads anaccurate estimation normally though excessive injections ofprobe packets lead a deterioration of accuracy. In this paper, we present a method to specify the optimal fluctuation
magnitude of probe packet intervals under the non-intrusive
context (the load of the probe packets is ignored in the nonintrusive context). In real measurement, we must design
experiments in which impact of the probe packet load isinsignificant. Reference [10] clarified the relationship between an asymptotic variance and ACF of target process,and discussed the optimal probing rate that keeps the accuracy deterioration insignificant. According to the results in
Ref. [10], in M/M/1 model with the arrival rate λ and the service rate μ, an asymptotic variance s2 (λ, μ, p) is given by thefollowing if we inject probe packet with probing rate pλ.
s2 (λ, μ, p) 

ρ2
4ρ3
+
p
,
(1 − ρ)2(1 − ρ)4(23)

where ρ = (1 + p)λ/μ. The optimal probing rate is pλ thatminimizes (23). p means the ratio of the probe stream to all
streams, and the p that gives optimal probing rate provides
insight to choose probing rate m/l.

examples based on the ACF of M/M/1 queue length process, and obtained some insights regarding the relationship among ACF, measurement period, the number of probe
packets, and the optimal fluctuation magnitude. It is not thecontention of this paper that the M/M/1 model is a goodmodel for the modern networks. Of course, M/M/1 model
is fundamental but unreal model and the modern networks
are not well-modeled as it. However, the optimal fluctuation
magnitude that specified by our method does not depend on
any properties of M/M/1 except the ACF. Therefore, we obtain same results if the shape of ACF of process that we wantto measure is similar to that of M/M/1 queue length processeven if M/M/1 does not exactly model the inside of the target network (e.g. behavior of packet, network topology, andqueueing, etc.).
The ACFs of processes that we are targeting are monotonically decreasing and convex functions on the interval[0, ∞) though our method that presented in Sect. 5 can apply to a process with any ACF. Monotonically decreasing
and convex ACFs of delay/loss processes are well-motivatedby analysis of real Internet traﬃc [12]. The most importantparameter to characterize these ACFs is decreasing rate forτ → ∞.
ACF (22) of M/M/1 queue length process is simple
function that satisfies above two conditions, and it can havevarious decay rate by changing parameter ρ as shown in
Fig. 3. We can consider that the family of ACFs (22) thatare based on M/M/1 queue length process represents various
ACFs that we are targeting since target ACFs are characterized by decay rate.
We can expect that the insights that we obtained in
Sect. 6 can be utilized when we design experiments for measurements of delay/loss processes whose ACF is monotonically decreasing and convex. In Sect. 6, we gained two main
insights: (1) the optimal fluctuation magnitude has robustness to a change of measurement period l; (2) the fluctuation
magnitude of 20% of the average probe interval is enough to
avoid phase-lock phenomenon for various probing rate and
ACFs that have a wide variety of decay rate. As we mentioned above, it is diﬃcult to gain the exact knowledge of
the ACF. However, these insights can apply to various target
processes that have similar ACF structure even if we cannot
gain the knowledge of the ACF. Therefore, we can design ameasurement on the safe side by setting the fluctuation magnitude to 20% of probe intervals (needless to say, we can design experiments optimally if we can gain the knowledge of
the ACF). In addition to above insights, we understand thatthe results of validation of approximation that the second
and the third terms on the right-hand side of (18) are negligible can also apply to various target processes that have
similar ACF structure.
8.

7.

Conclusion

Generality of the Result

We discuss generality of the result of M/M/1 model presented in Sect. 6. In Sect. 6, we presented the evaluation

In this paper, we analysed the optimal fluctuation magnitude
that should be added to the timing of probe packets. For the
analysis, we introduced a probing policy that randomly per-

WATABE and AIDA: ON OPTIMAL MAGNITUDE OF FLUCTUATIONS IN PROBE PACKET ARRIVAL INTERVALS

3039

turbs the timing of probe packets by using a normal distribution. Moreover, we defined an evaluation function that canwell assess the phase-lock phenomenon, and we provided amethod that can specify the optimal fluctuation magnitude
by using the ACF of the target process that we want to measure.
We confirmed the validity of our method by applying
it to M/M/1 queue measurement. Furthermore, we showedthat the probing rate greatly aﬀects the optimal fluctuation
magnitude. The measurement period is not a critical parameter. Through our evaluation examples, we were able to findthat a fluctuation magnitude of 20% of the average probe interval is enough to avoid the phase-lock phenomenon for awide variety of ACFs.
In the future, we will validate the method in detail including verification on an actual network. To implement our
probing policy as an actual measurement method, we needto know the ACF of the target process (delay or loss processetc.) because it is needed to specify the optimal probing policy. Thus we will determine how to estimate the propertiesof the target network from past measurement data.
Acknowledgment
This work was supported by JSPS Grant-in-Aid for JSPS
Fellows Grant Number 24 · 3184.
References[1] G. Almes, S. Kalidindi, and M.J. Zekauskas, “A one-way delay metric for IPPM,” RFC2679, 1999.
[2] G. Almes, S. Kalidindi, and M.J. Zekauskas, “A one-way packet loss
metric for IPPM,” RFC2680, 1999.
[3] V. Paxson, G. Almes, J. Mahdavi, and M. Mathis, “Framework for
IP performance metrics,” RFC2330, 1998.
[4] J. Bolot, “Characterizing end-to-end packet delay and loss in theInternet,” High Speed Networks, vol.2, no.3, pp.289–298, 1993.
[5] V. Paxson, “End-to-end Internet packet dynamics,” ACM SIGCOMM Computer Communication Review, vol.27, no.4, pp.139–
152, 1997.
[6] C. Dovrolis, P. Ramanathan, and D. Moore, “Packet-dispersion techniques and a capacity-estimation methodology,” IEEE/ACM Trans.
Netw., vol.12, no.6, pp.963–977, 2004.
[7] R. Kapoor, L.J. Chen, A. Nandan, M. Gerla, and M.Y. Sanadidi,“CapProbe: A simple and accurate capacity estimation techniquefor wired and wireless environments,” ACM SIGCOMM Computer
Communication Review, vol.34, no.4, pp.67–78, 2004.
[8] M. Jain and C. Dovrolis, “End-to-end available bandwidth: Measurement methodology, dynamics, and relation with TCP throughput,” IEEE/ACM Trans. Netw., vol.11, no.4, pp.537–549, 2003.
[9] V.J. Ribeiro, R.H. Riedi, R.G. Baraniuk, J. Navratil, and L. Cottrell,“pathChirp: Eﬃcient available bandwidth estimation for network
paths,” Passive and Active Measurement Conference (PAM 2003)
Workshop, San Diego, CA, USA, April 2003.
[10] M. Roughan, “Fundamental bounds on the accuracy of network performance measurements,” ACM SIGMETRICS Performance Evaluation Review, vol.33, no.1, pp.253–264, 2005.
[11] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “The role of
PASTA in network measurement,” ACM SIGCOMM Computer
Communication Review, vol.36, no.4, pp.231–242, 2006.
[12] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “On optimal probing for delay and loss measurement,” ACM Internet Measurement

Conference (IMC 2007), pp.291–302, San Diego, CA, USA, Oct.
2007.
[13] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “Probing for loss:
The case against probe trains,” IEEE Commun. Lett., vol.15, no.5,
pp.590–592, 2011.
[14] J. Sommers, P. Barford, N. Duﬃeld, and A. Ron, “Improving accuracy in end-to-end packet loss measurement,” ACM SIGCOMM
Computer Communication Review, vol.35, no.4, p.157, Oct. 2005.
[15] M. Hasib, J. Schormans, and T. Timotijevic, “Accuracy of packet
loss monitoring over networked CPE,” IET Commun., vol.1, no.3,
pp.507–513, 2007.
[16] J. Sommers, P. Barford, N. Duﬃeld, and A. Ron, “A geometric approach to improving active packet loss measurement,” IEEE/ACM
Trans. Netw., vol.16, no.2, pp.307–320, April 2008.
[17] B.M. Parker, S.G. Gilmour, and J. Schormans, “Measurement ofpacket loss probability by optimal design of packet probing experiments,” IET Commun., vol.3, no.6, pp.979–991, 2009.
[18] R.W. Wolﬀ, “Poisson arrivals see time averages,” Operations Research, vol.30, no.2, pp.223–231, 1982.
[19] V. Raisanen, G. Grotefeld, and A. Morton, “Network performancemeasurement with periodic streams,” RFC3432, 2002.
[20] M. Roughan, “A comparison of poisson and uniform sampling foractive measurements,” IEEE J. Sel. Areas Commun., vol.24, no.12,
pp.2299–2312, 2006.
[21] S. Floyd and V. Jacobson, “Traﬃc phase eﬀects in packet-switchedgateways,” ACM SIGCOMM Computer Communication Review,
vol.21, no.2, pp.26–42, 1991.
[22] S. Floyd and V. Jacobson, “The synchronization of periodic routing
messages,” IEEE/ACM Trans. Netw., vol.2, no.2, pp.122–136, 2002.
[23] I.S. Gradshteyn, I.M. Ryzhik, A. Jeﬀrey, and D. Zwillinger, Tableof Integrals, Series, and Products, Seventh ed., ch. 12, p.1066, Academic press, New York, USA, 1980.
[24] I.S. Gradshteyn, I.M. Ryzhik, A. Jeﬀrey, and D. Zwillinger, Table ofIntegrals, Series, and Products, Seventh ed., ch. 3, p.488, Academicpress, New York, USA, 1980.
[25] H. Stark and F.B. Tuteur, Modern Electrical Communications: Theory and Systems, pp.421–422, Prentice Hall, 1979.
[26] P. Billingsley, Probability and Measure, ch. 5, pp.366–382, Jhon Wiley & Sons, 1986.
[27] P.M. Morse, “Stochastic properties of waiting lines,” Operations Research Society of America, vol.3, no.3, pp.255–261, 1955.
[28] J. Abate and W. Whitt, “The correlation functions of RBM andM/M/1,” Stochastic Models, vol.4, no.2, pp.315–359, 1988.

Appendix
We prove that the probability that at least one packet of mprobe packets injects in [t, t + Δt) is (mΔt)/l for any t (0 ≤t < l) when we inject the probe packets at {T i } given by (10).
Proof. The probability that ith packet is injected in infinitesimal diﬀerence [t, t + Δt) (0 ≤ t < l) under the condition
S = s is∞l(i − 1)Δt ·−s ,pnorm t + kl −mk=−∞where pnorm (t) denotes a pdf of normal distribution with average 0 and standard deviation σ. Then, the probability that
one of packet of m probe packets is injected in [t, t + Δt)
under the condition S = s is∞m l(i − 1)Δt ·−s .
pnorm t + kl −mi=1 k=−∞

IEICE TRANS. COMMUN., VOL.E96–B, NO.12 DECEMBER 2013

3040

Therefore, since S follows a uniform distribution U(0, l/m),
the probability that one of packet is injected in [t, t + Δt) is
as follow.
m
Δt ·
l

l
m

0

∞
m 

i=1 k=−∞∞l 

pnorm t + kl −l(i − 1)
− s dsml(i − 1)m
− s dspnorm t + kl −l 0 k=−∞
mm= Δt · .
l= Δt ·



Kohei Watabe
received his B.E. and M.E.
degrees in Engineering from Tokyo Metropolitan University, Tokyo, Japan, in 2009 and 2011.
He has been a graduate student of the Graduate
School of Information Science and Technology,
Osaka University since April 2011. He has beena JSPS research fellow (DC2) since April 2012.
He is a student member of the IEEE.

Masaki Aida
received the B.S. degreein Physics and M.S. degree in Atomic Physics
from St. Paul’s University, Tokyo, Japan, in
1987 and 1989, respectively, and received the
Ph.D. in Telecommunications Engineering fromthe University of Tokyo, Japan, in 1999. After joining NTT Laboratories in April 1989, hehas been engaged in research on traﬃc issues incomputer communication networks. From April
2005 to March 2007, he was an Associate Professor at the Faculty of System Design, Tokyo
Metropolitan University. He has been a Professor of the Graduate Schoolof System Design, Tokyo Metropolitan University since April 2007. Hereceived the Best Tutorial Paper Award of IEICE Communications Society
in 2013. Prof. Aida is a member of the IEEE, IEICE, and the Operations
Research Society of Japan.