切换时延不为零的光交换调度算法

Scheduling algorithm of optical switches with switching delay

文章针对切换时延不为零的光交换调度提出了一种新算法———2近似启发算法。算法由两部分组成:选择匹配和决策权重。其中,选择匹配是确定光交叉阵列的切换次数,由贪心算法完成;决策权重是决定各个配置的持续时长,它是通过选择一个值以使剩下的业务矩阵的开销估计最优。2近似启发算法的近似因子为2,时间复杂度为O(N2logN)。仿真表明这种调度算法更接近最优调度,比DOUBLE[1]和AD JUST[2]算法更能自适应传送来的不同业务模式。

A new algorithm -2 approximation heuristic algorithm is presented for the scheduling of optical switches with configuration delay, which works by combining two main operations： matching selection and weight decision. Matching selection is achieved by greedy algorithm, which determines the times of the switch, while weight decision decides the holding time of the configuration selected, which is achieved by choosing a value such that the remaining traffic matrix has the best possible cost estimate. The algorithm has an approximation factor of 2 with a time complexity of O（N^2logN） . The simulation results demonstrate that this algorithm is close to optimal scheduling and more self-adjustable to various traffic arrival patterns than DOUBLE and ADJUST algorithms.