A game-theoretic approach towards congestion control in communication networks.
Most of the end-to-end congestion control schemes are "voluntary" in nature and critically depend on end-user cooperation. We show that in the presence of selfish users, all such schemes will inevitably lead to a congestion collapse. Router and switch mechanisms such as service disciplines and buffer management policies determine the sharing of resources during congestion. We show, using a game-theoretic approach, that all currently proposed mechanisms, either encourage the behaviour that leads to congestion or are oblivious to it.We propose a class of service disciplines called the Diminishing Weight Schedulers (DWS) that punish misbehaving users and reward congestion avoiding well behaved users. We also propose a sample service discipline called the Rate Inverse Scheduling (RIS) from the class of DWS schedulers. With DWS schedulers deployed in the network, max-min fair rates constitute a unique Nash and Stackelberg Equilibrium. We show that RIS solves the problems of excessive congestion due to unresponsive flows, aggressive versions of TCP, multiple parallel connections and is also fair to TCP.
INTRODUCTION
Most of the end to end congestion control schemes [23,
17, 32, 26, 16] are voluntary in nature and critically depend
on end-user cooperation. The TCP congestion control algorithms
[23, 5, 20, 21, 19, 9] voluntarily reduce the sending
rate upon receiving a congestion signal such as ECN [25],
packet loss [14, 10, 18] or source quench [24]. Such congestion
control schemes are successful because all the end-users
cooperate and volunteer to reduce their sending rates using
IBM India Research Lab, Hauz Khas, New Delhi - 110016,
INDIA.
y Indian Institute of Technology, Delhi, Hauz Khas, New
z Network Appliance, CA, USA.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
similar algorithms, upon detection of congestion.
As the Internet grows from a small experimental network
to a large commercial network, the assumptions about co-operative
end-user behaviour may not remain valid. Factors
such as diversity, commercialization and growth may lead to
non-cooperative and competitive behaviours [12] that aim
to derive better individual utility out of the shared Internet
resources.
If an end-user does not reduce its sending rate upon congestion
detection, it can get a better share of the network
bandwidth. The
ows of such users are called unresponsive
ows [8, 7]. Even responsive
ows that react to congestion
signal can get unfair share of network bandwidth by being
more conservative in reducing their rates and more aggressive
in increasing their rates. Such
ows are termed as
TCP-incompatible
ows [8, 7]. Even TCP-compatible
ows
such as dierent variants of TCP give dierent performance
[21] under dierent conditions. Such behaviours though currently
not prevalent, are present in the Internet, and pose
a serious threat to Internet stability [12, 8]. If widespread,
such behaviours may lead to a congestion collapse of the Internet
(see Section 2). Therefore it is important to have an
approach towards congestion control that is not dependent
on cooperative end users voluntarily following an end-user
behaviour from a class of predened behaviours.
In this paper we propose a game-theoretic approach towards
congestion control. The crux of the approach is to
deploy schedulers and/or buer management policies at intermediate
switches and routers that punish misbehaving
ows by cutting down their rates thereby encouraging well
behaved
ows. There have been discussions [29] on punishing
misbehaving users but they do not talk about such
punishments in a game-theoretic framework. We propose a
class of scheduling algorithms called the Diminishing Weight
Scheduling (DWS) that punish misbehaving
ows in such
a way that the resulting game-theoretic equilibrium (Nash
Equilibrium) results in fair resource allocations. We show
that with DWS scheduling deployed in the network, max-min
fair rates [4] constitute a Nash as well as a Stackelberg
Equilibrium. Thus, with DWS scheduling deployed,
the \best selsh behaviour" for each user is to estimate its
fair rate and send tra-c at that rate.
Our game-theoretic approach is very similar to that proposed
by Shenker [27] to analyze switch service disciplines.
However, Shenker uses a discrete queueing theoretic model
of input tra-c which does not accurately model the tra-c
in today's data networks. Moreover, Shenker's analysis is
restricted to a single switch/router and does not extend to
an arbitrary network in a straight forward manner. We use a
continuous
uid-
ow based input tra-c model which is more
realistic and amenable to analysis in an arbitrary network.
This makes our approach more practical and applicable to
networks such as the Internet.
The steepness of the diminishing weight function determines
the amount of penalty imposed on a misbehaving
ow.
Steeper weight functions impose stricter penalties to misbe-
having
ows. As the weight function becomes
at, DWS
approaches WFQ scheduling which imposes no penalty on
a misbehaving
ow. We also present a sample service discipline
called Rate Inverse Scheduling (RIS) where the diminishing
weight function is the inverse of the input rate. By
using dierent weight functions in DWS, the switch designers
and ISPs can choose from a variety of reward-penalty
proles to meet their policy requirements.
With DWS deployed, we show that it is in the interest
of each individual end-user to follow a TCP-style in-
crease/decrease algorithm. Using simulations we show that
end-users using dierent versions of TCP are actually able
to converge to their fair rates, even in the presence of misbehaving
users.
In Section 2 we present our game-theoretic formulation
and show that in the presence of selsh users, the current
resource management policies will lead to a congestion col-
lapse. In Section 3 we present the DWS scheduling algorithm
and discuss its properties in Section 4. We present
some preliminary simulation results in Section 5. We conclude
in Section 6. The proofs are provided in the Appendix.
2. A GAME-THEORETIC MODEL OF A
Consider a link of capacity C shared by N users. There
is a su-ciently large shared buer, a buer management
policy, and a service discipline to partition the link capacity
among the users. Assume that user i sends a constant rate
tra-c
ow at a rate r i (the input rate). Some of this trafc
may be dropped due to buer over
ows. Assume that,
in steady state the tra-c of user i is delivered at the destination
with an average output rate
output rate is a function of sending rate of all the N users,
the switch service discipline S, and the buer management
policy B. Mathematically, this is written as
denotes the N-dimensional vector
of input rates and
denotes the N -
dimensional vector of output rates and
SB () is the function
(called the resource management function) dependent
on scheduling discipline S and buer management policy B
mapping the vector of input rates to the vector of output
rates.
Consider a network comprising multiple nodes and links.
Assume that tra-c of user i traverses links l 1
the resource management function at link l j be
denote the vector of input rates of all users at link l j . The
input rate of user i at link l 1 is r 1
. Since we assume
that all users send tra-c at a constant rate, the output rate
of user i at link l 1 is also a constant given by
Therefore, the input rate of user i at link l 2 will also be
constant given by r 2
Similarly we have:
Output
Rate
(Mbps)
Input Rate (Mbps)
All other flows sending at 1 Mbps
FCFS
RED
FRED
LQD
RIS

Figure

1: Uncongested link0.51.52.53.5
Output
Rate
(Mbps)
Input Rate (Mbps)
All other flows sending at 4 Mbps
FCFS
RED
FRED
LQD
RIS

Figure

2: Congested link
The nal output rate of the user will be given by:
In general, a user's utility (or satisfaction) depends on
its output rate, loss rate and end-to-end delay. However,
for a majority of applications the output rate is the most
important factor determining the user's utility. For instance,
\re-hose applications" described in [29] are completely loss
tolerant. For streaming media applications, loss tolerance
can be obtained using forward error correction techniques
[2]. For bulk transfer applications, loss tolerance can be
achieved using selective retransmissions [4]. Therefore, for
simplicity, we assume that a user's utility is an increasing
function of its output rate only. The class of such utility
functions U
, is formally dened as
1. U 2 U
maps a user's output rate
to a real-valued
non-negative utility,
2. U(
If user i was to act in a selsh manner, it would choose a
sending rate r i which would maximize its utility (and hence
the output rate), irrespective of the amount of inconvenience
caused (loss of utility) to other users. Consider what will
happen in such a scenario with dierent packet service disciplines
and buer management policies.
Consider a link of capacity shared by ve
users sending tra-c at a constant rate. Figures 1 and 2
1 Later, in Section 4 we also consider the class of utility function
U
l where a user's utility is also dependent on its loss
rate.
Legend Scheduling discipline Buer management policy
FCFS First come rst serve Shared buers, drop tail
Worst case fair weighted fair queueing Per
ow buers, drop tail [3]
LQD First come rst serve Longest queue tail drop [30]
First come rst serve Dynamic threshold [6]
RED First come rst serve Random early drop [10]
FRED First come rst serve Flow RED [18]
RIS Rate inverse scheduling Per
ow buers, drop tail

Table

1: Notations for schedulers and buer management policies
A
O
Link Speeds:
L, M, N: 1 Mbps
O,

Figure

3: Congestion collapse in a sample network
show the variation in a user's output rate as a function of
its input rate for dierent scheduling disciplines and buer
management policies. Refer to Table 1 for notations.
For FCFS, the output rate of a user (and hence the user's
utility) always increases as its input rate increases. How-
ever, the slope of the graph depends on the input rate of
other users. In such a case, there is an incentive for each
user to increase its sending (input) rate, irrespective of what
other users are doing. If each user was to act selshly, to
maximize its own utility, the link will end up becoming heavily
congested with each user sending tra-c at its maximum
possible rate and receiving only a tiny fraction of the tra-c
sent. This is characterized by the concept of Nash Equilibrium
[11].
the utility of player i when the player adopts the strategy
and all the other players adopt the strategy . A strategy
prole   is a Nash Equilibrium if, for every player i,
for all  i is the set of strategies that user i
can adopt.
In other words, a Nash Equilibrium is a strategy prole
where no user has an incentive to deviate unilaterally from
its strategy. If all the users are selsh and non-cooperating
they would eventually adopt strategies that constitute a
Nash Equilibrium.
Here, the vector of input rates r constitutes a strategy
prole, and each user's utility U(
) is a monotonically increasing
function of its output rate
. For FCFS, RED, and
DT resource management policies, the only Nash Equilibrium
is when the input rates approach innity.
Therefore, it is appropriate to say that FCFS encourages
behaviour that leads to congestion. In a network comprising
multiple nodes and links, selsh user behaviour will lead to
worse disasters [7, 8] (similar to the congestion collapse)
where input rate of each user will approach their maximum
possible and output rates will approach zero. To see this,
consider the network and
ows shown in Figure 3. Assume
that FCFS policy is deployed at every link. Every user will
send tra-c at the rate of the access link, 10 Mbps, and
will get a net output rate of less than 100Kbps at the nal
destination.
Now consider WF2Q. The output rate of a user remains
equal to its input rate as long as it is less than or equal
to its fair rate. When, the input rate becomes larger than
the fair rate, the output rate remains constant at fair rate
(C=N ). Above is true irrespective of the input rates of other
users. In such a scenario, a selsh user will increase its input
rate till the fair rate. However, a user has no incentive
to increase its input rate beyond the fair rate, nor does it
have any incentive to keep its input rate down to the fair
rate. Therefore, in a network comprising multiple nodes and
links, when a selsh user neither knows its fair rate, nor the
resource management policies employed (FCFS or WFQ),
it may simply nd it convenient to keep on increasing its
input rate much beyond the fair rate. For WF2Q, LQD,
and FRED, it seems that any vector of input rates where
each user's input rate is more than C=N constitutes a Nash
Equilibrium. We say that such policies are oblivious to congestion
causing behaviour.
Observe from Figures 1 and 2 that all the resource management
policies (except RIS which will be described in following
sections) either encourage behaviour leading to congestion
or are oblivious to it.
For end-to-end congestion control schemes to be eective
in the presence of selsh users (and in the absence of other
incentives such as usage based charging, congestion pricing
etc.), a resource management mechanism in the interior of
the network (i.e., the tra-c police) is needed that punishes
misbehaving users and rewards well behaved users, while
what is present in today's networks is just the opposite. In
the following section we describe a class of service disciplines
that achieve the purpose of rewarding the well behaved users
and punishing the misbehaving users.
3. DIMINISHING WEIGHTSCHEDULERS
The class of Diminishing Weight Schedulers (DWS) is dened
for the idealized
uid-
ow tra-c model. It is derived
from the Generalized Processor Sharing (GPS) scheduling
algorithm [22]. Consider a link of capacity C shared by
users sending tra-c as N distinct
ows. Let A i (t) be
the amount of tra-c of
ow i entering the scheduler buer
in the interval (0; t] and S i (t) be the amount of tra-c of
ow i served by the scheduler in the interval (0; t]. Dene
the backlog of
ow
i at time t > 0 as the total
system backlog at time t as
(t). Dene the
input rate of a
ow at the link at time t as r i
and dene the output rate of
ow i at the link at time t as
A GPS scheduler [22] on a link may be dened as the
unique scheduler satisfying the following properties:
Flow Conservation:
0: (2)
Work Conservation:
If B(t) > 0; then
GPS Fairness:
where  i is the GPS weight assigned to
ow i.
The
ow conservation property implies that for a
ow, the
tra-c served cannot be more than the tra-c arrived. The
work conservation property implies that if there is a non-zero
backlog in the system, then the link is not kept idle. The
fairness property implies that the output (service) rates of all
the backlogged
ows will be proportional to their respective
GPS weights, while the output rates of non-backlogged
ows
will be smaller.
GPS assigns constant weights to all the
ows. DWS differ
from GPS in this regard. In DWS, each bit gets a GPS
weight that is a decreasing function of that bit's arrival (in-
put) rate. If the bit at the head of the queue of
ow i at time
t arrived at time  i (t), then in DWS,  i
where W (r) is the diminishing weight function, which is a
continuous and strictly decreasing function of r. The class
of DWS schedulers is formally dened as the schedulers satisfying
the following properties:
Flow Conservation:
Work Conservation:
If B(t) > 0; then
DWS Fairness:
where  i is the DWS weight for
ow i. Thus, DWS rewards
ows with small rates by assigning them large GPS weights
and punishing
ows with large rates by assigning them small
GPS weights. The amount of punishment depends upon the
steepness of the diminishing weight function. If it is a
at
function such as the 1=log(r) function, then DWS resembles
the GPS scheduling. If the diminishing weight function is
steep then strict penalties are enforced to misbehaving users.
The DWS weights  may be set in accordance with the pric-
ing, resource sharing or other administrative policies, in the
same way the as GPS weights  are set when GPS based
schedulers are deployed.
The Rate Inverse Scheduler (RIS) is a special case of the
DWS scheduler where the diminishing weight function is
the inverse function (W 1=r). Thus the DWS fairness
condition for RIS reduces to the following:
RIS Fairness:
Assume, for simplicity that all DWS weights are set to 1
and all users send tra-c at a constant rate. Thus, all output
rates will also be constant. From the
ow conservation
property it follows that
. The DWS fairness condition
can be simplied as follows:
It follows that if two
ows i and j are backlogged, then
We now prove some important properties of DWS schedul-
ing. Dene the congestion characteristic function G(x; r) as:
Dene the rate constant  for a link with a vector of input
rates r as :
Theorem 3.1 (Rate Constant). Rate constant  as
dened in Eq 11 is unique and the output rate of
ow i is
uniquely given by
The proof is provided in the Appendix. Hence, given the
input rates of
ows, using the rate constant  it is possible
to uniquely determine the output rate of any
ow. We dene
the fair rate f as follows:
Lemma 3.1. The fair rate f as dened in Eq.12 is unique.
The proof is provided in the Appendix. The output rate
can be represented in terms of the fair rate as follows:
We now show that if the input rate of a
ow is less than or
equal to the fair rate, then the
ow will get all its bits transmitted
without loss, otherwise it will suer a loss according
to the diminishing weight function W ().
Lemma 3.2. If r i  f then
f .
Proof. Case
W (f ), since W () is a strictly decreasing function. Hence we
get r i =W (r i )  f=W (f ). Using Eq.12 we get r i  :W (r i ).
Therefore,
Case In this case we get r i =W (r i ) > f=W (f ),
since W () is a strictly decreasing function. Use Eq.12 to get
f .
The above behaviour is also evident from Figures 2 and
7. We say that a
ow i contributes to a link's congestion
scheduling, the output rate of a
ow remains equal to its input rate as long as the
ow does
not contribute to congestion. However, as soon as the
ow
contributes to congestion its output rate begins to decline
according to the diminishing weight function W (). In DWS,
dierent weight functions can be chosen to meet specic
policy requirements. Observe from Figure 7 that the weight
function W imposes a very small penalty on
misbehaving
ows and is very similar to WFQ whereas the
weight function W imposes very strict penalties.
The following result follows from Lemma 3.2
Corollary 3.1. The output rate for any
ow i is less
than equal to the fair rate (
We now establish the relationship between the fair rate f ,
the link capacity C and the number of users N . It also
suggests that if all the users are equal (with equal DWS
weights), then the fair rate is indeed fair.
Lemma 3.3. Fair rate f is greater than or equal to C=N .
The proof is provided in the Appendix. From Lemmas
3.2 and 3.3, observe that if a user i's input rate is C=N , its
output rate will also be equal to C=N (since r
and hence DWS results in fair allocation of resources.
Lemma 3.4. If a
ow i is experiencing losses (
then decreasing the
ow's input rate by a su-ciently small
amount will either increase its output rate, or leave it unchanged
(i.e. 9- > 0 s.t. if r 0
The proof is provided in the Appendix.
Lemma 3.5. If a
ow i is not experiencing losses, then increasing
the
ow's input rate by a su-ciently small amount
will either increase its output rate or leave it unchanged (i.e.
The proof is provided in the Appendix.
The above two lemmas establish that a
ow experiencing
may have an incentive to reduce its input
rate, whereas a
ow experiencing no losses may have incentive
to increase its input rate. This is very similar to
the behaviour of TCP's increase/decrease algorithms which
increase input rate when there are no losses and decrease
the input rate as soon as losses are observed. Later in Section
5 using simulations we show that dierent versions of
TCP actually do converge close to their fair rate when DWS
schedulers are deployed.
3.1 Packetized Diminishing Weight
Schedulers (PDWS)
In a network, tra-c does not
ow as a
uid. Instead it
ows as packets containing chunks of data that arrive at
discrete time boundaries. Therefore, a scheduler is needed
Buffers RIS Scheduler
Packet
Collector
Output Link
packet
streams
Input

Figure

4: Hypothetical model for DWS with discrete
packet boundaries
that works with discrete packets. Packetized DWS is derived
from the DWS scheduler in the same way as packetized
GPS is derived from the GPS scheduler. Therefore the implementation
details of PDWS are very similar to those of
PGPS except for minor changes in equations computing the
timestamps. It should be straightforward to adapt PDWS
to the simplications of PGPS like Virtual Clock [34], Self
Clocked Fair Queueing [13], WF2Q+ [33], Frame based Fair
Queueing
Denote the arrival time of the k th packet of
ow i as a k
the length of the k th packet of
ow i as L k
. We model the
th arrival of
ow i as if it were
uid
owing at a rate r k
in the interval (a k 1
The rate of arrival
of all the bits of the packet is given by r k
and therefore this
packet gets a GPS weight given by  k
being
a special case of DWS has  k
RIS). A packet becomes eligible for service by the scheduler
only after its last bit has arrived, i.e., at time a k
. We assume
that there is a hypothetical packet collector before the DWS
scheduler which collects all the bits of a packet and gives
them to DWS only when they become eligible (see Figure 4).
Now, we dene the nish time of a packet as the time
when the last bit of the packet gets serviced in a hypothetical
DWS scheduler with a packet collector as shown in Figure 4.
PDWS is dened as the scheduler that schedules packets in
increasing order of their nish times.
Along the lines of PGPS implementation [31], PDWS is
based on the concept of system virtual time and virtual n-
ish time of packets. The scheduler maintains a virtual time
function v(t). Upon a packet arrival, each packet is tagged
with a virtual nish time as follows:
The packets are serviced in increasing order of their virtual
nish times. To compute the virtual time at any in-
stant, an emulation of hypothetical DWS system of Figure 4
is maintained which is similar to most PGPS implementa-
tions. When a packet k of
ow i arrives, it is tagged with
a GPS weight of  k
i and is also given to the DWS emula-
tion. The emulation computes the virtual nish time of the
packet by Eq 15. The rate of change of virtual time with
real time is given by
the GPS weight corresponding to the packet of
ow i which
is currently in service in the DWS emulation.
In real practice tra-c arrivals are bursty. Therefore, it is
better to use a smoothed arrival rate, instead of instantaneous
arrival rates for GPS weight computation. The scheduler
PDWS with  smoothing sets  k
. The value of  is taken such that
the half life of smoothing is of the order of one round trip
time (R) when packet size of Lmax is used to send tra-c.
This gives:
where f is the fair rate of the
ow.
4. PROPERTIES OF DWS
We now describe some desirable game-theoretic properties
of DWS Schedulers. In this section, for all results number
of users, N  2 unless otherwise specied.
4.1 Single Link
With DWS scheduling, the best strategy for each individual
user is to send tra-c at its fair rate. This is formally
illustrated in the following theorem.
Theorem 4.1. Consider a link of capacity C, shared by
users, using DWS scheduling with unit DWS weights.
is the unique Nash Equilibrium for the
system.
The proof is provided in the Appendix. The naive selsh
users will converge to a Nash Equilibrium. However, in case
a user (say a leader) had information about other users' utility
functions or behaviours, scheduling and/or queue management
policies at the gateways, it could choose a value for
its input rate and the other users would equilibrate to a Nash
Equilibrium in the N 1 user subsystem. The leading user
can then choose its input rate based on which of these N 1
subsystem Nash Equilibria maximizes the leading user's util-
ity. This is formally called a Stackelberg Equilibrium.
prole   is a Stackelberg Equilibrium with user 1 leading
1. it is a Nash Equilibrium for users
2. the leader's utility is maximized, i.e.
a Nash Equilibrium for users
adopts the strategy 1 ,
is the set of strategies that user i can follow.
The leader's utility at a Stackelberg Equilibrium is never
less than that in any other Nash Equilibrium. So a user with
more information may try to drive the system towards one
of its Stackelberg Equilibria. This can be avoided if Nash
and Stackelberg Equilibria coincide. We now show this to
be true for a single link with DWS scheduling.
Theorem 4.2. Consider a link of capacity C, shared by
users, using DWS scheduling with unit DWS weights.
is the unique Stackelberg Equilibrium for
the system.
The proof is provided in the Appendix. Since the unique
Nash and Stackelberg Equilibria coincide, a user will benet
most by sending at its fair rate. Any user sending at a rate
higher than its fair rate will be penalized, and other users
can then receive a better output rate. This is characterized
by the concept of Nash rate.
Definition 3. Given a user with input rate r, dene
Nash rate for the remaining users as:
We now discuss some properties of the Nash rate.
Lemma 4.1. The Nash rate ((r)) is a strictly increasing
function of r in the range (C=N; 1).
Proof. For r 2 (C=N; 1), we rewrite denition 17 in the
Since W () is strictly decreasing, r increases as x increases
and vice-versa. Also note that the value of x satisfying the
above equation for a given value of r is unique.
Lemma 4.2. The Nash rate is greater than or equal to
C=N i.e. (r)  C=N .
Proof. For r  C=N , we see from the denition of Nash
rate (Eq. 17) that (r)  C=N .
For r > C=N , note from Lemma 4.1, that (r) is increasing
in (C=N; 1). Also note that (r) is continuous at C=N
(Eq. 17), and (C=N) = C=N . Hence, (r)  C=N .
When a user sends at r, the best strategy for other users
is to send tra-c at their Nash rate (r). This is formally
stated in the following theorem.
Theorem 4.3. If a user (say user 1) sends at r1 then
is the unique Nash Equilibrium for the
remaining N 1 users.
The proof is provided in the Appendix. Observe that
if a user sends at r1  C=N , thereby not contributing to
congestion, then the spare capacity is divided equally among
the others 1)). If a user misbehaves
and sends tra-c at a rate r1 > C=N , while other users
remain well behaved, then other users can safely increase
their rate upto (r1 ), whereas the misbehaving user gets
penalized to its residual Nash rate R (r), dened as follows.
Definition 4. Given a user with input rate r, dene its
residual Nash rate as:
The following two lemmas illustrate that the more a user
contributes to congestion the more penalty it incurs.
Lemma 4.3. The residual Nash rate is less than or equal
to C=N i.e. R (r)  C=N .
This immediately follows from Eq.
Lemma 4.4. R(r) is strictly decreasing function of r in
the range (C=N; 1).
The proof immediately follows from Eq.
A steep weight function results in severer punishment for
a user contributing to congestion and larger equilibrium output
rate for well behaving users. This is illustrated in Figure
5 which plots Nash rate and residual Nash rate for different
diminishing weight functions. As can be easily ob-
served, a steeper weight function(W results in a
larger penalty as compared to a less steep weight function
Nash
Rate
(Mbps)
Input Rate (r) (Mbps)
Nash Rates
W(r)=1/r

Figure

5: Nash rate
4.2 Arbitrary Network of Links
Consider an arbitrary network servicing N
ows. Assume
that DWS scheduling is deployed at every link in the net-
work. Assume that the input rate of each
ow is constant.
Therefore, the input and output rates of users at every other
link will also be constant. Now, the input and output rate
of each
ow at each link can be computed using Eq. 1, 12
and 13.
The following theorem establishes that even in an arbitrary
network of links, max-min fair input rates constitute
a Nash as well a Stackelberg Equilibrium if DWS schedulers
are deployed at each link. Max-min fairness [4] is a well
known notion of fairness in an arbitrary network. Denote
by M, the 1 N vector of max-min fair rates of these
ows
through this network.
Theorem 4.4. Consider N users sending their tra-c as
distinct
ows through an arbitrary network with independent
DWS scheduling at each link. The max-min fair rates
M constitute a Nash as well as a Stackelberg Equilibrium
for the users.
The proof is provided in the Appendix. Furthermore, it
is not necessary that the same weight function be used at
each link. This makes it easier to adopt DWS in a heterogenous
environment with dierent administrative domains and
policies.
Besides M, there may be other equilibria also, and users
may try to aect which equilibrium to reach. In such a
case, it can be shown that at least one user will experience
losses in any other Nash Equilibria. This is illustrated in
the following Lemma.
Lemma 4.5. Consider N users sending their tra-c as N
distinct
ows through an arbitrary network with independent
DWS scheduling at each link. The max-min fair rates
M constitutes the unique Nash as well as the Stackelberg
Equilibrium in which there are no losses in the system.
The proof is provided in the Appendix. In general, a user's
utility may also depend on its loss rate in addition to the
output rate. Out of many Nash Equilibrias giving the same
output rates, generally users will prefer one with smaller
losses. We formally dene this class of utility functions (U
l
as follows:
Mbps 2ms
100 Mbps 30ms
100 Mbps 30ms
100 Mbps 30ms
100 Mbps 30ms
100 Mbps 30ms

Figure

Simulation Scenario
1. U 2 U
l maps a user's output rate
and loss-rate l to
a real-valued non-negative utility.
2. U(
3. U(
If all users have such utility functions, it turns out that
M is the unique Nash as well Stackelberg Equilibrium.
This is illustrated in the following theorem which is similar
to Theorem 4.1 and Theorem 4.2 for a single link.
Theorem 4.5. Consider N users sending their tra-c as
distinct
ows through an arbitrary network with independent
DWS scheduling at each link. Let U i be the utility function
of user i. If 8 i U
l , then the max-min fair rates
M constitutes the unique Nash and Stackelberg Equilibrium.
The proof is provided in the Appendix. Therefore the
\best selsh behaviour" for a user is to send tra-c at its
max-min fair rate.
5. SIMULATION RESULTS
The results in the previous section imply that the \best
selsh behaviour" for a user in the presence of other similar
users is to send tra-c at its max-min fair rate. However, the
max-min fair rate depends on (a) the link capacities, (b) the
number of
ows through each link, (c) the input rate of other
ows and (d) the path of each
ow. A user will not know
these parameters in general and thus will not be able to know
its max-min fair rate. However, from Lemmas 3.4 and 3.5 it
does seem that in case of a single link with DWS scheduling,
each iteration of a TCP style increase/decrease algorithm
with suitable parameters will bring input rates closer to the
fair rates. Therefore, if a single link with DWS scheduling
is modeled as a game, then TCP-like end user algorithms
seem to be reasonable strategies to play the game.
In this section we illustrate through simulations that the
dierent versions of TCP algorithms are indeed able to converge
to their max-min fair rate, (and at Nash rates in the
presence of misbehaving users), when DWS schedulers are
deployed in the network. The convergence to Nash rates is
also shown for dierent diminishing weight functions. More-
over, specic versions of TCP and the round trip times of
individual
ows have little impact on the average output
rate of a
ow. Therefore, DWS scheduling solves most of
the problems of congestion control in the presence of misbehaving
users [7, 8].
Output
Rate
(Mbps)
Input Rate (Mbps)
All other flows sending at 4 Mbps
FCFS
RED
w(r)=1/log(r)
RIS: w(r)=1/r
w(r)=1/r^2
w(r)=1/r^4

Figure

7: DWS Performance in the presence of CBR
ows
5.1 Simulation Scenario
The simulation scenario is shown in Figure 6. The bottle-neck
link has a capacity of 10 Mbps and propagation delay
of 2 ms. There are ve access links of capacity 100 Mbps
and propagation delay ms.
The buer size for a
ow at each link was set to its round
product. PDWS with  smoothing,
per
ow buers and tail drop was used. NS [1] was used to
carry out all the simulations.
5.2 CBR flows
The bottleneck link is shared by ve CBR
ows, four of
which send tra-c at a constant rate of 4 Mbps. The rate
of the fth
ow is varied from 0 Mbps to 7.2 Mbps. A plot
of its output rate vs. the input rate for various scheduling
algorithms and buer management policies is shown in

Figure

7.
This is a scenario of heavy congestion. Note from Figure 7,
that with DWS scheduling the
ow is able to receive its fair
rate as long as it does not cause congestion. The
ow starts
receiving a penalty when its input rate exceeds the fair rate.
The amount of penalty depends on the weight function W ().
Note that the penalties are higher with W
lower with W log(r).
5.3 TCP with unresponsive flows
A
ow that does not change its input rate during congestion
is referred to as an unresponsive
ow [7]. Responsive
ows back o by reducing their sending rate upon detecting
congestion while unresponsive
ows continue to inject
packets into the network thereby grabbing a larger share of
the bandwidth. As a result the presence of unresponsive
ows gives rise to unfairness in bandwidth allocation. With
PDWS scheduling deployed, we show that TCP style AIMD
algorithms can estimate and send tra-c at their max-min
fair rate (or Nash rate) even in the presence of misbehaving
ows.
The bottleneck link is shared by 5 users, 4 using (re-
sponsive) TCP Tahoe and one unresponsive constant bit
rate (CBR) source. Responsive TCP
ows back during
congestion while unresponsive CBR
ows continue to inject
packets into the network thus attempting to grab a larger
share of the bandwidth. Figure 8 shows the average output
rates for a representative TCP
ow as the input rate of the0.51.52.5
Output
Rate
(Mbps)
Input Rate (Mbps) of CBR
4 TCP and 1 CBR
CBR (w(r)=1/r)
CBR (w(r)=1/r^2)

Figure

8: DWS Performance in the presence of TCP
and CBR
ows
CBR
ow is varied. Each point in the graph represents a
simulation of 20 seconds. However, the output rates correspond
to the average rate in the last 10 seconds of the
simulation when they get stabilized.

Figure

8 shows that TCP
ows are able to get close to
their Nash rate (shown in Figure 5) and hence to their Nash
Equilibrium (according to Theorem 4.3).
Note that with W log(r) the output rate of CBR
ow is greater than that of the TCP
ow. This is because
the inverse log weight function gives very little penalty to
the misbehaving CBR
ow and is very similar to WFQ. The
bandwidth left by TCP because of timeouts and retransmits
is grabbed by the CBR
ow despite its (slightly) small GPS
weight. As CBR increases its rate further, the penalty slowly
increases allowing TCP to grab a larger share.
5.4 TCP Versions
Dierent versions of TCP like Tahoe, Reno [21], Vegas [5],
and Sack [20] are known to perform dierently [21]. We show
that with DWS scheduling there is very little dierence in
the output rates achieved by these versions. The simulation
scenario is shown in Figure 6 with dierent versions of TCP
at n2, n3, n4 and n5. Packetized rate inverse scheduler
was used at the bottleneck link. Figure 9 shows
the total bytes of a
ow transferred as a function of time.
The output rate is given by the slope of the graph. Since
the slopes are almost identical we see that all versions get
identical rates.
5.5 Multiple vs Single Connection
Opening multiple simultaneous connections is a very simple
way to grab more bandwidth from simple FCFS (drop-
tail) gateways. The simulation scenario is shown in Figure 6
with FCFS employed at node n0. The users at nodes n2, n3,
n4, n5 and n6 open 1, 2, 3, 4 and 5 TCP Reno connections
to node n1 respectively.
Typically, a user opening more simultaneous connection
is able to grab more bandwidth. However, this is not the
case with DWS scheduling when all the TCP connections of
a user are treated as a single
ow.

Figure

shows a plot of
bytes transferred vs. time when PRIS is deployed at node
n0. We see that all users get an almost identical bandwidth.
5.6 TCP with different Round Trip Times
Total
data
received
time (sec)
Versions
Sack
Reno
Vegas
Tahoe

Figure

9: PRIS Performance in the presence of different
Total
data
received
time (sec)
Multiple TCP connections
connections
connections
connections
connections
connections

Figure

10: PRIS Performance in the presence of
multiple connections
The Round Trip Time (RTT) of a TCP connection determines
how fast it adapts itself to the current state of the
network. A connection with smaller RTT is able to infer the
status of the network earlier than a connection with larger
RTT. Therefore, large RTT connections typically achieve
lower output rates.
The simulation scenario is the same as shown in Figure 6
except that the propagation delays of links (n2-n0), (n3-
n0), (n4-n0), (n5-n0) and (n6-n0) are set to 5, 10, 20, 50,
100 ms respectively. PRIS scheduler was used and the value
of  was taken to be 0:9 which corresponds to the  of the
minimum RTT
ow according to Eq 16. Figure 11 shows
that when PRIS is deployed, after a few transients initially,
all
ows are able to achieve almost identical rates.
5.7 Network
In this section we show that with DWS scheduling deployed
in a network adaptive
ows like TCP are able to
estimate and converge to their max-min fair rates. The simulation
scenario is shown in Figure 12. There are 6 TCP
Reno
ows. The paths of
ows 0, 1, 2, 3, 4, and 5 are
(n0-n2-n1), (n4-n3-n5), (n0-n2-n3-n4), (n1-n2-n3-n5), (n0-
and (n1-n2-n3-n4) respectively. The buer size
of each
ow on each gateway was taken to be 300 packets
which is the bandwidth delay product of the
ow with
Total
data
received
time (sec)
5 TCPs with Different RTT
Rtt 14ms
Rtt 24ms
Rtt 44ms
104ms
Rtt 204ms

Figure

11: PRIS Performance in the presence
ows
with varying RTTs
ms
ms
ms
ms ms
Link Capacities 10Mbps

Figure

12: Simulation scenario for a network135790
Output
Rate
(Mbps)
time (sec)
RIS scheduling in a Network
Flowid 3
Flowid 4
Flowid 5

Figure

13: Output rates of
ows in a network with
PRIS
largest RTT. For this scenario the max-min fair rate [4] for
ows 0 and 1 is 5 Mbps and for
ows 2, 3, 4, and 5 is 2.5
Mbps.

Figure

13 shows a plot of output rate vs. time for all
6
ows. We see that after some initial transients all
ows
converge to their max-min fair rates.
6. CONCLUSIONS
Using the techniques of game-theory, we showed that the
current resource sharing mechanisms in the Internet either
encourage congestion causing behaviour, or are oblivious to
it. While these mechanisms may be adequate currently,
their applicability in the future remains questionable. With
growth, heterogeneity and commercialization of the Inter-
net, the assumption of end-users being cooperative might
not remain valid. This may lead to a congestion collapse of
the Internet due to selsh behaviour of the end-users.
We proposed a class of switch scheduling algorithms by
the name Diminishing Weight Schedulers (DWS) and showed
that they encourage congestion avoiding behaviour and punish
behaviours that lead to congestion. We showed that for
a single link with DWS scheduling, fair rates constitute the
unique Nash and Stackelberg Equilibrium. We also showed
that for an arbitrary network with DWS scheduling at every
link, the max-min fair rates constitute a Nash as well as a
Stackelberg Equilibrium. Therefore, when DWS schedulers
are deployed, even the selsh users will try to estimate their
max-min fair rate and send tra-c only at that rate.
It is possible to set dierent DWS weights for dierent
users (or tra-c classes). This should lead to (in a game-theoretic
manner) weighted fair sharing in case of a single
link and weighted max-min fair sharing in case of a network.
These weights may be set in accordance with the pricing or
other resource sharing policies.
We dened the concept of Nash rate and showed how
the choice of dierent weight functions can aect the
reward-penalty prole of DWS. With the 1=r 2 diminishing
weight function, the penalty imposed is large, whereas with
1= log(r) diminishing weight function, the behaviour of DWS
is only marginally dierent from that of GPS which imposes
no penalty. Therefore DWS may also be viewed as a generalization
of GPS scheduling with suitable game-theoretic
properties. DWS does not require dierent nodes to use the
same weight function. Therefore, it is well suited for heterogenous
environment consisting of dierent administrative
domains, where each domain may independently choose a
diminishing weight function according to its administrative
policies.
Although the max-min rate constitute Nash and Stackelberg
Equilibrium, it is not clear how users can estimate their
max-min fair rates. For this, a decentralized distributed
scheme such as the one is proposed [15] is required. Moreover
one needs to establish that such a distributed scheme
will be stable and will indeed converge to the max-min fair
rates when DWS schedulers are deployed in the network.
This is a topic under investigation. Our current paper does
not address this issue in a theoretical framework. Also, in
this paper we assumed that the input rate of every user is
constant. With a distributed scheme to estimate the max-min
fair rate, this assumption will not remain valid. Analyzing
DWS scheduling with dynamically changing rates is
another open problem.
We believe that, it should be possible to design distributed
algorithms that are stable and converge to the max-min fair
rates in presence of DWS scheduling. It seems that additive
increase and multiplicative decrease algorithms (such as the
one followed by TCP) with proper engineering may perform
well with DWS scheduling.
Using simulations we showed that in a network with DWS
scheduling, most of the TCP variants are able to estimate
their max-min fair rate reasonably well, irrespective of their
versions and round trip times (RTT). We also showed that
with DWS, the TCP users indeed get rewarded according to
their Nash rates in the presence of unresponsive, misbehaving
CBR
ows which get punished.
Our proposed model requires per-
ow queueing and
scheduling in the core routers, which may not be very easy
to implement in a realistic situation. However, this work
presents a signicantly dierent view of resource sharing and
congestion control in communication networks and gives a
a class of scheduling algorithms that can be used to solve
the problem in a game-theoretic framework. Based on this
work, one may be able to design \core stateless" policies [29]
with similar properties.
7.

ACKNOWLEDGEMENTS

We thank the computer communication review editors
and the anonymous reviewers for their helpful comments
on this paper.
8.



--R


Priority encoding transmission.

Data Networks.
Vegas: New techniques for congestion detection and avoidance.
Dynamic queue length thresholds in a shared memory ATM switch.
Congestion control principles.
Promoting the use of end-to-end congestion control in the internet
The NewReno modi
Random early detection gateways for congestion avoidance.
Game Theory.
Eliciting cooperation from sel

Congestion avoidance and control.

ERICA switch algorithm: A complete description.
Credit update protocol for ow-controlled ATM networks: Statistical multiplexing and adaptive credit allocation
Dynamics of random early detection.
Forward acknowledgement: Re
selective acknowledgement options.
Analysis and comparison of TCP Reno and Vegas.
A generalized processor sharing approach to ow control - the single node case
Transmission control protocol.
Something a host could do with source quench: The source quench introduced delay (SQuID).
A proposal to add explicit congestion noti
A binary feedback scheme for congestion avoidance in computer networks
Making greed work in networks: A game-theoretic analysis of switch service disciplines
Design and analysis of frame-based fair queuing: A new tra-c scheduling algorithm for packet switched networks


Hardware implementation of fair queueing algorithms for asynchronous transfer mode networks.
A taxonomy for congestion control algorithms in packet switching networks.
Hierarchical packet fair queueing algorithms.
Virtual clock
--TR
Data networks
Congestion avoidance and control
A binary feedback scheme for congestion avoidance in computer networks
VirtualClock
Random early detection gateways for congestion avoidance
Making greed work in networks
Credit-based flow control for ATM networks
Design and analysis of frame-based fair queueing
Hierarchical packet fair queueing algorithms
Forward acknowledgement
Dynamics of random early detection
<italic>Core</italic>-stateless fair queueing
Promoting the use of end-to-end congestion control in the Internet

--CTR
Luis Lpez , Gemma del Rey Almansa , Stphane Paquelet , Antonio Fernndez, A mathematical model for the TCP tragedy of the commons, Theoretical Computer Science, v.343 n.1-2, p.4-26, 10 October 2005
Petteri Nurmi, Modeling energy constrained routing in selfish ad hoc networks, Proceeding from the 2006 workshop on Game theory for communications and networks, October 14-14, 2006, Pisa, Italy
D. S. Menasch , D. R. Figueiredo , E. de Souza e Silva, An evolutionary game-theoretic approach to congestion control, Performance Evaluation, v.62 n.1-4, p.295-312, October 2005
Xiaojie Gao , Leonard J. Schulman, Feedback control for router congestion resolution, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
Altman , T. Boulogne , R. El-Azouzi , T. Jimnez , L. Wynter, A survey on networking games in telecommunications, Computers and Operations Research, v.33 n.2, p.286-311, February 2006
Luis Lpez , Antonio Fernndez , Vicent Cholvi, A game theoretic comparison of TCP and digital fountain based protocols, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.12, p.3413-3426, August, 2007
game theory;nash equilibrium;fairness;DWS;GPS;congestion control;stackelberg equilibrium;generalized processor sharing;RIS;scheduling;TCP