大容量高带宽路由查找算法设计与FPGA实现

为了解决目前IP路由查表大容量和高吞吐需求的同时,实现低硬件资源成本,提出一种大容量高带宽IP路由查表算法,并完成FPGA实现。算法将FIB表项的存储映射为字典树的数据结构,进行路径压缩和级别压缩以节省存储资源。将字典树根节点信息存储在片内SRAM,子树节点存储于片外DRAM。查找时,在芯片硬件内采用流水线方式优化资源负载均衡,实现片外DRAM的一次访问即可得到结果,实现了单周期线速查表,并支持增量更新。该算法通过FPGA设计实现,并进行仿真和实机验证。结果表明,该方案可同时支持大容量IPv4和IPv6 FIB表项并行查找,与现有方案相比,做到了更大容量、更高带宽和更低成本。

基于前缀劫持及路由更改对BGP产生的影响

在网络中,由于配置错误或恶意路由宣告而导致的BGP前缀劫持事件,给当今的互联网带来了极大的麻烦。外包缓解措施是最近提出的一种前缀劫持缓解修复的方法。它通过将把数据同步出来传送给路由器,再提取ROA当中的信息,更新证书后,替换Update报文中的内容再进行传递的机制方法,来缓解源AS号劫持事件,使机制重定向位置以此吸引大量网络流量。吸引和重定向行为的AS号对于提高修复能力非常有效。因此,如何衡量不同AS号的缓解效果并有效选择缓解因子是外包缓解措施的关键问题。为了从网络整体来均衡能耗,延长网络生存时间,采取了Cluster路由算法改进的方法,对不同的簇树中节点关系的选择,由不同节点的能量来避免路由发生回路和绕路等现象,从而更改Cluster-list id进行严格的路由选择,实现最优路由产生。

差分隐私下的一种频繁序列模式挖掘方法

频繁序列模式挖掘是数据挖掘领域的1个基本问题,然而模式本身及其支持度计数都有可能泄露用户隐私信息.差分隐私(differential privacy,DP)作为一种新出现的隐私保护技术,定义了一个相当严格的攻击模型,通过添加噪音使数据失真达到隐私保护的目的.由于序列数据内在序列性和高维度的特点,给差分隐私应用于频繁序列模式挖掘带来了挑战.对此提出了一种基于交互式差分隐私保护框架的频繁序列模式挖掘算法Diff-FSPM(differential-privacy frequent sequential pattern mining).该算法利用指数机制获取最优序列长度,并采用一种维规约策略获得原始序列数据集的规约表示,有效降低序列维度的影响;应用前缀树压缩频繁序列模式,利用拉普拉斯机制产生的噪音扰动频繁模式的真实支持度计数,同时采用闭频繁序列模式和Markov假设,有效分配隐私预算,并利用一致性约束后置处理,增强输出模式的可用性.理论角度证明算法满足ε-差分隐私,实验结果验证算法具有较好的可用性.

一种基于前缀树的频繁模式挖掘算法

挖掘频繁模式是许多数据挖掘任务的关键步骤。基于FP-Tree的挖掘算法由于无须生成候进项集效率明显高于Apriori类算法,但FP-Tree结构存在动态维护复杂、而且在挖掘过程中需要递归地创建大量的条件FP-Tree,时空效率不高。因此,本文提出一种基于前缀树的新算法。该算法通过引入一种新结构—前缀树(Prefix Tree)用来压缩存放数据所相关信息,并通过调整前缀树中节点信息和节点键直接在Prefix Tree上采用深度优先的策略挖掘频繁模式,而不需要任何附加的数据结构,从而大大提高了挖掘效率。

无重复投影数据库扫描的序列模式挖掘算法

序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广泛应用.基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一.然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降.算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能.实验和分析都表明SPMDS性能优于PrefixSpan.

一种基于Hadoop的关联规则挖掘算法

传统的并行关联规则算法对每一次迭代都定义一个MapReduce任务,以实现候选项集的生成和计数功能,但多次启动MapReduce任务会带来极大的性能开销。文中定义了一种并行关联规则挖掘算法PST-Apriori,该算法采取分治策略,在每个分布式计算节点定义一个前缀共享树,通过递归调用的方式将事务T生成的候选项集逐层压缩到前缀共享树(PST)中。然后广度遍历PST,逐层将每个节点对应的〈key,value〉作为map函数的输入,并由MapReduce框架自动按照key值进行聚集。最后调用reduce函数对多个任务的处理结果进行汇总,得到满足最小支持度阈值的频繁项集。算法只使用两个MapReduce任务,且PST按照key值排序便于Mapper端的shuffle操作,提高了运行效率。

支持告警序列差分隐私保护的网络入侵关联方法

在网络入侵情报协同分析过程中,告警数据的共享使被攻击者面临隐私泄露的风险。针对现有告警信息隐私保护方法无法应对背景知识下恶意分析的问题,提出一种新的网络告警关联分析方法。以原始告警序列数据集作为输入,利用Laplace机制构建支持差分隐私保护的噪声告警序列前缀树。在此基础上,通过遍历噪声前缀树生成泛化告警序列数据集,使用频繁序列挖掘算法实现告警关联。从理论角度证明该方法支持ε-差分隐私保护,并在典型多步攻击场景LLDoS1.0 inside数据集上进行验证。实验结果表明,该方法在保护告警序列隐私的同时,能够提高告警关联准确性。

分布环境中的并行频繁模式挖掘算法

频繁模式的并行挖掘算法是数据挖掘中重要的研究课题。目前已经提出的并行算法大多是基于Apriori或基于FP-tree。由于两者的固有局限性,而且在计算过程中需要多次同步,因而具有较低的性能。文章提出了一种基于分布数据库的并行挖掘算法。该算法尽可能地让每个处理器独立地挖掘,每个处理器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽量减少候选全局频繁模式的规模,减少网络的通信量和同步次数以提高挖掘效率。

最大频繁模式的快速挖掘与更新算法

挖掘和更新最大频繁模式是多种数据挖掘应用中的关键问题。之前的许多研究都是采用Apriori类的候选生成-检验方法或基于FP-Tree的方法,而产生大量候选和动态创建大量FP-Tree的代价太高,特别是在支持度阈值较小或存在长模式时。因此,文章提出了一种最大频繁模式的快速挖掘算法DMFP及更新算法IUMFP。DMFP算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。算法IUMFP充分利用以前的挖掘结果减少发现更新数据中新的最大频繁模式的代价。

基于交集为空的概念格批处理生成算法

采用剪枝方法,通过对NextClosure算法的改进,提出一种基于剪枝的概念格批处理算法Prun-NextClosure,减少了概念格构造过程中闭包运算的次数,从而提高概念格的构造效率。实验使用随机生成的数据集,验证了该算法的正确性和有效性。

RFID系统中改进的混合查询树防碰撞算法

针对无线射频识别(RFID)技术系统中的标签碰撞问题,采用混合查询树与多叉树结合的方法,提出一种改进的混合查询树防碰撞算法。在QT算法的基础上,通过标签序列生成器判断标签碰撞信息,结合八叉树询问机制,避免空闲周期和延迟时隙产生,减少碰撞以及标签冲突和系统开销。实验结果证明,该算法优于QT、HQT算法,可减少查询次数和系统通信量,改进的混合查询树算法的识别效率较HQT算法提高46.1%。

改进的树型结构RFID防碰撞算法

将整棵大查询树分为若干分支,在每一个分支内进行标签识别,减少碰撞发生的概率。算法分为前缀确定和分支查询2个阶段,在前缀确定阶段读取所有标签前缀,每个前缀代表一个分支,依次遍历每一分支;查询过程采用后退式搜索策略和动态搜索方式。理论分析和仿真实验表明,算法能够从查询次数、时延、吞吐率多方面改善RFID系统的整体性能。

一种最大频繁模式的快速挖掘算法

挖掘最大频繁模式是多种数据挖掘应用中的关键问题。提出一种挖掘最大频繁模式的快速算法,该算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。

基于前缀树的高效频繁项集挖掘算法

针对频繁项集挖掘时间与空间效率低的问题,提出一种基于前缀树的高效频繁项集挖掘算法,通过对事务集进行预处理,创建索引表并分配索引编号,保证前缀树中事务顺序的一致性,根据索引编号等信息创建紧凑的前缀树,采用自底向上的挖掘与投影的方式挖掘出频繁项集。实验结果表明,该算法挖掘效率高、占用空间少。

一种基于前缀树的增量序列挖掘算法

在已有模式的基础上,该文挖掘出了新的模式,减少了挖掘原始数据库次数,指出了IncSpan+算法存在的问题,说明了基于半频繁模式的增量挖掘算法的缺陷,提出了一种增量序列模式挖掘算法。该算法构造了前缀树表示序列模式,并用广度剪枝和深度剪枝维护该前缀树的结构。实验表明,该算法具有良好的性能。

基于树型结构和加权熵的中文高频词提取算法

提出了一种基于树型结构和加权熵的中文高频词提取算法。简单介绍了中文的树型结构和加权信息熵,详细叙述了算法的原理和设计步骤,并给出了具体的算法描述。实验结果表明,该算法是可行和有效的。

一种基于哈希表和Trie树的快速IP路由查找算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。

一种基于前缀编码的树生成算法

为了使树生成算法更为通用且效率更高,提出一种基于前缀编码的树生成算法.算法中的节点采用前缀编码的数据结构,便于用户对树中节点及其下层子节点上的关联数据进行快速查询和统计.由于在构造树之前已采用先根遍历的方式对节点进行了排序,同时建树过程中记录了最近各层节点的信息,因此无需搜索节点的上下层信息就可直接建立起树,大幅提高了建树效率,算法时间复杂度为O(n).该算法无需额外的数据预处理即可构造任意子树,且不会增加算法复杂度.

可靠可缩放安全多播密钥更新实现研究

实现安全多播的一般方法是设法让参与多播的所有成员共享一个组密钥 当有组成员离开或组密钥失密时 ,要进行组密钥的更新 当多播组较大时 ,组密钥更新的缩放性和可靠性是一个重要问题 解决缩放性可采用批量密钥更新方法 (BKR) ;解决可靠性可基于报文重传和纠错码等方法 WKA给出了一种对密钥树分层加权解决上述问题 在分析密钥更新需求的基础上 ,基于WKA方法 ,提出了一种在前缀编码的密钥树中 ,实现动态分层式密钥更新的方法 (A WKA) 使用前缀编码可以很方便地计算出密钥树中变化结点位置关系 ,从而为动态分层提供快速、准确的决策依据 仿真分析表明 。

基于前缀编码的先根遍历树生成算法的研究与应用

在管理信息系统的层次分类树中,为了快速查询分类信息并高效地生成层次分类子树,提出了一种基于前缀编码的先根遍历树生成算法。该算法中的节点采用前缀编码的数据结构,便于快速检索出子树节点集合;在构造子树时预先对其进行先根遍历,产生有序遍历表,同时记录最近各层节点的信息,使得建立子树的效率得到大幅提高。最后通过实例验证了所提算法的有效性,为管理信息系统中层次分类树的建立提供了可行的解决途径。