Hybrid Key Duplication Hashing Techniques for IP Address Lookup
- 1
- 2
Abstract
This In the past decade there has been an increasing need for designs to address the time and cost efficiency issues from various computer network applications such as general IP address lookup and specific network intrusion detection. Hashing techniques have been widely adopted for this purpose, among which XOR-operation-based hashing is one of most popular techniques due to its relatively small hash process delay. In most current commonly used XOR-hashing algorithms, each of the hash key bits is usually explicitly XORed only at most once in the hash process, which may limit the amount of potential randomness that can be introduced by the hashing process. In [1] a series of bit duplication techniques are proposed by systematically duplicating one row of key bits. This paper further looks into various ways in duplicating and reusing key bits to maximize randomness needed in the hashing process so as to enhance the overall performance further. Our simulation results show that, even with a slight increase in hardware requirement, a very significant reduction in the amount of hash collision can be obtained by the proposed technique.
- C. Martinez and W.-M. Lin, “Advanced Hash Algorithms with Key Bits Duplication for IP Address Lookup,” The 5th International Conference on Networking and Services, Valencia, 20-25 April 2009, pp. 137-142.
- P. Newman, G. Minshall, T. Lyon and L. Hutson, “IP Switching and Gigabit Routers,” IEEE Communications Magazine, Vol. 35, No. 1, 1997, pp. 64-69. doi:10.1109/35.568212
- O. Amble and D. E. Knuth, “Ordered Hash Tables,” Computer Journal, Vol. 17, No. 2, 1974, pp. 135-142. doi:10.1093/comjnl/17.2.135
- M. A. Ruiz-Sanchez, E. W. Biersack and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network, Vol. 15, No. 2, 2001, pp. 8-23. doi:10.1109/65.912716
- R. Jain, “A Comparison of Hashing Schemes for Address Lookup in Computer Networks,” IEEE Transactions on Communications, Vol. 40, No. 10, October 1992, pp. 1570- 1573. doi:10.1109/26.168785
- A. Moestedt and P. Sjodin, “IP Address Lookup in Hardware for High-Speed Routing,” Proceedings of IEEE Hot Interconnects 6 Symposium, Stanford, 13-15 August 1998, pp. 31-39.
- X. J. Nie, D. J. Wilson, J. Cornet, D. Damm and Y. Q. Zhao, “IP Address Lookup Using A Dynamic Hash Function,” Canadian Conference on Electrical and Computer Engineering, Saskatoon, 1-4 May 2005, pp. 1642-1647.
- S. Nilsson and G. Karlsson, “IP Address Lookup Using LC-Tries,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, June 1999, pp. 1083-1092. doi:10.1109/49.772439
- V. Srinivasan and G. Varghese, “Faster IP Lookups Using Controlled Prefix Expansion,” Proceedings of the 1998 ACM SIGMETRICS Joint International Conference on Measurement and Modeling of Computer Systems, Madison, 22-26 June 1998, pp. 1-10.
- M. Waldvogel, G. Varghese, J. Turner and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proceedings of the ACM SIGCOMM'97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Cannes, 14-18 September 1999, pp. 25- 35.
- A. Broder and M. Mitzenmacher, “Using Multiple Hash Functions to Improve IP Lookups,” 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, 22-26 April 2001, pp. 1454-1463.
- S.-H. Chung, S. Jean, H. Yoon and J.-W. Cho, “A Fast and Updatable IP Address Lookup Scheme,” International Conference on Computer Networks and Mobile Computing, Beijing, 16-19 October 2001, pp. 419-424.