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