(57)【要約】【課題】ネットワークの通信品質の計測精度が向上し、かつ、同通信品質に関する統計情報を管理するためのテーブルを小規模にできるノード装置を提供する。【解決手段】Ｚ−ｌｉｓｔ２１２に重要度を判定するためのデータがあり、重要度判別部２１３でＺ−ｌｉｓｔ２１２から該当フローの重要度が判別される。Ｅ−ｌｉｓｔ２２２で監視重要度の高いフローの統計データが格納され、入替え判定部２２１で該当フローの重要度とＥ−ｌｉｓｔ２２２内の重要度から入替え判定が行われる。振分部２３１で入替え判定部２２１からのデータがパケット情報と統計情報で各処理部に振り分けられ、統計情報品質計測部２３２で、統計情報で伝達された部分の品質が計測され、通常パケット品質計測部２３３で、パケット情報で伝達された部分の品質が計測され、統合品質計算部２３４で通常パケット及び統計情報の各品質が合算されて品質結果２３５で記録される。
2008108403.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの通信品質を観測するノード装置であって、
ネットワークに流れるパケットを観測するパケット観測手段と、
該パケット観測手段により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類手段と、
該パケット分類手段により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出手段と、
ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを有し、前記統計情報を検索して既に該統計情報が作成されている場合には当該統計情報を更新し、該統計情報が作成されていない場合には前記監視重要度に基づいて前記統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理手段と
を備えてなることを特徴とするノード装置。
【請求項２】
前記パケット観測手段は、
前記ネットワークを通過する一部のパケットを観測対象とすることを特徴とする請求項１記載のノード装置。
【請求項３】
前記監視重要度算出手段は、
過去に到着したパケットの履歴に基づいて分類種別の到着割合又は到着数を計算し、この計算結果に基づいて前記監視重要度を算出することを特徴とする請求項１又は２記載のノード装置。
【請求項４】
前記監視重要度算出手段は、
過去に到着したパケットの履歴を格納するテーブルを備え、当該パケットの分類が前記パケットの履歴に存在するか否かを検索することによって、当該パケットの分類の到着割合又は到着数を計算することを特徴とする請求項１から請求項３のいずれかに記載のノード装置。
【請求項５】
前記監視重要度算出手段は、
過去に到着したパケットの履歴を格納するテーブルを備え、該テーブルのエントリとして、フロー識別を登録するためのフローＩＤ、及びエントリが更新又は参照された回数を含むことを特徴とする請求項１から請求項４のいずれかに記載のノード装置。
【請求項６】
前記統計情報管理手段は、
前記統計情報管理テーブルのエントリ情報の１つとして、カウンタ値又は監視重要度のいずれか１つを有し、到着したパケットが前記統計情報管理テーブルに存在する場合には、該当する分類の統計情報を更新し、該統計情報管理テーブルに存在しない場合には、前記エントリ情報のカウンタ値又は監視重要度に基づいて、到着したパケットを新規に登録し、登録されていたエントリ情報をテーブルから追い出すことを特徴とする請求項１から請求項３のいずれかに記載のノード装置。
【請求項７】
前記統計情報管理手段は、
前記統計情報管理テーブルに到着したパケットの分類が存在しないとき、該統計情報テーブルのエントリを選択し、このエントリに記載されている監視重要度に基づいてエントリの入替え確率を決定することを特徴とする請求項１、２、３又は６に記載のノード装置。
【請求項８】
ネットワークの通信品質を観測するノード装置に用いられる統計情報管理テーブルの入替え方法であって、
ネットワークに流れるパケットを観測するパケット観測ステップと、
該パケット観測処理により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類ステップと、
該パケット分類処理により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出ステップと、
ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを設け、前記統計情報を検索して既に該統計情報が作成されている場合には当該統計情報を更新し、該統計情報が作成されていない場合には前記監視重要度に基づいて統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理ステップと
を有することを特徴とする統計情報管理テーブルの入替え方法。
【請求項９】
前記パケット観測ステップは、
前記ネットワークを通過する一部のパケットを観測対象とすることを特徴とする請求項８に記載の統計情報管理テーブルの入替え方法。
【請求項１０】
前記監視重要度算出ステップは、
過去に到着したパケットの履歴に基づいて分類種別の到着割合又は到着数を計算し、この計算結果に基づいて前記監視重要度を算出することを特徴とする請求項８又は請求項９に記載の統計情報管理テーブルの入替え方法。
【請求項１１】
前記監視重要度算出ステップは、
過去に到着したパケットの履歴を格納するテーブルを備え、当該パケットの分類が前記パケットの履歴に存在するか否かを検索することによって、当該パケットの分類の到着割合又は到着数を計算する構成とされていることを特徴とする請求項８から請求項１０のいずれかに記載の統計情報管理テーブルの入替え方法。
【請求項１２】
前記監視重要度算出ステップは、
過去に到着したパケットの履歴を格納するテーブルを備え、該テーブルのエントリとして、フロー識別を登録するためのフローＩＤ、及びエントリが更新又は参照された回数を含むことを特徴とする請求項８から請求項１１のいずれかに記載の統計情報管理テーブルの入替え方法。
【請求項１３】
前記統計情報管理ステップは、
前記統計情報管理テーブルのエントリ情報の１つとして、カウンタ値又は監視重要度のいずれか１つを有し、到着したパケットが前記統計情報管理テーブルに存在する場合には、該当する分類の統計情報を更新し、該統計情報管理テーブルに存在しない場合には、前記エントリ情報のカウンタ値又は監視重要度に基づいて、到着したパケットを新規に登録し、登録されていたエントリ情報をテーブルから追い出すことを特徴とする請求項８から請求項１０のいずれかに記載の統計情報管理テーブルの入替え方法。
【請求項１４】
前記統計情報管理ステップは、
前記統計情報管理テーブルに到着したパケットの分類が存在しないとき、該統計情報テーブルのエントリを選択し、このエントリに記載されている監視重要度に基づいてエントリの入替え確率を決定することを特徴とする請求項８、９、１０又は１３記載の統計情報管理テーブルの入替え方法。
【請求項１５】
ネットワークの通信品質を観測する通信システムであって、
ネットワークに流れるパケットを観測するパケット観測手段と、
該パケット観測手段により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類手段と、
該パケット分類手段により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出手段と、
ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを有し、前記統計情報を検索して既に該統計情報が作成されている場合には当該統計情報を更新し、該統計情報が作成されていない場合には前記監視重要度に基づいて前記統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理手段と
を備えてなることを特徴とする通信システム。
【請求項１６】
ネットワークの通信品質を観測するノード装置のプログラムであって、前記プログラムは前記ノード装置に
ネットワークに流れるパケットを観測するパケット観測処理と、
該パケット観測処理により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類処理と、
該パケット分類処理により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出処理と、
ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを設け、前記統計情報を検索して既に該統計情報が作成されている場合には当該統計情報を更新し、該統計情報が作成されていない場合には前記監視重要度に基づいて統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理処理と
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ノード装置、及び該ノード装置に用いられる統計情報管理テーブルの入替え方法に係り、特に、ネットワークの通信品質を計測し、計測結果に基づいてトラフィック制御を行う場合に用いて好適なノード装置、及び該ノード装置に用いられる統計情報管理テーブルの入替え方法に関する。
【背景技術】
【０００２】
ネットワークの通信品質を計測する装置や、この計測結果に基づいてトラフィック制御を行うノード装置では、装置内で通信品質に関する統計情報を管理するテーブルが設けられ、この統計情報に基づいて、その後のトラフィック制御の処理内容が決定されるようになっているものがある。【０００３】
従来、この種の技術としては、たとえば、非特許文献１に記載されたものがある。
非特許文献１（Internet
Engineering Task Force のＲＦＣ３９５４）に記載されたネットフロー（ＮｅｔＦｌｏｗ）では、ノード装置内で統計情報を作成してネットワークの品質を計測する技術が示されている。すなわち、ネットフローは、ルータあるいは計測プローブ内に設けられてネットワークの品質を計測する機構であり、次の機能（１），（２），（３）を有している。
（１）ルータのインタフェースを通過する全てのパケット、又は一部のパケットをキャプチャする機能
（２）キャプチャしたパケットからルータ内に存在する統計情報を更新する機能
（３）一定期間毎に統計情報の結果から、ＲＦＣ３９５４などで決められたネットフローのフォーマットに従ったパケットを生成し、データ解析装置へ送付する機能【０００４】
これらの機能により、データ解析装置では、ネットフロー機構が存在するルータを通過したパケットの情報が収集され、ネットワークの品質（主に通信量）が監視される。ここで、上記機能（２）については、データ解析装置内に設けられているテーブルにより、フロー毎に１エントリとなるような統計情報が記録されることにより、同統計情報が更新されるようになっている。このエントリ量は有限であるため、装置を長期間運用するためには、エントリ情報を逐次入れ替えていく必要がある。この方法は、実装依存であるが、一般的には、そのフロー情報の通信が一定時間なかった場合にエントリから削除するインアクティブタイマや、通信が継続していても一定時間毎にエントリ情報をデータ解析装置へ送付あるいは削除するアクティブタイマ、また、ＴＣＰ（Transmission Control Protocol ）の“ＦＩＮ”や“ＲＳＴ”のフラグ情報を参照して通信が終わった場合に削除する方法、キャッシュが一杯になったときに、先に登録されたエントリから削除していくＦＩＦＯ（First In First Out）方式や、最後に登録されたエントリから削除していくＬＩＦＯ（Last In First Out ）などの方式がある。【０００５】
また、非特許文献２に記載されたネットワーク品質制御技術では、装置内で統計情報を作成し、その結果に基づいてトラフィック制御を行う装置に関する技術が示されている。
すなわち、この装置は、たとえばルータのようなトラフィック転送／制御を行う装置であり、次の機能（１），（２），（３），（４）を有している。
（１）入力パケットの出力方路の決定
（２）入力パケットに基づいて、装置内に存在する統計情報の更新
（３）統計情報に基づいて、入力パケットの廃棄の可否の決定
（４）（１）の結果及び（３）の結果に基づいて、パケットを処理（出力方路に転送か又はパケット廃棄）
ここで、この装置では、フロー毎に１エントリとなるような統計情報を記録するテーブルが設けられているが、全てのフローの統計情報を管理すると、膨大な量のエントリが必要となるため、パケットのサンプリングを行うことにより、観測するパケットの量を減らし、少なくなったパケット量に基づいて、フローの統計情報が作成される。
【非特許文献１】B.Claise, ”Cisco Systems NetFlowServices Export Version 9, ”IETF,RFC3954,October 2004.
【非特許文献２】林理恵、宮村崇、塩本公平、漆谷重雄、“エレファントフローのリアルタイム測定によるネットワーク品質制御技術の検討、”信学技法（NS2005-117、CQ2005−71、TM2005-11 ）、2005年11月
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記従来の技術では、次のような問題点があった。
すなわち、非特許文献１に記載されたネットフローでは、基本的に全てのフローがテーブルの登録対象となっており、流れているフローの本数に対して、テーブル量が小さい場合、エントリの入替えが頻繁に発生するため、情報が一度テーブルに登録されてから削除されるまでの時間が短くなり、短期間の統計情報しか集計できない可能性がある。これに伴い、データ解析装置での処理負荷が大きくなったり、計測精度が低下したりするという問題点がある。また、このネットフローでは、全フローに対する監視重要度を等しく扱っている。このため、統計情報を管理するテーブルの規模を大きくしてエントリ入替えが頻繁に発生しないようにする必要があるが、実現は容易ではない。【０００７】
また、非特許文献２に記載されたトラフィック制御を行う装置では、パケットのサンプリングにより、監視するパケット数を減らすことは可能であるが、監視したフローに関しては、全てテーブルに保持する必要があるので、ある程度の大きさのフロー情報をもつ必要がある。また、この装置でも、上記ネットフローと同様に、全フローに対する監視重要度を等しく扱っている。このため、テーブルの規模を大きくする必要があるが、実現は容易ではない。【０００８】
この発明は、上述の事情に鑑みてなされたもので、ネットワークの通信品質の計測精度が向上し、かつ、同通信品質に関する統計情報を管理するためのテーブルを小規模にできるノード装置、及び該ノード装置に用いられる統計情報管理テーブルの入替え方法を提供することを目的としている。
【課題を解決するための手段】
【０００９】
上記課題を解決するための本発明は、ネットワークの通信品質を観測するノード装置に係り、前記ネットワークに流れるパケットを観測するパケット観測手段と、該パケット観測手段により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類手段と、該パケット分類手段により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出手段と、ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを有し、前記統計情報を検索して既に該統計情報が作成されている場合には、当該統計情報を更新し、該統計情報が作成されていない場合には、前記監視重要度に基づいて前記統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理手段とを備えてなることを特徴とする。【００１０】
上記課題を解決するための本発明は、ネットワークの通信品質を観測するノード装置に用いられる統計情報管理テーブルの入替え方法に係り、前記ネットワークに流れるパケットを観測するパケット観測ステップと、該パケット観測処理により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類ステップと、該パケット分類処理により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出ステップと、ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを設け、前記統計情報を検索して既に該統計情報が作成されている場合には、当該統計情報を更新し、該統計情報が作成されていない場合には、前記監視重要度に基づいて統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理ステップとを行うことを特徴とする。【００１１】
上記課題を解決するための本発明は、ネットワークの通信品質を観測する通信システムであって、ネットワークに流れるパケットを観測するパケット観測手段と、該パケット観測手段により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類手段と、該パケット分類手段により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出手段と、ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを有し、前記統計情報を検索して既に該統計情報が作成されている場合には当該統計情報を更新し、該統計情報が作成されていない場合には前記監視重要度に基づいて前記統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理手段とを備えてなることを特徴とする。【００１２】
上記課題を解決するための本発明は、ネットワークの通信品質を観測するノード装置のプログラムであって、前記プログラムは前記ノード装置に、ネットワークに流れるパケットを観測するパケット観測処理と、該パケット観測処理により観測されたパケットの特定のフィールドを参照し、該フィールドの種類に応じて当該パケットを分類するパケット分類処理と、該パケット分類処理により分類されたパケットの種類毎に監視重要度を算出する監視重要度算出処理と、ネットワークの通信品質に関する統計情報を管理する統計情報管理テーブルを設け、前記統計情報を検索して既に該統計情報が作成されている場合には当該統計情報を更新し、該統計情報が作成されていない場合には前記監視重要度に基づいて統計情報管理テーブルを入れ替えるか否かを判定する統計情報管理処理とを実行させることを特徴とする。
【発明の効果】
【００１３】
本発明は、ネットワークに流れるパケットを観測し、観測したパケットの特定のフィールドが参照されて同フィールドの種類に応じて当該パケットを分類し、分類されたパケットの種類毎に監視重要度を算出する。そして、上記通信品質に関する統計情報が検索されて既に該統計情報が作成されている場合には、当該統計情報を更新し、同統計情報が作成されていない場合には、上記監視重要度に基づいて統計情報管理テーブルを入れ替えるか否かを判定する。これにより、統計情報管理テーブルの規模を大きくすることなく、通信品質の計測精度を向上させることができる。
【図面の簡単な説明】
【００１４】
【図１】この発明のノード装置が用いられる環境を示す模式図である。
【図２】この発明の第１の実施の形態である品質観測端末２に用いられるＥ−ｌｉｓｔとＺ−ｌｉｓｔの登録処理の概要を示す図である。
【図３】この発明の第１の実施の形態である品質観測端末２に用いられるＥ−ｌｉｓｔとＺ−ｌｉｓｔの登録処理の概要を示す図である。
【図４】図１中の品質観測端末２の構成を示すブロック図である。
【図５】品質観測端末２の重要度算出部２１０及び統計情報管理部２２０の動作を説明するフローチャートである。
【図６】この発明のノード装置が用いられる他の環境を示す模式図である。
【図７】この発明の第２の実施の形態におけるＥＺ−ｌｉｓｔの入替え確率を説明する図である。
【図８】Ｅ−ｌｉｓｔ及びＺ−ｌｉｓｔの登録処理の概要を示す図である。
【図９】第２の実施の形態の品質観測端末２ｂの構成を示すブロック図である。
【図１０】品質観測端末２ｂの統計情報管理部２４０の動作を説明するフローチャートである。
【図１１】この発明の第３の実施の形態である品質観測端末の構成を示すブロック図である。
【図１２】品質観測端末２ｃの重要度算出部２１０及び統計管理＆廃棄判定処理２５０の動作を説明するフローチャートである。
【符号の説明】
【００１５】
ＮＷＡ，ＮＷＢ      ネットワーク
２      品質観測端末（ノード装置）
２００      パケット転送部（パケット観測手段、パケット分類手段）
２１０      重要度算出部（監視重要度算出手段）
２１１      検索部（重要度算出部の一部）
２１２      Ｚ−ｌｉｓｔ（重要度算出部の一部）
２１３      重要度判別部（重要度算出部の一部）
２２０      統計情報管理部（統計情報管理手段）
２２１      入替え判定部
２２２      Ｅ−ｌｉｓｔ
２３０      品質計測部
２３１      振分部
２３２      統計情報品質計測部
２３３      通常パケット品質計測部
２３４      統合品質計算部
２３５      品質結果
２４０      統計情報管理部（統計情報管理手段）
２４１      検索部
２４２      ＥＺ−ｌｉｓｔ
２４３      入替え判定部
２４４      入替え確率
２５０      統計管理＆廃棄判定処理（統計情報管理手段）
２５１      入替え判定部
２５２      Ｅ−ｌｉｓｔ
２５３      廃棄判定処理
２６１，２６２      パケット廃棄
【発明を実施するための最良の形態】
【００１６】
ネットワークのトラフィックの分布が均一でないことを利用して、重点的に管理したい項目に対して高い重要度を設定し、その重要度に基づいて当該ノード装置内のテーブルを使用し、重要度の高いフローに絞って詳細なトラフィック統計情報を取り、同トラフィック情報に基づいてパケット廃棄の判定を行うノード装置、及び同ノード装置に用いられる統計情報管理テーブルの入替え方法を提供する。【００１７】
本発明の第１の実施の形態について説明する。
図１は、この発明のノード装置が用いられる環境を示す模式図である。
この環境では、たとえば、パソコンなどの通信端末１ａ，１ｂ，１ｃ，１ｄがネットワークＮＷＡに接続され、同ネットワークＮＷＡには、ノード装置として品質観測端末２が接続されている。品質観測端末２は、ネットワークＮＷＢに接続され、同ネットワークＮＷＢには通信端末１ｅ，１ｆ，１ｇ，１ｈが接続されている。品質観測端末２は、ネットワークＮＷＡとネットワークＮＷＢとの間の通信路に挿入され、同通信路に流れる通信パケットを計測する。この実施では、この品質観測端末２の内部に設けられている通信品質の統計情報を管理する統計情報管理テーブルの入替え方法について説明する。すなわち、通過パケットの履歴に基づいて、ある特定フィールドが同じパケット群に対する観測重要度を決定し、この観測重要度の結果に基づき、品質観測端末２内の統計情報管理テーブルで統計情報を監視するパケット群を決定する。【００１８】
図２及び図３は、この発明の第１の実施の形態である品質観測端末２に用いられるＥ−ｌｉｓｔとＺ−ｌｉｓｔの登録処理の概要を示す図である。図２及び図３では、ある特定フィールドが同じパケット群に対する観測重要度を決定するリストがＺ−ｌｉｓｔ、及び、品質観測端末２内で統計情報を監視するリストがＥ−ｌｉｓｔとして表示されている。【００１９】
図４は、図１中の品質観測端末２の構成を示すブロック図である。
この実施の形態では、特定フィールドが同じパケット群を「フロー」という。ここでのフローの具体例としては、送受信ＩＰアドレス、送受信ポート番号、送受信ＭＡＣアドレス、プロトコルＩＤのいずれか１つ以上の組でパケットをグルーピングすることが考えられる。あるいは、ＩＰ（Internet Protocol ）やＴＣＰなどのプロトコルヘッダに存在するフラグ情報での分類や、ＩＰやＶＬＡＮ（Virtual Local Area Network）やＭＰＬＳ（Multi protocol Label Switching ）などのプロトコルヘッダに存在する優先度情報でグルーピングすることや、これらの組み合わせでグルーピングすることが考えられる。また、こられの番号や分類は、完全に同一なもので分類する方法の他に、複数の範囲を設定し、設定した範囲であれば同一のグループに分類することが考えられる。【００２０】
品質観測端末２は、パケット転送部２００と、重要度算出部２１０と、統計情報管理部２２０と、品質計測部２３０とから構成されている。重要度算出部２１０は、検索部２１１と、重要度を判定するためのデータが存在するＺ−ｌｉｓｔ２１２と、Ｚ−ｌｉｓｔ２１２の結果から該当フローの重要度を判別する重要度判別部２１３とから構成されている。統計情報管理部２２０は、該当フローの重要度とＥ−ｌｉｓｔ２２２内の重要度から入替え判定を行う入替え判定部２２１と、監視重要度の高いフローの統計データが格納されているＥ−ｌｉｓｔ２２２とから構成されている。品質計測部２３０は、統計情報管理部２２０から送付されたデータをパケット情報と統計情報で各処理部に振り分ける振分部２３１と、統計情報で伝達された部分の品質を計測する統計情報品質計測部２３２と、パケット情報で伝達された部分の品質を計測する通常パケット品質計測部２３３と、通常パケットの品質と統計情報の品質を合算する統合品質計算部２３４と、そこで計算された品質情報を記録する品質結果２３５とから構成されている。【００２１】
パケット転送部２００では、ある入口から品質観測端末２に入ってきたパケットを観測し、その結果を重要度算出部２１０と統計情報管理部２２０とへ送付すると同時に、他方の出口からネットワーク中に転送する処理を行う。この処理は、パケット入力毎に行われる。ただし、パケット転送部２００でパケットをサンプリングして間引いて少なくしたパケットを重要度算出部２１０と統計情報管理部２２０とに転送しても良い。【００２２】
重要度算出部２１０では、パケット転送部２００から送付されたパケット情報に基づいて検索部２１１で処理を行う。検索部２１１では、Ｚ−ｌｉｓｔ２１２の検索を行う。Ｚ−ｌｉｓｔ２１２は、ＩＤとカウンタ値Ｃを有するリストであり、パラメータとしてエントリの置換え確率ｑを有している。ＩＤとしては、フロー情報を使用する。フローのＩＤがＺ−ｌｉｓｔ２１２内に存在すれば、該当するＩＤのカウンタ値Ｃを“１”カウントアップする。もし、フローのＩＤがＺ−ｌｉｓｔ２１２内に存在しなければ、Ｚ−ｌｉｓｔ２１２内のＩＤをランダムに選択し、乱数を発生させて置換え確率ｑよりも小さければ、選択されていたＩＤのエントリをＺ−ｌｉｓｔ２１２から追い出して、今回到着したパケットをそのエントリに登録し、カウンタ値として“１”を選択する。乱数発生結果が置換え確率ｑよりも大きければ、Ｚ−ｌｉｓｔ２１２に対する処理は何も行わない。【００２３】
置換えが発生した場合、次式（１）に示すようなレート推定を行う。式（１）では、ｐがＺ−ｌｉｓｔ２１２の平均ヒット率、ｑはＺ−ｌｉｓｔ２１２の置換え確率、Ｃｉは置換えが発生した際に追い出されたフローが有するカウンタ値Ｃ、Ｍはエントリの大きさである。このため、式（１）のレート計算は、同一フローのパケットが到着したときではなく、他フローのパケットが到着した際に行われる。
Ｒi ＝（１−ｐ）・（ｑ／Ｍ）・（Ｃi −１）      …（１）
ここで、Ｚ−ｌｉｓｔ２１２がカウントアップされる場合は、図３中の時刻Ａから時刻Ｃの間、時刻Ｄから時刻Ｅの間、又は、時刻Ｆから時刻Ｈの間のいずれかに相当する。これらのどれに分類されるかは、Ｅ−ｌｉｓｔ２２２の状態によって確定される。ここで、Ｚ−ｌｉｓｔ２１２でカウントアップが発生せず、エントリの入替えが発生する場合は、時刻Ａ，Ｃ，Ｄ，Ｅ，Ｆ，Ｈのいずれかの瞬間に相当する。重要度判定部２１３では、Ｚ−ｌｉｓｔ２１２の値に基づいて重要度Ｆの判定を行う。重要度Ｆの判定方法は、様々な方法が存在する。高レートのフローの監視優先度を上げる場合には、式（１）のＲi の結果を優先度とする。【００２４】
統計情報管理部２２０では、パケット転送部２００からのパケット情報と重要度算出部２１０で計算された重要度とを入力する。入替え判定部では、Ｅ−ｌｉｓｔ２２２の内容と重要度判定部２１３の結果、パケット転送部２００のパケット情報に基づいて処理を決定する。Ｅ−ｌｉｓｔ２２２はフローＩＤと重要度Ｅ値と、統計情報（通信量、パケットロス数、フラグ数など）を組として有するリストである。また、入替え判定部２２１では、Ｅ−ｌｉｓｔ２２２の中で重要度が一番小さいフローＩＤとその重要度Ｅ値とを記憶しておく。ここで記憶している最小重要度のＥ値を、以下、「Ｅｍｉｎ」という。パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２２２に登録されていないフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されていないフローに属する場合には、何もせず、パケット情報を品質計測部２３０に送付する。この際にパケットをサンプリングして一定確率で送付しても良い。これは、図３のタイミングでは、時刻Ａ以前や時刻Ｈ以降に相当する。【００２５】
パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２２２に登録されていないフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されているフローに属する場合には、カウントアップ後のＺ−ｌｉｓｔ２１２の優先度ＦとＥｍｉｎの値とを比較し、優先度Ｆの方がＥｍｉｎよりも大きければ、Ｅｍｉｎを有するフローの情報をＥ−ｌｉｓｔ２２２から削除（削除されるフローからみると、図３中の時刻Ｇに相当）し、登録されていた重要度Ｅと統計情報とを品質計測部２３０へ送付する。そして、現在のフローに関するエントリをＥ−ｌｉｓｔ２２２に登録する（新規登録されるフローからみると、図３中の時刻Ｂに相当）。エントリに登録する際は、フローＩＤには、グループのフロー情報を登録し、重要度Ｅ値は空欄、統計情報はクリア状態（通信量やパケットロス数、フラグ数などを“０”にしておく）に設定する。優先度Ｆの方がＥｍｉｎよりも小さければ、Ｅ−ｌｉｓｔ２２２には何も変更を加えずにパケット情報を品質計測部２３０へ送付する（図３中の時刻Ａから時刻Ｂの間、あるいは時刻Ｇから時刻Ｈの間に相当する）。【００２６】
パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２２２に登録されているフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されていないフローに属する場合、検索部２１１の結果でＺ−ｌｉｓｔ２１２に入替えが発生しなかった場合には、Ｅ−ｌｉｓｔ２２２では、登録されている統計情報を更新する（図３中の時刻Ｃから時刻Ｄの間、あるいは時刻Ｅから時刻Ｆの間に相当）。検索部２１１の結果でＺ−ｌｉｓｔ２１２に入替えが発生した場合には、現在処理中のパケットに属するフローの統計情報を更新する（図３中の時刻Ｄや時刻Ｆに相当）と同時に、Ｚ−ｌｉｓｔ２１２の入替えで追い出されたフローの処理判定を行う。追い出されたフローもＥ−ｌｉｓｔ２２２に存在していた場合、Ｚ−ｌｉｓｔ２１２で追い出された時点のカウンタ値Ｃを使って最終的な重要度Ｆを計算し、その情報をＥ−ｌｉｓｔ２２２の統計情報の重要度Ｅとして記載する（図３中の時刻Ｃや時刻Ｅに相当）。Ｚ−ｌｉｓｔ２１２から追い出されたフローがＥ−ｌｉｓｔ２２２に存在しない場合、処理は行わない。パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２２２に登録されているフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されているフローに属する場合、Ｚ−ｌｉｓｔ２１２を更新すると同時に、Ｅ−ｌｉｓｔ２２２も更新する（図３中の時刻Ｂから時刻Ｃの間、あるいは時刻Ｄから時刻Ｅの間、あるいは時刻Ｆから時刻Ｇの間に相当する）。【００２７】
品質計測部２３０では、振分部２３１にて、統計情報管理部２２０からの情報の分類を行い、パケット情報が到着した場合には通常パケット品質計測部２３３へ、統計情報が到着した場合には統計情報品質計測部２３２へ振分ける。通常パケット品質計測部２３３では、送付されたパケット情報から該当箇所の品質（通信量など）の計測を行い、その結果を統合品質計算部２３４へ送付する。統計情報品質計測部２３２では、送付された統計情報から該当箇所の品質（通信量やパケットロスなど）の計測を行い、その結果を統合品質計測部２３４へ送付する。統合品質計算部２３４では、通常パケット品質計測部２３３及び統計情報品質計算部２３２での結果を合わせて、１つの品質情報を算出し、その結果を品質結果２３５へ記録する。【００２８】
この実施の形態では、品質観測端末２は、ネットワークの回線上に挿入される形態で説明を行ったため、図１に示す環境で用いられものとして説明を行ったが、図６に示すように、ネットワーク中にパケットをコピーするＴＡＰ（ターミナルアダプタ）を挿入したり、ルータやスイッチであるポートのパケットをコピーするミラーポート機能を設定したりすることにより、パケットを観測する形態も可能である。その場合には、図４中のパケット転送部２００は、品質観測端末２外からのパケットを受信する機能を有するものになる。また、重要度算出部２１０、統計情報管理部２２０、及び品質計測部２３０は、全て品質観測端末２の一装置内に設けられているが、それぞれ別の装置内に設けられていてもよく、その場合には各部間の情報伝達は、ネットワークを介して行われる。【００２９】
また、入替え判定部２２１においてＥ−ｌｉｓｔにカウントされなかった情報は、パケット情報として品質計測部２３０へ送付するものとしているが、Ｅ−ｌｉｓｔに登録された重要な情報だけを統計情報として送付するものとしても良い。また、品質計測部２３０で計測する情報として、通信量やパケットロスとしたが、フローのグルーピングを、あるＩＰアドレス群で発生したＴＣＰフラグ情報の数で分類してセキュリティに関する情報を集めるなど、算出する品質情報としては通信量に限らない。また、パケット転送部２００で観測したパケット情報を重要度算出部２１０と統計情報管理部２２０に同時に送付するものとしているが、重要度算出部２１０へ送付し、統計情報管理部２２０に対しては、重要度算出部２１０からフローの重要度と共にパケット情報そのものを送付するようにしても良い。【００３０】
また、高レートのフローの優先度を高い優先度に設定したが、低レートのフローの優先度を上げる場合には、式（１）のＲi の結果の逆数を優先度とする方法も考えられる。さらに、特定のレートを観測する場合には、基準となるレートＲｂを設けておき、計算したＲとＲｂとの差分を取り、その逆数を優先度とする方法も考えられる。さらに、上記優先度計算は、レートであるＲi 値をベースとして計算しているが、カウンタ値Ｃをベースに同様の優先度設定を行っても良い。また、Ｅ−ｌｉｓｔ２２２にフロー情報を登録するタイミングについて、Ｚ−ｌｉｓｔ２１２のカウントアップ中のＣ値から重要度を算出し、Ｅｍｉｎと比較するものとしたが、Ｚ−ｌｉｓｔ２１２からフロー情報が追い出されて最終的なカウンタ値Ｃや重要度ＦとＥｍｉｎを比較するように変更しても良い。その場合は、Ｅ−ｌｉｓｔ２２２にエントリ入替えが発生した際に、新規登録されるフローのパケットは、現在処理中のフローとは異なるため、統計情報はクリア状態にする。重要度Ｅに関しては、Ｚ−ｌｉｓｔ２１２から追い出された際の最終的な重要度が確定しているので、その値を記録する。【００３１】
また、フローの入替えは、パケット転送部２００でパケット観測が行われた場合を説明しているが、Ｅ−ｌｉｓｔ２２２の統計情報をエントリ毎にアクティブタイマ（情報が更新されている状態でも一定間隔毎）やインアクティブタイマ（情報が更新されなくなってから一定時間経過）を起動して、統計情報を品質計測部２３０へ送付する方法も考えられる。その際、Ｅ−ｌｉｓｔ２２２から情報を削除して送付する場合や、情報は削除せずに送付する方法がある。情報がＥ−ｌｉｓｔ２２２から削除される場合には、次のフローがすぐにエントリを埋めるように、重要度を低く、たとえば“０”にしておくことが考えられる。【００３２】
図５は、品質観測端末２の重要度算出部２１０及び統計情報管理部２２０の動作を説明するフローチャートである。
この図を参照して、この例の品質観測端末２に用いられる統計情報管理テーブルの入替え方法の処理内容について説明する。
この品質観測端末２では、ネットワークに流れるパケットが観測され（パケット観測処理）、同パケット観測処理により観測されたパケットの特定のフィールドが参照され、同フィールドの種類に応じて当該パケットが分類され（パケット分類処理）、同パケット分類処理により分類されたパケットの種類毎に監視重要度が算出される（監視重要度算出処理）。そして、通信品質に関する統計情報を管理する統計情報管理テーブルが設けられ、同統計情報が検索されて既に該統計情報が作成されている場合には当該統計情報が更新される一方、同統計情報が作成されていない場合には上記監視重要度に基づいて統計情報管理テーブルを入れ替えるか否かが判定される（統計情報管理処理）。【００３３】
すなわち、パケット転送部２００にパケットが到着すると、その内容が検索部２１１と入替え判定部２２１とに転送されて処理が開始され、ステップＡ１へ遷移する。ステップＡ１では、検索部２１１によりＺ−ｌｉｓｔ２１２の検索が行われ、現在処理中のパケットのフローがＺ−ｌｉｓｔ２１２に登録されているか否かを調べる。登録されている場合にはステップＡ２へ遷移し、登録されていない場合にはステップＡ９へ遷移する。ステップＡ２では、Ｚ−ｌｉｓｔ２１２の更新処理が行われる。具体的には、Ｚ−ｌｉｓｔ２１２のカウンタ値を“１”カウントアップする。そして、重要度判定部２１３が、カウントアップしたフローの暫定的な重要度Ｆを算出する（最終的な重要度は、Ｚ−ｌｉｓｔ２１２から該当フローが追い出された際に決定する）。この処理が終了すると、ステップＡ３へ遷移する。【００３４】
ステップＡ３では、入替え判定部２２１によりＥ−ｌｉｓｔ２２２の検索が行われ、パケット転送部２００から送付されるパケットの属するフローがＥ−ｌｉｓｔ２２２に存在するか否かを検索する。Ｅ−ｌｉｓｔ２２２に存在する場合は、ステップＡ６へ遷移し、存在しない場合にはステップＡ４へ遷移する。ステップＡ４では、Ｅ−ｌｉｓｔ２２２の重要度が一番小さい値Ｅｍｉｎと更新中のＺ−ｌｉｓｔ２１２でカウントアップしたフローの暫定的な重要度Ｆとを比較する。重要度Ｆの方がＥｍｉｎよりも重要度が高い場合にはＥ−ｌｉｓｔ２２２の入替えが発生し、ステップＡ５へ遷移する。Ｅｍｉｎの方が重要度Ｆよりも重要度が高い場合には、入替えは発生せず、ステップＡ８へ遷移する。【００３５】
ステップＡ５では、Ｅｍｉｎに属するフローをＥ−ｌｉｓｔ２２２から追い出し、現在処理中のパケットの属するフローのエントリを作成する。ここで、統計情報はクリア状態、重要度は空欄のままとしておき、ステップＡ７へ遷移する。また、ステップＡ６では、Ｅ−ｌｉｓｔ２２２の通信量のカウントアップや、シーケンス番号のチェックによるパケットロス発生の有無、フラグ情報など、管理している統計情報の更新を行い、処理を終了する。ステップＡ７では、ステップＡ５でＥ−ｌｉｓｔ２２２から追い出されたエントリの情報を品質計測部２３０へ送付して処理を終了する。ステップＡ８では、パケット転送２２０から入替え判定部２２１へ送付されたパケット情報を品質判定部２３０へ送付する。ステップＡ９では、Ｚ−ｌｉｓｔ２１２の入替え判定処理を行う。この場合、乱数を発生させて、Ｚ−ｌｉｓｔ２１２に存在する入替え確率ｑと比較し、入替え確率ｑの方が大きければ、入替え処理が発生し、ステップＡ１０へ、入替え確率ｑの方が小さければ、ステップＡ１２へ遷移する。【００３６】
ステップＡ１０では、Ｚ−ｌｉｓｔ２１２の入替え処理を行う。この場合、Ｚ−ｌｉｓｔ２１２のエントリをランダムで選択してＺ−ｌｉｓｔ２１２から追い出し、そのエントリに現在処理中のパケットの情報に属する情報を記載する。ＩＤは、現在処理中のパケットが属するフローを記載し、カウンタ値Ｃは“１”を記録する。その後、ステップＡ１１へ遷移する。ステップＡ１１では、重要度判定部２１３で、ステップＡ９で入替えが発生したフローのカウンタ値Ｃから式（１）のレート計算を行い、その結果に基づいてフローの重要度Ｆを計算する。そのフローがＥ−ｌｉｓｔ２２２に存在する場合、フローの重要度ＦをＥ−ｌｉｓｔ２２２内の重要度Ｅに記載する。そして、ステップＡ１２へ遷移する。ステップＡ１２では、入替え判定部２２１で、Ｅ−ｌｉｓｔ２２２を検索する。現在処理中のフローが存在する場合、ステップＡ１３へ遷移し、存在しない場合にはステップＡ８へ遷移する。ステップＡ１３では、Ｅ−ｌｉｓｔ２２２に現在処理中のフローが存在するので、通信量のカウントアップや、シーケンス番号のチェックによるパケットロス発生の有無、フラグ情報等、管理している統計情報の更新が行われ、処理が終了する。以上のように、品質観測端末２で処理が行われる。【００３７】
従来技術では、テーブルで管理しているエントリ、あるいはフローに対して監視するための重要度が設定されておらず、等しく管理されていた。このため、膨大な量のフローが流れているネットワークを監視するためには、管理するテーブルのエントリ量を大きくする必要があり、装置で用意する必要のある計算リソースやメモリ容量が大きくなるという問題があった。逆に、管理するテーブルのエントリ量を小さくした場合、統計情報で管理する情報が断片的になり計測精度が低下するという問題があった。【００３８】
一方、この実施の形態では、テーブルで管理しているエントリ、あるいはフローに対して監視するための重要度を与えている。この実施の形態では、小規模なテーブルを用いて確率的に計算したスループットが監視重要度となっている。この重要度に基づいてテーブルの入れ替えを行っているため、膨大な量のフローのうちで重要度の高いもののフローの統計情報を特に監視することができる。ネットワーク中のフローの発生は、多くの場合、均一ではない。たとえば、転送量のトラフィック分布は全体の数％のフローが、全体の半数以上のトラフィック量を占めている状態（非特許文献２参照）である。さらに、この大半のトラフィック量を占めるフロー（以下、「エレファントフロー」という）はスループットとも高い相関があることが報告されている。このため、この均一でない分布に対して適切な重要度を与えることができれば、監視重要度を設定し、テーブルを入れ替えることによって、少数のフロー情報を管理するテーブルを作成すれば、半数以上のトラフィックを監視することができるようになり、装置で用意する必要のある計算リソースやメモリ容量を削減することができる。【００３９】
実施の形態１では、重要度を決定するテーブルと、統計情報を管理するテーブルとが別々に設けられていた。これに対して、第２の実施の形態では、重要度の決定と統計情報の管理とが同一のテーブルで行われる。【００４０】
図７は、この発明の第２の実施の形態におけるＥＺ−ｌｉｓｔの入替え確率を説明する図、及び図８が、Ｅ−ｌｉｓｔ及びＺ−ｌｉｓｔの登録処理の概要を示す図である。
この実施の形態でも、実施の形態１と同様に、特定フィールドが同じパケット群を「フロー」という。ここでのフローの具体例としては、送受信ＩＰアドレス、送受信ポート番号、送受信ＭＡＣアドレス、プロトコルＩＤのいずれか１つ以上の組でパケットをグルーピングすることが考えられる。あるいはＩＰやＴＣＰなどプロトコルヘッダに存在するフラグ情報での分類や、ＩＰやＶＬＡＮやＭＰＬＳなどプロトコルヘッダに存在する優先度情報でグルーピングすることや、これらの組み合わせでグルーピングすることが考えられる。またこられの番号や分類は、完全に同一なもので分類する方法のほかに、複数の範囲を設定し、設定した範囲であれば同一のグループに分類することが考えられる。【００４１】
図９は、第２の実施の形態の品質観測端末２ｂの構成を示すブロック図であり、第１の実施の形態を示す図４中の要素と共通の要素には共通の符号が付されている。
この品質観測端末２ｂは、パケット転送部２００と、品質計測部２３０と、統計情報管理部２４０とから構成されている。統計情報管理部２４０は、フロー情報を検索する検索部２４１と、検索部２４１に入替え確率を通知する入替え確率２４４と、入替え結果を品質計測部２３０に送付する入替え判定部２４３とから構成されている。パケット転送部２００では、ある入口から品質観測端末２ｂに入ってきたパケットを観測し、その結果を統計情報管理部２４０へ送付すると同時に、他方の出口からネットワーク中に転送する処理を行う。この処理は、パケット入力毎に行われる。ただし、パケット転送部２００でパケットをサンプリングして間引いて少なくしたパケットを統計情報管理部２４０へ転送しても良い。【００４２】
統計情報管理部２４０では、パケット転送部２００から送付されたパケット情報に基づいて検索部２４１で処理を行う。検索部２４１では、ＥＺ−ｌｉｓｔ２４２を検索する。ＥＺ−ｌｉｓｔ２４２は、ＩＤとカウンタ値Ｃと統計情報を有するリストであり、パラメータとしてエントリの入替え確率を有している。この入替え確率は、カウンタ値Ｃ毎に有しており、カウンタ値“１”のときの入替え確率をｑ１、カウンタ値“２”のときの入替え確率をｑ２、及び、カウンタ値“ｎ”のときの入替え確率をｑｎとする。この情報は、入替え確率２４４に格納されている。フローのＩＤがＥＺ−ｌｉｓｔ２４２内に存在すれば、該当するＩＤのカウンタ値Ｃを“１”カウントアップし、さらに管理している通信量やパケットロスの量フラグの数などの統計情報を更新する。もし、フローのＩＤがＥＺ−ｌｉｓｔ２４２内に存在しなければ、ＥＺ−ｌｉｓｔ２４２内のＩＤをランダムに選択し、そのエントリでカウントされているカウンタ値を読み出す。カウンタ値に基づいて入替え確率２４４を検索して入替え確率ｑｎを算出し、乱数発生させて入替え確率ｑｎよりも小さければ、選択されていたＩＤのエントリをＥＺ−ｌｉｓｔ２４２から追い出して、今回到着したパケットをそのエントリに登録し、カウンタ値として“１”を選択する。乱数発生結果が入替え確率ｑｎよりも大きければ、ＥＺ−ｌｉｓｔ２４２に対する処理は何も行わない。【００４３】
入替え確率を図７に示すように設定した場合、次式（２）のようにしてレートを推定することができる。式（２）では、ｐがＥＺ−ｌｉｓｔの平均ヒット率、ｑはＥＺ−ｌｉｓｔの入替え確率、Ｃi は入替えが発生した際に追い出されたフローが有していたカウンタ値Ｃ、Ｍはエントリの大きさである。このため、式（２）のレート計算は、同一フローのパケットが到着したときではなく、他フローのパケットが到着した際に行われる。
（１−ｐ）・（ｑ１／Ｍ）・（Ｃi −１）＜Ｒi 
＜（１−ｐ）・（ｑｎ／Ｍ）・（Ｃi −１）      …（２）
ここで、図７に示す例では、カウンタ値が大きくなるにつれて、入替え確率が低くなるように設定されているが、カウンタ値が大きくなるにつれ、入替え確率が大きくなるように設定しても良い。また、図７では、変化が線形となっているが、非線形の関数や区間によって変化する関数、定数項が存在するなど、一般的な関数を使用することができる。【００４４】
入替え判定部２４３では、検索部２４１の結果が、ＥＺ−ｌｉｓｔ２４２が更新（カウンタアップ）された場合には、何もしない。ＥＺ−ｌｉｓｔ２４２が更新されず、入替えが発生した場合には、追い出されたフローの統計情報を品質計測部２３０へ送付する。入替えが発生しなかった場合には、パケット情報を品質計測部２３０へ送付する。この実施の形態では、品質観測端末２ｂをネットワークの回線上に挿入する形態で説明したため、図１に示す環境で用いられるものとして説明したが、図６に示すように、ネットワーク中にパケットをコピーするＴＡＰを挿入したり、ルータやスイッチであるポートのパケットをコピーするミラーポート機能を設定したりことにより、パケットを観測するようにしても良い。その場合には、図９中のパケット転送部２００は、品質観測端末２ｂ外からのパケットを受信する機能を有するものになる。【００４５】
また、この実施の形態では、統計情報管理部２４０及び品質計測部２３０が全て品質観測端末２ｂの一装置内に存在するが、統計情報管理部２４０と品質計測部２３０とがそれぞれ別の装置内に設けられていても良く、その場合には各部間の情報伝達は、ネットワークを介して行われる。また、この実施の形態では、入替え判定部２４３においてＥＺ−ｌｉｓｔにカウントされなかった情報は、パケット情報として品質計測部２３０へ送付するものとしているが、ＥＺ−ｌｉｓｔに登録された重要な情報だけを統計情報として送付するようにしても良い。また、この実施の形態では、ＥＺ−ｌｉｓｔ２４２の入替え確率は、入替え確率２４４で管理されており、検索部２４１が読み出すものとしたが、ＥＺ−ｌｉｓｔ２４２内に記載しておいても良く、また、検索部２４１でカウンタ値に基づいて毎回計算しても良い。【００４６】
図１０は、品質観測端末２ｂの統計情報管理部２４０の動作を説明するフローチャートである。
この図を参照して、この例の品質観測端末２ｂに用いられる統計情報管理テーブルの入替え方法の処理内容について説明する。
パケット転送部２００にパケットが到着すると、その内容が検索部２４１へ転送されて処理が開始され、ステップＢ１へ遷移する。ステップＢ１では、検索部２４１がＥＺ−ｌｉｓｔ２４２の検索を行い、現在処理中のパケットのフローがＥＺ−ｌｉｓｔ２４２に登録されているか否かを調べ、登録されている場合にはステップＢ２へ遷移し、登録されていない場合にはステップＢ４へ遷移する。ステップＢ２では、ＥＺ−ｌｉｓｔ２４２の更新処理が行われる。具体的には、ＥＺ−ｌｉｓｔ２４２のカウンタ値を“１”カウントアップする。そして、管理されている通信量やパケットロスの量フラグの数などの統計情報が更新され、処理が終了する。ステップＢ３では、パケット転送２２０から送付されたパケット情報が品質判定部２３０へ送付され、処理が終了する。【００４７】
ステップＢ４では、ＥＺ−ｌｉｓｔ２４２の入替え判定が行われる。入替え判定は、検索部２４１で行われる。はじめにＥＺ−ｌｉｓｔ２４２のエントリをランダムに選択してそのカウンタ値を読み込む。その結果から入替え確率２４４を検索し、入替え確率ｑｎを読み出す。検索部２４１は、その後、乱数を作成して入替え確率ｑｎと比較し、入替え確率ｑｎの方が大きければ、入替え処理が発生してステップＢ５へ遷移し、入替え確率ｑｎの方が小さければ、ステップＢ３へ遷移する。ステップＢ５では、エントリ情報の入替えを行う。ステップＢ４で選択されたエントリ情報をＥＺ−ｌｉｓｔ２４２から追い出して、現在処理中のフローのエントリを作成する。この新規登録では、カウンタ値を“１”にして、統計情報をクリアした状態にしておく。この処理後、ステップＢ６へ遷移する。ステップＢ６では、入替え時のカウンタ値に基づいて、追い出されたフローのレート計算を式（２）を用いて行う。そして、ステップＢ７へ遷移する。ステップＢ７では、処理Ａ４でＥＺ−ｌｉｓｔ２４２から追い出されたエントリの情報を品質計測部２３０へ送付して処理を終了する。【００４８】
以上のように、この第２の実施の形態では、テーブルで管理しているエントリの入替え確率を変更することにより、確率的に長くテーブルに存在しやすくなるフローと、短くテーブルに存在しやすくなるフローができる。監視したいフローを確率的にテーブルに長く存在しやすくなるフローとすれば、重要度の高いフローの統計情報を特に監視することができる。たとえば、カウンタ値が高くなったときに入替え確率を低くするように設定すれば、レートの高いフローが長くテーブルにとどまりやすくなり、レートの低いフローがテーブルから早く追い出されやすくなる。このため、監視重要度を考慮し、そのフローが長くテーブルに存在するように入替え確率を設定することにより、少数のテーブルで、効率的に重要な情報を監視することができるようになり、装置で用意する必要のある計算リソースやメモリ容量を削減することができる。【００４９】
図１１は、この発明の第３の実施の形態である品質観測端末の構成を示すブロック図である。
上記第１及び第２の実施の形態では、監視重要度の高いフローを重点的に監視するテーブルにより、ネットワーク品質を計測していた。これに対して、この第３の実施の形態では、同様のテーブルを用いて計測した結果からパケット廃棄判定処理を行い、パケット転送部２００から転送されるパケットを制御する。【００５０】
この例の品質観測端末２ｃは、同図１１に示すように、パケット転送部２００と、重要度算出部２１０と、品質計測部２３０と、統計管理＆廃棄判定処理２５０と、パケット廃棄２６１，２６２とから構成されている。統計管理＆廃棄判定処理２５０は、該当フローの重要度とＥ−ｌｉｓｔ内の重要度から入替え判定を行う入替え判定部２５１と、監視重要度の高いフローの統計データが格納されているＥ−ｌｉｓｔ２５２と、パケットの廃棄判定を行う廃棄判定処理２５３とから構成されている。パケット廃棄２６１，２６２は、パケット廃棄処理を行う。【００５１】
パケット転送部２００では、ある入口から品質観測端末２ｃに入ってきたパケットを観測し、その結果を重要度算出部２１０と統計管理＆廃棄判定処理２５０とへ送付すると同時に、他方の出口からネットワーク中に転送する処理を行う。この処理は、パケット入力毎に行われる。ただし、パケット転送部２００でパケットをサンプリングして間引いて少なくしたパケットを重要度算出部２１０と統計管理＆廃棄判定処理２５０へ転送しても良い。重要度算出部２１０の処理は、第１の実施の形態と同様である。統計管理＆廃棄判定処理２５０では、パケット転送部２００からのパケット情報と重要度算出部２１０で計算した重要度とを入力する。入替え判定部２５１では、Ｅ−ｌｉｓｔ２５２の内容と重要度算出部２１０の結果、パケット転送部２００のパケット情報に基づいて処理を決定する。Ｅ−ｌｉｓｔ２５２は、フローＩＤと重要度Ｅ値と、統計情報（通信量やパケットロス数、フラグ数など）を組として有するリストである。また、入替え判定部２５１では、Ｅ−ｌｉｓｔ２５２の中で重要度が一番小さいフローＩＤとその重要度Ｅ値を記憶しておく。ここで記憶している最小重要度のＥ値を、「Ｅｍｉｎ」という。【００５２】
パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２５２に登録されていないフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されていないフローに属する場合には、何もせず、パケット情報を品質計測部２３０に送付する。この際にパケットをサンプリングして一定確率で送付しても良い。パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２５２に登録されていないフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されているフローに属する場合には、カウントアップ後のＺ−ｌｉｓｔ２１２の優先度ＦとＥｍｉｎの値とを比較し、優先度Ｆの方がＥｍｉｎよりも大きければ、Ｅｍｉｎを有するフローの情報をＥ−ｌｉｓｔ２２２から削除し、登録されていた重要度Ｅと統計情報とを、品質計測部２３０へ送付する。そして、現在のフローに関するエントリをＥ−ｌｉｓｔ２５２に登録する。エントリに登録する際は、フローＩＤには、グループのフロー情報を登録し、重要度Ｅ値は空欄、統計情報はクリア状態（通信量やパケットロス数、フラグ数などを“０”にしておく）に設定する。優先度Ｆの方がＥｍｉｎよりも小さければ、Ｅ−ｌｉｓｔ２５２には何も変更を加えずにパケット情報を品質計測部２３０へ送付する。【００５３】
パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２５２に登録されているフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されていないフローに属する場合、検索部２１１の結果でＺ−ｌｉｓｔ２１２に入替えが発生しなかった場合には、Ｅ−ｌｉｓｔ２５２では登録されている統計情報を更新する。ただし、情報を更新する前に廃棄判定処理２５１で現在のパケットを本装置で転送するか廃棄するかを判定する。統計情報に記載されているフローに関しては、詳細な情報を収集することが可能であるため、廃棄の判定は、通信量が一定値になった場合や、通信時間が一定時間となった場合などに、他のフローとの公平性を考慮して、確率的に該当パケットを廃棄させたり、全パケットを廃棄したりする方法が考えられる。【００５４】
ここで、廃棄すると判定された場合、Ｅ−ｌｉｓｔ２５２の統計情報の更新は行わず、入替え判定部２５１から品質計測部２３０へのデータ転送も行わない。検索部２１１の結果でＺ−ｌｉｓｔ２１２に入替えが発生した場合には、現在処理中のパケットに属するフローの統計情報を更新すると同時に、Ｚ−ｌｉｓｔ２１２の入替えで追い出されたフローの処理判定を行う。追い出されたフローもＥ−ｌｉｓｔ２５２に存在していた場合、Ｚ−ｌｉｓｔ２１２で追い出された時点のカウンタ値Ｃを使って最終的な重要度Ｆを計算し、その情報をＥ−ｌｉｓｔ２２２の統計情報の重要度Ｅとして記載する（図３中の時刻Ｃや時刻Ｅに相当）。Ｚ−ｌｉｓｔ２１２から追い出されたフローがＥ−ｌｉｓｔ２２２に存在しない場合、処理は行わない。【００５５】
パケット転送部２００からのパケットが、Ｅ−ｌｉｓｔ２５２に登録されているフローに属する場合で、Ｚ−ｌｉｓｔ２１２に登録されているフローに属する場合、Ｚ−ｌｉｓｔ２１２を更新すると同時に、Ｅ−ｌｉｓｔ２２２も更新する。ただし、情報を更新する前に廃棄判定処理２５１で現在のパケットを品質観測端末２ｃで転送するか廃棄するかを判定する。統計情報に記載されているフローに関しては、詳細な情報を収集することが可能であるため、廃棄の判定は、通信量が一定値になった場合や、通信時間が一定時間となった場合などに他のフローとの公平性を考慮して、確率的に該当パケットを廃棄させたり、全パケットを廃棄したりする方法が考えられる。ここで、廃棄すると判定された場合、Ｅ−ｌｉｓｔ２５２の統計情報の更新は行わず、入れ替え判定部２５１から品質計測部２３０へのデータ転送も行わない。品質計測部２３０の処理は、第一の実施の形態と同様である。パケット廃棄２５１で廃棄判定されたパケットに対しては、パケット廃棄２６１やパケット廃棄２６２で廃棄される。【００５６】
この実施の形態では、重要度算出部２１０、統計管理＆廃棄判定処理２５０、品質計測部２３０、パケット廃棄２６１、及びパケット廃棄２６２が全て品質観測端末２ｃの一装置内に設けられているが、それぞれ別の装置内に設けられていても良く、その場合には各部間の情報伝達は、ネットワークを介して行われる。また、この実施の形態では、入替え判定部２５１においてＥ−ｌｉｓｔにカウントされなかった情報は、パケット情報として品質計測部２３０へ送付するものとしているが、Ｅ−ｌｉｓｔに登録された重要な情報だけを統計情報として送付するようにしても良い。また、この実施の形態では、パケット転送部２００で観測したパケット情報を重要度算出部２１０と統計管理＆廃棄判定処理２５０に同時に送付するものとしたが、重要度算出部２１０に送付し、統計管理＆廃棄判定処理２５０に対しては重要度算出部２１０からフローの重要度と共にパケット情報そのものを送付するようにしても良い。【００５７】
また、この実施の形態では、フローの入替えはパケット転送部２００でパケット観測が行われた場合を記載しているが、Ｅ−ｌｉｓｔ２５２の統計情報をエントリ毎にアクティブタイマ（情報が更新されている状態でも一定間隔毎）やインアクティブタイマ（情報が更新されなくなってから一定時間経過）を起動して、統計情報を品質計測部２３０へ送付する方法も考えられる。その際、Ｅ−ｌｉｓｔ２５２から情報を削除して送付する場合や情報は削除せずに送付する方法がある。情報がＥ−ｌｉｓｔ２５２から削除される場合には、次のフローがすぐにエントリを埋めるように、重要度を低く、たとえば“０”にしておくことが考えられる。【００５８】
図１２は、品質観測端末２ｃの重要度算出部２１０及び統計管理＆廃棄判定処理２５０の動作を説明するフローチャートである。
この図を参照して、この例の品質観測端末２ｃに用いられる統計情報管理テーブルの入替え方法の処理内容について説明する。
パケット転送部２００にパケットが到着すると、その内容が検索部２１１と入替え判定部２２１とに転送されて処理が開始され、ステップＡ１へ遷移する。ステップＡ１では、検索部２１１でＺ−ｌｉｓｔ２１２の検索が行われ、現在処理中のパケットのフローがＺ−ｌｉｓｔ２１２に登録されているか否かを調べ、登録されている場合にはステップＡ２へ遷移し、登録されていない場合にはステップＡ９へ遷移する。ステップＡ２では、Ｚ−ｌｉｓｔ２１２の更新処理が行われる。具体的には、Ｚ−ｌｉｓｔ２１２のカウンタ値を“１”カウントアップする。そして、重要度判定部２１３が、カウントアップしたフローの暫定的な重要度Ｆを算出する（最終的な重要度はＺ−ｌｉｓｔ２１２から該当フローが追い出された際に決定する）。その処理が終了すると、ステップＡ３へ遷移する。【００５９】
ステップＡ３では、入替え判定部２２１により、Ｅ−ｌｉｓｔ２５２の検索が行われ、パケット転送部２００から送付のパケットの属するフローがＥ−ｌｉｓｔ２５２に存在するか否かを検索する。Ｅ−ｌｉｓｔ２５２に存在する場合はステップＣ１へ遷移し、存在しない場合にはステップＡ４へ遷移する。ステップＡ４では、Ｅ−ｌｉｓｔ２５２の重要度が一番小さい値Ｅｍｉｎと更新中のＺ−ｌｉｓｔ２１２でカウントアップしたフローの暫定的な重要度Ｆとが比較される。重要度Ｆの方がＥｍｉｎよりも重要度が高い場合にはＥ−ｌｉｓｔ２５２の入替えが発生し、ステップＡ５へ遷移する。Ｅｍｉｎの方が重要度Ｆよりも重要度が高い場合には、入替えは発生せず、ステップＡ８へ遷移する。ステップＡ５では、Ｅｍｉｎに属するフローをＥ−ｌｉｓｔ２５２から追い出し、現在処理中のパケットの属するフローのエントリを作成する。ここで統計情報はクリア状態、重要度は空欄のままとしておき、ステップＡ７へ遷移する。ステップＡ７では、ステップＡ５でＥ−ｌｉｓｔ２５２から追い出されたエントリの情報を品質計測部２３０へ送付して処理を終了する。【００６０】
ステップＡ８では、パケット転送２２０から入替え判定部２２１へ送付されたパケット情報が品質判定部２３０へ送付される。ステップＡ９では、Ｚ−ｌｉｓｔ２１２の入替え判定処理が行われ、乱数を発生させて、Ｚ−ｌｉｓｔ２１２に存在する入替え確率ｑと比較し、入替え確率ｑの方が大きければ、入替え処理が発生してステップＡ１０へ遷移し、入替え確率ｑの方が小さければ、ステップＡ１２へ遷移する。ステップＡ１０では、Ｚ−ｌｉｓｔ２１２の入替え処理が行われる。Ｚ−ｌｉｓｔ２１２のエントリをランダムで選択してＺ−ｌｉｓｔ２１２から追い出し、そのエントリに現在処理中のパケットの情報に属する情報を記載する。ＩＤは現在処理中のパケットが属するフローを記載し、カウンタ値Ｃは“１”を記録する。その後、ステップＡ１１へ遷移する。【００６１】
ステップＡ１１では、重要度判定部２１３で、ステップＡ９で入替えが発生したフローのカウンタ値Ｃから式（１）のレート計算を行い、その結果に基づいてフローの重要度Ｆを計算する。そのフローがＥ−ｌｉｓｔ２２２に存在する場合、フローの重要度ＦをＥ−ｌｉｓｔ２５２内の重要度Ｅに記載し、ステップＡ１２へ遷移する。ステップＡ１２では、入替え判定部２２１で、Ｅ−ｌｉｓｔ２５２を検索する。現在処理中のフローが存在する場合にはステップＣ３へ遷移し、存在しない場合にはステップＡ８へ遷移する。ステップＣ１では、廃棄判定処理２５３で廃棄判定処理が行われる。これは、Ｅ−ｌｉｓｔ２５２に登録されている統計情報を参照し、一定量の通信が行われた、あるいは一定時間以上通信が継続しているなどの判断基準により、パケット廃棄判定を行う。廃棄すると判断した場合は、パケット廃棄２６１、あるいはパケット廃棄２６２へパケット廃棄を指示する。そして、ステップＣ２へ遷移する。ステップＣ２では、Ｅ−ｌｉｓｔ２５２の統計情報の更新を行い、処理が終了する。ステップＣ３では、ステップＣ１と同様の処理を行う。処理終了後ステップＣ４へ遷移する。ステップＣ４では、ステップＣ２と同様の処理が行われる。【００６２】
この実施の形態では、テーブルで管理しているエントリ、あるいはフローに対して監視するための重要度を与えている。すなわち、この実施の形態では、小規模なテーブルを用いて確率的に計算したスループットが監視重要度となっている。この重要度に基づいてテーブルの入れ替えを行っているため、膨大な量のフローのうちで重要度の高いものフローの統計情報を特に監視することができる。ネットワーク中のフローの発生は、多くの場合、均一ではない。たとえば、転送量のトラフィック分布は全体の数％のフローが、全体の半数以上のトラフィック量を占めている状態（非特許文献２参照）である。さらに、この大半のトラフィック量を占めるフロー（エレファントフロー）はスループットとも高い相関があることが報告されている。このため、この均一でない分布に対して適切な重要度を与えることができれば、監視重要度を設定し、テーブルを入れ替えることによって、少数のフロー情報を管理するテーブルを作成すれば、半数以上のトラフィックを監視することができるようになり、装置で用意する必要のある計算リソースやメモリ容量を削減することができる。また、フローの特性をトラフィック量とスループットに分類すると、低レートで少量のフロー、低レートで大量のフロー、高レートで少量のフロー、高レートで大量のフローと単純に分けることができる。従来のレートでトラフィック制御をかけると、高レートで少量のフローと高レートで大量のフローも同様の制御となってしまうが、高レートのフローの統計情報を取って重点的に監視し、トラフィック量が大量になってからパケット廃棄を行うといった利用方法も可能となる。【００６３】
この発明は、ネットワークの通信品質を管理する装置全般に適用できる。【００６４】
本出願は、２００７年３月６日に出願された日本出願特願２００７−０５５７８７号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2008108403.tif 000003
【図２】
2008108403.tif 000004
【図３】
2008108403.tif 000005
【図４】
2008108403.tif 000006
【図５】
2008108403.tif 000007
【図６】
2008108403.tif 000008
【図７】
2008108403.tif 000009
【図８】
2008108403.tif 000010
【図９】
2008108403.tif 000011
【図１０】
2008108403.tif 000012
【図１１】
2008108403.tif 000013
【図１２】
2008108403.tif 000014
【国際調査報告】
2008108403.tif 000015
2008108403.tif 000016