NeTS: Small: An Efficient Reachability Analysis Method for Large Dynamic Networks and Its Applications

企业和校园网络通常很大，其中许多网络拥有数百个路由器和数千个交换机，这些交换机将数万台主机和服务器互连在一起。企业的IP网络不仅负责传输IP数据包，还负责基于安全和策略考虑阻止数据包。可以从一个节点传输到另一个节点的数据包集（可达性集）由路由器配置和保护路由器和交换机的传出和传入接口的数据包过滤器控制。计算可达性集的能力不仅对于故障排除可达性问题是有价值的，而且对于在链路/路由器故障的情况下或在部署新链路/路由器之前调试和重新设计访问控制列表（Access Control List，ACL）也是有价值的。目前，还没有足够快的方法在线计算大型动态网络的可达集。该项目将利用一个新的想法，非常快速计算的可达性集的基础上，开发一个理论基础，将网络设计和配置转化为一门科学，并开发软件工具，用于监测，诊断和配置大型动态网络。该项目的目标和活动包括：㈠设计和执行足够快的算法，以便在毫秒内计算可达性集合并回答在线可达性查询; ㈡设计和执行各种方法和算法，以便以每几秒钟一次的频率更新拓扑结构、包过滤器和转发表发生动态变化的大型网络的可达性集合;（三）分析？原子包集？从操作网络的配置文件计算，用于知识发现和识别网络可达性结构;（iv）设计和实现网络范围的可达性策略语言，使得可以使用自动化工具来检查网络配置满足所述策略;（v）调查─- 向下设计方法，用于利用网络设计人员使用的软件工具来配置新网络，以根据网络范围的可达性策略生成分组过滤器，更广泛的影响：这一项目的成果将有助于为网络设计和管理奠定科学基础，并为配置网络创造一种自上而下的设计方法，这是建立更安全可靠的网络的关键方面。 它还将教育本科生和研究生的新概念，正式的分析方法，以及网络设计和配置的软件工具。特别是，这个项目的结果将被纳入本科生和研究生班正在教授的主要研究员在得克萨斯大学奥斯汀分校。 调查人员将积极寻求高中生、本科生和研究生的参与，特别是来自代表性不足的少数民族的学生。从项目中创建的软件工具？的研究成果将在自由软件基金会的许可下提供给其他研究人员。

Enterprise and campus networks are often large with many having hundreds of routers and thousands of switches which interconnect tens of thousands of hosts and servers. The IP network for an enterprise is not only charged with delivering IP packets but also blocking packets based on security and policy considerations. The set of packets that can travel from one node to another node (reachability set) is controlled by router configurations and by packet filters that guard the outgoing and incoming interfaces of routers and switches. The ability to compute reachability sets is valuable not only for troubleshooting reachability problems but also for debugging and redesigning access control lists (ACLs) in case of link/router failures or before new links/routers are deployed. At present, there is no method fast enough for online computation of reachability sets for large dynamic networks. This project will leverage a novel idea for very fast computation of reachability sets as the basis for developing a theoretical foundation for both transforming network design and configuration into a science and for developing software tools for monitoring, diagnosing, and configuring of large dynamic networks. The objectives and activities in the project include the following: (i) Design and implementation of algorithms fast enough to compute reachability sets and answer an online reachability query in milliseconds; (ii) design and implementation of methods and algorithms to update reachability sets of large networks with dynamic changes in topology, packet filters, and forwarding tables at a frequency of once every few seconds; (iii) analysis of ?atomic packet sets? computed from configuration files of operational networks for knowledge discovery and identifying network reachability structure; (iv) design and implementation of a network-wide reachability policy language such that automated tools can be used to check that a network configuration satisfies stated policies; (v) investigation of a top-down design approach for configuring new networks with software tools used by network designers to generate packet filters from network-wide reachability policies, with ACLs generated automatically to implement the packet filters.Broader Impact:The results of this project will contribute towards a scientific foundation for network design and management and the creation of a top-down design approach for configuring networks, which are key aspects of building more secure and reliable networks. It will also educate undergraduate and graduate students on new concepts, formal analysis methods, and software tools for network design and configuration. In particular, the results of this project will be incorporated into the undergraduate and graduate classes being taught by the principal investigator at the University of Texas at Austin. The investigators will actively seek out involvement by high school, undergraduate, and graduate students, especially students from under-represented minorities. The software tools to be created from the project?s research findings will be made available to other researchers under a license of the Free Software Foundation.