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

  • Ecology - Mr. Sault&#x27;s Classroom

    Ecology - Mr. Sault's Classroom

    One way to define ecology is "the study of the interaction . of living things with each other, and with the non-living parts of . their environment." Ecology. The word "ecology" comes from the Greek words oikos meaning "the place...
  • U.S. General Services Administration Planning for SmartPay Transition

    U.S. General Services Administration Planning for SmartPay Transition

    Ensure APC appointment letters and training are current and maintained at the Component. Ensure cardholder training and Statements of Understanding (SOUs) are current. Cardholder 101 Training required with initial application and refresher training every 3 years. APC Mandatory Training required...
  • Craig A. Anderson, Ph.D. Professor of Psychology &amp; Chair ...

    Craig A. Anderson, Ph.D. Professor of Psychology & Chair ...

    7±2 Deadly Sins in Media Violence Research. Craig A. Anderson, Distinguished Professor. Digital Media & Developing Minds Congress. Cold Spring Harbor Laboratory, Oct. 15-18, 2018
  • Chapter 22 -The Ordeal of Reconstruction

    Chapter 22 -The Ordeal of Reconstruction

    The black regiments could only serve west of the Mississippi River because of the prevailing attitudes following the Civil War. The name "Buffalo Soldiers" has become interesting lore in itself. There seem to be three possible reasons for the name....
  • IP Due Diligence

    IP Due Diligence

    Solve this issue by proper claim drafting one claim on one single economic entity in the claim Case Law Germany Exhaustion No written Rule in the Patent Act but an established principle under case law and binding as customary law...
  • Starfish: A Self-tuning System for Big Data Analytics

    Starfish: A Self-tuning System for Big Data Analytics

    Part of the Starfish system . This talk: tuning individual MapReducejobs. Challenges. Heavy use of programming languages for MapReduce programs and UDFs (e.g., Java/Python) Data loaded/accessed as opaque files. Large space of tuning choices. 8/31/2011. Duke University
  • What are we remembering on Remembrance Day? - Sheffield

    What are we remembering on Remembrance Day? - Sheffield

    Why did people come to Sheffield in the 1950s and 1960s? Sheffield was a major industrial city until the 1980s so the earlier arrivals came here to find work, particularly in the steel industry. Large-scale immigration started in Sheffield later...
  • Sub-brand to go here Doing gender through imagined

    Sub-brand to go here Doing gender through imagined

    155 words Working-class boy's essay misclassified as a girl's essay * I am married and I have no children. At the moment I am working in a pet shop. with all the animals arond me I am very fond of...