ネットワークの混雑を制御するアルゴリズムに「公平な通信を提供しきれない」という問題があることが判明

2022年7月2日に発生したKDDIの通信障害では、多数の端末からアクセスが集中したためにネットワークで輻輳(ふくそう)が発生し、KDDIのモバイル通信などを利用しづらい状況が長時間にわたり続きました。輻輳について行われた新たな海外研究で、本来あらゆるユーザーが公平にネットワークへアクセスできるよう管理するアルゴリズムに偏りがある可能性が指摘されました。

Researchers discover major roadblock in alleviating network congestion | MIT News | Massachusetts Institute of Technology
https://news.mit.edu/2022/algorithm-computer-network-bandwidth-0804

マサチューセッツ工科大学の研究者らによると、Googleが開発したTCP BBRを始めとする輻輳制御アルゴリズムには偏りが存在する可能性があるとのこと。これにより、1つ以上の送信者が他の送信者に比べて帯域幅をほとんど受け取れない問題が常態化する「飢餓(starvation)」という事態が回避できなくなると、研究者らは指摘しています。

インターネット上でデータを送信するコンピューターや機器はデータを小さなパケットに分割し、特殊な輻輳制御アルゴリズムを使ってそのパケットをどのくらいの速度で送信するかを決定します。

もしアルゴリズムがない場合、ユーザーのコンピュータはネットワーク接続の品質や他の送信者がどれくらいネットワークを使用しているかなどの情報が不足するため、ネットワーク上でデータパケットを送信する速度を正しく決定できないとのこと。しかるべき役割を担う輻輳制御アルゴリズムはパケットの損失と遅延から輻輳を推測し、どの程度の速度でデータを送信するかを決定することができます。

パケットを送る速度が遅すぎると利用可能な帯域幅を十分に活用することができず、あまりに速すぎるとネットワークに負担がかかってパケットが破棄されてしまいます。このように破棄されたパケットは再送信しなければならず、遅延が長くなってしまいます。つまり、輻輳制御アルゴリズムには利用可能なネットワーク容量を各ユーザーに公平に割り当てることで、遅延を最小限に抑える役割もあります。

しかし、インターネットは複雑で、輻輳とは無関係な理由でパケットが遅延・損失することがあります。輻輳制御アルゴリズムは研究者らが「ジッター」とひとまとめに呼ぶ「輻輳とは無関係の遅延」と「輻輳による遅延」を見分けることができないそうで、予測不可能なジッターがアルゴリズムを混乱させ、アルゴリズムがパケットを不均等な速度で送信するようになった結果、誰かが完全にネットワークからシャットアウトされてしまうとのこと。

研究を率いたMohammad Alizadeh氏は「ネットワーク経路の複雑さと、それらがデータパケットに及ぼすあらゆる影響を考慮すると、現行の輻輳制御アルゴリズムが上記の問題を回避することは基本的に不可能です」と指摘。Alizadeh氏らは知っている限りのアルゴリズムで実験し、自分たちで新たにアルゴリズムを作成してまで試したにもかかわらず、誰かがネットワークからシャットアウトされてしまう状況が例外なく発生してしまったとのこと。このようなアルゴリズムは「公平である」と広く信じられているため、研究者たちはこの結果に驚いたそうです。

今回の研究では、現行の「遅延集中型アルゴリズム」では飢餓が防げないことが分かりましたが、遅延が集中しないアルゴリズムがあれば問題が回避できる可能性もあるとのこと。

研究の筆頭著者であるVenkat Arun氏は「広く使われているアルゴリズムでこのような単純な問題が長い間知られていなかったという事実は、実証実験だけでアルゴリズムを理解することがいかに難しいかを示しています」と述べました。Arun氏らは問題を解決できるアルゴリズムが見つかるかどうか、さらなる研究を続けたいと考えているとのことです。