バックオフアルゴリズム（ばっくおふあるごりずむ）
最終更新：2026/4/25
バックオフアルゴリズムは、通信ネットワークにおいて、衝突が発生した場合に再送を試みるまでの待機時間をランダムに増加させることで、再衝突の確率を低減する手法である。
別名・同義語 衝突回避アルゴリズムランダムバックオフ
ポイント
主にCSMA/CDなどの多重アクセス方式で用いられ、ネットワークの効率的な利用を促進する。待機時間のランダム化により、複数の端末が同時に再送する事態を回避する。
概要
バックオフアルゴリズムは、複数の端末が同じ通信路を共有する環境において、データの衝突を回避し、ネットワークの効率を向上させるために用いられる。特に、イーサネットのCSMA/CD（Carrier Sense Multiple Access with Collision Detection）方式において重要な役割を果たす。
動作原理
バックオフアルゴリズムの基本的な動作は以下の通りである。
- 衝突検出: 端末がデータを送信中に衝突を検出すると、送信を中断する。
- ランダムな待機時間: 衝突を検出した端末は、0から2n-1までのランダムな整数nを生成し、nスロット時間だけ待機する（スロット時間は、フレーム送信時間など、ネットワークの特性によって定義される）。
- 再送: 待機時間が経過した後、再び通信路を検知し、空いている場合にデータを再送する。
このランダムな待機時間を導入することで、複数の端末が同時に再送する確率を低減し、再衝突を回避することができる。
バリエーション
バックオフアルゴリズムには、いくつかのバリエーションが存在する。
- 指数バックオフ: 衝突回数が増えるごとに、待機時間の範囲を指数関数的に増加させる手法。これにより、繰り返し衝突が発生する場合でも、再衝突の確率を効果的に低減できる。
- 切り捨て二項バックオフ: 待機時間を決定する際に、二項分布に基づいてランダムな値を生成する手法。指数バックオフよりも効率的な衝突回避が可能となる。
応用例
バックオフアルゴリズムは、イーサネット以外にも、無線LAN（IEEE 802.11）などの様々な通信規格で採用されている。また、分散システムにおける競合制御など、ネットワーク以外の分野でも応用されている。