Review: A binary Feedback Scheme for Congestion Avoidance in Computer Networks

The paper proposes an 'effective' congestion avoidance mechanism for
connectionless networks. It ensures the network operates at the maximally
efficient point and beyond which a slight increase in load results in a
large increase in response time. Their mechanism involves explicit feedback
by using a field in the packet header which is then used by the "user"
(entity that manages the window size of the end user) to adjust the window
size.
The "explicit binary feedback" scheme works as follows:
- A router that is congested sets a "congestion indication bit" in the
header of the packet flowing forward to the destination, any router that is
not congested ignores the bit. This bit is initially cleared when the packet
is transmitted from the source.
- At the destination, the bit is copied to the transport layer header of the
acknowledgement packet, which is then transmitted to the source.
- The user copies the bit to a data structure used by the congestion
avoidance algorithm. Note that the user can be either at the sender or the
receiver.

They model the network as a feedback control system in which signal
generation corresponds to generating the congestion indication signal in the
network, signal filtering alters the amount of traffic and the decision
function determines the amount of change. They then find the optimal
operating point by maximizing power (throughput/response time) and
efficiency (power of resource/maximum power).

The paper discusses two sets of policies for controlling traffic placed on
the network:
1) Router Policies:
 - Congestion Detection: the average queue length is monitored at each
router. If this is greater than one at the time the packet arrives, the
congestion indication bit is set. The paper discusses the advantage of using
average queue length over utilization (depends on distribution of service
time) and instantaneous queue length (a transient condition).
 - Feedback Filter (level 1 of filtering): the average queue length is the
number of packets in the router that are queued and those that are currently
in service, averaged over a period T, where T is the last busy + idle cycle
and the busy period of this cycle. This adaptive filtering acts as a 'low
pass filter'.

2)User Policies:
 - Decision Frequency: updating after every ack results in oscillations due
to overcorrection. Therefore, the window size is updated after the number of
acks received is equal to the sum of the previous window size (Wp) and
current window size (Wc). The congestion bits received are stored.
 - Use of Received Information: maintaining too long a history may result in
history dominating the update, therefore, the user only examines the last Wc
bits to update the window size. This method is also simple and avoids
maintaining additional state to relate the bits received.
 - Signal Filtering: to filter out noise, the cut off factor is set to 50%,
that is, if 50% of the bits are set, Wc is decreased, otherwise it is
increased.
 - Decision Function: The additive increase - multiplicative decrease
algorithm is used for window resizing. This maintains an overall global
window size close to the maximally efficient, maintains fairness across
multiple resources (if the window size is stored as a real number at the
source and then rounded when needed), minimizes oscillations in window size
and minimizes the time to achieve steady-state. However, deciding on a
multiplicative factor invloves a tradeoff: a small value achieves fairness
more rapidly but a large value reduces oscillations around the maximally
efficienct window size. The authors choose to reduce the oscillations.

The paper shows that the mechanism performs well under transient conditions,
and operates the network at stable point when overloaded, when users use
arbitrary starting window sizes and when the congestion is at the source and
not in the network.
The paper explains the ideas well, although there seems to be quite some
repitition at various points. I agree with the authors that the proposed
mechanism is better than those that involve extra packets to control or
avoid congestion, but I believe the overhead of this additional bit may also
not be necassary.
Received on Mon Sep 25 2006 - 21:32:28 EDT