Slide 1Chapter 3 outlinePrinciples of Congestion ControlCauses/costs of congestion: scenario 1Causes/costs of congestion: scenario 2Causes/costs of congestion: scenario 2Causes/costs of congestion: scenario 3Causes/costs of congestion: scenario 3Approaches towards congestion controlCase study: ATM ABR congestion controlCase study: ATM ABR congestion controlChapter 3 outlineSlide 13TCP Congestion Control: detailsTCP Slow StartTCP Slow Start (more)RefinementRefinement: inferring lossSummary: TCP Congestion ControlTCP throughputSaw Tooth behaviorTCP FairnessWhy is TCP fair?Chapter 3: SummaryTransport Layer 3-1CS 118 Spring 2014Chpt 3 - Section 3DTransport Layer 3-2Chapter 3 outline3.1 Transport-layer services3.2 Multiplexing and demultiplexing3.3 Connectionless transport: UDP3.4 Principles of reliable data transfer3.5 Connection-oriented transport: TCPsegment structurereliable data transferflow controlconnection management3.6 Principles of congestion control3.7 TCP congestion controlTransport Layer 3-3Principles of Congestion ControlCongestion:informally: “too many sources sending too much data too fast for network to handle”different from flow control!manifestations:lost packets (buffer overflow at routers)long delays (queueing in router buffers)a top-10 problem!Transport Layer 3-4Causes/costs of congestion: scenario 1 two senders, two receiversone router, infinite buffers no retransmissionlarge delays when congestedmaximum achievable throughputLink Capacity = Cunlimited shared output link buffersHost Alin : original dataHost BloutTransport Layer 3-5Causes/costs of congestion: scenario 2 one router, finite buffers sender retransmission of lost packetfinite shared output link buffersHost Alin : original dataHost Bloutl'in : original data, plus retransmitted dataTransport Layer 3-6Causes/costs of congestion: scenario 2 always: (goodput) because of finite buffer“perfect” retransmission only when loss:retransmission of delayed (not lost) packet makes larger (than perfect case) for samelinlout=linlout>linlout“costs” of congestion: more work (retrans) for given “goodput”unneeded retransmissions: link carries multiple copies of pktR/2R/2linloutb. Finite bufferR/2R/2linlouta. Infinite bufferR/2R/2linloutc. Dupl retransmR/4R/3Transport Layer 3-7Causes/costs of congestion: scenario 3 four sendersmultihop pathstimeout/retransmitlinQ: what happens as and increase ?linfinite shared output link buffersHost Alin : original dataHost Bloutl'in : original data, plus retransmitted dataHost CHost DDeadlock: Queue 1 is full with D->B pkts etc Queue 1Queue 2Queue 3Queue 4Transport Layer 3-8Causes/costs of congestion: scenario 3 In a deadlock, all input packets dropped - no progressHost AHost BloutDeadlock!!!DeadlockTransport Layer 3-9Approaches towards congestion controlEnd-end congestion control:no explicit feedback from networkcongestion inferred from end-system observed loss, delayapproach taken by TCPNetwork-assisted congestion control:routers provide feedback to end systemssingle bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM)explicit rate sender should send atTwo broad approaches towards congestion control:Transport Layer 3-10Case study: ATM ABR congestion controlABR: available bit rate:“elastic service” if sender’s path “underloaded”: sender should use available bandwidthif sender’s path congested: sender throttled to minimum guaranteed rateRM (resource management) cells:sent by sender, interspersed with data cellsbits in RM cell set by switches (“network-assisted”) NI bit: no increase in rate (mild congestion)CI bit: congestion indicationRM cells returned to sender by receiver, with bits intactTransport Layer 3-11Case study: ATM ABR congestion controltwo-byte ER (explicit rate) field in RM cellcongested switch may lower ER value in cellsender’ send rate thus maximum supportable rate on pathEFCI bit in data cells: set to 1 in congested switchif data cell preceding RM cell has EFCI set, sender sets CI bit in returned RM cellThe above is nice, but MUCH “too complicated” for the Internet designers - rule: keep design SIMPLE and complexity out of the Network, in the HostsTransport Layer 3-12Chapter 3 outline3.1 Transport-layer services3.2 Multiplexing and demultiplexing3.3 Connectionless transport: UDP3.4 Principles of reliable data transfer3.5 Connection-oriented transport: TCPsegment structurereliable data transferflow controlconnection management3.6 Principles of congestion control3.7 TCP congestion controlTransport Layer 3-13TCP congestion control: additive increase, multiplicative decreaseApproach: increase transmission rate (window size), probing for usable bandwidth, until loss occursadditive increase: increase CongWin by 1 MSS every RTT until loss detectedmultiplicative decrease: cut CongWin in half after loss timecongestion window sizeSaw toothbehavior: probingfor bandwidth8 Kbytes16 Kbytes24 KbytestimecongestionwindowTransport Layer 3-14TCP Congestion Control: detailssender limits transmission: LastByteSent-LastByteAcked CongWinRoughly,CongWin is dynamic, function of perceived network congestionHow does sender perceive congestion?loss event = timeout or 3 duplicate acksTCP sender reduces rate (CongWin) after loss eventthree CongWin “reduction”+ “growth” mechanisms:AIMDslow startconservative after timeout eventsrate = CongWin RTT Bytes/secTransport Layer 3-15TCP Slow StartWhen connection begins, CongWin = 1 MSSExample: MSS = 500 bytes & RTT = 200 msecinitial rate = 20 kbpsavailable bandwidth may be >> MSS/RTTdesirable to quickly ramp up to respectable rateWhen connection begins, increase rate exponentially fast until first loss eventTransport Layer 3-16TCP Slow Start (more)When connection begins, increase rate exponentially until first loss event:double CongWin every RTTdone by incrementing CongWin for every ACK receivedSummary: initial rate is slow but ramps up exponentially fastHost Aone segmentRTTHost Btimetwo segmentsfour segmentsTransport Layer 3-17RefinementQ: When should the exponential increase switch to linear? A: When CongWin gets to 1/2 of its value before timeout. Implementation:Variable Threshold At loss event, Threshold
View Full Document
Unlocking...