Method for routing and spectrum assignment

Patent metadata

Field	Value
Publication number	US-9252912-B2
Application number	US-201213542295-A
Country	US
Kind code	B2
Filing date	Jul 5, 2012
Priority date	Apr 9, 2012
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

Methods and apparatus are disclosed for performing a spectrum assignment and route selection algorithm in an optical WDM network. The optical WDM is assigned an optical band of frequencies. In accordance to the present invention, a new spectrum assignment in the optical band always adjoins a spectrum assignment previously allocated. The very first spectrum assignment may be made to start with one end frequency in the optical band. Given a spectrum demand, one or more spectrum assignments are identified and one or more feasible routes are determined. Among the one or more feasible routes, an optimal route may be selected based on a set of pre-defined criteria. The spectrum assignment and route selection algorithm disclosed herein reduces computational complexities and improves spectrum efficiencies.

First claim

What is claimed is:

1. A method of assigning spectrum and selecting a route for a connection between a source node and a destination node within an optical network, wherein a plurality of optical links connect the source node with the destination node, said method comprising:
determining a spectrum demand for the connection;
for each optical link, identifying, by a Path Computation Element, one or more potential spectrum allocations for the connection, each of the one or more potential spectrum allocations having a width equal to the spectrum demand, wherein each of said potential spectrum allocations starts with either a starting frequency of an optical band assigned to the optical network or an end of a previously allocated spectrum;
for each potential spectrum allocation, determining, by the Path Computation Element, a corresponding set of available optical links to obtain a residual graph that represents the residual capacity on each of the set of available optical links;
generating an auxiliary graph based on the residual graphs, wherein the auxiliary graph comprises one or more layers with each layer corresponding to a respective residual graph;
among all routes represented by the residual graphs, identifying one or more feasible routes that connect the source node and the destination node; and
selecting a route among the one or more feasible routes based on the auxiliary graph.

2. The method of claim 1 , wherein the spectrum demand comprises the frequency bandwidth required by the connection.

3. The method of claim 1 , wherein identifying the one or more potential spectrum allocations for the connection that each satisfy the spectrum demand comprises on each optical link:
identifying one or more spans of available spectrum that satisfy the spectrum demand; and
within each of the one or more spans of available spectrum, determine a potential spectrum allocation that starts with either a starting frequency or an end of a previously allocated spectrum.

4. The method of claim 1 , wherein the starting frequency corresponds to the lowest frequency in the optical band assigned to the optical network.

5. The method of claim 1 , wherein the starting frequency corresponds to the highest frequency in the optical band assigned to the optical network.

6. The method of claim 1 , wherein selecting a route based on the pre-defined criterion comprises selecting the shortest route among the one or more feasible routes.

7. The method of claim 1 , wherein selecting a route based on the pre-defined criterion comprises selecting the lowest cost route among the one or more feasible routes.

8. The method of claim 1 , further comprising selecting the route with the lowest starting frequency when two or more routes satisfy the predefined criterion.

9. A Path Computation Element configured to assign spectrum and select a route for a connection between a source node and destination node located in an optical network, said optical network comprising a plurality of optical links connecting the source node and the destination node, said Path Computation Element comprising:
an optical module for interfacing with the optical network;
one or more processing circuits configured to:
determine a spectrum demand for the connection;
for each optical link, identify one or more potential spectrum allocations for the connection, each of the one or more potential spectrum allocations having a width equal to the spectrum demand, wherein each of said potential spectrum allocations starts with either a starting frequency in an optical band assigned to the optical network or an end of a previously allocated spectrum;
for each potential spectrum allocation, determine a corresponding set of available optical links to obtain a residual graph that represents the residual capacity on each of the set of available optical links;
generate an auxiliary graph based on the residual graphs, wherein the auxiliary graph comprises one or more layers with each layer corresponding to a respective residual graph;
identify, among all routes represented by the residual graphs, one or more feasible routes that connect the source node and the destination node; and
select a route among the one or more feasible routes based on the auxiliary graph.

10. The Path Computation Element of claim 9 , wherein the spectrum demand comprises the frequency bandwidth required by the connection.

11. The Path Computation Element of claim 9 , wherein identifying the one or more potential spectrum allocations for the connection that each satisfy the spectrum demand comprises on each optical link:
identifying one or more spans of residual spectrum that satisfy the spectrum demand; and
within each of the one or more spans of residual spectrum, allocating a potential spectrum allocation that starts with either a starting frequency or an end of a previously allocated spectrum.

12. The Path Computation Element of claim 9 , wherein the starting frequency corresponds to the lowest frequency in the optical band assigned to the optical network.

13. The Path Computation Element of claim 9 , wherein the starting frequency corresponds to the highest frequency in the optical band assigned to the optical network.

14. The Path Computation Element of claim 9 , wherein the one or more processing units are further configured to select a route based on the pre-defined criterion by selecting the shortest route among the one or more feasible routes.

15. The Path Computation Element of claim 9 , wherein the one or more processing units are further configured to select a route based on the pre-defined criterion by selecting the lowest cost route among the one or more feasible routes.

16. The Path Computation Element of claim 9 , wherein the one or more processing units are further configured to select the route with the lowest starting frequency when two or more routes satisfy the pre-defined criterion.

Assignees

• Xia Ming
• Dahlfort Stefan
• Ericsson Telefon Ab L M

Inventors

• Xia Ming
• Dahlfort Stefan

Classifications

• H04Q2011/0086

  Network resource allocation, dimensioning or optimisation · CPC title

• H04J14/0267

  Optical signaling or routing · CPC title

• H04Q11/0067

  Provisions for optical access or distribution networks, e.g. Gigabit Ethernet Passive Optical Network (GE-PON), ATM-based Passive Optical Network (A-PON), PON-Ring · CPC title

• H04Q11/0066

  Provisions for optical burst or packet networks · CPC title

• H04J14/0257 Primary

  Wavelength assignment algorithms · CPC title