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

What the Algorithm Really Does

In WMNs, dispersion due to both contending and cross traffic are at wireless nodes and access point. So traffic would not be FIFO manner. This causes random delay between two successive packets. Hence, to trace the behavior of WMNs, Bandwidth Probe measures two variables, CEffective and TAchievable. CEffective indicates the maximum capability of the wireless networks delivered to the network layer traffic. Wireless network adopts the dynamic rate to send the traffic, so the CEffective is defined as the continuous function of packet size L and time t.

tmp2367_thumb_thumb

where A(t) is the packet pair dispersion at time t. We can also model this equation in discrete manner.

tmp2368_thumb_thumb


where A(i) is the Dispersion of ith packet pair. The second parameter TAchievable measures the dispersion of the packets due to the contention between the probe and contending traffic.


tmp2369_thumb_thumb

TAchievabie is also known as the average packet dispersion rate i.e. the average time used to forward one single packet. It uses only the effect of contending traffic along the direction of the probing flow.

As discussed before, the relation can be established among the measured parameters by Bandwidth Probe and A as A < TAchievable < CEffective. With the assumption of Bandwidth Probe ri > CEffective, proposed model (4) can be described if ri = CEffective then

tmp2370_thumb[2]

A can be derived from (10) but if

tmp2371_thumb[2]

following equation

tmp2372_thumb[2]

To derive the bound of A, if CEffective =0 and TAchievable < CEffective/2 then A will be 0 otherwise it can be derived from the above equations. If A is equal to CEffective, this implies that the network is idle (no cross traffic). Otherwise, the leftover portion of CEffective by the cross and contending traffic is A.

Dispersion Model of Bandwidth Probe Algorithm

Interaction among TSend, TRece,ive and Cross Traffic related Process (x)

Fig. 4. Interaction among TSend, TRece,ive and Cross Traffic related Process (x)

For considering the dispersion model assume that the probing sequence enters the transmission queue at instance {Tsendi, i=0,1,..,n-1}, their departure instance (i.e. instance at which they completely leave the transmission queue) is defined by {TReceiveri, i=0,1,..,n-1}.

Bandwidth Probe assumes negligible transmission time as compared to the dispersion and service delay. If cross traffic related process forms the sequence |xi,i=0,1, .,n-1}, fig. 4 shows the inter departure time at the output path. The output gap between the packet is defined as

tmp2374_thumb[2]

This can be expressed as the cross traffic related process form of sequence as follows

tmp2375_thumb[2]

The calculated value of AReceiver and ASender can establish the relation between dispersion and ri and ro of rate response curve described in (2).

tmp2376_thumb[2]

From the above discussion, we infer that rate of packet trains can be used for the interaction with traversing system. Considering the cross traffic as the offered load, the dispersion equations can be modeled as dispersion perspective where E[.] is the limiting average of a sample of a path process.

If

tmp2377_thumb[2]

utilization of the cross traffic in FIFO order the output dispersion is the function of the average

tmp2378_thumb[2]

and service delay ( Vi) of ith packets when they are contending for the medium then

tmp2379_thumb[2]

is the average service delay of the hop-

If

tmp2380_thumb[2]

is the average service delay of the hop-workload by cross traffic. The following equation can describe the aggregate bound

 

tmp2381_thumb[2]

The above equations shows the behavior of the rate response curve in the steady state. The output dispersion at the receiver’s side denoted by equations (15) and (16) is used to calculate the TAchievabie given in (9).

Analysis and Experimental Results

In this section we present the simulation results and analysis of the proposed model. We have used 802.11b/g standard for simulation and the nodes are configured to CSMA/CA; so simulated data packets are preceded by an RTS/CTS exchange [23]. The header size is as per the standard- RTS has 20 bytes, CTS has 14 bytes, ACK has 14 bytes and MAC has 34 bytes. In each of the subsections, we have run the simulation 50 times and the given result is the mean of all the estimated results.

Measurement of Available Bandwidth by Different Packet Sizes

In this simulation, we have created a topology with wired and wireless nodes and access point. The wired link capacity is 30 Mbps and the wireless channel is using the CMU wireless extension[18]. The wireless channel is tuned on the IEEE 802.11b based lucent way eLAN card at 5.5 Mbps with no mobility, with the effective transmission range as 250 meters and interference range as 550 meters. The origin of the Probe packet is the wired node and destination is the wireless node. Ad hoc On-Demand Distance Vector (AODV) [18] is as the route agent. Each wireless node is configured in the multi-hop scenario. The results estimated by Bandwidth Probe are as expected. Figure.5 shows that if the size of the probe packet is large then the estimated capacity is high and if its size is small then the estimated capacity is less. This is because, if the packet size is small, more number of ACKs contend for the medium with other packets at the link layer.

Result of available bandwidth estimation (without interference)

Fig. 5. Result of available bandwidth estimation (without interference)

Bandwidth estimation along a chain of nodes with different packet lengths

Fig. 6. Bandwidth estimation along a chain of nodes with different packet lengths

Measurement of Available Bandwidth on Chain Topology

With the same scenario as in subsection A, all the wireless nodes are placed in a row. The result has come out favourably as expected[17] and the effective end-to-end capacity decreases as the length of chain grows. Bandwidth Probe is able to achieve the end-to-end capacity estimation that closely matches the analytical prediction (of the single hop capacity).

Table 2. Estimated Available Bandwidth by Different Techniques (in Mbps)

Tuned Capacity / Cross Traffic

54 / 2 Mbps

48/2 Mbps

36/2 Mbps

24/2 Mbps

IGI/PTR

3.726

3.312

2.484

1.656

Pathload

3.672

3.26

2.448

1.632

Pathchirp

10.612

9.544

7.408

5.272

WBest

6.696

5.952

4.464

2.976

Bandwidth Probe

7.452

6.624

4.496

3.312

Ground Truth

8.64

7.68

5.76

3.84

Comparison with the Existing Bandwidth Estimation Techniques

In this subsection, we have created a test bed having two wired nodes with a capacity of 100 Mbps, one access point and four wireless nodes. Each wireless node is placed equi-distant from each other and from access point. Each wireless node is using 802.11g standard. Table 2 shows the different link rate of the wireless nodes and rate of cross traffic in the different cases. The effective transmission and interference range is 250m and 550m respectively. We have set one of the wired nodes as the source and a wireless node as the destination. Cross traffic is created by CBR UDP with packet size as 1000 bytes same as probe packet size. The value ground truth of A is given by analytical method.

Table 2 clearly shows that the Bandwidth Probe estimates A more accurately than the rest of the measurement techniques. IGI/PTR and Pathload always underestimates A while Pathchirp overestimates it. WBest measures a good approximation of A but it is not considering the steady state behavior of the system and hence the estimated A can vary over time and produce inaccurate results.

Figure 7 shows the mean relative error in all the four cases mentioned in Table 2. IGI/PTR and Pathload gives high relative error in the estimation. Pathchirp and WBest show better accuracy and lower relative error. But, Bandwidth Probe is having the best accuracy and least relative error. It is also evident that Bandwidth Probe is having larger variability than the other estimation techniques. Intrusiveness is the probe byte sent by the estimation tools during measurement.

Mean error while estimating available bandwidth

Fig. 7. Mean error while estimating available bandwidth

Intrusiveness in different techniques

Fig. 8. Intrusiveness in different techniques

Convergence of different techniques

Fig. 9. Convergence of different techniques

Figure 8 shows that Bandwidth Probe has much lower intrusiveness as compared to the other techniques with values as low as 130 Kbytes. IGI/PTR and Patchirp have an intrusiveness of 570 Kbytes and 450 Kbyte respectively. Pathload has the largest intrusiveness around 1600 Kbytes. WBest is comparatively having better intrusiveness of 170 Kbytes. Convergence is the time spent by the estimation techniques during measurement. Figure. 9 shows that Bandwidth Probe seems to have much less convergence time compared to the others with 0.48 seconds. IGI/PTR uses convergence time 1.5 seconds. Pathchirp has the longest convergence time of 18 seconds and Pathload having around 15 sec . WBest is also comparatively better in the sense of convergence having convergence time 1.2 seconds.

Conclusion

In this paper, we have proposed a new bandwidth estimation technique for the WMNs and multi-hop wireless network. To avoid estimation delay and the effect of random errors in the wireless channel, we use a statistical measurement technique in an iterative way. It is an estimation method which depends on the dispersion principle that uses probe packet trains for the measurement. Bandwidth Probe inserts certain spacing between the packet trains showing direct relation to the gap of packet pairs. We have also given the experimental details and comparison with the existing techniques. The results clearly shows that Bandwidth Probe is able to deal with the contending traffic, interference and mobility more efficiently.

Next post:

Previous post: