(57)【要約】【課題】ＥＣＮをサポートしているネットワークでパーフェクトシミュレーションを行っても統計的な偏りを排除可能なネットワーク性能評価方法及びネットワーク性能評価装置を提供することを目的とする。【解決手段】本発明に係るネットワーク性能評価方法及びネットワーク性能評価装置は、中間状態からのシミュレーション系列が最大状態と最小状態からのシミュレーション系列に挟まれた領域を外れる場合、当該シミュレーション系列を新たな上界又は下界としてシミュレーションを続けることとした。【選択図】図６
2019029976.tif 000002
【特許請求の範囲】
【請求項１】
ＥＣＮ（Ｅｘｐｌｉｃｉｔ  Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ）をサポートするネットワークを性能を評価するネットワーク性能評価方法であって、
前記ネットワークに含まれる全てのキューのキュー長の組み合わせで前記ネットワークが取り得る各々のネットワーク状態を表現し、初期として、全ての前記ネットワーク状態のうち、全ての前記キューのキュー長が最大となる最大状態を上界、全ての前記キューのキュー長が最小となる最小状態を下界とする開始手順と、
残存するネットワーク状態の上界と下界を見出し、見出した上界のネットワーク状態と下界のネットワーク状態に対して、同じ乱数を用いた状態遷移関数で状態遷移させるパーフェクトシミュレーションを実行する更新手順と、
前記更新手順後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約していない場合は前記更新手順を繰り返し、前記更新手順後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約している場合は１つに集約したネットワーク状態を状態サンプルとして取得する判定手順と、
を行うことを特徴とするネットワーク性能評価方法。
【請求項２】
前記更新手順では、
残存するネットワーク状態の上界と下界を見出すときに、
前記ＥＣＮによる送信元の送出レートを変更するキューとキュー長から成る基準が設定され、
前記上界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第１推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、大きい方のネットワーク状態を新たな上界とし、
前記下界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第２推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、小さい方のネットワーク状態を新たな下界とする
ことを特徴とする請求項１に記載のネットワーク性能評価方法。
【請求項３】
ＥＣＮをサポートするネットワークを性能を評価するネットワーク性能評価装置であって、
前記ネットワークに含まれる全てのキューのキュー長の組み合わせで前記ネットワークが取り得る各々のネットワーク状態を表現し、初期として、全ての前記ネットワーク状態のうち、全ての前記キューのキュー長が最大となる最大状態を上界、全ての前記キューのキュー長が最小となる最小状態を下界とする状態遷移図と、
前記状態遷移図に残存するネットワーク状態の上界と下界を見出し、見出した上界のネットワーク状態と下界のネットワーク状態に対して、同じ乱数を用いた状態遷移関数で状態遷移させるパーフェクトシミュレーションを実行する更新部と、
前記更新部が実行したパーフェクトシミュレーション後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約していない場合は前記パーフェクトシミュレーションを繰り返し、前記更新部が実行したパーフェクトシミュレーション後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約している場合は１つに集約したネットワーク状態を状態サンプルとして取得する判定部と、
を備えることを特徴とするネットワーク性能評価装置。
【請求項４】
前記更新部は、
残存するネットワーク状態の上界と下界を見出すときに、
前記ＥＣＮによる送信元の送出レートを変更するキューとキュー長から成る基準が設定され、
前記上界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第１推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、大きい方のネットワーク状態を新たな上界とし、
前記下界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第２推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、小さい方のネットワーク状態を新たな下界とする
ことを特徴とする請求項３に記載のネットワーク性能評価装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ネットワーク性能評価のための数値シミュレーションに関する。
【背景技術】
【０００２】
ネットワーク状態の定常分布を高精度に推定するために、パーフェクトシミュレーションと呼ばれる技術が存在する（例えば、非特許文献１を参照。）。まず、パーフェクトシミュレーションについて説明する。
【０００３】
［１］ネットワークモデル
ここでは、図１のようにＮ個のキューを直列につないだネットワークを考える（図１ではＮ＝２）。フローは一本のみとし、送信元の送出レートをｒ０とする。キューｊ∈｛１，・・・，Ｎ｝の転送レートをｒｊ、最大キュー長をＱｊ、パケット数（キュー長）をｑｊとする。
【０００４】
このネットワークの状態ｓは、キュー長の組合せ（ベクトル）によって
ｓ＝（ｑ１，ｑ２，・・・，ｑＮ）
と表される。便宜上、送信元のｉｎｄｅｘを０で表し、宛先をＮ＋１で表す。送信元のキューには常にパケットがあると考え、ｑ０＝∞とする。また、宛先の最大キュー長は無限大とし、ＱＮ＋１＝∞とする。
状態ｓにおけるキューｊのキュー長を、
ｓ．ｑｊ
のように表すこととする。
【０００５】
キューｊからキューｊ＋１へのイベントをＥｊ→ｊ＋１と表記する。イベントＥｊ→ｊ＋１が発生すると、そのときのキューの状態によって次ステップのキュー長は以下のように変化する。
Ａ．キューｊに移動させるパケットが存在しない場合
【数Ａ】
2019029976.tif 000003
Ｂ．キューｊからキューｊ＋１にパケットが移動する場合
【数Ｂ】
2019029976.tif 000004
Ｃ．キューｊ＋１が一杯なので、送信を待つ場合（ｌｉｎｋ−ｌｅｖｅｌ  ｂａｃｋ−ｐｒｅｓｓｕｒｅをかけるネットワークを想定する。）
【数Ｃ】
2019029976.tif 000005
【０００６】
図２は状態遷移を説明する例である。図２の例ではＮ＝２である。図２において符号２１−０〜２１−８が各状態ｓであり、それぞれの状態がｓ＝（ｑ１，ｑ２）で表されている。例えば、符号２１−０は状態ｓ＝（０，０）でキュー１にもキュー２にもパケットが存在しないことを意味する。
【０００７】
図２において実線はイベントＥ０→１（送信元からキュー１へ１つのパケットを転送する）、点線はイベントＥ１→２（キュー１からキュー２へ１つのパケットを転送する）、破線はイベントＥ２→３（キュー２から宛先へ１つのパケットを転送する）である。例えば、遷移（ｉ）は、ｓ＝（０，０）の状態においてイベントＥ０→１で送信元からキュー１へパケットが転送されるときの状態遷移である。遷移（ｉｉ）は、ｓ＝（１，０）の状態においてイベントＥ１→２でキュー１からキュー２へパケットが転送されるときの状態遷移である。遷移（ｉｉｉ）は、ｓ＝（０，１）の状態においてイベントＥ２→３でキュー２から宛先へパケットが転送されるときの状態遷移である（イベント終了後各キューは空となる。）。また、キューが最大キュー長のときは、数Ｃのように当該キューへのパケット転送のイベントが発生しても状態は変わらない。
【０００８】
ここで、イベントの発生確率について定義する。イベントＥｊ→ｊ＋１の発生確率ｐｊ→ｊ＋１は次式で表される。
【数１】
2019029976.tif 000006
【０００９】
［２］パーフェクトシミュレーション
システムが取り得る状態の集合をＳとする。状態遷移は既知であり、既約（ｉｒｒｅｄｕｃｉｂｌｅ）かつ非周期的（ａｐｅｒｉｏｄｉｃ）であるとする。パーフェクトシミュレーションでは、すべての状態から並行してシミュレーションを開始する状況を想定する。また、いずれの状態から開始した場合でも、各ステップで同じ乱数を用いる。ステップｉでの状態をｓｉ、次の遷移を決めるために用いる乱数をρｉ∈［０，１］とし、状態遷移関数Ｔ：Ｓ×［０，１］→Ｓを次のように定義する。
【数２】
2019029976.tif 000007
なお、次式以降ρｉの表記を省略する。
【００１０】
同じ乱数を用いることから、一度、同じ状態に合流したシミュレーション系列は、その後、まったく同じ状態系列をたどることになる。ステップが進むごとに到達可能な状態が減るため、ステップｉで到達可能な状態の集合を
Ｓｉ＝Ｔｉ（Ｓ）＝｛Ｔｉ（ｓ）：ｓ∈Ｓ｝
とすると、次式が成り立つ。
【数３】
2019029976.tif 000008
【００１１】
また、図３のように、任意の状態から開始したシミュレーション系列は、いずれひとつの状態に「合体」する。
【数４】
2019029976.tif 000009
【００１２】
この状況では、各シミュレーションが無限の過去に開始され、一つの状態に合体したと考えることができる。なぜなら、０番目のステップを「全状態」から開始することで、どのようなシミュレーション系列も包含するからである。無限の過去からのシミュレーションだと考えれば、ステップ数の有限性に起因する統計的な偏りを排除できる。なお、合体後の系列であれば、どの状態をサンプルしてもよい。
【００１３】
以上のように、パーフェクトシミュレーションとは、統計的な偏りなしに、一つのサンプルを得る方法である。通常は、乱数列を変えて何度もシミュレーションを実行し、いくつものサンプルを得る。そして、定常分布確率などを計算する。
【００１４】
ネットワークが取り得る状態は非常に多いため、全状態からシミュレーションを行うのは非効率である。非特許文献１などにより、図１のネットワークモデルでは、以下の最大状態（数５；全てのキューが満状態）と最小状態（数６；全てのキューが空状態）からのシミュレーション系列のみを考慮すれば十分であることが示されている。
【数５】
2019029976.tif 000010
【数６】
2019029976.tif 000011
【００１５】
なぜなら、他の状態からのシミュレーション系列は、ステップ０における最大状態からのシミュレーション系列と最小状態からのシミュレーション系列に挟まれた領域から外れないため、上下界より先に合体してしまうからである。図３で説明すると他の状態（中間状態）の系列３Ｘ（白丸）は、上界の系列３９（黒丸）と下界の系列３１（黒四角）に挟まれた領域内でのみ状態遷移を行い、上界の系列３９と下界の系列３１より先に合体する。なお、数５と数６から開始するシミュレーション系列を上界それぞれ下界と呼んでいる。
【００１６】
図４は、上下界系列のみを追跡することで効率化したパーフェクトシミュレーションを説明するフローチャートである。ステップＳ１１でステップｉ＝０（初期）の最大状態と最小状態をシミュレートする。ステップＳ１２で同じ状態遷移関数Ｔを用いて遷移先の状態をシミュレートする。その結果、最大状態と最小状態が一致するか否かを判断する（ステップＳ１３）。最大状態と最小状態が一致していなければステップＳ１２とＳ１３を繰り返す。最大状態と最小状態が一致すれば、一致した状態をネットワーク状態の正常分布とする（ステップＳ１４）。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Ａ．  Ｂｕｓｉｃ，  Ｂ．  Ｇａｕｊａｌ，  ａｎｄ  Ｊ．Ｍ．  Ｖｉｎｃｅｎｔ．  Ｐｅｒｆｅｃｔ  ｓｉｍｕｌａｔｉｏｎ  ａｎｄ  ｎｏｎ−ｍｏｎｏｔｏｎｅ  ｍａｒｋｏｖｉａｎ  ｓｙｓｔｅｍｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＶａｌｕｅＴｏｏｌｓ，  ｐａｇｅｓ  １−１０．  ＩＣＳＴ，２００８．
【非特許文献２】Ｓ．  Ｆｌｏｙｄ．  “ＴＣＰ  ａｎｄ  ｅｘｐｌｉｃｉｔ  ｃｏｎｇｅｓｔｉｏｎ  ｎｏｔｉｆｉｃａｔｉｏｎ”．  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔ．  Ｃｏｍｍｕｎ．  Ｒｅｖ．，２４（５）：８−２３，１９９４．
【非特許文献３】Ｊ．  Ｒ．  Ｓａｎｔｏｓ，  Ｙ．  Ｔｕｒｎｅｒ，  ａｎｄ  Ｇ．  Ｊａｎａｋｉｒａｍａｎ．  “Ｅｎｄ−ｔｏ−ｅｎｄ  ｃｏｎｇｅｓｔｉｏｎ  ｃｏｎｔｒｏｌ  ｆｏｒ  ＩｎｆｉｎｉＢａｎｄ”．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＩＥＥＥ  ＩＮＦＯＣＯＭ，  ｖｏｌｕｍｅ  ２，  ｐａｇｅｓ  １１２３−１１３３，２００３
【発明の概要】
【発明が解決しようとする課題】
【００１８】
［３］送出レート変更における課題
ここで、シミュレーション対象のネットワークがＥＣＮ（Ｅｘｐｌｉｃｉｔ  Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ；非特許文献２、３を参照。）をサポートしている場合を考える。ＥＣＮは、ルータなどの通信機器から送信元へ送出レート抑制を指示することで、ネットワークの輻輳を事前に回避する技術である。
【００１９】
ＥＣＮにより次のように送出レート変更をするとする。あるキューｍ（０＜ｍ≦Ｎ）の状態がｑｍ≧θ（０＜θ≦Ｑｍ）であれば、送信元の送出レートｒ０をｒ∧０（０＜ｒ∧０＜ｒ０）に変更する。なお、キューｍから送信元への通知遅延は無視し、ｑｍの状態が送出レートに瞬時に反映されると仮定する。
【００２０】
ここで、送出レート変更後のイベント発生確率ｐ∧ｊ→ｊ＋１は以下のようになる。
【数７】
2019029976.tif 000012
つまり、状態によってイベント発生率が異なる。
【００２１】
状態によってイベント発生率が異なる場合、ステップ０での最大状態及び最小状態からのシミュレーション系列のみの検討では不十分である。なぜなら、図５のように中間状態からのシミュレーション系列３Xが、最大状態からのシミュレーション系列３９と最小状態からのシミュレーション系列３１に挟まれた領域を外れることがあるからである。つまり、状態によってイベント発生率が異なる場合、最大状態及び最小状態からのシミュレーション系列が、すべての状態のシミュレーション系列に対する上下界にならない。従って、中間状態からのシミュレーション系列がまだ合体していないのに、最大状態と最小状態からのシミュレーション系列が合体した状態をサンプルすることになる。
【００２２】
つまり、ＥＣＮをサポートしているネットワークにパーフェクトシミュレーションを行う場合、統計的な偏りを排除することが困難という課題がある。そこで、本発明は、上記課題を解決するために、ＥＣＮをサポートしているネットワークでパーフェクトシミュレーションを行っても統計的な偏りを排除可能なネットワーク性能評価方法及びネットワーク性能評価装置を提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記目的を達成するために、本発明に係るネットワーク性能評価方法及びネットワーク性能評価装置は、中間状態からのシミュレーション系列が最大状態と最小状態からのシミュレーション系列に挟まれた領域を外れる場合、当該シミュレーション系列を新たな上界又は下界としてシミュレーションを続けることとした。
【００２４】
具体的には、本発明に係るネットワーク性能評価方法は、ＥＣＮ（Ｅｘｐｌｉｃｉｔ  Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ）をサポートするネットワークを性能を評価するネットワーク性能評価方法であって、
前記ネットワークに含まれる全てのキューのキュー長の組み合わせで前記ネットワークが取り得る各々のネットワーク状態を表現し、初期として、全ての前記ネットワーク状態のうち、全ての前記キューのキュー長が最大となる最大状態を上界、全ての前記キューのキュー長が最小となる最小状態を下界とする開始手順と、
残存するネットワーク状態の上界と下界を見出し、見出した上界のネットワーク状態と下界のネットワーク状態に対して、同じ乱数を用いた状態遷移関数で状態遷移させるパーフェクトシミュレーションを実行する更新手順と、
前記更新手順後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約していない場合は前記更新手順を繰り返し、前記更新手順後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約している場合は１つに集約したネットワーク状態を状態サンプルとして取得する判定手順と、
を行うことを特徴とする。
【００２５】
また、本発明に係るネットワーク性能評価装置は、ＥＣＮをサポートするネットワークを性能を評価するネットワーク性能評価装置であって、
前記ネットワークに含まれる全てのキューのキュー長の組み合わせで前記ネットワークが取り得る各々のネットワーク状態を表現し、初期として、全ての前記ネットワーク状態のうち、全ての前記キューのキュー長が最大となる最大状態を上界、全ての前記キューのキュー長が最小となる最小状態を下界とする状態遷移図と、
前記状態遷移図に残存するネットワーク状態の上界と下界を見出し、見出した上界のネットワーク状態と下界のネットワーク状態に対して、同じ乱数を用いた状態遷移関数で状態遷移させるパーフェクトシミュレーションを実行する更新部と、
前記更新部が実行したパーフェクトシミュレーション後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約していない場合は前記パーフェクトシミュレーションを繰り返し、前記更新部が実行したパーフェクトシミュレーション後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約している場合は１つに集約したネットワーク状態を状態サンプルとして取得する判定部と、
を備えることを特徴とする。
【００２６】
常に最大状態を上界と最小状態を下界とすることができるので送信元の送出レートが変更されて状態によってイベントの発生率が異なるようになっても統計的な偏りを排除可能である。従って、本発明は、ＥＣＮをサポートしているネットワークでパーフェクトシミュレーションを行っても統計的な偏りを排除可能なネットワーク性能評価方法及びネットワーク性能評価装置を提供することができる。
【００２７】
ネットワーク状態の上界と下界を次のように見つけることができる。
具体的には、本発明では、残存するネットワーク状態の上界と下界を見出すときに、
前記ＥＣＮによる送信元の送出レートを変更するキューとキュー長から成る基準が設定され、
前記上界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第１推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、大きい方のネットワーク状態を新たな上界とし、
前記下界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第２推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、小さい方のネットワーク状態を新たな下界とする
ことを特徴とする。
【発明の効果】
【００２８】
本発明は、ＥＣＮをサポートしているネットワークでパーフェクトシミュレーションを行っても統計的な偏りを排除可能なネットワーク性能評価方法及びネットワーク性能評価装置を提供することができる。
【図面の簡単な説明】
【００２９】
【図１】ネットワークモデルを説明する図である。
【図２】ネットワークモデルにおける状態遷移を説明する図である。
【図３】パーフェクトシミュレーションによる状態の系列遷移を説明する図である。
【図４】パーフェクトシミュレーションを説明するフローチャートである。
【図５】パーフェクトシミュレーションによる状態の系列遷移を説明する図である。
【図６】本発明に係るネットワーク性能評価方法での状態遷移を説明する図である。
【図７】本発明に係るネットワーク性能評価方法を説明するフローチャートである。
【図８】本発明に係るネットワーク性能評価装置を説明する構成図である。
【図９】ネットワークモデルにおける状態遷移を説明する図である。
【発明を実施するための形態】
【００３０】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００３１】
図６は、本実施形態のネットワーク性能評価方法の概念を説明する状態遷移図である。最大状態からのシミュレーション系列３９と最小状態からのシミュレーション系列３１に挟まれた領域を外れる中間状態からのシミュレーション系列３Xがあれば、系列３Xを新たな上界又は下界としてパーフェクトシミュレーションを続ける。
【００３２】
ここで、最大状態からのシミュレーション系列３９と最小状態からのシミュレーション系列３１に挟まれた領域を外れる系列３Xを見つけるために全状態からシミュレーションを行うのは非効率である。そこで、下記の計算を行うことで当該領域を外れる系列を見つけることとする。
【数８】
2019029976.tif 000013
数８は中間領域の状態の中で上界を超える系列があればそれを上界とすることを意味する。
【数９】
2019029976.tif 000014
数９は中間領域の状態の中で下界を下回る系列があればそれを下界とすることを意味する。
【００３３】
ここで、ｓｕｐ演算は集合を引数とし、以下のようにして全要素の「上界」を計算する。
【数１０】
2019029976.tif 000015
また、ｉｎｆ演算も同様に「下界」を計算する。
【数１１】
2019029976.tif 000016
つまり、各ステップｉにて数８及び数９に従って上下界を更新し、それらが合体したときの状態をサンプルすればよい。
【００３４】
図７は、本実施形態のネットワーク性能評価方法を説明するフローチャートである。
本ネットワーク性能評価方法は、ＥＣＮをサポートするネットワークを性能を評価するネットワーク性能評価方法であって、
前記ネットワークに含まれる全てのキューのキュー長の組み合わせで前記ネットワークが取り得る各々のネットワーク状態を表現し、初期として、全ての前記ネットワーク状態のうち、全ての前記キューのキュー長が最大となる最大状態を上界、全ての前記キューのキュー長が最小となる最小状態を下界とする開始手順Ｓ３１と、
残存するネットワーク状態の上界と下界を見出し、見出した上界のネットワーク状態と下界のネットワーク状態に対して、同じ乱数を用いた状態遷移関数で状態遷移させるパーフェクトシミュレーションを実行する更新手順Ｓ３２と、
更新手順Ｓ３２後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約していない場合は前記更新手順を繰り返し、更新手順Ｓ３２後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約している場合は１つに集約したネットワーク状態を状態サンプルとして取得する判定手順（Ｓ３３、Ｓ３４）と、
を行うことを特徴とする。
【００３５】
特に、更新手順Ｓ３２では、
残存するネットワーク状態の上界と下界を見出すときに、
前記ＥＣＮによる送信元の送出レートを変更するキューとキュー長から成る基準が設定され、
前記上界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第１推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、大きい方のネットワーク状態を新たな上界とし（数８）、
前記下界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第２推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、小さい方のネットワーク状態を新たな下界とする（数９）
ことを特徴とする。
【００３６】
図８は、本実施形態のネットワーク性能評価装置を説明するブロック図である。
本ネットワーク性能評価装置は、ＥＣＮをサポートするネットワークを性能を評価するネットワーク性能評価装置であって、
前記ネットワークに含まれる全てのキューのキュー長の組み合わせで前記ネットワークが取り得る各々のネットワーク状態を表現し、初期として、全ての前記ネットワーク状態のうち、全ての前記キューのキュー長が最大となる最大状態を上界、全ての前記キューのキュー長が最小となる最小状態を下界とする状態遷移図１１と、
状態遷移図１１に残存するネットワーク状態の上界と下界を見出し、見出した上界のネットワーク状態と下界のネットワーク状態に対して、同じ乱数を用いた状態遷移関数で状態遷移させるパーフェクトシミュレーションを実行する更新部１２と、
更新部１２が実行したパーフェクトシミュレーション後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約していない場合は前記パーフェクトシミュレーションを繰り返し、更新部１２が実行したパーフェクトシミュレーション後の上界のネットワーク状態と下界のネットワーク状態とが１つに集約している場合は１つに集約したネットワーク状態を状態サンプルとして取得する判定部１３と、
を備える。
【００３７】
特に、更新部１２は、
残存するネットワーク状態の上界と下界を見出すときに、
前記ＥＣＮによる送信元の送出レートを変更するキューとキュー長から成る基準が設定され、
前記上界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第１推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、大きい方のネットワーク状態を新たな上界とし（数８）、
前記下界のネットワーク状態と該ネットワーク状態から前記基準のキューのキュー長に基づいて推定した第２推定ネットワーク状態とを前記状態遷移関数で遷移させて比較し、小さい方のネットワーク状態を新たな下界とする（数９）
ことを特徴とする。
【００３８】
（数８と数９についての説明）
ここで、図２の状態遷移図を基に数８と数９についての説明を行う。送出レートがｒ∧０に変更される状態の集合をＳ∧とし、送出レートがｒ０のまま変更されない状態の集合をＳ∨とする。たとえば、送出レート変更の基準となるキューをｍ＝２とし、閾値をθ＝２とすると、Ｓ∧とＳ∨は図９のように分けられる。なお、それらに重複はなく（数１２）、それらの和は全集合である（数１３）。
【数１２】
2019029976.tif 000017
ただし、φは空集合である。
【数１３】
2019029976.tif 000018
【００３９】
ここで、Ｓ∧内の状態はいずれも送出レートがｒ∧０であり、変化はない。つまり、Ｓ∧内の状態に限定すれば、図３で説明したように最大状態と最小状態からのシミュレーション系列のみを考慮すれば十分である（最大・最小に挟まれた領域を飛び出す中間状態はない）。Ｓ∨内の状態についても同様である。そうすると、送出レートの変更を考えると、Ｓ∧内の最大・最小状態と、Ｓ∨内の最大・最小状態の計４状態を考慮すれば十分となる。なぜなら、Ｓ∧あるいはＳ∨いずれかの最大状態からの遷移しか、次ステップの最大状態になりえないからである。具体的には、図５のように系列３１と系列３１で挟まれる領域を飛び出す可能性がある状態は、Ｓ∨の最大状態のみである。同様に、Ｓ∧あるいはＳ∨いずれかの最小状態からの遷移しか、次ステップの最小状態になりえない。ここで、Ｓ∧の最大状態と最小状態をｓ∧ｓｕｐとｓ∧ｉｎｆとし、Ｓ∨の最大状態と最小状態をｓ∨ｓｕｐとｓ∨ｉｎｆとする。
【００４０】
図９を用いてさらに説明する。全状態Ｓにおける最大状態がｓｓｕｐ＝（１，２）であり、ｓｉｎｆ＝（０，１）だったとする。考慮すべき４状態のうち、Ｓ∧における最大状態はｓ∧ｓｕｐ＝ｓｓｕｐ＝（１，２）であり、Ｓ∨における最小状態はｓ∨ｉｎｆ＝  ｓｉｎｆ＝（０，１）である。
【００４１】
以下、残る２状態を考える。
Ｓ∧における最小状態とは、すなわち全体の最小状態ｓｉｎｆにおいて、キューｍの状態のみをθに引き上げた状態と考えればよい。図９の場合、ｍ＝２、θ＝２なので、ｓｉｎｆ＝（０，１）においてキュー２のキュー長を２としてｓ∧ｉｎｆ＝（０，２）∈Ｓ∧となる。これを次のように記載する。
【数１４】
2019029976.tif 000019
ここで、状態ｓにおけるｊ番目のキュー長を“ｓ．ｑｊ”とし、ｓｉｎｆにおいてはｑ１＝０、ｑN＝ｑ２＝１である。
【００４２】
同様に、Ｓ∨における最大状態は、全体の最大状態ｓｓｕｐにおいて、キューｍの状態のみをθからひとつ下げた状態（θ−１）となる（Ｓ∨の範囲で最大のキュー長はθ−１である）。図９の場合、ｍ＝２、θ＝２なので、ｓｓｕｐ＝（１，２）においてキュー２のキュー長を１つ下げて１としてｓ∨ｓｕｐ＝（１，１）∈Ｓ∨となる。これを次のように記載する。
【数１５】
2019029976.tif 000020
ここで、状態ｓにおけるｊ番目のキュー長を“ｓ．ｑｊ”とし、ｓｓｕｐにおいてはｑ１＝１、ｑN＝ｑ２＝２である。
【００４３】
数８は、ステップｉにおける最大状態が与えられたときステップｉ＋１の最大状態を求める計算式であり、ｓｉ∧ｓｕｐ（＝ｓｉｓｕｐ）またはｓｉ∨ｓｕｐからの遷移のうち大きいほうをステップｉ＋１の最大状態ｓｉ＋１ｓｕｐとすることを意味する。すなわち、
【数１６】
2019029976.tif 000021
である。
【００４４】
数９は、ステップｉにおける最小状態が与えられたときステップｉ＋１の最小状態を求める計算式であり、ｓｉ∨ｉｎｆ（＝ｓｉｉｎｆ）またはｓ∧ｉｎｆからの遷移のうち小さいほうをステップｉ＋１の最小状態ｓｉｎｆとすることを意味する。すなわち、
【数１７】
2019029976.tif 000022
である。
【００４５】
なお、状態ｓの大小関係を下記のように定義する。
【数１８】
2019029976.tif 000023
すなわち、２つの状態（ｓ、ｓ’）についてキューごとに長さを比較し、状態ｓが状態ｓ’に対してすべてのキューがより長いか同じであれば、状態ｓは状態ｓ’より大きいか等しい（小さくない）と言える。また、２つの状態（ｓ、ｓ’）についてキューごとに長さを比較したときに、状態ｓが状態ｓ’に対して長いキューと短いキューが存在する場合、数１０を利用する。つまり、ｓｕｐによって状態ｓと状態ｓ’より大きい状態ｓ”を計算して「大きい」状態として利用する。
なお、ｓｕｐは、いずれかの状態のほうが大きい場合、大きいほうの状態をそのまま返す。
【数１９】
2019029976.tif 000024
【００４６】
（効果）
本発明は、ＥＣＮをサポートするネットワークのシミュレーションにおいて、状態遷移先の全状態に対する「上下界」を効率的に計算して、パーフェクトシミュレーションを実行する。このため、本発明は次のような効果を得ることができる。
ネットワーク性能評価の観点では、ＥＣＮをサポートするネットワークのシミュレーションにおいて、ネットワーク状態の正常分布を、統計的な偏りなしに高精度で推定できる。
シミュレーション技術の観点では、送出レートが動的に変化するネットワークであっても、統計的な偏りのないパーフェクトシミュレーションを効率的に実行できるようになる。
【符号の説明】
【００４７】
１１：状態遷移図
１２：更新部
１３：判定部
１４：状態サンプル部
２１−０〜８：ネットワーク状態
３１、３９、３Ｘ：系列
【図１】
2019029976.tif 000025
【図２】
2019029976.tif 000026
【図３】
2019029976.tif 000027
【図４】
2019029976.tif 000028
【図５】
2019029976.tif 000029
【図６】
2019029976.tif 000030
【図７】
2019029976.tif 000031
【図８】
2019029976.tif 000032
【図９】
2019029976.tif 000033