网原第一次实验:滑动窗口协议(Netriver平台)

在debug两个小时之后,我现在只想高呼一声:“垃圾Netriver!垃圾测试服务器!”首先,在Win8以上的系统都运行不了,真令人头大,非得让我装一个XP的虚拟机。而且,同样的程序的运行结果时对时错,都不知道什么时候算是对了。算了,总之先讲下实验内容吧。

实验内容

实验目的

要求实现滑动窗口协议中的1bit滑动窗口协议和退后N帧协议,更深刻地理解滑动窗口协议。

实验机制

窗口机制简介

在滑动窗口协议中,发送方始终保持一个已发送但尚未确认的帧的序号表,称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号,下界表示未得到确认的帧的最小序号。发送窗口大小=上界-下界,大小可变。发送方每发送一个帧,序号取上界值,上界加1;每接收到一个确认序号等于发送窗口下界的正确响应帧,下界+1;若确认序号落在发送窗口之内,则发送窗口下界连续+1,直到发送窗口下界=确认序号+1。

接收方有一个接收窗口,大小固定,但不一定与发送窗口相同。接收窗口的上界表示允许接收的最大序号,下界表示希望接收的序号。接收窗口容纳允许接收的信息帧,落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收,并产生一个响应帧,上界、下界都+1,接收窗口大小保持不变。

从滑动窗口的角度来分析1bit滑动窗口和退后N帧这两种协议,它们的差别仅在于各自窗口的大小不同而已。1bit滑动窗口的发送窗口=1,接收窗口=1;退后N帧协议的发送窗口>1,接收窗口=1。

1bit滑动窗口协议

当发送窗口和接收窗口的大小固定为1时(即1bit滑动窗口协议),滑动窗口协议退化为停等协议(stop and wait)。该协议规定发送方每发送一帧后就要停下来,等待接收方已正确接收的确认(acknowledgement)返回后才能继续发送下一帧,信道利用率很低。由于接收方需要判断接收到的帧是新发的帧还是重复的帧,因此发送方要为每一个帧加一个序号。停等协议规定只有一帧完全发送成功后,才能发送新的帧,因而只用1bit来编号就够了。

退后N帧协议

在退后N帧协议中,发送方在发完一个数据帧后,不必停下来等待确认帧,而是连续发送若干个数据帧。发送方在每发送完一个数据帧时,都要对该帧设置计时器。若在所设置的超时时间内未收到该帧的确认帧,则该帧就被判为出错或丢失,发送方就必须重新发送该帧及其后的所有帧。

具体内容

根据滑动窗口协议原理,实现滑动窗口协议中发送方的功能,对发送方发出的帧进行缓存,等待确认,并在超时发生时对部分帧进行重传。具体来说,要求用C语言编写1bit滑动窗口协议和退后N帧协议函数,响应系统的发送请求、接收帧消息以及超时消息,并根据滑动窗口协议进行相应处理。实验所需的模板见下面。

实验模板

#include "sysinclude.h"
 
extern void SendFRAMEPacket(unsigned char* pData, unsigned int len);
 
#define WINDOW_SIZE_STOP_WAIT 1
#define WINDOW_SIZE_BACK_N_FRAME 4
 
typedef enum {data, ack, nak} frame_kind;
 
typedef struct frame_head
{
    frame_kind kind;  // 帧类型
    unsigned int seq;  // 序号
    unsigned int ack;  // 确认号
    unsigned char data[100];  // 数据
};
 
typedef struct frame
{
    frame_head head;  // 帧头
    int size;  // 数据的大小
};
 
typedef struct Buffer
{
    unsigned char* pBuffer;
    frame* pFrame;
    unsigned int leng;
};
 
/*
停等协议测试函数
1-bit滑动窗口
pBuffer:指针,指向系统要发送或接收到的帧内容,或者指向超时信息中超时帧的序号内容。
buffersize:pBuffer表示内容的长度(字节数)
messageType:分为以下几种情况:
1. MSG_TYPE_TIMEOUT:某个帧超时:根据帧的序号将该帧及后面的帧重新发送
2. MSG_TYPE_SEND:系统要发送一个帧:缓存到发送队列中;若发送窗口未满,则打开一个窗口发送这个帧;否则返回并进入等待状态
3. MSG_TYPE_RECEIVE:系统接收到一个帧的ACK:首先检查ACK的值,然后将ACK对应的窗口关闭
*/
int stud_slide_window_stop_and_wait(char *pBuffer, int bufferSize, UINT8 messageType)
{
    return 0;
}
 
/*
回退n帧测试函数
pBuffer:指针,指向系统要发送或接收到的帧内容,或者指向超时信息中超时帧的序号内容。
buffersize:pBuffer表示内容的长度(字节数)
messageType:分为以下几种情况:
1. MSG_TYPE_TIMEOUT:某个帧超时:根据帧的序号将该帧及后面的帧重新发送
2. MSG_TYPE_SEND:系统要发送一个帧:缓存到发送队列中;若发送窗口未满,则打开一个窗口发送这个帧;否则返回并进入等待状态
3. MSG_TYPE_RECEIVE:系统接收到一个帧的ACK:首先检查ACK的值,然后将ACK对应的窗口关闭
*/
int stud_slide_window_back_n_frame(char *pBuffer, int bufferSize, UINT8 messageType)
{
    return 0;
}
 
/*
* 选择性重传测试函数
*/
int stud_slide_window_choice_frame_resend(char *pBuffer, int bufferSize, UINT8 messageType)
{
    return 0;
}

我的实验代码

实现思路非常直观:定义类型Buffer用来存储每一帧的内容,开一个名为window的数组用来存储窗口中的帧,一个名为waitList的链表用来存储等待序列中的帧。停等协议和退后N帧协议的实现方法是几乎相同的,只是窗口的大小不同。

#include "sysinclude.h"
#include <list>
#include <fstream>
 
ofstream fout("slide_window.txt");
 
/*
* 发送帧函数
* 数据需要以网络序存储
*/
extern void SendFRAMEPacket(unsigned char* pData, unsigned int len);
 
#define WINDOW_SIZE_STOP_WAIT 1
#define WINDOW_SIZE_BACK_N_FRAME 4
 
typedef enum {data, ack, nak} frame_kind;
typedef struct frame_head
{
    frame_kind kind;  // 帧类型
    unsigned int seq;  // 序号
    unsigned int ack;  // 确认号
    unsigned char data[100];  // 数据
};
typedef struct frame
{
    frame_head head;  // 帧头
    int size;  // 数据的大小
};
typedef struct Buffer
{
    unsigned char* pBuffer;
    frame* pFrame;
    unsigned int leng;
};
 
/*
* 停等协议测试函数
* 1-bit滑动窗口
* pBuffer:指针,指向系统要发送或接收到的帧内容,或者指向超时信息中超时帧的序号内容。指向的内容为网络序,要转换成主机序,是从数据帧头开始的。
buffersize:pBuffer表示内容的长度(字节数)
messageType:分为以下几种情况:
1. MSG_TYPE_TIMEOUT:某个帧超时:根据帧的序号将该帧及后面的帧重新发送
2. MSG_TYPE_SEND:系统要发送一个帧:缓存到发送队列中;若发送窗口未满,则打开一个窗口发送这个帧;否则返回并进入等待状态
3. MSG_TYPE_RECEIVE:系统接收到一个帧的ACK:首先检查ACK的值,然后将ACK对应的窗口关闭
*/
int stud_slide_window_stop_and_wait(char *pBuffer, int bufferSize, UINT8 messageType)
{
    static Buffer window[WINDOW_SIZE_STOP_WAIT];  // 注意取模
    static int lower = 1, upper = 1;  // 窗口的上界和下界:[lower, upper) 
    static list<Buffer> waitList;
 
    switch (messageType)
    {
        case MSG_TYPE_RECEIVE:  // 收到确认帧
        {
            unsigned int ack = ntohl(((frame*)pBuffer) -> head.ack); // 注意网络序
            if (ack < lower || ack >= upper) // 在滑动窗口之外则丢弃
                break;
            fout << "MSG_TYPE_RECEIVE" << endl;
            fout << "ack = " << ack << ", lower = " << lower << ", upper = " << upper << endl;
            fout.flush();
            int i;
            // 确认序号落在发送窗口之内,下界连续+1,直到发送窗口下界=确认序号+1
            for (i = lower; i < upper; i++)
            {
                fout << "i = " << i << ", seq = " << ntohl(window[i % WINDOW_SIZE_STOP_WAIT].pFrame -> head.seq) << endl;
                fout.flush();
                if (ntohl(window[i % WINDOW_SIZE_STOP_WAIT].pFrame -> head.seq) == ack)
                {
                    lower = i + 1;
                    break;
                }
            }
            // 发送窗口空出,发送等待队列中的帧
            while (!waitList.empty() && upper - lower < WINDOW_SIZE_STOP_WAIT)  
            {
                Buffer buffer = waitList.front();
                waitList.pop_front();
                SendFRAMEPacket(buffer.pBuffer, buffer.leng);
                window[upper % WINDOW_SIZE_STOP_WAIT] = buffer;
                upper++;
            }
            break;
        }
 
        case MSG_TYPE_SEND:  // 发送新的一帧
        {
            // 保存帧的内容,注意不能只保存指针
            Buffer buffer;
            buffer.pFrame = new frame();
            *(buffer.pFrame) = *((frame*) pBuffer);
            buffer.pBuffer = (unsigned char*) buffer.pFrame;
 
            unsigned int seq = ntohl(((frame*)pBuffer) -> head.seq);
            fout << "MSG_TYPE_SEND" << endl;
            fout << "seq = " << seq << ", lower = " << lower << ", upper = " << upper << endl;
            fout.flush();
 
            // 将帧加入等待序列中
            buffer.leng = bufferSize;
            waitList.push_back(buffer);
 
            // 当发送窗口未满时,发送等待序列中的帧
            while (!waitList.empty() && upper - lower < WINDOW_SIZE_STOP_WAIT) 
            {
                Buffer buffer = waitList.front();
                waitList.pop_front();
                SendFRAMEPacket(buffer.pBuffer, buffer.leng);
                window[upper % WINDOW_SIZE_STOP_WAIT] = buffer;
                upper++;
            }
 
            break;
        }
 
        case MSG_TYPE_TIMEOUT:
        {
            unsigned int seq = *((unsigned int*) pBuffer); // 看起来pBuffer如果是一个unsigned int,则不是网络序
 
            fout << "MSG_TYPE_TIMEOUT" << endl;
            fout << "seq = " << seq << endl;
            fout.flush();
 
            // 全部重发
            // 注意:与指导书上不同的是,这里需要重发全部未确认帧,而不是只重发超时的帧及其之后的所有帧
            for (int i = lower; i < upper; i++) {
                Buffer buffer = window[i % WINDOW_SIZE_BACK_N_FRAME];
                SendFRAMEPacket(buffer.pBuffer, buffer.leng);
            }
 
            break;
        }
 
        default: // 出错了
            return -1;
    }
    return 0;
}
 
/*
* 回退n帧测试函数
未实现,但如果删掉会报错
*/
int stud_slide_window_back_n_frame(char *pBuffer, int bufferSize, UINT8 messageType)
{
   // 略,实现方法与停等协议完全相同,只有窗口大小不同
}
 
/*
* 选择性重传测试函数
*/
int stud_slide_window_choice_frame_resend(char *pBuffer, int bufferSize, UINT8 messageType)
{
    return 0;
}

实验代码在本地的输出

MSG_TYPE_SEND
seq = 1, lower = 1, upper = 1
MSG_TYPE_SEND
seq = 2, lower = 1, upper = 2
MSG_TYPE_SEND
seq = 3, lower = 1, upper = 2
MSG_TYPE_SEND
seq = 4, lower = 1, upper = 2
MSG_TYPE_SEND
seq = 5, lower = 1, upper = 2
MSG_TYPE_RECEIVE
ack = 1, lower = 1, upper = 2
i = 1, seq = 1
MSG_TYPE_RECEIVE
ack = 2, lower = 2, upper = 3
i = 2, seq = 2
MSG_TYPE_TIMEOUT
seq = 3
MSG_TYPE_RECEIVE
ack = 3, lower = 3, upper = 4
i = 3, seq = 3
MSG_TYPE_RECEIVE
ack = 4, lower = 4, upper = 5
i = 4, seq = 4
MSG_TYPE_RECEIVE
ack = 5, lower = 5, upper = 6
i = 5, seq = 5
MSG_TYPE_SEND
seq = 1, lower = 1, upper = 1
len = 29
MSG_TYPE_SEND
seq = 2, lower = 1, upper = 2
len = 29
MSG_TYPE_SEND
seq = 3, lower = 1, upper = 3
len = 29
MSG_TYPE_SEND
seq = 4, lower = 1, upper = 4
len = 29
MSG_TYPE_SEND
seq = 5, lower = 1, upper = 5
len = 29
MSG_TYPE_SEND
seq = 6, lower = 1, upper = 5
len = 29
MSG_TYPE_RECEIVE
ack = 2, lower = 1, upper = 5
send lower = 3 upper = 5
send lower = 3 upper = 6
MSG_TYPE_TIMEOUT
seq = 3, lower = 3, upper = 7
MSG_TYPE_TIMEOUT
seq = 4, lower = 3, upper = 7
MSG_TYPE_RECEIVE
ack = 6, lower = 3, upper = 7

Netriver实验系统的输出

// 停等协议测试
begin test!, testItem = 0  testcase = 0
accept len = 32 packet
accept len = 946 packet
frame seq ======================1
send a message to main ui, len = 39  type = 2  subtype = 1
frame seq ======================2
frame seq ======================3
frame seq ======================4
frame seq ======================5
accept len = 24 packet
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
send a message to main ui, len = 39  type = 2  subtype = 1
accept len = 24 packet
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
accept len = 24 packet
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
send a message to main ui, len = 39  type = 2  subtype = 1
accept len = 24 packet
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
send a message to main ui, len = 39  type = 2  subtype = 1
accept len = 24 packet
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
accept len = 6 packet
result = 0
send a message to main ui, len = 6  type = 1  subtype = 7

// 退后N帧测试
begin test!, testItem = 0  testcase = 1
accept len = 32 packet
accept len = 868 packet
frame seq ======================1
// 调用函数,messageType为MSG_TYPE_SEND,发送帧序列号为1
send a message to main ui, len = 39  type = 2  subtype = 1
// 调用SendFRAMEPacket函数发送序列号为1的帧
frame seq ======================2
// 调用函数,messageType为MSG_TYPE_SEND,发送帧序列号为2
send a message to main ui, len = 39  type = 2  subtype = 1
frame seq ======================3
// 调用函数,messageType为MSG_TYPE_SEND,发送帧序列号为3
send a message to main ui, len = 39  type = 2  subtype = 1
frame seq ======================4
// 调用函数,messageType为MSG_TYPE_SEND,发送帧序列号为4
send a message to main ui, len = 39  type = 2  subtype = 1
frame seq ======================5
// 调用函数,messageType为MSG_TYPE_SEND,发送帧序列号为5
frame seq ======================6
// 调用函数,messageType为MSG_TYPE_SEND,发送帧序列号为6
accept len = 24 packet
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
// 
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
send a message to main ui, len = 39  type = 2  subtype = 1
accept len = 24 packet 
send a message to main ui, len = 22  type = 2  subtype = 0
receive a frame
accept len = 6 packet
result = 0
send a message to main ui, len = 6  type = 1  subtype = 7
Test over!

思考题

1

退后N帧协议与1bit滑动窗口协议相比有何优点?

可以连续发送数据帧,不必在发送每一帧后都等待确认帧,增加了传输效率。

2

退后N帧协议有什么缺点?如何改进?

缺点是如果某一帧出错,就需要把全部未确认帧都重传一遍,这使得传输效率降低。可以用选择性重传来弥补这一缺陷。

参考文献


新增一则回应

除非特别注明,本页内容采用以下授权方式: Creative Commons Attribution-ShareAlike 3.0 License