IP lookup with low memory requirement and fast update
作者： M. Berger
DOI: 10.1109/HPSR.2003.1226720
关键词:
摘要: The paper presents an IP address lookup algorithm with low memory requirement and fast updates. scheme, which is denoted prefix-tree, uses a combination of trie tree search, efficient in usage because the contains exactly one node for each prefix routing table. time complexity update operations prefix-tree. operation basic binary prefix-tree may require that high number nodes be traversed. improvements to decrease time, including shortcut tables multi-bit trees. compared path compressed using prefixes from real
sci-hub.se 参考文章(7)
Robert Sedgewick, Algorithms in C ,(1990)
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
M.A. Ruiz-Sanchez, E.W. Biersack, W. Dabbous, Survey and taxonomy of IP address lookup algorithms IEEE Network. ,vol. 15, pp. 8- 23 ,(2001) , 10.1109/65.912716
Martina Zitterbart, High–performance routing–table lookup Philosophical Transactions of the Royal Society A. ,vol. 358, pp. 2217- 2231 ,(2000) , 10.1098/RSTA.2000.0643
M. Uga, K. Shiomoto, A fast and compact longest match prefix look-up method using pointer cache for very long network address international conference on computer communications and networks. pp. 595- 602 ,(1999) , 10.1109/ICCCN.1999.805579
Craig Labovitz, G. Robert Malan, Farnam Jahanian, Internet routing instability acm special interest group on data communication. ,vol. 27, pp. 115- 126 ,(1997) , 10.1145/263105.263151
Thomas M. Chen, Stephen S. Liu, ATM Switching Systems ,(1995)