捎带确认
在上一篇数据链路层协议设计与实现(1)中，我们看到的几个协议，对于信道的利用率都不高，原因在于数据基本都是单向传输。对于停等协议和自动重传协议来说，其实数据已经是双向传输的，但是反向传输的都是ACK，这样利用率也不高。
针对上述的情况，更好的做法是使用捎带确认的方式，将ACK和将要发送的数据放在一帧里面一起发送，这样可以减少发送的帧数。
使用捎带确认有个问题需要解决。因为我们无法预期下次发送的数据是在什么时候，如果很久都没有数据要发送，这样会导致ACK超时，从而使发送方重发。为了避免等待过长的时间，需要设置一个ACK定时器。当定时器超时，则单独发送ACK，而不是继续等待下次发送的数据。
滑动窗口协议
滑动窗口协议是双向协议，信道两端既是发送方又是接收方，可以提高信道的利用率。
滑动窗口的本质在于任一时刻，发送方都保留一组序号，表示发送方可以发送的帧号，即认为这些帧落在了发送窗口中，同理，接收方也维护一组序号，表示可以接收的帧，认为这些帧落在了接收窗口中。
接收窗口和发送窗口不必有一样的上下界，甚至不需要有一样的大小。下面分别来看下几种滑动窗口协议。
协议的基本接口定义可以参见上篇数据链路层协议设计与实现(1)
1位滑动窗口协议
顾名思义，1位滑动窗口协议的发送窗口和接收窗口大小都为1
public void protocol() {
Frame frame = new Frame();
// 当前正在发送的帧的序列号
int currentSeq = 0;
// 期望收到的帧的序列号
int exceptSeq = 0;
Packet packet = fromNetworkLayer();
frame.setSeq(currentSeq);
frame.setPacket(packet);
frame.setAck(1 - exceptSeq);
toPhysicalLayer(frame);
startTimer(frame.getSeq());
while (true){
EventType event = waitForEvent();
if (event == FRAME_ARRIVAL){
frame = fromPhysicalLayer();
//对于发送方来说，如果收到一个正确的ACK
if (frame.getAck() == currentSeq){
stopTimer(currentSeq);
packet = fromNetworkLayer();
currentSeq = inc(currentSeq);
}
//对于接收方来说，如果收到了期望收到的帧
if (frame.getSeq() == exceptSeq){
toNetworkLayer(frame.getPacket());
exceptSeq = inc(exceptSeq);
}
frame.setPacket(packet);
frame.setSeq(currentSeq);
frame.setAck(1 - exceptSeq);
toPhysicalLayer(frame);
startTimer(currentSeq);
}
}
}
回退n帧协议
在上述的协议中都默认有一个假设，一个帧到达接收方所需的时间加上ACK返回的时间是可以忽略不计的。然而事实却不是如此。如果发送方在ACK到来之后，才发送下一帧，那么信道大部分时间都处于空闲状态。例如，从A端到B端的时间是250ms，那么实际上发送一帧的时间需要(250 + 250)=500ms，因为一帧发送过去需要250ms，ACK返回回来需要250ms
所以更好的方式是，在等待ACK返回的这段时间里，可以多发送几帧，也就是把发送窗口设置大一点。
回退n帧协议的本质是，发送窗口为n，接收窗口为1，发送方会保存已经发送的帧，当接收方没有收到期望的帧时，发送方会重新发送之前已经发送的帧
发送窗口size = 2^n - 1
接收窗口size = 1
public static final int MAX_SEQ = 7;
// 发送窗口，用来保存发送方发送过的帧
private Packet[] packets = new Packet[MAX_SEQ + 1];
public void protocol() {
// 发送方正打算发送帧的帧号
int nextSeq = 0;
// 接收方期望收到帧的帧号
int exceptSeq = 0;
// 发送方期望收到的ACK
int exceptAck = 0;
// 当前发送窗口的size，MAX_SEQ - currentWindowSize表示空闲窗口的大小
int currentWindowSize = 0;
while (true){
EventType event = waitForEvent();
switch (event){
case NETWORK_LAYER_READY:
Packet packet = fromNetworkLayer();
sendData(nextSeq,exceptSeq,packet);
currentWindowSize = currentWindowSize + 1;
nextSeq = inc(nextSeq);
break;
case FRAME_ARRIVAL:
Frame frame = fromPhysicalLayer();
// 接收方收到了期望的帧
if (frame.getSeq() == exceptSeq){
//将数据发送到网络层
toNetworkLayer(frame.getPacket());
// 期望收到下一帧
exceptSeq = inc(exceptSeq);
}
// 如果收到ACK为n，则帧号为n-1,n-2，……的帧接收方也必然收到了(不然不会发送为帧号为n的帧号)
while (between(exceptAck,frame.getAck(),nextSeq)){
//释放发送窗口
currentWindowSize = currentWindowSize - 1;
stopTimer(exceptAck);
exceptAck = inc(exceptAck);
}
break;
case CSKSUM_ERROR:
break;
case TIMEOUT:
// 当超时，从期望收到的ACK开始回退
nextSeq = exceptAck;
for (int i = 1; i <= currentWindowSize; i++){
sendData(nextSeq, exceptAck, packets[nextSeq]);
nextSeq = inc(nextSeq);
}
break;
default:
}
if (currentWindowSize < MAX_SEQ){
enableNetworkLayer();
}else {
disableNetworkLayer();
}
}
}
/**
* 发送一帧
* @param nextSeq 当前发送帧的帧号
* @param exceptSeq 期望收到帧的帧号
* @param packet 分组
*/
private void sendData(int nextSeq, int exceptSeq, Packet packet){
Frame frame = new Frame();
frame.setSeq(nextSeq);
/*假设期望收到帧的帧号为n，那么表示n-1帧(前一帧)肯定是收到了，所有ack=n-1,
又因为帧号是在[0,7]之间循环，n的前一帧 = (n + MAX_SEQ) % (MAX_SEQ + 1)
*/
int ack = (exceptSeq + MAX_SEQ) % (MAX_SEQ + 1);
frame.setAck(ack);
frame.setPacket(packet);
packets[nextSeq] = packet;
toPhysicalLayer(frame);
startTimer(nextSeq);
}
/**
* 可以释放发送窗口空间的情况
* 归根结底需要满足 exceptAck <= currentAck < nextSeq，只不过因为帧号是循坏的，所以需要考虑几种情况
* 帧号循环: 0123456701234567
* @param exceptAck 期望收到的ACK
* @param currentAck 当前收到的ACK
* @param nextSeq 当前准备发送帧的帧号
* @return
*/
private boolean between(int exceptAck, int currentAck, int nextSeq){
boolean condition1 = exceptAck <= currentAck && currentAck < nextSeq;
boolean condition2 = nextSeq < exceptAck && exceptAck <= currentAck;
boolean condition3 = currentAck < nextSeq && nextSeq < exceptAck;
return condition1 || condition2 || condition3;
}
选择性重传协议
如果信道可靠性较高，错误发生的情况较少，那么可以使用回退n帧的协议。但是如果错误发生的比较频繁，大量重传，会导致带宽的浪费。
选择性重传协议的本质在于，保存已收到的帧(即使不是期望收到的帧号)，也就是接收窗口大于1。当收到期望的帧时，就是之前收到的帧一起发送给网络层。
public class SelectRepeatProtocol implements Protocol {
public static final int MAX_SEQ = 7;
public static final int WINDOW_SIZE = 4;
/**
* 用来保存已发送的数据
*/
private Packet[] sendPackets = new Packet[WINDOW_SIZE];
/**
* 用来保存已接收的数据
*/
private Packet[] receivePackets = new Packet[WINDOW_SIZE];
/**
* 用来标记接收窗口被占用的情况，为true，表示第index位已经被占用
*/
private boolean[] arrivals = new boolean[WINDOW_SIZE];
/**
* 是否已经发送了NAK
*/
private boolean noNak = true;
@Override
public void protocol() {
// 正在发送帧的帧号
int nextSeq = 0;
// 接收方期望收到帧的帧号
int exceptSeq = 0;
// 发送方期望收到ACK
int exceptAck = 0;
// 当前发送窗口大小，表示发送方已经发送了多少帧
int sendWindowSize = 0;
// 接收窗口的上限边界
int upper = WINDOW_SIZE;
while (true){
EventType event = waitForEvent();
switch (event){
case NETWORK_LAYER_READY:
// 从网络层获取数据
Packet packet = fromNetworkLayer();
// 保存将要发送的数据保
sendPackets[nextSeq % WINDOW_SIZE] = packet;
sendFrame(DATA,nextSeq,exceptSeq,sendPackets);
// 帧号自增
nextSeq = inc(nextSeq);
// 发送窗口size自增
sendWindowSize = sendWindowSize + 1;
break;
case FRAME_ARRIVAL:
Frame frame = fromPhysicalLayer();
// 收到的是数据帧
if (frame.getKind() == DATA){
/**
* 1. 收到的不是期望的帧
* 2. 还没有发送过NAK
* 同时满足这两个条件，则发送NAK，让发送方重发接收方期望收到的帧
*/
if (frame.getSeq() != exceptSeq && noNak){
sendFrame(NAK,0,exceptSeq,sendPackets);
}else {
// 启动ack定时器，一段时间内，没有反向数据发送，则为ACK单独发送一帧
startAckTimer();
}
// 收到的帧在接收窗口中并且是第一次收到
if (between(exceptSeq,frame.getSeq(),upper) && !arrivals[frame.getSeq() % WINDOW_SIZE]){
// 标记这一帧已经收到
arrivals[frame.getSeq() % WINDOW_SIZE] = true;
// 保存这一帧
receivePackets[frame.getSeq() % WINDOW_SIZE] = frame.getPacket();
//如果接收方期望的帧已经收到，则将接收窗口之前收到的帧一起发送给网络层
while (arrivals[exceptSeq % WINDOW_SIZE]){
toNetworkLayer(receivePackets[exceptSeq % WINDOW_SIZE]);
noNak = true;
//重置标记位
arrivals[exceptSeq % WINDOW_SIZE] = false;
exceptSeq = inc(exceptSeq);
// 接收窗口的上限往前移一位
upper = inc(upper);
startAckTimer();
}
}
}
// 如果收到NAK，并且丢失帧位于发送窗口中，重发丢失的那一帧
if (frame.getKind() == NAK && between(exceptAck, (frame.getAck() + 1) % (MAX_SEQ + 1),nextSeq)){
sendFrame(DATA,(frame.getAck() + 1) % (MAX_SEQ + 1),exceptSeq,sendPackets);
}
// 释放发送窗口
while (between(exceptAck, frame.getAck(),nextSeq)){
stopTimer(exceptAck % WINDOW_SIZE);
exceptAck = inc(exceptAck);
sendWindowSize = sendWindowSize - 1;
}
break;
case CSKSUM_ERROR:
// 收到损坏的帧，若没有发送过NAK，则发送NAK
if (noNak){
sendFrame(NAK,0,exceptSeq,sendPackets);
}
case TIMEOUT:
break;
case ACK_TIMEOUT:
// 没有等到反向的流量进行捎带确认，则单独发送ACK
sendFrame(ACK,0,exceptSeq,sendPackets);
break;
default:
}
}
}
/**
* 发送一帧
* @param kind 帧类型，数据帧，NAK
* @param seq 帧号
* @param exceptSeq 期望收到的帧号
* @param packets 网络分组数据
*/
private void sendFrame(FrameKind kind,int seq,int exceptSeq,Packet[] packets){
Frame frame = new Frame();
if (kind == DATA){
frame.setPacket(packets[seq % WINDOW_SIZE]);
}
frame.setSeq(seq);
frame.setAck((exceptSeq + MAX_SEQ) % (MAX_SEQ + 1));
if (kind == NAK){
noNak = false;
}
if (kind == DATA){
startTimer(seq % WINDOW_SIZE);
}
stopAckTimer();
}
/**
* 检测帧号是否在窗口之中，需要满足
* 窗口下边界 < 检测帧号 < 窗口上边界
* 由于帧号是循坏的，因此需要分别考虑几种情况
* @param except 窗口下边界
* @param current 检测帧号
* @param next 窗口上边界
* @return
*/
private boolean between(int except, int current, int next){
boolean condition1 = except <= current && current < next;
boolean condition2 = next < except && except <= current;
boolean condition3 = current < next && next < except;
return condition1 || condition2 || condition3;
}
}
总结
- 滑动窗口协议是双向协议，可以提供信道的利用率
- 发送窗口和接收窗口的上下界不一定相同
- 在信道错误率较高的情况下，不适合使用回退n帧协议
