Hybrid Key Duplication Hashing Techniques for IP Address Lookup

Rujiroj Tiengtavat, Wei-Ming Lin

.

DOI: 10.4236/ijcns.2011.45037                

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.

Keywords

Hash Algorithm, IP Address Lookup, Intrusion Detection

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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.
[2]	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
[3]	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
[4]	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
[5]	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
[6]	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.
[7]	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.
[8]	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
[9]	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.
[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.
[11]	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.
[12]	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.
[13]	D. Yu, B. Smith and B. Wei, “Forwarding Engine for Fast Routing Lookups and Updates,” Global Telecommunications Conference, Rio de Janeireo, 5-9 December 1999, pp.1556-1564.
[14]	C. Martinez, D. Pandya and W.-M. Lin, “On Designing Fast Non-Uniformly Distributed IP Address Lookup Hash- ing Algorithms,” IEEE/ACM Transactions on Networking, Vol. 17, No. 6, December 2009, pp. 1916-1925. doi:10.1109/TNET.2009.2014949
[15]	D. Pao, C. Liu, L. Yeung and K. S. Chan, “Efficient Hardware Architecture for Fast IP Address Lookup,” IEEE Proceedings of Computers and Digital Techniques, Vol. 150, No. 1, 2003, pp. 43-52. doi:10.1049/ip-cdt:20030082
[16]	P. A. Yilmaz, A. Belenkiy, N. Uzun, N. Gogate and M. Toy, “A Trie-Based Algorithm for IP Lookup Problem,” Global Telecommunications Conference, San Francisco, 27 November - 1 December 2000, pp. 593-598.
[17]	R. Tiengtavat and W.-M. Lin, “Advanced Hashing with Hybrid Key Duplication for IP Address Lookup,” The 9th IEEE International Symposium on Network Computing and Applications, Cambridge, 15-17 July 2010, pp. 261- 264.
[18]	C. Martinez and W.-M. Lin, “Adaptive Hashing Technique for IP Address Lookup in Computer Networks,” 14th IEEE International Conference on Networks, Singapore, 13-15 September 2006, pp. 198-203. doi:10.1109/ICON.2006.302586
[19]	D. Pandya, C. Martinez, W.-M. Lin and P. Patel, “Advanced Hashing Techniques for Non-Uniformly Distributed IP Address Lookup,” 3rd IASTED International Conference on Communications and Computer Networks, Lima, 4-6 October 2006, pp. 46-51.
[20]	PeerGuaridan 2, 2007. http://phoenixlabs.org/pg2/