Disjoint superposition for reduction of conjoined prefixes in IP lookup for actual IPv6 forwarding tables

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Helix is a recently-proposed scheme that performs IP lookup in a single memory access. Helix uses parallel prefix matching at the different prefix lengths and the position of prefixes in a binary tree for reducing the amount of memory used. The scheme enables fast table updates as prefixes are kept in their original form. In Helix, a large number of prefixes is stored in a very small amount of memory and route updates, as the lookup process, is performed in a single memory access. Most IPv6 testings of IP lookup schemes are performed on forwarding tables generated synthetically from IPv4 tables as IPv6 tables have a small prefix count. However, the prefix distribution of address blocks in actual tables may be correlated and that may result in using large amounts of memory to represent them. Here, we proposed the application of disjoint superpositions in Helix to further reduce the amount of memory used to represent these forwarding tables. We show that under IPv6 forwarding tables, Helix prevails in performing lookup operations in a single memory access time.

Original languageEnglish (US)
Title of host publication2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509013289
DOIs
StatePublished - Jan 1 2016
Event59th IEEE Global Communications Conference, GLOBECOM 2016 - Washington, United States
Duration: Dec 4 2016Dec 8 2016

Publication series

Name2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings

Other

Other59th IEEE Global Communications Conference, GLOBECOM 2016
CountryUnited States
CityWashington
Period12/4/1612/8/16

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality

Keywords

  • Address lookup
  • Helicoidal properties
  • Parallel matching
  • Parallel search
  • Single memory access

Fingerprint Dive into the research topics of 'Disjoint superposition for reduction of conjoined prefixes in IP lookup for actual IPv6 forwarding tables'. Together they form a unique fingerprint.

Cite this