(57)【要約】【課題】  受信サーバにおけるキューイング量を監視して未然に輻輳状態を評価する評価システムを提供することを課題とする。【解決手段】  送信元ノードと送信先ノードとの間の輻輳評価方法であって、下記ｄの標準正規型の確率密度関数１−Φ（ｄ）を実行して上記送信先ノードの送信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えた場合は、輻輳状態と評価する輻輳評価方法を提供する。【数１】2006166425.tif 000047【選択図】図１
2006166425.tif 000002
【特許請求の範囲】
【請求項１】
広域情報系において、パケットデータを送信元ノードから送信先ノードに伝送する場合に、上記送信元ノードと送信先ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価方法であって、上記各ノードが備える送受信キューで入力されるパケット及び出力されるパケットの時間間隔と累積するパケットの個数とが対数正規型の確率密度分布に従う場合に、下記ｄの標準正規型の確率密度関数１−Φ（ｄ）を実行して上記送信先ノードの送信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えたと判断した場合は、輻輳状態と評価することを特徴とする輻輳評価方法。
【数１】
2006166425.tif 000045
【請求項２】
上記算出された値が基準値を超えて、送信元ノードの送信キューが輻輳状態と判断された場合には、送信先ノードに送信拒否のメッセージを送るとともに上記送信キューにパケットを滞留させておくことを特徴とする請求項１記載の輻輳評価方法。
【請求項３】
広域情報系において、パケットデータを送信元ノードから送信先ノードに伝送する場合に、上記送信元ノードと送信先ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価方法であって、上記各ノードが備える送受信キューで入力されるパケット及び出力されるパケットの時間間隔と累積するパケットの個数とが対数正規型の確率密度分布に従う場合に、下記ｄ’の標準正規型の確率密度関数e-re(T-t)・Φ（１−ｄ’）を実行して上記送信先ノードの受信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えたと判断した場合は、輻輳状態と評価することを特徴とする輻輳評価方法。
【数２】
2006166425.tif 000046
【請求項４】
上記各所定の基準値が、過去のデータから算出された非輻輳状態の経験値によって与えられることを特徴とする請求項１から請求項３までのいずれかに記載の輻輳評価方法。
【請求項５】
広域情報系において、パケットデータを送信ノードから受信ノードに伝送する場合に、上記送信ノードと受信ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価システムであって、上記送信ノードが請求項２記載の１−Φ（ｄ）の式を実行する算出手段とこの算出手段によって算出された結果と上記所定の基準値とを比較する比較手段とこの比較手段によって算出結果の値が基準値を超えた場合に輻輳状態と判断する輻輳評価処理手段とを備えたことを特徴とする輻輳評価システム。
【請求項６】
上記送信ノードが請求項２記載の送信拒否のメッセージの生成手段と、この生成されたメッセージを送信先ノードに送信する送信手段とを備えたことを特徴とする請求項５記載の輻輳評価システム。
【請求項７】
広域情報系において、パケットデータを送信ノードから受信ノードに伝送する場合に、上記送信ノードと受信ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価システムであって、上記送信ノードが請求項３記載のe-re(T-t)・Φ（１−ｄ）の式を実行する算出手段とこの算出手段によって算出された結果と上記所定の基準値とを比較する比較手段とこの比較手段によって算出結果の値が基準値を超えた場合に輻輳状態と判断する輻輳評価処理手段とを備えたことを特徴とする輻輳評価システム。
【請求項８】
上記送信ノード及び受信ノードがルータ又はサーバであることを特徴とする請求項５から請求項８までのいずれかに記載の輻輳評価システム。
【請求項９】
上記送受信ノードを、上記請求項１から請求項４までのいずれかに記載の輻輳評価のための各方法を機能させることを特徴とする輻輳評価プログラム。
【請求項１０】
請求項９に記載の輻輳評価のための各方法を実行するプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
広域情報系に存在するノード、特に、IP網を介したパケット通信であって、ルータ、サーバ等の送受信キューにおける輻輳状態の評価を行なう輻輳評価方法、輻輳評価システム、輻輳評価プログラム及びこのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
現在、広域情報系、特にＩＰ網内に存在してパケットの送受信を行う複数のノード間では、ＴＣＰ／ＩＰという通信プロトコルが採用されている。
【０００３】
このＴＣＰ／ＩＰプロトコルにおいて、データを目的のアプリケーションに引き渡すトランスポート層のプロトコルがＴＣＰである。
【０００４】
このＴＣＰは、ノード間に仮想的な通信回線を作り、パケットデータを送信した 順番で相手が受信するようにし、さらに通信中にデータ紛失が生じた場合は再送信を行うコネクション型という形式を採用している。
【０００５】
このコネクション型のプロトコルでは、パケットデータの送受信が確実に行われているかどうかを確認するため、送信するデータに２０乃至６０バイトのＴＣＰヘッダ情報（シーケンス番号、確認応答番号等）が付されている。
【０００６】
データ通信の分野では、通信回線を効率的に利用するために、データを多重化して伝送できるパケット通信が盛んに行われているが、受信ノード側の処理能力以上の通信要求が発生すると、この受信ノードでは、一部の通信要求を無効にし、あるいは通信要求の受付を停止する輻輳状態になる。すなわち、輻輳とは、ネットワークのトラフィックが増加して有効な通信ができなくなってしまう状況をいう。
【０００７】
ルータ等のネットワーク機器では、いわゆるパケットシェイピングといって、例えば１０Ｍｂｐｓの速度を５Ｍｂｐｓに落として通信路を細くし、外部からの受信を少なくすることが行われている。
【０００８】
上記のように、コネクション型のプロトコルが採用されているにもかかわらず、しばしば輻輳状態に陥るのは、各ノードでパケットデータ処理に時間がかかり、この処理時間と外部からのパケット受信との間で同期がとれないことに起因している。
【０００９】
そこで、従来、この輻輳状態の有無を未然に確認するために、受信キューの蓄積パケット量を監視することが行われていた（例えば、特許文献１参照。）。
【００１０】
また、ＩＰ網において、ＩＰアドレスごとの単位時間当たりのパケット数をグラフ化したトラフィックパターンと実際に監視したトラフィックの監視結果とを比較し、両者の差が所定の閾値以上となった場合に、検出信号を出力し、その対象となったトラフィックパターンのＩＰアドレスに対応するＷＥＢページごとのハイパーリンク情報を集計したリンクパンターンを参照し、輻輳の可能性を判断するトラフィック輻輳予測システムが提案されていた（例えば、特許文献２参照。）。
【特許文献１】特開２００３−６９６１３（請求項３、図７の記載）
【特許文献２】特開２００４−３４３４６６（請求項１、図１の記載）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ところで、上記パケットを受信した各ノードでは送信を待つパケットデータを保存するメモリであるキューに一時的にパケットデータを保存し、例えば、パケットに優先度を付けて優先度の高いパケットから送出するなどの所定の規則に従ってパケット送出を行うキューイングという技術が採用されている。
【００１２】
しかしながら、上記従来の技術では、受信サーバからバッファに入力されるパケット量を監視しているため、バッファでオーバーフローしたパケットについては、通常破棄されてしまい通信に不具合が生じていた。
【００１３】
サーバの輻輳状態を回避するためには、上記入力されるパケット量よりも、キューイング量を監視することが重要である。
【００１４】
また、トラフィックパターンを監視する上記従来技術による輻輳評価手法については、輻輳の原因がハイパーリンクの数に起因する場合には有効な手法であるが、輻輳を引き起こす原因は動画像のように大容量のデータ通信が行なわれる場合もあり、必ずしもパケット通信全般の輻輳評価を行なう汎用性のある手法ではなかった。
【００１５】
そこで、本発明は、上記問題点に鑑み、広域情報系におけるキューイング量を監視することによって未然に輻輳状態を評価する評価システム、輻輳評価プログラムを記録した記録媒体、及び輻輳評価方法を提供することを課題とする。
【課題を解決するための手段】
【００１６】
ところで、画像データのような１つのパケット長が大きいデータの場合、受信サーバへの入力分布としては、対数正規型分布は実際によく観られる分布である。従って、入力分布として対数正規型分布を想定することは、複雑な広域情報系のサーバ系モデリングを考察する上で実用的かつ有益的である。
【００１７】
本発明にかかる広域情報系サーバの輻輳状態の評価システムは、受信サーバ内でのパケットの発生、入力、出力の時間間隔が対数正規型の確率密度分布になるような場合、受信サーバ内のパケットがキューイングバッファをフロースルーする挙動が、１次元拡散型の編微分方程式で規定できることと、数理ファイナンスにおけるオプション評価理論での評価モデル式がブラックショールズの方程式となることという両者の一致点に注目した。
【００１８】
すなわち、受信サーバ内のキューイングバッファをフローするパケットの挙動と数理ファイナンスにおけるデリバティブの挙動とが同一式で表現できることに注目した。    そこで、上記課題を解決するために、本発明にかかる輻輳評価方法は、広域情報系において、パケットデータを送信元ノードから送信先ノードに伝送する場合に、上記送信元ノードと送信先ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価方法であって、上記各ノードが備える送受信キューで入力されるパケット及び出力されるパケットの時間間隔と累積するパケットの個数とが対数正規型の確率密度分布に従う場合に、下記ｄの標準正規型の確率密度関数１−Φ（ｄ）を実行して上記送信先ノードの送信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えたと判断した場合には、輻輳状態と評価することを特徴とする。
【数１】
2006166425.tif 000003
【００１９】
この方法によれば、送信キューにおけるパケットの挙動を上記関数によって特定し、輻輳状態を把握することができる。
【００２０】
上記算出された値が基準値を超えて、送信元ノードの送信キューが輻輳状態と判断された場合には、送信先ノードに送信拒否のメッセージを送るとともに上記送信キューにパケットを残しておくようにしてもよい。このような方法によれば、適切なパケット経路の選択が可能となる。
【００２１】
また、本発明にかかる輻輳評価方法は、広域情報系において、パケットデータを送信元ノードから送信先ノードに伝送する場合に、上記送信元ノードと送信先ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価方法であって、上記各ノードが備える送受信キューで入力されるパケット及び出力されるパケットの時間間隔と累積するパケットの個数とが対数正規型の確率密度分布に従う場合に、下記ｄ’の標準正規型の確率密度関数e-re(T-t)・Φ（１−ｄ’）を実行して上記送信先ノードの受信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えた場合は、輻輳状態と評価することを特徴とする。
【数２】
2006166425.tif 000004
【００２２】
この方法によれば、受信キューにおけるパケットの挙動を上記関数によって特定し、輻輳状態を把握することができる。
【００２３】
なお、上記各所定の基準値は、過去のデータから算出された非輻輳状態の経験値によって与えられるようにしてもよい。
【００２４】
上記課題を解決するために、本発明にかかる輻輳評価システムは、広域情報系において、パケットデータを送信ノードから受信ノードに伝送する場合に、上記送信ノードと受信ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価システムであって、上記送信ノードが請求項２記載の１−Φ（ｄ）の式を実行する算出手段とこの算出手段によって算出された結果と上記所定の基準値とを比較する比較手段とこの比較手段によって算出結果の値が基準値を超えた場合に輻輳状態と判断する輻輳評価処理手段とを備えたことを特徴とする。
【００２５】
上記輻輳評価システムは、上記送信ノードが請求項２記載の送信拒否のメッセージの生成手段と、この生成されたメッセージを送信先ノードに送信する送信手段とを備えたものであってもよい。
【００２６】
また、本発明にかかる輻輳評価システムは、広域情報系において、パケットデータを送信ノードから受信ノードに伝送する場合に、上記送信ノードと受信ノードとの間のトラフィック状況を輻輳状態の有無で評価する輻輳評価システムであって、上記送信ノードが請求項３記載のe-re(T-t)・Φ（１−ｄ）の式を実行する算出手段とこの算出手段によって算出された結果と上記所定の基準値とを比較する比較手段とこの比較手段によって算出結果の値が基準値を超えた場合に輻輳状態と判断する輻輳評価処理手段とを備えたことを特徴とする。
【００２７】
上記送信ノード及び受信ノードとしては、たとえばルータ又はサーバであればよい。
【００２８】
本発明にかかる輻輳評価プログラムは、上記送受信ノードを、上記請求項１から請求項４までのいずれかに記載の輻輳評価のための各方法を機能させることを特徴とする。
【００２９】
本発明にかかるコンピュータ読み取り可能な記録媒体は、請求項９に記載の輻輳評価のための各方法を実行するプログラムを記録したことを特徴とする。
【発明の効果】
【００３０】
以上説明したとおり、本発明にかかる輻輳評価方法及び輻輳評価システムでは、広域情報系において、入力過程及び入力キューイングの動的特性が対数正規型の確率密度分布になることから、数理ファイナンスの考え方を応用することにより、効率的なパケット送信の決定を定式化することができるようになった。
【００３１】
すなわち、数理ファイナンスにおけるダイナミックヘッジを活用することにより、ノード内の送信キューの安定化状態を表現し、適切な送信経路選択が可能になるという効果を奏する。
【００３２】
また、数理ファイナンスのバイナリオプションを適用し、パケットロスの確率を求めることにより、広域情報系のボトルネックを評価することができ、情報システムのサービスレベルを維持するうえで非常に有用な効果を奏する。
【００３３】
さらに、各ノードの送信キューと受信キューとの双方の輻輳状態を評価することができるのでパケットの挙動を的確に捉えてタイムリーな輻輳回避が可能になる。特に、広域情報系に存在するノード内のキューのオーバーフロー回避機能として公知のＲＥＤ（Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ）では、パケットが破棄されてしまうため、本発明を利用すれば、パケットロスする前に的確な輻輳評価が可能になり、スムーズなパケット通信の提供を可能にするという効果を奏する。
【発明を実施するための最良の形態】
【００３４】
図１（ａ）は、本発明にかかるルータ系の輻輳評価システムの構成図であり、図１（ｂ）はサーバ系の輻輳評価システムの構成図である。
【００３５】
図１（ａ）を参照して、Ｒｓは、送信元ルータであり、ＩＰ網を介して送信元ルータＲｓは、送信先ルータＲｒに接続されている。送信先ルータＲｒは、送信元ＲｓからＩＰ網を介してパケットデータを受信する。パケットデータは、入力ポートＲｒ１を通じて受信キューＲｒ２に一時的に保持される。受信キューで保持されたパケットデータのヘッダにある宛先ＩＰアドレスに基づき宛先判定部Ｒｒ３は、転送するルータを判定する。宛先判定部Ｒｒ３によって判定されたパケットデータは、転送制御部Ｒｒ４によってルーティングテーブルを参照しながら転送先のルータを判断し、転送先のルータに対応する送信キューＲｒ５で一時的に保持される。送信キューＲｒ５で保持されたパケットデータは、送信制御部Ｒｒ６によって順次対応する出力ポートＲｒ８から送信される。この受信ルータＲｒに本発明に係る輻輳評価方法を実行する輻輳評価部Ｒ８が設けられている。輻輳評価部Ｒ８は、少なくとも、所定の時刻までのキューＲｒ２又はＲｒ５の輻輳評価値を算出する算出手段とこの算出手段によって算出された結果と所定の基準値とを比較する比較手段とこの比較手段によって算出結果の値が基準値を超えた場合に輻輳状態と判断する輻輳評価処理手段を有する。
【００３６】
図１（ｂ）を参照して、Ｓｓは、送信サーバであり、ＩＰ網を介し、ルータを通じて送信サーバＳｓは、受信サーバＳｒに接続されている。送信サーバＳｓは、送信側アプリケーションからさまざまな大きさのデータが複数個送信側ＴＣＰモジュールに渡される。送信側ＴＣＰモジュールではキュー（図示せず）を利用してこれらのデータを蓄積する。蓄積されたデータは、ＴＣＰヘッダがつけられてセグメントが形成される。この送信側ＴＣＰモジュールで形成されたセグメントは、送信側ＩＰモジュールに渡され、物理的に送信できるサイズに断片化される。これら断片化されたデータは、それぞれ上記ＴＣＰヘッダが付され、パケットデータとしてＩＰ網に送り出される。このパケットデータは、ＩＰ網からルータを介して受信サーバＳｒで受信される。受信サーバＳｒで受信されたパケットデータは、最初にキューＳｒｑに転送される。このとき、この受信サーバＳｒが輻輳状態にない場合、キューＳｒｑの内部では、上記パケットデータがキューから、ＩＰモジュールＳｒ１に転送される。一方、受信サーバＳｒが輻輳状態にある場合、キューＳｒｑの内部では、上記パケットデータがキューＳｒｑに溜まり、バッファ（図示せず）が空くとバッファに転送されて、ＩＰモジュールＳｒ１に転送される信側ＩＰモジュールＳｒに転送されたパケットは再構成化され、受信側ＴＣＰモジュールＳｒ２に渡される。このＴＣＰモジュールＳｒ２では、各パケットデータのシーケンス番号を調べて連続したデータが受け付けられているかどうかを検証する。検証が済むと、上記ＴＣＰヘッダを削除し、受信サーバＳｒで該当するアプリケーションＳｒ３が要求するサイズのデータにしてアプリケーションＳｒ３に渡す。
【００３７】
この受信サーバＳｒに本発明に係る輻輳評価方法を実行する輻輳評価部Ｓｒ４が設けられている。輻輳評価部Ｓｒ４は、少なくとも、所定の時刻までのキューＳｒｑの輻輳評価値を算出する算出手段とこの算出手段によって算出された結果と所定の基準値とを比較する比較手段とこの比較手段によって算出結果の値が基準値を超えた場合に輻輳状態と判断する輻輳評価処理手段を有する。
【００３８】
本実施の形態では、以下通信ノードとしてルータを示したが、図１で示す通り、これに限定される趣旨ではなく、広域情報系に設けられ、送受信キューを内蔵し、パケットデータ通信を行なうものであれば、たとえばサーバであってもよい。
【００３９】
また、図１では、輻輳評価部を送信先ルータＲｒ及び受信サーバＳｒに内蔵した形態を示したが、本発明にかかる輻輳評価方法を実施する形態は、これに限定されるものではなく、送信先ルータＲｒ及び受信サーバＳｒと外部接続する端末に、本発明にかかる輻輳評価プログラムを直接インストールし、あるいは上記輻輳評価プログラムを記録したコンピュータ読み取り可能な記録媒体からインストールし、輻輳評価を行なうような形態でもよい。
【００４０】
図２により、送信元ルータから送信先ルータまでのパケットの動きを説明する。ルータ（ｉ−１）は、その前のリンクにつながるルータからパケットを受信する。受信したパケットは受信キューを経由してパケット処理された後送信キューに送られ、ルータ（ｉ）に送信される。パケットはこのルータ（ｉ）でも、ルータ（ｉ−１）と同じ動きをする。送受信キューの容量は有限長とする。
【００４１】
本発明にかかる輻輳評価方法は、上記パケット処理過程において、下記ｄの標準正規型の確率密度関数１−Φ（ｄ）を実行してルータ（ｉ）の送信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えた場合は、輻輳状態と評価するものである。
【数１】
2006166425.tif 000005
【００４２】
また、本発明にかかる輻輳評価方法は、上記パケット処理過程において、下記ｄ’の標準正規型の確率密度関数e-re(T-t)・Φ（１−ｄ’）を実行して上記送信先ノードの受信キューにおける所定の時刻までのパケット数の獲得確率の値を算出し、この値が所定の基準値を超えた場合は、輻輳状態と評価するものである。
【数２】
2006166425.tif 000006
以下、これら２つの式の導入について説明する。
【００４３】
ルータ（ｉー１）から送信されて、ルータ（ｉ）に入力される入力過程およびルータ（ｉ）内のパケット処理から入力される入力過程をモデル化する。まず、以下のような仮定を行なう。
［仮定１］個々のパケット到着レートは、１つ前に到着したパケットとの間隔のみにより定まる。パケットの消滅は、ルータ（ｉー１）とルータ（ｉ）とのリンク間および各ルータ内では発生しないものとする。
［仮定２］パケットレートは、パケット発生時点の通信システムの状態により定まる。
［仮定３］システムに加わる加法的外乱は、主に通信路におけるサイト間の非線形特性（例えばキューイング）により定まる。
［仮定４］ルータ（ｉ）、ルータ（ｉー１）内のパケット処理から送信キューに送出される個々のパケットレートは、１つ前の先行パケットとの間隔のみにより定まる。
【００４４】
図３は、上記ルータ（ｉー１）及びルータ（ｉ）から成るルータ系におけるパケット入力過程のモデルをあらわしてる。ここでは、上記［仮定１］に従ってパケットの間隔時系列を以下のように表す。
【００４５】
図３における各文字を以下のように定義する。
［定義１］Ｓｊ（ｔ）：ｊ番目のパケットの時刻ｔでの到着時刻
［定義２］Ｓｊ−１（ｔ）：（ｊ−１）番目のパケットの時刻ｔでの到着時刻
【００４６】
以下、まず、式１−Φ（ｄ）について説明する。
上記定義により、任意のルータ系における入力過程の到着時間間隔は、
［式１］
2006166425.tif 000007
と定義できる。
【００４７】
時刻ｔ≧０におけるＴｊ（ｔ） は、ここでは連続値をとる値として定義している。また、Ｔｊ（ｔ）の時間的変化率ｄＴｊ（ｔ）＝ｄｔは一定値をとるのではなく，ルータ(ｉ) に送信されてくるパケット蓄積量に影響を与えながら、刻々と変化する。
【００４８】
次に、図４により、ルータ（ｉ）のパケット処理を示す。図４で示すルータ（ｉ）のパケット処理で使われている変数の確率空間(Ω，Ｆ) は可測空間であり、Ｉ は，[０，∞) として時間区間を表す。また、確率空間(Ｚｔ；Ｆｔ；Ｐ)，ｔ∈Ｉと表され，Ｐ は、(Ω，Ｆ) における確率測度，(Ｆｔ) は増大するσ− 集合体の族であり、(Ｚｔ) は，(Ｆｔ) に適合するランダム変数の族である。
【００４９】
図４に表われる各変数は，上記の確率空間上で定義された確率変数である。Ｎｊ(ｔ) は広域情報系からのパケット入力過程である。ルータ内パケットの受信用キューイング過程に関して、キューイングバッファとして広域情報系からの入力キュー（ＱＲ（ｔ））と出力キュー（(ＱＳ（ｔ)）の２種類のキューが存在する。Ｎｊ(ｔ)，ＱＲ(ｔ)，ＱＳ(ｔ)，はすべて確率的な挙動を示し、それぞれは独立した確率過程とする。ここでは，ＱＲ(ｔ)とＱＳ(ｔ)の確率的挙動は同一とする。以上の考え方を応用することにより、広域ネットワーク系におけるルータ入力過程のモデルを構築する。そこで、［式１］ を利用することによりＴｊ（ｔ）のモデルを以下のように定式化する。
［式２］
2006166425.tif 000008
【００５０】
ここで，β[・] はＴｊ（ｔ）に関する確率分布を，ｎｊ（ｔ） は上記仮定３による加法的外乱を表している。さらに，パケットレートをρ（ｔ）［bits/sec］とおき，入力パケット[bits] をＮｊ(ｔ)とおくと
［式３］
2006166425.tif 000009
と定義できる。ただし，ｊ＝１，２，… である。それゆえ、[式３]は形式的に
［式４］
2006166425.tif 000010
と書ける。このとき，Ｗ[・] はＮｊ（ｔ） に関する確率分布である。ｂ[・] は、外乱項係数の入力依存性を表している。ここで、[式４]の線形モデルとして次式を得る。
［式５］
2006166425.tif 000011
Ｗ０，ｂ０はＮｊ（ｔ）の平均値Ｎｊｍの回りで線形化したときの係数であり、それぞれ
［式６］
2006166425.tif 000012
［式７］
2006166425.tif 000013
である。以上のようなモデリングにより、広域情報系のルータ入力過程は
［式８］
2006166425.tif 000014
のような対数正規型の確率微分方程式で表されることがわかる。ただし、μｊ は、Ｎｊ（ｔ）の平均，σｊはＮｊ（ｔ）の分散を表す。また、ｄＺｊ（ｔ） は、ウィナー過程としての外乱項を示す［仮定(３)]。
【００５１】
すなわち、上述の考え方によりルータ内の受信パケット用バッファのキューイングモデルは形式的に以下のように表現できる。
［式９］
2006166425.tif 000015
μＲは、ＱＲ（ｔ）の平均、σＲはＱＲ（ｔ）の分散、ｄＺ（ｔ） はウィナー過程としての外乱項を表している。ここで、ルータ内送信パケット用バッファのキューイングモデルは受信用バッファのモデルと同様のため，以下のように表現することができる。
［式１０］
2006166425.tif 000016
μＳは、ＱＳ（ｔ）の平均、σＳはＱＳ（ｔ）の分散、ｄＺ（ｔ） はウィナー過程としての外乱項を表している。
【００５２】
このようにして、広域情報系に存在するルータ系に入力されるパケットがルータ内にキューイングされ、ルータキューイングから出力されたパケットは、その後ルータ内で処理される。このことを図４で表す。なお、このルータ系の前提条件として、図４における広域情報系に存在するルータ系へのパケット入力は、対数正規分布をとるものとする。パケット入力の確率モデルは次式で表される。
［式１１］
2006166425.tif 000017
【００５３】
ここで、ルータが入力パケットの一部を破棄して安定状態へ遷移する状態をダイナミックヘッジを利用して説明する。ここで送信元ルータの確率モデルを図４のように表す。この考え方は、数理ファイナンスにおけるデリバティブズをルータ系キューイングの安定状態評価に応用したものである。金融における株価の変動，円・ドルの為替変動の時間的変動が、ある条件のもとで確率微分方程式で記述できることはよく知られている。ここで，Ｖｓ（ｔ） を定義する。この変数は、ルータへのキューイング輻輳状態を表すための係数を意味する。例えば、パケット受信ルータのキューイング過程ＱＳ（ｔ）は、ある汎関数Ｖ (・) により、獲得確率Ｖ（ＱＳ（ｔ），ｔ）としてルータ内受信キューイングの輻輳状態の評価値を表す。
【００５４】
さらに、送信キューにおける輻輳回避（ダイナミック・ヘッジ）を次のように定義する。
［定義３］ルータ(ｉ)の送信輻輳回避に関する定義式を以下に示す。
［式１２］
2006166425.tif 000018
と定義する。式（12）の確率的変動は、
［式１３］
2006166425.tif 000019
と構成できる。Ｕ は、値の変動が少ないほどキューイングバッファが安定していることを表している。しかし、ルータに許容レート以上のパケットが到着している場合はパケットを破棄して輻輳を回避するため、この値は基本的に変動しないことになる。
【００５５】
ＶＳ（ｔ）は
［式１４］
2006166425.tif 000020
と定義できる。また、ＶＳ（ｔ）を、以下のような獲得確率として定義する。
［式１５］
2006166425.tif 000021
【００５６】
いま、この送信キューのキューイング量に対する輻輳評価の基準値を輻輳評価値と呼ぶことにする。ここで、ルータ(ｉ−１)から送信されるパケットから輻輳回避するための輻輳回避関数ＶＳ（ｔ）は[∂Ｖ（ＱＳ（ｔ）/∂ＱＳ（ｔ））] に依存していることがわかる。
【００５７】
上記式（９）、（１０）、（１１）のモデル式において、［式１５］の輻輳評価を考えることにする。［式１５］は、次のように計算される。
【００５８】
評価時刻Ｔ におけるルータ内累積パケット量ＱＳ（Ｔ）と輻輳評価値ＤＳ（Ｔ）に関して、ｔ＜Ｔ の時点で、かつＱＳ（ｔ）＜ＤＳ（Ｔ）となる確率をＰｒ（ＱＳ（ｔ）＜ＤＳ（Ｔ）｜ＱＳ（Ｔ）） とすると
［式１６］
2006166425.tif 000022
となり、上記式を導くことができる。ここで、Φ（・）は、標準正規確率密度関数であり、
［式１７］
2006166425.tif 000023
である。なお、r は、ファイナンスでは「安全レート」を意味するが、ここでは、キューイングバッファがオーバーフローしないようなトラフィックレートを意味する。この式を計算することにより、ルータ(ｉ)系からの送信評価に活用することができる。
【００５９】
次に、式e-re(T-t)・Φ（１−ｄ’）について説明する。
【００６０】
まず、ｌｉをリンク数、ｌｉ∈Ｌとすると、ルータ間の通信範囲を決めるパラメータＲｌｉは次式で定義される。ただし、ｉ＝１，２，…，ｎ，ルータ間の通信範囲は、連続したリンクとする。
［式１８］
2006166425.tif 000024
ソース（ｉ）から発信する通信速度をｘｉ（ｔ）とおくと
［式１９］
2006166425.tif 000025
とあらわせる。ただし、τｉ（ｔ）は、ルータ（ｉ）からルータ（ｉ＋１）へ可能な論理的なデータ量ωｉ（ｔ）を送信するための送信時間であり、ωｉ（ｔ）は送信可能な論理的なデータ量である。ＴＣＰ/ＩＰプロトコルでは、ウィンドウサイズと呼び、送信元ルータから送信先ルータにデータを効率よく送信することができるデータ容量のことをいう。このときルータ（ｉ）とルータ（ｉ＋１）のリンク間における情報フローｙｉ（ｔ）は、下記［式２０］であらわすことができる。
［式２０］
2006166425.tif 000026
τｌｉは、送信元ルータ（ｉ）から送信先ルータ（ｉ＋１）へのパケット転送遅延時間とする。ここでは、送信元から送信先へのパケット転送遅れ、つまり片側だけの時間遅れについてモデル化を考える。そこで、パケット転送遅れをむだ時間系のシステムとして取り扱うことによりモデル化を行なう。パケットのあるサイズを持った論理的なデータが、送信先に送られる形態である。これは、ある種の１次元流体が移動する形態に相当すると考えられる。
【００６１】
上記［定義１］及び［定義２］により、任意のルータ系における入力過程の到着時間間隔は、
［式２１］
2006166425.tif 000027
と定義できる。ただし、νは、パルス時間間隔の遅れをあらわす。このような時間間隔遅れ系列の考え方は、例えば、自律的に発生する神経パルス列においても見られる。ただし、この場合じゃ、遅れ時間はない。ここでは、周期パルス列の分散関係、すなわち、パルス間隔系列の確率分布に着目し、それを利用することを基本としている。時刻ｔ≧０におけるＴｊ（ｔ−ν） はここでは連続値をとる値として定義している。また，Ｔｊ（ｔ−ν）の時間的変化率ｄＴｊ（ｔ−ν）＝ｄｔは一定値をとるのではなく、ルータ(ｉ) に送信されてくるパケット蓄積量に影響を与えながら，刻々と変化する。
【００６２】
次に、図４により、ルータ（ｉ）のパケット処理図を示す。図４で示すルータ（ｉ）のパケット処理で使われている変数の確率空間(Ω，Ｆ) は可測空間であり、Ｉ は、[０，∞) として時間区間を表す。また、確率空間(Ｚｔ；Ｆｔ；Ｐ)，ｔ∈Ｉと表され、Ｐ は、(Ω，Ｆ) における確率測度、(Ｆｔ) は増大するσ− 集合体の族であり，(Ｚｔ) は，(Ｆｔ) に適合するランダム変数の族である。
【００６３】
図４ に表われる各変数は，上記の確率空間上で定義された確率変数である。Ｎｊ(ｔ) は広域情報系からのパケット入力過程である。ルータ内パケットの受信用キューイング過程に関して，キューイングバッファとして広域情報系からの入力用（ＱＲ（ｔ））と出力用（(ＱＳ（ｔ)）の２種類のキューが存在する。通常、送信キューよりも受信キューがルータ内のパケット処理のボトルネックにより、増大する。そこで、ここでは、受信キューについて説明する。Ｎｊ(ｔ)，ＱＲ(ｔ)，ＱＳ(ｔ)，はすべて確率的な挙動を示し，それぞれは独立した確率過程とする。ここでは，ＱＲ(ｔ) とＱＳ(ｔ)の確率的挙動は同一とする。以上の考え方を応用することにより，広域ネットワーク系におけるルータ入力過程のモデルを構築する。そこで，［式２１］ を利用することによりＴｊ（ｔ−ν）のモデルを以下のように定式化する。
［式２２］
2006166425.tif 000028
よりＴｊ（ｔ）のモデルを以下のように定式化する。
【００６４】
ここで，β[・] はＴｊ（ｔ−ν）に関する確率分布を，ｎｊ（ｔ） は上記仮定３による加法的外乱を表している。さらに，パケットレートをρ（ｔ）［bits/sec］とおき，入力パケット[bits] をｙｌｊ(ｔ)とおくと
［式２３］
2006166425.tif 000029
と定義できる。ただし，ｊ＝１，２，… である。それゆえ，[式２３]は形式的に
［式２４］
2006166425.tif 000030
と書ける。このとき，Ｗ[・] はｙｌｉ（ｔ） に関する確率分布である。ｂ[・] は、外乱項係数の入力依存性を表している。ここで、[式２４]の線形モデルとして次式を得る。
［式２５］
2006166425.tif 000031
Ｗ０，ｂ０はｙｌｉ（ｔ）の平均値ｙｌｉｍの回りで線形化したときの係数であり，それぞれ
［式２６］
2006166425.tif 000032
［式２７］
2006166425.tif 000033
である。それゆえ、［式２６］は形式的に以下のようにあらわされる。
［式２８］
2006166425.tif 000034
このとき［式２８］における外乱項を
［式２９］
2006166425.tif 000035
とおく。ただし、ｄＺｊ（ｔ）はウィナー過程としての外乱項である。
［式３０］
2006166425.tif 000036
すなわち、［式３０］は広域ルータ系における情報遅れ時間間隔系列の動的モデルを表している。ここで簡単のために［式３０］を線形近似すると形式的に
［式３１］
2006166425.tif 000037
とあらわせる。ここでは、ボトルネック系において、パケットフローｙli(t)は、キュー長及びキュー長の平均値の関数として定義している。
【００６５】
そこで、［式３０］により派生する状態として安定状態関数を定義する。ここで、安定状態関数をＶｌｉ（ｙｌｉ（ｔ），ｔ）とあらわす。このＶ（ｙｌ（ｔ），ｔ）（添字ｌ及びｉを省略）をパケットマーク評価確率と呼ぶ。このときＶ（ｙｌ（ｔ），ｔ）を
［式３２］
2006166425.tif 000038
で定義する。ここで、Ｙ（ｔ，ｌｉ）は、確率評価ｙｌ（ｔ）の集合である。一方、Ｖ（ｔ，ｌｉ）に対する評価を
［式３３］
2006166425.tif 000039
とする。ここで、Ｈはヘビサイドオペレータである。すなわち、不安定、安定の２相状態の評価として以下のように定義する。
［定義１］安定状態
［式３４］
2006166425.tif 000040
［定義２］不安定状態
［式３５］
2006166425.tif 000041
である。ゆえに、ファイナンス理論を応用すれば、これはバイナリコールオプションと同様の意味を持っている。このとき、
［式３６］
2006166425.tif 000042
［式３７］
2006166425.tif 000043
上記［式３６］をパケットマーク評価確率（獲得確率）と呼ぶ。ただし、
［式３８］
2006166425.tif 000044
である。
以上より、式e-re(T-t)・Φ（１−ｄ’）を導くことができた。上記［式２０］により情報時間遅れを計測し、かつ［式３６］により、パケット獲得確率を計算することができる。ここで求められた値は、広域情報系あるいは広域情報系の数理モデルの構築を補助し、制御系設計に効力をもたらすものと思われる。
【実施例】
【００６６】
以上の諸式について実際に計算機上でシミュレーションを行い，その結果を確認した。
【００６７】
まず、式１−Φ（ｄ）についてのシミュレーション結果を説明する。
図５は、ネットワーク構成模式図である。トラフィックを生成する端末Ｔに対し、３ 台のルータを階層的に接続した。３ 台のルータ(i)，ルータ(v)，ルータ(w) は左から時計回りにそれぞれ，図４のルータ(i)，ルータ(v)，ルータ(w)に相当する。
なお，ＴＣＰ/ＩＰなど他のプロトコルスタック、リンクの伝送速度、ルータ内プロセッサの遅延はシミュレーションの対象から除外した。 
端末Ｔから発生したトラフィックは，ルータ(i) の受信キューに到達し、その後パケット処理プロセッサを経由し送信キューへ転送される。このとき［式１６］ によって転送先が決定され、ルータ(v)，ルータ(w) のいずれかに送信される。プロセッサでの遅延は０である。ルータ（ｉ）は、ルータ(v)及びルータ(w)のは受信キューの輻輳状況を式(１６) によって判断し、いずれか一方のルータが輻輳状態であると評価した場合は、ルータ(i) から輻輳状態と評価したルータに対し送信拒否メッセージを送信する。ルータ(i) の送信キューは、ルータ(v)又はルータ(w) への送信拒否メッセージと、輻輳評価値に基づきパケットを転送する。ルータ(v)及びルータ(w)の双方から受信拒否されていた場合、ルータ（ｉ）はパケットを送信キューに残しておく。
【００６８】
シミュレーションへの入力パラメータとして、端末Ｔから発生するトラフィックの送信レート，各ルータの受信バッファ・送信バッファのサービス能力について、それぞれ対数正規分布の平均，分散を設定できる。シミュレーションモデルでは，このパラメータを様々な値に変化させたときのルータ(i) における輻輳評価値［式１６］ と、安定状態を測る指標である［式１２］を確認している。なお、以降に記すシミュレーション結果は１０００秒間実行したときの値を利用している。
条件１:送信レートの平均を変更した時の動作
まず，各ルータのサービス時間を一定にしたままで、端末Ｔにおける送信レートの平均値を表１のように変化させ、各設定でシミュレーションを実行した。全ルータのサービス時間は，シナリオ１の送信レートと同じ平均0.001秒，分散０．３に設定してある。なお、シミュレーションモデルの都合上、設定値は送信・サービスの間隔(単位:秒) で指定してある。
条件２:送信レートの分散を変更した時の動作
次に、条件１と同様に各ルータのサービス時間を一定にしたままで、端末Ｔにおける送信レートの分散を表２ のように変化させ、シミュレーションを実行した。
表１ 各シナリオの送信レート（平均を変化）
送信レート
シナリオ      平均(秒)            分散
１            ０．００１          ０．３
２            ０．００２          ０．３
３            ０．００１３３３    ０．３
４            ０．０００５        ０．３
表２ 各シナリオの送信レート（分散を変化）
送信レート
シナリオ      平均(秒)            分散
１            ０．００１          ０．３
５            ０．００１          ０．６
６            ０．００１          ０．９
７            ０．００１          １．２
各シナリオのシミュレーション結果を図６に示す。このグラフは輻輳評価値を平均した結果である。
図６で示すルータ(i) の送信キュー長を比較すると、キューサイズの大小にしたがって輻輳評価式の示す値が変動している。
そこで、ルータ(i) の送信キューに滞留しているパケット数と［式１６］との相関係数を調べた。その結果を表３に示す。この値から，輻輳評価値とキュー状況とは強く関連していることが確認できる。
表３ 各シナリオにおける相関係数
シナリオ        相関係数
１            −０．７２４
２            −０．８７８
３            −０．７９３
４            −０．７８２
５            −０．６６９
６            −０．８４５
７            −０．８９４
この状況を見るために、まず、シナリオ１において２５５−２５９秒の期間でＮｊ（ｔ）とＵ［式１２］ を抜き出したものが図７、その時の破棄パケット量が図８である。ここでは入力パケットＮｊ（ｔ）が大きく変化することにより、Ｕ もつられて変動しているが、その後溢れたパケットが破棄されたため、安定状態に遷移していることを確認できる。
【００６９】
次に、シナリオ６において４００−４０４秒の区間でキュー長と獲得確率ＶＳ（ｔ）（輻輳評価値）を抜き出したのが図９である。キュー長が増大したことにより、獲得確率が減少していることが分かる。
【００７０】
以上のシミュレーション結果から、本発明にかかる輻輳評価方法によって求められる輻輳評価値は、ルータなどのノード内のキューの状況を示す値として適切であることがわかる。
【００７１】
次に、式e-re(T-t)・Φ（１−ｄ’）に関するシミュレーション結果を説明する。
【００７２】
ここでは、ラウンド・トリップ時間（ＲＴＴ）が対数正規モデルになるという前提のキューイングのオーバーフロー評価を示した。以下各グラフのパケット長（対数正規）の偏差は、σ＝１００Ｍ、５０Ｍ、１０Ｍ、５Ｍ、１Ｍ（Ｍ＝１００万）の５種であり、共通のパラメータは下記の通りである。
パケット間隔：開始時０．０１秒→終了時０．００５秒
パケット長平均：１０００バイト
平均・偏差計算：毎回最新の１００サンプルから測定
評価時間Ｔ：毎回１００秒
ＲＴＴ間隔閾値Ｙｌｋ：１秒
シミュレーション時間：１時間
【００７３】
図１０は、パケットロス確率（輻輳評価値）を示したグラフである。パケットマーク評価確率とは、受信キューに蓄積されたキューがオーバーフローする割合をいう。図１０では、横軸を時間（秒）、縦軸をパケットロス確率とし、パラメータとして複数の分散値を設定した。図１０によれば、２５００秒近傍でパケットマーク評価確率の値が１から急峻に減少している。これは、受信キュー内のパケットがフル状態になり、オーバーフローする状態を示している。なお、値１が受信キューが空の状態であり、値０がフル状態である。
【００７４】
図１１は、ＲＴＴの平均値を示したグラフである。横軸を時間（秒）、縦軸をＲＴＴの時間間隔の平均とし、パラメータとして複数の分散値を設定した。送受信しているルータ間で常にＰＩＮＧコマンドを送出し、その返答が来るまでの時間を計測している。ＴＣＰ/ＩＰプロトコルでは、この値が大きいと送信先のルータに何か異変があると判断している。図１１によれば、送出するパケット頻度が大きいと、ＲＴＴの平均も上昇する傾向を示している。
【００７５】
図１２は、ＲＴＴ間隔の偏差を示したグラフである。横軸を時間（秒）、縦軸をＲＴＴの偏差とし、パラメータとして複数の分散値を設定した。偏差は、送信するパケット長を調整することにより変動させることができる。図１２から明らかな通り、受信キューに蓄積される際に、受信キューがフルになる割合が高いことを示している。
【００７６】
以上のシミュレーション結果から、本発明にかかる輻輳評価方法によって求められる輻輳評価値は、ルータなどのノード内のキューの状況を示す値として適切であることがわかる。
【産業上の利用可能性】
【００７７】
本発明によれば、広域情報系に存在する受信サーバの輻輳評価を行うことができるので、ＩＰ網を利用したパケット通信の分野で、輻輳評価システムとして適用できる。
【図面の簡単な説明】
【００７８】
【図１】（ａ）本発明にかかるルータ系の輻輳評価システムの構成図、（ｂ）本発明にかかるサーバ系の輻輳評価システムの構成図
【図２】送信元ルータから送信先ルータまでのパケットの動きを示した図
【図３】ルータ（ｉー１）及びルータ（ｉ）から成るルータ系におけるパケット入力過程のモデルを示した図
【図４】ルータ（ｉ）のパケット処理図
【図５】ネットワーク構成模式図
【図６】各シナリオにおける輻輳評価値のシミュレーション結果を示すグラフ
【図７】シナリオ１において２５５−２５９秒の期間でＮｊ（ｔ）とＵ を抜き出した結果を示すグラフ
【図８】図７のときのパケット破棄量の変化を示すグラフ
【図９】シナリオ６において４００−４０４秒の区間でキュー長と獲得確率ＶＳ（ｔ）を抜き出した結果を示すグラフ
【図１０】パケットマーク評価確率を示したグラフ
【図１１】ＲＴＴの平均値を示したグラフ
【図１２】ＲＴＴ間隔の偏差を示したグラフ
【符号の説明】
【００７９】
Ｒｓ    送信元ルータ
Ｒｒ    送信先ルータ
Ｒｒ２  送信キュー
Ｒｒ５  受信キュー
Ｒｒ８  輻輳評価部
Ｓｓ    送信サーバ
Ｓｒ    受信サーバ
Ｓｒｑ  キュー
Ｓｒ４  輻輳評価部
【図１】
2006166425.tif 000048
【図２】
2006166425.tif 000049
【図３】
2006166425.tif 000050
【図４】
2006166425.tif 000051
【図５】
2006166425.tif 000052
【図６】
2006166425.tif 000053
【図７】
2006166425.tif 000054
【図８】
2006166425.tif 000055
【図９】
2006166425.tif 000056
【図１０】
2006166425.tif 000057
【図１１】
2006166425.tif 000058
【図１２】
2006166425.tif 000059