(19)中华人民共和国国家知识产权局
(12)发明专利说明书 | ||
(10)申请公布号 CN 103428093 A (43)申请公布日 2013.12.04 | ||
(21)申请号 CN201310277108.0
(22)申请日 2013.07.03
(71)申请人 北京邮电大学
地址 100876 北京市海淀区西土城路10号
(72)发明人 关建峰 张宏科 许长桥 张萌 权伟 戴彧 张朝贵 韩冰洁 何云航
(74)专利代理机构
代理人
(51)Int.CI
H04L12/741
权利要求说明书 说明书 幅图 |
(54)发明名称
(57)摘要
本发明公开了一种基于名字路由前缀存储，匹配以及路由更新方法及装置，包括布隆滤波器单元，Trie单元和流行度计数单元。其中，布隆滤波器单元，根据名字名字前缀的统计特性，存储名字前缀的前m层，对到达路由器的请求名字做快速前缀匹配；Trie单元，用于存储名字前缀的后n层，对请求名字做快速后缀查询；流行度计数单元，用于统计请求名字的流行度并相应地改变布隆滤波器和Trie的存储结构。本发明利用布隆滤波器低概率的冲突与低内存特性、Trie查的快速性、并行查、真实名字前缀的统计规律以及基于流行度统计的路由更新，能够解决新型网络体系中基于名字的路由寻址问题，能够满足未来网络消耗内存小、匹配速度快、吞吐量大的要求。 | |
法律状态
法律状态公告日 | 法律状态信息 | 法律状态 |
权 利 要 求 说 明 书
1.一种基于名字路由前缀存储及匹配方法，其特征在于，路由前缀分解成二元组，分别进行存储和匹配。
2.如权利要求1所述方法，路由前缀二元组分别存储于Bloom filter单元和Trie单元，其特征包括：
A、将前缀名字分解B-prefix与T-suffix。其中，B-prefix为前缀名字的前m层，T-suffix为前缀名字后几层；
B、将B-prefix插入第m号布隆滤波器；将T-suffix插入B-prefix对应的Trie中；
C、如果前缀名字的层数n少于等于m，则将此前缀名字插入第n号布隆滤波器。
3.如权利要求2所述的方法，其特征在于，B-prefix为前缀名字的前m层，m由所有名字前缀的统计特性自适应地调整。
4.如权利要求2所述的方法，其特征在于，拥有相同层数的B-prefix对应一个布隆滤波器，例如，编号为4的布隆滤波器存储的前缀名字层数为4。
5.如权利要求2所述的方法，其特征在于，B-prefix对应的Trie，是指每个不同的B-prefix都对应一个Trie，用来存储T-suffix，T-suffix中的最后一个component所在的Trie节点中，存放着前缀名字的路由器转发端口号。
6.如权利要求1所述的方法，路由前缀匹配其特征在于：
步骤A、计算请求名字name的层数n，如果n小于等于m，则将name的前1层，前2层，……，前n层并行地在对应的布隆滤波器中查，输出查结果栈s；否则，执行步骤B；
步骤B、将name的前1层，前2层，前3层…前m层并行地在对应的布隆滤波器中查，输出查结果栈s；
步骤C、栈s如果为空，执行步骤E；如果不为空，则取栈A顶元素level，并且pop栈顶元素，取name前level层的component作为B-prefix，取name的level层之后的component作为T-suffix，在B-prefix对应的Trie中查T-suffix是否存在，如果存在，取得转发端口号ethx，执行步骤D；如果不存在，执行步骤C；
步骤D、将请求包从路由器的ethx口转发；
步骤E、将请求包从路由器的默认端口转发。
7.如权利要求5所述的方法，其特征在于，步骤A中输出查结果栈s，是指将查询结果为真的布隆滤波器的号码按从小到大的顺序存入空栈s中，比如，“www/baidu/movie/”，如果“www/”存在于1号布隆滤波器中，“www/baidu/”不存在于2号布隆滤波器中，“www/baidu/com/”存在于3号布隆滤波器中，则栈s中按从小到大存储的是：1和3，其中3为栈顶元素。
8.如权利要求5所述的方法，其特征在于，所述步骤B中的并行查，是指同时查，可用硬件实现，时间复杂度为第m号布隆滤波器的时间复杂度。
9.如权利要求5所述的方法，其特征在于，所述步骤E中的路 由器默认端口，是指没有任何前缀名字与请求名字匹配，则该请求包会被从某个固定端口转发。
10.如权利要求1所述的方法，其支持基于请求名字流行度的更新Bloom filter与Trie的方法，所述方法包括：
步骤A、将前缀匹配成功的前缀名字保存在列表L中；
步骤B、当列表L中条目数量等于X时，取出X个前缀名字的前1层作为B-prefix，统计B-prefix的个数，将每个B-prefix及其个数保存到s中；然后，取出X个前缀名字的前两层作为B-prefix，重复以上步骤，一直取到前n层为止，n为层数最多的前缀名字的层数；
步骤C、将个数超过Y的B-prefix定义为流行度比较高的前缀名字的B-prefix，并删除它们在对应的布隆滤波器和Trie中的记录，重新组建新的布隆滤波器和Trie，用于单独存放流行度较高的前缀名字。
说 明 书
<p>技术领域
本发明涉及计算机网络技术领域，特别涉及一种路由前缀匹配方法与装置。 二个字独特好听名字
背景技术
随着互联网的发展，人们对数据内容本身的需求越来越强烈。在这种背景下，传统的以主机为中心的网络体系结构已经难以满足现在互联网的发展，这导致下一代网络体系CCN（Content-Centric Networking）应运而生。与传统基于IP的网络体系不同，CCN是一种全新的以内容和信息为中心的网络体系，它使用网络用户所需内容的名字来定位数据资源，而不是使用定向IP地址。CCN中每个数据包报头中携带请求内容的名字，路由器中的转发表由若干内容名字前缀构成，转发时，需将请求内容的名字进行最长前缀匹配（LPM），与现有基于IPV4/IPV6网络转发路由表不同的地方在于：CCN每个名字前缀由几十甚至上百个字符组成，较IPV4/IPV6固定长度地址有可变的长度，这使名字前缀匹配变得复杂；另外，CCN的转发表可能远远大于当今IP的转发表，IP转发表具有400万IP前缀，而CCN可能高达10亿。
转发表条目的剧增，使得网络的吞吐量受到一定的影响，为了保证网络的性能，急需一种内存占用小，匹配时间少，路由表更新速度快，能很好的适应CCN的前缀匹配算法。
发布评论