はじめに
ルーティングプロトコルであるOSPFと、最短経路を求めるアルゴリズムであるダイクストラ法との関係について備忘録を残しておきます。
そもそもOSPFとは
OSPFはOpen Shortest Path Firstの略で、自立システム（Autonomous System）と呼ばれる地域ネットワークやプロバイダ内部のどのホストなのかを認識するIGP（Interior Gateway Protocol）で利用されるプロトコルのこと。リンク状態型（Link-State）の経路制御アルゴリズムを利用している。
代表的な経路制御アルゴリズムは以下の2つである。
| 距離ベクトル型 | リンク状態型 | |
|---|---|---|
| 概要 | 距離と方向によって目的のネットワークやホストの位置を決定する方法 | ルーターがネットワーク全体の接続状態を確認して経路制御表を作成する方法 |
| 詳細 | ルーター間でネットワークの向きと距離に関する情報が交換され、この向きと距離の情報から経路制御表（ルーティングテーブル）を作成する。通過するルーターの数が距離（メトリック）の値として使われる。処理が比較的簡単である反面、向きと距離の情報しかないため、ネットワークの構造が複雑になると、経路制御情報が安定するまでに時間がかかる、経路にループが生じやすくなる、といった問題がある。 | ネットワークの構造はどのルーターにとっても同じであるため、全てのルーターが同じ情報をもつことになる。このため、各ルーターが経路制御情報を他のルーターと同期させれば経路制御を安定させることができ、ネットワークが複雑になっても各ルーターは正しい経路制御情報を持つことができ、安定した経路制御を行うことができる。その反面、 ネットワークトポロジーから経路制御表を求める計算には高いCPU能力と多くのメモリ資源が必要になる。このため、OSPFではネットワークをエリアに分割できるようになっており、経路制御情報を減らせるような工夫がされている。 |
| 主なプロトコル | RIP, EGP | IS-IS, OSPF
|
距離ベクトル型のRIPでは、通過するルーターの数が最も少ない方向を経路に設定するが、リンク状態型のOSPFでは、各リンクに重み（コスト）を付けることができ、この重みの合計値が最も少ない方向を経路に設定する。
そもそもダイクストラ法とは
ダイクストラ法は構造化プログラミングを提唱したダイクストラという偉い人が考えた、グラフにおける2点間の最短経路を求めるアルゴリズムのこと。
似たようなアルゴリズムにベルマン・フォード法があり、これは負の重みが許容される場合の2点間の最短距離を求めるアルゴリズムであり、グラフの辺の重みが全て非負である場合には、より高速なダイクストラ法が利用される。
Pythonでこのアルゴリズムを実装すると以下のようになる。
dijkstra.py
import heapq
# 辺情報を表す構造体
class edge:
def __init__(self, end, leng):
self.end = end # 辺の終点
self.leng = leng # 辺の重み
INF = 10**9 # 初期化で使う十分大きな数
# 入力を受け取る
N, M = map(int, input().split())
G = [[] for _ in range(N)] # G[i]：頂点 i を始点とする辺情報を格納する
for i in range(M):
u, v, w = map(int, input().split())
G[u].append(edge(v, w))
dist = [INF for _ in range(N)] # dist[i]：頂点 0 から頂点 i への暫定的な経路長
dist[0] = 0
done = [False for _ in range(N)] # done[i]：頂点 i の最短距離が確定しているか
hq = [] # (仮の最短距離、頂点番号) を管理するヒープ
heapq.heapify(hq)
# ヒープに最初の時点における情報を入れておく
for v in range(N):
heapq.heappush(hq, (dist[v], v))
while len(hq) > 0:
# ヒープの先頭要素を取り出す (v は頂点番号、d は 0 → v の仮の最短距離)
[d, v] = heapq.heappop(hq)
# 頂点 v の最短距離がすでに確定しているなら、何もしない
if done[v]: continue
# 頂点 v を始点とする辺 e について、更新を行う
for e in G[v]:
if dist[e.end] > dist[v] + e.leng:
# 距離の更新がある場合には、ヒープに更新後の情報を入れる
dist[e.end] = dist[v] + e.leng
heapq.heappush(hq, (dist[e.end], e.end))
# 頂点 v の最短距離を確定させる
done[v] = True
# 答えを出力する
for i in range(N):
print(dist[i])
OSPFとダイクストラ法との関係性
- ネットワークLSA（Network Link State Advertisement, ネットワークにどのルーターが接続されているかを表す、ネットワークを中心に作成した情報）やルーターLSA（Router Link State Advertisement, ルーターにどのネットワークが接続されているかを表す、ルーターを中心に作成した情報）を
OSPFによってルーター間で交換し、各ルーターは、ネットワークの構造を表すリンク状態データベース（Link State Database）を作成する。 - ルーターは自分のリンク状態DBを完成させると、ネットワーク内の各ルーターまでの経路をすべて抽出し、経由するリンクの総コストを計算する。そして最も総コストの小さな経路を、そのルーターへの最短経路であると判断し、これを繰り返して最短パスツリーを構築する。これが
ダイクストラ法である。
参考文献
以上、ルーティングプロトコルのOSPFとアルゴリズムのダイクストラ法との関係性に関する備忘録でした。