Achieving 100% throughput in input-buffered WDM optical packet interconnects

All-optical wavelength-division-multiplexing (WDM) interconnects are a promising candidate for future ultra highspeed interconnections due to the huge capacity of optics. Packet scheduling algorithms that can guarantee 100% throughput under various types of traffic enable an interconnect to achieve its full capacity. However, although such algorithms have been proposed for electronic interconnects, they cannot be directly applied to WDM optical interconnects due to the following reasons. First, almost all of these algorithms depend on the virtual output queue (VOQ) technique which is currently difficult to implement in WDM optical interconnects due to lack of optical RAM; Second, a packet arriving at the input of a WDM interconnect now have more than one output wavelength channels to choose from due to wavelength conversion capability. The former motivates us to search for a new input buffering fabric that is more practical under the current optical technology and can achieve satisfactory performance, and the latter indicates that a new definition of "admissible traffic" may be needed for WDM optical interconnects. In this paper, we first introduce a new fiber- delay-line (FDL) based input buffering fabric that is able to provide flexible buffering delay in WDM optical interconnects. We then give a new definition of "admissible traffic" for a WDM optical interconnect, and propose the most- packet wavelength-fiber pair first (MPWFPF) scheduling algorithm for WDM interconnects using such buffering fabric. We theoretically prove that with the new buffering fabric, MPWFPF can deliver 100% throughput for input-buffered WDM interconnects with no speedup required. Finally, we further propose a faster scheduling algorithm, WDM-iSLIP, that can efficiently determine an approximate optimal schedule with much lower time complexity. Extensive simulations have been conducted to verify the theoretical results, and test the performance of the proposed scheduling algorithms in input- -buffered WDM interconnects with the new buffering fabric.