マルチキャスト通信における経路計算方法
【課題】 データ遅延の減少、利用するネットワークリソースの削減を可能にする。
【解決手段】 本発明は、最初は始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合に辿り着く経路の中で最も経路コストが小さい経路を、マルチキャストツリー集合に加え、この処理を最終的にすべてのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャストツリー生成アルゴリズムにおいて、与えられたマルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合までの経路を構成するリンクのリンクコストの総計が最も小さい経路（以下、「最短経路」と記す）の経路コストを再決定する際に、該与えられたマルチキャストツリーからの経由するリンク数が大きい経路は経路コストが大きくなるように比重を付与する。
【解決手段】 本発明は、最初は始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合に辿り着く経路の中で最も経路コストが小さい経路を、マルチキャストツリー集合に加え、この処理を最終的にすべてのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャストツリー生成アルゴリズムにおいて、与えられたマルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合までの経路を構成するリンクのリンクコストの総計が最も小さい経路（以下、「最短経路」と記す）の経路コストを再決定する際に、該与えられたマルチキャストツリーからの経由するリンク数が大きい経路は経路コストが大きくなるように比重を付与する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト通信における経路選択方法に係り、特に、マルチキャストツリーを生成するための経路計算（ルーティング）装置における経路選択方法に関する。IP(Internet Protocol)ネットワークでは、IPTVのような放送型のサービス要求が高まっており、このIPストリームを（G）MPLS（Multi Protocol Label Switching）で明示的に張った土管に通すことにより、帯域を確保して放送型サービスのQoSを保証する必要がある。これらの要求を満たすためには、効率よくマルチキャストツリーを作成する必要がある。
【背景技術】
【０００２】
アルゴリズムの最初はマルチキャストの始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合に辿り着く経路の中で最も経路コストが小さい経路をマルチキャストツリーに加え、この処理を最終的に全てのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャスト生成アルゴリズムがある。
【０００３】
そのマルチキャストツリー生成アルゴリズムとして、MPH(minimum-cost path heuristics)アルゴリズム（例えば、非特許文献１参照）と、MARS(multiplex-aware route-selection)アルゴリズムがある。この両者は、アルゴリズムが異なり、MARSが計算量、処理速度共に優れていることが示されているが、生成されるマルチキャストツリーは同一となる。
【０００４】
本発明は、MARSアルゴリズムを改良しているので、MARSアルゴリズムについて説明する。
【０００５】
図１は、MARSのフローを示す。
【０００６】
ステップ０） 当該ステップでは、アルゴリズムの初期条件と、アルゴリズムが使う集合の定義を示す。集合Eはマルチキャストの終点ノードのうち、まだその終点までの経路が決定していない終点ノードの集合である。集合Eはアルゴリズムの最初は全てのマルチキャストの終点ノードを保持するが、終点ノードまでの経路が決定した終点ノードは集合Eから削除される。集合PQはマルチキャストを構成するブランチになり得るブランチ候補の集合である。集合Vはステップ２で選択されたブランチ上のノードで当該ブランチ始点ノードを除いた全てのノードを格納する。但し、アルゴリズムの最初はマルチキャストツリーの始点ノードのみがVに格納される。集合Rには、ステップ２で選択されたPQ内の最少ブランチが格納されていき、最終的にこのブランチの集合がマルチキャストツリーの全ての構成ブランチとなる。
【０００７】
ステップ１） 初期条件が設定されると、集合V内の各ノードから集合Eに格納されている全ての終点ノードまでの最短経路をブランチ候補としてPQに格納するが、PQはまだ経路が決まっていないマルチキャストツリーの終点毎に１つのブランチ候補を保持するので、もし既にPQに当該終点ノードに対応するブランチ候補が存在する場合は、新ブランチ候補と既存ブランチ候補を比較し、新ブランチ候補の経路コストが小さいときのみ、既存ブランチ候補と新ブランチ候補を入れ替える。そして、全てのV内のノードからのブランチ候補の生成が終わった後にVを空集合にする。
【０００８】
ステップ２） 集合PQ内で最少の経路コストを保持する最少ブランチをPQから取り出し集合Rに格納する。同時に当該最少ブランチ上の始点ノードを除いた全てのノードをVに格納する。
【０００９】
ステップ３） 集合Eからステップ２で格納された最少ブランチの終点ノードを取り出す。
【００１０】
ステップ４） 集合Eが空集合かどうかの判断を行い、空集合の場合はアルゴリズムの終了となる。空集合ではない場合はステップ１の処理に戻る。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】松浦,森田,高見,"P2MP TEに適用するSteiner Treeアルゴリズムの検討,"信学技報（ICM2009-32(2009-11)）.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記のアルゴリズムMARSは、マルチキャストツリーのコスト（マルチキャストツリーを構成するブランチの経路コストの合計）を小さくするためには有効であるが、マルチキャストツリーが利用する(G)MPLSのラベル（ラベルは各リンク毎に必要）数が大きくなる場合がある。また、マルチキャストツリーを構成する各ブランチのホップ数が大きくなり、データ遅延につながるケースがある。
【００１３】
本発明は、上記の点に鑑みなされたもので、データ遅延の減少、利用するネットワークリソースの削減が可能なマルチキャストネットワークにおける経路計算方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するため、本発明（請求項１）は、複数ノードを通信リンクを介して相互に接続可能としたネットワークにおいて、ある始点ノードから他のすべてのノード内の部分集合である複数ノードまでの経路を計算するための経路計算方法であって、
最初は始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合にたどり着く経路の中で最も経路コストが小さい経路を、記憶手段のマルチキャストツリー集合に加え、この処理を最終的にすべてのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャストツリー生成アルゴリズムにおいて、
与えられたマルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合までの経路を構成するリンクのリンクコストの総計が最も小さい経路（以下、「最短経路」と記す）の経路コストを再決定する際に、該与えられたマルチキャストツリーからの経由するリンク数が大きい経路は経路コストが大きくなるように比重を付与する比重付与過程を有する。
【００１５】
また、本発明（請求項２）は、前記比重付与過程において、
前記与えられたマルチキャストツリー上のノードvから、前記経路が決まっていないマルチキャスト終点eまでの最短経路をpath(v, e)とした場合、その経路の再決定される経路コストpath_cost(v, e)を、比重βを用いて、
path_cost(v, e) = |path(v, e)|+β|hop(path(v, e))|
と定義する（但し、|path(v, e)|はpath(v,e)が経由するリンクのリンクコストの合計、|hop(path(v, e))|はpath(v, e)が経由するリンク数、βは正数）。
【発明の効果】
【００１６】
本発明によれば、マルチキャスト通信における経路選択において、経路上のリンク数（ホップ数）も考慮した重み（比重）をリンクコストに付与することにより、マルチキャストツリー生成アルゴリズムで生成されたマルチキャストツリーの各ブランチのホップ数、使用が必要な(G)MPLSのラベル数を少なくできるので、データ遅延の減少、利用するネットワークリソースの削減に寄与できる。
【図面の簡単な説明】
【００１７】
【図１】MARS(multiplex-aware route-selection)フローである。
【図２】本発明の一実施の形態における経路計算装置の構成図である。
【図３】本発明の一実施の形態における比重（β値）による選択経路の変更例である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
図２は、本発明の一実施の形態における経路計算装置の構成を示す。
【００２０】
同図に示す経路計算装置（PCE）１は、ネットワークトポロジ管理モジュール１００、ブランチ候補処理モジュール２００、最小木作成モジュール３００、最短経路作成モジュール４００から構成される。
【００２１】
ネットワークトポロジ管理モジュール１００は、複数のノードと、これらのノード間を接続するリンクにより構成されるネットワークを管理するもので、リンク毎にリンク情報を管理すると共に、ノード毎にノード情報を管理する。リンク情報は、ノード間を接続するすべてのリンクについてそれぞれ、その方向（ＡＺ／ＺＡ）毎にコスト（cost）を管理する。またノード情報は、ノード毎に存在するマルチキャスト終点グループ毎に、当該ノードを始点とし、当該マルチキャスト終点グループに属する各終点ノードまでの最短経路を表す情報をそれぞれ管理する。なお、マルチキャスト終点グループは、マルチキャストツリーの終点ノード集合毎に存在し、当該ノードから各終点までの最短経路と、その経路コストを保持する。このマルチキャスト終点グループは、最小木作成処理部２３で、各ノードからマルチキャスト終点ノードまでの最短経路を取得する際にO(1)の時間計算量で処理を行うために利用される。ネットワークトポロジ管理モジュール１００は、ネットワークトポロジ管理処理部２１と、複数の記憶部を備えている。記憶部は、リンク情報記憶部３１と、ノード情報記憶部３２とから構成される。
【００２２】
リンク情報記憶部３１には、ネットワーク内の各ノード間のリンク情報が記憶される。またノード情報記憶部３２には、マルチキャスト終点グループ毎に、ネットワーク上の当該ノードから当該マルチキャスト終点グループに属する複数の終点ノードまでの最短経路情報が、当該終点ノードに対応付けられて記憶される。
【００２３】
ネットワークトポロジ管理処理部２１は、ネットワーク上のすべてのノードと、これらのノード間を接続するリンクを管理するための処理を行うもので、リンク情報を上記リンク情報記憶部３１に、ノード情報をノード情報記憶部３２にそれぞれ格納する。
【００２４】
ブランチ候補処理モジュール（PQ)２００は、最小木作成モジュール３００が最小木作成アルゴリズムの中で利用するブランチ候補をブランチ候補記憶部３５に登録する。また、最小木作成モジュール３００からの要求によりブランチ候補を検索する機能も併せ持つ。ブランチ候補処理モジュール２００は、ブランチ候補処理部２２と、ブランチ候補記憶部３５を備えている。ブランチ候補処理部２２は、最小木作成モジュール３００が最小木作成アルゴリズムの中で利用するブランチ候補をブランチ候補記憶部３５に記憶すると共に、最小木作成モジュール３００からの要求によりブランチ候補を検索する処理を行う。ブランチ候補記憶部３５は、上記ブランチ候補を記憶するために使用される。
【００２５】
最小木作成モジュール３００は、最小木作成処理部２３と、ブランチ記憶部３６を備え、最小木作成アルゴリズムとして最短経路にホップ数比重に応じた経路コストを再設定する手法を用いたMARSアルゴリズムを保持する。MARSアルゴリズムでは、ブランチ候補をブランチ候補処理モジュール２００に登録すると共に、この登録されたブランチ候補を検索のために利用して最小木を作成し、当該ブランチ候補をブランチ候補記憶部３５から削除し、新たなブランチとしてブランチ記憶部３６（集合R）に格納する。また、必要に応じて各ノードからマルチキャスト終点グループの各終点ノードまでの最短経路を、上記ネットワークトポロジ管理モジュール１００で管理されているノード情報中のマルチキャスト終点グループから取得する。この際にノード情報記憶部３２のマルチキャスト終点グループの各最短経路の経路コストは図２の(*1)に示すように、当該最短経路上のリンク数（ホップ数）に応じた比重を付けることができる。なお、当該MARSアルゴリズムについては後述する。
【００２６】
最短経路作成モジュール４００は、最短経路作成処理部２４を備えている。この最短経
路作成処理部２４は、ネットワークトポロジ管理モジュール１００のリンク情報記憶部３１で管理されているリンク情報を利用して、ノード間の最短経路を探索アルゴリズムを用いて定期的に探索する処理と、その探索結果をネットワークトポロジ管理モジュール１００内のノード情報記憶部３２の各ノード情報に含まれるマルチキャスト終点グループごとの最短経路情報に反映させる処理を、ネットワークトポロジ管理モジュール１００のネットワーク管理処理部２１を介して実行する。
【００２７】
なお、上記ネットワークトポロジ管理処理部２１、ブランチ候補処理部２２、最小木作成処理部２３及び最短経路作成処理部２４は、何れもＰＣＥ１が備える中央処理ユニット（ＣＰＵ；Central Processing Unit）（図示せず）に、プログラムを実行させることにより実現される。
【００２８】
上記の構成の最小木作成モジュール３００に保持されているMARSアルゴリズムについて、図１に示す従来のMARSアルゴリズムのとの差異を示す。従来は、Ｖ内の各ノードからＥ内の各終点までの最短経路の経路コストは、最短経路を構成するリンクコストの総計としていたが、本発明では、当該最短経路の経路コストを再設定する際に、最短経路の経由するリンク数が大きい最短経路は経路コストが大きくなるように比重を付与する。この最短経路の経路コストの再設定により、MARSアルゴリズムのステップ２で選択されるPQ内の最小ブランチが変更される。
【００２９】
図３は、本発明の一実施の形態における比重（β値）によるMARSアルゴリズムのステップ２で選択される最小ブランチの変更例を示す。
【００３０】
同図において、円はノードを示し、ノード間を結ぶ矢印つきの線は当該ノード間の方向性を持ったリンクを示し、矢印の方向のリンクコストが付与されている。
【００３１】
ノードv2はマルチキャストツリーに属するノードで終点ノードeに最も近いノードを示す。その際に、図１に示した従来のアルゴリズムMARSでは経路v2−b−a−eが、経路コストが最も小さいコストとなり、ステップ２でPQ内の最小ブランチとして選択されるが、本発明では、経路上のリンク数に応じて再決定される最短経路の経路コストを用いると、選択結果が変わることになる。
【００３２】
図３の例において、与えられたマルチキャスト上のノードｖから経路が決まっていないマルチキャスト終点ｅまでの最短経路をpath(v,e)とした場合、その経路の再決定される経路コストpath_cost(v,e)を、比重βを用いて
path_cost(v, e) = |path(v, e)|+β|hop(path(v, e))|
のように定義する。ここで、|path(v, e)|はpath(v,e)が経由するリンクのリンクコストの合計、|hop(path(v, e))|はpath(v, e)が経由するリンク数、βは正数とする。
【００３３】
β=2とした場合、
path_cost(v1-a-e) =4+4=8,
path_cost(v2-b-a-e) =3+6=9
となり、経路v1−a−eの方が経路コストが小さくなり、図１のステップ２で選択される最小ブランチが異なる。この例のように、リンク数の少ないブランチが優先的に選択されることになるので、最終的にブランチ記憶部３６の集合Rに格納されるブランチを構成するリンク数は少なくなる。
【００３４】
なお、β=0とした場合は、経路上のリンク数に応じた比重がなくなるので、従来のMARSアルゴリズムと同様の結果がでる。
【００３５】
比重は、例えば、許容遅延時間が小さいサービスにはホップ数を短くする設定が必要になるので、その場合の比重βの値を大きくすることでホップ数の小さいマルチキャストツリーを作成することが有効である。サービスの許容遅延時間応じて自動的にβの値を設定する手法も可能となる。
【００３６】
逆にβの値を大きくしすぎるとマルチキャストツリーのコストが大きくなる可能性があり、伝送容量の小さいリンクを過多に利用する結果になる場合があるが、そのβの値はネットワーク(NW)オペレータがNWの状況を加味して適切に設定することが可能となる。
【００３７】
上記では、最良の形態としてMARSアルゴリズムに適用する例を示しているが、この例に限定されることなく、他の経路選択アルゴリズムに適用することも可能である。
【００３８】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００３９】
１ 経路計算装置（PCE）
２１ ネットワークトポロジ管理処理部
２２ ブランチ候補処理部
２３ 最小木作成処理部
２４ 最短経路作成処理部
３１ リンク情報記憶部
３２ ノード情報記憶部
１００ ネットワークトポロジ管理モジュール
２００ ブランチ候補処理モジュール
３００ 最小木作成モジュール
４００ 最短経路作成モジュール
【技術分野】
【０００１】
本発明は、マルチキャスト通信における経路選択方法に係り、特に、マルチキャストツリーを生成するための経路計算（ルーティング）装置における経路選択方法に関する。IP(Internet Protocol)ネットワークでは、IPTVのような放送型のサービス要求が高まっており、このIPストリームを（G）MPLS（Multi Protocol Label Switching）で明示的に張った土管に通すことにより、帯域を確保して放送型サービスのQoSを保証する必要がある。これらの要求を満たすためには、効率よくマルチキャストツリーを作成する必要がある。
【背景技術】
【０００２】
アルゴリズムの最初はマルチキャストの始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合に辿り着く経路の中で最も経路コストが小さい経路をマルチキャストツリーに加え、この処理を最終的に全てのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャスト生成アルゴリズムがある。
【０００３】
そのマルチキャストツリー生成アルゴリズムとして、MPH(minimum-cost path heuristics)アルゴリズム（例えば、非特許文献１参照）と、MARS(multiplex-aware route-selection)アルゴリズムがある。この両者は、アルゴリズムが異なり、MARSが計算量、処理速度共に優れていることが示されているが、生成されるマルチキャストツリーは同一となる。
【０００４】
本発明は、MARSアルゴリズムを改良しているので、MARSアルゴリズムについて説明する。
【０００５】
図１は、MARSのフローを示す。
【０００６】
ステップ０） 当該ステップでは、アルゴリズムの初期条件と、アルゴリズムが使う集合の定義を示す。集合Eはマルチキャストの終点ノードのうち、まだその終点までの経路が決定していない終点ノードの集合である。集合Eはアルゴリズムの最初は全てのマルチキャストの終点ノードを保持するが、終点ノードまでの経路が決定した終点ノードは集合Eから削除される。集合PQはマルチキャストを構成するブランチになり得るブランチ候補の集合である。集合Vはステップ２で選択されたブランチ上のノードで当該ブランチ始点ノードを除いた全てのノードを格納する。但し、アルゴリズムの最初はマルチキャストツリーの始点ノードのみがVに格納される。集合Rには、ステップ２で選択されたPQ内の最少ブランチが格納されていき、最終的にこのブランチの集合がマルチキャストツリーの全ての構成ブランチとなる。
【０００７】
ステップ１） 初期条件が設定されると、集合V内の各ノードから集合Eに格納されている全ての終点ノードまでの最短経路をブランチ候補としてPQに格納するが、PQはまだ経路が決まっていないマルチキャストツリーの終点毎に１つのブランチ候補を保持するので、もし既にPQに当該終点ノードに対応するブランチ候補が存在する場合は、新ブランチ候補と既存ブランチ候補を比較し、新ブランチ候補の経路コストが小さいときのみ、既存ブランチ候補と新ブランチ候補を入れ替える。そして、全てのV内のノードからのブランチ候補の生成が終わった後にVを空集合にする。
【０００８】
ステップ２） 集合PQ内で最少の経路コストを保持する最少ブランチをPQから取り出し集合Rに格納する。同時に当該最少ブランチ上の始点ノードを除いた全てのノードをVに格納する。
【０００９】
ステップ３） 集合Eからステップ２で格納された最少ブランチの終点ノードを取り出す。
【００１０】
ステップ４） 集合Eが空集合かどうかの判断を行い、空集合の場合はアルゴリズムの終了となる。空集合ではない場合はステップ１の処理に戻る。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】松浦,森田,高見,"P2MP TEに適用するSteiner Treeアルゴリズムの検討,"信学技報（ICM2009-32(2009-11)）.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記のアルゴリズムMARSは、マルチキャストツリーのコスト（マルチキャストツリーを構成するブランチの経路コストの合計）を小さくするためには有効であるが、マルチキャストツリーが利用する(G)MPLSのラベル（ラベルは各リンク毎に必要）数が大きくなる場合がある。また、マルチキャストツリーを構成する各ブランチのホップ数が大きくなり、データ遅延につながるケースがある。
【００１３】
本発明は、上記の点に鑑みなされたもので、データ遅延の減少、利用するネットワークリソースの削減が可能なマルチキャストネットワークにおける経路計算方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するため、本発明（請求項１）は、複数ノードを通信リンクを介して相互に接続可能としたネットワークにおいて、ある始点ノードから他のすべてのノード内の部分集合である複数ノードまでの経路を計算するための経路計算方法であって、
最初は始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合にたどり着く経路の中で最も経路コストが小さい経路を、記憶手段のマルチキャストツリー集合に加え、この処理を最終的にすべてのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャストツリー生成アルゴリズムにおいて、
与えられたマルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合までの経路を構成するリンクのリンクコストの総計が最も小さい経路（以下、「最短経路」と記す）の経路コストを再決定する際に、該与えられたマルチキャストツリーからの経由するリンク数が大きい経路は経路コストが大きくなるように比重を付与する比重付与過程を有する。
【００１５】
また、本発明（請求項２）は、前記比重付与過程において、
前記与えられたマルチキャストツリー上のノードvから、前記経路が決まっていないマルチキャスト終点eまでの最短経路をpath(v, e)とした場合、その経路の再決定される経路コストpath_cost(v, e)を、比重βを用いて、
path_cost(v, e) = |path(v, e)|+β|hop(path(v, e))|
と定義する（但し、|path(v, e)|はpath(v,e)が経由するリンクのリンクコストの合計、|hop(path(v, e))|はpath(v, e)が経由するリンク数、βは正数）。
【発明の効果】
【００１６】
本発明によれば、マルチキャスト通信における経路選択において、経路上のリンク数（ホップ数）も考慮した重み（比重）をリンクコストに付与することにより、マルチキャストツリー生成アルゴリズムで生成されたマルチキャストツリーの各ブランチのホップ数、使用が必要な(G)MPLSのラベル数を少なくできるので、データ遅延の減少、利用するネットワークリソースの削減に寄与できる。
【図面の簡単な説明】
【００１７】
【図１】MARS(multiplex-aware route-selection)フローである。
【図２】本発明の一実施の形態における経路計算装置の構成図である。
【図３】本発明の一実施の形態における比重（β値）による選択経路の変更例である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
図２は、本発明の一実施の形態における経路計算装置の構成を示す。
【００２０】
同図に示す経路計算装置（PCE）１は、ネットワークトポロジ管理モジュール１００、ブランチ候補処理モジュール２００、最小木作成モジュール３００、最短経路作成モジュール４００から構成される。
【００２１】
ネットワークトポロジ管理モジュール１００は、複数のノードと、これらのノード間を接続するリンクにより構成されるネットワークを管理するもので、リンク毎にリンク情報を管理すると共に、ノード毎にノード情報を管理する。リンク情報は、ノード間を接続するすべてのリンクについてそれぞれ、その方向（ＡＺ／ＺＡ）毎にコスト（cost）を管理する。またノード情報は、ノード毎に存在するマルチキャスト終点グループ毎に、当該ノードを始点とし、当該マルチキャスト終点グループに属する各終点ノードまでの最短経路を表す情報をそれぞれ管理する。なお、マルチキャスト終点グループは、マルチキャストツリーの終点ノード集合毎に存在し、当該ノードから各終点までの最短経路と、その経路コストを保持する。このマルチキャスト終点グループは、最小木作成処理部２３で、各ノードからマルチキャスト終点ノードまでの最短経路を取得する際にO(1)の時間計算量で処理を行うために利用される。ネットワークトポロジ管理モジュール１００は、ネットワークトポロジ管理処理部２１と、複数の記憶部を備えている。記憶部は、リンク情報記憶部３１と、ノード情報記憶部３２とから構成される。
【００２２】
リンク情報記憶部３１には、ネットワーク内の各ノード間のリンク情報が記憶される。またノード情報記憶部３２には、マルチキャスト終点グループ毎に、ネットワーク上の当該ノードから当該マルチキャスト終点グループに属する複数の終点ノードまでの最短経路情報が、当該終点ノードに対応付けられて記憶される。
【００２３】
ネットワークトポロジ管理処理部２１は、ネットワーク上のすべてのノードと、これらのノード間を接続するリンクを管理するための処理を行うもので、リンク情報を上記リンク情報記憶部３１に、ノード情報をノード情報記憶部３２にそれぞれ格納する。
【００２４】
ブランチ候補処理モジュール（PQ)２００は、最小木作成モジュール３００が最小木作成アルゴリズムの中で利用するブランチ候補をブランチ候補記憶部３５に登録する。また、最小木作成モジュール３００からの要求によりブランチ候補を検索する機能も併せ持つ。ブランチ候補処理モジュール２００は、ブランチ候補処理部２２と、ブランチ候補記憶部３５を備えている。ブランチ候補処理部２２は、最小木作成モジュール３００が最小木作成アルゴリズムの中で利用するブランチ候補をブランチ候補記憶部３５に記憶すると共に、最小木作成モジュール３００からの要求によりブランチ候補を検索する処理を行う。ブランチ候補記憶部３５は、上記ブランチ候補を記憶するために使用される。
【００２５】
最小木作成モジュール３００は、最小木作成処理部２３と、ブランチ記憶部３６を備え、最小木作成アルゴリズムとして最短経路にホップ数比重に応じた経路コストを再設定する手法を用いたMARSアルゴリズムを保持する。MARSアルゴリズムでは、ブランチ候補をブランチ候補処理モジュール２００に登録すると共に、この登録されたブランチ候補を検索のために利用して最小木を作成し、当該ブランチ候補をブランチ候補記憶部３５から削除し、新たなブランチとしてブランチ記憶部３６（集合R）に格納する。また、必要に応じて各ノードからマルチキャスト終点グループの各終点ノードまでの最短経路を、上記ネットワークトポロジ管理モジュール１００で管理されているノード情報中のマルチキャスト終点グループから取得する。この際にノード情報記憶部３２のマルチキャスト終点グループの各最短経路の経路コストは図２の(*1)に示すように、当該最短経路上のリンク数（ホップ数）に応じた比重を付けることができる。なお、当該MARSアルゴリズムについては後述する。
【００２６】
最短経路作成モジュール４００は、最短経路作成処理部２４を備えている。この最短経
路作成処理部２４は、ネットワークトポロジ管理モジュール１００のリンク情報記憶部３１で管理されているリンク情報を利用して、ノード間の最短経路を探索アルゴリズムを用いて定期的に探索する処理と、その探索結果をネットワークトポロジ管理モジュール１００内のノード情報記憶部３２の各ノード情報に含まれるマルチキャスト終点グループごとの最短経路情報に反映させる処理を、ネットワークトポロジ管理モジュール１００のネットワーク管理処理部２１を介して実行する。
【００２７】
なお、上記ネットワークトポロジ管理処理部２１、ブランチ候補処理部２２、最小木作成処理部２３及び最短経路作成処理部２４は、何れもＰＣＥ１が備える中央処理ユニット（ＣＰＵ；Central Processing Unit）（図示せず）に、プログラムを実行させることにより実現される。
【００２８】
上記の構成の最小木作成モジュール３００に保持されているMARSアルゴリズムについて、図１に示す従来のMARSアルゴリズムのとの差異を示す。従来は、Ｖ内の各ノードからＥ内の各終点までの最短経路の経路コストは、最短経路を構成するリンクコストの総計としていたが、本発明では、当該最短経路の経路コストを再設定する際に、最短経路の経由するリンク数が大きい最短経路は経路コストが大きくなるように比重を付与する。この最短経路の経路コストの再設定により、MARSアルゴリズムのステップ２で選択されるPQ内の最小ブランチが変更される。
【００２９】
図３は、本発明の一実施の形態における比重（β値）によるMARSアルゴリズムのステップ２で選択される最小ブランチの変更例を示す。
【００３０】
同図において、円はノードを示し、ノード間を結ぶ矢印つきの線は当該ノード間の方向性を持ったリンクを示し、矢印の方向のリンクコストが付与されている。
【００３１】
ノードv2はマルチキャストツリーに属するノードで終点ノードeに最も近いノードを示す。その際に、図１に示した従来のアルゴリズムMARSでは経路v2−b−a−eが、経路コストが最も小さいコストとなり、ステップ２でPQ内の最小ブランチとして選択されるが、本発明では、経路上のリンク数に応じて再決定される最短経路の経路コストを用いると、選択結果が変わることになる。
【００３２】
図３の例において、与えられたマルチキャスト上のノードｖから経路が決まっていないマルチキャスト終点ｅまでの最短経路をpath(v,e)とした場合、その経路の再決定される経路コストpath_cost(v,e)を、比重βを用いて
path_cost(v, e) = |path(v, e)|+β|hop(path(v, e))|
のように定義する。ここで、|path(v, e)|はpath(v,e)が経由するリンクのリンクコストの合計、|hop(path(v, e))|はpath(v, e)が経由するリンク数、βは正数とする。
【００３３】
β=2とした場合、
path_cost(v1-a-e) =4+4=8,
path_cost(v2-b-a-e) =3+6=9
となり、経路v1−a−eの方が経路コストが小さくなり、図１のステップ２で選択される最小ブランチが異なる。この例のように、リンク数の少ないブランチが優先的に選択されることになるので、最終的にブランチ記憶部３６の集合Rに格納されるブランチを構成するリンク数は少なくなる。
【００３４】
なお、β=0とした場合は、経路上のリンク数に応じた比重がなくなるので、従来のMARSアルゴリズムと同様の結果がでる。
【００３５】
比重は、例えば、許容遅延時間が小さいサービスにはホップ数を短くする設定が必要になるので、その場合の比重βの値を大きくすることでホップ数の小さいマルチキャストツリーを作成することが有効である。サービスの許容遅延時間応じて自動的にβの値を設定する手法も可能となる。
【００３６】
逆にβの値を大きくしすぎるとマルチキャストツリーのコストが大きくなる可能性があり、伝送容量の小さいリンクを過多に利用する結果になる場合があるが、そのβの値はネットワーク(NW)オペレータがNWの状況を加味して適切に設定することが可能となる。
【００３７】
上記では、最良の形態としてMARSアルゴリズムに適用する例を示しているが、この例に限定されることなく、他の経路選択アルゴリズムに適用することも可能である。
【００３８】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００３９】
１ 経路計算装置（PCE）
２１ ネットワークトポロジ管理処理部
２２ ブランチ候補処理部
２３ 最小木作成処理部
２４ 最短経路作成処理部
３１ リンク情報記憶部
３２ ノード情報記憶部
１００ ネットワークトポロジ管理モジュール
２００ ブランチ候補処理モジュール
３００ 最小木作成モジュール
４００ 最短経路作成モジュール
【特許請求の範囲】
【請求項１】
複数ノードを通信リンクを介して相互に接続可能としたネットワークにおいて、ある始点ノードから他のすべてのノード内の部分集合である複数ノードまでの経路を計算するための経路計算方法であって、
最初は始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合にたどり着く経路の中で最も経路コストが小さい経路を、記憶手段のマルチキャストツリー集合に加え、この処理を最終的にすべてのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャストツリー生成アルゴリズムにおいて、
与えられたマルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合までの経路を構成するリンクのリンクコストの総計が最も小さい経路（以下、「最短経路」と記す）の経路コストを再決定する際に、該与えられたマルチキャストツリーからの経由するリンク数が大きい経路は経路コストが大きくなるように比重を付与する比重付与過程を有することを特徴とするマルチキャストネットワークにおける経路計算方法。
【請求項２】
前記比重付与過程において、
前記与えられたマルチキャストツリー上のノードvから、前記経路が決まっていないマルチキャスト終点eまでの最短経路をpath(v, e)とした場合、その経路の再決定される経路コストpath_cost(v, e)を、比重βを用いて、
path_cost(v, e) = |path(v, e)|+β|hop(path(v, e))|
と定義する（但し、|path(v, e)|はpath(v,e)が経由するリンクのリンクコストの合計、|hop(path(v, e))|はpath(v, e)が経由するリンク数、βは正数）
請求項１記載のマルチキャストネットワークにおける経路計算方法。
【請求項１】
複数ノードを通信リンクを介して相互に接続可能としたネットワークにおいて、ある始点ノードから他のすべてのノード内の部分集合である複数ノードまでの経路を計算するための経路計算方法であって、
最初は始点ノードのみからなるマルチキャストツリーを定義し、当該マルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合にたどり着く経路の中で最も経路コストが小さい経路を、記憶手段のマルチキャストツリー集合に加え、この処理を最終的にすべてのマルチキャストツリー終点ノードまでの経路が決まるまで繰り返すマルチキャストツリー生成アルゴリズムにおいて、
与えられたマルチキャストツリーから、まだ経路が決まっていないマルチキャスト終点ノード集合までの経路を構成するリンクのリンクコストの総計が最も小さい経路（以下、「最短経路」と記す）の経路コストを再決定する際に、該与えられたマルチキャストツリーからの経由するリンク数が大きい経路は経路コストが大きくなるように比重を付与する比重付与過程を有することを特徴とするマルチキャストネットワークにおける経路計算方法。
【請求項２】
前記比重付与過程において、
前記与えられたマルチキャストツリー上のノードvから、前記経路が決まっていないマルチキャスト終点eまでの最短経路をpath(v, e)とした場合、その経路の再決定される経路コストpath_cost(v, e)を、比重βを用いて、
path_cost(v, e) = |path(v, e)|+β|hop(path(v, e))|
と定義する（但し、|path(v, e)|はpath(v,e)が経由するリンクのリンクコストの合計、|hop(path(v, e))|はpath(v, e)が経由するリンク数、βは正数）
請求項１記載のマルチキャストネットワークにおける経路計算方法。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１３−９８６４７（Ｐ２０１３−９８６４７Ａ）
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１１−２３７７５１（Ｐ２０１１−２３７７５１）
【出願日】平成２３年１０月２８日（２０１１．１０．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願日】平成２３年１０月２８日（２０１１．１０．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]