Fundamentals of Computer Networks: Congestion Control and Queuing Disciplines
This content delves into the principles of congestion control, queuing disciplines, and algorithms in computer networks. It covers topics such as packet scheduling, drop policies, FIFO, priority queuing, and common issues like packet discrimination and priority starvation. The images provided offer visual aids to better comprehend the concepts discussed, making it a valuable resource for understanding network management.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Congestion Control The Router s View 14-740: Fundamentals of Computer Networks Credit: Bill Nace Material from Computer Networking: A Top Down Approach, 6thedition. J.F. Kurose and K.W. Ross
traceroute Queuing Disciplines Random Early Drop (RED) Gateways 14-740: Fall 2017 2
Queuing Queue: A buffer with packets awaiting transmission Queuing algorithm determines Packet scheduling: ordering of transmission Allocates bandwidth Drop policy: which packet gets discarded Allocates buffer space Affects latency experienced by a packet 14-740: Fall 2017 3
Queuing Algorithms FIFO Priority Queueing Round Robin Queuing Fair Queuing (FQ) Weighted Fair Queuing (WFQ) 14-740: Fall 2017 4
First in, First Out No priority scheme Importance or source of the packet doesn t matter FIFO is a packet scheduling algorithm It determines the order of transmission 14-740: Fall 2017 5
Drop Tail Drop Tail is a drop policy It determines which packet is dropped FIFO with drop tail is the simplest of all packet scheduling algorithms/drop policies Most widely used in Internet routers 14-740: Fall 2017 6
FIFO-DT Problems Does not discriminate packets from all flows go in the same queue Importance or source of the packet doesn t matter Relies on end-hosts to implement congestion control but does not police the sources An ill-behaved end-host can send as fast as possible causing loss in other flows 14-740: Fall 2017 7
Priority Queuing FIFO + label each packet with a priority Router uses one queue for each priority Sends from highest priority queues first Drops from lowest priority queues first 14-740: Fall 2017 8
Priority Queuing Problem: High priority will starve low priority Economics (i.e. $$) could solve, but Internet is decentralized 14-740: Fall 2017 9
Round Robin Queuing Separate queue for each flow Router services each queue in turn (round-robin) If a flow sends too fast, its own queue would fill up Drop the packets? Separate drop policy can be implemented Multiple queues doesn t necessarily mean more wasted space 14-740: Fall 2017 10
Fair Queuing (FQ) Problem with Round Robin: Packets are not same length A flow with bigger packets will get more bandwidth in a packet-by-packet round- robin router 14-740: Fall 2017 11
FQ Algorithm Desired: Bit-by-bit round-robin But cannot send a bit at a time! Calculate transmission finishing time for each packet Transmit in order of finishing time 14-740: Fall 2017 12
FQ Characteristics Work conserving: Link is never left idle if there is at least one packet in a queue Effectively share a link with multiple flows For n flows, each uses 1/n of bandwidth Achieves max-min fairness Maximizes the min data rate of any flow ... thus no starvation of any flow 14-740: Fall 2017 13
Weighted FQ Assigns a weight (priority) to each queue From where? Manual config or source signaling Weight is proportional to number of bits to transmit each time the router services that queue FQ same as WFQ with weight = 1 for each queue Not exactly reservation-based, but can be used as a component of reservation-based resource allocation Differentiated Services Architecture 14-740: Fall 2017 14
traceroute Queuing Disciplines Random Early Drop (RED) Gateways 14-740: Fall 2017 15
Congestion Control TCP controls congestion once it happens Strategy: increase load to find the point where congestion happens Then back off Rinse, repeat TCP needs to create loss to discover available bandwidth 14-740: Fall 2017 16
Congestion Avoidance Can we avoid congestion before it occurs? Sender could reduce send rate just before packets start being dropped Router knows congestion state (based on queue lengths) and could signal end- hosts DECbit, ATM ABR, TCP ECN Random Early Drop (RED) gateways 14-740: Fall 2017 17
What is RED? Router-centric congestion control But still leverages TCP end-hosts Active Queue Management (AQM) scheme Decides which connection to notify of congestion Randomly chooses a packet ... ... before buffer overflow, thus early Chosen packet is dropped to inform sender Also can mark with explicit congestion notification (ECN) flag without generating packet loss 14-740: Fall 2017 18
RED Design Guidelines Goals Reduce persistent queuing delay Reduce unnecessary packet drops in some cases Control average queue size Stay to left of knee point region of high throughput and low delay 14-740: Fall 2017 19
Design Guidelines (2) Avoid global synchronization Don t want all connections to back off and increase at the same time Avoid bias against bursty traffic which otherwise uses low bandwidth Don t want to drop packets mostly from bursty connections 14-740: Fall 2017 20
Algorithm for each packet arrival calculate average queue size avg if avg < minth add packet to queue if maxth avg mark(drop) the arriving packet if minth avg < maxth calculate probability pa rand < pa? if so: mark the arriving packet 14-740: Fall 2017 21
Another look Details: Compute Calculate How? How big is big? 14-740: Fall 2017 22
Compute Avg Queue Length Determines degree of burstiness that will be allowed in the router queue Use our old friend EWMA avg (1- ) avg + q_length Short-term increases in queue size do not result in significant increase in avg Focuses on long-lived congestion 14-740: Fall 2017 23
Example Queue size vs average queue size 14-740: Fall 2017 24
Short Term Variations? Why filter out the short-term variations? Isn t it good to react to congestion ASAP? End-host cannot react as soon as it is detected at the router It takes RTT/2 to signal sender By that time, transient congestion might be gone 14-740: Fall 2017 26
How big is big? Set some thresholds minth: if avg queue length is less than this, there is no congestion maxth: if greater than this, there is congestion if avg is between minth and maxth, then there is growing concern 14-740: Fall 2017 27
Calculate Probability Want to mark (i.e. drop) packets if the queue length is too long, and the longer it is, the more likely we want it to be that we drop: pb maxp (Avg - minth) / (maxth- minth) ... and not in clusters, so the longer the string of not- dropped packets, the more likely we want it to eb that we drop. pa pb / (1 - count pb) count is the number of packets not dropped while Avg has been medium pa is the actual drop probability 14-740: Fall 2017 28
Drop Probability 14-740: Fall 2017 29
What is wrong with Drop Tail? RED specifically tries to keep the router from Drop Tail regime Random and Early Biased against bursty connection When packets from a bursty connection arrive, highly likely the queue will overflow dropping those packets Global synchronization Drop packets from multiple connections at the same time causing them all to enter slow start 14-740: Fall 2017 30
Is RED Fair? Probability of a particular flow s packets being dropped is roughly proportional to the share of bandwidth that flow is getting at the router But an ill-behaved flow is not limited to its fair share Can identify bad flows, but additional mechanisms on top of RED needed to deal with them 14-740: Fall 2017 31
Problems with RED Relies on end-hosts reacting to ECN or packet loss Unresponsive flows may ... Ignore RED signals Use more than fair share of bandwidth Different application and traffic mix than in 1993 14-740: Fall 2017 32
Scaling problem Floyd93 used simulations of small networks to justify RED algorithm But, when scaling to large network, large propagation delays cause RED to update estimated avg queue length too slowly New variant: SPRED has emerged. It uses a Smith Predictor to better account for the impact of the delay upon the control loop. https://en.wikipedia.org/wiki/Smith_predictor 14-740: Fall 2017 33
RED Status How widely is RED deployed in the Internet? Fairly common in modern routers Research Extensions Weighted RED Adaptive / Active RED (ARED) infers if RED should be more / less aggressive based on observations of avg queue length 14-740: Fall 2017 34
Lesson Objectives Now, you should be able to: describe the differences between packet scheduling algorithms and drop policies describe the algorithm and issues with the following queueing algorithms: FIFO, Priority Queueing, Round Robin, Fair Queuing and Weighted Fair Queueing analyze a scenario using one of the following queueing algorithms: FIFO, Priority Queueing, Round Robin, Fair Queuing and Weighted Fair Queueing 14-740: Fall 2017 35
You should be able to: describe the opportunities for a router to do congestion control describe the goals and details of the RED Gateway algorithm, as well as its advantages when compared to FIFO or other queueing algorithsm calculate average queue length and drop probability as the RED algorithm does
