IIT Home Page CNR Home Page

Efficient IP table lookup via adaptive stratified trees with selective reconstructions

IP address lookup is a critical operation for high-bandwidth routers in packet-switching networks, such as Internet. The lookup is a nontrivial operation, since it requires searching for the longest prefix, among those stored in a (large) given table, matching the IP address. Ever increasing routing table size, traffic volume, and links speed demand new and more efficient algorithms. Moreover, the imminent move to IPv6 128-bit addresses will soon require a rethinking of previous technical choices. This article describes a the new data structure for solving the IP table lookup problem christened the adaptive stratified tree (AST). The proposed solution is based on casting the problem in geometric terms and on repeated application of efficient local geometric optimization routines. Experiments with this approach have shown that in terms of storage, query time, and update time the AST is at a par with state of the art algorithms based on data compression or string manipulations (and often it is better on some of the measured quantities).
ACM Journal of Experimental Algorithms, 2008

Autori: M.Pellegrini, G.Fusco
Autori IIT:

Tipo: Articoli su riviste non ISI con referee internazionali
Area di disciplina: Computer Science and Engineering
Da pagina 1 a pagina 28