Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers

Internet backbone refers to the principal data routes between large, strategically interconnected networks and core routers on the Internet. Internet backbone router is essentially the core router of Internet backbone and its performance is mainly relevant to the reliability of its mainboard. The mainboard is an embedded system consisting of hardware and software. Its reliability testing involves executing a number of test cases, which are designed to expose potential defects, under harsh environmental conditions. The testing process is largely prolonged due to the dramatic increase of the number of test cases, mainly due to the continuous increase and upgrade of its functional modules. Thus, there is a big demand from industry to improve the reliability testing efficiency and effectiveness. In this work, we exploit the principles of regression testing in software maintenance: test case selection and prioritization, and construct two testing planning models to largely reduce the testing time as well as to improve the effectiveness of failure detections. The former is a two-step model we introduced in previous work that optimizes test case selection and test case sequencing sequentially. The latter, an integrated model is newly developed, optimizing the test case selection and sequencing simultaneously with the precedence constraints among the test cases. Moreover, we propose exact algorithms based on branch-and-price for solving these two models. Finally, we present a case study demonstrating that the integrated model outperforms the two-step method and the advantage is more significant if the sequencing objective has greater weight in the integrated objective function.