CSE237A – Final Project Report

CSE237A – Final Project Report

Donghwan Jeon Sudipta Kundu

Performance Comparison using different routing metrics in Ad-hoc Wireless Networks

Abstract: We implemented test beds platform for wireless ad-hoc networks using Click software router and DSDV algorithm, and measured delay and throughput for different routing metrics: minimum hop and ETX. The result shows that wireless link quality varies a lot due to transmission power and channel dynamics, and well designed routing metric can improve the network performance.

1. Introduction

Wireless communication is one of the hottest research areas. Among many challenging problems in wireless communications, routing protocol is critical for the efficiency and lifetime of the network. For the last decade, many proactive and reactive routing protocols [1, 2, 3] have been proposed, and some research groups have presented the comparison of proposed routing protocols [4, 5]. However, most research was performed on only simulator rather than real platform. While network simulations have advantages in terms of convenience, they often ignore or simplify the complexity of wireless environment such as asymmetric links or dynamic link condition. For this reason, some research groups conducted research regarding wireless network with test beds, and proposed new routing metrics such as ETX [8] and ETT [9].

In this project, we conducted experiments on test beds to examine the characteristics of wireless communication link and the effect of newly proposed routing metrics. For the test bed implementations, we ported the Click modular router [6] to the XScale based hardware platforms with Linux. We also carefully designed an ad-hoc network with different transmission power levels to model more general wireless networks with limited number of test beds. The results show important characteristics of the wireless link and the benefits of carefully designed routing metrics.

2. Click Router

Click is a modular software router developed by Parallel and Distributed Operating System group of MIT. The main advantages are its modular structure and standard configuration language implementation. Packets are processed and routed according to a given configuration modeled with flow graph. Although Click was developed for wired network routing, MIT GRID project expanded it to wireless ad-hoc networks with DSDV and DSR implementations. However, we found that only DSDV implementation works with the current version of the Click. Fig.1 shows the operation of the Click router on kernel level and user level. We chose user level implementation due to its convenience in debugging and portability.

2.1 DSDV

DSDV (Destination Sequenced Distance Vector Routing) [1] is a table based algorithm based on the classical Distributed Bellman-Ford (DBF) routing. Each node in the network maintains a routing table for all the possible destinations with the number of hops, next hop, and a sequence number. The sequence number plays an important role in differentiating old routes from fresh ones and avoiding the formation of loops in routing. Routing information is propagated by periodic broadcasting. There are two kinds of propagations: incremental dump and full dump. Incremental dump spread only changed information, while full dump carries all the information the node has. DSDV always uses routing entry with the highest sequence number when it needs to decide a route. If there are a few entries with the same sequence number, it will use the entry with the minimum hops. We used a DSDV implementation developed from GRID project that supports a few different routing metrics including hop counts and ETX.

3 Results

3.1 Execution of the Project

1. Bring-up the platform with wireless network

Rebuild the Linux kernel to support PCMCIA wireless network interface card.

2. Setup a small ad-hoc network with few platforms

Setup an ad-hoc wireless network of 5 Xscale platforms so that they can communicate among each other.

3. Research the state of the art in routing frameworks for Linux

There are many ways in which we can implement and test different routing protocols under Linux. For example, we can port each algorithm directly in the kernel or use modular framework like Click Modular Router (Click). Looking into the simplicity of porting routing protocols and the current state of art we decided to use Click.

4. Research which routing protocols to use for our project

We decided to use DSDV routing protocol as it was the only open source real implementation available for Click.

5. Port DSDV routing protocol on test beds

6. Experiment

The experiment consisted of running some scenarios on the test beds using different routing metrics (like Hop count [HC] and ETX).

7. Analyze

We analyzed the above experiments for performance and delay and reported the results.

3.2 Experimental Setup

For the project we were able to setup a real (though small) wireless ad-hoc network using the PXA27X Xscale development platforms provided by Intel. We used 5 platforms and 5 Cisco Aironet 350 wireless PCMCIA cards. The experimental setup and the corresponding graph are shown in figure 2. We ported click modular router with DSDV routing protocol in each of this platforms. The experiments consists of performance analysis of different routing metric (HC and ETX) in the DSDV routing protocol.

3.3 Throughput Analysis

Source -> Sink	Hop Count		ETX
	Time to send 3906 KB (sec)	Throughput (KB/sec)	Time to send 3906 KB (sec)	Throughput (KB/sec)
1 -> 2	39.69	98.4127	39.76	98.23944
1 -> 3	48.63	80.32079	49.19	79.40638
1 -> 4	56.52	69.10828	54.20	72.06642
1 -> 5	54.39	71.81467	44.87	87.05148
2 -> 1	40.22	97.11586	39.83	98.06678
2 -> 3	48.81	80.02459	49.45	78.98888
2 -> 4	58.53	66.73501	47.35	82.49208
2 -> 5	52.12	74.94244	39.46	98.98632
3 -> 1	39.36	99.2378	39.13	99.82111
3 -> 2	43.13	90.56341	47.12	82.89474
3 -> 4	84.17	46.40608	52.67	74.15986
3 -> 5	52.78	74.00531	42.56	91.77632
Table 1: Throughput Results

To measure throughput, we use the Linux ‘wget’ and ‘time’ utility. HTTP servers were started in the nodes 1, 2 and 3 and then we measured the time needed to get a fixed amount of bytes over the ad-hoc wireless network. The results are summarized in table 1 and figure 3. In our experiments we had a setup of at most 2 hops, so in most cases the throughput of HC and ETX are similar. One result that deviated from what we assumed was that of the weakest link (3 -> 4). Theoretically, we believed that the difference in throughput between HC and ETX for 3 -> 4 will be significant compared to other links. But this was not the case, upon analysis we realized that even though node 3 cannot reach node 4 in 1 hop, while sending a stream of data, the interference in the link 2->3 also increases (since wireless communication is inherently broadcast and usually interference range is much more than transmission range (more than twice)). We assume that if we increase the number of hops between two nodes the advantages of ETX over HC will be significant.

3.4 Delay Analysis

For delay analysis we ‘ping’ different nodes (one at a time) and measure the round trip average delay between the nodes. The results are summarized in table 2 and figure 4. From the figures we can also deduce the link quality of our experimental wireless ad-hoc network. In particular if we see the figure 4d (from node 4), we can observe that there is significantly more delay between the node 1, 2 and 3 than 5.

3.5 Asymmetric Link Analysis

We also studied the asymmetric behavior of wireless link. For example as in figure 5 we can see that the delay from node 3 to 1 is about 20% more than that of from 1 to 3. This is primarily because the transmission power of node 3 is much less than that of 1.

From

ETX

3.4

3.8

5.1

3.5

3.9

5.9

3.4

3.8

8.1

3.6

4.3

9.0

11.5

55.0

122.5

8.3

24.3

86.4

5.6

7.3

12.3

5.6

5.8

41.9

3.5

3.9

6.3

3.6

4.4

11.2

3.5

4.5

7.5

3.7

4.9

11.8

23.6

66.7

132.7

4.8

20.0

81.3

3.5

6.2

28.2

3.5

5.8

35.9

3.4

4.5

8.6

3.4

3.9

6.6

23.6

66.7

132.7

3.4

4.8

14.8

9.2

58.3

177.4

7.8

23.6

91.0

5.6

17.6

63.1

5.6

14.0

94.6

7.1

53.6

152.1

7.9

29.0

62.1

5.8

49.6

168.6

4.6

15.0

45.2

8.5

52.1

89.5

7.9

19.6

74.5

3.4

4.1

10.8

3.4

4.1

11.0

5.9

7.7

20.6

5.7

7.8

18.9

3.6

4.7

13.0

3.6

7.6

58.5

5.7

8.9

27.8

5.7

11.5

86.2

3.3

5.1

39.2

3.5

4.1

7.7

All results are in millisecond. In each cell the first row is for minimum delay of the packets in that experiment. The second row is the average delay of the packets. The third row is the maximum delay in the set of packets in that experiment.

Table 2: Delay Analysis

Text Box:

4. Conclusion:

Figure 5: Asymmetric Link Analysis

We setup test beds for ad hoc wireless networks with Click modular router. From the various experiments, we conclude that the quality of wireless network link varies according to transmission power level of each wireless node and dynamic channel status. Moreover, we find out that carefully chosen routing metrics can improve the quality of the network in terms of delay and throughput although in our limited experimental setup interference hinders from utilizing the improved throughput.

5. References:

[1] Charles E. Perkins and Pravin Bhagwat. Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers. In Proceedings of the SIGCOMM ’94 Conference on Communications Architectures, Protocols and Applications, pages 234–244.

[2] Josh Broch, David B. Johnson, and David A. Maltz. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet-Draft, draft-ietf-manet-dsr-00.txt, March 1998. Work in progress.

[3] Charles Perkins. AdHoc On Demand Distance Vector (AODV) routing. Internet-Draft, draft-ietf-manet-aodv-00.txt, November 1997. Work in progress.

[4] Josh Broth, David A. Maltz, David B. Johnson, Yih-Chun Hu and Jorjeta Jetcheva, “A performance Comparison of Multi-hop Wireless Ad Hoc Network Routing Protocols”. Mobicom’98, Dallas Texas, 25-30 October 1998.

[5] Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, and Mikael Degermark. Scenario-based performance analysis of routing protocols for mobile ad-hoc networks. In Proc. ACM/IEEE MobiCom, pages 195–206, August 1999.

[6] Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. The click modular router. ACM Transactions on Computer Systems, 18(3):263–297, August 2000.

[7] M. Neufeld, A. Jain, and D. Grunwald, “ Nsclick:: bridging network simulation and deployment,” in Proc. of ACM Intl Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2002.

[8] D. De Couto, D. Aguayo, J. Bicket, and R. Morris. High-throughput path metric for multi-hop wireless routing. In MOBICOM, 2003.

[9] R. Draves, J. Padhye, and B. Zill. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. In MobiCom, Phildelphia, PA, Sep 2004.