Networking Theory and Fundamentals - Lecture 2

Tham khảo tài liệu 'networking theory and fundamentals - lecture 2', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Networking Theory and Fundamentals - Lecture 2 TCOM 501: Networking Theory & Fundamentals Lecture 2 January 22, 2003 Prof. Yannis A. Korilis 1 Topics 2-2 Delay in Packet Networks Introduction to Queueing Theory Review of Probability Theory The Poisson Process Little’s Theorem Proof and Intuitive Explanation Applications Sources of Network Delay 2-3 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 Basic Queueing Model 2-4 Buffer Server(s) Departures Arrivals 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 Characteristics of a Queue 2-5 m b Number of servers m: one, multiple, infinite Buffer size b Service discipline (scheduling): FCFS, LCFS, Processor Sharing (PS), etc Arrival process Service statistics Arrival Process 2-6 n −1 n +1 n τn t tn τ 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 Service-Time Process 2-7 n −1 n +1 n 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? Queue Descriptors 2-8 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 infinite Queue Descriptors: Examples 2-9 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 system Probability Fundamentals 2-10 Exponential Distribution Memoryless Property Poisson Distribution Poisson Process Definition and Properties Interarrival Time Distribution Modeling Arrival and Service Statistics The Exponential Distribution 2-11 A continuous RV X follows the exponential distribution with parameter µ, if its probability density function is:  µe− µ x if x ≥ 0 f X ( x) =  if x < 0 0 Probability distribution function: 1 − e − µ x if x ≥ 0 FX ( x ) = P{ X ≤ x} =  if x < 0 0 Exponential Distribution (cont.) 2-12 Mean and Variance: 1 1 E[ X ] = , Va r ( X ) = µ µ2 Proof: ∞ ∞ E[ X ] = ∫ x f X ( x ) dx = ∫ xµ e− µ x dx = 0 0 1 ∞ + ∫ e− µ x dx = = − xe− µ x ∞ µ 0 0 2 2 ∞ ∞ E[ X ] = ∫ x µ e + 2 ∫ xe− µ x dx = −µx 2 −µx ∞ dx = − x e E[ X ] = 2 2 µ µ2 ...