(57)【要約】【課題】単一リンク障害からの復旧を高速化するための、Fast Reroute方式を適用した最適なポイントツーマルチポイントパスの経路計算を簡単にすること。【解決手段】ネットワーク内の各リンクを迂回する予備パス経路を予め求め(S21)、予備パス経路を固定し、整数計画法を用いて現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパス経路(S22)および経路コスト(S23)を求める。次に、現用ポイントツーマルチポイントパス経路を固定し、整数計画法を用いて現用パスと予備パス群全体の経路コストを最小化する予備パス群の経路(S25)および経路コスト(S26)を求める。経路コストの改善度が所定値未満になるまで現用ポイントツーマルチポイントパスおよび予備パス経路を更新しつつ経路計算処理を繰り返す(S24,S27)。【選択図】図２
2008182423.tif 000002
【特許請求の範囲】
【請求項１】
Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間の現用パスの経路および該現用パスが通過する各リンクを迂回する予備パス群を求めるポイントツーマルチポイントパス経路計算装置であって、
ネットワーク内の各リンクを迂回する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過するリンクを迂回する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段と、
現用ポイントツーマルチポイントパスの経路を前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に固定し、整数計画法を用いて、現用パスと現用パスが通過するリンクを迂回する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段と、
前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスおよび予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段を備え、
前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路を直前に求められたものに更新しつつ交互に繰り返し実行し、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力することを特徴とするポイントツーマルチポイントパス経路計算装置。
【請求項２】
さらにネットワーク内の各リンクを迂回する予備パスの経路を最小コスト経路の形で予め求める予備パス計算手段を備え、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パスの経路を当初に予備パスの経路として固定することを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算装置。
【請求項３】
前記現用パス経路計算手段は、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、該制約式の元で、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過するリンクを迂回する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求めることを特徴とする請求項１または２に記載のポイントツーマルチポイントパス経路計算装置。
【請求項４】
前記予備パス経路計算手段は、現用パスが通過する各リンクを迂回する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、該制約式の元で、現用パスが通過するリンクを迂回する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求めることを特徴とする請求項１ないし３のいずれかに記載のポイントツーマルチポイントパス経路計算装置。
【請求項５】
Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間で現用パスの経路および該現用パスが通過する各リンクを迂回する予備パス群を求めるために、コンピュータを、
ネットワーク内の各リンクを迂回する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過するリンクを迂回する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段、現用ポイントツーマルチポイントパスの経路を前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に固定し、整数計画法を用いて、現用パスと現用パスが通過するリンクを迂回する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段、前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段として機能させ、
前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路をそれ以前に求められたものに更新しつつ、交互に繰り返し行わせ、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力させるためのプログラム。
【請求項６】
さらにコンピュータを、ネットワーク内の各リンクを迂回する予備パス群の経路を最小コスト経路の形で予め求める予備パス計算手段として機能させ、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パス群の経路を当初に予備パス群の経路として固定する請求項５に記載のプログラム。
【請求項７】
前記現用パス経路計算手段は、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、該制約式の元で、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過するリンクを迂回する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求める請求項５または６に記載のプログラム。
【請求項８】
前記予備パス経路計算手段は、現用パスが通過する各リンクを迂回する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、該制約式の元で、現用パスが通過するリンクを迂回する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求める請求項５ないし７のいずれかに記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポイントツーマルチポイントパス経路計算装置およびプログラムに関し、特に、単一リンク障害からの復旧を高速化するための、Fast Reroute方式を適用した最適なポイントツーマルチポイントパスの経路を求めることができるポイントツーマルチポイントパス経路計算装置およびプログラムに関する。
【背景技術】
【０００２】
非特許文献１には、現用パスが通過する各リンクあるいはノードを迂回する予備パス群を設けるFast Reroute方式が提案されている。Fast Reroute方式は、MPLS(multiprotocol label switching)パス用に標準化されており、これによれば一対の発着ノードを接続する現用ポイントツーポイントパスの単一リンク障害あるいは単一ノード障害からの復旧を高速化できる。
【０００３】
Fast Reroute方式では、現用パスが通過する各リンクあるいはノードを迂回する予備パス群を予め設定しておき、リンク障害あるいはノード障害が生じたとき、障害となったリンクあるいはノードを使用しないようにトラフィックを予備パスに迂回させる。
【０００４】
非特許文献２には、現用ポイントツーポイントパスのコストに加えて、Fast Reroute方式によって設定される予備パス群のコストも考慮して、全体のコストを最小化する現用パスおよび予備パス群経路を求める方法が提案されている。
【非特許文献１】P. Pan, G. Swallow, and A. Atlas Ed., "Fast Reroute Extensions to RSVP-TE for LSP Tunnels," IETF RFC4050, May 2005.
【非特許文献２】M. Kodialam and T. V. Lakshman, "Restorable dynamic quality of service routing," IEEE Commun. Mag., vol. 40, no. 6, pp. 72-81, June 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１で提案されているのは、一対の発着ノードを接続するポイントツーポイントパスについてのFast Reroute方式であり、これをそのまま発ノードと複数の着ノードを接続するポイントツーマルチポイントパスに対して適用した場合、得られるパスの経路の最適性が劣化する。すなわち、発ノードと各着ノードを接続する現用ポイントツーポイントパスと予備パス群の経路を個別に求め、これにより得られた現用ポイントツーポイントパスの経路および予備パス群の経路を全ての着ノードについて合成した場合、個別には最適な経路であっても全体として最適なものとはならない。
【０００６】
非特許文献２には、Fast Reroute方式を適用した場合の現用パスとそれに伴う予備パスの経路を計算することが提案されている。しかし、これもポイントツーポイントパスについてのものである。しかも、これではホップバイホップで経路を計算するので、必ずしも全体コストを最小化するパスの経路を求めることができない。
【０００７】
本発明の目的は、上記課題を解決し、単一リンク障害からの復旧を高速化するための、Fast Reroute方式を適用した最適なポイントツーマルチポイントパスの経路を簡単な計算で求めることができるポイントツーマルチポイントパス経路計算装置およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明は、Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間の現用パスの経路および該現用パスが通過する各リンクを迂回する予備パス群を求めるポイントツーマルチポイントパス経路計算装置であって、ネットワーク内の各リンクを迂回する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過するリンクを迂回する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段と、現用ポイントツーマルチポイントパスの経路を前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に固定し、整数計画法を用いて、現用パスと現用パスが通過するリンクを迂回する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段と、前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスおよび予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段を備え、前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路を直前に求められたものに更新しつつ交互に繰り返し実行し、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力する点に第１の特徴がある。
【０００９】
また、本発明は、さらにネットワーク内の各リンクを迂回する予備パスの経路を最小コストの経路の形で予め求める予備パス計算手段を備え、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パスの経路を当初に予備パスの経路として固定する点に第２の特徴がある。
【００１０】
また、本発明は、前記現用パス経路計算手段が、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、該制約式の元で、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過するリンクを迂回する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求める点に第３の特徴がある。
【００１１】
さらに、本発明は、前記予備パス経路計算手段が、現用パスが通過する各リンクを迂回する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、該制約式の元で、現用パスが通過するリンクを迂回する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求める点に第４の特徴がある。
【００１２】
本発明は、ポイントツーマルチポイントパス経路計算装置としてだけでなく、コンピュータを上記各手段として機能させるプログラムとしても実現できる。
【発明の効果】
【００１３】
本発明によれば、単一リンク障害からの復旧を高速化するための、Fast Reroute方式を適用したポイントツーマルチポイントパスの最小コスト経路を、整数計画法を用いて求めることができる。その際、現用パスの経路と現用パスが通過するリンクを迂回する予備パス群の経路を個別に交互に繰り返し求めるので、整数計画法を用いて一括計算して求める場合に比べて問題規模を小さくでき、計算を簡単化することができ、かつ十分な最適性を有する経路を求めることができる。
【発明を実施するための最良の形態】
【００１４】
以下、図を参照して本発明を説明する。図１は、本発明が適用されるネットワークの例を示す概念図である。図１は、発ノードをA、着ノードをB,C,E,H,Jとする現用ポイントツーマルチポイントパス(図示実線)が設定された例であり、発ノードを白丸で示し、着ノードを黒丸で示している。なお、D,F,G,Iは中継ノードである。
【００１５】
Fast Reroute方式では、発ノードと複数の着ノード間を接続する現用ポイントツーマルチポイントパスの単一リンク障害からの復旧を高速化するために、ネットワーク内において、個々のリンクを迂回する予備パス群を設定する。すなわち、ネットワーク内の個々のリンクに対して該リンクの始点を発ノード、該リンクの終点を着ノードとして該リンクを迂回する予備パスを設定する。
【００１６】
図１では、例えばリンクB-Cに対する予備パスの経路はB-E-D-C、リンクC-Dに対する予備パスの経路はC-F-E-D、リンクC-Gに対する予備パスの経路はC-I-H-Gである。これらの予備パスの経路をそれぞれ破線で示している。ここでは単一のリンク障害を想定しているので、リンクB-Cに対する予備パスとリンクC-Dに対する予備パスは、リンクE-Dのリソースを共用することができる。
【００１７】
本発明は、Fast Reroute方式を適用して単一リンク障害を復旧することを想定し、現用ポイントツーマルチポイントパスの経路コストに加え、単一リンク障害に対応してFast Reroute方式によって現用パスが通過するリンクを迂回するように設定される予備パス群の経路コストも考慮して、最小経路コストとなる現用パスおよび予備パス群を求めるものである。以下、実施形態を詳細に説明する。
【００１８】
図２は、本発明の一実施形態におけるパス経路の計算処理を示すフローチャートである。なお、本発明は、以下に説明する各処理を実行する手段を備えたパス経路計算装置として実現できるが、コンピュータを、各処理を実行する手段として機能させるプログラムとしても実現できる。
【００１９】
まず、ネットワーク内の各リンクを迂回する予備パスの経路を予め求める(S21)。ここで求める予備パスは各リンクを迂回する任意のものとしてもよいが、効率的に最適経路を求めるという面からは、各リンクを迂回する最小コスト経路の形で予め求めるのが好ましい。最小コスト経路は、経路を構成するリンクのコスト累積値が最小となるようにして求めることができる。
【００２０】
次に、S21で求められた予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求め(S22)、求められた現用ポイントツーマルチポイントパスの経路を保存する。なお、ここで求められた経路を保存するのは、現用ポイントツーマルチポイントパスの経路が初めて求められたからであり、後述するように、それ以前に求められた現用ポイントツーマルチポイントパスの経路が存在する場合にはその経路を今回求められた経路に更新する。
【００２１】
S22で現用ポイントツーマルチポイントパスの経路を求める整数計画法における制約式は次の通りである。
(発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式)
【００２２】
【数１】
2008182423.tif 000003
(現用ポイントツーマルチポイントパスの経路に関する制約式)
【００２３】
【数２】
2008182423.tif 000004
(予備パス間でのリソース共用に関する制約式)
【００２４】
【数３】
2008182423.tif 000005
【００２５】
ここで、各シンボルの意味は次の通りである。
N：ネットワークを構成するノードの集合
n：ネットワークを構成するノード
Link：ネットワークを構成するリンクの集合
l,l′：ネットワークを構成するリンク(式中で定義)
s：発ノード
D:着ノードの集合
d：１つの着ノード
nｉｎ：ノードnへの入リンクの集合
nｏｕｔ：ノードnからの出リンクの集合
sｉｎ：発ノードsへの入リンクの集合
sｏｕｔ：発ノードsからの出リンクの集合
dｉｎ：着ノードdへの入リンクの集合
dｏｕｔ：着ノードdからの出リンクの集合
BLｌ：リンクlを迂回する予備パスの経路を構成するリンクの集合
wｄ，ｌ：リンクlが着ノードdへの現用ポイントツーポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ：リンクlが現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ′：リンクl′が現用パスが通過するリンクを迂回する予備パス群の経路に含まれる時１、含まれない時０となるバイナリー変数
【００２６】
上記式(1)は、発ノードsと各着ノードd間の現用ポイントツーポイントパスの経路について、発ノードsからその現用ポイントツーポイントパスが必ず１本出て行き、また、発ノードsにその現用ポイントツーポイントパスが入ることはないこと(上段の式)、着ノードdにはその現用ポイントツーポイントパスが必ず１本入り、また、着ノードdからその現用ポイントツーポイントパスが出ることはないこと(中段の式)、発ノードsと着ノードd以外のノードn(中継ノード)では、その現用ポイントツーポイントパスが入っていなければ、その現用ポイントツーポイントパスが出ることはなく、その現用ポイントツーポイントパスが入っていれば、その現用ポイントツーポイントパスが出て行き、また、その現用ポイントツーポイントパスの出入りは、１本だけであること(下段の式)を制約している。
【００２７】
上記式(2)は、あるリンクに関して、着ノードdへの現用ポイントツーポイントパスの経路に含まれれば、該リンクのリソースは現用ポイントツーマルチポイントパスによって使用されること、すなわち、各着ノードdへの現用ポイントツーポイントパスを合成したものが現用ポイントツーマルチポイントパスであることを制約している。
【００２８】
上記式(3)は、あるリンクに関して、現用パスが通過する各リンクに対応する予備パス群の経路の少なくとも１つに含まれれば、該リンクのリソースが予備パスによって使用されること、また、予備パスによって使用されるリンクのリソース量は、含まれる予備パスの経路の数には依存しないことを制約している。
【００２９】
整数計画法において最小とすべき目的関数は、下記式(4)で与えられる。ここで、distｌはリンクlのコストである。式(4)は、現用ポイントツーマルチポイントパスの経路を構成するリンクと現用パスが通過する各リンクに対応する予備パス群の経路を構成するリンクの距離の総和Sum Distanceを求めるものである。なお、リンクコストdistｌがリンクlの距離に対応するものとしている。
【００３０】
【数４】
2008182423.tif 000006
【００３１】
上記(1)〜(3)の制約式を条件とし、上記式(4)を目的関数とする整数計画法を解くことによってWｌの値(1か0のバイナリ変数)を求める。これによって求められたWｌの値(=1)は現用ポイントツーマルチポイントパスの経路を示す。
【００３２】
次に、現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の経路コストを求める(S23)。なお、経路コストは上記式(4)で求めることができる。
【００３３】
次に、S23で求められた経路コストの改善度が予め設定した閾値よりも小さいか否かを判定する(S24)。経路コストの改善度とは、それ以前に求められた経路コストから改善(低下)した度合を意味する。当初では以前に求められた経路コストが存在しないのでS25に進む。
【００３４】
S25では、S22で求められた現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて、現用パスが通過する各リンクに対して、コストを最小化する予備パスの経路を求める。そして、現用パスが通過する各リンクに対する予備パスの経路をここで求められた予備パスの経路に更新する。S25で新たに予備パスの経路を求める整数計画法における制約式は次の通りである。
(現用パスが通過する各リンクを迂回する予備パスの経路に関する制約式)
【００３５】
【数５】
2008182423.tif 000007
(予備パス間でのリソース共用に関する制約式)
【００３６】
【数６】
2008182423.tif 000008
【００３７】
ここで、新たに出てきた各シンボルの意味は次の通りである。それ以外の各シンボルの意味は上記と同じである。
ｓｌ：リンクlの始点ノード
ｄｌ：リンクlの終点ノード
sｌｉｎ：始点ノードｓｌへの入リンクの集合
sｌｏｕｔ：始点ノードｓｌからの出リンクの集合
dｌｉｎ：終点ノードｄｌへの入リンクの集合
dｌｏｕｔ：終点ノードｄｌからの出リンクの集合
WL：現用ポイントツーマルチポイントパスの経路を構成するリンクの集合
bｌ，ｌ′：リンクl′が、現用パスが通過するリンクlを迂回する予備パスの経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ′：リンクl′が現用パスが通過するリンクを迂回する予備パス群の経路に含まれる時１、含まれない時０となるバイナリー変数
【００３８】
上記式(5)は、現用パスが通過する始点ノードｓｌと終点ノードｄｌ間のリンクlを迂回する予備パスの経路について、リンクl以外の出リンクを使用して、始点ノードｓｌから予備パスが必ず１本出て行き、また、始点ノードｓｌにその予備パスが入ることはないこと(上段の式)、リンクl以外の入リンクを使用して、終点ノードｄｌにはその予備パスが必ず１本入り、また、終点ノードｄｌからその予備パスが出ることはないこと(中段の式)、始点ノードｓｌと終点ノードｄｌ以外のノードでは、その予備パスが入っていなければ、その予備パスが出ることはなく、その予備パスが入っていれば、その予備パスが出て行き、また、その予備パスの出入りは、１本だけであること(下段の式)を制約している。
【００３９】
上記式(6)は、あるリンクに関して、現用パスが通過する各リンクに対応する予備パス群の経路の少なくとも１つに含まれれば、該リンクのリソースが予備パスによって使用されること、また、使用される該リンクのリソース量は、含まれる予備パスの経路数には依存しないことを制約している。
【００４０】
この場合、現用パスの経路コストは固定であるので、整数計画法において最小とすべき目的関数は、下記式(7)で与えることができる。式(7)は、現用パスが通過する各リンクに対応する予備パス群の経路を構成するリンクの距離の総和Sum Distanceを求めるものである。
【００４１】
【数７】
2008182423.tif 000009
【００４２】
上記(5)、(6)の制約式を条件とし、上記式(7)を目的関数とする整数計画法を解くことによってbｌ，ｌ′の値(1か0のバイナリ変数)を求める。これによって計算されたbｌ，ｌ′の値(=1)は、現用パスが通過する各リンクを迂回する予備パス群の新たな経路を示す。
【００４３】
次に、現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の経路コストを求める(S26)。なお、経路コストは上記式(7)に現用パスの経路コストを加算することにより求めることができる。
【００４４】
次に、S23で求められた経路コストに対するS26で求められた経路コストの改善度が予め設定した閾値よりも小さいか否かを判定する(S27)。そして、経路コストの改善度が予め設定した閾値よりも小さいと判定された場合には経路計算処理を終了する。そうでないと判定された場合はまだコスト改善の余地があるとしてS22に戻り、新たに経路計算処理を繰り返す。
【００４５】
S27で経路計算処理を終了する場合には、S22で求められた経路を現用ポイントツーマルチポイントパスの経路として出力する。予備パス群の経路としては、S25で更新後あるいは更新前の経路を出力する。
【００４６】
S22に戻った場合には、新たにS22以下の経路計算処理を繰り返す。繰り返しの経路計算処理でのS22では、S25で更新された予備パスの経路を固定して現用ポイントツーマルチポイントパスの経路を求め、それ以前に求められた現用ポイントツーマルチポイントパスの経路を今回求められた経路に更新する。そして、更新後の現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の経路コストを求め(S23)、この経路コストがS26で求められた経路コストより予め設定した閾値以上に改善されたか否かを判定する(S24)。ここで経路コストの改善度が予め設定した閾値よりも小さいと判定された場合には経路計算処理を終了し、そうでないと判定された場合はS25に進む。
【００４７】
S24で経路計算処理を終了する場合には、S22で更新後あるいは更新前の経路を現用ポイントツーマルチポイントパスの経路として出力する。予備パス群の経路としては、S25で求められた経路を出力する。
【００４８】
S26〜S27では、前回と同様に、現用パスが通過する各リンクを迂回する予備パス群の経路、現用パスと現用パスが通過する各リンクを迂回する予備パス群全体の経路コストを求め、経路コストの改善度が予め設定した閾値より小さければ経路計算処理を終了し、そうでなければS22に戻る。以下、同様に経路計算処理を繰り返す。
【００４９】
本発明では、整数計画法を用いて現用パスの経路と現用パスが通過する各リンクを迂回する予備パス群の経路を交互に繰り返し求めるので、十分に最適性を有する経路を簡単に求めることができる。現用パスの経路と現用パスが通過する各リンクを迂回する予備パス群の経路を同時に求めようとすると、整数計画法におけるバイナリー変数の数が、(全リンク数)*((着信ノード数)+(全リンク数))よりも多くなって問題規模が非常に大きくなり、処理負担が増大する。
【００５０】
しかし、本発明では、S22の計算でのバイナリー変数の数は(全リンク数)*(着信ノード数)、S25の計算でのバイナリー変数の数は(全リンク数)*(現用パスが通過するリンク数)程度となって問題規模を小さくでき、処理負担を軽減することができる。
【００５１】
本発明によれば、ポイントツーマルチポイント通信サービスを高信頼かつリソースの利用効率よく実現することができ、これによって複数拠点への映像配信サービスなどを高信頼かつ低コストで提供することができるようになる。
【図面の簡単な説明】
【００５２】
【図１】本発明が適用されるネットワークの例を示す概念図である。
【図２】本発明におけるポイントツーマルチポイントパス経路の計算処理を示すフローチャートである。
【符号の説明】
【００５３】
A・・・発ノード、B,C,E,H,J・・・着ノード、D,F,G,I・・・中継ノード
【図１】
2008182423.tif 000010
【図２】
2008182423.tif 000011