悩んでいる人
C言語でARQプロトコルを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/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プロトコルのコード一式はこちらです．
解凍して以下のコマンドでコンパイルして下さい．
|
1 2 3 4 5 |
$ unzip stop_and_wait.zip $ cd stop_and_wait $ make gcc -o stop_and_wait_client stop_and_wait_client.c -Wall gcc -o stop_and_wait_server stop_and_wait_server.c -Wall |
Stop-and-Waitプロトコルのクライアントとサーバのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <unistd.h> #include <arpa/inet.h> #define PORT 65432 #define MAX_SEQ_ID 10 #define BUFSIZE 128 #define ACK "ACK" int main(void) { int sock; int i, n; struct sockaddr_in client; char buf[BUFSIZE]; if ((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&client, 0, sizeof(client)); client.sin_family = AF_INET; client.sin_port = htons(PORT); client.sin_addr.s_addr = inet_addr("127.0.0.1"); if (connect(sock, (struct sockaddr *) &client, sizeof(client)) == -1) { perror("connect"); goto end; } for (i = 0; i <= MAX_SEQ_ID; i++) { memset(buf, 0, sizeof(buf)); sprintf(buf, "%d", i); printf("Message to server: %s\n", buf); if (write(sock, buf, strlen(buf)) == -1) { perror("write"); goto end; } if ((n = read(sock, buf, sizeof(buf))) == -1) { perror("read"); goto end; } buf[n] = '\0'; printf("Message from server: %s\n", buf); if (strcmp(buf, ACK) != 0) { fprintf(stderr, "Error: message is not ACK\n"); goto end; } usleep(1000); } end: if (close(sock) == -1) { perror("close"); exit(2); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <unistd.h> #include <arpa/inet.h> #define PORT 65432 #define MAX_SEQ_ID 10 #define BACKLOG 1024 #define BUFSIZE 128 #define ACK "ACK" int main(void) { int s_sock, c_sock; struct sockaddr_in server, other; socklen_t add; char buf[BUFSIZE]; int i, n; if ((s_sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&server, 0, sizeof(server)); memset(&other, 0, sizeof(other)); server.sin_family = AF_INET; server.sin_port = htons(PORT); server.sin_addr.s_addr = INADDR_ANY; if (bind(s_sock, (struct sockaddr *) &server, sizeof(server)) == -1) { perror("bind"); goto end; } if (listen(s_sock, BACKLOG) == -1) { perror("listen"); goto end; } add = sizeof(other); if ((c_sock = accept(s_sock, (struct sockaddr *) &other, &add)) == -1) { perror("accept"); goto end; } for (i = 0; i <= MAX_SEQ_ID; i++) { memset(buf, 0, sizeof(buf)); if ((n = read(c_sock, buf, sizeof(buf))) == -1) { perror("read"); goto end2; } printf("Message from client: %s\n", buf); if (write(c_sock, ACK, sizeof(ACK)) == -1) { perror("write"); goto end2; } usleep(1000); } end2: if (close(c_sock) == -1) { perror("close"); exit(2); } end: if (close(s_sock) == -1) { perror("close"); exit(3); } return 0; } |
実行方法を紹介します．
まずはサーバを実行します．
|
1 |
$ ./stop_and_wait_server |
次に別の端末でクライアントを実行します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
$ ./stop_and_wait_client Message to server: 0 Message from server: ACK Message to server: 1 Message from server: ACK Message to server: 2 Message from server: ACK Message to server: 3 Message from server: ACK Message to server: 4 Message from server: ACK Message to server: 5 Message from server: ACK Message to server: 6 Message from server: ACK Message to server: 7 Message from server: ACK Message to server: 8 Message from server: ACK Message to server: 9 Message from server: ACK Message to server: 10 Message from server: ACK |
もう一度サーバの端末をみると，以下の結果になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 |
$ ./stop_and_wait_server Message from client: 0 Message from client: 1 Message from client: 2 Message from client: 3 Message from client: 4 Message from client: 5 Message from client: 6 Message from client: 7 Message from client: 8 Message from client: 9 Message from client: 10 |
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プロトコルのコード一式はこちらです．
解凍して以下のコマンドでコンパイルして下さい．
|
1 2 3 4 5 |
$ unzip stop_and_wait_arq.zip $ cd stop_and_wait_arq $ make gcc -o stop_and_wait_arq_client stop_and_wait_arq_client.c -Wall gcc -o stop_and_wait_arq_server stop_and_wait_arq_server.c -Wall |
Stop-and-Wait ARQプロトコルのクライアントとサーバのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <sys/time.h> #include <sys/wait.h> #include <unistd.h> #include <arpa/inet.h> #define PORT 65432 #define MAX_SEQ_ID 10 #define BUFSIZE 128 #define ACK "ACK" #define TIMEOUT_SEC 3 int main(void) { int sock; struct sockaddr_in client; char buf[BUFSIZE]; int i, n; int ret; fd_set set; struct timeval timeout; if ((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&client, 0, sizeof(client)); client.sin_family = AF_INET; client.sin_port = htons(PORT); client.sin_addr.s_addr = inet_addr("127.0.0.1"); if (connect(sock, (struct sockaddr *) &client, sizeof(client)) == -1) { perror("connect"); goto end; } for (i = 0; i <= MAX_SEQ_ID; i++) { resend: memset(buf, 0, sizeof(buf)); sprintf(buf, "%d", i); printf("Message to server: %s\n", buf); if (write(sock, buf, sizeof(buf)) == -1) { perror("write"); goto end; } FD_ZERO(&set); FD_SET(sock, &set); timeout.tv_sec = TIMEOUT_SEC; timeout.tv_usec = 0; if ((ret = select(sock + 1, &set, NULL, NULL, &timeout)) == -1) { perror("select"); goto end; } else if (ret == 0) { printf("\n[Resend message]\n"); goto resend; } else { if ((n = read(sock, buf, sizeof(buf))) == -1) { perror("read"); goto end; } } buf[n] = '\0'; if (strcmp(buf, ACK) != 0) { printf("\nACK problem %s\n", buf); goto resend; } } end: if (close(sock) == -1) { perror("close"); exit(2); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <sys/socket.h> #include <sys/types.h> #include <sys/time.h> #include <netinet/in.h> #include <unistd.h> #include <arpa/inet.h> #include <fcntl.h> #define PORT 65432 #define BUFSIZE 128 #define BACKLOG 1024 #define MAX_SEQ_ID 10 #define ACK "ACK" #define NAK "NAK" #define DISCARD_ID 6 #define NAK_ID 8 int main(void) { int s_sock, c_sock; struct sockaddr_in server, other; socklen_t other_size; char buf[BUFSIZE], buf2[BUFSIZE]; bool discard_flag, nak_flag; int i, n; if ((s_sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&server, 0, sizeof(server)); memset(&other, 0, sizeof(other)); server.sin_family = AF_INET; server.sin_port = htons(PORT); server.sin_addr.s_addr = INADDR_ANY; if (bind(s_sock, (struct sockaddr *) &server, sizeof(server)) == -1) { perror("bind"); goto end; } if (listen(s_sock, BACKLOG) == -1) { perror("listen"); goto end; } other_size = sizeof(other); if ((c_sock = accept(s_sock, (struct sockaddr *) &other, &other_size)) == -1) { perror("accept"); goto end; } discard_flag = nak_flag = true; for (i = 0; i <= MAX_SEQ_ID; i++) { memset(buf, 0, sizeof(buf)); if ((n = read(c_sock, buf, sizeof(buf))) == -1) { perror("read"); goto end2; } buf[n] = '\0'; sprintf(buf2, "%d", i); if (i == DISCARD_ID && discard_flag) { discard_flag = false; printf("\n[Discard packet]\n"); i--; continue; } printf("Message from client: %s\n", buf); if (i == NAK_ID && nak_flag) { nak_flag = false; i--; if (write(c_sock, NAK, sizeof(NAK)) == -1) { perror("write"); goto end2; } } else { if (write(c_sock, ACK, sizeof(ACK)) == -1) { perror("write"); goto end2; } } } end2: if (close(c_sock) == -1) { perror("close"); exit(2); } end: if (close(s_sock) == -1) { perror("close"); exit(3); } return 0; } |
実行方法を紹介します．
まずはサーバを実行します．
|
1 |
$ ./stop_and_wait_arq_server |
次に別の端末でクライアントを実行します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
./stop_and_wait_arq_client Message to server: 0 Message to server: 1 Message to server: 2 Message to server: 3 Message to server: 4 Message to server: 5 Message to server: 6 [Resend message] Message to server: 6 Message to server: 7 Message to server: 8 ACK problem NAK Message to server: 8 Message to server: 9 Message to server: 10 |
もう一度サーバの端末をみると，以下の結果になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
$ ./stop_and_wait_arq_server Message from client: 0 Message from client: 1 Message from client: 2 Message from client: 3 Message from client: 4 Message from client: 5 [Discard packet] Message from client: 6 Message from client: 7 Message from client: 8 Message from client: 8 Message from client: 9 Message from client: 10 |
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プロトコルのコード一式はこちらです．
解凍して以下のコマンドでコンパイルして下さい．
|
1 2 3 4 5 |
$ unzip go_back_n_arq.zip $ cd go_back_n_arq $ make gcc -o go_back_n_arq_client go_back_n_arq_client.c -Wall gcc -o go_back_n_arq_server go_back_n_arq_server.c -Wall |
Go-Back-N ARQプロトコルのクライアントとサーバのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <sys/time.h> #include <sys/wait.h> #include <unistd.h> #include <arpa/inet.h> #define PORT 65432 #define MAX_SEQ_ID 10 #define BUFSIZE 128 #define TIMEOUT_SEC 3 #define N 4 #define ACK "ACK" int main(void) { int sock; struct sockaddr_in client; struct timeval timeout; fd_set set; int ret; char buf[BUFSIZE], buf2[BUFSIZE]; int i, j, n; int window_ack_index; if ((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&client, 0, sizeof(client)); client.sin_family = AF_INET; client.sin_port = htons(PORT); client.sin_addr.s_addr = inet_addr("127.0.0.1"); if (connect(sock, (struct sockaddr *) &client, sizeof(client)) == -1) { perror("connect"); goto end; } for (i = 0; i <= MAX_SEQ_ID; i += window_ack_index) { window_ack_index = 0; for (j = i; j < i + N && j <= MAX_SEQ_ID; j++) { memset(buf, 0, sizeof(buf)); sprintf(buf, "%d", j); printf("Message to server: %s\n", buf); if (write(sock, buf, sizeof(buf)) == -1) { perror("write"); goto end; } usleep(1000); } for (j = i; j < i + N && j <= MAX_SEQ_ID; j++) { FD_ZERO(&set); FD_SET(sock, &set); timeout.tv_sec = TIMEOUT_SEC; timeout.tv_usec = 0; if ((ret = select(sock + 1, &set, NULL, NULL, &timeout)) == -1) { perror("select"); goto end; } else if (ret == 0) { printf("Going back from %d: timeout\n", i); break; } else { if ((n = read(sock, buf, sizeof(buf))) == -1) { perror("read"); goto end; } buf[n] = '\0'; printf("Message from server: %s\n", buf); sprintf(buf2, "%s%d", ACK, i + window_ack_index); if (strcmp(buf, buf2) == 0) { window_ack_index++; } else { break; } } } } end: if (close(sock) == -1) { perror("close"); exit(2); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <sys/socket.h> #include <sys/types.h> #include <sys/time.h> #include <netinet/in.h> #include <unistd.h> #include <arpa/inet.h> #include <fcntl.h> #define PORT 65432 #define MAX_SEQ_ID 10 #define BACKLOG 1024 #define BUFSIZE 128 #define ACK "ACK" #define DISCARD_ID 5 int main(void) { int s_sock, c_sock; struct sockaddr_in server, other; socklen_t other_size; int i, j, n; char buf[BUFSIZE]; bool flag = true; if ((s_sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&server, 0, sizeof(server)); memset(&other, 0, sizeof(other)); server.sin_family = AF_INET; server.sin_port = htons(PORT); server.sin_addr.s_addr = INADDR_ANY; if (bind(s_sock, (struct sockaddr *) &server, sizeof(server)) == -1) { perror("bind"); goto end; } if (listen(s_sock, BACKLOG) == -1) { perror("listen"); goto end; } other_size = sizeof(other); if ((c_sock = accept(s_sock, (struct sockaddr *) &other, &other_size)) == -1) { perror("accept"); goto end; } for (i = 0; i <= MAX_SEQ_ID; i++) { memset(buf, 0, sizeof(buf)); if (i == DISCARD_ID && flag) { printf("i = %d: [Simulation loss]\n", i); flag = false; if (read(c_sock, buf, sizeof(buf)) == -1) { perror("read"); goto end2; } } if ((n = read(c_sock, buf, sizeof(buf))) == -1) { perror("read"); goto end2; } buf[n] = '\0'; printf("Message from client: %s\n", buf); j = atoi(buf); if (j != i) { printf("Discarded as out of order\n"); i--; } else { memset(buf, 0, sizeof(buf)); sprintf(buf, "%s%d", ACK, i); printf("Message to client: %s\n", buf); if (write(c_sock, buf, sizeof(buf)) == -1) { perror("write"); goto end2; } } } end2: if (close(c_sock) == -1) { perror("close"); exit(2); } end: if (close(s_sock) == -1) { perror("close"); exit(3); } return 0; } |
実行方法を紹介します．
まずはサーバを実行します．
|
1 |
$ ./go_back_n_arq_server |
次に別の端末でクライアントを実行します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
$ ./go_back_n_arq_client Message to server: 0 Message to server: 1 Message to server: 2 Message to server: 3 Message from server: ACK0 Message from server: ACK1 Message from server: ACK2 Message from server: ACK3 Message to server: 4 Message to server: 5 Message to server: 6 Message to server: 7 Message from server: ACK4 Going back from 4: timeout Message to server: 5 Message to server: 6 Message to server: 7 Message to server: 8 Message from server: ACK5 Message from server: ACK6 Message from server: ACK7 Message from server: ACK8 Message to server: 9 Message to server: 10 Message from server: ACK9 Message from server: ACK10 |
もう一度サーバの端末をみると，以下の結果になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
$ ./go_back_n_arq_server Message from client: 0 Message to client: ACK0 Message from client: 1 Message to client: ACK1 Message from client: 2 Message to client: ACK2 Message from client: 3 Message to client: ACK3 Message from client: 4 Message to client: ACK4 i = 5: [Simulation loss] Message from client: 6 Discarded as out of order Message from client: 7 Discarded as out of order Message from client: 5 Message to client: ACK5 Message from client: 6 Message to client: ACK6 Message from client: 7 Message to client: ACK7 Message from client: 8 Message to client: ACK8 Message from client: 9 Message to client: ACK9 Message from client: 10 Message to client: ACK10 |
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プロトコルのコード一式はこちらです．
解凍して以下のコマンドでコンパイルして下さい．
|
1 2 3 4 5 |
$ unzip selective_repeat_arq.zip $ cd selective_repeat_arq $ make gcc -o selective_repeat_arq_client selective_repeat_arq_client.c -Wall gcc -o selective_repeat_arq_server selective_repeat_arq_server.c -Wall |
Selective Repeat ARQプロトコルのクライアントとサーバのコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <sys/time.h> #include <sys/wait.h> #include <string.h> #include <unistd.h> #include <arpa/inet.h> #define PORT 65432 #define BUFSIZE 128 #define MAX_SEQ_ID 10 #define ACK "ACK" #define TIMEOUT_SEC 3 #define N 4 int do_write(int sock, int id) { char buf[BUFSIZE]; memset(buf, 0, sizeof(buf)); sprintf(buf, "%d", id); printf("Message to server: %s\n", buf); return write(sock, buf, sizeof(buf)); } int main(void) { int sock; fd_set set; struct sockaddr_in client; char buf[BUFSIZE]; struct timeval timeout; int ret; int i, j, n; int total = 0; int current_index; if ((sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&client, 0, sizeof(client)); client.sin_family = AF_INET; client.sin_port = htons(PORT); client.sin_addr.s_addr = inet_addr("127.0.0.1"); if (connect(sock, (struct sockaddr *) &client, sizeof(client)) == -1) { perror("connect"); goto end; } while (total <= MAX_SEQ_ID) { current_index = total; for (i = current_index; i < current_index + N && i <= MAX_SEQ_ID; i++) { if (do_write(sock, i) == -1) { perror("write"); goto end; } usleep(1000); } for (i = current_index; i < current_index + N; i++) { resend: FD_ZERO(&set); FD_SET(sock, &set); timeout.tv_sec = TIMEOUT_SEC; timeout.tv_usec = 0; if ((ret = select(sock + 1, &set, NULL, NULL, &timeout)) == -1) { perror("select"); goto end; } else if (ret == 0) { printf("Timeout for message: %d\n", i); if (do_write(sock, i) == -1) { perror("write"); goto end; } usleep(1000); goto resend; } else { if ((n = read(sock, buf, sizeof(buf))) == -1) { perror("read"); goto end; } else if (n == 0) { continue; } buf[n] = '\0'; printf("Message from server: %s\n", buf); if (strncmp(buf, ACK, strlen(ACK)) != 0) { j = atoi(buf + strlen(ACK)); printf("Corrupt message ACK%d\n", j); if (do_write(sock, j) == -1) { perror("write"); goto end; } usleep(1000); goto resend; } else { total++; } } } } end: if (close(sock) == -1) { perror("close"); exit(2); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #include <sys/socket.h> #include <sys/types.h> #include <sys/time.h> #include <netinet/in.h> #include <unistd.h> #include <arpa/inet.h> #include <fcntl.h> #define PORT 65432 #define BUFSIZE 128 #define BACKLOG 1024 #define ACK "ACK" #define NAK "NAK" #define MAX_SEQ_ID 10 #define DISCARD_ID 5 bool is_fault(void) { int d = rand() % 2; return d > 0; } int main(void) { int s_sock, c_sock; struct sockaddr_in server, other; socklen_t other_size; char buf[BUFSIZE]; bool flag = true; int i, n; int isfault; char buf2[BUFSIZE]; // srand(time(NULL)); srand(0); if ((s_sock = socket(AF_INET, SOCK_STREAM, 0)) == -1) { perror("socket"); exit(1); } memset(&server, 0, sizeof(server)); memset(&other, 0, sizeof(other)); server.sin_family = AF_INET; server.sin_port = htons(PORT); server.sin_addr.s_addr = INADDR_ANY; if (bind(s_sock, (struct sockaddr *) &server, sizeof(server)) == -1) { perror("bind"); goto end; } if (listen(s_sock, BACKLOG) == -1) { perror("listen"); goto end; } other_size = sizeof(other); if ((c_sock = accept(s_sock, (struct sockaddr *)&other, &other_size)) == -1) { perror("accept"); goto end; } i = 0; while (i <= MAX_SEQ_ID) { memset(buf, 0, sizeof(buf)); memset(buf2, 0, sizeof(buf2)); if (i == DISCARD_ID && flag == true) { printf("i = %d: [Simulation loss]\n", i); flag = false; if (read(c_sock, buf, sizeof(buf)) == -1) { perror("read"); goto end2; } continue; } if ((n = read(c_sock, buf, sizeof(buf))) == -1) { perror("read"); goto end2; } isfault = is_fault(); printf("Message from client: %s\n", buf); printf("Corruption status: %d\n", isfault); if (isfault) { strcpy(buf2, NAK); } else { strcpy(buf2, ACK); i++; } strcat(buf2, buf); printf("Message to client: %s\n", buf2); if (write(c_sock, buf2, sizeof(buf2)) == -1) { perror("write"); goto end2; } } end2: if (close(c_sock) == -1) { perror("close"); exit(2); } end: if (close(s_sock) == -1) { perror("close"); exit(3); } return 0; } |
実行方法を紹介します．
まずはサーバを実行します．
|
1 |
$ ./selective_repeat_arq_server |
次に別の端末でクライアントを実行します．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
$ ./selective_repeat_arq_client Message to server: 0 Message to server: 1 Message to server: 2 Message to server: 3 Message from server: NAK0 Corrupt message ACK0 Message to server: 0 Message from server: ACK1 Message from server: NAK2 Corrupt message ACK2 Message to server: 2 Message from server: NAK3 Corrupt message ACK3 Message to server: 3 Message from server: NAK0 Corrupt message ACK0 Message to server: 0 Message from server: NAK2 Corrupt message ACK2 Message to server: 2 Message from server: ACK3 Message from server: ACK0 Message from server: NAK2 Corrupt message ACK2 Message to server: 2 Message from server: NAK2 Corrupt message ACK2 Message to server: 2 Message from server: ACK2 Message to server: 4 Message to server: 5 Message to server: 6 Message to server: 7 Message from server: NAK4 Corrupt message ACK4 Message to server: 4 Message from server: ACK5 Message from server: NAK7 Corrupt message ACK7 Message to server: 7 Message from server: NAK4 Corrupt message ACK4 Message to server: 4 Message from server: ACK7 Message from server: ACK4 Timeout for message: 7 Message to server: 7 Message from server: ACK7 Message to server: 8 Message to server: 9 Message to server: 10 Message from server: ACK8 Message from server: ACK9 Message from server: NAK10 Corrupt message ACK10 Message to server: 10 Message from server: ACK10 |
もう一度サーバの端末をみると，以下の結果になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
$ ./selective_repeat_arq_server Message from client: 0 Corruption status: 1 Message to client: NAK0 Message from client: 1 Corruption status: 0 Message to client: ACK1 Message from client: 2 Corruption status: 1 Message to client: NAK2 Message from client: 3 Corruption status: 1 Message to client: NAK3 Message from client: 0 Corruption status: 1 Message to client: NAK0 Message from client: 2 Corruption status: 1 Message to client: NAK2 Message from client: 3 Corruption status: 0 Message to client: ACK3 Message from client: 0 Corruption status: 0 Message to client: ACK0 Message from client: 2 Corruption status: 1 Message to client: NAK2 Message from client: 2 Corruption status: 1 Message to client: NAK2 Message from client: 2 Corruption status: 0 Message to client: ACK2 Message from client: 4 Corruption status: 1 Message to client: NAK4 Message from client: 5 Corruption status: 0 Message to client: ACK5 i = 5: [Simulation loss] Message from client: 7 Corruption status: 1 Message to client: NAK7 Message from client: 4 Corruption status: 1 Message to client: NAK4 Message from client: 7 Corruption status: 0 Message to client: ACK7 Message from client: 4 Corruption status: 0 Message to client: ACK4 Message from client: 7 Corruption status: 0 Message to client: ACK7 Message from client: 8 Corruption status: 0 Message to client: ACK8 Message from client: 9 Corruption status: 0 Message to client: ACK9 Message from client: 10 Corruption status: 1 Message to client: NAK10 Message from client: 10 Corruption status: 0 Message to client: ACK10 |
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社で自分に合うスクールを見つけましょう．後悔はさせません！
