The Taub Faculty of Computer Science Events and Talks

Tables that match a given key to its value (e.g., hash tables) have become crucial algorithmic building blocks for contemporary networking devices that need to take decisions on a large amount of data at high speed. Unlike traditional table-based data structures, the networking environment provides only very limited memory and necessitates a strict worst-case operation time. Furthermore, since such tables typically lie on the critical path of networking devices, the total number of memory accesses performed by these tables dramatically affects overall performance: A large number of memory accesses may increase the power consumption, and in some cases, decrease the throughput. In this talk, we consider tables based on multiple-choice hashing schemes. Such schemes are particularly suited to networking devices because they guarantee worst-case operation time, albeit with some percentage of overflowed elements. We introduce optimal online multiple choice hashing schemes, when the data structure should either support element deletions, or not. In particular, given $a$ memory accesses per packet, the fraction of overflowed elements under the optimal scheme that does not support deletions is $\Omega(e^{-a})$. This overflow fraction increases to $\Omega(1/a)$, when deletion support is required. We have also studied how to cope with the stringent memory requirements of networking devices. In particular, we introduce a scheme that allows splitting a large table across the entire network, while maintaining its overall semantics.