要約

  • 実験期の共有Ethernetで衝突が示したのは、複数端末が脆弱な時間窓内に送信したことだけだった。競争相手の身元も、順番待ちの列も、次スロットの予約も示さない。
  • 送信側コントローラーは破損した送信を止め、衝突回数を更新し、各自でランダムな再送間隔を選んだ。衝突が重なるほど平均待ち時間を広げ、途中のフレームには道を譲った。
  • Robert MetcalfeとDavid Boggsが描いた分散制御には協力も必要だった。乱数は再衝突の同期を崩すが、公平、配送、飢餓の不存在を保証するものではない。

ケーブルが確定した事実

一方の端末がキャリアを検出せず送信を始める。その信号が遠端へ届く前に、もう一方も空きと判断して送信する。波形が重なり、各コントローラーは自分が送り出した値とケーブル上の値の違いを検出する。現在のフレームは壊れているため中止する。

ここで確定したのは、伝搬遅延で区切られた時間内に試行が重なったという小さな事実である。衝突には相手のアドレスが書かれていない。絶対時刻上の先着者も決めない。早く検出した端末へ次の権利を移す機能もない。共有媒体は証人であって、調停者ではなかった。

1976年のMetcalfeとBoggsの論文は、Ethernetを放送型の多元接続チャネルであり、端末が分散制御する仕組みとして記述した。分散は無規則を意味しない。検知、中断、再試行の手順は共通である。一方、次にいつ動くかはローカルな判断として残る。

したがって衝突カウンターを、順番を待つ敗者の台帳として読んではならない。十回の衝突が十台の相手を意味するとは限らず、回数が少ないことも優遇の証拠ではない。どの衝突ドメインで、どの時間条件の下に起きたかが必要になる。

スロットの成功と配送の成功

原論文では、送信開始から衝突を発見できる最長時間、すなわち共有媒体の端から端までの往復伝搬遅延がスロットの境界になる。負荷時のスロットは、誰も試さない空き、複数が試す衝突、ただ一台が試す媒体獲得の三つに分かれる。

媒体獲得は、そのフレームを送り終える機会でしかない。次のスロットを予約しない。受信側の検査通過やアプリケーション処理も証明しない。論文はEthernetを確率的と呼び、干渉、雑音、受信機の停止、意図的破棄による損失を認めている。上位プロトコルは高い確率での受信を前提にしつつ、必要な確認を別に持たなければならない。

証拠も三段に分けるべきだ。送信側が媒体を得て送信を完了した。受信側がフレームを検証した。アプリケーションが処理を認めた。第一段のログを第三段の結果として扱えば、根拠のない確実性になる。

同じ未来を選ばないための乱数

衝突後、送信コントローラーは衝突回数を更新し、新しい再送間隔をランダムに生成する。MetcalfeとBoggsは、衝突のたびに平均遅延を二倍にし、待機中に別のフレームが通ればそれに譲ってから再試行すると説明した。論文はこの手法をBinary Exponential Backoffの発見的近似と位置づける。

目的は単に遅くすることではない。同時に同じ判断をした端末どうしの相関を切ることである。固定時間だけ待てば、二台は再び同時に動きやすい。独立した選択は多くの場合に両者を分け、競争が続くほど選択範囲を広げることで同一点への集中を減らす。

1997年のIEEE 802.3解釈文書は、後の切り詰め二進指数バックオフを明示する。衝突とジャムの後、端末は整数個のスロット時間を一様に選び、指数は試行回数とともに上限まで増え、成功するか試行限界に達する。また端末間の乱数相関を最小化するよう求める。この規定を、1973年の試作機にも同じ定数がすべて存在したかのように遡及させるべきではない。

Metcalfeは口述史で、衝突検出の一部がハードウェア、指数バックオフがハードウェア支援付きマイクロコードにあったと振り返る。意思決定の置き場所を理解する資料ではあるが、公開アルゴリズムや中立的な性能測定の代わりではない。

協力しない端末を確率は止められない

1976年論文は、公平な共有には一定の協力が必要だと明記した。高負荷時にも再送間隔を広げない端末はEtherを奪える。非常に長いパケットを送り続けても、他者の機会を減らせる。実験システムはどちらも禁止した。

ケーブルが検出できるのは信号の重なりであり、乱数生成器の誠実さや実装者の動機ではない。公平性は乱数の性質だけでなく、パケット長の制約、規則への適合、端末別の遅延と取得結果によって評価される。

功績も一人へ集約できない。論文はMetcalfeとBoggsの共著で、特許はRobert M. Metcalfe、David R. Boggs、Charles P. Thacker、Butler W. Lampsonを発明者として記す。ALOHAnet、PARCの実装者、標準化参加者も系譜の一部である。ACMのチューリング賞はMetcalfeの発明、標準化、商用化を評価しながら、BoggsをPARC Ethernetの共同発明者としている。

現代のリンクへ衝突物語を持ち込まない

検証では、まず本当に共有半二重の衝突ドメインだったかを確定する。次にキャリア状態、送信開始、衝突検出と中止、試行回数、選んだ待ち値、途中フレームへの譲歩、再試行を結ぶ。最後に媒体獲得と受信検証、上位確認を別々に照合する。

この列は手順への適合を示せるが、全端末の乱数が独立だったこと、待ち時間が平等だったこと、飢餓がなかったことまでは示せない。分布の主張には端末別の長期観測が要る。配送の主張には受信側の証拠が要る。

現在のEthernetは通常、スイッチを介したポイントツーポイントの全二重リンクである。共有同軸上の競争は存在しない。全二重と想定した装置に衝突値が出たなら、古典的な仕組みの正常動作ではなく、媒体、カウンター定義、duplex mismatchを疑うのが先である。

出典