ポイントツーマルチポイントパス経路計算方法
【課題】最短かつ高信頼のポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができるようにすること。
【解決手段】発ノードAと複数の着ノードB,C,E,H,J間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を計算で求める。この計算に際しては、発ノードAと各着ノードB,C,E,H,Jを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含める。この整数計画法を解くことによって現用および予備ポイントツーマルチポイントパス用経路を求める。
【解決手段】発ノードAと複数の着ノードB,C,E,H,J間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を計算で求める。この計算に際しては、発ノードAと各着ノードB,C,E,H,Jを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含める。この整数計画法を解くことによって現用および予備ポイントツーマルチポイントパス用経路を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポイントツーマルチポイントパス経路計算方法に関し、特に、発ノードと複数の着ノード間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を求めるポイントツーマルチポイントパス経路計算方法に関する。
【背景技術】
【０００２】
発ノードと複数の着ノード間を接続するポイントツーマルチポイントパスを計算により求めるに際し、パスの障害復旧を高速化するために、発ノードと各着ノード間で1＋1プロテクションを考慮する場合が存在する。
【０００３】
現用および予備ポイントツーマルチポイントパス用経路は、発ノードと各着ノードを接続する現用ポイントツーポイントパス用と予備ポイントツーポイントパス用の障害独立な２本の最短経路を個別に計算し、全ての着ノードについて求められた現用ポイントツーポイントパス用経路および予備ポイントツーポイントパス用経路を合成することにより求めることができる。
【０００４】
特許文献１には、各ノードペア(発ノードと着ノード)について、距離の総和が最小なり、互いにノードを共有しないルートを求めるために整数計画法を２回実行する光ネットワークの設計法が記載されている。
【特許文献１】特開２００２−３７４２８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来の方法は、発ノードと各着ノードを接続する現用ポイントツーポイントパス用と予備ポイントツーポイントパス用の最短経路を個別に計算するものであるので、発ノードと各着ノート間の個々のパスについては最短経路を求めることができるものの、それらを合成したときに全体として最短のポイントツーマルチポイントパス用経路が求まるとは限らない。また、特許文献１の光ネットワークの設計法では、整数計画法を２回適用し、それを解く必要がある。
【０００６】
本発明の目的は、上記課題を解決し、最短かつ高信頼のポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができるポイントツーマルチポイントパス経路計算方法を提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明は、発ノードと複数の着ノード間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を求めるポイントツーマルチポイントパス経路計算方法であって、発ノードと各着ノードを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含め、該整数計画法を解くことによって現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴としている。
【０００８】
また、本発明は、前記制約式を含み、現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路の距離の総和を目的関数とする整数計画法を解き、前記距離の総和を最小とする現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴としている。
【０００９】
さらに、本発明は、ネットワークに含まれる非パス分岐ノードを考慮して現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を定め、さらに非パス分岐ノードに関する制約式を整数計画法の中に含めることを特徴としている。
【発明の効果】
【００１０】
本発明によれば、全体として最短かつ高信頼のポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができる。また、ネットワーク中に、パスを分岐することができないノード(非パス分岐ノード)が含まれている場合でも、非パス分岐ノードを考慮して現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を定め、さらに非パス分岐ノードに関する制約式を整数計画法の中に含めることにより、１回の整数計画法を解くだけでポイントツーマルチポイントパス用経路を求めることができる。
【発明を実施するための最良の形態】
【００１１】
以下、図を参照して本発明を説明する。図１は、本発明が適用されるネットワークの例を示す概念図である。図１は、発ノードをA、着ノードをB,C,E,H,Jとするポイントツーマルチポイントパスが設定された例であり、発ノードを白丸で示し、着ノードを黒丸で示している。なお、D,F,G,Iは中継ノードである。
【００１２】
発ノードAと各着ノードB,C,E,H,J間において、図示実線の現用ポイントツーマルチポイントパス用経路と図示破線の予備ポイントツーマルチポイントパス用経路が存在し、これにより1＋1プロテクションが実現されている。なお、各ノードでは必要に応じてパスを複数のリンクへ分岐させることが可能である。
【００１３】
このように、発ノードと各着ノード間で1＋1プロテクションを行うことにより、各着ノードに対して現用ポイントツーマルチポイントパス経路と予備ポイントツーマルチポイントパス経路は互いに障害独立なルートとなっているので、各着ノードB,C,E,H,Jでは、発ノードAとの間の中継ノードあるいは各ノード間のリンクのいずれか１つに障害が発生しても、現用あるいは予備ポイントツーマルチポイントパス経路を選択して正常な通信を行うことができる。また、各着ノードでは、現用および予備ポイントツーマルチポイントパス経路のうちのいずれか障害のない方を適宜選択するだけでよいので、パスの障害復旧を高速化することができる。
【００１４】
本発明は、発ノードと各着ノード間で1＋1プロテクションを行う場合を想定して、現用および予備ポイントツーマルチポイントパス経路を求めるものであり、以下、実施形態について詳細に説明する。
【００１５】
ネットワークのトポロジー(N,Link)とリンクlの距離distｌが与えられたとき、整数計画法を用いて、発ノードと各着ノード間で互いに障害独立な現用および予備ポイントツーマルチポイントパス用の最短経路を求める。
【００１６】
このとき、発ノードと各着ノードを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関してそれぞれ合成し、それによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含めることにより、現用および予備ポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができるようにする。
【００１７】
発ノードと各着ノード間の単一の中継ノードあるいはリンクの障害を想定したとき、ポイントツーマルチポイントパス用経路を求める整数計画法における制約式は、下記式(1)〜(4)で表される。
（発ノードと各着ノード間の現用ポイントツーポイントパス用経路に関する制約式）
【００１８】
【数１】
【００１９】
（発ノードと各着ノード間の予備ポイントツーポイントパス用経路に関する制約式）
【００２０】
【数２】
【００２１】
（発ノードと各着ノード間の現用ポイントツーポイントパスと予備ポイントツーポイントパスの障害独立性に関する制約式）
【００２２】
【数３】
【００２３】
（現用および予備ポイントツーマルチポイントパス用経路に関する制約式）
【００２４】
【数４】
【００２５】
ここで、各シンボルの意味は次の通りである。
N：ネットワークを構成するノードの集合
n：ネットワークを構成するノード
Link：ネットワークを構成するリンクの集合
l：ネットワークを構成するリンク
s：発ノード
D:着ノードの集合
d：１つの着ノード
sｏｕｔ：発ノードsの出側リンクの集合
sｉｎ：発ノードsの入側リンクの集合
dｏｕｔ：着ノードdの出側リンクの集合
dｉｎ：着ノードdの入側リンクの集合
nｏｕｔ：ノードnの出側リンクの集合
nｉｎ：ノードnの入側リンクの集合
wｄ，ｌ：リンクlが着ノードdへの現用ポイントツーポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
bｄ，ｌ：リンクlが着ノードdへの予備ポイントツーポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ：リンクlが現用ポイントツーマルチポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ：リンクlが予備ポイントツーマルチポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
【００２６】
上記式(1)は、発ノードsと各着ノードd間の現用ポイントツーポイントパス用経路について、発ノードsからその現用ポイントツーポイントパスが必ず１本出て行き、また、発ノードsにその現用ポイントツーポイントパスが入ることはないこと(上段の式)、着ノードdにはその現用ポイントツーポイントパスが必ず１本入り、また、着ノードdからその現用ポイントツーポイントパスが出ることはないこと(中段の式)、発ノードsと着ノードd以外ノードn(中継ノード)では、その現用ポイントツーポイントパスが入っていなければ、その現用ポイントツーポイントパスが出ることはなく、その現用ポイントツーポイントパスが入っていれば、その現用ポイントツーポイントパスが出て行き、また、その現用ポイントツーポイントパスの出入りは、１本だけであること(下段の式)を制約している。
【００２７】
上記式(2)は、発ノードsと各着ノードd間の予備ポイントツーポイントパス用経路について、同様のことを制約している。
【００２８】
上記式(3)は、発ノードsと各着ノードd間の現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路について、各中継ノードnにはその現用および予備ポイントツーポイントパスの両者が通らないこと(上段の式)、また、各リンクはその現用および予備ポイントツーポイントパスで共用されないこと(下段の式)、つまり、その現用および予備ポイントツーポイントパスが同時に障害にならないこと(障害独立性)を制約している。なお、ここでは、中継ノードあるいはリンクの単一の障害を想定している。
【００２９】
上記式(4)は、発ノードsと各着ノードdを接続する互いに障害独立な現用ポイントツーポイントパスと予備ポイントツーポイントパスを全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路について、リンクlが発ノードsと各着ノードd間の現用ポイントツーポイントパスに使用されるものであれば、そのリンクは現用ポイントツーマルチポイントパスに使用されるものであること(上段の式)、また、リンクlが発ノードsと各着ノードd間の予備ポイントツーポイントパスに使用されるものであれば、そのリンクは予備ポイントツーマルチポイントパスとして使用されるものであること(下段の式)を制約している。
【００３０】
整数計画法において最小とすべき目的関数は、下記式(5)で与えられる。式(5)は、現用ポイントツーマルチポイントパス用経路に含まれるリンクと予備ポイントツーマルチポイントパス用経路に含まれるリンクの距離の総和Sum Distance、すなわち、現用および予備ポイントツーマルチポイントパス用経路の距離の総和を求めるものである。
【００３１】
【数５】
【００３２】
上記(1)〜(4)の制約式を条件とし、上記式(5)を目的関数とする整数計画法を解くことによってWｌおよびBｌの値(1か0のバイナリ変数)を求める。これによって求められたWｌの値は現用ポイントツーマルチポイントパスの経路を示し、Bｌの値は予備ポイントツーマルチポイントパスの経路を示す。
【００３３】
図１の例では、現用ポイントツーマルチポイントパス経路に含まれるA-BやC-G、B-CやC-Dなどの実線で示すリンクについてはWｌ＝1となり、予備ポイントツーマルチポイントパス経路に含まれるA-FやD-J、C-BやD-Cなどの破線で示すリンクについてはBｌ＝1となる。
【００３４】
以上のように、本発明では、発ノードと各着ノード間のポイントツーポイントパスの経路についての制約式(上記(1)〜(3))に、ポイントツーマルチポイントパスの経路についての制約式(上記式(4))を加えることにより、最短かつ高信頼性のポイントツーマルチポイントパス経路を１回の整数計画法で求めることを可能にしている。
【００３５】
以上実施形態を説明したが、本発明は、上記実施形態に限定されるものではない。例えば、上記実施形態では、ネットワークの各ノードが必要に応じてパスを複数のリンクへ分岐させることができるものであることを想定したが、本発明は、下記(6)〜(8)の制約式を追加することにより、図２に示すような、パスを分岐させることができないノード(非パス分岐ノード)を含むネットワークに対しても適用できる。ただし、非パス分岐ノードは、発ノードにはならないとする。
【００３６】
図２は、発ノードをA、着ノードをB,C,E,H,Jとするポイントツーマルチポイントパスが設定された例を示しており、発ノードを白丸で示し、着ノードを黒丸で示している。D,F,G,Iは中継ノードである。ここで、ノードD,Hは非パス分岐ノードである。
【００３７】
本例では、発ノードAと各着ノードB,C,E,H,J間において、図示実線の現用ポイントツーマルチポイントパス用経路と図示破線の予備ポイントツーマルチポイントパス用経路が存在する。ノードDは非パス分岐ノードであるので、ノードE-D間にはノードC方向とノードJ方向の計2本の予備パスを設定する必要がある。
【００３８】
また、ノードHも非パス分岐ノードであり、自分が受信するか、次のノードにそのまま中継する機能しか持っていないので、ノードG-H間には、ノードHの受信用とノードIへ中継される計2本の現用パスを設定する必要がある。
（現用および予備ポイントツーマルチポイントパス用経路に関する制約式）
【００３９】
【数６】
【００４０】
（非パス分岐ノードを考慮した現用および予備ポイントツーマルチポイントパス用経路に関する制約式）
【００４１】
【数７】
【００４２】
（非パス分岐ノードに関する制約式）
【００４３】
【数８】
【００４４】
ここで新たに出てきたシンボルの意味は次の通りである。
K：非パス分岐ノードの集合
k：非パス分岐ノード
W′ｌ：リンクlが含まれる現用ポイントツーマルチポイントパス用経路数を表す整数変数
B′ｌ：リンクlが含まれる予備ポイントツーマルチポイントパス用経路数を表す整数変数
【００４５】
整数計画法において最小とすべき目的関数は、下記式(9)で与えられる。
【００４６】
【数９】
【００４７】
上記(1)〜(4)の制約式に加えて上記(6)〜(8)の制約式を条件とし、上記式(9)を目的関数とする整数計画法を解くことによってW′ｌおよびB′ｌの値を求める。これによって求められたW′ｌの値は現用ポイントツーマルチポイントパスの経路を示し、B′ｌの値は予備ポイントツーマルチポイントパスの経路を示す。
【００４８】
本発明によれば、ポイントツーマルチポイント通信サービスを高信頼かつリソースの利用効率よく実現することができ、これによって、複数拠点への映像配信サービスなどを高信頼かつ低コストで提供することができるようになる。
【図面の簡単な説明】
【００４９】
【図１】本発明が適用されるネットワークの例を示す概念図である。
【図２】本発明が適用されるネットワークの他の例を示す概念図である。
【符号の説明】
【００５０】
A・・・発ノード、B,C,E,H,J・・・着ノード、D,F,G,I・・・中継ノード
【技術分野】
【０００１】
本発明は、ポイントツーマルチポイントパス経路計算方法に関し、特に、発ノードと複数の着ノード間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を求めるポイントツーマルチポイントパス経路計算方法に関する。
【背景技術】
【０００２】
発ノードと複数の着ノード間を接続するポイントツーマルチポイントパスを計算により求めるに際し、パスの障害復旧を高速化するために、発ノードと各着ノード間で1＋1プロテクションを考慮する場合が存在する。
【０００３】
現用および予備ポイントツーマルチポイントパス用経路は、発ノードと各着ノードを接続する現用ポイントツーポイントパス用と予備ポイントツーポイントパス用の障害独立な２本の最短経路を個別に計算し、全ての着ノードについて求められた現用ポイントツーポイントパス用経路および予備ポイントツーポイントパス用経路を合成することにより求めることができる。
【０００４】
特許文献１には、各ノードペア(発ノードと着ノード)について、距離の総和が最小なり、互いにノードを共有しないルートを求めるために整数計画法を２回実行する光ネットワークの設計法が記載されている。
【特許文献１】特開２００２−３７４２８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来の方法は、発ノードと各着ノードを接続する現用ポイントツーポイントパス用と予備ポイントツーポイントパス用の最短経路を個別に計算するものであるので、発ノードと各着ノート間の個々のパスについては最短経路を求めることができるものの、それらを合成したときに全体として最短のポイントツーマルチポイントパス用経路が求まるとは限らない。また、特許文献１の光ネットワークの設計法では、整数計画法を２回適用し、それを解く必要がある。
【０００６】
本発明の目的は、上記課題を解決し、最短かつ高信頼のポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができるポイントツーマルチポイントパス経路計算方法を提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明は、発ノードと複数の着ノード間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を求めるポイントツーマルチポイントパス経路計算方法であって、発ノードと各着ノードを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含め、該整数計画法を解くことによって現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴としている。
【０００８】
また、本発明は、前記制約式を含み、現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路の距離の総和を目的関数とする整数計画法を解き、前記距離の総和を最小とする現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴としている。
【０００９】
さらに、本発明は、ネットワークに含まれる非パス分岐ノードを考慮して現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を定め、さらに非パス分岐ノードに関する制約式を整数計画法の中に含めることを特徴としている。
【発明の効果】
【００１０】
本発明によれば、全体として最短かつ高信頼のポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができる。また、ネットワーク中に、パスを分岐することができないノード(非パス分岐ノード)が含まれている場合でも、非パス分岐ノードを考慮して現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を定め、さらに非パス分岐ノードに関する制約式を整数計画法の中に含めることにより、１回の整数計画法を解くだけでポイントツーマルチポイントパス用経路を求めることができる。
【発明を実施するための最良の形態】
【００１１】
以下、図を参照して本発明を説明する。図１は、本発明が適用されるネットワークの例を示す概念図である。図１は、発ノードをA、着ノードをB,C,E,H,Jとするポイントツーマルチポイントパスが設定された例であり、発ノードを白丸で示し、着ノードを黒丸で示している。なお、D,F,G,Iは中継ノードである。
【００１２】
発ノードAと各着ノードB,C,E,H,J間において、図示実線の現用ポイントツーマルチポイントパス用経路と図示破線の予備ポイントツーマルチポイントパス用経路が存在し、これにより1＋1プロテクションが実現されている。なお、各ノードでは必要に応じてパスを複数のリンクへ分岐させることが可能である。
【００１３】
このように、発ノードと各着ノード間で1＋1プロテクションを行うことにより、各着ノードに対して現用ポイントツーマルチポイントパス経路と予備ポイントツーマルチポイントパス経路は互いに障害独立なルートとなっているので、各着ノードB,C,E,H,Jでは、発ノードAとの間の中継ノードあるいは各ノード間のリンクのいずれか１つに障害が発生しても、現用あるいは予備ポイントツーマルチポイントパス経路を選択して正常な通信を行うことができる。また、各着ノードでは、現用および予備ポイントツーマルチポイントパス経路のうちのいずれか障害のない方を適宜選択するだけでよいので、パスの障害復旧を高速化することができる。
【００１４】
本発明は、発ノードと各着ノード間で1＋1プロテクションを行う場合を想定して、現用および予備ポイントツーマルチポイントパス経路を求めるものであり、以下、実施形態について詳細に説明する。
【００１５】
ネットワークのトポロジー(N,Link)とリンクlの距離distｌが与えられたとき、整数計画法を用いて、発ノードと各着ノード間で互いに障害独立な現用および予備ポイントツーマルチポイントパス用の最短経路を求める。
【００１６】
このとき、発ノードと各着ノードを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関してそれぞれ合成し、それによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含めることにより、現用および予備ポイントツーマルチポイントパス用経路を１回の整数計画法を解くだけで求めることができるようにする。
【００１７】
発ノードと各着ノード間の単一の中継ノードあるいはリンクの障害を想定したとき、ポイントツーマルチポイントパス用経路を求める整数計画法における制約式は、下記式(1)〜(4)で表される。
（発ノードと各着ノード間の現用ポイントツーポイントパス用経路に関する制約式）
【００１８】
【数１】
【００１９】
（発ノードと各着ノード間の予備ポイントツーポイントパス用経路に関する制約式）
【００２０】
【数２】
【００２１】
（発ノードと各着ノード間の現用ポイントツーポイントパスと予備ポイントツーポイントパスの障害独立性に関する制約式）
【００２２】
【数３】
【００２３】
（現用および予備ポイントツーマルチポイントパス用経路に関する制約式）
【００２４】
【数４】
【００２５】
ここで、各シンボルの意味は次の通りである。
N：ネットワークを構成するノードの集合
n：ネットワークを構成するノード
Link：ネットワークを構成するリンクの集合
l：ネットワークを構成するリンク
s：発ノード
D:着ノードの集合
d：１つの着ノード
sｏｕｔ：発ノードsの出側リンクの集合
sｉｎ：発ノードsの入側リンクの集合
dｏｕｔ：着ノードdの出側リンクの集合
dｉｎ：着ノードdの入側リンクの集合
nｏｕｔ：ノードnの出側リンクの集合
nｉｎ：ノードnの入側リンクの集合
wｄ，ｌ：リンクlが着ノードdへの現用ポイントツーポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
bｄ，ｌ：リンクlが着ノードdへの予備ポイントツーポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
Wｌ：リンクlが現用ポイントツーマルチポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
Bｌ：リンクlが予備ポイントツーマルチポイントパス用経路に含まれる時１、含まれない時０となるバイナリー変数
【００２６】
上記式(1)は、発ノードsと各着ノードd間の現用ポイントツーポイントパス用経路について、発ノードsからその現用ポイントツーポイントパスが必ず１本出て行き、また、発ノードsにその現用ポイントツーポイントパスが入ることはないこと(上段の式)、着ノードdにはその現用ポイントツーポイントパスが必ず１本入り、また、着ノードdからその現用ポイントツーポイントパスが出ることはないこと(中段の式)、発ノードsと着ノードd以外ノードn(中継ノード)では、その現用ポイントツーポイントパスが入っていなければ、その現用ポイントツーポイントパスが出ることはなく、その現用ポイントツーポイントパスが入っていれば、その現用ポイントツーポイントパスが出て行き、また、その現用ポイントツーポイントパスの出入りは、１本だけであること(下段の式)を制約している。
【００２７】
上記式(2)は、発ノードsと各着ノードd間の予備ポイントツーポイントパス用経路について、同様のことを制約している。
【００２８】
上記式(3)は、発ノードsと各着ノードd間の現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路について、各中継ノードnにはその現用および予備ポイントツーポイントパスの両者が通らないこと(上段の式)、また、各リンクはその現用および予備ポイントツーポイントパスで共用されないこと(下段の式)、つまり、その現用および予備ポイントツーポイントパスが同時に障害にならないこと(障害独立性)を制約している。なお、ここでは、中継ノードあるいはリンクの単一の障害を想定している。
【００２９】
上記式(4)は、発ノードsと各着ノードdを接続する互いに障害独立な現用ポイントツーポイントパスと予備ポイントツーポイントパスを全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路について、リンクlが発ノードsと各着ノードd間の現用ポイントツーポイントパスに使用されるものであれば、そのリンクは現用ポイントツーマルチポイントパスに使用されるものであること(上段の式)、また、リンクlが発ノードsと各着ノードd間の予備ポイントツーポイントパスに使用されるものであれば、そのリンクは予備ポイントツーマルチポイントパスとして使用されるものであること(下段の式)を制約している。
【００３０】
整数計画法において最小とすべき目的関数は、下記式(5)で与えられる。式(5)は、現用ポイントツーマルチポイントパス用経路に含まれるリンクと予備ポイントツーマルチポイントパス用経路に含まれるリンクの距離の総和Sum Distance、すなわち、現用および予備ポイントツーマルチポイントパス用経路の距離の総和を求めるものである。
【００３１】
【数５】
【００３２】
上記(1)〜(4)の制約式を条件とし、上記式(5)を目的関数とする整数計画法を解くことによってWｌおよびBｌの値(1か0のバイナリ変数)を求める。これによって求められたWｌの値は現用ポイントツーマルチポイントパスの経路を示し、Bｌの値は予備ポイントツーマルチポイントパスの経路を示す。
【００３３】
図１の例では、現用ポイントツーマルチポイントパス経路に含まれるA-BやC-G、B-CやC-Dなどの実線で示すリンクについてはWｌ＝1となり、予備ポイントツーマルチポイントパス経路に含まれるA-FやD-J、C-BやD-Cなどの破線で示すリンクについてはBｌ＝1となる。
【００３４】
以上のように、本発明では、発ノードと各着ノード間のポイントツーポイントパスの経路についての制約式(上記(1)〜(3))に、ポイントツーマルチポイントパスの経路についての制約式(上記式(4))を加えることにより、最短かつ高信頼性のポイントツーマルチポイントパス経路を１回の整数計画法で求めることを可能にしている。
【００３５】
以上実施形態を説明したが、本発明は、上記実施形態に限定されるものではない。例えば、上記実施形態では、ネットワークの各ノードが必要に応じてパスを複数のリンクへ分岐させることができるものであることを想定したが、本発明は、下記(6)〜(8)の制約式を追加することにより、図２に示すような、パスを分岐させることができないノード(非パス分岐ノード)を含むネットワークに対しても適用できる。ただし、非パス分岐ノードは、発ノードにはならないとする。
【００３６】
図２は、発ノードをA、着ノードをB,C,E,H,Jとするポイントツーマルチポイントパスが設定された例を示しており、発ノードを白丸で示し、着ノードを黒丸で示している。D,F,G,Iは中継ノードである。ここで、ノードD,Hは非パス分岐ノードである。
【００３７】
本例では、発ノードAと各着ノードB,C,E,H,J間において、図示実線の現用ポイントツーマルチポイントパス用経路と図示破線の予備ポイントツーマルチポイントパス用経路が存在する。ノードDは非パス分岐ノードであるので、ノードE-D間にはノードC方向とノードJ方向の計2本の予備パスを設定する必要がある。
【００３８】
また、ノードHも非パス分岐ノードであり、自分が受信するか、次のノードにそのまま中継する機能しか持っていないので、ノードG-H間には、ノードHの受信用とノードIへ中継される計2本の現用パスを設定する必要がある。
（現用および予備ポイントツーマルチポイントパス用経路に関する制約式）
【００３９】
【数６】
【００４０】
（非パス分岐ノードを考慮した現用および予備ポイントツーマルチポイントパス用経路に関する制約式）
【００４１】
【数７】
【００４２】
（非パス分岐ノードに関する制約式）
【００４３】
【数８】
【００４４】
ここで新たに出てきたシンボルの意味は次の通りである。
K：非パス分岐ノードの集合
k：非パス分岐ノード
W′ｌ：リンクlが含まれる現用ポイントツーマルチポイントパス用経路数を表す整数変数
B′ｌ：リンクlが含まれる予備ポイントツーマルチポイントパス用経路数を表す整数変数
【００４５】
整数計画法において最小とすべき目的関数は、下記式(9)で与えられる。
【００４６】
【数９】
【００４７】
上記(1)〜(4)の制約式に加えて上記(6)〜(8)の制約式を条件とし、上記式(9)を目的関数とする整数計画法を解くことによってW′ｌおよびB′ｌの値を求める。これによって求められたW′ｌの値は現用ポイントツーマルチポイントパスの経路を示し、B′ｌの値は予備ポイントツーマルチポイントパスの経路を示す。
【００４８】
本発明によれば、ポイントツーマルチポイント通信サービスを高信頼かつリソースの利用効率よく実現することができ、これによって、複数拠点への映像配信サービスなどを高信頼かつ低コストで提供することができるようになる。
【図面の簡単な説明】
【００４９】
【図１】本発明が適用されるネットワークの例を示す概念図である。
【図２】本発明が適用されるネットワークの他の例を示す概念図である。
【符号の説明】
【００５０】
A・・・発ノード、B,C,E,H,J・・・着ノード、D,F,G,I・・・中継ノード
【特許請求の範囲】
【請求項１】
ネットワークにおける発ノードと複数の着ノード間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を求めるポイントツーマルチポイントパス経路計算方法であって、
発ノードと各着ノードを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含め、該整数計画法を解くことによって現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴とするポイントツーマルチポイントパス経路計算方法。
【請求項２】
前記制約式を含み、現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路の距離の総和を目的関数とする整数計画法を解き、前記距離の総和を最小とする現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算方法。
【請求項３】
ネットワークに含まれる非パス分岐ノードを考慮して現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を定め、さらに非パス分岐ノードに関する制約式を整数計画法の中に含めることを特徴とする請求項１または２に記載のポイントツーマルチポイントパス経路計算方法。
【請求項１】
ネットワークにおける発ノードと複数の着ノード間で1＋1プロテクションを行う場合の現用および予備ポイントツーマルチポイントパス用経路を求めるポイントツーマルチポイントパス経路計算方法であって、
発ノードと各着ノードを接続する互いに障害独立な現用ポイントツーポイントパス用経路と予備ポイントツーポイントパス用経路を全ての着ノードに関して合成することによって得られる現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を１つの整数計画法の中に含め、該整数計画法を解くことによって現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴とするポイントツーマルチポイントパス経路計算方法。
【請求項２】
前記制約式を含み、現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路の距離の総和を目的関数とする整数計画法を解き、前記距離の総和を最小とする現用および予備ポイントツーマルチポイントパス用経路を求めることを特徴とする請求項１に記載のポイントツーマルチポイントパス経路計算方法。
【請求項３】
ネットワークに含まれる非パス分岐ノードを考慮して現用ポイントツーマルチポイントパス用経路と予備ポイントツーマルチポイントパス用経路に関する制約式を定め、さらに非パス分岐ノードに関する制約式を整数計画法の中に含めることを特徴とする請求項１または２に記載のポイントツーマルチポイントパス経路計算方法。
【図１】
【図２】
【図２】
【公開番号】特開２００７−２０８８９２（Ｐ２００７−２０８８９２Ａ）
【公開日】平成１９年８月１６日（２００７．８．１６）
【国際特許分類】
【出願番号】特願２００６−２８２５０（Ｐ２００６−２８２５０）
【出願日】平成１８年２月６日（２００６．２．６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成１９年８月１６日（２００７．８．１６）
【国際特許分類】
【出願日】平成１８年２月６日（２００６．２．６）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]