adhoc_routing_protocolsV1.pdf

Mobile Ad-Hoc Networks MANET  Ad Hoc Networks Wireless networks can be divided in two fundamental categories:  Infrastructure-based Wireless clients connecting to a base-station (APs, Cell Towers) that provides all the traditional network services (routing, address assignment...

Mobile Ad-Hoc Networks MANET  Ad Hoc Networks Wireless networks can be divided in two fundamental categories:  Infrastructure-based Wireless clients connecting to a base-station (APs, Cell Towers) that provides all the traditional network services (routing, address assignment)  Infrastructure-less The clients themselves must provide all the traditional services to each other  Ad Hoc Networks An infrastructure wireless network An Ad-hoc network  Ad Hoc Networks Ad-hoc networks main features:  Decentralized  Do not rely on preexisting infrastructure  Each node participates in routing by forwarding data to neighbor nodes  Fast network topology changes due to nodes’ movement  Ad Hoc Networks Why do we need ad-hoc networks?  More laptop users  More smartphones users (e.g.. Android phones, iPhones)  More devices with Wi-Fi-support (e.g.. televisions, hi- fi, home-theaters, media servers etc.)  Moving users, vehicles, etc.  Outdoors places  In all these occasions there is no centralized infrastructure (such APs)  So ad-hoc network is a necessity  What’s unique about a MANET ? Moving nodes  ever changing topology Wireless links  various and volatile link quality Pervasive (cheap) devices  Power constraints Security – Confidentiality, other attacks  Challenges in MANET Routing Need dynamic routing – Frequent topological changes possible. – Very different from dynamic routing in the Internet. – Potential of network partitions. Routing overhead must be kept minimal – Wireless  low bandwidth – Mobile  low power – Minimize # of routing control messages – Minimize routing state at each node  Other Challenges Auto configuration issues – Address assignment – Service discovery Security issues – Ease of denial-of-service attack – Misbehaving nodes difficult to identify – Nodes can be easily compromised New Applications/services – Location based: Distribute some information to all nodes in a geographic area (geocast). – Content based: Query all sensors that sensed something particular in the past hour.  Ad-hoc routing algorithms Discuss and comparison 1. Ad-Hoc on-demand Distance Vector Routing (AODV) 2. Dynamic Source Routing (DSR)  Ad-hoc routing algorithms Hottest routing algorithm categories:  Pro-active (table-driven) routing This type of protocols maintains fresh lists of destinations & their routes by periodically distributing routing tables throughout the network. Disadvantages: 1. Respective amount of data for maintenance 2. Slow reaction on restructuring and failures (e.g. OSLR Optimized Link State Routing Protocol, DSDV Destination-Sequenced Distance Vector Routing )  Reactive (on-demand) routing On demand route discovery by flooding the network with Route Request packets Disadvantages: 1. High latency time in route finding 2. Flooding can lead to network clogging (e.g. AODV, DSR)  Outline  Ad-Hoc on-demand Distance Vector Routing (AODV)  General info  Path Discovery  Path Maintenance  Local Connectivity Maintenance  Conclusion  Dynamic Source Routing (DSR)  Comparison of AODV and DSR  (AODV) General info  Reactive algorithms like AODV create routes on- demand. They must however, reduce as much as possible the acquisition time  We could largely eliminate the need of periodically system-wide broadcasts  AODV uses symmetric links between neighboring nodes. It does not attempt to follow paths between nodes when one of the nodes can not hear the other one  (AODV) General info  Nodes that have not participate yet in any packet exchange (inactive nodes), they do not maintain routing information  They do not participate in any periodic routing table exchanges  (AODV) General info  Each node can become aware of other nodes in its neighbourhood by using local broadcasts known as hello messages  neighbour routing tables are organized to : 1. optimize response time to local movements 2. provide quick response time for new routes requests  (AODV) General info AODV main features:  Broadcast route discovery mechanism  Bandwidth efficiently (small header information)  Responsive to changes in network topology  Loop free routing  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  General info  Path Discovery  Path Maintenance  Local Connectivity Maintenance  Conclusion  Dynamic Source Routing (DSR)  Comparison of AODV and DSR  (AODV) Path Discovery  Initiated when a source node needs to communicate with another node for which it has no routing info  Every node maintains two counters:  node_sequence_number  broadcast_id  The source node broadcast to the neighbors a route request packet (called RREQ)  (AODV) Path Discovery  RREQ structure  src_addr and broadcast_id uniquely identifies a RREQ  broadcast_id is incremented whenever source node issues a RREQ  Each neighbor either satisfy the RREQ, by sending back a routing reply (RREP), or rebroadcast the RREQ to its own neighbors after increasing the hop_count by one.  (AODV) Path Discovery  If a node receives a RREQ that has the same with a previous RREQ it drops it immediately  If a node cannot satisfy the RREQ, stores:  Destination IP  Source IP  broadcast_id  Expiration time (used for reverse path process)  src_sequence_#  (AODV) Path Discovery 1. Reverse Path Setup  In each RREQ there are:  src_sequence_#  the last dest_sequence_#  src_sequence_# used to maintain freshness information about the reverse route to the source  dest_sequnece_# indicates how fresh a route must be, before it can be accepted by the source  (AODV) Path Discovery 1.Reverse Path Setup (continue)  As RREQ travels from source to many destinations, it automatically sets up the reverse path, from all nodes back to the source. But how does it work?  Each node records the address of the neighbor from which it received the first copy of the RREQ  These entries are maintained for at least enough time, for the RREQ to traverse the network and produce a reply  (AODV) Path Discovery 1.Reverse Path Setup (continue) RREQ reached destination Reversed path is fully set up From which RREP can travel S Source node back to S D Destination node D W Z Neighbor nodes Z V W, Y can not satisfy RREQ i.Z, V,Set U can not satisfy up reverse pathRREQ W ii. i.Rebroadcast Set up reverse RREQpath to Y ii. Rebroadcast neighbors RREQ to neighbors U S sends RREQ S Figure 1  (AODV) Path Discovery 2. Forward Path Setup  A node receiving a RREP propagates the first RREP for a given source towards the source (using the reverse path that has already established)  Nodes that are not in the path determined by the RREP will time out after 3000 ms and will delete the reverse pointers  (AODV) Path Discovery 2. Forward Path Setup (continue) S Source node D replies with a D Destination node RREP to Z D Z W Z has a reversed path to W Z receives RREP and set up a Z W Z W has a forward path to Z forward pointer V The same for the W Time out other Y nodes U S Figure 2  (AODV) Path Discovery 2. Forward Path Setup (Conclusion)  Minimum number of RREPs towards source  The source can begin data transmission as soon as the first RREP received and update later its routing information if it learns of a better route  Route Requests in AODV Consider the following network and show how the AODV protocol would operate and shall find a new path from the source node S to destination node D. Draw diagrams to show the operations of the AODV protocol and clearly indicate the Y flow of different kinds of data transmission in establishing the path. Z S E F B C M L J A G H D K I N Represents a node that has received RREQ for D from S  Route Requests in AODV Y Broadcast transmission Z S E F B C M L J A G H D K I N Represents transmission of RREQ  Route Requests in AODV Y Z S E F B C M L J A G H D K I N Represents links on Reverse Path  Reverse Path Setup in AODV Y Z S E F B C M L J A G H D K I N Node C receives RREQ from G and H, but does not forward it again, because node C has already forwarded RREQ once  Reverse Path Setup in AODV Y Z S E F B C M L J A G H D K I N  Reverse Path Setup in AODV Y Z S E F B C M L J A G H D K I N Node D does not forward RREQ, because node D is the intended target of the RREQ  Route Reply in AODV Y Z S E F B C M L J A G H D K I N Represents links on path taken by RREP  Forward Path Setup in AODV Y Z S E F B C M L J A G H D K I N Forward “next-hops” are setup when RREP travels along the reverse path – there is no actual path stored Represents a next-hop entry on the forward path to D  Data Delivery in AODV Y DATA Z S E F B C M L J A G H D K I N Routing table entries used to forward data packet. Route is not included in packet header.  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  General info  Path Discovery  Path Maintenance  Local Connectivity Maintenance  Conclusion  Dynamic Source Routing (DSR)  Comparison of AODV and DSR  (AODV) Path Maintenance  Movement of nodes not lying along an active path does NOT affect the route to that path's destination  If the source node moves, it can simply re-initiate the route discovery procedure  If the destination or some intermediate node moves, a special RREP is sent to the affected nodes  To find out nodes movements periodic hello messages can be used, or (LLACKS) link-layer acknowledgments.  (AODV) Path Maintenance  When a node is unreachable the special RREP that is sent back towards the source, contains a new sequence number and hop count of ∞ D Link between Z and D fails Z sends a special RREP Z V So do W W Y U Figure 3 S So now source must find a new path. To do that, it sents a RREQ with a new greater sequence number  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  General info  Path Discovery  Path Maintenance  Local Connectivity Maintenance  Conclusion  Dynamic Source Routing (DSR)  Comparison of AODV and DSR  (AODV) Local Connectivity Maintenance  Nodes learn of their neighbors in one or two ways: 1. Whenever a node receives a broadcast from a neighbour it update its local connectivity information about this neighbour 2. If a neighbour has not sent any packets within hello_interval it broadcasts a hello message, containing its identity and its sequence number  (AODV) Local Connectivity Maintenance How hello messages work:  Neighbors that receive the hello message update their local connectivity information to the node that have broadcasted the hello message  Receiving a hello from a new neighbor, or failing to receive allowed_hello_loss (typically 2) consecutive hello messages from a node previously in the neighborhood, indicates that the local connectivity has changed  (AODV) Conclusion AODV main features:  Nodes store only the routes they need  Need for broadcast is minimized  Reduces memory requirements and needless duplications  Quick response to link breakage in active routes  Loop-free routes maintained by use of destination sequence numbers  Scalable to large populations of nodes  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  Dynamic Source Routing (DSR)  General  Basic Route Discovery  Basic Route Maintenance  Conclusion  Comparison of AODV and DSR  (DSR) General Two main mechanisms that work together to allow the discovery and maintainance of source routes:  Route discovery  Route maintainance  (DSR) General Route discovery:  Is the mechanism by which a source node S, obtains a route to a destination D  Used only when S attempt to send a packet to D and does not already know a route to D  (DSR) General Route maintainance:  Is the mechanism by which source node S is able to detect if the network topology has changed and can no longer use its route to D  If S knows another route to D, use it  Else invoke route discovery process again to find a new route  Used only when S wants to send a packet to D  (DSR) General  Each mechanism operate entirely on demand  DSR requires no periodic packets of any kind at any level  Uni-directional and asymmetric routes support (e.g. send a packet to a node D through a route and receive a packet D from another route)  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  Dynamic Source Routing (DSR)  General  Basic Route Discovery  Basic Route Maintenance  Conclusion  Comparison of AODV and DSR  (DSR) Basic Route Discovery When S wants to sent a packet to D:  it places in the header of the packet a source route giving the sequence of hops that the packet should follow on its way to D  S obtains a suitable source route by searching its route table  If no route found for D, S initiate the Route Discovery protocol to dynamically find a new route to D  (DSR) Basic Route Discovery Sender  Broadcasts a Route Request Packet (RREQ)  RREQ contains a unique Request ID and the address of the sender Receiver  If this node is the destination node, or has route to the destination send a Route Reply packet (RREP)  Else if is the source, drop the packet  Else if is already in the RREQ's route table, drop the packet  Else append the node address in the RREQ's route table and broadcast the updated RREQ  (DSR) Basic Route Discovery Id=2, {S, W, Z} D S Source node D Destination node Z Id=2, {S, Y} W Z Neighbor nodes Id=2, {S, W} V RREQ packet W Y Id=2, {S} U S Id=2, {S, Y} Id=2, {S} S sends RREQ  (DSR) Basic Route Discovery When a RREQ reaches the destination node, a RREP must be sent back to source The destination node:  Examine its own Route Cache for a route back to source  If found, it use this route to send back the RREP  Else, the destination node starts a new Route Discovery process to find a route towards source node  In protocols that require bi-directional links like 802.11, the reversed route list of the RREQ packet can be used, in order to avoid the second Route Discovery  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  Dynamic Source Routing (DSR)  General  Basic Route Discovery  Basic Route Maintenance  Conclusion  Comparison of AODV and DSR  (DSR) Basic Route Maintenance Each node transmitting a packet:  is responsible for confirming that the packet has been received by the next hop along the source route  The confirmation it is done with a standard part of MAC layer (e.g. Link-level ACKs in 802.11)  If none exists, a DSR-specific software takes the responsibility to sent back an ACK  When retransmissions of a packet in a node reach a maximum number, a Route Error Packet (RERR) is sent from the node back to the source, identifying the broken link  (DSR) Basic Route Maintenance The source:  Removes from the routing table the broken route  Retransmission of the original packet is a function of upper layers (e.g. TCP)  It searches the routing table for another route, or start a new Route Discovery process  (DSR) Basic Route Maintenance S Source node Link fails D Destination node D W Z Neighbor nodes Intermediate node sentsD)a Z RERR packet RERR(Z, RERR V W RERR(Z, D) Y U Route Table D: S, W, Z, D S Figure 5 V: S, Y, V  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  Dynamic Source Routing (DSR)  General  Basic Route Discovery  Basic Route Maintenance  Conclusion  Comparison of AODV and DSR  (DSR) Conclusion  Excellent performance for routing in multi-hop wireless ad hoc networks  Very low routing overhead even with continuous rapid motion, which scales to : 1. zero when nodes are stationary 2. the affected routes when nodes are moving  Completely self-organized & self-configuring network  Entirely on-demand operation. No periodic activity of any kind at any level  Outline  Ad-Hoc networks  Ad-hoc routing algorithms  Ad-Hoc on-demand Distance Vector Routing (AODV)  Dynamic Source Routing (DSR)  Comparison of AODV and DSR  Comparison of AODV and DSR Main common features:  On-demand route requesting  Route discovery based on requesting and replying control packets  Broadcast route discovery mechanism  Comparison of AODV and DSR Main common features: (continue)  Route information is stored in all intermediate nodes along the established path  Inform source node for a broken links  Loop-free routing  Comparison of AODV and DSR Main differences:  DSR can handle uni and bi-directional links, AODV uses only bi-directional  In DSR, using a single RREQ - RREP cycle, source and intermediate nodes can learn routes to other nodes on the route  DSR maintains many alternate routes to the destination, instead of AODV that maintains at most one entry per destination  Comparison of AODV and DSR Main differences: (continue)  DSR doesn’t contain any explicit mechanism to expire stale routes in the cache , In AODV if a routing table entry is not recently used , the entry is expired  DSR can’t prefer “fresher” routes when faced multiple choices for routes. In contrast, AODV always choose the fresher route (based on destination sequence numbers)  Comparison of AODV and DSR Main differences: (continue)  DSR’s RREQ has variable length depending on the nodes that the packet has traveled. AODV’s RREQ size is constant  As a result DSR’s header overhead may increase as more nodes become active, so we expect that AODV throughput in those scenarios to be better  Comparison of AODV and DSR Test bench set up:  100 nodes, some of them as sources  Nominal bit rate of 2 Mb/s  Nominal node range of 250 m  Continuously moving nodes Comparison of AODV and DSR  Comparison of AODV and DSR Performance DSR AODV metrics Packets delivered 56.88 83.66 /Packets sent (%) Average delay (s) 1.36 0.26 Routing Packets DSR AODV Route requests 37774 228094 Route replies 82710 17753 Route errors 26591 9808 Total 147075 255655 Application and routing statistics for an example scenario for a network of 100 nodes with continuous mobility and 40 sources  Conclusion  DSR outperforms AODV in less stressful situations (i.e., smaller number of nodes and lower load and/or mobility)  AODV outperforms DSR in more stressful situations (e.g., more load, higher mobility)  DSR commonly generates less routing load than AODV  Poor delay and throughput of DSR due to lack of any mechanism to expire stale routes or determine the freshness of routes