A Scalable Exact matching in Balance Tree Scheme for IPv6 Lookup
Qiong Sun, Xiaoyu Zhao, Xiaohong Huang, Wenjian Jiang, Yan Ma · 2007
Recently, the significantly increased IPv6 address length has posed a greater challenge on wire-speed router for IP lookup. As a result, even the most efficient IPv4 lookup scheme can not meet the demand in IPv6. In this paper, we make a thorough study of real world IPv4/IPv6 routing tables and find out the useful characteristic of leaf nodes for the first time. The leaf nodes can be arranged in a single balance tree and thus change the LPM (longest prefix matching) model to exact matching one in routing lookup. This exact matching model can not only reduce the number of searching keys, but can also reduce the memory cost and support fast update. What's more, the searching procedure can stop immediately when meeting a match. The balance tree in our scheme is a general concept. Here, we implement with three typical trees: B-tree, red black tree and avl tree and make a detailed comparison from every aspect. The experimental results show that its average lookup speed and memory cost is less than one third of the newly proposed rangebased algorithm PIBT[1]. And among these three balance tree schemes, avl tree has the best lookup speed and memory consumption while B-tree scheme has the least update time.