Stop-and-wait ARQとは? わかりやすく解説

自動再送要求

(Stop-and-wait ARQ から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/01/24 01:56 UTC 版)

ナビゲーションに移動 検索に移動

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

ARQプロトコルの種類として、Stop-and-wait ARQGo-Back-N ARQSelective 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 がある。

統計的分析

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

ここで

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

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

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

ここで

  • は、情報ビット列のみを送達させるのにかかる時間である。
  • は、タイムアウト時間である。
  • は、パケットの送信(成功か失敗かは問わない)にかかる時間である。

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 を使うことで、この問題を回避することが可能となる。

脚注

  1. ^ 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.

外部リンク


Stop-and-wait ARQ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/12/25 02:55 UTC 版)

自動再送要求」の記事における「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 ARQSelective Repeat ARQ がある。

※この「Stop-and-wait ARQ」の解説は、「自動再送要求」の解説の一部です。
「Stop-and-wait ARQ」を含む「自動再送要求」の記事については、「自動再送要求」の概要を参照ください。

ウィキペディア小見出し辞書の「Stop-and-wait ARQ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

Stop-and-wait ARQのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Stop-and-wait ARQのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの自動再送要求 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの自動再送要求 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS