ディジクストラよりも高速？

昨年、ある人たちが私にネットワーク上で最短経路を求める新しい手法についての記事を転送してくれました。研究では、ほとんどのネットワーキング教科書（弊社教材も含む）で教えられているディジャストラの古典的アルゴリズムより優れていると主張しています。最初は懐疑的でした。まるで誰かがリーマン予想を証明したと言われた時のようにです。ディジャストラは伝説的存在で、彼の1959年のアルゴリズムはパケット交換より数年前に登場しました。OSPF仕様（リンクステート経路制御プロトコルの2大手のうちの一つで、もう一方がIS‑IS）は、実装者への指針として非常に詳細です。本質的にはディジャストラのアルゴリズムを使うようにというものです。これまで数十年にわたりほとんどの実装はそのままに、速度向上のためだけに小さな改良が加えられてきましたが、本質的な変更はありませんでした。

新しいアルゴリズムは小さなチューニングではなく、全く異なるアプローチを示しています。主張は「ディジャストラはソート操作が必要であるため、最良のソートアルゴリズムほどしか性能が出せない」という点に対し、この新手法は「ソート障壁を突破する」ことです。ソート自体を回避し、ディジャストラよりも優れた性能境界を達成すると言われています。

私は論文そのものを評価できる立場ではありませんが、ACM Theory of Computing Symposiumといったトップレベルの会議で査読を通過し、十分な検証を受けているため、その理論自体に疑いはありません。私が議論したいのは「本当に重要か？」という点です。

理論的性能向上が実際にどれほど影響するかを評価するとき、すぐに浮かんだ2つの主要な問題があります。

1. 実運用ルーティングシステムでのスケーリング限界
   ディジャストラの計算時間は、ノード数 n（ルータ）とエッジ数 m（リンク）のネットワークでは O(n log n + m) です。新手法は O(m log^(2/3)n) を主張しており、大きな n に対しては低くなるはずです。しかし実際に差が出るのは n がどれだけ大きくなるかによります。定数係数は両者で異なり、小さな n ではスケーラビリティが低いアルゴリズムの方が高速になる場合もあります。

   私が知ったところ、今日の大型 OSPF や IS‑IS コアネットワークではルータ数は数百台程度であり、最大規模のサービスプロバイダネットワークでも数千台にすぎません。BGP が扱うプレフィックス数と比べると小さいため、SPF 計算におけるスケーラビリティは制約要因ではありません。

2. 性能の他の側面
   Big Router で働いていた時期には MPLS と高速再ルーティング（FRR）を担当していました。FRR は MPLS を利用してリンク障害時に経路収束を待たずにパケットを迂回させますが、ルーティングプロトコルの開発者は収束時間の短縮に注力しました。MPLS と標準ルーティングの両方で最も重要なのは障害検出の速さです。OSPF の Hello パケットが欠落したことを確認するまで数十秒待たなければならないと、ミリ秒単位で最短経路を計算しても意味がありません。この考えから BFD（Bidirectional Forwarding Detection）が生まれました。BFD はリンク障害検出の高速かつ独立したメカニズムです。

   ルーティング収束に影響する他の要因は次のとおりです。

   • 新しいリンクステートパケットを送信し、ネットワーク全体で伝搬させる時間；
   • パケットを受信して OS の適切なプロセスへ渡す時間；
   • SPF 実行時間；
   • ルーティング情報ベース（RIB）を更新する時間；
   • フォワーディングテーブルへの影響を計算する時間；
   • 大型ルータでフォワーディングテーブルの更新をラインカードへプッシュする時間；
   • リンクステートパケットを隣接ノードへ洪水させる時間。

   これらのステップは何年にもわたって分析・最適化され、2003 年にはサブ秒収束が実現しました。SPF 計算時間を数ミリ秒削減するよりも、これらの部分を改善した方が重要でした。

結局のところ、ディジャストラアルゴリズムはエンジニアにとってコードを書きやすいという点で依然として実装方法として選ばれています。2001 年のインタビューでディジャストラは次のように語っています。

「論文自体は読みやすく、むしろかなり良いものです。私がそれをノートとペンなしで設計した理由の一つは、後で「避けられる複雑さ」を回避する必要があることに気づいたからです。」

言い換えれば：Keep It Simple, Stupid（簡潔に保とう）。私はエンジニアを OSPF 仕様書へ向かわせる方が、数ミリ秒だけ収束時間を短縮できるハイブリッド Bellman‑Ford/ディジャストラ アプローチを勉強させるよりも有効だと考えています。将来的に誰かがディジャストラの論文や OSPF 仕様書ほど明快な説明を書き、ハイブリッドアルゴリズムが大規模マッピングアプリケーションで素晴らしい結果を出すようになるかもしれません。しかし、実運用ルータにおいてディジャストラのアルゴリズムが置き換わる日が来るとは思いません。

---

関連読書

• 先日の Frank Gehry に関する投稿を受けて、NY Review of Books が彼について書いた優れた記事があります。
• 宇宙でのデータセンターはひどいアイディアです；動機があるなら FCC に知らせることができます。
• Wiki Education は Wikipedia への AI 生成参照を調査し、LLM が生成した参照は信じられるように見えても実際には記載内容を含まないことが多いと判明しました。これは LLM が何を語っているのか分からないようなものです。このような記事をクリーンアップするプロジェクトがあります。
• プレビュー画像は Unsplash の Shio Yang によるものです。