Please use this identifier to cite or link to this item:
Title: DRES : dynamic range encoding scheme for TCAM coprocessors
Authors: Che, H
Wang, Z
Zheng, K
Liu, B
Keywords: Network processor
Packet classification
Range matching
Ternary CAM
Issue Date: 2008
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on computers, 2008, v. 57, no. 7, p. 902-915 How to cite?
Journal: IEEE transactions on computers 
Abstract: One of the most critical resource management issues in the use of ternary content-addressable memory (TCAM) for packet classification/ filtering is how to effectively support filtering rules with ranges, known as range matching. In this paper, the dynamic range encoding scheme (DRES) is proposed to significantly improve the TCAM storage efficiency for range matching. Unlike the existing range encoding schemes requiring additional hardware support, DRES uses the TCAM coprocessor itself to assist range encoding. Hence, DRES can be readily programmed in a network processor using a TCAM coprocessor for packet classification. A salient feature of DRES is its ability to allow a subset of ranges to be encoded and, hence, to have full control over the range code size. This advantage allows DRES to exploit the TCAM structure to maximize the TCAM storage efficiency. DRES is a comprehensive solution, including a dynamic range selection algorithm, a search key encoding scheme, a range encoding scheme, and a dynamic encoded range update algorithm. Although the dynamic range selection algorithm running in the software allows optimal selection of ranges to be encoded to fully utilize the TCAM storage, the dynamic encoded range update algorithm allows the TCAM database to be updated lock free without interrupting the TCAM database lookup process. DRES is evaluated based on real-world databases and the results show that DRES can reduce the TCAM storage expansion ratio from 6.20 to 1.23. The performance analysis of DRES based on a probabilistic model demonstrates that DRES significantly improves the TCAM storage efficiency for a wide spectrum of range distributions.
ISSN: 0018-9340
EISSN: 1557-9956
DOI: 10.1109/TC.2007.70838
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 15, 2018


Last Week
Last month
Citations as of Aug 3, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 12, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.