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

Article

Testing methodology for an ad hoc routing protocol

Authors:

Stéphane Maag,

Fatiha ZaidiAuthors Info & Claims

PM2HW2N '06: Proceedings of the ACM international workshop on Performance monitoring, measurement, and evaluation of heterogeneous wireless and wired networks

Pages 48 - 55

https://doi.org/10.1145/1163653.1163663

Published: 02 October 2006 Publication History

Abstract

Ad hoc protocols, Testing, Verification, Model checking, PLTL, SPIN, Simulations. In this paper, we define a model of an ad hoc routing protocol, i.e. the OLSR (Optimized Link-State Routing) protocol. This model handles novel constraints related to such networks and issues new challenges to treat these constraints. In the network community, the practice is based on simulation models that allow to perform performance measures but no formal methods are used. We propose to promote the use of formal description techniques such as the promela and SDL languages that are both well accepted in the community of communication protocols. Until now, few works exist that handle the formal description of ad hoc networks, this network has as a main feature the absence of infrastructure. So, conformance testing and verification need to be revisited in order to bridge the gap between these new protocols and formal methods. In order to test and verify such protocols we need first to dispose of a formal model of what we want to verify and test. This is what we propose herein

References

[1]

Information Technology, Open Systems Interconnection, Conformance Testing Methodology and Framework- Part 3: Tree and Tabular Combined Notation, ISO/IEC 9646-3, Part 1:Test Realisation, ISO/IEC 9646-4.]]

[2]

The network simulator. http://www.isi.edu/nsnam/ns, 2004.]]

[3]

The opnet modeler. http://www.opnet.com/products/modeler/home.html, 2005.]]

[4]

B. Algayres, Y. Lejeune, and F. Hugonnet. Goal: Observing sdl behaviors with geode. In The Proceedings of SDL'95, pages 223--230. Elsevier, 1995.]]

[5]

Roscoe A.W. A Classical Mind, Essays in Honour of C.A.R. Hoare, chapter Model-Checking CSP. Prentice Hall, 1994.]]

Digital Library

[6]

S. Barbin, L. Tanguy, and C. Viho. Towards a formal framework for interoperability testing. In M. Kim, B. Chin, S. Kang, and D. Lee, editors, 21st IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems, pages 53--68, August 2001.]]

Digital Library

[7]

C. Besse, A. Cavalli, M. Kim, and F. Zaïdi. Automated Generation of Interoperability Testing. In IFIP TC6/WG6.1 Fourteenth International Conference on Testing od Communication Systems, pages 169--184, Berlin, march 2002. Kluwer Academic.]]

Digital Library

[8]

A. Cavalli, A. Mederreg, and F. Zaïdi. Application of formal testing methodology to wireless telephony networks. In 2nd International Information and Telecommunications TEchnologies Symposium, I2TS'2003, Florianopolis, Brazil, october 2003.]]

[9]

A. Cavalli, A. Mederreg, F. Zaïdi, P. Combes, W. Monin, R. Castanet, M. MacKaya, and P. Laurencot. A Multi-Services and Multi-Protocol Validation Platform - Experimentations Results. In The 16th IFIP TESTCOM, pages 17--32, Oxford, march 2004. Lectures Notes in Computer Science.]]

[10]

Ana Cavalli, David Lee, Christian Rinderknecht, and Fatiha Zaïdi. Hit-or-Jump: An Algorithm for Embedded Testing with Applications to IN Services. In Formal Methods for Protocol Engineering And Distributed Systems, pages 41--56, Pékin, Chine, October 1999. Kluwer Academic.]]

Digital Library

[11]

R. de Renesse and Aghvami A.H. Formal verification of ad hoc routing protocols using spin model checker. In Proceedings of IEEE MELECON'04, Croatia, May 2004.]]

[12]

O. Dubuisson. ASN.1. Springer, 1999.]]

[13]

Bhargavan K. et al. Verisim: Formal analysis of network simulations. In Proceedings of 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2000), pages 2--13, 2000.]]

Digital Library

[14]

G.J. Holzmann. Design and validation of computer protocols. Prentice-Hall Inc, 1991.]]

Digital Library

[15]

G.J. Holzmann. SPIN Model Checker. Addison-Wesley, 2003.]]

[16]

Zakkiudin I. Towards a game theoretic understanding of ad-hoc routing. In ENTCS, volume 119, pages 67--92. ENTCS, 2005.]]

Digital Library

[17]

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

[18]

Bhargavan K., Obradovic D., and Gunter G. Formal verification of standards for distance vector routing protocols. Technical report, University of Pennsylvania, 1999.]]

[19]

Doldi L. Validation of Telecom Systems with SDL. John Wiley and Sons, May 2003.]]

[20]

D. Lee and M. Yannakakis. Principles and Methods of Testing Finite State Machines - a Survey. In The Proceedings of IEEE, volume 84, pages 1090--1123, August 1996.]]

[21]

Vadim Okun, Paul E. Black, and Yaacov Yesha. Testing with model checker: Insuring fault visibility. In Proceedings of 2002 WSEAS International Conference on System Science, pages 1351--1356, Rio de Janeiro, Brazil, October 2002.]]

[22]

S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. IETF - BCP 14, RFC 2119, March 1997.]]

Digital Library

[23]

Lin T., Midkiff S., and Park J. A framework for wireless ad hoc routing protocols. In Proc. of IEEE Wireless Communications and Networking Conf. (WCNC), 2003.]]

[24]

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

Digital Library

[25]

Glässer U. and Q-P. Gu. Formal description and analysis of a distributed location service for mobile ad hoc networks. Technical report, Fraser University, 2003.]]

[26]

R.G. de Vries and J. Tretmans. On-the-fly conformance testing using spin. In Fourth Workshop on Automata Theoretic Verification with the Spin Model Checker, ENST 98 S 002, pages 115--128, Paris, France, November 2, 1998.]]

[27]

Irfan Zakiuddin, Michael Goldsmith, Paul Whittaker, and Paul H. B. Gardiner. A methodology for model-checking ad-hoc networks. In Proc. of SPIN 2003, pages 181--196, Protland, OR, USA, 2003.]]

Cited By

Maag SGrepet CCavalli A(2019)A formal validation methodology for MANET routing protocols based on nodes' self similarityComputer Communications10.1016/j.comcom.2007.10.03131:4(827-841)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2007.10.031
Marroquin AMartinez VSolares JMaag S(2018)A Distributed Test-Cases Dependencies Framework - Application to the SIP Protocol2018 IEEE 38th Central America and Panama Convention (CONCAPAN XXXVIII)10.1109/CONCAPAN.2018.8596359(1-6)Online publication date: Nov-2018
https://doi.org/10.1109/CONCAPAN.2018.8596359
Le TMaag S(2016)Ads Network Monitoring Integrating Realistic Urban Mobility Patterns2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA)10.1109/WAINA.2016.99(737-742)Online publication date: Mar-2016
https://doi.org/10.1109/WAINA.2016.99
Show More Cited By

Index Terms

Testing methodology for an ad hoc routing protocol

Recommendations

Ad hoc routing protocol verification through broadcast abstraction
FORTE'05: Proceedings of the 25th IFIP WG 6.1 international conference on Formal Techniques for Networked and Distributed Systems

We present an improved method for analyzing route establishment in ad hoc routing protocols. An efficient abstraction for Propagating Localized Broadcast with Dampening (PLBD) is developed. Applying this result we are able to verify networks and ...
Modeling the optimized link-state routing protocol for verification
TMS/DEVS '12: Proceedings of the 2012 Symposium on Theory of Modeling and Simulation - DEVS Integrative M&S Symposium

The exhaustive property verification of mobile ad hoc routing protocols has proven difficult, especially for proactive protocols. Several attempts to produce tractable models have failed. This article presents the application of formal methods to verify ...
Dynamic source routing (DSR) protocol implementation in ns-3
SIMUTOOLS '12: Proceedings of the 5th International ICST Conference on Simulation Tools and Techniques

Routing protocols are essential to the performance of wireless networks especially in mobile ad-hoc scenarios. The development of new routing protocols requires comparing them against well-known protocols in various simulation environments. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PM2HW2N '06: Proceedings of the ACM international workshop on Performance monitoring, measurement, and evaluation of heterogeneous wireless and wired networks

October 2006

114 pages

ISBN:1595935029

DOI:10.1145/1163653

Program Chairs:
M. Ould-Khaoua
University of Glasgow, UK
,
B. Caminero
University of Castilla-La Mancha Albacete, Spain

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MSWiM06

Sponsor:

MSWiM06: 9th International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems 2006

October 2, 2006

Terromolinos, Spain

Acceptance Rates

PM2HW2N '06 Paper Acceptance Rate 16 of 30 submissions, 53%;

Overall Acceptance Rate 74 of 226 submissions, 33%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
707
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Maag SGrepet CCavalli A(2019)A formal validation methodology for MANET routing protocols based on nodes' self similarityComputer Communications10.1016/j.comcom.2007.10.03131:4(827-841)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.comcom.2007.10.031
Marroquin AMartinez VSolares JMaag S(2018)A Distributed Test-Cases Dependencies Framework - Application to the SIP Protocol2018 IEEE 38th Central America and Panama Convention (CONCAPAN XXXVIII)10.1109/CONCAPAN.2018.8596359(1-6)Online publication date: Nov-2018
https://doi.org/10.1109/CONCAPAN.2018.8596359
Le TMaag S(2016)Ads Network Monitoring Integrating Realistic Urban Mobility Patterns2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA)10.1109/WAINA.2016.99(737-742)Online publication date: Mar-2016
https://doi.org/10.1109/WAINA.2016.99
Marroquin ACalderon DHernandez M(2016)Forward Experiments on the Test Cases Dependencies Architecture: A Use Case Trial2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA)10.1109/WAINA.2016.54(743-747)Online publication date: Mar-2016
https://doi.org/10.1109/WAINA.2016.54
Marroquin AGonzalez DMaag SNadimi ECerny TKim SWang W(2015)A novel distributed testing approach based on test cases dependencies for communication protocolsProceedings of the 2015 Conference on research in adaptive and convergent systems10.1145/2811411.2811554(497-504)Online publication date: 9-Oct-2015
https://dl.acm.org/doi/10.1145/2811411.2811554
Marroquin AGonzalez DMaag S(2015)Testing distributed systems with test cases dependencies architecture2015 7th IEEE Latin-American Conference on Communications (LATINCOM)10.1109/LATINCOM.2015.7430116(1-6)Online publication date: Nov-2015
https://doi.org/10.1109/LATINCOM.2015.7430116
Cavalli AHigashino TNúñez M(2015)A survey on formal active and passive testing with applications to the cloudannals of telecommunications - annales des télécommunications10.1007/s12243-015-0457-870:3-4(85-93)Online publication date: 18-Feb-2015
https://doi.org/10.1007/s12243-015-0457-8
Friginal Jde Andrés DRuiz JMartínez M(2014)A survey of evaluation platforms for ad hoc routing protocolsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.09.01075:PA(395-413)Online publication date: 24-Dec-2014
https://dl.acm.org/doi/10.1016/j.comnet.2014.09.010
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
Verma AGujral M(2012)Formal Specification of Trusted Neighbor Information Base of OLSR Routing Protocol of Adhoc Network Using Z LanguageGlobal Trends in Computing and Communication Systems10.1007/978-3-642-29219-4_63(560-570)Online publication date: 2012
https://doi.org/10.1007/978-3-642-29219-4_63
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents