要約

  • ECMPは同じルーティングコストの次ホップを複数使えるという分類であり、各経路のMTU、遅延、パケット順序、マルチキャスト上の役割が同じだとは保証しない。
  • RFC 2991は、同一フローを一つの経路に留めながら、次ホップ追加・削除時の再割り当てを抑える方式を比較した。

tracerouteが記録するのは、そのプローブが通った経路だ。ルーターが選択肢として持っていた他の次ホップや、別のフローの割り当てまでは見えない。「等コスト」を経路そのものの同等性と読み替えると、この観測範囲を取り違える。

Dave ThalerとChristian Hoppsが2000年11月に発表した RFC 2991は、ユニキャストとマルチキャストにおけるマルチパス転送を整理した情報提供文書である。OSPFとIS-ISは等コストマルチパス（ECMP）を明示的に認め、一部のルーター実装はRIPなどにも適用していた。同じ宛先への有効な次ホップが複数あれば、転送装置は各パケットをどこへ送るか決めなければならない。

ラウンドロビンで順番に出口を変えれば、見かけ上は負荷を分散できる。しかし同じ通信がMTUも遅延も異なる経路を行き来する。パケットごとに経路MTUが揺れれば、経路MTU探索の前提が崩れる。遅れて届いたパケットの前に後続パケットがそろうと、TCPは損失と判断して高速再送を起こしうる。余計な再送は帯域を消費し、バッファも必要にする。pingやtracerouteも異なる枝を観測し、経路を誤って示すことがある。マルチキャストではさらに、当時のプロトコルが送信元やコア、ランデブーポイントへ向かう単一の木を作り、重複やループを防いでいた。木の根へ向かう次ホップは一つでなければならず、パケット単位の交替は単なる性能上の好みではない。

RFC 2991でいう「フロー」は、ルーターが状態を保持する粒度を指す。常に状態があるとは限らず、RFC 2474のマイクロフローのようにポート番号まで使うとも限らない。宛先アドレスだけの場合も、送信元・宛先・プロトコル番号の組み合わせの場合もある。先頭でない断片にはトランスポート層の情報がないことがあるし、ポートを選択キーに加えると、同じ両端間の後続通信でMTUなどの経路情報を再利用しにくくなる。「フロー」の定義は実装に委ねられたが、その選択は経路の一貫性を左右した。

一つのフローを同じ経路に留めれば、会話の途中で経路が入れ替わる問題は減る。だが次ホップが加わる、または消えるとき、どれだけの既存フローが動くのか。ECMPでは候補経路の変更が転送中の通信に直結しやすく、経路フラップ時の並べ替えや損失の範囲も広がりうる。そこでRFCは、再割り当てを小さくすることと、選択計算を軽くすることを同時に求めた。

Modulo-Nハッシュは軽い。フローをハッシュし、次ホップ数Nで割った余りから出口を選ぶ。ただしNが変わると、RFCの分析では (N-1)/N のフローが別経路へ移る。ハッシュしきい値方式は出力空間を各次ホップの領域に分け、境界付近の割り当てだけを動かす。次ホップの増減で四分の一から二分の一が移るとRFCは見積もった。RFC 2992はこの方式の撹乱量を詳しく分析している。Highest Random Weight（HRW）はフローと各候補次ホップを組み合わせてハッシュし、最も高い値を選ぶ。メンバー一つの変更で動くのは約 1/N のフローに抑えられる一方、計算量はModulo-NのおよそN倍となる。

これらは文書が置いたモデル上の割合であり、本番ルーターの測定値ではない。数えているのはフローであって、バイト数、顧客数、サービス影響ではない。少数の長大なフローが大半のトラフィックを占める場合、フロー数の均等さから容量の均等さは導けない。

フロー状態の有無は、コストを払うタイミングを変える。状態を作るときに次ホップを選べば、各パケットで再計算する必要はない。RFCは、状態を持つユニキャストと送信元／グループ状態を持つマルチキャストにはHRWを推奨した。ユニキャストで状態を持たない転送器は到着時に選択を計算するため、安定性よりCPUを重く見る場合にはハッシュしきい値方式が推奨された。これはアーキテクチャに条件づけられた選択で、普遍的な勝者ではない。

2011年のRFC 6438も、経路ごとの負荷を分けること、同一フローの順序を保つこと、リンクを遊ばせないことの間に緊張があると記している。問題の持続性を示す後年の文書ではあるが、全ルーターがRFC 2991の方式を採用した証拠ではない。

この歴史から残るのは、層を混同しないことだ。ルーティングコストは候補を分類し、選択器はフローを割り当て、物理経路は実際のMTUや遅延を決め、TCPは受信結果に反応する。安定性には計算コストか負荷の偏りという代償があり、再割り当てには既存通信を動かす代償がある。「等コスト」というラベルだけでは、どちらを受け入れるべきか決められない。

出典