Bandwidth Probe: An End-to-End Bandwidth Measurement Technique in Wireless Mesh Networks (WiMoA 2011 and ICCSEA 2011) Part 1

Abstract

End-to-end Bandwidth Estimation is an important metric for network management and monitoring. It can also improve the effectiveness of congestion control mechanism, audio/video stream adoration and dynamic overlay. In recent years, many techniques have been developed for bandwidth estimation in the wired as well as the last-hop wireless networks, but they under-perform in Wireless Mesh Networks (WMNs). This is because of the lack of understandability of the wireless multi-hop environment. In this paper, we present an active bandwidth measurement technique called Bandwidth Probe based on the packet dispersion principle. It measures the steady state bandwidth of the system while considering the effects of the FIFO cross and CSMA/CA-based contending traffic. We also show how to achieve the stationary state behavior of the system to limit the number of probe packets. On simulation, Bandwidth Probe gives a accurate estimation of the available bandwidth using average convergence time and lower intrusiveness.

Keywords: Bandwidth Probe, WMN, bandwidth estimation, packet train.

Introduction

Wireless Mesh Networks (WMNs)[1] is based on the IEEE 802.11s WLAN standard [3][21]. Being a different type of the architecture, WMNs can decrease the operational and infrastructure cost of traditional wireless network by being built all around the wireless and its self organizing nature. Also, it can resolve the problems of ad-hoc[24][22] network like loose connectivity and limited coverage area by keeping some node stationary which provides wireless backbone for service to the clients. But in actual, there is lack of end-to-end tools to estimate resources like path capacity and available bandwidth which is essential for the congestion avoidance[2], video/audio stream adoration and dynamic overlay[10]. Knowledge of these resources can improve the performance of the WMNs.


WMNs have the following properties as opposed to wired networks as well as last-hop wireless due to which errors may occur in the bandwidth estimation.

1 Fading and Interference. Wireless channels’ properties are highly variable due to fading and interference. Other potentially hidden stations implemented on same or different radio standards using the same frequency band create interference on the wireless medium which can often affect WMNs due to its multiple radio configuration. Its effects can cause high change of the signal-to-noise ratio leading to high bit error rates. Even stations having different coding schemes combined with rate adaptation may be used for compensation and its available bandwidth can change dramatically.

2 Contention. Wireless nodes share the same medium and contend for access to the channel. To avoid collisions, stations listen to the channel to detect nearby transmissions. It is controlled by the MAC protocol and bandwidth estimation is done on assumption that node gets the channel access in FIFO order[4]. This assumption may fail in case of hidden stations, so there is a need of additional mechanisms such as CSMA/CA[23] which handle the contention in a fully distributed manner and follow the random channel allocation to the node.

3 Frequent packet loss. Wireless system manages the packet delivery by stop-and-wait ARQ technique. Retransmission can consume channel capacity and lead to varying one-way delays which can affect the bandwidth estimation.

Two methods are available for the bandwidth estimation- Direct method and iterative method[5]. Spruce[6], WBest[7] and IGI[8] use direct probing with the assumption that link effective capacity (CEffective) is already known and then using the rate response model [14], it calculates the available bandwidth (A). WBest is a two-step algorithm; in the first step its evaluate the link CEffective and then it sends the packet train to evaluate the A. Spruce assumes that the CEffective is already known and directly applies the rate response model to calculate the A. IGI uses probing trains with increasing gaps to evaluate A.

TOPP[9], DietTopp[12] and Pathchirp[13] use the iterative method which do not require the previous knowledge of link CEffective. They use multiple probing rate, aiming to check the behavior of the rate response model and its turning point. TOPP uses trains of packet pairs with increasing rates and apply the rate response model for A estimation. DietTopp uses multiple node case with varying proving rates. Pathchirp increases the probing rates of chirp within a single probe.

These bandwidth estimation tools yield highly unreliable values because of their assumption to develop the bandwidth measurement model by considering only the effect of cross traffic. As discussed, they are based on the rate response model. It assumes the single bit-carrier multiplexing of several users in the FIFO order which is not applicable to WMNs. The contention among users is supported by CSMA/CA which often does not follow the FIFO assumption and nodes get the channel access in distributed manner. Fig.1 shows the traffic in WMNs – cross and contending traffic.

Wired-Wireless Testbed Setup

Fig. 1. Wired-Wireless Testbed Setup

Motivated by the challenges in the existing model and properties of the WMNs, we have proposed a new model in lines with the rate response curve discussed in the next section. Based on the proposed model, we have developed a new algorithm "Bandwidth Probe", which is specially tailored towards WMNs for the A estimation. It is a single stage algorithm which sends the packet trains with certain spacing between the packets. The spacing between the packets in the train depend on the input rate of the packet trains with the assumption that the input rate is always greater than the CEffective of the network. Our main objective is to consider the effect of both cross and CSMA/CA based contending traffic in the steady state system and to reduce the random wireless error during the bandwidth calculation.

The rest of the paper proceeds as follows: In the second section we give the background work and proposed model. In the third section we describe the developed bandwidth estimation algorithm, Bandwidth Probe and its dispersion model that shows its actual behavior. In the last section we describe the analysis, experimental simulation and comparison with the existing tools and methods.

Background and Proposed Model

The rate response curve[14][15] is one of the fundamental model for bandwidth estimation. Such a model places the fluid assumption for the cross traffic that it traverses the FIFO queue where the probing flows. Under the assumption, CEffective of the network is already known and then A of the network is given as

tmp2357_thumb

where n is part of the capacity utilized by the cross traffic. If the input rate and output rate of probe flow are ri and ro respectively, the rate response curve behavior of the networks in the presence of cross traffic can be represented as

tmp2358_thumb

We can also estimate the available bandwidth in a direct way if ri = CEffective. In such a case the A will be

tmp2359_thumb

The probe packets rate can be presented in term of the input gap (A^, output gap(Ao) between the packet pair and packet size(L), ri = L /Ai and ro = L /Ao. As opposed to the above mentioned rate response curve which only considers the effect of cross traffic, an assumption is taken that all the nodes which get the channel access under FIFO mechanism cannot hold any longer in the CSMA/CA based MAC environment.

Model of CSMA/CA based system

Fig. 2. Model of CSMA/CA based system

This is because it often handles the contention in a fully distributed manner and the nodes get the access of the channel in a random distributed manner. So A cannot be accurately derived from (2) in WMNs. Figure. 2 shows the typical model of CSMA/CA based wireless system and its traffic behaviors.

To deal with the effect of CSMA/CA we consider an extra parameter – achievable throughput (TAchievabie). The TAchievable is the average packet dispersion rate at the receiver side. It measures the bandwidth along the direction of probe traffic and later infers the accurate value of A. So with the help of this new parameter we proposed a new model for rate response curve (2) which will be suitable for the WMNs. If input rate of probe traffic ri is described by the following equation: ro= min( ri, TAchievabie ), Dispersion(^Dis) measurement of the receiver side is ADiS=max(ASendeT, ^Receiver).

The above parameters gives the clarity about the value of TAchievable < ri, which will always be valid. So, proposed model for the WMNs is as follows

tmp2361_thumb

Bandwidth Estimation Algorithm

Bandwidth Probe depends on the proposed model mentioned in eq (4) and uses a similar mechanism where the rate of the packet train can be converted into certain spacing of the train’s packets. That shows a direct relation to the gap model of the packet pair dispersion[16][20] at receiver side. It uses the independent packet pairs in the packet trains to calculate CEffective and packet trains for TAchievable. To reduce the effect of the interference and uncertain nature of the wireless environments, it uses the mean value of CEffective and TAchievable to calculate A. In a single probe, it sends N number of packet trains with each packet train having n packets to capture the steady state behavior of the system and detect packet queuing behavior and its transmissions[15] at the wireless node and access point. It sends the packet train with the assumption ri > CEffective that produces the smallest gap between the packets to get the narrow link capacity estimate[17].

Bandwidth Probe

Bandwidth Probe is a single stage algorithm, having three parts to calculate the CEffective, TAchievable and A. Calculation of CEffective and TAchievable will be done parallelly. The sender sends the packet train with 4Sender time gap between each packet pairs and the receiver receives them with ^Receiver time gaps, if Tsendi and Tsendi+1 are the sending times of the ith and i + 1th packet respectively and TReceive± and TReceivei+1 are the receiving times of the ith and i + 1th packet respectively.

Table 1. Bandwidth Probe Algorithm

Bandwidth Probe Algorithmtmp2363_thumb

where ADisi is the dispersion measurement of the packet pair in the packet train at the receiver side. Assume k(n) is the average service delay of the hop-workload by cross traffic. The complete Bandwidth Probe algorithm is described in Table 1.

Bandwidth Estimation during Probe Packet Loss

If the probe packets are lost, Bandwidth Probe runs only on the packet pairs that are received successfully in the packet train. It passes A to the low pass filter. Here, Aold and Acurrent are the old and current available bandwidths respectively.

tmp2364_thumb

For setting the constant value in (5) in packet loss situation we perform an experiment wherein we calculate the throughput of the performed application.

Synchronization and Clock Skew Issues

For successful bandwidth estimation, System needs to rely on a perfectly synchronized clock [25]. Suppose S is the time offset between the sender and the

tmp2365_thumb

Eq. (6) shows the dispersion of the packet pair. Since it includes the time offset between the sender and receiver, the calculated A will not be affected by synchronization issues and the measured samples of dispersion will produce a good estimation. And clock drift can be avoided by considering the mean value of dispersion issues.

Length of Packet Train and Input Gap between Packets

Behavior of the system - Service Delay (sec) vs Number of Packets

Fig. 3. Behavior of the system – Service Delay (sec) vs Number of Packets

The length of packet train is very important in the sense of accuracy, convergence and intrusiveness. We perform an experiment with the same scenario as in section 5-A to discuss the service delay and to retrieve the length of the packet which will produce the transient state. Service delay is the packet wait at the head of the transmission queue until it gains access to the channel and is completely transmitted. Transient state is the state in which the system is neither empty nor in backlog when the probing packet is transmitted. The transitory is maximum when the probe traffic and cross traffic send their fair share. To provide synchronization, we use syn-server which connects both sender and receiver. From fig. 3, we infer that the Service delay of the packets is initially low but gradually its distribution changes as more and more packets started reaching the queue link. In order to achieve the practical train length, we repeat the experiment more than 50 times. After sending 140 packets, we get the steady state of the system in every trial. The gap between the packets depends on ri. So Agender= L / ri. The probing sequence depends on the Pois-son distribution to assure proper interaction with the system and considering no context switch within a packet train accessing.

Next post:

Previous post: