DYNAMIC SERVER ALLOCATION TO PARALLEL QUEUES WITH RANDOMLY VARYING CONNECTIVITY

Consider N parallel queues competing for the attention of a single server. At each time slot each queue may be connected to the server or not depending on the value of a binary random variable, the connectivity variable. The server is allocated to one of the connected queues at each slot; the allocation decision is based on the connectivity information and on the lengths of the connected queues only. At the end of each slot, service may be completed with a given fixed probability. Such a queueing model is appropriate for some communication networks with changing topology (radio networks with mobile users, or networks with variable links such as meteor-burst communication channels). In the case of infinite buffers, necessary and sufficient conditions are obtained for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected queue stabilizes the system when the stabilizability conditions hold. The same policy minimizes the delay for the special case of symmetric queues (i.e., queues with equal arrival, service, and connectivity statistics) is provided. In a system with a single buffer per queue, an allocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical.