Method for utilization-based traffic throttling in a wireless mesh network

Abstract

A system and method for managing congestion in a multi-hop wireless network, employing congestion notification messages. The technology has three main components: a mechanism at the Medium Access (MAC) layer for determining when a given source or transit node is deemed congested; a mechanism at the Network Layer (NL) determining how to propagate this information to applications, including suitably combining overload indications received from neighbors; and a mechanism at the Transport Layer (TL) of each source of traffic for determining when a source is generating excessive traffic, and combining it with Medium Access Control (MAC)-based overload indication from downstream nodes, thus providing a multi-layer approach to traffic throttling.

Claims

1. A method for managing congestion in a multi-hop wireless network comprising a plurality of communication devices communicating packets through a communication medium, comprising: determining a self-congestion parameter at a Medium Access Control (MAC) layer of a respective communication device representing congestion in the multi-hop wireless network; receiving a neighbor congestion parameter from a neighbor communication device of the multi-hop wireless network; propagating information comprising the determined self-congestion parameter of the respective communication device and neighbor congestion parameter from the neighbor communication device through the Medium Access Control (MAC) layer of the respective communication device to the communication medium of the multi-hop wireless network; determining, dependent on the propagated information comprising the neighbor congestion parameter, at a Transport Layer (TL) of the respective communication device, that the respective communication device in the multi-hop wireless network is generating excessive traffic of packets in the communication medium of the multi-hop wireless network, according to at least one criterion; and modulating a flow of packets in the communication medium of the multi-hop wireless network from the respective communication device, dependent on the determining of the excessive traffic of packets, to thereby regulate traffic in the multi-hop wireless network.

2. The method according to claim 1, wherein the Medium Access Control (MAC) layer determines the self-congestion parameter based on at least a Transmit Overhead Utilization (TOU) parameter and a Received/Transmit Utilization (RTU) parameter.

3. The method according to claim 2, wherein the Medium Access Control (MAC) layer employs a Carrier Sense Multiple Access (CSMA) protocol, and imposing a waiting time after sensing of a transmission carrier of the neighbor communication device, and prior to transmission of a packet through the communication medium.

4. The method according to claim 3, wherein the waiting time is dependent on a forced jitter time and a backoff time.

5. The method according to claim 4, wherein the Medium Access Control (MAC) layer measures a Transmit Overhead Utilization (TOU) comprising a time used for transmission of a message comprising at least one packet, the jitter time, and the backoff time used prior to transmission of the message comprising at least one packet, accumulated over a time window period.

6. The method according to claim 5, wherein the Transmit Overhead Utilization (TOU) is expressed as a ratio of time used for transmission of the message over the time window period, and the Transmit Overhead Utilization (TOU) is determined based on:
TOU(t)=(T(t−w,t)+J(t−w,t)+B(t−w,t))/w where: t is the current time, w is the number of seconds in the past that is being considered, the window period, T=T(t.sub.1, t.sub.2) is the total amount of time spent transmitting between times t.sub.1 and t.sub.2, J=J(t.sub.1, t.sub.2) is the total amount of time spent in jitter between times t.sub.1 and t.sub.2, and B=B(t.sub.1, t.sub.2) is the total amount of time spent in backoff between times t.sub.1 and t.sub.2.

7. The method according to claim 4, wherein the Medium Access Control (MAC) layer measures a Received/Transmit Utilization (RTU) comprising a time used for reception of a message comprising at least one packet, expressed as a ratio of the time used for reception of a message comprising at least one packet over a window period.

8. The method according to claim 7, wherein Received/Transmit Utilization (RTU) is determined based on:
RTU(t)=(T(t−w,t)+R(t−w,t))/w where: t is the current time, w is the window period, T(t.sub.1, t.sub.2) is the total amount of time spent transmitting between times t.sub.1 and t.sub.2, and R=R(t.sub.1, t.sub.2) is the total amount of time spent in active receive between times t.sub.1 and t.sub.2.

9. The method according to claim 2, wherein the Transmit Overhead Utilization (TOU) and the Receive/Transmit Utilization (RTU) are a function on T, R, J, B, for f and g:
TOU(t)=f(T(t,t−w)+J(t,t−w)+B(t,t−w),w);
RTU(t)=g(T(t,t−w)+J(t,t−w)+B(t,t−w),w) where: t is a current time, w is the number of seconds in the past that is being considered, a window period, T=T(t.sub.1, t.sub.2) is the total amount of time spent transmitting between times t.sub.1 and t.sub.2, J=J(t.sub.1, t.sub.2) is the total amount of time spent in jitter between times t.sub.1 and t.sub.2, B=B(t.sub.1, t.sub.2) is the total amount of time spent in backoff between times t.sub.1 and t.sub.2, and R=R(t.sub.1, t.sub.2) is the total amount of time spent in active receive between times t.sub.1 and t.sub.2.

10. The method according to claim 2, wherein each of the Transmit Overhead Utilization (TOU) and the Receive/Transmit Utilization (RTU) has a congestion-determination threshold.

11. The method according to claim 10, wherein the Transmit Overhead Utilization (TOU) threshold and the Receive/Transmit Utilization (RTU) threshold are each history-dependent.

12. The method according to claim 10, wherein the Transmit Overhead Utilization (TOU) threshold and Receive/Transmit Utilization (RTU) threshold are each applied with hysteresis.

13. The method according to claim 12, wherein the Medium Access Control (MAC) layer determines the self-congestion parameter of the respective communication device depending on a self-overload status, which indicates a self-overload if and only if the Transmit Utilization Overhead (TOU) is above a hysteresis-dependent threshold or the Receive/Transmit Utilization (RTU) is above a hysteresis-dependent threshold.

14. The method according to claim 12, wherein the Medium Access Control (MAC) layer indicates no self-overload if and only if the Transmit Utilization Overhead (TOU) is below a hysteresis-dependent threshold and the Receive/Transmit Utilization (RTU) is below a hysteresis-dependent threshold.

15. The method according to claim 14, wherein a self-overload status remains at a prior state unless either of the Transmit Utilization Overhead (TOU) and Receive/Transmit Utilization (RTU) are above the hysteresis-dependent threshold or both Transmit Utilization Overhead (TOU) and Receive/Transmit Utilization (RTU) are below the hysteresis-dependent threshold.

16. The method according to claim 2, wherein the Medium Access Control (MAC) layer determines the self-congestion parameter as a self-overload status of the respective communication device dependent on the Transmit Overhead Utilization (TOU) parameter and the Received/Transmit Utilization (RTU) parameter, and the self-overload status is forwarded by the Medium Access Control (MAC) layer to the Transport Layer (TL).

17. The method according to claim 12, wherein the Medium Access Control (MAC) layer receives the neighbor congestion parameter of the neighbor communication device as a respective self-overload status of the neighbor communication device dependent on a respective Transmit Overhead Utilization (TOU) parameter and a Received/Transmit Utilization (RTU) parameter of the neighbor communication device.

18. The method according to claim 17, further comprising maintaining a neighbor-overload status dependent on whether any neighbor communication device indicates a self-overload status, wherein the neighbor-overload status is cleared if no self-overload status is received from any neighbor communication device within a timeout period.

19. The method according to claim 18, further comprising maintaining a net-overload status comprising self-overload status OR neighbor-overload status, further comprising: communicating an alert from the Medium Access Control (MAC) layer of the respective communication device to the Transport Layer (TL) of the respective communication device when the net-overload status changes; setting a TL-overload status to overload if net-overload status is overload and a rate the Transport Layer (TL) is sending packets is in excess of a threshold rate; and limiting a rate at which the Transport Layer (TL) sends packets to the threshold rate if the TL-overload status is overload.

20. The method according to claim 19, further comprising: propagating the TL-overload status, at a Network Layer (NL) of the respective communication device to the multi-hop wireless network, to an application associated with generating the excessive traffic of packets; and throttling traffic from the application dependent on the TL-overload status.

21. A non-transitory computer readable medium for controlling a programmable automated device to manage congestion in a node of a multi-hop wireless network comprising a plurality of communication devices communicating packets through a communication medium, comprising: executable instructions for determining a self-congestion parameter at a Medium Access Control (MAC) layer of a respective communication device representing congestion in the multi-hop wireless network; executable instructions for receiving a neighbor congestion parameter from a neighbor communication device of the multi-hop wireless network; executable instructions for propagating information comprising the determined self-congestion parameter of the respective communication device and neighbor congestion parameter from the neighbor communication device through the Medium Access Control (MAC) layer of the respective communication device to the communication medium of the multi-hop wireless network; executable instructions for determining, dependent on the propagated information comprising the neighbor congestion parameter, at a Transport Layer (TL) of the respective communication device, that the respective communication device in the multi-hop wireless network is generating excessive traffic of packets in the communication medium of the multi-hop wireless network, according to at least one criterion; and executable instructions for modulating a flow of packets in the communication medium of the multi-hop wireless network from the respective communication device, dependent on the determining of the excessive traffic of packets, to thereby regulate traffic in the multi-hop wireless network.

22. A node of a multi-hop wireless network, the multi-hop wireless network comprising a plurality of communication devices communicating packets through a communication medium, the node comprising: a transceiver configured to communicate through the communication medium, under control of a Medium Access Control (MAC) layer and a Transport Layer (TL); and an automated controller which controls the Medium Access Control (MAC) layer, and the Transport Layer (TL), the automated controller being configured to: determine a self-congestion parameter at the Medium Access Control (MAC) layer of the node representing congestion in the multi-hop wireless network; receive a neighbor congestion parameter from a neighbor communication device of the multi-hop wireless network through the transceiver; propagate information comprising the determined self-congestion parameter of the node and neighbor congestion parameter from the neighbor communication device through the Medium Access Control (MAC) layer through the transceiver to the communication medium of the multi-hop wireless network; determine, dependent on the propagated information comprising the neighbor congestion parameter, at the Transport Layer (TL) of the node, that the node is generating excessive traffic of packets in the communication medium of the multi-hop wireless network, according to at least one criterion; and modulate a flow of packets in the communication medium of the multi-hop wireless network from the node, dependent on the determining of the excessive traffic of packets, to thereby regulate traffic in the multi-hop wireless network.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a flowchart of logic behind computation of a self-overload status of a device in an ad hoc network.

(2) FIG. 2 shows a flowchart of logic behind computation of NET-overload, TL-overload and throttling, based on the self-overload determined according to FIG. 1.

(3) FIG. 3 shows a schematic diagram of a prior art communication device.

(4) FIG. 4 shows a schematic diagram of a prior art telephony device and the prior art communication device according to FIG. 3.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(5) MAC Layer: Overload Detection

(6) The overload status at the Media Access Control (MAC) layer is measured via the Transmit Overhead Utilization (TOU) and the Received/Transmit Utilization (RTU).

(7) The Medium Access Control (MAC) Layer employs a Carrier Sense Multiple Access (CSMA) approach. Prior to transmission, there are two kinds of forced waiting times when a node that has a packet to send is nonetheless prohibited from sending in order to minimize chances of packet collisions. The first is a forced jitter before transmitting a packet which happens before the channel is sensed. The second is a backoff which is activated when a node senses the channel busy.

(8) The Transmit Overhead Utilization (TOU) consists of the time used by the message on the radio frequency transmission, including the jitter and the backoff used prior to transmission, accumulated over a window period. It is expressed as the ratio of the utilization time over a window period. Specifically,
TOU(t)=(T(t−w,t)+J(t−w,t)+B(t−w,t))/w

(9) where:

(10) t is the current time,

(11) w is the number of seconds in the past that is being considered (the window period),

(12) T=T(t.sub.1, t.sub.2) is the total amount of time spent transmitting between times t.sub.1 and t.sub.2,

(13) J=J(t.sub.1, t.sub.2) is the total amount of time spent in jitter between times t.sub.1 and t.sub.2, and

(14) B=B(t.sub.1, t.sub.2) is the total amount of time spent in backoff between times t.sub.1 and t.sub.2.

(15) The Received/Transmit Utilization (RTU) consists of the time used by the received message (as soon as detected) on the RF air and the time used by the transmit message on the RF air. It is expressed as the ratio of the utilization time over the window period. Specifically,
RTU(t)=(T(t−w,t)+R(t−w,t))/w

(16) where:

(17) t is the current time,

(18) w is the window period, T(t.sub.1, t.sub.2) is the total amount of time spent transmitting between times t.sub.1 and t.sub.2, and

(19) R=R(t.sub.1, t.sub.2) is the total amount of time spent in active receive between times t.sub.1 and t.sub.2.

(20) Although the above describes a specific function for computing Transmit Utilization Overhead (TOU) and Receive/Transmit Utilization (RTU), any function on T, R, J, B can be used. That is, in general, Transmit Utilization Overhead (TOU) and Receive/Transmit Utilization (RTU) are as follows, for some embodiment off and g.
TOU(t)=f(T(t,t−w)+J(t,t−w)+B(t,t−w),w);
RTU(t)=g(T(t,t−w)+J(t,t−w)+B(t,t−w),w)

(21) For example, f might give a higher weight to transmission time T than jitter J and backoff B.

(22) The window w is a configured parameter. For example, w may be 60 seconds.

(23) The overload flag of a given device, referenced as self-overload, is set to ON or OFF depending on the values of TOU and RTU measured above. In order to minimize oscillations, a “high water mark” and “low water mark” is used, e.g., hysteresis. The flag is set to ON when the TOU reaches more than TOU.sub.high or the RTU reaches more than RTU.sub.high. It is set to OFF when the TOU reaches less than TOU.sub.low and the RTU reaches less than RTU.sub.low.

(24) The values of TOU.sub.high, TOU.sub.low, RTU.sub.high and RTU.sub.low are the high and low water marks for TOU and RTU, and are configurable. In an example implementation, they are set at 0.6, 0.5, 0.4 and 0.3 respectively.

(25) FIG. 1 shows the logic behind the computation of the self-overload status of a device. First the current values of TOU and RTU are compared with the configured “high water marks” as follows. The current value of TOU is compared with the configured value of TOU.sub.high. If TOU exceeds TOU.sub.high, then the device Medium Access Control (MAC) declares its self-overload status as ON. If instead the TOU is less than or equal to TOU.sub.high, then the device proceeds to compare the current value of RTU with the configured value of RTU.sub.high. If RTU exceeds RTU.sub.high, then the device once again declares its self-overload status as ON. If instead RTU is less than or equal to RTU.sub.high, then TOU and RTU are compared with the configured “low water marks” as follows.

(26) The current value of TOU is compared with the configured value of TOU.sub.low. If TOU is less than TOU.sub.low, then the device Medium Access Control (MAC) does not affect any change in its self-overload status. If instead the TOU is greater than or equal to TOU.sub.high, then the device proceeds to compare the current value of RTU with the configured value of RTU.sub.low. If RTU is less than RTU.sub.low, then the device does not affect any change in its status. If instead, the RTU is greater than or equal to RTU.sub.low, then it declares its self-overload status as OFF.

(27) Network Layer: Overload Dissemination

(28) All transmitted packets contain an overload status field that indicates whether or not the sender of the packet is overloaded. A node sets the overload status field to ON if its self-overload status is ON, else it sets it to OFF.

(29) The self-overload status, ON or OFF, of a device is also forwarded to the Transport Layer (TL) of the device.

(30) Devices also maintain a neighbor-overload status to track if any of its neighbors are overloaded. When a device receives a packet with the overload status field ON, it sets its neighbor-overload to ON. The neighbor-overload status returns to OFF after OVERLOAD_STATUS_EXPIRY consecutive seconds without receiving any packet with overload status ON from any of its neighbors. An example value of OVERLOAD_STATUS_EXPIRY is 10 seconds.

(31) A device combines its self-overload status with its neighbor-overload status to create a NET-overload status as follows. If the self-overload status is ON or the neighbor-overload status is ON, the NET-overload status is set to ON, otherwise it is set to OFF. In terms of Boolean operations,
NET-overload=self-overload OR neighbor-overload

(32) Whenever the NET-overload status toggles from ON to OFF or OFF to ON, an alert is sent to the Transport Layer, along with the NET-overload status.

(33) Transport Layer: Throttling

(34) The Transport Layer (TL) receives an alert from the Network Layer. The Transport Layer (TL) uses its own flag called TL-overload which is OFF by default. If the NET-overload status it receives is ON, and it is currently sending more than one packet every TL_PACING seconds on average, then it sets the TL-overload status to ON.

(35) Whenever TL-overload is on, the device regulates the number of packets it sends such that no more than one packet every TL_PACING seconds is sent. For example, a value of 10 seconds may be used for TL_PACING.

(36) Whenever the TL-overload status changes from OFF to ON, an optional indication is sent to any applications that are running over it (in many systems, this is done by having a “socket interface” or equivalent thereof), so that they can choose to alert the user (human or machine) to slow down sending. Similarly, when the TL-overload status changes from ON to OFF, an optional indication is sent. The mechanism for such indication may vary depending upon the context. The user and/or the application may or may not choose to slow down. Either way the Transport Layer (TL) regulates the packet sending the NL as mentioned above.

(37) FIG. 2 shows the logic behind the computation of NET-overload, TL-overload and throttling. To begin, the computational logic first observes the current value of self-overload as determined by the flowchart shown in FIG. 1. If the self-overload is ON, then the device automatically sets its net-overload to be ON. If instead the self-overload is OFF, then the device checks if its neighbor-overload is ON, and if and only if this is the case, the net-overload is set to ON, otherwise setting the net-overload as well as the TL-overload to OFF.

(38) If the net-overload is set to ON, the method further determines whether to throttle traffic, or not, as follows. The device first checks if the current measured value of the PACING (average time interval between consecutive packets) is less than the configured value TL_PACING. If so, the TL-overload is set to ON. It then further proceeds to delay packets such that the PACING is higher than the TL_PACING. It also sends a message to the application to inform it of the TL-overload status. Applications may choose to reduce their sending rate accordingly.

(39) FIG. 3 shows an example physical layout of an embodiment of the communication device technology known as a goTenna®. Note that added hardware and features may be added as desired, but an advantage of the technology is that the design itself can remain simple. A battery 1301 is provided to power the system. This may be, for example, 1350 mAH lithium ion battery, or a standard type 1350 mAH cylindrical cell. A micro USB connector (e.g., USB 2.0) is provided for charging and communications. The device has a circuit board or boards 1303 which hold the processor, memory and radio, for example. A Bluetooth radio 1304 is provided for wireless communication with a smartphone. The MURS, GPRS, or other type radio transceiver broadcasts and receives through the antenna 1302, which may be internal, or provided externally through an SMA connector.

(40) FIG. 4 schematically shows the hardware architecture in more detail. The smartphone, of typical design, has a processor 1406, WiFi radio 1412, Cellular radio 1407, Bluetooth module 1409 (which may be integrated with other components), and an address book 1410. The WiFi radio 1412 communicates though antenna 1413 with a wireless local area network, and can ultimately reach the Internet 1414. The Cellular radio 1407 communicates though antenna 1408 with a cellular network 1411, which can also ultimately reach the Internet 1414.

(41) It is to be understood that the above description is intended to be illustrative, and not restrictive. Many other examples will be apparent to those of skill in the art upon reading and understanding the above description. Although the disclosure has been described with reference to specific examples, it will be recognized that the disclosure is not limited to the examples described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. Accordingly, the specification and drawings are to be regarded in an illustrative sense rather than a restrictive sense. The scope of the disclosure should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.