(57)【要約】【課題】マルチキャストツリーが構成するリンク数を最小限に抑えたマルチキャスト経路計算を可能にする。【解決手段】本発明は、受信ノードの計算順序を決定し、計算順序が最上位の受信ノード・探索ノードを決定し、探索ノードからのホップ数及び合計コストを計算し、受信ノードから送信ノードへ、または、受信ノードから既にでき上がったツリーへ、ホップ数が最も少なくなるように経路を決定する。ホップ数が同数の場合には、探索ノードから合計コストが小さくなるように経路を決定する。【選択図】図１
2008005066.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャスト経路を計算するマルチキャスト経路計算方法であって、
要求取得手段が、各ノードの接続関係を表したトポロジ情報及び、送信ノードと複数の受信ノードを受け付け、該送信ノードを経路記憶手段に格納する要求取得ステップと、
計算順序決定手段が、受信ノードの計算順序を決定する計算順序決定ステップと、
計算受信ノード決定手段が、前記経路記憶手段に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する計算受信ノード決定ステップと、
探索ノード決定手段が、訪問済みノード記憶手段を参照して、訪問済みノードが１つも無い場合は、前記受信ノードを探索ノードとして決定し、訪問済みノードがある場合は、まだ訪問済みとなっていないノードの中から、ノード情報記憶手段を参照して、ホップ数が最小のノードを探索ノードとして決定し、ホップ数が最小のノードが複数ある場合は、その中から合計コストが最小のノードを次の探索ノードとして決定し、該探索ノードを該訪問済みノード記憶手段に格納する探索ノード決定ステップと、
経路パラメータ計算手段が、前記探索ノードの隣接ノードについて、該探索ノード経由の経路における第１のホップ数と第１の合計コストを計算する経路パラメータ計算ステップと、
経路パラメータ判定手段が、前記隣接ノードについて、前記ノード情報記憶手段を参照し、ホップ数が格納されていない場合、または、他のノード経由の経路における第２のホップ数が既に計算されているが、前記第１のホップ数の方が小さい場合は、該第１のホップ数、前記第１の合計コスト、前記探索ノード経由の経路を該ノード情報記憶手段に格納し、該第２のホップ数が該第１のホップ数と等しく、かつ、他のノード経由の経路における第２の合計コストが既に計算されているが、前記第１の合計コストの方が小さい場合は、該第１のホップ数、該第１の合計コスト、前記探索ノード経由の経路を該ノード情報記憶手段に格納する経路パラメータ判定ステップと、
制御手段が、前記経路記憶手段を参照して、前記探索ノードが含まれていなければ、前記探索ノード決定ステップ以降の処理を繰り返し、
経路保存手段が、前記ノード情報記憶手段を参照して、前記探索ノードから前記受信ノードまでの経路を前記経路記憶手段に格納する経路保存ステップと、
前記制御手段が、前記経路記憶手段を参照して、受信ノードが該経路記憶手段に全て格納されていなければ、前記訪問済みノード記憶手段と前記ノード情報記憶手段の情報を削除し、前記計算受信ノード決定ステップ以降の処理を繰り返し、
経路出力手段が、前記経路記憶手段に格納された経路を出力する経路出力ステップと、
を行うことを特徴とするマルチキャスト経路計算方法。
【請求項２】
前記計算順序決定ステップにおいて、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、
前記最小ホップ数が最も小さい受信ノードを計算順序最上位とし、該最小ホップ数が最も大きい受信ノードを計算順序最下位とする、
請求項１記載のマルチキャスト経路計算方法。
【請求項３】
前記計算順序決定ステップにおいて、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、
前記最小ホップ数が最も大きい受信ノードを計算順序最上位とし、該最小ホップ数が最も小さい受信ノードを計算順序最下位とする、
請求項１記載のマルチキャスト経路計算方法。
【請求項４】
前記経路パラメータ計算ステップにおいて、
前記探索ノードが受信ノードである場合は、ホップ数を１とする、
請求項１記載のマルチキャスト経路計算方法。
【請求項５】
マルチキャスト経路を計算するマルチキャスト経路計算装置であって、
各ノードの接続関係を表したトポロジ情報及び、送信ノードと複数の受信ノードを受け付け、該送信ノードを経路記憶手段に格納する要求取得手段と、
受信ノードの計算順序を決定する計算順序決定手段と、
前記経路記憶手段に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する計算受信ノード決定手段と、
訪問済みノード記憶手段を参照して、訪問済みノードが１つも無い場合は、前記受信ノードを探索ノードとして決定し、訪問済みノードがある場合は、まだ訪問済みとなっていないノードの中から、ノード情報記憶手段を参照して、ホップ数が最小のノードを探索ノードとして決定し、ホップ数が最小のノードが複数ある場合は、その中から合計コストが最小のノードを次の探索ノードとして決定し、該探索ノードを該訪問済みノード記憶手段に格納する探索ノード決定手段と、
前記探索ノードの隣接ノードについて、該探索ノード経由の経路における第１のホップ数と第１の合計コストを計算する経路パラメータ計算手段と、
前記隣接ノードについて、前記ノード情報記憶手段を参照し、ホップ数が格納されていない場合、または、他のノード経由の経路における第２のホップ数が既に計算されているが、前記第１のホップ数の方が小さい場合は、該第１のホップ数、前記第１の合計コスト、前記探索ノード経由の経路を該ノード情報記憶手段に格納し、該第２のホップ数が該第１のホップ数と等しく、かつ、他のノード経由の経路における第２の合計コストが既に計算されているが、前記第１の合計コストの方が小さい場合は、該第１のホップ数、該第１の合計コスト、前記探索ノード経由の経路を該ノード情報記憶手段に格納する経路パラメータ判定手段と、
前記経路記憶手段を参照して、前記探索ノードが含まれていなければ、前記探索ノード決定手段、経路パラメータ計算手段、経路パラメータ判定手段の処理を繰り返す第１の制御手段と、
前記ノード情報記憶手段を参照して、前記探索ノードから前記受信ノードまでの経路を前記経路記憶手段に格納する経路保存手段と、
前記経路記憶手段を参照して、受信ノードが該経路記憶手段に全て格納されていなければ、前記訪問済みノード記憶手段と前記ノード情報記憶手段の情報を削除し、前記計算受信ノード決定手段、前記探索ノード決定手段、前記経路パラメータ計算手段、前記経路パラメータ判定手段、前記第１の制御手段、前記経路保存手段の処理を繰り返す第２の制御手段と、
前記経路記憶手段に格納された経路を出力する経路出力手段と、
を有することを特徴とするマルチキャスト経路計算装置。
【請求項６】
前記計算順序決定手段は、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、該最小ホップ数が最も小さい受信ノードを計算順序最上位とし、該最小ホップ数が最も大きい受信ノードを計算順序最下位とする、
請求項５記載のマルチキャスト経路計算装置。
【請求項７】
前記計算順序決定手段は、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、該最小ホップ数が最も大きい受信ノードを計算順序最上位とし、該最小ホップ数が最も小さい受信ノードを計算順序最下位とする、
請求項５記載のマルチキャスト経路計算装置。
【請求項８】
前記経路パラメータ計算手段は、
前記探索ノードが受信ノードである場合は、ホップ数を１とする、
請求項５記載のマルチキャスト経路計算装置。
【請求項９】
コンピュータに、
請求項５乃至８記載のマルチキャスト経路計算装置の各手段を実行させることを特徴とするマルチキャスト経路計算プログラム。
【請求項１０】
コンピュータに、
請求項５乃至８記載のマルチキャスト経路計算装置の各手段を実行させるプログラムを格納したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト経路計算方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に係り、特に、RSVP-TE(Resource Reservation Signaling Protocol for Traffic Engineering)をベースとしたマルチキャストMPLS(Multi Protocol Label Switching)において、LSP(Label Switched Path)に対するFRR(Fast Reroute)の迂回パス設定数の減少やリソースの有効利用を目的とし、マルチキャスト経路を構成するリンク数を最小に抑えるためのマルチキャスト経路計算方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
RSVP-TEをベースとしたマルチキャストMPLSでは、経路を明示的に指定することができ、また、その経路に予約帯域を設定することが可能である。さらに、マルチキャストツリーを構成するリンク１本１本に、予めFRRの迂回経路を設定することで、経路上で障害が発生したときも高速に障害箇所を迂回することができる。一方、受信ユーザ数が増えることなどにより、マルチキャストツリーを構成するリンク数が多くなると、ネットワークリソースを大量に予約する必要があり、また、ＦＲＲの迂回経路設定の数も増大することになる。ＦＲＲの迂回経路は、ネットワークが正常に運用されている間は利用されないため、できるだけ最小限に抑えることが期待される。このように、RSVP-TEを用いたマルチキャストMPLSでは、経路を最適に計算する必要がある。
【０００３】
図１０に示すように、RSVP-TEが動作しているMPLSネットワークにおいて、トポロジ情報収集機構によって集められたトポロジ情報１１と、送信伝送装置、受信伝送装置などのLSP要求１２を受け付けて、LSP経路を計算し、その計算結果を経路設定機構１３に出力するLSP経路計算装置１０が用いられている。
【０００４】
このようなLSP経路計算装置において、従来技術であるダイクストラ経路計算方法が用いられている。このダイクストラ経路計算方法は、少ない計算時間で、送信ノードから受信ノードまでのリンクに付与されたリンクコストの合計が最小になるような経路を計算することができる（例えば、非特許文献１参照）。
【非特許文献１】WIDE 2002年インターネットアーキテクチャ第６回講義資料、インターネット  <http://www.soi.wide.ad.jp/class/20020022/materials_for_student/06/na‐06.pdf> 10ページ、11ページ［online］，掲載日不明［2006年４月１０日検索］
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のダイクストラ経路計算方法は、合計コストを小さく抑えることはできるが、マルチキャストツリーを構成するリンク数を少なくすることはできない。RSVP-TEを用いたマルチキャストMPLSの経路計算では、リソースの有効利用やFRRの迂回経路設定数増加防止を目的として、ツリーを構成するリンク数をできるだけ少なくする必要がある。
【０００６】
本発明は、上記の点に鑑みなされたもので、マルチキャストツリーを構成するリンク数を最小限に抑えたマルチキャスト経路計算が可能なマルチキャスト経路計算方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００７】
図１は、本発明の原理を説明するための図である。
【０００８】
本発明（請求項１）は、マルチキャスト経路を計算するマルチキャスト経路計算方法であって、
要求取得手段が、各ノードの接続関係を表したトポロジ情報及び、送信ノードと複数の受信ノードを受け付け、該送信ノードを経路記憶手段に格納する要求取得ステップ（ステップ１）と、
計算順序決定手段が、受信ノードの計算順序を決定する計算順序決定ステップ（ステップ２）と、
計算受信ノード決定手段が、経路記憶手段に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する計算受信ノード決定ステップ（ステップ３）と、
探索ノード決定手段が、訪問済みノード記憶手段を参照して、訪問済みノードが１つも無い場合は、受信ノードを探索ノードとして決定し、訪問済みノードがある場合は、まだ訪問済みとなっていないノードの中から、ノード情報記憶手段を参照して、ホップ数が最小のノードを探索ノードとして決定し、ホップ数が最小のノードが複数ある場合は、その中から合計コストが最小のノードを次の探索ノードとして決定し、該探索ノードを該訪問済みノード記憶手段に格納する探索ノード決定ステップ（ステップ４）と、
経路パラメータ計算手段が、探索ノードの隣接ノードについて、探索ノード経由の経路における第１のホップ数と第１の合計コストを計算する経路パラメータ計算ステップ（ステップ５）と、
経路パラメータ判定手段が、隣接ノードについて、ノード情報記憶手段を参照し、ホップ数が格納されていない場合、または、他のノード経由の経路における第２のホップ数が既に計算されているが、第１のホップ数の方が小さい場合は（ステップ６（ａ））、該第１のホップ数、第１の合計コスト、探索ノード経由の経路を該ノード情報記憶手段に格納し（ステップ８）、該第２のホップ数が該第１のホップ数と等しく、かつ、他のノード経由の経路における第２の合計コストが既に計算されているが、第１の合計コストの方が小さい場合は（ステップ６（ｂ），ステップ７（ｃ））、該第１のホップ数、該第１の合計コスト、探索ノード経由の経路を該ノード情報記憶手段に格納する（ステップ８）経路パラメータ判定ステップと、
制御手段が、経路記憶手段を参照して、探索ノードが含まれていなければ、探索ノード決定ステップ以降の処理を繰り返し（ステップ９）、
経路保存手段が、ノード情報記憶手段を参照して、探索ノードから受信ノードまでの経路を経路記憶手段に格納する経路保存ステップ（ステップ１０）と、
制御手段が、経路記憶手段を参照して、受信ノードが該経路記憶手段に全て格納されていなければ、訪問済みノード記憶手段とノード情報記憶手段の情報を削除し、計算受信ノード決定ステップ以降の処理を繰り返し（ステップ１１）、
経路出力手段が、経路記憶手段に格納された経路を出力する経路出力ステップ（ステップ１２）と、を行う。
【０００９】
また、本発明（請求項２）は、計算順序決定ステップ（ステップ２）において、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、
最小ホップ数が最も小さい受信ノードを計算順序最上位とし、該最小ホップ数が最も大きい受信ノードを計算順序最下位とする。
【００１０】
また、本発明（請求項３）は、計算順序決定ステップ（ステップ２）において、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、
最小ホップ数が最も大きい受信ノードを計算順序最上位とし、該最小ホップ数が最も小さい受信ノードを計算順序最下位とする。
【００１１】
また、本発明（請求項４）は、経路パラメータ計算ステップ（ステップ５）において、
探索ノードが受信ノードである場合は、ホップ数を１とする。
【００１２】
図２は、本発明の原理構成図である。
【００１３】
本発明（請求項５）は、マルチキャスト経路を計算するマルチキャスト経路計算装置であって、
各ノードの接続関係を表したトポロジ情報及び、送信ノードと複数の受信ノードを受け付け、該送信ノードを経路記憶手段１０３に格納する要求取得手段１１０と、
受信ノードの計算順序を決定する計算順序決定手段１２０と、
経路記憶手段１０３に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する計算受信ノード決定手段１４０と、
訪問済みノード記憶手段１０４を参照して、訪問済みノードが１つも無い場合は、受信ノードを探索ノードとして決定し、訪問済みノードがある場合は、まだ訪問済みとなっていないノードの中から、ノード情報記憶手段１０５を参照して、ホップ数が最小のノードを探索ノードとして決定し、ホップ数が最小のノードが複数ある場合は、その中から合計コストが最小のノードを次の探索ノードとして決定し、該探索ノードを該訪問済みノード記憶手段に格納する探索ノード決定手段１５０と、
探索ノードの隣接ノードについて、探索ノード経由の経路における第１のホップ数と第１の合計コストを計算する経路パラメータ計算手段１６０と、
隣接ノードについて、ノード情報記憶手段１０５を参照し、ホップ数が格納されていない場合、または、他のノード経由の経路における第２のホップ数が既に計算されているが、第１のホップ数の方が小さい場合は、該第１のホップ数、第１の合計コスト、探索ノード経由の経路を該ノード情報記憶手段１０５に格納し、該第２のホップ数が該第１のホップ数と等しく、かつ、他のノード経由の経路における第２の合計コストが既に計算されているが、第１の合計コストの方が小さい場合は、該第１のホップ数、該第１の合計コスト、探索ノード経由の経路を該ノード情報記憶手段１０５に格納する経路パラメータ判定手段１７０と、
経路記憶手段１０３を参照して、探索ノードが含まれていなければ、探索ノード決定手段１５０、経路パラメータ計算手段１６０、経路パラメータ判定手段１７０の処理を繰り返す第１の制御手段１００−１と、
ノード情報記憶手段１０５を参照して、探索ノードから受信ノードまでの経路を経路記憶手段１０３に格納する経路保存手段１８０と、
経路記憶手段１０３を参照して、受信ノードが該経路記憶手段１０３に全て格納されていなければ、訪問済みノード記憶手段１０４とノード情報記憶手段１０５の情報を削除し、計算受信ノード決定手段１４０、探索ノード決定手段１５０、経路パラメータ計算手段１６０、経路パラメータ判定手段１７０、第１の制御手段１００−１、経路保存手段１８０の処理を繰り返す第２の制御手段１００−２と、
経路記憶手段に格納された経路を出力する経路出力手段１９０と、を有する。
【００１４】
また、本発明（請求項６）は、計算順序決定手段１２０において、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、該最小ホップ数が最も小さい受信ノードを計算順序最上位とし、該最小ホップ数が最も大きい受信ノードを計算順序最下位とする。
【００１５】
また、本発明（請求項７）は、計算順序決定手段１２０において、
それぞれの受信ノードについて、送信ノードから受信ノードまでの最小ホップ数を計算し、該最小ホップ数が最も大きい受信ノードを計算順序最上位とし、該最小ホップ数が最も小さい受信ノードを計算順序最下位とする。
【００１６】
また、本発明（請求項８）は、経路パラメータ計算手段１７０において、
探索ノードが受信ノードである場合は、ホップ数を１とする。
【００１７】
また、本発明（請求項９）は、コンピュータに、請求項５乃至８記載のマルチキャスト経路計算装置の各手段を実行させるマルチキャスト経路計算プログラムである。
【００１８】
また、本発明（請求項１０）は、コンピュータに、請求項５乃至８記載のマルチキャスト経路計算装置の各手段を実行させるプログラムを格納したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１９】
上記のように本発明によれば、受信ノードから送信ノードへ、または、受信ノードから既に出来上がったツリーへ、ホップ数が最も少なくなるように経路を決定する。また、ホップ数が同数の場合は、合計コストが小さくなるように経路を決定する。
【００２０】
これにより、ツリーを構成するリンク数をできるだけ少なく抑えてマルチキャスト経路を決定することができる。本発明は、RSVP-TEをベースとしたマルチキャストMPLSにおいて、FRRの迂回経路の設定数減少や、ネットワークリソースの有効利用において、効果を発揮する。
【発明を実施するための最良の形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
［第１の実施の形態］
図３は、本発明の第１の実施の形態におけるマルチキャスト経路計算装置の構成を示す。
【００２３】
同図に示すマルチキャスト経路計算装置は、要求取得部１１０、計算順序決定部１２０、初期化部１３０、計算受信ノード決定部１４０、探索ノード決定部１５０、経路パラメータ計算部１６０、経路パラメータ判定部１７０、経路保存部１８０、経路出力部１９０、制御部１００、トポロジ情報記憶部１０１、送信・受信ノード記憶部１０２、経路記憶部１０３、訪問済みノード記憶部１０４、ノード情報記憶部１０５から構成される。
【００２４】
要求取得部１１０は、外部からトポロジ情報、送信ノード、受信ノードを入力装置からの入力、または、記憶装置から読み出すことにより取得し、トポロジ情報をトポロジ情報記憶部１０１に、送信ノード・受信ノードを送信・受信ノード記憶部１０２に、送信ノードを経路記憶部１０３に格納する。
【００２５】
計算順序決定部１２０は、送信・受信ノード記憶部１０２を参照し、受信ノードの計算順序を決定し、送信・受信ノード記憶部１０２に当該計算順序を格納する。
【００２６】
初期化部１３０は、訪問済みノード記憶部１０４、ノード情報記憶部１０５を初期化する。
【００２７】
計算受信ノード決定部１４０は、送信・受信ノード記憶部１０２及び経路記憶部１０３を参照し、経路記憶部１０３に格納されていない受信ノードの中で計算順序最上位の受信ノードを決定する。
【００２８】
探索ノード決定部１５０は、訪問済みノード記憶部１０４を参照し、探索ノードを決定し、当該探索ノードを訪問済みノード記憶部１０４に格納する。
【００２９】
経路パラメータ計算部１６０は、トポロジ情報記憶部１０１を参照し、探索ノードの隣接ノードについて、探索ノード経由の経路における第１のホップ数と第１の合計コストを計算する。
【００３０】
経路パラメータ判定部１７０は、ノード情報記憶部１０５を参照し、隣接ノードについて、既に格納されている第２のホップ数と合計コストと、第１のホップ数と合計コストを比較し、ノード上表記憶部１０５の情報を更新する。
【００３１】
経路出力部１９０は、経路記憶部１０３に格納された経路を出力する。
【００３２】
制御部１００は、上記の各部の処理を制御する。
【００３３】
次に、上記の構成における動作を説明する。
【００３４】
図４、図５は、本発明の第１の実施の形態における動作のフローチャートである。
【００３５】
ステップ１０１）  まず、要求取得部１１０が、ネットワークの各ノードの接続関係を表したトポロジ情報と、送信ノード及び受信ノードを取得する。トポロジ情報には、各ノードの接続関係のほか、各リンクのコスト値を含む。また、受信ノードは、複数のノードとなる。また、取得したトポロジ情報をトポロジ情報記憶部１０１に、送信ノードと受信ノードを、送信・受信ノード記憶部１０２に保存する。
【００３６】
ステップ１０２）  次に、要求取得部１１０が、送信ノードを経路記憶部１０３に保存する。
【００３７】
ステップ１０３）  次に、計算順序決定部１２０が、送信ノードから各受信ノードまでの最小ホップ数を計算する。
【００３８】
ステップ１０４）  次に、計算順序決定部１２０が、上記の送信ノードから各受信ノードまでの最小ホップ数を比較し、最小ホップ数が最も小さい受信ノードを計算順序最上位、最も大きい受信ノードを最下位とし、計算順序を送信・受信ノード記憶部１０２の各受信ノードに対して保存する。
【００３９】
ステップ１０５）  次に、初期化部１３０が、訪問済みノード記憶部１０４とノード情報記憶部１０５の情報を削除する。但し、最初はデータが格納されていないため、この必要はない。
【００４０】
ステップ１０６）  次に、計算受信ノード決定部１４０が、経路記憶部１０３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する。但し、最初は、経路記憶部１０３には、送信ノードしか保存されていないため、計算順序最上位の受信ノードが決定される。
【００４１】
ステップ１０７）  次に、探索ノード決定部１５０が、訪問済みノード記憶部１０４になんらかのノードが保存されているかを判定する。何も保存されていない場合は、ステップ１０８に移行する。訪問済みノード記憶部１０４に何らかのノードが保存されている場合、ステップ１０９に移行する。
【００４２】
ステップ１０８）  前ステップで決定された受信ノードを探索ノードとして決定し、当該ノードを訪問済みノード記憶部１０４に保存し、ステップ１１２に移行する。
【００４３】
ステップ１０９）  まだ訪問済みとなっていないノードの中について、ノード情報記憶部１０５に保存されているノードに対するホップ数と合計コストと経路を参照し、ホップ数が最小のノードが複数あるかどうかを判定する。ホップ数が最小のノードが１つの場合は、ステップ１１０に移行する。ホップ数が最小のノードが複数ある場合は、ステップ１１１に移行する。
【００４４】
ステップ１１０）  当該ノードを探索ノードとして決定し、訪問済みノード記憶部１０４に保存し、ステップ１１２に移行する。
【００４５】
ステップ１１１）  ホップ数が最小のノードの中で、合計コストが最小のノードを一つ選び、該ノードを探索ノードとして決定し、訪問済みノード記憶部１０４に保存する。
【００４６】
ステップ１１２）  次に、経路パラメータ計算部１６０が、探索ノードｖの隣接ノードｕについて、探索ノード経由のホップ数Ｈ１と、合計コストＣ１を計算する。ここで、
Ｈ１＝Ｉｄ＊Ｈ（ｖ）＋１
で、Ｉｄは、探索ノードが受信ノードの１つであれば０、そうでなければ１をとる値、Ｈ（ｖ）は、探索ノードのホップ数である。また、
Ｃ１＝Ｃ（ｖ）＋ｗ（ｖ，ｕ）
で、Ｃ（ｖ）は、探索ノードの合計コスト、ｗ（ｖ，ｕ）は、探索ノードと隣接ノード間のリンクのコスト値である。Ｈ（ｖ）やＣ（ｖ）は、ノード情報記憶部１０５に保存されている値を用いる。ノード情報記憶部１０５の探索ノードｖの情報が何も保存されていない場合、Ｈ（ｖ）、とＣ（ｖ）は０である。
【００４７】
ステップ１１３）  次に、経路パラメータ判定部１７０が、ノード情報記憶部１０５を参照し、上記の隣接ノードｕに対して、他のノード経由のホップ数Ｈと合計コストＣが既に保存されているかどうかを判定する。保存されていない場合は、ステップ１１６に移行する。既に、ＨとＣが保存されている場合は、ステップ１１４に移行する。
【００４８】
ステップ１１４）  まず、Ｈ１＜Ｈかどうかを判定し、そうであれば、ステップ１１６に移行する。そうでなければステップ１１５に移行する。
【００４９】
ステップ１１５）  Ｈ１＜Ｈでない場合で、Ｈ１＝ＨかつＣ１＜Ｃである場合も、ステップ１１６に移行する。そうでない場合は、ステップ１１７に移行する。
【００５０】
ステップ１１６）  保存されていない場合は、ノード情報記憶部１０５の隣接ノードｕに、Ｈ１とＣ１及び経路として、探索ノードを保存する。Ｈ１＜Ｈの場合は、ノード情報記憶部１０５の隣接ノードｕに、Ｈ１とＣ１と経路（探索ノード）を上書きする。Ｈ１＜Ｈでない場合で、Ｈ１＝ＨかつＣ１＜Ｃである場合にも、ノード情報記憶部１０５の隣接ノードｕに、Ｈ１とＣ１と経路（探索ノード）を上書きする。
【００５１】
ステップ１１７）  探索ノードに対する隣接ノード全てに対し、Ｈ１とＣ１の計算が行われるまで、経路パラメータ計算部１６０以下の処理（ステップ１１２以降の処理）を繰り返し行う。
【００５２】
ステップ１１８）  制御部１００は、探索ノードが経路記憶部１０３に保存されていなければ、探索ノード決定部１５０以下の各部に対してステップ１０７以降の処理を繰り返し実行させる。探索ノードが経路記憶部１０３に保存されているノードであれば、ステップ１１９に移行する。
【００５３】
ステップ１１９）  ノード情報記憶部１０５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として保存する。この経路は、ノード情報記憶部１０５の各ノードに保存されている経路（ノード）を辿ることで得られる。
【００５４】
ステップ１２０）  制御部１００は、全ての受信ノードが、経路記憶部１０３に保存されるまで、初期化部１３０以下の各部に対してステップ１０５以降の処理を繰り返し実行させる。
【００５５】
ステップ１２１）  全ての受信ノードが経路記憶部１０３に保存されたら、最後に、経路出力部１９０が、経路記憶部１０３に保存されている経路を出力して処理を終了する。
【００５６】
以下に、上記の動作の具体例を説明する。
【００５７】
以下の説明で利用するトポロジを図６に示す。
【００５８】
まず、要求取得部１１０がトポロジ情報を取得する。各ノードの接続関係、各リンクのコスト値は、図６に示すとおりである。次に、要求取得部１１０は、送信ノードと受信ノードを取得する。本具体例では、送信ノードをノード１、受信ノードＡをノード６、受信ノードＢをノード１３、受信ノードＣをノード１２、受信ノードＤをノード１５とする。要求取得部１１０は、トポロジ情報をトポロジ情報記憶部１０１、送信ノードと受信ノードを送信・受信ノード記憶部１０２に保存する（ステップ１０１）。さらに、要求取得部１１０は、送信ノードを経路記憶部１０３に保存する（ステップ１０２）。
【００５９】
次に、計算順序決定部１２０が、送信ノードから各受信ノードまでの最小ホップ数を計算する（ステップ１０３）。本具体例において、各受信ノードの最小ホップ数は、受信ノードＡが２、受信ノードＢが３、受信ノードＣが５、受信ノードＤが５となる。計算順序決定部１２０は、これらの値を比較し、最小ホップ数が小さい順に以下の通り、計算順序を決定する。
【００６０】
・１位：ノードＡ
・２位：ノードＢ
・３位：ノードＣ
・４位：ノードＤ
ここで、ノードＣとノードＤは、最小ホップ数が等しいため、記号順に順位を決定したが、他の方法でもよい。これらの情報を送信・受信ノード記憶部１０２の受信ノードそれぞれに関連付けて保存する（ステップ１０４）。
【００６１】
次に、初期化部１３０が、訪問済みノード記憶部１０４とノード情報記憶部１０５の情報を削除する（ステップ１０５）。但し、最初はデータが格納されていないため、この必要はない。
【００６２】
次に、計算受信ノード決定部１４０が、経路記憶部１０３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ１０６）。但し、最初は、経路記憶部１０３には、送信ノードしか保存されていないため、計算順序最上位の受信ノードが決定される。本動作例では、受信ノードＡが選択される。
【００６３】
次に、探索ノード決定部１５０が、訪問済みノード記憶部１０４に何らかのノードが保存されているかを判定する（ステップ１０７）。最初は何も保存されていないため、前の処理で決定された受信ノードＡを探索ノードとして決定し、当該ノードを訪問済みノード記憶部１０４に保存する（図７（ａ）参照）（ステップ１０８）。
【００６４】
次に、経路パラメータ計算部１６０が、探索ノードｖの隣接ノードｕについて、探索ノード経由のホップ数Ｈ１と、合計コストＣ１を計算する（ステップ１１２）。
【００６５】
さらに、経路パラメータ判定部１７０が、ノード情報記憶部１０５を参照し、上記の隣接ノードｕに対して、他のノード経由のホップ数Ｈと合計コストＣが既に保存されているかどうかを判定する（ステップ１１３）。最初は、保存されていないため、ノード情報記憶部１０５の隣接ノードｕ、Ｈ１とＣ１及び、経路として、探索ノードを保存する（ステップ１１６）。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７（ｂ）参照）。図７（ｂ）において、ホップ数はＨ、合計コストはＣ、経路はＲで示す。
【００６６】
探索ノードが経路記憶部１０３に保存されていないので（ステップ１１８、Ｎｏ）、探索ノード決定の処理（ステップ１０７）に戻る。
【００６７】
探索ノード決定部１５０が、訪問済みノード記憶部１０４を参照し、ノードが保存されているため（ステップ１０７、Ｙｅｓ）、訪問済みとなっていないノードについて、ノード情報記憶部１０５に保存されているノードに対するホップ数と合計コストと経路を参照し、ホップ数が最小のノードが複数あるかどうかを判定する（ステップ１０９）。本具体例では、ホップ数が最小の１を持つノードが６つあるため、ホップ数が最小のノードの中で、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが１のノードが選択されるが、複数あるため、ノード番号順にノード２が探索ノードとして選択され、訪問済みノード記憶部１０４に保存される（図７（ｃ）参照）（ステップ１１１）。
【００６８】
次に、経路パラメータ計算部１６０が、探索ノードｖの隣接ノードｕについて、探索ノード経由のホップ数Ｈ１と、合計コストＣ１を計算する（ステップ１１２）。
【００６９】
さらに、経路パラメータ判定部１７０が、ノード情報記憶部１０５を参照し、上記の隣接ノードｕに対して、他のノード経由のホップ数Ｈと合計コストＣが既に保存されているかどうかを判定する（ステップ１１３）。保存されていないノードには、ノード情報記憶部１０５の隣接ノードｕに、Ｈ１とＣ１及び、経路として、探索ノードを保存する（ステップ１１６）。既に、ＨとＣが保存されているノードにおいては（ステップ１１３、Ｙｅｓ）、Ｈ１＜Ｈ、または、Ｈ１＝ＨかつＣ１＜Ｃの場合（ステップ１１４，Ｙｅｓ、ステップ１１５，Ｙｅｓ）、Ｈ１とＣ１を新たなＨ、Ｃとして、また、探索ノードを経路として保存する（ステップ１１６）。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７（ｄ））。
【００７０】
上記の、探索ノード決定、経路パラメータ計算、経路パラメータ判定の処理を繰り返し行うと、探索ノードがノード５、ノード７、ノード１０、ノード３、ノード９、ノード１の順に決定される（図７（ｅ）〜（ｈ）参照）。
【００７１】
ノード１は、経路記憶部１０３に保存されているため、上記繰り返し処理は終了され、経路記憶部１０３に探索ノードから受信ノードＡまでの経路が保存される（図８（ｉ）参照）。
【００７２】
経路記憶部１０３に、全ての受信ノードが保存されていないため（ステップ１２０、Ｎｏ）、初期化部１３０の処理に戻る。初期化部１３０は、訪問済みノード記憶部１０４と、ノード情報記憶部１０５の情報を削除する（図８（ｊ）参照）（ステップ１０５）。
【００７３】
次に、計算受信ノード決定部１４０が、送信・受信ノード記憶部１０２を参照し、次の計算受信ノードを受信ノードＢと選択する（ステップ１０６）。
【００７４】
探索ノード決定、経路パラメータ計算、経路パラメータ判定の処理を上記同様に繰り返すと、探索ノードがノード１３、ノード９、ノード１１、ノード１０、ノード５の順に決定される。
【００７５】
ノード５は、経路記憶部１０３に保存されているため、上記繰り返し処理は終了され、経路記憶部１０３に探索ノードから受信ノードＢまでの経路が保存される（図８（ｋ））（ステップ１１９）。
【００７６】
経路記憶部１０３に、全ての受信ノードが保存されていないため（ステップ１２０、Ｎｏ）、初期化部１３０の処理に戻る。初期化部１３０は、訪問済みノード記憶部１０４と、ノード情報記憶部１０５の情報を削除する（ステップ１０５）。
【００７７】
次に、計算受信ノード決定部１４０が、送信・受信ノード記憶部１０２を参照し、次の計算受信ノードを受信ノードＣと選択する（ステップ１０６）。
【００７８】
探索ノード決定、経路パラメータ計算、経路パラメータ判定の処理を、上記同様に繰り返すと、探索ノードがノード１２、ノード８、ノード１１、ノード１６、ノード１５、ノード１４、ノード４、ノード７、ノード１０、ノード１３の順に決定される。ここで、ノード１５が、探索ノードとして決定されたとき、経路パラメータ計算部１６０において、Ｈ１の計算では、Ｉｄが０にセットされることに注意が必要である。
【００７９】
ノード１３は、経路記憶部１０３に保存されているため、上記繰り返し処理は終了され、経路記憶部１０３に探索ノードから受信ノードＣまでの経路が保存される（図８（ｌ）参照）（ステップ１１９）。
【００８０】
経路記憶部１０３に全ての受信ノードが保存されたため（ステップ１２０、Ｙｅｓ）、最後に経路出力部１９０が経路記憶部１０３を参照し、マルチキャスト経路を、例えば、以下のように出力し処理を終了する（ステップ１２１）。
【００８１】
・受信ノードＡへの経路：１，５，６
・受信ノードＢへの経路：１，５，９，１３
・受信ノードＣへの経路：１，５，９，１３，１４，１５，１２
・受信ノードＤへの経路：１，５，９，１３，１４，１５
上記の第１の実施の形態によれば、送信ノードから受信ノードまでの最小ホップ数が小さい順に経路を計算していくため、無駄に遠回りする経路が生成されることを防ぐことが可能である。また、出来上がったツリーに最小のホップ数で経路を接続させていくこと、経路探索の途中で他の受信ノードを通過する経路を優先的に選択することにより、リンク数を最小限に抑えることが可能である。
【００８２】
［第２の実施の形態］
本実施の形態は、第１の実施の形態における計算順序決定部の処理のみが異なる。装置構成自体は第１の実施の形態における図３に示す構成と同様であるので、その説明は省略する。
【００８３】
本実施の形態における計算順序決定部１２０は、送信ノードから各受信ノードまでの最小ホップ数を計算し、得られた最小ホップ数を比較し、最小ホップ数が最も大きい受信ノードを計算順序最上位、最も小さい受信ノードを最下位とし、計算順序を送信・受信ノード記憶部１０２の各受信ノードに対し保存する。
【００８４】
第１の実施の形態における具体例において、各受信ノードの最小ホップ数は、受信ノードＡが２、受信ノードＢが３、受信ノードＣが５、受信ノードＤが５であるため、計算順序決定部１２０は、これらの値を比較し、最小ホップ数が大きい順に以下の通り、計算順序を決定する。
【００８５】
・１位：ノードＣ
・２位：ノードＤ
・３位：ノードＢ
・４位：ノードＡ
ここで、ノードＣとノードＤは、最小ホップ数が等しいため、記号順に順位を決定したが、他の方法でもよい。これらの情報を送信・受信ノード記憶部１０２にそれぞれ関連付けて保存する。
【００８６】
計算順序決定部１２０の処理以外は、全て第１の実施の形態と同じであるので、その説明を省略する。
【００８７】
上記の第２の実施の形態によれば、送信ノードから受信ノードまでの最小ホップ数が大きい順に経路を計算していくため、計算の途中で他の受信ノードを経路に取り込みやすくなるため、リンク数を最小限に抑えることが可能である。
【００８８】
なお、上記の第１・第２の実施の形態における動作をプログラムとして構築し、マルチキャスト経路計算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８９】
また、構築されたプログラムを、コンピュータ読み取り可能なディスク装置や、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールして実行させる、または、配布することが可能である。
【００９０】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００９１】
本発明は、マルチキャスト通信に用いる経路計算技術に適用可能である。
【図面の簡単な説明】
【００９２】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１の実施の形態におけるマルチキャスト経路計算装置の構成図である。
【図４】本発明の第１の実施の形態における動作のフローチャート（その１）である。
【図５】本発明の第１の実施の形態における動作のフローチャート（その２）である。
【図６】本発明の第１の実施の形態における動作例で利用するトポロジを示す図である。
【図７】本発明の第１の実施の形態における動作例を説明する図（その１）である。
【図８】本発明の第１の実施の形態における動作例を説明する図（その２）である。
【図９】本発明の第１の実施の形態における動作例を説明する図（その３）である。
【図１０】ＬＳＰ経路計算装置を説明するための図である。
【符号の説明】
【００９３】
１０  マルチキャスト経路計算装置（ＬＳＰ経路計算装置）
１１  トポロジ情報
１２  ＬＳＰ設定条件
１３  経路設定機構
１００  制御部
１００−１  第１の制御手段
１００−２  第２の制御手段
１０１  トポロジ情報記憶部
１０２  送信・受信ノード記憶部
１０３  経路記憶手段、経路記憶部
１０４  訪問済みノード記憶手段、訪問済みノード記憶部
１０５  ノード情報記憶手段、ノード情報記憶部
１１０  要求取得手段、要求取得部
１２０  計算順序決定手段、計算順序決定部
１３０  初期化部
１４０  計算受信ノード決定手段、計算受信ノード決定部
１５０  探索ノード決定手段、探索ノード決定部
１６０  経路パラメータ計算手段、経路パラメータ計算部
１７０  経路パラメータ判定手段、経路パラメータ判定部
１８０  経路保存手段、経路保存部
１９０  経路出力手段、経路出力部
【図１】
2008005066.tif 000003
【図２】
2008005066.tif 000004
【図３】
2008005066.tif 000005
【図４】
2008005066.tif 000006
【図５】
2008005066.tif 000007
【図６】
2008005066.tif 000008
【図７】
2008005066.tif 000009
【図８】
2008005066.tif 000010
【図９】
2008005066.tif 000011
【図１０】
2008005066.tif 000012