Christopher J. Martinez
Abstract
Computer networks have continued to make substantial advances in the past couple of decades through better technologies and methodologies employed. As the usage of the networks continues to increase exponentially, high throughput of the networks has to be maintained with various performance-efficient network algorithms. IP address lookup is one of the processes, the performance of which dearly affects the overall network performance. Hashing has been widely used for fast IP address lookup due to its simplicity, but mostly assuming on hashing from an address set with uniformly distributed key values. Performance from these known hashing techniques is far from optimal due to the high nonuniformity in actual IP address distribution. In this paper, we propose a preprocessing method for the IP address databases to extract certain regularity to allow for design of more efficient hashing algorithms based on XOR operations. Simulation results show an improvement in performance ranging from 35% to 72% on randomly generated addresses and several sample IP address databases. The paper also shows that the proposed algorithms deliver comparable performance to other well-known hashing algorithms such as the CRC and RS hashing while requiring much less hardware to implement and a much shorter time to perform.
- O. Amble and D. E. Knuth, "Ordered hash tables," Comput. J., vol. 17, no. 2, pp. 135-142, 1974.Google Scholar
Cross Ref
- A. Broder and M. Mitzenmacher, "Using multiple hash functions to improve IP lookups," in Proc. IEEE INFOCOM, 2001, pp. 1454-1463.Google ScholarCross Ref
- W. E. Burr, "Cryptographic hash standards: Where do we go from here?," IEEE Security Privacy, vol. 4, no. 2, pp. 88-91, Mar.-Apr. 2006. Google ScholarDigital Library
- S.-H. Chung, J. Sungkee, H. Yoon, and J.-W. Cho, "A fast and updatable IP address lookup scheme," in Proc. ICCNMC, 2001, p. 419. Google ScholarDigital Library
- R. Jain, "A comparison of hashing schemes for address lookup in computer networks," IEEE Trans. Commun., vol. 40, no. 10, pp. 1570-1573, Oct. 1992.Google ScholarCross Ref
- D. E. Knuth, The Art of Computer Programming, 2nd ed. Reading, MA: Addison-Wesley, 1998, vol. 3, Sorting and Searching. Google ScholarDigital Library
- C. Martinez, W.-M. Lin, and P. Patel, "Optimal XOR hashing for a linearly distributed address lookup in computer networks," in Proc. Symp. Arch. Netw. Commun. Syst., Princeton, NJ, Oct. 2005, pp. 203-210. Google ScholarDigital Library
- C. Martinez and W.-M. Lin, "Adaptive hashing technique for IP address lookup in computer networks," in Proc. 14th IEEE ICON, Singapore, Sep. 2006, pp. 1-6.Google Scholar
- A. Moestedt and P. Sjodin, "IP address lookup in hardware for highspeed routing," in Proc. IEEE Hot Interconnects 6 Symp., Stanford, CA, Aug. 1998, pp. 31-39.Google Scholar
- P. Newman, G. Minshall, T. Lyon, and L. Hutson, "IP switching and gigabit routers," IEEE Commun. Mag., vol. 35, no. 1, pp. 64-69, Jan. 1997. Google ScholarDigital Library
- X. Nie, D. J. Wilson, J. Cornet, G. Damm, and Y. Zhoa, "IP address lookup using a dynamic hash function," in Proc. IEEE Elect. Comput. Eng., Canadian Conf., May 2005, pp. 1646-1651.Google Scholar
- S. Nilsson and G. Karlsson, "IP-address lookup using LC-tries," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1083-1092, Jun. 1999. Google ScholarDigital Library
- D. Pao, C. Liu, L. Yeung, and K. S. Chan, "Efficient hardware architecture for fast IP address lookup," in Proc. IEEE INFOCOM, 2002, pp. 555-5.Google Scholar
- M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, "Survey and taxonomy of IP address lookup algorithms," IEEE Netw., vol. 15, no. 2, pp. 8-23, Mar./Apr. 2001. Google ScholarDigital Library
- A. Satoh and T. Inoue, "ASIC hardware focused comparison for hash functions MD5, RIPEMD-160, and SHS," in Proc. Int. Conf. Inf. Technol., Coding Comput., Jun. 2005, pp. 90-94. Google ScholarDigital Library
- R. Sedgewick, Algorithms. Reading, MA: Addison-Wesley, 1988. Google ScholarDigital Library
- V. Srinivasan and G. Varghese, "Faster IP lookups using controlled prefix expansion," in Proc. SIGMETRICS, Madison, WI, 1998, pp. 1-10. Google ScholarDigital Library
- M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable high speed IP routing lookups," in Proc. ACM SIGCOMM, Sep. 1999, pp. 25-35. Google ScholarDigital Library
- G. B. White and M. I. Huson, "A peer-based hardware protocol for intrusion detection systems," in Proc. MILCOM, 1996, pp. 468-472.Google Scholar
- P. A. Yilmaz, A. Belenkiy, N. Uzun, N. Gogate, and M. Toy, "A trie-based algorithm for IP lookup problem," in Proc. IEEE Globecom, 2000, pp. 593-598.Google Scholar
- D. Yu, B. Smith, and B. Wei, "Forwarding engine for fast routing lookups and updates," in Proc. IEEE Globecom, 1999, pp. 1556-1564.Google Scholar
- PeerGuaridan 2, Phoenixlabs, 2007 {Online}. Available: http:// phoenixlabs.org/pg2/Google Scholar
Index Terms
- On designing fast nonuniformly distributed IP address lookup hashing algorithms
Recommendations
A fast and scalable IPv4 and 6 address lookup algorithm
Due to Internet's exponential growth in the last few years, we face two serious problems. First, the network becomes congested. Second, the number of IP addresses is not enough for distribution. For network congestion, we use fibers in the backbone of ...
IP address lookup for internet routers using balanced binary search with prefix vector
We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence ...
High-speed IP address lookup using balanced multi-way trees
Rapid growth of the Internet traffic requires more bandwidth and high-speed packet processing in the Internet routers. As one of the major packet processing performed in routers, address lookup determines an output port using the destination IP address ...
Comments