 |
制約付き最短パス優先（CSPF）は、最短経路アルゴリズムの拡張です。CSPFを使用して計算されたパスは、一連の制約を満たす最短経路です。これは、指定された制約セットに違反するリンクをプルーニングした上で、最短経路アルゴリズムを実行することを意味します。制約セットには、リンクごとに必要な最小帯域幅（帯域幅保証制約とも呼ばれます）、エンドツーエンド遅延、通過リンクの最大数、ノードの追加/除外などが含まれます。CSPFは、MPLSトラフィックエンジニアリングで広く使用されています。CSPFを使用したルーティングは、制約ベースルーティング（CBR）として知られています。
CSPF を使用して計算されたパスは、OSPFおよびIS-ISから計算されたパスとまったく同じになる場合もあれば、満たすべき制約のセットに応じてまったく異なる場合もあります。
帯域幅制約のある例
右側のネットワークを考えてみましょう。ここでは、x 単位の帯域幅制約を満たすルータ A からルータ C へのルートを計算する必要があり、各リンクのリンク コストはホップ カウント (つまり 1) に基づいています。
x = 50 ユニットの場合、CSPF はパス A → B → C を生成します。
x = 55 ユニットの場合、CSPF はパス A → D → E → C を生成します。
x = 90 ユニットの場合、CSPF はパス A → D → E → F → C を生成します。
これらすべてのケースでは、OSPFとIS-ISによってパス A → B → C が生成されます。
ただし、このトポロジ内のリンクコストが異なる場合、CSPFはそれに応じて異なるパスを決定することがあります。例えば、前述のように、A → BとB → Cを除くすべてのリンクのリンクコストとしてホップカウントが使用され、コストが4であるとします。この場合、次のようになります。
x = 50 ユニットの場合、CSPF はパス A → D → E → C を生成します。
x = 55 ユニットの場合、CSPF はパス A → D → E → C を生成します。
x = 90 ユニットの場合、CSPF はパス A → D → E → F → C を生成します。
参考文献
- Ziegelmann, Mark (2007).制約付き最短経路と関連問題. 制約付きネットワーク最適化. VDM Verlag Dr. Müller . ISBN 978-3-8364-4633-4。
