论文部分内容阅读
提出了一种新颖的2 近似启发式算法,对具有切换时延的光交换机进行调度.算法主要包含两步操作:匹配选择和权重判决.匹配选择通过贪心算法实现,它决定了交换机内核的配置情况;权重判决确定了交换内核配置的持续时间,其实现机理为:对于给定的匹配,所选择的权重要使得剩余业务矩阵的估计成本为最优.该算法的时间复杂度为O(N2logN).相对于最优调度算法来说,此算法理论上可保证2近似,即性能至多比最优调度恶化2倍.仿真结果表明:此文算法几乎可以逼近最优调度,比Adjust和Double算法更能自适应于各种变化的业务方式。
A novel 2-approximate heuristic algorithm is proposed to schedule optical switches with switching delay.The algorithm mainly consists of two steps: matching selection and weight decision.The matching selection is implemented by greedy algorithm, which determines the configuration of the switch core The weight decision determines the duration of the exchange kernel configuration, and the realization mechanism is as follows: For a given match, the chosen weight should make the estimated cost of the remaining service matrix be optimal.The time complexity of the algorithm is O (N2logN Compared with the optimal scheduling algorithm, this algorithm can theoretically guarantee 2 approximations, that is, the performance is at most 2 times worse than the optimal one. Simulation results show that this algorithm can approximate the optimal scheduling almost, More adaptive to a variety of business practices.