Packet-Mode Emulation of Output-Queued Switches

Faculty of Electrical Engineering The Gaussian Nature of TCP Mark Shifrin Supervisor: Dr. Isaac Keslassy M.Sc Seminar Large Network Presentation Characterizing traffic is essential to understanding the behavior of large Internet networks. Network is large and complex contains millions of flows. The interaction and mutual impact is difficult to understand. 2

Large Network Related Challenges What do we pursue? Ability to analyze problems: Congestions High packet losses Ability to make planning decisions: Bottleneck capacity decision Buffer

size RTT (Round Trip Time) distribution 3 Obstacles and Difficulties Today: no existing efficient large network model because of numerous problems. Problems: Many TCP feedback behaviors (congestion avoidance, slow-start, ) Complex interactions among flows Complex queueing analysis Many topologies

Many protocols (TCP, UDP, ) Complex interactions between flows and ACKs 4 Reducing the Network into Basic Components Bottlenecks dictate the behavior of the flows. Assumption: The network can be subdivided into basic dumbbell topologies with a single forward bottleneck. 5 Previous work rule-of-thumb Router

Source C Destination RTT Universally applied rule-of-thumb for TCP flows: A router needs a buffer size: B RTT C

RTT is the two-way propagation delay C is capacity of bottleneck link Context Mandated in backbone and edge routers. Appears in RFPs and IETF architectural guidelines. Usually referenced in [Villamizar and Song, 94] Already known by inventors of TCP [Van Jacobson, 88] Has major consequences for router design 6

Previous Work Stanford Model [Appenzeller et al., 04 | McKeown and Wischik, 05 | McKeown et al., 06] Assumption 1: TCP Flows modeled as i.i.d. total window W has Gaussian distribution Assumption 2: Queue is the only variable part queue has Gaussian distribution: Q=W-CONST use smaller buffer than in rule of thumb We also consider small buffers. But, with small buffers: Buffers lose Gaussian property Link variations cannot be neglected 7

Previous Work Total Arrival is Poisson Distributed Assumption: M/M/1/K model of buffer with TCP ]Avrachenkov et al., 01] Using the model of [Padhye et al., 98] for the M/M/1/K analysis. We show that the Poisson model is far from reality. 8 What is new in our analysis? Dividing the Dumbbell Topology into components (Lines). Finding

separately the pdf of the traffic of each component we can describe the statistics of the entire network. We show the impact of one component on another. We find a new model of TCP congestion window (cwnd) distribution, considering correlated losses. We use it to find the pdf of the traffic on the Lines. We prove that distributions of the packets on the Lines are Gaussian.

We find Transmission rate, Queue (Q) distribution and the packet loss. 9 Contents of the Dumbbell Topology Line L2 Line L5 Line L3 Line L4 Line L1 Q Line L6 10

Contents of the Dumbbell Topology Line L5 Line L2 Line L3 Line L4 Line L1 Q Line L6 11 Outline

Models of single objects Transmission rate and packet loss derivation Arrival rate of single flow

Total arrival rate Q distribution Packet loss Gaussian models of Lines Finding the model of cwnd . Correlated losses Packet Loss Event derivation Model of li1 L1 model , Lindeberg Central Limit Theorem Models of other lines and of W.

Conclusions 12 Model Development Flow li1 pdf total arrival rate cwnd Q pdf l arrival rates packet loss i 1

13 TCP Newreno Congestion Control (Reminder) Slow Start w w*2 Congestion Avoidance: w w+1 Fast Retransmit and Fast Recovery: w w/2 Treats multiple losses in the same window Timeout (TO): w 1

14 CWND Simple Markov Chain Solution Simple Markov Chain. Assumption: Timeout (TO) probability is small comparatively to the halving. Model 1: Independent losses [Altman et al., 04] 15

Model 2: Packet loss event derivation w=n/2 w=n pe(n)*n p: packet loss probability. Original transition was given by p*n. We cannot use p because the losses are correlated. probability of the Loss Event for window size n is equal to pe(n)n Assumption: In window of size n with losses , each packet in the

same window has equal probability to experience the packet loss event. Intuition: pe is the effective packet loss, which is independent for every packet. Fast Retransmit and Fast Recovery able to recover almost in the same way no matter how many packets are lost in the window. 16 Correlated Losses Packet losses are strongly correlated: given one packet was lost in a TCP window, the

probability is higher for others in the same window to be lost. Assumption: For a given window size n, given at least one lost packet, the distribution of the number of lost packets is independent of the network condition! (No actual impact of p, RTT distribution, Buffer size) Denote this distribution as Pr(l(n)=k), for k=1n 17 Packet Loss Burst Size Distribution 18 Packet Loss Burst Size Distribution 19

Expected packet loss burst size Pr(l(n)=l) = Pr(l lost packets for w=n|loss event happened) E[l(n)]- expected value of the size of the bursty loss, given at least one packet was lost, for window size n. At every loss event in window of size n, E[l(n)] packets fall in average. Every loss event is effectively treated as a single loss (approximation)

pe effective packet loss probability. 21 What is this pe actually? Theorem: pe(n)/p =1/ E[l(n)], i.e. independent of p for a given n. Proof outline: For arbitrary lost packet B denote AB as P(some packets lost in window containing B) p=P(B|AB)*p(AB)+ P(B|ABC)*p(ABC) P(B|AB)=E[l(n)]/n

0 p(AB)=pe(n)*n Conclusion: pe(n)=p/ E[l(n)] Intuition: E[l(n)] losses treated as a single loss! 22 pe/p - simulation results 500 flows traced by NS2 tools, event by event. 23

MC Transitions (Approach 1 & 2) Approach 1: Pr(w(t+1)=w(t)/2 | w(t)=n)=n*pe(n) Pr(TO)=const (known) Pr(w(t+1)=w(t)+1 | w(t)=n)=1-Pr(TO)Pr(w(t+1)=w(t)/2 | w=n). Approach 2: Pr(w(t+1)=w(t)/2

| w(t)=n)=Ph1+Ph2 Then Ph1 is the probability of loss in the first half of the window and Ph2 is the probability of loss in the second half of the window. Improvement: introduce Slow Start in the model 24 Results ( pdf,low p) 26 Results (cdf, low p)

27 Results (pdf, medium p) 28 Results (cdf, medium p) 29 Results (pdf, high p) 30 Results (cdf, high p) 31

Model of li1 li1 pdf cwnd packet loss 32 li1 distribution uniform vs. bursty source l1 i li2 B

li5 l i 3 li4 dest. li6 rtti=tp1i+tp2i+tp3i+tp4i+tp5i+tp6i Approach 1: Uniform packet distribution. l1(t)i = wi(t)*

tpi1/rtti. Approach 2: Bursty Packet Distribution 33 Bursty Transmission and li1 model Assumption: All packets in a flow move in a single burst Transmission and queueing times of the entire burst negligible comparatively to propagation latencies Conclusion 1: All packets belonging to an arbitrary flow i are present almost always on

the same link (l1i,l2i,l3i,l4i,l5i,l6i). Conclusion 2: The probability of burst of flow i being present on the certain link is equal to the ratio of its propagation latency to the total rtti. 34 li1 probability density function We compare the measured results vs. the models 1 and 2 Reminder of the model 1: l1(t)i = wi(t)* tpi1/rtti. 35

Model results li1 , logarithmic scale 36 Outline Models of single objects Transmission rate and packet loss derivation

Arrival rate of single flow Total arrival rate Q distribution Packet loss Gaussian Models of Lines Finding the model of cwnd . Correlated losses

Packet Loss Event derivation Model of li1 L1 model , Lindeberg Central Limit Theorem Models of other lines and of W. Conclusions 38 Model Development Flow li1 pdf cwnd total arrival rate l1i arrival rates 39

Rate Transmission Derivation The objective is to find the pdf of the number of packets sent on some link i, ri, in a time unit t. Assumptions: The rate on each one of the links in L1 is statistically independent We assume that the transmissions are bursty. We assume that the rate is proportional to the distribution of l1i and to the ratio t/tp1i.

tp1i is the latency on the corresponding link. 40 Arrival rate of a single flow source B l2 i li1 li1 *t/tp1i t

tp1i t is the same for all flows. We find the arrival distribution for every flow in t msec. 41 Rate PDF on the single line The distribution is the same, but with different parameters. For finding the total rate Lindeberg Central Limit Theorem is needed. 42

Total Rate Theorem: The proof is using the Lindeberg condition. The idea: Central Limit Theorem holds if the share of each flow comparatively to the sum is negligible as the number of the flows grows. Argument for the proof: cwnd is limited by maximum value so does the l1i and ri. Another alternative: Using a Poisson arrival rate - too small variance (result of the bursty transmission not reflected)

43 Rate Model - Results Probability Total arrival rate number of packets per t 45 Model Development Flow li1 pdf total arrival rate cwnd Q pdf l arrival rates

packet loss i 1 46 Q pdf Two possible ways to find the Q distribution: Running MC simulation using samples of R G/D/1/K analysis using R for arrivals [TranGia and Ahmadi, 88]

Both ways yield almost the same results. Packet loss p is derived from the Q distribution. 47 Q pdf - results Probability Q state 0 to 585 packets 48 Fixed Point Solution: p=f(p) li1 pdf total arrival rate cwnd

Q pdf l arrival rates packet loss i 1 49 Packet Loss Rate Solution by gradient algorithm 1. 2.

3. 4. 5. 6. 7. Start with approximate p Find the cwnd and all l1i Find all rates of all flows Find the total rate and Q pdf Find new p Make a correction according to the error weighted by step size and go to 2. Till the error small enough fixed point found 50 Packet loss - results

Model gives about 10%-25% of discrepancy. Case 1: Measured: p=2.7%, Model: p=3% Case 2: Measured: p=0.8%, Model: p=0.98% Case 3: Measured: p=1.4%, Model: p=1.82% Case 4: Measured: p=0.452%, Model: p=0.56% 51 Outline

Models of single objects Transmission rate and packet loss derivation

Arrival rate of single flow Total arrival rate Q distribution Packet loss Gaussian Models of Lines Finding the model of cwnd . Correlated losses Packet Loss Event derivation Model of li1 L1 model , Lindeberg Central Limit Theorem Models of other lines and of W.

Conclusions 52 L1 (reminder) Line L5 Line L3 Line L1 Q 53 Lindeberg Central Limit Theorem All li1 are statistically independent.

The distribution is the same but with different parameters because of different RTT simple Central Limit Theorem wont fit. Theorem: Conclusion : Using the model for cwnd and then for li1 we are able to find the L1 distribution. 54 L1 Model Results

56 What else can we know from our model? Line L2 Line L5 Line L3 Line L4 Line L1 Q Line L6 Stanford Model: Gaussian Queue, Gaussian W, constant traffic on the links Our model: non-Gaussian Queue, Gaussian W, Gaussian traffic on the

links. 57 Packets on other lines client cwnd l1 i li2 B bcwnd li5

l i 3 li4 li6 server bcwnd 58 Model Development Flow cwnd

W Total bcwnd li2 L2 li4 L4 li5 L5

li6 L6 59 cwnd on the Lines We know the pdf for the cwnd the window at the source. This window travels the lines as the single burst The burst which passes through the Q loses some packets.

How can we know the distribution of the window of packets after it passes the Q? Suggestion: Using l(n) distribution for window of size n. Reminder: Pr(l(n)=l) = Pr(l lost packets for w=n|loss event happened) 60 Packet Loss Burst Size Distribution (Reminder) 61 Markov Chain of bcwnd 1-Ploss Ploss*P(l(n)=1)

w=1 w=2 w=3 w=n-1 w=n Ploss*P(l(n)=n-3) Ploss*P(l(n)=n-2) Ploss*P(l(n)=n-1) 62

Back cwnd algorithm (bcwnd) The fall probability for window of size n: Ploss= pe(n)*n. (TO is small and omitted) For each n from 1 to 64 update: Pr(bcwnd=n)=P(cwnd=n)-P(cwnd=n)* For Ploss each I, i=0 to n-1 update: P(bcwnd=i)=P(cwnd=i)+ P(cwnd=n)* Ploss*P(l(n)=n-i)

The update done from low to the highest state. 63 bcwnd and cwnd comparison 64 Models for L2, L4,L5,L6 Typical case: tp1i, tp2i, tp4i, tp5i, tp6i, all have a different distribution Approach 1: Use model of L1 with cwnd and

scale by ratio of means of tp. ratio of tp gives unreliable result for both the expected value and variance Approach 2: Use bcwnd for the model for l2i, l4i, l5i, l6i. The model is exactly the same as for l1i, but bcwnd instead of cwnd used. Corresponding latencies for each line used. Use The Lindeberg Central Limit Theorem, exactly in the same way as for L1! 65

L2 Model result demonstration 66 Topology Reminder of the Lines Line L2 Line L5 Line L3 Line L4 Line L1 Q Line L6 67

The Gaussian distributions L4 L2 L1 L6 L5 W NS2 simulation of 500 flows with all different time propagations 68 Are these lines really Gaussian? 69

W sum of all cwnd Two approaches to find W. cwnd model is known. All TCP connections are i.i.d classical Central Limit Theorem is applicable. Counting by summing all the components: W=L1+L2+L3+L4+L5+L6+Q. L3 and Q are non Gaussian components. cwnd i of different flows have some small correlation. L1,L2,L4,L5,L6 - all Gaussian. L1 almost the perfect Gaussian.

70 What Size of Buffer do We Need? Case 1 Buffer 154 772 3862 Formula p (%) Avg cwnd C*RTT/sqrt(N)/17.5 0.8 21 C*RTT/sqrt(N)/3.5 0.664 24.5

C*RTT/sqrt(N)/0.7 0.45 28.5 Case 2 Buffer 154 450 1802 Formula C*RTT/sqrt(N)/8 C*RTT/sqrt(N)/2 C*RTT/sqrt(N)/0.5 p (%) Avg cwnd 3.26 8

2.98 8.8 2.01 11.5 71 Outline Models of single objects Transmission rate and packet loss derivation

Arrival rate of single flow Total arrival rate Q distribution Packet loss Gaussian Models of Lines

Finding the model of cwnd . Correlated losses Packet Loss Event derivation Model of li1 L1 model , Lindeberg Central Limit Theorem Models of other lines and of W. Conclusions 72 Conclusions.. We know the probabilistic models of different components of the network Single

flows General components We can plan routers or networks now by deciding the C and the B, given some topology and packet loss limit. 73 Thanks are going to: Dr. I. Keslassy for guidance and inspiration Lab Staff for relentless support: Hai Vortman, Yoram Yihyie, Yoram Or-Chen,

Alex Students for some simulations. Listeners in this class for the patience.. 74

Recently Viewed Presentations

  • Experimental Design - Buckeye Valley

    Experimental Design - Buckeye Valley

    Use a baggie or pan to create the cold and warm water bath, then place the beaker containing the fish into the water bath. Do not put ice cubes/cold water/hot water directly in with the fish. Place thermometer into the...
  • So far in this course, you have been

    So far in this course, you have been

    Suppose Lenny and George started with two rabbits and that in each month following those rabbits have two babies. Also suppose that every month thereafter, each pair of rabbits has two babies. Your Task: With your team, determine how many...
  • Student Web Application Tutorial

    Student Web Application Tutorial

    Application Structure. Student.java. Models the data structure of Database. Constructs Data Object. Provides Set and Get method for the data // Line 19 -26 define the data members according to the database
  • Film - Ckv Broklede

    Film - Ckv Broklede

    History of film(art) in keywords A. Narrative (Fairy) tale, romantic, drama, melodrama, historic, western, action, science fiction Plot, motivation, parallels, development, order, couse and effect Dramaturgy (building of tension), themes and motives Similar to drama and literature B. Non narrative...
  • Introduction to Ethical Philosophy, Bioethics, Ethical ...

    Introduction to Ethical Philosophy, Bioethics, Ethical ...

    Define the terms ethics and morals and philosophical uses of these terms. Discuss systems of moral reasoning as they have been used throughout history. Use a variety of ethical approaches and theories in personal and professional relationships. Define the term...
  • Unit 8. Day 2. 2 types of scale

    Unit 8. Day 2. 2 types of scale

    2 types of scale factor problems. Scale Factor 2:3. Scale Factor ? Was a scale factor used? If so, what is it?
  • Drawing Bar above holds all your customizing tools

    Drawing Bar above holds all your customizing tools

    Sample Country Map — Taiwan Maps come ready to edit To customize 1. Select a country by clicking on it with your pointer 2. Use the paint bucket to fill states with new colors 3. Change Lines, add text, boxes,...
  • Introduction to Cryptographic Currencies Claudio Orlandi cs.au.dk/~orlandi Thanks

    Introduction to Cryptographic Currencies Claudio Orlandi cs.au.dk/~orlandi Thanks

    Programmablemoney? "Bitcoinuses a scripting system for transactions.Forth-like, Script is simple, stack-based, and processed from left to right. It is purposefully not Turing-complete, with no loops."