(57)【要約】【課題】基盤ネットワーク上に構成される連携型仮想ネットワークの形を、元の連携型仮想ネットワークを最小限かつ均等に拡大させた形に近付ける。【解決手段】通常仮想ノードを選択する第１選択部１０１と、通常仮想ノードの割当先候補となる基盤ノード群から前記選択された通常仮想ノードの割当先候補を選択する第２選択部１０２と、選択した通常仮想ノードと基盤ノードに割当済みの各仮想ノードとの仮想ネットワーク上での距離vdistanceをそれぞれ算出する第１計算部２０１と、割当先候補の基盤ノードと仮想ノードが割当済みの各基盤ノードとの基盤ネットワーク上での距離sdistanceをそれぞれ算出する第２計算部２０２と、各距離sdistanceとvdistanceの距離比が所定の基準値を下回ると、前記選択した通常仮想ノードを今回の割当先候補の基盤ノードへ割り当てる通常仮想ノード割当手段３０２とを具備した。【選択図】図７
2020014111.tif 000002
【特許請求の範囲】
【請求項１】
基盤ノード群から構成される基盤ネットワークに、通常仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割り当てる方法において、
未割当の通常仮想ノードおよびその割当先候補となる未割当の基盤ノードの対を選択する第１手順と、
前記選択された対の未割当の基盤ノードと各割当済みの基盤ノードとの距離と前記選択された対の未割当の通常仮想ノードと各割当済みの仮想ノードとの距離との距離比をそれぞれ算出する第２手順と、
前記各距離比が所定の基準値を下回ると、前記未割当の通常仮想ノードを前記割当先候補の基盤ノードに割り当てる第３手順と、
前記第１ないし第３手順を繰り返す第４手順とを含むことを特徴とする連携型仮想ネットワーク割当方法。
【請求項２】
仮想ネットワークの各仮想リンクを要求帯域の降順で選択する第５手順と、
前記選択した仮想リンクを基盤ネットワークの対応する基盤パスに割り当てる第６手順とを更に含むことを特徴とする請求項１に記載の連携型仮想ネットワーク割当方法。
【請求項３】
前記第１手順では、未割当の通常仮想ノードを、その要求容量の降順に選択し、未割当の基盤ノードを、その空き容量が前記選択された未割当の通常仮想ノードの要求容量以上の基盤ノード集合から空き容量の降順に選択することを特徴とする請求項１または２に記載の連携型仮想ネットワーク割当方法。
【請求項４】
前記第３手順において、所定の基準値を下回らない距離比が算出されると、前記第１の手順において、前記基盤ノード集合から空き容量が次に大きい未割当の基盤ノードを選択することを特徴とする請求項３に記載の連携型仮想ネットワーク割当方法。
【請求項５】
前記基盤ノード集合に、前記距離比が所定の基準値を下回る未割当の基盤ノードが存在しないと、前記基準値を緩和して前記第１ないし第３手順を繰り返すことを特徴とする請求項４に記載の連携型仮想ネットワーク割当方法。
【請求項６】
前記仮想ネットワークが、仮想ノードとして連携仮想ノードを含み、
前記基盤ネットワークが、基盤ノードとして共用基盤ノードを含み、
前記第１手順の前に、各連携仮想ノードをいずれかの共用基盤ノードに割り当てる手順を更に含むことを特徴とする請求項１ないし５のいずれかに記載の連携型仮想ネットワーク割当方法。
【請求項７】
前記各連携仮想ノードを共用基盤ノードのいずれかに割り当てる手順は、
共用基盤ノードごとに、他の共用基盤ノードまでの基盤ネットワーク上での平均距離を算出する手順と、
連携仮想ノードごとに、他の連携仮想ノードまでの仮想ネットワーク上での平均距離を算出する手順とを含み、
各連携仮想ノードを各共用基盤ノードに、前記各平均距離の昇順で割り当てることを特徴とする請求項６に記載の連携型仮想ネットワーク割当方法。
【請求項８】
前記基盤ネットワーク上での基盤ノード間の距離が、始点となる基盤ノードの空き容量が大きいほど短くなり、基盤ノード間を接続する基盤パスの空き帯域が大きいほど短くなるように定義されることを特徴とする請求項１ないし７のいずれかに記載の連携型仮想ネットワーク割当方法。
【請求項９】
前記仮想ネットワーク上での仮想ノード間の距離が、始点となる仮想ノードの要求容量が大きいほど短くなり、仮想ノード間を接続する仮想パスの要求帯域が大きいほど短くなるように定義されることを特徴とする請求項１ないし８のいずれかに記載の連携型仮想ネットワーク割当方法。
【請求項１０】
前記基盤ネットワーク上での基盤ノード間の距離が、始点となる基盤ノードの空き容量の逆数および始点の基盤ノードから他端の基盤ノードへ至る基盤パスを構成する各基盤リンクの空き帯域の逆数の和の重み付け和に基づいて求められることを特徴とする請求項８に記載の連携型仮想ネットワーク割当方法。
【請求項１１】
前記仮想ネットワーク上での仮想ノード間の距離が、始点となる仮想ノードの要求容量の逆数および始点の仮想ノードと他端の仮想ノードとを接続する仮想パスを構成する各仮想リンクの要求帯域の逆数の和の重み付け和に基づいて求められることを特徴とする請求項９に記載の連携型仮想ネットワーク割当方法。
【請求項１２】
通常基盤ノードを含む基盤ノード群から構成される基盤ネットワークに、通常仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割り当てる仮想ネットワーク割当装置において、
基盤ノードに割り当てる通常仮想ノードを選択する第１選択手段と、
通常仮想ノードの割当先候補となる基盤ノード群から前記選択された通常仮想ノードの割当先候補を選択する第２選択手段と、
前記選択した通常仮想ノードと基盤ノードに割当済みの各仮想ノードとの仮想ネットワーク上での距離vdistanceをそれぞれ算出する第１計算手段と、
前記割当先候補の基盤ノードと仮想ノードが割当済みの各基盤ノードとの基盤ネットワーク上での距離sdistanceをそれぞれ算出する第２計算手段と、
基盤ネットワーク上での前記各距離sdistanceと、仮想ネットワーク上での対応する前記各距離vdistanceとの距離比が所定の基準値を下回ると、前記選択した通常仮想ノードを前記今回の割当先候補の基盤ノードへ割り当てる通常仮想ノード割当手段とを具備したことを特徴とする連携型仮想ネットワーク割当装置。
【請求項１３】
前記第２選択手段は、前記通常仮想ノード割当手段が、前記各距離比の少なくとも一つが所定の基準値を下回らないと判断すると、割当先候補となる基盤ノードを他の基盤ノードに切り替えることを特徴とする請求項１２に記載の連携型仮想ネットワーク割当装置。
【請求項１４】
仮想ネットワークの各仮想リンクを要求帯域の降順で選択して基盤ネットワークの対応する基盤パスに割り当てる仮想リンク割当手段を更に具備したことを特徴とする請求項１２または１３に記載の連携型仮想ネットワーク割当装置。
【請求項１５】
前記仮想ネットワークが、仮想ノードとして連携仮想ノードを含み、
前記基盤ネットワークが、基盤ノードとして共用基盤ノードを含み、
各通常仮想ノードをいずれかの基盤ノードに割り当てる前に、各連携仮想ノードを共用基盤ノードのいずれかに割り当てる連携仮想ノード割当手段を更に具備したことを特徴とする請求項１２ないし１４のいずれかに記載の連携型仮想ネットワーク割当装置。
【請求項１６】
前記連携仮想ノード割当手段は、
共用基盤ノードごとに、他の共用基盤ノードまでの基盤ネットワーク上での平均距離を算出する手段と、
連携仮想ノードごとに、他の連携仮想ノードまでの仮想ネットワーク上での平均距離を算出する手段とを具備し、
各連携仮想ノードを各共用基盤ノードに、前記各平均距離の昇順で割り当てることを特徴とする請求項１５に記載の連携型仮想ネットワーク割当装置。
【請求項１７】
前記第１計算手段は、仮想ネットワーク上での仮想ノード間の距離vdistanceを、始点となる仮想ノードの要求容量が大きいほど短くなり、仮想ノード間を接続する仮想パスの要求帯域が大きいほど短くなるように定義することを特徴とする請求項１２ないし１６のいずれかに記載の連携型仮想ネットワーク割当装置。
【請求項１８】
前記第２計算手段は、基盤ネットワーク上での基盤ノード間の距離sdistanceを、始点となる基盤ノードの空き容量が大きいほど短くなり、基盤ノード間を接続する基盤パスの空き帯域が大きいほど短くなるように定義することを特徴とする請求項１２ないし１７のいずれかに記載の連携型仮想ネットワーク割当装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連携型仮想ネットワークを基盤ネットワークに割り当てる方法および装置に係り、特に、サービス連携機能を有する基盤ノードを互いに共用する連携型仮想ネットワークを当該基盤ネットワークに割り当てる方法および装置に関する。
【背景技術】
【０００２】
非特許文献１には、各仮想ノードと当該仮想ノードの割り当てが可能な全ての基盤ノードとを拡張リンクを用いて接続することによって、基盤ネットワークを表すグラフを拡張し、本拡張グラフ上での数理計画モデルを使って仮想ネットワークの基盤ネットワークへの割り当てを実現する方法が開示されている。
【０００３】
非特許文献２には、既に基盤ノードに割り当てられている仮想ノードの隣接仮想ノードを、新たに割り当てられる仮想リンクが、予め与えられた最大基盤パス長以下の基盤パスに割り当て可能となるような基盤ノードへ、逐次的に割り当てて行く方法が開示されている。
【０００４】
特許文献１および２には、各仮想ノードと当該仮想ノードの割り当てが可能な全ての基盤ノードとを、拡張リンクを用いて接続することによって、基盤ネットワークを表すグラフを拡張し、本拡張グラフ上で逐次的に各仮想リンクを最小コスト経路に割り当てることによって、当該仮想リンクを割り当てる基盤パスと当該仮想リンクが接続する仮想ノードの基盤ノードへの割り当てを決定して行く方法が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第６２７９４２７号公報
【特許文献２】特許第６３０７３７７号公報
【非特許文献】
【０００６】
【非特許文献１】M. Chowdhury, M. R. Rahman, and R. Boutaba, "ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping," IEEE/ACM Trans. on Networking, vol. 20, no. 1, pp. 206-219, Feb. 2012.
【非特許文献２】J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in Proc. ACM VISA'09, August 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１では、数理計画モデルを使用するために計算量が増加し、大規模な基盤ネットワークへの仮想ネットワークの割り当てには適用できない。非特許文献２では、逐次的に基盤ノードに割り当てる仮想ノードの順番によっては、効率的な仮想ネットワーク割当が実現できない場合が存在する。
【０００８】
特許文献１および２では、最小コスト経路に割り当てる仮想リンクの順番によっては、効率的な仮想ネットワーク割り当てが実現できない場合が存在する。
【０００９】
本発明の目的は、上記の技術課題を解決し、基盤ネットワーク上に構成される連携型仮想ネットワークの形を、元の連携型仮想ネットワークを最小限かつ均等に拡大させた形に近付けられる連携型仮想ネットワークの割当方法および装置を提供することにある。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明は、基盤ノード群から構成される基盤ネットワークに、通常仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割り当てる仮想ネットワークの割当方法および装置において、以下の構成を具備した点に特徴がある。
【００１１】
(1) 基盤ノードに割り当てる通常仮想ノードを選択し、割当先候補となる基盤ノード群から前記選択された通常仮想ノードの割当先候補を選択し、前記選択した通常仮想ノードと基盤ノードに割当済みの各仮想ノードとの仮想ネットワーク上での距離vdistanceをそれぞれ算出し、前記割当先候補の基盤ノードと仮想ノードが割当済みの各基盤ノードとの基盤ネットワーク上での距離sdistanceをそれぞれ算出し、対応する距離sdistanceとvdistanceの距離比が所定の基準値を下回ると、前記選択した通常仮想ノードを今回の割当先候補の基盤ノードへ割り当てるようにした。
【００１２】
(2) 前記仮想ネットワークが、仮想ノードとして連携仮想ノードを含み、前記基盤ネットワークが、基盤ノードとして共用基盤ノードを含み、各通常仮想ノードをいずれかの基盤ノードに割り当てる前に、各連携仮想ノードを共用基盤ノードのいずれかに割り当てるようにした。
【００１３】
(3) 仮想ネットワーク上での仮想ノード間の距離vdistanceを、始点となる仮想ノードの要求容量が大きいほど短くなり、仮想ノード間を接続する仮想パスの要求帯域が大きいほど短くなるように定義した。
【００１４】
(4) 基盤ネットワーク上での基盤ノード間の距離sdistanceを、始点となる基盤ノードの空き容量が大きいほど短くなり、基盤ノード間を接続する基盤パスの空き帯域が大きいほど短くなるように定義した。
【発明の効果】
【００１５】
本発明によれば、以下の効果が達成される。
【００１６】
(1) 基盤ネットワーク上に構成された連携型仮想ネットワークの形が、共用基盤ノード群の配置に応じた最小の比率で、元の連携型仮想ネットワークを均等に拡大させた形に近付くため、基盤リソース利用効率の良い連携型仮想ネットワーク割り当てが実現できる。
【００１７】
(2) 連携仮想ノード群の共用基盤ノード群への割り当て結果を利用することにより、最初の通常仮想ノードから、精度の良い基盤ノードへの割り当てが可能となる。
【００１８】
(3) 連携型仮想ネットワークを割り当てた後の基盤ノードの空き容量や基盤リンクの空き帯域を均等化させることができるため、より多くの連携型仮想ネットワークを基盤ネットワークに割り当てることができる。
【００１９】
(4) 要求帯域の大きな仮想リンクが相対的に短い基盤パスに割り当てられるため、連携型仮想ネットワークを割り当てるために必要な総基盤リンク帯域を減らすことができる。
【図面の簡単な説明】
【００２０】
【図１】基盤ネットワークSNに連携型仮想ネットワークVNを割り当てる方法を模式的に示した図（その１）である。
【図２】基盤ネットワークSNに連携型仮想ネットワークVNを割り当てる方法を模式的に示した図（その２）である。
【図３】本発明による連携型仮想ネットワーク割当方法の概念図である。
【図４】本発明の一実施形態に係る連携型仮想ネットワークの基盤ネットワークへの割当処理の手順を示したフローチャートである。
【図５】通常仮想ノードの基盤ノードへの割当処理の手順を示したフローチャートである。
【図６】連携仮想ノードの共用基盤ノードへの割当処理の手順を示したフローチャートである。
【図７】本発明の一実施形態に係る仮想ネットワーク割当装置の主要部の構成を示した機能ブロック図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１，２は、サービス連携機能を有する共用基盤ノード群を含む基盤ネットワークSNに対して、連携仮想ノード群を含む連携型仮想ネットワークVNを割り当てる方法を模式的に示した図である。
【００２２】
連携型仮想ネットワークVNは、図１に示したように、ハッチング（●）で示した連携仮想ノードvn（vn1，vn3）と、白丸（○）で示した通常仮想ノードvn（vn2，vn4）とを仮想リンクvlで連結して構成される。基盤ネットワークSNは、ハッチングで示した共用基盤ノードsn（●）と、それ以外の通常基盤ノードsn（○）とを基盤リンクで連結して構成される。
【００２３】
連携型仮想ネットワークVNの連携仮想ノードvn（群）および基盤ネットワークSNの共用基盤ノードsn（群）は予め指定されている。共用基盤ノードsnには、各連携型仮想ネットワークVNが共有するデータを管理するサーバ（図示省略）が接続されている。
【００２４】
連携型仮想ネットワークVNの各連携仮想ノードvnおよび各通常仮想ノードvn（以下、「仮想ノード」で総称する場合もある）の要求容量および各仮想リンクvlの要求帯域は予め指定される。前記要求容量の指標としては、例えば仮想ノードを構成するコンピュータのリソース（メモリ、CPU、ディスク記録媒体など）の要求容量や要求稼働率を用いることができる。各仮想ノードvnは、それぞれ異なる１個の基盤ノードsnに割り当てられる。
【００２５】
本実施形態では、各連携仮想ノードvnは、それぞれ異なる１個の共用基盤ノードsnに割り当てられ、各通常仮想ノードvnは、それぞれ異なる１個の基盤ノードsnに割り当てられる。図２の例では、連携仮想ノードvn1，vn3が、それぞれ共用基盤ノードsn6，sn3に割り当てられ、通常仮想ノードvn2，vn4が、それぞれ基盤ノードsn1，sn7に割り当てられている。
【００２６】
連携型仮想ネットワークVNの各仮想リンクvlは、当該仮想リンクvlの両端に接続された仮想ノードvnが割り当てられる基盤ノードsn間を接続する１本の基盤パスに割り当てられる。図２の例では、通常仮想ノードvn3，vn4間を接続する仮想リンクvl4は、基盤ノードsn3，sn8，sn7を通る基盤パスに割り当てられる。
【００２７】
各仮想ノードvnおよび仮想リンクvlの割り当ては、基盤ノードsnの空き容量および基盤パスを構成する各基盤リンクの空き帯域を超えて行う事はできない。例えば、仮想リンクvl4の割り当ては、基盤ノードsn3，sn8間の基盤リンクおよび基盤ノードsn8，sn7間の基盤リンクの空き帯域を超えて行う事はできない。前記空き容量の指標としては、例えば基盤ノードを構成するコンピュータのリソース（メモリ、CPU、ディスク記録媒体など）の空き容量や空き稼働率を用いることができる。
【００２８】
本実施形態では、連携仮想ノードvn群の共用基盤ノード群snへの割り当てを最初の基準点として、基盤ネットワークSN上の仮想ノードが割当てられた基盤ノード間の距離と連携型仮想ネットワークVN上の当該仮想ノード間の距離との比率が最小かつ均一となるように、逐次的に各仮想ノードを各基盤ノードへ割り当てる。これにより、基盤ネットワークSN上に構成される連携型仮想ネットワークVNの形を、元の連携型仮想ネットワークを共用基盤ノード群の配置に応じた最小の比率で均等に拡大させた相似形状に近付けることができる。
【００２９】
図３は、本発明による連携型仮想ネットワーク割当方法の概念図である。ここでは、連携仮想ノードvn1，vn2が、それぞれ共用基盤ノードsn1，sn2に予め割り当てられている状態から、最初に通常仮想ノードvn3が基盤ノードsn3に割り当てられ、次いで、通常仮想ノードvn4の割当先となる基盤ノードを決定する場合を説明する。
【００３０】
基盤ノードsn4が通常仮想ノードvn4の割当先候補の一つである場合、割当先候補の基盤ノードsn4から仮想ノードvn1が割当済みの基盤ノードsn1までの基盤ネットワークSN上での距離と、割り当てようとしている仮想ノードvn4から前記仮想ノードvn1までの連携型仮想ネットワークVN上の距離との比率R1を求める。
【００３１】
次いで、割当先候補の基盤ノードsn4から他の仮想ノードvn2が割当済みの基盤ノードsn2までの基盤ネットワーク上での距離と、仮想ノードvn4から前記仮想ノードvn2までの距離との比率R2を求める。
【００３２】
さらに、割当先候補の基盤ノードsn4から他の仮想ノードvn3が割当済みの基盤ノードsn3までの基盤ネットワーク上での距離と、仮想ノードvn4から前記仮想ノードvn3までの距離の比率R3を求める。
【００３３】
そして、これらの比率R1，R2，R3を最小かつ均等と認識できれば、実際に仮想ノードvn4を割当先候補の基盤ノードsn4に割り当てて割当済みとし、これを連携型仮想ネットワークVNの全ての仮想ノードvnに対して繰り返す。
【００３４】
図４は、本発明の一実施形態に係る連携型仮想ネットワークVNの基盤ネットワークSNへの割当処理の手順を示したフローチャートである。
【００３５】
ステップＳ１では、仮想ネットワークVNの全ての連携仮想ノードvnが、基盤ネットワークSNの所定の条件を満足する各共用基盤ノードへ割り当てられる。なお、当該割当方法に関しては、後に図６のフローチャートを参照して詳細に説明する。
【００３６】
ステップＳ２では、通常仮想ノードvnの一つが、その要求容量の降順で選択される。ステップＳ３では、選択された通常仮想ノードvnが未割当の基盤ノードsnのいずれかに割り当てられる。なお、当該割当方法に関しても、後に図５のフローチャートを参照して詳細に説明する。
【００３７】
ステップＳ４では、未選択の通常仮想ノードvnの有無が判断される。未選択の通常仮想ノードvnが無くなるまではステップＳ２へ戻り、次の通常仮想ノードvnが前記要求容量の降順で選択されて上記の各処理が繰り返される。全ての通常仮想ノードvnについて基盤ノードsnへの割り当てが完了するとステップＳ５へ進む。
【００３８】
ステップＳ５では、仮想リンクvlの一つが、その要求帯域の降順で順次に選択される。ステップＳ６では、選択された仮想リンクvlが基盤ネットワークSNの基盤パスに割り当てられる。各仮想リンクvlは、その両端の仮想ノードvnが割り当てられた基盤ノードsn間を接続する全ての基盤リンクが前記要求帯域以上の空き帯域を有する最短基盤パスに割り当てられる。
【００３９】
ステップＳ７では、未選択の仮想リンクの有無が判断され、未選択の仮想リンクvlが無くなるまで、ステップＳ５へ戻って上記の各処理が繰り返される。全ての仮想リンクvlについて、その基盤パスへの割り当てが完了すると当該処理を終了する。
【００４０】
図５は、前記図４のステップＳ３で実施される通常仮想ノードvnの基盤ノードsnへの割当手順を示したフローチャートである。本実施形態では、未だ仮想ノードが割り当てられておらず、かつ割り当てようとしている通常仮想ノードvnの要求容量以上の空き容量を有する基盤ノードが割当先候補となる。
【００４１】
ステップＳ３０１では、変数marginに初期値が設定される。変数marginは、仮想ネットワークVNの各仮想リンクvlに対応する基盤ネットワークSN上の基盤パスと、当該仮想リンクvlの距離比の許容上限値であり、仮想ネットワークVNが割り当てられる基盤ネットワーク上の割当部分のネットワークトポロジを、仮想ネットワークVNのトポロジに対して、より小さな相似比の相似に近い形状にするための値に設定される。
【００４２】
ステップＳ３０２では、未だ仮想ノードが割り当てられておらず、かつ選択されている通常仮想ノードvnの要求容量以上の空き容量を有する全ての基盤ノードsnが、前記通常仮想ノードvnの割当先候補の集合とされる。ステップＳ３０３では、前記割当先候補集合から空き容量の降順に、今回の割当先候補の基盤ノードsnが一つ取り出される。
【００４３】
ステップＳ３０４では、割当済の仮想ノードvn'と基盤ノードsn'との組み合わせ（仮想・基盤ノード対）の一つが選択される。ステップＳ３０５では、前記選択された通常仮想ノードvnから前記仮想・基盤ノード対の仮想ノードvn'までの仮想ネットワークVN上の距離vdistanceが算出され、さらに前記取り出された割当先候補の基盤ノードsnから前記仮想・基盤ノード対の基盤ノードsn'までの基盤ネットワークSN上の距離sdistanceが算出される。
【００４４】
ステップＳ３０６では、次式(1)に基づいて、距離比（sdistance／vdistance）が前記変数marginと比較される。
【００４５】
【数１】
2020014111.tif 000003
【００４６】
上式(1)が成立すればステップＳ３０７へ進み、未だ距離比の比較が済んでいない未選択の仮想／基盤ノード対の有無が判断される。未選択の仮想／基盤ノード対が存在する限りはステップＳ３０４へ戻り、選択する仮想／基盤ノード対を切り換えながら、前記ステップＳ３０５の距離算出および前記ステップＳ３０６の判断が繰り返される。
【００４７】
全ての仮想／基盤ノード対との関係で前記距離比が変数margin以下であれば、今回の割当を正当と判断してステップＳ３０８へ進み、前記選択された今回の通常仮想ノードが前記取り出された今回の割当先候補の基盤ノードに割り当てられて割当済とされる。
【００４８】
これに対して、上式(1)を満足できない仮想／基盤ノード対が一つでも存在すれば、今回の割当を正当ではないと判断してステップＳ３０９へ進む。ステップＳ３０９では、前記ステップＳ３０２で構成した割当先候補集合が空になったか否かが判断される。空でない限りはステップＳ３０３へ戻り、前記空き容量が次に大きい基盤ノードを次の割当先候補として取り出し、上記の各処理が繰り返される。
【００４９】
また、割当先候補集合が空になっているとステップＳ３１０へ進み、変数marginの値を緩和（本実施形態では、増加）させた後にステップＳ３０２へ戻り、割当先候補集合を再構築した後に上記の各処理が繰り返される。
【００５０】
上記の割当処理によれば、全ての通常仮想ノードvnについて、割当先基盤ノードsnと全ての仮想／基盤ノード対の割当済み基盤ノードとの間の基盤ネットワーク上の距離と、当該通常仮想ノードvnと全ての仮想／基盤ノード対の対応する割当済み仮想ノードとの間の仮想ネットワーク上の距離との距離比を、より小さな一定の値に抑えられようになる。
【００５１】
図６は、前記ステップＳ１で実行される、連携仮想ノードの共用基盤ノードへの割当処理の手順を示したフローチャートである。
【００５２】
ステップＳ１０１では、共用基盤ノードsnごとに、他の共用基盤ノードsnまでの基盤ネットワークSN上での平均距離が算出される。ステップＳ１０２では、各共用基盤ノードsnが他の共用基盤ノードsnまでの平均距離の昇順にソートされる。
【００５３】
ステップＳ１０３では、連携仮想ノードvnごとに、他の連携仮想ノードvnまでの連携仮想ネットワークVN上での平均距離が算出される。ステップＳ１０４では、各連携仮想ノードvnが他の連携仮想ノードvnまでの平均距離の昇順にソートされる。
【００５４】
ステップＳ１０５では、各連携仮想ノードvnが、ソート順の等しい共用基盤ノードsnに割り当てられる。
【００５５】
本実施形態では、基盤ネットワークSN上での基盤ノード間の距離sdistanceが、次式(2)に示したように、始点となる基盤ノードsnの空き容量SCsnの逆数と、始点の基盤ノードsnから他端の基盤ノードsn'へ至る最短の基盤パス長SPとの重み付け和として求められる。前記最短の基盤パス長SPは、当該最短の基盤パスを構成する各基盤リンクslの空き帯域SBslの逆数の和として定義される。
【００５６】
【数２】
2020014111.tif 000004
【００５７】
前記仮想ネットワーク上での仮想ノード間の距離vdistanceは、次式(3)に示したように、始点となる仮想ノードvnの要求容量VCvnの逆数と、始点の仮想ノードvnから他端の仮想ノードvn'へ至る最短の仮想パス長VPとの重み付け和として求められる。前記最短の仮想パス長VPは、当該最短仮想パスを構成する各仮想リンクvlの要求帯域VBvlの逆数の和として定義される。
【００５８】
【数３】
2020014111.tif 000005
【００５９】
基盤ネットワークSNにおいては、基盤ノードsnの空き容量や基盤パスの空き帯域が大きい程、距離が短くなるため、その様な基盤ノードや基盤パスに仮想ノードや仮想リンクが割り当てられる確率が高くなる。
【００６０】
すなわち、空き容量が大きい基盤ノードには、変数marginの値が小さい段階で優先的に仮想ノードが割り当てられ、空き帯域が大きい基盤パスには、最短パスとして仮想リンクが割り当てられる確率が高くなる。これにより、連携型仮想ネットワークを割り当てた後の基盤ノードの空き容量や基盤リンクの空き帯域を均等化させることができる。
【００６１】
一方、仮想ネットワークにおいては、仮想ノードの要求容量や仮想パスの要求帯域が大きい程、距離が短くなる。従って、要求容量の大きな連携仮想ノードは、空き容量の大きな共用基盤ノードに割り当てられ、要求帯域の大きな仮想リンクは相対的に短い基盤パスに割り当てられる。
【００６２】
これにより、連携仮想ノード群を割り当てた後の共用基盤ノード群の空き容量を均等化することができる。また、連携型仮想ネットワークを割り当てるために必要な総基盤リンク帯域を減らすことができる。基盤ノードにおける空き容量制約と基盤リンクにおける空き帯域制約とを比較して、前者が強い場合は、重み値weightを0.0に近付け、後者が強い場合は、重み値weightを1.0に近付けることにより、効果的な連携型仮想ネットワーク割り当てを実現できる。
【００６３】
図７は、本発明の一実施形態に係る仮想ネットワーク割当装置の主要部の構成を示した機能ブロック図である。本発明の仮想ネットワーク割当装置は、汎用のコンピュータやサーバに各機能を実現するアプリケーション（プログラム）を実装することで構成できる。あるいはアプリケーションの一部がハードウェア化またはROM化された専用機や単能機としても構成できる。
【００６４】
仮想ネットワーク割当装置１には、連携型仮想ネットワークVNのトポロジ情報および基盤ネットワークSNのトポロジ情報が入力される。仮想ネットワークVNのトポロジ情報には、各仮想ノードvnの要求容量、各仮想リンクvlの要求帯域および各仮想ノードvnが連携仮想ノードおよび通常仮想ノードのいずれであるかの情報が含まれる。
【００６５】
基盤ネットワークSNのトポロジ情報には、各基盤ノードsnの空き容量、各基盤リンクの空き帯域および各基盤ノードsnが共用基盤ノードおよび通常基盤ノードのいずれであるかの情報が含まれる。
【００６６】
ノード選択部１０は、第１選択部１０１および第２選択部１０２を含む。第１選択部１０１は、基盤ネットワークSNの一の基盤ノードsnに割り当てる仮想ネットワークVNの仮想ノードvnを選択する。本実施形態では、前記図４のステップＳ２に関して説明したように、通常仮想ノードvnがその要求容量の降順に選択される。
【００６７】
第２選択部１０２は、前記選択した仮想ノードvnの割当先候補となる基盤ノードsnを選択する。本実施形態では、前記図５のステップＳ３０２，Ｓ３０３に関して説明したように、空き容量が前記選択された通常仮想ノードvnの要求容量以上の基盤ノードsnが空き容量の降順に選択される。
【００６８】
距離計算部２０は、第１計算部２０１および第２計算部２０２を含む。第１計算部２０１は、仮想ノード間の距離を上式(3)に基づいて算出する。第２計算部２０１は、基盤ノード間の距離を上式(2)に基づいて算出する。
【００６９】
割当部３０は、連携仮想ノード割当部３０１、通常仮想ノード割当部３０２および仮想リンク割当部３０３を含む。
【００７０】
連携仮想ノード割当部３０１は、前記図６のフローチャートを参照して説明したように、共用基盤ノードsnごとに、他の共用基盤ノードsnまでの基盤ネットワークSN上での平均距離を算出し、その昇順に各共用基盤ノードsnをソートする（ステップＳ１０１，Ｓ１０２）。
【００７１】
さらに、連携仮想ノードvnごとに、他の連携仮想ノードvnまでの連携仮想ネットワークVN上での平均距離を算出し、その昇順に各連携仮想ノードvnをソートする（ステップＳ１０３，Ｓ１０４）。そして、各連携仮想ノードvnを、平均距離のソート順が等しい各共用基盤ノードに割り当てる。
【００７２】
通常仮想ノード割当部３０２は、前記図５のフローチャートを参照して説明したように、前記第２計算部が計算した基盤ネットワーク上での各距離sdistanceと、前記第１計算部２０１が計算した仮想ネットワーク上での対応する各距離vdistanceとの距離比(sdistance/vdistance)が所定の基準値marginを下回ると、選択した通常仮想ノードを今回の割当先候補の基盤ノードへ割り当てる。
【００７３】
仮想リンク割当部３０３は、前記図４のステップＳ５，Ｓ６，Ｓ７に関して説明したように、連携仮想ネットワークVNの仮想リンクvlの一つを、その要求帯域を指標とする降順で順次に選択し、これを基盤ネットワークSNの基盤パスに割り当てることを繰り返す。
【符号の説明】
【００７４】
１０…ノード選択部，２０…距離計算部，３０…割当部，１０１…第１選択部，１０２…第２選択部，２０１…第１計算部，２０２…第２計算部，３０１…連携仮想ノード割当部，３０２…通常仮想ノード割当部，３０３…仮想リンク割当部
【図１】
2020014111.tif 000006
【図２】
2020014111.tif 000007
【図３】
2020014111.tif 000008
【図４】
2020014111.tif 000009
【図５】
2020014111.tif 000010
【図６】
2020014111.tif 000011
【図７】
2020014111.tif 000012