上世纪中期,计算机的出现给人类的生活带来了翻天覆地的变化,网络的发展速度更令人叹为观止。计算机网络具备分布广域性,体系结构开放性,资源共享性和信道共用性的特点,这些特点在增加了网络实用性的同时,也不可避免地给系统带来了脆弱性和危险性等一系列让人们不得不担心的问题,使其面临严重的安全隐患。同时,IPv4的许多不足也已经逐渐显露出来,如IP地址严重缺乏、不能提供多媒体服务、不支持移动用户等。其中最迫切需要解决的就是IP地址不足及骨干路由器中路由表过于庞大等问题。为了解决这些问题,IETF制定了新一代的IP协议:IPv6协议。可以肯定地说,IPv6将成为今后Internet的主导。但同时,IPv6的网络安全问题也同样摆在人们面前。防火墙这一强有力的网络安全工具已在IPv4网络得到广泛的应用,但可以应用在IPv6网络中防火墙工具还很少,这也是本论文的研究背景之一。通过查阅大量的资料可以发现现有的许多Linux防火墙的过滤规则匹配算法都采用的是顺序查找。但是,顺序查找算法在处理大规则集时,其匹配效率下降得很快,尤其是IPv6的地址空间巨大,使得包过滤的效率更低。因此可以得出如下结论:对过滤规则的顺序查找是防火墙的性能瓶颈,也是系统对IP包处理的性能瓶颈。也就是说防火墙的可靠性并不是百分之百的。基于此,本文以增强防火墙的可靠性为目的,在深入分析了现有的几种包分类算法的基础上,提出一种基于二叉树的过滤规则快速匹配算法,本算法采用Trie数据结构存储过滤规则表,并且只在叶节点存储相应的规则,因此可以节省存储空间。规则的匹配项一般包括源地址、目的地址、源端口、目的端口和协议类型五项,在本算法中,对规则的匹配采用先分解再综合的思路,即分别各自匹配规则项,再把得到的结果综合找交集,得到该数据包所对应的匹配规则,防火墙就可以根据该规则对数据包做出相应的处理。通过对顺序匹配过滤规则算法的改进,提高了防火墙的规则匹配速度和系统吞吐量,达到了增强防火墙的可靠性的目的。并对Linux下的锁所带来的效率问题和丢包问题进行了深入研究,根据本算法的特点设计了锁在算法中的具体使用方法。此外,本文还分析了数据包过滤技术的另一个问题:规则冲突,给出了一个规则冲突的理论分析和查找算法。实验证明该算法能准确地检测出相互冲突的过滤规则。本文在对防火墙的算法和性能进行分析的基础上,完成了在IPv6网络下的快速过滤规则匹配算法和规则冲突查找算法的设计和实验。基于现有的防火墙开发技术,对改进和提高IPv6下防火墙的可靠性作了有益的尝试。