טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentRottenstreich Ori
SubjectCoding Schemes for Memory-Efficient Routers
DepartmentDepartment of Electrical Engineering
Supervisor Professor Isaac Keslassy
Full Thesis textFull thesis text - English Version


Abstract

The Internet network core is composed of a set of nodes, called routers that are connected by physical links. The goal of the routers is to process packets and to forward them to their destinations. The processing should be done on a per-packet basis and is often implemented in hardware using high-performance on-chip memories. With the dramatic growth in the amount of information required for the processing, new techniques to improve the capacity of the limited-size memories are required. To address this challenge, we study in this thesis coding schemes to improve the memory efficiency of routers.

In the first part of the thesis, we deal with the Bloom filter and its popular variant the Counting Bloom filter (CBF). These data structures are widely used in networking device algorithms and especially in routers. They implement fast set representations to support membership queries with limited error.  Unlike Bloom filters, CBFs also support element deletions. First, we introduce a new general method based on variable increments to improve the efficiency of CBFs and their variants. We demonstrate that this method can always achieve a lower false positive rate and a lower overflow probability bound than CBF in practical systems. Next, we uncover the Bloom paradox in Bloom filters: sometimes, it is better to disregard the query results of Bloom filters, and in fact not to even query them, thus making them detrimental. We analyze conditions under which the Bloom paradox occurs, and demonstrate that it depends on the a priori membership probability.

In the second part of the thesis, we study efficient encodings of classification rules in ternary content-addressable memories (TCAMs). TCAMs are the de-facto industrial standard for high-speed packet classification. The most complicated classification rules are range rules, which usually require multiple TCAM entries to encode them. We explore the theoretical hardness of encoding one-dimensional and two-dimensional ranges and provide new upper bounds on the TCAM worst-case range expansions. We further suggest new analytical tools to prove the tightness of these bounds. We then present an optimal encoding for all generalized extremal range rules. Such rules represent 89% of all non-trivial rules in a typical real-life classification database. We suggest a new method of simply calculating the optimal expansion of an extremal range. Last, we propose modified TCAM architectures that can use additional logic to significantly reduce the range expansions, both in the worst case and using real-life classification databases.