TY - GEN
T1 - Achieving 100% throughput in input-buffered WDM optical packet interconnects
AU - Liu, Lin
AU - Yang, Yuanyuan
PY - 2008
Y1 - 2008
N2 - All-optical wavelength-division-multiplexing (WDM) interconnects are a promising candidate for future ultra high-speed 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.
AB - All-optical wavelength-division-multiplexing (WDM) interconnects are a promising candidate for future ultra high-speed 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.
KW - Input-buffered
KW - Maximum weighted matching
KW - Packet scheduling
KW - Wavelength conversion
KW - WDM optical packet interconnects
UR - https://www.scopus.com/pages/publications/51049089080
U2 - 10.1109/IPDPS.2008.4536309
DO - 10.1109/IPDPS.2008.4536309
M3 - Conference contribution
AN - SCOPUS:51049089080
SN - 9781424416943
T3 - IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM
BT - IPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM
T2 - IPDPS 2008 - 22nd IEEE International Parallel and Distributed Processing Symposium
Y2 - 14 April 2008 through 18 April 2008
ER -