Table of Contents

Question of the Day

TBD

Assigned Reading

Chapter 3.3 - 3.6.

Summary of Notation

Notation	Meaning
N(t)	number of customers in the network at time t
Ni	number of customers in the network after the ith customer departs from the network
N	average number of customers in the network
D(t)	number of departures during the interval [0, t]
A(t)	number of arrivals during the interval [0, t]
A_i	number of arrivals during the service interval for the ith customer
U(X)	indicator function for random variable X
λ	average arrival rate into the network
1/λ	average interarrival time between customers
τ	average interarrival time between customers
τ_i	interarrival time between customer i-1 and customer i
T	average time a customer spends in the network
μ	average service rate
1/μ	average service time per customer
ρ	utilization; average fraction of time the server is busy; the probability that the server is busy at some randomly selected time
N_q	average number of customers waiting in the queue
W	average time a customer spends in the queue

M/G/1 Queueing Systems

A queueing system that is M/G/1 states that the arrival process (i.e. distribution of interarrival times) is Poisson, denoted by M, the service distribution (i.e. the expected service time) is general, denoted by G, and there is a single server, denoted by 1. A Poisson arrival process implies that the interarrival times τ_i are independent and identically distributed with an exponential distribution and expected value 1/λ. A general service process implies that the service times Y⁽ⁱ⁾ are independent and identically distributed with an unspecified distribution function and average service time 1/μ and variance of this service time σ_Y².

The results that follow apply to any single server queueing system with Poisson arrivals, independent and identically distributed service times, and a FCFS queueing discipline. The queueing system is in steady state if the utilization, ρ is less than 1.

Derivation of the P-K Formulas

For Poisson arrivals and steady state operation, the distribution function for the number of customers in a system is the same at any arbitrary point in time. As such, ρ = E[U(N(t))] = E[U(N_i)] = E[A_i+1], where A_i has the same distribution function for all i. This means we can drop the subscript and state that ρ = E[A].

Recall that N_i+1 = N_i - U(N_i) + A_i+1. If we square both sides of this equation, and take the expected values, we obtain:

Taking a closer look at each side of this expression, we can observe the following with respect to each term in the equation:

LHS and RHS Term 1

Steady state operation implies a distribution function of Ni that is the same for all i, thus:

RHS Term 2

which implies:

RHS Term 4

so:

RHS Term 5

The number of arrivals during the service interval depends only on the length of the service interval, not on N_i assuming that steady state RVs are independent of the arrival process. So A_i+1 is independent of N_i and U(N_i). So:

RHS Term 6

Similarly:

Putting it all Together

Furthermore, because the system has Poisson arrivals (i.e. memoryless) and is operating in steady state, the number of customers in the system does not depend on t. Thus:

This means we can write the original, complex expression more simply as:

where solving for N yields:

What about RHS Term 3?

We haven't solved for E[A²] though, which is the second moment of A. We know that the mean and variance of a random service time are known as 1/μ and σ_Y², respectively. So:

and:

So:

Since Y is itself a RV, we'll write the above expression more generally as:

But:

So:

We can the above into N, which we solved for earlier as:

which results in:

From Little's Law, we can relate N to λT as:

Let the coefficient of variation of the service time random variable be defined as:

Given this, we can rewrite:

as:

The P-K Formulas

The Pollaczek-Khinchine (P-K) mean-value formulas give the mean number (N) and mean time (T) as functions of utilization (ρ), arrival rate, and the first (1/μ) and second (σ_Y²) moments of the service time.

M/G/1

For an M/G/1 queueing system, the P-K formulas are:

It can be observed that for a fixed λ and μ (and thus a fixed ρ), N and T increase linearly with σ_Y², the variance of the service time. Furthermore, N and T can be minimized if the service time is constant (i.e. deterministic), which implies σ_Y² = 0. Thus, there are two special cases of the M/G/1 queueing system:

M/M/1
M/D/1

M/M/1

For M/M/1, the arrival rate is Poisson with exponentially distributed interarrival times. The service times are exponentially distributed with mean 1/μ and σ_Y² = (1/μ)².

Thus, from the M/G/1 P-K formulas, we can derive and simplify the formulas for an M/M/1 queueing system:

and:

So, the P-K formulas for an M/M/1 system are:

M/D/1

For M/D/1, the arrival rate is Poisson with exponentially distributed interarrival times. The service times are deterministic/fixed at 1/μ and σ_Y² = 0.

Thus, from the M/G/1 P-K formulas, we can derive and simplify the formulas for an M/D/1 queueing system:

Comparison of M/G/1 Queueing Systems

Average time in the system as a function of utilization

Average number in the system as a function of utilization

Contrast to D/D/1

For D/D/1 queueing systems, the P-K formulas do not apply.

Examples

Example 1

Suppose an application passes data transmission requests to the data communications protocol in an end host. The requests arrive according to a Poisson distribution. The data from each request is encapsulated in a single frame for transmission across the outgoing link, and the frame lengths have an exponential distribution. The capacity of the point-to-point link is denoted as C bits/second.

In this example, the customers are frames, and the server is the hardware that transmits frames onto the link.

Because there are Poisson arrivals, the interarrival times are memoryless and exponentially distributed and we start our Kendall's notation for the queueing system as M/*/*. The frames are said to have exponentially distributed lengths. This means the service times will be exponentially distributed (i.e. longer frames take longer to service). Thus, our queueing system is M/M/*. Finally, because we are transmitting onto a single point-to-point link (i.e. a bus), only one transmission can occur at once. Thus, there must be a single server, and we complete our system classification as M/M/1.

The average frame length is 1/μ_l or 1000 bits/frame. Thus, the average service time is 1/μ or 1/μ_lC seconds/frame.

Suppose the utilization of the transmission channel is determined to be 0.6.

What is the average number of frames queued or in transmission?

We can directly reference the P-K formulas for an M/M/1 queueing system, and compute:

If an average of one second elapses from the time that a data request occurs until transmission of the corresponding frame is complete, what is the link capacity?

The P-K formulas for our M/M/1 queueing system also come in handy here:

So:

What is the average fraction of time the channel is busy, and what is the average number of frames in service?

This is a trick question. Both of these are different ways to ask for the utilization of the system. The utilization was given to us as 0.6, thus the answer to both these questions is 0.6.

Can there be exactly ρ frames in service at any instant?

Since we are modeling a real-world, physical system with a single server that works in units of frames, either a single frame is being serviced or no single frame is being serviced. Thus, the answer is no; there must be either 0 or 1 frames in service at any given instant. ρ, on the other hand, denotes the probability that a frame is being serviced at an arbitrary moment in time.

Example 2

Consider a single server FCFS queueing system with interarrival times that are exponentially distributed with a mean value of 3 minutes and service times that are exponentially distributed with a mean value of 2 minutes.

Given this little bit of information, we can deduce that the arrival process is Poisson with arrival rate λ = 1/3 customers/minute, the service rate is μ = 1/2 customers/minute, and that the queueing system is M/M/1.

What is the probability that an arrival will have to wait for service?

This is simply the probability that an arrival finds the server busy, which is the utilization. Thus, we can compute the utilization, ρ, as:

What is the average length of the queue?

We can directly use the P-K formulas for an M/M/1 queueing system, and compute the average number of customers waiting in line as:

If the mean service time is 2 minutes, what must the mean interarrival time be so that the average wait in the queue is 5 minutes?

We want to find 1/λ (the average interarrival time), and we know the average service time is 1/μ = 2 minutes. The utilization, ρ, is ρ = λ/μ, so we have a way of finding 1/λ given that we can determine the utilization.

As given by the P-K formulas for an M/M/1 queueing system, we can compute the utilization using the known values of μ and W:

From this, we can directly compute the average interarrival time using the definition of utilization:

For the mean interarrival time computed above, find the average transaction time and the average number of waiting customers in the system

The average transaction time is the time a customer spends in the system, which is the wait time in the queue plus the service time:

We can use Little's Law directly to compute the average number of customers in the system:

At what mean interarrival time does the queue grow arbitrarily large?

If the queue were to grow arbitrarily large, the system would be considered unstable given the fixed service rate. Thus, we want to find the point at which the system becomes unstable. Stability is defined as the utilization being less than or equal to 1:

Thus, we can solve for 1/λ, which is the average interarrival time:

Example 3

A batch scheduling computer completes each job assigned to the CPU before starting the next job. This system can be modeled as an M/M/1 queueing system, where the average length of a job is 1/μ_j instructions.

Suppose there are two options available:

One fast computer
Ten slower computers

The single fast computer has an execution speed of C instructions/second, and each of the slower computers has an execution speed of C/10 instructions/second.

If the faster computer is used, the arrival rate of new jobs is λ. If the ten slower computers are used, each is responsible for 10% of the jobs arriving by a Poisson distribution at rate λ/10. Envision 10 separate queues leading to 10 separate slow computers. Each queue is "magically" assigned 10% of the customers. A job is never split and handled by multiple of the 10 computers in parallel.

Determine the fraction of time each computer is busy and the average total delay for both options (1) and (2)

One Fast Computer

So:

and:

Ten Slow Computers

and:

but:

So, the configuration with ten slower computer leads to much larger delays than with the single fast computer.

In option (2), suppose any arriving or waiting job can use any available computer. What queueing model is appropriate?

This implies a ten-server queueing model, or an M/M/10 queueing system, which is more difficult to analyze.

Example 4

A total of M terminals are connected to a concentrator (i.e. a multiplexer). The output line from the concentrator operates at 1200 bits/second. Message lengths from each terminal are fixed at 28 bytes. The concentrator itself adds a 2-byte protocol header to each message, bringing the total message length to 30 bytes.

Messages from each terminal arrive to the concentrator with a Poisson distribution at a rate of 3 messages/minute.

Determine the maximum number of terminals that can be connected to the concentrator without resulting in an unstable system

Suppose X₁, X₂, ..., X_M are independent Poisson distributed RVs with average arrival rates of λ₁,λ₂ , ..., λ_M, respectively. If this is the case, then X = X₁ + X₂ + ... + X_M is also a Poisson distributed RV with average arrival rate λ = λ₁ + λ₂ + ... + λ_M.

Given this fact, all of the arrivals from the M terminals taken together form a Poisson arrival process with rate:

and expected service time:

Stable operation occurs from ρ < 1, which implies:

Suppose that only the original 28 bytes of each message are stored in the queue and that the 2-byte header is added during transmission. What is the average buffer space occupied if 70 terminals are attached to the connector? Include both the queue buffer and space to store a copy of the current transmission.

The system is an M/D/1 queueing system, so using the P-K formulas for M/D/1, the average messages in the system is:

and the average buffer space occupied is:

As a question for the reader, what is the answer to the above question if 99 terminals are attached?

Queueing Systems with Priority-Based Disciplines

So far, we have discussed FCFS queueing systems. Oftentimes, network operators are concerned with fast service for certain classes of users and slower/normal service for other users. For example, real-time voice or video streaming requires minimal delay and small delay variation (jitter). Likewise, network management traffic should react quickly to critical problems, and higher paying customers might should be provided superior service.

Priority Queueing

Consider P classes of customers ordered by priority, where class 1 is the lowest priority and class P is the higher priority. A separate queue can be used for each class:

The queueing discipline for such a priority queueing system could be to take the next customer from the highest priority queue that is not empty, where customers within a single class are served on FCFS basis.

If a higher priority customer arrives while a lower priority customer is being served, there are a variety of ways the event can be handled:

Nonpreemptive Service

Once service begins for a customer, regardless of their priority, continue serving the customer even if a higher priority customer arrives during service. Zero service interruption occurs in this scenario.

Preemptive Service without Resumption

In this mode of operation, the priority queueing system will terminate ongoing service for a customer if a higher priority customer arrives during the service. The customer that is "kicked out" of the server is placed back at the front of the queue in its service class (i.e. it will be served first the next time the service class is selected for servicing). No work is saved for the lower preempted customer; processing must start from scratch.

Preemptive Service with Resumption

In this model, ongoing service of a customer is terminated if a higher priority customer arrives. The interrupted customer and its service state is placed at the front of the corresponding queue. When the preempted customer is selected again for service, it will resume service where the server left off.

Mean Waiting Time

The model we will use is a nonpreemptive service with Poisson arrivals for each customer class (λ_i rate for priority class i), independent and identically distributed service times for a given class (where RV Y_i will represent the service time for arbitrary customer of class i), and where distinct classes may have different service time distributions.

The fraction of time the server is busy with class i customers is known as the traffic intensity for class i (i.e. the utilization of the server by class i traffic):

The condition for stability is:

Let W_i denote the mean waiting time in the queue for customers in class i. Note that T_i = W_i + 1/μ_i is the mean time in the system for customers of class i.

The goal is to determine the mean waiting time for each class. We will consider the arriving customer of priority class j, which must wait for:

the completion of the service interval for the customer currently in service (if any), defined by the average wait W₀
the service time for customers of priorities j through P that are already waiting, defined by the average wait W_A
the service time for customers of priorities j+1 through P that arrive while the customer of interest is queued for servicing, defined by the average W_B

Consider W₀

First, let's consider W₀, the mean delay due to a customer already in service when the customer of interest arrives. Suppose a customer from class i is in service when the customer of interest arrives. Let Z_i denote the remaining service time for the current customer after the customer of interest arrives.

For Poisson arrivals, it can be shown that:

Note that if Yi has an exponential distribution, then:

which is expected for a memoryless RV.

But, the probability that an arrival finds a class i customer in service is ρ_i.

So:

Consider W_A

Second, let's consider W_A, the mean delay due to customers of higher priority j or greater that are already queued for service when the customer of interest arrives.

Let, N_q⁽ⁱ⁾ denote the average number of customers of class i in the queue, W_i denote the average waiting time for customers of class i, and N_q,i,j denote the number of class-i customers in the queue when the class-j customer arrives.

Then, by Little's Law:

Consider W_B

Lastly, let's consider W_B, the mean delay due to customers of higher priority that arrive while the customer of interest is in the queue. Let M_i,j denote the number of class-i customers that arrive while the class-j customer of interest is in the queue. Then:

Since the average time a class-j customer spends in the queue is W_j:

So:

Putting W₀, W_A, and W_BTogether

Recall that we are trying to determine the mean waiting time, W_j, for each customer of j = 1, 2, ..., P. Combining the results above:

where:

Solving for W_j:

for j = 1, 2, ..., P.

However, W_j is given in terms of W_j+1, ..., W_P. We can solve recursively for W_P, then for W_P-1, ..., then for W₁:

for j =1, 2, ..., P, where:

Example 1: How does the mean waiting time for class 1 customers compare to that of class 2 customers?

Given there are two classes of traffic (P = 2), let class 1 be standard data and class 2 be urgent data.

where:

As we would expect, note that:

Example 2: What are N, N_q, T, and W for each class of customer and for the system as a whole?

Consider a single-server queueing system with a nonpreemptive priority queueing discipline and two classes of customers. The arrivals for each class are Poisson with rates λ₁ = 2 arrivals/second, and λ₂ = 1 arrival/second, respectively.

Class 1 customers have exponential service times with an average service time of 1/4 seconds, while class 2 customers have deterministic service with a service time of 1/4 seconds. This implies μ₁ = 4 services/second and μ₂ = 4 services/second.

First note that:

As such, the queueing system is stable.

Class 1 Customers (w/exponential service times)

Class 2 Customers (w/deterministic service times)

So:

and:

and:

Putting it all together

Thus, we can use Little's Law to find the N_q for each class of customer:

and:

Likewise, we can solve for T and N of each class:

To analyze the entire system (comprised of both customer classes), we can solve for W, T, N, and N_q:

Browser not supported