1Router Congestion Control:RED, ECN, and XCPWhere we left off• Signal of congestion: Packet loss• Fairness: Cooperating end-hosts usingAIMD– Next lecture: Enforcement for QoS, rate,delay, jitter guarantees• But note: A packet drop is a very bluntindicator of congestion• Routers know more than they’re telling…2What Would Router Do?• Congestion Signaling:– Drop, mark, send explicit messages• Buffer management:– Which packets to drop?– When to signal congestion?• Scheduling– If multiple connections, which one’s packets tosend at any given time?Congestion Signaling• Drops (we’ve covered)• In-band marking– One bit (congested or not): ECN– Multiple bits (how congested / how muchavailable): XCP• Out-of-band notification– IP Source Quench• Problem: It sends more packets when things arecongested…• Not widely used.3When to mark packets?• Drop-tail:– When the buffer is full– The de-facto mechanism today– Very easy to implement– Causes packets to be lost in bursts• Can lose many packets from a single flow…• Can cause synchronization of flows– Keeps average queue length high• ½ full. delay– Note relation to FIFO (first-in-first out): a schedulingdiscipline, NOT a drop policy, but they’re oftenbundledActive Queue Mgmt. w/RED• Explicitly tries to keep queue small– Low delay, but still high throughput under bursts– (This is “power”: throughput / delay)• Assumes that hosts respond to lost packets• Technique:– Randomization to avoid synchronization• (Recall that if many flows, don’t need as much buffer space!)– Drop before the queue is actually full4RED algorithm• If qa < min– Let all packets through• If qa > max– Drop all packets• If qa > min && qa < max– Mark or drop w/probability p_a• How to compute qa? How to compute pa?RED OperationMin threshMax threshAverage Queue LengthminthmaxthmaxP1.0Avg queue lengthP(drop)5Computing qa• What to use as the queue occupancy?– Balance fast response to changes– With ability to tolerate transient burps– Special case for idle periods…• EWMA to the rescue again…– Qa = (1 – wq)*qa + w_q * q• But what value of wq?– Back of the envelope: 0.002– RED is sensitive to this value, and it’s one of thethings that makes it a bit of a pain in practice– See http://www.aciri.org/floyd/red.htmlComputing pa• Pb via linear interpolation– Pb = max_p * (qa – min / max – min)• Method 1: pa = pb– Geometric random variable for inter-arrivals betweendrops.– Tends to mark in batches ( Sync)• Method 2:– Uniform r.v. X be uniform in {1, 2, … 1/pb-1}– Set pa = pb/(1-count * pb)• Count = # unmarked packets since last mark6RED parameter sensitivity• RED can be very sensitive to parameters– Tuning them is a bit of a black art!• One thing: “gentle” RED– max_p <= pb <= 1 as– maxthresh <= qa <= 2*maxthresh– instead of “cliff” effect. Makes RED more robust tochoice of maxthresh, max_p• But note: Still must choose wq, minthresh…• RED is not very widely deployed, but testingagainst both RED and DropTail is very commonin research, because it could be.“Marking”, “Detection”• RED is “Random Early Detection”– Could mean marking, not dropping• Marking?– DECbit: “congestion indication” binaryfeedback scheme.– If avg queue len >thresh, set the bit– If > half of packets marked, exponentialdecrease, otherwise linear increase7Marking 2: ECN• In IP-land– Instead of dropping a packet, set a bit– If bit set, react the same way as if it had been dropped (but youdon’t have to retransmit or risk losing ACK clocking)• Where does it help?– Delay-sensitive apps, particularly low-bw ones– Small window scenarios• Some complexity:– How to send in legacy IP packets (IP ToS field)– Determining ECN support: two bits (one “ECN works”, one“congestion or not”– How to echo bits to sender (TCP header bit)• More complexity: Cheating!– We’ll come back to this later. :)Beyond congestion indication• Why do we want to do more?• TCP doesn’t do so well in a few scenarios:– High bandwidth-delay product environments• Additive increase w/1000 packet window• Could take many RTTs to fill up after congestion• “not a problem” with a single flow with massive buffers (intheory)• a real problem with real routers and bursty cross-traffic– Short connections• TCP never has a chance to open its window– One caveat: A practical work-around to many ofthese problems is opening multiple TCP connections.The effects of this are still somewhat unexplored withregard to stability, global fairnes and efficiency, etc.8XCPFeedback =+ 0.1 packetRound Trip TimeCongestion WindowFeedback =- 0.3 packet How does XCP Work?9How Does an XCP Router Computethe Feedback?Congestion ControllerFairness ControllerGoal: Divides Δ betweenflows to converge to fairnessLooks at a flow’s state inCongestion HeaderAlgorithm:If Δ > 0 ⇒ Divide Δ equallybetween flowsIf Δ < 0 ⇒ Divide Δ betweenflows proportionally to theircurrent rates MIMD AIMDGoal: Matches input traffic tolink capacity & drains the queueLooks at aggregate traffic &queueAlgorithm:Aggregate traffic changes by ΔΔ ~ Spare BandwidthΔ ~ - Queue SizeSo, Δ = α davg Spare - β QueueΔ = α davg Spare - β Queue22402!"#!=<< andTheorem: System convergesto optimal utilization (i.e.,stable) for any link bandwidth,delay, number of sources if:(Proof based on NyquistCriterion)Getting the devil out of the details …Congestion ControllerFairness ControllerNo Parameter TuningAlgorithm:If Δ > 0 ⇒ Divide Δ equally between flowsIf Δ < 0 ⇒ Divide Δ between flowsproportionally to their current ratesNeed to estimate number offlows N!"=TinpktspktpktRTTCwndTN)/(1RTTpkt : Round Trip Time in headerCwndpkt : Congestion Window in headerT: Counting IntervalNo Per-Flow State10Apportioning feedback• Tricky bit: Router sees queue sizes andthroughputs; hosts deal in cwnd. Mustconvert.• Next tricky bit: Router sees packets;host’s response is the sum of feedbackreceived across its packets. Mustapportion feedback onto packets.• Requirement: No per-flow state at routerXCP: Positive Feedback• spare b/w to allocate• N flows• per-flow: Δ propto rtt– Larger RTT needs more cwnd increase to addsame amount of b/w• per-packet:– # packets observed in time d ~ cwnd/rtt– combining them: pi ~ spare/N
View Full Document
Unlocking...