IP address lookup is a fundamental task for Internet routers. Because of the rapid growth of both traffic and links capacity, the time budget to process a packet continues to decrease and lookup tables unceasingly grow; therefore, new algorithms are required to improve lookup performance. However, the large density disparity on the prefix range within real lookup tables suggests a hybrid adaptive technique as effective and simple solution. Therefore, this paper presents a novel approach in which various prefix length ranges are represented with distinct data structures and stored in different memories. In this way, the different frequencies of forwarding rules can be taken in account and the memory hierarchy of real platforms can be exploited. This leads to small structures to be put in fast memory for the most dense ranges and larger structures (with a lower number of accesses) in the slower memories for the other ranges. The results remark the low number of off-chip memory accesses of our scheme and a valuable speedup.

A Heuristic and Hybrid Hash-based Approach to Fast Lookup

ANTICHI, GIANNI;GIORDANO, STEFANO;PROCISSI, GREGORIO;VITUCCI, FABIO
2009

Abstract

IP address lookup is a fundamental task for Internet routers. Because of the rapid growth of both traffic and links capacity, the time budget to process a packet continues to decrease and lookup tables unceasingly grow; therefore, new algorithms are required to improve lookup performance. However, the large density disparity on the prefix range within real lookup tables suggests a hybrid adaptive technique as effective and simple solution. Therefore, this paper presents a novel approach in which various prefix length ranges are represented with distinct data structures and stored in different memories. In this way, the different frequencies of forwarding rules can be taken in account and the memory hierarchy of real platforms can be exploited. This leads to small structures to be put in fast memory for the most dense ranges and larger structures (with a lower number of accesses) in the slower memories for the other ranges. The results remark the low number of off-chip memory accesses of our scheme and a valuable speedup.
9781424451739
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/200596
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact