Possible Alternative Strategies for Replica Retrieval

Redman Replica Retrieval Effectiveness

Flooding-based

The most intuitive and simple RR strategies are flooding-based. A first possible solution, which we will call IRP Flooding (IF) in the following, could establish that delegates disseminate IRPs about all their hosted resources to all nodes in the dense MANET (flooding of IRP messages). However, “the cost of making sure that everyone knows about everything is prohibitive” in MANET environments, mainly for scalability reasons [vaidya]. In fact, to maintain an eager-consistent up-to-date view of IRPs, any delegate with a changing set of hosted resources should overburden the network with continuous IRP update message flooding; moreover, also the memory required to locally maintain IRPs of all replicas in the dense region could be unsustainable.

A second possible flooding-based solution (Query Flooding - QF) could specify that delegates do not have to diffuse any IRP; message flooding is necessary in the search phase where all nodes are exhaustively explored to look for requested resources (flooding of search messages). QF makes sense only if the number of RR searches is very limited and it is not worth paying the overhead for diffusing IRPs. Moreover, if the frequency of node entrances/exits in/out the dense MANET is very high, IRPs tend to become stale very soon, and the advantages of IF is significantly reduced.

k-hop Distance IRP Dissemination

Our research activity has focused on investigating novel RR strategies to avoid message flooding during the search phase by distributing IRPs only to a subset of nodes in the dense MANET. An original solution investigated, called k-hop Distance IRP Dissemination (k-DID), specifies to place IRPs only on nodes positioned at fixed k-hop distance the ones from the others. In other words, i) the IRP related to a specified resource should be placed at exactly k hops from at least another copy of the same IRP; ii) there should not be a path shorter than k hops between two copies of the same IRP; and iii) IRPs should be distributed over the whole network so that each node is at most at k hops from the IRP of any replicated resource. When adopting k-DID, IRP retrieval (and consequently replica discovery) only requires to explore the nodes situated, on average, at (k/2)-hop distance from the searcher. Let us observe that k-DID improves the solution in [watanabe], where placement information similar to REDMAN IRPs is duplicated on all nodes located at fixed distance from resource-hosting nodes; in [watanabe] IRP nodes could also be at single-hop distance the one from the other.

We have carefully investigated how k-DID could be effectively implemented in a lightweight way. Let us preliminary note that an IRP distribution strategy based on a single network flooding is infeasible, since it cannot determine which nodes at k-hop distance from an IRP-owning node are also at k-hop distance the one from the other. To practically present our k-DID implementation, suppose a delegate is willing to diffuse IRPs of its resources at k-hop distance. k-DID executes the following steps:

• the delegate prevents its neighbors distant less than k hops to host an IRP copy by flooding a denial message with TTL=k. Nodes receiving those messages with TTL>0 change their state to unavailable to reflect their unavailability for IRP hosting;
• the delegate sends an IRP copy and assigns its initial role of IRP distributor to one of the nodes, identified at step 1, that are placed exactly at k-hop distance and whose state is free;
• steps 1 and 2 are reiterated until the IRP distributor cannot identify any free node at k-hop distance. If there are no free nodes, the backtracking phase at step 4 starts;
• during backtracking, the IRP distributor commands its distributor predecessor to repeat step 4. If a free potential IRP distributor is found, then IRP dissemination goes on from step 1. Otherwise, step 4 is repeated until the initial resource delegate is reached, thus ending the protocol.

Let us say that N is the number of nodes belonging to the network and F(k) the average number of nodes belonging to a k-hop-diameter sphere included in the dense MANET. k-DID imposes a relevant overhead in terms of messages sent for distributing IRPs, mainly depending on N and k. However, the number of nodes with IRPs is low (about one node every F(k/2) ones) and the search message overhead is very low. In fact, each client expects to find a replica of the requested resource by querying all nodes within its surrounding k/2 hops. However, k-DID hardly scales in presence of node mobility since it is difficult to preserve the validity of the three above constraints without imposing heavy communication-intensive maintenance protocols for IRP distribution.