(57)【要約】【課題】  途中ノードでの現用予備切り替えを可能とし、切り替え時間を短縮する。【解決手段】  与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算し、主転送経路上の全リンクに対して予備転送経路を計算する。このときに、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測し主転送経路を計算し、この計算された主転送経路上のリンク毎に予備転送経路を計算して求める。【選択図】  図１
2005130369.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、
与えられた始点と複数の終点とをそれぞれ結ぶマルチキャスト主転送経路（以下、主転送経路という）をマルチキャスト転送経路計算装置により計算するステップと、
この計算された主転送経路をマルチキャスト経路設定装置が設定するステップと、
前記計算した主転送経路上の全リンクに対してそれぞれマルチキャスト予備転送経路（以下、予備転送経路という）を前記マルチキャスト転送経路計算装置により計算するステップと、
この計算された全予備転送経路をマルチキャスト転送経路設定装置により設定するステップと
を実行するマルチキャスト転送経路設定方法であって、
前記マルチキャスト転送経路計算装置は、
前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分けるステップと、
前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路（１≦ｋ≦Ｎ：ｋ、Ｎは１以上の整数）を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求めるステップと、
このｋ個の経路を求めるステップにより１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定するステップと、
前記ｋ個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求めるステップを最短経路が求まるまで繰り返し行うステップと
を実行することを特徴とするマルチキャスト転送経路設定方法。
【請求項２】
前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了するステップを実行する請求項１記載のマルチキャスト転送経路設定方法。
【請求項３】
マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、
与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する手段と、
前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する手段と
を備えたマルチキャスト転送経路計算装置であって、
前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける手段と、
前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路（１≦ｋ≦Ｎ：ｋ、Ｎは１以上の整数）を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める手段と、
このｋ個の経路を求める手段により１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する手段と、
前記ｋ個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める手順を最短経路が求まるまで繰り返し行う手段と
を備えたことを特徴とするマルチキャスト転送経路計算装置。
【請求項４】
前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する手段を備えた請求項３記載のマルチキャスト転送経路計算装置。
【請求項５】
情報処理装置にインストールすることにより、その情報処理装置に、
マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、
与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する機能と、
前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する機能と
を備えたマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムであって、
前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける機能と、
前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路（１≦ｋ≦Ｎ：ｋ、Ｎは１以上の整数）を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める機能と、
このｋ個の経路を求める機能により１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する機能と、
前記ｋ個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める手順を最短経路が求まるまで繰り返し行う機能と
を備えたマルチキャスト転送経路計算装置に相応する機能を実現させることを特徴とするプログラム。
【請求項６】
前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する機能を実現させる請求項５記載のプログラム。
【請求項７】
請求項５または６記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト転送に利用する。特に、マルチキャスト主転送経路（以下、主転送経路という）の障害対策に関する。
【背景技術】
【０００２】
コンピュータネットワーク上で、動画や音声を特定多数のユーザに配送するマルチキャスト転送が注目を集めている。この転送方式は、経路の始点と選択された１つ以上の終点とを結ぶ経路のうち、経路が分かれている部分において情報をコピーし、各終点へと情報を配送する。
【０００３】
特定多数の終点へ始点と一対一で転送を行うユニキャスト転送を用いて情報を配送した場合には、終点の数だけ始点は情報を用意する必要がある。よって、マルチキャスト転送を用いることにより、ネットワーク内の情報量は減少する。
【０００４】
マルチキャスト転送では特定多数の終点をマルチキャストグループと呼ばれる管理単位で管理を行い、マルチキャストグループに対して１つの転送経路が設定される。この転送経路は始点からマルチキャストグループに属するすべての終点を接続するように設定される。経路上のリンクが故障した場合には、ユニキャスト転送の場合には１対１の転送なので情報が届かなくなるといった影響を受ける終点は少ないが、マルチキャスト転送の場合には１対複数の転送であるため１つのリンク故障によって影響を受ける終点の数が多くなることがある。図１０にその例を示す。
【０００５】
本例ではユニキャスト転送の場合には情報が届かなくなるのは１受信者のみとなるが、マルチキャスト転送の場合には６終点となる。そのためマルチキャスト転送においてマルチキャスト予備転送経路（以下、予備転送経路という）を持つことはユニキャスト転送に比べて重要である。
【０００６】
現在、リンクに対する予備転送経路ではなく主転送経路に対して予備転送経路を求めるアルゴリズムとして以下のような方式が公開されている（例えば、非特許文献１、２、３参照）。
【０００７】
これらの方式は、主転送経路と予備転送経路を同時に求めるアルゴリズムであり、特に、非特許文献１で紹介されている方式は、主転送経路と予備転送経路が利用する帯域を少なくすることを目的にしている。
【非特許文献１】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 Transactions on Networking,7(5):641-652,1999.
【非特許文献４】V.Kompella 他,“Multicast routingfor multimedia communication,”IEEE/ACM Transactions on Networking,Volume:1Issue:3,pp.286-292,June 1993
【非特許文献５】Q.Zhu,他,“A source-based algorithmfor delay-constrained minimum-cost multicasting,”proc in IEEE INFOCOM’95,vol.1,pp.377-385,1995
【非特許文献６】E.Q.V.Martins,M.M.B.Pascal,andJ.L.E.Santos.Deviation Algorithms for Ranking Shortest Paths.InternationalJournal of Foundations of Computer Science.1999.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ここで、上記の非特許文献１、２、３で紹介されている技術では、故障発生が始点ノードに伝わらない限り、切替えができないため、切替えに時間がかかるという問題があった。切替えに時間がかかると受信者に情報が届かなくなる時間が長くなることになる。
【０００９】
本発明は、このような背景に行われたものであって、始点ではなく主転送経路上の各リンクに予備転送経路を準備することにより、途中ノードで切替えすることが可能となり、切替時間の短縮を実現できることを目的とする。
【課題を解決するための手段】
【００１０】
本発明の第一の観点は、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路をマルチキャスト転送経路計算装置により計算するステップと、この計算された主転送経路をマルチキャスト経路設定装置が設定するステップと、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を前記マルチキャスト転送経路計算装置により計算するステップと、この計算された全予備転送経路をマルチキャスト転送経路設定装置により設定するステップとを実行するマルチキャスト転送経路設定方法である。
【００１１】
ここで、本発明の特徴とするところは、前記マルチキャスト転送経路計算装置は、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分けるステップと、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路（１≦ｋ≦Ｎ：ｋ、Ｎは１以上の整数）を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求めるステップと、このｋ個の経路を求めるステップにより１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定するステップと、前記ｋ個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求めるステップを最短経路が求まるまで繰り返し行うステップとを実行するところにある（請求項１）。前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了するステップを実行することができる（請求項２）。これにより、効率よく予備転送経路の最短経路を計算することができる。
【００１２】
本発明の第二の観点は、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する手段と、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する手段とを備えたマルチキャスト転送経路計算装置である。
【００１３】
ここで、本発明の特徴とするところは、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける手段と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路（１≦ｋ≦Ｎ：ｋ、Ｎは１以上の整数）を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める手段と、このｋ個の経路を求める手段により１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する手段と、前記ｋ個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める手順を最短経路が求まるまで繰り返し行う手段とを備えたところにある（請求項３）。前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する手段を備えることができる（請求項４）。
【００１４】
本発明の第三の観点は、情報処理装置にインストールすることにより、その情報処理装置に、マルチキャスト転送装置がそれぞれ設けられた複数のノードにより構成されたマルチキャストネットワークに適用され、与えられた始点と複数の終点とをそれぞれ結ぶ主転送経路を計算する機能と、前記計算した主転送経路上の全リンクに対してそれぞれ予備転送経路を計算する機能とを備えたマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムである。
【００１５】
ここで、本発明の特徴とするところは、前記計算した主転送経路に対する経路上のリンク毎の予備転送経路計算時に、このリンクを除くことにより、前記主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける機能と、前記始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路（１≦ｋ≦Ｎ：ｋ、Ｎは１以上の整数）を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める機能と、このｋ個の経路を求める機能により１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定する機能と、前記ｋ個の経路を求めるステップにより未だ最短経路が求まらないときにはこれまでの仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める手順を最短経路が求まるまで繰り返し行う機能とを備えたマルチキャスト転送経路設定装置に相応する機能を実現させるとこにある（請求項５）。前記計算した主転送経路上の全リンクに対し、前記予備転送経路を求めた時点で予備転送経路の計算を終了する機能を実現させることができる（請求項６）。
【００１６】
本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項７）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００１７】
これにより、汎用の情報処理装置を用いて、マルチキャスト転送でデータ転送を行っている際、リンク故障時にリンク毎の予備リンクを持つことで、故障発生の近隣ノードで予備転送経路に切替が可能となり、高速な切替が実現できるマルチキャスト転送経路計算装置を実現することができる。
【発明の効果】
【００１８】
本発明によれば、マルチキャスト転送でデータ転送を行っている際、リンク故障時にリンク毎の予備リンクを持つことで、故障発生の近隣ノードで予備転送経路に切替が可能となり、高速な切替が実現できる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の一実施形態によるマルチキャスト転送経路設定方法を、図面を参照して説明する。
【００２０】
図１は本発明の概要を説明するための図である。本発明は、主転送経路上の全リンクに対して予備転送経路を設定するマルチキャスト転送経路設定方法である。そして、当該マルチキャストネットワークは、マルチキャスト転送経路設定装置が設けられた複数のノードにより構成されており、また、各ノードのいずれかのノードにマルチキャスト転送経路計算装置またはマルチキャスト転送経路設定装置が設けられている。
【００２１】
そして、ネットワーク内のマルチキャスト転送装置が各リンクで発生するデータ転送遅延などを示すネットワーク計測情報をデータが流れる方向ごとに収集し（１）、そしてマルチキャスト転送装置がマルチキャスト転送経路計算装置やマルチキャスト転送経路設定装置にネットワーク計測情報を通知する（２）。そしてマルチキャストにより転送するデータの転送経路の設定の必然性が生じたときに、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置によって後述の処理に従いデータの主転送経路と予備転送経路の設定が実行される。
【００２２】
本発明においては、マルチキャスト転送装置はノード間で転送されるデータのネットワーク計測情報を収集する機能を有し、マルチキャスト転送経路計算装置は、主転送経路と予備転送経路を計算する機能を有し、マルチキャスト転送経路設定装置は主転送経路と予備転送経路を設定する機能を有する。また、１つのノードが複数の上述の装置の機能を有している場合もある。
【００２３】
ここで、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置とが異なる装置である場合には、マルチキャスト転送経路設定装置がマルチキャスト転送経路計算装置へ主転送経路と予備転送経路の計算を依頼する。また、マルチキャスト転送経路設定装置とマルチキャスト転送経路計算装置とが同一装置である場合には、マルチキャスト転送経路設定装置が自身の経路計算モジュールに主転送経路計算と予備転送経路計算とを指示する。
【００２４】
そして、マルチキャスト転送経路設定装置もしくはマルチキャスト転送経路計算装置の経路計算モジュールが、収集した情報をもとに主転送経路と予備転送経路とを計算する（５）。そして計算結果はマルチキャスト転送経路設定装置の経路設定モジュールに通知され（６）、当該計算結果を受信したマルチキャスト転送経路設定装置がデータの主転送経路と予備転送経路とを設定する。
【００２５】
なお、上述のネットワーク計測情報を収集する機能においては、既に提案されているＯＳＰＦ−ＴＥ(Open Shortest Path First-Traffic Engineering)やＩＳ−ＩＳ−ＴＥ(Intermediate
system-Intermediate system-Traffic Engineering)などの隣接ノード間でのネットワーク計測情報を交換する機能が備わった経路計算プロトコルを拡張して用いることによりネットワーク計測情報を収集する。
【００２６】
また、マルチキャスト転送経路計算装置は、マルチキャスト転送装置からネットワーク計測情報を受信する機能と、かつ主転送経路と予備転送経路の計算結果を送信するパケット転送機能、主転送経路と予備転送経路の計算に使用するアルゴリズムを実現するプログラム、ネットワーク計測情報や主転送経路と予備転送経路の経路計算プログラムや主転送経路と予備転送経路の計算結果を保存する記憶媒体、ならびに主転送経路と予備転送経路計算を実行する経路計算機能により構成される。
【００２７】
本発明で使用する主転送経路計算プログラムは、公知のアルゴリズムを実装したプログラムを利用する。また、本発明で使用する予備転送経路プログラムは、求まった主転送経路上のリンク毎に予備転送経路を計算することを目的とする。
【００２８】
計算した主転送経路に対する経路上のリンクの予備転送経路計算時に、このリンクを除くことで、マルチキャスト主転送経路を、マルチキャスト主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分け、前記始点を含む部分経路木に含まれる全ノードへ結ぶ仮始点を作成し、前記始点を含まないそれ以外の部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の経路を前記計測結果に基づいて公知のｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムによって求め、１つ以上の経路が求まった場合には求まった経路の中から所定の条件を満足するものを予備転送経路として決定する。
【００２９】
もし、経路が求まらない場合には、仮終点の下流隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路をマルチキャスト転送装置により計測されたネットワーク内のリンク上を流れるトラヒックの状態に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める。以下上記と同様に、１つ以上の経路が求まれば、求まった経路の中から所定の条件を満足するものを予備転送経路として決定し、経路が求まらない場合には、仮終点の隣接ノードを仮終点とし、前記仮始点から当該仮終点までのｋ個の最短経路を前記トラヒック状況に基づいてｋｔｈ  ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて計算してｋ個の経路を求める。これを１つの予備転送経路が求まるまで行う（請求項１、３）。
【００３０】
なお、ここで所定の条件を満足する経路とは、例えば、主転送経路以上の帯域を確保できる経路であるとか、あるいは、主転送経路と同程度のリンクコストの経路である。
【００３１】
前記計算した主転送経路に対する経路上のリンクの全リンクに対して、予備転送経路を求めた時点で予備転送経路の計算を終了する（請求項２、４）。
【００３２】
次に、本発明のマルチキャスト転送経路設定方式を実現するために必要なマルチキャスト転送経路計算装置とマルチキャスト転送経路設定装置とを説明する。
【００３３】
図２はマルチキャスト転送経路計算装置の構成を示す図である。図２に示すマルチキャスト転送経路計算装置は、ネットワーク内のノードや各ノードをつなぐリンクで発生する遅延コストに関するネットワーク計測情報を管理する情報管理部２０と、主転送経路と予備転送経路を計算する経路計算部３０と、送受信するパケットを処理するパケット処理部４０により構成される。そして、マルチキャスト転送経路計算装置のパケット処理部４０が情報管理部２０で管理されるネットワーク計測情報や経路計算依頼の受信や、経路計算部３０が計算した主転送経路と予備転送経路の計算結果のマルチキャスト転送経路設定装置への送信を行う。
【００３４】
また、マルチキャスト転送経路計算装置の情報管理部２０はトラヒック状態の情報の収集に使用するＯＳＰＦやＩＳ−ＩＳなどのルーチングプロトコルで使用される情報交換プロトコルを処理するルーチングプロトコルモジュール２１とそのプロトコルによって得られたネットワークのトポロジや遅延、コストなどのネットワーク計測情報を管理する計測情報記憶部２２とを備えている。また、経路計算部３０は、主転送経路と予備転送経路とを計算する経路計算処理モジュール３１と、計算結果を記憶する計算結果記憶部３２とを備えている。
【００３５】
また、パケット処理部４０は、到着したパケットの種別を判断し、そのパケットを転送、または情報管理部に送るパケット転送処理モジュール４１とパケットの転送先を記録するパケット転送テーブル記憶部４２と、ネットワークインタフェース４３とを備えている。
【００３６】
図３は、マルチキャスト転送経路設定装置の構成を示す図である。図３に示すマルチキャスト転送経路設定装置は、ネットワーク内のノードやリンクで発生する遅延やコストに関する情報を管理する情報管理部５０と、自身の処理により発生する遅延やコストなどを測定する測定部６０と、新たなデータフローが発生したときに経路設定を行う経路設定用プロトコル処理部７０と、到着したパケットを処理するパケット処理部８０とにより構成される。
【００３７】
そして、情報管理部５０の基本構成はマルチキャスト転送経路計算装置の情報管理部２０と同様であり、ルーチングプロトコルモジュール５１と、計測情報記憶部５２とを備えている。また、測定部６０はパケット処理部８０が備えるネットワークインタフェース８３の状態や、ネットワーク上の各ノードの処理の遅延などの情報を測定する測定モジュール（図示省略）を備えている。
【００３８】
また、パケット処理部８０は到着したパケットの種別を判断し、パケットの転送を行い、また、新規の経路設定の決定を判断するパケット転送処理モジュール８１と、パケットの転送先を記録するパケット転送テーブル記憶部８２と、ネットワークインタフェース８３とを備えている。
【００３９】
また、マルチキャスト転送経路設定装置は、経路計算部９０を備えており、経路計算部９０は主転送経路と予備転送経路とを計算する計算処理モジュール９１と、計算結果を記憶する計算結果記憶部９２とを備えている。なお、主転送経路と予備転送経路の計算をマルチキャスト転送経路設定装置が行う場合には、この経路計算部９０がマルチキャスト転送経路計算装置と同様の処理を行う。
【００４０】
経路設定用プロトコル処理部７０はパケット処理部８０から主転送経路設定と予備転送経路設定依頼を受信し、その経路設定依頼のマルチキャスト転送経路計算装置への送信処理を行う。また、経路設定用プロトコル処理部７０はマルチキャスト転送経路計算装置から受信した主転送経路と予備転送経路の計算結果にしたがってデータ転送のための主転送経路とリンク故障対応のための予備転送経路を設定する機能を有する。
【００４１】
なお、マルチキャスト転送経路計算装置とマルチキャスト転送経路設定装置とが同一ノードである場合には、そのノードはマルチキャスト転送経路計算装置とマルチキャスト転送経路設定装置の各処理部を有し、上述の各処理部の処理を行う。また、マルチキャスト転送装置の機能が同一ノードに備えられる場合には、経路設定用プロトコル処理部７０は隣接するノードに対して経路計算依頼を行う。
【００４２】
次に、上記のマルチキャスト転送経路計算装置、マルチキャスト転送経路設定装置、マルチキャスト転送装置の動作を説明する。ネットワーク内のマルチキャスト転送装置の機能を有するノードは常にネットワークのトポロジや遅延やコストを表すネットワーク計測情報を隣接ノード間で交換する。そして各ノードは、その交換の処理によって得られたネットワーク計測情報を記憶する。
【００４３】
ノードが交換するネットワーク計測情報は、自ノードで計測したネットワーク計測情報のみならず、自ノードが保持する他ノードが計測したネットワーク計測情報も含まれる。これらの交換動作により、各ノードはネットワーク内の全ノードにおける接続情報や遅延などのネットワーク計測情報を保持する。そして、新たに主転送経路および予備転送経路を設定するマルチキャスト転送経路設定装置の機能を有するノードは、マルチキャスト転送経路計算装置の機能を有するノードに経路計算依頼をする。
【００４４】
このとき、マルチキャスト転送経路計算装置の機能を有するノードは情報管理部２０で管理されているネットワーク内のトポロジや遅延などのトラヒックに関するネットワーク計測情報と、経路計算依頼をしたノードから送られてきた終点の情報とに基づいて予備転送経路を計算する。また、このとき、ネットワーク計測情報は、リンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎にトラヒック状態を計測した計測結果であり、当該計測結果に基づきリンク毎に、かつ、当該リンクにデータが流れる際の進行方向毎に主転送経路に対する予備転送経路を計算する。
【００４５】
図４はマルチキャスト転送経路計算装置における予備転送経路計算の処理を示すフローチャートである。まず、マルチキャスト転送経路設定装置の機能を有するノードからの主経路計算と予備転送経路計算依頼をマルチキャスト転送経路計算装置が受け付ける。このとき、マルチキャスト転送経路計算装置は、マルチキャスト転送経路設定装置からデータ転送の終点の情報も受け付ける。すると、マルチキャスト転送経路計算装置の経路計算部３０が情報管理部２０の計測情報記憶部２２に記録されているネットワークのトポロジやトラヒック状態を示すネットワーク計測情報を読み取る（ステップＳ１）。
【００４６】
そして、経路計算処理モジュール３１がネットワーク計測情報を用いて、公知の主転送経路アルゴリズムを利用して、データ転送の始点と全終点までのコストの和が最小の主転送経路を計算する（ステップＳ２）。このとき、経路計算処理モジュール３１は経路計算依頼を送信したノードを始点とし、データ転送の終点の全ノードまでのコストの和が最小の主転送経路を計算する。なお、主転送経路を求めるためのアルゴリズムは、例えば、非特許文献４、５により公知のアルゴリズムを利用する。
【００４７】
次に、マルチキャスト転送経路計算装置の経路計算処理モジュール３１はステップＳ２で求めた主転送経路上のリンク毎の予備転送経路を全リンクに対して求める。主転送経路上のあるリンクに対する予備転送経路をステップＳ３からステップＳ９で求める。予備転送経路は全リンクに対して求めるため、ステップＳ３からステップＳ９を全リンクに対して行う。
【００４８】
主転送経路上にあるリンクに着目してそのリンクの予備転送経路を求める際、その着目したリンクを主転送経路から削除し、主転送経路を、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける（ステップＳ３）。始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成する（ステップＳ４）。始点を含まない部分経路木の頂点を仮終点とする（ステップＳ５）。仮始点から仮終点までのｋ個の最短経路を求める（ステップＳ７）。ステップＳ７でｋ個の最短経路を求める際には、例えば、非特許文献６のような公知アルゴリズムを利用する。
【００４９】
ステップＳ７で１つ以上の経路が求まれば（ステップＳ８）、その経路から最適な経路を着目したリンクに関する予備転送経路として計算を終了する（ステップＳ９）。ステップＳ７で１つも経路が求まらない場合（ステップＳ８）には仮終点の木の下流隣接ノードを仮始点とする（ステップＳ６）。ただし仮終点の木の下流隣接ノードが複数ある場合には１のずつ仮終点としてステップＳ６からステップＳ７を下流隣接ノード分繰り返す。
【００５０】
最後にこのようにして計算して得られた予備転送経路の結果を経路計算処理モジュール３１は、パケット処理部４０を介して経路計算依頼を出したノードに返送する。
【００５１】
なお、本実施例では、マルチキャスト転送装置が遅延などのネットワーク計測情報を収集する際には、ＯＳＰＦ−ＴＥを用いる。ＯＳＰＦ−ＴＥはユニキャストのルーチングプロトコルであるＯＳＰＦのトポロジ情報交換情報に遅延などのネットワーク内のトラヒック情報を格納した転送プロトコルである。
【００５２】
また、本実施例では、データの転送経路を設定するプロトコルとして、明示的な経路指定を実施するＲＳＶＰ−ＴＥ(Resource Reservation Protocol-Traffic Engineering)を拡張したマルチキャストＭＰＬＳ(Multi
Protocol Label Switching)プロトコルを使用する。マルチキャストＭＰＬＳは、通常のＭＰＬＳで用いられるＲＳＶＰ−ＴＥに対して、ＬＳＰ(Label
Switched Path)を生成するメッセージ中にツリートポロジを格納できる情報要素を追加し、そのトポロジ情報に沿ってＰｏｉｎｔ−ｔｏ−Ｍｕｌｔｉｐｏｉｎｔ  ＬＳＰを確立することができる技術である。
【００５３】
次に、本発明による転送経路を計算する処理の一実施例について説明する。図５はマルチキャストネットワークを示す図である。この図においてＰはデータ転送の始点でマルチキャスト転送設定装置でもある。Ｒ１〜Ｒ４がデータ転送の終点である。またＮ１〜Ｎ１０は始点と終点との間の中間ノードであり、マルチキャスト転送装置の機能を有している。なお、マルチキャスト転送設定装置Ｐ、ノードＮ１〜Ｎ１０、終点Ｒ１〜Ｒ４は転送ケーブル（リンク）により接続されてマルチキャストネットワークを構成している。そして、各リンクは遅延とコストという２つの特性を持っている。そして、マルチキャスト転送経路設定装置Ｐは、マルチキャスト転送経路計算装置Ｃが計算した結果に基づいて、終点Ｒ１〜Ｒ４に対してデータを転送する。
【００５４】
マルチキャスト転送経路計算装置Ｃは、マルチキャスト転送経路設定装置Ｐからの経路計算依頼を受けると、主転送経路を計算し、その結果を受けて予備転送経路を計算する。マルチキャスト転送経路設定装置ＰがＮ１からＮ９のリンクに対する予備転送経路を計算する例を示す。
【００５５】
まず、図６に示すように、Ｎ１からＮ９のリンクを削除し、主転送経路の始点を含む部分経路木と始点を含まないそれ以外の部分経路木の２つに分ける。次に、図７に示すように、始点を含む部分経路木に含まれる全ノードを結ぶ仮始点を作成する。次に、図８に示すように、始点を含まない部分経路木の頂点を仮終点とし、仮始点から仮終点までのｋ個の最短経路を求める。このとき、仮始点から始点を含む部分経路木に含まれる全ノードを結ぶリンクのコストは全て同じ値にしても良いし、異なる値にしてもよい。ただしそのコストをもとに公知のアルゴリズムを用いてｋ個の最短経路を求める。本例では３個（ｋ＝３）の最短経路が求まった。この中でどの経路を予備転送経路として選択するかはオペレータやプログラムに委ねられるが、本例では、図９に破線で示すように、マルチキャストデータの逆流をしないＮ２→Ｎ５→Ｎ７→Ｎ９を最適な経路として予備転送経路とする。
【００５６】
例えばＮ１からＮ９のリンクに対する予備転送経路を求めようとしても、仮始点から始点を含まない部分経路木の頂点（Ｎ９）への経路が見つからない場合には、頂点の木の下流隣接ノード（Ｎ１０、Ｎ８）を仮終点として図４で示したステップＳ６から、ステップＳ７を下流ノード回（本例の場合は２回）繰り返す。ここで１つ以上の経路が見つかれば予備転送経路の計算は終了する（請求項１、３）。計算した主転送経路上の全リンクに対し、予備転送経路を求めた時点で予備転送経路の計算を終了する（請求項２、４）。
【００５７】
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のマルチキャスト転送経路計算装置に相応する機能を実現させるプログラムとして実現することができる（請求項５、６）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項７）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、情報管理部２０、経路計算部３０、パケット処理部４０にそれぞれ相応する機能を実現させることができる。また、マルチキャスト転送経路設定装置にマルチキャスト転送経路計算装置の機能が含まれている場合には、当該情報処理装置に、情報管理部５０、経路計算部９０、パケット処理部８０にそれぞれ相応する機能を実現させることができる。さらに、マルチキャスト転送経路設定装置の機能として、経路設定用プロトコル処理部７０、測定部６０に相応する機能を実現させることもできる。
【産業上の利用可能性】
【００５８】
本発明によれば、マルチキャスト転送でデータ転送を行っている際、リンク故障時にリンク毎の予備リンクを持つことで、故障発生の近隣ノードで予備転送経路に切替が可能となり、高速な切替が実現できる。これにより、ネットワークユーザのサービス品質向上に寄与することができる。
【図面の簡単な説明】
【００５９】
【図１】本発明の概要図。
【図２】本実施例のマルチキャスト転送経路計算装置の構成図。
【図３】本実施例のマルチキャスト転送経路設定装置の構成図。
【図４】本実施例の転送経路計算アルゴリズムのフロー図。
【図５】マルチキャストネットワーク例を示す図。
【図６】２つの部分経路木に分けた結果を示す図。
【図７】仮始点を作成した様子を示す図。
【図８】仮終点を作成し最短経路を求める様子を示す図。
【図９】求まった予備転送経路を示す図。
【図１０】ユニキャスト転送とマルチキャスト転送とを比較する図。
【符号の説明】
【００６０】
２０、５０  情報管理部
２１、５１  ルーチングプロトコルモジュール
２２、５２  計測情報記憶部
３０、９０  経路計算部
３１、９１  経路計算処理モジュール
３２、９２  計算結果記憶部
４０、８０  パケット処理部
４１、８１  パケット転送処理モジュール
４２、８２  パケット転送テーブル記憶部
４３、８３  ネットワークインタフェース
６０  測定部
７０  経路設定用プロトコル処理部
Ｃ  マルチキャスト転送経路計算装置
Ｐ  マルチキャスト転送経路設定装置
Ｎ１〜Ｎ１０  ノード
Ｒ１〜Ｒ４  終点
【図１】
2005130369.tif 000003
【図２】
2005130369.tif 000004
【図３】
2005130369.tif 000005
【図４】
2005130369.tif 000006
【図５】
2005130369.tif 000007
【図６】
2005130369.tif 000008
【図７】
2005130369.tif 000009
【図８】
2005130369.tif 000010
【図９】
2005130369.tif 000011
【図１０】
2005130369.tif 000012