A Cross-Layer Approach to Resource Discovery and Distribution in Mobile ad-hoc Networks Chaiporn Jaikaeo Computer Engineering Kasetsart University, Thailand (+662) 942-8555 Ext 1424 cpj@cpe.ku.ac.th Xiang Cao Computer and Information Sciences University of Delaware, USA (+1) 302-831-1131 cao@cis.udel.edu Chien-Chung Shen Computer and Information Sciences University of Delaware, USA (+1) 302-831-1951 cshen@cis.udel.edu ABSTRACT This paper describes a cross-layer approach to designing robust P2P system over mobile ad-hoc networks. The design is based on simple functional primitives that allow routing at both P2P and network layers to be integrated to reduce overhead. With these primitives, the paper addresses various load balancing techniques. Preliminary simulation results are also presented. Categories and Subject Descriptors C.2.4 [Distributed Systems]: Distributed Applications General Terms Algorithms and design 1. INTRODUCTION Mobile ad-hoc networks (MANETs) consist of mobile nodes that autonomously establish connectivity via multi-hop wireless communications. Without relying on any existing, pre-configured network infrastructure or centralized control, MANETs are useful in situations where impromptu communication facilities are required, such as battlefield communications and disaster relief missions. As MANET applications demand collaborative processing and information sharing among mobile nodes, resource (service) discovery and distribution have become indispensable capabilities. One approach to designing resource discovery and distribution schemes over MANETs is to construct a peer-to-peer (P2P) system (or an overlay) which organizes peers of the system into a logical structure, on top of the actual network topology. However, deploying such P2P systems over MANETs may result in either a large number of flooding operations triggered by the reactive routing process, or inefficiency in terms of bandwidth utilization in proactive routing schemes. Either way, constructing an overlay will potentially create a scalability problem for large-scale MANETs. Due to the dynamic nature of MANETs, P2P systems should be robust by being scalable and adaptive to topology changes. These systems should also provide efficient and effective ways for peers to interact, as well as other desirable application specific features. This paper describes a design paradigm that uses the following two functional primitives to design robust resource discovery and distribution schemes over MANETs. 1. Positive/negative feedback. Query packets are used to explore a route to other peers holding resources of interest. Optionally, advertisement packets are sent out to advertise routes from other peers about available resources. When traversing a route, these control packets measure goodness of the route and leave feedback information on each node along the way to guide subsequent control packets to appropriate directions. 2. Sporadic random walk. As the network topology and/or the availability of resources change, existing routes may become stale while better routes become available. Sporadic random walk allows a control packet to explore different paths and opportunistically discover new and/or better routes. Adopting this paradigm, the whole MANET P2P system operates as a collection of autonomous entities which consist of different types of control packets such as query and advertisement packets. These packets work collaboratively, but indirectly, to achieve common tasks, such as resource discovery, routing, and load balancing. With collaboration among these entities, a MANET P2P system is able to ‘learn" the network dynamics by itself and adjust its behavior accordingly, without the overhead of organizing peers into an overlay. The remainder of this paper is organized as follows. Related work is described in the next section. Section 3 describes the resource discovery scheme. Section 4 describes the resource distribution scheme. The replica invalidation scheme is described in Section 5, followed by it performance evaluation in Section 6. Section 7 concludes the paper. 2. RELATED WORK For MANETs, P2P systems can be classified based on the design principle, into layered and cross-layer approaches. A layered approach adopts a P2P-like [1] solution, where resource discovery is facilitated as an application layer protocol and query/reply messages are delivered by the underlying MANET routing protocols. For instance, Konark [2] makes use of a underlying multicast protocol such that service providers and queriers advertise and search services via a predefined multicast group, respectively. Proem [3] is a high-level mobile computing platform for P2P systems over MANETs. It defines a transport protocol that sits on top of the existing TCP/IP stack, hence relying on an existing routing protocol to operate. With limited control over how control and data packets are routed in the network, it is difficult to avoid the inefficiency of the general-purpose routing protocols which are often reactive and flooding-based. In contrast, cross-layer approaches either relies on its own routing mechanism or augments existing MANET routing algorithms to support resource discovery. 7DS [4], which is the pioneering work deploying P2P system on mobile devices, exploits data locality and node mobility to dissemination data in a single-hop fashion. Hence, long search latency may be resulted as a 7DS node can get data of interest only if the node that holds the data is in its radio coverage. Mohan et al. [5] propose an adaptive service discovery algorithm that combines both push and pull models. Specifically, a service provider/querier broadcasts advertisement/query only when the number of nodes advertising or querying, which is estimated by received control packets, is below a threshold during a period of time. In this way, the number of control packets on the network is constrained, thus providing good scalability. Despite the mechanism to reduce control packets, high overhead may still be unavoidable, especially when there are many clients trying to locate different services, due to the fact that the algorithm relies on flooding, For resource replication, Yin and Cao [6] design and evaluate cooperative caching techniques for MANETs. Caching, however, is performed reactively by intermediate nodes when a querier requests data from a server. Data items or resources are never pushed into other nodes proactively. Thanedar et al. [7] propose a lightweight content replication scheme using an expanding ring technique. If a server detects the number of requests exceed a threshold within a time period, it begins to replicate its data onto nodes capable of storing replicas, whose hop counts from the server are of certain values. Since data replication is triggered by the request frequency alone, it is possible that there are replicas unnecessarily created in a large scope even though only nodes within a small range request this data. Our proposed resource replication mechanism, in contrast, attempts to replicate a data item in appropriate areas, instead of a large area around the server, where the item is requested frequently. 3. RESOURCE DISCOVERY We propose a cross-layer, hybrid resource discovery scheme that relies on the multiple interactions of query, reply and advertisement packets. We assume that each resource is associated with a unique ID1 . Initially, when a node wants to discover a resource, it deploys query packets, which carry the corresponding resource ID, and randomly explore the network to search for the requested resource. Upon receiving such a query packet, a reply packet is generated by the node providing the requested resource. Advertisement packets can also be used to proactively inform other nodes about what resources are available at each node. In addition to discovering the ‘identity" of the node providing the requested resource, it may be also necessary to discover a ‘route" leading to this node for further interaction. To allow intermediate nodes to make a decision on where to forward query packets, each node maintains two tables: neighbor 1 The assumption of unique ID is made for brevity in exposition, and resources could be specified via attribute-value assertions. table and pheromone table. The neighbor table maintains a list of all current neighbors obtained via a neighbor discovery protocol. The pheromone table maintains the mapping of a resource ID and a neighbor ID to a pheromone value. This table is initially empty, and is updated by a reply packet generated by a successful query. Figure 1 illustrates an example of a neighbor table and a pheromone table maintained by node A having four neighbors. When node A receives a query packet searching for a resource, it makes a decision to which neighbor it should forward the query packet by computing the desirability of each of the neighbors that have not been visited before by the same query packet. For a resource ID r, the desirability of choosing a neighbor n, δ(r,n), is obtained from the pheromone value of the entry whose neighbor and resource ID fields are n and r, respectively. If no such entry exists in the pheromone table, δ(r,n) is set to zero. Once the desirabilities of all valid next hops have been calculated, they are normalized to obtain the probability of choosing each neighbor. In addition, a small probability is also assigned to those neighbors with zero desirability to exercise the sporadic random walk primitive. Based on these probabilities, a next hop is selected to forward the query packet to. When a query packet encounters a node with a satisfying resource, a reply packet is returned to the querying node. The returning reply packet also updates the pheromone table at each node on its return trip by increasing the pheromone value in the entry whose resource ID and neighbor ID fields match the ID of the discovered resource and the previous hop, respectively. If such an entry does not exist, a new entry is added into the table. Therefore, subsequent query packets looking for the same resource, when encountering this pheromone information, are then guided toward the same destination with a small probability of taking an alternate path. Since the hybrid discovery scheme neither relies on a MANET routing protocol nor arranges nodes into a logical overlay, query packets are to traverse the actual network topology. In dense networks, relatively large nodal degrees can have potential impacts on this random exploring mechanism. To address this issue, the hybrid scheme also incorporates proactive advertisement in addition to the reactive query. To perform proactive advertisement, each node periodically deploys an advertising packet containing a list of its available resources" IDs. These packets will traverse away from the advertising node in a random walk manner up to a limited number of hops and advertise resource information to surrounding nodes in the same way as reply packets. In the hybrid scheme, an increase of pheromone serves as a positive feedback which indirectly guides query packets looking for similar resources. Intuitively, the amount of pheromone increased is inversely proportional to the distance the reply packet has traveled back, and other metrics, such as quality of the resource, could contribute to this amount as well. Each node also performs an implicit negative feedback for resources that have not been given a positive feedback for some time by regularly decreasing the pheromone in all of its pheromone table entries over time. In addition, pheromone can be reduced by an explicit negative response, for instance, a reply packet returning from a node that is not willing to provide a resource due to excessive workload. As a result, load balancing can be achieved via positive and negative feedback. A node serving too many nodes can either return fewer responses to query packets or generate negative responses. 2 The 3rd International Conference on Mobile Technology, Applications and Systems - Mobility 2006 Figure 1: Example illustrating neighbor and pheromone tables maintained by node A: (a) wireless connectivity around A showing that it currently has four neighbors, (b) A"s neighbor table, and (c) a possible pheromone table of A Figure 2: Sample scenarios illustrating the three mechanisms supporting load-balancing: (a) resource replication, (b) resource relocation, and (c) resource division 4. RESOURCE DISTRIBUTION In addition to resource discovery, a querying node usually attempts to access and retrieve the contents of a resource after a successful discovery. In certain situations, it is also beneficial to make a resource readily available at multiple nodes when the resource can be relocated and/or replicated, such as data files. Furthermore, in MANETs, we should consider not only the amount of load handled by a resource provider, but also the load on those intermediate nodes that are located on the communication paths between the provider and other nodes as well. Hence, we describe a cross-layer, hybrid resource distribution scheme to achieve load balancing by incorporating the functionalities of resource relocation, resource replication, and resource division. 4.1 Resource Replication Multiple replicas of a resource in the network help prevent a single node, as well as nodes surrounding it, from being overloaded by a large number of requests and data transfers. An example is when a node has obtained a data file from another node, the requesting node and the intermediate nodes can cache the file and start sharing that file with other surrounding nodes right away. In addition, replicable resources can also be proactively replicated at other nodes which are located in certain strategic areas. For instance, to help nodes find a resource quickly, we could replicate the resource so that it becomes reachable by random walk for a specific number of hops from any node with some probability, as depicted in Figure 2(a). To realize this feature, the hybrid resource distribution scheme employs a different type of control packet, called resource replication packet, which is responsible for finding an appropriate place to create a replica of a resource. A resource replication packet of type R is deployed by a node that is providing the resource R itself. Unlike a query packet which follows higher pheromone upstream toward a resource it is looking for, a resource replication packet tends to be propelled away from similar resources by moving itself downstream toward weaker pheromone. When a resource replication packet finds itself in an area with sufficiently low pheromone, it makes a decision whether it should continue exploring or turn back. The decision depends on conditions such as current workload and/or remaining energy of the node being visited, as well as popularity of the resource itself. 4.2 Resource Relocation In certain situations, a resource may be required to transfer from one node to another. For example, a node may no longer want to possess a file due to the shortage of storage space, but it cannot simply delete the file since other nodes may still need it in the future. In this case, the node can choose to create replicas of the file by the aforementioned resource replication mechanism and then delete its own copy. Let us consider a situation where a majority of nodes requesting for a resource are located far away from a resource provider, as shown on the top of Figure 2(b). If the resource R is relocatable, it is preferred to be relocated to another area that is closer to those nodes, similar to the bottom of the same figure. Hence network bandwidth is more efficiently utilized. The 3rd Conference on Mobile Technology, Applications and Systems - Mobility 2006 3 The hybrid resource distribution scheme incorporates resource relocation algorithms that are adaptive to user requests and aim to reduce communication overhead. Specifically, by following the same pheromone maintenance concept, the hybrid resource distribution scheme introduces another type of pheromone which corresponds to user requests, instead of resources. This type of pheromone, called request pheromone, is setup by query packets that are in their exploring phases (not returning ones) to guide a resource to a new location. 4.3 Resource Division Certain types of resources can be divided into smaller subresources (e.g., a large file being broken into smaller files) and distributed to multiple locations to avoid overloading a single node, as depicted in Figure 2(c). The hybrid resource distribution scheme incorporates a resource division mechanism that operates at a thin layer right above all the other mechanisms described earlier. The resource division mechanism is responsible for decomposing divisible resources into sub-resources, and then adds an extra keyword to distinguish each sub-resource from one another. Therefore, each of these sub-resources will be seen by the other mechanisms as one single resource which can be independently discovered, replicated, and relocated. The resource division mechanism is also responsible for combining data from these subresources together (e.g., merging pieces of a file) and delivering the final result to the application. 5. REPLICA INVALIDATION Although replicas improve accessibility and balance load, replica invalidation becomes a critical issue when nodes caching updatable resources may concurrently update their own replicas, which renders replicas held by other nodes obsolete. Most existing solutions to the replica invalidation problem either impose constrains that only the data source could perform update and invalidate other replicas, or resort to network-wide flooding which results in heavy network traffic and leads to scalability problem, or both. The lack of infrastructure supports and frequent topology changes in MANETs further challenge the issue. We apply the same cross-layer paradigm to invalidating replicas in MANETs which allows concurrent updates performed by multiple replicas. To coordinate concurrent updates and disseminate replica invalidations, a special infrastructure, called validation mesh or mesh for short, is adaptively maintained among nodes possessing ‘valid" replicas of a resource. Once a node has updated its replica, an invalidation packet will only be disseminated over the validation mesh to inform other replica-possessing nodes that their replicas become invalid and should be deleted. The structure (topology) of the validation mesh keeps evolving (1) when nodes request and cache a resource, (2) when nodes update their respective replicas and invalidate other replicas, and (3) when nodes move. To accommodate the dynamics, our scheme integrates the components of swarm intelligence to adaptively maintain the validation mesh without relying on any underlying MANET routing protocol. In particular, the scheme takes into account concurrent updates initiated by multiple nodes to ensure the consistency among replicas. In addition, version number is used to distinguish new from old replicas when invalidating any stale replica. Simulation results show that the proposed scheme effectively facilitates concurrent replica updates and efficiently perform replica invalidation without incurring network-wide flooding. Figure 3 depicts the idea of ‘validation mesh" which maintains connectivity among nodes holding valid replicas of a resource to avoid network-wide flooding when invalidating replicas. Figure 3: Examples showing maintenance of validation mesh There are eight nodes in the sample network, and we start with only node A holding the valid file, as shown in Figure 3(a). Later on, node G issues a query packet for the file and eventually obtains the file from A via nodes B and D. Since intermediate nodes are allowed to cache forwarded data, nodes B, D, and G will now hold valid replicas of the file. As a result, a validation mesh is established among nodes A, B, D, and G, as depicted in Figure 3(b). In Figure 3(c), another node, H, has issued a query packet for the same file and obtained it from node B"s cache via node E. At this point, six nodes hold valid replicas and are connected through the validation mesh. Now we assume node G updates its replica of the file and informs the other nodes by sending an invalidation packet over the validation mesh. Consequently, all other nodes except G remove their replicas of the file from their storage and the validation mesh is torn down. However, query forwarding pheromone, as denoted by the dotted arrows in Figure 3(d), is setup at these nodes via the ‘reverse paths" in which the invalidation packets have traversed, so that future requests for this file will be forwarded to node G. In Figure 3(e), node H makes a new request for the file again. This time, its query packet follows the pheromone toward node G, where the updated file can be obtained. Eventually, a new validation mesh is established over nodes G, B, D, E, and H. To maintain a validation mesh among the nodes holding valid replicas, one of them is designated to be the focal node. Initially, the node that originally holds the data is the focal node. As nodes update replicas, the node that last (or most recently) updates a 4 The 3rd International Conference on Mobile Technology, Applications and Systems - Mobility 2006 corresponding replica assumes the role of focal node. We also name nodes, such as G and H, who originate requests to replicate data as clients, and nodes B, D, and E who locally cache passing data as data nodes. For instance, in Figures 3(a), 3(b), and 3(c), node A is the focal node; in Figures 3(d), 3(e), and 3(f), node G becomes the focal node. In addition, to accommodate newly participating nodes and mobility of nodes, the focal node periodically floods the validation mesh with a keep-alive packet, so that nodes who can hear this packet are considered themselves to be part of the validation mesh. If a node holding a valid/updated replica doesn"t hear a keep-alive packet for a certain time interval, it will deploy a search packet using the resource discovery mechanism described in Section 3 to find another node (termed attachment point) currently on the validation mesh so that it can attach itself to. Once an attachment point is found, a search_reply packet is returned to the disconnected node who originated the search. Intermediate nodes who forward the search_reply packet will become part of the validation mesh as well. To illustrate the effect of node mobility, in Figure 3(f), node H has moved to a location where it is not directly connected to the mesh. Via the resource discovery mechanism, node H relies on an intermediate node F to connect itself to the mesh. Here, node F, although part of the validation mesh, doesn"t hold data replica, and hence is termed nondata node. Client and data node who keep hearing the keep-alive packets from the focal node act as if they are holding a valid replica, so that they can reply to query packets, like node B in Figure 3(c) replying a request from node H. While a disconnected node attempting to discover an attachment point to reattach itself to the mesh, the disconnected node can"t reply to a query packet. For instance, in Figure 3(f), node H does not reply to any query packet before it reattaches itself to the mesh. Although validation mesh provides a conceptual topology that (1) connects all replicas together, (2) coordinates concurrent updates, and (3) disseminates invalidation packets, the technical issue is how such a mesh topology could be effectively and efficiently maintained and evolved when (a) nodes request and cache a resource, (b) when nodes update their respective replicas and invalidate other replicas, and (c) when nodes move. Without relying on any MANET routing protocols, the two primitives work together to facilitate efficient search and adaptive maintenance. 6. PERFORMANCE EVALUATION We have conducted simulation experiments using the QualNet simulator to evaluate the performance of the described resource discovery, resource distribution, and replica invalidation schemes. However, due to space limitation only the performance of the replica invalidation is reported. In our experiments, eighty nodes are uniformly distributed over a terrain of size 1000×1000 m2 . Each node has a communication range of approximately 250 m over a 2 Mbps wireless channel, using IEEE802.11 as the MAC layer. We use the random-waypoint mobility model with a pause time of 1 second. Nodes may move at the minimum and maximum speeds of 1 m/s and 5 m/s, respectively. Table 1 lists other parameter settings used in the simulation. Initially, there is one resource server node in network. Two nodes are randomly picked up every 10 seconds as clients. Every β seconds, we check the number of nodes, N, which have gotten data. Then we randomly pickup Min(γ,N) nodes from them to initiate data update. Each experiment is run for 10 minutes. Table 1: Simulation Settings HOP_LIMIT 10 ADVERTISE_HOP_LIMIT 1 KEEPALIVE_INTERVAL 3 second NUM_SEARCH 1 ADVERTISE_INTERVAL 5 second EXPIRATION_INTERVAL 10 second Average Query Generation Rate 2 query/ 10 sec Max # of Concurrent Update (γ) 2 Frequency of Update (β) 3s We evaluate the performance under different mobility speed, the density, the maximum number of concurrent update nodes, and update frequency using two metrics: • Average overhead per update measures the average number of packets transmitted per update in the network. • Average delay per update measures how long our approach takes to finish an update on average. All figures shown present the results with a 70% confidence interval. Figure 4: Overhead vs. speed for 80 nodes Figure 5: Overhead vs. density Figure 6: Overhead vs. max #concurrent updates Figure 7: Overhead vs. freq. Figure 8: Delay vs. speed Figure 9: Delay vs. density The 3rd Conference on Mobile Technology, Applications and Systems - Mobility 2006 5 Figure 10: Delay vs. max #concurrent updates Figure 11: Delay vs. freq. Figures 4, 5, 6, and 7 show the overhead versus various parameter values. In Figure 4, the overhead increases as the speed increase, which is due to the fact that as the speed increase, nodes move out of mesh more frequently, and will send out more search packets. However, the overhead is not high, and even in speed 10m/sec, the overhead is below 100 packets. In contrast, the packets will be expected to be more than 200 packets at various speeds when flooding is used. Figure 5 shows that the overhead almost remains the same under various densities. That is attributed to only flooding over the mesh instead of the whole network. The size of mesh doesn"t vary much on various densities, so that the overhead doesn"t vary much. Figure 6 shows that overhead also almost remains the same under various maximum number of concurrent updates. That"s because one more node just means one more flood over the mesh during update process so that the impact is limited. Figure 7 shows that if updates happen more frequently, the overhead is higher. This is because the more quickly updates happen, (1) there will be more keep_alive message over the mesh between two updates, and (2) nodes move out of mesh more frequently and send out more search packets. Figures 8, 9, 10, and 11 show the delay versus various parameter values. From Figure 8, we know the delay increases as the speed increases, which is due to the fact that with increasing speed, clients will move out of mesh with higher probability. When these clients want to update data, they will spend time to first search the mesh. The faster the speed, the more time clients need to spend to search the mesh. Figure 9 shows that delay is negligibly affected by the density. Delay decreases slightly as the number of nodes increases, due to the fact that the more nodes in the network, the more nodes receives the advertisement packets which helps the search packet find the target so that the delay of update decreases. Figure 10 shows that delay decreases slightly as the maximum number of concurrent updates increases. The larger the maximum number of concurrent updates is, the more nodes are picked up to do update. Then with higher probability, one of these nodes is still in mesh and finishes the update immediately (don"t need to search mesh first), which decreases the delay. Figure 11 shows how the delay varies with the update frequency. When updates happen more frequently, the delay will higher. Because the less frequently, the more time nodes in mesh have to move out of mesh then they need to take time to search the mesh when they do update, which increases the delay. The simulation results show that the replica invalidation scheme can significantly reduce the overhead with an acceptable delay. 7. CONCLUSION To facilitate resource discovery and distribution over MANETs, one approach is to designing peer-to-peer (P2P) systems over MANETs which constructs an overlay by organizing peers of the system into a logical structure on the top of MANETs" physical topology. However, deploying overlay over MANETs may result in either a large number of flooding operations triggered by the routing process, or inefficiency in terms of bandwidth usage. Specifically, overlay routing relies on the network-layer routing protocols. In the case of a reactive routing protocol, routing on the overlay may cause a large number of flooded route discovery message since the routing path in each routing step must be discovered on demand. On the other hand, if a proactive routing protocol is adopted, each peer has to periodically broadcast control messages, which leads to poor efficiency in terms of bandwidth usage. Either way, constructing an overlay will potentially suffer from the scalability problem. The paper describes a design paradigm that uses the functional primitives of positive/negative feedback and sporadic random walk to design robust resource discovery and distribution schemes over MANETs. In particular, the scheme offers the features of (1) cross-layer design of P2P systems, which allows the routing process at both the P2P and the network layers to be integrated to reduce overhead, (2) scalability and mobility support, which minimizes the use of global flooding operations and adaptively combines proactive resource advertisement and reactive resource discovery, and (3) load balancing, which facilitates resource replication, relocation, and division to achieve load balancing. 8. REFERENCES [1] A. Oram, Peer-to-Peer: Harnessing the Power of Disruptive Technologies. O"Reilly, March 2000. [2] S. Helal, N. Desai, V. Verma, and C. Lee, Konark - A Service Discovery and Delivery Protocol for ad-hoc Networks, in the Third IEEE Conference on Wireless Communication Networks (WCNC), New Orleans, Louisiana, 2003. [3] G. Krotuem, Proem: A Peer-to-Peer Computing Platform for Mobile ad-hoc Networks, in Advanced Topic Workshop Middleware for Mobile Computing, Germany, 2001. [4] M. Papadopouli and H. Schulzrinne, A Performance Analysis of 7DS a Peer-to-Peer Data Dissemination and Prefetching Tool for Mobile Users, in Advances in wired and wireless communications, IEEE Sarnoff Symposium Digest, Ewing, NJ, 2001, (Best student paper & poster award). [5] U. Mohan, K. Almeroth, and E. Belding-Royer, Scalable Service Discovery in Mobile ad-hoc Networks, in IFIP Networking Conference, Athens, Greece, May 2004. [6] L. Yin and G. Cao, Supporting Cooperative Caching in Ad Hoc Networks, in IEEE INFOCOM, 2004. [7] V. Thanedar, K. Almeroth, and E. Belding-Royer, A Lightweight Content Replication Scheme for Mobile ad-hoc Environments, in IFIP Networking Conference, Athens, Greece, May 2004. 6 The 3rd International Conference on Mobile Technology, Applications and Systems - Mobility 2006
manet hybrid discovery scheme neighbor discovery protocol negative feedback query packet replica invalidation validation mesh invalidation packet route discovery message concurrent update resource discovery
manet p2p system manet routing protocol mobile ad-hoc network