(57)【要約】【課題】ネットワーク間の通信経路に障害等が発生した場合、系に混乱を与えることなく適切な経路を確保する。【解決手段】各ルータは、ＲＰＭパケットを全てのルータに転送し、ＲＰＭパケットが経由したルータを当該パケットに記録し、このパケットに自身のルータの記録があればこれを転送せずに廃棄する。ネットワーク構成情報から障害を判断したときに「ネットワーク状態通知パケット」で各ルータに通知する。ネットワーク正常の場合はスタティックルーティングを行い、ネットワーク異常の場合はダイナミックルーティングに切り替える。スタティックルーティングで、ルートスキャンパケットを転送して中継経路を検査し、無効なパスを発見したときに代替経路で有効なものに一斉に変更する。ネットワークの障害が回復した場合にデフォルトルーティングテーブルによる経路制御に戻る。【選択図】図１
2007288464.tif 000002
【特許請求の範囲】
【請求項１】
ルータ（あるいはレイヤ３スイッチ）により、ネットワーク間でパケットの中継経路を制御するルーティング方式であって、
各ルータは、ネットワークのルーティングを行なうためのプロトコルを搭載し、経路の管理情報をルータ間で通知し合うＲＰＭ（ルーティング・プロトコル・マネジメント）パケットを用意し、前記ＲＰＭパケットは、ＲＰＭの管理情報のメッセージと、経由したルータのアドレステーブルとを有し、
前記各ルータは、前記ＲＰＭパケットをネットワーク中の全てのルータに転送するルータキャストには、ＲＰＭパケットが経由したルータを当該パケットに記録し、このパケットを受信したルータが当該パケットに記録された経由ルータの記録を参照し、自身の記録があればこれを転送せずに廃棄するパケット転送手段を備えたことを特徴とするネットワークのルーティング方式。
【請求項２】
前記ルータは、
接続されているべき隣接ルータ、接続されているべきインタフェース、および、そのリンクの状態を記録するテーブルを持つネットワーク構成情報を常時監視し、一部でも問題があればネットワーク障害を判断する手段と、
前記ネットワークの障害を判断したときに「ネットワーク状態通知パケット」でネットワーク中の各ルータに通知する手段と、
ネットワーク正常の場合はスタティックルーティングを行い、ネットワーク異常の場合はダイナミックルーティングに切り替える手段とを備えたことを特徴とする請求項１に記載のネットワークのルーティング方式。
【請求項３】
前記ルータは、
複数のスタティックルーティングテーブルを設け、各スタティックルーティングテーブルにはネットワーク全体で統一するためのＩＤを割り当てる手段と、
スタティックルーティングの開始で、ルートスキャンパケットを転送して任意のＩＤのルーティングテーブルによる中継経路を検査する手段と、
前記中継経路の検査結果に無効なパスを発見したときに、代替経路で有効なものを探し出し、「ルート変更パケット」を転送してルーティングテーブルをそのシリーズにするように系全体に要求する手段と、
前記ルート変更要求された他のルータがそのルーティングテーブルを調査し、問題があった場合にその要求に対して拒否をする手段と、
前記ルート変更要求に対して拒否がなかった場合に、系全体のルーティングテーブルを一斉に変更する手段とを備えたことを特徴とする請求項１または２に記載のネットワークのルーティング方式。
【請求項４】
前記ルータは、前記ルーティングテーブルが変更された後、ネットワークの障害が回復した場合にデフォルトルーティングテーブルによる経路制御に戻る手段を備えたことを特徴とする請求項３に記載のネットワークのルーティング方式。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルータあるいはＬ３（レイヤ３）スイッチによるネットワークのルーティング方式に関する。
【背景技術】
【０００２】
ネットワーク間でパケットの中継経路を制御する「ルーティング」には、事前に設定された固定の経路に基づいて中継を行なう「スタティックルーティング」と、ルータ間での経路情報のやり取りで決定された経路に基づいて中継を行なう「ダイナミックルーティング」があり、環境やユーザの都合でどちらかが選択されて運用される。
【０００３】
ダイナミックルーティングには幾つかの方法があるが、イーサネット（登録商標）等の非同期ネットワークにおけるルーティングとしては、もっぱらＲＩＰ（Routing Information Protocol），ＯＳＰＦ（Open Shortest Path First）などのルーティングプロトコルが使用される。ＲＩＰは、経路を構成するルータ数（ホップ数）に従って最短経路を動的に決定する。ＯＳＰＦは、伝送帯域をもパラメータとして階層化したルーティングが可能になり、通信障害等が発生したときに、新たな通信経路を検索してその確保が可能となる（例えば、特許文献１参照）。
【特許文献１】特開２００２−３７４２９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
スタティックルーティングは、ユーザが設定した経路に忠実に従ってパケットの中継が行なわれるため、ルーティングは安定する。しかし、ネットワークに障害が発生しても自力でこれを迂回することはできない。意図しない経路が組まれることを嫌ってスタティックルーティングを選択するユーザもいるが、これではダイナミックルーティングの恩恵を受けることができない。
【０００５】
しかし、ダイナミックルーティングには一般に以下のような欠点がある。
【０００６】
（１）ルーティングによって決定した経路がユーザの想定からかけ離れたものになる可能性がある。
【０００７】
（２）誤ったルーティング情報によって系が混乱に陥るおそれがある。
【０００８】
例えば、ＲＩＰを使った場合、転送経路はホップ数を元に計算されるため、回線速度などを考慮した経路を構築させるのには困難が伴う（ＲＩＰではホップ数の上限が小さいため、ホップ数の重み付けで対応するのも難しい）。
【０００９】
また、（２）については、場合によってはループ発生の原因にもなるので重大な問題を引き起こすおそれがある。
【００１０】
本発明の目的は、通信経路に障害等が発生した場合、系に混乱を与えることなく適切な経路を確保できるネットワークのルーティング方式を提供することにある。
【課題を解決するための手段】
【００１１】
前記の課題を解決するための本発明は、以下の構成を特徴とする。
【００１２】
（１）ルータ（あるいはレイヤ３スイッチ）により、ネットワーク間でパケットの中継経路を制御するルーティング方式であって、
各ルータは、ネットワークのルーティングを行なうためのプロトコルを搭載し、経路の管理情報をルータ間で通知し合うＲＰＭ（ルーティング・プロトコル・マネジメント）パケットを用意し、前記ＲＰＭパケットは、ＲＰＭの管理情報のメッセージと、経由したルータのアドレステーブルとを有し、
前記各ルータは、前記ＲＰＭパケットをネットワーク中の全てのルータに転送するルータキャストには、ＲＰＭパケットが経由したルータを当該パケットに記録し、このパケットを受信したルータが当該パケットに記録された経由ルータの記録を参照し、自身の記録があればこれを転送せずに廃棄するパケット転送手段を備えたことを特徴とする。
【００１３】
（２）前記ルータは、
接続されているべき隣接ルータ、接続されているべきインタフェース、および、そのリンクの状態を記録するテーブルを持つネットワーク構成情報を常時監視し、一部でも問題があればネットワーク障害を判断する手段と、
前記ネットワークの障害を判断したときに「ネットワーク状態通知パケット」でネットワーク中の各ルータに通知する手段と、
ネットワーク正常の場合はスタティックルーティングを行い、ネットワーク異常の場合はダイナミックルーティングに切り替える手段とを備えたことを特徴とする。
【００１４】
（３）前記ルータは、
複数のスタティックルーティングテーブルを設け、各スタティックルーティングテーブルにはネットワーク全体で統一するためのＩＤを割り当てる手段と、
スタティックルーティングの開始で、ルートスキャンパケットを転送して任意のＩＤのルーティングテーブルによる中継経路を検査する手段と、
前記中継経路の検査結果に無効なパスを発見したときに、代替経路で有効なものを探し出し、「ルート変更パケット」を転送してルーティングテーブルをそのシリーズにするように系全体に要求する手段と、
前記ルート変更要求された他のルータがそのルーティングテーブルを調査し、問題があった場合にその要求に対して拒否をする手段と、
前記ルート変更要求に対して拒否がなかった場合に、系全体のルーティングテーブルを一斉に変更する手段とを備えたことを特徴とする。
【００１５】
（４）前記ルータは、前記ルーティングテーブルが変更された後、ネットワークの障害が回復した場合にデフォルトルーティングテーブルによる経路制御に戻る手段を備えたことを特徴とする。
【発明の効果】
【００１６】
以上のとおり、本発明によれば、経由ルータをパケットに記録してゆくことにより、一度受信したことのあるパケットをルータが転送しなくなるため、無駄なパケット巡回を最小限に抑えながら、ネットワーク中のルータにメッセージをマルチキャストすることができる。
【００１７】
また、ネットワークにおける障害の発生の有無を認識し、尚且つその認識をネットワーク中のルータで共有し、その認識に基づいてルーティングポリシーを変更することにより、ネットワーク正常時はユーザの想定した通りの経路でルーティングを行ない（スタティックルーティング）、ネットワークに異常が起きた場合にのみ、ダイナミックルーティングプロトコルによって構築された転送経路を有効として通信状態の確保を図ることが可能となる。
【００１８】
また、意図した通りの中継経路が組まれるかどうか確信が持てないのでダイナミックルーティングを使いたくないが、障害が発生した場合には代替経路に切り替えたい場合に対応することができる。すなわち、通常時に適用するルーティングテーブルおよび発生しうる障害を想定した代替ルーティングテーブルをひとつまたは複数設定しておくことにより、ユーザが意図した通りのルーティング経路が適用され、障害の発生に対しても想定した代替経路が適用され、ユーザの希望に沿ったルーティングを行なうことが可能となる。
【００１９】
また、ルーティングテーブルがデフォルト以外のルーティングテーブルに遷移したあとでネットワークの障害が回復した場合に、デフォルトルーティングテーブルによる経路制御に戻ることにより、経路制御として最も好ましいデフォルトルーティングテーブルに基づくルーティングができる。
【発明を実施するための最良の形態】
【００２０】
本実施形態は、ネットワークのルーティングを行なうためのプロトコルを各ルータに搭載し、このプロトコルの実現にはＲＰＭ（ルーティング・プロトコル・マネジメント）パケット、ネットワーク状態通知パケット、ルートスキャンパケット、ルート変更パケットを用意し、これらをルータ間でパケット転送する。以下、これらパケットを使用したルーティング方式を詳細に説明する。
【００２１】
（１）ＲＰＭパケットの構造と転送方式
一般的なプロトコルと同様に、ＲＰＭでもその管理情報をルータ間で通知し合う必要がある。そのために、まずＲＰＭ情報を運搬するための「ＲＰＭパケット」を定義する。
【００２２】
ＲＰＭパケットの転送形態は、従来のユニキャストパケット転送と同等のユニキャスト方式と、ネットワーク中の全てのルータに対するマルチキャストとして転送するルータキャスト方式とする。
【００２３】
図１にはルータＲＡ、ＲＢと、その間に転送する各種パケットを示し、このうちＲＰＭパケットは以下のパラメータを持たせる。
【００２４】
・タイプ：このパケットに記載されているメッセージのタイプを示す。
【００２５】
・メッセージ：ＲＰＭの管理情報の本体。メッセージのタイプによってそれぞれ固有のフォーマットを持つ。
【００２６】
・経由ルータテーブル：ＲＰＭパケットが経由したルータのアドレスのテーブル。可変長となる。このテーブルは、ルータキャスト方式による転送の場合のみ設ける。
【００２７】
・経由ルータテーブル長：経由ルータテーブルの長さを示す。このパラメータは、ルータキャスト方式による転送の場合のみ設ける。
【００２８】
次に、ＲＰＭパケットの転送形態について詳しく説明する。
【００２９】
（Ａ）ユニキャスト方式
従来のユニキャスト転送と同等。ルータは、ルーティングテーブルから判断される転送先インタフェースにＲＰＭパケットを転送する。
【００３０】
（Ｂ）ルータキャスト方式
ルータで接続されたネットワークにおいて、全ルータに対するマルチキャスト転送を行なう方式。ルータは、受信ポートを除く全ポートにパケットを転送する。しかし、ルータが単純にこの転送を行なってしまうと、ループ接続がある場合には無駄なパケットの巡回が発生してしまう。これを避けるために、ＲＰＭパケットのルータキャストでは次の手順で行う。
【００３１】
（ｓｔｅｐ１）ルータキャストＲＰＭパケットを受信したルータは、そのパケットの「経由ルータテーブル」を検索し、自身のアドレスが記入されているかどうかを調べる。
【００３２】
（ｓｔｅｐ２）前記テーブルに自身のアドレスを発見したら、そのパケットは転送せずに廃棄する。
【００３３】
（ｓｔｅｐ３）前記テーブルに自身のアドレスが発見されなかったら、同テーブルに自身のアドレスを追加し、経由ルータテーブル長をインクリメントし、それを他の隣接ルータに転送する。
【００３４】
以上の手順により、パケットがループ上を冗長に巡回することを避ける。このルータキャスト方式の動作例を、図２に示すネットワーク構成を例として説明する。比較のために、単純なルータマルチキャストを行なった場合の例も併せて示す。
【００３５】
図２の（ａ）：Ａ，Ｂ，Ｃ，Ｄはルータを、丸数字はインタフェースをそれぞれ示している。仮にルータＡのインタフェース「丸数字１」からルータキャストパケット（□）を、同インタフェース「丸数字２」から単純なマルチキャストパケット（■）をそれぞれ送信したとする。なお、ルータキャストパケットの経由ルータテーブルにはルータＡが登録されている。
【００３６】
図２の（ｂ）：ルータキャストパケットがルータＢに到達したとき、ルータＢは同パケットの経由ルータテーブルを参照して自身のアドレスを探したが、見つからないので自身のアドレスを追加し、隣接ルータに転送する。一方、単純マルチキャストパケットを受信したルータＤは単純に隣接ルータへこれを転送する。
【００３７】
図２の（ｃ）：上記の図２（ｂ）と同じ要領で各パケットが中継される。ルータキャストパケットの経由ルータテーブルもそれぞれ更新される。
【００３８】
図２の（ｄ）：ルータＤからルータキャストパケット（□ＡＢＤ）を受信したルータＡは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。ルータＤからルータキャストパケット（□ＡＢＤ）を受信したルータＣは、その経由ルータテーブルを参照したが、自身のアドレスがないのでそれを追加し、ルータＢに転送する（□ＡＢＤＣ）。ルータＣからルータキャストパケット（□ＡＢＣ）を受信したルータＤは、その経由ルータテーブルを参照したが、自身のアドレスがないのでそれを追加し、ルータＡ，Ｂに転送する（□ＡＢＣＤ）。一方、単純マルチキャストパケットは相変わらず単純に転送される。
【００３９】
図２の（ｅ）：ルータＤからルータキャストパケット（□ＡＢＣＤ）を受信したルータＡは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。ルータＣからルータキャストパケット（□ＡＢＤＣ）を受信したルータＢは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。ルータＤからルータキャストパケット（□ＡＢＣＤ）を受信したルータＢは、その経由ルータテーブルを参照したところ、その中に自身のアドレスが登録されていることを発見したため、これを廃棄する。これにより、ルータキャストパケットはなくなる。一方、単純マルチキャストパケットは単純転送される。
【００４０】
以降は、寿命が尽きるまで単純マルチキャストパケットは転送され続ける。しかも、増殖を続ける。
【００４１】
以上の例で見たように、単純マルチキャスト方式ではＴＴＬ（Time to Live：パケットの有効期間）が尽きるまで無駄なパケット巡回が発生してしまうが、ルータキャスト方式ではパケットの巡回は発生せず、ひとつのメッセージ転送における重複は最小限に抑えられる。
【００４２】
（２）ルーティングポリシーの動的切り替え
ネットワークの状態に応じてスタティックルーティングとダイナミックルーティングを使い分けるための方式について説明する。この方式は、（Ａ）障害の有無の検出、（Ｂ）障害の通知、（Ｃ）ルーティング方式の切り替えの３つの機構で構成される。
【００４３】
（Ａ）障害の有無の検出
ユーザは正常時におけるネットワーク構成を「ネットワーク構成情報」としてルータに登録しておく。ルータは登録された構成を常時監視し、一部でも問題があればネットワークの障害であると判断する。
【００４４】
ネットワーク構成情報は、図１中に示すように、そのルータに接続されているべきルータ、接続されているべきインタフェース、およびそのリンク状態をもってひとつのエントリとする、エントリテーブルである。図３を参照して以下に例を示す。
【００４５】
図３の（ａ）には、Ａ，Ｂ，Ｃ，Ｄの４つのルータがネットワーク上に存在する場合を示し、丸数字はインタフェースをそれぞれ示している。
【００４６】
ユーザはネットワークの運用を開始する前に、このネットワーク構成を各ルータに設定しておく。設定が完了すると、各ルータのネットワーク構成情報は図３の（ｂ）のようになる。なお、ネットワークの運用前なのでリンク情報は未定‘？’となっている。ネットワークの運用が開始されたら、リンク状態は正常（○）か異常（×）のいずれかとなる。
【００４７】
運用が開始されると各ルータは経路情報を通知するためにルーティングパケットの交換を開始する。これにより、登録されたルータが然るべきインタフェースに接続されているかどうかを確認できる。詳細なリンク状態判定基準（ルール）を以下に示す。
【００４８】
（ルール１）ハードウェア的にリンクステータスをモニタできる場合には、モニタされたリンクステータスがＯＦＦであればリンク状態を異常と判断する。リンクステータスがＯＮであった場合には以降の条件で判断する。なお、リンクステータスがＯＮであっても、実際にネットワーク構成情報で設定されたルータが正しく接続されている証拠とはならない。
【００４９】
（ルール２）標準的には、ネットワーク運用開始直後はリンク状態を正常とみなす。この条件は、正常なネットワークであっても運用を開始してから実際にルーティングパケットを受信するまでにはタイムラグがあるので、その期間を異常と判断するのは適切でないことによる。ユーザのネットワーク運用ポリシーによっては異常と判断してもよいが、少なくとも運用するネットワーク内では初期値を「正常」か「異常」のどちらかに統一しておく。
【００５０】
（ルール３）ネットワーク構成情報で設定されたルータからのルーティングパケットが設定されたインタフェースで受信されたら、リンク状態が正常であるとの判断が維持される。
【００５１】
（ルール４）ネットワーク構成情報で設定されたルータからのルーティングパケットが設定されたインタフェースで受信されない状態が所定の時間以上続いた場合には、そのリンク状態が異常であると判断する。
【００５２】
図３の例では、ネットワークに問題がなければ各インタフェースでルーティングパケットが受信されるのでネットワーク構成情報のリンク状態は図４のように更新される。
【００５３】
次に、各ルータは自身に登録されたネットワーク構成情報の各エントリのリンク状態を常時更新し、その結果をもとにネットワークの障害を以下のように検出する。
【００５４】
（ルール５）自身に登録されたネットワーク構成情報のエントリのリンク状態がひとつでも異常であるならば、そのルータはこれをネットワークの障害として検出する。
【００５５】
図４の例で見ると、ルータＡ，Ｂ，Ｃ，Ｄの各ネットワーク構成情報のリンク状態はみな正常（○）なので、どのルータもネットワークの障害は検出していない。ここで、図５に示すように、仮にルータＣ−Ｄ間で断線が発生したとする。
【００５６】
この断線によって、ルータＣはインタフェース「丸数字４」で受け取っていたルータＤからのルーティングパケットを受信しなくなり、またルータＤはインタフェース「丸数字９」で受け取っていたルータＣからのルーティングパケットを受信しなくなる。この状態になって所定の時間が経過したら、ルータＣ、Ｄはネットワーク構成情報の該当エントリのリンク状態を異常「×」として更新する（図５の（ｂ）参照）。
【００５７】
ルータＣおよびＤは、ネットワーク構成情報においてリンク状態が異常であるエントリがあるため、ネットワークの障害として検出される。
【００５８】
このように、事前に設定されたネットワーク構成が実際の構成上で機能しない場合にネットワーク障害として検出することができる。
【００５９】
（Ｂ）障害の通知
ここでは、あるルータがネットワークの障害に気が付いたときにそれをネットワーク中の各ルータに通知するための手続きについて規定する。
【００６０】
ルーティングポリシーの管理を適切に行なうためには、ネットワーク中の全てのルータがネットワークの障害発生の有無について、共通した認識を持っていなければならない。すなわち、共通した認識を持っていれば、それが間違った認識であったとしても、重大な通信障害のもとになることはない。なお、通信できないパスがあるかもしれないが、設定に誤りさえなければ、転送経路がループ化した状態で落ち着いてしまうことはない。
【００６１】
図６の（ａ）に図５の（ａ）と同じ状態を示すように、ルータＣ−Ｄ間の断線が発生すると、ルーティングパケットの受信停止によってルータＣ，Ｄはネットワークの障害を検出することができるが、ルータＡ，Ｂは障害発生箇所に隣接していないため、障害を検出することはできない。
【００６２】
そこで、障害の発生を他のルータにも知らせるために「ネットワーク状態通知パケット」を定義する。ネットワーク状態通知パケットは図１中に示すように、ＲＭＰパケット仕様に準拠し、以下の項目を設ける。
【００６３】
・転送形態＝ルータキャスト方式
・メッセージタイプ＝「ネットワーク状態通知メッセージ」
また、ネットワーク状態通知パケットは以下の固有のパラメータを持つ。
【００６４】
・障害検出フラグ＝ネットワーク障害の有無を示す。障害ありの場合にセットする。
【００６５】
ネットワーク状態通知パケットは以下のように運用される。
【００６６】
・前記の障害の検出の機構によって、ネットワークの障害を検出した状態のルータは、障害検出フラグをセットしたネットワーク状態通知パケットを定期的に送信し続ける。
【００６７】
・前記の障害の検出の機構によって、ネットワークの障害を検出しなくなったルータは、障害検出フラグをセットしたネットワーク状態通知パケットの定期送信を中止する。
【００６８】
・「ネットワーク異常」（以下の説明参照）と判断された状態において、一定期間以上、ネットワークの障害を通知されない場合（つまり、障害検出フラグがセットされたネットワーク状態通知パケットを受信しなかった場合）には、障害検出フラグをクリアしたネットワーク状態通知バケットを発信する。
【００６９】
ルータは、ネットワークの状態が正常であるか異常であるかについて以下のように判断する。
【００７０】
（ルール１）前記の障害の検出機構によってネットワークの障害を検出した場合には「ネットワーク異常」と判断する。
【００７１】
（ルール２）障害検出フラグがセットされたネットワーク障害通知パケットを受信した場合にも「ネットワーク異常」と判断する。
【００７２】
（ルール３）前記の障害の検出の機構によってネットワークの障害を検出しておらず、尚且つ、障害検出フラグがセットされたネットワーク状態通知パケットを一定期間以上受信しておらず、尚且つ、障害検出フラグがクリアされたネットワーク状態通知パケットを受信した場合には「ネットワーク正常」と判断する。
【００７３】
図６を参照して、障害発生通知の動作例を示す。
【００７４】
図６の（ａ）：障害発生状態を示す。
【００７５】
図６の（ｂ）および図６の（ｃ）：ルータＣ，Ｄはネットワーク障害を検出し、前記のルータキャスト方式で障害をネットワーク全体に通知する。図中の下線付きルータは「ネットワーク異常」と判断したルータを示す。
【００７６】
ルータＣ，Ｄはネットワーク状態通知パケット（障害検出フラグ＝セット）を定期的に送信する。
【００７７】
図６の（ｄ）：ルータＣ−Ｄ間の断線が回復したとき、ルータＣ，Ｄはネットワークの障害を検出しない状態となったため、障害検出フラグをセットしたネットワーク状態通知パケットの送信を中止し、ネットワーク状態通知パケットの定期送信が途絶え、静かな状態となる。ただし、いずれのルータも未だに「ネットワーク異常」と認識している。
【００７８】
上記の状態にて所定の時間が経過し、障害検出フラグをクリアしたネットワーク状態通知パケットを任意のルータが送信する。冗長な送信を避けるために、各ルータがランダムなタイミングで同パケットを送信し、他のルータが先に同パケットを送信した場合には自身の送信を控えるのが望ましい（誰かひとりがこれを系全体に通知すればよい）。
【００７９】
図６の（ｅ）：各ルータは「ネットワーク正常」と認識するようになる。
【００８０】
（Ｃ）ルーティング方式の切り替え
前記の（Ａ）障害の有無検知と（Ｂ）障害の通知の機構により、各ルータはネットワークの正常・異常を正しく判断できる。この判断に基づいてルーティングポリシーを以下のように運用する。
【００８１】
（ルール１）「ネットワーク正常」の場合はスタティックルーティングを行なう。
【００８２】
（ルール２）「ネットワーク異常」の場合はダイナミックルーティングを行なう。
【００８３】
これにより、ネットワークが正常である限り、ユーザが想定した経路に基づいてパケットが中継される。また、障害が発生した場合には、ダイナミックルーティングに切り替えられるために、障害箇所の迂回経路が自動的に組まれて通信状態が維持される。
【００８４】
（３）複数のスタティックルーティングエントリの運用
前記までは、障害発生時にダイナミックルーティングに切り替える方式を示したが、以下には障害が起きても想定外の中継経路が組まれないようにするための方式を示す。この方式では、各ルータはスタティックルーティングのときに使用する中継経路をひとつではなく、複数の設定を可能とし、実際のネットワーク上に展開可能な経路設定を選んでルーティングを行なう。
【００８５】
（Ａ）経路情報の設定
図１中に示すように、スタティックルーティングで使用するルーティングテーブルをルータに設定する。このテーブルには、デフォルトで使用するルーティングテーブルの他に、障害などによってデフォルト経路が使用不可になった場合に使用する代替ルーティングテーブルをひとつあるいは複数を登録可能とする。全てのルーティングテーブルにはＩＤが割り当てられ、デフォルトのルーティングテーブルにはＩＤ＝０を割り当てる。
【００８６】
ルーティングは常に同じＩＤを持つルーティングテーブルに基づいて行なわれるので、同一ＩＤのルーティングテーブルにおいて転送ループなどの矛盾のないように注意深く設定を行なう必要がある。ネットワークにおける全てのルータにルーティングテーブルを設定したら運用を開始する。
【００８７】
図７に例を示す。図７の（ａ）に示すルーティング状態において、仮に、Ａ−Ｂ，Ｂ−Ｃ，Ｂ−Ｄ間が高速、Ａ−Ｄ間が中速、Ｃ−Ｄ間が低速とする。このネットワークに従来のＲＩＰをそのまま適用すると、ホップ数が短いという理由で高速であるにもかかわらず、低速なパスを含む転送経路が組まれるため、図７の（ｂ）に例を示すように、ユーザは複数の静的な経路情報を設定したとする。
【００８８】
図７の（ｂ）に示すルーティングテーブルは、各ルータＡ，Ｂ，Ｃ，Ｄの左側はネットワークを示し、右側の数字はそのネットワーク宛てのパケットを転送すべきインタフェースを示す。この例では、ルータＡにネットワークａ、ルータＢにネットワークｂ、ルータＣにネットワークｃが接続されているものとする。例えば、ルータＢがネットワークｄ宛てのパケットを受信したら、これをインタフェース「丸数字７」へ転送する（ＩＤ＝０の場合）。
【００８９】
（Ｂ）デフォルトルーティングテーブル（ＩＤ＝０）に基づいて運用開始
ＩＤ＝０のルーティングテーブルに基づいて運用を開始する。この時点では、デフォルトルーティングテーブルによるルーティングが完全に機能するかどうか分からない。もしかしたら、ある経路が断線しているため、一部のパケットが宛て先に届かない可能性もある。
【００９０】
ただし、設定そのものに問題がない限り、ネットワークが正常であろうとなかろうと、少なくとも中継がループしてしまうおそれはない。なぜならば、ネットワークが正常なときにループになってしまうならば、それは設定のミスであり、ネットワークが異常なときにはリンクの欠損が発生するので、ループが発生するはずがないからである。
【００９１】
（Ｃ）ルーティングテーブルの検査
スタティックルーティングを開始したら、ルータは現在運用している中継経路に問題がないかどうか確かめなくてはならない。そこで、中継経路のチェックを行なうために「ルートスキャンパケット」を定義する。ルートスキャンパケットは図１中に示すように、ＲＭＰパケット仕様に準拠し、以下の項目を設ける。
【００９２】
・転送形態＝ユニキャスト方式（ネットワークを宛て先とする）
・メッセージタイプ＝「ルートスキャンメッセージ」
また、ルートスキャンパケットは以下の固有のパラメータを持つ。
【００９３】
・ルーティングテーブルＩＤ＝チェックする経路情報のＩＤ
ルータはルートスキャンパケットを次の手順で運用する。
【００９４】
（ｓｔｅｐ１）ルータに登録されている宛て先ネットワーク全てに対してルートスキャンパケットを送信して返事を待つ。
【００９５】
（ｓｔｅｐ２）ルートスキャンパケットを受信したルータはそれを中継する。ただし、ルーティングするのに使用するルーティングテーブルはそのパケットに含まれているルーティングテーブルＩＤで指定されたルーティングテーブルとする。もし仮に、一般フレームがＩＤ＝０のルーティングテーブルに基づいてルーティングされている状態において、ＩＤ＝１のルートスキャンパケットが受信されたら、このパケットだけはＩＤ＝１のルーティングテーブルに基づいて中継される。
【００９６】
（ｓｔｅｐ３）ルートスキャンパケットは中継されてゆき、やがて宛て先ネットワークに直接接続されたルータがこのパケットを受け取る。このルータはそれをネットワークには転送せずに送信元ルータに返信する。
【００９７】
（ｓｔｅｐ４）自分が送信したルートスキャンパケットに対する返信を受け取ったルータは、その経路が機能していると判断し、ルーティングテーブルの該当エントリに○印を付ける。
【００９８】
（ｓｔｅｐ５）自分が送信したルートスキャンパケットに対する返信を受け取らずに一定期間が経過したら再送する。
【００９９】
（ｓｔｅｐ６）ルートスキャンパケットの返事を所定回数以上連続して受け取れない場合には、その経路がだめであると判断し、ルーティングテーブルの該当エントリに×印を付ける。
【０１００】
（ｓｔｅｐ７）この経路チェックを絶えず継続する。
【０１０１】
この手順でルーティングテーブルをチェックし、全てのエントリに○か×を付けてゆく。全てのエントリに○印がついている場合にはその経路情報でのルーティングを継続することができる。
【０１０２】
図８は、図７の状態の例を用いて経路制御の行なわれる様子を示す。仮にＩＤ＝０に基づいてルーティングしているとし、ここでルータＡによる経路スキャンに注目する。なお、同様の経路スキャンを他のルータも行なっているが、簡単のためこの例題では表記しない。
【０１０３】
図８の（ａ）：ルータＡはネットワークｂ，ｃ，ｄ宛てにルートスキャンパケットを送信する。ルータＡのＩＤ＝０の経路情報によれば、いずれのネットワークもインタフェース「丸数字１」がアサインされているので、これらのパケットはこのインタフェースから送信される。これらのルートスキャンパケットの経路情報ＩＤにはいずれも０がセットされている。
【０１０４】
図８の（ｂ）：ルータＢは自身のルーティングテーブルに基づいてルートスキャンパケットを処理する。ネットワークｃ，ｄ宛てのルートスキャンパケットはそれぞれインタフェース「丸数字５」、「丸数字７」へ転送される。また、ネットワークｂ宛てのルートスキャンパケットは自身の管理するネットワーク宛てであるので、これをルータＡに対して返信する（宛て先がルータＡに書き換えられる）。
【０１０５】
図８の（ｃ）：ルータＡはネットワークｂ宛てに送ったルートスキャンパケットの返信を確認したので、ルーティングテーブルの該当エントリは正常であると判断し、○印を付ける。また、ルータＣ，Ｄはそれぞれ自身の管理するネットワーク宛てのルートスキャンパケットを受信したので、これをルータＡに対して返信する。
【０１０６】
図８の（ｄ）：ルータＢはルータＡ宛てのルークスキャンパケットを受信したので、これをルータＡに転送する。
【０１０７】
図８の（ｅ）：ルータＡはネットワークｃ，ｄ宛てに送ったルートスキャンパケットの返信を確認したので、ルーティングテーブルの該当エントリは正常であると判断し、○印を付ける。
【０１０８】
以上のように、ルータＡのルーティングテーブルの全てのエントリに○印がついたので、ルータＡはこのルーティングテーブルに基づいてルーティングを続けても問題ない。ただし、障害はいつ発生するかわからないので、定期的にチェックを行なう必要がある。
【０１０９】
仮に、ルータＢ−Ｄ間が断線していた場合には上記の図８の（ｂ）〜（ｅ）は以下のようになる。
【０１１０】
図８の（ｂ）：ルータＡからネットワークｄ宛てのルートスキャンパケットを受信したルータＢはＩＤ＝０のルーティングテーブルに基づいてインタフェース「丸数字７」にこれを転送する。
【０１１１】
図８の（ｃ）：Ｂ−Ｄ間は断線しているため、ルータＢが転送したネットワークｄ宛てルートスキャンパケットはルータＤに届かないため、ルータＤは何もしない。
【０１１２】
図８の（ｄ）：ネットワークｄ宛てのルートスキャンパケットは既にネットワーク中には存在しない。
【０１１３】
図８の（ｅ）：ネットワークｄ宛てに送ったルートスキャンパケットの返事が来ないため、ルータＡは（何度かリトライした後に）該当エントリに×印を添付する。この結果、ルーティングテーブル（ＩＤ＝０）は、図９のようになる。
【０１１４】
これでルータＡはＩＤ＝０のルーティングテーブルを使っていたのでは、一部のパスが無効であることに気が付く。
【０１１５】
（Ｄ）ルーティングテーブルの切り替え手続き
ルーティングテーブルを検査した結果、その中に無効なパスを発見したルータは、代替経路で有効なものを探し出し、見つかったらルーティングテーブルをそのシリーズにするように系全体にアピールする。アピールが認められたら、系全体のルーティングテーブルを一斉に変更する。
【０１１６】
以下に詳細な手順を示すが、この手続きを行なうために「ルート変更パケット」を定義する。ルート変更パケットは、図１中にも示すように、ＲＭＰパケット仕様に準拠し、以下の項目を設ける。
【０１１７】
・転送形態＝ルータキャスト方式
・メッセージタイプ＝「ルート変更メッセージ」
また、ルートスキャンパケットは以下の固有のパラメータを持つ。
【０１１８】
・ルーティングテーブルＩＤ＝この変更手続きで対象となっているルーティングテーブルＩＤ
・コマンド＝変更手続き上のコマンド。「要求」「拒否」「実施」のいずれか。
【０１１９】
このルート変更パケットを使用したルーティングテーブルの切り替えには、以下の手順によって行われる。
【０１２０】
（ｓｔｅｐ１）代替ルーティングテーブルの検索
前記の（Ｃ）ルーティングテーブルの検査によって現行のルーティングテーブルに欠陥を見つけたルータは、他に有効なルーティングテーブルがないかどうか、同様の手順を駆使して検索する。代替ルーティングテーブルの検索はＩＤの小さい方から順次行なってゆく（ただし、現行のテーブルを除く）。仮に、ＩＤ＝０でのルーティングに問題があれば、ＩＤ＝１，２，３，…の順番でルーティングテーブルを検索してゆく。ルーティングテーブルの検査における手順は（Ｃ）ルーティングテーブルの検査で示した通りである。有効な代替ルーティングテーブルが見つかったら、次のステップへと進む。見つからなかった場合にはルーティングテーブルの変更をあきらめる。
【０１２１】
（ｓｔｅｐ２）ルーティングテーブル変更アピール
有効な代替ルーティングテーブルが見つかったら、そのルータはこのルーティングテーブルの採用をネットワーク全体にアピールする。そのルータは前記のルート変更パケットを送信する。ここで、ルーティングテーブルＩＤには採用を希望するルーティングテーブルＩＤ、コマンドには「要求」をそれぞれセットする。以降、アピールが受け入れられるか、あるいは明示的に拒否を示されるまで、このＩＤに対するアピールを繰り返す。
【０１２２】
（ｓｔｅｐ３）アピールされたＩＤの検査
ルート変更パケットによって、ネットワークの各ルータは要求されたＩＤのルーティングテーブルが自身にとっても有効かどうかを検査する。検査方法は前記の（Ｃ）ルーティングテーブルの検査で示した通りである。もし、そのルーティングテーブルでは無効なパスがあることが分かったルータは、そのルーティングテーブルに対して拒否を示すためにルート変更パケットを送信する。ここで、ルーティングテーブルＩＤには拒否するルーティングテーブルのＩＤ、コマンドを「拒否」をそれぞれセットする。アピールされたルーティングテーブルでも問題ないことが分かったルータは、現行のルーティングを続けながら、変更アピール手続きでの次のアクションを待つ。
【０１２３】
（ｓｔｅｐ４）ルーティングテーブルの変更
変更を希望するルータがルート変更「要求」パケットを送信し始めてから所定の時間が経過し、その間にルート変更「拒否」パケットを受信しなかった場合には、そのルータはアピールが受け入れられたと判断し、ルート変更パケットを送信する。ここで、ルーティングテーブルＩＤにはアピールしていたルーティングテーブルＩＤ、コマンドには「実施」をセットする。この後、同ルータはこのルート変更「実施」パケットを定期的に送信し、そのルーティングテーブルが採用された状態を維持する。もし、その必要がなくなった場合にはこのパケットの定期送信を中止する。
【０１２４】
（ｓｔｅｐ５）ルーティングテーブルの変更拒否
もし、アピール期間中にルート変更「拒否」パケットを受信した場合に、このルーティングテーブルへの変更はあきらめて、別の代替ルーティングテーブルの検索工程に戻る。別の代替ルーティングテーブルが見つかったら、同様の手順でそのルーティングテーブルに対する採用アピールを行なう。
【０１２５】
以上の手順になるルーティングテーブル変更手続きの例を図１０、図１１を参照して以下に説明する。前記の（Ｃ）ルーティングテーブルの検査の例のように、Ｂ−Ｄ間で断線が発生し、たまたまルータＡがそれに最初に気が付いたとする。なお、経路チェックは各ルータが定期的に行なっており、それらは非同期であるので、誰が最初に気が付くかは不定となる。
【０１２６】
図１０の（ａ）：ルータＡはＩＤ＝０のルーティングテーブルに問題を見つけたので、ＩＤ＝１のルーティングテーブルの有効性について調査する。ＩＤ＝１のテーブルに基づいて、ネットワークｂ，ｃ，ｄ宛てのルートスキャンパケットがインタフェース「丸数字２」から送信された。以降の手順は（Ｃ）ルーティングテーブルの検査で示した通りである。
【０１２７】
図１０の（ｂ）：上記の検査において、ネットワークｂ，ｃ宛てに送信したルートスキャンパケットは、ルータＤにおいてインタフェース「丸数字８」に転送されてしまうため、ルータＢ，Ｃへ到達することなく消滅する。従って、（何度かリトライした後に）ルータＡのテーブルは図示のようにチェックされる。
【０１２８】
図１０の（ｃ）：ＩＤ＝１のルーティングテーブルではだめなことがわかったので、ルータＡは次にＩＤ＝２のルーティングテーブルのチェックを行なう。手順は前述の通りである。
【０１２９】
図１１の（ａ）：上記の検査の結果、この経路では問題ないことが判明した。
【０１３０】
図１１の（ｂ）：ルータＡはＩＤ＝２に対するルート変更「要求」パケットを送信する。同バケットの転送手順は以前に説明した通りである。
【０１３１】
このとき、ネットワーク中のルータＢ，Ｃ，Ｄはルート変更「要求」パケットを受信したので、それぞれがＩＤ＝２のルーティングテーブルのチェックを開始する。手順は以前に示した通りである。
【０１３２】
図１１の（ｃ）：ルータＢ，Ｃ，ＤはそれぞれＩＤ＝２のルーティングテーブルの調査結果をルーティングテーブルに書き込む。いずれのルータにおいても×印はつかなかったので、この提案に対して異を唱えるルータは現れない。
【０１３３】
図１１の（ｄ）：アピール期間が経過し、旦つアピールが拒否されなかったので、ルータＡはルート変更「実施」パケットを送信する。また、ルータＡは自身のルーティングテーブルをＩＤ＝２のものに変更する。
【０１３４】
次に、ルート変更「実施」パケットを受信したルータＢ，Ｃ，Ｄは、アピールが実行に移されたことを知ったので、さっそく各自のルーティングテーブルをＩＤ＝２のものに変更する。
【０１３５】
さらに、ＩＤ＝２のルーティングテーブルに基づくルーティングが開始され、ユーザが設定した通りの障害迂回経路に基づいてパケット中継が行なわれるようになる。
【０１３６】
（５）デフォルト経路情報への復帰
ネットワークに障害がなければ、デフォルトルーティングテーブルに基づくルーティングがもっとも望ましい。そこで、ルーティングテーブルがデフォルト以外のルーティングテーブルに遷移したあとでネットワークの障害が回復した場合に、デフォルトルーティングテーブルによる経路制御に戻る手段を設ける。
【０１３７】
前記の（４）ルーティングテーブルの切り替え手続で示したように、ルーティングテーブルの変更状態維持を望むルータは定期的にルート変更「実施」パケットを送信し続ける。このルータは変更状態を維持する一方、デフォルトルーティングテーブルでのルーティングが回復するのを監視するため、定期的にＩＤ＝０のルーティングテーブルを検査する。検査方法は前記の（Ｃ）ルーティングテーブル検査方法で示した通りである。
【０１３８】
もしも、ＩＤ＝０でのルーティングに問題ないことが判明したら、そのルータはルート変更「実施」パケットの定期送信を中止する。
【０１３９】
もし、他にもそのＩＤのルーティングテーブルによるルーティングを望むルータがいれば、ルート変更「実施」パケットの定期送信はそのルータに引き継がれ、引き続きその状態が維持される。
【０１４０】
もし、他にだれもそのＩＤのルーティングテーブルによるルーティングを特に希望しない場合には、ネットワークにルート変更「実施」パケットを送信するものがいなくなる。
【０１４１】
ルート変更「実施」パケットが一定期間以上途絶えた場合には、ネットワーク中の任意のルータがＩＤ＝０のルーティングテーブルへ変更するためのアピールを開始する。ＩＤ＝０へのルーティングテーブルへの変更に対するアピールがなされたら、他のルータはさっそくＩＤ＝０のルーティングテーブルのチェックを開始する。その結果、ＩＤ＝０のルーティングテーブルでは問題のあることがわかったルータは、ＩＤ＝０に対するルート変更「拒否」パケットを発信する。なお、ＩＤ＝０でのルーティングに問題のあるルータは現行のＩＤのルーティングテーブルによるルーティングを維持するため、前述のルート変更「実施」パケットを定期的に送信し続けなけばならない。
【０１４２】
ＩＤ＝０への変更に異議を唱えるルータがいなければ、アピール期間が満了した後に、アピールが実施に移されるのは、既に説明した通りである。
【０１４３】
なお、デフォルト経路情報に戻った場合には、ＩＤ＝０に対するルート変更「実施」パケットの定期送信は必要ない。ルート変更「実施」パケットの定期送信はＩＤ≠０であるルーティングテーブルに基づくルーティングを維持したい場合にのみ必要とする。
【図面の簡単な説明】
【０１４４】
【図１】本発明の実施形態を示すルータＲＡ、ＲＢと各種パケットの例。
【図２】ルータキャスト方式のネットワーク構成例。
【図３】４つのルータ構成とネットワーク構成情報の例。
【図４】ネットワーク構成とリンク状態の変化例。
【図５】ネットワークの断線とリンク状態の変化例。
【図６】ネットワーク障害時の通知の例。
【図７】ルーティング状態における経路情報の設定例。
【図８】ルーティング状態における経路制御の例。
【図９】ルーティングの定期的なチェック結果による経路状態の例。
【図１０】ルーティングテーブル変更手続きの例（その１）。
【図１１】ルーティングテーブル変更手続きの例（その２）。
【符号の説明】
【０１４５】
ＲＡ、ＲＢ  ルータ
【図１】
2007288464.tif 000003
【図２】
2007288464.tif 000004
【図３】
2007288464.tif 000005
【図４】
2007288464.tif 000006
【図５】
2007288464.tif 000007
【図６】
2007288464.tif 000008
【図７】
2007288464.tif 000009
【図８】
2007288464.tif 000010
【図９】
2007288464.tif 000011
【図１０】
2007288464.tif 000012
【図１１】
2007288464.tif 000013