Congestion ControlJean Walrandwww.eecs.berkeley.edu/~wlrWalrand 2OutlineThe ProblemWhat is fair?ApproachesWalrand 3The ProblemFlows share links:How to share the links bandwidth?Walrand 4The ProblemWhat should be the ideal sharing?? Does it matter?? What is fair?How can we implement it?? Flows are not aware ?of each other?of the network topology and link rates? Need a decentralized solutionWalrand 5The ProblemDoes it Matter?Congestion occurs? Access link?Slow link (56k, DSL, T1, wireless, …)? Access network?E.g., behind the DSLAMCan improve treatment of flows? E.g., one flow should not get a much smaller fraction of bandwidth? Some flows might need some guaranteed bandwidthWalrand 6The ProblemWhat is Fair?Possible definitions:Walrand 7The ProblemWhat is Fair?Example 1:Walrand 8The ProblemWhat is Fair?Example 2:Walrand 9The ProblemWhat is Fair?Example 3:Walrand 10ApproachesEnd-to-End Control:? Sources adjust their rates? Can share rate among different flowsTraffic shaping: ? Access control by network?Policing and dropping?Cheating RAWRouter bandwidth assignment:? Scheduling per class or “flow”?WFQ, DRR, Priority, …? Differentiated dropping or marking?WRED, RIO, …Walrand 11ApproachesEnd-to-End Control:? Idea: ?Not congested => increase rate?Congested => slow down? Questions:?How to detect congestion?? Missing ACKs: Usual TCP (Reno)? Delayed ACKs: TCP Vegas? Routers mark packets: ECN, AVQ, …?How to increase/slow down?? AIMD? Improved algorithmsWalrand 12ApproachesEnd-to-End: Detecting congestionTail Drop: Drop when full? Unfair to bursty traffic ? Multiple losses => bad for window size …? Synchronizes sourcesRED: Drop as recent average queue length becomes large: p(q_av)VQ: Monitor virtual queue served with slower rateECN: Mark instead of dropping; ACKs reflect marks –Obviously betterWalrand 13ApproachesEnd-to-End: AIMD - JustificationWalrand 14ApproachesEnd-to-End: AIMD - RenoWalrand 15ApproachesEnd-to-End: AIMD – Router MemoryThis is pretty bad …!Walrand 16ApproachesEnd-to-End: AIMD – REDThis is a bit idealized …Walrand 17ApproachesEnd-to-End: AIMD (cont)Solution: When source gets ACK,It replaces W by W + a.RTT/WSolution: When source gets ACK,It replaces W by W + a.RTT/WWalrand 18ApproachesEnd-to-End: AIMD (cont)Walrand 19ApproachesEnd-to-End: AIMD (cont)Walrand 20ApproachesEnd-to-End: AIMD + SchedulingWalrand 21ApproachesEnd-to-End: Admission ControlWalrand 22ApproachesAccess ControlInefficient: Unnecessarily limits x2and x3Walrand 23Approaches ApproachesAccess ControlWalrand 24ApproachesAccess ControlWalrand 25ApproachesRouter SchedulingComplex: Requires router configurationWalrand 26ApproachesRouter
View Full Document
Unlocking...