XCP: eXplicit Control ProtocolDina KatabiMIT Lab for Computer [email protected]/dinaSharing the Internet InfrastructureTwo Types of Requirements:1. Efficiency: Use links to maximum capacity2. Allocation: What is the share of each user?• Fairness; Differential Bandwidth Allocation; Priority …• Is fundamentalq Much research in Congestion Control, QoS, DiffServ, Pricing …• Is difficult because of Scale!Traditionally, a single mechanism controls both Efficiency and AllocationExample: In TCP, it is Additive-Increase Multiplicative-Decrease (AIMD)XCP Approach: Decouple Efficiency and Allocation Controls 1. Find best mechanism to control aggregate traffic at a link to achieve efficient links utilization2. Find best mechanism to shuffle the bandwidth in the aggregate traffic to converge to the desired allocationDecoupling Efficiency Control from Allocation ControlSharing Internet ResourcesShow it via examples …Congestion ControlExample 1:Congestion ControlExample 1:QueueCongestion ControlExample 1:QueueCongestion ControlExample 1:QueueCongestion ControlExample 1:QueueCongestion ControlExample 1:QueueCongestion!I should slow down!Congestion ControlExample 1:Congestion!I should slow down!Control the sources’ rates to get:• Efficiency: good link utilization, small queues, few drops• Fairness: Senders congested at same link get equal throughputThe Congestion Control ProblemTraditional ApproachTCPTCPTCP couples Efficiency & FairnessControl drops at router [RED, REM, AVQ, …]TCP’s ThroughputDropTimeTCP uses AIMD: • No Drop: Increase by a constant increment (i.e., 1 packet/RTT) • Drop: Halve throughputProblems with Current Approaches:• Good performance requires parameter tuning [RED, ARED, REM, PI-controller, AVQ, …] • Inefficient as bandwidth or delay increases [Low02]Round Trip Delay (sec)TCP UtilizationBottleneck Bandwidth (Mb/s)TCP Utilization⇒ Need to change congestion control because:• Bandwidth is increasing (demands for it are increasing too!) making TCP more inefficient• Delay is already a problem⇒ Need to change congestion control because:• Bandwidth is increasing (demands for it are increasing too!) making TCP more inefficient• Delay is already a problemCongestion Control is Inefficient Because:• Congestion feedback is binary (i.e., drop or no-drop) and indifferent to the degree of congestiono As a result, TCP oscillates between over-utilizing the link and under-utilizing itEfficient congestion control requiresExplicit feedback (I.e., routers tell senders the degree of congestion ) Efficient congestion control requiresExplicit feedback (I.e., routers tell senders the degree of congestion ) Solution:Answer: Per-flow state in routers ⇒ Doesn’t Scale!Unexpressive & ScalableExpressive & ScalableUnexpressive & UnscalableTCP, TFRC, Binomial, …Why Current Approaches Don’t Use Expressive Feedback?×Expressive & UnscalableIn ATM: ERICA, Charny’s , OSU, …(almost none in the Internet)(Flow: packets from same sender)• Efficient link utilization needs expressive feedback• In coupled systems, expressive feedback led to per-flow state (Unscalable!) Efficiency Problem:Solution: Use Decoupling• Decoupling looks at efficiency as a problem about aggregate traffic• Match aggregate traffic to link capacity and drain the queue• Benefits: No need for per-flow informationRouter computes a flow’s fair rate explicitlyTo make a decision, router needs state of all flowsUnscalableShuffle bandwidth in aggregate to converge to fair rates To make a decision, router needs state of this flowPut a flow’s state in its packets [Stoica]ScalableFairness ControlXCP: An eXplicit Control Protocol1. Efficiency Controller2.Fairness ControllerFeedback Round Trip TimeCongestion WindowCongestion HeaderFeedback Round Trip TimeCongestion WindowHow does XCP Work?Feedback = + 0.1 packetFeedback = + 0.1 packet Round Trip TimeCongestion WindowFeedback = - 0.3 packetHow does XCP Work?Congestion Window = Congestion Window + FeedbackRouters compute feedback without keeping any per-flow state Routers compute feedback without keeping any per-flow state How does XCP Work?How Does an XCP Router Compute the Feedback?Efficiency ControllerFairness ControllerGoal: Matches input traffic to link capacity & drains the queueGoal: Divides ∆ between flows to converge to fairnessLooks at aggregate traffic & queueLooks at a flow’s state in Congestion Header Algorithm:Aggregate traffic changes by ∆∆ ~ Spare Bandwidth∆ ~ - Queue SizeSo, ∆ = α davgSpare - β QueueAlgorithm:If ∆ > 0 ⇒ Divide ∆ equally between flowsIf ∆ < 0 ⇒ Divide ∆ between flows proportionally to their current rates(Proven to converge to fairness)MIMDAIMD∆ = α davgSpare - β Queue22402αβπα =<< andTheorem: System is stable (I.e., converges to efficiency) for any link bandwidth, delay, number of sources if:(Proof based on NyquistCriterion)It Is Tricky …Efficiency ControllerFairness ControllerNo Parameter TuningNo Parameter TuningAlgorithm:If ∆ > 0 ⇒ Divide ∆ equally between flowsIf ∆ < 0 ⇒ Divide ∆ between flows proportionally to their current ratesNeed to estimate number of flows N∑×=.avgdinpktsiavgiCwnddRTTNRTTi: Round Trip Time of pktiCwndi: Congestion Window in pktiNo Per-Flow StateNo Per-Flow StateWindows change by ∆ every davgTraffic rate changes by every davgRate r(t) changes per time unit byavgd∆2)()(avgavgdtQdtSrβα−=&2avgdr∆=&∆ = α davgSpare - β Queue22402αβπα =<< andTheorem: System is stable (I.e., converges to efficiency) for any link bandwidth, delay, number of sources if:(Proof based on NyquistCriterion)It Is Tricky …Efficiency ControllerFairness ControllerNo Parameter TuningNo Parameter TuningAlgorithm:If ∆ > 0 ⇒ Divide ∆ equally between flowsIf ∆ < 0 ⇒ Divide ∆ between flows proportionally to their current ratesNeed to estimate number of flows N∑×=.avgdinpktsiavgiCwnddRTTNRTTi: Round Trip Time of pktiCwndi: Congestion Window in pktiNo Per-Flow StateNo Per-Flow StateImplementationImplementation uses few multiplications & additions per packet Practical!XCP can co-exist with TCP and can be deployed graduallyGradual DeploymentPerformanceSimulations Show XCP is Better• Extensive Simulations • Compared with TCP over DropTail, RED, REM, AVQ, CSFQ XCP:• Better utilization• Near-zero drops• Fairer• Efficient & robust to increase in
View Full Document
Unlocking...