(57)【特許請求の範囲】
【請求項１】
同一発着(OD)ノードペア間の任意のトラヒックフローの集合であるマクロフロー(MF)を単位にトラヒックエンジニアリング(TE)による経路設定が可能なネットワークにおいて、ODネットワークアドレスのフローからMF単位に集約するフロー集約装置であって、
生成MF数Mと、時間を一定周期Tのタイムスロット(TS)に分割し、評価期間1≦t≦Lの各TStにおける各フローfの発生トラヒック量Rf,tを含むパラメタを入力するパラメタ入力手段と、
前記各フローfの発生トラヒック量Rf,tを用いて、各ODノードペア間に存在するF本のフローをM本のMFに分類するMF生成手段とを有し、
前記MF生成手段は、
前記パラメタの前記生成MF数Mが与えられると、MFのトラヒック変動量Vx、もしくはMF最大トラヒック量Qのいずれか一つを最適化するため、FmをMF  mに分類されたフローの集合と定義するとき、
1)  1≦m≦Mの各mのFmを空集合φに初期化する第１の過程；
2)前記Fのフローから特性値Yfの降順にフローfを選択する第２の過程；
3)選択したフローfを前記Mの各MFmに分類したときのMF集合の目的関数として用いる特性値Pを、既にMFに分類されたフローのみを考慮して算出する第３の過程；
4)前記特性値Pが最小となるMFm*にフローfを分類（Fm=Fm+{f}）する第４の過程；
を行い、前記Fの全フローがMFのいずれかに分類されるまで前記第１の過程から前記第４の過程の処理を繰り返すことによりM個のMFを生成する
フロー集約装置。
【請求項２】
前記MF生成手段は、
最適化の目的関数Pと、フローfのMFへの割当順番を決めるfの特性値Yfとして、前記MFトラヒック変動量Vxを低減することを目的に、Xm,tが各MFmの各TS  tにおける既分類フローの発生トラヒック量の総和で、
【数３２】
0005888684.tif 000034
が、Xm,tの評価期間に渡る平均値
【数３３】
0005888684.tif 000035
であるときに
【数３４】
0005888684.tif 000036
で算出される各MFの評価期間におけるトラヒック量の分散の総和Φを前記Pに、前記Yfを各フローfのトラヒック量の変動係数に
【数３５】
0005888684.tif 000037
として設定するMFトラヒック量分散の総和の最小化手段、
最適化の目的関数Pと、フローfのMFへの割当順番を決めるfの特性値Yfとして、前記MF最大トラヒック量Qを低減することを目的に、
【数３６】
0005888684.tif 000038
で算出される各MFの評価期間における最大トラヒック量の全MFにわたる最大値Ψを前記Pに設定し、前記Yfを各フローfの最大トラヒック量に
【数３７】
0005888684.tif 000039
として設定するMF最大ピークトラヒック量最小化手段、
前記MF最大トラヒック量Qを低減することを目的に、
【数３８】
0005888684.tif 000040
で算出される各MFの評価期間における総トラヒック量の全MFにわたる最大値Ωを前記Pに、前記Yfを各フローfの総トラヒック量に
【数３９】
0005888684.tif 000041
として設定するMF最大総トラヒック量最小化手段、
前記最適化の目的関数Pと、フローfのMFへの割当順番を決めるfの特性値Yfとして、MF最大トラヒック量Qを低減することを目的に、Fを全フローの集合、
【数４０】
0005888684.tif 000042
をTStにおける総トラヒック量
【数４１】
0005888684.tif 000043
とするとき、
【数４２】
0005888684.tif 000044
で算出される各MFの各TSにおけるトラヒック量比率の最大値
【数４３】
0005888684.tif 000045
を前記Pに設定し、Yfを各フローfのピークトラヒック量比率
【数４４】
0005888684.tif 000046
に設定するMF最大ピーク比率最小化手段、
前記第３の過程、及び前記第４の過程における各フローfを各MFに収容する際に、前記ピークトラヒック量比率
【数４５】
0005888684.tif 000047
が、予め与えた制約条件値を超えないMFのみを候補とし、前記Yfを各フローfのトラヒックの変動係数に設定するMFトラヒック量分差の総和の最小化及びピーク比率制約手段、
のいずれかを含む
請求項１記載のフロー集約装置。
【請求項３】
同一発着(OD)ノードペア間の任意のトラヒックフローの集合であるマクロフロー(MF)を単位にトラヒックエンジニアリング(TE)による経路設定が可能なネットワークにおいて、ODネットワークアドレスのフローからMF単位に集約するフロー集約装置であって、
生成MF数Mと、時間を一定周期Tのタイムスロット(TS)に分割し、評価期間1≦t≦Lの各TStにおける各フローfの発生トラヒック量Rf,tと、クラスタ数Kと、重みパラメタβとを含むパラメタを入力するパラメタ入力手段と、
前記各フローfの発生トラヒック量Rf,tを用いて、各ODノードペア間に存在するF本のフローをM本のMFに分類するMF生成手段とを有し、
前記MF生成手段は、
前記各フローfを各TStにおける発生トラヒック量Rf,tを要素とするL次元のベクトルRfを用いてK個のクラスタｃにクラスタリングするクラスタ分類手段と、
各クラスタcから各MFの各TSにおけるトラヒック量の最大値を最小化してトラヒック比率を求める抽出トラヒック比率設計手段と、
前記トラヒック比率に基づき、フローをMFに集約するMF集約手段と、
を含むフロー集約装置。
【請求項４】
前記クラスタ分類手段は、
前記各フローfを各TStにおける発生トラヒック量Rf,tを要素とするL次元のベクトルRfを用いて、球面k-means法により評価期間におけるトラヒックの時系列パタンが似たフローを同一のクラスタに分類する手段を含み、
前記抽出トラヒック比率設計手段は、
K個の各クラスタcに分類されたフローの集合をGcとし、該各クラスタcから一定の比率αm,c(0≦α≦1)のトラヒックをM本の各MF  mに分類するとき、該各クラスタcの各TStにおける総トラヒック量を
【数４６】
0005888684.tif 000048
とするとき、各MFの各TSにおけるトラヒック量の最大値を最小化する線形計画問題
【数４７】
0005888684.tif 000049
を解くことで、分類比率αm,cを最適設計する手段を含み、
前記MF集約手段は、
前記フローfをMF  mに割当てる場合に1を、そうでない場合に0をとる二値変数をxf,mとし、各TStにおいて、該xf,mから定まる各MF  mのクラスタcからの抽出トラヒック量
【数４８】
0005888684.tif 000050
と、前記抽出トラヒック比率設計手段で導出した前記分類比率αm,cから算出されるトラヒック量αm,cZc,tとの差分の全期間にわたる総和sの全MFにわたる最大値Sと、前記xf,mから算出されるQとの重み付け線形和を最小化するよう整数計画問題
【数４９】
0005888684.tif 000051
を解くことでxf,mを設計する手段を含む
請求項３記載のフロー集約装置。
【請求項５】
同一発着(OD)ノードペア間の任意のトラヒックフローの集合であるマクロフロー(MF)を単位にトラヒックエンジニアリング(TE)による経路設定が可能なネットワークにおいて、ODネットワークアドレスのフローからMF単位に集約する装置におけるフロー集約方法であって、
生成MF数、時間を一定周期Tのタイムスロット(TS)に分割し、評価期間1≦t≦Lの各TStにおける各フローfの発生トラヒック量Rf,tを含むパラメタを入力するパラメタ入力ステップと、
前記各フローfの発生トラヒック量Rf,tを用いて、各ODノードペア間に存在するF本のフローをM本のMFに分類するMF生成ステップとをコンピュータが実行し、
前記MF生成ステップは、
前記パラメタの前記生成MF数Mが与えられると、MFのトラヒック変動量Vx、もしくはMF最大トラヒック量Qのいずれか一つを最適化するため、FmをMF  mに分類されたフローの集合と定義するとき、
1)  1≦m≦Mの各mのFmを空集合φに初期化する第１の過程；
2)前記Fのフローから特性値Yfの降順にフローfを選択する第２の過程；
3)選択したフローfを前記Mの各MFmに分類したときのMF集合の目的関数として用いる特性値Pを、既にMFに分類されたフローのみを考慮して算出する第３の過程；
4)前記特性値Pが最小となるMFm*にフローfを分類（Fm=Fm+{f}）する第４の過程；
を含み、前記Fの全フローがMFのいずれかに分類されるまで前記第１の過程から前記第４の過程の処理を繰り返すことによりM個のMFを生成する
ことを特徴とするフロー集約方法。
【請求項６】
同一発着(OD)ノードペア間の任意のトラヒックフローの集合であるマクロフロー(MF)を単位にトラヒックエンジニアリング(TE)による経路設定が可能なネットワークにおいて、ODネットワークアドレスのフローからMF単位に集約する装置におけるフロー集約方法であって、
生成MF数、時間を一定周期Tのタイムスロット(TS)に分割し、評価期間1≦t≦Lの各TStにおける各フローfの発生トラヒック量Rf,tを含むパラメタを入力するパラメタ入力ステップと、
前記各フローfの発生トラヒック量Rf,tを用いて、各ODノードペア間に存在するF本のフローをM本のMFに分類するMF生成ステップとをコンピュータが実行し、
前記MF生成ステップは、
前記各フローfを各TStにおける発生トラヒック量Rf,tを要素とするL次元のベクトルRfを用いてK個のクラスタｃにクラスタリングするステップと、
各クラスタcから各MFの各TSにおけるトラヒック量の最大値を最小化してトラヒック比率を求めるステップと、
前記トラヒック比率に基づき、フローをMFに集約するステップと、
を含むことを特徴とするフロー集約方法。
【請求項７】
コンピュータを、
請求項１乃至４のいずれか１項に記載のフロー集約装置の各手段として機能させるためのフロー集約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フロー集約装置及び方法及びプログラムに係り、特に、同一発着（OD）ノードペア間の任意のトラヒックフローの集合であるマクロフロー（MF）を単位にトラヒックエンジニアリング（TE）による経路設定が可能なネットワークにおいて、TE制御コストを抑制するためにMF数を抑制し、かつ経路の安定性を高めるためトラヒック変動量の小さいMFを生成するためのフロー集約装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
インターネットは個々のフローの状態を網内で管理せず受信アドレスに基づきルーティング処理を行う。各ISP(Internet Services Provider)が管理する単一AS(Autonomous System)内では、OSPF(Open Shortest Path First)により固定的に設定されたリンク重みの総和が最小となる経路上にパケットが転送される。また、フローの受付制御を行わず転送レートは送信ホストが自律的に決定するため、原理的にリンク輻輳が発生し得る。そのため適切な通信品質を維持するために、ネットワーク(NW)を構成する全てのリンクの負荷が適切な水準以下となるようNWを設計・管理することがISPの主要な課題の一つとなる。リンク負荷は交流トラヒックデマンドの変動や各種障害に起因する経路の変更によって常に変化する。そのため使用率の低いリンクを積極的に利用するようパケットの流れる経路を動的に設定し、リンク負荷の分散を図るトラヒックエンジニアリング(TE)が数多く検討されている(例えば、非特許文献１参照)。ただし、これらの方式の多くはOSPFの使用を前提とし、リンク重みを適切に設定することで経路制御を行う。すなわち目的NWアドレスの単位で経路が設定されるため経路制御の粒度が荒く、高いリンク負荷平準化効果を実現することが困難なことが予想される。
【０００３】
一方で近年、OpenFlow に代表される SDN(Software Defined Network) 技術への注目が高まっている。OpenFlowでは、発着IPアドレス、発着ポート番号、プロトコル番号等のヘッダ情報を任意に組合せたものでフローを定義し、フローを単位に経路を制御することが可能である。SDNを用いることで、従来の技術では困難であったフロー単位の粒度の細かい経路制御が容易に可能となる。OpenFlowではコントローラがNW内の各ノードを集中制御することで、経路設定ポリシィを柔軟に変えることが可能であり、短い時間周期での動的経路制御が実現できる。例えばHongらやJainらは、データセンタ間NWにSDNを用いることで、細粒度で短期間に経路を切替るTE方式を提案している(例えば、非特許文献２参照)。
【０００４】
このようにSDNを用いることで、より粒度の細かい単位での経路制御が可能となり、高いリンク負荷平準化効果が期待される。しかし一方で、各ノードやコントローラは各経路制御単位の経路状態を保持する必要があり、例えば、発着 IP アドレス、発着ポート番号、プロトコルタイプの５タプルで定義されるフローを経路制御の粒度とした場合、管理すべき状態数が膨大となり大規模NWへの適用が困難となることが予想される。またTEは将来のトラヒック予測値に基づき行われるが、個別フローのトラヒックの時間変動は、目的NWアドレスの単位で経路を設定する場合と比較して大きくなるため、予測外れによる経路制御の性能低下が懸念される。しかし一方で、従来のOSPFのリンク重みを用いた経路制御法のように、目的NWアドレスを単位に荒い粒度で経路を設定した場合、大量のトラヒックが一回の経路制御対象となるため、経路制御の負荷平準化効果の低下が懸念される。また経路の迂回先のリンクが新たに高負荷となり、再度、経路が変更される結果、経路が不安定となる可能性がある。
【０００５】
そのため個別フローよりは大きく、かつ同一目的NWアドレスよりは小さな粒度で、TEを実施することが望ましい。すなわち、同一発着NWアドレスを有するフロー集合から一部のフローを集約したマクロフロー(MF)を定義し、MFを単位に経路制御を行うことが有効である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】A. Elwalid, C. Jin, S. Low, and I. Widjaja,"MATE: MPLS Adaptive Traffic Engineering,"IEEE INFOCOM 2001.
【非特許文献２】C. Y. Hong, et al., "Achieving high utilization with softwaredriven WAN," ACM SIGCOMM 2013. S. Jain, et al., "B4: Experience with a globally deployed software defined WAN," ACM SIGCOMM 2013.
【非特許文献３】Y. Hu, D. M. Chiu, and J. C. S. Lui, "Entropy based adaptive flow aggregation," IEEE/ACM Transactions on Networking, 17(3), pp. 698-711, 2009.
【非特許文献４】Y. Zhang, et al., "Online identification of hierarchical heavy hitters: algorithms, evaluation, and applications," ACM IMC 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
MFを生成する差異に考慮すべき要件を以下に示す。
【０００８】
(1)生成MF数M：各TE制御対象に対して、そのトラヒック量に基づいて経路を設定する。そのためTE制御対象ごとに各時点のトラヒックを測定し、必要によっては将来のトラヒック量を予測する必要がある。また、経路を最適設計する際に必要となる計算量は、TE制御対象の増加に伴い急激に増加することから、生成MF数Mは小さい方が望ましい。
【０００９】
(2)MFトラヒック変動量Vx：各フローのトラヒック量は変動するため、複数のフローを集約したMFのトラヒック量も変動する。各経路変更対象のある時点のトラヒック量や、ある期間の平均トラヒック量の予測値といった、一定の値で丸められたトラヒック量を元に、TE制御対象の経路を決めるため、TEの効果を高めるには各MFxのトラヒック変動量Vxは小さい方が望ましい。
【００１０】
(3)MF最大トラヒック量Q：TEによって、あるMFの経路が変更されたときに、このMFが新たに経由するリンクの負荷が増加するが、MFの最大トラヒック量が大きな場合、経由先のリンクの負荷が大きく増加する。その結果、経路変更先のリンクで新たに輻輳が生じ、再度、このMFが他の経路に変更され、経路が不安定となる可能性がある。TEによる経路変更を安定して行うためには、MFの最大トラヒック量Qは小さい方が望ましい。
【００１１】
複数のフローを集約したMFの構成法に関して、これまでにもいくつかの検討が見られる。例えばフロー計測におけるメモリ消費量を抑えることを目的に、IPヘッダ情報を階層的に探索することでトラヒック量の大きなフロー集約パタンを効率的に発見する方法が提案されている(例えば、非特許文献３参照)。またトラヒック量の大きなフローを発見することを目的に、同様のフロー集約法が提案されている(例えば、非特許文献４参照)。しかしこれらの方法は、TEの制御対象としてMFを構成することは想定しておらず、上述した３つの要件を満たすことができない。
【００１２】
生成MF数Mを減少させ多数のフローをMFに集約するほど、生成MFのトラヒック変動量Vxは統計多重効果により減少する。しかし一方で、MFの最大トラヒック量Qの増大が予想される。そのためQと、MおよびVxとの間には負の相関性があり、これら三つの設計目標の全てを最適化することは困難である。
【００１３】
本発明は、上記の点に鑑みなされたもので、ネットワークのすべてのリンクを適切な水準以上の効率で運用するトラヒックエンジニアリングを行うために、同一発着(OD)ネットワークアドレスのフローからマクロフロー（MF）単位に集約し、最適な経路を算出することが可能なフロー集約装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
一態様によれば、同一発着(OD)ノードペア間の任意のトラヒックフローの集合であるマクロフロー(MF)を単位にトラヒックエンジニアリング(TE)による経路設定が可能なネットワークにおいて、ODネットワークアドレスのフローからMF単位に集約するフロー集約装置であって、
生成MF数、時間を一定周期Tのタイムスロット(TS)に分割し、評価期間1≦t≦Lの各TStにおける各フローfの発生トラヒック量Rf,tを含むパラメタを入力するパラメタ入力手段と、
前記パラメタを用いて、TE制御コストを抑制するためにMF数を抑制し、かつ経路の安定性を高めるためトラヒック変動量の小さいMFを生成するMF生成手段と、
を有し、
前記MF生成手段は、
前記各フローfの発生トラヒック量Rf,tを用いて、各ODノードペア間に存在するF本のフローをM本のMFに分類する手段を含むフロー集約装置が提供される。
【発明の効果】
【００１５】
一態様によれば、同一発着(OD)ノードペア間の任意のトラヒックフローの集合であるマクロフロー(MF)を単位にトラヒックエンジニアリング(TE)による経路設定が可能なネットワークにおいて、TE制御コストを抑制するためにMF数を抑制し、かつ経路の安定性を高めるためトラヒック変動量の小さいMFを生成できる効果がある。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施の形態におけるフロー集約装置の構成例。
【図２】本発明の第１の実施の形態における貪欲算法に基づくMやVxを最小化するフローチャート。
【図３】本発明の第２の実施の形態におけるクラスタリングを用いたマクロフロー生成のフローチャート。
【図４】本発明の第２の実施の形態における球面k-means法のフローチャート。
【図５】本発明の第２の実施の形態における各クラスタから一部のトラヒックを抽出して各MFに集約する例。
【図６】Kansas CityからLos Angelesの間に対して生成されたMFのトラヒック変動係数の平均値を示す図。
【図７】ChicagoからWashingtonの間に対して生成されたMFトラヒック変動係数の平均値を示す図。
【図８】各MFのトラヒック変動係数の累積分布を示す図。
【図９】Kansas CityからLos Angelesの間に対して生成されたMFの最大ピークトラヒック量を示す図。
【図１０】ChicagoからWashingtonの間に対して生成されたMFの最大ピークトラヒック量を示す図。
【図１１】最大リンク負荷の時系列を示す図。
【図１２】リンク負荷の標準偏差の時系列を示す図。
【発明を実施するための形態】
【００１７】
以下、図面と共に本発明の実施の形態を説明する。
【００１８】
図１は、本発明の一実施の形態におけるフロー集約装置の構成例を示す。
【００１９】
同図に示すフロー集約装置１００は、パラメタ入力部１０１、マイクロフロー（MF）生成部１０２、MF出力部１０３を有する。
【００２０】
パラメタ入力部１０１は、MF設計に必要となる、生成MF数M、評価期間内の各タイムスロット(TS)tにおける各フローfの発生トラヒック量Rf,t、そして、クラスタリングを用いたMF生成法の場合に必要となるクラスタ数Kと重みパラメタβを入力する。
【００２１】
MF生成部１０２は、パラメタ入力部１０１から入力されたパラメタ値に基づき、M個のMFを生成し、MF出力部１０３によって、生成MFが出力される。
【００２２】
次に、本発明の実施の形態に係る、経路制御のためのフロー集約手法について説明する。
【００２３】
各発着(OD)ノードペア間に存在するF本のフローをM本のマクロフロー(MF)に分類し、各MFに対象に経路を変更することを考える。時間を一定周期Tのタイムスロット（TS）に分割し、評価期間１≦t≦Lの各TStにおける各フローｆの発生トラヒック量Rf,tを用いてMFを設計する。ここで、
【００２４】
【数１】
0005888684.tif 000002
をRf,tの評価期間における平均値
【００２５】
【数２】
0005888684.tif 000003
と定義する。
【００２６】
以後、個別フローやMFといったTEの制御対象のことを総称して「TE制御対象」と表記する。
【００２７】
以下では、第１の実施の形態として、貪欲算法により生成MF数MやMFのトラヒック変動量Vxを最小化するアプローチと、第２の実施の形態として、クラスタ分析により生成したトラヒック変動パタンが近いフローの各グループからフローを抽出してMFを生成するときの抽出比率を最適化するアプローチ、の二つの方式を提案する。
【００２８】
［第１の実施の形態］
本実施の形態では、図１に示す構成を有するフロー集約装置のパラメタ入力部１０１において、パラメタとして、生成MF数M、評価期間内の各タイムスロット(TS)tにおける各フローfの発生トラヒック量Rf,tをMF生成部１２０に入力する。
【００２９】
以下に、MF生成部１２０の処理を説明する。
【００３０】
生成MF数Mを与えたときに、MFのトラヒック変動量Vxか、もしくは最大トラヒック量Qのいずれか一つを最適化することを考える。F本のフローがある発着ノードペア間に存在するとき、これらをM個のMFに分類する組合せはMF個存在し、FやMの増加に伴い急激に増加するため、以下の図２に示す貪欲算法に基づく手順を用いて近似最適解を導出する。ただしFmをMFmに分類されたフローの集合と定義する。
【００３１】
ステップ１０１）1≦m≦Mの各mのFmを空集合φに初期化する。
【００３２】
ステップ１０２）フローの集合Fのフローから特性値Yfの降順にフローfを選択する。
【００３３】
ステップ１０３）選択したフローfをMの各MFmに分類したときのMF集合の目的関数として用いる特性値Pを、既にMFに分類されたフローのみを考慮して算出する。
【００３４】
ステップ１０４）Pが最小となるMFm*にフローfを分類（Fm=Fm+{f}）する。
【００３５】
ステップ１０５）Fの全フローがMFのいずれかに分類されるまでステップ１０２〜１０４の処理を反復する。
【００３６】
最適化の目的関数として用いる特性値Pと、フローfのMFへの割当順番を決めるfの特性値Yfとして、以下の（ａ）〜（ｅ）の５つを考える。
【００３７】
（ａ）  MFトラヒック量分散の総和の最小化：
MFトラヒック変動量Vxを低減することを目的に、各MFの評価期間におけるトラヒック量の分散の総和ΦをPに設定する。すなわち、
【００３８】
【数３】
0005888684.tif 000004
に設定する。ただしXm,tは各MFmの各TS tにおける既分類フローの発生トラヒック量の総和であり、
【００３９】
【数４】
0005888684.tif 000005
は、以下のXm,tの評価期間に渡る平均値である。
【００４０】
【数５】
0005888684.tif 000006
そして、Yfを以下のように各フローfのトラヒック量の変動係数に設定する。
【００４１】
【数６】
0005888684.tif 000007
（ｂ）  MF最大ピークトラヒック量の最小化：
MF最大トラヒック量Qを低減することを目的に、各MFの評価期間における最大トラヒック量の全MFにわたる最大値ΨをPに設定する。すなわち、
【００４２】
【数７】
0005888684.tif 000008
に設定する。そして、以下のように、Yfを各フローfの最大トラヒック量に設定する。
【００４３】
【数８】
0005888684.tif 000009
（ｃ)  MF最大総トラヒック量の最小化：
MF最大トラヒック量Qを低減することを目的に、各MFの評価期間における総トラヒック量の全MFにわたる最大値ΩをPに設定する。すなわち、
【００４４】
【数９】
0005888684.tif 000010
に設定する。そしてYfを、以下のように、各フローfの総トラヒック量に設定する。
【００４５】
【数１０】
0005888684.tif 000011
（ｄ）  MF最大ピーク比率の最小化：
経路の安定性を考えたとき、各MFの最大トラヒック量ではなく、全トラヒック量に対して占める割合の最大値を最小化することも考えられる。そこでMF最大トラヒック量Qを低減することを目的に、各MFの各TSにおけるトラヒック量比率の最大値
【００４６】
【数１１】
0005888684.tif 000012
をPに設定する。即ち、Fを全フローの集合、
【００４７】
【数１２】
0005888684.tif 000013
をTStにおける総トラヒック量とすると
【００４８】
【数１３】
0005888684.tif 000014
【００４９】
【数１４】
0005888684.tif 000015
に設定する。そして、以下のようにYfを各フローfのピークトラヒック量比率に設定する。
【００５０】
【数１５】
0005888684.tif 000016
（ｅ）  MFトラヒック量分散の総和の最小＋ピーク比率制約：
MFトラヒック変動量Vxの低減を目的としつつ、MF最大トラヒック量Qに制約上限を考慮することで、双方のバランスをとる。目的関数として用いる特性値Pは上記の式(1)と同一であるが、図２のステップ１０３，ステップ１０４で各フローfを各MFに収容する際に、ピークトラヒック量比率
【００５１】
【数１６】
0005888684.tif 000017
が、予め与えた制約上限値を超えないMFのみを候補として考える。Yfはやはり(ａ)の「MFトラヒック量分散の総和の最小化」と同様に、各フローfのトラヒック量の変動係数に設定する。
【００５２】
[第２の実施の形態]
本実施の形態では、クラスタリングを用いたマクロフローを生成する例を説明する。
【００５３】
本実施の形態では、MF生成部１０２は、パラメタ入力部１０１から第１の実施の形態の入力に加えて、クラスタ数Kと重みパラメタβが入力される。
【００５４】
MFトラヒック変動量VxとMF最大トラヒック量Qの双方が良好なパレート最適なMF集約を厳密に行うには、考えられる全ての集約パタンを調べる必要があり計算時間の観点から困難である。ところでVxとQの双方を抑えたMFを生成するためには、可能な限り時間変動パタンの異なるフローを同一のMFに集約することで、統計多重効果を向上させることが有効と思われる。このような観点から本実施の形態では、クラスタリングを用いたMF生成法について検討する。
【００５５】
本アプローチによるMF生成法は、(I)フローのクラスタ分類、(II)各フロークラスタからの抽出トラヒック比率の最適設計、(III)最適抽出トラヒック比率に基づきフローをMFに集約、の３つのステップから構成される。以下に図３の各々のステップについて述べる。
【００５６】
ステップ２１０）フローのクラスタ分類：
各フローfを、各TStにおける発生トラヒック量Rf,tを要素とするL次元のベクトルRfを用いてクラスタリングすることで、評価期間におけるトラヒックの時系列パタンが似たフローを同一のクラスタに分類する。クラスタ分類手法としては、非階層型クラスタ分析法として代表的なk-means法を用いる。k-means法は、パラメタ入力部１０１から与えられたK個のクラスタに分類対象をランダムに分類した状態からスタートし、生成された各クラスタの重心からの距離が最も近いクラスタに各分類対象を割当て直す処理を解が収束するまで反復する。
【００５７】
ただしRf,tの大きさがフローごとに大きく異なる場合、Rf,tをそのままベクトル要素としてクラスタ化を行うと、時系列パタンが似たフローを同一のクラスタに分類することが困難となる。そこで、Rfの各要素をRfの大きさ
【００５８】
【数１７】
0005888684.tif 000018
で除して1に正規化したベクトル
【００５９】
【数１８】
0005888684.tif 000019
に基づき、同様に各クラスタcの重心rc={rc,1,rc,2,…,rc,L}を正規化した値
【００６０】
【数１９】
0005888684.tif 000020
をクラスタcの重心とみなしてクラスタ分類を行う球面k-means法を適用する。以下に、図４と共に、球面k-means法の手順を示す。
【００６１】
ステップ２１１）各フローfに対して、
【００６２】
【数２０】
0005888684.tif 000021
を要素にもつL次元正規化ベクトルを算出する。
【００６３】
ステップ２１２）K個の各クラスタcの重心
【００６４】
【数２１】
0005888684.tif 000022
をL次元空間の正規化ベクトルからランダムに初期設定する。
【００６５】
ステップ２１３）各フローfを、
【００６６】
【数２２】
0005888684.tif 000023
と重心
【００６７】
【数２３】
0005888684.tif 000024
との距離
【００６８】
【数２４】
0005888684.tif 000025
が最小となるクラスタcに割り当てる。
【００６９】
ステップ２１４）各クラスタcの正規化重心
【００７０】
【数２５】
0005888684.tif 000026
を再計算する。
【００７１】
ステップ２１５）クラスタ構成が収束するまでステップ２１３とステップ２１４を反復する。
【００７２】
ステップ２２０）クラスタからの抽出トラヒック比率設計：
前手順で生成されたK個の各クラスタcに分類されたフローの集合をGcとする。そして各クラスタcから一定の比率αm,c(0≦αm,c≦1)のトラヒックをM本の各MFmに分類することを考える。すなわち各クラスタcの各TStにおける総トラヒック量をZc,tとするとき
【００７３】
【数２６】
0005888684.tif 000027
図５に示すようにαm,cZc,tのトラヒックをMF mのTS tに分類する。そのため各MF mのTS tにおけるトラヒック量をMm,tとすると、
【００７４】
【数２７】
0005888684.tif 000028
となる。そして各MFの各TSにおけるトラヒック量の最大値を最小化する以下の線形計画問題を解くことで、分類比率αm,cを最適設計する。
【００７５】
【数２８】
0005888684.tif 000029
ステップ２３０）フローのMF集約：
生成した各クラスタを構成するトラヒックを任意の粒度で分割できる場合には、ステップ２２０において、MFの最大トラヒック量を最小化する最適解が得られる。しかし実際にはフローの粒度でのみMF集約が可能であるため、各クラスタを構成するトラヒックを任意の粒度で分割することはできない。そこでフローfをMF mに割当てる場合に1を、そうでない場合に0をとる二値変数をxf,mとし、各TS tにおいて、xf,mから定まる各MF mのクラスタcからの抽出トラヒック量
【００７６】
【数２９】
0005888684.tif 000030
と、ステップ２２０で導出した分類比率αm,cから算出されるトラヒック量αm,cZc,tとの差分の全期間にわたる総和sが最小化するようxf,mを設計する整数計画問題を考える。
【００７７】
以上のMF収容方針によりMFトラヒック変動量Vxの低減が期待されるが、同時に、もう一方の設計目標であるMF最大トラヒック量Qの低減を考慮するため、xf,mから算出されるQと、sの全MFにわたる最大値Sとの重み付け線形和を最小化する、以下の整数計画問題を定義する（βは0≦β≦1の範囲の実数パラメタ）。
【００７８】
【数３０】
0005888684.tif 000031
＜生成MFに関する性能評価＞
以下では、米国の実験用NWであるInternet2（登録商標）で取得された4時間にわたるフロー情報の公開データを用いて、第１の実施の形態で述べた貪欲算法に基づく５つのMF生成法と、第２の実施の形態で述べたクラスタリングMF生成法の各々を用いてMFを生成した結果を分析する。
【００７９】
・評価条件
Internet2（登録商標）は9つのノードから構成されており、72の各ODペア間に5分の各TS内で発生したトラヒック量をRf,tに設定し、前半の24TSを評価対象期間とする。一例として、72のODペアのうちKansas City - Los Angeles間と、Chicago - Washington間の結果についてのみ、以下では示す。長さの短いフローに対してはTEの効果が期待できないことから、評価対象期間において3つ以上のTSでトラヒックが観測されたフローのみをMF集約の対象とする。評価対象に用いたフロー数は、Kansas City - Los Angeles間で1,101本、Chicago - Washington間で8,488本である。
【００８０】
第１の実施の形態における、貪欲算法のうち、MFトラヒック量分散の総和の最小化にピーク比率制約を付加する場合は、各フローの各TSにおけるトラヒック量の最大値に1.2を乗じた値をMFの許容トラヒック量の上限値に設定した。
【００８１】
また、第２の実施の形態における、クラスタリングを用いた方式ではクラスタ数Kを任意に設定できるが、Kを様々な値に設定して検証を行ったところ、1クラスタに含まれるフロー数が10以下となるKが極端に大きい場合や、2や3といったKが極端に小さい場合には、MF生成結果に大幅な悪化が見られたものの、その間の値に設定している場合はKを変えても結果に大きな影響がなかった。そのためKを各ODペアに対して、評価対象期間におけるMF集約対象フロー数が500未満の場合は5に、500以上1,000未満の場合は10に、1,000以上5,000未満の場合は20に、5,000以上の場合は30に、各々設定した。そのためKansas City - Los Angeles間はK=20、Chicago - Washington間はK=50とした。クラスタリングを用いたMF生成法の手順ステップ２２０とステップ２３０における最適化問題の解をCBC MILP Solver 2.7.5を用いて導出した。また目的関数における重みパラメタをβ＝1/3に設定した。
【００８２】
・マクロフロー生成結果：
図６に、Kansas City - Los Angelesを対象に3から50の範囲の様々な値にMF数Mを設定したときに、各方式で生成されたMFのトラヒック量の平均変動係数Φをプロットする。図７には同様にChicago - Washingtonの結果を示す。ただし、
【００８３】
【数３１】
0005888684.tif 000032
である。第１の実施の形態で述べた、目的関数がMFトラヒック量の総和、MF最大ピークトラヒック量、MF最大総トラヒック量、MF最大ピーク比率、そしてMFトラヒック量分散の総和+ピーク比率制約、の5つの貪欲算法による方法を、各々、G/var、G/peak、G/sum、G/pr、G/var+pbと表記する。MFへの集約を行わず全フローを個別に扱った場合(Individualと表記)の結果を点線で示す。
【００８４】
Mの増加に伴い各MFを構成するフロー数が減少するため、統計多重効果が低下し、Φは増加するが、いずれの方式を用いた場合もΦは集約を行わない場合と比較して半分程度の値以下に低減され、TE制御対象としての安定性の向上が確認できる。MF集約方式の中では、各MFのトラヒック変動量を最小化するG/varとG/var+pbのΦが小さいが、トラヒック変動を考慮しないG/peakとG/prのΦは大きい。ところでKansas City - Los AngelesのMの全領域と、Chicago - WashingtonのMの15以下の領域において、クラスタリング（Clustering）のΦが最も大きい。これは各MFへの集約粒度がフローであるため、生成された各クラスタから任意の粒度でトラヒックを抽出して各MFに集約することができず、第２の実施の形態で述べたステップ２２０で最適設計した抽出比率αm,cと、実際にステップ２３０で実施されるMF集約における分類比率とに誤差が生じることが要因と思われる。
【００８５】
図８にMF数をM=20に設定したときの、各方式によって生成されたMFのトラヒック量の変動係数の累積分布を示す。図６，７で見たように、G/varとG/var+pbが最も小さなΦを達成するが、これらの方式は他方式と比較して、生成された全てのMFのトラヒック量の変動係数が低く抑えられていることが確認できる。
【００８６】
図９にKansas City - Los Angelesを対象に、式(2)で与えられるMFの最大ピークトラヒック量ΨをMに対して同様にプロットする。図１０には同様にChicago - Washingtonの結果を示す。ただしΨの単位は各TS内の発生トラヒック量(Mbytes)である。MFへの集約を行うことでΨは常に非減少となるが、Mの増加に伴い各MFを構成するフロー数が減少するためΨは減少する。やはりクラスタリング（Clustering）のΨは全体的に大きい。Mが15程度以上の領域では、G/peak、G/pr、IndividualのΨの差異は小さく、これらの集約方式を用いた場合のΨの増加は無視できる。Mの増加に伴い各MFを構成するフロー数が減少するためΨは減少するが、Mが20程度以上の領域では、突出してトラヒック量の大きなフローのΨに対する比率が大きくなり、Mを増加させてもΨの低減効果は小さい。MF集約法の中では、ピークトラヒック量を最小化するG/peakやG/prが、Mの広い領域でΨが最小となり、G/var+pbもピーク比率を制約条件として考慮している効果により良好な特性を示している。最大トラヒック量を考慮しないG/varとG/sumのΨは大きい。
【００８７】
以上の評価結果をまとめると、クラスタリングを用いる方法は貪欲算法と比較して、全体的にMFトラヒック量の変動量や最大値を抑える効果は小さい。またクラスリングを用いる方法は、貪欲算法による方式と比較すると非常に計算時間が大きくなる。以上のことから、貪欲算法を用いた方式を用いることが望ましい。貪欲算法の中ではG/var+pbが両尺度において良好な評価値を達成した。またMF数Mを増加させるにつれて、MFトラヒック量の変動量は増加するのに対して、MF最大トラヒック量は20程度で値が収束しており、それ以上Mを増やしても結果の改善は見られないことから、評価に用いたトラヒックデータにおいては、MF数は20程度で十分である。例えばM=20でG/var+pbを用いた場合、Individualと比較してTE制御対象の最大トラヒック量の増加を15%程度に抑えながら、トラヒック変動量を1/5程度に低減でき、TEのリンク負荷平準化効果の向上が期待される。
【００８８】
＜TEの効果に関する性能評価＞
MFを単位としたTEを行うことで、TEの制御管理対象の数を大幅に低減することができるが、一方で制御粒度が荒くなるためTEの効果の低減が懸念される。そこで以下では、フローを単位にTEを行う従来の場合と、MFを単位にTEを行う場合とで、達成されるTEの効果を比較評価する。TEの効果を測る尺度としては、評価期間中の全ての各TSにわたる各リンク、各TSの平均トラヒック量(ave.ave)、各TSにおける最大リンクトラヒック量の全期間にわたる平均値(ave.max)、各TSにおける最小リンクトラヒック量の全期間にわたる平均値(ave.min)、各TSにおける各リンクのトラヒック量の標準偏差の全期間にわたる平均値(ave.sd)の4つを考える。
【００８９】
・評価条件：
TEの評価には、ノード数100で各ノードの次数が2以上で平均が4のランダムNWを作成し用いた。そして100×99=9,900個のODペアの各々に対して、上記のMF生成評価に用いたInternet2（登録商標）の72のODペアからランダムに一つ選択したODペアの4時間(48TS)の各フローのトラヒック量Rf,tをシミュレーション期間中に発生させた。ただしフローデータに含まれる多数のフローは1〜2スロット程度のごく少数のTSにおいてのみトラヒックが発生しているが、TEの効果を得るためには、ある程度の長さを有するフローのみを対象とする必要があることから、4TS以上でトラヒックが発生したフローのみをTEの対象とした。
【００９０】
実際には、将来のトラヒック量の予測に基づきMFを生成する必要があるが、本稿では予測方式については議論せず、予測が正確に行われていることを想定し、48の全TSのトラヒック量を用いてMFを生成した。またTEは、シミュレーション開始時に、各ODペアに対して30本のK-shortest path(ホップ数の最も短い30本の経路)を算出してTEの経路候補とした。すなわちシミュレーションの開始時点において、48の全TSのトラヒック量Rf,tに基づき、上記の「生成MFに関する性能評価」で述べた各方式でMFを生成した。そして生成された各MFに対して、各TSにおける最大トラヒックの降順に、一つずつ、48の全TSのNW上の全リンクの最大トラヒック量が最小となる経路を、30本の候補経路から選択して設定した。なおTEを用いない場合(NonTE)は、最短ホップ経路を常に設定した。また評価NWの各ODペアに対して適用するMF数Mを20に設定した。
【００９１】
・TEによるリンク負荷の平準化効果：
MFの導入のTEの効果に与える影響を分析するために、リンク負荷に関する4つの評価尺度を、TEを用いない場合(NonTE)、各フローの単位でTEを実施した場合(MicroTE)、そしてClustering, G/var、G/var+pbの3つの各提案方式で生成されたMFの単位でTEを実施した場合とで比較する。表１に、5つの各方式の4つの評価値をまとめる(単位はGbytes/slot)。NonTEの場合、常に最短ホップ経路が用いられるためave.aveは最小となり、MicroTEによって25%程度増加する。
【００９２】
【表１】
0005888684.tif 000033
しかしMicroTEはNonTEと比較して、ave.maxを30%程度、ave.sdを55%程度低減しており、TEによるリンク負荷平準化効果が確認できる。図１１に各TSにおける最大リンク負荷を、図１２にリンク負荷の標準偏差をプロットするが、評価に用いた全てのTSにおいて、この傾向が確認できる。
【００９３】
3つのMF生成方式の間では負荷平準化効果の差異は小さい。MFによるTEは、MicroTEと比較してava.aveを10%程度増加させるものの、ave.maxは5%程度、ave.sdは50%程度、減少させている。MFを単位にTEを実施した場合、個別フローでTEを行うMicroTEと比較して制御粒度が荒くなるものの、上記の「マイクロフロー生成結果」で述べたようにTE制御対象のトラヒック変動量が抑制されることの効果が要因と思われる。
【００９４】
上記の「TEの効果に関する性能評価」の「評価条件」で述べたように、評価では個別フローやMFといった各TE制御対象を最大トラヒック量の降順に、以後に経路を割当てるTE制御対象を考慮しないで経路を選択した。例えば同一発着ノード間に二本の経路候補AとBが存在し、二つのTS1とTS2において、各々、フローaが(100, 20)のトラヒック、フローbが(0, 80)のトラヒック、フローcが(80, 50)のトラヒックを生成する場合について考える。各フローを対象にTEを実施し、最初にフローaが経路Aを割当てられた場合、次に経路が割当てられるフローbには経路Bが割当てられる。そして残るフローcを経路Aに割当てた場合の最大リンク負荷は180に、経路Bに割当てた場合の最大リンク負荷は130となることから、より最大リンク負荷の小さい経路Bがフローcに対して割当てられる。一方、例えばフローaとフローbを一本のMF(a+b)に集約しているときは、最初に経路が割当てられるMF(a+b)に経路Aが割当てられた場合、残るフローcには経路Bが割当てられるため、この場合の最大リンク負荷は100となる。
【００９５】
この例に示すような、後で経路が割当てられるTE制御対象を考慮しないで経路を割当てた結果、最大リンク負荷が増加する可能性は、各TE制御対象のトラヒック変動量が大きなほど大きくなる。図６，７で見たように、MFのトラヒック変動量は個別フローと比較して小さくなるため、MFをTE制御対象とした方が最大リンク負荷やリンク負荷の分散が抑えられたものと思われる。そのため、例えばM=20として本発明の方式を用いて生成されたMFを単位に経路制御を行うことで、個別フローを単位に行う場合と比較して、リンク負荷平準化効果を50%程度向上させつつ、TE制御対象数を1/50〜1/400程度に低減することが可能である。
【００９６】
なお、上記の第１、２の実施の形態に示すMF生成部１０２における処理をプログラムとして構築し、フロー集約装置として利用されるコンピュータにインストールして実行させる、また、ネットワークを介して流通させることが可能である。
【００９７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００９８】
１００  フロー集約装置
１０１  パラメタ入力部
１０２  MF生成部
１０３  MF出力部
【図１】
0005888684.tif 000052
【図２】
0005888684.tif 000053
【図３】
0005888684.tif 000054
【図４】
0005888684.tif 000055
【図５】
0005888684.tif 000056
【図６】
0005888684.tif 000057
【図７】
0005888684.tif 000058
【図８】
0005888684.tif 000059
【図９】
0005888684.tif 000060
【図１０】
0005888684.tif 000061
【図１１】
0005888684.tif 000062
【図１２】
0005888684.tif 000063