Method and apparatus for inter-zone restoration

• US 8,762,568 B1
• Filed: 07/06/2001
• Issued: 06/24/2014
• Est. Priority Date: 07/06/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Zadikian, H. Michael, Baghdasarian, Zareh, Saleh, Ali N., Parsi, Vahid
• Primary Examiner(s): Tiv, Backhean
• Application Number:
  US09/899,962
• Time in Patent Office: 4,736 Days
• Field of Search: 370/355, 370/354, 709/239, 709/238, 709/240
• US Class Current: 709/239
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085

Abstract

A method and system is provided to reduce the time to restore links in a communication system. The method and system employ a preplanned backbone zone to eliminate downtime searches for alternate paths. Efficient use of restoration techniques assures that inter-zone routes are properly allocated. Alternate paths are chosen by calculating shortest paths from a root node to a target node. The shortest paths are placed in a table for lookup whenever a communication failure occurs. Considerations as to cost and length are taken into account in determining the alternative routes.

Claims

1. A method comprising:

establishing a virtual path over a first route in a backbone zone, wherein

the backbone zone comprises a plurality of zones coupled to one another by a plurality of inter-zone links,

the plurality of zones comprises a source zone and a destination zone, and

the first route comprises at least one inter-zone link between a first border node of the source zone and a second border node of the destination zone;

identifying a pre-planned alternative route in the backbone zone, wherein

the pre-planned alternative route is between the first border node of the source zone and the second border node of the destination zone, and

the pre-planned alternative route is automatically determined using a shortest path first (SPF) algorithm prior to detection of a first inter-zone link failure in the first route;

detecting the first inter-zone link failure in the first route;

establishing the virtual path over the pre-planned alternative route, in response to detection of the first inter-zone link failure comprising

releasing link bandwidth used by the virtual path, and

restoring the virtual path if the first inter-zone link failure indicates failure of the first border node of the source zone;

detecting a second inter-zone link failure in the first route;

configuring the pre-planned alternative route to pass through a transit zone upon detecting the second inter-zone link failure, wherein

the transit zone comprises one or more tandem nodes used by the virtual path, and

the tandem node neither originates or terminates the virtual path; and

providing communication between the destination zone and the source zone via the pre-planned alternative route.

2. The method of claim 1, wherein:

the first route meets class of service requirements between the source zone and the destination zone; and

the pre-planned alternative route meets the class of service requirements between the source zone and the destination zone.

3. The method of claim 2, further comprising:

requesting one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

4. The method of claim 2, further comprising:

establishing one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

5. The method of claim 1, further comprising:

routing the pre-planned alternative route through a transit zone, wherein

the plurality of zones comprises the transit zone, and

the transit zone is distinct from the source zone and the destination zone.

6. The method of claim 1, further comprising:

requesting one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

7. The method of claim 1, further comprising:

establishing one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

8. The method of claim 1, wherein

the source zone executes a first copy of a topology distribution algorithm,

the destination zone executes a second copy of the topology distribution algorithm,

the first copy of the topology distribution algorithm lacks topology information for the destination zone, and

the second copy of the topology distribution algorithm lacks topology information for the source zone.

9. The method of claim 8, further comprising:

routing the pre-planned alternative route through a transit zone wherein

the transit zone executes a third copy of the topology distribution algorithm,

the third copy of the topology distribution algorithm lacks topology information for the source zone,

the third copy of the topology distribution algorithm lacks topology information for the destination zone, and

the routing the pre-planned alternative route through the transit zone is based at least in part on the third copy of the topology distribution algorithm.

10. The method of claim 1, further comprising

computing the first route in the backbone zone between the source zone and the destination zone, wherein

the first route is computed using a topology database that comprises information about the plurality of inter-zone links;

disqualifying the at least one inter-zone link of the first route from a copy of the topology database to produce a pruned topology database; and

computing a second route in the backbone zone between the source zone and the destination zone, wherein

the second route is computed using the pruned topology database, and

the second route is assigned as the pre-planned alternative route for the first route.

11. The method of claim 10, wherein

the computing the first route comprises

generating a first route cost data set using the topology database, wherein

the first route is computed using the first route cost data set;

and

the computing the second route comprises

generating a second route cost data set using the pruned topology database, wherein

the second route is computed using the second route cost data set, and

the second route is link-disjoint from the first route.

12. The method of claim 10, wherein the first route and the second route are computed using the shortest path first (SPF) algorithm.

13. The method of claim 1, wherein

the inter-zone link failure is detected by the first border node, and

the first border node initiates the establishing the virtual path over the pre-planned alternative route, in response to detection of the inter-zone link failure.

14. The method of claim 13, wherein the SPF algorithm calculates at least one of

a minimum-cost route, or

a minimum-hop route.

15. The method of claim 13, wherein the SPF algorithm calculates a route that meets a quality of service (QoS).

16. The method of claim 13, wherein the first route and the second route are best-effort routes.

17. The method of claim 1, wherein the establishing the virtual path over the pre-planned alternative route comprises

informing a third border node of the pre-planned alternative route, wherein

the third border node is coupled to an inter-zone link of the pre-planned alternative route,

the informing comprises

transmitting a path creation message from the first border node to the third border node, and

the path creation message comprises the pre-planned alternative route.

18. The method of claim 17, wherein the first border node and the third border node are in a same zone of the plurality of zones.

19. The method of claim 17, wherein the first border node and the third border node are in different zones of the plurality of zones.

20. A network element comprising:

a processor configured to

establish a virtual path over a first route in a backbone zone, wherein

the backbone zone comprises a plurality of zones coupled to one another by a plurality of inter-zone links,

the plurality of zones comprises a source zone and a destination zone, and

the first route comprises at least one inter-zone link between a first border node of the source zone and a second border node of the destination zone;

identify a pre-planned alternative route in the backbone zone, wherein

the pre-planned alternative route is between the first border node of the source zone and the second border node of the destination zone, and

the pre-planned alternative route is automatically determined using a shortest path first (SFP) algorithm, prior to detection of a first inter-zone link failure in the first route;

detect the first inter-zone link failure in the first route;

establish the virtual path over the pre-planned alternative route, in response to detection of the first inter-zone link failure comprising

releasing link bandwidth used by the virtual path, and

restoring the virtual path if the first inter-zone link failure indicates failure of the first border node of the source zone;

detect a second inter-zone link failure in the first route;

configure the pre-planned alternative route to pass through a transit zone upon detecting the second inter-zone link failure, wherein

the transit zone comprises one or more tandem nodes used by the virtual path, and

the tandem node neither originates or terminates the virtual path; and

provide communication between the destination zone and the source zone via the pre-planned alternative route.

21. The network element of claim 20, wherein the processor is configured to:

route the pre-planned alternative route through a transit zone, wherein

the plurality of zones comprises the transit zone, and

the transit zone is distinct from the source zone and the destination zone.

22. The network element of claim 20, wherein the processor is configured to:

request one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

23. The network element of claim 20, wherein the processor is configured to:

establish one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

24. The network element of claim 20, wherein:

the first route meets class of service requirements between the source zone and the destination zone; and

the pre-planned alternative route meets the class of service requirements between the source zone and the destination zone.

25. The network element of claim 24, wherein the processor is configured to:

request one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

26. The network element of claim 24, wherein the processor is configured to:

establish one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

27. A system comprising:

means for establishing a virtual path over a first route in a backbone zone, wherein

the backbone zone comprises a plurality of zones coupled to one another by a plurality of inter-zone links,

the plurality of zones comprises a source zone and a destination zone, and

the first route comprises at least one inter-zone link between a first border node of the source zone and a second border node of the destination zone;

means for identifying a pre-planned alternative route in the backbone zone, wherein

the pre-planned alternative route is between the first border node of the source zone and the second border node of the destination zone, and

the pre-planned alternative route is automatically determined using a shortest path first (SFP) algorithm, prior to detection of a first inter-zone link failure in the first route;

means for detecting the first inter-zone link failure in the first route;

means for establishing the virtual path over the pre-planned alternative route, in response to detection of the first inter-zone link failure comprising

releasing link bandwidth used by the virtual path, and

restoring the virtual path if the first inter-zone link failure indicates failure of the first border node of the source zone;

means for detecting a second inter-zone link failure in the first route;

means for configuring the pre-planned alternative route to pass through a transit zone upon detecting the second inter-zone link failure in the first route, wherein

the transit zone comprises one or more tandem nodes used by the virtual path, and

the tandem node neither originates or terminates the virtual path; and

means for providing communication between the destination zone and the source zone via the pre-planned alternative route.

28. The system of claim 27, comprising:

means for routing the pre-planned alternative route through a transit zone, wherein

the plurality of zones comprises the transit zone, and

the transit zone is distinct from the source zone and the destination zone.

29. The system of claim 27, comprising:

means for requesting one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

30. The system of claim 27, comprising:

means for establishing one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

31. The system of claim 27, wherein:

the first route meets class of service requirements between the source zone and the destination zone; and

the pre-planned alternative route meets the class of service requirements between the source zone and the destination zone.

32. The system of claim 31, comprising:

means for requesting one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

33. The system of claim 31, comprising:

means for establishing one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

34. A non-transitory computer-readable storage medium having instructions encoded therein, wherein the instructions are executable by a processor to perform acts comprising:

establishing a virtual path over a first route in a backbone zone, wherein

the backbone zone comprises a plurality of zones coupled to one another by a plurality of inter-zone links,

the plurality of zones comprises a source zone and a destination zone, and

the first route comprises at least one inter-zone link between a first border node of the source zone and a second border node of the destination zone;

identifying a pre-planned alternative route in the backbone zone, wherein

the pre-planned alternative route is between the first border node of the source zone and the second border node of the destination zone, and

the pre-planned alternative route is automatically determined using a shortest path first (SFP) algorithm, prior to detection of a first inter-zone link failure in the first route;

detecting the first inter-zone link failure in the first route;

establishing the virtual path over the pre-planned alternative route, in response to detection of the first inter-zone link failure comprising

releasing link bandwidth used by the virtual path, and

restoring the virtual path if the first inter-zone link failure indicates failure of the first border node of the source zone;

detecting a second inter-zone link failure in the first route;

configuring the pre-planned alternative route to pass through a transit zone upon detecting the second inter-zone link failure in the first route, wherein

the transit zone comprises one or more tandem nodes used by the virtual path, and

the tandem node neither originates or terminates the virtual path; and

providing communication between the destination zone and the source zone via the pre-planned alternative route.

35. The computer-readable storage medium of claim 34, wherein the instructions are executable by the processor to perform acts comprising:

routing the pre-planned alternative route through a transit zone, wherein

the plurality of zones comprises the transit zone, and

the transit zone is distinct from the source zone and the destination zone.

36. The computer-readable storage medium of claim 34,

wherein the instructions are executable by the processor to perform acts comprising:

requesting one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

37. The computer-readable storage medium of claim 34,

wherein the instructions are executable by the processor to perform acts comprising:

establishing one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route.

38. The computer-readable storage medium of claim 34, wherein:

the first route meets class of service requirements between the source zone and the destination zone; and

the pre-planned alternative route meets the class of service requirements between the source zone and the destination zone.

39. The computer-readable storage medium of claim 38, wherein the instructions are executable by the processor to perform acts comprising:

requesting one or more new intra-zone paths to be established within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.

40. The computer-readable storage medium of claim 38, wherein the instructions are executable by the processor to perform acts comprising:

establishing one or more new intra-zone paths within a zone that is coupled to an inter-zone link of the pre-planned alternative route, wherein

the one or more new intra-zone paths meet the class of service requirements between the source zone and the destination zone.