OPN09-02: Lightpath Scheduling and Allocation Under a Flexible Scheduled Traffic Model

In the scheduled traffic model, the design problem is to allocate resources to a set of demands whose setup and teardown times are known in advance. The setup and teardown times may be fixed, or may be allowed to slide within a larger window. Optimal integer linear program (ILP) solutions for the first problem (fixed setup/teardown times) have been presented in the literature. In this paper we present a new and complete ILP formulation for the more general flexible window scheduled traffic model, where the setup and teardown times may vary within a specified range. We consider a survivable, wavelength convertible network, using path protection techniques. Our ILP provides an integrated solution, which jointly optimizes the problem of scheduling the demands (in time) and allocating resources for the primary and backup lightpaths. We are able to generate optimal solutions, in a reasonable amount of time, for practical networks. For very large networks, we have proposed a two-step optimization process. The first step schedules the demands optimally in time, and the second step uses existing techniques for the fixed window model to perform routing and wavelength assignment for the scheduled demands.