HUANG Han-lin, XU Ke, LI Qi, LI Tong, FU Song-tao, GAO Xiang-yu
The Internet, as a critical component of a nation's information infrastructure, has played a significant role in various domains. However, as its scale continues to expand and its applications deepen, we also face the potential catastrophic consequences of inconsistent network behaviors. To ensure the normal operation of the Internet and the consistency of network behaviors, there is an urgent need for deployable network verification technologies that align network operations with the intentions of network operators. Extensive research has been conducted on network verification technologies, assisting users in automating the detection of network errors and analyzing their root causes. However, to meet the increasing demands of the expanding Internet, scalability has become a crucial challenge in deploying network verification technologies. Specifically, how to quickly identify and diagnose errors in network policies, while satisfying time and space complexity constraints, has become a research hotspot in effectively applying network verification technologies in practice. To address this problem, this paper delves into and summarizes cutting-edge research on the temporal and spatial scalability of network verification. It begins by introducing the background knowledge related to network verification and then describes the current issues and challenges faced in network verification. Focusing on the core issue of scalability, the paper thoroughly analyzes existing work in achieving scalable verification from both the data plane and control plane perspectives. It provides a systematic analysis of the characteristics of these approaches, showcasing the distinctions and connections among related studies. According to the existing researches, we find that: (1) The scalability of data plane verification is primarily constrained by header space and forwarding matching rules, while the scalability of control plane verification is mainly limited by the complexity of multiple protocols and policies. (2) Although both data plane and control plane research employ similar scalable verification techniques, they address different but interconnected targets. For example, incremental computation in the data plane primarily focuses on updating packet equivalence classes, while incremental computation in the control plane primarily deals with network models affected by configuration changes. When applying network slicing techniques, both data plane and control plane independently validate the network by dividing it into multiple segments. (3) Compared to spatial scalability, current research places greater emphasis on temporal scalability, where reducing verification time overhead appears to be the primary pursuit of verification tools. (4) Previous research predominantly adopted a centralized verification approach, which involved collecting control plane or data plane information and then performing centralized analysis and verification. However, there has been a recent trend towards distributed verification, such as Coral and Tulkun in control plane verification. Lastly, based on the current research landscape, the paper concludes by summarizing and forecasting the research trends in scalable network verification technologies, offering valuable insights for researchers in this field. In conclusion, this paper presents a comprehensive review and outlook on the topic of scalability in network verification. It emphasizes the importance of aligning network behaviors with the intentions of network operators to ensure the reliable and consistent operation of the Internet. By addressing the challenges of scalability, researchers can advance the development of network verification technologies that can effectively verify large-scale networks within the constraints of time and space complexity. Ultimately, this contributes to enhancing the reliability and security of the Internet as a critical information infrastructure.