最近の仕事はLinuxのフロー制御に多少関連しています。数年前にTCについて知り、その原理をある程度理解して以来、触っていません。TCのコマンドラインは好きではありません。あまりにも扱いにくいからです。iptablesのコマンドラインも多少扱いにくいですが、技術的すぎるTCのコマンドラインよりは直感的です。もしかしたら、TCフレームワークに対する私の理解はNetfilterフレームワークほど深くないのかもしれません。その可能性はあります。iptables/Netfilterはtc/TCに対応しています。

Linuxカーネルには、トラフィックレート制限、トラフィックシェーピング、ポリシー適用（ドロップ、NATなど）を実装できるトラフィック制御フレームワークが組み込まれています。このフレームワークについて他に何が思い浮かびますか？今は思い浮かばないかもしれませんが、NetfilterフレームワークはTCフレームワークに似ていますが、両者には大きな違いがあることを簡単に述べておきます。

Netfilterフレームワークを習得すれば、TCフレームワークの理解ははるかに容易になります。特にNetfilterの限界を認識している場合は、それらの限界を念頭に置いてTCの設計に取り組むことで、TCがNetfilterの欠点の一部に対処していることに気づくかもしれません。詳細に入る前に、まず両者の類似点と、当初の意図の違いによる設計上の大きな違いについてご紹介します。

まず、Netfilterについてお話しましょう。このフレームワークは、ネットワークプロトコルスタックのカーネルパスに沿ってデータパケットをフィルタリングするように設計されています。まるで道路の検問所のようなものです。Netfilterは、プロトコルスタックがネットワークデータパケットを処理するパス上の5か所に、このようなチェックポイントを設置します。データパケットはこれらのチェックポイントを通過する際に検査され、受け入れ、破棄、キューイング、他のパスへのインポートなど、複数のアクションが実行されます。Netfilterフレームワークは、1つのデータパケットに対して1つの結果を生成するだけで済みます。チェックポイントが提供するサービスは、Netfilterフレームワークでは規定されていません。

さて、TC（Treatment Control）を見てみましょう。TCは、データパケットやストリームに対して、レート制限やシェーピングといったサービスを提供することを目的としています。これは、Netfilterのように単一の結果で表現できるものではありません。これらのサービスを提供するには、一連のアクションが必要です。したがって、「これらのアクションの実行をどのように計画し、体系化するか」がTCフレームワーク設計の鍵となります。言い換えれば、TCフレームワークは、アクションを実行するだけでなく、どのように実行するかに重点を置いています。簡単に言えば、Netfilterフレームワークは「何をするか」に焦点を当てているのに対し、TCフレームワークは「どのように行うか」に焦点を当てています。（Netfilterについては既に多くのコードと記事を書いているので、ここでは詳細は割愛します…）

レート制限とトラフィックシェーピングに関する理論は豊富にあり、トークンバケットは一般的な例です。しかし、この記事ではトークンバケットアルゴリズム自体ではなく、LinuxにおけるTCフレームワークの実装に焦点を当てています。短い記事では、フロー制御理論の歴史と様々なオペレーティングシステムにおけるその実装を詳細に説明することは不可能です。しかし、ほとんどの実装ではキューの使用が現実的な選択肢であることは周知の事実です。そこで疑問が生じます。LinuxのTCフレームワークはどのようにキューを整理しているのでしょうか？キューの構成について詳しく説明する前に、NetfilterとTCを最後にもう一度比較してみましょう。

UNIX のキャラクタ デバイスとブロック デバイスの違いを理解していれば、Netfilter フレームワークと TC フレームワークの違いも比較的容易に理解できます。Netfilter フック ポイントはパイプで接続されたキャラクタ デバイスに似ており、skb はこのデバイス内の一方向の文字ストリームです。通常、文字は入力された順序で一方の端から流入し、もう一方の端から流出し、ACCEPT または DROP などの結果を返します。一方、TC フレームワークはブロック デバイスに似ており、コンテンツへのランダム ストレージとランダム アクセスを実行します。つまり、skb パケットが入力される順序は、必ずしも出力される順序と一致しません。これはまさにフロー シェーピングに必要なことです。言い換えれば、TC フレームワークはフロー制御のために、このバッファ内にランダム アクセス パケット ストレージ バッファを実装する必要があります。もちろん、既に説明したように、これはキューを使用して実装されます。

もちろん、絶対的なものはありません。Netfilterのフックポイントは、ストレージバッファを持つ場合や、一連のアクションを実行する場合もあります。代表的な例としては、フラグメントの再構成やconntrackにおけるNAT機能などが挙げられます。PREROUTINGフックポイントにおけるフラグメントの再構成では、フラグメントはフックポイントに投入され、すべてのフラグメントが到着して再構成に成功した後、フックポイントから一斉に流れ出るまで、一時的に格納されます。NATの場合、Netfilterの処理結果はACCEPTだけでなく、「一連のアクションを実行する」ことに間違いなくなります。また、私はNetfilterを用いてフロー制御を実装するモジュールをいくつか作成しました。逆に、TCフレームワークはNetfilterの機能を実装することもできます。つまり、これらのフレームワークの設計原理と本質を理解すれば、容易に活用・拡張できるということです。

個人的には、単一のNetfilterフックポイントに対して、TCフレームワークはスーパーセットであり、実装の柔軟性は高いものの、複雑さも増すと考えています。TCにはないNetfilterの魅力は、フックポイントの位置定義にあります。

さて、それでは TC フレームワークの設計の正式な紹介を始めましょう。

タスク制御（TC）を紹介する多くのオンラインリソースでは、TCは「キュールール、カテゴリ、フィルタ」で構成されると説明されていますが、そのほとんどが曖昧です。あえて言えば、これらはすべて単一のドキュメントや書籍から派生したものです。TCフレームワークの設計を異なる視点から理解している人はほとんどいません。これは本質的に難しい作業であり、私は個人的にこの種の作業を楽しんでいます。TCのキュー構成を紹介する前に、まず再帰制御とは何かを説明したいと思います。再帰制御は階層的な制御であり、制御方法は各レベルで一貫しています。CFSスケジューリングに精通している人は、グループスケジューリングとタスクスケジューリングが全く同じスケジューリング方法を使用していることをご存知でしょう。しかし、グループとタスクは明らかに異なるレベルに属しています。この状況を簡潔に説明するために、次の図を描きました。

制御ロジックの構成だけでなく、LinuxでもUNIXプロセスモデルの実装において、このツリー状の再帰制御ロジックが採用されています。各レベルは2階層のツリー構造になっており、次の図に示されています。

ご覧のとおり、再帰制御はフラクタルです。これを説明するために、3次元の図を使用する方が適切でしょう。上の図では、リーフノードを除く各ノードは独立した小さなツリーです。大きなツリーでも小さなツリーでも、制御ロジックと組織ロジックの特性は全く同じです。

再帰制御により、X over Y (略して XoY)、PPPoE、IP over UDP (tun モードの OpenVPN)、TCP over IP (ネイティブ TCP/IP スタック) などのプロトコル スタック設計で見られる制御ロジックの任意の重ね合わせが容易になります。TC の場合、次の要件を考慮してください。

1. 帯域幅全体を TCP と UDP に 2:3 の比率で割り当てます。

2. TCP トラフィックでは、送信元 IP アドレスの範囲に応じて異なる優先順位に分割されます。

3. 同じ優先キュー内で、HTTP アプリケーションとその他のアプリケーションに 2:8 の比率で帯域幅を割り当てます。

4....

上記の要件からわかるように、これは再帰的な制御要件です。1と3はどちらも帯域幅割り当てを使用しますが、明らかに異なるレベルに属しています。全体的なアーキテクチャは次のようになります。

しかし、事態は見た目よりもはるかに複雑です。上の図はTCフレームワークを垣間見せてくれますが、実装の実用的な助けにはなりません。いくつかの典型的な問題が残っています。どのデータパケットをどのキューに割り当てるかをどのように特定するのでしょうか？図中の非リーフノードはどのようなデータ構造を表すべきでしょうか？それらは真のキューではありませんが、キューの振る舞いを示す必要があるため、どのように表現するのでしょうか？

LinuxがTurbo Cを実装した際、「キュー」の概念は抽象化され、基本的に2つのコールバック関数ポインタが保持されました。1つは「enqueue」操作用、もう1つは「dequeue」操作用です。「enqueue」も「dequeue」も、必ずしも実際にデータパケットをキューに入れるわけではなく、「一連の操作を実行する」だけです。この「一連の操作」とは、以下のようなものです。

1. リーフ ノードの場合、データ パケットを実際のキューに追加するか、実際のキューからデータ パケットを取得します。

2. 他の抽象キューの enqueue/dequeue メソッドを再帰的に呼び出します。

上記のポイント2で「その他の抽象キュー」について言及されています。では、この抽象キューをどのように見つけるのでしょうか？これには、パケットの特性に基づいて抽象キューに分類するための選択肢、つまりセレクタが必要です。TCの設計ブロック図は次のように表すことができます。

ご覧のとおり、TCフレームワークを「キュープロシージャ、カテゴリ、フィルタ」という典型的なトリプルで定義するのではなく、再帰制御の意味を用いて説明しました。この典型的なトリプルをこの図に適用すると、次のようになります。[テキストを削除した図の画像]。図が煩雑にならないように、不要なテキストを削除していることに注意してください。テキストについては、上の画像を参照してください。

変化にもかかわらず、根本的な原則は同じままであることは明らかです。つまり、諺にあるように、偉大な心は同じことを考えます。

さて、少し脱線します。Netfilter関連ですが、TCとの比較ではなく、個人的な考えを述べたいと思います。かつて私はCiscoのACLを高く評価していました。なぜなら、CiscoのACLはネットワークインターフェースカード（NIC）に適用されるのに対し、Netfilterは処理デバイスではなく処理パスでパケットを傍受するからです。Netfilterにとって、処理デバイスは単なる無意味な一致です。関連性に関わらず、すべてのパケットはNetfilterのフックポイントを通過しなければならず、少なくとも「-i ethX...」に一致するかどうかをチェックしなければなりません。そこで、`net_device`にフィルタリストを添付することを検討し、コードをいくつか書いてみたところ、うまく動作したので、採用することにしました。私は車輪の再発明をよくする人間で、TCの実装を見て、TCフレームワークこそがまさに私が求めていたものだと気づきました。そこで、Netfilterで実現できることはすべてTCでも実現できると断言しました。さらに、TCはキュー制御規則（データ構造フィールドはQdiscキュー制御規則として記述され、従来のトリプレット記法の影響を受けない）に基づいており、抽象的なエンキュー/デキューでは実装方法が規定されていません。さらに、キュー制御規則はネットワークインターフェースカード（NIC）（より正確には、NICが複数のキューをサポートしている場合はNICのキュー）にバインドされており、処理パス上でインターセプトされることはありません。したがって、2つの選択肢があります。

1. シンプルなFIFOキューを内蔵した新しいQdiscを実装します。エンキュー操作はNetfilterから移植されたマッチ/ターゲットを実行し、すべてのACCEPTパケットをFIFOにキューイングします。

2. 分類子を変更する：パケットをカテゴリに分類するかどうかは、パケットの特性だけでなく、追加のアクションコールバック関数の実行にも依存します。この関数が0を返した場合のみ、成功を表します。これはコールバックであるため、任意のアクション（ドロップ、NATなど）をコールバック内で実行でき、密室で必要な処理を実行できます。

上記のポイント1と2のうち、ポイント2は既に実装されています。ポイント1は実装が簡単で、キュープロシージャを実装する、つまり、各キュープロシージャにアクションを追加するだけです（次の図を参照）。

2 番目のポイントは比較的単純で、基本的には、以下の拡大画像に示すように、菱形の形状を操作することです。

こうして、長年の悲願であったTCフレームワークを用いたファイアウォールとNATの実装に至りました。実は以前からこのことは知っていましたが、TCコマンドは設定が専門的すぎる上に、メンテナンスがiptablesルールのメンテナンスよりも非常に難しいため、あまり好きではありませんでした。メンテナンスは極めて重要で、ルールの書き方を考えることよりも重要です。ルールを書くのは一瞬のことで、経験があればあっという間に書けます。問題に遭遇した時、お酒を飲んだ後のように、一瞬でひらめくこともあるでしょう。しかし、メンテナンスは長期的な取り組みであり、必ずしも自分がメンテナンスを行うとは限りません。テクノロジー社会は利他的な社会であるため、他者への配慮も欠かせません。

はい、これで十分です。基本的な部分は網羅し、詳細は省きましたが、フレームワークは提供できたと思います。TCコマンドライン自体は特に気に入っているわけではありませんが、各TCコマンドとカーネルデータ構造の関係を示す図で締めくくりたいと思いました。繰り返しますが、この図も詳細が不足しており、不完全です。`match` は重要ではないと分かっているので省略しています。

私の記事を読んでも、コピペして使えるようなものは見つからないかもしれません。コードやコマンドは省略されています。私自身も、何年も前に書いたものを見ると、とにかく早く動かしたいと強く思うのですが、なかなかそんなことはありません。しかし、私は実装よりもアイデアの方が重要だと考えています。実装や現実の背後にある本質を理解すれば、きっと自信を持ってスムーズに扱えるようになるはずです。