高端路由器CIDR表非关键字索引的B-Tree机制

doi:10.13190/jbupt.200905.104.duhj

北京邮电大学学报 ›› 2009, Vol. 32 ›› Issue (5): 104-108.doi: 10.13190/jbupt.200905.104.duhj

高端路由器CIDR表非关键字索引的B-Tree机制

杜慧军;杨宁

(广东技术师范学院电子与信息学院, 广州 510665)

收稿日期:2009-03-12 修回日期:1900-01-01 出版日期:2009-10-28 发布日期:2009-10-28
通讯作者: 杜慧军

A Kind of Non-Key Words Index B-Tree Mechanism in High-End Router CIDR List

DU Hui-jun,YANG Ning

(College of Electronics and Information, Guangdong Polytechnic Normal University, Guangzhou 510665, China)

Received:2009-03-12 Revised:1900-01-01 Online:2009-10-28 Published:2009-10-28
Contact: DU Hui-Jun

摘要/Abstract

摘要：

不分类的互联网协议(IP)地址方式无类别域间路由(CIDR)可以解决高端路由器中路由匹配延
迟问题. 通过对CIDR表深入分析，在参考数据库的非关键字索引方法和分割索引算法的基础
上，提出了一种满足CIDR表要求的非关键字索引的BTree算法. 该算法首先对CIDR表的全
部前缀地址集合进行分割索引，分割后，CIDR表被改变成一种BTree索引结构；然后按照I
P地址的非关键字对CIDR表进行快速查找. 仿真结果表明，本文算法更好地满足了快速查找I
P地址的需求.

关键词: 高端路由器, 无类别域间路由选择表, 索引查找算法

Abstract:

To solve the problem of route matching delay in the core routers, an unclassified Internet protocol (IP) address mode, classless inter-domain routing (CIDR), is introduced. By analyzing the CIDR list and referring to the non-keyword index method and the partitioned indexing algorithm in databases, a novel B-Tree algorithm with nonkeyword index which satisfies the requirements of the CIDR list is brought forward. This algorithm firstly makes a partitioned index on the set of all the prefix addresses in the CIDR list. Being partitioned, the CIDR list is changed into a B-Tree index structure. Then the algorithm does fast lookup in the CIDR list according to the non-keywords of the IP addresses. Simulation shows that the new algorithm meets the demand for the IP address fast lookup.

Key words: high-end router, classless inter domain routing list, index lookup algorithm

杜慧军;杨宁. 高端路由器CIDR表非关键字索引的B-Tree机制[J]. 北京邮电大学学报, 2009, 32(5): 104-108.

DU Hui-jun,YANG Ning. A Kind of Non-Key Words Index B-Tree Mechanism in High-End Router CIDR List[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(5): 104-108.

参考文献

[1] Courses E, Surveys T. High-performance TCAM-based IP lookup engines//IEEE Conference on Computer Communications Workshops 2008. New York: IEEE Press, 2008: 1-6.
[2] Lim H, Seo J, Jung Y. High speed IP address lookup architecture using hashing[J]. IEEE Communication Letters, 2003, 7(10): 502-504.
[3] He Bingsheng, Luo Qiong. Cache-oblivious query processing//Conference on Innovative Data Systems Research. California: ISI Press, 2007: 44-55.
[4] Soh S, Hiryanto L, Rai S. Efficient prefix updates for IP router using lexicographic ordering and updatable address set[J]. IEEE Transactions on Computers, 2008, 5(1): 110-125.
[5] Majumder A, Rastogi R, Vanama S. Scalable regular expression matching on data streams//Proceedings of the 2008 ACM SIGMOD International Conference. New York: ACM Press, 2008: 161-172.
[6] 刘尉悦, 王永纲, 张万生, 等. 基于Hash和二叉树的路由表查找算法[J]. 中国科学技术大学学报, 2006, 36(3): 293-296. Liu Weiyue, Wang Yonggang, Zhang Wansheng, et al. IP address lookup algorithm based on Hash and binary-trie[J]. Journal of University of Science and Technology of China, 2006, 36(3): 293-296.
[7] Luo Jin, Zu Xiaofang, Liu Shuliang, et al. Design and compressed storage of inverted index based on mixed word segmentation//WKDD 2008. New York: IEEE Press, 2008: 334-338.
[8] Chang M, Poon C K. Efficient phrase querying with common phrase index[J]. Information Processing & Management, 2008, 44(2): 756-769.
[9] Blanco R, Silvestri F. ECIR 2008 workshop on efficiency issues on information retrieval[J]. ACM SIGIR Forum, 2008, 42(1): 59-62.
[10] Chen Su, Ooi B C, Tan K L, et al. ST2B-Tree: a self-tunable spatio-temporal B⁺-Tree index for moving objects//Proceedings of the 2008 ACM SIGMOD International Conference. New York: ACM Press, 2008: 29-42.

高端路由器CIDR表非关键字索引的B-Tree机制

A Kind of Non-Key Words Index B-Tree Mechanism in High-End Router CIDR List

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价