__特___集__
Ethernet の再送処理 - バックオフアルゴリズム
Ethernet では、自分が送信したフレームがコリジョンに遭遇すると、ランダムに生成した待ち時間が経過した後、フレームの再送信を試みます。待ち時間を生成するための計算式を、Truncated Exponential Backoff Algorithm と呼びます。
このアルゴリズムで算出される待ち時間は、必ず、スロットタイム(512BT) のn倍となります。
0 <= n < 2^k (2のk乗)
n --- 0 以上 2^k 未満
k --- Frame 再送信回数(1 〜 10)
n --- 0 以上 2^k 未満
k --- Frame 再送信回数(1 〜 10)
k に再送信回数が代入されるのは1 〜10 までで、11回目以降16回目までは10 が代入されます。
つまり、再送待ち時間は最長52.4 ミリ秒( ＝ 2^10 * 512BT)となります。
送信中のフレームがコリジョンに遭遇すると（1回目）、0 〜 2^1 -1 の中からランダムにバックオフタイムが選択されます(0 もしくは 1)。
0 --- 512BT * 0 = 0BT = 0 second
1 --- 512BT * 1 = 512BT = 51.2 usec
1 --- 512BT * 1 = 512BT = 51.2 usec
10Mbps の場合、1が選択されると、51.2マイクロ秒の待ち時間が経過した後、フレームの再送信を試みます。
0が選択された場合は、待ち時間無しで再送を試みます。
2回目の送信がコリジョンに遭遇すると、0 〜2^2 -1 の中からランダムに、バックオフタイムが選択されます(0/1/2/3)。
0 --- 512BT * 0 = 0BT = 0 second
1 --- 512BT * 1 = 512BT = 51.2 usec
2 --- 512BT * 2 = 1024BT = 102.4 usec
3 --- 512BT * 3 = 1536BT = 153.6 usec
1 --- 512BT * 1 = 512BT = 51.2 usec
2 --- 512BT * 2 = 1024BT = 102.4 usec
3 --- 512BT * 3 = 1536BT = 153.6 usec
| 再送回数(k) |
n=0〜2^k-1 |
最大待ち時間 (n * 512BT) |
|---|---|---|
| 1 | 1 | 512 |
| 2 | 3 | 1536 |
| 3 | 7 | 3584 |
| 4 | 15 | 7680 |
| 5 | 31 | 15872 |
| 6 | 63 | 32256 |
| 7 | 127 | 65024 |
| 8 | 255 | 130560 |
| 9 | 511 | 261632 |
| 10 | 1023 | 523766 |
| 11 | 1023 | 523766 |
| 12 | 1023 | 523766 |
| 13 | 1023 | 523766 |
| 14 | 1023 | 523766 |
| 15 | 1023 | 523766 |
| 16 | N/A | フレーム破棄 |
再送は15回まで可能です。
16回目の再送が発生すると、端末はフレームを破棄し、再送回数カウンタを初期化した後、以後の処理を上位層に委ねます。
n は、コリジョンに遭遇した端末が想定する、コリジョンドメイン内の端末数を意味します。
初めてコリジョンに遭遇すると、端末はコリジョンドメインに、自分以外に1台端末が存在すると想定します。
2回目は3台、3回目は7台、とExponential(指数関数的)に想定端末数を増加させて行きます。
想定端末数が1023 に達すると(再送回数が10回に達すると)、以後は想定端末数は増加しません。 この1023 に、自分自身を足した1024が、コリジョンドメインに存在可能な最大端末数です。
ネットワークエンジニアになろう！のトップページへ戻る
