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

• US 20140185454A1
• Filed: 07/26/2013
• Published: 07/03/2014
• 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
• Granted Patent: US 9,240,947 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-29. -29. (canceled)

30. A method, comprising:

computing, at least in part via a processor, an effective wireless bandwidth for a path according to a first technique when a number of contiguous wireless links along the 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;

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.

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

32. The method of claim 31, wherein the first function is a reciprocal function.

33. The method of claim 31, wherein the second function is a minima function.

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

35. The method of claim 31, further comprising computing a best path through a mesh network that includes the contiguous wireless links.

36. The method of claim 35, further comprising determining the best path at least in part according to the effective wireless bandwidth.

37. The method of claim 36, routing traffic according to the best path.

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

39. The method of claim 38, wherein a wireless interface is included in the node.

40. The method of claim 38, wherein a wired interface is included in the node.

41. A system, comprising:

means for computing an effective wireless bandwidth for a path according to a first technique when a number of contiguous wireless links along the 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;

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.

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

43. The system of claim 42, wherein the first function is a reciprocal function.

44. The system of claim 42, wherein the second function is a minima function.

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

46. The system of claim 42, further comprising means for computing a best path through a mesh network that includes the contiguous wireless links.

47. The system of claim 46, further comprising means for determining the best path at least in part according to the effective wireless bandwidth.

48. The system of claim 47, routing traffic according to the best path.

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