(57)【特許請求の範囲】
【請求項１】
マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算方法であって、
前記通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、探索経路記憶手段に格納するダイクストラ経路計算ステップと、
前記探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する受信装置数カウントステップと、
送信伝送装置を訪問済記憶手段に格納し、探索対象装置とする初期設定ステップと、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定ステップと、
前記マルチキャスト判定ステップにおいて、ユニキャスト伝送装置と判定されたときは、前記受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として、候補装置記憶手段に格納すると共に、該候補装置までのリンクコストと経路を前記探索経路記憶手段に格納するユニキャスト装置用候補装置決定ステップと、
前記マルチキャスト判定ステップにおいて、探索対象装置がマルチキャスト伝送装置であるときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、前記候補装置記憶手段に格納するマルチキャスト装置用候補装置決定ステップと、
前記候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定ステップと、
前記訪問済装置記憶手段に全ての受信装置が設定されている場合に、前記探索経路記憶手段に格納されている経路を出力する出力ステップと、
を行うことを特徴とするマルチキャスト経路計算方法。
【請求項２】
マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算方法であって、
前記通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、探索経路記憶手段に格納するダイクストラ経路計算ステップと、
前記探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する第１の受信装置数カウントステップと、
送信伝送装置を訪問済記憶手段に格納し、探索対象装置とする初期設定ステップと、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定ステップと、
前記マルチキャスト判定ステップにおいて、ユニキャスト伝送装置であると判定されたときは、前記受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として選択し、候補装置記憶手段に格納するユニキャスト装置用候補装置決定ステップと、
選択した候補装置までの経路以外を切断したトポロジに対して、再び、全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト経路計算方法によってマルチキャスト経路を計算し、前記探索経路記憶手段に格納するステップと、
前記探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、前記受信装置数記憶手段に格納する第２の受信装置数カウントステップと、
前記マルチキャスト判定ステップにおいて、マルチキャスト伝送装置であると判定されたときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、前記候補装置記憶手段に格納すると共に、再選択された候補装置までのリンクコストと経路を前記探索経路記憶手段に格納するマルチキャスト装置用候補装置決定ステップと、
前記候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定ステップと、
前記訪問済装置記憶手段に全ての受信装置が設定されている場合に、前記探索経路記憶手段に格納されている経路を出力する出力ステップと、
を行うことを特徴とするマルチキャスト経路計算方法。
【請求項３】
マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算装置であって、
各伝送装置の送信伝送装置までの経路とリンクコストを記憶する探索経路記憶手段と、
探索された伝送装置を訪問済装置として記憶する訪問済装置記憶手段と、
候補装置を記憶する候補装置記憶手段と、
カウントされた受信装置数を記憶する受信装置数記憶手段と、
前記通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、前記探索経路記憶手段に格納するダイクストラ経路計算手段と、
前記探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、前記受信装置数記憶手段に格納する受信装置数カウント手段と、
送信伝送装置を前記訪問済記憶手段に格納し、探索対象装置とする初期設定手段と、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定手段と、
前記マルチキャスト判定手段において、ユニキャスト伝送装置と判定されたときは、前記受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として、候補装置記憶手段に格納するユニキャスト装置用候補装置決定手段と、
前記マルチキャスト判定手段において、探索対象装置がマルチキャスト伝送装置であるときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、前記候補装置記憶手段に格納すると共に、再選択された候補装置までのリンクコストと経路を前記探索経路記憶手段に格納するマルチキャスト装置用候補装置決定手段と、
前記候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定手段と、
前記訪問済装置記憶手段に全ての受信装置が設定されている場合に、前記探索経路記憶手段に格納されている経路を出力する経路完了判定手段と、
を有することを特徴とするマルチキャスト経路計算装置。
【請求項４】
マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算装置であって、
各伝送装置の送信伝送装置までの経路とリンクコストを記憶する探索経路記憶手段と、
探索された伝送装置を訪問済装置として記憶する訪問済装置記憶手段と、
候補装置を記憶する候補装置記憶手段と、
カウントされた受信装置数を記憶する受信装置数記憶手段と、
前記通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、前記探索経路記憶手段に格納するダイクストラ経路計算手段と、
前記探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、前記受信装置数記憶手段に格納する第１の受信装置数カウント手段と、
送信伝送装置を前記訪問済記憶手段に格納し、探索対象装置とする初期設定手段と、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定手段と、
前記マルチキャスト判定手段において、ユニキャスト伝送装置であると判定されたときは、前記受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として選択し、候補装置記憶手段に格納するユニキャスト装置用候補装置決定手段と、
選択した候補装置までの経路以外を切断したトポロジに対して、再び、全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト経路計算方法によってマルチキャスト経路を計算し、前記探索経路記憶手段に格納する経路再計算手段と、
前記探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、前記受信装置数記憶手段に格納する第２の受信装置数カウント手段と、
前記マルチキャスト判定手段において、マルチキャスト伝送装置であると判定されたときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、前記候補装置記憶手段に格納すると共に、再選択された候補装置までのリンクコストと経路を前記探索経路記憶手段に格納するマルチキャスト装置用候補装置決定手段と、
前記候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定手段と、
前記訪問済装置記憶手段に全ての受信装置が設定されている場合に、前記探索経路記憶手段に格納されている経路を出力する経路完了判定手段と、
を有することを特徴とするマルチキャスト経路計算装置。
【請求項５】
探索経路記憶手段、訪問済装置記憶手段、候補装置記憶手段、受信装置数記憶手段と、を有するコンピュータを、
請求項３または請求項４に記載された手段を有するマルチキャスト経路計算装置として、機能させる請求項３または請求項４に記載された手段を有するマルチキャスト経路計算装置として、コンピュータを機能させることを特徴とするマルチキャスト経路計算プログラム。
【請求項６】
探索経路記憶手段、訪問済装置記憶手段、候補装置記憶手段、受信装置数記憶手段と、を有するコンピュータを、
請求項３または請求項４に記載された手段を有するマルチキャスト経路計算装置として、機能させるプログラムを格納したことを特徴とするマルチキャスト経路計算プログラムを格納した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト経路計算方法及び装置およびプログラム及びプログラムを格納した記憶媒体に係り、特に、マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、送信伝送装置から、受信伝送装置までのリンクコストが最小になるような経路を求めるために使用されるマルチキャスト経路計算方法及び装置およびプログラム及びプログラムを格納した記憶媒体に関する。
【背景技術】
【０００２】
従来、通信網において、図２０に示すように、トポロジ情報収集機構によって集められたトポロジ情報１０と、送信伝送装置、受信伝送装置、必要帯域などの経路設定制約条件１１から、マルチキャスト経路を計算し、その計算結果を経路設定機構１３に出力するマルチキャスト経路計算装置１２が用いられている。
【０００３】
ここで、図２１を用いて、従来技術であるダイクストラマルチキャスト経路計算方法を用いたマルチキャスト経路計算装置について説明する。
【０００４】
図２１の（ａ）のような接続関係とリンクコストを含むトポロジ情報と、送信伝送装置・受信伝送装置の条件が入力された際に、送信伝送装置から受信伝送装置までのリンクコストが最小になるようなマルチキャスト経路を計算する。
【０００５】
次に、同図（ｂ）に示すように、送信伝送装置Ａから、隣接する伝送装置（Ｂ，Ｉ）までのリンクコストを計算し、候補装置とする。次に、その候補装置の中から、送信伝送装置からのリンクコストが最小のものを選択する。本トポロジでは、リンクコストが“２”であるＢを選択し、送信伝送装置ＡからＢまでの経路を決定する。Ｂを候補装置から外し、訪問済装置とする。その決定した伝送装置と隣接する伝送装置を探索する。そのとき、隣接した装置の中に、決定した伝送装置の一つ前の装置Ａは含めないこととする。同図（ｃ）に示すように、それぞれ隣接する伝送装置に対して、その決定した伝送装置経由での送信伝送装置からのリンクコストを計算し、候補装置とする。
【０００６】
同様にして、図２２（ｄ）に示すように、Ｉを訪問済装置とし、Ｉに隣接する伝送装置Ｅ，Ｈを候補装置とする。
【０００７】
次に候補装置の中から、送信伝送装置からのリンクコストが最小のものを選択するが、複数ある場合は、その他の経路設定制約条件等を用いて一つを選択する。この例においては、Ｇを選択し、Ｇを訪問済装置とする。さらに、その伝送装置Ｇに隣接する経路を候補にする際、その隣接装置が既に候補装置や訪問済み伝送装置となっている場合は、既に計算されている送信伝送装置からのリンクコストと、先程決定した伝送装置Ｇ経由での送信伝送装置からのリンクコストを比較し、小さい方をその隣接装置までの経路とする。従って、図２２（ｅ）において、Ｈは、Ｉからの候補装置となっているが、送信伝送装置からのリンクコストの比較によって（同図（ｄ），（ｅ）の比較）、Ｈは、Ｇからの候補装置となる。Ｆは、Ｇ経由での送信伝送装置からのリンクコストが大きいことから、Ｂからの候補装置のままとなる。
【０００８】
続いて、図２２（ｆ）に示すように、先程と同様にＦまでの、経路において、Ｆを候補装置から外し、訪問済装置とする。さらに、Ｅまでの経路を決定し、Ｅを候補装置からはずし、訪問済装置とする。図２３（ｇ）に示すように、Ｅの隣接装置を候補装置Ｄとする。
【０００９】
全装置の探索後は、候補装置の中から、送信伝送装置からのリンクコストが小さい順に経路を決定していく。
【００１０】
これにより、図２３（ｈ）に示すように、送信伝送装置から入力された全ての受信伝送装置を含むマルチキャスト経路が発見できたことになる。その経路から、図２３（ｉ）に示すように、受信伝送装置に到達しない不要な経路を削除し、経路設定機構１３へ出力する。
【００１１】
この出力結果では、ユニキャスト伝送装置であるＢにおいて分岐が発生している。このように、従来技術においては、マルチキャスト伝送装置とユニキャスト伝送装置の違いを考慮せずに、リンクコストのみを用いて探索対象装置から複数の候補装置を決定するため、本来分岐ができないユニキャスト伝送装置において分岐するような経路が出力されてしまう（例えば、非特許文献１参照）。
【非特許文献１】WIDE ２００２年インターネットアーキテクチャ第６回講義資料http://www.soi.wide.ad.jp/class/20020022/materials_for_student/06/na-06.pdf  （１０ページ、１１ページ）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
上記に示した技術では、入力されたトポロジ情報と経路設定制約条件から、送信伝送装置から各受信伝送装置までのリンクコストを最小にするようなマルチキャスト経路を計算し、経路設定機構に出力することができる。
【００１３】
しかし、既存技術では、マルチキャスト伝送装置とユニキャスト伝送装置が混在したような通信網において、それらの違いを考慮せずに経路計算が行われるため、分岐ができないユニキャスト伝送装置においても分岐してしまうようなマルチキャスト経路が出力されてしまうという問題がある。その結果、経路設定機構では、正常に経路設定ができず、通信ができない。
【００１４】
本発明は、上記の点に鑑みなされたもので、マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網においても、送信伝送装置から各受信伝送装置までのリンクコストが小さくなるようにしつつ、ユニキャスト伝送装置では分岐が発生しないマルチキャスト経路を出力することが可能なマルチキャスト経路計算方法及び装置及びプログラム及びマルチキャスト経路計算プログラムを格納した記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００１５】
図１は、本発明の原理を説明するための図である。
【００１６】
本発明（請求項１）は、マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算方法であって、
通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、探索経路記憶手段に格納するダイクストラ経路計算ステップ（ステップ１）と、
探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する受信装置数カウントステップ（ステップ２）と、
送信伝送装置を訪問済記憶手段に格納し、探索対象装置とする初期設定ステップ（ステップ３）と、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定ステップ（ステップ４）と、
マルチキャスト判定ステップにおいて、ユニキャスト伝送装置と判定されたときは、受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として、候補装置記憶手段に格納するユニキャスト装置用候補装置決定ステップ（ステップ５）と、
マルチキャスト判定ステップにおいて、探索対象装置がマルチキャスト伝送装置であるときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、候補装置記憶手段に格納すると共に、再選択された候補装置までのリンクコストと経路を探索経路記憶手段に格納するマルチキャスト装置用候補装置決定ステップ（ステップ６）と、
候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定ステップ（ステップ７）と、
訪問済装置記憶手段に全ての受信装置が設定されている場合に（ステップ８）、探索経路記憶手段に格納されている経路を出力する出力ステップ（ステップ９）と、を行う。
【００１７】
本発明（請求項２）は、マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算方法であって、
通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、探索経路記憶手段に格納するダイクストラ経路計算ステップと、
探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する第１の受信装置数カウントステップと、
送信伝送装置を訪問済記憶手段に格納し、探索対象装置とする初期設定ステップと、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定ステップと、
マルチキャスト判定ステップにおいて、ユニキャスト伝送装置であると判定されたときは、受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として選択し、候補装置記憶手段に格納するユニキャスト装置用候補装置決定ステップと、
選択した候補装置までの経路以外を切断したトポロジに対して、再び、全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト経路計算方法によってマルチキャスト経路を計算し、探索経路記憶手段に格納するステップと、
探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する第２の受信装置数カウントステップと、
マルチキャスト判定ステップにおいて、マルチキャスト伝送装置であると判定されたときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、候補装置記憶手段に格納すると共に、再選択された候補装置までのリンクコストと経路を探索経路記憶手段に格納するマルチキャスト装置用候補装置決定ステップと、
候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定ステップと、
訪問済装置記憶手段に全ての受信装置が設定されている場合に、探索経路記憶手段に格納されている経路を出力する出力ステップと、を行う。
【００１８】
図２は、本発明の原理構成図である。
【００１９】
本発明（請求項３）は、マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算装置であって、
各伝送装置の送信伝送装置までの経路とリンクコストを記憶する探索経路記憶手段１１２と、
探索された伝送装置を訪問済装置として記憶する訪問済装置記憶手段１１１と、
候補装置を記憶する候補装置記憶手段１１３と、
カウントされた受信装置数を記憶する受信装置数記憶手段１１４と、
通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、探索経路記憶手段１１２に格納するダイクストラ経路計算手段１２０と、
探索経路記憶手段１１２から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段１１４に格納する受信装置数カウント手段１１０と、
送信伝送装置を訪問済記憶手段１１１に格納し、探索対象装置とする初期設定手段１０３と、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定手段１０４と、
マルチキャスト判定手段１０４において、ユニキャスト伝送装置と判定されたときは、受信装置数記憶手段１１４に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として、候補装置記憶手段１１３に格納するユニキャスト装置用候補装置決定手段と、
マルチキャスト判定手段１０４において、探索対象装置がマルチキャスト伝送装置であるときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、候補装置記憶手段１１３に格納すると共に、再選択された候補装置までのリンクコストと経路を探索経路記憶手段１１２に格納するマルチキャスト装置用候補装置決定手段１０６と、
候補装置記憶手段１１３に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段１１１に格納する探索対象装置決定手段１０８と、
訪問済装置記憶手段１１１に全ての受信装置が設定されている場合に、探索経路記憶手段１１２に格納されている経路を出力する経路完了判定手段１０９と、を有する。
【００２０】
本発明（請求項４）は、マルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網において、入力された通信網のトポロジ情報と経路設定制約条件を用いてダイクストラマルチキャスト経路計算方法を適用して、マルチキャスト経路を計算するマルチキャスト経路計算装置であって、
各伝送装置の送信伝送装置までの経路とリンクコストを記憶する探索経路記憶手段と、
探索された伝送装置を訪問済装置として記憶する訪問済装置記憶手段と、
候補装置を記憶する候補装置記憶手段と、
カウントされた受信装置数を記憶する受信装置数記憶手段と、
通信網内の全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト計算方法によって、マルチキャスト経路を計算し、探索経路記憶手段に格納するダイクストラ経路計算手段と、
探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する第１の受信装置数カウント手段と、
送信伝送装置を訪問済記憶手段に格納し、探索対象装置とする初期設定手段と、
探索対象装置がユニキャスト伝送装置かマルチキャスト伝送装置かの判定を行うマルチキャスト判定手段と、
マルチキャスト判定手段において、ユニキャスト伝送装置であると判定されたときは、受信装置数記憶手段に格納されている受信装置数が最大の経路にある隣接装置の一つを候補装置として選択し、候補装置記憶手段に格納するユニキャスト装置用候補装置決定手段と、
選択した候補装置までの経路以外を切断したトポロジに対して、再び、全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラマルチキャスト経路計算方法によってマルチキャスト経路を計算し、探索経路記憶手段に格納する経路再計算手段と、
探索経路記憶手段から出力された経路を用いて、ユニキャスト伝送装置における各経路が到達することができる受信装置数を計算し、受信装置数記憶手段に格納する第２の受信装置数カウント手段と、
マルチキャスト判定手段において、マルチキャスト伝送装置であると判定されたときは、当該探索対象装置の隣接装置の中から選択した候補装置が、既にユニキャスト伝送装置から選択された候補装置である場合、該ユニキャスト伝送装置の隣接装置の中から候補装置を再選択し、候補装置記憶手段に格納すると共に、再選択された候補装置までのリンクコストと経路を探索経路記憶手段に格納するマルチキャスト装置用候補装置決定手段と、
候補装置記憶手段に格納されている候補装置の中からリンクコストが最小の候補装置を選択し、訪問済装置として訪問済装置記憶手段に格納する探索対象装置決定手段と、
訪問済装置記憶手段に全ての受信装置が設定されている場合に、探索経路記憶手段に格納されている経路を出力する経路完了判定手段と、を有する。
【００２１】
本発明（請求項５）は、探索経路記憶手段、訪問済装置記憶手段、候補装置記憶手段、受信装置数記憶手段と、を有するコンピュータを、
請求項３または請求項４に記載された手段を有するマルチキャスト経路計算装置として、機能させるマルチキャスト経路計算プログラムである。
【００２２】
本発明（請求項６）は、探索経路記憶手段、訪問済装置記憶手段、候補装置記憶手段、受信装置数記憶手段と、を有するコンピュータを、
請求項３または請求項４に記載された手段を有するマルチキャスト経路計算装置として、機能させるプログラムを格納した記憶媒体である。
【発明の効果】
【００２３】
上記のように、本発明によれば、マルチキャスト伝送装置とユニキャスト伝送装置が通信網上で混在しているシステムにおいて、まず、全ての伝送装置をマルチキャスト伝送装置と見做してダイクストラにて経路計算を行い、マルチキャスト伝送装置の場合は、送信伝送装置からのリンクコストが最小になるように分岐していき、ユニキャスト伝送装置については、経路計算結果の分岐経路のうちから、到達可能な受信伝送装置の数が多い経路を選択する。これにより、ユニキャスト伝送装置での分岐の抑制、伝送コストが小さい経路の選択を実現することができる。
【発明を実施するための最良の形態】
【００２４】
以下、図面と共に本発明の実施の形態を説明する。
【００２５】
［第１の実施の形態］
図３は、本発明の第１の実施の形態における経路計算装置の構成を示す。
【００２６】
同図に示す経路計算装置は、トポロジ情報記憶部１０１、制約条件記憶部１０２、初期設定部１０３、マルチキャスト判定制御部１０４、マルチキャスト判定部１０５、マルチキャスト装置用候補装置決定部１０６、ユニキャスト装置用候補装置決定部１０７、探索対象装置決定部１０８、経路完了判定部１０９、受信装置数カウント部１１０、訪問済装置記憶部１１１、探索経路記憶部１１２、候補装置記憶部１１３、受信装置数記憶部１１４から構成される。このうち、トポロジ情報記憶部１０１、制約条件記憶部１０２、訪問済装置記憶部１１１、探索経路記憶部１１２、候補装置記憶部１１３、受信装置数記憶部１１４は、メモリ、ハードディスク等の記憶媒体に格納されているものとする。
【００２７】
トポロジ情報記憶部１０１では、入力された装置間の接続関係、各装置のマルチキャスト配信能力、装置間のリンクコストなどを記憶する。
【００２８】
制約条件記憶部１０２では、送信装置、受信装置等の出力すべき経路の制約条件を記憶する。
【００２９】
初期設定部１０３では、制約条件記憶部１０２より送信装置の情報（例えば、装置ＩＤ）を取り出し、訪問済装置記憶部１１１に保存する。また、その送信装置の情報（例えば、装置ＩＤ）を探索対象装置として、マルチキャスト判定制御部１０４に送る。
【００３０】
マルチキャスト判定制御部１０４は、初期設定部１０３から探索対象装置の情報（例えば、装置ＩＤ）を受け取り、マルチキャスト判定部１０５に対して“全ての装置をマルチキャスト伝送装置とみなす”制御信号と探索対象装置の情報（例えば、装置ＩＤ）を送る。さらに、探索経路記憶部１１２に対して、計算終了後、受信装置数カウント部１１０に出力するよう信号を送る。また、受信伝送装置数カウント部１１０より、受信伝送装置数設定完了の信号を受けた場合は、訪問済装置記憶部１１１、探索経路記憶部１１２、候補装置記憶部１１３のデータをリセットし、初期設定部１０３に対して再開の制御信号を送る。
【００３１】
マルチキャスト判定部１０５では、マルチキャスト判定制御部１０４から制御信号を受けている場合は、受け取った探索対象装置の情報（例えば、装置ＩＤ）をマルチキャスト装置用候補装置決定部１０６に送る。制御信号を受けていない場合は、トポロジ情報記憶部１０１よりマルチキャスト能力を読み出し、探索対象装置がマルチキャスト装置からユニキャスト装置かを判定し、その判定結果によって、探索対象装置をユニキャスト装置用候補装置決定部１０７、または、マルチキャスト用候補装置決定部１０６に送る。
【００３２】
ユニキャスト用候補装置決定部１０７では、トポロジ情報記憶部１０１より、探索対象装置の隣接装置を取得する。その探索対象装置における各隣接装置の受信装置数を受信装置数記憶部１１４より取得し、受信伝送装置数が最大の隣接装置を一つ選択し、その装置を候補装置記憶部１１３に設定する。また、送信伝送装置から、その選択した候補装置までのリンクコストと経路を探索経路記憶部１１２に設定する。
【００３３】
マルチキャスト用候補装置決定部１０６では、トポロジ情報記憶部１０１より、探索対象装置の隣接装置と隣接装置とのリンクコストを取得する。各隣接装置の探索対象装置経由のリンクコストを計算し、探索経路記憶部１１２に設定されていないか、もしくは設定されているリンクコストより小さい場合、その隣接装置の情報（例えば、装置ＩＤ）を候補装置記憶部１１３に設定する。その際、この候補装置の情報が既に候補装置記憶部１１３に設定されていて、他のユニキャスト伝送装置からの候補装置である場合、そのユニキャスト伝送装置の情報（例えば、装置ＩＤ）をユニキャスト用候補装置決定部１０７に送る。
【００３４】
探索対象装置決定部１０８では、候補装置記憶部１１３に設定されているリンクコストが最小の候補装置を読み出し、探索対象装置とし、その装置の情報（例えば、装置ＩＤ）を経路完了判定部１０９に送る。また、その装置の情報（例えば、装置ＩＤ）を候補装置記憶部１１３から削除し、訪問済装置記憶部１１１に保存する。
【００３５】
経路完了判定部１０９では、訪問済装置記憶部１１１に制約条件記憶部１０２にある全受信装置が設定されているかを判別し、全て含まれている場合は経路完了とし、探索経路記憶部１１２に完了の信号を送信する。全て含まれていない場合は、受信した探索対象装置の情報をマルチキャスト判定部１０５へ送る。
【００３６】
探索経路記憶部１１２は、経路完了判定部１０９からの完了の信号を受けて、記憶されている経路を出力する。マルチキャスト判定制御部１０４から制御信号を受けている場合は、受信装置数カウント部１１０に出力し、制御信号を受けていない場合は、経路を出力して正常終了する。
【００３７】
受信装置数カウント部１１０では、探索経路記憶部１１２と制約条件記憶部１０２を参照して、受信したマルチキャスト経路を探索し、全ユニキャスト伝送装置の各方路における到達できる受信伝送装置をカウントし、その数を受信装置数記憶部１１４に設定する。また、設定完了後、マルチキャスト判定部１０５に受信伝送装置数設定完了の信号を送信する。
【００３８】
図４〜図８は、本発明の第１の実施の形態における動作のフローチャートである。
【００３９】
以下のフローチャートにおいて、ｓは、送信伝送装置を示し、ｖは、探索対象伝送装置（通常、経路が決定したばかりの伝送装置）を示す。
【００４０】
ステップ１０１）  予め、全装置をマルチキャストとみなし、ダイクストラ方式にて経路を計算し、探索経路記憶部１１２に格納する。
【００４１】
ステップ１０２）  予め、計算した探索経路記憶部１１２の経路を探索し、ユニキャスト装置の次ホップ装置を通って到達することができる受信装置数を受信装置数記憶部１１４に格納する。
【００４２】
ステップ１０３）  初期設定部１０３において、送信伝送装置ｓを探索対象伝送装置ｖとする。
【００４３】
ステップ１０４）  マルチキャスト判定部１０５において、トポロジ情報記憶部１０１を参照して、探索対象装置ｖがマルチキャスト伝送装置であるかを判定する。マルチキャスト伝送装置である場合は、ステップ１０５に移行し、そうでない場合は、ステップ２００［処理３］に移行する。
【００４４】
ステップ１０５）  探索対象装置ｖに隣接し、確定した経路上におけるｖの一つ前の伝送装置ではない伝送装置をｆとする。なお、ｆが一つも存在しない場合は、以下の処理を実行しない。
【００４５】
マルチキャスト装置用候補装置決定部１０６は、探索対象装置ｖ経由の送信装置ｓと伝送装置ｆ間のリンクコストを計算し、その値をｄｆとする。
【００４６】
ステップ１０６）  マルチキャスト装置用候補決定部１０６は、伝送装置ｆのリンクコストｄｆを取得して、訪問済装置記憶部１１１と候補装置記憶部１１３を参照して、伝送装置ｆが訪問済装置、または、他の装置の候補装置かを判定する。
【００４７】
訪問済装置でない場合は、ステップ１０８に移行し、訪問済装置である場合は、ステップ１０７に移行する。
【００４８】
ステップ１０７）  訪問済装置である場合は、既に計算されているリンクコストがステップ１０５で計算されたリンクコストｄｆより大きいかを判定し、大きい場合はステップ１０９に移行し、そうでない場合は、ステップ１１４に移行する。
【００４９】
ステップ１０８）  マルチキャスト用候補装置決定部１０６は、送信伝送装置ｓから伝送装置ｆまでの探索装置ｖ経由の経路とリンクコストを探索経路記憶部１１２に保存し、ｆを候補装置とする。［処理２］
ステップ１０９）  マルチキャスト用候補装置決定部１０６は、探索経路記憶部１１２に保存されている経路におけるｆの一つ前の伝送装置をｐとする。
【００５０】
ステップ１１０）  上記のステップ１０８と同様の動作を行う。
【００５１】
ステップ１１１）  マルチキャスト判定部１０５において、伝送装置ｐがマルチキャスト伝送装置かを判定し、マルチキャスト伝送装置であれば、ステップ１１４に移行する。
【００５２】
ステップ１１２）  マルチキャスト伝送装置でなければ、ｐを探索装置ｖとする。
【００５３】
ステップ１１３）  後述するステップ２００〜ステップ２０７［処理３］の処理を行う。
【００５４】
ステップ１１４）  マルチキャスト伝送装置であれば、ユニキャスト用候補装置決定部１０７において、候補装置記憶部１１３を参照して、候補装置が存在するかを判定し、存在する場合は、ステップ１２０に移行する。
【００５５】
ステップ１１５）  候補装置が存在しない場合は、探索対象装置決定部１０８において、送信伝送装置ｓからのリンクコストが最小となる候補装置をｉとする。複数ある場合は、その他の条件を用いて一つを選択する。そのｉまでの経路を決定し、ｉを候補装置記憶部１１３から削除し、ｉを訪問済装置として訪問済装置記憶部１１１に保存する。
【００５６】
ステップ１１６）  候補装置ｉを探索装置ｖとする。
【００５７】
ステップ１１７）  経路完了判定部１０９は、訪問済装置記憶部１１１を参照して決定した経路に全ての受信伝送装置が含まれているかを判定し、含まれている場合は、ステップ１１８に移行し、含まれていない場合はステップ１０４に移行する。
【００５８】
ステップ１１８）  経路完了判定部１０９は、受信装置に通じない経路を探索経路記憶部１１２から削除する。
【００５９】
ステップ１１９）  探索経路記憶部１１２の経路を決定した経路として出力する。
【００６０】
ステップ１２０）  「解なし」を出力し、強制終了する。
【００６１】
［処理３：ステップ２００〜ステップ２０７］
ステップ２００）  ユニキャスト装置用候補装置決定部１０７は、探索対象伝送装置ｖに隣接する伝送装置をｆとする。
【００６２】
ステップ２０１）  ｆが複数存在するかを判定し、存在する場合は、ステップ２０２に移行し、存在しない場合はステップ２０５に移行する。
【００６３】
ステップ２０２）  ユニキャスト装置用候補装置決定部１０７は、受信装置数記憶部１１４を参照して、記憶している受信装置数が多い伝送装置を一つ選択し、同数のものが複数ある場合は、物理リンク数や、マルチキャスト配信能力などを用いた優先付け条件によって決定する。
【００６４】
ステップ２０３）  前述のステップ１０５の処理を行う。
【００６５】
ステップ２０４）  前述のステップ１０８の処理を行い、ステップ１１４に移行する。
【００６６】
ステップ２０５）  ステップ２０１において、ｆが複数存在しない場合、ｆが１つは存在しているかを判定し、１つ存在している場合はステップ２０６に移行し、一つも存在していない場合は、ステップ１１４に移行する。
【００６７】
ステップ２０６）  前述のステップ１０５の処理を行う。
【００６８】
ステップ２０７）  前述のステップ１０８の処理を行い、ステップ１１４に移行する。
【００６９】
［第２の実施の形態］
図９は、本発明の第２の実施の形態における経路計算装置の構成を示す。なお、前述の第１の実施の形態における図３の構成と同一構成部分には同一符号を付す。
【００７０】
同図に示す経路計算装置は、トポロジ情報記憶部１０１、ダイクストラ用トポロジ情報記憶部２０１、制約条件記憶部１０２、初期設定部１０３、ダイクストラ制御部２０２、マルチキャスト判定部１０５、マルチキャスト装置用候補装置決定部１０６、ユニキャスト装置用候補装置決定部１０７、探索対象装置決定部１０８、経路完了判定部１０９、受信装置カウント部１１０、訪問済装置記憶部１１１、ダイクストラ用訪問済装置記憶部２０３、探索経路記憶部１１２、ダイクストラ用探索経路記憶部２０４、候補装置記憶部１１３、ダイクストラ用候補装置記憶部２０５、受信装置数記憶部１１４から構成される。このうち、トポロジ情報記憶部１０１、制約条件記憶部１０２、訪問済装置記憶部１１１、探索経路記憶部１１２、候補装置記憶部１１３、受信装置数記憶部１１４、ダイクストラ用訪問済装置記憶部２０３、ダイクストラ用探索経路記憶部２０４、ダイクストラ用候補装置記憶部２０５は、メモリ、ハードディスク等の記憶媒体に格納されているものとする。
【００７１】
トポロジ情報記憶部１０１では、入力された装置間の接続関係、各装置のマルチキャスト配信能力、装置間のリンクコストなどを記憶する。
【００７２】
ダイクストラ用トポロジ情報記憶部２０１では、ダイクストラ用に用いるトポロジ情報を記憶し、初回は、トポロジ情報記憶部１０１と同じ情報を設定する。
【００７３】
制約条件記憶部１０２では、送信装置、受信装置などの出力すべき経路の制約条件を記憶する。
【００７４】
初期設定部１０３では、制約条件記憶部１０２より送信装置を取り出し、訪問済装置記憶部１１１に保存する。また、その送信装置の情報（例えば、装置ＩＤ）を探索対象装置として、ダイクストラ制御部２０２に送る。
【００７５】
ダイクストラ制御部２０２は、初回に初期設定部１０３より探索対象装置を受信、または、ユニキャスト伝送装置用候補装置決定部１０７より制御信号を受信した場合、マルチキャスト判定部１０５に対して、“全ての装置をマルチキャスト伝送装置とみなす”ように制御信号と探索対象装置の情報（例えば、装置ＩＤ）を送る。さらに、探索経路記憶部１１２に対して、計算終了後、受信装置数カウント部１１０に出力するよう信号を送る。マルチキャスト用候補装置決定部１０６、探索対象装置決定部１０８、経路完了判定部１０９に対して、ダイクストラにて動作するように制御信号を送る。
【００７６】
また、ダイクストラ制御部２０２は、受信装置数カウント部１１０より、受信伝送装置数設定完了の信号を受けた場合は、ダイクストラ用訪問済装置記憶部２０３、ダイクストラ用探索経路記憶部２０４、ダイクストラ用候補装置記憶部２０５をリセットし、初回は、初期設定部１０３に対して再開の制御信号を送信し、２回目以降は、ユニキャスト装置用候補装置決定部１０７に再開の制御信号を送信する。
【００７７】
マルチキャスト判定部１０５では、ダイクストラ制御部２０２から制御信号を受けている場合は、受け取った探索対象装置の情報（例えば、装置ＩＤ）をマルチキャスト装置用候補装置決定部１０６に送る。制御信号を受けていない場合は、トポロジ情報記憶部１０１よりマルチキャスト能力を読み出し、探索対象装置がマルチキャスト装置か、ユニキャスト装置かを判定し、その判定結果によって、探索対象装置をユニキャスト装置用候補装置決定部１０７、または、マルチキャスト用候補装置決定部１０６に送る。
【００７８】
ユニキャスト用候補装置決定部１０７では、トポロジ情報記憶部１０１より、探索対象装置の隣接装置を取得する。その探索装置における各隣接装置の受信装置数を受信装置数記憶部１１４より取得し、受信伝送装置数が最大の隣接装置を一つ選択し、その装置を候補装置記憶部１１３に設定する。また、送信伝送装置から、その選択した候補装置までのリンクコストと経路を探索経路記憶部１１２に設定する。選択されなかったリンクをダイクストラ用トポロジ情報記憶部２０１から削除する。ダイクストラ制御部２０２にダイクストラ計算を開始するように信号を送信する。また、ダイクストラ制御部２０２より、ダイクストラ経路計算が完了した信号を受けた場合、処理を探索対象装置決定部１０８に移す。
【００７９】
マルチキャスト用候補装置決定部１０６では、ダイクストラ制御部２０２より制御信号を受信していない場合、トポロジ情報記憶部１０１より探索対象装置の隣接装置と隣接装置とのリンクコストを取得する。各隣接装置の探索対象装置経由のリンクコストを計算し、探索経路記憶部１１２に設定されていないか、もしくは設定されているリンクコストより小さい場合、その隣接装置を候補装置記憶部１１３に設定する。その際、その候補装置が既に候補装置記憶部１１３に設定されていて、他のユニキャスト伝送装置からの候補装置である場合、そのユニキャスト伝送装置の情報（例えば、装置ＩＤ）をユニキャスト用候補装置決定部１０７に送る。
【００８０】
また、マルチキャスト用候補装置決定部１０６では、ダイクストラ制御部２０２より制御信号を受信している場合、ダイクストラ用トポロジ情報記憶部２０１より、探索対象装置の隣接装置と隣接装置とのリンクコストを取得する。各隣接装置の探索対象装置経由のリンクコストを計算し、ダイクストラ用探索経路記憶部２０４に設定されていないか、もしくは、設定されているリンクコストより小さい場合、その隣接装置をダイクストラ用候補装置記憶部２０５に設定する。
【００８１】
探索対象装置決定部１０８では、ダイクストラ制御部２０２より制御信号を受信していない場合、候補装置記憶部１１３に設定されているリンクコストが最小の候補装置を呼び出し対象探索対象装置とし、呼び出し対象探索対象装置の情報（例えば、装置ＩＤ）を当該経路完了判定部１０９に送る。また、その装置の情報（例えば、装置ＩＤ）を候補装置記憶部１１３から削除し、訪問済装置記憶部１１１に保存する。
【００８２】
また、探索対象装置決定部１０８では、ダイクストラ制御部２０２より制御信号を受信している場合は、ダイクストラ用候補装置記憶部２０５に設定されているリンクコストが最小の候補装置を呼び出し、探索対象装置とし、当該探索対象装置の情報（例えば、装置ＩＤ）を経路完了判定部１０９に送る。また、その装置の情報（例えば、装置ＩＤ）をダイクストラ候補装置記憶部２０５から削除し、ダイクストラ訪問済記憶部２０３に保存する。
【００８３】
経路完了判定部１０９では、ダイクストラ制御部２０２より制御信号を受信していない場合、訪問済装置記憶部１１１に制約条件記憶部１０２にある全受信装置が設定されているかを判別し、全て含まれている場合は、経路完了とし、探索経路記憶部１１２に完了の信号を送信する。全て含まれていない場合は、受信した探索対象装置の情報（例えば、装置ＩＤ）をマルチキャスト判定部１０５に送る。
【００８４】
ダイクストラ制御部２０２により制御情報を受信している場合、ダイクストラ用訪問済装置記憶部２０３に制約条件記憶部１０２にある全受信装置が設定されているかを判別し、全て含まれている場合は経路完了とし、ダイクストラ用探索経路記憶部２０４に完了の信号を送信する。全て含まれていない場合は、受信した探索対象装置の情報（例えば、装置ＩＤ）をマルチキャスト判定部１０５に送る。
【００８５】
探索経路記憶部１１２は、経路完了判定部１０９からの完了の信号を受けて、記憶されている経路を出力する。
【００８６】
ダイクストラ用探索経路記憶部２０４は、経路完了判定部１０９からの完了信号を受けて、記憶されている経路を受信装置数カウント部１１０に出力する。
【００８７】
受信装置数カウント部１１０では、受信したマルチキャスト経路を探索し、全ユニキャスト伝送装置の各方路における到達できる受信伝送装置をカウントし、その数を受信装置数記憶部１１４に設定する。また、設定完了後、ダイクストラ制御部２０２に受信伝送装置数設定完了の信号を送信する。
【００８８】
次に、上記の構成における動作を説明する。
【００８９】
図１０〜図１４は、本発明の第２の実施の形態における動作のフローチャートである。
【００９０】
以下のフローチャートにおいて、ｓは、送信伝送装置を示し、ｖは、探索対象伝送装置（通常、経路が決定したばかりの伝送装置）を示す。
【００９１】
［処理４：ステップ３０１〜ステップ３０３］
ステップ３０１）  ダイクストラ制御部２０２は、ダイクストラ用の各記憶部と受信装置数用記憶部１１４のデータをリセットする。
【００９２】
ステップ３０２）  ダイクストラ用トポロジ情報記憶部２０１のダイクストラ用トポロジを用いて全装置をマルチキャストとみなし、ダイクストラ方式にて経路を計算する。
【００９３】
ステップ３０３）  計算した経路を探索し、ユニキャスト装置の次ホップ装置を通って到達することができる受信装置数を受信装置数記憶部１１４に設定する。
【００９４】
ステップ３０４）  送信伝送装置ｓを探索対象伝送装置ｖとする。
【００９５】
ステップ３０５）  マルチキャスト判定部１０５において、探索対象伝送装置ｖがマルチキャスト伝送装置であるかを判定し、マルチキャスト伝送装置である場合には、ステップ３０６に移行し、そうでない場合は、ステップ４００に移行する。
【００９６】
ステップ３０６）  ここで、探索対象伝送装置ｖに隣接し、確定した経路上におけるｖの一つ前の伝送装置ではない伝送装置をｆとする。なお、ｆが一つも存在しない場合は、以下の処理は実行しない。
【００９７】
［処理１：ステップ３０７］
ステップ３０７）  マルチキャスト装置用候補装置決定部１０６は、探索対象伝送装置ｖ経由の送信伝送装置ｓとｆ間のリンクコストを計算し、それをｄｆとする。
【００９８】
ステップ３０８）  訪問済装置記憶部１１１と候補装置記憶部１１３を参照し、ｆが訪問済装置であるかを判定し、訪問済装置または、他の装置の候補装置である場合は、ステップ３０９へ移行し、訪問済装置または、他の装置の候補装置でない場合は、ステップ３１０に移行する。
【００９９】
ステップ３０９）  マルチキャスト装置用候補装置決定部１０６は、既に計算されているリンクコストがｄｆより大きいかを判定し、大きい場合はステップ３１１に移行し、そうでない場合は、ステップ３１６に移行する。
【０１００】
［処理２：ステップ３１０］
ステップ３１０）  ｓからｆまでのｖ経由の経路とリンクコストを候補装置記憶部１１３に保存し、ｆを候補装置する。ステップ３１６に移行する。
【０１０１】
ステップ３１１）  探索経路記憶部１１２に保存されている経路におけるｆの一つ前の伝送装置をｐとする。
【０１０２】
ステップ３１２）  上記のステップ３１０と同様の処理を行う。
【０１０３】
ステップ３１３）  マルチキャスト判定部１０５は、伝送装置ｐがマルチキャスト伝送装置かを判定し、マルチキャスト伝送装置であればステップ３１６に移行し、そうでなければ、ステップ３１４に移行する。
【０１０４】
ステップ３１４）  ｐを探索対象伝送装置ｖとする。
【０１０５】
ステップ３１５）  ステップ４００〜ステップ４０９の処理［処理３］を行う。
【０１０６】
ステップ３１６）  全てのｆに対して以下の処理を実行する。
【０１０７】
ステップ３１７）  マルチキャスト装置用候補装置決定部１０６は、候補装置記憶部１１３を参照して、ｆが存在するかを判定し、存在する場合はステップ３１８に移行し、存在しない場合は、ステップ３２３に移行する。
【０１０８】
ステップ３１８）  探索対象装置決定部１０８は、ｓからのリンクコストが最小となる候補装置をｉとする。複数ある場合は、その他の条件を用いて一つを選択する。そのｉまでの経路を決定し、ｉを候補装置記憶部１１３から削除する。ｉを訪問済装置として訪問済装置記憶部１１１に保存する。
【０１０９】
ステップ３１９）  探索対象装置決定部１０８は、ｉを探索対象伝送装置ｖとする。
【０１１０】
ステップ３２０）  経路完了判定部１０９は、決定した経路に全ての受信装置が含まれているかを判定し、含まれている場合はステップ３２１に移行し、含まれていない場合はステップ３０５に移行する。
【０１１１】
ステップ３２１）  受信装置に通じない経路を探索経路記憶部１１２から削除する。
【０１１２】
ステップ３２２）  探索経路記憶部１１２の決定した経路を出力し、処理を終了する。
【０１１３】
ステップ３２３）  ステップ３１７において候補が存在しない場合には、「解なし」を出力し、強制終了する。
【０１１４】
［処理３：ステップ４００〜４０９］
ステップ４００）  ステップ３０５において、ｖがマルチキャスト伝送装置でないと判断された場合、ユニキャスト用候補装置決定部１０７は、ｖに隣接する伝送装置をｆとする。
【０１１５】
ステップ４０１）  ｆが複数存在するかを判定し、複数存在する場合はステップ４０２に移行し、複数存在しない場合はステップ４０７に移行する。
【０１１６】
ステップ４０２）  受信装置数記憶部１１４を参照して、記憶している受信装置数が多い伝送装置を一つ選択する。同数のものが複数ある場合は、物理リンク数や、マルチキャスト配信能力などを用いた優先付け条件によって決定する。
【０１１７】
ステップ４０３）  決定されなかった装置とｖのリンクを切断したトポロジをダイクストラ用トポロジとしてダイクストラ用トポロジ情報記憶部２０１に保存する。
【０１１８】
ステップ４０４）  ステップ３０１〜ステップ３０３［処理４］を行う。
【０１１９】
ステップ４０５）  ステップ３０７［処理１］を行う。
【０１２０】
ステップ４０６）  ステップ３１０［処理２］を行う。
【０１２１】
ステップ４０７）  ステップ４０１において、ｆが複数でないとき、ｆが一つは存在するかを判定し、存在する場合は、ステップ４０８に移行し、１つも存在しない場合はステップ３１７に移行する。
【実施例】
【０１２２】
以下、本発明の実施例を説明する。
【０１２３】
［第１の実施例］
図１５、図１６を用いて、第１の実施例を説明する。
【０１２４】
以下の例では、送信伝送装置を｛Ａ｝とし、受信伝送装置を｛Ｂ，Ｉ，Ｋ，Ｌ｝として説明する。
【０１２５】
図１５、図１６に示す各伝送装置Ａ，Ｂ，Ｄ，Ｅ，Ｆ，Ｇ，Ｉ，Ｊ，Ｋ，Ｌはマルチキャスト伝送装置であり、Ｃ，Ｈ，はユニキャスト伝送装置である。
【０１２６】
図１５（ａ）にある接続関係とリンクコストを含むトポロジ情報及び送信伝送装置、受信伝送装置の入力を受け付ける。
【０１２７】
（１）全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラ方式にて、マルチキャスト経路を計算する。その経路によって、全ユニキャスト経路の各方路の受信伝送装置数をカウントする（図１５（ｂ））。
【０１２８】
ユニキャスト伝送装置ＣのＥへの方路は、Ｉ，Ｋ，Ｌに通じるため受信伝送装置数は、３となる。Ｄへの方路は０となる。同様に、ＨのＪへの方路は、Ｋ，Ｌに通じるため受信伝送装置数は２となり、Ｉへの方路は、１となる。
【０１２９】
（２）送信伝送装置Ａを訪問済装置と探索対象装置とし、かつ、候補装置、訪問済装置、探索経路等をリセットし、マルチキャスト経路の計算を再開する。
【０１３０】
（３）探索対象装置Ａは、マルチキャスト伝送装置で、ＢとＣが候補装置となる（図１５（ｃ））。
【０１３１】
（４）Ｂを次の探索対象装置とし、訪問済装置とする。
【０１３２】
（５）Ｂから候補装置は存在しないので、Ｃを次の探索対象装置とし、訪問済装置とする。
【０１３３】
（６）Ｃは、ユニキャスト伝送装置であるため、受信伝送装置数を用いて、一つの候補装置を選択する。この場合、Ｅが受信伝送装置数３で最多となり、Ｅを候補装置とする。
【０１３４】
（７）候補装置のうち、Ｅを次の探索対象装置とし、訪問済装置とする（図１５（ｄ））。
【０１３５】
（８）Ｅは、マルチキャスト伝送装置のため、ＧとＨを候補装置とする（図１６（ｅ））。
【０１３６】
（９）Ｇを次の探索対象装置とし、訪問済装置とする。
【０１３７】
（１０）Ｇには、候補装置が存在しないので、Ｈを次の探索対象装置とし、訪問済装置とする。
【０１３８】
（１１）Ｈは、ユニキャスト伝送装置であるので、受信伝送装置数を一つの候補装置を選択し、受信伝送装置数２で最多のＪを候補装置とする（図１６（ｆ））。
【０１３９】
（１２）同様に探索を進め、図１６（ｇ）の経路が計算される。
【０１４０】
（１３）不要な経路（Ｅ−Ｇ間）を削除し、図１６（ｈ）を出力する。
【０１４１】
［第２の実施例］
図１７〜図１９を用いて、第２の実施例を説明する。
【０１４２】
以下では、送信伝送装置を｛Ａ｝とし、受信伝送装置を｛Ｃ，Ｄ，Ｇ｝として説明する。
【０１４３】
図１７〜図１９に示す各伝送装置Ａ，Ｃ，Ｄ，Ｅ，Ｇはマルチキャスト伝送装置であり、Ｂ，Ｆ，Ｈ，Ｉはユニキャスト伝送装置である。
【０１４４】
（１）全ての伝送装置をマルチキャスト伝送装置とみなして、ダイクストラ方式にてマルチキャスト経路を計算する。その経路によって、全ユニキャスト経路の各方路の受信伝送装置数をカウントする（図１７（ｂ））。
【０１４５】
ユニキャスト伝送装置ＩのＥへの方路は、Ｄに通じるため受信伝送装置数は、１となる。Ｈへの方路は０となる。同様に、ＢのＣへの方路は、Ｃに通じるため、受信伝送装置数は、１となり、Ｇへの方路は、１となる。
【０１４６】
（２）送信伝送装置Ａを訪問済装置と探索対象装置とし、かつ、候補装置、訪問済装置、探索経路等をリセットし、マルチキャスト経路の計算を再開する。
【０１４７】
（３）探索対象Ａは、マルチキャスト伝送装置で、ＢとＣが候補装置となる（図１７（ｃ））。
【０１４８】
（４）リンクコストが最小のＢを次の探索対象装置とし、訪問済装置とする。
【０１４９】
（５）Ｂはユニキャスト伝送装置であるため、受信伝送装置数を用いて、一つの候補装置を選択する。この場合、ＣとＧが受信伝送装置数１で最多となるが、物理リンク数などによってＣを候補装置とする（図１８（ｄ））。
【０１５０】
（６）Ｂにおいて候補装置として選択されなかったＧ、Ｆを切断したトポロジに対して、ダイクストラ方式を用いて計算し、再度、受信伝送装置数を再設定する（図１８（ｅ））。
【０１５１】
（７）再び探索を再開し、Ｉを次の探索対象装置とし、探索済装置とする。
【０１５２】
（８）Ｉはユニキャスト伝送装置であるため、受信伝送装置数を用いて候補装置を選択する。この場合は、ＨとＥは同じ受信伝送装置数であるが、物理リンク数等でＨを候補装置とする（図１８（ｆ））。
【０１５３】
（９）ＩとＥ間のリンクを削除したトポロジを用いてダイクストラで経路を計算し、受信伝送装置数を再設定する（図１９（ｇ））。
【０１５４】
（１０）Ｃを次の探索対象装置とし、訪問済装置とする。
【０１５５】
（１１）Ｇを次の探索対象装置とし、訪問済装置とする（図１９（ｈ））。
【０１５６】
（１２）同様に探索を進めていき、図１９（ｉ）を出力する。
【０１５７】
また、上記の図３、図９に示す、初期設定部１０３、マルチキャスト判定制御部１０４、マルチキャスト判定部１０５、マルチキャスト装置用候補装置決定部１０６、ユニキャスト装置用候補装置決定部１０７、探索対象装置決定部１０８、経路完了判定装置１０９、受信装置カウント部１１０、及び、ダイクストラ経路計算方法を用いた経路計算の処理をプログラムとして構築し、コンピュータに実行させる、または、ネットワークを介して流通させることが可能である。
【０１５８】
また、構築したプログラムを、ハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、コンピュータにインストールして実行させる、または、配布することが可能である。
【０１５９】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１６０】
本発明は、ＭＰＬＳ技術のようなマルチキャスト伝送装置とユニキャスト伝送装置が混在した通信網に対してマルチキャスト経路を設定する技術に適用可能である。
【図面の簡単な説明】
【０１６１】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１の実施の形態における経路計算装置の構成図である。
【図４】本発明の第１の実施の形態における動作のフローチャート（その１）である。
【図５】本発明の第１の実施の形態における動作のフローチャート（その２）である。
【図６】本発明の第１の実施の形態における動作のフローチャート（その３）である。
【図７】本発明の第１の実施の形態における動作のフローチャート（その４）である。
【図８】本発明の第１の実施の形態における動作のフローチャート（その５）である。
【図９】本発明の第２の実施の形態における経路計算装置の構成図である。
【図１０】本発明の第２の実施の形態における動作のフローチャート（その１）である。
【図１１】本発明の第２の実施の形態における動作のフローチャート（その２）である。
【図１２】本発明の第２の実施の形態における動作のフローチャート（その３）である。
【図１３】本発明の第２の実施の形態における動作のフローチャート（その４）である。
【図１４】本発明の第２の実施の形態における動作のフローチャート（その５）である。
【図１５】本発明の第１の実施例における一連の動作を説明するための図（その１）である。
【図１６】本発明の第１の実施例における一連の動作を説明するための図（その２）である。
【図１７】本発明の第２の実施例における一連の動作を説明するための図（その１）である。
【図１８】本発明の第２の実施例における一連の動作を説明するための図（その２）である。
【図１９】本発明の第２の実施例における一連の動作を説明するための図（その３）である。
【図２０】マルチキャスト経路計算装置を説明するための図である。
【図２１】従来技術を説明するための図（その１）である。
【図２２】従来技術を説明するための図（その２）である。
【図２３】従来技術を説明するための図（その３）である。
【符号の説明】
【０１６２】
１０１  トポロジ情報記憶手段、トポロジ情報記憶部
１０２  制約条件記憶手段、制約条件記憶部
１０３  初期設定手段、初期設定部
１０４  マルチキャスト判定制御部
１０５  マルチキャスト判定手段、マルチキャスト判定部
１０６  マルチキャスト装置用候補装置決定手段、マルチキャスト装置用候補装置決定部
１０７  ユニキャスト装置用候補装置決定手段、ユニキャスト装置用候補装置決定部
１０８  探索対象装置決定手段、探索対象装置決定部
１０９  経路完了判定手段、経路完了判定部
１１０  受信装置数カウント手段、受信装置数カウント部
１１１  訪問済装置記憶手段、訪問済装置記憶部
１１２  探索経路記憶手段、探索経路記憶部
１１３  候補装置記憶手段、候補装置記憶部
１１４  受信装置数記憶手段
１２０  ダイクストラ経路計算手段
２０１  ダイクストラ用トポロジ情報記憶部
２０２  ダイクストラ制御部
２０３  ダイクストラ用訪問済装置記憶部
２０４  ダイクストラ用探索経路記憶部
２０５  ダイクストラ用候補装置記憶部
【図１】
0004479601.tif 000002
【図２】
0004479601.tif 000003
【図３】
0004479601.tif 000004
【図４】
0004479601.tif 000005
【図５】
0004479601.tif 000006
【図６】
0004479601.tif 000007
【図７】
0004479601.tif 000008
【図８】
0004479601.tif 000009
【図９】
0004479601.tif 000010
【図１０】
0004479601.tif 000011
【図１１】
0004479601.tif 000012
【図１２】
0004479601.tif 000013
【図１３】
0004479601.tif 000014
【図１４】
0004479601.tif 000015
【図１５】
0004479601.tif 000016
【図１６】
0004479601.tif 000017
【図１７】
0004479601.tif 000018
【図１８】
0004479601.tif 000019
【図１９】
0004479601.tif 000020
【図２０】
0004479601.tif 000021
【図２１】
0004479601.tif 000022
【図２２】
0004479601.tif 000023
【図２３】
0004479601.tif 000024