Stress testing of OSPF protocol implementation based on large-scale routing simulation

摘要

The stability and robustness of routing protocol implementations (RPI) in a router are becoming more and more important with the growth of the Internet. This paper proposes a novel approach named stress testing to evaluate routing protocols, which treats RPI as a black box without any assumptions. Compared with some traditional testing techniques, the architecture of stress testing is proposed. We use a stochastic Petri net model to describe the test process of OSPF RPI with the OSPF protocol emulation and the highspeed interaction of many simulated routes. Based on this model, we have developed an "integrated performance tester" as a test bed, with which we evaluated the running characteristics of a CISCO2600 router. Analyzing the test results with mathematical methods, we obtained that the computational complexity of OSPF RPI in this router is O((InN)⁴) to the number of its routing table entries. We have also given the upper bound of the network scale it supports. This experiment shows that stress testing can be widely used to inspect the stability, scalability and adaptability of other RPI, e.g. RIP, BGP.