...

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:

Image Added

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):

Image Added

The condition for stability is:

Image Added

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.

Image Added

For Poisson arrivals, it can be shown that:

Image Added

Note that if Yi has an exponential distribution, then:

Image Added

which is expected for a memoryless RV.

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

So:

Image Added

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:

Image Added

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:

Image Added

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

Image Added

So:

Image Added

Putting W₀, W_A, and W_B Together

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:

Image Added

where:

Image Added

Solving for W_j:

Image Added

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₁:

Image Added

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

Image Added