(57)【要約】【課題】冗長マルチキャストツリーを構成する際に必要となるループを効率的に発見すること。【解決手段】本発明は、複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置に適用される。本発明のマルチキャストツリー計算装置は、送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有する。【選択図】図１
2011166360.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置であって、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、
前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有することを特徴とするマルチキャストツリー計算装置。
【請求項２】
前記グループ間リンク抽出部にて抽出された各リンクを基準に従い評価し、その評価結果に基づいて、前記ループを構成する際に使用するリンクを選択するリンク評価値計算部をさらに有することを特徴とする請求項１に記載のマルチキャストツリー計算装置。
【請求項３】
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パスのパス長を用いることを特徴とする請求項２に記載のマルチキャストツリー計算装置。
【請求項４】
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端のノードのそれぞれ上流にある各ノードへの各パスのパス長の差も用いることを特徴とする請求項３のマルチキャストツリー計算装置。
【請求項５】
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パス中に含まれる各リンクのコスト値を用いることを特徴とする請求項２に記載のマルチキャストツリー計算装置。
【請求項６】
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パス中に含まれる各リンクのリンク遅延を用いることを特徴とする請求項２に記載のマルチキャストツリー計算装置。
【請求項７】
送信元ノードから各ノードまでの最短パスツリーを計算する最短パスツリーを計算する最短パスツリー計算部をさらに有し、
前記ノードグルーピング部は、前記最短パスツリー計算部にて計算された最短パスツリーを用いて、前記グループ分けを行うことを特徴とする請求項１から６のいずれか１項に記載のマルチキャストツリー計算装置。
【請求項８】
前記最短パスツリー計算部は、ダイクストラ法を用いて最短パスツリーを計算することを特徴とする請求項７に記載のマルチキャストツリー計算装置。
【請求項９】
複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置によるマルチキャストツリー計算方法であって、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うグルーピングステップと、
前記分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するリンク抽出ステップと、を有することを特徴とするマルチキャストツリー計算方法。
【請求項１０】
リンクを介して互いに接続された複数のノードと、
送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置と、を有し、
前記マルチキャストツリー計算装置は、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、
前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有することを特徴とするネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いに冗長な２つのマルチキャストツリーを計算する技術に関する。
【背景技術】
【０００２】
マルチキャストは、送信元から送出されたパケットをネットワーク中でコピーし、複数の受信者に配信する通信方式であり、ネットワーク上において映像配信などの放送型サービスを実現するために用いられている。
【０００３】
しかし、マルチキャストでは、ネットワーク中でパケットロスが発生すると、多数の受信者に影響を与えるため、高信頼化の技術が必要となる。
【０００４】
そこで、通常のマルチキャストに送達確認機能や再送機能を付与した、高信頼マルチキャストという技術が開発されている。しかし、高信頼マルチキャストで用いられている、パケットロスが発生した場合に再送を行うというアプローチは、再送の間、視聴映像が停止してしまうという問題が発生してしまうため、放送型サービスには向いていない。
【０００５】
高信頼化を実現する別のアプローチとして、２つのマルチキャストツリーを互いに冗長になるように構成し、それぞれのマルチキャストツリー上にて冗長にパケットを配信することで、信頼性を確保するという手法が存在する。ここで、「互いに冗長」と呼んでいるのは、送信元ノードを除くいずれかのノードもしくはリンクが故障によりなくなったとしても、故障ノードを除くすべてのノードが、２つのマルチキャストツリーのいずれかにて送信元ノードと接続されている状態のことである。
【０００６】
図７は、ノード１１〜２０をリンクを介して接続したネットワーク上に、互いに冗長となるように構成した２つのマルチキャストツリーの例を示した図である。
【０００７】
例えば、ノード１２が故障した場合、ノード１３はパケットをツリー１経由で受信できなくなる。しかし、ノード１３は、ノード１７，１６，１５，１４の順でパケットが流れてくるツリー２経由で、パケットを受信することが可能である。
【０００８】
このように、映像配信を互いに冗長となる２つのマルチキャストツリーを用いて行うことにより、ネットワーク中のノードもしくはリンクが単一で故障を発生した時にも、パケットロスなくサービスを提供し続けることができる。
【０００９】
この互いに冗長となるマルチキャストツリーを計算する方法は、非特許文献１に開示されている。この方法では、送信元ノードを基点かつ終点とするループを構成し、そのループに沿ってツリー１のパスを張り、逆方向にツリー２のパスを張るということを行っている。
【００１０】
図８Ａは、送信元を基点かつ終点としたループ構成を示す図である。図８Ａでは、ノード１１→ノード１２→ノード１５→ノード１６→ノード１７→ノード１１というループが構成されている。このループに沿って、構成されたツリーが図８Ｂに示されている。図８Ｂでは、ツリー１のパスが、ノード１１→ノード１２→ノード１５→ノード１６→ノード１７という順で構成されている。さらにこのパスとは逆方向に、ノード１１→ノード１７→ノード１６→ノード１５→ノード１２という順にツリー２のパスが構成されている。
【００１１】
図８Ｂでは、ノード１３，１４，１８，１９，２０は、まだいずれのツリーにも組み込まれていない。このとき、図８Ｂの終了時点ですでにツリーに組み込まれているノード（ノード１１，１２，１５，１６，１７）を仮想的な送信元ノード２１とみなし、ノード２１→ノード１３→ノード１４→ノード２１というループを構成する（図９Ａ）。さらにこのループの順逆方向にそって、それぞれツリー１，２のパスを構成する（図９Ｂ）。
【００１２】
このように、基本的に、送信元ノードを基点かつ終点としたループを構成し、ループの順逆方向にそれぞれパスを構成するという手順を繰り返していくことで、すべてのノードを含む２つのマルチキャストツリーを構成することができる。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Medard, M. and Finn, S.G. and Barry, R.A. : "Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs," IEEE/ACM Transactions on Networking (TON), Vol.7, No.5, pp.641-652, 1999.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、非特許文献１に開示された方法には、以下のような課題がある。
【００１５】
第１の課題は、互いに冗長となる２つのマルチキャストツリー（冗長マルチキャストツリー）の構成の際に用いるループを、どのように発見するかという具体的な方法が示されていないということである。
【００１６】
第２の課題は、ループの構成法によっては、送信元ノードからあるノードまでのツリー１とツリー２のそれぞれのパス長の差が大きくなる場合があるということである。この場合、送信元ノードから送出されたあるパケットがそれぞれのツリー上のパスを経由してそのノードに到達するとき、受信時刻の差が大きくなる。もし、一方のパス上で失われたパケットをもう一方のパスで受信したパケットで補完することを考えた場合、映像配信においては受信時刻の差は小さいほうが望ましい。
【００１７】
そこで、本発明は、上述した課題のいずれかを解決することができるマルチキャストツリー計算装置および計算方法、並びにネットワークシステムを提供することにある。
【課題を解決するための手段】
【００１８】
本発明のマルチキャストツリー計算装置は、
複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置であって、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、
前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有することを特徴とする。
【００１９】
本発明のマルチキャストツリー計算方法は、
複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置によるマルチキャストツリー計算方法であって、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うグルーピングステップと、
前記分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するリンク抽出ステップと、を有することを特徴とする。
【００２０】
本発明のネットワークシステムは、
リンクを介して互いに接続された複数のノードと、
送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置と、を有し、
前記マルチキャストツリー計算装置は、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、
前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有することを特徴とする。
【発明の効果】
【００２１】
本発明によれば、送信元ノードの次転送先ノード毎に各ノードをグルーピングし、リンク両端のノードがそれぞれ異なるグループに所属するリンクを、ループを構成する際に使用するリンクの候補として抽出する。
【００２２】
そのため、冗長マルチキャストツリーを構成する際に必要となるループを効率的に発見することができるという効果が得られる。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１および第２の実施形態のマルチキャストツリー計算装置の構成を示すブロック図である。
【図２】本発明の第１の実施形態のマルチキャストツリー計算装置における冗長マルチキャストツリーを計算する処理を示すフローチャートである。
【図３】本発明の第１の実施形態のマルチキャストツリー計算装置における冗長マルチキャストツリーを構成する過程の一状態を示す図である。
【図４】各リンクにコスト値が付与されたネットワーク上に最短パスツリーが構成されている例を示す図である。
【図５】本発明の第２の実施形態のマルチキャストツリー計算装置における冗長マルチキャストツリーを構成する過程の一状態を示す図である。
【図６】本発明の第２の実施形態のマルチキャストツリー計算装置におけるパス長評価値を求める処理を示すフローチャートである。
【図７】ネットワーク上に冗長マルチキャストツリーが構成されている例を示す図である。
【図８Ａ】非特許文献１に記載の方法における冗長マルチキャストツリーを構成する過程の一状態を示す図である。
【図８Ｂ】非特許文献１に記載の方法における冗長マルチキャストツリーを構成する過程の一状態を示す図である。
【図９Ａ】非特許文献１に記載の方法における冗長マルチキャストツリーを構成する過程の一状態を示す図である。
【図９Ｂ】非特許文献１に記載の方法における冗長マルチキャストツリーを構成する過程の一状態を示す図である。
【発明を実施するための形態】
【００２４】
以下に、本発明を実施するための形態について図面を参照して説明する。
（１）第１の実施形態
図１は、本発明の一実施形態のマルチキャストツリー計算装置の機能構成を示すブロック図である。なお、本発明のマルチキャストツリー計算装置は、ネットワークシステムを構成するノードの内部、または、ノードの外部のサーバ等により実現されるものである。
【００２５】
図１に示すように、本実施形態のマルチキャストツリー計算装置１００は、最短パスツリー計算部１０１、ノードグルーピング部１０２、グループ間リンク抽出部１０３、リンク評価値計算部１０４、ループ構成部１０５、ツリーパス構成部１０６、トポロジー情報データベース１１１、および冗長マルチキャストツリー保管部１１２から構成される。
【００２６】
最短パスツリー計算部１０１は、トポロジー情報データベース１１１を参照し、送信元ノードから各ノードまでの最短パスツリーを計算する。
【００２７】
ノードグルーピング部１０２は、送信元の次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行う。
【００２８】
グループ間リンク抽出部１０３は、ノードグルーピング部１０２によるグループ分けの結果から、トポロジー情報データベース１１１を参照し、リンク両端のノードがそれぞれ異なるグループに所属するようなリンクを、ループを構成する際に使用するリンクの候補として抽出する。
【００２９】
リンク評価値計算部１０４は、グループ間リンク抽出部１０３により抽出された各リンクを、基準に従って評価する。ここでは、送信元ノードからのパス長を基準に評価するものとする。すなわち、リンク評価値計算部１０４は、各リンクのパス長評価値を計算し、パス長評価値が一番低いリンクを選択する。
【００３０】
ループ構成部１０５は、リンク評価値計算部１０４により選択されたリンクを用いて、冗長マルチキャストツリー構築段階で必要なループを構成する。
【００３１】
ツリーパス構成部１０６は、ループ構成部１０５により構成されたループの順逆方向に沿ってツリー１，２のパスを構成する。
【００３２】
トポロジー情報データベース１１１は、計算対象となるネットワークのトポロジー情報が格納されたデータベースである。トポロジー情報データベース１１１へのトポロジー情報の格納は、事前に手動で入力してもよいし、ネットワーク管理ソフトウェアなどが他のシステムにおいて収集、管理している情報を入力してもよい。
【００３３】
冗長マルチキャストツリー保管部１１２は、ツリーパス構成部１０６により構成されたツリー１，２にネットワーク中の全ノードが含まれるときに、そのツリー１，２を冗長マルチキャストツリーの最終出力結果として格納する。
【００３４】
以下、本実施形態のマルチキャストツリー計算装置１００における冗長マルチキャストツリーを計算する処理を、図２のフローチャートに沿って説明する。
【００３５】
図２に示すように、まず、最短パスツリー計算部１０１は、トポロジー情報データベース１１１を参照し、送信元ノードから各ノードまでの最短パスツリーを、ダイクストラ法を用いて計算する（ステップＡ１）。ここでは、他の最短パスツリー計算のアルゴリズムを、ダイクストラ法の代わりに用いてもよい。
【００３６】
以降の処理は、ステップＡ１で計算した最短パスツリーをベースに行われるが、必ずしも最短パスツリーである必要はない。つまり、全ノードが含まれ、送信元ノードが基点となるツリーであれば、以降の処理は他のツリーを用いても行ってもよい。
【００３７】
次に、ノードグルーピング部１０２は、送信元ノードを除く各ノードを、送信元ノードの次転送先毎にグループ分けする（ステップＡ２）。図３の矢印は、送信元ノード１１を基点とする最短パスツリーを表している。ここでは、ノード１２とノード１７の２つのノードが送信元ノード１１の次転送先となっており、各ノードはノード１２を含むグループ３１とノード１７を含むグループ３２のいずれかに分類される。ノード１２，１７以外の各ノードがいずれかのグループに分類されるかは、以下のように決定される。最短パスツリー上でノード１２の下流側にあるノードを、ノード１２と同じグループ３１へと分類する。つまりノード１３，１４，１５，２０はグループ３１へと分類される。同様にノード１７の下流側にあるノード１６，１８，１９は、グループ３２へと分類される。
【００３８】
次に、グループ間リンク抽出部１０３は、リンク両端のノードがそれぞれ異なるグループに所属しているリンクを抽出する（ステップＡ３）。図３の例では、ノード１５と１６の間のリンクおよびノード１９と２０の間のリンクがこの条件に該当する。
【００３９】
次に、リンク評価値計算部１０４は、ステップＡ３で抽出された各リンクに対し、パス長評価値を計算し、このパス長評価値が一番低いリンクを選択する（ステップＡ４）。ここで、パス長評価値とは、このリンクを使用して構成するループのパス長を表す値であり、この値が低いほど構成した２つのツリーにおける送信元からのパス長の差が小さくなる。このパス長評価値は、次のように算出する。まず、リンク両端のノードそれぞれに対し、最短パスツリー上で送信元ノードからのパス長を求める。これらの値を合計したものが、そのリンクのパス長評価値である。図３の例では、ノード１５，１６間のリンクに関しては、送信元ノード１１からノード１５へのパス長は２、ノード１６へのパス長も２であるので、このリンクのパス長評価値は４である。一方、ノード１９，２０間のリンクに関しては、送信元ノード１１からノード１９へのパス長が３、ノード２０へのパス長が４であるので、このリンクのパス長評価値は７である。この場合、パス長評価値が低いノード１５，１６間のリンクの方が選択される。
【００４０】
次に、ループ構成部１０５は、ステップＡ４で選択されたリンクを用いて、ループを構成する（ステップＡ５）。図３の例では、ノード１５，１６間のリンクが選択されたため、ノード１１→ノード１２→ノード１５→ノード１６→ノード１７→ノード１１のループが構成される。
【００４１】
次に、ツリーパス構成部１０６は、ステップＡ５で構成されたループに沿って、ツリー１，２を構成する（ステップＡ６）。図３の例では、ツリー１はノード１１→ノード１２→ノード１５→ノード１６→ノード１７と構成され、ツリー２はノード１１→ノード１７→ノード１６→ノード１５→ノード１２と構成される。
【００４２】
ここで、ネットワーク中のすべてのノードがツリーに組み込まれている場合は（ステップＡ７のＹｅｓ）、冗長マルチキャストツリー保管部１１２が、ツリーパス構成部１０６において構成されたツリー１，２を、冗長マルチキャストツリーの最終出力結果として格納し、処理を終了する。
【００４３】
一方、ネットワーク中のすべてのノードがツリーに組み込まれていない場合は（ステップＡ７のＮｏ）、ステップＡ８へと進む。
【００４４】
ステップＡ８において、ノードグルーピング部１０２は、これまでのステップでツリー１，２に組み込まれたノード群を１つの仮想的な送信元ノードとみなし、各ノードを送信元ノードの次転送先毎にグループ分けを行い、その後に、ステップＡ３へと戻る。このステップＡ８は、実際の送信元ノードの代わりに、仮想的な送信元ノードを使う点を除けば、ステップＡ２と同様の動作である。
【００４５】
なお、本実施形態では、リンク評価値計算部１０４において、リンクを評価する基準として、送信元ノードからのパスの長さであるパス長評価値を用いていたが、その代わりに、パス中のリンクのコスト値の合計値であるコスト評価値を用いてもよい。例えば、図４のように各リンクにコスト値が付与されているネットワークにおいて、ノード１５とノード１６の間のリンクのコスト評価値は以下のように求める。ノード１１からノード１５へのパス上のリンクのコストを合計すると、２＋５で７になる。また、ノード１１からノード１６へのパス上のリンクのコストを合計すると、２＋４で６になる。つまりノード１５とノード１６の間のリンクのコスト評価値は１３となる。
【００４６】
また、リンクのコスト値の代わりに、リンクの遅延の値を使用してもよい。この場合、他のシステムにおいて各リンクの遅延を測定し、その値をコスト値の代わりにし、コスト値の場合と同様の計算を行うことで得られる評価値を用いる。
【００４７】
上述したように本実施形態では、あるツリーを元に、送信元ノードの次転送先ノード毎に各ノードをグルーピングし、リンク両端のノードがそれぞれ異なるグループに所属するようなリンクを、ループを構成する際に使用するリンクの候補として抽出する。
【００４８】
そのため、冗長マルチキャストツリーを構成する際に必要となるループを効率的に発見することができるという効果が得られる。
【００４９】
また、本実施形態では、上記で抽出された各リンクについて、リンク両端のノードの送信元ノードからのパスの長さや、パスに含まれる各リンクのコスト値や遅延を用いて評価を行い、その評価結果を基に、ループを構成する際に使用するリンクを選択する。
【００５０】
そのため、送信元ノードから各ノードへの２つのパス長の差がなるべく小さくなるループを発見することができるという効果が得られる。
（２）第２の実施形態
本実施形態のマルチキャストツリー計算装置１００の構成自体は第１の実施形態と同様である。
【００５１】
第１の実施形態では、送信元からのパス長を評価値として用いていた。しかし、図２におけるステップＡ８で仮想的な送信元ノードを考慮した場合、この仮想的な送信元ノードから送出されるパケットはパスにより異なるタイミングで送出される可能性がある。
【００５２】
図９Ａおよび図９Ｂの例では、仮想的な送信元ノード２１→ノード１３→ノード１４とループが構成され、このループに沿ってツリー１，２が延伸されている。このとき、実際には、ツリー１経由において、ノード１３へはノード１１およびノード１２を経由してパケットは到達し、ツリー２経由において、ノード１４へはノード１７，１６，１５を経由してパケットは到達する。しかし、この仮想的な送信元ノード２１内に含まれる分のパス長は、第１の実施形態で用いていたパス長評価値では考慮されていなかった。
【００５３】
そこで、本実施形態では、仮想的な送信元ノード内に含まれる部分のパス長も考慮した新しいパス長評価値を導入する。
【００５４】
以下、本実施形態のマルチキャストツリー計算装置１００における、各リンクのパス長評価値を求める処理を、図６のフローチャートに沿って説明する。なお、この図６の処理は、リンク評価値計算部１０４が図２のステップＡ４において行う処理となる。
【００５５】
図６に示すように、まず、リンクｌの両端のノードをそれぞれｎ１，ｎ２としたときに、それぞれ仮想的な送信元ノードからｎ１，ｎ２までのパス長ｐ（ｎ１），ｐ（ｎ２）を求める（ステップＢ１）。図５の例では、例えば、ノード１３，１４間のリンクをｌとしたときに、ノード１３をｎ１、ノード１４をｎ２とする。このとき、ｐ（ｎ１），ｐ（ｎ２）はそれぞれ１となる。
【００５６】
次に、最短パスツリー上でｎ１，ｎ２から上流側に辿っていったときにたどり着くノードで、すでに冗長マルチキャストツリーに含まれているノードを見つけｎ’１，ｎ’２とする（ステップＢ２）。図５の例では、ｎ１であるノード１３を最短パスツリーに沿って辿ると、仮想的な送信元ノード２１中のノード１２にたどり着く。よって、この場合、ノード１２をｎ’１とする。同様に、ノード１５がｎ’２となる。
【００５７】
次に、冗長ツリー１，２上における、実送信元ノードからノードｎ’１までのパス長をｐ１（ｎ’１），ｐ２（ｎ’１）とする（ステップＢ３）。図５の例では、実送信元ノード１１からｎ’１であるノード１２までのパス長は、ツリー１上で１、ツリー２上で４となるので、これらの値がそれぞれｐ１（ｎ’１），ｐ２（ｎ’１）となる。
【００５８】
次に、ステップＢ３と同様の処理をｎ’２に対しても行い、冗長ツリー１，２上における、実送信元ノードからノードｎ’２までのパス長をｐ１（ｎ’２），ｐ２（ｎ’２）とする（ステップＢ４）。図５の例では、実送信元ノード１１からｎ’２であるノード１５までのパス長は、ツリー１上で２、ツリー２上で３となるので、これらの値がそれぞれｐ１（ｎ’２），ｐ２（ｎ’２）となる。
【００５９】
次に、ｐ１（ｎ’１）＋ｐ２（ｎ’２）の値とｐ１（ｎ’２）＋ｐ２（ｎ’１）の値との比較を行う（ステップＢ５）。図５の例では、リンク１３，１４間のリンクが以降に選択されループが構成されたとすると、ノード１２からノード１３へのパスは、ツリー２ではなくツリー１を延伸する必要がある。一方、ノード１５からノード１４へのパスは、ツリー１ではなくツリー２を延伸する必要がある。これが逆になった場合、ノード１２，１５間のリンクが単一故障点となり、ここが故障するとノード１３や１４はツリー１，２のどちらからもパケットを受け取ることができなくなる。このような状態は、ステップＢ１でのどちらのノードをｎ１とするかに依存してしまう。このような状況を防ぐために、単一故障点が発生するような状況では、発生しない状況に比べて、パス長の和が大きくなることを利用するために、このステップＢ５では実ノードからのパス長の和を比較している。
【００６０】
ステップＢ５において、前者の値の方が小さかった場合、ｐ１（ｎ’１）とｐ２（ｎ’２）のパス長の差をとり、その値をｄとする（ステップＢ６）。図５の例では、それぞれのパス長が１と４なので、ｄの値は３となる。
【００６１】
ステップＢ５において、後者の値の方が大きいか、もしくは同じ値だった場合、ｐ１（ｎ’２）とｐ２（ｎ’１）のパス長の差をとり、その値をｄとする（ステップＢ７）。
【００６２】
最後に、リンクｌのパス長評価値Ｅ（ｌ）をＥ（ｌ）←ｐ（ｎ１）＋ｐ（ｎ２）＋ｄとして求める（ステップＢ８）。図５の例では、ｐ（ｎ１），ｐ（ｎ２），ｄの値が、それぞれ１，１，４であるため、Ｅ（ｌ）は６となる。
【００６３】
このように、第１の実施形態ではｐ（ｎ１），ｐ（ｎ２）の値のみを使用していたが、本実施形態ではｄの値もあわせて使用する点が異なっている。
【００６４】
上述したように本実施形態では、抽出した各リンクについて、仮想的な送信元ノード内に含まれる分のパス長をも考慮して評価を行うため、送信元ノードから各ノードへの２つのパス長の差がなるべく小さくなるループを、より高い精度で発見することができるという効果が得られる。
（付記１）
複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置であって、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、
前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有することを特徴とするマルチキャストツリー計算装置。
（付記２）
前記グループ間リンク抽出部にて抽出された各リンクを基準に従い評価し、その評価結果に基づいて、前記ループを構成する際に使用するリンクを選択するリンク評価値計算部をさらに有することを特徴とする付記１に記載のマルチキャストツリー計算装置。
（付記３）
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パスのパス長を用いることを特徴とする付記２に記載のマルチキャストツリー計算装置。
（付記４）
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端のノードのそれぞれ上流にある各ノードへの各パスのパス長の差も用いることを特徴とする付記３のマルチキャストツリー計算装置。
（付記５）
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パス中に含まれる各リンクのコスト値を用いることを特徴とする付記２に記載のマルチキャストツリー計算装置。
（付記６）
前記リンク評価値計算部は、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パス中に含まれる各リンクのリンク遅延を用いることを特徴とする付記２に記載のマルチキャストツリー計算装置。
（付記７）
送信元ノードから各ノードまでの最短パスツリーを計算する最短パスツリーを計算する最短パスツリー計算部をさらに有し、
前記ノードグルーピング部は、前記最短パスツリー計算部にて計算された最短パスツリーを用いて、前記グループ分けを行うことを特徴とする付記１から６のいずれか１項に記載のマルチキャストツリー計算装置。
（付記８）
前記最短パスツリー計算部は、ダイクストラ法を用いて最短パスツリーを計算することを特徴とする付記７に記載のマルチキャストツリー計算装置。
（付記９）
複数のノードをリンクを介して互いに接続したネットワークシステムにおいて、送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置によるマルチキャストツリー計算方法であって、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うグルーピングステップと、
前記分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するリンク抽出ステップと、を有することを特徴とするマルチキャストツリー計算方法。
（付記１０）
前記抽出された各リンクを基準に従い評価し、その評価結果に基づいて、前記ループを構成する際に使用するリンクを選択するリンク選択ステップをさらに有することを特徴とする付記９に記載のマルチキャストツリー計算方法。
（付記１１）
前記リンク選択ステップでは、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パスのパス長を用いることを特徴とする付記１０に記載のマルチキャストツリー計算方法。
（付記１２）
前記リンク選択ステップでは、リンクを評価する基準として、送信元ノードから、当該リンク両端のノードのそれぞれ上流にある各ノードへの各パスのパス長の差も用いることを特徴とする付記１１のマルチキャストツリー計算方法。
（付記１３）
前記リンク選択ステップでは、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パス中に含まれる各リンクのコスト値を用いることを特徴とする付記１０に記載のマルチキャストツリー計算方法。
（付記１４）
前記リンク選択ステップでは、リンクを評価する基準として、送信元ノードから、当該リンク両端の各ノードへの各パス中に含まれる各リンクのリンク遅延を用いることを特徴とする付記１０に記載のマルチキャストツリー計算方法。
（付記１５）
送信元ノードから各ノードまでの最短パスツリーを計算する最短パスツリーを計算する最短パスツリー計算ステップをさらに有し、
前記グルーピングステップでは、前記計算された最短パスツリーを用いて、前記グループ分けを行うことを特徴とする付記９から１４のいずれか１項に記載のマルチキャストツリー計算方法。
（付記１６）
前記最短パスツリー計算部は、ダイクストラ法を用いて最短パスツリーを計算することを特徴とする付記１５に記載のマルチキャストツリー計算方法。
（付記１７）
リンクを介して互いに接続された複数のノードと、
送信元ノードを基点かつ終点とするループを構成し、該ループの順逆方向にそれぞれパスを構成するという手順を繰り返すことで、前記複数のノードをすべて含む２つのマルチキャストツリーを計算するマルチキャストツリー計算装置と、を有し、
前記マルチキャストツリー計算装置は、
送信元ノードの次転送先ノード毎に、その下流にある各ノードを分類し、グループ分けを行うノードグルーピング部と、
前記ノードグルーピング部にて分類された各グループを用い、リンク両端の各ノードが互いに異なるグループに所属するリンクを、前記ループを構成する際に使用するリンクの候補として抽出するグループ間リンク抽出部と、を有することを特徴とするネットワークシステム。
【産業上の利用可能性】
【００６５】
本発明は、キャリアネットワーク上などに構成するパスを計算する装置などに適用可能である。
【符号の説明】
【００６６】
１１〜２０    ノード
１００    マルチキャストツリー計算装置
１０１    最短パスツリー計算部
１０２    ノードグルーピング部
１０３    グループ間リンク抽出部
１０４    リンク評価値計算部
１０５    ループ構成部
１０６    ツリーパス構成部
１１１    トポロジー情報データベース
１１２    冗長マルチキャストツリー保管部
【図１】
2011166360.tif 000003
【図２】
2011166360.tif 000004
【図３】
2011166360.tif 000005
【図４】
2011166360.tif 000006
【図５】
2011166360.tif 000007
【図６】
2011166360.tif 000008
【図７】
2011166360.tif 000009
【図８Ａ】
2011166360.tif 000010
【図８Ｂ】
2011166360.tif 000011
【図９Ａ】
2011166360.tif 000012
【図９Ｂ】
2011166360.tif 000013