Fast restoration mechanism and method of determining minimum restoration capacity in a transmission networks

• US 7,133,359 B2
• Filed: 03/27/2002
• Issued: 11/07/2006
• Est. Priority Date: 04/04/2001
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Weis, Bernd X.
• Primary Examiner(s): Marcelo, Melvin
• Application Number:
  US10/106,502
• Publication Number:
  US 20030067867A1
• Time in Patent Office: 1,686 Days
• Field of Search: 370/216, 370/221, 370/222, 370/223, 370/224
• US Class Current: 370/222
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/037 Routes obligatorily traversing service-related nodes
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

In order to restore a network after a failure, it is important to have sufficient spare capacity available. To ensure restorability, a Hamiltonian mesh, being a closed sequence of links traversing each network node exactly once, is determined and half of its capacity is reserved for restoration purpose. In the case of a line failure of a link other than the links of the Hamiltonian mesh, affected traffic is split in two portions and rerouted over the two directions of the Hamiltonian mesh. In the case the network has no Hamiltonian mesh, a mesh coverage is determined and sufficient spare capacity reserved for restoration purpose.

Claims

1. A method of restoring a meshed transmission network upon occurrence of a line failure, said method comprising:

determining at least one mesh in the network, said mesh being a closed sequence of bi-directional links traversing each node part of the mesh exactly once, wherein remaining links in the network, which do not form part of the mesh but being protected by the mesh, intersect said mesh;

reserving transmission capacity within said mesh for restoration purpose;

routing during failure-free operation an idle signal along said mesh using said reserved capacity; and

in the case of a failure of a link in the network, rerouting traffic from the failed link over said mesh using said reserved capacity.

2. A method according to claim 1, wherein said mesh is a Hamiltonian mesh traversing each node in the network exactly once.

3. A method according to claim 2, comprising:

reserving half of the link capacity of said Hamiltonian mesh for restoration purpose and

in the case of a failure, splitting traffic to be transmitted over the failed link into two portions and rerouting said two portions over two directions of said Hamiltonian mesh using said reserved capacity.

4. A method according to claim 1, wherein said rerouting is carried out in the end nodes of said failed link, only.

5. A method according to claim 2, wherein said determining a Hamiltonian mesh is carried out using a distributed search by spreading messages between the network nodes using GMPLS protocol.

6. A method according to claim 2, wherein, if no Hamiltonian mesh could be found for the network, the method comprises determining a mesh coverage of two or more meshes for the network and reserving transmission capacity within said meshes for restoration purpose.

7. A method according to claim 2, further comprising:

augmenting the transmission capacity of said Hamiltonian mesh by doubling the Hamiltonian mesh transmission capacity; and

reserving said augmented capacity for restoration purpose.

8. A method according to claim 5, wherein a time-out is applied to the messages to avoid explosion of the number of generated messages and wherein in case the time-out lapses without finding a Hamiltonian mesh, a largest mesh found is taken and a distributed search is initiated under the network nodes not part of the largest mesh to determine a mesh coverage.

9. A method according to claim 1, further comprising determining a capacity assignment for the links of the mesh based on the maximum capacity of each link and of the capacity of the links to be protected, said capacity assignment being performed by the steps of determining an initial capacity assignment, modifying said initial capacity assignment in the case of constraint violations to obtain an initial feasible capacity assignment and optimizing said initial feasible capacity assignment by minimizing a cost function to obtain an optimized feasible capacity assignment.

10. A method according to claim 1, further comprising logically dividing said network into geographical sub-networks and determining a Hamiltonian mesh for each of said sub-networks, each Hamiltonian mesh traversing each node of its corresponding sub-network exactly once, the set of Hamiltonian meshes forming a mesh cover for said network.

11. A method of restoring a meshed transmission network upon occurrence of a line failure, said method comprising:

determining a Hamiltonian mesh in the network, said Hamiltonian mesh being a closed sequence of bi-directional links traversing each node in the network exactly once, wherein remaining links in the network, which do not form part of the Hamiltonian mesh but being protected by the Hamiltonian mesh, intersect said Hamiltonian mesh; and

if no Hamiltonian mesh could be found for the network, determining a mesh coverage of two or more meshes for the network and reserving transmission capacity within said meshes for restoration purpose.

12. A method of restoring a meshed transmission network upon occurrence of a line failure, said method

determining a Hamiltonian mesh in the network, said mesh being a closed sequence of bi-directional links traversing each node in the network exactly once, wherein remaining links in the network, which do not form part of the Hamiltonian mesh but being protected by the Hamiltonian mesh, intersect said Hamiltonian mesh;

augmenting the transmission capacity of said Hamiltonian mesh by doubling the Hamiltonian mesh transmission capacity; and

reserving said augmented capacity for restoration purpose.

13. A method of restoring a meshed transmission network upon occurrence of a line failure, said method comprising

determining a Hamiltonian mesh in the network, said Hamiltonian mesh being a closed sequence of bi-directional links traversing each node of the network exactly once, wherein remaining links in the network, which do not form part of the Hamiltonian mesh but being protected by the Hamiltonian mesh, intersect said Hamiltonian mesh;

reserving transmission capacity within said mesh for restoration purpose; and

in the case of a failure of a link in the network, rerouting traffic from the failed link over said mesh using said reserved capacity;

wherein said determining a Hamiltonian mesh is carried out using a distributed search by spreading messages between the network nodes using GMPLS protocol, and

wherein a time-out is applied to the messages to avoid explosion of the number of generated messages and wherein in case time-out lapses without finding a Hamiltonian mesh, a largest mesh found is taken and a distributed search is initiated under the network nodes not part of the largest mesh to determine a mesh coverage.

14. A method of restoring a meshed transmission network upon occurrence of a line failure, said method

determining at least one mesh in the network, said mesh being a closed sequence of bi-directional links traversing each node part of the mesh exactly once, wherein remaining links in the network, which do not form part of the mesh but being protected by the mesh, intersect said mesh;

determining a transmission capacity assignment for the links of the mesh based on the maximum transmission capacity of each link and of the transmission capacity of the links to be protected, said transmission capacity assignment being performed by determining an initial transmission capacity assignment, modifying said initial transmission capacity assignment in the case of constraint violations to obtain an initial feasible transmission capacity assignment and optimizing said initial feasible transmission capacity assignment by minimizing a cost function to obtain an optimized feasible transmission capacity assignment;

reserving transmission capacity within said mesh for restoration purpose; and

in the case of a failure of a link in the network, rerouting traffic from the failed link over said mesh using said reserved capacity.

15. A method of restoring a meshed transmission network upon occurrence of a line failure, said method comprising:

logically dividing said network into geographical sub-networks and determining a Hamiltonian mesh for each of said sub-networks, each Hamiltonian mesh traversing each node of its corresponding sub-network exactly once, the set of Hamiltonian meshes forming a mesh cover for said network;

reserving transmission capacity within said mesh cover for restoration purpose; and

in the case of a failure of a link in the network, rerouting traffic from the failed link over said mesh cover using said reserved capacity.

16. A method of determining the minimum restoration capacity in a meshed transmission network, said method comprising:

determining a Hamiltonian mesh for each sub-network in the network, said Hamiltonian mesh being a closed sequence of bi-directional links traversing each node of its corresponding sub-network exactly once, the set of Hamiltonian meshes forming a mesh cover for said network; and

reserving half of the transmission capacity within said Hamiltonian meshed for restoration purpose.

17. A network planning tool for determining the minimum restoration capacity in a meshed transmission network, said tool comprising:

means for logically dividing said network into geographical sub-networks; and

means for determining a Hamiltonian mesh for each sub-network in the network, said Hamiltonian mesh being a closed sequence of bi-directional links traversing each node of its corresponding sub-network mesh exactly once.

18. A network element in a meshed transmission network, said network element being part of a mesh being a closed sequence of bi-directional links traversing each node part of said mesh exactly once, part of the transmission capacity within said mesh being reserved for restoration purpose;

said network element comprising;

means for routing during failure-free operation an idle signal along said mesh using said reserved capacity;

means for detecting a failure of a link terminated by said network element; and

means for splitting traffic to be transmitted over the failed link into two portions and rerouting said two portions over the two directions of said mesh using said reserved capacity.

19. A network management device for configuring network elements of a meshed transmission network, said device comprising:

means for determining a mesh in the network, said mesh being a closed sequence of bi-directional links traversing each node part of said mesh exactly once;

means for configuring said network elements part of said mesh to reserve part of the transmission capacity within said mesh for restoration purpose; and

means for routing during failure-free operation an idle signal along said mesh using said reserved capacity.