(57)【要約】【課題】サービス連携機能を有する１個の共用基盤ノードに障害が発生しても、他の共用基盤ノードを用いてサービス連携を継続できる連携型仮想ネットワーク割当を実現する。【解決手段】高信頼連携型仮想ネットワーク割当装置１は、拡張グラフ生成部１０および混合整数計画法モデル求解部２０を含む。拡張グラフ生成部１０は、基盤ネットワークグラフに対して、高信頼連携型仮想ネットワークVNを構成する各仮想ノードに対応する拡張ノードを追加したうえで、各拡張ノードを、対応する仮想ノードの割当てが可能な基盤ノード群と拡張リンクによって接続して拡張グラフを生成する。混合整数計画法モデル求解部２０は、拡張グラフ上の混合整数計画法モデルを、一般的制約条件，予備容量確保条件および接続性維持条件の各制約条件下で求解することによって高信頼連携型仮想ネットワークの基盤ネットワークへの割当てを行う。【選択図】図４
2020120269.tif 000002
【特許請求の範囲】
【請求項１】
共用基盤ノードを含む基盤ノード群から構成される基盤ネットワークに、連携仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割当てる方法において、
基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手順と、
仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手順と、
前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手順と、
前記拡張グラフ上で、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性が維持される接続性維持制約条件、を含む混合整数計画法モデルを求解する手順とを含むことを特徴とする連携型仮想ネットワーク割当方法。
【請求項２】
共用基盤ノードを含む基盤ノード群から構成される基盤ネットワークに、通常仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割当てる方法において、
基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手順と、
仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手順と、
前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手順と、
前記拡張グラフ上で、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する容量維持制約条件、を含む混合整数計画法モデルを求解する手順とを含むことを特徴とする連携型仮想ネットワーク割当方法。
【請求項３】
前記混合整数計画法モデルを求解する手順は、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する容量維持制約条件、を更に含む混合整数計画法モデルを求解することを特徴とする請求項１に記載の連携型仮想ネットワーク割当方法。
【請求項４】
前記混合整数計画法モデルを求解する手順は、各基盤ノードに確保する容量、各基盤リンクに確保する帯域および各共用基盤ノードに確保する予備容量の総和を、最小化すべき総コストとして求解することを特徴とする請求項２または３に記載の連携型仮想ネットワーク割当方法。
【請求項５】
前記混合整数計画法モデルを求解する手順は、基盤リンクの空き帯域および基盤ノードの空き容量に、相互に反比例する重み付けを行うことを特徴とする請求項４に記載の連携型仮想ネットワーク割当方法。
【請求項６】
前記拡張グラフを生成する手順は、前記基盤ネットワークを表すグラフに対して、割当対象の高信頼連携型仮想ネットワークを構成する各仮想ノードに対応する拡張ノードを追加し、当該仮想ノードを割当てることが可能な全ての基盤ノードとの間に拡張リンクを設定することを特徴とする請求項１ないし５のいずれかに記載の連携型仮想ネットワーク割当方法。
【請求項７】
共用基盤ノードを含む基盤ノード群から構成される基盤ネットワークに、連携仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割当てる装置において、
基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、各基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手段と、
仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手段と、
前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手段と、
前記拡張グラフ上で、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性が維持される接続性維持制約条件、を含む混合整数計画法モデルを求解する手段とを含むことを特徴とする連携型仮想ネットワーク割当装置。
【請求項８】
共用基盤ノードを含む基盤ノード群から構成される基盤ネットワークに、通常仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割当てる装置において、
基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、各基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手段と、
仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手段と、
前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手段と、
前記拡張グラフ上で、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する容量維持制約条件、を含む混合整数計画法モデルを求解する手段とを含むことを特徴とする連携型仮想ネットワーク割当装置。
【請求項９】
前記混合整数計画法モデルを求解する手段は、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する容量維持制約条件、を更に含む混合整数計画法モデルを求解することを特徴とする請求項１に記載の連携型仮想ネットワーク割当装置。
【請求項１０】
前記混合整数計画法モデルを求解する手順は、各基盤ノードに確保する容量、各基盤リンクに確保する帯域および各共用基盤ノードに確保する予備容量の総和を、最小化すべき総コストとして求解することを特徴とする請求項８または９に記載の連携型仮想ネットワーク割当装置。
【請求項１１】
前記混合整数計画法モデルを求解する手順は、基盤リンクの空き帯域および基盤ノードの空き容量に、相互に反比例する重み付けを行うことを特徴とする請求項１０に記載の連携型仮想ネットワーク割当装置。
【請求項１２】
前記拡張グラフを生成する手段は、前記基盤ネットワークを表すグラフに対して、割当対象の高信頼連携型仮想ネットワークを構成する各仮想ノードに対応する拡張ノードを追加し、当該仮想ノードを割当てることが可能な全ての基盤ノードとの間に拡張リンクを設定することを特徴とする請求項７ないし１１のいずれかに記載の連携型仮想ネットワーク割当装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サービス連携機能を有する基盤ノードを互いに共用する連携型仮想ネットワークを基盤ネットワークに割当てる方法および装置に係り、特に、サービス連携機能を有する１個の共用基盤ノードに障害が発生しても、他の共用基盤ノードを用いてサービス連携を継続できる連携型仮想ネットワーク割当方法および装置に関する。
【背景技術】
【０００２】
非特許文献１には、各仮想ノードと当該仮想ノードの割当てが可能な全ての基盤ノードとを拡張リンクを用いて接続することによって、基盤ネットワークを表すグラフを拡張し、本拡張グラフ上での数理計画モデルを使って仮想ネットワークの基盤ネットワークへの割当てを実現する方法が開示されている。
【０００３】
非特許文献２には、予め予備仮想ノードと予備仮想ノードに接続される予備仮想リンクとを確保しておき、単一基盤ノード障害が発生した際には、予備仮想ノードも含めて仮想ノードを再配置することにより、仮想ネットワーク構成を維持するような高信頼仮想ネットワークの基盤ネットワークへの割当て方法が開示されている。
【０００４】
特許文献１および２には、各仮想ノードと当該仮想ノードの割当てが可能な全ての基盤ノードとを、拡張リンクを用いて接続することによって、基盤ネットワークを表すグラフを拡張し、本拡張グラフ上で逐次的に各仮想リンクを最小コスト経路に割当てることによって、当該仮想リンクを割当てる基盤パスと当該仮想リンクが接続する仮想ノードの基盤ノードへの割当てを決定して行く方法が開示されている。
【０００５】
特許文献３には、サービス連携機能を有する基盤ノードを互いに共用する連携型仮想ネットワークの基盤ネットワークへの割当てに関して、連携仮想ノード群の共用基盤ノード群への割当てを最初の基準点として、仮想ネットワーク上の仮想ノード間の距離と基盤ネットワーク上の対応する基盤ノード間の距離との比率が均一かつ最小となるように、逐次的に各仮想ノードを基盤ノードへ割当てる方法が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第６２７９４２７号公報
【特許文献２】特許第６３０７３７７号公報
【特許文献３】特願２０１８−１３４８２５号
【非特許文献】
【０００７】
【非特許文献１】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.
【非特許文献２】B. Guo et al., "Survivable virtual network design and embedding to survive a facility node failure," IEEE JLT, vol. 32, no. 3, pp. 483-493, Feb. 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１では、仮想ノードが割当てられている基盤ノードに障害が発生した場合、当該仮想ノードが持つ機能を維持することができない。非特許文献２では、サービス連携機能を有する予備の共用基盤ノードを用意する必要がある。
【０００９】
特許文献１および２では、最小コスト経路に割当てる仮想リンクの順番によっては、効率的な仮想ネットワーク割当てが実現できない場合が存在する。
【００１０】
特許文献３では、連携仮想ノードが割当てられている共用基盤ノードに障害が発生した場合、サービス連携機能に対する処理容量が不足し、サービス連携機能を利用できなくなる仮想ノードが発生する恐れがある。
【００１１】
本発明の目的は、上記の技術課題を解決し、連携仮想ノードが割当てられた共用基盤ノード群に予備容量を予め確保しておき、更には正常な連携仮想ノードと全ての仮想ノードとの接続性が維持されるようにすることで、一つの共用基盤ノードに障害が発生した場合でもサービス連携を継続できる高信頼連携型仮想ネットワークを基盤ネットワークへ割当てる方法および装置を提供することにある。
【課題を解決するための手段】
【００１２】
上記の目的を達成するために、本発明は、共用基盤ノードを含む基盤ノード群から構成される基盤ネットワークに、連携仮想ノードを含む仮想ノード群から構成される仮想ネットワークを割当てる方法、装置において、以下の構成を具備した点に特徴がある。
【００１３】
(1) 基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、各基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手順（手段）と、仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手順（手段）と、前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手順（手段）と、前記拡張グラフ上で、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性が維持される接続性維持制約条件、を含む混合整数計画法モデルを求解する手順（手段）とを具備した。
【００１４】
(2) 基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手順（手段）と、仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手順（手段）と、前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手順（手段）と、前記拡張グラフ上で、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する容量維持制約条件、を含む混合整数計画法モデルを求解する手順（手段）とを具備した。
【００１５】
(3) 基盤ネットワークのトポロジー情報、共用基盤ノードの識別情報、各基盤ノードの空き容量および各基盤リンクの空き帯域を含む基盤ネットワーク情報を取得する手順（手段）と、仮想ネットワークのトポロジー情報、連携仮想ノードの識別情報、各仮想ノードの要求容量および各仮想リンクの要求帯域を含む連携型仮想ネットワーク割当要求を取得する手順（手段）と、前記基盤ネットワーク情報および連携型仮想ネットワーク割当要求に基づいて、前記基盤ネットワークを表すグラフを拡張した拡張グラフを生成する手順（手段）と、前記拡張グラフ上で、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性が維持される接続性維持制約条件、および共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する容量維持制約条件、を含む混合整数計画法モデルを求解する手順（手段）とを具備した。
【００１６】
(4) 混合整数計画法モデルを求解する際、各基盤ノードに確保する容量、各基盤リンクに確保する帯域および各共用基盤ノードに確保する予備容量の総和を、最小化すべき総コストとして求解するようにした。
【００１７】
(5) 混合整数計画法モデルを求解する際、基盤リンクの空き帯域および基盤ノードの空き容量に、相互に反比例する重み付けを行うようにした。
【００１８】
(6) 拡張グラフを生成する手順（手段）は、前記基盤ネットワークを表すグラフに対して、割当対象の高信頼連携型仮想ネットワークを構成する各仮想ノードに対応する拡張ノードを追加し、当該仮想ノードを割当てることが可能な全ての基盤ノードとの間に拡張リンクを設定するようにした。
【発明の効果】
【００１９】
本発明によれば、以下のような効果が達成される。
(1) 混合整数計画法モデルを求解する際に、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性を維持できる接続性維持条件、を制約条件としたので、サービス連携機能を有する１個の共用基盤ノードが障害になった場合でも、他の共用基盤ノードを用いてサービス連携を継続できる高信頼連携型仮想ネットワークを効率的に基盤ネットワークへ割当てることができる。
【００２０】
(2) 混合整数計画法モデルを求解する際に、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する予備容量確保条件、を制約条件としたので、サービス連携機能を有する１個の共用基盤ノードが障害になった場合でも、その共用基盤ノードに割当てられていた連携仮想ノードに対応する予備容量を確保した共用基盤ノードと他の仮想ノードとの接続性が維持されるときは、障害の発生した共用基盤ノードに割当てられていた連携仮想ノードが提供するサービスを、そのパフォーマンスを維持したまま継続できる高信頼連携型仮想ネットワークを基盤ネットワークへ割当てることができる。
【００２１】
(3) 混合整数計画法モデルを求解する際に、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性を維持できる接続性維持条件、および共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保する予備容量確保条件、を制約条件としたので、サービス連携機能を有する１個の共用基盤ノードが障害になった場合でも、他の共用基盤ノードを用いて、パフォーマンスを低下させることなくサービス連携を継続できる高信頼連携型仮想ネットワークを基盤ネットワークへ割当てることができる。
【００２２】
(4) 混合整数計画法モデルを求解する際、各基盤ノードに確保する容量、各基盤リンクに確保する帯域および各共用基盤ノードに確保する予備容量の総和を、最小化すべき総コストとして求解するので、所要基盤リンク帯域および所要基盤ノード帯域の削減が可能になる。
【００２３】
(5) 混合整数計画法モデルを求解する際、基盤リンクの空き帯域および基盤ノードの空き容量に、相互に反比例する重み付けを行うようにしたので、各基盤リンクへのトラヒック負荷および各基盤ノードへの処理負荷の均一化が図られ、割当て可能な高信頼連携型仮想ネットワーク数の増加が期待される。
【００２４】
(6) 拡張グラフを生成する手段は、基盤ネットワークグラフに対して、割当対象である高信頼連携型仮想ネットワークを構成する各仮想ノードに対応する拡張ノードを追加し、当該仮想ノードを割当てることが可能な全ての基盤ノードとの間に拡張リンクを設定するようにしたので、各連携仮想ノードを、それぞれ異なる１個の共用基盤ノードに割当てる割当てが可能になる。
【図面の簡単な説明】
【００２５】
【図１】共用基盤ノード群を含む基盤ネットワークに対して連携仮想ノード群を含む連携型仮想ネットワークを割当てる方法を模式的に示した図である。
【図２】従来の基盤ネットワークに対する連携型仮想ネットワークの割当て例を示した図である。
【図３】本発明の一実施形態に係る基盤ネットワークに対する連携型仮想ネットワークの割当て例を示した図である。
【図４】本発明の第１実施形態にかかる高信頼連携型仮想ネットワーク割当装置の主要部の構成を示した機能ブロック図である。
【図５】図１に示した高信頼連携型仮想ネットワークおよび基盤ネットワークに基づいて生成した拡張グラフを示している。
【図６】本発明の第２実施形態にかかる高信頼連携型仮想ネットワーク割当装置の主要部の構成を示した機能ブロック図である。
【図７】本発明の第３実施形態にかかる高信頼連携型仮想ネットワーク割当装置の主要部の構成を示した機能ブロック図である。
【発明を実施するための形態】
【００２６】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、サービス連携機能を有する共用基盤ノード群を含む基盤ネットワークSNに対して、連携仮想ノード群を含む連携型仮想ネットワークVNを割当てる方法を模式的に示した図であり、図２は、基盤ネットワークSNに対する連携型仮想ネットワークVNの割当て例を示した図である。本実施形態では、サービス連携機能を有する１個の共用基盤ノードに障害が発生しても他の共用基盤ノードを用いてサービス連携を継続できる、高信頼連携型仮想ネットワークが基盤ネットワークに割当てられる。
【００２７】
高信頼連携型仮想ネットワークVNは、図１に示したように、ハッチング（●）で示した連携仮想ノードvn（vn1，vn2）と、それ以外の白丸（○）で示した通常仮想ノードvn（vn3，vn4）とを仮想リンクvlで連結して構成される。基盤ネットワークSNは、ハッチングで示した共用基盤ノードsn（sn1，sn4，sn6）と、それ以外の白丸で示した通常基盤ノードsn（sn2，sn3…）とを基盤リンクで連結して構成される。
【００２８】
高信頼連携型仮想ネットワークVNの連携仮想ノードvn（群）および基盤ネットワークSNの共用基盤ノードsn（群）は予め指定されている。共用基盤ノードsnには、各連携型仮想ネットワークVNが共有するデータを管理するサーバ（図示省略）が接続されている。
【００２９】
また、高信頼連携型仮想ネットワークVNを構成する各連携仮想ノードvnおよび各通常仮想ノードvn（以下、「仮想ノード」で総称する場合もある）の要求容量および各仮想リンクvlの要求帯域は予め与えられる。同様に、基盤ネットワークSNを構成する各共用基盤ノードsnおよび各通常基盤ノードsn（以下、「基盤ノード」で総称する場合もある）の空き容量および各基盤リンクの空き帯域も予め与えられる。
【００３０】
前記要求容量の指標としては、例えば仮想ノードを構成するコンピュータのリソース（メモリ、CPU、ディスク記録媒体など）の要求容量や要求稼働率を用いることができる。前記空き容量の指標としては、例えば基盤ノードを構成するコンピュータのリソースの空き容量や空き稼働率を用いることができる。
【００３１】
高信頼連携型仮想ネットワークVNを構成する各連携仮想ノードvnは、それぞれ異なる１個の共用基盤ノードsnに割当てられ、各通常仮想ノードvnは、それぞれ異なる１個の基盤ノードsnに割当てられる。図２の例では、連携仮想ノードvn1，vn2が、それぞれ共用基盤ノードsn6，sn1に割当てられ、通常仮想ノードvn3，vn4が、それぞれ基盤ノードsn3，sn7に割当てられている。各仮想ノードvnの割当ては、基盤ノードsnの空き容量を超えて行う事はできない。
【００３２】
高信頼連携型仮想ネットワーVNを構成する各仮想リンクvlは、当該仮想リンクvlの両端に接続された仮想ノードvnが割当てられる基盤ノードsn間を接続する１本の基盤パスに割当てられる。各仮想リンクvlの割当ては、基盤パスを構成する各基盤リンクの空き帯域を超えて行う事はできない。
【００３３】
図３は、本実施形態における高信頼連携型仮想ネットワークの基盤ネットワークへの割当て例を、図２に示した従来の割当て例との比較において示した図であり、連携仮想ノードvn1，vn2は、それぞれ共用基盤ノードsn6，sn1に割当てられ、通常仮想ノードvn3，vn4は、それぞれ基盤ノードsn3，sn7に割当てられている。
【００３４】
図２の例では、仮想リンクvl4は基盤パスsn3−sn1−sn7に割当てられる。このとき、仮想リンクvl4の割当ては、基盤リンクsn3−sn1および基盤リンクsn1− sn7の空き帯域を超えて行う事はできない。
【００３５】
図３の例では、仮想リンクvl4は基盤パスsn3−sn4−sn7に割当てられる。このとき、仮想リンクvl4の割当ては、基盤リンクsn3−sn4および基盤リンクsn4−sn7の空き帯域を超えて行う事はできない。
【００３６】
本実施形態の高信頼連携型仮想ネットワーク割当方法では、連携仮想ノードが割当てられている共用基盤ノード群に予備容量を予め確保しておき、１個の共用基盤ノードに障害が発生して当該共用基盤ノードを割当てられていた連携仮想ノードとの接続性が失われても、他の正常な連携仮想ノードと全ての仮想ノードとの接続性が維持されるように、高信頼連携型仮想ネットワークVNを基盤ネットワークSNへ割当てる。
【００３７】
図２，３に示した割当て例では、連携仮想ノードvn1，vn2が共用基盤ノードsn6，sn1に割当てられているので、共用基盤ノードsn6に障害が発生した際にもサービス連携機能を維持するために、予め連携仮想ノードvn1の要求容量分の予備容量を共用基盤ノードsn1に確保して置く。
【００３８】
また、共用基盤ノードsn1に障害が発生した際にもサービス連携機能を維持するために、予め連携仮想ノードvn2の要求容量分の予備容量を共用基盤ノードsn6に確保して置く。
【００３９】
さらに、図２の割当て例では、共用基盤ノードsn1に障害が発生した際、共用基盤ノードsn1を経由している仮想リンクvl4も障害となり、仮想ノードvn3は正常な連携仮想ノードvn1から連携サービスを受けられなくなる。
【００４０】
一方、図３の割当て例では、共用基盤ノードsn1に障害が発生した際にも、仮想ノードvn3と正常な連携仮想ノードvn1の接続性が保たれ、仮想ノードvn3は連携仮想ノードvn1から継続して連携サービスを受けられる。そこで、本実施形態では、図２に例示した高信頼連携型仮想ネットワークの割当ては避けて、図３に例示した高信頼連携型仮想ネットワークの割当てを実現する。
【００４１】
図４は、本発明の一実施形態に係る高信頼連携型仮想ネットワークの基盤ネットワークへの割当方法を適用した高信頼連携型仮想ネットワーク割当装置１の主要部の構成を示した機能ブロック図であり、拡張グラフ生成部１０および混合整数計画法モデル求解部２０を主要な構成としている。
【００４２】
このような高信頼連携型仮想ネットワーク割当装置１は、汎用のコンピュータやサーバに各機能を実現するアプリケーション（プログラム）を実装することで構成できる。あるいはアプリケーションの一部がハードウェア化またはROM化された専用機や単能機としても構成できる。
【００４３】
本実施形態では、基盤ネットワーク情報および高信頼連携型仮想ネットワーク割当要求が入力情報として与えられる。前記基盤ネットワーク情報は、基盤ネットワークのトポロジー情報、共用基盤ノードを識別する共用基盤ノード情報、各基盤ノードの空き容量および各基盤リンクの空き帯域で構成される。前記高信頼連携型仮想ネットワーク割当要求は、仮想ネットワークのトポロジー情報、連携仮想ノードを識別する連携仮想ノード情報、各仮想ノードの要求容量および各仮想リンクの要求帯域で構成される。
【００４４】
前記拡張グラフ生成部１０は、前記２つの入力情報に基づき、混合整数計画法モデルの対象となる拡張グラフを生成する。拡張グラフは、図５に示したように、基盤ネットワークグラフに対して、高信頼連携型仮想ネットワークVNを構成する各仮想ノードに対応する拡張ノードを追加したうえで、各拡張ノードを、対応する仮想ノードの割当てが可能な基盤ノード群と拡張リンクによって接続して構成される。
【００４５】
連携仮想ノードは共用基盤ノードのみに割当て可能なので、連携仮想ノードに対応する拡張ノードvn1，vn2は、いずれも拡張リンクによって共用基盤ノードsn1，sn4，sn6のみに接続される。一方、通常仮想ノードは共用基盤ノードを含む全ての基盤ノードに割当て可能なので、通常仮想ノードに対応する拡張ノードvn3，vn4は、いずれも拡張リンクによって全ての基盤ノードに接続される。
【００４６】
混合整数計画法モデル求解部２０は、前記生成した拡張グラフ上の混合整数計画法モデルを、所定の制約条件下で求解することによって高信頼連携型仮想ネットワークの基盤ネットワークへの割当てを行う。
【００４７】
本実施形態の混合整数計画法モデルには、連携型仮想ネットワーク割当に要求される一般的な制約条件（一般的制約条件：次式(1)−(10)）に加えて、(1)共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保するための制約条件（予備容量確保条件：次式(11)−(13））と、(2)１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性を維持するための制約条件（接続性維持条件：次式(14)−(18））とが含まれる。
【００４８】
以下の説明では、混合整数計画法モデルにおける各定数および各集合を以下の様に定義する。
SN：基盤ノード集合（基盤ネットワークのトポロジー情報）
SSN：共用基盤ノード集合（共用基盤ノード情報）
SL：基盤リンク集合（基盤ネットワークのトポロジー情報）
SC w：基盤ノード w の空き容量
SB u, v：基盤リンク (u, v) の空き帯域
EN：拡張（仮想）ノード集合（仮想ネットワークのトポロジー情報）
CEN：連携仮想ノード群に対応する拡張（仮想）ノード集合（連携仮想ノード情報）
EL：拡張リンク集合（仮想ネットワークのトポロジー情報）
VC m：仮想ノード m の要求容量
VB i：仮想リンク i の要求帯域
INOUT n：拡張グラフ上のノードnの接続リンク集合（仮想ネットワークのトポロジー情報）
s i：仮想リンク i の始点拡張（仮想）ノード
t i：仮想リンク i の終点拡張（仮想）ノード
α u, v：基盤リンク (u, v) の重み（単位帯域当たりのコスト）
β w：基盤ノード w の重み（単位容量当たりのコスト）
weight：基盤リンクと基盤ノードのコスト比（0.0≦weight≦1.0）
A：十分大きな値を持つ定数。
【００４９】
また、混合整数計画法モデルにおける変数を以下の様に定義する。
x iu, v：仮想リンクi が割当てられた基盤パスが基盤・拡張リンク (u, v) を通過するか否かを示すバイナリ―変数。
y iw：仮想リンクi が割当てられた基盤パスが基盤ノードw を通過するか否かを示すバイナリ―変数。
z m, w：拡張ノードmに対応する仮想ノードが基盤ノードwに割当てられたか否かを示すバイナリ―変数。
svc cm, sw：拡張ノードcmに対応する連携仮想ノードが共用基盤ノードswに割当てられた時に、共用基盤ノードswに確保される予備容量を示す実変数。
vxi ssn, vn0, vn：共用基盤ノードssnの障害時に、通常仮想ノードvn0と仮想ノードvnを接続する仮想パスが仮想リンクiを通過するか否かを示すバイナリ―変数。
vym ssn, vn0, vn：共用基盤ノードssnの障害時に、通常仮想ノードvn0と仮想ノードvnを接続する仮想パスが仮想ノードmを通過するか否かを示すバイナリ―変数。
【００５０】
混合整数計画法モデルに基づく従来の連携型仮想ネットワーク割当てに関して本実施形態が採用する制約条件（一般的制約条件）は、次式(1)−(10)の通りである。
【００５１】
（通常基盤ノードの容量制約）
仮想ノードの要求容量が割当先の基盤ノードの空き容量よりも小さくなければならない制約条件であり、次式(1)で与えられる。
【００５２】
【数１】
2020120269.tif 000003
【００５３】
（基盤リンクの帯域制約）
仮想リンクの要求帯域が割当先の基盤リンクの空き帯域よりも小さくなければならない制約条件であり、次式(2)で与えられる。
【００５４】
【数２】
2020120269.tif 000004
【００５５】
（仮想リンクが割当てられた基盤パス制約）
仮想リンクが割当てられた基盤パスは、出リンクおよび入リンクとして中継基盤ノードの接続リンクを２回通り、非中継基盤ノードの接続リンクは１回も通らず、更に始点ノードの接続リンクおよび終点ノードの接続リンクを１回だけ通るというパス保存則であり、次式(3)，(4)で与えられる。
【００５６】
【数３】
2020120269.tif 000005
【００５７】
【数４】
2020120269.tif 000006
【００５８】
（変数の関係制約）
【００５９】
【数５】
2020120269.tif 000007
【００６０】
（仮想ノードの割当制約）
各拡張ノードは各基盤ノードに１回だけ割当てられ、各基盤ノードには高々１個の拡張ノードが割当てられるという制約条件であり、次式(6)，(7)で与えられる。
【００６１】
【数６】
2020120269.tif 000008
【００６２】
（変数の値域制約）
【００６３】
【数７】
2020120269.tif 000009
【００６４】
また、共用基盤ノードに割当てられた連携仮想ノード容量以上の予備容量を当該共用基盤ノード以外の共用基盤ノードに確保するための制約条件（予備容量確保条件）は、次式(11)−(13）の通りである。
【００６５】
（変数の関係制約）
仮想ノードが割当てられていない共用基盤ノードに確保される予備容量が０となる制約条件であり、次式(11)で与えられる。
【００６６】
【数８】
2020120269.tif 000010
【００６７】
（予備容量に関する制約）
ある共用基盤ノード以外の共用基盤ノードに確保する予備容量の合計は、当該共用基盤ノードに割当てられた連携仮想ノードの要求容量以上でなければならないという制約条件であり、次式(12)で与えられる。
【００６８】
【数９】
2020120269.tif 000011
【００６９】
（共用基盤ノードの容量制約）
共用基盤ノードに連携仮想ノードが割当てられるとき、予備容量を含めた要求容量は共用基盤ノードの空き容量以下でなければならないという制約条件であり、次式(13)で与えられる。
【００７０】
【数１０】
2020120269.tif 000012
【００７１】
さらに、１個の共用基盤ノードに障害が発生した際にも正常な連携仮想ノードと全ての仮想ノードとの接続性を維持するための制約条件（接続制約条件）は、次式(14)−(18)の通りである。
【００７２】
（共用基盤ノード障害時の障害仮想リンク）
共用基盤ノードの障害発生時における高信頼連携型仮想ネットワークの連結性に関する制約条件は、仮想リンクiが割当てられた基盤パスが共用基盤ノードssnを通る時、共用基盤ノードssnに障害が発生した際には、通常仮想ノードvn0と仮想ノードvnを接続する仮想パスは仮想リンクiを通過しないことであり、次式(14)で与えられる。
【００７３】
【数１１】
2020120269.tif 000013
【００７４】
（共用基盤ノード障害時における２個の仮想ノード間の仮想パス制約）
共用基盤ノードssnに障害が発生した際には、通常仮想ノードvn0と共用基盤ノードssnに割当てられた仮想ノード以外の仮想ノードvn （z vn, ssn = 0）とを接続する仮想パスに関して、制約条件(3)および(4)と同様のパス保存則が成り立たなければならない。ここで以下の制約条件(15)は制約条件(3)に対応し、以下の制約条件(16)は制約条件(4)に対応する。仮想ノードvnが、共用基盤ノードssnに割当てられた仮想ノードである場合は（z vn, ssn = 1）、Aが十分大きな値を持つ定数であるため、制約条件(15)および(16)は無効となる。
【００７５】
【数１２】
2020120269.tif 000014
【００７６】
【数１３】
2020120269.tif 000015
【００７７】
（変数の値域制約）
【００７８】
【数１４】
2020120269.tif 000016
【００７９】
混合整数計画法モデルにおいて最小化すべき総コストは、各基盤ノードに確保する容量、各基盤リンクに確保する帯域および各共用基盤ノードに確保する予備容量の総和であり、次式(19)で与えられる。
【００８０】
【数１５】
2020120269.tif 000017
【００８１】
上式(20)，(21)で表される重みは、所要基盤リンク帯域および所要基盤ノード帯域の削減に加えて、各基盤リンクへのトラヒック負荷および各基盤ノードへの処理負荷の均一化を目的としている。すなわち基盤リンクの空き帯域および基盤ノードの空き容量に反比例する重みを用いることによって、大きな帯域を要求する仮想リンクは大きな空き帯域を有する基盤リンクに割当てられ易くなり、大きな容量を要求する仮想ノードは大きな空き容量を有する基盤ノードに割当てられ易くなる。各基盤リンクへのトラヒック負荷および各基盤ノードへの処理負荷の均一化を図ることにより、割当て可能な高信頼連携型仮想ネットワーク数の増加が期待される。
【００８２】
なお、上記の実施形態では、混合整数計画法モデル求解部２０が、一般的制約条件，予備容量確保条件および接続性維持条件の３つの制約条件下で混合整数計画法モデルを求解するものとして説明したが、本発明はこれのみに限定されるものではなく、図６に示した第２実施形態のように、一般的制約条件および接続性維持条件の２つの制約条件下で求解するようにしても良い。具体的には、制約条件(11)および(12)を削除し、制約条件(13)の代わりに、共用基盤ノードに関しても制約条件(1)を適用する。
【００８３】
第２実施形態によれば、障害の発生した共用基盤ノードに割当てられていた連携仮想ノードの要求容量を他の一の共用基盤ノード上に確保できない。しかしながら、接続性維持条件を充足しており、ノード間の接続性は維持されている。したがって、障害の発生した共用基盤ノードに割当てられていた連携仮想ノードが提供するサービスを、多少のパフォーマンス低下は余儀なくされるものの継続できる高信頼連携型仮想ネットワーク割当てが可能になる。
【００８４】
さらに、図７に示した第３実施形態のように、一般的制約条件および予備容量確保条件の２つの制約条件下で求解するようにしても良い。具体的には、制約条件(14)−(18)を除いて求解する。
【００８５】
第３実施形態によれば、障害の発生した共用基盤ノードに割当てられていた連携仮想ノードの要求容量を他の一の共用基盤ノード上に確保できるので、サービス連携機能を有する１個の共用基盤ノードが障害になった場合でも、その共用基盤ノードに割当てられていた連携仮想ノードに対応する予備容量を確保した共用基盤ノードと他の仮想ノードとの接続性が維持されるときは、障害の発生した共用基盤ノードに割当てられていた連携仮想ノードが提供するサービスを、そのパフォーマンスを維持したまま継続できる高信頼連携型仮想ネットワーク割当てが可能になる。
【符号の説明】
【００８６】
１…高信頼連携型仮想ネットワーク割当装置，１０…拡張グラフ生成部，２０…第１実施形態に係る混合整数計画法モデル求解部，３０…第２実施形態に係る混合整数計画法モデル求解部，４０…第３実施形態に係る混合整数計画法モデル求解部
【図１】
2020120269.tif 000018
【図２】
2020120269.tif 000019
【図３】
2020120269.tif 000020
【図４】
2020120269.tif 000021
【図５】
2020120269.tif 000022
【図６】
2020120269.tif 000023
【図７】
2020120269.tif 000024