下载  >  开发技术  >  其它  > 论文研究-一种基于GPU的高效NDN数据名查找算法 .pdf

论文研究-一种基于GPU的高效NDN数据名查找算法 .pdf 评分

一种基于GPU的高效NDN数据名查找算法 ,周奔,张大方,命名数据网络(Named Data Network,NDN)是一种新型网络体系架构,它在转发数据包时是以数据名作为核心而不是IP地址。因此,数据名查找�
图武获记义在线 研究现状 目前来说,对于数据名查找问题一般有以下几种类型的解决方案:基于哈希表的解决方 案,基于布鲁姆过滤器的方案和基于树形结构的方案。 在基于哈希表的解决方案中,有通过区分核心和边界路由器,同时设计基于指纹哈希的 核心路由器,从而减少了核心路由器存储开销的方案,同时,也有方案采用贪心的查 找机制来减少查找次数,并采用基于指纹的完美哈希表减少存储开销,从而提高查找吞 吐量。而在基于布鲁姆过滤器的方案中,则有采用基于两阶段布鲁姆过滤器的命名查找方 法该方法在第ˉ阶段确定最长匹配前缀,第二阶段确定转发端∏号,从而提扃了转 发吞吐量,降低了空间开销。采用前缀布鲁姆过滤器扩展算法则通过平衡每一个布鲁姆过 滤器的负载,从而以提高吞吐量。最后,基于树形结构的解决方案中有通过对数据名分 块然后进行「次编码的方案,这样可以在一定程度上压缩存储。而另一更优秀的方法则是 采用基于的命名查找数据结构 ,它不但提高了查找速率,同时也采用 状态迁移表压缩了存储空间。 本文的方法则是结合了第一种和第三和的结果,通过对 这一数据结构的改进提 出了新的数据结构,本文不但实现了数据名的线速度查找而且进一步压缩了存 储空间。 基于 的数据名查找方法 因为数据名是字符串类型的,而一般最常用的字符串搜索数据结构就是前缀树 它比直接采用字符串比较的方法来査找宁符串的效率无疑是要高很多,而且也能较人的减少 数据名的存储开销。但是,它的缺陷也很明显,因为数据名前缀树的结构可能会非常稀疏 有大量的节点可能只有条边,如果按照·般的字典树的方式来建树的话,就会浪费很大 的存储空间。 前缀树其实也可以看成是一个有限状态机(),即把每个节点看成是一个状态,而 每个状态有个分支可到达下一层次的状态。正如上节所说,由于每个状态的实际用到的 分支数的不桷定性,很可能得到的是个稀疏,那么就需要对它进行压缩存储, 在这里采用的是对齐迁移数组 它的原理就是把刚刚所说的 中的每个状态的有效分支(即真正存在输入字符的分支)存储到同一个数组里面,存 储的方式就是:把当前的状态的标号加上分支上字符对应的 值从而得到一个和,然 后这个分支就存储在数组的第个位置,如果该位置已经被占据,则需将当前状态的所有分 支都进行同一大小的位置偏移直至无冲突为止。从这可以看出,这其实是一种基于哈希表的 图武获记义在线 存储方式。图是的个实例。 a/bc/ Address transition lab/c 1045.1001 ab/ 1046 1096 b999 1097 998 109s /997 1099b,1002 1100 1101c1051 1102 1053 图一个 name FIB构成的前缀树和ATA数组实例 显然,这种基于哈希机制的压缩存储方式能够大大减少存储空间。而其存在问题 则是当某个状态的分支发生存储冲突时需要将该状态的所有分支都进行重新存储。然而,随 着数据名的规模不断増加,这种冲突发生的概率会越来越大,为了解决这种冲突,哐一的解 决办法就是不断增加的大小来满足存储需求。而这恰恰又降低了存储效率,因此需要 对其进行进一步改进。 数据结构即是对的进一步改进的结果。它通过增加表的数量而不是 增加的大小来解决上文中说的哈希冲突问题。显然,多个表中出现的哈希冲突 次数无疑要远远低于单一表,因此每个的表的大小不需要太大即可满足所需的 存储要求。同时,多个表的总大小也会远远低于采用单个表时的大小。本文的 数据结构则是在 的基础上再次进行改进,它为每个状态的每个分支提供了两 个侯选位置,当第一个侯选位置已经被占据后则去査看第二个候选位置是否也被使用。如果 两个候选位置均被使用,则再对该状态的所有分支进行迁移。显然,这一做法使得存储冲突 发生的概率再次降低。图是一个 和 的对比结构图。 图武获记义在线 Ilash1(com/=0 I lash (com/ =1 Hashi(cn/)=2 Hash2(cn/=3 Hash1(hp/)=0 Hash2(hp/)=1 Hash1(hk/)=1 Hash2(hk/)=2 MATA AIAO ATA1 Hash1 h Hash1 ccom SO S1 hk Hash Hash1 ch CATA ATAD S0- Hash1 Hash1 Hash1 hp/ Cn Hash2 图 和 的对比结构图 从图可以看出,由两种哈希函数提供的两个候选位貿使得 能够避免一些存储 冲突,从而提高了的利用率,所以能够大大降低存储开销。但是可能存在的问题则 是由于候选位置的存仁,当查找某个分支时可能需要进行两次查找,而这肯定会降 低查找性能。因此,本文充分的利用了的特点,即它可以多线程并行同时探测多个候 选位賀,而且多个候选位置在同一个中,这样也能更好的利用上的缓存来实现更 快的探测。 联合机制 考虑到和各自的性能特点,本文最终采用了 联合机制来实现对应 的数据结构与算法。具体步骤是,首先在上实现这一数据结构的构造算法和更 新算法,然后将 从传输到,最后在上实现数据名的查找并将结果返 回至在端,本文使用的是这一编程语言,而在端的编程语言则是 它们两者可以很好的协同处理并实现相应的数据结构与算法。 实验结果 由于)没有现实中的数据名数据,所以本文按照大多数论文的方式,在 上选取了的表作为实验数据集。基于这些数据,本文对 和 这两种结 图武获记义在线 构做了对比实验,主要集中在它们的内存开销和查找速度方面。为了观察 算法在数 据规模不断扌大的情况下的表现情况,本文对实验数据进行了分组,将数据分成相等大小的 份,每次选择前份为第次的表大小。然后再对每一次的表进行实验,最后 得到次的结果对比图。 内存 首先,来看看 算法和 算法在存储方面的性能对比。在这里,本文选用了 两个标准来分析存储性能,它们分别是存储空间大小和存储利用率。从图和图中可以明 显发现, 的存储利用率要远远高」,达到了的比例,而存储大小则只有 的五分之一左右。因此,从存储性能来看 算法要优于 算法 Mata 300 Cata 100 K-th 图存储空间大小对比图 图武获记义在线 MATA 100· CATA E0N5 20 0 10 k-th 图存储利用率对比图 查找速度 接下来,看看 的实际查找性能。同样的,本文在实验中选取了廷时和吞吐率这 两个参数作为查找性能参考标准。从图和图可以出来, 算法和 算法在延 时和吞吐率上的表现相差无几,延时都在左右,吞吐率则都在 左石。这说明 算法在查找性能上也能达到 一样的效果 MATA 106 CATA 105 104 103 102 101 100 99 98 97 K-th 图查找延时对比图 图武获记义在线 MAT 100 CATAI 90 90 70 C 10 6 k-th 图春吐率对比图 结论 本文提岀一种新的基于的数据名查找算法。它通过对 这一数据结构的改进 设计了一种新的数据结构,将单哈希策略改进成多哈希,从而为存储提供了多个侯选 位置,在不影响査找性能的基础上使得存储效率大大提髙,进而也大幅度地减少了存储开销。 这样在随着未来网终规模的不断扩大中,该算法的存储优势也将更加明显。在接下来 的研究中,本文也希望能够进一步优化算法的并行性,使得其在这一平台上取 得更好的表现。 致谢(可选 首先,要感谢我的导师张大方教授对我的悉心指导,然后我的师兄李彦彪博士也在我 的实际研究工作中帮助了我很多,再次感谢你们,止是由你们的帮助,才能有今天这样的 成果,谢谢你们! 参考文献 图武获记义在线

...展开详情
所需积分/C币:7 上传时间:2019-08-27 资源大小:446KB
举报 举报 收藏 收藏
分享 分享
论文研究-一种改进的Otsu算法研究 .pdf

一种改进的Otsu算法研究,李冰玉,彭利标, Otsu(最大类间方差)算法的一些优秀性质使得它在许多不同的图像分割系统中得到非常广泛的应用,该算法运算量不大,在一定条件下�

立即下载
论文研究-一种改进的S-MAC协议 .pdf

一种改进的S-MAC协议,周富生,陈伟,本文首先简单介绍了无线传感器网络,之后给出了无线传感器网络S-MAC协议的一种改进思路,并通过使用NS2进行仿真,验证了协议改进的�

立即下载
论文研究-一种Ad Hoc网络QoS路由算法研究 .pdf

一种Ad Hoc网络QoS路由算法研究,郑四海,李腊元,本文在研究各种接纳控制算法的基础上,改进了一种适合于Ad Hoc网络QoS路由的接纳控制算法(AAC)。改进的AAC算法能对共享的可用资源进行�

立即下载
论文研究-一种新的改进粒子群算法研究 .pdf

一种新的改进粒子群算法研究,马金玲,唐普英,研究粒子群优化算法(PSO)的收敛速度,以提高该算法性能是PSO的一个重要而且有意义的研究。Jun Sun 等人通过对PSO系统下的单个个体在�

立即下载
论文研究-一种轮廓跟踪的UPF方法 .pdf

一种轮廓跟踪的UPF方法,袁健,张文霞,针对通用目标轮廓跟踪中CONDENSATION 粒子算法的不足,提出一种轮廓跟踪的UPF方法。通过将Unscented 卡尔曼滤波器与粒子滤波的结合,并实�

立即下载
论文研究-一种对称MMSE的改进算法 .pdf

一种对称MMSE的改进算法,陶涛,,本文分析讨论了时域均衡器最小均方误差(MMSE)算法原理、特点及运算复杂度,并在次基础上提出了一种新的改进算法,使MMSE矩阵计算�

立即下载
论文研究-一种提高多普勒精度的方法 .pdf

一种提高多普勒精度的方法,廖卓,,全球定位卫星系统(GNSS)的速度测量在高动态运动环境下具有重要意义。接收机跟踪环路提供的多普勒频移是用户速度求解的重要观测��

立即下载
论文研究-一种LDO稳压器芯片的研究与设计 .pdf

一种LDO稳压器芯片的研究与设计,于飞,邹锦华,设计出一种适合便携式电子产品应用的LDO(Low-dropout voltage regulator)稳压器芯片。相比于传统的LDO稳压器芯片,新的设计在误差放大器与�

立即下载
论文研究-一种新型SQL注入攻击的研究与防范 .pdf

一种新型SQL注入攻击的研究与防范,赵阳,郭玉翠,针对一种以HTTP Headers为途径的新型SQL注入攻击进行了深入研究。通过分析具体的SQL注入实例,揭示了该新型SQL注入攻击的原理,并提出了针�

立即下载
论文研究-一种嵌入式视频监控系统 .pdf

一种嵌入式视频监控系统,刘冬,,当前有不少视频监控系统是基于GSPCA开发的,它们存在不能在本地显示视频,缺乏移动检测等图像处理功能,对于存储空间要求高等缺点�

立即下载
论文研究-一种改进的加权质心定位算法 .pdf

一种改进的加权质心定位算法,杨路,刘慧珍,无线传感网络定位算法中,节点在测量距离时受到外部环境干扰导致RSSI值大幅度波动,影响定位精度。通过对阴影模型的研究发现,节��

立即下载
论文研究-一种改进的增强型AdaBoost算法 .pdf

一种改进的增强型AdaBoost算法,李文辉,倪洪印,本文分析了传统的Adaboost算法在训练过程中可能出现的退化问题以及目标类权重分布出现过适应的现象,文章提出了一种改进的Adaboost算��

立即下载
论文研究-一种新型的LDPC译码器设计 .pdf

一种新型的LDPC译码器设计,钟贵锋,李庆,摘要:性能逼近Shannon限的低密度奇偶校验(Low-Density Parity-Check, LDPC) 纠错码,在实际应用中需要解决的问题是尽可能降低译码的复杂度。��

立即下载
论文研究-一种罗特曼透镜波束形成网络设计 .pdf

一种罗特曼透镜波束形成网络设计,曹扬,陈鹏,本文设计了一种基于等光程原理的罗特曼透镜波束形成网络。该波束形成网络中心频率20GHz,具有15个输入口,16个输出口以及4个虚端口��

立即下载
论文研究-一种基于k-means的分布式k-anonymity算法 .pdf

一种基于k-means的分布式k-anonymity算法,张琦颖,程祥,随着的大数据时代的到来,数据分享、数据发布的需求日益增加。然而未经处理发布或共享原始数据,将引起隐私泄露问题。k-anonymity匿�

立即下载
论文研究-一种基于OpenStack的云用量采集模型 .pdf

一种基于OpenStack的云用量采集模型,孙福全,宋茂强,本文提出了一种面向云环境的虚拟机用量数据采集模型,它可以采集基于OpenStack云环境中虚拟机用量信息。文章首先介绍了用量采集模型��

立即下载
论文研究-一种带唤醒电路的有源标签设计 .pdf

一种带唤醒电路的有源标签设计,余强,聂在平,本文提出了一种微波频段带唤醒电路的有源RFID标签设计。对其进行了硬件设计和相应的软件编程。CC2430的应用使得有源标签在节能的前��

立即下载
论文研究-一种大功率可调开关电源的设计 .pdf

一种大功率可调开关电源的设计,杨剑,周伟,本文给出了一种新型大功率可调开关电源的应用设计。采用Buck型开关电源拓扑,以带单路PWM输出和电流电压反馈检测MC33060为控制IC,配��

立即下载
论文研究-一种改善的HHT端点效应抑制方法 .pdf

一种改善的HHT端点效应抑制方法,张帆,廖星权,经验模态分解(EMD)是Hilbert-Huang变换(HHT)的核心算法。在EMD分解中,利用三次样条函数拟合信号上下包络在数据两端不可避免地会出��

立即下载
论文研究-一种基于引力模型的链接分析算法 .pdf

一种基于引力模型的链接分析算法,张利国,张宪超,链接分析在Web信息检索领域起着重要的作用。HITS算法是一种经典的链接分析算法。本文分析了HITS算法存在的问题,并在其基础上提出了�

立即下载