Technical Report PHD-2014-02

Title: Fast Decisions in High-Speed Networking Devices
Authors: Yossi Kanizo
Supervisors: Isaac Keslassy and David Hay
Abstract: Tables that match a given key to its value (e.g., hash tables) have become crucial algorithmic building blocks for contemporary networking devices, which typically handle large amounts of data at high speeds. For example, these tables are used for heavy-hitter flow identification, flow state keeping, virus signature scanning, flow counter management, IP address lookup algorithms, and access control. Networking devices tables require a strict worst-case operation time along with limited table size, unlike traditional table-based data structures where amortized operation time is typically the main figure of merit.

In this dissertation, we first consider multiple-choice hashing schemes, which are particularly suited to such a worst-case operation time bound. Assuming a uniform memory model and an overflow list, often implemented using Content-Addressable Memory (CAM), we start by considering multiple-choice hashing schemes without deletion operations, i.e. only insertion and query operations. In this case, we find \emph{optimal} online hashing schemes with guaranteed worst case operation time. Then, we extend the model by considering also cases where deleting elements is allowed. While previous results show the same asymptomatic behavior between the two models, we show that when bucket sizes are bounded the performance may dramatically decrease. In particular, in the deletions case, optimal online schemes decrease the expected overflow fraction as slowly as $\Omega(1/a)$, compared to $\Omega(e^{-a})$ in case deletion are not allowed, where $a$ is the average number of memory accesses. We also study a \emph{balancing problem} variant, where elements need to be balanced among the buckets using only few memory accesses. The construction of an energy efficient Bloom filter-like data structure is a direct application of this problem.

In addition, we consider a combined memory model (e.g., of both SRAM and DRAM), in which some of the elements are stored in a fast memory, while others are stored in a significantly slower memory. In this case, we provide a tight upper bound on the number of elements that can be stored in the fast memory when using a multiple-choice hashing scheme with $d=2$ choices.

Finally, we show how network rules usually implemented using Ternary Content-Addressable Memories (TCAMs) at the ingress points of the network can be split among all routers in the network, such that each switch can maintain a smaller TCAM, while preserving the same overall classification functionality.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2014
To the main CS technical reports page

Computer science department, Technion