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

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

2009-03-03

arxiv.org/abs/0903.0604v1

Computer Science

Networking and Internet Architecture

Long version of preprint to appear in the IEEE Transactions on Networking

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Stability Region and Delay Performance of Linear-Memory Randomized Scheduling for Time-Varying Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Stability Region and Delay Performance of Linear-Memory Randomized Scheduling for Time-Varying Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Stability Region and Delay Performance of Linear-Memory Randomized Scheduling for Time-Varying Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-653945