14525964
Adaptive strategies for efficiently locating internet-based servers in MANETs
Providing Internet access to Mobile Ad hoc Networks (MANETs) can greatly extend their applications, increase their scalability, and improve the quality of service. However, a critical problem is how the mobile hosts can locate Internet-based servers efficiently in a dynamic, unstructured network. Neither reactive strategies, where the hosts initiate on-demand server discovery, nor proactive strategies, where the servers periodically advertise their availability information, are optimal. To that end, this paper studies adaptive strategies that (1) combine both proactive advertising by the servers and on-demand discovery by the mobile hosts, and (2) determine the relative rate of proactive advertising and on-demand discovery adaptively according to the network characteristics including the host mobility level and the offered load. We propose and evaluate two novel, integrated algorithms. First, to determine the rate of proactive advertising, we propose an exponential backoff algorithm to probe the optimal operating point. Second, to reduce the network traffic due to reactive (on-demand) discovery, we propose a novel controlled flooding algorithm. Our simulation study reveals that, compared to the previous proactive strategies and reactive strategies, our adaptive strategies reduce network traffic for locating the servers by several times when the network has a moderate offered load and a low or high level of host mobility.
16906364
Scalable and Robust Aggregation Techniques for Extracting Statistical Information in Sensor Networks
Wireless sensor networks have stringent constraints on system resources and data aggregation techniques are critically important. However, accurate data aggregation is difficult due to the variation of sensor readings and due to the frequent communication failures. To address these difficulties, we propose a scalable and robust data aggregation algorithm. The novelty of our work includes two aspects. First, our algorithm exploits the mixture model and the Expectation Maximization (EM) algorithm for parameter estimation. Hence, it captures the effects of aggregation over different scales while keeping the communication cost low. Second, our algorithm exploits loss-tolerant multi-path routing schemes. Hence, it obtains accurate statistical information even in the presence of high link and node failure rates. We demonstrate that our techniques reduce communication cost while retaining the precious statistical information otherwise neglected by other aggregation techniques. Our evaluation shows the proposed techniques are robust against link and node failures, and perform consistently well.
18051966
Design and analysis of adaptive strategies for locating internet-based servers in MANETs
A critical problem in providing Internet access to Mobile Ad Hoc Networks (MANETs) is how the mobile hosts can locate Internet-based servers efficiently in a dynamic, unstructured network. This paper studies adaptive strategies that combine both proactive advertising by the servers and on-demand discovery by the mobile hosts. The adaptive strategies determine the relative rate of proactive advertising and on-demand discovery according to system characteristics such as host mobility level and offered load. Our simulation study reveals that, compared to the previous proactive strategies and reactive strategies, the adaptive strategies reduce network traffic by several times when the network has a moderate offered load and a low or high level of host mobility.
7586381
Dynamic Load Balancing for I/O-Intensive Tasks on Heterogeneous Clusters
Since I/O-intensive tasks running on a heterogeneous cluster need a highly effective usage of global I/O resources, previous CPU- or memory-centric load balancing schemes suffer significant performance drop under I/O-intensive workload due to the imbalance of I/O load. To solve this problem, we develop two I/O-aware load-balancing schemes, which consider system heterogeneity and migrate more I/O-intensive tasks from a node with high I/O utilization to those with low I/O utilization. If the workload is memory-intensive in nature, the new method applies a memory-based load balancing policy to assign the tasks. Likewise, when the workload becomes CPU-intensive, our scheme leverages a CPU-based policy as an efficient means to balance the system load. In doing so, the proposed approach maintains the same level of performance as the existing schemes when I/O load is low or well balanced. Results from a trace-driven simulation study show that, when a workload is I/O-intensive, the proposed schemes improve the performance with respect to mean slowdown over the existing schemes by up to a factor of 8. In addition, the slowdowns of almost all the policies increase consistently with the system heterogeneity.
20068677
A case study of parallel I/O for biological sequence search on Linux clusters
In this paper we analyze the I/O access patterns of a widely-used biological sequence search tool and implement two variations that employ parallel-I/O for data access based on PVFS (Parallel Virtual File System) and CEFT-PVFS (cost-effective fault-tolerant PVFS). Experiments show that the two variations outperform the original tool when equal or even fewer storage devices are used in the former. It is also found that although the performance of the two variations improves consistently when initially increasing the number of servers, this performance gain from parallel I/O becomes insignificant with further increase in server number. We examine the effectiveness of two read performance optimization techniques in CEFT-PVFS by using this tool as a benchmark. Performance results indicate: (1) doubling the degree of parallelism boosts the read performance to approach that of PVFS; and (2) skipping hot-spots can substantially improve the I/O performance when the load on data servers is highly imbalanced. The I/O resource contention due to the sharing of server nodes by multiple applications in a cluster has been shown to degrade the performance of the original tool and the variation based on PVFS by up to 10 and 21 folds, respectively; whereas, the variation based on CEFT-PVFS only suffered a two-fold performance degradation.
7218297
Improving effective bandwidth of networks on clusters using load balancing for communication-intensive applications
Clusters have emerged as a primary and cost-effective infrastructure for parallel applications, including communication-intensive applications that transfer a large amount of data among nodes of a cluster via interconnection networks. Conventional load balancers have been proven effective in increasing utilization of CPU, memory, and disk I/O resources in a cluster. However, most of the existing load-balancing schemes ignore network resources, leaving open an opportunity for improving effective bandwidth of networks on clusters running parallel applications. For this reason, we propose a communication-aware load balancing technique that is capable of improving performance of communication-intensive applications by increasing effective utilization of networks in cluster environments. Our load-balancing scheme can make use of an application model to quickly and accurately determine the load induced by a variety of parallel applications. Simulation results on executing a wide range of parallel applications on a cluster show that the proposed scheme can significantly improve the performance in slowdown and turn-around time over three existing schemes by up to 206% (with an average of 74%) and 235% (with an average of 82%), respectively.
18773100
An Approach to Broaden the Semantic Coverage of ACL Speech Acts
Current speech-act based ACLs specify domain-independent information about communication and relegate domain-dependent information to an unspecified content language. This is reasonable, but the ACLs cover only a small fraction of the domain-independent information possible. As a key element of modern ACLs, the set of communicative acts needs to be as complete as possible to enable agents to communicate the widest range of information with agreed-upon semantics. This paper describes a new approach to broaden the semantic coverage of ACL speech acts. It provides agents with the ability to express more of the possible meanings in human languages and yields a more powerful ACL. Specifically, we first compare Austin's and Searle's classifications, and Ballmer and Brennenstuhl's comprehensive classification of speech acts. The main meaning categories and their semantics are given next. Finally, a multifaceted evaluation of our approach is presented, which points out that the approach potentially can combine the benefits of the FIPA ACL with Ballmer and Brennenstuhl's speech act classification, resulting in a more expressive ACL.
12626958
False Rate Analysis of Bloom Filter Replicas in Distributed Systems
Bloom filters have been widely used in distributed systems where they are replicated to process distributed queries. Bloom filter replicas become stale in a dynamic environment. A good understanding of the impact of staleness on false negatives and false positives can provide the system designers with important insights into the development and deployment of distributed Bloom filters in many distributed systems. To our best knowledge, this paper is the first one that analyzes the probabilities of false negatives and positives by developing analytical models, which take the staleness into consideration. Based on the theoretical analysis, we proposed an updating protocol that directly control the false rate. Extensive simulations validate the analytical models and prove the updating protocol to be very accurate and effective