Multi-match Packet Classification Scheme Combining TCAM with an Algorithmic Approach

Hyesook Lim,Nara Lee,Jungwon Lee 대한전자공학회 2017 IEIE Transactions on Smart Processing & Computing Vol.6 No.1

Packet classification is one of the essential functionalities of Internet routers in providing quality of service. Since the arrival rate of input packets can be tens-of-millions per second, wirespeed packet classification has become one of the most challenging tasks. While traditional packet classification only reports a single matching result, new network applications require multiple matching results. Ternary content-addressable memory (TCAM) has been adopted to solve the multi-match classification problem due to its ability to perform fast parallel matching. However, TCAM has a fundamental issue: high power dissipation. Since TCAM is designed for a single match, the applicability of TCAM to multi-match classification is limited. In this paper, we propose a cost- and energy-efficient multi-match classification architecture that combines TCAM with a tuple space search algorithm. The proposed solution uses two small TCAM modules and requires a single-cycle TCAM lookup, two SRAM accesses, and several Bloom filter query cycles for multimatch classifications.

On Adding Bloom Filters to Longest Prefix Matching Algorithms

Hyesook Lim,Kyuhee Lim,Nara Lee,Kyong-Hye Park IEEE 2014 IEEE Transactions on Computers Vol. No.

<P>High-speed IP address lookup is essential to achieve wire-speed packet forwarding in Internet routers. Ternary content addressable memory (TCAM) technology has been adopted to solve the IP address lookup problem because of its ability to perform fast parallel matching. However, the applicability of TCAMs presents difficulties due to cost and power dissipation issues. Various algorithms and hardware architectures have been proposed to perform the IP address lookup using ordinary memories such as SRAMs or DRAMs without using TCAMs. Among the algorithms, we focus on two efficient algorithms providing high-speed IP address lookup: parallel multiple-hashing (PMH) algorithm and binary search on level algorithm. This paper shows how effectively an on-chip Bloom filter can improve those algorithms. A performance evaluation using actual backbone routing data with 15,000-220,000 prefixes shows that by adding a Bloom filter, the complicated hardware for parallel access is removed without search performance penalty in parallel-multiple hashing algorithm. Search speed has been improved by 30-40 percent by adding a Bloom filter in binary search on level algorithm.</P>

Priority Tries for IP Address Lookup

Hyesook Lim,Changhoon Yim,Swartzlander, Earl E IEEE 2010 IEEE Transactions on Computers Vol.59 No.6

<P>High-speed IP address lookup is essential to achieve wire speed packet forwarding in Internet routers. The longest prefix matching for IP address lookup is more complex than exact matching because it involves dual dimensions: length and value. This paper presents a new formulation for IP address lookup problem using range representation of prefixes and proposes an efficient binary trie structure named a priority trie. In this range representation, prefixes are represented as ranges on a number line between 0 and 1 without expanding to the maximum length. The best match to a given input address is the smallest range that includes the input. The priority trie is based on the trie structure, with empty internal nodes in the trie replaced by the priority prefix which is the longest among those in the subtrie rooted by the empty nodes. The search ends when an input matches a priority prefix, which significantly improves the search performance. Performance evaluation using real routing data shows that the proposed priority trie is very good in performance metrics such as lookup speed, memory size, update performance, and scalability.</P>

Hierarchical Binary Search Tree for Packet Classification

Hyesook Lim,Ha Neul Chu,Changhoon Yim [Institute of Electrical and Electronics Engineers 2007 IEEE Communications Letters Vol.11 No.8

<P>In order to provide value-added services such as policy-based routing and the quality of services in next generation network, the Internet routers need to classify packets into flows for different treatments. Since packet classification should be performed in wire-speed for every packet incoming in several hundred gigabits per second, it becomes a major challenge in the Internet routers. In this letter, we propose a new packet classification scheme based on hierarchical binary search tree. The proposed scheme hierarchically connects binary search trees without empty internal nodes, and hence the proposed architecture significantly improves the search performance as well as greatly reduces the memory requirement compared with trie-based schemes.</P>

Tuple Pruning Using Bloom Filters for Packet Classification

Hyesook Lim,So Yeon Kim IEEE 2010 IEEE micro Vol.30 No.3

<P>Tuple pruning for packet classification provides fast search and a low implementation complexity. The tuple pruning algorithm reduces the search space to a subset of tuples determined by individual field lookups that cause off-chip memory accesses. The authors propose a tuple-pruning algorithm that reduces the search space through Bloom filter queries, which do not require off-chip memory accesses.</P>

A Quad-Trie Conditionally Merged with a Decision Tree for Packet Classification

Hyesook Lim,Youngju Choe,Miran Shim,Jungwon Lee IEEE 2014 IEEE communications letters Vol.18 No.4

<P>Trie-based algorithms and decision tree-based algorithms are well-known packet classification solutions which show trade-off between throughput performance and memory requirement. The trie-based algorithms require small memory since each rule is stored exactly once, but they do not provide high throughput because of rule comparison at every rule node. The decision tree-based algorithms provide high throughput since the number of rules compared with an input packet can be controlled as a limited number, but they require excessive amount of memory because of high degree of rule replication. This paper proposes to combine these two types of algorithms. The proposed algorithm primarily constructs a trie and then applies a decision tree for nodes having more rules than a threshold value. Simulation results show that the throughput performance is improved by up to 41 times compared with the trie, and the memory requirement is reduced by up to 38 times compared with the decision tree, so that the performance of both is within a tolerable range for practical implementation.</P>

Complement Bloom Filter for Identifying True Positiveness of a Bloom Filter

Hyesook Lim,Jungwon Lee,Changhoon Yim IEEE 2015 IEEE communications letters Vol.19 No.11

<P>The use of Bloom filters in network applications has increased rapidly. Since Bloom filters can produce false positives, the trueness of each positive needs to be identified by referring to an off-chip hash table. This letter proposes a new method for identifying the trueness of Bloom filter positives. We propose the use of an additional Bloom filter programmed for the complement set of the given set. In querying an input, if the complement Bloom filter produces a negative result, the input is a member of the given set since Bloom filters never produce a false negative. When both Bloom filters produce positives, a hash table needs to be referred to in our method. We provide a mathematical analysis, whereby the probability of referring to a hash table converges to the summation of the false positive probabilities of each Bloom filter. We provide the simulation result that the rate of referring to a hash table in our method is the order of 10<SUP>-5</SUP> for Bloom filter sizing factor 32.</P>

Ternary Bloom Filter Replacing Counting Bloom Filter

Lim, Hyesook,Lee, Jungwon,Byun, Hayoung,Yim, Changhoon IEEE 2017 IEEE COMMUNICATIONS LETTERS Vol.21 No.2

<P>A counting Bloom filter (CBF) is commonly used in many applications for the membership queries of dynamic data since the CBF can provide delete operations. A CBF uses an array of c-bit counters. The c should be large enough to avoid overflows. In this letter, we propose an alternative to CBF, named ternary Bloom filter (TBF) for performance improvement. The proposed TBF allocates the minimum number of bits to each counter and includes more number of counters instead to reduce false positive probability. We present a mathematical analysis and experimental results for a set of performance measures. When the TBF consumes the same amount of memory as the CBF, the TBF provides much lower false positive rates than the CBF.</P>

Comparison of Molecular Weight Distribution of Commercially Purified Oat and Barley β-glucans

Hyesook S. Lim,Pamela J. White 한국식품과학회 1997 Food Science and Biotechnology Vol.6 No.1

Binary searches on multiple small trees for IP address lookup

Lim, Hyesook,Lee, Bomi,Kim, Wonjung IEEE 2005 IEEE communications letters Vol.9 No.1

Rapid growth of Internet traffic requires more Internet bandwidth and high-speed packet processing in Internet routers. IP address lookup in routers is an essential operation that should be performed in real-time for routers where hundreds of million packets arrive per second. In this paper, we propose a new software-based architecture for efficient IP address lookup. In the proposed scheme, a large routing table is divided into multiple balanced trees, and sequential binary searches are performed on those trees, and hence the number of memory accesses depends on the number of routing entries not on the length of routing prefixes. Performance evaluation results show that the proposed architecture requires a single 301.7 Kbyte SRAM to store about 41000 routing entries, and an address lookup is achieved by 11 memory accesses in average.