(57)【特許請求の範囲】
【請求項１】
経路サーバが、転送装置から前記転送装置間の隣接関係に関する情報である隣接情報を収集し、収集した前記隣接情報を基に、通信データの転送路である経路情報を計算し、前記計算した経路情報を前記転送装置それぞれへ配信し、  前記転送装置が、前記配信された経路情報を参照して、受信した通信データの転送を行うネットワークシステムであって、  前記経路サーバは、  前記経路情報として、前記転送装置間をつなぐ経路の障害発生前に使用するプライマリ経路情報と、前記経路の障害発生時に使用する１以上のバックアップ経路情報と、を計算し、前記各転送装置へ配信し、  前記各転送装置は、  前記経路サーバから配信されたプライマリ経路情報と、前記バックアップ経路情報と、を記憶部に格納し、  前記経路に障害が発生すると、参照する経路情報を、前記プライマリ経路情報から、前記バックアップ経路情報に切り換えて、前記通信データの転送を行い、 前記バックアップ経路情報によって前記通信データの転送を行っているときに、前記経路に障害が発生した場合、受信した通信データを破棄する  ことを特徴とするネットワークシステム。
【請求項２】
前記ネットワークシステムは、複数のエリアに分割されており、  どの前記経路サーバが、どの前記エリアに属する転送装置へ前記経路情報の配信を行うかが設定されており、  前記経路サーバのそれぞれは、前記エリア内の転送装置に対する前記プライマリ経路情報および前記バックアップ経路情報を計算し、  前記計算したプライマリ経路情報およびバックアップ経路情報を、前記経路情報の配信対象としている前記エリア内の転送装置へ配信する  ことを特徴とする請求項１に記載のネットワークシステム。
【請求項３】
前記複数のエリアは、  前記複数の経路サーバのうちの１つであるマスタ経路サーバが経路情報の配信対象としている第１のエリアと、  前記マスタ経路サーバとは別の経路サーバであるサブ経路サーバが経路情報の配信対象としている第２のエリアと、  を有しており、  前記サブ経路サーバは、  前記第２のエリアに属する転送装置から隣接情報を収集し、収集した前記隣接情報を基に、前記第２のエリアにおける転送装置の配置に関する情報であるトポロジ情報を計算し、計算した前記トポロジ情報を前記マスタ経路サーバへ送信し、  前記マスタ経路サーバは、前記第１のエリアに属する転送装置から隣接情報を収集するとともに、前記サブ経路サーバから、前記第２のエリアのトポロジ情報を収集し、前記収集した第１のエリアの隣接情報および前記第２のエリアのトポロジ情報を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、  前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、  前記マスタ経路サーバおよび前記サブ経路サーバのそれぞれは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象としている前記エリアに属する前記転送装置の経路情報を計算する  ことを特徴とする請求項２に記載のネットワークシステム。
【請求項４】
前記マスタ経路サーバは、  前記第１のエリアにおける転送装置間の障害が生じている転送装置の情報を含む障害情報を受信すると、  自身の記憶部に格納されている第２のエリアのトポロジ情報と、前記受信した障害情報と、を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、  前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、  前記マスタ経路サーバおよび前記サブ経路サーバは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象の前記エリアに属する前記転送装置のプライマリ経路情報を計算する  ことを特徴とする請求項３に記載のネットワークシステム。
【請求項５】
前記サブ経路サーバは、  前記経路情報の配信対象としている前記第２のエリアにおける転送装置間の障害が生じている転送装置間の接続情報を含む障害情報を受信すると、  当該障害情報を含む情報をマスタ経路サーバへ送信し、  前記マスタ経路サーバは、  自身の記憶部に格納されている第２のエリアのトポロジ情報と、前記送信された障害情報と、を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、  前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、  前記マスタ経路サーバおよび前記サブ経路サーバは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象としている前記エリアに属する前記転送装置のプライマリ経路情報を計算する  ことを特徴とする請求項３に記載のネットワークシステム。
【請求項６】
経路サーバが、転送装置から前記転送装置間の隣接関係に関する情報である隣接情報を収集し、収集した前記隣接情報を基に、通信データの転送路である経路情報を計算し、前記計算した経路情報を前記転送装置それぞれへ配信し、  前記転送装置が、前記配信された経路情報を参照して、受信した通信データの転送を行うネットワークシステムによる経路制御方法であって、  前記経路サーバは、  前記経路情報として、前記転送装置間をつなぐ経路の障害発生前に使用するプライマリ経路情報と、前記経路の障害発生時に使用する１以上のバックアップ経路情報と、を計算し、前記各転送装置へ配信し、  前記各転送装置は、  前記経路サーバから配信されたプライマリ経路情報と、前記バックアップ経路情報と、を記憶部に格納し、  前記経路に障害が発生すると、参照する経路情報を、前記プライマリ経路情報から、前記バックアップ経路情報に切り換えて、前記通信データの転送を行い、 前記バックアップ経路情報によって前記通信データの転送を行っているときに、前記経路に障害が発生した場合、受信した通信データを破棄する  ことを特徴とする経路制御方法。
【請求項７】
前記ネットワークシステムは、複数のエリアに分割されており、  どの前記経路サーバが、どの前記エリアに属する転送装置へ前記経路情報の配信を行うかが設定されており、  複数の前記経路サーバのそれぞれが、自身が前記経路情報の配信対象としている前記エリア内の転送装置へ配信する前記プライマリ経路情報および前記バックアップ経路情報を計算し、  前記計算したプライマリ経路情報およびバックアップ経路情報を、前記経路情報の配信対象としている前記エリア内の転送装置へ配信する  ことを特徴とする請求項６に記載の経路制御方法。
【請求項８】
前記複数のエリアは、  前記複数の経路サーバのうちの１つであるマスタ経路サーバが経路情報の配信対象としている第１のエリアと、  前記マスタ経路サーバとは別の経路サーバであるサブ経路サーバが経路情報の配信対象としている第２のエリアと、  を有しており、  前記サブ経路サーバは、  前記第２のエリアに属する転送装置から隣接情報を収集し、収集した前記隣接情報を基に、前記第２のエリアにおける転送装置の配置に関する情報であるトポロジ情報を計算し、計算した前記トポロジ情報を前記マスタ経路サーバへ送信し、  前記マスタ経路サーバは、前記第１のエリアに属する転送装置から隣接情報を収集するとともに、前記サブ経路サーバから、前記第２のエリアのトポロジ情報を収集し、前記収集した第１のエリアの隣接情報および前記第２のエリアのトポロジ情報を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、  前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、  前記マスタ経路サーバおよび前記サブ経路サーバのそれぞれは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象としている前記エリアに属する前記転送装置の経路情報を計算する  ことを特徴とする請求項７に記載の経路制御方法。
【請求項９】
前記マスタ経路サーバは、  前記第１のエリアにおける転送装置間の障害が生じている転送装置の情報を含む障害情報を受信すると、  自身の記憶部に格納されている第２のエリアのトポロジ情報と、前記受信した障害情報と、を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、  前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、  前記マスタ経路サーバおよび前記サブ経路サーバは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象の前記エリアに属する前記転送装置のプライマリ経路情報を計算する  ことを特徴とする請求項８に記載の経路制御方法。
【請求項１０】
前記サブ経路サーバは、  前記経路情報の配信対象としている前記第２のエリアにおける転送装置間の障害が生じている転送装置間の接続情報を含む障害情報を受信すると、  当該障害情報を含む情報をマスタ経路サーバへ送信し、  前記マスタ経路サーバは、  自身の記憶部に格納されている第２のエリアのトポロジ情報と、前記送信された障害情報と、を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、  前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、  前記マスタ経路サーバおよび前記サブ経路サーバは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象としている前記エリアに属する前記転送装置のプライマリ経路情報を計算する  ことを特徴とする請求項８に記載の経路制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、ネットワークシステムおよび経路制御方法の技術に関する。
【背景技術】
【０００２】
ネットワーク事業者において、転送網の機能追加や拡張を適宜行い、新たなネットワークサービスをフレキシブルかつ低コストに実現することは重要である。現在の一般的な転送装置（ルータなど）は、経路計算機能などを提供する制御系の機能と、実際にパケット転送を行うデータ転送系が同一筐体内に物理的に統合された構造となっている。そのため、ネットワークに要求される機能追加・拡張などに対し、フレキシブルに対応できないという課題がある。
【０００３】
このような問題点を解決する方法として、制御系機能とデータ転送系機能とを物理的に分離させてネットワーク上に分散配備するアーキテクチャが提案されている（例えば、非特許文献１参照）。
図１９は、従来のネットワークシステムの例を示す図であり、（ａ）は自律分散型のネットワークシステムであり、（ｂ）は非特許文献１に記載のアーキテクチャによるネットワークシステムを示す図である。
【０００４】
図１９（ａ）に示す自律分散型のネットワークシステム１９０１では、各々の転送装置１９０２が経路情報の計算および格納を行っている。
これに対し、図１９（ｂ）に示す非特許文献１に記載の制御系とデータ系を分離したネットワークシステム１９５１では経路計算機能やネットワーク情報収集などの制御系機能が経路サーバ１９５２に集中配備され、データ転送機能のみが転送装置１９５３に配備されることとなる。経路サーバ１９５２はすべての転送装置１９５３の経路情報１９５４を計算し、各転送装置１９５３へ、この経路情報を配信する。
【０００５】
転送装置１９５３は経路サーバ１９５２から受信した経路情報１９５４に従ってデータ転送（パケット転送）を行う。図１９（ｂ）のアーキテクチャにおいて、制御プロトコルの拡張や経路計算方式の変更などの機能追加は、制御系機能に対してのみ影響を与えるため、機能追加や拡張は転送装置に対して行うのではなく、経路サーバ１９５２に対してのみ行えばよい。このため、図１９（ｂ）のネットワークシステム１９５１によれば、新たなネットワークサービスをフレキシブルかつ低コストに実現できる。また、図１９（ａ）に示すアーキテクチャでは評価目的などのため、商用の転送装置１９０２に研究段階の機能の追加を行うことが困難であるが、制御系とデータ系を分離したアーキテクチャ（図１９（ｂ））ではキャリアが管理する経路サーバ１９５２に対して機能追加を行えばよいため、試験等が行いやすいというメリットがある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】M. Caesar, D. Caldwell, N. Feamster, J. Rexford, A. Shaikh, and J. V. D. Merwe, “Design and Implementation of a Routing Control Platform,” in proceedings of NSDI 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１に記載のアーキテクチャでは、ネットワークを構成するノード（転送装置）やリンクの障害が発生した場合、経路サーバ１９５２は障害発生後のネットワーク情報を収集し、経路計算を行い、再度すべての転送装置に配信する必要がある。このとき、経路サーバ１９５２はすべての転送装置の経路情報の計算と経路情報の作成を行う必要があるため処理負荷が増加する。例えば、図１９（ａ）に示すアーキテクチャのように経路計算機能を転送装置１９０２に配備した場合、各転送装置１９０２が自身の経路情報のみを作成すればよいのに対し、制御系とデータ系を分離した図１９（ｂ）のアーキテクチャでは、経路サーバ１９５２がノード（転送装置１９５３）分の経路情報を計算する必要があるため、図１９（ａ）のアーキテクチャと比べて計算負荷が増加する。このため、図１９（ｂ）における制御系とデータ系を分離したアーキテクチャでは障害などの網状態変化に対する経路の即時切換が行えないという課題がある。
また、図１９（ｂ）に示すアーキテクチャでは、経路サーバ１９５２に障害が発生した場合、経路の切換自体が行えなくなるという問題がある。
【０００８】
つまり、図１９（ｂ）（非特許文献１）の制御系とデータ系を分離した（つまり、経路サーバ１９５２に経路情報の計算を集中させた）アーキテクチャでは制御系機能とデータ転送系機能を物理的に分離させてネットワーク上に分散配備することで、制御系の機能追加・拡張に対する柔軟性や低コスト性を提供することができる。一方で、経路サーバが全転送装置の経路情報を管理・計算する必要があるため、障害などの網状態変化に対する経路の即時切換が困難となるという問題がある。
【０００９】  このような背景に鑑みて本発明がなされたのであり、本発明は、転送装置間のリンクに障  害が生じたとき、経路サーバによる経路計算を待つことなく、経路の切り換えが可能なネットワークシステムおよび経路制御方法を提供することを課題とする。
【課題を解決するための手段】
【００１０】  本発明は、前記課題を解決するために創案されたものであり、請求項１に記載のネットワークシステムは、経路サーバが、転送装置から前記転送装置間の隣接関係に関する情報である隣接情報を収集し、収集した前記隣接情報を基に、通信データの転送路である経路情報を計算し、前記計算した経路情報を前記転送装置それぞれへ配信し、前記転送装置が、前記配信された経路情報を参照して、受信した通信データの転送を行うネットワークシステムであって、前記経路サーバは、前記経路情報として、前記転送装置間をつなぐ経路の障害発生前に使用するプライマリ経路情報と、前記経路の障害発生時に使用する１以上のバックアップ経路情報と、を計算し、前記各転送装置へ配信し、前記各転送装置は、前記経路サーバから配信されたプライマリ経路情報と、前記バックアップ経路情報と、を記憶部に格納し、前記経路に障害が発生すると、参照する経路情報を、前記プライマリ経路情報から、前記バックアップ経路情報に切り換えて、前記通信データの転送を行い、前記バックアップ経路情報によって前記通信データの転送を行っているときに、前記経路に障害が発生した場合、受信した通信データを破棄することを特徴とする。【００１１】  かかる発明によれば、障害が発生したときのためのバックアップ経路情報を各転送装置へ配信しておくことで、転送装置間のリンクで障害が発生しても経路サーバによる経路情報の再計算を待つことなく、経路を切り換えることができる。 さらに、かかる発明によれば、経路情報の計算を複数の経路サーバに分散させることで、１台あたりの経路サーバの処理負荷を軽減することができる。 また、かかる発明によれば、バックアップ経路情報が使用されている状態から、他のバックアップ経路情報へ切り換えることで生じ得る通信データのループを防止することができる。【００１２】  また、請求項２に記載のネットワークシステムは、請求項１に記載のネットワークシステムであって、前記ネットワークシステムは、複数のエリアに分割されており、どの前記経路サーバが、どの前記エリアに属する転送装置へ前記経路情報の配信を行うかが設定されており、前記経路サーバのそれぞれは、前記エリア内の転送装置に対する前記プライマリ経路情報および前記バックアップ経路情報を計算し、前記計算したプライマリ経路情報およびバックアップ経路情報を、前記経路情報の配信対象としている前記エリア内の転送装置へ配信することを特徴とする。【００１３】  かかる発明によれば、経路情報の計算を複数の経路サーバに分散させることで、１台あたりの経路サーバの処理負荷を軽減することができる。【００１６】  また、請求項６に記載の経路制御方法は、経路サーバが、転送装置から前記転送装置間の隣接関係に関する情報である隣接情報を収集し、収集した前記隣接情報を基に、通信データの転送路である経路情報を計算し、前記計算した経路情報を前記転送装置それぞれへ配信し、前記転送装置が、前記配信された経路情報を参照して、受信した通信データの転送を行うネットワークシステムによる経路制御方法であって、前記経路サーバは、前記経路情報として、前記転送装置間をつなぐ経路の障害発生前に使用するプライマリ経路情報と、前記経路の障害発生時に使用する１以上のバックアップ経路情報と、を計算し、前記各転送装置へ配信し、前記各転送装置は、前記経路サーバから配信されたプライマリ経路情報と、前記バックアップ経路情報と、を記憶部に格納し、前記経路に障害が発生すると、参照する経路情報を、前記プライマリ経路情報から、前記バックアップ経路情報に切り換えて、前記通信データの転送を行い、前記バックアップ経路情報によって前記通信データの転送を行っているときに、前記経路に障害が発生した場合、受信した通信データを破棄することを特徴とする。【００１７】  かかる発明によれば、転送装置間のリンクに障害が発生しても、参照する経路情報をプライマリ経路情報から、バックアップ経路情報へ切り換えることで、経路サーバによる経路情報の再計算を待つことなく、経路を切り換えることができる。また、経路サーバに障害が発生して、障害発生時の経路情報の再計算ができない状態となっても、バックアップ経路情報を参照することができるので、通信データの転送を継続することができる。 さらに、かかる発明によれば、バックアップ経路情報が使用されている状態から、他のバックアップ経路情報へ切り換えることで生じ得る通信データのループを防止することができる。【００１８】  また、請求項７に記載の経路制御方法は、請求項６における経路制御方法であって、前記ネットワークシステムは、複数のエリアに分割されており、どの前記経路サーバが、どの前記エリアに属する転送装置へ前記経路情報の配信を行うかが設定されており、複数の前記経路サーバのそれぞれが、自身が前記経路情報の配信対象としている前記エリア内の転送装置へ配信する前記プライマリ経路情報および前記バックアップ経路情報を計算し、前記計算したプライマリ経路情報およびバックアップ経路情報を、前記経路情報の配信対象としている前記エリア内の転送装置へ配信することを特徴とする。【００１９】
かかる発明によれば、経路情報の計算を複数の経路サーバに分散させることで、１台あたりの経路サーバの処理負荷を軽減することができる。
【００２０】  また、請求項３に記載のネットワークシステムおよび請求項８に記載の経路制御方法のそれぞれは、請求項２に記載のネットワークシステムおよび請求項７における経路制御方法であって、前記複数のエリアは、前記複数の経路サーバのうちの１つであるマスタ経路サーバが経路情報の配信対象としている第１のエリアと、前記マスタ経路サーバとは別の経路サーバであるサブ経路サーバが経路情報の配信対象としている第２のエリアと、を有しており、前記サブ経路サーバは、前記第２のエリアに属する転送装置から隣接情報を収集し、収集した前記隣接情報を基に、前記第２のエリアにおける転送装置の配置に関する情報であるトポロジ情報を計算し、計算した前記トポロジ情報を前記マスタ経路サーバへ送信し、前記マスタ経路サーバは、前記第１のエリアに属する転送装置から隣接情報を収集するとともに、前記サブ経路サーバから、前記第２のエリアのトポロジ情報を収集し、前記収集した第１のエリアの隣接情報および前記第２のエリアのトポロジ情報を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、前記マスタ経路サーバおよび前記サブ経路サーバのそれぞれは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象としている前記エリアに属する前記転送装置の経路情報を計算することを特徴とする。【００２１】
かかる発明によれば、すべてのエリア内の隣接情報の収集が１台の経路サーバに集中することがないため、隣接情報を収集する際の通信負荷を軽減することができる。また、各経路サーバ間で送受信される情報はトポロジ情報であるので、各経路サーバ間の通信負荷も軽減することができる。
【００２２】 請求項４に記載のネットワークシステムおよび請求項９に記載の経路制御方法のそれぞれは、請求項３に記載のネットワークシステムおよび請求項８に記載の経路制御方法であって、前記マスタ経路サーバは、前記第１のエリアにおける転送装置間の障害が生じている転送装置の情報を含む障害情報を受信すると、自身の記憶部に格納されている第２のエリアのトポロジ情報と、前記受信した障害情報と、を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、前記マスタ経路サーバおよび前記サブ経路サーバは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象の前記エリアに属する前記転送装置のプライマリ経路情報を計算することを特徴とする。【００２３】  また、請求項５に記載のネットワークシステムおよび請求項１０の経路制御方法のそれぞれは、請求項３に記載のネットワークシステムおよび請求項８に記載の経路制御方法であって、前記サブ経路サーバは、前記経路情報の配信対象としている前記第２のエリアにおける転送装置間の障害が生じている転送装置間の接続情報を含む障害情報を受信すると、当該障害情報を含む情報をマスタ経路サーバへ送信し、前記マスタ経路サーバは、自身の記憶部に格納されている第２のエリアのトポロジ情報と、前記送信された障害情報と、を基に、前記第１のエリアおよび前記第２のエリアを合わせた全エリアのトポロジ情報を計算し、前記サブ経路サーバへ、前記全エリアのトポロジ情報を配信し、前記マスタ経路サーバおよび前記サブ経路サーバは、前記全エリアのトポロジ情報を基に、前記経路情報の配信対象としている前記エリアに属する前記転送装置のプライマリ経路情報を計算することを特徴とする。【００２４】  請求項４，５，９，１０に記載の発明によれば、各エリアに障害が生じても、請求項３，８の効果を維持しつつ、新たなプライマリ経路を計算し、配信することができる。
【発明の効果】
【００２９】  本発明によれば、転送装置間のリンクに障害が生じたとき、経路サーバによる経路計算を待つことなく、経路の切り換えが可能なネットワークシステムおよび経路制御方法を提供することができる。
【図面の簡単な説明】
【００３０】
【図１】第１実施形態に係るネットワークシステムの例を示す図である。
【図２】第１実施形態に係る経路サーバの構成を示す図である。
【図３】第１実施形態に係る転送装置の構成例を示す図である。
【図４】第１実施形態で使用する各種情報に関する内容を表に示したものである。
【図５】第１実施形態に係るトポロジ情報の例を示す図である。
【図６】第１実施形態に係る経路情報の例を示す図である。
【図７】経路情報配信の概要を示す図である。
【図８】第１実施形態に係る経路切換の概要を示す図である（その１）。
【図９】第１実施形態に係る経路切換の概要を示す図である（その２）。
【図１０】第１実施形態に係る通常時における経路情報の計算処理の流れを示すフローチャートである。
【図１１】第１実施形態に係る障害発生時における経路情報の計算処理の流れを示すフローチャートである。
【図１２】第１実施形態に係る転送装置における経路情報受信・設定処理の流れを示すフローチャートである。
【図１３】第１実施形態に係る転送処理の流れを示すフローチャートである。
【図１４】第２実施形態に係るネットワークシステムの構成例を示す図である。
【図１５】第２実施形態に係るマスタ経路サーバにおける経路情報計算処理（通常時）の流れを示すフローチャートである。
【図１６】第２実施形態に係るサブ経路サーバにおける経路情報計算処理（通常時）の流れを示すフローチャートである。
【図１７】第２実施形態に係るマスタ経路サーバにおける経路情報計算処理（障害発生時）の流れを示すフローチャートである。
【図１８】第２実施形態に係るサブ経路サーバにおける経路情報計算処理（障害発生時）の流れを示すフローチャートである。
【図１９】従来におけるネットワークシステムの構成例を示す図である。
【発明を実施するための形態】
【００３１】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００３２】［第１実施形態］  まず、図１〜図１３を参照して、本発明の第１実施形態について説明する。（ネットワークシステム）  図１は、第１実施形態に係るネットワークシステムの例を示す図である。  ネットワークシステム１０は、ルータなどの転送装置２と、これらの転送装置２に対する経路情報３００を計算し、計算した経路情報３００を各転送装置２へ配信する経路サーバ１とを有している。  なお、経路サーバ１は、基準となる（経路の障害発生前に使用する）経路情報３００（プライマリ経路情報３０１と称する）を計算するプライマリ経路計算部１０２の他に、ネットワークに障害が生じたときに使用する予備の経路情報３００（バックアップ経路情報３０２と称する）を転送装置２毎に計算するバックアップ経路計算部１０３を有し、計算した経路情報３００（以下、経路情報３００と記載する場合は、プライマリ経路情報３０１とバックアップ経路情報３０２との両方を指すものとする）を、対応する転送装置２へ配信する。なお、図１における破線矢印は経路情報３００の配信を示している。
【００３３】
各転送装置２間の接続をリンクと称する。転送装置２間にはトラヒックが発生しており、このトラヒックは通信データであるＩＰ（Internet Protocol）パケット（以下、パケットと称する）の単位で、リンクを介して転送先の転送装置２に到着するものとする。
なお、図１において、バックアップ経路情報３０２が複数（図１では２つ）存在するのは、経路サーバ１は、各々の障害パターンに対応したバックアップ経路情報３０２を、転送装置２毎に計算するため、１つの転送装置２に対応・格納するバックアップ経路情報３０２は複数となることを示している。
【００３４】
（経路サーバの構成）
図２は、第１実施形態に係る経路サーバの構成を示す図である。適宜、図１を参照する。
経路サーバ１は、処理部１００と、記憶部であるトポロジ情報ＤＢ（Data Base）１１０、プライマリ経路情報ＤＢ１２０、バックアップ経路情報ＤＢ１３０とを有している。
処理部１００は、トポロジ情報処理部１０１、プライマリ経路計算部１０２、バックアップ経路計算部１０３、経路設定部１０４、障害・復帰情報受信部１０５、オペレータＩ／Ｆ（Interface）部１０６とを有している。
トポロジ情報処理部１０１は、各転送装置２から送信される隣接情報を収集し、収集した隣接情報を基に、ネットワークシステム１０内の転送装置２の配置情報であるトポロジ情報を計算し、計算したトポロジ情報をトポロジ情報ＤＢ１１０に格納する。
プライマリ経路計算部１０２は、計算したトポロジ情報に基づいて、転送経路の計算を行うことで各転送装置２に対応したプライマリ経路情報３０１を計算すると、このプライマリ経路情報３０１をプライマリ経路情報ＤＢ１２０に格納する
バックアップ経路計算部１０３は、計算したトポロジ情報に基づいて、あらゆる障害パターンに備えた迂回経路であるバックアップ経路の情報であるバックアップ経路情報３０２を、転送装置２毎に計算し、このバックアップ経路情報ＤＢ１３０に格納する。
経路設定部１０４は、計算した経路情報３００（プライマリ経路情報３０１およびバックアップ経路情報３０２）を対応する転送装置２に送信する。
オペレータＩ／Ｆ部１０６は、管理者とのインタフェースであり、サーバメンテナンスやバックアップ経路情報３０２の計算契機を用いるＰＣ（Personal Computer）などの端末に入力する。
【００３５】
トポロジ情報ＤＢ１１０に格納されているトポロジ情報、プライマリ経路情報ＤＢ１２０に格納されているプライマリ経路情報３０１、およびバックアップ経路情報ＤＢ１３０に格納されているバックアップ経路情報３０２については、後記して説明する。
【００３６】
なお、経路サーバ１はＰＣなどで実現されるものであり、処理部１００および処理部１００における各部１０１〜１０６は、図示しないＲＯＭ（Read Only Memory）や、ＨＤＤ（Hard Disk Drive）に格納されたプログラムが、ＲＡＭ（Random Access Memory）に展開され、ＣＰＵ（Central Processing Unit）によって実行されることによって具現化する。
【００３７】
（転送装置）
図３は、第１実施形態に係る転送装置の構成例を示す図である。適宜、図１を参照する。
転送装置２は、動作制御部２００、パケット制御部２１０、プライマリ経路情報ＤＢ（記憶部）２２０およびバックアップ経路情報ＤＢ（記憶部）２３０を有している。
動作制御部２００は、経路情報３００に関する設定を行うものであり、隣接情報送信部２０１、障害・復帰情報送信部２０２、経路情報受信部２０３およびハードウェア管理部２０４を有している。パケット制御部２１０は、パケット４００の転送などに関する処理を行うものであり、状態変化検出部２１１、パケット転送部２１２を有している。
【００３８】
隣接情報送信部２０１は、自身に接続している転送装置２との隣接関係の情報である隣接情報を送信する。
障害・復帰情報送信部２０２は、状態変化検出部２１１が検出した障害（リンクの不通）の情報である障害情報や、復帰の情報である復帰情報を経路サーバ１へ送信する。障害情報や復帰情報は、例えば、自身のノードＩＤ（Identification）と、不通となっている相手先の転送装置２のノードＩＤとの組の情報である。
経路情報受信部２０３は、経路サーバ１から配信される経路情報３００（プライマリ経路情報３０１およびバックアップ経路情報３０２）を受信する。
ハードウェア管理部２０４は、配信された経路情報３００をプライマリ経路情報ＤＢ２２０や、バックアップ経路情報ＤＢ２３０に格納する。また、ハードウェア管理部２０４は、自身のリセットなどを行うメンテナンス機能も有する。
【００３９】
状態変化検出部２１１は、リンクの障害や、リンクの復帰を検出し、障害情報や復帰情報を生成する。
パケット転送部２１２は、経路情報３００を参照することによって、パケット４００を次の転送装置２へ転送する。また、障害が検出された場合には、適切なバックアップ経路情報３０２への切り換えを行う。
【００４０】
なお、プライマリ経路情報ＤＢ２２０に格納されているプライマリ経路情報３０１、およびバックアップ経路情報ＤＢ２３０に格納されているバックアップ経路情報３０２については、後記して説明する。
また、図３に示すようにパケット４００には、ヘッダ部に後記して説明する経路ＩＤが付されている。
【００４１】
転送装置２における動作制御部２００、パケット制御部２１０および各部２０１〜２０４，２１１，２１２は、ＲＯＭなどに格納されたプログラムが、ＣＰＵによって実行されることによって具現化する。
【００４２】
（各種情報）
図４は、第１実施形態で使用する各種情報に関する内容を表に示したものである。
トポロジ情報は、情報要素としてノードとリンクの接続関係を有しており、経路サーバ１のトポロジ情報処理部１０１が各転送装置２から収集し、トポロジ情報ＤＢ１１０に格納される情報である。
プライマリ経路情報３０１は、障害が検出されていない状態のときに使用される経路情報３００であり、情報要素として経路ＩＤ、パケットの宛先アドレス、および転送装置２の出力インタフェース（Ｉ／Ｆ）を有する。ここで、出力インタフェースはネクストホップアドレスとしてもよい。プライマリ経路情報３０１は、トポロジ情報を基に、経路サーバ１のプライマリ経路計算部１０２が各転送装置２毎に計算し、対応する転送装置２に配信する情報である。なお、経路ＩＤは、経路を一意に識別するためのＩＤであり、プライマリ経路情報３０１には「０」が設定される。
【００４３】
バックアップ経路情報３０２は、障害発生後に使用される経路情報３００であり、情報要素として経路ＩＤ、宛先アドレス、および出力インタフェース（Ｉ／Ｆ）を有する。出力インタフェースはネクストホップアドレスでもよい。前記したように、バックアップ経路情報３０２は、トポロジ情報を基に、経路サーバ１のバックアップ経路計算部１０３が、障害の各転送装置２毎に計算し、対応する転送装置２に配信される情報である。バックアップ経路情報３０２の経路ＩＤは「０」以外の値が格納される。
【００４４】
なお、転送装置２のプライマリ経路情報ＤＢ２２０およびバックアップ経路情報ＤＢ２３０は、ハードウェア転送を高速化するためにＣＡＭ（Content‐Addressable Memory）などとしてもよい。
【００４５】
（トポロジ情報）
図５は、第１実施形態に係るトポロジ情報の例を示す図である。
トポロジ情報は、始点ノードＩＤ、終点ノードＩＤ、接続状態、リンクコストなどを有する。リンクコストは、使用されるルーティングプロトコルによって規定される値である。なお、ノードとは転送装置２のことであり、以降、転送装置２をノードと適宜称することがある。
言い換えれば、トポロジ情報はすべての転送装置２における隣接関係を記述した情報であり、接続関係にない転送装置２間では、接続の欄に「なし」が登録されることとなる。
【００４６】
（経路情報）
図６は、第１実施形態に係る経路情報の例を示す図である。ここで示す経路情報３００の構成はプライマリ経路情報３０１およびバックアップ経路情報３０２に共通のものである。
経路情報３００は、経路情報３００を区別する経路ＩＤと、宛先アドレスと、出力インタフェース（Ｉ／Ｆ）とを有する。前記したように、出力インタフェース（Ｉ／Ｆ）は、ネクストホップアドレスでもよい。
【００４７】
（概要）
ここで、図７〜図９を参照して、第１実施形態の概要を説明する。
図７は、経路情報配信の概要を示す図である。図７（ａ）は非特許文献１に記載の技術（比較例）による経路情報３００配信の概要図であり、図７（ｂ）は本実施形態に係る経路情報３００配信の概要図である。
図７（ａ）に示すように、非特許文献１に記載の技術では、１つの転送装置２に対し、１つの経路情報３００が配信されるのに対し、図７（ｂ）に示す本実施形態では、１つの転送装置２に対し、プライマリ経路情報３０１、バックアップ経路情報３０２といった複数の経路情報３００が配信される。そして、各経路情報３００（経路）は経路ＩＤで区別される。言い換えれば、各経路情報３００は経路ＩＤによってカプセル化されている。
【００４８】
図８および図９は、第１実施形態に係る経路切換の概要を示す図である。
図８では、転送装置２ａから転送装置２ｃに対しパケット４００（図３）を送信する場合を示す。なお、図３に示すようにパケット４００には使用する経路ＩＤが記述されている。
図８（ａ）に示すように、プライマリ経路（経路ＩＤ「０」）では、転送装置２ａ→転送装置２ｂ→転送装置２ｃの順にパケット４００が送信される（矢印８０１）が、転送装置２ｂ，２ｃ間のリンクの障害が検出されると、転送装置２ａから送信されたパケット４００は、転送装置２ｂでとまる（矢印８０２）。転送装置２ｂは、バックアップ経路情報３０２から適切なものを選択する（経路ＩＤ「１」が選択されたとする）と、パケット４００内の経路ＩＤを「０」から「１」に書き換え、選択されたバックアップ経路情報３０２に従う新たな転送装置２へ、書き換えたパケット４００を送信する。図８（ａ）の場合、転送装置２ｂは、パケット４００を転送装置２ａへ返す（矢印８０３）。
【００４９】
経路ＩＤを書き換えられたパケット４００を受信した転送装置２ａは、パケット４００に記述されている経路ＩＤをキーとして、バックアップ経路情報３０２（経路ＩＤ「１」）をバックアップ経路情報ＤＢ２３０から取得すると、そのバックアップ経路情報３０２に従ってパケット４００を送信する（転送装置２ａ→転送装置２ｄ→転送装置２ｅ→転送装置２ｆ→転送装置２ｃ：矢印８０４）。
【００５０】
転送装置２ｂは、リンクの遮断を検出するとともに、経路サーバ１へ転送装置２ｂ，２ｃ間のリンクに障害が発生している旨の障害情報を送る。障害情報は、転送装置２における定期的な生存確認において、確認相手から生存情報が送られてこなかった場合に、転送装置２が経路サーバ１へ送る情報であり、自転送装置２のノードＩＤと、確認先のノードＩＤとが組となった情報である。このように障害情報には、隣接情報と同様に自身の転送装置２のノードＩＤと、リンク先の転送装置２のノードＩＤが記述されているので、経路サーバ１は、この障害情報を基に、プライマリ経路情報３０１の再計算を行う。そして、経路サーバ１は、再計算したプライマリ経路情報３０１（転送装置２ａ→転送装置２ｄ→転送装置２ｅ→転送装置２ｆ→転送装置２ｃ）を各転送装置２へ配信する。各転送装置２は、自身のプライマリ経路情報ＤＢ２２０に格納しているプライマリ経路情報３０１を新たに受信したプライマリ経路情報３０１に更新し、更新したプライマリ経路情報３０１に従ってパケット４００の転送を行う（破線矢印８０５）。
【００５１】
図８（ｂ）のように、再計算されたプライマリ経路情報３０１に従って各転送装置２がパケット４００の転送を行っているときに（矢印８０５）、転送装置２ｂ，２ｃ間のリンクの復帰が検出されると、転送装置２ｂは転送装置２ｂ，２ｃ間のリンクが復帰した旨の復帰情報を経路サーバ１に送信する。復帰情報は、転送装置２における定期的な生存確認において、生存確認できていなかった確認相手から生存情報が送られてくるようになった場合に、転送装置２が経路サーバ１へ送る情報であり、自転送装置２のノードＩＤと、確認先のノードＩＤとが組となった情報である。このように復帰情報には、隣接情報と同様に自身のノードＩＤと、リンク先のノードＩＤとを含んでいるので、復帰情報を受信した経路サーバ１は、復帰情報を基に、プライマリ経路情報３０１の再々計算を行う。そして、経路サーバ１は、再々計算したプライマリ経路情報３０１（転送装置２ａ→転送装置２ｂ→転送装置２ｃ）を各転送装置２へ配信し、各転送装置２は新たに受信したプライマリ経路情報３０１に従ってパケット４００の転送を行う（破線矢印８０６）。なお、転送装置２は復帰を検知しても、バックアップ経路情報３０２へ切り換えることは行わない。これは、復帰時の経路切り換えは緊急を要するものではないためである。
【００５２】
図９は、第１実施形態に係る経路切換の概要を示す図である。
図９（ａ）は、プライマリ経路情報３０１（経路ＩＤ「０」）の例を示す図であり、転送装置２Ａ→転送装置２Ｂ→転送装置２Ｃの順にパケット４００を送信する経路が記述されていることを示す。
図９（ｂ）は、バックアップ経路情報３０２（経路ＩＤ「１」）の例を示す図であり、このバックアップ経路には、転送装置２Ａ，２Ｂ間のリンクに障害が発生した際の経路として、転送装置２Ａ→転送装置２Ｄ→転送装置２Ｂ→転送装置２Ｃの経路が記述されている。
図９（ｃ）は、別のバックアップ経路情報３０２（経路ＩＤ「２」）の例を示す図であり、このバックアップ経路には、転送装置２Ｂ，２Ｃ間のリンクが遮断した際の経路として、転送装置２Ａ→転送装置２Ｄ→転送装置２Ｅ→転送装置２Ｃの経路が記述されている。なお、図９（ｃ）において、パケット４００が転送装置２Ｂに送信された後、転送装置２Ａに戻っているが、これは図８でも記載したように、転送装置２Ｂまで送られたパケット４００は、転送装置２Ｂによって経路ＩＤを「０」から「２」に書き換えられ、書き換えられたバックアップ経路情報３０２に従う新たな転送装置２へパケット４００が送信された結果、転送装置２Ａに戻されることを示している。
【００５３】
＜処理＞
次に、図２および図３を参照しつつ、図１０〜図１３を参照して本実施形態に係る処理を説明する。
（経路情報計算処理（通常時））
図１０は、第１実施形態に係る通常時における経路情報の計算処理の流れを示すフローチャートである。ここで通常時の処理とは、ネットワーク始動時、および転送装置２の除去・追加などネットワーク状態が変化したときに、管理者がオペレータＩ／Ｆ部１０６を介して経路サーバ１に情報を入力することによって、経路サーバ１が行う処理のことである。
まず、トポロジ情報処理部１０１が、各転送装置２の隣接情報送信部２０１から隣接情報を収集する（Ｓ１０１）。
そして、トポロジ情報処理部１０１が、収集した隣接情報を基に、トポロジ情報を計算する（Ｓ１０２）。
次に、プライマリ経路計算部１０２が、計算したトポロジ情報を基に、各転送装置２に対応したプライマリ経路情報３０１を転送装置２毎に計算する（Ｓ１０３）。
さらに、バックアップ経路計算部１０３が、取得したトポロジ情報を基に、バックアップ経路情報３０２を転送装置２毎に計算する（Ｓ１０４）。前記したように、バックアップ経路情報３０２は、どのリンクが１ヶ所切断しても、すべての転送装置２へデータが送れるよう計算される。従って、１つの転送装置２に対して生成されるバックアップ経路情報３０２は複数となる。
そして、経路設定部１０４が、計算した経路情報３００（プライマリ経路情報３０１およびバックアップ経路情報３０２）を、それぞれ該当する転送装置２へ配信する（Ｓ１０５）。
【００５４】
（経路情報計算処理（障害発生時））
図１１は、第１実施形態に係る障害発生時における経路情報の計算処理の流れを示すフローチャートである。この処理は、経路サーバ１が行う処理である。
まず、障害・復帰情報受信部１０５が、転送装置２から障害情報を受信したか否かを判定する（Ｓ２０１）。
ステップＳ２０１の結果、障害情報を受信していない場合（Ｓ２０１→Ｎｏ）、障害・復帰情報受信部１０５は、ステップＳ２０５へ処理を進める。
【００５５】
ステップＳ２０１の結果、障害情報を受信した場合（Ｓ２０１→Ｙｅｓ）、前記したように障害情報には、障害が生じているリンクの隣接情報が含まれているので、トポロジ情報処理部１０１が、受信した障害情報を基に、トポロジ情報を更新する（Ｓ２０２）。具体的には、障害情報に含まれている２つのノードＩＤの接続情報を「あり」から「なし」に変更する。
そして、プライマリ経路計算部１０２が、更新したトポロジ情報に従って新たなプライマリ経路情報３０１を転送装置２毎に再計算すると（Ｓ２０３）、経路設定部１０４が新たなプライマリ経路情報３０１を各転送装置２へ配信する（Ｓ２０４）。
【００５６】
次に、障害・復帰情報受信部１０５が、転送装置２から復帰情報を受信したか否かを判定する（Ｓ２０５）。
ステップＳ２０５の結果、復帰情報を受信していない場合（Ｓ２０５→Ｎｏ）、障害・復帰情報受信部１０５は、ステップＳ２０１へ処理を戻す。
【００５７】
ステップＳ２０５の結果、障害情報を受信した場合（Ｓ２０５→Ｙｅｓ）、復帰情報には、復帰したリンクの隣接情報が含まれているので、トポロジ情報処理部１０１が、受信した復帰情報を基に、トポロジ情報を更新する（Ｓ２０６）。具体的には、復帰情報に含まれている２つのノードＩＤの接続情報を「なし」から「あり」に変更する。
そして、プライマリ経路計算部１０２が、更新したトポロジ情報に従って新たなプライマリ経路情報３０１を転送装置２毎に再々計算すると（Ｓ２０７）、経路設定部１０４が新たなプライマリ経路情報３０１を各転送装置２へ配信する（Ｓ２０８）。
【００５８】
（経路情報受信・設定）
図１２は、第１実施形態に係る転送装置における経路情報受信・設定処理の流れを示すフローチャートである。
まず、経路情報受信部２０３が、図１０のステップＳ１０５で配信された経路情報３００（プライマリ経路情報３０１およびバックアップ経路情報３０２）を受信し、ハードウェア管理部２０４が受信した経路情報３００をプライマリ経路情報ＤＢ２２０およびバックアップ経路情報ＤＢ２３０に格納することで経路情報３００の設定を行う（Ｓ３０１）。
転送装置２の状態変化検出部２１１は、隣接する転送装置２に生存確認情報を定期的に送信し、リンクの状態を監視している。つまり、状態変化検出部２１１が、隣接する転送装置２からの生存確認応答を受信しなかったことでリンクの障害を検知したか否かを判定している（Ｓ３０２）。
ステップＳ３０２の結果、障害を検知しなかった場合（Ｓ３０２→Ｎｏ）、状態変化検出部２１１はステップＳ３０２へ処理を戻す。
【００５９】
ステップＳ３０２の結果、障害を検知した場合（Ｓ３０２→Ｙｅｓ）、障害・復帰情報送信部２０２は、自転送装置２のノードＩＤと、生存確認応答を得ることがてきなかった相手先の転送装置２のノードＩＤとを対の情報とした障害情報を経路サーバ１へ送信する（Ｓ３０３）。
そして、経路情報受信部２０３は、経路サーバ１から図１１のステップＳ２０４で配信されたプライマリ経路情報３０１を受信したか否かを監視する（Ｓ３０４）。
ステップＳ３０４の結果、プライマリ経路情報３０１を受信していない場合（Ｓ３０４→Ｎｏ）、経路情報受信部２０３はステップＳ３０４へ処理を戻す。なお、経路サーバ１からのプライマリ経路情報３０１を受信していないうちに、パケット４００を受信した場合は、後記する図１３のステップＳ４０４で「Ｎｏ」の処理が行われ、経路はバックアップ経路情報３０２による経路へ切り換えられることとなる。
【００６０】
ステップＳ３０４の結果、プライマリ経路情報３０１を受信した場合（Ｓ３０４→Ｙｅｓ）、ハードウェア管理部２０４が、プライマリ経路情報ＤＢ２０に保持しているプライマリ経路情報３０１を、受信したプライマリ経路情報３０１に更新する（Ｓ３０５）。以降、ステップＳ３０５で更新されたプライマリ経路情報３０１に従ってパケット４００の転送が行われる。つまり、バックアップ経路情報３０２は、プライマリ経路情報３０１が再計算されている間のための緊急用の経路情報３００である。
【００６１】
そして、状態変化検出部２１１が、隣接する転送装置２からの生存確認応答を受信したことでリンクの復帰を検知したか否かを判定する（Ｓ３０６）。
ステップＳ３０６の結果、復帰を検知しなかった場合（Ｓ３０６→Ｎｏ）、状態変化検出部２１１はステップＳ３０６へ処理を戻す。
【００６２】
ステップＳ３０６の結果、復帰を検知した場合（Ｓ３０６→Ｙｅｓ）、障害・復帰情報送信部２０２は、自転送装置２のノードＩＤと、生存確認応答を得ることができた相手先の転送装置２のノードＩＤとを対の情報とした復帰情報を経路サーバ１へ送信する（Ｓ３０７）。
そして、経路情報受信部２０３は、経路サーバ１から図１１のステップＳ２０８で配信されたプライマリ経路情報３０１を受信したか否かを監視する（Ｓ３０８）。
ステップＳ３０８の結果、プライマリ経路情報３０１を受信していない場合（Ｓ３０８→Ｎｏ）、経路情報受信部２０３はステップＳ３０８へ処理を戻す。
【００６３】
ステップＳ３０８の結果、プライマリ経路情報３０１を受信した場合（Ｓ３０８→Ｙｅｓ）、ハードウェア管理部２０４が、プライマリ経路情報ＤＢ２２０に保持しているプライマリ経路情報３０１を、受信したプライマリ経路情報３０１に更新する（Ｓ３０９）。
【００６４】
（転送処理）
図１３は、第１実施形態に係る転送処理の流れを示すフローチャートである。この処理は、各転送装置２が行う処理である。
パケット転送部２１２は、パケット４００を受信したか否かを判定する（Ｓ４０１）。
ステップＳ４０１の結果、パケット４００を受信していない場合（Ｓ４０１→Ｎｏ）、パケット転送部２１２はステップＳ４０１へ処理を戻す。
ステップＳ４０１の結果、パケット４００を受信すると（Ｓ４０１→Ｙｅｓ）、パケット転送部２１２がパケット４００のヘッダに記述されている経路ＩＤを取得し（Ｓ４０２）、取得した経路ＩＤに対応した経路情報３００（プライマリ経路情報３０１もしくはバックアップ経路情報３０２）をプライマリ経路情報ＤＢ２２０あるいはバックアップ経路情報ＤＢ２３０から取得する（Ｓ４０３）。
【００６５】
次に、パケット転送部２１２は、取得した経路情報３００において、パケット４００の宛先アドレスへ転送するための出力インタフェースに障害が発生しているか否かを判定することにより、パケット４００が転送可か否かを判定する（Ｓ４０４）。
ステップＳ４０４の結果、パケット４００が転送可であれば（Ｓ４０４→Ｙｅｓ）、パケット転送部２１２は、取得した経路情報３００に記述されている出力インタフェースを介して、パケット４００を転送し（Ｓ４０５）、ステップＳ４０１へ処理を戻す。
ステップＳ４０４の結果、パケット４００の転送が不可であれば（Ｓ４０４→Ｎｏ）、パケット転送部２１２は、パケット４００のヘッダに記述されている経路ＩＤが「０」であるか否か（つまり、現在使用している経路情報３００がプライマリ経路情報３０１であるか否か）を判定する（Ｓ４０６）。
ステップＳ４０６の結果、経路ＩＤが「０」ではない場合（ＳＳ４０６→Ｎｏ）、つまり、現在使用している経路情報３００がすでにバックアップ経路情報３０２である場合、パケット転送部２１２は、そのパケット４００を破棄し（Ｓ４０７）、パケット転送部２１２はステップＳ４０１へ処理を戻す。これは、すでにバックアップ経路情報３０２を使用している状態で、さらに他のバックアップ経路情報３０２へ経路情報３００を変更した際に生じ得る転送ループを防止するためである。
【００６６】
ステップＳ４０６の結果、経路ＩＤが「０」である場合（Ｓ４０６→Ｙｅｓ）、パケット転送部２１２は、適切なバックアップ経路情報３０２を選択する（Ｓ４０８）。このとき、バックアップ経路情報３０２には、どのリンクに障害が発生したときには、どのバックアップ経路情報３０２を使用するといった情報が記述されているので、パケット転送部２１２は、その情報を基にバックアップ経路情報３０２を選択する。
そして、パケット転送部２１２は、パケット４００のヘッダに記述されている経路ＩＤをステップＳ４０８で選択したバックアップ経路情報３０２の経路ＩＤに書き換え（Ｓ４０９）、そのパケット４００を、経路ＩＤに従う新たな転送先となる転送装置２へ送信する（Ｓ４１０）。返信されたパケット４００を受信した転送装置２（パケット送信元）は、ステップＳ４０１以下の処理に従って、該パケット４００を転送する。
【００６７】
また、復帰前のプライマリ経路情報３０１（再計算したプライマリ経路情報３０１）に従ってパケット４００の転送を行っているときに、さらに障害が発生した場合、経路サーバ１が警告表示を行って管理者に通知し、管理者の指示によって図１５の経路情報３００の計算処理が行われてもよい。
そして、経路情報３００を配信する方法は任意のプロトコルを用いてよく、例えばＦｏｒＣＥＳなどを使用してもよい（例えば、A. Doria, R. Haas, J. H. Salim, H. Khosravi, and W. M. Wang, “ForCES Protocol Specification,”IETF Internet draft  draft-ietf-forces-protocol-22, Mar. 2009.を参照）
【００６８】
（第１実施形態のまとめ）
各転送装置２にリンクの障害発生時に使用するバックアップ経路情報３０２を設定することにより、リンクの障害発生時に経路サーバ１による経路情報３００の再計算を待つことなく、経路を切り換えることができる。
また、経路サーバ１に障害が発生して、経路情報３００の再計算が不可能となっても、バックアップ経路情報３０２によってパケット４００の転送を継続することができる。
さらに、バックアップ経路情報３０２に従って、パケット４００の転送を行っているときにリンクの障害が発生した場合、パケット４００を破棄（通信を停止）することで、バックアップ経路情報３０２が使用されている状態から、他のバックアップ経路情報３０２へ切り換えることで生じ得るルーティングのループを防止することができる。
また、障害発生時や、復帰時に再計算される経路情報３００は、プライマリ経路情報３０１のみであるので、経路サーバ１における経路情報３００の計算負荷や、転送装置２への経路情報３００の配信時における通信負荷を無駄に増加させることがない。
【００６９】
［第２実施形態］
次に、図１４〜図１８を参照して本発明の第２実施形態を説明する。
第２実施形態では、ネットワークシステム１０ａを複数のエリアに分割し、各エリアを経路情報３００（図１）の配信対象とする経路サーバ１を複数用意することで、第1実施形態の効果を維持しつつ、経路情報３００の計算処理負荷を軽減する。
【００７０】
（システム構成）
図１４は、第２実施形態に係るネットワークシステムの構成例を示す図である。
ここでは、ネットワークシステム１０ａをバックボーンエリア（第１のエリア）１４１１とサブエリア（第２のエリア）１４１２とに分割し、さらにサブエリア１４１２をサブエリア１４１２ａおよびサブエリア１４１２ｂに分割している。サブエリア１４１２は、いくつ設定してもよいが、マスタ経路サーバ１４１１はネットワークシステム１０ａに１つだけ設定される。それぞれのエリアにおける転送装置２を配信対象としている経路サーバ１（マスタ経路サーバ１４０１、サブ経路サーバ１４０２ａ，１４０２ｂ）を設置する。図１４において、マスタ経路サーバ１４０１はバックボーンエリア１４１１を配信対象とし、サブ経路サーバ１４０２ａはサブエリア１４１２ａを配信対象とし、サブ経路サーバ１４０２ｂはサブエリア１４１２ｂを配信対象としている。
【００７１】
サブ経路サーバ１４０２ａはサブエリア１４１２ａにおける転送装置２の隣接情報（以下、サブエリア１４１２ａの隣接情報と称する。サブエリア１４１２ｂおよびバックボーンエリア１４１１に対しても同様）を収集し、この隣接情報を基に計算したトポロジ情報をマスタ経路サーバ１４０１へ送信する。同様に、サブ経路サーバ１４０２ｂはサブエリアｂの隣接情報を収集し、この隣接情報を基に計算したトポロジ情報をマスタ経路サーバ１４０１へ送信する。
なお、サブ経路サーバ１４０２からマスタ経路サーバ１４０１へ送信される情報は、トポロジ情報に限らず、すでに一度トポロジ情報を受信している場合は、差分情報である各転送装置２から取得した隣接情報としてもよい。
サブ経路サーバ１４０２ａ，１４０２ｂよりサブエリア１４１２ａ，１４１２ｂのトポロジ情報を収集したマスタ経路サーバ１４０１は、自身が収集したバックボーンエリア１４１１の隣接情報と、サブエリア１４１２ａ，１４１２ｂのトポロジ情報を基に、すべてのエリア（バックボーンエリア１４１１、サブエリア１４１２ａ，１４１２ｂ）のトポロジ情報を計算し、計算したすべてのエリアのトポロジ情報をサブ経路サーバ１４０２ａ，１４０２ｂに送信する。
【００７２】
すべてのエリアのトポロジ情報を有するようになった各経路サーバ１は、自身が配信対象とするエリア毎に経路情報３００（プライマリ経路情報３０１およびバックアップ経路情報３０２）を計算する。
つまり、マスタ経路サーバ１４０１は、転送装置２ｏ，２ｐ，２ｑに対応した経路情報３００を計算し、サブ経路サーバ１４０２ａは、転送装置２ｒ，２ｓ，２ｔに対応した経路情報３００を計算し、サブ経路サーバ１４０２ｂは、転送装置２ｕ，２ｖ，２ｗに対応した経路情報３００を計算し、それぞれの転送装置２へ配信する。
【００７３】
なお、マスタ経路サーバ１４０１およびサブ経路サーバ１４０２の構成は図２に示す経路サーバ１の構成と同様であり、転送装置２の構成は図３に示す転送装置２の構成と同様であるため、ここでは説明を省略する。
【００７４】
以下、図２、図３および図１４を参照しつつ、図１５から図１８を参照して第２実施形態における各経路サーバ１の動作を説明する。なお、転送装置２の動作は第１実施形態と同様であるため説明および図示を省略する。
（経路情報計算処理（通常時：マスタ経路サーバ））
図１５は、第２実施形態に係るマスタ経路サーバにおける経路情報計算処理（通常時）の流れを示すフローチャートである。なお、図１５および図１６における通常時の処理とは、ネットワーク始動時、および転送装置２の除去・追加などネットワーク状態が変化したときに、管理者が経路サーバ１に情報を入力することによって、マスタ経路サーバ１４０１および各サブ経路サーバ１４０２が行う処理のことである。
まず、マスタ経路サーバ１４０１のトポロジ情報処理部１０１が、バックバーンエリア内の転送装置２の隣接情報送信部２０１から隣接情報を収集する（Ｓ５０１）。
次に、マスタ経路サーバ１４０１のトポロジ情報処理部１０１が、各サブ経路サーバ１４０２から各サブエリア１４０２のトポロジ情報を収集する（Ｓ５０２）。
そして、トポロジ情報処理部１０１が、ステップＳ５０１で収集したバックボーンエリア１４１１の隣接情報およびステップＳ５０２で収集した各サブエリア１４１２のトポロジ情報から、全エリアのトポロジ情報を計算する（Ｓ５０３）。具体的には、トポロジ情報処理部１０１は、バックボーンエリア１４１１の隣接情報を基に、バックボーンエリア１４１１のトポロジ情報を計算すると、バックボーンエリア１４１１のトポロジ情報と、各サブエリア１４１２のトポロジ情報とを併せる。なお、各エリアの境界に存在する転送装置２（図１４における転送装置２ｐ−転送装置２ｒなど）間の接続情報は、各エリアのトポロジ情報内に記述されている。
【００７５】
そして、トポロジ情報処理部１０１は、各サブ経路サーバ１４０２へ計算した全エリアのトポロジ情報を配信する（Ｓ５０４）。このとき、サブ経路サーバ１４０２へ送信するトポロジ情報は、バックボーンエリア１４１１および各サブエリア１４１２を含むすべてのトポロジ情報でもよいし、必要なトポロジ情報だけ配信してもよい。例えば、図１４のサブ経路サーバ１４０２ａにサブエリア１４１２ａのトポロジ情報を配信しても意味がないので、サブ経路サーバ１４０２ａへはバックボーンエリア１４１１およびサブエリア１４１２ｂのトポロジ情報のみを送信するようにしてもよい。
【００７６】
次に、マスタ経路サーバ１４０１のプライマリ経路計算部１０２およびバックアップ経路計算部１０３が、計算した全エリアのトポロジ情報を基に、バックボーンエリア１４１１内の転送装置２（図１４の転送装置２ｏ〜２ｑ）に対するプライマリ経路情報３０１およびバックアップ経路情報３０２（経路情報３００）を計算する（Ｓ５０５）。
次に、マスタ経路サーバ１４０１の経路設定部１０４が、バックボーンエリア１４１１内の転送装置２へ計算したプライマリ経路情報３０１を配信する（Ｓ５０６）。
【００７７】
（経路情報計算処理（サブ経路サーバ））
図１６は、第２実施形態に係るサブ経路サーバにおける経路情報計算処理（通常時）の流れを示すフローチャートである。
まず、サブ経路サーバ１４０２のトポロジ情報処理部１０１が、自身が経路情報３００の配信対象としているサブエリア１４１２に属する転送装置２の隣接情報送信部２０１からサブエリア１４１２の隣接情報を収集する（Ｓ６０１）。
次に、トポロジ情報処理部１０１は、収集した隣接情報から、自身が経路情報３００の配信対象としているサブエリア１４１２におけるトポロジ情報を計算する（Ｓ６０２）。
続いて、トポロジ情報処理部１０１が、マスタ経路サーバ１４０１へ計算したサブエリア１４１２のトポロジ情報を送信する（Ｓ６０３）。
【００７８】
そして、トポロジ情報処理部１０１が、図１５のステップＳ５０４でマスタ経路サーバ１４０１から配信された全エリアのトポロジ情報を受信する（Ｓ６０４）。前記したように、このとき受信するトポロジ情報は、バックボーンエリア１４１１および各サブエリア１４１２すべてのトポロジ情報でもよいし、必要なトポロジ情報だけを受信してもよい。
【００７９】
そして、サブ経路サーバ１４０２のプライマリ経路計算部１０２およびバックアップ経路計算部１０３が、受信した全エリアのトポロジ情報を基に、サブエリア１４１２内の転送装置２（図１４の転送装置２ｒ〜２ｔ、あるいは転送装置２ｕ〜２ｗ）に対するプライマリ経路情報３０１およびバックアップ経路情報３０２（経路情報３００）を計算する（Ｓ６０５）。
次に、サブ経路サーバ１４０２の経路設定部１０４が、自身が経路情報３００の配信対象としているサブエリア１４１２内の転送装置２へ計算したプライマリ経路情報３０１を配信する（Ｓ６０６）。
【００８０】
（経路情報計算処理（障害発生時：マスタ経路サーバ））
図１７は、第２実施形態に係るマスタ経路サーバにおける経路情報計算処理（障害発生時）の流れを示すフローチャートである。
まず、マスタ経路サーバ１４０１の障害・復帰情報受信部１０５またはトポロジ情報処理部１０１が、自身に対応するバックボーンエリア１４１１におけるいずれかの転送装置２から障害情報を受信したか、あるいはサブ経路サーバ１４０２からトポロジ情報を受信したか否かを判定する（Ｓ７０１）。
ステップＳ７０１の結果、障害情報およびトポロジ情報を受信していない場合（Ｓ７０１→Ｎｏ）、障害・復帰情報受信部１０５およびトポロジ情報処理部１０１は、ステップＳ７０６へ処理を進める。
ステップＳ７０１の結果、障害情報あるいはトポロジ情報を受信した場合（Ｓ７０１→Ｙｅｓ）、トポロジ情報処理部１０１が、受信した障害情報あるいはサブ経路サーバ１４０２から受信したトポロジ情報を基に全エリアのトポロジ情報を計算する（Ｓ７０２）。
そして、トポロジ情報処理部１０１は、各サブ経路サーバ１４０２へ計算した全エリアのトポロジ情報を配信する（Ｓ７０３）。
そして、プライマリ経路計算部１０２が、全エリアのトポロジ情報を基に、バックボーンエリア１４１１内のプライマリ経路情報３０１を再計算する（Ｓ７０４）。
続いて、経路設定部１０４が、バックボーンエリア１４１１内の転送装置２へ再計算したプライマリ経路情報３０１を配信する（Ｓ７０５）。
【００８１】
次に、マスタ経路サーバ１４０１の障害・復帰情報受信部１０５が、ステップＳ７０１において、バックボーンエリア１４１１から障害情報を受信した場合は復帰情報を受信した否かを判定し、ステップＳ７０１においてサブ経路サーバ１４０２からトポロジ情報を受信した場合は、マスタ経路サーバ１４０１のトポロジ情報処理部１０１がサブ経路サーバ１４０２から再度送られたトポロジ情報を受信したか否かを判定する（Ｓ７０６）。
ステップＳ７０６の結果、復帰情報およびトポロジ情報を受信していない場合（Ｓ７０６→Ｎｏ）、障害・復帰情報受信部１０５は、ステップＳ７０１へ処理を戻す。
【００８２】
ステップＳ７０６の結果、復帰情報あるいはトポロジ情報を受信している場合（Ｓ７０６→Ｙｅｓ）、トポロジ情報処理部１０１が、受信した障害情報あるいはトポロジ情報を基に全エリアのトポロジ情報を計算する（Ｓ７０７）。全エリアのトポロジ情報の計算方法は、図１５のステップＳ５０３と同様である。
そして、トポロジ情報処理部１０１は、各サブ経路サーバ１４０２へ計算した全エリアのトポロジ情報を配信する（Ｓ７０８）。
そして、プライマリ経路計算部１０２が、全エリアのトポロジ情報を基に、バックボーンエリア１４１１内のプライマリ経路情報３０１を再々計算する（Ｓ７０９）。
続いて、経路設定部１０４が、バックボーンエリア１４１１内の転送装置２へ再々計算したプライマリ経路情報３０１を配信する（Ｓ７１０）。
【００８３】
（経路情報計算処理（障害発生時：サブ経路サーバ））
図１８は、第２実施形態に係るサブ経路サーバにおける経路情報計算処理（障害発生時）の流れを示すフローチャートである。
まず、サブ経路サーバ１４０２の障害・復帰情報受信部１０５が、自身に対応するサブエリア１４１２の転送装置２のいずれかから障害情報を受信した否かを判定する（Ｓ８０１）。
ステップＳ８０１の結果、障害情報を受信していない場合（Ｓ８０１→Ｎｏ）、処理部１００はステップＳ８０４へ処理を進める。
ステップＳ８０１の結果、障害情報を受信している場合（Ｓ８０１→Ｙｅｓ）、トポロジ情報処理部１０１は、受信した障害情報を基にトポロジ情報を更新し（Ｓ８０２）、マスタ経路サーバ１４０１へ更新したトポロジ情報を送信する（Ｓ８０３）。障害情報を基にトポロジ情報を更新する処理は第１実施形態で行われた処理と同様である。
【００８４】
続いて、障害・復帰情報受信部１０５が、自身に対応するサブエリア１４１２の転送装置２にいずれかから復帰情報を受信した否かを判定する（Ｓ８０４）。
ステップＳ８０４の結果、復帰情報を受信していない場合（Ｓ８０４→Ｎｏ）、処理部１００はステップＳ８０７へ処理を進める。
ステップＳ８０４の結果、復帰情報を受信している場合（Ｓ８０４→Ｙｅｓ）、トポロジ情報処理部１０１は、受信した障害情報を基に、トポロジ情報を更新し（Ｓ８０５）、マスタ経路サーバ１４０１へ更新したトポロジ情報を送信する（Ｓ８０６）。復帰情報を基にトポロジ情報を更新する処理は第１実施形態で行われた処理と同様である。
【００８５】
次に、トポロジ情報処理部１０１が、マスタ経路サーバ１４０１から図１７のステップＳ７０３またはステップＳ７０８で配信された全エリアのトポロジ情報を受信したか否かを判定する（Ｓ８０７）。
ステップＳ８０７の結果、全エリアのトポロジ情報を受信していない場合（Ｓ８０７→Ｎｏ）、処理部１００はステップＳ８０１へ処理を戻す。
ステップＳ８０７の結果、全エリアのトポロジ情報を受信している場合（Ｓ８０７→Ｙｅｓ）、プライマリ経路計算部１０２が、受信した全エリアのトポロジ情報を基に、経路情報３００の配信対象としているサブエリア１４１２内のプライマリ経路情報３０１を計算する（Ｓ８０８）。
そして、経路設定部１０４が、経路情報３００の配信対象としているサブエリア１４１２内の転送装置２へ計算したプライマリ経路情報３０１を配信し（Ｓ８０９）、処理部１００はステップＳ８０１へ処理を戻す。
【００８６】
なお、第２実施形態において、転送装置２の処理は第１実施形態と同様であるため、図示および説明を省略する。
【００８７】
第２実施形態によれば、経路サーバ１は、自身が対応しているエリアの転送装置２に対して経路情報３００を計算すればよいので、経路情報３００の計算処理負荷を軽減することができる。
さらに、第１実施形態では、ネットワークシステム１０ａ内のすべての隣接情報を１つの経路サーバ１が収集する必要があったが、第２実施形態では、自身が対応しているエリア内の隣接情報を収集すればよいので、通信の効率を向上させることができる。
さらに、各経路サーバ１間の通信は、トポロジ情報のみであるため、各経路サーバ１間の通信負荷は軽微なものとすることができる。
【００８８】
なお、第２実施形態において、サブエリア１４１２のリンクに障害が発生した場合、障害情報を受信したサブ経路サーバ１４０２が、障害が発生したサブエリア１４１２のトポロジ情報を計算して、そのトポロジ情報をマスタ経路サーバ１４０１へ送信しているが、サブ経路サーバ１４０２は受信した障害情報のみをマスタ経路サーバ１４０１へ送信してもよい。このとき、マスタ経路サーバ１４０１は、受信した障害情報を基に全エリアのトポロジ情報を更新する。このようにすると、サブ経路サーバ１４０２は障害情報のみをマスタ経路サーバ１４０１へ転送すればよく、またマスタ経路サーバ１４０１も障害情報に記述されているリンクの接続を「あり」から「なし」に更新すればよいので、マスタ経路サーバ１４０１およびサブ経路サーバ１４０２の計算負荷が、図１７および図１８に記載の方法よりさらに軽減され、また通信負荷も図１７および図１８に記載の方法よりさらに軽減される。
なお、復帰の際の処理も同様に行うことができる。
【符号の説明】
【００８９】  １      経路サーバ  ２，２ａ〜２ｆ，２ｏ〜２ｑ，２Ａ〜２Ｅ  転送装置  １０，１０ａ  ネットワークシステム  １００  処理部  １０１  トポロジ情報処理部  １０２  プライマリ経路計算部  １０３  バックアップ経路計算部  １０４  経路設定部  １０５  状態変化検出部  １０６  オペレータＩ／Ｆ部  １１０  トポロジ情報ＤＢ  １２０  プライマリ経路情報ＤＢ  １３０  バックアップ経路情報ＤＢ  ２００  動作制御部  ２０１  隣接情報送信部  ２０２  障害・復帰情報送信部  ２０３  経路情報受信部  ２０４  ハードウェア管理部  ２１０  パケット制御部  ２１１  状態変化検出部  ２１２  パケット転送部  ２２０  プライマリ経路情報ＤＢ（記憶部）  ２３０  バックアップ経路情報ＤＢ（記憶部）  ３００  経路情報  ３０１  プライマリ経路情報  ３０２  バックアップ経路情報  ４００  パケット（通信データ）  １４０１  マスタ経路サーバ  １４０２，１４０２ａ，１４０２ｂ  サブ経路サーバ  １４１１  バックボーンエリア（第１のエリア）  １４１２，１４１２ａ，１４１２ｂ  サブエリア（第２のエリア）
【図１】
0005411817.tif 000002
【図２】
0005411817.tif 000003
【図３】
0005411817.tif 000004
【図４】
0005411817.tif 000005
【図５】
0005411817.tif 000006
【図６】
0005411817.tif 000007
【図７】
0005411817.tif 000008
【図８】
0005411817.tif 000009
【図９】
0005411817.tif 000010
【図１０】
0005411817.tif 000011
【図１１】
0005411817.tif 000012
【図１２】
0005411817.tif 000013
【図１３】
0005411817.tif 000014
【図１４】
0005411817.tif 000015
【図１５】
0005411817.tif 000016
【図１６】
0005411817.tif 000017
【図１７】
0005411817.tif 000018
【図１８】
0005411817.tif 000019
【図１９】
0005411817.tif 000020