JP2007288464A - ネットワークのルーティング方式 - Google Patents

Abstract

【課題】ネットワーク間の通信経路に障害等が発生した場合、系に混乱を与えることなく適切な経路を確保する。
【解決手段】各ルータは、ＲＰＭパケットを全てのルータに転送し、ＲＰＭパケットが経由したルータを当該パケットに記録し、このパケットに自身のルータの記録があればこれを転送せずに廃棄する。ネットワーク構成情報から障害を判断したときに「ネットワーク状態通知パケット」で各ルータに通知する。ネットワーク正常の場合はスタティックルーティングを行い、ネットワーク異常の場合はダイナミックルーティングに切り替える。スタティックルーティングで、ルートスキャンパケットを転送して中継経路を検査し、無効なパスを発見したときに代替経路で有効なものに一斉に変更する。ネットワークの障害が回復した場合にデフォルトルーティングテーブルによる経路制御に戻る。
【選択図】図１

Description

本発明は、ルータあるいはＬ３（レイヤ３）スイッチによるネットワークのルーティング方式に関する。

ネットワーク間でパケットの中継経路を制御する「ルーティング」には、事前に設定された固定の経路に基づいて中継を行なう「スタティックルーティング」と、ルータ間での経路情報のやり取りで決定された経路に基づいて中継を行なう「ダイナミックルーティング」があり、環境やユーザの都合でどちらかが選択されて運用される。

ダイナミックルーティングには幾つかの方法があるが、イーサネット（登録商標）等の非同期ネットワークにおけるルーティングとしては、もっぱらＲＩＰ（Routing Information Protocol），ＯＳＰＦ（Open Shortest Path First）などのルーティングプロトコルが使用される。ＲＩＰは、経路を構成するルータ数（ホップ数）に従って最短経路を動的に決定する。ＯＳＰＦは、伝送帯域をもパラメータとして階層化したルーティングが可能になり、通信障害等が発生したときに、新たな通信経路を検索してその確保が可能となる（例えば、特許文献１参照）。
特開２００２−３７４２９２号公報

スタティックルーティングは、ユーザが設定した経路に忠実に従ってパケットの中継が行なわれるため、ルーティングは安定する。しかし、ネットワークに障害が発生しても自力でこれを迂回することはできない。意図しない経路が組まれることを嫌ってスタティックルーティングを選択するユーザもいるが、これではダイナミックルーティングの恩恵を受けることができない。

しかし、ダイナミックルーティングには一般に以下のような欠点がある。

（１）ルーティングによって決定した経路がユーザの想定からかけ離れたものになる可能性がある。

（２）誤ったルーティング情報によって系が混乱に陥るおそれがある。

例えば、ＲＩＰを使った場合、転送経路はホップ数を元に計算されるため、回線速度などを考慮した経路を構築させるのには困難が伴う（ＲＩＰではホップ数の上限が小さいため、ホップ数の重み付けで対応するのも難しい）。

また、（２）については、場合によってはループ発生の原因にもなるので重大な問題を引き起こすおそれがある。

本発明の目的は、通信経路に障害等が発生した場合、系に混乱を与えることなく適切な経路を確保できるネットワークのルーティング方式を提供することにある。

前記の課題を解決するための本発明は、以下の構成を特徴とする。

（１）ルータ（あるいはレイヤ３スイッチ）により、ネットワーク間でパケットの中継経路を制御するルーティング方式であって、
各ルータは、ネットワークのルーティングを行なうためのプロトコルを搭載し、経路の管理情報をルータ間で通知し合うＲＰＭ（ルーティング・プロトコル・マネジメント）パケットを用意し、前記ＲＰＭパケットは、ＲＰＭの管理情報のメッセージと、経由したルータのアドレステーブルとを有し、
前記各ルータは、前記ＲＰＭパケットをネットワーク中の全てのルータに転送するルータキャストには、ＲＰＭパケットが経由したルータを当該パケットに記録し、このパケットを受信したルータが当該パケットに記録された経由ルータの記録を参照し、自身の記録があればこれを転送せずに廃棄するパケット転送手段を備えたことを特徴とする。

（２）前記ルータは、
接続されているべき隣接ルータ、接続されているべきインタフェース、および、そのリンクの状態を記録するテーブルを持つネットワーク構成情報を常時監視し、一部でも問題があればネットワーク障害を判断する手段と、
前記ネットワークの障害を判断したときに「ネットワーク状態通知パケット」でネットワーク中の各ルータに通知する手段と、
ネットワーク正常の場合はスタティックルーティングを行い、ネットワーク異常の場合はダイナミックルーティングに切り替える手段とを備えたことを特徴とする。

（３）前記ルータは、
複数のスタティックルーティングテーブルを設け、各スタティックルーティングテーブルにはネットワーク全体で統一するためのＩＤを割り当てる手段と、
スタティックルーティングの開始で、ルートスキャンパケットを転送して任意のＩＤのルーティングテーブルによる中継経路を検査する手段と、
前記中継経路の検査結果に無効なパスを発見したときに、代替経路で有効なものを探し出し、「ルート変更パケット」を転送してルーティングテーブルをそのシリーズにするように系全体に要求する手段と、
前記ルート変更要求された他のルータがそのルーティングテーブルを調査し、問題があった場合にその要求に対して拒否をする手段と、
前記ルート変更要求に対して拒否がなかった場合に、系全体のルーティングテーブルを一斉に変更する手段とを備えたことを特徴とする。

（４）前記ルータは、前記ルーティングテーブルが変更された後、ネットワークの障害が回復した場合にデフォルトルーティングテーブルによる経路制御に戻る手段を備えたことを特徴とする。

以上のとおり、本発明によれば、経由ルータをパケットに記録してゆくことにより、一度受信したことのあるパケットをルータが転送しなくなるため、無駄なパケット巡回を最小限に抑えながら、ネットワーク中のルータにメッセージをマルチキャストすることができる。

また、ネットワークにおける障害の発生の有無を認識し、尚且つその認識をネットワーク中のルータで共有し、その認識に基づいてルーティングポリシーを変更することにより、ネットワーク正常時はユーザの想定した通りの経路でルーティングを行ない（スタティックルーティング）、ネットワークに異常が起きた場合にのみ、ダイナミックルーティングプロトコルによって構築された転送経路を有効として通信状態の確保を図ることが可能となる。

また、意図した通りの中継経路が組まれるかどうか確信が持てないのでダイナミックルーティングを使いたくないが、障害が発生した場合には代替経路に切り替えたい場合に対応することができる。すなわち、通常時に適用するルーティングテーブルおよび発生しうる障害を想定した代替ルーティングテーブルをひとつまたは複数設定しておくことにより、ユーザが意図した通りのルーティング経路が適用され、障害の発生に対しても想定した代替経路が適用され、ユーザの希望に沿ったルーティングを行なうことが可能となる。

また、ルーティングテーブルがデフォルト以外のルーティングテーブルに遷移したあとでネットワークの障害が回復した場合に、デフォルトルーティングテーブルによる経路制御に戻ることにより、経路制御として最も好ましいデフォルトルーティングテーブルに基づくルーティングができる。

本実施形態は、ネットワークのルーティングを行なうためのプロトコルを各ルータに搭載し、このプロトコルの実現にはＲＰＭ（ルーティング・プロトコル・マネジメント）パケット、ネットワーク状態通知パケット、ルートスキャンパケット、ルート変更パケットを用意し、これらをルータ間でパケット転送する。以下、これらパケットを使用したルーティング方式を詳細に説明する。

（１）ＲＰＭパケットの構造と転送方式
一般的なプロトコルと同様に、ＲＰＭでもその管理情報をルータ間で通知し合う必要がある。そのために、まずＲＰＭ情報を運搬するための「ＲＰＭパケット」を定義する。

ＲＰＭパケットの転送形態は、従来のユニキャストパケット転送と同等のユニキャスト方式と、ネットワーク中の全てのルータに対するマルチキャストとして転送するルータキャスト方式とする。

図１にはルータＲＡ、ＲＢと、その間に転送する各種パケットを示し、このうちＲＰＭパケットは以下のパラメータを持たせる。

・タイプ：このパケットに記載されているメッセージのタイプを示す。

・メッセージ：ＲＰＭの管理情報の本体。メッセージのタイプによってそれぞれ固有のフォーマットを持つ。

・経由ルータテーブル：ＲＰＭパケットが経由したルータのアドレスのテーブル。可変長となる。このテーブルは、ルータキャスト方式による転送の場合のみ設ける。

・経由ルータテーブル長：経由ルータテーブルの長さを示す。このパラメータは、ルータキャスト方式による転送の場合のみ設ける。

次に、ＲＰＭパケットの転送形態について詳しく説明する。

（Ａ）ユニキャスト方式
従来のユニキャスト転送と同等。ルータは、ルーティングテーブルから判断される転送先インタフェースにＲＰＭパケットを転送する。

（Ｂ）ルータキャスト方式
ルータで接続されたネットワークにおいて、全ルータに対するマルチキャスト転送を行なう方式。ルータは、受信ポートを除く全ポートにパケットを転送する。しかし、ルータが単純にこの転送を行なってしまうと、ループ接続がある場合には無駄なパケットの巡回が発生してしまう。これを避けるために、ＲＰＭパケットのルータキャストでは次の手順で行う。

（ｓｔｅｐ１）ルータキャストＲＰＭパケットを受信したルータは、そのパケットの「経由ルータテーブル」を検索し、自身のアドレスが記入されているかどうかを調べる。

（ｓｔｅｐ２）前記テーブルに自身のアドレスを発見したら、そのパケットは転送せずに廃棄する。

（ｓｔｅｐ３）前記テーブルに自身のアドレスが発見されなかったら、同テーブルに自身のアドレスを追加し、経由ルータテーブル長をインクリメントし、それを他の隣接ルータに転送する。

以上の手順により、パケットがループ上を冗長に巡回することを避ける。このルータキャスト方式の動作例を、図２に示すネットワーク構成を例として説明する。比較のために、単純なルータマルチキャストを行なった場合の例も併せて示す。

図２の（ａ）：Ａ，Ｂ，Ｃ，Ｄはルータを、丸数字はインタフェースをそれぞれ示している。仮にルータＡのインタフェース「丸数字１」からルータキャストパケット（□）を、同インタフェース「丸数字２」から単純なマルチキャストパケット（■）をそれぞれ送信したとする。なお、ルータキャストパケットの経由ルータテーブルにはルータＡが登録されている。

図２の（ｂ）：ルータキャストパケットがルータＢに到達したとき、ルータＢは同パケットの経由ルータテーブルを参照して自身のアドレスを探したが、見つからないので自身のアドレスを追加し、隣接ルータに転送する。一方、単純マルチキャストパケットを受信したルータＤは単純に隣接ルータへこれを転送する。

図２の（ｃ）：上記の図２（ｂ）と同じ要領で各パケットが中継される。ルータキャストパケットの経由ルータテーブルもそれぞれ更新される。

図２の（ｄ）：ルータＤからルータキャストパケット（□ＡＢＤ）を受信したルータＡは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。ルータＤからルータキャストパケット（□ＡＢＤ）を受信したルータＣは、その経由ルータテーブルを参照したが、自身のアドレスがないのでそれを追加し、ルータＢに転送する（□ＡＢＤＣ）。ルータＣからルータキャストパケット（□ＡＢＣ）を受信したルータＤは、その経由ルータテーブルを参照したが、自身のアドレスがないのでそれを追加し、ルータＡ，Ｂに転送する（□ＡＢＣＤ）。一方、単純マルチキャストパケットは相変わらず単純に転送される。

図２の（ｅ）：ルータＤからルータキャストパケット（□ＡＢＣＤ）を受信したルータＡは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。ルータＣからルータキャストパケット（□ＡＢＤＣ）を受信したルータＢは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。ルータＤからルータキャストパケット（□ＡＢＣＤ）を受信したルータＢは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。これにより、ルータキャストパケットはなくなる。一方、単純マルチキャストパケットは単純転送される。

以降は、寿命が尽きるまで単純マルチキャストパケットは転送され続ける。しかも、増殖を続ける。

以上の例で見たように、単純マルチキャスト方式ではＴＴＬ（Time to Live：パケットの有効期間）が尽きるまで無駄なパケット巡回が発生してしまうが、ルータキャスト方式ではパケットの巡回は発生せず、ひとつのメッセージ転送における重複は最小限に抑えられる。

（２）ルーティングポリシーの動的切り替え
ネットワークの状態に応じてスタティックルーティングとダイナミックルーティングを使い分けるための方式について説明する。この方式は、（Ａ）障害の有無の検出、（Ｂ）障害の通知、（Ｃ）ルーティング方式の切り替えの３つの機構で構成される。

（Ａ）障害の有無の検出
ユーザは正常時におけるネットワーク構成を「ネットワーク構成情報」としてルータに登録しておく。ルータは登録された構成を常時監視し、一部でも問題があればネットワークの障害であると判断する。

ネットワーク構成情報は、図１中に示すように、そのルータに接続されているべきルータ、接続されているべきインタフェース、およびそのリンク状態をもってひとつのエントリとする、エントリテーブルである。図３を参照して以下に例を示す。

図３の（ａ）には、Ａ，Ｂ，Ｃ，Ｄの４つのルータがネットワーク上に存在する場合を示し、丸数字はインタフェースをそれぞれ示している。

ユーザはネットワークの運用を開始する前に、このネットワーク構成を各ルータに設定しておく。設定が完了すると、各ルータのネットワーク構成情報は図３の（ｂ）のようになる。なお、ネットワークの運用前なのでリンク情報は未定‘？’となっている。ネットワークの運用が開始されたら、リンク状態は正常（○）か異常（×）のいずれかとなる。

運用が開始されると各ルータは経路情報を通知するためにルーティングパケットの交換を開始する。これにより、登録されたルータが然るべきインタフェースに接続されているかどうかを確認できる。詳細なリンク状態判定基準（ルール）を以下に示す。

（ルール１）ハードウェア的にリンクステータスをモニタできる場合には、モニタされたリンクステータスがＯＦＦであればリンク状態を異常と判断する。リンクステータスがＯＮであった場合には以降の条件で判断する。なお、リンクステータスがＯＮであっても、実際にネットワーク構成情報で設定されたルータが正しく接続されている証拠とはならない。

（ルール２）標準的には、ネットワーク運用開始直後はリンク状態を正常とみなす。この条件は、正常なネットワークであっても運用を開始してから実際にルーティングパケットを受信するまでにはタイムラグがあるので、その期間を異常と判断するのは適切でないことによる。ユーザのネットワーク運用ポリシーによっては異常と判断してもよいが、少なくとも運用するネットワーク内では初期値を「正常」か「異常」のどちらかに統一しておく。

（ルール３）ネットワーク構成情報で設定されたルータからのルーティングパケットが設定されたインタフェースで受信されたら、リンク状態が正常であるとの判断が維持される。

（ルール４）ネットワーク構成情報で設定されたルータからのルーティングパケットが設定されたインタフェースで受信されない状態が所定の時間以上続いた場合には、そのリンク状態が異常であると判断する。

図３の例では、ネットワークに問題がなければ各インタフェースでルーティングパケットが受信されるのでネットワーク構成情報のリンク状態は図４のように更新される。

次に、各ルータは自身に登録されたネットワーク構成情報の各エントリのリンク状態を常時更新し、その結果をもとにネットワークの障害を以下のように検出する。

（ルール５）自身に登録されたネットワーク構成情報のエントリのリンク状態がひとつでも異常であるならば、そのルータはこれをネットワークの障害として検出する。

図４の例で見ると、ルータＡ，Ｂ，Ｃ，Ｄの各ネットワーク構成情報のリンク状態はみな正常（○）なので、どのルータもネットワークの障害は検出していない。ここで、図５に示すように、仮にルータＣ−Ｄ間で断線が発生したとする。

この断線によって、ルータＣはインタフェース「丸数字４」で受け取っていたルータＤからのルーティングパケットを受信しなくなり、またルータＤはインタフェース「丸数字９」で受け取っていたルータＣからのルーティングパケットを受信しなくなる。この状態になって所定の時間が経過したら、ルータＣ、Ｄはネットワーク構成情報の該当エントリのリンク状態を異常「×」として更新する（図５の（ｂ）参照）。

ルータＣおよびＤは、ネットワーク構成情報においてリンク状態が異常であるエントリがあるため、ネットワークの障害として検出される。

このように、事前に設定されたネットワーク構成が実際の構成上で機能しない場合にネットワーク障害として検出することができる。

（Ｂ）障害の通知
ここでは、あるルータがネットワークの障害に気が付いたときにそれをネットワーク中の各ルータに通知するための手続きについて規定する。

ルーティングポリシーの管理を適切に行なうためには、ネットワーク中の全てのルータがネットワークの障害発生の有無について、共通した認識を持っていなければならない。すなわち、共通した認識を持っていれば、それが間違った認識であったとしても、重大な通信障害のもとになることはない。なお、通信できないパスがあるかもしれないが、設定に誤りさえなければ、転送経路がループ化した状態で落ち着いてしまうことはない。

図６の（ａ）に図５の（ａ）と同じ状態を示すように、ルータＣ−Ｄ間の断線が発生すると、ルーティングパケットの受信停止によってルータＣ，Ｄはネットワークの障害を検出することができるが、ルータＡ，Ｂは障害発生箇所に隣接していないため、障害を検出することはできない。

そこで、障害の発生を他のルータにも知らせるために「ネットワーク状態通知パケット」を定義する。ネットワーク状態通知パケットは図１中に示すように、ＲＭＰパケット仕様に準拠し、以下の項目を設ける。

・転送形態＝ルータキャスト方式
・メッセージタイプ＝「ネットワーク状態通知メッセージ」
また、ネットワーク状態通知パケットは以下の固有のパラメータを持つ。

・障害検出フラグ＝ネットワーク障害の有無を示す。障害ありの場合にセットする。

ネットワーク状態通知パケットは以下のように運用される。

・前記の障害の検出の機構によって、ネットワークの障害を検出した状態のルータは、障害検出フラグをセットしたネットワーク状態通知パケットを定期的に送信し続ける。

・前記の障害の検出の機構によって、ネットワークの障害を検出しなくなったルータは、障害検出フラグをセットしたネットワーク状態通知パケットの定期送信を中止する。

・「ネットワーク異常」（以下の説明参照）と判断された状態において、一定期間以上、ネットワークの障害を通知されない場合（つまり、障害検出フラグがセットされたネットワーク状態通知パケットを受信しなかった場合）には、障害検出フラグをクリアしたネットワーク状態通知バケットを発信する。

ルータは、ネットワークの状態が正常であるか異常であるかについて以下のように判断する。

（ルール１）前記の障害の検出機構によってネットワークの障害を検出した場合には「ネットワーク異常」と判断する。

（ルール２）障害検出フラグがセットされたネットワーク障害通知パケットを受信した場合にも「ネットワーク異常」と判断する。

（ルール３）前記の障害の検出の機構によってネットワークの障害を検出しておらず、尚且つ、障害検出フラグがセットされたネットワーク状態通知パケットを一定期間以上受信しておらず、尚且つ、障害検出フラグがクリアされたネットワーク状態通知パケットを受信した場合には「ネットワーク正常」と判断する。

図６を参照して、障害発生通知の動作例を示す。

図６の（ａ）：障害発生状態を示す。

図６の（ｂ）および図６の（ｃ）：ルータＣ，Ｄはネットワーク障害を検出し、前記のルータキャスト方式で障害をネットワーク全体に通知する。図中の下線付きルータは「ネットワーク異常」と判断したルータを示す。

ルータＣ，Ｄはネットワーク状態通知パケット（障害検出フラグ＝セット）を定期的に送信する。

図６の（ｄ）：ルータＣ−Ｄ間の断線が回復したとき、ルータＣ，Ｄはネットワークの障害を検出しない状態となったため、障害検出フラグをセットしたネットワーク状態通知パケットの送信を中止し、ネットワーク状態通知パケットの定期送信が途絶え、静かな状態となる。ただし、いずれのルータも未だに「ネットワーク異常」と認識している。

上記の状態にて所定の時間が経過し、障害検出フラグをクリアしたネットワーク状態通知パケットを任意のルータが送信する。冗長な送信を避けるために、各ルータがランダムなタイミングで同パケットを送信し、他のルータが先に同パケットを送信した場合には自身の送信を控えるのが望ましい（誰かひとりがこれを系全体に通知すればよい）。

図６の（ｅ）：各ルータは「ネットワーク正常」と認識するようになる。

（Ｃ）ルーティング方式の切り替え
前記の（Ａ）障害の有無検知と（Ｂ）障害の通知の機構により、各ルータはネットワークの正常・異常を正しく判断できる。この判断に基づいてルーティングポリシーを以下のように運用する。

（ルール１）「ネットワーク正常」の場合はスタティックルーティングを行なう。

（ルール２）「ネットワーク異常」の場合はダイナミックルーティングを行なう。

これにより、ネットワークが正常である限り、ユーザが想定した経路に基づいてパケットが中継される。また、障害が発生した場合には、ダイナミックルーティングに切り替えられるために、障害箇所の迂回経路が自動的に組まれて通信状態が維持される。

（３）複数のスタティックルーティングエントリの運用
前記までは、障害発生時にダイナミックルーティングに切り替える方式を示したが、以下には障害が起きても想定外の中継経路が組まれないようにするための方式を示す。この方式では、各ルータはスタティックルーティングのときに使用する中継経路をひとつではなく、複数の設定を可能とし、実際のネットワーク上に展開可能な経路設定を選んでルーティングを行なう。

（Ａ）経路情報の設定
図１中に示すように、スタティックルーティングで使用するルーティングテーブルをルータに設定する。このテーブルには、デフォルトで使用するルーティングテーブルの他に、障害などによってデフォルト経路が使用不可になった場合に使用する代替ルーティングテーブルをひとつあるいは複数を登録可能とする。全てのルーティングテーブルにはＩＤが割り当てられ、デフォルトのルーティングテーブルにはＩＤ＝０を割り当てる。

ルーティングは常に同じＩＤを持つルーティングテーブルに基づいて行なわれるので、同一ＩＤのルーティングテーブルにおいて転送ループなどの矛盾のないように注意深く設定を行なう必要がある。ネットワークにおける全てのルータにルーティングテーブルを設定したら運用を開始する。

図７に例を示す。図７の（ａ）に示すルーティング状態において、仮に、Ａ−Ｂ，Ｂ−Ｃ，Ｂ−Ｄ間が高速、Ａ−Ｄ間が中速、Ｃ−Ｄ間が低速とする。このネットワークに従来のＲＩＰをそのまま適用すると、ホップ数が短いという理由で高速であるにもかかわらず、低速なパスを含む転送経路が組まれるため、図７の（ｂ）に例を示すように、ユーザは複数の静的な経路情報を設定したとする。

図７の（ｂ）に示すルーティングテーブルは、各ルータＡ，Ｂ，Ｃ，Ｄの左側はネットワークを示し、右側の数字はそのネットワーク宛てのパケットを転送すべきインタフェースを示す。この例では、ルータＡにネットワークａ、ルータＢにネットワークｂ、ルータＣにネットワークｃが接続されているものとする。例えば、ルータＢがネットワークｄ宛てのパケットを受信したら、これをインタフェース「丸数字７」へ転送する（ＩＤ＝０の場合）。

（Ｂ）デフォルトルーティングテーブル（ＩＤ＝０）に基づいて運用開始
ＩＤ＝０のルーティングテーブルに基づいて運用を開始する。この時点では、デフォルトルーティングテーブルによるルーティングが完全に機能するかどうか分からない。もしかしたら、ある経路が断線しているため、一部のパケットが宛て先に届かない可能性もある。

ただし、設定そのものに問題がない限り、ネットワークが正常であろうとなかろうと、少なくとも中継がループしてしまうおそれはない。なぜならば、ネットワークが正常なときにループになってしまうならば、それは設定のミスであり、ネットワークが異常なときにはリンクの欠損が発生するので、ループが発生するはずがないからである。

（Ｃ）ルーティングテーブルの検査
スタティックルーティングを開始したら、ルータは現在運用している中継経路に問題がないかどうか確かめなくてはならない。そこで、中継経路のチェックを行なうために「ルートスキャンパケット」を定義する。ルートスキャンパケットは図１中に示すように、ＲＭＰパケット仕様に準拠し、以下の項目を設ける。

・転送形態＝ユニキャスト方式（ネットワークを宛て先とする）
・メッセージタイプ＝「ルートスキャンメッセージ」
また、ルートスキャンパケットは以下の固有のパラメータを持つ。

・ルーティングテーブルＩＤ＝チェックする経路情報のＩＤ
ルータはルートスキャンパケットを次の手順で運用する。

（ｓｔｅｐ１）ルータに登録されている宛て先ネットワーク全てに対してルートスキャンパケットを送信して返事を待つ。

（ｓｔｅｐ２）ルートスキャンパケットを受信したルータはそれを中継する。ただし、ルーティングするのに使用するルーティングテーブルはそのパケットに含まれているルーティングテーブルＩＤで指定されたルーティングテーブルとする。もし仮に、一般フレームがＩＤ＝０のルーティングテーブルに基づいてルーティングされている状態において、ＩＤ＝１のルートスキャンパケットが受信されたら、このパケットだけはＩＤ＝１のルーティングテーブルに基づいて中継される。

（ｓｔｅｐ３）ルートスキャンパケットは中継されてゆき、やがて宛て先ネットワークに直接接続されたルータがこのパケットを受け取る。このルータはそれをネットワークには転送せずに送信元ルータに返信する。

（ｓｔｅｐ４）自分が送信したルートスキャンパケットに対する返信を受け取ったルータは、その経路が機能していると判断し、ルーティングテーブルの該当エントリに○印を付ける。

（ｓｔｅｐ５）自分が送信したルートスキャンパケットに対する返信を受け取らずに一定期間が経過したら再送する。

（ｓｔｅｐ６）ルートスキャンパケットの返事を所定回数以上連続して受け取れない場合には、その経路がだめであると判断し、ルーティングテーブルの該当エントリに×印を付ける。

（ｓｔｅｐ７）この経路チェックを絶えず継続する。

この手順でルーティングテーブルをチェックし、全てのエントリに○か×を付けてゆく。全てのエントリに○印がついている場合にはその経路情報でのルーティングを継続することができる。

図８は、図７の状態の例を用いて経路制御の行なわれる様子を示す。仮にＩＤ＝０に基づいてルーティングしているとし、ここでルータＡによる経路スキャンに注目する。なお、同様の経路スキャンを他のルータも行なっているが、簡単のためこの例題では表記しない。

図８の（ａ）：ルータＡはネットワークｂ，ｃ，ｄ宛てにルートスキャンパケットを送信する。ルータＡのＩＤ＝０の経路情報によれば、いずれのネットワークもインタフェース「丸数字１」がアサインされているので、これらのパケットはこのインタフェースから送信される。これらのルートスキャンパケットの経路情報ＩＤにはいずれも０がセットされている。

図８の（ｂ）：ルータＢは自身のルーティングテーブルに基づいてルートスキャンパケットを処理する。ネットワークｃ，ｄ宛てのルートスキャンパケットはそれぞれインタフェース「丸数字５」、「丸数字７」へ転送される。また、ネットワークｂ宛てのルートスキャンパケットは自身の管理するネットワーク宛てであるので、これをルータＡに対して返信する（宛て先がルータＡに書き換えられる）。

図８の（ｃ）：ルータＡはネットワークｂ宛てに送ったルートスキャンパケットの返信を確認したので、ルーティングテーブルの該当エントリは正常であると判断し、○印を付ける。また、ルータＣ，Ｄはそれぞれ自身の管理するネットワーク宛てのルートスキャンパケットを受信したので、これをルータＡに対して返信する。

図８の（ｄ）：ルータＢはルータＡ宛てのルークスキャンパケットを受信したので、これをルータＡに転送する。

図８の（ｅ）：ルータＡはネットワークｃ，ｄ宛てに送ったルートスキャンパケットの返信を確認したので、ルーティングテーブルの該当エントリは正常であると判断し、○印を付ける。

以上のように、ルータＡのルーティングテーブルの全てのエントリに○印がついたので、ルータＡはこのルーティングテーブルに基づいてルーティングを続けても問題ない。ただし、障害はいつ発生するかわからないので、定期的にチェックを行なう必要がある。

仮に、ルータＢ−Ｄ間が断線していた場合には上記の図８の（ｂ）〜（ｅ）は以下のようになる。

図８の（ｂ）：ルータＡからネットワークｄ宛てのルートスキャンパケットを受信したルータＢはＩＤ＝０のルーティングテーブルに基づいてインタフェース「丸数字７」にこれを転送する。

図８の（ｃ）：Ｂ−Ｄ間は断線しているため、ルータＢが転送したネットワークｄ宛てルートスキャンパケットはルータＤに届かないため、ルータＤは何もしない。

図８の（ｄ）：ネットワークｄ宛てのルートスキャンパケットは既にネットワーク中には存在しない。

図８の（ｅ）：ネットワークｄ宛てに送ったルートスキャンパケットの返事が来ないため、ルータＡは（何度かリトライした後に）該当エントリに×印を添付する。この結果、ルーティングテーブル（ＩＤ＝０）は、図９のようになる。

これでルータＡはＩＤ＝０のルーティングテーブルを使っていたのでは、一部のパスが無効であることに気が付く。

（Ｄ）ルーティングテーブルの切り替え手続き
ルーティングテーブルを検査した結果、その中に無効なパスを発見したルータは、代替経路で有効なものを探し出し、見つかったらルーティングテーブルをそのシリーズにするように系全体にアピールする。アピールが認められたら、系全体のルーティングテーブルを一斉に変更する。

以下に詳細な手順を示すが、この手続きを行なうために「ルート変更パケット」を定義する。ルート変更パケットは、図１中にも示すように、ＲＭＰパケット仕様に準拠し、以下の項目を設ける。

・転送形態＝ルータキャスト方式
・メッセージタイプ＝「ルート変更メッセージ」
また、ルートスキャンパケットは以下の固有のパラメータを持つ。

・ルーティングテーブルＩＤ＝この変更手続きで対象となっているルーティングテーブルＩＤ
・コマンド＝変更手続き上のコマンド。「要求」「拒否」「実施」のいずれか。

このルート変更パケットを使用したルーティングテーブルの切り替えには、以下の手順によって行われる。

（ｓｔｅｐ１）代替ルーティングテーブルの検索
前記の（Ｃ）ルーティングテーブルの検査によって現行のルーティングテーブルに欠陥を見つけたルータは、他に有効なルーティングテーブルがないかどうか、同様の手順を駆使して検索する。代替ルーティングテーブルの検索はＩＤの小さい方から順次行なってゆく（ただし、現行のテーブルを除く）。仮に、ＩＤ＝０でのルーティングに問題があれば、ＩＤ＝１，２，３，…の順番でルーティングテーブルを検索してゆく。ルーティングテーブルの検査における手順は（Ｃ）ルーティングテーブルの検査で示した通りである。有効な代替ルーティングテーブルが見つかったら、次のステップへと進む。見つからなかった場合にはルーティングテーブルの変更をあきらめる。

（ｓｔｅｐ２）ルーティングテーブル変更アピール
有効な代替ルーティングテーブルが見つかったら、そのルータはこのルーティングテーブルの採用をネットワーク全体にアピールする。そのルータは前記のルート変更パケットを送信する。ここで、ルーティングテーブルＩＤには採用を希望するルーティングテーブルＩＤ、コマンドには「要求」をそれぞれセットする。以降、アピールが受け入れられるか、あるいは明示的に拒否を示されるまで、このＩＤに対するアピールを繰り返す。

（ｓｔｅｐ３）アピールされたＩＤの検査
ルート変更パケットによって、ネットワークの各ルータは要求されたＩＤのルーティングテーブルが自身にとっても有効かどうかを検査する。検査方法は前記の（Ｃ）ルーティングテーブルの検査で示した通りである。もし、そのルーティングテーブルでは無効なパスがあることが分かったルータは、そのルーティングテーブルに対して拒否を示すためにルート変更パケットを送信する。ここで、ルーティングテーブルＩＤには拒否するルーティングテーブルのＩＤ、コマンドを「拒否」をそれぞれセットする。アピールされたルーティングテーブルでも問題ないことが分かったルータは、現行のルーティングを続けながら、変更アピール手続きでの次のアクションを待つ。

（ｓｔｅｐ４）ルーティングテーブルの変更
変更を希望するルータがルート変更「要求」パケットを送信し始めてから所定の時間が経過し、その間にルート変更「拒否」パケットを受信しなかった場合には、そのルータはアピールが受け入れられたと判断し、ルート変更パケットを送信する。ここで、ルーティングテーブルＩＤにはアピールしていたルーティングテーブルＩＤ、コマンドには「実施」をセットする。この後、同ルータはこのルート変更「実施」パケットを定期的に送信し、そのルーティングテーブルが採用された状態を維持する。もし、その必要がなくなった場合にはこのパケットの定期送信を中止する。

（ｓｔｅｐ５）ルーティングテーブルの変更拒否
もし、アピール期間中にルート変更「拒否」パケットを受信した場合に、このルーティングテーブルへの変更はあきらめて、別の代替ルーティングテーブルの検索工程に戻る。別の代替ルーティングテーブルが見つかったら、同様の手順でそのルーティングテーブルに対する採用アピールを行なう。

以上の手順になるルーティングテーブル変更手続きの例を図１０、図１１を参照して以下に説明する。前記の（Ｃ）ルーティングテーブルの検査の例のように、Ｂ−Ｄ間で断線が発生し、たまたまルータＡがそれに最初に気が付いたとする。なお、経路チェックは各ルータが定期的に行なっており、それらは非同期であるので、誰が最初に気が付くかは不定となる。

図１０の（ａ）：ルータＡはＩＤ＝０のルーティングテーブルに問題を見つけたので、ＩＤ＝１のルーティングテーブルの有効性について調査する。ＩＤ＝１のテーブルに基づいて、ネットワークｂ，ｃ，ｄ宛てのルートスキャンパケットがインタフェース「丸数字２」から送信された。以降の手順は（Ｃ）ルーティングテーブルの検査で示した通りである。

図１０の（ｂ）：上記の検査において、ネットワークｂ，ｃ宛てに送信したルートスキャンパケットは、ルータＤにおいてインタフェース「丸数字８」に転送されてしまうため、ルータＢ，Ｃへ到達することなく消滅する。従って、（何度かリトライした後に）ルータＡのテーブルは図示のようにチェックされる。

図１０の（ｃ）：ＩＤ＝１のルーティングテーブルではだめなことがわかったので、ルータＡは次にＩＤ＝２のルーティングテーブルのチェックを行なう。手順は前述の通りである。

図１１の（ａ）：上記の検査の結果、この経路では問題ないことが判明した。

図１１の（ｂ）：ルータＡはＩＤ＝２に対するルート変更「要求」パケットを送信する。同バケットの転送手順は以前に説明した通りである。

このとき、ネットワーク中のルータＢ，Ｃ，Ｄはルート変更「要求」パケットを受信したので、それぞれがＩＤ＝２のルーティングテーブルのチェックを開始する。手順は以前に示した通りである。

図１１の（ｃ）：ルータＢ，Ｃ，ＤはそれぞれＩＤ＝２のルーティングテーブルの調査結果をルーティングテーブルに書き込む。いずれのルータにおいても×印はつかなかったので、この提案に対して異を唱えるルータは現れない。

図１１の（ｄ）：アピール期間が経過し、旦つアピールが拒否されなかったので、ルータＡはルート変更「実施」パケットを送信する。また、ルータＡは自身のルーティングテーブルをＩＤ＝２のものに変更する。

次に、ルート変更「実施」パケットを受信したルータＢ，Ｃ，Ｄは、アピールが実行に移されたことを知ったので、さっそく各自のルーティングテーブルをＩＤ＝２のものに変更する。

さらに、ＩＤ＝２のルーティングテーブルに基づくルーティングが開始され、ユーザが設定した通りの障害迂回経路に基づいてパケット中継が行なわれるようになる。

（５）デフォルト経路情報への復帰
ネットワークに障害がなければ、デフォルトルーティングテーブルに基づくルーティングがもっとも望ましい。そこで、ルーティングテーブルがデフォルト以外のルーティングテーブルに遷移したあとでネットワークの障害が回復した場合に、デフォルトルーティングテーブルによる経路制御に戻る手段を設ける。

前記の（４）ルーティングテーブルの切り替え手続で示したように、ルーティングテーブルの変更状態維持を望むルータは定期的にルート変更「実施」パケットを送信し続ける。このルータは変更状態を維持する一方、デフォルトルーティングテーブルでのルーティングが回復するのを監視するため、定期的にＩＤ＝０のルーティングテーブルを検査する。検査方法は前記の（Ｃ）ルーティングテーブル検査方法で示した通りである。

もしも、ＩＤ＝０でのルーティングに問題ないことが判明したら、そのルータはルート変更「実施」パケットの定期送信を中止する。

もし、他にもそのＩＤのルーティングテーブルによるルーティングを望むルータがいれば、ルート変更「実施」パケットの定期送信はそのルータに引き継がれ、引き続きその状態が維持される。

もし、他にだれもそのＩＤのルーティングテーブルによるルーティングを特に希望しない場合には、ネットワークにルート変更「実施」パケットを送信するものがいなくなる。

ルート変更「実施」パケットが一定期間以上途絶えた場合には、ネットワーク中の任意のルータがＩＤ＝０のルーティングテーブルへ変更するためのアピールを開始する。ＩＤ＝０へのルーティングテーブルへの変更に対するアピールがなされたら、他のルータはさっそくＩＤ＝０のルーティングテーブルのチェックを開始する。その結果、ＩＤ＝０のルーティングテーブルでは問題のあることがわかったルータは、ＩＤ＝０に対するルート変更「拒否」パケットを発信する。なお、ＩＤ＝０でのルーティングに問題のあるルータは現行のＩＤのルーティングテーブルによるルーティングを維持するため、前述のルート変更「実施」パケットを定期的に送信し続けなけばならない。

ＩＤ＝０への変更に異議を唱えるルータがいなければ、アピール期間が満了した後に、アピールが実施に移されるのは、既に説明した通りである。

なお、デフォルト経路情報に戻った場合には、ＩＤ＝０に対するルート変更「実施」パケットの定期送信は必要ない。ルート変更「実施」パケットの定期送信はＩＤ≠０であるルーティングテーブルに基づくルーティングを維持したい場合にのみ必要とする。

本発明の実施形態を示すルータＲＡ、ＲＢと各種パケットの例。 ルータキャスト方式のネットワーク構成例。 ４つのルータ構成とネットワーク構成情報の例。 ネットワーク構成とリンク状態の変化例。 ネットワークの断線とリンク状態の変化例。 ネットワーク障害時の通知の例。 ルーティング状態における経路情報の設定例。 ルーティング状態における経路制御の例。 ルーティングの定期的なチェック結果による経路状態の例。 ルーティングテーブル変更手続きの例（その１）。 ルーティングテーブル変更手続きの例（その２）。

符号の説明

ＲＡ、ＲＢ ルータ

Claims (4)

1. ルータ（あるいはレイヤ３スイッチ）により、ネットワーク間でパケットの中継経路を制御するルーティング方式であって、
   各ルータは、ネットワークのルーティングを行なうためのプロトコルを搭載し、経路の管理情報をルータ間で通知し合うＲＰＭ（ルーティング・プロトコル・マネジメント）パケットを用意し、前記ＲＰＭパケットは、ＲＰＭの管理情報のメッセージと、経由したルータのアドレステーブルとを有し、
   前記各ルータは、前記ＲＰＭパケットをネットワーク中の全てのルータに転送するルータキャストには、ＲＰＭパケットが経由したルータを当該パケットに記録し、このパケットを受信したルータが当該パケットに記録された経由ルータの記録を参照し、自身の記録があればこれを転送せずに廃棄するパケット転送手段を備えたことを特徴とするネットワークのルーティング方式。
2. 前記ルータは、
   接続されているべき隣接ルータ、接続されているべきインタフェース、および、そのリンクの状態を記録するテーブルを持つネットワーク構成情報を常時監視し、一部でも問題があればネットワーク障害を判断する手段と、
   前記ネットワークの障害を判断したときに「ネットワーク状態通知パケット」でネットワーク中の各ルータに通知する手段と、
   ネットワーク正常の場合はスタティックルーティングを行い、ネットワーク異常の場合はダイナミックルーティングに切り替える手段とを備えたことを特徴とする請求項１に記載のネットワークのルーティング方式。
3. 前記ルータは、
   複数のスタティックルーティングテーブルを設け、各スタティックルーティングテーブルにはネットワーク全体で統一するためのＩＤを割り当てる手段と、
   スタティックルーティングの開始で、ルートスキャンパケットを転送して任意のＩＤのルーティングテーブルによる中継経路を検査する手段と、
   前記中継経路の検査結果に無効なパスを発見したときに、代替経路で有効なものを探し出し、「ルート変更パケット」を転送してルーティングテーブルをそのシリーズにするように系全体に要求する手段と、
   前記ルート変更要求された他のルータがそのルーティングテーブルを調査し、問題があった場合にその要求に対して拒否をする手段と、
   前記ルート変更要求に対して拒否がなかった場合に、系全体のルーティングテーブルを一斉に変更する手段とを備えたことを特徴とする請求項１または２に記載のネットワークのルーティング方式。
4. 前記ルータは、前記ルーティングテーブルが変更された後、ネットワークの障害が回復した場合にデフォルトルーティングテーブルによる経路制御に戻る手段を備えたことを特徴とする請求項３に記載のネットワークのルーティング方式。
   

Images