Integrated Provisioning of Sliding Scheduled Services Over WDM Optical Networks [Invited]

Many future Internet applications supported over optical networks may require large amounts of guaranteed bandwidth between two remote end hosts, but this bandwidth may not necessarily be needed immediately. To ensure a deterministic service, Internet customers may prefer to reserve network resources, e. g., lightpaths, in advance and may indicate an approximate time window in the future during which the bandwidth should be reserved for a certain period of time; however, the exact start time of the reservation is not specified, but can slide in the predefined time window. This type of user traffic is called "sliding scheduled traffic." Optical network design for provisioning sliding scheduled traffic is a highly complex task that has been dealt with in the literature by two-step approaches, which first schedule user demands in time and then perform their routing and wavelength assignment (RWA). We propose a scalable integrated design for the sliding scheduling provisioning problem (SSPP), based on the Lagrangean relaxation (LR) approach, which can jointly perform the scheduling and RWA of the demands. We first develop a new mathematical model for SSPP, to which it is suitable to apply the relaxation of some of the model's constraints. We use an integrated heuristic called IPSR (integrated provisioning of sliding requests), which is next enhanced with a cost assignment based on Lagrangean multiplier information, to serve as the primal algorithm for our LR approach (named IPSR-LR). We compare our approaches with an existing two-step heuristic algorithm for SSPP and show that both IPSR and IPSR-LR are able to outperform it. In addition, our numerical results show that IPSR-LR improves over IPSR under all typical experimental cases that we considered. Furthermore, we compare our approaches with the solutions provided by an integer linear program for the SSPP, which is, however, less scalable for large problem sizes compared with our algorithms.