SHIP: A Scalable High-Performance IPv6 Lookup Algorithm That Exploits Prefix Characteristics
- 25 July 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 27 (4) , 1529-1542
Abstract
Due to the emergence of new network applications, current IP lookup engines must support high bandwidth, low lookup latency, and the ongoing growth of IPv6 networks. However, the existing solutions are not designed to address jointly these three requirements. This paper introduces SHIP, an IPv6 lookup algorithm that exploits prefix characteristics to build a data structure designed to meet future application requirements. Based on the prefix length distribution and prefix density, prefixes are first clustered into groups sharing similar characteristics and then encoded in hybrid trie-trees. The resulting memory-efficient and scalable data structure can be stored in low-latency memories and allows the traversal process to be parallelized and pipelined in order to support high packet bandwidth in hardware. In addition, SHIP supports incremental updates. Evaluated on real and synthetic IPv6 prefix tables, SHIP has a logarithmic scaling factor in terms of the number of memory accesses and a linear memory consumption scaling. Compared with other well-known approaches, SHIP reduces the required amount of memory per prefix by 87%. When implemented on a state-of-the-art field-programmable gate array (FPGA), the proposed architecture can support processing 588 million packets per second.Keywords
All Related Versions
Funding Information
- Natural Sciences and Engineering Research Council of Canada
- PROMPT
- Ericsson Canada
- Kaloom
This publication has 35 references indexed in Scilit:
- Compressing IP Forwarding Tables: Towards Entropy Bounds and BeyondIEEE/ACM Transactions on Networking, 2014
- A Hybrid Hardware Architecture for High-Speed IP Lookups and Fast Route UpdatesIEEE/ACM Transactions on Networking, 2013
- DXRACM SIGCOMM Computer Communication Review, 2012
- Tree bitmapACM SIGCOMM Computer Communication Review, 2004
- Classifying packets with hierarchical intelligent cuttingsIEEE Micro, 2000
- IP-address lookup using LC-triesIEEE Journal on Selected Areas in Communications, 1999
- Faster IP lookups using controlled prefix expansionACM SIGMETRICS Performance Evaluation Review, 1998
- Scalable high speed IP routing lookupsACM SIGCOMM Computer Communication Review, 1997
- Perfect hashingTheoretical Computer Science, 1997
- PATRICIA—Practical Algorithm To Retrieve Information Coded in AlphanumericJournal of the ACM, 1968