Context-aware fault tolerance in migratory services

ABSTRACT

Mobile ad hoc networks can be leveraged to provide ubiquitous services capable of acquiring, processing, and sharing real-time information from the physical world. Unlike Internet services, these services have to survive frequent and unpredictable faults such as disconnections, crashes, or users turning off their devices. This paper describes a context-aware fault tolerance mechanism for our migratory services model. In this model, a per-client service instance transparently migrates to different nodes in the network to provide a continuous and semantically-correct interaction with its client. The proposed fault tolerance mechanism extends the primary-backup approach with a context-aware checkpointing process. The backup node is dynamically selected based on its distance from the client and service, the similarity of its mobility pattern with those of the client and service, the frequency of the checkpointing process, and the size of the checkpointing state.

We demonstrate the feasibility of our approach through a prototype implementation tested in a small scale ad hoc network of smart phones. Additionally, we simulate our mechanism in a realistic urban environment with 300 pedestrians, cyclists, and cars. Compared to approaches where the backup node is a neighbor of the service node or the client node itself, our mechanism performs as much as 80% better than the former for recovery ratio, and three times better than the latter for network overhead, while achieving better or similar recovery latency.

References

1. A. Acharya and B. R. Badrinath. Checkpointing distributed applications on mobile computers. In Proceedings of the 3rd International Conference on Parallel and Distributed Information Systems (PDIS'94), pages 73--80. IEEE Computer Society Press, 1994.
2. L. Alvisi, T. C. Bressoud, A. El-Khashab, K. Marzullo, and D. Zagorodnov. Wrapping Server-Side TCP to Mask Connection Failures. In Proceedings of INFOCOM'01, pages 329--337, 2001.
3. N. Budhiraja, K. Marzullo, F. B. Schneider, and S. Toueg. The primary-backup approach. In S. Mullender, editor, Distributed systems (2nd Ed.), pages 199--216. ACM Press/Addison-Wesley, 1993.
4. G. Cao and M. Singhal. Mutable checkpoints: A new checkpointing approach for mobile computing systems. IEEE Trans. Parallel Distrib. Syst., 12(2):157--172, 2001.
5. R. Chandra, V. Ramasubramanian, and K. Birman. Anonymous Gossip: Improving Multicast Reliability in Mobile Ad-Hoc Networks. In Proceedings of the 21th IEEE International Conference on Distributed Computing Systems (ICDCS'01), pages 275--283, 2001.
6. F. Cristian. Understanding fault-tolerant distributed systems. Communications of the ACM, 34(2):56--78, February 1991.
7. T. Gopalsamy, M. Singhal, D. Panda, and P. Sadayappan. A Reliable Multicast Algorithm for Mobile Ad Hoc Networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS'02), pages 563--570, July 2002.
8. R. Grimm, J. Davis, E. Lemar, A. Macbeth, S. Swanson, T. Anderson, B. Bershad, G. Borriello, S. Gribble, and D. Wetherall. System Support for Pervasive Applications. ACM Trans. Comput. Syst., 22(4):421--486, 2004.
9. S. K. Gupta and P. K. Srimani. An Adaptive Protocol for Reliable Multicast in Mobile Multi-hop Radio Networks. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99), page 111, 1999.
10. R. Handorean, R. Sen, G. Hackmann, and G.-C. Roman. Context Aware Session Management for Services in Ad Hoc Networks. In Proceedings of the 2005 IEEE International Conference on Services Computing (SCC'05), pages 113--120, July 2005.
11. P. Kang, C. Borcea, G. Xu, A. Saxena, U. Kremer, and L. Iftode. Smart Messages: A Distributed Computing Platform for Networks of Embedded Systems. The Computer Journal, pages 475--494, 2004. The British Computer Society. Oxford University Press.
12. B. Karp and H. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'00), pages 243--254, August 2000.
13. R. Leung, J. Liu, E. Poon, A.-L. C. Chan, and B. Li. MP-DSR: A QoS-Aware Multi-Path Dynamic Source Routing Protocol for Wireless Ad-Hoc Networks. In Proceedings of the 26th Annual IEEE Conference on Local Computer Networks (LCN'01), pages 132--141, 2001.
14. J. Luo, P. Eugster, and J. Hubaux. Pilot: Probabilistic lightweight group communication system for ad hoc networks. IEEE Transactions on Mobile Computing, 3(2):164--179, April 2004.
15. J. Luo, P. T. Eugster, and J.-P. Hubaux. Route Driven Gossip: Probabilistic Reliable Multicast in Ad Hoc Networks. In Proceedings of INFOCOM'03, pages 2229--2239, March 30 - April 3 2003.
16. M. Marwah, S. Mishra, and C. Fetzer. TCP Server Fault Tolerance Using Connection Migration to a Backup Server. In Proceedings of the International Conference on Dependable Systems and Networks (DSN'03), page 373, 2003.
17. J. Nzouonta, N. Rajgure, G. Wang, and C. Borcea. VANET routing on city roads using real-time vehicular traffic information. Under Submission, December 2007.
18. Öznur Özkasap, Z. Genç;, and E. Atsan. Epidemic-based approaches for reliable multicast in mobile ad hoc networks. SIGOPS Oper. Syst. Rev., 40(3):73--79, 2006.
19. E. Pagani. Providing reliable and fault tolerant broadcast delivery in mobile ad-hoc networks. Mob. Netw. Appl., 4(3):175--192, 1999.
20. C. Perkins and E. Royer. Ad-Hoc On-Demand Distance Vector Routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA'99), pages 90--100, 1999.
21. N. Ravi, C. Borcea, P. Kang, and L. Iftode. Portable Smart Messages for Ubiquitous Java-Enabled Devices. In Proceedings of the 1st Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04), pages 412--421. IEEE Computer Society, 2004.
22. O. Riva, T. Nadeem, C. Borcea, and L. Iftode. Context-aware Migratory Services in Ad Hoc Networks. IEEE Transactions on Mobile Computing, 6(12):1313--1328, December 2007.
23. G. Shenoy, S. K. Satapati, and R. Bettati. HYDRANET-FT: Network Support for Dependable Services. In Proceedings of the the 20th IEEE International Conference on Distributed Computing Systems (ICDCS'00), page 699, April 2000.
24. A. Shieh, A. C. Myers, and E. G. Sirer. Trickles: A Stateless Network Stack for Improved Scalability, Resilience and Flexibility. In Proceedings of the 2nd USENIX Symposium on Networked Systems Design and Implementation (NSDI'05), pages 175--188, May 2005.
25. F. Sultan, K. Srinivasan, D. Iyer, and L. Iftode. Migratory TCP: Connection Migration for Service Continuity in the Internet. In Proceedings of the 22nd IEEE International Conference on Distributed Computing Systems (ICDCS'02), page 469, July 2002.
26. J. Tang, G. Xue, and W. Zhang. Reliable routing in mobile ad hoc networks based on mobility prediction. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS'04), pages 466--474. IEEE Computer Society, 2004.
27. C. Wan, A. Campbell, and L. Krishnamurthy. PSFQ: A Reliable Transport Protocol For Wireless Sensor Networks. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications (WSNA'02), pages 1--11, Atlanta, GA, September 2002.
28. World Wide Web Consortium, Cambridge, MA, USA. Efficient XML Interchange Measurements Note, July 2007. W3C Working Draft.
29. Z. Ye, S. V. Krishnamurthy, and S. K. Tripathi. A Framework for Reliable Routing in Mobile Ad Hoc Networks. In Proceedings of INFOCOM'03, pages 270--280, March 30 - April 3 2003.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

    • Reliability

• Networks

  • Network performance evaluation

• Software and its engineering

  • Software organization and properties

    • Extra-functional properties

      • Software reliability

    • Software system structures

      • Distributed systems organizing principles