(57)【要約】【課題】SDNの各スライスが物理リンクごとに一つのパケット転送キューを共用してリンク帯域を共用するラヒックフロー割当方法および装置を提供する。【解決手段】入力インタフェース１０は、ネットワークのトポロジー情報の入力およびトラヒックフロー情報の入力を受け付ける。ツリートポロジー候補作成部２０は、スライスごとにトラヒックフローの経路を合成して構成される複数のツリートポロジー候補を作成する。トラヒックフロー割当計算部３０は、スライス間でのツリートポロジー候補の組み合わせを対象に、トラヒックフローが通過する各リンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を、各リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下で、整数計画法モデルの解として計算する。【選択図】図７
2015126355.tif 000002
【特許請求の範囲】
【請求項１】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、
ネットワークのトポロジー情報およびトラヒックフロー情報に基づいて、スライスごとに複数のツリートポロジー候補を作成する手段と、
スライス間でのツリートポロジー候補の組み合わせを対象に、トラヒックフローが通過する各リンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを具備し、
前記トラヒックフロー割当を計算する手段は、各リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下で、ツリートポロジー候補の組み合わせおよび各ツリートポロジー候補におけるトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当装置。
【請求項２】
前記トラヒックフロー割当を計算する手段は、各リンクについて、複数のスライスに当該リンクを共用させるためのスライス間スケジューリングコスト、および同一のスライス内で複数の優先クラスのトラヒックフローに当該リンクを共用させるためのスライス内スケジューリングコストの総和が最小となるトラヒックフロー割当を計算することを特徴とする請求項１に記載のトラヒックフロー割当装置。
【請求項３】
前記スライス間スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士に当該リンクの帯域を共有させて１スライスとみなしたときに当該リンクを共用するスライス数に比例した値であることを特徴とする請求項２に記載のトラヒックフロー割当装置。
【請求項４】
前記スライス間スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士に当該リンクの帯域を共有させて１スライスとみなしたときに当該リンクを共用するスライス数に依存し、スライス数が「１」以下のリンクではゼロ、「２」以上のリンクでは当該スライス数に比例した値であることを特徴とする請求項２に記載のトラヒックフロー割当装置。
【請求項５】
前記スライス内スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士にリンク帯域を共有させて１スライスとみなしたときのパケット転送キュー数に依存し、パケット転送キュー数が「１」以下のスライスではゼロ、「２」以上のスライスでは当該パケット転送キュー数に比例した値であることを特徴とする請求項２ないし４のいずれかに記載のトラヒックフロー割当装置。
【請求項６】
前記整数計画法モデルは、優先クラスの異なるトラヒックフロー同士にリンク帯域を共用させないことを特徴とする請求項１ないし５のいずれかに記載のトラヒックフロー割当装置。
【請求項７】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、
ネットワークのトポロジー情報およびトラヒックフロー情報に基づいて、スライスごとに複数のツリートポロジー候補を作成する手段と、
スライス間でのツリートポロジー候補の組み合わせを対象に、トラヒックフローが通過する各リンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを具備し、
前記トラヒックフロー割当を計算する手段は、各リンクを通過するトラヒックフローの優先クラスが複数であるスライスのうち、相互に対応する優先クラスを有し、かつ各優先クラスにリンク帯域が固定的に割り当てられているスライス同士に、対応する優先クラスのリンク帯域を共用させる条件下で、ツリートポロジー候補の組み合わせおよび各ツリートポロジー候補におけるトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当装置。
【請求項８】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当方法において、
ネットワークのトポロジー情報およびトラヒックフロー情報に基づいて、スライスごとに複数のツリートポロジー候補を作成する手順と、
スライス間でのツリートポロジー候補の組み合わせを対象に、トラヒックフローが通過する各リンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手順とをコンピュータに実行させ、
前記トラヒックフロー割当の計算では、各リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下で、ツリートポロジー候補の組み合わせおよび各ツリートポロジー候補におけるトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当方法。
【請求項９】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当方法において、
ネットワークのトポロジー情報およびトラヒックフロー情報に基づいて、スライスごとに複数のツリートポロジー候補を作成する手順と、
スライス間でのツリートポロジー候補の組み合わせを対象に、トラヒックフローが通過する各リンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手順とをコンピュータに実行させ、
前記トラヒックフロー割当の計算では、各リンクを通過するトラヒックフローの優先クラスが複数であるスライスのうち、相互に対応する優先クラスを有し、かつ各優先クラスにリンク帯域が固定的に割り当てられているスライス同士に、対応する優先クラスのリンク帯域を共用させる条件下で、ツリートポロジー候補の組み合わせおよび各ツリートポロジー候補におけるトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め発着ノード等の属性が与えられたトラヒックフロー群に対して、ネットワーク上の経路を割り当てるトラヒックフロー割当方法および装置に係り、特に、SDN（Software-Defined Network）の各スライス（仮想ネットワーク）間でパケット転送キューの共用によるリンク帯域の共用を少ない計算リソースで実現するトラヒックフロー割当方法および装置に関する。
【背景技術】
【０００２】
ソフトウェアによって仮想的なネットワークを作り上げる技術として、非特許文献１，２にSDNが開示されている。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月，進藤資訓
【発明の概要】
【発明が解決しようとする課題】
【０００６】
SDNの各スライスは物理ネットワークの各リンクを共用できるが、その際、スライスごとに独自のリンク帯域を設定するとリンク帯域を有効利用できない。例えば、帯域が２Gの物理リンクについて、スライスA，Bに1Gずつの帯域が固定的に割り当てられていると、例えばスライスAのトラヒック量が多く、スライスBのトラヒック量が少ない場合でも、スライスAにスライスBの余剰帯域を割り当てられない。
【０００７】
これに対して、物理リンク毎にスライスA，Bが一つのパケット転送キューを共用するようにして2Gの帯域を割り当てれば、各スライスA，Bは余剰帯域を他のスライスに分け与えることができるので、各スライスのサービス品質を低下させることなくリンク帯域を有効利用できる。しかしながら、これまでSDNの各スライスが物理リンクごとに一つのパケット転送キューを共用してリンク帯域を共用することが検討されていなかった。
【０００８】
このような技術課題に対して、本発明の発明者等は、ネットワークのトポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算し、その際、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下でトラヒックフロー割当を計算する方法および装置を発明し、特許出願した（特許文献１）。
【０００９】
しかしながら、特許文献１に開示された整数計画法モデルの直接解法は大量の計算リソースを使用するので、小規模なSDNにしか適用できないという技術課題があった。
【００１０】
本発明の目的は、上記の技術課題を解決し、SDNの各スライスが物理リンクごとに一つのパケット転送キューを共用してリンク帯域を共用するトラヒックフロー割当を、少ない計算リソースで実現できるトラヒックフロー割当方法および装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために、本発明は、SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、ネットワークのトポロジー情報およびトラヒックフロー情報に基づいて、スライスごとに複数のツリートポロジー候補を作成する手段と、スライス間でのツリートポロジー候補の組み合わせを対象に、トラヒックフローが通過する各リンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを設けた。
【００１２】
前記トラヒックフロー割当を計算する手段は、各リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下で、ツリートポロジー候補の組み合わせおよび各ツリートポロジー候補におけるトラヒックフロー割当を計算するようにした。
【発明の効果】
【００１３】
本発明によれば、以下のような効果が達成される。
(1) 各スライスにおいて、予め与えられた複数のツリートポロジー候補の中から、最もパケット転送スケジューリングコストを削減するツリートポロジー候補を選択するために整数計画法モデルの求解を行うのみなので、大量の計算リソースを必要とせず、規模の大きなSDNにも適用できる。
【００１４】
(2) 仮想ネットワークである各スライス上でツリートポロジー候補を構成することにより、各スライスにおいて通過するトラヒックフローの優先クラスが１種類であるリンクの割合を増加させて、スライス間でのパケット転送キューおよびリンク帯域の共用を促進し、リソース利用効率の向上を図ることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明によるスライス間でのパケット転送キューの共用によるリンク帯域の共用の典型例を示した図である。
【図２】トラヒックフローに優先クラスが設定されているためにパケット転送キューの共用によるリンク帯域の共用に適さない例を示した図である。
【図３】トラヒックフローに優先クラスが設定されていてもパケット転送キューの共用によるリンク帯域の共用に適した例を示した図（その１）である。
【図４】トラヒックフローに優先クラスが設定されていてもパケット転送キューの共用によるリンク帯域の共用に適した例を示した図（その２）である。
【図５】リンクを共用するスライス数および各スライスに設定されるパケット転送キューとスケジューリングコストとの関係を説明するための図である。
【図６】ツリートポロジーの一例を示した図である。
【図７】本発明の一実施形態に係るトラヒックフロー割当装置の主要部の構成を示した機能ブロック図である。
【図８】スライスごとに複数のツリートポロジー候補を作成する手順を示したフローチャートである。
【図９】本発明によるスライス間でのパケット転送キューの共用によるリンク帯域の共用の他の例を示した図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態について詳細に説明する。ここでは初めに、本発明におけるパケット転送キューの共用によるリンク帯域の共用およびその際のツリートポロジーの有用性について説明し、次いで、ツリートポロジーを前提にリンク帯域の共用によりスケジューリングコストを最小化できるトラヒックフロー割り当ての方法について詳細に説明する。
【００１７】
なお、本実施形態におけるスケジューリングコストとは、各ノードが各トラヒックフローのパケットをその優先クラスに応じた優先度で転送するために要する処理コストであり、リンク帯域を共有するスライス数やパケット転送キュー数に依存する。
【００１８】
本発明では、典型的には図１に示したように、複数のスライス（ここでは、２つのスライス#1，#2）において同一の物理リンクにそれぞれ設けていたパケット転送キューを一つにまとめ、複数のスライス#1，#2に一つのパケット転送キューを共用させることにより、当該リンクに関してスライス#1，#2のそれぞれに割り当てられていたリンク帯域の総和をスライス#1，#2が共用するトラヒックフロー割当を実現する。
【００１９】
一方、トラヒックフローに複数の優先クラスが設けられているスライスでは、一般的に優先クラスに応じて相対的に優劣のある帯域割り当てが行われるが、このような帯域割当は契約サービスの料金等に基づくものなので、優先クラスの高いパケット転送が増えた結果、優先クラスの低いパケット転送機会が失われてサービス品質が低下したとしても、スライス内では不公平感はあまり無い。
【００２０】
しかしながら、図２に示したように、トラヒックフローに複数の優先クラスが設けられているスライス（#3，#4）にリンク帯域を共用させると、一方のスライス（ここでは、スライス#4）のトラヒックフローが増加して高優先トラヒックフローが増えると、他方のスライス（ここでは、スライス#3）の、特に低優先トラヒックフローに割り当てられるべき帯域が浸食されてしまい、そのサービス品質に低下が生じるので不公平が生じる。
【００２１】
そこで、本発明ではパケット転送キューの共用によるリンク帯域の共用の対象とするスライスを、各リンクに単一かつ同一の優先クラスのトラヒックフローのみが流れるスライス同士に限定した。
【００２２】
なお、このようなスライスの組み合わせには、図１に示したように、優先クラスが唯一であるスライス同士のみならず、図３，４に示したように、スライスとしては優先クラスの異なるトラヒックフローが存在するものの、リンク単位では、高優先トラヒックフローのみが流れるスライス（図３）、低優先トラヒックフローのみが流れるスライス（図４）のように、優先クラスが唯一となるスライス同士でも同様なので、当該スライスについてはリンク帯域の共用対象とした。
【００２３】
なお、図１ないし図４では説明の都合上、２つのスライス間でのリンク帯域の共用を例にして説明したが、図５に示したように、例えば８つのスライス#1〜#8により共用されるリンクでは、スライス#1，#2はリンク帯域を共用し、スライス#3，#4は共用せず、スライス#5，#6は共用し、スライス#7，#8は共用することになる。
【００２４】
本発明では、ネットワーク全体で、上記のようなスライス間のパケット転送キューおよびリンク帯域の共用を促進し、パケット転送のスケジューリングコストを最小化するトラヒックフロー割当を実現する。
【００２５】
最小化されるパケット転送スケジューリングコストは、各リンクにおけるパケット転送スケジューリングコストの総和である。各リンクにおけるパケット転送スケジューリングコストは、スライス間スケジューリングコストとスライス内スケジューリングコストとの和である。
【００２６】
スライス間スケジューリングコストは、リンク帯域を共用するスライス数が１以下の時はゼロであり、スライス数が２以上の時にはスライス数に比例する。なお、スライス数は、リンク帯域の共用を図った後のスライス数である。したがって、図１，３，４の例では「0」、図５の例では、[#1+#2]，[ #3]，[ #4]，[ #5+#6]および[ #7+#8]の「5」となる。
【００２７】
なお、スライス間スケジューリングコストとして、各スライス対応に設けられるパケット転送処理を行う仮想マシンの台数を考える時は、スライス間スケジューリングコストは単純にスライス数に比例する。したがって、図１，３，４の例では「1」、図５の例では、[#1+#2]，[ #3]，[ #4]，[ #5+#6]および[ #7+#8]の「5」となる。
【００２８】
一方、スライス内のスケジューリングコストは、各スライスにおけるスケジューリングコストの総和である。各スライスにおけるスケジューリングコストは、パケット転送キューの個数が１以下の時はゼロであり、パケット転送キューの個数が２以上の時には、パケット転送キュー数に比例する。したがって、図１，３，４の例では「0」、図５の例では、スライス#3における「2」およびスライス#4における「2」の計「4」となる。
【００２９】
本発明では、リンク帯域制御を行う必要があるスライス間のスケジューリングコストを最小化するトラヒックフロー割当を実現し、さらにスライス間スケジューリングコストが等しい場合には、スライス内のスケジューリングコストを最小化するトラヒックフロー割当を実現する。
【００３０】
一方、本発明によるパケット転送キューの共用によるリンク帯域の共用では、リンク帯域を共用できるスライスが、当該リンクを通過するトラヒックフローの優先クラスが１種類であるスライス同士に制限される。したがって、リンク帯域の共用をより促進するためには、各スライスには、通過するトラヒックフローの優先クラスが１種類であるリンクをより多く含むトポロジーであることが望まれる。
【００３１】
ここで、ループを含むことが無いツリー構造のネットワークトポロジーに注目すると、図６に示したように、最下層のリーフをエンドノードとみなせば、当該エンドノードに近いリンクには当該エンドノードを始点または終点とするトラヒックフローしか流れないので優先クラスが１種類である可能性が高くなる。また、エンドノードから離れたリンクほどより多くのトラヒックフローに共用されることになるので、通過するトラヒックフローの優先クラスが複数である可能性が高くなる。
【００３２】
すなわち、各スライスをツリートポロジーにできれば、各リンクを通過するトラヒックフロー数の不均等化が図られ、通過するトラヒックフローの優先クラスが１種類であるリンク数が増えるので、スライス間でのリンク帯域の共用が促進される。
【００３３】
のみならず、後に詳述するように、本発明では全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当が整数計画法モデルの解として計算されるが、各スライスのネットワークトポロジーを予めツリートポロジーに限定できれば計算リソースを大幅に削減できる。
【００３４】
そこで、本発明ではスライスごとに、要求されているトラヒックフローを満足できる複数のツリートポロジー候補を予め用意し、スライス間での各ツリートポロジー候補の組み合わせの中から、スケジューリングコストを最小化できる組み合わせを整数計画法モデルの解として計算するようにした。
【００３５】
図７は、本発明の一実施形態に係るトラヒックフロー割当装置１の主要部の構成を示した機能ブロック図である。このようなトラヒックフロー割当装置１は、汎用のコンピュータやサーバに、後述する各機能を実現するアプリケーション（プログラム）を実装することで構成できる。あるいは、アプリケーションの一部がハードウェア化またはROM化された専用機や単能機として構成しても良い。
【００３６】
入力インタフェース（I/F）１０は、ネットワークのトポロジー情報の入力を受け付けて記憶するトポロジー情報受付部１０ａ、およびトラヒックフロー情報の入力を受け付けて記憶するトラヒックフロー情報受付部１０ｂを含む。
【００３７】
ツリートポロジー候補作成部２０は、ネットワークのトポロジー情報およびトラヒックフロー情報に基づいて、スライスごとにトラヒックフローの経路を合成して構成される複数のツリートポロジー候補を作成する。
【００３８】
図８は、スライスごとに複数のツリートポロジー候補を作成する手順を示したフローチャートであり、イーサネット(登録商標)においてループ構成を回避するためのスパニングツリープロトコルとして知られている。
【００３９】
本実施形態では、スライスごとに当該スライスに属するトラヒックフローが１本ずつランダムに選択され、最小コスト経路計算法によるトラヒックフローの割当が逐次的に実現される。そして、トラヒックフローの割当が行われるごとに、当該トラヒックフローに割当てられたリンクのコストを十分小さな値に更新し、当該スライスに属する全てのトラヒックフローの割当が終了した時点でコストが十分に小さな値に更新されているリンク群が、得られたツリートポロジー候補を示す。本実施形態では、以上の処理がスライスごとに所定のツリートポロジー候補数分だけ繰り返される。
【００４０】
すなわち、ステップS１０１ではリンク帯域の共用対象となるスライスのリストが作成される。ステップS１０２では、前記スライスリストから今回注目する一のスライス（注目スライス）が取り出される。ステップS１０３では、ツリートポロジー候補数Ncadに初期値として「１」がセットされる。
【００４１】
ステップS１０４では、前記注目スライスのフローリストがトラヒックフロー情報に基づいて作成される。ステップS１０５では、全てのリンクコストが「1.0」に初期設定される。ステップS１０６では、前記フローリストからランダムに一のトラヒックフローが選択されて注目トラヒックフローとされる。
【００４２】
ステップS１０７では、前記注目トラヒックフローに対して最小コスト経路が割り当てられる。ステップS１０８では、注目トラヒックフローが通過するリンクのコストが十分に小さな値（例えば、0.001）に設定される。
【００４３】
ステップS１０９では、前記フローリストに登録されている全てのトラヒックフローに関して最小コスト経路の割り当てが完了したか否かが判定される。完了していなければステップS１０５へ戻り、注目トラヒックフローを切り替えながら前記最小コスト経路の割当およびリンクコストの更新が繰り返される。
【００４４】
その後、フローリストに登録されている全てのトラヒックフローに関する処理が完了したと判定されるとステップS１１０へ進み、コストの低いリンク集合が今回の注目スライスに関するツリートポロジー候補の一つとして登録される。ステップS１１１では、ツリートポロジー候補数Ncadがインクリメントされる。
【００４５】
ステップS１１２では、ツリートポロジー候補数Ncadが所定の候補数に達したか否かが判定される。所定の候補数に達していなければ、ステップS１０４へ戻って上記の各処理が繰り返され、今回の注目スライスについて別のツリートポロジー候補が作成される。
【００４６】
本実施形態では、スライスごとにフローリストに登録されたトラヒックフローが最終的には全て選択されることになるので、注目されるトラヒックフロー群は毎回同一である。しかしながら、ランダムな順序で注目される各トラヒックフローの最小コスト経路を探索する過程で、トラヒックフローが一度でも通過したリンクはリンク集合に加えられると同時に、そのコストが十分小さな値に更新される。
【００４７】
従って、任意のノードAとノードBとが、リンク集合に含まれるリンクのみによって構成される経路で接続されていれば、その経路のコストは十分小さく、以後のトラヒックフローの最小コスト経路が、もしノードAとノードBを通過するのであれば必ず同じ経路を辿ることになる。すなわち、リンク集合に含まれるリンクによって、ノードAとノードBとを含むループ経路が構成されることはない。従ってリンク集合はループを含まないトポロジー、すなわちツリートポロジーを構成することになる。
【００４８】
その後、ステップS１１２において、今回の注目スライスに関して所定数のツリートポロジー候補が取得できたと判定されるとステップS１１３へ進み、これらのツリートポロジー候補が当該注目スライスのツリートポロジー候補群として登録される。ステップS１１４では、全てのスライスに関してツリートポロジー候補群の抽出が完了したか否かが判定される。完了していなければステップS１０２へ戻り、注目スライスを切り替えながら上記の各処理が繰り返され、スライスごとにNcad個のツリートポロジー候補群が抽出される。
【００４９】
図７へ戻り、トラヒックフロー割当計算部３０は、前記トポロジー情報および各スライスにおけるツリートポロジー候補情報を入力とする整数計画法モデルを解いて、パケット転送のスケジューリングコストを最小化する、ツリートポロジー候補の組み合わせおよびトラヒックフローの割当結果を出力する。
【００５０】
ネットワークのトポロジー情報は、ネットワークを構成するノード集合およびリンク集合を含む。ツリートポロジー候補情報は、各ツリートポロジー候補を構成する、当該スライスに含まれるトラヒックフローの経路に関する情報である。整数計画法モデルにおける定数および集合は以下のように定義される。
Node：ノード集合
node：ノード
s：発ノード
d：着ノード
t：中継ノード
Link：リンク集合
link：リンク
node inout：ノードnodeに接続するリンクの集合
Flow：トラヒックフロー集合
f：トラヒックフロー
Pr：優先クラス集合
pr：優先クラス
Sl：スライス集合
sl：スライス
FPr (pr)：優先クラスprに属するトラヒックフロー集合
FSl (sl)：スライスslに属するトラヒックフロー集合
MCad：各スライスにおけるツリートポロジー候補数
cad：ツリートポロジー候補。
X f, cad (link)：トラヒックフローfを含むスライスにおいて、ツリートポロジー候補cadが選択される時、トラヒックフローfがリンクlinkを通過する時に「1」、そうでない時に「0」であるバイナリー定数
A：十分大きな値を持つ定数
【００５１】
また、各変数は以下のように定義される。
Y sl, cad：スライスslにおいて、ツリートポロジー候補cadが選択される時に「1」、そうでない時に「0」であるバイナリー変数
Q pr, sl (link)：スライスslにおいて優先クラスpr に属するトラヒックフローが、リンクlink を通過する時に「1」、そうでない時に「0」であるバイナリー変数
Q1 sl (link)：スライスslにおいて１つ以上の優先クラスに属するトラヒックフローが、リンクlink を通過する時に「1」、そうでない時に「0」であるバイナリー変数
Q2 sl (link)：スライスslにおいて２つ以上の優先クラスに属するトラヒックフローが、リンクlink を通過する時に「1」、そうでない時に「0」であるバイナリー変数
NQ pr (link)：あるスライスにおいて、優先クラスpr に属するトラヒックフローのみが、リンクlink を通過する時に「1」、そうでない時に「0」であるバイナリー変数
SQ (link)：２つ以上のスライスに属するトラヒックフローが、リンクlink を通過する時に「1」、そうでない時に「0」であるバイナリー変数
【００５２】
整数計画法モデルにおいて、各スライスにおいて選択されるツリートポロジー候補の条件は次式(1)で与えられる。
【００５３】
【数１】
2015126355.tif 000003
【００５４】
次式(2)は、各スライスにおいて各優先クラスに属するトラヒックフローが各リンクを通過する条件であり、Q pr, sl (link)は、ΣΣ(X f, cad (link)×Y sl, cad)が０以下であれば「0」、１以上であれば「1」となる。
【００５５】
【数２】
2015126355.tif 000004
【００５６】
次式(3)は、各スライスにおいて、１つ以上の優先クラスに属するトラヒックフローがリンクを通過する条件であり、Q1 sl (link)は、ΣQ pr, sl (link)が０以下であれば「0」、１以上であれば「１」となる。
【００５７】
【数３】
2015126355.tif 000005
【００５８】
次式(4)は、各スライスにおいて、２つ以上の優先クラスに属するトラヒックフローがリンクを通過する条件であり、Q2 sl (link)は、ΣQ pr, sl (link)-1が０以下であれば「0」、１以上であれば「１」となる。
【００５９】
【数４】
2015126355.tif 000006
【００６０】
次式(5)は、あるスライスにおいて、各優先クラスに属するトラヒックフローのみがリンクを通過する条件である。
【００６１】
【数５】
2015126355.tif 000007
【００６２】
次式(6)は、２つ以上のスライスに属するトラヒックフローがリンクを通過する条件であり、SQ (link)は、ΣQ2 sl (link)+ΣNQ pr (link)-1が０以下であれば「0」、１以上であれば「１」となる。
【００６３】
【数６】
2015126355.tif 000008
【００６４】
最小化すべきパケット転送のスケジューリングコストは、次式(7)のように表される。
【００６５】
【数７】
2015126355.tif 000009
【００６６】
上式(7)において、上段の定数W1に乗じられる項は、スライス間のスケジューリングコストを表し、定数W1は、スライス数をスライス間スケジューリングコストに換算する比例定数を表している。下段の定数W2に乗じられる項は、スライス内のスケジューリングコストを表し、定数W2は、パケット転送キュー数をスライス内スケジューリングコストに換算する比例定数を表している。
【００６７】
前記定数W1に乗じられる項において、第１項（ΣQ2 sl…）は、今回の注目リンクlink（∈Link）に、同一スライス内で優先クラスの異なる複数のトラヒックフローが流れるスライス総数、すなわち当該注目リンクに関して、単独でスライス間スケジューリングが必要となるスライス総数であり、前記スライス#3，#4に相当する。
【００６８】
第２項（ΣNQ…）は、今回の注目リンクlink（∈Link）に、当該優先クラスに属するトラヒックフローのみが流れるスライスが存在するような優先クラス（pr）の総数であり、前記スライス[#1+#2]，[ #5+#6]，[ #7+#8]に対応する優先クラスに相当する。すなわち、当該注目リンクに関して、１つの優先クラスに属するトラヒックフローのみが流れるリンク帯域共用の対象と成り得るスライスについて、リンク帯域の共用が図られた後のスライス総数を表す。
【００６９】
ただし、注目リンクが複数のスライスで共用されていなければ、当該注目リンクに関するスライス間スケジューリングは不要なので、これらの和にはSQ (link)が乗じられる。なお、スライス間スケジューリングコストとして、各スライス対応に設けられるパケット転送処理を行うための仮想マシンの台数を考える時は、SQ (link)を乗じない。
【００７０】
前記定数W2に乗じられる項は、今回の注目リンクlinkにおいて、スライス内のスケジューリングが必要となる、複数の異なる優先クラスのトラヒックフローが流れるスライスslに含まれる、パケット転送キューの総数であり、前記スライス#3，#4において２つずつ設けられるパケット転送キューに相当する。
【００７１】
本実施形態では、W2の値に比べてW1の値が十分大きく設定される。これにより、スライス間のスケジューリングコストを最小化するトラヒックフロー割当が実現され、更にスライス間スケジューリングコストが等しい場合には、スライス内のスケジューリングコストを最小化するトラヒックフロー割当が実現される。各トラヒックフローの割当結果は、各スライスにおいて選択されたツリートポロジー候補を表す変数Y sl, cadの値から、定数X f, cad (link)の値よって知ることができる。
【００７２】
本実施形態によれば、SDNの各スライスにおいて、予め与えられた複数のツリートポロジー候補の中から、最もパケット転送スケジューリングコストを削減するツリートポロジー候補を選択するために整数計画法モデルの求解を行うのみなので、大量の計算リソースを必要とせず、規模の大きなSDNにも適用できる。
【００７３】
また、本実施形態によれば、仮想ネットワークである各スライス上でツリートポロジー候補を構成することにより、各スライスにおいて通過するトラヒックフローの優先クラスが１種類であるリンクの割合を増加させて、スライス間でのパケット転送キューおよびリンク帯域の共用を促進し、リソース利用効率の向上を図ることができる。
【００７４】
なお、上記の実施形態では、リンク帯域の共用対象となるスライス組を、リンクを通過するトラヒックフローの優先クラスが唯一かつ同一のスライス同士とし、優先クラスの異なる複数のトラヒックフローが通過するスライス同士は共用の対象外であるものとして説明した。
【００７５】
しかしながら、優先クラスの異なる複数のトラヒックフローが通過するスライス同士であっても、図９に示したように、スライス内の各優先クラスにリンク帯域が固定的に割り当てられていれば、対応する優先クラス同士でパケット転送キューを一つにまとめて共用させることで、優先クラスごとに各リンク帯域の総和を共用させても良い。このとき、各スライスの対応する優先クラスに割り当てられていた帯域は必ずしも同一でなくて良い。
【００７６】
このようにすれば、優先クラスが同一のパケット同士は公平に扱われ、一方のスライスの高優先トラヒックフローが増加しても、他方のスライスの低優先トラヒックフローに割り当てられるべき帯域は確保される。したがって、サービス品質を不公平に低下させることなくリンク帯域の利用効率を向上させることができる。
【符号の説明】
【００７７】
１…トラヒックフロー割当装置，１０…入力インタフェース，１０ａ…トポロジー情報受付部，１０ｂ…トラヒックフロー情報受付部，２０…ツリートポロジー候補作成部，３０…トラヒックフロー割当計算部
【図１】
2015126355.tif 000010
【図２】
2015126355.tif 000011
【図３】
2015126355.tif 000012
【図４】
2015126355.tif 000013
【図５】
2015126355.tif 000014
【図６】
2015126355.tif 000015
【図７】
2015126355.tif 000016
【図８】
2015126355.tif 000017
【図９】
2015126355.tif 000018