CAJ | 학술논문

光交换结构有同步和异步两种工作方式,同步算法已经很多了,但异步调度算法却研究得较少.针对这种情况,提出了一个新的异步调度算法--LETF算法.证明了LETF算法在有两个输出端口时为最优调度算法,并进一步证实在多输出端口时,该算法为2近似调度算法.理论分析和仿真表明,LETF算法的时间复杂度为O(N),能达到100%吞吐量.一般情况下,在加速比最小时能无限接近于最优调度.
광교환결구유동보화이보량충공작방식,동보산법이경흔다료,단이보조도산법각연구득교소.침대저충정황,제출료일개신적이보조도산법--LETF산법.증명료LETF산법재유량개수출단구시위최우조도산법,병진일보증실재다수출단구시,해산법위2근사조도산법.이론분석화방진표명,LETF산법적시간복잡도위O(N),능체도100%탄토량.일반정황하,재가속비최소시능무한접근우최우조도.
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.