C LANGUAGE TECHNOLOGY

【C言語】ARQ(Automatic Repeat-reQuest)プロトコル【Stop-and-Wait,Go-Back-N,Selective Repeat】

2022年7月23日

悩んでいる人

C言語でARQプロトコルを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

ARQ(Automatic Repeat-reQuest)プロトコル

ARQ(Automatic Repeat-reQuest)プロトコルとは,信頼性の高いデータ通信を達成するために,送達確認とタイムアウトを使う誤り制御手法による自動再送要求プロトコルです.

送達確認(acknowledgement)とは,受信側が送信側に対してデータフレームを正しく受信したことを通知するメッセージを送ることです.

タイムアウト(timeout)とは,送信側がデータフレームを送信してから妥当なある時間(本記事のコードでは3秒)が経った時点を指します.

送信側がそれまでに送達確認を受信できない場合,通常同じデータフレームを再送し,送達確認を受信するか再送回数が既定回数になるまで再送を繰り返します.

ARQプロトコルの種類として以下が挙げられますので,それぞれ解説していきます.

  • Stop-and-Wait ARQプロトコル
  • Go-Back-N ARQプロトコル
  • Selective Repeat ARQプロトコル

Stop-and-Waitプロトコル

まずは従来のStop-and-Waitプロトコル(ARQではない)を解説します.

送信側は1度に1つのフレームを送ります.

フレームを送った後,送信側はACKを受信するまで次のフレームを送りません.

受信側はフレームの受信に成功するとACKを送信します.

Stop-and-Waitプロトコルの問題は,信頼性が低い通信路の影響でACKが送信側に届かない場合,送信側はACKを無限に待ってしまうことです.

Stop-and-Waitプロトコルの解説動画はこちらです.

Stop-and-Waitプロトコルのコード一式はこちらです.

解凍して以下のコマンドでコンパイルして下さい.

Stop-and-Waitプロトコルのクライアントとサーバのコードは以下になります.

実行方法を紹介します.

まずはサーバを実行します.

次に別の端末でクライアントを実行します.

もう一度サーバの端末をみると,以下の結果になります.

Stop-and-Wait ARQプロトコル

Stop-and-Wait ARQプロトコルは,シンプルなARQです.

送信側は1度に1つのフレームを送ります.

フレームを送った後,送信側はACKを受信するまで次のフレームを送りません.

受信側はフレームの受信に成功するとACKを送信します.

ACKがある一定時間以内に送信側に届かない場合をタイムアウトと呼び,送信側は同じフレームを再送します.

このARQにより,信頼性が低い通信路でもStop-and-Wait ARQプロトコルは正常に通信ができます.

Stop-and-Wait ARQプロトコルの問題は,フレームを送信するたびにACK受信を待つ必要があり,後述するGo-Back-N ARQプロトコルやSelective Repeat ARQプロトコルと比較して,スループットが低いことです.

Stop-and-Wait ARQプロトコルの解説動画はこちらです.

Stop-and-Wait ARQプロトコルのコード一式はこちらです.

解凍して以下のコマンドでコンパイルして下さい.

Stop-and-Wait ARQプロトコルのクライアントとサーバのコードは以下になります.

実行方法を紹介します.

まずはサーバを実行します.

次に別の端末でクライアントを実行します.

もう一度サーバの端末をみると,以下の結果になります.

Go-Back-N ARQプロトコル

Go-Back-N ARQプロトコルは,個々のフレームについてACKパケットが受信側から送信側に届かなくても,送信側は「ウィンドウサイズ」までのデータフレームを送信し続けるARQプロトコルです.

受信側はデータフレームのシーケンス番号を確認し,ACKにその番号を付与して送信します.

期待したシーケンス番号でないフレームは受信側で無視します(フレーム順序が乱れたらACKを返しません).

送信側はウィンドウ上限までの全フレームを送信すると,最も後に受信したACKのシーケンス番号まで送信完了したと判断し,その次のフレームから次のウィンドウの送信を開始します.

Go-Back-N ARQプロトコルはStop-and-wait ARQプロトコルのように毎回ACK受信を待たないので,コネクション効率が高く常にパケットを送信し続けます.

Go-Back-N ARQプロトコルでは問題が発生したときフレームを複数回送信することになり,しかも問題発生箇所以降の全フレームを再送することになります.

Go-Back-N ARQプロトコルで利用するウィンドウサイズをスライドする「Sliding Windowプロトコル」の解説動画はこちらです.

Go-Back-N ARQプロトコルの解説動画はこちらです.

Go-Back-N ARQプロトコルのコード一式はこちらです.

解凍して以下のコマンドでコンパイルして下さい.

Go-Back-N ARQプロトコルのクライアントとサーバのコードは以下になります.

実行方法を紹介します.

まずはサーバを実行します.

次に別の端末でクライアントを実行します.

もう一度サーバの端末をみると,以下の結果になります.

Selective Repeat ARQプロトコル

Selective Repeat ARQプロトコルは,Go-Back-N ARQプロトコルに似ていますが,途中でフレームが失われても,送信側はウィンドウサイズの分だけフレームを送信し,受信側はエラーが起きてもフレームを受信し続けます.

Go-Back-N ARQプロトコルとは異なり,Selective Repeat ARQプロトコルは受信できなかったフレームのみ再送するのでスループットを向上することができます.

また,Go-Back-N ARQプロトコルと同様にウィンドウサイズのスライドにはSliding Windowプロトコルを利用します.

Selective Repeat ARQプロトコルの解説動画はこちらです.

Selective Repeat ARQプロトコルのコード一式はこちらです.

解凍して以下のコマンドでコンパイルして下さい.

Selective Repeat ARQプロトコルのクライアントとサーバのコードは以下になります.

実行方法を紹介します.

まずはサーバを実行します.

次に別の端末でクライアントを実行します.

もう一度サーバの端末をみると,以下の結果になります.

Hybrid ARQ(HARQ)プロトコル

Hybrid ARQ(HARQ)プロトコルは,高レートな前方エラー訂正(FEC:Forward Error Correction)とARQの誤り制御を組み合わせたプロトコルです.

FECの例としてリード・ソロモン符号,BCH符号が挙げられます.

FECの符号を実装したエラー検出訂正符号ライブラリを知りたいあなたはこちらからどうぞ.

HARQプロトコルの解説動画はこちらです.

まとめ

C言語でARQプロトコルを紹介しました.

具体的には,Stop-and-Wait ARQプロトコル(ARQではないプロトコルを含む),Go-Back-N ARQプロトコル,Selective Repeat ARQプロトコルを解説しました.

また,ARQプロトコルの応用例としてHARQプロトコルを紹介しました.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , ,