switching, where traffic is generated
by selfish users.
We study a packetized
traffic model, which is more realistic than
the widely used fluid model.
We assume that routers have
FIFO buffers of bounded capacity
managed by the drop-tail policy.
The utility of each user
depends on its transmission rate and
the congestion level. Since selfish
users try to maximize their own utility
disregarding the system objectives, we
study Nash equilibria that correspond
to a steady state of the system.
We quantify the degradation
in the network performance called the price of anarchy
resulting from such selfish behavior. We show
that for a single bottleneck buffer, the price
of anarchy is proportional to the number
of users. Then we
propose a simple modification of the Random Early Detection (RED)
drop policy which reduces the price of anarchy to a
constant.
We demonstrate that a Nash equilibrium can be reached
if all users deploy TCP Vegas as their transport protocol.
We also consider some natural extensions of our model
including the case of multiple Quality of Service (QoS)
requirements, routing on parallel links and general networks with
multiple bottlenecks.