Research On Key Techniques Of Rollback Recovery In Mobile Computing Environment

With the development of the wireless networks and mobile computing devices, mobile computing has been highly regarded and widely researched. It is considered as one of the main directions in the IT field. Due to the unreliable mobile hosts and fragile network connections, it is significant to research on the fault tolerance of the mobile systems. Checkpointing and Rollback-Recovery (CRR), as an effective software-implemented fault tolerant technique, has the virtues of easy implementation with less resource requirements, and therefore becomes a promising paradigm for the mobile computing environment.The existing CRR algorithms developed for the distributed systems can not directly be used to the mobile computing environment because of the limited resources of the embedded mobile computing devices, such as wearable computers, PDAs or sensor nodes. This dissertation includes comprehensive approaches on CRR to reduce the storage cost and the communication cost of checkpointing and message logging, to enhance the autonomy of mobile hosts and to implement the transparent recovery.Process checkpoint is essential in the CRR study. Reducing the overhead of the Process checkpoint is a key factor in reliability design. Two checkpoint interval optimization schemes,the step-checkpointing and the memory threshold-control checkpointing,are presented. Both of them are feasible to the OS kernel-level rollback recovery mechanism. In the step-checkpointing scheme, checkpoint intervals are modulated on-line according to the characteristic of software or hardware environment-dependent system that the failure rate fluctuates acutely shortly after the system fails. On the other hand, checkpoint size monitoring and threshold-control checkpoint adjusts the checkpoint interval by predicting the amount of data to be saved. Combining these two schemes can effectively improve the performance of the embedded mobile computer system.Asynchronous rollback and recovery is suitable for the mobile hosts which move across cells and disconnect from the wireless networks from time to time. A novel rollback recovery algorithm applicable to mobile environment based on casual message logging is presented and the consistency of the system is formally proven. This algorithm takes advantage of Antecedence Graph to trace the message dependency of mobile hosts. Simultaneously, the storage of uncoordinated checkpoint, volatile sender-based message log and Antecedence Graph information is carried out on the Mobile Support Station in order that the mobile hosts can gain transparent fault tolerant service. The simulation result shows: the causal message logging algorithm has the minimized rollback cost and less communication and storage cost in the failure free phase comparing to those of the optimistic message logging and pessimistic message logging.By casual message logging, processes can rolls back asynchronously. But in the large-scale mobile environments, the traditional causal message logging has the disadvantage of high communication and storage cost. This paper presents a hierarchical casual message logging protocol MC_HCML. The casual dependency relations of the mobile host in the same cell are logged in the volatile storage of the Mobile Support Station with the format of the incremental Antecedence Graph and are shared among MSSs. The simulation result shows that MC_HCML has less communication cost and storage cost in the failure-free phase and the rollback recovery phase comparing to the node-level casual message logging and optimistic message loggingA Quasi-Synchronous checkpoiting algorithm with Selective Message Logging(QSC_SMLA) is presented for heterogeneous mobile networks. The stable optimized message logs are selectively stored in the mobile support stations to maintain the consistency of the whole mobile system while the inherent checkpoint interval of each kind of nodes are kept unchanged. The performance evaluation and simulation result shows that QSC_SMLA has lower checkpoint cost on the mobile hosts and lower communication cost and storage cost on the mobile support stations comparing to the traditional communication induced checkpointing and synchronized checkpointing. This algorithm is considered as a feasible solution for the heterogeneous mobile networks consisted of nodes with limited computing and communication resources.