Wireless mesh routing protocol utilizing hybrid link state algorithms

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.

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.