基于矩阵分解的光交换机分组调度算法

Packet scheduling based on matrix decomposition in optical switches

研究基于矩阵分解的光交换机分组调度算法。首先讨论了一种将双随机矩阵快速分解为置换矩阵的算法,随后提出了依据其队长在线调度置换矩阵的p-LQF算法。仿真显示p-LQF的平均分组时延接近甚至低于LQF,在业务强度较大时远低于i-LQF。证明了p-LQF对于符合强大数定理的任何可接入业务是稳定的。然后讨论了p-LQF算法对分组动态到达的适应性。最后说明了p-LQF对矩阵进行有限量化以降低算法复杂度时依然能保持系统稳定。

The packet scheduling in optical switches was investigated based on matrix decomposition technology. First a simple matrix decomposition algorithm was proposed for a doubly stochastic matrix. And then a dynamical online scheduling algorithm called p-LQF was proposed by choosing the permutation with the largest backlog. It was shown by simulation results that p-LQF had closed to or even lower average packet delay than LQF, much lower than i-LQE The p-LQF algorithm was proved to be stable for any admissible traffic satisfies the strong law of largest numbers. It was also demonstrated that p-LQF was robust to dynamical packet arrivals, and stable for the matrix with bounded traffic quantization.