Method for controlling flood broadcasts in a wireless mesh network
Computer networks with multiple nodes are often required to deliver packets to all nodes in the network, commonly referred to as “flooding.” Flooding is used to deliver multicast and broadcast packets generated by application, network and other layers of the networking stack. Flooding can be done very reliably but less efficiently via node to node “unicast” transmissions, or very efficiently but less reliably via “broadcast” transmissions. In order to balance reliability with efficiency, this invention defines a threshold for the number of neighboring nodes as seen by a given node prior to a flooding operation to determine whether data should be unicast or broadcast. Below that threshold, unicast is used; at or above that threshold, broadcast is used. The invention also incorporates knowledge of nodes seen in turn by neighbor nodes as part of this decision.
1. A method for packet flooding over a computer network comprising two or more network node devices, each of the network node devices comprising at least one transceiver device and a processor that implements a data communications protocol to communicate data to other ones of the network node devices, wherein the data sent is divided into data packets, the method comprising:
(a) maintaining, in each of the network node devices, a system-wide global flooding threshold setting;
(b) maintaining, in each of the network node devices, a count of neighbor network node devices;
(c) for a received packet that specifies flooding, comparing the threshold setting maintained in step (a) to a number of neighbor network node devices of each neighbor network node device;
(d) if it is determined in step (c) that the count is below the threshold setting, using a unicast transmission to forward the received packet to each of the neighbor network node devices in turn; and
(e) if it is determined in step (c) that the count is at or above the threshold setting, forwarding the received packet to each of the neighbor network nodes, wherein step (e) comprises using a broadcast.
2. A method as in claim 1 , wherein step (e) comprises using the broadcast to forward the received packet to all of the neighbor network node devices at once.
3. A method as in claim 1 , wherein each of the network node devices performs step (b) by maintaining a count of its neighbor network node devices and reports any changes to each of its neighbor network node devices on an as-needed basis, tracking what has already been reported to each of the neighbor network node devices in order to minimize a number of reports necessary to send to each of the neighbor network node devices.
4. A method as in claim 1 , wherein the network comprises a wireless mesh network.
5. A method as in claim 1 , wherein step (c) further comprises: for the received packet that specifies flooding, comparing the threshold setting maintained in step (a) also to the count of neighbor network node devices maintained in step (b).
6. A method for packet flooding over a computer network comprising two or more network node devices, each of the network node devices comprising at least one transceiver device and a processor that implements a data communications protocol to communicate data to other ones of the network node devices, wherein the data sent is divided into data packets, the method comprising:
(a) maintaining, in each of the network node devices, a system-wide global flooding threshold setting;
(b) maintaining, in each of the network node devices, a count of neighbor network node devices;
(c) for a received packet that specifies flooding, comparing the threshold setting maintained in step (a) to the count of neighbor network node devices maintained in step (b);
(d) if it is determined in step (c) that the count is below the threshold setting, using a unicast transmission to forward the received packet to each of the neighbor network node devices in turn; and
(e) if it is determined in step (c) that the count is at or above the threshold setting, forwarding the received packet to each of the neighbor network nodes, wherein step (e) comprises using a broadcast;
wherein, for a local count at or above the defined threshold setting, step (e) comprises:
(i) comparing the neighbor count of each neighbor network node device to the threshold setting;
(ii) if the neighbor count of the neighbor network node device is below the threshold setting, using a unicast transmission to forward the flood packet to that neighbor network node device; and
(iii) if the neighbor count of the neighbor network node device is at or above the threshold setting, using a broadcast transmission to forward the flood packet to all neighbor network node devices at once.
7. A method as in claim 6 , wherein step (e) comprises using the broadcast to forward the received packet to all of the neighbor network node devices at once.
8. A method as in claim 6 , wherein each of the network node devices performs step (b) by maintaining a count of its neighbor network node devices and reports any changes to each of its neighbor network node devices on an as-needed basis, tracking what has already been reported to each of the neighbor network node devices in order to minimize a number of reports necessary to send to each of the neighbor network node devices.
9. A method as in claim 6 , wherein the network comprises a wireless mesh network.
10. A method as in claim 6 , wherein step (c) further comprises: for the received packet that specifies flooding, comparing the threshold setting maintained in step (a) also to a number of neighbor network node devices of each neighbor network node device.
11. A system for packet flooding over a computer network comprising two or more network node devices, the network node devices comprising:
at least one transceiver device; and
a processor that implements a data communications protocol to communicate data to other ones of the network node devices, wherein the data sent is divided into data packets, the processor configured for:
(a) maintaining, in each of the network node devices, a system-wide global flooding threshold setting;
(b) maintaining, in each of the network node devices, a count of neighbor network node devices;
(c) for a received packet that specifies flooding, comparing the threshold setting maintained in step (a) to a number of neighbor network node devices of each neighbor network node device;
(d) if it is determined in step (c) that the count is below the threshold setting, using a unicast transmission to forward the received packet to each of the neighbor network node devices in turn; and
(e) if it is determined in step (c) that the count is at or above the threshold setting, forwarding the received packet to each of the neighbor network nodes, wherein step (e) comprises using a broadcast.
12. A system as in claim 11 , wherein the processor is configured to perform step (e) by using the broadcast to forward the received packet to all of the neighbor network node devices at once.
13. A system as in claim 11 , wherein the processor in each of the network node devices is configured to perform step (b) by maintaining a count of its neighbor network node devices and reports any changes to each of its neighbor network node devices on an as-needed basis, tracking what has already been reported to each of the neighbor network node devices in order to minimize a number of reports necessary to send to each of the neighbor network node devices.
14. A system as in claim 11 , wherein the at least one transceiver device comprises a transceiver device for a wireless mesh network.
15. A system as in claim 11 , wherein step (c) further comprises: for the received packet that specifies flooding, comparing the threshold setting maintained in step (a) also to the count of neighbor network node devices maintained in step (b).
16. A system for packet flooding over a computer network comprising two or more network node devices, the network node devices comprising:
at least one transceiver device; and
a processor that implements a data communications protocol to communicate data to other ones of the network node devices, wherein the data sent is divided into data packets, the processor configured for:
(a) maintaining, in each of the network node devices, a system-wide global flooding threshold setting;
(b) maintaining, in each of the network node devices, a count of neighbor network node devices;
(c) for a received packet that specifies flooding, comparing the threshold setting maintained in step (a) to the count of neighbor network node devices maintained in step (b);
(d) if it is determined in step (c) that the count is below the threshold setting, using a unicast transmission to forward the received packet to each of the neighbor network node devices in turn; and
(e) if it is determined in step (c) that the count is at or above the threshold setting, forwarding the received packet to each of the neighbor network nodes, wherein step (e) comprises using a broadcast;
wherein, for a local count at or above the defined threshold setting, the processor is configured to perform step (e) by:
(i) comparing the neighbor count of each neighbor network node device to the threshold setting;
(ii) if the neighbor count of the neighbor network node device is below the threshold setting, using a unicast transmission to forward the flood packet to that neighbor network node device; and
(iii) if the neighbor count of the neighbor network node device is at or above the threshold setting, using a broadcast transmission to forward the flood packet to all neighbor network node devices at once.
17. A system as in claim 16 , wherein the processor is configured to perform step (e) by using the broadcast to forward the received packet to all of the neighbor network node devices at once.
18. A system as in claim 16 , wherein the processor in each of the network node devices is configured to perform step (b) by maintaining a count of its neighbor network node devices and reports any changes to each of its neighbor network node devices on an as-needed basis, tracking what has already been reported to each of the neighbor network node devices in order to minimize a number of reports necessary to send to each of the neighbor network node devices.
19. A system as in claim 16 , wherein the at least one transceiver device comprises a transceiver device for a wireless mesh network.
20. A system as in claim 16 , wherein step (c) further comprises: for the received packet that specifies flooding, comparing the threshold setting maintained in step (a) also to a number of neighbor network node devices of each neighbor network node device.
21. A system for ensuring reliable and efficient packet flooding over a computer network comprising two or more network node devices, the network node devices comprising:
at least one transceiver device; and
a processor that implements a data communications protocol to communicate data to other ones of the network node devices, wherein the data sent is divided into data packets, with each of the data packets being encoded with a protocol header that includes that packet's source address, destination address, transmitter address, receiver address, cost information, and data flags that indicate the type and other attributes of any given packet, the processor configured for:
(a) maintaining, in each of the network node devices, a system-wide global flooding threshold setting;
(b) maintaining, in each of the network node devices, a count of neighbor network node devices;
(c) for a received packet that specifies flooding, comparing the threshold setting maintained in step (a) to the count of neighbor network node devices maintained in step (b);
(d) if it is determined in step (c) that the count is below the threshold setting, using a unicast transmission to forward the received packet to each of the neighbor network node devices in turn; and
(e) if it is determined in step (c) that the count is at or above the threshold setting, forwarding the received packet to each of the neighbor network nodes, wherein step (e) comprises using a broadcast;
wherein, for a local count at or above the defined threshold setting, the processor is configured to perform step (e) by:
(i) comparing the neighbor count of each neighbor network node device to the threshold setting;
(ii) if the neighbor count of the neighbor network node device is below the threshold setting, using a unicast transmission to forward the flood packet to that neighbor network node device; and
(iii) if the neighbor count of the neighbor network node device is at or above the threshold setting, using a broadcast transmission to forward the flood packet to all neighbor network node devices at once.
22. A system as in claim 21 , wherein the processor is configured to perform step (e) by using the broadcast to forward the received packet to all of the neighbor network node devices at once.
23. A system as in claim 21 , wherein the processor in each of the network node devices is configured to perform step (b) by maintaining a count of its neighbor network node devices and reports any changes to each of its neighbor network node devices on an as-needed basis, tracking what has already been reported to each of the neighbor network node devices in order to minimize a number of reports necessary to send to each of the neighbor network node devices.
24. A system as in claim 21 , wherein the at least one transceiver device comprises a transceiver device for a wireless mesh network.