Cross-layer cooperation between membership estimation and routing

ABSTRACT

Mobile Ad hoc networks are characterised by the absence of a centralised infrastructure and node heterogeneity. Due to size and mobility requirements of the nodes that make up such a network the protocols employed often must deal with limited bandwith and avoid high power consumption. In classical layered protocol stacks, services are run in isolation. We argue, that in order to save band-with, reduce power and improve performance, various services that are running on a node may co-operate.

We have identified two services in particular that can benefit greatly from such a co-operation: The routing protocol, which is responsible for discovering routes between nodes in the system and the membership estimation service, which is responsible for providing an estimation of the current composition of the system. The two services are the fundamental building blocks for distributed algorithms and applications at a higher level.

In this paper we show how these two basic protocols can cooperate. The membership estimation service can provide useful information to the routing protocol, whereas routing may aid to maintain the membership estimation updated. We describe an implementation of a cross layer architecture, in which the Dynamic Source Routing protocol (DSR) and our Gossip-based membership estimation service share information. We show results of performacne experiments reflecting how this cooperation improves the performance of both services. Finally, we identify scenarios in which the interaction is of most benefit.

REFERENCES

• 1: G. Amoussou, H. Mohanna, M. Kadoch, and Z. Dziong. Improvement of route cache in dsr protocol by predicting effective communication distance between nodes. 2006.
• 2: C. Basile, M. Killijian, and D. Powell. A survey of dependability issues in mobile wireless networks, 2003.
• 3: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 4: Juan-Carlos Cano , Pietro Manzoni, A Performance Comparison of Energy Consumption for Mobile Ad Hoc Network Routing Protocols, Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.57, August 29-September 01, 2000
• 5: I. Chakeres, E. Belding-Royer, and C. Perkins. Dynamic manet on-demand routing protocol (dymo). Internet Draft, December 2005.
• 6: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg , Bernadette Charron-Bost, On the impossibility of group membership, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.322-330, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248120]
• 7: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 8: Ching-Hua Chuan , Sy-Yen Kuo, Cache Management of Dynamic Source Routing for Fault Tolerance in Mobile Ad Hoc Networks, Proceedings of the 2001 Pacific Rim International Symposium on Dependable Computing, p.199, December 17-19, 2001
• 9: T. Clausen , P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC Editor, 2003
• 10: Marco Conti , Gaia Maselli , Giovanni Turi , Silvia Giordano, Cross-Layering in Mobile Ad Hoc Network Design, Computer, v.37 n.2, p.48-51, February 2004 [doi>10.1109/MC.2004.1266295]
• 11: Patrick T. Eugster , Rachid Guerraoui , Anne-Marie Kermarrec , Laurent Massoulieacute;, Epidemic Information Dissemination in Distributed Systems, Computer, v.37 n.5, p.60-67, May 2004 [doi>10.1109/MC.2004.1297243]
• 12: Michael J. Fischer, The Consensus Problem in Unreliable Distributed Systems (A Brief Survey), Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.127-140, August 21-27, 1983
• 13: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 14: Richard Andrew Golding, Weak-consistency group communication and membership, University of California at Santa Cruz, Santa Cruz, CA, 1992
• 15: Zygmunt J. Haas, Joseph Y. Halpern, and Erran L. Li. Gossip-based ad hoc routing. In INFOCOM, 2002.
• 16: David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 17: V. Kawadia and P. R. Kumar. A cautionary perspective on cross-layer design. Wireless Communications, IEEE {see also IEEE Personal Communications}, 12(1): 3--11, 2005.
• 18: Xiang-Yang Li , Kousha Moaveninejad , Ophir Frieder, Regional gossip routing for wireless ad hoc networks, Mobile Networks and Applications, v.10 n.1-2, p.61-77, February 2005 [doi>10.1145/1046430.1046436]
• 19: Wenjing Lou , Yuguang Fang, Predictive caching strategy for on-demand routing protocols in wireless ad hoc networks, Wireless Networks, v.8 n.6, p.671-679, November 2002 [doi>10.1023/A:1020327309720]
• 20: Jun Luo, Patrick Th. Eugster, and Jean-Pierre Hubaux. Probabilistic reliable multicast in ad hoc networks. Ad Hoc Networks, 2: 369--386, October 2004.
• 21: K. Murugan, S. Balaji, P. Sivasankar, and S. Shanmugavel. Cache based energy efficient strategies in mobile ad hoc networks. In ICPWC'05, pages 90--94. IEEE Computer Society, 2005.
• 22: Nikhil I. Panchal and Nael B. Abu-Ghazaleh. Active route cache optimaztion for ad hoc networks. Submitted, Infocom 2002, 2002.
• 23: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 24: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 25: The VINT project. The NS2 manual. Technical report, ISI, 2004. http://www.isi.edu/nsnam/ns/ns-documentation.html.
• 26: Lian Qin and Thomas Kunz. Survey on mobile ad hoc network routing protocols and cross-layer design. Technical Report Technical Report SCE-04-14, Carleton University, Systems and Computer Engineering, August 2004.
• 27: Božidar Radunović. A Cross-Layer Design of Wireless Ad-Hoc Networks. PhD thesis, 2005.
• 28: Vijay T. Raisinghani and Sridhar Iyer. Cross-layer design optimizations in wireless protocol stacks, 2004.
• 29: R. Van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. In Proceedings of Middleware'98, pages 55--70. IFIP, The Lake District, UK, 1998.
• 30: A. Schiper. Practical impact of group communication theory, 2002.
• 31: V. Srivastava and M. Motani. Cross-layer design: a survey and the road ahead. Communications Magazine, IEEE, 43(12): 112--119, 2005.
• 32: E. Vollset and P. Ezhilchelvan. A survey of reliable broadcast protocols for mobile ad-hoc networks, 2003.
• 33: Brian Whitworth , Roy Felton, Measuring disagreement in groups facing limited-choice problems, ACM SIGMIS Database, v.30 n.3-4, p.22-33, Summer/Fall 1999 [doi>10.1145/344241.344243]
• 34: Xin Yu. Study on cross-layer design and power conservation in ad hoc network. In Parallel and Distributed Computing, Applications and Technologies, PDCAT'03, pages 324--328, 2003.
• 35: Xin Yu, Improving TCP performance over mobile ad hoc networks by exploiting cross-layer information awareness, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023743]
• 36: Xinyan Zhang , Jiangchuan Liu, Gossip based streaming, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013420]

INDEX TERMS

Keywords:
DSR, ad hoc networks, cross-layer, distributed systems, group membership estimation