王道考研计算机网络2020版笔记
数据链路层的基本概念
1、节点：主机、路由器
2、链路：网络中两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤和微波。分为有线链路和无线链路。
3、数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成了数据链路。
4、帧：链路层的协议数据单元，封装网络层数据报。
数据链路层的功能
数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。
数据链路层的主要功能：数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻结点的目标机网络层。其主要作用是加强物理层传输原是比特流的功能，将物理层提供的可能出错的物理连接改为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
**功能一：为网络层提供服务。**无确认无连接服务，有确认无连接服务，有确认面向连接服务。有连接一定是有确认的！！！
**功能二：链路管理，**即连接的建立、维持、释放（用于面向连接的服务）
功能三：组帧。
封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。
首部和尾部包含许多的控制信息，一个重要作用：帧定界（确定帧的界限）。
帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。
组帧的四种方法：1、字符计数法，2、字符（节）填充法，3、零比特填充法，4、违规编码法。
透明传输是指不管所传输的数据是什么样子的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。当所传输的数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。
1、字符计数法：帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数。
2、字符填充法：SOH(Start of header)+装在帧中的数据部分+EOT(end of transmission)
当传送的帧是由文本文件组成时（文本文件的字符都是从键盘上输入的，都是ASC II码），不管从键盘上输入什么字符都可以放在帧里传过去，即透明传输。
当传送的帧是由非ASCII码的文本文件组成时，就要采用字符填充方法（添加转义字符）实现透明传输。
3、零比特填充法
在发送端，扫描整个信息字段，只要连续5个1，就立即填入1个0。
在接收端收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描。发现连续5个1时，就把后面的0删除。
保证了透明传输：在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的错误判断。
4、违规编码法
可以采用“高-高”，“低-低”来定界帧的起始和终止。
由于字节计数法中Count字段的脆弱性（其值若有差错将导致灾难性后果）及字符填充实现上的复杂性和不兼容性，目前较为普遍使用的帧同步法是比特填充和违规编码法。
功能四：差错控制（帧错/位错）。
差错从何而来
概括来说，传输中的差错都是由于噪声引起的。
全局性：1、由于线路本身电气特性所产生的随机噪声（热噪声）是信道固有的，随机存在的。
解决办法：提高信噪比来减少或避免干扰。
局部性：2、外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法：通常利用编码技术解决。
差错分为：
1、位错：比特位出错，1变成0，0变成1
2、帧错：帧丢失、帧重复、帧失序。
数据链路层的差错控制
针对于比特错：
1、差错编码：奇偶校验码、循环冗余码CRC
2、纠错编码：汉明码
数据链路层编码与物理层的数据编码与调制不同。物理层编码针对的是单个比特，解决传输过程中比特的同步问题，如曼彻斯特编码。而数据链路层的编码针对的是一组比特，它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。
冗余编码：在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否符合原规则，从而判断是否出错。
奇偶校验码（n-1位信息元，1位校验元）：
1、奇校验码：1的个数为奇数
2、偶校验码：1的个数为偶数
奇偶校验码的特点：
只能检查出奇数个比特错误，检错能力为50%。
检错编码—CRC循环冗余码
接收端检错过程：
把收到的每一个帧都除以同样的除数，然后检查得到的余数R。
1、余数为0，判定这个帧没有差错，接受。
2、余数不为0，判定这个帧有差错（无法确定到位），丢弃。
FCS的生成以及接收端CRC检验都是硬件实现，处理很迅速，因此不会延误数据的传输。
在数据链路层仅仅使用循环冗余编码CRC差错检测技术，只能做到对帧的无差错接收，即“凡是接收端数据链路层接受的帧，我们都能以非常接近于1的概率认为这些帧在传输的过程中没有产生差错“。”接收端接受的帧虽然曾收到了，但是最终还是因为有差错被丢弃“。”凡是接收端数据链路层接受的帧均无差错“。
海明码
发现双比特错，纠正单比特错
工作流程
确定校验码位数r ——>确定校验码和数据的位置——>求出校验码的值——>检错并纠错
1.确定校验码位数r
海明不等式：2^r >= k+r+1，r为冗余信息位，k为信息位
功能五：流量控制。
流量控制与可靠传输机制
数据链路层的流量控制：较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。
数据链路层的流量控制是点对点的，传输层的流量控制是端到端的。
数据链路层流量控制手段：接收方收不下就不回复确认。
传输层流量控制手段：接收端会给发送端一个窗口公告。
流量控制方法：
1.停止-等待协议
每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。
发送窗口大小=1，接收窗口大小=1
为什么要有停止等待协议：
除了比特出差错，底层信道还会出现丢包问题。
为了实现流量控制
研究停止-等待协议的前提：
虽然现在常用全双工通信方式，但是为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据（接收方）。
因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传输的。
“停止-等待”就是每发送完一个分组就停止发送，等待对方确认ACK，在收到确认后再发送下一个分组。
停止等待协议——有差错情况
1.数据帧丢失或检测到帧出错
超时计时器：每次发送一个帧就启动一个计时器。超时计时器设置的重传时间应当比帧传输的平均RTT更长一些。
发送完一帧后，必须保存它的副本。
数据帧和确认帧必须编号。
2.ACK丢失
丢失重复的数据帧，重传确认帧
3.ACK迟到
丢失重复的数据帧，重传确认帧；迟到的确认帧丢失
停止等待协议特点：
信道利用率低
信道利用率：发送方在一个发送周期内，有效地发送数据所需要的时间占整个发送周期的比率。
信道吞吐率 = 信道利用率*发送方的发送速率
2.滑动窗口协议：
后退N帧协议（GBN）
发送窗口：发送方维持一组连续的允许发送的帧的序号。
接收窗口：接收方维持一组连续的允许接收帧的序号。
发送窗口大小>1，接收窗口大小=1
GBN发送方必须响应的三件事
1、上层的调用
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送；如果窗口已满，发送方只需将数据放回给上层，暗示上层窗口已满。上层会等一会再发送。（实际中，发送方可以缓存这些数据，窗口不满时再发送帧）。
2、收到一个ACK
GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和它之前的全部帧。
3、超时事件
协议的名字为后退N/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像停止等待协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。
GBN接收方要做的事
如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中的数据部分交付给上层。
其余情况都丢失帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序号）。
GBN协议重点：
1、累积确认（偶尔捎带确认）
2、接收方只按顺序接收帧，不按序无情丢弃
3、确认序号最大的、按序到达的帧
4、发送窗口最大为2^n-1，接收窗口大小为1
GBN协议性能分析
因连续发送数据帧而提高了信道利用率。
在重传时必须把已经正确传送的数据帧重传，传续效率降低。
选择重传协议（SR）
设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧。
发送窗口大小>1，接收窗口大小>1
SR发送方必须响应的三件事
1、上层的调用
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否则就像GBN一样，要么将数据缓存，要么返回给上层后再传输。
2、收到一个ACK
如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了，并且有序号在窗口内的未发送帧，则发送这些帧。
3、超时事件
每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。
SR接收方要做的事
来者不拒（窗口内的帧）：SR接收方将确认一个正确接收的帧而不管其是否有序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧（收谁确认谁），直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口。
滑动窗口的大小：
发送窗口最好等于接收窗口。（大了会溢出，小了没意义），最大为2^(n-1)
可靠传输：发送端发啥，接收端收啥。
流量控制：控制发送速率，使接收方有足够的缓冲空间来接收每一个帧。
滑动窗口解决问题：
1.流量控制：收不下就不给确认，想发也发不了
2.可靠传输：发送方自动重传
SR协议重点：
1、对数据帧逐一确认，收一个确认一个
2、只重传出错帧
3、接收方有缓存
4、WTmax= WRmax = 2^(n-1)
|