...
| Table of Contents | ||
|---|---|---|
|
Question of the Day
TBD
Assigned Reading
Chapter 3.1 - 3.2. ECE 6400 students should also read Chapter 4.4 as an independent study.
Queuing Models
The goal of this module is to introduce the simplest way in which we can model the behavior of a link.
...
- First-come, first-served (FCFS)
- process customers in order of arrival
- most common queueing discipline
- e.g. linked list data structure where 0th element is always removed
- Last-come, first-served (LCFS)
- process most recent customer to have arrived
- could lead to starvation
- e.g. use of a stack via push and pop (brings back memories from x86 assembly, right?
)
- Round robin (RR)
- Poll from separate queues in a circular manner
- Processor sharing (PS)
- Time shared access to server
- All customers served simultaneously (but a little at a time)
- e.g. a CPU on a general purpose machine where the OS schedules tasks
- Random
- Priority
- Multiple classes of customers
- Some classes have higher or lower priority than others
- Higher priority customers receive "better" service
- Lower priority customers receive "worse" service
...
Thus, the average number of customers in the system during the interval [0, t] is:
Consider all customers in system at time t (i.e. N(t) customers). Let RN(t) denote the total time after t that those N(t) customers spend in the system. The average time spent in the system by all customers arriving in the interval [0, t] is:
So:
and:
For the stable system we are concerned with, the following limits hold:
...
There are many ways we can apply Little's Law in analyzing networks.
Using Little's Law with a Queue and a Server
Let's first consider its application to the queue and server of a system. N is the expected number of customers in the system, and T is the expected time each customer spends in the system.
Thus, Little's Law can be applied directly as:
Using Little's Law with Just a Queue
Next, let's consider its application to the queue only. Nq is the expected number of customers in the queue, and W is the expected time a customer spends waiting in the queue.
Thus, we can apply Little's Law scoped at the queue as:
Computing the Utilization (i.e. Pr(server is busy))
The average service time is the inverse of the service rate, or 1/μ. Thus:
So, multiplying all terms by λ, we get:
which implies:
where:
Note that ρ <= 1, since the arrival rate λ should be less than or equal to the service rate μ in a stable system.
Example: Route Through a Network
This has a queueing module that can be expressed as:
What is the average delay through the network?
The arrival to system 1 in arrivals per second is λ = λ1 + λ2 + λ3 = 3 arrivals/s. Thus, for system 1, the rate in is equal to the rate out, so the arrival rate to system 2 is λ = 3 arrivals/s. Similarly, the arrival rate to system 3 is λ = 3 arrivals/s.
The time spent in the entire system is T = T1 + T2 + T3. We can solve for each subsystem's time:
Thus, T = T1 + T2 + T3 = 0.883 + 0.367 + 0.867 = 2.067 seconds.
Utilization
Recall that utilization is the average fraction of time the system is busy. For a single server queueing system, the utilization is the average fraction of time the server is busy.
We can characterize the utilization in terms of the arrival rate λ and the service rate μ.
Method 1
The measured utilization during the interval [0, t'] is:
For a stable system operating in steady state:
Recall that:
where:
Method 2
Consider a system with a FCFS service and a single output channel.
We can remove the FCFS constraint, but analysis is more complex. So, let Ni denote the number of customers in the network just after the departure of the ith customer and let Ai+1 denote the number of arrivals that occur while customer i+1 is being served.
Case 1
Ni > 0, meaning the network is not empty when the ith customer departs.
The service for the (i+1)st customer begins immediately after the departure of the ith customer, so Ni+1 = Ni + Ai+1 - 1.
Case 2
Ni = 0, meaning the network is empty when the ith customer departs.
The network remains empty until the arrival of the (i+1)st customer, so Ni+1 = Ni + 1 + Ai+1 - 1 = 0 + 1 + Ai+1 - 1 = Ai+1.
Let's define an indicator function to denote whether or not the network is empty:
Combining the expressions for cases 1 and 2 into a single expression, we can write Ni+1 = Ni - U(Ni) + Ai+1, where Ni+1, Ni, and Ai+1 are random variables and U(Ni) is a random variable.
This means that E[Ni+1] = E[Ni] - E[U(Ni)] + E[Ai+1]. Note that E[U(Ni)] = Pr(Ni > 0).
We assume a steady state network, which means E[Ni] = E[Ni+1]. Thus, E[Ni] = E[Ni] - E[U(Ni)] + E[Ai+1] and E[U(Ni)] = E[Ai+1]. This result indicates the probability that the server is busy immediately after a departure is equal to the average number of arrivals that occur in one service time.
Our goal is to find the utilization (ρ), or the fraction of time the server is busy, or the probability the server is busy at an arbitrary time instant (all meaning the same thing).
When does ρ = E[U(Ni)]?
Deterministic Arrivals
Assume a D/D/1 queueing system (recall D = deterministic). The above model sports one arrival per second and has a service time of 1/2 second per customer.
Ni = 0 for all i, so E[U(Ni)] = E[0] = 0. But, ρ = 1/2. So, E[U(Ni)] != ρ for this D/D/1 queueing system.
Poisson Arrivals
However, it can be shown that for Poisson arrivals, E[U(Ni)] = ρ. Thus, for Poisson arrivals, ρ = E[U(Ni)] = E[Ai+1].
This means the utilization of the server is equal to the average number of arrivals during a service interval.
We will use this fact to evaluate the performance of queueing systems with Poisson arrivals.