1、Study of Distance Vector Routing Protocols for Mobile Ad Hoc Networks,Yi Lu, Weichao Wang, Bharat Bhargava CERIAS and Department of Computer Sciences Purdue University March 24th, 2003,*The research is supported by NSF, CERIAS, and CISCO,2,Index,Research motivation Our contribution Introduction to s
2、tudied protocols Simulation and analysis Our approach: Congestion aware distance vector (CADV) protocol Conclusion,3,Research motivation,The hybrid of Internet, cellular system and mobile ad hoc networks is emerging. It enables the pervasive computing at any where, any time. S. Bush, GE Research 99
3、The limited resources available to mobile nodes put challenges to the design of ad hoc routing protocols. Corson & Macker, IETF MANET WG 02 More than ten routing protocols have been proposed. A protocol tends to outperform others in some network environments. Jiang et al, ICCCN 01 Research is requir
4、ed to ascertain the reasons that lead to the difference in performance and guide the design of a more adaptable protocol.,4,Our contribution,The linear dependence between network topology changes and node mobility is investigated The suitable network environments for AODV and DSDV are identified The
5、 major cause for packet drop is studied A new protocol integrating congestion avoidance is proposed,5,Destination sequenced distance vector (DSDV) Proposed by Perkins in SigCOMM 94; The nodes periodically broadcast the routing tables and proactively construct the routes; Using destination sequence n
6、umbers to avoid routing loop and identify the freshness of the information; Advantages: Short delay brought by the proactive feature Difficult for the attackers to control the propagation of false information Disadvantages: Difficult to scale to large networks Computation and communication resources
7、 wasted on unused routes,Introduction to DSDV,6,Ad hoc on-demand distance vector (AODV) Proposed by Perkins and Royer Mobile Com and App 99; The routes are detected only when they are needed by the applications; Broadcast routing request (RREQ) and unicast routing reply (RREP) Using destination sequ
8、ence numbers to avoid routing loop and identify the freshness of the information; Advantages: Low overhead and smaller routing tables in light load networks Fast expiration of unused routes Disadvantages: On-demand feature brings a longer delay for the first packet Malicious nodes have more flexibil
9、ity on conducting attacks,Introduction to AODV,7,The frequency of link changes and route changes directly impact the overhead and adaptability of routing protocols; However, no network model is available to give out mathematical analysis; Our simulation will show that: Link changes and route changes
10、 fit into linear functions of the maximum moving speed of node when pause time is fixed; Link changes and route changes fit into linear functions of the node pause time when maximum moving speed is fixed Thus, topology changes can be measured by node mobility.,Correlation between link change and nod
11、e mobility,8,Correlation between link change and node mobility (cond),9,AODV and DSDV are studied by varying network environment parameters; Input parameters: Node mobility (maximum moving speed) Traffic load (number of connections) Network size (number of mobile nodes) Output parameters: Delivery r
12、atio Average packet delay Normalized protocol overhead Normalized power consumption,Simulation experiments,10,Simulation setup,11,Purpose: study the impact of mobility on the performance; Observation: Delivery ratio of DSDV drops faster as node mobility increases; The normalized overhead of AODV is
13、24 times more than DSDV when the network is loaded; The overhead of DSDV keeps stable as node mobility increases; The power consumption of both protocols is stable and close to each other;,Experiment 1: varying maximum speed,12,Simulation results of varying maximum speed,13,Purpose: examine the perf
14、ormance of both protocols under different loads; Observation: Delivery ratios of both protocols drop drastically as the network is fully loaded; The normalized overhead of AODV increases faster when the network is fully loaded; The power consumption of both protocols is stable and close to each othe
15、r;,Experiment 2: varying traffic load,14,Simulation results of varying traffic load,15,Purpose: investigate the reasons that cause packet loss, and guide the design of response; Observation: In both protocols, congestion is the primary reason for packet drop DSDV is easier to lead to congestion DSDV
16、 does not drop packets for “no route”; In DSDV, when links break, the intermediate nodes will buffer packets until new routes are available. This reduces packet drop.,Experiment 3: Reasons for packet drop,16,Simulation results of packet drop,17,Purpose: study the impact of node density on protocol p
17、erformance; Observation: When the number of connections 50, the delivery ratio of DSDV is better than AODV. The protocol overhead of AODV is larger than DSDV when the network is fully loaded.,Experiment 4: varying network size,18,Simulation results of varying network size,19,The proactive protocols
18、have advantages in supporting: Applications requiring QoS in ad hoc networks; Intrusion detection requiring distributed, global traffic monitoring; Design objective: Dynamically detect and avoid congestion and route packets through light-loaded paths; Improve network performance,Congestion Aware Dis
19、tance Vector (CADV),20,Congestion Aware Distance Vector (cond),Components: Real time traffic monitor Packet scheduler and traffic control Route maintenance module Route determination policy: Every node estimates the expected delay of sending a packet as:Apply a function f( E D , distance) to choose
20、route,21,Congestion Aware Distance Vector (cond),Performance of CADV: The delivery ratio of CADV outperforms AODV and DSDV The end-to-end delay becomes longer The protocol overhead is larger than DSDV. but because it is a pro-active protocol, the overhead does not increase as the traffic load increa
21、ses. The power consumption does not vary much,22,Preliminary results of CADV,23,The link changes and route changes are, with a high probability, linear functions of the maximum speed, and node pause time In less stressful environments, AODV outperforms DSDV for all metrics except protocol overhead.
22、DSDV performs better in denser networks with a heavier load On-demand protocols propagate the link changes faster, and reduce the packet drop caused by them Network congestion is the dominant reason for packet drop. The performance of the protocols can be improved by congestion avoidance,Observation
23、s & Conclusions,24,Develop a complete approach that considers more parameters such as available queue length and the delay on a path during the route determination Introduce the random feature into route determination to avoid traffic fluctuation Develop a fast response mechanism (local repair) in proactive protocols to reduce packet drop cause by route changes,Future work,
