Manet Report

1. INTRODUCTION A Network is defined as the group of people or systems or organizations who tend to share their information collectively for their business purpose. In Computer terminology the definition for networks is similar as a group of computers logically connected for the sharing of information or services (like print services, multi-tasking, etc.). Initially Computer networks were started as a necessity for sharing files and printers but later this has moved from that particular job of file and printer sharing to application sharing and business logic sharing.These networks may be fixed (cabled, permanent) or temporary. A network can be characterized as wired or wireless. Wireless can be distinguished from wired as no physical connectivity between nodes are needed. A mobile ad-hoc network (MANET) is an autonomous system of mobile nodes, a kind of a wireless network where the mobile nodes dynamically form a network to exchange information without utilizing any pre-existing fixed network infrastructure.For a MANET to be constructed, all needed is a node willing to send data to a node willing to accept data. Each mobile node of an ad-hoc network operates as a host as well as a router, forwarding packets for other mobile nodes in the network that may not be within the transmission range of the source mobile node. Each node participates in an ad-hoc routing protocol that allows it to discover multi-hop paths through the network to any other node.

1

fig 1.1 MANET is the infrastructureless approach to WLANs and WLLs etc. It is a self-configuring network of nodes and routers connected by wireless links, which in synchronization form a dynamic topology. These networks operate in standalone manner where routers and nodes are free to move and organize themselves randomly, causing a rapidly changing topology. This is why, these networks are very flexible and suitable for several types of applications, as they allow the establishment of temporary communication without any pre installed infrastructure. The transmission range of a mobile node in the network is limited to a circular region around the node, whose radius depends on the transmitted power, receiver sensitivity and propagation loss model. If the destination node is not in the transmission range of the source node, then the mobile ad hoc network works like a multi hop network with one or more node acting as routing node. Due to the limited wireless transmission range of each node, data packets then may be forwarded along multi-hops. The three types of traffic in MANETS are 1) Peer –to Peer: Communication between two nodes with one hop 2) Remote to Remote: Communication beyond one hop but existence of stable route 3) Dynamic Traffic: Nodes are dynamic and routes are reconstructed frequently.

fig 1.2 2

2. WIRED V/S WIRELESS NETWORKS The different types of networks available today are Wired and Wireless networks. Wired are differentiated from wireless as being wired from point to point.

2.1 WIRED NETWORKS These networks are generally connected with the help of wires and cables. Generally the cables being used in this type of networks are CAT5 or CAT6 cables. The connection is usually established with the help of physical devices like Switches and Hubs in between to increase the strength of the connection. These networks are usually more efficient, less expensive and much faster than wireless networks. Once the connection is set there is a very little chance of getting disconnected.

2.1.1 ADVANTAGES •

A wired network offer connection speeds of 100Mbps to 1000Mbps

•

Physical, fixed wired connections are not prone to interference and fluctuations in

•

Available bandwidth, which can affect some wireless networking connections.

2.1.2 DISADVANTAGES OVER WIRELESS NETWORKS •

Expensive to maintain the network due to many cables between computer systems and even if a failure in the cables occur then it will be very hard to replace that

particular

cable as it involved more and more costs. •

When using a laptop which is required to be connected to the network, a wired network will limit the logical reason of purchasing a laptop in the first place.

3

2.2 WIRELESS NETWORKS Wireless networks use some sort of radio frequencies in air to transmit and receive data instead of using some physical cables. The most admiring fact in these networks is that it eliminate the need for laying out expensive cables and maintenance costs. 2.2.1 ADVANTAGES OF WIRELESS NETWORKS •

Mobile users are provided with access to real-time information even when they are away from their home or office.

•

Setting up a wireless system is easy and fast and it eliminates the need for pulling out the cables through walls and ceilings.

•

Network can be extended to places which can not be wired.

2.2.2 DISADVANTAGES OF WIRELESS NETWORKS •

Interference due to weather, other radio frequency devices , or obstructions like walls.

•

The total Throughput is affected when multiple connections exists.

2.2.3 PROBLEMS IN WIRELESS COMMUNICATION Some of the problems related to wireless communication are multipath propagation, path loss, interference, and limited frequency spectrum. Multipath Propagation is, when a signal travels from its source to destination, in between there are obstacles which make the signal propagate in paths beyond the direct line of sight due to reflections, refraction and diffraction and scattering. Path loss is the attenuation of the transmitted signal strength as it propagates away from the sender. Path loss can be determined as the ratio between the powers of the transmitted signal to the receiver signal. This is mainly dependent on a number of factors such as radio frequency and the nature of the terrain. It is sometimes important to estimate the path loss in wireless communication networks. Due to the radio frequency and the nature of the terrain are not same 4

everywhere, it is hard to estimate the path loss during communication. During communication a number of signals in the atmosphere may interfere with each other resulting in the destruction of the original signal. Limited Frequency Spectrum is where, frequency bands are shared by many wireless technologies and not by one single wireless technology.

5

3. FEATURES OF MANET 3.1 Dynamic Topologies 3.2 Bandwidth-constrained, variable capacity links 3.3 Power-constrained operations 3.4 Limited physical security

3.1 DYNAMIC TOPOLOGIES Nodes are free to move arbitrarily; thus network topology—which is typically multihop—may change randomly and rapidly at unpredictable times. Adjustment of transmission and reception parameters such as power may also impact the topology.

3.2 BANDWIDTH-CONSTRAINED, VARIABLE CAPACITY LINKS Wireless links will continue to have significantly lower capacity than their hard-wired counterparts. One effect of this relatively low to moderate link capacities is that congestion is typically the norm rather than the exception; i.e. aggregate application demand is likely to exceed network capacity frequently.

3.3 POWER-CONSTRAINED OPERATIONS Some or all the nodes in a MANET rely on batteries for their energy. Thus, for these nodes, the most important design criteria may be that of power conservation.

3.4 LIMITED PHYSICAL SECURITY Mobile wireless networks are generally more prone to physical security threats than fixed, hardwired networks. Existing link security techniques are often applied within wireless networks to reduce security threats. 6

4.USES OF MOBILE AD HOC NETWORKS 4.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:

fig 4.1 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. 7

4.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).

4.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 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.

8

5. PROBLEMS IN MANET 5.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). 5.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 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.

5.3 ENERGY 9

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 omni-directional, as they need much more energy.

5.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. 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. 5.5 INTERFERENCE This is the major problem with mobile ad-hoc networks as links come and go depending on the transmission characteristics, one transmission might interfere with another one and node might overhear transmissions of other nodes and can corrupt the total transmission.

5.6 DYNAMIC TOPOLOGY This is also the major problem with ad-hoc routing since the topology is not constant. The mobile node might move or medium characteristics might change. In ad-hoc networks, routing tables must somehow reflect these changes in topology and routing algorithms have to be adapted. For example in a fixed network routing table updating takes place for every 30sec. This updating frequency might be very low for ad-hoc networks.

5.7 ROUTING OVERHEAD 10

In wireless ad-hoc networks, nodes often change their location within network. So, some stale routes are generated in the routing table which leads to unnecessary routing overhead.

6. ROUTING IN MANET 11

6.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.

6.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 the number of hops, the “shortest path”, or including more data for judging the best route, such as latency, congestion…

12

RIP (Routing Information Protocol)

One of the most basic and known routing protocols. Takes its decisions on the status of links (up or down) and the shortest path.

IGRP (Interior Gateway Routing An evolution of RIP using Protocol) bandwidth, load, delay, MTU, and reliability for building routing tables. EIGRP (Enhanced Interior Gateway An Evolution of IGRP, introducing Routing Protocol) router status in addition of link status. OSPF (Open Shortest Path First)

A link stated and shortest path protocol.

BGP (Border Gateway Protocol)

Standard protocol for the Internet core. table 6.1

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).

6.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 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 13

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.

fig 6.1

6.4 AD-HOC ROUTING PROTOCOLS There were different approaches, and then, different solutions. The three mains approaches are proactive protocols, reactive protocols and hybrids. 6.4.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 preestablished. 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.

6.4.2 REACTIVE 14

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 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. 6.4.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.

7. PRO-ACTIVE PROTOCOLS

15

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.

7.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. 7.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 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 16

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). 7.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.

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

17

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

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).

7.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.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. 7.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. 18

7.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.

19

fig 7.3 On figure 7.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 twohop 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.

20

fig 7.4 7.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.

8. REACTIVE PROTOCOLS As covered in chapter 7, 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.

8.1 AD HOC ON-DEMAND DISTANCE VECTOR (AODV) 21

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. 8.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 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. 8.1.2 ILLUSTRATION

22

fig 8.1 In the example illustrated by figure 8.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). 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.

8.2 DYNAMIC SOURCE ROUTING (DSR) 23

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. 8.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. 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.

fig 8.2

In figure 8.2, 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.

24

fig 8.3

In Figure 38.3, 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.

9. HYBRID 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 25

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.

9.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. 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).

26

fig 9.1

9.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.

fig 9.2 27

Figure 9.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 9.2, if B uses a bordercast, data will be sent to F, E and C (D and A will act as relays).

9.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.

9.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. 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 28

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

9.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.

9.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 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…

29

10. CONCLUSION We discovered during this report 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 30

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.

11. REFERENCES AND BIBLIOGRAPHY

[1] http://www.crhc.uiuc.edu/~nhv/ [2] http://www.adhoc.6ants.net/~paul/ [4] Computer Networks by Tanenbaum

31

32