(57)【要約】【課題】  マクロフロー安定性とマクロフロー数、マクロフローサイズのそれぞれの条件を満たすようなマクロフローを生成する。【解決手段】  本発明は、ネットワークのマクロフローの時系列トラヒック情報が与えられると、トラヒック情報をフロー制御技術でのトラヒックサイズが一定の範囲に収まるように任意の粒度に分解し、マクロフロー安定性、マクロフロー数、マクロフローサイズのそれぞれの条件を満たすマクロフローを生成し、解マクロフローとして解マクロフロー記憶手段に格納する。【選択図】  図２
2015156529.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークのトラヒックを収容する際に、トラヒックをマクロフロー単位に分割して制御するフロー集約装置であって、
前記ネットワークのマクロフローの時系列トラヒック情報が与えられると、トラヒック情報をフロー制御技術で制御可能な粒度に分解し、マクロフロー安定性、マクロフロー数、マクロフローサイズのそれぞれの条件を満たすマクロフローを生成し、解マクロフローとして解マクロフロー記憶手段に格納するマクロフロー算出手段を
有することを特徴とするフロー集約装置。
【請求項２】
前記マクロフロー算出手段は、
任意のフローヘッダ情報に基づいて、多次元フローデータベースにアクセスし、前記マクロフローの時系列トラヒック情報を取得する手段と、
前記時系列トラヒック情報のフローサイズが所定の閾値以上となるフロー情報を候補マクロフロー情報記憶手段に格納する手段と、
乱数X(0≦X≦1)を生成し、所定の制御パラメータとの大小関係により、前記候補マクロフロー情報記憶手段から、所定の安定条件を満たす単一安定マスクフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の非安定条件を満たす単一非安定マクロフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の複合安定条件を満たすマクロフローの組み合わせを選択して解マクロフローとして解マクロフロー記憶手段に格納する、または、該候補マクロフロー情報記憶手段の候補マクロフローリストを拡張するマクロフロー選択手段と、
前記解マクロフロー記憶手段の前記解マクロフローを前記多次元フローデータベースから削除し、更新後の多次元フローデータベースの情報でフローサイズ、時系列変動係数を再計算し、前記候補マクロフロー記憶手段を更新する更新手段と、
を含む請求項１記載のフロー集約装置。
【請求項３】
前記マクロフロー選択手段は、
候補マクロフロー拡張による解空間の探索と解マクロフロー選択による解選択をどの割合で実施するかを決める制御パラメータC、所定の閾値を表す制御パラメータA、制御パラメータBを用いて、
前記乱数Xが前記制御パラメータAより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の安定条件を満たすM個のマクロフローをランダムに選択し、前記単一安定マクロフローとして前記解マクロフロー記憶手段に格納する手段と、
前記乱数Xが前記制御パラメータA以上、かつ、前記制御パラメータBより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の非安定条件を満たすM個のマクロフローからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納する手段と、
前記乱数Xが前記制御パラメータB以上、かつ、前記制御パラメータCより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の複合安定条件を満たすM個のマクロフローの組み合わせからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納する手段と、
前記乱数Xが前記制御パラメータC以上である場合は、フローサイズが上位L個のN（N≦４）次元マクロフローからランダムに１つ選択し、選択したN次元マクロフローのヘッダ情報の未選択次元の各値から、選択することで最もフローサイズが大きくなる値を１つ選択し、マクロフローヘッダに追加してN+1次元のマクロフローを生成し、前記候補マクロフロー記憶手段に追加する手段と、
を含む請求項２記載のフロー集約装置。
【請求項４】
前記所定の安定条件を、
トラヒック安定条件CV(f)< CV_stable（但し、fはマクロフロー、CV(f)は該fの時系列トラヒック量の変動係数、stablecvは解マクロフローに安定フローとして追加できる最大の変動係数）及び、トラヒックサイズ条件sizemin<size(f)<sizemax（但し、size(f)は時系列トラヒック量の平均値、sizeminは解マクロフローに追加できる最小のフローサイズ、sizemaxは解マクロフローに追加できる最大のフローサイズ）とし、
前記所定の非安定条件を、
トラヒック非安定条件CV(f)< CV_unstable（但し、fはマクロフロー、CV(f)は該fの時系列トラヒック量の変動係数）及び、トラヒックサイズ条件sizemin<size(f)<sizemax（但し、size(f)は時系列トラヒック量の平均値）とし、
前記所定の複合安定条件を、
トラヒック安定条件CV(f+g)< CV_stable（但し、f+gは時系列データを合算したマクロフロー、CV(f+g)は該f+gの時系列トラヒック量の変動係数）及び、トラヒックサイズ条件sizemin<size(f+g)<sizemax（但し、size(f+g)はf+gの時系列トラヒック量の平均値）とする
請求項２または３に記載のフロー集約装置。
【請求項５】
ネットワークのトラヒックを収容する際に、トラヒックをマクロフロー単位に分割して制御するフロー集約方法であって、
フロー集約装置が、
前記ネットワークのマクロフローの時系列トラヒック情報が与えられると、トラヒック情報をフロー制御技術で制御可能な粒度に分解し、マクロフロー安定性、マクロフロー数、マクロフローサイズのそれぞれの条件を満たすマクロフローを生成し、解マクロフローとして解マクロフロー記憶手段に格納するマクロフロー算出ステップを
行うことを特徴とするフロー集約方法。
【請求項６】
前記マクロフロー算出ステップにおいて、
任意のフローヘッダ情報に基づいて、多次元フローデータベースにアクセスし、前記マクロフローの時系列トラヒック情報を取得するステップと、
前記時系列トラヒック情報のフローサイズが所定の閾値以上となるフロー情報を候補マクロフロー情報記憶手段に格納するステップと、
乱数X(0≦X≦1)を生成し、所定の制御パラメータとの大小関係により、前記候補マクロフロー情報記憶手段から、所定の安定条件を満たす単一安定マスクフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の非安定条件を満たす単一非安定マクロフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の複合安定条件を満たすマクロフローの組み合わせを選択して解マクロフローとして解マクロフロー記憶手段に格納する、または、該候補マクロフロー情報記憶手段の候補マクロフローリストを拡張するマクロフロー選択ステップと、
前記解マクロフロー記憶手段の前記解マクロフローを前記多次元フローデータベースから削除し、更新後の多次元フローデータベースの情報でフローサイズ、時系列変動係数を再計算し、前記候補マクロフロー記憶手段を更新する更新ステップと、
を行う請求項５記載のフロー集約方法。
【請求項７】
前記マクロフロー選択ステップにおいて、
候補マクロフロー拡張による解空間の探索と解マクロフロー選択による解選択をどの割合で実施するかを決める制御パラメータC、所定の閾値を表す制御パラメータA、制御パラメータBを用いて、
前記乱数Xが前記制御パラメータAより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の安定条件を満たすM個のマクロフローをランダムに選択し、前記単一安定マクロフローとして前記解マクロフロー記憶手段に格納するステップと、
前記乱数Xが前記制御パラメータA以上、かつ、前記制御パラメータBより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の非安定条件を満たすM個のマクロフローからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納するステップと、
前記乱数Xが前記制御パラメータB以上、かつ、前記制御パラメータCより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の複合安定条件を満たすM個のマクロフローの組み合わせからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納するステップと、
前記乱数Xが前記制御パラメータC以上である場合は、フローサイズが上位L個のN（N≦４）次元マクロフローからランダムに１つ選択し、選択したN次元マクロフローのヘッダ情報の未選択次元の各値から、選択することで最もフローサイズが大きくなる値を１つ選択し、マクロフローヘッダに追加してN+1次元のマクロフローを生成し、前記候補マクロフロー記憶手段に追加するステップと、
を行う請求項６記載のフロー集約方法。
【請求項８】
コンピュータを、
請求項１乃至４のいずれか１項に記載のフロー集約装置の各手段として機能させるためのフロー集約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フロー集約装置及び方法及びプログラムに係り、特に、ネットワークにおけるトラヒックを効率的に収容するためのフローを集約するためのフロー集約装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
限られたネットワークリソースを用いてトラヒックを効率的に収容する技術として、到着トラヒックを予測し、予測結果に基づいてトラヒックの経路を制御するトラヒックエンジニアリング技術が研究されている。トラヒックエンジニアリングの例として、ネットワーク内の最大リンク利用率を最小化することを目的とした経路制御などが考えられる。この場合、トラヒックの予測値に基づいて、ネットワーク内の空いているリンクを通過させるようにトラヒックの経路を制御する（例えば、非特許文献１参照）。
【０００３】
インターネット上のサービスの多様化に伴い、ネットワーク上を流れるトラヒックの時系列予測を正確に実施することが困難となってきている。これは、トラヒック内に様々なサービス、コンテンツ、利用者のトラヒックが混在しているためである。誤ったトラヒック予測値に基づいてトラヒックの経路を制御した場合、特定リンクにトラヒックが集中し、リンクが輻輳する可能性がある（非特許文献２参照）。
【０００４】
新しいトラヒック制御技術として、近年、OpenFlow に代表されるSDN(Software Defined Network)技術への注目が高まっている。これらの技術の登場により、従来のネットワーキング技術では困難であったマイクロフロー単位の経路制御が技術的に可能となった。また、NetFlow 等のフロー計測技術の普及も進んでおり、マイクロフロー単位の詳細なトラヒック情報(フローデータ) を把握することが容易となっている。
【０００５】
Openflow では、Openflowスイッチ上のフローエントリでフローを制御する。フローエントリはフロー識別フィールドとアクションフィールドから成る。フロー識別フィールドは発着IPアドレス、発着ポート番号、プロトコル番号等のフローを特定する情報から構成される。アクションフィールドには特定ポートへの出力や、フローのドロップ等のフローの処理方法が記載されている。
【０００６】
Openflow によって任意の粒度でのフロー制御が可能となる。例えば、宛先アドレスだけをフロー識別フィールドに使用することで、宛先IPアドレスのみに基づく粗い粒度の制御をすることが可能であり、一方で、5-tuple (送信元アドレス，宛先アドレス，送信元ポート番号，宛先ポート番号，プロトコル番号) 全てをフロー識別フィールドに使用することで、5-tupleフロー(マイクロフロー)に基づく細かい粒度の制御が可能である。フローエントリ毎に上記の粒度を変えることも可能である。
【０００７】
また、トラヒックをマクロフローと呼ばれる単位に分割する方法がある。マクロフローはフローヘッダ情報（発着IPアドレス，発着ポート番号，プロトコル番号等）を任意に組み合わせて識別するフローであり、Openflow 等のフロー制御技術での制御が可能である（例えば、非特許文献３参照）。
【０００８】
トラヒックを制御粒度に分割する方法として、例えば、一律に宛先アドレスだけで分割する方法や、一律に宛先アドレスと送信元アドレスの組合せで分割する方法が考えられる（例えば、非特許文献３，４参照）。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】A. Lakhina, M. Crovella, and C. Diot. Diagnosing Network-Wide Traffic Anomalies. In ACM SIGCOMM,Portland, August 2004.
【非特許文献２】工藤宏幸, 嶋村昌義, 池永全志, 鶴正人. "OpenFlow ネットワークにおける経路制御粒度が通信性能に与える影響 ", 電子情報通信学会技術研究報告. NS, ネットワークシステム, 111(8), 7-12, 2011.
【非特許文献３】Broido, Andre, Young Hyun, and Ruomei Gao. "Their share: diversity and disparity in IP traffic". Passive and Active Network Measurement. Springer Berlin Heidelberg, 2004. 113-125.
【非特許文献４】Kind, Andreas, Marc Ph Stoecklin, and Xenofontas Dimitropoulos. "Histogram-based traffic anomaly detection". Network and Service Management, IEEE Transactions on 6.2 (2009): 110-121.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記の非特許文献２の技術には、マクロフローの粒度（フローサイズ）によって経路制御の性能（最大リンク利用率）が大きく変わることが示されている。細粒度のマクロフローであるほど、緻密な経路制御が可能となり、より高い経路制御性能が得られる (マクロフローサイズに関する制約)。しかし、マクロフローを細粒度とした場合、制御対象フロー数が大きくなる。制御対象フロー数が大きいことで、経路計算にかかる計算量が大きくなり、ネットワーク機器への設定数が多くなる(マクロフロー数に関する制約)。例えば、Openflow スイッチでは任意のフロー識別フィールドを利用できる代わりに、設定可能経路数(フローエントリ数)の上限がIPルータと比べて小さく抑えられている。マクロフロー数はフローエントリ数以内に抑えることが求められる。
【００１１】
このため、適切なマクロフローサイズ、マクロフロー数条件を満たすマクロフローへと分割する必要がある。
【００１２】
また、非特許文献１の技術では、発ノード、宛先ノード別トラヒック（以下、ODフローと記す。OD(Origin-Destination)）集合を主成分分析を用いて定常成分、スパイク成分、ノイズ成分に分解することに成功している。しかし、分解されたトラヒックは個々のODフローの混合和となっており、分解されたトラヒック自体をそのまま制御することはできない。
【００１３】
また、非特許文献３，４の技術は、それぞれの宛先アドレスへのトラヒックのサイズ分布は一様ではなく、人気のある一部の宛先に大きく偏っていることが多い(非特許文献３)。この傾向はポート番号などでも同様である（非特許文献４）。このため、一律に分割方法を決めてしまうことで、分割結果のトラヒックサイズも大きく偏ってしまう。結果として、極端に大きい粒度のトラヒックが生成され、経路制御性能が低下することが懸念される。また、アドレスやポート番号に紐付くコンテンツやサービスやアプリケーションに応じて、安定性が大きく異なるため、分割結果のトラヒック安定性が満たされない場合がある。
【００１４】
上記のように、従来手法（非特許文献１の手法）では、Openflow等のフロー制御技術で制御可能な可制御性を保ったままトラヒックを分解することが難しい。例えば、非特許文献１では、ネットワークのトラヒック全体をODフローの混合和とし、例えば、ODフロー１を0.3 、ODフロー2 を0.2 だけ混ぜた混合フローを集約フローA と表現し、ODフロー１を0.5 、ODフロー2 を0.1 だけ混ぜた混合フローを集約フローB と表現すると、この場合、集約フローA，B には2種類のODを持つフローが混在しているため、集約フローA，B を制御することは困難である。これは、同じ送信元と宛先を持つフローが、それぞれ集約フローＡ、集約フローＢに存在するためである。
【００１５】
さらに、細粒度マクロフローには、制御対象フロー数が多いという課題があり、粗粒度マクロフローには経路制御性能が低いという課題が存在する。
【００１６】
本発明は、上記の点に鑑みなされたもので、マクロフロー安定性とマクロフロー数、マクロフローサイズのそれぞれの条件を満たすようなマクロフローを生成することが可能なフロー集約装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
一態様によれば、ネットワークのトラヒックを収容する際に、トラヒックをマクロフロー単位に分割して制御するフロー集約装置であって、
前記ネットワークのマクロフローの時系列トラヒック情報が与えられると、トラヒック情報をフロー制御技術で制御可能な粒度に分解し、マクロフロー安定性、マクロフロー数、マクロフローサイズのそれぞれの条件を満たすマクロフローを生成し、解マクロフローとして解マクロフロー記憶手段に格納するマクロフロー算出手段を有するフロー集約装置が提供される。
【発明の効果】
【００１８】
一態様によれば、予測可能性を考慮しながら、制御粒度を決めることにより、予測誤りを減らすことができる。また、所定の条件により制御対象のトラヒックサイズの上限を決めて集約できるため、トラヒックサイズが大きいことによる経路制御性能の劣化を防ぐことができる。さらに、制御対象のフロー数の上限を決めて集約できるため、経路計算に掛かるコスト、ネットワーク機器への設定コスト（フローエントリ数など）を抑えることができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施の形態におけるシステム構成例。
【図２】本発明の一実施の形態におけるフロー集約装置の構成例。
【図３】本発明の一実施の形態におけるフローデータベースの例。
【図４】本発明の一実施の形態におけるマクロフロー算出部の処理のフローチャート。
【発明を実施するための形態】
【００２０】
以下、図面と共に本発明の実施の形態を説明する。
【００２１】
本発明は、ネットワークを流れるトラヒックを分解して、
・マクロフロー安定性
・マクロフロー数
・マクロフローサイズ
のそれぞれの条件を満たし、Openflow等のフロー制御技術による制御が可能なマクロフローを生成する。
【００２２】
そのための処理として、
・ネットワークを流れるトラヒックの分解
・上記の条件を満たすようなマクロフローを生成
を行う。
【００２３】
本発明では、非特許文献１のようにマクロフロー粒度を一律に細粒度または粗粒度と決定することはせず、Openflowで使われる制御単位であるフローエントリ毎に任意のtuple組み合わせを設定する。ここで、フローエントリとは、主に、マッチフィールドとアクションフィールドとを有する。マッチフィールドは送受信アドレスや送受信ポート，プロトコル番号，VLAN IDなどのヘッダ情報を任意に組み合わせて記述されている。なお、全てのヘッダ情報を記載する必要はなく、ワイルドカードも使用可能である。例えば、宛先IP＝10.0.0.1、送信元ポート番号=80 といったマッチフィールドを作ると、宛先IPと送信元ポート番号だけを見てフローのマッチングを実施する。マッチフィールドにマッチしたフローはアクションフィールドに書かれたアクションを実施する。アクションフィールドには、どのポートから出力させるか、ドロップさせるか、等のアクションが記述される。フローエントリはマッチフィールドとアクションフィールドが記載された制御単位である。本発明は、このマッチフィールドをどう決めるかという点が重要であり、あまり細かい粒度に決めてしまうと、膨大な数のフローエントリ数が必要となり、粗すぎるとうまく経路制御できない場合がある。例えば、宛先IPの中でもトラヒック量の多いものとそうでないものがあり、一様では大きく偏っていることが多いため、一律にフローエントリの粒度を設定した場合には、フローエントリによって扱うフローのサイズが極端に大きかったり小さかったりする。
【００２４】
また、可能な全てのフロー構成情報の組み合わせは膨大となり、その全ての組み合わせについて集約条件を満たすかどうかを実時間で調べることは計算時間や必要メモリ空間の点で困難である。本発明では、宛先アドレスや送信ポート番号等のトラヒック粒度で各トラヒックを分類及び分割し、一定の条件でトラヒックを合算し、Openflow等のフロー制御技術で制御可能なマクロフローを生成する。
【００２５】
以下に詳細に説明する。
【００２６】
図１は、本発明の一実施の形態におけるシステム構成例である。同図に示すシステムでは、フロー制御技術としてOpenflowを例として説明する。
【００２７】
ノード１はOpenflowスイッチ２に接続され、Openflowスイッチ２は、トラヒック情報をトラヒック情報モニタ３に送信する。トラヒック情報モニタ３は、収集したトラヒック情報を、フロー集約装置１０に送出する。フロー集約装置１０で生成されたマクロフロー情報は経路計算エンジン４に送られ、経路計算エンジン４で経路計算がなされたフローエントリ情報がOpenflowコントローラ５に送られる。Openflowコントローラ５は、フローエントリ設定命令を各Openflowスイッチ２に送出する。
【００２８】
図２は、本発明の一実施の形態におけるフロー集約装置の構成例を示す。
【００２９】
同図に示すフロー集約装置１０は、マクロフロー算出部１１、候補マクロフロー記憶部１２、フローデータベース１３、解マクロフロー記憶部１４を有する。
【００３０】
なお、上記の構成以外に、図示しないが、フロー集約装置１０は、所定の閾値や制御パラメータや、条件（安定条件、非安定条件、安定条件（複合）、解マクロフロー追加条件、集約アルゴリズム終了条件等）を格納するメモリ等の記憶媒体を有するものとする。
【００３１】
候補マクロフロー記憶部１２は、候補マクロフロー情報を格納する。
【００３２】
フローデータベース１３は、図３（ｃ）に示すように、送信元IPアドレス、宛先アドレス、送信元ポート番号、宛先ポート番号、プロトコル番号、時系列トラヒック情報等のマイクロフロー情報を格納する多次元データベースであり、図３（ｂ）に示すように、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号、プロトコル番号等のマクロフロークエリに基づいて、対応するマイクロフロー情報を返却する。
【００３３】
解マクロフロー記憶部１４は、マクロフロー算出部１１で算出された解マクロフローを格納する。
【００３４】
マイクロフロー算出部１１は、図４に示す処理を行なう。
【００３５】
図４は、本発明の一実施の形態におけるマクロフロー算出部の処理のフローチャートである。
【００３６】
ステップ１０１）初期候補マクロフロー生成：
マクロフロー算出部１１は、フローデータベース１３にアクセスし、フローサイズが閾値Y以上となる１次元フロー情報を全て取得し、これを初期候補マクロフローとして候補マクロフロー情報記憶部１２に書き込む。ここで、閾値Yは予め決定され、メモリ（図示せず）等の記憶手段に格納されているものとする。
【００３７】
ステップ１０２）乱数X（０≦X≦１）を生成し、Xを評価：
マクロフロー算出部１１は、乱数X（0≦X≦1、実数）を生成し、制御パラメータA、B,Cと大小関係を評価する。制御パラメータCは候補マクロフロー拡張による解空間の探索と解マクロフロー選択による解選択をどの割合で実施するかを決める。Cが大きい場合には、候補マクロフローリスト拡張（ステップ１０６）が実施される割合が高くなり、より広い解空間から解を選ぶことができるため、解の精度が向上する。
【００３８】
一方で、解選択が実施される割合が低くなることで、最終的な解マクロフローを算出するまでの時間が長くなる。制御パラメータA,Bは３パターンの解選択処理をどの割合で実施するかを決定する。具体的には、閾値がA,Bの２つあれば、Xの値が、「A未満（X<A）」、「A以上B未満(A≦X<B)」、「B以上(X≧B)」のように３つのパターンに分けられる。
【００３９】
Xを評価した結果、x<Aであればステップ１０３に、A≦X＜Bであればステップ１０４に、B≦X＜Cであればステップ１０５に、C≦Xであればステップ１０６に移行する。
【００４０】
ステップ１０３）単一安定マクロフロー選択：
x<Aであれば、マクロフロー算出部１１は、候補マクロフロー記憶部１２にアクセスし、安定条件を満たすマクロフローを最大M個選択する。M個のマクロフローからランダムに１つ選択し、解マクロフロー記憶部１４の解マクロフローに「安定フロー」として加える。ここでは、ランダムに解を選択することで解が特定の局所解に収束することを防いでいる。
【００４１】
上記の安定条件として、トラヒック安定性条件
C.V.(f)< C.V._stable 
（但し、fはマクロフロー、C.V.(f)は該fの時系列トラヒック量の変動係数、C.V._stableは解マクロフローに安定フローとして追加できる最大の変動係数）
及び、トラヒックサイズ条件
sizemin<size(f)<sizemax
（但し、size(f)は時系列トラヒック量の平均値、sizeminは解マクロフローに追加できる最小のフローサイズ、sizemaxは解マクロフローに追加できる最大のフローサイズ）を用いる。
【００４２】
上記のC.V.は以下の式により求められる。
【００４３】
【数１】
2015156529.tif 000003
（但し、xiは時刻iのトラヒック量）
観測期間中に変動係数が小さくトラヒックの時系列変動が安定しているフローは将来に亘っても変動係数が小さくトラヒックの時系列が安定している可能性が高いと考えられる。
【００４４】
上記の処理の後、ステップ１０７の処理に移行する。
【００４５】
ステップ１０４）単一非安定マクロフロー選択：
A≦X＜Bであれば、候補マクロフロー記憶部１２にアクセスし、非安定条件を満たすマクロフローを最大M個選択する。M個のマクロフローからランダムに１つ選択し、解マクロフロー記憶部１４の解マクロフローに「非安定フロー」として加える。ここでは、ランダムに解を選択することで、解が特定の局所解に収束することを防いでいる。
【００４６】
上記の非安定条件として、
トラヒック非安定条件C.V.(f)<C.V._unstable
（但し、fはマクロフロー、C.V.(f)は該fの時系列トラヒック量の変動係数）
及び、トラヒックサイズ条件
sizemin<size(f)<sizemax
（但し、size(f)は時系列トラヒック量の平均値）を用いる。
【００４７】
ステップ１０５）ペア安定マクロフロー選択：
B≦X＜Cであれば、候補マクロフロー記憶部１２にアクセスし、安定条件（複合）を満たすマクロフロー組み合わせを最大M個選択する。M個のマクロフロー組み合わせからランダムに一つ選択し、解マクロフロー記憶部１４の解マクロフローに「安定フロー」として加える。ここでは、ランダムに解を選択することで解が特定の局所解に収束することを防いでいる。
【００４８】
安定条件（複合）として、トラヒック安定条件
C.V.(f+g)< C.V._stable
（但し、f+gは時系列データを合算したマクロフロー、C.V.(f+g)は該f+gの時系列トラヒック量の変動係数）
及び、トラヒックサイズ条件
sizemin<size(f+g)<sizemax
（但し、size(f+g)はf+gの時系列トラヒック量の平均値）を用いる。
という条件を用いる。
【００４９】
ステップ１０６）候補マクロフローリスト拡張
C≦Xであれば、候補マクロフロー記憶部１２の候補マクロフローリストを拡張することで、解空間を拡大する。フローサイズが上位L個のN次元マクロフローからランダムに一つ選択する（但し、N≦４）。選択したN次元のマクロフローヘッダ情報の未選択次元の各値から選択することで最もフローサイズが大きくなる値を１つ選択し、マクロフローヘッダに追加することで新たなN+1次元マクロフローを生成し、候補マクロフロー記憶部１２の候補マクロフローリストに追加する。
【００５０】
例えば、２次元マクロフロー（sipA,*,*,dpB,*）を(sipAk*,*,dpB,prA)を生成する。未選択次元は、dstIP，srcPort，protoの３次元とする。未選択次元から１つ値を選んで、３次元フローを生成する。このうち、proto=prAを選択して生成した３次元フローが最もフローサイズが大きくなった場合には、（sipA,*,*,dpB,prA）を候補として新たに候補マクロフロー記憶部１２に追加する。
【００５１】
ステップ１０７）フローデータベース更新及び候補マクロフロー情報更新：
上記のステップ１０３，１０４，１０５で選択した解マクロフローに含まれるマイクロフローをフローデータベース１３から削除する。更新後のフローデータベース１３の情報で候補マクロフローのフローサイズ、時系列変動係数を再計算し、候補マクロフロー記憶部１２に書き込む。
【００５２】
ステップ１０８）マクロフロー生成継続条件判定：
マクロフロー生成継続条件（残余フローサイズ、ループ回数）を評価し、継続条件を満たす場合は、ステップ１０２に移行し、再度マクロフロー構成の処理を実施する。継続条件を満たさない場合は、ステップ１０９に移行する。
【００５３】
例えば、残余フローサイズをsize(residual_flow)とした場合、size(residual_flow)＜residual_thresholdの場合には残余フローが殆ど残っていないと判定し、ステップ１０９に進み、それ以外の場合はステップ１０２（マクロ生成継続）に進む。ここで、residual_thresholdは残余フローサイズの閾値である。
【００５４】
また、例えば、ループ回数をnumloopとした場合、numloop > repeat_thresholdの場合にはループが十分な回数回ったと判定し、ステップ１０９（マクロフロー生成終了）へと進み、それ以外の場合はステップ１０２（マクロフロー生成継続）に進む。ここで、repeat_thresholdはアルゴリズム繰り返し回数の閾値である。
【００５５】
ステップ１０９）マクロ生成終了通知
マクロフロー生成が終了したことを解マクロフロー記憶部１４に通知する。
【００５６】
なお、図２に示すフロー集約装置１０の処理をプログラムとして構築し、フロー集約装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５８】
１  ノード
２  Openflowスイッチ
３  トラヒック情報モニタ
４  経路計算エンジン
５  Openflowコントローラ
１０  フロー集約装置
１１  マクロフロー算出部
１２  候補マクロフロー記憶部
１３  フローデータベース
１４  解マクロフロー記憶部
【図１】
2015156529.tif 000004
【図２】
2015156529.tif 000005
【図３】
2015156529.tif 000006
【図４】
2015156529.tif 000007
【手続補正書】
【提出日】平成27年3月17日(2015.3.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワークのトラヒックを収容する際に、トラヒックをマクロフロー単位に分割して制御するフロー集約装置であって、
前記ネットワークのマクロフローの時系列トラヒック情報が与えられると、任意のフローヘッダ情報に基づいてトラヒック情報を分解し、前記分解した時系列トラヒックのフローサイズが閾値以上となるフロー情報の中から、所定の安定条件を満たす単一安定マクロフロー、所定の非安定条件を満たす単一非安定マクロフローまたは所定の複合安定条件を満たすマクロフローの組み合わせを生成し、トラヒックがフロー制御技術で制御される単位である解マクロフローとして解マクロフロー記憶手段に格納するマクロフロー算出手段を
有することを特徴とするフロー集約装置。
【請求項２】
前記マクロフロー算出手段は、
任意のフローヘッダ情報に基づいて、多次元フローデータベースにアクセスし、前記マクロフローの時系列トラヒック情報を取得する手段と、
前記時系列トラヒック情報のフローサイズが所定の閾値以上となるフロー情報を候補マクロフロー情報記憶手段に格納する手段と、
乱数X(0≦X≦1)を生成し、所定の制御パラメータとの大小関係により、前記候補マクロフロー情報記憶手段から、所定の安定条件を満たす単一安定マクロフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の非安定条件を満たす単一非安定マクロフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の複合安定条件を満たすマクロフローの組み合わせを選択して解マクロフローとして解マクロフロー記憶手段に格納する、または、該候補マクロフロー情報記憶手段の候補マクロフローリストを拡張するマクロフロー選択手段と、
前記解マクロフロー記憶手段の前記解マクロフローを前記多次元フローデータベースから削除し、更新後の多次元フローデータベースの情報でフローサイズ、時系列変動係数を再計算し、前記候補マクロフロー記憶手段を更新する更新手段と、
を含む請求項１記載のフロー集約装置。
【請求項３】
前記マクロフロー選択手段は、
候補マクロフロー拡張による解空間の探索と解マクロフロー選択による解選択をどの割合で実施するかを決める制御パラメータC、所定の閾値を表す制御パラメータA、制御パラメータBを用いて、
前記乱数Xが前記制御パラメータAより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の安定条件を満たすM個のマクロフローをランダムに選択し、前記単一安定マクロフローとして前記解マクロフロー記憶手段に格納する手段と、
前記乱数Xが前記制御パラメータA以上、かつ、前記制御パラメータBより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の非安定条件を満たすM個のマクロフローからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納する手段と、
前記乱数Xが前記制御パラメータB以上、かつ、前記制御パラメータCより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の複合安定条件を満たすM個のマクロフローの組み合わせからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納する手段と、
前記乱数Xが前記制御パラメータC以上である場合は、フローサイズが上位L個のN（N≦４）次元マクロフローからランダムに１つ選択し、選択したN次元マクロフローのヘッダ情報の未選択次元の各値から、選択することで最もフローサイズが大きくなる値を１つ選択し、マクロフローヘッダに追加してN+1次元のマクロフローを生成し、前記候補マクロフロー記憶手段に追加する手段と、
を含む請求項２記載のフロー集約装置。
【請求項４】
前記所定の安定条件を、
トラヒック安定条件CV(f)<  CV_stable（但し、fはマクロフロー、CV(f)は該fの時系列トラヒック量の変動係数、stablecvは解マクロフローに安定フローとして追加できる最大の変動係数）及び、トラヒックサイズ条件sizemin<size(f)<sizemax（但し、size(f)は時系列トラヒック量の平均値、sizeminは解マクロフローに追加できる最小のフローサイズ、sizemaxは解マクロフローに追加できる最大のフローサイズ）とし、
前記所定の非安定条件を、
トラヒック非安定条件CV(f)<  CV_unstable（但し、fはマクロフロー、CV(f)は該fの時系列トラヒック量の変動係数）及び、トラヒックサイズ条件sizemin<size(f)<sizemax（但し、size(f)は時系列トラヒック量の平均値）とし、
前記所定の複合安定条件を、
トラヒック安定条件CV(f+g)<  CV_stable（但し、f+gは時系列データを合算したマクロフロー、CV(f+g)は該f+gの時系列トラヒック量の変動係数）及び、トラヒックサイズ条件sizemin<size(f+g)<sizemax（但し、size(f+g)はf+gの時系列トラヒック量の平均値）とする
請求項２または３に記載のフロー集約装置。
【請求項５】
ネットワークのトラヒックを収容する際に、トラヒックをマクロフロー単位に分割して制御するフロー集約方法であって、
フロー集約装置が、
前記ネットワークのマクロフローの時系列トラヒック情報が与えられると、任意のフローヘッダ情報に基づいてトラヒック情報を分解し、前記分解した時系列トラヒックのフローサイズが閾値以上となるフロー情報の中から、所定の安定条件を満たす単一安定マクロフロー、所定の非安定条件を満たす単一非安定マクロフローまたは所定の複合安定条件を満たすマクロフローの組み合わせを生成し、トラヒックがフロー制御技術で制御される単位である解マクロフローとして解マクロフロー記憶手段に格納するマクロフロー算出ステップを
行うことを特徴とするフロー集約方法。
【請求項６】
前記マクロフロー算出ステップにおいて、
任意のフローヘッダ情報に基づいて、多次元フローデータベースにアクセスし、前記マクロフローの時系列トラヒック情報を取得するステップと、
前記時系列トラヒック情報のフローサイズが所定の閾値以上となるフロー情報を候補マクロフロー情報記憶手段に格納するステップと、
乱数X(0≦X≦1)を生成し、所定の制御パラメータとの大小関係により、前記候補マクロフロー情報記憶手段から、所定の安定条件を満たす単一安定マクロフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の非安定条件を満たす単一非安定マクロフローを選択して解マクロフローとして解マクロフロー記憶手段に格納する、所定の複合安定条件を満たすマクロフローの組み合わせを選択して解マクロフローとして解マクロフロー記憶手段に格納する、または、該候補マクロフロー情報記憶手段の候補マクロフローリストを拡張するマクロフロー選択ステップと、
前記解マクロフロー記憶手段の前記解マクロフローを前記多次元フローデータベースから削除し、更新後の多次元フローデータベースの情報でフローサイズ、時系列変動係数を再計算し、前記候補マクロフロー記憶手段を更新する更新ステップと、
を行う請求項５記載のフロー集約方法。
【請求項７】
前記マクロフロー選択ステップにおいて、
候補マクロフロー拡張による解空間の探索と解マクロフロー選択による解選択をどの割合で実施するかを決める制御パラメータC、所定の閾値を表す制御パラメータA、制御パラメータBを用いて、
前記乱数Xが前記制御パラメータAより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の安定条件を満たすM個のマクロフローをランダムに選択し、前記単一安定マクロフローとして前記解マクロフロー記憶手段に格納するステップと、
前記乱数Xが前記制御パラメータA以上、かつ、前記制御パラメータBより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の非安定条件を満たすM個のマクロフローからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納するステップと、
前記乱数Xが前記制御パラメータB以上、かつ、前記制御パラメータCより小さければ、前記候補マクロフロー記憶手段にアクセスして、前記所定の複合安定条件を満たすM個のマクロフローの組み合わせからランダムに１つ選択し、前記単一非安定マクロフローとして前記解マクロフロー記憶手段に格納するステップと、
前記乱数Xが前記制御パラメータC以上である場合は、フローサイズが上位L個のN（N≦４）次元マクロフローからランダムに１つ選択し、選択したN次元マクロフローのヘッダ情報の未選択次元の各値から、選択することで最もフローサイズが大きくなる値を１つ選択し、マクロフローヘッダに追加してN+1次元のマクロフローを生成し、前記候補マクロフロー記憶手段に追加するステップと、
を行う請求項６記載のフロー集約方法。
【請求項８】
コンピュータを、
請求項１乃至４のいずれか１項に記載のフロー集約装置の各手段として機能させるためのフロー集約プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
一態様によれば、ネットワークのトラヒックを収容する際に、トラヒックをマクロフロー単位に分割して制御するフロー集約装置であって、
前記ネットワークのマクロフローの時系列トラヒック情報が与えられると、任意のフローヘッダ情報に基づいてトラヒック情報を分解し、前記分解した時系列トラヒックのフローサイズが閾値以上となるフロー情報の中から、所定の安定条件を満たす単一安定マクロフロー、所定の非安定条件を満たす単一非安定マクロフローまたは所定の複合安定条件を満たすマクロフローの組み合わせを生成し、トラヒックがフロー制御技術で制御される単位である解マクロフローとして解マクロフロー記憶手段に格納するマクロフロー算出手段を有するフロー集約装置が提供される。