...
| Table of Contents | ||
|---|---|---|
|
Question of the Day
TBD
Assigned Reading
Chapter 3.3 - 3.6.
...
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
...
Thus, we can solve for 1/λ, which is the average interarrival time:
Example 3
Example 4
...
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 X1, X2, ..., XM are independent Poisson distributed RVs with average arrival rates of λ1,λ2 , ..., λM, respectively. If this is the case, then X = X1 + X2 + ... + XM is also a Poisson distributed RV with average arrival rate λ = λ1 + λ2 + ... + λ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 Yi 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 Wi denote the mean waiting time in the queue for customers in class i. Note that Ti = Wi + 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 W0
- the service time for customers of priorities j through P that are already waiting, defined by the average wait WA
- 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 WB
Consider W0
First, let's consider W0, 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 Zi 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 WA
Second, let's consider WA, 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, Nq(i) denote the average number of customers of class i in the queue, Wi denote the average waiting time for customers of class i, and Nq,i,j denote the number of class-i customers in the queue when the class-j customer arrives.
Then, by Little's Law:
Consider WB
Lastly, let's consider WB, the mean delay due to customers of higher priority that arrive while the customer of interest is in the queue. Let Mi,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 Wj:
So:
Putting W0, WA, and WB Together
Recall that we are trying to determine the mean waiting time, Wj, for each customer of j = 1, 2, ..., P. Combining the results above:
where:
Solving for Wj:
for j = 1, 2, ..., P.
However, Wj is given in terms of Wj+1, ..., WP. We can solve recursively for WP, then for WP-1, ..., then for W1:
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, Nq, 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 λ1 = 2 arrivals/second, and λ2 = 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 μ1 = 4 services/second and μ2 = 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 Nq 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 Nq:
