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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. When performing rate calculations, RBCC partitions the available resources fairly amongst traffic flows, in both uncongested and congested operating regimes.
  7. 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.

Congestion Information in Packets

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.

When a source transmits a packet, it initialises the Desired_rate field to the bandwidth which it desires for the flow of traffic; this may be . The Rate field is also initialised to this value, and the Bottle_node field is set to the identify the source.

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.

These fields are not altered as the packet travels back to the source. Thus, when the source receives the packet, it obtains a measure of the lowest bandwidth available to it for the flow of traffic. It can then adjust its rate to not exceed this bandwidth, so as to minimise the congestion that the traffic flow causes to the network.

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.

Information Kept in Routers - The Allocated Bandwidth Table

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:

a value which uniquely identifies this flow of data.
the bandwidth which the source of this traffic desires; it can be .
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.
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