Routing method and system for a wireless network
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, at a portal routing device, a packet including a destination network address assigned to a wireless device;
receiving, at the portal routing device, a link-state register message from each of a plurality of non-portal routing devices, the link-state register message comprising backhaul link information and client link information;
aggregating, by the portal routing device, the link-state register messages from the plurality of non-portal routing devices to generate a backhaul link data structure storing the backhaul link information from the plurality of non-portal routing devices and a client link data structure storing the client link information from the plurality of non-portal routing devices, the backhaul link data structure being stored separately from the client link data structure at the portal routing device;
based on the client link data structure, identifying, at the portal routing device, a first wireless non-portal routing device from among the plurality of non-portal routing devices connected to the wireless device;
based on the backhaul link data structure, identifying, at the portal routing device, a route from the portal routing device to the first wireless non-portal routing device; and
wirelessly forwarding the packet from the portal routing device to the wireless device via the first wireless non-portal routing device.
2. The method of claim 1 , further comprising dropping, at the portal routing device, the packet transmitted from a second wireless non-portal routing device in the route, after the packet has been forwarded from the portal routing device.
3. The method of claim 1 , further comprising updating the client link data structure based on a roaming message transmitted from a third wireless non-portal routing device to which the wireless device is newly connected.
4. The method of claim 1 , wherein the backhaul link data structure includes a network address of a second wireless non-portal routing device as a next-hop address for the portal routing device to forward the packet to the first wireless non-portal routing device.
5. The method of claim 1 , wherein the backhaul link data structure includes an identifier of an outgoing network interface of the portal routing device connected to a next wireless non-portal routing device for the portal routing device to forward the packet to the first wireless non-portal routing device.
6. The method of claim 1 , wherein the packet is forwarded in response to the wireless device roaming to the first wireless non-portal routing device from a second wireless non-portal routing device.
7. The method of claim 1 , wherein the backhaul link data structure is unchanged due to an update of the client link data structure in response to the wireless device roaming between a plurality of wireless non-portal routing devices.
8. The method of claim 1 , wherein the client link data structure is shared with the first and other wireless non-portal routing devices in the network.
9. The method of claim 1 , further comprising:
generating, by the portal routing device, a link-state-update message comprising the backhaul link information and the client link information of each of the plurality of non-portal routing devices; and
broadcasting, by the portal routing device, the link-state-update message to the plurality of non-portal routing devices, wherein each of the plurality of non-portal routing devices is configured to be synchronized with one another and the portal routing device based on the link-state-update message.
10. The method of claim 1 , wherein, for each of the plurality of non-portal devices, the backhaul link information comprises logical link information between the non-portal device and an adjacent node of the network and the client link information comprises link information indicating a connection between the non-portal device and the wireless device.
11. A system, comprising:
a plurality of wireless non-portal routing devices; and
a portal routing device configured to:
receive a packet including a destination network address assigned to a wireless device;
receive a link-state register message from each of the plurality of non-portal routing devices, the link-state register message comprising backhaul link information and client link information;
aggregate the link-state register messages from the plurality of non-portal routing devices to generate a backhaul link data structure storing the backhaul link information from the plurality of non-portal routing devices and a client link data structure storing the client link information from the plurality of non-portal routing devices, the backhaul link data structure being stored separately from the client link data structure at the portal routing device;
based on the client link data structure, identify a first wireless non-portal routing device from among the plurality of non-portal routing devices connected to the wireless device;
based on the backhaul link data structure, identify a route from the portal routing device to the first wireless non-portal routing device; and
wirelessly forward the packet from the portal routing device to the wireless device via the first wireless non-portal routing device.
12. The system of claim 11 , wherein the portal routing device is further configured to drop the packet transmitted from a second wireless non-portal routing device in the route, after the packet has been forwarded from the portal routing device.
13. The system of claim 11 , wherein the portal routing device is further configured to update the client link data structure based on a roaming message transmitted from third a wireless non-portal routing device to which the wireless device is newly connected.
14. The system of claim 11 , wherein the backhaul link data structure includes a network address of a second wireless non-portal routing device as a next-hop address for the portal routing device to forward the packet to the first wireless non-portal routing device.
15. The system of claim 11 , wherein the backhaul link data structure includes an identifier of an outgoing network interface of the portal routing device connected to a next wireless non-portal routing device for the portal routing device to forward the packet to the first wireless non-portal routing device.
16. The system of claim 11 , wherein the portal routing device forwards the packet in response to the wireless device roaming to the first wireless non-portal routing device from another wireless non-portal routing device.
17. The system of claim 11 , wherein the backhaul link data structure is unchanged due to an update of the client link data structure in response to the wireless device roaming between a plurality of wireless non-portal routing devices.
18. A portal routing device, comprising:
a processor; and
a memory coupled to the processor storing instructions that when executed cause the processor to:
receive a packet including a destination network address assigned to a wireless device;
receive a link-state register message from each of a plurality of non-portal routing devices, the link-state register message comprising backhaul link information and client link information;
aggregate the link-state register messages from the plurality of non-portal routing devices to generate a backhaul link data structure storing the backhaul link information from the plurality of non-portal routing devices and a client link data structure storing the client link information from the plurality of non-portal routing devices, the backhaul link data structure being stored separately from the client link data structure at the portal routing device;
based on the client link data structure, identify a first wireless non-portal routing device from among the plurality of non-portal routing devices connected to the wireless device;
based on the backhaul link data structure, identify a route from the portal routing device to the first wireless non-portal routing device; and
wirelessly forward the packet from the portal routing device to the wireless device via the first wireless non-portal routing device.
19. The portal routing device of claim 18 , wherein the instructions further cause the processor to:
generate a link-state-update message comprising the backhaul link information and the client link information of each of the plurality of non-portal routing devices; and
broadcast the link-state-update message to the plurality of non-portal routing devices, wherein each of the plurality of non-portal routing devices is configured to be synchronized with one another and the portal routing device based on the link-state-update message.
20. The portal routing device of claim 18 , wherein, for each of the plurality of non-portal devices, the backhaul link information comprises logical link information between the non-portal device and an adjacent node of the network and the client link information comprises link information indicating a connection between the non-portal device and the wireless device.