12.4. ハッシュフィルタ: 超高速大量フィルタリング

たくさんのクライアントやコンピュータがあって数千ものルールを必要とし、 そのすべてに別々の QoS 指定を行うと、カーネルはこれらのルールへのマッチに、 多くの時間を費やすことになるでしょう。

デフォルトでは、すべてのフィルタはひとつの大きなチェインに共存しており、 priority の順にマッチされていきます。1000 のルールがあったら、 パケットに対して何を行うか決めるには、 1000 回のチェックが必要となるかもしれません。

それぞれ 4 つのルールからなる 256 個のチェインのほうが、 マッチの速度はずっと素早くなります。 ただしパケットを、これら 256 のチェインうち、 適切なルールがあるものに分散させることが必要になります。

これはハッシュを用いると可能になります。いまケーブルモデムの顧客が ネットワークに 1024 名いるとしましょう。IP アドレスは 1.2.0.0 から 1.2.3.255 までで、それぞれ 'lite', 'regular', 'premium' などの、 別々のカテゴリに属しているものとします。 この場合は以下のような 1024 のルールが必要になるでしょう。

# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.1 classid 1:1
...
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.3.254 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.3.255 classid 1:2

IP アドレスの末尾部分を「ハッシュキー」として利用すれば、 これを高速化できます。こうすると 256 のテーブルができ、 その最初のものはこのようになります。
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.1.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.2.0 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.3.0 classid 1:2

次のテーブルはこのようになります。
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
  1.2.0.1 classid 1:1
...

このようにして、最大で 4 つのチェック、 平均で 2 つのチェックしか必要なくなります。

設定は極めて複雑ですが、これだけ多くのルールがあるような状況では、 十分作業に見合います。まず root にフィルタを作り、 256 のエントリがあるテーブルを作ります。
# tc filter add dev eth1 parent 1:0 prio 5 protocol ip u32
# tc filter add dev eth1 parent 1:0 prio 5 handle 2: protocol ip u32 divisor 256

ここでいま作ったテーブルのエントリにいくつかルールを追加します。

# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.0.123 flowid 1:1
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.1.123 flowid 1:2
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.3.123 flowid 1:3
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
        match ip src 1.2.4.123 flowid 1:2
これはエントリ 123 で、1.2.0.123, 1.2.1.123, 1.2.2.123, 1.2.3.123 へのマッチを含んでおり、それぞれを 1:1, 1:2, 1:3, 1:2 に送ります。 ここでハッシュバケツは 16 進数で指定しなければならないことにご注意ください。 0x7b は 123 です。

次に「ハッシュフィルタ」を作ります。これはトラフィックを、 ハッシュテーブルの正しいエントリに向けます。
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 800:: \
        match ip src 1.2.0.0/16 \
        hashkey mask 0x000000ff at 12 \
        link 2:
はい、ここで数字のいくつかについては説明が必要でしょう。 デフォルトのハッシュテーブルは 800:: という名前になります。 すべてのフィルタはここから始まります。次に IP ヘッダの 12, 13, 14, 15 バイト目にある発信元アドレスを選び、 この最後の部分にのみ注目していることを指定しています。 これは先に作ったハッシュテーブル 2: に送っています。

かなり複雑ですが、実際に動作しますし性能向上は驚異的です。 この例はさらに改良が可能で、 理想的には各チェインに 1 つのフィルタしか入っていない状況にできます!