Determining the Optimal Configuration for the Zone Routing Protocol By M. R. Pearlman and Z. J. Haas
Presentation by Martti Huttunen
martti.huttunen@ee.oulu.fi
Determining the Optimal Configuration for the Zone Routing Protocol By M. R. Pearlman and Z. J. Haas
Presentation by Martti Huttunen
martti.huttunen@ee.oulu.fi
Introduction
Zone Routing Protocol
A hybrid proactive-reactive protocol
Single configuration parameter: Zone radius
The research problem
To find an optimal value for the zone radius
To use minimal control traffic
Parameters reflecting performance
Node velocity and density, network span and traffic
Classes of routing protocols
Proactive routing
Routing table is updated continuously
Pro: small (and stable) delay
Con: amount of control traffic
Reactive routing
Routes are traced as they are required
Pro: less route queries
Con: highly variable delays
Routing Protocols 1/2
Distributed Bellman-Ford
Problems: Slow convergence and amount of control traffic
Optimizations such as DSDV do not fully solve problems
Link-state protocols
OSPF: frequent changes in topology result in high control traffic
OLSR: uses multicasting (vs. point-to-point) to reduce control traffic
Global periodic topology updates are not well suited to larger or more dynamic networks
Routing Protocols 2/2
Wireless Routing Protocol
Each node constructs a minimum spanning tree using its neighbors’ spanning trees
Problem: All nodes must be able to store a full routing table and its construction is costly
Source-initiated protocols
TORA: also destination floods its information
Queries are very costly to the network
AODV: uses source routing to limit flooding
Full path transmission might result in large control packets
The Zone Routing Protocol
A hybrid proactive-reactive protocol
Proactive routing is used in the transmission range of the node
Reactive routing is performed only on selected nodes
Elimination of loops
The configuration is adaptive: traffic is analyzed and zone range modified accordingly
Intrazone Routing
Intrazone routing is proactive, termed IARP
IARP may utilize any proactive algorithm
In this paper, split-horizon version of the distance vector algorithm is used
To achieve functional coverage, a node should have sufficient amount of neighbors
Adjusting zone radius requires the capability of adjusting transmitter power
On the other hand, having a large routing zone might result in excessive control traffic
The amount of proactive control traffic depends only on zone membership vs. network size
Interzone Routing
Intrazone routing is reactive, termed IERP
Improves from flooding algorithms by utilizing the known zone topology
Increases probability of a node being able to provide a route
Helps in estimating propagation in (probable) cases where the destination is not in the current zone
Bordercasting is used
May be implemented via unicasting or selective multicasting
Problem: How to actually derive border information?
Interzone Routing Sequence
Is destination inside zone?
Yes -> Reply
Bordercast a routing request
Peripheral (border) nodes will continue sequence
Once the reply arrives, deliver it to the source
Each node appends its information to the request
Information is used to source-route the reply
A full path is provided
Routing information should be cached if possible
Multiple routes may be discovered
Example selection metrics: number of hops, delay
Interzone Routing Problems
Once the request leaves initial zone, the request may be reflected back
Results in very quick flooding of the network
Early termination process is required
Intermediate nodes must be able to receive bordercasted messages
Intermediate nodes will terminate queries they have already received
Nodes must be able to either eavesdrop routing requests or broadcasting must be applied
Evaluation Procedure
OPNET simulation - network parameters
Number of nodes N
Node density d (average nr. of neighbors/node)
Relative node velocity n (rate of new neighbor entry)
Measurements
Amount of control traffic vs. data
The optimal zone radius r (in hops)
IARP/node/s = n * IARP-update/neighbor (r , d)
BER is approximated to increase drastically at certain transmitter range
Evaluation Results – IARP traffic
Procedure consists of delivering topology changes
Simulation results show exponential growth r ^ n (roughly)
The n denotes number of neighbors
Evaluation Results – IERP traffic/query
Each node receives d packets per query
Data is effectively flooded over network
The early termination process limits traffic
Traffic decreases as a mostly linear function of r, as zones cover more nodes
Simulation shows that with networks d < 6, the average traffic decreases
This is because of network getting partitioned -> queries do not reach all nodes -> networks with d < 5 are ignored (!)
Also, when zones are dense, traffic increases
Detecting redundant queries becomes increasingly difficult
IERP/s = IERP-update/query/node (r , d) * N * (Rinitial + Rseq)
Rinitial = rate of new route queries, Rseq = Route update rate
Effects of node velocity?
Evaluation Results – total performance
As r increases, the rate of IERP queries decreases
Intrazone communication is more dominant
The node density curve is parabolic
As Rused >> Rfailure, the curve gets more steep and the minimum point more evident
The estimation of this information requires specific algorithms
2 options provided: min searching and traffic adapting
Traffic estimation: Min searching
r is adjusted periodically to find optimal value
Requires statistics of transmitted data and control information
These statistics are compared to the previous value
The comparison is used to determine if the direction of change was correct
A history of statistical values is kept per r value
Very sensitive to node velocity as converges slowly
Thresholds in traffic property changes trigger a new estimation
Traffic estimation: Traffic adaptive
r is adjusted according to the ratio of IARP/IERP traffic
As zones grow too large, IARP traffic becomes dominant
Does not require “triggering” as such, but is a continuous process
No extra traffic, analysis is based on required transactions
Oscillates on small r values
Simulation shows adaptive algorithm to be superior in terms of generated control traffic
Conclusions
The ZRP is a flexible and scalable solution
As IERP is triggered only on demand, the node velocity has little effect on control traffic and on the optimal zone radius
If traffic is periodic (vs. continuous), the performance is less affected by failed routes and node velocity
In these cases zone radius should be smaller
A less dense network with mobile nodes performs better with a larger zone radius
Achievements
Intra- and interzone routing is well applicable to heterogeneous networks
Natural selection of zones: different radio networks
Scales to very large networks
In WLAN-scale solutions is also sufficiently simple
Critique
Bordercasting is vital for IERP efficiency
Performance in less dense networks is questionable
Actual determination of IARP zone depends on the properties of the radio network used
Some IERP queries might be necessary to achieve full intrazone topology
Unicasted bordercasting is not very effective -> multi- or broadcasting should be available
Not very suitable for smallest devices
Various statistics and tables required
Comments