15-02-2011, 01:01 PM
kani_project.pdf (Size: 321.58 KB / Downloads: 125)
Distributed Cache Updating for the Dynamic
Source Routing Protocol
Abstract
On-demand routing protocols use route caches to make routing decisions. Due to mobility, cached routeseasily become stale. To address the cache staleness issue, prior work in DSR used heuristics with ad hocparameters to predict the lifetime of a link or a route. However, heuristics cannot accurately estimate timeoutsbecause topology changes are upredictable. In this paper, we propose proactively disseminating the brokenlink information to the nodes that have that link in their caches. We define a new cache structure calleda cache table and present a distributed cache update algorithm. Each node maintains in its cache table theinformation necessary for cache updates. When a link failure is detected, the algorithm notifies all reachablenodes that have cached the link in a distributed manner. The algorithm does not use any ad hoc parameters,thus making route caches fully adaptive to topology changes. We show that the algorithm outperforms DSRwith path caches and with Link-MaxLife, an adaptive timeout mechanism for link caches. We conclude thatproactive cache updating is key to the adaptation of on-demand routing protocols to mobility.
INTRODUCTION
In a mobile ad hoc network, nodes move arbitrarily. Mobility presents a fundamental challengeto routing protocols. Routing protocols for ad hoc networks can be classified into two major types:
proactive and on-demand.
Proactive protocols
attempt to maintain up-to-date routing information to
all nodes by periodically disseminating topology updates throughout the network. In contrast, ondemandprotocols attempt to discover a route only when a route is needed. To reduce the overheadand the latency of initiating a route discovery for each packet, on-demand routing protocols use routecaches. Due to mobility, cached routes easily become stale. Using stale routes causes packet losses,and increases latency and overhead. In this paper, we investigate how to make on-demand routing
protocols adapt quickly to topology changes. This problem is important because such protocols useroute caches to make routing decisions; it is challenging because topology changes are frequent To address the cache staleness issue in DSR (the Dynamic Source Routing protocol) [6], [8], priorwork [4], [11], [9] used adaptive timeout mechanisms. Such mechanisms use heuristics with ad hocparameters to predict the lifetime of a link or a route. However, a predetermined choice of ad hoc
parameters for certain scenarios may not work well for others, and scenarios in the real world aredifferent from those used in simulations. Moreover, heuristics cannot accurately estimate timeouts
because topology changes are unpredictable. As a result, either valid routes will be removed or staleroutes will be kept in caches.
To evict stale routes faster, DSR with path caches uses a small cache size. However, as trafficload or network size increases, small caches will cause route re-discoveries, because more routesneed to be stored, but small caches cannot hold all useful routes. If the cache size is set large, more
stale routes will stay in caches because FIFO replacement becomes less effective. It was shown thatpath caches with unlimited size perform much worse than caches with limited size, due to the largeamount of ROUTE ERRORS caused by the use of stale routes [4].In this paper, we propose proactively disseminating the broken link information to the nodes thathave that link in their caches. Proactive cache updating is key to making route caches adapt quicklyto topology changes. It is also important to inform only the nodes that have cached a broken link toavoid unnecessary overhead. Thus, when a link failure is detected, our goal is to notify all reachablenodes that have cached the link about the link failure.
We define a new cache structure called a cache table to maintain the information necessary forcache updates. A cache table has no capacity limit; its size increases as new routes are discovered anddecreases as stale routes are removed. Each node maintains in its cache table two types of informationfor each route. The first type of information is how well routing information is synchronized amongnodes on a route: whether a link has been cached in only upstream nodes, or in both upstream and
downstream nodes, or neither. The second type of information is which neighbor has learned whichlinks through a ROUTE REPLY. Thus, for each link in a node’s cache, the node knows which neighbor
nodes have cached that link. Therefore, topology propagation state, the information necessary andsufficient to remove stale routes, is kept in a distributed manner.gorith that uses the information kept by each node to achieve distributedcache updating. When a link failure is detected, the algorithm notifies selected neighborhoodnodes about the broken link: the closest upstream and/or downstream nodes on each route containing the broken link, and the neighbors that learned the link through ROUTE REPLIES. When a nodereceives a notification, the algorithm notifies selected neighbors. Thus, the broken link informationwill be quickly propagated to all reachable nodes that need to be notified.Our algorithm has the following desirable properties:_ Distributed: The algorithm uses only local information and communicates with neighborhood
nodes; therefore, it is scalable with network size.
_ Adaptive: The algorithm notifies only the nodes that have cached a broken link to update theircaches; therefore, cache update overhead is minimized.
_ Proactive on-demand: Proactive cache updating is triggered on-demand, without periodic behavior.
_ Without ad hoc mechanisms: The algorithm does not use any ad hoc parameters, thus makingroute caches fully adaptive to topology changes.Each node gathers the information about which node learns which link through forwarding packets,not through promiscuous mode, which is an optimization for DSR [10]. To handle situations where
promiscuous mode is used, we combine our algorithm and the secondary cache used in DSR withpath caches, without any modification to the algorithm.We evaluate the algorithm with and without promiscuous mode through detailed simulations. Weshow that, under non-promiscuous mode, the algorithm outperforms DSR with path caches by up
to 19% and DSR with Link-MaxLife [4] by up to 41% in packet delivery ratio. Under promiscuousmode, the algorithm improves packet delivery ratio by up to 7% for both caching strategies andreduces latency by up to 27% for DSR with path caches and 49% for DSR with Link-MaxLife.
Our contributions are threefold. First, we addressed the cache updating issue of on-demand routingprotocols. Second, we show that proactive cache updating is more efficient than adaptive timeout
mechanisms. Finally, we conclude that proactive cache updating is key to the adaptation of ondemandrouting protocols to mobility.
The organization of this paper is as follows. Section II gives an overview of DSR.
Section III
describes the cache update algorithm and two algorithms used to maintain the information for cache
updates. Section IV presents an evaluation of our algorithm. In Section V, we discuss related work,
and in Section VI, we present our conclusions.
II. THE DYNAMIC SOURCE ROUTING PROTOCOL
A. Overview of DSR
DSR consists of two on-demand mechanisms: Route Discovery and Route Maintenance. Whena source node wants to send packets to a destination to which it does not have a route, it initiatesa Route Discovery by broadcasting a ROUTE REQUEST. The node receiving a ROUTE REQUEST
checks whether it has a route to the destination in its cache. If it has, it sends a ROUTE REPLY tothe source including a source route, which is the concatenation of the source route in the ROUTEREQUEST and the cached route. If the node does not have a cached route to the destination, it adds
its address to the source route and rebroadcasts the ROUTE REQUEST. When the destination receivesthe ROUTE REQUEST, it sends a ROUTE REPLY containing the source route to the source. Each
node forwarding a ROUTE REPLY stores the route starting from itself to the destination. When thesource receives the ROUTE REPLY, it caches the source route.In Route Maintenance, the node forwarding a packet is responsible for confirming that the packethas been successfully received by the next hop. If no acknowledgement is received after the maximum
number of retransmissions, the forwarding node sends a ROUTE ERROR to the source, indicating thebroken link. Each node forwarding the ROUTE ERROR removes from its cache the routes containingthe broken link.
B. Route Caching in DSRDSR uses path caches [1] or link caches [4]. In a path cache, a node stores each route startingfrom itself to another node. In a link cache, a node adds a link to a topology graph, which represents
the node’s view of the network topology. Links obtained from different routes can form new routes.Thus, link caches provide more routing information than path caches.A node learns routes through forwading ROUTE REPLIES and data packets, or by overhearingpackets when promiscuous mode is used [10]. DSR does no cache the source route accumulated ina ROUTE REQUEST, since ROUTE REQUESTS are broadcast packets and thus links discovered maynot be bi-directional [8]. Due to the same reason, when a node forwards a ROUTE REPLY, it caches
only the links that have been confirmed by the MAC layer to be bi-directional [8], which are thedownstream links starting from the node to a destination. When forwarding a data packet, a nodecaches the upstream links as a separate route. After initiating a Route Discovery, a source node maylearn many routes returned either by intermediate nodes or by the destination; it will cache all thoseroutes. Thus, DSR aggressively caches and uses routing information.Besides Route Maintenance, DSR uses two mechanisms to remove stale routes. First, a sourcenode piggybacks on the next ROUTE REQUEST the last broken link information, which is called
a GRATUITOUS ROUTE ERROR. Although this optimization helps remove stale routes from morecaches, GRATUITOUS ROUTE ERRORS are not able to reach all nodes whose caches contain thebroken link, because some ROUTE REQUESTS will not be further propagated due to the use ofresponding to ROUTE REQUESTS with cached routes. Second, DSR uses heuristics: a small cachesize with FIFO replacement for path caches and adaptive timeout mechanisms for link caches [4],
where link timeouts are chosen based on observed link usages and breakages.
III. THE DISTRIBUTED CACHE UPDATE ALGORITHM
In this section, we first describe the cache staleness issue. We then give the definition of a cachetable and present two algorithms used to maintain the information for cache updates. Finally, wedescribe our distributed cache update algorithm in detail.A. Problem StatementOn-demand Route Maintenance results in delayed awareness of mobility, because a node is notnotified when a cached route breaks until it uses the route to send packets.
We classify a cachedroute into three types:
_ pre-active, if a route has not been used;
_ active, if a route is being used;
_ post-active, if a route was used before but now is not.
It is not necessary to detect whether a route is active or post-active, but these terms help clarifythe cache staleness issue. Stale pre-active and post-active routes will not be detected until they areused. Due to the use of responding to ROUTE REQUESTS with cached routes, stale routes may bequickly propagated to the caches of other nodes. Thus, pre-active and post-active routes are importantsources of cache staleness.
We show an example of the cache staleness issue. In Figure 1, assume that route ABCDE isactive, route FGCDH is post-active, and route IGCDJ is pre-active. Thus, node C has cached boththe upstream and the ownstream links for the active and post-active routes, but only the ownstream links, CDJ, for the pre-active route. When forwarding a packet for source A, node C detects thatlink CD is broken. It removes stale routes from its cache and sends a ROUTE ERROR to node A.However, the downstream nodes, D and E, will not know about the broken link. Moreover, nodeC does not know that other nodes also have cached the broken link, including all the nodes on thepost-active route, F, G, D, and H, and the upstream nodes on the pre-active route, I and G.
Stale routes have several adverse effects:_ Using stale routes causes packet losses if packets cannot be salvaged by intermediate nodes;
_ Using stale routes increases packet delivery latency, since the MAC layer goes through multipleretransmissions before concluding a link failure;
_ Using stale routes increases routing overhead, since the node detecting a link failure will senda ROUTE ERROR to te source node;
_ Using stale routes degrades TCP performance, since TCP will invoke congestion control mechanisms
for packet losses caused by route failures.
B. Assumption
Promiscuous mode [10] disables the network interface’s address filtering function and thus causesa protocol to receive all packets overheard by the interface. Since it is impossible to know whichneighbor overhears which link, we do not maintain such information in a cache table. To handle
promiscuous mode, we use a secondary cache to store overhead routes, without any modification tothe cache update algorithm. We will present this approach in detail in
C. Overview
When a node detects a link failure, our goal is to notify all reachable nodes that have cached thatlink to update their caches. To achieve this goal, the node detecting a link failure needs to knowwhich nodes have cached the broken link and needs to notify such nodes efficiently. This goal isvery challenging because of mobility and the fast propagation of routing information.Our solution is to keep track of topology propagation state in a distributed manner. Topologypropagation state means which node has cached which link. In a cache table, a node not only storesroutes but also maintain two types of information for each route:
(1) how well routing information
is synchronized among nodes on a route; and (2) which neighbor has learned which links through aROUTE REPLY. Each node gathers such information during route discoveries and data transmission,
without introducing additional overhead. The two types of information are sufficient, because eachnode knows for each cached link which neighbors have that link in their caches.Each entry in the cache table contains a field called DataPackets. This field records whethera node has forwarded 0, 1, or 2 data packets. A node knows how well routing information is
synchronized through the first data packet. When forwarding a ROUTE REPLY, a node caches onlythe downstream links; thus, its downstream nodes did not cache the first downstream link throughthis ROUTE REPLY. When receiving the first data packet, the node knows that upstream nodes
have cached all downstream links. The node adds the upstream links to the route consisting of thedownstream links. Thus, when a downstream link is broken, the node knows which upstream nodeneeds to be notified. The node also sets DataPackets to 1 before it forwards the first data packet to
the next hop. If the node can successfully deliver this packet, it is highly likely that the downstreamnodes will cache the first downstream link; otherwise, they will not cache the link through forwardingpackets with this route. Thus, if DataPackets in an entry is 1 and the route is the same as the sourceroute in the packet encountering a link failure, downstream nodes did not cache the link. However,if DataPackets is 1 and the route is different from the source route in the packet, downstream nodes
cached the link when the first data packet traversed the route. If DataPackets is 2, then downstreamnodes also cached the link, whether the route is the same as the source route in the packet.Each entry in the cache table contains a field called ReplyRecord. This field records which neighborlearned which links through a ROUTE REPLY. Before forwarding a ROUTE REPLY, a node recordsthe neighbor to which the ROUTE REPLY is sent and the downstream links as an entry. Thus, when8
an entry contains a broken link, the node will know which neighbor needs to be notified.The algorithm uses the information kept by each node to achieve distributed cache updating.When a node detects a link failure while forwarding a packet, the algorithm checks the DataPackets
field of the cache entries containing the broken link:
(1) If it is 0, indicating that the node has notforwarded any data packet using the route, then no downstream nodes need to be notified because
they did not cache the broken link.
(2) If it is 1 and the route being examined is the same as thesource route in the packet, indicating that the packet is the first data packet, then no downstream
nodes need to be notified but all upstream nodes do.
(3) If it is 1 and the route being examined isdifferent from the source route in the packet, then both upstream and downstream nodes need to be
notified, because the first data packet has traversed the route. (4) If it is 2, then both upstream anddownstream nodes need to be notified, because at least one data packet has traversed the route. Thealgorithm notifies the closest upstream and/or downstream nodes and the neighbors that learned thebroken link through ROUTE REPLIES. When a node receives a notification, the algorithm notifiesselected neighbors: upstream and/or downstream neighbors, and other neighbors that have cached the
broken link through ROUTE REPLIES. Thus, the broken link information will be quickly propagatedto all reachable nodes that have that link in their caches.
D. The Definition of a Cache Table
It was shown that no single cache size provides the best performance for all mobility scenarios [4]Thus, we design a cache table that has no capacity limit. Without capacity limit allows DSR to storeall discovered routes and thus reduces route discoveries. The cache size increases as new routes are
discovered and decreases as stale routes are removed.There are four fields in a cache table entry:
_ Route: It stores the links starting from the current node to a destination or from a source to adestination.
_ SourceDestination: It is the source and destination pair.
_ DataPackets: It records whether the current node has forwarded 0, 1, or 2 data packets. It is 0initially, incremented to 1 when the node forwards the first data packet, and incremented to 2when it forwards the second data packet.
_ ReplyRecord: This field may contain multiple entries and has no capacity limit. A ReplyRecordentry has two fields: the neighbor to which a ROUTE REPLY is forwarded and the route starting from the current node to a destination. A ReplyRecord entry will be removed in two cases:
when the second field contains a broken link, and when the concatenation of the two fields isa sub-route of the source route, which starts from the previous node in the source route to thedestination of the data packet. We will give a reason for the second case in the next section.
E. Information Collection and Maintenance
We use algorithms addRoute and findRoute to collect and maintain the information necessary forcache updates. Algorithm addRoute is called when a node attempts to add a route to its cache table.Algorithm findRoute is called when a node tries to find a route to some destination.
1) Adding a Route: Algorithm addRoute is shown in Figure 2. A node adds a route either from aROUTE REPLY or from a data packet. When a node receives a ROUTE REPLY, it attempts to add toits cache the route starting from itself to the destination (lines: 1–14). If the node is the destination
of the ROUTE REPLY (lines: 2–5), which is also the source node, it stores the source route and setsDataPackets to 0, as the route has not been used. If the node is an intermediate node forwardingthe ROUTE REPLY (lines: 7–14), it checks whether the route exists in its cache. If the route doesnot exist, the node creates a cache table entry to store the route, sets DataPackets to 0, and createsa ReplyRecord entry to record which neighor will learn the downstream links. If the route exists,the node adds an entry to the ReplyRecord field if the entry does not exist.
When a node receives a data packet, it checks whether the source route exists in its cache. Ifthe route exists and DataPackets is 1 (lines: 16–19), the node sets DataPackets to 2, since the nodeis forwarding the second data packet. If the route does not exist and the node is the destination
(lines: 21–22), it creates a cache table entry to store the route and sets DataPackets to 1, sincethe destination has received the first data packet. If the route does not exist and the node is anintermediate node (lines: 24–34), it searches its cache for a route consisting of the downstream links
of the source route. If such a route exists, the node adds the upstream links to the route to completea full path, and sets DataPackets to 1, since it is forwarding the first data packet. The node alsoremoves the ReplyRecord entry in which the concatenation of two fields is the route starting fromthe previous node to the destination of the packet. This is because the node has kept the informationthat the upstream nodes have cached the downstream links. The upstream nodes include the neighbor
recorded in the ReplyRecord entry. If the node cannot complete a full path (lines: 35–36), it createsa cache table entry to store the source route and sets DataPackets to 1. For this case, the packet is10
Algorithm: addRoute
Input: PACKET p;
Variables:
ID f irst, last; /* the first and last node in a source route */
ID next; /* the node to which a RREP is sent */
ID netID; ID pre;/* the previous node */ boolean is completed;
1 if p is a ROUTE REPLY then
2 if netID = p:dest then
3 e := getFromCacheTable(prcRoute);
4 if e = null then
5 cacheTable := cacheTable[f(prcRoute; ( f irst; last);0; )g
6 else
7 newRoute := prcRouteubPath(netID; last);
8 reply pair := (next;newRoute);
9 e := getFromCacheTable(newRoute);
10 if e = null then
11 cacheTable := cacheTable[f(newRoute; ( f irst; last);0; reply pair)g
12 else
13 if reply pair 62 e:replyRecord then
14 e:replyRecord := e:replyRecord[freply pairg
15 elseif p is a data packet then
16 e := getFromCacheTable(prcRoute);
17 if e 6= null then
18 if eP = 1 then
19 eP := 2
20 else
21 if netID = p:dest then
22 cacheTable := cacheTable[f(prcRoute; (prc; p:dest);1; )g
23 else
24 for each entry e 2 cacheTable do
25 if ercDestrc = prc and ercDest:dest = p:dest and prc = p:route[0] then
26 temp := prcRouteubPath(netID; last);
27 if temp = e:route and eP = 0 then
28 e:route := prcRoute;
29 eP := 1;
30 is completed := TRUE
31 for each entry r 2 e:replyRecord do
32 temp := prcRouteubPath(pre; last);
33 if (r:nodeNotifiedjjrubrouteSent) = temp then
34 e:replyRecord := e:replyRecord n frg;
35 if not is completed and prc = p:route[0] then
36 cacheTable := cacheTable[f(prcRoute; (prc; p:dest);1; )g
Fig. 2. Pseudo Code for Algorithm addRoute
the first packet from the source node that received a ROUTE REPLY sent by the current node or byanother node that has a cached route to the destination, and the route consisting of the downstreamlinks has been completed by another flow. We will show an example for this case in Section III-E.3.2) Finding a Route: Algorithm findRoute is shown in Figure 3. A node attempts to find a routeeither to respond to a ROUTE REQUEST or to send data packets. If a node finds a route to send aROUTE REPLY, it adds an entry to the ReplyRecord field of the corresponding cache table entry,which includes the neighbor to which the ROUTE REPLY is forwarded and the found route. If a node
Algorithm: findRoute
Input: ID dest, PACKET p, boolean respond to RREQ,
boolean used for salvaging
Output: PATH route
1 e0 := ;
2 for each entry e 2 cacheTable do
3 if dest 2 e:route then
4 temp := e:routeubPath(netID; dest)
5 if route = or jtempj < jroutej then
6 route := temp; e0 := e
7 if e0 = then exit;
8 if respond to RREQ then
9 reply pair := (prcRoute[prcRoute:length