DOC PREVIEW
USC CSCI 551 - 12a_decbit-6up

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1 Computer Communications - CSCI 551 Copyright © William C. Cheng Congestion NotificationBill Chenghttp://merlot.usc.edu/cs551-f122Congestion Avoidance Computer Communications - CSCI 551 Copyright © William C. ChengDetect congestion after it happensTCP’s approach is reactive: Increase load trying to maximize utilization until lossoccursTCP has a congestion avoidance phase, but that’sdifferent from what we’re talking about hereWe can try to predict congestion and reduce rate beforeloss occursAlternatively, we can be proactive:This is called congestion avoidance3Router Congestion Notification Computer Communications - CSCI 551 Copyright © William C. ChengRouter has unified view of queueing behaviorRouters well-positioned to detect congestionRouters can distinguish between propagation andpersistent queueing delaysRouters can decide on transient congestion, based onworkloadHosts themselves are limited in their ability to infer thesefrom perceived behavior4Router Mechanisms Computer Communications - CSCI 551 Copyright © William C. ChengThe DEC-bit schemeCongestion notificationRandom Early Detection (RED)explicit congestion feedback to the sourceimplicit congestion feedback to the sourcewell suited for TCPCongestion Avoidance(DEC-bit)[Ramakrishnan90a]Bill Chenghttp://merlot.usc.edu/cs551-f125 Computer Communications - CSCI 551 Copyright © William C. Chengalternative to TCPApproach to do congestion avoidanceuses information from routers, not just end-to-endFirst use of explicit congestion notification (for window-basedprotocols)power, efficiency, fairnessDefines several terms6 Computer Communications - CSCI 551 Copyright © William C. Cheng Key IdeasOn congestion, router sets a bit (CI) bit on packetBasic ideas:Receiver relays bit to sender in acknowledgementsSender uses feedback to adjust sending rateRouter: feedback policy (how and when does a routergenerate feedback)Key design questions:Source: signal filtering (how does the sender respond?)7 Computer Communications - CSCI 551 Copyright © William C. Cheng The DEC-bit Schemesource0data packetcongestionindication bitrouter congestedrouterdestination1data packetcongestionindication bit1ack packetcongestionindication bit8Design Choices for Feedback Computer Communications - CSCI 551 Copyright © William C. ChengSeparate packets (source quench)you can be near 100% utilization without seeing athroughput degradationWhat kind of feedbackMark packets, receiver propagates marks in ACKsBased on router utilizationWhen to generate feedbackbut what queue lengths (instantaneous, average)?Queue lengthswhich is TCP?Congestion avoidance vs. congestion controlwhich is DEC-bit?packet lossFeedback mechanisms:source quench packetCI-bit (or DEC-bit): congestion indication9Options Computer Communications - CSCI 551 Copyright © William C. Chengdetection mechanismRouter10Components of a Congestion Avoidance System Computer Communications - CSCI 551 Copyright © William C. Chengfeedback sending mechanismfeedback receiving mechanismUserdecision policydecision frequency?filtering?response11Components of a Congestion Avoidance System(for DEC-bit) Computer Communications - CSCI 551 Copyright © William C. Chengdetection mechanism (average queue length)Routerfeedback sending mechanism (DEC-bit)feedback receiving mechanism (DEC-bit in ACK)Userdecision policydecision frequency? (2 RTT)filtering? (> 50% with DEC-bit set)response (AIMD: cwnd=0.875×cwnd)Fast implementations possibleIt is desirable to implement FIFOShares delay among connectionsGives low delay during burstsFIFO queue length is then a natural choice for detecting theonset of congestion12Why Queue Lengths? Computer Communications - CSCI 551 Copyright © William C. Chengneed to consider average, not instantaneouswant to give smoother feedback to the user (want toidentify longer term congestion, not just transientbursts)Measuring queue sizeoption: exponential weighted moving average (EWMA)of queue sizeQavg = α Qavg + (1 - α) Qinstchoice: average over regeneration cycleswhy not use fixed averaging interval? (perhapsself-tuning)average queue length is the area under the curvedivided by the total time for the regeneration cycle13 Computer Communications - CSCI 551 Copyright © William C. Cheng Measuring Queue SizeInstantaneouspremature, unfairPossibilities:Averaged over a fixedtime window, orexponential averagecan be unfair if timewindow different fromround-trip timeAdaptive queue lengthestimation: busy/idle cyclesSolutionBut need to account forlong current busy periods14 Computer Communications - CSCI 551 Copyright © William C. Cheng Computing Average Queue LengthsWe already know the answer to this: AIMDDEC-bit scheme uses a multiplicative factor of 0.875How often should the source change window?In response to what received information should it changeits window?By how much should the source change its window?15Sender Behavior Computer Communications - CSCI 551 Copyright © William C. ChengWindow size would oscillate dramatically because ittakes time for a window change’s effects to be feltNot on every ACK receivedWhere W is window size before update and W’ is sizeafter updateCorrect policy: wait for (W+W’) ACKs16How Often to Change Window? Computer Communications - CSCI 551 Copyright © William C. ChengDepends on the policy to set the thresholdUse the CI bits from W’ acks in order to decide whethercongestion still persistsClearly, if some fraction of bits are set, then congestionexistsWhat fraction?When queue size threshold is 1, cutoff fraction shouldbe 0.5This has the nice property that the resulting power isrelatively insensitive to this choice17Using Received Information Computer Communications - CSCI 551 Copyright © William C. ChengMonitor packets within a windowif < 50% had CI set, then increase window by 1Sender policyelse new window = window * 0.875Make change if more than 50% of packets had CI set:Additive increase, multiplicative decrease for stability18Changing the Sender’s Window Computer Communications - CSCI 551 Copyright © William C. ChengFairness19Metrics Computer Communications - CSCI 551 Copyright © William C. ChengPowerEfficiencywhere xi = Ai / DA=allocation, D=demand (identical for all i)Tries to evenly split bandwidth between all flows20Fairness Computer Communications - CSCI 551 Copyright © William C. Cheng(Pxi)2/n (Px2i)(Pxi)2/n (Px2i)Is this good or bad? Why is this hard?not everyone needs the same bandwidthTCP does not always split bandwidth


View Full Document

USC CSCI 551 - 12a_decbit-6up

Download 12a_decbit-6up
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 12a_decbit-6up and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 12a_decbit-6up 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?