We model a single-hop mobile network under centralized control with N service classes as a system of N weighted cost parallel queues with M~1 Յ M Ͻ N ! servers, arrivals, varying binary connectivity, and Bernoulli service success at each queue+ We consider scheduling problems in this system and, under various assumptions on arrivals and connectivity, derive conditions sufficient, but not necessary, to guarantee the optimality of an index policy+ Consider a system of N mobiles communicating in discrete-time with a central network controller~e+g+, base station or satellite! that has M channels for message communication+ At each time slot, each mobile transmits a short control pulse~mes-sage! to the controller; the control message contains information about the type and number of data messages the mobile wants to send to the controller+ If the control message is received by the controller, the mobile is connected to the controller for *This research was supported in part by ARO grant DAAH04-96-1-0377 and AFOSR grants F49620-96-1-0028 and F49620-98-1-0370+ Probability in the Engineering and Informational Sciences, 14, 2000, 259-297+ 259 that time slot+ Hence, the controller knows at each time slot the mobiles that are connected to it, and the type and amount of information each mobile has to transmit+ Based on this information, the controller must decide how to dynamically allocate its channels over time so that it can minimize the expected discounted weighted flowtime associated with the transmission of messages+ We formulate an abstract problem that captures essential features of the singlehop network described above, and analyze several variants of that problem+ The general abstract problem can be described as follows+ We consider a discrete-time model of N queues served by M servers~M Ͻ N !+ At each time, at most one server can serve a queue+ At each time, a queue is either available to be served by any server~connected! or it is not~not connected!+ At each time, before the allocation of servers, the connectivity of all the queues is known for that time+ We allow for arrivals at each queue at each time, and arrivals at a given time are assumed to occur before server allocation at that time+ The statistics of the connectivity and arrival processes are assumed arbitrary+ When a server has been allocated to a connected queue, there is a probability, fixed for each queue, that the service is successful+ This service success process is i+i+d+ and independent among queues, although the success probability can be queue dependent+ We wish to determine a server allocation policy p which minimizes where F 0 summarizes all information available at the beginning of the allocation period+ C p is the cost under p, given by b is the discount factor, T is the finite horizon, c i is the holding cost of queue i~Q i !, by which we distinguish service class, and x t i is the length of Q i at time t+ In Problem~P! we have assumed that the horizon T is finite+ We first analyze Problem~P! and its refinements as finite horizon problems, and then show that the results of the analysis hold for the corresponding infinite horizon problems+ As mentioned, the model described in Problem~P! arises in the context of single-hop mobile radio networks, which can be modeled as a bank of message queues served by one or more communication channels+ The varying connectivity relates to a variety of mobile communication systems, such as cellular and mobile packet radio networks @10#, satellite communications @3#, and meteor-burst channels @4#+ The cost function then reflects the penalty for keeping packets waiting in each queue, and the queue weighting allows for a prioritization of packets for transmission+ The same model arises in image formation systems, where service decisions correspond to sensor allocations for specific surveillance areas for information-gathering purposes+ The model also has independent interest as a specific problem in queueing theory+ C. Lott and D. Teneketzis In @2,13#, the problem of N queues with different holding costs and one server with full connectivity was considered, and the simple cµ rule was shown to be optimal, but this result does not generalize to Problem~P!+ Our model is similar to that in @10#, but only a single server and no differentiated service are considered in that article+ The authors of @10# prove that the Longest Connected Queue~LCQ! policy is optimal+ The authors of @1# and @12# use similar but more general models than @10#, which also do not include differentiated service+ All three references determine policies that maximize throughput over an infinite horizon+ Throughput maximization over an infinite horizon leads to a family of scheduling policies, not all of which maximize throughput over a finite horizon+ Furthermore, throughput maximization is not the most appropriate performance criterion for networks providing multiple classes of service+ In @14#, the authors determine an optimal control policy for a non-Markovian M-server M-queue system in the presence of a continuous-time-varying external disturbance process, where control decisions occur only at fixed epochs and where service at a queue might interfere with service at other queues+ Optimality is defined in a maximal throughput sense and is proved using stability arguments+ The authors of @3# study a model of satellite network connectivity which, on the surface, seems similar to @10#+ However, by focusing on the question of server preemption, their model, and hence the nature of the optimal policy, is actually quite different+ A class of optimal adaptive policies for the model of @3# is proposed in @11#+ Again, this work does not incorporate multiple service classes+ To analyze meteor-burst communications, a discrete-time Markov chain model is proposed in @4# for the varying communications medium+ In @5#, a careful analysis of a single-server single-queue system is performed, where the server alternates between being "on" and "off+" In @4,5#, the goal is the analysis of detailed queue attributes under a fixed service policy, and questions of determining an optimal server allocation policy in a queueing network do not arise+ There are problems related to Problem~P!~e+g+, see @9# and the references therein!, where each of N queues has its own server and a controller must decide how to route arriving packets to the set of queues+ The structure of these problems leads to somewhat different solutions, such as in @9# where packet type is not distinguished and the queues have finite capacity+ The model of this article can be considered a special case of a restless multiarmed bandit, in the sense of @16#, where state transitions and rewards take on a particular structure+ The general restless bandit problem, where the number of arms and processors is infinite and their ratio is fixed, was investigated in @16# and @15#+ The results of @16# and @15# do not apply here, as the number of arms~queues! and processors is finite+ The system stability0maximal throughput approach used in much of the work just discussed implicitly assumes that all jobs are identical+ This implies that the control problem consists entirely in keeping the server~s! busy as much as possible+ Hence, optimal policies are those which keep the queues load balanced+ This situation changes when we allow jobs to have different service classes+ For example, for the case of a full-connectivity multiserver system with different hold- ing costs, it is easy to construct an example where the longest connected queue protocol is not optimal+ We can similarly construct an example demonstrating that the index policy is not optimal for a single-server varying connectivity system with different holding costs+ To the best of our knowledge, no results are presently available for the multiserver scheduling of parallel queues with connectivity constraints and multiple service classes+ In this article, we investigate an instance of multiserver scheduling of parallel queues with connectivity constraints and multiple service classes+ The main contribution of the article is the determination of conditions on job~message! weighting and job service times sufficient to guarantee the optimality of an index policy for Problem~P!+ We show by example that the above mentioned conditions are not necessary to ensure the optimality of the index policy+ The article is organized as follows+ In Section 2, Problem~P! is analyzed; a condition sufficient to guarantee the optimality of an index policy is presented+ In Section 3, various refinements to Problem~P!, including more specific assumptions on the arrival and connectivity processes, are considered+ These refinements allow for improved conditions which are still sufficient to guarantee optimality of the same index policy+ Section 4 contains a brief discussion of the infinite horizon problem and Section 5 summarizes the article+ Finally, Appendices A-F provide detailed proofs of some technical statements in the main body of text, not included there to improve the flow of the basic arguments+ To proceed with the analysis, we need the following definitions and notation+ N The number of queues+ M The number of servers+ T The length of the finite time horizon+ The cost RV associated with policy p, as defined in~2!+ By an index policy, we mean any policy which attaches a fixed numeric index to each queue and then plays the M connected and nonempty queues of highest index at each time+ The index of a queue refers to this numeric index, and not the queue's subscript+ As stated in Problem~P!, we wish to find an allocation policy p which minimizes J T p , defined in~1! as To achieve this, we need~1! a result that describes the effect of the initial condition on the performance of any index policy p and~2! an expression that specifies the difference in performance between any two policies, say J p and [ p, under the same initial condition+ We begin with the result that describes the effect of the initial condition on the performance of any index policy p+  Proof: First, note that if x 0 i ϭ 0, we have x 0 ϭ x 0 iϪ , and then the lemma is clearly true+ We henceforth assume x 0 i . 0, so that x 0 x 0 iϪ , and proceed by induction on T+ First, we define the following events: A1! At t ϭ1, the same queues are being served by our index policy p under x 0 and x 0 iϪ + A2! At t ϭ 1, M Ϫ 1 of the servers are allocated to the same queues by policy p under x 0 and x 0 iϪ ; the Mth server is allocated to Q i under x 0 and to Q j under x 0 iϪ , where Q j is of lower index than Q i + Because p is an index policy, a service difference occurs at t ϭ 1 only when x 0 i ϭ 1, p allocates to Q i under x 0 , and, under x 0 iϪ , p allocates to Q j , a queue of lower priority than Q i , instead of the empty Q i + Hence, events~A1! and~A2! partition the space of possible events+ We now proceed with the induction+ Let T ϭ 1+ Under~A1!, the cost difference is 1 For RVs x and y, event A, and s-field F, we define E @y6A, x, F # to mean E @y6A പ s~x! ∨ F #+ Under~A2!, the cost difference is because service success is assumed i+i+d+ and independent among queues+ From~5! and~6!, the induction basis step is established+ Now, assume~4! holds for an arbitrary T and consider the case of a T ϩ 1 horizon, labeling time so that the theorem is true over 2, + + + ,T ϩ1+ Then, under~A1!, we have because service success in both cases is the same+ By the induction hypothesis, Under~A2!, again since service is i+i+d+ and independent among queues, we find that where x 1 is the state resulting from x 0 when no service completion is achieved at t ϭ 1 at Q i and Q j + By the induction hypothesis, and by applying the induction hypothesis twice in succession, we get Combining~10!-~13!, we obtain Because A1 and A2 are a partition of all possibilities arising from the allocation of the M servers under the two different initial conditions~under the same index policy!,~9! and~14! imply that and the induction step is proved+ Hence the proof of Lemma 1 is complete+ Ⅲ Next, we derive an expression that specifies the difference in performance between any two policies J p and [ p under the same initial condition+ Earlier, we have defined C [ p to be the cost RV under [ p and C J p to be the cost RV under J p+ We now define R to be the difference To show J p optimal, it suffices to prove that for any other allocation policy [ p+ To prove~16!, consider two given policies [ p and J p and assume that at t ϭ1, they both run on the same system and that both Q i and Q j are connected and nonempty at this time+ Assume J p chooses Q i and not Q j , and [ p chooses Q j and not Q i at t ϭ1, and further assume that all other server allocations are the same for the two policies at t ϭ 1+ Recall that h t i is the service success indicator variable at time t for Q i + We then have where the last equality follows because service success is i+i+d+ and independent among queues and independent of all arrivals and connectivities+ We use~17! to prove the main result of this section, which is given by the following theorem+  Discussion: The essence of the result of Theorem 1 is the following: If we were guaranteed that the system described in Problem~P! operated away from the boundary all the time~i+e+, if the queues were continuously nonempty!, then it would be optimal to always allocate the M servers to the queues with the M highest indices+ Near the boundary, server utilization~because of empty queues! becomes a critical issue in determining an optimal server allocation strategy+ The index policy, which allocates servers without taking into account the number of customers in the queues, may result in server underutilization; thus, it may not be optimal near the boundary+ Consequently, if we require optimality of the index policy for Problem~P!, we must identify conditions to ensure that the advantage gained by always allocating the servers to the highest-index queues overcompensates potential losses resulting from server underutilization near the boundary+ Such a condition is expressed by~18!, which requires that the indices associated with the queues be sufficiently separated from each other+ Such a separation results in a priority ordering of the queues sufficient to guarantee the optimality of the index rule+ It is interesting to compare this result with the case in which all queues have the same weighting+ Then~see @10,12#!, the optimal policy is to serve the connected queues of longest length~LCQ!+ The intuition here is that, at a given time, serving any queue gives the same expected return as serving any other, so the optimal server allocation is the one which optimizes the expected number of services over the horizon+ The LCQ policy accomplishes this by minimizing the number of empty queues, trying to avoid the situation where connected empty queues and disconnected nonempty queues reduce service possibility+ On the other hand, Theorem 1 demonstrates the complementary case in which queues have sufficient spacing in weighting, so by serving the costlier queues first, any server underutilization~inef-ficiency! is sufficiently compensated+ Between these two extremes, there is a region of queue cost such that these two competing goals conflict, and the optimal policy becomes quite difficult to specify+ Proof~Theorem 1!: Assume that the queues have been labeled such that~18! is satisfied+ Consider M additional queues in the system, numbered N ϩ1, N ϩ 2, + + + , Nϩ M, each with c Nϩi ϭ m Nϩi ϭ 0+ Condition~18! is still satisfied with these extra  because of~18! and the fact that~1 Ϫ b!0@1 Ϫ~1 Ϫ m i !b# Յ 1+ Repetition of the argument leading to~19! shows that the assertion of the theorem is true for T ϭ 1+ To proceed with the induction, we assume that the assertion of the theorem is true when the horizon is T and prove that the index policy described in the statement of the theorem is optimal when the horizon is T ϩ1+ Consider policies [ p and J p with the following features: p and J p allocate M Ϫ 1 of the servers to the same queues; the M th server is allocated to Q i by policy J p and to Q j by policy [ p, where i Ͻ j+ Without any loss of generality, we assume that i Ͻ N+ F2! From time t ϭ 2 on, policies J p and [ p follow the optimal allocation policy for the T-horizon problem+ We define Q ϩ :ϭ $the set of queues with indices larger than that of Q j %, Q Ϫ :ϭ $The set of queues with indices equal to or less than that of Q j %,  Using the characteristics of policies [ p and J p, the above definitions, and~28! and 29!, we proceed to complete the induction step by determining a lower bound on E @R6F 0 # at t ϭ 1+ To accomplish this, we examine separately each of the four terms appearing in the right-hand side of~17!+ We prove that Combining~17! and~30!-~33!, we obtain Because of~28! and~29!, The last inequality in~35! is true because service success at Q i under [ p is independent of the event Dh 1 i ϭ 1 as well as the initial information state F 0 , because service  Combining~34!-~36!, we obtain and because of~18!, Consequently, policy J p is superior to [ p for the~T ϩ1!-horizon problem+ Repetition of the argument leading to~38! shows that, under~18!, the index policy described in the statement of the theorem is optimal for the~T ϩ 1!-horizon problem+ To complete the proof of the induction step, we must prove~30!-~33!+ The proofs of these equations are located in Appendices A-D+ With~30!-~33!, the induction step is complete and the theorem is proved+ Ⅲ Remark: The interchange argument used to prove the optimality of the cm rule in @2# cannot be applied to the case of either multiserver or that of varying connectivity, because it is not possible to guarantee that such an interchange time occurs+ We present two examples to illustrate the role of Condition~18!+ The first example shows that if Condition~18! is not satisfied, the index policy is not, in general, optimal+ The second example shows that Condition~18! is not necessary to guarantee the optimality of the index policy+ Example 1: Let T ϭ 2, N ϭ 2, M ϭ1, m 1 ϭ m 2 ϭ1, x 0 1 ϭ x 0 2 ϭ 1, c 1 Ͼ c 2 ϭ 0+9c 1 , and b ϭ 0+5+ Assume there are no arrivals, and connectivity is i+i+d+ with q 1 ϭ 1 and q 2 ϭ 0+5+ Then, and From~39! and~40!, we conclude that Q 1 has the higher index, but Condition~18! of Theorem 1 is not satisfied+ Denote by J p the index policy~i+e+, the policy that gives priority to Q 1 when both queues are connected and nonempty!, and by [ p, the policy that gives priority to Q 2 when both queues are connected and nonempty+ Then, J p is nonoptimal, because in the case where both queues are initially connected, Example 2: Consider the same situation as in Example 1 with the one difference: c 2 ϭ 0+7c 1 + Then,~39! is valid and Condition~18! of Theorem 1 is not satisfied because Nevertheless, the index policy J p is optimal because The result of Theorem 1 can be graphically described for a system consisting of two queues~N ϭ 2! and one server~M ϭ1!+ The graphical description is based on the following summary of the result of Theorem 1 for this case+ When both queues are connected at a given time, If we consider c 2 m 2 fixed and imagine varying c 1 m 1 , then, because of~42! and~43!, the space of possible values of c 1 m 1 is divided into three regions~shown in Fig+ 1!: 1! Serve Q 1 when both queues are connected;~2! serve Q 2 when both queues are connected;~3! optimal policy is unspecified+ The third region exists because~42! and~43! do not cover all possibilities+ The intuition developed from this simple case extends naturally to the general case+ Note that as b r 0, the region in Figure 1 where the optimal policy is not specified becomes empty+ This is the situation where future cost has no effect on current decisions, and so the best policy minimizes cost at the current time step only+ For this case, the optimal policy is a greedy algorithm~i+e+, the cm rule!+ 270 C. Lott and D. Teneketzis Condition~18!, which is sufficient to ensure the optimality of the index policy for Problem~P!, was derived under no assumptions on the arrival and connectivity processes+ The result of Theorem 1 can be strengthened under explicit assumptions on the aforementioned processes+ In this section we examine several instances of Problem~P! that arise under various assumptions on the arrival and connectivity processes+ We show that Condition~18! can be improved when more information is given about the arrival and0or connectivity processes+ As a reminder, the assumption of i+i+d+ service holds throughout this section of the article+ We assume i+i+d+ queue connectivity, independent of the service success process, but leave arrivals arbitrary+ We do not require independence of the connectivity between queues, only i+i+d+ for any given queue, and independence of service success for all queues+ We prove the following variant of Theorem 1+ Proof: We assume~44! is satisfied and proceed by induction+ We show first that for T ϭ 1, the result of Theorem 2 is true under~44! and then that the induction step holds+ First, note that So if~44! is satisfied, then necessarily m i c i Ն m j c j + Then, for T ϭ 1, the proof of the result of the theorem is the same as in Theorem 1+ We proceed with the induction step+ First, note that the arguments leading tõ 34! do not depend on the specific form of~18!; hence, the same arguments are valid here as well+ So,~34! is true+ Define Just as for t 1 , we define t 3 ϭ T ϩ 1 whenever t 3 Ͼ T+ As earlier, we know that t 1 Ն t s a+s+, where t s is defined by~26!+ We also have that t s Ն t 3 a+s+, which follows directly from their definitions+ Furthermore, by its definition, the independence of service success, and the i+i+d+ nature of connectivity at Q i , t 3 is independent of other system processes+ We thus obtain Next, we compute the right-hand side of~46!: Because of~46! and~47!, 272 Combining~34! and~48!, Inequality~44! then implies DJ Ն 0, and the induction step is completed by arguments identical to those following~38! in the proof of Theorem 1+ Under the additional assumption of i+i+d+ connectivity, Theorem 2 provides an improved sufficiency condition over Theorem 1+ For fixed q i m i , just as earlier, b r 0 means a reversion of the cm rule+ The difference between the problem considered in this section and Problem~P! is that in the "sufficiency factor"~1Ϫb!0@1Ϫ~1Ϫm i !b#, describing the separation of indices in~18!, m i is replaced by q i m i + Therefore, the rate at which Q i can be served is reduced by both connectivity and service probability, and this leads to a condition that is weaker~i+e+, better! than~18! and is sufficient to guarantee the optimality of the index policy+ In contrast to Section 3+1, here we assume Bernoulli arrivals and arbitrary connectivity+ The arrivals do not need to be independent among queues+ We prove the following variant of Theorem 1+  Proof: We begin with~34! because the arguments leading to it are as in the proof of Theorem 1+ Assume~49! is satisfied and note that Then, necessarily ∀i, j, m i c i Ն m j c j + Then, for T ϭ 1, the assertion of the theorem can be established in the same way as in Theorem 1+ To prove the induction step, we begin with~34! and define the stopping times: Just as earlier, we define t 3 ϭ T ϩ 1 whenever t 3 Ͼ T, and similarly for t 4 + It is immediate that t 1 Ն t 3 a+s+ @t 1 is defined by~22!#, as a minimum requirement for t 1 ϭ t is that Q i be empty for J p and service is possible at t+ If an arrival just occurred, the queue cannot be empty+ Also from the definitions, it is immediate that t 3 Ն t 4 a+s+ Moreover, by its definition, the independence of service success, and the i+i+d+ nature of arrivals at Q i , t 4 is independent of other system processes+ Hence, we obtain Letting S a i ϭ1 Ϫ a i , the probability of no arrival, we obtain for the right-hand side of 52!, Because of~52! and~53!, 274 Combining~34! and~54!, we find that Condition~49! then implies DJ Ն 0, and the rest of the induction step follows as in Theorem 1+ Ⅲ In this section, we assume both Bernoulli queues connectivity and Bernoulli arrivals+ Then, we get the following condition sufficient to guarantee the optimality of an index policy+  Proof: We assume~55! is satisfied and note that Then, c i m i Ն c j m j , ∀i, j, i Ͻ j, and for T ϭ 1, the proof of Theorem 4 is the same as that of Theorem 1+ To establish the induction step, we note that the arguments leading to~34! are the same as in Theorem 1 and define the stopping time t 5 ϭ min$t Ն 2: there is a service success and no arrival at Q i under [ p6Q i is always served when connected under [ p% and let t 5 ϭ T ϩ 1 whenever t 5 Ͼ T+ From the definitions, it follows that t 1 Ն t 5 a+s+ Note that for i+i+d+ arrivals and connectivity, the system is a Markov chain, and so F 0 information is summarized in x 0 ; from its definition, t 5 is independent of the initial state and service success at t ϭ 1+ Consequently, Letting S a i ϭ1 Ϫ a i , the probability of no arrival, we obtain for the right-hand side of 56!, Because of~56! and~57! and the Markovian property of the system, Combining~34! and~58!, we find Condition~55! then implies DJ Ն 0, and the rest of the induction step is the same as in Theorem 1+ We can improve the result of Theorem 4 by performing a more careful analysis of a first hitting time bound for t 1 + The resulting sufficient condition is more relaxed than~55!, but the expression describing the condition is more complicated and less intuitive+  and for any finite dimension L, define the L ϫ L matrix A i as then, at any time t, it is optimal to serve the M connected queues of highest index, or serve all queues if less than M are connected+ Further, the "sufficiency factor" is monotonic in the size of A i ; that is, Proof: The proof of Theorem 5 is given in Appendix E+ In this section, we drop the i+i+d+ assumption on arrivals and connectivity+ Under certain statistical assumptions on the arrival and connectivity processes, which are stated precisely in the following theorem, we derive a condition sufficient to guarantee the optimality of the index policy described in Section 2+ We show that this condition improves~18!+ Our results are summarized in the following theorem+  and if Q i is served at t+ Then, if there is a labeling of the queues such that and Condition~D1!, respectively, in @7#+ Condition~62! as well as Conditioñ D1! in @7# provide conditions on the drift of a process $x t , t Ն 0%; they differ in their requirements on the direction of the drift bound+ 2+ In general, it is difficult to explicitly specify the h i and r i which satisfy~64! and give the optimal condition in~65! and~66!, although they can be determined numerically+ 3+ As an example, from~65! we can achieve the condition of~18! when h i ϭ Ϫln b and r i ϭ10b Ϫ~10m i !@1 Ϫ~1 Ϫ m i !b#+ This gives a r i Ն 1 only when  which is easier to check and implies~64!+ However, there may be cases where~64! is satisfied and~67! is not+ We summarize the results in Table 1+ From the table, and from previous derivations, we observe that always and under certain conditions~E1! Յ~E6!+ The "sufficiency factors" that appear in the table indicate how much the indices of different queues must be separated from one another to guarantee that the index policy is optimal+ The above inequalities are intuitively pleasing because they show that as the statistical description of the sys- Arbitrary arrivals, arbitrary connectivity tem becomes more detailed, the sufficient conditions for the optimality of the index policy improve; that is, the additional statistical information about the system is used to reduce the separation among the queues' indices while the optimality of the index policy is maintained+ Comment: Note that the number of servers M never enters explicitly in the arguments of the proofs in Sections 2 and 3+ Therefore, we believe that even when the number of servers is a random function of time, the conditions sufficient to guarantee the optimality of the cm rule for the channel allocation problem described in this article are the same as those shown in Table 1+ 4. INFINITE HORIZON The index policy described in Section 2 is optimal for all finite-horizon problems under the conditions of Theorems 1-6+ Because the conditions of these theorems do not depend on the horizon T, one can prove by a simple contradiction argument that the same index policy is optimal for the corresponding infinite horizon problems under the same conditions+ We have shown that there are conditions on system parameters which guarantee the optimality of an index policy for the N-queue M-server system with arrivals and varying connectivity+ These conditions depend on the statistical assumptions made for the problem, as well as the value of key system parameters, such as arrival rate, connection probability, and service probability+ The interest in this problem arises from its applicability to several important systems, including mobile communication networks under centralized control and image formation systems+
In REF , the problem of multichannel allocation in single-hop mobile networks with multiple service classes was formulated as an RMAB, and sufficient conditions for the optimality of a myopictype index policy were established.
2000), ‘On the Optimality of An Index Rule in Multichannel Allocation for Single-Hop Mobile Networks with Multiple Service Classes
Probability in the Engineering and Informational Sciences
Mathematics