(57)【要約】【課題】SDNの各スライスが物理リンクごとに一つのパケット転送キューを共用してリンク帯域を共用するラヒックフロー割当方法および装置を提供する。【解決手段】入力インタフェース１０は、ネットワークのトポロジー情報の入力を受け付けて記憶するトポロジー情報受付部１０ａ、およびトラヒックフロー情報の入力を受け付けて記憶するトラヒックフロー情報受付部１０ｂを含む。トラヒックフロー割当計算部２０は、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下で、トポロジー情報およびトラヒックフロー情報を入力とする整数計画法モデルを解いて、パケット転送のスケジューリングコストを最小化するトラヒックフローの割当結果を出力する。【選択図】図６
2015119408.tif 000002
【特許請求の範囲】
【請求項１】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手段と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを具備し、
前記トラヒックフロー割当を計算する手段は、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当装置。
【請求項２】
前記トラヒックフロー割当を計算する手段は、各リンクについて、複数のスライスに当該リンクを共用させるためのスライス間スケジューリングコスト、および同一のスライス内で複数の優先クラスのトラヒックフローに当該リンクを共用させるためのスライス内スケジューリングコストの総和が最小となるトラヒックフロー割当を計算することを特徴とする請求項１に記載のトラヒックフロー割当装置。
【請求項３】
前記スライス間スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士に当該リンクの帯域を共有させて１スライスとみなしたときに当該リンクを共用するスライス数に比例した値であることを特徴とする請求項２に記載のトラヒックフロー割当装置。
【請求項４】
前記スライス間スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士に当該リンクの帯域を共有させて１スライスとみなしたときに当該リンクを共用するスライス数に依存し、スライス数が「１」以下のリンクではゼロ、「２」以上のリンクでは当該スライス数に比例した値であることを特徴とする請求項２に記載のトラヒックフロー割当装置。
【請求項５】
前記スライス内スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士にリンク帯域を共有させて１スライスとみなしたときのパケット転送キュー数に依存し、パケット転送キュー数が「１」以下のスライスではゼロ、「２」以上のスライスでは当該パケット転送キュー数に比例した値であることを特徴とする請求項２ないし４のいずれかに記載のトラヒックフロー割当装置。
【請求項６】
前記整数計画法モデルは、優先クラスの異なるトラヒックフロー同士にリンク帯域を共用させないことを特徴とする請求項１ないし５のいずれかに記載のトラヒックフロー割当装置。
【請求項７】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手段と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを具備し、
前記トラヒックフロー割当を計算する手段は、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが複数であるスライスのうち、相互に対応する優先クラスを有し、かつ各優先クラスにリンク帯域が固定的に割り当てられているスライス同士に、対応する優先クラスのリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当装置。
【請求項８】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当方法において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手順と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手順とをコンピュータに実行させ、
前記トラヒックフロー割当の計算では、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当方法。
【請求項９】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当方法において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手順と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手順手段とをコンピュータに実行させ、
前記トラヒックフロー割当の計算では、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが複数であるスライスのうち、相互に対応する優先クラスを有し、かつ各優先クラスのリンク帯域が固定的なスライス同士に、対応する優先クラスのリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め発着ノード等の属性が与えられたトラヒックフロー群に対してネットワーク上の経路を割り当てるトラヒックフロー割当方法および装置に係り、特に、SDN（Software-Defined Network）の各スライス（仮想ネットワーク）間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当方法および装置に関する。
【背景技術】
【０００２】
ソフトウェアによって仮想的なネットワークを作り上げる技術として、非特許文献１，２にSDNが開示されている。SDNでは、一つの物理ネットワーク上に「スライス」と呼ばれる完全に独立した仮想的なネットワークをいくつも構築できるため、スライスごとにユーザの要求に応じた固有のネットワークを構築できる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】「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の各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手段と、トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを設けた。
【０００８】
ここで、前記トラヒックフロー割当を計算する手段は、ネットワークのリンクごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下でトラヒックフロー割当を計算するようにした。
【発明の効果】
【０００９】
本発明によれば、以下のような効果が達成される。
【００１０】
(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）１０は、ネットワークのトポロジー情報の入力を受け付けて記憶するトポロジー情報受付部１０ａ、およびトラヒックフロー情報の入力を受け付けて記憶するトラヒックフロー情報受付部１０ｂを含む。
【００２９】
トラヒックフロー割当計算部２０は、前記トポロジー情報およびトラヒックフロー情報を入力とする整数計画法モデルを解いて、パケット転送のスケジューリングコストを最小化するトラヒックフローの割当結果を出力する。
【００３０】
ネットワークのトポロジー情報は、ネットワークを構成するノード集合およびリンク集合を含む。トラヒックフロー情報は、各トラヒックフローの発ノード、着ノード、所属優先クラス、所属スライスによって構成される。整数計画法モデルにおける定数および集合は以下のように定義される。
Node：ノード集合
node：ノード
s：発ノード
d：着ノード
t：中継ノード
Link：リンク集合
link：リンク
node inout：ノードnodeに接続するリンクの集合
Flow：トラヒックフロー集合
f：トラヒックフロー
Pr：優先クラス集合
pr：優先クラス
Sl：スライス集合
sl：スライス
FPr (pr)：優先クラスprに属するトラヒックフロー集合
FSl (sl)：スライスslに属するトラヒックフロー集合
A：十分大きな値を持つ定数
【００３１】
また、各変数は以下のように定義される。
X f, link：トラヒックフローfが、リンクlinkを通過する時に「1」、そうでない時に「0」であるバイナリー変数
Y f, node：トラヒックフローfが、ノードnodeを通過する時に「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)〜(3)で与えられる。これらはトラヒックフロー経路の保存則であり、(1)式は、発ノードsから出る各フローの経路数が「１」であるという制約である。(2)式は、着ノードdに入る各フローの経路数が「１」であるという制約である。(3)式は、発着ノードs，d以外のノードtについて、各フローの経路が通過しないか、もしくは１回のみ通過するという制約である。
【００３３】
【数１】
2015119408.tif 000003
【００３４】
【数２】
2015119408.tif 000004
【００３５】
【数３】
2015119408.tif 000005
【００３６】
次式(4)は、各スライスにおいて各優先クラスに属するトラヒックフローが各リンクを通過する条件であり、Q pr, sl (link)は、ΣX f, linkが０以下であれば「0」、１以上であれば「1」となる。
【００３７】
【数４】
2015119408.tif 000006
【００３８】
次式(5)は、各スライスにおいて、１つ以上の優先クラスに属するトラヒックフローがリンクを通過する条件であり、Q1 sl (link)は、ΣQ pr, sl (link)が０以下であれば「0」、１以上であれば「１」となる。
【００３９】
【数５】
2015119408.tif 000007
【００４０】
次式(6)は、各スライスにおいて、２つ以上の優先クラスに属するトラヒックフローがリンクを通過する条件であり、Q2 sl (link)は、ΣQ pr, sl (link)-1が０以下であれば「0」、１以上であれば「１」となる。
【００４１】
【数６】
2015119408.tif 000008
【００４２】
次式(7)は、あるスライスにおいて、各優先クラスに属するトラヒックフローのみがリンクを通過する条件である。
【００４３】
【数７】
2015119408.tif 000009
【００４４】
次式(8)は、２つ以上のスライスに属するトラヒックフローがリンクを通過する条件であり、SQ (link)は、ΣQ2 sl (link)+ΣNQ pr (link)-1が０以下であれば「0」、１以上であれば「１」となる。
【００４５】
【数８】
2015119408.tif 000010
【００４６】
最小化すべきパケット転送のスケジューリングコストは、次式(9)のように表される。
【００４７】
【数９】
2015119408.tif 000011
【００４８】
上式(9)において、上段の定数W1に乗じられる項は、スライス間のスケジューリングコストを表し、定数W1は、スライス数をスライス間スケジューリングコストに換算する比例定数を表している。下段の定数W2に乗じられる項は、スライス内のスケジューリングコストを表し、定数W2は、パケット転送キュー数をスライス内スケジューリングコストに換算する比例定数を表している。
【００４９】
前記定数W1に乗じられる項において、第１項（ΣQ2sl…）は、今回の着目リンク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の値が十分大きく設定される。これにより、スライス間のスケジューリングコストを最小化するトラヒックフロー割当が実現され、更にスライス間スケジューリングコストが等しい場合には、スライス内のスケジューリングコストを最小化するトラヒックフロー割当が実現される。各トラヒックフローの割当結果は、変数X f, linkまたはY f, nodeの値で示される。
【００５４】
本発明によれば、SDNにおいて、他スライスのパケット転送品質へ影響を及ばさない範囲で、各スライス間でのパケット転送キューおよびリンク帯域の共用が促進され、パケット転送のスケジューリングコストを最小化するトラヒックフロー割当を実現できる。また、各スライス間でのパケット転送キューおよびリンク帯域の共用が促進されるので、リンク帯域の利用効率が向上する。
【００５５】
なお、上記の実施形態では、リンク帯域の共用対象となるスライス組を、リンクを通過するトラヒックフローの優先クラスが唯一かつ同一のスライス同士とし、優先クラスの異なる複数のトラヒックフローが通過するスライス同士は共用の対象外であるものとして説明した。
【００５６】
しかしながら、優先クラスの異なる複数のトラヒックフローが通過するスライス同士であっても、図７に示したように、スライス内の各優先クラスにリンク帯域が固定的に割り当てられていれば、対応する優先クラス同士でパケット転送キューを一つにまとめて共用させることで、優先クラスごとに各リンク帯域の総和を共用させても良い。このとき、各スライスの対応する優先クラスに割り当てられていた帯域は必ずしも同一でなくて良い。
【００５７】
このようにすれば、優先クラスが同一のパケット同士は公平に扱われ、一方のスライスの高優先トラヒックフローが増加しても、他方のスライスの低優先トラヒックフローに割り当てられるべき帯域は確保される。したがって、サービス品質を不公平に低下させることなくリンク帯域の利用効率を向上させることができる。
【符号の説明】
【００５８】
１…トラヒックフロー割当装置，１０…入力インタフェース，１０ａ…トポロジー情報受付部，１０ｂ…トラヒックフロー情報受付部，２０…トラヒックフロー割当計算部
【図１】
2015119408.tif 000012
【図２】
2015119408.tif 000013
【図３】
2015119408.tif 000014
【図４】
2015119408.tif 000015
【図５】
2015119408.tif 000016
【図６】
2015119408.tif 000017
【図７】
2015119408.tif 000018
【手続補正書】
【提出日】平成25年12月26日(2013.12.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手段と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを具備し、
前記トラヒックフロー割当を計算する手段は、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当装置。
【請求項２】
前記トラヒックフロー割当を計算する手段は、各リンクについて、複数のスライスに当該リンクを共用させるためのスライス間スケジューリングコスト、および同一のスライス内で複数の優先クラスのトラヒックフローに当該リンクを共用させるためのスライス内スケジューリングコストの総和が最小となるトラヒックフロー割当を計算することを特徴とする請求項１に記載のトラヒックフロー割当装置。
【請求項３】
前記スライス間スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士に当該リンクの帯域を共有させて１スライスとみなしたときに当該リンクを共用するスライス数に比例した値であることを特徴とする請求項２に記載のトラヒックフロー割当装置。
【請求項４】
前記スライス間スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士に当該リンクの帯域を共有させて１スライスとみなしたときに当該リンクを共用するスライス数に依存し、スライス数が「１」以下のリンクではゼロ、「２」以上のリンクでは当該スライス数に比例した値であることを特徴とする請求項２に記載のトラヒックフロー割当装置。
【請求項５】
前記スライス内スケジューリングコストは、各リンクを通過するトラヒックフローの優先クラスが唯一かつ同一であるスライス同士にリンク帯域を共有させて１スライスとみなしたときのパケット転送キュー数に依存し、パケット転送キュー数が「１」以下のスライスではゼロ、「２」以上のスライスでは当該パケット転送キュー数に比例した値であることを特徴とする請求項２ないし４のいずれかに記載のトラヒックフロー割当装置。
【請求項６】
前記整数計画法モデルは、優先クラスの異なるトラヒックフロー同士にリンク帯域を共用させないことを特徴とする請求項１ないし５のいずれかに記載のトラヒックフロー割当装置。
【請求項７】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当装置において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手段と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手段とを具備し、
前記トラヒックフロー割当を計算する手段は、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが複数であるスライスのうち、相互に対応する優先クラスを有し、かつ各優先クラスにリンク帯域が固定的に割り当てられているスライス同士に、対応する優先クラスのリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当装置。
【請求項８】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当方法において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手順と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手順とをコンピュータに実行させ、
前記トラヒックフロー割当の計算では、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが１種類である複数のスライスのうち、当該優先クラスが同一のスライス同士にリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当方法。
【請求項９】
SDNの各スライス間でパケット転送キューの共用によるリンク帯域の共用を実現するトラヒックフロー割当を算出するトラヒックフロー割当方法において、
ネットワークのトポロジー情報およびトラヒックフロー情報を取得する手順と、
前記トポロジー情報およびトラヒックフロー情報を入力として、全てのリンクのパケット転送に関するスケジューリングコストの総和を最小化するトラヒックフロー割当を整数計画法モデルの解として計算する手順とをコンピュータに実行させ、
前記トラヒックフロー割当の計算では、ネットワークのリングごとに、当該リンクを通過するトラヒックフローの優先クラスが複数であるスライスのうち、相互に対応する優先クラスを有し、かつ各優先クラスのリンク帯域が固定的なスライス同士に、対応する優先クラスのリンク帯域を共用させる条件下でトラヒックフロー割当を計算することを特徴とするトラヒックフロー割当方法。
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2015119408.tif 000019