CSMA/CDのバックオフアルゴリズムを解説！衝突解決の仕組みと待ち時間の計算式

バックオフアルゴリズム（Back Off Algorithm）とは

バックオフアルゴリズムは、CSMA/CD（Carrier Sense Multiple Access with Collision Detection）方式において、伝送路上で発生したデータの衝突（コリジョン）を解決するためのアルゴリズムです。

複数の端末が同時に信号を送信し、衝突が発生すると、各デバイスはランダムな時間だけ待機してから再送信を行います。この待機と再送信のプロセスは、データが正常に転送されるまで繰り返されます。

「バックオフ」と呼ばれるのは、ノードが再び送信を試みる前に、一定時間「後ろに下がって（back-off）」待機するためです。ここで重要なポイントは、待機するランダム時間が、送信を試みた回数に比例して増加するという点です。試行回数が増えるほど待ち時間の範囲も広がり、再衝突の可能性が抑えられます。

アルゴリズムの流れ

以下のフローチャートは、バックオフアルゴリズムの動作を簡潔に示したものです。

図のように、衝突が発生するたびに試行回数 n が1ずつ増加し、それに伴って乱数を選ぶ範囲 [0, 2ⁿ-1] も拡大していきます。これにより、同じスロットを選んでしまう確率、すなわち衝突の発生確率が徐々に低下していきます。

一方で、この仕組みには欠点もあります。衝突が連続して発生するとバックオフ時間がどんどん長くなり、最大試行回数の上限に達したノードはパケットを破棄せざるを得なくなる場合があります。これは輻輳状態にあるネットワークでは特に深刻な問題となります。

待ち時間の計算式

衝突検出後、各ノードは次の式で求められる時間だけ送信を待機します。

Waiting time = K × Tslot

それぞれの要素は以下の通りです。

• T_slot：離散的なタイムスロット。長さは 2t であり、t はネットワーク内の最大伝搬遅延時間を表します。
• K：範囲 [0, 2ⁿ-1] からランダムに選ばれる整数。n は衝突が発生した回数（コンテンション番号）です。

例えば、初回の衝突（n=1）なら K は 0 または 1 のいずれかですが、衝突を重ねるごとに選択肢が倍々に増えていくため、長期的には公平性を保ちながら衝突を回避できるのがこのアルゴリズムの特徴です。この方式は「二進指数バックオフ（Binary Exponential Backoff）」とも呼ばれ、イーサネットなどのLAN規格で広く採用されています。