Abstract
We present probabilistic algorithms for testing IP routing protocols. Different than commercial testing tools, which select their test cases in an ad-hoc manner, our technique chooses test cases with a guaranteed fault coverage. Our algorithms are applied to testing RIP, OSPF, and BGP routing protocols. We test the routing table correctness, database information consistency with network topology and packet forwarding behaviors. We provide an analysis of test execution time and fault coverage. The algorithms are part of a software tool SOCRATES, developed at Bell laboratories. SOCRATES also creates a testing environment so that the generated test cases can be executed in real time on high speed routers.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-0-387-35533-7_26
Chapter PDF
Similar content being viewed by others
References
D. E. Comer and D. L. Stevens. Internetworking with TCP/IP, Vol. II. Prentice-Hall, 1999.
T. G. Griffin and G. Wilfong. An analysis of BGP convergenece properties. In ACM SIGCOMM, pages 277–288, 1999.
R. Hao, D. Lee, R. K. Sinha, and D. Vlah. Testing IP routing protocols - from probabilistic algorithms to a software tool. Bell Labs Tech Memo, 2000.
C. Hedrick. RFC 1058. URL = www. ietf.org/rf c. htm1, June 1988.
C. Huitema. Routing in the Internet. Prentice-Hall, 1995.
D. Massey and B. Fenner. Fault detection in routing protocols. Proceeding of International Conference on Network Protocols, pages 31–40, 1999.
J. Moy. RFC 2178. URL = http://www.ietf.org/rfc.html, July 1997.
Merit Networks. Gated. URL = http://www.gated.org.
Y. Rekhter and T. Li. RFC 1771. URL = www. ietf. org/rf c. html, March 1995.
K. Vardhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. Technical Report 96–631, USC/ISI, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 IFIP International Federation for Information Processing
About this chapter
Cite this chapter
Hao, R., Lee, D., Sinha, R.K., Vlah, D. (2000). Testing IP Routing Protocols — From Probabilistic Algorithms to a Software Tool. In: Bolognesi, T., Latella, D. (eds) Formal Methods for Distributed System Development. PSTV FORTE 2000 2000. IFIP — The International Federation for Information Processing, vol 55. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-35533-7_16
Download citation
DOI: https://doi.org/10.1007/978-0-387-35533-7_16
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4757-5264-9
Online ISBN: 978-0-387-35533-7
eBook Packages: Springer Book Archive