2004 International Conference on Parallel Processing (ICPP'04)
Optimal Parallel Scheduling Algorithm for WDM Optical Interconnects with Recirculating Buffering
Montreal, Quebec, Canada
August 15-August 18
ISBN: 0-7695-2197-5
In this paper we study scheduling algorithms in WDM optical interconnects with recirculating buffering. The interconnect we consider has wavelength conversion capabilities. We focus on limited range wavelength conversion while considering full range wavelength conversion as a special case. We formalize the problem of maximizing throughput and minimizing packet delay in such an interconnect as a matching problem in a bipartite graph and give an optimal parallel algorithm that runs in 0(Bk^2), as compared to 0((N+B)^3k^3) time if directly applying other existing matching algorithms, where N is the number of input/output fibers, B is the number of fiber delay lines and k is the number of wavelengths per fiber.
Citation:
Zhenghao Zhang, Yuanyuan Yang, "Optimal Parallel Scheduling Algorithm for WDM Optical Interconnects with Recirculating Buffering," icpp, pp.458-465, 2004 International Conference on Parallel Processing (ICPP'04), 2004