Method and apparatus for maximizing data transmission capacity of a mesh network
View Patent ↗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.
1. A method for maximizing data transmission capacity of a mesh network performed by a computer executing cost analysis software, wherein the mesh network comprises first and second data paths, and wherein the first and second data path comprise first and second pluralities of links, respectively; the method comprising:
the computer calculating the first routing cost for the first data path as a function of at least one first link cost that is weighted as a function of a first proximity of a first link of the first plurality of links to a first element of the mesh network;
the computer calculating the second routing cost for the second data path as a function of at least one second link costs that is weighted as a function of a second proximity of a second link of the second plurality of links to the first element or to a second element of the mesh network;
the computer selecting the first data path when the first routing cost is less than the second routing cost;
the computer selecting the second data path when the second routing cost is less than the first routing cost; and
the computer selecting either the first routing path or the second routing path when the first and second routing costs are equal; and
Wherein the at least one first link cost is less than the at least one second link cost when the second proximity is less than the first proximity, and wherein the at least one second link cost is less than the at least one first link cost when the first proximity is less than the second proximity.
2. The method of claim 1 wherein the at least one first link cost is weighted as a function of the first proximity and a first link capacity of the first link, and wherein the at least one second link cost is weighted as a function of the second proximity and a second link capacity of the second link.
3. The method of claim 1 wherein calculating the first and second routing costs comprises calculating the first and second routing costs as scalars.
4. The method of claim 1 wherein calculating the first and second routing costs comprises calculating the first and second routing costs as vectors.
5. The method of claim 1 wherein each of the first and second elements is any of a given node and given link of the mesh network that is bandwidth constrained.
6. The method of claim 1 wherein the given node is a gateway.
7. The method of claim 1 wherein:
the first link cost is weighted using a first weight when the first link is disposed upstream from a first node of the mesh network;
the first link cost is weighted using a second weight when the first link is disposed downstream from the first node;
the second link cost is weighted using a third weight when the second link is disposed upstream from the first node or from a second node of the mesh network; and
the second link cost is weighted using a fourth weight when the second link is disposed downstream from the first node or from the second.
8. The method of claim 7 wherein: the second weight is double the first weight, and wherein the fourth weight is double the third weight.
9. The method of claim 1 wherein:
the at least one first link cost is weighted as a function of a class of service in lieu of or in addition to the first proximity; and
the at least one second link cost is weighted as a function of a class of service in lieu of or in addition to the second proximity.
10. A method of maximizing data transmission capacity within a mesh network, wherein the mesh network comprises first and second data paths, and wherein the first and second data path comprise first and second pluralities of links, respectively; the method comprising:
transmitting a first cost message through the mesh network via the first data path;
adding, for the first plurality of links traversed by the first cost message, a respective first plurality of link costs to a first routing cost contained in the first cost message, wherein at least one first link cost of the first plurality of link costs is weighted as a function of a first proximity of a first link of the first plurality of links to a first element of the mesh network;
transmitting a second cost message through the mesh network via the second data path;
adding, for the second plurality of links traversed by the second cost message, a respective second plurality of link costs to a second routing cost contained in the second cost message, wherein at least one second link cost of the second plurality link costs is weighted as a function of a second proximity of a second link of the second plurality of links to the first element or to a second element of the mesh network;
routing information over the first data path when the first routing cost is optimal; and
routing the information over the second data path when the second routing cost is optimal; and
Wherein the at least one first link cost is less than the at least one second link cost when the second proximity is less than the first proximity, and wherein the at least one second link cost is less than the at least one first link cost when the first proximity is less than the second proximity.
11. The method of claim 10 further comprising:
determining that the first routing cost is optimal when the first routing cost is less than the second routing cost; and
determining that the second routing cost is optimal when the second routing cost is less than the first routing cost.
12. The apparatus of claim 10 wherein each of the first and second elements is any of a given node and given link of the mesh network that is bandwidth constrained.
13. The method of claim 10 wherein the given node is a gateway.
14. The method of claim 10 wherein:
the first link cost is weighted using a first weight when the first link is disposed upstream from a first node of the mesh network;
the first link cost is weighted using a second weight when the first link is disposed downstream from the first node;
the second link cost is weighted using a third weight when the second link is disposed upstream from the first node or from a second node of the mesh network; and
the second link cost is weighted using a fourth weight when the second link is disposed downstream from the first node or from the second node.
15. The method of claim 14 wherein: the second weight is double the first weight, and wherein the fourth weight is double the third weight.
16. The method of claim 10 wherein:
the at least one first link cost is weighted as a function of a class of service in lieu of or in addition to the first proximity; and
the at least one second link cost is weighted as a function of a class of service in lieu of or in addition to the second proximity.
17. An apparatus for maximizing the data transmission capacity of a mesh network, wherein the mesh network comprises first and second data paths, and wherein the first and second data path comprise first and second pluralities of links, respectively; the apparatus comprising: a mesh gateway and a plurality of nodes coupled to one another and to the mesh gateway via the first and second pluralities of links, wherein:
the mesh gateway is operable to:
originate towards a destination node, via the first data path, a first cost message containing a first routing cost; and
originate towards the destination node, via the second data path, a second cost message containing a second routing cost; and
the plurality of nodes are operable to:
add, for the first plurality of links traversed by the first cost message, a respective first plurality of link costs to the first cost message, wherein at least one first link cost of the first plurality link costs is weighted as a function of a first proximity of a first link of the first plurality of links to a first element of the mesh network; and
add, for the second plurality of links traversed by the second cost message, a respective second plurality of link costs to the second cost message, wherein at least one second link cost of the second plurality link costs is weighted as a function of a second proximity of a second link of the second plurality of links to the first element or to a second element of the mesh network; and
any of the mesh gateway and plurality of nodes are operable to:
routing information over the first data path when the first routing cost is optimal; and
routing the information over the second data path when the second routing cost is optimal; and
Wherein the at least one first link cost is less than the at least one second link cost when the second proximity is less than the first proximity, and wherein the at least one second link cost is less than the at least one first link cost when the first proximity is less than the second proximity.
18. The apparatus of claim 17 , wherein:
the first link cost is weighted using a first weight when the first link is disposed upstream from a first node of the mesh network;
the first link cost is weighted using a second weight when the first link is disposed downstream from the first node;
the second link cost is weighted using a third weight when the second link is disposed upstream from the first node or from a second node of the mesh network;
the second link cost is weighted using a fourth weight when the second link is disposed downstream from the first node or from the second node;
the first weight is less than he second weight; and
the third weight is less than the fourth weight.
19. The apparatus of claim 17 wherein each of the first and second elements is any of a given node and given link of the mesh network that is bandwidth constrained.
20. The apparatus of claim 19 wherein the given node is the mesh gateway.