25-04-2010, 12:59 PM
[attachment=3402]
¢ Ad Hoc Wireless Routing
¢ Different from routing in the wired world
¢ Desirable properties of a wireless routing protocol
“ Distributed operation
“ Loop freedom
“ Demand-based operation
“ Security
“ Sleep period operation
“ Unidirectional page link support
“ Corson M., Macker, J. Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations. IETF Internet Draft. http://ietfinternet-drafts/corson-draft-ietf-manet-issues-01.txt
¢ Overview of Ad hoc Routing Protocols
“ Globally precomputed, table based
¢ DSDV “ Destination-Sequenced Distance Vector
¢ WRP “ Wireless Routing Protocol
¢ GSR “ Global State Routing
¢ FSR “ Fisheye State Routing
¢ HSR “ Hierarchical State Routing
¢ ZHLS “ Zone-based Hierarchical Link State Routing Protocol
¢ CGSR “ Clusterhead Gateway Switch Routing Protocol
¢ Overview of Ad hoc Routing Protocols
¢ On-Demand, source initiated
“ AODV “ Ad Hoc On-demand Distance Vector Routing
“ DSR “ Dynamic Source Routing
“ TORA “ Temporally Ordered Routing Algorithm
“ CBRP “ Cluster Based Routing Protocols
“ ABR “ Associativity Based Routing
“ SSR “ Signal Stability Routing
¢ DSDV, DSR, AODV, TORA
¢ These four protocols were chosen for further study for several reasons:
“ Submitted to MANET for approval
“ Implemented in ns-2
“ Multiple performance studies have been done on these protocols
¢ Dynamic Destination-Sequenced Distance Vector (DSDV)
¢ C. Perkins and P. Bhagwat. Highly dynamic Destination-sequenced distance vector routing (DSDV) for mobile computers ACM SIGCOMM '94 p234-244, 1994.
¢ Each node knows the state and topology of the entire network
¢ Routes are chosen by a metric (least delay, best signal strength, etc..)
¢ Periodically and when triggered transmits the entire routing table to neighbors
“ Full dumps
“ Incremental dumps
¢ Avoids loops by using sequence numbers
¢ DSDV Recovery
¢ When a page link loss is detected at node N:
“ the metric of the route to the destination through the lost page link is advertised as infinity (the worst value), and
“ An incremental update is flooded to the neighbors
¢ DSDV Evaluation
¢ Loop avoidance
¢ Constant routing overhead versus mobility
“ Overhead increases as the number of nodes increases
¢ DSDV can no longer find a route reliably when there is high mobility (< 300s pause times)
¢ Ad Hoc On-Demand Distance Vector (AODV)2
¢ C. Perkins. Ad Hoc On-Demand Distance Vector (AODV) Routing IETF Internet Draft. http://ietfinternet-drafts/draft-ietf-manet-aodv-10.txt.
¢ Each node only keeps next-hop information
¢ Source broadcasts ROUTE REQUEST packets
“ Each node that sees the request and forwards it creates a reverse route to the source
“ If the node knows the route to the destination, it responds with a ROUTE REPLY
¢ All nodes along the reply route create a forward route to the destination
¢ AODV Recovery
¢ When a page link loss is detected at node N
“ any upstream nodes that have recently sent packets through this node are notified with an UNSOLICITED ROUTE REPLY with an infinite metric for that destination
¢ AODV Evaluation
¢ Routing overhead increases as mobility increases, but not as the number of nodes increases
¢ Sends many packets, but they are small
“ Costs to access the medium (RTS/CTS packets)
¢ Always delivers at least 95% of packets sent in all cases (Broch, et. al.)
¢ Temporally Ordered Routing Algorithm (TORA)
¢ V. D. Park and M.S. Corson. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proceedings of INFOCOMM ™97 April 1997. http://ics.uci.edu/atm/adhoc/paper-colle...ocom97.pdf.
¢ Discovers multiple routes to destination
¢ Separate logical copy of the algorithm for each destination exists on each node
¢ Creates a Directed Acyclic Graph with the destination as the head of the graph
¢ Requires IMEP (Internet MANET Encapsulation Protocol) “ guarantees reliable in-order delivery of routing messages
¢ TORA (cont)
¢ Each node keeps a reference value and a height for each destination
¢ QUERY packets are sent out until one reaches the destination or a node with a route to the destination
“ This node sends an update to its neighbors listing its height for that destination
¢ TORA Recovery
¢ The node, N which discovers the page link loss:
“ Does nothing because other routes still exist, or
“ If the lost page link is the last downstream page link of this node:
¢ changes its height to be the local maximum and
¢ transmits update packets to look for new routes
¢ TORA Evaluation
¢ Can contain routing loops for short periods of time
¢ High routing overhead
¢ Does not try to find the shortest path
¢ When there are large numbers of sources transmitting simultaneously, TORA cannot find paths
“ Congestion feedback loop
¢ When there is too much congestion, IMEP loses packets and tells TORA that the page link is down
¢ TORA sends out more UPDATE packets to reconfigure
¢ More congestion is created
¢ Dynamic Source Routing(DSR)
¢ David B. Johnson, Davis A. Maltz, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks October 1999. IETF Internet Draft. http://ietfinternet-drafts/draft-ietf-manet-dsr-10.txt.
¢ Routes are kept in each packet
“ Routes to that point in REQUEST packets
“ Full routes in data packets
¢ Routes are cached at each node to limit flooding of REQUEST packets
“ Any route that is seen through a node is cached
¢ Source sends out REQUEST packets
“ Any node which is the destination of a node which has a route to the destination replies with a route reply
“
¢ DSR Recovery
¢ A Route ERROR is sent to the Source
“ All nodes along the path remove that route
¢ Source uses a cached alternate route to destination or sends out request packets for a new route
¢ DSR Evaluation
¢ Always delivers at least 95% of all packets sent in all cases (Broch, et. al.)
¢ Routing packets are large because of the source routing
¢ Performance
¢ Broch, et al. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols MOBICOM ™98 p85-97, 1998.
¢ Measurements are from simulations with 50 nodes, pause times from 0s (constant motion) to 900s (no motion), transmission rates of 4 packets/s, and speed of nodes at 1m/s and 20 m/s
¢ Load was 10 sources transmitting simultaneously, 20 sources, and 30 sources
¢ Simulated in ns-2 on top of complete implementation of the 802.11 Medium Access Control (MAC) protocol Distributed Coordination Function (DCF)
¢ Performance
Convergence
¢ Convergence is the ability of the routing protocol to quickly stabilize the routes it knows
¢ DSR & AODV always deliver at least 95% of the packets sent in all cases
¢ TORA fails to converge at less than ~500s pause time for the 30 source experiments, but always converges for 10 and 20 sources.
“ Congestion feedback loop
¢ DSDV does not converge with a pause time less than ~300s when nodes are moving at 20 m/s
¢ Performance
Routing Overhead
¢ Broch, et al. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols MOBICOM '98 p85-97, 1998.
¢ NS-2, JavaSim Evaluations
¢ Looking for:
“ Basic network/TCP implementation
“ Ability to implement an application layer routing protocol (Gnutella)
¢ NS-2 is a popular network simulator
¢ JavaSim was recommended by a group doing similar research
¢ OMNet++ was pushed to the side because of the constant recompilation needed to run simulations
¢ NS-2 and JavaSim Similarities
¢ Event driven simulators
¢ tcl like interface
¢ Capable of network simulation
¢ Outputs to NAM and xgraph formats
“ Can also output to any format that's been programmed into it
¢ Bad documentation
“ JavaSim: no documentation other than javadoc
“ ns-2: documentation does not match code
¢ Differences
¢ ns-2 was designed as a network simulator
¢ Built in wireless medium support
¢ Uses octcl as an interface
¢ Does not handle application layer data well
¢ Designed as an all purpose simulator
¢ No known wireless support
¢ Uses jacl as an interface
¢ Full support for application layer data exchange
¢ NS-2
¢ octcl interface is easy to use and set up simulations
¢ Code is confusing written in both C++ and tcl, no standard for what should be written in each
¢ octcl must be installed as a separate program
¢ JavaSim
¢ Jacl interface is built-in to the simulator
¢ Jacl scripts are difficult to understand and not easy to set up simulations
¢ Can use actual Java applications as components
