一种基于树形数据结构的最长前缀匹配方法和装置

发明专利有效专利

申请号：
CN200810096906.2
IPC分类号：H04L12/56;G06F17/30
申请日期：
2008-05-05
申请人：
华为技术有限公司

基础信息

权利要求

说明书

PDF全文

法律信息

引证文献

著录项信息

专利名称	一种基于树形数据结构的最长前缀匹配方法和装置
申请号	CN200810096906.2	申请日期	2008-05-05
法律状态	授权	申报国家	中国
公开/公告日	2009-11-11	公开/公告号	CN101577662
优先权	暂无	优先权号	暂无
主分类号	H04L12/56 ? IPC结构图谱： H 电学 H9 电学 H04 电通信技术 H04L 数字信息的传输，例如电报通信（电报和电话通信的公用设备入H04M）〔4〕 H04L12/56 （转入H04L12/70）〔5，6〕	IPC分类号	H;0;4;L;1;2;/;5;6;;;G;0;6;F;1;7;/;3;0查看分类表>
申请人	华为技术有限公司	申请人地址	广东省深圳市龙岗区坂田华为总部办公楼变更专利地址、主体等相关变化，请及时变更，防止失效
权利人	华为技术有限公司	当前权利人	华为技术有限公司
发明人	梁军;沈士军;李猛;张娟;胡睿;龚钧
代理机构	北京集佳知识产权代理有限公司	代理人	逯长明

摘要

本发明公开了最长前缀匹配方法和装置，该方法包括：A.读取一个搜索节点；B.确定读出的搜索节点的偏移量域是否指示上一级别的节点内存在匹配的前缀，如果存在，将上一级别的节点内指向叶子节点数组的指针加上该搜索节点的偏移量域，更新当前最佳匹配指针，并执行步骤C；如果不存在，执行步骤C；C.确定该搜索节点的分支指示域和搜索关键字的对应比特匹配时，确定该搜索节点是否存在子节点；D.确定该搜索节点不存在子节点时，读取该搜索节点的内部位图，根据内部位图和搜索节点内指向叶子节点数组的指针，计算该搜索节点内存在的最长匹配前缀，更新当前最佳匹配指针，计算当前最佳匹配指针对应的叶子节点的地址。该方法可以提高查询速度。

序号	公开(公告)号	公开(公告)日	申请日	专利名称	申请人
该专利没有引用任何外部专利数据！

序号	公开(公告)号	公开(公告)日	申请日	专利名称	申请人
该专利没有被任何外部专利所引用！

我浏览过的专利

专利服务由北京酷爱智慧知识产权代理公司提供