Method of constructing a backup path in an autonomous system

• US 20070091794A1
• Filed: 10/20/2005
• Published: 04/26/2007
• Est. Priority Date: 10/20/2005
• Status: Abandoned Application

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bryant, Stewart, Nalawade, Gargi, Filsfils, Clarence, Ward, David, Scudder, John, Previdi, Stefano, Charles Shand, Ian
• Application Number:
  US11/254,469
• Publication Number:
  US 20070091794A1
• Time in Patent Office: Days
• US Class Current: 370/228
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A method of constructing a backup path in an autonomous system (AS) for failure of a first inter-AS link serving a first set of prefixes is described. The method comprises identifying an alternate inter-AS link serving said plurality of prefixes and constructing a tunnel thereto.

Claims

1-23. -23. (canceled)

24. A method, comprising:

identifying a first inter-autonomous system (AS) link serving a first set of prefixes;

identifying an alternate inter-AS link serving the first set of prefixes; and

constructing a backup tunnel to the alternate inter-AS link.

25. The method as in claim 24, wherein the first inter-AS link and alternate inter-AS link both originate at a first AS, wherein the first AS is one of a stub AS or a transit AS.

26. The method as in claim 24, further comprising:

performing the steps of identifying and constructing at a constructing router serving the first inter-AS link, wherein the alternate inter-AS link comprises a second inter-AS link from a second, backup router.

27. The method as in claim 26, further comprising:

constructing the backup tunnel from the constructing router to the backup router.

28. The method as in claim 24, further comprising:

receiving a candidate backup path notification from one or more routers in the AS.

29. The method as in claim 28, further comprising:

identifying by the candidate backup path notification at least one of a nexthop and priority of the candidate backup path.

30. The method as in claim 29, further comprising:

selecting a candidate backup path meeting at least one of a nexthop or priority criterion as a path for the backup tunnel.

31. The method as in claim 24, further comprising:

identifying failure of the first inter-AS link; and

in response, utilizing the backup tunnel to the alternate inter-AS link.

32. The method as in claim 31, further comprising:

utilizing the backup tunnel with an outer tunnel encapsulation, wherein the outer tunnel encapsulation is an address of an end point of the alternate inter-AS link; and

utilizing the backup tunnel with an inner tunnel encapsulation, wherein the inner tunnel encapsulation is an end point nexthop.

33. The method as in claim 24, wherein the backup tunnel is selected from the group consisting of:

a Multi-Protocol Label Switching (MPLS) tunnel;

a Layer-2 Tunneling Protocol (L2TP) tunnel; and

a Generic Routing Encapsulation (GRE) tunnel.

34. The method as in claim 24, further comprising:

constructing the backup tunnel to an end point of the alternate inter-AS link.

35. Software encoded in one or more computer-readable media and when executed operable to:

identify a first inter-autonomous system (AS) link serving a first set of prefixes;

identify an alternate inter-AS link serving the plurality of prefixes; and

construct a backup tunnel to the alternate inter-AS link.

36. An apparatus, comprising:

means for identifying a first inter-autonomous system (AS) link serving a first set of prefixes;

means for identifying an alternate inter-AS link serving the plurality of prefixes; and

means for constructing a backup tunnel to the alternate inter-AS link.

37. An apparatus comprising:

one or more processors;

a network interface communicatively coupled to the one or more processors and configured to communicate one or more packet flows among the one or more processors in a network; and

a memory adapted to store one or more sequences of instructions that when executed operable to i) identify a first inter-autonomous system (AS) link serving a first set of prefixes, ii) identify an alternate inter-AS link serving the plurality of prefixes, and iii) construct a backup tunnel to the alternate inter-AS link.

38. A method, comprising:

identifying a first inter-autonomous system (AS) path serving a first set of prefixes from a first AS;

identifying an alternate inter-AS path serving the first set of prefixes;

constructing a backup path advertisement identifying the alternate inter-AS path; and

advertising the backup path advertisement within the first AS.

39. The method as in claim 38, wherein the backup path is advertised as a virtual private network (VPN) route.

40. The method as in claim 39, wherein a set of components in the first AS comprise a common VPN having a unique route distinguisher.

41. The method as in claim 38, wherein the backup path advertisement comprises an “

ADD-PATH”

advertisement in the Border Gateway Protocol (BGP).

42. The method as in claim 38, further comprising:

constructing the backup path advertisement at an advertising router upon detection of an adjacent inter-AS link.

43. The method as in claim 38, further comprising:

receiving the backup path advertisement at a route server; and

distributing the advertisement from the route server.

44. The method as in claim 38, wherein the first AS is one of a stub AS or a transit AS.

45. The method as in claim 38, further comprising:

identifying failure of a first inter-AS path serving one or more pre-fixes; and

tunneling to an advertised inter-AS path serving the one or more pre-fixes.