<p>Motivated by few delay-optimal scheduling results, in comparison to results on throughput optimality, we investigate a canonical input-queued switch scheduling problem in which the objective is to minimize the discounted delay cost over an infinite time horizon. We derive an optimal scheduling policy and establish corresponding theoretical properties for the canonical switch, as well as establishing that some of these theoretical results additionally hold for the general switch. Our results provide important fundamental insights of interest to input-queued switches in general and are expected to be of interest more broadly than input-queued switches. Computational experiments demonstrate and quantify the benefits of our optimal scheduling policy over alternative policies such as variants of MaxWeight scheduling, well-known to be throughput optimal and more recently shown to be delay optimal in the heavy-traffic regime limit.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimal weighted-delay scheduling in \(2\times 2\) input-queued switches

  • Yingdong Lu,
  • Siva Theja Maguluri,
  • Mark S. Squillante,
  • Tonghoon Suk,
  • Yi Yao

摘要

Motivated by few delay-optimal scheduling results, in comparison to results on throughput optimality, we investigate a canonical input-queued switch scheduling problem in which the objective is to minimize the discounted delay cost over an infinite time horizon. We derive an optimal scheduling policy and establish corresponding theoretical properties for the canonical switch, as well as establishing that some of these theoretical results additionally hold for the general switch. Our results provide important fundamental insights of interest to input-queued switches in general and are expected to be of interest more broadly than input-queued switches. Computational experiments demonstrate and quantify the benefits of our optimal scheduling policy over alternative policies such as variants of MaxWeight scheduling, well-known to be throughput optimal and more recently shown to be delay optimal in the heavy-traffic regime limit.