网络排队论基础.ppt

TCOM 501: Networking Theory & Fundamentals
Lecture 2
January 22, 2003
Prof. Yannis A. Korilis
1
Topics
Delay in works
Introduction to Queueing Theory
Review of Probability Theory
The Poisson Process
Little’s Theorem
Proof and Intuitive Explanation
Applications
2
Sources work 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
3
Basic 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 buffer
Arrivals
Departures
Buffer
Server(s)
Queued
In Service
4
Characteristics of a Queue
Number of servers m: one, multiple, infinite
Buffer size b
Service discipline (scheduling): FCFS, LCFS, Processor Sharing (PS), etc
Arrival process
Service statistics
m
b
5
Arrival Process
: interarrival time between customers n and n+1
is a random variable
is a stochastic process
Interarrival times are identically distributed and have mon mean
l is called the arrival rate
6
Service-Time Process
: service time of customer n at the server
is a stochastic process
Service times are identically distributed mon mean
m is called the service rate
For packets, are the service times really random?
7
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: 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
8
Queue Descriptors: Examples
M/M/1: Poisson arrivals, exponential