Achieving 100% Throughput in Input-Buffered WDM Optical Packet Interconnects

Packet scheduling algorithms that deliver 100% throughput under various types of traffic enable an interconnect to achieve its full capacity. Although such algorithms have been proposed for electronic interconnects, they cannot be directly applied to WDM optical interconnects due to the following reasons. First, the optical counterpart of electronic random access memory (RAM) is absent; second, the wavelength conversion capability of WDM interconnects changes the conditions for admissible traffic. To address these issues, in this paper, we first introduce a new fiber-delay-line (FDL)-based input buffering fabric that is able to provide flexible buffering delay, followed by a discussion on the conditions that admissible traffic must satisfy in a WDM interconnect. We then propose a weight-based scheduling algorithm, named Most-Packet Wavelength-Fiber Pair First (MPWFPF), and theoretically prove that given a buffering fabric with flexible delay, MPWFPF delivers 100% throughput for input-buffered WDM interconnects with no speedup required. Finally, we further propose the WDM-i SLIP algorithm, a generalized version of the i SLIP algorithm for WDM interconnects, which efficiently finds an approximate optimal schedule with low 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.