Using Partial Persistence to Support Bursts of Operations in IP-Lookup
Tobias Langner, Thomas Ottmann · 2007
We present an enhanced path-copying method to make linked data structures partially persistent, that allows the carrying out any number of operations between two adjacent versions versus only one operation per version for the original method. This extended path-merging procedure makes heavy use of merged paths in binary search trees, that turn out to be a nimble method to represent nodes changed by manipulations of the tree. We show, through the results of several experiments, the efficiency of path-merging and compare its performance with path-copying. As domain-specific application in the environment of detecting conflict in packet filters, we replace the backbone data structure of SlabDetect, an algorithm for resolving conflicts in a set F of n one-dimensional packet filters, with a Red-Black tree upgraded with the path-merging method. The persisted SlabDetect algorithm provides a compact and task-oriented representation of the filters in F without increasing SlabDetect’s runtime complexity of O(n log n). In addition, we present data from experiments, to support the above and contrast the performances of both the original and the persisted variant of SlabDetect.