Improved Queue-Size Scaling for Input-Queued Switches via Graph Factorization
Improved Queue-Size Scaling for Input-Queued Switches via Graph Factorization
复制标题
通过图分解改进输入队列交换机的队列大小缩放
DOI：
--
复制
发表时间：
2019
影响因子：
1.2
通讯作者：
Y. Zhong
中科院分区：
文献类型：
--
作者：
Jiaming Xu;Y. Zhong
本文研究了n维排队系统中期望总队长的标度问题 乘以n$输入排队交换机，作为负载ρ和系统规模n的函数。我们提出了一类新的调度策略，在该策略下，期望的总队列大小为O_（1-ρ）^-4/3）log_（1-ρ）（max\frac 1 1，n
（八）
ight）$，对于所有n且ρ<1$，当到达率均匀时。这在两个区域中改进了以前最著名的标度：Oleft（n^1.5（1-ρ）^-1）logfrac 1 1-ρ
ight）$当n（n^-1.5）= 1-ρ = O（n^-1）$和$O = left（fracnlogn（1-ρ）^2
ight）$ when $1-ρ geq mega（n^-1）.在我们的方法中的一个关键成分是一个紧密的随机二部多重图，这可能是独立的利益的最大k-因子的表征。
This paper studies the scaling of the expected total queue size in an $n imes n$ input-queued switch, as a function of both the load ρ and the system scale n. We provide a new class of scheduling policies under which the expected total queue size scales as Ołeft( n(1-ρ)^-4/3 łog łeft(max\frac1 1-ρ, n
ight)
ight)$, over all n and ρ<1$, when the arrival rates are uniform. This improves over the previously best-known scalings in two regimes: Ołeft(n^1.5 (1-ρ)^-1 łog frac1 1-ρ
ight)$ when Ømega(n^-1.5 ) łe 1-ρ łe O(n^-1 )$ and $Ołeft(fracnłog n (1-ρ)^2
ight)$ when $1-ρ geq Ømega(n^-1 ). A key ingredient in our method is a tight characterization of the largest k-factor of a random bipartite multigraph, which may be of independent interest.