一种基于Trie的快速IP路由查找算法

Internet的飞速发展要求核心路由器能够实现快速的分组转发和路由更新功能,实现这一功能的关键是路由表的组织结构和快速的路由查找算法.提出了带有转发域信息树的多分支Trie结构路由查找算法,它由固定步长的多分支Tile结构的路由表和转发域信息树两部分组成.对于一个长度为w的路由前缀,其查找、插入、删除路由的时间复杂度均为O((w-m)/n+1),其中m、n为Trie树的步长.它解决路由查找过程中快速更新的问题,具有算法简单、查找速度快、易于更新、空间利用率高、便于向IPv6过渡等优点.     

基于FPGA的高速路由查找算法

随着因特网速度的不断提高、网络流量的不断增加和路由表项数目的不断增大，IP路由查找速度已经成为制约核心路由器性能的主要瓶颈。为了减少存储器的访问次数。提高路由查找速度。文中提出了一种基于四级流水线的并行查找方法，即并行查找四片存储器并进行最长前缀匹配．从而在一次访问存储器时间内完成查找的实现方法，同时给出了其硬件实现结构。仿真实验结果显示，该算法可实现100Mpps的查找速度并具有查找速度快、支持动态更新和易于硬件实现的特点．能满足20Gbps的核心路由器环境要求。     

基于非重叠前缀集合的并行路由查找系统

快速的路由查找机制是高性能路由器设计的关键.最长匹配查找是路由查找的难点所在.本文提出一个并行路由查找系统.它使用一种路由表划分方法,可将路由表中的前缀划分为若干个集合,集合内前缀没有重叠.从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找.基于这种方法,本文还提出一个通用的并行路由查找框架,框架适用于大多数路由查找算法.并行查找框架可简化查找算法的设计,提高查找算法的速度.使用二分查找算法,并行查找系统可以达到log₂(2N/B)的查找复杂度 (N为路由表前缀数目,B为大于4的整数).同时,并行查找系统对IPv6也具有很好的扩展性.     

一种分段式高速IP路由查找方法

本文提出了一种改进的分段式高速IP路由查表方法。若采用50ns的动态存储器,该方法可以在小于100ns内完成一次最长匹配路由查找并且具有快速的路由表项更新功能,对设计高速骨干路由器的线速查表引擎具有指导意义和实用价值。     

一种实现TCAM快速增量更新的算法

三重内容可寻址存储器TCAM（ternary content-addressable memory）是执行快速路由查找的常用硬件设备。在TCAM中进行最长前缀匹配操作最糟糕情况可能需要次存储操作，这里提出了一种算法来处理TCAM，结果使增量更新时间在最糟糕情况保持较小。通过对该算法与其他算法的性能分析，证明该算法在前缀长度排序限制条件下较常用算法更优。     

基于Bloom Filter的硬件字符串匹配设计与验证

布鲁姆过滤器（Bloom Filter）是一种基于多散列大数据量的数据检索分类算法,在分析布鲁姆过滤器工作原理的基础上,给出了一种基于标准布鲁姆过滤器的硬件字符串匹配检测系统模型。完成了该系统的C语言算法实现,通过实验测试与理论结果相比较,证明了其功能的正确性。在此基础上实现模型的Verilog RTL级描述,通过仿真,验证Verilog程序的功能。针对Altera CycloneⅡEP2C35F672C6FPGA（Field Programmable Gate Array）完成了逻辑综合和时序仿真,文中的硬件字符串匹配检测系统在网络入侵检测、数据库检索等方面具有一定的实用价值。     

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上．提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示。仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用。     

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP 路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法.在多分枝trie树中取消前缀查找,组成一个大的中间结点.在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示.仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用.     

一种基于查找表的FIR成型滤波实现装置

脉冲数字成型滤波器属于有限冲激响应(FIR)滤波器的一种,常规做法是通过传统的乘累加(MACs)方法来实现,即通过对输入信号与单位冲激响应进行线性卷积。但是,随着成型滤波器系数的增加,这种卷积运算势必会占用大量的MAC单元以及延迟单元,导致现场可编程门阵列(FPGA)硬件资源紧张,系统延迟增大,设备成本增加。本文联合了FIR成型滤波器群延时特征以及基带数字调制符号特性,提出了一种新的查找表(LUT)结构的FIR滤波方法,并且在FPGA上实现。软硬件仿真结果表明,这一方法无论从精确度和资源利用上都具有一定的优势。     

基于分割多分枝Trie树的并行路由查找算法

为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题,提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树,每棵子树又构成一棵单独的多分枝Trie树,子树中取消了前缀查找,采取组成一个大中间节点的方式,在中间节点之间采用固定步长查询,中间节点内部采用二进制Trie树来表示。实验结果表明,该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点,同时适用于IPv4和 IPv6地址。     

内容中心网络中名字查找技术的研究

内容中心网络作为一种新型的未来网络体系架构被提出,以满足当前互联网信息共享的需求。内容中心网络使用类似域名的层次化名字结构对内容进行标识、路由和查找。由于互联网中内容众多,使用名字前缀构建的路由表,比传统的IP路由表大2~5个数量级,且由于名字查找依旧遵循最长前缀匹配原则,使得实现高速名字查找是一个富有挑战性的难题。分析了名字查找的技术挑战、实施难点,介绍了主要技术方法以及当前在名字查找领域的主要研究成果。     

高性能安全路由器中快速路由查找算法的研究与实现

设计快速的路由查找算法是提高路由器整体性能的关键之一.文章在一种基于RAM快速路由查找算法的基础上,根据高性能安全路由器的设计要求,进一步融入Hash链式表以及Trie树查找算法的设计思想,提出了一种可配置的路由查找算法.通过动态配置算法中的评价函数系数,该算法可以适用于多种网络应用环境.     

高速IP路由查找中改善更新性能的方法

现有的高速IP路由查找算法更多地强调路由表的查找,却忽视了路由表的更新。而路由表的更新对整个路由查找算法的性能和实际应用有不可忽视的影响。分段式查找树(Multibittrie)查找算法作为常用的IP路由查找算法,具有算法简单、有效等特点,但是更新速率较慢。作者提出一种在分段式查找树中控制路由表更新时间的方法,此方法能够较大地改善分段式查找树的更新性能。文章对更新性能的改善作了论述。     

可加速最长前缀匹配的布隆过滤查找方案

作为一种具有过滤功能的数据结构,布隆过滤器在路由查找中正在被广泛应用。在路由查找中布隆过滤器主要用于预处理路由查询,因为路由表通常存储在片外的存储器中,布隆过滤可以将路由表中不存在的路由过滤掉,保证进入查找电路的都为有效路由,最大程度减少不必要的查找。我们的方案使用一种优化的布隆过滤器来加速最长前缀匹配,优化后的布隆过滤器可并行过滤避免了使用流水线技术带来的查找延迟,同时支持删除操作路由,路由更新后不需要重建过滤器降低了路由表的更新延迟。仿真结果表明使用不到2Mb的FPGA片内资源和外部DDR,我们的方案可实现每次查找平均一次片外访问。     

基于深度布隆过滤器的NDN网络三级名字查找方法

为提高命名数据网络(Name Data Networking, NDN)路由过程中内容名字查找的效率,该文提出一种基于深度布隆过滤器的3级名字查找方法。该方法使用长短记忆神经网络(Long Short Term Memory, LSTM)与标准布隆过滤器相结合的方法优化名字查找过程;采用3级结构优化内容名字在内容存储器(Content Store, CS)、待定请求表(Pending Interest Table, PIT)中的精确查找过程,提高查找精度并降低内存消耗。从理论上分析了3级名字查找方法的假阳性率,并通过实验验证了该方法能够有效节省内存、降低查找过程的假阳性。     

SybilBF: Defending against Sybil Attacks via Bloom Filters

Distributed systems particularly suffer from Sybil attacks, where a malicious user creates numerous bogus nodes to influence the functions of the system. In this letter, we propose a Bloom filter‐based scheme, SybilBF, to fight against Sybil attacks. A Bloom filter presents a set of Sybil nodes according to historical behavior, which can be disseminated to at least n·(e–1)/e honest nodes. Our evaluation shows that SybilBF outperforms state of the art mechanisms improving SybilLimit by a factor of (1/e)· at least.     

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

in network packet processing, high-performance string lookup systems are very important. In this article, an extended Bloom filter data structure is introduced to support value retrieval string lookup, and to improve its performance, a weighted extended Bloom filter （WEBF） structure is generalized. The optimal configuration of the WEBF is then derived, and it is shown that it outperforms the traditional Bloom filter. Finally, an application-specific integrated circuit （ASIC）-based technique using WEBF is outlined.