LCCF: A scheduling algorithm for asynchronous optical switches

Using optical technology for packet switch fabrics offers several advantages such as scalability, high bandwidth, lower power consumption, and lower cost. These optical fabrics may work in synchronous or asynchronous fashion. This paper focuses on the asynchronous optical switch scheduling (AOSS) problem. We show that the AOSS problem is NP-complete for switches with more than three ports by formulating it as an open-shop problem. A heuristic scheduling algorithm, Longest Complement Connection First (LCCF), is proposed to approximate the optimal solution. LCCF generates optimum schedule lengths for switches with two ports and is 2-approximation for larger switches. Our analysis will demonstrate that LCCF uses minimum speedup when compared to existing algorithms across a wide range of switching systems. Simulation also shows that LCCF algorithm achieves nearly optimum results in average cases. In addition, LCCF is simple and can be implemented in a distributed fashion.