Route protection in a communication network

• US 20020188756A1
• Filed: 05/03/2001
• Published: 12/12/2002
• Est. Priority Date: 05/03/2001
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Hayward, Kenneth, Odhams, David, Andersson, Loa, Morrall, Alex, Weil, Jon
• Granted Patent: US 7,380,017 B2
• Time in Patent Office: Days
• US Class Current: 709/240
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A communications network comprises a lower transport layer and an upper overlay incorporating a plurality of routers. Adjacencies are defined between respective pairs of routers. Path protection is provided by defining a software model of the overlay of the network and defining in the model a hierarchy of protection levels for the main path. Each protection level is characterised by a respective set of one or more broken adjacencies in the model, the adjacencies to be broken being determined from a knowledge of the underlying topology. A protection level is selected and a protection path avoiding the broken adjacencies associated with that protection level is calculated. If this calculated path is not available in the real network, a lower protection level in the hierarchy is selected and the protection path calculation repeated. The process continues until a suitable protection path is identified.

Claims

1. A method of fault recovery in a multi-layer communications network having a transport layer topology and an overlay topology, in which adjacencies are defined between a plurality of network nodes, the method comprising, for each adjacency for which a recovery path is to be determined, modifying the overlay topology by removal of selected adjacencies, attempting computation of a path, and if no path is available removing fewer selected adjacencies from the overlay topology and repeating said path computation.

2. A method as claimed in claim 1, wherein said adjacencies are selected from a knowledge of the transport layer topology.

3. A method of calculating a protection path for traffic carried on a main path in a multilayer communications network having a lower transport layer and an upper layer incorporating a plurality of routers, and in which adjacencies are defined between respective pairs of routers, the method comprising the steps of;

defining a model of the network;

defining in said model a hierarchy of protection levels, each said protection level being characterised by a respective set of broken adjacencies in said model;

attempting to calculate a recovery path for a selected protection level in said hierarchy; and

if no said path is available, repeating said calculation attempt for successive further protection levels in said hierarchy until a protection path is identified.

4. A method of calculating a protection path for traffic carried on a main path in a multi-layer communications network comprising a lower transport layer and an upper overlay incorporating a plurality of routers, there being a plurality of adjacencies defined between respective pairs of routers, wherein the method comprises the steps of;

defining a software model of the overlay of said network;

defining in said model a hierarchy of protection levels for said main path, each said protection level being characterised by a respective set of one or more broken adjacencies in said model;

selecting one said protection level and calculating a protection path avoiding the broken adjacencies associated with that protection level;

determining whether the calculated protection path is available in the network; and

,

if said calculated path is not available in the network, repeating said path calculation and determining steps for one or more further selected protection levels.

5. A method as claimed in claim 4, wherein said protection levels are selected in order of hierarchy.

6. A method as claimed in claim 5, wherein said protection path is calculated via a next next hop algorithm.

7. A method as claimed in claim 6, wherein a protection level is selected according to a class of traffic carried on the path to be protected.

8. A method as claimed in claim 7, wherein said network incorporates a transport layer comprising a plurality of switches interconnected by optical fibre paths.

9. A method as claimed in claim 7, wherein the network model topology is defined by a first list of adjacencies representing the overlay topology, and a second list of paths, one for each adjacency.

10. A method as claimed in claim 9, and further comprising editing the network model topology by selecting sequentially the adjacencies in the overlay topology, testing each adjacency against assumptions about what equipment has failed in light of a hypothesised IP layer adjacency loss indication, and, if the adjacency passes the test, removing it from the topology.

11. A method as claimed in claim 10, wherein said transport layer comprises a synchronous network.

12. A method as claimed in claim 11, wherein said network is a packet network.

13. A method as claimed in claim 12, wherein said network is a multi-protocol label switched network.

14. A method as claimed in claim 13, wherein said network incorporates one or more virtual private networks.

20. A network manager as claimed in claim 19, and embodied as software in machine readable form on a storage medium.

15. A method of identifying a protection path for traffic carried on a main path in a multi-layer communications network so as to remedy a fault condition involving one or more network elements, the method comprising the steps of:

assuming the failure of a plurality of network elements;

calculating a protection path circumventing all the assumed failed network elements and determining whether that calculated path is an available path in the network; and

if said calculated path is not an available path in the network, successively assuming the failure of fewer network elements and repeating the path calculation and determination steps for each successive assumption until an available protection path is Identified.

16. Software in machine readable form for identifying a protection path for traffic carried on a main path in a multi-layer communications network so as to remedy a fault condition involving one or more network elements, the software being arranged to perform the method steps of:

assuming the failure of a plurality of network elements;

calculating a protection path circumventing all the assumed failed network elements and determining whether that calculated path is an available path in the network; and

if said calculated path is not an available path in the network, successively assuming the failure of fewer network elements and repeating the path calculation and determination steps for each successive assumption until an available protection path is identified.

17. A method of network management for planning fault recovery paths in a multi-layer communications network having a transport layer and an overlay topology, and in which adjacencies are defined between a plurality of network nodes, the method comprising, providing a model of the network, and within said model for each recovery path to be determined, modifying the overlay topology by removal of selected adjacencies, attempting computation of a recovery path, and if no recovery path is available removing fewer selected adjacencies from the overlay topology and repeating said recovery path computation.

18. A method of network management for planning fault recovery paths in a multi-layer communications network so as to remedy a future fault condition involving one or more network elements on a traffic path, the method comprising the steps of:

providing a model of the network

assuming the failure of a plurality of network elements in said model;

calculating a protection path circumventing all the assumed failed network( elements and determining whether that calculated path is an available path in the network; and

if said calculated path is not an available path in the network, successively assuming the failure of fewer network elements and repeating the path calculation and determination steps for each successive assumption until an available protection path is identified.

19. A network manager for a multi-layer communications network and for planning fault recovery paths in said network so as to remedy a fault condition involving one or more network elements on a traffic path, the network manager being arranged to perform the method steps of:

providing a model of the network

assuming the failure of a plurality of network elements in said model;

calculating a protection path circumventing all the assumed failed network elements and determining whether that calculated path is an available path in the network; and

if said calculated path is not an available path in the network, successively assuming the failure of fewer network elements and repeating the path calculation and determination steps for each successive assumption until an available protection path is identified.

21. A communications network having a transport layer and an overlay topology, in which adjacencies are defined between a plurality of network nodes, wherein the network is provided with a path protection system for calculating recovery traffic paths so as to remedy network faults, said protection system being associated with a model of the network and being arranged to modify, within that model, the overlay topology by removal of selected adjacencies, to attempt computation of a path, and if no path is available, to remove fewer selected adjacencies from the overlay topology in said model and repeat said path computation.

22. A network as claimed in claim 21, wherein said protection system defines in said model a hierarchy of protection levels for said main path, each said protection level being characterised by a respective set of one or more broken adjacencies in said model.

23. A network as claimed in claim 22, wherein said protection system selects said protection levels in order of hierarchy.

24. A network as claimed in claim 23, wherein said protection path is calculated via a next next hop algorithm.

25. A network as claimed in claim 24, and incorporating a transport layer comprising a plurality of switches interconnected by optical fibre paths.

26. A network as claimed in claim 25, wherein said transport layer comprises a synchronous network.

27. A network as claimed in claim 26, and comprising a packet network.

28. A network as claimed in claim 27, and comprising a multi-protocol label switched network.