tailieunhanh - Lecture Networking theory & fundamentals - Chapter 2

The following will be discussed in this chapter: Delay in packet networks, introduction to queueing theory, review of probability theory, the poisson process, little’s theorem, proof and intuitive explanation. | Lecture Networking theory & fundamentals - Chapter 2 TCOM 501: Networking Theory & Fundamentals Lecture 2 January 22, 2003 Prof. Yannis A. Korilis 1 2-2 Topics Delay in Packet Networks Introduction to Queueing Theory Review of Probability Theory The Poisson Process Little’s Theorem Proof and Intuitive Explanation Applications 2-3 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 Focus: Queueing & Transmission Delay 2-4 Basic Queueing Model Buffer Server(s) 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 2-5 Characteristics of a Queue b m Number of servers m: one, multiple, infinite Buffer size b Service discipline (scheduling): FCFS, LCFS, Processor Sharing (PS), etc Arrival process Service statistics 2-6 Arrival Process n +1 n n −1 τn tn t τ n : interarrival time between customers n and n+1 τ n is a random variable {τ n , n ≥ 1} is a stochastic process Interarrival times are identically distributed and have a common mean E[τ n ] = E [τ ] = 1/ λ λ is called the arrival rate 2-7 Service-Time Process n +1 n n −1 sn t sn : service time of customer n at the server { s n , n ≥ 1} is a stochastic process Service times are identically distributed with common mean E [ sn ] = E [ s ] = µ µ is called the service rate For packets, are the service times really random? 2-8 Queue 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: .