15-441 Computer NetworkingCongestion Control ReviewTraffic and Resource Management Resource Management ApproachesCongestion Control in Today’s Internet More Ideas on Traffic Management Router Mechanisms Typical Internet QueuingFIFO + Drop-tail ProblemsFIFO + Drop-tail ProblemsActive 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? Throughput 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 Queueing Fair QueueingFair Rate Computation: Example 1Fair Rate Computation: Example 2 Fluid Flow SystemFluid Flow System: Example Implementation In Packet SystemPacket System: Example Limitations of Resource Management Architecture Today (II)Resource Management ApproachesComponents of Integrated Services NetworkControl Time ScaleObservations of Reservation SchemeIntegrated Services Network Components of Flow QoS NetworkHow Things Fit Together Packet Classification AlgorithmResource Management Approaches15-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(Demandi>∑Lecture 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(Demandi>∑Lecture 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 < minthdo 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
View Full Document