TBD
Chapter 3.3 - 3.6.
| 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] |
| Ai | 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 |
| Nq | average number of customers waiting in the queue |
| W | average time a customer spends in the queue |
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(i) are independent and identically distributed with an unspecified distribution function and average service time 1/μ and variance of this service time σY2.
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.
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(Ni)] = E[Ai+1], where Ai has the same distribution function for all i. This means we can drop the subscript and state that ρ = E[A].
Recall that Ni+1 = Ni - U(Ni) + Ai+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:
Steady state operation implies a distribution function of Ni that is the same for all i, thus:
which implies:
so:
The number of arrivals during the service interval depends only on the length of the service interval, not on Ni assuming that steady state RVs are independent of the arrival process. So Ai+1 is independent of Ni and U(Ni). So:
Similarly:
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:
We haven't solved for E[A2] 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 σY2, 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 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 (σY2) moments of the service time.
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 σY2, the variance of the service time. Furthermore, N and T can be minimized if the service time is constant (i.e. deterministic), which implies σY2 = 0. Thus, there are two special cases of the M/G/1 queueing system:
For M/M/1, the arrival rate is Poisson with exponentially distributed interarrival times. The service times are exponentially distributed with mean 1/μ and σY2 = (1/μ)2.
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:
For M/D/1, the arrival rate is Poisson with exponentially distributed interarrival times. The service times are deterministic/fixed at 1/μ and σY2 = 0.
Thus, from the M/G/1 P-K formulas, we can derive and simplify the formulas for an M/D/1 queueing system:
For D/D/1 queueing systems, the P-K formulas do not apply.
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.
We can directly reference the P-K formulas for an M/M/1 queueing system, and compute:
The P-K formulas for our M/M/1 queueing system also come in handy here:
So:
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.
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.
This is simply the probability that an arrival finds the server busy, which is the utilization. Thus, we can compute the utilization, ρ, as:
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:
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:
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:
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:
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:
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.
So:
and:
and:
but:
So, the configuration with ten slower computer leads to much larger delays than with the single fast computer.
This implies a ten-server queueing model, or an M/M/10 queueing system, which is more difficult to analyze.
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.
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:
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?
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.
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:
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.
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.
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.
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:
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:
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:
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:
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:
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:
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.
So:
and:
and:
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:
