LAN スイッチ:TCAM(Ternary CAM)とBCAM(Binary CAM)

さまざまなメーカから発売されるLAN スイッチのデータシートを見ると、ほとんどの製品がTCAM を実装しているのが分かります。

a

TCAM とBCAM の違い

TCAM(Ternary CAM、ターナリーCAM)とは何でしょうか? 従来のCAM と何が違うのでしょうか?

まずは、Ternary の意味を調べて見ましょう。
goo 英和辞書を見ると、

    三つ組の; 三元の; 第三位の; 【コンピュータ】3値の, 3進法の

とあります。
どうやら、キーワードは「三つ」にあるようです。

ディジタル・コンピュータが扱うデータを細かくしていくと、最後は0 か1 の二種類の値を表すビットになります。つまりBinary(バイナリー)です。

CAM に格納されるデータはディジタル情報なので、0か1 のどちらかです(バイナリー)。

※ 通常CAM と呼ぶときは、BCAM(Binary CAM)を指します。

TCAM もディジタル情報を扱うので、当然0 と1 です。
では、三つ目は何でしょうか?

答えは、Don't Care(ドントケア)です。
論理回路の勉強をしたことがある人は、聞いたことがあるのではないでしょうか?(ブール代数とかカルノー図とか)
0 と1 のどちらでも良いことを表す言葉です。0 or 1 です。

つまりTCAM は、検索対象に0、1、Don't Care の3 種類の状態が存在するわけです。


Don't Care は何のためにある?

0 と1 の2 種類しかないと、テーブル上の目当てのエントリーを検索で引き当てるためには、検索対象のエントリーが検索キーと完全に一致する必要があります。
Don't Care は0 と1 のどちらでも良い値です。つまり、検索する際に無視できるということです。

具体的には、検索対象のエントリーのうち、無視できる領域を表すマスクで表現します。
マスクと聞いてピンときた人もいますよね?
そうです。サブネット・マスクです。

サブネット・マスクは、IP アドレスのうち、ネットワーク部を意味する領域の大きさを表現するために使われます。
マスクされなかった部分はホスト部で、ネットワーク(サブネット)を表現する際には無視される部分です。

TCAM は、Longest Prefix matching(ロンゲストマッチと呼ばれるのが一般的)が必要なテーブル検索に利用されます。
ルーティング・テーブルやACL(Access Control List)の検索がもっとも多い使用例です。
レイヤ3 スイッチの多くがTCAM を採用しているのはこのためです。

これに対してレイヤ2 スイッチのMAC アドレステーブルは、TCAM である必要はありません。
MAC アドレスの検索にプリフィクスを指定する必要は無く、検索対象がキーと完全に一致していることが要求されるためです。

※ 仮に「MAC アドレスの先頭3 バイトが00-11-22 というエントリだけを探し出す」というような検索がMAC アドレス・テーブルに求められるのであれば、TCAM を使うメリットが出てきます。

しかし、MAC アドレス・テーブルをそのような目的で利用する機能は、現在はありません(今後もないでしょう)。


参考: なぜCisco のCatalyst はMAC アドレス・テーブルをCAM と呼ぶのか?