An Efficient Parallel IP Lookup Technique for IPv6 Routers Using Multiple Hashing with Ternary marker storage
Article Sidebar
Main Article Content
Abstract
Internet address lookup is a challenging problem because of the increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. Routing lookup involves computation of best matching prefix for which existing solutions scale poorly when traffic in the router increases or when employed for IPV6 address lookup. Our paper describes a novel approach which employs multiple hashing on reduced number of hash tables on which ternary search on levels is applied in parallel. This scheme handles large number of prefixes generated by controlled prefix expansion by reducing collision and distributing load fairly in the hash buckets thus providing faster worst case and average case lookups. The approach we describe is fast, simple, scalable, parallelizable, and flexible.
Article Details
Issue
Section
Communication and Sensor Networks
Copyright for articles published in this journal is retained by the authors, with first publication rights granted to the journal. By virtue of their appearance in this open access journal, articles are free to use, with proper attribution, in educational and other non-commercial settings. A Copyright Form should be downloaded by authors and must be faxed to the AJICT before the publication of their manuscripts will be scheduled.
References
T. Srinivasan et al. "High Performance Parallel IP Lookup Technique Using Distributed Memory Organization" In Proc. of the IEEE International Conference of Information Technology (ITCC'04), Las Vegas, USA.
V. Srinivasan, G. Varghese. "Fast address lookups using controlled prefix version". ACM Transactions on Computer Systems, Vol. 17, No. 1, February 1999, Pages 1–40.
https://doi.org/10.1145/296502.296503
M. Wald Vogel, G. Varghese, J. Turner, B. Plattener, "Scalable High Speed IP Routing Lookups". In Proc. Of SIGCOMM 97, 1997.
Miguel Á. Ruiz-Sánchez, INRIA Sophia Antipolis, Universidad Autónoma etropolitana Ernst W. Biersack, Institut Eurécom Sophia Antipolis Walid Dabbous, INRIA Sophia Antipolis,"Survey and Taxonomy of IP Address Lookup Algorithms". IEEE Network • March/April 2001
Pankaj Gupta "Algorithms For Routing Lookups and Packet Classification" December 2000.
V. Srinivasan, G. Varghese. "Fast address lookups using controlled prefix version". ACM Transactions on Computer Systems, Vol. 17, No. 1, February 1999, Pages 1–40.
https://doi.org/10.1145/296502.296503
M. Wald Vogel, G. Varghese, J. Turner, B. Plattener, "Scalable High Speed IP Routing Lookups". In Proc. Of SIGCOMM 97, 1997.
Miguel Á. Ruiz-Sánchez, INRIA Sophia Antipolis, Universidad Autónoma etropolitana Ernst W. Biersack, Institut Eurécom Sophia Antipolis Walid Dabbous, INRIA Sophia Antipolis,"Survey and Taxonomy of IP Address Lookup Algorithms". IEEE Network • March/April 2001
Pankaj Gupta "Algorithms For Routing Lookups and Packet Classification" December 2000.