在上述的协议中，数据帧只在一个方向上传输，会比较低效，低效的原因可能在于 _______ 。而这一小节作者较介绍了一种新的协议，旨在实现“两个方向上传输数据”、“数据链路层在接收到一个确认之前可以同时发送多个帧”。作者将上述目标概括为了8个字：_______，________。
作者引入了两个概念：
1. _______ ，它可以帮助一个数据链路层协议做到双向传输。
2. _______ ，它允许 ______ 方有多个字节在传输途中，从而提高传输效率。
当一个数据帧到达时，接收方并不是立即发送一个单独的 _______ ，而是 ______ ，直到网络层传递给它下一个数据包。确认信息被附加在 ______ 的 ______ 字段。这就是捎带确认。
它的最主要的好处在于：更好地利用了信道的 _______。但是这种方法存在的一个问题在于，在捎带之前，需要 _______ 。
在停等式协议中，采用了对帧进行编号的思想。而滑动窗口协议的本质是：在任何时刻发送方总是维护着一组序号（发送窗口），分别对应于 ________ 。同时接收方也维护着一个接收窗口，对应于 _______。
发送窗口里的序号，代表了那些 _______ 或者 ______ ，但还没有被确认的帧。任何时候，当有新的数据包从 ______ 到来时，它被赋予窗口中的下一个最高序号，并且发送窗口的上边界向 （前或后？）移一格。当收到一个确认时，发送窗口的 ______ （上或下？）边界也前移一格。按这种方法， 窗口持续地维护着一系列未被 ______ 的帧。请读者仔细思考此处涉及到的上边界和下边界的概念，从中体味到滑窗以及多帧在途的感觉(●ˇ∀ˇ●)。
由于当前在发送窗口中的帧有可能丢失或者损坏，所以发送方需要在 ______ 中保留这些帧，以满足 ______ 的需要。因此如果最大的窗口大小为n，则发送方需要 ______ 个 ______ 来存放______ 。如果发送窗口达到了 ______ ，则发送方的数据链路层必须强行关闭 ______ ，直到有下一个缓冲区空闲出来为止。
Question：
- 为什么捎带确认能在一定程度上减轻接收方的工作负担？
- 如何解决接收方进行捎带确认时的等待问题？
#define MAX_SEQ 1
typedef enum{ frame_arrival, cksum_err, timeout } event_type;
#include “protocol.h”
void protocol4 (void){
seq_nr next_frame_to_send;
seq_nr frame_expected;
frame r,s;
packet buffer;
event_type event;
next_frame_to_send = 0;
frame_expected = 0;
from_network_layer(&buffer);
s.info = buffer;
s.seq = next_frame_to_send;
s.ack = 1 - frame_expected;
to_physical_layer(&s);
____1____；
while(true){
wait_for_event(&event);
if(event == frame_arrival){
_____2____ ;
if(r.seq == frame_expected){
to_network_layer(&r.info);
inc(frame_expected);
}
if(r.ack == next_frame_to_send){
stop_timer(r.ack);
_____3____;
inc(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);
}
}
Question：
- 与发送方封装成帧相关的代码段是哪些？
- 补充空格1处的代码内容 ________
- 补充空格2处的代码内容 ________
while语句中，if(event == frame_arrival)运行完后，又通过s.info = buffer; s.seq = next_frame_so_send; s.ack = 1 - frame_expected;对s进行了一系列赋值。请问 s.ack 的含义是什么？它的作用是什么？if(r.ack == next_frame_to_send)这个if语句的作用是什么？如何理解其中的stop_timer(r.ack)和inc(next_frame_to_send)？- 补充空格3处的代码内容 ________
上面提到滑动窗口，只是简单的1位窗口。而这小节，作者先用一个例子，引入了多位滑动窗口，进而引申出管道化（pipelining）。
请读者先思考下面这个例子，给定一个50kb/s的卫星信道，它的往返传播延迟为500ms，它将使用上面提到的1位滑动窗口来发送长度为1000位的帧。在第t=0时开始发送第一帧。
Question：
1. 请问第一帧何时才能完全发送出去？
2. 假设接收方在接收帧时不需要停顿，并且能够立即传出确认帧，那么第一帧的确认帧何时才能到达发送方？
3. 请你计算出上述过程中，发送方参与的时间与过程的总时间之比，这个值即为有效宽带的利用率。
因此我们可以得出，如果发送方在发送下一帧必须等到 ________ ，那么必将会带来效率的低下。因此为了提高效率，很自然而然的就是发送方 ________ ，记其个数为w。
因此需要寻找一个合适的w，所以我们需要知道在一帧从发送方传到接收方期间 ________ ，而这个容量是由带宽乘以 单向 传送时间决定的。也被称为链路的 _______ 。例如上面的例子，带宽延迟乘积为 ________ （注意看清单向传送时间还是往返传送时间哦），将这个值除以一帧的位数，得到的值记为BD，则w与BD的关系为 _______ 。
对于w与BD的关系，关键点就在于需要明确在确认帧达到发送方之前，发送方可以不停地发送帧，于是“多帧在途”；同时第一帧是有长度的，虽然能够被接收方瞬间接收（理想情况下），但是需要花费20ms才能够从发送方完全传输过去。所以很容易得出，第一帧从发送方开始发出到确认帧返回发送方所用的总时间为20+250（单向传输时间）+250（单向传输时间），那么知道了总时间以及完全发送出一帧的时间，传输途中的帧的数量w也就可以得出了。
对于上面这个例子，在t=520ms时，发送方已经发送的帧的数目为 ______ ，此时 ______ 刚好到来，此后每隔 ______ ms就会到达一个确认，因此发送方在需要时总能够继续发送帧。
这种保持多个帧同时在传输途中的技术叫做 _______ 。而对于处理这种技术在传输中可能出现的错误，可以采用 _______ 和 ________ 的方法。
Question： 在一条不可靠的通信信道上像管道一样传送帧，如果一个长的数据流的中间某一帧被损坏或丢失，会发生什么事情？在发送方发现错误以前，大量的后续帧将到达接收方，当损坏的那个帧到达接收方时，接收方应该做什么？当后续正确帧到达后，接收方应该如何处理？
对于回退n协议，某一帧出错后，接收方将 _______ 后续所有帧，而且对这些帧不发送 _______ 。这种策略对应的窗口大小为 ________ 。如果在计时器超时以前，发送方 _______ ，则管道开始空闲。最终 _______ ，并且按照顺序 _______ 。
Question：
- 如果错误率比较高，使用回退n协议会有什么问题？
- 接收方的窗口为1，0号帧，1号帧，2号帧都被正确接收和确认，但是3号帧出现了损坏，之后发送方将进行怎样的操作？接收方呢？
// Go-back-n
# define MAX_SEQ 7
typedef enum{frame_arrival, cksum_err, timeout, network_layer_ready} event_type;
# include"protocol.h"
static boolean between(seq_nr a, seq_nr b, seq_nr c){
if(((a <= b) && (b < c) || (c < a) && (a <= b)|| (b < c) && (c < a)))
return true;
else
return false;
}
static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer[]){
frame s;
s.info = buffer[frame_nr];
s.seq = frame_nr;
s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1);
to_physical_layer(&s);
_____1_____;
}
void protocol5(void){
seq_nr next_frame_to_send;
seq_nr ack_expected;
seq_nr frame_expected;
frame r;
packet buffer[MAX_SEQ + 1];
seq_nr nbuffered;
seq_nr i;
event_type event;
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
nbuffered = 0;
while(true){
wait_for_event(&event);
switch(event){
case _____2_____;:
from_network_layer(&buffer[next_frame_to_send]);
nbuffered = nbuffered + 1;
send_data(next_frame_to_send, frame_expected, buffer);
inc(____3____);
break;
case frame_arrival:
from_physical_layer(&r);
if(r.seq == frame_expected){
to_network_layer(&r.info);
inc(____4____);
}
while(between(ack_expected, r.ack, next_frame_to_send)){
nbuffered = nbuffered - 1;
stop_timer(ack_expected);
inc(____5____);
}
break;
case cksum_err: break;
case timeout:
next_frame_to_send = ack_expected;
for(i = 1; i <= nbuffered; i++){
send_data(next_frame_to_send, frame_expected, buffer);
inc(____6____);
}
}
if(nbuffered < MAX_SEQ)
enable_network_layer();
else
disable_network_layer();
}
}
Question：
ack_expected的含义是什么？network_layer_ready的作用是什么？什么情况下，该事件可以被触发？static boolean between(seq_nr a, seq_nr b, seq_nr c)函数的作用是什么？为什么函数体中，要进行如下判断if(((a <= b) && (b < c) && || (c < a) && (a <= b)|| (b < c) && (c < a)))，提示：帧序号增加使用的是模运算。- 补充空格1处的代码内容 ________
- 补充空格2处的代码内容 ________
- 为什么触发
timeout事件后，要令next_frame_to_send = ack_expected - 在上述代码中，出现了四次
inc操作，分别对应空格3、4、5、6，请读者进行填充 _______ 、 _______ 、 _______ 、 _______ 。 - 假设有
MAX_SEQ+1个帧在传输途中未被确认，接收方收到了所有帧，但是所有帧的确认帧在发回的过程中都丢失了。请问此时接收方的frame_expected值为多少？发送方的next_frame_to_send的值为多少？这说明了什么？ - 在问题8的情形下，当发送方超时重传这MAX_SEQ+1个帧，接收方成功地接收到了这些帧，这会导致什么问题？
使用选择重传策略时，接收到的坏帧被 _______ ，但之后接收到的任何好帧都被 _______ 。当发送方超时时，只有 ________ 被重传。如果该帧正确到达，则接收方就可按顺序将 ________ 递交给网络层。选择重传对应的接收窗口长度 _______ 。
当接收方检测到错误时，它会发送一个 _______ ，它可以出发该帧的 _______ ，而不需要等到相应的 _______ ，因此可以提高协议性能。
在这个协议中，发送方和接收方分别维护一个 ________ 的窗口和 _______ 的窗口。发送方的窗口大小从 _______ 开始，逐渐增加到一个预设的最大值。 接收方窗口恒等于预设的最大值。接收方为其窗口中每个序号保留了一个 _______ ，与之关联的还有一个标志位（arrived），它的作用是 _______ 。
// Selective repeat
#define MAX_SEQ 7
#define NR_BUFS ((MAX_SEQ + 1)/2)
typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout} event_type;
# include"protocol.h"
boolean no_nak = true;
seq_nr oldest_frame = MAX_SEQ + 1;
static boolean between(seq_nr a, seq_nr b, seq_nr c){
if(((a <= b) && (b < c) || (c < a) && (a <= b)|| (b < c) && (c < a)))
return true;
else
return false;
}
static void send_data(frame_kind fk, seq_nr frame_nr, seq_nr frame_expected, packet buffer[]){
frame s;
s.kind = fk;
if(fk == data) s.info = buffer[frame_nr % NR_BUFS];
s.seq = frame_nr;
s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1);
if(fk == nak) no_nak = false;
to_physical_layer(&s);
if(fk == data) start_timer(frame_nr % NR_BUFS);
stop_ack_timer();
}
void protocol6(void){
seq_nr ack_expected;
seq_nr next_frame_to_send;
seq_nr frame_expected;
seq_nr too_far;
int i;
frame r;
packet out_buf[NR_BUFS];
packet in_buf[NR_BUFS];
boolean arrived[NR_BUFS];
seq_nr nbuffered;
event_type event;
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
too_far = BR_BUFS;
nbuffered = 0;
for(i = 0; i < NR_BUFS; i++) arrived[i] = false;
while(true){
wait_for_event(&event);
switch(event){
case network_layer_ready:
nbuffered ++;
from_network_layer(&out_buf[next_frame_to_send % NR_BUFS]);
send_frame(data, next_frame_to_send, frame_expected, out_buf);
inc(next_frame_to_send);
break;
case frame_arrival:
from_physical_layer(&r);
if(r.kind == data){
if((r.seq != frame_expected) && no_nak)
send_frame(nak, 0, frame_expected, out_buf);
else
start_ack_timer();
if(between(frame_expected, r.seq, too_far) && (arrived[r.seq % NR_BUFS] == false)){
arrived[r.seq % NR_BUFS] = true;
in_buf[r.seq % NR_BUFS] = r.info;
while(arrived[frmae_expected % NR_BUFS]){
to_network_layer(&in_buf[frame_expected % NR_BUFS]);
to_nak = true;
arrived[frame_expected % NR_BUFS] = false;
inc(frame_expected);
inc(too_far);
start_ack_timer();
}
}
}
if((r.kind == nak) && between(ack_expected, (r.ack+1)%(MAX_SEQ+1),next_frame_to_send))
send_frame(data, (r.ack + 1) % (MAX_SEQ + 1), frame_expected, out_buf);
while(between(ack_expected, r.ack, next_frame_to_send)) {
nbuffered = nbuffered - 1;
stop_timer(ack_expected % NR_BUFS);
inc(ack_expected;)
}
break;
case cksum_err:
if(no_nak) send_frame(nak, 0, frame_expected, out_buf);
break;
case timeout:
send_frame(data, oldest_frame, frame_expected, out_buf);
break;
case ack_timeout:
send_frame(ack, 0, frame_expected, out_buf);
}
if(nbuffered < NR_BUFS) enable_network_layer();
else disable_network_layer();
}
}
Question：
boolean arrived[NR_BUFS]的作用是什么？如果arrived的值为[false,true,true,false,false...]，第一个值为false，但是后面两个为true，这说明了什么？- 在问题1的情形下，假设没有传输错误同时假设
frmae_expected为0（对应arrived数组的第一个值的序号），当arrive数组第一个值变为true时，接下来会发生什么？对应的代码是哪一部分？ start_ack_timer()是辅助计时器，它的作用是什么？- 辅助计时器的超时值与数据帧计时器的超时值的关系是怎样的？
- 结合P192的例子，理解
NR_BUFS取值为何为MAX_SEQ + 1)/2
这一部分，作者主要介绍了三个常见情形下Internet上点到点线路的数据链路协议。第一种情形是通过广域网中的 _____ 光纤链路发送数据包的时候；第二种情形是运行在Internet边缘的电话网络本地回路上的ADSL链路。第三种情形是在有线电视网络的本地回路中的DOCSIS链路。一个称为 ______ 的标准协议被用在这些链路上发送数据包。（由于后两种情形涉及到第二章和第四章的很多内容，故先不作梳理~）
SONET是物理层协议，最常被用在广域网的 ______ 上。_______ 提供了一个以定义良好的_____ 运行的 ______，该比特流被组织成固定 ______ 的有效载荷，无论用户是否发送数据，每隔一段时间都要发送一个比特流。
为了运载数据包，将偶尔出现的数据包从传输它的连续比特流中区分出来，需要 ______。运行在IP路由器上的 _______ 就提供了这种机制。
PPP提供了三个特性：
1. _______（关键词：帧）
2. _______（关键词：链路控制）
3. _______（关键词：协商网络层）
PPP使用的是 ______ 填充技术，在internet中几乎采用一种 _______（一种模式）提供 _______ 的服务。
下面读者请回忆，“无编号模式”下的PPP帧的格式。
① Flag
② Address
③ Control
④ Protocol
⑤ _______
⑥ _______
⑦ _______
Question：
- 所有的PPP帧都从标志字节0x7E（二进制为 _______ ）开始。如果该标志字节如果出现在数据部分（在这里也被称之为Payload，负载），需要用 ______ 来进行填充。转义字节为0x7D，紧接着是被转义字节与0x20进行异或运算的结果，这两个字节构成了转义序列。那么，标志字节0x7E转义后的序列为 ______。
- 请读者思考为什么这种方法能够方便的找出帧的开始和结束？（与第三章一开始的成帧部分基本一致）
- 接收方收到一个帧后，需要 ______ 。具体做法是？（相当于一串逆过程。值得注意的是，字符串s1与字符串s2进行连续两次异或操作，将再次得到原字符串s1）