JP7720003B2 - トラヒックエンジニアリング装置、トラヒックエンジニアリング方法およびトラヒックエンジニアリングプログラム - Google Patents

Description

本発明は、トラヒックエンジニアリング装置、トラヒックエンジニアリング方法およびトラヒックエンジニアリングプログラムに関する。

増え続けるトラヒックを効率的に収容することは、通信キャリアにとって重要な課題である。これに対し、従来、ネットワークトポロジやリンク容量、交流トラヒック等の制約条件からなる数理最適化問題を解くことにより、ネットワーク資源の利用率が最小となるようなトラヒックの経路を算出し、トラヒックの経路を明示的に変更するトラヒックエンジニアリング（ＴＥ：Traffic Engineering）と呼ばれる技術が知られている（非特許文献１、２参照）。

橋本 仁、他５名、「パス再設定トラヒック量を制限可能な動的MPLS-TE手法の提案と評価」、電子情報通信学会論文誌B、（社）電子情報通信学会、2008年、Vol.J91-B No.6、pp. 645-654 Yufei Wang、Zheng Wang、「Explicit Routing Algorithms for Internet Traffic Engineering」、IEEE. Proceedings Eight International Conference on Computer Communications and Networks (Cat. No.99EX370)

しかしながら、従来技術では、経路変更の対象となる通信を、フロー情報や運用ポリシー等に基づいて限定したり抑制したりすることは困難である。例えば、従来のシステムではトラヒック識別の分解能が低く、リンク単位等、太束単位でのＴＥを行うことしかできない。また、交流トラヒックの情報をつまびらかに分析する仕組みがない。したがって、多重にラベリング・カプセリングされたトラヒックをつまびらかに分析した上で、経路変動を抑えるように経路を計算し、細粒度にトラヒックを識別して経路制御を行うことは困難である。また、通信キャリア等の大規模なネットワークでは、現実的な時間内に問題を解くことが困難であることが知られている。

本発明は、上記に鑑みてなされたものであって、フロー情報や運用ポリシー等に基づいて、経路変更の対象となる通信を限定したり抑制したりすることを可能とすることを目的とする。

上述した課題を解決し、目的を達成するために、本発明に係るトラヒックエンジニアリング装置は、ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得部と、経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算部と、を有することを特徴とする。

本発明によれば、フロー情報や運用ポリシー等に基づいて、経路変更の対象となる通信を限定したり抑制したりすることが可能となる。

図１は、ＴＥ装置の概要を説明するための図である。 図２は、ＴＥ装置の概要を説明するための図である。 図３は、ＴＥ装置の概要を説明するための図である。 図４は、ＴＥ装置の概要を説明するための図である。 図５は、ＴＥ装置の概略構成を例示する模式図である。 図６は、ネットワークトポロジ情報のデータ構成を例示する図である。 図７は、トラヒック情報データのデータ構成を例示する図である。 図８は、前処理部の処理を説明するための図である。 図９は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１０は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１１は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１２は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１３は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１４は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１５は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１６は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１７は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１８は、第１の実施形態のＴＥ装置の処理を説明するための図である。 図１９は、ＴＥ処理手順を示すフローチャートである。 図２０は、第２の実施形態のＴＥ装置の処理を説明するための図である。 図２１は、第２の実施形態のＴＥ装置の処理を説明するための図である。 図２２は、第３の実施形態のＴＥ装置の処理を説明するための図である。 図２３は、第３の実施形態のＴＥ装置の処理を説明するための図である。 図２４は、他の実施形態のＴＥ装置の処理を説明するための図である。 図２５は、ＴＥプログラムを実行するコンピュータを例示する図である。

以下、図面を参照して、本発明の一実施形態を詳細に説明する。なお、この実施形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。

［トラヒックエンジニアリング（ＴＥ）装置の概要］
図１～図４は、ＴＥ装置の概要を説明するための図である。まず、図１に示すように、本実施形態のＴＥ装置１０は、ＮＥ（Network Element）から収集された交流トラヒック情報から、ＶＰＮ等のサービスや、ユーザ通信、通信経路等の情報を分析し、分析した情報を元に、経路変動を抑制した経路計算を行う。

ここで、従来のＴＥでは、図２に例示するように、トラヒックの途中分岐・合流を許容するＢＰ（Bifurcation Problem）と、許容しないＮＢＰ（Non- Bifurcation Problem）とに分類される。ＢＰでは、図２（ａ）に例示するように、数理最適化問題の解が実数解となることが許容されるため、計算は早いが、トラヒックの途中分岐・合流を実在のネットワーク装置で実現することは困難であった。

一方、ＮＢＰでは、図２（ｂ）に例示するように、数理最適化問題の解が整数解に限定されるため、ネットワーク装置で実現することは可能であるものの、整数解の求解はＮＰ困難であることが知られている。

そこで、本実施形態のＴＥ装置１０では、経路計算の際には、ヒューリスティック解法を用いて、最適解ではないが現実的な時間内に、トラヒックの途中分岐・合流が発生しないように経路を計算する。

具体的には、図３に示すように、ＴＥ装置１０は、収集された交流トラヒック情報を分析して、ネットワークトポロジ情報とトラヒック情報データを取得し、記憶部１４に格納する。そして、ＴＥ装置１０は、取得したネットワークトポロジ情報とトラヒック情報データとを元にして、フローの経路変動を抑えた経路計算を行う。

その際に、ＴＥ装置１０は、後述するように、線形計画問題ソルバによる数理計算結果である最適解を活用して、経路計算を行ってもよい。例えば、ＴＥ装置１０は、ネットワークトポロジ情報とトラヒック情報データとを用いて、以下に示す目的変数、制約条件、変数で線形計画問題を立式して線形計画問題ソルバに引き渡し、結果の変数の返却を受け付ける。

線形計画問題の目的変数は、最大リンク使用率の最小化、経路変動フローの最小化とする。また、制約条件は、ネットワークトポロジ、リンク容量、各フローのトラヒック量・経路情報とする。また、変数は、各フローのトラヒックが通るべき経路とし、実数解を得る。

なお、ＴＥ装置１０は、図４に示すように、経路計算の前に、経路変動させたくないフローを削除する前処理を行って、経路計算の対象から除外する。図４に示す例では、プロミアムユーザ向けサービスであることを示すＶＰＮ識別子「Ｈ」のフローが、トラヒック情報データから当該フローを削除することにより、経路計算の対象から除外されている。これにより、経路変動の抑制を効率よく行うことが可能となる。

［第１の実施形態］
［ＴＥ装置の構成］
図５は、ＴＥ装置の概略構成を例示する模式図である。図５に例示するように、ＴＥ装置１０は、パソコン等の汎用コンピュータで実現され、入力部１１、出力部１２、通信制御部１３、記憶部１４、および制御部１５を備える。

入力部１１は、キーボードやマウス等の入力デバイスを用いて実現され、操作者による入力操作に対応して、制御部１５に対して処理開始などの各種指示情報を入力する。出力部１２は、液晶ディスプレイなどの表示装置、プリンター等の印刷装置等によって実現される。例えば、出力部１２には、後述するＴＥ結果が表示される。

通信制御部１３は、ＮＩＣ（Network Interface Card）等で実現され、ＬＡＮ（Local Area Network）やインターネットなどの電気通信回線を介した外部の装置と制御部１５との通信を制御する。例えば、通信制御部１３は、エッジルータ等のネットワーク装置や、ネットワーク装置の交流トラヒック情報を収集する収集装置、ＴＥを実施するコントローラ等の外部の装置と制御部１５との通信を制御する。

記憶部１４は、ＲＡＭ（Random Access Memory）、フラッシュメモリ（Flash Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現され。記憶部１４には、ＴＥ装置１０を動作させる処理プログラムや、処理プログラムの実行中に使用されるデータなどが予め記憶され、あるいは処理の都度一時的に記憶される。

本実施形態において、記憶部１４には、ネットワークトポロジ情報１４ａ、トラヒック情報データ１４ｂ等が記憶される。なお、記憶部１４は、通信制御部１３を介して制御部１５と通信する構成でもよい。

図６はネットワークトポロジ情報のデータ構成を例示する図である。ネットワークトポロジ情報１４ａは、エッジルータ等のネットワーク装置（ＮＥ）の接続形態を示す。例えば、図６に例示するように、ネットワークトポロジ情報１４ａは、ＮＥとＮＥ間のリンクをグラフ形式で表した情報である。なお、図６に示すＶ、Ｗ、Ｘ、Ｙ、Ｚはエッジルータである。

また、図７は、トラヒック情報データのデータ構成を例示する図である。図７に示すように、トラヒック情報データ１４ｂは、各フローの回線識別子、ＶＰＮ識別子、ユーザ通信識別子、通信元エッジルータ、通信先エッジルータ、利用帯域、通信経路の情報を含む。回線識別子は、例えば、Ｃ－ＶＬＡＮのＶＩＤである。ＶＰＮ識別子は、例えば、ＩＰｓｅｃ等のトンネルのアウターＩＰアドレスである。また、ユーザ通信識別子は、トンネルのインナーＩＰアドレスである。

図５の説明に戻る。制御部１５は、ＣＰＵ（Central Processing Unit）やＮＰ（Network Processor）やＦＰＧＡ（Field Programmable Gate Array）等を用いて実現され、メモリに記憶された処理プログラムを実行する。これにより、制御部１５は、図５に例示するように、取得部１５ａ、前処理部１５ｂ、経路計算部１５ｃ、および数理計算部１５ｄとして機能する。なお、これらの機能部は、それぞれが異なるハードウェアに実装されてもよい。例えば、前処理部１５ｂは、他の機能部とは異なるハードウェアに実装されてもよい。また、制御部１５は、その他の機能部を備えてもよい。

取得部１５ａは、ネットワーク装置の接続形態を示すネットワークトポロジ情報１４ａと、トラヒック内のフローの情報であるトラヒック情報データ１４ｂとを取得する。例えば、取得部１５ａは、交流トラヒック情報を収集する収集装置等から、通信制御部１３を介して交流トラヒック情報を取得する。また、取得部１５ａは、収集された交流トラヒック情報を分析して、ネットワークトポロジ情報１４ａとトラヒック情報データ１４ｂとを取得する。取得部１５ａは、取得したネットワークトポロジ情報１４ａとトラヒック情報データ１４ｂとを記憶部１４に格納する。

前処理部１５ｂは、トラヒック内のフローの情報であるトラヒック情報データ１４ｂから、経路変更を許容しないフローの情報を削除する。具体的には、前処理部１５ｂは、入力部１１あるいは通信制御部１３を介して、経路変更を許容しないフローを指定する入力を受け付けて、指定されたフローをトラヒック情報データ１４ｂから削除する。

例えば、前処理部１５ｂは、図４に例示したように、プロミアムユーザ向けサービス等の経路変動させたくないフローを、トラヒック情報データ１４ｂから削除する。これにより、前処理部１５ｂは、当該フローを後述するＴＥ処理の対象から除外する。

また、前処理部１５ｂは、トラヒック内のフローの情報であるトラヒック情報データ１４ｂに、異なる時刻で取得されたトラヒック量の平均値、最大値または最小値の少なくともいずれかを含める。

ここで、図８は、前処理部の処理を説明するための図である。トラヒックの時間変動を考慮してＴＥ処理を行うために、前処理部１５ｂは、図８に示すように、異なる時刻で取得された複数のデータについて、各フローの帯域について、平均値、最大値および最小値を算出してトラヒック情報データ１４ｂに追加してもよい。

通常、フローの帯域は時間に伴って変化するため、ある時刻のトラヒック情報を切り取って算出した経路が、異なる時刻で最適解になるとは限らない。これに対し、後述するＴＥ処理において、ネットワーク資源の空き具合やポリシーに応じて、各フローの帯域として、平均値、最大値または最小値を使い分けることが可能となる。例えば、ネットワーク資源の空具合が多い場合や、優先フローについて、利用帯域の最大値を用いてＴＥ処理を行う。

図５の説明に戻る。経路計算部１５ｃは、経路を変更するフローの数が最小となるように、各フローの経路を計算する。

具体的には、本実施形態のＴＥ装置１０では、数理計算部１５ｄが、経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する。また、経路計算部１５ｃは、トラヒック内のフローをグルーピングしたフロー群を対象にして得られた線形計画問題の解に基づいて、各フローの経路を確定する。

ここで、図９～図１８は、第１の実施形態のＴＥ装置の処理を説明するための図である。まず、図９に示すように、経路計算部１５ｃが、もともとのユーザ通信単位のフローを、ＶＰＮ単位あるいはＶＬＡＮ単位等にグルーピングして、粒度を荒くしたフロー群を作成する。また、数理計算部１５ｄが、ＶＰＮ単位等に荒い粒度に集約されたフロー群を対象にして線形計画問題を解く。

そして、経路計算部１５ｃが、実数解に対して各フローを当てはめる詰め込み問題を適用する。つまり、トラヒックの途中分岐が発生する実数解に対し、もともとのユーザ通信単位のフローを詰め込むことで、実数解を実現する。図８に示す例では、ＶＰＮ単位のフローを７０％と３０％とに分岐させる実数解が、ユーザ通信単位のフローの振り分けで実現されている。

具体的には、経路計算部１５ｃは、トラヒック情報データ１４ｂをエッジルータごとに集約し、図１０に例示するように、エッジルータ間の情報を表すトラヒック行列を作成する。図１０には、エッジルータ間の利用帯域（Ｍｂｐｓ）が例示されている。

次に、数理計算部１５ｄが、ネットワークトポロジ情報１４ａとトラヒック行列とを用いて、最大リンク利用率を最小にする線形計画問題を解き、最適解を計算する。

そして、経路計算部１５ｃは、最適解において分岐しているフローについて、回線単位で収容できないフローは、ＶＰＮ単位での収容を検討する。また、経路計算部１５ｃは、ＶＰＮ単位で収容できないフローは、ユーザ通信単位で検討する。また、経路計算部１５ｃは、ユーザ通信単位で収容できないフローは、ダイクストラ法で経路を計算する。

例えば、図１１～図１８に示す例では、図１０に示したトラヒック行列のうち、利用帯域が１３０ＭｂｐｓであるエッジルータＶからエッジルータＸへのフロー（Ｖ－Ｘフロー）をＴＥ処理の対象としている。

図１１（ａ）には、Ｖ－Ｘフローの最適解におけるリンクＬ１～Ｌ６のそれぞれの帯域が示されている。この帯域は、以下に説明するように、経路計算部１５ｃが各リンクに対して収容するフローの上限値とみなすことができる。例えば、Ｌ１には、１２７Ｍｂｐｓまでの利用帯域のフローを収容できる。なお、収容上限値は、調整用のパラメータを掛けて緩和してもよい。これにより、後述するように、収容できないフローが生じることを回避することが可能となる。

また、図１１（ｂ）には、１３０ＭｂｐｓのＶ－Ｘフローの回線単位の内訳が例示されている。同様に、図１２～図１７には、Ｖ－Ｘフローの回線単位、ＶＮＰ単位あるいはユーザ通信単位の内訳が例示されている。

経路計算部１５ｃは、対象のフローについて、その始点のノードから分岐する一番太いリンクを選択する。図１１（ａ）に示す例では、リンクＬ１が選択される。このリンクＬ１には１２７Ｍｂｐｓまでのフローを収容できる。経路計算部１５ｃは、その範囲に収容できる回線単位のフローを、グリーディ法により利用帯域が大きい順に収容する。例えば、リンクＬ１には、図１１（ｂ）に示す利用帯域１２０Ｍｂｐｓの回線識別子Ａのフローが収容される。

次に、経路計算部１５ｃは、回線識別子Ａのフローを対象として、リンクＬ１に続く一番太いリンクＬ２を選択する。このリンクＬ２には１０１Ｍｂｐｓまでのフローを収容できる。図１２（ａ）に示すように、その範囲に収容できる回線単位のフローもＶＰＮ単位のフローもない。そこで、経路計算部１５ｃは、図１２（ｂ）に示すユーザ通信単位のフローのうち、利用帯域１００Ｍｂｐｓであって一番太いユーザ通信識別子Ｍのフローを収容する。

次に、経路計算部１５ｃは、ユーザ通信識別子Ｍのフローを対象として、リンクＬ２に続く一番太いリンクＬ３を選択する。このリンクＬ３には１０１Ｍｂｐｓまでのフローを収容できる。経路計算部１５ｃは、図１３に示すように、その範囲にユーザ通信識別子Ｍのフローを収容する。この場合に、経路計算部１５ｃは、ユーザ通信単位のユーザ通信識別子Ｍのフローの収容が完了した旨を示すフラグ情報を返却する。

また、経路計算部１５ｃは、未収容のフローを対象とするため、１つ前に処理を戻し、リンクＬ２に収容可能な残余帯域を、１０１Ｍｂｐｓから確定した１００Ｍｂｐｓを差し引いた１Ｍｂｐｓに更新する。図１４（ｂ）に示す未収容のユーザ通信識別子Ｎのフローは、利用帯域２０Ｍｂｐｓであって、リンクＬ２の残余帯域に収容できない。

そこで、経路計算部１５ｃは、回線識別子Ａのフローを対象として、リンクＬ１に続くリンクＬ４を選択する。このリンクＬ４には、２６Ｍｂｐｓまでのフローを収容できるが、図１５（ａ）に示すように、その範囲に収容できるＶＰＮ単位のフローはない。そこで、経路計算部１５ｃは、ユーザ通信識別子Ｎのフローを収容する。

次に、経路計算部１５ｃは、ユーザ通信識別子Ｎのフローを対象として、リンクＬ４に続くリンクＬ５を選択する。このリンクＬ５には、２６Ｍｂｐｓまでのフローを収容できる。経路計算部１５ｃは、その範囲にユーザ通信識別子Ｎのフローを収容する。また、経路計算部１５ｃは、図１５（ｂ）に示すように、ユーザ通信単位のユーザ通信識別子Ｎのフローの収容が完了した旨を示すフラグ情報を返却する。

次に、経路計算部１５ｃは、未収容のフローを対象とするため、１つ前に処理を戻し、リンクＬ４の残余帯域を、２６Ｍｂｐｓから確定した２０Ｍｂｐｓを差し引いて６Ｍｂｐｓに更新する。一方、図１６（ｂ）に示すように、未収容のフローがないため、経路計算部１５ｃは、さらに１つ前に処理を戻し、図１６（ａ）に示すように、回線識別子ＡのＶＰＮ単位のフローの収容が完了した旨を示すフラグ情報を返却する。

次に、経路計算部１５ｃは、未収容の回線単位のフローを対象として、リンクＬ６を選択する。このリンクＬ６には３Ｍｂｐｓまでのフローを収容きるが、図１７（ａ）に示すように、その範囲に収容できる回線単位のフローがない。ここで未収容の回線識別子Ｃのフローについては、図１７（ｂ）に示すように、ＶＰＮ単位でもユーザ通信単位でも収容できない。そこで、経路計算部１５ｃは、ユーザ通信識別子Ｒのフローについて、未収容である旨を示す情報を返却して、Ｖ－Ｘフローについての処理を終了する。

なお、経路計算部１５ｃは、上記したように、収容上限値に調整用のパラメータを掛けて緩和することにより、未収容のフローが生じないようにしてもよい。

また、経路計算部１５ｃは、未収容のフローについて、始点から順次、ダイクストラ法により最短経路を探索することにより、経路を計算する。この場合に、経路計算部１５ｃは、図１８に例示するように、リンクｉ，ｊの残余帯域ｃ＿ｉ，ｊの逆数をリンクのメトリックとして、経路を計算する。これにより、残余帯域が大きいほど、つまり、リンク利用率が小さいほど、優先してリンクを含む経路が選択される。

また、経路計算部１５ｃは、確定した経路に基づいて、経路変更をコントローラに指示する。

［トラヒックエンジニアリング（ＴＥ）処理］
次に、図１９は、ＴＥ処理手順を示すフローチャートである。図１９のフローチャートは、例えば、ユーザが処理の開始を指示したタイミングで開始される。

まず、取得部１５ａが、交流トラヒック情報を収集する収集装置等から、交流トラヒック情報を取得して、分析することにより、ネットワークトポロジ情報１４ａとトラヒック情報データ１４ｂとを取得する（ステップＳ１）。取得部１５ａは、取得したネットワークトポロジ情報１４ａとトラヒック情報データ１４ｂとを記憶部１４に格納する。

次に、前処理部１５ｂが、経路変更を許容しないフローを指定する入力を受け付けて、指定されたフローをトラヒック情報データ１４ｂから削除する（ステップＳ２）。

次に、経路計算部１５ｃが、経路を変更するフローの数が最小となるように、各フローの経路を計算する（ステップＳ３）。具体的には、数理計算部１５ｄが、経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する。そして、経路計算部１５ｃは、トラヒック内のフローをグルーピングしたフロー群を対象にして得られた線形計画問題の解に基づいて、各フローの経路を確定する。

例えば、経路計算部１５ｃは、最適解において分岐しているフローについて、回線単位で収容できないフローは、ＶＰＮ単位での収容を検討する。また、経路計算部１５ｃは、ＶＰＮ単位で収容できないフローは、ユーザ通信単位で検討する。また、経路計算部１５ｃは、ユーザ通信単位で収容できないフローは、ダイクストラ法で経路を計算して確定する。

また、経路計算部１５ｃは、確定した経路に基づいて、経路変更をコントローラに指示する（ステップＳ４）。これにより、一連のＴＥ処理が終了する。

［第２の実施形態］
図２０および図２１は、第２の実施形態のＴＥ装置の処理を説明するための図である。なお以下では、上記の第１の実施形態のＴＥ装置１０のＴＥ処理と異なる点についてのみ説明を行い、共通する点についての説明を省略する。

第２の実施形態のＴＥ装置１０では、経路計算部１５ｃは、各フローのトラヒック量の降順の合計がトラヒック総量に対して所定の割合を占める場合に、該フローを対象に、各フローの経路を計算する。具体的には、経路計算部１５ｃは、図２０に示すように、トラヒック総量に対して支配的なＴｏｐ－ＮフローのみをＴＥ処理の対象とする。

ここで、Ｔｏｐ－Ｎフローとは、トラヒック総量の所定のパーセンテージを占めるフローである。この実施形態では、Ｔｏｐ－Ｎフロー以外のフローは経路変更を行わない。Ｔｏｐ－Ｎフローの数はＴｏｐ－Ｎフロー以外の数より圧倒的に多いものと想定される。したがって、ＴＥ装置１０は、ある程度十分な最適化効果を確保しつつ、経路変動が発生するフロー数を抑制することが可能となる。

図２１には、第２の実施形態のＴＥ処理手順が示されている。まず、経路計算部１５ｃが、トラヒック情報データ１４ｂのフローを利用帯域でソートする（ステップＳ１１）。

また、経路計算部１５ｃは、ソートされたトラヒック情報データ１４ｂの、Ｔｏｐ－Ｎフローを選択する。すなわち、経路計算部１５ｃは、トラヒック情報データ１４ｂのフローを利用帯域が大きい順に、総利用帯域の所定のＸ％となるように選択する（ステップＳ１２）。ここで、Ｘは、ＳＧ等で管理されるパラメータである。

経路計算部１５ｃは、選択したＴｏｐ－Ｎフローを以降の処理対象のフロー集合とする（ステップＳ１３）。また、経路計算部１５ｃは、Ｔｏｐ－Ｎフロー以外のフローの利用帯域を、ネットワークトポロジ情報１４ａのリンク容量から差し引く（ステップＳ１４）。

経路計算部１５ｃは、フロー集合からフローを１つずつ選択し、ダイクストラ法による最短路探索を行って、パス配置（経路）を決定する（ステップＳ１５）。この場合に、経路計算部１５ｃは、各リンクの残余帯域ｃ＿ｉｊの逆数をメトリックとして、経路を計算する。また、経路計算部１５ｃは、経路が決定したフローの利用帯域をリンク容量から差し引く（ステップＳ１６）。

経路計算部１５ｃは、フロー集合が空でない場合に（ステップＳ１７、Ｎｏ）、ステップＳ１５に処理を戻す。そして、経路計算部１５ｃは、フロー集合が空になった場合に（ステップＳ１７、Ｙｅｓ）、一連の処理を終了する。

［第３の実施形態］
図２２および図２３は、第３の実施形態のＴＥ装置の処理を説明するための図である。第３の実施形態のＴＥ装置１０では、経路計算部１５ｃは、数理計算部１５ｄが計算した解のうちの実数解について、ダイクストラ法により経路を再度計算する。具体的には、図２２に示すように、線形計画問題を周知の解法で解いた後、経路変動を考慮した改良を行う。具体的には、まず、線形計画問題を解き、最大リンク使用率を最小化するような各フローの経路の解を得る。

整数解は、ネットワーク装置で実現可能であるので、得られた経路が確定する。一方、実数解は、ネットワーク装置で実現が困難であるため、経路計算部１５ｃが、ダイクストラ法で再計算を行う。その際に、経路計算部１５ｃは、リンクのメトリックとして、ボトルネックリンクが悪化するか否か、また、経路計算部１５ｃは、リンク利用率のどれだけ増加するかに着目する。そして、もともとのパス配置（経路）でのリンク利用率と、再計算したパス配置でのリンク利用率とを比較して、リンク利用率が低くなる方のパス配置を採用する。

図２３には、第３の実施形態のＴＥ処理手順が示されている。まず、数理計算部１５ｄが、線形計画問題を解き、最大リンク使用率ｒと、各フローの経路とを求める（ステップＳ２１）。

経路計算部１５ｃは、フローのうち、経路が分岐する実数解となったフローを選択し、Ｓ＿ｄ、Ｓ＿ｅに分類する（ステップＳ２２）。ここで、Ｓ＿ｄは、リンク使用率がｒのリンクを通るフローであり、Ｓ＿ｅは、Ｓ＿ｄ以外のフローである。また、Ｓ＿ｄおよびＳ＿ｅ以外の整数解のフローの各リンク上の帯域をｆ＿ｉｊとして（ステップＳ２３）、経路を確定する。

経路計算部１５ｃは、Ｓ＿ｄおよびＳ＿ｅが空になるまで（ステップＳ２４）、ステップＳ２５～Ｓ２９の処理を繰り返す（ステップＳ３０）。

まず、経路計算部１５ｃは、ｆ＿ｉｊを基に、最大リンク利用率ｒ’を求める（ステップＳ２５）。次に、経路計算部１５ｃは、Ｓ＿ｄ、Ｓ＿ｅから１つずつフローを選択し、ダイクストラ法による最短経路探索によって、パス配置（経路）を決定する（ステップ２６）。この場合のリンクのメトリックは、次式（１）とする。

経路計算部１５ｃは、ダイクストラ法で求めたパス配置と、もともとのパス配置とが一致しているか否かを確認する（ステップＳ２７）。一致していない場合には（ステップＳ２７、Ｎｏ）、利用率が低くなる方のパス配置を採用し（ステップＳ２８）、経路が決定したフローの利用帯域をｆ＿ｉｊに加算する（ステップＳ２９）。一方、一致している場合には（ステップＳ２７、Ｙｅｓ）、ステップＳ２９に処理を進める。

そして、経路計算部１５ｃは、Ｓ＿ｄおよびＳ＿ｅが空になった場合に、一連の処理を終了する。

［他の実施形態］
図２４は、他の実施形態のＴＥ装置の処理を説明するための図である。ＴＥ装置１０は、上記第１～第３の実施形態の処理を組み合わせた処理を行ってもよい。図２４において、計算方法（１）とは、第１の実施形態の処理を意味している。また、計算方法（２）とは、第２の実施形態の処理を意味しており、計算方法（３）とは、第３の実施形態の処理を意味している。

具体的には、計算方法（１）では、図９に例示したように、第１の実施形態のグルーピングを行ってＴＥ対象の粒度を変更し、線形計画問題の解を求め、実数解に対して詰め込み問題を適用する。計算方法（２）では、図２０に例示したように、トラヒック総量に対して支配的なＴｏｐ－ＮのみをＴＥ処理の対象として選択し、ダイクストラ法でフロー配置を計算する。計算方法（３）では、図２２に例示したように、線形計画問題の解を求め、実数解について、経路変動を考慮して再配置を行う。

そして、ＴＥ装置１０は、図２４に例示するように、計算方法（１）～（３）の処理を組み合わせることにより、経路を確定することが可能である。これにより、状況に応じた最適な方式で、さらに効率よく経路変動を抑止してＴＥ処理を行うことが可能となる。

［効果］
以上、説明したように、ＴＥ装置１０において、取得部１５ａが、ネットワーク装置の接続形態を示すネットワークトポロジ情報１４ａと、トラヒック内のフローの情報であるトラヒック情報データ１４ｂとを取得する。また、経路計算部１５ｃは、経路を変更するフローの数が最小となるように、各フローの経路を計算する。

具体的には、数理計算部１５ｄが、経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する。また、経路計算部１５ｃが、トラヒック内のフローをグルーピングしたフロー群を対象にして得られた線形計画問題の解に基づいて、各フローの経路を確定する。これにより、フロー情報や運用ポリシー等に基づいて、現実的な時間内に効率よく経路変更の対象となる通信を限定したり抑制したりすることが可能となる。

または、経路計算部１５ｃは、各フローのトラヒック量の降順の合計がトラヒック総量に対して所定の割合を占める場合に、これらのフローを対象に、各フローの経路を計算する。これにより、フロー情報や運用ポリシー等に基づいて、現実的な時間内に効率よく経路変更の対象となる通信を限定したり抑制したりすることが可能となる。

または、数理計算部１５ｄは、経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する。また、経路計算部１５ｃは、解のうちの実数解について、ダイクストラ法により経路を再度計算する。これにより、フロー情報や運用ポリシー等に基づいて、現実的な時間内に効率よく経路変更の対象となる通信を限定したり抑制したりすることが可能となる。

また、前処理部１５ｂは、トラヒック内のフローの情報であるトラヒック情報データ１４ｂから、経路変更を許容しないフローの情報を削除する。これにより、経路変動を効率よく抑制することが可能となる。

また、前処理部１５ｂは、トラヒック内のフローの情報であるトラヒック情報データ１４ｂに、異なる時刻で取得されたトラヒック量の平均値、最大値または最小値の少なくともいずれかを含める。これにより、ネットワーク資源の空き具合やポリシーに応じて、各フローの帯域として、平均値、最大値または最小値を使い分けて、効果的なＴＥ処理を行うことが可能となる。

［プログラム］
上記実施形態に係るＴＥ装置１０が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。一実施形態として、ＴＥ装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記のＴＥ処理を実行するＴＥプログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記のＴＥプログラムを情報処理装置に実行させることにより、情報処理装置をＴＥ装置１０として機能させることができる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal Handyphone System）等の移動体通信端末、さらには、ＰＤＡ（Personal Digital Assistant）等のスレート端末等がその範疇に含まれる。また、ＴＥ装置１０の機能を、クラウドサーバに実装してもよい。

図２５は、ＴＥプログラムを実行するコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。

メモリ１０１０は、ＲＯＭ（Read Only Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic Input Output System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１０５１およびキーボード１０５２が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１０６１が接続される。

ここで、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施形態で説明した各情報は、例えばハードディスクドライブ１０３１やメモリ１０１０に記憶される。

また、ＴＥプログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュール１０９３として、ハードディスクドライブ１０３１に記憶される。具体的には、上記実施形態で説明したＴＥ装置１０が実行する各処理が記述されたプログラムモジュール１０９３が、ハードディスクドライブ１０３１に記憶される。

また、ＴＥプログラムによる情報処理に用いられるデータは、プログラムデータ１０９４として、例えば、ハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。

なお、ＴＥプログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１０４１等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、ＴＥプログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮ（Local Area Network）やＷＡＮ（Wide Area Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。

以上、本発明者によってなされた発明を適用した実施形態について説明したが、本実施形態による本発明の開示の一部をなす記述および図面により本発明は限定されることはない。すなわち、本実施形態に基づいて当業者等によりなされる他の実施形態、実施例および運用技術等は全て本発明の範疇に含まれる。

１０ ＴＥ装置
１３ 通信制御部
１４ 記憶部
１４ａ ネットワークトポロジ情報
１４ｂ トラヒック情報データ
１５ 制御部
１５ａ 取得部
１５ｂ 前処理部
１５ｃ 経路計算部
１５ｄ 数理計算部

Claims (9)

1. ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得部と、
   経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算部と、
   経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する数理計算部と、
   を有し、
   前記経路計算部は、
   前記トラヒック内のフローをグルーピングしたフロー群を対象にして得られた前記線形計画問題の解に基づいて、各フローの経路を確定する
   ことを特徴とするトラヒックエンジニアリング装置。
2. ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得部と、
   経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算部と、
   経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する数理計算部と、
   を有し、
   前記経路計算部は、前記解のうちの実数解について、ダイクストラ法により経路を再度計算する
   ことを特徴とするトラヒックエンジニアリング装置。
3. 前記経路計算部は、各フローのトラヒック量の降順の合計がトラヒック総量に対して所定の割合を占める場合に、該フローを対象に、各フローの経路を計算することを特徴とする請求項１又は請求項２に記載のトラヒックエンジニアリング装置。
4. 前記トラヒック内のフローの情報から、経路変更を許容しないフローの情報を削除する前処理部をさらに有することを特徴とする請求項１又は請求項２に記載のトラヒックエンジニアリング装置。
5. 前記前処理部は、前記トラヒック内のフローの情報に、異なる時刻で取得されたトラヒック量の平均値、最大値または最小値の少なくともいずれかを含めることを特徴とする請求項４に記載のトラヒックエンジニアリング装置。
6. トラヒックエンジニアリング装置が実行するトラヒックエンジニアリング方法であって、
   ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得工程と、
   経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算工程と、
   経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する数理計算工程と、
   を含み、
   前記経路計算工程は、
   前記トラヒック内のフローをグルーピングしたフロー群を対象にして得られた前記線形計画問題の解に基づいて、各フローの経路を確定する
   ことを特徴とするトラヒックエンジニアリング方法。
7. トラヒックエンジニアリング装置が実行するトラヒックエンジニアリング方法であって、
   ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得工程と、
   経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算工程と、
   経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する数理計算工程と、
   を含み、
   前記経路計算工程は、前記解のうちの実数解について、ダイクストラ法により経路を再度計算する
   ことを特徴とするトラヒックエンジニアリング方法。
8. ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得ステップと、
   経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算ステップと、
   経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する数理計算ステップと、
   をコンピュータに実行させ、
   前記経路計算ステップは、
   前記トラヒック内のフローをグルーピングしたフロー群を対象にして得られた前記線形計画問題の解に基づいて、各フローの経路を確定する
   ことを特徴とするトラヒックエンジニアリングプログラム。
9. ネットワーク装置の接続形態を示す情報と、トラヒック内のフローの情報とを取得する取得ステップと、
   経路を変更するフローの数が最小となるように、各フローの経路を計算する経路計算ステップと、
   経路を変更するフローの数が最小となり、かつ、最大リンク利用率が最小となるように立式した線形計画問題の解を計算する数理計算ステップと、
   をコンピュータに実行させ、
   前記経路計算ステップは、前記解のうちの実数解について、ダイクストラ法により経路を再度計算する
   ことを特徴とするトラヒックエンジニアリングプログラム。