More Web Proxy on the site http://driver.im/

article

A formal validation methodology for MANET routing protocols based on nodes' self similarity

Authors:

Ana CavalliAuthors Info & Claims

Computer Communications, Volume 31, Issue 4

Pages 827 - 841

https://doi.org/10.1016/j.comcom.2007.10.031

Published: 03 March 2008 Publication History

Abstract

Conformance testing for ad hoc routing protocols is crucial to the reliability of Wireless Mobile Ad Hoc Networks. Most of the works related to the validation of such protocols are based on simulation and emulation analysis of simulated/emulated implementations without taking into account formal specifications. However, for many reasons, it has often been shown that the results obtained from simulator studies are far from the real case studies. In this paper, we propose a new conformance testing methodology dedicated to the validation of MANET routing protocols, especially Dynamic Source Routing. After generating test sequences from the formal model, the main issue is to execute them. There exist many techniques in wired systems, but several MANET inherent constraints lead to cope with the diverse mobility patterns and the topological changes. Therefore, a nodes' self similarity approach is introduced as well a specific testing architecture dealing with unexpected and unpredictable topology and messages. Interesting results have been provided as illustrated through experiments.

References

[1]

NS, The network simulator. Available from: <http://www.isi.edu/nsnam/ns>, 2004.

[2]

OPNet, The opnet modeler. Available from: <http://www.opnet.com/products/modeler/home.html>, 2005.

[3]

Cowie, J., Nicol, D. and Ogielski, A., Modeline the global internet. Computing in Science and Engineering. 30-36.

[4]

L. Bajaj, M. Takai, R. Ahuja, K. Tang, R. Bagrodia, M. Gerla, Glomosim: a scalable network simulation environement, Technical Report 990027, UCLA Computer Science Department, May 1999.

[5]

D. Cavin, Y. Sasson, A. Shiper, On the accuracy of manet simulator, in: Workshop on Principle of Mobeil Computing, 2002.

[6]

Q. Ke, D. Maltz, D.B. Johnson, Emulation of multi-hop wireless ad hoc networks, in: Mobile and Multimedia Communications, 2000.

[7]

Bhargavan, K., Gunter, C., Lee, I., Sokolsky, O., Kim, M., Obradovic, D. and Viswanathan, M., Verisim: formal analysis of network simulations. IEEE Transactions on Software Engineering. v28 i2. 129-145.

[8]

M. Kim, M. Viswanathan, H. Ben-Abdallah, S. Kannan, I. Lee, O. Sokolsky, Formally specified monitoring of temporal properties, in: In Euromicro Conference on Real-Time Systems, 1999.

[9]

Lin, T., Midkiff, S.F. and Park, J.S., A framework for wireless ad hoc routing protocols. Wireless Communications and Networking. v2. 1162-1167.

[10]

Glasser, U. and Gu, Q.-P., Formal description and analysis of a distributed location service for mobile ad hoc networks. Theoretical Computer Science.

[11]

Zakkuidin, I., Hawkins, T. and Moffat, N., Towards a game theoretic understaing of ad hoc routing. Electronic Notes in Theoretical Computer Science. 119

[12]

D. Lee, D. Chen, R. Hao, R. Miller, J. Wu, X. Yin, A formal approach for passive testing of protocol data portions, in: Proceedings of the IEEE International Conference on Network Protocols, ICNP'02, 2002.

[13]

Alcalde, B., Cavalli, A., Chen, D., Khuu, D. and Lee, D., Network protocol system passive testing for fault management - a backward checking approach. In: Lecture Notes on Computer Science, vol. 3235. Springer. pp. 150-166.

[14]

Arnedo, J., Cavalli, A. and Nunez, M., Fast testing of critical properties through passive testing. In: Lecture Notes on Computer Science, vol. 2644/2003. Springer. pp. 295-310.

[15]

ISO/IEC, ISO/IEC 9646-1. Information Technology - Open Systems Interconnection - Conformance Testing Methodology and framework part 1: General concepts.

[16]

A. Cavalli, D. Lee, C. Rinderknecht, F. Zaidi, Hit-or-jump: an algorithm for embedded testing with applications to IN services, in: J. Wu, S.T. Chanson, Q. Gao (Eds.), Formal Methods for Protocol Engineering and Distributed Systems, FORTE XII/ PSTV XIX'99, vol. 156 of IFIP Conference Proceedings, Kluwer, Beijing, China, 1999.

[17]

Lee, D. and Yannakakis, M., Principles and methods of testing finite state machines - a survey. IEEE Transactions on Computers. v84. 1090-1123.

[18]

ITU-T, Recommandation Z.100: CCITT Specification and Description Language (SDL), Technical Report ITU-T, 1999.

[19]

D. Johnson, D. Maltz, Y.-C. Hu, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) - Experimental RFC, IETF MANET Working Group. Available from: <http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-10.txt>, July 2004.

[20]

S. Maag, C. Grepet, A. Cavalli, Un ModFle de Validation pour le Protocole de Routage DSR, in: Hermes (Ed.), CFIP 2005, Bordeaux, France, 2005, pp. 85-100.

[21]

C. Grepet, Methodology pour la validation de protocoles de routage ad hoc, Ph.D. Thesis, Evry Val d'Essonne University, January 2007.

[22]

F. Zaidi, Contribution a la génération de tests pour les composants de service. application aux services de rTseau intelligent., Ph.D. Thesis, Evry Val d'Essonne University, November 2001.

[23]

T. Clausen, P. Jacquet, Optimized Link State Routing Protocol (OLSR) - RFC3626, INRIA, ietf Edition, October 2003.

[24]

C. Grepet, S. Maag, A testing methodology for a manet routing protocol using a node self-similarity approach, in: The third IEEE PerCom Workshop on Pervasive Wireless Networking, 2007.

[25]

K. Merouane, C. Grepet, S. Maag, A methodology for interoperability testing of a manet routing protocol, in: The Third IEEE International Conference on Wireless and Mobile Communications, 2007.

Digital Library

[26]

S. Maag, F. Zaidi, Testing methodology for an ad hoc routing protocol, in: ACM PMšHWšN 2006, 2006.

[27]

C. Djouvas, N.D. Griffeth, N.A. Lynch, Using self-similarity for efficient network testing, Technical Report, Lehman College, 2005.

[28]

D.B. Johnson, Validation of wireless and mobile network models and simulation, Monarch Project, 1999.

[29]

Ns-2 emulator. Available from: <http://www.isi.edu/nsnam/ns/ns-emulation.html>.

[30]

E. Nordstrom, Dsr-uu v0.1. Available from: <http://core.it.uu.se/core/index.php/DSR-UU>, Uppsala University.

[31]

J. Dike, user-mode-linux. Available from: <http://user-mode-linux.sourceforge.net/>.

[32]

B. Wehbi, Dynamic remote access solution to a hot-zone, Master's Thesis, UniversitT Pierre et Marie Curie, 2005.

Cited By

Abassi RRiahla MTamine K(2021)Towards a Formal Validation of a Hybrid Multi-Agent Routing Protocol for Ad hoc NetworksInternational Journal of Business Data Communications and Networking10.4018/IJBDCN.28670317:2(1-15)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.4018/IJBDCN.286703
Sowah ROfori-Amanfo KMills GKoumadi K(2019)Detection and Prevention of Man-in-the-Middle Spoofing Attacks in MANETs Using Predictive Techniques in Artificial Neural Networks (ANN)Journal of Computer Networks and Communications10.1155/2019/46839822019Online publication date: 20-Jan-2019
https://dl.acm.org/doi/10.1155/2019/4683982
Shu TDing ZChen MXia J(2016)A heuristic transition executability analysis method for generating EFSM-specified protocol test sequencesInformation Sciences: an International Journal10.1016/j.ins.2016.07.059370:C(63-78)Online publication date: 20-Nov-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.07.059
Show More Cited By

Index Terms

A formal validation methodology for MANET routing protocols based on nodes' self similarity
1. Networks

Recommendations

Performance Comparison of MANET Routing Protocol based on RandomWaypoint Mobility Model
CSAI '17: Proceedings of the 2017 International Conference on Computer Science and Artificial Intelligence

Today, the use of Mobile Ad Hoc Network (MANET) is becoming increasingly popular due to its flexibility and ease of use wherever and whenever. MANET is able to adapt to many applications, such as disaster management and military operations. The MANET ...
MANET routing protocols vs. mobility models: performance analysis and comparison
AIC'09: Proceedings of the 9th WSEAS international conference on Applied informatics and communications

This paper considers performance of mobile ad hoc network (MANET) routing protocols with respect to group and entity mobility models. The three widely used routing protocols have been investigated and compared: Destination Sequenced Distance Vector (...
MANET Routing Protocols Comparison for Composite Traffic Network
IMCCC '13: Proceedings of the 2013 Third International Conference on Instrumentation, Measurement, Computer, Communication and Control

The choice of routing protocols is an important issue in the establishment and design of Ad hoc networks. However, existing routing protocols are based on single traffic source or simple traffic models used in conventional networks like HTTP and video ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Communications

Computer Communications Volume 31, Issue 4

March, 2008

218 pages

ISSN:0140-3664

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2007.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 03 March 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abassi RRiahla MTamine K(2021)Towards a Formal Validation of a Hybrid Multi-Agent Routing Protocol for Ad hoc NetworksInternational Journal of Business Data Communications and Networking10.4018/IJBDCN.28670317:2(1-15)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.4018/IJBDCN.286703
Sowah ROfori-Amanfo KMills GKoumadi K(2019)Detection and Prevention of Man-in-the-Middle Spoofing Attacks in MANETs Using Predictive Techniques in Artificial Neural Networks (ANN)Journal of Computer Networks and Communications10.1155/2019/46839822019Online publication date: 20-Jan-2019
https://dl.acm.org/doi/10.1155/2019/4683982
Shu TDing ZChen MXia J(2016)A heuristic transition executability analysis method for generating EFSM-specified protocol test sequencesInformation Sciences: an International Journal10.1016/j.ins.2016.07.059370:C(63-78)Online publication date: 20-Nov-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.07.059
Imran MZafar NAlnuem MAksoy MVasilakos A(2016)Formal verification and validation of a movement control actor relocation algorithm for safety---critical applicationsWireless Networks10.1007/s11276-015-0962-822:1(247-265)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s11276-015-0962-8
López JMaag SMorales GLadid LMontes ABruck PFerri FChbeir R(2013)A formal distributed network monitoring approach for enhancing trust management systemsProceedings of the Fifth International Conference on Management of Emergent Digital EcoSystems10.1145/2536146.2536160(76-83)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2536146.2536160
Viana AMaag SZaidi F(2011)One step forwardACM Computing Surveys10.1145/1883612.188361443:2(1-36)Online publication date: 4-Feb-2011
https://dl.acm.org/doi/10.1145/1883612.1883614
Cavalli AMaag Sde Oca EShin SOssowski S(2009)A passive conformance testing approach for a MANET routing protocolProceedings of the 2009 ACM symposium on Applied Computing10.1145/1529282.1529326(207-211)Online publication date: 8-Mar-2009
https://dl.acm.org/doi/10.1145/1529282.1529326

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents