クアッガアーキテクチャ
最初に、クアッガの一般的なアーキテクチャに関するいくつかの言葉。 Quaggaは、それぞれが特定の機能を実行するいくつかの個別のプログラムまたはデーモンで構成されています。 たとえば、ospfdデーモンはOSPFを実装し、bgpdはBGPを実装します。 Quaggaの中心的な役割は、zebraデーモンが果たします。 その主な役割の1つは、特定のプロトコルを実装し、さまざまなソースから受信した最適なルートを選択するデーモンからルーティング情報を取得することです。 その後、最適なルートがLinuxカーネルに転送され、実際にユーザートラフィックが転送されます（LinuxにQuaggaがインストールされていると思われます）。 したがって、ルーターの「インテリジェンス」（コントロールプレーン）とユーザートラフィックの送信（データプレーン）の古典的な分離が実装されます。 この場合、Quaggaはコントロールプレーンとして機能し、Linuxカーネルはデータプレーンとして機能します。 Quaggaルーティングテーブルはzebraデーモン内にあります。
ルート情報の保存
ルーティングテーブル内の個々のルートは、プレフィックス（通常はIPアドレスとプレフィックス長、たとえば192.168.0.0/24として示されます）として表すことができ、異なるルーティング情報に関連付けられます：ネクストホップ、アドミニストレーティブディスタンス、メトリック、ルートを報告したプロトコルなど ルーティングテーブルは、関連付けられた追加情報を備えた単純な多数のプレフィックスです。 zebraデーモンは、渡された、またはzebra自体で設定されたすべてのルートを保存します。 たとえば、ネクストホップ1.1.1.1を使用して静的ルート192.168.0.0/24を構成し、ospfdデーモンとネクストホップ2.2.2.2から同じプレフィックスを持つルートを受信した場合、zebraはこれらのルートの両方を保存して表示しますそれらは、show ip routeコマンドの出力に含まれます。 すべてのルートを保存すると、何らかの理由で現在の最適ルートが存在しなくなった場合に、新しい最適ルートをすばやく選択できます。 たとえば、この例では、静的ルートを削除した後、zebraはospfdデーモンを呼び出さずにすぐに最適なOSPFルートを選択します。 図に示すように、特定のプレフィックスのルートはリンクリストとして保存されます（この場合、プレフィックス192.168.0.0/24）。 最適なルートは緑色でマークされています。
次のルートを受信すると、そのルート情報がリンクリストの先頭に追加され、その後、特定のプレフィックスのすべてのルートを順番に表示して最適なルートを選択する手順が開始されます。 最適なルート（ネクストホップの有効性の対象）は、アドミニストレーティブディスタンスが最小のルートです。 デフォルトでは、異なるプロトコルからのルートは異なるアドミニストレーティブディスタンスを持つため（たとえば、OSPFには110があり、スタティックルートには1がある）、最適なルートを選択するための決定基準はアドミニストレーティブディスタンスです。 異なるルートに同じアドミニストレーティブディスタンスが設定されるような設定の場合、メトリックが最小のルートが最適です。 ルートのアドミニストレーティブディスタンスとメトリックが同じ場合、リストの最後に近いルート、つまり 前に追加されたもの。
ルートを削除すると、このルートは特定のプレフィックスのルートのリストから削除され、最適なルートを選択する手順も開始されます。 たとえば、静的ルートを削除すると、画像は次のようになります。
最適なルートを選択すると、その情報がLinuxカーネルに送信されます。
プレフィックスストレージ
原則として、1つのプレフィックスに対して多くのルートは存在せず、それらすべてを調べて最適なルートを選択するのにそれほど時間はかかりません。 はるかに難しいタスクは、ルートを追加または削除するときにプレフィックス自体を見つけることです。 ルーティングテーブルには多くの異なるプレフィックスが存在する可能性があります。数千から数万、そして正しいプレフィックスを見つけるためにすべてのプレフィックスを単純に順番に検索するのは非常に非効率的です。 より高速で効率的な検索のために、ルーティングテーブル内のすべてのプレフィックスは、コンパクトトライまたは圧縮バイナリプレフィックスツリーと呼ばれる構造として保存されます。
将来的には、プレフィックスはバイナリ形式で表現するのがより便利になりますが、最初のビットのみをプレフィックスの長さに等しい量で示します。 プレフィックスの残りのビットは0であり、検索には重要ではありません。 たとえば、バイナリのプレフィックス10.0.0.0/8は00001010のようになり、プレフィックス128.0.0.0/1は10のように1、128.0.0.0 / 2のようになります。
トライまたはプレフィクスツリーとその仕組みは、たとえばここで読むことができます 。 私たちの目的にとって、それを理解する最も簡単な方法は例です。 たとえば、プレフィックス1、111、010、0110000があります。これらのプレフィックスは、次のプレフィックスツリーとして編成されます。
白いノードは、興味のあるプレフィックスに対応しています。 黄色のノードは中間であり、ツリーの構造を適切に編成するのに役立ちます。 最上位ノードはツリーのルートであり、プレフィックス0.0.0.0/0に対応します。 目的のプレフィックスの検索は、次のように実行されます。 検索はツリーのルートから始まります。 次に、目的のプレフィックスの最初のビットがチェックされます。 最初のビットが0の場合、左の子に進みます。 最初のビットが1の場合、右の子へ。 次に、目的のプレフィックスの2番目のビットについてこの手順を繰り返し、次に3番目のビットについても同様に繰り返します。 目的のプレフィックスに到達するか、存在しないことを確認するまで。 必要なプレフィックスがない場合、適切な場所のツリーに追加されます。 ツリーへのアクセス数は目的のプレフィックスの長さに等しく、最長のIPv4プレフィックスは32であることがわかります。厳密には、ノードの場所によって一意に決定されるため、ツリーの各ノードにプレフィックスを保存する必要はありませんが、明確にするために指摘しました。 また、実際のQuagga構造では、プレフィックスは実際にツリーの各ノードに保存されます。
圧縮されたプレフィックスツリーは、分岐することなく長いチェーンを最適化するという点で通常のものと異なります。 この例では、圧縮されたプレフィックスツリーは次のようになります。
現在、現在のノードでプレフィックスを検索するとき、目的のプレフィックスの最初のnビットがノードのプレフィックスビットと一致するかどうかを確認します。nはノードのプレフィックスの長さです。 ビットが一致する場合、n + 1番目のビットの目的のプレフィックスを調べ、0または1のどちらであるかに応じて、左または右の子要素に移動します。
たとえば、プレフィックス011000は次のように検索されます。 通常どおり、ツリーのルートから開始します。 この場合のルートには長さ0のプレフィックスが含まれているため、目的のプレフィックスの最初のビットをチェックします。 0なので、左の子に行き、プレフィックス01のノードに到達します。ここで、目的のプレフィックスを現在のノードのプレフィックスと比較します。 プレフィックス011000の最初の2ビットがプレフィックス01と一致するかどうか。ビットが一致するため、次に進み、目的のプレフィックスの3番目のビットをチェックします。 3番目のビットは1なので、右の子に行き、必要な011000プレフィックスに入ります。プレフィックスを見つけるには、非圧縮ツリーの場合は7回ではなく3回ツリーを呼び出す必要がありました。 ある段階で、ノードのプレフィックスの最初のnビットが目的のプレフィックスのビットと一致しないことが判明した場合、これは目的のプレフィックスがないことを意味し、ツリーに追加されます。
Quaggaでは、プレフィックスはIPアドレスとプレフィックス長として保存されます。 この場合、最初のnビットのみが重要です。ここで、nはプレフィックスの長さで、残りは0であり、目的のプレフィックスの検索に参加しません。 たとえば、192.168.1.0 / 24というプレフィックスは次のようになります。
わかりやすくするために、次のように表示します。
ここの一番上に、10進数形式のプレフィックスの通常の形式を示します。以下に、赤でマークされたプレフィックスの長さに等しいビット数のバイナリ表現を示します。 このような指定では、プレフィックス0.0.0.0/0、10.0.0.0/8、172.16.0.0/16、192.168.0.0/24、192.168.1.0/24、192.168.2.0/24で構成されるルーティングテーブルは次のようになります。
たとえば、プレフィクス192.168.1.0/24を検索する場合、その1番目、2番目、23番目、および24番目のビットが順番にチェックされ、ツリー内の位置が検出されます。 各プレフィックスは、対応するルーティング情報も示します。 黄色で強調表示されているプレフィックスは中間であり、ルーティング情報はありません。
プレフィックスツリートラバーサル
最後に、show ip routeコマンドを入力したときに画像がどのように表示されるかを説明します。 ルートを表示するには、何らかの形でツリー内のすべてのプレフィックスをソートする必要があります。 この手順はツリートラバーサルと呼ばれ、さまざまな方法で実装できます。 Quaggaは、pre-orderedと呼ばれる回避策を使用します。これは、再帰的に定義するのが最も簡単です。
- 最初にツリーのトップを取得します。
- 次に、左のサブツリーを回ります。
- 次に、適切なサブツリーを回ります。
同じルールを使用して、サブツリーをバイパスします。 上記で作成したルーティングテーブルの場合、プレフィックスバイパスは次のようになります。 まず、ツリーの最上部、つまり プレフィックス0.0.0.0/0。 次に、左のサブツリーを回ります。 単一のプレフィックス10.0.0.0/8で構成されます。 次に、右のサブツリーを回って、図に表示します。
それを回避するために、同じルールを適用します。まず、そのルート、つまり 128.0.0.0/1プレフィックス、次にその左側のサブツリーをバイパスします。 接頭辞172.16.0.0/16、次に図に示す右側のサブツリー：
次に、このサブツリーの最上位、つまり プレフィクス192.168.0.0/22、左側のサブツリーをバイパスして、プレフィクス192.168.0.0/23、192.168.0.0/24および192.168.1.0/24、およびプレフィクス192.168.2.0/24で構成される右側のサブツリーを取得します。
したがって、次の順序でプレフィックスを取得します：0.0.0.0/0、10.0.0.0/8、128.0.0.0/1、172.16.0.0/16、192.168.0.0/22、192.168.0.0/23、192.168.0.0/ 24、192.168.1.0 / 24、192.168.2.0 / 24。 プレフィックス128.0.0.0/1、192.168.0.0/22、および192.168.0.0/23はサービスのものであり、ルーティングテーブルが表示されるときには表示されません。 残りのプレフィックスは、0.0.0.0 / 0、10.0.0.0 / 8、172.16.0.0 / 16、192.168.0.0 / 24、192.168.1.0 / 24、192.168.2.0 / 24の順に表示されます。
おわりに
結論として、上記の構造とアルゴリズムが実装されているQuaggaソースファイルのリストを示します。
Quaggaのソースは、download.savannah.gnu.org / releases / quaggaからダウンロードできます 。 バージョン0.99.24を使用しました。
プレフィックスを操作するための構造と関数は、lib / prefix.cファイルにあります。
プレフィックスツリーを操作するための構造と機能は、ファイルlib / table.cにあります。
ルーティング情報を操作するための構造と機能は、ファイルzebra / zebra_rib.cにあります