《计算机网络自顶向下》 Miscellaneous Lab1 Implementing a Reliable Transport Protocol（实现可靠的传输协议（下））_综合

文章目录

- 前引
- Lab1 实现可靠的传输协议
- - Lab1 文档查阅（友情提供下载链接）
  - GBN Go-Back-N版本实现思路
  - - 使用到的全局变量的说明
    - 接收方对于乱序到达的数据包采用缓存思路（尽管没采用但是很简单）
    - 累积确认机制实现
    - 环形缓冲区实现
    - A接收方设计实现
  - GBN Go-Back-N版本代码实现

前引

各位看官好这个是续着上面的交替位协议版本也就是比特位的代码实现
由于篇幅和长度限制主要是都放在一篇的话篇幅太长就看起来就不是那么方方便阅读了

GBN的话相对而言就要难的多了因为涉及滑动窗口了我们需要考虑这个问题如果处理而且对于我而言不是很想再用ack 和 nak了第一个是没有没有那么简洁第二个我也没有那么甘心所以之后就会改成用 累积确认ack的方式来弄了

第二个考虑缓冲区的问题因为有可能即将要发送的信息是在窗口大小之外的我们在交替位是通过扩大两条消息发送间隔来做到挨个挨个确定这个样子对于GBN而言的话我们的发送消息间隔就不要再那么短了发送稍微快一点但是对于定时器的时间设置也是一个需要考虑的点

尽管不是很好做但是我们的代码可以基于上一篇博客的继续写难度要小得多了毕竟上一张主要在熟悉实验环境和实验代码那废话少说下面继续走起了

Lab1 实现可靠的传输协议

Lab1 文档查阅（友情提供下载链接）

方便大家下载相关文档下面是查阅链接
Programming Assignment 5: Implementing a Reliable Transport Protocol
prog2.c代码

下面是查阅的文档截图详细的大家还是点进去仔细看看吧这里我用的是谷歌的自带翻译所以查阅起来比较方便阅读

在这里插入图片描述

GBN Go-Back-N版本实现思路

哈哈哈今晚之前终于写完了现在是10:13 这篇博客我可得好好摆摆这个可靠协议传输了不容易啊

经过我的三次大数据测试我的代码没有问题的跑完了这个传输过程毕竟是基于之前的交替位协议来写的 ^^
我第一次测试数据是10 0 0 10
第二次测试数据是10 0.2 0.2 10然后就发现了一个问题做了改进
第三次测试数据是20 0.2 0.2 10 就成功解决了问题至于什么问题还有为什么会出现这个问题我还是来说一下吧

对于这个版本的GBN 我对于上面的交替比特做出了以下改进
1、不再使用 NAK 对于ACK采用累积确认的方法来做滑动窗口
2、对于缓冲区采用了环形缓冲区（哈哈哈之前自制操作系统的时候学到的）尽管没用到但是思路是这个思路
3、美中不足的一点是对于接收方乱序到达的数据包没有采用缓存但其实采用缓存也不难算法思路也很简单之后会介绍别问我为什么不写（懒）

使用到的全局变量的说明

const float send_time_MAX = 14;  //由于消息的传输过去+来回大约为10s + 流水线
const int bufsize = 50;  //缓冲区的大小
struct pkt A_packet[50];    //采用环形缓冲区 如果大于50条信息也可以输出 但是需要改一下while那个地方的信息发出 不能只是'a' - 'z'
int A_seqnum;               //序列号
int A_windowsize_left;      //window剩下的大小
int A_basesend;             //从缓冲区输出的位置
int A_cachepos;             //当前缓冲区最前面储存的位置
int B_acknum;               //记录B 的累计确认位置

接收方对于乱序到达的数据包采用缓存思路（尽管没采用但是很简单）

先聊聊第三点吧其实本身GBN就没做缓存对于乱序到达的直接就丢弃了而只留下我们目前按照顺序下需要的数据包但是为什么没有用呢哈哈因为在我想到的时候我已经完成的差不多了对于B接收方的函数已经不想再动手脚了所以就没有完成下面我就先说一下对于缓存的大概实现思路

每次一个数据包到了之后看一下B_acknum自己及以上的包是否缓存了那怎么看呢用while函数往上走即可每往上走了一步我们就再往Layer5发送数据包然后对于发送方的回应我们每次返回B_acknum最后停在哪里就可以了

累积确认机制实现

哈哈哈这个就更简单了但是对于累计确认的那个发送方接受接收方的数据包处理需要注意以下
累积确认的话我们在A_Layer3层只需要处理比目前B_basesend大的这个可以很好的处理一种情况就是比如10号包 11号包 12号包同时发送但是由于10号包 11号包的传输很慢因为各种事情有延迟或者丢了只要12号包送过去了那么累计确认是对于发送过去的acknum 取最大的即认为最大的值以前的包都是收到了

后面还会说一下对于A接收方的 我自己写的决策

环形缓冲区实现

这个的话我们就用A_cachepos作为所有发送进来的缓冲区尾部
我们用A_basesend作为缓冲区的头部如果满了之后就又回到头部

A接收方设计实现

这个地方我还是稍微修改了一下因为我看到了出现这种情况
就是遇到传回来的包如果ack小于目前的A_basesend 就忽略如果等于的话我们就重发过去一个包不必停止计时器万一我们的计时器关闭了只发送一个包过去试一下接收方累积确认的多少了 -v-

说的有点不清楚大家可以自己带一下数据 - -

GBN Go-Back-N版本代码实现

里面有些关键变量我还是做了注释的这个大家不用担心 ^^
思路我觉得还是很简单的主要是把框架给搞清楚就ok了

实现结果我就不详细弄出来了哈哈哈
但是感兴趣的hxd 可以自己把代码复制了然后带入20 0.2 0.2 10 看看结果

由于模拟器的设定结束是由只要发送了这么多条信息也就是基本上msgs 数目 * time between two msg 就结束如果中间存在丢包或者坏包然后间隙设置的不足够长就会存在消息B方没有收完但大家不用担心消息去哪里了剩下的没有发完都放在缓存区了只要再给一定的时间后面的消息都是会按序发过去的 ^^

最后还想说一句 tcp协议如果接收方没有加缓存那真的是太灾难了 - - 如果就因为basesend没有发出去其他后面的窗口区都发出去了没有缓存后面的包都会丢弃掉所以还是不行的

#include <stdio.h>/* ******************************************************************ALTERNATING BIT AND GO-BACK-N NETWORK EMULATOR: VERSION 1.1 J.F.KuroseThis code should be used for PA2, unidirectional or bidirectionaldata transfer protocols (from A to B. Bidirectional transfer of datais for extra credit and is not required). Network properties:- one way network delay averages five time units (longer if thereare other messages in the channel for GBN), but can be larger- packets can be corrupted (either the header or the data portion)or lost, according to user-defined probabilities- packets will be delivered in the order in which they were sent(although some can be lost). **********************************************************************/#define BIDIRECTIONAL 0 /* change to 1 if you're doing extra credit *//* and write a routine called B_output */
#define TIMER_INTERRUPT 0
#define FROM_LAYER5 1
#define FROM_LAYER3 2#define OFF 0
#define ON 1
#define A 0
#define B 1typedef int bool;
#define true 1
#define false 0/* a "msg" is the data unit passed from layer 5 (teachers code) to layer */
/* 4 (students' code). It contains the data (characters) to be delivered */
/* to layer 5 via the students transport level protocol entities. */
struct msg
{
    char data[20];
};/* a packet is the data unit passed from layer 4 (students code) to layer */
/* 3 (teachers code). Note the pre-defined packet structure, which all */
/* students must follow. */
struct pkt
{
    int seqnum;int acknum;int checksum;char payload[20];
};/********* STUDENTS WRITE THE NEXT SEVEN ROUTINES *********/const float send_time_MAX = 14;
const int bufsize = 50;
struct pkt A_packet[50];    //采用环形缓冲区 如果大于50条信息也可以输出 但是需要改一下while的信息发出 不能只是'a' - 'z'
int A_seqnum;               //序列号
int A_windowsize_left;      //window剩下的大小
int A_basesend;             //从缓冲区输出的位置
int A_cachepos;             //当前缓冲区最前面储存的位置
int B_acknum;               //记录B 的累计确认位置/* called from layer 5, passed the data to be sent to other side */
A_output(message)struct msg message;
{
    int i,checksum = 0;A_cachepos = (A_cachepos + 1) % bufsize;for(i=0;i<20;++i){
    checksum += message.data[i];A_packet[A_cachepos].payload[i] = message.data[i];}A_packet[A_cachepos].seqnum = A_seqnum;A_packet[A_cachepos].acknum = 0;A_packet[A_cachepos].checksum = checksum + A_packet[A_cachepos].seqnum + A_packet[A_cachepos].acknum;++A_seqnum;if(A_windowsize_left >= 1){
    if(A_cachepos == A_basesend) starttimer(A,send_time_MAX);   //如果不是base 定时器不重启tolayer3(A,A_packet[A_cachepos]);                                       //直接送过去}--A_windowsize_left;    //减少缓冲区的大小
}/* called from layer 3, when a packet arrives for layer 4 */
A_input(packet)struct pkt packet;
{
    int checksum = 0,i;for(i=0;i<20;++i)checksum += packet.payload[i];checksum += (packet.acknum + packet.seqnum);if(checksum == packet.checksum && packet.acknum > A_basesend){
    A_windowsize_left += (packet.acknum - A_basesend);A_basesend = packet.acknum % bufsize;stoptimer(A);}else if(packet.acknum == A_basesend || checksum != packet.checksum)tolayer3(A,A_packet[A_basesend]);   //由于代价太大 我们只发送一个数据包 看一下当前累积确认到哪里了 不重新计时 因为有可能还有包没有送过来
}/* called when A's timer goes off */
// 我们采用的是 发送方如果base计时器到时 base 以及 (base + 窗口大小)以内全部缓存的包发出去 接收方的包不是按序到达的直接丢弃
// 由于缓存接收方的包 确认前面的全部到齐 还要写一个检测全部包到齐的算法 - - 其实也不难
// 用一个数组记录包到齐情况 每次到了之后看一下B_acknum 自己及以上的包是否在 每次到了之后用while函数往上走即可 每次acknum 返回while的终点即可A_timerinterrupt()
{
    int i;starttimer(A,send_time_MAX);for(i=A_basesend;i<bufsize;++i,i%=bufsize){
    tolayer3(A,A_packet[i]);if(i == A_cachepos) break;}
}/* the following routine will be called once (only) before any other */
/* entity A routines are called. You can use it to do any initialization */
A_init()
{
    A_seqnum = 0;A_windowsize_left = 8;A_basesend = 0;A_cachepos = -1;
}/* the following rouytine will be called once (only) before any other */
/* entity B routines are called. You can use it to do any initialization */
B_init()
{
    B_acknum = 0;
}/* Note that with simplex transfer from a-to-B, there is no B_output() */
/* called from layer 3, when a packet arrives for layer 4 at B*/
B_input(packet)struct pkt packet;
{
    int i,checksum = 0;for(i=0;i<20;++i)checksum += packet.payload[i];checksum += (packet.seqnum + packet.acknum);struct pkt* p = (struct pkt*)malloc(sizeof(struct pkt));struct pkt send_packet = *p;for(i=0;i<20;++i)send_packet.payload[i] = '\0';send_packet.seqnum = 1;send_packet.acknum = B_acknum;if(checksum == packet.checksum && B_acknum == packet.seqnum){
    send_packet.acknum = B_acknum + 1;tolayer5(B,packet.payload);++B_acknum;}send_packet.checksum = send_packet.seqnum + send_packet.acknum;tolayer3(B,send_packet);
}B_output(message)  /* need be completed only for extra credit */struct msg message;
{
    }/* called when B's timer goes off */
B_timerinterrupt()
{
    }/***************************************************************** ***************** NETWORK EMULATION CODE STARTS BELOW *********** The code below emulates the layer 3 and below network environment:- emulates the tranmission and delivery (possibly with bit-level corruptionand packet loss) of packets across the layer 3/4 interface- handles the starting/stopping of a timer, and generates timerinterrupts (resulting in calling students timer handler).- generates message to be sent (passed from later 5 to 4)THERE IS NOT REASON THAT ANY STUDENT SHOULD HAVE TO READ OR UNDERSTAND THE CODE BELOW. YOU SHOLD NOT TOUCH, OR REFERENCE (in your code) ANY OF THE DATA STRUCTURES BELOW. If you're interested in how I designed the emulator, you're welcome to look at the code - but again, you should have to, and you defeinitely should not have to modify ******************************************************************/struct event {
    float evtime;           /* event time */int evtype;             /* event type code */int eventity;           /* entity where event occurs */struct pkt *pktptr;     /* ptr to packet (if any) assoc w/ this event */struct event *prev;struct event *next;};
struct event *evlist = NULL;   /* the event list */int TRACE = 1;             /* for my debugging */
int nsim = 0;              /* number of messages from 5 to 4 so far */
int nsimmax = 0;           /* number of msgs to generate, then stop */
float time = 0.000;
float lossprob;            /* probability that a packet is dropped */
float corruptprob;         /* probability that one bit is packet is flipped */
float lambda;              /* arrival rate of messages from layer 5 */
int   ntolayer3;           /* number sent into layer 3 */
int   nlost;               /* number lost in media */
int ncorrupt;              /* number corrupted by media*/main()
{
    struct event *eventptr;struct msg  msg2give;struct pkt  pkt2give;int i,j;char c;init();A_init();B_init();while (1){
    eventptr = evlist;            /* get next event to simulate */if (eventptr==NULL)goto terminate;evlist = evlist->next;        /* remove this event from event list */if (evlist!=NULL)evlist->prev=NULL;if (TRACE>=2){
    printf("\nEVENT time: %f,",eventptr->evtime);printf(" type: %d",eventptr->evtype);if (eventptr->evtype==0)printf(", timerinterrupt ");else if (eventptr->evtype==1)printf(", fromlayer5 ");elseprintf(", fromlayer3 ");printf(" entity: %d\n",eventptr->eventity);}time = eventptr->evtime;        /* update time to next event time */if (nsim==nsimmax)break;                        /* all done with simulation */if (eventptr->evtype == FROM_LAYER5){
    generate_next_arrival();   /* set up future arrival *//* fill in msg to give with string of same letter */j = nsim % 26;for (i=0; i<20; i++)msg2give.data[i] = 97 + j;if (TRACE>2){
    printf(" MAINLOOP: data given to student: ");for (i=0; i<20; i++)printf("%c", msg2give.data[i]);printf("\n");}nsim++;if (eventptr->eventity == A)A_output(msg2give);elseB_output(msg2give);}else if (eventptr->evtype ==  FROM_LAYER3){
    pkt2give.seqnum = eventptr->pktptr->seqnum;pkt2give.acknum = eventptr->pktptr->acknum;pkt2give.checksum = eventptr->pktptr->checksum;for (i=0; i<20; i++)pkt2give.payload[i] = eventptr->pktptr->payload[i];if (eventptr->eventity == A)      /* deliver packet by calling */A_input(pkt2give);            /* appropriate entity */elseB_input(pkt2give);free(eventptr->pktptr);          /* free the memory for packet */}else if (eventptr->evtype ==  TIMER_INTERRUPT){
    if (eventptr->eventity == A)A_timerinterrupt();elseB_timerinterrupt();}else    printf("INTERNAL PANIC: unknown event type \n");free(eventptr);}terminate:printf(" Simulator terminated at time %f\n after sending %d msgs from layer5\n",time,nsim);
}init()                         /* initialize the simulator */
{
    int i;float sum, avg;float jimsrand();printf("----- Stop and Wait Network Simulator Version 1.1 -------- \n\n");printf("Enter the number of messages to simulate: ");scanf("%d",&nsimmax);       // 发送数据包数目printf("Enter packet loss probability [enter 0.0 for no loss]:");scanf("%f",&lossprob);      // 丢包率printf("Enter packet corruption probability [0.0 for no corruption]:");scanf("%f",&corruptprob);   // 包损坏率printf("Enter average time between messages from sender's layer5 [ > 0.0]:");scanf("%f",&lambda);        // 平均物理层传输时间printf("Enter TRACE:");scanf("%d",&TRACE);         // 追踪 用于调试的srand(9999);              /* init random number generator */sum = 0.0;                /* test random number generator for students */for (i=0; i<1000; i++)sum=sum+jimsrand();    /* jimsrand() should be uniform in [0,1] */avg = sum/1000.0;         // 随机概率 估计值在0.25 ~ 0.75if (avg < 0.25 || avg > 0.75){
    printf("It is likely that random number generation on your machine\n" );printf("is different from what this emulator expects. Please take\n");printf("a look at the routine jimsrand() in the emulator code. Sorry. \n");exit(0);}ntolayer3 = 0;nlost = 0;ncorrupt = 0;time=0.0;                    /* initialize time to 0.0 */generate_next_arrival();     /* initialize event list */
}/****************************************************************************/
/* jimsrand(): return a float in range [0,1]. The routine below is used to */
/* isolate all random number generation in one location. We assume that the*/
/* system-supplied rand() function return an int in therange [0,mmm] */
/****************************************************************************/float jimsrand()
{
    double mmm = 0x7fff;   /* largest int - MACHINE DEPENDENT!!!!!!!! */float x;                   /* individual students may need to change mmm */x = rand()/mmm;            /* x should be uniform in [0,1] */return(x);
}/********************* EVENT HANDLINE ROUTINES *******/
/* The next set of routines handle the event list */
/*****************************************************/generate_next_arrival()
{
    double x,log(),ceil();struct event *evptr;char *malloc();float ttime;int tempint;if (TRACE>2)printf(" GENERATE NEXT ARRIVAL: creating new arrival\n");x = lambda*jimsrand()*2;  /* x is uniform on [0,2*lambda] *//* having mean of lambda */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtime =  time + x;evptr->evtype =  FROM_LAYER5;if (BIDIRECTIONAL && (jimsrand()>0.5) )evptr->eventity = B;elseevptr->eventity = A;insertevent(evptr);
}// 由之前生成的包中的eventtime决定 传输顺序 在队列中的什么位置
insertevent(p)struct event *p;
{
    struct event *q,*qold;if (TRACE>2){
    printf(" INSERTEVENT: time is %lf\n",time);printf(" INSERTEVENT: future time will be %lf\n",p->evtime);}q = evlist;     /* q points to header of list in which p struct inserted */if (q==NULL)    /* list is empty */{
    evlist=p;p->next=NULL;p->prev=NULL;}else{
    for (qold = q; q !=NULL && p->evtime > q->evtime; q=q->next)qold=q;if (q==NULL)    /* end of list */{
    qold->next = p;p->prev = qold;p->next = NULL;}else if (q==evlist) /* front of list */{
    p->next=evlist;p->prev=NULL;p->next->prev=p;evlist = p;}else            /* middle of list */{
    p->next=q;p->prev=q->prev;q->prev->next=p;q->prev=p;}}
}printevlist()
{
    struct event *q;int i;printf("--------------\nEvent List Follows:\n");for(q = evlist; q!=NULL; q=q->next)printf("Event time: %f, type: %d entity: %d\n",q->evtime,q->evtype,q->eventity);printf("--------------\n");
}/********************** Student-callable ROUTINES ***********************//* called by students routine to cancel a previously-started timer */
stoptimer(AorB)int AorB;  /* A or B is trying to stop timer */
{
    struct event *q,*qold;if (TRACE>2)printf(" STOP TIMER: stopping timer at %f\n",time);/* for (q=evlist; q!=NULL && q->next!=NULL; q = q->next) */for (q=evlist; q!=NULL ; q = q->next){
    /* remove this event */if ( (q->evtype==TIMER_INTERRUPT  && q->eventity==AorB) ){
    if (q->next==NULL && q->prev==NULL)evlist=NULL;         /* remove first and only event on list */else if (q->next==NULL) /* end of list - there is one in front */q->prev->next = NULL;else if (q==evlist)     /* front of list - there must be event after */{
    q->next->prev=NULL;evlist = q->next;}else    /* middle of list */{
    q->next->prev = q->prev;q->prev->next =  q->next;}free(q);return;}}printf("Warning: unable to cancel your timer. It wasn't running.\n");
}starttimer(AorB,increment)int AorB;  /* A or B is trying to stop timer */float increment;
{
    struct event *q;struct event *evptr;char *malloc();if (TRACE>2)printf(" START TIMER: starting timer at %f\n",time);/* be nice: check to see if timer is already started, if so, then warn *//* for (q=evlist; q!=NULL && q->next!=NULL; q = q->next) */for (q=evlist; q!=NULL ; q = q->next){
    if (q->evtype==TIMER_INTERRUPT  && q->eventity==AorB ){
    printf("Warning: attempt to start a timer that is already started\n");return;}}/* create future event for when timer goes off */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtime =  time + increment;evptr->evtype =  TIMER_INTERRUPT;evptr->eventity = AorB;insertevent(evptr);
}/************************** TOLAYER3 ***************/
tolayer3(AorB,packet)int AorB;  /* A or B is trying to stop timer */
struct pkt packet;
{
    struct pkt *mypktptr;struct event *evptr,*q;char *malloc();float lastime, x, jimsrand();int i;ntolayer3++;/* simulate losses: */if (jimsrand() < lossprob){
    nlost++;if (TRACE>0)printf(" TOLAYER3: packet being lost\n");return;}/* make a copy of the packet student just gave me since he/she may decide */
/* to do something with the packet after we return back to him/her */mypktptr = (struct pkt *)malloc(sizeof(struct pkt));mypktptr->seqnum = packet.seqnum;mypktptr->acknum = packet.acknum;mypktptr->checksum = packet.checksum;for (i=0; i<20; i++)mypktptr->payload[i] = packet.payload[i];if (TRACE>2){
    printf(" TOLAYER3: seq: %d, acknum %d, check: %d ", mypktptr->seqnum,mypktptr->acknum,  mypktptr->checksum);for (i=0; i<20; i++)printf("%c",mypktptr->payload[i]);printf("\n");}/* create future event for arrival of packet at the other side */evptr = (struct event *)malloc(sizeof(struct event));evptr->evtype =  FROM_LAYER3;   /* packet will pop out from layer3 */evptr->eventity = (AorB+1) % 2; /* event occurs at other entity */evptr->pktptr = mypktptr;       /* save ptr to my copy of packet *//* finally, compute the arrival time of packet at the other end.medium can not reorder, so make sure packet arrives between 1 and 10time units after the latest arrival time of packetscurrently in the medium on their way to the destination */lastime = time;/* for (q=evlist; q!=NULL && q->next!=NULL; q = q->next) */for (q=evlist; q!=NULL ; q = q->next){
    if ( (q->evtype==FROM_LAYER3  && q->eventity==evptr->eventity) )lastime = q->evtime;}evptr->evtime =  lastime + 1 + 9*jimsrand();/* simulate corruption: */if (jimsrand() < corruptprob){
    ncorrupt++;if ( (x = jimsrand()) < .75)mypktptr->payload[0]='Z';   /* corrupt payload */else if (x < .875)mypktptr->seqnum = 999999;elsemypktptr->acknum = 999999;if (TRACE>0)printf(" TOLAYER3: packet being corrupted\n");}if (TRACE>2)printf(" TOLAYER3: scheduling arrival on other side\n");insertevent(evptr);
}tolayer5(AorB,datasent)int AorB;char datasent[20];
{
    int i;if (TRACE>2){
    printf(" TOLAYER5: data received: ");for (i=0; i<20; i++)printf("%c",datasent[i]);printf("\n");}
}

《计算机网络自顶向下》 Miscellaneous Lab1 Implementing a Reliable Transport Protocol（实现可靠的传输协议（下））