FOR WIRELESS NETWORK NODES

Field of the Invention

[0001] The present invention relates to a data processing method for reliably detecting node saturation in a wireless network. More particularly, the present invention provides a technique for passively monitoring the nodes of an IEEE 802.1 1 wireless multi-channel network so as to determine whether they are saturated.

Background of the Invention

[0002] An IEEE802.1 1 wireless local area network (WLAN) is a contention-based network wherein all the network nodes that share a common channel must compete with each other in order to win transmission opportunities. As a result of the contention-based nature of channel access, the capacity experienced by a node is not fixed. Consequently, it is not possible to always ensure that a node has sufficient capacity to satisfy its load requirements. In other words, under certain network load conditions a node may not be able to access enough channel bandwidth for transmitting its traffic load. This leads to a condition known as saturation, wherein the node cannot win a sufficient number of transmission opportunities for transmitting its data packets. Node saturation can have a detrimental impact on the performance of a network, because it can lead the nodes into congestion and correspondingly to an unacceptable increase in packet delay and loss, resulting in a poor performance for most applications.

[0003] In an infrastructure network, it is the access point (AP) that is most vulnerable to saturation, due to the asymmetric nature of the traffic flow, since all nodes, APs and clients will experience the same contention for access. However, as the AP needs to access the medium more often, it experiences the shortage of access opportunities more severely than the clients. [0004] Node saturation can also be a significant problem in WLAN mesh networks wherein mesh nodes are required to forward packets received from adjacent nodes. Owing to certain routing decisions, a particular node or set of nodes may at times have a large number of transmission paths directed towards them, whereby such nodes become network bottlenecks and vulnerable to saturation. The issue is compounded in ad-hoc networks, as existing routes may be interrupted due to node mobility and topology changes, with the result that redirected traffic may create new bottleneck nodes. Accordingly, it is important to detect saturation promptly and accurately, for effecting timely network channel changes and remove the conditions conducive of saturation and congestion.

[0005] Three main techniques are known for detecting the presence of saturated nodes on a network. A first technique is for the saturated node to inform neighbouring nodes in the network, that it has become saturated. The node can detect whether it is saturated or not by monitoring its transmission buffer and determining whether it is full or overflowing. Although the measurement of saturation is accurate, the communication of this measurement to neighbour nodes is unreliable, because the saturated node may not be able to announce its saturated condition to its neighbours.

[0006] The second technique is to regularly ping all the network nodes with probe packets for determining whether they are operating normally. Measuring the end-to-end loss or delay by sending probe packets is widely used in detecting the saturated node. However, this technique can also experience a lack of reliable communication with saturated nodes and it does not scale well. The communication of probe packets also consumes network channel bandwidth, which can have a negative impact on network performance due to the increased contention on the medium. [0007] A new technique is required for determining saturation at nodes of a wireless network, which should preferably mitigate the disadvantages associated with the above two techniques. Summary of the Invention

[0008] The present invention provides a distributed method and system, wherein each network node passively monitors the performance of adjacent or "neighbouring" nodes in order to detect if saturation is occurring. Each node uses a different network channel and experiences differing network medium conditions relative to adjacent nodes which it monitors, whereby an error margin will be associated with this technique relative to the first, more accurate technique previously described. However, and advantageously, this technique has no bandwidth overhead because it is passive and does not require a reliable communication path with all adjacent nodes, whether saturated or not. From the perspective of wireless applications, this passive monitor by adjacent neighbour nodes directly is much more convenient.

[0009] According to an aspect of the present invention, there is therefore provided a method of remotely determining saturation at each node of a wireless network, wherein the wireless network comprises a plurality H of communication channels over which a plurality N of nodes communicate data, comprising the steps of capturing packets transmitted by adjacent remote nodes within reception range for a predetermined time interval T interval ; calculating a Capacity Utilization (%CU) of each adjacent node from the captured packets, being the ratio of a network bandwidth used by a node for transmitting its data load and a network bandwidth available under the load conditions ; and comparing each adjacent node %CU against a predetermined threshold parameter for determining a saturated condition.

[00010] In an embodiment of the method according to the invention, the predetermined threshold parameter is preferably a value representative of node saturation probability. [00011] In an embodiment of the method according to the invention, the step of calculating may further comprise calculating traffic load, measuring contention and calculating MAC bandwidth components of each adjacent node. In a variant of this embodiment, the step of calculating traffic load further comprises assuming that a mean load of nodes from which packets cannot be captured is equal to the mean load of the nodes from which packets are captured. In a variant of this further embodiment, the step of measuring contention further comprises assuming that all frames from nodes from which packets cannot be captured are transmitted with a uniform time interval within the predetermined time interval T interval. With a consideration the failed transmitted frames due to collisions, assuming that most collisions involve just two nodes.

[00012] In an embodiment of the method according to the invention, the method preferably comprises the further step of extending the predetermined time interval T/nre/va/ for improving accuracy of %CU.

[00013] In an embodiment of the method according to the invention, the method preferably comprises the further step of reducing the predetermined time interval I interval for accelerating the detection of saturation.

[00014] In an embodiment of the method according to the invention, the method preferably comprises the further step of communicating data representative of the saturation determination to one or more of the adjacent nodes in beacon frames. In a variant of this embodiment, the beacon frames may contain a Capacity Utilization Information Element.

[00015] According to another aspect of the present invention, there is also provided a system comprising a wireless network with a plurality H of communication channels and a plurality N of nodes connected to the network, wherein each node is adapted to capture packets transmitted by adjacent remote nodes within reception range for a predetermined time interval T interval ; calculate a Capacity Utilization (%CU) of each adjacent node from the captured packets, being the ratio of a network bandwidth used by a node for transmitting its data load and a network bandwidth available under the load conditions ; and compare each adjacent node %CU against a predetermined threshold parameter for determining a saturated condition. [00016] In an embodiment of the system according to the invention, the predetermined threshold parameter is again preferably a value representative of node saturation probability. [00017] In an embodiment of the system according to the invention, each node is again adapted to calculate traffic load, measure contention and calculate MAC bandwidth components of each adjacent node, for calculating its %CU.

[00018] In a variant of this embodiment, each node is further adapted to assume that a mean load of nodes from which packets cannot be captured is equal to the mean load of the nodes from which packets are captured, for calculating the traffic load. In a variant of this further embodiment, each node is further adapted to assume that all frames from nodes from which packets cannot be captured are transmitted with a uniform time interval within the predetermined time interval T ^' interval, for measuring contention. Moreover, each node is adapted to assume that most collisions involve just two nodes to halve the fail transmission bandwidth.

[00019] In an embodiment of the system according to the invention, each node is further adapted to extend the predetermined time interval T ^' interval for improving accuracy of %CU.

[00020] In an embodiment of the system according to the invention, each node is further adapted to reduce the predetermined time interval Thtervai for accelerating the detection of saturation.

[00021] In an embodiment of the system according to the invention, each node is further adapted to communicate data representative of the saturation determination to one or more of the adjacent nodes in beacon frames. Such beacon frames preferably contain a Capacity Utilization Information Element.

[00022] According to yet another aspect of the present invention, there is also provided a network node in a wireless network, wherein the wireless network comprises a plurality N of nodes communicating data across a plurality H of channels, comprising monitoring means adapted to capture packets transmitted by adjacent remote nodes within reception range for a predetermined time interval T interval ; calculating means adapted to calculate a Capacity Utilization (%CU) of each adjacent node from the captured packets, being the ratio of a network bandwidth used by a node for transmitting its data load and its node capacity, i.e. a network bandwidth available under the load conditions ; and comparing means adapted to compare each adjacent node %CU against a predetermined threshold parameter for determining a saturated condition.

[00023] According to still another aspect of the present invention, there is also provided a set of instructions recorded on a data carrying medium which, when processed by each data processing terminal of a plurality N thereof connected to a wireless network having a plurality H of communication channels, configures each terminal to perform the steps of capturing packets transmitted by adjacent remote nodes within reception range for a predetermined time interval T interval ; calculating a Capacity Utilization (%CU) of each adjacent node from the captured packets, being the ratio of a network bandwidth used by a node for transmitting its data load and a network bandwidth available under the load conditions ; and comparing each adjacent node %CU against a predetermined threshold parameter for determining a saturated condition.

[00024] For any of the above embodiments and further variants, any in the plurality N of nodes may selected from the group comprising mobile telephone handsets, tablet computers, portable computers, personal digital assistants, portable media players, portable game consoles.

[00025] Other aspects are as set out in the claims herein. Brief Description of the Drawings

[00026] For a better understanding of the invention and to show how the same may be carried into effect, there will now be described by way of example only, specific embodiments, methods and processes according to the present invention with reference to the accompanying drawings in which:

[00027] Figure 1 shows a network environment comprising a network router providing a wireless communication medium and six data processing terminals configured as stations or nodes A, B, C, D, E and estimated node in communication therewith.

[00028] Figure 2 is a logical representation of MAC bandwidth information when a stations access the medium in Figure 1 .

[00029] Figure 3 illustrates that a collision occurs when two stations contend the network medium [00030] Figure 4 illustrates the relationship of Capacity Utilization, node capacity and traffic load of a WLAN node.

[00031] Figure 5 is a logical diagram of an embodiment of the method according to the invention, which may be embodied in each of the stations A, B, C, D and E of Figures 1 .

[00032] Figure 6 is a neighbours information table at remote observer node of Figure 1 . [00033] Figure 7 is a specific logical diagram of an embodiment of the method according to the invention.

[00034] Figure 8 shows the model of error associated with the Capacity Utilization estimation and the related modifications in order to minimize the error.

[00035] Figure 9 illustrates the logical diagram of an embodiment of node saturation detection according to the invention. Detailed Description of the Embodiments

[00036] There will now be described by way of example a specific mode contemplated by the inventors. In the following description numerous specific details are set forth in order to provide a thorough understanding. It will be apparent however, to one skilled in the art, that the present invention may be practiced without limitation to these specific details. In other instances, well known methods and structures have not been described in detail so as not to unnecessarily obscure the description. [00037] With reference to Figure 1 , an example embodiment of a system according to the invention is shown within a networked environment.

[00038] The networked environment includes three data processing terminals A, B, C, D and E hereinafter interchangeably referred to as stations or nodes A, B and C, each with Wireless Local Area Network (WLAN) connectivity. Each station A, B and C has wireless telecommunication emitting and receiving functionality over a wireless local area network ('WLAN') conforming to the IEEE 802.1 1 standard ('Wi-Fi'). In the WLAN, telecommunication is performed as data packets encoding voice, alphanumeric, audio, video and/or image data using the Internet Protocol (IP), Voice data over IP ('VoIP') protocol, Hypertext Transfer Protocol ('HTTP') or Secure Hypertext Transfer Protocol ('HTTPS'), the signal being relayed respectively to or from each station A, B, C, D and E by a wireless router. A typical station A, B, C, D or E for use with the system according to the invention may be any one of a desktop computer, laptop computer, a 'smartphone' and, generally, any sedentary or portable data processing device having at least data processing means, storage means and wireless networking means.

[00039] An embodiment of a passive saturation detection technique according to the invention is described hereafter with reference to Figure 5, suitable for implementation in the environment of Figure 1 . This new technique is based upon each node of the network passively and remotely observing adjacent nodes. In the example therefore, each of stations A, B, C, D and E performs the technique, whereby station A monitors each of stations B and C, station B monitors each of stations A and C, and node or station C monitors each of stations A and B, to determine whether they are saturated. [00040] The method implements a temporal analysis framework which models the way in which the IEEE 802.1 1 MAC mechanism wins transmission opportunities at each station. The critical performance metric produced by the model is the Capacity Utilization (%CU) of a node A, B, C and which is defined as the ratio of the bandwidth utilized by a node in transmitting its load and the bandwidth available under the current load conditions. It constitutes a measure of how close to saturation is a node operating, e.g. whether the node %CU is equal to 100%, which means that the current load is consuming all of the available capacity and cannot win any more transmission opportunities, thus that the node is saturated, or less than 100%.

[00041] There are four main phases involved in the embodiment of the saturation detection method shown in Figure 5: an initial observation phase, an intermediate filtering and processing phase, and a final saturation decision phase.

[00042] Before the observation phase, a C++ program to simulate and model the DCF mechanism, deferral and backoff procedure, re-transmission scheme, and the binary exponential back-off contention window in order to simulate the contention for access under saturation conditions and generate the fitted curves as a function of average contention.

[00043] During the observation phase, each station A, B and C captures packet transmissions from adjacent stations within its network signalling reception range. The station captures the frames that contend for access to the medium and processes the packet transmissions in a specified time interval ( interval). Increasing Ύ interval for observing the transmissions of adjacent stations leads to higher accuracy in detecting saturation; however, and correspondingly, it also leads to an increased detection time and decision delay, which may become unacceptable as it can lead to a higher probability of buffer overflow occurrences. Conversely, reducing Ύ interval for observing the transmissions of adjacent stations correspondingly decreases accuracy in detecting saturation, yet results in a faster saturation detection. It will be readily understood by the skilled reader that Ί interval is a variable, the optimum value of which should be selected according to conditions and factors prevalent in the network environment, such as environmental conditions, both the number N and geographical or topological distribution of stations, signalling noise, besides many other. The value may therefore be user-selected or -adjustable or, preferably still, automatically selected and/or adjustable. In a simple example, automatic selection of the specified time interval ( interval) may for instance depend upon the number of adjacent stations detected at the onset of an observation phase.

[00044] Each station A, B and C subsequently filters and processes the captured frames during the filtering and processing phase, for estimating the %CU value of its adjacent stations. Accordingly, each station A, B, C performs a series of operations which includes calculating the traffic load of adjacent stations, measuring their contention and calculating their MAC bandwidth components. [00045] An example of operation for estimating the %CU value is described hereafter by way of non-limitative example. The node capacity is the bandwidth available under the current load conditions and represents the maximum load that can be achieved by the node provided that the other network nodes maintains their current load.

[00046] If a channel has only one station, the relationship between the four MAC bandwidth components is shown as Figure 2:

BW _{bt r} + BW _idle = t (1)

BW^ = BW _load (k) _{( 2 )}

BW _access (k) + BW _fm (k) = BW _iMg = 1 - BW^ (3)

[00047] If a channel has two stations, the relationship between the four MAC bandwidth components is: B " W"busy = + * B " W "co„lli■si■on

BWioad represents the successfully transmitted frames, while BW collision represents the unsuccessfully transmitted frames. In the case where two or more nodes are contending for access, some bandwidth will be inevitably lost because of collisions between the nodes attempting to access the medium at the same time as shown in Figure 3. All frames, irrespective of whether they were successful or not, contribute to BWbusy.

[00048] For a network with multiple stations, the relationship between the MAC bandwidth components is more complex. The reason is that the time used to gain access the medium is shared between the contending stations.

[00049] The average access time has two components: the average time spent deferring (e.g. waiting for an interval of DIFS to elapse) and the average time spent backing off (e.g. decrementing the backoff counter to zero).

^aeetsi ^ defer ^backoff (^)

[00050] It is assumed that BW collision is negligible, the capacity of node / can be derived as follows:

C _evi m = AEFik) X [l -∑* _k BW _lea , _d (kr}] (6)

[00051 ] The Capacity Utilization (%CU) which is defined as the ratio of the bandwidth utilized by a node in transmitting its load and node capacity. For a node k, its Capacity Utilization can be derived as: ( 7 )

[00052] Each station A, B, C, D and E subsequently performs a Bayesian decision process based upon a %CU threshold parameter during the final decision making phase as Figure 9, in order to output a decision about node saturation for the monitored stations. The threshold parameter can be optimized by selecting an appropriate value for the saturation probability of the station through a minimum error-rate classifier based upon Bayesian decision theory. The optimal CU ^TH corresponds to the probability of node saturation in the network, i.e. the higher probability of node saturation, the lower optimal %CU threshold can be chosen. After the decision, the observing station (e.g. A) can encode the saturation decision information in beacon frames and communicate the beacon frames to its adjacent stations (e.g. B, C), so that they may take preventive actions to avoid further deterioration of data communications.

[00053] It will be readily understood by the skilled reader that the remote and passive measuring of one or more adjacent node's %CU value, will include an error inherent to the differences in the wireless medium as observed by the different stations. For example, errors may arise due to the estimated station having one or more adjacent stations (e.g. station D and E) which cannot be observed by the station (e.g. station B) performing the measurement as shown in Figure 1 . As the observer station and the observed stations do not experience the same medium, the estimation of %CU value performed by the observer station will differ from that experienced by the observed station itself.

[00054] The greater the difference in the state of the medium, for example due to the unobservable adjacent stations of the observed station, the larger the error involved in the estimation of %CU. The main sources of error in the estimation of %CU are the error in the calculation of the adjacent station load and the error in the calculation of the contention experienced by the observed adjacent stations. As a consequence of using a passive remote observation technique to detect node saturation in neighbour stations, errors associated with

%CU value estimation are unavoidable but they may be minimized through one or both of three assumptions, resulting in a more accurate determination of saturation occurrences. [00055] The model of error associated with the remote Capacity Utilization

(%CU) estimator as shown in Figure 9 analysis the factors that influence the accuracy of the estimator. [00056] The first assumption is that the mean load of the unobservable adjacent stations is equal to the mean load of the observable adjacent stations. This assumption has been shown to reduce the error associated with the estimation of %CU for the majority of test cases considered by the inventors.

[00057] For an estimated node k has N neighbours and the neighbour node can monitor M neighbours of node k For the neighbour node, the total neighbour load of node k that can be observed Then using Assumption One to estimate the neighbour load ∑†J _k BW _lBed (j ^' ) is:

Est Obsr Obsr

j B W _los M = B W _{lo ad} (j) + BW _load Q} x—^- i*k }≠*' ( 8 )

[00058] The second assumption is that the contention calculation of the observed adjacent station, as measured by the monitoring station, can be corrected by assuming that all the frames from the unobservable adjacent stations of the observed station are transmitted with a uniform time interval within the measurement interval of interest. This assumption is related to the first assumption, that the observed station and its adjacent stations share the same medium. The number of unobserved frames sent from the neighbour nodes of the observed node by the number of frames can be monitored

The formula can be written as:

„. b„sr .p^^-„Ob _t sr N—

llrio M

M ( 9 ;

[00059] Once a collision occurs at the receiver node, the node cannot observe this failed transmitted frame. However, the node can detect the failed transmission through the next successfully transmitted frame where the retransmission flag. If simply summing all the failed bandwidth of neighbour nodes of observed node, some bandwidth BWcoinsion will be double counted or even multiple counted because of collisions between the nodes attempting to access the medium at the same time. [00060] In order to avoid double counting of the failed bandwidth, halving the load bandwidth of failed transmissions under the assumption that most collisions involve just two nodes.

∑ i SlV _taQ£i O)™ ^sr =∑^ _k BW _lBad Q)^ + ∑ BW _ioad (JY ^ail (10)

[00061 ] The present invention thus provides a technique for passively estimating the %CU of a wireless network node or station with minimal overhead and no bandwidth consumption, and which can serve as generic solution for detecting node saturation. The technique supports packet routing decisions, also known to the skilled person as resource-aware routing, channel selection in multi- radio/multi-channel networks, radio resource management for bandwidth provisioning for VoIP and video streaming services, and admission control.

[00062] The advantages provided by the technique are multiple, and varied. Bandwidth provision for real-time services can be optimised at least computational and bandwidth requirements. The technique allows for the remote and passive detection of saturation in network nodes, which removes the need for inter-node communications, save as to communicating data representative of a saturation condition in a proactive embodiment. The technique allows for admission control, and scales efficiently in view of its peer-to-peer approach, particularly when implemented with assumptions about unobservable stations. The technique is apt to identify the network conditions corresponding to a DDoS (Distributed Denial of Service) attack occurring on a wireless network. [00063] Accordingly, use of the technique is expected to be comparably varied, for example by operators deploying large-scale and dense wireless networks; operators tasked with providing specified QoS (Quality of Service) levels and a corresponding real-time network performance monitoring mechanism for same across large-scale networks; operators with a requirement to improve visibility of network operations, performance and bottlenecks; and operators of wireless network hot spots. [00064] The embodiments in the invention described with reference to the drawings comprise a computer apparatus and/or processes performed in a computer apparatus. However, the invention also extends to computer programs, particularly computer programs stored on or in a carrier adapted to bring the invention into practice. The program may be in the form of source code, object code, or a code intermediate source and object code, such as in partially compiled form or in any other form suitable for use in the implementation of the method according to the invention. The carrier may comprise a storage medium such as ROM, e.g. CD ROM, or magnetic recording medium, e.g. a floppy disk or hard disk. The carrier may be an electrical or optical signal which may be transmitted via an electrical or an optical cable or by radio or other means.

[00065] In the specification the terms "comprise, comprises, comprised and comprising" or any variation thereof and the terms include, includes, included and including" or any variation thereof are considered to be totally interchangeable and they should all be afforded the widest possible interpretation and vice versa.

[00066] The invention is not limited to the embodiments hereinbefore described but may be varied in both construction and detail.