The previous chapters show that, despite the advances made in terms of congestion control, traditional protocols and router mechanisms are deficient in terms of minimising congestion. Rate-based congestion control techniques may be useful in overcoming some of these problems. In this chapter, I give a brief discussion of the deficiencies in traditional congestion control schemes, and describe possible remedies. Given the remedies proposed, I sketch a framework for congestion control which is constructed on a `sustainable rate' basis, without use of such paradigms as sliding windows and round-trip timers. I then examine the components of the framework in detail, and look at the parameters inherent in the framework.
End-to-end congestion control mechanisms do not perform well because they must infer network congestion from indirect evidence such as packet loss and round-trip delay increases. In many cases, these inferences are wrong: packets are lost due to other reasons such as packet corruption. Mechanisms which feed congestion information from routers back to traffic sources seem to work more effectively than purely end-to-end mechanisms.
The `sliding window' mechanism is often overused. In protocols such as TCP, sliding windows performs error recovery, end-to-end flow control, and a primitive congestion control. The solution to these three problems is thus not orthogonal. Fast changes in window size can lead to bursty source transmissions: This can cause both short-term and long-term congestion in routers and destinations.
Most end-to-end mechanisms require a round-trip timer to detect packet loss: this is a problem in itself. Due to the often high variance in round trip time, the timer is usually set too low or too high, causing unneeded packet retransmission or poor throughput, respectively. Its inaccuracy leads to incorrect end-to-end judgements of current levels of congestion, based on packet loss. A round-trip timer is also computationally expensive to implement.
To avoid these shortcomings, transport protocols should ensure that error recovery, flow control and congestion control are completely orthogonal. Sliding windows certainly should not be used for congestion control. True rate control should be used for both flow control and congestion control, and packet admission into the network should be as evenly-spaced as possible. This minimises the burstiness of traffic, and helps to minimise short-term router congestion.
A protocol using true rate control should obtain information on the preferred rate from any congestion control scheme in the underlying Network Layer. Error detection should be performed by Selective Acknowledgments and Selective Retransmission. This retransmits only those packets that have been lost and need retransmission.
Instead of a sliding window to limit in-transit traffic for error recovery, a transport protocol should be allowed to have as much in-transit traffic as it desires. This is limited only by its transmission rate, available memory, and the amount of application data ready to transmit. A round-trip timer is still required, but only when a source exhausts its supply of traffic to transmit and must wait for acknowledgments. Until the protocol runs out of data, it should be transmitting in a rate-controlled regime that ensures good throughput. As the timer's value is not critical, its estimation will not be computationally expensive. Furthermore, it will be rarely used, and will thus cause little overhead.
The ultimate aim of any congestion scheme is to reduce the load on the network to that which is sustainable. Simplistic schemes such as Source Quench only inform the source of the existence of congestion within the network: no other information can be deduced.
Protocols such as Dec Bit are an improvement over Source Quench in terms of their detection of congestion and the return of this information to sources. However, again, only the existence of congestion is returned to the sources.
Schemes such as RED, while admirable in attempting to address the problems of end-to-end congestion control, can only indicate congestion by dropping packets. Packets should not be discarded unless absolutely necessary.
If transport protocols choose to employ rate control as a congestion control method, a congestion scheme should attempt to determine the ideal rate of flow for each source. If these ideal rates can be returned to all sources, the adjustment of their rates should alleviate any congestion.
The aim of any router is to forward traffic and maximise power, operating at the knee of the power diagram in Figure 2 (pg. ). Power is maximised when response time is low and throughput is high.
Low response time occurs when network delays are low, such as when router buffer occupancy is low. Throughput is high when packets are not lost and links are fully utilised. Power is maximised when an incoming packet can be immediately retransmitted without being delayed due to buffering. Router buffer occupancies should therefore never exceed one packet.
Congestion mechanisms which depend on high buffer occupancies, such as packet reordering schemes and packet dropping schemes, can only be useful in exceptional circumstances when congestion recovery is required. A good congestion control scheme will keep the network operating at maximum power, with low buffer occupancies.
Bursty packet admission (from a traffic source or from an intermediate router)
will make low router buffer occupancies difficult to achieve, and will also
cause short-term packet delays due to buffering. Smooth packet admission
techniques such as Leaky Bucket
[Turner 86] should be used by traffic sources and routers to help reduce short-term congestion [Sidi et al 93]. If congestion recovery is required, router packet reordering schemes which smooth traffic admission may also be employed.
The essential thrust of the remedies just given is to obtain detailed congestion information from the network, and to use this to adjust transmission rates which will optimise overall network power. The obvious paradigm for such a congestion control system is to be rate-based.
During the development of my rate-based congestion control framework, I was guided by the following design decisions. These address the deficiencies that I have outlined in existing congestion control schemes.
These design decisions form the requirements for the components in the congestion framework.
The framework that I propose takes into account all of the requirements just discussed. In essence, the framework spreads the mechanisms of congestion control across both the Transport and Network Layers, measuring and using information on sustainable rates of traffic flow through the network. Figure 4 gives an overview of the framework, showing the main components. Routers consist of the functions shown in Figure 1 (pg. ) but with an extra function, the Sustainable Rate Measurement function.
The essential elements of my proposed rate-based congestion control framework are as follows:
Before discussing the individual components in the framework, we need to look at the data flows that allow the components to intercommunicate. In the framework, the network routers must measure the sustainable traffic rate across the network for each traffic flow, and return the measurement to the source. This is best achieved with a number of fields in the Network headers of each packet sent from and to the source.
In the direction of flow from source to destination (e.g in data packets), I propose that three fields be used:
When a source transmits a packet, it initialises the Desired_Rate field to the bit rate which it desires for the flow of traffic; The Rate field is also initialised to this value, and the Bottle_Node field is set to the identity of the source. A finite Desired_Rate indicates that the source knows in advance the maximum data rate required for its transmission. A Desired_Rate of indicates that the source will use as much bandwidth as is made available to it.
As the packet passes through a router, the Sustainable Rate Measurement function may lower the value of the Rate field if it has allocated a lower rate to the traffic flow than the current value of the Rate field. 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 sustainable rate 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), I propose that one field be used:
This field is not altered as the packet travels back to the source. Thus, when the source receives the packet, it obtains a measure of the lowest bit rate available to it for the flow of traffic. It can then adjust its rate to not exceed this value, so as to minimise the congestion that the traffic flow causes to the network.
Note that acknowledgment packets carry not only the Return_Rate field but also the three fields Desired_Rate, Rate and Bottle_Node. This is because data packets and acknowledgment packets form two traffic flows, and they require different amounts of bandwidth and in different directions, as shown in Figure 5. Thus data packets carry the `return' field to supply the destination with details of its acknowledgment traffic flow.
In order to best utilise the Return_Rate values from the network components, and in order to admit packets as evenly spaced as possible into the network, the source should use a packet admission scheme. I propose a variant of Leaky Bucket [Turner 86]. The bucket has infinite buffer capacity, and admits packets into the network so that, at packet admission time, the flow's bit rate is exactly the Return_Rate. The inter-packet delay, shown in Figure 6, is calculated using the equation
Note that if packets are not constant in size, the delay will vary in value, even when the Return_Rate value is constant. The delay between packets can be greater than the value determined by Equation 4.1 if there is no available data from the application to transmit. However, once data becomes available, the source must not transmit packets faster than the set rate in order to ``make up the average''.
Return_Rate values arrive in every acknowledgment packet from the destination. Immediate use of every value is liable to cause short-term rate fluctuations which could result in short-term congestion. To avoid this, the source must leave 1 round-trip gaps between delay changes, in order to allow the Return_Rate value used to take effect. Note that sequence numbers can be used to determine that a round-trip has occurred: a round-trip timer or round-trip time estimation is not required.
Although packets are initially admitted at intervals determined by Equation 4.1, this spacing will be destroyed if routers have queue sizes bigger than one packet. Routers should attempt to preserve spacing if possible, and refrain from reordering packets. In the simulations presented in Chapters 8 and 9, First-Come-First-Served queueing was used, with no attempt to preserve packet spacing. Section 10.10 shows that, despite this, packet spacings are preserved.
Any function that provides the error control desired by the transport protocol can be used here, as long as it meets the design decisions. That is, it must be orthogonal to the protocol's flow control, it should not retransmit data unnecessarily, and it should make no reliance on round-trip timers or round-trip time estimation if possible. Chapter 5 discusses a transport protocol which meets these requirements using Selective Retransmission.
It should be noted that, as shown in Figure 4, any packet retransmissions will form part of the uniformly-spaced packet stream exiting the source's Packet Admission Function.
As outlined in the previous section, a transport protocol should not retransmit data unnecessarily. The destination's Acknowledgment function must be designed with this requirement in mind. Thus, Go-Back-N is ruled out, and Acknowledgment functions such as Selective Acknowledgment should be used. The destination should return acknowledgments to the source as soon as possible, in order to provide timely feedback of the sustainable rate values. Where an acknowledgment acks several data packets, only the most recent sustainable rate value should be returned, as this holds the most timely sustainable rate information from the network.
The sustainable rate measurement function in each router is the cornerstone of the proposed congestion control framework. A discussion on the requirements and goals of the function, and an example instantiation, is presented in Chapter 6.
The router may use any packet queueing function which meets the design decisions. Queueing functions which attempt to preserve packet spacings for each source may be useful. First-Come-First-Served was used in the simulations described in Chapters 8 to 11.
Again, the router may use any packet dropping function which meets the design decisions. Dropping functions which attempt to preserve packet spacings for each source may be useful. If the rate-based framework keeps the network operating at maximum power, packet loss will occur rarely, and the choice of functions for both Packet Queueing and Packet Dropping will have little effect on the framework. This is borne out in the simulations described in Section 11.8. Drop Tail was used in the simulations described in Chapters 8 to 11.
As noted previously, congestion avoidance schemes attempt to keep the network operating at the knee of Figure 2 (pg. ). As the main source of congestion information in the framework is the sustainable rate measurement, the router can lower the Rate fields in packets further than normal, if it believes it is operating above the knee of the curve. In doing this, it must set itself as the Bottle_Node. This extra lowering of the Rate field will cause the source to throttle its transmission, and help to bring the router back below the knee of the curve.
Although the congestion framework has congestion avoidance, there may be times when a router reaches the point of congestion collapse. For example, a new traffic flow may learn about its rate allocation before other large round-trip flows learn that their allocation has been reduced. For a small period of time, more packets will be admitted into the network than can be transmitted.
The large round-trip flows will eventually learn about their new rates, but only after one round-trip. It should be possible to inform these flows about the problem in less than one round-trip. This control mechanism must also not overburden the network with congestion control information.
I propose as the congestion recovery mechanism a variant of Source Quench. When a router considers itself congested, it returns Rate Quench packets to the sources it believes are the cause of the congestion. These packets also have a Return Rate field, which the congested router sets to values which will alleviate congestion from each of the congesting sources. Upon receipt of a Rate Quench packet with a Return Rate field lower than the source's current rate, the source is obliged to immediately lower its rate to the value in the Rate Quench packet. Rate Quench packets can never raise a source's transmitting rate.
In order to ensure stale Rate Quench packets are not used, a source must discard Rate Quench packets which have a sequence number less than the last valid Rate Quench packet received.
A policy on Rate Quench packet generation is discussed in Section 8.4.
One problem with Rate Quench congestion control is that all routers along a flow's path may send Rate Quenches if a flow's rate is lowered. This is an excessive amount of control information admitted into the network. Section 11.3 describes how the use of Rate Quench packets affects the congestion control of the framework.
The Transport Layer is reduced in complexity, with a Leaky Bucket-style flow mechanism controlled by the sustainable rate measurements returned (via acknowledgments) from the routers.
Any transport protocol which meets the requirements described in this chapter may be used in the framework: for example, NETBLT, VMTP and XTP could be used. As much of the functionality of these protocols was not required in the rate-based congestion control framework, I chose to develop a new rate-based transport protocol, TRUMP. The description of this protocol is given in the next chapter.
The sustainable rate measurement function in each router plays a central role in the framework. Its requirements and goals, and a specific algorithm implementing these, RBCC, is discussed in Chapter 6.