(57)【要約】【課題】ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させながら、予め決められた性能指標を最適化する品質クラスを自ドメイン内パスに割り当てることを可能にすること。【解決手段】自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し(S38)、また、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算する(S41)。これにより計算されたドメイン間パス設定要求の到着率および成功率に基づいて、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策(各品質クラスに割り当てる確率)を決定する(S34〜S36)。【選択図】図３
2008205939.tif 000002
【特許請求の範囲】
【請求項１】
エンド・ツー・エンドの所要品質値が与えられ、自ドメインを含む複数のドメインを経由するドメイン間パスの設定要求に応答して、ドメイン間パスを構成する自ドメイン内パスに品質クラスを割り当てるための品質クラス割当方策決定装置において、
自ドメインへのドメイン間パス設定要求の到着を観測し、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算する第１の手段と、
下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測し、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算する第２の手段と、
前記第１および第２の手段により計算されたドメイン間パス設定要求の到着率および成功率に基づいて、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定する第３の手段を備えたことを特徴とする品質クラス割当方策決定装置。
【請求項２】
前記第１の手段は、通過する隣接下流ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し、
前記第２の手段は、通過する隣接下流ドメインが同じパスごとに、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算し、
前記第３の手段は、隣接下流ドメインごとに、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定することを特徴とする請求項１に記載の品質クラス割当方策決定装置。
【請求項３】
前記第１の手段は、着ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し、
前記第２の手段は、着ドメインが同じパスごとに、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算し、
前記第３の手段は、着ドメインごとに、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定することを特徴とする請求項１に記載の品質クラス割当方策決定装置。
【請求項４】
エンド・ツー・エンドの所要品質値が与えられ、自ドメインを含む複数のドメインを経由するドメイン間パスの設定要求に応答して、ドメイン間パスを構成する自ドメイン内パスに割り当てる品質クラスを決定するため、コンピュータを、
自ドメインへのドメイン間パス設定要求の到着を観測し、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算する第１の手段、
下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測し、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算する第２の手段、
前記第１および第２の手段により計算されたドメイン間パス設定要求の到着率および成功率に基づいて、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定する第３の手段として機能させるためのプログラム。
【請求項５】
前記第１の手段は、通過する隣接下流ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し、
前記第２の手段は、通過する隣接下流ドメインが同じパスごとに、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を観測し、
前記第３の手段は、隣接下流ドメインごとに、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定することを特徴とする請求項４に記載のプログラム。
【請求項６】
前記第１の手段は、着ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し、
前記第２の手段は、着ドメインが同じパスごとに、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を観測し、
前記第３の手段は、着ドメインごとに、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定することを特徴とする請求項４に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、品質クラス割当方策決定装置およびプログラムに関し、特に、ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させながら、自ドメインでの割当可能品質クラスの内から予め決められた性能指標を最適化する品質クラスを自ドメイン内パスに割り当てるために適用される品質クラス割当方策決定装置およびプログラムに関する。
【背景技術】
【０００２】
大規模ネットワークは、プロトコルあるいはネットワーク管理者が互いに異なる複数のネットワーク(この各ネットワークの領域を、以下ではドメインと称する)を接続することにより構成される。
【０００３】
このような大規模ネットワークにおいて、エンド・ツー・エンドの所要パス品質値が与えられたときのドメイン間パスを設定する際、各ドメインが、ドメイン間パスを構成する自ドメイン内パスのリソース消費を抑える技術が非特許文献１に記載されている。ここでは、着ドメインまでの残余パス品質値を満足する最低の品質クラスをドメイン間パスに割り当てる。なお、残余パス品質値は、自ドメインから着ドメインまでの間に要求されるパス品質値であり、自ドメインまでのパス品質値の消費分をエンド・ツー・エンドでの所要パス品質値から減算することにより求めることができる。
【０００４】
本発明者らは、エンド・ツー・エンドの所要パス品質値が与えられたときのドメイン間パスを設定する際に、各ドメインが自ドメインから着ドメインまでの全経由ドメインにおけるパスのリソース消費の総和を最小化するドメイン間パスの品質クラス割当方法を特許文献１で提案した。ここでは、着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数に対応させて、自ドメインにおける割当品質クラス候補を予め求めて置き、自ドメインにおける空きリソース量などに基づいて、品質クラス候補の中の１つの品質クラスをドメイン間パスに割り当てる。
【特許文献１】特願２００６−１８４３５７号(先願)
【非特許文献１】R. Zhang and J.-P. Vasseur, Ed., "MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements," IETF RFC4216, Nov. 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載された技術では、各ドメインは着ドメインまでの所要パス品質が自ドメイン内パスで満たされている限り、最低の品質クラスを自ドメイン内パスに割り当てるので、自ドメインのリソース消費を抑えることができる。しかしながら、下流ドメイン数が多い場合や、下流ドメインでの割当可能品質クラスがいずれも低いような場合には、ドメイン間パスのエンド・ツー・エンドでは所要パス品質が満足されなくなる可能性が高くなり、ドメイン間パス設定要求の損失率が増大するという課題がある。
【０００６】
特許文献１のドメイン間パスの品質クラス割当方法では、品質クラス候補の中から１つの品質クラスを選択してドメイン間パスに割り当てるが、割り当てる品質クラスの選択は、運用者の経験に頼らざるを得ない。また、下流ドメインでの割当可能品質クラスが想定よりも低い場合には、やはりドメイン間パスのエンド・ツー・エンドでの所要パス品質が満足されなくなり、ドメイン間パス設定要求の損失率が増大するという課題がある。
【０００７】
本発明の目的は、上記の課題を解決し、ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させながら、予め決められた性能指標を最適化する品質クラスを自ドメイン内パスに割り当てることができる品質クラス割当方策決定装置およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明は、エンド・ツー・エンドの所要品質値が与えられ、自ドメインを含む複数のドメインを経由するドメイン間パスの設定要求に応答して、ドメイン間パスを構成する自ドメイン内パスに品質クラスを割り当てるための品質クラス割当方策決定装置において、自ドメインへのドメイン間パス設定要求の到着を観測し、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算する第１の手段と、下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測し、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算する第２の手段と、前記第１および第２の手段により計算されたドメイン間パス設定要求の到着率および成功率に基づいて、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定する第３の手段を備えた点に第１の特徴がある。
【０００９】
また、本発明は、前記第１の手段が、通過する隣接下流ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し、前記第２の手段は、通過する隣接下流ドメインが同じパスごとに、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算し、前記第３の手段は、隣接下流ドメインごとに、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定する点に第２の特徴がある。
【００１０】
また、本発明は、前記第１の手段が、着ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算し、前記第２の手段は、着ドメインが同じパスごとに、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算し、前記第３の手段は、着ドメインごとに、自ドメインにおける品質クラス別パスの収容状態における割当可能品質クラスについての品質クラス割当方策を決定する点に第３の特徴がある。
【００１１】
なお、本発明は、品質クラス割当方策決定装置としてだけでなく、コンピュータを上記第１〜第３の手段として機能させるためのプログラムとしても実現できる。
【発明の効果】
【００１２】
本発明によれば、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別のパス設定要求の到着率に応じて、予め決められた性能指標を最適化する品質クラスを自ドメイン内パスに割り当てることが可能になる。
【００１３】
また、自ドメイン内パスに１つの品質クラスを割り当てた結果としての着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別のドメイン間パス設定要求に対する成功率に応じて、予め決められた性能指標を最適化する品質クラスを自ドメイン内パスに割り当てることが可能になる。すなわち下流ドメインにおける品質クラス割当方策に応じて、最適な品質クラスを自ドメイン内パスに割り当てることが可能になる。
【００１４】
また、通過する隣接下流ドメインが同じパスごとや、着ドメインが同じパスごとに最適な品質クラスを自ドメイン内パスに割り当てることが可能になる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明を詳細に説明する。図１は、本発明が適用される大規模ネットワークの主要部の構成例を模式的に示す図である。大規模ネットワークは、プロトコルやネットワーク管理者の異なる複数のネットワーク(ドメイン)A,B,C,・・・を、各ドメインの境界に設置されたボーダルータBRを介して相互に接続することにより構成されている。各ボーダルータBRにはポリシサーバPSが接続されている。図１では、例として、ドメインAのエンドノードaを送信元、ドメインDのエンドノードdを宛先とするドメイン間パスPadを図示している。
【００１６】
このような大規模ネットワークにおいて、エンド・ツー・エンドの所要パス品質値が与えられたときに、複数のドメインを経由するドメイン間パスを、予め発着ドメインごとに決められた１本の最短ドメイン間経路に沿って設定することを前提とする。ドメイン間パス設定要求は、最短ドメイン間経路に沿って、各経由ドメインに順番に到着する。ドメイン間パス設定要求が到着したとき、各経由ドメインは、ドメイン間パスを構成する自ドメイン内パスに割り当てる品質クラスを最適に決定する必要がある。
【００１７】
そのために、各ドメインのポリシサーバPSは、ドメイン間パス設定要求の到着率や下流ドメインにおけるドメイン間パス設定要求に対する成功率を計算し、それらに基づいて、品質クラス割当方策が最適化すべき性能指標が最適となるように品質クラス割当方策を求める。そして、これにより求められた品質クラス割当方策に従って自ドメイン内の各ノードを制御し、ドメイン間パスを構成する自ドメイン内パスに品質クラスを割り当てる。
【００１８】
上述したところから明らかなように、ポリシサーバPSは、本発明に係る品質クラス割当方策決定装置としての機能を有する。また、本発明に係るプログラムをポリシサーバPSに搭載することにより、品質クラス割当方策決定装置としての機能をポリシサーバPSに持たせることができる。このように、本発明は、品質クラス割当方策決定装置としてもプログラムとしても実現できる。
【００１９】
次に、各ドメインのポリシサーバPSにおける処理について説明する。ポリシサーバPSでは、まず、自ドメインでの割当可能品質クラスを選択する。この割当可能品質クラスの選択処理では、以下のようにして、自ドメインでの割当可能品質クラスを選択する。
【００２０】
自ドメインから着ドメインまでの下流ドメイン数(自ドメインおよび着ドメインを含む)をM、自ドメインと着ドメインとの間(自ドメインおよび着ドメインを含む)でドメイン間パスが満足すべき残余パス品質値(量子化して整数値で表現)をQとする。また、自ドメインで設定可能な品質クラス数をC、品質クラスj に対応する自ドメイン内パス品質値(量子化して整数値で表現)をqj、品質クラスjに属するパスのリソース使用量をrjとする。さらに、自ドメインにおける全リソース量をRとし、自ドメインにおける品質クラス別パス収容数(N０,・・・,NＣ−１)によって自ドメインの状態Sを表す。
【００２１】
図２は、各品質クラスに関する情報、つまり各品質クラスjに対応する自ドメイン内パス品質値qjおよびリソース使用量rjの具体例を示す。図２において、例えば、品質クラス0は、品質値1.0を有し、それを割り当てた場合のリソース使用量は16.0となることを示している。品質は、品質値が小さくなるほど良くなり、これに伴ってリソース使用量が増大する。
【００２２】
もしQがqjよりも小さいとき、jを割り当ててもQを満足することはできないので、jは割当可能品質クラスから除外する。また、もし状態Sにおける空きリソース量r(S)がrjよりも少ない場合、jを割り当てるだけのr(S)がないので、やはりjは割当可能品質クラスから除外する。残った品質クラスを割当可能品質クラスとして選択する。ここでは、割当可能品質クラスの集合をClass(Q, S)で表す。以上が、割当可能品質クラスの選択処理の具体的内容である。
【００２３】
次に、品質クラス割当方策を計算する。本発明では、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求の到着率を計算する。また、自ドメインで１つの品質クラスを割り当てた結果としての着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にドメイン間パス設定要求に対する成功率を計算する。そして、それらの計算結果に基づいて、自ドメインの状態に応じて品質クラス割当方策が最適化すべき性能指標が最適となるように品質クラス割当方策を求める。
【００２４】
ドメイン間パス設定要求の到着およびドメイン間パスの解法がマルコフ過程に従うものと仮定して、マルコフ決定理論を応用して品質クラス割当方策を計算する。ドメイン間パス設定要求の到着率およびドメイン間パス設定要求に対する成功率の変化に適応するために、自ドメインへのドメイン間パス設定要求の到着および下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測する。ドメイン間パス設定要求の到着率やドメイン間パス設定要求に対する成功率の計算は、予め決められた時間ごとに周期的に行えばよい。
【００２５】
これにより求められた品質クラス割当方策は、次回の品質クラス割当方策が求められるまで、自ドメイン内パスに品質クラスを割り当てるために使用される。
【００２６】
図３は、本発明に係る品質クラス割当方策決定装置における処理手順の一例を示すフローチャートである。まず、品質クラス割当方策計算周期タイマをセットする(S30)。この計算周期タイマにセットする時間は、ドメイン間パスへの品質割当方策をどの程度の頻度で変えるかに応じて予め決められる。以後、品質クラス割当方策の計算は、この周期ごとに行われる。
【００２７】
次に、ドメイン間パス設定要求の到着(イベント)を待つ(S31)。ここで、イベントが発生せず、計算周期タイマにセットされた時間が経過(タイムアウト)した場合(S32)、品質クラス割当方策の初期値を設定する(S33)。下流ドメイン数をM、残余パス品質値をQ、自ドメインの状態をS、状態Sに対する品質クラス割当方策をP(M,Q,S,j)としたとき、P(M,Q,S,j)の初期値は、例えば式(1)に従って与えることができる。
【００２８】
【数１】
2008205939.tif 000003
【００２９】
次に、ドメイン間パス設定要求の到着を観測することによって得られたドメイン間パス設定要求の到着率と下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測することによって得られたドメイン間パス設定要求の成功率を用い、S33で設定された品質クラス割当方策(初期値)から出発して、品質クラス割当方策が最適化すべき性能指標が最適となるように品質クラス割当方策を更新する(S34〜S36)。なお、ドメイン間パス設定要求の到着や下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かは、品質クラス割当方策を計算する以前に観測される。
【００３０】
以下、S34〜S36における処理について説明する。
ここで、ドメイン間パスの平均パス保留時間を単位時間として、次のようにシンボルを定義する。
A(M,Q): ドメイン間パス設定要求の到着を観測することによって得られた、下流ドメイン数がM、残余パス品質値がQであるようなドメイン間パス設定要求の単位時間当たりの到着率。
B(M-1,Q-qj) : 下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測することによって得られた、自ドメインを含まない下流ドメイン数がM-1、自ドメインを含まない残余パス品質値がQ-qjであるようなドメイン間パス設定要求に対する成功率。すなわち、下流ドメイン数がM、残余パス品質値がQであるようなドメイン間パスに対して、品質クラスjを割り当てたときの下流ドメインでのドメイン間パス設定要求に対する成功率。
P (M,Q,S,j): 求める品質クラス割当方策。すなわち下流ドメイン数がM、残余パス品質値がQであるようなドメイン間パスに対して、状態がSであるときに品質クラスjを割り当てる確率。ただし、品質クラスjは、Class(Q,S)に含まれるものとする。
N(S): 品質クラス割当方策が最適化すべき性能指標の状態Sにおける値。
【００３１】
図４は、ドメイン間パス設定要求の到着率A(M,Q)の具体例を示す図である。到着率A(M,Q)は、ドメイン間パス設定要求の到着を観測することによって得られたものであり、後述するS38で更新される。  図５は、ドメイン間パス設定要求の成功率B(M-1,Q-qj)の具体例を示す図である。成功率B(M-1,Q-qj)は、下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測することによって得られたものであり、後述するS41で更新される。
【００３２】
品質クラス割当方策の目標が、例えば平均パス収容数の最大化である場合、状態S=(N０,・・・,NＣ−１)のときのN(S)は、式(2)で与えられる。なお、N(S)は、任意の性能指標でよく、状態Sで得られる収益などとすることもできる。
【００３３】
【数２】
2008205939.tif 000004
【００３４】
マルコフ決定理論より、各ドメイン状態S全て(for all S)に対して式(3)が成立する。
【００３５】
【数３】
2008205939.tif 000005
【００３６】
式(3)において、〈N〉は最大化すべき性能指標の長時間平均値を表し、V(S)はドメイン状態Sから出発したときの性能指標の時間的累積値を示す。また状態S+Δjは、状態Sに対して品質クラスjのパス収容数が１本増加した状態、状態S-Δjは、状態Sに対して品質クラスjのパス収容数が１本減少した状態を示す。さらに、式(2)において、存在し得ないドメイン状態を含む項は無視する。定義からわかるように、V(S)の値自体は無限大になり、２つの値の差のみが意味を持つ。式(2)は、状態S全てに対して成立するので、状態数分だけ存在し、それらの式の任意の右辺を２つ組み合わせて構成されたV(S)に関する連立一次方程式の数は、状態数よりも１つだけ少なくなる。したがって、例えば、V(0)の値をゼロと置いて連立一次方程式を解くことにより、V(S)の値を求めることができる。S34では、上述のようにして、V(S)の値を求める。
【００３７】
品質クラス割当方策の目標が、式(3)における〈N〉の最大化であることから、S34でV(S)の値を求めた後、S35では、以下のようにしてP(M,Q,S,j)の値を更新する。
【００３８】
まず、以下の式(4)を満足しない品質クラスを割当可能品質クラスClass(Q,S)から一時的に除外し、それによって得られる新たな割当可能品質クラスをClass′(M,Q,S)とする。
【００３９】
【数４】
2008205939.tif 000006
【００４０】
次に、式(3)におけるP(M,Q,S,j)の係数をC(M,Q,S,j)とする。係数C(M,Q,S,j)は、式(5)で表される。
【００４１】
【数５】
2008205939.tif 000007
【００４２】
ドメイン状態がSであるとき、下流ドメイン数がM、残余パス品質値がQであるようなドメイン間パス設定要求に対して、係数C(M,Q,S,j)を最大化する割当可能品質クラスClass′(M,Q,S)に含まれる品質クラスをj*と置く。P(M,Q,S,j*)の係数C(M,Q,S,j*)は、式(6)で表される。
【００４３】
【数６】
2008205939.tif 000008
【００４４】
このとき、Class(Q,S)の要素数をn、Class′(M,Q,S)の要素数をn′とすると、ドメイン状態がSであるときの下流ドメイン数がM、残余パス品質値がQであるようなドメイン間パス設定要求に対して、式(7)に従ってP(M,Q,S,j*)およびP(M,Q,S,j)の値を更新する。
【００４５】
【数７】
2008205939.tif 000009
【００４６】
式(7)の上段の式は、割当可能品質クラスが２つ以上で、品質クラスj*が一時的な割当可能品質クラスClass′(M,Q,S)に含まれるとき、品質クラスj*を割り当てる確率P(M,Q,S,j*)をΔP′だけ増大させ、その他の品質クラスjを割り当てる確率P(M,Q,S,j)をΔP/(n-1)だけ減少させるように更新すること(全品質クラスについてのトータルの確率は1.0で変わらない)、ただし、更新後の確率P(M,Q,S,j*)は最大1.0までであり、更新後の確率P(M,Q,S,j)は最小0.0までであることを表している。
【００４７】
式(7)の中段の式は、割当可能品質クラスが１つで、その品質クラスが一時的な割当可能品質クラスClass′(M,Q,S)に含まれるとき、その品質クラスj*を割り当てる確率P(M,Q,S,j*)を更新しないことを表している。
【００４８】
式(7)の下段の式は、一時的な割当可能品質クラスClass′(M,Q,S)に含まれる品質クラスが存在しないとき、全ての品質クラスj(j∈Class(Q,S))について割り当てる確率P(M,Q,S,j)をΔP/nだけ減少させるように更新すること、ただし、更新後の確率P(M,Q,S,j)は最小0.0までであることを表している。なお、式(7)におけるΔP′,ΔP(更新幅)としては、0.01〜0.1程度の値を用いるのが適当である。
【００４９】
次のS36では、P(M, Q, S, j)の値が収束したか否かを判定する。P(M, Q, S, j)の値が収束したか否かは、更新前後のP(M, Q, S, j)の値の変化が所定閾値以下かどうかで判定できる。
【００５０】
S36で、P(M, Q, S, j)の値が収束していないと判定された場合、S34に戻ってS34〜S36の処理をP(M, Q, S, j)の値が収束するまで繰り返す。すなわち、全ての下流ドメイン数M、残余品質値Q、状態Sに対して更新されたP(M, Q, S, j)の値(暫定的な品質クラス割当方策)を式(3)に代入してV(S)の値を再び求め(S34)、その結果に応じて、再び式(7)を使ってP(M, Q, S, j)の値を更新する(S35)。
【００５１】
S36で、P(M, Q, S, j)の値が収束したと判定された場合には、収束したP(M, Q, S, j)の値を最適な品質クラス割当方策として導出する。その後、S20に戻る。
【００５２】
図６は、以上のようにして導出された品質クラス割当方策(品質クラス割当確率)の具体例を示す図である。図６は、例えば、下流ドメイン数Mが4、残余パス品質値Qが8.0であるようなドメイン間パスに対して、状態Sが(0,0,・・・,2)であるとき、品質クラス0,1,・・・,C-1を割り当てる確率はそれぞれ、0.2,0.2,・・・,0.2であることを示している。なお、斜線部は、割当可能な品質クラスを選択する処理において、自ドメインにおいて割り当てることができないとされて除外された品質クラスを示している。
【００５３】
S37〜S41は、計算周期タイマがタイムアウトする間での間、すなわち品質クラス割当方策が導出されて更新されるまでの期間内で行われる処理である。S31でイベント待ちしていて、計算周期タイマがタイムアウトするまでにドメイン間パス設定要求の到着が観測された場合(S37)、ドメイン間パス設定要求の到着率を計算(S38)するとともに、先に導出された最適な品質クラス割当方策に従って、到着したドメイン間パス設定要求に対する自ドメイン内パスに品質クラスを割り当てる(S39)。なお、最適な品質クラス割当方策がS34〜S36で先に導出されていなければ、式(1)で与えられる初期値をS39での品質クラス割当方策とすればよい。S38で計算されたドメイン間パス設定要求の到着率は、S34で次回の品質クラス割当方策を計算する際に用いられる。
【００５４】
次に、自ドメインでの品質クラスの割り当てが成功したか否かを判定する(S40)。ここで、成功したと判定された場合、下流ドメインにおけるドメイン間パス設定が成功したか否かを観測し、この観測結果に基づいて、下流ドメインにおけるドメイン間パス設定成功率を計算する(S41)。その後、S32に戻る。S41で計算された下流ドメインにおけるドメイン間パス設定成功率は、S34で次回の品質クラス割当方策を計算する際に用いられる。S40で、自ドメインでの品質クラスの割り当てが不成功と判定された場合にはそのままS32に戻る。なお、ドメイン間パス設定要求の到着率やドメイン間パス設定要求に対する成功率は、ドメイン間パス設定要求が到着する都度計算する必要はなく、予め決められた時間ごとに周期的に行ってもよい。
【００５５】
下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かは、運用上でドメイン間パスを設定する際に、シグナリングプロトコルを利用してドメイン間で情報を送受信することにより観測できる。また、自ドメインから下流ドメインに対してダミーのドメイン間パス設定要求を送信し、その応答を受信することによっても観測できる。
【００５６】
自ドメインに対する隣接下流ドメインが複数存在する場合、通過する隣接下流ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にパス設定要求の到着率を計算し、また、自ドメインを含まない着ドメインまでの残余パス品質値と着ドメインまでの経由ドメイン数別にパス設定要求に対する成功率を計算することによって、隣接下流ドメインごとに、異なる品質クラス割当方策を適用することができる。
【００５７】
以下、この場合の品質クラス割当処理について説明する。隣接下流ドメインをDowで表し、各シンボルを以下のように定義する。
A(Dow, M, Q): ドメイン間パス設定要求の到着を観測することによって得られた、通過する隣接下流ドメインがDow、下流ドメイン数がM、残余品質値がQであるようなドメイン間パス設定要求の単位時間当たりの到着率。
B(Dow, M-1, Q-qj) : 下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測することによって得られた、通過する隣接下流ドメインがDow、自ドメインを含まない下流ドメイン数がM-1、自ドメインを含まない残余パス品質値がQ-qjであるようなドメイン間パス設定要求に対する成功率。すなわち、通過する隣接下流ドメインがDow、下流ドメイン数がM、残余パス品質値がQであるようなドメイン間パスに対して、品質クラスjを割り当てたときの下流ドメインでのパス設定要求に対する成功率。
P(Dow, M, Q, S, j): 求める品質クラス割当方策。すなわち通過する隣接下流ドメインがDow、下流ドメイン数がM、残余品質値がQであるようなドメイン間パスに対して、状態がSであるときに品質クラスjを割り当てる確率。ただし、品質クラスjは、Class(Q, S)に含まれる。このとき、式(3)は、式(8)のように変形される。
【００５８】
【数８】
2008205939.tif 000010
【００５９】
式(8)からV(S)の値を求め、P(Dow, M, Q, S, j)の係数であるC(Dow, M, Q, S, j)の値に応じて、P(Dow, M, Q, S, j)の値を更新する。このとき、最適品質クラス割当方策への収束性の観点から、ある１つの隣接下流ドメインに対する品質クラス割当方策のみを、一度の更新の対象にすることが望ましい。
【００６０】
同様に、着ドメインが同じパスごとに、自ドメインを含む着ドメインまでの残余パス品質値別にパスの設定要求の到着率を計算し、また、自ドメインを含まない着ドメインまでの残余パス品質値別にパスの設定要求に対する成功率を計算することによって、ドメイン間パスの着ドメインごとに、異なる品質クラス割当方策を適用することができる。
【００６１】
以下、この場合の品質クラス割当処理について説明する。このとき、着ドメインをDesで表し、各シンボルを以下のように定義する。
A(Des, Q): ドメイン間パス設定要求の到着を観測することによって得られた、着ドメインがDes、残余品質値がQであるようなドメイン間パス設定要求の単位時間当たりの到着率。
B(Des, Q-qj) : 下流ドメインにおいてドメイン間パス設定要求に対する設定が成功したか否かを観測することによって得られた、着ドメインがDes、自ドメインを含まない残余パス品質値がQ-qjであるようなドメイン間パス設定要求に対する成功率。すなわち、着ドメインがDes、残余品質値がQであるようなドメイン間パスに対して、品質クラスjを割り当てたときの下流ドメインでのパス設定要求に対する成功率。
P(Des, Q, S, j): 求める品質クラス割当方策。すなわち着ドメインがDes、残余品質値がQであるようなドメイン間パスに対して、状態がSであるときに品質クラスjを割り当てる確率。ただし、品質クラスjは、Class(Q, S)に含まれる。このとき、式(3)は、式(9)のように変形される。なお、着ドメインが決まれば、下流ドメイン数(自ドメインから着ドメインまでのドメイン数)Mは決まるので、式(9)ではMを省略している。
【００６２】
【数９】
2008205939.tif 000011
【００６３】
式(9)式からV(S)の値を求め、P(Des, Q, S, j)の係数であるC(Des, Q, S, j)の値に応じて、P(Des, Q, S, j)の値を更新する。このとき、最適な品質クラス割当方策への収束性の観点から、ある１つの着ドメインに対する品質クラス割当方策のみを、一度の更新の対象にすることが望ましい。
【００６４】
以上のようにして、各ドメインのポリシサーバPSは、品質クラス割当方策を計算し、これにより求められた品質クラス割当方策に従ってドメイン間パスを構成する自ドメイン内パスに品質クラスを割り当てる。
【図面の簡単な説明】
【００６５】
【図１】本発明が適用される大規模ネットワークの主要部の構成例を模式的に示す図である。
【図２】各品質クラスに関する情報の具体例を示す図である。
【図３】本発明に係る品質クラス割当方策決定装置における処理手順の一例を示すフローチャートである。
【図４】ドメイン間パス設定要求の到着率の具体例を示す図である。
【図５】ドメイン間パス設定要求の成功率の具体例を示す図である。
【図６】導出された品質クラス割当方策の具体例を示す図である。
【符号の説明】
【００６６】
A,B,C,D・・・ドメイン、a,d・・・エンドノード、PS・・・ポリシサーバ、BR・・・ボーダルータ、Pad・・・ドメイン間パス
【図１】
2008205939.tif 000012
【図２】
2008205939.tif 000013
【図３】
2008205939.tif 000014
【図４】
2008205939.tif 000015
【図５】
2008205939.tif 000016
【図６】
2008205939.tif 000017