遅延時間推定方法、リンク容量設計方法、目標遅延時間判定方法およびその装置
【課題】 パケット転送にかかる遅延時間に関する分布のα・１００パーセント点となる遅延時間を推定する遅延時間推定方法、リンク容量設計方法、目標遅延時間判定方法およびその装置を提供する。
【解決手段】 ホストＡ・１は複数の試験パケットを送信し、ホストＢ・５が各々の試験パケットについて遅延時間を測定する。また、各ノード（ルータＡ・２、ルータＢ・３、ルータＣ・４）では隣接するリンクの利用率を測定する。遅延時間分析装置６は、ネットワークを介してホストＢ・５や各ノードより遅延時間やリンク利用率のデータを取得し、α・１００パーセント点となる遅延時間を推定する。
【解決手段】 ホストＡ・１は複数の試験パケットを送信し、ホストＢ・５が各々の試験パケットについて遅延時間を測定する。また、各ノード（ルータＡ・２、ルータＢ・３、ルータＣ・４）では隣接するリンクの利用率を測定する。遅延時間分析装置６は、ネットワークを介してホストＢ・５や各ノードより遅延時間やリンク利用率のデータを取得し、α・１００パーセント点となる遅延時間を推定する。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明は、パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定方法、リンク容量設計方法、目標遅延時間判定方法およびその装置に関するものである。
【０００２】
【従来の技術】従来、個々のパケットの遅延時間を測定する方法としては片側遅延測定法や、Ｐｉｎｇあるいは遅延測定法などの往復遅延時間を測定する方法がある。これら個々のパケットに関する測定値から、片側遅延時間あるいは往復遅延時間の分布のα・１００パーセント点となる遅延時間を推定する為には、度数分布を求め、その度数分布よりα・１００パーセント点となる遅延時間を推定する。具体的には、以下のような手順で推定する。まず、ｎ個の独立な遅延時間を測定する。次に、それらｎ個の測定値を降順に並べ替え、上位のα・ｎ番目（α・ｎが整数でない場合にはα・ｎに最も近い整数）番目となる遅延時間をα・１００パーセント点となる遅延時間と推定していた。
【０００３】また、従来のリンク容量設計方法としては、ＡＴＭ（非同期転送モード）ネットワークのセル損失率を目標値以下に抑えることを目標として、リンク容量を設計する方法がある。例えば、特願平１１−２４３３９８では、入力トラヒックモデルを仮定することなく、ＡＴＭ交換機内のバッファへの到着セル数のみを測定することにより、リンク容量を設計する方法が開示されている。更に説明すると、特定のＡＴＭ仮想パスに注目し、そのパスに付随するセル送出待ちバッファへの到着セル数を計数し、単位時間当たりの到着セル数の閾値と予め設定された測定時間Ｔおよびその整数ｋ倍であるｋＴとの積の値より、計測された到着セル数を超える頻度を算出することによって、ＡＴＭ仮想パスに付随するセル送出待ちバッファにおけるセル損失を効率よく推定し、実トラヒック需要に即したＡＴＭ仮想パスのリンク容量を算出する方法である。
【０００４】また、従来の目標遅延時間判定方法としては、特願２０００−０６１２２９において、実際のネットワークに高負荷をかけることによって、目標遅延時間を達成できていない場合のリンク利用率の値を求め、そのリンク利用率から目標遅延時間判定の閾値を算出し、その閾値をもって目標遅延時間を満足しているか判定する方法が示されている。
【０００５】
【発明が解決しようとする課題】上述したように、従来のパケットの遅延時間を推定する方法では、上位のα・ｎ番目の測定値は直接的に利用しているものの、それ以外の測定値に関しては、α・ｎ番目の測定値より大きいか小さいかといった情報しか用いておらず、必ずしも適切なα・１００パーセント点となる遅延時間を推定できないという問題があった。また、上述した方法で正確な値を推定するには多数の測定データが必要になる問題があった。
【０００６】また、上述した従来のリンク容量設計方法では、ＡＴＭネットワークのリンク容量を設計する場合に、算出した目標リンク容量がセル損失率を目標値以下に抑えることである為、遅延時間に注目したものではなく、遅延時間を考慮したリンク容量設計ではないという問題があった。また、あるリンクを通るパケットについて遅延時間の管理ができていないという問題があった。また、上述した従来の目標遅延時間判定方法では、実際のネットワークにおいて高負荷をかける必要があり、運用中のネットワークにおいては実用的ではないという問題があった。
【０００７】この発明は、上述した事情を考慮してなされたもので、パケット転送にかかる遅延時間に関する分布のα・１００パーセント点となる遅延時間を推定する遅延時間推定方法、リンク容量設計方法、目標遅延時間判定方法およびその装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】この発明は、上述した課題を解決すべくなされたもので、本発明による遅延時間推定方法においては、パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定方法であって、ｎ個の片側遅延時間あるいは往復遅延時間を測定し、それらを遅延時間に関して降順に並べ替えたものをｗi（ｉ＝１、２、…、ｎ）とし、定数ｓ（ｓ≧０）を用いて、各遅延時間ｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）と変形し、ｗi*に関する関数ｆ（ｗi*）をｆ（ｗi*）＝ｉ／ｎとして推定し、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）とみなしてｌｏｇＰｒ（Ｗ* ≧ｘ）＝δｘ＋β … （式１）
なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを推定し、得られた分布Ｐｒ（Ｗ* ≧ｘ）より、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間をｘ*＋ｓと推定することを特徴とする。
【０００９】これにより、測定された全ての遅延時間データの値を用いて、遅延時間分布の減衰率δ、切片定数ベータを推定している。遅延時間分布が、近似的に（式１）に従うことは、例えばＧ．Ｌ．Ｃｈｏｕｄｈｕｒｙ ａｎｄ Ｗ．Ｗｈｉｔｔによる「Ｈｅａｖｙ−ｔｒａｆｆｉｃ Ａｓｙｍｐｔｏｔｉｃ Ｅｘｐａｎｓｉｏｎｓ ｆｏｒ ｔｈｅ ａｓｙｍｐｔｏｔｉｃ Ｄｅｃａｙ Ｒａｔｅｓ ｉｎｔｈｅ ＢＭＡＰ／Ｇ／１ Ｑｕｅｕｅ」Ｃｏｍｍｕｎ．Ｓｔａｔｉｓｔ．−Ｓｔｏｃｈａｓｔｉｃ Ｍｏｄｅｌｓ，１０（２），ｐｐ．４５３−４９８（１９９４）に述べられている。本発明では、従来の方法に比べて少ない測定データ数でα・１００パーセント点の遅延時間を推定できるので、推定のための労力を減らすことができる。このことは、特にαの値が大きい場合（例えば０．９５や０．９９）により有効である。また、上述した式中の定数ｓは、ルータやスイッチバッファ内での待ち時間以外の処理にかかる時間を用いればよく、例えば、測定されたｗiの最小値を用いることによって、（式１）の精度を上げることができる。
【００１０】また、本発明によるリンク容量設計方法においては、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρ）／（ρδ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量ＣdemをＣdem＝Ｃ・ρ（１＋（ｄ2／（ｄ1−ｘ*obj））ｌｏｇ（１−α））…（式２）
によって算出することを特徴とする。
【００１１】これにより、入力トラヒックモデルを仮定することなく、遅延時間とリンク利用率のみを測定することにより、リンク容量を設計できる。上述した（式２）は、Ｓｈｉｏｄａ，Ｔｏｙｏｉｚｕｍｉ，Ｔｓｕｃｈｉｙａ，Ｓａｉｔｏ，「Ｓｅｌｆ−ｓｉｚｉｎｇ Ｎｅｔｗｏｒｋ： ａ Ｎｅｗ Ｎｅｔｗｏｒｋ Ｃｏｎｃｅｐｔ ｂａｓｅｄ ｏｎ Ａｕｔｏｎｏｍｏｕｓ ＶＰ ｂａｎｄｗｉｄｔｈ Ａｄｊｕｓｔｍｅｎｔ」Ｐｒｏｃ．ｏｆ ＩＴＣ １５，ｐｐ．９９７−１００６（１９９７）において前提とされる固定長パケット（ＡＴＭセル）を可変長パケットに拡張し、さらにパケット損失率（セル損失率）を遅延時間に置き換えることにより求められる。
【００１２】また、本発明による目標遅延時間判定方法においては、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、リンク利用率閾値をρ*として ρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）…（式３）
と設定し、将来時点において、そのリンク利用率ρが、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定することを特徴とする。
【００１３】これにより、遅延時間測定を定常的に行わなくても、リンク利用率だけを測定していれば、α・１００パーセント点の目標遅延時間を満足しているかの判定を行うことができる。上述した（式３）は、（式２）を変形することにより求めることができる。本発明でにおける目標遅延時間判定方法では、実際のネットワークへ高負荷をかけることなく、判定閾値を算出することができる。すなわち、ネットワーク運用中に閾値を決めることが容易となる。
【００１４】また、本発明における遅延時間推定装置においては、パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定装置であって、請求項１に記載の遅延時間推定方法を実行する遅延時間推定プログラムを記録した記録媒体と、前記遅延時間推定プログラムを実行する演算手段と、測定対象となっている経路の端となる前記ホストより測定した遅延時間データを取得するデータ取得手段とを具備することを特徴とする。
【００１５】また、本発明によるリンク容量設計装置においては、請求項２に記載のリンク容量設計方法を実行するリンク容量設計プログラムを記録した記録媒体と、前記リンク容量設計プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とする。
【００１６】また、本発明による目標遅延時間判定装置においては、請求項３に記載の目標遅延時間判定方法を実行する目標遅延時間判定プログラムを記録した記録媒体と、前記目標遅延時間判定プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とする。
【００１７】
【発明の実施の形態】以下、発明の実施の形態を通じて本発明を説明する。ただし、以下の実施の形態は特許請求の範囲に記載された発明を限定するものではなく、また実施の形態の中で説明されている特徴の組み合わせのすべてが発明の解決手段に必要であるとは限らない。図１R>１はこの発明の一実施形態による遅延時間推定対象となるネットワーク例を示すブロック図である。図に示すようにホストＡ・１とホストＢ・５は、ルータＡ・２、ルータＢ・３、ルータＣ・４を介して通信を行うこととする。ここで、ホストＡ・２からホストＢ・５までの遅延時間を次に示すように測定する。例えば、ホストＡ・１は複数の試験パケットを送信し、ホストＢ・５が各々の試験パケットについて遅延時間を測定する。また、各ノード（ルータＡ・２、ルータＢ・３、ルータＣ・４）では隣接するリンクの利用率を測定する。また、遅延時間分析装置６は、ネットワークを介してホストＢ・５や各ノードより遅延時間やリンク利用率のデータを取得し、分析する。
【００１８】ここで、遅延時間分析装置６は、ホストＢ・５や各ノードから遅延時間やリンク利用率のデータを取得するデータ取得部６ａと、その取得したデータを記憶するデータ記憶部６ｂと、データ記憶部６ｂに記憶されたデータを基に、種々の演算を行う演算部６ｃとから構成される。尚、遅延時間分析装置６は、遅延時間推定装置、リンク容量設計装置、目標遅延時間判定装置のいずれかであり、上述した構成は３つの装置に共通である。遅延時間分析装置６は、演算部６ｃに格納される演算プログラムの違いで、上記の遅延時間推定装置、リンク容量設計装置、目標遅延時間判定装置の内どの装置として動作するかが決まる。
【００１９】尚、上記に示した演算部６ｃに格納される演算プログラムによる各処理部は専用のハードウェアにより実現されるものであってもよく、また、各処理部はメモリおよびＣＰＵ（中央演算装置）により構成され、各処理部の機能を実現する為のプログラムをメモリにロードして実行することによりその機能を実現させるものであってもよい。また、上記メモリは、ハードディスク装置や光磁気ディスク装置、フラッシュメモリ等の不揮発性のメモリや、ＣＤ−ＲＯＭ等の読み出しのみが可能な記録媒体、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）のような揮発性のメモリ、あるいはこれらの組み合わせによるコンピュータ読み取り、書き込み可能な記録媒体より構成されるものとする。
【００２０】次に、遅延時間分析装置６が遅延時間推定装置である場合の実施形態について、遅延時間推定を行う動作フロー図である図２を用いて、遅延時間分析装置６（遅延時間推定装置）の動作を説明する。まず、データ取得部６ａがホストＢ・５において測定されたｎ個の遅延時間についてのデータをネットワーク経由で取得する（ステップＳ１）。同時に、取得された遅延時間データは、データ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得した遅延時間データを読み出し、昇べきの順に並べ替えて、それらをｗi（ｉ＝１、２、…、ｎ）とする（ステップＳ２）。次に、演算部６ｃは、定数ｓ（ｓ≧０）を用いて、各遅延時間データｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）へ変換する（ステップＳ３）。次に、演算部６ｃは、各々のｗi*に関して以下に示す関数ｆ（ｗi*）＝ｉ／ｎへ代入しｆ（ｗi*）の値を算出する（ステップＳ４）。次に、演算部６ｃは、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ*≧ｗi*）とみなして以下に示すｌｏｇＰｒ（Ｗ* ≧ｘ）＝δｘ＋β … （式１）
なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する（ステップＳ５）。次に、演算部６ｃは、ステップＳ５の線形回帰により求められる図３に示す回帰直線からα・１００パーセント点となる遅延時間を算出する（ステップＳ６）。尚、図３R>３に示す例では、α＝０．９９の場合における、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間を推定している。以上により、遅延時間分析装置６は遅延時間推定装置として、ホストＡ・１からホストＢ・５までのパケット移動に要する遅延時間データの分布より、α・１００パーセント点となる遅延時間を算出する。
【００２１】次に、遅延時間分析装置６が、リンク容量設計装置である場合の実施形態について、リンク容量設計を行う動作フロー図である図４を用いて、遅延時間分析装置６（リンク容量設計装置）の動作を説明する。まず、データ取得部６ａが、ホストＢ・５で測定されたｎ個の遅延時間データと、各ノードで測定されたリンク利用率ρのデータを取得する（ステップＳ１１）。同時に、取得されたデータはデータ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得した遅延時間データを読み出し、昇べきの順に並べ替えて、それらをｗi（ｉ＝１、２、…、ｎ）とする（ステップＳ１２）。次に、演算部６ｃは、定数ｓ（ｓ≧０）を用いて、各遅延時間データｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）へ変換する（ステップＳ１３）。次に、演算部６ｃは、各々のｗi*に関して以下に示す関数ｆ（ｗi*）＝ｉ／ｎへ代入しｆ（ｗi*）の値を算出する（ステップＳ１４）。次に、演算部６ｃは、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）と上述した（式１）なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する（ステップＳ１５）。次に、演算部６ｃは、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρｍ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρm）／（ρm・δ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量をＣdemとし以下の近似式Ｃdem＝Ｃ・ρm（１＋（ｄ2／（ｄ1−ｘ*obj））log（１−α））…（式２）
によってリンク容量を算出する（ステップＳ１６）。
【００２２】以上により、遅延時間分析装置６はリンク容量設計装置として、入力トラヒックモデルを仮定することなく、遅延時間とリンク利用率のみを測定することにより、リンク容量を設計することができる。尚、（式２）の変数ｄ1については定数ｒ1（例えばｒ1＝１）に置き換えても良い。また、（式２）の最大の利用率となっているリンクの利用率ρｍ、についても定数ｒ2（例えばｒ2＝１）に置き換えても良い。以上のように（式２）のｄ1、ρｍ等の変数はネットワークの構成や、実測値の分布傾向等を考慮した適当な定数に置き換えて（式２）を簡素化しても良い。
【００２３】次に、遅延時間分析装置６が、目標遅延時間判定装置である場合の実施形態について、目標遅延時間判定を行う動作フロー図である図５を用いて、遅延時間分析装置６（目標遅延時間判定装置）の動作を説明する。目標遅延時間判定を行うには、図５（ａ）に示すリンク利用率の閾値ρ*を算出するフローと、図５（ｂ）に示すリンク利用率の閾値ρ*と実際に測定されるリンク利用率ρを比較し、判定するフローとがある。最初に、図５（ａ）に示すリンク利用率の閾値ρ*を算出するフローの動作について説明する。まず、データ取得部６ａが、ホストＢ・５で測定されたｎ個の遅延時間データと、各ノードで測定されたリンク利用率ρのデータを取得する（ステップＳ２１）。同時に、取得されたデータはデータ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得した遅延時間データを読み出し、昇べきの順に並べ替えて、それらをｗi（ｉ＝１、２、…、ｎ）とする（ステップＳ２２）。次に、演算部６ｃは、定数ｓ（ｓ≧０）を用いて、各遅延時間データｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）へ変換する（ステップＳ２３）。次に、演算部６ｃは、各々のｗi*に関して以下に示す関数ｆ（ｗi*）＝ｉ／ｎへ代入しｆ（ｗi*）の値を算出する（ステップＳ２４）。次に、演算部６ｃは、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）と上述した（式１）なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する（ステップＳ２５）。次に、演算部６ｃは、データ記憶部６ｂよりリンク利用率データを読み出し、リンク利用率閾値をρ*として以下に示す式 ρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）…（式３）
よりリンク利用率の閾値ρ*を算出する（ステップＳ２６）。
【００２４】次に、図５（ｂ）に示すリンク利用率の閾値ρ*と実際に測定されるリンク利用率ρを比較し、判定するフローの動作について説明する。ホストＡ・１やホストＢ・５および各ノードの実動作時において、データ取得部６ａは、各ノード間におけるリンク利用率ρのデータを取得する（ステップＳ３１）。同時に、取得されたデータはデータ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得したリンク利用率データを読み出し、リンク利用率の閾値ρ*と比較を行い、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定する（ステップＳ３２）。
【００２５】以上により、遅延時間測定を定常的に行っていなくても、リンク利用率だけを測定していれば、α・１００パーセント点の目標遅延時間を満足しているかの判定をすることができる。すなわち、遅延時間測定にくらべてリンク利用率の測定は容易であり、リンク利用率だけで判定できることでより簡便にα・１００パーセント点の目標遅延時間を満足しているかの判定をすることができる。尚、リンク利用率の閾値ρ*を算出するフローは、実際にはネットワークの構成が変更された場合等に行われる。また、前記フローで求めたリンク利用率の閾値ρ*と実際に測定されるリンク利用率ρを比較し判定するフローは、実際には定常的に判定が行われる。具体的には、データ取得部６ａが、ボトルネックリンクのリンク利用率を定常的に取得し、演算部６ｃにて判定を行う。また、（式３）の変数ｄ1については定数ｒ3（例えばｒ3＝１）に置き換えても良い。すなわち（式３）のｄ1等の変数はネットワークの構成や、実測値の分布傾向等を考慮した適当な定数に置き換えて（式３）を簡素化しても良い。
【００２６】また、図１における演算部６ｃで各種処理を行う処理部の機能を実現する為のプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各処理を行っても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フロッピー（登録商標）ディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００２７】また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現する為のものであっても良い。さらに、前述した機能をコンピュータシステムに既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００２８】
【発明の効果】以上説明したように本発明による遅延時間推定方法は、まず、ｎ個の片側遅延時間あるいは往復遅延時間を測定する。次に、それらを遅延時間に関して降順に並べ替えたものをｗi（ｉ＝１、２、…、ｎ）とする。次に、定数ｓ（ｓ≧０）を用いて、各遅延時間ｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝と変形し、関数ｆ（ｗi*）＝ｉ／ｎへｗi*を代入して算出する。次に、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）とみなして上記（式１）なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する。次に、得られた分布Ｐｒ（Ｗ* ≧ｘ）より、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間をｘ*＋ｓと推定する。以上により、従来正確なα・１００パーセント点となる遅延時間を得るには多数の測定データが必要であったが、より少ない遅延時間の測定データで正確なα・１００パーセント点を推定することができる。
【００２９】また、本発明によるリンク容量設計方法は、まず、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定する。次に、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρ）／（ρδ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量Ｃdemを次式Ｃdem＝Ｃ・ρ（１＋（ｄ2／（ｄ1−ｘ*obj））ｌｏｇ（１−α））によって算出する。以上により、ホスト間のパケットを転送する経路上でボトルネックとなるリンク容量設計において、α・１００パーセント点となる遅延時間が目標遅延時間を満足するリンク容量を算出することができる。
【００３０】また、本発明による目標遅延時間判定方法は、まず、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定する。次に、リンク利用率閾値をρ*として次式ρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）により、リンク利用率の閾値ρ*を算出する。次に、そのリンク利用率の閾値ρ*を用いて、実際のホスト間にあるパケット転送の経路上におけるリンク利用率ρが、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定する。以上により遅延時間を直接測定することなく、リンク利用率の測定データから遅延時間分布におけるα・１００パーセント点の目標遅延時間を満足しているかの判定を行うことができる。
【図面の簡単な説明】
【図１】 本発明の一実施形態による遅延時間の推定対象となるネットワーク例を示すブロック図である。
【図２】 本発明の実施形態において遅延時間分析装置６が遅延時間推定装置である場合について、遅延時間推定を行う動作フロー図である。
【図３】 本発明の一実施形態による線形回帰により求められる回帰直線を示す図である。
【図４】 本発明の一実施形態による遅延時間分析装置６が、リンク容量設計装置である場合について、リンク容量設計を行う動作フロー図である。
【図５】 本発明の一実施形態による遅延時間分析装置６が、目標遅延時間判定装置である場合について、目標遅延時間判定を行う動作フロー図である。
【符号の説明】
１ ホストＡ
２ ルータＡ
３ ルータＢ
４ ルータＣ
５ ホストＢ
６ 遅延時間分析装置
６ａ データ取得部
６ｂ データ記憶部
６ｃ 演算部
【０００１】
【発明の属する技術分野】この発明は、パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定方法、リンク容量設計方法、目標遅延時間判定方法およびその装置に関するものである。
【０００２】
【従来の技術】従来、個々のパケットの遅延時間を測定する方法としては片側遅延測定法や、Ｐｉｎｇあるいは遅延測定法などの往復遅延時間を測定する方法がある。これら個々のパケットに関する測定値から、片側遅延時間あるいは往復遅延時間の分布のα・１００パーセント点となる遅延時間を推定する為には、度数分布を求め、その度数分布よりα・１００パーセント点となる遅延時間を推定する。具体的には、以下のような手順で推定する。まず、ｎ個の独立な遅延時間を測定する。次に、それらｎ個の測定値を降順に並べ替え、上位のα・ｎ番目（α・ｎが整数でない場合にはα・ｎに最も近い整数）番目となる遅延時間をα・１００パーセント点となる遅延時間と推定していた。
【０００３】また、従来のリンク容量設計方法としては、ＡＴＭ（非同期転送モード）ネットワークのセル損失率を目標値以下に抑えることを目標として、リンク容量を設計する方法がある。例えば、特願平１１−２４３３９８では、入力トラヒックモデルを仮定することなく、ＡＴＭ交換機内のバッファへの到着セル数のみを測定することにより、リンク容量を設計する方法が開示されている。更に説明すると、特定のＡＴＭ仮想パスに注目し、そのパスに付随するセル送出待ちバッファへの到着セル数を計数し、単位時間当たりの到着セル数の閾値と予め設定された測定時間Ｔおよびその整数ｋ倍であるｋＴとの積の値より、計測された到着セル数を超える頻度を算出することによって、ＡＴＭ仮想パスに付随するセル送出待ちバッファにおけるセル損失を効率よく推定し、実トラヒック需要に即したＡＴＭ仮想パスのリンク容量を算出する方法である。
【０００４】また、従来の目標遅延時間判定方法としては、特願２０００−０６１２２９において、実際のネットワークに高負荷をかけることによって、目標遅延時間を達成できていない場合のリンク利用率の値を求め、そのリンク利用率から目標遅延時間判定の閾値を算出し、その閾値をもって目標遅延時間を満足しているか判定する方法が示されている。
【０００５】
【発明が解決しようとする課題】上述したように、従来のパケットの遅延時間を推定する方法では、上位のα・ｎ番目の測定値は直接的に利用しているものの、それ以外の測定値に関しては、α・ｎ番目の測定値より大きいか小さいかといった情報しか用いておらず、必ずしも適切なα・１００パーセント点となる遅延時間を推定できないという問題があった。また、上述した方法で正確な値を推定するには多数の測定データが必要になる問題があった。
【０００６】また、上述した従来のリンク容量設計方法では、ＡＴＭネットワークのリンク容量を設計する場合に、算出した目標リンク容量がセル損失率を目標値以下に抑えることである為、遅延時間に注目したものではなく、遅延時間を考慮したリンク容量設計ではないという問題があった。また、あるリンクを通るパケットについて遅延時間の管理ができていないという問題があった。また、上述した従来の目標遅延時間判定方法では、実際のネットワークにおいて高負荷をかける必要があり、運用中のネットワークにおいては実用的ではないという問題があった。
【０００７】この発明は、上述した事情を考慮してなされたもので、パケット転送にかかる遅延時間に関する分布のα・１００パーセント点となる遅延時間を推定する遅延時間推定方法、リンク容量設計方法、目標遅延時間判定方法およびその装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】この発明は、上述した課題を解決すべくなされたもので、本発明による遅延時間推定方法においては、パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定方法であって、ｎ個の片側遅延時間あるいは往復遅延時間を測定し、それらを遅延時間に関して降順に並べ替えたものをｗi（ｉ＝１、２、…、ｎ）とし、定数ｓ（ｓ≧０）を用いて、各遅延時間ｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）と変形し、ｗi*に関する関数ｆ（ｗi*）をｆ（ｗi*）＝ｉ／ｎとして推定し、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）とみなしてｌｏｇＰｒ（Ｗ* ≧ｘ）＝δｘ＋β … （式１）
なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを推定し、得られた分布Ｐｒ（Ｗ* ≧ｘ）より、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間をｘ*＋ｓと推定することを特徴とする。
【０００９】これにより、測定された全ての遅延時間データの値を用いて、遅延時間分布の減衰率δ、切片定数ベータを推定している。遅延時間分布が、近似的に（式１）に従うことは、例えばＧ．Ｌ．Ｃｈｏｕｄｈｕｒｙ ａｎｄ Ｗ．Ｗｈｉｔｔによる「Ｈｅａｖｙ−ｔｒａｆｆｉｃ Ａｓｙｍｐｔｏｔｉｃ Ｅｘｐａｎｓｉｏｎｓ ｆｏｒ ｔｈｅ ａｓｙｍｐｔｏｔｉｃ Ｄｅｃａｙ Ｒａｔｅｓ ｉｎｔｈｅ ＢＭＡＰ／Ｇ／１ Ｑｕｅｕｅ」Ｃｏｍｍｕｎ．Ｓｔａｔｉｓｔ．−Ｓｔｏｃｈａｓｔｉｃ Ｍｏｄｅｌｓ，１０（２），ｐｐ．４５３−４９８（１９９４）に述べられている。本発明では、従来の方法に比べて少ない測定データ数でα・１００パーセント点の遅延時間を推定できるので、推定のための労力を減らすことができる。このことは、特にαの値が大きい場合（例えば０．９５や０．９９）により有効である。また、上述した式中の定数ｓは、ルータやスイッチバッファ内での待ち時間以外の処理にかかる時間を用いればよく、例えば、測定されたｗiの最小値を用いることによって、（式１）の精度を上げることができる。
【００１０】また、本発明によるリンク容量設計方法においては、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρ）／（ρδ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量ＣdemをＣdem＝Ｃ・ρ（１＋（ｄ2／（ｄ1−ｘ*obj））ｌｏｇ（１−α））…（式２）
によって算出することを特徴とする。
【００１１】これにより、入力トラヒックモデルを仮定することなく、遅延時間とリンク利用率のみを測定することにより、リンク容量を設計できる。上述した（式２）は、Ｓｈｉｏｄａ，Ｔｏｙｏｉｚｕｍｉ，Ｔｓｕｃｈｉｙａ，Ｓａｉｔｏ，「Ｓｅｌｆ−ｓｉｚｉｎｇ Ｎｅｔｗｏｒｋ： ａ Ｎｅｗ Ｎｅｔｗｏｒｋ Ｃｏｎｃｅｐｔ ｂａｓｅｄ ｏｎ Ａｕｔｏｎｏｍｏｕｓ ＶＰ ｂａｎｄｗｉｄｔｈ Ａｄｊｕｓｔｍｅｎｔ」Ｐｒｏｃ．ｏｆ ＩＴＣ １５，ｐｐ．９９７−１００６（１９９７）において前提とされる固定長パケット（ＡＴＭセル）を可変長パケットに拡張し、さらにパケット損失率（セル損失率）を遅延時間に置き換えることにより求められる。
【００１２】また、本発明による目標遅延時間判定方法においては、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、リンク利用率閾値をρ*として ρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）…（式３）
と設定し、将来時点において、そのリンク利用率ρが、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定することを特徴とする。
【００１３】これにより、遅延時間測定を定常的に行わなくても、リンク利用率だけを測定していれば、α・１００パーセント点の目標遅延時間を満足しているかの判定を行うことができる。上述した（式３）は、（式２）を変形することにより求めることができる。本発明でにおける目標遅延時間判定方法では、実際のネットワークへ高負荷をかけることなく、判定閾値を算出することができる。すなわち、ネットワーク運用中に閾値を決めることが容易となる。
【００１４】また、本発明における遅延時間推定装置においては、パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定装置であって、請求項１に記載の遅延時間推定方法を実行する遅延時間推定プログラムを記録した記録媒体と、前記遅延時間推定プログラムを実行する演算手段と、測定対象となっている経路の端となる前記ホストより測定した遅延時間データを取得するデータ取得手段とを具備することを特徴とする。
【００１５】また、本発明によるリンク容量設計装置においては、請求項２に記載のリンク容量設計方法を実行するリンク容量設計プログラムを記録した記録媒体と、前記リンク容量設計プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とする。
【００１６】また、本発明による目標遅延時間判定装置においては、請求項３に記載の目標遅延時間判定方法を実行する目標遅延時間判定プログラムを記録した記録媒体と、前記目標遅延時間判定プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とする。
【００１７】
【発明の実施の形態】以下、発明の実施の形態を通じて本発明を説明する。ただし、以下の実施の形態は特許請求の範囲に記載された発明を限定するものではなく、また実施の形態の中で説明されている特徴の組み合わせのすべてが発明の解決手段に必要であるとは限らない。図１R>１はこの発明の一実施形態による遅延時間推定対象となるネットワーク例を示すブロック図である。図に示すようにホストＡ・１とホストＢ・５は、ルータＡ・２、ルータＢ・３、ルータＣ・４を介して通信を行うこととする。ここで、ホストＡ・２からホストＢ・５までの遅延時間を次に示すように測定する。例えば、ホストＡ・１は複数の試験パケットを送信し、ホストＢ・５が各々の試験パケットについて遅延時間を測定する。また、各ノード（ルータＡ・２、ルータＢ・３、ルータＣ・４）では隣接するリンクの利用率を測定する。また、遅延時間分析装置６は、ネットワークを介してホストＢ・５や各ノードより遅延時間やリンク利用率のデータを取得し、分析する。
【００１８】ここで、遅延時間分析装置６は、ホストＢ・５や各ノードから遅延時間やリンク利用率のデータを取得するデータ取得部６ａと、その取得したデータを記憶するデータ記憶部６ｂと、データ記憶部６ｂに記憶されたデータを基に、種々の演算を行う演算部６ｃとから構成される。尚、遅延時間分析装置６は、遅延時間推定装置、リンク容量設計装置、目標遅延時間判定装置のいずれかであり、上述した構成は３つの装置に共通である。遅延時間分析装置６は、演算部６ｃに格納される演算プログラムの違いで、上記の遅延時間推定装置、リンク容量設計装置、目標遅延時間判定装置の内どの装置として動作するかが決まる。
【００１９】尚、上記に示した演算部６ｃに格納される演算プログラムによる各処理部は専用のハードウェアにより実現されるものであってもよく、また、各処理部はメモリおよびＣＰＵ（中央演算装置）により構成され、各処理部の機能を実現する為のプログラムをメモリにロードして実行することによりその機能を実現させるものであってもよい。また、上記メモリは、ハードディスク装置や光磁気ディスク装置、フラッシュメモリ等の不揮発性のメモリや、ＣＤ−ＲＯＭ等の読み出しのみが可能な記録媒体、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）のような揮発性のメモリ、あるいはこれらの組み合わせによるコンピュータ読み取り、書き込み可能な記録媒体より構成されるものとする。
【００２０】次に、遅延時間分析装置６が遅延時間推定装置である場合の実施形態について、遅延時間推定を行う動作フロー図である図２を用いて、遅延時間分析装置６（遅延時間推定装置）の動作を説明する。まず、データ取得部６ａがホストＢ・５において測定されたｎ個の遅延時間についてのデータをネットワーク経由で取得する（ステップＳ１）。同時に、取得された遅延時間データは、データ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得した遅延時間データを読み出し、昇べきの順に並べ替えて、それらをｗi（ｉ＝１、２、…、ｎ）とする（ステップＳ２）。次に、演算部６ｃは、定数ｓ（ｓ≧０）を用いて、各遅延時間データｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）へ変換する（ステップＳ３）。次に、演算部６ｃは、各々のｗi*に関して以下に示す関数ｆ（ｗi*）＝ｉ／ｎへ代入しｆ（ｗi*）の値を算出する（ステップＳ４）。次に、演算部６ｃは、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ*≧ｗi*）とみなして以下に示すｌｏｇＰｒ（Ｗ* ≧ｘ）＝δｘ＋β … （式１）
なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する（ステップＳ５）。次に、演算部６ｃは、ステップＳ５の線形回帰により求められる図３に示す回帰直線からα・１００パーセント点となる遅延時間を算出する（ステップＳ６）。尚、図３R>３に示す例では、α＝０．９９の場合における、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間を推定している。以上により、遅延時間分析装置６は遅延時間推定装置として、ホストＡ・１からホストＢ・５までのパケット移動に要する遅延時間データの分布より、α・１００パーセント点となる遅延時間を算出する。
【００２１】次に、遅延時間分析装置６が、リンク容量設計装置である場合の実施形態について、リンク容量設計を行う動作フロー図である図４を用いて、遅延時間分析装置６（リンク容量設計装置）の動作を説明する。まず、データ取得部６ａが、ホストＢ・５で測定されたｎ個の遅延時間データと、各ノードで測定されたリンク利用率ρのデータを取得する（ステップＳ１１）。同時に、取得されたデータはデータ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得した遅延時間データを読み出し、昇べきの順に並べ替えて、それらをｗi（ｉ＝１、２、…、ｎ）とする（ステップＳ１２）。次に、演算部６ｃは、定数ｓ（ｓ≧０）を用いて、各遅延時間データｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）へ変換する（ステップＳ１３）。次に、演算部６ｃは、各々のｗi*に関して以下に示す関数ｆ（ｗi*）＝ｉ／ｎへ代入しｆ（ｗi*）の値を算出する（ステップＳ１４）。次に、演算部６ｃは、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）と上述した（式１）なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する（ステップＳ１５）。次に、演算部６ｃは、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρｍ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρm）／（ρm・δ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量をＣdemとし以下の近似式Ｃdem＝Ｃ・ρm（１＋（ｄ2／（ｄ1−ｘ*obj））log（１−α））…（式２）
によってリンク容量を算出する（ステップＳ１６）。
【００２２】以上により、遅延時間分析装置６はリンク容量設計装置として、入力トラヒックモデルを仮定することなく、遅延時間とリンク利用率のみを測定することにより、リンク容量を設計することができる。尚、（式２）の変数ｄ1については定数ｒ1（例えばｒ1＝１）に置き換えても良い。また、（式２）の最大の利用率となっているリンクの利用率ρｍ、についても定数ｒ2（例えばｒ2＝１）に置き換えても良い。以上のように（式２）のｄ1、ρｍ等の変数はネットワークの構成や、実測値の分布傾向等を考慮した適当な定数に置き換えて（式２）を簡素化しても良い。
【００２３】次に、遅延時間分析装置６が、目標遅延時間判定装置である場合の実施形態について、目標遅延時間判定を行う動作フロー図である図５を用いて、遅延時間分析装置６（目標遅延時間判定装置）の動作を説明する。目標遅延時間判定を行うには、図５（ａ）に示すリンク利用率の閾値ρ*を算出するフローと、図５（ｂ）に示すリンク利用率の閾値ρ*と実際に測定されるリンク利用率ρを比較し、判定するフローとがある。最初に、図５（ａ）に示すリンク利用率の閾値ρ*を算出するフローの動作について説明する。まず、データ取得部６ａが、ホストＢ・５で測定されたｎ個の遅延時間データと、各ノードで測定されたリンク利用率ρのデータを取得する（ステップＳ２１）。同時に、取得されたデータはデータ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得した遅延時間データを読み出し、昇べきの順に並べ替えて、それらをｗi（ｉ＝１、２、…、ｎ）とする（ステップＳ２２）。次に、演算部６ｃは、定数ｓ（ｓ≧０）を用いて、各遅延時間データｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）へ変換する（ステップＳ２３）。次に、演算部６ｃは、各々のｗi*に関して以下に示す関数ｆ（ｗi*）＝ｉ／ｎへ代入しｆ（ｗi*）の値を算出する（ステップＳ２４）。次に、演算部６ｃは、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）と上述した（式１）なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する（ステップＳ２５）。次に、演算部６ｃは、データ記憶部６ｂよりリンク利用率データを読み出し、リンク利用率閾値をρ*として以下に示す式 ρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）…（式３）
よりリンク利用率の閾値ρ*を算出する（ステップＳ２６）。
【００２４】次に、図５（ｂ）に示すリンク利用率の閾値ρ*と実際に測定されるリンク利用率ρを比較し、判定するフローの動作について説明する。ホストＡ・１やホストＢ・５および各ノードの実動作時において、データ取得部６ａは、各ノード間におけるリンク利用率ρのデータを取得する（ステップＳ３１）。同時に、取得されたデータはデータ記憶部６ｂへ格納される。次に、演算部６ｃは、データ記憶部６ｂより取得したリンク利用率データを読み出し、リンク利用率の閾値ρ*と比較を行い、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定する（ステップＳ３２）。
【００２５】以上により、遅延時間測定を定常的に行っていなくても、リンク利用率だけを測定していれば、α・１００パーセント点の目標遅延時間を満足しているかの判定をすることができる。すなわち、遅延時間測定にくらべてリンク利用率の測定は容易であり、リンク利用率だけで判定できることでより簡便にα・１００パーセント点の目標遅延時間を満足しているかの判定をすることができる。尚、リンク利用率の閾値ρ*を算出するフローは、実際にはネットワークの構成が変更された場合等に行われる。また、前記フローで求めたリンク利用率の閾値ρ*と実際に測定されるリンク利用率ρを比較し判定するフローは、実際には定常的に判定が行われる。具体的には、データ取得部６ａが、ボトルネックリンクのリンク利用率を定常的に取得し、演算部６ｃにて判定を行う。また、（式３）の変数ｄ1については定数ｒ3（例えばｒ3＝１）に置き換えても良い。すなわち（式３）のｄ1等の変数はネットワークの構成や、実測値の分布傾向等を考慮した適当な定数に置き換えて（式３）を簡素化しても良い。
【００２６】また、図１における演算部６ｃで各種処理を行う処理部の機能を実現する為のプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各処理を行っても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フロッピー（登録商標）ディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００２７】また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現する為のものであっても良い。さらに、前述した機能をコンピュータシステムに既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００２８】
【発明の効果】以上説明したように本発明による遅延時間推定方法は、まず、ｎ個の片側遅延時間あるいは往復遅延時間を測定する。次に、それらを遅延時間に関して降順に並べ替えたものをｗi（ｉ＝１、２、…、ｎ）とする。次に、定数ｓ（ｓ≧０）を用いて、各遅延時間ｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝と変形し、関数ｆ（ｗi*）＝ｉ／ｎへｗi*を代入して算出する。次に、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）とみなして上記（式１）なる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを算出する。次に、得られた分布Ｐｒ（Ｗ* ≧ｘ）より、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間をｘ*＋ｓと推定する。以上により、従来正確なα・１００パーセント点となる遅延時間を得るには多数の測定データが必要であったが、より少ない遅延時間の測定データで正確なα・１００パーセント点を推定することができる。
【００２９】また、本発明によるリンク容量設計方法は、まず、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定する。次に、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρ）／（ρδ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量Ｃdemを次式Ｃdem＝Ｃ・ρ（１＋（ｄ2／（ｄ1−ｘ*obj））ｌｏｇ（１−α））によって算出する。以上により、ホスト間のパケットを転送する経路上でボトルネックとなるリンク容量設計において、α・１００パーセント点となる遅延時間が目標遅延時間を満足するリンク容量を算出することができる。
【００３０】また、本発明による目標遅延時間判定方法は、まず、請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定する。次に、リンク利用率閾値をρ*として次式ρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）により、リンク利用率の閾値ρ*を算出する。次に、そのリンク利用率の閾値ρ*を用いて、実際のホスト間にあるパケット転送の経路上におけるリンク利用率ρが、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定する。以上により遅延時間を直接測定することなく、リンク利用率の測定データから遅延時間分布におけるα・１００パーセント点の目標遅延時間を満足しているかの判定を行うことができる。
【図面の簡単な説明】
【図１】 本発明の一実施形態による遅延時間の推定対象となるネットワーク例を示すブロック図である。
【図２】 本発明の実施形態において遅延時間分析装置６が遅延時間推定装置である場合について、遅延時間推定を行う動作フロー図である。
【図３】 本発明の一実施形態による線形回帰により求められる回帰直線を示す図である。
【図４】 本発明の一実施形態による遅延時間分析装置６が、リンク容量設計装置である場合について、リンク容量設計を行う動作フロー図である。
【図５】 本発明の一実施形態による遅延時間分析装置６が、目標遅延時間判定装置である場合について、目標遅延時間判定を行う動作フロー図である。
【符号の説明】
１ ホストＡ
２ ルータＡ
３ ルータＢ
４ ルータＣ
５ ホストＢ
６ 遅延時間分析装置
６ａ データ取得部
６ｂ データ記憶部
６ｃ 演算部
【特許請求の範囲】
【請求項１】 パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定方法において、ｎ個の片側遅延時間あるいは往復遅延時間を測定し、それらを遅延時間に関して降順に並べ替えたものをｗi（ｉ＝１、２、…、ｎ）とし、定数ｓ（ｓ≧０）を用いて、各遅延時間ｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）と変形し、ｗi*に関する関数ｆ（ｗi*）をｆ（ｗi*）＝ｉ／ｎとして推定し、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）とみなしてｌｏｇＰｒ（Ｗ* ≧ｘ）＝δｘ＋βなる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを推定し、得られた分布Ｐｒ（Ｗ* ≧ｘ）より、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間をｘ*＋ｓと推定することを特徴とする遅延時間推定方法。
【請求項２】 請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρ）／（ρδ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量ＣdemをＣdem＝Ｃ・ρ（１＋（ｄ2／（ｄ1−ｘ*obj））ｌｏｇ（１−α））
によって算出することを特徴とするリンク容量設計方法。
【請求項３】 請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、リンク利用率閾値をρ*としてρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）
と設定し、将来時点において、そのリンク利用率ρが、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定することを特徴とする目標遅延時間判定方法。
【請求項４】 パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定装置において、請求項１に記載の遅延時間推定方法を実行する遅延時間推定プログラムを記録した記録媒体と、前記遅延時間推定プログラムを実行する演算手段と、測定対象となっている経路の端となる前記ホストより測定した遅延時間データを取得するデータ取得手段とを具備することを特徴とする遅延時間推定装置。
【請求項５】 請求項２に記載のリンク容量設計方法を実行するリンク容量設計プログラムを記録した記録媒体と、前記リンク容量設計プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とするリンク容量設計装置。
【請求項６】 請求項３に記載の目標遅延時間判定方法を実行する目標遅延時間判定プログラムを記録した記録媒体と、前記目標遅延時間判定プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とする目標遅延時間判定装置。
【請求項１】 パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定方法において、ｎ個の片側遅延時間あるいは往復遅延時間を測定し、それらを遅延時間に関して降順に並べ替えたものをｗi（ｉ＝１、２、…、ｎ）とし、定数ｓ（ｓ≧０）を用いて、各遅延時間ｗiをｗi*＝ｍａｘ｛ｗi−ｓ，０｝（ただしｍａｘ｛ａ，ｂ｝はａかｂの大きい方を表わす）と変形し、ｗi*に関する関数ｆ（ｗi*）をｆ（ｗi*）＝ｉ／ｎとして推定し、遅延時間Ｗ*がｗi*以上である確率Ｐｒ（Ｗ* ≧ｗi*）を、ｆ（ｗi*）＝Ｐｒ（Ｗ* ≧ｗi*）とみなしてｌｏｇＰｒ（Ｗ* ≧ｘ）＝δｘ＋βなる関数に線形回帰させることによって、遅延時間分布の減衰率δ、切片定数βを推定し、得られた分布Ｐｒ（Ｗ* ≧ｘ）より、Ｐｒ（Ｗ*≧ｘ*）＝１−αとなるｘ*を算出し、α・１００パーセント点となる遅延時間をｘ*＋ｓと推定することを特徴とする遅延時間推定方法。
【請求項２】 請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、最大の利用率となっているリンクの測定時点でのリンク容量をＣ、最大の利用率となっているリンクの現在の利用率をρ、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘobjを用いてｘ*obj＝ｍａｘ｛ｘobj−ｓ，０｝によって算出されるｘ*obj、ｄ2＝（１−ρ）／（ρδ）で算出されるｄ2、ｄ1＝β／δで算出されるｄ1、より最大の利用率となっているリンクの理想リンク容量ＣdemをＣdem＝Ｃ・ρ（１＋（ｄ2／（ｄ1−ｘ*obj））ｌｏｇ（１−α））
によって算出することを特徴とするリンク容量設計方法。
【請求項３】 請求項１における遅延時間分布の減衰率δ、切片定数βを推定し、請求項１の遅延時間測定方法で遅延時間を測定すると同時に、測定対象となっている経路上の各リンクの利用率を測定し、リンク利用率閾値をρ*としてρ*＝（ｄ1−ｘ*obj）／（ｄ2ｌｏｇ（１−α）＋ｄ1−ｘ*obj）
と設定し、将来時点において、そのリンク利用率ρが、ρ＞ρ*となる場合は、遅延時間分布におけるα・１００パーセント点の目標遅延時間ｘ*objを満足できないと判定することを特徴とする目標遅延時間判定方法。
【請求項４】 パケット通信ネットワーク上での任意のノード間、あるいはノードとホスト間、あるいはホストとホスト間における経路上でのパケット転送に要する片側遅延時間あるいは往復遅延時間に関する分布のα・１００パーセント点（０≦α≦１）となる片道遅延時間あるいは往復遅延時間を推定する遅延時間推定装置において、請求項１に記載の遅延時間推定方法を実行する遅延時間推定プログラムを記録した記録媒体と、前記遅延時間推定プログラムを実行する演算手段と、測定対象となっている経路の端となる前記ホストより測定した遅延時間データを取得するデータ取得手段とを具備することを特徴とする遅延時間推定装置。
【請求項５】 請求項２に記載のリンク容量設計方法を実行するリンク容量設計プログラムを記録した記録媒体と、前記リンク容量設計プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とするリンク容量設計装置。
【請求項６】 請求項３に記載の目標遅延時間判定方法を実行する目標遅延時間判定プログラムを記録した記録媒体と、前記目標遅延時間判定プログラムを実行する演算手段と、測定対象となっている経路上の各リンクの利用率を測定したデータを取得するデータ取得手段とを具備することを特徴とする目標遅延時間判定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００２−１１８５８６（Ｐ２００２−１１８５８６Ａ）
【公開日】平成１４年４月１９日（２００２．４．１９）
【国際特許分類】
【出願番号】特願２０００−３０６７１２（Ｐ２０００−３０６７１２）
【出願日】平成１２年１０月５日（２０００．１０．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１４年４月１９日（２００２．４．１９）
【国際特許分類】
【出願日】平成１２年１０月５日（２０００．１０．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]