Efficient Gray-Code-Based Range Encoding Schemes for Packet Classification in TCAM

被引：18

作者：

Chang, Yeim-Kuan ^{[1
]}

Su, Cheng-Chien ^{[1
]}

Lin, Yung-Chieh ^{[1
]}

Hsieh, Sun-Yuan ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 701, Taiwan

来源：

IEEE-ACM TRANSACTIONS ON NETWORKING | 2013年 / 21卷 / 04期

关键词：

Elementary intervals; Gray code; packet classification; ternary content addressable memory (TCAM);

D O I：

10.1109/TNET.2012.2220566

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

An efficient ternary content addressable memory (TCAM) encoding scheme using a binary reflected Gray code (BRGC) and the concept of elementary intervals is presented for efficiently storing arbitrary ranges in TCAM. The proposed layered BRGC range encoding scheme (L-BRGC) groups ranges into BRGC range sets in which each range can be encoded into a single ternary vector. The results of experiments performed on real-life and synthesized rule tables show that L-BRGC consumes less TCAM than all the existing range encoding schemes for all rule tables, except that the direct conversion scheme (EIGC) using elementary intervals and BRGC codes performs best for a small real-life ACL rule table.

引用

页码：1201 / 1214

页数：14

共 20 条

[1]

Brayton R.K., 1984, Logic minimization algorithms for VLSI synthesis

[2] Space-efficient TCAM-based oassification using gray coding [J].

Bremler-Barr, Anat ;

Hendler, Danny .

INFOCOM 2007, VOLS 1-5, 2007, :1388-+

[3] Layered Interval Codes for TCAM-based Classification [J].

Bremler-Barr, Anat ;

Hay, David ;

Hendler, Danny .

IEEE INFOCOM 2009 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-5, 2009, :1305-+

[4]

Buchsbaum A. L., 2003, J EXP ALGORITHMICS, V8, P1

[5] Dynamic segment trees for ranges and prefixes [J].

Chang, Yeim-Kuan ;

Lin, Yung-Chieh .

IEEE TRANSACTIONS ON COMPUTERS, 2007, 56 (06) :769-784

[6] Next generation routers [J].

Chao, HJ .

PROCEEDINGS OF THE IEEE, 2002, 90 (09) :1518-1558

[7] DRES: Dynamic range encoding scheme for TCAM coprocessors [J].

Che, Hao ;

Wang, Zhijun ;

Zheng, Kai ;

Liu, Bin .

IEEE TRANSACTIONS ON COMPUTERS, 2008, 57 (07) :902-915

[8]

Dong Q., 2006, Performance Evaluation Review, V34, P311, DOI 10.1145/1140103.1140313

[9]

Gupta P, 1999, COMP COMM R, V29, P147, DOI 10.1145/316194.316217

[10]

Lakshman T. V., 1998, Computer Communication Review, V28, P203, DOI 10.1145/285243.285283

← 1 2 →