前言

一个实验六个任务，实验文档一划划不到底。。看来老师们是真下功夫了啊

本文主要展示了作者在完成SZU计算机网络实验3的思路及过程，实验主要包括：

  1. 理解rdt2.1
  2. 实现rdt2.2
  3. 实现rdt3.0
  4. 实现回退N步（GBN）机制
  5. 实现面向无连接的可靠传输机制（GBN）
  6. 进行量化分析

文中出现的状态机演示图均基于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分支模拟状态机的运行，代码如下：

发送端

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
 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_time
    unsigned 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);
        }
    }
}

接收端

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
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和重传包；

为了统计数据包总数，我们在库文件中引入静态变量：

1
static unsigned long OverHead = 0;

在每次发送数据包，即调用udt_send时，将该变量+1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的函数：
1
2
3
4
unsigned long getOverHead(){
    printf("OverHead: %d\n", OverHead);
    return OverHead;
}

我们以相同的手段统计数据包损坏数，并计算数据包错误频率：

数据包错误频率 = 数据包损坏数 / 数据包总数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

而对于有效吞吐量，库文件中已经有提供函数给我们直接获取，需要我们传入程序运行的始末时间：

1
2
3
4
5
6
7
8
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 second
    printf("Total time elapsed: %lu ms\n", (end_time - start_time));
    printf("Goodput: %f B/s\n", goodput);
    return goodput;
}

在server.c中调用以上函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    // get start_time
    unsigned long start_time = GetTickCount();

    while (!finish_send)
    {
        /**状态机**/ 
    }
    
    // get end_time
    unsigned long end_time = GetTickCount();
    
    // calculate goodput
    calculate_goodput(start_time, end_time);
    // get overhead
    getOverHead();
    // get tamper rate
    calculate_tamper_rate();
}

由于默认的数据包数量是200，在该条件下，前后间隔时间太短接近于0，会导致计算吞吐量得到无穷大。因此在rdt.h中修改数据包数为20000：

1
#define TOTAL_PACKETS 20000

先运行接收端再运行客户端，分别将输出内容重定向到文本文件中：

1
root@Andrew:/mnt/d/.c/computernetwork/exp3-1# ./client.exe >client.txt

1
root@Andrew:/mnt/d/.c/computernetwork/exp3-1# ./server.exe > server.txt

在clumsy中设定Tamper = 0.3，测试结果如下：

1
2
3
4
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表格中，并绘制曲线如下：

image.png

image.png

根据图像可以看出，数据包总数 与 数据包错误频率 之间有呈非线性关系的趋势，而有效吞吐量 与 数据包错误频率 之间呈线性关系

二、实现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），如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 数据包定义
typedef enum
{
    // rdt 2.1
    // PACKET_TYPE_ACK = 1,
    // PACKET_TYPE_DATA = 0,
    // PACKET_TYPE_NAK = -1
    
    // rdt 2.2
    PACKET_TYPE_ACK_ODD = 1,
    PACKET_TYPE_DATA = 0,
    PACKET_TYPE_ACK_EVEN = -1
} Packet_Type;

那么就不需要原本的isACK以及isNAK，将其注释并引入isACKEven和isACKOdd判断数据包类型：

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
// 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）：

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
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.2
    currentState = 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.2
case 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的结果进行比较，绘制曲线如下

image.png

image.png

可以看到，rdt2.2对比rdt2.1发送的数据包总量更少，且有效吞吐量更高，说明rdt2.2确实减少了冗余数据包的发送，相比rdt2.1更为高效

三、实现rdt3.0

1. 理解rdt3.0

上述模型能够解决的只是数据包损坏的问题，一旦出现某个数据包丢包，对于以上模型都无法作出响应保证传输的可靠性

因此rdt3.0引入超时重传：

在发送端，每发一个数据包便开启一个计时器，当计时器超时仍未正常收到该数据包对应的ACK时，重传该数据包并重启计时器。

在rdt3.0中，只有计时器超时才会触发重传动作，收到受损的ACK或不正确的ACK不会触发重传。

因此，发送端状态机如下：

2. rdt3.0代码实现

首先定义定时器传入的函数，内容为重传当前数据包：

1
2
3
4
5
6
7
void CALLBACK timeout_function(void *lpParam, boolean timeout){
    if(timeout ){
        printf("Time out!\n");
        start_timer(timeout_function);
        udt_send(sockfd, sndpkt, &client_addr);
    }
}

在状态STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE和STATE_WAIT_FOR_CALL_ODD_FROM_ABOVE中，完成发送数据包时启动定时器；在状态STATE_WAIT_ACK_EVEN和STATE_WAIT_ACK_ODD中，修改代码使只有成功接收时才执行动作：

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
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++;
    start_timer(timeout_function);  // key step

    currentState = STATE_WAIT_ACK_EVEN;
    break;

case STATE_WAIT_ACK_EVEN:
    printf("STATE_WAIT_ACK_EVEN\n");
    rcvpkt = rdt_rcv(sockfd, &client_addr);

    // if (corrupt(rcvpkt) || isACKOdd(rcvpkt))         
    // {
    //     udt_send(sockfd, sndpkt, &client_addr);
    // }
    // else 
    if (notcorrupt(rcvpkt) && isACKEven(rcvpkt))    // 只有成功接收才有动作，其它无动作
    {
        free(sndpkt);

        stop_timer();   // key step
        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++;
    start_timer(timeout_function);  // key step

    currentState = STATE_WAIT_ACK_ODD;
    break;


case STATE_WAIT_ACK_ODD:
    printf("STATE_WAIT_ACK_ODD\n");
    rcvpkt = rdt_rcv(sockfd, &client_addr);
    
    // if (corrupt(rcvpkt) || isACKEven(rcvpkt))
    // {
    //     udt_send(sockfd, sndpkt, &client_addr);
    // }
    // else 
    if (notcorrupt(rcvpkt) && isACKOdd(rcvpkt))  // 只有成功接收才有动作，其它无动作
    {
        free(sndpkt);
        
        stop_timer();   // key step
        currentState = STATE_WAIT_FOR_CALL_EVEN_FROM_ABOVE;
        if (seq == TOTAL_PACKETS)
            finish_send = TRUE;
    }
    free(rcvpkt);
}

3. rdt3.0测试

在clumsy中设置 数据包损坏率Tamper 为1，改变 丢包率Drop 依次为0.3, 0.5, 1, 2, 3, 5, 10, 20, 30

分别绘制 数据包总数OverHead 和 有效吞吐量Goodput 关于 丢包率 的关系曲线如下：

image.png

image.png

发现 数据包总数-丢包率 的图像呈非线性曲线增长，而 有效吞吐量-丢包率 的图像呈指数型下降

四、实现基于ACK的GBN

前面说到的模型都是基于停等协议，需要收到前一个数据包对应的ACK才会接着发送下一个数据包，这种情况下信道占用率很不可观

回退N帧协议（Go Back N，or GBN）在发送端维护一个长度为N的窗口，已收到ACK部分的末位置base，以及下一个要发送的数据包的位置next_seq_num；在接收端按顺序逐一接收并发送ACK

根据文档给出的状态机模型，实现GBN的发送端和接收端如下：

发送端：

1
2
int N = 10;
int base = 1, next_seq_num = 1;                 // 定义GBN所需全局变量

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
void sending_packets()
{
    // 初始化状态

    char *data;
    Packet *rcvpkt;
    
    // get start_time
    unsigned long start_time = GetTickCount();

    while (base != TOTAL_PACKETS + 1)
    {
        while(next_seq_num < base + N && next_seq_num <= TOTAL_PACKETS){
            data = rdt_send(next_seq_num);
            sndpkt[next_seq_num] = make_pkt(next_seq_num, PACKET_TYPE_DATA, data);
            udt_send(sockfd, sndpkt[next_seq_num], &client_addr);
            if(base == next_seq_num)
                start_timer(timeout_function);
            next_seq_num++;
        }
        rcvpkt = rdt_rcv(sockfd, &client_addr);

        if(notcorrupt(rcvpkt)){
            base = get_ack_num(rcvpkt) + 1;
            if(base == next_seq_num)
                stop_timer();
            else
                start_timer(timeout_function);
        }

    }

    // get end_time
    unsigned long end_time = GetTickCount();

    // calculate goodput
    calculate_goodput(start_time, end_time);
    // get overhead
    getOverHead();
    // get tamper rate
    calculate_tamper_rate();
}

接收端：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void receiving_packets(){
    Packet *rcvpkt;
    Packet* sndpkt;
    int rcv_seq = -1;
    
    int expected_seq_num = 1;
    while (TRUE)
    {
        rcvpkt = rdt_rcv(sockfd, &server_addr);
        if(notcorrupt(rcvpkt) && has_seq_num(rcvpkt, expected_seq_num)){
            extract_data(rcvpkt);
            sndpkt = make_pkt(expected_seq_num, PACKET_TYPE_ACK, NULL);
            udt_send(sockfd, sndpkt, &server_addr);
            expected_seq_num++;
        }else if(notcorrupt(rcvpkt) && rcvpkt->seq < expected_seq_num){
            sndpkt = make_pkt(rcvpkt->seq, PACKET_TYPE_ACK, NULL);
            udt_send(sockfd, sndpkt, &server_addr);
        }
    }
}
1
2
3
boolean has_seq_num(Packet *rcvpkt, int expected_seq_sum){
    return rcvpkt->seq == expected_seq_sum;
}

五、实现基于NAK的GBN

该模型中，在发送端缓存数据包后持续发送，直到收到接收端返回的NAK错误，再重发出错数据包，并继续持续发送之后的数据包；在接收端按顺序逐一接收，如出现错误则发送NAK

代码实现上，在发送端维护两个全局变量：next_seq_num表示下一个要发送的数据包下标，naks_done表示关于NAK的错误已被处理，用于两个线程间通信，截断持续发送的过程

发送端：

1
2
3
// 自定义全局变量
int next_seq_num = 0;
boolean naks_done = TRUE;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char *data;
for (int i = 0; i < TOTAL_PACKETS; ++i)
{
    // 预先装填所有数据
    data = rdt_send(i);
    sndpkt[i] = make_pkt(i, PACKET_TYPE_DATA, data);
    
}

while(next_seq_num < TOTAL_PACKETS){
    if(naks_done){
        udt_send(sockfd, sndpkt[next_seq_num], &client_addr);
        next_seq_num++;   
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned long receive_naks(LPVOID pl_param)
{
    // 服务器应一直监听来自客户端的数据包

    // int last_nak_num = -1;
    while (1)
    {
        // TODO: 收到NAK处理重发
        Packet *rcvpkt = rdt_rcv(sockfd, &client_addr);
        naks_done = FALSE;

        if(notcorrupt(rcvpkt) && isNAK(rcvpkt)){ 
            udt_send(sockfd, sndpkt[rcvpkt->seq], &client_addr);    // 防止最后一个丢包
            next_seq_num = rcvpkt->seq + 1;
        }
        naks_done = TRUE;
    }
}

接收端：

1
2
3
// 定义为全局
int max_seq_received = -1;   // 目前为止按序接收到的最大序号
boolean packet_received = 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
// LOOP 1: 检查是否收到的包是否发生了比特错误
if (corrupt(rcvpkt))
{
    // TODO
    sndpkt = make_pkt(max_seq_received + 1, PACKET_TYPE_NAK, NULL);
    udt_send(sockfd, sndpkt, &server_addr);
    continue;
}

// LOOP 2: 检查是否收到的包是否为按序到达的
if (rcvpkt->seq == max_seq_received + 1)
{
    // TODO
    extract_data(rcvpkt);
    max_seq_received++;
    if(max_seq_received == TOTAL_PACKETS - 1)
        packet_received = 1;
    else{
        stop_timer();
        start_timer(timer_process);
    }                
}

// LOOP 3: 检查是否收到的包是否为乱序到达的
if (rcvpkt->seq > max_seq_received + 1)
{
    // TODO
    printf("receive a packet out of order: %d\n", rcvpkt->seq);
    sndpkt = make_pkt(max_seq_received + 1, PACKET_TYPE_NAK, NULL);
    udt_send(sockfd, sndpkt, &server_addr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// 定时器到期后触发的回调函数
VOID CALLBACK timer_process(PVOID lpParam, BOOLEAN TimerOrWaitFired)
{
    if (TimerOrWaitFired)
    {
        // TODO: 定时器到期处理逻辑
        start_timer(timer_process);
        Packet *sndpkt = make_pkt(max_seq_received + 1, PACKET_TYPE_NAK, NULL);
        udt_send(sockfd, sndpkt, &server_addr);

        // Notice: 若有需要，可以重置定时器，为下一个预期的数据包启动新的定时器，如在这里继续调用 set_or_update_timer 函数
    }
}

六、量化分析

该部分实验将测试ACK-GBN和NAK-GBN的执行过程中，数据包总量OverHead和有效吞吐量Goodput关于多个不同自变量的变化关系

1. 关于数据包错误率

image.png

image.png

2. 关于丢包率

image.png

image.png

3. 关于乱序数据包比例

image.png

image.png

4. 实验分析

通过对比发现，NAK-GBN在上述所有情况中的OverHead都要比ACK-GBN要少，且Goodput都远远超过ACK-GBN（几十倍）