Lecture 12: Queuing, Caching, and ContentDistributionOverview• How routers queue affects how TCP and otherprotocols behave• Two router questions: drop policy, schedulingpolicy• Reducing congestion through content distribution- Clients can cache- Services can use a CDNCongestion Control Revisited• Congestion is when the input rate >> output rate- In TCP, flow control window ensures sender does notexceed rate at which receiver consumes data- What if senders exceed a router’s maximum output rate?• What should routers do? Make sender slow down• TCP sending rate = window-size/RTT, so 2 options:1. Increase RTT – buffer more packets =⇒ more queuing delay2. Reduce window size – happens if router drops packets• Recall TCP reacts to packet loss by shrinkingcongestion window- Triple duplicate ack: halve window, enter CA state- Timeout: set window to 1, enter SS stateCongestion 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 & delay- Could minimize/eliminate drops with enormous buffers- But queuing delay highly frowned upon (interactive apps)Example: FIFO tail dropArrivingpacketNext freebufferFree buffers Queued packetsNext totransmit(a)ArrivingpacketNext totransmit(b)Drop• Differentiates packets only by when they arrive- Packet dropped if queue full when it arrivesTail drop issues• When stable, queue will always be nearly full- Guarantees high latency for all traffic• Possibly unfair for flows with small windows- E.g., small flow (< 4 segments) may be stuck in backoff,while larger flows can use fast retransmit to recover• Window synchronization- Consider many flows in a stable configuration- New flow comes in, causes a bunch of packet losses- Existing flows all cut their windows together(underutilizing link)- Flows all grow their windows together until link againoverloaded and many packets lost. Repeat. . .What 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 Queuing 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 window synchronization: many TCP flowsspeed up, all have packets dropped, all slow down, etc.RED Details• Compute average queue length- AvgLen = (1 − Weight) · AvgLen + Weight · SampleLen- 0 < 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
View Full Document
Unlocking...