(57)【要約】【課題】  マルチキャスト機能を持つノードと持たないノードが混在する環境でＭＳＴ経路計算を可能にする。【解決手段】  本発明は、記憶手段に格納されているリンクを所定の順に４つに分類し、各リンクの採用優先順位を分類を第１優先順位、コストを第２優先順位とし、採用優先順位が上位のものから採用して、ユニキャストノードの制約を考慮せずに初期ツリーを生成し、ユニキャストキャストノードの制約が満たされないノードＸがあると、ノードＸとリンクＡでつながったツリー上のノードＹに対して、ノードＹを含む未採用のリンクＢでコストが最小のものを選択し、リンクＡをリンクＢに置換し、ツリーを出力する。【選択図】  図１
2006237884.tif 000002
【特許請求の範囲】
【請求項１】
ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための経路計算装置における、最小木経路計算方法であって、
前記経路計算装置は、ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段を備え、
前記トポロジ記憶手段の前記接続関係情報を参照して、前記ノード情報に含まれるリンク集合を、
・両端の装置のいずれかのリンク数が１であるリンク；
・両端の装置がマルチキャスト装置であるリンク；
・両端の装置のいずれかがマルチキャスト装置であるリンク；
・両端の装置がユニキャスト装置であるリンク；
の順に並べ替え、リンクコストと共に前記トポロジ記憶手段の前記接続関係情報に格納するリンクソートステップと、
前記トポロジ記憶手段の前記接続関係情報を参照して、ソートされた順に、ループを構成しないように、該トポロジ記憶手段の前記ツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成ステップと、
前記マルチキャストツリー生成ステップにおいて、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、前記ユニキャスト装置の分岐能力に対して違反を起こしたノードを、前記トポロジ記憶手段の前記エラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の前記候補リストに格納する強制的マルチキャストツリー生成ステップと、
前記強制的マルチキャストツリー生成ステップにおいて、マルチキャストツリー生成後、前記エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、前記候補リストから、起点と終点が繋がった状態を維持可能で、かつ、前記エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、前記マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、持たない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、前記ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理ステップと、
を行うことを特徴とする最小木経路計算方法。
【請求項２】
ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための経路計算装置における、最小木経路計算方法であって、
前記経路計算装置は、ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段を備え、
前記トポロジ記憶手段の前記接続関係情報を参照して、前記ノード情報に含まれるリンク集合を、リンクコストの順番に並べ替え、リンクコストと共に前記トポロジ記憶手段の前記接続関係情報に格納するリンクソートステップと、
前記トポロジ記憶手段の前記接続関係情報を参照して、リンクコストの小さい順に、ループを構成しないように、該トポロジ記憶手段の前記ツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成ステップと、
前記マルチキャストツリー生成ステップにおいて、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、前記ユニキャスト装置の分岐能力に対して違反を起こしたノードを、前記トポロジ記憶手段の前記エラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の前記候補リストに格納する強制的マルチキャストツリー生成ステップと、
前記強制的マルチキャストツリー生成ステップにおいて、マルチキャストツリー生成後、前記エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、前記候補リストから、起点と終点が繋がった状態を維持可能で、かつ、前記エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、前記マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こさない場合は、前記ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理ステップと、
を行うことを特徴とする最小木経路計算方法。
【請求項３】
ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための最小木経路計算装置であって、
ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段と、
前記トポロジ記憶手段の前記接続関係情報を参照して、前記ノード情報に含まれるリンク集合を、
・両端の装置のいずれかのリンク数が１であるリンク；
・両端の装置がマルチキャスト装置であるリンク；
・両端の装置のいずれかがマルチキャスト装置であるリンク；
・両端の装置がユニキャスト装置であるリンク；
の順に並べ替え、リンクコストと共に前記トポロジ記憶手段の前記接続関係情報に格納するリンクソート手段と、
前記トポロジ記憶手段の前記接続関係情報を参照して、ソートされた順に、ループを構成しないように、該トポロジ記憶手段の前記ツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成手段と、
前記マルチキャストツリー生成手段において、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、前記ユニキャスト装置の分岐能力に対して違反を起こしたノードを、前記トポロジ記憶手段の前記エラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の前記候補リストに格納する強制的マルチキャストツリー生成手段と、
前記強制的マルチキャストツリー生成手段において、マルチキャストツリー生成後、前記エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、前記候補リストから、起点と終点が繋がった状態を維持可能で、かつ、前記エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、前記マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、前記ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理手段と、
を有することを特徴とする最小木経路計算装置。
【請求項４】
ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための最小木経路計算装置であって、
ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段と、
前記トポロジ記憶手段の前記接続関係情報を参照して、前記ノード情報に含まれるリンク集合を、リンクコストの順番に並べ替え、リンクコストと共に前記トポロジ記憶手段の前記接続関係情報に格納するリンクソート手段と、
前記トポロジ記憶手段の前記接続関係情報を参照して、リンクコストが小さい順に、ループを構成しないように、該トポロジ記憶手段の前記ツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成手段と、
前記マルチキャストツリー生成手段において、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、前記ユニキャスト装置の分岐能力に対して違反を起こしたノードを、前記トポロジ記憶手段の前記エラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の前記候補リストに格納する強制的マルチキャストツリー生成手段と、
前記強制的マルチキャストツリー生成手段において、マルチキャストツリー生成後、前記エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、前記候補リストから、起点と終点が繋がった状態を維持可能で、かつ、前記エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、前記マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、前記ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理手段と、
を有することを特徴とする最小木経路計算装置。
【請求項５】
ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための最小木経路計算プログラムであって、
ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段を備えるコンピュータ上で、
前記請求項１または、２記載の最小木経路計算方法を実現するための処理を実行させることを特徴とする最小木経路計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最小木経路計算方法及び装置及びプログラムに係り、特に、ネットワーク上でのＭＳＴ経路計算を実行する最小木経路計算方法及び装置及びプログラムに係り、特に、マルチキャストノードとユニキャストノードが混在するときの最小木経路計算方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
従来のＭＳＴ経路計算を実施する場合、最短木に対するKruskalのアルゴリズムを用いて、最小全域木を決定する方法があるが、ネットワーク上の全てのノードに対してマルチキャスト機能を持たせる必要がある（例えば、非特許文献１参照）。
【非特許文献１】Ｅ．クライツィグ、“最適化とグラフ理論”、培風館、pp．４４−４８、2003年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記の従来の方式を使用した場合、ネットワーク上の全てのノードに対してマルチキャスト機能を持たせる必要がある。
【０００４】
本発明は、上記の点に鑑みなされたもので、マルチキャスト機能を持つノードと持たないノードが混在する環境でＭＳＴ経路計算可能な最小木経路計算方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
図１は、本発明の原理を説明するための図である。
【０００６】
本発明（請求項１）は、ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための経路計算装置における、最小木経路計算方法であって、
経路計算装置は、ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段を備え、
トポロジ記憶手段の接続関係情報を参照して、ノード情報に含まれるリンク集合を、
・両端の装置のいずれかのリンク数が１であるリンク；
・両端の装置がマルチキャスト装置であるリンク；
・両端の装置のいずれかがマルチキャスト装置であるリンク；
・両端の装置がユニキャスト装置であるリンク；
の順に並べ替え、リンクコストと共にトポロジ記憶手段の接続関係情報に格納するリンクソートステップ（ステップ１）と、
トポロジ記憶手段の接続関係情報を参照して、ソートされた順に、ループを構成しないように、該トポロジ記憶手段のツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成ステップ（ステップ２）と、
マルチキャストツリー生成ステップにおいて、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、ユニキャスト装置の分岐能力に対して違反を起こしたノードを、トポロジ記憶手段のエラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の候補リストに格納する強制的マルチキャストツリー生成ステップ（ステップ３）と、
強制的マルチキャストツリー生成ステップ（ステップ３）において、マルチキャストツリー生成後、エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、候補リストから、起点と終点が繋がった状態を維持可能で、かつ、エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理ステップ（ステップ４）と、を行う。
【０００７】
本発明（請求項２）は、ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための経路計算装置における、最小木経路計算方法であって、
経路計算装置は、ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段を備え、
トポロジ記憶手段の接続関係情報を参照して、ノード情報に含まれるリンク集合を、リンクコストの順番に並べ替え、リンクコストと共にトポロジ記憶手段の接続関係情報に格納するリンクソートステップと、
トポロジ記憶手段の接続関係情報を参照して、リンクコストが小さい順に、ループを構成しないように、該トポロジ記憶手段のツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成ステップと、
マルチキャストツリー生成ステップにおいて、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、ユニキャスト装置の分岐能力に対して違反を起こしたノードを、トポロジ記憶手段のエラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の候補リストに格納する強制的マルチキャストツリー生成ステップと、
強制的マルチキャストツリー生成ステップにおいて、マルチキャストツリー生成後、エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、候補リストから、起点と終点が繋がった状態を維持可能で、かつ、エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理ステップと、を行う。
【０００８】
図２は、本発明の原理構成図である。
【０００９】
本発明（請求項３）は、ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための最小木経路計算装置であって、
ノード情報２１１、接続関係情報２１２、ツリー情報２１３、分岐能力に対して違反を起こした分岐違反のエラーノードの情報２１４１、該ツリーに用いられなかったリンクの情報である候補リスト２１４２を保持するトポロジ記憶手段２１０と、
トポロジ記憶手段２１０の接続関係情報２１２を参照して、ノード情報に含まれるリンク集合を、
・両端の装置のいずれかのリンク数が１であるリンク；
・両端の装置がマルチキャスト装置であるリンク；
・両端の装置のいずれかがマルチキャスト装置であるリンク；
・両端の装置がユニキャスト装置であるリンク；
の順に並べ替え、リンクコストと共にトポロジ記憶手段２１０の接続関係情報２１２に格納するリンクソート手段１２０と、
トポロジ記憶手段２１０の接続関係情報２１２を参照して、リンクコストが小さい順に、ループを構成しないように、該トポロジ記憶手段２１０のツリー情報２１３のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成手段１３０と、
マルチキャストツリー生成手段１３０において、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、ユニキャスト装置の分岐能力に対して違反を起こしたノードを、トポロジ記憶手段２１０のエラーノードの情報２１４１に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段２１０の候補リスト２１４２に格納する強制的マルチキャストツリー生成手段１４０と、
強制的マルチキャストツリー生成手段１４０において、マルチキャストツリー生成後、エラーノードの情報２１４１を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、候補リスト２１４２から、起点と終点が繋がった状態を維持可能で、かつ、エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理手段１５０と、を有する。
【００１０】
本発明（請求項４）は、ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための最小木経路計算装置であって、
ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段と、
トポロジ記憶手段の接続関係情報を参照して、ノード情報に含まれるリンク集合を、リンクコストの順番に並べ替え、リンクコストと共にトポロジ記憶手段の接続関係情報に格納するリンクソート手段と、
トポロジ記憶手段の接続関係情報を参照して、リンクコストが小さい順に、ループを構成しないように、該トポロジ記憶手段のツリー情報のマルチキャストツリーに追加し、かつ、ユニキャスト装置でツリーを分岐させないように該マルチキャストツリーに追加するマルチキャストツリー生成手段と、
マルチキャストツリー生成手段において、１つの起点となる装置と複数の終点となる装置を結ぶことができない場合は、ユニキャスト装置でツリーを分岐させない制約を解除し、１つの起点となる装置と複数の終点となる装置を結ぶことを優先的に処理し、ユニキャスト装置の分岐能力に対して違反を起こしたノードを、トポロジ記憶手段のエラーノードの情報に格納し、マルチキャストツリーの生成に用いられなかったリンクを該トポロジ記憶手段の候補リストに格納する強制的マルチキャストツリー生成手段と、
強制的マルチキャストツリー生成手段において、マルチキャストツリー生成後、エラーノードの情報を参照して、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合に対して、候補リストから、起点と終点が繋がった状態を維持可能で、かつ、エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードを確認し、当該対向エッジノードの持つ物理リンクから、マルチキャストツリーに含まれないリンク集合を持つかどうか確認を行い、もたない場合は１ホップ先の対向エッジノードを確認し、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し、持つ場合は、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い、
起こさない場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、起こす場合は、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し、起こす場合は、ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し、
起こす場合は、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換するDegree回避処理手段と、を有する。
【００１１】
本発明（請求項５）は、ツリーを分岐可能な機能を有するマルチキャスト装置と、ツリーを分岐不可能な機能を有するユニキャスト装置が混在し、各装置が接続関係情報やコスト情報を有するネットワークにおいて、１つの起点となる装置と複数の終点となる装置を結ぶマルチキャストツリーを生成するための最小木経路計算プログラムであって、
ノード情報、接続関係情報、ツリー情報、分岐能力に対して違反を起こした分岐違反のエラーノードの情報、該ツリーに用いられなかったリンクの情報である候補リストを保持するトポロジ記憶手段を備えるコンピュータ上で、
請求項１または、２記載の最小木経路計算方法を実現するための処理を実行させるプログラムである。
【発明の効果】
【００１２】
上記のように本発明によれば、マルチキャスト機能を持つノードと持たないノードが混在する環境において、ＭＳＴ生成時にP2MPノードがツリーの分岐ポイントになるように優先的に追加する処理を行うことにより、混在環境での動作を実現可能にし、かつ、優先的に追加することで、できるだけエラー回避処理を実施しないでＭＳＴを完成させ、アルゴリズム全体の処理を削減することができる。
【００１３】
また、ＭＳＴ生成時にノードのツリー分岐能力により、リンク追加が不可となった場合に、既に接続されているリンクとの交換により、ノード分岐能力に応じたＭＳＴを再生成するエラー回避処理を行うことで、混在環境での動作を実現可能にし、かつ、全てのP2MPノード環境で計算されるＭＳＴに近いツリーを計算可能にする。
【発明を実施するための最良の形態】
【００１４】
以下、図面と共に本発明の実施の形態を説明する。
【００１５】
最初に以下の説明で用いられる用語について定義する。
【００１６】
・ＭＳＴ(Minimum Spanning Tree)：
ネットワーク上の全てのノードを結ぶリンクでリンクコストが最小になる“リンクコスト最小の全域木”を最小木と呼ぶ。Kruskalアルゴリズムは、リンク集合をリンクコストの順番に並び替え、小さいリンクから順にループを構成しないようにツリーに追加していくことでＭＳＴを計算する。
【００１７】
・Ｐ２ＭＰノード(Point to Multipoint ノード)：
1対多のマルチキャストＬＳＰを設定可能なＭＰＬＳノードである。
【００１８】
・Ｐ２Ｐノード（Point to Point ノード）：
1対1のユニキャストｋｙストＬＳＰのみを設定可能なＭＰＬＳノードである。
【００１９】
・Sub-Graph ＩＤ（SG ID）：
各ノードのサブツリー情報を示す識別子。ツリー形成前は、全てのノードに異なるSG_IDが割り当てられており、リンクが追加される毎に、SG_IDをマージする。例えば、ノードＡとノードＢのSG_IDが同一値であれば、それは同一サブツリー上に存在することを意味する。そして、ＭＳＴ完成時に全てのSG_IDが同一値になる。
【００２０】
・Degree value(DV)：
各ノードのマルチキャスト分岐能力を示す識別子。例えば、Ｐ２Ｐノードでかつ、物理リンク数が1の場合、ＤＶ＝１となる。また、Ｐ２Ｐノードでかつ物理リンク数が２以上の場合、ＤＶ＝２となる。これはＰ２Ｐノードがマルチキャスト分岐能力を持たないので、物理リンク数が２以上でも能力値２を越えることはない。また、Ｐ２ＭＰノードでかつ、物理リンク数がＸ（Ｘ≧１）の場合、ＤＸ＝Ｘ，つまり物理接続リンク数が能力値となる。
【００２１】
・TO ADJUST list：
強制的にＭＳＴを生成したときにDegree errorを引き起こしたノードを格納するリストを意味する。ここで、“Degree error”とは、ＤＶを違反したノード（P2PノードのDegree value＞２）のことを意味する。たとえば、Ｐ２ＰノードＡがDegree errorを引き起こし、そのノードがエラーとなっているリンクを３つ（リンクＡＢ、リンクＡＣとリンクＡＤだったとする）持つならば、TO_ADJUST listは、A{B1,C1,D1}のように格納する。ここで１は、ホップ先のリンクとして定義されているが、もし、Degree errorを引き起こしているノードはｋホップ先のリンクを表示する場合（リンクA-x-x-B、リンクA-x-x-CとリンクA-x-xDで、AからＢ，Ｃ，Ｄまでｋホップだったとする。）、A{Bk,Ck,Dk}のように格納する。
【００２２】
・TO TEST list：
強制的にＭＳＴを生成するステップにおいて、ＭＳＴに使用されなかったリンクを格納するためのリストを意味する。ここでは、使用されないことが確認された順に格納する。
【００２３】
・TO TEST2 list：
Degree違反の回避ステップにおいて、“TO_TEST list”のリンクと交換されたDegree違反リンクを格納するためのリストを意味する。ここでは、ＭＳＴのリンクが交換された順に格納する。
【００２４】
［第１の実施の形態］
図３は、本発明の第１の実施の形態における経路計算装置の構成図である。
【００２５】
同図に示す経路計算装置２０は、経路計算制御部１００と記憶領域２００から構成される。
【００２６】
経路計算制御部１００は、初期設定部１１０、リンクソート部１２０、ＭＳＴ生成部１３０、強制的ＭＳＴ生成部１４０、Degree回避処理部１５０、及びツリー完成部１６０から構成される。
【００２７】
記憶領域２００は、トポロジ記憶部２１０を有し、当該トポロジ記憶部２１０には、ノード情報２１１、接続関係情報２１２、ツリー情報２１３、Degreeエラー回避情報２１４が格納されている。ノード情報２１１、接続関係情報２１２は、入力部10から入力されたものが設定される。
【００２８】
トポロジ記憶部２１０のノード情報２１１は、ノード識別子、始点・終点識別子、ノードのDegree識別子、ノードのグループ識別子を有する。
【００２９】
接続関係情報２１２は、リンク識別子、リンクコスト識別子、リンクソート識別子を有する。
【００３０】
ツリー情報２１３は、ＭＳＴ生成部１３０により生成されたＭＳＴ、及び強制的なＭＳＴ生成部１４０により追加されたＭＳＴを格納する。
【００３１】
Degreeエラー回避情報２１４は、エラーノードを管理するためのTO_ADJUST list（エラーノード管理部）と、TO_TEST list（候補リスト管理部）を有する。
【００３２】
入力部１０は、ネットワーク上の全ノードに異なるSG_IDを割り当て、各ノードの物理接続リンク数をP2P/P2MP能力を確認し、各ノードのDVを付与し、これらをトポロジ記憶部２１０に格納する。また、ネットワークのノード識別子、始点ノード／終点ノードの識別子をトポロジ記憶部２１０のノード情報２１１に格納する。また、各ノードの接続関係情報として、各リンク毎のリンク識別子、リンクコスト識別子をトポロジ記憶部210の接続関係情報２１２に格納する。
【００３３】
初期設定部１１０は、トポロジ記憶部２１０のノード情報２１１から、ノードのDegree識別子及びノードのグループ識別子を生成してノード情報２１１の領域に設定する。
【００３４】
リンクソート部１２０は、トポロジ記憶部２１０の接続関係情報２１２のリンク識別子及びリンクコスト識別子からリンクソート識別子を決定付ける。具体的には、ネットワーク上の全てのリンクを、
（１）両端の装置のいずれかのリンク数が1であるリンク；
（２）両端の装置がマルチキャスト装置であるリンク；
（３）両端の装置のいずれかがマルチキャスト装置であるリンク；
（４）両端の装置がユニキャストキャスト装置であるリンク；
の順に並べ替え、リンクソート識別子を付与してトポロジ記憶部２１０の接続関係情報２１２の領域に格納する。
【００３５】
ＭＳＴ生成部１３０は、トポロジ記憶部２１０の接続関係情報のリンク識別子、リンクコスト識別子、リンクソート識別子からツリー情報を決定付け、トポロジ記憶部２１０のツリー情報の領域に格納する。このとき、ソートされた順にループを構成しないように、トポロジ記憶部２１０のツリー情報２１３にマルチキャストツリーを追加し、かつユニキャスト装置でツリーを分岐させないようにリンクを追加する。
【００３６】
強制的ＭＳＴ生成部１４０は、ＭＳＴ生成部１３０においてＭＳＴ生成が完了しない場合に、ツリー情報２１３に追加されなかったリンクを、リンクコスト順に、ユニキャスト装置でツリーを分岐させない制約を解除し、再度ＭＳＴを生成し、ツリー情報２１３の領域に追加する。また、ツリー作成後、ユニキャスト装置の分岐能力に対して違反を起こしたものをエラーノードとしてトポロジ記憶部２１０のDegreeエラー回避情報２１４の領域に格納する。
【００３７】
Degree回避処理部１５０は、トポロジ記憶部２１０のDegreeエラー回避情報２１４のエラーノード管理部を参照して、ユニキャストキャストの分岐能力に対して違反を起こしたリンクに対して、候補リスト管理部のツリーで用いなかった残りのリンクから、起点と終点が繋がった状態を維持可能で、かつ、ユニキャスト装置の分岐違反を回避できるリンクと置換し、トポロジ記憶部２１０のツリー情報２１３に格納する。
【００３８】
ツリー完成部１６０は、トポロジ記憶部２１０のノード情報２１１の始点／終点識別子を参照して、ツリー情報２１３に格納されているツリー情報の中からツリー形成に不要となるリンクを削除し、ツリーを完成させ、出力部３０に出力する。
【００３９】
図４は、本発明の第１の実施の形態における経路計算方法のフローチャートである。
【００４０】
ステップ１０１）  初期設定：
初期設定部１１０は、ネットワーク上の全ノードに異なるSG_IDを割り当てる。また、各ノードの物理接続リンク数とP2P/P2MP能力を確認し、各ノードのDVを付与して、トポロジ記憶部２１０のノード情報２１１に設定する。
【００４１】
ここで、図５を用いて説明すると、入力部１０から、このネットワークについて、起点ノードをＣ、終点ノードをＢ，Ｋ，Ｍ，Ｇ，Ｉ，Ｏ，Ｑ，Ｒとし、トポロジ記憶部２１０のノード情報２１１の始点／終点識別子として設定し、各ノードの接続関係と各リンクコストを図のようにトポロジ記憶部２１０の接続関係情報２１２に設定する。
【００４２】
まず、ノードＡ〜Ｒまで、全ての異なるSG_IDを割り当てる。また、各ノードの物理接続リンク数とP2P/P2MP能力を確認すると、Ｒはエッジノートのため、ＤＶ＝１となる。
【００４３】
ノードＡ，Ｄ，Ｅ，Ｆ，Ｈ，Ｊ，Ｌ，Ｎ，ＰはP2Pノードでトランジットノードであるため、ＤＶ＝２となる。
【００４４】
ノードＣ，Ｇ，Ｍ，Ｏは、P2MPノードで物理接続リンクが“２”のためＤＶ＝２となる。
【００４５】
ノードＢ，Ｉ，Ｋ，Ｑは、P2MPノードで物理接続リンクが“３”のためＤＶ＝３となる。
【００４６】
よって、各ＤＶは、
Ａ：２，
Ｂ：３，
Ｃ：２，
Ｄ：２，
Ｅ：２，
Ｆ：２，
Ｇ：２，
Ｈ：２，
Ｉ：３，
Ｊ：２，
Ｋ：３，
Ｌ：２，
Ｍ：２，
Ｎ：２，
Ｏ：２，
Ｐ：２，
Ｑ：３，
Ｒ：１
となる。これらを、トポロジ記憶部２１０のノード情報２１１に格納する。
【００４７】
ステップ１０２）  リンクソート：
リンクソート部１２０において、トポロジ記憶部２１０の接続関係情報２１２のリンク識別子及びリンクコスト識別子を用いて、リンクネットワーク上の全てのリンクを以下の４つに分類し、分類１，２，３，４の順にソートし、トポロジ記憶部２１０の接続関係情報２１２のリンクソート識別子として格納する。分類方法を以下に示す。
【００４８】
分類１：両端のノードの接続リンク数のいずれかが１であるリンク；
分類２：両端のノードの接続リンク数が２以上でかつ、両端がP2MPノードになっているリンク；
分類３：両端のノードの接続リンク数が２以上でかつ、両端がP2MPノードとP2Pノードになっているリンク；
分類４：両端のノードの接続リンク数が２以上でかつ、両端がP2Pノードになっているリンク；
また、各分類内は、リンクコスト順にソートする。
【００４９】
ここで、図６を用いて説明すると、
分類１のリンクソート識別子は、
Ｒ−Ｊ（１０）、
となり、
分類２は、
Ｂ−Ｋ（６），
Ｑ−Ｉ（７）
となり、
分類３のリンクソート識別子は、
Ｂ−Ｄ（２），
Ｋ−Ｊ（３），
Ｇ−Ｆ（２），
Ｏ−Ｎ（２），
Ｃ−Ｄ（３），
Ｍ−Ｊ（３），
Ｉ−Ｆ（３），
Ｑ−Ｎ（３），
Ｂ−Ａ（４），
Ｋ−Ｌ（４），
Ｇ−Ｈ（４），
Ｏ−Ｐ（４），
Ｃ−Ａ（５），
Ｍ−Ｌ（５），
Ｉ−Ｈ（５），
Ｑ−Ｐ（５）
となり、
分類４のリンクソート識別子は、
Ｊ−Ｅ（６），
Ｆ−Ｅ（７），
Ｎ−Ｅ（８），
Ｄ−Ｅ（９）
となる。
【００５０】
ここで（）内の数値はコストを示す。これを各分類でコスト順に並べて格納する。
【００５１】
ステップ１０３）拡張クラスカルアルゴリズムによるＭＳＴ生成；
ＭＳＴ生成部１３０は、トポロジ記憶部２１０の接続関係情報２１２のリンク識別子、リンクコスト識別子、リンクソート識別子を取得し、リンクコスト順にループを構成しないようにツリーにリンクを追加し、ＭＳＴを生成し、トポロジ記憶部２１０のツリー情報２１３に格納する。このとき、追加されたリンクの両エッジを構成するノードがP2Pの場合には、P2PのノードDegreeがDegree≦２となる場合にのみツリー情報２１３へのリンク追加を許容する。また、ＭＳＴ生成部１３０は、ＭＳＴ生成時に追加されたエッジのSG_IDをチェックし、SG_IDが全てチェックされた場合、処理を中断する。この時、全てのSG_IDが同一値になれば、ＭＳＴ生成が完了し、後述するステップ１０７の処理を行い、ツリーが完成する。また、リンクを構成するエッジがソース・リーフノードに該当する場合には、ソース・リーフのSG_IDをチェックし、この時、ソースと全てのリーフノードのSG_IDが同一値になればＭＳＴ生成を完了し、ステップ１０７の処理を行いツリーが完成する。
【００５２】
ここで、図７を用いて説明すると、
Ｒ−Ｊ（１０），
Ｂ−Ｋ（６），
Ｂ−Ｄ（２），
Ｋ−Ｊ（２），
Ｇ−Ｆ（２），
Ｏ−Ｎ（２），
Ｃ−Ｄ（３）
の順にツリー情報２１３のＭＳＴに追加していく。
【００５３】
次に、Ｍ−Ｊ（３）を追加するとき、ノードＪでDegree違反を起こしてしまうためＭＳＴに追加しない。
【００５４】
次に、
Ｉ−Ｆ（３），
Ｑ−Ｎ（３），
Ｂ−Ａ（４），
Ｋ−Ｌ（４），
Ｇ−Ｈ（４），
Ｏ−Ｐ（４）
の順にツリー情報２１３のＭＳＴに追加していく。
【００５５】
次に、Ｃ−Ａ（５）を追加するとき、Ａ−Ｂ−Ｃ−Ｄでループを発生してしまうため、ＭＳＴに追加しない。
【００５６】
次に、Ｍ−Ｌ（５）をツリー情報２１３のＭＳＴに追加し、
次に、Ｉ−Ｈ（５），Ｑ−Ｐ（５）を追加するとき、Ｆ−Ｇ−Ｈ−Ｉ、Ｏ−Ｐ−Ｑ−Ｎでそれぞれループを発生してしまうため、ＭＳＴに追加しない。
【００５７】
次に、Ｊ−Ｅ（６），Ｆ−Ｅ（７），Ｎ−Ｅ（８），Ｄ−Ｅ（９）を追加するとき、ノードＪ，Ｆ，Ｎ，ＤでそれぞれDegree違反を起こしてしまうため、ＭＳＴに追加しない。
【００５８】
ステップ１０４）  強制的ＭＳＴ生成部１４０は、トポロジ記憶部２１０のツリー情報２１３及び、接続関係情報２１２を参照し、ステップ１０３の処理によりＭＳＴが完了したかを判定し、完了した場合には、ステップ１０７に移行し、完了しない場合にはステップ１０５に移行する。
【００５９】
ステップ１０５）  強制的なＭＳＴの生成；
強制的ＭＳＴ生成部１４０は、ＭＳＴに追加されなかったリンクをリンクコスト順にP2PノードDegree判定条件を解除し、（Degree≧３）再度ＭＳＴを生成する。全てのノードが１つのＭＳＴに追加された場合は処理を終了する。
【００６０】
ここで、図８を用いて説明すると、Ｍ−Ｊ（３），Ｃ−Ａ（５），Ｑ−Ｐ（５），Ｊ−Ｅ（６），Ｆ−Ｅ（７），Ｎ−Ｅ（８），Ｄ−Ｅ（９）の順に強制的にＭＳＴをツリー情報２１３に追加していくが、まず、Ｍ−Ｊ（３），Ｃ−Ａ（５），Ｉ−Ｈ（５），Ｑ−Ｐ（５）を追加するとき、
Ｍ−Ｌ−Ｋ−Ｊ，
Ａ−Ｂ−Ｃ−Ｄ，
Ｆ−Ｇ−Ｈ−Ｉ，
Ｏ−Ｐ−Ｑ−Ｎ
でそれぞれループを発生してしまうため、ツリー情報２１３のＭＳＴに追加しない。
【００６１】
次に、Ｊ−Ｅ（６），Ｆ−Ｅ（７）をツリー情報２１３に追加する。
【００６２】
これでＭＳＴが完成したので強制的なＭＳＴの生成を終了する。
【００６３】
ステップ１０６）  Degree違反の回避処理：
図９は、本発明の第１の実施の形態におけるDegree違反の回避ステップのフローチャートである。同図においてＥ’は、上記のTO_TEST listに対応し、Ｆは上記のTO_TEST2 listに対応する。
【００６４】
強制的ＭＳＴ生成処理（ステップ１０５）において、マルチキャストツリー生成後、Degree回避処理部１５０は、エラーノードの情報を参照して（ステップ２０１）、ユニキャスト装置の分岐能力に対して違反を起こしたノード集合Ｖに対して（ステップ２０２）、候補リストから、起点と終点が繋がった状態を維持可能で、かつ、エラーノード集合をノード情報の値の小さいものから順に、エラーを起こしているリンク集合の１ホップ先の対向エッジノードＶ’を確認し（ステップ２０３）、当該対向エッジノードの持つ物理リンクから、マルチキャストツリーに含まれないリンク集合Ｅ’を持つかどうか確認を行う（ステップ２０４）。持たない場合は１ホップ先の対向エッジノードを確認し（ステップ２０６）、当該確認処理を実施し、ネットワーク上に存在するノード数から１を引いた数まで当該確認処理を実施し（ステップ２０４〜２０８）、持つ場合は（ステップ２０７、Ｎｏ）、当該リンク集合からリンクコストの小さいものから順に、当該リンクの対向エッジノードを確認し、当該対向エッジノードが、当該リンクを追加することによって分岐能力を違反するかどうか確認を行い（ステップ２０９）、起こさない場合は（ステップ２１０、Ｎｏ）、当該リンクを当該マルチキャストツリーに追加し（ステップ２１１）、当該エラーを起こしていたリンクを削除し（ステップ２１２）、起こす場合は（ステップ２１０、Ｙｅｓ）、当該リンク集合からリンクコストの２番目に小さい物を確認し、当該リンク集合からリンクコストの一番大きいものまで確認し（ステップ２１３）、起こす場合は（ステップ２１４、Ｙｅｓ）、ノード集合からノード情報の値の２番目に小さいものから順に、確認を行い、当該ノード集合からノード情報の値の一番大きいものまで確認し（ステップ２１７〜２２１）、起さない場合は（ステップ２１４、Ｎｏ）、当該リンクを当該マルチキャストツリーに追加し、当該エラーを起こしていたリンクを削除し（ステップ２１５）、当該リンクを追加することで新たにエラーを起こしたノードをエラーノード集合に格納し（ステップ２１６）、エラーノード集合がなくなるまで続ける、当該ユニキャスト装置の分岐違反を回避できるリンクと置換する。
【００６５】
以下に、具体的に説明する。
【００６６】
Degree回避処理部１５０は、ステップ１０４で違反を起こしたノードとそれに対向する１ホップ先のノード情報をDegreeエラー回避情報２１４のTO_ADJUST list（エラーノード管理部）に格納する。また、ＭＳＴに組み込まれなかった残りのリンクをDegreeエラー回避情報２１４のTO_TEST list（候補リスト管理部）を順にチェックし、対向ノードをエッジに含むリンクがあれば、ツリー情報２１３のＭＳＴにそのリンクを追加し、Degree違反を起こしたノードと対向ノードを結ぶリンクをツリー情報２１３のＭＳＴから外すことで、Degreeエラーを回避することができないか確認を行う。最初は、P2PのDegree判定条件をDegree≦２で確認を行い、回避可能であれば、ツリー情報２１３のＭＳＴにリンクを追加する。そして、ＭＳＴから外れたリンクは、Degreeエラー回避情報２１４のTO_TEST listに格納する。これをDegreeエラー回避情報２１４のTO_ADJUST listに含まれる全てのノードに対して実施する。
【００６７】
ここで、図１０を用いて上記の動作を説明する。
【００６８】
Degreeエラー回避情報２１４のTO_ADJUST listとDegreeエラー回避情報２１４のTO_TEST listは下記の通りになり、
TO_ADJUST= J{E1,K1,R1}    F{E1,G1,I1}
TO_TEST= J-M(3)C-A(5)I-H(5)Q-P(5)N-E(8)D-E(9)
Degree違反を起こしているノードＦのリンクＦ−Ｉと交換可能なリンクがTO_TEST listに存在し、Ｉ−Ｈ（５）によって回避可能であることが確認されたため、Ｆ−Ｉをツリー情報２１３のＭＳＴから削除し、TO_TEST listからＩ−Ｈを削除し、TO-TEST2 listにＦ−Ｉを追加する。
【００６９】
Degree判定条件Degree≦２で確認後、まだ、Degreeエラー回避情報２１４のTO_ADJUST listにノードが残っている場合は、リンク接続時に実施していたP2PのDegree判定条件を解除し（Degree≧３）、TO_TEST listを順にチェックし、対向ノードをエッジに含むリンクがあれば、ツリー情報２１３のＭＳＴにそのリンクを追加し、Degree違反を起こしたノードと対向ノードを結ぶリンクをツリー情報２１３のＭＳＴから外すことでDegreeエラーを回避することができないか確認を行う。回避可能であれば、ＭＳＴにリンクを追加する。そして、ＭＳＴから外れたリンクはTO_TEST2 listに格納する。これをTO_ADJUST listに含まれる全てのノードに対して実施する。そのとき、新たにDegreeエラーを引き起こしてしまったノードは、Degreeエラー回避情報２１４のTO_ADJUST listに追加する。
【００７０】
ここで、図１１を用いて新たにDegreeエラーを起こしたノードについて説明すると、TO_ADJUST listとTO_TEST list、TO_TEST2 listは、下記の通りになり、
TO_ADJUST= J{E1,K1,R1}
TO_TEST=J-M(3)C-A(5)Q-P(5)N-E(8)D-E(9)
TO_TEST2=F-I(3)
Degree違反を起こしているノードＪのリンクＪ−Ｅと交換可能なリンクがTO_TEST listに存在し、Ｄ−Ｅ（９）によって回避可能であることが確認されたため、Ｊ−Ｅをツリー情報２１３のＭＳＴから削除し、Ｄ−ＥをＭＳＴに追加する。そして、TO_ADJUST listからＪを削除し、新たにノードＤがDegree違反を起こしたため、TO_ADJUST listにノードＤを追加し、TO_TEST listからＤ−Ｅを削除し、TO_TEST2 listにＪ−Ｅを追加する。
【００７１】
次に、上記のステップで新たにTO_ADUST listに追加されたノードについて、TO_TEST list、TO_TEST2 listを順にチェックし、対向ノードをエッジに含むリンクがあれば、ＭＳＴにそのリンクを追加し、Degree違反を起こしたノードと対向ノードを結ぶリンクをＭＳＴから外すことで、Degreeエラーを回避することができないか確認を行う。この時は、P2PのDegree判定条件をDegree≧２で確認を行い、回避可能であればツリー情報２１３のＭＳＴにリンクを追加する。そしてＭＳＴから外れたリンクはTO_TEST2 listに格納する。これを新たにTO_ADUST listに含まれた全てのノードに対して実施する。
【００７２】
ここで、図１２を用いて説明すると、Degreeエラー回避情報２１４のTO_ADUST listとTO_TEST list、TO_TEST2 listは、下記の通りになり、
TO_ADJUST= D{B1,C1,E1}
TO_TEST= J-M(3)C-A(5)Q-P(5)N-E(8)
TO_TEST2=F-I(3)J-E(6)
Degree違反を起こしているノードＤのリンクＤ−Ｃと交換可能なリンクがTO_TEST listに存在し、Ｃ−Ａ（５）によって回避可能であることが確認されたため、リンクＤ−Ｃをツリー情報２１３のＭＳＴから削除し、Ｃ−ＡをＭＳＴに追加する。そして、Degreeエラー回避情報２１４のTO_ADUST listからＤを削除し、TO_TEST2 listにＣ−Ｄを追加する。
【００７３】
対向する１ホップ先のノードと接続されるリンクとの交換でDegreeエラーの回避を確認後、まだ、Degreeエラー回避情報２１４のTO_ADUST listにノードが残っている場合は、Degree違反を起こしたノードとそれに対向する２ホップ先のノード情報をTO_ADUST listに格納し直し、上記のステップで格納されたTO_TEST list、TO_TEST2 listを用いて実施する。
【００７４】
まずは、TO_TEST listを順にチェックし、対向ノードをエッジに含むリンクがあれば、ツリー情報２１３のＭＳＴにそのリンクを追加し、Degree違反を起こしたノードの２ホップ先の対向ノードと、その１ホップ前のノードを結ぶリンクをツリー情報２１３のＭＳＴから削除することで、Degreeエラーを回避することができないか確認を行う。最初はP2PのDegree判定条件をDegree≦２で確認を行い、回避可能であればツリー情報２１３のＭＳＴにリンクを追加する。そして、ＭＳＴから外れたリンクはTO_TEST2 listに格納する。これをTO_ADUST listに含まれる全てのノードに対して実施する。
【００７５】
まだ、Degreeエラー回避情報２１４のTO_ADUST listにノードが残っている場合は、P2PのDegree判定条件を解除し（Degree≧３）、TO_TEST listを順にチェックし、Degreeエラーを回避することができないか確認を行う。
【００７６】
上記のステップで新たにTO_ADUST listに追加されたノードについて、P2PのDegree判定条件をDegree≦２でTO_TEST list、TO_TEST2 listを順にチェックし、Degreeエラーを回避することができないか確認を行う。
【００７７】
ここで、図１３を用いて説明すると、Degreeエラー回避情報２１４のTO_ADUST listとTO_TEST list、TO_TEST2 listは下記の通りになり、
TO_ADJUST=
TO_TEST=J-M(3)Q-P(5)N-E(8)
TO_TEST2=F-I(3)J-E(6)C-D(3)
TO_ADJUST=が全て消えて処理を中断する。
【００７８】
もし、ＤがTO_ADJUST=にノードが残っていたならば、Ｄから２ホップ先のノードをチェックし、D{A2,F2,J2,K2,N2}と記述する。
【００７９】
まだ、TO_ADUST listにノードが残っている場合は、以上の処理をＮホップまでTO_ADUST listのノードがなくなるまで繰り返す。
【００８０】
ステップ１０７）  ツリー完成：
ツリー完成部１６０は、ツリー情報２１３のＭＳＴを取得すると、接続関係情報２１２を参照し、ソース・リーフのSG_IDからツリー形成に不要となるリンクを削除し、ツリーを完成する。
【００８１】
ここで、図１４を用いて説明すると、ツリー情報２１３に存在するＯ−Ｐが不要なリンクであるので、ＭＳＴからＯ−Ｐを削除する。
【００８２】
［第２の実施の形態］
本実施の形態では、前述の第１の実施の形態におけるステップ１０１のSub-graph IDの初期化、ステップ１０３の拡張クラスカルアルゴリズムによるＭＳＴの生成、ステップ１０４の強制的なＭＳＴの生成、ステップ１０５のDegree違反の回避処理、ステップ１０７のツリーの完成の各ステップについては第１の実施の形態と同様であるが、ステップ１０２のリンクソートについてのみ処理が異なる。
【００８３】
本実施例では、ステップ１０２において、ネットワーク上の全てのリンクをリンクコスト順にソートする。
【００８４】
ここで、図１５を用いて説明すると、
Ｂ−Ｄ（２），
Ｋ−Ｊ（２），
Ｇ−Ｆ（２），
Ｏ−Ｎ（２），
Ｃ−Ｄ（３），
Ｍ−Ｊ（３），
Ｉ−Ｆ（３），
Ｑ−Ｎ（３），
Ｂ−Ａ（４），
Ｋ−Ｌ（４），
Ｇ−Ｈ（４），
Ｏ−Ｐ（４），
Ｍ−Ｌ（５），
Ｉ−Ｈ（５），
Ｑ−Ｐ（５），
Ｂ−Ｋ（６），
Ｊ−Ｅ（６），
Ｑ−Ｉ（（７），
Ｆ−Ｅ（７），
Ｎ−Ｅ（８），
Ｄ−Ｅ（９），
Ｒ−Ｊ（１０）
の順にソートする。
【００８５】
以降の処理については、第１の実施の形態と同様であるので、説明を省略する。
【００８６】
なお、上記の実施の形態における図４に示す動作をプログラムとして構築し、最小木経路計算装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
【００８７】
また、構築されたプログラムを最小木経路計算装置として利用されるコンピュータに接続されるハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、コンピュータにインストールする、または、配布することも可能である。
【００８８】
従来のKrushkalアルゴリズムを利用する方法は、図４に示されるトポロジを用いて計算した場合、既存アルゴリズムはDegree違反が発生し、経路を正しく計算できない。
【００８９】
これに対して、本発明は、Degree違反を起こすことなく正しくP2MPノードを分岐ポイントに設定して経路計算されることを確認した。また、本発明ではかならずDegree違反を起こさないことを確認するために、ネットワークシミュレータを用いて３２ノード〜２５６ノードネットワークをランダムに１５００パターン計算し、その中のP2MP比率を２０％から００％までのパターンを割り当てて計算した結果、全てのトポロジにおいて、Degree違反を起こすことなく、P2MPノードを分岐ポイントに設定して経路計算し、正しくツリーを構成していることを確認した。
【００９０】
また、ネットワークシミュレータを用いて、P2MP比率１００％の条件で（つまり、ALL P2MPネットワーク）経路計算した結果、既存Kruskal・拡張Kruskalaアルゴリズム共に、同一のツリーを構成することが明らかとなった。以上の結果により、本発明では、純粋P2MP環境・P2P/P2mP混在環境において最小木を計算可能であることが明らかとなった。
【００９１】
次に、第１の実施の形態と第２の形態について性能比較を実施した。
【００９２】
まず、第１の実施の形態、第２の実施の形態におけるＭＳＴ生成前のリンクの分類・リンクソートのステップの違いによる完成後のＭＳＴのトータルコストの影響を確認するために、それぞれの実施の形態におけるP2MP濃度・リーフ数に対するトータルツリーコスト値を比較した。その結果を図１６に示す。
【００９３】
同図に示す比較条件は、ネットワーク規模を２５６ノード、リンクコストを１〜６４までの正規分布で割り当て、P2MP比率を２０％、４０％、６０％、８０％、１００％、リーフ数を８，１６，３２，６４，１２８，２５５ノードとし、既存のKruskalアルゴリズムの計算結果を１とした場合の第１・第２の実施の形態のコスト比率を計算した。
【００９４】
同図のグラフの出力結果により、第１・第２の実施の形態のP2MP比率が１００％の時の結果は、ALL P2MPネットワークでの既存のKruskalアルゴリズムでの計算結果と同じ結果のコスト比率１となった。また、第２の実施の形態に関しては、P2MP比率が６０％以上のネットワークにおいてコスト比率１．５以下となり、ALL P2MPネットワークでの既存Kruskalアルゴリズムでの計算結果に近い値となった。
【００９５】
これにより、第１の実施の形態と比較して、第２の実施の形態の方がトータルツリーコスト値を低くすることが明らかとなった。これは、第１の実施の形態はリンクコストよりもむしろ、P2MPノードを優先的にＭＳＴに繋げる手法をとっているのに対し、第１の実施の形態では、リンクコスト順に優先的に繋げて並べているため、既存Kruskalの持つ最小木の特性に近くなったと考えられる。
【００９６】
次に、第１の実施の形態、第２の実施の形態のリンク分類・リンクソートのステップの違いによるDegreeエラー回避ステップの発生回数の影響を確認するために、それぞれの実施の形態におけるP2MP濃度・リーフ数に対するDegreeエラー回数ステップ発生時における最大ホップ回数（Degree回避処理のために、Degreeエラーを起こしているノードから何ホップ分先のノードまで処理に影響を及ぼしたか）を比較した結果を図１７に示す。
【００９７】
比較条件は、トータルコストを求めた条件と同一である。
【００９８】
図１７に示すグラフの出力結果により、第１の実施の形態はP2MP比率２０％・リーフ数２５５ノードという厳しい条件においても８０％以上の確率でDegree回避ステップを動作することなく、ＭＳＴを計算可能であった。さらに、P2MP比率を上げることによって、または、リーフ数を減らすことによって１００％に近い比率でDegree回避ステップを動作させることなくＭＳＴを計算可能であった。
【００９９】
一方で、第２の実施の形態では、P2MP比率を２０％・リーフ数２５５ノードという条件で最大１８ホップ目までDegree回避ステップを動作させていた。
【０１００】
これにより、第２の実施の形態と比較して、第１の実施の形態の方がDegree回避ステップの発生が少ないことが明らかとなった。これは、第２の実施の形態はリンクソート時に単純にコスト順に並べてＭＳＴに追加しているため、特にP2Pノードの割合が高いようなネットワーク環境において、Degree回避ステップが多数発生するのに対して、第１の実施の形態はリンク分類の時点でP2MPノードを優先的に繋げているため、Degree回避ステップが殆ど実施されなかったと考えられる。
【０１０１】
Kruskalアルゴリズムを改良し、P2P/P2MPノード混在環境でP2MPLSP経路計算可能なアルゴリズムを確立した。このアルゴリズムは純粋P2MP環境下では従来のＭＳＴを計算することも可能である。従って、本発明はいかなるノード条件でも正しくＭＳＴを計算できるため、大容量のデータ転送を要求するマルチキャスト配信ＮＷに有効と考えられる。将来的には、コピー能力の高いノードを意図的に分岐点とさせるＴＥや、ＧＭＰＬＳ？ＭＰＬＳマルチレイヤネットワークなどの環境における応用が期待される。
【０１０２】
なお、上記の図１６、図１７に記載されている「方式１」は第１の実施の形態に対応し、「方式２」は第２の実施の形態に対応する。
【０１０３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１０４】
マルチキャスト装置とユニキャスト装置が混在する環境において、最小木経路計算を行う技術に適用可能である。
【図面の簡単な説明】
【０１０５】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１の実施の形態における経路計算装置の構成図である。
【図４】本発明の第１の実施の形態における経路計算方法のフローチャートである。
【図５】本発明の第１の実施の形態における初期設定動作を説明するための図である。
【図６】本発明の第１の実施の形態におけるリンクソートを説明するための図である。
【図７】本発明の第１の実施の形態におけるＭＳＴ生成を説明するための図である。
【図８】本発明の第１の実施の形態における強制的なＭＳＴ生成処理を説明するための図である。
【図９】本発明の第１の実施の形態におけるDegree違反の回避ステップのフローチャートである。
【図１０】本発明の第１の実施の形態におけるDegree違反の回避ステップを説明するための図（その１）である。
【図１１】本発明の第１の実施の形態におけるDegree違反の回避ステップを説明するための図（その２）である。
【図１２】本発明の第１の実施の形態におけるDegree違反の回避ステップを説明するための図（その３）である。
【図１３】本発明の第１の実施の形態におけるDegree違反の回避ステップを説明するための図（その４）である。
【図１４】本発明の第１の実施の形態におけるツリーの完成処理を説明するための図である。
【図１５】本発明の第２の実施の形態におけるリンクソートを説明するための図である。
【図１６】本発明の第１・第２の実施の形態におけるP2MP濃度・リーフ数に対するトータルツリーコストの比較結果である。
【図１７】本発明の第１・第２の実施の形態におけるP2MP濃度・リーフ数に対するDegreeエラー回数ステップ発生時における最大ホップ数の比較結果である。
【符号の説明】
【０１０６】
１０  入力部
２０  経路計算装置
３０  出力装置
１００  経路計算制御部
１１０  初期設定部
１２０  リンクソート手段、リンクソート部
１３０  マルチキャストツリー生成手段、ＭＳＴ生成部
１４０  強制的マルチキャストツリー生成手段、強制的ＭＳＴ生成部
１５０  Degree回避処理手段、Degree回避処理部
１６０  ツリー完成部
２１０  トポロジ記憶手段
２１１  ノード情報
２１２  接続関係情報
２１３  ツリー情報
２１４  Degreeエラー回避情報
２１４１  エラーノードの情報
２１４２  候補リスト
【図１】
2006237884.tif 000003
【図２】
2006237884.tif 000004
【図３】
2006237884.tif 000005
【図４】
2006237884.tif 000006
【図５】
2006237884.tif 000007
【図６】
2006237884.tif 000008
【図７】
2006237884.tif 000009
【図８】
2006237884.tif 000010
【図９】
2006237884.tif 000011
【図１０】
2006237884.tif 000012
【図１１】
2006237884.tif 000013
【図１２】
2006237884.tif 000014
【図１３】
2006237884.tif 000015
【図１４】
2006237884.tif 000016
【図１５】
2006237884.tif 000017
【図１６】
2006237884.tif 000018
【図１７】
2006237884.tif 000019