15-441 Computer NetworkingCongestion Control ReviewTraffic and Resource ManagementResource Management ApproachesCongestion Control in Today’s InternetMore Ideas on Traffic ManagementRouter MechanismsTypical Internet QueuingFIFO + Drop-tail ProblemsSlide 10Active Queue ManagementDesign ObjectivesLock-out ProblemFull Queues ProblemRandom Early Detection (RED)RED AlgorithmRED OperationExplicit Congestion Notification (ECN) [ Floyd and Ramakrishnan 98]Congestion Control SummaryCongestion Control Summary (II)What are the Problems?Slide 22Throughput of UDP and TCP Flows With FIFOWhat Is the Solution?The Token BucketToken BucketTraffic Enforcement: ExampleRate-Limiting and SchedulingExample Outcome: Throughput of TCP and UDP Flows With Fair Queueing RouterFair QueueingFair QueueingFair Rate Computation: Example 1Fair Rate Computation: Example 2Fluid Flow SystemFluid Flow System: ExampleImplementation In Packet SystemPacket System: ExampleLimitations of Resource Management Architecture Today (II)Slide 39Components of Integrated Services NetworkControl Time ScaleObservations of Reservation SchemeIntegrated Services NetworkComponents of Flow QoS NetworkHow Things Fit TogetherPacket Classification AlgorithmSlide 4715-441 Computer NetworkingLecture 22 – Queue Management and QoSLecture 22: 2006-11-14 2Congestion Control Review•What is congestion control? •What is the principle of TCP?Lecture 22: 2006-11-14 3Traffic and Resource Management •Resources statistically shared•Overload causes congestion•packet delayed or dropped •application performance suffer•Local vs. network wide •Transient vs. persistent•Challenge•high resource utilization•high application performance)t(sourceRe)t(DemandiLecture 22: 2006-11-14 4Resource Management Approaches•Increase resources•install new links, faster routers•capacity planning, provisioning, traffic engineering•happen at longer timescale•Reduce or delay demand•Reactive approach: encourage everyone to reduce or delay demand•Reservation approach: some requests will be rejected by the network)t(sourceRe)t(DemandiLecture 22: 2006-11-14 5Congestion Control in Today’s Internet •End-system-only solution (TCP)•dynamically estimates network state•packet loss signals congestion •reduces transmission rate in presence of congestion•routers play little roleTCPTCPTCPControl Time scaleMonthsCapacity PlanningRTT (ms)Feedback ControlLecture 22: 2006-11-14 6More Ideas on Traffic Management •Improve TCP•Stay with end-point only architecture •Enhance routers to help TCP•Random Early Discard •Enhance routers to control traffic •Rate limiting•Fair Queueing •Provide QoS by limiting congestionLecture 22: 2006-11-14 7Router Mechanisms •Buffer management: when and which packet to drop? •Scheduling: which packet to transmit next? 12Schedulerflow 1flow 2flow nClassifierBuffer managementLecture 22: 2006-11-14 8Typical 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 22: 2006-11-14 9FIFO + 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 22: 2006-11-14 10FIFO + 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 22: 2006-11-14 11Active Queue Management•Design active router queue management to aid congestion control •Why?•Router has unified view of queuing behavior•Routers see actual queue occupancy (distinguish queue delay and propagation delay)•Routers can decide on transient congestion, based on workloadLecture 22: 2006-11-14 12Design 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 22: 2006-11-14 13Lock-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 22: 2006-11-14 14Full 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 22: 2006-11-14 15Random Early Detection (RED)•Detect incipient congestion•Assume hosts respond to lost packets•Avoid window synchronization•Randomly mark packets•Avoid bias against bursty trafficLecture 22: 2006-11-14 16RED 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 22: 2006-11-14 17RED OperationMin threshMax threshAverage Queue LengthminthmaxthmaxP1.0Avg queue lengthP(drop)Lecture 22: 2006-11-14 18Explicit Congestion Notification (ECN) [ Floyd and Ramakrishnan 98]•Traditional mechanism•packet drop as implicit congestion signal to end systems•TCP will slow down•Works well for bulk data transfer•Does not work well for delay sensitive applications•audio, WEB, telnet•Explicit Congestion Notification (ECN)•borrow ideas from DECBit•use two bits in IP header•ECN-Capable Transport (ECT) bit set by sender•Congestion Experienced (CE) bit set by routerLecture 22: 2006-11-14 19Congestion Control Summary•Architecture: end system detects congestion and slow down•Starting point: •slow start/congestion avoidance•packet drop detected by retransmission timeout RTO as congestion signal•fast
View Full Document
Unlocking...