Method and apparatus for maximizing data transmission capacity of a mesh network

• US 20070030811A1
• Filed: 03/10/2006
• Published: 02/08/2007
• Est. Priority Date: 08/02/2005
• Status: Active Grant

• Current Assignee: Trilliant Networks Incorporated
• Original Assignee: SkyPilot Networks Incorporated (Trilliant Networks Incorporated)
• Inventors: Cheng, Linker, Gordon, Paul, Frei, Randall
• Granted Patent: US 7,688,739 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08

Abstract

A mesh network routing protocol for optimizing network data transmission capacity using a cost analysis based upon a links proximity to the gateway or other bandwidth constrained node. Specifically, the protocol computes a plurality of routing costs associated with each data path, compares the routing costs, and then selects the data path associated with the lowest routing cost for the transmission of data. Each link in each of the paths is weighted in view of its proximity to an ingress/egress point to the mesh network or other bandwidth constrained node or link of the network.

Claims

1. A method for maximizing data transmission capacity of a mesh network comprising:

calculating a plurality of routing costs associated with a respective plurality of data paths;

weighting the routing costs depending upon a location of a node within a network;

comparing the weighted routing costs of each data path;

determining a lowest weighted routing cost; and

selecting a data path associated with the lowest weighted routing cost.

2. The method of claim 1 wherein the calculating step further comprises calculating the routing cost using link capacity.

3. The method of claim 1 wherein the calculating step further comprises calculating the routing cost as a scalar value.

4. The method of claim 1 wherein the calculating step further comprises calculating the routing cost as a vector.

5. The method of claim 1 wherein the weighting step further comprises weighting a routing cost higher for a link within the path, when the link is proximate a bandwidth constrained node or link.

6. The method of claim 5 wherein a bandwidth constrained node is a gateway.

7. The method of claim 1 wherein the weighting step comprises weighting an upstream link differently from a downstream link.

8. The method of claim 7 wherein a downstream link weight is double an upstream link weight.

9. The method of claim 1 wherein the calculating step further comprises calculating the routing cost based on a class of service.

10. A method of maximizing data transmission capacity within a mesh network comprising:

transmitting a cost message through a mesh network; and

for each link traversed by the cost message, adding a weighted routing cost to the cost message.

11. The method of claim 10 further comprising:

determining an optimal path through the mesh network using the weighted routing cost within the cost message.

12. The method of claim 10 wherein a weighting factor used for the weighted routing cost depends on proximity of a link to a bandwidth constrained node or link.

13. The method of claim 12 wherein a bandwidth constrained node is a gateway.

14. The method of claim 10 wherein the adding step comprises weighting an upstream link differently from a downstream link.

15. The method of claim 14 wherein a downstream link weight is double an upstream link weight.

16. The method of claim 10 wherein the calculating step further comprises calculating the routing cost based on a class of service.

17. An apparatus for maximizing the data transmission capacity of a mesh network comprising:

a mesh gateway for transmitting a cost message containing a routing cost through the mesh network; and

a plurality of nodes coupled to one another and the mesh gateway, where each of the nodes that receives the cost message computes a weighted routing cost for a link upon which the cost message was received, adds the weighted routing cost to the cost message and forwards the cost message to another node.

18. The apparatus of claim 17 wherein the weighted routing cost is used by the node for selecting a data path to the mesh gateway.

19. The apparatus of claim 17 wherein a weighting value for computing the weighted routing cost is computed as a function of the nodes proximity to the mesh gateway.

20. The apparatus of claim 17 wherein the links are comprised of a downstream and an upstream component and the downstream component is given a greater weighting than the upstream component in calculating the routing cost.