Effective bandwidth path metric and path computation method for wireless mesh networks with wired links
First Claim
1. A system comprising:
- a processor;
at least one interface coupled to the processor;
wherein the processor is enabled to execute instructionsto 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, andto 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.
9 Assignments
0 Petitions
Accused Products
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.
-
Citations
29 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method comprising:
-
evaluating, at least in part via at least one processor, 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, at least in part via the at least one processor, 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, at least in part via the at least one processor, 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, at least in part via the at least one processor, 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. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
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:
-
for each path of a plurality of paths from a first node in a mesh network to each of a respective plurality of other nodes in the mesh network, computing an effective wireless bandwidth according to a first technique if a number of contiguous wireless links along each path is less than a threshold; computing the effective wireless bandwidth for each path according to a second technique if the number is greater than the threshold; identifying a best computed path of the plurality of paths, the best computed path of the plurality of paths having the maximum bandwidth of the computed effective wireless bandwidths, wherein each best computed path is respectively the most efficient communication pathway known between the first node and each of the other nodes; at least in part enabling delivering traffic between the first node and a second node of the other nodes via the most efficient pathway known in accordance with the identifying; 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, the sets of contiguous wireless links comprising all sequences of wireless links in the contiguous wireless links having a respective length equal to the threshold. - View Dependent Claims (18, 19, 20, 21, 22, 23)
-
-
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. - View Dependent Claims (25, 26, 27, 28, 29)
-
Specification