具有切换时延的抢占和非抢占式光交换调度研究

在分组交换和路由器设计中引入光交换技术,在可升级性、带宽、功率消耗和成本等多方面具有好处.然而,光交换机的切换时延比电交换机的切换时延长得多,使得传统面向电交换的时隙调度算法不适合于光交换环境,因此,需要设计新的调度算法,以便在传输的时隙空隙和切换次数间找到折衷.将此类光交换调度问题分为抢占式调度和非抢占式调度两种不同情形,分析并指出了它们各自的优缺点.尽管非抢占式调度不利于在时隙空隙和切换次数间取得折衷,但对于任意的切换时延,给出的基于最大加权匹配的贪心算法都可以实现2-近似(成本不高于最优调度的两倍),而且算法复杂度不高,为O(N2).对于抢占式调度,也给出了一种新颖的调度算法——2-近似启发式算法.每次在查找交换机的切换矩阵时,该算法都能保证剩下的业务矩阵都是2-近似的.仿真结果和分析表明了2-近似启发式算法:1)非常逼近最优调度;2)比ADJUST和DOUBLE算法无论是在业务传输时延,还是在计算复杂度上,都有显著改善.