Assisting Reachability Verification of Network Configurations Updates with NUV

Abstract Configuring a network is always difficult and error-prone because of low-level configuration languages and complex routing mechanisms. Most network outages occur when network the configuration is updated. Thus, it is important to proactively verify network configurations. Unfortunately, there are two practical obstacles that inhibit the performance of existing configuration verification tools: (i) Lack of knowledge. Network users often do not know which input verification queries need to be verified. (ii) Limited scalability. Even the state-of-the-art tool (i.e., Minesweeper [1]) takes approximately 500 seconds to complete a single reachability query for a network with tens of routers. Considering the total number of queries that must be verified, real networks often make such techniques impractical. In this paper, we propose NUV, a framework for performing network configuration update verification. NUV outputs verification queries for only the endpoints whose forwarding behavior has changed under the updated network configuration. Based on the network forwarding model, NUV infers the potential traffic impact and eliminates endpoints whose forwarding behavior is equivalent in both the original network configuration and the updated configuration. The NUV outputs can be used as input to a rich collection of existing configuration verification tools. Evaluations on a series of benchmark networks show that NUV can solve the lack of knowledge problem, and it enables query verification to execute at speeds orders of magnitude faster than existing tools; thus, it also improves verification scalability.