Network path selection for multi-homed edges to ensure end-to-end resiliency

• US 8,724,456 B1
• Filed: 09/14/2010
• Issued: 05/13/2014
• Est. Priority Date: 05/19/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Hong, Bin William, Mehta, Apurva, Ramakrishnan, Ramanarayanan, Sun, Huaxiang, Kamath, Prakash
• Primary Examiner(s): Lee, Jae Y
• Assistant Examiner(s): Voltaire, Jean F
• Application Number:
  US12/881,999
• Time in Patent Office: 1,337 Days
• Field of Search: 370/216, 370/221, 370/225, 370/227, 370/238, 370/256, 370/257
• US Class Current: 370/225
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3041 where the computing system component is an input/output interface interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00
• CPC Class Codes: G06F 11/3055 Monitoring arrangements for monitoring the status of the computing system or of the computing system component, e.g. monitoring if the computing system is on, off, available, not available error or fault processing without redundancy G06F11/0703; error detection or correction by redundancy in data representation G06F11/08; error detection or correction by redundancy in operation G06F11/14; error detection or correction by redundancy in hardware G06F11/16

Abstract

Techniques are described for selecting an alternate path for end-to-end service data traffic that traverses multi-homed routers that provide the service to customer networks. For example, as described herein, a router that is a member of a first multi-homing set connected to a layer two (L2) network with one of a plurality of first access links. The router advertises a status of one of the first access links to a second multi-homing set connected to the first multi-homing set with one or more core links. A core link database stores advertised status information for access links of the first and second multi-homing set. Upon a link failure, a path selector selects a core link to transport service data traffic and directs a switch module to switch to active a status a first access links that connects to a router in the first multi-homing set connected to the selected core link.

Claims

1. A method comprising:

storing a plurality of access link condition records with a first router that is a member of a first multi-homing set of a plurality of routers each connected to a first layer two (L2) network with a respective one of a plurality of first access links, wherein the first multi-homing set communicates with a second L2 network using a plurality of second access links to provide a first service to the first and second L2 networks, wherein each access link condition record comprises a state field that denotes whether a corresponding access link is operational with respect to the first service and a status field that denotes whether the corresponding access link is designated as active for transporting first service data traffic, wherein the plurality of access link condition records stored by the first router includes a corresponding access link condition record for each of the first access links and for each of the second access links;

detecting, with the first router, a failure of a service link that connects the first and second L2 networks; and

in response to detecting the failure, applying a path selection policy with the first router to select a data path between the first and second L2 networks for the first service data traffic and to cause one of the plurality of routers in the first multi-homing set to switch a status of at least one of the first access links or one of the second access links to active.

2. The method of claim 1,

wherein the first service is a bridging service and the plurality of routers in the first multi-homing set bridge the first and second L2 networks by bridging first service data traffic between the active one of the first access links and the active one of the second access links,

wherein the failed service link is one of the first access links or second access links, and

wherein applying a path selection policy with the first router comprises applying the path selection policy to the access link condition records.

3. The method of claim 1,

wherein a protection link connects the first router to a second one of the plurality of routers in the first multi-homing set, and

wherein applying the path selection policy with the first router causes the first router to send first service data traffic to the second router via the protection link.

4. The method of claim 1,

wherein the first access links form a first multi-chassis link aggregation group and the second access links form a second multi-chassis link aggregation group, and

wherein applying the path selection policy with the first router causes the first multi-homing set to switch a status of one of the first access links to active and to switch a status of one of the second access links to active.

5. The method of claim 1,

wherein a plurality of core links of a layer three (L3) network interconnect the plurality of routers in the first multi-homing set to a plurality of routers in a second multi-homing set,

wherein each router in the second multi-homing set is connected to the second L2 network with a respective one of the plurality of second access links,

wherein one of the core links is designated active for transporting first service data traffic, and further comprising:

storing a plurality of core link condition records with the first router, wherein each core link condition record comprises a state field that denotes whether a corresponding one of the core links is operational with respect to the first service, a locally advertised field that denotes a status of one of the first access links that connects to a router in the first multi-homing set that is connected to the corresponding one of the core links, and a peer advertised field that denotes a status of one of the second access links that connects to a router in the second multi-homing set that is connected to the corresponding one of the core links,

wherein applying a path selection policy comprises applying the path selection policy to the core link condition records.

6. The method of claim 5, detecting, with the first router, a failure of a service link comprises detecting a failure of one of the core links.

7. The method of claim 5, further comprising:

sending, with the first router, a first access link advertisement via each one of the core links that is connected to the first router, wherein the first access link advertisement indicates a status of one of the first access links that connects to the first router;

receiving, with the first router, a second access link advertisement via a first one of the core links that is connected to the first router, wherein the second access link advertisement indicates a status of one of the second access links that connects to one of the routers in the second multi-homing set that connects to the first one of the core links; and

updating a peer advertised field in a corresponding one of the core link condition records for the first core link with the status indicated in the second access link advertisement.

8. The method of claim 7, wherein applying the path selection policy comprises applying the path selection policy in response to receiving the second access link advertisement.

9. The method of claim 5, wherein the core links interconnect the plurality of routers in the first multi-homing set to the plurality of routers in the second multi-homing set in a partial mesh.

10. The method of claim 5, further comprising:

sending, with the first router, one or more of the core link condition records to other routers in the first multi-homing set;

receiving, with the first router, one or more updated core link condition records from the other routers in the first multi-homing set; and

updating the core link condition records stored by the first router with the updated core link condition records.

11. The method of claim 5, wherein applying a path selection policy with the first router to select a data path between the first and second L2 networks for the first service data traffic comprises applying a path selection policy to the core link condition records to select one of the core links to activate for transporting first service data traffic.

12. The method of claim 11,

wherein the first multi-homing set is a primary multi-homing set, and wherein the path selection policy prioritizes, for selection by routers that are members of the primary multi-homing set, core links that correspond to core link condition records having a locally advertised field set to active status, and further comprising:

selecting one of the core links corresponding to a first one of the core link condition records to activate for transporting first service data traffic when the first core link condition record has a locally advertised field set to active status.

13. The method of claim 12, wherein applying a path selection policy with the first router to select a data path cause one of the plurality of routers in the first multi-homing set to switch a status of at least one of the first access links or second access links to active comprises switching to active a status of a standby one of the first access links that connects to one of the routers in the first multi-homing that is also connected to the selected core link.

14. The method of claim 11,

wherein the first multi-homing set is a secondary multi-homing set, and wherein the path selection policy prioritizes, for selection by routers that are members of the secondary multi-homing set, core links that correspond to core link condition records having a peer advertised field set to active status, and further comprising:

selecting one of the core links corresponding to a first one of the core link condition records to activate to transport first service data traffic when the first core link condition record has a peer advertised field set to active status.

15. The method of claim 14, wherein applying a path selection policy with the first router to select a data path cause one of the plurality of routers in the first multi-homing set to switch a status of at least one of the first access links or second access links to active comprises switching to active a status of a standby one of the first access links that connects to one of the routers in the first multi-homing that is also connected to the selected core link.

16. The method of claim 12, wherein the first access links form a first multi-chassis link aggregation group having a first group identifier and the second access links form a second multi-chassis link aggregation group having a second group identifier, and further comprising

determining, with the first router, that the first multi-homing set is the primary multi-homing set by comparing the first group identifier and second group identifier and selecting the greater identifier.

17. The method of claim 1,

wherein the first multi-homing set communicates with a second L2 network to provide a second service to the first and second L2 networks,

wherein applying a path selection policy with the first router causes one of the plurality of routers in the first multi-homing set to switch a status of at least one of the first access links or second access links to active only when the first service has a higher priority than the second service.

18. The method of claim 1, further comprising:

comparing a number of services operating over each of the first access links, wherein applying a path selection policy with the first router causes one of the plurality of touters in the first multi-homing set to switch a status of at least one of the first access links to active only when a standby one of the first access links is transporting data traffic for a fewer number of services than an active one of the first access links.

19. The method of claim 1, wherein the first service is a VPLS instance.

20. A first router that is a member of a first multi-homing set of a plurality of routers in a layer three (L3) network each connected to a first layer two (L2) network with a respective one of a plurality of first access links to provide a first service to the first L2 network, wherein the first router comprises:

a pseudowire setup module to establish one or more core links to interconnect the plurality of routers in the first multi-homing set to one or more routers of a plurality of routers in the L3 network in a second multi-homing set, wherein each router in the second multi-homing set is connected to the second L2 network with a respective one of a plurality of second access links, wherein one of the core links has an active status to transport first service data traffic;

an access link monitor to store a plurality of access link condition records, wherein each access link condition record comprises a state field that denotes whether a corresponding access link is operational with respect to the first service and a status field that denotes whether the corresponding access link is designated active for transporting the first service data traffic, wherein the plurality of access link condition records stored by the access link monitor includes a corresponding access link condition record for each of the first access links and for each of the second access links;

a core link database to store a plurality of core link condition records, wherein each core link condition record comprises a state field that denotes whether a corresponding one of the core links is operational with respect to the first service, a locally advertised field that denotes a status of one of the first access links that connects to a router in the first multi-homing set that is connected to the corresponding one of the core links, and a peer advertised field that denotes a status of one of the second access links that connects to a router in the second multi-homing set that is connected to the corresponding one of the core links;

a connection check module to detect failures of one or more of the core links connected to the first router and to set the state fields of core link condition records in core link database that correspond to the failed core links to a down value;

a path selection policy;

a plurality of interface cards to send and receive packets;

a switch module to switch a status of one of the first access links to activate to transport first service data traffic; and

a path selector to apply the path selection policy,

wherein the connection check module detects a failure of one of the core links, and

wherein the path selector, in response the failure, applies the path selection policy to the core link database to select one of the core links to activate to transport first service data traffic and to direct the switch module to switch to active a status of one of the first access links that connects to the router in the first multi-homing set that connects to the selected core link.

21. The first router of claim 20, further comprising:

an exchange module to send core link condition records to other routers of the first multi-homing set and to update core link database with updated core link condition records received from the other routers of the first multi-homing set.

22. The first router of claim 20,

wherein a protection link connects the first router to a second one of the plurality of routers in the first multi-homing set, and

wherein the path selector applies the path selection policy to cause the first router to send first service data traffic to the second router via the protection link.

23. The first router of claim 20, further comprising a link advertiser to:

send a first access link advertisement via each one of the core links that is connected to the first router, wherein the first access link advertisement indicates a status of one of the first access links that connects to the first router;

receive a second access link advertisement via a first one of the core links that is connected to the first router, wherein the second access link advertisement indicates a status of one of the second access links that connects to one of the routers in the second multi-homing set that connects to the first one of the core links; and

update a peer advertised field in a corresponding one of the core link condition records for the first core link with the status indicated in the second access link advertisement.

24. The first router of claim 23, wherein the path selector applies the path selection policy in response to the link advertiser receiving the second access link advertisement.

25. The first router of claim 20,

wherein the first multi-homing set is a primary multi-homing set, and wherein the path selection policy prioritizes, for selection by routers that are members of the primary multi-homing set, core links that correspond to core link condition records having a locally advertised field set to active status, and

wherein the path selector applies the path selection policy to select one of the core links corresponding to a first one of the core link condition records to activate to transport first service data traffic when the first core link condition record has a locally advertised field set to active status.

26. The first router of claim 25, wherein the switch module, to switch a status of one of the first access links to activate to transport first service data traffic, switches to active a status of a standby one of the first access links that connects to one of the routers in the first multi-homing that is also connected to the selected core link.

27. The first router of claim 20,

wherein the first multi-homing set is a secondary multi-homing set, and wherein the path selection policy prioritizes, for selection by routers that are members of the secondary multi-homing set, core links that correspond to core link condition records having a peer advertised field set to active status, and

wherein the path selector applies the path selection policy to select one of the core links corresponding to a first one of the core link condition records to activate to transport first service data traffic when the first core link condition record has a peer advertised field set to active status.

28. The first router of claim 27, wherein the switch module, to switch a status of one of the first access links to activate to transport first service data traffic, switches to active a status of a standby one of the first access links that connects to one of the routers in the first multi-homing that is also connected to the selected core link.

29. A system comprising:

a first layer two (L2) network;

a second L2 network;

a first multi-homing set comprising a plurality of routers in a layer three (L3) network, wherein each of the plurality of routers is connected to the first L2 network with a respective one of a plurality of first access links to provide a first service to the first L2 network;

a second multi-homing set comprising a plurality of routers in a L3 network, wherein each of the plurality of routers is connected to the second L2 network with a respective one of a plurality of second access links to provide the first service to the second L2 network; and

a plurality of core links to interconnect the plurality of routers in the first multi-homing set with the plurality of routers in the second multi-homing set,

wherein a first router in the first multi-homing set comprises a first core link database to store a plurality of core link condition records, wherein each core link condition record comprises a state field that denotes whether a corresponding one of the core links is operational with respect to the first service, a locally advertised field that denotes a status of one of the first access links that connects to a router in the first multi-homing set that is connected to the corresponding one of the core links, and a peer advertised field that denotes a status of one of the second access links that connects to a router in the second multi-homing set that is connected to the corresponding one of the core links,

wherein the first router in the first-multihoming set stores a plurality of access link condition records, wherein each access link condition record comprises a state field that denotes whether a corresponding access link is operational with respect to the first service and a status field that denotes whether the corresponding access link is designated as active for transporting first service data traffic, wherein the plurality of access link condition records stored by the first router includes a corresponding access link condition record for each of the first access links and for each of the second access links,

wherein, upon failure of a first one of the core links, the first router selects one of the core links to activate to transport first service data traffic when the core link condition record in the first core link database corresponding to the selected core link has a locally advertised field set to active status, and switches to active a status of a standby one of the first access links that connects to one of the routers in the first multi-homing that is also connected to the selected core link,

wherein a second router in the second multi-homing set comprises a second core link database to store a plurality of core link condition records, and

wherein, upon failure of the first one of the core links, the second router selects the core link selected by the first router to activate to transport first service data traffic when the core link condition record in the second core link database corresponding to the selected core link has a peer advertised field set to active status.