JP6279427B2 - 仮想ネットワーク割当方法および装置 - Google Patents

Description

本発明は、各仮想リンク対応に優先クラスが指定された新たな仮想ネットワークの割当要求に対して仮想ネットワーク割当を実現する仮想ネットワーク割当方法および装置に係り、特に、SDN（Software-Defined Network）の各スライス間で、物理リンク帯域および物理ノード処理容量の共用を促進して、スライス実行におけるスケジューリングコストを最小化する仮想ネットワーク割当方法および装置に関する。

ソフトウェアによって仮想的なネットワークを作り上げる技術として、非特許文献１，２にSDNが開示されている。SDNでは、一つの物理ネットワーク上に「スライス」と呼ばれる完全に独立した仮想的なネットワークをいくつも構築できるため、スライスごとにユーザの要求に応じた固有のネットワークを構築できる。

ここで、SDNの各スライスは物理ネットワークの各リンクを共用できるが、その際、スライスごとに独自のリンク帯域を設定するとリンク帯域を有効利用できない。例えば、帯域が２Gの物理リンクについて、スライスA，Bに1Gずつの帯域が固定的に割り当てられていると、例えばスライスAのトラヒック量が多く、スライスBのトラヒック量が少ない場合でも、スライスAにスライスBの余剰帯域を割り当てられない。

これに対して、物理リンク毎にスライスA，Bが一つのパケット転送キューを共用するように帯域を割り当てれば、各スライスA，Bは余剰帯域を他のスライスに分け与えることができるので、各スライスのサービス品質を低下させることなくリンク帯域を有効利用できる。しかしながら、これまで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月，進藤資訓

特許文献１では、複数のサービス優先クラスを指定する仮想ネットワーク割当において、各仮想ノードにおけるサービス処理品質に影響を及ぼさない範囲で、仮想ノード間での物理ノード処理容量の共用を促進して、サービス処理のスケジューリングコストを最小化することができなかった。

また、特許文献１に開示された整数計画法モデルの直接解法は大量の計算リソースを使用するので、大規模なSDNへの適用が難しいという技術課題があった。

本発明の目的は、上記の技術課題を解決し、複数のサービス優先クラスを指定する仮想ネットワーク割当において、各仮想ネットワークにおけるサービス品質に影響を及ぼさない範囲で、各スライス間で物理リンク帯域および物理ノード処理容量の共用を促進して、スライス実行におけるスケジューリングコストを削減できる仮想ネットワーク割当を実現する仮想ネットワーク割当方法および装置を提供することにある。

上記の目的を達成するために、本発明は、SDNの各スライスが既存仮想ネットワークと物理帯域を共用する仮想ネットワークを新規に割り当てる仮想ネットワーク割当装置において、以下の構成を具備した点に特徴がある。

(1) 物理ネットワークのトポロジー情報、既存仮想ネットワークの情報および物理ネットワークへ新規に割り当てる割当要求仮想ネットワークの情報を取得する手段と、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ノードを選択する手段と、割当要求仮想ネットワークの仮想リンクの割り当てによる各物理リンクのスケジューリングコストの増分を、物理リンク帯域の共有によるコスト削減を反映して計算する物理リンクコスト計算手段と、仮想ネットワークの仮想リンクごとに、前記各物理リンクのスケジューリングコストの増分に基づいて最小コスト経路を計算する最小コスト経路計算手段と、最小コスト経路の発着物理ノードペアにおけるスケジューリングコストの増分を、物理ノード処理容量の共有によるコスト削減を反映して計算する物理ノードコスト計算手段と、仮想リンクごとにコストを更新しながら求まる最小コスト経路およびその発着物理ノードのスケジューリングコストの増分に基づいて、最小コストの物理パス経路を与える物理リンク及び物理ノードに仮想リンクおよび仮想ノードを割り当てる仮想ネットワーク割当手段とを具備した。

(2) 物理リンクコスト計算手段は、各物理リンクのスケジューリングコストを、仮に割当対象の仮想リンクが当該物理リンクを通過した時のパケット転送に関するスケジューリングコストの増分に設定するようにした。

(3) 物理ノードコスト計算手段は、各物理ノード候補のスケジューリングコストを、仮に割当対象の仮想リンクと接続する仮想ノードが当該物理ノードに割り当てられた時のサービス処理に関するスケジューリングコストの増分に設定するようにした。

(4) 物理リンクコスト計算手段は、各物理リンクを通過する仮想リンクの優先クラスが１種類のみのスライス同士であって、かつ通過する仮想リンクの優先クラスが互いに同一のスライス間でのパケット転送キューの共用によるスケジューリングコストの削減を反映させるようにした。

(5) 物理ノードコスト計算手段は、各物理ノードにおいて、実行されるサービス処理の優先クラスが１種類のみのスライス同士であって、かつ実行されるサービス処理の優先クラスが互いに同一のスライス間でのトランザクションキューの共用によるスケジューリングコストの削減を反映させるようにした。

(1) 本発明によれば、SDNにおいて、指定された優先クラスに基づくサービス品質へ影響が及ばない範囲で、各スライス間での物理リンク帯域および物理ノード処理容量の共用を促進して、スライス実行におけるスケジューリングコストを削減する仮想ネットワーク割当を少ない計算量で実現できるようになる。

(2) 本発明によれば、各スライス間で物理リンク帯域および物理ノード処理容量の共用が促進されるので、統計多重効果によって物理リンク帯域および物理ノード処理容量の利用効率が向上する。

(3) 本発明によれば、各仮想ノードは、予め当該仮想ノードに対応付けられた物理ノードまたは当該物理ノードに隣接する物理ノードの中の１個に割り当てられるため、仮想ノードへのアクセス遅延を抑えることができる。

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)]および仮想ネットワークの割当結果[同図(c)]の一例を示した図である。

各仮想ノードNは１個の物理ノードqへ割り当てられる。また、複数個の仮想ノードNが１個の物理ノードqに割り当てられることはない。一方、各仮想リンクlは、当該仮想リンクlが接続する２個の仮想ノードNが割り当てられた２個の物理ノードqを発着ノードとする１本の物理パスへ割り当てられる。

図示の例では、物理ノードq2，q6，q11，q14に仮想ノードN1，N4，N2，N3がそれぞれ割り当てられている。また、物理リンクl14-15，l1-15，l1-2から構成される物理パスに仮想リンクL1-3が割り当てられ、物理リンクl11-12，l12-13，l13-14から構成される物理パスに仮想リンクL2-3が割り当てられ、物理リンクl6-14から構成される物理パスに仮想リンクL3-4が割り当てられ、物理リンクl2-11から構成される物理パスに仮想リンクL1-2が割り当てられている。

次いで、本実施形態の動作について説明する。本実施形態では、ネットワーク全体で、スライス間の物理リンク帯域および物理ノード帯域の共用を促進し、スライス実行におけるスケジューリングコストを最小化する。最小化されるスケジューリングコストは、各物理リンクにおけるパケット転送のスケジューリングコストおよび各物理ノードにおけるサービス処理のスケジューリングコストの重み付き総和である。

そのために、本実施形態では全ての仮想リンクに関して、逐次的にスライス実行におけるスケジューリングコストの増加を最小化するような物理パス経路を算出して割り当てる。逐次的な仮想リンク割当では、一旦、仮想ノードが物理ノードに割当てられた場合は、以後、当該仮想ノードの割当てを固定する。

本実施形態では、仮想ノードへのアクセス遅延の観点から、各仮想ノードは、予め当該仮想ノードに対応付けられている物理ノードまたは当該物理ノードに隣接する物理ノードの中の１個に割り当てられる。最後に、逐次的に算出した物理パス経路が、仮想ネットワーク割当の結果として出力される。

図５は、本実施形態の動作を示したフローチャートであり、ステップＳ１では、入力された仮想ネットワークの割当要求に基づいて、割当要求仮想ネットワークを構成する仮想リンクの一覧がリスト形式で作成される。ステップＳ２では、仮想リンクの一つが今回の注目仮想リンクとして選択される。ステップＳ３では、前記物理ネットワークのトポロジー情報および既存仮想ネットワーク情報に基づいて、各物理リンクのコストが計算される。

以下、ステップＳ３における物理リンクコストの設定方法について説明する。本実施形態では、各物理リンクのコストが、仮に注目仮想リンクが当該物理リンクを通過した時のパケット転送に関するスケジューリングコストの増加量ΔClinkに設定される。具体的には、既存割当仮想ネットワーク情報を考慮して、以下の４つの値のいずれかに設定される。

(1) ケース１
コスト計算対象の物理リンクを通過する割当要求仮想ネットワークを構成する仮想リンクが存在せず、同じ優先クラスの仮想リンクのみが当該物理リンクを通過するような既存仮想ネットワークが存在しない場合：ΔClink=1.0

(2) ケース２
コスト計算対象の物理リンクを通過する割当要求仮想ネットワークを構成する仮想リンクが存在せず、同じ優先クラスの仮想リンクのみが当該物理リンクを通過するような既存仮想ネットワークが存在する場合：ΔClink=ε（εは十分に小さな値）

(3) ケース３
コスト計算対象の物理リンクを通過する割当要求仮想ネットワークを構成する同じ優先クラスの仮想リンクが存在せず、当該物理リンクを通過する割当要求仮想ネットワークを構成する異なる１つの優先クラスの仮想リンクが存在する場合：ΔClink=1.0-LC（LCは当該物理リンクの直前のコスト）

(4) ケース４
その他の場合：ΔClink=ε

ケース１，２における物理リンクコストは、割当要求仮想ネットワークに関して、物理リンクを通過する仮想リンクが存在しない状態から、当該物理リンクを注目仮想リンクが最初に通過することによるスケジューリングコストの増加量である。従って、ケース１のように、同じ優先クラスの仮想リンクのみが当該物理リンクを通過するような既存仮想ネットワークが存在しない場合は、既存仮想ネットワークと物理リンク帯域を共用することができないので、スケジューリングコストの増加量ΔClinkは1.0となる。

これに対して、ケース２のように、同じ優先クラスの仮想リンクのみが当該物理リンクを通過するような既存仮想ネットワークが存在する場合は、その様な既存仮想ネットワークと物理リンク帯域を共用することができ、スケジューリングコストは増加しない。したがって、スケジューリングコストの増加量ΔClinkは十分に小さな実数εとなる。例えば、εはネットワークの総リンク数Lの逆数よりも小さな数である。

ケース３では、仮に注目仮想リンクが当該物理リンクを通過した場合、２つの優先クラスに属する仮想リンク群が当該物理リンクを通過することになるので、既存仮想ネットワークと物理リンク帯域を共用することができなくなり、当該物理リンクを通過する仮想リンクが全く存在しない状態からのスケジューリングコスト増加量は1.0となる。従って、当該物理リンクの直前のコストをLCで表せば、スケジューリングコストの増加量ΔClinkは1.0-LCとなる。

ケース４の場合は、仮に割当対象仮想リンクが当該物理リンクを通過しても、スケジューリングコストは増加しない。スケジューリングコストが増加しない場合、スケジューリングコストの増加量ΔClinkは十分小さな実数εとなる。

図５へ戻り、ステップＳ４では、注目する発着物理ノードの絞り込みが行われる。例えば図４(a)の例において、仮想ノードN1と物理ノードq2とが予め対応付けされていれば、仮想ノードN1にとっては、物理ノードq 2およびその隣接ノードq 1，q 3が発着物理ノードの候補とされる。

ステップＳ５では、今回の注目仮想リンクが接続する２つの仮想ノードに関して、割当候補となる全ての物理ノードを発着ノードとする最小コスト経路が順次に算出される。但し、仮想ノードが既に物理ノードに割り当てられている場合は、当該物理ノードに発着ノードが限定される。また、既に他の仮想ノードが割り当てられている物理ノードは発着ノード候補から除外される。

ステップS６では、前記物理ネットワークのトポロジー情報および既存仮想ネットワーク情報に基づいて、注目仮想リンクに前記最小コスト経路を与える発着物理ノードのスケジューリングコストが計算される。

本実施形態では、各物理ノードのコストが、仮に注目仮想リンクと接続する仮想ノードが当該物理ノードに割り当てられた時のサービス処理に関するスケジューリングコストの増加量ΔCnodeに設定される。具体的には、既存割当仮想ネットワーク情報を考慮して、以下の４つの値のいずれかに設定される。

(1) ケース１
コスト計算対象の物理ノードに仮想ノードが未だ割当てられておらず、同じ優先クラスのサービス処理のみを実行する仮想ノードが当該物理ノードに割当てられている既存仮想ネットワークが存在しない場合：ΔCnode=1.0

(2) ケース２
コスト計算対象の当該物理ノードに仮想ノードが未だ割当てられておらず、同じ優先クラスのサービス処理のみを実行する仮想ノードが当該物理ノードに割当てられている既存仮想ネットワークが存在する場合：ΔCnode=0.0

(3) ケース３
コスト計算対象の物理ノードに既に仮想ノードが割当てられており、当該仮想ノードでは、注目仮想リンクに対して指定された優先クラスのサービス処理は実行されず、異なる１つの優先クラスのサービス処理のみが実行される場合：ΔCnode=1.0-LC

(4) ケース４
その他の場合：ΔCnode=0.0

ケース１，２における物理ノードコストは、割当要求仮想ネットワークに関して、当該物理ノードに仮想ノードが割当てられていない状態から、最初に仮想ノードが割当てられることによるスケジューリングコストの増加量を示す。従って、ケース１のように、同じ優先クラスのサービス処理のみを実行する仮想ノードが当該物理ノードに割当てられている既存仮想ネットワークが存在しない場合は、既存仮想ネットワークと物理ノード帯域を共用することができず、スケジューリングコスト増加量ΔCnodeは1.0となる。

これに対して、ケース２のように、同じ優先クラスのサービス処理のみを実行する仮想ノードが当該物理ノードに割当てられている既存仮想ネットワークが存在する場合は、その様な既存仮想ネットワークと物理ノード帯域を共用することができるため、スケジューリングコストは増加しない。

ケース３においては、仮にコスト算出対象の物理パス経路が当該物理ノードを発着ノードとした場合、当該物理ノードに割当てられた仮想ノードで２つの優先クラスのサービス処理が実行されることになるので、既存仮想ネットワークと物理ノード帯域を共用することができなくなり、当該物理ノードに仮想ノードが割当てられていない状態からのスケジューリングコストの増加量は1.0となる。従って、当該物理ノードの直前のコストをLCで表せば、スケジューリングコストの増加量ΔCnodeは1.0-LCとなる。

ケース４の場合は、仮にコスト算出対象の物理パス経路が当該物理ノードを発着ノードとしても、スケジューリングコストは増加しない。

ステップＳ７では、今回の発着物理ノードペアに対して算出された最小コスト経路に対応する物理パス経路のコストが算出される。物理パス経路のコストは、当該物理パス経路を構成する各物理リンクのスケジューリングコストの増加量ΔClinkと発着物理ノードのスケジューリングコストの増加量ΔCnodeとの重み付き総和である。

ステップＳ８では、全ての発着物理ノードペアに関して物理パス経路のコスト算出が完了したか否かが判断される。完了していなければステップＳ５へ戻り、注目する発着物理ノードペアを変更して最小コスト経路の計算および物理パス経路のコスト算出が繰り返される。

ステップＳ９では、最小コストの物理パス経路を与える物理リンク及び物理ノードに仮想リンクおよび仮想ノードが割り当てられる。ステップＳ１０では、全ての仮想リンクの割り当てが完了したか否かが判断される。完了していなければステップＳ２へ戻り、注目仮想リンクを変更しながら、最小コスト経路の計算、物理パス経路のコスト算出および仮想リンクの割り当てが繰り返される。

本実施形態によれば、SDNにおいて、指定された優先クラスに基づくサービス品質へ影響が及ばない範囲で、各スライス間での物理リンク帯域および物理ノード帯域の共用を促進して、スライス実行におけるスケジューリングコストを削減する仮想ネットワーク割当を少ない計算量で実現できるようになる。

また、本実施形態によれば、各スライス間で物理リンク帯域および物理ノード帯域の共用が促進されるので、統計多重効果によって物理リンク帯域および物理ノード帯域の利用効率が向上する。

さらに、本実施形態によれば、各仮想ノードは、予め当該仮想ノードに対応付けられた物理ノードまたは当該物理ノードに隣接する物理ノードの中の１個に割り当てられるため、仮想ノードへのアクセス遅延を抑えることができる。

１…仮想ネットワーク割当装置，１０…ネットワーク情報入力部，２０…物理ノード候補選択部，３０…コスト計算部，３０１…物理リンクコスト計算部，３０２…物理ノードコスト計算部，４０…仮想ネットワーク割当部，４０１…最小コスト経路計算部，４０２…物理パス経路コスト計算部

Claims (12)

1. SDNの各スライスが既存仮想ネットワークと物理帯域を共用する仮想ネットワークを新規に割り当てる仮想ネットワーク割当装置において、
   物理ネットワークのトポロジー情報、既存仮想ネットワークの情報および物理ネットワークへ新規に割り当てる割当要求仮想ネットワークの情報を取得する手段と、
   前記各情報に基づいて、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ノードを選択する手段と、
   割当要求仮想ネットワークの仮想リンクの割り当てによる各物理リンクのスケジューリングコストの増分を、物理リンク帯域の共有によるコスト削減を反映して計算する物理リンクコスト計算手段と、
   仮想ネットワークの仮想リンクごとに、前記各物理リンクのスケジューリングコストの増分に基づいて、前記割り当て可能な物理ノードの組み合わせからなる各発着物理ノードペア間の最小コスト経路を計算する最小コスト経路計算手段と、
   前記最小コスト経路の発着物理ノードペアにおけるスケジューリングコストの増分を、物理ノード処理容量の共有によるコスト削減を反映して計算する物理ノードコスト計算手段と、
   仮想リンクごとにコストを更新しながら求まる最小コスト経路およびその発着物理ノードのスケジューリングコストの増分に基づいて、最小コストの物理パス経路を与える物理リンク及び物理ノードに仮想リンクおよび仮想ノードを割り当てる仮想ネットワーク割当手段とを具備したことを特徴とする仮想ネットワーク割当装置。
2. 前記物理リンクコスト計算手段は、各物理リンクのスケジューリングコストを、仮に割当対象の仮想リンクが当該物理リンクを通過した時のパケット転送に関するスケジューリングコストの増分に設定することを特徴とする請求項１に記載の仮想ネットワーク割当装置。
3. 前記物理ノードコスト計算手段は、各物理ノード候補のスケジューリングコストを、仮に割当対象の仮想リンクと接続する仮想ノードが当該物理ノードに割り当てられた時のサービス処理に関するスケジューリングコストの増分に設定することを特徴とする請求項１または２に記載の仮想ネットワーク割当装置。
4. 前記物理リンクコスト計算手段は、各物理リンクを通過する仮想リンクの優先クラスが１種類のみのスライス同士であって、かつ通過する仮想リンクの優先クラスが互いに同一のスライス間でのパケット転送キューの共用によるスケジューリングコストの削減を反映させることを特徴とする請求項１ないし３のいずれかに記載の仮想ネットワーク割当装置。
5. 前記物理ノードコスト計算手段は、各物理ノードにおいて、実行されるサービス処理の優先クラスが１種類のみのスライス同士であって、かつ実行されるサービス処理の優先クラスが互いに同一のスライス間でのトランザクションキューの共用によるスケジューリングコストの削減を反映させることを特徴とする請求項１ないし４のいずれかに記載の仮想ネットワーク割当装置。
6. 前記仮想ネットワーク割当手段は、最小コスト経路のコストおよび発着物理ノードのコストの重み付き総和に基づいて最小コストの物理パス経路を決定することを特徴とする請求項１ないし５のいずれかに記載の仮想ネットワーク割当装置。
7. 前記物理ノードを選択する手段は、既に他の仮想ノードが割当てられている物理ノードは除外し、当該仮想ノードが既に物理ノードに割当てられている場合は当該物理ノードに限定することを特徴とする請求項１ないし６のいずれかに記載の仮想ネットワーク割当装置。
8. SDNの各スライスが物理ネットワーク上に既存仮想ネットワークと物理帯域を共用する仮想ネットワークを新規に割り当てる仮想ネットワーク割当方法において、
   物理ネットワークのトポロジー情報、既存仮想ネットワークの情報および物理ネットワークへ新規に割り当てる割当要求仮想ネットワークの情報を取得する第１手順と、
   前記各情報に基づいて、割当要求仮想ネットワークの各仮想ノードを割り当て可能な物理ノードを選択する第２手順と、
   割当要求仮想ネットワークの仮想リンクの割り当てによる各物理リンクのスケジューリングコストの増分を、物理リンク帯域の共有によるコスト削減を反映して計算する第３手順と、
   仮想ネットワークの仮想リンクごとに、前記各物理リンクのスケジューリングコストの増分に基づいて、前記割り当て可能な物理ノードの組み合わせからなる各発着物理ノードペア間の最小コスト経路を計算する第４手順と、
   前記最小コスト経路の発着物理ノードペアにおけるスケジューリングコストの増分を、物理ノード処理容量の共有によるコスト削減を反映して計算する第５手順と、
   仮想リンクごとにコストを更新しながら求まる最小コスト経路およびその発着物理ノードのスケジューリングコストの増分に基づいて、最小コストの物理パス経路を与える物理リンク及び物理ノードに仮想リンクおよび仮想ノードを割り当てる第６手順とを含むことを特徴とする仮想ネットワーク割当方法。
9. 前記第３手順では、各物理リンクのスケジューリングコストが、仮に割当対象の仮想リンクが当該物理リンクを通過した時のパケット転送に関するスケジューリングコストの増分に設定されることを特徴とする請求項８に記載の仮想ネットワーク割当方法。
10. 前記第５手順では、各物理ノード候補のスケジューリングコストが、仮に割当対象の仮想リンクと接続する仮想ノードが当該物理ノードに割り当てられた時のサービス処理に関するスケジューリングコストの増分に設定されることを特徴とする請求項８または９に記載の仮想ネットワーク割当方法。
11. 前記第３手順では、各物理リンクを通過する仮想リンクの優先クラスが１種類のみのスライス同士であって、かつ通過する仮想リンクの優先クラスが互いに同一のスライス間でのパケット転送キューの共用によるスケジューリングコストの削減が反映されることを特徴とする請求項８ないし１０のいずれかに記載の仮想ネットワーク割当方法。
12. 前記第５手順では、各物理ノードにおいて、実行されるサービス処理の優先クラスが１種類のみのスライス同士であって、かつ実行されるサービス処理の優先クラスが互いに同一のスライス間でのトランザクションキューの共用によるスケジューリングコストの削減が反映されることを特徴とする請求項８ないし１１のいずれかに記載の仮想ネットワーク割当方法。