发明名称 |
一种基于两端限定双向链表子树的快速便利算法 |
摘要 |
本发明提供一种基于两端限定双向链表子树的快速便利算法,其包括如下步骤:步骤1,构建双向链表;步骤2,构建哈希表;步骤3,接收并处理兴趣包。与现有的技术相比,本发明的有益效果是:在遍历某颗子树的节点的时候,传统的算法销量地下,本文采用双向链表和Hashtable结合的方式,可以快速的查询出一个树的其实节点和结束节点,能实现添加O(1),删除O(1),查询O(n)。 |
申请公布号 |
CN105635001A |
申请公布日期 |
2016.06.01 |
申请号 |
CN201511032308.5 |
申请日期 |
2015.12.30 |
申请人 |
天津盛购科技发展有限公司 |
发明人 |
陈炳福;钟鑫;蒋彬;陈浩 |
分类号 |
H04L12/947(2013.01)I |
主分类号 |
H04L12/947(2013.01)I |
代理机构 |
|
代理人 |
|
主权项 |
一种基于两端限定双向链表子树的快速便利算法,其特征在于,包括如下步骤:步骤1,构建双向链表:用内容中心网络结点中的所有内容名字,建立内容中心网络中网络结点分段前缀树;用内容中心网络结点的分段前缀树,建立内容中心网络结点分段前缀树中结点的双向链表;步骤2,构建哈希表:将内容中心网络结点的内容缓存、待定兴趣表、转发信息表、分段前缀树以及双向链表中的所有内容名字均存储到哈希表中,完成内容中心网络中网络结点哈希表的构建;步骤3,接收并处理兴趣包:步骤31,采用哈希算法,计算接收兴趣包的内容名字的哈希值,将哈希值带入哈希表中查找哈希表的结点,将查找到的结点作为当前结点,将兴趣包的内容名字作为当前内容名字前缀;步骤32,判断哈希表中是否存在兴趣包的内容名字,若不存在,则执行步骤37,否则,执行步骤33;步骤33,当前结点的内容缓存标志位为真时,根据接收兴趣包的接口,发送当前结点对应的数据包,结束兴趣包的处理;步骤34,当前结点中的双向链表不为空时,取当前结点的双向链表中第一个结点为当前结点,执行步骤步骤33;步骤35,当前结点的待定兴趣表标志位为真时,添加待定兴趣表项,将兴趣包添加到待定兴趣表中,结束兴趣包的处理;步骤36,判断当前结点的转发信息表标志位是否为真,若是,则将当前结点的转发信息表接口列表复制到待转发接口列表中,删除待转发接口列表中接收兴趣包的接口,从待转发接口列表中的接口发送兴趣包,清空待转发接口列表,同时添加待定兴趣表项,结束兴趣包的处理;否则,丢弃兴趣包,结束兴趣包的处理;步骤37,去掉当前内容名字前缀中的最后一块,作为当前内容名字前缀;步骤38,当前内容名字前缀为空时,丢弃兴趣包,结束兴趣包的处理;步骤39,采用哈希算法,计算当前内容名字前缀的哈希值,将哈希值带入哈希表中查找哈希表结点,将查找到的哈希表结点作为当前结点,当前结点的转发信息表标志位为假时,执行步骤37;步骤40,当前结点的转发信息表标志位为真时,将当前结点的转发信息表接口列表复制到待转发接口列表中,删除待转发接口列表中接收兴趣包的接口,从转发接口列表中的接口发送兴趣包,清空待转发接口列表,同时添加待定兴趣表项,结束兴趣包的处理。 |
地址 |
300384 天津市南开区华苑产业区桂苑路13号2号楼2门1303单元 |