数据链路层（上）
数据链路层（上）
1.链路层导图
数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报
2.数据链路层概述
结点：主机、路由器
链路：网络汇总两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤和微波。分为有有线链路、无线链路
数据链路：网络中两个结点之间的逻辑通道，吧实现控制数据传输协议的硬件和软件加到链路上就构成数据链路
帧：链路层的协议数据单元，封装网络层数据报
数据链路层在物理层提供服务的基础上，下个网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻结点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
功能一：为网络层提供服务，无确认无连接服务，有确认无连接服务，有确认面向连接服务。（有连接就一定有确认！）
功能二：链路管理，即连接的建立、维持、释放（用于面向连接的服务）
功能三：组帧
功能四：流量控制，限制发送方
功能五：差错控制（帧错/位错）
3.帧的相关概念
是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧，接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。其中，首部和尾部包含了许多的控制信息，他们有一个重要的作用：帧定界（确定帧的界限）
接收方应当从接收的二进制比特流中区分出帧的起始和终止
透明传输：是指不管所传输数据是什么样的比特组合，都应当能够在链路上传送，因此，链路层就“看不见”有什么妨碍数据传输的东西，而当所传数据中的比特组合恰巧与某一控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息，这样子才能保证数据链路层的传输是透明的
1.字符计数法
2.字符（节）填充法
3.零比特填充法
4.违规编码法
4.差错编码
概括来说，传输中的差错都是由于噪声引起的
全局性：由于线路本身电气性质所产生的随机噪声（热噪声），是信道固有的，随机存在的。解决办法是提高信噪比来减少或避免干扰（对传感器下手）
局部性：外界特定的短暂原因所造成的冲击噪音，是产生差错的主要原因。解决办法是通常利用编码技术来解决
冗余编码：在数据发送前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之辩护，使得码字遵从不变的规则，接收端根据收到码字是否符合原规则，从而判断是否出错
5.检错编码
在接收端检错过程中，会把收到的每一个帧都除以相同的除数，然后检查得到的余数R。如果余数为0，则判定这个帧没有差错进行接受；如果余数不为0，则判定这个帧有差错（无法确实到位）进行丢弃
FCS生成以及接受段CRC检验都是由硬件实现，处理很迅速，因此不会延误数据的传输
6.纠错编码
两个合法编码（码字）的对应比特取值不同的比特数称为这两个码字的海明距离（码距），一个有效编码集中，任意两个合法编码（码字）的海明距离的最小值称为该编码集的海明距离（码距）
假设数据的位数m=4，那么满足不等式的最小r为3，也就D=1100的海明码应该有4+3=7位，其中原数据4位，校验码3位
7.流量控制
在现实中，较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。
数据链路层的流量控制是点对点的，其控制手段是接收方收不下就不回复确认
传输层的流量控制是端到端的，其控制手段是接收端给发送端一个窗口公告
停止—等待协议：发送窗口大小=1，接收窗口大小=1
后退N帧协议（GBN）：发送窗口大小>1，接收窗口大小=1
选择重传协议（SR）：发送窗口大小＞1，接收窗口大小＞1
发送端发啥，接收端就收啥
控制发送速率，使得接收方有足够的缓冲空间来接收每一帧
滑动窗口的解决依靠流量控制和可靠传输，通过流量控制如果收不下就不给确认，让发送方想发也发不了，以及依靠可靠传输让发送方自动重传
8.停止—等待协议
在传输过程中，除了比特出现差错，底层通信还会出现丢包问题。为了实现流量控制而产生
丢包：物理线路故障、设备故障、病毒攻击、路由信息 错误等原因，会导致数据包的丢失
9.后退N帧协议（GBN）
由于停止—等待协议的利用率不高，作为流水线技术，存在一定弊端，所以出现了新的协议
1、上层的调用：
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送，如果窗口已满，则发送方只需将数据返回给上层，暗示上层窗口已满。上层等一会再发送。（实际实现中，发送方可以缓存这些数据，在窗口不满时再发送帧）
2、收到了一个ACK：
GBN协议中，对n号帧的确认采用累计确认的方式，标明接收方已经在收到n号帧和它之前的全部帧
3、超时事件：
协议的名字为后退N帧/回退N帧，开源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中的一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧
1、发送ACK：
如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中 的数据部分交付给上层
2、维护expectedseqnum信息
其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任 何失序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序 号）
若采用n个比特对帧编号，那么发送窗口的尺寸WT 应满足：1≤ WT≤2^n-1。因为发送窗口尺寸过大，就会使得接收方无法区别新帧和旧帧。
1、累积确认
2、接收方只按顺序接收帧，不按序无情丢弃
3、确认序列号最大的，按序到达的帧
4、发送窗口最大为2^n-1，接收窗口大小为1
优点是因连续发送数据帧而提高了信道利用率，缺点是在重传时必须吧原来已经正确传送的数据帧重传，使得传送效率降低
10.选择重传协议（SR）
在GBN协议中，尽管有了改进，但是为了实现能不能只重传出错的帧从而提高传输效率的思想，提出了SR协议，通过设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧
1、上层的调用：
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否则就像GBN一样，要么将数据缓存，要么返回给上层之后再传输
2、收到一个ACK
如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果是该帧序号是窗口的下界（最左边第一个窗口对应 的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧
3、超时事件
每个帧都有自己的定时器，一个超时事件发送后只重传一个帧
来者不拒：SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧【收谁确认谁】，直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口
如果收到了窗口序号外（小于窗口下界）的帧，就返回一个ACK，其他情况，就忽略该帧
发送窗口最好等于接收窗口。（大了会溢出，小了没意义）
WTmax=WRmax=2^(n−1)
1、对数据帧逐一确认，收一个确认一个
2、只重传出错帧
3、接收方有缓存
4、WTmax=WRmax=2^(n−1)