Routing method and system for a wireless network

Abstract

A method and system for selecting a route in a wireless network for the transmission of a data packet between wireless nodes in the network using a modified link-state routing algorithm. A subset of nodes called portal nodes within the network are elected to do the broadcasting for the entire network. A wireless node identifies a unicast route back to its root portal node, and sends a link-state register message to this portal node. These link-state register messages received by each portal node are aggregated by them and are broadcast to each of the wireless nodes for storage. When a data packet is thereafter received by a wireless node from a neighboring node, it detects if the data packet satisfies one of a plurality of predetermined conditions and rebroadcasts the data packet to neighboring wireless nodes if none of the conditions is satisfied.

1 . A method comprising:
 receiving a first packet at a first network device, wherein the packet includes a destination network address assigned to a wireless client;   accessing a client link data structure to identify a first wireless access point node directly connected with the wireless client, wherein the client data structure includes link-state information specifying a wireless link directly connecting the first wireless access point node to the wireless client;   accessing a backhaul link data structure to identify at least a portion of a route from the first network device to the first wireless access point node, wherein the backhaul link data structure includes link-state information specifying a logical link between the first network device and the first wireless access point node, and wherein the logical link includes a second network device that is directly connected with the first network device and that is included in the portion of the route; and   forwarding the first packet towards the first wireless access point node via the second network device included in the portion of the route.   
     
     
         2 . The method of  claim 1 , wherein the backhaul link data structure includes a next-hop address from the first network device to the second network device included in the portion of the route. 
     
     
         3 . The method of  claim 1 , wherein the backhaul link data structure includes an identifier of an outgoing network interface of the first network device connected with the second network device included in the portion of the route. 
     
     
         4 . The method of  claim 1 , wherein:
 accessing the client link data structure comprises retrieving a wireless node identifier associated with the first wireless access point node from the client link data structure;   accessing the backhaul link data structure comprises using the wireless node identifier to retrieve the logical link from the backhaul link data structure.   
     
     
         5 . The method of  claim 1 , wherein the client link data structure and the backhaul link data structure are stored in the first network device. 
     
     
         6 . The method of  claim 1 , wherein the first network device generates the client link data structure and the backhaul link data structure in response to at least one unicast link-state message received from the second network device. 
     
     
         7 . The method of  claim 6 , wherein the second network device includes a portal network device associated with the first network device and the unicast link-state message includes link-state data aggregated from two or more network devices. 
     
     
         8 . The method of  claim 1 , wherein the first packet is sent in response to the wireless client roaming from the first wireless access point node to a second wireless access point node. 
     
     
         9 . The method of  claim 8 , further comprising following accessing the client link data structure to identify the first wireless access point node directly connected with the wireless client, updating the client link data structure to indicate that the wireless client is now directly connected with the second wireless access point node. 
     
     
         10 . The method of  claim 9 , wherein the backhaul link data structure is unchanged in response to the wireless client roaming from the first wireless access point node to the second wireless access point node. 
     
     
         11 . A system comprising:
 a client link data structure including link-state information specifying a wireless link directly connecting a first wireless access point node to a wireless client;   a backhaul link data structure including link-state information specifying a logical link between a first network device and the first wireless access point node;   the first network device configured to:
 receive a first packet including a destination network address assigned to the wireless client; 
 access the client link data structure to determine the first wireless access point node directly connected with the wireless client; 
 access the backhaul link data structure to determine at least a portion of the route from the first network device to the first wireless access point node using the logical link between the first network device and the first wireless access point node, wherein the logical link includes a second network device that is directly connected with the first network device and that is included in the portion of the route from the first network device to the first wireless access point node; 
 forward the first packet towards the first wireless access point node via the second network device included in the portion of the route. 
   
     
     
         12 . The system of  claim 11 , wherein the backhaul link data structure includes a next-hop address from the first network device to the second network device included in the portion of the route. 
     
     
         13 . The system of  claim 11 , wherein the backhaul link data structure includes an identifier of an outgoing network interface of the first network device connected with the second network device included in the portion of the route. 
     
     
         14 . The system of  claim 11 , wherein the first network device is further configured to:
 retrieve a wireless node identifier associated with the first wireless access point node from the client link data structure;   use the wireless node identifier to retrieve the logical link from the backhaul link data structure.   
     
     
         15 . The system of  claim 11 , wherein the first network device generates the client link data structure and the backhaul link data structure in response to at least one unicast link-state message received from the second network device. 
     
     
         16 . The system of  claim 15 , wherein the second network device includes a portal network device associated with the first network device and the unicast link-state message includes link-state data aggregated from two or more network devices. 
     
     
         17 . The system of  claim 11 , wherein the first packet is sent in response to the wireless client roaming from the first wireless access point node to a second wireless access point node. 
     
     
         18 . The system of  claim 17 , wherein the first network device is further configured to update the client link data structure to indicate that the wireless client is now directly connected with the second wireless access point node. 
     
     
         19 . The system of  claim 18 , wherein the backhaul link data structure is unchanged in response to the wireless client roaming from the first wireless access point node to the second wireless access point node. 
     
     
         20 . A system comprising:
 means for receiving a first packet at a first network device, wherein the packet includes a destination network address assigned to a wireless client;   means for accessing a client link data structure to identify a first wireless access point node directly connected with the wireless client, wherein the client data structure includes link-state information specifying a wireless link directly connecting the first wireless access point node to the wireless client;   means for accessing a backhaul link data structure to identify at least a portion of a route from the first network device to the first wireless access point node, wherein the backhaul link data structure includes link-state information specifying a logical link between the first network device and the first wireless access point node, and wherein the logical link includes a second network device that is directly connected with the first network device and that is included in the portion of the route; and   means for forwarding the first packet towards the first wireless access point node via the second network device included in the portion of the route.