Network CongestionOutlineCongestionControlling CongestionTCP Congestion ControlRouter-Based ControlSlide 7Economic InsightsSlide 9TCP-friendly Congestion ControlCongestion Control SchemesSingle-rate Vs. Multi-rateSingle-rate ProtocolsRate-based ApproachesWindow-based ApproachesMulti-rate ProtocolsSlide 17Slide 18MLDA and RainbowConclusionQuestions?Network CongestionNetwork CongestionGabriel NellUC BerkeleyOutlineOutlineBackground: what is congestion?Congestion control–End-to-end–Router-basedEconomic insightsOverview of TCP-friendly congestion control mechanismsCongestionCongestionThe state of sustained network overloadCongestion collapse–Traffic dominated by overhead such as packet retransmissionsCurrent internet–Dominated by best-effort traffic–TCP for guaranteed delivery; Congestion-aware–UDP for streaming applications; Congestion-unawareControlling CongestionControlling CongestionEnd-hosts–Advantages: cheap, scalable–Disadvantage: requires cooperationRouters–Advantages: can be more aggressive, has a complete picture of network traffic–Disadvantages: expensive, algorithms difficult to implement in hardwareTCP Congestion ControlTCP Congestion ControlImplemented at end hostsRelies on feedback–Implicit: packet drops indicate congestion–Explicit: ECN flags in headerCongestion controlled by changing window size: additive increase, multiplicative decrease (AIMD)Problem: delays in adapting to network conditions may cause oscillationsRouter-Based ControlRouter-Based ControlScheduling–Determines service order–Should be easy to implement, provide fairness and protection, and perform wellScheduling algorithms–FIFO (first in, first out)–Round-robin / weighted round-robin–Weighted fair queuingRouter-Based ControlRouter-Based ControlBuffer Management–Absorbs bursts–Shared/per-flow–Introduce delayQueue Management–Manage queue length, decide what packets to drop–RED effective, but difficult to parameterize for variable conditionsEconomic InsightsEconomic InsightsTragedy of the Commons–Network resources a public good–Negative externalitySolution: Internalize costs–Congestion pricing: cover fixed costs, charge extra under congestion conditions–Charge by willingness to payEconomic InsightsEconomic InsightsNew problem - customers prefer:–Flat rates–Constant performance, even if variable performance is better on averageTCP-friendly Congestion TCP-friendly Congestion ControlControlTCP-friendly: long-term throughput does not exceed that of TCP under the same conditionsMotivation: want to stream data such as audio and video without degrading overall network performanceFor convenience, consider long-lasting streamsCongestion Control SchemesCongestion Control SchemesWindow-based vs. Rate-basedUnicast vs. MulticastEnd-to-end vs. Router-supportedSingle-rate Vs. Multi-rateSingle-rate Vs. Multi-rateMeaningful when considering multicastSingle-rate sends data to each client at the same rateMultirate sends data to each client at whatever rate is best for that clientSingle-rate ProtocolsSingle-rate ProtocolsRate-based ApproachesRate-based ApproachesRAP – Rate Adaptation Protocol–Simple AIMD behaviorLDA+ – Loss-Delay Based Adaption Algorithm–Dynamic AIMD based on RTCP feedbackTFRC – TCP-Friendly Rate Control Protocol–Adjusts sending rate based on complex TCP equationTEAR – TCP Emulation at Receivers–Uses a congestion window to determine rate, but averages over larger timescalesWindow-based ApproachesWindow-based ApproachesRLA – Random Listening Algorithm–Tracks number n of congested receivers, window is decreased if a random number is 1/nMTCP – Multicast TCP–Arrange receivers in a tree, children report congestion to parents.–Root receives aggregate info, sends only as much data as smallest windowNCA – Nominee-Based Congestion Avoidance–Selects bottleneck as representative receiver, uses TCP-style congestion control algorithmMulti-rate ProtocolsMulti-rate ProtocolsRate-based ApproachesRate-based ApproachesRLC – Receiver-Driven Layered Congestion Control–Bandwidth consumed by each layer increases exponentially–Subscription to additional layers comes at particular times, which also increase exponentially; however congestion causes immediate layer dropsRate-based ApproachesRate-based ApproachesFLID-DL – Fair Layered Increase/Decrease with Dynamic Layering–Encodes data with digital fountain–Bandwidth consumed by a layer decreases over timeLTS/TFRP – Layered Transmission Scheme/TCP-Friendly Transport Protocol–Use simple TCP rate equation to decide subscription levelMLDA and RainbowMLDA and RainbowMLDA – Multicast Loss-Delay Based Adaption Algorithm (rate-based)–Same as LDA+, but performs rate calculation at receiverRainbow (window-based)–Encode data with digital fountain–Receivers individually request packets based on individual windowsConclusionConclusionCongestion is an important and complex problemMany solutions of varying effectiveness and complexity for various applicationsAreas of future research:–Methods of comparing protocols–Improve definitions of fairness, friendliness–Improve models of TCP
View Full Document