CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Memory Efficient IPV4/V6 Lookup using Path Compression

Published on April 2012 by C. Shalini, D. Shalini Punithavathani
journal_cover_thumbnail

International Conference in Recent trends in Computational Methods, Communication and Controls
Foundation of Computer Science USA
ICON3C - Number 8
April 2012
Authors: C. Shalini, D. Shalini Punithavathani
f1dac89e-298d-4e71-b573-91ddc748837b

C. Shalini, D. Shalini Punithavathani . Memory Efficient IPV4/V6 Lookup using Path Compression. International Conference in Recent trends in Computational Methods, Communication and Controls. ICON3C, 8 (April 2012), 9-12.

@article{
author = { C. Shalini, D. Shalini Punithavathani },
title = { Memory Efficient IPV4/V6 Lookup using Path Compression },
journal = { International Conference in Recent trends in Computational Methods, Communication and Controls },
issue_date = { April 2012 },
volume = { ICON3C },
number = { 8 },
month = { April },
year = { 2012 },
issn = 0975-8887,
pages = { 9-12 },
numpages = 4,
url = { /proceedings/icon3c/number8/6058-1059/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference in Recent trends in Computational Methods, Communication and Controls
%A C. Shalini
%A D. Shalini Punithavathani
%T Memory Efficient IPV4/V6 Lookup using Path Compression
%J International Conference in Recent trends in Computational Methods, Communication and Controls
%@ 0975-8887
%V ICON3C
%N 8
%P 9-12
%D 2012
%I International Journal of Computer Applications
Abstract

With the rapid growth of the Internet, IP-lookup becomes the bottle-neck in network traffic management. Therefore, the design of high speed IP routers has been a major area of research. The focus of this paper is on achieving significant reduction in memory requirements for the longest prefix-match operation needed in IPv4/v6 lookups. The Longest Prefix Matching (LPM) is one of the problems in the uni-bit trie representation, in which the number of nodes and the memory requirement is high for IP lookup. To solve this problem we propose a classic trie-based approach in IP lookup. We propose an algorithm to compress the uni-bit-trie representation of a given routing table by using single-prefix distance bounded path compression algorithm. This algorithm determines the optimal maximum skip distance at each node of the trie to minimize the total memory requirement

References
  1. Hoang Le, Weirong Jiang Juniper, Viktor K. Prasanna, Memory-Ef?cient IPv4/v6 Lookup on FPGAs Using Distance-Bounded Path Compression. IEEE International Symposium on Field-Programmable Custom Computing Machines, 2011, 242-249.
  2. H. Le, W. Jiang, and V. K. Prasanna. A sram-based architecture for trie-based ip lookup using fpga. In Proc. FCCM '08, 2008.
  3. M. Behdadfar, H. Saidi, H. Alaei, and B. Samari. Scalar prefix search - a new route lookup algorithm for next generation internet. In Proc. INFOCOM '09, 2009.
  4. D. R. Morrison. Patricia—practical algorithm to retrieve information coded in alphanumeric. J. ACM, 15(4):514–534, 1968.
  5. K. Sklower. A tree-based packet routing table for berkeley unix. In Winter Usenix Conf. , pages 93–99, 1991.
  6. F. Baboescu, D. M. Tullsen, G. Rosu, and S. Singh. A tree based router search engine architecture with single port memories. In Proc. ISCA '05, pages 123–133, 2005.
  7. A. Basu and G. Narlikar. Fast incremental updates for pipelined forwarding engines. IEEE/ACM Trans. Netw. , 13:690–703, June 2005.
  8. H. Song, M. S. Kodialam, F. Hao, and T. V. Lakshman. Scalable ip lookups using shape graphs. In Proc. ICNP '09, 2009.
  9. I. Sourdis, G. Stefanakis, R. de Smet, and G. N. Gaydadjiev. Range tries for scalable address lookup. In Proc. ANCS '09, 2009.
  10. M. Wang, S. Deering, T. Hain, and L. Dunn. Non-random generator for ipv6 tables. In HOTI '04, pages 35–40, 2004.
  11. R. Sangireddy, N. Futamura, S. Aluru, and A. K. Somani. Scalable, memory efficient, high-speed ip lookup algorithms. IEEE/ACM Trans. Netw. , 13(4):802–812, 2005.
  12. M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, "Survey and Taxonomy of IP Address Lookup Algorithms," IEEE Network, vol. 15, no. 2, pp. 8-23, 2001.
  13. H. Le and V. K. Prasanna. Scalable high throughput and power efficient ip-lookup on fpga. In Proc. FCCM '09, 2009.
  14. A. Andersson and S. Nilsson. Efficient implementation of suffix trees. Softw. Pract. Exper. , 25:129–141, February 1995.
Index Terms

Computer Science
Information Sciences

Keywords

Ip-lookup Longest Prefix Matching Skip Distance Routing Tables