(57)【特許請求の範囲】
【請求項１】
SDNのスライス間で物理リソース帯域を共用する仮想ネットワークを物理ネットワークに割り当てる仮想ネットワーク割当装置において、
物理ネットワークのトポロジー情報、既存仮想ネットワークの情報および物理ネットワークへ新規に割り当てる割当要求仮想ネットワークの情報を取得する手段と、
前記各情報に基づいて、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ノード候補を選択する手段と、
前記物理ネットワークのトポロジーに、割当要求仮想ネットワークの各仮想ノードに対応する擬似ノードを仮想的に追加し、当該各仮想ノードを割り当て可能な全ての物理ノード候補と当該擬似ノードとの間に擬似リンクを設定する物理ネットワーク拡張手段と、
拡張された物理ネットワーク上で、各仮想ノードが対応する擬似ノードに割り当てられたものとしてスライス実行におけるスケジューリングコストの総和を最小化する仮想ネットワーク割当を整数計画法モデルの解として計算する手段とを具備したことを特徴とする仮想ネットワーク割当装置。
【請求項２】
前記物理リソース帯域が物理リンク帯域であり、最小化するスケジューリングコストが、各物理リンクにおけるパケット転送のスケジューリングコストの総和であることを特徴とする請求項１に記載の仮想ネットワーク割当装置。
【請求項３】
前記物理リソース帯域が物理ノード帯域であり、最小化するスケジューリングコストが、各物理ノードにおけるサービス処理のスケジューリングコストの総和であることを特徴とする請求項１に記載の仮想ネットワーク割当装置。
【請求項４】
前記物理リソース帯域が物理リンク帯域および物理ノード帯域であり、最小化するスケジューリングコストが、各物理リンクにおけるパケット転送のスケジューリングコストおよび各物理ノードにおけるサービス処理のスケジューリングコストの重み付き総和であることを特徴とする請求項１に記載の仮想ネットワーク割当装置。
【請求項５】
前記物理ノード候補を選択する手段は、仮想ノードごとに当該仮想ノードと予め対応付けられた一の物理ノード及びこれに隣接する少なくとも一つの物理ノードを選択することを特徴とする請求項１ないし４のいずれかに記載の仮想ネットワーク割当装置。
【請求項６】
SDNのスライス間で物理リソース帯域を共用する仮想ネットワークを物理ネットワークに割り当てる仮想ネットワーク割当方法において、
物理ネットワークのトポロジー情報および既存仮想ネットワークの情報に基づいて、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ノード候補を選択する手順と、
物理ネットワークのトポロジーに割当要求仮想ネットワークの各仮想ノードに対応する擬似ノードを仮想的に追加し、各仮想ノードを割り当て可能な全ての物理ノード候補と当該擬似ノードとの間に擬似リンクを設定して物理ネットワークを拡張する手順と、
拡張された物理ネットワーク上で、各仮想ノードが対応する擬似ノードに割り当てられたものとしてスライス実行におけるスケジューリングコストの総和を最小化する仮想ネットワーク割当を整数計画法モデルの解として計算する手順とを含むことを特徴とする仮想ネットワーク割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想リンクごとに優先クラスが指定された新たな仮想ネットワークの割当要求に対して仮想ネットワーク割当を実現する仮想ネットワーク割当方法および装置に係り、特に、SDN（Software-Defined Network）の各スライス間で、物理リンク帯域および物理ノード容量の共用を促進して、スライス実行におけるスケジューリングコストを最小化する仮想ネットワーク割当方法および装置に関する。
【背景技術】
【０００２】
ソフトウェアによって仮想的なネットワークを作り上げる技術として、非特許文献１，２にSDNが開示されている。SDNでは一つの物理ネットワーク上に「スライス」と呼ばれる完全に独立した仮想的なネットワークをいくつも構築できるため、スライスごとにユーザの要求に応じた固有のネットワークを構築できる。
【０００３】
非特許文献３には、仮想ネットワークのトポロジーが与えられた時に、仮想ノードの物理ノードへの割当と仮想リンクの物理パスへの割当を行う仮想ネットワーク割当において、まず仮想ノードの物理ノードへの割当を行い、その後、仮想リンクの物理パスへの割当を行うことによって、物理ネットワークを構成する物理ノードや物理リンクの負荷を平準化する技術が開示されている。
【０００４】
非特許文献４には、仮想ネットワーク割当において、各仮想ノードを割当てることができる物理ノードの範囲を区分けし、仮想ノードの物理ノードへの割当と仮想リンクの物理パスへの割当を同時に行うことにより、物理ネットワークを構成する物理ノードや物理リンクの負荷を平準化する技術が開示されている。
【０００５】
非特許文献５には、仮想ネットワーク割当において、仮想ネットワーク間で一部のリンク帯域を共用することによって、仮想ネットワーク割当要求の受付率を向上させる技術が開示されている。
【０００６】
特許文献１には、複数のパケット転送優先クラスを指定する仮想ネットワーク割当において、各仮想リンクにおけるパケット転送品質に影響を及ぼさない範囲で、仮想リンク間での物理リンク帯域共用を促進して、パケット転送のスケジューリングコストを最小化する技術が開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特願2013-262879号
【非特許文献】
【０００８】
【非特許文献１】「Software Defined Networkにおける制御プレーンアプリケーション開発・運用監視を目的とした統合状態収集・解析機構の検討」電子情報通信学会技術研究報告. NS, ネットワークシステム 111(408), 127-132, 2012-01-19
【非特許文献２】「OpenFlow/SDNとネットワーク仮想化」信学技報, vol. 112, no. 230, IN2012-96, pp. 115-119, 2012年10月，進藤資訓
【非特許文献３】（Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," Proc. of IEEE Infocom 2006, April 2006.）
【非特許文献４】N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," Proc. of IEEE Infocom 2009, April 2009.
【非特許文献５】（S. Zhang, Z. Qian, J. Wu, and S. Lu, "An opportunistic resource sharing and topology-aware mapping framework for virtual networks," Proc. of IEEE Infocom 2012, April 2012.）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献３，４，５では、複数の優先クラスを指定する仮想ネットワーク要求の割当てを行うことができなかった。
【００１０】
特許文献１では、複数のサービス優先クラスを指定する仮想ネットワーク割当において、各仮想ノードにおけるサービス処理品質に影響を及ぼさない範囲で、仮想ノード間での物理ノード容量の共用を促進して、サービス処理のスケジューリングコストを最小化することができなかった。
【００１１】
また、特許文献１に開示された整数計画法モデルの直接解法は大量の計算リソースを使用するので、大規模なSDNへの適用が難しいという技術課題があった。
【００１２】
本発明の目的は、上記の技術課題を解決し、大規模なSDNへの適用が可能であり、各仮想ノードにおけるサービス処理品質に影響を及ぼさない範囲でスケジューリングコストを最小化できる仮想ネットワーク割当を実現できる仮想ネットワーク割当方法および装置を提供することにある。
【課題を解決するための手段】
【００１３】
上記の目的を達成するために、本発明は、SDNのスライス間で物理リソース帯域を共用する仮想ネットワークを物理ネットワークに割り当てる仮想ネットワーク割当装置において、以下の構成を具備した点に特徴がある。
【００１４】
(1) 物理ネットワークのトポロジー情報および既存仮想ネットワークの情報に基づいて、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ノード候補を選択する手段と、物理ネットワークのトポロジーに、割当要求仮想ネットワークの各仮想ノードに対応する擬似ノードを仮想的に追加し、当該各仮想ノードを割り当て可能な全ての物理ノード候補と当該擬似ノードとの間に擬似リンクを設定する手段と、拡張された物理ネットワーク上で、各仮想ノードが対応する擬似ノードに割り当てられたものとしてスライス実行におけるスケジューリングコストの総和を最小化する仮想ネットワーク割当を整数計画法モデルの解として計算する手段とを具備した。
【００１５】
(2) 物理ノード候補を選択する手段は、仮想ノードごとに当該仮想ノードと予め対応付けられた一の物理ノード及びこれに隣接する少なくとも一つの物理ノードを選択するようにした。
【発明の効果】
【００１６】
本発明によれば、以下のような効果が達成される。
(1) 各仮想ノードの割当候補となる物理ノードが、予め対応付けられた物理ノードおよび当該物理ノードに隣接する物理ノードの中のいずれか一つに制限されるので、整数計画法モデルによる解法を採用しても計算リソースの使用量を大幅に減ぜられるようになる。
【００１７】
(2) 各仮想ノードは、予め当該仮想ノードと対応付けられた物理ノードまたはその隣接ノードのいずれか一つに割当てられるので、仮想ノードがいずれの物理ノードへ割り当てられても仮想ノードへのアクセス遅延を抑えながらパスの多様性を確保できるようになる。
【００１８】
(3) SDNにおいて、指定された優先クラスに基づくサービス品質へ影響が及ばない範囲で、各スライス間での物理リンク帯域および物理ノード容量の共用を促進して、スライス実行におけるスケジューリングコストを最小化する仮想ネットワーク割当を実現できるようになる。
【００１９】
(4) 各スライス間で物理リンク帯域および物理ノード容量の共用が促進されるので、統計多重効果によって物理リンク帯域および物理ノード容量の利用効率が向上する。
【図面の簡単な説明】
【００２０】
【図１】SDNスライス間でのパケット転送キューの共用による物理リンク帯域の共用方法を模式的に表現した図である。
【図２】SDNスライス間でのトランザクションキューの共用による物理ノード容量の共用方法を模式的に表現した図である。
【図３】本発明の一実施形態に係る仮想ネットワーク割当装置の主要部の構成を示した機能ブロック図である。
【図４】物理ネットワークの拡張例を示した図である。
【図５】物理ネットワークのトポロジー情報、割当要求仮想ネットワークおよび仮想ネットワークの割当結果の一例を示した図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。ここでは初めに、SDNにおけるスライス間での物理リソース帯域の共用によるスケジューリングコストの削減について、(1)パケット転送キューの共用による物理リンク帯域の共用および(2)トランザクションキューの共用による物理ノード容量の共用を例に説明する。
【００２２】
なお、本実施形態では、物理リンク帯域および物理ノード容量を併せて物理リソース帯域と表現するものとし、物理ノード容量についても、物理リンク帯域に合わせて物理ノード帯域と表現する場合もある。
【００２３】
図１は、一の物理リンクに着目して、SDNスライス間でのパケット転送キューの共用による物理リンク帯域の共用方法を模式的に表現した図であり、同図(a)は共用前、同図(b)は共用後を表している。
【００２４】
本発明では、いずれのスライスにおいても、フロー単位で優先度設定が可能であり、高優先のフローを収容する仮想リンクは高優先仮想リンクとされ、低優先のフローを収容する仮想リンクは低優先仮想リンクとされる。
【００２５】
図示の例では、着目した物理リンクを、スライス#1，#2では高優先仮想リンクおよび低優先仮想リンクが通過し、スライス#3，#4では高優先の仮想リンクのみが通過し、スライス#5，#6では低優先の仮想リンクのみが通過している。高優先仮想リンクのパケット転送キューには、低優先仮想リンクのパケット転送キューよりも高い優先度でスケジューリング機会が与えられる。
【００２６】
ここで、異なるスライス上の仮想リンク同士であっても、同一の優先クラスに属する仮想リンク同士での物理リンク帯域の共用であれば、一方のスライスにおける仮想リンクのトラヒックフロー量の増加が、他方のスライスにおける仮想リンクのトラヒックフローのパケット転送品質へ与える影響は小さい。
【００２７】
そこで、本発明ではスライス#3，#4の組み合わせ、およびスライス#5，#6の組み合わせのように、各物理リンクにおいて、通過する仮想リンクの優先クラスが１種類のみのスライス同士であって、かつ通過する仮想リンクの優先クラスが互いに同一のスライス間でのみ、同図(b)に示したように、パケット転送キューの共用による物理リンク帯域の共用が図られる。
【００２８】
これに対して、スライス#1，#2の組み合わせのように、通過する仮想リンクの優先クラスが複数であるようなスライス間では、パケット転送キューおよび物理リンク帯域の共用は行わない。これは、もしパケット転送キューおよびリンク帯域の共用を行うと、一方のスライスにおいて高優先仮想リンクのトラヒックフロー量が増加した場合、他方のスライスにおいて低優先仮想リンクのトラヒックフローのパケット転送品質が不当に劣化する恐れがあるためである。
【００２９】
図２は、一の物理ノードに着目して、SDNスライス間でのトランザクションキューの共用による物理ノード帯域（容量）の共用方法を模式的に表現した図であり、同図(a)は共用前、同図(b)は共用後を表している。本発明では、仮想ノードで実行されるサービス処理について、高優先のフローに対応するサービス処理は高優先サービス処理とされ、低優先のフローに対応するサービス処理は低優先サービス処理とされる。
【００３０】
図示の例では、着目した物理ノードにおいて、スライス#1，#2の仮想ノードは高優先サービス処理および低優先サービス処理を実行し、スライス#3，#4の仮想ノードは高優先のサービス処理のみを実行し、スライス#5，#6の仮想ノードは低優先のサービス処理のみを実行する。高優先サービス処理をスケジューリングするトランザクションキューには、低優先サービス処理のトランザクションキューよりも高い優先度でスケジューリング機会が与えられる。
【００３１】
ここで、異なるスライス上の仮想ノード同士であっても、同一優先クラスに属するサービス処理同士でのトランザクションキューの共用による物理ノード帯域の共用であれば、一方のスライスにおけるサービス処理量の増加が、他方のスライスにおけるサービス処理の実行品質に与える影響は小さい。
【００３２】
そこで、本発明ではスライス#3，#4の組み合わせ、およびスライス#5，#6の組み合わせのように、各物理ノードにおいて、実行されるサービス処理の優先クラスが１種類のみのスライス同士であって、かつ実行されるサービス処理の優先クラスが互いに同一のスライス間でのみ、同図(b)に示したように、トランザクションキューの共用による物理ノード帯域の共用が図られる。
【００３３】
これに対して、スライス#1，#2の組み合わせのように、実行されるサービス処理の優先クラスが複数であるようなスライス間では、トランザクションキューおよび物理ノード帯域の共用は行わない。これは、もしトランザクションキューおよび物理ノード帯域の共用を行うと、一方のスライスで実行される高優先サービス処理量が増加した場合、他方のスライスで実行される低優先サービス処理の実行品質が不当に劣化する恐れがあるためである。
【００３４】
次いで、物理リンク帯域および物理ノード帯域の共用を促進して、スライス実行におけるスケジューリングコストを最小化する仮想ネットワーク割当について説明する。
【００３５】
本実施形態において最小化されるスケジューリングコストは、各物理リンクにおけるパケット転送に関するスケジューリングコストおよび各物理ノードにおけるサービス処理に関するスケジューリングコストの重み付き総和である。
【００３６】
各物理リンクにおけるスケジューリングコストは、スケジューリングの対象数で表され、各スライスによる物理リンク帯域共用後の物理リンク帯域の分割数となる。図１に示した例では、スケジューリングコストが物理リンク帯域共用によって６から４に削減されている。
【００３７】
同様に、各物理ノードにおけるスケジューリングコストも、スケジューリングの対象数で表され、各スライスによる物理ノード帯域共用後の物理ノード帯域の分割数となる。図２に示した例では、スケジューリングコストが物理ノード帯域共用によって６から４に削減されている。
【００３８】
図３は、本発明の一実施形態に係る仮想ネットワーク割当装置１の主要部の構成を示した機能ブロック図であり、汎用のコンピュータやサーバに各機能を実現するアプリケーション（プログラム）を実装することで構成できる。あるいはアプリケーションの一部がハードウェア化またはROM化された専用機や単能機としても構成できる。
【００３９】
ネットワーク情報入力部１０には、物理ネットワークのトポロジー情報、物理ネットワークへ割当済の既存仮想ネットワークの情報、および物理ネットワークへの仮想ネットワークの新規割り当てを要求する仮想ネットワーク割当要求が入力される。
【００４０】
前記物理ネットワークのトポロジー情報は、物理ネットワークを構成する物理ノード集合および物理リンク集合で表される。既存割当仮想ネットワーク情報は、各物理リンクおよび物理ノードに割当てられている仮想ネットワークと、その中でパケット転送またはサービス処理が行われる優先クラスによって表される。
【００４１】
前記仮想ネットワーク割当要求では、新たに割り当てられる仮想ネットワーク（割当要求仮想ネットワーク）の仮想ノードおよび仮想リンクで構成される仮想ネットワークトポロジーと、各仮想リンクが属する優先クラスとが指定される。各仮想リンク上では、指定された優先クラスに基づくパケット転送が行われ、各仮想リンクが接続する仮想ノードペア上では、指定された優先クラスに基づくサービス処理が実行される。
【００４２】
物理ノード候補選択部２０は、入力された各情報に基づいて、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ネットワークの物理ノード（候補）を選択する。本実施形態では、仮想ノードへのアクセス遅延の観点から、各仮想ノードは、予め当該仮想ノードと対応付けられた物理ノードおよび当該物理ノードに隣接する物理ノードの中のいずれか１つに割当てられる。
【００４３】
物理ネットワーク拡張部３０は、図４に示したように、与えられた物理ネットワークのトポロジー[同図(a)]に、割当対象である仮想ネットワークの各仮想ノードに対応する擬似ノードを仮想的に追加し、当該仮想ノードを割当てることが可能な全ての物理ノード（候補）と擬似ノードとの間に、破線で示した擬似リンクを設定する[同図(b)]ことで物理ネットワークを拡張する。
【００４４】
図示の例では、擬似ノードNv1が４つの物理ノードNp7，Np8，Np1，Np2と擬似リンクにより接続されている。同様に、擬似ノードNv2が３つの物理ノードNp1，Np2，Np3と擬似リンクにより接続されている。
【００４５】
仮想ネットワーク割当部４０は、拡張された物理ネットワーク上で、各仮想ノードが対応する擬似ノードに割り当てられたものとして、スライス実行におけるスケジューリングコストの総和を最小化する仮想ネットワーク割当を整数計画法モデルの解として計算する。
【００４６】
例えば図４(b)の例であれば、擬似ノード（仮想ノード）Nv5，Nv8を発着ノードとするパスについては、物理ノードNp4，Np5，Np6のいずれか（Nv5側）と物理ノードNp7，Np8，Np1，Np3（Nv8側）のいずれかとの組み合わせが発着ノードペアの候補となる。
【００４７】
その結果、アクセス遅延を生じさせない範囲でパスの多様性を確保することができ、また、全ての物理ノード候補を仮想ネットワークの発着ノードとするよりも、擬似ノードのみを発着ノードとすることにより、発着ノード数が減ぜられて計算量が減るので、整数計画法モデルの求解時における使用リソース量を低減できるようになる。
【００４８】
ここで、本実施形態では拡張された物理ネットワークに対する整数計画法モデルの定数および集合を以下の様に定義する。
Node：物理ノード集合
node：物理ノード
ENode：物理ノードと擬似ノードを合わせた拡張ノード集合
enode：拡張ノード
Link：物理リンク集合
link：物理リンク
VLink：擬似リンク集合
vlink：擬似リンク
ELink：物理リンクと擬似リンクを合わせた拡張リンク集合
elink：拡張リンク
Inout (enode)：拡張ノードenodeに接続する拡張リンクの集合
Sl：既存スライス集合
sl：既存スライス
Pr：優先クラス集合
pr：優先クラス
EQ pr, sl (link)：既存スライスslにおいて、優先クラスprに属する仮想リンクが物理リンクlinkを通過する時1、そうでない時0であるバイナリー定数
EQ1 sl (link)：既存スライスslにおいて、１つ以上の優先クラスに属する仮想リンクが物理リンクlinkを通過する時1、そうでない時0であるバイナリー定数
EQ2 sl (link)：既存スライスslにおいて、２つ以上の優先クラスに属する仮想リンクが物理リンクlinkを通過する時1、そうでない時0であるバイナリー定数
EQ pr, sl (node)：既存スライスslにおいて、優先クラスprに属するサービス処理が物理ノードnodeで実行される時1、そうでない時0であるバイナリー定数
EQ1 sl (node)：既存スライスslにおいて、１つ以上の優先クラスに属するサービス処理が物理ノードnodeで実行される時1、そうでない時0であるバイナリー定数
EQ2 sl (node)：既存スライスslにおいて、２つ以上の優先クラスに属するサービス処理が物理ノードnodeで実行される時1、そうでない時0であるバイナリー定数
Flow：割当対象スライスにおける仮想リンク集合
f：割当対象スライスにおける仮想リンク
FPr (pr)：割当対象スライスにおける優先クラスprに属する仮想リンク集合
s f：仮想リンクfが接続する一方の仮想ノードに対応する擬似ノード
d f：仮想リンクfが接続する他方の仮想ノードに対応する擬似ノード
A：十分大きな値を持つ定数
【００４９】
また、本実施形態では変数を以下の様に定義する。
X f, elink：割当対象スライスにおける仮想リンクfが拡張リンクelinkを通過する時1、そうでない時0であるバイナリー変数
Y f, node：割当対象スライスにおける仮想リンクfが物理ノードnodeを通過する時1、そうでない時0であるバイナリー変数
Z vlink：割当対象スライスにおいて、擬似リンクvlinkが接続する擬似ノードに対応する仮想ノードが擬似リンクvlinkが接続する物理ノードに割当てられる時1、そうでない時0であるバイナリー変数
Q pr (link)：割当対象スライスにおいて、優先クラスprに属する仮想リンクが物理リンクlinkを通過する時1、そうでない時0であるバイナリー変数
Q1 (link)：割当対象スライスにおいて、１つ以上の優先クラスに属する仮想リンクが物理リンクlinkを通過する時1、そうでない時0であるバイナリー変数
Q2 (link)：割当対象スライスにおいて、２つ以上の優先クラスに属する仮想リンクが物理リンクlinkを通過する時1、そうでない時0であるバイナリー変数
NQ pr (link)：既存スライスと割当対象スライスの少なくとも１つのスライスにおいて、優先クラスprに属する仮想リンクのみが物理リンクlinkを通過する時1、そうでない時0であるバイナリー変数
Q pr (node)：割当対象スライスにおいて、優先クラスprに属するサービス処理が物理ノードnodeで実行される時1、そうでない時0であるバイナリー変数
Q1 (node)：割当対象スライスにおいて、１つ以上の優先クラスに属するサービス処理が物理ノードnodeで実行される時1、そうでない時0であるバイナリー変数
Q2 (node)：割当対象スライスにおいて、２つ以上の優先クラスに属するサービス処理が物理ノードnodeで実行される時1、そうでない時0であるバイナリー変数
NQ pr (node)：既存スライスと割当対象スライスの少なくとも１つのスライスにおいて、優先クラスprに属するサービス処理のみが物理ノードnodeで実行される時1、そうでない時0であるバイナリー変数
【００５０】
本実施形態では、整数計画法モデルにおける制約式が、仮想リンク経路の保存則として次式(1)〜(3)で与えられる。
【００５１】
【数１】
0006279436.tif 000002
【００５２】
【数２】
0006279436.tif 000003
【００５３】
【数３】
0006279436.tif 000004
【００５４】
次式(4)は、仮想ノードが物理ノードに割当てられる条件であり、Zvlinkは、ΣXf,linkが０以下であれば「0」、１以上であれば「1」となる。
【００５５】
【数４】
0006279436.tif 000005
【００５６】
次式(5)は、割当対象スライスにおいて、各優先クラスに属する仮想リンクが物理リンクを通過する条件であり、Q pr(link)は、ΣXf,linkが０以下であれば「0」、１以上であれば「1」となる。
【００５７】
【数５】
0006279436.tif 000006
【００５８】
次式(6)は、割当対象スライスにおいて、１つ以上の優先クラスに属する仮想リンクが物理リンクを通過する条件であり、Q1(link)は、ΣQpr(link)が０以下であれば「0」、１以上であれば「１」となる。
【００５９】
【数６】
0006279436.tif 000007
【００６０】
次式(7)は、割当対象スライスにおいて、２つ以上の優先クラスに属する仮想リンクが物理リンクを通過する条件であり、Q2 sl (link)は、ΣQ pr, sl (link)-1が０以下であれば「0」、１以上であれば「１」となる。
【００６１】
【数７】
0006279436.tif 000008
【００６２】
次式(8)，(9)は、既存スライスと割当対象スライスの少なくとも１つのスライスにおいて、各優先クラスに属する仮想リンクのみが物理リンクを通過する条件である。
【００６３】
【数８】
0006279436.tif 000009
【００６４】
【数９】
0006279436.tif 000010
【００６５】
次式(10)は、割当対象スライスにおいて、各優先クラスに属するサービス処理が物理ノードで実行される条件である。
【００６６】
【数１０】
0006279436.tif 000011
【００６７】
次式(11)は、割当対象スライスにおいて、１つ以上の優先クラスに属するサービス処理が物理ノードで実行される条件である。
【００６８】
【数１１】
0006279436.tif 000012
【００６９】
次式(12)は、割当対象スライスにおいて、２つ以上の優先クラスに属するサービス処理が物理ノードで実行される条件である。
【００７０】
【数１２】
0006279436.tif 000013
【００７１】
次式(13)，(14)は、既存スライスおよび割当対象スライスの少なくとも１つのスライスにおいて、各優先クラスに属するサービス処理のみが物理ノードで実行される条件である。
【００７２】
【数１３】
0006279436.tif 000014
【００７３】
【数１４】
0006279436.tif 000015
【００７４】
最小化すべきスライス実行におけるスケジューリングコストは、各物理リンクにおけるパケット転送に関するスケジューリングコストおよび各物理ノードにおけるサービス処理に関するスケジューリングコストの重み付き総和として、次式(14)で与えられる。
【００７５】
【数１５】
0006279436.tif 000016
【００７６】
ここで、定数W1は、パケット転送に関するスケジューリングコストの重み値を表し、定数W2は、サービス処理に関するスケジューリングコストの重み値を表す。仮想ネットワークの割当結果は、変数X f, elinkまたはY f, nodeの値で示される。
【００７７】
図５は、前記ネットワーク情報入力部１０に入力される物理ネットワークのトポロジー情報[同図(a)]、割当要求仮想ネットワーク[同図(b)]および仮想ネットワークの割当結果[同図(c)]の一例を示した図である。
【００７８】
各仮想ノードNvは１個の物理ノードNpへ割り当てられる。また、複数個の仮想ノードNvが１個の物理ノードNpに割り当てられることはない。一方、各仮想リンクlは、当該仮想リンクlが接続する２個の仮想ノードNvが割り当てられた２個の物理ノードNpを発着ノードとする１本の物理パスへ割り当てられる。
【００７９】
図示の例では、物理ノードNp2，Np6，Np11，Np14に仮想ノードNv1，Nv4，Nv2，Nv3がそれぞれ割り当てられている。また、物理リンクl14-15，l1-15，l1-2から構成される物理パスに仮想リンクL1-3が割り当てられ、物理リンクl11-12，l12-13，l13-14から構成される物理パスに仮想リンクL2-3が割り当てられ、物理リンクl6-14から構成される物理パスに仮想リンクL3-4が割り当てられ、物理リンクl2-11から構成される物理パスに仮想リンクL1-2が割り当てられている。
【００８０】
本実施形態によれば、各仮想ノードの割当候補となる物理ノードが、予め対応付けられた物理ノードおよびその隣接ノードに制限されるので、整数計画法モデルによる解法を採用しても計算リソースの使用量を大幅に減ぜられるようになる。のみならず、各仮想ノードは、予め当該仮想ノードと対応付けられた物理ノードまたは当該物理ノードに隣接する物理ノードの中のいずれか一つに割当てられるため、仮想ノードへのアクセス遅延を抑えながらパスの多様性を確保できるようになる。
【００８１】
また、本実施形態によれば、SDNにおいて、指定された優先クラスに基づくサービス品質へ影響が及ばない範囲で、各スライス間での物理リンク帯域および物理ノード帯域の共用を促進して、スライス実行におけるスケジューリングコストを最小化する仮想ネットワーク割当を実現できる。
【００８２】
さらに、本実施形態によれば、各スライス間で物理リンク帯域および物理ノード帯域の共用が促進されるので、統計多重効果によって物理リンク帯域および物理ノード帯域の利用効率が向上する。
【符号の説明】
【００８３】
１０…ネットワーク情報入力部，２０…物理ノード候補選択部，３０…物理ネットワーク拡張部，４０…仮想ネットワーク割当部
【図１】
0006279436.tif 000017
【図２】
0006279436.tif 000018
【図３】
0006279436.tif 000019
【図４】
0006279436.tif 000020
【図５】
0006279436.tif 000021