DYNAMIC SERVER ALLOCATION TO PARALLEL QUEUES WITH RANDOMLY VARYING CONNECTIVITY

Consider N parallel queues competing for the attention of a single ser ver. At each time slot each queue may be connected to the server or no t depending on the value of a binary random variable, the connectivity variable. The server is allocated to one of the connected queues at e ach slot; the allocation decision is based on the connectivity informa tion and on the lengths of the connected queues only. At the end of ea ch 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 ca se of infinite buffers, necessary and sufficient conditions are obtain ed for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected qu eue stabilizes the system when the stabilizability conditions hold. Th e same policy minimizes the delay for the special case of symmetric qu eues (i.e., queues with equal arrival, service, and connectivity stati stics) is provided. In a system with a single buffer per queue, an all ocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical.