利己的なルーターがインターネット全体を遅くする～米コーネル大学の研究結果

■URL
http://www.news.cornell.edu/releases/Feb03/AAAS.Roughgarden.selfish.html

　「ルーターがパケットを送信する最速経路を選択してしまうために、インターネット全体の速度が低下する」。こんな研究結果をコーネル大学の研究者たちが発表した。

　この研究は、米コーネル大学のポストドクターTim Roughgarden氏と、コンピュータサイエンスの教授Eva Tardos氏が行なったもの。2月14日に開催されたインターネットに経済学の原理を応用するためのシンポジウム「Game Theoretic Aspects of Internet Computation」で、「Selfish Routing and the Price of Anarchy」と題して発表されたものだ。

　研究結果によると、“利己的な”ルーターはさまざまな経路の中からもっとも混雑が少ない経路を選び、その経路もまた混雑してくると前の選択の時には無視していた経路を選択するようになるという。ルーターがインターネット上のさまざまな地点でこの“利己的な”選択を続けると、インターネットシステム全体は数学者が言うところの「ナッシュフロー」という平衡状態に落ち着くことになるが、これは理想的なインターネットの速度よりも遅くなる。

　数学的な解析によると、このような利己的なルーティングの影響で、理想的なインターネットでパケットを送る時間よりも1.33倍の時間がかかることになるという。また、より複雑なネットワークの場合、最悪で1.67倍の時間がかかることも判明した。しかしながら、これらの数学的な解析は仮想ネットワークで行なわれたため、より複雑な状況の実際のインターネットで、この数学的モデルが通用するかどうかは未知数だ。

　Roughgarden氏は、この問題を解決し、できるだけインターネットの平均速度を速めるために実行可能な簡単な方法を提案している。ルーターが、自分が送信しようとしているパケットによって経路に与える影響を加味して上で、経路選択するような“少しだけ利他的な”アルゴリズムを選択することだ。そうすればパケットは最速のルートを通れないかもしれないが、すべてのユーザーの平均速度は向上することになるだろうとしている。

(2003/2/17)

[Reported by 青木 大我 (taiga@scientist.com) ]