社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

プレフィックス展開と比較回路の併用によるアクセス制御リストの効率的な管理恵聖†黄山本 耕次††

阿多 信吾†††

井上 一成††

村田 正幸†† 大阪大学 大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1–5†† 株式会社ルネサステクノロジ 〒 664–0005 兵庫県伊丹市瑞原 4–1††† 大阪市立大学 大学院工学研究科〒 558–8585 大阪市住吉区杉本 3–3–138
E-mail: †{h-hwang,murata}@ist.osaka-u.ac.jp, ††{yamamoto.koji4,inoue.kazunari}@renesas.com,†††ata@info.eng.osaka-cu.ac.jp
あらまし 高速なパケット分類を実現するために，TCAM (Ternary Content Addressable Memory) が使用されている．アクセス制御リストのフィールド中の範囲で表現されるポート番号をメモリに書き込む際に，複数のエントリを必要とすることが，TCAM の消費電力やコストが高くなる理由の一つになっている. 本稿では，ポート番号をメモリに書き込む時，プレフィックス展開を利用してエントリ数を削減する方法，および新しいハードウェア構成を提案する．さらに実運用された ACL リストを用いた評価により，提案アーキテクチャがより効率的にエントリ数を削除できることを示す．
キーワード

IP ルータ，ACL (アクセス制御リスト)，TCAM，プレフィックス展開，範囲比較回路，

ハードウェアコスト

Eﬃcient Management of Access Control List by
Combining Preﬁx Expansion and Range Matching Devices
Haesung HWANG† , Koji YAMAMOTO†† , Shingo ATA††† ,Kazunari INOUE†† , and Masayuki MURATA†† Graduate School of Information Science and Technology，Osaka University†† Renesas Technology Corporation††† Graduate School of Engineering，Osaka City University
E-mail: †{h-hwang,murata}@ist.osaka-u.ac.jp, ††{yamamoto.koji4,inoue.kazunari}@renesas.com,†††ata@info.eng.osaka-cu.ac.jp
Abstract TCAM (Ternary Content Addressable Memory) is a special type of memory used in routers in order toachieve high speed packet classiﬁcation. Port numbers are one of the ﬁve typical ﬁelds in an ACL (Access Control
List). Those that are expressed in ranges have been the reason for raising the cost of hardware due to the requirement of multiple entries. In this paper，we suggest a method to reduce the number of entries when expressing
ranges in TCAM，using preﬁx expansion and hardware modiﬁcation.
Key words IP Router，Access Control List，Ternary Content Addressable Memory，Preﬁx Expansion，
Range Matching Device，Hardware Cost

1. は じ め にが幅広く用いられている [1]．しかしながら，TCAM には，消費電力，チップの面積，原材料コスト等の問題点があり，大容

現在 IP ルータにおいて，パケットのルーティングテーブルや量の TCAM を搭載することが困難であることがたびたび指摘

アクセス制御リスト (ACL; Access Control List) を高速に検索されている．特に，多くの ACL を管理するためには非常に大するために，TCAM (Ternary Content Addressable Memory)

容量の TCAM が必要になるが，その一方で格納できる容量は—1—

表 1 Example of Access Control List

うにするため，TCAM に NOT および AND の演算機能を付加したものについても検討し，通常の OR 演算のみの組み合わ

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

せよりもより効率的に ACL を管理できることが可能であることを示す．

access-list 111 deny icmp any 10.1.1.0 0.0.0.255 echo

以降，2. において，範囲指定されたポート番号の取り扱い

access-list 191 permit udp any any range 16384 16483

に関する問題点と既存技術について紹介する．3. では提案する RMD 組み込み型，および AND/NOT 演算機能を付加した

限られており，管理者はハードウェア容量を意識した効率的なTCAM アーキテクチャについて述べる．また，4. では RMD

管理をせざるを得ず，ルータ設定を行う管理者の負担が大きい．

への格納ポリシー，および AND/NOT/OR を併用したプレ

また，TCAM 容量を超えた ACL を管理する場合，TCAM にフィックス展開のアルゴリズムについて述べる．そして 5. では格納できなかった ACL に対する性能が急激に劣化し，ルータ実運用されている ACL に対して本提案手法を適用した場合のの処理能力がワイヤスピードを保証できないなどの問題も生TCAM エントリ数削減効果について議論する．最後に 6. でまじる．

とめと今後の課題について述べる．

ACL が TCAM 容量を大量に消費する要因の一つとして，
ポート番号の範囲指定がある．通常，ACL は送受信 IP アドレ

2. ポート範囲指定の問題点と既存の解決手法

ス，送受信ポート番号，およびプロトコル番号（それに加えてTCAM とは，アドレスを入力としてそのアドレスに格納さTCP フラグなど）の組み合わせによって表現されたルールにれている内容を返す通常の RAM (Random Access Memory)

よってパケットを識別し，パケットが指定されたルールにマッとは異なり，格納された内容を探索し，入力データと同じ情報チした場合，そのルールで記述された処理（棄却，通過など）

が TCAM 内のどの位置に格納されているかを返す記憶デバイ

をパケットに対して行う．図 1 にアクセス制御リストの例を示スである．TCAM の各ビットには 0，1 および任意の値を表す

す．ルータにおける ACL の指定は，完全一致だけでなく，範* を格納することができる．検索は入力として探索キーが与え囲指定も可能なものが数多く存在する．特にポート番号についられたとき，そのキーの値と完全に一致する TCAM エントリては単一のポート番号を指定するだけでなく，任意の数値によのアドレスが返される．これを利用して，ルータでは ACL でる範囲指定が頻繁に行われる．しかしながら一方で，TCAM

制御したいパケットのヘッダ情報を TCAM に格納し，到着しは完全一致あるいは部分一致でなければ検索することができなたパケットのヘッダ情報を入力として TCAM を検索する．そい．部分一致検索の場合，範囲が 2 のべき乗であれば単独エン

して，該当するエントリが見つかれば，そのエントリに対するトリにより表現可能であるが，それ以外の任意の範囲について処理を行う．

は部分一致検索エントリを複数組み合わせなければならないた

CAM には，入力データに対して完全に一致したエントリ

め，ACL に対する必要 TCAM エントリ数が増大することにのみを返す Binary CAM (BCAM) と，* を使用することになる．これをプレフィックス展開 (Preﬁx Expansion) と呼ぶ．

よって * 以外の範囲の部分一致検索を行える Ternary CAM

通常，ACL の設定は人間の手によるものであり，その結果とし(TCAM) が存在する．ルータの経路表や ACL における IP アてポート番号の範囲指定は人間が理解しやすい値（5，10，100

ドレスの格納については，アドレスにおけるホスト ID 部分の単位など）で指定されることが多い．このことが，2 のべきを * で表現することで，ネットワークの単位で集約できること

乗で表現される TCAM の範囲指定との不整合を生じさせ，結など，TCAM との親和性が高い．しかし，範囲で表現されて果としてプレフィックス展開によるエントリ数はより多くなる

いるポート番号を格納するためには，IP アドレスのような単傾向になる．

純な集約を行うことができず，範囲に該当するすべてのエント

ポート番号の範囲指定によるエントリ数の削減手法はこれまリを記述することになる．たとえば，1024–65535 で指定されでにも検討されているが，いずれの手法においても，TCAM

たポート番号の範囲を格納する場合，もっとも単純な方法は，デバイスはあくまでも既存のものを使用し，ソフトウェアある

1024，1025，. . . ，65534，65535 のすべてのエントリを個別に

いは外部デバイスの併用によりエントリ削減を実現しようとす

記述し，完全一致による検索を行うことである．しかしこの方るものである．しかしながら，TCAM デバイス自体に拡張を法では 1 つのポート範囲を指定するために 64,512 行のエント

加えることによってどの程度エントリが削減できるか，というリが必要になり，資源を大量に消費する．本稿ではこれをフル点についてはこれまで検討されていない．

展開と呼ぶ．

そこで本稿では，プレフィックス展開による TCAM 消費量

この問題を解決するために，これまでにプレフィックス展開の増大を抑制するため，範囲指定回路 (RMD; Range Matchingと呼ばれる方法や範囲比較のためのハードウェア回路の導入な

Device) を既存の TCAM に組み込んだ改良型 TCAM チップ

どの手法が検討されている．本章では，これら既存の解決手法を提案する．TCAM 内に RMD を実装することで，外部からについて紹介し，その問題点について述べる．

は既存の TCAM と同様の利用法を維持しつつ任意の範囲指定

2. 1 プレフィックス展開

を容易にサポートすることが可能となり，トータルとしてハー

複数のポート番号を単一のエントリで記述するために，TCAM

ドウェアコストを軽減できることを示す．さらに，RMD の容の * を用い，ポート番号の下位ビットを * で格納することが考量が不足した場合においても，範囲指定がより柔軟に行えるよえられる．下位 i ビットを * とした場合，2i の単位で範囲を記—2—

述することが可能である．これを用いることで 1024–65535 は

1*************** 32768-65535

Normal
Src/Dst

D Q
En

D Q

Magnitude
comparator

01************** 16384-32767
01001************* 8192-16383
0001************ 4096-8191

A
B

From
[15:0]

000001********** 1024-2047の 6 行で表現できる．これをプレフィックス展開と呼ぶ．

A㻢B?1:0

D Q
En
A

00001*********** 2048-4095

BTo[15:0]

A㻡B?1:0
D Q

Search Line(a) Example of Range Matching Device

一の ACL に対して数多くのエントリ数を必要とする．このた

Conventional TCAM

Bits added for RMD

め，さらにエントリ数を削減する手法についてこれまでにも検SourceIP(32 bit)

DestinationIP(32 bit)

SourcePort(16 bit)

DestinationPort(32 bit)Protocol(8 bit)[2] では，ACL にある範囲をエンコードし，各範囲をそれぞれ一つのビットにマッピングする技術である．さらに，一つのInternal Search Key :範囲をエンコディングした結果，他の範囲に与える影響も考6.20 に比べ，1.23 まで削減できることを示している．TCAMの検索ビット長は限られていることから，範囲の種類が多くなるほど，TCAM でのアクセス回数が増加する．また，マッピングを行うために別のメモリが必要となり，検索回数が増加す

Hit

Load
Enable

エントリ数を削減することは可能であるものの，依然として単慮し，ポート範囲が TCAM に格納される際の平均フル展開率

0
1

D Q
En

D Q
En

フル展開と比較して，プレフィックス展開は大幅に必要 TCAM

討がなされている．

RMD

Port Range From and To in RMD :Search Key :

2436

1

*

*

*

*

*

1

*

*

*

*

*

1

*

*

*

*

*

1

*

*

*

*

*

1

0

1

0

0

0

6970
6999
2326
2837

3230
3253

HIT

1024
65535

5555
6555

(b) Bits for Range Matching Device in TCAM

図 1 Example of Range Matching Device with TCAMるなどの問題点が考えられる．
また [3] では，ポート番号で指定された範囲をできるだけ 2

ずポート番号を除いた情報で TCAM による完全一致検索をのべき乗で表現できるように，ACL で指定されたポート範囲

行い，ヒットしたエントリについて，さらに指定された L4Opに，ACL の挙動に悪影響を与えない制約内でポート番号範囲のの比較演算を満たすかどうかを検証することで行われる．こ

追加削除を行い，異なる ACL における範囲の共通化，簡略化

れにより，範囲指定されたポート番号は TCAM に格納するこをすることにより，必要エントリ数を削減する．最適化がなさとなく独立に L4Op において管理され，ACL のルールは単一れることにより，エントリ数が最大 50% 削減できることを示

TCAM エントリで表現することが可能となり，TCAM によりしている．しかしながら本方式では，最適化のために ACL 情

多くの ACL を格納することができる．

報をオリジナルのものから変更しなければならず，実 ACL としかしこの手法での最大の問題は TCAM の外部に L4Opの整合性がとりにくい．さらに，ある ACL のポート番号範囲

ハードウェア回路を実装している点である．L40p では TCAMが変更された場合，範囲に対する依存関係が複雑になっているへの格納データが，ポート番号によるものと全くフォーマット

ために，更新が必要となるエントリが多く発生するなど，ACLが異なるため，外部から TCAM へ検索データを入力する際，の更新に対して柔軟に対応できないという問題がある．

他の方式と同じ処理レートを実現するためには，L40p フォー

一方 [4] では，ある範囲を，プレフィックス展開するのではな

マットとポート番号フォーマットによりデバイス間で消費する

く，任意の三値 (0**1*0) を使用し，範囲のコーディングを行っ

I/O バンドが倍増してしまう．即ち，同一動作周波数のもとでている．このコーディングの結果は，一つのエントリで使用さはデータ入出力ピン数を 2 倍に拡張しなければならない．デバ

れていないビット空間に書き込んでいる．結果より，エンコー

イスの物理サイズが同一の場合，外部 I/O のための入出力ピンドに 32 ビットを使用した場合，全体のエントリ数を最大 50%

数を増やすと，相対的にピン間隔が狭くなり，より高い精度での削減可能である．しかし，[4] 自体でも指摘されているが，最適結線が求められる．また近年の高速ハードウェアデバイスでは，なエンコード手法は ACL の内容に依存し，最適解を得るため

Signal Integrity およびピン間干渉 (SSO (SimultaneousSignalのアルゴリズムが事前に決定できない，という問題点がある．

Output) noise) が重要なファクターとなっており，配線数が多2. 2 比較演算ハードウェアによる範囲指定

くなることによってピン間干渉ノイズばらつきが増大するため，

Cisco の IP ルータでは，範囲指定されたポート番号をよりノイズに対する対策も必要とされ，ボード設計の自由度が制約

少ない TCAM 資源で格納するため，外部に L4Op (Layer-4

される，多層化が必要となるなど，ボード設計に多大な労力と，

Operation Unit) を実装している [5]．これは，ポート番号に対コストを払う事になる．

して比較演算を可能とするハードウェアである．具体的には，

L4Op にポート番号および比較演算子 (gt (greater than)，lt(less than)，range，neq (not equal)) を指定し，入力された以上のことから，同様の動作をするハードウェアチップであれば外部ピン数がより少ない方が望ましい．

3. 範囲指定を実現する TCAM ハードウェア

ポート番号が，指定された比較演算を満足するかどうかを判定する．範囲指定された ACL のルールを満たすかどうかは，ま2. で述べたとおり，プレフィックス展開の最適化および L4Op

—3—

WL

8n + 0ML
8n + 1MLML
8n + 3ML
8n + 4ML
8n + 5ML
8n + 6WL

1

2Invert2Entry-And

4Entry-And

PE – Exclusive : 1 + b + c

LINES

8n + 7

8Entry-And

図 2 NOT/AND Operation Partax

PE – OR : a

4

LINES

LINE

ML

Prefix Expansion for range

WL

PRIORITY ENCODER

8n + 2WL

ADD : SHIFT THE LEFT CIRCUITS BY

Match
-Amp

ADD : SHIFT THE LEFT CIRCUITS BY

ML

ADD : SHIFT THE LEFT CIRCUITS BY

Entry

y

1
c

b

図 3 Preﬁx Expansion Algorithmsともできる．本稿では従来の OR に加えて，TCAM エントリの NOT および AND を実現するための TCAM 拡張について検討する．図 2 に NOT/AND 演算を追加した TCAM 回路の修正図を示す．まず左側の回路で NOT 演算を実現する．次に，論理積である AND については，必要に応じて動的にハード
ウェア回路を変更することはできないため，あらかじめ 2，4，

によるエントリ数の削減は，最適化が困難，更新が容易ではな
い，あるいはハードウェアの性能に影響を与えるなどの問題が存在する．これらの手法はあくまでも TCAM デバイスは既存のものを使用し，ソフトウェアあるいは外部デバイスの併用によりエントリ削減を実現しようとするものである．本稿では，TCAM デバイスの拡張によりポート番号の範囲指定をサポー
トし，エントリ数の削減を目指す．
ここでは TCAM の拡張として，範囲判定回路の追加，およびエントリ間論理演算子の追加について検討する．個別の詳細について以降の各節で説明する．

3. 1 範囲判定回路 (Range Matching Device)
図 1(a) は 提 案 す る 範 囲 判 定 回 路 Range Matching De-

vice (RMD) を示している．入力線として，Normal，RMD，
Src/Dst，From，To，Load Enable，Search Line があり，出力線として Hit がある．Normal と RMD は，ユーザが最初に
このデバイスを普通のメモリとして使用するか、範囲を記憶するデバイスで使用するかを決める入力である．RMD にある範囲を記憶させるには，Load Enable により，その範囲が送信元
か宛先か区別する Src/Dst に信号をセットする．同時に，ポー
ト番号範囲の From と To の値を 16 ビットで入力する．
検索時は，上記で設定された，情報を元に，送信元ポート番
号，宛先ポート番号から，どちらかが選択され，From およびTo との大小比較が行われる. From より大きく，かつ To より小さい場合に，Hit が 1 となる．このようにして各 RMD は，検索対象のポート番号に対して範囲内かそうでないかを 0 ある
いは 1 で返す．各 RMD の Hit は TCAM の範囲比較ビットに送られる．TCAM では，送受信 IP アドレスとポート番号，
プロトコル番号などのフィールドに加え，RMD 判定用のビッ
トを割り当てる．RMD ごとに 1 ビット割り当てて，使用したい範囲を持つ RMD に対してビットを 1 にセットし，残りを *にセットする．図 1(b) に TCAM 内の構造例を示す．この例の場合，2 行目のエントリは 2326–2837 の範囲を指定するため，

TCAM 内の RMD の部分は *1*** となる．このときポート番
号 2436 は，各 RMD での検証の結果，01000 となり，2 行目のエントリにヒットすることがわかる．

3. 2 エントリ間論理演算回路
TCAM エントリへのアクセスは少なくとも一つ以上一致す
るエントリが見つかった場合に検索が成功したと判断できることから，各エントリの結果を論理和で演算していると考えるこ

8 エントリの論理積をあらかじめ実装し，ACL のプレフィック
ス展開に応じてどの位置に記述するかを決定する．

4. TCAM デバイスの制御
4. 1 RMD 格納ポリシー
RMD の回路数は有限であり，TCAM 内部の仕様で決定されたものである．したがって，エントリ数の削減を最大限にするためには，もっとも削減効果の高い範囲を RMD に入力することが望ましい．そこで本稿では，RMD へ格納するポート
番号範囲の順位付けを以下で定義する Weight に基づいて決定する．

Weight = (プレフィックス展開後の行数-1) × (その範囲を参照している ACL 数)
すなわち，プレフィックス展開により多くのエントリが必要になるほど，あるいはその範囲を持つ ACL 数が多い範囲ほど
より RMD へ格納される傾向が強いことを意味する．

4. 2 プレフィックス展開の最適化
本節では，3. 2 で拡張した，エントリ間の NOT/AND/ORを実現する TCAM を用いたプレフィックス展開の最適化アルゴリズムについて示す．ここでは，最適化の程度および実現の容易さを勘案した 3 種類のアルゴリズムを提案する．図 3 にア
ルゴリズムの概要を示す．PE-OR は，従来のプレフィックス展開である．範囲を 2 のべき乗の組み合わせにより表現する．

From が 2i で，To が 2i+1 − 1 の時に最も優れていて 1 行で表現できる．ただし，16385-65534 の場合は，最悪値である 29
行となる．

PE-Exclusive は，範囲全体を完全包含する [2i –，2i+1 − 1]を決定し，不要部分を 2 のべき乗の組み合わせにより表現する．
この手法は PE-OR では表現が難しい範囲に効果的である．たとえば 16385-65534 の場合，PE-Exclusive を用いることで，16384-65535 AND (NOT 16384) AND (NOT 65535) の 3 行で表現できる．PE-OR と PE-Exclusive は補間関係にある．

PE-MIN は，総当たりによりもっともエントリが少なくなる
よう最適化されたプレフィックス展開を求める．以下にアルゴ
リズムを示す．
（ 1 ） まず，範囲 [x, y] 内に存在する k2x (1 <= 15) のう=x<
ち x がもっとも最大になるものを選択し，それを 基準点 b とする．さらに範囲を基準点を境界として 2 つに分割する（ 2 ） 基準点より大きい範囲について，b = j2i < x <=—4—Range Matching Device
with PE-MIN

Required Exact Matching Lines

600

10, 580400

7, 72212, 586600
7, 52814, 407200

Number of Range Matching Device

Number of Range Matching Device(a) Full Expansion

72

64

56

48

40

72

64

56

48

40

32

24

8

16

0
0

56

48

40

32

24

8

16

1

0

0

200

800
400

11, 410

10

1000

32

100

Apr.07, PE-OR

800

24

1000

Oct.07, PE-OR

1200

8

10000

1400

Apr.07, PE-MIN

Total Lines

Total Lines

1000001600
Oct.07, PE-MIN

16

1000

0

1200

1000000
Total Lines

10000000

Range Matching Device
with PE-OR

Number of Range Matching Device(b) Using Preﬁx Expansion with Range Matching Devices

図 4 Comparisons of Total Required Entries (w/ or w/o RMD)

表 2 Two ACL Sets for Evaluation

Comparison of Each Prefix Expansion Method

Apr. 07

Oct. 07# of unique ACL entries

6,440

7,202

16
Number of Lines after Prefix Expansion

Date Captured

Src Dest Src Dest
# of ranges

3

256# of unique ranges

6

63

325
74

(j + 1)2i を満たす最大の i(i < x) を求める
i

PE-OR

12

PE-Exclusive
PE-MIN

10
8
6
4
2
0

Sorted Distribution of 63 Uniq Ranges after Prefix Expansioni（ 3 ） [j2 , x] および [x, (j + 1)2 ] の 2 つの範囲について，
プレフィックス展開をした場合のエントリ数をそれぞれ再帰的14

図 5 Comparisons of Preﬁx Expansion Algorithmsに求め，それぞれ xl , xr とする（ 4 ） xl < xr なら，プレフィックス [b, j2i ] を追加，そうできく減少させることができる．特に，RMD の数が少ない場合なければ [b, (j + 1)2 ] を追加するの削減効果は大きく，提案方式である PE-MIN を用いた場合，（ 5 ） 基準点より小さい範囲も同様に求める

Oct.07 で 10 個，Apr.07 で 11 個の RMD があれば，必要エ

i

5. 評

価

本章では，実運用されている ACL を用いて，実際に範囲指ントリ数をそれぞれ半減させることが可能となる．また，従来方式である PE-OR の場合は，7 個の RMD でそれぞれ半減できる．

定されていてるポート番号を TCAM に格納したときに必要とさらに PE-MIN と PE-OR を比較すると，必要エントリ数

なるエントリ数について評価し，その結果について考察する．

は同じ数の RMD を用いた場合で，AND/NOT 比較演算子を評価で使用した ACL の概要を表 2 で示す．評価には稼働中の追加することで，約 25%のエントリ数を削減することが可能でキャンパスネットワークルータにおいて異なる時期に取得したある．PE-OR を用いて，PE-MIN と同程度の削減効果を得る

2 つの ACL を用いている．

ためには，RMD をさらに 2 から 3 個追加する必要がある．

5. 1 比較判定回路によるエントリ削減効果

5. 2 比較演算子を用いた最適化プレフィックス展開の効果

まず，比較回路によるエントリ数の削減効果について，図 4提案したプレフィックス展開アルゴリズムの違いによる影響により示す．図 4(a) は，範囲指定されたポート番号すべてをを調べるため，各方式によって ACL の必要エントリ数がどの個別のエントリとして格納（フル展開）した場合の必要エンように変化するかを調べた．図 5 は各展開アルゴリズムを用いトリ数を示したものである．この図より，比較回路が存在しなてプレフィックス展開を行った場合の各 ACL ルールに対するい場合は必要エントリ数が 100 万オーダになることがわかる．

必要エントリ数を比較したものである．結果として，PE-MIN

これは，クライアント側の動的ポート指定として使用されるを使用することにより，PE-OR と比較して必要エントリ数を1024-65535 の範囲が，フル展開により 64,512 エントリ消費約 25% 削減できることがわかる．

することが大きな要因である．このため比較回路を 1 つ実装

エントリ削減数のみを考えた場合，PE-MIN がもっとも少なし，そこに 1024-65536 を格納するだけで，必要エントリ数をいエントリ数を実現できているが，TCAM 内部に NOT およ

約 1/10 にまで軽減できる．

び AND の演算回路が必要になる．

次にプレフィックス展開を行った場合の RMD の削減効果に

5. 3 比較判定回路によるコストオーバーヘッドの検討

ついて，図 4(b) に結果を示す．節の RMD 格納ポリシーに基

最後に，RMD を追加することによるハードウェアのコスト

づき，Weight の値が最も大きくなるポート番号範囲より RMD

増加について検討する．図 6(a) に現在流通している 90 nm プに格納することを考える．その結果，プレフィックス展開を行っ

ロセスルールによる TCAM のハードウェア構成を示す．このた場合，RMD を追加することによって，必要エントリ数を大ハードウェアの要素ごとの構成比率は図 6(b) で示されている．

—5—

となる．

I/O buffer
Row Decoder
Priority Encoder

Control Logic

PLL

Sub TCAM Array

図 7(b) は，RMD を追加することによる節約可能なメモリをTCAM Array

示したものである．ここでは，データビットを 104，144，288，

432，576 ビットである場合，それぞれに対して RMD が増加
I/O buffer

した場合，各 RMD の数において節約できるメモリ量を示してGlobal-SL Driverいる．
この結果より，RMD の個数を増加させることによりはじ

SL/Write Driver
Pre-Amp.

めはメモリを削減することができるものの，ある値より多い

RMD を導入した場合，そのオーバーヘッド増の影響が大きく，(a) TCAM VLSI in 90nm Technology

必要メモリサイズが削減できないということが分かる．また，

Fuse
1%
ColDrv
2%

Control Logic :GLUE + ColDrv = 8%305K Gates

GLDrv
1%

データビットが短ければ短いほど，RMD が多くなると無駄にEtc
8%なるメモリ空間が増加する．それぞれのデータビットに対して，

RowDec4%GLUE
6%TCAM array
48%

IO
7%

WD/PRE/LSL
7%Match_Amp
9%(b) Cost compared to the existing chip

図 6 Existing TCAM and Cost comparision with suggested hard-ware

6. まとめと今後の課題
本稿ではアクセス制御リストの中で特に範囲で表現されているポート番号を TCAM でより効率的に管理するため，プレフィックス展開と範囲比較デバイスの併用した，新しい TCAM
アーキテクチャを提案した．またさらにエントリを削減するための範囲指定方法，および最適化プレフィックス展開手法も提xExact Match&
Don’t CarePort #

Port Ranges
using Range
Matching Device
Port Ranges
using
Prefix Expansion(a) Reduced and Increased

Saved Memory (Kbit)

Memory (Kbit)

Total Lines

ベース中に，範囲で表現されているポート番号の比率にも依存と考えられる．

PE
7%

RMD: 580 Gates x 200 RMDs x 2(margin) = 232K Gates
Current TCAM : TCAM with RMD = 100 : 106

Data bits

最も節約できるメモリ空間の最適 RMD 数は，ACL のデータ

案し，実運用 ACL を用いた評価により，提案アーキテクチャ

200

が既存のプレフィックス展開よりもより効率的に ACL を管理

100

できることを示した．今後の課題としては，多様な実運用 ACLを使用して提案手法を評価することと，実際に改良ハードウェ0
0 5 10 15 20 25 30 35 40 45 50 55 60
-100
-200

576
432
288

-300

144

アを搭載したチップを試作し，ネットワークプロセッサ全体の性能を評価することなどがある．
謝

辞

104

本研究の遂行において，多大なるご協力をいただいた，大阪-400
Number of Range Matching Device(b) Saved Memory Space

Memory Space

図 7 Wasted and Saved Memory when Range Matching Devices

are used

このうち，全体の約 8% を占める Control Logic の構成ゲート
数はおよそ 305 K である．一方 RMD は 1 つあたり 580 ゲー
トを使用する．この RMD を 200 個搭載するためには，レイア
ウトマージンを含めるとおよそ 232 K ゲート必要になる．これは，TCAM 全体の約 6% に相当する．したがって，6% 程度の製造コストの増加によって，TCAM の必要エントリ数を大幅に削減することが可能となり，より多くの ACL を格納することができる．なお，構成比率については今後 65 nm に移行しても大きく変化しないものと考えられる．
また，図 7(a) に示すとおり，RMD を 1 個増加させると，その RMD にマッチするかどうかを判定するために TCAM のビットが 1 ビット必要となる．RMD を増加させることにより必要エントリ数を削減できる一方で，RMD 判定用に TCAM

大学サイバーメディアセンター准教授，長谷川剛博士に謝意を示す．また，本評価の一部は株式会社ルネサステクノロジイン
ターンシッププログラムにおいて行った．関係諸氏に感謝申し
上げる．
文

献

[1] H. Liu, “Reducing Routing Table Size Using TernaryCAM,” Hot Interconnects (HoTI), vol. 9, no. 2001, pp. 22–
24, 2001.
[2] H. Che, Z. Wang, K. Zheng, and B. Liu, “DRES: Dynamic
Range Encoding Scheme for TCAM Coprocessors,” technique report, Univ. of Texas at Arlington, http://crystal.
uta. edu/hche/dres. pdf, 2006.
[3] Q. Dong, S. Banerjee, J. Wang, D. Agrawal, and A. Shukla,“Packet Classiﬁers In Ternary CAMs Can Be Smaller,”in ACM SIGMETRICS ’06/Performance ’06, (New York,NY, USA), pp. 311–322, ACM Press, 2006.
[4] K. Lakshminarayanan, Rangarajan, and S. Venkatachary,“Algorithms for Advanced Packet Classiﬁcation withTernary CAMs,” in ACM SIGCOMM ’05, (New York, NY,
USA), pp. 193–204, ACM Press, 2005.
[5] M. A. Ross, S.-D. Chen, and A. V. Bechtolsheim, “Logical Operation Unit for Packet Processing, US Patent
6,658,002,” December 2003.

の検索ビット長が増大するため，両者のトレードオフを考慮しつつ実装する RMD の数を決定する必要がある．

—6—