【作者】 郑捷；

【导师】 王晓东；

【作者基本信息】 福州大学 ， 计算机软件与理论， 2003， 硕士

【摘要】 当前，网络化与信息化突破了时间和地域的限制，已成为全球化不可抗拒的世界潮流。目前互联网正与电话网、电视网、无线网、卫星网相结合，互联网在商业运作的驱动下，更加迅猛地发展。但是同时，网络的安全形势也同时越来越严峻。而防火墙作为网络安全的重要组成部分，其性能是非常重要的。防火墙的发展经历了五个时代，目前带状态监测的防火墙是防火墙技术的主流。在防火墙的性能上，过滤规则库的搜索和状态监测表的搜索、维护是关键。这两个方面的技术目前在国内外都研究得比较多。但是相对于网络应用的不断发展，尤其是近年来的宽带网络技术发展，还是有很大不足。在很多场合下，防火墙的性能已经成为网络带宽的瓶颈问题。本文在带状态监测的防火墙结构基础上，首先从总体上设计了整个防火墙的结构，进而研究了过滤规则库和状态监测表的搜索、维护问题，提出了将计算几何学、图论中的数据结构和算法引入防火墙的设计的方式，将基础理论应用到实践中来。在过滤规则库的搜索过程中，本文将规则库视为一个三维空间中有重叠的长方体集合，在规则库中搜索数据包匹配的规则，则转化为在长方体集合中搜索点所处的长方体的问题。参考了计算几何中在一个平面上多个不重叠的矩形中定位的算法，设计出初始化算法和搜索算法。在状态监测表的搜索、维护问题上，本文采用改进后的键树作为数据结构，并且设计了改进的键树的存储方案、在其上的搜索、添加、删除结点等的算法。除了将这些方面的数据结构与算法引入防火墙外，本文还进行了这些方法和其它一些实现方法之间的比较，综合分析了各自的优点与缺点，为将来从事设计的人员提供了一个参考。更多还原

【Abstract】 Now a day the development of the internet has widely spread the world. It surpassed the limitation of time and distance, made the world becoming a earth-village. And under the imitation of business, the internet developed much faster than pure technology. But meanwhile the internet becomes more and more dangerous.Firewall, as the main component of networking security, its performance is attached to more importance. The firewall has gone through 5 generations and the current main stream is firewall with state inspection. The main problem of the performance is searching of filter rules and state inspector table. There are a lot of researching done and being done in the world, but facing with the rapid progress of internet application, the performance is still unsatisfied. In many cases the firewall is still the choke point of the bandwidth.The thesis designed the structure of a firewall in global, and then it go deep into the problem of searching and maintaining the filter rules and the state inspection table. It employed the data structure and algorithms of geometry and graph theory in the design of firewall.In design of the filter rules, it takes the rules as a set of cuboids, and the searching process is transferred to a process of locating a point in these cuboids. With help of reference to some documents in geometry, it gave methods to solve of the problem.When discussed about the state inspector table, it employed key-tree as the storage method, but it improved the tree. It also gave the procedure about searching, inserting and deleting nodes in the tree.Besides the designing of data structure and algorithms, it made comparisons between its design scheme and some other schemers. It analyzed their advantages and disadvantages and made some advice for selecting the schemes.更多还原