DYNAMIC MULTI-PATH FORWARDING FOR SHARED-MEDIA COMMUNICATION NETWORKS

• US 20130051250A1
• Filed: 08/22/2011
• Published: 02/28/2013
• 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
• Granted Patent: US 8,630,291 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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;

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 a plurality of links of the particular node for communication with the particular node.

2. The method as in claim 1, wherein the communication with the particular node is from the particular node to a particular destination.

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

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

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.

4. The method as in claim 3, 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.

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

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

6. The method as in claim 5, 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.

7. The method as in claim 2, 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.

8. The method as in claim 2, 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.

9. The method as in claim 2, 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.

10. The method as in claim 9, 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.

11. The method as in claim 1, wherein the communication with the particular node is from a particular source to the particular node.

12. The method as in claim 11, wherein determining whether the quality of the plurality of links is below the threshold comprises:

determining that the quality of each of the one or more links is below the threshold in response to multi-path forwarding having been utilized over the plurality of links of the particular node for communication from the particular node to a particular destination.

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

determining that multi-path forwarding was utilized over the plurality of links of the particular node for communication from the particular node to a particular destination due to weakness of the plurality of links only in a direction from the particular node to the particular destination; and

in response, determining that the quality of each of the one or more links is below the threshold only in response to determining the quality of the plurality of links based on respective link metrics in comparison to the threshold in a direction from the particular source to the particular node.

14. The method as in claim 11, wherein determining whether the quality of the plurality of links is below the threshold comprises:

determining that the quality of each of the one or more links is below the threshold in response to determining the quality of the plurality of links based on respective link metrics in comparison to the threshold.

15. The method as in claim 11, wherein utilizing multi-path forwarding comprises:

generating a plurality of source-routes to the particular node that respectively traverse the plurality of links of the particular node; and

forwarding the communication over the plurality of source-routes.

16. The method as in claim 11, wherein utilizing multi-path forwarding comprises:

determining that a forwarding node was a merge-point for a received uplink multi-path communication from the particular node to a particular destination over a plurality of local links of the forwarding node; and

in response, forwarding communication toward the particular node by the forwarding node over the plurality of local links of the forwarding node.

17. 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;

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 a plurality of links of the particular node for communication with the particular node.

18. The apparatus as in claim 17, wherein the communication with the particular node is from the particular node to a particular destination.

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

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

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.

20. The apparatus as in claim 17, wherein the communication with the particular node is from a particular source to the particular node.

21. The apparatus as in claim 20, wherein the process when executed to determine whether the quality of the plurality of links is below the threshold is further operable to at least one of either:

i) determine that the quality of each of the one or more links is below the threshold in response to multi-path forwarding having been utilized over the plurality of links of the particular node for communication from the particular node to a particular destination; and

ii) determine that the quality of each of the one or more links is below the threshold in response to determining the quality of the plurality of links based on respective link metrics in comparison to the threshold.

22. The apparatus as in claim 20, wherein the process when executed to utilize multi-path forwarding is further operable to:

generate a plurality of source-routes to the particular node that respectively traverse the plurality of links of the particular node; and

forward the communication over the plurality of source-routes.

23. The apparatus as in claim 20, wherein the process when executed to utilize multi-path forwarding is further operable to:

determine that the apparatus was a merge-point for a received uplink multi-path communication from the particular node to a particular destination over a plurality of local links of the apparatus; and

in response, forward communication toward the particular node over the plurality of local links of the apparatus.

24. 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;

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 a plurality of links of the particular node for communication with the particular node.

25. The computer-readable media as in claim 24, 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.