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