[计算机网络]数据链路层
0 概论：数据链路层都干什么事，提供啥功能
比物理层再高一层就是数据链路层，咱们上一篇讲物理层，物理层直接接触传输介质，现在数据链路层是使用物理层的传输服务，然后实现更多的功能。物理层是只管把比特流传到传输介质上，我只管传，我不管传给谁，我也不管我传的时候别人是不是也正在传即是不是有冲突，我物理层就只管传，那么那些事谁来管呢？是你数据链路层。
所谓链路就是一条物理线路，数据链路是物理线路加上规程
提供两个相邻的网络节点或主机及其相连的网络节点之间的可靠通信
- 将不可靠的物理链路变为可靠的逻辑链路
- 流量控制：发送端可能发送过快，导致拥挤和丢失
- 为网络层提供服务：
- 将来自原机器的网络层的数据传送到目标机器的网络层
- >1.无确认无连接的服务
- （适用于误码率低的可靠信道）
- >2.有确认无连接的服务
- >1.无确认无连接的服务
- 将来自原机器的网络层的数据传送到目标机器的网络层
（适用于不可靠信道、无线信道）
>3.有确认面向连接的服务
（长延迟的不可靠信道）
有确认就一定有链接，不存在有连接没确认的
- 链路管理：建立链路、释放链路、介质访问控制
然后接下来咱们就一块一块来讲这些功能都是怎么实现的：
1 组帧:
组帧：从网络层接受数据，并加上有意义的比特位形成头部和尾部来携带地址和其他控制信息。一个含有这些附加控制信息的数据单元称为帧。
帧定界又称帧同步：就是在首尾各加点东西，然后读的时候先读到那个代表开始，然后又读了一次代表结束，使得接收方应该能从接收到的二进制比特流中区分出帧的起始和终止，
有四种方法：
1.1 字符计数
在帧头部加一个字符，就存帧总共的字符个数（当然计数字符自己也算）
1.2 字符填充
首尾各加一个特殊字符，然后信息位中如果发现有控制字符，就在前面加一个转义字符（转义字符本身也算控制字符）
1.3 零比特填充
首位各加一个01111110，然后信息位中每连续遇到5个1就加入一个0（防止有效载荷中出现标志比特）
零比特填充法更容易用硬件来实现，虽然原理跟字符填充法差不多但是性能优于字符填充法
1.4 违规编码
就比如曼彻斯特编码，本来前低后高=0，前高后低=1，没有前高后高或前低后低这种说法，但是我就加入这么一位，让它来代表开始和终止
因为违规，所以特殊
2 差错控制：
数据帧可能出现损坏、丢失、重复、乱序现象
比特差错：0变1了，或者1变0了
ARQ：自动重复请求
FEC：前向纠错
2.1 检错编码：
循环冗余码：
循环冗余校验码
奇偶校验码：
奇偶校验码讲解视频
2.2 纠错编码：
位错：
CRC循环冗余校验码
帧错：帧的丢失，重复或失序
定时器：
帧编号：
3 流量控制&差错控制:
这一块有几个协议，他们之间的关系应该是这样的：滑动窗口协议是一个大的概念，分为：
- 停止等待协议
- 发送窗口=1，接收窗口=1
- 回退n协议(GBN)
- 发送窗口=n,接收窗口=1
- 选择重传协议(SR)
- 发送窗口=n，接收窗口=n
4 介质访问控制(Media Access Control, MAC):
学到这的时候我一开始有个疑问说最直接接触传输介质的不是物理层么，为啥不由物理层来执行介质访问控制？网络分层体系结构的设计者就是这么设计的，这么设计也有一定的合理性，物理层是光管发，我如何发比特流变成各种形式的光信号电信号传到传输介质上，我只管发，至于给谁发、啥时候发、发的时候有没有跟别人产生冲突，我物理层是不管的，是由你数据链路层来管的，所以数据链路层可以说使用物理层提供的发送服务，然后实现了介质访问控、流量控制、差错控制这些更多的功能。
介质访问控制其实就是为了解决冲突，主要有以下这些手段。
有静态和动态之分，这里的静态和动态是怎么说法呢，就是怎么就静态怎么就动态了，就是说像静态这些多路复用，他给每个结点的分配是固定的，公平的，一直就是这个规则不会变，比如时分，咱们就设时间片为5s，你发5s我发5s咱俩轮着来，一直就这么执行。但是动态的话会根据实际情况，可能其他结点都不发就这个结点一直发，也可能多个结点像时分多路复用那样快速轮换，总之每个结点分到的对这个信道的配额会动态的不断变化，不是一成不变的，所以叫动态。
王道的思维导图不错，放这起个总览的作用：
4.1 信道划分介质访问控制（静态介质访问控制）
4.1.1 时分多路复用TDM
数字技术
共享频率，但不共享时间
4.1.2 频分多路复用FDM
模拟技术
共享时间，但不共享频率
4.1.3 波分多路复用WDM
光的频分多路复用
4.1.4 码分多路复用CDMA
4.2 随机介质访问控制（动态介质访问控制）
4.2.1 CSMA载波监听多路访问
CSMA主要有用的特性是监听信道，
在具体讲CSMA这个协议及其CA和CD变种之前，首先得明确两个概念，这两个概念各大教材包括王道都没讲明白，导致理解起来吃力，我自己耗费了很长时间才弄明白，总结在这里：
信道忙闲：
怎么算忙，怎么算闲？咱们说，一个结点监听信道，它只能监听自己这一个点，所以不管有没有结点正在发送，也不管信道上有没有数据在传播，只要这个结点检测到自己这里有来自其他结点的信号经过，那它就认为信道忙，要没有它就认为是空闲。
我初学时在这里陷入很大的误区，主要因为教材讲解的模糊、不明确，导致我以为“只要信道上有数据就叫忙”，“有结点正在发送就叫忙”。后来看了王道的视频（他甚至都没有明说）自己推断了半天才明白。
碰撞：
这里理解的难点是，实际的碰撞和结点检测到碰撞是两回事。
什么叫碰撞了，就是同一时刻，两股数据出现在了信道的同一位置，这就叫碰撞。
那么结点如何去检测到碰撞呢？是必须在它发送的过程中检测到有其他结点的信号到了自己这，它才能检测到发生了碰撞。
同样是由于教材和课程的不明确，我初学时在这里也有误区，以为碰撞检测是依赖争用期，只要从开始发时计时，经过争用期没有检测到其他信号就叫没有发生碰撞。
4.2.2 CSMA/CD
一般的CSMA是发送前监听信道，监听到闲了就发送，然后就不再监听了。
CD则是发送时还监听，就为了监听冲突/碰撞。
总体算法可以陈述如下：
忙怎么办？
忙继续监听，和1坚持一样
争用期和最小帧长：
看图3.22的倒数第二行，设想极端情况，当A发送的数据就差一点点到达B时，B突然发了一个bit。
根据上面说忙闲和碰撞的定义，A开始发送数据后需要经过的时间，A发的数据能到达每个结点，使每个结点监听信道时都能监听到A的信号，从而不会发送。但是假如说，就在差0.00001秒到
时离A最远的B突然发了一个bit，那么这是发生碰撞的最极端情况了，这个bit要到达A还需要
的时间。所以争用期=2
，只要过了争用期A还没检测到其他结点的信号到自己这，A就能确定肯定没发生碰撞。
最小帧长就是说，根据检测碰撞的定义，一个结点必须在自己发送数据时同时检测到有其他结点的信号到自己这，它才能知道碰撞了，还是考虑上面那种极端情况，如果说，那来自B的一个bit到A时，A的数据早发完了，那么A就检测不到碰撞了。这属于是实际发生了碰撞但A检测不到。所以为了确保任何碰撞都能被检测到，就限制最小帧长为：争用期*带宽.
检测到碰了怎么办？
二进制指数回避算法，
确定基本退避时间=争用期
确定参数K=min[重传次数，10]
确定倍数r,r从[0,1,2,3,---2^k-1]中随便取一个
退避时间为：基本退避时间*r
重传次数最高为16次，如果超过16次，向上层报错
4.2.3 CSMA/CA
王道计算机考研 计算机网络
CSMA/CA协议主要用在无线局域网中，那么
为什么不用CD?
1.因为无线网络中发送信号远强于接收信号(信号随距离减弱），且信号不稳定。假如我是结点A，我自己发送的信号很强，而别的结点的发送信号到我这里已经很弱了，那么我自己的发送信号干扰了别的结点的发送信号，我可能就听不到别的结点也在发送了。
2.隐蔽站问题：
所谓隐蔽站，就是说无线信号的传播有距离限制，比如就10m，那么我距离接入点8m，你距离接入点7m，咱俩相距15m，那么监听不监听都没用，因为反正咱俩听不到彼此，咱俩就有可能同时发送造成冲突。
CA和CD相比区别就是不去检测碰撞而尽量去避免碰撞，所采取的手段就是DIFS、随机退避和信道预约。
CD是监听，闲则立即发，忙则继续监听，CA是闲则等待DIFS然后发RTS，忙则随机退避，CA只要发了就不再去检测冲突。
这部分主要是CSMA/CD会考一些计算题比较难，需要把最小帧长的计算掌握清楚，别的就都是考概念
然后这块经常会各种MAC协议的优缺点，什么情况下适合选哪种，统一总结一下就是说：
高负载时，无碰撞协议好，
低负载时，碰撞协议好。因为低负载的时候往往无碰撞协议的信道利用率就低了。
4.2.4 令牌环网：
令牌环网，物理星型，逻辑环形
令牌包含：
标记位
发送方信息
接收方信息
数据
过程：
每个节点拿到令牌后有一段固定的令牌持有时间，这段时间可以给令牌里装数据，同时置标记位为忙
装完以后把令牌在环网里转一圈回到手里，置标记位为闲
然后顺着环网给下一个人
优缺点：
1.令牌开销
2.延迟，如果A想发，但令牌在D手里，那要等D->C->B->A