41

CHAPTER 6

Bottlenecks and Flow

Equivalence

We see that, for a separable network, we can compute the joint distribution with Jackson’s Theorem

if it is open, and compute the mean performance measures with MVA if it is closed. Although the

separability requirement has been progressively relaxed, it remains restrictive. For example, although

one can view the Internet as a massive queueing network, there are few queueing-theoretic models of

the Internet; the ﬁnite buffers in routers, the bounded packet lengths, the feedback effect of packet

acknowledgements, etc. all get in the way of applying results from queueing theory.

There are no general techniques for solving nonseparable queueing networks. Even so, we can

often get bounds by analyzing bottleneck queues, or get an approximate solution by decomposing

the network, as illustrated in this chapter.

6.1 BOTTLENECK ANALYSIS

Consider a (closed or open) queueing network, with throughput X. Suppose queue i has K

i

servers,

with average service time S

i

per job. Let V

i

be the average number of visits to queue i per job, and

service demand D

i

= V

i

S

i

. By Little’s Law, the utilization per server is

V

i

XS

i

K

i

=

XD

i

K

i

≤ 1, so X ≤

K

i

D

i

.

This is true for every i,so

X ≤ min

i

K

i

D

i

.

A queue that gives the minimum K

i

/D

i

or (equivalently) the maximum service demand per server

D

i

/K

i

is called a bottleneck.

A bottleneck also maximizes XD

i

/K

i

, so it has highest utilization per server. There is always

a maximum D

i

/K

i

, so a bottleneck always exists. Relieving a bottleneck by speeding up its servers

(i.e., reducing D

i

) or adding servers (i.e., increasing K

i

) only shifts the bottleneck to another queue.

42 6. BOTTLENECKS AND FLOW EQUIVALENCE

sources destinations

bottleneck link

routers

Figure 6.1: The dumbbell model frequently used in Internet trafﬁc analysis.

Note that a bottleneck can be identiﬁed from K

i

and D

i

, without knowing V

i

and S

i

, nor

solving for X. Identifying a bottleneck in a network is important; as its name suggests, a bottleneck

deﬁnes a bound and, to a large extent, it determines the performance of a system. This is one

reason many simulation and analytical studies of Internet trafﬁc adopts a dumbbell model, like in

Fig. 6.1. A bottleneck may not be caused by hardware; for example,TCP’s congestion window limits

a connection’s throughput, so it can act like a bottleneck.

For an open queueing network, a bottleneck deﬁnes a capacity bound, like the vertical asymp-

tote in Fig. 2.5 for an M/G/1 queue — performance deteriorates rapidly as workload approaches

that bound.

For a closed network, Little’s Law gives N = XT , where T is system time. Now, when the

population size N is small, there is little queueing, so T ≈

i

D

i

; therefore, X ≈

N

i

D

i

, which is

approximately linear in N.

For large N, the bottleneck imposes a bound X ≤ min

i

K

i

D

i

,so

T ≈

N

min

i

K

i

D

i

, which is approximately linear in N.

The shapes of X and T as functions of N are thus as shown in Fig. 6.2; in particular, a

bottleneck deﬁnes a throughput barrier on X. Note that the asymptotically linear increase in T for

a closed system is signiﬁcantly different from the super-linear increase for an open system like the

M/G/1 in Fig. 2.5. The difference lies in the feedback for a closed system: If a system is open, new

jobs arrive regardless of congestion, so completion time balloons; if the system is closed, however,

then a slow down in job completion time also slows down the generation of new jobs.

For the interactive (closed) system in Fig. 1.4, we get corresponding bounds on response time

R from R = T − Z.

Get *Analytical Performance Modeling for Computer Systems* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.