(57)【要約】【課題】障害発生時にツリーの切替だけで通信が継続することを可能にする。【解決手段】本発明は、保護すべきサブツリーに対してバックアップサブツリーの経路を計算し、計算した経路に沿ってバックアップサブツリーを生成し、サブツリー内で障害発生時にトラヒックを前記バックアップサブツリーに切り替える。【選択図】　　　図１
2004080532.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクション方法において、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算し、
計算した経路に沿ってバックアップサブツリーを生成し、
前記サブツリー内で障害発生時にトラヒックを前記バックアップサブツリーに切り替えることを特徴とするマルチキャストプロテクション方法。
【請求項２】
前記バックアップサブツリーを生成する際に、
任意に選択された保護すべきサブツリーに対して、該サブツリーのソースノードから、該サブツリー内のユーザ収容ノードを除く全てのリンク及びノードを共有せずに迂回し、該サブツリーの１ホップ下流の全ノード及び該サブツリー内の全ユーザ収容ノードに接続するバックアップサブツリーを生成する請求項１記載のマルチキャストプロテクション方法。
【請求項３】
前記バックアップサブツリーの経路を計算する際に、
前記保護すべきサブツリーのソースノードが、既存のリンクステート型ルーチングプロトコルにより取得したトポロジ情報から該サブツリー内のノード及びリンクを除去したグラフと、自身が属するマルチキャストツリーのトポロジ情報を用いて、前記バックアップサブツリーの経路を計算する請求項１記載のマルチキャストプロテクション方法。
【請求項４】
前記保護すべきサブツリーのソースノードがバックアップサブツリーを生成するために、バックアップサブツリーの経路情報を記載した制御信号を、前記バックアップサブツリーのトポロジに沿って送信し、途中ノードでツリー状態を生成しながらバックアップサブツリーを構築する請求項１記載のマルチキャストプロテクション方法。
【請求項５】
前記保護すべきサブツリーに属するリンクもしくは、ノードに障害が発生した際に、
障害発生箇所の上流ノードがその障害を検出し、該上流ノードが、制御信号により障害の発生を前記サブツリーの上流側に送信し、
前記制御信号を受信したサブツリーのソースノードが、マルチキャストトラヒックをバックアップサブツリーに切り替える請求項１記載のマルチキャストプロテクション方法。
【請求項６】
マルチキャストツリーの生成にマルチキャストＭＰＬＳ（Ｍｕｌｔｉ　Ｐｒｏｔｏｃｏｌ　Ｌａｂｅｌ　Ｓｗｉｔｃｈｉｎｇ）　を利用する場合において、マルチキャストＭＰＬＳのＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ　ＬＳＰ　の一部分であるサブツリーに対してプロテクションを適応する請求項１記載のマルチキャストプロテクション方法。
【請求項７】
前記マルチキャストＭＰＬＳにおいて、
前記サブツリーを保護するためのバックアップサブツリーの生成プロトコル及びバックアップサブツリーのソースノードに対して障害を通知する制御信号として、マルチキャストＭＰＬＳのＲＳＶＰ−ＴＥ（Ｒｅｓｏｕｒｃｅ　Ｒｅｓｅｒｖａｔｉｏｎ　Ｐｒｏｔｏｃｏｌｆｏｒ　Ｔｒａｆｆｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ）　メッセージを利用する請求項６記載のマルチキャストプロテクション方法。
【請求項８】
マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクション装置であって、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算する経路計算手段と、
前記経路計算手段で計算された経路に沿ってバックアップサブツリーを生成するバックアップサブツリー生成手段と、
前記サブツリー内で障害発生時にトラヒックを前記バックアップサブツリーに切り替えるトラヒック切替手段と、を有することを特徴とするマルチキャストプロテクション装置。
【請求項９】
前記バックアップサブツリー生成手段は、
任意に選択された保護すべきサブツリーに対して、前記サブツリーのソースノードから、該サブツリー内のユーザ収容ノードを除く全てのリンク及びノードを共有せずに迂回し、該サブツリーの１ホップ下流の全ノード及び該サブツリー内の全ユーザ収容ノードに接続するバックアップサブツリーを生成する手段を含む請求項８記載のマルチキャストプロテクション装置。
【請求項１０】
前記経路計算手段は、
前記保護すべきサブツリーのソースノードが、既存のリンクステート型ルーチングプロトコルにより取得したトポロジ情報から該サブツリー内のノード及びリンクを除去したグラフと、自身が属するマルチキャストツリーのトポロジ情報を用いて、前記バックアップサブツリーの経路を計算する手段を含む請求項８記載のマルチキャストプロテクション装置。
【請求項１１】
前記バックアップサブツリー生成手段は、
途中ノードでツリー状態を生成しながらバックアップサブツリーを構築するために、バックアップサブツリーの経路情報を記載した制御信号を、前記バックアップサブツリーのトポロジに沿って送信する手段を含む請求項８記載のマルチキャストプロテクション装置。
【請求項１２】
前記トラヒック切替手段は、
前記保護すべきサブツリーに属するリンクもしくは、ノードに障害が発生した際に、障害発生箇所の上流ノードによりその障害が検出されると、該上流ノードから制御信号を受信し、該制御信号に基づいて、マルチキャストトラヒックをバックアップサブツリーに切り替える手段を有する請求項１１記載のマルチキャストプロテクション装置。
【請求項１３】
前記マルチキャストツリーの生成時にマルチキャストＭＰＬＳを利用する場合において、マルチキャストＭＰＬＳのＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ　ＬＳＰ（Ｌａｂｅｌ　Ｓｗｉｔｃｈｅｄ　Ｐａｔｈ）　　の一部分であるサブツリーに対してプロテクションを適応する手段を含む請求項８記載のマルチキャストプロテクション装置。
【請求項１４】
前記マルチキャストＭＰＬＳにおいて、
前記サブツリーを保護するためのバックアップサブツリーの生成プロトコル及びバックアップサブツリーのソースノードに対して障害を通知する制御信号として、マルチキャストＭＰＬＳのＲＳＶＰ−ＴＥメッセージを利用する請求項１３記載のマルチキャストプロテクション装置。
【請求項１５】
マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクションを実行するマルチキャストプロテクションプログラムであって、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算する経路計算ステップと、
前記経路計算ステップで計算された経路に沿ってバックアップサブツリーを生成するバックアップサブツリー生成ステップと、
前記サブツリー内で障害発生時にトラヒックを前記バックアップサブツリーに切り替えるトラヒック切替ステップと、を実行することを特徴とするマルチキャストプロテクションプログラム。
【請求項１６】
マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクションを実行するマルチキャストプロテクションプログラムを格納した記憶媒体であって、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算する経路計算ステップと、
前記経路計算ステップで計算された経路に沿ってバックアップサブツリーを生成するバックアップサブツリー生成ステップと、
前記サブツリー内で障害発生時にトラヒックを前記バックアップサブツリーに切り替えるトラヒック切替ステップと、を実行するプログラムを格納したことを特徴とするマルチキャストプロテクションプログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチキャストプロテクション方法及び装置及びマルチキャストプロテクションプログラム及びマルチキャストプロテクションプログラムを格納した記憶媒体に係り、特に、マルチキャストツリーのプロテクションを行うためのマルチキャストプロテクション方法及び装置及びマルチキャストプロテクションプログラム及びマルチキャストプロテクションプログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
従来のマルチキャストでは、マルチキャストツリーの途中経路上でリンク障害やノード障害が発生した場合、即座に障害箇所を迂回する技術がなく、ユニキャストルーチングプロトコルの再収束後にマルチキャストプロトコルが再度ツリーを構築しなおすことでマルチキャスト通信が再開している。
【０００３】
【発明が解決しようとする課題】
上記のように、従来は、再度ツリーを構築しなおすことでマルチキャスト通信が再開するため、障害の回避に数十秒から数分という時間を要し、その間はマルチキャスト通信が途絶えてしまうという問題がある。
【０００４】
本発明は、上記の点に鑑みなされたもので、障害発生時にツリーの切替だけで通信が継続することが可能なマルチキャストプロテクション方法及び装置及びマルチキャストプロテクションプログラム及びマルチキャストプロテクションプログラムを格納した記憶媒体を提供することを目的とする。
【０００５】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
【０００６】
本発明は、マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクション方法において、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算し（ステップ１）、
計算した経路に沿ってバックアップサブツリーを生成し（ステップ２）、
サブツリー内で障害発生時にトラヒックをバックアップサブツリーに切り替える（ステップ３）。
【０００７】
また、本発明は、バックアップサブツリーを生成する際に、
任意に選択された保護すべきサブツリーに対して、サブツリーのソースノードから、該サブツリー内のユーザ収容ノードを除く全てのリンク及びノードを共有せずに迂回し、該サブツリーの１ホップ下流の全ノード及び該サブツリー内の全ユーザ収容ノードに接続するバックアップサブツリーを生成する。
【０００８】
また、本発明は、バックアップサブツリーの経路を計算する際に、
保護すべきサブツリーのソースノードが、既存のリンクステート型ルーチングプロトコルにより取得したトポロジ情報からサブツリー内のノード及びリンクを除去したグラフと、自身が属するマルチキャストツリーのトポロジ情報を用いて、バックアップサブツリーの経路を計算する。
【０００９】
また、本発明は、保護すべきサブツリーのソースノードがバックアップサブツリーを生成するために、バックアップサブツリーの経路情報を記載した制御信号を、バックアップサブツリーのトポロジに沿って送信し、途中ノードでツリー状態を生成しながらバックアップサブツリーを構築する。
【００１０】
また、本発明は、保護すべきサブツリーに属するリンクもしくは、ノードに障害が発生した際に、
障害発生箇所の上流ノードがその障害を検出し、該上流ノードが、制御信号により障害の発生をサブツリーの上流側に送信し、
制御信号を受信したサブツリーのソースノードが、マルチキャストトラヒックをバックアップサブツリーに切り替える。
【００１１】
また、本発明は、マルチキャストツリーの生成にマルチキャストＭＰＬＳを利用する場合において、マルチキャストＭＰＬＳのＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ　ＬＳＰ　の一部分であるサブツリーに対してプロテクションを適応する。
【００１２】
また、本発明は、マルチキャストＭＰＬＳにおいて、
サブツリーを保護するためのバックアップサブツリーの生成プロトコル及びバックアップサブツリーのソースノードに対して障害を通知する制御信号として、マルチキャストＭＰＬＳのＲＳＶＰ−ＴＥメッセージを利用する。
【００１３】
図２は、本発明の原理構成図である。
【００１４】
本発明は、マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクション装置１００であって、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算する経路計算手段１１０と、
経路計算手段で計算された経路に沿ってバックアップサブツリーを生成するバックアップサブツリー生成手段１２０と、
サブツリー内で障害発生時にトラヒックをバックアップサブツリーに切り替えるトラヒック切替手段１３０と、を有する。
【００１５】
また、本発明のバックアップサブツリー生成手段１２０は、
任意に選択された保護すべきサブツリーに対して、サブツリーのソースノードから、該サブツリー内のユーザ収容ノードを除く全てのリンク及びノードを共有せずに迂回し、該サブツリーの１ホップ下流の全ノード及び該サブツリー内の全ユーザ収容ノードに接続するバックアップサブツリーを生成する手段を含む。
【００１６】
また、本発明の経路計算手段１１０は、
保護すべきサブツリーのソースノードが、既存のリンクステート型ルーチングプロトコルにより取得したトポロジ情報からサブツリー内のノード及びリンクを除去したグラフと、自身が属するマルチキャストツリーのトポロジ情報を用いて、バックアップサブツリーの経路を計算する手段を含む。
【００１７】
また、本発明のバックアップサブツリー生成手段１２０は、
途中ノードでツリー状態を生成しながらバックアップサブツリーを構築するために、バックアップサブツリーの経路情報を記載した制御信号を、バックアップサブツリーのトポロジに沿って送信する手段を含む。
【００１８】
また、本発明のトラヒック切替手段１３０は、保護すべきサブツリーに属するリンクもしくは、ノードに障害が発生した際に、障害発生箇所の上流ノードによりその障害が検出されると、該上流ノードから制御信号を受信し、該制御信号に基づいて、マルチキャストトラヒックをバックアップサブツリーに切り替える手段を有する。
【００１９】
また、本発明のマルチキャストプロテクション装置１００は、マルチキャストツリーの生成時にマルチキャストＭＰＬＳを利用する場合において、マルチキャストＭＰＬＳのＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ　ＬＳＰ　の一部分であるサブツリーに対してプロテクションを適応する手段を含む。
【００２０】
また、本発明のマルチキャストプロテクション装置１００は、マルチキャストＭＰＬＳにおいて、
サブツリーを保護するためのバックアップサブツリーの生成プロトコル及びバックアップサブツリーのソースノードに対して障害を通知する制御信号として、マルチキャストＭＰＬＳのＲＳＶＰ−ＴＥメッセージを利用する。
【００２１】
本発明は、マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクションを実行するマルチキャストプロテクションプログラムであって、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算する経路計算ステップと、
経路計算ステップで計算された経路に沿ってバックアップサブツリーを生成するバックアップサブツリー生成ステップと、
サブツリー内で障害発生時にトラヒックをバックアップサブツリーに切り替えるトラヒック切替ステップと、を実行する。
【００２２】
本発明は、マルチキャストネットワーク上でマルチキャストツリーの一部であるサブツリーに対してプロテクションを適用するためのマルチキャストプロテクションを実行するマルチキャストプロテクションプログラムを格納した記憶媒体であって、
保護すべきサブツリーに対してバックアップサブツリーの経路を計算する経路計算ステップと、
経路計算ステップで計算された経路に沿ってバックアップサブツリーを生成するバックアップサブツリー生成ステップと、
サブツリー内で障害発生時にトラヒックをバックアップサブツリーに切り替えるトラヒック切替ステップと、を実行するプログラムを格納する。
【００２３】
上記のように、本発明では、事前にバックアップサブツリーが生成されていることで、障害発生時にルーチングプロトコルの経路再収束やマルチキャストプロトコルによるツリーの再構築が不要となり、障害の発生をサブツリーのソースノードに通知するだけでバックアップサブツリーへの経路切替が完了するため、従来のマルチキャストでは実現困難な高速な障害回避が実現できる。
【００２４】
さらに、任意のサブツリーに対してプロテクションを適用することができるため、障害の影響範囲の大きいマルチキャストツリーのソース付近にだけプロテクションを適用することや、特定の顧客に対する経路上のみをプロテクションの対象とするといったことが可能であり、サービスの要求条件やツリーの規模に応じた柔軟なプロテクションの適用が可能となる。
【００２５】
また、本発明では、サブツリー内のいかなるリンク及びノードに障害が発生しても、バックアップサブツリーに切り換えることにより、当該サブツリーより下流のノードに対するトラヒックを保護することができる。また、バックアップサブツリーに保護対象となるサブツリー内のユーザ収容ノードを含むことにより、バップアップサブツリーへの切替が完了した後も、当該ユーザ収容ノードに収容されるユーザに対するトラヒックを保護することができる。
【００２６】
また、本発明によれば、ＯＳＰＦ等の既存のリンクステート型ルーチングプロトコルにより得られるネットワークトポロジ情報と、自身が属するマルチキャストツリーのトポロジ情報を利用するだけで容易にバックアップサブツリーの経路を計算することが可能となる。これらの情報をサブツリーのソースノードが取得することは容易であり、バックアップサブツリーの経路計算のために必要な情報を収集するために新たなプロトコルの開発を必要としないという利点がある。
【００２７】
また、本発明では、計算された経路に沿って自動的にバックアップサブツリーを生成することが可能である。また、マルチキャストツリーを生成する際に、ソース起動型のツリー作成プロトコルを利用する場合には、バックアップサブツリーの生成にも同一のプロトコルが利用できる。これにより、バックアップサブツリー生成用の特殊なプロトコルを開発するコストを省くことができると共に、複数のツリー生成プロトコルを動作させずに済むことによるノードの処理負荷の軽減を図ることが可能となる。
【００２８】
また、本発明では、障害を検出したノードが、制御信号により即座に上流に障害が発生した旨を通知するため、サブツリーのソースノードが早期に障害発生を認識することが可能となり、障害発生からバックアップサブツリーへの経路の切替までの時間を大幅に短縮することができる。これにより、障害発生によるエンドユーザへの影響を最小限に留め、高信頼なマルチキャストサービスを実現することが可能となる。
【００２９】
また、本発明によれば、マルチキャストＭＰＬＳプロトコルにより生成されたＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ　ＬＳＰ　の一部分であるサブツリーに対して、サブツリー全体を保護するプロテクション機能を提供することが可能となる。これにより、従来のユニキャストＭＰＬＳで可能であったリンク・ノードプロテクションと同様の機能をマルチキャストＭＰＬＳ上でも実現することが可能となる。
【００３０】
また、本発明によれば、マルチキャストＭＰＬＳで提案されているＲＳＶＰ−ＴＥ　拡張プロトコルをそのままバックアップサブツリーの生成に用いることができると共に、障害通知の制御信号としてもＲＳＶＰ−ＴＥ　のメッセージを利用することができる。これにより、マルチキャストツリーの生成・バックアップサブツリーの生成・障害通知の制御信号の全てを同一のプロトコルセットで実現できるため、アーキテクチャの簡易化が図れると共に、実装もシンプルなものとなる。
【００３１】
【発明の実施の形態】
以下、図面共に本発明の実施の形態を説明する。
【００３２】
図３は、本発明の一実施の形態におけるマルチキャストプロテクション装置の構成を示す。
【００３３】
同図に示すマルチキャストプロテクション装置１００は、マルチキャストツリーの計算や生成を行うプロトコル処理部５１と、データパケットの転送処理を高速で実施するパケット処理部５２から構成される。
【００３４】
プロトコル処理部５１は、ＯＳＰＦ等のリンクステートルーチングプロトコルを動作させるルーチングプロトコルモジュール５３、そのプロトコルによって得られたネットワークトポロジ情報を格納するリンクステートデータベース５４、マルチキャストＭＰＬＳで生成するツリーのトポロジを格納するマルチキャストツリートポロジデータベース５６、マルチキャストツリートポロジデータベース５６の情報を元に実際にツリーを生成するマルチキャストＭＰＬＳプロトコルを動作させるマルチキャストＭＰＬＳプロトコルモジュール５５、及び、既に確立したマルチキャストツリーに対して、障害時の迂回路となるバックアップサブツリーを計算するバックアップサブツリー計算モジュール５７から構成される。
【００３５】
パケット処理部５２は、パケット転送処理部５８、パケット転送テーブル５９、及びネットワークインタフェース６０から構成される。
【００３６】
ネットワークインタフェース６０で受信されたパケットは、パケット転送処理部５８に渡される。パケット転送処理部５８では、通常のデータパケットであれば、パケット転送テーブル５９を参照して次ホップを決定し、パケットを転送する。受信したパケットがプロトコル処理に関するものであれば、そのパケットの種別に応じたプロトコル処理モジュール（ルーチングプロトコルモジュール５３、もしくは、マルチキャストＭＰＬＳプロトコルモジュール５５）に送る。
【００３７】
次に、上記の構成における一連の動作を説明する。
【００３８】
図４は、本発明の一実施の形態におけるバックアップサブツリーを生成動作のフローチャートである。
【００３９】
ステップ１０１）　バックアップサブツリー計算モジュール５７が、リンクステートデータベース５４からネットワークトポロジの情報を、さらに、マルチキャストツリートポロジデータベース５６からバックアップサブツリーを生成する元となるツリーの構成情報を取得する。
【００４０】
ステップ１０２）　バックアップサブツリー計算モジュール５７が、それらの情報を利用して、バックアップサブツリーを計算する。
【００４１】
ステップ１０３）　バックアップサブツリーのトポロジが決まったら、そのトポロジ情報をマルチキャストＭＰＬＳプロトコルモジュール５５に渡す。
【００４２】
ステップ１０４）　ＭＰＬＳプロトコルモジュール５５は、ＲＳＶＰ−ＴＥシグナリングを用いてバックアップサブツリーを生成する。
【００４３】
一方、障害が発生した場合の処理を以下に示す。
【００４４】
図５は、本発明の一実施の形態におけるバックアップサブツリーへの迂回処理の手順を示すフローチャートである。
【００４５】
パケット転送処理部５８は、自ノードが障害発生を検出したノードであれば、障害の発生をマルチキャストＭＰＬＳプロトコルモジュール５５に通知し、該当リンクに障害の影響を受けたＬＳＰがあるかどうかを判定する（ステップ２０１）。また、下流ノードからＲＳＶＰ−ＴＥのエラーメッセージにより障害発生の通知を受けた場合（ステップ２０２）も、その通知がマルチキャストＭＰＬＳプロトコルモジュール５５に渡され、ＬＳＰの障害発生を認識する（ステップ２０３）。
【００４６】
次に、自ノードがバックアップサブツリーのソースノードとなっているかどうか判定する（ステップ２０４）。即ち、自ノードで転送経路の切り替えが可能かどうかを判断する。自ノードがソースノードでなければ、さらに上流のノードに対してＲＳＶＰ−ＴＥエラーメッセージを送信する（ステップ２０５）。
【００４７】
自ノードがソースノードであれば、転送経路を切り替えるために、マルチキャストＭＰＬＳプロトコルモジュール５５が、パケット処理部５２にあるパケット転送テーブル５９を書き換える（ステップ２０６）。これによりバックアップサブツリーへ経路が切り替わることとなり、迂回処理が完了する（ステップ２０７）。
【００４８】
【実施例】
以下、図面と共に本発明の実施例を説明する。
【００４９】
本実施例では、マルチキャストツリーを生成するプロトコルとしてＲＳＶＰ−ＴＥ　を拡張したマルチキャストＭＰＬＳを適用する。マルチキャストＭＰＬＳは、通常のＭＰＬＳで用いられるＲＳＶＰ−ＴＥ　に対して、ＬＳＰ　を生成するメッセージ中にツリートポロジを格納できる情報要素を追加し、そのトポロジ情報に沿ってＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ　ＬＳＰ　を確立することができる技術である。
マルチキャストＭＰＬＳでは、ソース側からツリーを構築するＲｏｏｔ−ｉｎｉｔｉａｔｅｄ方式と、リーフ側からツリーを構築するＬｅａｆ−ｉｎｉｔｉａｔｅｄ方式の両方をサポートしているが、本発明は、Ｒｏｏｔ−ｉｎｉｔｉａｔｅｄ方式において適用されるものである。
まず、保護対象となるサブツリーに対応するバックアップサブツリーを生成するステップについて説明する。
【００５０】
図６は、本発明の一実施例のバックアップサブツリーが満たす条件を説明するための図である。
【００５１】
図６に示すマルチキャストネットワーク１において、１０個のノード＃１〜＃１０を含むマルチキャストツリー２を考える。このうち、ノード＃１は、ソース、ノード＃６、＃８、＃９、＃１０は直接ユーザを収容しているノード（リーフノード）である。ここで、保護対象となるサブツリー３として、ノード＃１、＃２、＃４、＃５、＃６を想定する。
【００５２】
ここで、サブツリー３を保護するバックアップサブツリー４を生成する。バックアップサブツリー４は、サブツリー３のソースノード１から、サブツリー３内のユーザ収容ノード＃６を除く全てのリンク及びノードを共有せずに迂回し、サブツリー３の１ホップ下流のノード＃８、＃９、＃１０、及びサブツリー３内のユーザ収容ノード＃６を接続しなくてはならず、図６に太破線で示したようなツリーとなる。
【００５３】
このような条件を満たすバックアップサブツリーの経路を、サブツリーのソースノードとなるノード＃１が、自身の保持する情報から計算する。サブツリーのソースノードは、図７に示すように、ＯＳＰＦ等のリンクステート型ルーチングプロトコルによって得られたネットワーク内のリンクステートデータベース（ネットワークトポロジ情報）１１と、自身が属するマルチキャストツリートポロジ情報１２を保持する。ツリーの生成にマルチキャストＭＰＬＳを利用する本実施の形態では、ツリー本体を生成する拡張ＲＳＶＰ−ＴＥ　のメッセージ中にマルチキャストツリートポロジを表す情報要素が含まれ、これによりマルチキャストツリートポロジ情報１２を得ることができる。
【００５４】
これらの情報を用いて、サブツリーのソースノードは、以下のような手順でバックアップサブツリーを計算する。
【００５５】
▲１▼　まず、マルチキャストツリートポロジ情報１２を参照し、保護対象サブツリー１３の１ホップ下流のノードを検索する。この場合、ノード＃８、＃９、＃１０が該当する。
【００５６】
▲２▼　次に、保護対象サブツリー１３の中に、直接ユーザを収容するリーフノードが含まれているかどうかを調べる。ここでは、ノード＃６がそれに該当する。この時点で、バックアップサブツリーは、サブツリーのソースノード＃１と、ノード＃６、＃８、＃９、＃１０を結ぶツリーになることが決まる。
【００５７】
▲３▼　次に、図８に示すように、リンクステートデータベース２１から、保護対象サブツリーに含まれるリンク２２とノード２３を除去し、残ったリンクとノードの集合からなるグラフから、上記の▲２▼で決定したノード群を含むバックアップサブツリー２４を決定する。ここで、バックアップツリーの経路を実際に計算する手法は、既に提案されているアルゴリズム（ＳＰＴ：Ｓｈｏｕｒｔｅｓｔ　Ｐａｔｈ　Ｔｒｅｅ　など）を適用することができる。
【００５８】
このようにして得られたバックアップサブツリーに沿って、マルチキャストＭＰＬＳを用いて、実際にツリーを生成する。
【００５９】
図９のシーケンス図に示すように、サブツリーのソースノード＃１から、バックアップサブツリーのトポロジ情報３２を含むＲＳＶＰのＰａｔｈメッセージ３１を下流方向に送信し、途中ノードでは、Ｐａｔｈメッセージに含まれるトポロジ情報３２に従って、次々とＰａｔｈメッセージを下流に送信する。それに応じてＲｅｓｖメッセージ３３が上流に返されることにより、バックアップサブツリーが生成される。この一連の動作は、マルチキャストＭＰＬＳを利用してマルチキャストツリーを生成する動作と全く同一である。
【００６０】
最後に、障害が発生した際にトラフィックをバックアップサブツリーに切り換える処理について説明する。
【００６１】
図１０に示すように、サブツリー内で障害が発生した箇所（障害箇所４１）の上流ノード＃２が障害を検出すると、ツリーの上流側に向かって障害通知メッセージ４２を送信する。マルチキャストＭＰＬＳでは、ＰａｔｈＥｒｒ　（パスエラー）メッセージが送信される。サブツリーのソースノード＃１がこのメッセージを受信し、障害箇所がサブツリー内部であることを確認すると、トラヒックの送信をバックアップサブツリー４３に切り換える。これにより、高速に障害箇所を回避し、マルチキャスト通信を継続することが可能となる。
【００６２】
また、実施の形態におけるマルチキャストプロテクション装置の構成要素をプログラムとして構築し、マルチキャストプロテクション装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【００６３】
また、構築されたプログラムをマルチキャストプロテクション装置として利用されるコンピュータに接続されるハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際にインストールすることにより、本発明を実現することも可能である。
【００６４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【００６５】
【発明の効果】
上述のように、本発明によれば、マルチキャストツリーの一部分であるサブツリーを保護対象とするバックアップサブツリーを予め生成しておくことにより、障害発生時にツリーの切り替えだけで通信を継続することができ、障害発生による通信への影響を最小限に抑えることが可能となる。これにより、既存のマルチキャストでは困難であった高信頼なサービスを提供することができるようになる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態におけるマルチキャストプロテクション装置の構成図である。
【図４】本発明の一実施の形態におけるバックアップサブツリーの生成動作のフローチャートである。
【図５】本発明の一実施の形態におけるバックアップサブツリーへの迂回処理の手順を示すフローチャートである。
【図６】本発明の一実施例のバックアップサブツリーが満たす条件を説明するための図である。
【図７】本発明の一実施例のサブツリーのソースノードが保持する情報を説明するための図である。
【図８】本発明の一実施例のサブツリーのソースノードが保持する情報からバックアップサブツリーを決定する手順を説明するための図である。
【図９】本発明の一実施例のマルチキャストＭＰＬＳによってバックアップサブツリーを生成するシーケンスを説明するための図である。
【図１０】本発明の一実施例のサブツリー内で障害が発生した際にバックアップサブツリーにトラヒックを切り替える動作を説明するための図である。
【符号の説明】
１　マルチキャストネットワーク
２　マルチキャストツリー
３　保護対象となるサブツリー
４　バックアップサブツリー
１１　リンクステートデータベース（トポロジ情報）
１２　マルチキャストツリートポロジ情報
１３　保護対象サブツリー
２１　リンクステートデータベース（ネットワークトポロジ情報）
３１　ＲＳＶＰのＰａｔｈメッセージ
３２　バックアップサブツリーのトポロジ情報
４１　障害箇所
４２　障害通知メッセージ
４３　バックアップサブツリー
５１　プロトコル処理部
５２　パケット処理部
５３　ルーチングプロトコルモジュール
５４　リンクステートデータベース
５５　マルチキャストＭＰＬＳプロトコルモジュール
５６　マルチキャストツリートポロジデータベース
５７　バックアップサブツリー計算モジュール
５８　パケット転送処理部
５９　パケット転送テーブル（フォワーディングテーブル）
６０　ネットワークインタフェース
１００　マルチキャストキャストプロテクション装置
１１０　経路計算手段
１２０　バックアップサブツリー生成手段
１３０　トラヒック切替手段
【図１】
2004080532.tif 000003
【図２】
2004080532.tif 000004
【図３】
2004080532.tif 000005
【図４】
2004080532.tif 000006
【図５】
2004080532.tif 000007
【図６】
2004080532.tif 000008
【図７】
2004080532.tif 000009
【図８】
2004080532.tif 000010
【図９】
2004080532.tif 000011
【図１０】
2004080532.tif 000012