[Iccrg] My definition of congestion

[S. Keshav]

Folks,
    Here is an excerpt from my 1991 thesis that answers one of the two
questions I raised: What is congestion? I will attempt to discuss the other
opinions presented in this list in a separate message.

--------------------8<--------------------------------------

Some common definitions of congestion

Since congestion occurs at high network
loads, definitions of congestion focus on some aspect of network behavior
under high load. We first discuss a scenario that leads to network
congestion in reservationless networks, and then motivate some definitions.

Consider a reservationless network, where, due to some reason, the short
term packet arrival rate at some switch exceeds its service rate. (The
service rate is determined by the processing time per packet and the
bandwidth of the output line. Thus, the bottleneck could be either the
switch’s CPU or the outgoing line: in either case, there is congestion.) At
this point, packets are buffered, leading to delays. The additional delay
can cause sources to time out and retransmit, increasing the load on the
bottleneck [101]. This feedback leads to a rapidly deteriorating situation
where retransmissions dominate the traffic, and effective throughput rapidly
diminishes. Further, if there is switch to switch flow control (as
in ARPANET, Tym- net, Datapac, Sirpent, etc.), new packets may not be
allowed to enter the switch, and so packets might be delayed at a
preceding switch as well. This can lead to deadlock, where all traffic comes
to a standstill. 

Note that three things happen simultaneously.

- First,  the queueing delay of the data packets increases.
- Second, there may be packet losses.
- Finally, in the congested state, the traffic is dominated by
retransmissions, so that the effective data rate decreases.

The standard definitions of congestion are thus of the form: ‘‘A network is
congested if, due to overload, condition X occurs’’, where X is excessive
queueing delay, packet loss or decrease in effective throughput.

These definitions are not satisfactory for several reasons.

First, delays and losses are indices of performance that are being
improperly used as indices of congestion, since the change in the indices
may be due to symptoms of phenomena other than congestion.

Second, the definitions do not specify the exact point at which the network
can be said 
to be congested (except in a deterministic network, where the knee of the
load-delay curve, and hence congestion, is well defined, but that is the
trivial case). For example, while a network that has mean queueing delays in
each switch of the order of 1 to 10 service times is certainly not
congested, it is not clear whether a network that has a queueing delay of
1000 service times is congested or not. It does not seem possible to come up
with any reasonable threshold value to determine congestion!

Third, a network that is congested from the perspective of one user is not
necessarily cong- ested from the perspective of another. For example, if
user A can tolerate a packet loss rate of 1 in 1000, and user B can tolerate
a packet loss rate of 1 in 100, and the actual loss rate is 1 in 500, then A
will claim that the network is congested, whereas B will not. A network
should be called uncongested only if all the users agree that it is.

A New definition 

>From the discussion above, it is clear that network congestion
depends on a user’s perspective. A user who demands little from the
network can tolerate a loss in performance much better than a more demanding
user. For example, a user who uses a network only to send and receive
electronic mail will be happy with a delivery delay of a day, while this
performance is unacceptable for a user who uses a network for real-time
audio communication. The key point is the notion of the utility that a user
gets from the network, and how this utility degrades with network loading.

The concept of ‘utility’ used here is borrowed from economic theory. It is
used to refer to a user’s preference for a resource, or a set of resources
(often called a resource bundle). Strictly speaking, the utility of a user
is a number that represents the relative preference of that user for a
resource (or performance) bundle, so that, if a user prefers bundle A to
bundle B, the utility of A is greater than the utility of B. For example, if
A is {end-to-end delay of 1 second, average throughput 200 pkts/second}, and
B is {end-to-end delay of 100 seconds, average throughput 20000
pkts/second}, a user may prefer A to B, and we would assign a utility to A
that is greater than the utility of B, while another user may do the
opposite. 

In classic microeconomic theory, utilities are represented by a
function over the resources. Since utilities express only a preference
ordering, utility functions are insensitive to monotonic translations, and
the utilities of two users cannot be compared; the function can only be used
to relatively rank two resource bundles from the point of view of a single
user. An example of a utility function is αT − (1−α)RTT, where α is a
weighting constant, T is the average throughput over some interval, and
RTT is the average round-trip-time delay over the same interval. As the
throughput increases, the utility increases, and as delays increase, the
utility decreases. The choice of α determines the relative weight a user
gives to throughput and delay. A delay-sensitive user will choose α→0,
whereas a delay-insensitive user’s α→1.

In practice, a utility function may
depend on a threshold. For example, a user may state that he or she is
indifferent to delay, as long as it is less than 0.1 seconds. Thus, if the
user gets a delay of 0.05 seconds during some interval of time, and 0.06
seconds in a later period, as far as the user is concerned, there has been
no loss of utility. However, if some user’s utility does decrease as a
result of an increase in the network load, that user will perceive the
network to be congested. This motivates our definition.

Definition:

A network  is said to be congested from the perspective of user i if the
utility of i decreases due to an increase in network load.


Remarks: 

1. A network can be
congested from the perspective of one user, and uncongested from the
perspective of another.

2. A network can be said to be strictly uncongested
if no user perceives it to be congested.

3. A user’s utility may decrease
due to something other than network load, but the user may not be able to
tell the difference. The onus on the user is to determine the cause of the
loss of utility, and to take appropriate corrective action.

This definition 
is better than existing definitions since it avoids the three problems
raised earlier. First, we make a clear distinction between a performance
index and a congestion index. It is possible for a performance metric to
decrease (for example, for RTT to increase), without a change in the
congestion index (for example, if α = 1). Second, the definition makes it
clear that congestion occurs from the point of view of each individual user.
Finally, the point of congestion is precisely the one where the user detects
a loss of utility. No further precision is necessary, since, if the users
are not dissatisfied with the available service, then the network
performance, no matter how poor it is in absolute terms, is satisfactory.

Our definition places congestion control in a new light. A network that
controls congestion, by our definition, must be responsive to the utility
function of the users, and must be able to manage its resources so that
there is no loss of utility as the load increases. Thus, the network must be
able to differentiate between conversations, and prioritize conversations
depending on the stringency of their owner’s utility. A naive approach that
ignores the user’s quality-of-service requirements is automatically ruled
out by this definition.


------8<-----------------

The rest of the chapter can be found at:

http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/91/thesis/ch1.pdf

There is some material there also on scope, requirements, and assumptions
that are relevant to this list, and we should probably discuss those later.

thanks

keshav