基本数据链路层协议（第n次学数据链路层，这次一定要理清！——数据链路层最全面有条理的解析（六））

基本数据链路层协议（第n次学数据链路层，这次一定要理清！——数据链路层最全面有条理的解析（六））

基本数据链路层协议

• 有关底层通信模型的基本假设
• 三个单工协议
• • 乌托邦式单工协议
  • 无错信道上的单工停-等协议
  • 有错信道上的单工停-等协议
• 滑动窗口协议（全双工）
• • 1位滑动窗口协议
  • 回退N协议
  • 选择重传协议

有关底层通信模型的基本假设

• 假设物理层、数据链路层和网络层都是独立的进程，他们通过来回传递消息进行通信。
• 主机A希望用一个可靠的面向连接的服务向主机B发送一个长数据流，假设A的数据链路层请求数据时，网络层总能立即满足数据链路层的需求。
• 假设主机不会崩溃。

三个单工协议

乌托邦式单工协议

1. 不考虑任何出错情况。
2. 数据只能单向传输。
3. 接收方缓冲区无限大。

协议由两个单独的过程组成：运行在源主机上的发送过程，运行在目的主机上的接受过程。
发送过程是一个无限的while循环，尽可能快地把数据放在线路上。
接收过程是在等待唯一可能的事件，即到达了一个未损坏的帧发生。
整个处理过程接近于无确认的无连接服务，差错控制和流量控制就要依赖上层解决了。（当然，即使无确认的无连接服务也要做一些差错检测的工作。）

无错信道上的单工停-等协议

1. 不考虑通信信道出错。
2. 数据只能从发送方传到接收方，但帧可以在两个方向上传送。
3. 考虑了接收方接收速率和发送方发送速率不匹配的问题，即进行流量控制。

此问题的一种解决方案显然是建立足够强大的接收器，但这对硬件要求极高，且只是把发送方太快这个问题转移到了网络层考虑。
更一般的解决方案是：接收方从帧中取出数据包并传递给网络层后，给发送方返回一个哑帧，允许其发送下一帧。这种双向传送是交替关系，可使用半双工的物理信道。

有错信道上的单工停-等协议

1. 考虑通信信道出错，若一帧在传输过程中被损坏，接收方可以检测出来，即进行差错控制。
2. 数据只能从发送方传到接收方，但帧可以在两个方向上传送。
3. 考虑了接收速率和发送速率不匹配的问题。

如果只是简单的在发送方设置定时器，超时重传，那么当确认帧丢失时，就会造成帧重复，因此要让发送方在每个帧的头部加入序号，接收方检查序号判断是否为重复帧。
当m号帧发出，代表m-1号帧必定已经被确认，则此时的问题就与m-1号帧完全无关了，因此，序号关系可仅限于后两者，即m和m+1之间，换言之，只需要,一位序号就足够了，即0和1。
发送方发出一帧后启动计时器，若

1. 收到完好确认帧：从网络层获取下一个数据包放入缓冲区覆盖之前的。
2. 收到受损确认帧或计时器超时：不改变缓冲区内容和序号，重传上一帧。

接收方收到有效帧后，检查其序号，若

1. 不是重复帧，去封装传递给网络层。
2. 为重复帧，重新向发送方发送这一帧的确认。

滑动窗口协议（全双工）

☛上面的三个协议均为单工协议，一种实现全双工数据传输的方法是设立两条独立的传输方向相反的单工链路。
☛更好的方法是用一条链路来同时传输两个方向上的数据。如A和B相互传送数据，当然也相互发送确认，接收方只要检查帧头部的类型字段就可区分出是数据帧还是确认帧。
☛该方法仍可继续改进。当收到一个数据帧，接收方并不立即发送单独的确认帧，而是等待本主机的网络层给它传递下一个要发送的数据包，然后将确认信息附加在数据帧上发送出去。这种方式叫做稍待确认，更好地利用的信道的可用带宽。
☛而为了防止接收方长期无数据发送导致一直不返回确认从而导致发送方计时器超时的现象出现，数据链路层需要采用某种自组织方式：等待一个固定时间，如果时间内没有网络层的数据包到来，则发送一个单独的确认帧。
☛滑动窗口协议的本质：在任何时刻，发送方总是维持着一组序号，分别对应于允许它发送的帧，或者是已经发送但还没被确认的帧。同时，接收方也维持着一组序号，对应于一组允许它接受的帧。对于发送方，当网络层的一个数据包到来时，它被赋予窗口中下一个最高序号，且窗口上边界前移一格，收到一个确认时，窗口的下边界也前移一格。
序号的最小值是0，最大值是2ⁿ-1,即序号所占的字段是n位。

1位滑动窗口协议

发送方和接收方窗口大小均为1，即停-等式滑动窗口。n=1，序号为0-1。
正常情况： A的数据链路层先开始发送第一帧。
异常情况：A和B同时试图将各自的0号帧发向对方。B收到A的A0包后，发现携带的不是对B0的确认，因此重发B0，而,由于收到的来自B的第一个B0包携带的不是对A0的确认，就又进行重发A0操作，且携带对B0的确认，B收到后发出B1，并携带对A0的二次确认，而在A收到B的二次确认之前，收到了B对A0的第一次确认，于是发出A1，并携带对B0的二次确认，B收到A1后，发现并非B1的确认，于是重发B1，同时携带对A1的确认，然后，A收到了B所发的携带对A0的第二次确认的B1包，于是重发A1，同时携带对B1的确认，B收到这个携带对B1确认的A1后，发出携带对A1确认的B2……这样的情况同样发生在过早超时的情况下（即使有一方明显地首先开始传输）。每一帧都会被发送多次，严重浪费带宽。

回退N协议

以上的所有协议，都忽略了传播时延。但如果使用卫星信道，会出现这种情况：
带宽50kb/s，传播往返时延500ms，若利用1位滑窗发送1000bit帧长的帧，t=0时发送第一帧，发送时延为20ms，则t=520ms时，确认帧才回到发送方。即信道利用率是20/520=3.8%。可见，从效率角度来看，长传播时延，高带宽，短帧三者的组合是一种灾难。
如果放松“发送一帧前必须有前一帧确认”这一限制，即当面对很长的传播时延时，同时发送w个帧，而不是只发一个，可以获得更高的带宽利用率。如果w选得足够大，发送方就可以连续发送帧，因为在待发送的帧发送之前，前面帧的确认就返回了，发送窗口一直富余。
那么，如何选取合适的w呢？
想象发送窗口大小为w，即一共有w个序号可用，发送完0号，开始发送1号时，0号开始在信道上传播，那么当1号~（w-1）号都发送完成后，如果恰好0号的确认回到了发送端，那么就可以立刻重新使用序号0，以实现不间断的发送帧。即w-1个帧的总发送时延应当等于0号帧的传播时延。这个过程可表示为下式：
设信道带宽为B，帧长L，单向传播时延为D。则

DBP称作延时带宽积，表示链路上最大可容纳的已发送但未被确认的比特数。
当同时传送多帧时，如果这个数据流中某一帧被损坏或丢失，但在发送方发现问题之前，其之后的大量帧已被发出，并即将到达接收方，而损坏帧必将被丢弃，但又要保证按顺序接收，那么接收方该如何处理那些大量的后续帧呢？
有两种方法处理：

1. 接收窗口大小为1，直接丢弃失序的帧
   在图(a)中，发送窗口大小为7，接收窗口大小为1。首先发送方连续发出0-6号，收到Ack0后发7号，收到Ack1后发8号，但2号帧出错，因此直到发送方2号帧计时器超时也没有收到Ack2，接收方丢弃2-8号帧，发送方从2号帧开始依次重传2、3、4、5、6、7、8……
   
   任何时候可同时发送帧的最大个数，即发送窗口的大小，都不能等于可用序号的个数。
   回退N协议中可以使w=MAX_SEQ。
   我们利用一个场景来解释这个限制存在的原因：
   若MAX_SEQ=7，而发送方一次性发送0-7共8个帧，当7号帧的确认返回到发送方后，发送0-7的另外8个帧，然后第二个7号帧的确认也返回了。那么是第二批的8个帧全部正确接收了呢，还是由于这8个帧全都接收失败了，所以又发送了一次第一个7号帧的确认呢？就无法分辨了。因此发送窗口的大小不能超过MAX_SEQ，在本例中即不能超过7。
2. 接收窗口大小不是1，选择重传
   在图(b)中，发送窗口大小为7，接收窗口大小不为1，接收方接收到2号帧出错后，还可继续接受3、4、5、6、7、8，并被数据链路层缓存起来，暂时不交给网络层，但返回给发送方的确认一直是最后一个正确接受的1号帧的Ack1,。发送方的2号帧计时器超时后，重传2号帧，接收方收到后，返回最后一个正确接收的8号帧的Ack8，同时将2、3、4、5、6、7、8按照顺序传递给网络层，然后发送方继续发送9、10、11……
   这里采用了累计确认机制，对所收到的最后一个正确的帧进行确认。
   
   这种策略常常和否定策略结合使用，即当接收方检测到某帧错误时，发送一个否定确认NAK给发送方，立刻触发该帧的重传操作，不必等到相应的计时器超时，可提高协议性能。

数据链路层可以根据帧的确认情况控制是否接收网络层下发的数据，以实现流量控制，限制发送窗口大小。

选择重传协议

上述选择重传这样的非顺序接收容易引发特殊的问题，下面用一个例子来说明：
假设我们使用3位序号，那么发送窗口最大为7，接收窗口也为7。现在发送方发出0-6号帧，接收方正确接收并依次递交给网络层，并发出确认帧，并且向前移动接收窗口到7-5号。然而此时，突发意外，这些所有的确认帧都被摧毁，发送方会以为0号帧发送失败了，因此重发0号帧，而此时，接收窗口恰好包含0号，因此接收方会以为，这个被重发的0号帧就是第二批数据中的新的0号帧，然后将其接收至缓冲区。由于此时0（第一个）、1、2、3、4、5、6号帧都被接受，接收方同样返回最大序号的6号确认。这时，发送方才认为，自己第一批发的0-6号帧全都被正确接收了，于是向前移动窗口，发送7-5号帧。发出7号帧后，接收方正确接收，且由于比它序号小的帧都已收到，所以直接被递交给网络层。接下来，接收方找到刚才接收到的第二个0号帧，作为新一批的0号帧递交给网络层，于是，网络层得到了一个不正确的数据包，协议失败！
解决这个问题的方法是确保接收方在向前移动窗口之后，新老窗口序号没有重叠。即窗口的最大尺寸应该不超过序号个数的一半，w=(MAX_SEQ+1)/2。
如图（c)、(d)所示，若仍使用3位序号，发送窗口、接收窗口大小均为4，若接收方已正确接收0-3号帧，并向前移动窗口，此时确认全部被摧毁，发送方重发0号帧，接收方发现0并不在接收窗口内，因此重新发3号确认帧，发送方就会意识到0-3号已被正确接收，并继续发送4-7号帧。
接收方所需要的缓冲区个数应当等于窗口的大小。发送方所需的计时器数量等同于缓冲区个数。
由于上述的确认帧都是稍待确认，因此如果逆向数据很少时，接收方需要一个辅助的Ack计时器在发送方计时器超时之前返回单独的确认帧。

下一节，我们将聊聊这些基本协议与MAC子层的关系。