Research Seminar - October 22, 2004

A Data Structures View at the IP Lookup and Packet Classification Problem

Abstract: IP address lookup is a critical operation for high speed packet switching. The lookup requires searching for the longest prefix among those stored in a large given routing table matching a given IP address. More generally, incoming packets have to be classified into different flows according to one or more fields in the packet headers. These problems have been studied thoroughly by researches in the network and algorithms communities from different points of view. In this talk we sketch the large variety of data structures used for solving the problems. Among them are not only variants of (balanced) search trees but also all kinds of geometric structures like segment trees, interval trees, and priority search trees.