On Queue-Size Scaling for Input-Queued Switches
On Queue-Size Scaling for Input-Queued Switches
复制标题
关于输入队列交换机的队列大小缩放
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Y. Zhong
中科院分区：
文献类型：
--
作者：
Devavrat Shah;J. Tsitsiklis;Y. Zhong
我们研究了在一个$n中期望总队长的最优缩放 乘以n$输入排队交换机，作为端口数n$和负载因子的函数
ho$，它已被证明是$Theta（n/（1-
ho））$。在最近的一项工作中，这一猜想的有效性已经建立了制度，其中1-
时间复杂度为O（1/n^2）。在本文中，我们在这个猜想的方向上取得了进一步的进展。我们提供了一类新的调度策略，在该策略下，期望的总队列大小为$O（n^{1.5}（1-
ho）^{-1}log（1/（1-
（ho）$当$1-
时间复杂度为O（1/n）。这是对现有技术的改进;例如，对于$
ho = 1 - 1/n$最好的已知界限是O（n^3）$，而我们的是O（n^{2.5}log n）$。
We study the optimal scaling of the expected total queue size in an $n imes n$ input-queued switch, as a function of the number of ports $n$ and the load factor $
ho$, which has been conjectured to be $Theta (n/(1-
ho))$. In a recent work, the validity of this conjecture has been established for the regime where $1-
ho = O(1/n^2)$. In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as $O(n^{1.5}(1-
ho)^{-1}log(1/(1-
ho)))$ when $1-
ho = O(1/n)$. This is an improvement over the state of the art; for example, for $
ho = 1 - 1/n$ the best known bound was $O(n^3)$, while ours is $O(n^{2.5}log n)$.