Technical Report No. 232 - Abstract

C. Maindorfer
Relaxed Min-Augmented Range Trees for Dynamic IP Router Tables

When an Internet router receives a packet \emph {p} from an input link interface, it uses \emph {p}'s destination field to look up a routing database. The result of the lookup provides an output link interface, to which packet \emph {p} is forwarded. Ever increasing routing table sizes, traffic volume and link speeds demand efficient lookup algorithms. In router tables, IP lookup is intermixed with updates, hence it is important to avoid extensive locking. Furthermore, updates should be processed as fast as possible in order to minimize packet loss and packet delay. \\ In relaxed balanced data structures, rebalancing is uncoupled from the update such that the rebalancing tasks can be performed gradually after urgent updates.\\ We will investigate how the min-augmented range tree, a structure which can be utilized for IP lookup, can be relaxed.