(57)【特許請求の範囲】
【請求項１】
ネットワーク上で輻輳が発生しているかどうかを判定するリンク輻輳判定方法において、
予め定められた時間間隔におけるリンク平均使用率を算出するステップと、前記リンクを通過する平均同時接続フロー数を算出するステップと、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出するステップと、
前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するステップとを有することを特徴とするリンク輻輳判定方法。
【請求項２】
前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満であり、当該リンクにおけるパケット損失率が予め定められた第１のパケット損失率未満の場合に、前記リンク平均使用率当たりの平均同時接続フロー数を算出することを特徴とする請求項１に記載されたリンク輻輳判定方法。
【請求項３】
前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、当該リンクにおけるパケット損失率が予め定められた第２のパケット損失率以上で、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定することを特徴とする請求項１または請求項２のいずれかに記載されたリンク輻輳判定方法。
【請求項４】
パケットヘッダ中の送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号及びトランスポートプロトコルが同一であるものを同一フローと識別し、また同一フローに属するパケットが予め定められた時間以内に検出されない場合に当該フローが終了したと見なすことによって前記平均同時接続フロー数を算出することを特徴とする請求項１乃至請求項３のいずれか１項に記載されたリンク輻輳判定方法。
【請求項５】
ＴＣＰパケット中のＳＹＮパケット及びＦＩＮパケットを検出することによって前記平均同時接続フロー数を算出することを特徴とする請求項１乃至請求項３のいずれか１項に記載されたリンク輻輳判定方法。
【請求項６】
ネットワーク上で輻輳が発生しているかどうかを判定するリンク輻輳判定装置において、
予め定められた時間間隔におけるリンク平均使用率を算出するリンク使用率算出部と、前記リンクを通過する平均同時接続フロー数を算出する同時接続フロー数算出部と、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出する使用率当たりの同時接続フロー数算出部と、
前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するリンク輻輳判定部とを備えることを特徴とするリンク輻輳判定装置。
【請求項７】
前記使用率当たりの同時接続フロー数算出部は、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満であり、当該リンクにおけるパケット損失率が予め定められた第１のパケット損失率未満の場合に、前記リンク平均使用率当たりの平均同時接続フロー数を算出するものであることを特徴とする請求項６に記載されたリンク輻輳判定装置。
【請求項８】
前記リンク輻輳判定部は、前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、当該リンクにおけるパケット損失率が予め定められた第２のパケット損失率以上で、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するものであることを特徴とする請求項６または請求項７のいずれかに記載されたリンク輻輳判定装置。
【請求項９】
前記同時接続フロー数算出部は、パケットヘッダ中の送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号及びトランスポートプロトコルが同一であるものを同一フローと識別し、また同一フローに属するパケットが予め定められた時間以内に検出されない場合に当該フローが終了したと見なすことによって前記平均同時接続フロー数を算出するものであることを特徴とする請求項６乃至請求項８のいずれか１項に記載されたリンク輻輳判定装置。
【請求項１０】
前記同時接続フロー数算出部は、ＴＣＰパケット中のＳＹＮパケット及びＦＩＮパケットを検出することによって前記平均同時接続フロー数を算出するものであることを特徴とする請求項６乃至請求項８のいずれか１項に記載されたリンク輻輳判定装置。
【請求項１１】
ネットワーク上で輻輳が発生しているかどうかを判定するリンク輻輳判定装置としてコンピュータを機能させる為のプログラムにおいて、予め定められた時間間隔におけるリンク平均使用率を算出するリンク使用率算出部と、前記リンクを通過する平均同時接続フロー数を算出する同時接続フロー数算出部と、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出する使用率当たりの同時接続フロー数算出部と、
前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するリンク輻輳判定部としてコンピュータを機能させることを特徴とするプログラム。
【請求項１２】
前記使用率当たりの同時接続フロー数算出部は、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満であり、当該リンクにおけるパケット損失率が予め定められた第１のパケット損失率未満の場合に、前記リンク平均使用率当たりの平均同時接続フロー数を算出するものであることを特徴とする請求項１１に記載されたプログラム。
【請求項１３】
前記リンク輻輳判定部は、前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、当該リンクにおけるパケット損失率が予め定められた第２のパケット損失率以上で、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するものであることを特徴とする請求項１１または請求項１２のいずれかに記載されたプログラム。
【請求項１４】
前記同時接続フロー数算出部は、パケットヘッダ中の送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号及びトランスポートプロトコルが同一であるものを同一フローと識別し、また同一フローに属するパケットが予め定められた時間以内に検出されない場合に当該フローが終了したと見なすことによって前記平均同時接続フロー数を算出するものであることを特徴とする請求項１１乃至請求項１３のいずれか１項に記載されたプログラム。
【請求項１５】
前記同時接続フロー数算出部は、ＴＣＰパケット中のＳＹＮパケット及びＦＩＮパケットを検出することによって前記平均同時接続フロー数を算出するものであることを特徴とする請求項１１乃至請求項１３のいずれか１項に記載されたプログラム。
【請求項１６】
ネットワーク上で輻輳が発生しているかどうかを判定するリンク輻輳判定装置としてコンピュータを機能させる為のプログラムを記録したコンピュータ読み取り可能な記録媒体において、
予め定められた時間間隔におけるリンク平均使用率を算出するリンク使用率算出部と、前記リンクを通過する平均同時接続フロー数を算出する同時接続フロー数算出部と、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出する使用率当たりの同時接続フロー数算出部と、
前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するリンク輻輳判定部としてコンピュータを機能させる為のプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１７】
前記使用率当たりの同時接続フロー数算出部は、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満であり、当該リンクにおけるパケット損失率が予め定められた第１のパケット損失率未満の場合に、前記リンク平均使用率当たりの平均同時接続フロー数を算出するものであることを特徴とする請求項１６に記載されたコンピュータ読み取り可能な記録媒体。
【請求項１８】
前記リンク輻輳判定部は、前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、当該リンクにおけるパケット損失率が予め定められた第２のパケット損失率以上で、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定するものであることを特徴とする請求項１６または請求項１７のいずれかに記載されたコンピュータ読み取り可能な記録媒体。
【請求項１９】
前記同時接続フロー数算出部は、パケットヘッダ中の送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号及びトランスポートプロトコルが同一であるものを同一フローと識別し、また同一フローに属するパケットが予め定められた時間以内に検出されない場合に当該フローが終了したと見なすことによって前記平均同時接続フロー数を算出するものであることを特徴とする請求項１６乃至請求項１８のいずれか１項に記載されたコンピュータ読み取り可能な記録媒体。
【請求項２０】
前記同時接続フロー数算出部は、ＴＣＰパケット中のＳＹＮパケット及びＦＩＮパケットを検出することによって前記平均同時接続フロー数を算出するものであることを特徴とする請求項１６乃至請求項１８のいずれか１項に記載されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はネットワーク上で輻輳が発生しているかどうかを判定するリンク輻輳判定装置に関し、特にＩＰネットワークのリンクの輻輳状態を検出するリンク輻輳判定装置に適用して有効な技術に関するものである。
【０００２】
【従来の技術】
従来、種々のデータ処理でＩＰ（Internet Protocol）ネットワークが用いられる様になってきており、ＩＰネットワークの重要性が高まってきている。その様なＩＰネットワークが多くの処理で用いられ、ネットワーク上を送受信されるパケットの数が増加すると、入力パケット量がリンクの帯域を越え輻輳が生じる場合がある。この輻輳はネットワークの機能に多大な悪影響を与える為、ネットワーク上で輻輳が発生している場合にはこれをできるだけ早く検出し、これを解消する必要がある。
現状のＩＰネットワーク管理においては、あるリンクが輻輳しているか否かは主にリンク使用率から判定している。またリンクを通過するフローのスループットを測定し、その平均等の統計値がある閾値以下になった場合を輻輳状態と判定する方法も考えられる。
【０００３】
【発明が解決しようとする課題】
前記従来のＩＰネットワーク管理において、あるリンクが輻輳しているか否かをリンク使用率から判定した場合、リンク使用率とユーザの体感するスループット等の品質との関連が不明である為、輻輳状態と判定する使用率を具体的に特定することが困難であった。
【０００４】
またリンクを通過するフローのスループットを測定し、その平均等の統計値がある閾値以下になった場合を輻輳状態と判定する方法では、１）スループットの測定は、当該リンク上を通過する全てのパケットをキャプチャしフローを組み上げてスループットを算出するか、若しくは当該リンクの前段か後段若しくは両方に試験パケット送受信機を設置して、試験パケットを送信することによってスループット測定を能動的に行う必要があり、一般的にこれは困難である、２）当該リンクがボトルネックでない場合であっても、当該リンクを通過するフローが通過する前後のネットワークの状態によって平均スループットはネットワーク毎に異なり、具体的な閾値の特定が困難である、という問題があった。
【０００５】
本発明の目的は上記問題を解決し、リンクが輻輳しているか否かや品質の劣化原因が当該リンクであるか否かを的確に判定することが可能な技術を提供することにある。
【０００６】
【課題を解決するための手段】
本発明は、ネットワーク上で輻輳が発生しているかどうかを判定するリンク輻輳判定装置において、予め定められた時間間隔におけるリンク平均使用率とそのリンクを通過する平均同時接続フロー数を観測してリンク輻輳状態を判定するものである。
【０００７】
本発明では上記の目的を達成する為、あるリンクを通過するフローのスループットの平均は当該リンクがボトルネックとなっていない場合には負荷に係わらず一定であり、かつ同時接続フロー数とリンク平均使用率は比例関係となること、また当該リンクがボトルネックとなる場合には平均スループットの劣化が観測され、同時接続フロー数がリンク平均使用率に対して、非線形的に増加するという現象を用いて、同時接続フロー数とリンク平均使用率の関係を観測することにより、当該リンクがボトルネックか否かを判定する。
【０００８】
すなわち本発明では、予め定められた時間間隔におけるリンク平均使用率を算出すると共に、前記リンクを通過する平均同時接続フロー数を算出し、前記算出したリンク平均使用率が、予め定められた、ボトルネックと成りえない第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出しておく。
【０００９】
次に、前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合に当該リンクが輻輳状態であると判定する。
【００１０】
また当該リンクにおけるパケット損失率を用い、そのリンクにおけるパケット損失率が予め定められた第１のパケット損失率未満の場合に前記リンク平均使用率当たりの平均同時接続フロー数を算出したり、そのリンクにおけるパケット損失率が予め定められた第２のパケット損失率以上である場合にリンク輻輳状態と判定することとしても良い。
【００１１】
またパケットヘッダ中の送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号及びトランスポートプロトコルが同一であるものを同一フローと識別し、また同一フローに属するパケットが予め定められた時間以内に検出されない場合に当該フローが終了したと見なすことによって前記平均同時接続フロー数を算出したり、ＴＣＰ（Transmission Control Protocol）パケット中のＳＹＮパケット及びＦＩＮパケットを検出することによって前記平均同時接続フロー数を算出することとしても良い。
【００１２】
以上の様に本発明のリンク輻輳判定装置によれば、予め定められた時間間隔におけるリンク平均使用率とそのリンクを通過する平均同時接続フロー数を観測してリンク輻輳状態を判定するので、リンクが輻輳しているか否かや品質の劣化原因が当該リンクであるか否かを的確に判定することが可能である。
【００１３】
【発明の実施の形態】
以下にネットワーク上で輻輳が発生しているかどうかを判定する一実施形態のリンク輻輳判定装置について説明する。
【００１４】
図１は本実施形態のＩＰネットワークの基本構成の一例を示す図である。図１に示す様にリンク輻輳判定装置１００はノード間のリンクに挿入される形態で利用され、予め定められた時間間隔におけるリンク平均使用率とそのリンクを通過する平均同時接続フロー数を観測してリンク輻輳状態を判定する。
【００１５】
図２は本実施形態のリンク輻輳判定装置１００の概略構成を示す図である。図２に示す様に本実施形態のリンク輻輳判定装置１００は、パケットヘッダ解析部２０１と、リンク使用率算出部２０２と、同時接続フロー数算出部２０３と、同時接続フロー数／使用率採用可否判断部２０４と、使用率当たりの同時接続フロー数算出部２０５と、リンク輻輳判定部２０６とを有している。
【００１６】
パケットヘッダ解析部２０１は、前段ノードから到着したパケットのヘッダを解析してヘッダ情報を読み取った後に当該パケットを後段ノードへ送信する処理部である。リンク使用率算出部２０２は、予め定められた時間間隔におけるリンク平均使用率を算出する処理部である。
【００１７】
同時接続フロー数算出部２０３は、前記リンクを通過する平均同時接続フロー数を算出する処理部である。同時接続フロー数／使用率採用可否判断部２０４は、前記算出したリンク平均使用率が予め定めておいた第１のリンク平均使用率未満かどうかをチェックする処理部である。
【００１８】
使用率当たりの同時接続フロー数算出部２０５は、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出する処理部である。
【００１９】
リンク輻輳判定部２０６は、前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定する処理部である。
【００２０】
リンク輻輳判定装置１００をパケットヘッダ解析部２０１、リンク使用率算出部２０２、同時接続フロー数算出部２０３、同時接続フロー数／使用率採用可否判断部２０４、使用率当たりの同時接続フロー数算出部２０５及びリンク輻輳判定部２０６として機能させる為のプログラムは、ＣＤ−ＲＯＭ等の記録媒体に記録され磁気ディスク等に格納された後、メモリにロードされて実行されるものとする。なお前記プログラムを記録する記録媒体はＣＤ−ＲＯＭ以外の他の記録媒体でも良い。また前記プログラムを当該記録媒体から情報処理装置にインストールして使用しても良いし、ネットワークを通じて当該記録媒体にアクセスして前記プログラムを使用するものとしても良い。
【００２１】
図３は本実施形態のパケットヘッダ解析処理の処理手順を示すフローチャートである。図３に示す様にリンク輻輳判定装置１００のパケットヘッダ解析部２０１は、前段ノードから到着したパケットのヘッダを解析してヘッダ情報を読み取った後に当該パケットを後段ノードへ送信する処理を行う。
【００２２】
ステップ３０１でリンク輻輳判定装置１００のパケットヘッダ解析部２０１は、前段ノードからパケットが到着しているかどうかを調べ、パケットが到着している場合にはステップ３０２へ進む。
【００２３】
ステップ３０２では、前記到着したパケットのパケットヘッダを解析して、パケットサイズ、送信ＩＰアドレス、受信ＩＰアドレス、トランスポートプロトコル種別、送信ポート番号、受信ポート番号、ＴＣＰフラグ等のヘッダ情報を読み取る。ステップ３０３では、前記ヘッダ情報の読み取りを行ったパケットを後段ノードへ送信する。
【００２４】
ステップ３０４では、前記読み取ったパケットサイズをリンク使用率算出部２０２へ通知する。ステップ３０５では、前記読取った送信ＩＰアドレス、受信ＩＰアドレス、トランスポートプロトコル種別、送信ポート番号、受信ポート番号、ＴＣＰフラグといったヘッダ情報を同時接続フロー数算出部２０３に通知する。
【００２５】
図４は本実施形態のリンク使用率算出処理の処理手順を示すフローチャートである。図４に示す様にリンク輻輳判定装置１００のリンク使用率算出部２０２は、予め定められた時間間隔におけるリンク平均使用率を算出する処理を行う。
【００２６】
ステップ４０１でリンク輻輳判定装置１００のリンク使用率算出部２０２は、パケットヘッダ解析部２０１からパケットサイズが通知されているかどうかを調べ、パケットサイズが通知されている場合にはステップ４０２へ進む。ステップ４０２では、前記通知されたパケットサイズと以前に通知されているパケットサイズとの和を求める。
【００２７】
ステップ４０３では、予め定められた所定の時間t0が経過しているかどうかを調べ、所定の時間t0が経過している場合にはステップ４０４へ進む。
ステップ４０４では、所定の時間t0の間に通過したパケットサイズの和をt0で割ったものを更にリンク帯域で割ることによってt0毎のリンク平均使用率ρを算出する。ステップ４０５では、前記算出したリンク平均使用率ρを、同時接続フロー数／使用率採用可否判断部２０４及びリンク輻輳判定部２０６に通知する。ステップ４０６では、前記算出したパケットサイズの和を格納している変数を初期化してステップ４０１へ戻る。
【００２８】
図５は本実施形態の同時接続フロー数算出処理の処理手順を示すフローチャートである。図５に示す様にリンク輻輳判定装置１００の同時接続フロー数算出部２０３は、前記リンクを通過する平均同時接続フロー数を算出する処理を行う。
【００２９】
ステップ５０１でリンク輻輳判定装置１００の同時接続フロー数算出部２０３は、パケットヘッダ解析部２０１から送信ＩＰアドレス、受信ＩＰアドレス、トランスポートプロトコル種別、送信ポート番号、受信ポート番号、ＴＣＰフラグといったヘッダ情報が通知されているかどうかを調べ、前記ヘッダ情報が通知されている場合にはステップ５０２へ進む。
【００３０】
ステップ５０２では、前記通知されたヘッダ情報と以前に通知されたヘッダ情報とを比較して、前記通知された送信ＩＰアドレス、受信ＩＰアドレス、トランスポートプロトコル種別、送信ポート番号、受信ポート番号の５つの値が新規のものであるかどうかを調べ、新規のものである場合には新しいフローの発生と判断してステップ５０３へ進み、ステップ５０３では、同時接続フロー数カウンタを「１」増加させる。
【００３１】
ステップ５０４では、既存フローに属するパケットが予め定めておいたt_fl時間到着していないかどうかを調べ、前記パケットがt_fl時間到着していない場合には当該フローが終了したと判断してステップ５０５へ進み、同時接続フロー数カウンタを「１」減ずる。
【００３２】
ステップ５０６では、予め定められた所定の時間t0が経過しているかどうかを調べ、所定の時間t0が経過している場合にはステップ５０７へ進む。ステップ５０７では、前記の同時接続フロー数カウンタの平均値を算出して平均同時接続フロー数Ｎとし、ステップ５０８では、前記算出した平均同時接続フロー数Ｎを同時接続フロー数／使用率採用可否判断部２０４及びリンク輻輳判定部２０６に通知する。
【００３３】
図６は本実施形態の使用率当たりの同時接続フロー数算出処理の処理手順を示すフローチャートである。図６に示す様にリンク輻輳判定装置１００の使用率当たりの同時接続フロー数算出部２０５は、前記算出したリンク平均使用率が予め定められた第１のリンク平均使用率未満である場合に、リンク平均使用率当たりの平均同時接続フロー数を算出する処理を行う。
【００３４】
ステップ６０１でリンク輻輳判定装置１００の同時接続フロー数／使用率採用可否判断部２０４は、リンク使用率算出部２０２や同時接続フロー数算出部２０３からリンク平均使用率ρ及び平均同時接続フロー数Ｎが通知されているかどうかを調べ、リンク平均使用率ρ及び平均同時接続フロー数Ｎが通知されている場合にはステップ６０２へ進む。
【００３５】
ステップ６０２では、前記通知されたリンク平均使用率ρが予め定めておいた第１のリンク平均使用率である閾値ρ_0未満であるかどうかを調べ、リンク平均使用率ρが閾値ρ_0未満である場合にはステップ６０３へ進む。ここで前記閾値ρ_0はボトルネックと成り得ないリンク平均使用率であるものとする。ステップ６０３では、前記通知された値（ρ、Ｎ）を使用率当たりの同時接続フロー数算出部２０５に通知する。
【００３６】
ステップ６０４で使用率当たりの同時接続フロー数算出部２０５は、前記通知されたリンク平均使用率ρ及び平均同時接続フロー数Ｎを以下の数１に代入し、リンク平均使用率当たりの平均同時接続フロー数Ｒを更新する。ここで数１のａは平滑化パラメータである。
【００３７】
【数１】
Ｒ←（１−ａ）×Ｒ＋Ｎ／ρ×ａ
【００３８】
図７は本実施形態のリンク輻輳判定処理の処理手順を示すフローチャートである。図７に示す様にリンク輻輳判定装置１００のリンク輻輳判定部２０６は、前記算出したリンク平均使用率が予め定められた第２のリンク平均使用率以上であり、前記算出した平均同時接続フロー数が、前記算出したリンク平均使用率当たりの平均同時接続フロー数と前記算出したリンク平均使用率との積よりも大きい場合にリンク輻輳状態と判定する処理を行う。
【００３９】
ステップ７０１でリンク輻輳判定装置１００のリンク輻輳判定部２０６は、リンク使用率算出部２０２や同時接続フロー数算出部２０３からリンク平均使用率ρ及び平均同時接続フロー数Ｎが通知されているかどうかを調べ、リンク平均使用率ρ及び平均同時接続フロー数Ｎが通知されている場合にはステップ７０２へ進む。
【００４０】
ステップ７０２では、前記通知されたリンク平均使用率ρが予め定めておいた第２のリンク平均使用率である閾値ρ_1以上であるかどうかを調べ、リンク平均使用率ρが閾値ρ_1以上である場合にはステップ７０３へ進む。ここで閾値ρ_1は前記閾値ρ_0よりも大きい値であるものとするが、閾値ρ_0と同じ値を用いても良い。
【００４１】
ステップ７０３では、前記通知された平均同時接続フロー数Ｎが以下の数２を満たすかどうかを調べ、数２を満たす場合にはステップ７０４へ進む。ここで、数２のＲは使用率当たりの同時接続フロー数算出部２０５によって算出されたリンク平均使用率当たりの平均同時接続フロー数であり、εは予め定めておいた定数である。
【００４２】
【数２】
Ｎ≧ρ×Ｒ×（１＋ε）
【００４３】
ステップ７０４では、当該リンクが輻輳状態であると判定し、そのリンクが輻輳状態であることを示す判定結果をリンク輻輳判定装置１００の出力装置に出力する。
【００４４】
図８は本実施形態のパケット損失率を考慮した使用率当たりの同時接続フロー数算出処理の処理手順を示すフローチャートである。図８に示す様にリンク輻輳判定装置１００の使用率当たりの同時接続フロー数算出部２０５は、そのリンクにおけるパケット損失率が予め定められた第１のパケット損失率未満であるかを考慮して、リンク平均使用率当たりの平均同時接続フロー数を算出する処理を行っても良い。
【００４５】
すなわちステップ８０１で使用率当たりの同時接続フロー数算出部２０５は、リンク輻輳判定装置１００に接続されているノードから通知されたパケット損失率Ｌが予め定めておいた第１のパケット損失率である閾値Ｌ0未満であるかどうかを調べ、パケット損失率Ｌが閾値Ｌ0未満である場合にはステップ６０３へ進む。なお他の処理ステップは図６で説明したものと同様の処理を行うものとする。
【００４６】
図９は本実施形態のパケット損失率を考慮したリンク輻輳判定処理の処理手順を示すフローチャートである。図９に示す様にリンク輻輳判定装置１００のリンク輻輳判定部２０６は、そのリンクにおけるパケット損失率が予め定められた第２のパケット損失率以上であるかを考慮して、リンク輻輳状態の判定を行っても良い。
【００４７】
すなわちステップ９０１でリンク輻輳判定部２０６は、リンク輻輳判定装置１００に接続されているノードから通知されたパケット損失率Ｌが予め定めておいた第２のパケット損失率である閾値Ｌ1以上であるかどうかを調べ、パケット損失率Ｌが閾値Ｌ1以上である場合にはステップ７０３へ進む。ここで閾値Ｌ1は前記閾値Ｌ0よりも大きい値であるものとするが、閾値Ｌ0と同じ値を用いても良い。なお他の処理ステップは図７で説明したものと同様の処理を行うものとする。また図８のパケット損失率を考慮した使用率当たりの同時接続フロー数算出処理と、図９のパケット損失率を考慮したリンク輻輳判定処理とを組み合わせても良い。
【００４８】
図１０は本実施形態のＳＹＮパケット及びＦＩＮパケットの検出による同時接続フロー数算出処理の処理手順を示すフローチャートである。図１０に示す様にリンク輻輳判定装置１００の同時接続フロー数算出部２０３は、トランスポートプロトコルがＴＣＰである場合にＳＹＮパケット及びＦＩＮパケットを検出して前記リンクを通過する平均同時接続フロー数を算出しても良い。
【００４９】
すなわちステップ１００１でリンク輻輳判定装置１００の同時接続フロー数算出部２０３は、パケットヘッダ解析部２０１から送信ＩＰアドレス、受信ＩＰアドレス、トランスポートプロトコル種別、送信ポート番号、受信ポート番号、ＴＣＰフラグといったヘッダ情報が通知されているかどうかを調べ、前記ヘッダ情報が通知されている場合にはステップ１００２へ進む。
【００５０】
ステップ１００２では、前記通知されたヘッダ情報のＴＣＰフラグ中のＳＹＮビットがセットされているかどうかを調べ、ＳＹＮビットがセットされている場合には新しいフローの発生と判断してステップ１００３へ進み、ステップ１００３では、同時接続フロー数カウンタを「１」増加させる。
【００５１】
ステップ１００４では、前記通知されたヘッダ情報のＴＣＰフラグ中のＦＩＮビットがセットされているかどうかを調べ、ＦＩＮビットがセットされている場合には当該フローが終了したと判断してステップ１００５へ進み、同時接続フロー数カウンタを「１」減ずる。
【００５２】
ステップ１００６では、予め定められた所定の時間t0が経過しているかどうかを調べ、所定の時間t0が経過している場合にはステップ１００７へ進む。ステップ１００７では、前記の同時接続フロー数カウンタの平均値を算出して平均同時接続フロー数Ｎとし、ステップ１００８では、前記算出した平均同時接続フロー数Ｎを同時接続フロー数／使用率採用可否判断部２０４及びリンク輻輳判定部２０６に通知する。
【００５３】
図１１は本実施形態のＳＹＮパケット及びＦＩＮパケットの検出による同時接続フロー数カウンタ増減の一例を示す図である。図１１に示す様にこの方法ではＳＹＮパケットが検出された場合には同時接続フロー数カウンタを「１」増加させ、ＦＩＮパケットが検出された場合には同時接続フロー数カウンタを「１」減少させる。
【００５４】
図１２は本実施形態のあるリンクを通過するフローの同時接続数、その平均スループット、使用率の関係を示す図である。図１２に示した関係は、現在のインターネット上のリンクにおいて上記３個の値を測定した場合に一般的に得られるものである。
【００５５】
あるリンクがボトルネックとなっていない、使用率がある値以下の領域では、当該リンクを通過するフローのスループットの平均は一定であり、かつ同時接続フロー数と使用率はほぼ比例関係となり、また当該リンクがボトルネックとなる、高使用率の領域では平均スループットが劣化し、同時接続フロー数が使用率に対して非線形的に増加する。従って、本実施形態において説明した様に、リンクが輻輳しているか否かは使用率と同時接続フロー数の関係を分析することによって判定可能である。
【００５６】
前記の様に本実施形態では、観測が簡易な同時接続フロー数とリンク平均使用率、若しくはパケット損失率という値のみからそれらの関係を算出することにより、当該リンクが輻輳しているか否か品質の劣化原因が当該リンクであるか否かを判定するリンク輻輳判定装置を提供することができる。
【００５７】
以上説明した様に本実施形態のリンク輻輳判定装置によれば、予め定められた時間間隔におけるリンク平均使用率とそのリンクを通過する平均同時接続フロー数を観測してリンク輻輳状態を判定するので、リンクが輻輳しているか否かや品質の劣化原因が当該リンクであるか否かを的確に判定することが可能である。
【００５８】
【発明の効果】
本発明によれば予め定められた時間間隔におけるリンク平均使用率とそのリンクを通過する平均同時接続フロー数を観測してリンク輻輳状態を判定するので、リンクが輻輳しているか否かや品質の劣化原因が当該リンクであるか否かを的確に判定することが可能である。
【図面の簡単な説明】
【図１】本実施形態のＩＰネットワークの基本構成の一例を示す図である。
【図２】本実施形態のリンク輻輳判定装置１００の概略構成を示す図である。
【図３】本実施形態のパケットヘッダ解析処理の処理手順を示すフローチャートである。
【図４】本実施形態のリンク使用率算出処理の処理手順を示すフローチャートである。
【図５】本実施形態の同時接続フロー数算出処理の処理手順を示すフローチャートである。
【図６】本実施形態の使用率当たりの同時接続フロー数算出処理の処理手順を示すフローチャートである。
【図７】本実施形態のリンク輻輳判定処理の処理手順を示すフローチャートである。
【図８】本実施形態のパケット損失率を考慮した使用率当たりの同時接続フロー数算出処理の処理手順を示すフローチャートである。
【図９】本実施形態のパケット損失率を考慮したリンク輻輳判定処理の処理手順を示すフローチャートである。
【図１０】本実施形態のＳＹＮパケット及びＦＩＮパケットの検出による同時接続フロー数算出処理の処理手順を示すフローチャートである。
【図１１】本実施形態のＳＹＮパケット及びＦＩＮパケットの検出による同時接続フロー数カウンタ増減の一例を示す図である。
【図１２】本実施形態のあるリンクを通過するフローの同時接続数、その平均スループット、使用率の関係を示す図である。
【符号の説明】
１００…リンク輻輳判定装置、２０１…パケットヘッダ解析部、２０２…リンク使用率算出部、２０３…同時接続フロー数算出部、２０４…同時接続フロー数／使用率採用可否判断部、２０５…使用率当たりの同時接続フロー数算出部、２０６…リンク輻輳判定部。
【図１】
0003672497.tif 000002
【図２】
0003672497.tif 000003
【図３】
0003672497.tif 000004
【図４】
0003672497.tif 000005
【図５】
0003672497.tif 000006
【図６】
0003672497.tif 000007
【図７】
0003672497.tif 000008
【図８】
0003672497.tif 000009
【図９】
0003672497.tif 000010
【図１０】
0003672497.tif 000011
【図１１】
0003672497.tif 000012
【図１２】
0003672497.tif 000013