《数据通信与计算机网络（第二版）》电子教案
笫六讲
数据链路协议
数据链路协议
将由简单到复杂介绍三个数据链路层的协议。
简单的模型
该模型中有两个主机A和B交换报文。它们各自连接到一个节点机，分别为节点机A和B。节点A和B之间有物理信道直接相连，通过在其上建立的数据链路可以交换由报文构成的帧。
本讲内容
第三章 数据链路层
数据链路协议
停等协议
顺序接收的管道协议
选择重传协议
停等协议
最简单的停等（stop-and-wait）协议
这个协议规定发送方每发送一帧后就要停下来，等待对方已正确接收的确认（Acknowledgement，Ack）帧返回后才能继续发送下一帧 (下面使用类java语言)
Sender
while (1) {
transmit (frame);
try {
receive (ack);
} catch (timeout) {
retransmit (frame);
}
get new frame
}
Receiver
while (1) {
receive (frame);
transmit (ack);
}
停等协议（续）
对前面的改进：
必须将发送的数据帧编以序号来区分是新发送的帧还是重新发送的帧
确认帧Ack也应加上序号以表示是确认哪一帧
用类JAVA代码来描述己加上数据帧序号和确认帧序号的停等协议执行过程，如后面一页所示：
停等协议（续）
Sender
next_frame_to_send= 0;
while (1) {
transmit (frame next_frame_to_send);
try {
while (1) {
receive (ack n);
if (n != next_frame_to_send)
continue;
}
} catch (timeout) {
retransmit(frame);
}
next_frame_to_send ++;
}
Receiver
frame_expected = 0;
while (1) {
receive (frame n);
ack (frame n);
if (n != frame_expected)
continue;
frame_expected ++;
}
再加上接收方校验的过程后停等协议发送方和接收方运行的流程示意图
接受方
0→期待帧号
期待帧号⊕1→期待帧号
恢复报文送主机
等待
校验和检查
收到帧的Seq
=期待帧号
确认帧号Ack = Seq (返回)
不对
对
对
不对
数据帧到达
0→发送帧号
从主机取报文
装配帧
(seq = 发送帧号)
发送,并置计时器
等待
Ack =
发送帧号
发送帧号⊕1→发送帧号
发送方
对
不对
计时器超时
发送数据帧
返回Ack帧
停等协议（续）
停等协议的最大缺点是由于发送方要停下来等待Ack返回后再继续发送而造成信道的浪费。
设信道容量是B bps，帧长度为L bits，信号在信道中的往返传播延迟时间（propagation delay）是2R，并假定返回的Ack帧很短，不占用信道时间。在一个周期中实际用于发送的时间是L/B。而空等待的时间是2R。因此，信道的实际有效利用率只有
停等协议的信道利用率
实际上，若由于信道差错而收不到Ack而造成超时重传以及有效传送的数据必须加上帧头（包括用于校验的冗余位）构成帧来发送，它们也都会造成信道有效利用率的损失。
B为信道容量（b/s）
R为单程传播延迟时间（s）
L为数据帧长度（bits）
并设
D为帧内有效数据的长度（bits）
H为帧头的长度（bits）
显然有，L=H+D。
另外，可以认为Ack帧不含有用户数据，故其长度亦为H。又令
T表示等待Ack的超时间隔时间（s）
P1和P2分别表示数据帧和Ack帧出错或丢失的概率
则每个数据帧不能正确发送和收到确认ACK的概率为
从而可求得最终发送成功所需的平均发送次数为
或者说，平均重传次数为
在 时间内，真正用来发送有效用户数据的时间仅为D / B ，即信道有效利用率为
信通利用率的分析
超时间隔T必须取得足够大，即T≥H/B +2R，才能使得在发送成功时不会由于太早超时而误重传。为了使U达到最大，可取
T= H/B +2R。此时有
停等协议的捎带确认
本讲内容
第三章 数据链路层
数据链路协议
停等协议
顺序接收的管道协议
选择重传协议
顺序接收的管道协议
使用管道协议：
可以提高信道的有效利用率，就要允许发送方不等确认帧返回就再连续发送若干帧
由于允许连续发出多个未被确认的帧，帧号就不能仅采用一位（只有0和1两种帧号），而要采用多位帧号才能区分
凡是被发送出去尚未被确认的帧都可能出错或丢失而要求重发，因而都要保留下来。这就要求发送方有较大的发送缓冲区保留准备重发的帧
顺序接收的管道协议（续）
“回退n”（go back n）
顺序接收的管道协议（续）
回退n的缺陷：允许已发送未被确认的帧越多，可能要退回来重发的帧也越多
改进：发送窗口
为了控制发送方的发送速度以及受发送缓冲区大小的制约等因素都要求对发送方已发出但尚未经确认的帧的数目加以限制，这个数目就是“发送窗口”
落在这个窗口内的帧号就是等待接收返回的Ack信息的帧号。由于帧号只有有限的位数，到一定时间后就又反复循环了
顺序接收的管道协议（续）
滑动窗口（sliding window）协议
若帧号取3位（即000~111，或0号到7号），发送窗口取值为2，则发送的过程
图中发送方阴影所示代表了发送窗口，而接收方阴影所示则可相应地被视为接收窗口。在进行的过程中，窗口位置一直在滑动 （停等协议可以看成是发送窗口等于1的滑动窗口协议的特例 ）
本讲内容
第三章 数据链路层
数据链路协议
停等协议
顺序接收的管道协议
选择重传协议
选择重传协议
选择重传（selective repeat）的工作原理：
选择重传协议（续）
选择重传协议的优点：
在某帧出错时减少了后面所有帧都要重传的浪费
但接收方要有一个足够大的缓冲区来暂存未按顺序正确接收到的帧
可以用滑动窗口的观点来统一看待停等、回退n和选择重传这三种协议，其差别仅在其窗口的大小
练习题
使用回退n协议在3000km长的
若帧号位数为3，窗口尺寸为2，请对选择重传协议画出由初始状态出发下列事件依次发生时的滑动窗口图：发送帧0、发送帧1、接收帧0、接收确认帧0、发送帧2、接收反向确认帧1、接收帧2、重发帧1、接收帧1、接收确认帧2。
在50Kbps的卫星信道上发送1K比特长的帧，确认信号总是由数据帧捎带。帧头很短，使用三位顺序号。对下述三种协议，最大可能达到的信道有效利用率是多少？
(1) 停等协议
(2) 回退n协议
(3) 选择重传协议
在重负荷的50Kbps的卫星信道上，用选择重传协议发送含40位帧头和3960位数据的帧。假定无确认帧，NAK帧为40位，数据帧的出错率为1%，NAK帧的出错率可忽略不计，顺序号是7位，问由于帧头和差错重发而浪费的信道带宽占百分之几？
