Because of the problems with window-based flow control schemes, and with
the limited amount of congestion information available from single-bit
congestion schemes, I was motivated to develop a congestion control scheme that
returned appropriate rate information to the source of a traffic flow,
and a matching transport protocol which could use this information.
During the development of these, I was guided by the following design
decisions:
- Dropping packets is highly undesirable.
-
A router which is dropping packets is operating in congestion recovery
mode, well past the optimum point of operation [Jain 90].
A congestion control scheme should emphasise congestion avoidance, but
also provide congestion recovery.
- Router queue sizes >1 are highly undesirable.
-
Jain [Jain 90] shows that an average router queue length
of 1 packet is the optimum value. A congestion scheme should strive to
keep queue lengths at length 1.
- Use of round-trip timers is undesirable.
-
Round-trip time estimation is complex and difficult to get right.
A new transport protocol should avoid the use of round-trip timers
if possible.
- Use of windows for flow control is undesirable.
-
Window update schemes are also complex and difficult to get right.
Poor window updates can also lead to bursty traffic, undesirable
both from the point of view of congestion and time-sensitive
network traffic. Limited window sizes can also lead to poor
utilisation in high-speed networks with large latencies.
- Selective retransmission is preferred to Go-back-N error recovery.
-
Go-back-N error recovery will retransmit packets that have been
successfully received by the destination. A much better retransmission
scheme is selective retransmission.
- Separation of error control and flow control is desirable.
-
Packet loss should not be tightly associated with congestion or flow
control in a transport protocol. Packets are lost for many other
reasons than congestion. A transport protocol should use packet loss
to prompt packet retransmission and nothing else.
- Transport flow control should use congestion information from routers.
-
Bit-setting techniques help a source identify the presence of
congestion, but do not indicate the extent of congestion.
Routers should feed back more than one bit of congestion information
to transport protocols.
Following these design decisions, I have developed RBCC, a rate-based
congestion control scheme, and TRUMP, a rate-based unicast message transport
protocol. TRUMP and RBCC have the following characteristics:
- TRUMP uses a rate-based flow control scheme, using rate information
provided by RBCC in routers. TRUMP uses a selective retransmission
scheme for error control. The flow control and error control mechanisms
are orthogonal.
- TRUMP admits packets into the network uniformly spaced in time; this
minimises short-term congestion due to bursty traffic. Routers attempt
to preserve the time spacing of packets in a traffic flow.
- TRUMP advertises a desired data rate to RBCC. This rate may be infinite
(e.g for FTP traffic) or finite (e.g for audio or telnet traffic). RBCC
will never allocate more bandwidth than the desired rate.
- TRUMP does not measure or use round-trip times. A single timer is used
to prompt the transmission of the next data packet. The timer is set
solely from the suggested data rate provided by RBCC.
- In the router, the RBCC congestion control scheme calculates the
sustainable data rate across the network for each traffic flow.
This sustainable rate is passed to the TRUMP instantiation which is the
source of the the traffic flow.
- When performing rate calculations, RBCC partitions the
available resources fairly amongst traffic flows, in both uncongested
and congested operating regimes.
- Routers may implement other congestion control mechanisms such as queue
reordering and packet dropping schemes to complement RBCC. Routers
should drop packets fairly when necessary.
Each packet which traverses the network contains a number of fields
which are used by RBCC to set the bandwidth available to the source. In the
direction of flow from source to destination (e.g in data packets),
three fields are used:
|
Desired_rate | The bandwidth which the source of this traffic desires;
it can be . |
|
Rate | The bandwidth which has been allocated to this flow of
traffic by a router. |
|
Bottle_node | The router which set the value of the Rate
field in the packet. |
As the packet passes through a router, RBCC may lower the value of
the Rate field if it has allocated less bandwidth to the traffic
flow. If it alters the Rate field, the Bottle_node field
is set to identify the router. When the packet reaches its destination,
the Rate field holds the lowest bandwidth allocated by the routers
along the packet's path, and the Bottle_node field identifies
the node that set this lowest rate.
In the direction of flow from destination to source (e.g in
acknowledgment packets), two fields are used:
|
Return_Rate | The value of the last Rate field which
reached the destination. |
|
Return_Bottle_node | The value of the last Bottle_node field
which reached the destination. |
Note that acknowledgment packets carry not only the two `return'
fields but also the three fields Desired_rate, Rate and
Bottle_node. This is because a bi-directional traffic flow
(data and acknowledgment packets) require different amounts
of bandwidth and in different directions. Data packets carry the two `return'
fields for the same reason.
In order to calculate sustainable rates for traffic flows, RBCC needs to
maintain information about these flows. Each router has a number of output
interfaces which connect it to other routers, or to sources and destinations of
data. For each output interface, RBCC keeps a table of information
which describes the bandwidth that has been allocated for each flow of data
currently passing through the output interface. This table is known as the
Allocated Bandwidth Table, or ABT. Each entry in the table
has the following fields:
- Conn_id,
- a value which uniquely identifies this flow of data.
- Desired_rate,
- the bandwidth which the source of this traffic
desires; it can be .
- Rate,
- the bandwidth which has been allocated by the router for
this flow of traffic; it cannot be zero or a value greater than the
bandwidth of the output interface. Similarly, the sum of the
Rate fields in the table must not exceed the bandwidth
of the output interface.
- Bottle_node,
- the router which this router believes is the bottleneck
on this flow of traffic. It may or may not be the current router.
The next section describes how the packet fields and the Allocated Bandwidth
Tables are used by TRUMP and RBCC.
Warren Toomey
Fri Mar 15 10:43:33 EST 1996