酷い輻輳によるパケット損失に勝つための方法を記しておきます。

ECNを有効にする

エンドポイントがECN対応のTCPパケットは輻輳制御で優遇される傾向にあるようです。例えば、Ciscoの (PIEより一世代古い) WREDアルゴリズムでは、ECN対応パケットが露骨に優遇されています。
http://www.cisco.com/cisco/web/support/JP/docs/CIAN/IOS/IOS15_1M_T/CG/012/wred_ecn.html?bid=0900e4b1825ae572

デスクトップ版Windowsは標準でECNが無効となっているため、ECNを有効にするためには手動で設定する必要があります。Linuxでも全てでECNを有効にするためにはsysctl net.ipv4.tcp_ecn=1とする必要があります (恒常的に設定するためには/etc/sysctl.confに書く必要があります)。なお、一部のECN未対応の環境では問題が起こることもあるので注意。

ちゃんとECNが有効になっているかは、sudo tcpdump -i eth1 "tcp[tcpflags] & (tcp-syn) != 0"で、外向きSYNパケットにW (ECN CWR)やE (ECN-Echo)のフラグが付いているかを確認してください。

TCPを使う

UDPにはECNフラグがありませんし、パケット損失への強さも上位プロトコルによります。そのため、ネットワークに存在するルータの輻輳制御によっては、TCPの方が有利になる場合があります (もちろんTCPが不利になる場合もあります)。

例えばGoogle ChromeでQUICを切ったり、DNSでTCPのみにするとパケット損失が減る可能性があります。こちらの環境ではDNSをTCPにすると、3way handshakeのせいで全体的に遅くなるものの、タイムアウトはしにくくなっているようです (たまに遅くなるものの、1秒未満なので再送ではないはず?)。遅くならないようにTCP Fast Openを使いたいところですが、それを使うためにはglibcのDNS問い合わせ部分の改変が必要になるはずなので断念。

DNSの速度測定 (Ubuntu)

DNSの速度測定には、dnsdiagのdnspingが便利でしょう。以下により、導入できます。

sudo apt-get install python3-dnspython
git clone https://github.com/farrokhi/dnsdiag.git
cd dnsdiag/
git submodule update --init

UDPでのテストは以下のように行います (8.8.8.8の部分は試したいDNSキャッシュサーバーに変更してください)。

./dnsping.py -s 8.8.8.8 qiita.com

TCPでのテストは以下のように行います。

./dnsping.py -s 8.8.8.8 -T qiita.com

DNS問い合わせを標準でTCPにする (Ubuntu)

DNSサーバーを外部のものに変更し (DNSサーバーが192.168.1.1とかだとTCPにしても意味ないですから)、resolv.confにoptions use-vcを追加させてDNSをTCPにします。具体的には、/etc/resolvconf/resolv.conf.d/headに以下の内容を書き込み、sudo resolvconf -uを実行します (なお、以下は便宜上Google Public DNSのIPアドレスを使用していますが、ISP網内にあるISPのDNSキャッシュサーバーの方が良い場合はそれに書き換えてください)。

options use-vc
nameserver 8.8.8.8
nameserver 8.8.4.4

ちゃんとTCPになっているかは、sudo tcpdump -i eth1 udp port 53で何も無いことを確認すれば分かります。

終わりに

これらの手法がCiscoの新たなアルゴリズムであるPIE AQMや、他社メーカーのルーターに通用するかは分かりませんが、パケット損失が酷い環境では一般的に有用でしょう。この記事がパケット損失に困っている人の助けになれば幸いです。