新 米 エ ン ジ ニ ア の た め の

初歩 のはじめに今まで内緒にしていたのだが、実は私はよく道に迷う。どこか初めての場所に行く
ときには一応地図は見るのだが、道順までは調べない。最寄りの駅を地図で見て、そこからの相対的な位置関係だけを確認してインターネット技術出かけてしまうのだ。地図をコピーして持《第7回 OSPFの話》と頭の中で繰り返し唱えている。まるで子っては出かけるのだが、目的地の最寄り駅に着くまでは二度と見ようとはしない。電車の中では、ただひたすら「XX 駅の北口」
供のお使いのようである。だいたいが記憶力が弱いので、完璧な道順を最初に調べた
ところで、目的地に着くまで憶えていられる自信がない。したがって、とりあえずの中間地点である目的地の最寄り駅に着くまでは、その先のことは考えないのである。
最寄り駅に着き無事に目的の出口から出浅羽 登志也

られると、そこでやれやれと地図を広げて、

asaba@iij.ad.jp
株式会社インターネットイニシアティブ

次の目標点を探す。駅前から3 つ目の、三和銀行がある角を左に曲がればよいと分かれば、もうそこからは三和銀行しか頭にな

今回は、これまで解説してきたルーティングの話に関連して、最適経路を発見するためのアルゴリズムをステップを追って見ていきます。また、これを実際のネットワーク上で実現するためのプロトコルである
OSPF の概略を紹介します。

い。銀行の角を左に曲がったところでまた地図を見る。4 つ目の信号を渡ったところのXX ビルの5 階が目的地であれば、ひとまずXX ビルの5 階というのは忘れて、ひたすら信号の数を数えながら歩く。なんとか信号を4 つまで数えたところで、再びビルの名前と階を確認する。ここでそのビルが目の前にあれば一安心である。
この方法にはどこにも落ち度はないように見える。だが時として思いもかけぬところに行ってしまうのである。決して方向音痴ではないはずなのだが（まさにこういう

158 INTERNET MAGAZINE 1995/9

インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

をおそらく賢明なる読者諸兄は日頃から実のを方向音痴というのだろうか？）。一度、本当は、最初からちゃんと地図で最終的やっと目的地に着いて、さてXX ビルはどこな目的地までのいくつかある道順の中からかいなと見渡してみると、あたりには民家所要時間やさらに運賃まで調べたうえでどしかなかったことがある。確かに番地はこうやってそこまでたどり着くかを考えるのこのはずなのに、ビルがない。ビルはどこが人間のあるべき姿なのだろう。この場合、に行った！と、もう一度手帳に書いた目的目的地までの最適な経路というのは、一概ネットワークトポロジーが与えられたと地の住所をよく調べてみると「浅草橋○-には定まらないかもしれない。最も速い経きに、その上での最適経路を計算するため践されているに違いない。

SPF アルゴリズム

×」とある。おそるおそる手帳から目を離路が最も安い運賃であれば問題はないが、のアルゴリズムが存在する。これはSPFして目の前にある家の表札を見上げてみる

こっちから行けば速いけれどもちょっと高（Shortest Path First）アルゴリズムとかまと、そこには「浅 草○-×」と書いてあっくついて、こっちから行けば安いけどちょたは考案者の名前をとってDijkstra（ダイた。頭の中でがらがらと橋が崩れ落ちる音っと時間がかかる、というような場合もあクストラ）アルゴリズムとか呼ばれている。

がした。もちろんこれは方向音痴以前の問る。このような場合もすべて調べ上げて、

図 1 のようなトポロジーのグラフを考え題ではある。

状況に応じて最適な経路を選ぶということる。図では、ノードの中の文字がノードの名前、リンクに付けられた数字が、各ノードからそのリンクを経由してリンクの反対側にあるノードに至るためのコストを表している。たとえば、ノードA からノードB にA

1

3行くためのコストは5、ノードB からノードCA に行くためのコストは3 である。

7

ここで、ノードA から他のすべてのノー5ドに至るための経路のうち、コストが最小となるものを計算するにはどうしたらよいだろうか？

3B325

D

頭が腸捻転を起こしそうになるかもしれないが、ここはぐっと我慢しよう。以下の6ような手順で計算していけばよい。

109F

8E34

図1 サンプルグラフ

インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

INTERNET MAGAZINE 1995/9159

ステップ 1ステップ 2ステップ 3

まず出発点のノードA から隣接するB、C

ステップ1 で、図中の最小経路はA → C

ステップ2 で、図中の最小経路はA → Bの各ノードに行くためのコストを表すグラであったので、C からまだ最小経路が分かであったので、B からまだ最小経路が分かフを図2 のように作る。図2 より、A からBっていないすべてのノードに対するリンクをっていないすべてのノードに対するリンクをに行くためのコストは5 であり、A からC に図に加える。C からはA とD に行くリンク図に加える。B からはA とD に行くリンク行くためのコストは1 であることが分かる。

があるが、A は既に最小経路が分かっていがあるが、A はすでに最小経路が分かって図中の全経路のうち、コストが最小のものるので除外し、図 3 のようなグラフができいるので除外し、図 4 のようなグラフがではA からC に行く経路なので、これを太いる。図3 では、A →B とA →C →D の2 つのきる。図 4 では、A → B → D とA → C → D

矢印で表し、また、この時点でC に至る最経路が存在するが、A →B のコストが5、Aの2 つの経路が存在するが、A → B → D の小経路がA → C であることが分かるので、→C →D のコストが8 となる。ここでA →Bコストが7、A →C →D のコストが8 となる。

ノードC に＊の印を付ける。またノードAが最小の経路なので、A →B の矢印を太く

ここでA → B → D が最小の経路なので、BからA はコスト0 と考えられるので、これもし、またこの時点でB への最小経路はA →→D の矢印を太くし、またこの時点でD へすでに最小経路は分かっているということBであることが分かるのでB に＊の印を付けの最小経路はA →B →D であることが分かで、＊の印を付ける。

る。

るのでD に＊の印を付ける。また、経路 A→C →D は同じD への経路でより高いコストを持つので、C → D の矢印を消す。C かA*5A*5B1B*

1

C*
7C*

D
図2 ステップ1160 INTERNET MAGAZINE 1995/9

図3 ステップ2

インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

新米エンジニアのための初 歩 の イ ン タ ー ネ ッ ト 技 術

A*A*
5511B*

B*

C*

272

D*
10D*

C*

6DE

図4 ステップ3F*

図5 ステップ4ら先に進む矢印が全部消えてしまったので、うなグラフができる。図5 では、A →B →D→ D → F であったので、F からまだ最小経

これ以降はC から先に進むリンクに関して→ E とA → B → D → F の2 つの経路が存在路が分かっていないすべてのノードに対すは調べなくてよい。

するが、A → B → D → E のコストが17、Aるリンクを図に加える。F からはD、E に行→B →D →F のコストが13 となる。ここでくリンクがあるが、D はすでに最小経路がA → B → D → F が最小の経路なので、D →分かっているので除外し、図 6 のようなグF の矢印を太くし、またこの時点でF へのラフができる。図 6 では、A → B → D → F

最小経路はA → B → D → F であることが分→ E とA → B → D → E の2 つの経路が存在かるのでF に＊の印を付ける。

するが、A →B →D →F →E のコストが16、ステップ 4ステップ3 で、図中の最小経路はA → B→D であったので、D からまだ最小経路がA → B → D → E のコストが17 となる。ここ分かっていないすべてのノードに対するリンクを図に加える。D からはB、C、E、F

ステップ 5

経路が分かっているので除外し、図 5 のよでA →B →D →F →E が最小の経路なので、F → E の矢印を太くし、またこの時点でEに行くリンクがあるが、B、C はすでに最小ステップ4 で、図中の最小経路はA → Bへの最小経路はA →B →D →F →E である

インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

INTERNET MAGAZINE 1995/9161

ことが分かるので、E に＊の印を付ける。
また経路 A → B → D → E は同じE への経路でより高いコストを持つので、D → E の矢印を消す。
以上でA からすべてのノードに向かう最A*

小経路が求められたので、アルゴリズムは終了し、図 7 のような、A からの最小コストグラフができあがる。

51

このように、常にその時点での最小経路（Shortest Path）から順に調べられていくので、このアルゴリズムはShortest PathB*C*First と呼ばれる。

OSPF
2OSPF（Open Shortest Path First）は、このSPF アルゴリズムを用いて経路制御を行 うためのプロトコルとして、 I E T F（Internet Engineering Task Force）によD*って規定された。最初のO（Open）は、この規格がすべての人に対して公開される10ものであることを表すために付けられてい6る。
OSPF では、非常に大雑把に言って以下の2 つのプロセスをとる。

EF*

1. OSPF に参加するすべてのルーターが、自分の持つすべてのリンクのコスト、リンクの表すネットワーク、隣接ルーターなどの情報を交換する。これにより、

3

図1 のような全体のトポロジー情報をすべてのルーターが持つことになる
2. 各ルーターは得られたトポロジー情報かE*

らSPF アルゴリズム用いてネットワーク全体に対する最適経路を計算する
また、OSPF の特徴としては以下のもの

図6 ステップ5

162 INTERNET MAGAZINE 1995/9が挙げられる。

インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

新米エンジニアのための初 歩 の イ ン タ ー ネ ッ ト 技 術ことを意味している。たとえば、隣接するOSPF は、ルーターが持つリンクの状態・複数のメトリックを用いることができる

ノード間のリンクの利用料金を1 つのメトの情報を用いることからLink State Routing

・特定のデスティネーションに対して複数リックとして表し、さらにディレイをもう1Protocol とも呼ばれる。これに対して、前・素早く収束し、ループが起こらないつのメトリックとして用いて、2 種類の最適に見たRIP のようなプロトコルはDistance・エリアの概念を用いることにより、大経路表を持つことができる。IP のヘッダー

Vector Routing Protocol と呼ばれる。

規模なネットワークでも用いることがでではこのTOS を表現することができるので、きる速く届けたいデータグラムに対してはディ

ここで注意すべき点は、すべてのルータレイが最小になる経路表を用い、料金を最ーが同じトポロジーの情報を持っていなけ

小にしたいデータグラムに対しては経路の難しいことを言っているようだが、結局ればいけないという点である。これはネッ

料金が最小になるような経路表を用いればはすべてのルーターが同じ地図を持って、トワーク上のどこかのリンクが落ちたり、ルよいわけである。ただし、1 つのデータグラ

その地図を見ながら経路制御しましょうね、ーターが落ちたなどという情報が、すぐにムに対しては経路上のすべてのルーターでということである。最初に述べたように全体に伝わらなければならないということ一貫して同じ経路表を用いないとループが（私のようにずぼらではない）人間様が普通を意味している。

起こりうるので注意が必要である。にやっていることをルーティングで実現しの経路を用いることができる

おわりにまた、コストとして単一のメトリックでOSPF ではこれらを実現するために、さただけなのである（なんて、こんな私が偉はなく、複数のメトリックを用いることがまざまな手法を用いている。プロトコルのそうに言えるすじあいではないのだが……）。

できるということは、TOS（Type Of Ser-

詳細については誌面の都合上、次回に譲るvice）を用いたルーティングができるということにする。

1

A

次回はOSPF のプロトコルについてもうちょっと詳しく解説してみようと思う。

C

5

2

B

D
6

F
3

E
図7 最小コストグラフ

インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

INTERNET MAGAZINE 1995/9163

［インターネットマガジン バックナンバーアーカイブ］ ご利用上の注意
この PDF ファイルは、株式会社インプレス R&D（株式会社インプレスから分割）が 1994 年～2006 年まで発行した月刊誌『インターネットマガジン』の誌面を PDF 化し、「インターネットマガジン バックナンバーアーカイブ」として以下のウェブサイト「All-in-One INTERNET magazine 2.0」で公開しているものです。

http://i.impressRD.jp/bn
このファイルをご利用いただくにあたり、下記の注意事項を必ずお読みください。
z 記載されている内容（技術解説、URL、団体・企業名、商品名、価格、プレゼント募集、アンケートなど）は発行当時のものです。
z 収録されている内容は著作権法上の保護を受けています。著作権はそれぞれの記事の著作者（執筆者、写真の撮影者、イラストの作成者、編集部など）が保持しています。
z 著作者から許諾が得られなかった著作物は収録されていない場合があります。
z このファイルやその内容を改変したり、商用を目的として再利用することはできません。あくまで個人や企業の非商用利用での閲覧、複製、送信に限られます。
z 収録されている内容を何らかの媒体に引用としてご利用する際は、出典として媒体名および月号、該当ページ番号、発行元（株式会社インプレス R&D）、コピーライトなどの情報をご明記ください。
z オリジナルの雑誌の発行時点では、株式会社インプレス R&D（当時は株式会社インプレス）と著作権者は内容が正確なものであるように最大限に努めましたが、すべての情報が完全に正確であることは保証できません。このファイルの内容に起因する直接的および間接的な損害に対して、一切の責任を負いません。お客様個人の責任においてご利用ください。

このファイルに関するお問い合わせ先
All-in-One INTERNET magazine 編集部
im-info@impress.co.jp
Copyright © 1994-2007 Impress R&D, an Impress Group company. All rights reserved.