Performance Improvement Of Zrp Using Caching Technique Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Route caching scheme can significantly change network performance of zone routing protocols in mobile ad hoc networks (MANETs). The caching of previously discovers route is needed to avoid the rediscovery of routes for sending each packet. The link breakage is detected when an attempted data transmission fails, loss of a route will go undetected if there is no attempt to use this route. The timer based approach is based on the hypothesis that routes are only valid for specific amount of time (timeout period) from their last use. Each node in a cached route has an associated timestamp of last use. The timer based caching eliminate stale routes so that route cache is faster and thus applying this technique in Zone Routing Protocol (ZRP) improve the performance of ZRP protocol .In this paper ,we proposed a timer based caching scheme for zone routing protocol. Zone routing protocol combines the proactive protocol which pro-actively updates network state and maintains route regardless of whether any data traffic exists or not .Reactive protocol which only determines route to a destination if there is some data to be sent to the destination.


Routing Protocols, ZRP, IARP, IERP, NDP, Caching, Ad-hoc Networks

1. Introduction

Routing in Ad hoc network is different than wired network due to the property of wireless and mobility of nodes. There are many routing protocols are proposed. These protocol are broadly divided in to three category namely On-Demand, Table-Driven, Hybrid routing protocols. Table Driven routing protocol maintain table about information of nodes in network. In order to cop inconsistency of information they exchange information periodically. On Demand routing protocol is not maintained any table about nodes in network. Whenever a source need route information to destination they perform search and discover route to destination. On Demand routing protocol is not exchange any type of information between each other. Hybrid routing protocol is behaving like Table Driven up to some extend and after this limit they are behaving like On Demand routing protocol. This paper suggests the Timer- Based Route Cache technique to improve the performance of ZRP protocol. The structure of the paper is as follows: Section 2 gives a brief review of Zone Routing Protocol, Section 3 discusses the route cache & cache time out techniques Section 4 presents data structure & the path creation algorithm, Section 5 presents the Methodology used and section 6 concludes this work.

2. Zone Routing Protocol

ZRP is a hybrid routing protocol which combine the advantages of both the proactive and reactive approaches. ZRP divides its network into different zones. Each node has its own zone with coverage of all nodes within the range of r-hops which is referred as the zone radius. Each node may be within multiple overlapping zones, and each zone may be of a different size. A node is said to be central node if it is at a radius of r-hops from the neighboring nodes within the routing zone. The other nodes are divided into peripheral nodes and interior nodes. Peripheral nodes are nodes whose minimum distance to the central node is exactly equal to the zone radius. The nodes whose minimum distance is less than zone radius are interior nodes. ZRP works in three sub-protocols, namely, IntrA-zone Routing Protocol(IARP), IntEr-zone Routing Protocol(IERP), and Bordercasting Routing Protocol(BRP). Within a routing zone, ZRP uses proactive discovery by IARP. IERP is used as reactive protocol for communication between these zones. The path is calculated on demand using a form of selective flooding that exploits the underlying zone structure generated by the IARP. Specifically, flooding is based on sending query packets only to the peripheral nodes using a special kind of multicast transmission called bordercast. Route maintenance is responsible for maintaining interzone paths. The BRP is responsible for the forwarding of a route request. Before constructing a zone and determine border nodes, a node needs to know about its local neighbors. A node may use the media access control (MAC) protocols to learn about its direct neighbors. It also may require a Neighbor Discovery Protocol (NDP).

3. Route Caching

3.1.Causes of stale caching

we identify three main trouble spots that are the root cause of the stale cache problem. 1) Incomplete error notification: When a link breaks, route errors are not propagated to all caches that has an entry with the broken link. Instead, the route error is unicast only to the source whose data packet is responsible for identifying the link breakage via a link layer feedback. Thus only a limited number of caches are cleaned. The failure information is, however, propagated by piggybacking it onto the subsequent route requests from the source. But as the route requests may not be propagated network-wide (because of replies from caches), many caches may remain unclean. 2) No expiry: There is no mechanism to expire stale routes. If not cleaned explicitly by the error mechanism, stale cache entries will stay forever in the cache. 3) Quick pollution: There is no way to determine the freshness of any route information. For example, even after a stale cache entry is erased by a route error, a subsequent "in-flight" data packet carrying the same stale route can put that entry right back in. This possibility increases at high data rates, as there will be a large number of "in-flight" data packets upstream carrying the stale route to "un-erase" the route. This problem is compounded by liberal use of snooping. Stale routes are picked up by any other node overhearing any transmission. Thus, cache "pollution" can propagate fairly quickly.

3.2 Cache Timeout

As nodes are coming near and go away from each other connection between them is change dynamically. Cache has information about current topology of network. Topology of network is change due to the interference or mobility. It may be possible that a node may have link in his cache is not exist This stale information in cache can create many attempted to send packet, an Route Error Message and possible Route Discovery which is lead to overhead of network. But if packet is not going through link between nodes, we can't determine state of link. So we need some additional mechanism in cache for deleting old entries. We use time out where each entry are deleted after a specific time. Choosing this time out value is also a critical issue. If we choose smaller value for time our means after this time link is present then but source start an unnecessary Route Request and over head of network is increase. On other hand if we choose time out value large then link or path is broken before time out and information inside cache is stale and condition is worst. There are two methods are suggested for associating a time out with each entry of cache.

3.2.1 Static Timeout

Whenever a entry (link or path) is added in cache a predefine time T1 is attached with this entry. When ever a reply come through this link or path a specific time T2 is added in remaining time.

3.2.2 Adaptive Timeout

In adaptive timeout policy timeout associate with every entry is depend on current condition of network. This time is also update dependent on current situation of network.

3.3 Cache Origination

It is the fundamental question of cache origination that which data structure we are using so we can store and retrieve data efficiently.

3.3.1 Path Cache

When every source receive Route Reply from destination it also receive complete source route in the sequence of link between them. First link is between source and his neighborer and last link is between second last node and destination. By caching all of these paths separately we can consist path cache. It is very simple to implement like link list in data structure. In path cache we can easily identified that this path is loop free. Searching for any destination is also simple.

Fig.1 Path Cache Organization

3.3.2 Link Cache

This can be implemented graph as data structure. Every link returned by Route Reply is adding in to unified graph we can create link cache. Searching is more difficult in link cache compare to path cache. We use Dijkstra shortest path algorithm .Route in path cache is always present in link cache but vise versa is not true. By connecting individual links be can get batter path which may not present in path cache. Whenever a link is break a complete route in path cache is deleted while in link cache only one link is delete and other links are remains same.

Fig.2 Link Cache Organization

For calculation of timeout value it use average lifetime of route and time science last link is broken. Multiply average life time of route by some factor then apply MAX function on both values. Formula for computing time out T for every entry

T = MAX (α * average route lifetime, time since last link breakage)

The value of T is computed periodically and is used to expire stale entries from the cache.

4. Caching Scheme

This paper presents the timer based route expiry mechanism when applied to IERP part of ZRP. Its working is described in the following sections.

4.1 IERP Path for Route Cache

When a node S wants to send packet to node D, it first checks for the route in IARP table. If node D is not found in the table, it immediately invokes IERP for discovering the new path as shown in Figure 2. The figure also includes the route reply mechanism. Interzone Path creation. A single interzone path from S to D is created during a route request/reply cycle by allowing only the destination D to send a single reply for a given request. The path is tagged with a unique identifier A single interzone path from S to D is created during a route request/reply cycle by allowing only the destination D to send a single reply for a given request. The path is tagged with a unique identifier. ID, for example, obtained by using increasing sequence numbers generated by the requesting node.

When S triggers a new route discovery for a node D, it bordercasts a query message to all its border nodes.The message contains the identifier ID and a route accumulation vector AV[ ] initialized with AV[0]= S.

Let M be the number of active nodes (not including S and D).

1. When a border node X ≠ D receives a query message, if the message is received for the first time and the redundant query filter rules are satisfied: a. It adds its own identification into the accumulation vector. As an example, if the node X corresponds to node Bj in the interzone path, then AV [j]= X. b. If D belongs to X's routing zone, then the latter unicasts the query message to D. Otherwise, it executes a bordercast.

2. When the destination node D receives a query message with identifier ID for the first time: a. It stores the tuples (AV [i], AV[M], M + 1- i),

for 0 <=i<= M - 1 in EZT.

b. It prepares the list RN =(AV [i], M + 1- i), for 0 <=i<= M

c. It sets AV[M + 1]= D.

d. It sends a reply message to AV[M] The message contains the AV vector accumulated in the query message.

3. When a border node Bj receives a reply message: a. If Bj ≠ S, then it stores the triple (ID,AV[j-1],AV[j + 1]) in the IZP table, thus becoming an active node.

b. It stores the following tuples in EZT:

(AV [i], AV[ j-1], j - i), for 0 <=i<= j - 2 (AV [i], AV[ j+1], i - j), for j+2 <=i<= M+1

c. it prepares RN =[(AV [j +i], [i] for -j<=i<=M+ 1]

d. If Bj ≠ S, then it forwards the reply message to the node AV [j - 1]

Fig. 2b shows the state at node B2 after the reception of the reply message with AV =[S,B1,B2,B3,B4,D] that caused the execution of the following actions:

1. B2 becomes a member of an interzone path (it stores the triple (ID,B1,B3) in IZP)

2. B2 adds the entries (S,B1, 2), (B4,B3, 2), (D,B3, 3) in EZT.

3. B2 prepares the list of reachable nodes RN =[(S,2),(B1,1),(B3,1),(B4, 2)(D,3)]

4. B2 forwards the reply to B1.

The route is stored in the cache by the intermediate peripheral nodes, Bi. Figure 2 (c) shows the link breakage between the nodes B2 and B3

Fig 2 (a) Route Request & (b) Route reply through border nodes (c) Link breakage

4.2 Implementation

In a cache table, a node not only stores routes but also maintains the information necessary for cache updates. Each node maintains two types of information for each route: (1) how well the routing information is synchronized among nodes on the route, and (2) which neighbor node has learned which links through a ROUTE REPLY. Thus, for each cached link, a node knows which neighbor nodes have cached that link. When a link failure is detected, the algorithm notifies the neighborhood nodes that have that link in their caches. When a node receives a notification, the algorithm notifies selected neighbors. Therefore, the broken link information will be quickly propagated to all the reachable nodes that have the broken link in their caches.

Every route which has already invalided will not be remained at the Route Cache when it expires its remaining time. Also, due to dividing the cache's capacity, stale routes on intermediate nodes will be eliminated faster from the Route Cache than those of the conventional Route Cache because of reduced capacity. when a node receives the same route which is existing in the conventional Route Cache through the Route Request or Reply, the additional remaining time on the New Route Cache of that node will be given to that route by making a priority high, under the consideration that route has less chance to change its route. In case a new route arrives at that capacity a moment that a capacity is fully filled with routes, the algorithm checks the remaining time of each route within the capacity to determine which of them has to eliminate from the capacity, after checking the remaining time, the route that has the shortest remaining time is eliminated and a new route will register at that capacity newly. This paper presents the proposed research work on applying the Timer based route caching technique to ZRP.

5. Methodology

This paper investigates the impact of node mobility on the performance of ZRP when applied with Timer Based Route Cache technique. The performance study of the protocol can be made using network simulator ns2. The results can find out using the following metrics: 1) Packet Delivery Ratio (PDR) The fraction of originated data packets that are successfully delivered to their intended destination nodes. This specifically counts packets that are sent by the "application layer" on a source node that are received by the "application layer" on the corresponding destination node. 2) Total Overhead It is the number of separate overhead packets used by the routing protocol including the IARP and IERP packets. Each transmission (whether original or forwarding) of an overhead packet is counted. 3)Average End-to-End Delay This includes all possible delays caused by buffering during route discovery latency, queuing at the interface queue, retransmission delays at the MAC, propagation and transfer times.



Simulation Time

750 s

Network Coverage Area

1000 x 1000 m2

Number of Nodes


Routing Zone


Mobility Model

Model: Random Way Point

Pause Time: 0s, 100, …, 500s

Minimum Speed: 1 m/s

Maximum Speed: 20 m/s

Node Placement : Random


Source: CBR

Number of Sources : 10

Rate: 1 packet/s

Packet Size: 512 bytes




2 Mbps

Radio Range


Table 1. Parameters used for Simulation

The parameters used in our simulations are summarized in Table.1. We have assumed that all network nodes have same transmission range of 200m

6. Result Analysis

6.1 Delivery Performance

Fig.5 Throughput comparison for ZRP and Cached ZRP

The Figure 5 shows the comparative performance of the normal ZRP and ZRP with Caching. The Packet Delivery Ratio becomes almost equal for ZRP applied with and without the Caching when there is no mobility of the nodes. But, it can be seen that at medium and high mobility conditions, the ZRP protocol with caching shows a considerable improvement in the performance. It can be observed that there is more than 5% of the throughput in ZRP with Caching when compared with simple ZRP.

6.2 Overhead Performance

Fig. 6 Effect of Control Overhead on ZRPandCached ZRP

Figure 6 shows the effect of Control overhead on the performance of normal ZRP and ZRP with Caching at different mobility conditions. It can be observed that there is a great reduction in the control packets. This is obvious due to the readily availability of the routes in the route cache present at each node even after the link failures. This caching reduces the route discovery packets in IERP part of ZRP.

6.3 Delay Performance

Fig. 7 Effect of Delay on ZRP and Cached ZRP

Figure 7 presents the variation of delay with the mobility of the nodes for both normal ZRP and the ZRP with Caching. Even though some inconsistency in the data is reported, still, there is a considerable improvement in the performance. The statistics state that there is about 5% reduction in delay in case of Cached ZRP when compared with normal ZRP.

6. Conclusion

The timer based caching eliminate stale routes so that route cache is faster and thus applying this technique to Zone Routing Protocol (ZRP) improve the performance of ZRP protocol. Selecting the expiry time in the route cache is a key factor that influences the performance. This can be static or variable.