Scheduling in buffered WDM packet switching networks with arbitrary wavelength conversion capability

Optical networking is a promising candidate for high-speed communication networks because of its huge bandwidth. In this paper we study optimal scheduling in buffered WDM packet switching networks with arbitrary wavelength conversion ability. We focus on limited range wavelength conversion while considering full range wavelength conversion as a special case of it. We formalize the problem of maximizing network throughput and minimizing total delay in such a network as finding an optimal matching in a weighted bipartite graph. We then give a simple and fast algorithm called the scan and swap algorithm that solves the problem in O(kB²) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to other existing algorithms that need at least O(k²B² + k²BN) time where N is the number of input fibers.