(57)【要約】【課題】ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させながら、最小コストのドメイン間パスを設定できるドメイン間パスの品質クラス割当方法、プログラムおよびその記憶媒体を提供する。【解決手段】自ドメインから着ドメインまでの下流ドメイン数N、および自ドメインと着ドメインとの間でドメイン間パスが満足すべき品質値Qごとに、リソース使用量の総和を最小化することを目的とした数理モデルを解いて、自ドメインを含む下流ドメインのドメイン内パスに割り当て可能な品質クラス候補を求め、この品質クラス候補のいずれかを自ドメイン内パスに割り当てる。【選択図】図５
2008017005.tif 000002
【特許請求の範囲】
【請求項１】
自ドメインを含む複数のドメインを経由するドメイン間パスの設定要求に応答して、ドメイン間パスを構成する自ドメイン内パスに割り当てる品質クラスを決定するドメイン間パスの品質クラス割当方法において、
各ドメインが、
ドメイン間パスの自ドメインから所定の着ドメインまでの下流ドメイン数N、および自ドメインと着ドメインとの間で前記ドメイン間パスが満足すべき品質値Qを設定する手順と、
前記下流ドメイン数Nおよび品質値Qごとに、自ドメインから着ドメインまでの全経由ドメインにおける使用リソース量の総和を最小化する数理モデルを解いて、自ドメインを含む下流ドメインがそれぞれのドメイン内パスに割り当て可能な品質クラス候補を算出する手順とを含み、
各ドメインがさらに、
ドメイン間パス設定要求を受信して、当該ドメイン間パスでの下流ドメイン数Nおよび品質値Qに関する情報を取得する手順と、
前記下流ドメイン数Nおよび品質値Qに対応した品質クラス候補を選択する手順と、
前記品質クラス候補の中から、前記ドメイン間パスを構成する自ドメイン内パスに割り当てる品質クラスを決定する手順と、
前記自ドメイン内パスに割り当てた品質クラスに基づいて更新されたドメイン間パス設定要求を下流ドメインへ転送する手順とを含むことを特徴とするドメイン間パスの品質クラス割当方法。
【請求項２】
前記ドメイン内パスの品質クラスを決定する手順は、
自ドメインの空きリソース量が、品質クラス候補の中で最低の品質クラスに必要なリソース量よりも多いときに、当該最低の品質クラスを自ドメイン内パスに割り当てる手順と、
自ドメインの空きリソース量が、品質クラス候補の中で最低の品質クラスに必要なリソース量よりも少ないときに、使用リソース量が前記空きリソース量よりも少ない品質クラスの中で最高の品質クラスを自ドメイン内パスに割り当てる手順とを含むことを特徴とする請求項１に記載のドメイン間パスの品質クラス割当方法。
【請求項３】
前記自ドメイン内パスに割り当てる品質クラスを決定する手順では、品質クラス候補のいずれかを、前記数理モデルにおける下流ドメインへの各品質クラス候補の割当数に応じた確率で自ドメイン内パスに割り当てることを特徴とする請求項１に記載のドメイン間パスの品質クラス割当方法。
【請求項４】
前記自ドメイン内パスに割り当てる品質クラスを決定する手順では、自ドメインの空きリソース量が所定の基準値以上であれば、品質クラス候補のいずれかを、前記数理モデルにおける下流ドメインへの各品質クラス候補の割当数に応じた確率で自ドメイン内パスに割り当て、自ドメインの空きリソース量が所定の基準値未満であれば、品質クラス候補の中で最低の品質クラスを自ドメイン内パスに割り当てることを特徴とする請求項１に記載のドメイン間パスの品質クラス割当方法。
【請求項５】
前記請求項１ないし４のいずれかに記載の品質クラス割当方法をコンピュータに実行させるためのドメイン間パスの品質クラス割当プログラム。
【請求項６】
請求項５に記載の品質クラス割当プログラムをコンピュータによる読み出し可能に記憶したドメイン間パスの品質クラス割当プログラムの記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ドメイン間パスの品質クラス割当方法、プログラムおよびその記憶媒体に係り、特に、ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させながら、最小コストのドメイン間パスを設定できるドメイン間パスの品質クラス割当方法、プログラムおよびその記憶媒体に関する。
【背景技術】
【０００２】
大規模なネットワークは、プロトコルあるいはネットワーク管理者が互いに異なる複数のネットワーク（このネットワーク領域を、以下ではドメインと称する）を接続することにより構成される。
【０００３】
このような大規模ネットワークにおいて、エンド・ツー・エンドの所要品質値が与えられたドメイン間パスを設定する際に、各ドメインがドメイン間パスを構成する自ドメイン内パスのリソース消費を抑える技術が非特許文献１に開示されている。ここでは、自ドメインから着ドメインまでの間に要求されるパス品質が、少なくとも自ドメイン内パスでは満たされる範囲内で最低の品質クラスが自ドメイン内パスに割り当てられる。
【非特許文献１】R. Zhang and J.-P. Vasseur, Ed., "MPLS Inter-Autonomous System (AS) Traffic Engineering (TE) Requirements," IETF RFC4216, Nov. 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記した従来技術では、各ドメインは着ドメインまでの所要パス品質が自ドメイン内パスで満たされている限り、自ドメインのリソース消費を抑えるために最低の品質クラスを自ドメイン内パスに割り当てるので、下流ドメイン数が多い場合や、下流ドメインで割り当て可能な品質クラスがいずれも低いような場合には、ドメイン間パスのエンド・ツー・エンドでは所要品質が満足されなくなる可能性が高くなり、ドメイン間パスの設定要求損失率が増大する。
【０００５】
本発明の目的は、上記した従来技術の課題を解決し、ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させながら、最小コストのドメイン間パスを設定できるドメイン間パスの品質クラス割当方法、プログラムおよびその記憶媒体を提供することにある。
【課題を解決するための手段】
【０００６】
上記した目的を達成するために、本発明は、自ドメインを含む複数のドメインを経由するドメイン間パスの設定要求に応答して、ドメイン間パスを構成する自ドメイン内パスに割り当てる品質クラスを決定するドメイン間パスの品質クラス割当方法を対象とし、各ドメインが以下の手順を含むことを特徴とする。
【０００７】
すなわち、ドメイン間パスの自ドメインから所定の着ドメインまでの下流ドメイン数N、および自ドメインと着ドメインとの間で前記ドメイン間パスが満足すべき品質値Qを設定する手順と、下流ドメイン数Nおよび品質値Qごとに、自ドメインから着ドメインまでの全経由ドメインにおける使用リソース量の総和を最小化する数理モデルを解き、自ドメインを含む下流ドメインがそれぞれのドメイン内パスに割り当て可能な品質クラス候補を算出する手順と、ドメイン間パス設定要求を受信して当該ドメイン間パスでの下流ドメイン数Nおよび品質値Qに関する情報を取得する手順と、下流ドメイン数Nおよび品質値Qに対応した品質クラス候補を選択する手順と、品質クラス候補の中から、前記ドメイン間パスを構成する自ドメイン内パスに割り当てる品質クラスを決定する手順と、自ドメイン内パスに割り当てた品質クラスに基づいて更新されたドメイン間パス設定要求を下流ドメインへ転送する手順とを含むことを特徴とする。
【発明の効果】
【０００８】
本発明によれば、ドメイン間パスに要求されるエンド・ツー・エンドでの品質を満足させつつ、各ドメインが自ドメインを経由するドメイン間パスの設定要求損失率を低減できるようになる。
【発明を実施するための最良の形態】
【０００９】
以下、図面を参照して本発明の最良の実施の形態について詳細に説明する。図１は、本発明の品質クラス割当方法が適用されるドメイン間ネットワークの主要部の構成を模式的に表現した図であり、プロトコルやネットワーク管理者の異なる複数のネットワーク（ドメイン）が、各ドメインの境界に設置されたボーダルータBRを介して相互に接続され、各ボーダルータBRにはポリシサーバPSが接続されている。ここでは、ドメインAのエンドノードaを送信元、ドメインDのエンドノードdを宛先とするドメイン間パスPadを例にして、各ドメインにおける当該ドメイン間パスPadを構成する自ドメイン内パスへの品質クラスの割当方法を説明する。
【００１０】
図２は、本実施形態における品質クラス割当方法の手順を示したフローチャートであり、ドメイン間パスPadが経由する各ドメインA，B，C，DのボーダルータBRに接続されたポリシサーバPSにおいて自律的に実行される。
【００１１】
本実施形態では、各ドメインにおいてドメイン間パス設定要求が検知された際に自ドメイン内パスに最適な品質クラスを直ちに決定できるように、ドメイン間パス上の自ドメインから着ドメインまでの下流ドメイン数（自ドメインおよび着ドメインを含む）と、自ドメインと着ドメインとの間（自ドメインおよび着ドメインを含む）でドメイン間パスが満足すべき品質値ごとに、自ドメイン内パスに割り当て可能な品質クラス候補を予め各ポリシサーバPSに登録（ステップＳ１）しておき、その後、ドメイン間パス設定要求が到着したときに、要求パスの下流ドメイン数および品質値に基づいて品質クラス候補を前記ポリシサーバPSから抽出し、当該品質クラス候補の中から自ドメインに最適な品質クラスを自律分散的に選択して自ドメイン内パスに割り当てる（ステップＳ２〜Ｓ５）。
【００１２】
以下、図２のフローチャートに沿って本実施形態の動作を詳細に説明する。ステップＳ１では、各ドメインにおいて、自ドメインから着ドメインまでの全経由ドメインにおける使用リソース量の総和を最小化する品質クラス候補が、下流ドメイン数およびドメイン間パスが満足すべき品質値ごとに算出されてポリシサーバPSに登録される。
【００１３】
ここでは、自ドメインから着ドメインまでの下流ドメイン数（自ドメインおよび着ドメインを含む）をN、自ドメインと着ドメインとの間（自ドメインおよび着ドメインを含む）でドメイン間パスが満足すべき品質値（量子化して整数値で表現）をQとする。また、各ドメインが設定可能な品質クラス数をC、品質クラスj に対応する自ドメイン内パス品質値（量子化して整数値で表現）をqj、品質クラスjに属するパスのリソース使用量をrjとする。
【００１４】
そして、遅延や廃棄率等の加算型の品質を想定して、以下の制約条件(1)、決定変数(2)および目的関数(3)の数理モデルを整数計画法などで解き、下流ドメインの少なくとも一つで選択される品質クラスを、前記下流ドメイン数Nおよび品質値Qと対応付けて、自ドメイン内パスに割り当て可能な品質クラス候補として登録する。
2008017005.tif 000003
2008017005.tif 000004
2008017005.tif 000005
【００１５】
ここで、決定変数(2)のx i, j は、自ドメインからi 番目の下流ドメインで品質クラスj が選択される場合に値が「１」、選択されない場合に値が「０」であるバイナリ変数である。したがって、制約条件(1)はパス上の各下流ドメインで選択された、品質クラスjに対応するパス品質値qjの総和が、自ドメインと着ドメインとの間でパスが満足すべき品質値Qを満足する（≦Q）ことを表している。目的関数(3)は、自ドメインから着ドメインまでの全経由ドメインにおけるリソース使用量の総和を最小化することを表している。
【００１６】
図３は、前記ステップＳ１における品質クラス候補の算出手順を示したフローチャートである。
【００１７】
ステップＳ１０１では、下流ドメイン数N（Nはドメイン総数以下）および品質値Qが設定される。ステップＳ１０２では、今回の下流ドメイン数Nおよび品質値Qに対して、上述の数理モデルの解法を行い、下流ドメインの少なくとも一つで選択される品質クラスを、自ドメイン内パスに割り当て可能な品質クラス候補として、前記ポリシサーバPSに登録する。
【００１８】
なお、全ての下流ドメインで最高の品質クラスが選択されても着ドメインまでの要求品質値を満足できない場合には、上述の数理モデルの解が存在しないので、この場合は割り当て品質クラス候補は無いと考えてパス設定要求が損失と見なされる。
【００１９】
ステップＳ１０３では、全ての下流ドメイン数Nおよび品質値Qに対して、上述の数理モデルの解法が繰り返される。但し、品質値Qは、各品質クラスjに対応するパス品質値qjが連続した実数ではなく離散値であれば、所要品質値Qが取り得る値も離散値となるので、この離散値（エンドツーエンドでのドメイン間パスの所要品質値以下で、かつその所要品質値から全ての品質クラスに対応する自ドメイン内パス品質値の最大公約数のゼロを含む整数倍を引いた値）のみについて計算することで計算量を減じられるようになる。
【００２０】
図４は、所定の品質値Qにおいて、品質クラス数Cが「５」、下流ドメイン数Nが「４」である場合の数理モデルの解の一例を示しており、図５は、図４の解に対応してポリシサーバPSに予め保持して置くべき品質クラス候補割当情報を示している。
【００２１】
図４では、０番目の下流ドメインすなわち自ドメインのドメイン内パスの品質クラスを「１」、１番目の下流ドメイン（図１では、ドメインＢ）のドメイン内パスの品質クラスを「３」、２番目の下流ドメイン（図１では、ドメインＣ）のドメイン内パスの品質クラスを「２」、３番目の下流ドメイン（図１では、ドメインＤ）のドメイン内パスの品質クラスを「１」に設定すれば、所定の品質値Qを満足させつつ、４つの下流ドメインにおけるリソース使用量の総和を最小化できることを意味している。
【００２２】
但し、加算型の品質を想定するのであれば、下流ドメインとその品質クラスとの組み合わせは任意なので、ポリシサーバPSに保持される品質クラス候補割当情報は、図５の通りとなる。これは、品質クラス１を４つの下流ドメインのいずれか２つに割り当て、品質クラス２を４つの下流ドメインのいずれか１つに割り当て、品質クラス３を４つの下流ドメインのいずれか１つに割り当て、品質クラス０，４はいずれの下流ドメインにも割り当てないことにより、所定の品質値Qを満足させつつ、４つの下流ドメインにおけるリソース使用量の総和を最小化できることを意味している。
【００２３】
図２に戻り、各ドメインではその後、ステップＳ２においてドメイン間パス設定要求の到着が検知されると、ステップＳ３では、このドメイン間パス設定要求に登録されているパス設定情報に基づいて、自ドメインから着ドメインまでの下流ドメイン数Nと、自ドメインと着ドメインとの間でドメイン間パスが満足すべき品質値Qとが認識される。
【００２４】
前記下流ドメイン数Nは、例えばドメイン間パス設定要求に登録されている着ドメインと、自ドメインで管理しているドメイン間経路情報とに基づいて認識できる。前記品質値Qは、ドメイン間パス設定要求を中継する各ドメインが、自ドメインで割り当てた品質クラスをドメイン間パス設定要求に登録しておき、このドメイン間パス設定要求を受信した各下流ドメインが、発ドメインと着ドメインとの間で満足すべき品質値から、経由した各上流ドメインで割り当てられた品質クラスに応じた品質値を減じることで判定できる。
【００２５】
ステップＳ４では、前記下流ドメイン数Nおよび品質値Qに応じた品質クラス候補がポリシサーバPSから検索される。ステップＳ５では、検索された品質クラス候補の中から、自ドメイン内パスに割り当てる品質クラスが決定される。本実施形態では、以下の３つの手法のいずれかに基づいて品質クラスが決定される。
【００２６】
図６は、第１の品質クラス決定方法の手順を示したフローチャートであり、品質クラス候補の中で最低の品質クラスが、常に自ドメイン内パスに割り当てられる。
【００２７】
ステップＳ５０１では、前記下流ドメイン数Nおよび品質値Qに応じて選択された品質クラス候補がポリシサーバPSに登録されているか否かが判定され、既登録であればステップＳ５０２へ進む。ステップＳ５０２では、品質クラス候補の中で最低の品質クラス（図５の例では、品質クラス１）に相当する空きリソース量をドメイン内に確保できるか否かが判定され、確保できればステップＳ５０３へ進む。ステップＳ５０３では、当該最低の品質クラスが自ドメイン内パスに割り当てられる。
【００２８】
これに対して、前記ステップＳ５０２において、品質クラス候補内で最低の品質クラスに相当する空きリソース量を自ドメイン内に確保できなければステップＳ５０４へ進む。ステップＳ５０４では、品質クラス候補とは無関係に、空きリソース量の範囲内で割当可能な品質クラスの有無が判定され、割当可能な品質クラスがあればステップＳ５０５へ進む。ステップＳ５０５では、割当可能な品質クラスの中で最高の品質クラスが自ドメイン内パスに割り当てられる。
【００２９】
なお、ステップＳ５０１において品質クラス候補が未登録と判定されるか、あるいはステップＳ５０４において空きリソース量の範囲内で割当可能な品質クラスが無いと判定されると、今回のパス設定要求が損失とされる。
【００３０】
図７は、第２の品質クラス決定方法の手順を示したフローチャートであり、品質クラス候補のいずれかが、前記数理モデルにおける下流ドメイン（自ドメインを含む）への各品質クラス候補の割当数に応じた確率で自ドメイン内パスに割り当てられる。
【００３１】
ステップＳ５１１では、前記下流ドメイン数Nおよび品質値Qに応じた品質クラス候補がポリシサーバPSに登録されているか否かが判定され、既登録であればステップＳ５１２へ進む。ステップＳ５１２では、前記品質クラス候補の中から、前記数理モデルによる下流ドメインへの各品質クラス候補の割当数に応じた確率で一つの品質クラスが選択される。
【００３２】
すなわち、品質クラス候補が図５の通りであり、下流ドメインに品質クラス１が２つ、品質クラス２が一つ、品質クラス３が一つ割り当てられるのであれば、品質クラス１が５０％の確率で割り当てられ、品質クラス２、３がいずれも２５％の確率で割り当てられる。
【００３３】
ステップＳ５１３では、ドメイン内の空きリソース量Miが所定のリソース量Mj以上であるか否かが判定され、Mi≧MjであればステップＳ５１４へ進む。前記リソース量Mjは、ステップＳ５１２で選択された品質クラスで消費されるリソース量に相当する。ステップＳ５１４では、前記ステップＳ５１２で選択された品質クラスが自ドメイン内パスに割り当てられる。
【００３４】
これに対して、前記ステップＳ５１３において、自ドメイン内の空きリソース量Miがリソース量Mj未満と判定されるとステップＳ５１５へ進む。ステップＳ５１５では前記ステップＳ５０４と同様に、品質クラス候補とは無関係に、空きリソース量の範囲内で割当可能な品質クラスの有無が判定され、割当可能な品質クラスがあればステップＳ５１６へ進む。ステップＳ５１６では前記ステップＳ５０５と同様に、割当可能な品質クラスの中で最高の品質クラスが自ドメイン内パスに割り当てられる。
【００３５】
図８は、第３の品質クラス決定方法の手順を示したフローチャートであり、上記した第１および第２の方式を組み合わせた方式である。
【００３６】
ステップＳ５２１では、前記下流ドメイン数Nおよび品質値Qに応じた品質クラス候補がポリシサーバPSに登録されているか否かが判定され、既登録であればステップＳ５２２へ進む。ステップＳ５２２では、ドメイン内の空きリソース量Miが所定の基準値Mref以上であるか否かが判定され、Mi≧MrefであればステップＳ５２３へ進む。
【００３７】
ステップＳ５２３では、前記品質クラス候補の中から、前記数理モデルによる下流ドメインへの各品質クラス候補の割当数に応じた確率で一つの品質クラスが選択される。ステップＳ５２４では、ドメイン内の空きリソース量Miが所定のリソース量Mj以上であるか否かが判定され、Mi≧MjであればステップＳ５２５へ進み、Mi＜MjであればステップＳ５２８へ進む。前記リソース量Mjは、ステップＳ５２３で選択された品質クラスで消費されるリソース量に相当する。ステップＳ５２５では、前記ステップＳ５２３で選択された品質クラスが自ドメイン内パスに割り当てられる。
【００３８】
これに対して、前記ステップＳ５２２において、ドメイン内の空きリソース量Miが基準値Mref未満と判定されるとステップＳ５２６へ進む。ステップＳ５２６では、
前記ステップＳ５０２と同様に、品質クラス候補の中で最低の品質クラスに相当する空きリソース量をドメイン内に確保できるか否かが判定され、確保できればステップＳ５２７へ進む。ステップＳ５２７では、当該最低の品質クラスが自ドメイン内パスに割り当てられる。
【００３９】
さらに、前記ステップＳ５２６において、品質クラス候補内で最低の品質クラスに相当する空きリソース量をドメイン内に確保できなければステップＳ５２８へ進む。ステップＳ５２８では前記ステップＳ５０４と同様に、品質クラス候補とは無関係に、空きリソース量の範囲内で割当可能な品質クラスの有無が判定され、割当可能な品質クラスがあればステップＳ５２９へ進む。ステップＳ５２９では前記ステップＳ５０５と同様に、割当可能な品質クラスの中で最高の品質クラスが自ドメイン内パスに割り当てられる。
【００４０】
以上のようにして、自ドメイン内パスへの品質クラスの割り当てが完了すると、ステップＳ６では、前記パス設定要求が更新され、前記自ドメイン内パスに割り当てた品質クラスが追加登録される。ステップＳ７では、更新されたパス設定要求が下流側のドメインへ転送される。その後、前記自ドメイン内パスに割り当てた品質クラスに基づいてドメイン内でルート探索が実行され、前記品質クラスを満足する自ドメイン内パスがドメイン内に確立される。
【００４１】
なお、下流側の各ドメインでも同等に、下流ドメイン数N’および品質値Q’に基づいて自ドメイン内パスが順次に選択される。
【図面の簡単な説明】
【００４２】
【図１】本発明が適用されるドメイン間ネットワークの構成を模式的に表現した図である。
【図２】本実施形態における品質クラス割当方法の手順を示したフローチャートである。
【図３】品質クラス候補の算出手順を示したフローチャートである。
【図４】数理モデルの解の一例を示した図である。
【図５】ポリシサーバPSに保持される品質クラス候補割当情報の一例を示した図である。
【図６】第１の品質クラス決定方法の手順を示したフローチャートである。
【図７】第２の品質クラス決定方法の手順を示したフローチャートである。
【図８】第３の品質クラス決定方法の手順を示したフローチャートである。
【符号の説明】
【００４３】
A，B，C，D…ドメイン
a，d…エンドノード
PS…ポリシサーバ
BR…ボーダルータ
【図１】
2008017005.tif 000006
【図２】
2008017005.tif 000007
【図３】
2008017005.tif 000008
【図４】
2008017005.tif 000009
【図５】
2008017005.tif 000010
【図６】
2008017005.tif 000011
【図７】
2008017005.tif 000012
【図８】
2008017005.tif 000013