Routing and wavelength assignment in optical networks

Abstract

A method for solving routing and wavelength assignment (RWA) problems for all-optical networks involves formulating a joint optimization problem in which the routing of lightpaths and assignment of wavelengths on links of those routes to the lightpaths is expressed jointly in terms of a single optimization criterion. The method features formulation of the joint optimization problem as a continuous variable optimization problem with a convex constraint set. Integer constraints, for example, related to the fact that any particular lightpath is not permitted to split over multiple routes or over separate wavelengths on a link of its route, are not necessarily represented explicitly by the constraint set. However, the formulation of the objective function is such that although the problem is formulated in terms of continuous optimization variables, optimal solutions to the problem are integer or equivalent to an integer solution, thereby satisfying the integer constraints.

1. A method for assigning communication sessions in a communication network in which a network controller is configured to communicate with nodes that are coupled by communication links and at least some of the communication links support communication on discrete multiplexed channels, the method comprising:
 at the network controller, accepting a specification of a communication capacity for each of a plurality of communication sessions between nodes of the network to be assigned to paths formed by links and multiplexed channels on said links through the network according to a cost function that depends on said assignment; and 
 computing a routing configuration by the network controller, including 
 formulating a continuous optimization problem in terms of a set of optimization variables and an objective function that depends on the optimization variables, wherein the optimization variables are subject to a set of constraints that define a continuous convex multidimensional region and wherein each assignment of the communication session to paths formed by links and multiplexed channels through the network corresponds to a different point in the continuous region, 
 solving the continuous optimization problem, including determining optimal values for each of the optimization variables that optimize the objective function, and 
 determining the assignment of the communication sessions to paths formed by links and multiplexed channels through the network such that it corresponds to the optimal values obtained in solving the continuous optimization problem, wherein said assignment optimizes the cost function. 
 
   
   
     2. The method of  claim 1  wherein formulating the continuous optimization problem includes determining a set of linear constraints that define the convex region. 
   
   
     3. The method of  claim 2  wherein formulating the continuous optimization problem includes formulating the objective function to include terms that each corresponds to a different link of the network, and each of said terms is a function of the assignment of communication sessions to the corresponding link. 
   
   
     4. The method of  claim 3  wherein formulating the objective function includes formulating terms that correspond to links on which multiple communication channels are multiplexed, and said terms each includes' a convex function of a number of communication sessions assigned to said multiplexed communication channels. 
   
   
     5. The method of  claim 4  wherein the function of the number of communication sessions has discontinuities in its first derivative at values of its argument corresponding to assignments of the communication sessions to paths in the network. 
   
   
     6. The method of  claim 5  wherein the function is a piecewise linear function. 
   
   
     7. The method of  claim 6  wherein the function has constant slope between values of its argument corresponding to feasible assignments of the communication sessions to paths in the network. 
   
   
     8. The method of  claim 1  wherein formulating the continuous optimization problem further includes formulating the objective function as a linear function of the optimization variables. 
   
   
     9. The method of  claim 8  wherein solving the continuous optimization problem includes applying a linear programming algorithm. 
   
   
     10. The method of  claim 9  wherein applying the linear programming algorithm uses a simplex algorithm. 
   
   
     11. The method of  claim 1  wherein formulating the continuous optimization problem includes formulating the set of constraints to include constraints related to the capabilities of the nodes to route communication between particular communication channels on links coupled to said nodes. 
   
   
     12. The method of  claim 11  wherein the network includes nodes that couple optical links that carry wavelength multiplexed optical communication channels, and wherein formulating the set of constraints includes formulating constraints related to capabilities of said nodes to couple optical communication channels associated with particular wavelengths on different links coupled to said nodes. 
   
   
     13. The method of  claim 12  wherein formulating the constraints related to capabilities of said nodes to couple optical communication channels includes formulating constraints related to wavelength continuity at the nodes, formulating constraints related to wavelength conversion capabilities at the node, or both. 
   
   
     14. The method of  claim 1  wherein the optimization problem characterizes previously assigned communication sessions on the network, whereby the method is for dynamically routing communication sessions. 
   
   
     15. The method of  claim 14  wherein formulating the optimization problem includes formulating constraints related to assigned routes of the previously assigned communication sessions. 
   
   
     16. The method of  claim 14  wherein the network supports reassignment of the previously assigned communication sessions and the objective function includes a penalty term related to the previous assignments, and the formulated optimization problem is such that reassignment of the previously assigned sessions is feasible, but is penalized relative to a solutions that maintain the previous assignments. 
   
   
     17. An optical communication network comprising:
 nodes coupled by optical communication links in which the links support communication on a set of wavelength multiplexed channels; and 
 a network controller coupled to the nodes and configured to compute a jointly optimization of an assignment of communication sessions to paths through the network and to wavelength multiplex channels on the links of said paths according to a cost function; 
 wherein computing the joint optimization comprises
 formulating a continuous optimization problem in terms of a set of optimization variables and an objective function that depends on the optimization variables, wherein the optimization variables are subject to a set of constraints that define a continuous convex multidimensional region and wherein each assignments of the communication session to paths formed by links and multiplexed channels through the network correspond to a discrete points in the continuous region, 
 solving the continuous optimization problem, including determining optimal values of the optimization variables such that they optimize the objective function, and 
 determining the assignment of the communication sessions to paths formed by links and wavelength multiplexed channels through the network such that the assignment corresponds to the optimal values obtained in solving the continuous optimization problem, wherein said assignment optimizes the cost function. 
 
 
   
   
     18. The system of  claim 17  wherein said set of constraints includes constraints related to a communication capacity for each of the plurality of communication sessions between nodes of the network, and wherein the objective function includes a sum of terms each associated with a different link of the network, wherein each term includes a convex function of the number of wavelength multiplexed channels assigned to a communication session on the associated link and the convex function has breakpoints at arguments corresponding to integer values of the number of channels assigned. 
   
   
     19. The system of  claim 18  wherein the set of constraints further includes constraints related to capabilities of nodes to coupled channels at particular wavelength on different of the links coupled to said nodes. 
   
   
     20. A method for configuring an optical communication network with nodes coupled by optical communication links in which the links support communication on a set of wavelength multiplexed channels such that it supports a plurality of communication sessions between nodes of the network on paths formed by links and wavelength multiplexed channels on said links, comprising:
 formulating by a network controller for the communication network a continuous optimization problem in terms of a set of optimization variables and an objective function that depends on the optimization variables, wherein the optimization variables are subject to a set of constraints that define a continuous convex multidimensional region and wherein each assignments of the communication session to paths formed by links and multiplexed channels through the network correspond to a discrete points in the continuous region; 
 solving by the network controller the continuous optimization problem, including determining optimal values for each of the optimization variables that optimize the objective function and determining the assignment of the communication sessions to paths formed by links and multiplexed channels through the network such that it corresponds to the optimal values obtained in solving the continuous optimization problem; and 
 determining by the network controller a configuration of network resources according to the determined assignment of communication sessions.