可扩展的网络验证技术:研究现状与发展趋势  

Scalable Network Verification Technologies:State of the Art and Future

作　　者：黄翰林 徐恪[1,2,3] 李琦 李彤 付松涛[1] 高翔宇 HUANG Han-lin;XU Ke;LI Qi;LI Tong;FU Song-tao;GAO Xiang-yu(Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China;Beijing National Research Center for Information Science and Technology,Beijing 100084,China;Zhongguancun Laboratory,Beijing 100094,China;Institute for Network Science and Cyberspace,Tsinghua University,Beijing 100084,China;Key Laboratory of Data Engineering and Knowledge Engineering(Renmin University of China),Beijing 100872,China)

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]北京信息科学与技术国家研究中心,北京100084 [3]中关村实验室,北京100094 [4]清华大学网络科学与网络空间研究院,北京100084 [5]数据工程与知识工程教育部重点实验室(中国人民大学),北京100872

出　　处：《电子学报》2024年第4期1083-1102,共20页Acta Electronica Sinica

基　　金：国家重点研发计划(No.2022YFB3102300,No.2022YFB3102301);国家自然科学基金(No.61932016,No.62132011,No.62202473,No.U22B2031,No.61825204);北京高校卓越青年科学家计划(No.BJJWZYJH01201910003011)。

摘　　要：互联网作为国家信息基础设施的重要组成部分,已经在各个领域发挥着巨大的作用.随着其规模不断扩大和应用持续深入,我们也面临着意图不一致的网络行为可能导致的灾难性危害.为了确保互联网的正常运行和网络行为的一致性,我们迫切需要可部署的网络验证技术,以确保网络运行时的行为与网络运维人员的意图一致.当前已经有许多关于网络验证技术的研究,这些研究帮助用户实现自动检测网络错误,并进一步分析错误产生的原因.然而,为了满足互联网规模不断扩大的需求,可扩展性问题成为在互联网部署网络验证技术的一项重要挑战.即如何在满足时间和空间复杂度约束的前提下,快速发现并排查网络策略的错误,真正将网络验证技术应用于实际,成为一个研究热点.本文从数据面验证和控制面验证两个方面出发,深入研究和总结了现有的网络验证研究工作,并探索了基于时空优化的可扩展性技术,对这些方案的特点进行了系统性分析.最后,本文总结和展望了网络验证可扩展技术的未来研究趋势,为该领域的研究人员提供一定的参考.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 cata⁃strophic consequences of inconsistent network behaviors.To ensure the normal operation of the Internet and the consisten⁃cy of network behaviors,there is an urgent need for deployable network verification technologies that align network opera⁃tions 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 increas⁃ing demands of the expanding Internet,scalability has become a crucial challenge in deploying network verification technol⁃ogies.Specifically,how to quickly identify and diagnose errors in network policies,while satisfying time and space com⁃plexity 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 thor⁃oughly 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 pri⁃marily 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 an

关 键 词：网络验证 可扩展性 网络配置 时空优化 数据面验证 控制面验证 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]