Routing On Ad Hoc Networks

School of Engineering BSc Honours Project Report

Project Title: Routing on Ad Hoc Networks Name:

Mathieu Gallissot

Course:

Computer Network Management and Design

Supervisor:

Maurice Mitchell

Date:

May 2007

ROUTING ON AD HOC NETWORKS

Mathieu Gallissot (0509781) May 2007

This report is submitted in partial fulfilment on the requirements for the degree of BSc Honours in Computer Network Management and Design at The Robert Gordon University, Aberdeen.

BSc Honours Project Report

ii

DECLARATION I confirm that the material presented in this report is my own work. Where this is not the case, the source of material has been acknowledged. All third-party trademarks are hereby acknowledged.

Signed ............................................................................................................. Mathieu Gallissot School of Engineering The Robert Gordon University, Aberdeen May 2007

BSc Honours Project Report

iii

ABSTRACT Since the early 90‟s, there have been two revolutions in the world of communications: Internet and wireless. The first one tends to merge different kinds of networks into one consisting of more than a billion users across the world . Wireless also had a huge growth over the passing years, first with cellular phones (more than one billon users) and then with wifi. Nowadays, merging Internet and wireless technologies seems ineluctable, for reaching a permanent network where big quantities of information are going to travel whatever kind of terminal is used. But, using Internet‟s associated protocol on mobile networks is not as easy as people think. Internet was designed in the early 70‟s, for wired network. With the success of this technology, the usage starts to need more and more requirements, for video and voice for example. This report will cover the adaptation of the mechanism of routing into wireless networks, in particular, Wifi.

BSc Honours Project Report

iv

ACKNOWLEDGEMENTS

I would like to thank Maurice Mitchell, my project supervisor, who allowed me to research this really interesting subject. I am also grateful to people who help me through in one way or another, as: 

Mark Greiss, Yuan Yuan and Chih-Heng Ke for their tutorials and help on NS-2.



All people on the NS-2 mailing list, especially Allaa Hilal and Manpreet Grewal

Thanks also go to all open source software developers.

BSc Honours Project Report

v

TABLE OF CONTENTS ROUTING ON AD HOC NETWORKS................................................................................................ II DECLARATION ........................................................................................................................................ III ABSTRACT ................................................................................................................................................. IV ACKNOWLEDGEMENTS ........................................................................................................................ V TABLE OF CONTENTS .......................................................................................................................... VI LIST OF FIGURES ............................................................................................................................... VIII LIST OF TABLES ..................................................................................................................................... IX LIST OF SYMBOLS AND/OR ABBREVIATIONS ....................................................................... X 1

INTRODUCTION ............................................................................................................................... 1 1.1 THE WIRELESS WORLD .................................................................................................................. 1 1.1.1 Infrastructure ................................................................................. 1 1.1.2 Ad Hoc ........................................................................................... 1 1.2 USAGE OF AD HOC NETWORKS ..................................................................................................... 2 1.2.1 Extending Coverage ........................................................................ 2 1.2.2 Communicating where no infrastructure exists .................................... 3 1.2.3 Community Networks ...................................................................... 3 1.3 PROBLEMS IN WIRELESS COMMUNICATIONS ................................................................................. 5 1.3.1 Security ......................................................................................... 5 1.3.2 Bandwidth ...................................................................................... 5 1.3.3 Energy ........................................................................................... 6 1.3.4 Asymmetric connections .................................................................. 6 1.4 ROUTING .......................................................................................................................................... 7 1.4.1 Definition ....................................................................................... 7 1.4.2 Routing in a wired environment ........................................................ 7 1.4.3 Routing problems in Ad Hoc networks ................................................ 8 1.5 AD HOC ROUTING PROTOCOLS ....................................................................................................... 9 1.5.1 Proactive ........................................................................................ 9 1.5.2 Reactive ......................................................................................... 9 1.5.3 Hybrids .........................................................................................10

2

PRO-ACTIVE PROTOCOLS ........................................................................................................ 11 2.1 DESTINATION SEQUENCED DISTANCE VECTOR (DSDV).......................................................... 11 2.1.1 Algorithm ......................................................................................11 2.1.2 Illustration ....................................................................................12 5.1.1 Performance ..................................................................................13 5.2 OPTIMIZED LINKED STATE ROUTING (OLSR) ........................................................................... 13 5.2.1 Algorithm ......................................................................................14 5.2.2 MultiPoint Relay (MPR) ....................................................................14 5.2.3 Performance ..................................................................................16 5.2.4 Implementation .............................................................................16 10.1 OTHER PROACTIVE PROTOCOLS ............................................................................................... 18 10.1.1 Fisheye State Routing (FSR) ............................................................18 10.1.2 Hierarchical State Routing (HSR) ......................................................19 10.1.3 Distance Routing Effect Algorithm for Mobility (DREAM) ......................19

11

REACTIVE PROTOCOLS ......................................................................................................... 20

BSc Honours Project Report

vi

11.1 AD HOC ON-DEMAND DISTANCE VECTOR (AODV) .............................................................. 20 11.1.1 Algorithm ......................................................................................20 11.1.2 Illustration ....................................................................................21 11.1.3 Implementation .............................................................................22 11.2 DYNAMIC SOURCE ROUTING (DSR)....................................................................................... 22 11.2.1 Algorithm ......................................................................................22 11.2.2 Implementation .............................................................................24 11.3 OTHER REACTIVE PROTOCOLS ................................................................................................. 24 11.3.1 Temporally-Ordered Routing Algorithm (TORA) ..................................24 11.3.2 Relative Distance Micro-discovery Ad Hoc Routing (RDMAR) ................25 12

HYBRIDS PROTOCOLS ........................................................................................................... 26

12.1 12.2 12.3 14.1 17.1 17.2 18

DEFINITION ............................................................................................................................... 26 ZONE ROUTING, ZONE RADIUS AND BORDERCASTING NOTIONS ........................................ 27 INTRAZONE ROUTING PROTOCOL (IARP) ............................................................................. 28 INTERZONE ROUTING PROTOCOL (IERP) .............................................................................. 29 BORDER RESOLUTION PROTOCOL (BRP) ............................................................................... 29 NEIGHBOUR DETECTION PROTOCOL (NDP) .......................................................................... 29

SIMULATION ............................................................................................................................... 31

18.1 SIMULATION SYSTEM ................................................................................................................ 31 18.1.1 The Network Simulator 2 (NS2) .......................................................31 18.1.2 Processing results ..........................................................................33 18.1.3 Observations .................................................................................34 18.2 SIMULATION SCENARIO ............................................................................................................ 36 22.1 SIMULATION RESULTS ............................................................................................................... 37 22.1.1 Application traffic vs. routing traffic ..................................................37 22.1.2 Impact of the number of nodes ........................................................39 22.1.3 Impact of Mobility ..........................................................................42 22.1.3.1 22.1.3.2 22.1.3.3 22.1.3.4

DSDV ......................................................................................................................................... 42 OLSR .......................................................................................................................................... 43 AODV ......................................................................................................................................... 43 DSR ............................................................................................................................................ 44

22.1.4 Impact of topology size ...................................................................45 22.2 THE CASE OF ZRP..................................................................................................................... 45 23

DISCUSSION ............................................................................................................................... 46

24

CONCLUSION .............................................................................................................................. 47

REFERENCES ............................................................................................................................................. 48 BIBLIOGRAPHY....................................................................................................................................... 49 APPENDIX A ............................................................................................................................................. 50 THE SIMULATION SYSTEM ............................................................................................................................ 50 APPENDIX B.............................................................................................................................................. 60 INSTALLATION OF NS-2 UNDER UBUNTU 6.06.............................................................................................. 60

BSc Honours Project Report

vii

LIST OF FIGURES Figure 1-1: Infrastructure mode vs. Ad Hoc mode ...................................... 2 Figure 1-2: Example of range extension with Ad Hoc .................................. 3 Figure 1-3: FON Hotspots in Aberdeen City Centre ..................................... 4 Figure 1-4: Former Brazil president with an OLPC laptop ............................. 5 Figure 1-8: Ad Hoc routing protocols design .............................................. 9 Figure 2-1: Example of DSDV (1) ............................................................ 12 Figure 2-2: Example of DSDV (2) ............................................................ 12 Figure 2-3: Relay Selection mechanism .................................................... 15 Figure 2-4: Example of traffic reduction using selected relays ..................... 16 Figure 2-5: Screenshot of the OLSR.ORG windows application .................... 17 Figure 2-6: The Fisheye mechanism ........................................................ 18 Figure 3-1: Example of AODV route discovery ........................................... 21 Figure 3-2: DSR route discovery process .................................................. 23 Figure 3-3: DSR route maintenance process ............................................. 23 Figure 4-1: Structure of ZRP protocol ...................................................... 27 Figure 4-2: ZRP zone definition ............................................................... 28 Figure 5-1: Simulation system overview ................................................... 31 Figure 5-2: Simulation software design .................................................... 32 Figure 5-3: Result processing design ....................................................... 34 Figure 5-4: Results of simulation processing ............................................. 35 Figure 5-5: Simulation parameters in a tree ............................................. 37 Figure 5-6: Application traffic vs. routing traffic for DSDV, OLSR, AODV and DSR ..................................................................................................... 38 Figure 5-7: Impact of the number of nodes on the routing packets exchanged ........................................................................................................... 40 Figure 5-8: Impact of the number of nodes on the routing data exchanged .. 41 Figure 5-9: Impact of mobility with DSDV ................................................ 42 Figure 5-10: Impact of mobility with OLSR ............................................... 43 Figure 5-11: Impact of mobility with AODV ............................................... 44 Figure 5-12: Impact of mobility with DSR ................................................. 45

BSc Honours Project Report

viii

LIST OF TABLES Table Table Table Table Table Table Table Table

1-1: 2-1: 3-1: 3-2: 5-1: 5-2: 5-3: 5-4:

List of famous routing protocols used on wired networks ............. 8 List of available implementation for OLSR ................................. 18 List of available AODV implementation ..................................... 22 List of available implementations for DSR ................................. 24 MySQL tables summary .......................................................... 33 MySQL table "simulation" structure .......................................... 33 MySQL table “traces” structure ................................................ 33 Simulation traffic overview ...................................................... 39

BSc Honours Project Report

ix

LIST OF SYMBOLS AND/OR ABBREVIATIONS GSM: Global System for Mobile Communications IETF: Internet Engineering Task Force LLC: Link Layer Control MANET: Mobile Ad hoc NETworks MIT: Massachusetts Institute of Technology MPT: MultiPoint Relay OLPC: One Laptop Per Child OSI: Open System Interconnection RFC: Request for Comments

BSc Honours Project Report

x

1 INTRODUCTION Routing on an Ad Hoc network is a small piece in a huge world, the wireless networking world. We will see in this chapter every dependency linked to this world, from the routing principle to the “Ad Hoc” definition.

1.1 The Wireless World The wireless mode can work in two different modes, the first one is the most common, called the architecture mode. This mode is just using wireless for the end user loop. The second kind of operating mode for a wireless network is the Ad Hoc mode. This one relies only on wireless communications.

1.1.1 Infrastructure The most known example of infrastructure wireless network is GSM and, more recently, wifi. As said above, this mode is just using the wireless for the end user loop, which means between the user terminal and a “radio terminal”. This term “radio terminal” describes a Base station (for GSM), or an access point (for wifi). Its role is basically to serve as a gateway between a wired network (called distribution system) and its wireless zone. Technically speaking, each “radio terminal” spreads a signal around, creating a coverage zone. Each client is able to communicate within this zone, but then, has to renegotiate with another “radio terminal” if available. The “radio terminal” has the key role of referee in this kind of network, as each station has to communicate only with its radio terminal. Mobility is then limited to a coverage zone, and so, has a limited impact on this implementation. This infrastructure design can be seen as a first way to implement wireless technologies into the settled wired world. In fact, from the technical point of view, only the first two layers are modified in the OSI model. These changes concern only the physical layer (going from a wire to a wireless media) and the Logical Link Control (LLC) layer (how to access the media). Other layers of the OSI model are working as in a wired network.

1.1.2 Ad Hoc Ad Hoc is an expression from the Latin which means “for this purpose”. Ad Hoc networks introduce a new way of communication. Since communications

BSc Honours Project Report

1

networks were created, there were two kinds of device, the one which uses the network and the one which acts for the network. This rule is true in telephony (phones vs. switches), in Internet (computers, servers vs. routers, switches, hub…) and also in the infrastructure mode described above (user terminal vs. radio terminal). In Ad Hoc networks, each station is using the network and creating the network. For example, in a wifi network, a laptop is able to send and receive data for itself, but it can also forward others data (acting as a router). This design has the main advantage to be independent of any distribution system, or any hierarchy such as an access point. If A wants to communicate with B, then, they just have to connect to each other and exchange data. But, this design also extends coverage and mobility possibilities. If A wants to communicate with C, but C is out of range, B, a station in both A and C radio zones, can forward packets. Also, if A is moving closer to C, A and C can stop using B as a relay.

Figure 1-1: Infrastructure mode vs. Ad Hoc mode

1.2 Usage of Ad Hoc Networks 1.2.1 Extending Coverage Ad Hoc networks can be used for extending the coverage area of an access point. By this way, a single access point where a few users are connected can provide a network access to out-of-range machines. Figure 1-2 describes this implementation of Ad Hoc networks:

BSc Honours Project Report

2

Figure 1-2: Example of range extension with Ad Hoc

This example shows how the Ad Hoc model can extend an infrastructure wireless network. Without Ad Hoc, only station A could access the internet using the access point. But, if each station is able to forward the packets to the Access Point, then, B can access the internet, as well as C and the final user.

1.2.2 Communicating where no infrastructure exists Ad Hoc networks can also be used in an environment where no infrastructure exists. A good example is when an army is deploying into a destroyed place or an empty space. In this case, each station can be configured for forwarding communications to the appropriate destination. This example also shows the mobility benefit of the Ad Hoc model. This case also applies in the ocean, in the air or even in space (for satellites).

1.2.3 Community Networks A community network is a network where everybody shares its connections with other people. The most famous example of community network is FON. FON is a Spanish company, sponsored by Skype and Google, who want to

BSc Honours Project Report

3

establish a world wide community network. FON provide to every registered user with an internet connection and a wifi access point at low cost. The user must connect this access point to his Internet connection and share his connection with other FON users.

Figure 1-3: FON Hotspots in Aberdeen City Centre (Green dots if enable, orange dot if down)

There are two ways to use Ad Hoc for community networks. The most commonly used, is to extend coverage as explained above. Access points are deployed into a city (most common scale) depending of the density of users, and then, Ad Hoc is used to extend the coverage of these access points. In this scenario, the density of access points is important as too many users connected to the same access point can overload its connection. Also, there must be enough users to relay the network where no coverage exists. Another way to use the Ad Hoc model is to create what‟s called a mesh network. This time, each access point is part of the Ad Hoc network, and can be connected or not to a distribution system. The notion of hierarchy present in the architecture doesn‟t exist anymore. A good illustration of this wireless mesh network is the one made by the One Laptop Per Child project. This project, initiated by an MIT association, has a goal to design a cheap computer (sold at 100$) for third world countries, in order to promote education.

BSc Honours Project Report

4

Figure 1-4: Former Brazil president with an OLPC laptop

These laptops are wifi enabled, and configured for an established Ad Hoc network. That means that every child with one of these laptops relays data for others, even if the laptop is switched off (with a very low consumption wireless chipset). Some schools can have the role of access point, but this is not an obligation. In this case, a child will be able to connect to others, and Internet, share information and knowledge with others.

1.3 Problems in wireless communications 1.3.1 Security Because the signal is diffused in the air, everybody is able to receive it. This is a major problem for security. If people have the correct equipment for a specific signal, they are able to use it (i.e. radio, TV…). Using a wireless communication is equivalent to shouting information from the top of a roof. One of the most effective ways for securing a wireless signal is to encrypt it (encrypting data or even the signal).

1.3.2 Bandwidth Wireless networks suffer from low and unreliable bandwidth. This problem is due to the radio media. Many parameters can affect a radio liaison: interferences, obstacles, mobility…etc

BSc Honours Project Report

5

As the number of frequencies is limited, and as the bandwidth is proportional to the frequency, the radio frequency space is cut in channels. For Wifi, there are two main frequency spaces, 2.4 GHz (802.11b/g) and 5 GHz (802.11a). 2.4 GHz is also the operating frequency of microwaves, so, using both of these in a close space affects the link quality of the wifi connection, and sometimes, the link is lost. Obstacles also affect radio waves. It first reduces the power of the signal, and then, it can also reflect the signal, and destroy it in the same way. In a mobile environment, radio waves are subject to the Doppler Effect, causing a frequency distortion. In addition, bandwidth on a radio link is shared between every device using it. Access methods must be designed for avoiding collisions and improve communication, but, these access methods also reduce the availability of the bandwidth. It has been proved that on a wifi link, in practice, only 50% of the theoretical bandwidth is available, and tests showed that latency is more important than on wired networks.

1.3.3 Energy A known problem of radio links is the amount of energy they require, not only for the amount of calculation needed for modulation, but mainly for the power needed for the antenna. When a device wants to communicate with a wire, it concentrates all the energy on this wire. For wireless communication, antennas are usually omnidirectional, as they need much more energy. Also, the absorption in the air is very important compared to wires.

1.3.4 Asymmetric connections An

asymmetric

connection

is

a

common

problem

in

wireless

telecommunications. There are many causes for that. The radio propagation model is the main cause. In theory, connections are symmetric, signal power reduces proportionally to the distance between the emitter and the receptor. In practice, the antenna design and the environment can cause the device to be able to receive from another device, but will not be able to send to this device.

BSc Honours Project Report

6

This problem can also appear depending on the chipset design. Some chipsets can restore a low-power signal but will not be able to provide enough power to the antenna for responding to this signal.

1.4 Routing 1.4.1 Definition Routing is the mechanism used in communications to find a path between two entities. This is represented in the OSI model as the third layer (called Network). The role of routing a network is similar to the role of a road map for a post office, in both cases; we need to locate the destination, and more importantly, the best way to reach it. It especially has an important role, as the Internet was first designed for military communications. Americans wanted a communication infrastructure able to handle the fact that some part of a network core may be down. In this case, a mechanism should redirect data to its destination. As an OSI layer, this mechanism receives data “ready to send” from the upper layer, then calculates the best path for the destination, and forwards it to layer 2. In the real world, this layer has a very limited role for computers, but, it is the main role for routers, in a network core. For other kinds of network, there are similar mechanisms. For mobile phones, a database centralises the base station where each mobile is connected. This database is used for every call to a mobile phone, providing the end destination to the network core.

1.4.2 Routing in a wired environment Routing has been designed firstly for a routing environment, where there is a network core and network clients. In this case, routers use routing protocol to logically

locate

themselves, and draw

a network topology.

With this

mechanism, routers are able to define a routing table. This routing table contains the information for helping the router to make a decision on where to forward received packets. Routing protocols helps to build routing tables, as these protocols exchange data between routers, containing information about the network. Each protocol acts a different way. The forwarding decision can be taken only depending on

BSc Honours Project Report

7

the number of hops, the “shortest path”, or including more data for judging the best route, such as latency, congestion… One of the most basic and known

RIP (Routing Information

routing protocols. Takes its decisions

Protocol)

on the status of links (up or down) and the shortest path.

IGRP (Interior Gateway Routing Protocol) EIGRP (Enhanced Interior Gateway Routing Protocol)

An evolution of RIP using bandwidth, load, delay, MTU, and reliability for building routing tables. An

Evolution

of

IGRP,

introducing

router status in addition of link status.

OSPF (Open Shortest

A

Path First)

protocol.

BGP (Border Gateway

Standard protocol for the Internet

Protocol)

core.

link

stated

and

shortest

path

Table 1-1: List of famous routing protocols used on wired networks

Routing protocols are often qualified depending on the size of information they have to exchange in order to build a correct table. A routing protocol should not use by itself the entire bandwidth available on a link. They are also qualified on how often they have to exchange data, and how complex they are (just link state or using more information on the link).

1.4.3 Routing problems in Ad Hoc networks In infrastructure mode, the routing part is handled by the access point and the distribution system; every wireless device just has to forward all its traffic to this access point. But, in Ah Hoc networks, there is no “referee” for connections, and, every device acts as a router. This scenario is totally new. Adding to this, devices are not fixed, they can be mobile, contrary to the Internet where every router has “fixed” neighbours (excepts if a link goes down). For solving this problem, the IETF (Internet Engineering Task Force), powerful standardisation authority in the communication world, created the MANET work group. This group has a mission to create and discuss routing protocols

BSc Honours Project Report

8

for Ad Hoc networks. This task is very important, due to the complexity of routing on Ad Hoc networks. The work started in January 1999, with the publication of the informational RFC 2501. This document presents the 4 main constraints for routing on Ad Hoc networks, such as dynamics topology, bandwidth constraints, energy constraints and low physical security. The group has then to comply with these constraints in order to build an efficient algorithm of route calculation.

Figure 1-5: Ad Hoc routing protocols design

1.5 Ad Hoc routing protocols There were different approaches, and then, different solutions. The three mains approaches are proactive protocols, reactive protocols and hybrids.

1.5.1 Proactive Proactive protocols are close to wired routing protocols in the manner that the routing table is built before the data has to be sent. That means these protocols are constantly making requests to their neighbours (if any) in order to draw a network topology, and then, build the routing table. The disadvantage of this principle is to not be reactive to topology changes, as the tables are pre-established. At the time the data has to be sent, it is not certain that the gateway designed by the routing table will still be there to forward the data.

1.5.2 Reactive Reactive protocols are more specific to Ad Hoc networks. Contrary to the proactive algorithm, they ask their neighbours

for a route when they have

data to send. If the neighbours do not have any known route, they broadcast BSc Honours Project Report

9

the request, and so on. Once the final destination has been reached by these broadcasts, an answer is built and forwarded back to the source. This source can then transmit the data on the newly discovered route. Each device used for forwarding the routing packets has learned the route at the same time. The disadvantage of this design is the amount of routing traffic exchanged between devices. In the case of a large topology, the traffic will be spread on each link until the end node is found. It also can result in a high latency.

1.5.3 Hybrids A Hybrid protocol will use the two above algorithms. The main goal is to reduce broadcasts and latency, but improve the dynamism impact. The whole network will be separated into logical zones, and each zone will have a gateway. Inside each zone, a reactive protocol will be used. For inter-zone routing, a proactive protocol will be used.

BSc Honours Project Report

10

2 PRO-ACTIVE PROTOCOLS As proactive protocols are constantly updating their routing tables in order to be ready when data has to be sent, they are called table-driven protocols. This type of protocol is close to wired networks where the same mechanisms are used in order to take routing decisions. These mechanisms are used for finding the shortest path across the network topology; it can be the “Link state” method or the “Distance Vector” method. With the “Link State” method, each node has its own view of the network, including the states of its own channels. When an event on the channel occurs, the node floods the network topology with its own new view of the topology. Other nodes which receive this information use algorithms to reflect changes on the network table. With the “Distance Vector” routing approach, each node transmits to its close nodes its vision of the distance which separate it from all the hosts of the network. Based on the information received by the neighbourhood, each node performs a calculation in order to define routing tables with the shortest path to all destinations available in the network.

2.1 Destination Sequenced Distance Vector (DSDV) DSDV was one of the first proactive routing protocols available for Ad Hoc networks. It was developed by C. Perkins in 1994, 5 years before the informational RFC of the MANET group. It has not been standardised by any regulation authorities but is still a reference.

2.1.1 Algorithm DSDV is based on the Bellman-Ford algorithm. First designed for graph search applications, this algorithm is also used for routing since it is the one used by RIP. With DSDV, each routing table will contain all available destinations, with the associated next hop, the associated metric (numbers of hops), and a sequence number originated by the destination node. Tables are updated in the topology per exchange between nodes. Each node will broadcast to its neighbours entries in its table. This exchange of entries can be made by dumping the whole routing table, or by performing an

BSc Honours Project Report

11

incremental update, that means exchanging just recently updated routes. Nodes who receive this data can then update their tables if they received a better route, or a new one. Updates are performed on a regular basis, and are instantly scheduled if a new event is detected in the topology. If there are frequent changes in topology, full table exchange will be preferred whereas in a stable topology, incremental updates will cause less traffic. The route selection is performed on the metric and sequence number criteria. The sequence number is a time indication sent by the destination node. It allows the table update process, as if two identical routes are known, the one with the best sequence number is kept and used, while the other is destroyed (considered as a stale entry).

2.1.2 Illustration Let us consider the two following topologies (figure 2-1 and figure 2-2). At t=0, the network is organized as shows figure 2-1. We suppose at this time the network is stable, each node has a correct routing table of all destinations.

Figure 2-1: Example of DSDV (1)

Then, we suppose G is moving, and at t+1, the topology is as shown in figure 2-2.

Figure 2-2: Example of DSDV (2)

At this stage, the following events are detected, and actions are taken:

BSc Honours Project Report

12



On node C: link with G is broken, the route entry is deleted, and updates are sent to node D.



On node A and F, a new link is detected, the new entry is added to the routing table and updates are sent to neighbours.



On node G, two new links are detected (to A and F), and one is broken (to C), the routing table is updated and a full dump is sent to neighbours (as the routing table is entirely changed, a full dump equals an incremental update).

2.1.3 Performance As with every table-driven protocol, DSDV reduces the latency by having a route when the data has to be sent. But, DSDV presents a few problems, mainly in the route table update process. One of the major problems is that data is exchanged only between neighbours, and then, a change in the topology can take time to be spread in the whole topology. That introduces the notion of route fluctuation. When a node disappears, it takes time for this change to be reflected in the whole topology. So, if the topology is dynamic, the routing layer will be unstable until changes are reflected everywhere. This route fluctuation problem can be demonstrated with the example in chapter 2.1.2. Updates are sent after events, links broken and new links. At t+1, the routing protocol will transmit routing table updates according to the newly detected events. But, once these updates are processed by nodes D, B and E, nodes C and D still have no routes for G, and it will take two more updates until the entire topology will be updated on all nodes.

2.2 Optimized Linked State Routing (OLSR) OLSR is another proactive protocol. Initiated by the INRIA (Institut Nationnal de Recherche en Informatique et Automatique, national research institute in computer sciences and automatism) It has been proposed for standardisation to the IETF with the RFC 3626 in October 2003. As a proactive protocol, OLSR is table-driven. The change comparing to other proactive protocols is in the route updating process.

BSc Honours Project Report

13

2.2.1 Algorithm OLSR is using a state link routing protocol. It takes decisions based on the shortest path, using the Dijkstra algorithm for calculating this shortest path. This algorithm is the most used for state link routing. Also, a particularity of OLSR is to use a mechanism of multipoint relays (MPR). Multipoint relays for a specific node are the only ones to forward routing specific broadcasted messages, in order to reduce the amount of traffic exchanged and duplicates data. As a proactive protocol, OLSR defines two ways to maintain and update tables. First, OLSR acts for its neighbourhood; it uses “HELLO” messages in order to inform its neighbours about its current links states. These “HELLO” messages contain a timeout, a hold time, and information about link status, such as symmetric, asymmetric or MPR. In opposition to DSDV, it is not the routing table that is exchanged. OLSR will use this data base on all neighbours received packets to modify and maintain the routing table. These “HELLO” packets are broadcasted on a regular basis. OLSR also uses “TOPOLOGY CONTROL” packets. This type of packet is event scheduled. Each node which detects a change in its direct neighbourhood will send this packet containing its network address and a list of its MPR. This packet is used to inform other nodes of topology changes. This will start a new route calculation process.

2.2.2 MultiPoint Relay (MPR) The multipoint relay selection algorithm is based on a very simple rule. Each node assigns a relay to a few of its direct neighbours, for covering every node at a two-hop distance.

BSc Honours Project Report

14

Figure 2-3: Relay Selection mechanism

On figure 2-3, A has to choose relays for the network. Its direct neighbours are B, C, D and E. The relay selection algorithm will check which one of these direct neighbours can cover the two-hop distance one (F, G, H, I, J, K). In this case, B and E are the only nodes able to cover these two-hop nodes for A, so, A will select them as primary relays. In the end, the best neighbours are qualified depending on how many nodes they can cover. That brings more effectiveness for the routing protocol by avoiding duplicate traffic. One of the characteristics of this algorithm is that depending on the source node, relays of this source can be different as soon as the multipoint rule is respected. This leads to a good traffic distribution between each node. With OLSR, this relay selection avoids unnecessary traffic, as only MPR can relay routing table updates.

BSc Honours Project Report

15

Figure 2-4: Example of traffic reduction using selected relays

2.2.3 Performance OLSR increases performance comparing to DSDV, due to the multipoint relay mechanism. This mechanism reduces the amount of data exchanged by avoiding useless transmissions such as duplicates. MPR also reflects changes quicker in the topology by reducing the route fluctuation impact in a mobile environment. So, compared to DSDV, OLSR is quicker and uses less control traffic. But, on large topologies, OLSR is still vulnerable to quick network changes.

2.2.4 Implementation OLSR has been widely implemented, especially for community networks. This protocol is available for both Linux and Windows operating systems. The most famous implementation of OLSR is olsrd, published as open source software per OLSR.ORG. In addition to the protocol specification, this implementation includes a link quality extension. A few plugins are also available, such as: 

HTTPInfo, a plugin giving information about protocol statistics through a web page



Nameservice, a plugin acting as a name server for Ad Hoc networks. This plugin is useful as Ad Hoc networks can be infrastructure-less, and does not necessarily have a DNS server.

BSc Honours Project Report

16



Dynamic Internet Gateway, a plugin for announcing an internet connection share available.



Secure OLSR, a plugin that adds signatures to OLSR specific messages. Only nodes with a correct shared key can then process these messages.



Dot topology information, a plugin that generates graph data of the topology.

Figure 2-5: Screenshot of the OLSR.ORG windows application

Also, Table 2-1 shows the list of others implementations of OLSR are available, with their specification. Name

IP

Operating Systems

Licens e GPL Comme rcial

crcolsr6ds_rfc HOLSR

6 4

Linux Linux

nOLSR Nrlolsrd

4 4

Windows Windows/Unix/MacOS 10

QPL ?

OLSR for W2k and Pocket PC

4

Windows

GPL

BSc Honours Project Report

Comments RFC 3626 Compliant HITACHI implementation, RFC 3626 Compliant, IPv6 is in progress RFC 3626 compliant RFC 3626 Packet formats, no MID messages Draft version 3.0 compliant

17

olsrd

4,6 Linux, Windows

GPL

OOLSR pyOLSR

4 4

Qolyester

4,6 Linux

GPL XFree8 6-style GNU

Linux, Windows (XP,CE) Linux

RFC 3626 Compliant, Extendable through the use of plugins RFC 3626 Compliant RFC 3626 Compliant RFC 3626 Compliant, LRI Extension of OLSR QOLSR

Table 2-1: List of available implementation for OLSR

2.3 Other Proactive protocols 2.3.1 Fisheye State Routing (FSR) The FSR protocol is based on the “Fisheye” method proposed by Kleinrock and Stevens. This method was, as the Bellman-Ford algorithm, primarily designed for graph processing, in particular, the amount of data needed for drawing a graph.

Figure 2-6: The Fisheye mechanism

For routing, the fisheye approach tends to rely on the accuracy of routing tables. Which means that on nearest nodes, the routing information will be much more accurate than for far nodes. This accuracy is represented by the

BSc Honours Project Report

18

amount of information exchanged and the time interval they are exchanged over.

2.3.2 Hierarchical State Routing (HSR) HSR is a proactive routing protocol introducing a notion of hierarchy. It uses dynamic groups, hierarchic levels with an efficient management of localisation. With HSR, the topology of the network is saved on a hierarchic basis, and, the network is split into subsets, or groups. In each group, a node must be elected for representing other nodes. This representative node will be part of the higher level group, and then, must elect again another representative… The routing decision is taken using nodes‟ addresses. The address scheme must be also hierarchic, following the same tree as the topology.

2.3.3 Distance Routing Effect Algorithm for Mobility (DREAM) DREAM is based on the localisation of mobile nodes, and introduces a notion of geography. Each node knows approximately its localisation in the topology. When data has to be sent, and the sender knows approximately the localisation of the destination, it broadcasts the packet in the destination direction. Otherwise, the packet is simply broadcast on the whole topology. In order to localise properly each node in the network, “TOPOLOGY CONTROL” packets with localisation information are broadcasted regularly.

BSc Honours Project Report

19

3 Reactive protocols As covered in chapter 2, proactive protocols define a best path through the topology for every available node. This route is saved even if not used. Permanently saving routes cause a high traffic control on the topology, in particular in networks with a high number of nodes. Reactive protocols are the most advanced design proposed for routing on Ad Hoc networks. They define and maintain routes depending on needs. There are different approaches for that, but most are using a backward learning mechanism or a source routing mechanism.

3.1 Ad hoc On-demand Distance Vector (AODV) AODV was proposed to standardisation by the RFC 3561 in July 2003. It was designed by the same people who designed DSDV. AODV is a distance vector routing protocol, which means routing decisions will be taken depending on the number of hops to destination. A particularity of this network is to support both multicast and unicast routing.

3.1.1 Algorithm The AODV algorithm is inspired from the Bellman-Ford algorithm like DSDV. The principal change is to be On Demand. The node will be silent while it does not have data to send. Then, if the upper layer is requesting a route for a packet, a “ROUTE REQUEST” packet will be sent to the direct neighbourhood. If a neighbour has a route corresponding to the request, a packet “ROUTE REPLY” will be returned. This packet is like a “use me” answer. Otherwise, each

neighbour

will

forward

the

“ROUTE

REQUEST”

to

their

own

neighbourhood, except for the originator and increment the hop value in the packet data. They also use this packet for building a reverse route entry (to the originator). This process occurs until a route has been found. Another part of this algorithm is the route maintenance. While a neighbour is no longer available, if it was a hop for a route, this route is not valid anymore. AODV uses “HELLO” packets on a regular basis to check if they are active neighbours. Active neighbours are the ones used during a previous route discovery process. If there is no response to the “HELLO” packet sent to a

BSc Honours Project Report

20

node, then, the originator deletes all associated routes in its routing table. “HELLO” packets are similar to ping requests. While

transmitting,

if

a

link

is

broken

(a

station

did

not

receive

acknowledgment from the layer 2), a “ROUTE ERROR” packet is unicast to all previous forwarders and to the sender of the packet.

3.1.2 Illustration

Figure 3-1: Example of AODV route discovery

In the example illustrated by figure 3-1, A needs to send a packet to I. A “ROUTE REQUEST” packet will be generated and sent to B and D (a). B and D add A in their routing table, as a reverse route, and forward the “ROUTE REQUEST” packet to their neighbours (b). B and D ignored the packet they exchanged each others (as duplicates). The forwarding process continues while no route is known (c). Once I receives the “ROUTE REQUEST” from G (d), it generates the “ROUTE REPLY” packet and sends it to the node it received from. Duplicate packets continue to be ignored while the “ROUTE REPLY” packet goes on the shortest way to A, using previously established reverse routes (e and f).

BSc Honours Project Report

21

The reverse routes created by the other nodes that have not been used for the “ROUTE REPLY” are deleted after a delay. G and D will add the route to I once they receive the “ROUTE REPLY” packet.

3.1.3 Implementation Table 3-1 shows the list of available implementations of AODV. Some are proposing improvements such as multicast and ipv6 compatibility. Name AODV-UCSB

IP 4

Operating Systems Free BSD

AODV-UIUC Net AODV-UU AODV-UU for IPv6 AODV for Windows HUT AODV for IPv6 KERNEL-AODV MAODV

4

Linux

License Comments BSD Compliant with AODV Draft v6 (No longer supported) GNU

4 6

Linux, Embedded Linux Linux

GNU GNU

4

MS Windows XP

?

6

Linux

BSD

AODV IPv6 draft 01

4 4

Linux Linux

? GNU

TinyAODV

n/a TinyOS

BSD

UoB-JAdhoc

4

GPL

RFC 3561 Compliant Multicast AODV, based on AODV-UU Simplified version of AODV for TinyOS RFC 3561 Compliant

UoBWinAODV WinAODV

4 4

Mixed GNU

RFC 3561 Compliant RFC 3561 Compliant

Linux, Windows (XP & 2000), Embedded Linux Windows XP Windows XP & Windows CE

RFC 3561 Compliant AODV for IPv6

Table 3-1: List of available AODV implementation

3.2 Dynamic Source Routing (DSR) As a reactive protocol, DSR has some similitude with AODV. Thus, the difference with AODV is that DSR focuses on the source routing rather than on exchanging tables.

3.2.1 Algorithm DSR uses explicit source routing, which means that each time a data packet is sent, it contains the list of nodes it will use to be forwarded. In other terms, a sent packet contains the route it will use. This mechanism allows nodes on the route to cache new routes, and also, allows the originator to specify the route it wants, depending on criteria such as load balancing, QoS… This mechanism also avoids routing loops.

BSc Honours Project Report

22

If a node has to send a packet to another one, and it has no route for that, it initiates a route discovery process. This process is very similar to the AODV protocol as a route request is broadcast to the initiator neighbourhood until a route is found. Thus, the difference is that every node used for broadcasting this route request packet deduces the route to the originator, and keeps it in cache. Also, there can be many route replies for a single request.

Figure 3-2: DSR route discovery process

In figure 3-4, A wants a route to E. It broadcasts a route request to its neighbours with an arbitrary chosen ID. Neighbours forward this broadcast, and at each node, the reverse route entry is added into the route request packet. When E receives this route request, it can sent a route reply to A using the reverse route included in the packet. The route reply packet contains the request ID and the reverse route. Another difference with AODV is in the route maintenance process. DSR does not use broadcasts such as AODV‟s “HELLO” packets. Instead, it uses layer two built-in acknowledgments.

Figure 3-3: DSR route maintenance process

In Figure 3-5, A is responsible for the flow between A and B, B is responsible for the flow between B and C, and so on. If A is sending data to E, with a previously cached route, and C didn‟t receive any acknowledgment from D, then, C deduces the link is broken and sends a “ROUTE ERROR” packet to A and any other nodes who had previously used this link. Concerned nodes will then remove this route from their table, and use another one if they had other answers from their previous queries. Otherwise, the route discovery process is used in order to find another path to E.

BSc Honours Project Report

23

3.2.2 Implementation The table 3-2 shows the list of implementations available for DSR. There is no ipv6 support available at this stage, neither QoS nor security additional features. Name

IP

DSR Router MCL

4 4

Monarch Project PicoNet Mobile Router DSR Router MCL

4

Monarch Project PicoNet Mobile Router

Operating Systems Linux MS Windows

License

?

4

Free BSD 3.3 and 2.2.7 Linux

User space, DSR Draft ? LQSR – Layer 2.5 source routing with multi-radio support & several link selection metrics Compliant to DSR draft 03

GPL

Compliant to DSR draft 05

4 4

Linux MS Windows

GNU MSRSSLA

4

Free BSD 3.3 and 2.2.7 Linux

?

User space, DSR Draft ? LQSR – Layer 2.5 source routing with multi-radio support & several link selection metrics Compliant to DSR draft 03

GPL

Compliant to DSR draft 05

4

GNU ? MSRSSLA

Comments

Table 3-2: List of available implementations for DSR

3.3 Other Reactive protocols 3.3.1 Temporally-Ordered Routing Algorithm (TORA) This protocol has been made for reducing the impact of mobility in Ad Hoc networks. For reducing this impact, each node is learning more than one route for each destination. By this way, if links are broken, the impact is minimal, only a few routes will be broken. Another characteristic of this protocol is that control messages are only concerned with nodes near the event source of these messages. For example, if a link is broken, the broadcast concerning this event will not be relayed on the whole topology. In this protocol, using the shortest path is not the most important, as using the longest path avoids traffic and latency related to the route discovery process. TORA also uses Directed Acyclic Graph (DAG), using the direction of the node for the broadcasting process.

BSc Honours Project Report

24

3.3.2 Relative Distance Micro-discovery Ad Hoc Routing (RDMAR) RDMAR has been made in order to reduce the amount of control traffic caused by quick topology changes. This protocol uses a new way to discover routes, called Relative Distance Micro-discover (RDM). The idea of RDM is to rely on the fact that broadcast messages can be based on a relative distance (RD) between two nodes. An algorithm is used for estimating the distance between two nodes, using information about node mobility, time past between the last communication and the last value of the RD. Based on this new RD, flooding can be made only in the direction where the node might be found.

BSc Honours Project Report

25

4 HYBRIDS PROTOCOLS A routing protocol is proactive when it continually maintains its routing table. By this way, routes are available when needed. Reactive protocol starts a route discovery process when data has to be sent. The advantage of a proactive protocol is that when a datagram must be sent, the route is already available, so, the processing time to find a route in the routing table is not important. Reactive protocols require much more time for finding a route as they are “On Demand”. But, in an Ad Hoc environment, nodes are willing to move, and then, it reflects frequent changes in the topology. In such an environment, reactive protocols are much more reliable and efficient as proactive protocol will require exchanging a lot of data. Hybrid protocols tend to merge advantages of reactive and proactive protocols. Their aim is to use an “On Demand” route discovery system, but, with a limited research cost. This chapter will cover the Zone Routing Protocol (ZRP), as it is known to be the main protocol in this category. Others protocols such as the Hazy Sighted Link State Routing Protocol (HSLS) exist, but they are not as well documentated and implemented as ZRP.

4.1 Definition The Zone Routing Protocol (ZRP) is the reference in terms of hybrid protocol. Initiated by staff of the Cornell University, it is a hybrid routing framework using both reactive and proactive ad hoc routing protocol. Even if this proposition has been rejected by the MANET group, it still stands as the most advanced hybrid routing project for Ad Hoc networks. ZRP relies on the simple fact that nearest changes are the most important. So, in order to reduce useless traffic on the topology, the approach is to define zones for each node. Inside each zone, a proactive routing protocol will be used. This proactive protocol will be defined as IntrAzone Routing Protocol (IARP) in the ZRP protocol, in opposition to the IntErzone Routing Protocol (IERP) which will be used for finding a route outside the defined zone. This inter-zone routing protocol will be a reactive protocol. ZRP did not define any specific protocol for IARP. In fact, ZRP is more a framework than an entire solution, and then, IARP and IERP are free to be chosen BSc Honours Project Report

26

In addition to this, two other protocols are defined in the framework; they are used for zoning specific problems. These protocols are Neighbour Detection Protocol (NDP) and Border Resolution Protocol (BRP).

Figure 4-1: Structure of ZRP protocol

4.2 Zone Routing, Zone Radius and Bordercasting notions As ZRP uses two routing protocols, a zone has to be defined for each node. These zones are defined on a metric distance, which means depending on the number of hops. Each node will use the Neighbour Detection Protocol (NDP) in order to draw a table of their neighbour. The zone for each node is then defined by peripheral nodes, these nodes are at a specific hop distance from the central node. This number of hops is called the zone radius.

BSc Honours Project Report

27

Figure 4-2: ZRP zone definition

Figure 4-2 shows an example for a zone with a radius of two. B is the central node; C, E and F are the peripheral nodes, as they are two hops

distance

from B. As G is three hops distance from B, it is out of the zone. Given the definition of ZRP, inside this zone, an IARP will be used. But, for communicating outside of this zone, IERP will be used. An important mechanism for ZRP is bordercasting. Bordercasting can be described as a multicast for peripheral nodes only. While using IARP, data is sent using unicast (or multicast, depending on which protocol has been implemented). Bordercasting is then used for IERP, as it is not concerning nodes within the zone. So, in the example given with figure 4-2, if B uses a bordercast, data will be sent to F, E and C (D and A will act as relays).

4.3 IntrAzone Routing Protocol (IARP) The most reasonable choice for IRAP is to use a proactive protocol based on vector distance algorithm. As every node must know the topology within its zone, this kind of protocol is the most effective, as every route within the topology is known (see chapter 2). Also, as the zone is range limited, there will not be any fluctuation problems, and traffic will also be limited to a small amount of information (as there is a small amount of nodes, so, a small amount of routing entries). The only restrictions to using any kind of proactive routing protocol such as IARP is to do the following modifications, in order to work with IERP and BRP: 

Deactivating neighbourhood detection feature if any and replacing it with ZRP‟s specific neighbourhood table.



Replacing the direct routing table modification process with an update process of IERP table.

BSc Honours Project Report

28

4.4 IntErzone Routing Protocol (IERP) For IERP, an “On Demand” protocol is more suitable as it is the most effective on large topologies. Using a reactive protocol means that every time a packet has to be sent out of the zone of the sender, a route discovery process will start (see chapter 3). So, as the sender knows its neighbours (using IARP), and has no route for the destination, it will bordercast its zone peripheral nodes using IERP “ROUTE REQUEST”. As these peripheral nodes are in their own zone, they know using their own neighbourhood table if they have an appropriate route. If not, they will bordercast the “ROUTE REQUEST” to their own peripheral nodes, except the one they received from. The routing process continues as described by the implemented reactive protocol. As for IARP, any kind of reactive protocol can be used, but, the following modification should be made before implementation: 

Deactivating neighbourhood detection feature and use ZRP built-in table



Manage importing IARP routing tables



Replace broadcasts with BRP bordercasts

4.5 Border Resolution Protocol (BRP) BRP is a delivery service working for the ZRP framework. It is a protocol used in order to control IERP packets flooding and to improve its performance. As explained in chapter 3, reactive protocols broadcast “ROUTE REQUEST” packets to the whole neighbourhood. Using the ZRP framework, each node knows its neighbourhood within the zone radius. So, instead of flooding whole zones, BRP is used for flooding only peripheral nodes. BRP introduces mechanisms in order to make sure that a node is not duplicating any request, and also to check if a node has already responded to the request. For controlling flooding, identifiers are defined in each packet, so, forwarders can detect duplicates. They can also mark a zone as already covered.

4.6 Neighbour Detection Protocol (NDP) Neighbour detection is made on consulting lower layers, such as the layer two for retrieving the MAC table. This process is possible as every node in an Ah Hoc network is broadcasting wireless specific packets (called beacons). Layer 2

BSc Honours Project Report

29

can then build a table containing MAC addresses and then transmit it to the NDP. NDP also exchanges its tables with direct neighbours (depending on the zone radius) in order to allow IARP to build a correct table of the neighbourhood. NDP can also select nodes depending on criteria such as low power, blacklist, QoS…

BSc Honours Project Report

30

5 SIMULATION Deploying an Ah Hoc environment for testing seems pretty impossible. As many parameters have to be taken care of, such as number of devices, topology size, mobility, a network simulator is generally used.

5.1 Simulation System In order to evaluate performance of the previously described project, I designed a simulation system. This system, based on a Linux distribution, was designed in order to simulate wireless scenarios, varying parameters such as topology size, speed of mobile nodes and routing protocol used. Another part of this system was designed in order to interpret and graph results.

Figure 5-1: Simulation system overview

5.1.1 The Network Simulator 2 (NS2) NS2 is the simulator used along with this project. It is open source software which allows a lot of modification, such as adding protocols. Its popularity within the academic community leads to a great development around Ad Hoc research and wireless models. The version used was the latest available, 2-31. It is given with all dependencies, and associated configuration (All In One

BSc Honours Project Report

31

package) In addition to the default Ad Hoc routing protocols implemented in NS2 (DSR, DSDV, AODV and TORA), I have added plugins for ZRP and OLSR. The plugin for OLSR is an implementation called UM-OLSR. It is published and maintained by MASIMUM. The code did not require any changes, and, the installation was eased by a patch file. The plugin for ZRP is available on a project page located on the Cornell University website. This plugin was designed for a much earlier version of NS2, so, I had a few changes to make (see Appendix). For running a simulation using NS2, the first thing to do is describe the scenario to simulate using a TCL script. Then, NS2 will compute the simulation and produce a trace file of events happened. This trace file contains data about packets sent, received, forwarded, dropped, size of packets, type of packets, layer concerned… It also contains nodes moved logs. In order to automate the simulation, a Perl script was used (Perl script 1 in figure 5-2). This scripts goal was to compute a scenario, varying chosen parameters, write it to the file system and launch the simulation. The results were then written into the file system, in a folder tree corresponding to the simulation parameters.

Figure 5-2: Simulation software design

BSc Honours Project Report

32

5.1.2 Processing results In order to interpret the simulation result, I have designed a system based on a database and on a graph generator. The choice of using a database was due to the size and the complexity of the trace files generated per NS2. Trace files could easily take 2Mbytes of space, and the total used disk space after having made all the simulations was 4.16Gbytes. As access to the file system was long, and as only half of the information contained in trace file was useful, I have decided to create a script for parsing all trace files and put each trace in a table, with only the information which was going to be used later. Access to the database was much quicker and very useful as well since I could easily sort the data I needed. The database was split into two tables, one containing information about the simulation scenario, and the other containing the packet trace associated to these simulations. On the table 5-1, we can see that the size of the data has been reduced per 2. Tables 5-2 and 5-3 show the data structure of each MySQL tables.

Table Records Type Size simulation 2,352 MyISAM 362.4 KiB traces 41,863,658 MyISAM 2.4 GiB 2 table(s) 41,866,010 -2.4 GiB Table 5-1: MySQL tables summary

Field

Type

Field

Type

sim_id nodes duration topology speed protocol filename dropped_packets dropped_size routing_packet routing_size traffic_packet traffic_size moves

double int(1) float double varchar(5) varchar(4) varchar(100) double double double double double double double

index sim_id event time node layer type size

double double char(1) float int varchar(3) varchar(4) double

Table 5-3: MySQL table “traces” structure

Table 5-2: MySQL table "simulation" structure

BSc Honours Project Report

33

The other part of the system was a web server with PHP enabled. PHP module for apache allows manipulating MySQL data. Also, with the GD extension, it allows graph rendering.. An additional PHP library, JPGraph, was used for generating these graphs, using the GD extension.

Figure 5-3: Result processing design

5.1.3 Observations The complexity of NS-2 was the main problem of my experiments. A beginner in C++ and a stranger to the TCL family, it took me time to understand how to process. The installation of this software reported bugs at the compilation stage, so, I had to correct a few files. The integration of ZRP was also a problem. Created for a different structure of NS-2, I had to adapt a few parts of its code. Also, ZRP‟s C++ code was erroneous. A lot of warnings related to the C++ syntax were reported while compiling. I first ignored these errors but simulations ends prematurely with a segmentation fault. So, after correcting all these errors, and using debugging options with the compiler, I was able to run simulations. But, after a few seconds, memory leaks appeared. Despite my efforts, I was unable to correct this error, and I could not integrate ZRP into my simulation system.

BSc Honours Project Report

34

Also, there was a conflict with TORA. The problem was located on a TCL object, so, I could not use the usual C++ debugger in order to trace the problem. I was not able to find a solution in the time I had, even by contacting the development team. It seems that the compiler I used with the Linux distribution (Ubuntu) was the cause. As a result, I did not use this protocol. I also had another problem. While test simulations were fine, once in my simulation system, NS-2 reported unusual errors. These errors were related to the scheduler of NS-2, whose aim‟s is to coordinate events in the simulation. The main error was “Time going backwards”, and,it prematurely ends the simulation. A partial trace file was still produced.

Figure 5-4: Results of simulation processing

Figure 5-3 shows the percentage of failed and successful simulations for each protocol. A failed simulation does not mean that there are no results. For example, the average time of calculation for DSR was 70% of the time described in the scenario. Trace files were partially generated and can be processed for further analysis, but with care. Last but not least, NS-2 requires a lot of calculation resources. Even by using a powerful server, a simulation can take 10 minutes in order to be completed. This affected my result, as I could not run the same scenario many times, for adding accuracy by taking average values.

BSc Honours Project Report

35

5.2 Simulation Scenario The scenarios for simulation must demonstrate efficiency of protocols depending on Ad Hoc specifications. These specifications are mainly density of nodes and mobility of nodes. Also, what we want to compare is the amount of control traffic in each case compared to the normal traffic. To meet these requirements, I used the following model: 6

Simulations will use for each scenario four routing protocols: AODV, DSDV, DSR and OLSR.

7

The number of nodes will change from 2 to 99 for each topology.

8

There will be two topology sizes, one for a high density of nodes and one for a low density of nodes.

9

For each topology size, there will be three speed ranges for nodes. The speed will be individually assigned on a random basis within the speed range.

The only parameter I could not master is the traffic regulation. From the example I used, I could only arbitrarily define pairs of stations for establishing a connection. My approach was then to simulate FTP traffic between each pair of nodes. Then, if the node was able to communicate, it would have initiated the communication.

BSc Honours Project Report

36

Figure 5-5: Simulation parameters in a tree

9.1 Simulation results 9.1.1 Application traffic vs. routing traffic By considering the amount of application traffic comparison with the amount of routing traffic, we must first remember some networking facts: packet and size of packet. While transmitting

data, depending on the size of the

message, one or more packets can be used. If the data is smaller than the MTU (Message Transfer Unit), then, one packet is enough. If the data is larger, more packets will be needed. As routing related data consists of small amounts of data, every message will correspond to a single small packet, whereas for application related traffic, packets will have the maximum size. Simulations show that the average size of routing packets is 44 bytes, while the average size of application packets is 580 bytes (with acknowledgments).

BSc Honours Project Report

37

Figure 5-6: Application traffic vs. routing traffic for DSDV, OLSR, AODV and DSR

We can see on figure 5-6 that the results are similar from one protocol to another. For the generation of these graphs, all results were included, without any distinction of density of nodes and speed of nodes. But, we have to consider for this analysis that the amount of traffic was important, and more than 2000 simulation results are merged for these graphs. An average of the routing traffic was 800Tbytes per protocol, all simulations included. The amount of application traffic is around 1E12 bytes in the same context! With these considerations, we can see that, in a manner of size, proactive protocols consume a bit more control traffic than reactive protocol. That is due to the exchange of routing tables. Also, the average of the size of packet is less important for proactive protocols than for reactive protocols, but the number of packets overall is more important.

BSc Honours Project Report

38

Traffic (Tbytes)

Traffic ( million packets)

Routing (Tbytes)

Routing (million packets)

Average size of packet (traffic)

9,122.510

Average size of packet (routing) 74.38

DSDV

892.580

1,620.716

678.603

OLSR

1,139.500

2,071.340

817.407

11,308.664

72.28

550.12

AODV

1,011.099

1,836.136

713.008

9,630.378

74.03

550.66

DSR

1,084.228

1,970.075

776.613

10,913.393

71.16

550.34

TOTAL

4,127.409

7,498.269

2,985.633

40,974.946

72.86

550.44

550.73

Table 5-4: Simulation traffic overview

9.1.2 Impact of the number of nodes We saw within the previous chapter that proactive protocols and reactive protocols have different ways to find routes. One of the interesting things is that some may be more efficient with a small amount of nodes, while others may be more efficient with a larger number of nodes.

BSc Honours Project Report

39

Figure 5-7: Impact of the number of nodes on the routing packets exchanged

We can see with figure 5-7 the evolution of control traffic depending on the number of nodes. For the four protocols, the amount of traffic is stable. The scenario implies that traffic should work in pairs, so, for 2 nodes, the two nodes should generate FTP traffic. For 98 nodes, there should be 49 connections, so the traffic should have grown with the number of nodes. This can be explained by the fact that central nodes in the topology may have been overloaded due to the small bandwidth available on a wireless link. In fact, by performing a further analysis on the trace files, central nodes were forwarding at the maximal operating speed. An important observation is that for a small number of nodes, DSDV and AODV are the protocol generating the smallest amount of packets, while DSR and OLSR produce 10% more. For a larger number of nodes, DSDV is still the most effective protocol. But, figure 5-8, based on the amount of bytes instead of the amount of packets, shows that DSDV is also responsible for a lot of packet loss. Also, it shows that OLSR is the protocol using the most bandwidth.

BSc Honours Project Report

40

Figure 5-8: Impact of the number of nodes on the routing data exchanged

BSc Honours Project Report

41

9.1.3 Impact of Mobility The simulation scenario implies that nodes will move at a random speed range. There were three random ranges, one from 0 to 5 meters per second, another one from 0 to 10 meters per second and the last one from 10 to 20 meters per second. Also, moves are scheduled after 10 seconds (for a total of 15 seconds of simulation). As there are too many parameters to take care of, I will use averages on particular scenarios.

9.1.3.1

DSDV

Figure 5-9 shows a simulation with 20 nodes, a random speed range between 0 and 5 meters per second, and a 500 square meters topology. Traffic between nodes is set to start after 2 seconds.

Figure 5-9: Impact of mobility with DSDV

We can see that for the first two seconds, the traffic is relatively small. That can be explained by the fact that routing tables are empty and two seconds are necessary to stabilize the network (see the fluctuation problem in chapter 2.1). After this, application traffic is at an optimal level, and routing traffic is negligible. After 10 seconds, nodes changes of direction. This does not have an immediate impact, but after two more seconds, the routing traffic starts to increase. This can be explained by the fact that the routing tables were still valid, but as nodes changes of direction, links starts to be broken, and the DSDV algorithm has to perform an important amount of updates.

BSc Honours Project Report

42

9.1.3.2

OLSR

Figure 5-10 shows a simulation with 80 nodes, a random speed range between 0 and 10 meters per second, and a 500 square meters topology. Traffic between nodes is set to start after 2 seconds.

Figure 5-10: Impact of mobility with OLSR

We can see at the very beginning of the simulation traffic related to routing, precisely for the relay selection of OLSR. After, while no traffic is needed, no more routing packets are sent. Comparing with DSDV, more routing traffic occurs after the two first seconds. Also the mobility is not reflected in the trace analysis, the changes of direction of nodes after 10 seconds does not increase the amount of routing packets later. The more important amount of routing packets can be explained by the fact that the speed of nodes is more important than in the scenario used at figure 5-9.

9.1.3.3

AODV

Figure 5-11 shows a simulation with 30 nodes, a random speed range between 0 and 10 meters per second, and a 500 square meters topology. Traffic between nodes is set to start after 2 seconds.

BSc Honours Project Report

43

Figure 5-11: Impact of mobility with AODV

As an “On Demand” protocol, AODV stays silent while there is no traffic to send. That explains the two first seconds with zero traffic. After, there is a peak corresponding to the route discovery process. Peaks represent broken links. Once the route has been discovered, the communication can be established, and no more route discovery process is needed. But, while some nodes are moving quickly, the route is no more valid after 2 more seconds, and new route discoveries have to be used.

9.1.3.4

DSR

Figure 5-12 shows a simulation with 30 nodes, a random speed range between 0 and 5 meters per second, and a 500 square meters topology. Traffic between nodes is set to start after 2 seconds.

BSc Honours Project Report

44

Figure 5-12: Impact of mobility with DSR

We can see that the DSR algorithm causes fewer peaks than AODV. We can suppose it is due to the route reverse learning that each node performs. It is also for the same reason that there is less traffic related to the routing protocol.

9.1.4 Impact of topology size The topology size does not have an important impact. In fact, it is just reducing the amount of traffic as some nodes are out of range. The dynamism it should have had was only reflected when a high speed was applied to nodes, but, in this case, most of the simulation reported a failure.

9.2 The case of ZRP As I could not integrate ZRP into my simulation system, I made some manual simulations in order to compare this protocol with the others. Even if simulations could not be performed entirely, the partial result looks encouraging for this protocol. The amount of ZRP traffic on a given node was around 5%. The documentation on internet claims that on an optimal topology, it can be reduce to 2%.

BSc Honours Project Report

45

10 DISCUSSION This project was very interesting, and there is a lot to discuss. First, Routing on Ad Hoc network is still a research subject, as even if concrete work has been made, the MANET group did not standardise any proposed protocols; Request For Comments, if any, are still in an experimental status. Also, some MANET requirements, such as security and energy problems, are not on the first line. Researchers are trying to find a good algorithm rather than solving these particular points. Even if there are some implementations of security mechanism in some protocols (such as olsrd), Ad Hoc networks are really sensitive, especially if you trust everybody to forward your private data. Nowadays, I would not use an Ad Hoc network for browsing my bank website, as everybody forwarding my messages will be able to read them (if not encrypted). The number of protocols and their documentation is also a problem. More than a hundred routing protocols for Ad Hoc are listed on the Wikipedia website. Some are pure protocols, others are specific case implementations. This diversity made the documentation part of this project a really hard task, and at the end, the least confusing way to find reliable information was to directly read the RFCs. Last but not least, testing Ad Hoc networks is not as simple as I thought. As real tests would have been almost impossible to carry out, the simulation was necessary. But, using a simulator

such as NS-2 requires some knowledge

about this software, and I mainly used my time to fix errors

rather than

taking advantage of such a tool. I cannot deny that this project developed my knowledge, and, it also helped me to use and improve the knowledge that I accumulated during my education,

from

database

to

computer

science,

networking

and

telecommunication. But, I wish I could have spent more time and had more resources in order to correct my errors on the scenario design I have made for simulations.

BSc Honours Project Report

46

11 CONCLUSION We discovered during this project the problems associated with Ad Hoc networks, more specifically routing on Ad Hoc networks. We also discovered solutions for these problems. Five routing protocols were covered. First, proactive protocols; table-driven as their peers in the wired world, they have the disadvantage of not being really reactive to topology changes. DSDV in particular is subject to route fluctuation, and brings a lot of instability. OLSR tends to correct this problem. Then, we covered reactive protocols; a new approach for wireless networks, with the “On Demand” routing mechanism. They have the advantage of not being vulnerable to dynamism in topologies, but have the disadvantage of having higher delays than proactive protocols. They can rely on old routing techniques, such as the vector distance that AODV adapts to the “On Demand” approach, or can use less current mechanisms, such as the source routing characterising DSR. The last protocol covered was ZRP, taking the advantage of both proactive and reactive protocols. Even by testing protocols, there is no perfect solution. The test carried out shows that protocol efficiency depends on the context. On large and dynamic topologies, reactive protocols will have an advantage, while on small and relatively

fixed

topologies;

proactive

protocols

will

be

more

efficient.

Nevertheless, hybrid protocols have a slight advantage on both approaches, as they use a proactive protocol for small distances and a reactive protocol for longer distances.

BSc Honours Project Report

47

REFERENCES Charles Perkins. and Pravin Bhagwat, “Highly Dynamic DestinationSequenced Distance-Vector Routing (DSDV) for Mobile Computers” RFC 4728 : “The DSR specification” RFC 3626 : “The OLSR specification” RFC 3561 : “The AODV specification” Zygmunt Haas, Marc Pearlman and Prince Samar “The Zone Routing Protocol (ZRP) for Ad Hoc Networks”

BIBLIOGRAPHY Wikipedia http://en.wikipedia.org ZRP homepage http://www.zrp.be NS-2 official website http://www.isi.edu/nsnam/ns OLSR developer team: http://www.inria.fr Andrew Tanenbaum “Les Réseaux” Tayeb Lemlouma “Le Routage dans les Réseaux Mobiles Ad Hoc” Thomas Clausen “Comparative Study of Routing Protocols for Mobile Ad-hoc NETworks” Francisco Ros and Pedro Ruiz “Implementing a New Manet Unicast Routing Protocol in NS2” Yuan Yuan NS-2 homepage: http://www.cs.umd.edu/~yuanyuan/Linksold.html Mark Greis’ tutorial on NS-2: http://www.isi.edu/nsnam/ns/tutorial

APPENDIX A The simulation system SQL Script The following script was used for creating the tables in the project database. Data format was selected in order to reduce the overall size of data. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

-- Simulation table structure CREATE TABLE `simulation` ( `sim_id` double NOT NULL, `nodes` int(1) NOT NULL, `duration` float NOT NULL, `topology` double NOT NULL, `speed` varchar(5) NOT NULL, `protocol` varchar(4) NOT NULL, `filename` varchar(100) NOT NULL, `dropped_packets` double NOT NULL, `dropped_size` double NOT NULL, `routing_packet` double NOT NULL, `routing_size` double NOT NULL, `traffic_packet` double NOT NULL, `traffic_size` double NOT NULL, `moves` double NOT NULL, PRIMARY KEY (`sim_id`) ) ENGINE=MyISAM DEFAULT CHARSET=latin1; -- Trace table structure CREATE TABLE `traces` ( `index` double NOT NULL auto_increment, `sim_id` double NOT NULL, `event` char(1) NOT NULL, `time` float default NULL, `node` int default NULL, `layer` varchar(3) default NULL, `type` varchar(4) default NULL, `size` double default NULL, PRIMARY KEY (`index`) ) ENGINE=MyISAM DEFAULT CHARSET=latin1;

Perl 1 Script The Perl 1 script (See figure 5-1 and figure 5-2) was the script used in order to compute simulation scenarios. Some of the parameters of this script are hard coded and were changed (topology size and speed). 1 2 3 4

#!/usr/bin/perl -w $routingp[0] = "DSDV"; $routingp[1] = "AODV"; $routingp[2] = "DSR";

5 $routingp[3] = "OLSR"; 6 $nbnode = 100; 7 $speed=10; 8 $size=2000; 9 10 if (! -e "/home/project/simulation/log") { system("touch /home/project/simulation/log") ; } 11 open(LOG,">>/home/project/simulation/log") || die "Erreur de lecture /home/project/simulation/log, Erreur: $!"; 12 $m=0; 13 while(TRUE) { 14 if($m==4) { exit(); } 15 for($l=2; $l<$nbnode; $l = $l+1) { 16 $home_folder = "/home/project/simulation/".$routingp[$m]; 17 $work_folder = $home_folder."/".$l; 18 if (! -d "$work_folder") { 19 print "Creating home folder $work_folder\n"; 20 mkdir ($work_folder); 21 } 22 $k=1; 23 while (-e "$work_folder/$k.tcl") { 24 $k++; 25 } 26 27 $mapx = $size; 28 $mapy = $size; 29 30 print LOG "Start simulation with routing protocol $routingp[$m]\t mobile node = $l \t instance $k\n"; 31 system("touch $work_folder/$k.tcl"); 32 open(FILE,">$work_folder/$k.tcl") || die "Erreur de lecture $work_folder/$k.tcl, Erreur: $!"; 33 init(); 34 place_nodes(); 35 generate_movement(); 36 generate_traffic(); 37 finish(); 38 39 sub init { 40 print FILE "# Define options 41 set val(chan) Channel/WirelessChannel ;# channel type 42 set val(prop) Propagation/TwoRayGround ;# radio-propagation model 43 set val(netif) Phy/WirelessPhy ;# network interface type 44 set val(mac) Mac/802_11 ;# MAC type\n"; 45 if ($m==3) { 46 print FILE "set val(ifq) CMUPriQueue ;# interface queue type\n"; 47 } 48 else { print FILE "set val(ifq) Queue/DropTail/PriQueue ;# interface queue type\n"; } 49 print FILE " set val(ll) LL ;# link layer type 50 set val(ant) Antenna/OmniAntenna ;# antenna model 51 set val(ifqlen) 50 ;# max packet in ifq 52 set val(nn) $l

;# number of mobilenodes 53 set val(rp) $routingp[$m] ;# routing protocol 54 set val(x) $mapx ;# X dimension of topography 55 set val(y) $mapy ;# Y dimension of topography 56 set val(stop) 15 ;# time of simulation end 57 set ns [new Simulator] 58 set tracefd [open $work_folder/$k.trace.tr w] 59 60 \$ns trace-all \$tracefd 61 # set up topography object 62 set topo [new Topography] 63 64 \$topo load_flatgrid \$val(x) \$val(y) 65 66 create-god \$val(nn) 67 68 # 69 # Create nn mobilenodes [\$val(nn)] and attach them to the channel. 70 set chan_1_ [new \$val(chan)] 71 72 # configure the nodes 73 \$ns node-config -adhocRouting \$val(rp) \\ 74 -llType \$val(ll) \\ 75 -macType \$val(mac) \\ 76 -ifqType \$val(ifq) \\ 77 -ifqLen \$val(ifqlen) \\ 78 -antType \$val(ant) \\ 79 -propType \$val(prop) \\ 80 -phyType \$val(netif) \\ 81 -channel \$chan_1_ \\ 82 -topoInstance \$topo \\ 83 -agentTrace ON \\ 84 -routerTrace ON \\ 85 -macTrace OFF \\ 86 -movementTrace ON 87 88 for {set i 0} {\$i < \$val(nn) } { incr i } { 89 set node_(\$i) [\$ns node] 90 }\n"; 91 } 92 93 sub place_nodes { 94 print FILE "# Provide initial location of mobilenodes 95 for {set i 0} {\$i < \$val(nn) } { incr i } { 96 \$node_(\$i) set X_ [expr ($mapx*rand())] 97 \$node_(\$i) set Y_ [expr ($mapy*rand())] 98 \$node_(\$i) set Z_ 0.0 99 } 100 "; 101 } 102 103 sub generate_movement { 104 print FILE "# Generation of movement 105 for {set i 0} {\$i < \$val(nn) } {incr i} { 106 for {set j 0} {\$j < \$val(stop) } {set j [expr

{\$j + 10}]} { 107 \$ns at \$j \"\$node_(\$i) setdest [expr ($mapx*rand())] [expr ($mapy*rand())] [expr (10+$speed*rand())]\" 108 } 109 } 110 "; 111 } 112 sub generate_traffic { 113 for($i=0; $i<$l-1; $i = $i+2) { 114 print FILE "# Generation of traffic 115 set tcp$i [new Agent/TCP/Newreno] 116 \$tcp$i set class_ 2 117 set sink$i [new Agent/TCPSink] 118 \$ns attach-agent \$node_($i) \$tcp$i 119 \$ns attach-agent \$node_(".($i+1).") \$sink$i 120 \$ns connect \$tcp$i \$sink$i 121 set ftp$i [new Application/FTP] 122 \$ftp$i attach-agent \$tcp$i 123 \$ns at 2.0 \"\$ftp$i start\" 124 "; 125 } 126 } 127 128 sub finish { 129 print FILE " 130 131 132 # Telling nodes when the simulation ends 133 for \{set i 0\} \{\$i < \$val(nn) \} \{ incr i \} \{ 134 \$ns at \$val(stop) \"\$node_(\$i) reset\"; 135 \} 136 137 # ending nam and the simulation 138 \$ns at \$val(stop) \"stop\" 139 \$ns at 150.01 \"puts \\\"end simulation\\\" ; \$ns halt\" 140 proc stop \{\} \{ 141 global ns tracefd 142 \$ns flush-trace 143 close \$tracefd 144 \} 145 146 \$ns run 147 "; 148 } 149 close(FILE); 150 system ("ns $work_folder/$k.tcl"); 151 } 152 $m++; 153 } 154 155 close(LOG);

Perl 2 Script

This script was used in order to extract the main information of each simulation and put this data into the “simulation” table of the project database (see figure 5-1 and figure 5-3). 1 #!/usr/bin/perl -w 2 use Switch; 3 use DBI; 4 $dbh = DBI->connect( "DBI:mysql:database=project;host=localhost", 5 "project", 6 "project", 7 {'RaiseError' => 1} 8 ); 9 10 $folder[0]="sim100-5-500"; 11 $folder[1]="sim100-10-500"; 12 $folder[2]="sim100-10+5-500"; 13 $folder[3]="sim100-5-2000"; 14 $folder[4]="sim100-10-2000"; 15 $folder[5]="sim100-10+5-2000"; 16 17 $size[0]=500; 18 $size[1]=2000; 19 20 $speed[0]="5"; 21 $speed[1]="10"; 22 $speed[2]="10+10"; 23 24 $routingp[0] = "DSDV"; 25 $routingp[1] = "AODV"; 26 $routingp[2] = "DSR"; 27 $routingp[3] = "OLSR"; 28 29 $index=1; 30 31 for($i=0; $i<6; $i++) { 32 for($m=0; $m<4; $m++) { 33 $home_folder = "/home/project/".$folder[$i]."/".$routingp[$m]; 34 for($l=2; $l<100; $l++) { 35 $work_folder = $home_folder."/".$l; 36 $filename=$work_folder."/1.trace.tr"; 37 if ($i<3) { $n=0; } 38 else { $n=1; } 39 if ( $i==0 || $i==3 ) { $o = 0; } 40 if ( $i==1 || $i==4 ) { $o = 1; } 41 if ( $i==2 || $i==5 ) { $o = 2; } 42 open(FILE,"<$filename"); 43 if (FILE) { 44 @file = ; 45 foreach $line (@file) { 46 @words = split(/ /, $line); 47 if($words[0] eq "M") { $moves++;} 48 if($words[0] eq "D" || $words[0] eq "d") { 49 if($words[4] eq "NRTE") { 50 $traffic_size+=$words[7]; 51 } 52 else { $dropped_size+=$words[8]; }

53 $dropped_packets++; 54 } 55 if($words[0] eq "s" || $words[0] eq "r") 56 { if($words[3] eq "AGT") { 57 $traffic_packet++; 58 $traffic_size+=$words[8]; 59 } 60 else { 61 if($words[3] eq "RTR") { 62 if($words[7] eq "tcp" || $words[7] eq "ack") { 63 } 64 else { 65 $routing_packet++; 66 $routing_size+=$words[8]; 67 } 68 } 69 } 70 } 71 $duration = $words[1]; 72 } 73 close(FILE); 74 } 75 else { $duration=0; } 76 $query = "INSERT INTO simulation ( 77 sim_id, 78 nodes, 79 duration, 80 topology, 81 speed, 82 protocol, 83 filename, 84 dropped_packets, 85 dropped_size, 86 routing_packet, 87 routing_size, 88 traffic_packet, 89 traffic_size, 90 moves 91 ) 92 VALUES ( 93 '$index', 94 '$l', 95 '$duration', 96 '$size[$n]', 97 '$speed[$o]', 98 '$routingp[$m]', 99 '$filename', 100 '$dropped_packets', 101 '$dropped_size', 102 '$routing_packet', 103 '$routing_size', 104 '$traffic_packet', 105 '$traffic_size', 106 '$moves' 107 );"; 108 print "sim_id '$index', nodes '$l', duration '$duration', topology '$size[$n]', speed '$speed[$o]', protocol '$routingp[$m]'\n"; 109 $sth = $dbh->prepare($query); 110 $res = $sth->execute;

111 112 113 114 }

$index++; } }

Perl 3 script This script is similar to the last one except it parses trace files in detail and put each trace into the „trace‟ table of the project database (see figure 5-1 and figure 5-3). 1 #!/usr/bin/perl -w 2 use Switch; 3 use DBI; 4 $dbh = DBI->connect( "DBI:mysql:database=project;host=localhost", 5 "project", 6 "project", 7 {'RaiseError' => 1} 8 ); 9 10 $folder[0]="sim100-5-500"; 11 $folder[1]="sim100-10-500"; 12 $folder[2]="sim100-10+5-500"; 13 $folder[3]="sim100-5-2000"; 14 $folder[4]="sim100-10-2000"; 15 $folder[5]="sim100-10+5-2000"; 16 17 $size[0]=500; 18 $size[1]=2000; 19 20 $speed[0]="5"; 21 $speed[1]="10"; 22 $speed[2]="10+10"; 23 24 $routingp[0] = "DSDV"; 25 $routingp[1] = "AODV"; 26 $routingp[2] = "DSR"; 27 $routingp[3] = "OLSR"; 28 open(LOG,">>/home/project/traces_log"); 29 $index=1; 30 for($i=0; $i<6; $i++) { 31 for($m=0; $m<4; $m++) { 32 #$home_folder = "/home/project/".$folder[$i]."/".$routingp[$m]; 33 34 35 for($l=2; $l<100; $l++) { 36 $query = "SELECT `filename` FROM `simulation` WHERE sim_id =$index"; 37 $sth = $dbh->prepare($query); 38 $res = $sth->execute; 39 $row = $sth->fetchrow_hashref; 40 print $row->{filename}."\n"; 41 $filename=$row->{filename}; 42 #$work_folder = $home_folder."/".$l; 43 #$filename=$work_folder."/1.trace.tr";

44 if ($i<3) { $n=0; } 45 else { $n=1; } 46 if ( $i==0 || $i==3 ) { $o = 0; } 47 if ( $i==1 || $i==4 ) { $o = 1; } 48 if ( $i==2 || $i==5 ) { $o = 2; } 49 open(FILE,"<$filename"); 50 if (FILE) { @file = ;} 51 else { @file={0}; } 52 foreach $line (@file) { 53 @words = split(/ /, $line); 54 @node = split(//, $words[2]); 55 if($words[0] eq "M") { 56 $query = "INSERT INTO traces ( 57 sim_id, 58 event, 59 time, 60 node 61 ) 62 VALUES ( 63 '$index', 64 'M', 65 '$words[1]', 66 '$words[2]' 67 );"; 68 } 69 else { $query = "INSERT INTO traces ( 70 sim_id, 71 event, 72 time, 73 node, 74 layer, 75 type, 76 size) 77 VALUES ( 78 '$index', 79 '$words[0]', 80 '$words[1]', 81 '$node[1]', 82 '$words[3]', 83 '$words[7]', 84 '$words[8]' 85 );"; 86 87 } 88 #print LOG "sim_id $index,event $words[0],time $words[1],node $node[1],layer $words[3],type $words[7],size $words[8]\n"; 89 $sth = $dbh->prepare($query); 90 $res = $sth->execute; 91 } 92 close(FILE); 93 $index++; 94 } 95 } 96 } 97 close(LOG);

Example of PHP script for generating graphs The following script was used in order to generate the figure 5-12 graph

1 =$j)$j++; 54 } 55 56 // Free results 57 mysql_free_result($result); 58 59 // Close connexion 60 mysql_close($link);

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

$graph = new Graph (500,300,"auto"); $graph->SetScale("linlin"); $graph->title->Set("Trace analysis for simulation $sim_id"); $graph->img->SetMargin(70,30,20,40); // First create the individual plots $p[] = new LinePlot($move); $p[] = new LinePlot($traffic); $p[] = new LinePlot($routing); $p[] = new LinePlot($dropped); $p[0]->SetLegend("Mouvement"); $p[1]->SetLegend("Traffic"); $p[2]->SetLegend("Routing"); $p[3]->SetLegend("Dropped"); $p[0]->SetFillColor("red"); $p[1]->SetFillColor("blue"); $p[2]->SetFillColor("green"); $p[3]->SetFillColor("yellow"); // Then add them together to form a accumulated plot $accplot = new AccLinePlot($p); // Add the accumulated line plot to the graph $graph->Add($accplot); $graph->xaxis->SetTitle('Time (mseconds)','middle'); $graph->yaxis->SetTitle('Traffic (packets)','middle'); $graph->yaxis->SetLabelPos(SIDE_TOP); $graph->legend->Pos(0.8,0.1,"left","top"); $graph->Stroke(); ?>

APPENDIX B Installation of NS-2 under Ubuntu 6.06 In order to install the NS-2 suite, the first thing to do is to retrieve the latest version of the all-in-one package. Then, we should be sure that we have the necessary libraries in order to compile the software. On a default system, the following command will automatically retrieve and install these libraries. #apt-get install gcc g++ make automake libxmu-dev Then, as root in a terminal, extract the package containing NS-@ and all the libraries, and execute the install script: #tar –xvzf ns-allinone-2.31.tar.gz #cd ns-allinone-2.31 #./install The installation can be tested by executing a test script (see output of the install script). More specifically, for NS-2, a correction has to be made on the file ns-allinone2.31/ns-2.31/mac/wireless-phy.cc, line 55, the line redefining “MAX” should be commented as it is already defined as per a header file. In order to install OLSR, the archive containing the code should be downloaded on the UM-OLSR webpage. This package contains a patch file with code. The patch file will do all the work. There might be some conflicts depending of the version (latest version supported of NS-2 is 2.29), but these conflicts are minor and can be easily recovered. The patch will add OLSR entries into NS-2 common code. NS-2 must be recompiled after this new addition. #cd ns-allinone-2.31/ns-2.31/ #make clean #./configure –-enable-debug #make #make install The installation of ZRP is a bit more complex. The latest version supported for NS-2 is more than 3 years old. It is also given with a patch file. This file can

be modified in order to reflect the changes over the last versions (a few number of lines to change). The code has also to be modified since the new version of C++ compiler requires a correct syntax. The code must be changed as variables in constructors must be declared in the same order they are used in the constructor‟s arguments.