基于C语言实现的滑动窗口协议

chester

发布日期: 2020-08-24 14:22:21 浏览量: 86
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

一、实验内容

利用所学数据链路层原理,自己设计一个滑动窗口协议,在仿真环境下编程实现有噪音信道环境下两站点之间无差错双工通信。信道模型为8000bps全双工卫星信道,信道传播时延270毫秒,信道误码率为10-5,信道提供字节流传输服务,网络层分组长度固定为256字节。

二、实验目的

通过该实验,进一步巩固和深刻理解数据链路层误码检测的CRC校验技术,以及滑动窗口的工作机理。滑动窗口机制的两个主要目标:(1) 实现有噪音信道环境下的无差错传输; (2)充分利用传输信道的带宽。在程序能够稳定运行并成功实现第一个目标之后,运行程序并检查在信道没有误码和存在误码两种情况下的信道利用率。为实现第二个目标,提高滑动窗口协议信道利用率,需要根据信道实际情况合理地为协议配置工作参数,包括滑动窗口的大小和重传定时器时限以及ACK搭载定时器的时限。这些参数的设计,需要充分理解滑动窗口协议的工作原理并利用所学的理论知识,经过认真的推算,计算出最优取值,并通过程序的运行进行验证。

通过该实验提高同学的编程能力和实践动手能力,体验协议软件在设计上各种问题和调试难度,设计在运行期可跟踪分析协议工作过程的协议软件,巩固和深刻理解理论知识并利用这些知识对系统进行优化,对实际系统中的协议分层和协议软件的设计与实现有基本的认识。

三、实验环境

  • win10平台 版本1909 (OS内部版本 18363.900)

  • Visual Studio Code

  • Visual Studio 2019

四、软件设计

4.1 数据结构

结构体定义

  1. typedef unsigned char seq_nr;
  2. typedef unsigned char frame_kind;
  3. typedef int event_type; //protocol中定义5个event
  4. /*
  5. #define NETWORK_LAYER_READY 0 //网络层有待 发送的分组。此事件发生后才 可以调用 get_packet()得到网络层待发送的下一个 分组。
  6. #define PHYSICAL_LAYER_READY 1 //物理层发送队列的长度低于50字节
  7. #define FRAME_RECEIVED 2 //物理层收到了一整帧
  8. #define DATA_TIMEOUT 3 //定时器超时,参数arg中返回发生超时的定时器的编号
  9. #define ACK_TIMEOUT 4 //所设置的搭载ACK定时器超时
  10. */
  11. typedef struct FRAME
  12. {
  13. frame_kind kind; //数据种类
  14. seq_nr ack; //ACK号
  15. seq_nr seq; //数据序号
  16. unsigned char data[PKT_LEN]; //数据 PKT_LEN = 256
  17. unsigned int padding;
  18. } frame;
  19. typedef struct PACKET
  20. {
  21. unsigned char data[PKT_LEN]; //数据
  22. } packet;

帧结构

  1. DATA Frame
  2. +=========+========+========+===============+========+
  3. | KIND(1) | SEQ(1) | ACK(1) | DATA(240~256) | CRC(4) |
  4. +=========+========+========+===============+========+
  5. ACK Frame
  6. +=========+========+========+
  7. | KIND(1) | ACK(1) | CRC(4) |
  8. +=========+========+========+
  9. NAK Frame
  10. +=========+========+========+
  11. | KIND(1) | ACK(1) | CRC(4) |
  12. +=========+========+========+

宏定义

  1. #define DATA_RESEND_TIME 2890 //数据帧超时重传定时时间
  2. #define ACK_TIMER 1200 //ack帧定时时间
  3. #define MAX_SEQ 19 //最大序号
  4. #define NR_BUFS ((MAX_SEQ + 1) / 2) //((MAX_SEQ + 1) / 2)
  5. // #define inc(k) ((k) = ((k) + 1) % (MAX_SEQ + 1)) //自加

全局变量

  1. seq_nr frame_expected; //接受窗口下界
  2. seq_nr too_far; //接受窗口上界 + 1
  3. seq_nr next_frame_to_send; //发送窗口上界 + 1
  4. seq_nr ack_expected; //发送窗口下界
  5. seq_nr nbuffered; //发送缓存数量
  6. seq_nr oldest_frame = MAX_SEQ + 1;
  7. // static seq_nr buffer[PKT_LEN];
  8. packet out_buf[NR_BUFS]; //发送缓存
  9. packet in_buf[NR_BUFS]; //接受缓存
  10. static int phl_ready = 0; //物理层就绪
  11. static int no_nak = 1; //没有nak被发送
  12. int arrived[NR_BUFS];

主函数变量

  1. int arg; //接受wait_for_event返回的参数
  2. event_type event; //event_type在protocol.h中定义
  3. frame r; //帧结构
  4. int len; //保存从物理层收到的数据长度

4.2 模块结构

  1. static void put_frame(unsigned char *frame, int len)
  2. //功能: 为frame计算crc,并且将加上4位crc的frame(长度为len + 4 )送到物理层
  3. //参数frame 帧起始字节地址
  4. //参数len 帧长度
  5. static int between(seq_nr a, seq_nr b, seq_nr c)
  6. //功能:判断b是否在ac窗口内
  7. //参数a 滑动窗口下界
  8. //参数b 被判断的序号
  9. //参数c 滑动窗口上界
  10. static void send_data_frame(frame_kind fk, seq_nr frame_nr, seq_nr frame_expected, packet buffer[])
  11. //功能:将buffer中编号为frame_nr的fk类型的数据包发送出去,并且捎带ack。
  12. //参数fk 帧种类 有 FRAME_DATA FRAME_ACK FRAME_NAK
  13. //参数frame_nr 数据包序号
  14. //参数frame_expected 捎带ACK
  15. //参数 buffer[] 缓存

调用关系:箭头→ A → B 表示A模块调用B模块

4.3 算法流程图

五、实验结果分析

描述你所实现的协议软件是否实现了有误码信道环境中无差错传输功能。

在有误码信道环境中,若收到错帧有以下措施保证无差错传输功能。

  • 出错时,若当时未发送该帧的NAK,则发送NAK给对方,要求对方重传,若已经发送NAK,则等待计时器超时后重传

  • 收到帧序号位于接受窗口的帧时,将该帧放入in_buf中缓存,延迟递交给网络层,即使前面出错了,也能保证在缓冲区内的数据不丢失

  • ACK采用捎带确认的方式,如果当前没有数据进行稍待确认,则ACK定时器超时,ACK帧单独重发

程序的健壮性如何,能否可靠地长时间运行。

程序的健壮性十分不错。我在-f选项下运行了接近3.5ws(9.7h)没有崩溃,并且效率与之前测得数据匹配,94.38% 94.20%,仅有百分之零点几的下降,说明不仅其健壮性,可靠性。因为时间原因没有继续将其测试下去,但我相信该程序能继续运行下去。

协议参数的选取:滑动窗口的大小,重传定时器的时限,ACK搭载定时器的时限,这些参数是怎样确定的?根据信道特性数据,分组层分组的大小,以及你的滑动窗口机制,给出定量分析,详细列举出选择这些参数值的具体原因。

  • 滑动窗口的大小

    1. 链路利用率 <= Ws / (1 + 2Td*C/L)

    其中B = 8000bps / 263B = 3.802个/s,D = 270ms,因此算出W的最小值约为3.05,因此滑动窗口的大小应该大于3.05,将窗口开大会浪费缓冲区,并且有可能导致物理层拥塞,因此我不打算将缓冲区开成最大。观察log文件,发现数据链路层大概每收8帧发给网络层一次,因此我认为缓存的极限区域为8,但为了留出余量,经过测试发现MAX_SEQ = 19是一个比较好的参数。因此将缓存设置为10,MAX_SEQ = 19, NR_BUFS = 10。

  • ACK定时器ACK_RESEN_TIME的确定
    从理论上看,数据帧263Byte,ACK帧6Byte,单向传输延迟为270ms,通过观察log文件,发现每8帧会传送给网络层一次,因此为了刚好在接收方接受完这八帧时,下8帧也到达,可以算出ACK_RESEND_TIMER,先算出8帧从发送到接受方的时间 263 * 8 + 270 + 7(间隔时间) = 2381ms,因需要在八帧处理完前ack到达,因此ACK_RESEND_TIMER要小于该值,因此我取平均数1200

  • 数据超时重传定时器DATA_RESEND_TIME的确定
    理论计算值:263 + 270 + x(假设立马传ACK回来) + 6 + 270 = 809ms + x,但是,如果直接通过理论计算,我认为并不能得到好的参数,因为,理论计算无法考虑到捎带ACK,以及ACK延迟发送的问题,以及队列排队等待,程序处理时间,因此我通过对log的分析,才得到程序中的DATA_RESEND_TIME。
    第一行为发送帧序号,第二行接受方接受时间+ACK返回到发送放时间,因为程序中存在稍待确认以及延迟发送ACK,因此我假设接到数据立即返回ACK帧,以此算出RTT。
    该测试log文件名为 datalink-A/B 参数-fud3 A/B 结果 93.74 93.73 DT 3000 AT 270 测试参数DATA_TIMER = 2900, ACK_TIMER = 270

第一轮数据

序号 0 1 2 4 8 16 32 64 128
时间ms 838 827 841 845 833 882 817 815 849

第二轮数据

序号 0 1 2 4 8 16 32 64 128
时间ms 834 831 846 848 833 831 847 840 845

(加粗为去掉的数据)

通过第一轮第二轮数据,去掉最低的两个以及最高的两个,可算出,平均RTT = 838.5,并且减去ACK回传时间,以及信道延迟,可得到一个平均数X = RTT – 6ms – 270ms – 270ms = 292.25,可以得到,一个263B的数据帧的处理时间约为292.25ms, 而通过观察.log文件,在ACK_TIMER = 270ms的情况下,大约8个数据包接收方返回一个ACK,因此,我们可以将8个数据包当做一个数据包传送,因此可以算出DATA_TIMER,也就是延迟时间为 8 * 292.25 + 7(间隔时间) + 270 + 6 + 270 = 2891,因此我设置DATA_TIMER为2890。

理论分析:根据所设计的滑动窗口工作机制(Go-Back-N或者选择重传),推导出在无差错信道环境下分组层能获得的最大信道利用率;推导出在有误码条件下重传操作及时发生等理想情况下分组层能获得的最大信道利用率。给出理论推导过程。理论推导的目的是得到信道利用率的极限数据。为了简化有误码条件下的最大利用率推导过程,可以对问题模型进行简化,比如:假定超时重传的数据帧的回馈ACK帧可以100%正确传输,但是简化问题分析的这些假设必须不会对整个结论产生较大的误差。

  • 无差错信道下:无差错信道,当a,b以洪水模式发送数据包时,链路利用率的极限值应该为256/263 = 97.34%

  • 有差错信道下:当差错率为10^-5时,10^5bit约能产生49个数据包,其中有一个出错,需要重传,假设重传的数据包一定正确,则10^5bit需要约50个数据包,因此利用率为49256/50263 = 95.4%

实验结果分析:你的程序运行实际达到了什么样的效率,比对理论推导给出的结论,有没有差距?给出原因。有没有改进的办法?如果没有时间把这些方法付诸编程实施,介绍你的方案。

序号 命令选项 说明 运行时间(秒) Selective算法线路利用率(%)A Selective算法线路利用率(%)B
1 -–utopia 无误码信道数据传输 1700 54.96 96.97
2 站点A分组层平缓方式发出数据,站点B周期性交替“发送100秒,停发100秒” 1300 53.61 94.38
3 –-flood —utopia 无误码信道,站点A和站点B的分组层都洪水式产生分组 1300 96.97 96.97
4 –-flood 站点A/B的分组层都洪水式产生分组 1300 94.35 94.62
5 —flood -–ber=1e-4 站点A/B的分组层都洪水式产生分组,线路误码率设为10-4 2700 62.91 61.72
  • 命令为-u时, A效率相对样例数据,高了1%,而B效率仅低0.03%,因此在命令-u情况下,比样例数据稍好

  • 无命令选项时,A效率相对样例数据,低了0.7%,而B高了0.7%,总体上持平

  • 命令为 -fu时,AB效率均与样例数据相差0.03%,因此与样例数据持平,仅有稍稍的差距

  • 命令为-f时,AB均与样例数据相差0.7%,因此与样例有较小的差距

  • 命令为-f—ber=1e-4时, A效率高于样例数据20%,而B效率仅低于样例数据12%,总体高于8%,因此总体上比样例数据好很多

对比样例数据,仅有在命令为-f时,能看出总体上1.4%的差距,其他命令下,均与样例接近,甚至在提高误码率的情况下,总体效率高于样例数据。

我认为出现这种情况的原因是,其中的超时定时器和ACK定时器,我没有完全按照理论计算,而是通过实际数据,取平均值,测得,因此更好地考虑了程序在本机测试环境下产生的一些程序上,物理层上的处理时间,因此效率较好。

改进方法

  • 可以测得更多组数据,我这里仅取了两轮一共20组数据,取其中16组进行计算,若取更多数据可以取10轮200组数据,再除去最高10个及最低10个数据,再进行平均,可以得到更加精确的数据

  • 可以通过增加一些测试程序逻辑,例如测试程序能直接测试数据包的RTT,从而得到更好地超时定时器时间

  • 关于NR_BUFS,在误码率高的情况下,增加程序的窗口,可以提升效率,但在误码率低的情况下,过多的窗口会导致缓冲区的浪费,因此要根据链路速率,误码率,等因素进行合适的调整

通过以上改进方法可以有效提升效率,但因为时间以及工作量原因,不在此进行更加详细的说明。

存在的问题:在“表3 性能测试记录表”中给出了几种测试方案,在测试中你的程序有没有失败,或者,虽未失败,但表现出来的性能仍有差距,你的程序中还存在哪些问题?

  • 均没有失败,并且差距很小,甚至在-f –ber=1e-4的情况下总体效率高出样例8%

  • 程序中存在问题为,没有将最优的窗口大小测试出来,因为需要大量测试,且测试时间一次20min,每组100min,需要时间过大,仅仅采用了一个比较合适的窗口

六、实验结果截图

  • -–utopia 无误码信道数据传输

该图忘记截头了,A效率54.90% B效率96.97%

A效率54.18 B效率96.97

  • 无 站点A分组层平缓方式发出数据,站点B周期性交替“发送100秒,停发100秒”

A效率 53.61% B效率94.38%

  • –-flood —utopia 无误码信道,站点A和站点B的分组层都洪水式产生分组

A效率96.97% B效率96.97%

  • –-flood 站点A/B的分组层都洪水式产生分组

A效率94.35% B效率94.62%

  • —flood -–ber=1e-4 站点A/B的分组层都洪水式产生分组,线路误码率设为10-4

A效率62.91% B效率61.72%

七、研究和探索的问题

7.1 CRC校验能力

首先CRC的检测能力是能检测所有单个错、奇数个错误,和离散的二位错误,以及所有长度为r位的突发差错。并且长度为256Byte的帧出错,且不被发现的概率约为1/2^32次方,甚至概率更低,就以1/2^32次方计算,传输速率为8000bps,假设一天中50%的时间都在检测,则每秒约检测3.9个包,则3.91260*60/2^32为一天出错的概率,则约254924天会出一次错,约700年出一次错。因此能够实现无差错传输,并且我的推算已经是保守计算,实际校验能力可能更强,如果还不放心,可以使用CRC-64进行检验。

7.2 软件测试方面的问题

  • -u 是为了测试软件能否完成传输的基本功能,因为无差错,且数据量并不像洪水模式下这么多。如果-u测试失败,则说明程序有较大问题

  • -f是为了测试软件能否在高压力下完成传输的功能,如果无法通过测试,说明软件中一些定时设置和缓存设置需要改变

  • -b 增加误码率,增大软件的测试压力,理由如2

七、实验总结和心得体会

本次代码的编写时间约为4h,虽然一次编译通过,但是有许多问题等待解决,因此debug,调试参数最终花了一天的时间

  • 完成本实验的实际上机调试约为15h

  • 编程工具上,因为一直使用win系统,以及在初学编程时就用的visual studio进行操作,因此编程工具上没有太大的问题

  • 编程语言上,对指针的使用以及理解仍然有一点问题,但经过反复思考,查阅资料,最后没有太影响到整个编写程序的过程

  • 协议方面遇到了一个十分严重的问题,书上代码中,调整frame_expected, next_frame_to_send 均是通过宏定义的 inc(k),进行调整,我在编写代码时,没有考虑到有轮循的状况,便直接参考了这一方面,导致在运行过程中不断出现data ack timeout,然后数据链路层错误,这一方面我想了很久,最后查看log后才发现需要通过模运算保证frame_expected, next_frame_to_send在正常数据范围内

  • 在使用库的过程中没有发现什么其他的问题,效率方面也没有深入研究源代码分析,主要时间花在调试协议设计上的bug,以及效率优化方面

  • 通过这次实验,我对加深了对C语言的熟悉程度,对于滑动窗口协议有了更加深刻的理解,也提高了我查阅资料,查阅文档的能力,还有对陌生模块调用的能力,因为protocol.c中的函数均不是自己写的,对我整个代码水平有提高

上传的附件 cloud_download 数据链路层实验.rar ( 25.66mb, 2次下载 ) cloud_download 计算机网络实验一.pdf ( 858.62kb, 2次下载 )

发送私信

3
文章数
0
评论数
最近文章
eject