Routing Lookup Algorithm Performance Analysis and Research

Abstract:

This paper describes several current routing lookup algorithms, to study and analysize the complexity and operating practical performance of these routing lookup algorithms. The results show that although the binary search algorithm is not greatly improved in the searching performance, but in IPv6 environment, because searching performance of multi-branch Trie tree will decrease greatly, thus the superiority of binary search algorithm will be reflected better.

• Periodical: Advanced Materials Research (Volumes 181-182)
• Pages: 109-112
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.181-182.109
• Online since: January 2011
• Authors: Xian Min Wei
• Keywords: Binary Search Algorithm, Hash Table, Multi-Branch Trie Tree, Prefix Expansion, Step Width

References

[1] M. Waldvogel, G. Varghese,J. Turner, and B. Platter. Scalable High Speed IP Routing Lookups[J]. Proceedings of ACM SIGCOMM, 2004: 25~36.

DOI: 10.1145/263109.263136

[2] V. Srinivasan. Fast and Efficient Internet Lookups[R]. PhD thesis, Washington University, (1999).

[3] Girija Narlikar, Francis Zane. Performance Modeling for Fast IP Lookups[J]. Proceeding of ACM SIGMETRICS, (2005).

DOI: 10.1145/384268.378423

[4] S. Nilsson and G. Karlsson. IP Address Lookup Using LC-Tries[J]. IEEE Journal on Selected Areas in Communications, 1999, 17(6): 1067~1082.

DOI: 10.1109/49.772439

[5] Huan Liu. Routing Table Compaction in Ternary TCAM[J]. IEEE Micro. January/February (2002).