JP2006279482A - ネットワーク、ルータ装置、それに用いる切替方法及びそのプログラム並びに記録媒体 - Google Patents

Abstract

【課題】リンクや隣接ルータ装置がダウンした際、転送パケットのループが発生しない経路に高速に切替可能なルータ装置を提供する。
【解決手段】主経路計算部１１２で予め算出して主経路表１２２に格納した経路情報を元にパケット転送部１２でリンク３１〜３ｎのいずれかに転送するルーティング処理を行う際、リンクまたは隣接するルータ装置の故障を故障検知器１３２で検知したとき、代替経路計算部１１３で想定故障箇所に対して予め算出して代替経路表１３１１〜１３１ｎに格納した代替経路へ高速切替部１３により直ちに切り替える。代替経路計算部１１３は、想定故障箇所に対する代替経路がループとなるか否かをループ経路判定部１１４で判定し、ループにならない代替経路のみを代替経路表１３１１〜１３１ｎに格納する。また、故障発生から一定時間経過後や他のルータ装置から経路更新完了を受信時、ループと判定された代替経路を主経路表１２２に追加する。
【選択図】図１

Description

本発明は、ネットワーク、ルータ装置、それに用いる切替方法及びそのプログラム並びにプログラム記録媒体に関し、特に、ノード（ルータ装置）に接続しているリンクや隣接するノードの故障を検知したときに、動的経路制御による経路情報の更新を行うことなく、事前に計算して蓄積しておいた代替経路への高速経路切替を行う技術に関する。

現在、インターネットで用いられている経路制御プロトコルは、自律システムの内部での経路制御に使用するＩＧＰｓ（Interior Gateway Protocols）と自律システム間の経路情報の交換に用いるＥＧＰｓ（Exterior Gateway Protocols）とに分けられる。ここでの自律システム（ＡＳ：Autonomous System）とは、単一の管理ポリシーで運用されているネットワークであり、例えば、ある企業内のネットワークやＩＳＰ（Internet Services Provider）などのネットワークがこれに該当する。

ＩＧＰｓは、大きく分けて、二つのタイプのプロトコルに分類され、それぞれに用いられる経路決定アルゴリズムが異なる。一つは、ディスタンスベクター型と呼ばれ、このタイプの代表的なプロトコルにＲＩＰ（Routing Information Protocol）がある。ディスタンスベクターアルゴリズムでは、送信元と宛先間のルータホップつまり通過しなければならないルータ装置の数が一番小さい経路が選択される。

このプロトコルを用いることにより、自律システム中のすべてのルータ装置は到達可能なすべてのネットワークの情報を知ることができるが、知ることができる情報は、それぞれのルータ装置において最終宛先への経路上にある次転送先のルータ装置のアドレスと最終宛先までに経由するルータ装置の台数だけである。ＩＧＰｓで用いられているもう一つのアルゴリズムは、リンクステートアルゴリズムであり、ＯＳＰＦ（Open Shortest Path First routing）やＩＳ−ＩＳ（Intermediate System - Intermediate System）などのプロトコルでは、このアルゴリズムが用いられている。リンクステート型プロトコルでは、自律システム内のトポロジーに関する情報を全ルータ装置で共有することができる。

ここでのトポロジー情報とは、自律システム内にどのようなルータ装置が存在し、それぞれがどのようなリンク(ネットワーク)で接続されているかという情報である。

自律システム内の各ルータ装置は、トポロジー情報から生成される有向グラフを用い、各ノード（ルータ装置）に対して最小コストを達成するパスからなる最短パスツリーを作成し、目的宛先までの最短パスを計算し、各宛先毎の次転送先ルータ装置を確定する。最短パスツリーを作成するためのアルゴリズムには、通常、Dijkstraのアルゴリズムが用いられる。以上の一連の最短パス選択決定動作を、リンクステート型プロトコルにおける経路計算と呼ぶ。

一般に、ルータ装置は、故障やメンテナンスにより接続するリンクや隣接するノードがダウンし、トポロジー情報に変化が生じたときには、その変化を自律システム中の他のルータ装置に通知する。トポロジー情報の変化を知った各ルータ装置は、それぞれ、新たに変化したトポロジー情報を元に経路計算を行い、経路表の更新を行う。このことにより、故障したリンクやノードを除いた状態のトポロジー情報に基づいたパケット転送が行われる。しかし、自律システム中の他のルータ装置へのトポロジー情報変化の通知や経路計算には、ネットワーク規模にも依存するが、約数百ms程度の時間がかかるため、この間、パケットが正常に転送されないパケットロスが発生する可能性がある。

このようなパケットロスの発生を最小限に食い止めるために、高速経路切替の技術が考えられている。

これらの高速経路切替技術では、事前に、各リンクや各ノードのダウンを想定した場合のトポロジー情報を元に代替経路を計算しておく。しかる後、実際に、あるリンクやノードのダウンを検知したときには、事前に計算しておいた代替経路を用いてパケットの転送を行うようにしている。

次に、図９のような構成からなる従来のルータ装置における従来の高速経路切替技術について図１０のネットワーク図を用いて説明する。ここに、図９は、従来のルータ装置の機能構成を示すブロック構成図であり、図１０は、従来の高速経路切替技術におけるパケット転送経路を示すネットワーク図である。

図９に示すルータ装置１Ｃは、経路制御部１１、パケット転送部１２及びネットワークインターフェイス２１〜２ｎで構成され、経路制御部１１は、トポロジー情報交換部１１１、主経路計算部１１２で構成され、パケット転送部１２は、ルーティング処理部１２１、主経路表１２２で構成される。

トポロジー情報交換部１１１により、隣接ルータ装置との間でトポロジー情報の交換を行うことにより収集したトポロジー情報は、主経路計算部１１２に引き渡され、主経路計算部１１２にて、通常のＩＧＰ（Interior Gateway Protocol）の経路計算を行い、主経路表１２２に経路情報の登録を行う。

パケット転送部１２のルーティング処理部１２１においては、各ネットワークインターフェイス２１〜２ｎから受信したパケットのヘッダ部分にある宛先アドレスに基づいて主経路表１２２の経路情報を参照して、次転送先アドレスのルータ装置に対して、受信したパケットを送出する。

次に、図９のルータ装置１Ｃのような構成からなるルータ装置を用いた従来の高速経路切替技術について、図１０を用いて説明する。ルータ装置５４からルータ装置５１へ至るパスは、ルータ装置５２を経由するパス６１とルータ装置５３を経由するパス６２との二つがある。通常、ＯＳＰＦやＩＳ−ＩＳなどのＩＧＰでは、パス中のリンクに設定されているコストの合計が最も小さいパスを最短パスとして選択し、選択されたパス上における次転送先ルータ装置のアドレスを主経路表１２２に登録する。

図１０においては、図１０（ｃ）に示すように、パス６１よりもパス６２の方がパス上のリンクのコスト値の合計が小さいので、ルータ装置５４の経路中のルータ装置５１への経路情報には、次転送先として図１０（ａ）のようにルータ装置５３が主経路表１２２に登録される。一方、図１０（ｂ）に示すように、リンク７４がダウンした場合には、ルータ装置５４は、ルータ装置５１宛てのパケットを転送する代替経路としてルータ装置５２に向けて転送することにより、宛先のルータ装置５１までのパケット転送を正常に行うことができる。

しかし、このような切替方式では、経路がループしてしまう可能性がある。このループ発生例について図１１を用いて説明する。図１１は、従来の高速経路切替技術におけるループの発生を示すネットワーク図である。ルータ装置５４からルータ装置５３へのパケットは、正常時においては、図１１（ｃ）に示すように、パス６２が最短パスとなるため、図１１（ａ）のようにリンク７４を経由してルータ装置５３に転送される。

一方、リンク７４のダウン時には、パス６１経由でパケットが転送されることを期待して、ルータ装置５４は、ルータ装置５３宛てのパケットをルータ装置５２に転送する。しかし、リンク７４のダウンを知らないルータ装置５２は、転送されてきたパケットの宛先であるルータ装置５３へのパスとして、当該ルータ装置５２自身からルータ装置５３への複数のパスのうち、最短のパスがパス６３であると判断し、図１１（ｂ）に示すように、パケットをルータ装置５４に転送する。このように、ルータ装置５３宛ての経路は、ルータ装置５２とルータ装置５４との間でループとなってしまう。

ＩＰ（Internet
Protocol）では、他のネットワーク技術とは異なり、それぞれのルータ装置が受け取ったパケット中の宛先フィールドを見て次転送先ルータ装置に転送するという動作を独立して行っている。このことは、自律システム内の各ルータ装置は、それぞれの経路表を形成する際には同一のトポロジー情報を元にしているという前提に立って、はじめてうまく機能することを意味している。このため、故障を検知したルータ装置が、独自の判断で代替経路を使うということは、この前提が崩れ、前述のループの発生を引き起こす危険性が生じてしまう。

また、ＩＰにおける転送動作においては、転送の経路判断は、パケットの宛先フィールドのみを用いて行っている。このため、自律システム内の各ルータ装置においてあらかじめ代替経路を作成した代替経路表を用意していたとしても、受信したパケットの転送を行う際に、通常の経路表を用いればよいか、もしくは代替経路表を用いればよいかの判断ができない。

以上のように、ループの発生を引き起こす可能性があるため、現状においては、ＩＰにおける高速経路切替技術が使用されるのは、イコールコストマルチパスが存在する場合に限られていた。イコールコストマルチパスが存在するということは、ある宛先に対して同一コストで最短パスが複数存在するということである。このようなケースであれば、ルータ装置は、イコールコストマルチパスのうち、いずれのパスを使用しても宛先までパケットの転送が可能である。

図１２を用いて、イコールコストマルチパスが存在する例について説明を行う。図１２は、イコールコストマルチパスを示すネットワーク図である。ルータ装置５４からルータ装置５１へのパスは、図１２（ｃ）に示すようにパス６１及びパス６２の二つ存在する。それぞれのパスのコスト値は共に「５」となるため、パス６１，６２はイコールコストマルチパスである。

ここで、図１２（ａ）に示すように、正常時において、例えば、ルータ装置５４がルータ装置５１へのパスとしてパス６２を使用することとすると、ルータ装置５１宛てのパケットはリンク７４に送出される。一方、リンク７４がダウンした場合、ルータ装置５４はパス６２とイコールコストであるパス６１を使用してパケットを転送する。パス６１はリンクダウン以前からルータ装置５４とルータ装置５１との間の最短パスであるため、図１２（ｂ）のようにリンク７４ダウン後に即座に切り替えても、パケットは、ループとならずルータ装置５１まで到達することが可能である。

ループの検出方式の従来例が、特許文献１に示す特許第３５５３３９８号公報「ルーティング装置及びルーティング方法」に記載されている。この従来例では、宛先毎に宛先ノードをルートノードとする逆方向の最短パスツリーを計算することによりループが発生するか否かの判定が行われている。該特許文献１の目的は、ルーティングの結果、パケットが送出されるべきリンクが輻輳しているときに、代わりに他のリンクに送出する際にそのリンクがループとならないかを調べることにある。この方法では、各ノードにおいて宛先ノード毎に最短パスツリーの計算を行う必要がある。

このように、前記特許文献１の例では、輻輳の回避が目的であるため、すべての宛先のパケットに対して迂回を行う必要は必ずしもなく、トラフィックの多いいくつかの宛先に対して最短パスツリーの計算を行えばよい。

しかし、前記特許文献１の技術では、リンク故障時の迂回を目的とする場合には、故障リンクを通過するパケットのすべての宛先に対して、最短パスツリーを計算する必要がある。

このため、前記特許文献１の方法を、リンク故障時の代替経路のループ判定に用いるには、計算量が多くなり、現実的でない。

また、特許文献２に示す特開２００３−２７３９０４号公報「経路制御方法、経路制御装置」には、想定した故障のリンクもしくは隣接ルータ装置を除いた状態におけるトポロジー情報を基にした最短パスツリーを用いて代替経路を算出する技術が記載されているが、算出された代替経路がループ状態を生じるか否かまで判定することができない。

特許第３５５３３９８号公報（第５頁、図４） 特開２００３−２７３９０４号公報（第６頁、図５）

前述のように、従来技術における問題点は、リンクの故障時にそのリンクを使用する全経路に対して高速経路切替を行うと、ループとなる経路が生じる可能性がある点である。ループが発生すると、該当するパケットが宛先に到達できないだけでなく、転送を行うルータ装置の負荷が増大していくという問題がある。

ループが生じる理由は、故障を検知したルータ装置は、リンク故障後のトポロジー情報を元に計算を行った代替経路表を用いてパケットの転送を行うが、自律システム内の他のルータ装置が用いている経路表を計算する際に用いたトポロジー情報は故障した当該リンクが故障していない状態のものであったためである。

更には、従来は、リンク故障にも対処可能な有効なループ判定方法が存在していないために、例えばＩＰにおける高速経路切替技術としては、実際に使用されるまでには至っていない。

本発明の目的は、代替経路のループ判定を行い、ループとならない経路のみを用いる高速経路切替方式を提供することにある。ループ判定によりループするものと判断された経路については、高速経路切替時に使用しないようにし、転送パケットのループの発生を防止し、ループによるパケット転送の処理負荷を軽減することを可能にすることにある。一方、ループ判定によりループしないと判定された経路に関しては、リンク故障時に高速経路切替を行う代替経路として採用し、経路制御プロトコルにより、故障発生後のトポロジー情報を元にした経路情報の更新が完了するまでの間、該代替経路を用いてパケットの転送を継続することを可能にすることにある。

前述の課題を解決するため、本発明によるネットワーク、ルータ装置、それに用いる切替方法及びそのプログラム並びにプログラム記録媒体は、次のような特徴的な構成を採用している。

（１）外部と接続するためのネットワークインターフェイスと、予め主経路表に格納された経路情報に基づいて前記ネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送部と、前記主経路表に格納する経路情報を算出する主経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替部とを少なくとも有するルータ装置であって、
前記代替経路計算部により前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定部を有し、該ループ経路判定部によりループとならないと判定された代替経路を前記代替経路表に格納するルータ装置。
（２）前記代替経路計算部において、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、代替経路を計算する上記（１）のルータ装置。
（３）前記ループ経路判定部において、前記主経路計算部により算出された経路情報における宛先までのコスト値と、前記代替経路計算部により算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行う上記（１）または（２）のルータ装置。
（４）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定部においてループになると判定された経路を前記ループ経路表に格納するループ経路格納部を有する上記（１）乃至（３）のいずれかのルータ装置。
（５）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（４）のルータ装置。
（６）他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信部を有する上記（４）または（５）のルータ装置。
（７）他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（６）のルータ装置。
（８）外部と接続するためのネットワークインターフェイスと、予め主経路表に格納された経路情報に基づいて前記ネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送部と、前記主経路表に格納する経路情報を算出する主経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替部とを少なくとも有するルータ装置を含むネットワークであって、
前記代替経路計算部により前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定部を前記ルータ装置に有し、該ループ経路判定部によりループとならないと判定された代替経路を前記代替経路表に格納するネットワーク。
（９）前記ルータ装置の前記代替経路計算部において、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、代替経路を計算する上記（８）のネットワーク。
（１０）前記ルータ装置の前記ループ経路判定部において、前記主経路計算部により算出された経路情報における宛先までのコスト値と、前記代替経路計算部により算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行う上記（８）または（９）のネットワーク。
（１１）前記ルータ装置において、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定部においてループになると判定された経路を前記ループ経路表に格納するループ経路格納部を有する上記（８）乃至（１０）のいずれかのネットワーク。
（１２）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（１１）のネットワーク。
（１３）前記ルータ装置において、他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信部を有する上記（１１）または（１２）のネットワーク。
（１４）他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（１３）のネットワーク。
（１５）予め主経路表に格納された経路情報に基づいて、外部と接続するためのネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送ステップと、前記主経路表に格納する経路情報を算出する主経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替ステップとを少なくとも有する切替方法であって、
前記代替経路計算ステップにより前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定ステップを有し、該ループ経路判定ステップによりループとならないと判定された代替経路を前記代替経路表に格納する切替方法。
（１６）前記代替経路計算ステップにおいて、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、代替経路を計算する上記（１５）の切替方法。
（１７）前記ループ経路判定ステップにおいて、前記主経路計算ステップにより算出された経路情報における宛先までのコスト値と、前記代替経路計算ステップにより算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行う上記（１５）または（１６）の切替方法。
（１８）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定ステップにおいてループになると判定された経路を前記ループ経路表に格納するループ経路格納ステップを有する上記（１５）乃至（１７）のいずれかの切替方法。
（１９）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（１８）の切替方法。
（２０）他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信ステップを有する上記（１８）または（１９）の切替方法。
（２１）他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（２０）の切替方法。
（２２）予め主経路表に格納された経路情報に基づいて、外部と接続するためのネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送ステップと、前記主経路表に格納する経路情報を算出する主経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替ステップとを少なくともルータ装置にて実行させる切替プログラムであって、
前記代替経路計算ステップにより前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定ステップを有し、該ループ経路判定ステップによりループとならないと判定された代替経路を前記代替経路表に格納する切替プログラム。
（２３）前記代替経路計算ステップにおいて、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、代替経路を計算する上記（２２）の切替プログラム。
（２４）前記ループ経路判定ステップにおいて、前記主経路計算ステップにより算出された経路情報における宛先までのコスト値と、前記代替経路計算ステップにより算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行う上記（２２）または（２３）の切替プログラム。
（２５）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定ステップにおいてループになると判定された経路を前記ループ経路表に格納するループ経路格納ステップを有する上記（２２）乃至（２４）のいずれかの切替プログラム。
（２６）前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（２５）の切替プログラム。
（２７）他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信ステップを有する上記（２５）または（２６）の切替プログラム。
（２８）他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納する上記（２７）の切替プログラム。
（２９）上記（２２）乃至（２８）のいずれかの切替プログラムを、コンピュータにより読み取り可能な記録媒体に記録しているプログラム記録媒体。

本発明のネットワーク、ルータ装置、それに用いる切替方法及びそのプログラム並びにプログラム記録媒体によれば、以下のような効果を得ることができる。

すなわち、本発明による効果は、リンク故障時の高速経路切替を行う際にループとなる経路を切り替え対象から除外することができ、転送パケットのループの発生を防止し、ルータ装置の負荷を軽減しつつ、高速経路切替が実現できることである。その理由は、代替経路計算時のパスのコストを利用することにより、ループ判定を行うことが可能となるためである。

更に説明すれば、故障を想定するリンクもしくは隣接ルータ装置を除いた状態におけるトポロジーを元にした最短パスツリーを使用して、代替経路計算部により算出される代替経路情報と、主経路計算部により算出される主経路情報と、を用いて、代替経路がループとなるか否かをループ経路判定部にて判定し、ループとならない経路のみを代替経路としてあらかじめ設定して、リンク故障もしくは隣接ルータ装置の故障の際に、該代替経路に高速経路切替を行うことにより、該代替経路を用いてパケットの転送を継続することを可能とし、もって、パケットの損失を最小限に抑えることができる。

また、本発明による他の効果は、リンクやルータ装置の故障発生後に、自律システム内の各ルータ装置が、従来の経路制御プロトコルによる経路情報の更新を行ったとしても、リンクや隣接ルータ装置の故障発生からあらかじめ定めた一定時間経過後やあるいは他のルータ装置からの経路更新完了の通知を受信した以降においては、ループとなる経路は発生しないことである。その理由は、自律システム内の各ルータ装置は、故障発生後のトポロジーを元にして算出した経路によりルーティング処理を行うためである。

以下、本発明によるネットワーク、ルータ装置、それに用いる切替方法及び切替プログラム並びにそのプログラム記録媒体の好適な実施例について添付図を参照して説明する。なお、以下の実施例の説明においては、本発明によるルータ装置（ノード）の具体的な構成やネットワーク接続形態について、図面を参照しながら詳細に説明する。かかる説明により、本発明によるネットワークの具体的な実施例や、それらに用いる経路の切替方法の実施例について、さらには、該切替方法をルータ装置上に搭載のコンピュータにより実行可能な切替プログラムの実施例や、該切替プログラムをコンピュータにより読み取り可能な記録媒体に記録したプログラム記録媒体の実施例についても、容易に想到することができるので、これらの発明に関する具体的な実施例についての説明を割愛する。

（第１の実施例）
まず、本発明によるルータ装置（ノード）の第１の実施例について図面を参照して詳細に説明する。

図１は、本発明によるルータ装置の機能構成の一実施例を示すブロック構成図である。また、図２は、本発明によるルータ装置における主経路表及び代替経路表の一構成例を示すテーブル構成図である。

図１において、本発明によるルータ装置１は、経路制御部１１、パケット転送部１２、高速切替部１３及びネットワークインターフェイス２１〜２ｎとを少なくとも含んで構成される。経路制御部１１は、トポロジー情報交換部１１１、主経路計算部１１２、代替経路計算部１１３及びループ経路判定部１１４を含んで構成される。

パケット転送部１２は、ルーティング処理部１２１、主経路表１２２を含んで構成される。ネットワークインターフェイス２１〜２ｎは、各隣接ルータ装置（ノード）との間のリンク３１〜３ｎとそれぞれ接続されて、隣接ルータ装置（ノード）との間のパケット送受信を行う。高速切替部１３は、リンク３１〜３ｎ毎に対応して用意された代替経路表１３１１〜１３１ｎを含む経路切替部１３１、故障検知部１３２を少なくとも含んで構成される。

経路制御部１１のトポロジー情報交換部１１１は、ＯＳＰＦ（Open Shortest Path First routing）などの従来の経路制御プロトコルを使用して、隣接ルータ装置との間でトポロジー情報の交換を行う。収集したトポロジー情報は主経路計算部１１２及び代替経路計算部１１３に引き渡される。

また、トポロジー情報交換部１１１は、ネットワークインターフェイス２１〜２ｎからリンクや隣接ルータ装置（ノード）の故障通知を受けた場合、トポロジー情報に変化が発生したと認識し、その変化分を各隣接ルータ装置に通知する。

主経路計算部１１２は、通常のＩＧＰ（Interior Gateway Protocol）の経路計算を行い、主経路表１２２に経路情報の登録を行う。

代替経路計算部１１３は、各ネットワークインターフェイス２１〜２ｎに接続している各リンク３１〜３ｎそれぞれについて、トポロジー情報交換部１１１から得たトポロジー情報を元に、該当リンクが故障した場合のトポロジーを用いて経路計算を行い、代替経路を算出する。

ループ経路判定部１１４は、代替経路計算部１１３により算出された代替経路情報と主経路計算部１１２により算出された経路情報とを用いてループ判定を行い、ループしないと判定された経路情報のみを各故障リンク毎に用意された代替経路表１３１１〜１３１ｎに登録する。

パケット転送部１２の主経路表１２２の構成例を図２（ａ）に示す。図２（ａ）における主経路表１２２は、宛先１２２１、マスク長１２２２、次転送先１２２３、インターフェイス１２２４及びコスト１２２５で一組となる経路情報を格納したテーブルである。なお、図２（ａ）の主経路表１２２では、宛先１２２１や次転送先１２２４に例示するように、ＩＰｖ４の場合の例を示しているが、ＩＰｖ６の場合も、同様なエントリを有するテーブルとして構成すればよい。

パケット転送部１２のルーティング処理部１２１は、各ネットワークインターフェイス２１〜２ｎから受信したパケットのヘッダ部分にある宛先アドレスのフィールドを参照し、主経路表１２２を使って、次転送先アドレスとインターフェイスを検索する。ルーティング処理部１２１は、検索結果のインターフェイスを経由して次転送先アドレスのルータ装置に対して、受信したパケットを送出する。

高速切替部１３の故障検知部１３２は、各ネットワークインターフェイス２１〜２ｎの状態を常時監視しており、故障を検知すると、経路切替部１３１に対して切替指示を行う。ここでの故障とは、ネットワークインターフェイス２１〜２ｎ自身のハードウェア故障、ネットワークインターフェイス２１〜２ｎが接続している各リンク３１〜３ｎのダウン、及び隣接ルータ装置の故障を含んでいる。ここで、故障検知部１３２は、以下のいずれかもしくはその組み合わせによる故障検知を行っている。

（ａ）ネットワークインターフェイスのハードウェアの機能を利用した、ネットワークインターフェイスハードウェア故障の検知
（ｂ）ネットワークインターフェイスの機能を利用した、下位レイヤのリンクダウンの検知
（ｃ）隣接ルータ装置に対するkeepaliveパケットの送信、受信による隣接ルータ装置の死活監視

ここでは、ネットワークインターフェイス２１〜２ｎの故障は、そのネットワークインターフェイス２１〜２ｎに接続しているリンク３１〜３ｎの故障と同様に扱う。

経路切替部１３１は、代替経路表１３１１〜１３１ｎを含んで構成しており、代替経路表１３１１〜１３１ｎは、それぞれネットワークインターフェイス２１〜２ｎに対応しており、故障検知部１３２による故障検知時に、主経路表１２２中の経路と入れ替えを行うための代替経路情報を格納している。

一例として、図２（ｂ）に、リンク３１を接続するネットワークインターフェイス２１に対応する代替経路表１３１１のテーブル構成例を示す。ネットワークインターフェイス２１の代替経路表１３１１は、主経路表１２２の構成と同様に、宛先１３１１１、マスク長１３１１２、次転送先１３１１３、インターフェイス１３１１４及びコスト１３１１５で一組となる経路情報を格納したテーブルから構成される。

経路切替部１３１は、故障検知部１３２から切替指示を受け取ると、故障したリンク例えばリンク３１のネットワークインターフェイス２１に対応した代替経路表１３１１の経路情報を主経路表１２２の経路情報と入れ替える。ただし、入れ替えを行うのは、代替経路表１３１１に登録されている経路情報のみである。

図２の例を用いて説明すると、主経路表１２２に登録されている経路情報のうち、宛先１２２１の「192.168.1.0」及び「192.168.12.0」の経路情報は、代替経路表１３１１にも代替経路を有する宛先１３１１１として登録されているため、ネットワークインターフェイス２１の故障時には、この経路情報の次転送先１２２３の「172.16.1.254」及び「172.16.1.254」を、代替経路表１３１１に登録されている次転送先１３１１３の「172.16.3.254」及び「172.16.5.1」への入れ替えが行われる。しかし、主経路表１２２中の宛先１２２１の「192.168.10.0」の経路情報は、代替経路表１３１１中には存在していないので、ネットワークインターフェイス２１の故障時には入れ替えなどは行わず、そのまま使用する。

ここまでの説明は、ルータ装置１に接続しているリンクの故障のみを対象として説明を行ってきたが、本発明は、隣接ルータ装置の故障の場合にも同様に適用可能である。その場合、代替経路表は、当該ルータ装置に隣接するルータ装置の数だけ用意される。隣接ルータ装置の故障の検知には、前述の隣接ルータ装置に対するkeepaliveパケットの送受信による死活監視による方法を使用する。

（動作説明）
次に、図３〜４を参照して、図１の実施例に示すルータ装置１の動作について詳細に説明する。ここで、図３は、本発明によるルータ装置における代替経路決定処理の一例を示すフローチャートであり、図４は、本発明によるルータ装置におけるループ判定処理の一例を示すフローチャートである。

本発明の機能を採用したルータ装置１においても、通常時は、一般のルータ装置と同様の動作を行っている。すなわち、各ネットワークインターフェイス２１〜２ｎから受信したパケットは、パケット転送部１２の主経路表１２２において決定される次転送先ルータ装置に送出される。また、一般のルータ装置では、ルータ装置の新規起動時及び自律システム内の他のルータ装置からトポロジーの変化の通知を受けたときに、経路制御部１１の主経路計算部１１２において、隣接ルータ装置との間で交換されるトポロジー情報を元に経路計算が行われ、主経路表１２２に経路情報が登録される。

まず、本ルータ装置１の主経路表１２２及び代替経路表１３１１〜１３１ｎの経路計算手順について、図３のフローチャートを用いて説明する。

トポロジー情報交換部１１１にて収集したトポロジー情報を元にして、主経路計算部１１２において自律システム中の全ノードに対する最短パスツリーを用いた経路計算を行う（ステップＳ１）。

しかる後、代替経路計算部１１３による代替経路の計算を行う。
まず、ルータ装置１に接続されているリンク３１〜３ｎのうち、代替経路の計算を行っていないリンクを一つ、例えばリンク３１を、選択する（ステップＳ２）。

選んだリンク例えばリンク３１が故障したと想定した場合の経路計算を、代替経路計算部１１３にて行い、自律システム中の全ノードに対する代替経路情報を算出する（ステップＳ３）。

次に、ステップＳ１の計算結果（主経路情報）とステップＳ３の計算結果（代替経路情報）との比較を行う（ステップＳ４）。この比較により、同一の宛先に対して、次転送先、送出インターフェイスが両者で異なる経路の抽出を行う。

ステップＳ４で抽出された経路のうち、ループ判定を行っていない経路を一つ選び（ステップＳ５）、該経路のループ判定を行う（ステップＳ６）。経路のループ判定の詳細については、別途後述する。

ステップＳ６のループ判定において、該当経路がループにならないと判定された場合には（ステップＳ６のＮｏ）、リンクごとに用意された代替経路表例えばリンク３１の代替経路の登録用として用意された代替経路表１３１１に、該当経路を前記宛先に対する代替経路として登録する（ステップＳ７）。一方、ステップＳ６のループ判定において、該当経路がループとなると判定された場合には（ステップＳ６のＹｅｓ）、代替経路表への登録は行わずに、ステップＳ８へと進む。

次に、ループ判定を行っていない代替経路がまだ残っているか否かを調べ（ステップＳ８）、残っていれば（ステップＳ８のＹｅｓ）、ステップＳ５へ戻り、残っている代替経路についてループ判定を行う。一方、残っていなければ（ステップＳ８のＮｏ）、ルータ装置１に接続しているリンクのうち、代替経路を計算していないリンクがまだ存在するか否かを調べる（ステップＳ９）。存在する場合には（ステップＳ９のＹｅｓ）、ステップＳ２に戻り、次のリンクに関する代替経路を計算する処理を行い、存在しない場合には（ステップＳ９のＮｏ）、主経路、代替経路の計算に関する一連の手順を終了する。

次に、本発明によるルータ装置１のループ判定手順の一例について、図４のフローチャートを用いて説明する。

まず、ループ判定を行う経路情報において、主経路計算時に求めた宛先までのコスト値を変数ｘに代入する（ステップＳ１１）。次に、リンク故障時の代替経路における宛先までのコスト値を変数ｙに代入する（ステップＳ１２）。さらに、故障時の代替経路における次ルータ装置までのリンクのコスト値を変数ｚに代入する（ステップＳ１３）。

次に、それぞれの値が代入された変数ｘ,ｙ,ｚを用いて、
（ｙ−ｚ） ＜ （ｘ＋ｚ）
という不等式が成り立つか否かを調べる（ステップＳ１４）。

この不等号が成り立つ場合には（ステップＳ１４のＹｅｓ）、当該経路はループしないものと判定する（ステップＳ１５）。

一方、ステップＳ１４における不等式が成り立たない場合は（ステップＳ１４のＮｏ）、当該経路はループするものと判定する（ステップＳ１６）。

ステップＳ１４におけるこの不等式の判定により、当該経路のループ判定が可能であることを、図５のネットワーク図を用いて説明する。ここに、図５は、本発明によるルータ装置における代替経路のループ判定の一例を説明するためのネットワーク図である。

図５においては、一例として、図１１として前述した場合と同様に、ルータ装置（ノード）５４におけるルータ装置（ノード）５３宛ての経路を対象として示している。パケット送信元（ｓｒｃ：ｓｏｕｒｃｅ）のルータ装置５４におけるパケット送信先（ｄｓｔ：ｄｅｓｔｉｎａｔｉｏｎ）のルータ装置５３までの経路としては、リンク７４の故障前は、パス６１が最短パスであり、主経路表１２２にこのパス６１が登録されている。このパス６１のコストが「ｘ」であるとする。

一方、リンク７４が故障したときに、ルータ装置５４は、代替経路の計算において、パス６２を導き出し、次転送先ルータ装置としてルータ装置５２が選択されるものとする。また、パス６２のコストは「ｙ」であるとする。このとき、隣のルータ装置５２がルータ装置５３宛てのパケットを、パス６２に沿っているパス６３を使用するか、もしくはルータ装置５４に戻るパス６４を使用するかを調べる必要がある。

ルータ装置５４とルータ装置５２との間のリンク７２のコストを「ｚ」とすると、パス６３のコストは、
（ｙ−ｚ）
であり、一方、パス６４のコストは、
（ｘ＋ｚ）
となる。

このときに、ルータ装置５２において、ルータ装置５３宛ての経路として、パス６４ではなく、パス６３が選ばれるのは、パス６３のコストがパス６４のコストよりも小さいときであり、不等式
（ｙ−ｚ） ＜ （ｘ＋ｚ）
が成り立つ場合である。よって、図４のステップＳ１４に示すように、この不等式が成り立つときには、代替経路はループとならないものと判定することができ、該代替経路が代替経路表に登録される。

（第２の実施例）
次に、本発明によるルータ装置（ノード）の第２の実施例について図面を参照して詳細に説明する。

図６は、本発明によるルータ装置の機能構成の他の実施例を示すブロック構成図であり、第２の実施例におけるブロック構成図を例示している。図６に示すルータ装置１Ａは、第１の実施例として図１に示したルータ装置１の高速切替部１３とは異なる構成の高速切替部１３Ａを備えている以外は、図１のルータ装置１と全く同様の構成である。

すなわち、図６に示すルータ装置１Ａは、高速切替部１３Ａの経路切替部１３１Ａ中に、図１の場合と同様の代替経路表１３１１〜１３１ｎを備えている他に、さらに、ループ経路表１３２１〜１３２ｎを備えている点が、第１の実施例に示したルータ装置１と異なっている。

ループ経路表１３２１〜１３２ｎは、代替経路表１３１１〜１３１ｎと同様に、故障を想定した各リンク毎に用意されており、ループ経路判定部１１４においてループと判定された経路情報を格納している。

本発明によるルータ装置においては、リンク故障時に即座に経路を切り替える高速経路切替を行う際に、前述したように、代替経路がループとなるか否かの判定を行っている。しかし、本発明による高速経路切替における代替経路情報は、リンク故障後のトポロジー情報を元に計算したものを使用しているため、リンク故障発生後、経路制御プロトコルにより自律システム内のトポロジー情報の同期が終了した後であれば、代替経路としてループと判定された経路も含めて、すべての経路が、ループとなることはない。このため、本実施例においては、ループ経路判定部１１４においてループすると判定された経路も、経路制御プロトコルによる自律システム内のトポロジー情報の同期後に使用可能とするために、ループ経路表１３２１〜１３２ｎにあらかじめ格納しておく。

次に、図７のフローチャートを用いて、本実施例におけるリンク故障発生時の切替動作について説明する。図７は、本発明によるルータ装置における故障検出時の切替処理の他の例を示すフローチャートであり、第２の実施例における切替手順を示している。

通常動作時においては、接続されているいずれかのリンクの故障が検出されるまで待ち合わせる（ステップＳ２１）。

故障が検出されたときには（ステップＳ２１のＹｅｓ）、接続リンク毎に用意された代替経路表１３１１〜１３１ｎのうち、故障したリンク例えばリンク３１に対応した代替経路表例えば代替経路表１３１１の内容に、主経路表１２２の内容を入れ替える（ステップＳ２２）。

次に、トポロジー情報交換部１１１により、自律システム内の他のルータ装置にリンクの故障に伴うトポロジー情報の変化を通知する（ステップＳ２３）。

さらに、リンクの故障を検知してからあらかじめ定めた一定時間ts経過後に、ループ経路表１３２１〜１３２ｎのうち、故障リンクに対応するループ経路表例えばループ経路表１３２１の経路情報を主経路表１２２に追加登録する（ステップＳ２４）。その後、主経路表１２２、代替経路表１３１１〜１３１ｎ及びループ経路表１３２１〜１３２ｎの内容を、新しいトポロジーを基にしたものに更新する（ステップＳ２５）。

ここで、リンク故障検知した時点から、ループ経路表１３２１〜１３２ｎのいずれか該当するループ経路表の内容を主経路表１２２に追加登録するまでの一定時間であるtsは、ネットワーク中のトポロジー情報の同期に要する時間を見積もった値であり、予め設定しておく。

このことにより、トポロジー情報の同期後の主経路計算部１１２による新たな経路情報の更新処理における処理負荷を削減することができる。

（第３の実施例）
次に、本発明によるルータ装置（ノード）の第３の実施例について図面を参照して詳細に説明する。

図８は、本発明によるルータ装置の機能構成のさらに異なる実施例を示すブロック構成図であり、第３の実施例におけるブロック構成図を例示している。図８に示すルータ装置１Ｂは、第２の実施例として図６に示したルータ装置１Ａの経路制御部１１とは異なる構成の経路制御部１１Ａを備えている以外は、図６のルータ装置１Ａと全く同様の構成である。

すなわち、図８に示すルータ装置１Ｂは、経路制御部１１Ａ中に経路更新完了送信部１１５と経路更新完了受信部１１６とをさらに備えている点が、第２の実施例に示すルータ装置１Ａの経路制御部１１とは異なっている。第２の実施例では、ループ経路表１３２１〜１３２ｎの内容を主経路表１２２に追加登録するタイミングtsが、リンク故障が発生してからあらかじめ決められた時間の経過後であった。しかし、この時間tsを決めるためには、自律システム内の各ルータ装置におけるトポロジー情報の同期が終了するのに十分な時間を見積もる必要があり、適切な値を決めることが難しい。

本実施例においては、自律システム内の各ルータ装置のうち、故障リンクに直接接続していないルータ装置は、一般のルータ装置と同様に、従来の経路制御プロトコルを用いた経路情報更新の動作を行っている。

つまり、故障リンクに接続しているルータ装置からのトポロジー情報変更のメッセージをトポロジー情報交換部１１１において受信し、主経路計算部１１２において新しいトポロジー情報を元に経路計算を行い、得られた経路情報を主経路表１２２に登録する。主経路表１２２の経路情報の更新が完了すると、主経路計算部１１２は、経路更新完了送信部１１５に経路情報更新完了の通知を行う。

経路情報更新完了の通知を受けた経路更新完了送信部１１５は、隣接ルータ装置に対して、経路情報の更新が完了した旨を示す経路情報更新完了メッセージを送信する。

一方、経路情報更新完了メッセージを経路更新完了受信部１１６にて受信したルータ装置は、経路切替部１３１Ａにおいてループ経路表１３２１〜１３２ｎの内容を主経路表１２２へ追加登録する。

主経路表１２２への追加登録を行う場合、まず、リンクもしくは隣接ルータ装置毎に用意されているループ経路表１３２１〜１３２ｎのうち、故障したリンクもしくは隣接ルータ装置に対応したものを選ぶ。次に、故障リンクもしくは故障隣接ルータ装置に対応するそのループ経路表に格納されている経路情報のうち、次転送先が経路更新完了メッセージの送信元のルータ装置のＩＰアドレスが示す経路情報のみを選択して、主経路表１２２に追加登録する。つまり、ループする経路情報のうち、次転送先の経路が更新されたものは、もはや、ループを起こさない経路であるので、自身の主経路表１２２に追加登録し、パケットの転送に用いるということである。

また、第２の実施例における方法と組み合わせて使用してもよい。第３の実施例の方法では、経路更新完了メッセージを受信しない限り、ループ経路表１３２１〜１３２ｎ中の経路情報が主経路表１２２に反映されることはないが、ある経路更新完了メッセージがなんらかの理由により送られてこない場合には、あらかじめ決められた時間だけ待って、その後、経路更新完了メッセージを受信していないルータ装置に関するループ経路表１３２１〜１３２ｎの経路情報を主経路表１２２に登録するようにしてもよい。

以上のように、動的経路制御が行われている自律システムにおいて、リンクやルータ装置の故障により、経路情報の更新が必要になった場合、従来技術では、自律システム中の他のルータ装置へのトポロジー変化の通知や経路計算に、約数百msの時間を要するため、この間正常なパケット転送ができなくなる事態が発生する。あるいは、従来の高速経路切替として、故障を検知したルータ装置が事前に計算しておいた代替経路に即座に切り替えた際に、転送パケットがループしてしまい、正しく転送できなくなるのみならず、転送を行うルータ装置が過負荷状態に陥るという欠点があった。

これに対して、本発明によるルータ装置によれば、接続するリンクや隣接のルータ装置（ノード）の故障を検知したときに、動的経路制御による経路情報の更新を行うことがないので、高速な切替動作が可能であり、さらに、高速切替用の代替経路として事前に計算する際に、当該代替経路がループになるか否かを判定して、ループにならない経路のみを用いることとしているので、故障検知時に、代替経路を直ちに切り替えても、転送パケットは、ループが発生せず、正しく転送することができるとともに、ルータ装置が過負荷になることもなく、高速な経路切替を正常に実現することができる。

このように、本発明によるルータ装置は、故障による通信途絶の絶無が期待されるキャリアバックボーンのＩＰネットワークにおける高可用性ルータ装置に好適に適用することが可能である。また、本発明による高速切替方法は、無線リンクにより構成される無線ネットワークにも有効に適用可能である。無線リンクは、有線のリンクよりも、外部要因により切断状態になる可能性が高い。このため、リンクダウン時に即座に経路を切り替えることができ、また、ループにより帯域を浪費することなく、通信を継続することが可能となる本発明による高速切替方法が有効である。

以上、本発明の好適実施例の構成を説明した。しかし、斯かる実施例は、本発明の単なる例示に過ぎず、何ら本発明を限定するものではないことに留意されたい。本発明の要旨を逸脱することなく、特定用途に応じて種々の変形変更が可能であることが、当業者には容易に理解できよう。

本発明によるルータ装置の機能構成の一実施例を示すブロック構成図である。 本発明によるルータ装置における主経路表及び代替経路表の一構成例を示すテーブル構成図である。 本発明によるルータ装置における代替経路決定処理の一例を示すフローチャートである。 本発明によるルータ装置におけるループ判定処理の一例を示すフローチャートである。 本発明によるルータ装置における代替経路のループ判定の一例を説明するためのネットワーク図である。 本発明によるルータ装置の機能構成の他の実施例を示すブロック構成図である。 本発明によるルータ装置における故障検出時の切替処理の他の例を示すフローチャートである。 本発明によるルータ装置の機能構成のさらに異なる実施例を示すブロック構成図である。 従来のルータ装置の機能構成を示すブロック構成図である。 従来の高速経路切替技術におけるパケット転送経路を示すネットワーク図である。 従来の高速経路切替技術におけるループの発生を示すネットワーク図である。 イコールコストマルチパスを示すネットワーク図である。

符号の説明

１，１Ａ，１Ｂ，１Ｃ ルータ装置（ノード）
１１，１１Ａ 経路制御部
１１１ トポロジー情報交換部
１１２ 主経路計算部
１１３ 代替経路計算部
１１４ ループ経路判定部
１１５ 経路更新完了送信部
１１６ 経路更新完了受信部
１２ パケット転送部
１２１ ルーティング処理部
１２２ 主経路表
１２２１ 宛先
１２２２ マスク長
１２２３ 次転送先
１２２４ インターフェイス
１２２５ コスト
１３，１３Ａ 高速切替部
１３１，１３１Ａ 経路切替部
１３１１〜１３１ｎ 代替経路表
１３１１１ 宛先
１３１１２ マスク長
１３１１３ 次転送先
１３１１４ インターフェイス
３１１１５ コスト
１３２ 故障検知部
１３２１〜１３２ｎ ループ経路表
２１〜２ｎ ネットワークインターフェイス
３１〜３ｎ リンク
５１〜５４ ルータ装置（ノード）
６１〜６４ パス
７１〜７４ リンク

Claims (29)

1. 外部と接続するためのネットワークインターフェイスと、予め主経路表に格納された経路情報に基づいて前記ネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送部と、前記主経路表に格納する経路情報を算出する主経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替部とを少なくとも有するルータ装置であって、
   前記代替経路計算部により前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定部を有し、該ループ経路判定部によりループとならないと判定された代替経路を前記代替経路表に格納することを特徴とするルータ装置。
2. 前記代替経路計算部において、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、代替経路を計算することを特徴とする請求項１に記載のルータ装置。
3. 前記ループ経路判定部において、前記主経路計算部により算出された経路情報における宛先までのコスト値と、前記代替経路計算部により算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行うことを特徴とする請求項１または２に記載のルータ装置。
4. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定部においてループになると判定された経路を前記ループ経路表に格納するループ経路格納部を有することを特徴とする請求項１乃至３のいずれかに記載のルータ装置。
5. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項４に記載のルータ装置。
6. 他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信部を有することを特徴とする請求項４または５に記載のルータ装置。
7. 他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項６に記載のルータ装置。
8. 外部と接続するためのネットワークインターフェイスと、予め主経路表に格納された経路情報に基づいて前記ネットワークインターフェイス経由で受信したパケットのルーティング処理を行う
   パケット転送部と、前記主経路表に格納する経路情報を算出する主経路計算部と、 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算部と、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替部とを少なくとも有するルータ装置を含むネットワークであって、
   前記代替経路計算部により前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定部を前記ルータ装置に有し、該ループ経路判定部によりループとならないと判定された代替経路を前記代替経路表に格納することを特徴とするネットワーク。
9. 前記ルータ装置の前記代替経路計算部において、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、代替経路を計算することを特徴とする請求項８に記載のネットワーク。
10. 前記ルータ装置の前記ループ経路判定部において、前記主経路計算部により算出された経路情報における宛先までのコスト値と、前記代替経路計算部により算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行うことを特徴とする請求項８または９に記載のネットワーク。
11. 前記ルータ装置において、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定部においてループになると判定された経路を前記ループ経路表に格納するループ経路格納部を有することを特徴とする請求項８乃至１０のいずれかに記載のネットワーク。
12. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項１１に記載のネットワーク。
13. 前記ルータ装置において、他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信部を有することを特徴とする請求項１１または１２に記載のネットワーク。
14. 他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納部により前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項１３に記載のネットワーク。
15. 予め主経路表に格納された経路情報に基づいて、外部と接続するためのネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送ステップと、前記主経路表に格納する経路情報を算出する主経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替ステップとを少なくとも有する切替方法であって、
    前記代替経路計算ステップにより前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定ステップを有し、該ループ経路判定ステップによりループとならないと判定された代替経路を前記代替経路表に格納することを特徴とする切替方法。
16. 前記代替経路計算ステップにおいて、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、
    代替経路を計算することを特徴とする請求項１５の切替方法。
17. 前記ループ経路判定ステップにおいて、前記主経路計算ステップにより算出された経路情報における宛先までのコスト値と、前記代替経路計算ステップにより算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行うことを特徴とする請求項１５または１６に記載の切替方法。
18. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定ステップにおいてループになると判定された経路を前記ループ経路表に格納するループ経路格納ステップを有することを特徴とする請求項１５乃至１７のいずれかに記載の切替方法。
19. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項１８に記載の切替方法。
20. 他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信ステップを有することを特徴とする請求項１８または１９に記載の切替方法。
21. 他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項２０に記載の切替方法。
22. 予め主経路表に格納された経路情報に基づいて、外部と接続するためのネットワークインターフェイス経由で受信したパケットのルーティング処理を行うパケット転送ステップと、前記主経路表に格納する経路情報を算出する主経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに使用する代替経路を算出して代替経路表に格納する代替経路計算ステップと、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知したときに前記代替経路表に格納されている経路情報への入替処理を行う切替ステップとを少なくともルータ装置にて実行させる切替プログラムであって、
    前記代替経路計算ステップにより前記代替経路表に代替経路情報を格納する際に該代替経路がループとなるか否かの判定を行うループ経路判定ステップを有し、該ループ経路判定ステップによりループとならないと判定された代替経路を前記代替経路表に格納することを特徴とする切替プログラム。
23. 前記代替経路計算ステップにおいて、前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の想定した故障に対して、当該リンクまたはルータ装置を除いた状態のトポロジー情報を元に最短パスツリーを生成し、生成された最短パスツリーに基づいて経路計算を行うことにより、
    代替経路を計算することを特徴とする請求項２２に記載の切替プログラム。
24. 前記ループ経路判定ステップにおいて、前記主経路計算ステップにより算出された経路情報における宛先までのコスト値と、前記代替経路計算ステップにより算出された代替経路情報における宛先までのコスト値と、前記ネットワークインターフェイス毎に割り当てられているコスト値とを用いて、ループの判定を行うことを特徴とする請求項２２または２３に記載の切替プログラム。
25. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置毎に用意されるループ経路表を有し、前記ループ経路判定ステップにおいてループになると判定された経路を前記ループ経路表に格納するループ経路格納ステップを有することを特徴とする請求項２２乃至２４のいずれかに記載の切替プログラム。
26. 前記ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の故障を検知してからあらかじめ定めた一定時間経過した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項２５に記載の切替プログラム。
27. 他のルータ装置から経路の更新が完了した旨を示す経路更新完了メッセージを受信する経路更新完了受信ステップを有することを特徴とする請求項２５または２６に記載の切替プログラム。
28. 他のルータ装置から前記経路更新完了メッセージを受信した場合、前記ループ経路格納ステップにより前記ループ経路表に格納された経路を前記主経路表に追加して格納することを特徴とする請求項２７に記載の切替プログラム。
29. 請求項２２乃至２８のいずれかに記載の切替プログラムを、コンピュータにより読み取り可能な記録媒体に記録していることを特徴とするプログラム記録媒体。
    

Images