Ad-Hoc Wireless Networks PDF

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

Wireless Mobile & Multimedia Networking 7COM1076 Ad-hoc Networks 2 Dr Tazeen Syed [email protected] Senior Lecturer School of Physics Engineering and Computer Science (SPECS)  7COM1076 –Wireless Mobile & Multimedia Networking Outline ❑ Table Driven Routing protocol ❑ DSDV ▪ Count to infinity Problem ▪ Basic operations ▪ Routing table Structure ▪ Sequence Number ▪ Route Advertisement ▪ Route Updating ❑ DSDV Routing Establishment ▪ Building routing tables ▪ Adding new node ❑ DSDV Route Maintenance ▪ Link Breakage ❑ Stability and Scalability  7COM1076 –Wireless Mobile & Multimedia Networking Table Driven/Proactive Routing protocols ❑ They are extension of wired network routing protocols. ❑ They maintain the global topology information in the form of tables in every node. ❑ These tables are updated frequently in order to maintain consistent and accurate network state information. ▪ Destination Sequenced Distance-Vector (DSDV) ▪ Wireless Routing protocol (WRP) ▪ Source-tree Adaptive Routing Protocol (STAR) ▪ Cluster-Head Gateway Switch Routing Protocol (CGSR)  7COM1076 –Wireless Mobile & Multimedia Networking Table Driven/Proactive Routing protocols  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Routing Protocol Destination Sequenced Distance-Vector Enhanced version of Bellman-Ford routing protocol ❑ Loop free ▪ Tag each routing table entry with a destination sequence number ❑ Faster convergence ▪ Make immediate route advertisement on significant changes in routing table but wait with advertising of unstable routes (damping fluctuations) ❑ Counter the count-to-infinity problem  7COM1076 –Wireless Mobile & Multimedia Networking Basic operation – DSDV ▪ Each node maintains routing information for all known destinations ▪ Routing information must be updated periodically (no sleeping nodes) ▪ Traffic overhead even if there is no change in network topology ▪ Maintains routes which are never used ▪ Tables are exchanged between neighbors at regular intervals to keep up-to-date view of the network topology ▪ Routes to ALL destinations are always readily available at every node. ▪ Table updates are initiated by a destination with a new sequence number always greater than the previous one.  7COM1076 –Wireless Mobile & Multimedia Networking Count-to-infinity problem  7COM1076 –Wireless Mobile & Multimedia Networking Routing Table Structure Routing table of A ▪ Dest: destination node ▪ NextNode: go to the destination through this node ▪ Dist: distance of going to the destination through the NextNode. ▪ SeqNo: sequence number originated from destination.  7COM1076 –Wireless Mobile & Multimedia Networking Use of Sequence Number ▪ Destination sequenced ▪ On each advertisement the sender increases its own destination sequence number (use only even numbers) ▪ If a node is no more reachable (timeout) increase sequence number of this node by 1 (odd sequence number) and set metric = ∞ ▪ Ensures a route is loop-free and fresh.  7COM1076 –Wireless Mobile & Multimedia Networking Route Advertisement ▪ Routing information in tables is transmitted by broadcast. ▪ Route advertisements are transmitted periodically or immediately when any significant topology change is available. ▪ Two types of advertisement ▪ Full dump: all information from the transmitting node ▪ Incremental dump: all information that has changed since the last full dump ▪ Full dump if incremental dump exceeds one NPDU (network protocol data unit)  7COM1076 –Wireless Mobile & Multimedia Networking Route Updating Rules ▪ The route entry with the higher sequence number is chosen; ▪ If the sequence numbers of two route entries are the same, the one with the smaller metric is chosen.  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Building Routing Tables (1) ▪ Initial states  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Building Routing Tables (2) ▪ B advertises a full dump. ▪ A receives the advertisement and updates its routing table. ▪ C receives the advertisement and updates its routing table.  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Building Routing Tables (3) ▪ A advertises a full dump ▪ C advertises a full dump ▪ B receives both advertisements and updates its routing table.  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Building Routing Tables (4) ▪ B advertises a full dump ▪ A receives the advertisement and updates its routing table ▪ C receives the advertisement and updates its routing table  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of New Node (1) ▪ New node D comes and broadcasts its existence. ▪ C receives D’s advertisement, updates its routing table  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of New Node (2) ▪ C broadcasts a full dump immediately  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of New Node (3) ▪ D creates the routing table based on C’s advertisement. ▪ B updates its routing table  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Link Breakage (1) Node D leaves, and node C detects the link breakage, and updates its routing table by setting the distance to D as infinity and increasing the sequence number to D by 1.  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Link Breakage (2) When node B’s full dump reaches node C, node C notes it is out-of-date, since node C has a higher sequence number for destination D in its routing table.  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Link Breakage (3) Node C broadcasts the link breakage to node B  7COM1076 –Wireless Mobile & Multimedia Networking DSDV Route Establishment & Maintenance ❑ Example of Link Breakage (4) Node B broadcasts the link breakage to node A  7COM1076 –Wireless Mobile & Multimedia Networking Stability and Scalability ▪ DSDV requires a full dump update periodically, so it is not efficient in route updating ▪ Whenever topology of a network changes, DSDV is unstable until update packets propagate through the network ▪ DSDV is effective for creating ad-hoc networks for small populations of mobile nodes ▪ DSDV is a fairly brute force approach, because connectivity information needs periodical update throughout the whole network  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.1, 7.2, 7.3, 7.4.1 ❑ RFC 2501. ▪ http://www.ietf.org/rfc/rfc2501.txt  7COM1076 –Wireless Mobile & Multimedia Networking Any Thank you Questions? [email protected]