Ad Hoc Networks Routing (1/2) Instructor: Carlos Pomalaza-Ráez Fall 2003 University of Oulu, Finland
Ad Hoc Networks Routing (1/2) Instructor: Carlos Pomalaza-Ráez Fall 2003 University of Oulu, Finland
Mobile Ad Hoc Networks (MANET)
Main Features
Dynamic topology, e.g. nodes can join or leave the network as well as they can change the range of their transmissions
Each node acts as independent router
Because of the wireless mode of communication:
Bandwidth-constrained and variable capacity links
Limited transmitter range
Energy-constrained
Limited physical security
MAC and network protocols are of a distributed nature
Complex routing protocols with large transmission overheads and large processing loads on each node A loose collection of mobile nodes that are capable of communicating with each other without the aid of any established infrastructure or centralized administration
Dynamic Topology
Node mobility in Ad Hoc networks has had a great effect in the designing of routing protocols Node mobility creates a dynamic topology, i.e., changes in the connectivity between the nodes as a direct function of the distance between each other, the characteristics of the area where they are deployed and,, of course, the power of their transmitters
Where We Find Ad Hoc Networks
Military operations
Rescue and recovery scenarios
Local Area
Office, building WLANs
Home networks
Robot networks
Sensor networks
Personal Area Networking
Interconnection of wireless devices
Games
Habitat monitoring
Micro climate
Wildlife
Routing Protocols
Desired Properties
Distributed
Consider both uni- and bi-directional links
Energy efficient
Secure Performance Metrics
Data throughput, i.e., how well does the network deliver packets from the source to destination
Delay, e.g., end-to-end delay of packet delivery
Overhead costs, i.e., average of control packets produced per node
Power consumption, i.e., average power used by each node
Proactive vs. Reactive
Proactive routing maintains routes to every other node in the network
Table driven
Regular routing updates impose large overhead
No latency in route discovery, i.e., data can be sent immediately
Most routing information might never be used
Suitable for high traffic networks
Bellman-Ford type algorithms Reactive routing maintains routes to only those nodes which are needed
Cost of finding routes is expensive since flooding is involved
Might be delay before transmitting data
Cache information from other nodes’ transmissions
May not be appropriate for real-time applications
Good for low/medium traffic networks
Proactive vs. Reactive
S D S D Route Updates Routes Data Flow Timer Based Proactive Route REQ Route REP Data Flow On Demand Reactive
Mobility (proactive vs. reactive)
S D S D Must wait for the updates to be transmitted, processed and new routing tables be built Timer Based Proactive A new route request is sent and a new route is found On Demand Reactive
Destination Sequenced Distance Vector DSDV
Traditional distance vector algorithms are based on the classical Bellman-Ford (DBF) algorithm. This algorithm has the drawback that routing loops can occur. To eliminate or minimize the formation of loops the nodes are required to often coordinate and communicate among themselves. The problem is composed if there are frequent topological changes. The Routing Information Protocol (RIP) is based on this type of algorithm. The application of RIP to Ad Hoc networks is limited since it was not designed for such environment. The objective of DSDV protocols is to preserve the simplicity of RIP and avoid the looping problem in a mobile wireless environment. Main features of DSDV are: Routing tables have entries for every network destination and the number of hops to each
Each route table entry is tagged with a sequence number originated by the destination
Nodes periodically communicate their routing table to their neighbors and when there is a significant new information available
Routing information is normally transmitting using a broadcasting or multicasting mode
DSDV
Within the headers of the packet, the transmitter route tables usually carry the node hardware address, the network address, and the route transmission sequence number. Receiving a transmission from a neighbor doesn’t indicate immediately the existence of a bi-directional link with that neighbor. A node does not allow routing through a neighbor until that neighbors shows that it also has the node as a neighbor. This means that DSDV algorithms use only bi-directional links.
An important parameter value is the time between broadcasting routing information packets. However when any new and substantial route information is received by a mobile node, the updated route information is transmitted as soon as possible. Route Tables Entry Structure
Destination’s address
Number of hops required to reach the destination
Sequence number of the information received regarding that destination, as originally stamped by the destination
DSDV-Topological Changes
Broken links are a normal occurrence in Ad Hoc networks. They are detected by the MAC layer or inferred if no transmissions are received from a neighbor for some time
A broken link is given a metric of ∞ and an updated sequence number
A broken link translates into a substantial route change and thus this new routing information is immediately broadcasted to all neighbors
To propagate new routing information, particularly the one generated by broken links, and to avoid large transmission overheads two types of routing packets are used:
Full dump – carries all the available information
Incremental – carries only information changed after the last dump
When a node receives a new routing packet the information is compared to the one already available at the node
Routes with a more recent sequence number are always used
Newly computed routes are scheduled for immediate advertisement
DSDV Operation - Example
A H G F E D C B T002_D S050_H 3 F H T002_D S128_G 2 F G T001_D S076_F 1 F F T002_D S392_E 2 F E T001_D S710_D 0 D D T001_D S564_C 2 B C T001_D S128_B 1 B B T001_D S406_A 2 B A Install Time Sequence No Metric Next Hop Destination Metric = Number of hops to reach destination
Sequence Number = The freshness of received route, used to avoid routing loops
Install Time = Indicates when a received route was installed, used for damping route fluctuations D’s Routing Table D’s Advertised Routing Table S050_H 3 H S128_G 2 G S076_F 1 F S392_E 2 E S564_C 2 C S128_B 1 B S406_A 2 A Sequence No Metric Destination
DSDV Operation – Example (A moves)
A H G F E D C B A When A moves and it is detected as routing neighbor by G and H it causes these nodes to advertise their updated routing information (incremental update)
Upon reception of this update F updates its own routing tables and broadcast the new information
D receives this update and carries out an update of its routing table
DSDV Operation – Example (A moves)
D’s Updated Routing Table T002_D S160_H 3 F H T002_D S238_G 2 F G T001_D S186_F 1 F F T002_D S502_E 2 F E T001_D S820_D 0 D D T001_D S674_C 2 B C T001_D S238_B 1 B B T810_D S516_A 3 F A Install Time Sequence No Metric Next Hop Destination D’s Updated Advertised Routing Table S160_H 3 H S238_G 2 G S186_F 1 F S502_E 2 E S674_C 2 C S238_B 1 B S516_A 3 A Sequence No Metric Destination
Reactive Protocols
Dynamic Source Routing (DSR) Ad-Hoc On Demand Distance Vector (AODV) Every packet carries the routing sequence
Intermediate nodes may learn routes on “heard” traffic (RREQ, RREP, DATA)
No periodic sending of routing packets
May piggyback route requests on route replies
Must use link layer feedback to find broken links
Uses “traditional” routing tables
Hello messages sent periodically to identify neighbors
Sequence numbers guarantees freshness
Route requests are sent in reverse direction, i.e. only uses bi-directional links
May use link layer feedback to find broken links
DSR – Overview
D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc Wireless Networks,” In Mobile Computing, edited by T. Imielinski and H. Korth, Chapter 5, pages 153-181, Kluwer Academic Publishers, 1996. To send a packet the sender constructs a source route in the packet’s header
The source route has the address of every host through which the packet should be forwarded to reach its destination
Each host in the ad hoc network maintains a route cache in which it stores source routes it has learned
Each entry in the route cache has an expiration period, after which it will be deleted
If the sender doesn’t have a route to a destination it then attempts to find out by using a routing discovery process
While waiting for the routing discovery to complete the sender continues sending and receiving packets with other hosts
Each host uses a route maintenance procedure to monitor the correct operation of a route
DSR – Route Discovery
A B G D E H node discards packets having been seen s D C F Source broadcasts a route packet with the address of the source and destination A neighbor that receives the request looks up its route cache to look for a route to destination. If not found it appends its address into the packet and re-broadcasts it A-B H A H A H A H A-D H A-C H
DSR – Route Discovery
A B G D E H s C F A-B-G H A-B-E H D A-B-E-F H node discards packets having been seen
DSR – Route Discovery
A B G D E H s C F reply packet follows the reverse path of the route request packet recorded in broadcast packet A-B-G-H D A-B-G-H A-B-G-H
Route Discovery: at source A
A need to send to G Lookup Cache for route A to G Route found? Start Route Discovery Protocol Route Discovery finished Packet in buffer? Send packet to next-hop done Buffer packet no Write route in packet header yes yes no Continue normal processing wait
Comments