On Stability Region and Delay Performance of Linear-Memory Randomized Scheduling for Time-Varying Networks

Free registration required

Executive Summary

Throughput optimal scheduling policies in general require the solution of a complex and often NP-hard optimization problem. Related literature has shown that in the context of time-varying channels, randomized scheduling policies can be employed to reduce the complexity of the optimization problem but at the expense of a memory requirement that is exponential in the number of data flows. In this paper, the authors consider a Linear-Memory Randomized Scheduling Policy (LM-RSP) that is based on a pick-and-compare principle in a time-varying network with N one-hop data flows. For general ergodic channel processes, they study the performance of LM-RSP in terms of its stability region and average delay.

  • Format: PDF
  • Size: 386.45 KB