MapReduce is a software framework for processing data-intensive applications with a parallel manner in cloud computing systems. Some MapReduce jobs have the deadline requirements for their job execution. The existing deadline-constrained MapReduce scheduling schemes do not consider the following two problems: various node performance and dynamical task execution time. In this paper, we utilize the Bipartite Graph modelling to propose a new MapReduce Scheduler called the BGMRS. The BGMRS can obtain the optimal solution of the deadline-constrained scheduling problem by transforming the problem into a well-known graph problem: minimum weighted bipartite matching. The BGMRS has the following features. It considers the heterogeneous cloud computing environment, such that the computing resources of some nodes cannot meet the deadlines of some jobs. In addition to meeting the deadline requirement, the BGMRS also takes the data locality into the computing resource allocation for shortening the data access time of a job. However, if the total available computing resources of the system cannot satisfy the deadline requirements of all jobs, the BGMRS can minimize the number of jobs with the deadline violation. Finally, both simulation and testbed experiments are performed to demonstrate the effectiveness of the BGMRS in the deadline-constrained scheduling.

MapReduce is a software framework for processing data-intensive applications with a parallel manner in cloud computing systems. There are also an increasing number of MapReduce jobs that require deadline guarantees. The existing deadline-concerning scheduling schemes do not consider the two problems in the MapReduce computing environment: slot performance heterogeneity and job time variation. In this paper, we utilize the Bipartite Graph modeling to propose a new MapReduce Scheduler called the BGMRS. The BGMRS can obtain the optimal solution of the deadline-constrained scheduling problem by transforming the problem into a well-known graph problem: minimum weighted bipartite matching. The BGMRS has the following features. It considers the heterogeneous cloud computing environment, such that the computing resources of some nodes cannot meet the deadlines of some jobs. As the job progresses, the BGMRS can dynamically find different computing resources for running the job without violating the job deadline. This is beneficial in the computing resource utilization. The BGMRS can also trade the data locality off against the deadline to make more jobs with deadline guarantees. If the available computing resources of the system cannot meet all job deadlines, the BGMRS can minimize the number of jobs with the deadline violation. Finally, simulation experiments are performed to demonstrate the effectiveness of the BGMRS in the deadline-constrained scheduling.

Cloud computing provides scalable computing and storage resources. More and more data-intensive applications are developed in this computing environment. Different applications have different quality-of-service (QoS) requirements. To continuously support the QoS requirement of an application after data corruption, we propose two QoS-aware data replication (QADR) algorithms in cloud computing systems. The first algorithm adopts the intuitive idea of high-QoS first-replication (HQFR) to perform data replication. However, this greedy algorithm cannot minimize the data replication cost and the number of QoS-violated data replicas. To achieve these two minimum objectives, the second algorithm transforms the QADR problem into the well-known minimum-cost maximum-flow (MCMF) problem. By applying the existing MCMF algorithm to solve the QADR problem, the second algorithm can produce the optimal solution to the QADR problem in polynomial time, but it takes more computational time than the first algorithm. Moreover, it is known that a cloud computing system usually has a large number of nodes. We also propose node combination techniques to reduce the possibly large data replication time. Finally, simulation experiments are performed to demonstrate the effectiveness of the proposed algorithms in the data replication and recovery.

Abstract This paper presents an efficient route recovery approach for a collaborative mobilead hocnetwork (MANET). In the collaborative MANET, the movement of a node can be controlled by other nodes. Based on the property of the controllable movement, each active node (each node on a route) can be protected by its neighboring nodes. When the movement of an active node causes a link breakage on a route, its neighboring nodes compete with each other to move to the original location of the moving active node. Using the movements of neighboring nodes, the proposed approach can achieve route recovery without pre‐establishing or dynamically finding backup routes. The proposed approach also has much less recovery overhead than previous approaches because of the local recovery. Finally, we perform extensive simulations to compare the proposed approach with previous approaches. The simulation results show that the proposed approach has better recovery performance under dense and sparse MANET architectures. Copyright © 2010 John Wiley & Sons, Ltd.

This paper presents an efficient approach for improving file availability in super-peer-based peer-to-peer (P2P) file-sharing systems. In the super-peer-based P2P file-sharing system, peers are organized into multiple groups. In each group, there is a special peer called super-peer to serve the regular peers within the same group. With this property, the proposed approach utilizes the super-peer to tolerate the departure (failure) of a regular peer in order to protect shared files. Unlike traditional replication-based approaches, the proposed approach keeps track of the file queries in the super-peer to support fault tolerance. The cost of tracking the file queries is much smaller than the cost of replicating the file contents in advance. Furthermore, the proposed approach uses a logical connection technique to consider the departure (failure) of the super-peer. Finally, simulation experiments are performed to quantify the performance and overhead of the proposed approach.

Randomized scheduling is a well-known scheduling algorithm for wireless sensor networks to prolong network lifetime. In this algorithm, sensor nodes are randomly assigned to multiple working subsets. These subsets alternatively perform the sensing tasks for monitoring a sensor filed. In each subset, only a portion of sensor nodes are active. It is difficult to maintain the full sensing coverage and network connectivity in a sensor field. For the network connectivity problem of the randomized scheduling, it has been discussed. In this paper, we propose a distributed approach for assisting the randomized scheduling to provide the full coverage. To efficiently achieve this goal, the proposed approach is divided into two main stages: field partition and coverage improvement. The handling problems of these two stages can be transferred to two geometry problems: Voronoi polygon construction and circle covering. Simulation results show that the proposed approach can significantly improve the coverage quality of the randomized scheduling.

This paper presents an efficient fault-tolerant approach for the super-peers of peer-to-peer (P2P) file sharing systems. In the super-peer based P2P file sharing system, peers are organized into multiple groups. In each group, it has a special peer called super peer to serve the regular peers within the group. In this hierarchical architecture, if the super peer departs (fails), any file queries to its serving regular peers cannot be delivered. In the proposed approach, we propose a multiple publication technique to make each regular peer logically connect with two or more super peers in other groups. If a regular peer finds that its serving super peer cannot work, one of its other connected super peers will be selected as its new serving super peer to continuously process the file queries. To examine the effectiveness of the proposed approach, comprehensive simulations are performed to quantify the performance and overhead of the proposed approach.

Communication-induced checkpointing (CIC) protocols can be used to prevent the domino effect. Among such protocols, those belonging to the index-based category associate checkpoints with sequence numbers in a way that checkpoints with an equal sequence number are ensured to be consistent. Specifically, index-based protocols must cooperate with their underlying indexing methods to achieve their goal. The adopted indexing scheme makes a great impact on the number of forced checkpoint the protocol will take. Moreover, an indexing method exhibit different performance for different degrees of heterogeneity imposed on a distributed system. All existing index-based protocols only employ a fixed indexing scheme, however, and thus cannot suit themselves well for all kinds of computing environments. In this paper, we propose two new indexing techniques that can adjust themselves according to the extent of present system heterogeneity. Those new methods are also justified by a simulation study in the text.

In this paper, we present an efficient route recovery approach for ad hoc networks, which modifies an existing ad hoc routing protocol (AODV) to enhance the recovery capability and reduce the recovery overhead. Under the proposed approach, each node on an active route (each active node) maintains a backup node. Once an active node moves (fails) to result in link breakages in its route, the broken active route can be locally repaired by moving the backup node of the moving (faulty) active only. Unlike previous approaches, the proposed approach does not incur the route discovery overhead. To achieve high recovery capability, the proposed approach also considers the backup node mobility. The backup node mobility is usually ignored on the previous approaches. Finally, we performed extensive simulations to demonstrate the effectiveness of the proposed approach over previous approaches in the recovery capability, overhead, and route length.

Communication-induced checkpointing (CIC) protocols can be used to prevent the domino effect. The fully-informed (FI) protocol proposed in the literature is known as the best CIC protocol so far. In this paper, we investigate some properties of such a protocol. First, we discover that an enhancement adopted by the FI protocol rarely takes effect in practice. In particular, we prove that such an enhancement is invalid over a tree communication network. Moreover, the size of the control information that the FI protocol piggybacks on application messages can be further reduced on such a type of network. Next, we show how to apply the FI protocol to another improved indexing strategy introduced in the literature. The management of a Boolean array in its control information carried on a message must be modified. Finally, we present a simulation study to analyze the properties of the FI protocol.

This work presents an efficient approach to providing mobile multicast with the fault-tolerant capability. In multicast communication, packets can be concurrently sent from a source node to all the members by means of a multicast delivery tree. If a failure occurs in one node (link) of the multicast tree, the faulty tree will be partitioned into several disconnected subtrees. The multicast service for some members will be disrupted. The main goal of This work is to make members immune from failure affection. The proposed approach contains two schemes. The first scheme uses the redundant resources of a mobile network to reconnect the disconnected subtrees. Unlike the traditional approaches, the first scheme does not generate loops. In addition, it can control the maximum delivery delay of the new reconnected multicast tree. The second scheme is issued when the first scheme cannot reconnect all the subtrees based on the network topology support. It extracts the failure-free part of the faulty multicast tree to form a safe multicast subtree. Then, all the members are virtually moved to the delivery range of the safe multicast subtree to continuously receive multicast packets. Finally, the fault-tolerant capability of the proposed approach and its overhead are examined and compared with previous approaches by simulation.

This paper presents the fault tolerance of Mobile IP in wireless systems. Mobile IP can support wireless users with continuous network connections while changing locations. It is achieved by allocating a number of mobility agents (foreign agents and home agents) in the architecture of a wireless system. If a failure occurs in a mobility agent, the wireless users located in the coverage area of the faulty mobility agent will lose their network connections. To tolerate the failures of mobility agents, this paper proposes an efficient approach to maintaining the network connections of wireless users without being affected by the failures. Once detecting a failure in a mobility agent, failure-free mobility agents are dynamically selected to be organized as a backup set to take over the faulty mobility agent. Compared to the previous approaches, the proposed approach does not take any actions against failures during the failure-free period. Besides, the hardware redundancy technique is also not used in the proposed approach. The overhead of the proposed approach is analyzed using the M/G/c/c queuing model. The results show that the proposed approach can effectively resolve the fault-tolerant problem of Mobile IP in wireless systems.

The paper investigates the reliability of Mobile IP in a cellular system. To support the node mobility, a lot of mobility agents are deployed in the packet network of a cellular system to retain the continuous network connectivity while mobile nodes move their locations. If a mobility agent fails, the mobile nodes under its coverage area will be affected. The network connectivity of these mobile nodes will be disrupted. The main goal of this paper is to present an efficient approach to tolerating the failures of mobile agents. Once failures occur in a mobility agent, its in-progress and new-arrival workload can be redirected to other mobility agents. The mobile nodes under the mobility agent's coverage area do not lose their data executive ability. The overhead of the proposed fault-tolerant approach is also measured in terms of the performance degradation on other mobility agents by using an M/G/m/m queueing mode. The analytic results show that the performance degradation is very low if the workloads of the faulty mobility agent are not too heavy.

Domino-Effect Freedom (DEF) is a property stating that unbounded, cascading rollback propagation will not occur during the process of finding a consistent global checkpoint. DEF checkpointing protocols can be classified into two different categories: index-based and model-based. An index-based protocol timestamps local checkpoints with sequence numbers for achieving consistency, while a model-based one prohibits the formation of particular checkpoint and communication patterns in the execution. We explore several characteristics of communication-induced checkpointing protocols with the DEF property. First, we demonstrate that there is no optimal online scalar DEF protocol, in terms of the number of forced checkpoints. Then some techniques for comparing protocols are proposed. We construct some patterns or give formal proofs to compare the performance of both index-based and model-based protocols.