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, each respective communication device comprising a communication transceiver, communicating traffic of packets under control of a Media Access Control (MAC) Layer and a Transport Layer (TL), the method comprising: determining at the Media Access Control (MAC) Layer of a respective communication device a self-congestion parameter; receiving communication congestion parameters from neighboring communication devices through the communication transceiver; determining at the Transport Layer (TL) of the respective communication device, based on at least the received communication congestion parameters, that the respective communication device is generating excessive traffic of packets; and modulating the traffic from the respective communication device selectively dependent on the determination at the Transport Layer (TL) that the respective communication device is generating excessive traffic of packets.

2. The method according to claim 1, wherein the Media Access Control (MAC) Layer determines the self-congestion parameter based on at least a Transmit Overhead Utilization (TOU) parameter.

3. The method according to claim 1, wherein the Media Access Control (MAC) Layer determines the self-congestion parameter based on at least a Received/Transmit Utilization (RTU) parameter.

4. The method according to claim 1, wherein the Media 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.

5. The method according to claim 4, wherein the Media Access Control (MAC) Layer employs a Carrier Sense Multiple Access (CSMA) protocol and senses a transmission collision; further comprising waiting after sensing of a transmission carrier of a neighbor communication device, and prior to transmission of a packet through a communication medium, for a waiting time dependent on a forced jitter time and a backoff time.

6. The method according to claim 4, wherein the Media Access Control (MAC) Layer measures: the Transmit Overhead Utilization (TOU) comprising a time used for transmission of a message comprising at least one packet, a jitter time, and a backoff time used prior to transmission of the message comprising at least one packet, accumulated over a time window period; and the 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.

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

8. The method according to claim 1, wherein the Media Access Control (MAC) Layer determines the self-congestion parameter of the respective communication device depending on a self-overload status, which indicates no self-overload if and only if a Transmit Utilization Overhead (TOU) and a Receive/Transmit Utilization (RTU) are each below a hysteresis-dependent threshold.

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

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

11. The method according to claim 1, further comprising maintaining a neighbor-overload status dependent on whether any neighbor communication device indicates a self-overload status during a period.

12. The method according to claim 1, further comprising: communicating an alert indicating a change in a network-overload status from the Media Access Control (MAC) Layer of the respective communication device to the Transport Layer (TL) of the respective communication device; setting a Transport Layer (TL)-overload status to overload if the network-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 Transport Layer (TL)-overload status is overload.

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

14. A communication node of a multi-hop wireless network, comprising: a communication transceiver for transmitting and receiving information with a communication medium, having an associated Media Access Control (MAC) Layer and a Transport Layer (TL); at least one automated processor configured to: receive a respective neighbor congestion parameter from at least one neighbor communication device of the multi-hop wireless network; broadcast self-congestion parameter determined at the Media Access Control (MAC) Layer, representing congestion in the multi-hop wireless network and the received neighbor congestion parameter through the communication transceiver under control of the Transport Layer (TL); determine at the Transport Layer (TL), dependent on at least the received respective neighbor congestion parameters, that the communication node is generating excessive traffic of packets; and modulate a flow of packets through the communication transceiver dependent on the determining of the excessive traffic of packets; and a memory configured to store the self-congestion parameter and the neighbor congestion parameter.

15. The communication node according to claim 14, wherein the Media Access Control (MAC) Layer employs a Carrier Sense protocol, and the at least one automated processor is configured to determine the self-congestion parameter based on at least a Transmit Overhead Utilization (TOU) parameter, and a Received/Transmit Utilization (RTU) parameter.

16. The communication node according to claim 15, wherein: the at least one automated processor is further configured to impose 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, the waiting time being dependent on a forced jitter time and a backoff time; each of the Transmit Overhead Utilization (TOU) and the Received/Transmit Utilization (RTU) has a congestion-determination threshold; and the Media Access Control (MAC) Layer measures: the 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; and the 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.

17. The communication node according to claim 14, wherein the Media Access Control (MAC) Layer determines the self-congestion parameter of the respective communication device depending on a self-overload status, which indicates no self-overload if and only if a Transmit Utilization Overhead (TOU) and a Receive/Transmit Utilization Received/Transmit Utilization (RTU) are each below a hysteresis-dependent threshold, wherein the self-overload status remains at a prior state unless either of the Transmit Overhead Utilization (TOU) and the Received/Transmit Utilization (RTU) are above the hysteresis-dependent threshold or both the Transmit Overhead Utilization (TOU) and the Received/Transmit Utilization (RTU) are below the hysteresis-dependent threshold.

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

19. The communication node according to claim 14, wherein the at least one automated processor is further configured to: communicate an alert from the Media Access Control (MAC) Layer of the respective communication device to the Transport Layer (TL) of the respective communication device of a change in a net-overload status; set a Transport Layer (TL)-overload status to overload if the net-overload status is overload and a rate the Transport Layer (TL) is sending packets is in excess of a threshold rate; limit a rate at which the Transport Layer (TL) sends packets to the threshold rate if the Transport Layer (TL)-overload status is overload; propagate the Transport Layer (TL)-overload status to an application associated with generating the excessive traffic of packets, at a Network Layer (NL) of the respective communication device to the multi-hop wireless network; and throttle traffic from the application dependent on the Transport Layer (TL)-overload status.

20. A non-transitory computer readable medium storing computer executable instructions for controlling a programmable processor of a communication device to manage congestion in a multi-hop wireless network comprising a plurality of the communication devices, each respective communication device comprising a communication transceiver, communicating traffic of data packets under control of lower-level a Media Access Control (MAC) Layer and a higher-level Transport Layer (TL), comprising: instructions for determining at the Media Access Control (MAC) Layer of a respective communication device a communication congestion parameter; instructions for receiving communication congestion parameters from neighboring communication devices through the Media Access Control (MAC) Layer; instructions for determining at the Transport Layer (TL) of the respective communication device that the respective communication device is generating excessive traffic; and instructions for modulating the traffic from the respective communication device selectively dependent on the received congestion parameters.

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
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.

(9) 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
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.

(10) 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 of 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).

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

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

(13) 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.

(14) 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.

(15) 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.

(16) 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.

(17) Network Layer: Overload Dissemination

(18) 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.

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

(20) 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.

(21) 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

(22) 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.

(23) Transport Layer: Throttling

(24) 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.

(25) 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.

(26) 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.

(27) 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.

(28) 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.

(29) 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.

(30) 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.

(31) 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.