Effective Bandwidth Path Metric and Path Computation Method for Wireless Mesh Networks with Wired Links

• US 20070211636A1
• Filed: 12/29/2006
• Published: 09/13/2007
• Est. Priority Date: 03/09/2006
• Status: Active Grant

• Current Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Original Assignee: FireTide Incorporated (UNICOM Global, Inc.)
• Inventors: Prakash, Ravi, Singhal, Amar, Jetcheva, Jorjeta, Bellur, Bhargav
• Granted Patent: US 7,768,926 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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 system comprising:

a processor;

at least one interface coupled to the processor;

wherein the processor is enabled to execute instructions

to determine respective first and second current costs associated with traversing respective first and second current paths of links in a mesh network, each of the current paths being associated with a source node and a destination node of the mesh network,

to replace a first minimum cost having an associated first best path with the first current cost and to replace the first best path with the first current path if the first current cost is less than the first minimum cost, and

to replace a second minimum cost having an associated second best path with the second current cost and to replace the second best path with the second current path if the second current cost is less than the second minimum cost;

wherein the last link of the first current path is a wired link and the last link of the second current path is a wireless link; and

wherein at least one of the first and the second current costs is calculated based at least in part on bandwidth reduction due to any contiguous wireless links along at least one of the first and the second current paths.

2. The system of claim 1, wherein the at least one interface is at least one of a wired interface and a wireless interface.

3. The system of claim 1, wherein the processor is further enabled to execute other instructions to select a routing path that corresponds to the respective best path associated with the minimum of the first and the second minimum costs.

4. The system of claim 1, wherein the interface is a first wireless interface and further comprising a second wireless interface coupled to the processor.

5. The system of claim 4, wherein the processor and the wireless interfaces are implemented in a node of the mesh network, and at least one of the wireless interfaces is active along at least one of the paths.

6. The system of claim 1, wherein at least one of the paths includes a series of segments.

7. The system of claim 6, wherein at least one specific path includes a series of segments, and the specific path is one of the current paths or one of the best paths.

8. The system of claim 7, wherein at least one of the segments has at least one wireless sub-segment and at least one wired sub-segment.

9. The system of claim 8, wherein at least one of the at least one wireless sub-segment and the at least one wired sub-segment have at least two links.

10. A method comprising:

evaluating respective first and second current costs associated with traversing respective first and second current paths of links in a mesh network;

if the first current cost is less than a first minimum cost associated with a first best path, then replacing the first minimum cost with the first current cost and replacing the first best path with the first current path;

if the second current cost is less than a second minimum cost associated with a second best path, then replacing the second minimum cost with the second current cost and replacing the second best path with the second current path;

wherein the last link of the first current path is a wired link and the last link of the second current path is a wireless link; and

wherein at least one of the first and the second current costs is calculated based at least in part on bandwidth reduction due to any contiguous wireless links along at least one of the first and the second current paths.

11. The method of claim 10, further comprising selecting a routing path that corresponds to the respective best path associated with the minimum of the first and the second minimum costs.

12. The method of claim 11, further comprising routing traffic along the routing path.

13. The method of claim 10, wherein the evaluating comprises determining an effective bandwidth for any contiguous wireless links along any of the first and the second current paths.

14. The method of claim 13, wherein the effective bandwidth of each respective contiguous wireless link is a function of at least one of an inverse sustainable data rate, a count of wireless links, and a count of wired and wireless links.

15. The method of claim 10, wherein the evaluating is implemented by executing programmed instructions by a processor included in a node along one of the paths.

16. The method of claim 15, wherein the node includes at least one of an Ethernet compatible interface associated with the wired link and an 802.11 compatible interface associated with the wireless link.

17. A computer readable medium having a set of instructions stored therein which when executed by a processing element causes the processing element to perform operations comprising:

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

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

wherein the first technique includes 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 includes 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, the sets of contiguous wireless links including all sequences of wireless links in the contiguous wireless links having a respective length equal to the threshold.

18. The computer readable medium of claim 17, wherein the first function is a reciprocal function.

19. The computer readable medium of claim 17, wherein the second function is a minima function.

20. The computer readable medium of claim 17, the operations further comprising computing the effective wireless bandwidth according to the second technique if the number is equal to the threshold.

21. The computer readable medium of claim 17, the operations further comprising computing a best path through a mesh network that includes the contiguous wireless links, the best path being determined at least in part according to the effective wireless bandwidth.

22. The computer readable medium of claim 21, the operations further comprising routing traffic according to the best path.

23. The computer readable medium of claim 22, wherein the processor is included in a node that is part of the mesh network.

24. A system comprising:

means for determining an effective wireless bandwidth for a path according to one of a plurality of techniques, the path having a length of contiguous wireless links;

means for selecting one of the techniques based at least in part on the length;

means for determining a best path through a mesh network that includes the contiguous wireless links and at least one wired link;

means for routing traffic according to the best path; and

wherein the means for selecting selects a first one of the techniques if the length is less than a threshold, and selects a second one of the techniques if the length is greater than the threshold.

25. The system of claim 24, wherein:

the first technique comprises means for calculating the effective wireless bandwidth as 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

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

26. The system of claim 25, wherein the function calculates the effective wireless bandwidth corresponding to a minimum of reciprocals of the plurality of inverse effective data rates.

27. The system of claim 24, wherein the at least one wired link is interfaced to a node of the mesh network that is also an endpoint of the contiguous wireless links.

28. The system of claim 27, wherein the contiguous wireless links are a first set of contiguous wireless links, the wired link is a first wired link, and the first set of contiguous wireless links and the first wired link in combination are a first segment;

and the mesh network further includes a second segment having a second set of contiguous wireless links and a second wired link.

29. The system of claim 27, wherein the wired link is a first wired link;

and the first set of contiguous wireless links, the first wired link, and a second wired link contiguous with the first wired link are in combination a segment.