トンネリング技術を用いた汎用機器によるデータセンターマルチパスの実現 Multipathing in Commodity-based Data Center Networks with IP Tunneling 中 村 遼†1 関 谷 勇 司 †3 石 原 知 洋 †2 江 崎 浩†1 データセンター内における通信量は日々増加しており，ネットワークの可用性とスループットの向 上が大きな課題となっている．そのため，データセンターネットワークにおける効率的なデータ配送 手法について多くの研究が行われてきた．しかし，既存研究の多くは，ネットワークスイッチのハード ウェアに対して変更を加える必要があり実環境への適用性に欠ける，事前に設計したルールに基づい てネットワークを構成するため，トポロジ変更への追従性に欠けるといった問題がある．そこで本研 究では，汎用機器のみを用いて構築するレイヤー 3 のデータセンターネットワークにおいて，IP トン ネル技術を用いた効率的なマルチパスの利用手法を提案する．本提案手法は，サーバのネットワーク スタックへの小さな変更のみで実現される．本論文では，提案手法をランダムグラフトポロジのネッ トワークに適用した場合について評価を行い，最短経路を用いる場合に対して 1.2 倍から 1.3 倍，ま た Equal Cost Multipath よりもスループットを向上できることがわかった． 1. 背 景 クラウドコンピューティングに代表されるような， このような課題に対して，学術と実運用双方から多 くの提案が行われている．その中でまず，可用性を向 上するための手法として，データセンターネットワー データをネットワーク越しに保存，利用するアプリケー クを IP によるレイヤー 3 ネットワークで構築する手 ションの増加によって，データセンター内の通信量は 法がある．IP ネットワークにおけるホップバイホップ 増加を続けている．そのため，データーセンターネッ ルーティングと動的経路制御技術は，データセンター トワークにおける可用性とスループットの向上が大き ネットワークにおいても高い可用性を実現する．障害 な課題となっている．データセンターネットワークに などによってトポロジ変更が起きた際，ネットワーク おける可用性とは，トポロジ変更に対する追従性であ を構成する各スイッチは自律的にその変更を検知し， る．日々運用されるネットワークでは，障害による経 経路の再計算を行ってネットワークを修復する．この 路の切り替わりや，段階的な機器の投入によるネット トポロジ変更に対するレイヤー 3 ネットワークの可用 ワークの増強などが発生する．データセンターネット 性の高さは，インターネットを構成する技術として広 ワークは，こういったトポロジの変更に柔軟に追従で く利用されてきたことからも示されている．そのため きなければならない．高い可用性の実現に加えて，ス データセンターネットワークをレイヤー 3 で構築する ループットの向上も必要である．増え続ける通信量に 試みは，実環境においても行われ始めている1),2) ． 対して，ネットワーク全体の転送量を増やすために単 一方，スループットを向上するための手法として， 純に設備を追加していくのは，運用とコストの観点か マルチパスの利用がある．まず，任意のサーバ間に複 ら現実的ではない．そのため，同一の機器，構成でも， 数のパスを構成するトポロジとして，Fat-tree や B- なるべくネットワーク全体の転送量を大きくすること Cube3) ，ランダムグラフ4) などがある．そして，こ が求められる． れらのトポロジ上でトラフィックを複数のパスに分散 するための様々な手法が提案されている5) ．これらを †1 東京大学情 情報理工学系研究科 University of Tokyo, Graduate School of Information Science and Technology †2 東京大学 総合文化研究科 University of Tokyo, Graduate School of Arts and Sciences †3 東京大学 情報基盤センター University of Tokyo, Information Technology Center 用い，サーバが送信するトラフィックを複数のパスに 分散することで利用するリンクを増やし，ネットワー ク全体のスループットを向上する．複数のパスを利用 するための一般的な手法として，Equal Cost Multi- path (ECMP) が広く用いられている．ECMP 対応 のスイッチは，ある宛先に対して同一コストの転送先 が複数存在する場合，パケットの 5 タプルなどのハッ を使用できるか，トポロジ変更への追従性，という 4 シュ値をもとに転送先を分散する．ECMP 以外の手 つの項目について比較した結果を表 1 に示す．これは， 法としては，スイッチのハードウェアに特殊な変更を 既存研究である SPAIN12) における比較を整理し，ト 加えるものが，レイヤー 3 とレイヤー 2 ネットワーク ポロジ変更への追従性を追加したものである． の双方について提案されている6),7) ． このように多くの可用性とスループットの向上手法 1 章で述べたように，レイヤー 3 の IP ネットワー クは，ホップバイホップルーティングと動的経路制御 が提案されてきたが，実際のデータセンターネット によって，トポロジ変更への高い追従性を実現する． ワークに適用されるには至っていない．その原因とし VL213) はデータセンターネットワークをレイヤー 3 て，構築と運用のためのコストが挙げられる8) ．ネッ ネットワークで構築することで可用性を実現すると同 トワークを構築するためのコストを抑えるため，多く 時に，COTS スイッチの利用によって実ネットワー の場合，Commodity-Off-The-Shel (COTS) スイッチ クへの適用性を確保している．また，Facebook では， と呼ばれる容易に入手可能な汎用ネットワーク機器の COTS スイッチを用いて BGP によるレイヤー 3 の 利用が前提とされる．しかし，可用性を実現する手 データセンターネットワークを構築している2) ．しか 法9),10) ，スループットの向上手法6),7) ともに，ネット し，これらはスループットの向上のために ECMP を ワークを構成するスイッチのハードウェアに対して特 利用する．通常の ECMP はトラフィックをパケット 殊な変更を要求する．特殊なハードウェアの利用は， のハッシュ値に基づいて分散するため，特定のパスに コストの増大を招くため，これらの技術を実環境に導 トラフィックが偏る可能性がある．そのため，ECMP 入するための大きな障害となっている．また，COTS では効率的に複数のパスを利用することができない6) . スイッチで実現可能なマルチパス手法である ECMP ECMP に対して，SPAIN12) はマルチパスを利用す は，パケットを振り分ける際にパケットのハッシュ値 るために VLAN を用いる．VLAN は大抵の COTS のみを考慮するため，特定のパスにトラフィックが偏 スイッチで利用可能である．その上で，SPAIN は複 るといった問題がある6) ．このように既存手法では， 数のパスを指定できるように VLAN をセットアップ 汎用ネットワーク機器のみを用いて，可用性とスルー するためのアルゴリズムを提案している．これによっ プットの向上を同時に実現するには至っていない． て，SPAIN は COTS スイッチの利用による実環境 そこで本研究では，特殊な変更の無い COTS スイッ への適用性と，ECMP 以外のマルチパス利用手法に チのみを用いて構築したレイヤー 3 のデーターセン よる高いスループットを同時に実現している．しかし ターネットワークにおいて，効率的にマルチパスを利 SPAIN では，トポロジの変更が起こった際に，まず 用するための手法を提案する．レイヤー 3 でネット ネットワーク全体のトポロジを再検出し，各パスを指 ワークを構築することで可用性を実現し，マルチパス 定するための VLAN のセットアップを再計算し，全 の利用によってスループットの向上を実現する．提案 スイッチに再度設定を投入する必要がある．そのため， 手法では，トラフィックを複数のパスに分散する手法 SPAIN はレイヤー 3 の動的経路制御を行う手法に対 として，COTS スイッチがサポートしているトンネリ して可用性の面で不足がある． ング技術を用いる．これまでに行った研究において， 可用性を実現するレイヤー 3 のホップバイホップ 提案手法を Fat-tree トポロジに適用した場合にスルー ルーティングと動的経路制御のアーキテクチャをレイ プットを向上できることが分かっている11) ．そこで本 ヤー 2 ネットワークに適用する手法として，TRILL9) 論文では，データセンタートポロジの 1 つとして提案 や SEATTLE10) がある．これらの手法は，レイヤー 2 4) されているランダムグラフ に提案手法を適用する． のデータリンク層に新しくルーティングのための識別 そして，シミュレータを用いた評価実験を行い，提案 子を導入し，その識別子に基づいたルーティングを行 手法を用いた場合，最短経路のみを利用した場合に対 う．しかしこれらの機能は既存の COTS スイッチには して 1.2 倍から 1.3 倍，また ECMP よりもスループッ 無いため，スイッチのハードウェアに対して特別な変 トを向上できることが分かった． 更を必要とする．また一方で，PortLand7) はレイヤー 2. 既 存 研 究 2 ネットワークにおいて，特定のアドレッシングルー ルを適用し，そのルールに基づいて ECMP とは異な データセンターネットワークの可用性とスループッ るマルチパスの利用を行う．PortLand は，Al-Fares トの向上について，多くの既存研究がある．これらを， らによって提案されたレイヤー 3 ネットワークのため 想定するトポロジ，利用できるパス，COTS スイッチ アドレッシングルール6) をレイヤー 2 へと拡張した 表1 SPAIN12) にもとづく既存研究の比較 トポロジ 利用するパス COTS スイッチを利用 トポロジ変更への追従性 Multiple Tree ECMP YES YES TRILL9) Arbitrary ECMP NO YES SEATTLE10) Arbitrary Single Path NO YES Fat-tree ECMP NO NO Arbitrary Multiple Paths YES NO Fat-tree ECMP YES YES Facebook2) PortLand7) SPAIN12) VL213) ものである．この PortLand も，スループットを上げ るために，SEATLE などと同様，スイッチのハード Dst : Switch C Src: X.X.X.X ウェアに変更を必要とする． Dst : Server D Src: Server S このように既存研究では，ハードウェアへの変更を Payload Switch B Switch C Switch A Switch D Payload 行わないまま，可用性とスループットの向上を同時 に実現することはできていない．そこで本研究では， COTS スイッチで構築されるレイヤー 3 データセン ターネットワークにおいて，ECMP とは異なるマル Dst : Server D Src: Server S Server S Server D 図 1 提案手法の概要 チパスの利用手法を提案する．本手法は，COTS ス イッチのみを用いることで実環境への適用性を維持し ように，中継点を明示するための何らかの識別子をパ たまま，レイヤー 3 ネットワークによる高い可用性と， ケットに埋め込むことができれば，サーバがパケット ECMP とは異なるマルチパス手法によるスループッ を通すべきパスを指定し，トラフィックを複数のパス トの向上を実現する． に分散できるようになる． 3. 提 案 手 法 パケットに特定のスイッチを経由させるための手法 として，ソースルートオプションがある．IPv4 では 本研究では，データセンターネットワークを，COTS Loose Source and Record Route Option，IPv6 で スイッチを用いてレイヤー 3 で構築することを前提と は Routing Header として標準化されており，IP ス する．これによって，2 章で述べたように，実環境へ タックの一部であるため COTS スイッチも対応してい の適用性と可用性を実現することができる．このとき， る．しかしながら，ソースルートオプションはセキュ COTS スイッチは効率的にトラフィックを分散する機 リティ上の問題によって利用できない，また多くのス 能を持たない．そこで，トラフィックを複数のパスに イッチにおいて CPU で処理されるためスループット 分散する機能を，ネットワークを構成するスイッチの が出ないなど，多くの問題がある．そのため，実環境 ハードウェアから，ソフトウェアによる機能追加が容 において，ソースルートオプションを中継点の指定に 易なサーバへと移す．つまり，サーバのネットワーク 用いることは現実的では無い． スタックに変更を加えることによって，サーバが複数 ソースルートオプションの代わりに，提案手法では のパスを選択してトラフィックを分散し，スループッ パケットに中継点を明示するための識別子として，ト トを向上させる． ンネリング技術を用いる．サーバがパケットを送信す 3.1 概 要 る際，IP でカプセル化を行う．そのとき，内部 IP ヘッ 図 1 に，提案手法の概要を示す．ある送信元サーバ ダの宛先は最終的な通信先サーバのアドレス，送信元 からある宛先サーバへのパスは，そのパスに対応する は送信するサーバ自身のアドレスとする．そして，カ スイッチをパケットの中継点として明示することで指 プセル化する外部 IP ヘッダの宛先は中継点として利 定できる．図 1 中，サーバ S からサーバ D への最短 用するスイッチのアドレス，送信元には全サーバで同 経路がスイッチ B を経由する場合，サーバ S はスイッ 一の IP アドレスを用いる．図 1 では，サーバ S がサー チ C を中継するようパケットに指定できれば，最短経 バ D に対してパケットを送信する際，外部 IP ヘッダ 路以外のパスへとパケットを通すことができる．また， の宛先としてスイッチ C のアドレスを用いることで， スイッチ B とスイッチ C をパケットごとに指定すれ 最短経路ではないパスへとパケットを通すことができ ば，両方のパスへとトラフィックを分散できる．この る．スイッチ C がカプセル化されたパケットを受信す ると，外部 IP ヘッダとカプセル化ヘッダを取り外し てサーバ D へと送信する．また，複数のスイッチを Userland Applications Kernel 中継させたい場合には，中継する順番に従ってパケッ トを複数回カプセル化することで，任意のパスへとパ IP packet Match iplb module Destination Prefix ケットを通すことができる．このように，トンネリン グ技術を用いることでサーバがパケットを通すパスを 明示的に指定する． 10.1.0.0/24 Tun hdr + IP packet 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 3.2 IP トンネルの規模性 端点から端点へとパケットをカプセル化して運ぶト ンネリング技術を，そのまま中継するスイッチの指定 図2 サーバへの変更の概要 のために用いた場合，トンネルの数とその規模性が問 題になる．あるデータセンターネットワークにおいて， アプリケーションがパケットを送信すると，iplb は 全てのパスを全てのサーバが指定できるようにするた まずパケットの宛先アドレスが先ほどの経路表にマッ めには，全てのサーバと全てのスイッチの間で IP トン チするかを検証する．マッチした場合，そのパケット ネルを構築する必要がある．しかし，一般的な COTS を通すべきパスを決定し，パスに通すために中継する スイッチで作成できるトンネル数は数十から数百程 スイッチを宛先とした IP ヘッダを付与する． 度であり，数千台規模のサーバやスイッチを収容する データセンターにおいては現実的でない． 送信するパケットを通すべきパスは，フローごとに， ラウンドロビンで決定する．フローは 5 タプル (宛先ア そこで提案手法では，このトンネル数の規模性の問 ドレス，送信元アドレス，プロトコル番号，宛先ポー 題を回避するために，全サーバで同一のアドレスを ト番号，送信元ポート番号) によって識別される．これ トンネルの送信元アドレスとして用いる．図 1 中の は，同一フローを構成するパケットが別のパスを通っ X.X.X.X がこのアドレスを示す．提案手法において， た場合，パケットの到着順序に入れ替わりが発生し， パケットは常にサーバによってカプセル化され，スイッ 上位のトランスポート層において性能の低下が発生す チによってカプセル化を解除される．つまり，スイッ ることを防ぐためである．アプリケーションの送信し チがパケットをカプセル化してサーバへ送信すること たフローの情報は，決定されたパスとともに iplb 内 は無く，トンネル内のパケットの通信方向は常に一方 で一定時間保持される． 向のみである．よって，全てのサーバはカプセル化し た際の外側 IP ヘッダの送信元アドレスとして，同一 4. ランダムグラフトポロジへの適用 の IP アドレスを用いることができる．このように同 本研究では，提案手法を，Jellyfish4) で提案される 一の IP アドレスを外部ヘッダの送信元に用いること ランダムグラフトポロジで構築されたデータセンター で，各スイッチに必要なトンネルは，スイッチ自身か ネットワークに適用する．Jellyfish では，ランダムグラ らその共通アドレス (X.X.X.X )，というただ 1 つと フトポロジでネットワーク全体のスループットを上げ なる．このようにして，提案手法ではトンネル数の規 るために，k-shortest path14) と Multipath TCP15) 模性を確保する． の利用が提案されている．しかし既存の COTS スイッ 3.3 サーバネットーワクスタックへの変更 チで構築するネットワークでは，k-shortest path ルー 提案手法は，トラフィックを複数のパスに分散する ティングを行うことはできない．そこで，提案手法を 機能を，ネットワークからサーバのネットワークスタッ k-shortest path のパス選択手法として利用すること クへと移す．本節では，この提案手法を実現するため で，COTS スイッチを用いたランダムグラフトポロジ に必要なサーバへの変更について述べる． でのスループット向上を実現する． サーバのネットワークスタックへの変更は，図 2 に 示す 1 つのカーネルモジュール (iplb) によって実現さ 4.1 ランダムグラフによるデータセンターネット ワーク れる．iplb は，カーネルスペースにロンゲストマッチ Jellyfish において，ランダムグラフは以下のように に基づく経路表を保持する．この経路表には，宛先ネッ 定義される．ネットワークを構成するスイッチ i は， トワークごとに，その宛先ネットワークへと到達する ki 本のポートを持つ．そして，ri 本ポートを他のス 複数のパスと，各パスを通すために中継しなければな イッチとの接続に用い，残った ki − ri 本のポートを用 らないスイッチのリストを保持する．ユーザランドの いてサーバを収容する．スイッチ i が ri 本のポートを 用いて接続するスイッチは，一様な確率で他のスイッ Userland Applica/on チから選択される．このようにして定義されるランダ ムグラフを，データセンターネットワークのトポロジ として用いる．本論文では，Jellyfish と同様に，全て MPTCP Kernel TCP TCP のスイッチが同じ k 本のポートを持ち，r 本のポート 短いパスのことである．これを見つけるために，Yen によって提案された k-shortest loopless path アルゴ リズム14) をはじめ，計算量の異なるいくつかのアル flow flow Path 1 flow k-shortest path は，あるグラフにおいて，特定の始 点から特定の宛先へ到達するパスのうち，k 番目まで TCP iplb flow をスイッチ間の接続に用いるものとする． TCP Path 2 Path 3 Path 4 Random Graph Network 図 3 提案手法による MPTCP サブフローの各パスへの割り当て ゴリズムがある．Yen のアルゴリズムによって作られ る k-shortest path は，始点から，宛先への最短経路 の各パスに通すために，提案手法を用いる． を外れた点 (分岐点) までの最短経路と，その分岐点か 提案手法を k-shortest path と MPTCP に組み合わ ら終点までの最短経路をつなげたパスである14) ．この せて用いる際の概要を図 3 に示す．ユーザランドのア 分岐点を変更していくことで，k 本のパスを作成する． プリケーションがデータを送信すると，MPTCP がそ ECMP によって利用できるパスは同一コストの最短経 のデータを複数の TCP セッションに分散して送信す 路に限られる．そのため，ランダムグラフで ECMP る．iplb は，各 TCP サブフローを事前に設定された を用いた場合，利用できないリンクが多く発生して k 本の各パスへとカプセル化を用いて転送する．複数 しまう．そこで各サーバ間の通信において k-shortest のパスにまたがった輻輳制御や，パケットの到着順が path アルゴリズムで発見した k 本のパスにトラフィッ 入れ変わった際の再構成などは MPTCP によって行 クを分散することで，ECMP では使えなかったリン われる．また，iplb はサーバの同一インターフェー クも利用することができる． スから送信されるフローも別のパスに通すことができ k-shortest path アルゴリズムでネットワーク上の るため，MPTCP を利用するためにひとつのサーバに 複数パスを見つけた上で，それらのパスにトラフィッ 複数のインターフェースを用意する必要は無い．この クを分散するために Multipath TCP(MPTCP)15) を ようにサーバの送信するパケットを k 本のパスへ分散 用いる．MPTCP は，複数の TCP セッションを束ね して送信することで，ランダムグラフトポロジにおい て 1 つの TCP セッションとして扱うためのトランス て，スイッチハードウェアへの変更無しで ECMP よ ポート層のプロトコルである．MPTCP では，1 つの りも多くのリンクを利用してトラフィックを転送する． MPTCP セッションを構成する複数の TCP セッショ ンが，異なる IP インターフェース経由で，異なる経 4.3 中継点の選択 iplb はあくまで指定した中継点となるスイッチへ 路を通って確立されることを想定している．そのため， とパケットをカプセル化して送信する機能である．そ 複数の TCP セッションをまとめて輻輳制御する機構 のため，特定のパスへ明示的にパケットを通すには， (Linked Increase アルゴリズム) を持つ．Jellyfish で 各パスにおいて中継しなければならないスイッチを決 は，この MPTCP を用いて 1 つの TCP セッション 定する必要がある．本節ではこの，あるパスについて を複数のサブフローとし，各サブフローを k-shortest 中継すべきスイッチを決定する手法について述べる． path アルゴリズムで見つけた複数のパスに分散する ことでネットワーク全体のスループットを向上させる． ひとつの送信元からひとつの宛先への k-shortest path は，同じ始点から同じ終点へ向かう途中の分岐 4.2 提案手法の適用 によって形成される．そこで，各パスを始点から比較 4.1 節で述べたように，k-shortest path と MPTCP していき，分岐したすぐ先のスイッチを中継点として によって，ランダムグラフで ECMP 以上のスループッ 記録していくことで，中継点のリストを作成すること トを実現する．しかし，Jellyfish の論文中でも述べられ ができる．まず，k-shortest path で発見した k 本の ているように，k-shortest path に選択的にトラフィッ パスから木構造をつくる．例として，k = 6 のとき， クを流すことは，既存の COTS スイッチに実装され スイッチ 8 からスイッチ 17 へと向かうパスから木構 た機能では実現できない．そこで本研究では，サーバ 造をつくる様子を図 4 に示す．各パスを木構造に追加 が MPTCP を構成するサブフローを k-shortest path する際，同一のスイッチであっても異なるホップ数に 用する．サーバが送信するトラフィックは MPTCP に 8 11 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 > よって複数の TCP サブフローに分割され，各フロー 12 が提案手法を用いて k-shortest path の各パスへ分散 1 2 4 3 して送信される．また各パスを明示的に指定するため 5 9 10 6 の中継点となるスイッチは，本節で述べた手法によっ て決定される． 2 17 9 4 10 17 図 4 k 本のパスから各パスの中継点の探索 (k = 6) 5. 評 価 データセンターネットワークを COTS スイッチを 用いたレイヤー 3 ネットワークで構築することによっ て，障害に対する可用性と，実環境への適用性を実現 Algorithm 1 中継点リストの作成 function DFsearch(V , relaylist, parent) if V.leaf list = 0 then する．そして，ランダムグラフトポロジのネットワー クで k-shortest path と MPTCP に提案手法を組み 合わせることで，スループットの向上を目指す．本論 V is bottom node. dump relaylist. 文ではその評価として，本手法によってネットワーク return. 全体のスループットがどの程度向上したかについて実 end if 験を行った．評価項目は，1) スループットの向上度 if parent.leaf list > 1 then 合い，2) カプセル化によるオーバーヘッド，の 2 点で push V to relaylist. end if for v in V.leaf list do DFsearch(v, relaylist, V ) ある． 本手法を用いた場合，COTS スイッチを利用した ネットワークにおいても，最短経路のみを用いた場合 と ECMP を用いた場合に対して，多くのリンクを利 end for 用できるはずである．そこでまず，これによってネッ end function トワーク全体のスループットがどの程度向上するかに ついて実験を行った．次に，カプセル化のオーバーヘッ 出てきたスイッチは別のノードとして扱う．これは， ドについて評価を行った．提案手法では，サーバが送 木構造の中でループが発生するのを防ぐためである． 信する全てのパケットはカプセル化されて送信される． 各パスを指定するには，この木構造において終点に またパスによっては，複数回カプセル化される．その 到るまでに分岐した箇所を中継点として指定していけ ため，MTU に対してパケットサイズの減少が発生し， ばよい．そこで，アルゴリズム 1 に示す深さ優先探索 スループットが低下することが考えられる．このカプ を行う．始点から，自ノードの前のノードが 2 本以上 セル化に起因するスループットの低下が問題の無い範 の子ノードを持つ場合，つまり自ノードが分岐した先 囲に収まるかどうかを調査した． のノードである場合は，自身を中継点のリストに追加 5.1 実 験 環 境 する，という処理を行いながら探索する．例えば図 4 実験環境として，ns-316) とその拡張である ns-3- において，ノード 8，11，1 と辿った際，ノード 1 か dce17) を用いた．ns-3 はネットワークシミュレータ ら見て前となるノード 11 は 2 つの子ノードを持つ． であり，ns-3-dce は，ns-3 上で Linux カーネルを動 そこでノード 1 は自身を中継点リストに追加する．次 作させるための拡張である．シミュレータ上で構築し にノード 5 もノード 1 が複数の子ノードを持つため たトポロジは，表 3 に示すサイズの異なる 3 つのト 自身を中継点リストに追加する．こうして終点となる ポロジである．ポート数に対するスイッチの数とサー ノード 17 まで辿り，⟨8, 11, 1, 5, 2, 9, 17⟩ のパスを通 バの数は，3-level k-ary Fat-tree に準ずる6) ．各サイ すための中継点は ⟨1, 5⟩ であると分かる．同様にして， ズのトポロジについて，ns-3 上にネットワークをつく ⟨8, 11, 1, 9, 17⟩ のパスは ⟨1, 9⟩，⟨8, 11, 2, 9, 17⟩ のパス り，ここに接続される全てのサーバにおいて，Linux は ⟨2⟩ となる． カーネルモジュールとして実装した iplb を用いて他 このようにして，COTS スイッチで構築したデータ のサーバへの k-shortest path を通る中継点の設定を センターネットワークにおいてサーバが明示的にパス 行った．カプセル化には，Generic Routing Encapsu- を指定するための手法をランダムグラフトポロジに適 lation (GRE) を用いた．また，全てのリンクの MTU 表 2 シミュレーション結果 トポロジサイズ 4 ポート 6 ポート 8 ポート ECMP 1.12 1.21 1.25 2 1.18 1.19 1.16 3 1.22 1.28 1.28 k-shortest 4 1.23 1.30 1.31 表 3 実験トポロジサイズ path (k = 1 8) 5 6 7 1.22 1.23 1.19 1.28 1.30 1.30 1.31 1.31 1.30 8 1.17 1.31 1.30 1 スイッチ数 サーバ数 4 ポート 6 ポート 8 ポート 20 45 80 16 54 128 0.8 CDF スイッチのポート数 0.6 0.4 0.2 は 9000 バイトとした．実験では，それぞれのトポロ ジにおいて，各サーバがランダムに選択した宛先サー バに対して 8 つの TCP サブフローから成る MPTCP 8-port 12-port 0 0 1 2 3 4 Number of relay points 5 6 図 5 各パスにおける必要なカプセル化回数 トラフィックを同時に送信し，各サーバが受信できた バイト数の合計を計測した． が 24 バイト減少する．つまり，1 つのパスを指定す 5.2 実 験 結 果 るために 3 つの中継点が必要な場合，72 バイトのパ 各トポロジにおいて，テストトラフィックを送受信 ケットサイズの減少が起こる． するサーバのペアをランダムに変更しながら 15 回実 MTU サイズが 1500 バイトの場合，72 バイトのパ 験を行った結果の平均を表 2 に示す．表 2 の値は，最 ケットサイズの減少は，4.8%の性能低下となる．し 短経路のみを用いた場合に，各サーバが受信できたバ かし，データセンターネットワークは 1 つの管理者に イト数の合計を 1 として正規化したものである．この よって管理されるネットワークであり，MTU が 9000 実験の結果から，4 ポートの際は k = 3 から k = 6 ま バイト以上のジャンボフレームを利用できる．MTU での k-shortest path を利用した場合，最短経路のみ を 9000 バイトとした場合，72 バイトのカプセル化 の場合に対して約 1.2 倍ほどスループットが向上する オーバーヘッドは，0.8%の性能低下にしかならない． ことがわかった．k = 6 までなのは，各サーバから宛 このことから，ジャムボフレームの適用可能なデータ 先までのパスに対してネットワーク全体のリンクの数 センターネットワークにおいては，カプセル化のオー が少ないためである．そして 6 ポート以上のサイズの バーヘッドは問題にならないと言える． ランダムグラフでは，k = 6 以上の k-shortest path を利用することによって，最短経路のみを用いた場合 6. 結論と今後の課題 に対して 1.3 倍ほどのスループットを実現できること 本研究では，COTS スイッチによって構築されたレ がわかった．また全てのサイズにおいて，ECMP よ イヤー 3 データセンターネットワークにおいて，トン りも高いスループットを実現できた． ネリング技術を用いて効率的にマルチパスを利用する 5.3 カプセル化によるオーバーヘッド ための手法を提案した．そしてシミュレータ上で評価 本節では，カプセル化によるオーバーヘッドについ を行い，ランダムグラフトポロジのネットワークにお て述べる．図 5 に，8 ポートのスイッチ，および 12 いて，最短経路のみを用いた場合の 1.2 倍から 1.3 倍， ポートのスイッチで構成したランダムグラフ (180 ス また ECMP よりも高いスループットを実現できるこ イッチ，432 サーバ) において，k = 8 の k-shortest とを示した．今後の課題として，まずコントロールプ path を用いた際，各パスを指定するために必要な中 レーンシステムがある．実環境で利用するためには， 継点の数を累積密度分布に並べたものを示す．8 ポー 中継点の自動設定と，障害時に短時間での切り替えを トの場合，90%以上のパスを 3 つの中継点で指定する 行う必要がある．そのために現在，OSPF を用いたコ ことができる．また，12 ポートの場合は 4 つで指定 ントロールプレーンの設計と実装、評価を行っている． することができる．カプセル化のフォーマットとして またカプセル化自体のオーバーヘッドについても評価 GRE を用いた場合，1 回のカプセル化で GRE ヘッ を行う．その上で，ランダムグラフ以外のトポロジに ダと外側 IP ヘッダの追加によって，パケットサイズ も提案手法が適用可能であるかの調査を行う． SIGCOMM Comput. Commun. Rev., 39(1):68– 73, December 2008. 9) D.Eastlake 3rd, T.Senevirathne, A.Ghanwani, 1) Petr Lapukhov. Building scalable data cenD.Dutt, and A.Banerjee. Transparent Interconters: Bgp is the better igp. https://www.nanog.org/ meetings/nanog55/presentations/Monday/Lapukhov nection of Lots of Links (TRILL) Use of IS-IS . RFC, IETF, May 2014. .pdf, June 2010. NANOG 55. 10) Changhoon Kim, Matthew Caesar, and Jen2) Alexey Andreyev. Introducing data cennifer Rexford. Floodless in seattle: A scalable ter fabric, the next-generation facebook data ethernet architecture for large enterprises. In center network. https://code.facebook.com/ Proceedings of the ACM SIGCOMM 2008 Conposts/360346274145943/introducing-data-centerference on Data Communication, SIGCOMM fabric-the-next-generation-facebook-data-center’08, pages 3–14, New York, NY, USA, 2008. network/, November 2014. Facebook, Inc. ACM. 3) Chuanxiong Guo, Guohan Lu, Dan Li, Haitao 11) R.Nakamura, Y.Sekiya, and H.Esaki. Layer-3 Wu, Xuan Zhang, Yunfeng Shi, Chen Tian, Multipathing in Commodity-based Data CenYongguang Zhang, and Songwu Lu. Bcube: ter Networks. In Global Internet Symposium A high performance, server-centric network ar2015, IEEE, April 2015. chitecture for modular data centers. In Pro12) Jayaram Mudigonda, Praveen Yalagandula, ceedings of the ACM SIGCOMM 2009 ConferMohammad Al-Fares, and Jeffrey C. Mogul. ence on Data Communication, SIGCOMM ’09, Spain: Cots data-center ethernet for multipages 63–74, New York, NY, USA, 2009. ACM. pathing over arbitrary topologies. In Proceed4) Ankit Singla, Chi-Yao Hong, Lucian Popa, ings of the 7th USENIX Conference on Netand P. Brighten Godfrey. Jellyfish: Networked Systems Design and Implementation, working data centers randomly. In ProceedNSDI’10, pages 18–18, Berkeley, CA, USA, ings of the 9th USENIX Conference on Net2010. USENIX Association. worked Systems Design and Implementation, 13) Albert Greenberg, JamesR. Hamilton, Navendu NSDI’12, pages 17–17, Berkeley, CA, USA, Jain, Srikanth Kandula, Changhoon Kim, 2012. USENIX Association. Parantap Lahiri, DavidA. Maltz, Parveen Pa5) M.F. Bari, R. Boutaba, R. Esteves, L.Z. tel, and Sudipta Sengupta. Vl2: A scalable and Granville, M. Podlesny, M.G. Rabbani, Qi flexible data center network. In Proceedings of Zhang, and M.F. Zhani. Data center network the ACM SIGCOMM 2009 Conference on Data virtualization: A survey. Communications SurCommunication, SIGCOMM ’09, pages 51–62, veys Tutorials, IEEE, 15(2):909–928, February New York, NY, USA, 2009. ACM. 2013. 14) J.Yen. Finding the k shortest loopless paths 6) Mohammad Al-Fares, Alexander Loukissas, in a network. In Management Science, 1971, and Amin Vahdat. A scalable, commodity data 1971. center network architecture. In Proceedings of 15) A. Ford, C. Raiciu, M. Handley, and O. the ACM SIGCOMM 2008 Conference on Data Bonaventure. TCP Extensions for Multipath Communication, SIGCOMM ’08, pages 63–74, Operation with Multiple Addresses. RFC 6824, New York, NY, USA, 2008. ACM. IETF, January 2013. 7) Radhika NiranjanMysore, Andreas Pamboris, 16) ns-3 project. http://www.nsnam.org/. Nathan Farrington, Nelson Huang, Pardis 17) Hajime Tazaki, Frédéric Uarbani, Emilio Miri, Sivasankar Radhakrishnan, Vikram SubMancini, Mathieu Lacage, Daniel Camara, ramanya, and Amin Vahdat. Portland: A scalThierry Turletti, and Walid Dabbous. Direct able fault-tolerant layer 2 data center netcode execution: Revisiting library os architecwork fabric. In Proceedings of the ACM SIGture for reproducible network experiments. In COMM 2009 Conference on Data CommunicaProceedings of the Ninth ACM Conference on tion, SIGCOMM ’09, pages 39–50, New York, Emerging Networking Experiments and TechNY, USA, 2009. ACM. nologies, CoNEXT ’13, pages 217–228, New 8) Albert Greenberg, James Hamilton, DavidA. York, NY, USA, 2013. ACM. Maltz, and Parveen Patel. The cost of a cloud: 参 考 文 献 Research problems in data center networks.
© Copyright 2024 ExpyDoc
