利索能及
我要发布
收藏
专利号: 2018102757955
申请人: 湖南科技大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-12-08
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于命名数据网络的Top‑k查询方法,其特征在于实施步骤包括:

1)接收上一跳的查询兴趣包,对循环或重复的查询兴趣包对应的查询兴趣包进行抑制,如果接收的查询兴趣包被抑制,则跳转执行步骤1);否则,跳转执行步骤2);

2)判断完全匹配内容存储CS是否找到匹配的Top‑k查询结果,如果找到匹配的Top‑k查询结果则跳转执行步骤3);否则,跳转执行步骤4);

3)判断Top‑k查询结果是否完备,如果Top‑k查询结果完备,则向上一跳返回完备的Top‑k查询结果,结束并退出;否则如果Top‑k查询结果不完备,则跳转执行步骤4);

4)初始化转发信息库转出接口数组变量OutfaceFIB和待定兴趣表转出接口数组变量OutfacePIT;判断完全匹配待定兴趣表PIT是否找到匹配的条目,如果找到匹配的条目,则将查询兴趣包的接收接口inface添加到匹配的条目、待定兴趣表PIT中匹配条目的Outface的值添加到待定兴趣表转出接口数组变量OutfacePIT;否则,将查询兴趣包存入待定兴趣表PIT,并设置存入条目的待定兴趣表转出接口数组变量OutfacePIT为空;

5)判断最长前缀匹配转发信息库FIB是否匹配成功,如果匹配不成功,则丢弃查询兴趣包并退出;否则,跳转执行步骤6);

6)将匹配结果存入转发信息库转出接口数组变量OutfaceFIB;

7)将转发信息库转出接口数组变量OutfaceFIB减去待定兴趣表转出接口数组变量OutfacePIT得到下一跳接口集合OUT;

8)执行本地Top‑k查询,将本地Top‑k查询得到的k个答案作为Top‑k查询结果并缓存到内容存储CS,并根据下一跳接口集合OUT将查询兴趣包分别转发至各下一跳;

9)等待下一跳返回内容数据包,当收到内容数据包时解析获取内容数据包中的Top‑k查询结果,并跳转执行步骤10);

10)将收到的Top‑k查询结果、内容存储CS中的Top‑k查询结果进行聚合处理,得到包含k个答案的新的Top‑k查询结果并替换更新内容存储CS中的缓存;

11)根据下一跳集合OUT中的下一跳是否全部返回Top‑k查询结果来更新内容存储CS中的Top‑k查询结果的完备状态,如果内容存储CS中的Top‑k查询结果尚未完备,则跳转执行步骤9);否则,跳转执行步骤12);

12)将内容存储CS中的Top‑k查询结果封装,判断完全匹配待定兴趣表PIT是否找到匹配的条目,如果找到匹配的条目,则将封装后的Top‑k查询结果转发给匹配的条目对应的上一跳;否则,丢弃查询兴趣包并退出。

2.根据权利要求1所述的基于命名数据网络的Top‑k查询方法,其特征在于,步骤1)的详细步骤包括:

1.1)接收上一跳的查询兴趣包;

1.2)判断完全匹配待定兴趣表PIT是否找到匹配的条目,如果找到匹配的条目,则将查询兴趣包携带的随机数值nonce和匹配的条目的随机数值nonce是否相同,如果随机数值nonce相同,则跳转执行步骤1.3);否则,则将查询兴趣包的接收接口inface添加到匹配的条目、待定兴趣表PIT中匹配条目的发送接口outface的值添加到待定兴趣表转出接口数组变量OutfacePIT,则跳转执行步骤2);如果没有找到匹配的条目,则将查询兴趣包存入待定兴趣表PIT,并设置存入条目的待定兴趣表转出接口数组变量OutfacePIT为空,跳转执行步骤2);

1.3)通过接收查询兴趣包的接收接口inface向上一跳发送否定应答消息NACK,收到否定应答消息NACK的上一跳在待定兴趣表PIT中删除该查询兴趣包对应的发送接口outface,如果该查询兴趣包对应的发送接口outface是该查询兴趣包的唯一的一个发送接口outface,则在待定兴趣表PIT中删除该查询兴趣包对应的条目;跳转执行步骤1)。

3.根据权利要求2所述的基于命名数据网络的Top‑k查询方法,其特征在于,步骤1)中接收的查询兴趣包包含响应策略信息字段ReStrategy,所述响应策略信息ReStrategy包含了向上一跳返回Top‑k查询结果的方式,返回Top‑k查询结果的方式分别包括三种:(1)聚合后立即响应策略IRA:每一次聚合处理后立即返回Top‑k查询结果;(2)仅响应最终聚合策略MAR‑1:仅在Top‑k查询结果完备时返回Top‑k查询结果;(3)多次聚合后响应策略MAR‑2:多次聚合处理后立即返回Top‑k查询结果且在Top‑k查询结果完备时返回Top‑k查询结果;且步骤3)中如果Top‑k查询结果不完备时:如果响应策略信息ReStrategy为聚合后立即响应策略IRA则立即向上一跳返回匹配的Top‑k查询结果,然后再跳转执行步骤4);如果响应策略信息ReStrategy为多次聚合后响应策略MAR‑2则根据聚合处理的次数对多次聚合后响应策略MAR‑2的聚合次数取模,根据取模结果是否为指定值来决定是否向上一跳返回匹配的Top‑k查询结果,然后再跳转执行步骤4);步骤11)中如果内容存储CS中的Top‑k查询结果尚未完备时:如果响应策略信息ReStrategy为聚合后立即响应策略IRA则立即向上一跳返回内容存储CS中的Top‑k查询结果,然后再跳转执行步骤9);如果响应策略信息ReStrategy为多次聚合后响应策略MAR‑2则根据聚合处理的次数对多次聚合后响应策略MAR‑2的聚合次数取模,根据取模结果是否为指定值来决定是否向上一跳返回内容存储CS中的Top‑k查询结果,然后再跳转执行步骤9)。

4.根据权利要求1所述的基于命名数据网络的Top‑k查询方法,其特征在于,步骤11)中更新内容存储CS中的Top‑k查询结果的完备状态的详细步骤包括:在待定兴趣表PIT中将该查询兴趣包对应的返回Top‑k查询结果的发送接口outface删除,如果返回Top‑k查询结果的发送接口outface已经是最后一个发送接口outface或者该查询兴趣包在待定兴趣表PIT中的条目的持续超过预设时间阈值InterestLifeTime,则删除该查询兴趣包在待定兴趣表PIT中的条目,并更新内容存储CS中的Top‑k查询结果的完备状态为完备。

5.根据权利要求1所述的基于命名数据网络的Top‑k查询方法,其特征在于,步骤10)将收到的Top‑k查询结果、内容存储CS中的Top‑k查询结果进行聚合处理的详细步骤包括:首先,根据内容存储CS中的Top‑k查询结果、收到的Top‑k查询结果两者的内容判断进行聚合处理的聚合类型,所述聚合类型包括缓存包含聚合、新到包含聚合、重叠聚合和不相交聚合四种,其中缓存包含聚合是指内容存储CS中的Top‑k查询结果包含收到的Top‑k查询结果,新到包含聚合是指收到的Top‑k查询结果包含内容存储CS中的Top‑k查询结果,重叠聚合是指内容存储CS中的Top‑k查询结果和收到的Top‑k查询结果两者部分重叠,不相交聚合是指内容存储CS中的Top‑k查询结果和收到的Top‑k查询结果两者不重叠;然后,基于不同的聚合类型进行不同的聚合处理:针对缓存包含聚合,直接将内容存储CS中的Top‑k查询结果作为聚合处理结果输出;针对新到包含聚合,直接将收到的Top‑k查询结果替换内容存储CS中的Top‑k查询结果并作为聚合处理结果输出;针对重叠聚合和不相交聚合,则将内容存储CS中的Top‑k查询结果、收到的Top‑k查询结果根据预设的评分函数进行评分,根据评分将内容存储CS中的Top‑k查询结果、收到的Top‑k查询结果两者进行快速排序,并针对快速排序的所有响应答案选择得分最高的k个响应答案作为聚合处理结果输出。

6.根据权利要求5所述的基于命名数据网络的Top‑k查询方法,其特征在于,步骤1)中接收的查询兴趣包包含评分阈值MaxScore,所述根据评分将内容存储CS中的Top‑k查询结果、收到的Top‑k查询结果两者进行快速排序之前,还包括将收到的Top‑k查询结果中包含的k个响应答案中评分大于评分阈值MaxScore的响应答案删除。

7.一种基于命名数据网络的Top‑k查询系统,包括计算机系统,其特征在于,所述计算机系统被编程以执行权利要求1~6中任意一项所述基于命名数据网络的Top‑k查询方法的步骤。