Queue simulations

Queue simulations

The Internets architecture for managing congestion Damon Wischik, UCL www.wischik.com/damon Some Internet History 1974: First draft of TCP/IP [A protocol for packet network interconnection, Vint Cerf and Robert Kahn] 1983: ARPANET switches on TCP/IP 1986: Congestion collapse 1988: Congestion control for TCP [Congestion avoidance and control, Van Jacobson] A Brief History of the Internet, the Internet Society End-to-end control Internet congestion is controlled by the end-systems. The network operates as a dumb pipe. [End-to-end arguments in system design by Saltzer, Reed, Clark, 1981] request User Server (TCP) End-to-end control

Internet congestion is controlled by the end-systems. The network operates as a dumb pipe. [End-to-end arguments in system design by Saltzer, Reed, Clark, 1981] Server (TCP) User data End-to-end control Internet congestion is controlled by the end-systems. The network operates as a dumb pipe. [End-to-end arguments in system design by Saltzer, Reed, Clark, 1981] acknowledgements Server (TCP) User data The TCP algorithm, running on the server, decides how fast to send data. traffic rate [0-100 kB/sec] TCP time [0-8 sec]

if (seqno > _last_acked) { if (!_in_fast_recovery) { _last_acked = seqno; _dupacks = 0; inflate_window(); send_packets(now); _last_sent_time = now; return; } if (seqno < _recover) { uint32_t new_data = seqno - _last_acked; _last_acked = seqno; if (new_data < _cwnd) _cwnd -= new_data; else _cwnd=0; _cwnd += _mss; retransmit_packet(now); send_packets(now); return; } uint32_t flightsize = _highest_sent - seqno; _cwnd = min(_ssthresh, flightsize + _mss); _last_acked = seqno; _dupacks = 0; _in_fast_recovery = false; send_packets(now); return; } if (_in_fast_recovery) { _cwnd += _mss; send_packets(now); return;

} _dupacks++; if (_dupacks!=3) { send_packets(now); return; } _ssthresh = max(_cwnd/2, (uint32_t)(2 * _mss)); retransmit_packet(now); _cwnd = _ssthresh + 3 * _mss; _in_fast_recovery = true; _recover = _highest_sent; } How TCP shares capacity individual flow bandwidths available bandwidth sum of flow bandwidths time Motivation: buffer size Internet routers have buffers, to accomodate bursts in traffic. How big do the buffers need to be?

3 GByte? Rule of thumbwhat Cisco does today 300 MByte? [Appenzeller, Keslassy, McKeown, 2004 ] 30 kByte? Large buffers are unsustainable: Data volumes double every 10 months CPU speeds double every 18 months Memory access speeds double every 10 years Motivation: TCPs teleology [Kelly, Maulloo, Tan, 1998] U(x) P(y,C) Consider several TCP flows sharing a single link Let xr be the mean bandwidth of flow r [pkts/sec] Let y be the total bandwidth of all flows [pkts/sec] Let C be the total available capacity [pkts/sec] TCP and the network act so as to solve maximise r U(xr) - P(y,C) over xr0 where y=r xr x C y

U(x) Bad teleology severe penalty for allocating too little bandwidth little extra valued attached to highbandwidth flows x Bad teleology U(x) flows with large RTT are satisfied with little bandwidth flows with small RTT want more bandwidth x P(y,C) Bad teleology

no penalty unless links are overloaded C y TCPs teleology U(x) P(y,C) The network acts as if its trying to solve an optimization problem Is this what we want the Internet to optimize? Does it even succeed in performing the optimization? x C y Synchronization Desynchronized TCP flows:

Synchronized TCP flows: aggregate traffic rate individual flow rates aggregate traffic is smooth network solves the optimization + + = aggregate traffic is bursty network oscillates about the optimum + + = time Synchronization

Desynchronized TCP flows: Synchronized TCP flows: aggregate traffic rate individual flow rates aggregate traffic is smooth network solves the optimization + + = aggregate traffic is bursty network oscillates about the optimum + + = time

TCP traffic model When there are many TCP flows, the aggregate traffic rate xt varies smoothly, according to a differential equation [Misra, Gong, Towsley, 2000] aggregate traffic rate The equation involves pt, the packet loss probability at time t, RTT, the average round trip time desynchronized time synchronized traffic rate [0-100 kB/sec] TCP time [0-8 sec] if (seqno > _last_acked) { if (!_in_fast_recovery) { _last_acked = seqno; _dupacks = 0; inflate_window(); send_packets(now); _last_sent_time = now;

return; } if (seqno < _recover) { uint32_t new_data = seqno - _last_acked; _last_acked = seqno; if (new_data < _cwnd) _cwnd -= new_data; else _cwnd=0; _cwnd += _mss; retransmit_packet(now); send_packets(now); return; } uint32_t flightsize = _highest_sent - seqno; _cwnd = min(_ssthresh, flightsize + _mss); _last_acked = seqno; _dupacks = 0; _in_fast_recovery = false; send_packets(now); return; } if (_in_fast_recovery) { _cwnd += _mss; send_packets(now); return; } _dupacks++; if (_dupacks!=3) { send_packets(now); return; } _ssthresh = max(_cwnd/2, (uint32_t)(2 * _mss));

retransmit_packet(now); _cwnd = _ssthresh + 3 * _mss; _in_fast_recovery = true; _recover = _highest_sent; } Queue model How does packet loss probability pt depend on buffer size? There are two families of answers, depending on queueing delay: Small buffers (queueing delay RTT) Large buffers (queueing delay RTT) 2000 1 5 1 5 2 0 2 0 200

1 0 5 1 0 2 0 1 0 5 200 2 0 1 5 time 20 2 0 time [0-5 sec] 42 43

44 45 1 5 41 0 0 5 0 40 2000 delay queueing 0.19 ms 1 5 2 0 1 5 200 delay

queueing 1.9 ms 5 v a l1 1 0 1 5 queue size [0-15 pkt] 2 0 queueing 20 delay 19 ms 1 0 0

0 5 v a l1 1 0 5 0 2 0 1 5 1 0 5 0 5 1 0 As the optical fibres line rate increases queue size fluctuates more and more rapidly queue size distribution 20

does not change 40 41 42 43 44 45 time (it depends only on link utilization, not on line rate) 0 v a l1 Small buffers 40 41 42 43 time

44 45 Large buffers (queueing delay 200 ms) queue val1size 0 50 100 150 [0-160 pkt] queueapprox 40 42 44 46 time 50

time 48[0-10 sec] When xt

50 time 48[0-10 sec] When xtC the queue fills up and packets begin to get dropped Large buffers (queueing delay 200 ms) queue val1size 0 50 100 150 [0-160 pkt] queueapprox 40 42 44 46

time 50 time 48[0-10 sec] When xtC the queue fills up and packets begin to get dropped TCPs may overshoot, leading to synchronization Large buffers (queueing delay 200 ms) queue val1size 0 50 100 150 [0-160 pkt] queueapprox 40 42

44 46 time 50 time 48[0-10 sec] Drop probability depends on both traffic rate xt and queue size qt Analysis Write down differential equations for aggregate TCP traffic rate xt for queue dynamics and loss prob pt taking account of buffer size Calculate average link utilization average queue occupancy/delay extent of synchronization and consequent loss of utilization, and jitter [Gaurav Raina, PhD thesis, 2005] Stability/instability analysis traffic rate xt/C

1.4 1.2 0.8 0.6 20 40 60 80 100 20 40 60 80 100 1.4 1.2 0.8 0.6

For some values of C*RTT, the dynamical system is stable For others it is unstable and there are oscillations (i.e. the flows are partially synchronized) When it is unstable, we can calculate the amplitude of the oscillations time Instability plot traffic intensity x/C 0.5 -1 log10 of pkt loss probability p 1 extent of oscillations in x/C -2 -3 -4

queue equation 1.5 2 TCP throughput equation Instability plot traffic intensity x/C 0.5 1 1.5 2 -1 C*RTT=4 pkts log10 of pkt loss probability p -2 -3

C*RTT=20 pkts -4 C*RTT=100 pkts Alternative buffer-sizing rules 0.5 1 1.5 2 Intermediate buffers buffer = bandwidth*delay / sqrt(#flows) or Large buffers buffer = bandwidth*delay -1 -2 -3 -4 b25

b100 b400 -1 -2 Large buffers with AQM -3 buffer=bandwidth*delay*{,1,4} -4 0.5 b10 1 1.5 b20 -1 b50 -2 Small buffers

-3 buffer={10,20,50} pkts -4 0.5 b50 1 1.5 b1000 -1 -2 Small buffers, ScalableTCP p -3 buffer={50,1000} pkts [Vinnicombe 2002] [T.Kelly 2002] -4 -5 -6 0.5

1 1.5 Conclusion The network acts to solve an optimization problem. We can choose which optimization problem, by choosing the right buffer size & by changing TCPs code. It may or may not attain the solution In order to make sure the network is stable, we need to choose the buffer size & TCP code carefully. Prescription ScalableTCP in end-systems need to persuade Microsoft, Linus Much smaller buffers in routers need to persuade BT/AT&T ScalableTCP gives more weight to highbandwidth flows. And its been shown to be stable. U(x)

P(y,C) With small buffers, the network likes to run with slightly lower utilization, hence lower delay x C y

Recently Viewed Presentations

  • SILVERBACK 70 SERIES PASSING OFFENSIVE PLAYBOOK PASSING TREE

    SILVERBACK 70 SERIES PASSING OFFENSIVE PLAYBOOK PASSING TREE

    passing tree #0 hitch #1 speed out #2 slant #3 deep out #4 drag #5 comback #6 curl #8 post #7 corner #9 go #0 hitch: 5 or 7 steps break down at the top of the stem while faceing...
  • Pine View Middle School An IB MYP World

    Pine View Middle School An IB MYP World

    MYP Language and Literature courses are designed to offer a study of a wide range of literary and non-literary text types, writing styles and techniques, allowing students to comment on the significance of any possible contexts, audiences, purpose, and the...
  • Average Velocity

    Average Velocity

    Average Velocity ν = Δx /Δt Unit: m/s Average Acceleration a = Δv / Δt Unit: m/s2 Big Five (Δx=) Δx = vit + ½ at2 Unit: m Big Five (x=) x = xi + vt Unit: m Big Five...
  • Pet and Animal Emergency Planning Planning for animal

    Pet and Animal Emergency Planning Planning for animal

    Develop a buddy system with neighbors, friends and relatives to make sure that someone is available to care for or evacuate your pets if you are unable to do so. Be prepared to improvise and use what you have on...
  • Literacy Lessons - EduGAINs

    Literacy Lessons - EduGAINs

    Every effort must be made to engage students in the college community and to encourage them to access the supports and practise the learning skills they needs. * Lesson 1.1, which focuses on the Seneca College web site, focuses on...
  • Read &amp; Write Gold 11

    Read & Write Gold 11

    Read & Write Gold 11 is a program designed to help individuals struggling with reading and writing, those with learning disabilities such as Dyslexia, or English Language Learners. Today, our goal is to learn some of the basic tools to...
  • Theories of International Trade and Investment International Business:

    Theories of International Trade and Investment International Business:

    Firms sustain innovation (and by extension, competitive advantage) by continually finding better products, services, and ways of doing things. For example, Australia's Vix ERG (www.vix-erg.com) is a world leader in fare collection equipment and software systems for the transit industry.
  • Algebra 2 Common Core Miss Mazzeo - WordPress.com

    Algebra 2 Common Core Miss Mazzeo - WordPress.com

    Algebra 2 Common CoreMiss Mazzeo and Ms. Prizio. Welcome! Please find a seat. ... Complete the Google Form sent to you Skedula also available on my website . mazzeomath.wordpress.com. HW due Tuesday 9/13/16. Have a parent sign the contract. Get...