TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 1

Fairness of Traffic Controls for Inelastic Flows In

the Internet
Dah Ming Chiu Adrian Sai-Wah Tam

Abstract— In best-effort networks, fairness has been used as As the Internet shifts to support increasing volume of
a criterion to guide the design of traffic controls. The notion multimedia applications, there has been continuous debate on
of fairness has evolved over time, from simple equality to a
the next generation Internet architecture. Various proposals
form of equality modulated by the user’s need (e.g. max-min
have been made for building a multi-services network to
and proportional fairness). However, fairness has always been
defined on a per-user basis for a deterministic workload. In this support different types of applications, for example ATM [1],
paper, we argue that we must redefine the notion of fairness Integrated Service [2], Differentiated Service [3] and MPLS-
when we study traffic controls for the co-existence of elastic and based traffic engineering [4]. Despite such efforts, a prevalent
inelastic traffics. Our results indicate that subjecting inelastic
belief is that the Internet’s connectionless service model does
flows to fairness congestion control on a per-flow basis does not
not need to change, as long as there is adequate provisioning of
necessarily maximize the network’s utility. Instead, inelastic flows
may follow their own form of traffic control, such as admission network bandwidth (see [5] for a systematic discussion of this
control (without congestion control). At the aggregate level, our viewpoint). What is needed instead is a relaxed end-system
results indicate that it still makes sense to maintain a balance congestion control that co-exists with the widely used TCP
between elastic and inelastic traffic. In order to support our
congestion control.
arguments, we develop a methodology for comparing different
So what is a suitable alternative congestion control for
traffic controls for given utility functions and different workloads,
both deterministic and stochastic. multimedia applications to practice? The orthodox solution
requires all applications to share network bandwidth fairly,
Index Terms— congestion control, admission control, fairness,
utility maximization, non-convex utility function, stochastic traffic as existing TCP flows do. If an application needs more
model bandwidth than the prevailing fair share, then it should adapt
its bandwidth (down) in favor of fairness. It is recognized
I. I NTRODUCTION that multimedia flows need more gradual adaptation to fair
Internet is a connectionless network. It relies on congestion bandwidth share, so the effort of designing the alternative
control implemented in the end-systems to prevent offered control is focused on a smooth transient response in bandwidth
load exceeding network capacity, as well as evenly allocate adaption. Proposals of such congestion control schemes are
network resources to different users and applications. In generally referred to as TCP-friendly congestion controls in
the past, the applications (such as email, file transfer) were the literature [6]–[8].
predominantly elastic, or in other words flexible in their The thesis of this paper is to argue for abandoning the
bandwidth requirements. The Internet architecture served these traditional notion of fairness in designing end-system traffic
applications well. controls for different types of applications. Unlike the case

Dah Ming Chiu and Adrian Sai-Wah Tam are with the Department of
with elastic traffic, the best way to deal with congestion
Information Engineering, The Chinese University of Hong Kong, Shatin, N.T., for inelastic traffic should be some form of admission
Hong Kong (email: dmchiu,swtam3
@[Link]).
control, which is by definition unfair in the traditional sense.
This work was partially supported by University Grants Committee, Hong
Kong SAR under RGC grant 4232/04E (project 2150420) and AoE grant
Furthermore, it is important to consider the stochastic nature of
AoE/E-01/99 (project 4801312). bandwidth allocation, rather than the allocation of bandwidth
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 2

to a fixed number of flows. The fact that flows arrive at significance of this work and future directions are discussed
different times and have different demands for the network in the concluding section.
should also be taken into account in fair bandwidth allocation.
II. R EVIEW OF PREVIOUS WORK
While we argue against insisting on per-flow TCP- Actually, some of the basic ideas we are espousing have
friendliness, our results show that in a self-regulated network, been discussed at some length in a seminal paper by Shenker
it is still sensible to apply TCP-friendliness principles at the ten years ago [5]. Shenker pointed out the obvious benefits
aggregate level. In other words, it yields higher utility for both in merging different types of networks (i.e. data, voice and
kinds of traffic to maintain a balanced allocation according to TV) into a single network. While over-provisioning can always
the respective demand. satisfy the needs of such an integrated network, Shenker
argued that it is more effective to introduce multiple services
The methodology used to substantiate and support these
into the network to support the different applications. Most
arguments is to define the bandwidth allocation problem as
importantly, to measure how good a network is, he introduced
a network utility optimization problem. There is significant
the notion of utility maximization. Shenker elaborated on some
prior literature on this approach which we will review.
different forms of utility function for different types of (e.g.
Our contribution is to extend the standard network utility
elastic and inelastic) flows, and applied utility maximization
maximization by considering non-concave utility functions to
to justify the role for admission control in the situation
model inelastic flows, as well as considering both the elastic
when the utility function is non-concave. Although [5] was
and inelastic traffic as stochastic processes with finite sizes.
written in the context of advocating Integrated Service [2],
Both of these extensions have been considered recently in
which pre-dated subsequent work on end-system admission
separate contexts [9]–[11], but we apply these extensions
control [12] and TCP-friendly congestion control [6], its
together to develop a methodology to evaluate different traffic
analysis and discussion of network design goals, viz. the utility
controls for the co-existence of TCP and non-TCP flows.
optimization framework, still applies to end-system based
In particular, it is challenging to account for the utility of
traffic controls.
flows of different sizes. We adopt a decomposition model for
Before the utility maximization formulation, various
accounting the utility of flows of different sizes which makes
performance metrics had been adopted in studying network
the computation feasible.
traffic control algorithms. In addition to the obvious goals
The rest of the paper is organized as follows. In section II, of maximizing the throughput and minimizing the delay,
we briefly review the classic results on bandwidth allocation fairness was also adopted as an important goal [13], [14]. In
and fairness of network traffic controls. In section III, we a simple setting of a fixed number of flows sharing a common
develop our methodology for studying network fairness and bottleneck, the simple notion of fairness corresponding to
discuss the validity of the TCP-friendliness approach. In dividing bandwidth equally among competing flows seems
section IV, we apply our approach to a homogeneous class particularly appealing. Both distributed algorithms (e.g. AIMD
of flows, the utility function is parametrized to model both [13]) and centralized algorithms (e.g. fair queueing [15]) were
elastic as well as inelastic flows. In section V, we apply our proposed to implement fair traffic control. The emphasis of
methodology to a scenario where heterogeneous flows (both equality was also extended to the case when not all flows share
elastic and inelastic flows) co-exist. We introduce idealized the same path. In a general network topology with arbitrary
models of several traffic controls for inelastic flows, and apply flows, fair bandwidth allocation is first applied to the most
our methodology to compare them. Specifically, for inelastic limiting bottleneck, and iteratively to all bottlenecks, leading
flows, we compare how admission control fares against TCP- to the definition of max-min fairness.
friendly (like) controls, for the deterministic workload case in The theory of network utility maximization blossomed when
section VI and stochastic workload in section VII. Finally, the Kelly et al applied it to create a fluid model of the Internet
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 3

with elastic applications under congestion control [16]. Kelly’s in a network under distributed traffic controls. For more
model reduces the complicated network under distributed realistic evaluation, it is still important to consider a stochastic
congestion control to a standard convex optimization problem workload of flows.
There is a body of work studying bandwidth allocation with
max Ui  xi 
x stochastic workloads as well [9], [18]. See [19] for a survey
i

subject to Rx  c of this topic. The thrust of these studies often focus on how
to create a stochastic model for which there is a product form
where x denotes the transmission rate of a set of flows; the
solution (e.g. Whittle networks), or such product-form solution
flows’ routes (which links are use by a flow) are represented by
can be used as a performance bounds for the original model
the zero-one matrix R; the capacity of the links are represented
[20].
by c, and the utility of the i-th flow is represented by Ui  xi  .
One way to derive the solution for this problem is through III. A N EW A PPROACH FOR E VALUATING N ETWORK
decomposing the problem into a set of sub-problems for the T RAFFIC C ONTROLS
flows and the network, and this has a straight correspondence Most of the notations for the rest of the paper are introduced
to Internet’s end-system congestion control with network in this section. Table I provide a summary.
feedback. Kelly showed that the simplistic AIMD-like [13]
distributed congestion control adopted in the Internet is stable, A. Type of Flows and Utility Functions

and achieves a sensible operating point assuming logarithmic In our new problem formulation, we consider two types of
utility functions. The resultant bandwidth allocation is referred flows that use the network in different ways:

to as being proportionally fair. In [17], a more general family Holding time flows. Such a flow has a holding time. After
of utility functions (of which the logarithmic utility is only using the network for the holding time, the flow leaves.
a special case) is introduced. Based on this family of utility 
File transfer flows. Such a flow has a file size. It stays in
functions, it is possible to relate the different types of network the network for as long as necessary until the complete
fairness, such as max-min fairness, proportional fairness, and file has been transferred from source to destination.
maximum-throughput allocation, as the solutions of utility Holding time flows are normally inelastic flows whereas
maximization corresponding to different utilities. While this file transfer flows are normally elastic flows. The degree of
theory is very elegant, because its assumption of concave elasticity of each kind of flow, however, is determined by the
utility functions (to make the problem tractable as convex respective utility function which will be introduced below. In
optimization problems), it is limited to characterize a network the following discussion, we assign an elastic utility function
with elastic flows only. Furthermore, we also believe the to file transfer flows and refer to them as elastic flows. The
assumption that all flows stay indefinitely long for the system elasticity of the utility function assigned to holding time flows
to reach a steady state is too limiting. is controlled by a parameter. For the study of different traffic
Recently, some authors begin to consider the utility controls in this paper, we assume the holding time flows have a
maximization problem when not all users have concave rather inelastic utility function, hence we also refer to holding
utility functions [10], [11]. This considerably complicates time flows as inelastic flows unless noted otherwise.
the utility maximization problem. However, they showed Since we are considering flows of finite size, it is necessary
that under some continuity conditions, distributed price- to account for how the utility of a flow depends on its size.
based (congestion feedback based) congestion algorithms can We consider the two types of flows separately.
still converge to the optimal solution. These studies mostly a) Holding time flows: We find the utility of a holding
consider a given fixed number of flows, derive the best steady time flow by decomposition.
state bandwidth allocation to these flows. These results give Consider a holding time flow f with holding time T , arriving
new insights to co-existence of elastic and inelastic traffic at time t0 , and achieving rate x f  t  for t0  t  t0  T . The
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 4

TABLE I
the unit of uI  is utility per unit time (e.g. seconds). The
S YMBOLS AND NOTATIONS
assumption above becomes
Symbol Explanation Assumption 1 (Utility composition of holding time flows):
f, fj Flows or subflows
The utility of a holding time flow is the sum of the utility of
x  t  , xE  t  , xI  t  Bandwidth allocated to a flow at time t, elastic, or
inelastic the instantaneous rates the flow achieves, namely
aE  n m  , aI  n m  Bandwidth allocation to an elastic/inelastic flow as a
function of system state, (n m)
 f  uI  x f  t  dt 
T
T , Tj Holding time of an inelastic flow, j This assumption obviously does not always hold. For
S, S j File size of an elastic flow, j example, consider a flow f that achieves rate x f  t   1 for

f Utility accrued by a flow f

t  0  T  2 and x f  t   0  5 for t   T  2  T  . Alternatively,
uE  x  Utility accrued by a byte of elastic flow transferred at
rate x. The unit is utility per byte. consider another flow f  with the same holding time T but
uI  x  Instantaneous utility of an inelastic flow with allocated achieves rate
bandwidth x. The unit is utility per unit time.
sk  Sigmoidal utility function with parameter k, as in (1) 1 for t  k  t t k  1  , k  0  2  4 
G Utility throughput, also known as u-put
xf  t  
0 5 for t  t t k  1  , k
 k  1  3  5 
GE  t  , GI  t  Instantaneous utility throughput of elastic/inelastic
flows where tk  t0  δ for some small δ ! T . For each scenario, the
ḠE , ḠI Average utility throughput of elastic/inelastic flows
flow’s utility comes out the same according to assumption 1. In
ḠCE , ḠCI Average utility throughput of elastic/inelastic flows
under traffic control C reality, we expect the first flow, f to get a lower utility for most
n,n  t  Number of elastic flows, at time t inelastic applications since it is easier to tolerate occasional
m,m  t  Number of inelastic flows, at time t
loss than continuous loss. Nonetheless, this assumption makes
P  n m Probability that the network has n elastic flows and m
inelastic flows the inelastic flows decomposable, and allows a reasonable way
PC  n m Probability that the network has n elastic flows and m to account for the utility of flows of different sizes.
inelastic flows under control C
b) File transfer flows: Intuitively, the utility of a file
α Desired rate of inelastic flows
ε Minimal rate allowed for each elastic flow by inelastic transfer flow depends on two things:
flows when performing aggressive admission control. 
the time it takes the transfer to complete
See section VII.

the file size
λE Arrival rate of elastic flows
1 µE Mean file size of elastic flows, E  S  1 µE We expect it to be a non-increasing function of the former,
λI Arrival rate of inelastic flows
and a non-decreasing function of the latter. The dependency on
1 µI Mean holding time of inelastic flows, E  T  1 µI
ρE Offered load of elastic flows, ρE  λE  µE completion time is equivalent to (the reciprocal) dependency
ρI Traffic intensity of inelastic flows, ρI  λI  µI on average transfer rate. Consider a file transfer flow f of
αρI Offered load of inelastic flows.
file size S f , that achieved a certain transfer rate x f  t  between
ρ ρ  ρE  αρI , this is the total bandwidth demand by
both elastic and inelastic flows some start of finish time of the file transfer, and x¯f denotes
the average transfer rate of the flow f . The assumption for the
utility of a file transfer flow can be stated as:
Assumption 2 (Utility composition of file transfer flows):
The utility of a file transfer flow is the sum of utility for each
utility achieved by flow f is denoted  f. We can view f as
byte which is a function of the average rate, namely
the composition of subflows f j ( j  1  h) of holding times
Tj ( j  1  h, j Tj  T ). We assume that the utility of f  f  S f uE  x¯f  

is comparable to the sum of the utility of the subflows. In the Again, we derive the utility of a flow by decomposition. The
limit, as each subflow becomes sufficiently short, the utility function uE  x̄  is a (usually concave) utility function on the
of a subflow (at time t) becomes the utility of achieving an average rate. Note, the unit of uE  is utility per unit of data
instantaneous rate x  t  which we denote using uI  x  t  . Note, (e.g. bytes). Therefore, the total utility of a flow can be thought
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 5

of as being composed from the utility of each byte of the flow. 1

k=0.1
But unlike in the holding time case, each component utility is
0.8 k=0.3
based on the same average rate instead of the instantaneous
0.6 k=1
rate.
sk(x)
k=2
Some alternative definitions of the utility composition rule 0.4
k=5
of file transfer flows were also considered. One possibility
0.2
is to let the utility of each data unit be dependent on the k=50
k=1000
0 x
instantaneous rate of transferring that unit of data. This would 0 0.2 0.4 0.6 0.8 1
give rise to the following paradox. Let f be a flow of size
S f and achieved rate x f  t  , and f is decomposed as two Fig. 1. A family of sigmoidal function sk  x  with different values of k

flows g and h so that Sg  Sh  S f , and xg  t  and xh  t  cover

different intervals of the original horizon of x f  t  . Since uE  is a sigmoidal function:
is concave, by Jensen’s inequality we know
0 if x %$ 1
π x ')( 1
sk  x   sink 2 & ( 2 '*( 1
if $ 1 + x %$ 2 (1)
  f "  g #   h
1 if x ,"$ 2 .

So the utility of a flow increases as we decompose a flow A family of the sigmoidal functions sk  is plotted in Figure
(without any other change in the transfer of a flow), not a 1. Note, x is the given rate; $ 1 and $ 2 are thresholds so that
satisfying property. Another possibility is to make flow utility when x "$ 1 , sk  x   0 and when x ,"$ 2 , sk  x   1 (in Figure
be a non-linear function (e.g. concave) of the file size. This 1, $ 1  0 and $ 2  1). The parameter k controls the shape
would also cause the flow utility change as we split up a flow. of sk  x  . The larger the value of k, the closer the function is
In real life, a file transfer can be split up into multiple smaller to a step function. For k larger than 1, there is an inflexion
file transfers, and there is a large class of traffic controls point where the change in the gradient goes from positive to
that may take advantage of such flow splitting (e.g. schedule negative. When we use this sigmoidal function as the inelastic
them to be transferred sequentially or in parallel, possibly on utility function, we assume k , 1.
different paths). The analysis of these cases is beyond the In this paper, we set uE  x   log  1  x  and uI  x   sk  x 
scope of the current paper. with $ 1  0 and $ 2  α , where α is the rate at which the
inelastic flow is intended to transfer its data. We use this
particular set of function to ensure the utility of a flow is
bounded and always positive.
B. Utility function

In the previous subsection, we established the utility of C. Workload

a flow in relation to functions uE  or uI  . Actually, the What we have introduced so far allows us to define a
elasticity of a flow are determined by the shape of uE  and workload which is simply a set of elastic and inelastic
uI  . flows that use the network. A workload can be stochastic
If the utility function of instantaneous rate is non-decreasing or deterministic. A deterministic workload would be defined
and concave, then we consider the associated flow elastic. by a fixed set of flows with given arrival times, given file
For an inelastic flow, its utility function (for instantaneous sizes (and holding times), and a utility function for each
rate) is still non-decreasing, but the slope might not always flow. A stochastic workload, on the other hand, would be
be decreasing. A good example of an elastic utility function is defined by given arrival rates (e.g. assuming Poisson arrivals),
a logarithmic function, and that for an inelastic utility function and given distributions of file size and holding time (e.g.
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 6

assuming exponential distribution), and the corresponding reasons. Once we establish the methodology, we can compare
utility functions for elastic and inelastic flows. any two traffic controls which are considered reasonable to
In this paper, we consider both deterministic workloads implement in practice. In particular, we will try to compare fair
as well as stochastic workloads. When studying stochastic congestion control with admission control as two alternatives
workloads, we assume an exponential distribution for file size for managing inelastic traffic in a mixed traffic environment.
and holding time to make the model reducible to a Markov In addition to workload, we need to define (a) network state,
chain and use standard techniques to compute the performance (b) traffic control, and (c) utility throughput, as follows.
metrics.
The state of such a simple network can be characterized
Assumption 3 (Flow size distribution): Flow size (file
by the flow population in the network and the per-flow states.
size or holding time) is exponentially distributed.
At time t, the flow population of the network is given by the
More realistic flow size distributions (e.g. heavy-tailed) and
ordered pair  n  t   m  t  , where n  t  is the number of elastic
packet level (rather than flow level) modeling is beyond the
(file transfer) flows and m  t  the number of inelastic (holding
scope of the current paper, and is under further study.
time) flows. The state of flow f j is given by the current rate
xfj  t .
D. Comparison of Traffic Controls
Given the network state, it is possible to define traffic
We start by restricting ourselves to the simplest network, controls — the object of our study. A traffic control can
with the following assumption, which applies to the rest of be thought of as a function that maps the network state
this paper: (current state plus history) and other workload information to
Assumption 4 (Network): The network consists of a bandwidth allocation. We are mainly interested in distributed
single link. traffic controls, which means a flow’s allocation is based only
This is a reasonable assumption when the focus is to on its own flow state and some summary information about
consider a set of flows sharing a single bottleneck. In a the network’s state. For example, if the traffic control is TCP,
general network setting, network utility maximization tends to the summary of network state would be a binary variable
favor shorter flows (those traversing fewer links) than longer indicating whether the total load exceeds the nominal system
flows, as made clear by [16]. This is a different dimension capacity or not. For each traffic control we study, we will list
in designing heterogeneous traffic controls that should be out what network summary information must be gathered later
considered separately in the future. when we describe those traffic controls.
Given a workload and network topology and static workload
In a real-life system, it takes time for the traffic control
(fixed number of flows), it is possible to decompose and
implemented in each flow to gather needed information for
transform the network utility optimization problem to use
making adjustments, and it also takes time for the controls to
distributed algorithms to obtain the optimal allocation. For
take effect. The ensuing dynamics is extremely complicated.
example, this has been studied for elastic flows in [16],
For our purposes, we assume idealized controls; in other words
and for mixed elastic and inelastic flows in [10] and [11].
For stochastic workloads, however, the problem becomes Assumption 5 (Fluid model with zero feedback delay):

more complicated. One established framework for studying Traffic controls can implement any rate within the link

optimal controls is through Markov decision processes. Using capacity and sense the network condition instantaneously, and

this approach, the derived optimal traffic control will likely the controls take effect immediately.

be state-dependent, which is not easy to implement in a This assumption makes it possible to account for the different
distributed fashion. In this paper, we focus on answering a traffic controls as different transition rates in a Markov process
simpler question: how do we compare two traffic controls? model, and compute the state space probability distribution,
This is more tractable as well as quite useful for practical P  n  m .
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 7

E. Utility Throughput aI  of the system state1 :

Finally, we define utility throughput (u-put for short) as the xI  t   aI  n  t   m  t  

rate the network is generating utility based on the different

flows getting served by the network. This is a function of Then the instantaneous u-put equation becomes

the traffic control adopted, and consequently the basis for

GI  t   m  t  uI  xI  t  
comparing different traffic controls. Theoretically, each flow
finishes accruing certain amount of utility from the network If the system is in steady state, then there is a steady state
at its departure time. The u-put would then be the rate the distribution for m  t  (and n  t  elastic flows), P  n  m . So we
network accrues utility based on this process. can calculate ḠI :  E  GI  as:
Let  f1  f2  fK  be the set of flows that complete in time
ḠI  muI  aI  n  m  P  n  m (4)
interval [0  T ]. Then the u-put (denoted G) can be generally
n m 1- 0
defined as
K The u-put of elastic flows, according to Assumption 2 can
j- 1  fj
G (2) be computed based on the utility of each data unit (byte)
T
transferred. During a time interval t to t  δ t, let a total of
This definition can be used for both stochastic workloads as R  t  bytes (from n  t  elastic flows) be transferred. The u-put
well as deterministic workloads. of elastic flows at time t can be written as:
In the stochastic workload case, flows are assumed to be R t0
of finite size (given by some distribution) and are assumed GE  t   uE  x̄ j 
to arrive at a certain rate λ with some inter-arrival time j- 1

distribution. The systems of interest are those that are stable, for δ t approaching zero. The average rate x̄ j here denotes the
or in other words converge to a steady state. In the steady state, average rate of the flow the j-th transferred byte belongs to,
it is possible to derive an average flow utility for holding time and uE  is the elastic utility function defined earlier. Unlike
and file transfer flows,  I and  E respectively. in the inelastic case, however, x̄ j is some property of a flow
and we do not have a steady state distribution for that. To
facilitate the computation, we make another assumption:
G  GI  GE  λI  I λE  E (3)
Assumption 6 (Same average rate): For a stochastic
workload, the average rate seen by each file transfer flow is
Equation 3 can in turn be computed in terms of the
the same as the steady state file transfer flow rate averaged
components of flow utility according to Assumption 1 and
over all elastic flows, and it is independent of file size, namely
2.
At time t, let there be a set M  t  ( . M  t  .# m  t  ) inelastic x̄ j  aE  n  m  P  n  m2 x̄ 
m n 1- 0
flows, and let x f j  t  be the transmission rate of inelastic flow
Here, n is the number of elastic flows in the network and
fj  M  t  . The network is thus accumulating inelastic utility
aE  n  m  denotes the bandwidth allocated to each elastic flows
at the rate:
under certain traffic control in state  n  m  . Intuitively, this
GI  t   uI  x f j  t   assumption is more reasonable if flows are not too small,
j / M t0 relative to the fluctuation of network utilization.

Here, uI  is the inelastic utility function. 1 Note, aI  in this form is not general enough to represent all traffic
controls. For example, not all flows necessarily have the same rate. Even
If the traffic control under consideration is such that all
in our case, those flows rejected by admission control will get zero rates. But
inelastic flows (in the network) transmit at the same rate xI  t  , for our purpose of computing u-put, we are only interested in admitted flows
then we can write down the traffic controls as simple function and they are assumed to have the same rate as other flows in the same class.
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 8

Now we can readily write down the u-put for elastic flows potentially large) population model, and multiple kinds of
rewards2 .
ḠE  λE E   f In the following sections, we apply this methodology to a
 λE E  S f  uE  x¯f  comparative study of some specific traffic controls.
 ρE uE aE  n  m  P  n  m  (5)
m n 1- 0
IV. C ASE S TUDY: T RAFFIC C ONTROLS FOR

The definition of u-put is quite general, and can be H OMOGENEOUS F LOWS

readily applied to the case of deterministic workloads, as Before analyzing the case of two classes of traffic, we first
long as the bandwidth allocation functions aI  n  t   m  t  and compare different traffic controls for holding time flows when
aE  n  t   m  t  are well-defined. We will see an example of this it is the only kind of traffic (when elastic traffic is absent). We
in section VI. vary the utility function to see how it affects the selection of
The reason we separately account for the elastic and the best traffic control.
inelastic utility is that it is very difficult to calibrate the Let the holding time flows arrive at a rate of λI and let
utility functions to make the two kinds of utilities addable. each flow have an average holding time of 1  µI . Let the utility
This slightly complicates the comparison of different traffic function be
controls, but is a more reasonable way to account for the
0 if x  0
situations.
π x
sk  x   sink 2 & α if 0 + x  α (6)
Thus we have explained for each traffic control, C, how to
compute the u-put as a pair of values,  ḠCE  ḠCI  , corresponding 1 if x , α

to the elastic and inelastic utility throughput. This affords us Which is (1) with $ 1 0 and $ 2 α . The utility varies between
a way to compare traffic controls. If ḠH
E , ḠKE and ḠH
I , ḠKI , zero and one. As illustrated in Figure 2, the utility is zero for
then we can say traffic control H is better than K. Note, this rate x  0, and increases with x until it reaches 1 when x  α
would be just for the one workload that is analyzed. In order and stays the same for larger values of x. The parameter k
to do a complete comparison for traffic control H and K, it is controls the shape of the curve. In one extreme, when k  1,
necessary to evaluate a spectrum of representative workloads the utility function is concave. In this case, a holding-time
that are of interest. flow behaves a little like an elastic flow, in the sense that
Let ḠCE  w  and ḠCI  w  be the elastic and inelastic u-put for it can still benefit from a rate significantly smaller than its
traffic control C under different workloads index by w. In order desired rate α . In the other extreme, for larger values of k the
to conclude that a traffic control H is better than K, we require utility function approaches a step function. This corresponds
to the classic utility function of an inelastic flow with α as its
ḠH
E w 43 ḠKE  w 5 w W desired rate. These type of flows cannot benefit from a rate
ḠH K
I  w 43 ḠI  w  5 w W sufficiently smaller than its desired rate.
We consider two types of traffic controls: congestion
where W is some set of benchmark workloads. control (with fair allocation) and admission control. Under
This completes the description of our methodology for Assumptions 3, 4 and 5 both can be analyzed by standard
comparing two traffic controls. In essence, this methodology queueing models.
(when considering stochastic workloads) is rather similar to The fair congestion control can be modeled by a M/M/∞
the Markov reward processes [21]. In the terminology of [21], queue. In a state with m jobs, since all flows are of the
comparing u-put is analogous to comparing the system gain
2 This is why it is not straightforward to consider using policy iteration
under two different policies to find out which is the better method to optimize our traffic controls. But this is something we are working
policy. In our case, we do need to deal with an infinite (or on.
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 9

1 16 1000
k
Gcc, k=1
14
0.8
12

utility throughput
Gac 100 Gac > Gcc
0.6 10
sk(x) 6
8
0.4 Gcc, k=2
6
10
4 Gcc, k=5
0.2 Gac = Gcc
2 Gac < Gcc
Gcc, k=50
0 x 0 ρ 1 ρ
0 0.5α α 1.5α 0 5 10 15 20 25 30 35 40 45 50 0 5 10 15 20 25 30 35 40 45 50

Fig. 2. A particular utility function for inelastic Fig. 3. Utility throughput in homogeneous case, Fig. 4. Crossover value of k at different offered
flows, with k  50. with α  07 1 load ρ , with α  07 1

holding time type, the departure rate is mµI . The steady state Erlang-B model. When fair congestion control is applied, the
probability distribution of number of flows is given by situation becomes interesting. The system u-put depends on the
ρIn e ' ρI utility function, parametrized by k. When k  1, the utility is
Pcc  m2 
m! still elastic (concave). The fair congestion control consistently
1
The u-put in state m, however, is given by msk  m . According gives higher u-put for all values of ρ . When k  2, i.e. when
to equation (4), the steady state average u-put is the utility becomes mildly inelastic, there is a crossover point
∞
1 in the u-put curves. In other words, when the offered load
Gcc  msk  m Pcc  m8
m- 0 is sufficiently high, there is a point when it is better to start
The admission control case can be modeled by a M/M/h/h applying admission control (for k  2, this point is roughly
loss system, where h :9 1  α ; denotes the maximum number ρ  20). As the utility function becomes more inelastic, the
of flows the network can accommodate giving them their crossover point appears earlier and earlier. It is clear that
desired rate α . The steady state probability distribution of the the admission control approach becomes asymptotically better
number of flows is given by than fair congestion control as k becomes large.
h Figure 4 shows the crossover value of k versus each offered
ρIm ρIj ' 1
Pac  m2 
load ρ . The curve serves as a dividing line: for all the values
m! j!
j- 0
of (ρ  k) above the curve, it is better to use admission control,
Since the admission control scheme does not over-admit, all
and vice versa. Actually, for many points below the curve
admitted flows get utility of 1, and all blocked flows get utility
(e.g. ρ + 5), admission control is also reasonable since the
of zero. This means the steady state u-put is simply
u-put curve for admission control is approximately the same
h
Gac  msk  m1  Pac  m as the fair congestion control curve until the crossover point,
m- 0 as shown in Figure 3.
h
 mPac  m
m- 0 V. C ASE S TUDY: T RAFFIC C ONTROLS FOR
 ρ  1 < Pac  h  H ETEROGENEOUS F LOWS

where Pac  h is the blocking probability. The case of considerable practical interest is when both
Since we have closed-form expressions for the u-puts of elastic and inelastic flows sharing the network. We let the
both systems we want to compare, we can plot them against traffic control for elastic flows be some form of fair congestion
the offered load, ρ , as in Figure 3. control, as in the Internet. For inelastic flows, there are three
The figure shows that the u-put for the admission controlled options we want to compare: (1) no control (NC), (2) fair
system, Gac , increases monotonically as ρ increases and congestion control (CC), (3) admission control (AC). We
reaches a saturated level. This is expected behavior for the discuss how bandwidth is allocated in each case.
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 10


No control (NC). Perform neither congestion control nor In other words, the newly arriving flow is admitted
admission control. This is meant to model the behavior only if its desired rate (α ) is no greater than the
of UDP flows. In this case, when 1  α or more inelastic prevailing fair share for each elastic flow. The above
flows are in the network, the network capacity is totally condition actually reduces to
consumed (equally shared) by the inelastic flows, and the
 n  m  1 α  1
elastic flows get no service. Otherwise, if there are m +
1  α inelastic flows, each inelastic flow gets α and the Because this form of admission control tries to be

elastic flows share the remaining 1 < mα . friendly to elastic (hence TCP) flows, we refer to it

Fair congestion control (CC). Perform TCP-friendly as TCP-friendly admission control.

congestion control. Here, we model it as the same fair To summarize, we can write down the traffic control

congestion control as adopted for elastic flows, with a functions for NC, CC, AC1 and AC2 in terms of what they

slight difference. When the fair share is smaller than α , allocate to elastic flows (aE  n  m  ) and what they allocate to

then the fair share is used, but when the fair share is inelastic flows (aI  n  m  ) when there are n and m flows of each

greater than α , the inelastic flows would still consume kind respectively:

α . This is a different treatment than the model in [18] 1 ' mα

if mα  1
n
NC: aE  n  m  
where rate allocated to inelastic flow is always the same
0 if mα , 1
as elastic flows.
1 ' mα

Admission control (AC). Perform admission control but n if  n  m  α  1 (7)
CC: aE  n  m  
no congestion control once admitted. In general, the 1
n= m if  n  m  α , 1
admission control function can be quite sophisticated. For
1 ' mα
AC1, AC2: aE  n  m   if mα  1
example, it may depend on the playback rate α and the n

holding time µi . In our analysis, we assume the playback

α if mα  1
rate for all inelastic flows are the same, and consider a NC: aI  n  m  
1
m if mα , 1
rather simple form of admission control that is oblivious
to the holding time. Assume the network already has α if  n  m  α  1 (8)
CC: aI  n  m  
n elastic flows and m inelastic flows, a newly arriving 1
if  n  m  α , 1
n= m
(inelastic) flow is admitted if
AC1, AC2: aI  n  m   α if mα  1
nε " m  1  α  1
For AC1 and AC2, aE  n  m  and aI  n  m  are defined assuming
The parameter ε represents some minimal rate the the m inelastic flows have been admitted. Therefore, aE  n  m 
admission control scheme tries to leave alone for each 1
and aI  n  m  for the m ,>9 α; case are not specified.
elastic traffic. It is a knob to tune how aggressive to make For inelastic flows, the utility function uI  is the same
the admission control try. We consider two extreme cases: sigmoidal function introduced before in Equation 6. For elastic
– Aggressive admission control (AC1). In this case, flows, the utility function uE  is the frequently adopted log
ε ! α . In other words, the arriving flow is admitted function, with normalization:
as long as it is possible to allocate to it the desired
uE  x   log  1  x   (9)
rate of α , even if this means all elastic flows have
Now we are ready to compare the four cases: NC, CC, AC1
to run at their minimum rate of ε .
and AC2 as alternative traffic controls for inelastic flows in co-
– Fair admission control (AC2). In this case, ε  α.
existence with elastic flows. We first consider a deterministic
Precisely, the arriving inelastic flow is admitted if
workload case, and then the more general stochastic workload
1 < nα
3 α case in the next two sections.
m 1
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 11

TABLE II
VI. C ASE S TUDY: S TATIC W ORKLOAD
C OMPARING ḠE OF DIFFERENT TRAFFIC CONTROLS

Range of m Comparison Region

We first study a special workload when all n elastic and m 1 @ nα
0? m? ḠAC2  ḠCC
E  ḠAC1  ḠNC (i)
inelastic flows arrive at the same time3 and stay on indefinitely. α E E E
1 @ nα 1 @ nε
m ḠAC2 B ḠCC
E B ḠAC1  ḠNC (ii)
If the flow were an elastic flow, it has an infinite file size; if α A A α E E E
1 @ nε 1 @ nε
m ḠAC2 B ḠCC
E B ḠAC1 B ḠNC (iii)
α A A ε E E E
it were an inelastic flow, it has an infinite holding time. We 1 @ nε
? m ḠAC2 B ḠAC1 B ḠCC
E B ḠNC (iv)
ε E E E
referred to these as infinite flows. This is a special case of
deterministic workload, and it is the workload commonly used
in the study of congestion control and bandwidth allocation for A. Comparing Elastic Utility Throughput

homogeneous networks with elastic traffic flows only. We also Let ḠNC CC AC1 and ḠAC2 be the elastic u-put for NC,
E  ḠE  ḠE E
refer to this as the static workload. An important reason for CC, AC1 and AC2 respectively. After some straightforward
taking a special look at this workload is that it is possible to algebraic manipulations, we have
derive closed-form solutions, so that the results will lead to Proposition 1: The relationship between the elastic u-put
more insights and certain degree of validation of the general for NC, CC, AC1 and AC2 is as given in Table II.
result. Furthermore, since all the flows (of each type) are the The proof is given in the appendix. NC favors inelastic
same, these results are independent of the assumptions on how flows, hence always produces the least elastic u-put, as
the utility of flows of different lengths are computed. expected. Interestingly, AC2 always produces the most (or

Given the above definition of workload with infinite flows, equal to the most) elastic u-put. Finally, when the network is

the network state  n  m  remains unchanged and in a steady overprovisioned (i.e. few flows are competing for the network),

state by definition. The utility throughput for elastic and all four traffic controls generate the same elastic u-put. Figure

inelastic flows are also constant, respectively: 5 shows the four regions of the (n  m) space corresponding to
the four different rankings in Proposition 1.

ḠE  ρE uE aE  n  m  P  n  m For any fixed n, the value Ḡe is monotonically decreasing

m n 1- 0 with m, as increasing inelastic flows grab bandwidth away
 ρE uE  aE  n  m  from inelastic flows. Figure 8 shows Ḡe against m for a fixed

 naE  n  m  uE  aE  n  m  ; (10) n. The merit of this class of admission control algorithms is
that after certain point, the inelastic flows will not continue
ḠI  muI  aI  n  m  P  n  m
n m 1- 0 to take away bandwidth because it would be detrimental to
 muI  aI  n  m   themselves.

according to (4) and (5). The four traffic controls can be B. Comparing Inelastic Utility Throughput
compared by substituting aI  n  m  and aE  n  m  for these Similarly, let ḠNC CC AC1 and ḠAC2 denote the inelastic
I  ḠI  ḠI I
controls into the above u-put equations. u-put for NC, CC, AC1 and AC2 respectively.
Given the static workload, it is necessary to assume an order The comparative situation for inelastic u-put is more
of arrival for the n and m flows so that aE  n  m  and aI  n  m  complicated, as illustrated in Table III for a specific set of
can be defined for AC1 and AC2. For the following analysis, parameters. The ten different regions in Table III refer to those
we assume all the n elastic flows arrived before the m inelastic depicted in Figure 9.
flows. This assumption creates a certain bias to the results, As in the previous case, region (i) corresponds to the
which will be discussed at the end of Section VI.B. underloaded case where all traffic controls are the same.
Region (ii) is a small region where CC is better than AC2.
3 The order of arrival does matter for the evaluation of admission controls. This is the case when n and m are such that the offered load
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 12

n n n
(x) (xi) (x)
1/ε 1/ε 1/ε

(iv) (viii) (ix) (viii) (ix)

(vii)
(vii)
(ii) (iii) (ii) (iii) (iv) (iv)
1/α 1/α 1/α
(v) (iii)
(vi) (vi)
(i) (i) (i)
m m m
0 1/α 1/ε 0 1/α 0 1/α

Fig. 5. Regions of different comparative outcome Fig. 6. Regions of different comparative outcome Fig. 7. Regions of different comparative outcome
for elastic u-put for inelastic u-put for inelastic u-put, when k  ∞

¯Ḡe ¯Ḡi ¯Ḡi

AC1 AC1

AC2 AC2

AC2 NC NC

CC CC

CC
AC1
NC
m (i) (ii)(iii) (iv) (v) (vi) m (i) (iii) (iv) (vi) m
(i) (ii) (iii) (iv)

Fig. 8. Plot of Ḡe Fig. 9. Regions of different comparative outcome Fig. 10. Regions of different comparative outcome
for inelastic u-put for inelastic u-put, when k  ∞

TABLE III
system utility for the rest of the flows. Finally, regions (vii)
C OMPARING ḠI FOR DIFFERENT TRAFFIC CONTROLS
to (ix) correspond to the cases when n is large enough so
Comparison Region that AC2 would not admit any inelastic flows, and region (x)
GNC  GAC1  GCC  GiAC2 (i)
i i i corresponds to the case when n is so large that neither AC
GNC
i  GAC1
i B GCC
B Gi
i
AC2 (ii)
NC
Gi  Gi AC1 AC2 CC controls would admit any inelastic flows. In these severely
B Gi B Gi (iii)
NC AC1 AC2 CC
Gi B Gi B Gi B Gi (iv) overloaded cases, even though AC is out-performed by CC
AC1
Gi NC AC2 CC
B Gi B Gi B Gi (v)
and NC, all flows are enjoying very low utilities (the allocated
GAC1
i B Gi
AC2
B Gi
NC
B Gi
CC (vi)
GNC  G AC1 G CC G AC2  0 (vii) bandwidth is less than 1/α or 1/ε ).
i i B i B i
GNC
i B Gi
AC1 CC
B Gi B Gi
AC2  0 (viii)
AC1 NC CC AC2 
Figure 9 plots the inelastic u-put against m for a given
Gi B Gi B Gi B Gi 0 (ix)
Gi B Gi B Gi  GAC2
NC CC AC1  0 (x) value of n. The different regions of comparative outcomes are
i
indicated.

barely exceeds the capacity to offer all flows what is desired The above example clearly shows the rankings of the traffic

by inelastic flows (α ). By admitting one or two additional controls, although the exact characterization of these regions

inelastic flows than AC2, if the inelastic utility function is cannot be expressed in closed-form. We do have the following

not steep enough (k is not too large, hence there is still some asymptotic result when k tends to infinity (i.e. the inelastic

elasticity), then CC would be slightly better than AC2. For utility function approaches a step function.

regions (iii) to (iv), AC1 and AC2 are more effective (than Proposition 2: The relationship between the inelastic u-put
CC) by blocking some inelastic flows in order to gain higher for NC, CC, AC1 and AC2 asymptotically converges to that
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 13

TABLE IV TABLE V

C OMPARING ḠI OF DIFFERENT TRAFFIC CONTROLS AT k  ∞ T HE WORKLOAD SETS FOR WHICH WE COMPARED THE TRAFFIC

CONTROLS
Range of m and n Comparison Reg.
1C nα 1
0? m? α 0? n α GNC
i  GAC1
i  GCC
i  GiAC2 (i) Workload parameter Figures
A
1C nα 1C nε 1
α m? α 0? n α GNC
i  GAC1
i B GAC2
i B GCC
i  0 (iii) 1 ρE  αρI  1 0? ρ ? 2 α  0 7 05 Figure 11(a)
A A
1C nε 1 1 ρE  αρI 1
0? ρ α
α A m? α 0? n α GNC
i B GAC1
i B GAC2
i B GCC
i  0 (iv) 2  9 ? 2  0 7 05 Figure 11(c)
A
1
0? n 1
GAC1 GAC2 GNC  GCC 3 ρE  αρI  9 0? ρ ? 2 α  0 7 05 Figure 11(b)
α A m A α i B i B i i  0 (vi)
1C nα 4 ρE  αρI  1 ρ  0 7 50 0 7 01 ? α ? 07 5 Figure 13(a)
α m ? 1C αnε α1 ? n 1
ε GNC
i  GAC1
i B GCC
i  GAC2
i  0 (vii)
1C nε
A
1 1
A
1
5 ρE  αρI  1 ρ  0 7 95 0 7 01 ? α ? 07 5 Figure 13(b)
α A m? α α ? nA ε GNC B GAC1 B GCC  GAC2  0 (viii)
i i i i
6 ρE  αρI  1 ρ  1 7 40 0 7 01 ? α ? 07 5 Figure 13(c)
1 1 1
α A m α ? nA ε GAC1
i B GNC
i  GCC
i  GAC2
i  0 (ix) 7 ρE  αρI 
1
ρ  0 7 95 0 7 01 ? α ? 07 5 Figure 14(a)
9
1 1
α A m ε ? n GNC
i  GCC
i  GAC1
i  GAC2
i  0 (x) 8 ρE  αρI  9 ρ  0 7 95 0 7 01 ? α ? 07 5 Figure 14(c)
1C nε 1 1
α A m? α ε ? n GNC
i B GCC
i  GAC1
i  GAC2
i  0 (xi)

To compute the u-put for each traffic control, we plug

given in Table IV, as the inelastic utility function converges
PC  n  m into (4) and (5), where PC  n  m is defined in Table I.
to a step function (k D ∞ if uI  is a sigmoidal function).
The u-put for the four traffic controls are compared for the
The proof is given in the appendix. Figure 7 depicts the
workload sets shown in Table V. For all these cases, we set k 
regions in the (n  m) space that produce the rankings in
50 in the sigmoidal function (a reasonably stiff inelastic utility
Proposition 2. In this case, the boundaries between the regions
function); and ε  0  001 for AC1. The following notations for
are clear-cut. Region (ii) and (v) have disappeared because the
the workloads are adopted
CC and NC curves in Figure 10 drops sharply to zero as soon
as one extra inelastic flow is admitted above the thresholds ρE  λE  µ E

given by the AC1 and AC2 lines. For this asymptotic case, ρI  λI  µ I
it is possible to conclude that AC2 is always better than CC, ρ  ρE  αρI 
in the sense AC2 generates more u-put for both elastic and
The ratio ρE  αρI indicates the relative intensity of the
inelastic traffic.
elastic offered load to that of the inelastic offered load. The
In this comparison (for static workload), we have assumed
quantity ρ is the total offered load. Finally, recall α is the
that all n elastic flows arrived before any of the m inelastic
desired bandwidth for each inelastic flow (as a fraction of the
flows. This assumption helps the admission control schemes
bottleneck link bandwidth). In workload sets 1-3, we fixed
(AC1 and AC2) to generate more elastic u-put and less
the ratio of traffic intensities and desired rate, but varied the
inelastic u-put, when compared to the case where flows arrive
total offered load. In workload sets 4-8, we fixed the traffic
randomly. This bias does not materially affect the overall
ratios and total offered load, but varied the desired rate. These
results, since it does not exclusively favor one kind of control
sets of workloads covered a wide spectrum of network loading
over another kind.
scenarios.
VII. C ASE S TUDY: S TOCHASTIC W ORKLOAD
Now we are going to study the case when the flows are A. Comparison for Different Offered Load

finite. We have both elastic (file transfer) flows as well as Figure 11(a) shows the u-put of elastic and inelastic flows,
inelastic (holding time) flows in the network. The inelastic with equal traffic intensities ρE and αρI , as we vary total
flows are with arrival rate λI , average holding time 1  µI , a offered load ρ . When ρ is small, we can hardly differentiate
desired transmission rate of α , and a sigmoidal utility function the u-put for different controls. For each control, the u-put
with a sufficiently large k. The elastic flows have arrival rate increases as ρ increases. This means it does not matter which
λE , average file size 1  µE , and a concave utility function as control algorithm we use for inelastic flows when we are not
(9). in the congested regime.
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 14

0.025 0.025 0.03

CC
NC
AC1 0.025
0.02 AC2 0.02

0.02
0.015 0.015
0.015
0.01 0.01
0.01

0.005 0.005 CC CC
NC 0.005 NC
AC1 AC1
AC2 AC2
0 0 0
0 0.5 1 1.5 2 0 0.5 1 1.5 2 0 0.5 1 1.5 2

10 18 2
CC CC CC
9 NC 16 NC 1.8 NC
AC1 AC1 AC1
8 AC2 14 AC2 1.6 AC2
7 1.4
12
6 1.2
10
5 1
8
4 0.8
6
3 0.6
2 4 0.4
1 2 0.2
0 0 0
0 0.5 1 1.5 2 0 0.5 1 1.5 2 0 0.5 1 1.5 2
(a) ρE : αρI  1:1 (b) ρE : αρI  1:9 (c) ρE : αρI  9:1

Fig. 11. Elastic (top) and inelastic (bottom) utilities vs. ρ

When the total offered load approaches the network Intuitively, this is exactly caused by the all-or-nothing nature
capacity, the service starts to degrade. The u-put is in a of the utility function for inelastic flows.
downward trend for all controls when ρ , 1. However, the In summary, we make two observations from the analysis
result is more graceful for some controls than others. Under of this workload:
aggressive admission control (AC1) or no control (NC), the 
Both elastic and inelastic u-put depend on offered load
elastic u-put drops quickly to zero when ρ increases to 1.
irrespective of the traffic control. When offered load
When ρ , 1, the NC case becomes unstable (elastic population
is low, the u-put is low; as offered load approach the
blows up) whereas the u-put in the AC1 case will stay at almost
network capacity, the u-put peaks; as offered load exceed
zero. The fair congestion control (CC) and fair admission
network capacity, the u-put declines, gracefully for some
control (AC2) perform more gracefully as total offered load ρ
controls but much more precipitously for other controls.
increases to and beyond network capacity. AC2 always yields 
The admission control AC2 consistently out-performs fair
higher elastic u-put compared to the other three controls.
congestion control (CC) in terms of both elastic and
inelastic u-put. AC1 performs better than CC for inelastic
The overall trend for inelastic u-put is similar. When the u-put but worse for elastic u-put. The No Control (NC)
total offered load is less than network capacity, the u-put case becomes unstable prematurely (when ρ approaches
gradually increases at an almost equal rate for all controls. capacity). So no definitive statements can be made for
As ρ approaches network capacity, the inelastic u-put reaches AC1 or NC relative to CC.
its peak for all controls. After that, the NC case first becomes
unstable (due to total population blowing up). For the two
B. Comparison for Different Traffic Mixes
admission control cases, as AC1 more aggressively admits
inelastic flows it performs the best; but AC2 delivers almost Figures 11(b) and 11(c) are similar to Figure 11(a) but are
the same performance. Both admission controls perform for different traffic mixes. They show the utility throughput
significantly better than fair congestion control (CC) when for elastic and inelastic flows with traffic ratio ρE : αρI equal
ρ , 1. The u-put of CC is almost zero in this congested regime. to 1:9 and 9:1 respectively, instead of 1:1 in Figure 11(a).
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 15

From these figures, we can see that the observations made fair congestion control, then they may be allocated less
at the end of the last section still hold. In particular, AC2 still instantaneous bandwidth than they desire. However, this does
consistently out-performs CC for these workloads. There are not affect the departure times of these flows. Therefore, under
some quantitative differences as discussed below. fair congestion control it is possible to receive arbitrarily
In Figure 11(b), when the majority of the flows are inelastic, heavy offered load of holding time flows without affecting
the choice of traffic control has a more significant impact, the population size, as indicated by the analysis in Section
to both inelastic as well as elastic u-puts. When admission IV.
control (AC1 or AC2) is applied, inelastic u-put degrades
Similarly if holding time flows are subject to admission
gracefully from the peak in comparison to the fair congestion
control without any congestion control, the original offered
control case (CC). Intuitively, the reason is that the inelastic
load may be compressed since whatever the network cannot
utility function prefers fewer flows operating at desired rate
handle would have been blocked. But in this case, the
rather than more flows operating at reduced rate. For elastic
compression affects those blocked flows only, rather than all
u-put, fair admission control (AC2) is able to significantly out-
flows. So in this situation, the network is also stable for
perform not only CC, but also AC14 .
arbitrary offered load as shown in Section IV.
In Figure 11(c), when the majority of the flows are elastic,
the impact of the control used for inelastic flows is small, as The offered load presented by the file transfer flows,
expected. It is worth noting that as ρE approaches the network however, are not compressible. If less bandwidth is allocated
capacity (in this case, it means ρ approaches 1  0  9 E 1  11) the to these flows, the file transfers will progress more slowly, and
elastic u-put quickly drops to zero no matter which control is more load tend to be accumulated for later. In this case, it is
used. This raises an interesting question: What is the set of well-established that if ρ 3 1 the system is not stable.
offered load for which the system is stable (the population does We state without proof that in a network of mixed
not increase to infinity in steady state) for each traffic control flows (both file transfer as well as holding time type of
we are studying? In the next subsection, we take a detour to flows), if the traffic control adopts either CC or admission
discuss this question, before continuing with comparing traffic control (in the form of AC2 or AC1 with ε 0, then it
3
controls under other workloads. is sufficient to require ρE 1 to ensure the network with
+

mixed traffic is stable. Intuitively, this can be rationalized in

C. Stability the following sense. If ρE 1, then consider the network’s
+

A M/M/∞ queue is stable as long as the offered load is capacity be reduced by ρE , and there is still finite capacity
less than the service capacity; in other words, ρ is less than left. Since the traffic controls for holding time flows can
1. In Section IV, however, we plotted the u-put of a network maintain stability for arbitrary offered load, as the file transfer
with homogeneous traffic for ρ greater than 1. Similarly, in workload accumulates eventually the holding time flows will
this section we consider workloads with ρ greater than 1 (see be compressed sufficiently to accommodate the file transfer
Table V). Why is the system still stable when ρ is greater than load [18]. Note, however, the NC case is an exception. Since
1? What is the stability criterion for our models? there is no control whatsoever on the inelastic flows, it is
It turns out this depends on how we model the flows. By necessary to have ρE  αρI + 1 to ensure stability.
modeling (inelastic) flows as holding time flows, it means
In reality, our results demonstrate this is true. In Figure
under certain traffic controls the offered load is compressible
11(a), we see the u-put is positive when the inelastic flows
[18]. For example, if the inelastic flows are subject to
are under either fair congestion control or admission control.
4 This is a very interesting property of the model, namely AC1 and AC2
In Figure 11(b), although we only plot u-put for 0  ρ  2
give similar aggregate performance for inelastic flows; but AC2 is able to give
significantly better aggregate performance for elastic flows. A detailed study
(hence 0  ρE  0  2) for easy comparison, we did verify that
of the reason for this behavior is given in a separate paper [22]. the network is still stable for other values of ρE + 1. Finally,
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 16

1200 20
CC CC
NC 18 NC
1000 AC1 AC1
AC2 16 AC2
14
800
12
600 10
8
400
6
4
200
2
0 0
0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

Fig. 12. Mean population of elastic (left) and inelastic (right) flows vs. ρ , with ρE : αρI  1:1

for Figure 11(c), it is evident the network is only stable up to likely means more compression on the inelastic flows;
roughly ρ + 1  1 (hence ρE + 1). hence more gain by the elastic flows.
Furthermore, we can plot the mean population size against 
For small α , the performance of different traffic
total offered load ρ , as shown in Figure 12. Under light load, controls tends to be similar. For larger values of α ,
the mean population size is roughly the same for different the performance difference between different controls
traffic controls. At ρ  1, the NC case first blows up, namely widens. We attribute this to the effect of discretization.
the elastic population goes to infinity. As ρ approaches 2 (i.e. For larger α values, the difference between the effect of
ρE approaches 1), the elastic population under the other three admitting a flow versus not admitting a flow is amplified.
controls also increase abruptly. For 1  ρ  2, it is interesting Just like packing large objects into a box, it becomes
to note that the elastic population under AC1 is significantly more difficult to achieve good efficiency as well.
more than CC and AC2; and AC2 is the only control that can 
AC2 is always best for elastic u-put, while AC1 and NC
keep the elastic population low in this stable but congested are the worst for elastic flows. For inelastic u-put, AC1
regime. and NC perform better. But AC2 performs at least as good
as CC if not better. So our previous conclusion about
D. Sensitivity to Different Playback Rates superiority of AC2 over CC remains true.
Another important parameter of the workload is the desired 
For the case when ρ exceeds 1, the NC case becomes
rate (or playback rate) α . In the above workloads, we picked unstable as we found out before. Fair congestion control
a playback rate of 0  05 (equivalent to 5% of the network (CC), while remains stable, performance quite poor in
capacity). In this section, we study how the conclusion might inelastic u-put. This is due to the steep inelastic utility
change for different playback rates. function which values under-allocated inelastic flows very
Figures 13(a), 13(b) and 13(c) plot the u-put against little.
different α under moderate load (ρ  0  5), heavy load (ρ 

0  95), and highly congested load (ρ  1  4) respectively,

all with balanced traffic mix. We can make the following
observations: Next we varied the traffic mix while keeping ρ  0  95,

Generally speaking, as α increases, the elastic u-put as shown in Figure 14. The above observations about the
increases whereas the inelastic u-put decreases. This can general trends and the superiority of AC2 over CC remains
be readily explained. If the traffic control is admission true. In addition, Figure 14(a) and 14(c) show the sensitivity
control, then a higher playback rate means the probability of α when the majority of flows is inelastic and the majority
of accepting an inelastic flow would be lower; therefore of flows is elastic respectively. As expected, the value of α
more resources are left to elastic flows. If the traffic has more effect when the majority of flows is inelastic (note,
control is fair congestion control, a higher playback rate Figure 14(a) and 14(c) use different scales for the y-axes).
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 17

0.0265 0.04 0.05

CC CC CC
0.026 NC NC 0.045 AC1
AC1 AC1 AC2
0.0255 AC2 0.035 AC2 0.04
0.025 0.035
0.0245 0.03 0.03
0.024 0.025
0.0235 0.025 0.02
0.023 0.015
0.0225 0.02 0.01
0.022 0.005
0.0215 0.015 0
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

25 45 30
CC CC CC
NC 40 NC AC1
AC1 AC1 25 AC2
20 AC2 35 AC2

30 20
15
25
15
20
10
15 10

5 10
5
5

0 0 0
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
(a) ρ  07 5 (b) ρ  0 7 95 (c) ρ  17 4

Fig. 13. Elastic (top) and inelastic (bottom) utilities vs. α with ρE : αρI  1:1

0.04 0.04 0.026

CC CC CC
NC NC 0.024 NC
0.035 AC1 AC1 AC1
AC2 0.035 AC2 AC2
0.022
0.03

0.03 0.02
0.025
0.018
0.02
0.025 0.016
0.015
0.014
0.02
0.01 0.012

0.005 0.015 0.01

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

90 45 10
CC CC CC
80 NC 40 NC 9 NC
AC1 AC1 AC1
70 AC2 35 AC2 8 AC2
7
60 30
6
50 25
5
40 20
4
30 15
3
20 10 2
10 5 1
0 0 0
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
(a) ρE : αρI  1:9 (b) ρE : αρI  1:1 (c) ρE : αρI  9:1

Fig. 14. Elastic (top) and inelastic (bottom) utility vs. α with ρ  0 7 95

VIII. C ONCLUSION letting inelastic flows adopt other traffic controls such as

As the Internet is increasingly being used to support both admission control.

inelastic multimedia applications as well as traditional elastic To investigate the merit of this viewpoint, we propose a
applications, a central issue is how these applications should methodology to compare the different traffic controls based
share network bandwidth. In this paper, we challenge the on utility maximization. We model the traffic as deterministic
conventional wisdom of requiring all flows in the network or stochastic workloads composed of file transfer (elastic)
to be TCP friendly on a per-flow basis. Instead, we propose flows and holding time (inelastic) flows. Based on some
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 18

TABLE VI
general assumptions on the form of utility functions, we derive
N O . OF I NELASTIC F LOWS A DMITTED FOR E ACH R EGION IN F IGURE 5
a systematic procedure for computing the rate the network
generates aggregate utility of elastic and inelastic flows. We Region (i) Region (ii) Region (iii) Region (iv)
AC1 m m FG 1 @ nε G α H FG 1 @ nε G α H
call these the elastic and inelastic utility throughputs (u-puts).
AC2 m FG 1 @ nα G α H FI 1 @ nα J α H FG 1 @ nα G α H
Different traffic controls can then be compared based on
comparing these u-puts.
Outside of region (i), namely when  n  m  α , 1, NC
From analysis based on this methodology, we find a form
allocates no bandwidth to elastic flows, hence it is ranked
of TCP-friendly admission control, when applied to inelastic
lower than the other three controls. The comparison of AC1,
flows, out-performs TCP-friendly congestion control in terms
AC2 and CC depends on how many inelastic flows are
of both elastic as well as inelastic u-puts. This implies, from
admitted. Given that the elastic flows all arrive before the
maximizing the social welfare point of view, it is better to be
inelastic flows, Table VI lists the number of inelastic flows
TCP-friendly at the traffic class aggregate level rather than at
admitted by AC1 and AC2 in different regions respectively.
the per-flow level.
Given this information, and the traffic control definition in
We believe both the methodology and the conclusion
Equation 7, it is straightforward to verify that the rankings in
opens up new directions for further research. One may
Table II are true.
continue to explore for more optimal form of traffic control
than stay content with TCP-friendly admission control. The
Proof of Proposition 2
methodology itself can be further improved as it involves
For AC1 and AC2, the allocated bandwidth for each
a number of strong assumptions. For example, it would be
admitted flow is always α . The comparison (hence the
interesting to model the retry behavior of the rejected flows. In
ranking) of AC1 and AC2 boils down to counting the number
our analysis, while the conclusions under light load and heavy
of inelastic flows admitted. Therefore, the ranking of AC1
load are clear-cut, the moderate load case deserves further
and AC2 are the same in region (i), and AC1 generates more
scrutiny. When applying our methodology to the stochastic
inelastic u-puts in the rest of the regions, based on Table VI.
workloads, we rely mostly on numeric methods to solve for the
Many of the regions correspond to special cases when
large Markov chains involved. We believe there are additional
allocations are zero for specific traffic controls. Since inelastic
asymptotic results to be obtained. It would also be interesting
flows all arrive after the elastic flows, above the line nα  1
to remove the exponential file size assumption and see how
(region (vii) or higher), aI  n  m  is zero for AC2; and above
it affects the conclusions. Finally, how to implement TCP-
the line nε  1 (region (x) and higher), aI  n  m  is zero for
friendly admission control in a distributed fashion is also a
both AC1 and AC2. Given that uI  is a step function, to the
very challenging problem not addressed in this paper.
right of the line mα  1 (region (vi), (ix) and (x)), aI  n  m  is
zero for both CC and NC.
A PPENDIX
The regions when most of the allocations are greater than
Proof for Proposition 1 zero (regions (i), (iii), (iv) (vii) and (viii)) are of more interest
From Equation 10, the u-put equation for elastic flows is of in comparison. In each case, it is straightforward to derive the
the form naE  n  m  uE  aE  n  m  for any traffic control. Since rankings in Table IV based on Equation 8 and Table VI that
xuE  x  is an increasing function in x, we can compare the gives the number of inelastic flows admitted.
ranking of the four traffic controls based on the respective
R EFERENCES
allocation functions aE  n  m  , if all m flows are admitted.
[1] D. E. McDysan and D. L. Spohn, ATM — Theory and Application. New
For region (i) in Figure 5, all m inelastic flows are admitted.
York, NY, USA: McGraw-Hill, 1995.
The aE  n  m  is the same for all four controls, and their elastic [2] R. Braden, D. Clark, and S. Shenker, “Integrated services in the internet
u-puts are the same. architecture: an overview,” IETF RFC1633, June 1994.
TECH REPORT SUBMITTED FOR JOURNAL PUBLICATION, UPDATED OCTOBER 2006 19

[3] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An

architecture for differentiated services,” IETF RFC2475, Dec. 1998.
[4] E. Osborne and A. Simha, Traffic Engineering with MPLS. Cisco Press,
Mar. 2002.
[5] S. Shenker, “Fundamental design issues for the future internet,” IEEE
Journal on Selected Areas in Communications, vol. 13, Sept. 1995.
[6] J. Mahdavi and S. Floyd, “TCP-friendly unicast rate-based flow control,”
Technical note sent to the end2end-interest mailing list, Jan. 1997.
[7] M. Handley, S. Floyd, J. Padhye, and J. Widmer, “TCP friendly rate
control (TFRC): Protocol specification,” IETF RFC3448, Jan. 2003,
proposed Standard. [Online]. Available: [Link]
txt
[8] J. Padhye, J. Kurose, D. Towsley, and R. Koodli, “A model based TCP-
friendly rate control protocol,” in Proceedings NOSSDAV. Basking
Ridge, NJ: International Workshop on Network and Operating System
Support for Digital Audio and Video (NOSSDAV), June 1999.
[9] L. Massoulié and J. Roberts, “Bandwidth sharing: Objectives and
algorithms,” IEEE/ACM Transactions on Networking, vol. 10, 2002.
[10] M. Chiang, S. Zhang, and P. Hande, “Distributed rate allocation for
inelastic flows: Optimization frameworks, optimality conditions, and
optimal algorithms,” in Proceedings of INFOCOM 2005, Mar. 2005.
[11] J.-W. Lee, R. R. Masumdar, and N. B. Shroff, “Non-convex optimization
and rate control for multi-class services in the internet,” IEEE/ACM
Transactions on Networking, vol. 13, no. 4, pp. 827–840, 2005.
[12] L. Breslau, E. Knightly, S. Shenker, I. Stoica, and H. Zhang,
“Endpoint admission control: Architectural issues and performance,” in
Proceedings of SIGCOMM 2000, Aug. 2000.
[13] D. M. Chiu and R. Jain, “Analysis of the increase and decrease
algorithms for congestion avoidance in computer networks,” Computer
Networks and ISDN Systems, vol. 17, 1989.
[14] R. Jain, D. M. Chiu, and W. Hawe, “A quantitative measure of fairness
and discrimination for resource allocation in shared computer systems,”
DEC, DEC Technical Report DEC-TR-301, Sept. 1984.
[15] A. Demers, S. Keshav, and S. Shenker, “Analysis and simulation of a
fair queueing algorithm,” in Proceedings of the ACM SIGCOMM’89,
Sept. 1989.
[16] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control in
communication networks: Shadow prices, proportional fairness and
stability,” Journal of the Operational Research Society, vol. 49, pp. 237–
252, 1998.
[17] J. Mo and J. Walrand, “Fair end-to-end window-based congestion
control,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–
567, 1998.
[18] P. Key, L. Massoulié, A. Bain, and F. Kelly, “A network flow model for
mixtures of file transfers and streaming traffic,” in Proceedings of ITC
18, Berkin, Germany, Sept. 2003.
[19] J. Roberts, “A survey on statistical bandwidth sharing,” Computer
Networks, July 2004.
[20] T. Bonald and A. Proutiere, “On performance bounds for the
integration of elastic and adaptive streaming flows,” ACM SIGMETRICS
Performance Evaluation Review, vol. 32, pp. 235–245, 2004.
[21] R. Howard, Dynamic Programming and Markov Processes. Cambridge
MA, USA: MIT Press, 1960.
[22] A. S.-W. Tam, D. M. Chiu, J. C. S. Lui, and Y. C. Tay, “A case for
TCP-friendly admission control,” 2006, proceedings of IEEE IWQoS.