Effective bandwidth path metric and path computation method for wireless mesh networks with wired links

• US 9,240,947 B2
• Filed: 07/26/2013
• Issued: 01/19/2016
• Est. Priority Date: 03/09/2006
• Status: Active Grant

• Current Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Original Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Inventors: Bellur, Bhargav Ramachandra, Prakash, Ravi, Singhal, Amar, Jetcheva, Jorjeta Gueorguieva
• Primary Examiner(s): Duong, Frank
• Application Number:
  US13/952,078
• Publication Number:
  US 20140185454A1
• Time in Patent Office: 907 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

Enhanced mesh network performance is provided by computation of a path metric with respect to multi-hop paths between nodes in a mesh network and determination of a path through the mesh network that is optimal according to the path metric. Information is communicated in the mesh network according to the determined path. Nodes in the mesh network are enabled to communicate via one or more wireless links and/or one or more wired links. The path metric optionally includes an effective bandwidth path metric having elements (listed from highest to lowest conceptual priority) including an inverse of a sustainable data rate, a number of wireless links, and a number of wireless and wired links. The sustainable data rate is a measure of communication bandwidth that is deliverable by a path for a period of time. Accounting is made for interference between contiguous wireless links operating on the same channel.

Claims

1. A method, comprising:

computing, at least in part via a processor, an effective wireless bandwidth for a particular path according to a first technique when a number of contiguous wireless links along the particular path is less than a threshold;

computing, at least in part via the processor, the effective wireless bandwidth according to a second technique when the number is greater than the threshold;

routing traffic, at least in part via the processor, according to a best path determined in accordance with the effective wireless bandwidth;

wherein the first technique comprises calculating a first effective wireless bandwidth as a first function of a reciprocal of an inverse resultant data rate, the inverse resultant data rate being a sum of respective reciprocal bandwidths corresponding to each of the contiguous wireless links; and

wherein the second technique comprises calculating a second effective wireless bandwidth as a second function of a plurality of inverse effective data rates, each of the inverse effective data rates corresponding to a respective set of contiguous wireless links, each of the sets having a respective length equal to the threshold.

2. The method of claim 1, wherein the sets include all sequences of wireless links in the contiguous wireless links having a respective length equal to the threshold.

3. The method of claim 2, wherein the first function is a reciprocal function.

4. The method of claim 2, wherein the second function is a minima function.

5. The method of claim 2, further comprising computing the effective wireless bandwidth according to the second technique when the number is equal to the threshold.

6. The method of claim 2, wherein the best path is through a mesh network that includes the contiguous wireless links.

7. The method of claim 6, further comprising the determining the best path in accordance with the effective wireless bandwidth.

8. The method of claim 6, wherein the processor is included in a node that is part of the mesh network.

9. The method of claim 8, wherein a wireless interface is included in the node.

10. The method of claim 8, wherein a wired interface is included in the node.

11. The method of claim 1, wherein the first function is a reciprocal function and the second function is a minima function.

12. A system, comprising:

means for computing an effective wireless bandwidth for a particular path according to a first technique when a number of contiguous wireless links along the particular path is less than a threshold;

means for computing the effective wireless bandwidth according to a second technique when the number is greater than the threshold;

means for routing traffic according to a best path determined in accordance with the effective wireless bandwidth;

wherein the first technique comprises calculating a first effective wireless bandwidth as a first function of a reciprocal of an inverse resultant data rate, the inverse resultant data rate being a sum of respective reciprocal bandwidths corresponding to each of the contiguous wireless links; and

wherein the second technique comprises calculating a second effective wireless bandwidth as a second function of a plurality of inverse effective data rates, each of the inverse effective data rates corresponding to a respective set of contiguous wireless links, each of the sets having a respective length equal to the threshold.

13. The system of claim 12, wherein the sets include all sequences of wireless links in the contiguous wireless links having a respective length equal to the threshold.

14. The system of claim 13, wherein the first function is a reciprocal function.

15. The system of claim 13, wherein the second function is a minima function.

16. The system of claim 13, further comprising means for computing the effective wireless bandwidth according to the second technique when the number is equal to the threshold.

17. The system of claim 13, wherein the best path is through a mesh network that includes the contiguous wireless links.

18. The system of claim 17, further comprising means for determining the best path in accordance with the effective wireless bandwidth.

19. The system of claim 17, wherein the means are included in a node that is part of the mesh network.

20. The system of claim 12, wherein the first function is a reciprocal function and the second function is a minima function.