Managing fate-sharing in shared-media communication networks

• US 8,954,582 B2
• Filed: 01/14/2014
• Issued: 02/10/2015
• Est. Priority Date: 02/23/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Primary Examiner(s): Blair, Douglas
• Assistant Examiner(s): SHAH, MEHULKUMAR J
• Application Number:
  US14/154,875
• Publication Number:
  US 20140136881A1
• Time in Patent Office: 392 Days
• Field of Search: 709/217, 709/223, 709/224, 714/4.1, 714/4.11, 714/41, 714/47.1, 714/47.2, 714/47.3
• US Class Current: 709/224
• CPC Class Codes: G06F 11/2002 where interconnections or communication control functionality are redundant flexible arrangements for bus networks involving redundancy H04L12/40176
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04W 40/34 Modification of an existing route

Abstract

In one embodiment, a management device receives one or more fate-sharing reports locally generated by one or more corresponding reporting nodes in a shared-media communication network, the fate-sharing reports indicating a degree of localized fate-sharing between one or more pairs of nodes local to the corresponding reporting nodes. The management device may then determine, globally from aggregating the fate-sharing reports, one or more fate-sharing groups indicating sets of nodes having a global degree of fate-sharing within the communication network. As such, the management device may then advertise the fate-sharing groups within the communication network, wherein nodes of the communication network are configured to select a plurality of next-hops that minimizes fate-sharing between the plurality of next-hops.

Claims

1. A method, comprising:

receiving, by a management device, one or more fate-sharing reports, the fate-sharing reports indicating a degree of localized fate-sharing between one or more pairs of nodes local to corresponding reporting nodes;

aggregating the one or more fate-sharing reports;

determining, globally from the aggregated fate-sharing reports, one or more fate-sharing groups indicating sets of nodes having a global degree of fate-sharing within the communication network; and

advertising the fate-sharing groups within the communication network to be used by nodes in the communication network to select a plurality of next-hops that minimizes fate-sharing between the plurality of next-hops.

2. The method as in claim 1, further comprising:

applying a confidence weighting factor to each of the fate-sharing groups.

3. The method as in claim 1, wherein the fate-sharing reports indicate the degree of localized fate-sharing between one or more pairs of nodes based on a ratio of a number of times communication with a specific pair of nodes failed at the same time versus a number of times the communication with the specific pair of nodes did not fail at the same time.

4. A method, comprising:

generating one or more fate-sharing reports by a particular node, the fate-sharing reports indicating a degree of localized fate-sharing between one or more pairs of nodes local to the particular node;

sending the one or more fate-sharing reports to a management device of the communication network;

receiving fate-sharing groups from the management device, the fate-sharing groups indicating sets of nodes having a global degree of fate-sharing within the communication network; and

selecting a plurality of next-hops from the particular node that minimizes fate-sharing between the plurality of next-hops based on the fate-sharing groups.

5. The method as in claim 4, wherein locally generating one or more fate-sharing reports comprises:

detecting a failure of a primary next-hop;

selecting a back-up next-hop;

in response to failure of the back-up next-hop, recording that both the primary next-hop and back-up next-hop failed at the same time;

in response to functionality of the back-up next-hop, recording that the back-up next-hop did not fail at the same time as the primary next-hop; and

determining the degree of localized fate-sharing between the primary next-hop and back-up next-hop based on a comparison between a number of times that both the primary next-hop and back-up next-hop failed at the same time versus a number of times that the back-up next-hop did not fail at the same time as the primary next-hop.

6. The method as in claim 4, wherein locally generating one or more fate-sharing reports comprises:

determining the degree of localized fate-sharing between one or more pairs of nodes based on sending messages to the one or more pairs of nodes, the messages selected from a group consisting of;

data messages;

keepalive messages; and

explicit fate-sharing probe messages.

7. The method as in claim 4, wherein selecting a plurality of next-hops that minimizes fate-sharing comprises:

selecting the plurality of next-hops such that none of the selected next-hops are in a same fate-sharing group as any other selected next-hop.

8. The method as in claim 4, wherein selecting a plurality of next-hops that minimizes fate-sharing comprises:

selecting at least two next-hops of the plurality of next-hops that are in a same fate-sharing group as each other, wherein the at least two next-hops are selected to minimize localized fate-sharing between the at least two next-hops.

9. The method as in claim 4, wherein sending the one or more fate-sharing reports comprises:

sending a particular fate-sharing report in response to the degree of localized fate-sharing between a corresponding particular pair of nodes surpassing a configured threshold.

10. The method as in claim 4, wherein the fate-sharing reports indicate the degree of localized fate-sharing between one or more pairs of nodes based on a ratio of a number of times communication with a specific pair of nodes failed at the same time versus a number of times the communication with the specific pair of nodes did not fail at the same time.

11. The method as in claim 4, further comprising:

determining that the fate-sharing between the plurality of selected next-hops surpasses a given threshold; and

, in response;

activating a redundancy protection scheme over the plurality of selected next-hops.

12. The method as in claim 4, wherein sending the fate-sharing reports comprises one of either including the reports within one or more dedicated report messages or including the reports within routing control messages.

13. The method as in claim 4, further comprising:

determining fate-sharing between a plurality of paths through the communication network; and

selecting a plurality of paths from the particular node that minimizes fate-sharing between the plurality of paths.

14. An apparatus, comprising:

one or more network interfaces;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive one or more fate-sharing reports, the fate-sharing reports indicating a degree of localized fate-sharing between one or more pairs of nodes local to corresponding reporting nodes;

aggregate the one or more fate-sharing reports;

determine, globally from the aggregated fate-sharing reports, one or more fate-sharing groups indicating sets of nodes having a global degree of fate-sharing within the communication network; and

advertise the fate-sharing groups within the communication network to be used by nodes in the communication network to select a plurality of next-hops that minimizes fate-sharing between the plurality of next-hop.

15. The apparatus as in claim 14, wherein the process when executed is further operable to:

apply a confidence weighting factor to each of the fate-sharing groups.

16. An apparatus, comprising:

one or more network interfaces to communicate in a shared-media communication network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

generate one or more fate-sharing reports by a particular node, the fate-sharing reports indicating a degree of localized fate-sharing between one or more pairs of nodes local to the particular node;

send the one or more fate-sharing reports to a management device of the communication network;

receive fate-sharing groups from the management device, the fate-sharing groups indicating sets of nodes having a global degree of fate-sharing within the communication network; and

select a plurality of next-hops from the particular node that minimizes fate-sharing between the plurality of next-hops based on the fate-sharing groups.

17. The apparatus as in claim 16, wherein the process when executed to locally generate one or more fate-sharing reports is further operable to:

detect a failure of a primary next-hop;

select a back-up next-hop;

in response to failure of the back-up next-hop, record that both the primary next-hop and back-up next-hop failed at the same time;

in response to functionality of the back-up next-hop, record that the back-up next-hop did not fail at the same time as the primary next-hop; and

determine the degree of localized fate-sharing between the primary next-hop and back-up next-hop based on a comparison between a number of times that both the primary next-hop and back-up next-hop failed at the same time versus a number of times that the back-up next-hop did not fail at the same time as the primary next-hop.

18. The apparatus as in claim 16, wherein the process when executed to locally generate one or more fate-sharing reports is further operable to:

determine the degree of localized fate-sharing between one or more pairs of nodes based on sending messages to the one or more pairs of nodes, the messages selected from a group consisting of;

data messages;

keepalive messages; and

explicit fate-sharing probe messages.

19. The apparatus as in claim 16, wherein the process when executed to select a plurality of next-hops that minimizes fate-sharing is further operable to:

select the plurality of next-hops such that none of the selected next-hops are in a same fate-sharing group as any other selected next-hop.

20. The apparatus as in claim 16, wherein the process when executed to select a plurality of next-hops that minimizes fate-sharing is further operable to:

select at least two next-hops of the plurality of next-hops that are in a same fate-sharing group as each other, wherein the at least two next-hops are selected to minimize localized fate-sharing between the at least two next-hops.

21. The apparatus as in claim 16, wherein the process when executed to send the one or more fate-sharing reports is further operable to:

send a particular fate-sharing report in response to the degree of localized fate-sharing between a corresponding particular pair of nodes surpassing a configured threshold.

22. The apparatus as in claim 16, wherein the fate-sharing reports indicate the degree of localized fate-sharing between one or more pairs of nodes based on a ratio of a number of times communication with a specific pair of nodes failed at the same time versus a number of times the communication with the specific pair of nodes did not fail at the same time.

23. The apparatus as in claim 16, wherein the process when executed is further operable to:

determine that the fate-sharing between the plurality of selected next-hops surpasses a given threshold; and

, in response;

activate a redundancy protection scheme over the plurality of selected next-hops.

24. The apparatus as in claim 16, wherein the process when executed is further operable to:

determine fate-sharing between a plurality of paths through the communication network; and

select a plurality of paths from the particular node that minimizes fate-sharing between the plurality of paths.