Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report

可視化コンテンツ共有のためのネットワークスライス自動構築システム
遠藤 新1,a)

木戸 善之2伊達 進2下條 真司2

概要：研究において生成される実験結果やシミュレーション結果を映像や画像に変換したものである可視化コンテンツを共有することは重要である．大容量かつ大規模な可視化コンテンツの共有には十分なネッ
トワーク資源の確保が必要となる．可視化コンテンツの共有を行うユーザグループからネットワーク資源の確保を依頼されるネットワーク管理者は，独立したネットワーク資源を割り当てた論理ネットワークであるネットワークスライスを構築する．しかし，ユーザからの多様な要求を聞き入れる必要がある，かつ，
複数のネットワークスライスが混在するため，可視化コンテンツ共有のためのネットワーク資源割り当てを最適化することは困難である．本研究では，可視化コンテンツ共有のためにネットワークスライスを自動で構築するシステムの実現の一環として，可視化コンテンツ共有の多様な要求に対応してネットワーク
スライスの構成を決定するスケジューリング手法を提案する．評価では，提案手法についてシミュレー
ションを行い，より多いユーザグループへのネットワークスライスの提供が可能なことを確認した．
キーワード：可視化コンテンツ共有，仮想ネットワーク自動生成，ネットワークスケジューリング

Automatic Construction System of Network Slices
for Sharing Visualization Contents
Arata Endo1,a)Yoshiyuki Kido2

Susumu Date2

Shiji Shimojo2

Abstract: In collaboration researches, it is important to share visualization contents, or, images or movies
into which experimentation and simulation results of researches are transformed. An user group requires
enough network resources to share large-scale and -capacity visualization contents so that it asks a network
administrator to allocate the network resources to itself. The network administrator constructs a network
slice, that is, a logical network with the network resources independent from other logical networks for the
allocation. However, it is diﬃcult for the network administrator to optimize the network resource allocation for sharing visualization contents because meeting diverse requirements of user groups and constructing
multiple network slices are needed. In this research, we propose the scheduling method to meet the diverse
requirements as part of the realizing the automatic construction system of network slices for sharing visualization contents. To evaluate the proposed method, we conducted the simulation and verified that more
network slices can be provided to user groups with the proposed method.
Keywords: Visualization Content Sharing, Virtual Network Automatic Genaration, Network Scheduling

1. はじめに12a)

大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology,
Osaka University, Suita, Osaka 565–0871, Japan
大阪大学サイバーメディアセンター
Cybermedia Center, Osaka University
endou.arata@ais.cmc.osaka-u.ac.jpⓒ 2017 Information Processing Society of Japan

共同研究における研究者同士の意見交換をサポートする
共同研究基盤の重要性が高まっている．共同研究では，研
究者はそれぞれ地理的に離れた拠点に属しており，研究者

1Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report

は自身の拠点とは別の拠点に所属する研究者と共同作業す

この手法は，単一端末における操作のみで，独立した帯域

ることが共同研究活動の上で必要となる．遠隔地間での研幅やトポロジを割り当てた論理ネットワークであるネット

究活動を支援する基盤，つまり共同研究基盤は，共同研究

ワークスライスを OpenFlow ネットワーク上に生成する．

の件数は年々増加しているため，今後重要となることが予

このように，スケジューリング手法の問題によってネット測される．

ワークスライス自動構築システムの実現が困難となって共同研究基盤の 1 つの要素として，高解像度な可視化コいる．

ンテンツの表示が可能である大規模可視化装置がある．研

本研究では，ネットワーク管理者の負担の解消のために，究の議論において，実験やシミュレーションから得られる可視化コンテンツ共有を可能とするネットワークスライス

知見の共有は重要である．知見の共有には直感的な理解やを複数のユーザグループに対して提供するシステムの実現分析が必要であり，実験結果である数値データを画像や映を目指す．そのために，可視化コンテンツ共有に応じて発像に変換した可視化コンテンツは，直感的な理解や分析を生するユーザグループの多様な要求に対応し，最適なネッ容易にする．大規模可視化装置は，4K や 8K などの高解トワーク資源の割り当てを可能とするスケジューリング手

像度を持つ可視化コンテンツを高精細に表示可能な装置で法を提案する．提案手法を用い，ネットワークスライス自ある．代表例としては，Tiled Display (TD) [7] がある．

動構築システムのプロトタイプを実現することを本研究のしかし，各拠点の大規模可視化装置間で高解像度な可視目的とする．

化コンテンツを共有し，同時視聴や協調的な操作を行うこ

以下，2 章では既存のスケジューリング手法における問とは困難である．可視化コンテンツ共有を広域ネットワー

題を説明する．3 章では，可視化コンテンツ共有に対応す

ク上で実施するユーザグループが高精細，高品質な可視化

るネットワークスライスのスケジューリング手法を提案すコンテンツの視聴を要求する場合，遅延やパケットロスにる．4 章では，提案手法を用いたネットワークスライスをよる可視化コンテンツの品質劣化を回避するのに十分な自動構築するプロトタイプシステムについて説明する．5

ネットワーク資源を確保することが必要となる．ネット

章では，提案手法を評価するため，プロトタイプシステム

ワーク資源の確保には，論理ネットワークの利用とネットを用いたシミュレーション実験を行う．6 章では，本研究

ワークの占有の 2 つの方法があげられる．論理ネットワーのまとめと将来課題について述べる．

クとは，物理ネットワーク上に作成した L2 仮想オーバ
レイネットワークを指す．論理ネットワークの利用には，

2. 既存のスケジューリング手法の問題

ネットワーク管理者を頼ることが必要となる．ネットワー

ユーザグループのリクエストに基づいてネットワーク

ク管理者は，ネットワークのトポロジ，トラフィック，必

スライスに割り当てる帯域幅とトポロジを決定するスケ要となる帯域幅，もしくはホップ数などを考慮して，手動

ジューリング手法の研究としては，Virtual Overlay Net-

でユーザグループの要求する可視化コンテンツ共有のため

work Scheduling [1], [2], [4] がある．これらの研究では，の論理ネットワークを設定する．一方で，ネットワークはランダムに発生する複数のユーザグループからのリクエ

他のユーザグループにとっても共通の基盤であるため，占ストに対して，複数拠点を接続する仮想オーバーレイネッ

有しての利用は難しい．しかし，論理ネットワークの作成

トワーク（ネットワークスライス）に割り当てる帯域幅とにおいてユーザグループ間でのネットワーク資源の割りトポロジをヒューリスティック法で逐次的に算出してい当てを最適化しなければならず，ネットワーク最適化問題

く手法を提案している．具体的なアルゴリズムの例としは，最適解を導き出すことが難しい NP 困難な問題であて， Algorithm 1 を示す．このアルゴリズムを採用するス

る．さらに，広域ネットワーク上の論理ネットワークの経

ケジューラは，管理する物理ネットワークのネットワーク

路上にある全てのスイッチなどのネットワーク機器に対しグラフとリンク帯域幅を把握しているものとする．各定数て，ユーザグループごとに設定を施すことはネットワークと変数は，表 1 で示す．まず，ユーザグループはリクエス

管理者の負担となる．

トをスケジューラに送信する．リクエストを受信したスケ

論理ネットワークに対してネットワーク資源を割り当

ジューラは，物理ネットワークグラフの複製を生成し，そてるスケジューリング手法としては，Gu 氏らの提案するのリクエストが帯域幅の不足により利用できない物理リン

Virtual Overlay Network Scheduling がある [4]．しかし，

クを複製したネットワークグラフから削除する．この複製

この手法は可視化コンテンツ共有に応じて発生するユーザ

したネットワークグラフの上で，3 つのヒューリスティッ

グループの多様な要求に応じてスケジューリングするこク法による経路探索手法のうちいづれかを用いて各仮想とができない．また，この手法はヒューリスティック法をリンクに割り当てる経路を算出する．どの手法を用いるか用いているため，最適なネットワーク資源の割り当てがではスケジューラの実装時に決定される．全ての仮想リンク

きない場合もある．論理ネットワークの設定の自動化につについて経路を算出できた場合は，リクエストを受理し，いては，Sherwood 氏らが提案する Flowvisor がある [8]．

ネットワークスライスに割り当てる帯域幅とトポロジの情ⓒ 2017 Information Processing Society of Japan2

Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report

Algorithm 1 Virtual Overlay Network Scheduling [4]クを利用する可視化コンテンツの解像度に合わせてその仮

1: Given incoming request r n = (S n , Ln , T n , bn ), generate temporary graph copy G′ (V, E) = G(V, E)
2: Remove non-feasible links in G′ (V, E), i.e., ce (t) < bn inn[tn
s , te ]3: for i = 1 to |Ln | do4:
if minimum hop count then5:
Assign unity weight to links in G′ (V, E)
6:
Run Dijkstra’s shortest-path for i-th virtual links
7:
else if minimum distance then8:
Assign dynamic weight to links in G′ (V, E)
9:Run Dijkstra’s shortest-path for i-th virtual links
10:
else
11:
Run k-SP between end-points of i-th virtual link
12:
Select path with maximum bottleneck bandwidth13:
end if
14: end for
15: if all virtual link connections in Ln routed then16:
Setup successful, copy G′ (V, E) → G(V, E)
17: end if

想リンクに要求される帯域幅が異なる．また，可視化コン
テンツがマルチキャストとユニキャストのどちらの手法で配信されるかによって，ネットワークスライスの各仮想リンクに要求される帯域幅が異なる．このように多様なユー
ザグループの要求で必要とされるネットワークスライスに対して，既存のスケジューリング手法では，全ての仮想リ
ンクが同じ帯域幅を持ち，仮想リンク間で物理リンクを共有しないネットワークスライスのみを生成する．この特徴
により，各仮想リンクへの異なる帯域幅の割り当てや，マルチキャストな帯域幅の利用ができず，冗長な帯域幅の割り当てが生じてしまう．
また，既存のスケジューリング手法では，ヒューリス
ティック法を用いるために，帯域幅とトポロジの最適な割り当てができない場合がある．Algorithm 1 で示す手法では，リクエストを到着順に処理し，受理済みのリクエストに対する帯域幅とトポロジの再割り当てはしないため，十分

表 1
定数・変数

各定数と変数の定義

な帯域があっても割り当てができない場合がある．これに定義

対して，Bai 氏らの提案する手法では再割り当てをしないV

ルータやスイッチなどの物理ノード集合

点を改良している [1], [2]．これらの手法では，Algorithm 1

E

物理リンク集合においてある仮想リンクに対する物理経路の割り当てを失G(V, E)

物理ネットワークを表すネットワークグラフn

リクエストを送信したユーザグループ

rnn n
rn = (S n , Ln , tn
s , te , b ) で表されるユーザグルー

プ n のリクエスト

Sn

リクエスト rnが指定するノード集合

敗した時に，その仮想リンクに対して 1 つの候補経路を用意する．そして，用意した候補経路が割り当て可能となるように，受理済みのリクエストに割り当てられた帯域幅とトポロジを再割り当てする．しかし，用意される候補経路

Ln

リクエスト r n が指定する仮想リンク集合

は 1 つだけであり，この経路が最適であるとは限らない．

tns

リクエスト r n が指定する可視化コンテンツ共有を

このことによって，スケジューリングが失敗するリクエス

開始する時間tne

リクエスト r n が指定する可視化コンテンツ共有を終了する時間トが増える場合がある．
帯域幅とトポロジの最適な割り当てを達成する手法としbn

リクエスト r n が指定する帯域幅て整数計画法があるが，スケジューリング手法に整数計画

ce (t)

物理リンク e のリンク帯域幅のうち，時刻 t にネッ法を採用する場合，ユーザグループに対してネットワーク

トワークスライス生成を予約したリクエストが利用

スライスの生成が可能であるかどうか判別するまでの時間

していない帯域幅が長くなることが課題となる．一般的に，ユーザグループのスケジュールには可視化コンテンツ共有の実施だけでな報であるネットワークスライス構成を出力する．

く，他の多くの予定が決められている．ユーザグループが上述した既存のスケジューリング手法では，ネットワー

自身のスケジュールを管理する上で，可視化コンテンツ共

クスライスに帯域幅とトポロジを効率的に割り当てる上有の実施可能な日をできるだけ早く知ることが可能であるで可視化コンテンツ共有におけるユーザグループの多様ことが望ましい．そのためには，リクエスト受理の成否をな要求に対応することは困難である．なぜなら既存のスケできるだけ早くユーザグループに伝えることが必要とな

ジューリング手法では，前提として全ての仮想リンクが同る．しかし，整数計画問題は NP 困難な問題であり，そのじ帯域幅を持ち，仮想リンク間で物理リンクを共有しな計算時間は長く，リクエスト受理の成否を受け取るまでのい，つまり占有利用するネットワークスライスのみを生成

時間が長くなる．上記であげた既存研究 [1], [2], [4] におすることになっている．一方で，可視化コンテンツ共有でいても，整数計画問題が NP 困難な問題であることを理由

は，共有する可視化コンテンツや共有を行うグループ，共に，整数計画法によるスケジューリングは困難であると述有に用いる手段などのユーザグループの要求が変化するご

べられている．

とに，ネットワークスライスに必要な帯域幅やトポロジが変わる．例えば，解像度が異なる複数の可視化コンテンツの共有に提供するネットワークスライスでは，各仮想リンⓒ 2017 Information Processing Society of Japan

3. 提案手法
本研究では，可視化コンテンツ共有における多様なユー

3Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report
リクエスト数が少ない時間帯

⽇中
ヒューリスティック法によるスケジューリングリクエスト
ユーザ リクエスト受理

記録

の成否

暫定的予約

整数計画法によるスケジューリング

リクエスト
リクエスト
リクエスト
リクエスト

最適化

⼊⼒
ネットワークネットワーク
スライス構成ネットワーク
スライス構成ネットワーク
スライス構成スライス構成置き換え

ネットワークネットワーク
スライス構成ネットワーク
スライス構成ネットワーク
スライス構成スライス構成ネットワークスライス生成
指定の⽇時

容易な Algorithm 1 の minimum hop count の手法に沿ったアルゴリズムとする．ただし，全ての仮想リンクへの物
理リンクの割り当てが成功した時，その物理リンク集合から重複する物理リンクを 1 つを残して取り除いたものを，ネットワークスライスに割り当てる．これにより，仮想リンク間で重複する物理リンクの本数分の帯域幅が 1 つのネットワークスライスに割り当てられていた既存手法を修正し，1 本分の帯域幅を割り当てるに止めることができる．

図 1

提案手法の概要

リクエストの少ない時間帯に行われる 2 段階目では，受理した全てのリクエストに対する帯域幅とトポロジの割り

ザグループの要求に対応し，かつ整数計画法による最適な当てを最適化する目的で，整数計画法によるスケジューリ

帯域幅とトポロジの割り当てを行うため，ユーザグループ

ングを行う．リクエストを出すユーザグループは勤務時間から受け付けたリクエストに対して 2 段階に分けたスケ内に可視化コンテンツ共有を実施する日付を検討すること

ジューリングを実行する手法を提案する．提案手法の概要が想定されるため，夜間などの勤務時間外にユーザグルー

を図 1 で示す．各段階のスケジューリングにおいては，可プがリクエストを出すことは少ない．こうした時間帯に，視化コンテンツ共有における多様なユーザグループの要求受理した全てのリクエストに対する整数計画法によるスケに対応への一歩として，様々な解像度を持つ可視化コンテ

ジューリングを長時間かけて実行する．算出された最適解

ンツ，ストリーミングによる可視化コンテンツの配信，マで得られる帯域幅とトポロジの割り当てが，暫定的予約よルチキャストな帯域幅の利用を想定する．

り帯域幅の利用率が低い場合，暫定的予約とその最適解かリクエストの受け付け時である 1 段階目では，ユーザグら得た帯域幅とトポロジの割り当てによるネットワークス

ループに対するリクエスト受理の成否を短い時間で返すたライス生成の予約を置き換える．時間内に最適解が得られめに，ヒューリスティック法によるスケジューリングを行なかった場合は，最適解の代わりに実行可能解を適用して，う．提案手法を実装するシステムは，複数のユーザグルー

予約を置き換える．帯域幅の利用率が高い場合，もしくは，

プからのリクエストを受け付ける．スケジューリングで必実行可能解もない場合は，暫定的な予約によるネットワー

要とするリクエストは，2 章で述べた既存研究におけるリクスライスの生成をそのまま指定の日時に行う．この段階

nnクエストと同様に r = (S , Ln, tns , tne , bn ) とする．シス

テムは，複数のユーザグループからのリクエストに対して受け付けたリクエストから順にヒューリスティック法を用は，リクエストの少ない時間帯が訪れるたびに行い，より低い帯域幅の利用率で予約を更新していく．
提案手法で用いられる整数計画法では，目的関数を式 1，

いたスケジューリングを実行する．スケジューリングに成制約式を式 2–9 とする整数計画問題を解く．式中の各変数

功した場合，すなわち，リクエストの要求に応じてネットの定義は，表 2 で示す．この整数計画問題は，2 章で述べワークスライスに割り当てる帯域幅とトポロジを確保できた既存研究で言及されている整数計画問題を修正し，マルた場合は，そのリクエストを受理する．受理したリクエス

チキャストな帯域幅の利用に対応した問題である．目的関トについて，リクエストの内容は記録して 2 段階目におけ数の最小化は，各リクエストが利用する物理リンクの本数る整数計画法で利用し，ネットワークスライス構成はネッを，リクエストの指定する帯域幅が大きいものを優先してトワークスライス生成の暫定的な予約に利用する．失敗最小化することを意味している．各制約式について説明すした場合は，リクエストで指定した日時とは他の，ネット

る．まず，式 2, 3 は un,e,k = min

∑

vin

∑

n,e,k
を表現
vjn pi,j

ワークスライス生成が可能な日時を，ユーザグループに対する big-M 法 [10] を活用した制約式である．式 4–8 は各して複数提示するリコメンドを実行する．リコメンドにお仮想リンクに物理リンクを割り当てるための制約式である．

いては，T n のみを別の日時に変更したリクエストの複製

仮想リンクの両端である 2 つのノード間をつなぐ経路上にに対してヒューリスティック法によるスケジューリングをある各ノードの特徴として，経路の両端に位置するノード

行う．リコメンドで探索する別の日時については，本研究のリンク次数は 1，それ以外のノードのリンク次数は 2 とでは簡易化のため，ユーザグループが指定した日付の前後なる．これらの式は，この特徴を定式化しており，仮想リ

2 日間とした．

ンクの両端のノードをつなぐ経路の存在を保証する．式 9

ヒューリスティック法よるスケジューリングは，2 章では，ネットワークスライスを利用する間，仮想リンクには述べた既存研究を基礎とし，マルチキャストな帯域幅の利

同じ物理リンクが割り当てられることを保証する制約式で用に対応する．本研究ではマルチキャストな帯域幅の利用ある．式 10 は，全てのリクエストに割り当てられた物理を想定するスケジューリングの実現を目的の 1 つとしてい

リンクの帯域幅の合計がリンク帯域幅を超えないことを保るため，ヒューリスティック法の基本的な部分は，実装の証するための制約式である．

ⓒ 2017 Information Processing Society of Japan4

Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report
ネットワーク ネットワーク
スライス A の スライス B の
⽣成を予約
⽣成を予約

表 2 各変数の定義
変数

説明

R

n n
rn = (S n , Ln , tn
s , te , b ) で表されるリクエスト集合

E

物理リンク集合C

リンク帯域幅M

big-M 法における十分に大きい定数

Tn

n
tn
≤ tn
s ≤ T
e で表されるネットワークスライスを利用

拠点

ユーザB 物理ネットワーク
リクエスト処理

リクエスト

リクエスト r n の仮想リンク (vin , vjn ) が時間 k に物理リ

可視化コンテンツ
共有先の拠点共有する⽇時minimize∑ ∑ ∑bn un,e,k(1)

r n ∈R e∈E kinT n∑

指定の⽇時にネットワークスライスを⽣成

図 2

ネットワークスライス自動構築システムの概要

ムは，ユーザグループにとって簡易的なリクエスト形式の提供を実現するリクエスト処理モジュール，最適なネット
ワークスライス構成を算出するスケジューリングモジュー∑

pn,e,k≤ M un,e,ki,jrn ∈ R, e ∈ E, k ∈ T n

vin ∈S n vjn ∈S n∑

ネットワークスライス構成

ネットワークスライス B

ネットワークスライス⾃動構築システム

リクエスト r n が時間 k に物理リンク e を利用するかどうかを示すバイナリフラグ (利用する場合 un,e,k = 1)

スケジューリングアロケーション

する場合 pn,e,k
= 1)
i,j

u

ネットワークスライス A

𝑟 " = (𝑆 " , 𝐿" , 𝑡 )" ,𝑡 *" , 𝑏 " )ンク e を利用するかどうかを示すバイナリフラグ (利用n,e,kネットワークスライス
A，B を⽣成可視化コンテンツ

ユーザA

する時間

pn,e,ki,j

1週間経過

ル，ネットワークスライス生成を実行するアロケーション
モジュールの 3 つのモジュールで構成される．まず，ユー(2)∑≥ un,e,kpn,e,ki,jr ∈ R, e ∈ E, k ∈ Tnnvin ∈S n vjn ∈S n

ザグループが本システムに対してリクエストを送信した場
合，リクエスト処理モジュールがそのリクエストを受け付ける．受け付けたリクエストは，スケジューリングモジュー∑=1pn,e,ki,jr ∈ R, k ∈ T
n

n

(3)

ルが要求するリクエスト形式に変換され，スケジューリン, vin ∈ S n ,グモジュールに渡される．スケジューリングモジュールは，

vin →e∑

提案手法の 1 段階目のスケジューリングを実行し，算出しvjn ∈ S n=0pn,e,ki,j(4)

rn ∈ R, k ∈ T n , vin ∈ S n ,からのリクエストが少ない時間帯に，提案手法の 2 段階目

vjn ∈ S n

イス構成を上書きする．リクエストでユーザグループが指

e→vin

∑

=1
pn,e,ki,j(5)rn ∈ R, k ∈ T n , vin ∈ S n ,

e→vjn

∑

vjn ∈ S npn,e,k=0i,j(6)

rn ∈ R, k ∈ T n , vin ∈ S n ,vjn →e∑ n,e,k ∑ n,e,kpi,j =
pi,je→v

r ∈ R, k ∈ T
n

(7)
n

, v ̸∈ vin , vjn ,vin ∈ S n , vjn ∈ S n (8)∑bn un,e,k ≤ Cのスケジューリングを実行し，記録したネットワークスラ
定した時間になった場合，アロケーションモジュールが記録したネットワークスライス構成を元にネットワークスラ
イスをネットワーク上に生成する．指定した時間が経過した場合は，生成したネットワークスライスをネットワーク
上から削除する．各モジュールの詳細については，以下で説明する．

vjn ∈ S nv→epn,e,k= pn,e,k+1
i,ji,j

たネットワークスライス構成を記録する．ユーザグループr ∈ R, e ∈ E, k ∈ T ,nnvin ∈ S n , vjn ∈ S n(9)e ∈ E, k ∈ T n(10)

r n ∈R

本システムでは，以下の項目を入力するためのユーザイ
ンタフェースを想定する．

• 共有する可視化コンテンツ• 共有先拠点• 共有する日時
リクエスト処理モジュールでは，上述した値より，以下の項目を抽出する．

• 共有拠点の仮想ノード集合• 共有拠点間の仮想リンク集合

4. ネットワークスライス自動構築システム• 共有する日時• 要求帯域幅

本研究では，提案したスケジューリング手法を組み込ん仮想ノード集合は，共有する可視化コンテンツと共有先のだネットワークスライス自動構築システムのプロトタイプ

拠点が位置するノードの集合とする．仮想リンク集合は，を実装した．本システムの概要を図 2 で示す．本システ共有する可視化コンテンツが位置するノードと共有先の拠ⓒ 2017 Information Processing Society of Japan5

Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report点が位置するノードをそれぞれつなぐリンクの集合とす
る．共有する日時は，ユーザグループが指定した日時をそのまま利用する．帯域幅は，各可視化コンテンツが必要とする帯域幅の合計とする．各可視化コンテンツが必要とする帯域幅については，本研究では簡易化のために既知のものとした．
スケジューリングモジュールでは，リクエスト処理モ
ジュールから受け取ったリクエストに対して，提案手法を実装したスケジューリングを実行する．スケジューリング
の内容は，3 章で述べた通りである．提案手法の 2 段階目で

図 3想定するネットワーク

計算する必要のある整数計画問題は，オープンソースウェ
アであり，利用の簡単な最適化問題ソルバーである GLPK

シミュレーション実験の想定について説明する．まず，(GNU Linear Programming Kit) [6] を用いて解く．整数

本システムは図 3 で示すネットワーク上でネットワークス

計画問題がリクエストの少ない時間帯だけで完了するとはライスを提供すると想定する．このネットワークは，学術限らないので，本システムではスケジューリングの計算時

ネットワーク SINET [11] を模式化した図であり，各物理間の上限を 6 時間と設定し，それを超えた時点の実行可能

リンクのリンク帯域は 10 Gbps とする．これにより，実環解をスケジューリングの結果とする．スケジューリングが境に近いシミュレーションが行える．ネットワーク上の各算出し，記録したネットワークスライス構成は，アロケー

ノードは，それぞれが可視化コンテンツを持つ研究拠点でションモジュールと共有する．

あると想定し，リクエスト内では全てのノードが可視化コ

アロケーションモジュールでは，スケジューリングモ

ンテンツと共有先の拠点として指定可能であるとする．各ジュールで算出したネットワークスライス構成を元にネッ拠点の持つ可視化コンテンツの解像度は，高解像度なもの

トワークスライスの生成を実行する．ネットワークスライ

ほどその数が少なくなるようにした上でランダムに設定す

ス生成の手法としては 1 章でも紹介した Flowvisor の他にる．ユーザグループがリクエスト内で指定する可視化コン

も，AutoSlice [3] や，OpenSlice [5]，AutoVFlow [9] など

テンツと共有先の拠点については，それぞれ指定する数を数多くの手法が存在する．本システムでは，ネットワーク

ランダムに決定したのち，指定する内容もランダムに決定

スライス生成手法の中でも，早期に開発され，単純な作りする．これらのランダムに条件を決定するものについては，で扱いが容易である Flowvisor を用いる．Flowvisor を利

様々な状況を想定するために各シミュレーションにつきそ用して，ネットワークスライス構成に指定される物理リン

れぞれ異なる条件を用意する．ただし，提案手法とヒュークが割り当てられたネットワークスライスを生成する．

リスティック法のみの手法を正しく比較するために，それ5. 評価

ぞれの手法を適用するシミュレーションで同じ条件を使用
したシミュレーションの結果同士のみを比較する．

本研究では，提案するスケジューリング手法に関して，シミュレーション実験の内容について説明する．シミュ

より多いユーザグループに対するネットワークスライス

レーションでは，シミュレーション内の数日の間だけリクの提供と，短い時間でのリクエスト受理の成否の伝達の 2

エストを受け付けるを行う．シミュレーション内の 1 日あつの指標を評価するために，提案手法を組み込んだネット

たりにユーザグループが送信するリクエストの数についてワークスライス自動構築システムのシミュレーション実験

は，ブロック率に影響を与えることが想定されるため，10，を行った．シミュレーションにおいては，2 つの指標を評

15，20，25，30 にそれぞれ値を変えてシミュレーションを価するために，スケジューリングにおいて帯域幅の不足な実施する．シミュレーション内の 1 日では，事前に決めたどによりネットワークスライス生成の予約ができなかった

1 日あたりに送信するリクエスト数だけ送られるリクエス

確率を指すブロック率と，ユーザグループがリクエストを

トを順に処理し，そのシミュレーションが提案手法を適用出してからその成否を受け取るまでの時間であるシステム

する場合は最後に整数計画法によるスケジューリングを行

応答時間を測定した．ブロック率に関しては，比較のためう．この処理の過程において，それぞれのリクエストを受に，提案手法を用いた場合と，1 段階目のヒューリスティッ

け付けてからスケジューリングが終了するまでの間をシス

ク法のみを用いた場合のそれぞれについてシミュレーショ

テム応答時間として測定する．また，各リクエストに対しン実験を行った．提案手法のブロック率がより低いというてスケジューリングが失敗し，かつ，リコメンドも失敗しことは，それだけ多くのリクエストを受け付けたというこた回数を測定する．リコメンドが成功し複数の日時が提示とであり，より多いユーザグループへのネットワークスラされた場合は，その中からランダムに 1 つ日時を選び，共イスの提供を達成したことを示す．

有する日時をその日時に変更したリクエストを受理したもⓒ 2017 Information Processing Society of Japan

6

Vol.2017-OS-140 No.11
2017/5/17

情報処理学会研究報告
IPSJ SIG Technical Report

0

3

5423

たものです．

6

[1]

.1

参考文献

[2]
[3]

1 
図 4



[4]

ブロック率の測定結果のとして扱う．

[5]

シミュレーション実験の結果について説明する．各シ
ミュレーションの試行回数は 10 回とした．システム応答時間の結果は，平均 25.3 ms となり，十分に短い時間と言え[6]

る．提案手法とヒューリスティック法のみの手法のブロック率については，図 4 の通りである．ブロック率は，スケ[7]

ジューリングに失敗した回数を送信された全リクエストの数で割ることで算出する．結果からは，1 日に送信するリクエスト数が増えるに従ってどちらの手法も増加している[8]

ことがわかる．この増加は，ネットワークスライスに割り当て可能なリンク帯域幅が有限なために発生する．また，結果からは，提案手法のブロック率がヒューリスティック[9]法のみの手法のブロック率を全体的に下回っていることがわかる．これは，提案手法で実行される整数計画法によってネットワークスライスに割り当てられる帯域幅やトポロジが最適化され，より多くのネットワークスライスが提供できたことを示す．

6. まとめ[10][11]Bai, H. et al.: Virtual Network Scheduling Design, Proceedings of 2014 IEEE 3rd International Conference on
Cloud Networking (CloudNet 2014), pp. 362–367 (2014).
Bai, H. et al.: Overlay Network Scheduling Design, Computer Communications, Vol. 82, pp. 28–38 (2016).
Bozakov, Z. and Papadimitriou, P.: AutoSlice: Automated and Scalable Slicing for Software-Defined Networks, Proceedings of the 2012 ACM Conference on
CoNEXT Student Workshop, pp. 3–4 (2012).
Gu, F., Xie, C., Peng, M., Çavdar, Ç., Khan, S. andGhani, N.: Virtual Overlay Network Scheduling, IEEE
Communications Letters, Vol. 15, No. 8, pp. 893–895(2011).
Liu, L., Muñoz, R., Casellas, R., Tsuritani, T., Martı́nez,
R. and Morita, I.: OpenSlice: an OpenFlow-Based Control Plane for Spectrum Sliced Elastic Optical Path Networks, Optics Express, Vol. 21, No. 4, p. 4194 (2013).
Makhorin, A.: GLPK - GNU Project - Free Software
Foundation (FSF), http://www.mext.go.jp/a_menu/
shinkou/sangaku/1380184.htm.
Renambot, L., Marrinan, T., Aurisano, J., Nishimoto,A., Mateevitsi, V., Bharadwaj, K., Long, L., Johnson,
A., Brown, M. and Leigh, J.: SAGE2: A Collaboration Portal For Scalable Resolution, Future Generation
Computer Systems, Vol. 54, pp. 296–305 (2016).
Sherwood, R., Gibb, G., Yap, K.-K., Appenzeller, G.,
Casado, M., McKeown, N. and Parulkar, G.: Flowvisor: A Network Virtualization Layer, OpenFlow Switch
Consortium, Technical Report, pp. 1–13 (2009).
Yamanaka, H., Kawai, E. and Shimojo, S.: AutoVFlow:
Virtualization of Large-scale Wide-area OpenFlow Networks, Computer Communications, Vol. 102, pp. 28–46(2016).
宮代隆平，松井知己：ここまで解ける整数計画，システム
制御情報: システム制御情報学会誌，pp. 363–368 (2006).
栗本崇，漆谷重雄：学術情報ネットワーク (SINET5)の概要 (ネットワークシステム)，電子情報通信学会技術研究報告， Vol. 116, No. 44, pp. 41–46 (2016).

本研究では，可視化コンテンツ共有を行うユーザからのリクエストに応じた，論理ネットワーク自動構築システムのプロトタイプを提案した．ネットワークはスケジューリ
ングによって生成され，スケジューリングにはヒューリス
ティック手法と整数計画法の二段階の組み合わせた実装を行った．提案手法の評価では，シミュレーション実験を実施し，システム応答時間とブロック率をそれぞれ測定した．
結果として，システム応答時間は平均 25.3 ms と十分短
い時間となり，ブロック率は提案手法がヒューリスティッ
ク法のみの手法を全体的に下回った．これは，より多くのユーザグループに対してネットワークスライスの提供が可能なことを示す．これらのことから，提案手法は，リクエ
スト受理の成否の伝達までの時間が短く，より多いユーザ
グループにネットワークスライスの提供が可能であると確認できた．
謝辞 本研究は JSPS 科研費 JP26540053 の助成を受けⓒ 2017 Information Processing Society of Japan

7