Utility Optimal Scheduling in Processing Networks

Details Utility Optimal Scheduling in Processing Networks Utility Optimal Scheduling in Processing Networks

2010-10-09

arxiv.org/abs/1010.1862v1

Mathematics

Optimization and Control

Scientific paper

We consider the problem of utility optimal scheduling in general \emph{processing networks} with random arrivals and network conditions. These are generalizations of traditional data networks where commodities in one or more queues can be combined to produce new commodities that are delivered to other parts of the network. This can be used to model problems such as in-network data fusion, stream processing, and grid computing. Scheduling actions are complicated by the \emph{underflow problem} that arises when some queues with required components go empty. In this paper, we develop the Perturbed Max-Weight algorithm (PMW) to achieve optimal utility. The idea of PMW is to perturb the weights used by the usual Max-Weight algorithm to ``push'' queue levels towards non-zero values (avoiding underflows). We show that when the perturbations are carefully chosen, PMW is able to achieve a utility that is within $O(1/V)$ of the optimal value for any $V\geq1$, while ensuring an average network backlog of $O(V)$.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-221281