טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentKanizo Josef Hai
SubjectFast Decisions in High-Speed Networking Devices
DepartmentDepartment of Computer Science
Supervisors Professor Isaac Keslassy
Dr. David Hay
Full Thesis textFull thesis text - English Version


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 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 Ω(1/a), compared to Ω(e-a) in case deletion are not allowed, where a is the average number of memory accesses. We also study a 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 lower bound on the number of elements that can be stored 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.