Routing method and system for a wireless network
View Patent ↗A method and system for selecting a route in a wireless network for the transmission of a data packet between wireless nodes in said network using a modified link-state routing algorithm wherein only a limited number of broadcast messages are generated to synchronize the link-state database throughout the wireless network. A subset of nodes called portal nodes within the network are elected to do the broadcasting for the entire network. Each portal node broadcasts an announcement of its identity to all of the wireless nodes. Each wireless node responds to these broadcasts to select one of the portal nodes as its root portal node. It then 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 of routing a packet to a wireless client in a wireless network, the method comprising:
receiving a first packet at a first network device, wherein the first packet includes a destination network address assigned to the 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 link 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;
dropping the first packet upon detection of a condition associated with a possible broadcast loop, otherwise forwarding the first packet towards the first wireless access point node via the second network device included in the portion of the route, wherein the condition includes detection of a reverse route from the first network device to an original sender of the first packet, the reverse route involving an outgoing network interface of the first network device that is a wireless network interface and the reverse route comprising a next-hop address that is different from a transmitting network interface address of a relaying network device, the first packet being received by the first network device from the transmitting network interface address of the relaying network device.
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 being received from the second network device;
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.
7. 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, the method further comprising:
after 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;
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.
8. The method of claim 1 , further comprising determining the reverse route from the first network device to the original sender of the first packet using a reverse-path-lookup.