  We consider a server serving a time-slotted queued system of multiple
packet-based flows, with exogenous packet arrivals and time-varying service
rates. At each time, the server can observe instantaneous service rates for
only a subset of flows (from within a fixed collection of observable subsets)
before scheduling a flow in the subset for service. We are interested in
queue-length aware scheduling to keep the queues short, and develop scheduling
algorithms that use only partial service rate information from subsets of
channels to minimize the likelihood of queue overflow in the system.
Specifically, we present a new joint subset-sampling and scheduling algorithm
called Max-Exp that uses only the current queue lengths to pick a subset of
flows, and subsequently schedules a flow using the Exponential rule. When the
collection of observable subsets is disjoint, we show that Max-Exp achieves the
best exponential decay rate, among all scheduling algorithms using partial
information, of the tail of the longest queue in the system. Towards this, we
employ novel analytical techniques for studying the performance of scheduling
algorithms using partial state, which may be of independent interest. These
include new sample-path large deviations results for processes obtained by
non-random, predictable sampling of sequences of independent and identically
distributed random variables. A consequence of these results is that scheduling
with partial state information yields a rate function significantly different
from scheduling with full channel information. In the special case when the
observable subsets are singleton flows, i.e., when there is effectively no a
priori channel-state information, Max-Exp reduces to simply serving the flow
with the longest queue; thus, our results show that to always serve the longest
queue in the absence of any channel-state information is large-deviations
optimal.
