コラム

CTC教育サービス・ホーム　＞　コラム　＞　グーグルのクラウドを支えるテクノロジー　＞　第97回　インターネット上のロードバランサーの構成調査（パート1）

グーグルのクラウドを支えるテクノロジー

CTC 教育サービス

[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

第97回　インターネット上のロードバランサーの構成調査（パート1） (中井悦司) 2021年1月

はじめに

　今回からは、2020年に公開された論文「Classification of load balancing in the Internet(PDF）」を紹介していきます。この中では、ネットワーク経路を調べる伝統的なツールである「traceroute」をロードバランサーを含む経路に対応するための拡張手法が提案されており、さらにこれを用いた実際の調査結果が示されています。

tracerouteの基本的な仕組み

　はじめに、一般的なtracerouteの仕組みを簡単に説明しておきます。IPネットワークでは、パケットを中継するルーターには、それぞれに個別のIPアドレスが設定されています。ネットワークに送出したパケットは、複数のルーターを経由して送信先の機器に到達しますが、途中で通過したルーターのIPアドレスがわかれば、どのような経路を通っていったかが把握できます。tracerouteは、IPパケットに付随するTTL（Time to live）という情報を用いて、経路上のルーターのIPアドレスを調べます。
　TTLは、パケットが送信先の機器に到達するまでに通過できるルーターの最大数を表します。たとえば、TTL=3に設定したパケットを送出すると、ルーターを通過するごとにTTLの値が1ずつ減っていき、3つ目のルーターでTTL=0になります。すると、3つ目のルーターはこのパケットを破棄して、パケットを破棄したことを示すメッセージを送信元の機器に通知します。tracerouteは、このメッセージの中にパケットを破棄したルーターのIPアドレスが含まれていることを利用して、経路上のルーターのIPアドレスを確認します。はじめに、TTL=1に設定したパケットを送信すると、1つ目のルーターでパケットが破棄されるので、このルーターからの通知メッセージにより、1つ目のルーターのIPアドレスがわかります。次に、TTL=2に設定したパケットを送信するすると、2つ目のルーターでパケットが破棄されて、このルーターからの通知メッセージにより、2つ目のルーターのIPアドレスがわかります。このようにして、送信先の機器にパケットが到達するまで、TTLの値を増やしながら何度もパケットを送信する事で、経路上のすべてのルーターのIPアドレスを取得します。

ロードバランサーを含む経路の探索

　tracerouteの仕組みは、シンプルでわかりやすいものですが、経路上にロードバランサーがあると経路をうまく調査できないことがあります。たとえば、送信元「s」と送信先「d」の間に図1（左）のような経路があったとします。AとBはロードバランサーの機能を持ったルーターで、パケットごとに送り先のルーターを選択するため、「s」から「d」に到る経路が1つに定まりません。

fig01

図1　ロードバランサーを含む経路の例（論文より抜粋）　

　さらに、tracerouteでは、TTLを増やしながら何度もパケットを送信するため、パケットごとに経路が異なる場合もあり得ます。たとえば、最初の3つのパケットが次の様な経路を通ったとします。

・1回目（TTL=1）：s → A
・2回目（TTL=2）：s → A → C
・3回目（TTL=3）：s → A → B → D

　ルーターAは、2つ目と3つ目のパケットに対して、異なる経路を割り当てています。しかしながら、tracerouteは、それぞれのパケットが最終的に破棄された場所（パケットを破棄したルーターのIPアドレス）しかわからないため、「s → A → C → D」という経路でパケットが転送されたものと誤った解釈を行います。つまり、先ほどの図1（右）のように、本来はあり得ない経路を検知してしまいます。
　tracerouteのこのような制限は以前から知られており、これまでにもロードバランサーを含む経路を正しく判別するための機能拡張がいくつか提案されてきました。最も単純な方法は、同じTTLの値を持ったパケットを何度も送信して、その結果を比較するというものです。さきほどの例であれば、TTL=2のパケットを何度か送信すれば、「s → A → C」と「s → A → B」の両方の結果が得られて、ルーターAが2つの経路を持つロードバランサーであることがわかります。
　しかしながら、経路上に複数のロードバランサーがある場合、パケットが取り得る経路のパターンが指数的に増加するため、すべてのロードバランサーを検知するには、多数のパケットを送信する必要があります。また、どれだけ多数のパケットを送信したとしても、それで本当にすべてのロードバランサーを正しく検知できたかはわかりません。特に、最近は、SDN（Software defined network）の技術を用いたロードバランサーも多く、パケットを振り分けるアルゴリズムにもさまざまなバリエーションがあります。冒頭の論文では、パケットのヘッダー情報を変化させることで、できるだけ多くの経路にパケットが振り分けられるようにしながら、少ないパケット数で統計的に信頼できる精度でロードバランサーを発見するアルゴリズムが提案されています。アルゴリズムの詳細については、少し高度な内容になるため、ここでは説明を割愛します。興味のある方は、ぜひ、論文に目を通してみてください。

次回予告

　今回は、2020年に公開された論文「Classification of load balancing in the Internet」の導入として、tracerouteの仕組みとロードバランサーを含む経路に対する課題を説明しました。本文で触れた様に、論文内では、この課題を解決するアルゴリズムが示されており、さらには、このアルゴリズムを実装したツールを用いて、インターネット上のさまざまな経路を大規模に調査した結果が紹介されています。次回は、この調査結果を紹介したいと思います。

Disclaimer：この記事は個人的なものです｡ここで述べられていることは私の個人的な意見に基づくものであり、私の雇用者には関係はありません｡