本文主要是介绍【SZU计算机网络实验】从rdt到GBN,这实验居然实现了TCP的可靠数据传输机制?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
一个实验六个任务,实验文档一划划不到底。。看来老师们是真下功夫了啊
本文主要展示了作者在完成SZU计算机网络实验3的思路及过程,实验主要包括:
- 理解rdt2.1
- 实现rdt2.2
- 实现rdt3.0
- 实现回退N步(GBN)机制
- 实现面向无连接的可靠传输机制(GBN)
- 进行量化分析
文中出现的状态机演示图均基于mermaid。在本文中,过渡文字中第一行表示事件,第二行之后表示动作
参考资料:
实验文档:计算机网络课程综合实验平台 (snrc.site)
一、理解rdt2.1
0. 理解rdt1.0和rdt2.0
在理解rdt2.1之前,我们需要先了解rdt2.1出现的背景,才能知道其解决的问题
rdt全称reliable data transfer,即可靠数据传输
由于网络层是不可靠传输,而位于网络层之上的传输层中的TCP,试图为上层提供可靠的传输
1) rdt1.0
rdt1.0作为第一代的rdt模型,它假设底层信道(网络层及其以下层)是可靠的,即传输层的这一端到另一端之间,它们都是按序到达,且不会出现数据的损坏和丢包
因而rdt1.0的发送端和接收端的状态机的表示如下
发送端
rdt_send(data)表示上层(应用层)发送数据到该层
packet=make_pkt(data)表示将数据封装成数据包,udt_send(packet)将数据包传递给下层
接收端
rdt_rcv(packet)表示从下层接收到数据包
extract(packet, data)表示从数据包中提取出数据,deliver_data(data)将数据分发到上层
2) rdt2.0
rdt1.0过于理想,实际上发送的数据包很可能在传输过程中,出现比特差错
那么接收端就需要对数据包做差错检测。如果数据包没有受损,则反馈给发送端一个ACK;若数据包受损,则反馈给发送端一个NAK
而发送端在发送数据包后等待接收端的反馈,根据反馈是ACK还是NAK选择进入下一个数据包的发送,或是重传原来的数据包
rdt2.0的状态机如下:
发送端
可以发现在构造数据包时,多引入了一个变量checksum即校验码:sndpkt=make_pkt(data, checksum)
接收端
接收到数据包时,利用notcorrupt(rcvpkt)和corrupt(rcvpkt)判断数据包受损与否
若未受损,构造ACK数据包并反馈:sndpkt=make_pkt(ACK) udt_send(sndpkt)
若受损,构造NAK数据包并反馈:sndpkt=make_pkt(NAK) udt_send(sndpkt)
1. 引入rdt2.1
1) rdt2.1的状态转移
在rdt2.0中,通过引入ACK/NAK解决了发送的数据包可能存在比特差错的问题
但是,接收端反馈的ACK/NAK数据包也可能在传输过程中出现比特差错,这就需要在接收端构造ACK/NAK数据包时也使用checksum校验码,并且在发送端对ACK/NAK数据包进行校验。
这就导致了一种情况:当发送的数据包成功抵达接收方,而接收方发送的ACK出现比特差错时,发送方需要重传原来的数据包,而接收方无法识别这是新的数据包还是原来的数据包的重传
因此需要为每个数据包标号0/1:
当发送端发送数据包0,进入等待ACK/NAK的状态;数据包0成功抵达接收端,接收端发送一个ACK并进入等待数据包1的状态;但是该ACK出现比特差错,发送端需要重传数据包0,继续等待ACK/NAK,接收端接收到数据包0,知道是重复的数据包,返回一个ACK并继续等待数据包1
故rdt2.1的状态机如下以及:
发送端
与rdt2.0相比,rdt2.1在make_pkt中新增了一个参数,值为0/1:
sndpkt=make_pkt(0, data, checksum)
sndpkt=make_pkt(1, data, checksum)
在等待ACK/NAK的状态中,当接收包损坏或为NAK时重发,只有接收包未损坏且为ACK时才进入下一数据包的发送:
corrupt(rcvpkt) || isNAK(rcvpkt)
notcorrupt(rcvpkt) && isACK(rcvpkt)
接收端
与rdt2.0相比,rdt2.1在make_pkt中增加了一个checksum:
sndpkt=make_pkt(ACK, checksum)
sndpkt=make_pkt(NAK, checksum)
在Wait for 0 call from below状态中,只有接收到未损坏且序列号为0的数据包,才会提取并分发数据并发送一个ACK,跳转到Wait for 1 call from below状态;接收到未损坏且序列号为1的数据包时,认定其为重复,不提取分发,但是发送一个ACK;接收到损坏的数据包时,发送一个NAK
2) rdt2.1的代码实例
在c语言中利用一个while循环+switch分支模拟状态机的运行,代码如下:
发送端
void sending_packets()
{// 初始化状态Sender_State currentState = STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE;int seq = 0;char *data;Packet *rcvpkt;boolean finish_send = FALSE;// get start_timeunsigned long start_time = GetTickCount();while (!finish_send){switch (currentState){case STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE:printf("STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE\n");data = rdt_send(seq);sndpkt = make_pkt(seq, PACKET_TYPE_DATA, data);udt_send(sockfd, sndpkt, &client_addr);seq++;currentState = STATE_WAIT_ACK_NAK_EVEN;break;case STATE_WAIT_ACK_NAK_EVEN:printf("STATE_WAIT_ACK_NAK_EVEN\n");rcvpkt = rdt_rcv(sockfd, &client_addr);if (corrupt(rcvpkt) || isNAK(rcvpkt)){udt_send(sockfd, sndpkt, &client_addr);}else if (notcorrupt(rcvpkt) && isACK(rcvpkt)){free(sndpkt);currentState = STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE;}free(rcvpkt);break;case STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE:printf("STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE\n");data = rdt_send(seq);sndpkt = make_pkt(seq, PACKET_TYPE_DATA, data);udt_send(sockfd, sndpkt, &client_addr);seq++;currentState = STATE_WAIT_ACK_NAK_ODD;break;case STATE_WAIT_ACK_NAK_ODD:printf("STATE_WAIT_ACK_NAK_ODD\n");rcvpkt = rdt_rcv(sockfd, &client_addr);if (corrupt(rcvpkt) || isNAK(rcvpkt)){udt_send(sockfd, sndpkt, &client_addr);}else if (notcorrupt(rcvpkt) && isACK(rcvpkt)){free(sndpkt);currentState = STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE;if (seq == TOTAL_PACKETS)finish_send = TRUE;}free(rcvpkt);}}
}
接收端
void receiving_packets(){Packet *rcvpkt;Packet* sndpkt;int rcv_seq = -1;// 初始化状态Receiver_State currentState = STATE_WAIT_FOR_EVEN_FROM_BELOW; while (TRUE){switch (currentState){case STATE_WAIT_FOR_EVEN_FROM_BELOW:printf("STATE_WAIT_FOR_EVEN_FROM_BELOW\n");rcvpkt = rdt_rcv(sockfd, &server_addr);if (notcorrupt(rcvpkt) && is_seq_even(rcvpkt)){extract_data(rcvpkt);rcv_seq = rcvpkt->seq;sndpkt = make_pkt(rcv_seq, PACKET_TYPE_ACK, NULL);udt_send(sockfd, sndpkt, &server_addr);free(sndpkt);currentState = STATE_WAIT_FOR_ODD_FROM_BELOW;}else if (corrupt(rcvpkt)){sndpkt = make_pkt(rcv_seq, PACKET_TYPE_NAK, NULL);udt_send(sockfd, sndpkt, &server_addr);free(sndpkt);}else if (notcorrupt(rcvpkt) && is_seq_odd(rcvpkt)){sndpkt = make_pkt(rcv_seq, PACKET_TYPE_ACK, NULL);udt_send(sockfd, sndpkt, &server_addr);free(sndpkt);}case STATE_WAIT_FOR_ODD_FROM_BELOW:printf("STATE_WAIT_FOR_ODD_FROM_BELOW\n");rcvpkt = rdt_rcv(sockfd, &server_addr);if (notcorrupt(rcvpkt) && is_seq_odd(rcvpkt)){extract_data(rcvpkt);rcv_seq = rcvpkt->seq;sndpkt = make_pkt(rcv_seq, PACKET_TYPE_ACK, NULL);udt_send(sockfd, sndpkt, &server_addr);free(sndpkt);currentState = STATE_WAIT_FOR_EVEN_FROM_BELOW;}else if (corrupt(rcvpkt)){sndpkt = make_pkt(rcv_seq, PACKET_TYPE_NAK, NULL);udt_send(sockfd, sndpkt, &server_addr);free(sndpkt);}else if (notcorrupt(rcvpkt) && is_seq_even(rcvpkt)){sndpkt = make_pkt(rcv_seq, PACKET_TYPE_ACK, NULL);udt_send(sockfd, sndpkt, &server_addr);free(sndpkt);}free(rcvpkt);break;}}
3) rdt2.1的测试
实验要求我们以 数据包错误频率(Tamper rate) 为自变量,改变其值
观察 数据包总数(OverHead) 和 有效吞吐量(Goodput) 这两个因变量与之的关系
数据包总数(OverHead)= 发送端总发包量 + 接收端总发包量,即包括正常数据包、ACK/NAK包、重传包;
有效吞吐量(Goodput) = 有效数据包数量 × 数据包大小 ÷ 数据发送总时间,其中有效数据包不包括ACK/NAK和重传包;
为了统计数据包总数,我们在库文件中引入静态变量:
static unsigned long OverHead = 0;
在每次发送数据包,即调用udt_send时,将该变量+1:
void udt_send(SOCKET sockfd, Packet *packet, struct sockaddr_in *addr)
{char *buffer = (char *)malloc(sizeof(Packet));memcpy(buffer, packet, sizeof(Packet));// 发送通知if (sendto(sockfd, buffer, sizeof(Packet), 0, (struct sockaddr *)addr, sizeof(*addr)) == SOCKET_ERROR){printf("Error code : %d\n", WSAGetLastError());printf("Sendto failed.\n");}else{printf("Sent successfully. Sequence: %d; Type:%d.\n", packet->seq, packet->type);OverHead++; // 统计OverHead}free(buffer);
}
提供获取OverHead的函数:
unsigned long getOverHead(){printf("OverHead: %d\n", OverHead);return OverHead;
}
我们以相同的手段统计数据包损坏数,并计算数据包错误频率:
数据包错误频率 = 数据包损坏数 / 数据包总数
static unsigned long corruptNum = 0;
boolean corrupt(Packet *rcvpkt)
{if (rcvpkt->checksum != calculate_checksum(rcvpkt)){corruptNum++; // 统计数据包损坏数printf("Packet corrupted!\n");return TRUE;}else{return FALSE;}
}
float calculate_tamper_rate(){float tamper_rate = corruptNum * 1.0 / OverHead;printf("Tamper Rate: %f\n", tamper_rate);return tamper_rate;
}
而对于有效吞吐量,库文件中已经有提供函数给我们直接获取,需要我们传入程序运行的始末时间:
float calculate_goodput(unsigned long start_time, unsigned long end_time)
{unsigned long long total_bytes_received = MAX_PACKET_SIZE * TOTAL_PACKETS; // 接收到的总字节数float goodput = (float)total_bytes_received / (float)(end_time - start_time) * 1000.0f; // bytes per secondprintf("Total time elapsed: %lu ms\n", (end_time - start_time));printf("Goodput: %f B/s\n", goodput);return goodput;
}
在server.c中调用以上函数如下:
// get start_timeunsigned long start_time = GetTickCount();while (!finish_send){/**状态机**/ }// get end_timeunsigned long end_time = GetTickCount();// calculate goodputcalculate_goodput(start_time, end_time);// get overheadgetOverHead();// get tamper ratecalculate_tamper_rate();
}
由于默认的数据包数量是200,在该条件下,前后间隔时间太短接近于0,会导致计算吞吐量得到无穷大。因此在rdt.h中修改数据包数为20000:
#define TOTAL_PACKETS 20000
先运行接收端再运行客户端,分别将输出内容重定向到文本文件中:
root@Andrew:/mnt/d/.c/computernetwork/exp3-1# ./client.exe >client.txt
root@Andrew:/mnt/d/.c/computernetwork/exp3-1# ./server.exe > server.txt
在clumsy中设定Tamper = 0.3,测试结果如下:
Total time elapsed: 1531 ms
Goodput: 13376878.000000 B/s
OverHead: 20105
Tamper Rate: 0.002835
修改Tamper的值依次为0.3, 0.5, 1, 2, 3, 5, 10, 20, 30,统计汇总到excel表格中,并绘制曲线如下:
根据图像可以看出,数据包总数 与 数据包错误频率 之间有呈非线性关系的趋势,而有效吞吐量 与 数据包错误频率 之间呈线性关系
二、实现rdt2.2
1. 理解rdt2.2
想要理解为什么引入rdt2.2,还是得看rdt2.1在哪种场景下会比较低效:
假设连续三个数据包满足以下条件:接收端正常接收数据包,接收端返回的ACK发生错误,发送端重传的数据包发生错误
如果是rdt2.1,之后会发生:接收端返回一个NAK,之后发送端再重传一个数据包
可以发现,在上述场景中,发送端重传的数据包无论是否发生错误,对接收端来说都是没有用的。而如果该数据包损坏,接收端就得返回一个NAK,导致发送端不得不再重传一次没有用的数据包
于是rdt2.2引入一种解决方案:
不使用NAK,而是将ACK编号:接收端只有在接收到当前期待的数据包(比如数据包0)时,才会返回该序号的ACK(比如ACK0),其他情况(接收到数据包1 或 接收到受损的数据包)都会返回另一序号的ACK(比如ACK1)
因此,rdt2.2的状态机如下:
发送端
相比rdt2.1,rdt2.2检查ACK的函数多了一个参数,值为0/1,用于判断ACK的序号的奇偶性;并将isNAK替换为当前期待ACK序号奇偶性相反的isACK,比如,在状态Wait for ACK 0:
isACK(rcvpkt) 变为 isACK(rcvpkt, 0)
isNAK(rcvpkt) 变为 isACK(rcvpkt, 1)
接收端
相比rdt2.1,rdt2.2在状态Wait for 0 call from below时,将corrupt(rcvpkt) 和 notcorrupt(rcvpkt) && has_seq1(rcvpkt)合并为一种情况:
corrupt(rcvpkt) || has_seq1(rcvpkt)
并统一发送ACK1(make_pkt构造ACK数据包也增加了一个序号参数):
make_pkt(ACK, 1, checksum)
否则(正常接收到数据包0)发送ACK0:
make_pkt(ACK, 0, checksum)
2. rdt2.2代码实现
由于rdt2.2不需要NAK,并且将ACK编号为ACK0和ACK1
在库文件中将数据包类型(包括ACK, DATA, NAK)修改为(ACK0, DATA, ACK1),如下:
// 数据包定义
typedef enum
{// rdt 2.1// PACKET_TYPE_ACK = 1,// PACKET_TYPE_DATA = 0,// PACKET_TYPE_NAK = -1// rdt 2.2PACKET_TYPE_ACK_ODD = 1,PACKET_TYPE_DATA = 0,PACKET_TYPE_ACK_EVEN = -1
} Packet_Type;
那么就不需要原本的isACK以及isNAK,将其注释并引入isACKEven和isACKOdd判断数据包类型:
// rdt v2.1
// boolean isACK(Packet *rcvpkt)
// {
// if (rcvpkt->type == PACKET_TYPE_ACK)
// {
// printf("Received ACK of %d\n", rcvpkt->seq);
// return TRUE;
// }
// return FALSE;
// }
// boolean isNAK(Packet *rcvpkt)
// {
// if (rcvpkt->type == PACKET_TYPE_NAK)
// {
// printf("Received NAK of %d\n", rcvpkt->seq);
// return TRUE;
// }// return FALSE;
// }// rdt v2.2
boolean isACKOdd(Packet *rcvpkt)
{if (rcvpkt->type == PACKET_TYPE_ACK_ODD) // key step{printf("Received ACK ODD of %d\n", rcvpkt->seq);return TRUE;}return FALSE;
}
boolean isACKEven(Packet *rcvpkt)
{if (rcvpkt->type == PACKET_TYPE_ACK_EVEN) // key step{printf("Received ACK EVEN of %d\n", rcvpkt->seq);return TRUE;}return FALSE;
}
对于发送端,将状态 STATE_WAIT_ACK_NAK_EVEN 和 STATE_WAIT_ACK_NAK_ODD 修改为 STATE_WAIT_ACK_EVEN 和 STATE_WAIT_ACK_ODD,根据状态机模型合并两个分支(以下key step):
switch (currentState){case STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE:printf("STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE\n");data = rdt_send(seq);sndpkt = make_pkt(seq, PACKET_TYPE_DATA, data);udt_send(sockfd, sndpkt, &client_addr);seq++;// rdt v2.1:// currentState = STATE_WAIT_ACK_NAK_EVEN;// rdt v2.2:currentState = STATE_WAIT_ACK_EVEN;break;// rdt v2.1:// case STATE_WAIT_ACK_NAK_EVEN:// printf("STATE_WAIT_ACK_NAK_EVEN\n");// rcvpkt = rdt_rcv(sockfd, &client_addr);// if (corrupt(rcvpkt) || isNAK(rcvpkt))// {// udt_send(sockfd, sndpkt, &client_addr);// }// else if (notcorrupt(rcvpkt) && isACK(rcvpkt))// {// free(sndpkt);// currentState = STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE;// }// free(rcvpkt);// break;// rdt v2.2:case STATE_WAIT_ACK_EVEN:printf("STATE_WAIT_ACK_EVEN\n");rcvpkt = rdt_rcv(sockfd, &client_addr);if (corrupt(rcvpkt) || isACKOdd(rcvpkt)) // key step{udt_send(sockfd, sndpkt, &client_addr);}else if (notcorrupt(rcvpkt) && isACKEven(rcvpkt)) // key step{free(sndpkt);currentState = STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE;}free(rcvpkt);break;case STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE:printf("STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE\n");data = rdt_send(seq);sndpkt = make_pkt(seq, PACKET_TYPE_DATA, data);udt_send(sockfd, sndpkt, &client_addr);seq++;// rdt v2.1// currentState = STATE_WAIT_ACK_NAK_ODD;// rdt v2.2currentState = STATE_WAIT_ACK_ODD;break;// rdt v2.1// case STATE_WAIT_ACK_NAK_ODD:// printf("STATE_WAIT_ACK_NAK_ODD\n");// rcvpkt = rdt_rcv(sockfd, &client_addr);// if (corrupt(rcvpkt) || isNAK(rcvpkt))// {// udt_send(sockfd, sndpkt, &client_addr);// }// else if (notcorrupt(rcvpkt) && isACK(rcvpkt))// {// free(sndpkt);// currentState = STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE;// if (seq == TOTAL_PACKETS)// finish_send = TRUE;// }// free(rcvpkt);// rdt v2.2case STATE_WAIT_ACK_ODD:printf("STATE_WAIT_ACK_ODD\n");rcvpkt = rdt_rcv(sockfd, &client_addr);if (corrupt(rcvpkt) || isACKEven(rcvpkt)) // key step{udt_send(sockfd, sndpkt, &client_addr);}else if (notcorrupt(rcvpkt) && isACKOdd(rcvpkt)) // key step{free(sndpkt);currentState = STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE;if (seq == TOTAL_PACKETS)finish_send = TRUE;}free(rcvpkt);}}
3. rdt2.2测试
以数据包错误率为自变量对rdt2.2进行与上述相同的测试,并与rdt2.1的结果进行比较,绘制曲线如下
可以看到,rdt2.2对比rdt2.1发送的数据包总量更少,且有效吞吐量更高,说明rdt2.2确实减少了冗余数据包的发送,相比rdt2.1更为高效
三、实现rdt3.0
这篇关于【SZU计算机网络实验】从rdt到GBN,这实验居然实现了TCP的可靠数据传输机制?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!