15-441 Computer NetworkingOverviewTCP PerformanceSlide 4Slide 5Queuing DisciplinesTypical Internet QueuingFIFO + Drop-tail ProblemsSlide 9Active Queue ManagementDesign ObjectivesLock-out ProblemFull Queues ProblemRandom Early Detection (RED)RED AlgorithmRED OperationSlide 17Observed TCP ProblemsDelayed ACKSTCP ACK Generation [RFC 1122, RFC 2581]Delayed Ack ImpactSilly Window SyndromeNagel’s AlgorithmTCP ExtensionsLarge WindowsWindow Scaling: Example Use of OptionsMaximum Segment Size (MSS)Protection From WraparoundSlide 29Changing WorkloadsShort TransfersSlide 32Well Behaved vs. Wild WestTCP Fairness IssuesTCP (Summary)Slide 3615-441 Computer NetworkingLecture 10 – TCP & RoutersLecture 10: 09-30-2002 2Overview•TCP & router queuing•TCP details•WorkloadsLecture 10: 09-30-2002 3TCP Performance•Can TCP saturate a link?•Congestion control•Increase utilization until… link becomes congested•React by decreasing window by 50%•Window is proportional to rate * RTT•Doesn’t this mean that the network oscillates between 50 and 100% utilization?•Average utilization = 75%??•No…this is *not* right!Lecture 10: 09-30-2002 4TCP Performance•In the real world, router queues play important role•Window is proportional to rate * RTT•But, RTT changes as well the window•Window to fill links = propagation RTT * bottleneck bandwidth•If window is larger, packets sit in queue on bottleneck linkLecture 10: 09-30-2002 5TCP Performance•If we have a large router queue can get 100% utilization•But, router queues can cause large delays•How big does the queue need to be?•Windows vary from W W/2•Must make sure that link is always full•W/2 > RTT * BW•W = RTT * BW + Qsize•Therefore, Qsize > RTT * BW•Ensures 100% utilization•Delay?•Varies between RTT and 2 * RTTLecture 10: 09-30-2002 6Queuing Disciplines•Each router must implement some queuing discipline•Queuing allocates both bandwidth and buffer space:•Bandwidth: which packet to serve (transmit) next •Buffer space: which packet to drop next (when required)•Queuing also affects latencyLecture 10: 09-30-2002 7Typical Internet Queuing•FIFO + drop-tail•Simplest choice•Used widely in the Internet•FIFO (first-in-first-out) •Implies single class of traffic•Drop-tail•Arriving packets get dropped when queue is full regardless of flow or importance•Important distinction:•FIFO: scheduling discipline•Drop-tail: drop policyLecture 10: 09-30-2002 8FIFO + Drop-tail Problems•Leaves responsibility of congestion control completely to the edges (e.g., TCP)•Does not separate between different flows•No policing: send more packets get more service•Synchronization: end hosts react to same eventsLecture 10: 09-30-2002 9FIFO + Drop-tail Problems•Full queues•Routers are forced to have have large queues to maintain high utilizations•TCP detects congestion from loss•Forces network to have long standing queues in steady-state•Lock-out problem•Drop-tail routers treat bursty traffic poorly•Traffic gets synchronized easily allows a few flows to monopolize the queue spaceLecture 10: 09-30-2002 10Active Queue Management•Design active router queue management to aid congestion control •Why?•Router has unified view of queuing behavior•Routers can distinguish between propagation and persistent queuing delays•Routers can decide on transient congestion, based on workloadLecture 10: 09-30-2002 11Design Objectives•Keep throughput high and delay low•High power (throughput/delay)•Accommodate bursts•Queue size should reflect ability to accept bursts rather than steady-state queuing•Improve TCP performance with minimal hardware changesLecture 10: 09-30-2002 12Lock-out Problem•Random drop•Packet arriving when queue is full causes some random packet to be dropped•Drop front•On full queue, drop packet at head of queue•Random drop and drop front solve the lock-out problem but not the full-queues problemLecture 10: 09-30-2002 13Full Queues Problem•Drop packets before queue becomes full (early drop)•Intuition: notify senders of incipient congestion•Example: early random drop (ERD):•If qlen > drop level, drop each new packet with fixed probability p•Does not control misbehaving usersLecture 10: 09-30-2002 14Random Early Detection (RED)•Detect incipient congestion•Assume hosts respond to lost packets•Avoid window synchronization•Randomly mark packets•Avoid bias against bursty trafficLecture 10: 09-30-2002 15RED Algorithm•Maintain running average of queue length•If avg < minth do nothing•Low queuing, send packets through•If avg > maxth, drop packet•Protection from misbehaving sources•Else mark packet in a manner proportional to queue length•Notify sources of incipient congestionLecture 10: 09-30-2002 16RED OperationMin threshMax threshAverage Queue LengthminthmaxthmaxP1.0Avg queue lengthP(drop)Lecture 10: 09-30-2002 17Overview•TCP & router queuing•TCP details•WorkloadsLecture 10: 09-30-2002 18Observed TCP Problems•Too many small packets•Delayed acks•Silly window syndrome•Nagel’s algorithmLecture 10: 09-30-2002 19Delayed ACKS•Problem:•In request/response programs, you send separate ACK and Data packets for each transaction•Solution:•Don’t ACK data immediately•Wait 200ms (must be less than 500ms – why?)•Must ACK every other packet•Must not delay duplicate ACKsLecture 10: 09-30-2002 20TCP ACK Generation [RFC 1122, RFC 2581]EventIn-order segment arrival, No gaps,Everything else already ACKedIn-order segment arrival, No gaps,One delayed ACK pendingOut-of-order segment arrivalHigher-than-expect seq. #Gap detectedArrival of segment that Partially or completely fills gapTCP Receiver actionDelayed ACK. Wait up to 500msfor next segment. If no next segment,send ACKImmediately send singlecumulative ACK Send duplicate ACK, indicating seq. #of next expected byteImmediate ACK if segment startsat lower end of gapLecture 10: 09-30-2002 21Delayed Ack Impact•TCP congestion control triggered by acks•If receive half as many acks window grows half as fast•Slow start with window = 1•Will trigger delayed ack timer•First exchange will take at least 200ms•Start with > 1 initial window•Bug in BSD, now a “feature”/standardLecture 10: 09-30-2002 22Silly Window Syndrome•Problem: (Clark, 1982)•If receiver advertises small increases in the receive window then the sender may waste time sending lots of
View Full Document
Unlocking...