Internet Congestion Control with Active Queue Management (AQM)ContentsI. Internet Congestion ControlInternet Traffic EngineeringWhat is congestion ?What is congestion ? - 2Congestion Control and AvoidanceImplicit vs. Explicit feedbackImplicit vs. Explicit feedback - 2TCP Congestion ControlTCP Congestion Control - 2TCP Congestion Control - 3Slide 13Active Queue Management (AQM) - 1AQM - 2AQM - 3AQM - 4REDAQM - 5 : BLUEAQM - 6 : SREDAQM - 7 : AREDAQM - 8Explicit Congestion Notification (ECN)ECN - 2Slide 25II. Mathematical Modeling and AnalysisOverview - 1Overview - 2Mathematical Modeling of AQM - 2Mathematical Modeling of AQM - 3Mathematical Modeling of AQM - 4Mathematical Modeling of AQM - 5Mathematical Modeling of AQM - 6Mathematical Modeling of AQM - 7Mathematical Modeling of AQM - 8Problems with existing AQMsProblems with existing AQMs - 2Problems with existing AQMs - 3Problems with existing AQMs - 4Problems with existing AQMs - 5ContentsIII. Adaptive AQM and User ResponseInput traffic load PredictionAdaptive AQM algorithmsAdaptive AQM algorithms - 2Adaptive AQM algorithms - 3Adaptive AQM algorithms - 4Adaptive parameter configurationAdaptive parameter configuration - 2Adaptive parameter configuration - 3Adaptive User response algorithmSlide 53IV. Further StudiesMathematical Modeling and AnalysisMathematical Modeling and Analysis - 2Mathematical Modeling and Analysis - 3Slide 58Simulation studyPerformance MetricsOther approaches of CC - 1: PricingOther approaches - 2: OptimizationOther approaches - 3: FairnessMore about AQMMore about AQM - 2More about AQM - 3More about AQM - 4More about AQM - 5ReferencesInternet Congestion Control with Active Queue Management (AQM)September 4, 2001Seungwan Ryu([email protected])PhD Student of IE DepartmentUniversity at Buffalo2ContentsInternet Congestion ControlMathematical Modeling and AnalysisAdaptive AQM and User ResponseFurther studies3I. Internet Congestion ControlInternet Traffic EngineeringWhat is Congestion ?Congestion Control and AvoidanceImplicit vs. Explicit feedbackTCP Congestion ControlActive Queue management (AQM)Explicit Congestion Notification (ECN)4Internet Traffic EngineeringMeasurement: for reality checkExperiment: for Implementation IssuesAnalysis:Bring fundamental understanding of systemsMay loose important facts because of simplificationSimulation:Complementary to analysis: Correctness, exploring complicate modelMay share similar model to analysis5What is congestion ?What is congestion ?The aggregate demand for bandwidth exceeds the available capacity of a link.What will be occur ?Performance Degradation•Multiple packet losses•Low link utilization (low Throughput)•High queueing delay•Congestion collapse6What is congestion ? - 2 Congestion ControlOpen-loop control- Mainly used in circuit switched network (GMPLS)Closed-loop control- Mainly used in packet switched network- Use feedback information: global & localImplicit feedback control- End-to-end congestion control- Examples:TCP Tahoe, TCP Reno, TCP Vegas, etc.Explicit feedback control- Network-assisted congestion control- Examples:IBM SNA, DECbit, ATM ABR, ICMP source quench, RED, ECN7Congestion Control and AvoidanceTwo approaches of handling CongestionCongestion Control (Reactive)•Play after the network is overloadedCongestion Avoidance (Proactive)•Play before the network becomes overloaded8Implicit vs. Explicit feedbackImplicit feedback Congestion ControlNetwork drops packets when congestion occurSource infers congestion implicitly•time-out, duplicated ACKs, etc.Example: end-to-end TCP congestion ControlSimple to implement but inaccurate •implemented only at transport layer (e.g., TCP)9Implicit vs. Explicit feedback - 2Explicit feedback Congestion ControlNetwork component (e.g., router) provides congestion indication explicitly to sources•use packet marking, or RM cells (in ATM ABR control)Examples: DECbit, ECN, ATM ABR CC, etc.Provide more accurate information to sources But is more complicate to implement•Need to change both source and network algorithm•Need cooperation between sources and network component10TCP Congestion ControlUses end-to-end congestion controluses implicit feedback •e.g., time-out, triple duplicated ACKs, etc. uses window based flow control•cwnd = min (pipe size, rwnd)•self-clocking•slow-start and congestion avoidanceExamples:•TCP Tahoe, TCP Reno, TCP Vegas, etc.11TCP Congestion Control - 2Slow-start and Congestion AvoidancecwndTimeRTT124Slow StartW*WW+1RTTCongestion AvoidanceW*/212TCP Congestion Control - 3TCP TahoeUse slow start/congestion avoidanceFast retransmit: an enhancementdetect packet (segments) drop by three duplicate ACKsW = W/2, and enter congestion avoidanceTCP Reno (fast recovery)Upon receiving three duplicate ACKsssthresh = W/2, and retransmit missing packetsW = ssthresh +3Upon receiving next ACK: W = ssthreshAllow the window size grow fast to keep the pipeline full13TCP Congestion Control - 3TCP SACK (Selected Acknowledgement)TCP (Thaoe) sender can only know about a single lost per RTTSACK option provides better recovery from multiple lossesThe sender can transmit all lost packetsBut those packets may have already been receivedOperationAdd SACK option into TCP headerThe receiver sends back SACK to sender to inform the reception of the packetThen, the sender can retransmit only the missing packet14Active Queue Management (AQM) - 1Performance Degradation in current TCP Congestion ControlMultiple packet lossLow link utilizationCongestion collapseThe role of the router becomes importantControl congestion effectively in networksAllocate bandwidth fairly15AQM - 2Problems with current router algorithmUse FIFO based tail-drop (TD) queue managementTwo drawbacks with TD: lock-out, full-queueLock-out: a small number of flows monopolize usage of buffer capacityFull-queue: The buffer is always full (high queueing delay)Possible solution: AQMDefinition: A group of FIFO based queue management mechanisms to support end-to-end congestion control in the Internet16AQM - 3Goals of AQMReducing the average queue length:Decreasing end-to-end delayReducing packet losses:More efficient resource allocationMethods:Drop packets before buffer becomes fullUse (exponentially