自動再送要求

自動再送要求（じどうさいそうようきゅう、英: Automatic repeat-request, ARQ）は、信頼性の高いデータ通信を達成するために、送達確認とタイムアウトを使う誤り制御手法。自動再送制御とも。送達確認（acknowledgement）とは、受信側が送信側に対してデータフレームを正しく受信したことを通知するメッセージを送ることである。タイムアウト（timeout）とは、送信側がデータフレームを送信してから妥当なある時間が経った時点を指し、送信側がそれまでに送達確認を受信できない場合、通常同じデータフレームを再送し、送達確認を受信するか再送回数が既定回数になるまで再送を繰り返す。

ARQプロトコルの種類として、Stop-and-wait ARQ、Go-Back-N ARQ、Selective Repeat ARQ がある。

ARQ から派生したハイブリッドARQ (HARQ) は実装コストは増大するが性能が改善され、特に無線通信に適している。

Stop-and-wait ARQ

Stop-and-wait ARQ は、非常に単純な自動再送要求(ARQ)である。送信側は1度に1つのフレームを送る。フレームを送った後、送信側は ACK を受信するまで次のフレームを送らない。受信側はフレームの受信に成功すると ACK を送信する。ACK がある一定時間以内に送信側に届かない場合をタイムアウトと呼び、送信側は同じフレームを再送する。

このような実装を Stop-and-wait ARQ と呼ぶ。しかし、実際の実装ではいくつかの問題が生じる。

一般に送信機はフレームの末尾に冗長検査番号を付与する。受信機はその冗長検査番号を使ってフレームに破損がないか調べる。フレームに破損がないと判断した場合、受信機は ACK を送る。フレームに破損があると判断した場合、受信機はそのフレームを捨て、ACK を送らない。フレームに実際には破損がなくとも、そのフレームは完全に失われる。

問題は、ACK フレームが破損したり失われた場合である。この場合送信側はACKを受信しないのでタイムアウトとなり、フレームを再送する。受信側は同じフレームを2回受信することになるが、再送されたフレームが前のフレームと同じものかどうかは分からない（プロトコル上定義されていない）。

もう1つの問題は、転送媒体によっては受信側が送ったACKを受け取る前に送信側がタイムアウトするほどレイテンシが大きい場合である。この場合も送信側はフレームを再送し、受信側は同じフレームを2回受信することになる。送信側はACKを2回受け取ることになり、送信側の実装によってはタイムアウトしたと判断したフレームのACKと解釈できない場合があり、問題が生じる。

これらの問題を防ぐための最も一般的な解決策は、フレームのヘッダ部に1ビットのシーケンス番号を付与することである。このシーケンス番号は通常のフレームの順序に従って、1と0という値を交互にとる。受信側がACKを送るとき、次に受信したいフレームのシーケンス番号をACKフレームに含める。このようにすれば、受信側はシーケンス番号を調べることでフレームの重複を検出できる。続けて受信した2つのフレームのシーケンス番号が同じだった場合、これらは重複しており、2つめのフレームは捨てられる。同様に、続けて受信したACKに同じシーケンス番号がある場合、同じフレームへのACKであると判断できる。

Stop-and-wait ARQ は、フレームを送信するたびにACK受信を待つ必要があり、他の手法よりも非効率である。より効率化するには、複数のフレームを連続して送信し、それら全体に対してACKを返すようにすればよい。このような方式として Go-Back-N ARQ や Selective Repeat ARQ がある。

統計的分析

以下の方程式が妥当かどうかは簡単に示せる。

$\left\{{\begin{array}{l}t_{i}=i\cdot t_{G}\\P_{i}=p^{i}\cdot \left(1-p\right)\end{array}}\right.$

ここで

$t_{T}$ は、パケットを送信先まで送達させるのにかかる時間であり、必要な再送を全て含めた時間である。
$t_{i}$ は、 $i$ 回の再送を伴うフレーム送達にかかる時間である。
$t_{G}$ は、フレームを送信し、そのACKを受信するまでにかかる時間である。
$P_{i}$ は、フレーム送信に $i$ 回失敗する確率である。
$p$ は、フレーム送信を1回失敗する確率である。

これらの方程式から1つのフレームを Stop-and-wait ARQ 方式で送達させるのにかかる期待時間を計算すると、次のようになる。

$E\left[t_{T}\right]=t_{G}+\sum _{i=1}^{\infty }t_{i}\cdot P_{i}=t_{G}+t_{G}\cdot \left(1-p\right)\cdot \sum _{i=1}^{\infty }i\cdot p^{i}=t_{G}\cdot \left(1+{\frac {p}{1-p}}\right)$

この期待時間を使って、利用係数と効率を求めることができる。

\rho ={\frac {t_{F}}{E\left[t_{T}\right]}}={\frac {t_{F}\cdot \left(1-p\right)}{t_{F}+t_{O}}}

\eta ={\frac {t_{I}}{E\left[t_{T}\right]}}=\rho \cdot {\frac {t_{I}}{t_{F}}}

ここで

$t_{I}$ は、情報ビット列のみを送達させるのにかかる時間である。
$t_{O}$ は、タイムアウト時間である。
$t_{F}$ は、パケットの送信（成功か失敗かは問わない）にかかる時間である。

Go-Back-N ARQ

Go-Back-N ARQ は、自動再送要求（ARQ）プロトコルの実装の1つ。個々のフレームについてACKパケットが受信側から送信側に届かなくても、送信側は「ウィンドウサイズ」までのデータフレームを送信し続ける。

受信側はデータフレームのシーケンス番号を確認し、ACKにその番号を付与して送信する。期待したシーケンス番号でないフレームは受信側で無視する（フレーム順序が乱れたらACKを返さない）。送信側はウィンドウ上限までの全フレームを送信すると、最も後に受信したACKのシーケンス番号まで送信完了したと判断し、その次のフレームから次のウィンドウの送信を開始する。

ウィンドウサイズはシーケンス番号の最大値より小さくする必要がある。それによってパケットの転送失敗を検出できる。^[1]

Go-Back-N ARQ は Stop-and-wait ARQ のように毎回ACK受信を待たないので、コネクション効率が高く常にパケットを送信し続ける。しかし、問題が発生したときフレームを複数回送信することになり、しかも問題発生箇所以降の全フレームを再送することになる。このような無駄を防ぐ手法として、Selective Repeat ARQ が使われる^[1]。

Selective Repeat ARQ

Selective Repeat ARQ は、自動再送要求（ARQ）プロトコルの実装の1つ。Go-Back-N ARQ に似ているが、途中でフレームが失われても、送信側はウィンドウサイズのぶんだけフレームを送信し、受信側はエラーが起きてもフレームを受信し続ける。

メッセージ列の送受信の場合、受信側は受信できなかったフレームのシーケンス番号を覚えておき、その後のACK送信時にそのシーケンス番号を付与する。送信側からのフレームが受信側に届かなかった場合でも、送信側はウィンドウのぶんだけのフレームを送信し続ける。受信側は、受信ウィンドウが一杯になるまでフレーム受信を続け、個々のフレームに対して受信できなかったフレームのシーケンス番号を付与したACKを返す。送信ウィンドウの全フレームを送信し終えたら、送信側はACKに示された番号のフレームを再送する。

送信ウィンドウと受信ウィンドウは同じ大きさでなければならず、間違いが発生しないようシーケンス番号の最大値はウィンドウサイズの2倍以上でなければならない。対応するACKを受信した場合、送信側は送信ウィンドウをそのぶんだけずらす^[1]。

メッセージを分割転送する場合、若干異なった方式となる。メッセージ長が一定でない非継続的伝送路では、通常のARQプロトコルやハイブリッドARQはメッセージを単一ユニットとして扱うことがある。一方選択的再送は、メッセージを固定長のフレームに分割してから基本的ARQ機構と共に使われることがある。従って、元の可変長メッセージは可変個のサブブロックを連結することで表される。標準ARQでは、メッセージ全体に対して、ACK または NAK が返されるが、選択的転送を伴うARQでは、個々のサブブロック（フレーム）毎にACKまたはNAKが返される。この場合、再送されるのは ACK が返されなかったサブブロックのみとなる。

可変長メッセージを扱う多くの伝送路モデルでは、メッセージ長と受信成功確率は反比例する。つまり、短いメッセージの方が成功裡に受信しやすい。従って標準のARQ技法ではメッセージ長の増大と共に効率が悪くなっていく。メッセージの分割転送と Selective Repeat ARQ を使うことで、この問題を回避することが可能となる。

衛星通信のように遅延時間を少なくしなければいけない場面などに用いられることが多い。

脚注

^ ^a ^b ^c Tanenbaum, Andrew S. Computer Networks 4th ed. ISBN 0-13-066102-3

参考文献

Tanenbaum, Andrew S., Computer Networks, 4th ed. ISBN 0-13-066102-3
Peterson and Davie, Computer Networks: A Systems Approach, Third Edition, 2003
R.A.Comroe and D.J.Costello. "ARQ schemes for data transmission in mobile radio systems". IEEE J. Select. Areas Commun., 2:472-481, July 1984.

外部リンク

Go-Back-N ARQ demonstration in a Java applet
Selective Repeat Protocol Javaアプレットによるデモ
Selective Repeat Applet Javaアプレットによるデモ

[Tanenbaum-1] Tanenbaum, Andrew S. Computer Networks 4th ed. ISBN 0-13-066102-3

[1]