一种支持动态名字查找的NDN网络路由转发表设计

发布时间：2022-01-01 16:13

　　路由转发表是命名数据网络转发模块中重要的组成部分,转发表不仅要能被快速构建,还要支持高速的动态名字查找.所谓动态查找,是指当进行名字查找时,转发表还需同时支持表项的插入、更新和删除操作.设计二者兼顾的转发表仍是一大挑战,当前的研究成果主要是通过先构建路由表,再新建一个路由表索引来实现快速的名字查找,但对于高速动态名字查找效果仍然不佳.在本文中,我们将改进后的自适应基数树融合到转发表中,使转发表能利用基数树的特点,实现快速构建和动态名字查找,这种新的转发表称为自索引转发表.实验评估表明,自索引转发表有效提升了转发表的构建速度,保证了动态名字查找的效率,并在一定程度上节省了新建额外索引的内存开销. 

【文章来源】：小型微型计算机系统. 2017,38(06)北大核心CSCD

【文章页数】：6 页

【部分图文】：

一个简单的基数树

通过路径遍历将key值还原出来．2．2AＲT数据结构原始基数树的中间节点大小是固定的，即每个节点具有相同个数的指针，为保证每个字符都能正确指向下一个节点，通常中间节点会很大，例如生成ASCII字符集的基数树，每个中间节点至少需要128个指针，称之为Node128．当数据集过大时，随着插入元素的增加，基数树的内存开销也会急剧增加，同时由于每个节点的分支过多，插入和查找效率也会下降．AＲT是对基数树的改进，其优势在于中间节点大小是可以自动调节的，这样不仅节省了内存开销，还能提高元素的插入和查找效率．图2AＲT中间节点的转化过程Fig．2ConversionprocessofAＲT'sinnernodeAＲT中间节点从小到大排列分别为:Node4、Node16、Node48和Node256．Node4节点具有4个指向下个节点的指针，当指针分配完时，Node4节点将自动转化成拥有16个指针的Node16节点，以满足更多元素插入的需要;当Node16节点指针数少于4个时，节点又会转变为Node4，以节省内存空间．与此类似，Node48和Node256具有相同的功能，整个节点的转化过程如图2所示．AＲT的叶子节点仍用来存储key值对应的value值．2．3AＲT基本操作AＲT的四个基本操作分别是:insert、lookup、update和de-lete．在操作描述过程中使用到的参数定义如下:定义1．＜Kn，V＞，Kn为包含n个字符的key值，字符分别为c1，c2，．．．ci，．．．cn，ci代表Kn的第i个字符;V为对应的value值;定义2．Nj，为AＲT中间节点，其中j为节点Nj的标识;定义3．Ｒ，为AＲT的根节点，Ｒ本质上仍是一个中间节点，设Ｒ的节点标识为N0;定义4．L，为AＲT叶子节点，存储对应的value值．2．3．1Insert(插入)插入一个键值对＜Kn，V＞的具体过程如下:①从根节点?

SIF的构建Fig．3ConstructionofSIF

【参考文献】：
期刊论文
[1]信息中心网络研究综述[J]. 夏春梅,徐明伟.  计算机科学与探索. 2013(06)



本文编号：3562436