Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
复制标题
DOI：
10.1239/aap/1151337082
复制
发表时间：
2006-06
影响因子：
1.2
通讯作者：
Antonis Dimakis;J. Walrand
中科院分区：
文献类型：
--
作者：
Antonis Dimakis;J. Walrand
针对广义交换模型，研究了一种自然的低复杂度调度策略——最长队列优先调度策略的稳定性。与一般调度策略不同的是，LQF的稳定性除了取决于到达过程的平均强度外，还取决于到达过程的方差。我们确定了LQF对于独立的、相同分布的到达过程是吞吐量最优的新的充分条件。确定性流体类比在排队网络稳定性分析中被证明是强大的，但不能充分表征LQF的稳定性。我们将扩散尺度的样本路径函数和局部流体限制的性质结合到更清晰的稳定性表征中。
We consider the stability of the longest-queue-first scheduling policy (LQF), a natural and low-complexity scheduling policy, for a generalized switch model. Unlike that of common scheduling policies, the stability of LQF depends on the variance of the arrival processes in addition to their average intensities. We identify new sufficient conditions for LQF to be throughput optimal for independent, identically distributed arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize the stability of LQF. We combine properties of diffusion-scaled sample path functionals and local fluid limits into a sharper characterization of stability.