Congestion Control in Computer Network

In this tutorial, you will learn the basic concepts of congestion control. After reading this tutorial, you will learn about different ways to prevent congestion. You will also learn about the pros and cons of different methods of congestion control.

Contents:

1. What is Congestion?
2. What is Congestion Control?
3. Network Provisioning and Traffic-Aware Routing
4. Admission Control
5. Traffic Throttling
6. Traffic Throttling Schemes
7. Load Shedding
8. Random Early Detection

What is Congestion?

Multiple routers are connected to a network. When each end device on the network sends a packet, a large number of packets are generated. The packet will arrive late at the destination due to a large number of packets presents in a network. This causes packet delay and is known as congestion.

• The congestion is a condition where the packet load is more than the load the network can handle.
• When congestion occurs on a network, it degrades the performance of the network.
• If network congestion occurs, the network layer is notified and decides what to do with the extra packets.
• When the network experiences congestion, the network layer communicates with the transport layer and tells it to reduce the load placing on the network.
• Usually, congestion occurs when the router learns and processes the packet. The router has a memory block called a buffer, in which the router holds the packets before processing and for some time after processing. This process is repeated for each incoming packet and causes packet delay.

What is Congestion Control?

Congestion control techniques are used to control congestion on the network. Congestion control mechanisms are used on the network to keep the load below the network capacity. As we discussed that congestion affects the performance of the network, so in the congestion control mechanism, delay and throughput are used to measure the performance of the network.

• Here, do not get confused between congestion control and flow control as both are different.
• In the flow control, the flow of packets is controlled only between a sender and a receiver. In congestion control, congestion is a global problem which means that all hosts and routers experience packet congestion.
• Generally, the basic idea of ​​controlling congestion on a network is to create a network that has the capability to handle pre-determined traffic.
• Various methods are used to determine how to prevent congestion or how to manage it when congestion occurs.

The figure below shows the methods of congestion control.

As shown in the figure, Network provisioning, Traffic-aware routing, Admission control, Traffic Throttling, and Load Shedding are the method to congestion control.

Network Provisioning and Traffic-Aware Routing

When it comes to controlling congestion two methods come in mind, either increases the bandwidth or resources of the network or decreases the load. So, let’s understand the first two approaches of congestion control that are network provisioning and traffic-aware routing.

Network Provisioning: In network provisioning, the network is constructed in such a way that it can handle pre-determined traffic.

• If less bandwidth is present on a link, then it causes congestion on the network. Also, resources are added dynamically when severe congestion is detected.
• In cases of severe congestion, routers or lines originally designed for the backup enable to prevent congestion.
• In network provisioning, routers and links heavily loaded all the time are regularly upgraded to ensure performance.

Traffic-aware routing: In this method, the path changes when the router finds traffic in the link.

The below diagram explains the traffic-aware routing approach.

• As shown in the figure, there are 12 routers on a network. Network-1 and Network-2 are connected by two links, R5 to R11 and R6 to R12.
• The link from R5 to R11 is congested because the link is carrying packets beyond its capacity. Therefore, Router-5 notices that there is a heavy load on the R5 to R11 link, so it looks for another way to send the packets quickly.
• Router-5 finds that the path from R6 to R12 is free, and there is no traffic on the link, so it will send packets using the path from R6 to R12.
• Router-5 continuously sends packets on path R6-R12 until it finds path R5-R11 available.
• From this example, we can say that the traffic is spread over both R5-R11 and R6-R12.

Admission Control

Admission control is a mechanism used to prevent congestion in connection-oriented networks. In this method, the new virtual-circuit network is not set up until the old virtual circuit can handle the traffic. Leaky bucket and Token bucket are techniques of admission control.

• In a leaky bucket, incoming packets fall into the bucket and leak out at a constant rate. The incoming rate may vary, but the outgoing rate remains constant.
• In the leaky bucket technique, if the host does not send any packets for some time, its bucket becomes empty. Time is wasted because none of the packets use this time. In the token bucket, the host stores the credits for the future in the form of packets.
• Leaky Bucket detects the average data rate of incoming traffic and converts it to fixed-rate traffic. If the bucket on the network is full, it drops the packet.
• Admission control mechanisms can be combined with traffic-aware routing and used across networks.

Traffic Throttling

When communication occurs between a sender and a receiver on a network, the sender sends as much traffic to the receiver as possible. If the network becomes congested by receiving a large number of packets, it notifies the sender to throttle back and slow down the transmission.

• The traffic throttling approach is used on both datagram networks and virtual-circuit networks.
• Routers monitor the resources they have and check the links over which packets arrive, checks the buffer of queued packets and the number of packets lost. Traffic can be throttled using this technique.
• In another approach to throttling traffic, the router looks at the delay present in the incoming packets. By measuring the delay, the router decides whether there is any congestion in the packet. This is a common technique used mostly on networks.
• But what will the router do if it experiences packet congestion? Therefore, if congestion is experienced, the router notifies the appropriate sender who sent the packet and alerts it to the congestion.
• To respond to congestion, routers use different schemes. They are as follows:
  • Choke Packets
  • Explicit Congestion Notification
  • Hop-by-Hop Backpressure

Traffic Throttling Schemes

Typically, the router uses choke packets, explicit congestion network (ECN), and hop-by-hop backpressure mechanisms to notify the sender about congestion.

Choke Packets: In this method, the router directly informs the sender about the congestion. Router chokes packets containing congested packets and sends them to the sender.

• When the sender receives a choke packet from the router, it reduces the data sending rate by 40-50% to prevent congestion on the network.
• If after the sender lowers the data rate, the network becomes congested then the router sends choke packets again. The sender receives choke packets until the network is balanced.

Explicit Congestion Network (ECN): Instead of sending choke packets to the source, the router sets the Congestion Experienced (CE) bit and sends it to the sender. When the sender receives the CE bit, he knows that the packets he sends are experiencing congestion. This mechanism is known as Explicit Congestion Notification (ECN).

The diagram below explains the explicit congestion notification method.

• As shown in the figure, PC-1 sends the packet to PC-2 on the network, it passes through two routers.
• First, the packet is unmarked, which means that the Congestion Experienced (CE) bit is not set. As the packet enters Router-2, which is congested, the packet sets the CE bit.
• When PC-2 receives the packet, it checks whether the CE bit is set, if it is set, it sends the Echo packet to the sender and informs that the packet is experiencing congestion on Router-2.
• Upon receiving an echo reply, the sender throttles the traffic and slows down the transmission speed.

Hop-by-Hop Backpressure: In this method, the destination sends choke packets hop-by-hop. Let us understand with an example.

The below diagram explains the hop-by-hop backpressure mechanism.

• As shown in the figure, Router-1 sends packets continuously at a speed of 100 Mbps. Now, Router-4 can only handle packets at 40 Mbps. So, it will generate a choke packet and send it to Router-3.
• When Router-3 receives the choke packet, it reduces the flow of the packet to Router-4. But, Router-3 is also receiving a large number of packets, so it will send a choke packet to Router-2.
• As soon as Router-2 receives the choke packet, it also reduces the flow of data and forwards the choke packet to Router-1.
• In this way, Router-1 also receives a choke packet and this reduces the flow of data sending.

Load Shedding

When none of the above methods work to prevent congestion on the network, the router starts discarding packets to balance the network. This is known as load shedding, in which routers simply drop packets when they cannot handle them.

• The key point in load shedding is how the router discards the packets. This varies according to the applications and services used by the network.
• For example, if two devices are transferring files using FTP, the old packets are more important than the new packets.
• If a packet contains routing information, it is considered as an important packet because the loss of this packet can result in network downtime.
• In the load shedding method, packets are marked with their priority, using which the router decides how important they are to the network. It enforces a wise abandonment policy.
• Random early detection is a part of the load shedding method used to deal with congestion.

Random Early Detection

Random Early Detection (RED) is an algorithm used to determine when to discard packets. Using the RED mechanism, the router decides which packets to drop quickly before they cause problems on the network.

• Senders are sending packets over a network at a very high speed. In RED, the packets are randomly selected by the router. Because packets are randomly selected, the routers do not tell which router is causing the most trouble in the network.
• When the sender does not receive an acknowledgment for its sent packets, it knows that the sent packets experience congestion and are discarded by the router. In addition, it also reduces the data rate, the throughput.
• Routers using the RED mechanism improve network performance as packets are dropped only when the buffer is full by checking the priority of the packets.
• RED is similar to ECN but is used when senders cannot receive an explicit signal. If the ECN is available on the network, notifying the sender about congestion is the preferred option.