(57)【要約】【課題】ネットワーク負荷を抑制しつつ、時間変動の大きなトラヒックをリアルタイムに観測する。【解決手段】データ計数部１１Ａが、フローごとに、観測データに基づいてフローに関する単位時間あたりに転送されたデータの計数値を求め、トラヒック量推定部１１Ｂが、フローごとに、計数値に基づいてフローに関する推定トラヒック量を推定し、平均トラヒック量補正部１１Ｃが、フローごとに、推定トラヒック量に基づいてフローに関する平均トラヒック量を補正し、フローテーブル設定部１１Ｄが、フローごとに、補正した平均トラヒック量と推定トラヒック量との差分を計算し、差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブルを設定する。【選択図】  図１
2018026741.tif 000002
【特許請求の範囲】
【請求項１】
観測対象ネットワークの各所に配置された複数の観測器から通知された、フローのトラヒック量を示す観測データに基づいて、前記フローのトラヒック量を観測・推定するトラヒック観測装置であって、
観測対象としてフローテーブルに登録されている複数のフローエントリに基づいて、これらフローエントリと対応するフローごとに、前記観測データから前記フローに関するトラヒック量を観測・推定する観測・推定部を備え、
前記観測・推定部は、
前記フローごとに、前記観測データに基づいて前記フローに関する単位時間あたりに転送されたデータの計数値を求めるデータ計数部と、
前記フローごとに、前記計数値に基づいて前記フローに関する推定トラヒック量を推定するトラヒック量推定部と、
前記フローごとに、前記推定トラヒック量に基づいて前記フローに関する平均トラヒック量を補正する平均トラヒック量補正部と、
前記フローごとに、補正した前記平均トラヒック量と前記推定トラヒック量との差分を計算し、前記差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブルを設定するフローテーブル設定部とを備える
ことを特徴とするトラヒック観測装置。
【請求項２】
請求項１に記載のトラヒック観測装置において、
前記トラヒック量推定部は、前記計数値が得られた条件における、前記フローに関する平均トラヒック量と前記推定トラヒック量との差分に関する事後確率を求め、前記事後確率に関する平均と分散を得ることにより前記推定トラヒック量の推定を繰り返す最尤推定部を備えることを特徴とするトラヒック観測装置。
【請求項３】
請求項１または請求項２に記載のトラヒック観測装置において、
前記フローテーブル設定部は、候補として選択された候補フローテーブル内からランダムに選択したフローエントリの分割および削除を行うことにより複数の新たな候補フローテーブルを生成し、これら新たな候補フローテーブルのうちから、新たな候補フローテーブルごとに求めた評価指標に基づいて、前記新たなフローテーブルを特定することを特徴とするトラヒック観測装置。
【請求項４】
請求項１〜請求項３のいずれかに記載のトラヒック観測装置において、
前記観測・推定部は、前記データ計数部、前記トラヒック量推定部、前記平均トラヒック量補正部、および前記フローテーブル設定部における演算処理の内容が記述された観測・推定プログラムと、前記観測・推定プログラムで用いる一連の数値計算処理の内容が記述された観測・推定ライブラリプログラムとに基づいて、前記演算処理を高速実行する観測・推定加速部により実現されることを特徴とするトラヒック観測装置。
【請求項５】
観測対象ネットワークの各所に配置された複数の観測器から通知された、フローのトラヒック量を示す観測データに基づいて、前記フローのトラヒック量を観測・推定するトラヒック観測装置で用いられるトラヒック観測方法であって、
観測・推定部が、観測対象としてフローテーブルに登録されている複数のフローエントリに基づいて、これらフローエントリと対応するフローごとに、前記観測データから前記フローに関するトラヒック量を観測・推定する観測・推定ステップを備え、
前記観測・推定ステップは、
前記フローごとに、前記観測データに基づいて前記フローに関する単位時間あたりに転送されたデータの計数値を求めるパケット計数ステップと、
前記フローごとに、前記計数値に基づいて前記フローに関する推定トラヒック量を推定するトラヒック量推定ステップと、
前記フローごとに、前記推定トラヒック量に基づいて前記フローに関する平均トラヒック量を補正する平均トラヒック量補正ステップと、
前記フローごとに、補正した前記平均トラヒック量と前記推定トラヒック量との差分を計算し、前記差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブルを設定するフローテーブル設定ステップとを備える
ことを特徴とするトラヒック観測方法。
【請求項６】
コンピュータが、請求項１〜請求項３のいずれかに記載のトラヒック観測装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信トラヒック観測技術に関し、特に汎用サーバに観測機能を付加してトラヒックを効率的に観測するトラヒック観測技術に関する。
【背景技術】
【０００２】
近年、ネットワークの制御プレーンとデータプレーンを分離し、論理的集中管理によりネットワークサービスの自動化を実現するＳＤＮ（Software Defined Networking）関連技術が、将来の柔軟化指向ネットワークを実現するためのキーテクノロジーとして多くの関心を集めている。その影響はクラウドサービスを提供するためのデータセンタに留まらず、通信事業者の広域インフラの在り方に及んでいる。
【０００３】
背景として、汎用サーバの高性能化が挙げられる。２０１３年には世界の通信事業者が連携して、ＮＦＶ（Network Functions Virtualization）の構想が提唱されている。ＮＦＶは、特定ベンダの高価なプロプライエタリ・ハードウェア装置ではなく、安価なコモディティ・ハードウェアとネットワーク仮想化技術を用いて、ソフトウェア主体で迅速かつ柔軟にネットワークサービスを提供し、設備コストおよび運用コストの低減を図るものである。
【０００４】
このようなＳＤＮやＮＦＶによるネットワークに限らず、従来からのＩＰネットワークにおける負荷の高い処理のひとつに、通信トラヒック量を観測して情報収集・制御するネットワーク統計情報処理がある。ネットワーク管理者は輻輳を起こすことなく変動するトラヒックを収容しなければならない。従来、ネットワーク管理者はトラヒックを収容するために、冗長なリンク容量を用意することによってこの問題を回避してきた。しかしながら、このアプローチではトラヒック変動の増加に合わせて高いコストが必要になる。
【０００５】
多大なコストを必要せずに変動するトラヒックを収容する方法の一つとして、トラヒック変動に追随して経路を動的に設定する手法が検討されている。このアプローチはＴＥ（トラヒックエンジニアリング：Traffic Engineering）と呼ばれ盛んに研究されている。ＴＥでは通常、管理装置が設置されることになる。管理装置はネットワーク内のノードからトラヒック観測情報を収集し、次に、収集したトラヒック観測情報に基づいて適切な経路を算出する。
【０００６】
既存のＴＥの手法ではＮｅｔＦｌｏｗ（非特許文献１）やｓＦｌｏｗ（非特許文献２）などのトラヒック観測技術が用いられる。ＮｅｔＦｌｏｗは、観測器においてフロー毎にトラヒックカウンタを用意しパケットが到着するとそれらを計数し、管理装置において全観測器からフロー統計値を収集してトラヒック観測情報を取得する方式である。一方、ｓＦｌｏｗは、観測器でサンプリングされたパケット情報を整理し直接管理装置に送信する方式であり、管理装置はサンプリングされたパケット情報に基づいてトラヒック情報を把握することができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】B.Claise，"Cisco Systems NetFlow Services Export Version 9"，RFC 3954，Oct.2004，p.9，「5. Export Packet Format」
【非特許文献２】Peter Phaal 他，"sFlow Version 5"，Jul.2004, http://sflow.org/sflow_version_5.txt，p.6，「3. Sampling Mechanisms」
【非特許文献３】T.Benson 他，"MicroTE: Fine Grained Traffic Engineering for Data Centers"，in Proceedings of ACM CoNEXT，2011
【非特許文献４】辻ほか，"圧縮センシングを用いた時空間階層化トラヒック観測手法"，信学技報，vol.114，no.478，IN2014-162，pp.243-248，Mar.2015
【非特許文献５】"OpenFlow Switch Specification"，OPEN NETWORKING FOUNDATION，Version 1.3.4(Protocol version 0x04)，March 27，2014
【発明の概要】
【発明が解決しようとする課題】
【０００８】
これらＴＥの手法の大半は、日単位のトラヒック変動に焦点を置き、数時間の間隔で定期的に経路を設定する。しかしながら、このような時間間隔での経路制御は、トラヒック変動がかなり大きい場合には十分に対応できない。例えば、非特許文献３では、数秒間隔での経路制御はデータセンターネットワーク内の通信ノード間の十分な帯域確保に必要であることが示されている。
【０００９】
短い時間間隔でのＴＥを達成するためには、短い間隔でのトラヒック観測情報の収集が必要となる。しかしながら、短い間隔でトラヒック観測情報を収集する際、ネットワークのうち情報収集を行うトラヒック観測装置の近くでトラヒックが集中し、大きな負荷が発生するため、かなりのオーバーヘッドを要する。そこでは、多数のノードからの大量のトラヒック観測情報が短い間隔で定期的にトラヒック観測装置に送信されることになるため、トラヒック観測装置付近のリンクは特に混雑するという問題点がある。
【００１０】
本発明はこのような課題を解決するためのものであり、ネットワーク負荷を抑制しつつ、時間変動の大きなトラヒックをリアルタイムに観測できるトラヒック観測技術を提供することを目的としている。
【課題を解決するための手段】
【００１１】
このような目的を達成するために、本発明にかかるトラヒック観測装置は、観測対象ネットワークの各所に配置された複数の観測器から通知された、フローのトラヒック量を示す観測データに基づいて、前記フローのトラヒック量を観測・推定するトラヒック観測装置であって、観測対象としてフローテーブルに登録されている複数のフローエントリに基づいて、これらフローエントリと対応するフローごとに、前記観測データから前記フローに関するトラヒック量を観測・推定する観測・推定部を備え、前記観測・推定部は、前記フローごとに、前記観測データに基づいて前記フローに関する単位時間あたりに転送されたデータの計数値を求めるデータ計数部と、前記フローごとに、前記計数値に基づいて前記フローに関する推定トラヒック量を推定するトラヒック量推定部と、前記フローごとに、前記推定トラヒック量に基づいて前記フローに関する平均トラヒック量を補正する平均トラヒック量補正部と、前記フローごとに、補正した前記平均トラヒック量と前記推定トラヒック量との差分を計算し、前記差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブルを設定するフローテーブル設定部とを備えている。
【００１２】
また、本発明にかかる上記トラヒック観測装置の一構成例は、前記トラヒック量推定部が、前記計数値が得られた条件における、前記フローに関する平均トラヒック量と前記推定トラヒック量との差分に関する事後確率を求め、前記事後確率に関する平均と分散を得ることにより前記推定トラヒック量の推定を繰り返す最尤推定部を備えている。
【００１３】
また、本発明にかかる上記トラヒック観測装置の一構成例は、前記フローテーブル設定部が、候補として選択された候補フローテーブル内からランダムに選択したフローエントリの分割および削除を行うことにより複数の新たな候補フローテーブルを生成し、これら新たな候補フローテーブルのうちから、新たな候補フローテーブルごとに求めた評価指標に基づいて、前記新たなフローテーブルを特定するようにしたものである。
【００１４】
また、本発明にかかる上記トラヒック観測装置の一構成例は、前記観測・推定部が、前記データ計数部、前記トラヒック量推定部、前記平均トラヒック量補正部、および前記フローテーブル設定部における演算処理の内容が記述された観測・推定プログラムと、前記観測・推定プログラムで用いる一連の数値計算処理の内容が記述された観測・推定ライブラリプログラムとに基づいて、前記演算処理を高速実行する観測・推定加速部により実現されている。
【００１５】
また、本発明にかかるトラヒック観測方法は、観測対象ネットワークの各所に配置された複数の観測器から通知された、フローのトラヒック量を示す観測データに基づいて、前記フローのトラヒック量を観測・推定するトラヒック観測装置で用いられるトラヒック観測方法であって、観測・推定部が、観測対象としてフローテーブルに登録されている複数のフローエントリに基づいて、これらフローエントリと対応するフローごとに、前記観測データから前記フローに関するトラヒック量を観測・推定する観測・推定ステップを備え、前記観測・推定ステップは、前記フローごとに、前記観測データに基づいて前記フローに関する単位時間あたりに転送されたデータの計数値を求めるパケット計数ステップと、前記フローごとに、前記計数値に基づいて前記フローに関する推定トラヒック量を推定するトラヒック量推定ステップと、前記フローごとに、前記推定トラヒック量に基づいて前記フローに関する平均トラヒック量を補正する平均トラヒック量補正ステップと、前記フローごとに、補正した前記平均トラヒック量と前記推定トラヒック量との差分を計算し、前記差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブルを設定するフローテーブル設定ステップとを備えている。
【００１６】
また、本発明にかかるプログラムは、コンピュータが、前述したいずれかのトラヒック観測装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１７】
本発明によれば、観測対象ネットワークを流れるフローのうち、平均トラヒック量と推定トラヒック量との差分が大きいフローが、優先的に観測されることになる。このため、トラヒック観測装置ＳＶに集中する負荷を低減しながら、トラヒックの急増等の突発的な環境変動に精度よく追随して、必要な粒度のフローのトラヒック量を推定することができ、高精度にトラヒック観測することが可能となる。したがって、観測対象ネットワークに対する負荷を抑制しつつ、時間変動の大きなトラヒックをリアルタイムに観測することが可能となり、結果として動的なＳＤＮ制御を実現することができる。
【図面の簡単な説明】
【００１８】
【図１】トラヒック観測装置の構成を示すブロック図である。
【図２】トラヒック観測装置が利用される一般的なトラヒック観測システムを示す説明図である。
【図３】観測・推定部の回路構成例である。
【図４】トラヒック観測装置で実行される観測・推定処理を示すフローチャートである。
【図５】一般的なフローテーブルの構成例である。
【図６】ＥＭ法に基づく事後確率の平均・標準偏差算出処理を示すフローチャートである。
【図７】フローテーブル設定処理を示すフローチャートである。
【発明を実施するための形態】
【００１９】
次に、本発明の一実施の形態について図面を参照して説明する。
［トラヒック観測装置］
まず、図１および図２を参照して、本実施の形態にかかるトラヒック観測装置ＳＶについて説明する。図１は、トラヒック観測装置の構成を示すブロック図である。図２は、トラヒック観測装置が利用される一般的なトラヒック観測システムを示す説明図である。
【００２０】
このトラヒック観測装置ＳＶは、全体としてサーバ装置などの情報処理装置からなり、観測対象ネットワークＮＷの各所に配置されて、指定されたフローに関するトラヒック量を観測する複数の観測器ＴＲを備えるトラヒック観測システム１で用いられて、観測器ＴＲから通知されたフローのトラヒック量を示す観測データに基づいて、フローのトラヒック量を観測・推定する装置である。
【００２１】
トラヒック観測装置ＳＶには、主な回路部として、観測・推定部１１、メインメモリ１２、メインプロセッサ１３、およびフローテーブル１４が設けられている。
観測・推定部１１は、観測対象としてフローテーブル１４に登録されている複数のフローエントリに基づいて、これらフローエントリと対応するフローごとに、前記観測データからフローに関するトラヒック量を観測・推定する機能を有している。
【００２２】
メインメモリ１２は、ハードディスクや半導体メモリなどの記憶装置からなり、観測・推定部１１で実行する演算処理の内容が記述された観測・推定プログラム１２Ａや、観測・推定プログラム１２Ａで用いる一連の数値計算処理の内容が記述された観測・推定ライブラリプログラム１２Ｂ、さらにはメインプロセッサ１３で実行するメインプログラムなどの各種処理情報を記憶する機能を有している。
【００２３】
メインプロセッサ１３は、汎用サーバで用いられるＣＰＵからなり、メインメモリ１２のメインプログラムを実行することにより、トラヒック観測装置ＳＶ全体の動作を制御する機能と、観測・推定プログラム１２Ａおよび観測・推定ライブラリプログラム１２Ｂに基づいて観測・推定部１１を制御する機能とを有している。
フローテーブル１４は、半導体メモリなどの記憶装置からなり、観測対象となるフローのフローエントリが登録されている処理データである。
【００２４】
図２に示すように、一般的なトラヒック観測システム１では、観測対象ネットワークＮＷの各所に配置され観測器ＴＲ、この例では６個の観測器ＴＲ１〜ＴＲ６で指定されたフローｊのトラヒック量が観測され、得られた観測データがＸ１ｊ〜Ｘ６ｊがトラヒック観測装置ＳＶに通知される。
【００２５】
具体的には、観測器ＴＲｉにおいて、過去に観測されたトラヒック情報をもとに、指定されたフローｊについてトラヒック予測モデルＭｉｊを生成してトラヒック観測装置ＳＶに通知する。以後、ＴＲｉは、フローｊの観測データＸｉｊとＭｉｊとの誤差を計算し、誤差が許容値を超える場合は、Ｍｉｊから得られた予測値ＥｉｊとＸｉｊとの差分データＤｉｊを量子化し、得られた差分データＤＸｉｊをＳＶへ通知する。ＳＶでは、ＤＸｉｊを逆量子化して得られた差分値Ｄｉｊと、予め通知されたＭｉｊから得られた予測値Ｅｉｊとから、元の観測データＸ‘ｉｊを推定する。
【００２６】
この際、各観測地点で生成された差分データＤＸｉｊは、ＳＶを根とする木構造の経路に沿って通知される。その際、各観測器ＴＲでは、自身の子となる観測器ＴＲから転送されてきた差分情報を含むパケットと自身の差分情報を合わせて少数のパケットとなるように圧縮した上で転送を行う。これにより、ネットワーク内のいずれの地点においても、観測周期ごとに少数のパケットしか流れず、ネットワークの帯域を圧迫することを防ぐことができる。
【００２７】
しかしながら、短い時間間隔でトラヒック観測情報を収集するには、各観測器ＴＲのフロー数によっては依然として大きなオーバーヘッドを要する。なぜなら、多数の観測器ＴＲからの大量のトラヒック観測情報が短い時間間隔で定期的にトラヒック観測装置ＳＶに送られることになるため、トラヒック観測装置ＳＶ付近のリンクが特に混雑するからである。
【００２８】
本発明にかかるトラヒック観測装置ＳＶは、特にこのような課題を考慮したものであり、観測・推定部１１における主な処理部として、データ計数部１１Ａ、トラヒック量推定部１１Ｂ、平均トラヒック量補正部１１Ｃ、およびフローテーブル設定部１１Ｄを設けたものである。
【００２９】
すなわち、データ計数部１１Ａは、フローごとに、観測データに基づいてフローに関する単位時間あたりに転送されたデータの計数値（パケット数やデータ数）を計数する機能を有している。
トラヒック量推定部１１Ｂは、フローごとに、計数値からフローに関する推定トラヒック量を推定する機能を有している。
【００３０】
平均トラヒック量補正部１１Ｃは、フローごとに、推定トラヒック量に基づいてフローに関する平均トラヒック量を補正する機能を有している。
フローテーブル設定部１１Ｄは、フローごとに、補正した平均トラヒック量と推定トラヒック量との差分を計算し、差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブル１４を設定する機能を有している。
【００３１】
図３は、観測・推定部の回路構成例である。本発明におけるトラヒック観測装置ＳＶの構成上の特徴は、観測・推定プログラム１２Ａおよび観測・推定ライブラリプログラム１２Ｂで動作する観測・推定部１１を汎用サーバの拡張機能としてアドオン可能としている点である。これにより、観測性能が問題にならないケースでは観測・推定部１１における観測機能を、メインプロセッサ１３上にソフトウェアとして実装することができる。
【００３２】
一方、観測性能が問題となる場合は、図３に示すとおり、ＦＰＧＡ（Field Programmable Gate Array）のようなプログラマブルデバイス上のアクセラレータ機能として、観測・推定部１１における観測機能を観測・推定加速部２１上に処理モジュールとして実装してもよい。この場合、ＰＣＩ  Ｅｘｐｒｅｓｓに代表されるシリアルＩ／Ｏインタフェースを介して汎用サーバの拡張ボードとして観測・推定部１１を実装することができ、汎用サーバによるソフトウェア処理の柔軟性を保ちながら、処理性能を補うことができる。したがって、実装するプログラムおよびデバイスの別を問わず、通信用デバイス一般に適用することができる。
【００３３】
観測・推定加速部２１は、データ計数部１１Ａ、トラヒック量推定部１１Ｂ、平均トラヒック量補正部１１Ｃ、およびフローテーブル設定部１１Ｄにおける演算処理の内容が記述された観測・推定プログラム１２Ａと、観測・推定プログラム１２Ａで用いる一連の数値計算処理の内容が記述された観測・推定ライブラリプログラム１２Ｂとに基づいて、演算処理を高速実行する機能を有している。
制御Ｉ／Ｆ部２２は、観測・推定プログラム１２Ａに記述された指示に応じて、観測・推定加速部２１での演算処理に用いる各種処理データの設定および参照を行う機能を有している。
【００３４】
観測データの取得方法である統計情報取得ステップについては、非特許文献４において圧縮センシングを用いた取得手法が提案されており、トラヒック観測装置ＳＶは観測対象ネットワークＮＷ上に分散配置されている複数の観測器ＴＲから観測データを効率的に収集することができる。
トラヒック観測装置ＳＶは、このようにして収集した観測データ２３に基づいて、推定トラヒック量２４の推定、平均トラヒック量２５の補正、さらにはフローテーブル１４の設定かかる多量の計算を、観測・推定プログラム１２Ａと連携する観測・推定ライブラリプログラム１２Ｂを通じて、高速に処理することができるだけでなく、制御Ｉ／Ｆ部２２を通じて柔軟に観測・推定加速部２１の動作を変更することができる。
【００３５】
［本実施の形態の動作］
次に、図４を参照して、本実施の形態にかかるトラヒック観測装置ＳＶの動作について説明する。図４は、トラヒック観測装置で実行される観測・推定処理を示すフローチャートである。
【００３６】
周期的な処理タイミングを示すタイムスロットの到来に応じて、観測・推定部１１は、図４の観測・推定処理を実行する。なお、各観測器ＴＲで観測されたフローに関する観測データがトラヒック観測装置ＳＶに通知されるごとに、データ計数部１１Ａは、通知された観測データ２３から、観測時刻ｔにおける単位時間あたりの計数値Ｙ（ｔ）をフローごとに計数し、フローテーブル１４のうち対応するフローエントリの統計情報として保存する。
【００３７】
また、トラヒック観測システム１において、各観測器ＴＲにおけるトラヒック情報の収集、推定、観測に用いるルーティングテーブル１４の設定は、トラヒック観測装置ＳＶにより行う。このため、トラヒック観測装置ＳＶでは、トラヒック量の把握が必要な各フローに対して、それぞれのフローについて、予め設定されている直近の観測区間における平均トラヒック量Ｔavg（加重移動平均値）を保持している。
【００３８】
図５は、一般的なフローテーブルの構成例である。ここでは、非特許文献５に記された、ＳＤＮを実現するための１つの技術標準で用いられているフローテーブルの構成例が示されており、フローごとに、マッチ条件（Match fields），優先度（Priority），統計情報（Counters），実行処理（Instruction），寿命（Timeouts），識別情報（Cookie），フラグ（Flags）の組がフローエントリとして登録されている。
【００３９】
まず、トラヒック量推定部１１Ｂは、フローテーブル１４に登録されているフローエントリと対応するフローについて、それぞれのフローに関する現時点ｔにおける計数値Ｙ（ｔ）をフローテーブル１４から取得し（ステップＳ１０）、それぞれのフローに関する推定トラヒック量Ｔ（ｔ）を推定する（ステップＳ１１）。
【００４０】
次に、平均トラヒック量補正部１１Ｃは、フローごとに、それぞれの推定トラヒック量Ｔ（ｔ）に基づいて、長期にわたる平均的なトラヒック量を示す平均トラヒック量Ｔavgを補正する（ステップＳ１２）。
【００４１】
この後、フローテーブル設定部１１Ｄは、フローごとに、補正した平均トラヒック量Ｔavgと推定トラヒック量Ｔ（ｔ）との差分μfを計算し、得られた差分μfに基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブル１４を設定し（ステップＳ１３）、一連の観測・推定処理を終了する。これにより差分が大きいフローが重点的に観測されるように、次のタイムスロットにおける観測用のフローテーブル１４が設定される。
【００４２】
［トラヒック量推定処理］
次に、トラヒック量推定部１１Ｂにおけるトラヒック量推定処理について詳細に説明する。
トラヒック量推定部１１Ｂにおけるトラヒック量推定処理（図４のステップＳ１１に相当）は、対象フローの計数値が計数された条件における、現時点のトラヒック量と平均トラヒック量との差分の事後確率を求め、その平均と分散を得ることにより現時点における各フローのトラヒック量の推定を繰り返す最尤推定ステップを有する。
【００４３】
本ステップでは、現時点ｔにおけるフローエントリの計数値Ｙ（ｔ）を取得し、観測が必要な粒度での各フローの推定トラヒック量Ｔ（ｔ）を推定する。ここで、現時点ｔにおけるフローテーブル１４の設定より求まる、計数値Ｙ（ｔ）と各フローの関係を示す行列Ａ（ｔ）を定義する。すると、次の式（１）に示す関係が成り立つ。
【数１】
2018026741.tif 000003
【００４４】
そのため、この関係が成り立つように、推定トラヒック量Ｔ（ｔ）を推定すればよい。
ここで、Ｔ（ｔ）の要素のうち、Ｔavgと大きくかけ離れているフローは少ないと考えられる。そのため、本手法では、次の式（２）の関係を持つ、ＴavgとＴ（ｔ）との差分、すなわちトラヒックの短期変動成分ΔＴ（ｔ）を推定することにより、Ｔ（ｔ）を求める。
【数２】
2018026741.tif 000004
【００４５】
ここで、ΔＴ（ｔ）は、次の式（３）に示す条件を満たし、かつ、ΔＴ（ｔ）のうち大きな値となる要素は限られている。そのため、圧縮センシングを適用し、ΔＴ（ｔ）を求めることができると考えられる。
【数３】
2018026741.tif 000005
【００４６】
本発明では、ΔＴ（ｔ）の事前確率として、次の式（４）で示される確率を与える。また、ΔＴ（ｔ）の事後確率は、Ｙ（ｔ）とΔＴ（ｔ）との関係より、次の式（５）となる。ただし、Ｎ（）は正規分布、Γ（）はガンマ関数を示す。また、αは正規分布の標準偏差を示す変数であり、その分布は式（４）で定義されている。なお、ａ，ｂはαを定義するガンマ分布のパラメータである。また、式（５）のα0-1はトラヒック量の観測誤差に関する標準偏差である。
【００４７】
【数４】
2018026741.tif 000006
【数５】
2018026741.tif 000007
【００４８】
ここで、ベイズの定理により、次の式（６）に示す関係が成立する。そのため、事後確率Ｐ（ΔＴ（ｔ）｜Ｙ（ｔ））は、αが決まれば、多変量正規分布として定めることができる。
【数６】
2018026741.tif 000008
【００４９】
本発明における最尤推定ステップでは、この事後確率についての平均と標準偏差をＥＭ法により定める。図６は、ＥＭ法に基づく事後確率の平均・標準偏差算出処理を示すフローチャートである。
【００５０】
図６では、まず、αを固定し、次の式（７）に基づき、事後確率の平均μと標準偏差Σ（分散σ2）を求める（ステップＳ２０）。
【数７】
2018026741.tif 000009
【００５１】
次に、事後確率の平均μと標準偏差Σを固定した上で、次の式（８）に基づいて、Ｐ（Ｙ（ｔ）｜α）を最大化するようなαを求める（ステップＳ２１）。ただし、ＫはＹ（ｔ）の要素数を示す。
【数８】
2018026741.tif 000010
【００５２】
この後、直前の平均μ’と比べた新たな平均μの変化（αiのうちの最大値：ｍａｘi｜μi-μ’i｜）と閾値Ｔbayesとを比較することにより得られた解の収束有無を判定し（ステップＳ２２）、平均μの変化が閾値Ｔbayes以上であれば（ステップＳ２２：ＮＯ）、収束なしと判定して新たな平均μを直前の平均μ’として保存した後（ステップＳ２３）、ステップＳ２０へ戻って、事後確率の平均μと標準偏差Σの算出を繰り返す。
【００５３】
一方、平均μの変化が閾値Ｔbayesを下回った時点で（ステップＳ２２：ＹＥＳ）、収束ありと判定して繰り返しを終了する。これにより、求めた平均μを用いて、現時点ｔにおける推定トラヒック量Ｔ（ｔ）を得ことができる。
【００５４】
［平均トラヒック量補正処理］
次に、平均トラヒック量補正部１１Ｃにおける平均トラヒック量補正処理について詳細に説明する。
平均トラヒック量補正部１１Ｃにおける平均トラヒック量補正処理（図４のステップＳ１２に相当）は、推定トラヒック量Ｔ（ｔ）の加重移動平均により平均トラヒック量Ｔavgを求めるものとする。ただし、現時点ｔの推定トラヒック量Ｔ（ｔ）には、推定誤差が含まれる。そのため、推定誤差が大きいフローのトラヒック量がＴavgに大きな影響を与えることを防ぐ必要がある。
【００５５】
本発明では、ベイズ推定により各時刻ｔの推定トラヒック量Ｔ（ｔ）を得ており、その平均μと分散σが得られる。そのため、本発明では、分散σが大きく、正確な推定値が得られていないと考えられるフローについては、Ｔavgに影響を与えないようにする。本ステップにおいて、Ｔavgの各要素Ｔfavgは、次の式（９）のように補正する。
【数９】
2018026741.tif 000011
【００５６】
この際、μfはＴavgと推定トラヒック量Ｔ（ｔ）との差分の予測値である。また、γfは次の式（１０）のように定める。ただし、γallはパラメータであり、σfはフローｆのベイズ推定の予測値の標準偏差である。
【数１０】
2018026741.tif 000012
【００５７】
［フローテーブル設定処理］
次に、図７を参照して、フローテーブル設定部１１Ｄにおけるフローテーブル設定処理について詳細に説明する。図７は、フローテーブル設定処理を示すフローチャートである。
フローテーブル設定部１１Ｄにおけるフローテーブル設定処理は、現時点で候補となっているフローテーブル候補について、フローテーブル候補内からランダムに選択したフローエントリよりも細粒度なエントリを追加するフロー分割ステップと、同じくフローテーブル候補内からランダムに選択したフローエントリを削除するフロー削除ステップとを行うことにより新たなフローテーブル候補を生成するフローテーブル候補生成ステップと、これら新たなフローテーブル候補の優先順位に基づいて、新たなフローテーブル候補を淘汰するフローテーブル候補淘汰ステップとを備え、これを繰り返すことにより、適切なフローテーブル１４を求めることを特徴とする。
【００５８】
現時点におけるトラヒック量が平均トラヒック量と近いフローについては、新たな観測結果を得なくても精度よくトラヒック量が求まるのに対して、平均トラヒック量と大きくかけ離れたフローについては、新たな観測結果を得ないと正確なトラヒック量を推定することは困難である。
そこで、本発明では、平均トラヒック量との差が大きくなる可能性の高いフローを精度よく観測できるようなフローテーブル１４を設定する。
【００５９】
図７に示す手順では、まず、現時点で候補となっているフローテーブル候補について、フローテーブル候補のランダムに選択したフローエントリの、より細粒度なエントリ、すなわち、時間粒度（タイムスロット単位での時間範囲）および空間粒度（１ｂｉｔ単位での送信元・宛先ＩＰアドレスのプレフィックス等）の、より細かいエントリを追加するフローの分割と、ランダムに選択したフローエントリの削除とを行うことにより、新たなフローテーブル候補を生成する（ステップＳ３０）。
【００６０】
次に、これら新たなフローテーブル候補のそれぞれについて、例えば後述する観測行列のランクを示す指標１や予期される推定誤差の重み付きの和を示す指標２などからなるの指標を計算して優先順位を特定し、優先順位が下位の候補を淘汰する（ステップＳ３１）。
この後、残った新たなフローテーブル候補のうち、最も優先順位が高いフローテーブル候補を新たな最善解として選択し、直前の繰り返しで得られた最善解の指標から新たな最善解の指標の差分、すなわち新たな最善解の指標に関する改善幅が、予め設定されている基準値Ｔrule以上である場合は（ステップＳ３２：ＮＯ）、ステップＳ３０に戻って新たなフローテーブル候補を生成する。また、改善幅が基準値Ｔruleより小さくなった時点で（ステップＳ３２：ＹＥＳ）、繰り返しを終了する。
【００６１】
本手順において、フローテーブル候補の優先順位は以下の２つの指標をもとに定める。
指標１：観測行列のランク
各フローテーブル候補について、ｉ行ｊ列の要素を、観測対象フローのうちｊ個目のフローがｉ個目のフローエントリのルールにマッチする場合は１、それ以外は０に定める観測行列Ａcand（ｔ＋１）を定義し、当該フローテーブル候補を設定した際に得られる観測行列Ａcand（ｔ＋１）のランクが大きいフローテーブル候補を優先する。これにより、より多くのフローに関する情報を取得可能なフローテーブル１４を設定可能となる。
【００６２】
指標２：予期される推定誤差の重み付きの和
各フローについて予期される推定誤差と、当該フローの観測の重要度の積を求め、その和が小さいものを優先する。
これにより、重要なフローを正確に推定できるようなフローテーブル１４が設定される。
【００６３】
ここで、各フローについて予測される推定誤差の大きさは、次の式（１１）のＹ’（ｔ＋１）が観測されたという条件下においてベイズ推定を行い、得られた各フローの推定結果に対する標準偏差σ’とする。ただし、Ｔ’（ｔ＋１）は、現時点の推定トラヒック量とする。
【数１１】
2018026741.tif 000013
【００６４】
また、各フローの重要度は、直近の推定トラヒック量が平均トラヒック量とかけ離れたと考えられるフローを重要視できるように決める。ただし、推定誤差が大きく正しく推定できていない可能性がある箇所も存在することを考慮に入れる必要がある。上記を考慮し、フローｆの重要度Ｇfを次の式（１２）のように定める。これにより、推定結果の標準偏差も考慮した上で、長期的平均と現在のトラヒックの差が大きくなる可能性の高いフローを重視することができる。
【数１２】
2018026741.tif 000014
【００６５】
［本実施の形態の効果］
このように、本実施の形態は、観測・推定部１１において、データ計数部１１Ａが、フローごとに、観測データに基づいてフローに関する単位時間あたりに転送されたデータの計数値を求め、トラヒック量推定部１１Ｂが、フローごとに、計数値に基づいてフローに関する推定トラヒック量を推定し、平均トラヒック量補正部１１Ｃが、フローごとに、推定トラヒック量に基づいてフローに関する平均トラヒック量を補正し、フローテーブル設定部１１Ｄが、フローごとに、補正した平均トラヒック量と推定トラヒック量との差分を計算し、差分に基づいて観測すべきフローを特定し、これらフローのフローエントリが登録された新たなフローテーブル１４を設定するようにしたものである。
【００６６】
これにより、観測対象ネットワークＮＷを流れるフローのうち、平均トラヒック量と推定トラヒック量との差分が大きいフローが、優先的に観測されることになる。このため、トラヒック観測装置ＳＶに集中する負荷を低減しながら、トラヒックの急増等の突発的な環境変動に精度よく追随して、必要な粒度のフローのトラヒック量を推定することができ、高精度にトラヒック観測することが可能となる。したがって、観測対象ネットワークＮＷに対する負荷を抑制しつつ、時間変動の大きなトラヒックをリアルタイムに観測することが可能となり、結果として動的なＳＤＮ制御を実現することができる。
【００６７】
以上、本発明の実施形態が示され、説明がなされた。実施形態の説明において「〜部」と説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手段」、「〜処理」であってもよい。また、本実施形態で「〜部」として説明しているものは、ＲＯＭに記憶されたファームウェアおよび再構成型デバイス・素子・基板・配線などのハードウェアで実現されていても構わない。或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵにより読み出されて実行される。すなわち、プログラムは、本発明の実施形態の「〜部」としてコンピュータを機能させるものである。あるいは、実施形態の「〜部」の手順や方法をコンピュータに実行させるものである。
【００６８】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【００６９】
１…トラヒック観測システム、ＳＶ…トラヒック観測装置、１１…観測・推定部、１１Ａ…データ計数部、１１Ｂ…トラヒック量推定部、１１Ｃ…平均トラヒック量補正部、１１Ｄ…フローテーブル設定部、１２…メインメモリ、１２Ａ…観測・推定プログラム、１２Ｂ…観測・推定ライブラリプログラム、１３…メインプロセッサ、１４…フローテーブル、２１…観測・推定加速部、２２…制御Ｉ／Ｆ部、２３…観測データ、２４…推定トラヒック量、２５…平均トラヒック量、ＴＲ…観測器、ＮＷ…観測対象ネットワーク。
【図１】
2018026741.tif 000015
【図２】
2018026741.tif 000016
【図３】
2018026741.tif 000017
【図４】
2018026741.tif 000018
【図５】
2018026741.tif 000019
【図６】
2018026741.tif 000020
【図７】
2018026741.tif 000021