论文部分内容阅读
光交换结构有同步和异步两种工作方式,同步算法已经很多了,但异步调度算法却研究得较少。针对这种情况,提出了一个新的异步调度算法——LETF算法。证明了LETF算法在有两个输出端口时为最优调度算法,并进一步证实在多输出端口时,该算法为2近似调度算法。理论分析和仿真表明,LETF算法的时间复杂度为O(N),能达到100%吞吐量。一般情况下,在加速比最小时能无限接近于最优调度。
There are two working modes of optical switching structure, synchronous and asynchronous, and the synchronization algorithm has been a lot, but asynchronous scheduling algorithm has been studied less. In response to this situation, a new asynchronous scheduling algorithm - the SETF algorithm is proposed. It is proved that the LETF algorithm is the optimal scheduling algorithm when there are two output ports and further confirms that the algorithm is a 2-approximate scheduling algorithm when it has multiple output ports. Theoretical analysis and simulation show that the LETF algorithm has a time complexity of O (N) and achieves 100% throughput. Under normal circumstances, the speed limit can be infinitely close to the optimal scheduling.