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

doi:10.13190/jbupt.200905.104.duhj

JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM ›› 2009, Vol. 32 ›› Issue (5): 104-108.doi: 10.13190/jbupt.200905.104.duhj

• Reports • Previous Articles Next Articles

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

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

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.

References

[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.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments