(57)【特許請求の範囲】
【請求項１】
中継するパケットのＩＰヘッダのオプション部分に、指名ルータを通過したことを示す情報を書き込む書込部を有する指名ルータと、
受信したパケットのＩＰヘッダのオプション部分に前記指名ルータを通過したことを示す情報が書き込まれているか監視する監視部と、前記監視部による監視の結果、前記指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値の期間以上受信されない場合、経路の再構築を行う再構築部と、を有するルータと、
を備えたことを特徴とする通信システム。
【請求項２】
前記ルータは、
前記監視部による監視の結果、指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値の期間以上受信されない場合、前記指名ルータが不明な状態であることを他のルータへ通知する通知部をさらに有し、
前記再構築部は、前記通知部により前記指名ルータが不明な状態であることを通知してから所定のしきい値の期間を経過する間に前記指名ルータが動作していることを示す通知が受信できない場合、経路の再構築を行う
ことを特徴とする請求項１記載の通信システム。 
【請求項３】
前記通知部は、他のルータから指名ルータが不明な状態である通知を受信した場合、当該他のルータへしきい値を通知し、
前記再構築部は、前記通知部により前記指名ルータが不明な状態であることを通知してから前記しきい値および他のルータから通知されるしきい値のうち、最大のしきい値の期間を経過する間に前記指名ルータが動作していることを示す通知が受信できない場合、経路の再構築を行う
ことを特徴とする請求項２記載の通信システム。 
【請求項４】
前記指名ルータは、
各ルータへ中継するパケットの送信間隔が前記しきい値以上となることが予測される場合、ＩＰヘッダのオプション部分に、指名ルータを通過したことを示す情報を書き込んだパケットを送信する制御を行う送信部をさらに有することを特徴とする請求項１または請求項２に記載の通信システム。 
【請求項５】
指名ルータに選出された場合、中継するパケットのＩＰヘッダのオプション部分に、指名ルータを通過したことを示す情報を書き込む書込部と、
指名ルータに選出されていない場合、受信したパケットのＩＰヘッダのオプション部分に前記指名ルータを通過したことを示す情報が書き込まれているか監視する監視部と、
前記監視部による監視の結果、前記指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値の期間以上受信されない場合、経路の再構築を行う再構築部と、
を有することを特徴とするルータ。 
【請求項６】
指名ルータが、
中継するパケットのＩＰヘッダのオプション部分に、指名ルータを通過したことを示す情報を書き込み、
指名ルータと隣接関係にあるルータが、
受信したパケットのＩＰヘッダのオプション部分に前記指名ルータを通過したことを示す情報が書き込まれているか監視し、
監視の結果、前記指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値の期間以上受信されない場合、経路の再構築を行う、
ことを特徴とする通信方法。 
【請求項７】
指名ルータに選出された場合、中継するパケットのＩＰヘッダのオプション部分に、指名ルータを通過したことを示す情報を書き込み、
指名ルータに選出されていない場合、受信したパケットのＩＰヘッダのオプション部分に前記指名ルータを通過したことを示す情報が書き込まれているか監視し、
監視の結果、前記指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値の期間以上受信されない場合、経路の再構築を行う、
各処理を実行させることを特徴とするルータの制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システム、ルータ、通信方法および制御プログラムに関する。
【背景技術】
【０００２】
近年のＩＰ（Internet  Protocol）技術の高度化に伴い、通信ネットワークのＩＰ化が進んでいる。そして、通信ネットワークにおけるルーティング方式としてＯＳＰＦ(Open  Shortest  Path  First)が知られている。
【０００３】
ＯＳＰＦは、それまでの既存のルーティングプロトコルであるＲＩＰ(Routing  Information  Protocol)やＥＩＧＲＰ(Enhanced  Interior  Gateway  Routing  Protocol)などのディスタンスベクタ型ルーティングプロトコルに代わる、リンクステート型ルーティングプロトコルとして開発された。ディスタンスベクタ型ルーティングプロトコルは、経由するルータ数が最小となるようにルーティングを行う方式である。ディスタンスベクタ型ルーティングプロトコルは、大規模なネットワークに適用した場合、ルーティングループが発生したり、ネットワークの障害情報を更新すると更新情報を行き渡らせるコンバージェンス時間が更新間隔とホップ数の積で長くなるなどの欠点がある。
【０００４】
ＯＳＰＦは、これらの課題を解決するために、経路の評価基準としてホップ数ではなく「コスト」を用い、それに基づきルーティングを行い、経路情報に変更があれば即座にＯＳＰＦルータへマルチキャストで通知する方式を取っている。ＯＳＰＦルータは、まず、ＯＳＰＦルータ同士でＨｅｌｌｏパケットと呼ばれるＯＳＰＦのメッセージパケットを用いて隣接関係を確立し、その隣接ルータ同士でＬＳＡ(Link  State  Advertisement)パケットを用いて経路情報を交換する。経路情報は、そのルータへ接続されている回線の相手ルータのアドレス及びコスト値である。コスト値は、回線の帯域や管理者の判断によって任意に設定可能である。最初の立ち上げ時のみ、すべてのＯＳＰＦルータは、同一のルーティングテーブルを持つために、すべての経路情報を交換するが、以降は経路の変更があったときに、その差分情報を交換する。
【０００５】
ディスタンスベクタ型ルーティングプロトコルは、ネットワークが大規模になると、隣接関係の数の増大により経路情報の交換数が大きくなる。例えば、ｎ台のルータが同じブロードキャストネットワークを共有しており、全てのルータが他のルータとルーティング情報を交換する場合、ｎ（ｎ−１）／２通りの交換が行われる計算となる。よって、ルータの台数ｎが多くなるほど発生するトラフィックも増加する。
【０００６】
ＯＳＰＦは、トラフィックの増加を抑えるため、統括して管理する指名ルータ（ＤＲ：Designated  Router）を選出し、指名ルータ以外のルータと指名ルータとが隣接関係を構築する方法が備わっている。この方法によりルーティングトラフィックは大幅に削減され、経路情報の交換は２（ｎ−１）−１通りとなる。指名ルータの選出は、Ｈｅｌｌｏパケットの交換によって行う。ＯＳＰＦでは、例えば、Ｈｅｌｌｏパケットにより全ルータの中でＯＳＰＦプライオリティ値が最も高いものを指名ルータと選出する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】John  T.  Moy,  “OSPF  Version  2,”  Request  For  Comments  (Standard)  RFC  2328,  Internet  Engineering  Task  Force,  April  1998.
【非特許文献２】John  T.  Moy,  “OSPF  :Anatomy  of  an  Internet  Routing  Protocol”,  Addison-Wesley  Professional,  February  1998.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＯＳＰＦでは、回線断等の経路状態に変更があった場合、指名ルータへ変更された旨のＬＳＡパケットを通知する。指名ルータは、経路状態に変更があった旨の通知を受けると、管理範囲の全ルータへ経路状態の変更を通知する。ＯＳＰＦでは、隣接ルータの生存確認にも、Ｈｅｌｌｏパケットを使用する。Ｈｅｌｌｏパケットは、一定間隔で隣接関係にあるルータへ送出される。標準設定では、一定間隔は１０秒間隔とされている。もし、ルータが正常に動作していれば、Ｈｅｌｌｏパケットを交換し合い、正常動作していることが確認される。もし、Ｈｅｌｌｏパケットを３回送り、相手の生存が確認できなければ、相手が動作停止していると判断して、経路情報の変更を行う。このとき、指名ルータを選出しているモードの場合は、指名ルータが機能を停止していることになるため、全ルータでＨｅｌｌｏパケットを交換し合い、指名ルータの再選出を行う。
【０００９】
Ｈｅｌｌｏパケットを使った生存確認法では、計３個のＨｅｌｌｏパケットを送出してさらに１０秒まって初めて生存確認を判断するため、生存を確認するまで時間が４０秒以上かかる。この時間間隔を、Router  Dead  Intervalと呼ぶ。指名ルータが機能を停止していれば、この間、指名ルータの管理範囲内において回線障害が発生した箇所を迂回する等のルーティングは不可能となる。したがって、この時間は、パケット遅延となる。
【００１０】
指名ルータを代替するため、バックアップ指名ルータ(ＢＤＲ:Backup  DR)を動作させる方法もある。バックアップ指名ルータは、常に指名ルータと同様に管理を行うが、直接、隣接ルータへ経路情報を通知しない。指名ルータからの通知が一定期間無いとき、指名ルータとなり通知を行い、バックアップ指名ルータの再選出を行う。
【００１１】
しかし、多重障害等により指名ルータとバックアップ指名ルータが同時に機能停止に陥ると、やはりRouter  Dead  Intervalが発生し、指名ルータとバックアップ指名ルータの再選出を行うため、その間、障害箇所を避けるルーティングの変更が不可能となる。その結果、通信ネットワークを介して他の装置と通信を行うアプリケーションへ一時的に支障を来たすことが考えられる。
【００１２】
また、ＯＳＰＦルータの間にレイヤ２ネットワーク(Ｌ２:Layer  2  Network)がある場合、Ｌ２で回線障害が発生したり、Ｌ２を越えた先のＯＳＰＦの指名ルータ及びバックアップ指名ルータが機能停止になった場合も同様にRouter  Dead  Intervalが発生する。
【００１３】
すなわち、ＯＳＰＦでは、回線断や指名ルータの異常等の経路に異常があった場合、経路の切替えに時間がかかり、パケット遅延が発生する場合がある。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、経路に異常があった場合に経路の切替えを速やかに行うことができる通信システム、ルータ、通信方法および制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本願の開示する通信システムは、中継するパケットのＩＰヘッダのオプション部分に、指名ルータを通過したことを示す情報を書き込む書込部を有する指名ルータと、受信したパケットのＩＰヘッダのオプション部分に前記指名ルータを通過したことを示す情報が書き込まれているか監視する監視部と、前記監視部による監視の結果、前記指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値以上受信されない場合、経路の再構築を行う再構築部と、を有するルータと、を備えたことを特徴とする。
【発明の効果】
【００１６】
本願の開示する通信システムの一つの態様によれば、経路に異常があった場合に経路の切替えを速やかに行うことができる。
【図面の簡単な説明】
【００１７】
【図１】図１は、通信システムの概略的な構成を示す図である。
【図２Ａ】図２Ａは、指名ルータに異常が発生した場合を示す図である。
【図２Ｂ】図２Ｂは、指名ルータとの間にあるＬ２スイッチに異常が発生した場合を示す図である。
【図３】図３は、指名ルータと隣接関係にあるルータの機能的構成を示すブロック図である。
【図４】図４は、ルータがＯＳＰＦにより指名ルータを選定する際の動作状態の遷移を示す図である。
【図５】図５は、完全状態となった以降の指名ルータの動作状態の遷移を示す図である。
【図６】図６は、完全状態となった以降のルータの動作状態の遷移を示す図である。
【図７】図７は、完全状態となった以降の指名ルータの処理の流れを示すフローチャートである。
【図８】図８は、完全状態となった以降のルータの処理の流れを示すフローチャートである。
【図９Ａ】図９Ａは、指名ルータに障害が発生した場合の動作を示す図である。
【図９Ｂ】図９Ｂは、指名ルータに障害が発生した場合の動作を示す図である。
【図９Ｃ】図９Ｃは、指名ルータに障害が発生した場合の動作を示す図である。
【図９Ｄ】図９Ｄは、指名ルータに障害が発生した場合の動作を示す図である。
【図９Ｅ】図９Ｅは、指名ルータに障害が発生した場合の動作を示す図である。
【図１０Ａ】図１０Ａは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【図１０Ｂ】図１０Ｂは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【図１０Ｃ】図１０Ｃは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【図１０Ｄ】図１０Ｄは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【図１０Ｅ】図１０Ｅは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【図１０Ｆ】図１０Ｆは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【図１１Ａ】図１１Ａは、回線を通るアプリケーションのパケットが少なくなった場合の動作を示す図である。
【図１１Ｂ】図１１Ｂは、回線を通るアプリケーションのパケットが少なくなった場合の動作を示す図である。
【図１１Ｃ】図１１Ｃは、回線を通るアプリケーションのパケットが少なくなった場合の動作を示す図である。
【図１１Ｄ】図１１Ｄは、回線を通るアプリケーションのパケットが少なくなった場合の動作を示す図である。
【図１２Ａ】図１２Ａは、パケットが喪失した場合の動作を示す図である。
【図１２Ｂ】図１２Ｂは、パケットが喪失した場合の動作を示す図である。
【図１２Ｃ】図１２Ｃは、パケットが喪失した場合の動作を示す図である。
【図１２Ｄ】図１２Ｄは、パケットが喪失した場合の動作を示す図である。
【図１２Ｅ】図１２Ｅは、パケットが喪失した場合の動作を示す図である。
【図１３】図１３は、制御プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１８】
以下に、本願の開示する通信システム、ルータ、通信方法および制御プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１９】
［システム構成］
まず、本実施例に係る通信システムの構成について説明する。図１は、通信システムの概略的な構成を示す図である。
【００２０】
図１に示す通信システム１０は、複数のネットワーク１１〜１４が接続されて構成されている。ネットワーク１１は、各ネットワーク１２〜１４を互いに接続する中枢のコアネットワークである。各ネットワーク１２〜１４は、ネットワーク１１に接続され、例えば、企業の拠点毎などに設けられたネットワークである。以下、ネットワーク１１は、「バックボーンネットワーク」とも言う。また、ネットワーク１２〜１４は、「ローカルネットワーク」とも言う。
【００２１】
ネットワーク１１〜１４には、複数のルータ２０が設けられている。ルータ２０は、ルーティング方式としてＯＳＰＦによりパケットのルーティングを行うことが可能とされている。本実施例では、ネットワーク１１〜１４を１つのエリアとして、ネットワーク１１〜１４に設けられた全てのルータ２０の中から指名ルータおよびバックアップ指名ルータを選出し、選出した指名ルータおよびバックアップ指名ルータにより各ルータ２０の経路情報を管理する。指名ルータとバックアップ指名ルータの選出は、Ｈｅｌｌｏパケットの交換によって行う。例えば、Ｈｅｌｌｏパケットにより全ルータの中でＯＳＰＦプライオリティ値が最も高いものを指名ルータ、２番目に高いものをバックアップ指名ルータとする。図１の例では、バックボーンネットワーク１１に設けられたルータ２０ａが指名ルータに選出され、バックボーンネットワーク１１に設けられたルータ２０ｂがバックアップ指名ルータに選出されている。指名ルータ２０ａとバックアップ指名ルータ２０ｂが選出されると、指名ルータ２０ａおよびバックアップ指名ルータ２０ｂ以外の各ルータ２０は、指名ルータ２０ａおよびバックアップ指名ルータ２０ｂと隣接関係を確立し、ＬＳＡパケットを用いて経路情報の交換を行う。
【００２２】
ここで、このようにネットワーク１１〜１４を１つのエリアとして指名ルータ２０ａおよびバックアップ指名ルータ２０ｂを選出した場合、指名ルータ２０ａおよびバックアップ指名ルータ２０ｂが同時に障害により機能停止に陥ると、ネットワーク全体で一定期間ルーティング変更を行えない状態が発生する場合がある。
【００２３】
しかし、ルータ２０は、何れかも指名ルータとして機能することが可能であり、指名ルータ２０ａが停止したとしても、他のルータ２０を指名ルータとして再選出することが可能である。このため、指名ルータ再選出のときに発生するRouter  Dead  Intervalを回避し、高速に経路切り替えができれば、通信システム１０を介して他の装置と通信を行うアプリケーションに支障が出ることを抑制できる。
【００２４】
Router  Dead  Intervalを短縮するために、生存確認を判断するため送信するＨｅｌｌｏパケットの間隔を小さくすることが考えられる。しかし、Ｈｅｌｌｏパケットの間隔を１０秒以下にすると、輻輳によりＨｅｌｌｏパケットの損失率が受容できないレベルとなる。また、輻輳を回避するためにルータにＲＥＤ(Random  Early  Detection)方式を機能させることも考えられるが、一般にＲＥＤを機能させるためのＲＥＤパラメータの調整はトラヒックパターンに依存し、最適に機能させるパラメータ設定は困難である。
【００２５】
ところで、通信システム１０では、回線断や指名ルータの異常等の経路に異常があった場合、次のような状態が発生する。図２Ａは、指名ルータに異常が発生した場合を示す図である。例えば、図２Ａに示すように、指名ルータ２０ａが異常となった場合は、Router  Dead  Intervalが発生し、各ルータ２０に指名ルータ２０ａ方向からのパケットが途絶する。
【００２６】
また、例えば、指名ルータ２０ａとルータ２０との間のネットワークにＬ２スイッチ２２があり、Ｌ２スイッチ２２部分において障害が発生する場合がある。図２Ｂは、指名ルータとの間にあるＬ２スイッチに異常が発生した場合を示す図である。例えば、図２Ｂに示すように、指名ルータ２０ａとの間にあるＬ２スイッチ２２が異常となった場合は、指名ルータ２０ａ方向からはＬ２スイッチ２２の制御パケットしか来なくなる。つまり、各ルータ２０は、指名ルータ２０ａ方向からのパケットを監視していれば、指名ルータ２０ａの生存確認ができる。
【００２７】
そこで、本実施の形態に係る通信システム１０では、Ｈｅｌｌｏパケットに頼らずに指名ルータ２０ａの生存確認を行うために、指名ルータ２０ａは、中継するパケットに指名ルータ２０ａを通過したことを示す情報を書き込む。例えば、指名ルータ２０ａは、中継するパケットのＩＰヘッダのオプション部分に、指名ルータ２０ａを通過したことを示す情報を書き込む。各ルータ２０は、受信したパケットに指名ルータ２０ａを通過したことを示す情報が書き込まれているか監視する。例えば、各ルータ２０は、受信したパケットのＩＰヘッダのオプション部分に指名ルータ２０ａを通過したことを示す情報が書き込まれているか監視する。このように、各ルータ２０が、受信したパケットに指名ルータ２０ａを通過したことを示す情報が書き込まれているか監視することにより、指名ルータ２０ａの生存確認を行うことができる。そして、各ルータ２０は、監視の結果、指名ルータを通過したことを示す情報が書き込まれたパケットが所定のしきい値以上受信されない場合、経路の再構築を行う。しきい値の詳細については、後述する。これにより、通信システム１０は、経路の切替えをより速やかに行うことができる。
【００２８】
［ルータ２０の構成］
続いて、本実施例に係る通信システム１０に含まれるルータ２０の機能的構成について説明する。なお、各ルータ２０は、それぞれ物理的な構成は略同様であり、指名ルータ２０ａに選択された場合、各ルータ２０と隣接関係を確立して経路情報の交換し、交換した経路情報に基づき、ＳＰＦ（Shortest  Path  First）アルゴリズムを用いてルーティングテーブルを作成し、作成したルーティングテーブルを各ルータ２０へ送信する。以下では、指名ルータ２０ａと、隣接関係にある１台のルータ２０についての機能的な構成について説明する。
【００２９】
図３は、指名ルータと隣接関係にあるルータの機能的構成を示すブロック図である。指名ルータ２０ａおよびルータ２０は、インタフェース部３０と、記憶部３１と、制御部３２とをそれぞれ有する。
【００３０】
インタフェース部３０は、不図示のポートを介して外部のネットワークとパケットを入出力するインタフェースである。
【００３１】
記憶部３１は、各種のデータを記憶する記憶デバイスである。例えば、記憶部３１は、制御部３２で実行されるパケットのルーティングを行うプログラムや、ＯＳＰＦ方式のルーティングプロトコルを用いて他のルータ２０とパケットを交換して指定ルータを選出するプログラム、指名ルータとして動作するためのプログラム、経路の異常を検出するプログラムなど各種プログラムを記憶する。さらに、記憶部３１は、ルーティングテーブルなど各種情報や、制御部３２で実行されるプログラムの実行に用いられる各種データを記憶する。本実施例に関係するデータとして、記憶部３１は、リンクステートエントリの情報や、ルーティングテーブル、しきい値、後述する許容時間などを記憶する。かかる記憶部３１の一態様としては、フラッシュメモリやＮＶＳＲＡＭ(Non  Volatile  Static  Random  Access  Memory)などのデータを書き換え可能な半導体メモリの他、ハードディスクや光ディスクなどの記憶装置を採用できる。
【００３２】
制御部３２は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。例えば、制御部３２は、ＯＳＰＦ方式のルーティングプロトコルを用いて他のルータ２０とパケットを交換して指定ルータの選出を行う。制御部３２は、指定ルータに選出された場合、他の各ルータ２０と隣接関係を確立し、各ルータ２０へ最新のリンクステートエントリが通知するなどルーティングの管理を行う。また、制御部３２は、最新のリンクステートエントリの情報からルーティングテーブルを作成し、作成したルーティングテーブルに基づき、インタフェース部３０に入力したパケットのルーティングを行う。制御部３２には、各種の集積回路や電子回路を採用できる。例えば、集積回路としては、ＡＳＩＣ（Application  Specific  Integrated  Circuit）が挙げられる。また、電子回路としては、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などが挙げられる。指名ルータ２０ａの制御部３２は、本実施例に関係する処理部として、書込部４０と、計測部４１と、算出部４２と、判定部４３と、送信部４４とを有する。また、ルータ２０の制御部３２は、本実施例に関係する処理部として、監視部５０と、計測部５１と、算出部５２と、解除部５３と、通知部５４と、再構築部５５とを有する。
【００３３】
書込部４０は、中継するパケットに指名ルータ２０ａを通過したことを示す情報を書き込む。例えば、指名ルータ２０ａは、中継するパケットのＩＰヘッダのオプション部分に、指名ルータ２０ａを通過したことを示すマークとして情報を書き込む。なお、情報を書き込む位置は、オプション部分の未使用の位置であれば何れであってもよい。
【００３４】
計測部４１は、パケットの送信間隔を計測する処理部である。例えば、計測部４１は、各ルータ２０毎に、マークを書き込んだパケットの送信間隔を計測する。
【００３５】
算出部４２は、各種の算出を行う処理部である。例えば、算出部４２は、計測部４１により計測されるパケットの送信間隔に基づいて、しきい値を算出する。なお、しきい値の算出は、送信間隔が計測される毎に、随時行うものとしてもよく、一定の時間間隔など所定のタイミングで行うものとしてもよい。
【００３６】
ここで、しきい値の算出方法について説明する。本実施例では、しきい値を算出する方法として、ＴＣＰ（Transmission  Control  Protocol）で用いられているタイムアウトを判定する方法を利用する。ＴＣＰは、到着するパケットを常時計測し、その到着間隔の平均と平均偏差を計算している。そして、到着間隔の平均に平均偏差の所定の倍率（例えば、２倍）を足した値をしきい値とし、これを超えるものはタイムアウトと判定する。
【００３７】
これと同様に、本実施例でも、パケットの間隔がしきい値以上であれば、相手の指名ルータ２０ａはパケット送出できない状態、すなわち機能停止になったと判定する。所定の倍率は、本実施例では２倍とするが、試験評価の上、倍率を決定してもよい。算出部４２は、以下のような算出法により計測としきい値を算出する。
【００３８】
Ｅｒｒ＝Ｍ×Ａ
Ａ→Ａ＋ｇ×Ｅｒｒ
Ｄ→Ｄ＋ｈ×（｜Ｅｒｒ｜×Ｄ）
しきい値＝Ａ＋２Ｄ
【００３９】
ここで、Ａは平滑化されたパケット間隔であり、Ｄは平滑化された平均偏差であり、Ｍはマークされたパケットの間隔(計測値)であり、ｈは係数（例えば、１／４）であり、Ｅｒｒは平滑化されたパケット間隔と計測値との差であり、ｇは係数（例えば、１／４）である。
【００４０】
判定部４３は、各種の判定を行う処理部である。例えば、判定部４３は、各ルータ２０毎のパケットの送信間隔がしきい値以上となることが予測されるか判定する。判定部４３は、計測部４１により計測される各ルータ２０毎の送信間隔の何れかがしきい値から所定の許容時間を減算した時間となった場合、マークを書き込んだパケットの送信間隔がしきい値以上となることが予測されるものと判定する。この許容時間は、固定値としてもよく、変動値としてもよい。例えば、許容時間は、通信システム１０で発生する通信遅延分の時間として、管理者が固定値として定めてもよい。また、許容時間は、通信システム１０を伝送されるパケットを監視して最大の通信遅延時間を求め、最大の通信遅延時間または最大の通信遅延時間に所定の係数を乗算した時間としてもよい。
【００４１】
送信部４４は、各種のパケットを送信する処理部である。例えば、送信部４４は、判定部４３によりパケットの送信間隔がしきい値以上となることが予測された場合、指名ルータ２０ａが生存していることを知らせるため、ＩＰヘッダのオプション部分に、指名ルータ２０ａを通過したことを示すマークを書き込んだパケットを、送信間隔がしきい値以上となるルータ２０へ送信する。また、送信部４４は、ルータ２０からＭｉｓｓｉｎｇメッセージを受信した場合、Ａｌｉｖｅパケットをマルチキャストする。
【００４２】
一方、監視部５０は、指名ルータ２０ａが正常に動作しているか否かを監視する処理部である。例えば、監視部５０は、インタフェース部３０で受信したパケットのＩＰヘッダのオプション部分に指名ルータ２０ａを通過したことを示すマークが書き込まれているか監視する。
【００４３】
計測部５１は、パケットの受信間隔を計測する処理部である。例えば、計測部５１は、マークを書き込んだパケットの送信間隔を計測する。
【００４４】
算出部５２は、各種の算出を行う処理部である。例えば、算出部５２は、計測部５１により計測されるパケットの受信間隔に基づいて、上述した算出部４２と同様の演算により、しきい値を算出する。なお、しきい値の算出は、送信間隔が計測される毎に、随時行うものとしてもよく、一定の時間間隔など所定のタイミングで行うものとしてもよい。
【００４５】
解除部５３は、データの解除を行う処理部である。例えば、解除部５３は、監視部５０による監視の結果、ＩＰヘッダのオプション部分に指名ルータを通過したことを示すマークが書き込まれたパケットを検出した場合、書き込まれたマークのデータを解除する。指名ルータ２０ａを通過したことを示すマークが解除されたパケットは、宛先へと転送される。
【００４６】
通知部５４は、各種の通知を行う処理部である。例えば、通知部５４は、監視部５０による監視の結果、マークが書き込まれたパケットがしきい値以上受信されない場合、指名ルータ２０ａが不明な状態であることを示すＭｉｓｓｉｎｇメッセージをマルチキャストする。また、通知部５４は、他のルータ２０からＭｉｓｓｉｎｇメッセージを受信した場合、当該他のルータ２０へ現在のしきい値を通知する。そして、通知部５４は、他のルータ２０からＭｉｓｓｉｎｇメッセージを受信した後にマークが書き込まれたパケットを受信した場合、Ａｌｉｖｅパケットをマルチキャストする。
【００４７】
再構築部５５は、ルーティング経路の再構築を行う処理部である。例えば、再構築部５５は、通知部５４によりＭｉｓｓｉｎｇメッセージをマルチキャストしてから上記しきい値の期間を経過する間に指名ルータ２０ａが動作していることを示す通知が受信できない場合、経路の再構築を行う。例えば、再構築部５５は、指名ルータ２０ａが動作していることを示す通知として、Ａｌｉｖｅパケットが受信できない場合、経路の再構築を行う。
【００４８】
次に、ルータ２０の動作状態の遷移について説明する。図４は、ルータがＯＳＰＦにより指名ルータを選定する際の動作状態の遷移を示す図である。
【００４９】
１．Down  State（停止状態）
ルータ２０は、動作可能な状態であるが、他のルータ２０とまだ情報交換を行なっていない状態であり、他のルータ２０を識別できない状態である。
【００５０】
２．Attempt  State（試行状態）
ルータ２０は、まず、ＯＳＰＦのマルチキャストアドレス（２４４．０．０.５）宛てにＨｅｌｌｏパケットを送信する。まだ、Attempt  Stateは、ルータ２０が、他のルータ２０からＨｅｌｌｏパケットを受信できていない状態である。
【００５１】
３．Init  State（初期状態）
Ｈｅｌｌｏパケットを送信するルータ２０をルータＡ、受信するルータ２０をルータＢとすると、ルータＡから送信するＨｅｌｌｏパケットの隣接ルータフィールドには、まだルータＢがリストアップされていない状態である。各ルータ２０は、他のルータ２０からのＨｅｌｌｏパケットを受信した場合、自身の隣接ルータリストに他のルータ２０を追加する。例えば、ルータＢは、ルータＡからのＨｅｌｌｏパケットを受信した場合、自身の隣接ルータリストにルータＡを追加する。Ｈｅｌｌｏパケットを受信したルータ２０は、ユニキャストの応答Ｈｅｌｌｏパケットを、自身の全ての隣接ルータリストと一緒に、他のルータ２０に送信する。例えば、ルータＢは、ルータＡへユニキャストの応答Ｈｅｌｌｏパケットを、自身の全ての隣接ルータリストと一緒に送信する。
【００５２】
４．2-Way  State（双方向状態）
応答のＨｅｌｌｏパケットを受信したルータ２０は、メッセージの隣接ルータフィールドの中に自身が記載されていることを確認し、双方向状態となる。このＨｅｌｌｏパケットの交換プロセス実行中に、相互の優先度フィールドがチェックされ、指名ルータ及びバックアップ指名ルータ選出の手続きが行われ、指名ルータ及びバックアップ指名ルータとの間で隣接関係が確立される。
【００５３】
５．Exstart  State（起動後状態）
各ルータ２０は、リンクステートデータベースの作成（初期化）を開始する。また、各ルータ２０は、隣接関係にあるルータ２０との間でマスター／スレーブ関係を確立する。
【００５４】
６．Exchange  State（交換状態）
ルータ２０は、マスター／スレーブ関係がネゴシエートされると、ＤＢＤ（データベース記述:Data  Base  Description）パケットを送信する。なお、最初にＤＢＤパケットを送信するルータ２０をマスター、相手先のルータ２０をスレーブとする。最初のＤＢＤパケット送信時に、データベース記述シーケンス番号の初期値を定義し、その後、一連のＤＢＤパケット交換のたびに、シーケンス番号は増分される。
【００５５】
７．Loading  State（ロード状態）
ＤＢＤパケットを受信したルータ２０は、ＬＳＡｃｋ（リンク状態確認応答:Link  State  Acknowledgement）メッセージに、受信したＤＢＤパケットのシーケンス番号をコピーして、ＤＢＤパケットを受信したことを通知する。また、ルータ２０は、受信したＤＢＤパケットのＬＳＡヘッダ内のＬＳＡシーケンス番号をチェックして、現在記憶している情報と受信した情報と比較する。受信したＤＢＤパケットのリンクステートエントリのほうが新しい場合は、ＬＳＲ（リンク状態要求:Link  State  Request）パケットを送信し、最新情報の部分を要求する。ＬＳＲパケットを受信したルータ２０は、ＬＳＵ（リンク状態更新:Link  State  Update)パケットを送信する。ＬＳＵパケットを受信したルータ２０は、ＬＳＡｃｋパケットで確認応答する。
【００５６】
８．Full  State（完全状態）
あるルータ２０に対してすべてのＬＳＲパケットの処理が終了すると、その隣接ルータ２０は、同期してFull  Stateの状態となったとみなされる。この時点で隣接関係にあるルータ２０同士が同一のリンクステートデータベースを持つ。すなわち、指名ルータ２０ａ及びバックアップ指名ルータ２０ｂに選出されたルータ２０は、他の各ルータ２０と隣接関係を確立することにより、他の各ルータ２０のＤＢＤパケットによりリンクステートエントリが通知される。また、他のルータ２０は、指名ルータに選択されたルータ２０から最新のリンクステートエントリが通知される。よって、各ルータ２０は、同一のリンクステートデータベースを持つ。ルータ２０は、リンクステートデータベースの情報からＳＰＦツリーを生成し、生成したＳＰＦツリーを基にルーティングテーブルを作成する。そして、各ルータ２０は、受信したパケットをルーティングテーブルの情報に基づいてパケットのルーティングを行う。
【００５７】
次に、完全状態となった以降の指名ルータ２０ａの動作状態の遷移について説明する。図５は、完全状態となった以降の指名ルータの動作状態の遷移を示す図である。
【００５８】
１．Measurement（計測状態）
指名ルータ２０ａは、受信したＩＰパケットにマークし、ルーティングテーブルの情報に基づいて受信したＩＰパケットを隣接ルータ２０へ送信する。また、指名ルータ２０ａは、各ルータ２０毎に、ＩＰパケットの到着間隔を計測して、しきい値を算出する。
【００５９】
２．Dummy  Packet  Generation（ダミーパケット生成状態）
指名ルータ２０ａは、しきい値を超えてもマークすべきＩＰパケットが受信できないことが予測される場合、マークすべきＩＰパケットが受信できない期間がしきい値を超えることが予測される隣接ルータ２０へダミーのマーク付きＩＰパケットを生成して送信する。
【００６０】
３．Confirmation  Acknowledgement（確認応答状態）
指名ルータ２０ａは、Ｍｉｓｓｉｎｇパケットを受信した場合、Ａｌｉｖｅパケットをマルチキャストする。そして、１．Measurementの状態へ遷移する。
【００６１】
次に、完全状態となった以降の指名ルータ２０ａ及びバックアップ指名ルータ以外のルータ２０の動作状態の遷移について説明する。図６は、完全状態となった以降のルータの動作状態の遷移を示す図である。
【００６２】
１．Measurement（計測状態）
指名ルータ及びバックアップ指名ルータ以外のルータ２０は、マークされたパケットの受信を監視し、受信間隔を計測する。また、ルータ２０は、マークされたＩＰパケットの受信間隔を計測してしきい値を算出する。ルータ２０は、計測される受信間隔をしきい値と比較し、しきい値より小さければ計測状態を維持し、しきい値以上であれば後述する２．Ｍｉｓｓｉｎｇの状態へ遷移する。また、ルータ２０は、Ｍｉｓｓｉｎｇパケットを受信した場合、後述する３．Confirmation  Thresholdの状態へ遷移する。
【００６３】
２．Missing（指名ルータの生存確認不可状態）
ルータ２０は、Ｍｉｓｓｉｎｇパケットをマルチキャストする。ルータ２０は、Ｍｉｓｓｉｎｇパケットをマルチキャストした後、他のルータ２０からしきい値が格納されたパケットを受信した場合、受信したパケットのしきい値と算出したしきい値を比較して、最大のしきい値を求める。ルータ２０は、最大のしきい値の期間を経過するまでに他のルータ２０からＡｌｉｖｅパケットを受信した場合、指名ルータ２０ａが正常動作しており、隣接関係を結んでいる経路上で障害が発生したと判断し、後述する５．Ospf-Initの状態へ遷移する。すなわち、ルータ２０は、現在の最大のしきい値の期間を経過するまでに他のルータ２０からしきい値が格納されたパケットを受信した場合、現在の最大のしきい値と受信したパケットに格納されたしきい値を比較し、より大きいものを最大のしきい値として用いる。よって、現在の最大のしきい値の期間を経過するまでに他のルータ２０からより値の大きなしきい値を格納したパケットが受信された場合、最大のしきい値は、受信したパケットに格納されたしきい値に更新される。ルータ２０は、最大のしきい値の期間を経過するまでに他のルータ２０からＡｌｉｖｅパケットを受信した場合、後述する５．Ospf-Initの状態へ遷移する。一方、ルータ２０は、最大のしきい値の期間を経過するまでにＡｌｉｖｅパケットを受信しなかった場合、後述する６．Ospf-Restart状態へ遷移する。
【００６４】
３．Confirmation  Threshold（しきい値確認状態）
ルータ２０は、他のルータ２０からＭｉｓｓｉｎｇパケットを受信した場合、現在のしきい値を格納したパケットをＭｉｓｓｉｎｇパケットの送信元のルータ２０へ直ちに送信して、現在のしきい値を通知する。
【００６５】
４．Confirmation（マークパケット確認状態）
ルータ２０は、しきい値の期間を経過するまでにＩＰパケットを受信した場合、Ａｌｉｖｅパケットをマルチキャストし、１．Measurementの状態へ戻る。また、ルータ２０は、他のルータ２０からＡｌｉｖｅパケットを受信した場合も、１．Measurementの状態へ戻る。
【００６６】
５．Ospf-Init（ＯＳＰＦ  初期状態）
ルータ２０は、指名ルータ２０ａへＬＳＡを送信し、ＯＳＰＦの６．Exchange  Stateの状態へ遷移する。
【００６７】
６．Ospf-Restart（すべてのルータがOSFP  初期状態)
ルータ２０は、指名ルータ２０ａが停止したと判断し、Ｉｎｉｔパケットをマルチキャストする。これにより、各ルータ２０は、指名ルータ２０ａがダウンしたことを示すＯＳＰＦの１．Down状態へ遷移して、指名ルータ２０ａの再選出を行う。
【００６８】
次に、完全状態となった以降の指名ルータ２０ａの処理の流れを説明する。図７は、完全状態となった以降の指名ルータの処理の流れを示すフローチャートである。この処理は、完全状態となった際に実行される。
【００６９】
図７に示すように、計測部４１は、各ルータ２０毎のマークを書き込んだパケットの送信間隔をゼロに初期化する（Ｓ１０）。計測部４１は、各ルータ２０毎にマークを書き込んだパケットの送信間隔の計測を開始する（Ｓ１１）。
【００７０】
判定部４３は、パケットが受信されたか否かを判定する（Ｓ１２）。パケットが受信されない場合（Ｓ１２否定）、後述するＳ１６へ移行する。一方、パケットが受信された場合（Ｓ１２肯定）、書込部４０は、中継するパケットに指名ルータ２０ａを通過したことを示すマークを書込む（Ｓ１３）。送信部４４は、ルーティングテーブルの情報に基づいて、マークが書き込まれたパケットを宛先に送信する（Ｓ１４）。計測部４１は、宛先がルータ２０であった場合、パケットを送信したルータ２０に対するパケットの送信間隔をゼロに初期化する（Ｓ１５）。
【００７１】
判定部４３は、各ルータ２０毎のパケットの送信間隔にしきい値以上となることが予測されるものがあるか否かを判定する（Ｓ１６）。例えば、判定部４３は、各ルータ２０毎のパケットの送信間隔が、しきい値から所定の許容時間を減算した時間以上となったものがあるか否かを判定する。
【００７２】
送信間隔がしきい値から所定の許容時間を減算した時間以上となるものがない場合（Ｓ１６否定）、後述するＳ１９へ移行する。一方、送信間隔がしきい値から所定の許容時間を減算した時間以上となったものがある場合（Ｓ１６肯定）、送信部４４は、送信間隔が減算した時間以上となったルータ２０に対してＩＰヘッダのオプション部分にマークを書き込んだパケットを送信する（Ｓ１７）。計測部４１は、パケットを送信したルータ２０のパケットの送信間隔をゼロに初期化する（Ｓ１８）。
【００７３】
判定部４３は、Ｍｉｓｓｉｎｇパケットを受信したか否かを判定する（Ｓ１９）。Ｍｉｓｓｉｎｇパケットを受信していない場合（Ｓ１９否定）、後述するＳ２１へ移行する。一方、Ｍｉｓｓｉｎｇパケットを受信した場合（Ｓ１９肯定）、送信部４４は、Ａｌｉｖｅパケットをマルチキャストする（Ｓ２０）。
【００７４】
送信部４４は、ＬＳＡの受信などにより経路の再構が指示されたか否かを判定する（Ｓ２１）。送信部４４は、経路の再構が指示された場合（Ｓ２１肯定）、処理を終了する。一方、経路の再構が指示されていない場合（Ｓ２１否定）、Ｓ１１へ移行する。
【００７５】
次に、完全状態となった以降の指名ルータ及びバックアップ指名ルータ以外のルータ２０の処理の流れを説明する。図８は、完全状態となった以降のルータの処理の流れを示すフローチャートである。この処理は、完全状態となった際に実行される。
【００７６】
図８に示すように、計測部５１は、前回、マークが書き込まれたパケットの受信間隔をゼロに初期化する（Ｓ３０）。計測部５１は、マークが書き込まれたパケットの受信間隔の計測を開始する（Ｓ３１）。
【００７７】
監視部５０は、パケットを受信したか否かを判定する（Ｓ３２）。パケットを受信していない場合（Ｓ３２否定）、後述するＳ３７へ移行する。一方、パケットを受信した場合（Ｓ３２肯定）、監視部５０は、受信したパケットにマークが書き込まれたパケットであるか否かを判定する（Ｓ３３）。マークが書き込まれたパケットではない場合（Ｓ３３否定）、後述するＳ３５へ移行する。一方、マークが書き込まれたパケットである場合（Ｓ３３肯定）、解除部５３は、書き込まれたマークのデータを解除する（Ｓ３４）。そして、監視部５０は、ルーティングテーブルの情報に基づいて、受信パケットを宛先へ送信する（Ｓ３５）。計測部５１は、受信パケットにマークが書き込まれたパケットであった場合、受信間隔をゼロに初期化する（Ｓ３６）。
【００７８】
通知部５４は、マークが書き込まれたパケットの受信間隔がしきい値以上となったか否かを判定する（Ｓ３７）。受信間隔がしきい値未満である場合（Ｓ３７否定）、上述のＳ３２へ移行する。一方、受信間隔がしきい値以上となった場合（Ｓ３７肯定）、通知部５４は、Ｍｉｓｓｉｎｇメッセージをマルチキャストする（Ｓ３８）。
【００７９】
監視部５０は、他のルータ２０からしきい値が格納されたパケットを受信したか否かを判定する（Ｓ３９）。しきい値が格納されたパケットを受信していない場合（Ｓ３９否定）、後述するＳ４１へ移行する。一方、しきい値が格納されたパケットを受信した場合（Ｓ３９肯定）、監視部５０は、現在のしきい値と受信したパケットに格納されたしきい値を比較し、より大きいものをしきい値とする（Ｓ４０）。
【００８０】
監視部５０は、Ａｌｉｖｅパケットを受信したか否かを判定する（Ｓ４１）。Ａｌｉｖｅパケットを受信した場合（Ｓ４１肯定）、通知部５４は、指名ルータ２０ａへＬＳＡを送信し（Ｓ４２）、処理を終了して６．Exchange  Stateの状態へ移行する。
【００８１】
一方、Ａｌｉｖｅパケットを受信していない場合（Ｓ４１否定）、監視部５０は、Ｍｉｓｓｉｎｇメッセージをマルチキャストしてからしきい値の期間を経過したか否か判定する（Ｓ４３）。しきい値の期間を経過していない場合（Ｓ４３否定）、上述のＳ３９へ移行する。一方、しきい値の期間を経過した場合（Ｓ４３肯定）、再構築部５５は、Ｉｎｉｔパケットをマルチキャストし（Ｓ４４）、処理を終了してＯＳＰＦの１．Down状態へ遷移して、指名ルータ２０ａの再選出を行う。
【００８２】
次に、いくつかの例を用いて本実施例に係る通信システム１０の動作を説明する。
【００８３】
最初に、指名ルータ２０ａに障害が発生した場合の動作例を説明する。図９Ａ〜９Ｅは、指名ルータに障害が発生した場合の動作を示す図である。
【００８４】
典型的な動作例として、指名ルータ２０ａとルータ２０とがネットワークを介して接続され、指名ルータ２０ａで不具合が発生する例を考える。ここでは、ネットワークの回線には、障害は発生していないが、指名ルータ２０ａ上でプログラムに不具合が発生し、機能停止している状況である場合を想定する。バックアップ指名ルータも設置されている場合は、バックアップ指名ルータにも同時に同様な不具合が発生していると想定する。以降では、説明を簡単にするために、指名ルータ２０ａの障害と隣接する３台のルータ２０の動作について説明する。
【００８５】
通常状態では、図９Ａに示すように各ルータ２０は、指名ルータ２０ａよりマーク付きＩＰパケットを受信する。また、各ルータ２０および指名ルータ２０ａは、ともにパケット間隔を計測してしきい値を算出する。
【００８６】
図９Ｂは、指名ルータ２０ａに障害が発生し、指名ルータ２０ａのＯＳＰＦ機能が停止した状態を示す。ただし、ネットワークの回線状態は正常である。指名ルータ２０ａのＯＳＰＦ機能が停止した場合、３台のルータ２０のうちルータＡは、しきい値を経過してもマーク付きＩＰパケットを受信できないため、図９Ｃに示すように、Ｍｉｓｓｉｎｇパケットをマルチキャストする。
【００８７】
ルータＡ以外のルータ２０は、Ｍｉｓｓｉｎｇパケットを受信した場合、図９Ｄに示すように、各自のしきい値（ＭＴ）をマルチキャストする。ルータＡは、他のルータ２０から通知された各しきい値より最大値を求める。
【００８８】
ルータＡ以外のルータ２０も、マーク付きパケットを受信できないため、Ａｌｉｖｅパケットを送信できずにしきい値の最大値の時間が経過する。ルータＡは、しきい値の最大値を待ってもＡｌｉｖｅパケットを受信できないため、図９Ｅに示すように、Ｉｎｉｔパケットをマルチキャストして、ＯＳＰＦ初期状態へ移行する。
【００８９】
次に、指名ルータ２０ａとルータＡとの間のネットワークにＬ２スイッチ２２があり、Ｌ２スイッチ２２部分において障害が発生した場合の動作例を説明する。図１０Ａ〜１０Ｆは、Ｌ２スイッチ部分に障害が発生した場合の動作を示す図である。
【００９０】
通常状態では、図１０Ａに示すように各ルータ２０は、指名ルータ２０ａよりマーク付きＩＰパケットを受信する。また、ルータ２０および指名ルータ２０ａは、ともにパケット間隔を計測してしきい値を算出する。
【００９１】
図１０Ｂは、Ｌ２スイッチ２２に障害が発生した状態を示す。ただし、指名ルータ２０ａを含めてその他のルータ２０およびネットワークの回線状態は正常である。Ｌ２スイッチ２２に障害が発生した場合、ルータＡは、しきい値を経過してもマーク付きＩＰパケットを受信できないため、図１０Ｃに示すように、Ｍｉｓｓｉｎｇパケットをマルチキャストする。指名ルータ２０ａは、通常通りマーク付きＩＰパケットを送信しており、回線障害の発生が分からない。
【００９２】
ルータＡ以外のルータ２０は、Ｍｉｓｓｉｎｇパケットを受信した場合、図１０Ｄに示すように、しきい値（ＭＴ）をマルチキャストする。ルータＡは、しきい値が格納されたパケットを受信した場合、現在の最大のしきい値と受信したパケットに格納されたしきい値を比較し、より大きいものを最大のしきい値として用いる。ルータＡ以外のルータ２０は、指名ルータ２０ａからも通常通りマーク付きＩＰパケットを受信している。このため、ルータＡ以外のルータ２０は、図１０Ｅに示すように、Ａｌｉｖｅパケットをマルチキャストする。
【００９３】
ルータＡは、他のルータ２０からＡｌｉｖｅパケットを受信する。これにより、ルータＡは、指名ルータ２０ａが正常動作しているが、回線障害があり、以前のルートが使えないことを検出する。そこで、ルータＡは、新しいルートで指名ルータと隣接関係を結ぶためＬＳＡを指名ルータ２０ａへ送信し、図１０Ｆに示すように、初期状態へ遷移する。
【００９４】
次に、障害は発生していないが、回線を通るアプリケーションのパケットが少なくなった場合の動作例を説明する。図１１Ａ〜１１Ｄは、回線を通るアプリケーションのパケットが少なくなった場合の動作を示す図である。ここでは、説明を簡単にするために、指名ルータ２０ａと隣接する１台のルータ２０の動作について説明する。
【００９５】
通常状態では、図１１Ａに示すようにルータ２０は、指名ルータ２０ａよりマーク付きＩＰパケットを受信する。また、ルータ２０および指名ルータ２０ａは、ともにパケット間隔を計測してしきい値を算出する。
【００９６】
図１１Ｂは、回線を通るアプリケーションのパケットが少なくなり、指名ルータ２０ａより送信されるマーク付きＩＰパケットが一時、送信されない期間が発生した状態を示す。指名ルータ２０ａは、パケットの間隔がしきい値以上となることが予測される場合、図１１Ｃに示すように、ダミーのマーク付きＩＰパケットをルータ２０へ送信する。
【００９７】
ルータ２０は、図１１Ｄに示すように、ダミーのマーク付きＩＰパケットを受信することにより、指名ルータ２０ａが正常動作していることが分かり、通常通りの動作を続ける。これにより、指名ルータ２０ａからルータ２０へ中継されるパケットの期間がしきい値よりも長い場合でも、ルータ２０は、図１１Ｄに示すように、ダミーのマーク付きＩＰパケットを受信することにより、指名ルータ２０ａのＯＳＰＦ機能が停止した状態と判定せずに動作しつづけることができる。
【００９８】
次に、輻輳等によってマーク付きＩＰパケット、Ｍｉｓｓｉｎｇパケット、Ａｌｉｖｅパケットなどのパケットが喪失した場合の動作例を説明する。図１２Ａ〜１２Ｅは、パケットが喪失した場合の動作を示す図である。
【００９９】
通常状態では、図１２Ａに示すように各ルータ２０は、指名ルータ２０ａよりマーク付きＩＰパケットを受信する。また、ルータ２０および指名ルータ２０ａは、ともにパケット間隔を計測してしきい値を算出する。
【０１００】
図１２Ｂは、指名ルータ２０ａから送信されるはずのマーク付きＩＰパケットが、輻輳等の何らかのネットワークの不具合により、ルータＡへ届かない状態を示す。ただし、指名ルータ２０ａを含めてその他のルータ２０は正常である。パケットが喪失した場合、ルータＡでは、計測しているパケットの受信期間がしきい値を超える。このため、ルータＡは、図１２Ｃに示すように、Ｍｉｓｓｉｎｇパケットをマルチキャストする。ここで、Ｍｉｓｓｉｎｇパケットも何らかの不具合により、いくつかが途中で廃棄されたものとする。
【０１０１】
Ｍｉｓｓｉｎｇパケットを受信した他のルータ２０は、図１２Ｄに示すように、現在のしきい値（ＭＴ）をルータＡへ送信する。このしきい値を記載したパケットも何らかの不具合により、いくつか途中で廃棄されたとする。ルータＡは、いくつかのしきい値を記載したパケットを受信しその最大値を算出し、Ａｌｉｖｅパケットの受信を待つ。
【０１０２】
一方、指名ルータ２０ａは正常動作している。このため、各ルータ２０は、ＡｌｉｖｅパケットをルータＡへ送信する。その全てのＡｌｉｖｅパケットが喪失することは考えにくく、図１２Ｅに示すように、いずれかのＡｌｉｖｅパケットがルータＡに到達する。ルータＡは、Ａｌｉｖｅパケットを受信することにより、指名ルータ２０ａが正常動作しているが、隣接関係のある経路上で障害が発生したと判断する。そこで、ルータＡは、自身のＯＳＰＦの初期状態へ状態遷移し、隣接関係の再構築を試みる。
【０１０３】
ここで、従来のＨｅｌｌｏパケットを使った生存確認法では、計４個のＨｅｌｌｏパケットを送出して初めて生存確認を判断する。このため、従来のＨｅｌｌｏパケットを使った生存確認法では、生存を確認して経路を切替えるまで時間が４０秒以上かかる。
【０１０４】
一方、本実施例の方式は、ＩＰパケット間隔のしきい値によるが、しきい値を１秒であれば約１０秒程度、しきい値が０.１秒の場合は約７秒程度で経路を切替えることができ、いずれの場合も既存方式と比較して経路切替の大幅な時間短縮が可能となる。また、本実施例の方式は、回線中を流れるＩＰパケットが少ない場合、ダミーのＩＰパケットを送信する機能を使い、しきい値を超えない送信間隔にするため、通信負荷が上昇することになる。しかし、例えば、６４バイトのダミーのＩＰパケットを０.１秒間隔で送信しても、５．１２ｋｂｐｓの帯域にしかならない。このため、本実施例の方式は、通信負荷を過剰に上昇させることもない。
【０１０５】
上述してきたように、本実施例に係る通信システム１０では、指名ルータ２０ａは、中継するパケットのＩＰヘッダのオプション部分に、指名ルータ２０ａを通過したことを示す情報を書き込む。指名ルータ２０ａ以外のルータ２０は、受信したパケットのＩＰヘッダのオプション部分に指名ルータ２０ａを通過したことを示す情報が書き込まれているか監視する。そして、ルータ２０は、監視の結果、指名ルータ２０ａを通過したことを示す情報が書き込まれたパケットが所定のしきい値以上受信されない場合、経路の再構築を行う。これにより、本実施例に係る通信システム１０は、経路に異常があった場合に経路の切替えを速やかに行うことができる。通信システム１０は、このように経路の切替えを速やかに行うことができる結果、経路に異常により、通信システム１０を介して通信を行うアプリケーションに支障を来たすことが抑制できる。また、本実施例に係る通信システム１０は、指名ルータ２０ａの生存確認のため、Ｈｅｌｌｏパケットを送信する必要がなくなり、トラヒックを軽減できる。また、本実施例に係る通信システム１０は、パケットのＩＰヘッダに指名ルータ２０ａを通過したことを示す情報が書き込むため、パケットが中継されるネットワークにＬ２スイッチ２２が存在してもルーティングに影響を受けることがない。また、本実施例に係る通信システム１０は、パケットのＩＰヘッダのオプション部分に指名ルータ２０ａを通過したことを示す情報が書き込むため、パケットの実データに影響を与えることがなく、また、ＩＰヘッダの宛先などの情報も書き換えないため、パケットのルーティングに影響を与えることもない。
【０１０６】
また、ルータ２０は、監視の結果、指名ルータ２０ａを通過したことを示す情報が書き込まれたパケットが所定のしきい値以上受信されない場合、指名ルータ２０ａが不明な状態であることを他のルータ２０へ通知する。そして、ルータ２０は、指名ルータ２０ａが不明な状態であることを通知してから所定のしきい値の期間を経過する間に指名ルータ２０ａが動作していることを示す通知が受信できない場合、経路の再構築を行う。これにより、本実施例に係る通信システム１０は、指名ルータ２０ａとの間の経路の異常と、指名ルータ２０ａの機能停止を判別して、経路の切替えを行うことができる。
【０１０７】
また、ルータ２０は、他のルータ２０から指名ルータが不明な状態である通知を受信した場合、当該他のルータ２０へしきい値を通知する。そして、ルータ２０は、指名ルータが不明な状態であることを通知してからしきい値および他のルータ２０から通知されるしきい値のうち、最大のしきい値の期間を経過する間に指名ルータ２０ａが動作していることを示す通知が受信できない場合、経路の再構築を行う。これにより、本実施例に係る通信システム１０は、指名ルータ２０ａの機能停止を検出して、経路の切替えを行うことができる。
【０１０８】
また、指名ルータ２０ａは、各ルータ２０へ中継するパケットの間隔がしきい値以上となることが予測される場合、ＩＰヘッダのオプション部分に、指名ルータ２０ａを通過したことを示す情報を書き込んだパケットを送信する。これにより、本実施例に係る通信システム１０は、指名ルータ２０ａを経由してルータ２０へ送信されるパケットが少なく、パケットの間隔がしきい値以上となる場合でも、経路の切替えが行われることを抑制できる。
【実施例２】
【０１０９】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【０１１０】
例えば、上記の実施例では、ネットワーク１１〜１４を１つのエリアとして指名ルータおよびバックアップ指名ルータを選出する場合について例示したが開示の装置はこれに限定されない。例えば、ネットワーク１１〜１４をそれぞれエリアに分けて指名ルータおよびバックアップ指名ルータを選出し、それぞれのエリアにおいて指名ルータが指名ルータを通過したことを示すマークを書き込んだパケットをエリア内のルータに転送し、エリア内の各ルータがマークを書き込んだパケットの受信間隔から指名ルータの機能停止を検出してもよい。
【０１１１】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図３に示す制御部３２をさらに細かい処理部に分けてもよい。
【０１１２】
［制御プログラム］
また、上記の実施例で説明した制御部３２の各種の処理は、あらかじめ用意されたプログラムをコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図１３を用いて、上記の実施例で説明した制御部３２と同様の機能を有する制御プログラムを実行するコンピュータの一例を説明する。図１３は、制御プログラムを実行するコンピュータを示す図である。
【０１１３】
図１３に示すように、コンピュータ３００は、ＣＰＵ（Central  Processing  Unit）３１０、ＲＯＭ（Read  Only  Memory）３２０、ＨＤＤ３３０、ＲＡＭ（Random  Access  Memory）３４０を有する。これら３００〜３４０の各部は、バス４００を介して接続される。
【０１１４】
ＲＯＭ３２０には、上記の実施例１に示す制御部３２と同様の機能を発揮する制御プログラム３２０ａが予め記憶される。すなわち、ＲＯＭ３２０には、図１３に示すように、制御プログラム３２０ａが記憶される。なお、制御プログラム３２０ａについては、適宜分離しても良い。
【０１１５】
ＨＤＤ３３０には、各種の情報が記憶される。例えば、ＨＤＤ３３０は、リンクステートエントリの情報や、ルーティングテーブル、しきい値、許容時間を記憶する。
【０１１６】
そして、ＣＰＵ３１０は、各種の情報を読み出してＲＡＭ３４０に格納する。ＣＰＵ３１０は、ＲＡＭ３４０に格納された関係情報を用いて、制御プログラム３２０ａを実行する。なお、ＲＡＭ３４０に格納される各データは、常に全てのデータがＲＡＭ３４０に格納される必要はなく、処理に必要なデータのみがＲＡＭ３４０に格納されれば良い。
【０１１７】
なお、上記した制御プログラム３２０ａについては、必ずしも最初からＲＯＭ３２０に記憶させておく必要はない。
【０１１８】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１１９】
１０    通信システム
２０    ルータ
２０ａ  指名ルータ
２０ｂ  バックアップ指名ルータ
３０    インタフェース部
３１    記憶部
３２    制御部
４０    書込部
４１    計測部
４２    算出部
４３    判定部
４４    送信部
５０    監視部
５１    計測部
５２    算出部
５３    解除部
５４    通知部
５５    再構築部
【図１】
0005953101.tif 000002
【図２Ａ】
0005953101.tif 000003
【図２Ｂ】
0005953101.tif 000004
【図３】
0005953101.tif 000005
【図４】
0005953101.tif 000006
【図５】
0005953101.tif 000007
【図６】
0005953101.tif 000008
【図７】
0005953101.tif 000009
【図８】
0005953101.tif 000010
【図９Ａ】
0005953101.tif 000011
【図９Ｂ】
0005953101.tif 000012
【図９Ｃ】
0005953101.tif 000013
【図９Ｄ】
0005953101.tif 000014
【図９Ｅ】
0005953101.tif 000015
【図１０Ａ】
0005953101.tif 000016
【図１０Ｂ】
0005953101.tif 000017
【図１０Ｃ】
0005953101.tif 000018
【図１０Ｄ】
0005953101.tif 000019
【図１０Ｅ】
0005953101.tif 000020
【図１０Ｆ】
0005953101.tif 000021
【図１１Ａ】
0005953101.tif 000022
【図１１Ｂ】
0005953101.tif 000023
【図１１Ｃ】
0005953101.tif 000024
【図１１Ｄ】
0005953101.tif 000025
【図１２Ａ】
0005953101.tif 000026
【図１２Ｂ】
0005953101.tif 000027
【図１２Ｃ】
0005953101.tif 000028
【図１２Ｄ】
0005953101.tif 000029
【図１２Ｅ】
0005953101.tif 000030
【図１３】
0005953101.tif 000031