TCOM 501: Networking Theory & FundamentalsTopicsSources of Network DelayBasic Queueing ModelCharacteristics of a QueueArrival ProcessService-Time ProcessQueue DescriptorsQueue Descriptors: ExamplesProbability FundamentalsThe Exponential DistributionExponential Distribution (cont.)Memoryless PropertyPoisson DistributionPoisson Distribution (cont.)Sum of Poisson Random VariablesSum of Poisson Random Variables (cont.)Sampling a Poisson VariableSampling a Poisson Variable (cont.)Poisson Approximation to BinomialPoisson Process with Rate lInterarrival-Time StatisticsSmall Interval ProbabilitiesMerging & Splitting Poisson ProcessesModeling Arrival StatisticsLittle’s TheoremCounting Processes of a QueueTime AveragesProof of Little’s Theorem for FCFSProof of Little’s for FCFS (cont.)Probabilistic Form of Little’s TheoremProbabilistic Form of Little (cont.)Slide 33Time vs. Stochastic AveragesMoment Generating FunctionDiscrete Random VariablesContinuous Random Variables1TCOM 501: Networking Theory & FundamentalsLecture 2January 22, 2003Prof. Yannis A. Korilis2-2TopicsDelay in Packet NetworksIntroduction to Queueing TheoryReview of Probability TheoryThe Poisson ProcessLittle’s TheoremProof and Intuitive ExplanationApplications2-3Sources 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 linkFocus: Queueing & Transmission Delay2-4Basic Queueing Model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 bufferArrivalsDeparturesBuffer Server(s)Queued In Service2-5Characteristics of a QueueNumber of servers m: one, multiple, infiniteBuffer size bService discipline (scheduling): FCFS, LCFS, Processor Sharing (PS), etcArrival processService statisticsmb2-6Arrival Process : interarrival time between customers n and n+1 is a random variable is a stochastic processInterarrival times are identically distributed and have a common mean is called the arrival raten1n -1n +ntnttntnt{ , 1}nnt �[ ] [ ] 1/nE Et t l= =2-7Service-Time Process : service time of customer n at the server is a stochastic processService times are identically distributed with common mean is called the service rateFor packets, are the service times really random?n1n -1n +nstns{ , 1}ns n �[ ] [ ]nE s E s m= =2-8Queue DescriptorsGeneric descriptor: A/S/m/k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 infinite2-9Queue Descriptors: ExamplesM/M/1: Poisson arrivals, exponentially distributed service times, one server, infinite bufferM/M/m: same as previous with m serversM/M/m/m: Poisson arrivals, exponentially distributed service times, m server, no bufferingM/G/1: Poisson arrivals, identically distributed service times follows a general distribution, one server, infinite buffer*/D/∞ : A constant delay system2-10Probability FundamentalsExponential DistributionMemoryless PropertyPoisson DistributionPoisson ProcessDefinition and PropertiesInterarrival Time DistributionModeling Arrival and Service Statistics2-11The Exponential DistributionA continuous RV X follows the exponential distribution with parameter , if its probability density function is:Probability distribution function:1 if 0( ) { }0 if 0xXe xF x P X xxm-�- �= � =�<�if 0( )0 if 0xXe xf xxmm-��=�<�2-12Exponential Distribution (cont.)Mean and Variance:Proof: 21 1[ ] , Var( )E X Xm m= =0 0002 2 2020 02 22 2 2[ ] ( )12 2[ ] 2 [ ]2 1 1Var( ) [ ] ( [ ])xXx xx x xE X x f x dx x e dxxe e dxE X x e dx x e xe dx E XX E X E Xmm mm m mmmmm mm m m� �-�- � -� �- - � -= = ==- + == =- + = == - = - =� ��� �2-13Memoryless PropertyPast history has no influence on the future Proof: Exponential: the only continuous distribution with the memoryless property{ | } { }P X x t X t P X x> + > = >( ){ , } { }{ | }{ } { }{ }x txtP X x t X t P X x tP X x t X tP X t P X tee P X xemmm- +--> + > > +> + > = => >= = = >2-14Poisson DistributionA discrete RV X follows the Poisson distribution with parameter  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 { } , 0,1,2,...!kP X k e kkll-= = =2-15Poisson Distribution (cont.)Mean and VarianceProof: [ ] , Var( )E X Xl l= =0 0 002 2 20 0 020 0 02 2 2[ ] { }! ( 1)!![ ] { }! ( 1)!( 1)! ! !Var( ) [ ] ( [ ])k kk k kjjk kk k kj j jj j jE X kP X k e k ek ke e ejE X k P X k e k e kk ke j je ej j jX E X E Xl ll l ll ll l ll lll l ll ll l ll l l l ll� � �- -= = =�- -=� � �- -= = =� � �- - -= = == = = =-= = == = = =-= + = + = += - = +� � ��� � �� � �2l l l- =2-16Sum of Poisson Random VariablesXi , i =1,2,…,n, are independent RVsXi follows Poisson distribution with parameter iPartial sum defined as:Sn follows Poisson distribution with parameter 1 2...n nS X X X= + + +1 2...nl l l l= + + +2-17Sum of Poisson Random Variables (cont.)P roof: F orn= 2. Generalization by induc-tion. T he pmf ofS=X1+X2isPfS=mg=mXk= 0PfX1=k; X2=m¡kg=mXk= 0PfX1=kgPfX2=m¡kg=mXk= 0e¡¸1¸k1k!¢e¡¸2¸m¡k2(m¡k)!=e¡(¸1+¸2)1m!mXk= 0m!k!(m¡k)!¸k1¸m¡k2=e¡(¸1+¸2)(¸1+¸2)mm!P oisson with parameter¸=¸1+¸2.2-18Sampling a Poisson VariableX follows Poisson distribution with parameter Each of the X arrivals is of type i with probability pi, i =1,2,…,n, independently of other arrivals; p1 + p2 +…+ pn = 1Xi denotes the number of type i arrivalsX1 , X2 ,…Xn are independentXi follows Poisson