On job assignment for a parallel system of processor sharing queues

858

IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7 , JULY 1990

On Job Assignment for a Parallel System of Processor Sharing Queues FLAVIO BONOMI, MEMBER, IEEE

i

Abstmct-Interest in the job assignment problem for parallel queues has been recently stimulated by research in the area of load balancing in distributed systems, where one is concerned with assigning tasks or processes to processors in order to achieve optimal system performance. However, most of the studies found in the literature refer to a system of parallel queues with FCFS service discipline, while it is well known that the processor sharing (PS) service discipline is often a better model for CPU scheduling in timeshared computer systems. In this paper, we underline some interesting peculiarities of the assignment problem with PS queues as compared to the usual case of the FCFS systems. Also, we propose an approach to the design of assignment algorithms which, in this case, produces solutions performing better than the well-known join-the-shortestqueue (JSQ) assignment rule. However, the algorithms obtained following this approach require more information about the nature of the state of the queueing system. We then illustrate the robustness of the JSQ policy with respect to the nature of the offered load and with respect to system nonhomogeneities, when we consider parallel systems of PS queues. Such properties, together with the cost of the overheads involved in the implementation of more complex policies, seems to indicate that the JSQ policy, although not necessarily optimal, offers a very good solution to the job assignment problem for PS parallel systems.

Index Term- Job assignment, join-the-shortest-queue, parallel systems of queues, performance analysis, processor sharing discipline, queueing systems, total completion time.

1. INTRODUCTION

T

HE job assignment problem has been studied extensively in the past decades. Much of the work has been motivated by problems arising in operations research [lo], [ 121, [14], and more recently in computer and communication systems [ll, [71, [15]. One example is the currently active research area of load balancing in distributed systems (see, e.g., [21-[51) where one is concerned with assigning tasks or processes to processors in order to achieve optimal system performance. Most of the studies found in the literature refer to a system of parallel queues with FCFS service discipline. However, it is well known that the processor sharing (PS) service discipline is often a better model for CPU scheduling in time-shared computer systems. Thus, in the context of job assignment in a multiprocessor computer system, it is important to study the performance of various job assignment algorithms by considering systems of parallel queues with PS service discipline. In this paper, we underline some interesting peculiarities of the assignment problem with PS queues as compared to

the usual case of the FCFS systems. Also, we propose an approach to the design of assignment algorithms for this case which produces solutions performing better than the wellknown join-the-shortest-queue (JSQ) assignment rule. However, one of the most important results of this study is the illustration of the robustness of the JSQ policy with respect to the nature of the offered load and with respect to system nonhomogeneities, when we consider parallel systems of PS queues. Such properties, together with the cost of the overheads involved in the implementation of more complex policies, suggests that the JSQ policy, although not necessarily optimal, offers a very good solution to the job assignment problem for PS parallel systems. This presentation is intended as an introduction to the issue. Ongoing work by this author is aiming at the more rigorous proof of some of the conjectures proposed and to the development of a more complete and rigorous view of the problem. In Section 11, we discuss two of the optimality criteria most commonly considered to compare job assignment policies, namely, the stochastic order and the average total completion time criterion. We show that the latter, while being weaker than the former, still provides a useful criterion when policies are to be evaluated in terms of average performance measures, such as, for example, the system average response time. In Section 11, we summarize some of the most relevant results available in the literature on job assignment to parallel FCFS servers. In Section 111, we discuss the assignment problem for a parallel system of PS queues with exponential interarrival times and exponential and identical service requirements. We prove the optimality of the JSQ assignment policy for this case. Section IV is devoted to the investigation of feasible policies for the case of general service time distribution. We propose an approach which can allow a meaningful comparison of servers in the perspective of job assignment. Finally, in Section V, we present a comparative discussion of the assignment problem for FCFS and PS parallel systems. The main observation is that there are some interesting structural differences between the two cases, which should be well understood in order to devise efficient (or optimal) assignment policies. Section VI is devoted to concluding remarks and open issues. Many are in fact the questions touched upon by this study which require further investigation. 11. SOMEOPTIMALITY CRITERIA

Manuscript received August 5 , 1987; revised March 23, 1988. The author is with AT&T Bell Laboratories, Holmdel, NJ 07733 IEEE Log Number 9035962.

In this section, we discuss two optimality criteria often referred to in the literature on job assignment to parallel servers.

0018-9340/90/0700-0858$01.00 0 1990 IEEE

F

859

BONOMI: JOB ASSIGNMENT FOR PARALLEL SYSTEM OF QUEUES

First, we consider optimality in the sense of stochastic or-

n(t)

t

TOTAL COMPLETION TIME C(T)

der (SO). Definition I: A policy a*is optimal in the sense of stochastic order if

T

(2.1) where nd(t) is the number of job departures by time t, the vector s(0) describes the initial state for the system, and the assignment policy considered is identified by the respective subscripts. This criterion, used in [12] and [14], is a very strong one, and it might be interesting to consider weaker criteria which still relate to relevant performance measures, such as the average response time, the average number in the system, etc. Thus, we next consider optimality in the sense of expected total completion time (TCT). Definition 2: A policy ?r* is optimal in the sense of the expected total completion time if

t

The total completion time C(7‘).

Fig. 1.

very wide class of criteria involving the expectation of more general functions of the number of jobs in the system. In what follows we will, for ease of notation, neglect the conditioning on the initial state. The following result provides a useful interpretation for the TCT-optimality. Proposition 2: If the arrival process is independent of the assignment policy adopted and of the initial state, then the two following problems

PI : minE,[C(T)] x

for everyT,

and n

E,*[C(T)ls(O)

=SI I E,[C(T)(s(O) =SI for every T ,

Pz : m, inxE,(dj) T ,s

(2.2)

where (nu(t) - nd(t))dt

(2.3)

and where n,(t)

= number

of arrivals in the interval [0, t],

nd(t) = number of departures in the interval [0, t],

when d j is the departure epoch for the jth job to leave the system, are equivalent. Proof: See Appendix 11. Finally, with the next Proposition we will relate the TCToptimality to the optimization of the average response time for the system. It is in this perspective that the TCT criterion provides a meaningful approach. Proposition 3: If the arrival process is independent of the assignment policy adopted and of the initial state, and a steadystate for the system exists, then

n(t) = number in the system at timet, ?r*

and we assume n,(t) = n,(T)

for every n,

i=l

is TCT-optimal

+ ?r* minimizes the long-run average response time for the system.

for everyt 2 T,

(i.e., we “turn off” the arrival process at time 7). Thus, C(T) is the area under the n(t) function when we consider only the arrivals that occurred by time T. (See Fig. 1.) The term total completion time used for C ( T ) can be intuitively justified by interpreting it as the sum of the times accumulated by each job in the system until all jobs arrived before time Tare completed. This criterion has been referred to, for example, in [6]. Since we should not expect any policy to be optimal for all classes of criteria, it is important to understand some of the properties of the different criteria which will affect the respective optimal policies. In what follows, we will discuss a few of such properties. Proposition I: x * is SO-optimal + ?r* is TCT-optimal. Proof: See Appendix I. Remark: The stochastic order optimality is indeed a very strong property and implies not only optimality in the sense of the other criterion discussed, but also in the sense of a

Proof: See Appendix 111. Thus, a TCT-optimal policy minimizes the average response time. In what follows, we will mainly be concerned with TCT-optimal policies. PROBLEM FOR A PARALLEL SYSTEM OF HI. THEJOBASSIGNMENT FCFS SERVERS: BASICRESULTS In this section, we present a brief survey of the results on the job assignment problem for FCFS parallel servers available in the literature. We first refer to the case of identical, constant speed servers. The Markovian model with Poisson arrival process and exponential service times has been first considered in [ 141, where the join-the-shortest-queue policy is proved to be optimal in the sense of stochastic order. In [12], a proof of stochastic order optimality for the JSQ policy is presented for the case of arbitrary arrival process and service time distributions with nondecreasing failure rate. The case of arbitrary arrival process and exponential service times is treated in [6]. In this work, it is proved that the JSQ policy

0

860

IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7, JULY 1990

TABLE I AVERAGE RESPONSE TIME( R )VERSUS ARRIVAL R A T E (A) FOR TWO-SERVER PARALLEL FCFS SYSTEM, WITH EXPONENTIAL A N D SERVICE DISTRIBUTION (1/ p = 1) INTERARRIVAL

X

+ U t

T

Fig. 2.

U

R

R

r*

Increment in total completion time A C ( T ) for an FCFS queue. 1.424

,

is optimal in the TCT sense. This result is in fact implied by Weber’s results (see the discussion presented in the previous section). The significance of this approach lies mainly in the proposal of the TCT criterion of optimality in this context. An interesting counterexample showing that the JSQ policy is not optimal in the sense of expected equilibrium response time for arbitrary service time distributions is provided by [13]. The selection of essentially a U-shaped service time distribution makes it possible to show how the queue length information for different servers can allow one to make inferences about the remaining service time for the jobs in service. Based on such inferences, it turns out that joining the shortest queue is, in some conditions, suboptimal, if the objective is the optimization of the average long-run job response time. In [ 3 ] ,the performance of two-server FCFS parallel systems with exponential arrival and service times under different assignment policies is compared. An extension of this work to the case of servers with nonidentical, constant speed, is presented in [4]. More recently Krishnan [lo]studied nonhomogeneous systems of FCFS parallel servers still under the assumption of Poisson arrival streams and exponential service time requirements. He proposes so defined “separable” policies which, although in general suboptimal, can, in many cases, outperform the JSQ policy. Finally, [8] studies the assignment problem for a two-server parallel system with quite general structure (including feedback). Before we conclude this section, a relevant property of FCFS parallel systems should be noted. Let us still consider the case of identical servers. Let Ui be the unfinished work present at server i at some time T. Then the response time RT for an incoming job, requiring r* units of service time, and assigned to server i at T, is given by Rf

=

Ui + r * .

(3.1)

In Fig. 2, we show the effect on the total completion time produced by the arrival of a new job at server i. Then it is easy to see that, in this case

AC(T)

C ( T ) - C ( T - ) = U; + r* = RT.

(3.2)

If the unfinished work U; is known at the arrival epoch of a new job for each i, then we can consider a policy T U which assigns the incoming job to server k if

Uk

=

min U;.

I

I

I

I

system, with the same number of servers. In fact, each job enters service at the same server and precisely at the same time in the two systems. As to be expected, policy T U provides a better average job response time than JSQ, as shown in Table I, for a two-server system with exponentially distributed interarrival and service times, where we compare simulation results for the JSQ to the analytical result available for the MIMI2 model. We note here that the error in the simulation results presented throughout this paper has been consistently maintained below 2% with confidence coefficient 0.95, and is very often below 1%, with the same confidence coefficient. For FCFS parallel systems the unfinished work at each server is thus a correct metric for server comparison when the objective of an assignment policy is the minimization of the average response time. IV. THEJOB ASSIGNMENT PROBLEM FOR A PARALLEL SYSTEM OF PROCESSOR SHARING SERVERS: EXPONENTIAL SERVICE REQUIREMENT DISTRIBUTION In the processor sharing service discipline (PS), introduced by Kleinrock [9]as a limit case of the round-robin discipline, all jobs in the system are simultaneously in service. When n jobs are in service, the work requirement of each job is being depleted at rate 1/ n . For exponentially distributed service requirements the state of the servers is completely determined by the number of jobs being served at each server. In what follows, we will discuss the TCT-optimality for the JSQ assignment discipline for the case of a PS parallel system with N servers, general interarrival distribution, and exponential service requirements. The proof is an extension of the proof provided in [6] for a system of two parallel FCFS servers. Let ni(t) be the number of jobs at server i at time t. Let the service time distributions be exponential with mean 1/ p . Customers arrive at times 0 < t l < t 2 < . . .T during interval [0,TI. At each time ti one of the servers must be selected for assignment of the newly arrived job. The problem is to find the assignment policy which minimizes, for all choices of T , E [ C ( T ) ]which , is given by N

i = l ,...s y

It is interesting to observe that the parallel FCFS system under policy T U is equivalent to a multiserver single FCFS queue

i=l

(4.1)

e

P

86 1

BONOMI: JOB ASSIGNMENT FOR PARALLEL SYSTEM OF QUEUES

where the last term determines the total completion time for the jobs present at time T, assuming no more arrival occurs after T. To see this, note that the first departure after Twill occur after an interval equal in expectation to 1/ p = (1 /np)(n), where the first term in the right-hand side is the expected length of the minimum of n exponential random variables with parameter p , while the second term is due to the fact that a PS server with n jobs provides service at rate 1/ n . Repeating a similar reasoning for all the successive interdeparture intervals it is immediate to justify the second sum in (4.1). Note that (4.1) is also valid for the case of FCFS servers. An intuitive reason for the similarity between the PS and the FCFS analyses is that, due to the memoryless property of the exponential distribution, all the jobs in service appear indistinguishable, despite their different attained service times. Thus, in the case we consider, a nonempty server, both FCFS and PS will produce interdeparture intervals which are exponentially distributed with parameter p . Thus. the exponential service requirement assumption allows us to carry through an analysis for the PS case which essentially only requires an extension to the case of N > 2 queues of the proof (valid for N = 2) presented in [6]. Since such an extension is straightforward, we will here state without proof the following theorem. Theorem 4.1: The JSQ policy is TCT-optimal for a system of N 2 2 PS parallel servers with general interarrival distribution and exponential service requirement. Remark: If the assumption on the arrival process is relaxed to that of a Poisson process, then the stronger optimality in the stochastic order sense can be proved to hold for the JSQ policy on a processor sharing system. This is due to the fact that in this case the stochastic processes describing the number of customers in the system under FCFS and PS disciplines are identical, as discussed above. As a consequence, the proofs available for the former discipline under the JSQ assignment policy are also appropriate for the latter. V. THEJOBASSIGNMENT PROBLEM FOR A PARALLEL SYSTEM OF PROCESSOR SHARING SERVERS: GENERAL SERVICE REQUIREMENT DISTRIBUTION

The special nature of the assignment problem for parallel PS servers becomes evident only when we consider the case of a general service requirement distribution. In this situation, the nonmemorylessness of the service distribution does not allow us to consider all jobs in service to be equivalent. The state of the parallel system of N processor sharing servers at time t is now characterized by the vector (5.1) with

where a ) ( [ )is the attained service for the jth of the n;(t)jobs in service at server i. A hint to the peculiar behavior of the PS parallel system is provided by the fact that Whitt’s counterexample [ 131, showing the nonoptimality of the JSQ for a case of a U-shaped

failure rate service distribution, does not apply to this case. It is in fact not possible here to gain information about the remaining service requirements for the jobs in service by looking at the numbers of jobs in the system as in the case of the FCFS system. When we consider PS parallel systems, however, some new and nontrivial questions arise. Given the state of the system, what should we estimate to determine the most favorable server, if we are trying to optimize a certain performance measure? For instance, is an estimate of the unfinished work at each server a parameter that can allow one to judge whether a server is a “good” candidate for assignment when we are interested in minimizing the average response time for the system? This was the case for FCFS parallel systems but it is not necessarily the case when the server discipline is PS, as we will show later. To clarify some of these issues we will consider the situation when, upon arrival of a new job, the information available includes the number of jobs at each server and the exact amount of the remaining service requirement for each job. Although in realistic situations such information is not commonly available, considering this idealized situation will allow us to gain insight into the basic underlying issues.

A . PS Assignment Problem with Perfect Information In this section, we consider the case of a system of processor sharing servers with Poisson arrivals and general service requirement distribution. The job assignment procedure can, however, be based on the exact knowledge of the remaining service requirement for all jobs present in the system. Being interested in policies which minimize the average job response time, we want to gain insight into possible TCToptimal policies. The information available about the servers at time t is now described by

S * ( t )= (Sl(t),

’ ‘ ’

,SN(t))

(54

with

s;(t>= (ni(t),r i ( t ) ,ri(t>,. . . ,rk,(t))

i = I , 2 , . . . ,N,

where

and r i ( t ) is the remaining service requirement of the kth job at server i, when the jobs are ordered in increasing remaining service requirement. For ease of notation, in what follows we will often omit specifying explicitly the dependence on t. Also, when it is clear that we are referring to a particular server, we will omit the superscripts identifying the server in question. Let C i ( T ) ,i = 1, 2, . . .N, be the total completion time for server i, when only the arrivals occurring up to time T are considered. Clearly N

C ( T )=

Ci(T). i=l

(5.3)

s

862

IEEE TRANSACTlONS ON COMPUTERS, VOL. 39, NO. 7, JULY 1990

"'"I

units of service. It is now possible to see that

C = d l +d2 + d ? + . . . +dn = rln

+r1 +r2(n

-

1)

+ + r2 + r3(n rl

-

2)

Fig. 3. Increment in total completion time A C ( T ) for a PS queue.

+: First, we will investigate the effect of the assignment at time t of the new job with service requirement r* to a PS server. We define

A ; ( t ) k C ; ( t )- C i ( t - ) .

1

+ r2 + r3 + r j ( n

-

j

+1)

(5.4)

Then we can prove the following result. Proposition 4: Let the state of a PS server just before the arrival to that server of a new job with service requirement r* at time t be given by

Let C * and C be the total completion times with and without the arrival of the new job, respectively, with no arrival after t (See Fig. 3 ) . Then

,

rl

(5.8) We now consider the total completion time C * ,where, besides the jobs present in the system at time t = 0, and described by the vector S above, we introduce a new job with service requirement r* . Then, by using (5.8) we can immediately write n+l

C* =

r1(2(n

+ 1 ) - 2i + 1 )

k=l

k

A P C * - C = 2 C r ; + r * ( 2 t ~ - 2 k + l ) (5.5) with i=l

r,!=ri where k = max {i: r; I r * } . Proof: Since a new arrival only modifies the curve of the number of jobs in the system as a function of time from the arrival instant on, we can as well assume the arrival time to be t = 0. Let d; and df be the ith departure epoch for the Also, server when the new arrival is not considered, and when it is considered, respectively. Then we can write

i r*

where d: is the new departure epoch for the job with remaining service requirement r, . Thus, A’ and A”’ are the total additional delays suffered by the jobs in the system with remaining service requirement smaller or equal to r * , and larger than r * , respectively. The delay through the system experienced by the new job is taken care of by the term A”. In this case, the first two terms in the expression of A “ define the component of such delay due to the presence of other jobs in the system, while the third is the actual service time received. Proposition 4 obviously suggests the idea of using A as a criterion for server selection when TCT-optimality is the concern. However, caution must be taken in this respect, since A does not directly consider the effect of future arrivals on the total completion time. Let us formulate a policy P A which, upon arrival of a new job, selects for assignment server k , with

Ak

=

min A; ...A

;=I,

where A; is the increment in total completion time that would be produced assigning the arriving job to server i, disregarding future arrivals. Policy T A is a myopic policy, since it optimizes total completion time over one period (i.e., between two successive arrivals). From the discussion given in this section it is clear how P A is not as much aiming at individual optimization as it is aiming at social optimization [ 111. However, in the context of processor sharing systems it seems that it may be more difficult to distinguish individual optimization from social optimization. In this respect, it is useful to compare the expressions for A’,

A”, and A”’ in (5.11). There, A”, the term which should relate to the individual optimization, contains terms which describe the effect of the new assignment on the jobs already in the system. Expression (5.5) can be used to derive some rules-of-thumb which can provide insight into the job assignment problem for parallel PS systems. As an example, assume that two servers have the same number of jobs being processed, and that the unfinished work at the two servers is also the same. Then, when assigning a new job to one of the servers, expression (5.5) suggests that it is better to select the server with the larger number of jobs that would leave the server before the completion of service for the job to be assigned. Next, as in the FCFS case, we will formulate a policy which compares servers on the basis of the unfinished work present at each server. Again, let us denote such a policy by T U . We define PU to be the (myopic) policy which, upon arrival of a new job, selects for assignment server k , with

with n,

U; =

Er; j=1

where, again, the dependence on t is left implicit. Ui is the unfinished work present at server i at the time of arrival of the new job. We recall that a similar policy would minimize the average response time in the case of a system of parallel FCFS servers. Also, it is clear how, for PS parallel systems, the unfinished work present at a server does not relate directly to the increment in total completion time produced by the assignment of a new job to that server. We are now ready to compare the three policies P A , T U , and JSQ on the basis of a simulation study of a system with two identical servers. As remarked above, the error in simulation results presented is consistently well below 2%, with confidence coefficient 0.95. In Tables 11, 111, and IV, we present the average response times of the P A , P ( I , and JSQ policies with varying job arrival rates, and, consequently, with varying levels of system utilization. The service distribution is assumed to be gamma with parameters CY = 0.1, CY = 1 (exponential distribution), and a = 4, respectively, and with the parameter /3 chosen to

I 864

IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7, JULY 1990

TA-BLE 111 RESPONSETIME(R)VERSUS ARRIVAL RATE(A) FOR AVERAGE TWO-SERVER PARALLEL PS SYSTEM, WITH EXPONENTIAL INTERARRIVAL AND SERVICE DISTRIBUTION (1/ p = 1)

TABLE V AVERAGE RESPONSE TIME( R ) VERSUS ARRIVAL RATE(A) FOR TWO-SERVER PARALLEL PS SYSTEM, WITH EXPONENTIAL INTERARRIVAL A N D DETERMINISTIC SERVICE TIME WITH UNITLENGTH

TABLE IV AVERAGF RESPONSE TIME(R)VERSUS ARRIVAL RATE(A) FOR Twr ’ .‘ER PARALLEL PS SYSTEM, WITH EXPONENTIAL &NTERARRIVALA N D GAMMA SERVICE DISTRIBUTION (ab = 1, CY = 4)

6

5.75 w

I t W v)

z

x v)

W

5.5

,.....*---.

(L

W

- ...........................................,.. *

(3

a

(L

W

> a

--- JSP - Tu ........ TA

5.25

5 0

I

1

I

2

I

3

I

4

I

5

I

6

I

7

8

I

I

I

9

1

(

SERVICE TIME VARIANCE

Fig. 5.

0

0

0.1

0.2 0.3 0.4 0.5 0.6 0.7 0.0 0.9 UTI L l Z A T l O N

Fig. 4. Average response time versus utilization for two-server PS parallel system. The service time distribution is gamma with parameter LY = 0.1 and unit mean.

always provide average service time of 1 time unit. The numerical results of Table I1 are shown graphically in Fig. 4. In Table V, the comparison is repeated by using a deterministic service time. The effect of the variance of the service distribution on the performance of the different algorithms is shown in Fig. 5 for a given value of system utilization (namely, per server utilization p = 0.9). The T A and JSQ policies do not seem to be sensitive to the variance of the service distribution. Thus, under such assignment policies, the independence of the av-

Average response time versus service time variance for two-server PS parallel system. The service time distribution is gamma.

erage response time of the usual single server PS systems on the variance of the service distribution is practically maintained when parallel systems are considered. However, the T U policy presents a response time curve which is increasing remarkably as a function of the variance of the service distribution. Note that, for the deterministic service time case, the decisions made by the T A and T U policies are identical. The results presented show how the T A policy always outperforms the JSQ policy, by offering an improvement in average response time of about 5%. What is relatively surprising is the poor performance offered by the T U policy, which, depending on the service distribution variance, can do remarkably worse than the JSQ policy. Thus, it seems that the T U policy uses the additional information about the job remaining service requirement in a counterproductive way, unless the variability of the service time distribution is very small. This phenomenon reveals a sharp difference in behavior of the parallel system of PS servers, as compared to the FCFS system, in which case T U provides an optimal assignment policy (see Section 111). It can be explained intuitively by noting that for PS systems the unfinished work does not directly capture the delaying effect on the incoming job due to the jobs already in the system.

c

7

865

BONOMI: JOB ASSIGNMENT FOR PARALLEL SYSTEM OF QUEUES

B . Hints Towards an Optimal Policy

,

6

Let us now return to the investigation of assignment policies for the case when the available information about the different servers is given by the state vectors of ( 5 . 1 ) , i.e., only the attained service for each job in the system is known. The simulation study presented in the previous section illustrates how, as expected, once perfect information about the state of the different servers is available, there are policies which provide noticeable improvement over the simple JSQ rule. One could thus reasonably expect to be able to identify assignment policies, which are based on the estimation of some function of the state of the system, and which outperform the JSQ rule in the case we are discussing. It is to be expected, however, that such policies will require some knowledge of the service time distribution for the parallel servers. Let us consider, for example, a policy T X which computes at each arrival instant t the conditional expected values for the increments Ai of (5.4),

A; = E [ A j I S ( t ) ]

i

= I,...,N,

(5.12)

and assigns the incoming job to the kth server, where

(ties might be resolved, for example, by an equiprobable random selection). A difficulty in this approach is that the evaluation of the Ai’s can be a very challenging task. In fact, it involves the determination of moments of the joint probability distribution for the ordered samples of a set of n generally nonidentical distributions. This problem is a generalization of the determination of the joint probability distribution for the order statistics. We can, however, consider simple approximations for the h i ’ s as follows. Let the state of server i be characterized by S

= (n,al,

a2,...,an)

where the time dependence is here implicit, and let ii * be the unconditional expected job service requirement. Then

5 W

z + 4 W v)

z

2

2Lz 3 w

:: E

> a

2

1

a

I

1

1

I

I

I

I

I

UTI LlZATlON

Fig. 6 . Average response time versus utilization for two-server PS parallel system. Service time distributon is discrete with unit mean and variance U2 = 5.464. TABLE VI AVERAGE RESPONSE TIME( R ) VERSUS ARRIVAL RATE(A) FOR TWO-SERVER PARALLEL PS SYSTEM, WITH EXPONENTIAL INTERARRIVAL AND TWO-POINT MASSSERVICE DISTRIBUTION WITH UNITMEANAND VARIANCE u2 = 5.464

11 1 1 1.136 1.476 2.518 5.742

1.127 1.501 2.721 6.253

1.122 1.443 2.465 5.680

We can also consider a policy T O , based on the estimation of the unfinished work at each server, given the state of the system, n,

k

hi s!Ai

=2

c Pi

+P ‘(2n

-

2k

+ 1)

(5.13)

Ui = E [ U i p ] = x E [ r , l a , ] i

=

l , . . . , N. (5.14)

j=1

i=l

Again, T O will assign the incoming job to the kth server, where

where PI

5 P2 5 i n

is the ordered set of conditional expected remaining service requirement given S i . Thus, P, =E[r,la,]

forj E [ l ,2 , . . . , n ] ,

with r j the residual service time given that the job has attained a , units of service, and k = max { i :

ri

5 P*}.

Let T A be the policy obtained by using the approximation (5.13).

In Fig. 6 and Table VI the average response time for the JSQ, T A , and T O policies are compared for the case of a discrete service time distribution with two probability masses (chosen for simplicity reasons), and for varying levels of system utilization. Policy T A performs uniformly better than the JSQ policy (but by a very small percentage). This result seems to confirm our suspicion that there exist assignment policies which provide better average response times than JSQ for the case of PS parallel systems with nonexponential service time distribution.

866

IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7. JULY 1990

TABLE VI1 PER SERVER UTILIZATION ( p ) , AVERAGE ~ S P O N S ETIME ( R ) AND AVERAGE RESPONSE TIMEFOR CLASS i (Ri , i = 1 , 2) VERSUS RATE(A) FOR TWO-SERVER PARALLEL PS ARRIVAL SYSTEM WITH EXPONENTIAL INTERARRIVAL AND SERVICE DISTRIBUTIONS JSQ

TU

1 1 :1 1 :!1 x

p

R,

R*

,134

2.104

,145

2.321

1.048

,199

3.405

1.888 ,7216

.338

6.188

R

,6560

2.0

.64

R

RA

x

8,

x2

,6496

,134

2.080

2.274

,7041

.145

2.255

,222

3.361

1.000

,200

3.222

.396

6.256

1.806

,338

5.878

R,

ii*

,6512

,135

2.083

,7113

.148

1.053

1.948

(1 = 0.1, 1= 2, Class Probability Distribution = (0.735, 0.265)) PI P2

Note that policy T O performs uniformly worse than JSQ, at least for this choice of the service time distribution, characterized by a large service time variance. The performance of policy T O can be expected to improve when we consider service time distributions with much smaller variance, and, in particular, when the service time is deterministic. In this last case, policy T O is the same as policies T U and T A . An important observation is that, when the service time distribution is assumed to be exponential, the three assignment policies discussed in this section lead to identical assignment decisions, and are thus equivalent. From the results shown it appears to be difficult to identify assignment policies which, at least under the assumptions we made (i.e., identical queues, single job class, etc.), provide sufficient performance improvement over the JSQ policy to justify practical interest. The question of whether under different assumptions we would have come to very different conclusions remains open. In the next section, we will offer some initial insight into the answer to some of these open questions by considering the case of nonhomogeneous systems and/or nonhomogeneousjob streams.

C . Some Observations for the Case of Nonhomogeneous Parallel Systems

to note how most of the average response time improvement produced by using the extra information on the job remaining service requirements is enjoyed by the jobs with longer service requirements. Little or no improvement is experienced by the shorter jobs. Intuitively this result can be explained by thinking that the knowledge of the number of jobs in service at the time of assignment of a new job provides accurate information about the service rate experienced by each job in a small interval around that time. For jobs that do not stay in the system for a long time this information is sufficient to determine a good assignment. The results for the simulation of a three-class system are presented in Table VIII, where we restrict our comparison to the more interesting policies JSQ and T A . Again, the JSQ policy seems to show a remarkable robustness with respect to the presence of nonhomogeneities in the arrival stream. Furthermore, in the area of multiprocessor systems, it is the average response time of the shorter jobs which is often specifically considered in evaluating the performance of the system. Thus, in view of practical applications of job assignment to multiprocessor systems, the results we just presented do not seem to encourage the implementation of the more complex algorithms discussed above. A comparison of job assignment policies for a system with two servers characterized by different speeds is presented in Table IX. The results show how the T A policy tends to utilize the system in a more balanced manner and provide an improvement in the average response times of the order of 5-6% over the JSQ policy. We must observe, however, that the policy T A does not make use of any information about server speeds. Obviously, it is possible to devise assignment policies using such information and providing remarkable improvements in performance over both JSQ and T A .

In this section, we will present some simulation results and some observations in reference to the job assignment problem for a parallel system of PS queues where more than one class of jobs is considered, and where the servers might be characterized by different speeds. We intend to investigate more thoroughly these issues in a forthcoming study. First we consider a system with two job classes and with two identical servers. The service requirement distribution is exponential for both classes, but the average service requirements VI. CONCLUDING REMARKS AND OPENISSUES are widely different. In Table VII, we compare the average response time for each class and the overall average response In this work, we presented an introductory study of the job time obtained by simulating the system under the JSQ, T A , assignment problem for a system of parallel PS servers with and T U policy (see Section V-A), respectively. It is interesting renewal arrivals.

0

867

BONOMI: JOB ASSIGNMENT FOR PARALLEL SYSTEM OF QUEUES

TABLE VI11

FERSERVER UTILIZATION ( p ) , AVERAGE RESPONSETIME(K)AND AVERAGE RESPONSETIMEFOR CLASSi ( R i , i = 1, 2, 3) VERSUS ARRIVAL RATE (A) FOR TWO-SERVER PARALLEL PS SYSTEM WITH EXPONENTIAL INTERARRIVAL AND SERVICE DISTRIBUTIONS

1;:;1 ;.;1 1.3

(-

1

.89

1.208

11.899

1

1.595

,149

1.205

11.441

1.997

,183

1.526

14.296

Lll;

,182 ,148

1.534

15.191

3.338

,273

2.455

24.380

3.172

,274

2.418

22.826

6.478

,503

4.761

47.484

5.948

.501

4.676

45.454

1 1 = 0.1, - = 1, - = 10, Class Probability Distribution = (0.6, 0.3, 0.1)) P2

PI

Ps

TABLE IX AVERAGE RESPONSE TIME( R ) AND UTILIZATION FOR SERVER i ( p i , i = 1 , 2) VERSUS ARRIVAL RATE(A) FOR TwoPS SYSTEM WITH EXPONENTIAL SERVER PARALLEL INTERARRIVAL AND SERVICE DISTRIBUTIONS, BUT DIFFERENT SERVER SPEEDS (s, = 1 , s2 = 2) JSQ

-

x

P1

Pz

,794

.304

.222

1.

,882

,480

1.5

1.058

2.

1.415

P1

PZ

,780

.30

.226

,356

.843

.470

,363

.640

,500

,992

,620

,510

,781

,663

1.323

,753

,675

.50

To compare the performance of different assignment policies, we chose to consider the expected total completion time as an optimality criterion, which implies the optimality in terms of average response times. When the service time and the interarrival time distributions are assumed exponential, the JSQ assignment policy can be proved to be optimal, even in the sense of stochastic order, for both PS and FCFS systems of parallel servers. However, when the service time distribution is not exponential, the PS system presents some characteristics which distinguish it from the FCFS system markedly. In terms of the job assignment problem, a major issue in the PS case is the comparison of servers given the system state. We presented a criterion which is suitable when the objective is the minimization of the expected total completion time, and, as a consequence, of the average response time through the system. Also, we showed how the use of the unfinishea work present at each server could lead to poor assignment policies for PS systems, while it results in an excellent assignment policy for the case of FCFS systems. The simulation study performed to compare the performances of different policies strongly supports the conclusion

0 0

4

2 3 SERVICE TIME VARIANCE

4

5

Fig. 7. Average response time versus service time variance for two-server parallel system. The service time distribution is gamma. The assignment policy is JSQ.

that the JSQ policy is not optimal for nonexponential service time distributions. This seems to be true independently of the nature (e.g., nondecreasing, decreasing, etc.) of the failure rate function for the service time distribution which is not the case for the FCFS systems. An interesting phenomenon we noted is the almost independence of the average response time for a parallel PS system under the JSQ assignment policy on the variance of the service time distribution. This feature seems to extend a property of a single server PS system to the more general case of special parallel systems. It also provides another relevant difference in the behavior of PS systems as compared to FCFS systems, as shown in Fig. 7, where we compare the two systems under JSQ and with varying variance for the gamma distributed service time. A practical implication of this study is that the JSQ assign-

868

IEEE TRANSACTIONS ON COMPUTERS, VOL. 39, NO. 7,JULY 1990

ment policy is extremely robust with respect to the variance of the service requirement distribution and it is very difficult to improve on the performance of such policy in practical implementation of homogeneous parallel PS systems. Similar considerations seem to hold for more general situations, as suggested by the preliminary investigation of the assignment problem for nonhomogeneous systems with multiclass arrival streams discussed above. Many important issues concerning the assignment problem in a PS environment have only been superficially touched upon by our study. Among these we mention the rigorous proof of optimality results for the case of nonexponential service distributions, the treatment of more general arrival processes, and the behavior of nonhomogeneous and/or multiclass systems.

From (A-1) we have that 03

E,-[n(t)(s(O)= S I

=CP,-(n(t) 03

5 -p,(n(t)

?r*

= E,[n(t)ls(O)= s ]

E,*[C(T)Is(O)=SI =E,*

[ [

for everyt, r , s .

i T c n ( t ) d t l s ( 0 =s] ) l m n ( t ) d t l s ( 0 )=s]

T,

= min

{ t : n(s) = 0, for everys 2 tln,(s) = n,(T), for everys

P,*( n(t) 2 I Is(0) =s)

n(t) = 0

= P,.

(n,(t) - n(j(t)2 I Is(0) =s)

=

P,* ( n,(t) - n d t ) 2 I I & ( t ) = k,

fort

[

for every T , s and = k,

8

APPENDIX II

s(0) =s)P,.(n,(t) = kls(0) =s).

Now, if we assume that the arrival process is independent of the assignment policy adopted, then = k ( s ( 0 )=s)

= P(n,(t) = k)

T,

where we used Fubini’s Theorem once again.

k 21

P,*(n,(t) = kls(0) =s) = P,(n,(t)

r

I E,[n(t)Js(O) = s ] d t

= E , i m n ( t ) d t l s ( 0 )=s] = E,[C(T)Is(O)= s ]

s(0) =SIP,*( n,(t) = kls(0) =s)

, * ( n d ( t ) 5 k -Iln,(t)

2T},

2 T c , and, by Fubini’s Theorem,

= l m E , * [ n ( t ) ( s ( O= ) s]dt

k 21

=

where

I

=p

=s)

(‘4-2) Then, since (A-1) and, consequently, (A-2) are valid independently of the arrival process, we have

=E,* is SO-optimal we have

>+(O)

i=l

APPENDIX I

Proof of Proposition I : Since that

2 I(s(0)=s)

I=1

Proof of Proposition 2: For simplicity of exposition we that the system is initially empty. The will of more general initial conditions does not require any conceptual modification of the argument given below. We can write, using the notation introduced above,

for any?r, k,s.

Let us now consider the term

n.V-1

We note that the following relation between events holds

j(dj+l - d j )

-

{no(t>= k } ( = ) { t E [ t k ,

j=l

fk+l)},

with t k the kth arrival epoch. Then, by using this consideration, it is immediate to conclude, by Definition 1, that

n,(T)-l

P,*(nd(t) > k -lln,(t) = k , s ( O ) =s)

L P,(nd(t) > k -Iln,(t) = k , s ( O ) =s) for every?r,s, k 21. But then we have

P,*( n ( t ) 2 IJs(0)=s) 5 P,(n(t)

2 Ik(0) =s)

for all?r,s, t andl.

Where aj and d j are the time of thejth arrival and departure, respectively. Also, since T , = dn,(T),

(A-1)

?

869

BoNOM1: 1 0 8 ASSIGNMENT FOR PARALLEL SYSTEM OF QUEUES

Since we assumed the arrival process to be independent of the assignment policy adopted, then

-

minE,[C(T)] = minE,

E] dj

-E

[: ]

Thanks are also due to the anonymous reviewers, whose dedicated work detected several imprecisions, and thus remarlebly improved the quality of this paper. REFERENCES

ai

It is now immediate to conclude the equivalence of problem w P I and Pz of Proposition 2. APPENDIX IU

[I]

121

[3]

Proof of Proposition 3: Define [4] I.

;=I

where dj - a ; is the response’time for the ith job to leave the system, d; and ai being the departure and arrival epochs for such a job, respectively. By Proposition 2 and the assumptions of Proposition 3 we have that

=Er(Rn)

[5]

[6]

D. Bertsekas, ”Dynamic behavior of shortest path routing algorithms for communication networks,” IEEE Trans. Auromor. Conrr.. vol. AC-27, pp. 60-74, 1982. R. M. Bryant and R. A. Finkel, “A stable distributed scheduling algorithm:’ in Pmc. 2nd In(. Con$. Disrribured Compur. Sysl.. 1981, pp. 314-323. Y. C. Chow and W. H. Kohler, “Dynamic load balancing in homcgeneous two-processor distributed systems.’’ Compur. Perform., K. M . Chandy and M. Reiser, Eds. New Yprk: North-Holland. 1977, pp. 39-52, Y. C. Chow and.W. Kohler, “Modgla oi dynamic load balancing in a heterogeneous multiple process& sysiem,” IEEE ”S.Compul.. vol. C-28, no. 5, pp, 354-361, May 1979. D. L.Eaget, E.D. Lazowslta. and]. Zahorjan, “Dynamic load sharing in homogeneous dislributed systems.” IEEE Trans. Soflware Eng., vol. SE-12, no. 5, pp. 354-361. May 1986. A. Ephremides, P.Varaya, and 1. Walrand, “A simple dynamic routing problem,”IEEE 7hm. Auromal. Conlr., vol. AC-25, pp. 690-693.

iwn

G. Foschini and J. Salz, “A basic dynamic routing problem and diffusion,” IEEE Ilnns. Commun., vol. COM-26. pp. 690-693, 1978. B. Hajek. “Optimal control of two interacting service stations,” IEEE Ilnonr. Auromal. Conrr., vol. AC-29. pp. 491499, 1984. L. Kleinrock, “Analysis of time-shared systcms,” Nova1 Res.Logisl. Quarrerly. vol. 11. pp. 59-73, 1964. K. R. Krishnan. “Joining the right queue: A Markov decision-rule,” in PKX. 26rh Con$. Daosopm’Conlr., Los Angeles. CA, Dec. 1987. pp. 1863-1868. s. Stidham, Jr., “Optimal control of admission to queueing systems,” IEEE “E.Aufomol. Conrr., vol. AC-30, no. 6, pp. 705-713, ~~

1985.

where x* is a TCT-optimal policy. If the system is stable, by ergodicity

R = n-m lim R .

exists and is a constant.

Then, by Fubini’s Theorem, since R , 2 0 for every n, n-m

n-m

R. W. Weber, “On optimal assignment of customers to pardel sewers,” 1. Appl. Pmb., vol. 15, pp. 4 0 6 4 1 3 , 1978. W. Whin, “Deciding which queue to join: Some counterexamples,” Oper. Res.,vol. 34, pp. 406-413. 1986. W. Winston, “Optimalily of the shortest line discipline,” J. Appl. Pmb., pp. 181-189, 1977. T. Yum and M. Sehwartz, “The join-biased-queue d e and its applications to routine in cam” communication networks.” IEEE hmr.

n-m

= E,(R) = R ,

where the subscript T implies that assignment policy T is being used, and, of course, we need A* and A to make the system w stable. ACKNOWLEDGMENT

We are sincerely grateful to W. Whitt, whose insights have been sustaining much of this work, and Y. T. Wang, whose encouragements and observations have been precious.

mavia nomi mi, ( ~ ‘ 8 3 - ~ . 8 5 )received the laurea in electrical engineering from Pavia University, Italy, in 1978 and the M.E. and Ph.D. degrees in electrical engineering from Comell University, Ithaca. NY, in 1981 and 1985, respectivcly. Since I985 he has been with thc Deparlment of Performance Analysis, AT&T Bell laboratories, Holmdel. NI. His current interests are in the areas of mathematical modeling, analysis, and engineering of computer and communication systems.