Question? Leave a message!




Network Layer Performance Modeling & Analysis

Network Layer Performance Modeling & Analysis 19
Computer Communication Networks (CCN) Network Layer Performance Modeling Analysis 1Overview • Network Layer Performance Modeling Analysis – Part I: Essentials of Probability – Part II: Inside a Router – Part III: Network Analysis Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 2Network Layer Performance Modeling Analysis: Part II Inside a Router • Basic Single Queue Model • Poisson Arrival Model • The M/M/1 Queue • Read any of the queuing theory references, e.g. Schwartz (Sections 2.13), Molloy, Kleinrock. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 3Queuing in the Network Layer at a Router Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 4Basic Single Queue Model • Classical queuing theory can be applied to an output link in a router. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 5Basic Single Queue Model • For example, a 56 kbps transmission line can “serve” 1000bit packets at a rate of 56,000 bits/sec  56 packets/sec 1000 bits/packet Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 6Applications of Queuing Analysis Outside of Networking • Checkout line in a supermarket • Waiting for a teller in a bank • Batch jobs waiting to be processed by the CPU Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 7Applications of Queuing Analysis Outside of Networking • “That’s the way the whole thing started, Silly but it’s true, Thinking of a sweet romance Beginning in a queue.” G. Gouldman, “Bus Stop” The Hollies Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 8The Poisson Arrival Model • A Poisson process is a sequence of events “randomly spaced in time” Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 9The Poisson Arrival Model • Examples – Customers arriving to a bank – Packets arriving to a buffer • The rate λ of a Poisson process is the average number of events per unit time (over a long time). Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 10Properties of a Poisson Process • For a length of time t the probability of n arrivals in t units  4 of time is n ()t t P() t e n n Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 11Properties of a Poisson Process • For 2 disjoint (nonoverlapping) intervals, (s , s ) and (s , s ), (i.e. 1 2 3 4 s s s s ), the number of  1 2 3 4 arrivals in (s , s ) is independent 1 2 of the number of arrivals in (s , 3 s ) 4 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 12Interarrival Times of a Poisson Process • Pick an arbitrary starting point in time (call it 0).  • Let = the time until the next 1 arrival t P( t) P (t) e 10 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 13Interarrival Times of a Poisson Process • So  tt F (t) P( t)1e and f (t) e  1 11  ,the time until the first arrival, 1 Has an exponential distribution Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 14Interarrival Times of a Poisson Process  • Let = the length of time 2 between the first and second arrival. • We can show that t P( t  s) P( t) e for any s,t 0 2 1 2  i.e. is exponential and 2  independent of 1 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 15Interarrival Times of a Poisson Process 3  • Similarly define as the time between the second and third  arrival; as the time between 4 the third and fourth arrival;… 3    • The random variables , , , 2 1 … are called the interarrival times of the Poisson process Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 16Interarrival Times of a Poisson Process • The interarrival time random   variables, , , … 1 2 3 – Are (pairwise) independent. – Each has an exponential distribution with mean 1/λ. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 17The M/M/1 Queue • An M/M/1 queue has – Poisson arrivals (with rate λ) – Exponential service times (with mean 1/μ, so μ is the “service rate”). – One (1) server – An infinite length buffer • The M/M/1 queue is the most basic and important queuing model. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 18Queuing Notation “M/M/1” is a special case of more general (Kendall) notation: X/Y/m/k, where • X is a symbol representing the interarrival process – M = Poisson (exponential interarrival times, )   – D = Deterministic (constant ). Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 19Queuing Notation • Y is a symbol representing the service distribution M = exponential, D = deterministic  G = General (or arbitrary). • m = number of servers • k = number of buffer slots (omitted when k = )  Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 20Aside: The D/D/1 Queue • The D/D/1 queue has – Deterministic arrivals (periodic with period = 1/λ). – Deterministic service times (each service takes exactly 1/μ). – As well as 1 server and an infinite length buffer. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 21Aside: The D/D/1 Queue • If λ μ then there is no waiting in a D/D/1 queue. Randomness is a major cause of delay in a network node Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 22State Analysis of an M/M/1 Queue • Let n be the state of the system = the number of packets in the system (including the server). • Let p be the steady state n probability of finding n customers waiting in the system (including the server). Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 23State Analysis of an M/M/1 Queue • How to find p The state n diagram: Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 24State Analysis of an M/M/1 Queue • If the system is stable (i.e. p 0  n for each n), then in a steady state it will drift back and forth across the dotted line. So, • the number of transitions from left to right = the number of transitions from right to left. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 25State Analysis of an M/M/1 Queue • Thus we obtain the balance equations p p for each n 0 nn1 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 26State Analysis of an M/M/1 Queue • Lets solve the balance pp equations: nn1 • For n = 0 we get  / • If we let , this becomes pp 10 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 27State Analysis of an M/M/1 Queue • Similarly 2 p  p p 2 1 0 • And if general p n Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 28State Analysis of an M/M/1 Queue n • We have for n =1,2,3,... p p p n 0 • We need to solve for p , so we 0 need one more equation. Use   p 1 n n0 • We obtain  1  p for 1 0  nn 1 pp 1 00  nn  00  for  1 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 29State Analysis of an M/M/1 Queue p  1 • So we must have 0 and n pn (1 ) for 1,2,3,... n Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 30State Analysis of an M/M/1 Queue • Note that requiring ρ 1 for stability (i.e. λ ) makes intuitive  sense. • Also ρ=1ρ 0 = probability that the queuing system is NOT empty = probability the server is working Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 31State Analysis of an M/M/1 Queue So ρ is sometimes called the “server utilization” n • Finally note that p = (1 ρ)p , n = n 0,1,2,3,… is a geometric distribution Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 32The Finite Buffer Case: M/M/1/N • Infinite buffer assumption is unrealistic in practice. • N = total number of buffer slots (including server). • New state diagram: Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 33The Finite Buffer Case: M/M/1/N • Get the same balance equations, pp but now only for n = nn1  0,1,2,…,N 1 with N . So n p p p for n 0,1,2,...,N nn10 as before, but we get a different p . 0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 34The Finite Buffer Case: M/M/1/N n pp • From for n = 0,1,2,…, N n 0 N  p and = 1 we get  n n0 N n pp  1 00 n1 • So 1 1 1 p ... 0 NN N1 n  (1 ) 1 1  n1 1 (1) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 35The Finite Buffer Case: M/M/1/N  0 • Note that this holds for any . No need to assume ρ 1. We always have the stability in the finite buffer case. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 36Blocking Probability and the Right Size Buffer • So in the finite buffer case, n (1 ) p for n 0,1,2,...,N n N1 1 • Note that P is the probability N that the buffer is full at an arbitrary point in time. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 37Blocking Probability and the Right Size Buffer • Since arrivals are independent of buffer state, we have P = P = N B probability an arriving packet is turned away due to a full buffer. • P is called blocking probability. B Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 38Blocking Probability and Buffer Size • P is very important B • We can use P to choose the B correct buffer size. 6 • Example: For ρ= 0.5, p 10 for N 6  N 18, while p 10 for N 19. N Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 39Blocking Probability and Buffer Size • Thus, if we desire a blocking 6 probability less than 10 , we need a buffer capable of holding 19 or more packets. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 40Throughput in the Finite Buffer Case  • The throughput of any queuing system is the rate at which customers successfully leave the system. • For the M/M/1 infinite buffer case, if the system is stable.  (Everything that arrives must eventually depart.) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 41Throughput in the Finite Buffer Case • For the M/M/1/N finite buffer  (1 P ) case, B (Everything that arrives and is not blocked must eventually depart.) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 42Throughput in the Finite Buffer Case Alternate way to compute throughput of M/M/1/N: Look at the output side. 1p • P (server is busy) = 0  • When the server is busy, the output rate = • when the sever is idle, the output rate = 0  (1pp ) 0 • So the average rate = 00 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 43Aside: Derivation of P = P N B Using Throughput • Equating our two formulas for  we get  (1pP ) (1 ) 0 B • Solving for P we get B N 1p (1 ) 0 Pp1 ... BN N1  1 • Isn’t that neat Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 44Approximation of a Finite Buffer System by the Infinite Buffer Model n p  (1  ) • For a infinite buffer, n nN1 p (1) /(1 ) • For a finite buffer, n • For ρ = 0.8 and N = 16 packets, these probabilities differ by less than 2.3 • For ρ = 0.8 and N = 32, the difference is only 0.06 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 45Approximation of a Finite Buffer System by the Infinite Buffer Model The infinite buffer model is a very good approximation of a finite buffer system. Even for moderate buffer sizes Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 46How Long is that Line • Lets look again at the M/M/1 queuing system. • n = the number in the system (including the server) • So the average number in the system is   n E(n) np (1 ) np (1 )  n 2 (1  ) 1 nn  00 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 47Little’s Formula and Queuing Delay • Let T = time spent by a customer in a queuing system (waiting and being served). • E(T) = the average delay for a customer. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 48Little’s Formula and Queuing Delay • Little’s Formula says E(T)E(n) • where λ is the “arrival rate for customers eventually served” (which  we called ) Little’s Formula holds for very general queuing systems (not just M/M/1). Even whole networks Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 49Little’s Formula and Queuing Delay • Little’s Formula is either deep of obvious. Intuition: • Pick a “typical customer” • When it arrives to the queuing system, it should find E(n) customers waiting. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 50Little’s Formula and Queuing Delay • When it leaves the system, it has been in the system for E(T). Thus λE(T) customers should have arrived during its time in the system. • In steady state, the average number of customers left behind on the departure should equal the average number found on the arrival, i.e. λE(T) = E(n) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 51Little’s Formula and Queuing Delay • Let’s apply Little to the M/M/1 queue En ( ) 1 ET() (1) • E(T) is measured in units of time. Sometimes it is more convenient to consider  En ( ) 1 ET() (1) 1 which is unitless Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 52Little’s Formula and Queuing Delay • Sometimes we consider the waiting time W, i.e. the time spent waiting in the queue (not in service). So, 1 E(W ) E(T)  Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 53Single Link Example • Poisson packet arrivals with rate λ = 2000 p/s • Fixed link capacity C = 1.544 Mb / s (T1 Carrier rate). Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 54Single Link Example • We approximate the packet length distribution by an exponential with mean L = 515 b/p • Thus the service time is exponential with mean 1 L 515 b /p  0.33ms /p  C 1.544 Mb /s i.e. packets are served at a rate of  3000 ps / Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 55Single Link Example • Using our formulas for an M/M/1 queue   0.67  So  En ( ) 2.0 packets 1 and En () ET ( )1.0 ms  Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 56Other Queuing Models • There are many other important queuing models which are useful in networking. • M/M/k for k1. Multiple servers – Good model of a link which is made up of multiple channels, either physically of through multiplexing (e.g. a T1 carrier is typically time division multiplexed with k = 24). – Has worse performance at lower loads than M/M/1 with same total capacity. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 57Other Queuing Models • M/M/k/k for k 1. One or more  servers, no buffers (except one in each server). – Important model in circuit switched networks. – Models a trunk line with k circuits available. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 58Other Queuing Models – Any customer (a call) which doesn’t get a circuit is blocked (gets a busy signal). – Blocking probability is given by the Erlang B (or Erlang Loss) Formula k  / k P  0 B k i  / i  i0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 59Other Queuing Models • M/G/1. Arbitrary service (packet length) distribution. – Can still compute the mean number in the system via the PollaczekKhinchine (PK) Formula    22 En ( ) 1 (1 ) 1   12   Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 60Other Queuing Models    22 En ( ) 1 (1 ) 1   12   2  where is the variance of the service time distribution. Again, variablility (randomness) causes delay. • Can apply Little’s Formula to get the mean delay Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 61Other Queuing Models • M/D/1. Deterministic service times (packet length). 2 – Special case of M/G/1 with  0    En ( ) 1 1  12   1 – Under heavy load ( ), M/D/1 has half the delay of an M/M/1 – This is one motivation for a fixed packetlength system like ATM Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 62Other Queuing Models • Can also model and analyze other queuing systems – With priority – With more general arrival process – With “vacations” – Many others Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 63Other Queuing Models • See Schwartz (Ch. 2), Kleinrock (Vol. I II) or take ECSE 6820/DSES6820, Queuing (sic) Systems Applications • Queuing theory is also used in analysis of Operating Systems, e.g. in CSCI6140 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 64