Congestion Control Study Notes for GATE & Computer Science Engineering Exams
By BYJU'S Exam Prep
Updated on: September 25th, 2023
When one a part of the subnet becomes overloaded, congestions results. Because routers are receiving packet faster than they will forward them, one among the 2 must happen. The subnet must prevent additional packets form entering the congested region until those already present are often processed. The congested routers can discard queued packets to form room for people who are arriving.
Table of content
Here we are providing the complete study notes on the Congestion Control for the preparation of GATE, Computer Science Engineering Exam.
Congestion Control Techniques: Several techniques can be employed for congestion control. These include
Warning Bit: A special bit in the packet header is set by the router to warn the source when congestion is detected. The bit is copied and piggy-backed on the ACK and sent to sender.
The sender mentions the number of ACK (acknowledgment) packets, it receives with the warning bit set and adjusts its transmission rate accordingly.
Choke Packets: A choke packet is control packet generated at congested node and transmitted to restrict traffic flow.
The source, one receiving the choke packet must reduce its transmission rate by a certain percentage.
Load Shedding: When buffers become full routers simply discard packets. Which packet is chosen to be the victim depends on the application and on the error strategy used in data link layer.
Random Early Discarded (RED): This is a proactive approach in which the router discards one or more packets before the buffer becomes completely full. Each time a packet arrives, the RED algorithm computes the average queue length.
Traffic Shaping
- Another method to congestion control is to shape the traffic before it enters the network.
- It controls the rate at which packets are sent (not just how many). Used in ATM and integrated services networks.
- At connections setup time, the sender and carrier negotiate a traffic pattern (shape).
- Two traffic shaping algorithms are as follows
- Leaky Bucket
- Token Bucket
The Leaky Bucket (LB) Algorithm
The Leaky Bucket algorithm used to control rate in the network. It is implemented as single-server queue with constant service time. If the buffer (bucket) overflows, then packets are discarded.
The leaky bucket enforces a constant output rate (average rate) regardless of the burstiness of the input. Does nothing when input is idle.
When packets are of the same size (as in ATM cells), the host should inject one packet per clock tick onto the network. But for variable length packets, it is better to allow a fixed number of bytes per tick.
Token Bucket (TB) Algorithm
In contrast to LB, the token bucket algorithm, allows the output rate to vary depending on the size of the burst.
According to the Token Bucket Algorithm:
C+ρs= Ms
where C= Capacity of the bucket
ρ= Token rate
s= Bursty traffic time in seconds
M= Output Rate
Congestion control at the transport layer:
There are three steps to control the congestion:
- Slow start algorithm: In this phase, the size of the sender’s window will increase exponentially until it became equal to the threshold value of the congestion network. Afterwards, Congestion avoidance will be used.
- Congestion Avoidance Algorithm: Here the increase in sender window size is additive i.e., increase in window size is based on RTT value. It is also known as linear increase and additive increase.
- Congestion detection algorithm: It is also known as the multiplicative decrease algorithm as the window size is getting reduced. It works as follows:
The graph can be shown as:
You can follow the detailed champion study plan for GATE CS 2022 from the following link:
Detailed GATE CSE 2022 Champion Study Plan
Aspirants can also practice 110+ Mock tests for exams like GATE, NIELIT, ISRO with BYJU’S Exam Prep Test Series check the following link here:
Click Here to Avail GATE CSE Test Series!
Thanks
Sahi Prep Hai Toh Life Set Hai!!
