A longest prefix first search tree for IP lookup
作者： Lih-Chyau Wuu , Kuo-Ming Chen , Tzong-Jye Liu
关键词: Ternary search tree 、 Hop (networking) 、 Loose Source Routing 、 Static routing 、 Network packet 、 Fractal tree index 、 Left-child right-sibling binary tree 、 Virtual routing and forwarding 、 Computer science 、 Routing table 、 Tree (data structure) 、 Supernetwork 、 Computer network 、 Longest prefix match 、 Trie 、 Search tree 、 Router 、 IP forwarding
摘要: One of the key design issues for IP routers is lookup mechanism. an important action in router that to find next hop each incoming packet with a longest-prefix-match address routing table. In this paper, we put table on longest prefix first search tree. The tree constructed as heap by length. That makes executing have minimal number memory accesses compared Trie [Sklower, K 1991], Patricia [Nilsson, S 1999] and Prefix [Berger, M 2003]. Some nodes our can contain two entries reduce nodes. For example, 138286 be stored 132050 Furthermore, proposed scheme updated without being reconstructed from scratch when changed, it applied both IPv4 IPv6 routers.
sci-hub.se 参考文章(9)
Y. Rekhter, T. Li, An Architecture for IP Address Allocation with CIDR RFC. ,vol. 1518, pp. 1- 27 ,(1993)
M. Berger, IP lookup with low memory requirement and fast update high performance switching and routing. pp. 287- 291 ,(2003) , 10.1109/HPSR.2003.1226720
V. Fuller, K. Varadhan, J. Yu, T. Li, Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy RFC 1519. ,vol. 1519, pp. 1- 24 ,(1993)
S. Nilsson, G. Karlsson, IP-address lookup using LC-tries IEEE Journal on Selected Areas in Communications. ,vol. 17, pp. 1083- 1092 ,(1999) , 10.1109/49.772439
Mikael Degermark, Andrej Brodnik, Svante Carlsson, Stephen Pink, Small forwarding tables for fast routing lookups acm special interest group on data communication. ,vol. 27, pp. 3- 14 ,(1997) , 10.1145/263105.263133
P. Gupta, S. Lin, N. McKeown, Routing lookups in hardware at memory access speeds international conference on computer communications. ,vol. 3, pp. 1240- 1247 ,(1998) , 10.1109/INFCOM.1998.662938
Lih-Chyau Wuu, Shou-Yu Pin, A fast IP lookup scheme for longest-matching prefix international conference on computer networks and mobile computing. pp. 407- 412 ,(2001) , 10.1109/ICCNMC.2001.962625
Shi-Ming Zhao, Nen-Fu Huang, A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers IEEE Journal on Selected Areas in Communications. ,vol. 17, pp. 1093- 1104 ,(1999) , 10.1109/49.772440
Mikael Degermark, Andrej Brodnik, Svante Carlsson, Stephen Pink, Small forwarding tables for fast routing lookups Computer Communication Review. ,(1997) , 10.1145/263109.263133