【ネットワーク】ネットワークの地図から最短ルートを計算!「ダイクストラ法とOSPF」|情報処理問題1000本ノック
ルーター同士が連携して最適なデータの抜け道を探すルーティング。OSPFプロトコルの頭脳として裏側で機能している超重要アルゴリズムを攻略しましょう。
1. 【 問題 】:OSPFで用いられる経路制御アルゴリズム
【 問題 】 ネットワークのルーティング(経路制御)プロトコルである「OSPF(Open Shortest Path First)」において、各ルーターがネットワーク全体の接続状態を表すトポロジーマップ(リンク状態データベース)を構築した後、自身を出発点として目的地までの累積コストが最小となる「最適経路」を動的に算出するために内部で用いている、グラフ理論の最短経路アルゴリズムはどれでしょうか?
① ベルマンフォード法 (Bellman-Ford Algorithm)
② ダイクストラ法 (Dijkstra's Algorithm)
③ プリム法 (Prim's Algorithm)
④ 二分探索法 (Binary Search)
2. 正解:
正解: ② ダイクストラ法
3. 解説:コストの数値を足し算し、最短を導く頭脳
OSPFは中〜大規模ネットワークで広く使われる「リンク状態型」のプロトコルです。そのルート計算の心臓部に組み込まれているのがダイクストラ法です。
・OSPFに参加しているルーターたちは、お互いに「自分の周りの回線速度(コスト)」の情報を交換し合い、ネットワーク全体の完璧な地図を共有します。
・地図が完成すると、各ルーターは自分がスタート地点となった『木の根』になり、ダイクストラ法(直前の問題で学んだ「最適性の原理」を応用した、確定ノードを広げていくアルゴリズム)を実行します。
・回線の太さ(帯域幅)をベースにした「コスト(距離)」を足し算していき、目的地へ最も安く(速く)辿り着けるルートを自動計算して、自身のルーティングテーブルに登録します。 ← ココが問題の正解!
★ ① ベルマンフォード法:OSPFではなく、もう1つの代表的なプロトコル「RIP(距離ベクトル型)」などのベースとなった最短経路アルゴリズムです。隣のルーターの情報だけを頼りにステップ数(ホップ数)をバケツリレー式に計算します。
★ ③ プリム法:グラフ全体において、すべての点を結びつつ、線の合計コストを最小にする「最小全域木(最小スパニングツリー)」を求めるアルゴリズムです(ネットワークのループを防ぐSTPなどに近い概念です)。
★ ④ 二分探索法:ソート(整列)済みのデータの中から、目的の値を中央の値と比べながら半分ずつ絞り込んで探す、基礎的なデータ検索アルゴリズムです。
1. 理解のコツ: 「カーナビのルート案内」をイメージしてください。
・「とにかく交差点を通過する回数が一番少ないルート(ホップ数重視)」を選ぶのがRIP(ベルマンフォード法)です。
・対して、「渋滞のなさや制限速度を考慮した『到着時間(コスト)』を地図データから割り出し、トータルで一番早く着くルート」を真面目に計算する高性能なナビがOSPF(ダイクストラ法)です。前問の『途中区間も最適でなければならない』という最適性の原理を使って無駄なく計算しています。
2. 試験対策の視点: 「OSPFプロトコル」「ネットワーク全体を把握」「最適経路(最短経路)を求めるアルゴリズム」という組み合わせが出たら「ダイクストラ法」が一択です。基本情報、応用情報、ネットワークスペシャリスト試験の午前において、ネットワーク分野の「OSPFの仕組み」としても、テクノロジー分野の「グラフアルゴリズム」としても非常によく狙われる、文系理系問わず超必須のクロスオーバー知識です。
4. まとめ
「ネットワーク全体のトポロジー地図を基に、目的地までの累積コストが最小となるルートを数学的に一本道として導き出す、OSPFの頭脳に採用された最短経路アルゴリズム」。これがダイクストラ法です。このアルゴリズムが各ルーターの中で独立して超高速に実行されているおかげで、インターネットの一部回線が切断されても、自動で最適な迂回路(抜け道)が一瞬で再計算される頑強なネットワークが維持されています。