The value of preemption and observability in time-varying channels

We study the problem of scheduling packets on communication channels whose service availability is modeled by independent Gilbert–Elliot (ON,OFF) Markov chains. Classical models assume that channel states are always known to the scheduler and that transmission is perfect for ON channels. We consider the often more realistic problem of non-preemptive scheduling on imperfect and unobservable channels. In particular, in our model, ON channels have a nonzero probability of unsuccessful transmission, the state of the channel is only observed upon successful transmission, and once a channel is activated, it must remain active until successful transmission. We give conditions under which simple policies are optimal. We also investigate the performance impact of not being able to preempt and of not having access to channel information. Combining known and novel results, we characterize the “Preemption Gain” and “Observability Gain.” Numerically, we show that these gains can be significant, highlighting the critical value of channel state information and preemption, and providing insight into the possible benefit of redesigning systems to permit preemption and/or to provide state information in communication channels.