When an Internet router receives a packet p from an input link interface, it uses p’s destination field to look up a routing database. The result of the lookup provides an output link interface, to which packet p is forwarded. In dynamic router tables, where IP lookup is intermixed with table updates, lookups may be delayed while a preceding update completes. To minimize this delay, it is important that updates are performed as fast as possible. In relaxed balanced data structures, rebalancing is uncoupled from updates such that the rebalancing tasks can be performed gradually in less busy times. We investigate how the min-augmented range tree, a structure which can be utilized for IP lookup, can be relaxed. Our experiments with real IPv4 routing data indicate that the relaxed balanced min-augmented range tree has a significant advantage over the strictly balanced version.

Packet classification enables network routers to provide advanced network services including network security, quality of service (QoS) routing, and multimedia communications. In order to classify a packet, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. Viewing the classification problem geometrically, classifying an arriving packet is equivalent to finding the highest priority hyperrectangle among all hyperrectangles that contain the point representing the packet. The R-tree and its variants, being among the most popular access methods for points and rectangles, have not been experimentally evaluated and benchmarked for their eligibility for the packet classification problem. In this paper we investigate how the R*-tree, a dynamic index structure for spatial data, is suited for packet classification. To this end we will benchmark R* with two representative classification algorithms using the ClassBench tools suite.

Packet Alters are rules for classifying packets based on their header fields. In order to avoid ambiguities in packet classification, the set of filters in a router table must be conflict-free, i.e. for any incoming packet p, there must be a unique best matching filter which applies to p. We present the first output-sensitive solution for the offline version of the conflict detection and resolving problem for 1-dimensional arbitrary range filters under the most-specific tie breaking rule. The algorithm achieves a worst case time complexity of O(n log n) and uses space O(n). Instead of reporting and resolving all pairs of conflicting filters, we straight away report those resolve filters that are necessary to make the set conflict-free.