Network Working Group J. Moy Request for Comments: 1583 Proteon, Inc. Obsoletes: 1247 March 1994 Category: Standards Track OSPF バージョン 2 このメモのステータス この文書はインターネットコミュニティにおける Internet standards track の プロトコルを記述し、改善のための議論、提案をリクエストするものである。 このプロトコルの状態と標準化の状況については、`Internet Official Protocol Standards' (STD 1) を参照されたい。この文書の配付は無制限である。 梗概 この文書は OSPF プロトコルのバージョン 2 について記している。OSPF は link-state 型経路制御プロトコルであるであり、自律システム内部で動作させる ように設計されている。各 OSPF ルータは同一の自律システムのトポロジを記述 するようなデータベースを維持する。このデータベースをもとに、Shortest Path Tree を構築することによって経路表が計算される。 OSPF はトポロジが変化した際に、最小の経路制御プロトコルトラフィックで経路を 再計算する。OSPF は等価なコストの複数のパスをサポートする。また、各 IP Type of Service について、それぞれ独立した経路を計算することができる。 エリアを用いた経路制御能力を提供するので、付加的なレベルの経路制御保護や 経路制御トラフィックの削減をすることができる。さらに、全ての OSPF 経路制御 プロトコルの情報交換は認証が行なわれる。 OSPF バージョン 2 は、RFC1247 で初めて文書化された。RFC1247 と本文書の違い は付録 E で解説している。違いはバグフィックス、わかりにくい部分の明確化 (clarification)などから成り、事実上バックワードコンパチブルである。 RFC1247の実装と本文書の実装は相互に通信できる。 コメントは ospf@gated.cornell.edu に送ってほしい。 1. はじめに この文書は `Open Shortest Path First (OSPF)' TCP/IP インターネット経路制御 プロトコルの仕様書である。OSPF は Interior Gateway Protocol(IGP) に分類 される。つまり、単一の自律システム(AS)内にあるルータ間で経路制御情報を配付 するためのものである。OSPFプロトコルは link-state もしくは SPF 技術に 基づいている。これは従来 TCP/IP インターネット経路制御プロトコルに用いられて きた Bellman-Ford 型の手法からの発展である。 OSPF プロトコルは Internet Engineering Task Force の OSPF ワーキング グループによって開発された。OSPF は IP サブネッティングの明示的なサポート、 TOS に基づく経路制御、外部からもたらされた経路情報へのタグ付けなど、 TCP/IP インターネット環境のために特別に設計されたものである。また、経路情報 更新時における認証の仕組みを提供し、経路情報更新情報の伝達には IP マルチ キャストを利用する。更にトポロジ変化への機敏な対応と、経路制御プロトコルの トラフィック量を少なくするために特に労力が払われている。 Fred Baker、Jeffrey Burgan、Rob Coltun、Dino Farinacci、Vince Fuller、 Phanindra Jujjavarapu、Milo Medin、Kannan Varadhan、その他このプロジェクトに アイデアとサポートを提供してくれた OSPF ワーキンググループに感謝の意を 表したい。 1.1 プロトコル概要 OSPF は IP パケットをパケットヘッダに記された送信先 IP アドレスと IP Type of Service に基づいて経路制御する。IP パケットは `そのまま (as is)' の状態 で経路制御される。自律システムを通るために付加的なプロトコルヘッダを使って カプセル化されるわけではない。OSPF はルータインタフェースの障害のような 自律システム内のトポロジ変化を短時間で検出し、収束するための時間を経た後に 新たにループの無い経路を計算する。収束までの時間は短く、最小限の経路制御 トラフィックしか生じない。 link-state 型プロトコルでは、ルータは自律システムのトポロジが記述された データベースを維持する。各ルータが持つデータベースは同一のものである。 データベースを構成する要素は、個々のルータのローカルな状態である。例えば 使用可能なインタフェース、到達可能な neighbor 等が挙げられる。ルータは ローカル状態の情報を flood することによって自律システム内に配付する。 全ルータは同じアルゴリズムの元に並行して動作する。各ルータはトポロジ データベースを基に、自身を root とする shortest-path tree を構築する。 この shortest-path tree が自律システム内の送信先に応じた経路情報を提供する。 外部からもたらされた経路制御情報は、tree内のleafとして表現される。 OSPF は Type of Service(TOS) に応じて独立した経路を計算する。送信先までの コストが同じ経路が複数ある場合には、トラフィックはその経路全てに均等に配分 される。経路のコストは、整数のメトリックで表現される。 OSPF はネットワークの集合をグループ化することを許している。このグループは エリアと呼ばれる。エリアのトポロジは、自律システムの他の部分からは隠される。 情報を隠すことにより、経路制御情報を大幅に削減することができる。また、 エリア内の経路制御はエリアのトポロジのみによって決定されるので、不正な経路 制御情報からエリアを守ることにも役立つ。エリアとは IP サブネット化された ネットワークを一般化したものである。 OSPF は IP サブネットについて柔軟な環境を提供する。OSPF によって配布される 経路は、送信先とマスクの情報を持っている。同じ IP ネットワークアドレスに 属する 2 つの異なるサブネットは異なるサイズであってもよい (つまり異なる マスクを設定してもよい)。ふつう、これは variable length subnetting として 扱われる。パケットはベストマッチ(最も一致する部分が長いか最も特定可能な) 経路を選択する。ホストルートは all-1bit のマスク(0xffffffff)を持つサブネット と考えられる。 OSPF プロトコルでは、全ての情報交換について認証が行われる。これは自律システム 内の経路制御には信頼のおけるルータだけが使用されることを意味している。 認証には多様な機構を用いることができる。各エリアについてそれぞれ 1 つの認証 機構を設定することができるので、エリアによっては他エリアよりも厳密な認証機構 を設定することができる。 外部からもたらされる経路制御情報 (例えば Exterior Gateway Protocol(EGP)から 得られた経路) は透過的に自律システム内を通過する。外部からの経路制御情報は OSPF の link-state 情報とは別に保持される。外部経路には、その経路を広告する ルータによってタグを設定することができる。このタグによって、自律システムの 境界にあるルータ間で付加的な情報を交換することが可能となる。 1.2 用語の定義 このセクションでは OSPF プロトコルで特定の意味を持っている用語と、本文書を 通じて使用される用語について定義する。Internet Protocol について明るくない 読者は、IP の入門として [RS-85-153] を参照してほしい。 ルータ 第三層で IP パケットを交換するもの。以前は IP に関する多くの文献で `gateway' と呼ばれていた。 自律システム (Autonomous System) 共通の経路制御プロトコルを用いて経路情報を交換しているルータのグループ。 `AS' と略記される。 Interior Gateway Protocol AS 内のルータが経路情報交換のために用いる経路制御プロトコル。 `IGP' と略記される。AS はそれぞれ単一の IGP を使用する。異なる AS では 異なる IGP が動作しているかもしれない。 ルータ ID OSPF プロトコルを走らせている各ルータに割り当てられる 32bit の番号。 この番号によって AS 内のルータを一意に識別することができる。 ネットワーク この文書では、IP のネットワーク、サブネット、スーパーネット全てを含む ものを指す。1 つの物理的なネットワークに複数の IP ネットワーク番号、 IP サブネット番号を割り当てることも可能である。その場合、1 つの物理的な ネットワークはそれぞれ独立した 2 つのネットワークであると見なされる。 ただし Point-to-Point の物理的なネットワークは例外で、ネットワーク番号が 幾つ割り当てられていても 1つのネットワークとして扱われる。 ネットワークマスク 1 つの IP ネットワーク、サブネット、スーパーネットに属する IP アドレスの 範囲を示す 32bit の数で、16 進数で表現される。例えば、クラス C のネット ワークマスクは 0xffffff00 で表される。他の文献では、255.255.255.0 の ような表記法も見られる。 マルチアクセスネットワーク 3 つ以上のルータとアタッチすることが可能な物理的ネットワーク。このネット ワーク上にあるルータは全て自分以外の相手と直接通信できる。すなわち、 マルチドロップネットワークは除外される。 インタフェース ルータと、ルータが接続しているネットワークとの接点。インタフェースは、 下位レベルのプロトコルやル経路制御プロトコルから得られた、インタフェース の状態の情報を持っている。ネットワークへのインタフェースの場合、 IP アドレスとネットワークマスクを持つ。(unnumbered な point-to-point の ネットワークである場合を除く)。インタフェースは、リンクとして扱われる こともある。 neighboring ルータ 共通のネットワークにインタフェースを持っている 2 つのルータ。マルチ アクセスネットワークでは、neighbor は OSPF の Hello プロトコルによって 動的に検出される。 ajacency 経路情報を交換するために選択される neighboring ルータの関係。全ての neighboring ルータの組み合わせが ajacent になるわけではない。 link-state 広告 ルータ、もしくはネットワークのローカルな状態を記述したもの。ルータの インタフェースの状態や、ajacency の情報が含まれる。各 link-state 広告は 経路制御ドメインに flood される。全てのルータ、ネットワークより収集 された link-state 広告は、OSPF プロトコルのトポロジカルなデータベースを 形成する。 Hello プロトコル OSPF プロトコルの一部で、neighbor との関係を確立したり、維持したりする ために用いられる。マルチアクセスネットワークでは、Hello プロトコルを 使って動的に neighboring ルータを発見することができる。 Designated ルータ 少なくとも 2 つのルータとアタッチしているマルチアクセスネットワークは Designated ルータを持つ。Designatedルータはマルチアクセスネットワークの link-state 広告を生成し、またプロトコルの動作において特別な責任を持つ。 Designated ルータの概念により、マルチアクセスネットワークで必要とされる ajacency の数を減らすことができる。結果的に経路制御プロトコルの トラフィック量とトポロジカルデータベースのサイズを小さくすることができる。 下位レベルプロトコル インターネットプロトコルや OSPF プロトコルにサービスを提供する、礎に なっているネットワークアクセスプロトコル。X.25 PDN に対する X.25 パケット やフレームレベル、イーサネットのイーサネット・データリンクレイヤが これに該当する。 1.3 link-state 型経路制御技術の歴史概要 OSPF は link-state 型経路制御プロトコルである。このプロトコルは、他の 文献では SPF-based プロトコルあるいは distributed-database プロトコルと 呼ばれている。このセクションでは、OSPF プロトコルに影響を与えた link-state 技術の開発について簡潔に記述する。 最初の link-state 型経路制御プロトコルは、ARPANET パケット交換ネットワークで 使用するために開発された。このプロトコルは、[McQuillan] 内に記述されている。 これが他の全ての link-state 型経路制御プロトコルの出発点となった。ARPANET の 均質な環境、すなわち同期シリアル線によって単一のベンダーのパケットスイッチが 接続されている環境のため、オリジナルプロトコルの設計と実装は簡潔なものに なっている。 このプロトコルの修正は [Perlman] で提案された。修正は経路制御プロトコルの 耐障害性を高めるためのもので、様々なことが行なわれた。特筆すべきは link-state 広告にチェックサムを加えたことで、これによってデータベースの改竄を検知する ことができるようになった。また、この論文は link-state 型プロトコルの経路制御 トラフィックのオーバヘッドを減少させる手段も含んでいる。これは link-state 広告生成の間隔を、その重要度によって広げていく仕組みを導入することによって 達成されていた。 link-state 型アルゴリズムは、ISO IS-IS 経路制御プロトコルとして用いることも 提案されている。このプロトコルは、[DEC] によって記述された。このプロトコル にはブロードキャストネットワーク上のオペレーション時にデータトラフィックと 経路制御トラフィックを減らす手法が含まれている。これは各ブロードキャスト ネットワークについて Designated ルータを選択し、そのルータがネットワークに 対する link-state 広告を生成することによって達成されている。 IETF の OSPF 分科会は、OSPF プロトコルの開発時にこれらの作業成果を拡張した。 Designated ルータの概念は大幅に拡張され、必要とされる経路制御トラフィック量を 更に削減した。マルチキャスト機能は経路制御のバンド幅を更に減らすために利用 される。エリア経路制御という機構は情報を隠し、守り、減少するために開発された。 最終的に、このアルゴリズムは TCP/IP インターネットの効果的なオペレーションの ために修正された。 1.4 本文書の構成 この仕様書のはじめの 3 セクションはプロトコルの機能、関数の一般的な概略を 述べる。セクション 4-16 ではプロトコルのメカニズムを詳細に説明する。 パケットのフォーマット、プロトコルで使用する定数や設定項目は付録で指定 される。 文中に出てくる `HelloInterval' のようなラベルはプロトコルの定数である。 これらの値は設定可能な場合もあり、そうでない場合もある。構造的な定数は 付録 B で説明される。設定可能な定数は付録 C で説明される。 プロトコルの詳細な仕様はデータ構造体の見地から説明される。これはより正確な 説明を行なうためである。プロトコルの実装では、記述された機能をサポートする ことが必要となるが、必ずしもこのメモ内に出てくる正確なデータ構造体を用いなく ともよい。 2. トポロジカルデータベース AS のトポロジカルデータベースより有向グラフが記述される。グラフの 頂点はルータとネットワークで構成される。2 つのルータが物理的な point-to-point ネットワークを介してアタッチされている場合、グラフの辺はその 2 つのルータを つなぐ。ルータとネットワークが辺でつながっている場合、ルータがネットワークに インタフェースを持つことを意味する。 頂点は機能に応じてさらに細かく分類される。このうちの幾つかのタイプだけが transit なデータトラフィック、すなわちローカルに生成されたものでなく、 送信先もローカルな場所でないトラフィックを配送する。transitトラフィックを 配送可能な頂点は、入力の向きを持つ辺と出力の向きを持つ辺を共に持つことに よって表現される。 頂点のタイプ 頂点の名称 transit トラフィックの配送 -------------------------------------------------------------- 1 ルータ 可 2 ネットワーク 可 3 stub ネットワーク 可 表1: OSPF における頂点の種類 OSPF は以下の種類の物理的なネットワークをサポートする。 point-to-point ネットワーク 一対のルータをつなぐネットワーク。例えば 56Kb のシリアル線は point-to-point ネットワークである。 ブロードキャストネットワーク 3 つ以上のルータアタッチをサポートしているネットワークで、アタッチ している全ルータに物理的なメッセージを伝える (ブロードキャストする) 能力を持つもの。このネットワーク上にある neighboring ルータは、OSPF の Hello プロトコルを用いることによって動的に検出される。Hello プロトコル 自身、ブロードキャスト能力を利用している。また、利用可能なら更に マルチキャスト能力を利用する。イーサネットはブロードキャスト ネットワークの一例である。 ノン・ブロードキャストネットワーク 3 つ以上のルータアタッチをサポートするが、ブロードキャスト能力を持たない ネットワーク。このネットワーク上でも neighboring ルータは OSPF の Hello プロトコルで検出される。しかし、ブロードキャスト能力がないため、Hello プロトコルを正しく動作させるために、幾つかの設定情報が必要となる。 このネットワークでは、本来マルチキャストされるべきパケットは、 neighboring ルータに 1 つずつ、順番に配送されなければならない。X.25 公衆 データネットワーク (PDN) はノン・ブロードキャストネットワークの一例 である。 グラフにおいて、ネットワークノードの neighborhood は、そのネットワークが マルチアクセスの能力を持っているかどうか (ブロードキャストであるかどうかは 問わない)、もしマルチアクセス能力がある場合はネットワークに接続されている ルータの数に依存する。図 1 に 3 つのケースを示す。四角形はルータを表し、 円および楕円はマルチアクセスネットワークを表す。ルータ名には RT、ネット ワーク名には N という文字が頭につけられる。ルータのインタフェース名には I という文字が頭に付けられる。ルータ間の線は point-to-point ネットワークを 表す。図の左側にはルータが接続されているネットワークを、右側にはグラフ化 した結果を載せている。 有向グラフでは、point-to-point ネットワークで接続されている 2 つのルータは それぞれ相手に向かう 2 つの辺のペアによって接続される形で表現される。 物理的な point-to-point ネットワークへのインタフェースは、必ずしも IP アドレスの割り当てを必要としない。そのようなネットワークは `unnumbered' と 呼ばれる。point-to-point ネットワークの表現法は、unnumbered ネットワークを 無理なくサポートできるように設計されている。インタフェースアドレスが存在 する場合、アドレスは stub な経路としてモデル化される。その場合、ルータが 互いにもう一方のルータのインタフェースアドレスへの stub なコネクションを 持つことに注意してほしい (図 1 参照)。 マルチアクセスネットワークに複数のルータがアタッチされる場合、有向グラフでは 全てのルータがネットワークを表現する頂点に双方向に接続されているものとして 表現される (図 1 参照)。マルチアクセスネットワークにアタッチされている ルータが 1 つだけである場合、ネットワークは stub コネクションとして表現 される。 **FROM** * |RT1|RT2| +---+Ia +---+ * ------------ |RT1|------|RT2| T RT1| | X | +---+ Ib+---+ O RT2| X | | * Ia| | X | * Ib| X | | 物理的な point-to-point ネットワーク **FROM** +---+ +---+ |RT3| |RT4| |RT3|RT4|RT5|RT6|N2 | +---+ +---+ * ------------------------ | N2 | * RT3| | | | | X | +----------------------+ T RT4| | | | | X | | | O RT5| | | | | X | +---+ +---+ * RT6| | | | | X | |RT5| |RT6| * N2| X | X | X | X | | +---+ +---+ マルチアクセスネットワーク **FROM** +---+ * |RT7| * |RT7| N3| +---+ T ------------ | O RT7| | | +----------------------+ * N3| X | | N3 * stub なマルチアクセスネットワーク 図 1: ネットワークマップを構成するもの ネットワークとルータは頂点で表現される。行 A と列 B の交点が X の場合、頂点 A と頂点 B は辺でつながれる。 グラフ内のネットワーク (stub もしくは transit) は、IP アドレスとネットワーク マスクを持つ。マスクはネットワーク上のノード数を表す。ルータに直接アタッチ されているホスト (ホストルートとして扱われる) は stub ネットワークとして 表現される。ホストルートのネットワークマスクは常に 0xffffffff であり、 ネットワーク上に 1 つだけノードが存在することを意味している。 図 2 は AS のサンプルマップを示したものである。H1 とラベル付けされた四角形は ルータ RT12 に SLIP 接続されているホストを表す。したがって、ルータ RT12 は ホストルートを広告する。ルータ間の線は物理的な point-to-point ネットワークを 意味する。ルータ RT6 と RT10 をつないでいる point-to-point ネットワークだけ がインタフェースに IP アドレスを割り当てられている。ルータ RT5 と RT7 は 他の AS と EGP コネクションを持つ。EGP 経由で学習された経路は両ルータ それぞれについて表示される。 コストは各ルータのインタフェースの出力側に関するものである。コストは システム管理者が設定できる。よりコストの小さいインタフェースほどデータ トラフィック配送のために使われやすい。コストは外部から得られた経路制御データ (例えば EGP から学習した経路) に関するものでもある。 図 2 のマップから形成される有向グラフを図 3 に示す。弧には対応するルータの 出力インタフェースに設定されたコストがラベル付けされる。コストがラベル付け されていない弧はコスト 0 であることを意味する。ネットワークからルータに 向かう弧は常にコスト 0 であることに注意されたい。これらの弧は重要である。 また、外部からもたらされる経路制御データは stub なものとしてグラフに表示 されることにも注意してほしい。 トポロジカルデータベース (もしくは先に有向グラフとして扱ったもの) は ルータが生成する link-state 広告を継ぎ合わせて作られる。transit タイプの 頂点の neighborhood は単一の独立した link-state 広告で表現される。図 4 は 2 種類の transit タイプの頂点すなわちルータとマルチアクセスネットワークに ついて、link-state の表現を図示したものである。ルータ RT12 は 2 つの ブロードキャストネットワークと 1 つの SLIP ラインへのインタフェースを持つ。 ネットワーク N6 は 3 つのルータがアタッチされたブロードキャストネットワーク である。ネットワーク N6 からアタッチされているルータまでのリンクのコストは 全て 0 である。ネットワーク N6 の link-state 広告は、実際にはアタッチされた ルータのうちの 1つ、Designatedルータとして選択されたルータによって生成される ことに注意してほしい。 + | 3+---+ N12 N14 N1|--|RT1|\ 1 \ N13 / | +---+ \ 8\ |8/8 + \ ____ \|/ / \ 1+---+8 8+---+6 * N3 *---|RT4|------|RT5|--------+ \____/ +---+ +---+ | + / | |7 | | 3+---+ / | | | N2|--|RT2|/1 |1 |6 | | +---+ +---+8 6+---+ | + |RT3|--------------|RT6| | +---+ +---+ | |2 Ia|7 | | | | +---------+ | | N4 | | | | | | N11 | | +---------+ | | | | | N12 |3 | |6 2/ +---+ | +---+/ |RT9| | |RT7|---N15 +---+ | +---+ 9 |1 + | |1 _|__ | Ib|5 __|_ / \ 1+----+2 | 3+----+1 / \ * N9 *------|RT11|----|---|RT10|---* N6 * \____/ +----+ | +----+ \____/ | | | |1 + |1 +--+ 10+----+ N8 +---+ |H1|-----|RT12| |RT8| +--+SLIP +----+ +---+ |2 |4 | | +---------+ +--------+ N10 N7 図 2: 自律システムの例 **FROM** |RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT| |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9| ----- --------------------------------------------- RT1| | | | | | | | | | | | |0 | | | | RT2| | | | | | | | | | | | |0 | | | | RT3| | | | | |6 | | | | | | |0 | | | | RT4| | | | |8 | | | | | | | |0 | | | | RT5| | | |8 | |6 |6 | | | | | | | | | | RT6| | |8 | |7 | | | | |5 | | | | | | | RT7| | | | |6 | | | | | | | | |0 | | | * RT8| | | | | | | | | | | | | |0 | | | * RT9| | | | | | | | | | | | | | | |0 | T RT10| | | | | |7 | | | | | | | |0 |0 | | O RT11| | | | | | | | | | | | | | |0 |0 | * RT12| | | | | | | | | | | | | | | |0 | * N1|3 | | | | | | | | | | | | | | | | N2| |3 | | | | | | | | | | | | | | | N3|1 |1 |1 |1 | | | | | | | | | | | | | N4| | |2 | | | | | | | | | | | | | | N6| | | | | | |1 |1 | |1 | | | | | | | N7| | | | | | | |4 | | | | | | | | | N8| | | | | | | | | |3 |2 | | | | | | N9| | | | | | | | |1 | |1 |1 | | | | | N10| | | | | | | | | | | |2 | | | | | N11| | | | | | | | |3 | | | | | | | | N12| | | | |8 | |2 | | | | | | | | | | N13| | | | |8 | | | | | | | | | | | | N14| | | | |8 | | | | | | | | | | | | N15| | | | | | |9 | | | | | | | | | | H1| | | | | | | | | | | |10| | | | | 図 3: 生成される有向グラフ ネットワークとルータは頂点で表現される。行 A と列 B の交点が X の場合、頂点 A と頂点 B はコスト X の辺でつながれる。 **FROM** **FROM** |RT12|N9|N10|H1| |RT9|RT11|RT12|N9| * -------------------- * ---------------------- * RT12| | | | | * RT9| | | |0 | T N9|1 | | | | T RT11| | | |0 | O N10|2 | | | | O RT12| | | |0 | * H1|10 | | | | * N9| | | | | * * RT12 のルータリンク広告 N9 のネットワークリンク広告 図 4: 個々の link-state の構成要素 ネットワークとルータは頂点で表現される。行 A と列 B の交点が X の場合、頂点 A と頂点 B はコスト X の辺でつながれる。 2.1 shortest-path tree OSPF のエリアが設定されていない場合、 AS 内の全ルータは、グラフ化された AS から導き出される同一のトポロジカルデータベースを持つ。ルータはこの グラフをもとに、自身を root とした最短のパスを樹状に算出することによって 経路表を生成する。明らかに shortest-path tree は計算を行なうルータに 依存する。ルータ RT6 に関する shortest-path tree の例を図 5 に示す。 tree は全てのネットワーク、ホストへの経路を与える。しかし、データ転送処理時 には目的地に向けたネクストホップしか用いられない。また、任意のルータへの 最善の経路が計算されていることにも注意してほしい。外部から得られたデータを 処理するためには、外部経路を広告している全ルータまでの距離とネクストホップ を考慮する必要がある。結果として得られるルータ RT6 の経路表を表 2 に示す。 numbered なシリアル線 (この場合、ルータ RT6 と RT10 の間のシリアル線) の 終点に向かう、独立した経路が存在することに注意してほしい。 他の AS に属するネットワークへの経路 (例えばN12のような)は、図 5 の shortest-path tree では点線で示されている。このような外部から得られた 経路制御情報の扱いは次のセクションで述べる。 RT6(origin) RT5 o------------o-----------o Ib /|\ 6 |\ 7 8/8|8\ | \ / | \ | \ o | o | \7 N12 o N14 | \ N13 2 | \ N4 o-----o RT3 \ / \ 5 1/ RT10 o-------o Ia / |\ RT4 o-----o N3 3| \1 /| | \ N6 RT7 / | N8 o o---------o / | | | /| RT2 o o RT1 | | 2/ |9 / | | |RT8 / | /3 |3 RT11 o o o o / | | | N12 N15 N2 o o N1 1| |4 | | N9 o o N7 /| / | N11 RT9 / |RT12 o--------o-------o o--------o H1 3 | 10 |2 | o N10 図 5: ルータ RT6 に関する SPF tree コストが記されていない辺はコスト 0 である (これらはネットワーク からルータへのリンクである)。ネットワーク N12-N15 への経路は 外部から得られた情報で、セクション 2.2 で扱う。 配送先 ネクストホップ 距離 ---------------------------------- N1 RT3 10 N2 RT3 10 N3 RT3 7 N4 RT3 8 Ib * 7 Ia RT10 12 N6 RT10 8 N7 RT10 12 N8 RT10 10 N9 RT10 11 N10 RT10 13 N11 RT10 14 H1 RT10 21 ---------------------------------- RT5 RT5 6 RT7 RT10 8 表 2: ルータ RT6 の経路表の一部でローカルな配送先をリストしたもの 2.2 外部経路情報の扱い tree が形成された後、外部の経路制御情報が検査される。外部の経路制御情報は EGP のような他の経路制御プロトコルや、静的な設定 (static route) によって 生成される。デフォルトルートが AS 外の経路制御情報に含まれていても 構わない。 外部の経路制御情報は、AS 内を変更されることなく flood される。図 2 を用いた 例では、AS 内の全ルータはルータ RT7 が 2 つの外部経路を持ち、それぞれ メトリック 2、9 であることを知っている。 OSPF は 2 種類の外部メトリックをサポートする。Type 1 外部メトリックは、 link-state メトリックと等価なものである。Type 2 外部メトリックは、自律 システム内の全てのパスのコストよりも大きなものである。Type 2 外部メトリック の使用はパケットを経路制御する際に用いられるコストの大半が AS 間の ものであるという前提のもとに、外部コストを内部の link-state メトリックに 変換する必要性を無くすものである。 Type 1 外部メトリック処理の例として、図 2 においてルータ RT7 と RT5 が Type 1 外部メトリックを広告していると仮定する。その場合、ルータ RT6 から 各外部経路までの距離は、外部経路のコストと、ルータ RT6 から外部経路を 広告しているルータまでの距離の和を計算することによって得られる。全ての 外部配送先について、最短の経路を広告しているルータが検出されるので、 その経路を広告しているルータに向かうネクストホップが目的地までのネクスト ホップとなる。 ルータ RT5、RT7 はどちらもネットワーク N12 への外部経路を広告している。 RT7 は RT6 に対して N12 への距離を 10(8+2) と広告する。これはルータ RT5 が 広告している N12 への距離 14(6+8) よりも良いので、RT7が選択される。表 3 は 外部経路が検査された後に経路表に追加されるエントリを示したものである。 配送先 ネクストホップ 距離 ---------------------------------- N12 RT10 10 N13 RT5 14 N14 RT5 14 N15 RT10 17 表 3: RT6 の経路表の一部で外部経路をリストしたもの Type 2 外部メトリックの処理はより簡単である。 AS 内の AS バウンダリ ルータまでの距離は考慮されないまま、最小の外部メトリックを広告している AS バウンダリルータが選択される。例として、図 2 においてルータ RT5、RT7 が Type 2 外部メトリックを広告していると仮定する。その場合、ネットワーク N12 に 向かう全トラフィックはルータ RT7 に配送される。なぜなら、コストが 2 < 8 で RT7 の方が小さいからである。等価なコストの Type 2 経路が存在する場合には、 その経路を広告しているルータまでの AS 内の距離が経路選択に用いられる。 AS 内に Type 1 と Type 2 の外部メトリックが同時に存在することもできる。 その場合、Type 1 外部メトリックが常に先に評価される。 このセクションでは、外部の送信先に向かうパケットは、常にその経路を広告して いる AS バウンダリルータを経由して経路づけられることを前提としてきている。 しかし、この前提は常に妥当であるわけではない。例えば、図 2 において、 ネットワーク N6 に RTX と呼ばれるルータがアタッチされたと仮定する。さらに、 この RTXは OSPF の経路制御には関与せず、AS バウンダリルータ RT7 と EGP 情報を 交換しているとする。この場合、ルータ RT7 は RTX に経路づけられるべきな 送信先については、OSPF の外部経路として広告するのを止める。これらの送信先に 向かうパケットが常に初めにルータ RT7 (経路を広告しているルータ) に 経路づけられることが必要となると、余分なホップ数がかかってしまうことが あるからである。 このような状況を扱うために、OSPF プロトコルは AS バウンダリルータが外部 経路を広告する際に `転送アドレス' を指定することを許している。先の例では ルータ RT7 は、RTX に直接経路づけられるべき送信先については `転送アドレス' としてルータ RTX の IPア アドレスを指定する。 `転送アドレス' には他にも利用法がある。AS 内のルータに `ルートサーバ (route server)' 機能を持たせることである。例えば図 2 において、 ルータ RT6 は外部の経路制御情報を静的な設定と外部の経路制御プロトコルの 組み合わせから得ることにより、ルートサーバになることができる。その場合、 RT6 は自身を AS バウンダリルータであると広告し、OSPF の外部経路を収集 したものを生成しはじめる。また、広告する外部経路それぞれについて、 `転送アドレス' フィールドに適切な設定を施すことにより、送信先に向けた 正しい AS の出口を指定する。 2.3 等価なコストのマルチパス 先の議論は、いかなる送信先についても 1 つの経路しか存在しないと考える ことにより、簡素化されているものである。実際には、等価なコストを持つ経路が 複数存在する場合、それらは全て検出され、使用される。この振る舞いは アルゴリズムの概念に何らかの変更を求めるものではないので、この議論は tree の生成処理の詳細について検討するまで延期する。 等価なコストのマルチパスを使うことにより、ルータは任意の与えられた送信先に ついて、潜在的には幾つかのネクストホップを利用可能である。 2.4 TOSに基づいた経路制御 OSPF は IP Type of Service それぞれについて、独立した経路を計算することが できる。これは全送信先について IP TOS に対して 1 つずつ、複数の経路表 エントリが潜在的には存在可能であることを意味する。OSPF では、IP TOS の 値は IP パケットヘッダ内に現れるので、正確に表現される。 (この文書において) このセクションに至るまでに示した全ての例は、経路は TOS に基づいて変化しないという仮定をしている。TOS に基づいた経路を区別する ために、各 TOS について独立したインタフェースコストを設定することができる。 例えば図 2 において、各インタフェースについてそれぞれ TOS に対応した 複数のコストをリストすることができる。TOS 0 のコストは常に指定されなければ ならない。 インタフェースのコストが TOS に基づいて多様に設定される場合、各 TOS 毎に 独立した shortest-path tree が計算される (セクション 2.1 参照)。更に、 外部コストも TOS に基づいて多様に設定することができる。例えば図 2 において、 ルータ RT7 は各 TOS 毎に独立した Type 1 メトリックを広告することができる。 その場合、ネットワーク N15 までの TOS X の距離を計算する場合は、RT7 までの 最短の TOS X のパスに RT7 が広告する ネットワーク N15 までの TOS X のコスト が加えられる (セクション 2.2 参照)。 全ての OSPF の実装は、TOS に基づいた経路の計算ができなければならない。 しかし、OSPF ルータは全パケットを TOS 0 のパスに経路づけるように設定する ことができ (付録 C 参照)、非 0 の TOS のパスを計算する必要性を無くすことが できる。この手法は、ルータの経路表の領域と演算リソースを節約するために 用いることができる。TOS 0 のみしか扱えないルータと、TOS に基づいた経路づけが できるルータは混在することができる。非 0 の TOS が要求されるトラフィックの 転送時には TOS 0 しか扱えないルータは可能な限り避けられる。 ルータが非 0 の TOS パスを計算しても、パスが存在しない場合がある。その場合 非 0 な TOS を要求するパケットは TOS 0 のパスを通るよう経路づけられる。 (セクション 11.1 参照)。 3. 自律システムのエリアへの分割 OSPF は連続したネットワークとホストの集合を共にグループ化することを許して いる。このグループに、グループに含まれるネットワークにインタフェースを持つ ルータを加えたものをエリアと呼ぶ。各エリアでそれぞれ基本的な link-state 型 経路制御アルゴリズムの独立したコピーが動作する。これは各エリアがそれぞれ 先のセクションで述べられたエリア自身のトポロジカルデータベースと、対応する グラフを持っていることを意味する。 エリアのトポロジは、エリア外からは見えない。換言すると、エリア内部にある ルータはエリア外の詳しいトポロジーについては何も知らないということである。 この情報の分離によって、AS を 1 つの link-state ドメインとして 扱う場合に比べ、経路制御トラフィックを著しく減少させる効果が得られる。 エリアの導入により、AS 内のルータ全てが必ずしも同じトポロジカル データベースを持つわけではなくなる。実際、ルータは接続されているエリアに 応じて、それぞれ独立したトポロジカルデータベースを持つようになる。(複数の エリアに接続されているルータはエリアボーダルータと呼ばれる)。同じエリアに 属する 2 つのルータは、そのエリアに関する同じエリアトポロジカルデータベースを 持つ。 AS 内の経路制御は、発信元と送信先が同じエリア内にあるかどうかに 依存して 2 レベルで行なわれる。同じエリア内である場合はエリア内経路制御が 用いられ、そうでない場合はエリア間経路制御が用いられる。エリア内経路制御 では、パケットはエリア内で得られた情報のみによって経路づけられる。エリア外 から得られた経路制御情報が使用されることはない。こうすることにより、エリア 内経路制御を不正な経路制御情報の挿入から保護している。エリア間経路制御に ついては、セクション3.2で論ずる。 3.1 自律システムのバックボーン バックボーンはどのエリアにも属していないネットワーク、そのネットワークに アタッチされているルータ、複数のエリアに属するルータから構成される。 バックボーンは連続していなければならない。 バックボーンが連続しないようにエリアを定義することもできる。その場合、 システム管理者は virtual link を設定することによってバックボーンの接続性を 復元しなければならない。 virtual link は、バックボーン以外で共通のエリアにそれぞれインタフェースを持つ 任意の 2 つのバックボーンルータの間で設定可能である。virtual link は バックボーンに属する。プロトコルは virtuala link で接続された 2 つのルータを unnumbered な point-to-point ネットワークによって接続されているように扱う。 バックボーンのグラフでは、この 2 つのルータは弧で接続され、コストはエリア内の 2 ルータ間の距離になる。virtual link 上を流れる経路制御プロトコルの トラフィックはエリア内経路制御で使用するものだけである。 バックボーンはエリア間の経路制御情報を配布する責任を持っている。バックボーン 自身はエリアの性質を全て持っている。バックボーンのトポロジは他のエリアからは 見えず、バックボーンも他エリアのトポロジは知らない。 3.2 エリア間経路制御 2 つのエリア間でパケットを経路制御する際にはバックボーンが使われる。 パケットが通過するパスは 3 つの連続した部分に分解することができる。すなわち、 発信元からエリアボーダルータまでのエリア内パス、発信エリアから送信先エリア までのバックボーンパス、そして送信先までのもう 1 つのエリア内パスである。 アルゴリズムは最小のコストを持ったパスの集合を検出する。 別の見方をすると、エリア間経路制御とは AS をバックボーンをハブに、各エリアを スポークとして強制的にスター型 (ネットワーク) の設定をしているという描写が できる。 バックボーンのトポロジーはエリア間で用いられるバックボーンパスを指定する。 バックボーンのトポロジーは virtual link を加えることによって拡張することが できる。これにより、システム管理者にエリア間トラフィックが用いる経路を ある程度制御する権限を与える。 ソースエリアのパケット出口として使用される正しいエリアボーダルータは、 外部経路を広告しているルータが選択されるのと全く同様な方法で選択される。 エリア内にあるエリアボーダルータは、それぞれエリア外の全ネットワークに 関するコストを要約し、エリアに向けて広告する。エリアに関する SPF tree が 計算された後、他の全ネットワークへの経路はエリアボーダルータのサマリを 検査することによって計算される。 3.3 ルータの分類 エリアの概念を導入するまでは、図 2 におけるルータ RT5 のような特別な機能を 持った OSPF ルータだけが外部経路制御情報を広告していた。AS を OSPF エリアに 分割する際、ルータはその機能に応じて、更に以下の 4 つのオーバーラップする カテゴリに分割される。 インターナルルータ 同じエリアに属するネットワークに直接接続されているルータ。バックボーン だけにしかインタフェースを持たないルータもこのカテゴリに属する。この カテゴリのルータは基本的な経路制御アルゴリズムのコピーを 1 つ動作させる。 エリアボーダルータ 複数のエリアにアタッチしているルータ。エリアボーダルータは基本的な アルゴリズムのコピーを複数個動作させる。アタッチしているエリア毎に 1 つのコピー、更にバックボーン用のコピーである。エリアボーダルータは アタッチしているエリアのトポロジカル情報を要約し、バックボーンに配布する。 バックボーンはその情報を他のエリアに順次配布する。 バックボーンルータ バックボーンにインタフェースを持つルータ。このカテゴリは 2 つ以上の エリアにインタフェースを持つルータ (すなわちエリアボーダルータ) 全てを 含む。しかし、バックボーンルータは必ずしもエリアボーダルータである必要は ない。全インタフェースがバックボーンに接続されているルータはインターナル ルータと考えられる。 AS バウンダリルータ 他の AS に属するルータと経路制御情報を交換しているルータ。このルータは AS 外への経路を持ち、AS 内にその経路が広告される。各 AS バウンダリルータ までのパスは AS 内の全ルータが知っている。このカテゴリは先に分類された カテゴリーとは独立したものである。すなわち、AS バウンダリルータは インターナルルータでもエリアボーダルータであっても良い。また、バック ボーンに関係していてもしていなくても良い。 3.4 エリア設定の例 図 6 はエリア設定の例を示している。第 1 エリアはネットワーク N1-N4、 アタッチされているルータ RT1-RT4 から構成される。第 2 エリアはネットワーク N6-N8、ルータ RT7、RT8、RT10、RT11 から構成される。第 3 エリアはネットワーク N9-N11、ホスト H1、ルータ RT9、RT11、RT12 から構成される。第 3 エリアは エリア外に経路を広告する際に、ネットワーク N9-N11、ホスト H1 が 1 つの 経路にグループ化されるように設定される (詳細はセクション 3.5 参照)。 図 6 において、ルータ RT1、RT2、RT5、RT6、RT8、RT9、RT12 はインターナル ルータである。ルータ RT3、RT4、RT7、RT10、RT11 はエリアボーダルータである。 最後に、先に述べたように RT5 と RT7 は AS バウンダリルータである。 図 7 はエリア 1 をトポロジカルデータベース化した結果である。図はエリア内 経路制御を完全に記述している。また、2 つのインターナルルータ RT1 と RT2 の 間のネットワークを完全に記している。エリアボーダルータ RT3、RT4 によって、 エリア外の全送信先までの距離がエリア 1 内に広告される。これらの経路は 図 7 では点線の stub な経路として示されている。また、RT3 と RT4 は AS バウンダリルータ RT5、RT7 の位置をエリア 1 内に広告しなければならない。 最後に、RT5、RT7 から広告される外部経路情報は AS 全域に flood される。 エリア 1 内にも伝播される。これらの広告はエリア 1 のデータベースに含まれ、 ネットワーク N12-N15 への経路を生成する。 ルータ RT3 と RT4 はエリア 1 のトポロジーを要約し、バックボーンに配布 しなければならない。バックボーンに広告される情報を表 4 に示す。このサマリは エリア 1 にどのネットワークが含まれるか (すなわち、ネットワーク N1-N4)、 またそれらのネットワークからルータ RT3、RT4 まで、それぞれどれだけの距離が あるかを示すものである。 ........................... . + . . | 3+---+ . N12 N14 . N1|--|RT1|\ 1 . \ N13 / . | +---+ \ . 8\ |8/8 . + \ ____ . \|/ . / \ 1+---+8 8+---+6 . * N3 *---|RT4|------|RT5|--------+ . \____/ +---+ +---+ | . + / \ . |7 | . | 3+---+ / \ . | | . N2|--|RT2|/1 1\ . |6 | . | +---+ +---+8 6+---+ | . + |RT3|------|RT6| | . +---+ +---+ | . 2/ . Ia|7 | . / . | | . +---------+ . | | .Area 1 N4 . | | ........................... | | .......................... | | . N11 . | | . +---------+ . | | . | . | | N12 . |3 . Ib|5 |6 2/ . +---+ . +----+ +---+/ . |RT9| . .........|RT10|.....|RT7|---N15. . +---+ . . +----+ +---+ 9 . . |1 . . + /3 1\ |1 . . _|__ . . | / \ __|_ . . / \ 1+----+2 |/ \ / \ . . * N9 *------|RT11|----| * N6 * . . \____/ +----+ | \____/ . . | . . | | . . |1 . . + |1 . . +--+ 10+----+ . . N8 +---+ . . |H1|-----|RT12| . . |RT8| . . +--+SLIP +----+ . . +---+ . . |2 . . |4 . . | . . | . . +---------+ . . +--------+ . . N10 . . N7 . . . .Area 2 . .Area 3 . ................................ .......................... 図 6: OSPFのエリア設定例 ネットワーク RT3 の広告 RT4 の広告 -------------------------------------- N1 4 4 N2 4 4 N3 1 1 N4 2 3 表4: ルータ RT3、RT4からバックボーンに広告されるネットワーク バックボーンのトポロジカルデータベースを図 8 に示す。描かれているルータは バックボーンルータである。ルータ RT11 は 2 つのエリアに属するのでバック ボーンルータである。バックボーンを接続するため、ルータ RT10 と RT11 の間で virtual link が設定される。 繰り返すが、ルータ RT3、RT4、RT7、RT10、RT11 はエリアボーダルータである。 ルータ RT3、RT4 がそうであったように、これらのルータはアタッチしている エリアの経路制御情報を要約し、バックボーンに配布する。要約された経路は 図 8 では点線の stub な線として描かれている。第 3 エリアでは、ネットワーク N9-N11 とホスト H1 は 1 つの経路として要約されるように設定されていることを 思い出してもらいたい。このため、図 8 ではネットワーク N9-N11、ホスト H1 に 対して 1 本の点線が描かれる。ルータ RT5、RT7 は AS バウンダリルータである。 これらのルータが広告する外部から得られた経路制御情報は図 8 では stub として 描かれる。 バックボーン上ではエリアボーダルータ間でサマリ情報を交換することができる。 各エリアボーダルータはそれぞれ他のエリアボーダルータのエリア情報のサマリを 聞いている。その後、収集した広告を検査し、バックボーン内の各広告ルータへの 距離を付加することによって、エリア外にある全ネットワークへの距離を描いた 絵を作成する。 例として、もう一度ルータ RT3 と RT4 を取り上げると、手続きは以下のように 進行する。はじめに、バックボーンの SPF tree が計算される。この SPF tree は 全エリアボーダルータまでの距離を与える。また、バックボーンに属する ネットワーク (Ia と Ib)、AS バウンダリルータ (RT5 と RT7) までの距離も 記入される。これらの計算結果を表 5 に示す。 次に、エリアボーダルータから各エリアのサマリ情報を見ることにより、RT3 と RT4 はエリア外にある全ネットワークまでの距離を決定することができる。 これらの距離は RT3 と RT4 によってエリア内に広告される。ルータ RT3、RT4 に よってエリア 1 内に広告される情報を表 6 に示す。 **FROM** |RT|RT|RT|RT|RT|RT| |1 |2 |3 |4 |5 |7 |N3| ----- ------------------- RT1| | | | | | |0 | RT2| | | | | | |0 | RT3| | | | | | |0 | * RT4| | | | | | |0 | * RT5| | |14|8 | | | | T RT7| | |20|14| | | | O N1|3 | | | | | | | * N2| |3 | | | | | | * N3|1 |1 |1 |1 | | | | N4| | |2 | | | | | Ia,Ib| | |15|22| | | | N6| | |16|15| | | | N7| | |20|19| | | | N8| | |18|18| | | | N9-N11,H1| | |19|16| | | | N12| | | | |8 |2 | | N13| | | | |8 | | | N14| | | | |8 | | | N15| | | | | |9 | | 図 7: エリア 1 のデータベース ネットワークとルータは頂点で表現される。行 A と列 B の交点が X の場合、頂点 A と頂点 B はコスト X の辺でつながれる。 **FROM** |RT|RT|RT|RT|RT|RT|RT |3 |4 |5 |6 |7 |10|11| ------------------------ RT3| | | |6 | | | | RT4| | |8 | | | | | RT5| |8 | |6 |6 | | | RT6|8 | |7 | | |5 | | RT7| | |6 | | | | | * RT10| | | |7 | | |2 | * RT11| | | | | |3 | | T N1|4 |4 | | | | | | O N2|4 |4 | | | | | | * N3|1 |1 | | | | | | * N4|2 |3 | | | | | | Ia| | | | | |5 | | Ib| | | |7 | | | | N6| | | | |1 |1 |3 | N7| | | | |5 |5 |7 | N8| | | | |4 |3 |2 | N9-N11,H1| | | | | | |1 | N12| | |8 | |2 | | | N13| | |8 | | | | | N14| | |8 | | | | | N15| | | | |9 | | | 図 8: バックボーンのデータベース ネットワークとルータは頂点で表現される。行 A と列 B の交点が X の場合、頂点 A と頂点 B はコスト X の辺でつながれる。 エリアボーダ RT3 からの RT4 からの ルータ 距離 距離 -------------------------------------- to RT3 * 21 to RT4 22 * to RT7 20 14 to RT10 15 22 to RT11 18 25 ______________________________________ to Ia 20 27 to Ib 15 22 ______________________________________ to RT5 14 8 to RT7 20 14 表 5: ルータ RT3、RT4 によって計算されるバックボーンの距離 表 6 はバックボーンに対して、Ia と Ib が 1 つの広告にグループ化されるような エリアレンジが設定されていると仮定していることに注意してほしい。 ルータ RT3、RT4によってエリア 1 に導入される情報は、RT1 のような内部 ルータがエリアボーダルータをインテリジェントに選択するために有効に作用する。 ルータ RT1 はネットワーク N6 へのトラフィックについては RT4 を使用し、 ネットワーク N10 へのトラフィックは RT3 を使用する。ネットワーク N8 への トラフィックについては、2 つのルータ間で負荷を分配する。 送信先 RT3 の広告 RT4 の広告 ------------------------------------- Ia,Ib 15 22 N6 16 15 N7 20 19 N8 18 18 N9-N11,H1 19 26 _____________________________________ RT5 14 8 RT7 20 14 表 6: ルータ RT3、RT4 によってエリア 1 に広告される配送先 ルータ RT1 は同じ方法によって AS バウンダリルータ RT5、RT7 までの最短パス を決定することもできる。そして RT5、RT7 の外部経路広告を調査することにより、 他の自律システム内の送信先 (ネットワーク N12-N15 のうちの 1 つ) への送信時 RT5、RT7 のどちらを使うかを決定することができる。 ここで、ルータ RT6-RT10 間の物理的な線に障害が発生すると、バックボーンが 切断されることに注意してほしい。ルータ RT7-RT10 間に virtual link を設定 することにより、ックボーンの接続性を高め、このような障害に対しても高い 耐性を与えることができる。また、RT7-RT10 間の virtual link は、第 3 エリア (ネットワーク N9 を含む) と、外部ネットワーク N12 の良質な経路情報を 広告するルータ RT7 の間に非常に短いパスを提供する。 3.5 IP サブネッティングのサポート OSPF は広告される経路それぞれに IP アドレスマスクを添付する。マスクは、 特定の経路によって記述されるアドレスの範囲を示すものである。例えば、送信先 128.185.0.0 に対するサマリ広告にマスク 0xffff0000 が指定されている場合、 そのサマリ広告は送信先 128.185.0.0 〜 128.185.255.255 をまとめたものを 1 つの経路として記述しているということである。同様に、ホストルートは 常にマスク 0xffffffff で広告される。これは送信先が 1 つしか存在しないことを 意味する。 広告される送信先の経路にマスクを含めることにより、一般に可変長 サブネッティングとして扱われているものを実装することができる。これはクラス A、B、C の 1 つのネットワーク番号を多様なサイズを持つたくさんのサブネットに 分割可能であることを意味する。例えば、ネットワーク 128.185.0.0 は 62 個の 多様なサイズのサブネットに分割することができる。サイズ 4K の 15 の サブネット、サイズ 256 の 15 のサブネット、サイズ 8 の 32 のサブネット である。表 7 は結果得られるネットワークアドレスとマスクを示している。 ネットワーク IP アドレス サブネットの アドレス マスク サイズ ----------------------------------------------- 128.185.16.0 0xfffff000 4K 128.185.1.0 0xffffff00 256 128.185.0.8 0xfffffff8 8 表 7: 幾つかのサブネットサイズの例 クラス A、B、C のネットワークを様々なサイズのサブネットに分割する方法は 数多く存在する。正しく分割する手続きについては本仕様書の範囲を超えるもので あるが、以下のガイドラインを制定する。すなわち、パケット転送時には常に パケットの送信先にベストマッチするネットワークに転送される。ここでベスト マッチとは最も一致する部分が長いか、最も特定可能ということである。例えば、 送信先 0.0.0.0 マスク 0x00000000 のデフォルトルートは常に全ての IP 送信先に マッチする。しかし、常に他のいかなるマッチよりも特定しにくい。サブネット マスクは全ての IP 送信先に対するベストマッチが明確になるよう割り当てられ なければならない。 OSPF エリアの概念は、IP サブネットワークの後にモデル化された。OSPF エリアは ネットワークをまとめたものとして、ゆるく定義されてきている。実際は、 OSPF エリアはアドレスレンジをリストしたものが指定される (詳細はセクション C.2 を参照のこと)。アドレスレンジはそれぞれ [アドレス、マスク] のペアとして 定義される。サブネット化されたネットワークが多くの独立したサブネットから 構成されるのと同じように、1 つのアドレスレンジは多くの独立したネットワークを 含み得る。エリアボーダルータは、各アドレスレンジについて 1 つの経路を 広告することによって、エリアの内容を要約し、バックボーンに配布する。経路の コストは、指定されたレンジに含まれるネットワークの中で最小のものが選ばれる。 例えば、1 つの IP サブネット化されたネットワークは、1 つの OSPF エリアとして 設定することができる。その場合、そのエリアは 1 つのアドレスレンジとして 定義される。すなわち、クラス A、B、C のネットワーク番号と、対応する ナチュラル IP マスクである。エリア内では、多様なサイズを持つサブネットを 幾つでも定義することができる。エリア外に対してはサブネット化された ネットワーク全体に対する 1 つの経路が配布される。エリア内のネットワークが サブネット化されていたとしても、それは隠される。エリア外に広告される経路の コストは、構成されるサブネットの中で最小のものが選択される。 3.6 stub エリアのサポート ある AS では、トポロジカルデータベースの主要な部分が AS external な広告に よって構成されていることがある。OSPF の AS external な広告は通常、AS 全体に flood される。しかし、OSPF は特定のエリアを `stub' エリアとして設定する ことを許している。AS external な広告は stub エリア内には flood されない。 AS external な送信先への経路制御は (エリア毎の) デフォルトルートだけに 基づいて行なわれる。こうすることにより、stub エリアの内部ルータは トポロジカルデータベースのサイズを小さくでき、結果として必要なメモリサイズを 小さくすることができる。 OSPF の stub エリアサポートの利便性を得るために、stub エリア内ではデフォルト ルートに基づいた経路制御が使用されなければならない。これは以下のように 達成される。1 つまたはそれ以上の stub エリアのエリアボーダルータがデフォルト ルートをサマリ広告に載せて stub エリア内に広告しなければならない。この サマリデフォルトは stub エリア内には flood されるが、それ以上は伝播されない。 (このため、このデフォルトルートは特定の stub エリアにしか関係しない)。 サマリデフォルトは明らかにエリア内パス、エリア間パスを通って到達できない 送信先 (つまり AS external な送信先) 全てにマッチする。 エリアは、そのエリアの出口が 1 つしかないとき、または外部の送信先毎に出口の 選択をする必要がないとき、stub として設定することができる。例えば、図 6 に おけるエリア 3 は stub エリアとして設定可能である。なぜなら、全ての 外部トラフィックはエリアボーダルータ RT11 を通過しなければならないから である。エリア 3 が stub として設定されると、ルータ RT11 はネットワーク N12-N15 に対する AS external な広告をエリア内に flood する替わりに、 (サマリリンク広告に載せて) デフォルトルートを広告する。 OSPF プロトコルは、あるエリアに属する全ルータが、そのエリアが stub として 設定されているかどうか認識することを保証している。これにより、AS external な広告を flood する際に混乱が生じないことが保証される。 stub エリアの使用にあたり、制限が 2、3 存在する。virtual link は stub エリア を経由して設定できない。更に、AS バウンダリルータは stub エリア内には 置くことができない。 3.7 エリアの分割 OSPF は積極的にエリアの分割を修復しようとは試みない。エリアが分割されると、 各コンポーネントは単純に独立したエリアとなる。バックボーンは新しく作られた エリアとの間で経路制御を行なうようになる。分割前にはエリア内経路制御で到達 できた幾つかの送信先は、分割後は到達するためにエリア間経路制御を必要と するようになる。 先のセクションでは、エリアはアドレスレンジのリストとして記述されていた。 どのようなアドレスレンジであったとしても、エリア分割時にはどれか 1 つの コンポーネント内に完全な形で含まれなければならない。これは、エリアの内容が バックボーンに要約されて広告される手法と共になされなければならない。 また、バックボーン自身は分割してはならない。もし分割してしまうと、AS の 一部が unreachable になる。バックボーンの分割は virtual link を設定する ことによって修復可能である (セクション 15 参照)。 エリア分割について考えるもう 1 つの方法は、セクション 2 で紹介した AS の グラフを見ることである。エリア ID は、グラフの辺を着色した色と見なす ことができる [1]。グラフの辺はネットワークに接続されているか、もしくは 自身が point-to-point ネットワークである。どちらの場合においても、グラフの 辺はネットワークのエリア ID で色づけされる。 同じ色に着色されていて、かつ頂点によって接続されているグラフの辺のグループは エリアを表現する。AS のトポロジーに手を加えていないならば、グラフはエリア ID で表される色に彩られた、幾つかの領域を持つことになる。 AS のトポロジーが変化した場合、エリアの 1 つが分割されるかもしれない。 その場合、AS のグラフは同じ色 (エリア ID) を持つ複数の領域を持つことになる。 AS 内の経路制御は、同じ色を持った領域が 1 つのバックボーン領域によって 接続されている限り、その機能を継続する。 4. 機能の概略 各エリアでは、OSPF の基本的な経路制御アルゴリズムの独立したコピーが動作する。 複数のエリアにインタフェースを持つルータでは、複数個のアルゴリズムのコピーが 動作する。経路制御アルゴリズムの簡潔なサマリは以下のとおりである。 ルータ起動時、初めに経路制御プロトコルのデータ構造体が初期化される。次に ルータは低階層のプロトコルからインタフェースが functional になったという 指示を待つ。 次に、ルータは neighbor を得るために、 OSPF の Hello プロトコルを使用する。 ルータは neighbor に Hello パケットを送信し、neighbor からの Hello パケットを 順次受信する。ブロードキャストネットワーク、point-to-point ネットワークでは ルータは Hello パケットをマルチキャストアドレス AllSPFRouters に送信する ことにより、neighboring ルータを動的に検出する。ノン・ブロードキャスト ネットワークでは、幾つかの設定情報が neighbor を検出するために必要になる。 全てのマルチアクセスネットワーク (ブロードキャスト、もしくはノン・ブロード キャスト) では、Hello プロトコルはまた、ネットワークに対する Designated ルータをも選択する。 ルータは新たに得られた neighbor から adjacency を形成しようと試みる。 トポロジカルデータベースは adjacent なルータのペア間で同期される。マルチ アクセスネットワークでは Designated ルータが adjacent になるべきルータを 決定する。 adjacency は経路制御プロトコルのパケット配布を制御する。経路制御プロトコルの パケットは、adjacency だけが送信し、受信する。特に、トポロジカルデータベース の更新情報の配布は、adjacency に沿って処理される。 ルータは、定期的に link-state と呼ばれる自らの状態を広告する。link-state は ルータの状態が変化したときにも広告される。ルータの adjacency には link-state 広告の内容が反映される。この adjacency と link-state の関係により、 プロトコルはダウンしたルータを現代的な手法で検出することができる。 link-state 広告はエリアを通って flood される。flood をするアルゴリズムは 信頼性があり、エリア内の全ルータが完全に同じトポロジカルデータベースを持つ ことを保証するものである。このデータベースは、エリアに属する各ルータから 受信した link-state 広告をまとめて構成される。このデータベースから、 各ルータは自身を root とした shortest-path tree を計算する。shortest-path tree はプロトコルの経路表を順次作成していく。 4.1 エリア間経路制御 先のセクションでは、1 つのエリア内におけるプロトコルのオペレーションに ついて述べた。エリア内経路制御のために、他の経路制御情報は特に関係しない。 エリア外の送信先への経路づけを可能にするために、エリアボーダルータは エリア内に付加的な経路制御情報を広告する。この付加的な情報は、そのエリアを 除いた AS の残り部分から作られる `蒸留物' である。 この蒸留物は以下のように生成される。定義により、各エリアボーダルータは バックボーンに接続されている。各エリアボーダルータは、アタッチされている エリアのトポロジを要約し、バックボーン上で伝達する。そのため、その情報は 他の全エリアボーダルータにも転送される。エリアボーダルータは、バックボーンに 関する完全なトポロジー情報と、エリアボーダルータから得られたエリアサマリを 持つ。この情報から、ルータは自身がアタッチしているエリアに含まれない全ての 送信先へのパスを計算する。その後、ルータはそれらのパスをアタッチしている エリアに広告する。これにより、エリア内部のルータが他のエリア内にある送信先に トラフィックを転送する際に、最適なエリア出口を選択することができる。 4.2 AS external な経路 他の AS に関する情報を持つルータは、その情報を AS 内に flood することが できる。この外部経路制御情報は、その AS に属する全ルータに 1 つ残らず配布 される。ただし例外が 1 つあり、外部経路制御情報は stub エリアには flood されない (セクション 3.6 参照)。 外部経路制御情報を利用するために、外部経路制御情報を広告する全ルータまでの パスは AS 全域 (stub エリアを除く) に知られていなければならない。このため、 AS ボーダルータの位置は (stub でない) エリアボーダルータによって要約され なければならない。 4.3 経路制御プロトコルのパケット OSPF プロトコルは IP プロトコル番号 89 を使用して、IP 上で直接動作する。 OSPF は明確なフラグメンテーション/リアセンブルのサポートはしない。 フラグメンテーションが必要な場合には、IPのフラグメンテーション/リセンブルが 用いられる。OSPF のプロトコルパケットは、大きいプロトコルパケットは幾つかの 小さなプロトコルパケットに分割できるように設計されている。この作業の実行を 推奨する。IP のフラグメンテーションは常に可能な限り避けられるべきである。 経路制御パケットは、常に IP TOS フィールドに 0 をセットして送信されるべき である。もし可能であるなら、経路制御プロトコルは送信、受信の際に、定常的な IP データトラフィック以上の優先度を与えられるべきである。これらを達成する 助けとして、OSPF プロトコルパケットは Internetwork Control (RFC791 参照) の 値がセットされた IP precedence フィールドを持つべきである。 全ての OSPF プロトコルパケットは付録 A に記述されているような共通の プロトコルヘッダを持つ。OSPF パケットのタイプは表 8 にリストされている。 これらのフォーマットもまた付録 A に記述されている。 タイプ パケット名 プロトコル関数 ---------------------------------------------------------- 1 Hello neighbor の検出、維持 2 Database Description データベースの内容の要約 3 Link State Request データベースのダウンロード 4 Link State Update データベースの更新 5 Link State Ack ack の flood 表 8: OSPF パケットのタイプ OSPF Hello プロトコルは、neighbor な関係を発見し、維持するために用いられる。 Database Description パケット、Link State Request パケットは adjacency を 形成するために使用される。OSPF の信頼性のある更新メカニズムは Link State Update パケット、Link State Acknowledgement パケットによって実装される。 各 Link State Update パケットは、その生成ポイントから 1 ホップ先に新しい link-state 広告の集合を運ぶ。1 つの Link State Update パケットには、幾つかの ルータの link-state 広告が含まれているかもしれない。各広告は生成ルータの ID と、link-state の内容のチェックサムがタグ付けされる。5 種類の異なる OSPF link-state 広告は、表 9 にリストされている。 上述したように、OSPFの経路制御パケット (Helloパケットを除く) は、adjacency だけに送信される。これは全ての OSPF のプロトコルパケットは、IP 的に 1 ホップ 移動することを意味していることに注意してほしい。ただし、virtual adjacency へのパケット送信は例外である。OSPF プロトコルパケットの IP 発信元アドレスは ルータ adjacency の片端であり、IP 送信先アドレスは adjacency のもう片側か IP マルチキャストアドレスとなる。 LS 広告の名称 広告に関する記述 タイプ ------------------------------------------------------------- 1 ルータリンク 全ルータで生成される。この広告は 広告 エリアにアタッチしているルータの インタフェースの状態をまとめて 記述する。1 つのエリアだけにしか flood されない。 ------------------------------------------------------------- 2 ネットワーク Designated ルータがマルチアクセス リンク広告 ネットワークに関して生成する。 この広告は、ネットワークに接続 しているルータのリストを含む。 1 つのエリアだけにしか flood されない。 ------------------------------------------------------------- 3,4 サマリリンク エリアボーダルータによって生成 広告 され、広告に関係するエリア全てに flood される。サマリリンク広告は AS 内にありながらもエリアの外に ある送信先への経路 (つまりエリア 間経路) を記述する。Type 3 広告は ネットワークへの経路、Type 4 広告 は AS バウンダリルータへの経路を 記述する。 ------------------------------------------------------------- 5 AS external AS バウンダリルータによって生成 リンク広告 され、AS 内に flood される。 各 AS external リンク広告は、 他の AS 内の送信先への経路を 記述する。その AS に向けた デフォルトルートを AS external リンク広告内に記述しても良い。 ------------------------------------------------------------- 表 9: OSPF の link-state 広告 4.4 基本実装要求 OSPF の実装には以下のシステムサポートを必要とする。 タイマ 2 つの異なる種類のタイマが必要とされる。1 つめは single shot timer と 呼ばれるもので、1 度発火し、処理されるべきプロトコルイベントの引き金と なるものである。2 つめは interval timer と呼ばれるもので、ある間隔毎に 連続的に発火するものである。これらのタイマは、定常的な間隔でパケットを 送信するために用いられる。Hello パケットの定常的なブロードキャスト (ブロードキャストネットワーク上の) が良い例である。どちらのタイマも 1 秒単位で設定される。 インターバルタイマは特性変化を避けて実装されるべきである。幾つかの ルータの実装では、パケットの処理がタイマの実行に影響を与え得る。1 つの ネットワークに複数のルータがアタッチされ、その全てがブロードキャストを する場合、特性変化によって (避けられるべき) 経路制御パケットの同期を 引き起こす可能性がある。特性変化を避けたタイマの実装ができない場合、 発火までのタイマ間隔に対して、微量の乱数を加算/減算するべきである。 IP マルチキャスト ある種の OSPF パケットは、IP マルチキャストデータグラムの形式を利用する。 したがって、適切な低階層のプロトコルにおける IP マルチキャスト データグラムの送信/受信サポートが要求される。OSPF に用いられる IP マルチキャストデータグラムは 2 ホップ以上は移動しない。このため、 IP マルチキャストデータグラムの転送機能は必要とされない。IP マルチ キャストの情報については [RFC 1112] を参照のこと。 可変長サブネットのサポート ルータの IP プロトコルサポートは、1 つの IP クラス A、B、C ネットワークを 様々なサイズのサブネットに分割できる機能を含まれなければならない。 これは一般に可変長サブネッティングと呼ばれるものである。詳細については セクション 3.5 を参照のこと。 IP スーパーネッティングのサポート ルータの IP プロトコルサポートには、連続した IP クラス A、B、C ネット ワークを aggregate し、スーパーネットと呼ばれるより大きな単位にする 機能が含まれなければならない。スーパーネッティングはインターネットに おける IP 経路制御の拡張性を改善する一手法として提案された。詳細は [RFC 1519] を参照のこと。 低階層のプロトコルのサポート ここでいう低階層のプロトコルとは、イーサネットのデータリンク層のような ネットワークアクセスプロトコルを言う。ネットワークインタフェースが アップ/ダウンした際に、このプロトコルから OSPF に指摘がされなければ ならない。例えばイーサネットにおいて、イーサネットトランシーバケーブルが 抜けた際にこの機能の真価が発揮される。 ノン・ブロードキャストな低階層のプロトコルのサポート X.25 PDN のようなノン・ブロードキャストネットワークはマルチアクセス ネットワークであることを思い出してほしい。このネットワークでは、ダウン しているか、存在しないルータに対してパケットを送信しようと試みる際に、 Hello プロトコルは低階層のプロトコルから OSPF への指示を検証することに よって助けが得られる。例えば X.25 PDN では、ダウンしている neighboring ルータがある場合、X.25 は症状と原因を明らかにし、情報を OSPF に渡すので、 X.25からの情報を受理することにより、ダウンしたルータの存在が指摘される。 リストの基礎的な取り扱い OSPF の機能のほとんどは link-state 広告のリスト処理によって記述される。 例えば、返事が返ってくるまで adjacent なルータに再送される収集された 広告は、1 つのリストとして記述される。どのような特別な広告であっても 多くのリストによって表現し得る。OSPF の実装では、必要に応じてリストの 要素となる広告の追加/削除といったリストのオペレーションが必要になる。 タスク処理のサポート 本仕様書の中に記述されているある種の手続きは、他の手続きを呼び出す。 時には、他の手続きがインライン処理、すなわち親手続きが終了する前に 実行されるべき場合がある。これは文中では手続きを実行する命令として 示される。別の場合には、他の手続きは親プロセスが終了した後にだけ実行 される。これはタスクをスケジュールする命令によって示される。 4.5 オプショナルな OSPF の機能 OSPF プロトコルは幾つかのオプショナルな機能を定義している。ルータはサポート しているオプショナルな機能を OSPF Hello パケット、Database Description パケット、link-state 広告内に示す。こうすることにより、オプショナルな機能を サポートするルータを 1 つの AS 内に共存させることができる。 ある特定のエリアにアタッチされているルータは、全て幾つかの機能をサポートして いなければならない。その場合、ルータはパケット内に記された機能が一致 しなければ、neighbor の Hello パケットを受け取らない。(つまり、サポートする サポート機能の不一致は neighbor の関係形成を妨げる)。この例として ExternalRoutingCapability が挙げられる (後述)。 他の機能は、Database Exchange 処理の間に調整することができる。これは Database Description パケット内にオプショナルな機能を指定することによって 達成される。機能が不一致の場合、2 つの neighbor 間で link-state 広告の サブセットだけが交換される。 経路表の生成処理もまたオプショナルな機能の有り/無しによって影響され得る。 例えば、オプショナルな機能が link-state 広告中で報告されている場合、特定の 機能をサポートしないルータは shortest path tree 構築の際に避けられる。 この例として TOS 経路制御機能が挙げられる (後述)。 現在の OSPF のオプショナルな機能を以下にリストする。より詳細な情報については セクション A.2 を参照のこと。 ExternalRoutingCapability OSPF のエリア全域を stub として設定することができる (セクション 3.6 参照)。AS external な広告は stub エリアには flood されない。この機能は OSPF オプションズフィールド内の E-bit によって表現される (セクション A.2 参照)。stub エリアが矛盾無く設定されることを保証するために、 stub エリアにインタフェースを持つ全ルータは Hello パケット内の E-bit を クリアしなければならない (セクション 9.5、10.5 参照)。 TOS 機能 全ての OSPF の実装は、IP Type of Service に基づき、独立した経路を 計算できなければならない。しかし、経路表の容量と処理系のリソースを 節約するために、OSPF ルータはパケット転送時に TOS を無視するような設定を することができる。その場合、ルータは TOS 0 だけの経路を計算する。 この機能は OSPF オプションズフィールド内の T-bit によって表現される。 (セクション A.2 参照)。TOS-capable なルータは、非 0 な TOS パスを計算 する際に、TOS-capable でないルータを避けようと試みる。 5. プロトコルのデータ構造体 本仕様書では、OSPF プロトコルはプロトコルの様々なデータ構造体をオペレートする ものとして記述される。以下のリストが最上位の OSPF データ構造体を構成する。 初期化が必要な場合には注記がなされている。OSPF エリア、インタフェース、 neighbor もまた後述するような関連するデータ構造体を持つ。 ルータ ID AS 内のルータを一意に識別する 32bit の数。実装の戦略の 1 つとして 考えられるのが、ルータに属する最小の IP インタフェースアドレスを用いる ことである。ルータの OSPF ルータ ID が変更されたなら、そのルータの OSPF ソフトウェアは新しいルータ ID が効果を発揮する前に再起動される べきである。ルータ ID を変更するための再起動前には、そのルータが生成して いる link-state 広告を経路制御ドメインから消去すべきである (セクション 14.1 参照)。そうしないと、link-state 広告は MaxAge に達するまで他の ルータに保持されてしまう。 エリア構造体 ルータが接続されているエリアはそれぞれ自分自身のデータ構造を持つ。 このデータ構造は基本的なアルゴリズムの働きを記述する。各エリアでは、 それぞれ独立した基本的アルゴリズムが動作していることを思い出してほしい。 バックボーン (エリア) 構造体 基本的なアルゴリズムは、バックボーンを 1 つのエリアとしてオペレートする。 このため、バックボーンはエリア構造体として表現される。 virtual link 設定 virtual link は、このルータを片方の端として設定される。virtual link を 設定するためには、そのルータはエリアボーダルータでなければならない。 virtual link はもう片側、すなわちもう 1 つのエリアボーダルータの ルータ ID によって識別される。両端のルータは virtual link の Transit エリアと呼ばれる共通のエリアにアタッチされていなければならない。 virtual link はバックボーンの一部であり、2 つのルータ間が unnumbered な point-to-point ネットワークで接続されているかのように振る舞う。 virtual link はパケットを転送するために、virtual link の Transit エリアの エリア内経路制御を利用する。virtual link は Transit エリアの shortest path tree 構築を通してアップ、ダウンする。 外部経路のリスト これらは AS 外にある送信先への経路である。これらはもう 1 つの経路制御 プロトコル (EGP のような) か、設定情報、あるいはその組み合わせ (例えば 動的に得た情報を静的に設定した OSPF のメトリックで広告する) によって 得られる。外部経路を持つルータは全て AS バウンダリルータと呼ばれる。 外部経路はこのルータによって、OSPF 経路制御ドメイン内に AS external な リンク広告に載せて広告される。 AS external リンク広告のリスト トポロジカルデータベースの一部。これらは AS バウンダリルータによって 生成される。AS バウンダリルータは AS 外の送信先への経路を保持する。 ルータ自身が AS バウンダリルータである場合、AS external リンク広告の 幾つかはそのルータ自身によって生成されていることに注意してほしい。 経路表 トポロジカルデータベースから導き出されるもの。ルータが転送可能な 送信先はコストとパスの集合によって表現される。パスはタイプと ネクストホップによって記述される。より詳しい情報については、セクション 11 を参照のこと。 TOS 機能 この項目はルータが TOS に基づいて独立した経路を計算できるかどうかを 示している。これは設定変更が可能なパラメータである。より詳しい情報に ついてはセクション 4.5、16.9 を参照のこと。 図 9 は代表的なルータの中に存在するデータ構造体をまとめたものである。 図示されているルータは、図 6 の RT10 である。ここで、ルータ RT10 は ルータ RT11 との間にエリア 2 をその Transit エリアとして virtual link を 設定していることに注意してほしい。これは図 9 では点線で示されている。 エリア 2 の shortest-path tree 構築を通して virtual link が active に なると、この点線がバックボーンへのインタフェースになる。(図 9 には 2 つの バックボーンインタフェースが描かれている)。 +----+ |RT10|------+ +----+ \+-------------+ / \ | 経路表 | / \ +-------------+ / \ +--------+ / \ +------------+ |エリア 2|---+ +---|バックボーン| +--------+***********+ +------------+ / \ * / \ / \ * / \ +---------+ +---------+ +------------+ +-----------------+ | N6 への | | N8 への | | RT11 への | |インタフェース Ib| |インタ | |インタ | |Virtual Link| +-----------------+ |フェース | |フェース | +------------+ | +---------+ +---------+ | | / \ | | | / \ | | | +--------+ +--------+ | +-------------+ +------------+ |Neighbor| |Neighbor| | |Neighbor RT11| |Neighbor RT6| | RT8 | | RT7 | | +-------------+ +------------+ +--------+ +--------+ | | +-------------+ |Neighbor RT11| +-------------+ 図 9: ルータ RT10 のデータ構造体 6. エリアのデータ構造体 エリアのデータ構造体には、基本的な経路制御アルゴリズムを動作させるために 用いられる全ての情報が含まれる。各エリアはそれぞれ自分自身のトポロジカル データベースを維持している。1 つのネットワークは 1 つのエリアに属する。 また、ルータのインタフェースも 1 つのエリアにしか接続しない。 ルータの adjacency はそれぞれ 1 つのエリアに属する。 OSPF のバックボーンはエリアの特性を全て持つ。このため、バックボーンもまた 1 つのエリア構造体によって表現される。データ構造体中の幾つかの項目は、 バックボーンと非バックボーンで異なる適用がなされることに注意してほしい。 エリアのトポロジカルデータベース (もしくは link-state データベース) は、 エリアに属するルータによって生成されたルータリンク広告、ネットワークリンク 広告、サマリリンク広告を収集して構成される。この情報は 1 つのエリアにだけ flood される。AS external リンク広告 (セクション 5 参照) も各エリアの トポロジカルデータベースの一部と考えられる。 エリア ID エリアを識別する 32bit の数。0.0.0.0 はバックボーンのエリア ID のために 予約されている。サブネット化されたネットワークを異なるエリアに割り当てて いる場合には、IP ネットワーク番号をエリア ID として用いることができる。 構成要素のアドレスレンジリスト エリアを定義するアドレスの範囲。各アドレスレンジは[アドレス、マスク]の ペアと Adviertize か DoNotAdvertize (セクション 12.4.3 参照) の どちらかの状態によって指定される。各ネットワークは自身が属する アドレスレンジに依存してエリアに割り当てられる。(指定されるアドレス レンジがオーバーラップすることは許されない)。例えば、あるサブネット化 された IP ネットワークを独立した OSPF エリアにする場合、そのエリアは 1 つのアドレスレンジ、すなわちナチュラルマスクを持ったクラス A、B、C の IP ネットワーク番号から構成される。 関連するルータのインタフェース そのエリアに接続しているルータのインタフェース。ルータのインタフェースは たった 1 つのエリア (もしくはバックボーン) だけに属する。バックボーンの 構造体では、このリストは全ての virtual link を含む。virtual link は もう片側のルータ ID によって識別され、そのコストは 2 つのルータ間に 存在する Transit エリアを通る最短のエリア内パスのコストである。 ルータリンク広告のリスト ルータリンク広告は、エリア内の各ルータによって生成される。これはエリアに アタッチしているルータのインタフェースの状態を記述する。 ネットワークリンク広告のリスト ネットワークリンク広告は、エリア内の transit なマルチアクセス ネットワークについて、それぞれ 1 つ生成される。ネットワークリンク広告は 現在そのネットワークに接続されているルータの集合を記述する。 サマリリンク広告のリスト サマリリンク広告は、そのエリアのエリアボーダルータより生成される。 これらは AS 内ではあるが、そのエリアの外にある送信先への経路を記述する。 shortest-path tree ルータ自身を root とする、そのエリアの shortest-path tree。ルータリンク 広告、ネットワークリンク広告を収集し、Dijkstra アルゴリズムによって 導き出される。 AuType エリアで用いられる認証のタイプ。認証のタイプは付録 D で定義されている。 全ての OSPF パケット交換は、認証がなされる。異なるエリアでは、異なる 認証機構を用いても構わない。 TransitCapability 1 つ以上のエリアがそのエリアを virtual link の Transit エリアとして 利用している場合にだけ、TRUE にセットされる。このパラメータは そのエリアで生成されたものでもなく、そのエリア内に送信されるわけでもない データトラフィックを配送できるかどうかを示すのと等価である。 このパラメータはそのエリアの shortest-path tree が構築 (セクション 16.1 参照) される際に計算され、経路表構築後に発生するステップ (セクション 16.3 参照) への入力に用いられる。 ExternalRoutingCapability AS external 広告がそのエリア内に flood されるかどうかを示す。これは 設定変更可能なパラメータである。AS external 広告がそのエリアから 締め出されている場合、そのエリアは `stub' と呼ばれる。stub エリア内では AS external な送信先への経路制御はデフォルトサマリルートに基づいて 行なわれる。バックボーンは stub エリアとして設定することができない。 また、virtual link も stub エリアを通しては設定できない。より詳細な 情報についてはセクション 3.6 参照。 StubDefaultCost エリアが stub エリアとして設定されており、そのルータがエリアボーダルータ である場合、StubDefaultCost はルータがエリア内に広告すべきデフォルト サマリリンクのコストを示す。各 IP TOS に対して、それぞれ独立したコストを 設定可能である。より詳細な情報についてはセクション 12.4.3 参照のこと。 特に指定が無い限り、本ドキュメントの残りのセクションは 1 つのエリア内に おけるプロトコルのオペレーションを扱う。 7. adjacency の bring up OSPF は経路制御情報を交換するために、neighbor なルータ間で adjacency を 作る。2 つの neighbor なルータ全てが adjacent になるわけではない。 このセクションでは、adjacency 形成に関する概論をカバーする。詳細については セクション 10 参照のこと。 7.1 Hello プロトコル Hello プロトコルは neighbor な関係を確立し、維持する責任を持つ。また、 neighbor 間の通信は双方向である保証をするものでもある。Hello パケットは 全ルータのインタフェースから定期的に送出される。neighbor の Hello パケット の中に自分自身がリストされている場合、通信が双方向であることを示す。 マルチアクセスネットワークでは、Hello プロトコルはそのネットワークに対する Designated ルータを選出する。Designated ルータは、どのような adjacency が ネットワーク上に形成されるかを制御する (後述)。 Hello プロトコルは、ブロードキャストネットワーク上ではノン・ブロードキャスト ネットワークと比べて異なった働きをする。ブロードキャストネットワークでは、 各ルータは Hello パケットを定期的にマルチキャストすることによって、自分自身の 状態を広告する。これにより、neighbor を動的に検出することが許される。 これらの Hello パケットには Designated ルータの立場から見たルータの情報と、 最近受け取った Hello パケットを送信したルータのリストが含まれている。 ノン・ブロードキャストネットワークでは Hello プロトコルのオペレーションの ために、幾つかの設定情報が必要になる。潜在的に Designated ルータになる 可能性があるルータは、それぞれネットワークにアタッチしている他の全ルータの リストを持つ。潜在的な Designated ルータは、ノン・ブロードキャスト ネットワークへのインタフェースが初めてオペレーショナルになった際に、 他の潜在的 Designated ルータ全てに Hello パケットを送信する。これは、 ネットワークに対する Designated ルータを発見しようとする試みである。 そのルータ自身が選出された Designated ルータである場合、ネットワークに アタッチしている他の全ルータに Hello パケットを送信しはじめる。 neighbor が検出された後は双方向の通信が保証される。また、(マルチアクセス ネットワーク上であるなら) Designated ルータが選出されたなら、その neighbor と adjacency を形成すべきかどうかという判定が行なわれる (セクション 10.4 参照)。 point-to-point ネットワークや virtual link 上で adjacency を確立するために、 試みは常に行なわれる。adjacency を bring up する最初のステップは、 neighbor 同士のトポロジカルデータベースを同期させることである。これは次の セクションでカバーされる。 7.2 データベースの同期 link-state 型の経路制御アルゴリズムでは、全てのルータにとってトポロジカル データベースを同期させることは極めて重要である。OSPF では、adjacent な ルータだけが同期状態の維持を要求されることによって簡略化している。同期処理は ルータが adjacency の関係を bring up しようと試みたら直ちに開始される。 各ルータは neighbor に Database Description パケットのシーケンスを送信する ことによって自分自身のデータベースを記述する。Database Description パケットは それぞれ、ルータのデータベースに属する link-state 広告の集合を記述する。 neighbor は、自分のデータベースが持つコピーよりも新しい link-state 広告を 発見したなら、そのより新しい広告がリクエストされるべきだと書き留める。 この Database Description パケットの送受信を `データベース交換処理' と呼ぶ。 この処理中は 2 つのルータはマスタ/スレーブの関係を形成する。各 Database Description パケットはシーケンス番号を持つ。マスタによって送信される Database Description パケット (ポーリング) は、シーケンス番号のエコーによって ack が 返される。ポーリングとそのレスポンスは、link-state データのサマリを含む。 マスタだけが Database Description パケットを再送することを許されている。 ポーリングは固定されたインターバルでのみ実行される。インターバル長は設定 されている RxmtInterval である。 Database Description は、更にパケットが続くことを示す M-bit を含む。 データベース交換処理は、M-bit が off になった Database Description パケットを 受け取ると完了する。 データベース交換処理の最中および処理後、各ルータは neighbor が最新の事例を 持つような link-state 広告のリストを持つ。これらの広告は、Link State Request パケットによってリクエストされる。満足されない Link State Request パケットは RxmtInterval で定められたインターバルで再送される。Database Description 処理が完了し、Link State Request が全て満足されたら、データベースは同期した と見なされ、ルータは互いに adjacent であるとマークする。このとき adjacency の機能が完全に使えるようになり、2 つのルータの link-state 広告を広告する ようになる。 adjacency は Database Description 処理が始まるとすぐに flood 手続きで使用 される。こうしてデータベース同期は簡略化され、予想される時間内で終わることを 保証する。 7.3 Designated ルータ 全てのマルチアクセスネットワークは Designated ルータを持つ。 Designated ルータは経路制御プロトコルについて、主要な 2 つの機能を実行する。 o Designated ルータは、ネットワークに替わってネットワークリンク広告を 生成する。この広告は、現在ネットワークにアタッチされているルータ (これには Designated ルータ自身も含まれる) をリストする。この広告の Link State ID (セクション 12.1.4 参照) には Designated ルータのインタフェース IP アドレス が使用される。IP ネットワーク番号はサブネットマスク/ネットワークマスクを 用いることによって得られる。 o Designated ルータはネットワーク上の他の全ルータと adjacent になる。 データベースは adjacency を通して (adjacency の bring-up と flood 手続きを 通して) 同期されるので、Designated ルータは同期プロトコルの中心的部分を 担当する。 Designated ルータは Hello プロトコルによって選出される。ルータの Hello パケットは、そのルータのルータ優先度を含む。ルータ優先度はインタフェース毎に 設定することができる。一般に、はじめてネットワークへのインタフェースが functional になった場合、そのネットワークに現在 Designated ルータが存在するか どうかがチェックされる。既に Designated ルータが存在する場合は、 ルータ優先度に関わらず受け入れられる。(これは Designated ルータの同一性を 予想することを困難にするが、Designated ルータがそう頻繁には変更されないことを 保証する。後述)。Designated ルータが存在しない場合、もしそのルータが ネットワーク中で最も高いルータ優先度を持っているならば Designated ルータに なる。より詳細な (かつ、より正確な) Designated ルータ選出に関する記述は セクション 9.4 に延べられている。 Designated ルータは多くの adjacency の端点である。ブロードキャストネット ワークにおける flood 手続きを最適化するために、Designated ルータは自分の Link State Update パケットを各 adjacency にそれぞれ送信せず、アドレス AllSPFRouters にマルチキャストする。 本文書のセクション 2 でエリアの有向グラフ記述について論じている。 ルータノードは、各ルータのルータ ID でラベル付けされる。マルチアクセスネット ワークは実際には Designated ルータの IP アドレスでラベル付けされる。 当然、Designated ルータが変更されるとグラフのネットワークノードが新しいものに 置き換えられる。これにより、そのネットワークとネットワークにアタッチしている 全ルータは新しい link-state 広告を生成する。トポロジカルデータベースが もう一度収束するまで、接続性が一時的に断になることがあり得る。断になると データトラフィックのレスポンスとして ICMP unreachable メッセージが送信され 続けることになる。以上の理由により、Designated ルータの変更は最小限にする べきである。また、ルータ優先度は、ネットワークで最も信頼できるルータが Designated ルータになるように設定されるべきである。 7.4 バックアップ Designated ルータ 新しい Designated ルータへの移行をスムーズに行なうために、各マルチアクセス ネットワークにはバックアップ Designated ルータが存在する。バックアップ Designated ルータもまたネットワーク上の全ルータと adjacent であり、以前に 動作していた Designated ルータに障害が発生すると Designated ルータになる。 もしバックアップ Designated ルータが存在しない場合、新しい Designated ルータ が必要になったとき、新しい Designated ルータとネットワークにアタッチしている 全ルータの間で新たに adjacency を形成しなければならない。adjacency 形成 処理の一部にトポロジカルデータベースの同期があるが、これは潜在的に 長時間を要し得る。その間はネットワークはデータトラフィックの transit には 使用できない。バックアップ Designated ルータはこの adjacency 形成を不要に する。なぜなら、それらは既に存在するからである。これは、transit データ トラフィックの中断時間を新しい link-state 広告を flood するだけの時間に することを意味する。(このアナウンスは新しい Designated ルータによって 行なわれる)。 バックアップ Designated ルータはネットワークに関するネットワークリンク広告を 生成しない。(もし生成するようにすれば、新しい Designated ルータへの移行は 更に早くなる。しかし、それはデータベースのサイズと Designated ルータが消失 した際の収束までの時間とのトレードオフになる)。 バックアップ Designated ルータもまた Hello プロトコルによって選出される。 各 Hello パケットはそれぞれ、ネットワークに対するバックアップ Designated ルータを指定するフィールドを持つ。 flood 手続きの幾つかのステップにおいて、バックアップ Designated ルータは パッシブな役割を演じ、Designated ルータにより多くの作業を行なわせる。 これによりローカルトラフィックの量を削減している。より詳細な情報については セクション 13.3 を参照のこと。 7.5 adjacency のグラフ adjacency は、2 つのルータが共通にインタフェースを持つネットワークに拘束 される。もし 2 つのルータが複数のネットワークにインタフェースを持つ場合は 複数の adjacency を持つことがある。 undirected グラフを形成することによって、adjacency をまとめたものを描く ことができる。頂点はルータから構成され、辺は 2 つのルータが adjacent な時 頂点間を結ぶ。adjacency のグラフは経路制御プロトコルのパケット、とりわけ Link State Update パケットの AS 内の流れを記述する。 共通のネットワークがマルチアクセスネットワークであるかどうかによって、 2 種類のグラフが考えられる。物理的な point-to-point ネットワークか virtual link によって接続されている 2 つのルータは、データベースが同期した 後に adjacency になる。マルチアクセスネットワークでは、Designated ルータと バックアップ Designated ルータ両方が、ネットワークにアタッチしている他の 全ルータと adjacent であり、全 adjacency に対して責任を持つ。 これらのグラフを図 10 に示す。ここではネットワーク N2 に対し、RT7 が Designated ルータ、RT3 がバックアップ Designated ルータであると仮定している。 バックアップ Designated ルータは flood 手続きの間、少ない、わずかな機能を 実行する (セクション 13.3 参照)。これがバックアップ Designated ルータ RT3 と 点線で接続されている理由である。 +---+ +---+ |RT1|------------|RT2| o---------------o +---+ N1 +---+ RT1 RT2 RT7 o---------+ +---+ +---+ +---+ /|\ | |RT7| |RT3| |RT4| / | \ | +---+ +---+ +---+ / | \ | | | | / | \ | +-----------------------+ RT5o RT6o oRT4 | | | N2 * * * | +---+ +---+ * * * | |RT5| |RT6| * * * | +---+ +---+ *** | o---------+ RT3 図 10: adjacency のグラフ 8. プロトコルパケットの処理 このセクションでは OSPF 経路制御プロトコルパケットの一般的な処理について 論ずる。ルータのトポロジカルデータベースが同期されていることが極めて重要で ある。そのため、経路制御プロトコルパケットは普通のデータパケットよりも 送受信時に優先的な処理がなされるべきである。 経路制御プロトコルパケットは adjacency に沿ってのみ送信される。(ただし、 adjacency を発見するために用いられる Hello パケットは例外である)。 これは virtual link を除く全経路制御プロトコルパケットが 1 IP ホップだけ 移動することを意味する。以後、各パケットのタイプについて、より詳しい情報と 特定のパケットタイプの処理を与えるセクションがリストされる。 8.1 プロトコルパケットの送信 ルータが経路制御プロトコルパケットを送信する際に、以下のような標準的 OSPF パケットヘッダのフィールドを埋める。ヘッダフォーマットの詳細については セクション A.3.1 を参照のこと。 バージョン番号 この仕様書に記述されるプロトコルの番号は 2 にセットされる。 パケットタイプ Link State Update や Hello パケットのような OSPF パケットのタイプ。 パケット長 標準的な OSPF パケットヘッダを含む、全 OSPF パケットの長さをバイトで 示す。 ルータ ID (パケットを生成している) ルータ自身の独自性を示すもの。 エリア ID パケットが送信されている OSPF のエリア。 チェックサム 64-bit の Authentication フィールドを除く OSPF パケット全体の、標準的な IP 16-bit の complement チェックサム。チェックサムはパケットを適切な 認証手続きに渡す前に計算される。 AuType と認証 OSPF パケットの交換はそれぞれ認証される。認証のタイプはプロトコルによって 割り当てられるもので、付録 D に記述されている。各 OSPF エリアそれぞれに ついて、異なる認証機構を用いることができる。64-bit の Authentication フィールドが適切な認証手続き (AuType によって決定される) によってセット される。この手続きは、送信パケット形成時に最後に呼び出されるべきである。 Authentication フィールドのセットはパケットの内容と Authentication キー (インタフェース毎に設定可能) によって決定される。 パケットの IP 送信先アドレスは以下のように選択される。物理的 point-to-point ネットワークの場合、IP 送信割きな常にアドレス AllSPFRouters にセットされる。 他の (virtual link を含む) 全ネットワークでは、OSPF パケットの大半は ユニキャストで送信される。すなわち、adjacency のもう片側に直接送信される。 この場合、IP 送信先アドレスは adjacency のもう片側に関係する、Neighbor IP アドレスになる (セクション 10 参照)。ブロードキャストネットワークでは ユニキャストで送信されないパケットが存在する。Hello パケットはマルチキャスト 送信先 AllSPFRouters に送信される。Designated ルータとバックアップ Designated ルータは共に Link State Update パケットと Link State Acknowledgment パケットを、マルチキャストアドレス AllSPFRouters に送信する。他の全ルータは Link State Update パケットと Link State Acknowledgment パケットを マルチキャストアドレス AllDRouters に送信する。 Link State Update の再送は `常に' ユニキャストで送信される。 IP 発信元アドレスは、送信するインタフェースの IP アドレスにセットされる べきである。unnumbered な point-to-point へのインタフェースは IP アドレスを 持たない。そのような場合、IP 発信元アドレスはルータが持つ他のアドレスのうち どれかにセットされるべきである。このため、ルータには少なくとも 1 つ IP アドレスが割り当てられなければならない [2]。ここで注意してほしいのは virtual link はほとんどの場合 unnumbered な point-to-point ネットワークと 同じように振る舞うが、IP インタフェースアドレスを持っている。これらは 経路表作成時に検出され、virtual link を通して送信する際に IP 発信元アドレス として使用される。 特定の OSPF パケットタイプのフォーマットについては、表 10 にリストされる セクションを参照のこと。 タイプ パケット名 詳細な解説のあるセクション ---------------------------------------------------------- 1 Hello セクション 9.5 2 Database description セクション 10.8 3 Link state request セクション 10.9 4 Link state update セクション 13.3 5 Link state ack セクション 13.5 表 10: OSPF プロトコルパケット転送に関する記述のあるセクション 8.2 プロトコルパケットの受信 プロトコルパケットが受信される際には、常に受信するルータのインタフェースに よってマークされる。virtual link が設定されているルータでは、どの インタフェースがパケットに関係しているのかが直ちには明らかにならないかも しれない。例えば、図 6 に描かれているルータ RT11 を考える。RT11 が ネットワーク N8 へのインタフェースで OSPF プロトコルパケットを受信したと すると、そのパケットはエリア 2 へのインタフェースに関するパケットかも しれないし、ルータ RT10 への virtual link (バックボーンの一部) に関する パケットかもしれない。以下では、初めにパケットは virtual link に関係しない と仮定することにする [3]。 パケットが IP レベルで受け取られるためには、たとえそれが OSPF の処理のために 送られてきたものであっても、幾つかのテストを通過しなければならない。 o IP チェックサムは正しくなければならない。 o パケットの IP 送信先アドレスは受信インタフェースの IP アドレスであるか、 IP マルチキャストアドレス AllSPFRouters、AllDRouters のどちらかでなければ ならない。 o IP プロトコルは OSPF (89) に指定されていなければならない。 o ローカルに生成されたパケットは OSPF へと通過させるべきではない。発信元 IP アドレスがチェックされ、マルチキャストパケットではなく、ルータ自身が 生成したものでないことを確認すべきである。 次に OSPF パケットヘッダが検証される。ヘッダで指定されるフィールドは インタフェースの受信に関して以下の設定とマッチしなければならない。 マッチしない場合、パケットは破棄されるべきである。 o バージョン番号フィールドはプロトコルバージョン 2 に指定されなければ ならない。 o 16-bit の OSPF パケット内容の complement チェックサムが検証されなければ ならない。64-bit の Authentication フィールドはチェックサムの計算から 外されなければならないことを思い出してほしい。 o OSPF ヘッダ内にある全てのエリア ID は検証されなければならない。以下の どちらの場合にも当てはまらない場合、そのパケットは破棄されるべきである。 ヘッダで指定されるエリア ID は、以下のどちらかでなければならない。 (1) 受信インタフェースのエリア ID と一致する。その場合、パケットは 1 ホップ前から送信されている。したがってパケットの IP 発信元アドレスは 受信インタフェースと同じネットワークでなければならない。 これは、IP 発信元アドレスと受信インタフェースアドレス双方に インタフェースのマスクでマスク処理をした後に比較することで判定できる。 この比較は point-to-point ネットワークでは行なうべきではない。 point-to-point ネットワークでアドレスが割り当てられている場合、それは それぞれ独立して割り当てられているかもしれないからである。 (2) バックボーンを示している。この場合、パケットは virtual link を経由して 送信されている。受信ルータはエリアボーダルータでなければならず、 パケット内で指定されるルータ ID (発信元ルータ) は、virtual link の もう片側のものでなければならない。受信インタフェースは、virtual link の transit エリアとして設定されているエリアにアタッチしていなければ ならない。全てのチェックが無事に通過すると、パケットは受理され、 virtual link (とバックボーンエリア) に関係するものとなる。 o IP 送信先が AllDRouters のパケットは、受信インタフェースの状態が DR か Backup の場合には受理するだけにすべきである (セクション 9.1 参照)。 o パケット内で指定される AuType は関係するエリアに対して指定される AuType に マッチしなければならない。 次に、パケットは認証されなければならない。これは指定される AuType に依存 する (付録 D 参照)。認証手続きでは Authentication キーを使うことができる。 Authentication キーはインタフェース毎に設定することができる。認証が失敗した 場合には、そのパケットは破棄されるべきである。 パケットのタイプが Hello の場合、そのパケットは Hello プロトコルによって 更に処理されるべきである (セクション 10.5 参照)。他の全パケットタイプは adjacency によってのみ送信/受信される。これは、パケットはルータの active な neighbor の 1 つから発信されていなければならないことを意味する。 受信インタフェースがマルチアクセスネットワーク (ブロードキャストか ノン・ブロードキャストのどちらか) である場合、発信者はパケットの IP ヘッダ 内の IP 発信元アドレスによって識別される。受信インタフェースが point-to-point リンクや virtual link の場合、発信者はパケットの OSPF ヘッダ内の ルータ ID (発信元ルータ) によって識別される。受信インタフェースに関するデータ構造体は active neighbor のリストを含む。どの active neighbor ともマッチしない パケットは破棄されるべきである。 この時点で、受信されたプロトコルパケットは全て active neighbor に関係する。 特殊なパケットタイプの入力処理については表 11 にリストされるセクションを 参照のこと。 タイプ パケット名 詳細な解説のあるセクション ---------------------------------------------------------- 1 Hello セクション 9.5 2 Database description セクション 10.6 3 Link state request セクション 10.7 4 Link state update セクション 13 5 Link state ack セクション 13.7 表 11: OSPF プロトコルパケット受理に関する記述のあるセクション 9. インタフェースのデータ構造体 OSPF のインタフェースは、ルータとネットワークの接続である。アタッチしている ネットワーク毎にそれぞれ OSPF インタフェースデータ構造体が存在する。 各インタフェース構造体は、多くて 1 つの IP インタフェースアドレスを持つ。 (後述)。1 つのネットワークに対する複数アドレスのサポートは将来の検討事項 である。 OSPF インタフェースは、アタッチしているネットワークを含むエリアに属していると 考えることができる。ルータのインタフェースから生成される全経路制御プロトコル パケットは、インタフェースのエリア ID でラベル付けされる。1 つ以上の ルータの adjacency は 1 つのインタフェースを通して形成し得る。ルータの link-state 広告はインタフェースの状態と、関連する adjacency を反映する。 以下の項目はインタフェースに関するものである。項目の数は、アタッチされた ネットワークに対する実際の設定であることに注意してほしい。つまり、 ネットワークに接続された全てのルータは同じ項目を持っていなければならない。 タイプ インタフェースがアタッチしているネットワークの種類。値はブロードキャスト またはノン・ブロードキャストであり、マルチアクセスや point-to-point、 virtual link ではない。 状態 インタフェースの functional レベル。状態は、そのインタフェースを通して full adjacency の形成が許されているかどうかを決定する。状態は、ルータの link-state 広告も反映している。 IP インタフェースアドレス インタフェースに関係する IP アドレス。この値は、インタフェースが生成した 全ての経路制御プロトコルパケット内の IP 発信元アドレスに記述される。 unnumbered な point-to-point ネットワークへのインタフェースは関連する IP アドレスを持たない。 IP インタフェースマスク サブネットマスクとしても扱われるもの。IP インタフェースアドレスのうち、 アタッチされているネットワークを識別する部分を示すもの。IP インタフェース アドレスを IP インタフェースマスクでマスクすることにより、アタッチ されているネットワークの IP ネットワーク番号が得られる。point-to-point ネットワークと virtual link では、IP インタフェースマスクは定義されて いない。そのようなネットワークでは、リンク自体に IP ネットワーク番号が 割り当てられていない。両端がアドレスを持つとしても、その値はそれぞれ 独立に割り当てられている。 エリア ID アタッチされているネットワークが属するエリアのエリア ID。インタフェース から生成される全てのプロトコルパケットは、エリア ID でラベル付けされる。 HelloInterval ルータがインタフェースから Hello パケットを送信する間隔を秒で表す。 この値は、このインタフェースから送信される Hello パケット内で広告される。 RouterDeadInterval ルータの neighbor が Hello パケットを聞くことを止めた場合、そのルータが ダウンしていると宣言するまでの秒数。この値は、このインタフェースから 送信される Hello パケット内で広告される。 InfTransDelay Link State Update パケットをこのインタフェースから送信する時に要する 時間を評価したものを秒で表したもの。Link State Update パケットに 含まれる link-state 広告は、送信前にこの値を増やされた age を持つ。 この値は転送と伝播の遅延を考慮に入れるべきで、0 より大きい値でなければ ならない。 ルータ優先度 8-bit の unsigned な整数。ネットワークにアタッチしている 2 つのルータが 共に Designated ルータになろうと試みたとき、より高いルータ優先度を持つ 方が優先される。ルータ優先度が 0 のルータはアタッチされたネットワークの Designated ルータになる資格を持たない。この値は、このインタフェースから 送信される Hello パケット内で広告される。 Hello タイマ インタフェースに Hello パケットを送信させるインターバルタイマ。 このタイマは毎 HelloInterval 秒毎に発火する。ノン・ブロードキャスト ネットワークでは、各 neighbor に対して独立した Hello パケットが 送信されることに注意してほしい。 ウエイトタイマ インタフェースに Waiting 状態を脱出させ、ネットワーク上の Designated ルータを選択させる single shot タイマ。タイマの長さは RouterDeadInterval 秒である。 neighbor ルータのリスト ネットワークにアタッチされている、他のルータ。マルチアクセスネットワーク では、このリストは Hello プロトコルによって形成される。この neighbor の 中の幾つかと adjacency を形成することになる。adjacent な neighbor の 集合は、neighbor の状態を試験することによって決定することができる。 Designated ルータ アタッチされているネットワークに対して選択されている Designated ルータ。 全てのマルチアクセスネットワークでは、Hello プロトコルによって Designated ルータが選択される。Designated ルータに対して、2 つの identification、すなわち、ルータ ID と IP インタフェースアドレス が 保持される。Designated ルータはネットワークに対する link-state を 広告する。このネットワーク link-state 広告は Designated ルータの IP アドレスでラベル付けされる。Designated ルータ (この値) は 0.0.0.0 で 初期化される。これは Designated ルータがいないことを示す。 バックアップ Designated ルータ バックアップ Designated ルータもまた、マルチアクセスネットワークでは Hello プロトコルによって選択される。ネットワークにアタッチされている 全ルータは Designated ルータ、バックアップ Designated ルータ両方と adjacent になる。バックアップ Designated ルータは、現在の Designated ルータに障害が発生した場合、Designated ルータになる。バックアップ Designated ルータ (この値) は 0.0.0.0 で初期化される。これはバックアップ Designated ルータがいないことを示す。 インタフェース出力コスト インタフェースからデータパケットを送信するコストで、link-state メトリック で表現される。この値はルータのリンク広告内で、このインタフェースの リンクコストという形で広告される。各 IP Type of Service それぞれについて 独立したコストが存在できる。インタフェースのコストは 0 より大きい値で なければならない。 RxmtInterval このインタフェースに属する adjacency に対して、link-state 広告を 再送するまでの間隔を秒で表したもの。この値は、Database Description パケットや Link State Request パケットを再送する際にも用いられる。 Authentication キー この設定されたデータによって、OSPF ヘッダの Authentication フィールドの 値を生成/検証する認証手続きが可能になる。Authentication キーは インタフェース毎に設定することができる。例えば、AuType が simple password を示しているなら、Authentication キーは 64bit のパスワードになる。 経路制御プロトコルが生成される際には、このキーは直接 OSPF ヘッダ内に 挿入される。各ネットワーク毎に独立したパスワードを設定することもできる。 9.1 インタフェースの状態 ルータのインタフェースの様々な状態について、このセクションで記述する。 状態は機能が進行していく順番でリストされている。例えば、操作できない状態が 最初にリストされ、その後に中間的な状態が続き、完全に functional な状態が 達成される。本仕様書では、この順序に関して、`状態が X よりも上位な インタフェース' といった扱い方をする。図 11 はインタフェースの状態遷移を グラフ化したものを示している。グラフの弧は状態遷移を引き起こすイベントで ラベル付けされる。これらのイベントについてはセクション 9.2 で述べられている。 インタフェース状態マシンについてはセクション 9.3 で詳細に述べられている。 +----+ UnloopInd +--------+ |Down|<--------------|Loopback| +----+ +--------+ | |InterfaceUp +-------+ | +--------------+ |Waiting|<-+-------------->|Point-to-point| +-------+ +--------------+ | WaitTimer|BackupSeen | | | NeighborChange +------+ +-+<---------------- +-------+ |Backup|<----------|?|----------------->|DROther| +------+---------->+-+<-----+ +-------+ Neighbor | | Change | |Neighbor | |Change | +--+ +---->|DR| +--+ 図 11: インタフェース状態の遷移 この状態遷移図に補則すると、イベント InterfaceDown は 常に強制的に Down 状態にする。LoopInd は強制的に Loopback 状態にするものである。 Down これがインタフェース状態の初期状態である。この状態の場合、低階層の プロトコルはこのインタフェースは使用できないと表示する。この状態の インタフェースはプロトコルトラフィックを全く送受信しない。 インタフェースの変数は全て初期値にセットされるべきである。 インタフェースタイマは全て無効になっているべきであり、このインタフェース に関して adjacency が存在すべきではない。 Loopback この状態では、ルータのネットワークへのインタフェースはループバックに なっている。インタフェースのループバックはハードウェア的もしくは ソフトウェア的に行なわれる。この状態のインタフェースは通常のデータ トラフィックに対しては使用されない。しかし、このインタフェースの品質に 関する情報を ICMP ping をインタフェースに送信するか、ビットエラーテスト のようなことを行なって得られることが望ましい。このため、IP パケットは Loopback 状態のインタフェースへと送られることがある。これを促進する ために、Loopback 状態のインタフェースはルータリンク広告の中で、 送信先が IP インタフェースアドレスであるような 1 つのホストルートとして 広告される [4]。 Waiting この状態では、ルータは (バックアップ) Designated ルータの存在を判定 しようと試みている。これを実行するため、ルータは受信した Hello パケットを モニタする。ルータは Waiting 状態から先に進むまではバックアップ Designated ルータも Designated ルータも選出することができない。 これにより、不必要な (バックアップ) Designated ルータの変化を防ぐことが できる。 Point-to-point この状態では、インタフェースはオペレーショナルであり、物理的な point-to-point ネットワークか virtual link のどちらかに接続している。 この状態に遷移する際に、ルータは neibor なルータと adjacency を 形成しようと試みる。Hello パケットは、毎 HelloInterval 秒毎に neighbor に 送信される。 DR Other インタフェースが、既に Designated ルータが選択されているマルチアクセス ネットワークへのものであることを示す。この状態の場合、ルータ自身は バックアップ Designated ルータにも選択されていない。このルータは Designated ルータと、(もし存在すれば) バックアップ Designated ルータと それぞれ adjacency を形成する。 Backup この状態では、ルータ自身がアタッチされているネットワークのバックアップ Designated ルータになっている。現在の Designated ルータに障害が発生 した場合、このルータは Designated ルータに昇格する。このルータは ネットワークにアタッチされている全ルータと adjacency を形成する。 バックアップ Designated ルータは flood 手続きの際に Designated ルータと 比較してわずかに異なる機能を実行する (セクション 13.3 参照)。バックアップ Designated ルータによって実行される機能の詳細はセクション 7.4 を参照 のこと。 DR この状態では、ルータ自身がアタッチされているネットワークの Designated ルータになっている。ネットワークにアタッチされている他の全ルータと adjacency が確立されている。このルータはネットワークノードに向けて ネットワークリンク広告を生成しなければならない。広告にはネットワークに アタッチされている全ルータ (Designated ルータ自身を含む) へのリンクが 含まれる。Designated ルータによって実行される機能の詳細はセクション 7.3 を参照のこと。 9.2 インタフェース状態を遷移させるイベント 状態遷移は数多くのイベントに影響される。これらのイベントは、図 11 において ラベル付けされた弧として描かれている。ラベルの定義は以下にリストされる。 OSPF プロトコルにおける、これらのイベントの効果の詳細についてはセクション 9.3 を参照のこと。 InterfaceUp 低階層のプロトコルは、ネットワークインタフェースがオペレーショナルで あると表示する。このイベントはインタフェースを Down 状態から 抜け出させる。virtual link においては、実際には shortest-path 計算の後に インタフェースがオペレーショナルであると表示する (セクション 16.7 参照)。 WaitTimer ウエイトタイマが発火している。すなわち、(バックアップ) Designated ルータが選出されるまでに必要とされる待ち時間が終わったことを示す。 BackupSeen ルータはネットワークに対するバックアップ Designated ルータが存在して いるかどうかを判定している。これは 2 通りの方法のうちの 1 つによって 実行される。1 つめは自分がバックアップ Designated ルータであると主張 している neighbor からの Hello パケットを受け取ることである。もう 1 つは 自分が Designated ルータであると主張している neighbor からの Hello パケットを受け取ることで、これはバックアップ Designated ルータが存在 しないことを示している。どちらの場合においても、neighbor とは双方向の 通信が行なわれなければならない。すなわち、このルータは neighbor の Hello パケットの中にいなければならない。このイベントは Waiting 状態の 終わりを告げるものである。 NeighborChange インタフェースに関する双方向な neighbor の集合が変化している。 (バックアップ) Designated ルータは再計算をしなければならない。以下に示す ような neighbor の変化は NeighborChange イベントを発生させる。 neighbor の状態についてはセクション 10.1 を参照のこと。 o 双方向の通信が neighbor との間に確立されている。換言すると、neighbor の 状態が 2-Way か、それよりも高位に遷移している。 o neighbor と双方向の通信ができない。換言すると、neighbor の状態が Init か、それよりも低位に遷移している。 o 双方向に通信している neighbor が、新たに自分を Designated ルータ、 もしくはバックアップ Designated ルータであると宣言した。これは neighbor の Hello パケットを試験することにより検出される。 o 双方向に通信している neighbor が、自分が Designated ルータ、もしくは バックアップ Designated ルータであると宣言しなくなった。これもまた neighbor の Hello パケットを試験することにより検出される。 o 双方向に通信しているルータの、広告されているルータ優先度が変化した。 これもまた neighbor の Hello パケットを試験することにより検出される。 9.3 インタフェース状態マシン 以下に、インタフェース状態遷移の詳細について記述する。各状態遷移はイベントに よって発生する (セクション 9.2 参照)。このイベントはインタフェースの状態に 応じて異なる効果を発揮する。このため、現在のインタフェースの状態と受信した イベントから下記のような状態マシンが作られる。状態マシンの各エントリは 結果として得られる新しいインタフェース状態と、必要とされるアクションを 記述する。 インタフェース状態が変化する際に、新たにルータリンク広告を生成しなければ ならない場合がある。詳細についてはセクション 12.4 を参照のこと。 以下に示す必要とされるアクションは neighbor 状態マシンに対するイベントを 生成する。例えば、インタフェースが操作できなくなったとき、その インタフェースに関する neighbor との接続は全て消失してしまう。 neighbor 状態マシンに関する詳細な情報についてはセクション 10.3 参照のこと。 状態 : Down イベント : InterfaceUp 新しい状態: アクションルーチンに依存する。 アクション: インターバル Hello タイマをスタートし、そのインタフェースから Hello パケットを周期的に送信できるようにする。アタッチしている ネットワークが物理的な point-to-point ネットワークか virtual link である場合、インタフェース状態は Point-to-point に遷移する。 そうでない場合、ルータが Designated ルータになることに適して いなければ、インタフェース状態は DR Other に遷移する。 そうでもないなら、アタッチしているネットワークがマルチアクセス ネットワークであり、ルータは Designated ルータになる資格を持つ。 この場合、Designated ルータを検出しようと試みるので、 インタフェースの状態は Waiting にセットされ、single shot ウエイトタイマがスタートされる。更に、アタッチされている ネットワークがノン・ブロードキャストの場合、このインタフェースに 関して設定されている neighbor のリストを試験し、Designated ルータになる資格を持つ neighbor に対し、それぞれ neighbor イベント Start を生成する。 状態 : Waiting イベント : BackupSeen 新しい状態: アクションルーチンに依存する。 アクション: セクション 9.4 で示したように、アタッチされているネットワークに 対するバックアップ Designated ルータと Designated ルータを 計算する。この計算の結果、インタフェースの新しい状態は DR Other、 Backup、DR のどれかになる。 状態 : Waiting イベント : WaitTimer 新しい状態: アクションルーチンに依存する。 アクション: セクション 9.4 で示したように、アタッチされているネットワークに 対するバックアップ Designated ルータと Designated ルータを 計算する。この計算の結果、インタフェースの新しい状態は DR Other、 Backup、DR のどれかになる。 状態 : DR Other、Backup、DR イベント : NeighborChange 新しい状態: アクションルーチンに依存する。 アクション: セクション 9.4 で示したように、アタッチされているネットワークに 対するバックアップ Designated ルータと Designated ルータを 再計算する。この計算の結果、インタフェースの新しい状態は DR Other、Backup、DR のどれかになる。 状態 : 任意の状態 イベント : InterfaceDown 新しい状態: Down アクション: 全てのインタフェース変数はリセットされ、インタフェースのタイマは 無効になる。また、このインタフェースに関する全ての neighbor との 接続は消失する。これは関係する全 neighbor に向けて、イベント KillNbr を生成することで実行される (セクション 10.2 参照)。 状態 : 任意の状態 イベント : LoopInd 新しい状態: Loopback アクション: このインタフェースはアタッチされているネットワークには接続されて いないので、上述の InterfaceDown イベントが実行される。 状態 : Loopback イベント : UnloopInd 新しい状態: Down アクション: アクションは何も必要ではない。例えば、インタフェース変数は Loopback 状態に入る際に既にリセットされている。インタフェースが 再び functional になるまでには、InterfaceUp イベントを受理する 必要があることに注意してほしい。 9.4 Designated ルータの選出 このセクションでは、ネットワークの Designated ルータ、バックアップ Designated ルータを計算する際に用いられるアルゴリズムについて記述する。 このアルゴリズムは、インタフェース状態マシンによって発動される。ルータが ネットワークに対するアルゴリズムを動作させる初期状態では、Designated ルータと バックアップ Designated ルータは 0.0.0.0 に初期化される。これは、Designated ルータとバックアップ Designated ルータが共に存在していないことを示す。 Designated ルータ選出アルゴリズムは、以下のように進行する。計算を行なっている ルータをルータ X と呼ぶ。ネットワークにアタッチされており、ルータ X と双方向 の通信を行なっている neighbor のリストが試験される。このリストは (このネットワーク上の)、ルータ X の neighbor であり、その状態が 2-Way か それより上位のものを収集したものである (セクション 10.1 参照)。ルータ X 自身 そのリストに含まれると考えられる。次に、リストから Designated ルータになる 資格を持たないものを削除する。(ルータ優先度が 0 のルータは Designated ルータになる資格を持たない)。リストに残ってるルータに対してのみ、以下の ステップが実行される。 (1) ネットワークの Designated ルータとバックアップ Designated ルータに 関する現在の値を記録する。このデータは後ほど比較に用いられる。 (2) 以下のように、ネットワークに対する新しいバックアップ Designated ルータを 計算する。リスト中の、Designated ルータであると宣言していないルータ だけがバックアップ Designated ルータになる資格がある。1 つかそれ以上の ルータが自分自身をバックアップ Designated ルータであると宣言している 場合 (すなわち、そのルータ達が生成する Hello パケット内で自分自身を Designated ルータではなく、バックアップ Designated ルータとしてリスト している場合)、より高いルータ優先度を持つものがバックアップ Designated ルータであると宣言される。ルータ優先度が等しい場合は、より大きな値の ルータ ID を持つものが選択される。どのルータも自分自身をバックアップ Designated ルータであると宣言していない場合、最も高いルータ優先度を 持つものが選択される (繰り返すが、自分自身を Designated ルータであると 宣言しているものは除外される)。また、ルータ ID が均衡を破るために 用いられる。 (3) 以下のように、ネットワークに対する新しい Designated ルータを計算する。 1 つかそれ以上のルータが自分自身を Designated ルータであると宣言 している場合 (すなわち、そのルータ達が生成する Hello パケット内で 自分自身を Designated ルータとしてリストしている場合)、より高い ルータ優先度を持つものが Designated ルータであると宣言される。 ルータ優先度が等しい場合は、より大きな値のルータ ID を持つものが 選択される。どのルータも自分自身を Designated ルータであると宣言して いない場合、新しくバックアップ Designated ルータを選出したのと同じ方法で Designated ルータが割り当てられる。 (4) ルータ X が新しい Designated ルータかバックアップ Designated ルータに なったか、あるいは Designated ルータにもバックアップ Designated ルータ にもなっていない場合、ステップ 2、3 を繰り返し、その後ステップ 5 に 進む。例えば、ルータ X が現在 Designated ルータになっている場合、 ステップ 2 が繰り返されたならルータ X はバックアップ Designated ルータに 選出される資格を持たない。このようにして、全てのルータが自分自身を バックアップ Designated ルータ、Designated ルータの両方であると宣言しない ことを保証している [5]。 (5) これらの計算の結果、ルータ自身は Designated ルータかバックアップ Designated ルータになるかもしれない。これに伴う付加的な義務については セクション 7.3、7.4 を参照のこと。ルータのインタフェース状態は状況に 応じてセットされるべきである。ルータ自身が現在 Designated ルータで あるなら、新しいインタフェース状態は DR になる。ルータ自身が現在 バックアップ Designated ルータであるなら、新しいインタフェース状態は Backup になる。どちらでもない場合、新しいインタフェース状態は DR Other に なる。 (6) アタッチされているネットワークがノン・ブロードキャストで、ルータ自身が Designated ルータかバックアップ Designated ルータになったなら、 Designated ルータになる資格を持たない neighbor に Hello パケットを送信 し始めなければならない (セクション 9.5.1 参照)。これは、ルータ優先度が 0 の neighbor に向けて、neighbor イベント Start を発行することによって 行なわれる。 (7) 上記の計算によって変更される Designated ルータもしくはバックアップ Designated ルータが識別された場合、このインタフェースに関する adjacency の集合は修正されなければならない。幾つかの adjacency を 形成しなくてはならず、その他の adjacency は関係が壊れる。これを達成する ため、状態が少なくとも 2-Way になっている全 neighbor に、イベント AdjOK? を発動する。これにより、全 neighbor の adjacency 適性が再試験される。 (セクション 10.3、10.4 参照)。 この選出アルゴリズムが複雑な理由は、現在の Designated ルータに障害が発生 した際に、規律正しくバックアップ Designated ルータから Designated ルータに 移行させる願望のためである。規律正しい移行は履歴現象 (hysteresis) の導入に よって保証される。すなわち、旧バックアップが新しい Designated ルータの 責任を受け入れるまで、新しいバックアップ Designated ルータは選択できない。 上記の手続きは、計算しているルータ (ルータ X) はそうならないとしても、 同じルータを Designated ルータ、バックアップ Designated ルータに選出 してしまうかもしれない。選出された Designated ルータは最も高いルータ優先度を 持つルータではないかもしれないし、バックアップ Designated ルータも 2 番目に 高いルータ優先度を持たないかもしれない。ルータ X 自身が Designated ルータに なる資格を持たないならば、上記の方法でバックアップ Designated ルータも Designated ルータも選択することはできない。ルータ X がネットワークにアタッチ している唯一の Designated ルータになる資格を持ったルータの場合、自分自身を Designated ルータとして選択し、バックアップ Designated ルータは存在しなく なる。 9.5 Hello パケットの送信 Hello パケットは functional なインタフェースからそれぞれ送信される。 Hello パケットは neighbor を発見し、関係を維持するために用いられる [6]。 マルチアクセスネットワークでは、Hello パケットは Designated ルータと バックアップ Designated ルータを選出するために用いられ、どの adjacency を 形成するかの判定にも用いられる。 Hello パケットのフォーマットはセクション A.3.2 に詳細が記されている。 Hello パケットはそのルータのルータ優先度 (Designated ルータ選択に用いられる) そのインタフェースから送信される Hello パケットのインターバル (HelloInterval) を含む。Hello パケットは neighbor が active であり続けるためにはどの頻度で Hello パケットを聞かなければならないか (RouterDeadInterval) を示す。 共通のネットワークにアタッチされている全ルータについて、HelloInterval と RouterDeadInterval は同じでなければならない。Hello パケットはアタッチされて いるネットワークの IP アドレスマスク (ネットワークマスク) を含む。 unnumbered な point-to-point ネットワークや virturl link では、この フィールドは 0.0.0.0 にセットされるべきである。 Hello パケットのオプションズフィールドには、ルータのオプショナルな OSPF 機能を記述する。現在、2 つのオプショナルな機能が定義されている。 (セクション 4.5、A.2 参照)。T-bit は、そのルータが各 IP TOS に対して 独立した経路を計算する機能がある場合にセットされるべきである。E-bit は アタッチされているエリアが AS external 広告を処理できる (すなわち、stub では ない) 場合にだけセットされるべきである。E-bit が誤ってセットされると、 neibor ルータは Hello パケットを拒否するようになる (セクション 10.5 参照)。 Hello パケットのオプションズフィールドの空き部分には 0 がセットされる べきである。 adjacent なルータ間の双方向通信を保証するため、Hello パケットは最近受信した Hello パケットを送信した全ルータのリストを含む。Hello パケットはまた、 現在選択されている Designated ルータとバックアップ Designated ルータを含む。 このフィールドの値が 0.0.0.0 なのは、未だに選択されていないことを意味する。 ブロードキャストネットワークと物理的な point-to-point ネットワークでは、 Hello パケットは HelloInterval 秒毎に IP マルチキャストアドレス AllSPFRouters に送信される。virtual link では、HelloInterval 秒毎に ユニキャストで送信される (virtual link のもう片側に直接宛てられる)。 ノン・ブロードキャストネットワークでは、Hello パケットの送信は より複雑である。これについては次のセクションでカバーされる。 9.5.1 ノン・ブロードキャストネットワーク上での Hello パケット送信 ノン・ブロードキャストネットワークにおいて Hello プロトコルの機能を提供する ためには、静的な設定情報が必要になる (セクション C.5 参照)。ネットワークに アタッチしている、Designated ルータになる資格を持った全ルータは、あらかじめ 設定されたネットワーク上の全 neighbor のリストを持つ。リストされたルータは それぞれ Designated ルータ適性によってラベル付けされる。 インタフェース状態は、送信されるべきいかなる Hello パケットに対しても、 少なくとも Waiting でなければならない。その後、Hello パケットはルータの neighbor の集合の一部に向けて (ユニキャストで) 送信される。ときには、 Hello パケットはタイマによって周期的に送信される。そうでない場合は受信した Hello パケットのレスポンスとして送信される。ルータの Hello パケット送信の 振る舞いは、そのルータ自身が Designated ルータになる資格を持つかどうかに 依存する。 ルータが Designated ルータになる資格を持つ場合は、Hello パケットは周期的に 他の Designated ルータの適性を持つ全 neighbor に送信されなければならない。 これは 2 つの適性を持ったルータは常に Hello パケットを交換していることを 意味する。これは Designated ルータ選出アルゴリズムが正しくオペレートされる ために必要である。Hello パケットの送信量を最小にするために、ノン・ブロード キャストネットワーク上の適性ルータの数は少量にとどめておくべきである。 ルータが Designated ルータになる資格を持たない場合、Hello パケットは Designated ルータとバックアップ Designated ルータ (存在していれば) の両方に 周期的に送信されなければならない。また、他の適性ルータ (現在の Designated ルータ、バックアップ Designated ルータは除く) から受信した Hello パケットの リプライとして Hello パケットを送信しなければならない。これは潜在的な Designated ルータと初期的な双方向の関係を確立するために必要とされる。 いかなる neighbor に周期的に Hello パケットを送信する場合でも、Hello パケットを送信するインターバルは neighbor の状態によって決定される。 neighbor の状態が Down の場合、Hello パケットは PollInterval 秒毎に送信 される。そうでない場合、Hello パケットは HelloInterval 秒毎に送信される。 10. neighbor のデータ構造体 OSPF ルータは、その neighbor ルータと会話している。独立した会話はそれぞれ 1 つの `neighbor のデータ構造体' によって記述される。各会話は特殊な OSPF ルータインタフェースに束縛される。また、neighbor ルータの OSPF ルータ ID か、Neighbor IP アドレスのどちらかによって識別される (後述)。 したがって、ある OSPF ルータが他のルータと複数の共通したネットワークに アタッチしている場合、複数の会話が発生し、それぞれが唯一の neighbor の データ構造体で記述される。本文書では、独立した会話それぞれをゆるやかに 独立した `neighbor' として扱う。 neighbor のデータ構造体は、2 つの neighbor の間で形成された adjacency に 関する情報と、これから adjacency を形成するために必要な情報を全て含む。 (しかし、全ての neighbor が adjacency になるわけではないことを思い出して ほしい)。adjacency は 2 つのルータ間の高度に発達した会話であると見ることが できる。 状態 neighbor との会話の functional レベル。セクション 10.1 で詳細に記述 される。 Inactivity タイマ single shot タイマで、発火することは、この neighbor からの Hello パケットを受信しなくなったことを示す。 Master/Slave 2 つの neighbor がデータベースを交換する場合、2 台のルータは master/slave の関係を形成する。master は最初の Database Description パケットを送信 する。このパケットだけが再送を許されている。slave は master の Database Description パケットに反応することしかできない。master/slave の 関係は、状態 ExStart で調整される。 DD シーケンス番号 個々の Database Description パケットを識別する 32-bit の数。neighbor の 状態が ExStart に入ると、DD シーケンス番号はその neighbor が今まで受信 していない値がセットされるべきである。考えられる構造としては、マシンの time of day カウンタを用いることである。DD シーケンス番号は新しい Database Description パケットを送信する毎に master によって増やされる。 1 度に 1 パケットだけしか outstanding を許されない。 Neighbor ID neighbor ルータの OSPF ルータ ID。Neighbor ID は Hello パケットを neighbor から受信した際に学習される。または virtual adjacency の場合は あらかじめ設定されている (セクション C.4 参照)。 Neighbor 優先度 neighbor ルータのルータ優先度。neighbor の Hello パケットに含まれている。 この項目は、アタッチされているネットワークに対する Designated ルータを 選択する際に用いられる。 Neighbor IP アドレス neighbor ルータのネットワークにアタッチしているインタフェースの IP アドレス。プロトコルパケットがユニキャストで、この adjacency を 通って送信される時、送信先 IP アドレスとして用いられる。 neighbor ルータが Designated ルータに選択されている場合は、この項目は ルータリンク広告内のリンク ID として用いられる (セクション 12.4.1 参照)。 Neighbor IP アドレスは neighbor から Hello パケットを受信した際に 学習される。virtual link の場合、Neighbor IP アドレスは経路表を構築 している間に学習される (セクション 15 参照)。 Neighbor オプション neighbor がサポートしている、オプショナルな OSPF 昨日。この項目は データベース交換処理の間に学習される (セクション 10.6 参照)。 neighbor のオプショナルな OSPF 機能は Hello パケット内にもリストされる。 こうすることにより、サポートする OSPF 機能に重大な違いがある場合には Hello パケットの受信を拒否 (すなわち、neighbor の関係形成すら開始 されない) することができる (セクション 10.5 参照)。オプショナルな OSPF 機能についてはセクション 4.5 に記述されている。 Neighbor の Designated ルータ neighbor の Designated ルータの認識。この項目が neighbor 自身である 場合、この項目は Designated ルータのローカルな計算において重要な ものである。マルチアクセスネットワークでだけ定義される。 Neighbor のバックアップ Designated ルータ neighbor のバックアップ Designated ルータの認識。この項目が neighbor 自身である場合、この項目はバックアップ Designated ルータのローカルな 計算において重要なものである。マルチアクセスネットワークでだけ定義 される。 次の変数の集合は、link-state 広告のリストである。これらのリストはエリアの トポロジカルデータベースのサブセットを記述する。1 つのエリアトポロジカル データベースの中には、5 つの異なるタイプの link-state 広告が存在し得る。 すなわち、ルータリンク、ネットワークリンク、Type 3 と Type 4 のサマリリンク、 (以上は全てエリアのデータ構造体に含まれる)、AS external リンク (グローバルなデータ構造体に含まれる) である。 link-state 再送リスト 既に flood されているが、adjacency から ack が返されていない link-state 広告のリスト。これらの内容は ack が返されるか、adjacency の関係が壊れる まで定期的に再送される。 データベースサマリリスト neighbor がデータベース交換状態に入った瞬間の、エリアのトポロジカル データベースを作成する link-state 広告の完全なリスト。このリストは Database Description パケットに載せられて neighbor に送信される。 link-state リクエストリスト トポロジカルデータベースを同期させるために、ここにリストされる neighbor からの link-state 広告が受信されなければならない。このリストは Database Description パケットを受信した際に作成され、Link State Request パケットに載せられて neighbor に送信される。このリストは適切な Link State Update パケットを受信した時に削除される。 10.1 neighbor の状態 neighbor の状態 (実際には、neighbor ルータと交わされている会話の状態) を この後のセクションで述べる。状態は機能が進行する順番にリストされる。例えば、 操作できない状態が最初にリストされ、その後に中間的な状態が続き、完全に functional な状態が達成される。本仕様書では、この順序に関して、`状態が X よりも上位な neighbor/adjacency' といった扱い方をする。図 12 と 13 は neighbor 状態の遷移をグラフで示したものである。グラフの弧は状態遷移を 引き起こすイベントでラベル付けされる。neighbor イベントについては セクション 10.2 で述べられる。 図 12 のグラフは Hello プロトコルに影響される状態遷移を示す。 Hello プロトコルは neighbor の獲得と維持に責任を持ち、neighbor 間で双方向の 通信を保証するものである。 +----+ |Down| +----+ | | Start | | +-------+ Hello | +------>|Attempt| Received | +-------+ | | +----+<-+ |HelloReceived |Init|<---------------+ +----+<--------+ | | |2-Way |1-Way |Received |Received | | +-------+ | +-----+ |ExStart|<--------+------->|2-Way| +-------+ +-----+ 図 12: neighbor の状態遷移 (Hello プロトコル) この状態遷移図に補則すると、イベント KillNbr は常に強制的に Down 状態にする。イベント InactivityTimer は常に強制的に Down 状態にする。イベント LLDown は常に強制的に Down 状態に する。 図 13 のグラフは adjacency の形成を示すものである。neighbor な 2 つのルータ 全てが adjacent にはならない (セクション 10.4 参照)。adjacency は neighbor の 状態が ExStart のときに形成され始める。2 つのルータが master/slave の状態を 見出すと、状態は Exchange へと遷移する。この時点で neighbor は flood 手続き に使用されるようになり、neighbor な 2 つのルータはデータベースの同期を 開始する。同期が完了すると neighbor は状態 Full になり、2 つのルータが 完全に adjacent になったと言える。この時点で adjacency は link-state 広告に リストされる。 neighbor のより詳細な状態遷移に関する記述と、各遷移における付加的な アクションについては、セクション 10.3 を参照のこと。 +-------+ |ExStart| +-------+ | NegotiationDone| +->+--------+ |Exchange| +--+--------+ | Exchange| Done | +----+ | +-------+ |Full|<---------+----->|Loading| +----+<-+ +-------+ | LoadingDone | +------------------+ 図 13: neighbor の状態遷移 (Database Exchange) この状態遷移図に補則すると、 イベント SeqNumberMismatch は強制的に ExStart 状態にする。 イベント BadLSReq は強制的に ExStart 状態にする。 イベント 1-Way は強制的に Init 状態にする。 イベント KillNbr は常に強制的に Down 状態にする。 イベント InactivityTimer は常に強制的に Down 状態にする。 イベント LLDown は常に強制的に Down 状態にする。 イベント AdjOK? は adjacency 形成/破棄に誘導する。 Down この状態は、neighbor の会話の初期状態である。neighbor からは最新の 情報を受信していないことを意味する。ノン・ブロードキャストネットワーク では、その頻度は少なくはなるが、"Down" 状態の neighbor にも Hello パケットが送信されるかもしれない (セクション 9.5.1 参照)。 Attempt この状態はノン・ブロードキャストネットワークにアタッチしている neighbor に関してのみ有効である。neighbor から最新の情報を受信していないが、 neighbor にコンタクトを取るために申し合わされた努力がなされるべきことを 意味している。これは、HelloInterval の間隔で Hello パケットを neighbor に 送信することによってなされる (セクション 9.5.1 参照)。 Init この状態では、neighbor からの Hello パケットを最近受信している。 しかし、その neighbor とは双方向の通信は確立していない。(すなわち、その ルータは neighbor の Hello パケット内に含まれていない)。この状態 (もしくはより高位の) neighbor は全て関連するインタフェースから送信される Hello パケットにリストされる。 2-Way この状態では、2 つのルータ間の通信は双方向である。これは Hello プロトコルのオペレーションによって保証される。この状態は、adjacency の 確立をはじめる前では最も進んだ状態である。(バックアップ) Designated ルータは 2-Way か、それよりも高位の状態にある neighbor の集合から選出 される。 ExStart この状態は 2 つの neighbor なルータ間で adjacency を形成する最初の段階 である。この段階のゴールはどちらのルータが master かを決定し、 DD シーケンス番号の初期値を決定することである。この状態もしくはより高位の neighbor 間の会話を adjacency と呼ぶ。 Exchange この状態では、ルータは Database Description パケットを neighbor に送信 することによって、自分自身の完全な link-state データベースを記述する。 各 Database Description パケットは DD シーケンス番号を持ち、全て陽に ack が返される。いかなる場合においても、一度に 1 つの Database Description パケットだけが outstanding することを許される。 この状態では、Link State Request パケットも送信され、neighbor のより 最新の広告が無いかどうかが問い合わされる。Exchange 状態もしくはより高位な 状態にある adjacency は全て flood 手続きに使用される。実際、これらの adjacency は、全種類の OSPF 経路制御プロトコルパケットを送受信する能力を 持っている。 Loading この状態では、Link State Request パケットが neighbor に送信され、 Exchange 状態でより新しい広告を見つけていないか (そして、それがまだ 受信されていないか) が問い合わされる。 Full この状態は neighbor なルータが完全に adjacent になっている。 これらの adjacency はルータリンク広告、ネットワークリンク広告に 現れる。