实验过程#
实验基于老师提供的 RDT 1.0 代码，使用 IntelliJ IDEA 进行开发，Java 版本为 1.8。使用 Git 进行版本控制实现代码的迭代开发。
RDT 1.0（原始版本）#
配置好开发环境后，首先运行老师提供的 RDT 1.0 代码，观察其运行结果。RDT 1.0 代码实现了一个简单的 TCP 发送端和接收端，通过控制台输出发送端和接收端的状态信息。由于 RDT 1.0 代码基于所依赖的信道十分可靠的假设，因此对于数据包的位错、丢失或者重复等情况并没有进行处理。
设置 tcpH.setTh_eflag((byte) 0)，即关闭信道的错误标志，运行 RDT 1.0 代码。
 |  |  |
对于发送端所有发出的包，接收端都能够正确接收并返回确认，recvData 中的数据也是完整的。
RDT 2.x#
RDT 2.0#
RDT 2.0 假设信道是不可靠的，即数据包可能会出现位错的情况。因此，RDT 2.0 需要在发送端和接收端实现数据包的校验和功能，以便在接收端检测出数据包是否出现位错。
public static short computeChkSum(TCP_PACKET tcpPack) {
TCP_HEADER tcpHeader = tcpPack.getTcpH();
int seq = tcpHeader.getTh_seq();
int ack = tcpHeader.getTh_ack();
TCP_SEGMENT tcpSegment = tcpPack.getTcpS();
int[] data = tcpSegment.getData();
CRC32 crc32 = new CRC32();
crc32.update(seq);
crc32.update(ack);
for (int i : data) {
crc32.update(i);
}
int checkSum = (int) crc32.getValue();
return (short) checkSum;
}
对传入的数据包进行校验和计算，分别将其序列号、确认号和数据部分的每个字节进行 CRC32 计算，得到校验和。这里有一个出入，老师的 PPT 上要求“校验和”也进参与计算，但是我认为校验和不应该参与计算，因为校验和是用来校验数据包是否出错的，如果校验和也参与计算，那么校验和的值就会影响校验和的计算结果。
在实现校验和方法前，所有包的校验和均为 0，即不进行校验和计算。
RDT 2.1 / RDT 2.2#
对于 RDT 2.1，接收方按序依次接收数据包，如果接收到的数据包的校验和正确，则先返回 ACK，然后查看数据包的序列号是否为期望的序列号，如果不是则不做处理，如果是则将数据包的放进缓冲以等待交付。而如果校验和错误，则返回一个 NAK。对于 RDT 2.2，接收方不使用 NAK，而是重传对上一个正确接收的数据包的 ACK。
实现上，注意到数据包的序列号 seq 是字节流号，而原来设计中接收方的 sequence 是一个递增的值，可以认为就是数据包的序号，因此需要将发送方发来的 seq 转换为 dataIndex。在 TCP_Sender 中，seq 的计算公式是
这样，要重传上一个正确接收的数据包的 ACK，只需要将上一个正确接收的数据包的 dataIndex（即当前期望的 dataIndex 减 1）算出来即可。在代码中，使用和老师设计一致的 sequence 来表示当前期望的 dataIndex。
在 TCP_Receiver 中，作出如下修改（黄色高亮部分）：
int sequence = 0; // 用于记录当前待接收的包序号，将原来的 1 改为 0，因为第一个包的序号是 0
// ...
@Override
// 接收到数据报：检查校验和，设置回复的 ACK 报文段
public void rdt_recv(TCP_PACKET recvPack) {
// 检查校验码，生成 ACK
int dataLength = recvPack.getTcpS().getData().length;
int dataSequence = (recvPack.getTcpH().getTh_seq() - 1) / dataLength;
if (CheckSum.computeChkSum(recvPack) == recvPack.getTcpH().getTh_sum()) {
// 生成 ACK 报文段（设置确认号）
tcpH.setTh_ack(recvPack.getTcpH().getTh_seq());
ackPack = new TCP_PACKET(tcpH, tcpS, recvPack.getSourceAddr());
tcpH.setTh_sum(CheckSum.computeChkSum(ackPack));
// 回复 ACK 报文段
reply(ackPack);
// 将接收到的正确有序的数据插入 data 队列，准备交付
if (dataSequence == sequence) {
dataQueue.add(recvPack.getTcpS().getData());
sequence++;
}
} else {
System.out.println("Recieve Computed: " + CheckSum.computeChkSum(recvPack));
System.out.println("Recieved Packet" + recvPack.getTcpH().getTh_sum());
System.out.println("Problem: Packet Number: "+ recvPack.getTcpH().getTh_seq() + " + InnerSeq: " + sequence);
tcpH.setTh_ack((sequence - 1) * dataLength + 1); // 无需使用 NAK
ackPack = new TCP_PACKET(tcpH, tcpS, recvPack.getSourceAddr());
tcpH.setTh_sum(CheckSum.computeChkSum(ackPack));
// 回复 ACK 报文段
reply(ackPack);
}
System.out.println();
// 交付数据（每 20 组数据交付一次）
if (dataQueue.size() == 20)
deliver_data();
}
先根据接收到的数据包计算出其 dataIndex（dataSequence，保持和一开始的变量名一致），然后检查校验和，如果校验和正确，则该包没有出现位错，生成 ACK 报文段，设置确认号为接收到的数据包的序列号，然后回复 ACK 报文段。如果校验和错误，则生成 ACK 报文段，设置确认号为上一个正确接收的数据包的序列号，然后回复 ACK 报文段。
没有出现位错并不意味着这个包一定是有序的期望的包，因此需要判断接收到的包的 dataIndex 是否为期望的 dataIndex（比较 dataSequence 和 sequence），如果是则交付数据，放入 dataQueue 中，sequence 加 1。
而对于发送方，老师提供的代码中已经实现了收到错误的 ACK 包后重传数据包的功能，因此不需要做额外的修改。
将接收方和发送方设置为 tcpH.setTh_eflag((byte) 1)，允许信道出错，运行 RDT 2.2 代码。
在发送方的 Log 中可以看到，发送方发送了一个错误的数据包 5601 后没有收到对应的 ACK，显示 NO_ACK，然后重传了数据包 5601。
查看接收方 Log 可以看到这个错误的数据包 5601 被接收方检测出校验和错误，因此接收方返回了上一个 ACK 即 5501。发送方收到重发的 ACK 后重传了数据包 5601。
 |  |
而在接收方这里的 Log 中，可以看到接收方发送了一个错误的 ACK，根据前一个 ACK 是 17801 可以判断这里本应该发送 17901 的 ACK。发送方收到了错误的 ACK 后，重传了数据包 17901。于是接收方又一次收到了正确的数据包，发送了正确的 ACK 并交付数据。
从@rdt-2.0-recvData 可以看到，接收方收到的数据包是有序的且数量为 100000，没有出现数据包的丢失或者重复。
RDT 3.0#
RDT 3.0 在 RDT 2.2 的基础上作出了新的假设，即数据包可能会出现丢失的情况。因此，RDT 3.0 需要在发送方实现超时重传的功能，即发送方发送数据包后，如果在一定时间内没有收到 ACK，则重传数据包。此时就不再需要接收方重传 ACK，接收方直接丢弃不在期望范围内的数据包并不做响应。
在 TCP_Sender 类中，作出如下修改（黄色高亮部分）：
// 计时器
private UDT_Timer timer;
@Override
// 可靠发送（应用层调用）：封装应用层数据，产生 TCP 数据报；需要修改
public void rdt_send(int dataIndex, int[] appData) {
// 生成 TCP 数据报（设置序号和数据字段/校验和),注意打包的顺序
tcpH.setTh_seq(dataIndex * appData.length + 1);// 包序号设置为字节流号：
tcpS.setData(appData);
tcpPack = new TCP_PACKET(tcpH, tcpS, destinAddr);
// 更新带有 checksum 的 TCP 报文头
tcpH.setTh_sum(CheckSum.computeChkSum(tcpPack));
tcpPack.setTcpH(tcpH);
// 对每个数据包设置定时器
// 重传任务
timer = new UDT_Timer();
UDT_RetransTask retransTask = new UDT_RetransTask(client, tcpPack);
timer.schedule(retransTask, 1000, 1000); // 1s 后开始重传，每 1s 重传一次
// 发送 TCP 数据报
udt_send(tcpPack);
flag = 0;
// 等待 ACK 报文
// waitACK();
while (flag == 0)
;
}
// ...
@Override
public void waitACK() {
// 循环检查 ackQueue
// 循环检查确认号对列中是否有新收到的 ACK
if (!ackQueue.isEmpty()) {
int currentAck = ackQueue.poll();
// 接收到的 ACK 号等于当前发送的包号，说明发送成功
if (currentAck == tcpPack.getTcpH().getTh_seq()) {
timer.cancel(); // 取消定时器
System.out.println("Clear: " + tcpPack.getTcpH().getTh_seq());
flag = 1;
// break;
}
// 不等于，说明发送失败，由计时器触发重传
}
}
在发送方中，使用 Timer（即我这里使用的老师封装好的 UDT_Timer）和 TimerTask 来实现超时重传的功能。在发送数据包后，启动一个定时器，在这里我设置定时器每隔 1s 重传数据包。在等待 ACK 的过程中，如果收到了 ACK，则取消定时器，否则在定时器触发时重传数据包。
在 TCP_Receiver 中，只修改了接收方的代码，将接收方的重传 ACK 的功能去掉，直接丢弃不在期望范围内的数据包。如下：
if (CheckSum.computeChkSum(recvPack) == recvPack.getTcpH().getTh_sum()) {
// 如果接收到的数据包的序号小于等于期望的序号，则接收数据，可能是重传的数据包
if (dataSequence <= sequence) {
// 生成 ACK 报文段（设置确认号）
tcpH.setTh_ack(recvPack.getTcpH().getTh_seq());
ackPack = new TCP_PACKET(tcpH, tcpS, recvPack.getSourceAddr());
tcpH.setTh_sum(CheckSum.computeChkSum(ackPack));
// 回复 ACK 报文段
reply(ackPack);
// 如果接收到的数据包的序号等于期望的序号，则将数据包放进缓冲以等待交付
if (dataSequence == sequence) {
sequence = dataSequence + 1;
dataQueue.add(recvPack.getTcpS().getData());
}
}
} else {
// ...
}
和原来相比，只加了两个判断条件，一个是判断接收到的数据包的序号是否小于等于期望的序号，如果是则接收数据包并回复 ACK；另一个是判断接收到的数据包的序号是否等于期望的序号，如果是则交付数据。对于超前的数据包，直接丢弃。出错的数据包也一样，直接丢弃且不回复 ACK。
这样设计也可以处理延迟送达的包。当一个数据包延迟送达时，发送方无法收到 ACK，会在定时器触发时重传数据包，和丢包的情况一样。所以此时可以使用 tcpH.setTh_eflag((byte) 7)，允许信道出错、丢包、延迟，运行 RDT 3.0 代码。
在发送方的 Log 中可以看到，发送方发送了一个错误的数据包 61901 后没有收到对应的 ACK，显示 NO_ACK，然后重传了数据包 61901。
查看接收方 Log 的时间，可以看到对于前一个错误包，接收方没有进行确认，而过了一会儿等到后面重发的包 61901 时，接收方才进行了确认，发送方才继续发送后面的数据。
再比如接收方发送了一个延迟的 16101 确认。
发送方计时器超时后发现没有收到期望的 ACK，于是将 16101 对应的数据包重发，此时接收方收到了这个包才重发了 ACK。
对于发送方发送的延迟的包（图中的 47301），在测试系统中会在全部包发完之后才发送，自然在计时器时间范围内，接收方不会收到期望的包，在发送过程中和丢失（如图中 46501、46701）没有什么区别。所以计时器时间到时，发送方便会再发一次，此时接收方收到包没有异常就会回复一个确认了。
再比如接收方的 ACK 出错的情况：
接收方发送了一个错误的 ACK，发送方没有收到期望的 ACK，于是重发了数据包。
发送方重发了数据包，接收方收到了数据包后发送了正确的 ACK。以及接收方 ACK 延迟的情况：
接收方发送了一个延迟的 ACK，观察时间，可以看到发送方在计时器超时后重发了数据包。
综上，对于 RDT 3.0 的关注点实现了以下几点：
- 出错
- 数据包出错
- 检查 Log 文件，是否所有出错的数据包都进行了重传，并且重传的数据包都得到了确认；检查输出文件，是否对应包的正确内容包含在输出文件中，而不是包含出错的包内容以及重复的包内容（重复可以通过检查输出文件行数的办法来看）。
- 检查收方在收到错误的数据包时，是否发错的是对上一个序号的确认。
- 发方在收到上一个序号的确认时，是否重传当前数据包。
- 确认包出错
- 检查 Log 文件，出错的确认包是否引发了当前包的重传，检查输出文件，是否对应包的正确内容包含在输出文件中，而且不包含出错的包内容以及重复的包内容。
- 检查发送方收到错误的确认时，是否重传当前包。
- 数据包出错
- 丢失
- 检查 Log 文件，发生丢包（包含数据包和确认包），是否发送方在 3s 后进行了超时重传（此处实现是 1s）。检查输出文件，是否对应包的正确内容包含在输出文件中，而且不包含重复的包内容（重复可以通过检查输出文件行数的办法来看）。
接下来实现滑动窗口类型的几个协议：Go-Back-N、Select Response 和 TCP。相比较前面的几个协议，使用滑动窗口的协议无需逐个包等待 ACK，而是流水线式地发送数据包，提高了传输效率。我先实现的是 Select Response 协议。
Select Response#
对于选择响应协议，发送方和接收方各维护一个窗口。发送方的窗口存放了所有准备发送或者已经发送但是还没有收到 ACK 的分组，接收方的窗口存放了所有准备接收或者已经接收但是还没有交付的分组。收发数据时，接收方逐个对所有正确收到的分组进行应答、对接收到的分组进行缓存，当左沿指针指向的包到达时对上层进行有效递交。发送方为每个分组维护一个计时器，当计时器超时时重传对应的分组。
@sender-window-sr 是发送方窗口的 UML 类图。在 SR 中我使用的数据结构是以数组形式实现的循环队列。队列的最大大小是窗口大小，队列中的每个元素是一个封装好的数据类型 SenderElem，包含了数据包、计时器和其 ACK 状态（用枚举类型表示）。
发送方窗口维护 3 个指针：base、nextToSend 和 rear。base 指向窗口的左沿，是整个队列中第一个未被 ACK 的包；nextToSend 指向下一个要发送的包；rear 指向队列中新加入的包之后。
在发送数据包前，先使用 pushPacket 方法将数据包加入队列，然后使用 sendPacket 方法发送数据包并启动计时器。当收到 ACK 后，使用 ackPacket 方法找到对应的包并更新其 ACK 状态，然后检查是否可以滑动窗口。
当窗口满时，发送方无法将新的包加入队列，直到窗口中的包被 ACK。
具体代码实现上，使用数组实现循环队列会显得代码量稍微多一些，主要原因还是要计算下标。
WindowElem：
WindowElem 是 SenderElem 和 ReceiverElem 的父类，封装了数据包和其 ACK 状态。
package com.ouc.tcp.test; import com.ouc.tcp.message.TCP_PACKET; public class WindowElem { protected TCP_PACKET packet; protected int flag; public WindowElem() { packet = null; flag = 0; } public TCP_PACKET getPacket() { return packet; } public void setElem(TCP_PACKET packet, int flag) { this.packet = packet; this.flag = flag; } public void resetElem() { packet = null; flag = 0; } }SenderElem：
SenderElem 类在 WindowElem 的基础上增加了计时器的功能。计时器的实现和 RDT 3.0 中的计时器一样，使用 Timer 和 TimerTask 来实现。
package com.ouc.tcp.test; import com.ouc.tcp.client.UDT_RetransTask; import com.ouc.tcp.client.UDT_Timer; enum SenderFlag { NOT_ACKED, ACKED } public class SenderElem extends WindowElem{ private UDT_Timer timer; public SenderElem() { super(); this.timer = null; } public boolean isAcked() { return flag == SenderFlag.ACKED.ordinal(); } public void scheduleTask(UDT_RetransTask retransTask, int delay, int period) { this.timer = new UDT_Timer(); this.timer.schedule(retransTask, delay, period); } public void ackPacket() { this.flag = SenderFlag.ACKED.ordinal(); this.timer.cancel(); } }SenderWindow：
窗口的三个指针我都设计成了单向增长的，即 base、nextToSend 和 rear 都是递增的。这样设计的好处是可以直接通过取模运算来获取下标，而不需要考虑指针的回退。
package com.ouc.tcp.test; import com.ouc.tcp.client.Client; import com.ouc.tcp.client.UDT_RetransTask; import com.ouc.tcp.message.TCP_PACKET; public class SenderWindow { private int size; private SenderElem[] window; private int base; private int nextToSend; // 下一个要发送的元素的下标 private int rear; // 窗口的最后一个元素的下标 public SenderWindow(int size) { this.size = size; this.window = new SenderElem[size]; for (int i = 0; i < size; i++) { this.window[i] = new SenderElem(); } this.base = 0; this.nextToSend = 0; this.rear = 0; } private int getIdx(int seq) { return seq % size; } // 取模运算获取下标 public boolean isFull() { return rear - base == size; } public boolean isEmpty() { return base == rear; } public boolean isAllSent() { return nextToSend == rear; } public void pushPacket(TCP_PACKET packet) { int idx = getIdx(rear); // 初始化为未 ACK window[idx].setElem(packet, SenderFlag.NOT_ACKED.ordinal()); rear++; } public void sendPacket(TCP_Sender sender, Client client, int delay, int period) { // 窗口为空或者窗口中的所有元素都已经发送 if (isEmpty() || isAllSent()) { return; } int idx = getIdx(nextToSend); TCP_PACKET pack = window[idx].getPacket(); window[idx].scheduleTask(new UDT_RetransTask(client, pack), delay, period); nextToSend++; sender.udt_send(pack); } public void ackPacket(int seq) { // 从 base 开始遍历，找到对应的包并 ACK for (int i = base; i != rear; i++) { int idx = getIdx(i); if (window[idx].getPacket().getTcpH().getTh_seq() == seq && !window[idx].isAcked()) { window[idx].ackPacket(); break; } } // 滑动窗口 while (base != rear && window[getIdx(base)].isAcked()) { int idx = getIdx(base); window[idx].resetElem(); base++; } } }TCP_Sender：
修改的地方依然用黄色高亮标出。和 RDT 3.0 相比，将计时器移入了窗口的元素中，每个数据包都有一个计时器。在将数据包加入窗口前判断窗口是否满，如果满了则等待窗口滑动。加入窗口时使用 clone 方法复制数据包，传入一个新的数据包对象。
enum WindowFlag { FULL, NOT_FULL // FULL: 窗口满 // NOT_FULL: 窗口未满 } public class TCP_Sender extends TCP_Sender_ADT { private TCP_PACKET tcpPack; //待发送的TCP数据报 private volatile int flag = WindowFlag.NOT_FULL.ordinal(); // 窗口状态标志 private final SenderWindow window = new SenderWindow(16); // ... @Override //可靠发送（应用层调用）：封装应用层数据，产生TCP数据报；需要修改 public void rdt_send(int dataIndex, int[] appData) { //生成TCP数据报（设置序号和数据字段/校验和),注意打包的顺序 tcpH.setTh_seq(dataIndex * appData.length + 1);//包序号设置为字节流号： tcpS.setData(appData); tcpPack = new TCP_PACKET(tcpH, tcpS, destinAddr); //更新带有checksum的TCP 报文头 tcpH.setTh_sum(CheckSum.computeChkSum(tcpPack)); tcpPack.setTcpH(tcpH); if (window.isFull()) { //窗口满，等待窗口滑动 flag = WindowFlag.FULL.ordinal(); } while (flag == WindowFlag.FULL.ordinal()) { //等待窗口滑动 } try { window.pushPacket(tcpPack.clone()); // 将数据包加入窗口 } catch (CloneNotSupportedException e) { throw new RuntimeException(e); } window.sendPacket(this, client, 1000, 1000); // 发送数据包 } // ... @Override //需要修改 public void waitACK() { //循环检查ackQueue //循环检查确认号对列中是否有新收到的ACK if (!ackQueue.isEmpty()) { int currentAck = ackQueue.poll(); window.ackPacket(currentAck); if (!window.isFull()) { flag = WindowFlag.NOT_FULL.ordinal(); } } } // ... }
@receiver-window-sr 是接收方窗口的 UML 类图。 接收方窗口的实现和发送方窗口的实现类似，只是接收方窗口不需要计时器，只需要维护一个窗口即可。实现上它只需要 1 个指针：base，指向窗口的左沿，是窗口下一个期望的包。之所以不需要 rear 是因为其序号有序，不需要额外的指针来标记。
每收到一个包，若校验码检查正确，则判断包的序号是否超出窗口右沿，如果在窗口内是则回复 ACK 并将包放入窗口，如果是重发包则回复 ACK 但不存入窗口，乱序包直接丢弃。若收到的包是窗口左沿的包，则交付数据并滑动窗口。校验码检查错误的包直接丢弃等待重发。
对每个 ReceiverElem，维护了一个数据包和一个包状态（等待包到来或已缓存）。而检查序号一步同样用了一个枚举类型表示包的状态，包括重发包、乱序（不在窗口内的包）和正常包，正常包又细分了一个窗口内的包和窗口左沿的包，这样可以更好地处理不同状态的包。
对于接收方窗口的实现，代码如下：
ReceiverElem：
和 SenderElem 相比，ReceiverElem 几乎是直接继承自 WindowElem，只是增加了一个数据包的状态的布尔值。
package com.ouc.tcp.test; enum ReceiverFlag { WAIT, BUFFERED // WAIT: 等待接收或已经确认 // BUFFERED: 已经接收但还未确认 } public class ReceiverElem extends WindowElem { public ReceiverElem() { super(); } public boolean isBuffered() { return flag == ReceiverFlag.BUFFERED.ordinal(); } }ReceiverWindow：
ReceiverWindow 只需要将包放入窗口和交付数据两个方法。对于包的状态使用 AckFlag 枚举类型表示。交付时，如果窗口左沿的包是已经缓存的包，则交付数据并滑动窗口。
package com.ouc.tcp.test; import com.ouc.tcp.message.TCP_PACKET; enum AckFlag { ORDERED, DUPLICATE, UNORDERED, IS_BASE // ORDERED: 接收到的包是按序的 // DUPLICATE: 接收到的包是重复的 // UNORDERED: 接收到的包提前送达，乱序 // IS_BASE: 接收到的包是基序号的包，开始交付数据 } public class ReceiverWindow { private final int size; private final ReceiverElem[] window; private int base; // 窗口的基序号，即下一个期望接收的包的序号 public ReceiverWindow(int size) { this.size = size; this.window = new ReceiverElem[size]; for (int i = 0; i < size; i++) { this.window[i] = new ReceiverElem(); } this.base = 0; } private int getIdx(int seq) { return seq % size; } // 取模运算获取下标 public int bufferPacket(TCP_PACKET packet) { int seq = (packet.getTcpH().getTh_seq() - 1) / packet.getTcpS().getData().length; // 超前送达，乱序 if (seq >= base + size) { return AckFlag.UNORDERED.ordinal(); } // 在窗口左侧，重复 if (seq < base) { return AckFlag.DUPLICATE.ordinal(); } // 在窗口内，缓存 window[getIdx(seq)].setElem(packet, ReceiverFlag.BUFFERED.ordinal()); // 在窗口左沿，交付数据 if (seq == base) { return AckFlag.IS_BASE.ordinal(); } return AckFlag.ORDERED.ordinal(); } public TCP_PACKET getPacketToDeliver() { // 如果窗口左沿的包没有缓存，则无法交付数据 if (!window[getIdx(base)].isBuffered()) { return null; } // 交付数据 TCP_PACKET packet = window[getIdx(base)].getPacket(); window[getIdx(base)].resetElem(); base++; return packet; } }TCP_Receiver：
修改的地方依然用黄色高亮标出。接收到数据包后，先检查校验和，然后调用 bufferPacket 方法将数据包放入窗口或响应。如果数据包是窗口左沿的包，则交付数据。
public class TCP_Receiver extends TCP_Receiver_ADT { private TCP_PACKET ackPack; //回复的ACK报文段 private ReceiverWindow window = new ReceiverWindow(16); // ... @Override //接收到数据报：检查校验和，设置回复的ACK报文段 public void rdt_recv(TCP_PACKET recvPack) { int dataLength = recvPack.getTcpS().getData().length; //检查校验码，生成ACK if (CheckSum.computeChkSum(recvPack) == recvPack.getTcpH().getTh_sum()) { int bufferResult = window.bufferPacket(recvPack); if (bufferResult == AckFlag.ORDERED.ordinal() || bufferResult == AckFlag.DUPLICATE.ordinal() || bufferResult == AckFlag.IS_BASE.ordinal()) { tcpH.setTh_ack(recvPack.getTcpH().getTh_seq()); ackPack = new TCP_PACKET(tcpH, tcpS, recvPack.getSourceAddr()); tcpH.setTh_sum(CheckSum.computeChkSum(ackPack)); reply(ackPack); } if (bufferResult == AckFlag.IS_BASE.ordinal()) { TCP_PACKET packet = window.getPacketToDeliver(); while (packet != null) { dataQueue.add(packet.getTcpS().getData()); packet = window.getPacketToDeliver(); } } } // 错误包不回复 ACK System.out.println(); //交付数据 deliver_data(); } // ... }
继续保持 tcpH.setTh_eflag((byte) 7)，允许信道出错、丢包、延迟，运行 Select Response 代码。
| Sender Log | Receiver Log |
|---|---|
 |  |
 |  |
不管是在 Sender Log 中还是在 Receiver Log 中，都可以很明显看出窗口的滑动。
比如@sender-log-sr，从时间上看，32201 到 33601 之间的包都是一个接一个（时间间隔很短）发送的，说明它们在一个窗口中。而 32101 的包一开始丢失了，导致 Sender 迟迟等不到回复，而此时（发出 33601 后）窗口满，无法继续发送，所以在 32101 重传前出现了较大的时间间隔，直到 32101 重传后窗口滑动，Sender 继续发送数据。
而@receiver-log-sr 中则是由于 18601 的 ACK 延迟了，导致 Sender 迟迟无法收到 ACK，窗口满了无法继续发送，直到 18601 重传、Receiver 发送 ACK，Sender 才继续发送数据。
查看交付的数据包，可以看到接收方收到的数据包是有序的且数量为 100000，没有出现数据包的丢失或者重复。可以说明 Select Response 协议的实现是正确的。
综上，对于 Select Response 的关注点实现了以下几点：
- 检查 Log 文件，当出现错误（包含数据包出错、数据包或确认报丢包）时，是否发方在 3s 后超时重传对应数据包（此处实现是 1s）。常见错误：发送方重传的数据包并不是出现错误问题的数据包。
- 检查输出文件，不存在乱序的情况。
Go-Back-N#
Go-Back-N 和 Select Response 相比，Sender 只在窗口左沿放置一个全局的计时器，而不是每个数据包都有一个计时器。当计时器超时时，重传窗口中的所有数据包。而 Receiver 也维护一个计时器，当计时器超时时，发回当前最后一个连续收到的包的 ACK，即累积确认。
在实现上，第一个修改是将每个数据包的计时器移入了 SenderWindow 类中。原来的计时器的 RetransTask 是重发单个分组，现在需要重发窗口中的所有数据包，因此需要修改 RetransTask 的实现。在 SenderWindow 类中：
- 加入子类 GBN_RetransTask 继承 UDT_RetransTask，重写 run 方法，实现重发整个窗口的数据包。要实现重发，需要将 TCP_Sender 传入，因为需要调用 udt_send 方法发送数据包。实现 sendWindow 方法，将窗口中的数据包逐个发送。
private UDT_Timer timer;
private int delay;
private int period;
private TCP_Sender sender;
public class GBN_RetransTask extends TimerTask {
private TCP_Sender sender;
private SenderWindow window;
public GBN_RetransTask(TCP_Sender sender, SenderWindow window) {
this.sender = sender;
this.window = window;
}
public void run() {
window.sendWindow();
}
}
public void resetTimer() {
timer.cancel();
timer = new UDT_Timer();
if (!isEmpty()) {
timer.schedule(new GBN_RetransTask(this), delay, period);
}
}
public void sendWindow() {
nextToSend = base;
while (nextToSend < rear) {
sendPacket();
}
}
发包时依然逐个发送数据包，但是在发送第一个包时启动计时器。在收到 ACK 时，逐个确认包并重置计时器。
private final SenderWindow window; /*构造函数*/ public TCP_Sender() { super(); //调用超类构造函数 super.initTCP_Sender(this); //初始化 TCP 发送端 // 由于窗口调用了 this，所以需要在构造函数中初始化 window = new SenderWindow(this, 16, 3000, 3000); } @Override //可靠发送（应用层调用）：封装应用层数据，产生 TCP 数据报；需要修改 public void rdt_send(int dataIndex, int[] appData) { //生成 TCP 数据报（设置序号和数据字段/校验和),注意打包的顺序 tcpH.setTh_seq(dataIndex * appData.length + 1);//包序号设置为字节流号： tcpS.setData(appData); tcpPack = new TCP_PACKET(tcpH, tcpS, destinAddr); //更新带有 checksum 的 TCP 报文头 tcpH.setTh_sum(CheckSum.computeChkSum(tcpPack)); tcpPack.setTcpH(tcpH); if (window.isFull()) { //窗口满，等待窗口滑动 flag = WindowFlag.FULL.ordinal(); } while (flag == WindowFlag.FULL.ordinal()) { //等待窗口滑动 } try { window.pushPacket(tcpPack.clone()); } catch (CloneNotSupportedException e) { throw new RuntimeException(e); } window.sendPacket(); }加入发包、收 ACK 时计时器的逻辑。按照 PPT 上的说明，在左沿发送第一个包时启动计时器。由于在 Go-Back-N 中接收方发回的 ACK 是最后一个连续收到的包的 ACK，所以在收到 ACK 时可以让确认包的步骤和滑动窗口的步骤合并。每确认一个包（等同于滑动窗口），重置计时器。
private void sendPacket() { if (isEmpty() || isAllSent()) { // 窗口为空或者窗口中的所有元素都已经发送 return; } int idx = getIdx(nextToSend); TCP_PACKET pack = window[idx].getPacket(); // 如果是第一个元素，启动定时器 if (atBase()) { timer.schedule(new GBN_RetransTask(sender, this), delay, period); } nextToSend++; sender.udt_send(pack); } public void ackPacket(int seq) { int idx = getIdx(base); for (int i = base; i != rear; i++) { int idx = getIdx(i); if (window[idx].getPacket().getTcpH().getTh_seq() <= ack && !window[idx].isAcked()) { window[idx].ackPacket(); window[idx].resetElem(); base++; resetTimer(); } } }
对于 Receiver，此时 Receiver 也需要维护一个计时器，当计时器超时时，发回当前最后一个连续收到的包的 ACK，而基于 Select Response 的代码上，实际上这个 ACK 就是 base - 1 的包的 ACK，因此和 Select Response 需要处理重复、窗口内或者窗口左沿相比，Go-Back-N 只需要处理窗口左沿的包。
在 TCP_Receiver 类中：
// 加入计时器
private UDT_Timer timer = new UDT_Timer();
// ...
@Override
//接收到数据报：检查校验和，设置回复的 ACK 报文段
public void rdt_recv(TCP_PACKET recvPack) {
// 等待 500ms，然后发回 ACK
timer.schedule(new TimerTask() {
@Override
public void run() {
reply(ackPack);
timer.cancel(); // 必须加入这一句，否则收一个包就会开一个计时器
timer = new UDT_Timer();
}
}, 500); // delay: 500ms
//检查校验码，生成 ACK
if (CheckSum.computeChkSum(recvPack) == recvPack.getTcpH().getTh_sum()) {
int bufferResult = window.bufferPacket(recvPack);
// 如果是窗口左沿的包，计时器计时 500ms 等待其余包到达
if (bufferResult == AckFlag.IS_BASE.ordinal()) {
TCP_PACKET packet = window.getPacketToDeliver();
while (packet != null) {
dataQueue.add(packet.getTcpS().getData());
tcpH.setTh_ack(packet.getTcpH().getTh_seq());
ackPack = new TCP_PACKET(tcpH, tcpS, recvPack.getSourceAddr());
tcpH.setTh_sum(CheckSum.computeChkSum(ackPack));
packet = window.getPacketToDeliver();
}
// 如果有计时器在等待，重置计时器，只有在 500ms 期间没有收到基序号的包时才会发回 ACK
if (timer != null) {
timer.cancel();
timer = new UDT_Timer();
timer.schedule(
new TimerTask() {
public void run() {
reply(ackPack); //回复 ACK 报文段
}
}, 500
);
}
// 如果是按序的包，继续等待，而如果是乱序或者重复的包则立即响应 ACK
} else if (bufferResult != AckFlag.ORDERED.ordinal()) {
reply(ackPack);
}
}
// ...
}
这一边计时器的设计比较巧妙。收包的情况可以分为三种：
- 收到的包是窗口左沿的包，即 base 包，此时 Receiver 会交付数据并回复 ACK，然后计时器开始计时 500ms，等待其余包到达。如果 500ms 内没有收到基序号的包，则发回 ACK。
- 收到的包是按序的包，Receiver 会继续等待，直到收到乱序或者重复的包，立即回复 ACK；或者收到窗口左沿的包，交付数据并继续等待。
- 收到的包是乱序或者重复的包，Receiver 立即回复 ACK。
因此如果所有的包都按序依次到达，Receiver 最长会在窗口满后的 500ms 后回复 ACK。而如果有乱序或者重复的包，Receiver 会立即回复 ACK。因此需要要求 Sender 重发窗口的间隔要比两个 RTT 长，否则 Receiver 会在 500ms 后回复 ACK，而 Sender 会在 2s 后重发窗口，这样会导致 Receiver 重复回复 ACK。这里我按照 PPT 上的说明，给 Sender 设置了 3s 的延迟和重发间隔。
继续保持 tcpH.setTh_eflag((byte) 7)，允许信道出错、丢包、延迟，运行 Go-Back-N 代码。
在 Go-Back-N 中，如果发送无异常，在 Sender Log 中会看到只有窗口的最后一个包被确认（因为收方计时器设置得远比传输时间长）。收方的计时器间隔为 500ms，因此大约每 500ms 发送一个 ACK。
而一旦分组出现问题或者 ACK 丢失、延迟，就会出现整个分组的重传。比如如图所示就是 28401 的错误导致了整个窗口的超时重传。
依然查看交付的数据包，可以看到也没有问题。
综上，对于 Go-Back-N 的关注点实现了以下几点：
- 检查 Log 文件，当出现错误（包含数据包出错、数据包或确认报丢包）时，发方在 3s 后超时重传当前窗口内的所有包；超时重传的包包含发送端已经收到确认的包。
- 检查接收方有没有做为期 500ms 的累计确认。
- 检查输出文件，是否对应包的正确内容包含在输出文件中，而不是包含出错的包内容以及重复的包内容。
- 接收方使用了窗口缓存，按 GB 协议，接收方不缓存失序的包，但我的代码基于 Select Response 的代码，考虑到 TCP 要求缓存失序包，我没有修改这一点。
TCP#
不需要拥塞控制的 TCP 相当于 Select Response 的 Receiver 和 Go-Back-N 的 Sender。
按照 PPT 上的说明，如果接收方收到的数据包恰为期望的数据包，则延迟 500ms 发回 ACK，而如果收到的数据包不是期望的数据包，则立即发回 ACK。这一点在 Go-Back-N 中已经实现，因此只需沿用对应的代码即可。
为了后面迭代实现 TCP 的拥塞控制做准备，我将 SenderWindow 的数据类型改为 LinkedBlockingDeque，来自 java.util.concurrent 包。这样可以更方便地实现慢开始和拥塞避免。
因此，修改 SenderWindow 类如下：
对于发送包计时器的实现，和 Go-Back-N 类似，只是判断条件由比较 base 改为判断窗口是否为空。
public boolean isEmpty() { return window.isEmpty(); } public void pushPacket(TCP_PACKET packet) { // 如果窗口为空，启动定时器 if (isEmpty()) { timer = new UDT_Timer(); timer.schedule(new GBN_RetransTask(this), delay, period); } window.push(new SenderElem(packet, SenderFlag.NOT_ACKED.ordinal())); }发送窗口时，逐个发送窗口中的数据包。而发送包的时候，滚动队列，将窗口左沿的包取出并发送，然后将其放回队列。
public void sendWindow() { // 发送窗口中的数据 for (SenderElem elem : window) { if (!elem.isAcked()) { sender.udt_send(elem.getPacket()); } } } public void sendPacket() { SenderElem elem = window.poll(); if (elem == null) { return; } if (!elem.isAcked()) { sender.udt_send(elem.getPacket()); } window.push(elem); }响应 ACK 时，逐个确认包并重置计时器。这里可以直接调用 remove 方法清除已经确认的包。
public void ackPacket(int ack) { for (SenderElem elem : window) { if (elem.getPacket().getTcpH().getTh_seq() <= ack) { elem.ackPacket(); window.remove(elem); resetTimer(); } } }
而由于接收方的代码沿用自 Select Response 修改成的 Go-Back-N，有乱序包缓存和延迟 500ms 累积确认的能力，因此不需要修改。
依然是保持 tcpH.setTh_eflag((byte) 7)，允许信道出错、丢包、延迟，运行 TCP 代码。
和 Go-Back-N 类似，累积确认的 ACK 会在 500ms 后发出，正常只确认窗口最右侧的包。
对于丢包导致的重传，延迟 3s 之后整个窗口进行重传。
查看交付的数据包，可以看到没有什么问题。
综上，对于 TCP 的关注点实现了以下几点：
- 检查 Log 文件，当出现错误（包含数据包出错、数据包或确认报丢包）时，发方在 3s 后超时重传当前窗口内的所有未收到确认的包；超时重传的包包含发送端已经收到确认的包。
- 检查接收方做了为期 500ms 的累计确认。
- 检查输出文件，对应包的正确内容包含在输出文件中，而不是包含出错的包内容以及重复的包内容。
- 发送端使用 LinkedBlockingDeque 作为窗口数据结构，方便实现慢开始和拥塞避免。窗口随着 ACK 的到来右移，窗口空间用完后以 IS_FULL 的标志阻止应用层继续调用。
- 发送端使用一个计时器来完成对于当前窗口内的所有未收到确认的包进行超时重传。
- 接收端使用了一个计时器来完成为期 500ms 的累计确认。
- 接收端使用了窗口缓存失序的包，累积确认后提交连续的报文段。
接下来加入拥塞控制，实现 TCP 的完整功能。
TCP Tahoe#
TCP Tahoe 用 3 个方法来拥塞控制，分别是慢开始、拥塞避免和快重传。
- 慢开始由 cwnd 和 ssthresh 两个变量控制。cwnd 表示当前窗口大小，ssthresh 表示慢开始阈值。在慢开始阶段，cwnd 每收到一个 ACK 就加 1，直到 cwnd 达到 ssthresh，相当于每次翻倍（指数增大）然后进入拥塞避免阶段。
- 拥塞避免阶段，cwnd 按照 1/cwnd 的比例增加，总体发包的数量就变成了 1，进入加法增大阶段
- 快重传是指当连续收到 3 个相同的 ACK 时，ssthresh 减半，cwnd 重置为 1，并重传窗口左沿的包。
SenderWindow 类修改如下：
- 加入 cwnd、dCwnd 和 ssthresh 三个变量，分别表示当前窗口大小、拥塞窗口大小和慢开始阈值。
private int cwnd = 1; // 等同于原来的窗口大小 size
private double dCwnd = 1.0; // 浮点类型的 cwnd，用于拥塞避免
private int ssthresh = 16; // 慢开始阈值
- 修改 ackPacket 方法，实现慢开始和拥塞避免。
在慢开始阶段，每收到一个 ACK，cwnd 加 1，实现乘法增大；在拥塞避免阶段，cwnd 按照 1/cwnd 的比例增加，总体发包的数量就变成了 1。也就是这一步计算需要用到浮点值的 cwnd。
```java
private void resendPacket(int ack) {
// 重传窗口左沿的包，100 是包的长度，用于计算字节流号
int expectedSeq = ack + 100;
for (SenderElem elem : window) {
if (elem.getPacket().getTcpH().getTh_seq() == expectedSeq) {
sender.udt_send(elem.getPacket());
break;
}
}
}
public void ackPacket(int ack) {
// 滑动窗口
for (SenderElem elem : window) {
if (elem.getPacket().getTcpH().getTh_seq() <= ack) { // 确认序号小于等于 ack 的包
elem.setAcked();
window.remove(elem);
if (cwnd < ssthresh) {
// 指数增大，慢开始
cwnd++;
dCwnd = cwnd;
}
// 每次收到 ACK 都重置计时器
resetTimer();
}
}
if (cwnd >= ssthresh) {
// 拥塞避免，加法增大
dCwnd += (double) 1 /cwnd;
cwnd = (int) dCwnd;
}
// 快重传，连续收到 3 个相同的 ACK 则重传窗口左沿的包
if (ack == lastAck) {
lastAckCount++;
} else {
lastAck = ack;
lastAckCount = 1;
}
if (lastAckCount >= lastAckCountLimit) {
// 拥塞避免，重置窗口大小
ssthresh = cwnd / 2;
cwnd = 1;
dCwnd = (double) cwnd;
// 快重传
resendPacket(ack);
}
}
```
对于 TCP_Receiver 也需要做一些修改，主要原因是在快重传和超时重传的“冲突”。超时重传一次传整个窗口的包，会导致 Receiver 响应 ACK 的时候，Sender 会收到多个 ACK，这样就会导致快重传的条件被满足。按照要求，应当对于所有的按序到达的包或者已经被确认过的包（重发的包）都延迟 500ms 累积确认，而不只是窗口左沿的包。
在 TCP_Receiver 类中：
public void rdt_recv(TCP_PACKET recvPack) {
// ...
if (CheckSum.computeChkSum(recvPack) == recvPack.getTcpH().getTh_sum()) {
int bufferResult = window.bufferPacket(recvPack);
if (bufferResult == AckFlag.ORDERED.ordinal() || bufferResult == AckFlag.DUPLICATE.ordinal()) {
// ...
} else {
reply(ackPack);
}
}
// ...
}
在 ReceiverWindow 类中，IS_BASE 则不再需要，因为 Receiver 不再需要对窗口左沿的包进行特殊处理。
public int bufferPacket(TCP_PACKET packet) {
int seq = (packet.getTcpH().getTh_seq() - 1) / packet.getTcpS().getData().length;
if (seq >= base + size) {
return AckFlag.UNORDERED.ordinal();
}
int idx = getIdx(seq);
if (seq < base) {
return AckFlag.DUPLICATE.ordinal();
}
window[idx].setElem(packet, ReceiverFlag.BUFFERED.ordinal());
// if (seq == base) {
// return AckFlag.IS_BASE.ordinal();
// }
return AckFlag.ORDERED.ordinal();
}
在运行过程中记录下 cwnd 和 ssthresh 的变化，使用 Python 绘制图表（截取了前 40 s）：
可以很明显看出慢开始、拥塞避免的过程。在慢开始阶段，cwnd 指数增长，而在拥塞避免阶段，cwnd 线性增长。快重传后，ssthresh 减半，cwnd 重置为 1，重新开始慢开始。
也可以在 Log 中体现出慢开始的过程：
可以看到第一个包被确认后，接下来开始计数的第二个包也被确认，然后是接下来的第四个、第八个包，这是慢开始的过程。
快重传的过程则是连续收到 3 个相同的 ACK，然后重传窗口左沿的包。这里 Sender 的 77501 包丢失，导致了 Receiver 无法收到期望的包，然后连续发了 3 个 99601 包的 ACK，Sender 立即就重传了 99701 包。
|  |  |
再比如 43101 的 ACK 丢失，导致 Sender 超时重传了整个窗口。
所以对于 Tahoe 的关注点实现了以下几点：
- 检查 Log 文件，当出现错误（包含数据包出错、数据包或确认报丢包）时，发方在 3s 后超时重传当前窗口内的所有未收到确认的包；超时重传的包包含发送端已经收到确认的包，基本 TCP 要点实现正确。
- 使用 LinkedBlockingDeque 作为窗口数据结构，方便实现慢开始和拥塞避免。
- 出现超时重传后，窗口大小减小使用 cwnd 和 ssthresh 两个变量控制，慢开始、拥塞避免和快重传的过程符合 Tahoe 的要求。变量的改变影响了 isFull 方法的判断，而已经在窗口内的包由于仍可能需要重传，因此不会立即删除，只有在确认后才会删除。
TCP Reno#
Reno 则是在 Tahoe 的基础上加入了快恢复机制，即当连续收到 3 个相同的 ACK 时，ssthresh 减半，cwnd 重置为 ssthresh 而不是 1。查了一下了解到也有不少人（比如 Linux 内核中）设计成 cwnd 重置为 ssthresh + 3（3 是 lastAckCountLimit），这样相当于对原来进行了一个修正。因此只需修改：
public void ackPacket(int ack) {
// ...
if (lastAckCount >= lastAckCountLimit) {
// 拥塞避免，重置窗口大小
ssthresh = cwnd / 2;
cwnd = ssthresh;
dCwnd = (double) cwnd;
// 快重传
resendPacket(ack);
}
}
依然记录下 cwnd 和 ssthresh 的变化，使用 Python 绘制图表（截取了前 10000 ms）：
可以看到 Reno 的 cwnd 变化和 Tahoe 有所不同，快恢复机制使得 cwnd 在快恢复阶段线性增长，而不是慢开始阶段的指数增长。在平均情况下 Reno 的传输效率要高于 Tahoe。
对于前面迭代的版本所验证的出错、丢包、延迟的问题，TCP Reno 也能很好地解决。
| Sender Log | Receiver Log |
|---|---|
 |  比如这里的 78601 丢失对应数据包的快重传处理。 |
| Sender Log | Receiver Log |
|---|---|
 |  ACK 出错，超时重传整个窗口。 |
综上，对于 Reno 的关注点实现了以下几点：
- 检查 Log 文件，当出现错误（包含数据包出错、数据包或确认报丢包）时，发方在 3s 后超时重传当前窗口内的所有未收到确认的包；超时重传的包包含发送端已经收到确认的包，基本 TCP 要点实现正确。
- 发送过程出现慢开始、加法增大；出现超时重传后，进入快恢复阶段，不进入慢开始。
- 接收方在传输出错时使用 AckFlag 判断收到包的类型，对于按序或者重发的包延迟 500ms 累积确认，其余（乱序）包立即回复 ACK。
- 发送方使用 lastAckCount 计数连续收到 3 个相同的 ACK，快重传后重置窗口大小为 ssthresh 进入快恢复阶段。
实验评估#
未完成关键困难#
所有的关键困难都已经解决，实现了 TCP 的基本功能和 Tahoe、Reno 的拥塞控制。
迭代开发#
使用 Git 进行版本管理，从 RDT 1.0 开始逐个迭代开发，并创建不同分支存放对应代码、修复后续问题。好处是每一个时间点的代码都可以倒回去查看，而且像 TCP 可以直接从 GBN 和 SR 分支中合并代码，十分方便。迭代开发也有利于同学们由浅入深学习 TCP 发展，更好理解不同时间 TCP 协议的差异和进步。
已解决主要问题#
实验过程中时常忘记协议的细节，粗略实现后在写实验报告分析 Log 时经常一边写一边改。
实验过程中有提到，是使用一个窗口一起发送还是逐个分组发送实现的问题。在意义上，我觉得两个都没问题。快重传机制一开始在我的设计策略下显得并不是完成得很好，本应该在连续收到 3 个相同的 ACK 时重传接收方期望的数据包，但在这过程中因为一次发送一个窗口的数据包，如果左沿的包丢失了，则在接下来一整个窗口的 ACK 都会是重复的，导致发送方会收到很多重复的 ACK。尽管快重传机制被触发了，但它重传的数量远大于 1 个。
|  |  |
要避免这个问题应该还是要避免整个窗口一起发送的策略，所以继续修改代码中 TCP_Sender 的 rdt_send 方法，改为不用等到窗口满就发包：
// ...
if (window.isFull()) {
//窗口满，等待窗口滑动
flag = WindowFlag.FULL.ordinal();
// 发送窗口中的数据
// window.sendWindow();
}
while (flag == WindowFlag.FULL.ordinal()) {
//等待窗口滑动
}
try {
window.pushPacket(tcpPack.clone());
} catch (CloneNotSupportedException e) {
throw new RuntimeException(e);
}
window.sendWindow();
// ...
而原来的 sendWindow 方法并没有被删除，在超时重传时还是会用到，我重命名为 resendWindow 方法。
还有一个困扰了有段时间的问题是处理 Receiver 发回的 ACK。以下是修改前后的代码：
| |
主要问题是出在高亮区域比 base < rear 更先判断，导致程序可能出现空指针错误。想到这样也不易读，于是我就改成了右边这样的写法。
实验系统建议#
- 提醒同学们实验的时候不要开 Clash 的 TUN 模式！ 每次都觉得很疑惑，怎么启动了发不出包呢？又或者是每次写着写着怎么突然发不出包了？后来发现是 Clash 的 TUN 模式开着，导致包全都被拦截了。
- 日志里可以把两方的 Log 合在一起，这样可以更好地看到两方的交互。