Whittle indexability in egalitarian processor sharing systems

Vivek S. Borkar, Sarath Pattathil

TL;DR

This paper tackles the challenge of optimally allocating resources in egalitarian processor sharing systems, a complex problem that can be modeled as a "restless bandit" problem. The authors establish that these systems are "Whittle indexable," meaning an efficient, near-optimal policy can be derived using a specific index-based approach. They also provide a numerical method to compute these indices and validate it with experiments.

What Problem Does This Paper Address?

Processor sharing systems, where multiple users share a single server's processing power, are fundamental to modern computing. The "egalitarian" model aims to distribute this power equally among active users. However, managing these systems efficiently, especially when jobs have varying costs and arrival rates, is a significant challenge. Traditional approaches struggle with the complexity of dynamic job arrivals and departures, and the fact that service rates can decrease as more jobs join the queue. This paper frames this problem as a "restless bandit" scenario, a type of sequential decision-making problem where actions (serving a job) have ongoing consequences. The core challenge is to find a policy that minimizes the long-run average cost, balancing the cost of holding jobs with the cost of processing them, while dealing with the inherent uncertainty of arrivals and departures.

Methods

The paper's main contribution is establishing Whittle indexability for egalitarian processor sharing systems. This means they show that an optimal policy can be constructed by calculating a "Whittle index" for each job/queue. This index essentially represents the value of activating a particular server for a job. The authors achieve this by:

  1. Modeling as a Restless Bandit: They map the processor sharing system to a restless bandit problem, where each queue is an arm of the bandit. The decision is whether to "pull" an arm (serve a job) or not.
  2. Lagrangian Relaxation: To handle the constraint of serving only one job at a time (or rather, activating only one server at a time), they use a Lagrangian relaxation technique. This transforms the constrained problem into a series of unconstrained individual control problems, each parameterized by a Lagrange multiplier (which they interpret as a "negative subsidy" or "tax" for inactivity).
  3. Dynamic Programming: They derive the dynamic programming equations for these individual problems.
  4. Structural Properties: They analyze the structural properties of the value functions associated with these problems, proving that the optimal policy for each individual problem is a threshold policy. This means there's a cutoff point: if the number of jobs in a queue is below the threshold, the server is activated; otherwise, it remains passive.
  5. Whittle Indexability Proof: Based on the threshold policy and the behavior of the value functions as the Lagrange multiplier changes, they prove Whittle indexability. This implies that the threshold (and thus the optimal policy) changes monotonically with the "subsidy" (or index value).
  6. Numerical Scheme: They propose an iterative numerical scheme to compute the Whittle indices, which is crucial for practical implementation.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and simulation-based experiments rather than using pre-existing datasets.

Key Insights and Ideas

  • Egalitarian Processor Sharing as a Restless Bandit: This is a novel framing that allows leveraging powerful existing theory from restless bandit problems.
  • Whittle Indexability is Key: The core insight is that these complex systems exhibit Whittle indexability. This is a significant result because Whittle index policies are known to be asymptotically optimal (and often near-optimal in practice) for restless bandits, offering a computationally tractable alternative to finding the true optimal policy.
  • Threshold Policies Emerge Naturally: The analysis reveals that optimal control for individual queues under this framework leads to simple threshold policies, making the decision-making process intuitive.
  • The "Negative Subsidy" Interpretation: The Lagrange multiplier's role as a "negative subsidy" for inactivity provides a useful economic interpretation for the Whittle index, linking it to the cost of keeping a server idle.

Key Results

  • Whittle Indexability Established: The paper formally proves that egalitarian processor sharing systems, under the specified model, are Whittle indexable.
  • Numerical Scheme Developed: A practical, iterative algorithm is presented for computing the Whittle indices.
  • Experimental Validation: Numerical experiments demonstrate that the Whittle index policy performs very well, achieving costs close to the optimal (or a lower bound) even for a small number of servers, and significantly outperforming simpler heuristics like the "Cμ rule" and random allocation. The paper shows that for I=2 servers, the Whittle policy is "not far away from the optimal."

Limitations and Future Work

  • Strong Condition q1 > 2p: The analysis relies on a strong condition relating service rate and arrival probability (q1 > 2p) to ensure geometric ergodicity. The authors suggest it would be beneficial to relax this condition, ideally to one based on "near-monotonicity" of the cost function, which would penalize unstable behavior.
  • Computational Intensity: While the Whittle index policy is computationally more tractable than the exact optimal policy, computing the indices themselves can still be intensive. The authors suggest exploring more efficient approximations, potentially using reinforcement learning techniques.
  • Generalizations: The paper focuses on a simple model. Future work could explore more complex processor sharing models, different arrival/departure processes, and more general cost structures.

Summary updated

Abstract

The egalitarian processor sharing model is viewed as a restless bandit and its Whittle indexability is established. A numerical scheme for computing the Whittle indices is provided, along with supporting numerical experiments.
BibTeX
@inproceedings{borkar2022whittle,
  author = {Vivek S. Borkar and Sarath Pattathil},
  title = {{Whittle indexability in egalitarian processor sharing systems}},
  booktitle = {Ann. Oper. Res},
  year = {2022},
  url = {https://openreview.net/forum?id=MsHeIuOSKCq},
}
Figure