We study the benefits and trade-off of using scheduled lightpaths for traffic adaption. We propose a network planning model, which allows lightpaths to slide within its desired timing window with no penalty on the optimization objective, and to slide beyond its desired timing window with a decreasing tolerance level. Our model quantitatively measures the timing satisfaction or violation. We apply the Lagrangian Relaxation and Subgradient Method to the formulated optimization problem. Our method demonstrated great computational efficiency when compared with other existing algorithms. Our simulation results show how timing flexibility improves network resource utilization and reduces rejections.

In this comment, several errors in Chlamtac et al., 1996, Lightpath (Wavelength) Routing in Large WDM Networks and one error in Xu et al., 2000, Dynamic Routing and Assignment of Wavelength Algorithms in Multifiber Wavelength Division Multiplexing Networks are pointed out. We present corrections to the errors.

We present a study on the static resource allocation in lightpath routed WDM networks, where each request is associated with a service grade. The goal is to maintain certain acceptance ratios for the requests of all grades, as well as to minimize the resource consumption. We propose a model of static grade-of-service (GoS) differentiation as minimizing the total rejection and cost penalty. Then, we use the Lagrangian relaxation and subgradient methods to solve the problem. The results of using static GoS differentiation are presented.

Various static resource allocation algorithms have been used in WDM networks to allocate resources such as wavelength channels, transmitters, receivers, and wavelength converters to a given set of static lightpath demands, based on certain design objectives. However, although optimized resource allocations can be obtained, it remains an open issue how to determine which resources are bottlenecks to achieve better performance. Existing static resource allocation algorithms do not explicitly measure the impact of a given resource on the design objective. In this paper, we propose such a measurement based on the Lagrangian relaxation (LR) framework We use the optimized values of Lagrange multipliers as a direct measurement of the criticality of resources. Such a quantitative measurement can be naturally acquired along with the optimization process to obtain the optimal solution (or a near optimal solution) to the static routing and wavelength assignment (RWA) problem. Such a measurement helps to identify critical resources, and thus to decide the best way to add or reallocate resources.

In this paper, we study the routing and wavelength assignment (RWA) problem in a semi-dynamic scenario where rearrangements are conducted in a series of sessions after traffic demands vary. Unlike pure static RWA problems, each rearrangement scheme must consider established lightpaths in the previous session. A novel formulation of the WDM network rearrangement problem is used to minimize rejected new demands and rerouted lightpaths. This is done by coordinating the re-routing of existing lightpaths with the adaptation to varying demands. The Lagrangean Relaxation and Subgradient Method (LRSM) has been successfully used to solve the problem along with fairness consideration. The superior performance and reduced computation complexity of our algorithm are demonstrated in sample networks. In addition, we evaluate the benefit of using wavelength converters in a WDM network rearrangement. In contrast to previous studies with conclusions that wavelength converters are of little value in the static RWA problem, we show that wavelength converters improve network performance in a WDM network rearrangement.

We propose a novel link-based formulation of the WDM network reconfiguration problem for the semi-dynamic scenario, where reconfigurations are required in a series of sessions as traffic demands vary. Each reconfiguration session must consider existing connections obtained from the previous reconfiguration session. We coordinate the reconfiguration of existing connections with the new traffic demands by minimizing the rejected demands and reconfigured connections. With a much more complicated formulation, we are also able to incorporate the fairness consideration. The Lagrangean Relaxation and Subgradient Methods (LRSM) are successfully used to solve the WDM network reconfiguration problem. We demonstrate superior algorithm performance and reduced computation complexity in sample networks. In addition, we demonstrate that there is a benefit of using wavelength converters in WDM network reconfiguration problem, in contrast to the conclusion of the previous studies that wavelength converters are of little value in the static RWA problem.

Unlike traditional heuristics, we provide in this paper an optimization framework for the routing and wavelength assignment (RWA) problems with the objective of minimizing the rejection penalty of the connection demands in an all-optical wavelength-division-multiplexing (WDM) network. Our new link-based formulation takes the fairness issue and the limited wavelength conversion into consideration. The framework employs a decomposition approach to decide on the rejection/selection of the route and wavelength assignment for a semilightpath, by appropriately relaxing some of the constraints in the Lagrangean relaxation (LR) method. At the higher level, we update Lagrange multipliers iteratively with the subgradient method. At the lower level, we propose the modified minimum cost semilightpath (MMCSLP) algorithm to solve all the subproblems. A heuristic algorithm is also proposed to generate a feasible RWA scheme based on the solution to the dual problem. When compared with some latest methodology in the literature, we demonstrate that our framework can achieve better performance in terms of the computation time and the number of connection demands rejected. The much shorter computation time is due to the polynomial time complexity of our framework. In addition to achieving a very good (near-optimal) solution, the influence from the change of the number of converters is studied. Finally, we demonstrate that our framework produces fairer routing decisions by adjusting some design parameters in our framework.

The emergence of DWDM (dense wavelength-division multiplexing) technology has provided the network designer great convenience in constructing a wavelength routing optical network. In this paper, we study the problem of routing and wavelength assignment (RWA) in an all-optical DWDM network. We formulated the problem into a constrained integer linear problem (ILP) and the objective is to minimize the overall cost of the routing scheme over the DWDM network. Considering the complexity of the RWA problem, a decomposition approach using Lagrangean relaxation is proposed to simplify the solution procedure. The overall problem is decomposed into semi-lightpath level subproblems for the wavelength and route selection from the source to the destination. The multipliers are then updated at high level. To optimize the dual function, subgradient approach is used. Also, a heuristics algorithm is proposed to generate a feasible RWA scheme based on the dual solution. The performance evaluation for the optimization result of one network example indicates that the algorithm we used can achieve very good near-optimum solution, and the influence from the changing of the number of resources is also studied.