Outline

Minimization of ACL Storage by Adding
Minimal Hardware of Range Matchingand Logical Gates to TCAM

• Introduction– Access Control List (ACL)– Ternary Content Addressable Memory (TCAM)– Prefix Expansion• Proposal & Contribution– Range Matching Device (RMD)– Optimization of Prefix Expansion (PE-MIN)– Managing TCAM (RMD + PE-MIN)

Haesung Hwang†，Koji Yamamoto‡，Shingo Ata§
Kazunari Inoue‡，Masayuki Murata†† Graduate School of Information Science and Technology, Osaka University‡ Renesas Technology Corporation§ Graduate School of Engineering, Osaka City University• Evaluation• Conclusion{h-hwang,murata}@ist.osaka-u.ac.jp{yamamoto.koji4,inoue.kazunari}@renesas.com
ata@info.eng.osaka-u.ac.jp

May 16, 2008

Sketch of Proposal
SourceIntroduction

Destination

RouterRMD3• Searches using the content of memory,
returns the memory address• Cell representation: 0 / 1 /＊ConsPros• High power
consumption• Large chip area
• Expensive inter chipcommunication cost

• Fast search speed
 Excellent performancein longest prefixmatch Simple andstandardized structureHigh Performance Switching and Routing

May 16, 2008

Introduction

Ternary CAM

May 16, 2008

IntroductionAccess Control List (ACL)• List in routers for packet classification(permit/deny)• Entries consist of source and destination IP
address, source and destination port
number, and protocol number• Storage in TCAM

Proposed TCAM

High Performance Switching and Routing

May 16, 2008

2

access-list 101 permit tcp host 10.1.1.2 host 172.16.1.1 eq telnet
access-list 102 deny tcp any range 137 139 any
access-list 101 permit ip 10.1.1.0 0.0.0.255 172.16.1.0 0.0.0.255
access-list 111 deny icmp any 10.1.1.0 0.0.0.255 echo
access-list 191 permit udp any any range 16384 16483

ACL
Conventional TCAM

High Performance Switching and Routing

High Performance Switching and Routing

4Motivation• Writing ACL in TCAM
– Issue of expressing port numbers in ranges
Q. How do we write “ranges” in memory?
Q. How do we restrain the growth of expensive
TCAM entry?

• Possible storage of ranges– Full expansion: writing every single number toexactly match the entire range– Prefix expansion: writing least significant bits as
don’t care bits
5May 16, 2008

High Performance Switching and Routing

61

Introduction

Example Prefix Expansion• For a port range of “1024 ~ 65535”,• Minimize memory usage by integrating
additional device within the TCAM
• Decrease worst case by optimizing prefix
expansion algorithm– Full Expansion： 64512 entries– Prefix Expansion： 6 entries
1***************
01**************
001*************
0001************
00001***********
000001**********

32768 - 65535
16384 - 32767
8192 - 16383
4096 - 8191
2048 - 4095
1024 - 2047

Goodperformanceof ranges inunits of 2iReduce TCAM’s memory consumption
by using Range Matching Device andoptimized prefix expansion• For a port range of “16385 ~ 65534”,– Full Expansion: 49150 entries– Prefix Expansion: 29 entries
High Performance Switching and Routing

May 16, 2008

Research Purpose

7

May 16, 2008

ProposalRange Matching Device (RMD)
Conventional TCAM

DST
IP(32)

SRC
IP
(32)

SRC
Port
(16)

DST
Port
(16)

Prot
(8)

1 ***** 1**** *1**

Logical Circuit of RMD* **1** **

*1232
6~283
73230~32535555~
65551024~
655356970~
69992436

HITProposal<Input><Compare> <Output>• Src/Dst Determine ifMatch/PortNonFROM≦• FROM ∀search key∀ match•TO≦TO• Write the range FROM ~ TO in the memory• Determine if the search key (port #) iswithin FROM ~ TO

• Additional bits to the conventional TCAM,
reserved to express pre-written ranges
High Performance Switching and Routing

May 16, 2008

8Bits added for RMD

Port Range FROM ~ TO in RMD :Search Key :High Performance Switching and Routing

9

Proposal BackgroundPrefix Expansion Algorithms

May 16, 2008

High Performance Switching and Routing

10

Proposal

Logical NOT/AND Gates in TCAM

Prefix expansion of range “5000 ~ 6000”• PE-OR: Conventional prefix expansion
B5008-5023

D5056-5119

A5000-5007
C5024-5055

AB

F5632-5887

CDEF

G

I5984-5999

HIJ• PE-MIN: Proposed prefix expansion
B5120-6143

A4992-5119

5000: 1001110001000
5120: 1010000000000
6000: 1011101110000
May 16, 2008

C4992-4999

(AB)

F6000
D6000-6015 E6016-6143

5120

(¬C¬D

High Performance Switching and Routing

LogicalAND Gate(4 Set)

LogicalNOT Gate

G5888-5951 J6000
H5952-5983

E5120-5631

¬E)

F11

• Logical gates are required in addition to theconventional TCAM to express the result of PE-MIN• Gain: Tradeoff between the additional gates andthe reduced line
May 16, 2008

High Performance Switching and Routing122Proposal

Evaluation

Entry Reduction using RMD
PE-MIN with Range Matching Device

13

May 16, 2008

Evaluation

GLDrv
1%

6%

Total Entries

Match_Amp
9%

RMD: 580 Gates x 20 RMDs = 11.6K Gates
Current TCAM : TCAM with RMD = 100 : 100.3

706560• Tradeoff in vertical and horizontal bit lengths• Gain/loss tradeoff depends on data bit length• Inserting 20 RMD to current TCAM
⇒ 0.3% increase in manufacturing cost
May 16, 2008

Ex.
Data bits: 576
RMDs : 11→Saves 170Kbit(Around 300entries.
30% reduction)

Etc
8%

TCAM array
48%

PE
7%

High Performance Switching and Routing

14

Overhead Cost Estimation 2

7%

WD/PRE/LSL
7%<TCAM VLSI in 90nm Technology>

High Performance Switching and Routing

Evaluation

Overhead Cost Estimation 1FuseNumber of RMDs

Number of RMDs

• PE-MIN: 50% of reduction with 10~11 RMDs
• PE-OR: 50% of reduction with 7 RMDs
• With only 2~3 additional RMDs, the reduction level ofPE-MIN can be achieved in case of PE-OR

High Performance Switching and Routing

1%Control Logic :GLUE + ColDrv ColDrv
2%= 8%RowDec
4%305K Gates
GLUE(Priori)
IO

55425056

45

1440

435

443230 ~ 3253

3054552560

1120

657 RMDs
528 lines
51015105555 ~ 5587

705555 ~ 6555

6554607255

1850

47 RMDs722 lines

6000456970 ~ 6999

800200401121000

400035128

11 RMDs
410 lines
3016200258400202326 ~ 2837

May 16, 2008

Total Entries# ofPE-MIN x Weight
Ranges # of Ranges

Apr.07, PE-OR

1200

10 RMDs
580 lines

600

Oct.07, PE-OR

1400

Apr.07, PE-MIN

800

0PE-MIN
lines

1600

Oct.07, PE-MIN

1000(Lines after PE - 1) x (Number of ACLs referring this range)
Range

PE-OR with Range Matching Device

12000• Weight of each range determines the order to bewritten in the RMD

51015

RMD Policy

15May 16, 2008

High Performance Switching and Routing

16

Conclusion & Future Work
• Proposed new TCAM architecture byintegrating Range Matching Device andusing optimized prefix expansion algorithm• Evaluated using actual ACL data
• Future work

Thank you– Analysis of the proposed method using otherACLs to achieve a general purpose TCAM
– Implementation of the proposed TCAM in thenetwork processor to investigate further
performance characteristics (i.e. powerconsumption)
May 16, 2008

High Performance Switching and Routing

17

May 16, 2008

High Performance Switching and Routing

183