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 in -active and session rate r= 1/x 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 i n-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 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