JP3977791B2 - マルチキャスト転送経路設定方法および装置 - Google Patents

Description

本発明は、コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト転送に利用する。特に、マルチキャスト主転送経路（以下、主転送経路という）の障害対策に関する。

コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト転送が注目を集めている。この転送方式は、経路の始点と選択された１つ以上の終点を結ぶ経路のうち、経路が分かれる部分において情報をコピーし、各終点へと情報を配送する。特定多数の終点へ始点と一対一で転送を行なうユニキャスト転送を用いて情報を配送した場合、終点の数だけ始点は情報を用意する必要がある。よって、マルチキャスト転送を用いることにより、ネットワーク内の情報量は減少する。

マルチキャスト転送では特定多数の終点をマルチキャストグループと呼ばれる管理単位で管理を行い、マルチキャストグループに対して１つの転送経路が設定される。この転送経路は始点からマルチキャストグループに属する全ての終点を接続するように設定される。経路上のリンクが故障した場合、ユニキャスト転送の場合には、１対１の転送なので情報が届かなくなるといった影響を受ける終点は少ないが、マルチキャスト転送の場合には１対複数の転送であるため１つのリンク故障によって影響を受ける終点の数が多くなることがある。

図１２にその例を示す。本例では、ユニキャスト転送の場合には情報が届かなくなるのは１受信者のみとなるが、マルチキャスト転送の場合には６終点となる。そのためマルチキャスト転送においてマルチキャスト予備転送経路（以下、予備転送経路という）を持つことはユニキャスト転送に比べて重要である。

現在、リンクに対する予備転送経路ではなく主転送経路に対して予備転送経路を求めるアルゴリズムとして、例えば、非特許文献１〜３のような方式が公開されている。これらの方式は、主転送経路と予備転送経路とを同時に求めるアルゴリズムであり、特に、非特許文献１で紹介されている方式は、主転送経路と予備転送経路とが利用する帯域を少なくすることを目的にしている。
M.Kodialem and T.Lakshman.Dynamicrouting of bandwidth guaranteed multicasts with failure backup.In Proceedingsof IEEE INFOCOM,June 2002. Alon Itai and Michael Rodeh.Themulti-tree approach to reliability in distributed networks.In IEEE Symposium onFoundations of Computer Science,pages 137-147,1984. M.M_edard,S.Finn,R.Barry,andR.Gallager.Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs.IEEE/ACM Transaction onNetworking,7(5):641-652,1999. V.Kompella他,"Multicast routing formultimedia communication,"IEEE/ACM Transactions on Networking,Volume:1Issue:3,pp.286-292,June 1993. Q.Zhu,他,"A source-based algorithm fordelay-constrained minimum-cost multicasting,"Proc in IEEE INFOCOM‘95,vol.1,pp.377-385,1995. E.W.Djikstra,"A note on two problemsin connection with graphs,"Numerische Mathematik,vol.1,pp.269-271,1959.

ここで、上記の非特許文献１〜３で紹介されている技術では、故障発生が始点ノードに伝わらない限り、切り替えができないため、切り替えに時間がかかるという問題があった。切り替えに時間がかかると受信者に情報が届かなくなる時間が長くなることになる。

本発明は、このような背景に行なわれたものであって、始点でははなく主マルチキャスト転送経路上の各リンクに予備転送経路を準備することにより、途中ノードでの現用予備切り替えを可能とし、切り替え時間を短縮することを目的とする。

本発明の第一の観点はマルチキャスト転送経路設定方法であって、本発明の特徴とするところは、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路をマルチキャスト転送経路計算装置により計算するステップと、この計算された主転送経路をマルチキャスト転送経路設定装置が設定するステップと、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を前記マルチキャスト転送経路計算装置により計算するステップと、この計算された全予備転送経路をマルチキャスト転送経路設定装置により設定するステップとを実行するところにある（請求項１）。

このように、主転送経路の全リンクに対して予備転送経路を計算することにより、主転送経路の途中で障害が発生したとき、障害発生が始点ノードまで伝わらなくても、途中のノードで予備転送経路に切り替えることができる。

また、前記マルチキャスト転送経路設定装置が前記マルチキャスト転送経路計算装置に主転送経路および予備転送経路の計算依頼を行なうステップと、この計算依頼を受けた前記マルチキャスト転送経路計算装置が前記計算依頼に基づいて前記主転送経路および前記予備転送経路を計算するステップと、その計算結果を前記マルチキャスト転送経路設定装置に通知するステップと、この通知を受け取った前記マルチキャスト転送経路設定装置が受け取った前記計算結果に従い主転送経路および予備転送経路を設定するステップとを実行することができる（請求項２）。

これにより、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置とを個別に設置し、１つのマルチキャスト転送経路計算装置により複数のマルチキャスト転送経路設定装置に対応することができる。

また、前記マルチキャスト転送装置が前記マルチキャストネットワーク内のリンク上を流れるトラヒックの状態を計測するステップと、当該計測結果を前記マルチキャスト転送経路計算装置に通知するステップと、前記マルチキャスト転送経路計算装置は、通知された前記計測結果に基づいて主転送経路および予備転送経路を計算するステップとを実行することができる（請求項３）。

これにより、ネットワークのトラヒック状況を反映した経路計算を行なうことができる。

また、前記マルチキャスト転送装置が前記マルチキャストネットワーク内のリンク上を流れるトラヒックの状態を計測する際に、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測するステップを実行することができる（請求項４）。

これにより、リンク毎にトラヒック状況を反映した経路計算を行なうことができる。さらに、同じリンクであってもデータが流れる際の進行方向毎にトラヒック状況を反映した経路計算を行なうことができるので、ネットワークの実際のトラヒック状況を精度よく反映することができる。

また、前記マルチキャスト転送経路計算装置は、前記計測結果に基づき前記主転送経路を計算して求めるステップと、この計算された主転送経路上のリンク毎に予備転送経路を計算して求めるステップとを実行することができる（請求項５）。

このようにリンク単位で予備転送経路を計算することにより、予備転送経路の全リンクに対して予備転送経路を設定することができる。

また、前記マルチキャスト転送経路計算装置は、前記求めた主転送経路から経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分けるステップと、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除き、仮始点から仮終点までの最短経路を前記計測結果に基づいて求めるステップと、最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とするステップと、最短経路が求まらない場合には前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除き、前記仮始点から仮終点までの最短経路を求めるステップと、このステップにより未だ最短経路が求まらない場合にはこれまでの仮終点の隣接ノードを新たな仮終点とし、前記始点を含まないそれ以外の部分経路木のうち前記新たな仮終点以外のノードとそのノードに接続されているリンクを全て除いて前記仮始点から前記新たな仮終点への最短経路を求めるステップを最短経路が求まるまで繰り返し行なうステップとを実行することができる（請求項６）。

これにより、効率よく予備転送経路の最短経路を計算することができる。

また、前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用するステップを実行することができる（請求項７）。

これにより、コストの安い経路を予備転送経路とすることができ、ネットワーク運営を効率よく行なうことができる。ここで「コストの安い経路」とは、例えば、距離の短い経路である。ここでいう距離とは、単に物理的な距離に限らず、帯域の大きさや通信品質によって定義することもできる。その他、本発明では、コストの定義については限定しない。

また、前記求めた主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了するステップを実行することができる（請求項８）。

本発明の第二の観点はマルチキャスト転送経路計算装置であって、本発明の特徴とするところは、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する手段と、この計算する手段により求めた主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する手段とを備えたところにある（請求項９）。

また、前記計算する手段は、マルチキャストネットワーク内のリンク上を流れるトラヒックの状態の計測結果に基づいて主転送経路および予備転送経路を計算する手段を備えることができる（請求項１０）。

また、前記計測結果は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、前記計算する手段は、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に前記主転送経路に対する予備転送経路を計算する手段を備えることができる（請求項１１）。

また、前記計算する手段は、求めた主転送経路から経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける手段と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除き、仮始点から仮終点までの最短経路を前記計測結果に基づいて求める手段と、最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とする手段と、最短経路が求まらない場合には前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除き、前記仮始点から仮終点までの最短経路を求める手段と、この手段により未だ最短経路が求まらない場合にはこれまでの仮終点の隣接ノードを新たな仮終点とし、前記始点を含まないそれ以外の部分経路木のうち前記新たな仮終点以外のノードとそのノードに接続されているリンクを全て除いて前記仮始点から前記新たな仮終点への最短経路を求めるステップを最短経路が求まるまで繰り返し行なう手段とを備えることができる（請求項１２）。

また、前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用する手段を備えることができる（請求項１３）。

本発明の第三の観点はプログラムであって、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する機能と、この計算する機能により求めた主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する機能とを備えたマルチキャスト転送経路計算装置に相応する機能を実現させるところにある（請求項１４）。

また、前記計算する機能として、マルチキャストネットワーク内のリンク上を流れるトラヒックの状態の計測結果に基づいて主転送経路および予備転送経路を計算する機能を実現させることができる（請求項１５）。

また、前記計測結果は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、前記計算する機能として、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に前記主転送経路に対する予備転送経路を計算する機能を実現させることができる（請求項１６）。

また、前記計算する機能として、求めた主転送経路から経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける機能と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除き、仮始点から仮終点までの最短経路を前記計測結果に基づいて求める機能と、最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とする機能と、最短経路が求まらない場合には前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除き、前記仮始点から仮終点までの最短経路を求める機能と、この機能により未だ最短経路が求まらない場合にはこれまでの仮終点の隣接ノードを新たな仮終点とし、前記始点を含まないそれ以外の部分経路木のうち前記新たな仮終点以外のノードとそのノードに接続されているリンクを全て除いて前記仮始点から前記新たな仮終点への最短経路を求めるステップを最短経路が求まるまで繰り返し行なう機能とを実現させることができる（請求項１７）。

また、前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用する機能を実現させることができる（請求項１８）。

本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項１９）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。

これにより、汎用の情報処理装置を用いて、マルチキャスト転送でデータ転送を行なっている際、リンク故障時に、リンク毎の予備リンクを持つことにより、故障発生の近隣ノードで予備転送経路に切り替え可能となり、高速な切り替えが実現できるマルチキャスト転送経路計算装置を実現することができる。

本発明によれば、マルチキャスト転送でデータ転送を行なっている際、リンク故障時に、リンク毎の予備リンクを持つことにより、故障発生の近隣ノードで予備転送経路に切り替え可能となり、高速な切り替えが実現できる。

以下、本発明の一実施形態によるマルチキャスト転送経路設定方法を、図面を参照して説明する。

図１は本発明の概要を説明するための図である。本発明は、主転送経路上の全リンクに対して予備転送経路を設定するマルチキャスト転送経路設定方法である。そして、当該マルチキャストネットワークは、マルチキャスト転送経路設定装置が設けられた複数のノードにより構成されており、また各ノードのいずれかのノードにマルチキャスト転送経路計算装置またはマルチキャスト転送経路設定装置が設けられている（請求項１）。

そして、ネットワーク内のマルチキャスト転送装置が各リンクで発生するデータ転送遅延などを示すネットワーク計測情報をデータが流れる方向毎に収集し（１）、そしてマルチキャスト転送装置がマルチキャスト転送経路計算装置やマルチキャスト転送経路設定装置にネットワーク計測情報を通知する（２）。そしてマルチキャストにより転送するデータの転送経路の設定の必然性が生じたときに、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置によって後述の処理に従いデータの主転送経路と予備転送経路の設定が実行される（請求項３、４）。

本発明においては、マルチキャスト転送装置はノード間で転送されるデータのネットワーク計測情報を収集する機能を有し、マルチキャスト転送経路計算装置は主転送経路と予備転送経路とを計算する機能を有し、マルチキャスト転送経路設定装置は主転送経路と予備転送経路とを設定する機能を有する。また、１つのノードが複数の上述の装置の機能を有している場合もある。

ここで、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置とが異なる装置である場合には、マルチキャスト転送経路設定装置がマルチキャスト転送経路計算装置へ主転送経路と予備転送経路の計算を依頼する（請求項２）。また、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置が同一装置である場合、マルチキャスト転送経路設定装置が自身の経路計算モジュールに主転送経路計算と予備転送経路計算を指示する。

そして、マルチキャスト転送経路設定装置もしくはマルチキャスト転送経路計算装置の経路計算モジュールが、収集した情報をもとに主転送経路と予備転送経路とを計算する（５）。そして計算結果はマルチキャスト転送経路設定装置の経路設定モジュールに通知され（６）、当該計算結果を受信したマルチキャスト転送経路設定装置がデータの主転送経路と予備転送経路とを設定する。

なお、上述のネットワーク計測情報を収集する機能においては、すでに提案されているＯＳＰＦ−ＴＥ(Open Shortest Path First-Traffic Engineering)やＩＳ−ＩＳ−ＴＥ(Intermediate
System-Intermediate System-Traffic Engineering)などの隣接ノード間でのネットワーク計測情報を交換する機能が備わった経路計算プロトコルを拡張して用いることによりネットワーク計測情報を収集する。

また、マルチキャスト転送経路計算装置は、マルチキャスト転送装置からネットワーク計測情報を受信する機能と、かつ主転送経路と予備転送経路の計算結果を送信するパケット転送機能、主転送経路と予備転送経路の計算に使用するアルゴリズムを実現するプログラム、ネットワーク計測情報や主転送経路と予備転送経路の経路計算プログラムや主転送経路と予備転送経路の計算結果を保存する記憶媒体、ならびに主転送経路と予備転送経路計算を実行する経路計算機能とにより構成される。

本発明で使用する主転送経路計算プログラムは、公知のアルゴリズムを実装したプログラムを利用する。また、本発明で使用する予備転送経路プログラムは、求まった主転送経路上のリンク毎に予備転送経路を計算することを目的とする（請求項５）。

求めた主転送経路から経路上のリンクの予備転送経路計算時に、該当するリンクを除くことで、主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分け、前記始点を含む部分経路木に含まれる全ノードへ結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除いて、仮始点から仮終点までの最短経路を前記計測結果に基づいて公知の最短経路アルゴリズムによって求める。

最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とし、最短経路が求まらない場合には、前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除いて、前記仮始点から仮終点までの最短経路を公知の最短経路アルゴリズムによって求める。

最短経路が求まらない場合には、仮終点の隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除いて、前記仮始点から仮終点への最短経路を求める。これを１つの最短経路が求まるまで繰り返して行なう（請求項６）。

このとき、前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用する（請求項７）。前記求めた主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する（請求項８）。

次に、本発明のマルチキャスト転送経路設定方式を実現するために必要なマルチキャスト転送経路計算装置とマルチキャスト転送経路設定装置を説明する。図２は、マルチキャスト転送経路計算装置の構成を示す図である（請求項９）。図２に示すマルチキャスト転送経路計算装置はネットワーク内のノードや各ノードをつなぐリンクで発生する遅延やコストに関するネットワーク計測情報を管理する情報管理部２０と、主転送経路と予備転送経路とを計算する経路計算部３０と、送受信するパケットを処理するパケット処理部４０により構成される。そして、マルチキャスト転送経路計算装置のパケット処理部４０が情報管理部２０で管理されるネットワーク計測情報や経路計算依頼の受信や、経路計算部３０が計算した主転送経路と予備転送経路の計算結果のマルチキャスト転送経路設定装置への送信を行なう。

また、マルチキャスト転送経路計算装置の情報管理部２０はトラヒック状態の情報の収集に使用するＯＳＰＦやＩＳ−ＩＳなどのルーチングプロトコルで使用される情報交換プロトコルを処理するルーチングプロトコルモジュール２１とそのプロトコルによって得られたネットワークのトポロジ遅延、コストなどのネットワーク計測情報を管理する計測情報記憶部２２とを備えている。また、経路計算部３０は、主転送経路と予備転送経路とを計算する経路計算処理モジュール３１と、計算結果を記憶する計算結果記憶部３２とを備えている。

また、パケット処理部４０は、到着したパケットの種別を判断し、そのパケットを転送、または情報管理部に送るパケット転送処理モジュール４１とパケットの転送先を記録するパケット転送テーブル記憶部４２と、ネットワークインタフェース４３とを備えている。

図３はマルチキャスト転送経路設定装置の構成を示す図である。図３に示すマルチキャスト転送経路設定装置は、ネットワーク内のノードやリンクで発生する遅延やコストに関する情報を管理する情報管理部５０と、自身の処理により発生する遅延やコストなどを測定する測定部６０と、新たなデータフローが発生したときに経路設定を行なう経路設定用プロトコル処理部７０と、到着したパケットを処理するパケット処理部８０とにより構成される。

そして、情報管理部５０の基本構成はマルチキャスト転送経路計算装置の情報管理部２０と同様であり、ルーチングプロトコルモジュール５１と、計測情報記憶部５２とを備えている。また、測定部６０はパケット処理部８０が備えるネットワークインタフェース８３の状態や、ネットワーク上の各ノードの処理の遅延などの情報を測定する測定モジュールを備えている。

また、パケット処理部８０は、到着したパケットの種別を判断し、パケットの転送を行い、また、新規の経路設定の決定を判断するパケット処理モジュール８１と、パケットの転送先を記録するパケット転送テーブル記憶部８２と、ネットワークインタフェース８３とを備えている。また、マルチキャスト転送経路設定装置は経路計算部９０を備えており、経路計算部９０は主転送経路と予備転送経路とを計算する経路計算処理モジュール９１と、計算結果を記憶する計算結果記憶部９２とを備えている。なお、主転送経路と予備転送経路の計算をマルチキャスト転送経路設定装置が行なう場合には、この経路計算部９０がマルチキャスト転送経路計算装置と同様の処理を行なう。

経路設定用プロトコル処理部７０はパケット処理部８０から主転送経路設定および予備転送経路設定の依頼を受信し、その経路設定依頼のマルチキャスト転送経路計算装置への送信処理を行なう。また、経路設定用プロトコル処理部７０は、マルチキャスト転送経路計算装置から受信した主転送経路および予備転送経路の計算結果に従ってデータ転送のための主転送経路およびリンク故障対応のための予備転送経路を設定する機能を有する。

なお、マルチキャスト転送経路計算装置とマルチキャスト転送経路設定装置とが同一ノードである場合には、そのノードはマルチキャスト転送経路計算装置およびマルチキャスト転送経路設定装置の各処理部を有し、上述の各処理部の処理を行なう。また、マルチキャスト転送装置の機能が同一ノードに備えられる場合には、経路設定用プロトコル処理部７０は隣接するノードに対して経路計算依頼を行なう。

次に、上記のマルチキャスト転送経路計算装置、マルチキャスト転送経路設定装置、マルチキャスト転送装置の動作を説明する。ネットワーク内のマルチキャスト転送装置の機能を有するノードは常にネットワークのトポロジや遅延やコストを表すネットワーク計測情報を隣接ノード間で交換する。そして各ノードは、その交換の処理によって得られたネットワーク計測情報を記憶する。

ノードが交換するネットワーク計測情報は、自ノードで計測したネットワーク計測情報のみならず、自ノードが保持する他ノードが計測したネットワーク計測情報も含まれる。これらの交換動作により、各ノードはネットワーク内の全ノードにおける接続情報や遅延などのネットワーク計測情報を保持する。そして、新たに主転送経路および予備転送経路を設定するマルチキャスト転送経路設定装置の機能を有するノードは、マルチキャスト転送経路計算装置の機能を有するノードに経路計算依頼をする。

このとき、マルチキャスト転送経路計算装置の機能を有するノードは情報管理部２０で管理されているネットワーク内のトポロジや遅延などトラヒックに関するネットワーク計測情報と、経路計算依頼をしたノードから送られてきた終点の情報に基づいて主転送経路およびその予備転送経路を計算する（請求項１０）。また、このとき、ネットワーク計測情報は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に前記主転送経路に対する予備転送経路を計算する（請求項１１）。

図４はマルチキャスト転送経路計算装置における予備転送経路計算の処理を示すフローチャートである。まず、マルチキャスト転送経路設定装置の機能を有するノードからの主経路計算と予備転送経路計算依頼をマルチキャスト転送経路計算装置が受け付ける。このとき、マルチキャスト転送経路計算装置は、マルチキャスト転送経路設定装置からデータ転送の終点の情報を受け付ける。すると、マルチキャスト転送経路計算装置の経路計算部３０が情報管理部２０の計測情報記憶部２２に記録されているネットワークのトポロジやトラヒック状態を示すネットワーク計測情報を読み取る（ステップＳ１）。

そして、経路計算処理モジュール３１がネットワーク計測情報を用いて、公知の主転送経路アルゴリズムを利用して、データ転送の始点と全終点までのコストの和が最小の主転送経路を計算する（ステップＳ２）。このとき、経路計算処理モジュール３１は経路計算依頼を送信したノードを始点とし、データ転送の終点の全ノードまでのコストの和が最小の主転送経路を計算する。なお、主転送経路を求めるためのアルゴリズムは、例えば、非特許文献４または５により公知のアルゴリズムを利用する。

次に、マルチキャスト転送経路計算装置の経路計算処理モジュール３１はステップＳ２で求めた主転送経路上のリンク毎の予備転送経路を全リンクに対して求める。主転送経路上のあるリンクに対する予備転送経路をステップＳ３からステップＳ９で求める。予備転送経路は全リンクに対して求めるため、ステップＳ３からステップＳ９を全リンクに対して行なう（請求項９）。

主転送経路上にあるリンクに着目してそのリンクの予備転送経路を求める際、その着目したリンクを主転送経路から削除し、主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける（ステップＳ３）。始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成する（ステップＳ４）。始点を含まない部分経路木の頂点を仮終点とする（ステップＳ５）。始点を含まない部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除いて、仮始点から仮終点までの最短経路を求める（ステップＳ７）。ステップＳ７で最短経路を求める際には、例えば、非特許文献６により公知のアルゴリズムを利用する。

ステップＳ７で最短経路が求まれば（ステップＳ８）、その最短経路を予備転送経路とし着目したリンクに関する予備転送経路の計算を終了する（ステップＳ９）。ステップＳ７で最短経路が求まらない場合（ステップＳ８）には仮終点の木の下流隣接ノードを仮始点とする（ステップＳ６）。ただし、仮終点の木の下流隣接ノードが複数ある場合には１ノードずつ仮終点としてステップＳ６からＳ７を下流隣接ノード分繰り返す（請求項１２）。

このときに、前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用する（請求項１３）。

最後にこのようにして計算して得られた予備転送経路の結果を経路計算処理モジュール３１は、パケット処理部４０を介して経路計算依頼を出したノードに返送する。

なお、本実施例では、マルチキャスト転送装置が遅延などのネットワーク計測情報を収集する際には、ＯＳＰＦ−ＴＥを用いる。ＯＳＰＦ−ＴＥはユニキャストのルーチングプロトコルであるＯＳＰＦのトポロジ情報交換情報に遅延などのネットワーク内のトラヒック情報を格納した転送プロトコルである。

また、本実施例では、データの転送経路を設定するプロトコルとして、明示的な経路指定を実施するＲＳＶＰ−ＴＥ(Resource Reservation Protocol-Traffic Engineering)を拡張したマルチキャストＭＰＬＳ(Multi
Protocol Label Switching)プロトコルを使用する。マルチキャストＭＰＬＳは、通常のＭＰＬＳで用いられるＲＳＶＰ−ＴＥに対して、ＬＳＰ(Label
Switched Path)を生成するメッセージ中にツリートポロジを格納できる情報要素を追加し、そのトポロジ情報に沿ってＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ ＬＳＰを確立することができる技術である。

次に、本発明による転送経路を計算する処理の一実施例について説明する。図５はマルチキャストネットワークを示す図である。この図においてＰはデータ転送の始点でマルチキャスト転送設定装置でもある。Ｒ１〜Ｒ４がデータ転送の終点である。また、Ｎ１〜Ｎ１０は始点と終点との間の中間ノードであり、マルチキャスト転送装置の機能を有している。なお、マルチキャスト転送設定装置Ｐ、ノードＮ１〜Ｎ１０、終点Ｒ１〜Ｒ４は転送ケーブル（リンク）により接続されてマルチキャストネットワークを構成している。また、各リンクは遅延とコストという２つの特性を持っている。

そして、マルチキャスト転送経路設定装置Ｐは、マルチキャスト転送経路計算装置Ｃが計算した結果に基づいて、終点Ｒ１〜Ｒ４に対してデータを転送する。

マルチキャスト転送経路計算装置Ｃは、マルチキャスト転送経路設定装置Ｐからの経路計算依頼を受けると、主転送経路を計算し、その結果を受けて予備転送経路を計算する。マルチキャスト転送経路設定装置ＰがＮ１からＮ９のリンクに対する予備転送経路を計算する例を示す。

まず、図６に示すように、Ｎ１からＮ９のリンクを削除し、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける。次に、図７に示すように、始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成する。次に、図８に示すように、始点を含まない部分経路木の頂点を仮終点とし、始点を含まない部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除いて、仮始点から仮終点までの最短経路を求める。このとき、仮始点から始点を含む部分経路木に含まれる全ノードを結ぶリンクのリンクコストは全て同じ値にしてもよいし、異なる値にしてもよい。ただし、そのコストを元に、例えば、非特許文献６により公知のアルゴリズムを用いて最短経路を求める。本例では、図９に示すように、最短経路が求まったので、Ｎ１からＮ９のリンクに対する予備転送経路の計算は終了し、Ｎ２→Ｎ５→Ｎ７→Ｎ９が求まった予備転送経路となる。

例えば図１０のようなマルチキャストネットワークの場合、Ｎ１からＮ９のリンクに対する予備転送経路を求めようとしても、仮始点から始点を含まない部分経路木の頂点（Ｎ９）への最短経路が見つからないため、頂点の木の下流隣接ノード（Ｎ１０、Ｎ８）を仮終点として図４で示したステップＳ６から、ステップＳ７を下流ノードの個数回（本例の場合２回）繰り返す。ここで最短経路が見つかれば予備転送経路の計算は終了する。図１１はＮ１０を仮終点として仮始点からの最短経路を計算した例を示す。

本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムとして実現することができる（請求項１４〜１８）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項１９）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、情報管理部２０、経路計算部３０、パケット処理部４０にそれぞれ相応する機能を実現させることができる。

本発明によれば、マルチキャスト転送でデータ転送を行なっている際、リンク故障時に、リンク毎の予備リンクを持つことにより、故障発生の近隣ノードで予備転送経路に切り替え可能となり、高速な切り替えが実現できる。これにより、ネットワークユーザのサービス品質向上に寄与することができる。

本発明の概念図。 本実施例のマルチキャスト転送経路計算装置の構成図。 本実施例のマルチキャスト転送経路設定装置の構成図。 本実施例の転送経路計算アルゴリズムのフロー図。 マルチキャストネットワーク例を示す図。 ２つの部分経路木に分けた結果を示す図。 仮始点を作成した様子を示す図。 仮終点を作成し最短経路を求める様子を示す図。 求まった予備転送経路を示す図。 マルチキャストネットワーク例を示す図。 仮始点から最短経路を求めている様子を示す図。 ユニキャスト転送とマルチキャスト転送とを比較する図。

符号の説明

２０、５０ 情報管理部
２１、５１ ルーチングプロトコルモジュール
２２、５２ 計測情報記憶部
３０、９０ 経路計算部
３１、９１ 経路計算処理モジュール
３２、９２ 計算結果記憶部
４０、８０ パケット処理部
４１、８１ パケット転送処理モジュール
４２、８２ パケット転送テーブル記憶部
４３、８３ ネットワークインタフェース
６０ 測定部
７０ 経路設定用プロトコル処理部
Ｃ マルチキャスト転送経路計算装置
Ｐ マルチキャスト転送経路設定装置
Ｎ１〜Ｎ１０ ノード
Ｒ１〜Ｒ４ 終点

Claims (19)

1. マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、
   与えられた始点と複数の終点とをそれぞれ結ぶマルチキャスト主転送経路（以下、主転送経路という）をマルチキャスト転送経路計算装置により計算するステップと、
   この計算された主転送経路をマルチキャスト転送経路設定装置が設定するステップと、
   前記計算した主転送経路上の全リンクに対してそれぞれマルチキャスト予備転送経路（以下、予備転送経路という）を前記マルチキャスト転送経路計算装置により計算するステップと、
   この計算された全予備転送経路をマルチキャスト転送経路設定装置により設定するステップと
   を実行することを特徴とするマルチキャスト転送経路設定方法。
2. 前記マルチキャスト転送経路設定装置が前記マルチキャスト転送経路計算装置に主転送経路および予備転送経路の計算依頼を行なうステップと、
   この計算依頼を受けた前記マルチキャスト転送経路計算装置が前記計算依頼に基づいて前記主転送経路および前記予備転送経路を計算するステップと、
   その計算結果を前記マルチキャスト転送経路設定装置に通知するステップと、
   この通知を受け取った前記マルチキャスト転送経路設定装置が受け取った前記計算結果に従い主転送経路および予備転送経路を設定するステップと
   を実行する請求項１記載のマルチキャスト転送経路設定方法。
3. 前記マルチキャスト転送装置が前記マルチキャストネットワーク内のリンク上を流れるトラヒックの状態を計測するステップと、
   当該計測結果を前記マルチキャスト転送経路計算装置に通知するステップと、
   前記マルチキャスト転送経路計算装置は、通知された前記計測結果に基づいて主転送経路および予備転送経路を計算するステップと
   を実行する
   請求項１記載のマルチキャスト転送経路設定方法。
4. 前記マルチキャスト転送装置が前記マルチキャストネットワーク内のリンク上を流れるトラヒックの状態を計測する際に、
   リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測するステップを実行する
   請求項３記載のマルチキャスト転送経路設定方法。
5. 前記マルチキャスト転送経路計算装置は、
   前記計測結果に基づき前記主転送経路を計算して求めるステップと、
   この計算された主転送経路上のリンク毎に予備転送経路を計算して求めるステップと
   を実行する請求項３または４記載のマルチキャスト転送経路設定方法。
6. 前記マルチキャスト転送経路計算装置は、
   前記求めた主転送経路から経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分けるステップと、
   前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除き、仮始点から仮終点までの最短経路を前記計測結果に基づいて求めるステップと、
   最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とするステップと、
   最短経路が求まらない場合には前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除き、前記仮始点から仮終点までの最短経路を求めるステップと、
   このステップにより未だ最短経路が求まらない場合にはこれまでの仮終点の隣接ノードを新たな仮終点とし、前記始点を含まないそれ以外の部分経路木のうち前記新たな仮終点以外のノードとそのノードに接続されているリンクを全て除いて前記仮始点から前記新たな仮終点への最短経路を求めるステップを最短経路が求まるまで繰り返し行なうステップと
   を実行する請求項５記載のマルチキャスト転送経路設定方法。
7. 前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用するステップを実行する請求項６記載のマルチキャスト転送経路設定方法。
8. 前記求めた主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了するステップを実行する請求項６記載のマルチキャスト転送経路設定方法。
9. マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、
   与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する手段と、
   この計算する手段により求めた主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する手段と
   を備えたことを特徴とするマルチキャスト転送経路計算装置。
10. 前記計算する手段は、マルチキャストネットワーク内のリンク上を流れるトラヒックの状態の計測結果に基づいて主転送経路および予備転送経路を計算する手段を備えた請求項９記載のマルチキャスト転送経路計算装置。
11. 前記計測結果は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、
    前記計算する手段は、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に前記主転送経路に対する予備転送経路を計算する手段を備えた
    請求項１０記載のマルチキャスト転送経路計算装置。
12. 前記計算する手段は、
    求めた主転送経路から経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける手段と、
    前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除き、仮始点から仮終点までの最短経路を前記計測結果に基づいて求める手段と、
    最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とする手段と、
    最短経路が求まらない場合には前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除き、前記仮始点から仮終点までの最短経路を求める手段と、
    この手段により未だ最短経路が求まらない場合にはこれまでの仮終点の隣接ノードを新たな仮終点とし、前記始点を含まないそれ以外の部分経路木のうち前記新たな仮終点以外のノードとそのノードに接続されているリンクを全て除いて前記仮始点から前記新たな仮終点への最短経路を求めるステップを最短経路が求まるまで繰り返し行なう手段と
    を備えた請求項９記載のマルチキャスト転送経路計算装置。
13. 前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用する手段を備えた請求項１２記載のマルチキャスト転送経路計算装置。
14. 情報処理装置にインストールすることにより、その情報処理装置に、
    マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、
    与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する機能と、
    この計算する機能により求めた主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する機能と
    を備えたマルチキャスト転送経路計算装置に相応する機能を実現させることを特徴とするプログラム。
15. 前記計算する機能として、マルチキャストネットワーク内のリンク上を流れるトラヒックの状態の計測結果に基づいて主転送経路および予備転送経路を計算する機能を実現させる請求項１４記載のプログラム。
16. 前記計測結果は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、
    前記計算する機能として、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に前記主転送経路に対する予備転送経路を計算する機能を実現させる請求項１５記載のプログラム。
17. 前記計算する機能として、
    求めた主転送経路から経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける機能と、
    前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノード自身とそのノードに接続されているリンクを全て除き、仮始点から仮終点までの最短経路を前記計測結果に基づいて求める機能と、
    最短経路が求まった場合には求まった最短経路を該当するリンクに対する予備転送経路とする機能と、
    最短経路が求まらない場合には前記始点を含まないそれ以外の部分経路木の頂点から見た木の下流隣接ノードを仮終点とし、前記始点を含まないそれ以外の部分経路木のうち仮終点以外のノードとそのノードに接続されているリンクを全て除き、前記仮始点から仮終点までの最短経路を求める機能と、
    この機能により未だ最短経路が求まらない場合にはこれまでの仮終点の隣接ノードを新たな仮終点とし、前記始点を含まないそれ以外の部分経路木のうち前記新たな仮終点以外のノードとそのノードに接続されているリンクを全て除いて前記仮始点から前記新たな仮終点への最短経路を求めるステップを最短経路が求まるまで繰り返し行なう機能と
    を実現させる請求項１６記載のプログラム。
18. 前記始点を含まないそれ以外の部分経路木から見た木の隣接ノードが複数存在し、前記仮始点から当該複数のノードへの最短経路が複数求められたときには、当該複数求められた最短経路のうちでコストの安い経路を予備転送経路として採用する機能を実現させる請求項１７記載のプログラム。
19. 請求項１４ないし１８のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。

Images