International Journal of Computer Networks and Applications (IJCNA)

Published By EverScience Publications

ISSN : 2395-0455

MENU
International Journal of Computer Networks and Applications (IJCNA)

International Journal of Computer Networks and Applications (IJCNA)

Published By EverScience Publications

ISSN : 2395-0455

IP Address Lookup in an IP Router Based On a Reorganized Binary Prefixes Value Tree (RBPVT)

Author NameAuthor Details

Haouassi Hichem, Maarouk Toufik Mesaaoud, Mahdaoui Rafik

Haouassi Hichem[1]

Maarouk Toufik Mesaaoud[2]

Mahdaoui Rafik[3]

[1]Univ Khenchela, Fac. ST, ICOSI Lab., BP 1252 El Houria, 40004 Khenchela, Algeria

[2]Univ Khenchela, Fac. ST, ICOSI Lab., BP 1252 El Houria, 40004 Khenchela, Algeria

[3]Univ Khenchela, Fac. ST, ICOSI Lab., BP 1252 El Houria, 40004 Khenchela, Algeria

Cite this Article

DOI: -

Pages : 9 - 15

 Download PDF

4761

Views

Abstract

IP address lookup to route data packets is an important function in a router and improving this function improves the overall performance of the router. From the data structures used for the prefixes representation, there are the trees that represent prefixes with their binary values. However, this data structure requires an improvement because of the longest prefix function search complexity. Our approach is used to improve the routing information search time in the prefixes values binary tree by periodically reorganizing the tree according to the use of prefixes; the most recently used prefixes are stored in the higher levels of the reorganized binary prefixes value tree (RBPVT) which improves the data packets routing time. The tests and evaluation of the access memory number of the longest prefix match search algorithm shows that the IP address lookup algorithm based on our RBPVT tree improves the performance of the IP routers in terms of average memory access number.

Index Terms

IP routers

IP address lookup algorithm

CIDR

binary prefixes value tree

Reference

  1. 1.
    Y.P. Dalal, U.D. Jha, R.K., "Security Comparison of Wired and Wireless Network with Firewall and Virtual Private Network (VPN)," in Recent Trends in Information, Telecommunication and Computing (ITC), 2010.
  2. 2.
    B. Ramakrishnan , S. R. Sreedivya , M. Selvi , “Adaptive Routing Protocol based on Cuckoo Search algorithm (ARP-CS) for secured Vehicular Ad hoc network (VANET)”, International Journal of Computer Networks and Applications (IJCNA) Volume 2, Issue 4, pp 173—178, 2015.
  3. 3.
    R. Vinuraj, SJ. Weta, “Application of Modified ACO Meta heuristic in Spray and Wait Routing”, International Journal of Computer Networks and Applications (IJCNA) Volume 2, Issue 5, pp. 232—241. 2015.
  4. 4.
    Antos, D.: Overview of data structures in IP lookups. CESNET Tchnical Report, (2002).
  5. 5.
    Hyesook, L., and Nara L.: Survey and Proposal on Binary Search Algorithms for Longest Prefix Match, IEEE COMMUNICATIONS SURVEYS & TUTORIALS, Vol. 14, No. 3, pp. 681—697, (2012).
  6. 6.
    T. Yang, G. Xie, Y. Li, Q. Fu, A. X. Liu, Q. Li, and L. Mathy. Guarantee IP Lookup Performance with FIB Explosion. In ACM SIGCOMM, pp. 39–50, 2014.
  7. 7.
    H. Lim, K. Lim, N. Lee, and K.-H. Park. On adding bloom filters to longest prefix matching algorithms. IEEE Transactions on Computers (TC), 63(2): pp.411–423, 2014.
  8. 8.
    S. V. Limkar, R. K. Jha, and S. Pimpalkar, “Ipv6: issues and solution for next millennium of internet,” in Proceedings of the International Conference & Workshop on Emerging Trends in Technology, ser. ICWET ’11. New York, NY, USA: ACM, 2011, pp. 953–954.
  9. 9.
    Wuu, L.C., Liu, T.J., Chen, K.M.: A longest prefix first search tree for IP lookup. Computer Networks, Vol. 51, Issue. 12, pp. 3354--3367 (2007).
  10. 10.
    Moestedt, A., Sjodin, P.: IP address lookup in hardware for high speed routing. Hot Interconnects VI, (1998).
  11. 11.
    Srinivasan, V., Varghese, G.: Fast address lookups using controlled prefix Expansion. Proceedings of ACM Sigmetrics, Vol. 17, Issue. 1, pp. 1--40. (1999).
  12. 12.
    Nilsson, S., Karlsson, G.: IP-address lookup using LC-Tries. IEEE Journal on selected areas in communications, Vol.17, Issue. 6, pp. 1083--1092. (1999).
  13. 13.
    Ravikumar, V.C., Mahapatra, R., Liu, J.C.: Modified LC-Trie based efficient routing lookup. Proceedings of the 10th IEEE MASCOTS 02, pp. 177 --182. (2002).
  14. 14.
    Morrison, D.R.: PATRICIA - practical algorithm to retrieve information coded in alphanumeric. ACM, Vol. 15, No. 14, pp. 514--34. (1968).
  15. 15.
    Lim, H., Mun, J.: An efficient IP address lookup algorithm using a priority-trie. IEEE, Global Telecommunications Conference, pp. 1--5. (2006).
  16. 16.
    Houassi, H., Bilami, A.: IP address lookup algorithm using a dynamic content binary trie. IRECOS, Vol. 5, NO 3, pp. 337--341. (2010).
  17. 17.
    Lampson, B. Srinivasan, V., Varghese, G.: IP lookups using multiway and multicolumn search. IEEE/ACM Networking, Transactions, Vol. 7, Issue. 3, pp. 1248--1256. (1999)
  18. 18.
    Suri, S., Varghese, Warkhede, G. P.: Multiway range trees: Scalable IP lookup with fast updates. IEEE, GLOBECOM '01. Vol. 3, pp. 1610--1614. (2001).
  19. 19.
    Lu, H., Sahni, S.: A B-Tree dynamic router-table design. IEEE Computers Transactions, Vol.54, Issue: 7, pp. 813--823. (2005).
  20. 20.
    Li, Y.K., Pao, D.: Address lookup algorithms for IPv6., IEE Proceding on Communication, Vol. 153, Issue. 6, pp. 909 --918. (2006).
  21. 21.
    Sun, Q., Zhao, X., Huang, X., Jiang, W., Ma1, Y.: Scalable exact matching in balance tree scheme for IPv6 lookup. IPv6'07, Kyoto, Japan, Copyright ACM 978-1-59593-713. (2007).
  22. 22.
    Yazdani N., Min, P.S.: Fast and scalable schemes for the IP address lookup problem. Proceedings of the IEEE Conference on High Performance Switching and Routing, Vol.3, pp. 1610--1614. (2000).
  23. 23.
    Yim, C., Lee, B., Lim, H.: Efficient binary search for IP address lookup. IEEE Communications Letters, Vol. 9, No. 7, pp. 652--654. (2005).
  24. 24.
    Lim, H., Lee, B., Kim, W. J.: Binary searches on multiple small trees for IP address lookup. IEEE Communications Letters, Vol. 9, No. 1, pp. 75--77. (2005).
  25. 25.
    Lim, H., Kim,W., Lee, B.: Binary search in a balanced tree for IP address lookup. Proceding of IEEE HPSR2005, pp. 490--494. (2005).
  26. 26.
    Wuu, L.C., Liu,T.J., Chen, K.M.: A longest prefix first search tree for IP lookup. Computer Networks, Vol. 51, Issue. 12, pp. 3354--3367. (2007).
  27. 27.
    Lim, H., Kim, H. G.: IP address lookup for Internet routers using balanced binary search with prefix vector. IEEE Transactions on communications, Vol. 57, No. 3, pp. 618--621. (2009).
SCOPUS
SCImago Journal & Country Rank

Announcements

Archives

Downloads

Contact Us

Dr.M. Milton Joe
EverScience Publications,
Nagercoil, Tamilnadu,India

Talk to Us

+91 9442777224

Email Us

editor@ijcna.org

info@ijcna.org

info@everscience.org

Quick Links

Follow Us

Copyright © 2023; EverScience Publications

Designed & Maintained By Shiro Software Solutions