Dynamic multi-path forwarding for shared-media communication networks

• US 8,630,291 B2
• Filed: 08/22/2011
• Issued: 01/14/2014
• Est. Priority Date: 08/22/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shaffer, Shmuel, Hui, Jonathan W., Vasseur, Jean-Philippe
• Primary Examiner(s): Duong, Frank
• Application Number:
  US13/214,844
• Publication Number:
  US 20130051250A1
• Time in Patent Office: 876 Days
• Field of Search: 370/312, 370328-339, 370/349, 370/351, 370389-390, 370/392, 3703955-39552, 370400-401
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

In one embodiment, a quality of one or more links of a particular node in a communication network may be determined, and then whether the quality of the one or more links is below a threshold may also be determined. In response to determining that the quality of at least one of the one or more links is above the threshold, a select one of the at least one of the one or more links with quality above the threshold may be utilized for communication with the particular node. Conversely, in response to determining that the quality of each of the one or more links is below the threshold, multi-path forwarding over a plurality of links of the particular node may be utilized for communication with the particular node.

Claims

1. A method, comprising:

determining a quality of one or more links of a particular node in a communication network wherein the communication with the particular node is from the particular node to a particular destination;

determining the quality of the one or more links as uplinks toward the destination;

determining whether the quality of the one or more links is below a threshold;

in response to determining that the quality of at least one of the one or more links is above the threshold, utilizing a select one of the at least one of the one or more links with quality above the threshold for communication with the particular node; and

in response to determining that the quality of each of the one or more links is below the threshold, utilizing multi-path forwarding over the plurality of links for communication with the node by single-hop multicasting the communication from the particular node over the plurality of uplinks to a plurality of respective receivers.

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

explicitly configuring the plurality of respective receivers as a multicast group prior to single-hop multicasting the communication over the plurality of links to the plurality of respective receivers, the communication indicating the multicast group and the particular destination.

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

implicitly creating a multicast group as the plurality of respective receivers based on the single-hop multicast communication.

4. The method as in claim 3, wherein the implicitly created multicast group is selected from a group consisting of:

all nodes sufficiently receiving the single-hop multicast communication; and

a subset of all nodes sufficiently receiving the single-hop multicast communication based on one or more filters.

5. The method as in claim 1, wherein determining whether the quality of the plurality of links is below the threshold comprises at least one of either:

i) determining the quality of the plurality of links based on respective link metrics in comparison to the threshold; and

ii) determining that a set of previous unicast communication attempts over one or more of the plurality of links have all failed.

6. The method as in claim 1, further comprising

indicating within the communication that the communication utilized multi-path forwarding, wherein intermediate nodes receiving the communication are configured to prevent duplicates of the communication in response to the communication utilizing multi-path forwarding.

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

receiving an acknowledgment for the multi-path communication from a particular receiver in response to that particular receiver having not heard another acknowledgment within a given time period.

8. The method as in claim 7, wherein the time period is selected from a group consisting of a randomized time and a time based on an order of the particular receiver within an explicit multicast group list.

9. An apparatus, comprising:

one or more network interfaces to communicate as one or more local links within a communication network;

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

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

determine a quality of one or more links of a particular node in the communication network wherein the communication with the particular node is from the particular node to a particular destination;

determine the quality of the one or more links as uplinks toward the destination;

determine whether the quality of the one or more links is below a threshold;

in response to determining that the quality of at least one of the one or more links is above the threshold, utilize a select one of the at least one of the one or more links with quality above the threshold for communication with the particular node; and

in response to determining that the quality of each of the one or more links is below the threshold, utilize multi-path forwarding over the plurality of links for communication with the node by single-hop multicasting the communication from the particular node over the plurality of uplinks to a plurality of respective receivers.

10. The apparatus as in claim 9, the process further configured to:

explicitly configure the plurality of respective receivers as a multicast group prior to single-hop multicasting the communication over the plurality of links to the plurality of respective receivers, the communication indicating the multicast group and the particular destination.

11. The apparatus as in claim 10, the process further configured to:

implicitly create a multicast group as the plurality of respective receivers based on the single-hop multicast communication.

12. The apparatus as in claim 11, wherein the implicitly created multicast group is selected from a group consisting of:

all nodes sufficiently receiving the single-hop multicast communication; and

a subset of all nodes sufficiently receiving the single-hop multicast communication based on one or more filters.

13. The apparatus as in claim 10, wherein the determination whether the quality of the plurality of links is below the threshold comprises at least one of either:

i) determine the quality of the plurality of links based on respective link metrics in comparison to the threshold; and

ii) determine that a set of previous unicast communication attempts over one or more of the plurality of links have all failed.

14. The apparatus as in claim 10, the process further configured to:

indicate within the communication that the communication utilized multi-path forwarding, wherein intermediate nodes receiving the communication are configured to prevent duplicates of the communication in response to the communication utilizing multi-path forwarding.

15. The apparatus as in claim 10, the process further configured to:

receive an acknowledgment for the multi-path communication from a particular receiver in response to that particular receiver having not heard another acknowledgment within a given time period.

16. The apparatus as in claim 15, wherein the time period is selected from a group consisting of a randomized time and a time based on an order of the particular receiver within an explicit multicast group list.

17. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

determine a quality of one or more links of a particular node in a communication network;

determine whether the quality of the one or more links is below a threshold;

determine the quality of the one or more links as uplinks toward the destination;

in response to determining that the quality of at least one of the one or more links is above the threshold, utilize a select one of the at least one of the one or more links with quality above the threshold for communication with the particular node; and

in response to determining that the quality of each of the one or more links is below the threshold, utilize multi-path forwarding over the plurality of links for communication with the node by single-hop multicasting the communication from the particular node over the plurality of uplinks to a plurality of respective receivers.

18. The computer-readable media as in claim 17, wherein the communication with the particular node is one of either from the particular node to a particular destination or from a particular source to the particular node.