Scheduling algorithm and switch fabric of optical switch are two major factors of optical switch, the optical switch fabrics may work in synchronous or asynchronous fashion. Previously, much work has been done for the synchronous optical switch scheduling, but few works focus on asynchronous optical switch scheduling (AOSS). In this paper, a new scheduling algorithm, Longest Element Transmission First (LETF), is proposed, which works under asynchronous schedule conditions with reconfiguration delay. LETF firstly proved to be an optimum schedule by switches with two ports and then 2 approximation for larger switches. We prove that AOSS problem is NP-hard for switches with more than three ports by formulating it as an open shop problem. The theory analysis and simulation results demonstrate that the novel algorithm runs at O(N) time complexity, achieves 100% throughout and performs abysmally close to the optimal scheduling in average cases by using minimum speedup.%光交换结构有同步和异步两种工作方式,同步算法已经很多了,但异步调度算法却研究得较少.针对这种情况,提出了一个新的异步调度算法--LETF算法.证明了LETF算法在有两个输出端口时为最优调度算法,并进一步证实在多输出端口时,该算法为2近似调度算法.理论分析和仿真表明,LETF算法的时间复杂度为O(N),能达到100%吞吐量.一般情况下,在加速比最小时能无限接近于最优调度.
展开▼
