Data is increasingly distributed across networks of mobile nodes such as wireless sensor networks, distributed smartphone applications, or ad hoc recovery networks in disaster scenarios, but must still be reliably collected, stored, and retrieved. While such networks run in either ad hoc mode or use existing infrastructure, all of them must deal with node heterogeneity. Wireless nodes invariably have differing levels of power availability, and often varying connectivity and computing power. While many distributed hash tables (DHTs) have been designed for mobile ad hoc or heterogeneous networks, they do not consider differences in node strength, or resource availability, for an arbitrary number of resource availability levels. In this paper, we present a scalable, location aware, hierarchical DHT that utilizes nodes' varying resource availability levels to increase and prolong the mobile network's data storage and retrieval capabilities. Furthermore, we compare this DHT to other location aware flat and hierarchical approaches, examining their structures' suitability for nodes with varying resource availability.
Today, mobile applications are no longer restricted to the classic client/server architecture relying on a backbone infrastructure. Instead, an increasing number of applications for smartphones (e.g. mobile games, content sharing) as well as wireless sensor network applications follow a serverless ad-hoc model of interaction and data exchange. Even if such applications require a server or gateway to initially fetch some data or to finally publish results, data has to be collected, exchanged, and stored for some time in the network. From a data management point of view, this poses two challenges: (1) to efficiently manage and retrieve data in a distributed way and (2) to reliably provide the data while taking possible node failures and resource restrictions (connectivity, battery power) into account.
Distributed hash tables (DHT) for mobile peer-to-peer
(P2P) networks have been proposed in the past to address
the first challenge. However, constructing a distributed hash
table on a mobile P2P network, where nodes have restricted
battery power and communication costs the peers vital
energy, is a definite challenge. While traditional DHTs such as
the Content Addressable Network (CAN) [
A fundamental operation for any kind of data management task (store, update, retrieve) in a DHT is the key lookup operation. To implement this operation in a (mobile) ad-hoc network, overlay nodes also forward messages on the network layer, in which case a long distance overlay hop may require many forwarding nodes, while a short distance lookup hop may be completed with few network hops. This case brings the additional challenge of routing distances, giving the physical distance that lookups traverse a central role in a network’s ability to survive its load. Thus, power and (in the future) location awareness are important for DHTs running on mobile networks.
Consider for example a large network based on smartphones, laptops and a limited number of servers that cooperatively maintain a DHT, with each node storing some of the global application data. As long as the load is balanced between the nodes, this network is inherently scalable - each of the nodes is responsible for fetching and storing a portion of the network’s information and for routing and processing a portion of the network’s requests. While the numerous smartphones jointly provide a large portion of the network’s storage and routing capabilities, a single smartphone has a restricted amount of battery power available in a give time frame (until it is recharged). Thus, the network must find a way to incorporate each of these weaker nodes’ resources in order to provide scalability without causing failure by overuse. In this paper, we address the second of the above mentioned challenges by examining several approaches to balancing maintenance and routing load according to node’s resource (i.e. power) availabilities and locations. None of these approaches acts blindly with regard to either resources or locations, yet each has clear limitation with regard to how much it can incorporate. Since we could, for example, consider a node’s restricted computing power or bandwidth availability instead of its power availability, we consider the abstract notion of a node’s “resource availability.”
The three major approaches towards addressing
heterogeneous node capabilities in DHTs - hierarchical DHT
structures, virtual nodes, and node movements within the
identifier space - are typically not well adept to our scenario.
Hierarchical approaches, typically with two tiers [
We compare four different structural resource and location
aware DHT approaches in this paper: (a) a novel,
multitiered hierarchical approach, (b) a two-tiered hierarchical
approach, (c) a flat resource and location aware approach
[
We discuss related work in Section 2; explain our network assumptions and foundations in Section 3; describe our novel DHTs and consider the routing complexity of the approaches in Section 4; and compare the four DHTs using simulation in Section 5.
The DHT forerunners such as CAN (Content
Addressable Network) [
The three main approaches for balancing load in
heterogeneous DHTs are the use of hierarchical DHT structures,
virtual nodes, and node movements within the identifier
space. Hierarchical DHTs often group nodes by some
defining characteristic such as group associations (e.g.
departments within a university) or peer capabilities (“have” or
“have not”). Systems with group structures such as Canon
[
Virtual nodes pose a different solution, with each physical
network node balancing its load independently by hosting a
varying number of virtual overlay nodes, each with its own
set of keys and links [
DHTs for mobile ad hoc networks (MANETs) pose
additional challenges since each overlay hop represents multiple
underlay hops on DHT nodes, underlay routing to unknown
destinations often results in broadcast messages, nodes’
mobility causes frequent changes in “good” routes, and high
node churn due to short uptimes (and dwindling resources)
requires highly dynamic protocols for overlay maintenance
and data persistence. Among the first DHTs suggested for
MANETs were Ekta [
While proximity-awareness plays a central role in the
development of DHTs for wireless networks, the treatment of
nodes’ heterogeneity also effects the robustness of the final
system, especially when considering nodes’ power
availability and connectivity. The numerous mentioned DHT
substrates handle node heterogeneity differently - ignoring it
completely or incorporating it in a flat or hierarchical
manner - but there exists limited work comparing these
various approaches. Furthermore, little has been done to treat
nodes with varying resource availabilities in DHTs with
mobile nodes on a finer scale than strong or week, as in the
Chord extension RBFM [
Coordinates. We assume that each node x has
sufficiently correct two dimensional virtual (not necessarily
geographical) network coordinates (x1, x2), such as used in
Vivaldi [
Resources. We model our analysis and simulations after nodes with varying power availability - from smartphones with very limited power to servers with an inexhaustible power source - but the proposed protocol need not be restricted to this use case. It only requires that each node x has a resource availability that can be expressed as an integer value xR ∈ {0, 1, . . . , lmax} for some fixed maximum level lmax. We assume that xR = 0 is the lowest possible resource level (but still operational) while xR = lmax implies unbounded resources. Note that resource levels must be globally defined so that a given resource level on differing node types is comparable. If we consider power availability with lmax = 3, that could mean that a handheld operating on battery power may have resource level two when fully charged, but a cell phone with a weaker battery may only reach a resource level one when fully charged.
For our simulation, we use a Zipf distribution for nodes’
resource levels, reflecting trends for node lifetime found in
peer-to-peer networks, where node lifetime tends to follow
a heavy-tailed Pareto distribution [
1 (` + 1)m · Pljm=a0x 1/(j + 1)m .
(1) Failures. For our simulation, we assume that failures are due to nodes’ resources being depleted by node activity. Each send and receive activity drains a node’s resources until the node fails (based on nodes with varying power availability). We use asymmetrical drain patterns, with a send costing more than a receive, but constant drain for all but the top level, which is not drained at all. The selected resource and drain values are abstract and serve as a benchmark to compare the protocols as opposed to assessing the real word battery runtimes. To provide results with as few dependencies as possible, we take a simplistic approach to churn in our evaluation, with nodes drained until they fail but no additional nodes added. The system runs until it has been reduced to half of the original nodes.
DHT Foundation. All of the approaches we use are
based on Chord [
Key Distance 1. The key distance from x to y is the clockwise distance on the key ring from xID to yID: dkey(x, y) := yID − xID mod 2m. 4.
We call our hierarchical approach Hierarchical Resource
Management (HRM), where nodes are separated into
different levels and maintain links within and between those
levels. The lowest level, consisting of the weakest nodes,
functions as a leaf level where each leaf node maintains a
parent node from some upper level. Each level is linked
together to form a location aware DHash++ [
In the following we refer to bottom level nodes with resource level = 0, upper level nodes with resource level > 0, top level nodes with resource level = lmax, and lower level nodes with resource level < lmax. In addition to each node’s links to its predecessor and first r successors, we have three additional types of links: leaf-parent links between bottom and upper level nodes; inter-level links which connect each upper level node with its immediate successor in each of the lmax − 1 upper levels; and level fingers which provide each upper level node shortcuts within its own resource level. 4.1
Each node is responsible for the keys in its simple key range, but we also consider an upper level node’s upper key range which contains all of its leaf nodes’ nodeIDs and is integral to successful routing. For this, each node maintains upper level successor and predecessor nodes, i.e. the first successor and predecessor nodes from any upper level. Then a node x’s upper key range x.urange consists of all keys between xID and its upper level successor’s key. Note that x.srange and x.urange overlap only in xID.
p3
p4 ,ixp2 B
p1 xID + 2i−1
xID xID
Leaf Links. Each bottom level node x (xr = 0) maintains a link to its parent node π(x), which is the first upper node preceding x in the keyspace. Thus, leaf nodes have parents from varying resource levels. Leaf nodes have neither inter-level links nor level fingers.
Inter-level Links. Each upper level node x establishes a link x.I[`] to its direct successor x.I[`].node in each of the upper levels `.
Level Fingers. In DHash++, each node x with nodeID xID chooses one link - or finger - x.F [i] per finger interval Bx,i := [xID + 2i−1, xID + 2i) for i ∈ {1, 2, . . . , m}. The corresponding node that x.F [i] points to is notated x.F [i].node. In our protocol, a node x only choses fingers within the same resource level, i.e. (x.F [i].node)R = xR. Furthermore, the number of fingers that a lower level node establishes varies from level to level.
A level 1 node x has as few fingers as necessary, establishing level fingers only to nodes which are closer successors in the keyspace than x’s closest higher level inter-level link. That means: dkey(x, x.F [i].node) < dkey(x, x.I.closestHigher). (2) Where x.I.closestHigher is the closest of x’s higher level inter-level links, x.I.closestLevel is x.I.closestHigher’s resource level, and x.I.closestInt is the finger interval in which x.I.closestHigher is found: x.I.closestLevel := dkey(x, x.I[`].node) argmax `:xR<`≤lmax x.I.closestHigher := x.I[x.I.closestLevel].node
x.I.closestInt := j : x.I.closestHigher ∈ Bx,j .
Meanwhile, level lmax and lmax − 1 nodes maintain fingers for each finger interval Bx,i := [xID + 2i−1, xID + 2i) for i ∈ {1, 2, . . . , m}. Nodes in additional levels ` with 1 < ` < lmax − 1 maintain sets of fingers of varying sizes, depending on `. We let x.F interval ∈ {1, 2, . . . , m} be the furthest finger interval in which a node x maintains a finger and x.F key = xID + 2F interval−1 its corresponding key value. For example, given five levels (lmax = 4), we might have: x.F interval = x.I.closestInt, xR = 1
m − 1, xR = 2 m, xR ∈ {3, 4}.
Thus, each upper level node x maintains a finger table with (at most) one finger for each finger interval Bx,i with i ∈ {1, 2, . . . , x.F interval}. Note that the fewer links a level maintains, the less maintenance load is incurred and the faster messages are passed on to other (higher) levels. Lookups are thus routed quickly out of the bottom layers and dispersed between the upper layers.
Level fingers are chosen in a location aware fashion as in DHash++. Nodes’ coordinates and resource levels are piggybacked on network messages, providing node information to other nodes at minimal overhead. Thus, an upper level node x choses for x.F [i] that known node with resource level xR in the finger interval Bx,i which has the smallest physical distance to x. For this, x maintains a set of lmax prospective links lists, one for each resource level, with the `th prospective links list containing a list of the closest (in terms of physical distance) k nodes in Bx,i for each i ∈ {1, 2, . . . , m} from level ` which are known to x. At most k nodes in Bx,i are saved via their resource levels, nodeIDs, and physical distances, so we have at most k · m · lmax saved nodes.
When x receives a message that originated at sender y, x uses y’s coordinates to determine dphy(x, y) and update its level yR prospective links list accordingly (see Figure 3). An ith-finger request is sent to the closest entry in x’s level xR prospective links list for Bx,i, if it contains an entry (see Figure 2). Otherwise, the first successor of key xID +2i−1 in resource level xR is contacted (see Figure 3), which requires level-specific lookup forwarding (see Routing). Upon node x’s receipt of a finger request response from node y, if yR = xR and y ∈ Bx,i with i ≤ x.F interval, then y is assigned to x.F [i]. If a given finger interval contains no level xR node, then this finger entry remains empty.
Note that while node x only links level fingers to nodes in level xR, maintaining prospective links lists for multiple levels causes little overhead while easing a node’s transition between resource levels. The prospective links list entries are continually updated with fresh node information to automatically adapt the network to changing coordinates and are deleted once used for a finger request to ensure their freshness. Simulations have shown that k = 1 is beneficial in networks with high churn, reducing the use of failed prospective links and minimizing the lists’ overhead.
Figure 1 shows the basic overlay stucture. The connected key ring on which each node establishes its predecessor and successor is shown on top, and the individual levels are shown below with the bottom level nodes assigned to their upper level predecessors (i.e. parents). Inter-level links are shown for three nodes only and level fingers were omitted. 4.2
To join the DHT, a node x must have valid network coordinates, choose a nodeID and resource level, and contact procedure maintainFinger(finger) lookupKey = myKey + getOffset(finger) myLevelList = prospLinkList(myLevel) if myLevelList.size(finger) > 0 thenlevel listEntry = myList.getClosestEntry(finger) lookupKey = listEntry.key myList.removeUsedEntry(listEntry) end if sendLookup(lookupKey) end procedure procedure suggestProspectiveLink(nodeInfo) finger = getFingerInterval(nodeInfo.key) dist = getPhysicalDist(nodeInfo.coordinates) level = nodeInfo.resourceLevel if pLList(level).contains(finger, nodeInfo.key) then pLList(level).update(finger, dist, nodeInfo) else if pLList(level).size(finger) < k or dist < pLList(level).farthestLinkDist(finger) then pLList(level).addNode(finger, dist, nodeInfo) while pLList(level).size(finger) > k do
pLList(level).removeFarthestLink(finger) end while end if end procedure one participating node. Once x has established links to its immediate predecessor p and successor s on the key ring, s sends its successor lists to x, which x uses to initialize its own list, and corresponding keys are transfered from s to x. Once x has completed the basic join in the overlay, it must also perform either a leaf join or upper level join (see below). The node x continually updates its prospective links lists and periodically performs finger maintenance (see Figure 3) to establish and maintain its fingers.
The basic reaction to node failures is as in Chord, with failed nodes also removed from the inter-level list, prospective link lists, and potentially the parent link or leaf list once their failure is noticed. An upper level node leaves gracefully by sending messages to each of its leaf nodes and its upper level predecessor informing them of their new parents/leaf nodes. Otherwise, if a leaf node’s parent has fails unexpectedly, the leaf node must perform a leaf join to reestablish a parent (see below).
Upper Level Joins and Failures. The upper level join serves two purposes: establishing the upper level successor and predecessor nodes (from any upper level) and transferring the responsibility for leaf nodes. Node x uses an upper level bootstrap node to send an upper level join message, which is routed along the upper level nodes to x’s upper level predecessor y, for which xID ∈ y.urange. Node y responds to x with its own upper level successor z and the list of y’s leaf nodes which are now in x.urange. Then y informs each of these leaf nodes of their new parent node x and removes them from its leaf list.
If an upper level node’s resource level is reduced to the lowest level, it becomes a leaf node and forfeits its role as parent node by transferring its leaf nodes to its upper level predecessor y. Leaf nodes ignore finger and inter-link requests, upper and leaf join requests, and upper stabilize requests. If it is observed that a node has left the upper levels, it must be removed from inter-level list, prospective link lists, upper level successor and predecessor links, and parent links (but not from successor and predecessor links).
Leaf Joins and Failures. Nodes with resource level 0 perform leaf joins to establish a live parent node. Recall that a node x’s parent is the first preceding upper level node on the key ring. The message is forwarded to an upper level bootstrap node and then routed to the upper level node whose upper level key range contains xID. This parent node responds and and enters x into its leaf list.
Maintenance. Given the dynamics of mobile networks, maintenance is integral for detecting and addressing network changes. Inter-level links and level fingers are maintained similar to in RBFM with varying maintenance intervals and are automatically adapted when nodes change resource levels. Thus, each link is maintained at an interval that depend on the link’s node’s resource level: Bottom level links are maintained according to a reference interval tref and higher level links at varying multiples of tref for each resource level.
However, leaf and parent links as well as upper level successor and predecessor links are maintained analogously to direct successor and predecessor links, using direct maintenance messages at a fixed interval. 4.3
Routing of lookups is not performed in a strictly greedy fashion like Chord, but rather in a series of greedy steps. Let κ be the message’s destination key. Now recall that a message is destined for the node whose simple key range contains κ. One negligible piece of information is added to messages: the key of the last upper level node that handled the message (only needed for high churn scenarios). Once a node x has determined that κ ∈/ x.srange, its routing behavior depends on its resource level as follows:
Leaf Nodes. If a message originates at a leaf node x, it is forwarded to the parent node. Otherwise, if x receives a messages for which its parent node was not the last upper level node to have handled the message, it forwards the message to its parent node. Otherwise, it forwards the message to its successor node y if κ ∈ y.srange or else to the closest preceding node from its successor list.
Upper Level Nodes. An upper level node x routes greedily to the closest preceding node in a resource level ≥ xR using both its finger table and inter-level list. For lower level nodes with restricted finger tables, this means that messages to ’distant’ destinations are routed to upward. For top level nodes, this means that messages are routed to the closest top level predecessor of κ.
If there is no closer predecessor node with resource level ≥ xR, then the message is routed back down the hierarchy by choosing the highest possible inter-level link preceding κ. If there are no such links, then κ ∈ x.urange and the message is delivered directly to the node y with κ ∈ y.srange: y is either x’s upper level successor (whose simple key range overlaps x.srange) or one of x’s leaf nodes.
Level Routing. Finger requests and inter-level link requests use level sensitive overlay routing. These requests are not necessarily delivered to the node x for which κ ∈ hord hord x.srange, but rather to the first successor of κ in a given level `. A node y considers itself the request’s destination if yR = ` and κ is between the sending node’s nodeID and yID. If not, y forwards to its level ` inter-level link if it succeeds κ, or to its closest known preceding link in level `.
Lookup Hop Length Theorem 1. Given a network with N nodes, the expected upper bound for the number of overlay hops required for a lookup from any node to the successor node of any key is O(log(N )) hops.
Proof. To show that routing terminates and find an upper bound on the routing hops, we consider the farthest possible lookup route. Since it takes at most one hop to route from a leaf to a parent node, we assume that each message originates at an upper level node. Furthermore, since it takes at most one hop to reach the node y with κ ∈ y.srange from κ’s upper level predecessor, we need only determine the number of hops necessary to reach κ’s upper level predecessor.
If the originating node, its successor, or its upper level successor are the destination, then we are done. Otherwise, the message is passed upwards until it reaches the first level in which the destination key is a predecessor of the current node x’s x.F key, i.e. dkey(x, κ) < dkey(x, x.F key). The message is passed up at most lmax−1 levels, from the bottom to the top level.
So assume that κ is a predecessor of x.F key and will thus
be routed within level λ := xR on level fingers until it has
reached either the destination node or the closest
predecessor node within level xR. Then, as shown in [
Assuming the message has not reached its destination, the message is passed at most once to each of the other upper levels and routed analogously (starting at higher levels first). So we have a total of lmax −1 remaining hops between other upper levels. However, since we know that y is the closest predecessor node to κ in level λ, we can use the expected number of network nodes between any two level λ nodes (some constant c) as an upper bound on the number of nodes on which remain to route over in each level. Thus, we expect at most O(log(c)) routing hops in each remaining level ` > 0, ` 6= λ, giving us an expected total of at most: 2 + 2(lmax − 1)+O(log(x.N )) + (lmax − 2)O(log(c)) ≤2 · lmax + cˆ + O(log(N )) =O(log(N )) for with some constant cˆ.
Note that our simulation results did show an increase in routing hops compared with Chord (1-2 hops), as expected due to the maximum 2·lmax hops up and down the hierarchy. 5.
In order to assess the various approaches’ capabilities to store and retrieve data, we observe node and network lifetimes, the ratio of successfully delivered lookups, and the ratio of forwarded lookup hops per resource level. Additionally, as a reflection of each approach’s suitability to mobile scenarios, we compare the average physical distance of lookup routing hops. We use two simulation configurations, one without node failures and one in which nodes’ resources are drained upon message send and receives, terminating the simulation once half of the nodes have failed (as described in Section 3). We consider here only systems with four resource availability levels (lmax = 3), leaving considerations about the ideal number of resource levels for future work. We compared the HRM overlay with Chord, RBFM, and three two-tier hierarchical overlays based on Chord, RBFM, and HRM. We found the variations caused by different RBFM finger maintenance intervals and stretch constants insignificant compared to the variations between approaches, so we chose to use fixed RBFM configurations.
The simulations were performed in OmNET++ using the
OverSim overlay framework [
The three different two-tier configurations we simulated in order to compare HRM with classical two-tier approaches consist of parent and leaf nodes. Nodes from each of the four resource availability levels are assigned to either a super peer or a leaf peer hierarchical layer. For HRM2:0-123, level 0 nodes are assigned to the leaf layer and level 1,2, and 3 nodes to the super peer layer. Within the super peer layer, nodes are unaware of their varying resource levels and choose their fingers based only on physical distance. Similarly, HRM2:0123 assigns level 0 and 1 nodes to the leaf layer and level 2 and 3 nodes to the super peer layer.
In order to add additional resource awareness, we combine HRM with RBFM to obtain a hybrid solution: in HRM2:0123 with RBFM nodes are again arranged with level 0 nodes in the leaf layer and level 1,2, and 3 nodes in the super peer layer. However, here the super nodes are aware of their different resource levels and choose fingers in a resource and location aware fashion as in RBFM. Thus, the upper level nodes build a simple RBFM overlay on which the bottom level nodes are hung as leaf nodes. The two-tier simulations were configured with linear finger maintenance and for HRM2:0-123 with RBFM using the stretch constant c = 90.
Further simulation configurations include: a relatively
infrequent finger maintenance period of 120 seconds for Chord
for reduced load, an RBFM overlay with quadratic finger
maintenance and stretch constant 90 (RBFM:Q90) (see [
The lifetimes of each of the systems before half of its nodes fail, as shown in Figure 4, vary strongly. Despite a very infrequent finger maintenance interval for Chord, set here intentionally to 240 seconds to reduce maintenance load, it cannot compare to the alternative approaches. Note that these results depend on the varying maintenance loads which we do not further discuss for the sake of brevity, but which produce a major portion of network load. Note that while HRM4 performs significantly better than RBFM, the two-tier approaches perform even better, most likely due to the higher average hop length of lookups in HRM (approximately one hop more per lookup). While Figure 4 demonstrates how well the traditional two tier approaches prolong node lifetimes, Figure 5 shows that these two-tier approaches’ performance suffers given high failure rates, reducing the success rate of lookups to under 65%. Considering only the node and network lifetimes together with the percentage of delivered lookups, RBFM and HRM4 clearly outperform the other approaches, with HRM4 providing the longer lifetimes.
Figures 5 and 6 also provide an overview of the lookup hop load distribution among the resource levels with and without node failures. Only successful lookups are included in these figures. Figure 6 clearly shows how strongly each approach prefers a single resource level for its lookup hops and demonstrates how important it is to design an overlay with the nodes’ resource availabilities in mind. For example, RBFM’s lookup hop distribution is more suitable for networks in which top level nodes can handle unlimited load while HRM4 is more suitable for systems with strong nodes in level 2 that should be used to reduce top level load.
Average lookup lengths ranged from 6.5 to 8.5 hops, with the hierarchical approaches tending to have around one hop more than the other approaches, presumably from the final and/or initial hops to and from leaf nodes. Note the high load on level 1 nodes for the two-tier approach HRM2:0-123 in Figure 6. We infer that this causes a high rate of node movement between the super peer and leaf layers, triggering HRM2:0-123’s low deliverabiliy rate. Similarly, HRM4 distributes more load to level 2 nodes at the cost of their average lifetimes (relative to the other levels) as seen in Figure 4.
The average physical distance of single lookup hops shown in Figure 7 reflects what we expect of the approaches’ routing hops’ distances: while RBFM:Q90 has a large pool of nodes from which to choose links with strong and physically close nodes, HRM4’s nodes have less choice for their links which are drawn from specific (less populated) hierarchical layers. HRM4 actually performs only slightly more locationaware than the completely location-naive Chord - reducing its usability for mobile network scenarios with ad hoc routing where location-awareness is integral: multi-tiered hierarchical approaches for MANETs require additional locationawareness such as PIS or PRS. On the other hand, level 2 and 3 nodes in HRM2:01-23 choose links from these two upper levels based only on distance, providing upper nodes with physically close links. Thus, depending on the tolerable lookup failure rate and desired distribution of load between the upper level nodes, HRM2:01-23 and RBFM are best suited for systems where the physical routing distance plays a central role.
Several novel and established location and resource aware overlay protocols were compared in this paper using two very specific scenarios. While the multi-tiered hierarchical approach HRM4 provided the best combination of node lifetime and lookup deliverability, its location-awareness is not suitable for MANETs without the further integration of PIS or PRS (proximity-aware identifier/route selection). RBFM demonstrated the most stable behavior with respect to node lifetime, lookup deliverability, and location-awareness, often outperforming two-tiered approaches. The two-tier approaches performed well on many measures, but failed to provide the robustness required for a system with high churn rates. Thus, the improvement of these approaches’ robustness could provide promising resource and location aware alternatives. The evaluation’s observations build a foundation for future work with more complicated and realistic scenarios, for example with upper bounds on the permissible load per time unit for varying resource levels, or the development of protocol-specific replication geared toward each approach’s specific strengths and weaknesses.