S2L4 - Congestion Control (Factors of Congestion ( Assume streams of…
S2L4 - Congestion Control
When too many packets are present in a subnet, performance degrades. (Congestion).
Then the number of packets dumped by hosts is within its carrying capacity, they are all delivered. (except transmission errors).
The number delivered is proportional to number sent.
As traffic increases too far, routers can no longer cope and begin to drop packets.
Factors of Congestion
Assume streams of packets arriving on three or 4 input lines and they need same output line. Result is a queue will build up. If buffer insufficient to hold all of them, packets are lost.
Assume memory is upgraded, congestion will still get worse. By the time packets get in front of queue, they have already timed out and duplicates have been sent. All these packets will be forwarded to next router, increasing load all the way to destination
Slow Processors can cause congestion; if routers' CPU slow at performing work of queueing buffers, updating tables; queues will build up
Principles of Congestion Control
Many problems can be viewd in a control pov. All solution divided into two group: open loop & closed loop
Open loop (preventive) attempt to solve the problem by good design, making sure does not occur in the first place.
Closed loop (reactive) are based on concept of feedback loop. Three parts when applied to congestion:
Monitor system to detect where and when congestion occurs
Pass this info to places where action can be taken
Adjust system operation to correct problem
Congestion prevention policies
Concerned how fast a sender times out and what it transmits upon timeout
Out of-order caching (buffering) Policy
If receivers routinely discard all out-of-order packets, they will have to be retransmitted again later, creating extra load.
If each packet acknowledged immediately, the packets generate extra traffic. However saved to be allied onto reverse traffic, extra timeouts and retransmissions may occur
Flow Control Policy
A tight flow control scheme reduces data rate and thus helps fight congestion
Virtual & datagram circuits
The choice between using either affects congestion since many congestion contro algo work only with virtual-circuit subnets
Packet Queuing & Service Policy
Relates to whether routers have one queue per input line, on per output or both. It also relates to the order in which packets are processed
Packet Discard Policy
Rule telling which packet is dropped when there is no buffer space.
Routing Algo Policy
A good one can help avoid congestion by spreading traffic all over the lines.
Packet Lifetime Management Policy
Deals with how long a packet may live before being discarded. I too long packets may clog up for a long time; too short packets may timeout before reaching their destination, inducing retransmissions
First four same as data link layer
Timeout determination Policy
Deals with determining the timeout interval. too short extra packets sent unnecessarily; too long, congestion reduced but response time when packet is lost suffers
Congestion Control in VC subnets (open loop)
Idea: Once congestion has been signaled, no more VC are set up until problem has gone away. Attempts to set a new Transport Layer fails.
Alternative: Allow new VC but carefully route all new VC around the congested routers
Congestion Control in Datagram Subnets
Approach that can be used: Each router can monitor utilisation of its output lines & other resources. For e.g it can associate variable Unew to reflect utilisation of line. For good estimate, a sample of instantaneous line utilisation f can be made periodically and update Unew
Unew = aUold + (1-a)f
where a is how fast router forgets recent history.
Whenever Unew moves above thershold, output line enters WARNING state. Each new packet checks if line in WARNING state. If it is, some action taken (warning bit, choke packets
Dynamic. Hosts send as much data it wants, the network informs it when sending too much
Difficult to tune. By how much host should slow down? Details not readily available in practice
After receiving choke packet, host should ignore additional for a short while. For how long?
Hop-by-hop choke packet
Same as choke packet but takes effect at each hop while choke travel back to source
If source far away from congestion, it will take a long time for choke to arrive and slow down source. Improvement: Make each router on the path receive and send choke packets.
choke sent to router which slows down.
If WARNING state, router sends a choke packet back to the source. Data packet tagged to not generate any more CHOKE PACKETS further.
When source receives choke packet, required to reduce traffic generation to specified destination by X%
Source host ignores choke packets for a fixed time interval
After that host checks for choke packets for another interval. If choke received, implies line still congested
When no other options, packet should be dropped.
Total Packet dropping
When buffer fills and a packet segment is dropped, drop all the rest of the segments since useless
Sources must specify priority. when discarded, router chooses lower priority
Chooses oldest one in buffer. Works well with multimedia which requires short delays