(57)【要約】【課題】マルチコア環境における各コアのデータ構造に対して、データ構造の再構築、データ構造の検索処理、およびＲＳＳ機能の調整を行うことなく、これらを効率的に合併できるトラフィックモニタリング方法、トラフィックモニタリング装置及びプログラムを提供することを目的とする。【解決手段】本発明に係るトラフィックモニタリング方法は、各コアが形成したデータ構造の要素をアイテム毎に比較し、当該要素内の統計値をいずれか一つの要素にまとめるとともに、他の要素の統計値をゼロとすることとした。データ構造の合併時に統計値がゼロである要素を無視することで、データ構造間の重複要素を除去することができる。【選択図】図１２
2020088640.tif 000002
【特許請求の範囲】
【請求項１】
マルチコア環境でのトラフィックモニタリング方法であって、
レシーブサイドスケーリング（ＲＳＳ：Ｒｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ）機能でパケットを複数のコアに振り分ける振分工程と、
所定時間毎に、それぞれの前記コアで、アイテム毎に前記パケットを観測して統計値を取得し、前記アイテムと前記統計値の組み合わせからなる要素で構成されるデータ構造を形成する観測工程と、
それぞれの前記コアで形成した前記データ構造の前記要素を前記アイテム毎に突き合わせ、前記アイテム毎に、いずれか１つのコアの前記要素の前記統計値を該統計値の目的に応じた値に書き換えし、他のコアの前記要素の前記統計値をゼロに置き換え、それぞれの前記コアの前記データ構造を合併する合併工程と、
を行うことを特徴とするトラフィックモニタリング方法。
【請求項２】
前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの出現回数であり、
前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の和である
ことを特徴とする請求項１に記載のトラフィックモニタリング方法。
【請求項３】
前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットのパケット長であり、
前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の和である
ことを特徴とする請求項１に記載のトラフィックモニタリング方法。
【請求項４】
前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの最大パケット長であり、
前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の最大値である
ことを特徴とする請求項１に記載のトラフィックモニタリング方法。
【請求項５】
前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの最小パケット長であり、
前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の最小値である
ことを特徴とする請求項１に記載のトラフィックモニタリング方法。
【請求項６】
前記所定時間に、
前記観測工程で、前記コアの一方のデータベースに前記データ構造を形成するとともに、前記合併工程で、前記コアの他方のデータベースに保管されている前記データ構造を合併することを特徴とする請求項１から５のいずれかに記載のトラフィックモニタリング方法。
【請求項７】
マルチコアのトラフィックモニタリング装置であって、
レシーブサイドスケーリング（ＲＳＳ：Ｒｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ）機能でパケットを複数に振り分ける振分部と、
前記振分部が振り分けた前記パケットをそれぞれ受信し、所定時間毎に、アイテム毎に前記パケットを観測して統計値を取得し、前記アイテムと前記統計値の組み合わせからなる要素で構成されるデータ構造を形成する複数のコアと、
それぞれの前記コアで形成した前記データ構造の前記要素を前記アイテム毎に突き合わせ、前記アイテム毎に、いずれか１つのコアの前記要素の前記統計値を該統計値の目的に応じた値に書き換えし、他のコアの前記要素の前記統計値をゼロに置き換え、それぞれの前記コアの前記データ構造を合併する合併部と、
を備えることを特徴とするトラフィックモニタリング装置。
【請求項８】
請求項１から６のいずれかに記載のトラフィックモニタリング方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、汎用ＣＰＵと汎用ＮＩＣ上で動作するトラフィックモニタリングのため方法、装置及びプログラムに関する。
【背景技術】
【０００２】
ＩＰネットワークにおいてトラフィックモニタリングは、日々の管理、運用、及び課金に必要な技術であるとともに、設備計画、収容設計、トラフィックエンジニアリング及びセキュリティ対応に必要な情報を提供する重要なタスクである。
【０００３】
高速、高精度、及びリアルタイムなモニタリング用途には専用ハードウエアが利用されている。しかし、専用ハードウエアは、高コストであり、自由に観測箇所を追加することが困難とう課題がある。一方、モニタリングを汎用ＣＰＵと汎用ＮＩＣを用いたソフトウェアで実現することもできる。汎用ＣＰＵと汎用ＮＩＣを用いることで、コストダウンを図ることができ、多数の場所に設置してモニタリングすることや必要に応じてモニタリングポイントを設置することができる。しかし、ソフトウェアによるパケット処理性能は専用ハードウエアと比較すると低い。このため、複数のＣＰＵによるマルチコアで性能の向上を図ることが検討されている。
【０００４】
マルチコアでトラフィックモニタリングを行う場合、性能を発揮するには次の２点が必要とされている。
１．トラフィックを各コアに均等に分散させるためＮＩＣでＲｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ（ＲＳＳ）（例えば、非特許文献１を参照。）を有効にする。
２．各コアを独立に動作させる（コア間に相互作用があった場合、同期処理が必要となるため性能が低下する）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｉｎｔｅｌ（登録商標）８２５７６ＥＢ  Ｇｉｇａｂｉｔ  Ｅｔｈｅｒｎｅｔ  Ｃｏｎｔｒｏｌｌｅｒ  Ｄａｔａｓｈｅｅｔ，  ｈｔｔｐｓ：／／ｗｗｗ．ｉｎｔｅｌ．ｃｏｍ／ｃｏｎｔｅｎｔ／ｄａｍ／ｗｗｗ／ｐｕｂｌｉｃ／ｕｓ／ｅｎ／ｄｏｃｕｍｅｎｔｓ／ｄａｔａｓｈｅｅｔｓ／８２５７６ｅｂ−ｇｉｇａｂｉｔ−ｅｔｈｅｒｎｅｔ−ｃｏｎｔｒｏｌｌｅｒ−ｄａｔａｓｈｅｅｔ．ｐｄｆ（２０１８年１１月６日検索）
【非特許文献２】Ｐａｔ  Ｍｏｒｉｎ，  “Ｏｐｅｎ  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ”，  ＡＵ  Ｐｒｅｓｓ  Ａｔｈａｂａｓｃａ  Ｕｎｉｖｅｒｓｉｔｙ，  ２０１３，  ｈｔｔｐ：／／ｗｗｗ．ａｕｐｒｅｓｓ．ｃａ／ｉｎｄｅｘ．ｐｈｐ／ｂｏｏｋｓ／１２０２２６（２０１８年１１月６日検索）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、マルチコアでトラフィックモニタリングを行う場合、観測粒度の設定により同じ観測アイテムが別々のコアに振り分けられる可能性がある。ここで観測粒度とは集計の単位であり、例えば“ＩＰペア毎に通信量を計測する”、“宛先ＩＰ毎に通信量を計測する”などの観測タスクにおけるＩＰペアや宛先ＩＰに相当する。
【０００７】
これはＲＳＳで計算対象となるヘッダ（例えばＩＰｖ６ペア）が観測粒度（例えばソースＩＰｖ６の先頭６４ｂｉｔのみ）と異なる場合などである。ここでＲＳＳはパケットヘッダの指定されたビット列からハッシュ値を計算し、そのハッシュ値に従いパケットを各ＣＰＵコアに振り分ける機能である（図１）。
【０００８】
これによりアイテムの観測値の正しい値が得られない場合がある。例えばＲＳＳでＩＰペアでハッシュ値を計算しており、アイテムとして各宛先ＩＰ毎に通信量を観測していた場合、同一の宛先ＩＰをもつパケットが別々のコアに割り振られる場合がある。このため、通信量が閾値を越えるかどうかを観測していた場合、各コアでは実際の通信量より少ない値しか観測できないため閾値判定を誤認する可能性がある。
【０００９】
さらに、ソフトウェアによるトラフィックモニタリングを複数のコアで行った場合、各コアで構築した複数のデータ構造を高速に合併（重複要素を排除）する必要性がある。複数のデータ構造から重複要素を排除する方法としては次の３つの方法がある。
方法１．各コアで観測により構築したデータ構造の各要素を入力として、一つの大きなデータ構造を再構築する方法
方法２．ＲＳＳのハッシュ値を調整して、同じキーは同じＣＰＵコアに割り振られるように調整する方法
方法３．全ての要素について各データ構造を検索して重複要素を削除する方法
【００１０】
以下、それぞれの方法についての課題を説明する。
【００１１】
〔方法１の課題〕
方法１は、再度データ構造を構築するので追加の領域計算量と時間計算量が必要という課題がある。
例えば、重複を排除するために集合を木構造（例えば、非特許文献２を参照。）などで実装した場合、データ構造の再構築にはＯ（ＴｌｏｇＴ）の計算量が必要となる。ここでＴは各コアで観測された要素数の合計である。
また、他の例として、データ構造にハッシュテーブル（例えば、非特許文献２を参照。）を利用していた場合、各コアでの観測により構築されたハッシュテーブルの各要素について、ハッシュ値を再度計算して、新しいハッシュテーブルに挿入する必要がある。このため、ハッシュ値の再計算の他に新しいハッシュテーブル用のメモリ確保などの作業が必要となる。
【００１２】
〔方法２の課題〕
ＲＳＳはＮＩＣの機能でありハードウエアでＲＳＳのハッシュ値が計算される。方法２は２つの課題がある。
【００１３】
課題の１つは、観測粒度にＲＳＳ機能を対応させる必要性である。観測粒度としては次のようなものが考えられる。
（１）  送信元ＩＰ
（２）  宛先ＩＰ
（３）  送信元ＩＰの上位２４ｂｉｔと宛先ＩＰの上位２４ｂｉｔの組
（４）  送信元ＩＰ、宛先ＩＰ、プロトコル番号、送信元ポート、宛先ポート
（５）  パケット長
例えば（５）のパケット長の場合はＲＳＳの計算にパケット長を含める必要がある。しかし、ＲＳＳ計算はＬ４のポート番号（ＴＣＰやＵＤＰのポート番号）までが一般的であり、パケット長はＲＳＳ機能として通常サポートされていない。
【００１４】
他の課題は、複数の観測粒度で観測する場合、観測粒度によって別のコアに割り振られてしまうことである。
例えば上記（１）と（２）を観測する場合を考える。図３及び図４は、ＲＳＳ計算フィールドと観測粒度の関係を説明した図である。図４で説明するように、ＲＳＳ計算に送信元ＩＰと宛先ＩＰを使用すると、同じ送信元ＩＰでも宛先ＩＰが異なるパケットは別のコアに割り振られる可能性があり（１）での観測粒度に適合しなくなる。一方、図３で説明するように、ＲＳＳ計算に送信元ＩＰのみを利用すると、同じ宛先ＩＰでも送信元ＩＰが異なるパケットが別のコアに割り振られる可能性があり（２）での観測粒度に適合しなくなる。ＲＳＳ計算に宛先ＩＰのみを利用する場合も同様である。
【００１５】
〔方法３の課題〕
方法３は、全ての要素について、各コアのデータ構造から検索し、それら重複要素を合併する方法である。このため、方法３は、各要素と各データ構造に対して検索操作を実施するので追加の計算時間を必要とし、合併も実行する必要があるという課題がある。
【００１６】
例えば、データ構造に木構造を利用して集合を利用していた場合を考える。検索はＯ（ｌｏｇＮ）の計算量が必要となる、Ｎは集合の要素数である。ここでｉ番目のコアのデータ構造の要素数を｜Ｔｉ｜とする。全てのデータ構造に対して並列に検索できる場合、Ｏ（Ｔｍａｘｉｌｏｇ｜Ｔｉ｜）の計算量が必要となる。並列に検索できない場合、式１の計算量が必要となる。
【数１】
2020088640.tif 000003
ただし、Ｔは各コアで観測された要素数の合計であり、
【数２】
2020088640.tif 000004
である。
【００１７】
また、例えば、データ構造にハッシュテーブルを利用していた場合は、再構築と同様に全要素のハッシュ値を再計算する必要がある。さらに、各コアで使用するハッシュ関数が異なる場合、対応したハッシュ関数を利用する必要があるため、異なるハッシュ関数の数だけハッシュ値を再計算する必要がある。
【００１８】
本発明は、上記の方法１〜３の課題を解決することを目的とする。すなわち、本発明は、上記課題を解決するために、マルチコア環境における各コアのデータ構造に対して、データ構造の再構築、データ構造の検索処理、およびＲＳＳ機能の調整を行うことなく、これらを効率的に合併できるトラフィックモニタリング方法、トラフィックモニタリング装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記目的を達成するために、本発明に係るトラフィックモニタリング方法は、各コアが形成したデータ構造の要素をアイテム毎に比較し、当該要素内の統計値をいずれか一つの要素にまとめるとともに、他の要素の統計値をゼロとすることとした。
【００２０】
具体的には、本発明に係るトラフィックモニタリング方法は、マルチコア環境でのトラフィックモニタリング方法であって、
レシーブサイドスケーリング（ＲＳＳ：Ｒｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ）機能でパケットを複数のコアに振り分ける振分工程と、
所定時間毎に、それぞれの前記コアで、アイテム毎に前記パケットを観測して統計値を取得し、前記アイテムと前記統計値の組み合わせからなる要素で構成されるデータ構造を形成する観測工程と、
それぞれの前記コアで形成した前記データ構造の前記要素を前記アイテム毎に突き合わせ、前記アイテム毎に、いずれか１つのコアの前記要素の前記統計値を該統計値の目的に応じた値に書き換えし、他のコアの前記要素の前記統計値をゼロに置き換え、それぞれの前記コアの前記データ構造を合併する合併工程と、
を行うことを特徴とする。
【００２１】
また、本発明に係るトラフィックモニタリング装置は、マルチコアのトラフィックモニタリング装置であって、
レシーブサイドスケーリング（ＲＳＳ：Ｒｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ）機能でパケットを複数に振り分ける振分部と、
前記振分部が振り分けた前記パケットをそれぞれ受信し、所定時間毎に、アイテム毎に前記パケットを観測して統計値を取得し、前記アイテムと前記統計値の組み合わせからなる要素で構成されるデータ構造を形成する複数のコアと、
それぞれの前記コアで形成した前記データ構造の前記要素を前記アイテム毎に突き合わせ、前記アイテム毎に、いずれか１つのコアの前記要素の前記統計値を該統計値の目的に応じた値に書き換えし、他のコアの前記要素の前記統計値をゼロに置き換え、それぞれの前記コアの前記データ構造を合併する合併部と、
を備えることを特徴とする。
【００２２】
本発明のようにデータ構造の要素の統計値を処理し、データ構造の合併時に統計値がゼロである要素を無視することで、データ構造間の重複要素を除去することができる。従って、本発明は、マルチコア環境における各コアのデータ構造に対して、データ構造の再構築、データ構造の検索処理、およびＲＳＳ機能の調整を行うことなく、これらを効率的に合併できるトラフィックモニタリング方法及びトラフィックモニタリング装置を提供することができる。
【００２３】
なお、前記統計値には、次のような値を採用できる。
（１）前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの出現回数であり、前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の和である。
（２）前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットのパケット長であり、前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の和である。
（３）前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの最大パケット長であり、前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の最大値である。
（４）前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの最小パケット長であり、前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の最小値である。
【００２４】
本発明に係るトラフィックモニタリング方法は、前記所定時間に、前記観測工程で、前記コアの一方のデータベースに前記データ構造を形成するとともに、前記合併工程で、前記コアの他方のデータベースに保管されている前記データ構造を合併することを特徴とすることが好ましい。
本トラフィックモニタリング方法は、定期的に合併工程を行い、データ構造の合併後に新たなデータが記録されることを防止することができる。
【００２５】
本発明に係るプログラムは、前記トラフィックモニタリング方法をコンピュータに実行させるためのプログラムである。
本発明に係るトラフィックモニタリング方法は、コンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【００２６】
なお、上記各発明は、可能な限り組み合わせることができる。
【発明の効果】
【００２７】
本発明は、マルチコア環境における各コアのデータ構造に対して、データ構造の再構築、データ構造の検索処理、およびＲＳＳ機能の調整を行うことなく、これらを効率的に合併できるトラフィックモニタリング方法、トラフィックモニタリング装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００２８】
【図１】マルチコアでトラフィックモニタリングを行う装置を説明する図である。
【図２】本発明に係るトラフィックモニタリング装置を説明する図である。
【図３】本発明の課題を説明する図である。
【図４】本発明の課題を説明する図である。
【図５】本発明に係るトラフィックモニタリング装置の動作を説明する図である。
【図６】本発明に係るトラフィックモニタリング装置の動作を説明する図である。
【図７】本発明に係るトラフィックモニタリング装置の動作を説明する図である。
【図８】本発明に係るトラフィックモニタリング装置の動作を説明する図である。
【図９】本発明に係るトラフィックモニタリング装置の動作を説明する図である。
【図１０】本発明に係るトラフィックモニタリング装置のコアを説明する図である。
【図１１】本発明に係るトラフィックモニタリング装置の動作を説明する図である。
【図１２】本発明に係るトラフィックモニタリング方法を説明するフローチャートである。
【発明を実施するための形態】
【００２９】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００３０】
図１及び図２は、本実施形態のトラフィックモニタリング装置を説明する図である。本トラフィックモニタリング装置は、
レシーブサイドスケーリング（ＲＳＳ：Ｒｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ）機能でパケットを複数に振り分ける振分部１１と、
振分部１１が振り分けた前記パケットをそれぞれ受信し、所定時間毎に、アイテム毎に前記パケットを観測して統計値を取得し、前記アイテムと前記統計値の組み合わせからなる要素で構成されるデータ構造を形成する複数のコア１２と、
それぞれのコア１２で形成した前記データ構造の前記要素を前記アイテム毎に突き合わせ、前記アイテム毎に、いずれか１つのコアの前記要素の前記統計値を該統計値の目的に応じた値に書き換えし、他のコアの前記要素の前記統計値をゼロに置き換え、それぞれのコア１２の前記データ構造を合併する合併部１３と、
を備える。
【００３１】
図１２は、本実施形態のトラフィックモニタリング装置が行うトラフィックモニタリング方法を説明するフローチャートである。本トラフィックモニタリング方法は、
レシーブサイドスケーリング（ＲＳＳ：Ｒｅｃｅｉｖｅ  Ｓｉｄｅ  Ｓｃａｌｉｎｇ）機能でパケットを複数のコアに振り分ける振分工程Ｓ１１と、
所定時間毎に、それぞれの前記コアで、アイテム毎に前記パケットを観測して統計値を取得し、前記アイテムと前記統計値の組み合わせからなる要素で構成されるデータ構造を形成する観測工程Ｓ１２と、
それぞれの前記コアで形成した前記データ構造の前記要素を前記アイテム毎に突き合わせ、前記アイテム毎に、いずれか１つのコアの前記要素の前記統計値を該統計値の目的に応じた値に書き換えし、他のコアの前記要素の前記統計値をゼロに置き換え、それぞれの前記コアの前記データ構造を合併する合併工程Ｓ１３と、
を行う。
【００３２】
本実施形態では、例として、前記要素の前記統計値が、前記要素の前記アイテムに該当する前記パケットの出現回数であり、前記合併工程での、該統計値の目的に応じた値が、全てのコアの前記要素の前記統計値の和であることで説明する。具体的には、観測タスクとしてｔ秒ごと、観測粒度（アイテム）毎の出現回数を計測することで説明する。
【００３３】
なお、統計値としてアイテムの総バイト数、最大パケット長、最小パケット長、その他の観測値を扱うことができる。最大パケット長や最小パケット長を観測する場合は後述するステップ８の総和Σをｍａｘやｍｉｎに置き換えることで同様に扱うことができる。
【００３４】
また、本実施形態のトラフィックモニタリング装置は、所定時間（ｔ秒）に、観測工程Ｓ１２で、前記コアの一方のデータベースに前記データ構造を形成するとともに、合併工程Ｓ１３で、前記コアの他方のデータベースに保管されている前記データ構造を合併するように動作する。
【００３５】
図１０は、コア１２の構造を説明する図である。各コア１２は、データ構造を記録するデータベースを２つ備える。例えば、当該データベースをＡ面とＢ面とする。図１１は、図１０のようなコア１２と合併部１３の動作を説明する図である。コア１２は、０秒からｔ秒までの観測結果をＡ面に記録する。続いてコア１２は、ｔ秒から２ｔ秒までの観測結果をＢ面に記録する。このようにコア１２は、ｔ秒毎に記録するデータ構造を交換していく。そして、合併部１３は、ｔ秒から２ｔ秒の間にＡ面のデータ構造を合併し、２ｔ秒から３ｔ秒の間にＢ面のデータ構造を合併していく。このようにｔ秒毎に合併するデータ構造を交換し、合併後に新しいデータが記録されないようにする。
【００３６】
図５〜図９は、本トラフィックモニタリング装置の動作を説明する図である。
ｉ番目のコア１２が観測したデータ構造をリストＴｉとしている。リストＴｉは、複数の要素ｘからなる。要素ｘは、アイテムａｊ（本実施形態では送信先アドレスである）と当該アイテムに該当するパケットの出現回数ｆｊのペアで表現される。ｊはアイテムを識別する符号である。
【数３】
2020088640.tif 000005
また、リスト要素ｘに対応するアイテムをａ（ｘ）、出現回数をｆ（ｘ）と書く。
【００３７】
例えば、オープンアドレス方式のハッシュテーブル（線形探索ハッシュテーブル（Ｌｉｎｅａｒ  Ｈａｓｈ  Ｔａｂｌｅ）など）（非特許文献２）はこのようなリストとしてみなせる。優先度付きキューや配列もリストとみなすことができる。
【００３８】
以下に述べる方法により、あるアイテムａが複数のリスト（式４参照）に含まれていた場合は式５のように更新する。
【数４】
2020088640.tif 000006
【数５】
2020088640.tif 000007
式５は、各コアが形成したデータ構造の要素をアイテム毎に比較し、当該要素内の統計値をいずれか一つの要素にまとめるとともに、他の要素の統計値をゼロとすることを意味する。このように更新できれば出現頻度が０の要素を無視することでデータ構造間の重複要素を除去できる。
【００３９】
具体的には次のように合併工程Ｓ１３を実行する。
［ステップ１］
まずアイテム間に全順序を定める。例えばビット列を自然数とみた順序などである。本実施形態では送信先アドレスの小さい順に作業を行うこととする。
［ステップ２］
ステップ１で定めた全順序に従い各Ｔｉを昇順にソートする（式６及び図５参照）。
【数６】
2020088640.tif 000008
ここでｌｉはリストＴｉの長さである。
［ステップ３］
各リストＴｉ内で処理対象の要素を選出する。
ｉ＝１，２，・・・，ｎについて式７とする。
【数７】
2020088640.tif 000009
ここでｓｉはｉ番目のリストＴｉの中で処理対象とする要素ｘの番号である（要素は、“ｘｉｓｉ”と表現できる。）。つまり、それぞれのＴｉ内で最初の処理対象の要素ｘを選出し、それらの番号ｓ１、ｓ２、ｓ３、ｓ４、・・・を１とする。
［ステップ４］
全てのリストについて選出する要素が存在するか確認する。Ｉは選出した要素ｘの集合である。
【数８】
2020088640.tif 000010
［ステップ５］
Ｉが空集合ならば終了する。
［ステップ６］
選出した要素の中で最小のアイテムをａ＊とする。
【数９】
2020088640.tif 000011
図５の状態であればａ＊＝１９２．０．２．９、図７の状態であればａ＊＝１９２．０．２．１０、図９の状態であればａ＊＝１９２．０．２．１１である。
［ステップ７］
集合Ｉの中で処理対象（アイテムａ＊がである）の要素の番号を見つける。
【数１０】
2020088640.tif 000012
図５の場合、処理対象はｓ３とｓ４であり、Ｊは３と４である。図７の場合、処理対象はｓ１とｓ２とｓ４であり、Ｊは１と２と４である。図９の場合、処理対象はｓ１とｓ３であり、Ｊは１と３である。
［ステップ８］
処理対象の要素の統計値をまとめる。図５、図７及び図９の場合、統計値が出現回数なので、処理対象の要素の出現回数を加算する。
【数１１】
2020088640.tif 000013
なお、前述したように、統計値の種類によって式１１の計算式は異なる。
［ステップ９］
各ｊ∈Ｊについて、式１２のようにリストの要素を更新する。
【数１２】
2020088640.tif 000014
具体的には、処理対象の要素の中で、番号が最小の要素の統計値をステップ８で計算した値に置き換え、他の要素の統計値をゼロに置き換える。
図５の場合、ｓ３とｓ４が処理対象なので、ｓ３の要素の統計値（出現回数）を２から５へ置き換え、ｓ４の要素の統計値（出現回数）を３から０へ置き換える。図６は、統計値を置き換えた後の状態を示している。
図７の場合、ｓ１とｓ２とｓ４が処理対象なので、ｓ１の要素の統計値（出現回数）を４から９へ置き換え、ｓ２とｓ４の要素の統計値（出現回数）をそれぞれ３から０、２から０へ置き換える。図８は、統計値を置き換えた後の状態を示している。
図９の場合、ｓ１とｓ３が処理対象なので、ｓ１の要素の統計値（出現回数）を１から４へ置き換え、ｓ３の要素の統計値（出現回数）を３から０へ置き換える。
［ステップ１０］
次のアイテムについて同様な作業を行う。
各ｊ∈Ｊについて式１３とし、ステップ４に戻る。
【数１３】
2020088640.tif 000015
【００４０】
ステップ２でのソートにクイックソート（非特許文献２）などを使うことで新しいメモリを確保する必要がない。またソート後は各リストを先頭から順番にアクセスするだけなので高速に操作が完了する。
【００４１】
各リストを並列でソートした場合、必要な計算量は式１４となる。
【数１４】
2020088640.tif 000016
各リストを並列にソートできない場合、必要な計算量は式１５となる。
【数１５】
2020088640.tif 000017
【００４２】
［付記］
以下は、本実施形態のトラフィックモニタリング方法を説明したものである。
本発明は、複数ｎ個のコアでトラフィックを観測することで構築された複数ｎ個のデータ構造を、重複要素を排除して合併する方法において、ｉ（ｉは１以上ｎ以下の整数）番目のコアが観測したデータ構造のリストＴｉの各々について「アイテムａｊとその出現回数ｆｊの組合せからなる要素ｘ」をアイテムａｊの所定の全順序に基づいて昇順にソートし、各リストの先頭から順に要素ｘを検査し、同じアイテムａｊからなる要素ｘ含む全てのリストＴｉについて当該要素ｘにおける出現回数ｆｊの総和を算出し、当該要素ｘを含むリストＴｉのうちｉが最小であるリストＴｉの当該要素ｘにおける出現回数ｆｊを算出した総和に置き換え、その他のリストＴｉの当該要素ｘにおける出現回数ｆｊを全て０に置き換える処理を繰り返すことを特徴とする。
【００４３】
本発明は次の３つをポイントとする。
（Ａ）オープンアドレス方式のハッシュテーブルや優先度付きキュー、配列などデータ構造はリストとして扱うこともできること。
（Ｂ）各リストのソートはクイックソートなどを利用すれば新しいメモリを確保することなく高速に実行できること。
（Ｃ）ソート後はリスト全体ではなくリストの先頭の要素のみを調べることで合併できること。
【００４４】
［発明の効果］
複数コアでトラフィックを観測する場合、構築した複数のデータ構造を高速に合併する必要があるが、本発明により、データ構造の再構築、データ構造の検索処理、ＲＳＳ機能の調整をすることなく複数のデータ構造を高速に合併できる。
【符号の説明】
【００４５】
１１：振分部
１２：コア
１３：合併部
【図１】
2020088640.tif 000018
【図２】
2020088640.tif 000019
【図３】
2020088640.tif 000020
【図４】
2020088640.tif 000021
【図５】
2020088640.tif 000022
【図６】
2020088640.tif 000023
【図７】
2020088640.tif 000024
【図８】
2020088640.tif 000025
【図９】
2020088640.tif 000026
【図１０】
2020088640.tif 000027
【図１１】
2020088640.tif 000028
【図１２】
2020088640.tif 000029