Method and apparatus for path selection and wavelength assignment in an optical network

• US 20030035166A1
• Filed: 08/17/2001
• Published: 02/20/2003
• Est. Priority Date: 08/17/2001
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Quantum Bridge Communications, Inc. (Motorola Solutions, Inc.)
• Inventors: Effenberger, Frank J., Lee, Kyoo J., Zhang, Hongbiao
• Granted Patent: US 7,020,394 B2
• Time in Patent Office: Days
• US Class Current: 398/58
• CPC Class Codes: H04J 14/0227 Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
• CPC Class Codes: H04J 14/0278 WDM optical network architectures
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/62 Wavelength based optical switching H04Q11/0062

Abstract

A method and apparatus for determining a shortest path between a source node and a destination node in an optical network of nodes interconnected with optical transmission links is disclosed. A wavelength graph is used to represent an optical network as a set of electronic nodes and optical channel nodes corresponding to the network nodes with a set of internal links and optical channel links. The electronic node represents the electronic switching fabric that interconnects OEO equipment within a physical node. A single-source shortest path algorithm (e.g., Dijkstra'"'"'s algorithm) is applied to the wavelength graph to determine a shortest path. The transformation of the network representation to include the electronic node greatly reduces the number of links in the wavelength graph and significantly increases the computational efficiency.

Claims

1. A method of determining a shortest path between a source node and a destination node in an optical network having plural network nodes interconnected with optical transmission links, the method comprising:

representing the network as a uni-directional graph G=<

V,E>

with V defining a set of network nodes and E defining a set of uni-directional optical transmission links;

transforming the graph G to a wavelength graph G′

=<

V′

,E′

>

with V′

defining a set of electronic nodes and optical channel nodes corresponding to the network nodes in set V and with E′

defining a set of internal links and optical channel links, the optical channel links corresponding to the optical transmission links in set E; and

applying a single-source shortest path algorithm to the graph G′

to determine a shortest path corresponding to an optimal path on graph G.

2. The method of claim 1 wherein transforming comprises:

assigning an electronic node to each network node, the electronic node representing an electronic switching fabric interconnecting optical-electrical-optical (OEO) transmitters and receivers of the network node;

assigning optical channel nodes to each network node, each optical channel node representing an optical cross-connect for an optical channel available at the network node;

for each network node, assigning an internal link from the electronic node to each optical channel node if an associated OEO transmitter is available for the corresponding optical channel and assigning an internal link to the electronic node from each optical channel node if an associated OEO receiver is available for the corresponding optical channel;

for each optical transmission link, assigning an optical channel link between a pair of optical channel nodes of corresponding network nodes if the corresponding optical channel is available on the associated optical transmission link; and

assigning costs to the internal links and the optical channel links.

3. The method of claim 2 wherein the costs assigned to the internal links are related to OEO conversion costs.

4. The method of claim 2 wherein the costs assigned to the optical channel links are related to costs of the corresponding optical transmission links.

5. The method of claim 1 wherein applying the single-source shortest path algorithm includes applying Dijkstra'"'"'s algorithm.

6. A method of determining an optimal path between a source node and a destination node in an optical network having plural network nodes interconnected with optical transmission links, the method comprising:

assigning an electronic node to each network node, the electronic node representing an electronic switching fabric interconnecting optical-electrical-optical (OEO) transmitters and receivers of the network node;

assigning optical channel nodes to each network node, each optical channel node representing an optical cross-connect for an optical channel available at the network node;

for each network node, assigning an internal link from the electronic node to each optical channel node if an associated OEO transmitter is available for the corresponding optical channel and assigning an internal link to the electronic node from each optical channel node if an associated OEO receiver is available for the corresponding optical channel;

for each optical transmission link, assigning an optical channel link between a pair of optical channel nodes of corresponding network nodes if the corresponding optical channel is available on the associated optical transmission link;

assigning costs to the internal links and the optical channel links; and

selecting an optimal path by applying a single-source shortest path algorithm.

7. The method of claim 6 wherein the costs assigned to the internal links are related to OEO conversion costs.

8. The method of claim 6 wherein the costs assigned to the optical channel links are related to costs of the corresponding optical transmission links.

9. Apparatus for a node in a network having plural nodes interconnected with optical transmission links, the apparatus comprising:

a processor;

a memory connected to the processor; and

a computer program, in the memory, for determining an optimal path between a source node and a destination node in the network, which;

represents the network as a uni-directional graph G=<

V,E>

with V defining a set of network nodes and E defining a set of uni-directional optical transmission links;

transforms the graph G to a wavelength graph G′

=<

V′

,E′

>

with V′

defining a set of electronic nodes and optical channel nodes corresponding to the network nodes in set V and with E′

defining a set of internal links and optical channel links, the optical channel links corresponding to the optical transmission links in set E; and

applies a single-source shortest path algorithm to the graph G′

to determine a shortest path corresponding to an optimal path on graph G.

10. The apparatus of claim 9 wherein transforming comprises:

assigning an electronic node to each network node, the electronic node representing an electronic switching fabric interconnecting optical-electrical-optical (OEO) transmitters and receivers of the network node;

assigning optical channel nodes to each network node, each optical channel node representing an optical cross-connect for an optical channel available at the network node;

for each network node, assigning an internal link from the electronic node to each optical channel node if an associated OEO transmitter is available for the corresponding optical channel and assigning an internal link to the electronic node from each optical channel node if an associated OEO receiver is available for the corresponding optical channel;

for each optical transmission link, assigning an optical channel link between a pair of optical channel nodes of corresponding network nodes if the corresponding optical channel is available on the associated optical transmission link; and

assigning costs to the internal links and the optical channel links.

11. The apparatus of claim 10 wherein the costs assigned to the internal links are related to OEO conversion costs.

12. The apparatus of claim 10 wherein the costs assigned to the optical channel links are related to costs of the corresponding optical transmission links.

13. A computer program product for determining an optimal path between a source node and a destination node in an optical network having plural network nodes interconnected with optical transmission links, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which:

assigns an electronic node to each network node, the electronic node representing an electronic switching fabric interconnecting optical-electrical-optical (OEO) transmitters and receivers of the network node;

assigns optical channel nodes to each network node, each optical channel node representing an optical cross-connect for an optical channel available at the network node;

assigns an internal link from the electronic node to each optical channel node if an associated OEO transmitter is available for the corresponding optical channel and assigning an internal link to the electronic node from each optical channel node if an associated OEO receiver is available for the corresponding optical channel;

assigns an optical channel link between a pair of optical channel nodes of corresponding network nodes if the corresponding optical channel is available on the associated optical transmission link;

assigns costs to the internal links and the optical channel links; and

selects an optimal path by applying a single-source shortest path algorithm.

14. A computer data signal comprising a code segment for determining an optimal path between a source node and a destination node in an optical network having plural network nodes interconnected with optical transmission links, the computer data signal including instructions to:

assign an electronic node to each network node, the electronic node representing an electronic switching fabric interconnecting optical-electrical-optical (OEO) transmitters and receivers of the network node;

assign optical channel nodes to each network node, each optical channel node representing an optical cross-connect for an optical channel available at the network node;

assign an internal link from the electronic node to each optical channel node if an associated OEO transmitter is available for the corresponding optical channel and assigning an internal link to the electronic node from each optical channel node if an associated OEO receiver is available for the corresponding optical channel;

assign an optical channel link between a pair of optical channel nodes of corresponding network nodes if the corresponding optical channel is available on the associated optical transmission link;

assign costs to the internal links and the optical channel links; and

select an optimal path by applying a single-source shortest path algorithm.