これから学ぶ人も、資格取得を目指す人も、最適なカリキュラムを選べます。
これから学ぶ人も、資格取得を目指す人も、最適なカリキュラムを選べます。
CTC 教育サービス
[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes
今回からは、2022年に公開された論文「Hashing Design in Modern Networks: Challenges and Mitigation Techniques」を紹介していきます。この論文では、ECMPなどのマルチパス技術を用いた現代のデータセンターネットワークにおける、負荷分散用のハッシュ関数に関わる課題が説明されており、論文の筆者らが考案した、数学的な理論に基づいた解決策が紹介されています。ECMPのように長く使われてきた技術にもまだ改善の余地があると気付かされる点で、興味深い内容の論文です。
はじめに、データセンターネットワークにおけるマルチパス構成の仕組みを説明しておきます。図1は、Googleのデータセンターでも用いられている、Closトポロジーのデータセンターネットワークです。サーバーが接続されたToR（Top of Rackスイッチ）を含めて、全部で5つのレイヤーからなる階層型の構成で、2つのToRの間には複数の通信経路が存在します。これら複数の経路を並列に使用することで、広い通信帯域を確保します。
図1 Closトポロジーのデータセンターネットワーク（論文より抜粋）
この際、通信パケットごとに経路を振り分ける技術がECMPです。図2の左図では、左側のサブネットから右側のサブネットにパケットが転送されていきますが、はじめに、スイッチS1は、このパケットをスイッチS2、スイッチS3のどちらに転送するかをECMPで決定します。具体的には、パケットヘッダに含まれる「送信元IPアドレス」「送信先IPアドレス」「TCP/UDPポート」などの情報からハッシュ値を計算して、このハッシュ値を2で割った余りの値でS1かS2を選択します。一般にn個の転送先があった場合、ハッシュ値をnで割った余りの値で決定します。その後に続くS2、S3も同様の方法で、次にパケットを送信するスイッチを選択します。
図2 ECMPによる経路選択（論文より抜粋）
このように、パケットヘッダに含まれる情報のハッシュ値に基づいて経路を選択することにより、同一のセッションに伴うパケットは必ず同じ経路を通ることになります。仮に同一のセッションに伴う複数のパケットがそれぞれに異なる経路を通ったとすると、送信先にパケットが到着する順序が入れ替わる可能性がありますが、このような問題を避ける事ができます。
ECMPによる負荷分散は、それぞれのスイッチが使用するハッシュ関数が同一（より一般には、ハッシュ値に相関関係のある関数）の場合、すべての経路が均等に使用されなくなるという問題があります。
たとえば、先ほどの図2において、S1はハッシュ値を2で割った余りが0（すなわち、ハッシュ値が偶数）のパケットをS2に転送して、同じく、S2はハッシュ値を2で割った余りが0（ハッシュ値が偶数）のパケットをS4に転送するものとします。この時、S1とS2が同じハッシュ関数を使用していると、S2は、S1から転送されたすべてのパケット（すなわちハッシュ値が偶数のパケット）に対して、同じ偶数のハッシュ値を得ます。したがって、S2はS1から受け取ったすべてのパケットをS4に転送することになり、結果として、S2からS5に転送されるパケットが存在しなくなります。次の図3はこの状況を説明したもので、H1はハッシュ関数で、indexはハッシュ値を2で割った余りの値を表します。それぞれのスイッチが同じハッシュ関数H1を使用しているため、indexが0のパケットとindexが1のパケットで2つの経路にわかれています。図2に戻ると、本来は、左図のようにPath1〜Path4の4種類の経路を使用するべき所が、右図のようにPath1とPath4の2種類の経路しか使用されなくなるというわけです。
図3 ハッシュ関数の相関により経路が偏る原理（論文より抜粋）
この問題を避けるために、ECMPの機能を提供するネットワークスイッチは、通常、複数の種類のハッシュ関数を提供しており、スイッチごとに計算原理の異なる（相関関係を持たない）ハッシュ関数を選択します。しかしながら、一般的なネットワークスイッチに搭載されるハッシュ関数は、多くても8種類程度のため、図1のような多数のネットワークスイッチからなる大規模なネットワーク環境では、すべてのスイッチで異なるハッシュ関数を使用することができず、経路によって通信量が偏るという問題が発生します。複雑なアルゴリズムのハッシュ関数を使用すれば、互いに相関関係を持たない多数のハッシュ関数を作り出すこともできますが、ネットワークスイッチ上のハッシュ関数は、高速なパケット転送を行うためにASICを用いてハードウェア的に実装されており、あまり複雑なアルゴリズムのハッシュ関数を搭載できないという事情もあります。
ECMPの機能を提供するネットワークスイッチでは、ハッシュ関数に「シード」と呼ばれる定数値を設定することができます。これは、入力値に対して、シードとのXORを演算してからハッシュ値を計算するもので、シードの値を変えることで、擬似的にハッシュ関数の種類を増やす事ができます。しかしながら、この方法では前述の問題は解決されないことが冒頭の論文で指摘されています。たとえば、ネットワークスイッチで広く使用されているCRCと呼ばれるハッシュ関数の場合、あるシード値のもとでハッシュ値を2で割った余りが一致する2つの入力値は、シード値を変えても、やはりハッシュ値を2で割った余りが一致してしまいます。
転送先が3個以上の場合やCRC以外のハッシュ関数の場合は、この議論は当てはまりませんが、論文内では、シミュレーションによってシード値の効果を確認しており、シード値だけでは経路の偏りを解消できないことが確認されています。
今回は、2022年に公開された論文「Hashing Design in Modern Networks: Challenges and Mitigation Techniques」に基づいて、大規模なデータセンターネットワークにおける、ECMPを用いた負荷分散の仕組みとその問題点を説明しました。次回は、論文内で紹介されている、この問題の解決策について説明していきます。
Disclaimer：この記事は個人的なものです｡ここで述べられていることは私の個人的な意見に基づくものであり、私の雇用者には関係はありません｡
[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes
