数据链路层

//
// Created by ricardo on 23-3-17.
//

#ifndef DATA_LINK_LAYER_PROTOCOL_H
#define DATA_LINK_LAYER_PROTOCOL_H

#define MAX_PKT 1024

typedef enum {
    false,
    true
} boolean;

typedef unsigned int seq_nr;

typedef struct {
    unsigned char data[MAX_PKT];
} packet;

typedef enum {
    data,
    ack,
    nck,
} frame_kind;

typedef struct {
    frame_kind kind;
    seq_nr seq;
    seq_nr ack;
    packet info;
} frame;

void wait_for_event(event_type *event);

void from_network_layer(packet *p);

void to_network_layer(packet* p);

void from_physical_layer(packet *p);

void to_physical_layer(packet* p);

void start_timer(seq_nr k);

void end_timer(seq_nr k);

void start_ack_time();

void end_ack_time();

void enable_network_layer();

void disable_network_layer();

#endif //DATA_LINK_LAYER_PROTOCOL_H

协议1 乌托邦单工协议

这个协议假设：

通信的单工的
通信是无错的
接收方有着无限的缓存

即：这个协议不需要任何的错误控制和流量控制

//
// Created by ricardo on 23-3-17.
//

typedef enum {
    frame_arrival
} event_type;
#include "protocol.h"

void send() {
    frame s;
    packet buffer;

    while (true) {
        from_network_layer(&buffer);
        s.info = buffer;
        to_physical_layer(&s);
    }
}

void receive() {
    frame r;
    event_type event;

    while (true) {
        wait_for_event(&event);

        from_physical_layer(&r);
        to_network_layer(&r.info);
    }
}

协议2 单工发送——等待协议

这个协议假设：

通信是单工的
通信是没有错误的
接受者有着有限的缓存

这个协议使用了一种发送——等待机制：

发送方发送数据开始等待
接收方接受数据并发送确认帧ACK
发送方收到确认帧，继续发送

//
// Created by ricardo on 23-3-17.
//

typedef enum {
    frame_arrival
} event_type;

#include "protocol.h"

void send()
{
    frame s;
    packet buffer;
    event_type event;

    while (true)
    {
        from_network_layer(&buffer);
        s.info = buffer;
        to_physical_layer(&s);
        wait_for_event(&event);
    }
}

void receive()
{
    frame r, s;
    event_type event;

    while (true) {
        wait_for_event(&event);
        from_physical_layer(&r);
        to_network_layer(&r.info);
        to_physical_layer(&s);
    }
}

协议3 带有重试的主动确认协议

如果将协议2应用在不可靠的传输信道上：

传输过程中帧损坏了：

接受者可以使用CRC纠错码发现和丢弃这个损坏的帧

发送者在等待ACK帧的过程中超时之后重新发送这个帧
传输过程中帧丢失了：

如果是数据帧丢失了：发送者超时之后重新发送

如果是ACK帧丢失了：发送者超时之后重新发送

但是ACK帧丢失之后重传可能遇到一个问题：发送者重新发送的数据帧会被接受者当作是新的数据帧。

为了解决这个问题，我们可以在数据帧的帧头上添加序列编号。

在这里由于实际上只需要两种状态，序列编号只需要一个比特，传输0或者1就可以了。

这样就将这个协议改造成了一个自动重传协议Automatic Repeat reQuest aka ARQ。

这个协议称为：单向传输数据的停止等待ARQ协议

发送方在数据帧中添加校验字段，发送之后启动超时定时器
接受方在接受数据之后利用校验码检查错误，出错就丢弃数据，校验无误的情况下发送确认帧
发送法收到确认帧，发送下一帧，重启定时器
如果发送方定时器超时，发送方重新发送刚发送的数据帧
在数据帧还携带一个序号，接受方根据序号来判断是否是重复发送的数据帧
确认帧中也携带序号，发送方通过序号确定是否是重复的确认帧

‍那么确认帧是必须携带序号吗：

在确认帧发送比较缓慢的时候，缺少序号的确认帧就可能导致问题。

因此确认帧是需要序号的，发送方通过序确认是否是重复的确认帧。

#define MAX_SEQ 1
typedef enum
{
    frame_arrival,
    cksum_err,
    timeout
} event_type;

#include "protocol.h"

void send()
{
    seq_nr next_frame_to_send;
    frame s;
    packet buffer;
    event_type event;

    next_frame_to_send = 0;
    from_network_layer(&buffer);
    while (true)
    {
        s.info = buffer;
        s.seq = next_frame_to_send;
        to_physical_layer(&s);
        start_timer(s.seq);
        wait_for_event(&event);

        if (event == frame_arrival)
        {
            from_physical_layer(&s);
            if (s.ack == next_frame_to_send)
            {
                stop_timer(s.ack);
                from_network_layer(&buffer);
                next_frame_to_send = 1 - next_frame_to_send;
            }
        }
    }
}

void receive()
{
    seq_nr frame_expected;
    frame r, s;
    event_type event;

    frame_expected = 0;
    while (true)
    {
        wait_for_event(&event);

        if (event == frame_arrival)
        {
            from_physical_layer(&r);
            if (r.seq == frame_expected)
            {
                to_network_layer(&r.info);
                frame_expected = 1 - frame_expected;
            }
            s.ack = 1 - frame_expected;
            to_physical_layer(&s);
        }
    }
}

协议4 实用的停止等待ARQ协议

设计原则：

在数据帧中增加校验字段，发送帧之后启动超时定时器
接收方对于收到的数据进行校验，如果出错则丢弃，如果校验无错，就发送确认帧或者通过下一个帧进行捎带确认
收到确认之后发送下一帧，重启定时器
如果定时器超时，则重新发送刚发送的数据帧
数据帧中携带发送序号，根据需要判断是否需要是重复的数据帧
根据确认帧判断是否重复的确认帧

捎带应答：

当收到一个数据帧时，不同于立刻发送一个确认帧，而是等待网络层给出下一个需要发送的数据包，并把确认帧附在需要发送的数据帧之后一同发送出去。

在这个过程中，发送方和确认方都需要维持一个滑动窗口。

#define MAX_SEQ 1
typedef enum
{
    frame_arrival,
    cksum_err,
    timeout
} event_type;

#include "protocol.h"

void protocol()
{
    seq_nr next_frame_to_send;
    seq_nr frame_expected;

    frame r, s;
    packet buffer;
    event_type event;

    from_network_layer(&buffer);
    s.info = buffer;
    s.seq = next_frame_to_send;
    s.ack = 1 - frame_expected;
    to_physical_layer(&s);
    start_timer(s.seq);

    while (true)
    {
        wait_for_event(&event);

        if (event == frame_arrival)
        {
            from_physical_layer(&r);

            if (r.seq = frame_expected)
            {
                to_network_layer(&r.info);
                frame_expected = 1 - frame_expected;
            }

            if (r.ack == next_frame_to_send)
            {
                stop_timer(r.ack);
                from_network_layer(&buffer);
                next_frame_to_send = 1 - next_frame_to_send;
            }

            s.info = buffer;
            s.seq = next_frame_to_send;
            s.ack = 1 - frame_expected;
            to_physical_layer(&s);
            start_timer(s.seq);
        }
    }
}

但是这个协议的效率非常的低。

在大部分的时间里，使用这个协议的信道都被阻塞等待确认帧。

协议5 回退N步协议

设计原则：

发送方和接收方都需要维持一个滑动窗口：

发送窗口：发送帧的缓冲队列

接受窗口：接受帧的缓冲队列
发送者将被允许在收到确认帧之前发送多个数据帧
如果接收方发现了传输错误，那么发送方必须回退到这个错误的帧重发进行纠错，已经发送的数据帧就废弃了

‍发送窗口大小的约束：

当序号的位数只有 $n$ 时，假设发送窗口的大小达到 $2^{n}$ 。

如果发送方发送所有可以发送的帧，而接收方在接受所有的数据之后发送确认帧时失败了，但是此时接受者的序号和发送者的序号相同，接受者会把发送者重新发送的帧当作新发送的帧接受。

‍因此该协议的发送窗口大小必须满足：

$Win d o wS i ze \leq 2^{n} - 1$

式子中的n表示序号的位数。

协议5的示例实现：

协议6 选择重传协议

Select Repeat/Select Reject。

接收方的缓存大于1，可以接受乱序的帧，并且只要求重传错误的帧。

选择重传中对于窗口大小的限制：

发送窗口和接受窗口大小之和不能大于 $2^{n}$ :

$w_{s} + w_{r} \leq 2^{n}$

发送窗口的大小大于接受窗口的大小
一般来说，取发送窗口和接受窗口大小为 $2^{n - 1}$

协议6相对于协议5的改进：

设置确认帧定时器：

在收到数据帧之后，等待一段时间的回传帧以进行捎带确认。如果定时器超时还没有等到回传的数据，直接发送确认帧。

利用这种方式减少单独确认帧的发送，提高信道的使用效率。
NAK帧：对于同一帧的错误，发送一次NAK

NAK帧的序号就是出错帧的序号。

帧接受之后校验出错和序号不对都算是出错。

协议6的示例实现：