02 - 数据链路层的详细认识
主要内容：
- 使用点对点信道的数据链路层
- 使用广播信道的数据链路层
时间有限我这里只写了一部分内容，更详细的内容可以直接看我的笔记第三章数据链路层
1、介绍
数据链路层的任务就是将分组从一个网络中或一个链路上的一端传送到另一端。数据链路层传送的数据单元称为帧（frame）。所以也可以说数据链路层的任务就是在一个网络（或一段链路上）传送以帧为单位的数据
数据链路层属于计算机网络的底层，仅在物理层的上方，在网络层的下方，网络中的主机、路由器等都必须实现数据链路层。数据链路层使用的信道主要有两种类型，点对点信道，广播信道
链路层位置.png
2、使用点对点信道的数据链路层
在点对点信道中最重要的是如何实现可靠传输（在实际中并不会在数据链路层实现可靠传输，而是交给上层）
2.1 封装成帧
2.1.1 帧封装
网络层的IP数据报必须向下传达到数据链路层，在数据报前后分别加上首部和尾部，封装成为一个完整的帧。因为在数据链路层就是以帧为单位传输和处理数据，因此，数据链路层中的帧长就是数据部分加上首部和尾部的长度。
帧的封装.png
2.1.2 帧定界
发送方将帧以比特流的形式发送给接收方(在物理层会转换成电信号)，接收方为了能够处理帧数据，必须正确认识每个帧的开始和结束，这就需要进行帧定界
帧定界有很多种，比如以太网就是在传输的帧与帧之间插入时间间隔来实现，只有首部有帧定界符，尾部没有帧定界符。还有一种就是在帧的首部和尾部都加上一个帧定界符。
帧定界符：
不同类型：
- 如果传输的内容是面向字节的，则使用不可打印的控制字符作为帧定界符
- 如果传输的是面向比特流的内容，则使用特殊的比特组合(比如PPP协议使用的是01111110）
帧定界符在透明传输中的问题和解决
问题： 传输数据存在使用帧定界符所使用的字符或比特组合，会出现错误的帧定界
解决：
- 在数据中的与帧定界符中刚好一样的字符或比特组合前增加一个转义字符
- 接收端的数据链路层在将数据送往网络层之前删除插入的转义字符
- 如果转义字符也出现在数据当中，那么应在转义字符前面再插入一个转义字符，接收端接收到连续的两个转义字符时，就删除前面的一个
注意:
- 链路层的协议要规定好头部和尾部的格式，这样发送方和接收方就可以按照格式去获取帧定界符
- 为了提高帧的传输效率，应当使帧的数据部分的长度尽可能大些。
- 但是考虑到其他因素(比如差错控制)也不能无节制的让数据部分的数据太多，所以每一种数据链路层协议都规定了帧的数据部分长度的上限，叫做最大传达单元
2.2 差错检测
通信链路的传输都不会是理想的，比特在传输过程中可能会产生差错，比如1变为0，0变为1，这叫做比特差错,因此就需要在接收端进行差错检测。
2.2.1 原理
发送方需要采用某种差错检测算法，使用发送的数据计算出差错检测码EDC，差错检测码随数据一起发送给接收方，接收方使用同样的差错检测算法计算出差错检测码EDC'，如果两者不一致，则表示出现差错，一般采用循环冗余检验（CRC）来检错
2.2.2 具体步骤
- 发送方进行差错检测算法并在尾部携带差错检测码（存放在帧检验序列中）
- 接收方进行差错检测
2.2.3 循环冗余检验（CRC）
差错检测算法：
接收双方需要约定好一个多项式，之后按照下图的方式进行处理
发送方和接收方的算法.png
案例说明
发送方的冗余校验：
发送方.png
说明：
- 构造被除数：在原来的待发送信息的基础上，后面需要加上多项式的最高次数个0
- 构造除数：由多项式各项系数组成，这里没有x的一次方，所以它的系数为0
- 做除法这里其实是进行异或操作
- 得到余数后，就将余数加在待传输数据的后面一起传给接收方
- 必须是最高次的位数，如果不够，就用0补足
接收方的冗余校验：
接收方.png
说明：
- 直接使用接收过来的信息作为被除数
- 除数仍然是多项式的各项系数构成的比特串
- 如果余数为0，则表示没有差错，如果不为0，则表示有差错
注意：
- 检错码只能检测出帧在传输过程中出现了差错，但并不能定位错误，因此无法纠正错误
- 要想纠正传输中的差错，可以使用冗余信息更多的纠错码进行前向纠正，但是开销很大，一般是不用的
- 差错检测算法其实只是非常接近于1的概率认为无差错，但并不是真的不会出现差错
2.3 可靠传输
有些情况下数据链路层需要向上层的网络层提供“可靠传输”的服务，也就是发送端发送什么，对应的接收端就必须接收什么。我们通过可靠传输协议来实现数据链路层的可靠传输，有三种，停止等待协议SW、回退N步协议GBN、选择重传协议SR。
可靠传输协议就是要在不可靠的信道上实现可靠的数据传输服务。
在计算机网络中实现可靠传输的基本方法就是：如果发现错误就重传
2.3.1 传输错误的类型
- 比特差错： 比如1变为0，0变为1
- 分组丢失： 路由器的分组队列已满，再次接收到的分组只能丢弃掉
- 分组失序： 数据并未按照发送顺序依次到达接收端
- 分组重复： 由于某些原因，有些分组在网络中滞留了，没有及时到达接收端，这可能会造成发送端对该分组的重发（超时重传机制），重发的分组到达接收端，但一段时间后，滞留在网络的分组也到达了接收端，这就造成分组重复的传输差错
2.3.2 停止等待协议SW
使用分组确认和超时重传机制就可以在不可靠的信道上实现可靠的数据传输。
2.3.2.1 分组确认
- 如何让发送方知道出现差错
- 接收方接收到正确的分组后，要向发送方发送一个确认分组ACK
- 接收方发现出现比特差错时，丢弃该分组，并向发送方发送一个否认分组NAK
- 接收方接收到信息如何处理
- 如果接收到确认分组ACK，则可以发送下一个分组
-
如果接收到否认分组NAK，则重传原来的分组，直到收到ACK为止
分组确认.png
2.3.2.2 超时重传
问题来源： 分组确认有一个问题，底层的信道丢失分组，当数据分组或确认分组丢失时，发送方将会一直等待接收方的确认分组，数据传输停止。
解决： 可以在发送方发送完一个数据分组后，启动一个超时计时器，若超出了设置的重传时间，发送方仍没有收到接收方的任何确认分组，就会重传原来的分组。
超时重传.png
注意： 重传时间的选择一般是略大于“从发送方到接收方的平均往返时间”数据链路层的往返时间是比较确定的，可以使用这种方式
2.3.2.3 数据重复
问题来源： 当确认分组丢失时，发送方将会超时重传，接收方将会接收到两个相同的分组，这就是重复分组，如果接收方无法识别重复分组，则会出现另一种差错，数据重复
解决：
- 使每个数据分组带上不同的发送序号，每发送一个新的数据分组就把他的发送序号加1。
- 只要用一个比特就够了，因为这里是停止等待，只能上一个分组成功了，才能传下一个分组，所以只要保证与上一个分组的序号不一致就可以，不需要考虑上两个、上三个的分组序号
-
这样如果接收方接收到的数据分组的序号相同，则认为出现数据重复，直接丢弃掉重复的分组
- 此时要注意，一定要给发送方补发一个确认分组ACK，要不然发送方还会继续发送相同的分组
-
确认分组也需要带上序号
- 因为如果确认分组并没有丢失，而是发送的太慢，当发送方认为已经超时并重传数据后，前面的确认分组才抵达，这样就会有两个确认分组，所以就需要加上序号，发现两个确认分组的序号相同，则删除重复的确认分组
- 数据链路层的点对点的往返时间比较确定，不太会出现过早超时情况，在数据链路层实现停止等待协议也就可以不对确认分组进行编号
数据重复.png
2.3.2.4 信道利用率
信道利用率.png
说明：
- 假设收发双方之间是一条直通的信道
- TD表示发送方发送数据分组所耗费的发送时延
- RTT表示收发双方之间的往返时间
- TA是接收方发送确认分组所耗费的发送时延
- 由图可以看出，如果往返时延RTT远大于数据帧发送时延TD时，信道利用率非常低
- 如果出现重传，则对于发送有效的数据信息来说，信道利用率还要更低
2.3.2.5 总结
- 发送方每发送完一个分组，必须停下来等接收到确认后才能发送下一个分组。所以这也是停止等待协议名称的来由
- 发送方发送完一个分组后，必须暂时保留已发送的分组的副本，如果超时则可以重传，直到收到相应的确认分组后再删除
- 如果想要使协议更加简单，可以不使用分组确认，而只是使用超时重传，使用分组确认的效率更高，重传的更及时
- 停止等待协议的优点是简单，缺点就是信道利用率太低
- 综上所述，实现停止等待协议，主要就是分组确认和超时重传，简单的情况下可能只有超时重传，对于数据重复的问题可以给数据分组加上序号，数据链路层的确认分组一般是不用加序号的
2.3.3 回退N步协议GBN
上面也可以看到停止等待协议的信道利用率很低，所以需要采用流水线传输方式，发送方不间断的发送分组来提高信道利用率。但是这种方式有可能会使接收方来不及处理这些分组，从而导致分组的丢失。因此需要限制发送方连续发送分组的个数避免这个问题，而这种方式就是回退N步协议。
简单理解回退N步协议就是停止等待协议只能发送一个分组就等待，回退N步协议是发送多个分组才处于等待状态
原理： 回退N步协议在流水线传输的基础上利用发送窗口来限制发送方连续发送分组的个数，是一种连续的ARQ协议
2.3.3.1 过程（以窗口大小为5来说）
- 发送方可以连续发送多个分组，直到有5个分组没有接收到确认分组
- 如果发送方收到一个确认分组，窗口就会向前滑动一个分组的位置，保证窗口的分组个数为5
- 注意这里的向前滑动的意思是向后面的分组滑动
- 这里在工作过程中发送窗口不断的向前滑动，因此这类协议又称为滑动窗口协议
- 如果发送方收到的是否认分组，或者超时，也就是这个分组发送失败，那么会把这个分组以及排在它后面的其他分组一起重新发送
- 因为这个分组失败了，后面的分组进入就会是无序分组，会被丢弃
注意：
- 接收方只按序接收分组
- 也就是说，如果前面有一个分组出现差错，需要重传，那么后面就算有其他的分组没有出现差错，也必须丢弃掉
- 发送方依然采用超时机制来重传出现差错或丢失的分组
- 因为接收方只按序接收分组，所以一旦某一个分组出现差错，那么后续连续发送的所有分组都要重传
- 最多会重传窗口大小个分组，这也是回退N步协议这个名称的来由
- 接收方采用累积确认的方式确认
- 接收方对分组N进行确认，说明已经正确接收到分组N之前的所有分组
- 因此不需要对收到的分组逐个发送确认分组
- 而是可以在收到几个分组后对按序到达的最后一个分组发送确认
2.3.3.2 总结
- 协议规定，发送方每收到一个确认，就把发送窗口向前滑动一次位置，在协议工作过程中发送窗口和接收窗口不断的向前滑动，这些协议就又被称为滑动窗口协议
- 滑动一次窗口是在接收到一次确认分组后进行的
- 累积确认并不能准确的向发送方准确反映出接收方已经正确收到所有的分组
- 接收窗口的大小为1，因此接收方只能按序接收正确到达的数据分组
- 一个分组的差错，会导致大量分组的重传，这些分组可能已经被正确接收了，只是由于没有按序到达，就需要丢弃，也是对信道的极大浪费
2.3.4 选择重传协议SR
选择重传协议是在回退N步协议的基础上，只重传出现差错的分组，这时接收窗口不再为1，以便先收下失序到达但仍然处于接收窗口中的分组，等到所缺分组收齐后再一并送交上层，这就是选择重传协议。
注意：
- 接收窗口不能为1，如果出现差错，需要先把后到达的已经确认的分组存放到接收窗口中，不送交上层，也不丢弃，需要存放到接收窗口中
- 接收方不能使用累积确认的方法，因为现在就有可能后面的分组已经确认没有差错，但是中间的分组是有差错的
