41
CHAPTER 6
Bottlenecks and Flow
Equivalence
We see that, for a separable network, we can compute the joint distribution with Jacksons 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 finite 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 Littles 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 traffic analysis.
Note that a bottleneck can be identified 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
defines 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 traffic adopts a dumbbell model, like in
Fig. 6.1. A bottleneck may not be caused by hardware; for example,TCPs congestion window limits
a connections throughput, so it can act like a bottleneck.
For an open queueing network, a bottleneck defines 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 defines a throughput barrier on X. Note that the asymptotically linear increase in T for
a closed system is significantly 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.