(57)【要約】【課題】ＳＤＮにおいて複数のコントローラを使用する場合に、適切なネットワーク構成の候補を発見できる設計装置、設計方法及び設計プログラムを提供すること。【解決手段】設計装置１は、ネットワーク構成の候補集合の初期状態をランダムに生成する初期化部１１と、候補集合の要素それぞれを、適応度の指標により評価する評価部１２と、候補集合の要素のうち、評価部による評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ評価部による評価が下位の候補を候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新部１３と、集合更新部１３による更新を、所定の条件を満たすまで繰り返した後、候補集合における評価部１２による評価が所定以上の部分集合を出力する出力部１４と、を備える。【選択図】図１
2019102919.tif 000002
【特許請求の範囲】
【請求項１】
ＳＤＮ（Ｓｏｆｔｗａｒｅ  Ｄｅｆｉｎｅｄ  Ｎｅｔｗｏｒｋ）における複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及び当該サブグラフの前記コントローラへの割り当てを定義したネットワーク構成を生成する設計装置であって、
前記ネットワーク構成の候補集合の初期状態をランダムに生成する初期化部と、
前記候補集合の要素それぞれを、適応度の指標により評価する評価部と、
前記候補集合の要素のうち、前記評価部による評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ前記評価部による評価が下位の候補を前記候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新部と、
前記集合更新部による更新を、所定の条件を満たすまで繰り返した後、前記候補集合における前記評価部による評価が所定以上の部分集合を出力する出力部と、を備える設計装置。
【請求項２】
前記集合更新部は、前記遺伝的オペレータとして、前記サブグラフの前記コントローラへの割り当て先の変更を含む交叉処理、及び前記サブグラフへの分割パターンの変更を含む突然変異処理を、それぞれ所定の確率で実行する請求項１に記載の設計装置。
【請求項３】
前記評価部は、複数の前記指標に基づくパレートフロント内において、前記指標それぞれに所定の重み付けをすることで前記適応度の順位付けを行う請求項１又は請求項２に記載の設計装置。
【請求項４】
前記評価部は、前記指標として、前記コントローラの数、前記コントローラ間の負荷分散、前記コントローラ間の通信遅延の少なくともいずれかを用いる請求項１から請求項３のいずれかに記載の設計装置。
【請求項５】
ＳＤＮにおける複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及び当該サブグラフの前記コントローラへの割り当てを定義したネットワーク構成をコンピュータが生成する設計方法であって、
前記ネットワーク構成の候補集合の初期状態をランダムに生成する初期化ステップと、
前記候補集合の要素それぞれを、適応度の指標により評価する評価ステップと、
前記候補集合の要素のうち、前記評価ステップによる評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ前記評価ステップによる評価が下位の候補を前記候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新ステップと、
前記集合更新ステップによる更新を、所定の条件を満たすまで繰り返した後、前記候補集合における前記評価ステップによる評価が所定以上の部分集合を出力する出力ステップと、を実行する設計方法。
【請求項６】
ＳＤＮにおける複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及び当該サブグラフの前記コントローラへの割り当てを定義したネットワーク構成をコンピュータに生成させるための設計プログラムであって、
前記ネットワーク構成の候補集合の初期状態をランダムに生成する初期化ステップと、
前記候補集合の要素それぞれを、適応度の指標により評価する評価ステップと、
前記候補集合の要素のうち、前記評価ステップによる評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ前記評価ステップによる評価が下位の候補を前記候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新ステップと、
前記集合更新ステップによる更新を、所定の条件を満たすまで繰り返した後、前記候補集合における前記評価ステップによる評価が所定以上の部分集合を出力する出力ステップと、を実行させるための設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＳＤＮ（Ｓｏｆｔｗａｒｅ  Ｄｅｆｉｎｅｄ  Ｎｅｔｗｏｒｋ）におけるネットワーク構成を設計するための装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、ＳＤＮと呼ばれるネットワークが研究されている。ＳＤＮは、ユーザの要求が変化するにつれて、低コストでネットワーク構成を容易に変更できる利点を有している。ＳＤＮは、パケットを転送するデータプレーンと、パケットの転送方法を決定する制御プレーンとが分離され、制御プレーンは、集中コントローラによって実行される。
【０００３】
単一の集中コントローラがネットワーク全体を管理する場合、スケーラビリティ、可用性及びセキュリティに課題がある。このため、ネットワークを複数のユニット（ドメイン）に分割し、複数のコントローラが協調してネットワークを管理することが提案されている（例えば、非特許文献１〜３参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｇ．  Ｗａｎｇ，  Ｚ．  Ｚｈａｏ，  Ｊ．  Ｐｅｎｇ，  Ｒ．  Ｌｉ  ａｎｄ  Ｈ．  Ｚｈａｎｇ，  “Ａｎ  ａｐｐｒｏｘｉｍａｔｅ  ａｌｇｏｒｉｔｈｍ  ｏｆ  ｃｏｎｔｒｏｌｌｅｒ  ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｉｎ  ｍｕｌｔｉ−ｄｏｍａｉｎ  ＳＤＮ  ａｒｃｈｉｔｅｃｔｕｒｅ，”  ９ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｉｎｇ  ｉｎ  Ｃｈｉｎａ，  Ｍａｏｍｉｎｇ，  ２０１４，  ｐｐ．  ６０１−６０５．
【非特許文献２】Ｓ．  Ｌａｎｇｅ  ｅｔ  ａｌ．，  “Ｈｅｕｒｉｓｔｉｃ  Ａｐｐｒｏａｃｈｅｓ  ｔｏ  ｔｈｅ  Ｃｏｎｔｒｏｌｌｅｒ  Ｐｌａｃｅｍｅｎｔ  Ｐｒｏｂｌｅｍ  ｉｎ  Ｌａｒｇｅ  Ｓｃａｌｅ  ＳＤＮ  Ｎｅｔｗｏｒｋｓ，”  ｉｎ  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｓｅｒｖｉｃｅ  Ｍａｎａｇｅｍｅｎｔ，  ｖｏｌ．  １２，  ｎｏ．  １，  ｐｐ．  ４−１７，  Ｍａｒｃｈ  ２０１５．
【非特許文献３】Ｂｒａｎｄｏｎ  Ｈｅｌｌｅｒ，  Ｒｏｂ  Ｓｈｅｒｗｏｏｄ，  ａｎｄ  Ｎｉｃｋ  ＭｃＫｅｏｗｎ．  ２０１２．  Ｔｈｅ  ｃｏｎｔｒｏｌｌｅｒ  ｐｌａｃｅｍｅｎｔ  ｐｒｏｂｌｅｍ．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｆｉｒｓｔ  ｗｏｒｋｓｈｏｐ  ｏｎ  Ｈｏｔ  ｔｏｐｉｃｓ  ｉｎ  ｓｏｆｔｗａｒｅ  ｄｅｆｉｎｅｄ  ｎｅｔｗｏｒｋｓ  （ＨｏｔＳＤＮ  ’１２）．  ＡＣＭ，  Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ＵＳＡ，  ７−１２．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、複数のコントローラでネットワークを管理する場合、何台のコントローラを使用し、ネットワーク全体をどのように分割して、コントローラをどのように配置するかが問題となり、これらを最適化することは難しかった。
【０００６】
本発明は、ＳＤＮにおいて複数のコントローラを使用する場合に、適切なネットワーク構成の候補を発見できる設計装置、設計方法及び設計プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る設計装置は、ＳＤＮにおける複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及び当該サブグラフの前記コントローラへの割り当てを定義したネットワーク構成を生成する設計装置であって、前記ネットワーク構成の候補集合の初期状態をランダムに生成する初期化部と、前記候補集合の要素それぞれを、適応度の指標により評価する評価部と、前記候補集合の要素のうち、前記評価部による評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ前記評価部による評価が下位の候補を前記候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新部と、前記集合更新部による更新を、所定の条件を満たすまで繰り返した後、前記候補集合における前記評価部による評価が所定以上の部分集合を出力する出力部と、を備える。
【０００８】
前記集合更新部は、前記遺伝的オペレータとして、前記サブグラフの前記コントローラへの割り当て先の変更を含む交叉処理、及び前記サブグラフへの分割パターンの変更を含む突然変異処理を、それぞれ所定の確率で実行してもよい。
【０００９】
前記評価部は、複数の前記指標に基づくパレートフロント内において、前記指標それぞれに所定の重み付けをすることで前記適応度の順位付けを行ってもよい。
【００１０】
前記評価部は、前記指標として、前記コントローラの数、前記コントローラ間の負荷分散、前記コントローラ間の通信遅延の少なくともいずれかを用いてもよい。
【００１１】
本発明に係る設計方法は、ＳＤＮにおける複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及び当該サブグラフの前記コントローラへの割り当てを定義したネットワーク構成をコンピュータが生成する設計方法であって、前記ネットワーク構成の候補集合の初期状態をランダムに生成する初期化ステップと、前記候補集合の要素それぞれを、適応度の指標により評価する評価ステップと、前記候補集合の要素のうち、前記評価ステップによる評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ前記評価ステップによる評価が下位の候補を前記候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新ステップと、前記集合更新ステップによる更新を、所定の条件を満たすまで繰り返した後、前記候補集合における前記評価ステップによる評価が所定以上の部分集合を出力する出力ステップと、を実行する。
【００１２】
本発明に係る設計プログラムは、ＳＤＮにおける複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及び当該サブグラフの前記コントローラへの割り当てを定義したネットワーク構成をコンピュータに生成させるための設計プログラムであって、前記ネットワーク構成の候補集合の初期状態をランダムに生成する初期化ステップと、前記候補集合の要素それぞれを、適応度の指標により評価する評価ステップと、前記候補集合の要素のうち、前記評価ステップによる評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ前記評価ステップによる評価が下位の候補を前記候補集合から削除する処理を繰り返し、次世代の候補集合に更新する集合更新ステップと、前記集合更新ステップによる更新を、所定の条件を満たすまで繰り返した後、前記候補集合における前記評価ステップによる評価が所定以上の部分集合を出力する出力ステップと、を実行させるためのものである。
【発明の効果】
【００１３】
本発明によれば、ＳＤＮにおいて複数のコントローラを使用する場合に、適切なネットワーク構成の候補を発見できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係る設計装置の機能構成を示す図である。
【図２】実施形態に係る設計方法のアルゴリズム１を示す図である。
【図３】実施形態に係るアルゴリズム内で使用する記号の意味を示す図である。
【図４】実施形態に係る設計方法のアルゴリズム２を示す図である。
【図５】実施形態に係る設計方法のアルゴリズム３を示す図である。
【図６】実施形態に係るネットワーク構成の一例を示す図である。
【図７】実施形態に係る第１の突然変異オペレータを例示する図である。
【図８】実施形態に係る第２の突然変異オペレータを例示する図である。
【図９】実施形態に係る第３の突然変異オペレータを例示する図である。
【図１０】実施形態に係る第４の突然変異オペレータを例示する図である。
【図１１】実施形態に係る第４の突然変異オペレータによるサブグラフのコントローラへの割り当ての変化を例示する図である。
【図１２】実施形態に係る第１の交叉オペレータを例示する図である。
【図１３】実施形態に係る第２の交叉オペレータを例示する図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る設計装置１の機能構成を示す図である。
【００１６】
設計装置１は、制御部１０及び記憶部２０の他、各種の入出力インタフェース等を備えた情報処理装置（コンピュータ）である。設計装置１は、記憶部２０に格納されたソフトウェア（設計プログラム）を制御部１０が実行することにより、後述の各種機能を実現する。これにより、設計装置１は、ＳＤＮにおける複数のドメインをノードとするグラフ構造に対して、複数のコントローラのいずれかによって管理される単位であるサブグラフへの分割、及びサブグラフのコントローラへの割り当てを定義したネットワーク構成を生成する。
【００１７】
制御部１０は、設計プログラムを実行することにより実現される機能部として、初期化部１１と、評価部１２と、集合更新部１３と、出力部１４とを備える。
【００１８】
初期化部１１は、ネットワーク構成の候補集合（Ｐｏｐｕｌａｔｉｏｎ）の要素数を入力パラメータとして、候補集合の初期状態をランダムに生成する。
【００１９】
評価部１２は、候補集合の要素であるネットワーク構成それぞれを、適応度の指標により評価する。
このとき、評価部１２は、複数の指標に基づくパレートフロント内において、指標それぞれに所定の重み付けをすることで適応度の順位付けを行う。
評価部１２は、複数の指標として、例えば、コントローラの数、コントローラ間の負荷分散、コントローラ間の通信遅延を用いる。
【００２０】
集合更新部１３は、候補集合の要素のうち、評価部１２による評価が上位の所定数を親として、遺伝的オペレータにより子となるネットワーク構成の候補を追加生成した後、追加生成した数だけ評価が下位の候補を候補集合から削除する処理を繰り返す。これにより、集合更新部１３は、候補集合を更新し、次世代の候補集合とする。
ここで、集合更新部１３は、遺伝的オペレータとして、サブグラフのコントローラへの割り当て先の変更を含む交叉処理、及びサブグラフへの分割パターン（パーティション）の変更を含む突然変異処理を、それぞれ所定の確率で実行する。
【００２１】
出力部１４は、集合更新部１３による更新を、所定の条件を満たすまで繰り返した後、候補集合における評価部１２による評価が所定以上の部分集合を出力する。
【００２２】
図２は、本実施形態に係る設計方法のアルゴリズム１を示す図である。
また、このアルゴリズム内で使用する記号の意味を、図３に示す。
本実施形態では、ＰＣＧＡ（Ｐａｒｅｔｏ−Ｃｏｎｖｅｒｇｉｎｇ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）に基づくＭＯＧＡ（Ｍｕｌｔｉ−Ｏｂｊｅｃｔｉｖｅ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）を適用したアルゴリズムにより、適応度の高いネットワーク構成の集合であるパレートフロント（ランク＝１）を出力する。
【００２３】
なお、ＰＣＧＡ及びＭＯＧＡは、それぞれ例えば下記の文献Ａ及びＢで提案されている。
文献Ａ：  Ｒａｊｅｅｖ  Ｋｕｍａｒ  ａｎｄ  Ｐｅｔｅｒ  Ｒｏｃｋｅｔｔ，  “Ｉｍｐｒｏｖｅｄ  ｓａｍｐｌｉｎｇ  ｏｆ  ｔｈｅ  Ｐａｒｅｔｏ−ｆｒｏｎｔ  ｉｎ  ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ  ｇｅｎｅｔｉｃ  ｏｐｔｉｍｉｚａｔｉｏｎｓ  ｂｙ  ｓｔｅａｄｙ−ｓｔａｔｅ  ｅｖｏｌｕｔｉｏｎ：  Ａ  Ｐａｒｅｔｏ  ｃｏｎｖｅｒｇｉｎｇ  ｇｅｎｅｔｉｃ  ａｌｇｏｒｉｔｈｍ”．  Ｅｖｏｌｕｔｉｏｎａｒｙ．  Ｃｏｍｐｕｔａｔｉｏｎ．  １０，  ３  （Ｓｅｐｔｅｍｂｅｒ  ２００２），  ２８３−３１４．
文献Ｂ：  Ｙａｎｇ  Ｚｈａｎｇ  ａｎｄ  Ｐｅｔｅｒ  Ｒｏｃｋｅｔｔ，  “Ａ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｔｈｒｅｅ  ｅｖｏｌｕｔｉｏｎａｒｙ  ｓｔｒａｔｅｇｉｅｓ  ｆｏｒ  ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ  ｇｅｎｅｔｉｃ  ｐｒｏｇｒａｍｍｉｎｇ”．  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｒｅｖｉｅｗ．  ２７，  ２−３  （Ｍａｒｃｈ  ２００７），  １４９−１６３．
【００２４】
アルゴリズム１は、ネットワークのグラフＧ、１つのコントローラが管理できる最大ドメイン数ｍ、候補集合の大きさ（要素数）Ｐ、集合更新部１３による世代更新の回数ｅｐｏｃｈｓｉｚｅ、ネットワーク構成の候補を追加生成するための親として選択する数ｐａｒｅｎｔｓｉｚｅ、突然変異（Ｍｕｔａｔｉｏｎ）の確率Ｐｍ、交叉（Ｃｒｏｓｓｏｖｅｒ）の確率Ｐｃを入力とする。
【００２５】
ステップ１において、初期化部１１は、グラフＧのサブグラフへの可能な分割パターン（パーティション）の集合Ｃを生成する。
初期化部１１は、例えば、非特許文献１のＭＧＳＣＰ（Ｍｏｄｉｆｉｅｄ  Ｇｒｅｅｄｙ  Ｓｅｔ  Ｃｏｖｅｒ  Ｐｒｏｂｌｅｍ）を用いた図４のアルゴリズム２により、サイズ（ドメイン数）ｘ≦ｍのサブグラフをシードとして、パーティションの集合Ｃを生成する。
【００２６】
ステップ２において、初期化部１１は、例えば、図５のアルゴリズム３により、ステップ１で生成した集合Ｃからランダムにパーティションｃを選択し、さらに各サブグラフに含めるドメインｄをドメインリストＤからランダムに選択することで、候補集合の初期状態を生成する。
【００２７】
ここで、ネットワーク構成は、グラフＧのサブグラフへの分割パターン（パーティション）と、各サブグラフのコントローラへの割り当てとで表現される。
例えば、図６は、グラフＧがサブグラフ１〜３に分割されたパーティション番号「１１」について、６つのコントローラのうち、サブグラフ１をコントローラ１に、サブグラフ２をコントローラ５に、サブグラフ３をコントローラ４にそれぞれ割り当てたネットワーク構成を示している。
【００２８】
ステップ３において、評価部１２は、複数の適応度の指標により、候補集合の要素それぞれを評価する。
適応度の指標は、例えば以下の３種類が採用される。
【００２９】
（１）コントローラの数（Ｎｕｍｂｅｒ  ｏｆ  Ｃｏｎｔｒｏｌｌｅｒｓ）
Ｃをコントローラの全数、ｃを使用されているコントローラの数、Ｃｍｉｎを使用されるコントローラの最小数、Ｃｍａｘを使用されるコントローラの最大数とすると、コントローラの数に関する指標は、例えば、以下の式（１）又は（２）で表される。これらの指標は、値が大きいほど適応度が高いことを示す。
【数１】
2019102919.tif 000003
【００３０】
（２）コントローラ間の負荷分散（Ｌｏａｄ＿Ｄｉｓｔｒｉｂｕｔｉｏｎ）
Ｄｉを候補集合のｉ番目の要素（ネットワーク構成）における全ドメイン数、Ｃｉをｉ番目の要素におけるコントローラ数、Ｄｊをｉ番目の要素におけるｊ番目のコントローラにより制御されるドメイン数とすると、負荷分散に関する指標は、例えば、以下の式（３）又は（４）で表される。これらの指標は、値が小さいほど適応度が高いことを示す。
【数２】
2019102919.tif 000004
【００３１】
（３）コントローラ間の通信遅延（Ｉｎｔｅｒ＿Ｃｏｎｔｒｏｌｌｅｒ＿Ｌａｔｅｎｃｙ）
Ｌｉ，ｊを、候補集合内のある要素（ネットワーク構成）Ｉにおける、ｉ番目のコントローラとｊ番目のコントローラとの間での通信遅延とすると、通信遅延に関する指標は、例えば、以下の式（５）で表される。この指標は、値が小さいほど適応度が高いことを示す。
【数３】
2019102919.tif 000005
【００３２】
ステップ４において、評価部１２は、複数の指標それぞれの高低を独立して評価し、各ネットワーク構成の候補をランク付けする。
ステップ５において、評価部１２は、少なくともパレートフロント（ランク＝１）にあるネットワーク構成の候補について、各指標に適宜の重み付けをして統合した適応度を付与する。
【００３３】
ステップ６及び７において、集合更新部１３は、世代数＃Ｅｐｏｃｈｓ、及び交叉処理によって追加生成した候補の合計数＃ＯｆｆＳｐｒｉｎｇを初期設定（０を代入）した後、ステップ８〜１９で世代数＃Ｅｐｏｃｈｓがｅｐｏｃｈｓｉｚｅに達するまで遺伝的オペレータによる進化処理を繰り返す。
【００３４】
ステップ９において、集合更新部１３は、適応度が上位のネットワーク構成から所定数（ｐａｒｅｎｔｓｉｚｅ）の候補を遺伝的オペレータにおける親として選択する。
【００３５】
ステップ１０において、集合更新部１３は、ｐａｒｅｎｔｓｉｚｅの親から、確率Ｐｃで子のネットワーク構成を追加生成する。生成した子の数をｃｈｉｌｄｓｉｚｅとする。
このときの遺伝的オペレータは交叉であるが、一対の親から子を生成する通常の処理ではなく、無性遺伝を模した１つの親から１つの子を生成するものとする。これにより、いずれのコントローラにも割り当てられないサブグラフ、又は複数のコントローラに同時に割り当てられたサブグラフ等の発生を防ぐことができる。なお、この交叉処理の詳細は後述する。
【００３６】
ステップ１１において、集合更新部１３は、ステップ１０で追加生成したｃｈｉｌｄｓｉｚｅのネットワーク構成に対して、確率Ｐｍで突然変異オペレータによる変更を施し、グラフＧのパーティション、又はサブグラフのコントローラへの割り当てを変更する。
【００３７】
ステップ１２において、集合更新部１３は、ステップ１０で生成したネットワーク構成、及び生成後にステップ１１で突然変異処理を施したネットワーク構成を、候補集合に追加する。さらに、評価部１２は、追加後の候補集合に対して、ネットワーク構成の各候補のランク付け及び適応度の付与を行う。
【００３８】
ステップ１３において、集合更新部１３は、候補集合から、ランク又は適応度の低いネットワーク構成を、追加された数（ｃｈｉｌｄｓｉｚｅ）だけ削除する。
ステップ１４において、集合更新部１３は、追加生成した候補の合計数＃ＯｆｆＳｐｒｉｎｇにｃｈｉｌｄｓｉｚｅを加算する。
【００３９】
ステップ１５〜１８において、集合更新部１３は、＃ＯｆｆＳｐｒｉｎｇが候補集合の要素数Ｐに達したか否かを判定する。要素数Ｐに達した場合、集合更新部１３は、＃ＯｆｆＳｐｒｉｎｇを初期化（０を代入）し、世代数＃Ｅｐｏｃｈｓをカウントアップする。
【００４０】
ステップ２０において、出力部１４は、ステップ１９で世代数＃Ｅｐｏｃｈｓがｅｐｏｃｈｓｉｚｅに達したと判定された場合、候補集合から適応度が上位の、あるいは最高ランク（ランク＝１）の部分集合を出力する。
【００４１】
本実施形態における遺伝的オペレータは、例えば、以下の突然変異オペレータ（第１〜第２）、及び交叉オペレータ（第１〜第４）が採用される。
【００４２】
図７は、本実施形態に係る第１の突然変異オペレータを例示する図である。
第１の突然変異オペレータでは、２つのコントローラに割り当てられるサブグラフが交換される。
例えば、図７では、６つのコントローラのうち、コントローラ１にサブグラフ１が、コントローラ４にサブグラフ３が、コントローラ５にサブグラフ２がそれぞれ割り当てられている構成について、２つのコントローラ４及び５が選択され、これらに割り当てられているサブグラフが交換される。すなわち、コントローラ４にサブグラフ２が、コントローラ５にサブグラフ３がそれぞれ割り当てられる。
【００４３】
図８は、本実施形態に係る第２の突然変異オペレータを例示する図である。
第２の突然変異オペレータでは、１つのサブグラフが割り当てのないコントローラに新たに割り当て変更される。
例えば、図８では、図７と同様のネットワーク構成に対して、サブグラフ３が選択され、割り当て先がコントローラ３に変更される。すなわち、コントローラ３にサブグラフ３が割り当てられ、コントローラ４は使用されなくなる。
【００４４】
図９は、本実施形態に係る第３の突然変異オペレータを例示する図である。
第３の突然変異オペレータでは、サブグラフ間にリンクのある２つのノードのうち、一方のノードが他方のサブグラフに移動される。
例えば、図９では、サブグラフ３に属するノードＡがサブグラフ２に移動することで、サブグラフ２及び３がそれぞれ、サブグラフ２’及び３’に変更される。
【００４５】
図１０は、本実施形態に係る第４の突然変異オペレータを例示する図である。
第４の突然変異オペレータでは、１つのサブグラフが複数のサブグラフに分割される。
例えば、図１０では、サブグラフ３が２つのサブグラフに分割され、サブグラフ３’及び４が生成される。
【００４６】
このとき、図１１に示すように、新たに生成されたサブグラフ４が、未使用のコントローラのいずれか、例えばコントローラ２に割り当てられる。
【００４７】
図１２は、本実施形態に係る第１の交叉オペレータを例示する図である。
第１の交叉オペレータでは、親となるネットワーク構成から、サブグラフのコントローラへの割り当てがランダムに変更されたネットワーク構成の候補が新たに生成される。
例えば、図１２では、サブグラフ１〜３の割り当て先が６つのコントローラからランダムに選択された複数の構成が列挙されている。これらのうち、いずれかのネットワーク構成が候補として新たに生成される。
【００４８】
図１３は、本実施形態に係る第２の交叉オペレータを例示する図である。
第２の交叉オペレータでは、第１の交叉オペレータと同様の交叉処理の前に第３又は第４の突然変異オペレータと同様の突然変異処理が実施される。
例えば、図１３では、第３の突然変異オペレータと同様の処理により、サブグラフ２及び３がサブグラフ２’及び３’に変更されたネットワーク構成を元にして、第１の交叉オペレータと同様の処理が施されたいずれかのネットワーク構成が候補として新たに生成される。
【００４９】
集合更新部１３は、この第２の交叉オペレータによりネットワーク構成の候補を追加生成した場合、さらにステップ１１（図２）で突然変異オペレータによる処理を行うことにより、グラフ分割の状態をより大きく変化させ、特徴の異なるネットワーク構成の候補を生成できる。
【００５０】
本実施形態によれば、設計装置１は、ＳＤＮにおいて複数のコントローラを使用する場合に、候補集合のうち適応度の高いネットワーク構成を親として、遺伝的オペレータによって子となるネットワーク構成の候補を追加生成し、適応度が低い候補を削除する。設計装置１は、この世代交代の処理を繰り返すことで、適応度の高い適切なネットワーク構成の候補を発見できる。
この結果、設計装置１は、与えられたグラフに対して、適切なネットワーク構成の候補を複数保持できる。これにより、設計装置１は、例えば、ＤＤｏＳ（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｄｅｎｉａｌ  ｏｆ  Ｓｅｒｖｉｃｅ）攻撃を受けたネットワークに対して、攻撃の影響範囲又は規模を限定できる新たなネットワーク構成の候補を複数提供し試行できる。
【００５１】
設計装置１は、遺伝的オペレータとして、サブグラフのコントローラへの割り当て先の変更を含む交叉処理と、サブグラフへの分割パターンの変更を含む突然変異処理とを、それぞれ所定の確率で実行することにより、遺伝的アルゴリズムをネットワーク構成の生成処理に対して良好に適用でき、適応度の高いネットワーク構成を効率的に発見することができる。
【００５２】
設計装置１は、適応度に関する複数の指標それぞれに所定の重み付けをすることで１つの指標に統一することにより、複数のネットワーク構成の候補を順位付けでき、適応度の高い集合を容易に発見することができる。
【００５３】
設計装置１は、適応度に関する指標として、コントローラの数、コントローラ間の負荷分散、及びコントローラ間の通信遅延を用いることにより、適応度を適切に評価でき、適切なネットワーク構成の候補を発見できる。
【００５４】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
前述の実施形態では、交叉オペレータ又は突然変異オペレータにより生成された新たなネットワーク構成の候補が、既存の構成と同一となる場合がある。集合更新部１３は、これらの重複した構成を候補集合に追加してもよいし、除外又は別の候補を生成してもよい。
また、第１及び第２の突然変異オペレータは、第１の交叉オペレータの処理に含まれると考え、採用しなくてもよい。この場合、突然変異の処理では、必ずパーティションの変更が行われる。
【００５５】
設計装置１による設計方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００５６】
１  設計装置
１０  制御部
１１  初期化部
１２  評価部
１３  集合更新部
１４  出力部
２０  記憶部
【図１】
2019102919.tif 000006
【図２】
2019102919.tif 000007
【図３】
2019102919.tif 000008
【図４】
2019102919.tif 000009
【図５】
2019102919.tif 000010
【図６】
2019102919.tif 000011
【図７】
2019102919.tif 000012
【図８】
2019102919.tif 000013
【図９】
2019102919.tif 000014
【図１０】
2019102919.tif 000015
【図１１】
2019102919.tif 000016
【図１２】
2019102919.tif 000017
【図１３】
2019102919.tif 000018