No Access

GENETIC-ALGORITHM MEMORY MINIMISATION FOR DESIGNING RECONFIGURABLE IP ADDRESS LOOKUP ENGINE

SAEED SHAMSHIRI

Electrical and Computer Engineering Department, University of Tehran, Tehran, 14395/515, Iran

Search for more papers by this author

and

S. MEHDI FAKHRAIE

Electrical and Computer Engineering Department, University of Tehran, Tehran, 14395/515, Iran

Search for more papers by this author

https://doi.org/10.1142/S1469026805001507Cited by:0 (Source: Crossref)

Abstract

IP address lookup engine is the beating heart of a router. For meeting the requirements of a desirable high-speed router, speed, memory consumption, scalability, and reconfigurability of its IP lookup engine are critical. This paper uses a genetic-algorithm approach to optimise the structure of fixed-stride multibit-trie IP lookup methods. In this work, the genetic algorithm is used first in the design phase as an offline optimisation mechanism. This nature-inspired simulation finds the most memory-efficient configuration of IP address segmentation for a fixed number of address segments. Then, for adapting to network variations, the proposed method dynamically changes the number of address segments to compromise between speed and memory consumption. Each time the number of segments changes, an online genetic program is run to optimise the segmentation. Therefore, the lookup engine reconfigures itself to cover more prefixes during the time. The reconfigurability in response to the network variations, and scalability to the number of prefixes improves the life time of a router that uses this method.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

M. A. Ruiz-Sanchez, E. W. Biersack and W. Dabbous, IEEE Network 15(2), 8 (2001), DOI: 10.1109/65.912716. Crossref, Google Scholar
D. R. Morrison, J. ACM 15(4), 514 (1968), DOI: 10.1145/321479.321481. Crossref, Google Scholar
K. Sklower, A tree-based packet routing table for Berkeley UNIX, Proc. 1991 Winter Usenix Conf. (1991) pp. 93–99. Google Scholar
P. Gupta, S. Lin and N. McKeown, Routing lookups in hardware at memory access speeds, Proc. IEEE INFOCOM '98 pp. 1240–1247, DOI: 10.1109/INFCOM.1998.662938. Google Scholar
T. Henriksson and I. Verbauwhede, Fast IP address lookup engine for SOC integration, Proc. Design and Diganostics of Electronic Cricuits and Systems pp. 200–210. Google Scholar
P. A. Yilmaz, A. Belenkiy and N. Uzun, A trie-based algorithm for IP lookup problem, IEEE Global Telecommunications Conference, GLOBECOM 20001 pp. 593–598, DOI: 10.1109/GLOCOM.2000.892085. Google Scholar
A. L. Buchsbaumet al., ACM J. Experimental Algorithmics 8, (2003), DOI: 10.1145/996546.996550. Google Scholar
V. Srinivasan and G. Varghese, Fast address lookups using controlled prefix expansion, Proc. ACM SIGMETRICS pp. 1–11. Google Scholar
C.-C. You, Y.-S. Chu, C.-F. Li, and H.-K. Su, Fast IP routing lookups and updates in hardware (2002) . Google Scholar
D. Paoet al., IEE Proceedings-Computers and Digital Techniques 150(1), 43 (2003), DOI: 10.1049/ip-cdt:20030082. Crossref, Google Scholar
D. E. Tayloret al., IEEE J. Selected Areas in Communications 21(4), (2003), DOI: 10.1109/JSAC.2003.810507. Google Scholar
S.-H. Oh and J.-S. Ahn, Bit-map trie: A data structure for fast forwarding lookups, IEEE Global Telecommunications Conference, GLOBECOM 2001 pp. 1872–1876, DOI: 10.1109/GLOCOM.2001.965899. Google Scholar
H. Michael Ji and R. Srinivasan, Fast IP routing lookup with configurable processor and compressed routing table, IEEE Global Telecommunications Conference, GLOBECOM 2001 pp. 2373–2377, DOI: 10.1109/GLOCOM.2001.966203. Google Scholar
M. Degermarket al., Small forwarding tables for fast routing lookups, Proc. SIGCOMM. 1997 Symposium pp. 3–14, DOI: 10.1145/263105.263133. Google Scholar
K. Seppanen, WSEAS Trans. Commun. 1(1), 76 (2002). Google Scholar
N.-F. Huanget al., A fast IP routing lookup scheme for gigabit switching routers, Proc. IEEE INFOCOM pp. 1429–1436. Google Scholar
S. Nilsson and G. Karlsson, Fast address lookup for internet routers, Proc. IFIP 4th Int. Conf. Broadband Communications (1998) pp. 11–22. Google Scholar
S. Nilsson and G. Karlsson, IEEE JSAC 17(6), 1083 (1999), DOI: 10.1109/49.772439. Google Scholar
G. Cheung and S. McCanne, Optimal routing table design for IP address lookups under memory constraints, Proc. Conf. Comp. Commun. IEEE Infocom pp. 1437–1444. Google Scholar
S. Sahni and K. S. Kim, Efficient construction of variable-stride multibit tries for IP lookup, Proc. IEEE Symp. Appl. Internet, SAINT (2002) pp. 220–229, DOI: 10.1109/SAINT.2002.994482. Google Scholar
V. Srinivasan and G. Varghese, ACM Trans. Comput. Syst. 1 (1999), DOI: 10.1145/296502.296503. Google Scholar
M. Waldvogelet al., Scalable high speed IP routing lookups, Proc. ACM SIGCOMM '97 pp. 25–36, DOI: 10.1145/263109.263136. Google Scholar
A. Broder and M. Mitzenmacher, Using multiple hash functions to improve IP lookups, Proc. IEEE INFOCOM 2001 (2001) pp. 1454–1463, DOI: 10.1109/INFCOM.2001.916641. Google Scholar
S. Dharmapurikar, P. Krishnamurthy and D. E. Taylor, Longest prefix matching using bloom filters, Proc. SIGCOMM 2003 pp. 25–29, DOI: 10.1145/863955.863979. Google Scholar
H. Liu, IEEE Micro 22(1), 58 (2002), DOI: 10.1109/40.988690. Google Scholar
F. Zane, G. Narlikar and A. Basu, CoolCAMs: power-efficient TCAMs for forwarding engines, IEEE INFOCOM1 (2003) pp. 42–52. Google Scholar
A. J. McAuley and P. Francis, Fast routing table lookup using CAMs, Proc. IEEE INFOCOM pp. 1382–1391, DOI: 10.1109/INFCOM.1993.253403. Google Scholar
K. Zheng et al. , An ultra high throughput and power efficient TCAM-based IP lookup engine , Proc. IEEE INFOCOM , DOI: 10.1109/INFCOM.2004.1354607 . Google Scholar
V. C. Ravikumar and R. N. Mahapatra, IEEE Micro 24(2), 60 (2004), DOI: 10.1109/MM.2004.1289292. Crossref, Google Scholar
D. Antos, Overview of data structures in IP lookups, CESNET Technical Report, September 2002 . Google Scholar
R. L. Haupt and S. E. Haupt , Practical Genetic Algorithms , 2nd edn. ( Wiley-Interscience , 2004 ) . Google Scholar
M. Mitchell , An Introduction to Genetic Algorithms (Complex Adaptive Systems) ( The MIT Press , 1998 ) . Crossref, Google Scholar
BGP routing table analysis reports: http://bgp.potaroo.net/index-bgp.html, retrieved on 16 July 2004 . Google Scholar
BGP routing table analysis reports: http://bgp.potaroo.net/as1221/bgp-active.html, retrieved on 5 April 2005 . Google Scholar