LIDS Lectures 22 &23 Flow and congestion contro Eytan Modiano Laboratory for Information and Decision Systems
QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are needed to see this picture. LIDS Lectures 22 & 23 Flow and congestion control Eytan Modiano Eytan Modiano Slide 1 Laboratory for Information and Decision Systems
FLOW CONTROL LIDS Flow control: end-to-end mechanism for regulating traffic between source and 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 of traffic entering the network ometimes the load is more than the network can handle Laboratory for Information and Decision Systems
FLOW CONTROL QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are needed to see this picture. LIDS • Flow control: end-to-end mechanism for regulating traffic between source and 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 of traffic entering the network – Sometimes the load is more than the network can handle Eytan Modiano Slide 2 Laboratory for Information and Decision Systems
WITHOUT FLOW CONTROL LIDS when overload occurs queues build up packets are discarded Sources retransmit messages congestion increases = instability Flow control prevents network instability by keeping packets waiting outside the network rather than in queues inside the network Avoids wasting network resources Prevent"disasters” Laboratory for Information and Decision Systems
WITHOUT FLOW CONTROL QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are 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 packets waiting outside the network rather than in queues inside the network – Avoids wasting network resources – Prevent “disasters” Eytan Modiano Slide 3 Lab oratory for Information and Decision Systems
OBJECTIVES OF FLOW CONTROL LIDS Maximize network throughput Reduce network delays Maintain quality-of-service parameters Fairness delay etc Tradeoff between fairness, delay, throughput Laboratory for Information and Decision Systems
OBJECTIVES OF FLOW CONTROL QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are 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 Lab oratory for Information and Decision Systems
FAIRNESS 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 unit and 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 give single link users 3/4 each, and 1/4 unit to the long session Laboratory for Information and Decision Systems
FAIRNESS QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are 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 unit and 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 give single link users 3/4 each, and 1/4 unit to the long session Eytan Modiano Slide 5 Laboratory for Information and Decision Systems
FAIRNESS LIDS Session 2 Session 1 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/11 packets in the buffer will belong to session 1 Laboratory for Information and Decision Systems
FAIRNESS QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are needed to see this picture. LIDS Session 2 Session 1 B C D E A 1 1 10 1 • 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/11 packets in the buffer will belong to session 1 Eytan Modiano Slide 6 Laboratory for Information and Decision Systems
DEADLOCKS FROM BUFFER OVERFLOWS msm am. LIDS 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 Laboratory for Information and Decision Systems
QuickTime™ and a GIF decompressor DEADLOCKS FROM BUFFER OVERFLOWS are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are 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 t raffic from B – B cannot accept any t raffic 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 Lab oratory for Information and Decision Systems
WINDOW FLOW CONTROL LIDS S D 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 Laboratory for Information and Decision Systems
WINDOW FLOW CONTROL QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are needed to see this picture. LIDS S D packet 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 Lab oratory for Information and Decision Systems
END TO END WINDOWS 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 active and session rate r= wld packets per second WX WX T「「「「∏A12|34567 d d Flow control not active Flow control active Laboratory for Information and Decision Systems
END TO END WINDOWS QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are 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 active and session rate r = W/d packets per second A (W=6) W X A (W=6) W X 1 23 4 5 6 7 B d B d Flow control not active Flow control active Eytan Modiano Slide 9 Lab oratory for Information and Decision Systems
Behavior of end-end windows LIDS 1/X R=min(1/x, W/d packets/second Wld 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 Laboratory for Information and Decision Systems
Behavior of end-end windows QuickTime™ and a GIF decompressor are needed to see this picture. QuickTime™ and a Photo - JPEG decompressor are 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 netwo rk Eytan Modiano Slide 10 Lab oratory for Information and Decision Systems