Efficient IP Table Lookup
via Adaptive Stratified Trees
with Selective Reconstructions

Autors

Marco Pellegrini, Istituto di Informatica e Telematica, CNR, Pisa, Italy
Giordano Fusco, University of Wisconsin-Madison, USA & IIT-CNR, Pisa, Italy

Abstract

IP address lookup is a critical operation for high bandwidth routers in packet switching networks such as Internet. The lookup is a non-trivial operation since it requires searching for the longest prefix, among those stored in a (large) given table, matching the IP address. Ever increasing routing tables 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 look up 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).

Appeared in

Proceedings of the 12th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, number 3221, pages 772-783, Bergen, Norway, September 2004.

Download

Conference paper: pdf, ps, SpringerLink
Slides: pdf, ps
Bibtex entry: bib