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.

Network Architecture

The network architecture under consideration has the following characteristics:

  1. The network is a wide-area network with nodes in the network passing data to other nodes along links. The nodes are arbitrarily connected; the network does not have a particular topology (e.g spanning tree, hypercube etc.).
  2. The network is connectionless. There is no reservation of network bandwidth or resources between a source of data transmission and its intended destination. End-to-end ``connections'' may be set up by the Transport layers in the source and destination, but the other nodes within the network are oblivious to this.
  3. The network is packet-switched. Packets are individually routed from source to destination. They may take different routes, and may arrive at the destination out-of-order.
  4. Packets are routed from one link to the next via nodes, often known as routers, packet switches or gateways. Nodes usually buffer incoming packets before they are transmitted on an outgoing link. This is described in greater detail in the next section.
  5. The network uses semi-static routing. Routes change slowly over time. Most route changes are performed manually, and most routes are static.
  6. The network sets no bandwidth constraints on data sources. A host may attempt to transmit data at a rate which will exceed the bandwidth or resources on the links and nodes between it and the data's destination.
  7. The network makes no transmission guarantee. The links on the network have finite bandwidth, and the nodes have finite buffer space for packets waiting to be switched. If network components are unable to forward data on to the destination, for any reason, the data may be discarded.
  8. The network is an internetwork. The nodes in the network are connected by links that vary greatly in type. There may be large variations in:

Routers - Bottlenecks in the Network

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.

Congestion in Connectionless Packet-switched Networks


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.

Network Performance as a function of Load

Warren Toomey
Fri Mar 15 10:43:33 EST 1996