Network Performance as a function of Load
Congestion in connectionless packet-switched wide-area networks is a major problem, and this problem is growing alarmingly in such networks as the Internet, which is suffering an exponential growth in users and network traffic. This technical report outlines a method of congestion avoidance for networks with this architecture, and compares the effectiveness of this method against TCP/IP in a single network scenario.
This technical report is divided into three parts. Part 1 (Sections 1 to 2) gives a brief look at the problem of network congestion and the current solutions for it. Part 2 (Sections 3 to 4) outlines a new solution to network congestion (RBCC) which is rate-based, and details the basis of its operation and its implementation in the REAL network simulator. Part 3 (Section 5) compares RBCC against the congestion mechanisms in TCP/IP in an example network scenario.
The network architecture under consideration has the following characteristics:
All the links on a network are joined together by routers. These forward packets arriving on incoming links to the appropriate outgoing links, to ensure that the packet is routed to its intended destination.
Incoming packets are buffered in an Input Buffer. Once in the buffer, they are selected by a Packet Selection Function to be passed to a Routing Function. The Routing Function determines on to which outgoing link a packet must be placed for it to get closer to its destination; this is done with a routing table which, as described earlier, is semi-static. When the correct link for the packet is found, the Routing Function passes the packet to a Packet Queueing Function for queueing on the output buffer for the link. When the packet reaches the other end of the queue, it is transmitted over the link to the next router, or to the final destination.
There are two fundamental bottlenecks in the given network architecture. Firstly, there is a minimum time needed for the router to decode the network header of the incoming packet, determine the route for the packet, and pass the packet to an outgoing link for transmission. Secondly, there is a delay for the packet to be transmitted on the outgoing link; this may just be the packet's transmission time for a full-duplex link, or there may be an extra delay for the link to become clear on a half-duplex link.
The second bottleneck indicates that the router must be prepared to buffer output packets, to prevent them from being lost while the router waits for an outgoing link to become clear. The two bottlenecks together indicate that the router must buffer incoming packets, to prevent them from being lost if they arrive too quickly for the router to process.
By definition, the router's buffers are finite. If a buffer becomes full, then no more packets can be queued in the buffer, and the router has no choice but to discard further packets. This causes data loss in the data flow between a source and destination, and usually causes the source to retransmit the data.
Although a router cannot queue a packet if the corresponding output buffer is full, it can choose either to discard the unqueued packet, or to discard a packet already in the output queue, and then queue the unqueued packet. This choice is performed by the Packet Queueing Function.
Given the above architecture, it is possible to see how network congestion can occur. A source of data flow on the network cannot reserve bandwidth across the network to its data's destination. It therefore is unable to determine directly what rate of data flow can be sustained between it and the destination.
If a source transmits data at too high a rate that can be sustained between it and the destination, one or more routers will begin to queue the packets in their buffers. If the queueing continues, the buffers will become full and packets from the source will be discarded, causing data loss and, if the source is attempting to guarantee transmission reliability, retransmission of data and increased transmission time between the source and the destination. Figure 1 from [Jain & Ramakrishnan 88] demonstrates the problem of congestion.
As the load (rate of data transmitted) through the network increases, the throughput (rate of data reaching the destination) increases linearly. However, as the load reaches the network's capacity, the buffers in the routers begin to fill. This increases the response time (time for data to traverse the network between source and destination) and lowers the throughput.
As the routers' buffers begin to overflow, packet loss tends to 100%, response time approaches infinity and the throughput approaches zero; this is the point of congestion collapse. This point is known as the cliff due to the extreme drop in throughput. Figure 1 also shows a plot of power, defined as the ratio of throughput to response time. The power peaks at the knee of the figure.