Question? Leave a message!




Network Layer Performance Modeling & Analysis

Network Layer Performance Modeling & Analysis 18
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 I Essential of Probability • Motivation • Basic Definitions • Modeling Experiments with Uncertainty • Random Variables: Geometric, Poisson, Exponential Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 3Network Layer Performance Modeling Analysis: Part I Essential of Probability • Read any of the probability references, e.g. Ross, Molloy, Papoulis, Stark and Wood • Check out the WWW version of the notes: http://networks.ecse.rpi.edu/vas tola/pslinks/perf/node1.html Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 4Motivation for learning Probability in CCN Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 5Basic Definitions • Think of Probability as modeling an experiment • The Set of all possible outcomes is the sample space: S • Classic “Experiment”: Tossing a die: S = 1,2,3,4,5,6 • Any subset A of S is an event: A = the outcome is even = 2,4,6 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 6Basic Operation of Events • For any two events A, B the following are also events: A A complement = all possible outcomes not in A AB  A union B = all outcomes in A or B or both AB  A intersect B = all outcomes in A and B • Note , the empty set. S   • If AB , then A and B are mutually exclusive. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 7Basic Operation of Events • Can take many unions: A A... A 12 n • Or even infinite unions:  A A... A 12 n n1 • Ditto for intersections Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 8Probability of Events •P is the Probability Mass function if it maps each event A, into a real number P(A), and: i.) P(A) 0 for every event A S ii.) P(S) = 1 iii.)If A and B are mutually exclusive events then, P(AB) P(A) P(B) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 9Probability of Events …In fact for any sequence of pair wisemutuallyexclusive events A ,A ,A ,... (i.e. A A 0 for any i j) we 1 2 3 ij have   P A P() A nn nn  11  Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 10Other Properties • P(A) 1 P(A) • PA ( ) 1 P(AB) P(A) P(B) P(AB) • • A B P(A) P(B) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 11Conditional Probability P(A B) • = (conditional) probability that the outcome is in A given that we know the outcome in B P() AB P(A B) P(B) 0 PB () •Example: Toss one die. Pi ( 3 i is odd)= •Note that: P(AB) P(B)P(A B) P(A)P(B A) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 12Independence • Events A and B are independent if P(AB) = P(A)P(B). • Example: A card is selected at random from an ordinary deck of cards. A=event that the card is an ace. B=event that the card is a diamond. P() AB PA () PB () P(A)P(B) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 13Independence • Event A and B are independent if P(AB) = P(A) P(B). • Independence does NOT mean that A and B have “nothing to do with each other” or that A and B “having nothing in common”. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 14Independence • Best intuition on independence is: A and B are independent if and only if (equivalently, ) P(B A) P(B) P(A B) P(A) i.e. if and only if knowing that B is true doesn’t change the probability that A is true. •Note: If A and B are independent and mutually exclusive, then P(A)=0 or P(B) = 0. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 15Random Variables • A random variable X maps each outcome s in the sample space S to a real number X(s). • Example: A fair coin is tossed 3 times. S=(TTT),(TTH),(THT),(HTT),(HHT),(HTH),(TH H),(HHH) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 16Random Variables • Let X be the number of heads tossed in 3 tries. X(TTT)= X(HHT)= X(TTH)= X(HTH)= X(THT)= X(THH)= X(HTT)= X(HHH)= • So P(X=0)= P(X=1)= P(X=2)= P(X=3)= Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 17Random Variable as a Measurement • Think of much more complicated experiments – A chemical reaction. – A laser emitting photons. – A packet arriving at a router. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 18Random Variable as a Measurement • We cannot give an exact description of a sample space in these cases, but we can still describe specific measurements on them – The temperature change produced. – The number of photons emitted in one millisecond. – The time of arrival of the packet. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 19Random Variable as a Measurement • Thus a random variable can be thought of as a measurement on an experiment Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 20Probability Mass Function for a Random Variable • The probability mass function (PMF) for a (discrete valued) random variable X is: P (x) P(X x) P(sS X(s) x) X Px ( ) 0 • Note that for  x X • Also for a (discrete valued) random variable X  Px ( ) 1  X x Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 21Cumulative Distribution Function • The cumulative distribution function (CDF) for a random variable X is F (x)P(Xx)P(sS X(s)x) X • Note thatFx() is nondecreasing in x, i.e. X x xF (x )F (x ) 1 2 xx 1 2 • Also limFx ( ) 0 and limFx ( )1 x x x x  Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 22PMF and CDF for the 3 Coin Toss Example Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 23Expectation of a Random Variable • The expectation (average) of a (discrete valued) random variable X is  X E(X ) xP(X x) xP (x) X x • Three coins example: 3 1 3 3 1 E(X ) xP (x) 01 2 31.5 X x0 8 8 8 8 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 24Important Random Variables: Bernoulli • The simplest possible measurement on an experiment: Success (X = 1) or failure (X = 0). • Usual notation: P (1)P(X1) p P (0)P(X 0)1 p XX • E(X)= Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 25Important Random Variables: Binomial • Let X = the number of success in n independent Bernoulli experiments ( or trials). P(X=0) = P(X=1) = P(X=2)= • In general, P(X = x) = Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 26Important Random Variables: Binomial • Exercise: Show that n and E(X) = np  Px ( ) 1 X x0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 27Important Random Variables: Geometric • Let X = the number of independent Bernoulli trials until the first success. P(X=1) = p P(X=2) = (1p)p 2 P(X=3) = (1p) p • In general, x1 P(X x) (1 p) p for x = 1,2,3,... Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 28Important Random Variables: Geometric • Exercise: Show that  1 P (x) 1 and E(x)  X p x1 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 29Important Random Variables: Poisson • A Poisson random variable X is defined by its PMF: x   P(X x) e x 0,1,2,... x Where 0 is a constant  • Exercise: Show that  and E(X) =  Px ( ) 1  X x0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 30Important Random Variables: Poisson • Poisson random variables are good for counting things like the number of customers that arrive to a bank in one hour, or the number of packets that arrive to a router in one second. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 31Continuousvalued Random Variables • So far we have focused on discrete( valued) random variables, e.g. X(s) must be an integer • Examples of discrete random variables: number of arrivals in one second, number of attempts until sucess Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 32Continuousvalued Random Variables • A continuousvalued random variable takes on a range of real values, e.g. X(s) ranges from 0 to  as s varies. • Examples of continuous(valued) random variables: time when a particular arrival occurs, time between consecutive arrivals. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 33Continuousvalued Random Variables • A discrete random variable has a “staircase” CDF. • A continuous random variable has (some) continuous slope to its CDF. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 34Continuousvalued Random Variables • Thus, for a continuous random variable X, we can define its probability density function (pdf) dF () x ' X f (x) F (x) X x dx • Note that since is non Fx () X decreasing in x we have for all x. fx ( ) 0 X Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 35Properties of Continuous Random Variables • From the Fundamental Theorem of Calculus, we have x F (x) f (x)dx Xx   • In particular,  fx(x)dx F ()1 X   • More generally, b f (x)dxF (b)F (a)P(a Xb) X X X  a Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 36Expectation of a Continuous Random Variable • The expectation (average) of a continuous random variable X is given by  E(X ) xf (x)dx X   • Note that this is just the continuous equivalent of the discrete expectation  E(X ) xP (x) X x Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 37Important Continuous Random Variable: Exponential • Used to represent time, e.g. until the next arrival x e for x  0 fx ( ) • Has PDF X 0 for x 0 for some 0   1 • Show f (x)dx 1 and E(X ) X   0 – Need to use integration by Parts Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 38Exponential Random Variable • The CDF of an exponential random variable is: xx x F (x) f (x)dxe dx XX  00 x  xx  ee1  0 • So x P(X x)1F (x)e X Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 39Memoryless Property of the Exponential • An exponential random variable X has the property that “the future is independent of the part”, i.e. the fact that it hasn’t happened yet, tells us nothing about how s e much longer it will take. • In math terms P(Xst Xt)P(Xs) for s,t 0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 40Memoryless Property of the Exponential P(Xst,Xt) • Proof: P(Xst Xt) P() Xt P() X s t  P() Xt () st e s eP() Xs  t e Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 41
Website URL
Comment