QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS Lectures 22 & 23 Flow and congestion control Eytan Modiano Eytan Modiano Slide 1 Laboratory for Information and Decision SystemsFLOW CONTROL QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS • Flow control: end-to-end mechanism for regulating traffic between sourceand destination • Congestion control: Mechanism used by the network to limit congestion • The two are not really separable, and I will refer to both as flow control • In either case, both amount to mechanisms for limiting the amount oftraffic entering the network – Sometimes the load is more than the network can handle Eytan Modiano Slide 2 Laboratory for Information and Decision SystemsWITHOUT FLOW CONTROL QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS • When overload occurs – queues build up – packets are discarded – Sources retransmit messages – congestion increases => instability • Flow control prevents network instability by keeping packetswaiting outside the network rather than in queues inside thenetwork – Avoids wasting network resources – Prevent “disasters” Eytan Modiano Slide 3 Laboratory for Information and Decision SystemsOBJECTIVES OF FLOW CONTROL QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS • Maximize network throughput • Reduce network delays • Maintain quality-of-service parameters – Fairness, delay, etc.. • Tradeoff between fairness, delay, throughput… Eytan Modiano Slide 4 Laboratory for Information and Decision SystemsFAIRNESS QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS Session 1 Session 2 Session 3 Session 4 • If link capacities are each 1 unit, then – Maximum throughput is achieved by giving short session one unitand zero units to the long session; total throughput of 3 units – One concept of fairness would give each user 1/2 unit; total throughput of 2 units – Alternatively, giving equal resources to each session would givesingle link users 3/4 each, and 1/4 unit to the long session Eytan Modiano Slide 5 Laboratory for Information and Decision SystemsFAIRNESS QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS Session 2 Session 1 C B D E A 1 1 1 10 • Limited buffer at node B • Clearly both sessions are limited to 1 unit of traffic • Without flow control, session 1 can dominate the buffer at node B – Since 10 session 1 packets arrive for each session 2 packet, 10/11packets in the buffer will belong to session 1 Eytan Modiano Slide 6 Laboratory for Information and Decision SystemsQuickTime™ and aGIF decompressorDEADLOCKS FROM BUFFER OVERFLOWS are needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS A B • If buffers at A fill up with traffic to B and vice versa, then A can not accept any traffic from B, and vice versa causing deadlock – A cannot accept any traffic from B – B cannot accept any traffic from A • A can be full of B traffic, B of C traffic, and C of A traffic. A B C Eytan Modiano Slide 7 Laboratory for Information and Decision SystemsWINDOW FLOW CONTROL QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS S Dpacket packet packet packet ACK ACK ACK • Similar to Window based ARQ – End-to-end window for each session, Wsd – Each packet is ACK’d by receiver – Total number of un-ACK’s packets <= Wsd ⇒ Window size is an upper-bound on the total number of packets and ACKs in the network ⇒ Limit on the amount of buffering needed inside network Eytan Modiano Slide 8 Laboratory for Information and Decision SystemsEND TO END WINDOWS QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS • Let x be expected packet transmission time, W be size of window,and d be the total round trip delay for a packet – Ideally, flow control would only be active during times of congestion Therefore, Wx should be large relative to the total round trip delay d in the absence of congestion If d <= Wx, flow control in-active and session rate r = 1/x If d > Wx, flow control active and session rate r = W/d packets per second A(W=6) W X A (W=6) W X 1 23 6 4 5 7 Bd B d Flow control not active Flow control active Eytan Modiano Slide 9 Laboratory for Information and Decision SystemsBehavior of end-end windows QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS 1/X W/d R = min { 1/x, W/d} packets/second WX round trip delay d • As d increases, flow control becomes active and limits the transmission rate • As congestion is alleviated, d will decrease and r will go back up • Flow control has the affect of stabilizing delays in the network Eytan Modiano Slide 10 Laboratory for Information and Decision SystemsChoice of window size QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS • Without congestion, window should be large enough to allowtransmission at full rate of 1/x packets per second – Let d’ = the round-trip delay when there is no queueing – Let N = number of nodes along the path – Let Dp = the propagation delay along the path ⇒ d’ = 2Nx + 2 Dp (delay for sending packet and ack along N links) ⇒ Wx > d’ => W > 2N + Dp/x • When Dp < x, W ~ 2N (window size is independent of prop. Delay) • When Dp >> Nx, W ~ 2Dp/x (window size is independent on path length Eytan Modiano Slide 11 Laboratory for Information and Decision SystemsImpact of congestion QuickTime™ and aGIF decompressorare needed to see this picture. QuickTime™ and a Photo - JPEG decompressorare needed to see this picture. LIDS •