CSE237A – Final Project Mid Report

Donghwan Jeon            Sudipta Kundu

 


Implementation and Comparison of Routing Protocols for Ad-hoc Networks

 

Goal:

1.                  Be familiar with wireless network experiment environments

2.                  Find the advantages and disadvantages of proactive routing(DSDV) and reactive routing(DSR)

3.                  Analyze the reasons for the differences between test-bed experiments and simulation

4.                  See the benefits of new routing metrics and calculate their overhead

 

Background and Motivation:

 

Recently, wireless sensor networks (WSN) have become one of the hottest research areas. Among many challenging problems WSN have raised, 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 comparisons have been done 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. In this project, we will conduct experiments on both test beds and simulator to compare widely known DSDV [1] and DSR [2] routing protocols. For fair comparisons, we will use Click modular router [6] for test beds and Nsclick [7] for simulation. Both of them share the same modular router implementations, thus reduce the gap between test beds and simulation. Moreover, we plan to incorporate recently proposed routing metrics such as ETX [8] and ETT [9] instead of hop counts to see how much they can improve the routing and how much they cost.

 

Project Description:

 

In this project we are going to setup a small wireless network (ad-hoc) using the Xscale platforms and compare few well known ad-hoc routing algorithms for performance (using metrics like throughput, end to end delay and routing overhead). If time permits we also intend to change each routing algorithm and test it with different routing metrics (like Hop count, ETX and ETT). Finally we will analyze the results based on the above metrics.

 

Project Execution:

 

Plan of Actions:

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 a few platforms

Setup an ad-hoc wireless network of at least 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. We need to research which option will be best for us (keeping in mind that we have to port that framework to Xcale platform)

4.      Research which routing protocols and criteria to use for our project

We need to research and decide why and which routing protocols we will use. The factors that we will consider are energy, bandwidth and performance. Few routing protocols that we may use are DSDV, CGSR, AODV, DSR, LMR, etc.

5.      Implement or port various routing protocols on test beds and simulator

We will implement or port the various routing algorithms and the framework we choose for arm-linux test beds and simulator (nsclick).

6.      Experiment

The experiment will consist of running some scenarios on the test beds and simulator for each routing protocol.

7.      Analyze

We will analyze the above experiments depending on a few criteria and report the results.

8.      Expanded Experiment

Conduct the above experiments again with different routing metrics (hop counts, ETX, ETT), and analyze the results.

 

Status or Results so far:

  1. We have been able to successfully run Linux kernel (2.4.21) with PCMCIA wireless network interface card.
  2. Due to unavailability of wireless network interface cards we are unable to setup the network, though we were able to bring up two platforms and those are able to communicate between each other in ad-hoc mode.
  3. After some research we decided to choose Click modular router as our experiment framework, because it can be configured to run different routing algorithm and also in different modes (user and kernel). We then cross-compiled click and ported it to the platform.
  4. Then we choose the DSDV routing algorithm and cross-compiled it for arm-linux and ported it to the target platform. We were able to communicate between two Xscale platforms using the DSDV algorithm in the Click modular router framework.
  5. We also partially decided the performance metrics we will be considering during the experiments:
    • Throughput
    • End to end delay
    • Routing overhead
  6. We short listed the routing algorithms that we want to compare namely DSDV and DSR.

 

Timeline:

5.      1st week: 1, 2, 3, 4 ………….. Deadline met

6.      2nd week: 1, 2, 3, 4 …………. Deadline met

7.      3rd week: 5, mid report ……... Deadline met

8.      4th week: 5, 6, 7

9.      5th week: 7, Final report

 

Expected Results and Summary:

 

In short, our progress is according to the timeline submitted in the project proposal. We have already done a lot of research on the available routing algorithms in ad-hoc network and are also able to port Click router and DSDV algorithm in the target platform. In the remaining time line, we will focus on:

-         Setting up nsclick simulation environment.

-         Do experiments on both test beds and simulator, and compare the results.

-         Find and analyze characteristics of routing protocols from the experiments.

-         See the effects of changing routing metrics on performance.

 

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.