4
Network Constraints and Effective
Bandwidths
This chapter concerns the technological constraints under which networks operate. Just as a
manufacturing facility produces goods by consuming input factors, so a communication
network provides communications services by consuming factors such as labour and
interconnection services, and by leasing equipment and simpler communications services.
We wish to emphasize the importance of timescales in service provisioning. In the short
run, a network’s size and capabilities for service provisioning are fixed. In the long run,
the network can adapt its resources to the amounts of services it wishes to provide. For
example, it might purchase and install more optical fibre links. The cost models of Chapter 7
use incremental cost to evaluate the costs of services and are based upon a consideration
of network operation over long timescales.
Innovations, such as electronic markets for bandwidth using auctions, are beginning to
permit some short run changes in service provisioning through the buying and selling
of resources. However, on short timescales of weeks or months, both the size of the
network and its costs of operation must usually be taken as fixed. On short timescales,
communications services resemble traditional digital goods, in that they have nearly zero
marginal cost, but a very large common fixed cost.
Prices can be used as a control to constrain the demand within the production capability of
the network: that is, within the so-called technology set. If one does this, then the consumer
demand and structure of the technology set determine prices. In this chapter we provide
tools that are useful in describing the technology sets of networks that offer the services and
service contracts described in Chapter 2. The exact specification of such a technology set is
usually not possible. However, by assessing a service’s consumption of network resources
by its effective bandwidth, we can make an accurate and tractable approximation to the
technology set.
More specifically, in Section 4.1 we define the idea of a technology set, or acceptance
region. Section 4.2 describes the important notion of statistical multiplexing. Section 4.3
concerns call admission control. Section 4.4 introduces the idea of effective bandwidths,
using an analogy of filling an elevator with boxes of different weights and volumes. We

;:::;x
k
/, is constrained to lie in a technology set, X. This set is defined by the
provider, who must ensure that he has the resources he needs to provide the services he sells.
It is implicit that each service has some associated performance guarantee and so requires
some minimum amount of resources. Thus, x lies in X (which we write x 2 X) if and only
if the network can fulfil the service contracts for the vector quantity of services x. Note that
here we are concerned only with the constraints that are imposed by the network resources;
we ignore constraints that might be imposed by factors such as the billing technology or
marketing policy.
Different models of market competition are naturally associated with different optimiza-
tion problems. This is discussed fully in Chapter 6. In a monopoly market it is natural to
consider the problem of maximizing the monopolist’s profit. In a market of perfect com-
petition it is natural to consider problems of maximizing social welfare. In both cases, the
problems are posed under the constraint x 2 X. Models of oligopoly concern competition
amongst a small number of suppliers and lead to games in which the suppliers choose
production and marketing strategies subject to the constraints of their technology sets.
Let x be the vector of quantities of k supplied service types. A general problem we wish
to solve is
maximize
x½0
f .x/; subject to g.x/ Ä 0 (4.1)
The objective function f .x/ might be the supplier’s profit, or it might be social welfare. Here
X Dfx : g.x/ Ä 0g, where the inequality is to be read as a vector inequality, expressing
m constraints of the form g
i
.x/ Ä 0, i D 1;:::;m. It is natural that the technology set
be defined in this way, in terms of resource constraints and constraints on guaranteed
performance. We suppose that f .x/ is a concave function of x. This is mathematically
convenient and reasonable in many circumstances. Without loss of generality, we assume

of cells that the service contract allows to service type i,andC is the capacity of the link.
Although such a constraint makes sense for synchronous networks, in which connections
are allocated fixed amounts of bandwidth during their lifetimes, equal to their peak rates
h
i
, it may not make sense for asychronous networks, where connections are allocated
bandwidth only when there is data to carry. If the service provider of such a network uses
(4.2) to define the technology set he does not make efficient use of resources. He can do
better by making use of statistical multiplexing, the idea of which is as follows. Typically,
the rate of a traffic stream that uses service type i fluctuates between 0 and h
i
, with some
mean, of say m
i
. At any given moment, the rates of some traffic streams will be near their
peaks, others near their mean and others near 0 or small. If there are many traffic streams,
then the law of averages states that the aggregate rate is very likely to be much less than
P
i
x
i
h
i
; indeed, it should be close to
P
i
x
i
m
i

x
k
Figure 4.1 The Call Admission Control (CAC) problem. Given the state of the system in terms of
the active traffic contracts and a history of load measurements, should a new traffic contract of type
i be admitted?
86 NETWORK CONSTRAINTS AND EFFECTIVE BANDWIDTHS
than the number that can be carried if we require no cell loss. If there is just a single type of
source then x
peak
D C=h
1
and x
stat.
D C=Þ
1
would be the number of streams that could be
carried without and with statistical multiplexing, respectively. Let us define the statistical
multiplexing gain for this case as
SMG D
x
stat.
x
peak
D
h
1
Þ
1
Clearly, it depends upon the CLP. In Example 4.1, the statistical multiplexing gain is a factor
of almost 5. The special case of requiring CLP D 0 is usually referred to as deterministic

. The technology set
A, which we also call the acceptance region, is that set of x D .x
1
;:::;x
k
/ corresponding
to quantities of traffic types that it is possible to carry simultaneously without violating this
QoS constraint (see Figure 4.2). Note that the technology set is defined implicitly by the
QoS constraint. Later we show how to make explicit approximations of it.
As explained in Sections 2.2.3 and 3.1.5, Call Admission Control (CAC) is a mechanism
that ensures that x remains in A. It does this by rejecting calls for new service connections
through the network that would take the load of active calls outside A. Thus the acceptance
region and CAC are intimately related. In practice, however, it is hard to know A precisely
and so we must be conservative. In implementing a particular decision rule for CAC, we
keep the load x within a region, say A
0
, that lies inside the true acceptance region, A.For
instance, a possible rule CAC rule is to accept a call only so long as (4.2) remains satisfied;
this would correspond to taking A
0
as the triangular region near the origin in Figure 4.2.
This rule is very conservative. The QoS constraint is easily satisfied, but the network carries
fewer calls and obtains less revenue than it would using a more sophisticated CAC. This
AN ELEVATOR ANALOGY 87
CAC based on
peak cell rate
x
2
x
1

;:::;h
k
. In contrast, we say that a CAC is dynamic when it is
based both on contract parameters and on-line measurements of the present traffic load.
It is desirable that the decision rule for CAC should be simple and that it should keep x
within a region that is near as possible to the whole of A, and so there be efficient use of
thenetwork.Whenwedefine A
0
in terms of a CAC rule we can call A
0
the ‘acceptance
region’ of that CAC; otherwise acceptance region means A, the exact technology set where
the QoS constraints are met.
Suppose that as new connections are admitted and old ones terminate the mix of traffic
remains near a point Nx on the boundary of A. We call Nx the operating point . We will shortly
see that the acceptance region can be well approximated at Nx by one or more constraints
like (4.3), and this constant Þ
i
can be computed off-line as a function of Nx, the source
traffic statistics, the capacity, buffer size and QoS required.
If a network has many links, connected in an arbitrary topology, then call admission is
performed on a per route basis. A route specifies an end-to-end path in the network. A
service contract is admitted over that route only if it can be admitted by each link of the
route. This may look like a simple extension of the single link case. However, the traffic
that is generated by a contract of a certain type is accurately characterized by the traffic
contract parameters only at the entrance point of the network. Once this traffic travels inside
the network, its shape changes because of interactions with traffic streams that share the
same links. In general, traffic streams modelled by stochastic processes are characterized
by many parameters. However, for call acceptance purposes, we seek a single parameter
characterization, namely the Þ

/ D .2; 5/ and .v
j
;w
j
/ D .4; 10/. Clearly the elevator can equally well
88 NETWORK CONSTRAINTS AND EFFECTIVE BANDWIDTHS
carry two boxes of type i as one box of type j,since.4; 10/ D 2 ð .2; 5/. But what should
one say when there is no integer n such that .v
i
;w
i
/ D n ð .v
j
;w
j
/? This is the question
posed in Figure 4.3.
It depends upon whether the elevator is full because of volume or because of weight.
Suppose that boxes arrive randomly and we place them in the elevator until no more fit. Let
x
i
denote the number of boxes of type i. If at this point the maximum volume constraint
is active, then
k
X
iD1
x
i
v
i

x
i
w
i
D W
and the effective usage is the weight of the box. We then say the effective bandwidth is w
i
.
In what sense is
w
i
,
i
= n ×
W,V
?
w
i
,
i
w
j
,
j
Figure 4.3 The elevator can carry a total weight of at most W and volume at most V . A box of
type i has weight w
i
and volume v
i
. A box of type i has n times the relative effective usage of a

iD1
x
i
Þ
i
Ä C
Ł
and define Þ.:::/D .Þ
1
.:::/;:::;Þ
k
.:::// and C
Ł
.:::/ as functions of x, v, w, V and W .
If these variables are such that the maximum volume constraint is active then Þ D v and
C
Ł
D V . But if they are such that the maximum weight constraint is active, then Þ D w
and C
Ł
D W .Thatis,
.Þ; C
Ł
/ D
(
.v; V /
.w; W /
as
P
i

;w
i
/, and on the
capacities, V; W . They also depend on the operating point x, since if we are given the
values of x for a full elevator we can determine which constraint is active.
There are various ways this operating point might be reached. It could be, as we have
imagined so far, that we simply fill the elevator with boxes as they arrive. Which of the
two constraints becomes active depends upon the rates at which the different types of box
arrive. This might depend on the time of the day. Alternatively, we might accept and reject
offered boxes so as to fill the elevator in a particular way. Alternatively, we might charge
boxes for use of the elevator. The more we charge the boxes of type i, the smaller will be
their rate of arrival.
Imagine that there are k agents, one associated with each box type. Agent i obtains
benefit u
i
.x
i
/ when the elevator carries x
i
boxes of type i . Suppose we wish to steer the
operating point to maximize the sum of these utilities, i.e. to maximize f D
P
i
u
i
.x
i
/.Let
Nx be the point on the boundary of A that does this. Assuming that each u
i

D ½v
i
, D ¼w
i
or D ½v
i
C ¼w
i
, in line with the three possibilities described
above. Then the point Nx,atwhich f is maximized within A, can be characterized as the
solution to k problems, the ith of which is to maximize [u
i
.x
i
/  p
i
x
i
] over x
i
. Note that
these k problems decouple and can be solved in a decentralized fashion. The ith problem
is to be solved by agent i. He seeks to maximize his net benefit, given that the price per
box of type i is p
i
. Thus the problem of maximizing the function f can be solved in a
decentralized fashion, within a market for services where this optimal price vector will be
determined. Observe that in most cases, p
i
= p

i
D .x
i
=T
i
/T
i
). As above, posting
prices that affect arrival rates can solve the problem of maximizing a utility function that
captures the value of the services to the customers. A similar observation applies to the
interpretation of x in (4.1). If each service is priced with an appropriate price p
i
, then the
market will find an equilibrium at the solution of this optimization problem. Again, such
prices should be proportional to the effective bandwidths of the services.
Note that it is valid to make this simple translation from x
i
as a number of boxes to an
arrival rate of boxes only if the boxes arrive regularly, i.e., exactly every T
i
=x
i
time units.
If, however, boxes arrive irregularly, say according to a stochastic process, and x
i
is only an
average arrival rate, then the instantaneous rate of arriving boxes can occasionally exceed
the average value. So, if the elevator is full some arriving boxes may be blocked from being
served. We discuss models that take account of such blocking effects in Sections 4.14 and 9.3.3
4.5 Effective bandwidths

=@x
k
j
xDNx
C o.ž/
(where o.ž/ denotes a term that is small compared to ž: explicitly, o.ž/=jžj!0asjžj!0).
So, we satisfy the binding constraint to within o.ž/ if
ž
1
@g
i
=@x
1
CÐÐÐCž
k
@g
i
=@x
k
j
xDNx
D 0
Thus, it is natural to define the effective bandwidth of contract j as Þ
j
D @g
i
=@x
j
þ
þ

P
j
x
j
Þ
j
D
P
j
Nx
j
Þ
j
defines a hyperplane that is tangent to g
1
D c
1
at the operating
point Nx, with Þ
j
D @g
1
=@x
j
þ
þ
xDNx
.HereÞ depends on which constraint is binding and this
depends on the operating point Nx. Now a local approximation to the boundary of g
1

j
= C*
k
Figure 4.5 The acceptance region A is defined by two constraints. At the operating point Nx,which
achieves the maximum of f in A, the active constraint is g
1
.x / Ä c
1
and so the effective
bandwidths will be of the form Þ
j
D @g
1
=@x
j
þ
þ
xDNx
. Note that the problem of maximizing f subject
to
P
k
jD1
x
j
Þ
j
Ä C
Ł
,whereC

Þ
j
(4.4)
If the operating point Nx was defined by maximizing f over A, then this line is also tangent
to a contour of f at this point. The problem of maximizing f subject to (4.4) is solved
also at Nx. Thus, for the purposes of identifying Nx, or motivating users to choose Nx in a
decentralized way, the approximation in (4.4) to the boundary of A is as good as the true
constraint g
1
.x/ Ä c
1
.
4.6 Effective bandwidths for traffic streams
The technology set for transport services depends on the information that is available
about the connections. We look first at the case in which we have a full description of each
connection’s traffic. In subsequent sections, we consider the more realistic case that the only
information available about a connection is its service contract. The material of this section
is mathematically intricate and some readers may wish to skip to the summary at the end.
We consider the simple problem of determining the number of contracts that can be
handled by a single switch. The switch has a buffer of size B and serves C cells per
second in a First Come First Serve (FCFS) fashion. In practice, switches may require
more sophisticated modelling than FCFS in order to capture the effects of the sophisticated
scheduling mechanisms that are used for differentiated services. Suppose the QoS is defined
only in terms of the CLP, or equivalently in terms of the probability that the content of
the buffer exceeds a certain level. Constraints concerned with exceeding maximum delay
bounds can also be modelled this way (see Example 4.7). However, it is reasonable to
focus on CLP because in present switch design this is more important than average delay.
Present designs use small buffers for real time services. This keeps the maximum delay
small. Even if large buffers are used, the CLP is usually already greater than we wish to
permit before the size of the delay becomes important.

e
sX
j
[0;t]
i
(4.5)
In Section 4.5, we showed that the binding constraint at the operating point Nx can be
approximated by the linear constraint
k
X
jD1
x
j
Þ
j
.s; t/ Ä C
Ł
(4.6)
where C
Ł
D
P
Nx
j
Þ
j
.s; t/.
We emphasize that the effective bandwidth of a traffic stream is a function of its multiplex-
ing context. This is fully summarized in the value of the parameters s and t. To determine
the effective bandwidth constraint, one must first find the values of these parameters. They

1
. This is because it is when the source
produces at a high rate for a relatively long time, of order t
2
, that the buffer overflows. During such
a long time, fluctuations on the t
1
timescale are evened-out and do not contribute to the overflow.
EFFECTIVE BANDWIDTHS FOR TRAFFIC STREAMS 93
upon the size of the buffer, the CLP and the precise mix of traffic that is multiplexed at
the operating point. If any of these change, then the most probable time to overflow also
changes. For example, t tends to zero as the size of buffer, B, tends to zero.
The value of the space parameter s (perhaps measured in kb
1
) measures the degree
to which advantage can be gained from statistical multiplexing. In particular, for links
with capacity much greater than the sum of the mean rates of the multiplexed sources,
s tends to zero and Þ
j
.s; t/ approaches the mean rate of a source of type j (e.g. as
lim
s!0
[s
1
log.
1
2
e
as
C

(e.g. as lim
s!1
[s
1
log.
1
2
e
as
C
1
2
e
bs
/ D maxfa; bg). For sources that do not have
maximum peak rates, such as a Gaussian one,
N
X
j
[0; t] D1. Note that this gives the
appropriate effective bandwidth for ‘deterministic multiplexing’ (i.e. for CLP D 0), since if
P
j
x
j
Þ
j
.1; t/ Ä C,wheret is given the value that maximizes the left-hand side of this
inequality, then
P

.0/
,
and N tends to infinity. It can be shown that
lim
N !1
1
N
log.CLP.N //
D sup
t½0
inf
s½0
"
st
k
X
jD1
x
.0/
j
Þ
j
.s; t/  s

C
.0/
t C B
.0/
Á
#