A Dynamic Lookup Scheme for Bursty Access

The problem of fast address lookup is crucial to routing and thus has received considerable attention. Most of the work in this field has focused on improving the speed of individual accesses - independent form the underlying access pattern. Recently, Gupta et.al., proposed an efficient data structure to exploit the bias in access pattern. This technique achieves faster lookups for more frequently accessed keys while bounding the worst case lookup time; in fact it is (near) optimal under constraints on worst case performance. However, it needs to be rebuilt periodically to reflect the changes in access patterns, which can be inefficient for bursty environments. In this paper we introduce a new dynamic data structure to exploit biases int he access pattern which tend to change dynamically. Recent work show that there are many circumstances under which access patterns change quickly. Our data strucutre, which we call the biased skip list (BSL), has a self-update mechanism which reflects the changes in the access patterns efficiently and immediately, without any need for rebuilding. It improves throughput while keeping the worst case access time bounded by that of the fastest (unbiased) schemes. We demonstrate the practicality of BSL by experiments on data with varying degrees of burstiness.