基于FPGA的访问控制列表并行查找设计与实现

在高安全要求的网络环境中,多种类型的网络设备均需要部署基于规则的访问控制功能。访问控制列表通过五元组进行规则匹配,实现对网络报文的筛选、过滤、处理、控制等操作。如何利用有限的资源实现更高查表性能、更多规则数量的访问控制列表,是相关设备的关键技术之一。通过分析网络通信设备中访问控制列表的一般工作流程,文章提出了一种改进的基于现场可编程逻辑门阵列(Field Programmable Gate Array,FPGA)实现的访问控制列表并行查找设计方法,并详细阐述了具体模块的实现方案。实验结果表明,该方案可以充分利用FPGA的存储与逻辑资源,实现较大规模的支持范围匹配的规则表项,并可以支持10 Gpbs速率等级网络通信的查表需求。

高端路由器CIDR表非关键字索引的B-Tree机制

不分类的互联网协议(IP)地址方式无类别域间路由(CIDR)可以解决高端路由器中路由匹配延迟问题.通过对CIDR表深入分析,在参考数据库的非关键字索引方法和分割索引算法的基础上,提出了一种满足CIDR表要求的非关键字索引的B-Tree算法.该算法首先对CIDR表的全部前缀地址集合进行分割索引,分割后,CIDR表被改变成一种B-Tree索引结构;然后按照IP地址的非关键字对CIDR表进行快速查找.仿真结果表明,本文算法更好地满足了快速查找IP地址的需求.

浅析汇编语言中数制转换方法之查表法

数制转换是计算机中非常基础和重要的,用汇编语言程序进行数制转换速度快。但是需使用大量的指令语句。因此寻找一种可靠高效,指令精简的方法更为重要,本文正是介绍具有这些优良特性的查表法。

基于OPNET的卫星路由查找算法仿真分析

为了更加直观的比较线性表算法、Trie tree算法以及Hash算法在卫星路由查找的性能,通过OPNET平台进行建模仿真.实验结果表明,三种算法路由查询次数相同.如果以访问次数为标准,选择Trie tree算法为宜.如果以查询深度为标准,选择Trie tree算法为宜.如果以响应时间为标准,由于Hash算法不稳定,选择线性表算法和Trie tree算法为宜.因此实验结论为,Trie tree算法总体性能最佳,但算法实现比较复杂,Hash算法不稳定,但对规则的增减比较容易,线性表算法易于实现,但访问次数较高.

基于多层混合结构的IPv6路由表查找算法

针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能,却使得路由更新需要重构整个路由表的问题,提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点,把前缀1～16位的不同取值按其在路由表中出现的概率降序存储在线性表中,在第二、三层把前缀的17～32位和33～48位分别用二叉平衡树组织,在第四层把49～64位使用线性表组织。实验结果表明,该算法查找速度快,占用内存少,动态增量更新速度快。

支持访问控制列表100Gbps线速查找的流水线方案研究

访问控制列表查找作为路由器的关键技术,可以根据IP数据包头信息对数据包进行更细粒度的分类,特别是对高速路由器中的快速查找技术的研究需求非常紧迫.访问控制列表根据几何分割可以生成决策树,查找过程可以通过遍历决策树加流水线的方式来实现.简单的流水线实现会带来内存利用不均匀的问题,为了解决该问题,本文采用双端口静态随机存储器技术,提出环形线性流水线结构来实现遍历树.该方法能均匀分布流水线中各段的内存,支持100Gbps线速处理.

一种硬件哈希表压缩方法及其性能研究

在高速、大容量的基于流的报文分类应用中,采用硬件哈希表具有成本低、扩展性好等优点。但由于需要在硬件哈希表中保存流标识,而流标识的长度依不同应用可能长达几十字节,一方面需要较大的存储空间,另一方面也严重影响了哈希查表的性能。提出了一种硬件哈希表压缩方法,可以有效压缩保存在哈希表中流标识的长度,减小所需存储器容量,提高查表性能,同时实现复杂度低,具有较高的实用价值。

Twitter数据采集方案研究

为了能够实时、高效地获取Twitter数据,在分析了传统采集方法的缺陷后,提出了基于Twitter List API和Lookup API的用户数据采集方案。该方案通过对用户进行分类,进而精确控制API的调用频率。经在超过26万Twitter用户和600万条消息的一系列实验证明,通过两套方案的结合可以实现Twitter用户数据高效实时的获取。

基于双向跳表的命名数据网内容存储池

针对命名数据网中内容存储池须要快速检索差异化名称数据、高效存储数据信息和有效支持缓存替换策略的设计需求,提出了一种基于双向跳表的命名数据网内容存储池的存储结构学习树-双向跳表(LT-DSL).该存储结构由部署于片上的学习树和部署于片下的双向跳表(DSL)两种数据结构组成.LT-DSL通过重新设计索引数据结构来学习索引内容在存储器中的分布情况,实现了数据的均匀映射,提升了存储效率,降低了存储开销;同时,通过采用全新的名称数据检索算法来快速检索名称数据,LT-DSL有效支持了缓存替换策略,加速了数据处理过程.实验结果表明:相比其他基于跳表的内容存储池方案,LT-DSL在有效支持缓存替换策略和满足网络丢包率低于1%的前提下,进一步提升了数据检索速度,降低了整体存储开销.