Method for allocating protection bandwidth in a telecommunications mesh network

• US 7,308,198 B1
• Filed: 05/16/2002
• Issued: 12/11/2007
• Est. Priority Date: 05/16/2001
• Status: Expired due to Fees

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Chow, Timothy Y., Chudak, Fabian A., Ffrench, Anthony M.
• Primary Examiner(s): Tran; Dzung
• Application Number:
  US10/150,816
• Time in Patent Office: 2,035 Days
• Field of Search: 398 4- 5, 398 10- 17, 398/19, 398 57- 60
• US Class Current: 398/58
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04Q 11/0062 Network aspects
• CPC Class Codes: H04Q 2011/0081 Fault tolerance; Redundancy; Recovery; Reconfigurability

Abstract

A telecommunications mesh network includes a plurality of nodes each interconnected by an edge. A traffic demand is received having a working path with a link of edges interconnecting a source node with a destination node. The telecommunications mesh network has one or more pre-cross-connected trails associated therewith that are subdivided into one or more subtrails. Subtrails that do not meet pre-determined conditions are discarded. A logical graph representation of the telecommunications mesh network is created from subtrails that have not been discarded. Unused, shortcut, and rival edges are inserted into the logical graph. A shortest admissible protection path from the source node to the destination node is identified from the logical graph.

Claims

1. A method for allocating protection bandwidth in a telecommunications mesh network, comprising:

receiving a demand to provide a protection path from a source node to a destination node in the telecommunications mesh network, the demand having a pre-determined working path with a sequence of edges interconnecting the source node to the destination node;

identifying a pre-cross-connectable protection path that maximizes bandwidth sharing from the source node to the destination node, wherein the pre-cross-connectable protection path does not include any multiple edge branch point conditions within the telecommunications mesh network, wherein the pre-cross-connectable protection path is identified by;

subdividing one or more pre-cross-connected trails of the telecommunications mesh network into one or more subtrails;

discarding any subtrail that does not meet any of one or more pre-determined conditions;

creating a logical graph representation of the telecommunications mesh network from subtrails that have not been discarded.

2. The method of claim 1, further comprising:

identifying a failure in the working path;

switching traffic from the working path to the pre-cross-connected protection path in response to the failure.

3. The method of claim 1, further comprising:

determining one or more pre-cross-connected trails associated with the telecommunications mesh network, each pre-cross-connect trail representing a connection between two or more nodes in the telecommunications mesh network with each node being connected by an edge.

4. The method of claim 1, further comprising:

ordering a plurality of demands for processing;

selecting a particular one of the plurality of demands having a highest priority.

5. The method of claim 1, wherein pre-cross-connected trails are discarded if they do not have entirely sharable protection edges.

6. The method of claim 1, wherein the pre-cross-connectable protection path is identified by probing forward from an initial active node in the logical graph to identify allowable partial paths therefrom.

7. The method of claim 6, wherein a partial path is an ordered quadruple identifying the partial path, a length of the partial path, forbidden edges associated with the partial path, and a state of the partial path.

8. The method of claim 1, wherein the pre-cross-connectable protection path does not include any rivals to its edges.

9. The method of claim 1, further comprising:

updating the telecommunications mesh network in response to the pre-cross-connectable protection path associated with the demand.

10. The method of claim 1, wherein a pre-cross-connected trail has connections between successive edges being intact or pre-cross-connected with either its endnodes being identical or edges at the endnodes not being connected.

11. A computer readable medium having code for allocating protection bandwidth in a telecommunications mesh network, the code operable to:

receive a demand to provide a protection path from a source node to a destination node in the telecommunications mesh network, the demand having a pre-determined working path with a sequence of edges interconnecting the source node to the destination node;

identify a pre-cross-connectable protection path that maximizes bandwidth sharing from the source node to the destination node, wherein the pre-cross-connectable protection path does not include any multiple edge branch point conditions within the telecommunications mesh network;

subdivide one or more pre-cross-connected trails of the telecommunications mesh network into one or more subtrails;

discard any subtrail that does not meet any of one or more pre-determined conditions;

create a logical graph representation of the telecommunications network from subtrails that have not been discarded.

12. The computer readable medium of claim 11, wherein the code is further operable to:

update the telecommunications mesh network in response to the pre-cross-connectable protection path.

13. The computer readable medium of claim 11, wherein the code is further operable to:

insert unused, shortcut, and rival edges into the logical graph.

14. The computer readable medium of claim 11, wherein the code is further operable to:

generate a cross-connection table, the cross-connection table including the one or more pre-cross-connection trails.

15. The computer readable medium of claim 11, wherein the code is further operable to:

identify a failure in the working path;

switch traffic from the working path to the pre-cross-connected protection path in response to the failure.

16. A method for allocating protection bandwidth in a telecommunications mesh network, comprising:

receiving a plurality of traffic demands, each traffic demand specifying a source node and a destination node, each traffic demand having a working path with a sequence of edges interconnecting the source node to the destination node through intermediate nodes;

ordering the plurality of traffic demands;

selecting a particular traffic demand having a highest priority;

generating a cross-connection table for the telecommunications mesh network;

pre-cross-connecting un-connected consecutive edges in the telecommunications mesh network;

breaking any pre-cross connections that violate a set of pre-determined conditions;

performing a primary and a secondary routing routine to identify a mesh protection path for the selected traffic demand, wherein the mesh protection path does not include any multiple edge branch point conditions within the telecommunications mesh network, wherein the primary routing routine includes;

subdividing one or more pre-cross-connected trails of the telecommunications mesh network into one or more subtrails;

discarding any subtrail that does not meet any of one or more pre-determined conditions;

creating a logical graph from subtrails that have not been discarded;

inserting unused, shortcut, and rival edges into the logical graph;

identifying a shortest admissible protection path from the source node to the destination node from the logical graph.

17. The method of claim 16, further comprising:

creating an auxiliary network representation in the primary routing routine using a load balancing criteria.

18. The method of claim 16, further comprising:

determining one or more pre-cross-connected trails associated with the telecommunications mesh network, each pre-cross-connect trail representing a connection between two or more nodes in the telecommunications mesh network with each node being connected by an edge.

19. The method of claim 16, wherein the shortest admissible protection path identified maximizes bandwidth sharing in the telecommunications mesh network and does not include any rivals to its edges.

20. The method of claim 16, further comprising:

adjusting an allocation plan for the telecommunications mesh network in response to the mesh protection path.