1 Computer)Networking)Conges1on)Control)Principles)of)Conges1on)Control)Conges1on:)• informally:)“too)many)sources)sending)too)much)data)too)fast)for)network)to)handle”)• different)from)flow)control!)• manifesta1ons:)– lost)packets)(buffer)overflow)at)routers))– long)delays)(queueing)in)router)buffers))• a)topE10)problem!)Conges1on)Control2 Causes/costs)of)conges1on:)scenario)1))• two)senders,)two)receivers)• one)router,)infinite)buffers))• no)retransmission)• large)delays)when)congested)• maximum)achievable)throughput)Conges1on)Control unlimited shared output link buffers Host A λin : original data Host B λout Causes/costs)of)conges1on:)scenario)2))• one)router,)finite)buffers))• sender)retransmission)of)lost)packet)Conges1on)Control finite shared output link buffers Host A λin : original data Host B λout λ'in : original data, plus retransmitted data3 Causes/costs)of)conges1on:)scenario)2))• always:)))))))))))))))))))))))))(goodput))• “perfect”)retransmission)only)when)loss:)• retransmission)of)delayed)(not)lost))packet)makes)))))))))larger)(than)perfect)case))for)same)Conges1on)Control λ"in λ"out = λ"in λ"out > λ"in λ"out “costs”)of)conges1on:))• more)work)(retrans))for)given)“goodput”)• unneeded)retransmissions:)link)carries)mul1ple)copies)of)pkt)R/2 R/2 λin λout b. R/2 R/2 λin λout a. R/2 R/2 λin λout c. R/4 R/3 Causes/costs)of)conges1on:)scenario)3))• four)senders)• mul1hop)paths)• 1meout/retransmit)Conges1on)Control λ"in Q:)what)happens)as))))))and)))))))))))increase)?)λ"in finite shared output link buffers Host A λin : original data Host B λout λ'in : original data, plus retransmitted data4 Causes/costs)of)conges1on:)scenario)3))Conges1on)Control another)“cost”)of)conges1on:))• when)packet)dropped,)any)“upstream)transmission)capacity)used)for)that)packet)was)wasted!)Host A Host B λoutApproaches)towards)conges1on)control)endEend)conges1on)control:)• no)explicit)feedback)from)network)• conges1on)inferred)from)endEsystem)observed)loss,)delay)• approach)taken)by)TCP)networkEassisted)conges1on)control:)• routers)provide)feedback)to)end)systems)– single)bit)indica1ng)conges1on)(SNA,)DECbit,)TCP/IP)ECN,)ATM))– explicit)rate)sender)should)send)at)Conges1on)Control two)broad)approaches)towards)conges1on)control:)5 TCP)conges1on)control:)Conges1on)Control ❒ goal:..TCP)sender)should)transmit)as)fast)as)possible,)but)without)conges1ng)network)❍ Q:)how)to)find)rate)just)below)conges1on)level)❒ decentralized:)each)TCP)sender)sets)its)own)rate,)based)on)implicit)feedback:))❍ ACK:)segment)received)(a)good)thing!),)network)not)congested,)so)increase)sending)rate)❍ lost.segment:)assume)loss)due)to)congested)network,)so)decrease)sending)rate)TCP)conges1on)control:)bandwidth)probing)Conges1on)Control ❒ “probing)for)bandwidth”:)increase)transmis sion )rate)on)receipt)of)ACK,)un1l)eventually)loss)occurs,)then)decrease)transmission)rate))❍ con1nue)to)increase)on)ACK,)decrease)on)loss)(since)available)bandwidth)is)changing,)depending)on)other)connec1ons)in)network)))ACKs being received, so increase rate X X X X X loss, so decrease rate sending rate time ❒ Q:)how)fast)to)increase/decrease?)❍ details)to)follow)TCP’s “sawtooth” behavior6 TCP)Conges1on)Control:)details)• sender)limits)rate)by)limi1ng)number)of)unACKed)bytes)“in)pipeline”:)– cwnd: differs)from)rwnd (how,)why?))• rwnd:)unused)buffer)space)– sender)limited)by min(cwnd,rwnd) • roughly,)• cwnd is)dynamic,)func1on)of)perceived)network)conges1on)Conges1on)Control rate = cwnd RTT bytes/sec LastByteSent-LastByteAcked ≤ cwnd cwnd!bytes RTT ACK(s) TCP)Conges1on)Control:))more)details)segment)loss)event:)reducing)cwnd!• 1meout:)no)response)from)receiver)– cut)cwnd to)1)• 3)duplicate)ACKs:)at)least)some)segments)geYng)through)(recall)fast)retransmit))– cut)cwnd)in)half,)less)aggressively)than)on)1meout)Conges1on)Control ACK)received:)increase)cwnd%❒ slowstart)phase:))❍ increase)exponen1ally)fast)(despite)name))at)connec1on)start,)or)following)1meout)❒ conges1on)avoidance:))❍ increase)linearly)7 TCP)Slow)Start)• when)connec1on)begins,)cwnd)=)1)MSS)– example:)MSS)=)500)bytes)&)RTT)=)200)msec)– ini1al)rate)=)20)kbps)• available)bandwidth)may)be)>>)MSS/RTT)– desirable)to)quickly)ramp)up)to)respectable)rate)• increase)rate)exponen1ally)un1l)first)loss)event)or)when)threshold)reached)– double)cwnd)every)RTT)– done)by)incremen1ng)cwnd)by)1)for)every)ACK)received)Conges1on)Control Host A one segment RTT Host B time two segments four segments TCP:)conges1on)avoidance)• when)cwnd > ssthresh)grow)cwnd)linearly)– increase)cwnd by)1)MSS)per)RTT))– approach)possible)conges1on)slower)than)in)slowstart)– implementa1on:)cwnd = cwnd + MSS/cwnd)for)each)ACK)received)Conges1on)Control ❒ ACKs:)increase)cwnd%by)1)MSS)per)RTT:)addi1ve)increase)❒ loss:)cut)cwnd)in)half)(nonE1meoutEdetected)loss)):)mul1plica1ve)decrease)AIMD)AIMD:)Addi1ve)Increase)Mul1plica1ve)Decrease)8 Popular)“flavors”)of)TCP)Conges1on)Control ssthresh ssthresh TCPTahoeTCPRenoTransmissionroundcwnd windowsize(insegments)Summary:)TCP)Conges1on)Control)• when)cwnd < ssthresh,)sender)in)slowEstart)phase,)window)grows)exponen1ally.)• when)cwnd >= ssthresh,)sender)is)in)conges1onEavoidance)phase,)window)grows)linearly.)• when)triple)duplicate)ACK)occurs,)ssthresh set)to)cwnd/2, cwnd set)to)~)ssthresh • when)1meout)occurs,)ssthresh)set)to)cwnd/2, cwnd)set)to)1)MSS.))Conges1on)Control9 TCP)Fai rness)fairness)goal:)if)K)TCP)sessions)share)same)bobleneck)link)of)bandwidth)R,)each)should)have)average)rate)of)R/K)Conges1on)Control TCP connection 1 bottleneck router capacity R TCP connection 2 Why)is)TCP)fair?)Two)compe1ng)sessions:)• Addi1ve)increase)gives)slope)of)1,)as)throughout)increases)• mul1plica1ve)decrease)decreases)throughput)propor1onally))Conges1on)Control R R equal bandwidth share Connection 1 throughput Connection 2 throughput congestion avoidance: additive increase loss: decrease window by factor of 2 congestion avoidance: additive increase loss: decrease window by factor of 210 Fairness)(more))Fairness)and)UDP)•
View Full Document