基于C语言的使用checksum进行差错检测

绝地灬酷狼 2024-04-07 16:00 81阅读 0赞

## 使用checksum进行差错检测 ##

### 协议设计 ###

#### 差错检测 ####

使用checksum进行差错检测，类似于udp的差错检测方式，使用回卷加法，之后将加和进行反码运算，放在数据的最开头，并且回卷加法使用8比特加法。  
![在这里插入图片描述][0cdbd2ba8dc2428bb2f0f3fd3b266177.png]

在发送方的检测使用时，差错和使用0，接收方接收到的数据进行整体的差错检测(包括差错和和数据报文)，如果没有差错，那么接收方的回卷加法和将是0。

差错和存放的数据为回卷加法的反码。

同样的，对于ACK/NAK包也需要进行差错检测。  
![在这里插入图片描述][793b22f02261485b9e41038ddc8408df.png]

#### 数据内容说明 ####

![在这里插入图片描述][fb6e7e1865084e5599eea602382b1261.png]

其中数据表文表示如下。

![在这里插入图片描述][4d79af6f25f548f7936faebc05135aa1.png]

标志位为1字节（8比特）；序号位1字节（8比特）表示数据包的序号，并且ACK/NAK也会包含标志位和序号位；之后的数据全部为信息数据。

对于整个发送的整条信息的最后一个段来说，如果是最后一个报文段，我们需要一个字节来表示他的数据段长度：  
![在这里插入图片描述][8734ab8eef4f465c8055ce376d87b30a.png]

如图所示，长度位位一个字节（8比特），表示后面的数据包的长度，因此如果最后一个数据包长度为509字节时，整个报文的长度可能达到513字节，因此再接受的时候需要统一按照513字节接收。

#### 连接建立 ####

建立连接的时候使用3次握手，并且和TCP有些许不同。

*  第一次的客户端向服务器发送握手协议标志位最低位为1（一个字节内的最低位为从右到左第一位），标志位其他的位为0，并且没有序号位和数据位，之后计算差错和，发送给服务器；
 *  服务器接收到后返回一个数据包，标志位倒数第二位的1，其他位为0，没有序号位和数据，之后计算差错和，返回给客户端；
 *  客户端收到这个数据包之后发送一个标志位倒数第三位为1，其他位为0的数据包，表示连接建立完成，此时两台机器可以开始进行可靠数据传输。

链接建立阶段发送得3个数据包长度均为2字节（为差错检测位和标志位）。

#### 数据包的长度限制 ####

对于一个数据包的长度是有限制的，对于不是整个传输数据结尾的数据包来说最多数据长度为509个字节，即数据报文为512个字节（加上标志位和序号位）。对于传输段最后的不完整的数据来说则有多少发多少。  
对于非结尾数据包，标志位的倒数第4位为1；对于结尾数据包，标志位的倒数4，5位为1；

> 因为一整个链接期间，可能发送得整个数据段不止一个，因此序号位需要在整个链接未断开时不断递增，否则接收方可能会混淆不同的阶段的数据。

#### ACK / NAK 数据包 ####

服务器接收到数据包之后，对于数据进行差错检测，对于"差错和"和"数据报文"进行统一的校验操作，ACK和NAK数据包长度均为3字节（包含差错检测位，标志位和序号位，序号位为其对应的接收包的序号，NAK序号可能不准确）。

*  如果回卷加法的结果是0，那么证明没有错误产生，则缓存接收到的数据报文。之后向客户端发送ACK数据包，ACK数据包的标志位的后两位为1，其他位都为0；
 *  如果回卷加法的结果不是0，那么证明出错了，那么发送NAK数据包，NAK数据包的标志位后3位为1，其他位都为0，表示接受的数据包出错。

#### 超时重传 / 出错重传 ####

因为停等机制的存在，我们需要在设置适当的停止等待协议，在数据包丢包的时候就会进行超时重传；并且在ACK/NAK进行丢包的时候也能进行数据包的超时重传。

*  超时重传：对于当前数据包开启一个计时器，如果超时则进行重传，并且选择适当的序号位。
 *  出错重传：出错重传分为两种，一个是自己的数据包重传，当对方发来的的NAK数据包被接收到的时候，我们需要进行重传；第二个是接收到的ACK或者NAK数据包校验有问题，无法恢复，则进行重传之前的数据包。

为了和之前保持一致，重传数据包的的标志位也和之前的标志位相同。

#### 连接断开 ####

断开连接使用两次挥手协议，首先断开数据包由客户端发送。

*  客户端发送一个标志位第一位为1的数据包，之后开始回收和释放自己的资源。
 *  服务端接受到一个标志位第一位的1的数据包之后，也开始释放自己的资源，之后向客户端发送一个标志位第2位为1的数据包，断开连接。

客户端需要接收到服务端的连接之后才能完全关闭连接，否则进行重传，链接断开的两个数据包长度均为2字节（包含差错检测位和标志位）。

#### 握手和挥手过程中的错误和丢包 ####

如果在挥手和握手期间传递的数据包出错，则从头进行整个挥手握手过程，保证连接信息完整性。

### 功能实现 ###

程序使用了两份代码进行实现，一份为客户端代码，为发送方，一份为服务端代码，为接收方。

程序会让发送方输入服务器的ip地址和所要发送的文件的文件名，之后程序进行连接和处理。  
首先我们会将文件名作为一个单独的数据段发送过去，之后发送整个文件的数据段，在接收端接收到两端数据之后，就可以根据文件名进行数据解析工作，或者在本地存储数据。

##### 实现细节 #####

在文件传输过程中的超时的设置：

> 因为在服务端recvfrom是进行阻塞接受的，我们先使用库函数将其阻塞时间进行设置，在我们的TIMEOUT范围之内。

传输的关键位置的丢包问题：

> 握手挥手过程中的丢包因为无法确认和检测，只能进行重新进行握手挥手实现，并且在挥手中进行超时次数的设置，超过次数认为对方完全断网，自己则进行资源回收后断网。  
> 传输第一个数据段的最后一个包的重传，可能会让接收方误认为是第二段的结束，我们需要设置全程传输时的序号递增，这样就可以解决上述问题

### 协议设计 ###

##### 整体发送流程 #####

对于上层应用程序发送来的数据段，首先进行各个发送包的封装，开始流水线的式的进行数据的发送，在发送窗口未填满时，边发送边进行接收检测，查看对方的是否有累计确认状态码发送过来。对于一个累计确认状态的序号高于当前的base序号的包，则进行发送窗口的滑动，并且更新定时器，继续数据包发送。

##### 差错检测 #####

使用类似3-1的回卷加法，进行差错检测位置的设定

##### 累计确认 #####

由于使用累计确认策略，我们将不会在接收方进行NAK包的设定。只有当当前序号之前的所有包都接收到了，发送这个序号对应的ack包，否则即使接受到了之后的包，也只会发送之前连续接受到的正确的包的ACK。

##### 数据段 #####

对于一个包内的编码设置依然如3-1报告中所示。

##### 滑动窗口 #####

对于发送方我们维护一个大小为WINDOW\_SIZE的序号窗口，这部分数据为已经发送确还未确认的。如果窗口未满，则我们可以继续发送数据包；如果窗口满了，则需要等待ACK确认后窗口的减小，之后才能发送数据包。

对于一个数据段的结束，因为窗口此时不能继续扩大，因此我们需要做特殊的标记处理，此时只许缩小窗口等待全部数据包确认，则可以退出发送函数。

##### GO——BACKN #####

对于每一个发送得数据包，我们记录了他发送出去的时间点，存储在一个队列里timer\_list中，之后根据当前clock()判断队首的包是否发送超时，超时后进行回退重发，并且清空队列；如果未超时收到包，则需要弹出队列队首，即更新计时器。

### 功能实现 ###

为了方便测试与运行，我们的的窗口大小，文件名和接收方ip均可以输入确定，之后在发送过程中我们会输出发送的进度，方便观察。

对于整体的GBN协议设计，我们使用了while循环来回调换recv和send进行实现，避免了使用线程导致的繁琐。

因为我们传送的序列号只有一个Char大小(8比特)，因此肯定存在序号回卷的可能，使得ACK序号和发送方窗口是否已满的判断很难通过base和nextpacknum判断，因此我们可以利用前面提到的timer\_list的长度和变换进行判断，使得序列号回卷变得可以处理。

在对方ACK包丢失的情况下，我们需要处理队列的出队个数，我们通过in\_list维护在队列中的序号这样可以O（1）进行查找，之后就可以应对ACK丢包现象对于发送方的影响。

### 协议设计 ###

##### 数据设计 #####

整体数据段设计和3-1相同，为了观察方便，在本次实验中将其整个数据段长度设置为250字节

##### 确认方式 #####

本次实验依然使用累计确认，并且对于ack的设置和对于其余的设置和对于累计方式和3-2相同，之后使用滑动窗口对发送方数据包进行处理。

##### 拥塞控制 #####

对于拥塞窗口我们使用了两个状态进行拥塞控制

*  状态一：慢启动状态，发送窗口初始设置为1，然后每次进行进行增加，即收到对方一个合格的ack之后，发送方会连续发送两个数据段过去。这样就可以模拟慢启动状态的指数增长，即每次发送窗口会增加一倍。
    
     *  如果期间有数据段包发生了超时重传，那么此时发送方应该进入，并且将下一轮的ssthresh设置为当前发送窗口的一半及cwnd/2，之后将cwnd设置为1，重新开始慢启动状态。
     *  如果当前发送窗口cwnd超过了ssthresh，则进入下一个状态———拥塞避免状态，将在下一点提及
     *  如果在当前出现了3个冗余ACK的情况，则计入另一个状态，快速回复状态。
 *  状态二：拥塞避免状态，发送窗口初始为转移到这个状态时的样子，然后窗口的增长方式变为没个发送阶段增长1个MSS，即下一个完整的发送窗口将会比当前完整的发送窗口大1，进行线性增长，直到出现以下状况：
    
     *  出现某个包的超时事件，表明这个包已经丢失。并且后面的包也会丢失，因此我们需要进行强烈的拥塞控制，将ssthresh设置为cwnd/2，并且将cwnd设置为1，重新进入慢启动状态。
     *  如果出现了3次冗余ACK，则证明只有一个包丢失，其余后面的包到达发送方，因此状态将走到下一个状态——快速恢复状态
 *  状态三：快速恢复状态，在产生3个冗余ack之后，就会进入这个状态，这个状态主要用于快速重传丢失的ack包，一直重传当前的丢失包，
    
     *  如果收到一个冗余ack则将发送窗口cwnd+1然后重新开始快速恢复状态
     *  如果成功收到了丢失包的ack，则进入拥塞控制状态
     *  如果出现了超时时间，则进入慢启动状态

#### 发送流程 ####

我们最开始以慢启动状态启动，之后按照遇到的情况在3个状态之间切换，完成整个数据包的发送和接受任务

### 使用方法 ###

只需要最开始输入接受方的ip地址，之后程序可以自动完成拥塞控制和累计确认滑动窗口等工作

##### 停等协议与滑动窗口对比 #####

运行环境均为使用router传送1M数据使用的时间，时间越短越好，计时单位为秒，mss为510，窗口大小为25，timeout为500ms

分析：当传输的丢包率增加时，各个协议因为需要停等超时触发的超时重传十分耽误时间，因此传输用时普遍增加。

因为滑动窗口可以更高效利用发送的带宽，提高带宽利用率，因为相较于停等协议有部分提升，但是由于丢包问题，GBN协议要求的回退N完全的重传也导致时间延长很大，因此较停等协议更优但是差别不大。

##### 滑动窗口不同的窗口大小的传输时间 #####

运行环境均为使用router传送1M数据使用的时间，时间越短越好，计时单位为秒，丢包率5%，mss为250，timeout为1500ms

运行环境均为使用router传送1M数据使用的时间，时间越短越好，计时单位为秒，丢包率0%，mss为250，timeout为1500ms

![在这里插入图片描述][795b4049b2fd467187c8e669f41b4943.png]

分析：滑动窗口协议因为其每次发送都会发送窗口大小的数据段，因此在丢包率较小的时候，越大的窗口总的来说是越优的，因为丢包率较小，传输时间差异不大，但是总体来说还是可以看出其更优。

当丢包率较大是，因为窗口的大小增加会导致GBN的时候重传的数据包过多，因此窗口太大会导致时间过长。

因此我们需要根据丢包率队窗口大小做一个折中。

##### 滑动窗口不同的窗口大小的传输时间 #####

运行环境均为使用router传送1M数据使用的时间，时间越短越好，计时单位为秒，mss为250，timeout为1500ms，无拥塞控制协议窗口大小为25

<table> 
 <thead> 
  <tr> 
   <th>丢包率</th> 
   <th>有拥塞控制</th> 
   <th>无拥塞控制</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0%</td> 
   <td>2.29s</td> 
   <td>2.53s</td> 
  </tr> 
  <tr> 
   <td>5%</td> 
   <td>391.76s</td> 
   <td>469.96s</td> 
  </tr> 
  <tr> 
   <td>10%</td> 
   <td>662.25s</td> 
   <td>1257.86s</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][00de6fda33b2447bb12439bcbf253c9b.png]

分析：拥塞控制就是一个在丢包率和窗口大小上的一个动态调整，因为其可以在没有丢包时尽量的扩大自己窗口提高带宽利用率；在丢包率提高是，减小窗口，防止GBN重传过多，因此，其在大部分情况下优于无拥塞控制的方案。  
|  
| 5% | 391.76s | 469.96s |  
| 10% | 662.25s | 1257.86s |

\[外链图片转存中…(img-xEOtdbCD-1663153543811)\]

分析：拥塞控制就是一个在丢包率和窗口大小上的一个动态调整，因为其可以在没有丢包时尽量的扩大自己窗口提高带宽利用率；在丢包率提高是，减小窗口，防止GBN重传过多，因此，其在大部分情况下优于无拥塞控制的方案。

[0cdbd2ba8dc2428bb2f0f3fd3b266177.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1067a4b1b0394807ab7f79ccfad7d058.png
[793b22f02261485b9e41038ddc8408df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6aa0d21193b74e328d3c2d96b1cb167b.png
[fb6e7e1865084e5599eea602382b1261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/cbe24864f91b44bea1bd8922b1c09885.png
[4d79af6f25f548f7936faebc05135aa1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/cb3918fa50464ea189eb274e84d19585.png
[8734ab8eef4f465c8055ce376d87b30a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/69457dbdd29c48649e3e4957aa5cb1f8.png
[795b4049b2fd467187c8e669f41b4943.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2ae714760faf4d30bf6ac57d084471e4.png
[00de6fda33b2447bb12439bcbf253c9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4fc5f803ea2c4437b7fae125ca217513.png