routing prtocols of ad hoc networks

Routing Protocols in Ad Hoc network:

1 Routing Protocols in Ad Hoc network Prof. Kakatkar M. N. Electronics & Telecommunication Dept.

What is an Ad hoc Network:

2 What is an Ad hoc Network Collection of mobile wireless nodes forming a network without the aid of any infrastructure or centralized administration Nodes have limited transmission range Nodes act as a routers

Ad Hoc Network:

3 Ad Hoc Network Characteristics Dynamic topologies Limited channel bandwidth Energy-constrained operation Limited security peer-to-peer (all nodes are routers) multi-hop routing frequent connection / topology changes

Wireless Ad-hoc Sensor Networks :

4 Wireless Ad-hoc Sensor Networks A wireless ad hoc sensor network consists of a number of sensors spread across a geographical area. Each sensor has wireless communication capability and some level of intelligence for signal processing and networking of the data.

Applications of Ad Hoc:

5 Applications of Ad Hoc Earliest uses: military Disaster Recovery emergency rescue Smart office Battle field Data acquisition

Mobile Ad-hoc Design Issues and Constraints:

6 Mobile Ad-hoc Design Issues and Constraints They are Infrastructure-less Dynamically Changing Network Topologies Network Security Limited Link Bandwidth and Quality Quality of Service Energy Constrained Operation

Ad Hoc Networks and Their Protocols::

7 Ad Hoc Networks and Their Protocols:

Some Implementation Choices:

8 Some Implementation Choices Flat vs. hierarchical architecture Routing information update Mechanism Table-based, demand-driven, cluster based Use of temporal information for routing Utilization of specific resources Assumptions about rate of change of topology and/or quality of connections

Mobile Ad-hoc Networks (MANETs) Routing Protocols:

9 Mobile Ad-hoc Networks (MANETs) Routing Protocols Ad-hoc Mobile Routing Protocols Table Driven Protocols On Demand Protocols Hybrid Protocols DSDV, WRP, STAR ABR, DSR, AODV, TORA ZRP

Slide 10:

10 Table Driven Routing Protocol Send periodic updates of the routes. Each node uses routing information to store the location information of other nodes in the network and this information is then used to move data among different nodes in the network. Have lower latency since routes are maintained at all times

Slide 11:

11 On Demand Routing Protocols Establish routes only when required to route data packets. Route discovery process Have longer transmission delays.

Slide 12:

12 Hybrid Routing Protocols Combine Table Based Routing Protocols with On Demand Routing Protocols. They use distance-vectors to establish the optimum routes, and report routing only when there is a change in the topology of the network. Each node in the network has its own routing zone, Each node keeps a record of routing information for its own zone.

DSR Concepts:

13 DSR Concepts Source routing No need to maintain up-to-date info at intermediate nodes On-demand route discovery No need for periodic route advertisements

DSR Components:

14 DSR Components Route discovery The mechanism by which a sending node obtains a route to destination Route maintenance The mechanism by which a sending node detects that the network topology has changed and its route to destination is no longer valid

DSR:

15 DSR ( Dynamic Source Routing) Resides in kernel IP layer (based on IPv6 format) messages: Route Request, Route Reply, Route Error, ACK Send, Retransmit buffers passive ACK

DSR Route Discovery:

16 DSR Route Discovery Route discovery - basic idea Source broadcasts route-request to Destination Each node forwards request by adding own address and re-broadcasting Requests propagate outward until: Target is found, or A node that has a route to Destination is found

C Broadcasts Route Request to F:

17 C Broadcasts Route Request to F A Source C G H Destination F E D B Route Request

C Broadcasts Route Request to F:

18 C Broadcasts Route Request to F A Source C G H Destination F E D B Route Request

H Responds to Route Request:

19 H Responds to Route Request A Source C G H Destination F E D B G,H,F

C Transmits a Packet to F:

20 C Transmits a Packet to F A Source C G H Destination F E D B F H,F G,H,F

DSR Route Discovery:

21 DSR Route Discovery One-hop Route Request (ask immediate neighbors) if that fails, broadcast request to whole network Route Reply is sent by destination or node with path in cache

Route Maintenance :

22 Route Maintenance When routing node/routing node link changes, existing source routes no longer work routing nodes respond to source routes with a Route Error, triggering a new route discovery B H I J G F E D A C K Route Error

Ad-hoc On Demand Distance Vector (AODV) :

23 Ad-hoc On Demand Distance Vector (AODV) On demand protocol that uses sequence numbers (DSDV) to build loop free routes Key difference from DSR is that source route is no longer required Path discovery Reverse Path setup Forward path setup Local connectivity management

In-Depth: AODV:

24 In-Depth: AODV ( Ad-hoc On-demand Distance Vector routing) Purely on-demand (no routes determined until needed) each node contains routing table of next-hop information for how to get to every other node

AODV Path Discovery:

25 AODV Path Discovery Source node broadcasts a path discovery message continues until it reaches destination, or node with path in table sequence numbers discovery response sent back along reverse path

AODV:

26 AODV Based on standard Distance Vector Algorithm Nodes maintain route cache and uses destination sequence number for each route entry Does nothing when connection between end points is still valid Route Discovery Mechanism is initiated when a route to new destination is needed by broadcasting a Route Request Packet (RREQ). Route Error Packets (RERR) are used to erase broken links

AODV Path/Connection Maintenance:

27 AODV Path/Connection Maintenance Nodes ‘ping’ with hello messages to test links timeouts assumed to be broken links (only) recent active nodes notified of topology changes--propagated to neighbors

DSR vs. AODV:

28 DSR vs. AODV

Conclusion:

29 Conclusion Source routing is good for on demand routes instead of a prior distribution Route discovery protocol used to obtain routes on demand Caching used to minimize use of discovery Periodic messages avoided. But need to buffer packets. To decide between links.

References:

30 References Jiang Li, Charles Blake et.al,” Capacity of Ad-hoc Wireless Network ”, Proceedings of the 7th ACM International Conference on Mobile Computing and Networking, Rome, Italy, July 2001. A.Velayutham ,K.Sundaresan,R.Sivakumar, “ Non-Pipelined Relay Improves Throughput Performance of Wireless Ad-Hoc Networks ”, submitted for Infocom 2005 Seungjoon Lee, Suman Banerjee, Bobby Bhattacharjee, “ The Case for a Multihop Wireless Local Area Network” , IEEE Infocom, Hong Kong, March 2004 P.Gupta, P.R. Kumar, “ The capacity of Wireless networks” , IEEE Transactions on Information theory 46(2):388-404,March 2000 Thomas M.Cover , Joy a thomas, “ Elements of Information Theory” , Wiley 1991

Slide 31:

31 THANKS!