Randomized Scheduling Algorithm for Queueing Networks

Details Randomized Scheduling Algorithm for Queueing Networks Randomized Scheduling Algorithm for Queueing Networks

2009-08-25

arxiv.org/abs/0908.3670v2

Computer Science

Information Theory

Scientific paper

There has recently been considerable interest in design of low-complexity, myopic, distributed and stable scheduling policies for constrained queueing network models that arise in the context of emerging communication networks. Here, we consider two representative models. One, a model for the collection of wireless nodes communicating through a shared medium, that represents randomly varying number of packets in the queues at the nodes of networks. Two, a buffered circuit switched network model for an optical core of future Internet, to capture the randomness in calls or flows present in the network. The maximum weight scheduling policy proposed by Tassiulas and Ephremide in 1992 leads to a myopic and stable policy for the packet-level wireless network model. But computationally it is very expensive (NP-hard) and centralized. It is not applicable to the buffered circuit switched network due to the requirement of non-premption of the calls in the service. As the main contribution of this paper, we present a stable scheduling algorithm for both of these models. The algorithm is myopic, distributed and performs few logical operations at each node per unit time.

Affiliated with

Also associated with

No associations

Rating

Randomized Scheduling Algorithm for Queueing 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 Randomized Scheduling Algorithm for Queueing Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Scheduling Algorithm for Queueing Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-233672