Metastability of fair bandwidth sharing

under fluctuating demand and necessity

of flow admission control

V. Marbukh

A flow-level Markov model for fair bandwidth sharing with packet

retransmissions and random flow arrivals=departures is proposed and

discussed. Despite the model being unstable even under light exogenous

load, a desirable metastable state may exist. The network can be stabilised

with flow admission control at the cost of small flow blocking probability.

Introduction: A flow level Markov model of fair bandwidth sharing

under fluctuating demand has been proposed in [1, 2] for a case of file

transfer flows, and in [3] for a case of a mixture of file transfer and

streaming flows. These Markov models assume separation of timescales: given numbers of flows in progress, the fair bandwidth sharing

protocol reaches equilibrium much faster than the numbers of flows in

progress change due to flow arrivals=departures. Stability under the

condition that each link can accommodate its average load was

established in [2, 3]. However, these Markov models and stability

results do not account for bandwidth wasted on transmissions of

‘dead’ file transferring packets which will be dropped downstream

and then retransmitted.

This Letter proposes to account for wasted bandwidth by assuming

that the file transfer rates are determined by the end-to-end goodputs

rather than the corresponding throughputs as in [1–3]. The ‘goodputbased’ Markov model is unstable even under light exogenous load, when

the corresponding throughput-based models [1–3] are stable. The

instability, observed in [4] by simulations, is a result of demand

fluctuations: increase in the number of flows in progress causes increase

in packet loss, reducing goodput and further increasing the number of

flows in progress. Despite instability, a desirable metastable network state

with a finite number of flows in progress may still exist. The network can

be stabilised in a close neighbourhood of this metastable state with

appropriately designed flow admission control at the price of a small flow

rejection probability. Network over provisioning without flow admission

control only reduces but does not eliminate the instability region.

Models with fixed set of flows: Consider a network comprised of links

j 2 J with capacities Cj. Given a vector of numbers of flows N 1⁄4 (Nr)

carried on all feasible routes r 2 R, the fixed point model [5] determines

end-to-end flow rates x 1⁄4 (xr) and packet loss probabilities p 1⁄4 (pr) for

all feasible routesr 2 R. In a case of small packet losses: pr <<1, (a, w) –

fair rate allocation [6] results in the following rate assignments:

xr 1⁄4 wr

P

j2r

pj

 !1=a

ð1Þ

where a, wr > 0 are some parameters, and end-to-end packet loss on a

route r 2 R is the sum of packet losses on all the links comprising this

route: pr 1⁄4 Spj, j 2 r. Cases a 1⁄4 0, a 1⁄4 1 and a 1⁄4 1 correspond,

respectively, to an allocation which maximises throughput, is proportionally fair or is maxmin fair. Case a 1⁄4 2 describes Transmission

Control Protocol (TCP) Reno.

A large number of expressions for source transmission rates in a

case of medium and heavy packet losses have been proposed. A

straightforward generalisation of (1) is as follows:

xr 1⁄4 wr 1  Q

j2r

ð1  pjÞ

, ) " # 1=a

Q

j2r

ð1  pjÞ

" #w 8

<

:

ð2Þ

where w 0, e.g. [7] considers w 1⁄4 1=a 1⁄4 0.5. When link j carries a large

number of flows the following fluid limit approximation can be used:

pj 1⁄4 max 

0; 1  Cj

 P

r:j2r

Nrxrj ð3Þ

where the link j load produced by flows carried on a route r is

xrj 1⁄4 xr

Q

j2r

j

ð1  pjÞ ð4Þ

and the part of a route r positioned upstream from link j 2 r is rj

. Given

a vector of numbers of flows in progress N 1⁄4 (Nr), (2)–(4) form a closed

system of fixed-point equations for a vector of source rates and link

packet losses (xr, pj). After solving (2)–(4), the goodput for a flow

carried on a route r is determined as follows:

gr 1⁄4 xr

Q

j2r

ð1  pjÞ ð5Þ

Markov models with arriving=departing flows: Following [3], assume

that the network carries file transfer and streaming flows. Introduce

vector (N1, N2), where N1 1⁄4 (N1r) and N2 1⁄4 (N2r) are the vectors of the

numbers of file transfer and streaming flows, respectively, carried on

all feasible routes r 2 R. We assume that file transfer and streaming

flows arrive on a route r 2 R according to a Poisson process of rate L1r

and L2r, respectively. The size of a file arriving on a route r 2 R is

distributed exponentially with average br and the holding time of a

streaming flow arriving on a route r 2 R is distributed exponentially

with average tr. All flow arrivals, file sizes and holding times are

jointly statistically independent.

We assume separation of time-scales: given vector N 1⁄4 N1þ N2 of

numbers of flows in progress N 1⁄4 (Nr) where Nr1⁄4 N1r1⁄4 N2r, the flow

control protocol reaches equilibrium bandwidth sharing much faster than

the number of flows change due to flow arrivals=departures. Under this

assumption the evolution of the number of flows in progress can be

approximated by a homogeneous in time t 0 Markov process (N1 (t),

N2(t)). We propose to account for retransmission of file transferring packets

by assuming that the file transfer rates are determined by the end-to-end

goodputs (5) rather than the corresponding throughputs xr as in [1–3]. This

seemingly minor change drastically alters stability properties of the

Markov process (N1(t), N2(t)) owing to deterioration of the aggregate

route goodputs as the numbers of flows in progress increase. Note that

separation of time-scales allows for modelling of congestion-dependent

admission control and user behaviour by assuming that rates Lir1⁄4 Lir (N)

depend on the vector of numbers of flows in progress N 1⁄4 N1þ N2.

It is known that the ability of links to sustain their average file

transfer load:

rj 1⁄4

def 1

Cj

P

r: j2r

L1rbr < 1; 8j 2 J ð6Þ

are necessary and sufficient conditions for ergodicity of the ‘throughput-based’ Markov model when rates Lir, 8i 1⁄4 1,2;r 2 R are fixed [2, 3].

One may expect that the necessary and sufficient stability conditions for

the ‘goodput-based’ Markov model can be obtained from (6) by

accounting for the additional load due to retransmissions of file

transferring packets:

r~j 1⁄4

def 1

Cj

P

r: j2r

L1rbr

P

i2r

þ

j

ð1  piÞ

< 1; 8j 2 J ð7Þ

where rj

þ is the part of a route r located downstream from link j 2 r. Link

packet losses pi increase, and typically approach 1, with increase in the

number of flows carried on the link. This may cause instability of the

goodputbased model in a case of multihop routes even under light loads,

when stability conditions for the throughput-based model (6) are satisfied.

Despite instability, the goodput-based model may have a desirable

metastable state with finite number of flows in progress. Under fluid

regime

Lir 1⁄4 e

1

lir; Cj 1⁄4 e

1

cj; lir; cj 1⁄4 Oð1Þ; e ! 0 ð8Þ

i 1⁄4 1, 2, 8r 2 R, 8j 2 J, this metastable state corresponds to a locally

stable equilibrium (nir*), nir* <1 of the following system of ordinary

differential equations:

n_ 1r 1⁄4 l1rðn1 þ n2Þ  b1

r n1rgrðn1 þ n2Þ ð9Þ

n_ 2r 1⁄4 l2rðn1 þ n2Þ  n2rt1

r ð10Þ

describing evolution of normalised numbers of flows in progress nir 1⁄4

eNir, i 1⁄4 1, 2, 8r 2 R [3]. The metastable state exists under sufficiently

light exogenous load and is realised if the initial number of flows in

progress is sufficiently small. Otherwise, the number of file transfer

flows infinitely grows with time: limt!1 n1r (t) 1⁄41, r 2 R, reflecting

instability of the corresponding Markov goodput-based model even

under light exogenous load lir, i 1⁄4 1, 2; r 2 R, when stability conditions

(6) for the corresponding throughput-based model are satisfied. The

network can be stabilised in a close neighbourhood of the desirable

Techset Composition Ltd, Salisbury Doc: {EL}Articles/Pagination/EL53520.3d

Telecommunication

ELECTRONICS LETTERS 13th September 2007 Vol. 43 No. 19
metastable state with appropriately designed flow admission strategy at

the cost of small flow rejection probability.

Example: Consider a symmetric ring network with K nodes, where

each node k 1⁄4 1,2,... , K is connected to node (k þ 1) mod (K) by a

directed link jk of capacity C. Let weights wr 1⁄4 w, flow arrival rates

lir 1⁄4 li, i 1⁄4 1, 2, average file sizes br 1⁄4 b, average streaming flow

durations yr 1⁄4 y and numbers of carried flows nir 1⁄4 ni, i 1⁄4 1, 2 be route

r 2 R independent, where the set of feasible l-link routes is R 1⁄4 {(jk,

j(kþ1)mod(K),... , j(kþl) mod(K)): k 1⁄4 1,... ,K}. We assume that flows

arrive only on feasible routes: lir 1⁄4 nir 1⁄4 0, i 1⁄4 1, 2, r2= R. Owing to

limited space we only consider a case of proportional fair rate

assignments (2) with a 1⁄4 1 and w 1⁄4 0 under fluid asymptotic regime

(8) and assume w 1⁄4 c. Introduce utilisation by file transfer flows

r 1⁄4 ll1b=c, utilisation by streaming flows b 1⁄4 ll2t, and normalised

numbers of flows carried on a link Zi 1⁄4 nil, i 1⁄4 1, 2. Under all these

assumptions the efficiency of the bandwidth sharing, measured by the

fraction of link bandwidth occupied by packets to be delivered to their

destinations as opposed to packets to be dropped downstream, is

gðZÞ 1⁄4 Z

ð1 þ Z=lÞ

l  1 ð11Þ

where Z 1⁄4 Z1 þ Z2. Note that (11) follows from (5) and expression for

the link packet loss p 1⁄4 (1 þ l=Z)

1

, which can be derived from (2)–(4).

Consider a case of fixed arrival rates li, i 1⁄4 1, 2 assuming that the

numbers of streaming flows in progress already reached equilibrium:

Z2 1⁄4 b [3]. In this case system (9)–(10) simplifies into the following

single differential equation for normalised number of file transfer flows

carried on a link:

bZ_1 1⁄4 r  Z1

ð1 þ ðZ1 þ bÞ=ðlÞÞl  1 ð12Þ

Equilibriums of (12) are determined by the following fixed-point

equation:

Z1 1⁄4 f ðZ1Þ 1⁄4def

r 1 þ Z1 þ b

l

 l

1

" # ð13Þ

Fig. 1 Solution to equilibrium fixed point equation Z1 1⁄4 f(Z1)

Fig. 1 shows the solution to the ‘steady-state’ equation (13) in two

cases: r > r

* (b) and r < r* (b), where the metastability threshold for

file transfer load r

* (b) monotonously decreases from r* (0) 1⁄4 1 to r* (1) 1⁄4 0 with increase in the exogenous streaming load b. If the

exogenous file transfer load r exceeds the metastability threshold:

r > r

*

(b), equilibrium equation (13) has no solution Z1 > 0, and

according to dynamic equation (12) the number of file transfer flows

in progress Z1 (t) infinitely grows with time for any initial Z1 (0) 0. If

the exogenous file transfer load r is below the metastability threshold:

r < r

*

(b), equilibrium equation (13) has two solutions Z1 1⁄4 Z1

*(r, b)

and Z1 1⁄4 Z1

** (r, b) describing, respectively, stable and unstable

equilibriums of dynamic equation (12). In this case the number of

file transfer flows in progress Z1(t) stabilises with time: limt!1 Z1

(t) 1⁄4 Z1*(r, b) if initially the network is lightly loaded Z1 (0) < Z1**(r,

b). Otherwise, i.e. if Z1 (0) > Z1

**(r, b) then the number of file transfer

flows in progress Z1 (t) infinitely grows: limt!1 Z1(t) 1⁄4 1.

Functions r*(b), Z1

*(r, b) and Z1**(r, b) can be easily evaluated

numerically. Consider some particular cases. In a case b1⁄40, i.e. when

the network carries only file transfer flows, the metastability threshold is

r* 1⁄4 1. When r < 1, the metastable state is Z1

* 1⁄4 0, and unstable state

Z1

** is the unique positive solution of equation Z=r 1⁄4 (1þZ=l)

1  1.

This equation yields Z1

** 1⁄4 4 (r1  1) if l 1⁄4 2, and takes the form

Z=r 1⁄4 e

Z  1 if l!1. When b!0, d 1⁄4

def 1  r!0, the following

asymptotic formulas result from (13):

d* 1⁄4

def 1  p

* 1⁄4

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

2

1  1

l b

r

ð14Þ

Z1

* 1⁄4 l

l  1

d 

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

l

l  1

l

l  1

d2  2b

s   ð15Þ

Z1

** 1⁄4 l

l  1

d þ

ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi

l

l  1

l

l  1

d2  2b

s   ð16Þ

More detailed analysis shows that equilibrium Z1

* represents the desirable metastable network state with a finite number of flows in progress.

This metastable state can be transformed into a stable state with flow

admission control, which admits arriving file transfer flows if and only

if the normalised number of file transfer flows already in progress Z1

lies within the stability region of this metastable state: Z1 < Z1**. The

stabilisation is achieved at the cost of asymptotically small flow

rejection probability under the fluid regime.

Conclusion: A flow-level performance model for fair bandwidth

sharing with packet retransmissions and arriving=departing flows is

proposed. The model accounts for packet retransmissions by assuming that file transfer rates are determined by the end-to-end goodputs

rather than the corresponding throughputs as in the conventional

model. This seemingly minor modification drastically alters the

model stability properties: the goodput-based model is unstable

even under light load when the conventional model is stable. Despite

instability, a desirable metastable network state with finite number of

flows in progress may still exist. The network can be stabilised in a

close neighbourhood of the desirable metastable state at the cost of a

small flow rejection probability. Future research should address

numerous questions raised by the possibility of metastability, such

as the effect of the fairness parameters a and wr in (1)–(2) on the

existence, stability margins, and queuing performance of the desirable

metastable state as well as a possibility of network stabilisation by a

distributed admission strategy for a general topology network.

# The Institution of Engineering and Technology 2007

22 February 2007

Electronics Letters online no: 20070543

doi: 10.1049/el:20070543

V. Marbukh (National Institute of Standards and Technology, 100

Bureau Drive, Gaithersburg, MD 20899-8920, USA)

E-mail: marbukh@nist.gov

References

1 Ben Fredj, S., Bonald, T., Proutiere, A., Regnie, G., and Roberts, J.:

‘Statistical bandwidth sharing: a study of congestion at flow level’. Proc.

of Sigcomm, San Biego, California, USA, 2001

2 de Veciana, G., Lee, T.J., and Konstantopoulos, T.: ‘Stability and

performance analysis of networks supporting elastic services’,

IEEE=ACM Trans. Netw., 2001, (9), pp. 2–14

3 Key, P., Massoulie, L., Bain, A., and Kelly, F.P.: ‘Fair Internet traffic

integration: network flow models and analysis’, Ann. Telecommun., 2004,

59, pp. 1338–1352

4 Massoulie, L., and Roberts, J.W.: ‘Arguments in favour of admission

control for TCP flows’. ITC 16, Edinburg, UK, June 1999

5 Gibbens, R.J., Sargood, S.K., Van Eijl, C., Kelly, F.P., Azmoodeh, H.,

Macfadyen, R.F., and Macfadyen, N.W.: ‘Fixed-point model for

end-to-end performance analysis of IP networks’. 13th ITC Specialist

Seminar: IP Traffic Modeling, Measurement and Management,

Monterey, USA, 2000

6 Mo, J., and Walrand, J.: ‘Fair end-to-end window-based admission

control,’, IEEE=ACM Trans. Netw., 2000, (8), pp. 556–567

7 Kelly, F.: ‘Mathematics unlimited and – 2001 and beyond’, in Engquist,

B., and Schmid, W. (Eds.): (Springer-Verlag, Berlin, 2001), pp. 685–702

ELECTRONICS LETTERS 13th September 2007 Vol. 43 No. 19