Open Access Open Access  Restricted Access Subscription or Fee Access

Anti-Message Logging based Checkpointing Scheme for Mobile Ad Hoc Networks

F. Praveen, S. Parveen Kumar

Abstract


Ad-hoc networks are a new paradigm of wireless communication for mobile hosts. There is no fixed infrastructure such as base stations. Fault-tolerance is an important design issue in building a reliable Ad hoc network. In this paper we propose a new anti-message logging based non-intrusive minimum process checkpointing scheme for ad hoc networks. We assume that it uses Cluster Based Routing Protocol (CBRP) which belongs to a class of Hierarchical Reactive routing protocols. It produces a consistent set of checkpoints; the algorithm makes sure that only minimum number of nodes in the cluster is required to take checkpoints; it uses very few control messages.

Keywords


Fault Tolerance, Consistent Global State, Coordinated Checkpointing, Mobile Systems and Ad Hoc Networks.

Full Text:

PDF

References


Acharya A. and Badrinath B. R., “Checkpointing Distributed Applications on Mobile Computers,” Proceedings of the 3rd International Conference on Parallel and Distributed Information Systems, pp. 73-80, September 1994.

Cao G. and Singhal M., “On coordinated checkpointing in Distributed Systems”, IEEE Transactions on Parallel and Distributed Systems, vol. 9, no.12, pp. 1213-1225, Dec 1998.

Cao G. and Singhal M., “On the Impossibility of Min-process Non-blocking Checkpointing and an Efficient Checkpointing Algorithm for Mobile Computing Systems,” Proceedings of International Conference on Parallel Processing, pp. 37-44, August 1998.

Cao G. and Singhal M., “Mutable Checkpoints: A New Checkpointing Approach for Mobile Computing systems,” IEEE Transaction On Parallel and Distributed Systems, vol. 12, no. 2, pp. 157-172, February 2001.

Chandy K. M. and Lamport L., “Distributed Snapshots: Determining Global State of Distributed Systems,” ACM Transaction on Computing Systems, vol. 3, No. 1, pp. 63-75, February 1985.

Elnozahy E.N., Alvisi L., Wang Y.M. and Johnson D.B., “A Survey of Rollback-Recovery Protocols in Message-Passing Systems,” ACM Computing Surveys, vol. 34, no. 3, pp. 375-408, 2002.

Elnozahy E.N., Johnson D.B. and Zwaenepoel W., “The Performance of Consistent Checkpointing,” Proceedings of the 11th Symposium on Reliable Distributed Systems, pp. 39-47, October 1992.

Koo R. and Toueg S., “Checkpointing and Roll-Back Recovery for Distributed Systems,” IEEE Trans. on Software Engineering, vol. 13, no. 1, pp. 23-31, January 1987.

Neves N. and Fuchs W. K., “Adaptive Recovery for Mobile Environments,” Communications of the ACM, vol. 40, no. 1, pp. 68-74, January 1997.

Parveen Kumar, Lalit Kumar, R K Chauhan, V K Gupta “A Non-Intrusive Minimum Process Synchronous Checkpointing Protocol for Mobile Distributed Systems” Proceedings of IEEE ICPWC-2005, pp 491-95, January 2005.

Prakash R. and Singhal M., “Low-Cost Checkpointing and Failure Recovery in Mobile Computing Systems,” IEEE Transaction On Parallel and Distributed Systems, vol. 7, no. 10, pp. 1035-1048, October1996.

J.L. Kim, T. Park, “An efficient Protocol for checkpointing Recovery in Distributed Systems,” IEEE Trans. Parallel and Distributed Systems, pp. 955-960, Aug. 1993.

Ni, W., S. Vrbsky and S. Ray, “Pitfalls in Distributed Nonblocking Checkpointing”, Journal of Interconnection Networks, Vol. 1 No. 5, pp. 47-78, March 2004.

L. Lamport, “Time, clocks and ordering of events in a distributed system” Comm. ACM, vol.21, no.7, pp. 558-565, July 1978.

Silva, L.M. and J.G. Silva, “Global checkpointing for distributed programs”, Proc. 11th symp. Reliable Distributed Systems, pp. 155-62, Oct. 1992.

David R. Jefferson, “Virtual Time”, ACM Transactions on Programming Languages and Systems, Vol. 7, NO.3, pp 404-425, July 1985.

Johnson, D.B., Zwaenepoel, W., “ Sender-based message logging”, In Proceedingss of 17th international Symposium on Fault-Tolerant Computing, pp 14-19, 1987.

Johnson, D.B., Zwaenepoel, W., “Recovery in Distributed Systems using optimistic message logging and checkpointing. pp 171-181, 1988.

Parveen Kumar, Lalit Kumar, R K Chauhan, “A Non-intrusive Hybrid Synchronous Checkpointing Protocol for Mobile Systems”, IETE Journal of Research, Vol. 52 No. 2&3, 2006.

Pushpendra Singh, Gilbert Cabillic, “A Checkpointing Algorithm for Mobile Computing Environment”, LNCS, No. 2775, pp 65-74, 2003.

Lalit Kumar Awasthi, P.Kumar, “A Synchronous Checkpointing Protocol for Mobile Distributed Systems: Probabilistic Approach” International Journal of Information and Computer Security, Vol.1, No.3 pp 298-314.

Parveen Kumar, “A Low-Cost Hybrid Coordinated Checkpointing Protocol for Mobile Distributed Systems”, Mobile Information Systems [An International Journal from IOS Press, Netherlands] pp 13-32, Vol. 4, No. 1, 2007.

Murthy & Manoj, “Ad hoc Wireless Networks Architectures and Protocols”, Pearson Education, 2004.

D.J. Baker and A. Ephremides, “The Architectural Organisation of a Mobile Radio Network via a Distributed algorithm”, IEEE Trans. Commun., vol. 29, no. 11, pp 1694-1701, Nov., 1981

D.J. Baker, A. Ephremides and J.A. Flynn “The design and Simulation of a Mobile Radio Network with Distributed Control”, IEEE J. sel. Areas Commun.., pp 226-237, 1984

B.Das, R. Sivakumar and V. Bharghavan, “Routing in Ad-hoc networks using a Spine”,Proc. Sixth International Conference, 1997.

B.Das, R. Sivakumar and V. Bharghavan, “Routing in Ad-hoc networks using Minimum connected Dominating Sets”,Proc. IEEE International Conference, 1997.

M.Gerla, G. Pei, and S.J. Lee, “Wireless Mobile Ad-hoc Network Routing”, Proc. IEEE/ACM FOCUS‟99, 1999.

M. Singhal and N. Shivaratri, Advanced Concepts in Operating Systems, New York, McGraw Hill, 1994.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.