ポイントツーマルチポイントパス経路計算装置およびプログラム
【課題】単一ノード障害からの復旧を高速化するための、Fast Reroute方式を適用した最適なポイントツーマルチポイントパスの経路計算を簡単にすること。
【解決手段】ネットワーク内の各隣接リンクペアに対する予備パスの経路を予め求め(S21)、予備パスの経路を固定し、整数計画法を用いて現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路(S22)および経路コスト(S23)を求める。次に、現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて全体の経路コストを最小化する予備パス群の経路(S25)および経路コスト(S26)を求める。経路コストの改善度が所定閾値未満になるまで以上の経路計算処理を交互に繰り返す(S24,S27)。
【解決手段】ネットワーク内の各隣接リンクペアに対する予備パスの経路を予め求め(S21)、予備パスの経路を固定し、整数計画法を用いて現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路(S22)および経路コスト(S23)を求める。次に、現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて全体の経路コストを最小化する予備パス群の経路(S25)および経路コスト(S26)を求める。経路コストの改善度が所定閾値未満になるまで以上の経路計算処理を交互に繰り返す(S24,S27)。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポイントツーマルチポイントパス経路計算装置およびプログラムに関し、特に、単一ノード障害からの復旧を高速化するための、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方式では、発ノードと複数の着ノード間を接続する現用ポイントツーマルチポイントパスの単一ノード障害からの復旧を高速化するために、ネットワーク内において各隣接リンクペアに対する予備パス群を設定する。すなわち、ネットワーク内において各ノードを介して隣接し、現用パスが通過する各リンクペア(隣接リンクペア)に対して、該隣接リンクペアの上流側リンクの始点を発ノード、下流側リンクの終点を着ノードとして、該ノードを迂回する予備パスを設定する。
【００１６】
図１において、ノードCを迂回する予備パスとしては、隣接リンクペアB-C,C-Dと隣接リンクペアB-C,C-Gに対する予備パスを設定する必要がある。隣接リンクペアB-C,C-Dに対する予備パスの経路は、例えばB-E-Dであり、隣接リンクペアB-C,C-Gに対する予備パスの経路は、B-E-D-H-Gである。これらの予備パスの経路をそれぞれ破線で示している。ここでは単一のノード障害を想定しているので、リンクB-EとリンクE-Dのリソースを共用することができる。
【００１７】
本発明は、Fast Reroute方式を適用して単一ノード障害を復旧することを想定し、現用ポイントツーマルチポイントパスの経路コストに加え、単一ノード障害に対応してFast Reroute方式によって現用パスが通過する各隣接リンクペアに対して設定される予備パス群の経路コストも考慮して、最小経路コストとなる現用パスおよび予備パス群を求めるものである。以下、実施形態を詳細に説明する。
【００１８】
図２は、本発明の一実施形態におけるパス経路の計算処理を示すフローチャートである。なお、本発明は、以下に説明する各処理を実行する手段を備えたパス経路計算装置として実現できるが、コンピュータを、各処理を実行する手段として機能させるプログラムとしても実現できる。
【００１９】
まず、ネットワーク内の各隣接リンクペアに対する予備パスの経路を予め求める(S21)。ここで求める予備パスは各隣接リンクペアに対して任意のものとすることができるが、効率的に最適経路を求めるという面からは、各隣接リンクペアを迂回する最小コスト経路の形で予め求めるのが好ましい。最小コスト経路は、経路を構成するリンクのコスト累積値が最小となるようにして求めることができる。
【００２０】
次に、S21で求められた予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求め(S22)、求められた現用ポイントツーマルチポイントパスの経路を保存する。なお、ここで求められた経路を保存するのは、現用ポイントツーマルチポイントパスの経路が初めて求められたからであり、後述するように、それ以前に求められた現用ポイントツーマルチポイントパスの経路が存在する場合にはその経路を今回求められた経路に更新する。
【００２１】
S22で現用ポイントツーマルチポイントパスの経路を求める整数計画法における制約式は次の通りである。
(発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式)
【００２２】
【数１】
(現用ポイントツーマルチポイントパスの経路に関する制約式)
【００２３】
【数２】
(隣接リンクペアの通過に関する制約式)
【００２４】
【数３】
(予備パス間でのリソース共用に関する制約式)
【００２５】
【数４】
【００２６】
ここで、各シンボルの意味は次の通りである。
n：ネットワークを構成するノード
N：ネットワークを構成するノードnの集合
l：ネットワークを構成するリンク
Link：ネットワークを構成するリンクlの集合
lp：隣接リンクペア
LP：隣接リンクペアlpの集合
l′：隣接リンクペアlpを構成する上流側リンク
l′′：隣接リンクペアlpを構成する下流側リンク
s：発ノード
d：１つの着ノード
D：着ノードdの集合
sｉｎ：発ノードsへの入リンクの集合
sｏｕｔ：発ノードsからの出リンクの集合
dｉｎ：着ノードdへの入リンクの集合
dｏｕｔ：着ノードdからの出リンクの集合
nｉｎ：ノードnへの入リンクの集合
nｏｕｔ：ノードnからの出リンクの集合
Wｌ′：リンクl′が現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ′′：リンクl′′が現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
BLPｌｐ：隣接リンクペアlpに対する予備パスの経路を構成するリンクの集合
wｄ，ｌ：リンクlが着ノードdへの現用ポイントツーポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ：リンクlが現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌｐ：隣接リンクペアlpが現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ：リンクlが、現用パスが通過する隣接リンクペアlpに対応する予備パス群の経路に含まれる時１、含まれない時０となるバイナリー変数
【００２７】
上記式(1)は、発ノードsと各着ノードd間の現用ポイントツーポイントパスの経路について、発ノードsからその現用ポイントツーポイントパスが必ず１本出て行き、また、発ノードsにその現用ポイントツーポイントパスが入ることはないこと(上段の式)、着ノードdにはその現用ポイントツーポイントパスが必ず１本入り、また、着ノードdからその現用ポイントツーポイントパスが出ることはないこと(中段の式)、発ノードsと着ノードd以外のノードn(中継ノード)では、その現用ポイントツーポイントパスが入っていなければ、その現用ポイントツーポイントパスが出ることはなく、その現用ポイントツーポイントパスが入っていれば、その現用ポイントツーポイントパスが出て行き、また、その現用ポイントツーポイントパスの出入りは、１本だけであること(下段の式)を制約している。
【００２８】
上記式(2)は、あるリンクに関して、着ノードdへの現用ポイントツーポイントパスの経路に含まれれば、該リンクのリソースは現用ポイントツーマルチポイントパスによって使用されること、すなわち、各着ノードへの現用ポイントツーポイントパスを合成したものが現用ポイントツーマルチポイントパスであること制約している。
【００２９】
上記式(3)は、現用パスが隣接リンクペアを通過するとは、現用パスが隣接リンクペアを構成する上流側および下流側の２つのリンクの両方を通過することであることを制約している。
【００３０】
上記式(4)は、あるリンクに関して、現用パスが通過する各隣接リンクペアに対する予備パス群の経路の少なくとも１つに含まれれば、該リンクのリソースが予備パスによって使用されること、また、予備パスによって使用されるリンクのリソース量は、含まれる予備パスの経路数には依存しないことを制約している。
【００３１】
整数計画法において最小とすべき目的関数は、下記式(5)で与えられる。ここで、distｌはリンクlのコストである。式(5)は、現用ポイントツーマルチポイントパスの経路を構成するリンクと現用パスが通過する各隣接リンクペアに対する予備パス群の経路を構成するリンクの距離の総和Sum Distanceを求めるものである。なお、リンクコストがリンクの距離に対応するものとしている。
【００３２】
【数５】
【００３３】
上記(1)〜(4)の制約式を条件とし、上記式(5)を目的関数とする整数計画法を解くことによってWｌの値(1か0のバイナリ変数)を求める。これによって求められたWｌの値(=1)は現用ポイントツーマルチポイントパスの経路を示す。
【００３４】
次に、現用パスと現用パスが通過する各隣接リンクペアに対応する予備パス群全体の経路コストを求める(S23)。なお、経路コストは上記式(5)で求めることができる。
【００３５】
次に、S23で求められた経路コストの改善度が予め設定した閾値よりも小さいか否かを判定する(S24)。経路コストの改善度とは、それ以前に求められた経路コストから改善(低下)した度合を意味する。当初では以前に求められた経路コストが存在しないのでS25に進む。
【００３６】
S25では、S22で求められた現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて、現用パスが通過する各隣接リンクペアに対して、コストを最小化する予備パスの経路を求める。そして、現用パスが通過する各隣接リンクペアに対する予備パスの経路を、ここで求めた予備パスの経路に更新する。S25で新たに予備パスの経路を求める整数計画法における制約式は次の通りである。
(現用パスが通過する各隣接リンクペアに対する予備パスの経路に関する制約式)
【００３７】
【数６】
(予備パス間でのリソース共用に関する制約式)
【００３８】
【数７】
【００３９】
ここで、新たに出てきた各シンボルの意味は次の通りである。それ以外の各シンボルの意味は上記と同じである。
sｌｐ：隣接リンクペアlpを構成する上流側リンクl′の始点ノード
dｌｐ：隣接リンクペアlpを構成する下流側リンクl′′の終点ノード
sｌｐ ｏｕｔ：始点ノードsｌｐからの出リンクの集合
sｌｐ ｉｎ：始点ノードsｌｐへの入リンクの集合
dｌｐ ｏｕｔ：終点ノードdｌｐからの出リンクの集合
dｌｐ ｉｎ：終点ノードdｌｐへの入リンクの集合
WLP：現用ポイントツーマルチポイントパスの経路を構成する隣接リンクペアlpの集合
bｌｐ，ｌ：リンクlが、現用パスが通過する隣接リンクペアlpに対する予備パスの経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ：リンクlが、現用パスが通過する各隣接リンクペアに対する予備パス群の経路に含まれる時１、含まれない時０となるバイナリー変数
【００４０】
上記式(6)は、現用パスが通過する各隣接リンクペアに対する予備パスの経路について、リンクl′以外の出リンクを使用して、隣接リンクペアを構成する上流側リンクの始点ノードsｌｐから予備パスが必ず１本出て行き、また、始点ノードsｌｐにその予備パスが入ることはないこと(上段の式)、リンクl′′以外の入リンクを使用して、隣接リンクペアを構成する下流側リンクの終点ノードdｌｐにはその予備パスが必ず１本入り、また、終点ノードdｌｐからその予備パスが出ることはないこと(中段の式)、始点ノードsｌｐと終点ノードdｌｐ以外のノードでは、その予備パスが入っていなければ、その予備パスが出ることはなく、その予備パスが入っていれば、その予備パスが出て行き、また、その予備パスの出入りは、１本だけであること(下段の式)を制約している。
【００４１】
上記式(7)は、あるリンクに関して、現用パスが通過する各隣接リンクペアに対する予備パス群の経路の少なくとも１つに含まれれば、該リンクのリソースが予備パスによって使用されること、また、使用される該リンクのリソース量は、含まれる予備パスの経路数には依存しないことを制約している。
【００４２】
この場合、現用パスの経路コストは固定であるので、整数計画法において最小とすべき目的関数は、下記式(8)で与えることができる。式(8)は、現用パスが通過する各隣接リンクペアに対する予備パス群の経路を構成するリンクの距離の総和Sum Distanceを求めるものである。
【００４３】
【数８】
【００４４】
上記(6)、(7)の制約式を条件とし、上記式(8)を目的関数とする整数計画法を解くことによってbｌｐ，ｌの値(1か0のバイナリ変数)を求める。これによって計算されたbｌｐ，ｌの値(=1)は、現用パスが通過する各隣接リンクペアに対する予備パス群の新たな経路を示す。
【００４５】
次に、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを求める(S26)。なお、経路コストは、上記式(8)に現用パスの経路コストを加算することにより求めることができる。
【００４６】
次に、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・・・中継ノード
【技術分野】
【０００１】
本発明は、ポイントツーマルチポイントパス経路計算装置およびプログラムに関し、特に、単一ノード障害からの復旧を高速化するための、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方式では、発ノードと複数の着ノード間を接続する現用ポイントツーマルチポイントパスの単一ノード障害からの復旧を高速化するために、ネットワーク内において各隣接リンクペアに対する予備パス群を設定する。すなわち、ネットワーク内において各ノードを介して隣接し、現用パスが通過する各リンクペア(隣接リンクペア)に対して、該隣接リンクペアの上流側リンクの始点を発ノード、下流側リンクの終点を着ノードとして、該ノードを迂回する予備パスを設定する。
【００１６】
図１において、ノードCを迂回する予備パスとしては、隣接リンクペアB-C,C-Dと隣接リンクペアB-C,C-Gに対する予備パスを設定する必要がある。隣接リンクペアB-C,C-Dに対する予備パスの経路は、例えばB-E-Dであり、隣接リンクペアB-C,C-Gに対する予備パスの経路は、B-E-D-H-Gである。これらの予備パスの経路をそれぞれ破線で示している。ここでは単一のノード障害を想定しているので、リンクB-EとリンクE-Dのリソースを共用することができる。
【００１７】
本発明は、Fast Reroute方式を適用して単一ノード障害を復旧することを想定し、現用ポイントツーマルチポイントパスの経路コストに加え、単一ノード障害に対応してFast Reroute方式によって現用パスが通過する各隣接リンクペアに対して設定される予備パス群の経路コストも考慮して、最小経路コストとなる現用パスおよび予備パス群を求めるものである。以下、実施形態を詳細に説明する。
【００１８】
図２は、本発明の一実施形態におけるパス経路の計算処理を示すフローチャートである。なお、本発明は、以下に説明する各処理を実行する手段を備えたパス経路計算装置として実現できるが、コンピュータを、各処理を実行する手段として機能させるプログラムとしても実現できる。
【００１９】
まず、ネットワーク内の各隣接リンクペアに対する予備パスの経路を予め求める(S21)。ここで求める予備パスは各隣接リンクペアに対して任意のものとすることができるが、効率的に最適経路を求めるという面からは、各隣接リンクペアを迂回する最小コスト経路の形で予め求めるのが好ましい。最小コスト経路は、経路を構成するリンクのコスト累積値が最小となるようにして求めることができる。
【００２０】
次に、S21で求められた予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求め(S22)、求められた現用ポイントツーマルチポイントパスの経路を保存する。なお、ここで求められた経路を保存するのは、現用ポイントツーマルチポイントパスの経路が初めて求められたからであり、後述するように、それ以前に求められた現用ポイントツーマルチポイントパスの経路が存在する場合にはその経路を今回求められた経路に更新する。
【００２１】
S22で現用ポイントツーマルチポイントパスの経路を求める整数計画法における制約式は次の通りである。
(発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式)
【００２２】
【数１】
(現用ポイントツーマルチポイントパスの経路に関する制約式)
【００２３】
【数２】
(隣接リンクペアの通過に関する制約式)
【００２４】
【数３】
(予備パス間でのリソース共用に関する制約式)
【００２５】
【数４】
【００２６】
ここで、各シンボルの意味は次の通りである。
n：ネットワークを構成するノード
N：ネットワークを構成するノードnの集合
l：ネットワークを構成するリンク
Link：ネットワークを構成するリンクlの集合
lp：隣接リンクペア
LP：隣接リンクペアlpの集合
l′：隣接リンクペアlpを構成する上流側リンク
l′′：隣接リンクペアlpを構成する下流側リンク
s：発ノード
d：１つの着ノード
D：着ノードdの集合
sｉｎ：発ノードsへの入リンクの集合
sｏｕｔ：発ノードsからの出リンクの集合
dｉｎ：着ノードdへの入リンクの集合
dｏｕｔ：着ノードdからの出リンクの集合
nｉｎ：ノードnへの入リンクの集合
nｏｕｔ：ノードnからの出リンクの集合
Wｌ′：リンクl′が現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ′′：リンクl′′が現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
BLPｌｐ：隣接リンクペアlpに対する予備パスの経路を構成するリンクの集合
wｄ，ｌ：リンクlが着ノードdへの現用ポイントツーポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ：リンクlが現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌｐ：隣接リンクペアlpが現用ポイントツーマルチポイントパスの経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ：リンクlが、現用パスが通過する隣接リンクペアlpに対応する予備パス群の経路に含まれる時１、含まれない時０となるバイナリー変数
【００２７】
上記式(1)は、発ノードsと各着ノードd間の現用ポイントツーポイントパスの経路について、発ノードsからその現用ポイントツーポイントパスが必ず１本出て行き、また、発ノードsにその現用ポイントツーポイントパスが入ることはないこと(上段の式)、着ノードdにはその現用ポイントツーポイントパスが必ず１本入り、また、着ノードdからその現用ポイントツーポイントパスが出ることはないこと(中段の式)、発ノードsと着ノードd以外のノードn(中継ノード)では、その現用ポイントツーポイントパスが入っていなければ、その現用ポイントツーポイントパスが出ることはなく、その現用ポイントツーポイントパスが入っていれば、その現用ポイントツーポイントパスが出て行き、また、その現用ポイントツーポイントパスの出入りは、１本だけであること(下段の式)を制約している。
【００２８】
上記式(2)は、あるリンクに関して、着ノードdへの現用ポイントツーポイントパスの経路に含まれれば、該リンクのリソースは現用ポイントツーマルチポイントパスによって使用されること、すなわち、各着ノードへの現用ポイントツーポイントパスを合成したものが現用ポイントツーマルチポイントパスであること制約している。
【００２９】
上記式(3)は、現用パスが隣接リンクペアを通過するとは、現用パスが隣接リンクペアを構成する上流側および下流側の２つのリンクの両方を通過することであることを制約している。
【００３０】
上記式(4)は、あるリンクに関して、現用パスが通過する各隣接リンクペアに対する予備パス群の経路の少なくとも１つに含まれれば、該リンクのリソースが予備パスによって使用されること、また、予備パスによって使用されるリンクのリソース量は、含まれる予備パスの経路数には依存しないことを制約している。
【００３１】
整数計画法において最小とすべき目的関数は、下記式(5)で与えられる。ここで、distｌはリンクlのコストである。式(5)は、現用ポイントツーマルチポイントパスの経路を構成するリンクと現用パスが通過する各隣接リンクペアに対する予備パス群の経路を構成するリンクの距離の総和Sum Distanceを求めるものである。なお、リンクコストがリンクの距離に対応するものとしている。
【００３２】
【数５】
【００３３】
上記(1)〜(4)の制約式を条件とし、上記式(5)を目的関数とする整数計画法を解くことによってWｌの値(1か0のバイナリ変数)を求める。これによって求められたWｌの値(=1)は現用ポイントツーマルチポイントパスの経路を示す。
【００３４】
次に、現用パスと現用パスが通過する各隣接リンクペアに対応する予備パス群全体の経路コストを求める(S23)。なお、経路コストは上記式(5)で求めることができる。
【００３５】
次に、S23で求められた経路コストの改善度が予め設定した閾値よりも小さいか否かを判定する(S24)。経路コストの改善度とは、それ以前に求められた経路コストから改善(低下)した度合を意味する。当初では以前に求められた経路コストが存在しないのでS25に進む。
【００３６】
S25では、S22で求められた現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて、現用パスが通過する各隣接リンクペアに対して、コストを最小化する予備パスの経路を求める。そして、現用パスが通過する各隣接リンクペアに対する予備パスの経路を、ここで求めた予備パスの経路に更新する。S25で新たに予備パスの経路を求める整数計画法における制約式は次の通りである。
(現用パスが通過する各隣接リンクペアに対する予備パスの経路に関する制約式)
【００３７】
【数６】
(予備パス間でのリソース共用に関する制約式)
【００３８】
【数７】
【００３９】
ここで、新たに出てきた各シンボルの意味は次の通りである。それ以外の各シンボルの意味は上記と同じである。
sｌｐ：隣接リンクペアlpを構成する上流側リンクl′の始点ノード
dｌｐ：隣接リンクペアlpを構成する下流側リンクl′′の終点ノード
sｌｐ ｏｕｔ：始点ノードsｌｐからの出リンクの集合
sｌｐ ｉｎ：始点ノードsｌｐへの入リンクの集合
dｌｐ ｏｕｔ：終点ノードdｌｐからの出リンクの集合
dｌｐ ｉｎ：終点ノードdｌｐへの入リンクの集合
WLP：現用ポイントツーマルチポイントパスの経路を構成する隣接リンクペアlpの集合
bｌｐ，ｌ：リンクlが、現用パスが通過する隣接リンクペアlpに対する予備パスの経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ：リンクlが、現用パスが通過する各隣接リンクペアに対する予備パス群の経路に含まれる時１、含まれない時０となるバイナリー変数
【００４０】
上記式(6)は、現用パスが通過する各隣接リンクペアに対する予備パスの経路について、リンクl′以外の出リンクを使用して、隣接リンクペアを構成する上流側リンクの始点ノードsｌｐから予備パスが必ず１本出て行き、また、始点ノードsｌｐにその予備パスが入ることはないこと(上段の式)、リンクl′′以外の入リンクを使用して、隣接リンクペアを構成する下流側リンクの終点ノードdｌｐにはその予備パスが必ず１本入り、また、終点ノードdｌｐからその予備パスが出ることはないこと(中段の式)、始点ノードsｌｐと終点ノードdｌｐ以外のノードでは、その予備パスが入っていなければ、その予備パスが出ることはなく、その予備パスが入っていれば、その予備パスが出て行き、また、その予備パスの出入りは、１本だけであること(下段の式)を制約している。
【００４１】
上記式(7)は、あるリンクに関して、現用パスが通過する各隣接リンクペアに対する予備パス群の経路の少なくとも１つに含まれれば、該リンクのリソースが予備パスによって使用されること、また、使用される該リンクのリソース量は、含まれる予備パスの経路数には依存しないことを制約している。
【００４２】
この場合、現用パスの経路コストは固定であるので、整数計画法において最小とすべき目的関数は、下記式(8)で与えることができる。式(8)は、現用パスが通過する各隣接リンクペアに対する予備パス群の経路を構成するリンクの距離の総和Sum Distanceを求めるものである。
【００４３】
【数８】
【００４４】
上記(6)、(7)の制約式を条件とし、上記式(8)を目的関数とする整数計画法を解くことによってbｌｐ，ｌの値(1か0のバイナリ変数)を求める。これによって計算されたbｌｐ，ｌの値(=1)は、現用パスが通過する各隣接リンクペアに対する予備パス群の新たな経路を示す。
【００４５】
次に、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを求める(S26)。なお、経路コストは、上記式(8)に現用パスの経路コストを加算することにより求めることができる。
【００４６】
次に、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・・・中継ノード
【特許請求の範囲】
【請求項１】
Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間の現用パスの経路および該現用パスが通過する各隣接リンクペアに対する予備パス群を求めるポイントツーマルチポイントパス経路計算装置であって、
ネットワーク内の各隣接リンクペアに対する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段と、
現用ポイントツーマルチポイントパスの経路を前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段と、
前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスおよび現用パスが通過する各隣接リンクペアに対する予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段を備え、
前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路を直前に求められたものに更新しつつ交互に繰り返し実行し、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力することを特徴とするポイントツーマルチポイントパス経路計算装置。
【請求項２】
さらにネットワーク内の各隣接リンクペアに対する予備パスの経路を最小コスト経路の形で予め求める予備パス計算手段を備え、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パスの経路を当初に予備パスの経路として固定することを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算装置。
【請求項３】
前記現用パス経路計算手段は、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式、隣接リンクペアの通過に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求めることを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算装置。
【請求項４】
前記予備パス経路計算手段は、現用パスが通過する各隣接リンクペアに対する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求めることを特徴とする請求項１または２に記載のポイントツーマルチポイントパス経路計算装置。
【請求項５】
Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間で現用パスの経路および該現用パスが通過する各隣接リンクペアに対する予備パス群を求めるために、コンピュータを、
ネットワーク内の各隣接リンクペアに対する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段、前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段、前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段として機能させ、
前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路を直前に求められたものに更新しつつ、交互に繰り返し実行させ、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力させるためのプログラム。
【請求項６】
さらにコンピュータを、ネットワーク内の各隣接リンクペアに対する予備パス群の経路を最小コスト経路の形で予め求める予備パス計算手段として機能させ、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パス群の経路を当初に予備パス群の経路として固定する請求項５に記載のプログラム。
【請求項７】
前記現用パス経路計算手段は、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式、隣接リンクペアの通過に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求める請求項５または６に記載のプログラム。
【請求項８】
前記予備パス経路計算手段は、現用パスが通過する各隣接リンクペアに対する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求める請求項５ないし７のいずれかに記載のプログラム。
【請求項１】
Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間の現用パスの経路および該現用パスが通過する各隣接リンクペアに対する予備パス群を求めるポイントツーマルチポイントパス経路計算装置であって、
ネットワーク内の各隣接リンクペアに対する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段と、
現用ポイントツーマルチポイントパスの経路を前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段と、
前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスおよび現用パスが通過する各隣接リンクペアに対する予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段を備え、
前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路を直前に求められたものに更新しつつ交互に繰り返し実行し、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力することを特徴とするポイントツーマルチポイントパス経路計算装置。
【請求項２】
さらにネットワーク内の各隣接リンクペアに対する予備パスの経路を最小コスト経路の形で予め求める予備パス計算手段を備え、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パスの経路を当初に予備パスの経路として固定することを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算装置。
【請求項３】
前記現用パス経路計算手段は、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式、隣接リンクペアの通過に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求めることを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算装置。
【請求項４】
前記予備パス経路計算手段は、現用パスが通過する各隣接リンクペアに対する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求めることを特徴とする請求項１または２に記載のポイントツーマルチポイントパス経路計算装置。
【請求項５】
Fast Reroute方式を適用してネットワークにおける発ノードと複数の着ノード間で現用パスの経路および該現用パスが通過する各隣接リンクペアに対する予備パス群を求めるために、コンピュータを、
ネットワーク内の各隣接リンクペアに対する予備パスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する現用ポイントツーマルチポイントパスの経路を求める現用パス経路計算手段、前記現用パス経路計算手段で求められた現用ポイントツーマルチポイントパスの経路に現用ポイントツーマルチポイントパスの経路を固定し、整数計画法を用いて、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の経路コストを最小化する予備パス群の経路を求める予備パス経路計算手段、前記現用パス経路計算手段および前記予備パス経路計算手段がそれぞれ現用ポイントツーマルチポイントパスの経路および予備パス群を求める際に、現用パスと現用パスが通過する各隣接リンクペアに対する予備パス群全体の最小化経路コストを求める最小化経路コスト計算手段として機能させ、
前記現用パス経路計算手段と前記予備パス経路計算手段での経路計算処理を、固定する予備パスの経路および現用ポイントツーマルチポイントパスの経路を直前に求められたものに更新しつつ、交互に繰り返し実行させ、前記最小化経路コスト計算手段で順次に求められる最小化経路コスト間での改善度が所定値未満になったときの現用ポイントツーマルチポイントパスおよび予備パス群の経路を出力させるためのプログラム。
【請求項６】
さらにコンピュータを、ネットワーク内の各隣接リンクペアに対する予備パス群の経路を最小コスト経路の形で予め求める予備パス計算手段として機能させ、前記現用パス経路計算手段は、前記予備パス計算手段で求められた予備パス群の経路を当初に予備パス群の経路として固定する請求項５に記載のプログラム。
【請求項７】
前記現用パス経路計算手段は、発ノードと各着ノード間の現用ポイントツーポイントパスの経路に関する制約式、現用ポイントツーマルチポイントパスの経路に関する制約式、隣接リンクペアの通過に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用ポイントツーマルチポイントパスを構成するリンクと現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする現用ポイントツーマルチポイントパスの経路を求める請求項５または６に記載のプログラム。
【請求項８】
前記予備パス経路計算手段は、現用パスが通過する各隣接リンクペアに対する予備パスの経路に関する制約式および予備パス間でのリソース共用に関する制約式を含み、現用パスが通過する各隣接リンクペアに対する予備パス群を構成するリンクの距離の総和を目的関数とする整数計画法を解くことにより、前記距離の総和を最小とする予備パス群の経路を求める請求項５ないし７のいずれかに記載のプログラム。
【図１】
【図２】
【図２】
【公開番号】特開２００８−１８２４２４（Ｐ２００８−１８２４２４Ａ）
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願番号】特願２００７−１３７２０（Ｐ２００７−１３７２０）
【出願日】平成１９年１月２４日（２００７．１．２４）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願日】平成１９年１月２４日（２００７．１．２４）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]