JULY 3 DEADLINE

Tunnicliffe_et_al-2009-International_Journal_of_Communication_Systems.pdf

Home >Information Systems homework help >JULY 3 DEADLINE

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS Int. J. Commun. Syst. 2009; 22:651–669 Published online 8 December 2008 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/dac.986

An approximate stochastic analysis of the packet-pair probing technique for available bandwidth estimation

Martin J. Tunnicliffe∗,† and Maria Winnett

Faculty of Computing, Information Systems and Mathematics, Kingston University, Kingston-on-Thames, Surrey KT1 2EE, U.K.

SUMMARY

The packet-pair probing algorithm for network-bandwidth estimation is examined and an approximate model is proposed for predicting its behaviour. The model replaces the Poisson arrival process with a Gaussian distribution and resolves the queue-size profile into two separate components: A transient component representing the buffer-emptying process and an equilibrium component representing the return to steady-state behaviour. Comparison with discrete-event simulation results shows that the model is accurate in single-hop paths when utilization is �70% when the cross-traffic packets are � 12 the size of the probe packets. When extended to two-hop paths, the model remains accurate for smaller cross-traffic packets (� 110 − 15 the probe-packet size). Copyright q 2008 John Wiley & Sons, Ltd.

Received 26 September 2007; Revised 19 September 2008; Accepted 20 October 2008

KEY WORDS: available bandwidth; bandwidth measurement; queuing dynamics; network modelling

1. INTRODUCTION

The term available bandwidth refers to the unused portion of a network-path’s capacity which new connections may utilize without taking bandwidth from the existing cross-traffic [1]. Reliable estimates of effective bandwidth are useful to network clients who may require a minimum bandwidth to support delay-sensitive multimedia applications, and to administrators for achieving optimal network configurations [2].

A network path typically consists of several links (or hops), each with its own capacity. The available bandwidth of the entire path is dictated by that of the tight-link, the link with the smallest available bandwidth. Available bandwidth a is related to tight-link capacity l, utilization � and

∗Correspondence to: Martin J. Tunnicliffe, Faculty of Computing, Information Systems and Mathematics, Kingston University, Kingston-on-Thames, Surrey KT1 2EE, U.K.

†E-mail: M.J.Tunnicliffe@king.ac.uk

652 M. J. TUNNICLIFFE AND M. WINNETT

cross-traffic c by the formula

a =l −c =l ·(1−�) (1) where (1−�) is the idle-rate, the ratio of time during which the link is inactive. Some bandwidth- probing algorithms determine a by multiplying l by the idle rate, which can be inferred from the delay distribution of probe packets [3] or from information passed from the MAC layer [4]. Though accurate for links in isolation, these techniques are problematic in wider network settings [4].

An alternative approach is typified by the packet-pair technique [5]. This belongs to a family of algorithms in which short sequences of evenly spaced probe packets are sent through the monitored path and increases in their temporal separation (or dispersion) are used to estimate the path’s properties. The packet sequences (or pairs) are widely separated such that the behaviour of each is unaffected by any of its predecessors and the disturbance to the network performance is minimal.

An advantage of the packet-pair technique is that it requires no prior knowledge of link capacity, which together with the effective bandwidth can (in principle) be inferred from the measured data. However, this rests upon certain assumptions concerning network behaviour; namely that packet scheduling is first-in–first-out (FIFO), that the raw bandwidth is constant and well-defined and that the bandwidth seen by discrete packet pairs is identical to that enjoyed by sustained streams. None of these assumptions is universally valid in wireless and broadband access networks where methods based on the idle-rate produce more accurate results [3, 4].

Nevertheless, the packet-pair algorithm is still valuable in conventional wired networks of switches and routers. Though it has been widely investigated, much of the previous work ignores the finite granularity of the cross-traffic that is treated as a continuous ‘fluid’. While this is approximately valid under certain conditions, it can give rise to a ‘probing bias’ [6] that distorts the bandwidth estimate. Attempts to analyse and eliminate this bias have tended to be quite complex (e.g. [7]) even when simplifying assumptions are made.

In the present paper we develop a simpler and more intuitive model, based partly on an empirical study of simulation data. The analysis mostly assumes a single-hop topology, though the extension to multi-hop topologies is also investigated. Simulations were performed using a purpose-written class-library (originally created for the work in [8]) that allows FIFO queuing nodes to be connected in arbitrary configurations and their status to be monitored using ‘virtual’ (zero-size) packets. All the C++ classes are available online and can be downloaded from http://staffnet.king.ac.uk/∼ku12881/netclasses/.

2. PACKET-PAIR PROBING AND THE FLUID MODEL

2.1. The fluid approximation

The use of hypothetical fluids to approximate discrete data-flows has quite a long history. Essen- tially, individual packet arrivals are ignored in favour of their average arrival rate which is treated as a continuous variable. (Alternatively the discrete packets could be considered infinitesimally small, thus constituting a continuous ‘fluid’.) This simplifies the mathematics, accelerating simu- lation speed [9] and bringing complex phenomena (such as TCP-flows [10]) within the scope of analysis. However, the disregard for individual packet behaviour sometimes introduces significant errors, as will shortly be demonstrated.

PACKET-PAIR PROBING TECHNIQUE 653

Figure 1. Interaction of fluidic traffic in a link of finite capacity l bits/s: (a) the offered probe rate r bits/s is reduced to a measured rate m bits/s by its passage through the link and (b) the ‘dispersion ratio’ r/m is equal to 1 when there is no congestion (r <a =l −c) but increases linearly when the

available bandwidth is exceeded.

As mentioned before, available bandwidth is measured by injecting probe packets into a path and observing their behaviour. The probe-packets’ response can be analysed using three different models:

Model 1: The fluid approximation is applied to both the probe-traffic and the cross-traffic. (This was the approach originally used by Melander et al. [5].)

Model 2: The probe-traffic is considered discrete, while the cross-traffic is assumed to be fluidic. Model 3: The probe-traffic and cross-traffic are both considered to be composed of discrete

packets.

Models 1 and 2 are simple and are dealt with in the remainder of this section. Model 3 is more problematic and forms the main thrust of this paper.

2.2. Single-hop network paths

During a probing event, packets are offered at a rate r bits/s and received at a measured rate m bits/s. Under the assumptions of Model 1, if the link capacity is l bits/s and the cross-traffic is cbits/s (Figure 1(a)), then the following relationship should hold:

m = ⎧⎨ ⎩ r, r +c�l l · r r +c r, r +c>l

(2)

i.e. packets are carried frictionlessly unless the aggregate arrival rate exceeds the link capacity, in which case the bandwidth is shared proportionally between the competing streams. (This assumes a policy of proportional fair queuing.) By combining Equations (1) and (2) we obtain:

m =

⎧⎪⎨ ⎪⎩ 1, r�a 1

l r +

( 1− a

) , r>a

(3)

Thus, a can be detected as a ‘knee’ in the graph of r/m vs r, and l can be determined from the slope for r>a (Figure 1(b)).

Model 2 requires that probe-packet arrivals be considered discrete events. The packet-pair technique employs sequences of just two probe packets spaced �in seconds apart, such that the offered rate r = Sp/�in (where Sp is the probe-packet size in bits). If the same two packets arrive

654 M. J. TUNNICLIFFE AND M. WINNETT

�out seconds apart at the network output, then the measured rate m = Sp/�out and r/m = �out/�in. This is the dispersion ratio, the factor by which the packets’ temporal separation is increased by the link.

Figure 2(a) shows the queue-size profile during the processing of a packet pair: If the cross- traffic packets are much smaller than the probe packets (the fluid assumption) then they are served almost immediately on arrival and the equilibrium queue size is practically zero. If probe packet #1 arrives at time t =0, the queue suddenly acquires Sp bits, which are subsequently processed at a rate l bits/s and the packet completes service when t = Sp/l seconds. Meanwhile, cross- traffic arrives at a rate cbits/s such that at time t seconds the buffer contains n(t) =max(Sp −(l − c)t,0) bits. If Packet #2 arrives at t = �in seconds, its service time must be (n(�in)+ Sp)/l and therefore

Sp l

+�out = n(�in)+ Sp

l +�in (4)

Substituting n(�in) =max(Sp −(l −c)�in,0) and re-arranging yields �out �in

=max ( 1

Sp �in

+ c l ,1

) (5)

which (remembering that r = Sp/�in, r/m = �out/�in and c =l −a) is identical to Equation (3). Models 1 and 2 are therefore mathematically equivalent and will be collectively referred to as the ‘fluid approximation’.

Figure 3(a) shows the results of a simulated packet-pair probing of a single-hop path. (Probe packet size 500 bytes and cross-traffic packet size Sc =1byte‡ were used to justify the fluid approx- imation.) Least-square analysis of the upper portion of the graph yields link capacity and available bandwidth estimates accurate to within 1% of their true values.

2.3. Multiple-hop network paths

While the results of Figure 3(a) were obtained using a single link in isolation, a real network path may have two or more congestible links, each with its own available bandwidth. Consider the path A–B in Figure 4(a): Node 1 forwards data at l1 bits/s and Node 2 at l2 bits/s. Node 1 has the lowest link capacity (l1 =1Mbit/s) and is termed the narrow-link of the path. However, Node 2 carries c2 = 1.5Mbit/s cross-traffic so its available bandwidth a2 is only 500kbit/s (compared with 800kbit/s at Node 1). Node 2 is therefore the tight-link, which dictates the overall effective bandwidth.

In a multi-hop path, each congestible link may generate its own characteristic slope-change in the �out/�in vs r curve. Park et al. [7] suggested that the characteristics of any link downstream of the tight-link will be unobservable since the probe-packet separation is too wide to be further expanded. However, this is not necessarily true if the tight-link capacity is greater than the available bandwidth of downstream links. Melander et al. [5] used this principle to analyse multi-link paths by iterative application of Equation (2): Using the notation employed in Figure 4, the rate offered

‡The simulation software is not subject to the constraints of TCP/IP, whose packet size is typically limited to 46–1500 bytes by the Ethernet protocol.

PACKET-PAIR PROBING TECHNIQUE 655

Figure 2. Queue-size profiles during a packet-pair probing event. Packet #1 creates a disturbance in the mean queue size which decays over time. The remnant is sensed in terms of the additional

time taken to service Packet #2: (a) fluid cross-traffic and (b) discrete cross-traffic.

to Node 2 (when Node 1 is congested) is l1r/(r +c1), which is potentially capable of exceeding a2. If Node 1 (which lies closer to probe-source than Node 2) is the tight-link, the model becomes:

�out �in

⎧⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎩

1, r�a1 1

l1 r +

( 1− a1

) , a1<r�a2

( 1

l1 + 1 l2

− a2 l1l2

) r +

( 1− a1

)( 1− a2

) , r>a2

l1 −a1 l1 −a2

(6)

656 M. J. TUNNICLIFFE AND M. WINNETT

Figure 3. Simulated dispersion-rate profiles obtained by probing (a) a single-hop and (b) a two-hop path under near-fluidic conditions (500 byte probe packets with 1 byte cross-traffic). The broken lines indicate

the fluid predictions for the different domains of Equations (3) and (7).

PACKET-PAIR PROBING TECHNIQUE 657

Figure 4. Two-hop network paths: (a) largest surplus first (LSF) Node 2 is the tight-link and (b) shortest surplus first (SSF) Node 1 is the tight-link.

The assumption that a2>a1 (called ‘smallest surplus first’ or SSF) [5] implies that the second slope change occurs at a rate higher than a2, which is clearly the situation in Figure 4(b). However, if Node 2 is the tight-link then it congests before Node 1 and the model becomes:

�out �in

⎧⎪⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎪⎩

1, r�a2 1

l2 r +

( 1− a2

) , a2<r�a1

( 1

l1 + 1 l2

− a2 l1l2

) r +

( 1− a1

)( 1− a2

) , r>a1

(7)

which is the situation illustrated in Figure 4(a). We shall call this the LSF or ‘largest surplus first’ model.

Figure 3(b) compares the results of a simulated probing of the LSF (Figure 4(a)) network with the predictions of Equation (7), showing close agreement within the three rate domains for near-fluid traffic (Sc =0.002Sp). However, without any knowledge of the network configuration, the data could just as easily be interpreted in terms of the SSF model, in which case the topology shown in Figure 4(b) would be inferred. (This network, when simulated under near-fluidic conditions, produces results almost identical to those of Figure 4(a).)

Melander’s solution to this ambiguity was always to assume the SSF configuration [5]. This produces worst-case results, since the available bandwidths of the upper bottlenecks tend to be lower than those inferred from any alternative model. Fortunately the most important inference, namely the tight-link bandwidth, is the same under both models. Though the model can be extended to include any number of congestible links, the current paper will be limited to one and two-hop scenarios.

2.4. Limitations of the fluid model

The fluid approximation requires that cross-traffic packets be far smaller than the probe packets; if this is not the case, a greater-than-predicted dispersion is observed when r ≈a. This effect,

658 M. J. TUNNICLIFFE AND M. WINNETT

Figure 5. Simulated dispersion-rate profiles for a single-hop path carrying 1 and 100 byte cross-traffic packets, compared with the corresponding fluid approximation. (Each data point represents the average of 500 measurements.) While the 1 byte results are almost identical to the fluid model, the 100 byte results show a consistent upward bias when the offered rate is close to the available bandwidth (1 Mbit/s). The inset shows the corresponding average queue-size profiles during the passage of a probe packet. (Each

graph represents the average of 1000 simulations.)

sometimes called ‘probing bias’ [6], is visible in the simulation results in Figure 5: Applying linear regression to such data tends to produce an overestimation of l and an underestimation of a.

To understand the origin of the probing bias it is necessary to consider how Model 3 (the ‘true’ scenario of discrete probe-traffic and discrete cross-traffic) differs from the fluid approximation. Firstly, discrete cross-traffic packets take a finite time to be serviced, so finite queues form even when r<a. This gives rise to an average ‘background’ or equilibrium queue-size neq, which raises the zero reference level of the queue-size profile (Figure 2(b)). Secondly, since traffic arrives in discrete randomly timed packages, the queue-size profile n(t) acquires a stochastic variability and it is necessary to talk in terms of the mean queue-size profile n̄(t) (which would be observed over many repeated probing events), together with a corresponding variance function. Thirdly, this variance creates a finite empty-queue probability once the probe packet has been serviced, slowing the mean emptying rate as the queue approaches equilibrium and thus giving rise to the concave n̄(t) profile shown in the inset of Figure 5. This makes the service time of the second packet greater than it would have been under the linear (fluid) model, increasing the rate of dispersion.

Probabilistic models have provided more accurate predictions of the queuing response under discrete traffic: Park et al. [7] used the transient M/D/c model developed by Franx [11] to predict the evolution of the state probability vector and hence the mean expected queue size. This model assumes that cross-traffic arrival is governed by a stationary Poisson process, though the introduction of equivalent-rate Pareto ON–OFF traffic produced no major changes in system behaviour. Though highly accurate, the model is both complex and computationally intensive.

PACKET-PAIR PROBING TECHNIQUE 659

In the current paper we develop a simpler model of the queuing dynamics and apply it to the analysis of the packet-pair probing event. The model, which includes both intuitive reasoning and empirical observation, agrees quite closely with simulation data under moderate (�70%) utilization when cross-traffic packets are relatively small (Sc� 12 Sp). We believe that with its relative simplicity, the model will be readily extendible to more complex probing situations.

3. DISCRETE QUEUING DYNAMICS

3.1. Discrete cross-traffic model

If a queue contains n0 bits at time t =0 then at any time t�0 there will be max(n0 −lt,0) of the original n0 bits remaining, while a number of new bits may have arrived. If we assume (along with Park et al. [7]) that the packet inter-arrival time is exponentially distributed and that all packets contain exactly Sc bits, then the number of arrived packets must be Poisson distributed with a mean of ct/Sc and a standard deviation of

√ ct/Sc. Therefore, the number of arriving bits must have a

mean value ct and a standard deviation √ cSct. Before there is any significant probability of the

queue becoming empty, the mean queue length is given by n0 −(l −c)t with standard deviation√ cSct, and can be approximated by a Gaussian distribution:

ft (n) = 1√

2�cSct exp

[ − (n −n0 +(l −c)t)

2cSct

] (8)

However, this only applies for n�0 (since the queue cannot empty below zero) and the contribution to the mean occupancy from the transient queue-emptying phase is given by:

n̄trans(t) = ∫ ∞ 0

nft (n)dn = √ cSct

2� exp

[ − (n0 −(l −c)t)

2cSct

]

+n0 −(l −c)t 2

[ 1+erf

( n0 −(l −c)t√

2cSct

)] (9)

The n<0 portion of the Gaussian distribution (Equation (8)) represents the set of possibilities in which the queue has already completely emptied and is recovering its equilibrium behaviour (see Figure 6). The latter may be modelled as a standard M/G/1 queuing system, for which the first and second moments of the waiting time w are given by

E(w) = �E(t 2 s )

2(1−�) and E(w 2 ) = �E(t

2 s )

(1−�) E(w)+ �E(t3s )

3(1−�) where � =c/Sc is the arrival rate of packets per second, ts is the packet service time and � =c/l is the utilization [12]. Since for an M/D/1 system the packet service times are all equal (ts = Sc/l), the mean equilibrium queue size is

neq =l · E(w) = cSc

2(l −c) (10)

660 M. J. TUNNICLIFFE AND M. WINNETT

Figure 6. Schematic representation of the Gaussian queue-size pdf’s during queue-emptying, showing the transient and equilibrium components. The equilibrium time teq represents the effective time-lag between

the queue becoming empty and returning to its equilibrium mean occupancy.

Figure 7. Effective equilibrium time (transition time for the step approximation, see inset) as a function of utilization. Results were obtained using three combinations of packet size and server rate. Each data

point represents the mean of five runs of 1000 independent simulations.

PACKET-PAIR PROBING TECHNIQUE 661

and the standard deviation

�eq = √ l2E(w2)−n2eq =neq

√ 1+ 4

[ l

c −1 ]

(11)

Since equilibrium is not achieved at the instant the queue becomes empty we make a further assumption; namely that the equilibrium queue size is restored abruptly teq seconds (the effective equilibrium time) after n reaches zero. (In other words, n(�) =neq · H(�−teq) where � is the time since the queue became empty and H(t) is the unit step function.) Thus, the contribution to mean occupancy from equilibrium recovery for t>teq is given by:

n̄eq(t) =neq ∫ 0

−∞ ft−teq (n)dn =

neq 2

[ 1−erf

( n0 −(l −c)(t −teq)√

2cSc(t −teq)

)] (12)

and the overall mean queue-occupancy becomes:

n̄(t) = { n̄trans(t), t�teq n̄trans(t)+n̄eq(t), t>teq

(13)

Of course, the transition between the empty and equilibrium conditions is in reality gradual; replacing n̄(t) with an abrupt-step function (see inset in Figure 7) is equivalent to replacing its first derivative n̄′(t) with a delta function positioned at its centroid. Thus, we define the effective equilibrium time as follows:

teq = 1

neq

∫ ∞ 0

t ·n̄′(t)dt = lim T →∞

[ T − 1

neq

∫ T 0

n̄(t)dt

] (14)

Profiles for n̄(t) were obtained for various combinations of l and Sc by averaging the results of 1000 independent simulations. To determine teq, the integral in Equation (14) was computed between zero and the earliest instant at which n̄(t) exceeded neq. Figure 7 shows the results normalized in terms of the corresponding numbers of packet service-times g =teq/ts, which is a function of utilization only. Thus

teq = Sc l

·g(�) where g(�) = 0.333 (1−�)2.19 (15)

where the expression for g(t) was obtained empirically from the data.

3.2. Response to a probe-packet arrival

Suppose that the first probing packet (arriving at time t =0) encounters the queue in its equilibrium condition, such that n0 has a mean value (Sp +neq) and a variance �2eq. Equations (9) and (12)

662 M. J. TUNNICLIFFE AND M. WINNETT

can now be rewritten:

n̄trans(t) = √ cSct +�2eq

2� exp

[ − (Sp +neq −(l −c)t)

2(cSct +�2eq)

]

+ Sp +neq −(l −c)t 2

⎡ ⎣1+erf

⎛ ⎝Sp +neq −(l −c)t√

2(cSct +�2eq)

⎞ ⎠ ⎤ ⎦ (16)

n̄eq(t) = neq 2

⎡ ⎣1−erf

⎛ ⎝Sp +neq −(l −c)(t −teq)√

2(cSc(t −teq)+�2eq)

⎞ ⎠ ⎤ ⎦ (17)

which may be inserted into Equation (13) to obtain the overall mean profile n̄(t). We have assumed of course that the convolution of the Poisson arrival distribution and the equilibrium occupancy distribution are approximately Gaussian and that the stepwise model for equilibrium recovery is valid under all loading conditions: The validity of these assumptions was tested a posteriori by comparing the model’s predictions with simulation data: Figure 8 shows that the model loses accuracy under very heavy utilization, and that the error increases as Sc approaches the magnitude of Sp. The fact that n̄(t) is under-predicted in regions where according to the model equilibrium recovery should not yet have begun (the onset of equilibrium-recovery is visible as a slight ‘glitch’ in the curve) suggests that the abrupt-step approximation is partly responsible for the error. However, for all Sc� 12 Sp and ��0.7 the model agrees very closely with the simulation data.

4. DISCRETE PACKET-PAIR MODEL: SINGLE-HOP SCENARIO

We return now to the discrete-traffic packet-pair mechanism illustrated in Figure 2(b): Packets #1 and #2 arrive �in seconds apart, and the time separation between their departures �out is measured. It is clear from the figure that

neq + Sp l

+�out = �in + n̄(�in)+ Sp

l (18)

which yields the following expression for the packet dispersion as a function of the probing rate r = Sp/�in:

�out �in

=1+ r Spl

{ n̄

( Sp r

) −neq

} (19)

where the function n̄ is obtained by substituting Equations (16) and (17) into Equation (13). Figure 9 compares simulation data obtained using 500 byte probe packets with 250 and 100 byte cross-traffic with the predictions of Equation (19) and the fluid approximation. For the 100 byte data, the discrete model is near perfect, and converges with the fluid model for both large and small r. For the 250 byte data the discrete model is mostly accurate but fails to converge with the fluid model under large r. The reasons for this will be addressed below.

PACKET-PAIR PROBING TECHNIQUE 663

Figure 8. Simulated mean queue-size profiles observed during the passage of a 500 byte probe packet, using (a) 250 byte (Sc = 12 Sp) and (b) 100 byte (Sc = 15 Sp) cross-traffic, compared with the model’s predictions.

(Each data-point represents the average of 1000 simulations.)

664 M. J. TUNNICLIFFE AND M. WINNETT

Figure 9. Comparison of analytical and simulated dispersion ratios using available bandwidth 0.3 and 0.7 Mbit/s (70 and 30% utilizations, respectively) and cross-traffic packets (a) one half (Sc = 12 Sp) and (b) one-fifth the size of the probe packets (Sc = 15 Sp). Each data point represents the average of five runs of 500 packet pairs each, and the error bars indicate ±1.96 times the

standard mean error (95% confidence interval).

PACKET-PAIR PROBING TECHNIQUE 665

4.1. The limit as Sc/Sp →0 As Sc becomes infinitesimal relative to Sp,neq, �eq,teq →0 (Equations (10), (11), (15)) and Equation (13) becomes

n(t) = { Sp −(l −c)t, t<Sp/(l −c) 0, t�Sp/(l −c)

(20)

(since limx→±∞[erf(x)] = ±1). Under these conditions it is easy to show that

�out �in

⎧⎪⎨ ⎪⎩ 1+ r

Spl

{ Sp −(l −c)

Sp r

} = r

l + c

l , r>l −c

1, r�l −c (21)

which is identical to Equations (3) and (5); hence, the discrete and fluid models converge (as expected) under near-fluid conditions.

4.2. The limit as r →0 This corresponds to the limit as t → ∞ in Equation (13), which requires n̄(t) →n̄eq(t) →neq (Equation (17)) and hence �out/�in →1 (Equation (19)). This is consistent with Figure 9, which shows the discrete and fluid models converging under low probing rates.

4.3. The limit as r → ∞ This corresponds to the limit as t →0 in Equation (13), which requires that n̄(t) be identical to n̄trans(t) (Equation (16)). For small Sc (� 15 Sp) this is almost undistinguishable from the fluidic queue-size profile Sp +neq −(l −c)t, and hence the discrete and fluid models converge (Figure 9(b)). However, Figure 9(a) suggests that the discrete and fluid models do not converge exactly for larger Sc (≈ 12 Sp), under which conditions the queue-size profile predicted by Equa- tion (16) has a steeper slope than that of the fluid approximation causing an upward shift in the asymptotic dispersion rate. However, this weakness in the model is only significant under very high utilization, and when the probe packets are not significantly larger than those of the cross-traffic.

5. DISCRETE PACKET-PAIR MODEL: MULTIPLE-HOP SCENARIOS

To extend the analysis to multiple-hop scenarios we follow Melander et al. [5] in applying the one-hop model iteratively. Figure 10 illustrates this idea for a two-hop path: The input probe gap �in is substituted into the model for Hop 1, the output of which (�

1 out) becomes the input gap

Figure 10. Iterative application of single-hop model in the analysis of a multiple-hop topology.

666 M. J. TUNNICLIFFE AND M. WINNETT

Figure 11. Simulated and analytical dispersion-rate profiles obtained for a two-hop network path in (a) largest surplus first and (b) shortest surplus first configuration. Error bars indicate ±1.96 times

the standard mean error (95% confidence interval).

(�2in) of Hop 2. This is perfectly valid under the fluid-traffic assumption (Section 2.2) where all the links behave deterministically. However, this is not the case with our discrete-traffic model, which takes a determinate �in and calculates the mean value of the resulting output-gap distribution. To

PACKET-PAIR PROBING TECHNIQUE 667

Figure 12. Comparison of analytical and simulated dispersion ratio profiles for a two-hop network path with equal available bandwidth at each hop (0.7 Mbit/s). Error bars indicate ±1.96 times the standard

mean error (95% confidence interval).

make �1out = �2in is to treat the latter as a determinate quantity, which is not strictly valid since nonlinearity within the Hop 2 may cause the resulting �2out to differ from the true mean value. (To understand this, consider that f (E(x)) = E( f (x)) when var(x)>0 and f (x) is a nonlinear function.) We nonetheless proceed with the approach, knowing that it is not altogether rigorously correct.

Figure 11 compares the model’s predictions with simulations of the network path of Figure 4(a) and its ‘alias’ topology of Figure 4(b), using 500 byte probe packets and a variety of cross-traffic packet sizes. Despite its imprecise assumptions, the model agrees quite closely with the data for Sc =50 and 100 bytes, even when the effects of the two slope-changes overlap. However, the introduction of 200 and 250 byte packets yields more significant errors, which can be explained by the greater statistical variation created by the larger packets.

It is interesting to consider a third scenario where the two links have equal available bandwidth, and there is no single identifiable tight-link. Figure 12 shows an example: Although Node 1 is the narrow-link, both nodes have exactly 700kbit/s of available bandwidth. Again 500 byte probe packets were used in conjunction with 100 and 250 byte cross-traffic packets: The model agrees closely with the 100 byte simulation results, while the 250 byte simulation yields a significantly greater dispersion than the model.

668 M. J. TUNNICLIFFE AND M. WINNETT

6. GENERAL DISCUSSION AND CONCLUSIONS

This paper began by considering the probing of single and multi-hop network paths under the packet-pair algorithm. Having demonstrated the breakdown of this model under finite packet-sized cross-traffic, an approximate stochastic model was developed and tested. This model was shown to produce accurate results for single-hop networks, though errors appeared when the utilization was high (80–90%). Furthermore, these errors became more severe as the cross-traffic packet size increased: For 80% utilization the model was reasonably accurate when Sc = 15 Sp but significantly inaccurate when Sc = 12 Sp. When applied to two-hop network paths, the model proved accurate only for smaller Sc (typically

1 10 to

1 5 Sp). Such errors are to be expected, given the underlying

assumptions: First the ‘true’ Poisson and approximate Gaussian distributions are only similar when the standard deviation is small relative to the mean (which ceases to be true when Sc approaches Sp.) Second, high utilization causes the queue-size profile to decay over longer time-periods, over which a better representation of equilibrium recovery than the simple step-model (Figure 7) is required. Finally the iterative application of the model to two-hop paths requires that statistical variation in the output gap of the first hop be small. Increases in Sc tend to increase this variability, thus reducing the accuracy of the prediction. However, if Sp is kept relatively large (say 1500 bytes in an Ethernet network) the model should be usable for typical average packet sizes and practical levels of utilization (�60%).

The paper has mostly addressed the modelling of the probing experiment rather than the extrac- tion of network-path information from packet-pair data. The latter is more challenging, and will be addressed in a separate paper. One particular challenge concerns the large stochastic variance of individual packet dispersions: Since many readings (100+) are often needed to obtain a reliable average, measurements must be spread over large time windows and short time-scale behaviour (particularly variations in the cross-traffic c) cannot be observed. The measurement window can of course be reduced by bunching the packet pairs closer together, but this introduces problems of its own; namely the interference between probing events compromises their statistical independence and the probe traffic takes an unacceptable share of the bandwidth being measured.

The software used to test the model was based on simple queuing assumptions that may not perfectly represent many real network components: In particular, a single raw bandwidth and FIFO queuing at each node, assumptions that are not universally valid in access networks and wi-fi [4]. The model (and its successors) will need to be verified using a more realistic network simulator and/or hardware components.

REFERENCES

1. Dovrolis C, Ramanathan P, Moore D. What do packet dispersion techniques measure? Proceedings of the IEEE INFOCOM 2001, Anchorage, AK, U.S.A., vol. 2, April 2001; 905–914.

2. Crovella M, Krishnamurthy M. Internet Measurement: Infrastructure, Traffic and Applications. Wiley: New York, 2006; 127–136.

3. Lakshminarayanan K, Padmanabhan VN, Padhye J. Bandwidth estimation in broadband access networks. Proceedings of the 4th ACM SIGCOMM Internet Measurement Conference (IMC’04), Taormina, Italy, October 2004; 314–321.

4. Lee HK, Hall V, Yum KH, Kim KI, Kim EJ. Bandwidth estimation in wireless lans for multimedia streaming purposes. Preprint available at http://www.cs.utsa.edu/∼yum/publication/icme06.pdf, 2007 (accessed 17 September 2008).

PACKET-PAIR PROBING TECHNIQUE 669

5. Melander B, Björkman M, Gunningberg P. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks. Proceedings of the IEEE Globecom’00, San Francisco, CA, U.S.A., vol. 1, November 2000; 415–420.

6. Liu X, Ravindran K, Liu B, Loguinov D. Single-hop probing asymptotics in available bandwidth estimation: sample-path analysis. Proceedings of the 4th ACM Internet Measurement Conference, Taormina, Italy, October 2004; 300–313.

7. Park K-J, Lim H, Choi C-H. Stochastic analysis of packet-pair probing for network bandwidth estimation. Computer Networks 2006; 50:1901–1915.

8. Hosseinpour M, Tunnicliffe MJ. TOPP probing of network links with large independent latencies. Proceedings of the 8th Annual Postgraduate Symposium on Telecommunications, Networking and Broadcasting, Liverpool, U.K., June 2007; 381–386.

9. Tunnicliffe MJ, Parish DJ. A hybrid simulator for an ATM network. International Journal of Communication Systems 2000; 13:179–184.

10. Liu J. Packet-level integration of fluid TCP models in real-time network simulation. Proceedings of the 38th Conference on Winter Simulation, Monterey, CA, U.S.A., December 2006; 2162–2169.

11. Franx GJ. The transient M/D/c queueing system. Preprint available at http://www.math.vu.nl/sto/publications/ 2002-9.pdf, 2002 (accessed 17 September 2008).

12. Scholl M, Kleinrock L. On the M/G/1 queue with rest periods and certain service-independent queuing disciplines. Operations Research 1983; 31:705–719.

AUTHORS’ BIOGRAPHIES

Martin J. Tunnicliffe obtained a BEng degree in Electrical and Electronic Engineering from the University of Bradford in 1987 and a PhD from Loughborough University in 1993. He currently teaches in the Faculty of Computing, Information Systems and Mathematics at Kingston University.

Maria Winnett holds a BSc from the University of Manchester and a PhD from Kingston University, where she is currently teaching in the Faculty of Computing, Information Systems and Mathematics. She has previously worked for a number of companies including Racal, Logica and Symbian.