Ad-Hoc Networks 3 PDF

Wireless Mobile & Multimedia Networking 7COM1076 Ad-hoc Networks 3 Dr Tazeen Syed [email protected] School of Physics Engineering and Computer Science (SPECS)...

Wireless Mobile & Multimedia Networking 7COM1076 Ad-hoc Networks 3 Dr Tazeen Syed [email protected] School of Physics Engineering and Computer Science (SPECS) 1  7COM1076 –Wireless Mobile & Multimedia Networking Outline ❑ Reactive Routing protocol ❑ Dynamic Source Routing (DSR) DSR Features Basic operations ▪ Route Discovery ▪ Route Cache ▪ Route Maintenance ❑ DSR Routing Establishment ❑ DSR Reply ❑ DSR Route Maintenance ❑ Advantages & Disadvantages ❑ Further Improvement 2  7COM1076 –Wireless Mobile & Multimedia Networking Reactive Routing protocols ▪ On-demand routing protocols also known as on-demand routing protocols. ▪ Execute the path-finding process and exchange routing information only when a path is required by a node to communicate with the destination. ▪ No periodic routing updates or routing information exchange. ▪ Some of the existing on-demand routing protocols are as follows: Dynamic Source Routing Protocol (DSR) Ad hoc On-demand Distance-Vector Routing Protocol (AODV) Temporally Ordered Routing Algorithm (TORA) Location-Aided Routing (LAR) Signal Stability-Based Adaptive Routing protocol (SSA) 3  7COM1076 –Wireless Mobile & Multimedia Networking Dynamic Source (DSR) Routing Protocol Features ▪ On-demand routing protocol. ▪ Designed to restrict the bandwidth consumed by control packets by eliminating periodic routing updates that which is required in the table-driven approaches. ▪ Operation is based on Source Routing ▪ Route discovery is initiated by the source node. ▪ Sender knows the complete path to the destination ▪ Intermediatory nodes are not required to know the entire routing path ▪ Less network overhead as the number of message exchange between nodes is low. 4  7COM1076 –Wireless Mobile & Multimedia Networking Basic Operations – DSR The basic operations of DSR include ▪ Route Discovery ▪ Route Cache ▪ Route Maintenance 5  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSR (cont.) Route Discovery When a node (source) intends to send data to another node (destination node) in the network it enters the route discovery phase 1. Source node: ▪ Source node has no route information at the initial stage ▪ Initializes and sends RouteRequest (RREQ) packets to the network. 2. Intermediate nodes: ▪ Forward RouteRequest to the network by flooding. ▪ Upon receiving this packet, the intermediate nodes rebroadcasts to neighbouring nodes only: If is not forwarded already If it is not the destination node provided the time to live not exceeded ▪ Use a source-sequenced number in RouteRequest to prevent loop formation and to avoid redundant forwarding. 6  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSR (cont.) Route Discovery 3. Destination node: ▪ Replies RouteReply (RREP)to the source node through the reverse path the RouteRequest packet had traversed. Route Request (RREQ) packet: ▪ A broadcast packet which is flooded throughout the network ▪ It consists of fields such as unique ID field/sequence number which is generated by the source node ▪ It has the source address and the destination address Route Reply (RREP) packet: ▪ This is a unicast packet send by destination node with complete path to the source node ▪ It carries the route traversed by the route request packet. 7  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSR (cont.) Node 1 is the source and node 15 is the destination node. Path 1 : 1-2-3-7-9-13-15 Path 2 : 1-5-4-12-15 Path 3 : 1-6-10-11-14-15 8  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSR (cont.) Route Caches ▪ Each node maintains a route cache that stores routes for destination nodes. ▪ Route cache is used during the route construction phase. ▪ Intermediate nodes can reply to the source node by sending a RouteReply (RREP) with the information in its route cache. Why is route cache used? Good or bad? 9  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSR (cont.) Route Caches Caching routes can affect network performance, particularly in dynamic, large and highly mobile environments: ▪ stale routes ▪ increased route errors ▪ cache overflow ▪ potential security vulnerabilities 10  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSR (cont.) Route maintenance ▪ When a wireless link is broken, a RouteError (RERR) message is generated from the node adjacent to the broken link to inform the source node. ▪ The source node reinitializes the route discovery procedure. ▪ The intermediate nodes and the source node remove the cashed entries when receiving the RouteError message. 11  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Discovery Example - Route Discovery (1) ▪ Node 1 wants to send data to node 12. 12  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Discovery (cont.) Example - Route Discovery (2) ▪ Node 1 which is the source node floods RouteRequest (RREQ) message Seq No. Source Dest 5 1 12 RREQ Packet from node 1 13  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Discovery (cont.) Example - Route Discovery (3) ▪ After intermediate nodes 2, 6 & 7 flood RouteRequest message Seq Source Path Dest No. 5 1 7 12 RREQ Packet from node 7 14  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Discovery (cont.) Example - Route Discovery (4) ▪ After intermediate nodes 3, 4, 8 & 9 flood RouteRequest message Seq Source Path Dest No. 5 1 7 9 12 RREQ Packet from node 9 15  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Discovery (cont.) Example - Route Discovery (5) ▪ After intermediate nodes 10 & 11 flood RouteRequest message Seq Dest Source Path No. 5 1 7 9 10 12 RREQ Packet from node 10 16  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Discovery (cont.) Example - Route Discovery (6) ▪ Destination node 12 sends back RouteReply message 17  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Established – Route Reply Route Reply ▪ Destination node on receiving the first RouteRequest , sends a RouteReply (RREP) ▪ RouteReply includes the route from the source to the destination on which RouteRequest was received by the destination ▪ Route Reply is sent by reversing the route in RouteRequest ▪ This requires bi-directional link ▪ If unidirectional (asymmetric) links are allowed, then RouteReply may need a route discovery for the source node from the destination node ▪ Piggyback RouteRequest on RouteReply to the source ▪ The destination node includes its RREQ inside the RREP packet sent to the source. This simultaneously serves as an RREQ from the destination to the source ▪ This improves efficiency by reducing the need for separate RREQ messages and facilitating quicker bidirectional route setup. ▪ Disadvantage is increased packet sizes and can affect network stability. 18  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Establishment – Route Cache Example - Route Cache (1) ▪ Node 14 wants to send data to node 12 and floods RouteRequest message 19  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Establishment – Route Cache (cont.) Example - Route Cache (2) ▪ Node 14 wants to send data to node 12 and floods RouteRequest message 20  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Maintenance Example - Route Maintenance (1) ▪ The link between node 8 & 11 is broken. 21  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Maintenance (cont.) Example - Route Maintenance (2) ▪ Node 8 sends back RouteError message to source node 1. 22  7COM1076 –Wireless Mobile & Multimedia Networking DSR Route Maintenance (cont.) Example - Route Maintenance (3) ▪ Node 1 re-discovers a route to destination node 12. 23  7COM1076 –Wireless Mobile & Multimedia Networking DSR Advantages & Disadvantages Advantages ▪ No need of periodical exchange of routing table. ▪ No need to find routes to all other nodes. Only need to find a route to the destination. ▪ Route cache helps reduce the control overhead and route setting up time Disadvantages ▪ Route maintenance does not locally repair a broken link. ▪ Route cache may be staled. ▪ High route setup delay. ▪ Routing overhead proportional to the path length. ▪ Packet header size grows with path length. 24  7COM1076 –Wireless Mobile & Multimedia Networking ▪ As the network size increases the route Path path also increases. Path Path ▪ Increase in data Data Data Data packet’s header. Network size ▪ Inefficient usage of network bandwidth 25  7COM1076 –Wireless Mobile & Multimedia Networking Further Improvements Care must be taken to avoid collisions between route requests and route reply propagated by neighbouring nodes. Increased contention if too many route replies come back due to nodes replying using their local cache. ▪ Route Reply Storm problem ▪ Reply storm may be eased by preventing a node from sending RREP if it hears another RREP with a shorter route ▪ Route reply storms also prevented by randomising delay time before sending route replies 26  7COM1076 –Wireless Mobile & Multimedia Networking References ❑ Ad Hoc Wireless Networks, architectures and protocols. C. Siva Ram Murthy and B. S. Manoj, 1st edition. ▪ Sections 7.5.1 27  7COM1076 –Wireless Mobile & Multimedia Networking Any Thank you Questions? [email protected] 28