On Stability Region and Delay Performance of Linear-Memory Randomized Scheduling for Time-Varying Networks
| Autor: | Lotfinezhad, Mahdi, Liang, Ben, Sousa, Elvino S. |
|---|---|
| Rok vydání: | 2009 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/TNET.2009.2017742 |
| Popis: | 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, we 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, we study the performance of LM-RSP in terms of its stability region and average delay. Specifically, we show that LM-RSP can stabilize a fraction of the capacity region. Our analysis characterizes this fraction as well as the average delay as a function of channel variations and the efficiency of LM-RSP in choosing an appropriate schedule vector. Applying these results to a class of Markovian channels, we provide explicit results on the stability region and delay performance of LM-RSP. Comment: Long version of preprint to appear in the IEEE Transactions on Networking |
| Databáze: | arXiv |
| Externí odkaz: |
|