(57)【要約】【課題】冗長トラフィックの発生を減少させるためのルーティングポイントを動的に決定することができる動的ルーティングポイント設定装置および動的ルーティングポイント設定方法を提供する。【解決手段】動的ルーティングポイント設定装置１００は、トラフィック情報を収集するトラフィック情報収集部１１０と、収集した前記トラフィック情報をもとに、群知能の最適化手法を用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部１２０と、決定されたルーティングポイントをルータ１１に設定するルーティングポイント設定部１３０と、を備える。ルーティングポイント解析部１２０は、分離した問題空間の次元数を削減し、低次元の探索空間での探索後、標本から得られたビット状態を高次元の問題空間にマッピングする。【選択図】図１
2019004208.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの情報を収集し、冗長トラフィックの発生を減少させるルーティングポイントを動的に決定し、ネットワーク装置へ設定する動的ルーティングポイント設定装置であって、
ネットワーク内のルーティング機能を持つ装置からトラフィック情報を収集するトラフィック情報収集部と、
収集した前記トラフィック情報をもとに、群知能の最適化手法を用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部と、
決定された前記ルーティングポイントを前記ネットワーク装置に設定するルーティングポイント設定部と、を備える
ことを特徴とする動的ルーティングポイント設定装置。
【請求項２】
前記ルーティングポイント解析部は、
前記トラフィック情報収集部によって収集されたトラフィックの状況から評価関数を用いて冗長トラフィック発生度を評価し、この評価値をもとに、冗長トラフィックを低減するルーティングポイントを探索する
ことを特徴とする請求項１に記載の動的ルーティングポイント設定装置。
【請求項３】
前記ルーティングポイント解析部は、
前記群知能の最適化手法としてＰＳＯ（Particle Swarm Optimization）を用いて、問題空間と探索空間とを分離し、前記問題空間よりも次元数を削減した探索空間においてルーティングポイントの探索を行う
ことを特徴とする請求項１に記載の動的ルーティングポイント設定装置。
【請求項４】
前記ルーティングポイント解析部は、
高次元の前記問題空間を、写像関数を用いて低次元の探索空間に写像する
ことを特徴とする請求項３に記載の動的ルーティングポイント設定装置。
【請求項５】
前記ルーティングポイント解析部は、
高次元の前記問題空間を、三角関数で表される写像関数を用いて低次元の探索空間に写像し、
前記三角関数の中で、最適値を探索する
ことを特徴とする請求項３に記載の動的ルーティングポイント設定装置。
【請求項６】
前記ルーティングポイント解析部は、
低次元の探索空間での探索後、標本から得られたビット状態を高次元の前記問題空間にマッピングする
ことを特徴とする請求項３ないし５のいずれか一項に記載の動的ルーティングポイント設定装置。
【請求項７】
ネットワークの情報を収集し、冗長トラフィックの発生を減少させるルーティングポイントを動的に決定し、ネットワーク装置へ設定する動的ルーティングポイント設定方法であって、
ネットワーク内のルーティング機能を持つ装置からトラフィック情報を収集するトラフィック情報収集部と、
収集した前記トラフィック情報をもとに、ＰＳＯを用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部と、
決定された前記ルーティングポイントを前記ネットワーク装置に設定するルーティングポイント設定部と、を有し、
前記ルーティングポイント解析部は、
前記ルーティングポイントを探索する場合、前記ＰＳＯにおける問題空間と探索空間とを分離し、前記問題空間の次元数を削減し、前記問題空間よりも次元数を削減した探索空間においてルーティングポイントの探索を行い、
低次元の探索空間でのルーティングポイントの探索後、標本から得られたビット状態を高次元の前記問題空間にマッピングする
ことを特徴とする動的ルーティングポイント設定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的ルーティングポイント設定装置および動的ルーティングポイント設定方法に関する。
【背景技術】
【０００２】
大学・企業・研究所等の組織内ネットワークの構築には、ＶＬＡＮ（Virtual Local Area Network）技術が広く利用されている。ＶＬＡＮを利用することで、単一の物理ネットワーク上に複数の論理ネットワークを実現することができる。
しかしＶＬＡＮネットワーク中に、ルーティング機能を持つ機器が複数存在するネットワークでは、各論理ネットワークの中継点であるルータの配置によっては冗長トラフィックを多発させ、ネットワーク全体の効率を落とす可能性がある。
仮想化基盤の環境で、異なるＶＬＡＮネットワークに属する仮想マシン同士が通信を行う場合、余分な通信経路を通過する。仮想化基盤の仮想スイッチをレイヤ２からレイヤ３に置き換えたとしても、冗長トラフィックの発生は回避することができない。
【０００３】
非特許文献１には、群知能の一種であるＰＳＯ（Particle Swarm Optimization、粒子群最適化）を用いたルーティングポイント選定方式が公開されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】離散ＰＳＯを用いた分散仮想ルータのための動的中継点制御，高橋他，人工知能学会論文誌 26(1), 25-33, 2011［online］,［平成２６年６月１日検索］,インターネット  〈 URL : https://www.jstage.jst.go.jp/article/tjsai/26/1/26_1_25/_pdf〉
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１では、ルーティングポイントの選定方式については述べられているが、具体的なネットワーク装置への設定方法については述べられていない。また、ルーティングポイントの選定方式についても、対象とするネットワークの大規模化に対応できないといったスケーラビリティに対する課題がある。
【０００６】
このような背景を鑑みて本発明がなされたのであり、本発明は、冗長トラフィックの発生を減少させるためのルーティングポイントを動的に決定することができる動的ルーティングポイント設定装置および動的ルーティングポイント設定方法を提供することを課題とする。
【課題を解決するための手段】
【０００７】
前記した課題を解決するため、請求項１に記載の発明は、ネットワークの情報を収集し、冗長トラフィックの発生を減少させるルーティングポイントを動的に決定し、ネットワーク装置へ設定する動的ルーティングポイント設定装置であって、ネットワーク内のルーティング機能を持つ装置からトラフィック情報を収集するトラフィック情報収集部と、収集した前記トラフィック情報をもとに、群知能の最適化手法を用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部と、決定された前記ルーティングポイントを前記ネットワーク装置に設定するルーティングポイント設定部と、を備えることを特徴とする動的ルーティングポイント設定装置とした。
【０００８】
このようにすることで、ＶＬＡＮネットワーク中にルーティング機能を持つ機器が複数存在するネットワークにおいて、各機器の中継点であるルーティングポイントの配置によって発生し得る冗長トラフィックを減少させることができる。
【０００９】
また、請求項２に記載の発明は、前記ルーティングポイント解析部が、前記トラフィック情報収集部によって収集されたトラフィックの状況から評価関数を用いて冗長トラフィック発生度を評価し、この評価値をもとに、冗長トラフィックを低減するルーティングポイントを探索する。
【００１０】
このようにすることで、群知能の最適化手法を用いて冗長トラフィックを低減するルーティングポイントを探索することができる。
【００１１】
また、請求項３に記載の発明は、前記ルーティングポイント解析部が、前記群知能の最適化手法としてＰＳＯを用いて、問題空間と探索空間とを分離し、前記問題空間よりも次元数を削減した探索空間においてルーティングポイントの探索を行うことを特徴とする。
【００１２】
このようにすることで、問題空間と探索空間を分離させ、問題空間の次元数を削減することにより効率的な探索を実現することができる。対象とするネットワークの大規模化に対応でき、スケーラビリティを確保することができる。
【００１３】
また、請求項４に記載の発明は、前記ルーティングポイント解析部が、高次元の前記問題空間を、写像関数を用いて低次元の探索空間に写像することを特徴とする。
【００１４】
このようにすることで、問題空間の次元数を削減して、探索の方向を狭めることができ、効率的な探索を実現することができる。
【００１５】
また、請求項５に記載の発明は、前記ルーティングポイント解析部が、高次元の前記問題空間を、三角関数で表される写像関数を用いて低次元の探索空間に写像し、前記三角関数の中で、最適値を探索することを特徴とする。
【００１６】
このようにすることで、三角関数で表される写像関数を用いて問題空間の次元数を削減して探索の方向を狭めることができる。三角関数の中で、最適値を探索することで、比較的小さい演算資源で効率的な探索を実現することができる。
【００１７】
また、請求項６に記載の発明は、前記ルーティングポイント解析部が、低次元の探索空間での探索後、標本から得られたビット状態を高次元の前記問題空間にマッピングすることを特徴とする。
【００１８】
このようにすることで、低次元から高次元の問題空間に戻すことができ、高次元の問題空間に戻された後には、通常のＰＳＯまたは離散ＰＳＯを含む群知能の最適化手法を用いて冗長トラフィックを低減するルーティングポイントを探索することができる。
【００１９】
また、請求項７に記載の発明は、ネットワークの情報を収集し、冗長トラフィックの発生を減少させるルーティングポイントを動的に決定し、ネットワーク装置へ設定する動的ルーティングポイント設定方法であって、ネットワーク内のルーティング機能を持つ装置からトラフィック情報を収集するトラフィック情報収集部と、収集した前記トラフィック情報をもとに、ＰＳＯを用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部と、決定された前記ルーティングポイントを前記ネットワーク装置に設定するルーティングポイント設定部と、を有し、前記ルーティングポイント解析部は、前記ルーティングポイントを探索する場合、前記ＰＳＯにおける問題空間と探索空間とを分離し、前記問題空間の次元数を削減し、前記問題空間よりも次元数を削減した探索空間においてルーティングポイントの探索を行い、低次元の探索空間でのルーティングポイントの探索後、標本から得られたビット状態を高次元の前記問題空間にマッピングすることを特徴とする動的ルーティングポイント設定方法とした。
【００２０】
このようにすることで、ＰＳＯにおける問題空間と探索空間を分離させ、問題空間の次元数を削減することにより効率的な探索を実現することができる。ＶＬＡＮネットワーク中にルーティング機能を持つ機器が複数存在するネットワークにおいて、各機器の中継点であるルーティングポイントの配置によって発生し得る冗長トラフィックを減少させることができる。対象とするネットワークの大規模化に対応でき、スケーラビリティを確保することができる。
【発明の効果】
【００２１】
本発明によれば、冗長トラフィックの発生を減少させるためのルーティングポイントを動的に決定することができる動的ルーティングポイント設定装置および動的ルーティングポイント設定方法を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施形態に係る動的ルーティングポイント設定装置を示す構成図である。
【図２】本発明の実施形態に係る動的ルーティングポイント設定装置の動作を示すフローチャートである。
【図３】本発明の実施形態に係る動的ルーティングポイント設定装置の問題空間と探索空間を分離し、問題空間の次元数を削減する状態を示す状態遷移図である。
【図４】本発明の実施形態に係る動的ルーティングポイント設定装置の解の表現方法を説明する図である。
【図５】本発明の実施形態に係る動的ルーティングポイント設定装置の問題空間を写像関数ｇ（ｘ）で写像し直したことを示す図である。
【図６】冗長トラフィックが発生する課題を説明する図であり、（ａ）はルータ２にルーティングポイントを設定した場合、（ｂ）はルータ１にルーティングポイントを設定した場合を示す図である。
【図７】ＰＳＯの最適化手法を説明する図であり、（ａ）は探索空間におけるノードのイメージ図、（ｂ）は（ａ）の矢印で示される探索を繰り返して最適解に近づくことを示すイメージ図である。
【図８】離散ＰＳＯを用いた動的中継点制御の実験結果を示す図である。
【図９】離散ＰＳＯを用いた動的中継点制御の課題を説明する図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明を実施するための形態（以下、「本実施形態」という）における動的ルーティングポイント設定装置等について説明する。
（背景説明）
動的ルーティングポイント設定において、対象とするネットワークは、ＶＬＡＮ等のＬ２レイヤでの仮想化技術を用いて構築されているネットワークである。仮想化技術を用いて構築されているネットワークは、同一ＶＬＡＮが複数拠点に跨って存在し、ルーティング機能を持つ装置（機器）が複数存在する。ＶＬＡＮネットワーク中にルーティング機能を持つ装置が複数存在する場合、各論理ネットワークの中継点であるルータの配置によっては冗長トラフィックが多発し、ネットワーク全体の効率を落とす可能性がある。
【００２４】
図６は、ルーティングポイントの配置によって冗長トラフィックが発生する課題を説明する図であり、（ａ）はルータ２にルーティングポイントを設定した場合、（ｂ）はルータ１にルーティングポイントを設定した場合を示す。
図６に示すネットワークは、ＶＬＡＮネットワーク中にルーティング機能を持つ装置が複数存在する物理ネットワークである。
図６に示す物理ネットワークには、ルータ１１１〜１１４と、ＶＬＡＮ２１ａ２，ＶＬＡＮ２１ｂ２，ＶＬＡＮ２１ａ３，ＶＬＡＮ２１ｂ３，ＶＬＡＮ２１ｃ３，ＶＬＡＮ２１ａ４，ＶＬＡＮ２１ｃ４と、が存在する。説明の便宜上、ルータ１１１はルータ１、ルータ１１２はルータ２、ルータ１１３はルータ３、ルータ１１４はルータ４と呼ぶ。このネットワーク上に３つのＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）（図６中、Ａ，Ｂ，Ｃ）があり、それぞれＶＬＡＮ２１ａ２，ＶＬＡＮ２１ａ３，ＶＬＡＮ２１ｃ４と、ＶＬＡＮ２１ｂ２，ＶＬＡＮ２１ｂ３と、ＶＬＡＮ２１ｃ３，ＶＬＡＮ２１ｃ４とする。ＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）は、エッジスイッチを構成するルータ１１２〜１１４に接続される。ＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）は、ルータ１１２〜１１４とコアスイッチを構成するルータ１１１を経由して接続される。
ルータ１〜４のいずれか１つに、各ＶＬＡＮの中継点であるルーティングポイントを配置できる。
【００２５】
図６の実線または破線矢印は、ＶＬＡＮ ＡからＶＬＡＮ Ｂへのトラフィックを表している。
図６（ａ）に示すように、ルータ２にルーティングポイント（中継点）を設定した場合、異なる拠点に存在するＶＬＡＮ ＡからＶＬＡＮ Ｂへの通信は、いずれもルータ２で中継され、トラフィック（図６の符号ａ参照）と、トラフィック（図６の符号ｂ参照）となる。このうち、太実線のトラフィック（図６の符号ａ参照）が冗長トラフィックとなる。
【００２６】
また、図６（ｂ）に示すように、ルータ１にルーティングポイント（中継点）を設定した場合、異なる拠点に存在するＶＬＡＮ ＡからＶＬＡＮ Ｂへのトラフィックは、いずれもルータ１で中継され、トラフィック（図６の符号ｃ参照）と、トラフィック（図６の符号ｄ参照）となる。このうち、太実線のトラフィック（図６の符号ｃ参照）は、ルータ１１１（コアスイッチ）経由となり冗長なパケットが発生する冗長トラフィックとなる。
【００２７】
ルーティングポイントは、１箇所のみしか設定できないため、必ず冗長トラフィックは発生してしまう。各論理ネットワークの中継点であるルータの配置によっては冗長トラフィックを多発させ、ネットワーク全体の効率を落とす可能性がある。
【００２８】
冗長トラフィックの発生を減少させるルーティングポイント選定方式として、非特許文献１が公開されている。
非特許文献１は、離散ＰＳＯを用いた分散仮想ルータのための動的中継点制御方法を提供する。まず、ＰＳＯの概要について述べ、次いで離散ＰＳＯを用いた分散仮想ルータとその課題について述べる。
【００２９】
<ＰＳＯを活用したルーティングポイント配置場所決定>
ＰＳＯは、群知能の一種である最適化手法であり、多数のノード（以下、エージェント）を探索空間に配置し、現在の状態と、自エージェントの探索履歴と、近隣エージェントの探索履歴とに基いて次状態を決定していく。結果的にエージェント群は、評価関数の最適解に近づくことになる。
具体的には以下の通りである。エージェントｉは、Ｄ次元空間で表現した現在の状態ｘｉ(→)（以下、ｘｉ(→)は、ｘｉのベクトルを示す）、ｉの履歴の中での最適状態ｐｉ(→)（以下、ｐｉ(→)は、ｐｉのベクトルを示す）、状態変位量ｖｉ(→)（以下、ｖｉ(→)は、ｖｉのベクトルを示す）の３つのベクトルで表記する。
【００３０】
現在の状態ｘｉ(→)は、探索空間における暫定解として考え、アルゴリズムの繰り返しにおいて評価関数を用いて評価する。もし、現在の状態ｘｉ(→)が探索履歴の中で最適評価値を得ることができれば、現在の状態ｘｉ(→)履歴の中での最適状態ｐｉ(→)として保存する。その評価値をpbestiという変数に保存する。
次に、各エージェントは、隣接関係にあるエージェントと互いの評価値Ｐiおよびpbestiを通信し合う。そして、隣接関係にあるエージェントの状態と比較し、それらの中で最適評価値となる解をｐｇ(→)（以下、ｐｇ(→)は、ｐｇのベクトルを示す）として保存する。最後に、現在の状態ｘｉ(→)に状態変位量ｖｉ(→)を加えることにより新たな解を選択する。現在の状態ｘｉ(→)の更新は、下記次状態決定式（１）で示される。
【数１】
2019004208.tif 000003
【００３１】
ここで、ｒ１，ｒ２は、一様分布乱数、ω，χ１，χ２は、定数であり、各要素の相対的影響を決定する。
【００３２】
図７は、ＰＳＯを説明する図であり、（ａ）は探索空間におけるノード（エージェント）のイメージ図、（ｂ）は（ａ）の矢印で示される探索を繰り返して最適解に近づくことを示すイメージ図である。
図７に示すように、ＰＳＯによる探索を繰り返すことで、最適解を発見することができる。
【００３３】
<離散ＰＳＯ>
標準的なＰＳＯは、連続空間を対象とした最適化手法である。離散空間を対象とした最適化問題を解くために、標準的なＰＳＯから派生した離散ＰＳＯを用いる。離散ＰＳＯは、エージェントの状態は０か１で構成されること、状態変位量は０か１を別の値に変化させる確率として表すこと、に特徴がある。上記式（１）で、各エージェントは状態変位量に従って次状態を決定する。しかし、離散ＰＳＯにおいて各エージェントの状態は２つのみであるため、状態変位量を状態変化確率と考え、状態変位量が大きいほど１になりやすく、小さいほど０になりやすいようにする。このため、状態変位量は、例えばジグモイド関数を用いて[０,１]に制限する。
【００３４】
<離散ＰＳＯを用いた動的中継点制御>
動的ルーティングポイント設定は、動的に変化するトラフィックを監視することによって、適切なルーティングポイントを設定し、ネットワーク内の冗長なパケットを削減することが目的である。離散ＰＳＯを、図６に示すようなＶＬＡＮの動的中継点問題に適用する。
前記非特許文献１では、ＰＳＯを用いたルーティングポイント選定手法が公開されている。前記非特許文献１で公開されているルーティングポイント選定手法は、下記、ステップＳ１〜Ｓ５を実行する。
【００３５】
ステップＳ１；全エージェントの状態をランダムとし、状態変位量を０で初期化する。
ステップＳ２；各エージェントの状態に対して、評価値を計算する。
ステップＳ３；最適値の更新を行う。
ステップＳ４；各エージェントの変位量と状態を上記式（１）に従って更新する。
ステップＳ５；環境の変化を検知した場合、上記ステップＳ１に、そうでなければ上記ステップＳ２に戻る。
【００３６】
図８は、離散ＰＳＯを用いた動的中継点制御の実験結果を示す図である。横軸にステップ（時間）、縦軸に冗長トラフィック発生率をとる。ルーティングポイントの移動間隔は、１８００ステップ（３０分）とした。評価指標は、ルーティングポイントを移動させてから、次に移動させるまでの時間（１８００ステップ）における冗長トラフィック発生率とした。また、６０ステップ毎に１０世代進化を行うＰＳＯ１（図８太破線参照）と、６０ステップ毎に５０世代進化を行うＰＳＯ２（図８細破線参照）との２種類を使用した。
図８の符号ｅ，ｆに示すように、ＰＳＯ１とＰＳＯ２では、トラフィックパターン変更後は、冗長トラフィック発生率が高い。しかし、学習によって冗長トラフィック発生率の発生が徐々に削減され（図８の符号ｇ，ｈ参照）、環境が変化した場合でも追従できていることが分かる。このように、離散ＰＳＯを用いた動的中継点制御により、動的に冗長トラフィックを削減するようなルーティングポイントが選定できることが実験結果として示されている。
【００３７】
なお、図８のＣｏｒｅ（図８太実線参照）およびＥｄｇｅ（図８細実線参照）は、比較例として、ＰＳＯを用いない設計者による中継点設定である。図８に示すように、Ｃｏｒｅ（図８太実線参照）は、Ｒａｎｄに最適化されて設定されているので、トラフィックパターン変更がない場合には、冗長トラフィック発生率は低い。しかし、トラフィックパターン変更後には、冗長トラフィック発生率は急激に高くなり、学習もされないので冗長トラフィック発生率は高いままである。Ｅｄｇｅ（図８太実線参照）は、特定のルータ配下での折り返しトラフィック量が多いモデル対応の特定６に最適化されて設定されているので、その場合には、冗長トラフィック発生率は低い。しかし、トラフィックパターン変更後には、冗長トラフィック発生率は急激に高くなり、学習もされないので冗長トラフィック発生率は高いままである。この場合、逆にＣｏｒｅ（図８太実線参照）の冗長トラフィック発生率は低くなる。
【００３８】
<離散ＰＳＯを用いた動的中継点制御の課題>
図９は、離散ＰＳＯを用いた動的中継点制御の課題を説明する図である。横軸にルータ数、縦軸に適切なルーティングポイントを設定できる確率をとる。
離散ＰＳＯは、エージェントの状態は０か１で構成され、状態変位量は０か１を別の値に変化させる確率として表される。このため、エージェント（ここではノード；ルータ）が増えると、状態変化確率は小さくなる。例えば、図９の破線に示すように、ルータ数が４の場合、状態変化確率が約０．５であるエージェントが選ばれる。ルータ数が１０の場合、状態変化確率が約０．２であるエージェントが選ばれる（図９の実線は選ばれなかったエージェント）、同様に、ルータ数が３０の場合、状態変化確率が約０．０７であるエージェントが選ばれる。このように、状態変化確率が小さくなると、選ばれたエージェントの確からしさ（確度）が減少する。
図９に示すように、対象とするネットワーク大規模化により、適切なルーティングポイントを設定できる確率が減少する。離散ＰＳＯを用いた動的中継点制御では、対象とするネットワークの大規模化に対応できないといったスケーラビリティに対する課題が存在する。
【００３９】
（実施形態）
図１は、本発明の実施形態に係る動的ルーティングポイント設定装置を示す構成図である。図６と同一構成部分には同一符号を付している。
図１に示す物理ネットワークには、ルータ１１１〜１１４と、ＶＬＡＮ２１ａ２，ＶＬＡＮ２１ｂ２，ＶＬＡＮ２１ａ３，ＶＬＡＮ２１ｂ３，ＶＬＡＮ２１ｃ３，ＶＬＡＮ２１ａ４，ＶＬＡＮ２１ｃ４と、が存在する。説明の便宜上、ルータ１１１はルータ１、ルータ１１２はルータ２、ルータ１１３はルータ３、ルータ１１４はルータ４と呼ぶ。
このネットワーク上に３つのＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）（図１中、Ａ，Ｂ，Ｃ）があり、それぞれＶＬＡＮ２１ａ２，ＶＬＡＮ２１ａ３，ＶＬＡＮ２１ｃ４と、ＶＬＡＮ２１ｂ２，ＶＬＡＮ２１ｂ３と、ＶＬＡＮ２１ｃ３，ＶＬＡＮ２１ｃ４とする。ＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）は、エッジスイッチを構成するルータ１１２〜１１４に接続される。ＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）は、ルータ１１２〜１１４とコアスイッチを構成するルータ１１１を経由して接続される。
ルータ１〜４のいずれか１つに、各ＶＬＡＮの中継点であるルーティングポイントを配置できる。
【００４０】
動的ルーティングポイント設定装置１００は、ルーティング機能を持つ機器が複数存在する上記ネットワークの情報を収集し、冗長トラフィックの発生を減少させるルーティングポイントを動的に決定し、ネットワーク装置へ設定する。
図１に示すように、動的ルーティングポイント設定装置１００は、ＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）（ネットワーク内のルーティング機能を持つ装置）から一定間隔でトラフィック情報を収集するトラフィック情報収集部１１０と、収集した前記トラフィック情報をもとに、群知能の最適化手法を用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部１２０と、決定されたルーティングポイントをルータ１１（ネットワーク装置）に設定するルーティングポイント設定部１３０と、を備える。
【００４１】
<トラフィック情報収集部１１０>
トラフィック情報収集部１１０は、Ｌ２レイヤでの仮想化技術を用いたネットワークを対象としてトラフィック情報を収集する。
【００４２】
<ルーティングポイント解析部１２０>
ルーティングポイント解析部１２０は、トラフィック情報収集部１１０によって収集されたトラフィックの状況から評価関数を用いて冗長トラフィック発生度を評価し、この評価値をもとに、冗長トラフィックを低減させるためのルーティングポイントを探索する。
ルーティングポイント解析部１２０は、ルーティングポイントを探索する場合、群知能の最適化手法における問題空間と探索空間とを分離し、分離した問題空間の次元数を削減する。
【００４３】
ルーティングポイント解析部１２０は、高次元の問題空間を、写像関数ｇ(x)を用いて低次元の探索空間に写像する。
ルーティングポイント解析部１２０は、高次元の問題空間を、三角関数で表される写像関数ｇ(x)を用いて低次元の探索空間に写像し、三角関数の中で、最適値を探索する。
ルーティングポイント解析部１２０は、低次元の探索空間での探索後、標本から得られたビット状態を高次元の問題空間にマッピングする。冗長トラフィックを低減させるためのルーティングポイントの探索においては、離散ＰＳＯを用いる。
【００４４】
<ルーティングポイント設定部１３０>
ルーティングポイント設定部１３０は、動的に決定されたルーティングポイントを、ルータ１１（ネットワーク装置）へ設定する。
【００４５】
以下、上述のように構成された動的ルーティングポイント設定装置１００の動作を説明する。
図２は、動的ルーティングポイント設定装置の動作を示すフローチャートである。また、トラフィック情報収集部１１０、ルーティングポイント解析部１２０およびルーティングポイント設定部１３０間の信号のやり取り（横方向の矢印参照）を示すことで、制御シーケンス図としての説明を兼ねる。
動的ルーティングポイント設定装置１００は、図２のフローを実行することで、ルーティングポイント配置場所を決定する。
まず、ステップＳ１０で対象とするネットワークの状態を定義し、トラフィック情報収集部１１０、ルーティングポイント解析部１２０およびルーティングポイント設定部１３０に通知する。ルーティングポイントはランダム配置とする。
【００４６】
<トラフィック情報収集部１１０の動作>
まず、トラフィック情報収集部１１０の動作について述べる。
ステップＳ１１でトラフィック情報収集部１１０は、対象装置からトラフィック情報を収集する。対象装置は、図１のＶＬＡＮ（ＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）（ネットワーク内のルーティング機能を持つ装置）である。
ステップＳ１２でトラフィック情報収集部１１０は、収集したトラフィック情報を保存する。
ここで、トラフィック情報収集部１１０は、ルーティングポイント解析部１２０からトラフィック情報要求を受付け、収集したトラフィック情報をルーティングポイント解析部１２０に送信する（ステップＳ５１参照）。
ステップＳ１３でトラフィック情報収集部１１０は、対象装置（図１のＶＬＡＮ Ａ，ＶＬＡＮ Ｂ，ＶＬＡＮ Ｃ）に変化があるかないかを確認する。対象装置に変化がない場合は、上記ステップＳ１１に戻り、対象装置に変化がある場合は、ステップＳ１４に進む。
ステップＳ１４でトラフィック情報収集部１１０は、対象装置を更新して上記ステップＳ１１に戻る。
【００４７】
<ルーティングポイント解析部１２０の動作>
次に、ルーティングポイント解析部１２０の動作について述べる。
ステップＳ２１でルーティングポイント解析部１２０は、全ノード状態を初期化する。また、ルーティングポイント解析部１２０は、ルーティングポイント設定部１３０からルーティングポイント配置場所情報取得要求を受付け、取得しているルーティングポイント配置場所情報をルーティングポイント設定部１３０に送信する（ステップＳ５２参照）。
ステップＳ２２でルーティングポイント解析部１２０は、トラフィック情報収集部１１０からトラフィック情報を取得する。具体的には、ルーティングポイント解析部１２０は、トラフィック情報収集部１１０に対しトラフィック情報要求を発行し（ステップＳ５１参照）、トラフィック情報収集部１１０からトラフィック情報収集部１１０が収集したトラフィック情報を受信する。
【００４８】
ステップＳ２３でルーティングポイント解析部１２０は、各ノードの評価値を算出する。評価値算出は、本動的ルーティングポイント設定の技術的特徴部分であり、詳細は後記する。
ステップＳ２４でルーティングポイント解析部１２０は、最適ルーティングポイント配置場所の更新を行う。
ステップＳ２５でルーティングポイント解析部１２０は、算出された各ノードの評価値をもとに、各ノードの状態を更新して上記ステップＳ２２に戻る。
【００４９】
<ルーティングポイント設定部１３０の動作>
次に、ルーティングポイント設定部１３０の動作について述べる。
ステップＳ３１でルーティングポイント設定部１３０は、最新のルーティングポイント配置場所情報を取得する。ルーティングポイント設定部１３０は、ルーティングポイント解析部１２０に対しルーティングポイント配置場所情報要求を発行し、ルーティングポイント解析部１２０が保持する最新のルーティングポイント配置場所情報を受信する（ステップＳ５１参照）。
ステップＳ３２でルーティングポイント設定部１３０は、現状のルーティングポイント配置場所との差分を確認する。
現状のルーティングポイント配置場所に差分がない場合は、上記ステップＳ３１に戻り、現状のルーティングポイント配置場所に差分がある場合は、ステップＳ３３に進む。
ステップＳ３３でルーティングポイント設定部１３０は、ルーティングポイント配置場所差分をもとに、ルータ１１（ネットワーク装置）に対してルーティングポイントを再設定して上記ステップＳ３１に戻る。
【００５０】
［離散ＰＳＯを活用したルーティングポイント配置場所決定］
次に、離散ＰＳＯを活用したルーティングポイント配置場所決定について説明する。
<原理説明>
ＰＳＯでは、問題空間が増えれば増えるほど高次元になる。離散ＰＳＯでないＰＳＯの場合は、連続値で値をとれるのに対し、離散ＰＳＯは、状態変位量は０か１である。このため、問題空間が増えて高次元になった場合、状態変化確率が小さくなる影響を著しく受け（前記図９参照）、選ばれたエージェントの確からしさが減少する。
本発明者らは、探索にあたって、問題空間と探索空間を分離させ、問題空間の次元数を削減することでスケーラビリティを確保する着想を得た。具体的には、写像関数ｇ(x)を用いて別の問題空間に写像し直して探索空間の次元数を削減し、探索の方向を狭めることで探索効率を高める。低次元空間で探索をした後、標本から得られたビット状態を高次元の問題空間にマッピングする。
【００５１】
図３は、問題空間と探索空間を分離し、問題空間の次元数を削減する状態を示す状態遷移図である。
ノード（エージェント）ｉは、
Ｄ次元空間で表現した問題空間の状態（内部状態）：ｘｉ(→)
写像関数：ｇ(x)
標本：ｘ(￣)＝{ｂc}１≦ｃ≦bitnum
探索空間の状態（外部状態）：ｘｉ(→)′
で表記する。
【００５２】
図３に示すように、問題空間が離散空間である際に、問題空間と探索空間を分離させる。そして、次式（２）に従って、写像関数ｇ（ｘ）を用いて問題空間の次元数を削減する。
【数２】
2019004208.tif 000004
【００５３】
図３に示すように、写像関数ｇ(x)を低次元関数とすることで、探索空間の次元数を削減する（後記）。
図３に示すように、標本から得られたビット状態を高次元の問題空間にマッピングする（後記）。
【００５４】
［ルーティングポイント解析部１２０の動作の具体例］
以下、<解の表現方法>〜<ノードｉの外部状態>は、図２のルーティングポイント解析部１２０の全ノード状態を初期化（ステップＳ２１）で実行される。
【００５５】
<解の表現方法>
図４は、解の表現方法を説明する図である。図１と同一構成部分には同一符号を付している。
図４に示すように、解を求めるネットワークは、ルータ１１０〜１１０と、各ＶＬＡＮ２１ａ〜２１ｃと、が存在する。説明の便宜上、ルータ１１０はルータ０、ルータ１１１はルータ１、ルータ１１２はルータ２、ルータ１１３はルータ３と呼ぶ。ＶＬＡＮ２１ａはＡ、ＶＬＡＮ２１bはＢ、ＶＬＡＮ２１ｃはＣを示す。
解Ｓは、次式（３）で示される。
【数３】
2019004208.tif 000005
【００５６】
<ノードｉの内部状態>
ノードｉの内部状態について述べる。
ノードｉの内部状態は、次式（４）で示される。
【数４】
2019004208.tif 000006
【００５７】
例えば、式（４）の枠で囲んだ行の右の、ｌｏｇ２Ｎｅｒは、Ｎｅｒが４の場合、ｌｏｇ２４は、２である。ｌｏｇ２Ｎｅｒは、天井関数（ceiling function）を用いて、実数に対しそれ以下の最小の整数を対応付ける。
ノードｉの内部状態の具体例は下記の通りである。
ノード（エージェント）ｉは、問題空間の次元が２次元空間であるとき、ノードｉの内部状態は、次式（５）で示される。式（５）の行は、問題空間の次元を示しており、エージェント（ノード；ルータ）の数が増えると、式（５）の行数が増えて高次元となる。
【数５】
2019004208.tif 000007
【００５８】
また、Ｓｉは、次式（６）で示される。
【数６】
2019004208.tif 000008
【００５９】
式（６）は、解の値がルータの数より大きくならないように制限をかけるための計算式である。
式（６）中、（００）２，（００）２，（１１）２は、２進数の状態であること表す。
Ｎｅｒは、ルータの数である。
例えば、Ｎｅｒが４の場合、（００）２は、ｍｏｄ  Ｎｅｒは、０を４で割った余りを表し、ここでは０である。次の、（１０）２は、１０進数に戻すと２であり、（１０）２ｍｏｄ  Ｎｅｒは、２を４で割った余りは２である。次の、（１１）２は、１０進数に戻すと３であり、（１１）２ｍｏｄ  Ｎｅｒは、３を４で割った余りは３である。この場合、Ｓi＝{０，２，３}が解になる。
【００６０】
<ノードｉの外部状態>
ノードｉの探索空間の状態（外部状態）について述べる。
ノードｉの外部状態は、写像関数ｇ(x)、外部状態ｘｉ(→)′、標本ｘ(￣)で表記される。
写像関数ｇ(x)は、次式（７）のような三角関数で示される。式（７）は一例であり、三角関数はどのようなものでもよい。
外部状態ｘｉ(→)′は、次式（８）で示される。
標本ｘ(￣)は、次式（９）で示される。
【数７】
2019004208.tif 000009
【００６１】
上記式（７）〜（９）について説明する。
上記式（７）は、ルータの数だけあった問題空間を、写像関数ｇ（ｘ）により定義し直し、三角関数で示されるａ，ｂ，ｃに写像し直している（式（７）中の○囲み参照）。すなわち、非特許文献１では、ルータの数だけあった問題空間で、それぞれの問題空間で最も高い確率を求めて、その中か１つ選んでいた。本実施形態では、この探索をやめて、次元数を減らすことで、探索の方向を狭めることで探索効率を高める。写像関数ｇ（ｘ）のａ，ｂ，ｃの三角関数の中で、最適な値を探すことにした。
上記式（８）は、上記ａ，ｂ，ｃから求められる外部状態ｘｉ(→)′である。
上記式（９）は、写像関数ｇ（ｘ）から値をサンプリングする標本の一例である。三角関数は波なので、何処の点をサンプリングしてもよい。例えば、整数値「−３」「−２」「１」…を標本とする。
【００６２】
<ノードｉの外部状態の具体例>
ノードｉの外部状態の具体例について述べる。
<ノードｉの外部状態の具体例>は、図２のルーティングポイント解析部１２０の各ノードの評価値を算出（ステップＳ２３）で実行される。
ノードｉは、２次元空間であるとき、環境中のＶＬＡＮ数ＮＶＬＡＮ：３、ルータ数Ｎｅｒ：４の場合、下記の通りである。
上述したように、前記式（４）の枠で囲んだ行の右の、ｌｏｇ２Ｎｅｒは、Ｎｅｒが４の場合、ｌｏｇ２４は、２である。ＶＬＡＮ数ＮＶＬＡＮは、３であるから、標本の数bitnumは、次式（１０）で示され、bitnum＝２×３＝６である。
【数８】
2019004208.tif 000010
【００６３】
標本ｘ(￣)は、前記式（９）で示される。
前記式（９）に、上記bitnum＝６を代入すると、標本ｘ(￣)は、式（１１）で示される。ここでは、標本ｘ(￣)は、整数６ビットである。
【００６４】
外部状態：ｘｉ(→)′は、式（１２）で与えられるとする。ここでは、３次元空間であった場合に、エージェントはａ軸，ｂ軸，ｃ軸の点で表される。
【００６５】
写像関数ｇ(x)は、前記式（７）で示され、式（７）中の丸で囲んだａ，ｂ，ｃに、上記式（１２）のｘｉ(→)′の[ａ，ｂ，ｃ]＝[２．２９，０．４７，１．８９]を当てはめると、式（１３）で示される。
上記式（１３）に示すｇ(x)を算出するまでが、写像関数ｇ(x)で、探索空間の次元数削減に対応する（図３参照）。
【００６６】
図５は、ルータの数だけあった問題空間を、写像関数ｇ（ｘ）で三角関数のａ，ｂ，ｃに写像し直したことを示す図である。図５は、上記式（１３）で記述される三角関数であるｇ(x)を示し、横軸は三角関数の周期である。ここでは、横軸上の整数値を標本とし、ここでは６ビットである。
【００６７】
次に、標本から得られたビット状態を高次元の問題空間にマッピングする（図３参照）。
具体的には、写像を用いて低次元化した図５に示す写像関数ｇ(x)をもとに、ｇ(x)からｘ(￣)＝{−３，−２，−１，０，１，２}の標本をとり、ノードｉの内部状態Ｘｉを算出する。ここでは、図５に示すｇ(x)が、ｘ(￣)でサンプリングされる。この点は、図５の黒丸で示した値が求められ、次式（１４）となる。ｇ(x)から標本ｘ(￣)＝{−３，−２，−１，０，１，２}をとり、ノードｉの内部状態Ｘｉを算出する計算が、標本から得られたビット状態を高次元の問題空間にマッピングに対応する。
Ｘｉ＝{{００}，{１０}，{１１}}      …（１４）
【００６８】
具体的に説明する。
図５に示す写像関数ｇ(x)において、１番目の標本「−３」のｇ(x)は、負であるため、Ｘｉの第１状態の対の一方は０となる（図５の符号ｋ参照）。１番目の標本「−２」のｇ(x)は、負であるため、Ｘｉの第１状態の対の他方は０となる（図５の符号ｌ参照）。２番目の標本「−１」のｇ(x)は、正であるため、Ｘｉの第２状態の対の一方は１となる（図５の符号ｍ参照）。２番目の標本「０」のｇ(x)は、負であるため、Ｘｉの第２状態の対の他方は０となる（図５の符号ｎ参照）。３番目の標本「１」のｇ(x)は、正であるため、Ｘｉの第３状態の対の一方は１となる（図５の符号ｏ参照）。３番目の標本「２」のｇ(x)は、正であるため、Ｘｉの第３状態の対の他方は１となる（図５の符号ｐ参照）。
なお、高次元化に戻す時も写像と呼ぶ。
【００６９】
<評価値>
評価値について述べる。
<評価値>は、図２のルーティングポイント解析部１２０の各ノードの評価値を算出（ステップＳ２３）で実行される。
評価値は、冗長フローの割合であり、次式（１５）で示される。評価値は、トラフィックの全フロー数に対して冗長フロー数がどれだけあるかを示す。前記図８に示すように、冗長フロー数が少ないほど評価値は高い。
【数９】
2019004208.tif 000011
【００７０】
<最適値の更新>
最適値の更新について述べる。
<最適値の更新>は、図２のルーティングポイント解析部１２０の最適ルーティングポイント配置場所の更新（ステップＳ２４）で実行される。
red(Xi)がred(Pi)よりも最適値である場合、次式（１６）で更新する。
Ｐi ←Ｘi      …（１６）
【００７１】
隣接エージェントの探索履歴の中での最適値も次式（１７）で更新する。
Ｐg ←Ｐj      …（１７）
【００７２】
<次状態の決定>
最適値の更新について述べる。
<次状態の決定>は、図２のルーティングポイント解析部１２０の各ノードの状態を更新（ステップＳ２５）で実行される。
次状態の決定は、前記式（１）を用いて決定する。
【００７３】
以上説明したように、本実施形態に係る動的ルーティングポイント設定装置１００は、ネットワーク内のルーティング機能を持つ装置からトラフィック情報を収集するトラフィック情報収集部１１０と、収集した前記トラフィック情報をもとに、群知能の最適化手法を用いて、冗長トラフィックを低減するルーティングポイントを探索し、当該ルーティングポイントを決定するルーティングポイント解析部１２０と、決定されたルーティングポイントをルータ１１に設定するルーティングポイント設定部１３０と、を備える。
ルーティングポイント解析部１２０は、ルーティングポイントを探索する場合、群知能の最適化手法における問題空間と探索空間とを分離し、分離した問題空間の次元数を削減し、低次元の探索空間での探索後、標本から得られたビット状態を高次元の問題空間にマッピングする。
【００７４】
これにより、ＶＬＡＮネットワーク中にルーティング機能を持つ機器が複数存在するネットワークにおいて、各ＶＬＡＮの中継点であるルーティングポイントの配置によって発生し得る冗長トラフィックを減少させることができる。
【００７５】
また、ルーティングポイント解析部１２０は、設定された評価関数を用いて収集されたトラフィックの状況から冗長トラフィック発生度を評価し、評価値をもとに、冗長トラフィックを低減するルーティングポイントを探索する。これにより、通常のＰＳＯまたは離散ＰＳＯを含む群知能の最適化手法を用いて冗長トラフィックを低減するルーティングポイントを探索することができる。
【００７６】
また、ルーティングポイント解析部１２０は、ルーティングポイントを探索する場合、群知能の最適化手法における問題空間と探索空間とを分離し、分離した問題空間の次元数を削減する。これにより、問題空間と探索空間を分離させ、問題空間の次元数を削減することにより効率的な探索を実現することができる。対象とするネットワークの大規模化に対応でき、スケーラビリティを確保することができる。
【００７７】
また、ルーティングポイント解析部１２０は、高次元の問題空間を、写像関数ｇ(x)を用いて低次元の探索空間に写像する。写像関数ｇ(x)を用いて問題空間の次元数を削減することで、探索の方向を狭めることができ、効率的な探索を実現することができる。
特に、ルーティングポイント解析部１２０は、高次元の問題空間を、三角関数で表される写像関数ｇ(x)を用いて低次元の探索空間に写像し、三角関数の中で、最適値を探索する。これにより、三角関数で表される写像関数ｇ(x)を用いて問題空間の次元数を削減して探索の方向を狭めることができる。三角関数の中で、最適値を探索することで、比較的小さい演算資源で効率的な探索を実現することができる。
【００７８】
また、ルーティングポイント解析部１２０は、低次元の探索空間での探索後、標本から得られたビット状態を高次元の問題空間にマッピングするので、低次元から高次元の問題空間に戻すことができ、高次元の問題空間に戻された後には、通常のＰＳＯまたは離散ＰＳＯを含む群知能の最適化手法を用いて冗長トラフィックを低減するルーティングポイントを探索することができる。
【００７９】
なお、上記実施形態において群知能の一種である最適化手法として、ＰＳＯを用いているが、群知能の一種である最適化手法を用いるものであればどのようなものでもよい。このような群知能の一種である最適化手法として、例えばアントコロニー最適化手法（Ant Colony Optimization,ACO）やカッコウ探索（Cuckoo search,CS）に適用が可能である。
【００８０】
また、上記実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述文書中や図面中に示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００８１】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部または全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行するためのソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、または、ＩＣ（Integrated Circuit）カード、ＳＤ（Secure Digital）カード、光ディスク等の記録媒体に保持することができる。
【符号の説明】
【００８２】
１１，１１０〜１１４  ルータ（ネットワーク装置）
２１ａ２，２１ｂ２，２１ａ３，２１ｂ３，２１ｃ３，２１ａ４，２１ｃ４  ＶＬＡＮ（ネットワーク内のルーティング機能を持つ装置）
１００  動的ルーティングポイント設定装置
１１０  トラフィック情報収集部
１２０  ルーティングポイント解析部
１３０  ルーティングポイント設定部
【図１】
2019004208.tif 000012
【図２】
2019004208.tif 000013
【図３】
2019004208.tif 000014
【図４】
2019004208.tif 000015
【図５】
2019004208.tif 000016
【図６】
2019004208.tif 000017
【図７】
2019004208.tif 000018
【図８】
2019004208.tif 000019
【図９】
2019004208.tif 000020