2-step-optimization procedure for routing and wavelength assignment with combined dedicated shared protections in multi-cable multi-fiber optical WDM networks
View Patent ↗The inventive 2-step-optimization procedure that addresses the generalized routing and wavelength assignment problem with variable number of combined 1+1 dedicated and shared connections for the first time. The proposed procedure results a solution in time that is polynomial of the input size. Thus, the time complexity of the 2-step-optimization procedure is significantly less than that of existing methods.
1. A computer implemented method for finding a routing and wavelength assignment for a given set of traffic demands requiring variable number of dedicated and shared protections, said method comprising:
constructing a layered graph responsive to locations of communication nodes and links between the nodes in a network;
finding a shortest route between source nodes and destination nodes in the network; assigning wavelengths along shared ones of the routes such that sharing of wavelengths is maximized;
searching from among the assigned wavelengths for potential solutions for routing and wavelength assignment in the network;
selecting one of the solutions requiring a minimum number of new wavelength links that balance communications in the network; and
finding a sharing factor of each wavelength, the sharing factor being a number of fiber cables on which the wavelength can be shared wherein if found working routes and dedicated background routes of a traffic request are link disjoint for all traffic requests then the wavelength on a certain fiber of a fiber link can be shared.
2. The computer implemented method of claim 1 , wherein the constructing step comprises:
ordering traffic demands on the network in descending order of their minimum hop distance between end nodes in the network;
assigning for each fiber cable link in the network a cost proportional to wavelength utilization of a fiber cable; and finding a shortest route by:
replacing negative fiber cable links in the network by positive fiber cable links and removing overlapping fiber cable links of the routes.
3. The computer implemented method of claim 1 , wherein finding the shortest route between source nodes and destination nodes includes initializing a set of routes in the network depicted in the layered graph and replacing each fiber cable link along the routes in the layered graph by a single link directed towards a source node.
4. A system comprising:
a network of fiber optic nodes and links; and
a computer with processor and memory for implementing an optimization for finding a routing and wavelength assignment for a given set of traffic demands in the network requiring variable number of dedicated and shared protections, the optimization comprising:
constructing a layered graph responsive to locations of communication nodes and links between the nodes in a network;
ordering traffic demands on the network in descending order of their minimum hop distance between end nodes in the network;
assigning for each fiber cable link in the network a cost proportional to wavelength utilization of a fiber cable;
finding a shortest route between source nodes and destination nodes in the network;
replacing negative fiber cable links in the network by positive fiber cable links and removing overlapping fiber cable links of the routes;
assigning wavelengths along shared ones of the routes such that sharing of wavelengths is maximized; and
searching from among the assigned wavelengths for potential solutions for routing and wavelength assignment in the network; and
selecting one of the solutions requiring a minimum number of new wavelength links that balance communications in the network; and
finding a sharing factor of each wavelength based on the relationship r 1 εQ n l i n l j qw , ∀ n l i , n l j , q, w, where w is the wavelength, n l i , n l j are i th and j th connecting nodes, q is a fiber within connecting nodes i and j, and for each wavelength w in a fiber q that is confined within fiber cable link l connecting nodes n l i and n l j , the ID of all successfully established requests that use the wavelength w for shared protection is recorded in the conflict set Q n l i n l j qw .
5. The system of claim 1 , wherein the optimization comprises finding a sharing factor of each wavelength, the sharing factor being a number of fiber cables on which the wavelength can be shared wherein if found working routes and dedicated background routes of a traffic request are link disjoint for all traffic requests then the wavelength on a certain fiber of a fiber link can be shared.
6. A computer implemented method for finding a routing and wavelength assignment for a given set of traffic demands requiring variable number of dedicated and shared protections, said method comprising the steps of:
constructing a layered graph responsive to locations of communication nodes and links between the nodes in a network;
finding a shortest route between source nodes and destination nodes in the network;
assigning wavelengths along shared ones of the routes such that sharing of wavelengths is maximized; and
searching from among the assigned wavelengths for potential solutions for routing and wavelength assignment in the network; and
selecting one of the solutions requiring a minimum number of new wavelength links that balance communications in the network, wherein the optimization comprises finding a sharing factor of each wavelength, the sharing factor being a number of fiber cables on which the wavelength can be shared wherein if found working routes and dedicated background routes of a traffic request are link disjoint for all traffic requests then the wavelength on a certain fiber of a fiber link can be shared.