Wireless mesh routing protocol utilizing hybrid link state algorithms

• US 20060285529A1
• Filed: 06/15/2006
• Published: 12/21/2006
• Est. Priority Date: 06/15/2005
• Status: Active Grant

• Current Assignee: U4EA Wireless, Inc. (Gos networks limited)
• Original Assignee: U4EA Wireless, Inc. (Gos networks limited)
• Inventors: Hares, Susan Kay, Bhandaru, Nehru
• Granted Patent: US 7,856,001 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04W 12/0431 Key distribution or pre-distribution; Key agreement
• CPC Class Codes: H04W 12/0433 Key management protocols
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Systems and methods are described for exchanging and determining routes in packet-switched mesh networks. Nodes in the mesh networks may be coupled via wireless and fixed-wire links. Routing protocols used to determine routes include link state protocols and hybrids of link state and path vector protocols. Type-Length-Value formats are provided to facilitate state information for nodes in the packet switched network, allowing paths to be re-routed through the mesh networks in real-time.

Claims

1. A computer network system comprising:

a plurality of communications nodes in communication via a plurality of wireless channels;

in the plurality of communications nodes, one or more hybrid communications nodes in communication with a wide area network via one or more fixed-wire channels;

a plurality of type-level-value parameters exchanged amongst the plurality of communications nodes via a plurality of network packets, each of the network packets including

a first type-level-value parameter indicating a network routing protocol to be used by the plurality of network packets,

a second parameter indicating a node from the plurality of communications nodes that originated the network packet,

one or more parameters indicating an amount of power available at the originating node,

one or more packets identifying a communications node that is linked directly to the originating node via one or more of a wireless channel from the plurality of wireless channels and a fixed-wire channel from the plurality of fixed wire channels,

one or more packets indicating one or more nodes that neighbor the neighboring node;

wherein each of the communications node is operative to receive the plurality of network packets, read the type-level-value parameters contained therein, and update a database of network paths for communication with the plurality of communications nodes by implementing the routing protocol in response to the type-level-value parameters.

2. The computer network system of claim 1, wherein the plurality of wireless channels include one or more IEEE 802.11 links.

3. The computer network system of claim 1, wherein the plurality of wireless channels include one or more IEEE 802.16 links.

4. The computer network system of claim 1, wherein the one or more fixed-wire channels include one or more IEEE 802.3 links.

5. The computer network system of claim 1, wherein the network routing protocol is a link state protocol.

6. The computer network system of claim 5, wherein the link state protocol is Open Shortest Path First (OSPF).

7. The computer network system of claim 1, wherein the network routing protocol is a link state path vector protocol.

8. The computer network system of claim 1, wherein the originating node is a mobile device, and the plurality of type level value parameters include a current battery life of the originating node.

9. In a computer network system including a plurality of communications nodes connected via a plurality of wireless channels, a method of determining network paths amongst the plurality of communications nodes, the method comprising:

at each node in the plurality of communications nodes, generating a first plurality of network packets, each of the first plurality of network packets including a plurality of network parameters further including

a first one or more parameters indicating one or more network routing protocols used by the node,

a second one or more parameters identifying the node,

a third one or more parameters indicating a status of the power currently available at the originating node,

a fourth one or more packets identifying one or more neighbor nodes that are directly coupled to the node,

a fifth one or more packets identifying one or more nodes that are directly coupled to the one or more neighbor nodes;

receiving, at each node in the plurality of nodes, a second plurality of network packets from the one or more neighbor nodes, the second plurality of network packets including the plurality of network parameters from other nodes in the plurality of communications nodes;

upon receiving the second plurality of network packets, determining a plurality of network paths to the other nodes in the plurality of communications nodes, determining the plurality of network paths further including implementing the one or more network routing protocols in response to the plurality of network parameters.

10. The method of claim 9, wherein the plurality of wireless channels include one or more IEEE 802.11 links.

11. The method of claim 9, wherein the plurality of wireless channels include one or more IEEE 802.16 links.

12. The method of claim 9, wherein the plurality of communications nodes are also in communication via one or more fixed-wire channels.

13. The method of claim 12, wherein the one or more fixed-wire channels include one or more Ethernet links.

14. The method of claim 9, wherein the one or more network routing protocols includes a link state protocol.

15. The method of claim 14, wherein the link state protocol is Open Shortest Path First (OSPF).

16. The method of claim 14, wherein the link state protocol is IS-IS.

17. The method of claim 9, wherein the one or more network routing protocols includes a link state path vector protocol.

18. The method of claim 9, wherein the node is a wireless client device.

19. The method of claim 18, wherein the third one or more parameters indicate a battery life remaining at the wireless client device.

20. A frame-switched communications network comprising:

a plurality of communications nodes coupled by fixed wire and wireless channels;

means for determining a hierarchical subset of nodes in the plurality of communications nodes that are in communication via the fixed wire and wireless channels, wherein the nodes in the hierarchical subset are arranged in a multicast tree hierarchy;

recursive means for determining the multi-cast tree hierarchy, and for alternating the hierarchy in real-time in response to events in the packet-switched communications network;

21. The frame-switched communications network of claim 20 further comprising:

means for developing, exchanging and updating security keys amongst subsets of the hierarchical subset in real-time.