NormanZyq
发布于 2020-02-23 / 3915 阅读
11
0

2019秋 计算机网络实验2 GBN协议的设计与实现(对应实验指导书的实验3)

实验要求

实验目的

理解滑动窗口协议的基本原理;掌握 GBN 的工作原理;掌握基于 UDP 设计并实现一个 GBN 协议的过程与技术。

实验内容

  1. 基于UDP设计一个简单的GBN协议,实现单向可靠数据传输(服务器到客户的数据传输)。

  2. 模拟引入数据包的丢失,验证所设计协议的有效性。

  3. 改进所设计的 GBN 协议,支持双向数据传输;(选作内容,加分项目,可以当堂完成或课下完成)

  4. 将所设计的 GBN 协议改进为 SR 协议。(选作内容,加分项目, 可以当堂完成或课下完成)

本文将全部都做,使用Java编写程序完成上述要求

在开始之前

实验指导书中给出了实验要点,下面先作出一些总结,有利于后续过程:

  1. 基于 UDP 实现的 GBN 协议,可以不进行差错检测,可以利用 UDP 协议差错检测;

  2. 自行设计数据帧的格式,应至少包含序列号Seq和数据两部分;

  3. 自行定义发送端序列号Seq比特数L以及发送窗口大小W,应满足条件 $W+1<= 2^L$

  4. 为了模拟ACK丢失,可以利用模N运算,每N次模拟丢包,或者每N次模拟接收。因为只是模拟,这个操作既可以在发送端也可以在接收端,如果在发送端,则少发送数据包,在接收端则不发回ACK。

  5. 当设置服务器端发送窗口的大小为1时,GBN协议就是停-等协议。

  6. 首先了解Java中建立UDP通信的方法,java.net包中提供了DatagramSocketDatagramPacket,这二者是UDP通信的工具包,DatagramSocket是UDP通信的socket,而DatagramPacket是数据包。在这个实验中,我用每个数据包模拟为分组。

  7. 超时任务的实现参考自CSDN

  8. 分组的规定:发送端末尾加上"Seq = %d"的字符串,接收端返回ACK时,在返回的packet的数据末尾加入字符串"ACK: %d"

1. 实现GBN协议,进行单向可靠数据传输

1.1. GBN发送端

思考:为了实现GBN协议,每个通信主机需要知道哪些信息:

对于发送端,它需要维护

  1. 窗口大小 WINDOW_SIZE

  2. 下一个序列号 nextSeq

  3. 待发送的分组个数 DATA_NUMBER

  4. 超时时间 TIMEOUT

因此根据GBN协议的FSM,可以很清晰的知道思路如下:

  1. 设置循环发送分组,判断nextSeq是否在窗口内,如果在就发送到127.0.0.1的预设端口(默认80),一次性发完一整个窗口内的分组并且等待对应序列号的ACK被返回。

    // 发送分组循环
    while (nextSeq < base + WINDOW_SIZE && nextSeq <= DATA_NUMBER) {
        // 模拟数据丢失暂时省略
        // 模拟发送分组
        String sendData = hostName + ": Sending to port " + destPort + ", Seq = " + nextSeq;
        byte[] data = sendData.getBytes();
        DatagramPacket datagramPacket = new DatagramPacket(data, data.length, destAddress, destPort);
        sendSocket.send(datagramPacket);
    
        System.out.println(hostName + "发送到" + destPort + "端口, Seq = " + nextSeq);
    
        if (nextSeq == base) {
            // 开始计时,等待接收端返回ACK
            timeModel.setTime(TIMEOUT);
        }
        nextSeq++;
        try {
            Thread.sleep(300);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
  2. 根据接收端返回的ACK编号调整窗口base的值为ACK+1,如果达到了窗口最大值,关闭计时器,如果还不是,就设置定时器继续等待。

    byte[] bytes = new byte[4096];
    DatagramPacket datagramPacket = new DatagramPacket(bytes, bytes.length);
    sendSocket.receive(datagramPacket);
    
    // 转换成String
    String fromServer = new String(datagramPacket.getData(), 0, datagramPacket.getLength());
    // 解析出ACK编号
    int ack = Integer.parseInt(fromServer.substring(fromServer.indexOf("ACK: ") + 5).trim());
    base = ack + 1;
    if (base == nextSeq) {
        // 停止计时器
        timeModel.setTime(0);
    } else {
        // 开始计时器
        timeModel.setTime(TIMEOUT);
    }
    
  3. 如果超时,说明发送端没有在限定时间内收到预期ACK,会重新发送这个序列号和其之后的所有分组。

    public void timeOut() throws IOException {
        for (int i = base; i < nextSeq; i++) {
            String resendData = hostName
                    + ": Resending to port " + destPort + ", Seq = " + i;
    
            byte[] data = resendData.getBytes();
            DatagramPacket datagramPacket = new DatagramPacket(data,
                    data.length, destAddress, destPort);
            sendSocket.send(datagramPacket);
    
            System.out.println(hostName
                    + "重新发送发送到" + destPort + "端口, Seq = " + i);
        }
    }
    

这样发送端的主体部分就已经实现了,完整代码见最后,下面实现GBN协议的接收端:

1.2. GBN接收端

  1. GBN中接收端存在“期望收到的序列号”,所以只要是收到了预期的序列号分组,就留下这个分组并且预期自增1,然后返回此序列号的ACK;如果不是,直接丢弃并返回上一个序列号的ACK。

    if (Integer.parseInt(received.substring(seqIndex + 6).trim()) == expectedSeq) {
        // 收到了预期的数据
        // 发送ACK
        // 模拟丢失ACK暂时省略
        sendACK(expectedSeq, receivePacket.getAddress(), receivePacket.getPort());
        System.out.println(hostName + " 期待的数据Seq = " + expectedSeq);
        // 期待值加1
        expectedSeq++;
    } else {
        // 未收到预期的Seq
        System.out.println(hostName + " 期待的数据Seq = " + expectedSeq);
        System.out.println(hostName + " 未收到预期编号");
        // 仍发送之前的ACK
        sendACK(expectedSeq - 1, receivePacket.getAddress(), receivePacket.getPort());
    }
    
  2. 发送ACK的IP地址和端口可能不确定,所以需要通过接收的receivePacket.getAddress()和getPort()获得IP地址和端口,这样才能将ACK发回正确的地方。

关于接收端使用的sendACK()方法,稍后会提到,先别关注它的实现,因为十分简短,当前先把思路理清。

1.3. 模拟丢失数据

  1. 发送端模拟丢失数据包,利用模N运算不发送特定的数据包达到模拟丢失的目的。将这段代码放在发送循环即将发出之前的位置。

    // 模拟数据丢失
    if (nextSeq % 5 == 0) {
        System.out.println(hostName + "假装丢失Seq = " + nextSeq);
        nextSeq++;
        continue;
    }
    
  2. 接收端模拟丢失ACK,将这段代码替换发送ACK的地方

    if (expectedSeq % 7 != 0) {
        sendACK(expectedSeq, receivePacket.getAddress(), receivePacket.getPort());
    } else {
        System.out.println(hostName + " 假装丢失ACK: " + expectedSeq);
    }
    

1.4. 封装一下?

因为后需要实现双向传输以及改造为SR协议,所以不如来封装一下。

写成一个MyHost.java文件,其中管理主机必备操作和数据,大致如下

(下面代码非完整代码)

public abstract class MyHost {

    protected final int WINDOW_SIZE;

    protected final int DATA_NUMBER;

    protected final int TIMEOUT;

    protected String hostName;

    /*下面的是发送数据相关的变量*/

    protected int nextSeq = 1;

    protected int base = 1;

    protected InetAddress destAddress;

    protected int destPort = 80;

    /*接收数据相关*/

    protected int expectedSeq = 1;

    /*Sockets*/

    protected DatagramSocket sendSocket;

    protected DatagramSocket receiveSocket;

    public MyHost(int RECEIVE_PORT, int WINDOW_SIZE,
                  int DATA_NUMBER, int TIMEOUT, String name) throws IOException {
        ...
    }

    ...

    public abstract void sendData() throws IOException;

    public abstract void timeOut() throws IOException;

    public abstract void receive() throws IOException;

    protected void sendACK(int seq, InetAddress toAddr, int toPort) throws IOException {
        ...
    }

    public String getHostName() {
        return hostName;
    }
}

创建GBNHost实现这个抽象类,这样就只需要在实例化对象后调用sendData()或者receive()就可以完成对发送端和接收端的判断了

2. 运行和改造成双向传输

第一,如何运行程序。因为有了简单的封装,运行程序变得方便。使用两个不同的线程分别调用 发送端和接收端的 发送和接收方法。但是有个缺点,就是打印出来的内容都在一个终端中,不够美观。

还有一个办法是写两个main函数(两个Java程序入口),一个是发送端,另一个是接收端,在两个终端中分别启动这两个程序,就能看到输出到不同终端的效果了。(我还没有找到如何将Java程序一次启动但是输出到两个终端的办法)

MyHost sender = new GBNHost(host1Port, 5, 20, 3, "Sender");
sender.setDestPort(host2Port);
MyHost receiver = new GBNHost(host2Port, 5, 20, 3, "Receiver");

new Thread(() -> {
    try {
        receiver.receive();
    } catch (IOException e) {
        e.printStackTrace();
    }
}).start();

new Thread(() -> {
    try {
        sender.sendData();
    } catch (IOException e) {
        e.printStackTrace();
    }
}).start();

<a href="https://imgse.com/i/3l8CFJ"><img src="https://s2.ax1x.com/2020/02/23/3l8CFJ.md.png" alt="3l8CFJ.png" border="0" /></a>

同时,改造成双向传输也变得十分简单,这时候需要四个线程,两个主机各自启动发送和接收就可以了,当然也能写成两个Java程序入口使其更直观。

[3l8Dlq](https://s2.ax1x.com/2020/02/23/3l8Dlq.md.png)](https://imgse.com/i/3l8Dlq)

3. 改造成SR协议

SR协议是一个选择发送协议,与GBN最大的不同是重发的时候发送的不是整个窗口,而是部分,因此需要知道哪些已发送、哪些未发送、哪些已正确接收。

基于MyHost抽象类,创建SRHost继承于此,但是为了模拟出SR协议的效果,维护的内容与GBN协议稍微有些区别:

/**
 * 作为发送方时发送过的分组。
 */
private Set<Integer> senderSentSet = new HashSet<>();

/**
 * 作为发送方时收到的ACK。
 */
private Set<Integer> senderReceivedACKSet = new HashSet<>();

/**
 * 作为接收方时收到的分组,用来作为缓存。
 */
private Set<Integer> receiverReceivedSet = new HashSet<>();

发送端是否发送和发送完成等的判断也不一样,SR协议的while条件是这个:

while (nextSeq < base + WINDOW_SIZE && nextSeq <= DATA_NUMBER && !senderSentSet.contains(nextSeq)) {
    ...
}

并且发送后需要将Seq加入到senderSentSet标记为已发送

senderSentSet.add(nextSeq);   // 加入已发送set

接收到ACK后,也需要做类似的操作,以便知道哪些还未正确发送

senderReceivedACKSet.add(ack);    // 加入已收到set

因为太长了,这里先不粘贴过多代码了,详见最后的完整代码。

SR协议的接收数据也有些许不同,收到乱序的但是在窗口内的数据包时不再丢弃,而是缓存起来,实现思路如下:

int seq = Integer.parseInt(received.substring(seqIndex + 6).trim());    // 获得seq
if (seq >= rcvBase && seq <= rcvBase + WINDOW_SIZE - 1) {
    receiverReceivedSet.add(seq);
    System.out.println(hostName + "收到一个窗口内的分组,Seq = " + seq + "已确认\n");

    // 模拟ACK丢失省略

    if (seq == rcvBase) {
        // 收到这个分组后可以开始滑动
        while (receiverReceivedSet.contains(rcvBase)) {
            rcvBase++;
        }
    }

} else if (seq >= rcvBase - WINDOW_SIZE && seq <= rcvBase - 1) {
    System.out.println(hostName + "收到一个已经确认过的分组,Seq = " + seq + "已再次确认");
    sendACK(seq, receivePacket.getAddress(), receivePacket.getPort());
} else {
    // 这个分组序列号太大,不在窗口内,应该舍弃
    System.out.println(hostName + "收到一个不在窗口内的分组,Seq = " + seq + "已舍弃");
}

4. SR协议运行效果

运行方式见3,在此不再赘述。

3lGvaF.md.png

左侧接收右侧发送。如图模拟Seq 5丢失,接收方未收到Seq 5,但是后续接收被缓存,直到发送方等待ACK 5超时后会重新发送Seq 5,如图:
3lJFr6.md.png

同样,如果接收方发回的ACK丢失,发送方等待ACK超时后也会重新发送分组,此时接收方会得知自己收到了一个重复的分组。
3lJmPH.md.png

5. 兼容停等协议:将GBN协议的窗口大小改成1就可以了

与GBN或SR的不同在于,GBN和SR都可以做到发送多个分组之后才收到ACK,打印出来的效果是“发送Seq-发送Seq-发送……-收到ACK-收到ACK”。 而停等协议中发送方每次发完一个分组就会等待ACK,所以打印结果是“发送Seq-收到ACK”的样子。

6. 遗憾

测试中我发现一个大问题,但是在提交实验之前都没有改好:如果数据包和ACK同时丢失,程序就死循环了。

7. 总结

到了寒假才想起来博客没发,已经记不得了(学了就忘)

3lG72n.md.png

代码下载:

链接: cs_networking_lab2.zip - zz的秘密空间


评论