(精) 计算机网络笔记：第三章——数据链路层
参考：
https://blog.csdn.net/smart_ferry/article/details/84952341?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task 《王道计算机网络考研复习指导 2021年》由NEU 2018级 软件1809班 整理和补充~
尚未更新完，可持续关注
数据链路层在物理层提供服务的基础上向网络层提供服务，起主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差别的数据链路，使之对网络层表现为一条无差错的链路。
数据链路层的功能：
为网络层提供服务 链路管理 帧定界、帧同步和透明传输 流量控制 差错控制 3.1.1 为网络层提供服务数据链路层可以为网络层提供的服务有：
无确认的无连接服务，适用于实时通信或误码率较低的通信信道，如以太网 有确认的无连接服务，适用于误码率较高的通信信道，如无线通信 有确认的面向连接服务，可靠性最高，适用于通信要求（可靠性、实时性）较高的场合 ！！！有连接就一定要有确认，即不存在无确认的面向连接的服务 3.1.2 链路管理 数据链路层连接的建立、维持和释放过程称为链路管理，它主要用于面向连接的服务。 链路两端的节点要进行通信，必须首先确认对方已处于就绪状态，并交换一些必要的信息以对帧序号初始化，然后才能建立连接，在传输过程中则要能维持连接，而在传输完毕后要释放该链接。 在多个站点共享同一物理信道的情况下（如局域网）如何在要求通信的站点分配和管理信道也属于数据链路层管理的范畴 3.1.3 帧定界、帧同步和透明传输 将一段数据的前后分别添加首部和尾部，就构成了帧。首部和尾部含有很多控制信息，作用：确定帧的界限，即帧定界 帧同步：接收方应能从接收到的二进制比特流中区分帧的开始与终止 透明传输：不管所传数据是什么样的比特组合，都应当能在链路上传送 3.1.4 流量控制 流量控制：限制发送方的数据流量，使其发送速率不致超过接收方的接收能力（由滑动窗口提供反馈机制） 对于数据链路层来说，控制的是相邻两节点之间数据链路上的流量，而对于运输层来说，控制的则是源端到目的端之间的流量 3.1.5 差错控制由于信道噪声等各种原因，帧在传输过程中可能会出现错误。用以使发送方确定接收方是否正确收到由其发送的数据的方法称为差错控制。
数据链路层中传输数据出现的错误分为位错和帧错（一个帧包含多个位）
位错指帧中的某些位出现了差错。 通常采用循环冗余校验（CRC）方式发现位错，通过自动重传请求（ARQ）方式重传出错的帧 帧错指帧的丢失、重复或失序等错误。在数据链路层引入定时器和编号机制，保证每一帧最终都能有且仅有一次正确地交付给目的节点 3.2 组帧数据链路层之所以要把比特组合成帧为单位传输，是为了在出错时只重发出错的帧，而不必重发全部数据，从而
提高效率。
组帧主要解决帧定界、帧同步、透明传输等问题
组帧时既要加首部也要加尾部
组帧通常有4种方法实现
3.2.1 字符计数法在帧头部使用一个计数字段来标明帧内字符数（计数字段提供的字节数包含自身所占用的一个字节）
弊端：如果计数字段出错，即失去了帧边界划分的根据，那么接收方就无法判断所传输帧的结束位和下一帧的开始位，收发双方将失去同步，从而造成灾难性后果
3.2.2 字符填充的首位定界符法 使用特定的字符来定界一帧的开始和结束。为了使信息位中出现的特殊字符不被误判为帧的首尾定界符，可以在特殊字符前面填充一个转义字符来加以区分。 3.2.3 零比特填充的首尾标志法零比特填充法允许数据帧包含任意个数的比特，也允许每个字符的编码包含任意个数的比特。它使用01111110来标志一帧的开始和结束，发送方的数据链路层在信息位中遇到==5个连续的1==时，将自动在其后插入一个0；接收方则执行逆操作。
零比特填充法容易由硬件来实现，性能优于字符填充方法。
即高-高电平对和低-低电平对在数据比特中是违规的
在物理层比特编码时通常采用违规编码法。
违规编码法不需要采用任何填充技术
由于字节计数法中计数字段的脆弱性和字符填充法实现上的复杂性与不兼容性，目前较常用的组帧方法是零比特填充法和违规编码法 3.3 差错控制 比特差错：实际通信链路都不是理想的，比特再传输过程中可能会产生差错，1->0 or 0->1 比特差错是传输差错中的一种 通常利用编码技术进行差错控制，主要有两类：自动重传请求（ARQ）和前向纠错（FEC）。 在ARQ方式中，接收端检测出差错时，就设法通知发送端重发，直到接收到正确的码字为止； 在FEC方式中，接收端不但能发现差错，而且能确定二进制数码的错误位置，从而加以纠正。 因此，差错控制又分为检错编码和纠错编码。 3.3.1 检错编码
检错编码都是采用冗余编码技术。
其核心思想是在有效数据（信息位）被发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使得码字遵从不变的规则。 常见的检错编码有奇偶校验码和循环冗余码奇偶校验码
由n-1位信息元和1位校验元组成，如果是奇校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为奇数；如果是偶校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为偶数循环冗余码
这里文字很难描述，大家凑合康康，
看完了吗？来做道题目吧。
要发送的数据是1101 0110 11，采用CRC校验，生成多项式是10011，那么最终发送的数据应是A . 1101 0110 1110 10 B . 1101 0110 1101 10
C . 1101 0110 1110 10 D . 1111 0011 0111 00 答案是：
最常见的纠错编码是海明码，能发现双比特错误，但只能纠正单笔特错误。
同上,仔细看应该能看懂的
停止–等待流量控制基本原理
发送方一次只能发一个帧，接收方对于接收到的帧必须反馈一个应答信号，发送方收到对上一个帧的应答信号后，才能发送下一个帧，否则发送方将一直等待（后可由重传技术改进）。 效率极低
滑动窗口流量控制基本原理
在任意时刻，发送方都维持一组连续的允许发送的帧的序号，称为发送窗口；同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。
发送窗口中存放的帧序号为当前情况下可以发送的帧以及已经发送了但尚未收到确认的帧，
在接收端只有当数据帧的序号落入接受窗口内才允许将该数据帧收下，
若接收到的数据帧落在接收窗口之外，则一律将其丢弃。
重要特性：
只有接收窗口向前滑动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动 从滑动窗口的概念看，停止--等待协议、后退N帧协议和选择重传协议只在窗口大小与接收窗口大小上有所区别
停止等待协议： 发送窗口大小 = 1 ， 接受窗口大小 = 1
后退N帧协议： 发 > 1 ， 接 = 1
选择重传协议： 发 > 1 , 接 > 1
接受窗口的大小为 1 时， 可保证帧的有序接受
数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的（注意与第 5 章传输层的滑动窗口协议的区别）
可靠传输机制
数据链路层的可靠传输通常使用确认和超时重传两种机制来完成 传统自动重传（Auto Repeat reQuest ，ARQ)请求分为三种：停等-等待（Stop-and-Wait）ARQ、后退N帧（Go-Back-N）ARQ 以及选择性重传（Selective Repeat）ARQ 在数据链路层中流量控制机制和可靠传输机制是交织在一起的。 3.4.2 单帧滑动窗口与停止–等待协议Stop-and-Wait
停止等待协议相当于发送窗口和接收窗口均为 1 的滑动窗口协议 在停止-等待协议中，除数据帧丢失外，还可能出现以下两种差错。 到达目的站的帧可能已经遭到破坏 发送方装备计时器，在一个帧发送之后，发送方 等待确认，如果在计时器超时且未收到确认，那么发送方会再次发送相同的帧。如此重复，直到该数据帧无错误地到达为止。 数据帧正确而确认帧被破坏 设置帧缓存区，出错时进行重传 3.4.3 多帧窗口与后退 N 帧协议 (GBN)GBN 协议：
发送方可以连续发帧，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；
当发送方发送了N个帧后，若发现该N个帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方必须重传该出错帧及随后的N个帧。
也就是说，接收方值允许按顺序接收帧
接收端不一定每收到一个正确的数据帧就必须立即发回一个确认帧，而是可以在连续收到好几个正确的数据帧后，才对最后一个数据帧发确认消息。
也就是说ACKn表示对第n号帧的确认，表示接收方已正确收到了第n号帧及其以前的所有帧，下次期望收到第n+1号帧或者是0号帧
接收端在返回ACKn时，将丢弃那些不按序到达的帧（接受窗口的大小为1）
若采用n个比特对帧编号，则GBN发送窗口的尺寸Wt应满足：1<=Wt<= x2−1x^2-1x2−1
本章疑难点 3.4.4 多帧滑动窗口与选择重传协议(SR)SR 协议
只重传出现差错的数据帧或者是计时器超时的数据帧。加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。
一旦接收方怀疑帧出错，就会发一个否定帧NAK给发送方，要求发送方对NAK中指定的帧进行重传。
若采用n个比特对帧编号，则SR发送窗口的尺寸WTW_TWT和接收窗口的尺寸WRW_RWR一般为： WTW_TWT = WRW_RWR = 2n−12^{n-1}2n−1
补充知识
信道利用率： 发送方从开始发送数据，到收到第一个确认帧为止，称为一个发送周期，记为T。 设发送方在这个周期内共发送了L比特的数据，发送方的数据传输率为C。 则发送方用于发送有效数据的时间为L/C，在这种情况下，信道的利用率为（L/C）/T 信道吞吐率 = 信道利用率 * 发送方的发送速率 3.5 介质访问控制 介质访问控制所要完成的主要任务是为使用介质的每个节点隔离来自同一信道上其他节点所传送的信号，以协调活动节点的传输。 用于决定广播信道中信道分配的协议属于数据链路层的一个子层，称为介质访问控制（MAC）子层 常见的介质访问控制方法有：信道划分介质访问控制、随机访问介质访问控制和轮询访问介质访问控制 其中前者是静态划分信道的方法，而后两者是动态分配信道的方法 3.5.1 信道划分介质 访问控制 信道划分的实质就是通过分时、分频、分码等方法把原来的一条广播信道，逻辑上分为几条用于两个几点之间通信的互不干扰的子信道，把广播信道转变为点对点信道。 频分多路复用（FDM） 每个子信道分配的带宽可不相同，但它们的总和必须不超过信道的总带宽。 实际应用中，为了防止子信道之间的干扰，相邻信道之间需要加入==
保护频带==
优点：充分利用了传输介质的带宽，系统效率较高；由于技术比较成熟，实现也比较容易。
时分多路复用（TDM）
将一条物理信道按时间分成若干时间片，轮流地分配给多个信号使用
统计时分多路复用（STDM，也称异步时分多路复用）：采用STDM帧，STDM帧不是固定分配时隙，而是按需动态地分配时隙，当终端有数据要传送时才会分配到时间片
波分多路复用（WDM）
光的频分多路复用
码分多路复用（CDM）可以观看视频理解：https://www.bilibili.com/video/av70228743?p=27
19：42 处
它们的核心思想是：胜利者通过争用获得信道，从而获得信息的发送权。因此，随机访问控制协议又称为争用型协议 实质：将广播信道转化为点对点信道
ALOHA 协议
纯 ALOHA 协议 当网络中的任何一个站点需要发送数据时，可以不进行任何检测就发送数据。如果在一段时间内没有收到确认，该站点就认为传输过程中发生了冲突。发送站点需要随机等待一段时间后再发送数据，直至发送成功。 网络吞吐量很低，为了克服这一缺点，产生了时隙 ALOHA协议 时隙 ALOHA 协议 时间划分一段段等长的时隙，规定只能在每个时隙开始时才能发送一个帧。避免了用户发送数据的随意性，减少了数据产生冲突的可能性，提高了信道的利用率。 在一个时隙内，有两个或两个以上的帧到达时，在下一个时隙将产生碰撞。
碰撞后重传策略与纯ALOHA协议相似
CSMA（Carrier Sense Multiple Access，载波侦听多路访问） 协议
+ 每个站点在发送前都先侦听一下公用的信道，发现信道空闲后再发送。
+ 与ALOHA协议的主要区别是多了一个载波侦听装置
+ 有三种不同的CSMA协议：
1. 1-坚持 CSMA：
当一个节点要发送数据时，首先侦听信道。
当侦听到信道忙后，继续坚持侦听信道；
当侦听到信道空闲后，发送帧的概率为1，即立即发送数据。
如果发生冲突（或一段时间内未受到肯定回复），则等待一个随机长的时间再监听，重复上述过程
优点：只要信道空闲，站点就马上发送，避免了信道利用率的损失。
缺点：如果有两个或两个以上的站点有数据有发送，冲突就不可避免
传播延迟对1-坚持CSMA协议的性能影响较大。
非坚持 CSMA：
当一个节点要发送数据时，首先侦听信道。
如果信道空闲，就立即发送数据；
如果信道忙就放弃监听。等待一个随机的时间后再重复上述过程
优点：采用随机的重发延迟时间，可以减少冲突发生的可能性
缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，信道使用率降低。
p-坚持 CSMA
用于时分信道。
当一个节点要发送数据时，首先侦听信道。
若信道空闲，便以概率 p 发送数据，以概率 1-p 推迟到下一个时隙。
若信道忙，就持续侦听，直至信道空闲；
优点：既能像1-坚持CSMA协议那样减少冲突，又能客服非坚持CSMA协议中由于随即等待而造成的延迟时间较长的缺点。
缺点：发生冲突后还是要坚持把数据帧发送完，造成浪费
三种不同类型的 CSMA 协议比较如下表所示。| 信道状态 | 1-坚持 | 非坚持 | p-坚持 |
|---|---|---|---|
| 空闲 | 立即发送数据 | 立即发送数据 | 以概率 p 发送数据，以概率1-p推迟到下一个时隙 |
| 忙 | 持续侦听，支持信道空闲 | 放弃侦听，等待一个随机的时间后再侦听 | 持续侦听，支持信道空闲 |
CSMA/CD 协议
CSMA/CA 协议
以下内容这几天慢慢更新
3.5.3 轮询访问介质 访问控制：令牌传递协议 3.6 局域网 3.6.1 局域网的基本概念和体系结构 3.6.2 以太网 与 IEEE 802.3 3.6.3 IEEE 802.11 3.6.4 令牌环网的基本原理 3.7 广域网 3.8 数据链路层设备 3.9 本章小结及疑难点答案是：C
作者：Masics丶
