A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks

Abstract

Advance lightpath reservation is a new research topic for connecting high-speed computer servers in lambda grid applications and for dynamic lightpath provisioning in the future optical internet. In such networks, users make call requests in advance to reserve network resources for communications. The challenge of the problem comes from how to jointly determine call admission control, lightpath routing, and wavelength assignment. In this paper, we propose an efficient Lagrangean relaxation (LGR) approach to resolve advance lightpath reservation for multi-wavelength optical networks. The task is first formulated as a combinatorial optimization problem in which the revenue from accepting call requests is to be maximized. The LGR approach performs constraint relaxation and derives an upper-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LGR approach employs a new heuristic algorithm to arrive at a near-optimal solution. By upper bounds, we assess the performance of LGR with respect to solution accuracy. We further draw comparisons between LGR and three heuristic algorithms-Greedy, First Come First Serve, and Deadline First, via experiments over the widely-used NSFNET network. Numerical results demonstrate that LGR outperforms the other three heuristic approaches in gaining more revenue by receiving more call requests.