Popular in Course
verified elite notetaker
Popular in Telecommunication
verified elite notetaker
This 37 page Class Notes was uploaded by Ryleigh Heller on Monday September 28, 2015. The Class Notes belongs to TCOM501 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/215359/tcom501-university-of-pennsylvania in Telecommunication at University of Pennsylvania.
Reviews for NETWKINGTHEORY&FUND
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/28/15
TCOM 501 Networking Theory amp Fundamentals Lecture 2 January 22 2003 Prof Yannis A Korilis g Topics Delay in Packet Networks Introduction to Queueing Theory Review of Probabilib Theory The Poisson Process Little s Theorem Proof and Intuitive Explanation Applications Sources of Network Delay Processing Delay Assume processing power is not a constraint Queueing Delay Time buffered waiting for transmission Transmission Delay Propagation Delay Time spend on the link transmission of electrical signal Independent of traffic carried by the link iv Focus Queueing amp Transmission Delay g Basic Queueing Model Buffer Servers I IIII IO III Arrivals Departures Queued In Service A queue models any service station with One or multiple servers A waiting area or buffer Customers arrive to receive service A customer that upon arrival does not find a free server is waits in the buffer g Characteristics of a Queue m Number of servers m one multiple infinite Buffer size 9 Service discipline scheduling FCFS LCFS Processor Sharing PS etc Arrival process r Service statistics g Arrival Process AK n 1 n A A Z39 A A A IT interarrival time between customers n and n1 Tn is a random variable I 114 n 2 1 is a stochastic process 9 Interarrival times are identically distributed and have a common mean Ez39n Ez39 12 k is called the arrival rate Service Time Process n1 n n l AK L V S service time of customer n at the server n Sn n 2 1 is a stochastic process r Service times are identically distributed with common mean ESn Es y H is called the service rate wFor packets are the service times really random Queue Descriptors Generic descriptor ASmk A denotes the arrival process For Poisson arrivals we use M for Markovian B denotes the service time distribution M exponential distribution D deterministic service times G general distribution m is the number of servers k is the max number of customers allowed in the system either in the buffer or in service k is omitted when the buffer size is infinite Queue Descriptors Examples MMl Poisson arrivals exponentially distributed service times one server infinite buffer MMm same as previous with m servers MMmm Poisson arrivals exponentially distributed service times m server no buffering MGl Poisson arrivals identically distributed service times follows a general distribution one server infinite buffer Doo A constant delay system Probability Fundamentals Exponential Distribution Memoryless Property Poisson Distribution Poisson Process Definition and Properties Interarrival Time Distribution Modeling Arrival and Service Statistics The Exponential Distribution A continuous RV X follows the exponential distribution with parameter u if its probabilib density function is ue x ifoO x fX 0 ifxlt0 I Probability distribution function 1 e x ifoO FXXPXSX 0 ifxlt0 g ExponentialDistribution cont Mean and Variance 1 2 EX i VarX u Proof EX ffoxdx fxye xdx 2 3 fe xdx xe x i u 2 2 3 2 Exe xdx 3EX EX2 foxzye xdx x26 x O 1U 1U VarltXgtEX2 ltEX2 2 1 1 u 2 2 2 u Memoryless Property Past history has no influence on the future PXgtxtXgttPXgtx Proof PX X PX r PXgtxtXgtt gtxt gt3 gtx PX gt t PX gt t e xt 6 PX gt x l 61 Exponential the only continuous distribution with the memoryless property Poisson Distribution A discrete RV Xfollows the Poisson distribution with parameter A if its probability mass function is Wide applicability in modeling the number of random events that occur during a given time interval The Poisson Process Customers that arrive at a post office during a day Wrong phone calls received during a week Students that go to the instructor s office during office hours and packets that arrive at a network switch Poisson Distribution cont Mean and Variance EX2 VarX2 2 Proof oo 1 00 2k A 00 2k EX kPXke k e 1 1 k k 1 1 00 3 1 2 e 22 e 2e 2 2 j0 J EX2 Zk2PX k e k2 e k kzo k0 k k0 k 1 0 2 0 2 0 2 e AAZC 2Zje 1 2eZZ o 12 2 j0 j0 j0 VarX EX2 EX2 22 2 22 2 Sum of Poisson Random Variables XI i12n are independent RVs XI follows Poisson distribution with parameter kl Partial sum defined as Sn X1X2Xn r Sn follows Poisson distribution with parameter 7L 1 1 12 n Sum of Poisson Random Variables cont Proof For n 2 Generalization by induc tion The pmf of S 2 X1 X2 is m PSm Z PX1 kX2m k kO m Z PX1 kPX2 m k kO k Ilt m e Al e A2 A7271 kzo k m k m e12i Z m kzo km k e A12A1 A2 m Poisson with parameter A A1 A2 g Sampling aPoisson Variable Xfollows Poisson distribution with parameter 7L Each of the Xarrivals is of type i with probabilib pi i12n independently of other arrivals P1P2 Pn 1 XI denotes the number of wpe i arrivals X1X2Xnare independent r XI follows Poisson distribution with parameter kl M9 Sampling aPoisson Variable cont Proof For n 2 Generalize by induction Joint pmf PX1 1X2 2 PX1 k1X2 k2X k1 k2 PX k1 k2 k1 k2 Aim HQ gt191 6 A I k1 k1 k2 1 mumklomb e AltP1p2gt Ap1p1k1 p2 AP2I 2 k1 k2 X1 and X2 are independent 1 e Apl Agjgkl 2 e Ap2 Xi follows Poisson distribution with parameter Api Poisson Approximation to Binomial Binomial distribution with Proof parameters n p PX k njpk1pnk k PX k njpk ka n k1n 1n X k 1 1 Wk k k 2 l 7 As n gtoo and p gtO with np7t nk1mn1n moderate binomial distribution nk Moo gt1 converges to Poisson with A n A parameter 7 l Zj We Poisson Process with Rate A At tZO counting process At is the number of events arrivals that have occurred from time 0 when AOO to time t At As number of arrivals in interval 5 t Number of arrivals in disjoint intervals independent Number of arrivals in any interval t tt of length I Depends only on its length I Follows Poisson distribution with parameter kt PAt 239 At n 6 n 01 n gt Average number of arrivals kt L is the arrival rate Interarrival Time Statistics Interarrival times for a Poisson process are independent and follow exponential distribution with parameter A gt tn time of nth arrival Tntn1tn nth interarrival time Pz39n SS1 eIS S 20 Proof Probability distribution function PTn S S 1 PTn gt S 1 PAtn S Afn O 1 6 15 Independence follows from independence of number of arrivals in disjoint intervals Small Interval Probabilities Interval t 5 t of length 5 PAt 5 At 0 1 25 05 PAt 5 At 1 25 05 PAt 5 At 2 2 05 Proof PAt 6 At 0 015 1 15 1amp2 1 A5 05 PA2 5 At 1 04515 2 151 A5 A5 05 PA2 5 At 2 2 1 PA2 5 At k 1 1 250 05 A5 05 2 05 Merging amp Splitting 7L1 M A1 Ak independent Poisson processes with rates k1 xk Merged in a single process A A1 Ak v A is Poisson process with rate k k1 kk gt k1 k2 Poisson Processes Mlp A Poisson processes with rate 7L Split into processes A1 and A2 independently with probabilities p and 1 p respectively A1 is Poisson with rate k1 kp A2 is Poisson with rate k2 7t1 p Modeling Arrival Statistics Poisson process widely used to model packet arrivals in numerous networking problems Justification provides a good model for aggregate traffic of a large number of independent users n traffic streams with independent identically distributed iid interarrival times with PDF Fs not necessarily exponential Arrival rate of each stream Mn r As n gtoo combined stream can be approximated by Poisson under mild conditions on Fs eg FOO F OgtO Most important reason for Poisson assumption Analytic tractability of queueing models g Little s Theorem V 39 739 A customer arrival rate N average number of customers in system T average delay per customer in system Little s Theorem System in steady state NzlT Counting Processes of a Queue A V Nt number of customers in system at time t oct number of customer arrivals till time t Ba number of customer departures ti time t Tl time spent in system by the ith customer Time Averages Time average over interval 0t Steady state time averages 1 r Ni O Nsds N 11mNt t gtOO 12 t l 1im1t f t gtoo 1 at Ti 2 T 1im at i1 t9 5 m 1im t t t gtoo Little s theorem N 1T Applies to any queueing system provided that n Limits T A and 8 exist and I A 8 I We give a simple graphical proof under a set of more restrictive assumptions Proof of Little s Theorem for FCFS FCFS system NOO 4 oct ancl BU staircase graphs 0 N0 00 BU 4 Shaded area between graphs St Nsds t Assumption NtO infinitely often For any such t of Nsds gt Nsds a 21610 gt Nt if r If limits NZ N TZ T ALI u exist Little s formula follows We will relax the last assumption Proof of Little s for FCFS cont In general even if the queue is not empty infinitely often 3930 t at 31 T t at T i1 0 i1 t t O t 050 gt 5t 3 Ni 3 it Result follows assuming the limits Tr gtT 17 and Est gt8 exist and i8 g Probabilistic Form of Little39s Theorem Have considered a single sample function for a stochastic process Now will focus on the probabilities of the various sample functions of a stochastic process Probability of n customers in system at time t 1940 PNt n Expected number of customers in system at t ENltrgt inmNm n imam Probabilistic Form of Little cont pnl ENt depend on t and initial distribution at t0 We will consider systems that converge to steady state there exist pn independent of initial distribution limpnt 2 pm n 01 t gtoo Expected number of customers in steady state stochastic aver EN ann limENt quot0 t 00 For an ergodic process the time average of a sample function is equal to the steady state expectation with probability 1 N limNt 1imENt EN t 00 t 00 Probabilistic Form of Little cont In principle we can find the probability distribution of the delay Tl for customer i and from that the expected value ETl which converges to steady state ET 11mEI i gtoo For an ergodic system 00 Z T T11ml1mEET i oo l i 00 a Probabilistic Form of Little s Formula EN xlET at Arrival rate define as A lim Ema t gtoo l Time vs Stochastic Averages Time averages Stochastic averages for all systems of interest in this course It holds if a single sample function of the stochastic process contains all possible realizations of the process at t gt oo Can be justified on the basis of general properties of Markov chains amp Moment Generating Function 2 Definition for any 75 E R emfxw dx etjPX 2 13 X discrete j X continuous MXCt EietX If the moment generating function MXt of X exists and is finite in some neighborhood of t 0 it determines the distribution of X uniquey Fundamental Properties for any n E W dn 0 cho EixnetX ii MXlt0gt EX Moment Generating Functions and Independence XY independent gt MXyt MXtMyt The opposite is not true amp Discrete Random Variables Distribution Prob Mass Fun Moment Gen Fun Mean Variance parameters PX k MX t VarX Binomial Zpk1 p k pet I 1 p np np1 p mp k01n k at 1 1 Geometrio 1 p 1p 1119p t 1 9 pr p k 17 2 39 39 rr 7 at T r 7 1 Negative Bin lt1 llp 1 pk 1119p t 2 9 p 1 Tap kTT1 Poisson 6 2 1 e t1 A A A k O7 17 ampContinuous Random Variables Distribution Prob Density Fun Moment Gen Fun Mean Variance parameters fX MX 75 VarX Uniform over aTb b2 a b a lt LU lt b Exponential Ae i A LE 2 0 Normal 1 6 x M220392 Mt039t22 u 02 M 02 27139039 ooltvltoo