Helix: IP lookup scheme based on helicoidal properties of binary trees

Roberto Rojas-Cessa, Taweesak Kijkanjanarat, Wara Wangchai, Krutika Patil, Narathip Thirapittayatakul

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this paper, we propose an IP lookup scheme, called Helix, that performs parallel prefix matching at the different prefix lengths and uses the helicoidal properties of binary trees to reduce tree height. The reduction of the tree height is achieved without performing any prefix modification. Helix minimizes the amount of memory used to store long and numerous prefixes and achieves IP lookup and route updates in a single memory access. We evaluated the performance of Helix in terms of the number of memory accesses and amount of memory required for storing large IPv4 and IPv6 routing tables with up to 512,104 IPv4 and 389,956 IPv6 prefixes, respectively. In all the tested routing tables, Helix performs lookup in a single memory access while using very small memory amounts. We also show that Helix can be implemented on a single field-programmable gate array (FPGA) chip with on-chip memory for the IPv4 and IPv6 tables considered herein, without requiring external memory. Specifically, Helix uses up to 72% of the resources of an FPGA to accommodate the most demanding routing table, without performance penalties. The implementation shows that Helix may achieve lookup speeds beyond 1.2 billion packets per second (Gpps).

Original languageEnglish (US)
Pages (from-to)78-89
Number of pages12
JournalComputer Networks
Volume89
DOIs
StatePublished - Oct 4 2015

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Keywords

  • Binary tree
  • Double helix
  • Helicoidal properties
  • IP lookup
  • IPv6 lookup
  • One memory access

Fingerprint

Dive into the research topics of 'Helix: IP lookup scheme based on helicoidal properties of binary trees'. Together they form a unique fingerprint.

Cite this