11.2 Single Queue Single Server Systems

Figure 11.1 depicts a single-line single-server queue. The system of Fig. 11.1 is also known as a G/G/1 queue. The first "G" indicates that the distribution of interarrival times of customers arriving to the system can be any generic distribution. The second "G" indicates that the service time distribution of the single server is also generic. The "1" indicates that there is a single server.

Figure 11.1. A single-line single-server system.

Customers arrive, join a waiting line if the server is not idle, wait their turn to use the server according to a FCFS queuing discipline, and depart after having received service. The average arrival rate of customers is denoted by l, the average time spent waiting in the queue is denoted by W, the average service is denoted by E[S], and the response time (i.e., the sum of the average waiting time plus the average service time) is denoted by T. Thus,

Equation 11.2.1

Sometimes, the inverse of the average response time (i.e., 1/E[S]) is denoted by m and represents the speed, or service rate, of the server. Likewise, the inverse of the arrival rate (i.e., 1/l) represents the average time between successive arrivals.

The following relationships are obtained by applying Little's Law (see Chapter 3) to the waiting line, to the entire queue, and to the server

Equation 11.2.2

Equation 11.2.3

Equation 11.2.4

where N_w, N, and N_s denote the average number of customers in the waiting line, in the entire queuing station, and at the server, respectively. The average number of customers in the server is also the fraction of time that the server is busy (i.e., its utilization). See Exercise 11.1.

In this chapter, r is used to denote the utilization of a server instead of the notation U used in other chapters. This choice is made because there is a rich literature on single queues and r is more widely used to express utilization. By using the same notation, readers are able to recognize the formulas discussed here to be equivalent to results presented in other publications. Hence,

Equation 11.2.5

Since the utilization of the server is the probability that the server is busy, the probability that the server is idle is equal to the probability p₀ that there are no customers in the queuing station. Hence,

Equation 11.2.6

Example 11.1.

The average interarrival time of packets to a communication link is equal to 5 msec and each packet takes 3 msec on average to be transmitted through the link. What is the utilization of the link?

The average interarrival time is the inverse of the average arrival rate. Therefore, l = 1/5 = 0.2 packets/msec. Thus, the utilization of the link is, according to Eq. (11.2.5), equal to r = 0.2 packets/msec x 3 msec/packet = 0.6 = 60%.

Unfortunately, the result of Eq. (11.2.6) is the only known exact result for G/G/1. However, by imposing additional assumptions about the distributions of the interarrival time and/or service time, a number of other interesting results are possible as discussed in the sections that follow. An approximate result for G/G/1 is given in Section 11.7.