Overview• How routers queue affects how TCP (and otherprotocols) behaves• Two router questions: drop policy, schedulingpolicy• Can reduce congestion through contentdistribution- Clients can cache- Services can use a CDNCongestion Control Revisited• Congestion is when the input rate >> output rate• In TCP, flow control prevents receiver fromdropping packets• Routers have limited storage too: queue overflows• TCP reacts to congestion by shrinking congestionwindow- Triple duplicate ack: halve window, enter CA state- Timeout: set window to 1, enter SS state• Today: what should routers do?Congestion at RouterDestination1.5-Mbps T1 linkRouterSource2Source1100-Mbps FDDI10-Mbps Ethernet• Router Goals- Prioritize who gets limited resources- Somehow interact well with TCPRouter design issues• Scheduling discipline- Which of multiple packets should you send next?- May want to achieve some notion of fairness- May want some packets to have priority• Drop policy- When should you discard a packet?- Which packet to discard?- Some packets more important (perhaps BGP)- Some packets useless w/o others (IP fragments)- Need to balance throughput & delayExample: FIFO tail dropArrivingpacketNext freebufferFree buffers Queued packetsNext totransmit(a)ArrivingpacketNext totransmit(b)Drop• Differentiates packets only by when they arrive• Might not provide useful feedback for sending hosts• Encourages sending as fast as possibleWhat to optimize for?• Fairness (in two slides)• High throughput – queue should never be empty• Low delay – so want short queues• Crude combination: power = Throughput/Delay- Want to convince hosts to offer optimal loadOptimalloadLoadThroughput/delayConnectionless flowsRouterSource2Source1Source3RouterRouterDestination2Destination1• Even in Internet, routers can have a notion of flows- E.g., base on IP addresses & TCP ports (or hash of those)- Soft state—doesn’t have to be correct- But if often correct, can use to form router policiesFairness• What is fair in this situation?- Each flow gets 1/2 link b/w? Long flow gets less?• Usually fair means equal- For flow bandwidths (x1, . . . , xn), fairness index:f(x1, . . . , xn) =(Pni=1xi)2nPni=1x2i- If all xis are equal, fairness is one- Weighted fairness is a simple extension• So what policy should routers follow?Scheduling Policy: Fair Queuing (FQ)• Explicitly segregates traffic based on flows• Ensures no flow consumes more than its share- Variation: weighted fair queuing (WFQ)• Note: if all packets were same length, would be easyFlow 1Flow 2Flow 3Flow 4Round-robinserviceFair Queueing Basics• Keep track of how much time each flow has usedlink• Compute how long a flow will have used link if ittransmits next packet• Send packet from flow which will have lowest useif it transmits- Why not flow with smallest use so far?- Because next packet may be huge (examples coming)FQ Algorithm• Suppose clock ticks each time a bit is transmitted• Pi: length of packet i• Si: time when packet i started transmission• Fi: time when packet i finished transmission• Fi= Si+ Pi• When does router start transmitting packet i?- If arrived before router finished packet i − 1 from this flow, thenimmediately after last bit of i − 1 (Fi−1)- If no current packets for this flow, then start transmitting whenarrives (call this Ai)• Thus: Fi= max(Fi−1, Ai) + PiFQ Algorithm (cont)• For multiple flows- Calculate Fifor each packet that arrives on each flow- Treat all Fis as timestamps- Next packet to transmit is one with lowest timestamp• Not perfect: can’t preempt current packet• Example:Flow 1 Flow 2(a) (b)OutputOutputF = 8F = 10F = 5F = 10F = 2Flow 1(arriving)Flow 2(transmitting)FQ Algorithm (cont)• One complication: inactive flows are penalized(Ai> Fi−1)• Over what interval do you consider fairness?- Standard algorithm considers no history- Each flow gets fair share while packets queued• Solution: Bi= Pi+ max(Fi−1, Ai− δ)• δ = interval of history to considerFair Queueing Importance• “Our packet-by-packet transmission algorithm issimply defined by the rule that, whenever a packetfinishes transmission, the next packet is the onewith the smallest Fαi.”• But, fair queueing not used in core routers: findingmin F in hundreds of thousands of flows isexpensive. Can be used on edge routers and lowspeed links.Drop Policy: Random Early Detection (RED)• Notification of congestion is implicit in Internet- Just drop the packet (TCP will timeout)- Could make explicit by marking the packet(ECN extension to IP allows routers to mark packets)• Early random drop- Don’t wait for full queue to drop packet- Instead, drop packets with some drop probability wheneverthe queue length exceeds some drop level- Prevents global synchronization: many TCP flows speedup, all have packets dropped, all slow down, etc.RED Details• Compute average queue lengthAvgLen = (1 − Weight) · AvgLen + Weight · SampleLen0 < Weight < 1 (usually 0.002)SampleLen is queue length each time a packet arrivesMaxThreshold MinThresholdAvgLenAvgLenQueue lengthInstantaneousAverageTime• Smooths out AvgLen over time- Don’t want to react to instantaneous fluctuationsRED Details (cont)• Two queue length thresholds:if AvgLen <= MinThreshold thenenqueue the packetif MinThreshold < AvgLen < MaxThreshold thencalculate probability Pdrop arriving packet with probability Pif MaxThreshold <= AvgLen thendrop arriving packetRED Details (cont)• Computing probability P- Pb= MaxP ·(AvgLen−MinThreshold)(MaxThreshold−MinThreshold)P(drop)1.0MaxPMinThresh MaxThreshAvgLen• Actual drop probability based on time since last drop- count = # pkts since drop or MinThresh < Avglen < MaxThresh- P = Pb/(1 − count · Pb)- Space out drops, separate when to drop from which to dropWhat P looks like00.20.40.60.810 10 20 30 40 50 60 70 80 90Count since last dropProbability of dropPb=0.05Pb=0.01Tuning RED- Probability of dropping a particular flow’s packet(s) is roughlyproportional to the share of the bandwidth that flow iscurrently getting- MaxP is typically set to 0.02- If traffic is bursty, then MinThreshold should be sufficientlylarge to allow link utilization to be maintained at an acceptablyhigh level- Difference between two thresholds should be larger than thetypical increase in the calculated average queue length in oneRTT; setting MaxThreshold to twice MinThreshold isreasonable for traffic on today’s
View Full Document
Unlocking...