IP address lookup is a fundamental task for Internet routers, due to the rapid growth of both traffic and links capacity. Many algorithms have been proposed to improve lookup performance in terms of memory consumption, search speed and update complexity. Due to the presence of wildcards and netmasks, such algorithms adopt several techniques to deal with longest prefix matching. However, the analysis of lookup tables reveals that the first 16 bits of forwarding rules are almost always specified. Therefore, more powerful exact-matching schemes can be applied to the first half of addresses. This paper presents a routing lookup accelerator (RLA) which allows the lookup of the first 16 bits to be sped up. The target is an efficient scheme to be implemented in small and fast memories of recent hardware platforms. Specifically, since in several forwarding tables the distribution of the first 16 bits is characterized by empty gaps as well as pronounced peaks, we propose to divide the address space in different ranges and to encode each address only as a difference with respect to a given address chosen as reference for that range. Then, a hybrid direct-addressing / multibit trie scheme is used for each range. As RLA is orthogonal to all other schemes, any other lookup algorithm can be used to perform longest prefix matching on the remaining bits.

A Prefix-Distribution Adaptive Scheme For Routing Lookup Acceleration

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

Abstract

IP address lookup is a fundamental task for Internet routers, due to the rapid growth of both traffic and links capacity. Many algorithms have been proposed to improve lookup performance in terms of memory consumption, search speed and update complexity. Due to the presence of wildcards and netmasks, such algorithms adopt several techniques to deal with longest prefix matching. However, the analysis of lookup tables reveals that the first 16 bits of forwarding rules are almost always specified. Therefore, more powerful exact-matching schemes can be applied to the first half of addresses. This paper presents a routing lookup accelerator (RLA) which allows the lookup of the first 16 bits to be sped up. The target is an efficient scheme to be implemented in small and fast memories of recent hardware platforms. Specifically, since in several forwarding tables the distribution of the first 16 bits is characterized by empty gaps as well as pronounced peaks, we propose to divide the address space in different ranges and to encode each address only as a difference with respect to a given address chosen as reference for that range. Then, a hybrid direct-addressing / multibit trie scheme is used for each range. As RLA is orthogonal to all other schemes, any other lookup algorithm can be used to perform longest prefix matching on the remaining bits.
9781424441488
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: https://hdl.handle.net/11568/200819
 Attenzione

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

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