CS551TCP Congestion ControlBill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. Chengrouters have finite buffer (packets get dropped)Retransmissions costs: (routers have finite buffer, sopacket get dropped)even if routers have infinite buffer spaceQueueing delays in router as packet arrival rate nearslink capacity2Causes and Costs of Congestion Computer Communications - CSCI 551 Copyright © William C. Chengcosts: wasting bandwidth to forward unneeded copiesretransmitted data eat up bandwidthwhen a packet is dropped along a path, the transmissioncapacity that was used at each of the upstream routersto forward that packet was wastedefficiencyThe theory behind congestion controlstabilityRetransmissions of large packets after loss of a singlefragmentIf both sources send at full speed, the router is overwhelmed3Congestion Computer Communications - CSCI 551 Copyright © William C. ChengOther forms of congestion collapse:Non-feedback controlled sources10 Mbps10 Mbps1.5 Mbpscongestion collapse: senders lose data from congestionand they resend, causing more congestion (can beself-reinforcing)Uses network resources efficientlyA mechanism which:Preserves fair network resource allocationPrevents or avoids collapseCongestion collapse is not just a theoryHas been frequently observed in many networksdelayloadthroughputload4 Computer Communications - CSCI 551 Copyright © William C. Cheng Congestion Control and Avoidanceknee cliffknee cliffavoids overrunning the receiverWhat does flow control do?avoids overrunning router buffers and saturating thenetworkWhat does congestion control do?both use windows: wnd for flow control and cwnd forcongestion control, actual window used is min(wnd,cwnd)What mechanism do they use?5 Computer Communications - CSCI 551 Copyright © William C. Cheng Congestion Control vs. Flow Control6 Computer Communications - CSCI 551 Copyright © William C. Cheng Congestion Control GoalsEfficiency (maximize throughput or power [Ramakrishnan90a])Fairness [Ramakrishnan90a]Stability [Jacobson88a]7 Computer Communications - CSCI 551 Copyright © William C. Cheng FairnessBut, defining fairness is hard... what is a user?Should treat all users equallyIn the absence of knowing requirements, assume a fairallocation means equal allocationMeasuring fair allocations [Ramakrishnan90a]Jain and Chiu’s fairness index:(Pxi)2/n (Px2i)(Pxi)2/n (Px2i)xi = throughput of flow iEx: fairness index = 1 if all xi are equalEx: fairness index = k/n if k out of n flows are equaland other flows (n-k) receives 0 throughputhost, flow, person?n flows through a link, each flow should get 1/n bandwidthwhat if their needs are different?Other schemes, e.g., fair queueing [Demers89a]power = throughput αdelaydelayloadthroughputloadpowerloadknee cliff8Efficiency Computer Communications - CSCI 551 Copyright © William C. ChengWant most throughput withlow delayPower [Ramakrishnan90a]0<α<1, α=1 results in powerbeing maximized at theknee of the curveSystem is most efficientat knee of curve(others may say that theknee of the delay curve is at L2)L1L2Avoidance keeps system at knee of curveAvoidance or control?9Congestion Control Design Computer Communications - CSCI 551 Copyright © William C. ChengBut, to do that, need routers to send accurate signals(some feedback)TCP uses its window to do congestion controlSending host must adjust amount of data it puts in thenetwork based on detected congestionBut what’s the right strategy to increase/decrease window(slow start, congestion avoidance, exponential backoff)Control responds to loss after the factbut also avoidance, sort ofthis is what ECN tries to accomplishanother possibility is to use rate (in the future)When to increase/decrease cwnd?10How To Adjust Window in TCP? Computer Communications - CSCI 551 Copyright © William C. ChengEfficiencyConstraints:FairnessStability or convergence (too much oscillation is bad)Out-of-date informationRTT is fundamental limit to how quickly you can reactObserve networkA control theory problemReduce window when congestion is perceivedIncrease window otherwiseto change additively: ai(t)Formulation allows for the feedback signal:11Linear Control Computer Communications - CSCI 551 Copyright © William C. Chengto change multiplicatively: bi(t)What does TCP do?Xi(t+1) = ai(t) + bi(t)Xi(t)user 1user 2user nΣΣ xi > Xgoal ?networkcan consider feedbackAIMD: additive increase, multiplicative decreasemaximize stability: slow increase, fast decrease12Linear Control Example [Chiu89a] Computer Communications - CSCI 551 Copyright © William C. Chenguser 1’s allocation x1user 2’s allocation x2fairnesslineefficiency line(full utilization)overloadunderloadoptimal(efficient and fair)13Linear Control Example [Chiu89a] Computer Communications - CSCI 551 Copyright © William C. Chenguser 1’s allocation x1user 2’s allocation x2fairnesslineefficiency line(full utilization)(x10,x20)14Linear Control Example [Chiu89a] Computer Communications - CSCI 551 Copyright © William C. Chenguser 1’s allocation x1user 2’s allocation x2fairnesslineadditiveincrease(x10,x20)efficiency line(full utilization)multiplicativeincrease15Linear Control Example [Chiu89a] Computer Communications - CSCI 551 Copyright © William C. Chenguser 1’s allocation x1user 2’s allocation x2fairnesslineadditiveincrease(x10,x20)efficiency line(full utilization)multiplicativedecrease16Linear Control Example [Chiu89a] Computer Communications - CSCI 551 Copyright © William C. Chenguser 1’s allocation x1user 2’s allocation x2fairnesslineadditiveincrease(x10,x20)efficiency line(full utilization)17 Computer Communications - CSCI 551 Copyright © William C. Cheng Linear Control Result [Chiu89a]Decrease must be mutiplicativesmoothness implies that multiplicative increase factormust be exactly 1Efficiency, fairness and distributedness imply thatIncrease must be additive and may have a multiplicativefactor18TCP Equally Shares Bandwidth On ACongested Link Computer Communications - CSCI 551 Copyright © William C. ChengTCP stream 1 throughputTCP stream 2 throughputRRequalbandwidthsharefull bandwidthutilization lineAno slow start19TCP Equally Shares Bandwidth On ACongested Link (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengTCP stream 1 throughputTCP stream 2 throughputRRequalbandwidthsharefull bandwidthutilization lineABA → B:congestionavoidance forboth streamsparalle to the45-degree linepacket loss,
View Full Document
Unlocking...