29
特集●ネットワーク技術

トンネリング技術を用いた汎用機器によるデータセンターマルチパスの実現
中村 遼 石原 知洋

関谷 勇司

江崎 浩

データセンター内における通信量は日々増加しており，ネットワークの可用性とスループットの向上が大きな課題となっている．そこで，データセンターネットワークにおけるマルチパスを用いた効率的なデータ配送手法について多くの研究が行われてきた．しかし，既存研究の多くは，ネットワークスイッチのハードウェアに対して変更を加える必要があり実環境への適用性に欠けるという問題がある．そこで本研究では，IP トンネル技術を用いた特定パスへのトラフィック配送手法を拡張することで，コストや障害時のスループットにおいて優位であるランダムグラフトポ
ロジのデータセンターネットワークを汎用機器のみを用いて構築する手法を提案する．本提案手法は，ネットワーク
スイッチには変更を加えず，サーバのネットワークスタックへの小さな変更のみで実現される．また，現在一般的に利用されている OSPF を用いた自動設定と障害復旧を行うシステムの設計と実装を行った．そして，シミュレータを用いた評価と実機を用いた実験を行い，提案手法がネットワーク全体の通信量の向上と高い可用性を汎用機器のみで実現可能であることを示した．

Improving availability and throughput is a significant challenge for data center networks. Recent studies haveattempted to use a variety of routing and multipathing techniques. However, no method has yet managed
to combine availability and throughput improvement with actual deployability, usually because of dedicatedhardware requirements. In addition, recent approaches lack availability for topology changes because of
requiring pre-configured topology. In this study, we propose a method to construct eﬃcient commoditybased random graph topology network by using an IP tunneling technique. The proposed method only
requires minimal modification for software network stack on end hosts. In addition, we designed and implemented a control plane system for proposed method using OSPF. Moreover, the evaluation shows thatour proposed method enables throughput improvement of a network and high availability with commodity
hardware switches.

ケーションの増加によって，データセンターにおけ1 はじめにる通信量は日々増加を続けている．Cisco Systems のクラウドコンピューティングに代表されるような，報告によると，世界のデータセンターにおける IP ト

データをネットワーク越しに保存し利用するアプリ

ラフィックは 2019 年に 2014 年の 3 倍に達すると予測されている [5]．そこで現在，一般的なデータセン

Multipathing in Commodity-based Data Center Networks with IP Tunneling.
Ryo Nakamura, Hiroshi Esaki, 東京大学情報理工学系
研究科, Graduate School of Information Science andTechnology, The University of Tokyo.
Tomohiro Ishihara, 東京大学総合文化研究科, Graduate School of Arts and Sciences, The University ofTokyo.
Yuji Sekiya, 東京大学情報基盤センター, Information
Technology Center, The University of Tokyo.
コンピュータソフトウェア, Vol.33, No.3 (2016), pp.29–43.
[研究論文] 2015 年 8 月 14 日受付.

ター内部のネットワークにおいて可用性とスループットの向上が大きな課題となっている．可用性とは，ある一定の期間内において，システムが要求通り動作できる状態にあると定義される．データセンターネット
ワークにおいては，障害の発生のしにくさや，障害発生時の修復速度が可用性に影響をおよぼす．そのためネットワークを構成する機器やリンクに障害が発生した際には，迅速に通信経路を復旧することが求められる．またコストの観点から，データセンターの仕様か30

コンピュータソフトウェア

らある通信容量を要求された際に，トポロジや経路制スイッチのみを用いて実現する手法を提案する．筆者

御の工夫によって可能な限り少ない機器数およびリン

らはこれまでに行った研究において，COTS スイッチ

ク数により同要求を満たすことが求められる．

のみを用いて構築した Fat-tree トポロジのレイヤー

こうしたデータセンターネットワークそのものに対3 データセンターネットワークで，IP トンネル技術

する課題に対して，様々な手法が提案されてきた．現を用いてトラフィックを効率的に分散する手法を提案

在，実際に運用されているデータセンターネットワー

した [18]．本研究では，この手法を拡張し，ランダム

クでは，Border Gateway Protocol(BGP) を用いた

グラフトポロジにおける k-shortest path の経路制御

レイヤー 3 の Clos トポロジを構築することで高い可と各パスへのトラフィックの分散を，COTS スイッチ用性を実現する方法 [3] [14] が用いられている．一方のみを用いたネットワーク上で実現する．その上で，上記のような Clos トポトジ以外にも，Fat-tree [2] や

OSPF を利用してパスの自動設定と復旧を行う機構

B-Cube [11]，HyperX [1] といったトポロジの利用がを設計し，実装した．以降，本論文ではまず 2 章で関提案されている．そして，これらのトポロジ上で効連研究を述べ，3 章で IP トンネル技術を用いたパス

率的にトラフィックを配送するための様々な手法が提選択手法について述べる．そして 4 章でランダムグ

案されている [4]．また Singla らは，様々なトポロジ

ラフトポロジとその実現手法について述べ，5 章で評の中でも，データセンターネットワークにランダム価実験を行う．最後に，6 章で結論と今後の課題につグラフトポロジを適用することを提案している [21]．

いて述べる．

Singla らは論文 [21] の中で，ランダムグラフトポロ
ジが Fat-tree に対してコストや障害時のスループッ

2 既存研究トの面で優位であるとしている．またランダムグラフ

データセンターネットワークの可用性とスループッ

トポロジでネットワーク全体のスループットを向上す

トの向上を目的とした多くの既存研究がある．しかしるため，k-shortest path [23] と Multipath TCP [7]

これらは，COTS スイッチを利用しながら，その両を利用している．

方を同時に実現できてはいない．既存研究を，想定す

このようにデータセンターネットワークの可用性とるトポロジ，利用できるパス，COTS スイッチを使

スループットを向上するために様々な手法が提案され用できるか，そして可用性という 4 つの項目についてきたが，実際のデータセンターネットワークに適用て比較した結果を表 1 に示す．可用性は，それらの手されるには至っていない．その原因として，構築コス法が，障害などのトポロジの変化に対して迅速に経路トが挙げられる [9]．ネットワークを構築するためのを修復することができるか，である．この表 1 をもコストを抑えるため，多くの場合，Commercial-Oﬀ-とに，可用性とスループットの向上，そして COTS

The-Shelf (COTS) スイッチと呼ばれる容易に入手可

スイッチの利用による実環境への適応性という観点か能な汎用ネットワーク機器の利用が前提とされる．し

ら既存研究の問題点を整理する．

かし既存の手法は，ネットワークを構成するスイッチ

データセンターネットワーク用に提案されるトポロのハードウェアに対して特殊な変更を必要とする．特ジの特徴は，あるスイッチ間に複数のパスが存在し，殊なハードウェアの利用はコストの増大を招くため，それらのパスにトラフィックを分散することによってこれらの技術を実環境に導入するための大きな障害

ネットワーク全体の転送量を増やすことである．ことなっている．一方 COTS スイッチを用いる手法でのとき，トラフィックを複数のパスに分散する最も一は高い可用性を実現できてはいない．つまり，COTS

般的な手法として，レイヤー 3 ネットワークにおけスイッチのみを用いて，可用性とスループットの向上

る Equal Cost Multipath (ECMP) がある．ECMPを同時に実現するには至っていない．

は，ある宛先への最短経路上に同一コストの複数の

そこで本研究では，Singla らの提案したランダムグ

リンクがあるとき，パケットのハッシュ値に基づい

ラフトポロジのデータセンターネットワークを COTSてトラフィックをそれらのリンクに分散する機能であVol. 33 No. 3 Aug. 2016
表1

31

SPAIN [17] にもとづく既存研究の比較

トポロジ

利用するパス

COTS スイッチを利用

可用性

Facebook [3]Multiple Tree

ECMP

YES

YES

TRILL [6]Arbitrary

ECMP

NO

YES

SEATTLE [13]ArbitrarySingle Path

NO

YES

PortLand [19]Fat-tree

ECMP

NO

NO

SPAIN [17]Arbitrary

Multiple Paths

YES

NO

VL2 [10]

Fat-tree

ECMP

YES

YES

Random Graphk-shortest path

NO

YES

Jellyfish [21]る．ECMP は既に多くのネットワーク機器においては，レイヤー 2 のデータリンク層に新たな識別子を導実装されており，VL2 [10] や Facebook [3] など，汎入し，ルーティングに利用する．しかし，こういった用機器を用いることを主眼に置いた手法で利用され機能は既存の COTS スイッチには無いため，スイッている．またデータセンターネットワークをレイヤー

チのハードウェアへの特別な変更を必要とする．ま3 で構築することで，高い可用性を得ることができた一方で，PortLand [19] はレイヤー 2 ネットワーク

る [10] [3] [14]．しかし ECMP には 2 つの問題があに特定のアドレッシングルールを適用し，そのルーる．ひとつは，パケットのハッシュ値に基づいてトラルに基づいて ECMP とは異なるマルチパスの利用を

フィックを分散するため特定のパスにトラフィックが行う．PortLand は，Al-Fares らによって提案された

偏ってしまう点．もうひとつは，最短経路で同一コスレイヤー 3 ネットワークのためアドレッシングルー

トのリンクしか利用できないためランダムグラフのル [2] をレイヤー 2 へと拡張したものである．このようなトポロジでは利用できるリンクが限られてしPortLand も SEATTLE などと同様スイッチのハー

まう点である [21]．

ドウェアに変更を必要とするため，COTS スイッチ

ECMP に対して，SPAIN [17] はマルチパスを利用を用いて構築することができない．

するために VLAN を用いる．VLAN は大抵の COTS

最後に，Singla らの提案する Jellyfish [21] では，スイッチで利用可能である．その上で，SPAIN は複データセンターネットワークとしてランダムグラフ

数のパスを指定できるように VLAN をセットアップ

トポロジを用いる．ランダムグラフトポロジは Fat-

するためのアルゴリズムを提案している．これによっtree トポロジに対して構築にかかるコストや障害時て，SPAIN は COTS スイッチの利用による実環境へのスループットの面で優位であるとしている．しかの適用性と，ECMP 以外のマルチパス利用手法によし，ランダムグラフトポロジにおいては，ある送信

る高いスループットを同時に実現している．しかし元から宛先まで同一コストで到達する経路が少ない

SPAIN では，トポロジの変更が起こった際に，まずため，ECMP ではトポロジ上の多くのリンクを利用

ネットワーク全体のトポロジを再検出し，各パスを指することができない．そこで Jellyfish では，宛先ご定するための VLAN のセットアップを再計算し，全とに k 番目まで短いパス，k-shortest path を利用すスイッチに再度設定を投入する必要がある．そのた

る．この k 本のパスに MPTCP を用いて各サブフ

め，SPAIN はレイヤー 3 の動的経路制御 [3] [10] を

ローを分散することで複数パスを利用する．しかし，行う手法に比べて可用性の面で不足がある．

k-shortestpath を実現する経路制御機構は COTS ス

また，可用性を実現するレイヤー 3 のホップバイ
ホップルーティングと動的経路制御のアーキテクチャ
をレイヤー 2 ネットワークに適用する手法として，TRILL [6] や SEATTLE [13] がある．これらの手法

イッチにはなく，ハードウェアに変更が必要なため実環境への適用性に欠ける．

32

コンピュータソフトウェア

3 IP トンネル技術を用いたパス決定手法
本研究では，Singla の提案するランダムグラフトポ
ロジのデータセンターネットワークを，COTS スイッ

Switch B	

Switch C	

Switch A	

Switch D	

Dst : Switch C
Src	
: X.X.X.X	
Dst : Server D
Src	
: Server S	
Payload	

Dst : Server D
Src	
: Server S	
Payload	

チのみを用いてレイヤー 3 で構築する手法を提案する．ランダムグラフトポロジにおいて k-shortestpath

Server S	

Server D	

と MPTCP を利用することでスループットの向上を，

COTS スイッチの利用によって実環境への適用性を，

図1

IP トンネル技術を用いたパス決定手法の概要

そしてレイヤー 3 で動的経路制御を使ってネットワー
クを構築することで可用性を実現する．このために，として，ソースルートオプションがある．IPv4 では

本章ではまず筆者らが先行研究 [18] で提案した，IP

Loose Source and Record Route Option，IPv6 では

トンネル技術を用いてトラフィックを選択的に決定しRouting Header として標準化されており，IP スタッ

たパスへ転送する手法について述べる．そして，4 章

クの一部であるため COTS スイッチも対応している．

にてランダムグラフへの拡張について述べる．また本

しかしながら，ソースルートオプションはセキュリ

論文では以後レイヤー 3 スイッチとしてスイッチといティ上の問題によって利用できない，また多くのスう言葉を用いる．

イッチにおいて CPU で処理されるためスループットが出ないなど，多くの問題がある．そのため，実環境

3. 1 概要

において，ソースルートオプションを中継点の指定にCOTS スイッチは ECMP 以外にトラフィックを複用いることは現実的ではない．

数パスへ分散する機能を持たない．そこで，本手法は，ソースルートオプションの代わりに，本手法ではパトラフィックを複数のパスに分散する機能を，ネット

ケットに中継点を明示するための識別子として，スワークを構成するスイッチから，ソフトウェアによるイッチのハードウェアでサポートされた IP トンネル

機能追加が容易なサーバへと移す．つまり，サーバの技術を用いる．本手法を適用したサーバは，パケット

ネットワークスタックに変更を加え，サーバが複数のを送信する際，IP でカプセル化を行う．そのとき，内パスへとトラフィックを分散することで，ネットワー

部 IP ヘッダの宛先は最終的な通信先サーバのアドレ

ク全体のスループットを向上させる．

ス，送信元は送信するサーバ自身のアドレスとする．

図 1 に，本手法の概要を示す．ある送信元サーバか

そして，カプセル化した外部 IP ヘッダの宛先は中継らある宛先サーバへのパスは，そのパスに対応するス

するスイッチのアドレス，送信元には全サーバで同イッチをパケットの中継点として明示することで指定

一の IP アドレスを用いる．図 1 は，サーバ S がサーできる．図 1 中，サーバ S からサーバ D への最短経

バ D に対してパケットを送信する際，外部 IP ヘッダ

路がスイッチ B を経由する場合，サーバ S はスイッの宛先としてスイッチ C のアドレスを用いることで，チ C を中継するようパケットに指定できれば，最短最短経路ではないパスへとパケットを通す様子を示し

経路以外のパスへとパケットを通すことができる．まている．スイッチ C がカプセル化されたパケットをた，パケットごとに中継点としてスイッチ B とスイッ

受信すると，外部 IP ヘッダとカプセル化ヘッダを取

チ C を指定すれば，両方のパスへとトラフィックをり外してサーバ D へと送信する．また複数のスイッ分散できる．このように，中継点を明示するためのチを中継させたい場合には，中継する順番に従ってパ

何らかの識別子をパケットに埋め込むことができれケットを複数回カプセル化することで任意のパスへとば，サーバがパケットを通すべきパスを指定し，トラパケットを転送する．

フィックを複数のパスに分散できる．
パケットに特定のスイッチを経由させるための手法

本手法はこのように IP トンネル技術を利用することで，COTS スイッチで構築されたレイヤー 3 ネッ

Vol. 33 No. 3 Aug. 201633

トワークにおける明示的なパスへのパケット転送を実を利用するため，ステートを管理するトンネリング

現する．IP トンネル技術は既に多くの COTS スイッ

プロトコルは本手法に用いることができない．しかチでサポートされており，ワイヤーレートでの転送もし，ステートを管理しないプロトコルとして，GRE可能である．例えば VL2 は，IP-in-IP トンネリング

や IPIP，VXLAN など，多くのプロトコルが利用可

を用い，汎用のスイッチチップである Broadcom の能である．このようにして，本手法ではトンネル数の56820 及び 56514 を使った実機の実験環境を作成し規模性を確保する．

ている．これらのチップは，ワイヤーレートのレイ
ヤー 2 及びレイヤー 3 パケット転送，そしてカプセ

3. 3 サーバネットーワクスタックへの変更

ル化とその解除の処理をサポートしている [10]．また

本手法は，トラフィックを複数のパスに分散する機

Microsoft はこの VL2 を Azure のストレージネット

能を，スイッチからサーバのネットワークスタックへ

ワークにデプロイしている [15]．このように，IP トと移す．本節では，本手法を実現するために必要なンネル技術を用いる本手法は，汎用機器を用いる実際

サーバへの変更について述べる．

のデータセンター環境で即座に利用可能である．

サーバのネットワークスタックへの変更は図 2 に示す 1 つのカーネルモジュール (iplb) によって実現

3. 2 IP トンネルの規模性される．iplb はカーネルスペースにロンゲストプレ

端点から端点へとパケットをカプセル化して運ぶトフィックスマッチに基づく経路表を保持する．この経ンネリング技術を，そのまま中継するスイッチの指定

路表には，宛先ネットワークごとに，その宛先ネットのために用いた場合，トンネルの数とその規模性がワークへと到達する複数のパスと，各パスを通すため問題になる．あるデータセンターネットワークにおいに中継しなければならないスイッチのリストを保持すて，全てのサーバが全てのパスを指定できるようにる．ユーザランドのアプリケーションがパケットを送するためには，全てのサーバと全てのスイッチの間で信すると，iplb はまずパケットの宛先アドレスが先

IP トンネルを構築する必要がある．しかし，一般的ほどの経路表にマッチするかを検証する．マッチしたな COTS スイッチで作成できるトンネル数は数十か場合，そのパケットを通すべきパスを決定し，パスにら数百程度であり，数千台規模のサーバやスイッチを通すために中継するスイッチを宛先とした IP ヘッダ

収容するデータセンターにおいては現実的でない．

を付与していく．このとき，1 つのパスに通すためにそこで本手法ではこのトンネル数の規模性の問題

複数のスイッチを経由する場合，各中継点を宛先としを回避するために，全サーバで同一のアドレスをトて複数回のカプセル化を行う．

ンネルの送信元アドレスとして用いる．図 1 中のある宛先ネットワーク宛のパケットを通すべきパ

X.X.X.X がこのアドレスを示す．本手法において，

スは，フローごとに決定する．フローは 5 タプル (宛パケットは常にサーバによってカプセル化され，ス
イッチによってカプセル化を解除される．つまり，ス
イッチがパケットをカプセル化してサーバへ送信す

UserlandApplications	
Kernel	

ることは無く，トンネル内のパケットの通信方向は
常に一方向のみである．よって，全てのサーバはカ

IP packet	

Match	
 iplb module	
Destination Prefix	

10.1.0.0/24	

プセル化した際の外側 IP ヘッダの送信元アドレスとして，同一の IP アドレスを用いることができる．同

Tun hdr +IP packet	

一の IP アドレスを外部ヘッダの送信元に用いること

10.1.24.0/24	

Relay switches	
path 1 : relay A	
path 2 : relay B	
path 1 : relay A, C	
path 2 : relay B, C	

で，各スイッチに必要なトンネルは，スイッチ自身
からその共通アドレス (X.X.X.X )，というただ 1 つとなる．また，X.X.X.X という存在しないアドレス

図2

サーバへの変更の概要

コンピュータソフトウェア

34

先アドレス，送信元アドレス，プロトコル番号，宛で各サーバ間の通信において k-shortest path アルゴ

先ポート番号，送信元ポート番号) によって識別されリズムで発見した k 本のパスにトラフィックを分散する．これは，同一フローを構成するパケットが別のパることで，ECMP では使えなかったリンクも利用すスを通った場合，パケットの到着順序に入れ替わりがることができる．

発生し，上位のトランスポート層において性能の低下が発生するのを防ぐためである．

k-shortest path アルゴリズムでネットワーク上の複数パスを見つけた上で，Jellyfish ではそれらのパスにトラフィックを分散するために Multipath TCP

4 ランダムグラフによるデータセンター
ネットワーク(MPTCP) [7] を用いる．MPTCP は，複数の TCP
セッションを束ねて 1 つの TCP セッションとして

本研究では，3 章で述べたトラフィックを特定パス扱うためのトランスポート層のプロトコルである．

に転送する手法を拡張し，ランダムグラフトポロジに

MPTCP は，1 つの MPTCP セッションを構成する

適用する．本章ではそのための MPTCP におけるサ

複数の TCP セッションが異なる IP インターフェー

ブフローの各パスへの割り当て手法，中継点の選択手

ス経由で異なる経路を通って確立されることを想定

法，そして OSPF を利用して自動で iplb の設定をするため，複数の TCP セッションをまとめて輻輳制行う機構について述べる．

御する機構 (Linked Increase アルゴリズム) を持つ．

Jellyfish では，この MPTCP を用いて 1 つの TCP
4. 1 ランダムグラフトポロジの利用法

セッションを複数のサブフローとし，各サブフロー

Jellyfish において，ランダムグラフは以下のようにを k-shortest path アルゴリズムで見つけた複数の定義される．ネットワークを構成するスイッチ i は ki

パスに分散する．各パスへのトラフィックの分散は本のポートを持つ．そして ri 本ポートを他のスイッ

MPTCP の輻輳制御機構によって管理され，ECMP

チとの接続に用い，残った ki − ri 本のポートを用いで発生する特定パスへのトラフィックの偏りを回避し，てサーバを収容する．スイッチ i が ri 本のポートをネットワーク全体のスループットを向上する．

用いて接続するスイッチは，一様な確率で他のスイッチから選択される．このようにして定義されるランダ

4. 2 iplb の適用手法

ムグラフを，データセンターネットワークのトポロジ

4. 1 節で述べたように，k-shortest path と MPTCPとして用いる．本論文では Jellyfish と同様に，全てを用いることでランダムグラフにおいて ECMP 以上のスイッチが同じ k 本のポートを持ち，r 本のポートのスループットを実現できる．しかし，Jellyfish のをスイッチ間の接続に用いるものとする．

論文中でも述べられているように，トラフィックを

k-shortest path とは，あるグラフにおいて，特定選択的に k-shortest path に分散して配送することの始点から特定の宛先へ到達するパスのうち，k 番目

は既存の COTS スイッチではできない．そこで本研までの短いパスのことである．これを見つけるために，

究では，サーバが MPTCP を構成するサブフローを

Yen によって提案された k-shortest loopless path ア

k-shortest path の各パスに通すために 3 章で述べたルゴリズム [23] をはじめ，計算量の異なるいくつか

iplb を用いることで，COTS スイッチによるランダのアルゴリズムがある．Yen のアルゴリズムによってムグラフトポロジのネットワークを実現する．

作られる k-shortest path は，始点から，宛先への最提案手法を k-shortest path と MPTCP に組み合

短経路を外れた点 (分岐点) までの最短経路と，そのわせて用いる際の概要を図 3 に示す．ユーザランド

分岐点から宛先までの最短経路をつなげたパスであのアプリケーションがある宛先にデータを送信する

る [23]．この分岐点を変更していくことで，k 本のパと，MPTCP がそのデータを複数の TCP セッション

スを作成する．2 章で述べたように，ECMP で利用に分散して送信する．iplb は，各 TCP サブフロー

できるパスは同一コストの最短経路に限られる．そこを事前に設定された k 本の各パスへとカプセル化をVol. 33 No. 3 Aug. 2016

35
8	

Userland	
  Applica/on	

11	

MPTCP	

Kernel	

TCP	

TCP	

TCP	

TCP	

ﬂow	

ﬂow	

ﬂow	

ﬂow	

iplb	

Path	
  1	

Path	
  2	

Path	
  3	

Path	
  4	

k-­‐shortest	
  path	  <	
  8,	
  11,	
  1,	
  9,	
  17	
  >	
  
<	
  8,	
  12,	  3,	  10,	
  17	
  >	
  
<	
  8,	
  11,	
  2,	
  9,	
  17	
  >	
<	
  8,	
  12,	  4,	  10,	
  17	
  >	
  
<	
  8,	
  11,	
  1,	
  5,	
  2,	
  9,	
  17	
  >	
  
<	
  8,	
  12,	
  3,	
  6,	
  4,	
  10,	  17	  >	

提案手法による MPTCP サブフローの各パスへの割り当て

1	

2	

4	

3	

5	

9	

10	

6	

2	

17	

9	

Random	  Graph	
  Network	

図3

12	

4	
10	

17	

図4

k 本のパスから各パスの中継点の探索 (k = 6)

用いて転送する．このとき，ある宛先ネットワーク宛てのパケットを通すべきパスは，フローごとに，ラウンドロビンで決定する．異なるパスを通る複数フ
ロー間の輻輳制御や，パケットの到着順が入れ変わった際の再構成などは MPTCP によって行われる．また，iplb はサーバの同一インターフェースから送信される複数のフローも異なるパスに通すことができる
ため，MPTCP を利用するためにひとつのサーバに複数のインターフェースを用意する必要は無い．このようにサーバの送信するパケットを k 本のパスへ分散して送信することで，Jellyfish で提案されたランダムグラフトポロジにおけるスループットの向上を，

COTS スイッチのみを用いて実現する．
をつくる様子を図 4 に示す．各パスを木構造に追加

4. 3 中継点の選択する際，同一のスイッチであっても異なるホップ数に

iplb におけるパスは，中継するスイッチのリスト出てきたスイッチは別のノードとして扱う．これは，で構成される．そのため，k-shortest path の特定パ木構造の中でループが発生するのを防ぐためである．

スへパケットを通すためには，そのパスにおいて中継

各パスを指定するには，この木構造において宛先にすべきスイッチを決定する必要がある．本節では，こ到るまでに分岐した箇所を中継点として指定していけの中継スイッチを決定する手法について述べる．

ばよい．そこで，Algorithm 1 に示す深さ優先探索をある送信元からある宛先への k-shortest path の各行う．始点から，自ノードの親のノードが 2 個以上のパスは，経路が途中で分岐することによって形成され子ノードを持つ場合，つまり自ノードが分岐した先のる．そこで，各パスを始点から比較していき，分岐しノードである場合は，自身を中継点のリストに追加すたすぐ先のスイッチを中継点として記録していくこる，という処理を行いながら探索する．例えば図 4 にとで，パスごとの中継点のリストを作成することがおいて，ノード 8，11，1 と辿った際，ノード 11 からできる．まず，k-shortest path で発見した k 本のパ

見て親となるノード 8 は 2 つの子ノードを持つ．そスから木構造をつくる．例として，k = 6 のとき，ス

こでノード 11 を中継点リストに追加する．次にノー

イッチ 8 からスイッチ 17 へと向かうパスから木構造

ド 1 もノード 11 が複数の子ノードを持つため自身を

36

コンピュータソフトウェア

中継点リストに追加する．こうして宛先であるノー

iplbd は，ユーザランドソフトウェアとして iplb

ド 17 まで辿り，⟨8, 11, 1, 5, 2, 9, 17⟩ のパスを通すたを用いる各サーバ上で動作する．この iplbd は 2 つめの中継点は ⟨11, 1, 5⟩ であると分かる．同様にして，のコンポーネントから構成される．1 つ目は OSPF プ⟨8, 11, 1, 9, 17⟩ のパスは ⟨11, 1, 9⟩，⟨8, 11, 2, 9, 17⟩ のロトコルを処理する部分である．これはサーバ自身をパスは ⟨11, 2⟩ となる．

収容するスイッチと OSPF の隣接関係を結び，LSA

このようにして，COTS スイッチで構築したデーを受け取ってトポロジ情報である LSDB を常に最新

タセンターネットワークにおいてサーバが明示的にパの状態に保つ．2 つ目は，カーネル内の iplb のパススを指定するための手法をランダムグラフトポロジに情報を更新する部分である．iplbd の起動時に LSDB

適用する．サーバが送信するトラフィックは MPTCPの構築が完了すると，このコンポーネントが LSDB

によって複数の TCP サブフローに分割され，各フの情報をもとに 4. 3 節で述べたアルゴリズムを用いローが提案手法を用いて k-shortest path の各パスへて各サーバへのパスと中継点を決定し，iplb に設定

分散して送信される．また各パスを指定するための中する．また新たな LSA を受信した場合，LSDB の更継スイッチは本節で述べた手法によって決定される．

新が完了すると，起動時と同様に再度パスの計算を行い，パス情報を更新する．このように各サーバ上で動4. 4 OSPF を用いた制御システム

作する iplbd が OSPF を用いてトポロジ情報の取得

実際のデータセンターネットワークでは，スイッチと障害時のパスの更新を行うことで，トポロジ変更にの追加や障害などによって頻繁にトポロジ変更が発生

対して迅速に対応し，可用性を実現する．

する．高可用性を実現するためには，こういったトポ
ロジの変更時に迅速にパスを復旧しなければならな

5 評価

い．そこで，自動でトポロジとその変更を検知し，各

本研究では，IP トンネル技術を用いた特定パスへサーバが各宛先へのパスを再計算して iplb の設定をのパケット転送手法を応用することで，Jellyfish で提更新する仕組みとして，iplbd を設計し，実装した．

案されたランダムグラフトポロジのデータセンター

トポロジとその変更の検知には，Open Shortest

ネットワークを COTS スイッチのみを用いて実現す

Path First (OSPF) [16] を用いる．OSPF は，現在る．また，OSPF を利用した制御機構によって，レ

最も広く利用されているルーティングプロトコルの 1

イヤー 3 ネットワークと同様の高い可用性を実現すつであり，多くの COTS スイッチにも実装されている．本論文ではこれらの評価として，1) 提案手法にる．OSPF に参加するノードは，Link State Adver-

よるスループットの向上度合い，2) カプセル化によtisement (LSA) というリンクの状態を記したパケッるオーバーヘッド，3) 障害時復旧に要する時間，の 3トをネットワーク内に伝搬する．この LSA をもとに，点について評価実験を行った．

全参加ノードが Link State Data Base (LSDB) とい
うそのネットワークの完全なトポロジ情報を共有す

5. 1 スループットの向上

る．また，リンクが切断した場合には新たに LSA を

本節では，ランダムグラフネットワークに iplb を伝搬し，トポロジの変更に追従して LSDB を更新す

適用することで，Jellyfish で示された通りにスルー

る．OSPF では各ノードが個別に宛先までの経路を計算するため，各ノードが持つ LSDB の内容，つまり

表2

実験トポロジサイズ

トポロジの情報は同一になることが保証されている．

スイッチのポート数

スイッチ数

サーバ数

提案手法では，データセンターネットワークのルー

4 ポート

20

16

ティングプロトコルとして OSPF を用い，その上で

6 ポート

45

54

iplbd がこの OSPF に参加することによってトポロ

8 ポート

80

128

ジ情報やその変更を検知し，パスの設定を更新する．

Vol. 33 No. 3 Aug. 2016
表3

37

シミュレーションパラメータ

パラメータ

値

リンク設定

タイプ:ポイントツーポイント，速度:10Mbps，MTU:9000 バイト

シミュレーション時間

開始 10 秒間がノード設定，その後 30 秒間テストトラフィックの送受信

テストトラフィック

TCP 1 フロー，MPTCP によって送信元ポートの異なる 8 サブフローに分割

MPTCP パスマネージャー

ndiﬀports (8 サブフロー)

TCP 輻輳制御機構

CUBIC (Linux デフォルト)

ネットワークスタック

liblinux [22] (Linux Kernel 3.14.33, MPTCP version 0.89)
表4

シミュレーション結果

k-shortest path (k)トポロジサイズ

ECMP

2

3

4

5

6

7

8

4 ポート

1.12

1.18

1.22

1.23

1.22

1.23

1.19

1.17

6 ポート

1.21

1.19

1.28

1.30

1.28

1.30

1.30

1.31

8 ポート

1.25

1.16

1.28

1.31

1.31

1.31

1.30

1.30

プットを向上できたかについて評価を行う．本手法にには同様に Linux カーネルを用い，基本的な IP ルー

よって，COTS スイッチで構築したネットワークにティングの設定と，GRE カプセル化を解く設定のみ

おいても，最短経路のみを用いた場合と ECMP を用を行った．また，全てのリンクの MTU は 9000 バイ

いた場合に対してより多くのリンクを利用してトラ

ト，リンク速度はシミュレーション時間の短縮のためフィックを転送できる．これを確認するため，シミュ

10Mbps とした．その他のシミュレーションパラメー

レータ上でランダムグラフネットワークを構築し，最タを表 3 に示す．また iplb の実装及び本シミュレー

短経路のみを用いた場合，ECMP を用いた場合，そして提案手法を用いた場合に転送できたトラフィック

ションコードを筆者らの Github レポジトリにて公開している †1 ．実験では，それぞれのトポロジにおい量を計測し，比較した．

て，各サーバがランダムに選択した宛先サーバに対実験環境として，ns-3 [20] とその拡張である ns-

して 8 つの TCP サブフローから成る MPTCP トラ

3 Direct Code Execution (ns-3-dce) [22] を用いた．

フィックを同時に送信し，各サーバが受信できたバイ

ns-3 はネットワークシミュレータであり，ns-3-dce

ト数の合計を計測した．

は，Linux カーネルをそのまま ns-3 上で実行するこ

各トポロジにおいて，テストトラフィックを送受信とができる拡張である．ns-3-dce を用いることで，実するサーバのペアをランダムに変更しながら 15 回実機用に実装した iplb のコードを変更を加えること験を行った結果の平均を表 4 に示す．表 4 の値は，最なくそのままシミュレーションに用いた．このシミュ短経路のみを用いた場合に各サーバが受信できたバ

レータ上で，表 2 に示すサイズの異なる 3 つのトポ

イト数の合計を 1 として正規化したものである．こロジを構築した．ポート数に対するスイッチの数との実験結果から，4 ポートの際は k = 3 から k = 6 ま

サーバの数は，3-level k-ary Fat-tree に準ずる [2]．

での k-shortest path を利用した場合，最短経路のみ

このシミュレータ上でネットワークに接続されたサーの場合に対して約 1.2 倍スループットが向上すること

バには，Linux カーネルモジュールとして実装したがわかった．k = 6 までなのは，各サーバから宛先ま

iplb を用いて他のサーバへの k-shortest path を通でのパスに対してネットワーク全体のリンクの数が少る中継点の設定を行った．カプセル化には，Generic

Routing Encapsulation (GRE) を用いた．スイッチ†1 https://github.com/upa/iplb

38コンピュータソフトウェア

ンダムグラフでは，k = 6 以上の k-shortest path を利用することで最短経路のみを用いた場合に対して1.3 倍ほどのスループットを実現できることがわかった．また全てのサイズにおいて，ECMP よりも高い
スループットを実現できた．

number of relay points

ないためである．そして 6 ポート以上のサイズのラ
7
6
5
4
3
2
1
0
4

k = 8 までの k-shortest path と MPTCP の併用によるスループットの向上は Jellyfish の論文中にお

図5

8

16
20
24
28
32
36
topology size (number of ports)

40

48

各トポロジサイズにおける中継点数

いて述べられている．本実験では，シミュレータ上のスイッチは一般的な IP ルーティングと GRE の機出する．トポロジのサイズは 5. 1 節での実験と同様

能のみを持つ．ここに iplb を実装した Linux カーネ

k-ary Fat-tree トポロジに従い，スイッチのポート数

ルをホストとして接続して利用することで，Jellyfish

によって決まる．スイッチのポート数を p とすると，で示された通り ECMP よりもスループットが向上すサーバ数は p3 /4，スイッチ数は p2 + p2 /4 となる．

ることを確認した．このことから，提案手法は Jelly-

図 5 に，トポロジサイズに対して，k = 8 の k-fish で提案されるランダムグラフトポロジにおけるshortest path の各パスを指定するために必要な中継

k-shortest path と MPTCP によるスループットの向点の数を示す．X 軸はトポロジサイズを，Y 軸は，そ上を，COTS スイッチのみを用いたデータセンターのサイズのランダムグラフトポロジで全サーバ間にネットワークで実現できるといえる．

設定したパスの中継点数の平均および最大最小値を示している．図 5 から，最も小さいサイズである 4

5. 2 カプセル化によるオーバーヘッド

ポートスイッチ (16 サーバ，20 スイッチ) の場合に，提案手法では k-shortest path の特定パスにトラ

平均 3 つ，最大 6 つと最も中継点が必要となっていフィックを転送するためにパケットをカプセル化する．

る．これは，8 本の k-shortest path を作成するためこの手法は，パスの中継点ごとにカプセル化ヘッダにはトポロジサイズが小さく，多くの迂回が必要なたが必要なため中継点の数が多いほどカプセル化の回めである．8 ポート以上のトポロジサイズでは，トポ数も増え，MTU サイズの減少による転送量の低下に

ロジサイズによらず 8 本のパスを作成するための中つながる．また，カーネルモジュールである iplb 内

継点数は，平均で 2 つ，最大で 4 つとなった．

での経路検索やカプセル化処理自体によってサーバ

カプセル化のフォーマットとして GRE を用いた場の送信性能が低下することが考えられる．そこでま合，1 回のカプセル化で GRE ヘッダと外側 IP ヘッず，k-shortest path を実現するために各パスで必要

ダの追加によって，パケットサイズが 24 バイト減少になる中継点の数を調べ，MTU サイズの減少によるする．つまり，1 つのパスを指定するために 2 つの中

スループットの低下率を検証した．その上で，iplb

継点が必要な場合，48 バイトのパケットサイズの減を用いた場合と用いない場合についてサーバの送信少が起こる．MTU サイズが 1500 バイトの場合，48性能を比較し，カーネルモジュールの処理による送信

バイトのパケットサイズの減少は，3.2%の性能低下

性能の低下について評価を行った．

となる．しかし，データセンターネットワークは 1

5. 2. 1 複数の中継点による MTU サイズの減少

つの管理者によって管理されるネットワークであり，

ランダムグラフトポロジにおいて必要な中継点のMTU が 9000 バイト以上のジャンボフレームを利用数を求めるため，簡単なシミュレータを実装した．シできる．MTU を 9000 バイトとした場合，48 バイト

ミュレータは，指定されたサイズのランダムグラフのカプセル化オーバーヘッドは，0.5%の性能低下にトポロジを Jellyfish にもとづいて生成し，各サーバ

しかならない．また図 5 から，8 ポート以上のトポロ

から他のサーバまでの k 本のパスとその中継点を算ジサイズで最も多く中継点を必要とするのは 4 つで

Vol. 33 No. 3 Aug. 201639

number of relay points

して Juniper Networks EX4200 を，10Gbps での計
65測時には CPU Intel Xeon CPU E5-2650 2.60GHz，

4

メモリ 32GB，NIC Intel X520 (82599ES) のサーバ

3と，スイッチとして Juniper Networks QFX5100 を210用いた．トラフィックの送信と計測には iperf を用い，
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
k (number of paths)

10 秒間 TCP のテストトラフィックを送信する試験を各組み合わせについて 20 回行った．

図6

16 ポートスイッチのトポロジにおける中継点数

iplb を用いる場合と用いない場合，そしてリンク速度を 1Gbps と 10Gbps で計測した結果を表 5 にあり，4 回のカプセル化でも低下率は 1%である．こ示す．表 5 中の低下率とは，iplb を用いた結果が用のことから，ジャムボフレームの利用可能なデータセいなかった結果に対してどの程度性能が低下したか

ンターネットワークにおいては，カプセル化によるパを示している．GRE による 1 度のカプセル化はパケットサイズの減少は問題にならないといえる．

ケットサイズを 24 バイト減少させる．これは，MTU

また，図 6 に 16 ポートスイッチ (1024 サーバ，320

9216 バイトでは 0.26%の性能低下となる．リンク速度スイッチ) のランダムグラフトポロジにおける，k-

1Gbps の際，iplb を用いない場合は 990Mbps に対

shortest path のパス数に対する中継点数の変化を示して用いた場合は 987Mbps であり，実測値では平均

す．図 5 同様，Y 軸はパス数 k に対して，全サーバ0.3%の性能低下であった．またリンク速度が 10Gbps

間に設定したパスのカプセル化回数の平均値と最大最の際は，iplb を用いない場合の 8929Mbps に対して小値を示している．図 6 から，パス数 k の増加に応8925Mbps と，平均 0.04%の性能低下となった．しかじて，必要な中継点の数も増えることがわかる．しかしこの性能低下は，実験の計測誤差の中に収まってし，その増加分は，k = 20 でも k = 8 に対して平均

いる．以上の結果から，両方のリンク速度において，および最大値が 1 回増える程度である．Jellyfish でiplb による性能低下は理論値の近くに収まっており，

示され，5. 1 節での追試の通り，ランダムグラフトポ

iplb 内での経路検索やカプセル化自体の処理は大きロジにおける MPTCP と k-shortest path の利用でなボトルネックではないといえる．

は，k = 8 でスループットを向上できることがわかっている．このことから，トポロジサイズに対するカプ

5. 3 トポロジ変更への追従性

セル化回数同様，k の数に対するカプセル化回数の増提案手法は，ランダムグラフネットワークの経路

加も問題にならないといえる．

制御プロトコルとして OSPF を用いる．各サーバ上

5. 2. 2 iplb によるオーバーヘッドで動作する iplbd は OSPF の LSDB の情報をもと

次に，サーバに iplb を適用した場合と適用しなかっにトポロジの把握と k-shortest path の計算を行う．

た場合について送信性能の計測を行った．実験では，

OSPF は堅牢性の高い経路制御プロトコルとして一2 台のサーバを用意し，その間に 1 台のレイヤー 3 ス

般に広く利用されており，大規模環境への適用のためイッチを挟んで接続し，一方のサーバからもう一方への最適化手法も多く提案されている [8]．また既存研とパケットを送信した．iplb を用いる場合には間の究のひとつである VL2 [10] も，データセンターネッ

レイヤー 3 スイッチがカプセル化を解除するよう設定

トワークの経路制御に OSPF を用いている．

した．リンク MTU は全て Juniper Networks の機器

OSPF によるレイヤー 3 ネットワークで iplb を用

における最大 MTU である 9216 バイト，カプセル化

いた際，経路変更時の k-shortest path の再計算時間のフォーマットには GRE を用い，1Gbps での計測時が問題となる．iplb において，k-shortest path は，には CPU Intel Xeon L3426 1.87GHz，メモリ 4GB，宛先となるサーバごとに設定される．しかし実際には

NIC Intel e1000 (82574L) のサーバと，スイッチとひとつのスイッチの下に複数のサーバが収容されるたコンピュータソフトウェア

40
表5

iplb によるサーバ送信性能の低下

リンク速度

iplb 無し

標準偏差

1Gbps

989.6Mbps

0.10Mbps

10Gbps

8929Mbps

38.5Mbps

iplb 有り

標準偏差低下率

987Mbps

1.38Mbps

0.30%

8925Mbps

104.1Mbps

0.04%

バから各スイッチまでの k-shortest path の計算に要1した時間を累積密度分布に並べたものを示す．図 7

CDF

0.8
0.6

0.2
0

から，トポロジサイズが 24 ポートスイッチの場合まtopology size 8
topology size 16
topology size 24
topology size 32
topology size 40
topology size 48

0.4

0

0.02

図7

0.04

0.06
0.08
process time (sec)

0.1

0.12

で，ひとつの宛先への k-shortest path を計算する時間は，9 割までが約 0.01 秒ほどであることがわかる．
0.14

k-shortest path の計算時間

16 ポートスイッチの場合，サーバ数は 1024 台，ス
イッチ数は 320 台のため，約 3.2 秒で全スイッチへの

k-shortest path の計算が完了する．24 ポートスイッ
チの場合，サーバ数は 3456 台，スイッチ数は 720 台

め，各サーバは他のサーバを収容する各スイッチまでのため，全スイッチへの 8 本のパスを計算するのにの k-shortest path を求めるだけでよい．Yen のアル

要する時間は約 7.2 秒となる．32 ポート以上のトポ

ゴリズムを用いて k 本の shortest path を求める計算

ロジサイズでは，9 割が 0.02 秒以内に完了するもの

量は，O(kn(e + nlogn))，e はリンク数，n はスイッの，スイッチ数が 1620 台のため，全スイッチまでのチ数，である．トポロジ変更が発生した際，各サー計算には約 32.4 秒要する．そのため，現在の実装でバはこの計算をスイッチごとに行う必要がある．こ全スイッチへの k-shortest path を再計算する場合にの計算が現実的な時間で完了するかを確認するため，は，16 ポートスイッチまでが現実的な時間に計算がiplbd が k-shortest path を計算するのに要する時間

終わるサイズであることがわかった．

について評価を行った．その上で，実機を用いた実験

今後の課題として，k-shortest path の計算時間を環境を構築し，小規模な環境で iplbd が実際に動作より短くするために，より高速なアルゴリズムと実装することを確認した．

を用いる必要がある．ループの無い k-shortest path

iplbd の計算時間に関する実験では，実際に数千を求めるアルゴリズムとして，Yen のアルゴリズムよ

台規模のネットワークを用意することは難しいため，りも計算量の少ないアルゴリズムが Hershberger らに

Python で実装した iplbd に事前に作成したランダム

よって提案されている [12]．また本実装では Python

グラフのトポロジ情報を与え，k-shortest path の計を用いたが，C 言語などを用いてより最適化した実算にかかる時間を計測した．実験には，CPU が Intel

装を行うことで計算時間を短縮できる可能性がある．

i7-3770K 3.50GHz，32GB メモリのマシンを用い，次に，実機を用いて実際に iplbd によってパスを処理系には PyPy 2.0.2 (Python 2.7.3) を用いた．実

再計算し，通信を復旧することができるか実験を行っ験では，iplbd に異なるサイズのトポロジ情報を与た．本実験のトポロジを図 8 に示す．2 台のサーバ

え，ひとつのサーバから他のサーバを収容する各スを用意し，その間に 2 本のパスができるように 4 台

イッチまでの 8 本の shortest path を計算するのにかのスイッチを接続した．その上で，全てのスイッチ

かる時間を計測した．また各サイズにおいて，トポロ

で OSPF を動作させ，サーバでは iplbd を動作させジをランダムに変更しながら 10 回実験を行った．こた．実験では，iplbd による最初のパス設定が終わっのトポロジのサイズはこれまでの実験と同様 3-level

た後，サーバ S からサーバ D へ iperf を用いて TCP

k-ary Fat-tree トポロジのサイズに従う．

トラフィックを流しつづけた．iperf の生成したトラ

図 7 に，各トポロジサイズにおいて，ひとつのサーフィックは MPTCP によって 8 本のサブフローに分Vol. 33 No. 3 Aug. 2016

した制御機構によって，実機環境においてレイヤー 3

Switch	Server S	

Switch	

ネットワークの可用性を活かした障害の復旧が可能でSwitch	Server D	

Switch	

図841あることがわかった．

6 結論と今後の課題
本研究では，IP トンネル技術を用いて，ランダム

復旧時間の実験トポロジ

Throughput (in Mbps)

グラフトポロジのレイヤー 3 データセンターネット
ワークを COTS スイッチのみを用いて構築する手法
1200
1000
800
600
400
200
0

を提案した．また，OSPF を用いた制御システムの設計と実装を行った．そして，シミュレータを用いた評価を行い，Jellyfish で提案されたランダムグラフ
30

35

40

45

50

55

60

65

70

Time (sec)

図9

リンク断発生時の受信トラフィック量の推移

トポロジにおける k-shortest path と MPTCP を用
いたスループットの向上を，COTS スイッチの持つ機能のみを用いて実現できることを示した．さらにランダムグラフトポロジにおけるカプセル化回数に関割され，各パスへと分散されてサーバ D へと送信さする評価と実機を用いた実験を行い，カプセル化やれた．そして図 8 に示す下側スイッチの持つ 2 本のサーバへの変更が性能低下の大きな要因とはならな

リンクを切断し，中継点のひとつであるこのスイッ

いこと，また OSPF を用いた制御機構によりトポロ

チをネットワークから取り除いた．このとき，OSPF

ジ変更時に自動的な復旧が可能であることを示した．

と iplbd によってパスの復旧が完了するまでサーバ

今後の課題として，他のトポロジへの適用がある．

D で受信できたトラフィック量を計測した．本実験の事前研究において提案手法を Fat-tree トポロジに適結果を図 9 に示す．図 9 の X 軸はトラフィックを送用し，本論文ではランダムグラフトポロジへの適用と信し始めてからの時間，Y 軸はサーバ D で受信でき復旧の自動化を行った．しかし，他にもデータセンタ

たトラフィック量を示している．このトラフィック量

ネットワークのために多くのトポロジが提案されていは，iperf サーバ (受信側) において 0.5 秒の頻度で取る [1] [11]．今後，これらのトポロジへも適用可能な得したものである．

形に提案手法を拡張していく予定である．

図 9 から，48 秒の時点で上記のリンクを切断し，49 秒に受信トラフィック量が 600Mbps 以下に，そし

参 考 文 献て 49.5 秒には約 900Mbps に戻ったことがわかる．こ[ 1 ] Ahn, J. H., Binkert, N., Davis, A., McLaren, M.
and Schreiber, R. S.: HyperX: Topology, Routing,and Packaging of Eﬃcient Large-scale Networks, inProceedings of the Conference on High Performance
Computing Networking, Storage and Analysis, SC’09, ACM, 2009.
[ 2 ] Al-Fares, M., Loukissas, A. and Vahdat, A.:
A Scalable, Commodity Data Center Network Architecture, in Proceedings of the ACM SIGCOMM
2008 Conference on Data Communication, SIGCOMM ’08, ACM, 2008.
[ 3 ] Andreyev, A.: Introducing data center fabric,
the next-generation Facebook data center network,https://code.facebook.com/posts/360346274145943/introducing-data-center-fabric-the-next-generation-facebook-data-center-network/, November 2014.
Facebook, Inc.

れは，リンクが切断された瞬間，物理層のリンク断を検知した OSPF が新しい LSA を送信し，それを受信した iplbd がパスの再計算を行い，障害が発生した
パスを iplb から削除したためである．パスが削除されるまでの間，上側スイッチを経由するパスを通るサ
ブフローによって通信が行われていた．iplbd によって不通となったパスの削除が行われた後，該当パスが無くなったサブフローは別のパスへと再割り当てされる．そして残った 1 本のパスを経由して全てのサ
ブフローが送信され，TCP が切断されることなく復旧された．このことから，提案手法は OSPF を利用42

コンピュータソフトウェア[ 4 ] Bari, M., Boutaba, R., Esteves, R., Granville, L.,
Podlesny, M., Rabbani, M., Zhang, Q. and Zhani,
M.: Data Center Network Virtualization: A Survey, Communications Surveys & Tutorials, IEEE,
Vol. 15, No. 2(2013), pp. 909–928.
[ 5 ] Cisco Systems, Inc: Cisco Global Cloud Index :Forecast and Methodology, 20142019, http://www.
cisco.com/c/en/us/solutions/collateral/serviceprovider/global-cloud-index-gci/Cloud Index
White Paper.html.
[ 6 ] Eastlake 3rd, D., Senevirathne, T., Ghanwani,A., Dutt, D. and Banerjee, A.: Transparent Interconnection of Lots of Links (TRILL) Use of IS-IS,
RFC 7176, IETF, May 2014.
[ 7 ] Ford, A., Raiciu, C., Handley, M. and Bonaventure, O.: TCP Extensions for Multipath Operation
with Multiple Addresses, RFC 6824, IETF, January
2013.
[ 8 ] Goyal, M., Soperi, M., Baccelli, E., Choudhury, G., Shaikh, A., Hosseini, H. and Trivedi, K.:
Improving Convergence Speed and Scalability in
OSPF: A Survey, Communications Surveys & Tutorials, IEEE, Vol. 14, No. 2(2012), pp. 443–463.
[ 9 ] Greenberg, A., Hamilton, J., Maltz, D. A. andPatel, P.: The Cost of a Cloud: Research Problems in Data Center Networks, SIGCOMM Comput. Commun. Rev., Vol. 39, No. 1(2008), pp. 68–73.
[10] Greenberg, A., Hamilton, J. R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D. A., Patel,
P. and Sengupta, S.: VL2: A Scalable and Flexible
Data Center Network, in Proceedings of the ACM
SIGCOMM 2009 Conference on Data Communication, SIGCOMM ’09, ACM, 2009.
[11] Guo, C., Lu, G., Li, D., Wu, H., Zhang, X.,
Shi, Y., Tian, C., Zhang, Y. and Lu, S.: BCube:A High Performance, Server-centric Network Architecture for Modular Data Centers, in Proceedingsof the ACM SIGCOMM 2009 Conference on Data
Communication, SIGCOMM ’09, ACM, 2009.
[12] Hershberger, J., Maxel, M. and Suri, S.: Finding the K Shortest Simple Paths: A New Algorithm
and Its Implementation, ACM Trans. Algorithms,
Vol. 3, No. 4(2007), Article 45.
[13] Kim, C., Caesar, M. and Rexford, J.: Floodless in Seattle: A Scalable Ethernet Architecture forLarge Enterprises, in Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication,
SIGCOMM ’08, ACM, 2008.
[14] Lapukhov, P.: Building Scalable Data Centers:
BGP is the Better IGP, https://www.nanog.org/
meetings/nanog55/presentations/Monday/
Lapukhov.pdf, June 2010. NANOG 55.
[15] Microsoft: Windows Azure’s Flat Network Storage to Enable Higher Scalability Targets, http://
blogs.msdn.com/b/hanuk/archive/2012/11/04/
windows-azure-s-flat-network-storage-to-enable-higher-scalability-targets.aspx.
[16] Moy, J.: OSPF Version 2, RFC 2328, IETF,

April 1998.
[17] Mudigonda, J., Yalagandula, P., Al-Fares, M.
and Mogul, J. C.: SPAIN: COTS Data-center Ethernet for Multipathing over Arbitrary Topologies,
in Proceedings of the 7th USENIX Conference on
Networked Systems Design and Implementation,
NSDI’10, USENIX Association, 2010.
[18] Nakamura, R., Sekiya, Y. and Esaki, H.: Layer3 Multipathing in Commodity-based Data Center Networks, in Global Internet Symposium 2015,
IEEE, GI’15, 2015.
[19] Niranjan Mysore, R., Pamboris, A., Farrington,N., Huang, N., Miri, P., Radhakrishnan, S., Subramanya, V. and Vahdat, A.: PortLand: A Scalable
Fault-tolerant Layer 2 Data Center Network Fabric,in Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, SIGCOMM ’09,
ACM, 2009.
[20] ns-3 project: http://www.nsnam.org/.
[21] Singla, A., Hong, C.-Y., Popa, L. and Godfrey,
P. B.: Jellyfish: Networking Data Centers Randomly, in Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, NSDI’12, USENIX Association, 2012.
[22] Tazaki, H., Uarbani, F., Mancini, E., Lacage,
M., Camara, D., Turletti, T. and Dabbous, W.:
Direct Code Execution: Revisiting Library OS Architecture for Reproducible Network Experiments,
in Proceedings of the Ninth ACM Conference on
Emerging Networking Experiments and Technologies, CoNEXT ’13, ACM, 2013.
[23] Yen., J.: Finding the k shortest loopless paths
in a network, in Management Science, 1971, 1971.

中 村 遼

2012 年慶應義塾大学環境情報学部卒
業，2014 年東京大学情報理工学系研
究科修士課程了，2014 年同後期博士課程入学．オーバーレイネットワー
クとルーティングの研究に従事．
石原知洋

2001 年日本大学理工学部物理学科卒，2003 年慶應義塾大学政策・メディア研究科修士課程卒業．2009 年慶応
義塾大学政策・メディア研究科後期博士課程修了，2010 年博士 (政策・メディア)．2009 年
より東京大学総合文化研究科特任助教に就任．2015
年より同助教．ドメインネームシステムおよびインVol. 33 No. 3 Aug. 2016
ターネットの運用技術に関する研究・開発に従事．
関谷勇司

1997 年 京 都 大 学 総 合 人 間 学 部 卒 ．
2005 年 慶 應 義 塾 大 学 政 策・メ ディ
ア研究科後期博士課程修了．博士 (政策・メディア)．2002 年より東京大学
情報基盤センター助手．2011 年同センター准教授．ク
ラウドを構成する要素技術と SDN，NFV，サイバーセキュリティに関する研究に従事．

43
江 崎 浩

1987 年九州大学大学院・工・電子修士課程了．同年 (株) 東芝入社．1990
年米国ニュージャージ州ベルコア社．

1994 年コロンビア大学・客員研究員．
1998 年東京大学大型計算機センター・助教授．2001
年同大学大学院・情報理工学系研究科・助教授．2005
年同大学大学院・同研究科・教授，現在に至る．博士(工学，東京大学)．MPLS-JAPAN 代表，IPv6 普及・高度化推進協議会専務理事，WIDE プロジェクト代表，JPNIC 副理事長．