王道考研 计算机网络笔记 第三章：数据链路层
本文基于
2019 王道考研 计算机网络: 2019 王道考研 计算机网络
个人笔记总结
第一章：王道考研 计算机网络笔记 第一章：概述&计算机网络体系结构
第二章：王道考研 计算机网络笔记 第二章：物理层
后续章节将陆续更新…
第三章
- 一、数据链路层基本概念
- 二、链路层的功能
- 1. 封装成帧
- 2. 透明传输
- 1. 字符计数法
- 2. 字符填充法
- 3. 零比特填充法
- 4. 违规编码法
- 3. 差错控制
- 1. 差错的由来
- 2. 数据链路层差错控制
- 3. 检错编码
- 奇偶校验码
- 循环冗余码
- 4. 纠错编码
- 4. 流量控制与可靠传输机制
- 概述
- 1. 流量控制的几种方法
- 2. 协议所属层次
- 3. 可靠传输、滑动窗口、流量控制的区别
- 1. 停止等待协议
- 出现原因
- 前提
- 应用情况
- 性能分析
- 2. 后退N帧协议(GBN)
- GBN中的滑动窗口
- GBN发送方必须响应的三件事
- GBN接收方要做的事
- 运行中的GBN
- GBN滑动窗口的长度
- 性能分析
- 总结
- 3. 选择重传协议(SR)
- SR中的滑动窗口
- SR发送方必须响应的三件事
- SR接收方要做的事
- 运行中的SR
- SR滑动窗口长度
- 总结
- 三、介质访问控制
- 1. 引入
- 2. 信道划分介质访问控制
- 频分复用`FDM`
- 时分复用`TDM`
- 波分多路复用`WDM`
- 码分多路复用`CDM`
- 3. 随机访问介质访问控制
- ALOHA协议
- 1. 纯ALOHA协议
- 2. 时隙ALOHA协议
- 3. 总结
- CSMA协议
- 1-坚持CSMA
- 非坚持CSMA
- p-坚持CSMA
- 总结
- CSMA-CD协议
- 1. CS MA CD概念
- 2. 传播时延对载波监听的影响
- 3. 二进制数规避算法
- 4. 最小帧长问题
- CSMA-CA协议
- 1. 为什么要有？
- 2. 工作原理
- 3. 对比CSMA/CD
- 4. 轮询访问介质访问控制
- 轮询协议
- 令牌传递协议
- 5. 总结
- 四、局域网
- 1. 基本概述
- 1. 定义及特点
- 2. 局域网拓扑结构
- 3. 局域网传输介质
- 4. 局域网介质访问控制
- 5. 局域网的分类
- 6. IEEE 802标准
- 7. MAC子层和LLC子层
- 2. 以太网
- 1. 概述
- 2. 无连接、不可靠服务
- 3. 以太网传输介质与拓扑结构发展
- 4. 10BASE-T以太网
- 5. 适配器和MAC地址
- 6. 以太网MAC帧
- 7. 高速以太网
- 3. 无线局域网
- 1. 概述
- 2. 802.11的MAC帧格式
- 3. 无线局域网的分类
- 五、广域网
- 1. 简介
- 2. PPP协议
- 1. 简介
- 2. 应满足的要求
- 3. 无需满足的要求
- 4. 三个组成部分
- 5. PPP协议状态图
- 6. PPP协议的帧格式
- 3. HDLC协议
- 1. 简介
- 2. HDLC的站
- 3. HDLC帧格式
- 4. PPP对比HDLC
- 六、链路层的设备
- 1. 集线器（Hub）
- 2. 网桥&交换机（Bridge）
- 3. 以太网交换机
- 4. 广播域&冲突域&总结
第三章大纲：
研究思想：
- 实际传输过程中，数据从信源A开始自上而下不断封装，最后转换成比特流的形式在链路上进行传输，到了中间系统首先自下而上解封装，然后再自上而下进行封装，再在链路上进行传输，最后传输到信宿的时候，自下而上解封装，还原出原始的数据，送给B
- 专门研究数据链路层的功能时，我们一般只关心协议栈当中水平方向的各个数据链路层；可以想象为A给B发信息的时候，数据是从A的数据链路层自左向右水平方向发送，如上图中箭头所示
一、数据链路层基本概念
数据链路层负责通过一条
链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。
结点：主机、路由器
链路：网络中两个结点之间的物理通道
链路的传输介质主要有双绞线、光纤和微波
分为有线链路、无线链路
数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路
帧：链路层的协议数据单元，封装网络层数据报
二、链路层的功能
数据链路层在物理层提供服务的基础上向网络层提供服务
- 其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层
- 其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接
改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
五大功能：
1. 封装成帧
封装成帧的过程就是将网络层的IP数据报加头加尾，形成链路层的数据传送单元帧，IP数据报也就成了帧的数据部分
概念：将一段数据的前后部分添加首部和尾部，构成一个帧；接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。
- 首部和尾部的标记，就是首部尾部添加的一个字节，这个字节叫做
帧定界符，接收端可据此确定帧开始和结束的位置 - 首部和尾部包含许多的控制信息，其中的帧定界符才实现
帧定界的作用；还有其他关于差错控制、流量控制、物理地址等信息
帧同步：接收方从接收到的二进制比特流中区分出帧的起始和终止
组帧就是在发送端封装成帧的过程，帧同步是在接受端识别帧开始和结束的过程
数据链路层的帧长：帧从帧首部到尾部包括中间数据部分的总长度
- 因此为了提高帧的传输效率，应该使帧的数据部分尽可能的大于帧的首部和尾部
- 但是由于链路层的协议，要规定所能传送的帧的最大数据部分上限
- 数据部分的极限值就叫做
最大传送单元MTU，不同协议MTU的值也不同
组帧有四种方法：
- 字符计数法
- 字符（节）填充法
- 零比特填充法
- 违规编码法
2. 透明传输
透明传输是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。
当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使接收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的
透明传输在组帧上的应用
1. 字符计数法
如果计数字段发生错误，比如从5到4，则第一个帧的结束位发生错误，导致后面所有的帧都发生错误，导致接受方无法正确的接收每一个帧，接受双方失去了同步
2. 字符填充法
就是加头SOH加尾EOT(均为一个字节)标记帧的开始与结束，根据不同的协议，SOH和EOT对应的比特组合不同
- 当传送的帧都使由文本文件组成时，都是ASCII，与一个字节的
SOH和EOT不会有交集，因此不会与这连个标记重复，可以实现透明传输 - 但当传送的帧由非ASCII码组成时，有可能出现数据内某段比特流数据正好与标记字段重复，从而导致误判断的情况，因此要采用
字符填充法
字符填充法：在数据部分与标记字段重复的字段前加转义字符，告诉接受端不用管我后面的字段是什么，正常接收即可，直到遇到真正的开始/结束标志
3. 零比特填充法
首部和尾部的标志相同，均是01111110
如果发送端发送一系列一连串的比特时，数据部分也出现了与标志相同的比特组合01111110，那么怎么实现透明传输呢？这就是零比特填充法要解决的问题
4. 违规编码法
因为曼彻斯特编码不使用高-高，低-低来表示数据信息，所以如果使用高-高，低-低来表示帧起始和终止就不会与数据冲突
3. 差错控制
1. 差错的由来
回顾：
为什么要在数据链路层进行差错控制？
因为错误可以尽早发现，不会让一个错误的数据包发送了很长时间到达最终目的地之后才被发现，从而导致网络资源的浪费
2. 数据链路层差错控制
数据链路层的差错控制主要强调的是比特错
针对比特错的控制方法由两种：
检错编码：奇偶校验码，循环冗余码纠错编码：海明码
注意：数据链路层编码和物理层的数据编码与调制不同。
- 物理层编码针对的是单个比特，解决传输过程中比特的同步等问题，如曼彻斯特编码。
- 而数据链路层的编码针对的是一组比特，它通过
冗余码的技术实现一组二进制比特串在传输过程是否出现了差错
冗余码：例如下图盒子上的6本信息就是冗余码，可据此判断是否出错
3. 检错编码
奇偶校验码
循环冗余码
4. 纠错编码
1、确定校验位数r
2、确定校验码和数据的位置
3、求出校验码的值
4、检错并纠错
4. 流量控制与可靠传输机制
概述
较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。
传输层也有流量控制，区别：
数据链路层的流量控制是
点对点的，而传输层的流量控制是端到端的。数据链路层流量控制手段：接收方收不下就不回复确认
传输层流量控制手段：接受端给发送端一个窗口公告（有多少窗口，缓冲区多大）
1. 流量控制的几种方法
2. 协议所属层次
停止等待协议、滑动窗口协议到底属于哪一层？
早些时候，链路的质量还没有那么可靠的时候，就需要数据链路层负责起可靠传输的功能，就会用到停止等待协议、后退N帧协议、选择重传协议等；随着链路质量的不断发展，链路的通信已经非常的可靠，这个时候就不需要数据链路层担负可靠传输的任务了，交给传输层来实现，链路层就主要负责流量控制
不管停止等待协议、滑动窗口协议是在数据链路层还是传输层，其功能都是进行可靠传输，只不过数据链路层的传输对象是帧，传输层的传输 对象是分组
3. 可靠传输、滑动窗口、流量控制的区别
1. 停止等待协议
出现原因
为什么要有
停止-等待协议?
因为在链路上除了比特出差错外，底层的信道还会出现丢包问题
丢包：物理线路故障，设备故障，病毒攻击，路由信息错误等原因，会导致数据包的丢失
这里的数据包就是一个数据，在不同层次有不同的名字；在链路层是帧，在网络层是数据报/分
组，在传输层是报文段
为了解决丢包问题并且实现流量控制，就需要有停止等待协议
前提
研究
停止等待协议的前提？
- 虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据（接收方）.
- 因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。
- “停止等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
应用情况
1、无差错情况
2、有差错情况
性能分析
通过上述几种情况，我们使用确认和超时重传的机制，实现了在不可靠的网络上面实现相对比较可靠的通信，但是停止等待协议也有其优缺点：
优点：简单
缺点：信道利用率低
TD：发送方发送一个数据帧的发送时延RTT：往返时延TA：确认帧的发送时延
停等协议发送方每发送一个帧就处于等待状态，等到接收方回复一个确认帧，发送方才会发送新的帧；因此停等协议大部分时间都是在等待，真正发送数据的时间很少，极大的浪费了资源；
为了解决停止等待协议太闲的问题，可以采用流水线技术，一次发送多个帧；但同时在其他方面急性改进：
- 必须增加序号范围，一次传送多个帧，要编序号
- 发送方需要缓存多个分组，为帧丢失重传备用
针对这种解决方案，就推出了下文的GBN和SR协议
2. 后退N帧协议(GBN)
GBN中的滑动窗口
注意：GAN协议中发送窗口有多个，接收窗口只有一个
- 停等协议中发送窗口和接收窗口都是一个
- SR协议中发送窗口有多个，接收窗口也可有多个
GBN发送方必须响应的三件事
例如：比如发送方发了0号帧给接收方，接收方返回一个0号确认帧；然后发送方发送1号帧，但是途中丢失，接收方接收不到1号帧，就一直等1号帧；接收方没有等到1号帧，等到了2号帧的到来，此时接收方会丢弃2号帧，后续来的3、4号帧也会相应丢弃，接收方会一直等待1号帧的到来；发送方也在一直等待着1号帧的确认到来，就造成了一种死锁的状态；因此发送方的超时计时器就来解决这个问题，如果超时，就会重传1号帧以及后续所有发送的但是没有被确认的帧
GBN接收方要做的事
运行中的GBN
GBN滑动窗口的长度
性能分析
- 因连续发送数据帧而提高了信道利用率
- 在重传时必须把原来已经正确传送的数据帧重传，使传送效率低
总结
累积确认（偶尔稍带确认：接收方同时也可以发送数据给发送方，相当于角色互换了，就可以将确认帧夹在数据里发给发送方）- 接收方只按顺序接收帧，不按序则丢弃
- 确认序列号最大的，按序到达的帧 （比如发送了1、2号帧并已确认，此时发送方发送了4号帧，发送方会丢弃，会返回ACK2催更，催发送方发3号帧并且对2号帧的确认）
- 发送窗口最大为2^n-1，接收窗口大小为1
3. 选择重传协议(SR)
SR中的滑动窗口
- SR协议中发送窗口有多个，接收窗口也可有多个
SR发送方必须响应的三件事
SR接收方要做的事
运行中的SR
SR滑动窗口长度
总结
- 对数据帧逐一确认，收一个确认一个
- 只重传错帧
- 接收方有缓存
- 最大的发送窗口=最大的接收窗口=2^(n-1)
三、介质访问控制
1. 引入
传输数据使用的两种链路
在广播信道当中，同一时间只能有一台主机发送信息，如果有多个节点同时发送信息，信道上就会发生信号冲突问题，通信就会失败，需要重传；因此需要对多节点共享的介质进行访问控制
介质访问控制分为两种：
- 静态划分信道：在用户通信之前，预先将信道按照时间(时隙)/空间(频率)对信道进行划分，使用户在通信过程中不会发生碰撞，不会相互干扰
- 动态分配信道：又叫做动态媒体接入控制/多点接入，信道并不是在用户通信时固定分配给用户，使得用户占用的带宽更大
2. 信道划分介质访问控制
也就是静态划分信道
频分复用FDM
时分复用TDM
改进的时分复用——统计时分复用STDM
集中器：将四个低速用户连接起来，将它们的数据集中起来，通过高速线路在一条信道上发送出去
波分多路复用WDM
码分多路复用CDM
3. 随机访问介质访问控制
动态划分信道的一种
ALOHA协议
ALOHA协议分为两种：
1. 纯ALOHA协议
2. 时隙ALOHA协议
相对于纯ALOHA协议就是固定了发送时间和重传时间（只能在一个时间片的开始），提高了效率
3. 总结
- 纯ALOHA比时隙ALOHA协议吞吐量更低，效率更低（吞吐量就是一段时间内成功发送的平均帧数）
- 纯ALOHA想发就发，时隙ALOHA只有在时间片段开始时才能发
CSMA协议
1-坚持CSMA
非坚持CSMA
p-坚持CSMA
总结
对于以上三种CSMA，它们的冲突检测方案只能在发送完整段数据帧之后，是否收到来自接收方的确认帧来判断是否发生冲突，如果没有收到来自接收方的确认帧，发送方就会判定发生冲突，因此之前发送的数据帧完全浪费
CSMA-CD协议
1. CS MA CD概念
2. 传播时延对载波监听的影响
3. 二进制数规避算法
如何确定碰撞重传的时间？
例题：
4. 最小帧长问题
- 如果发送了一个很小的帧发生了碰撞，但是由于帧太短，帧发送完毕之后才检测到发生了碰撞，已经没有办法停止发送；
- 而CSMA/CD的诞生就是为了能够及时叫停，解决只有帧发完之后才能检测到碰撞的问题，因此定义了一个
最小帧长，希望在检测到碰撞的时候，帧还没发送结束 - 上述我们得到，最迟经过2个传播时延，检测到碰撞，因此要求帧的传输时延>=2倍信号在总线中的传播时延，就可以保证检测到碰撞时帧还没有发送完，便可以叫停
CSMA-CA协议
1. 为什么要有？
CSMA-CD协议已经很全能，为什么还要有CSMA-CA协议？
答：应用场景不同
- CA使用于无线局域网当中，很难用CD实现，因为空间大，冲突检测范围大，很难实验
- CD常应用于总线式以太网当中，是一种有线网络的情况
2. 工作原理
3. 对比CSMA/CD
4. 轮询访问介质访问控制
动态划分信道的一种
轮询协议
缺点：
- 询问的过程就是发送一个较短的数据帧，如果从属节点较多，就会多次轮询，产生较大的开销
- 对于靠后的主机，会有等待延迟，等待前面的主机轮询结束
- 单点故障，如果主结点宕机，则从属节点都通信不了（实际会有备用主结点）
优点：
- 不会发生冲突，每次只能允许一台主机发送数据，该主机占用全部带宽
令牌传递协议
5. 总结
四、局域网
1. 基本概述
1. 定义及特点
2. 局域网拓扑结构
3. 局域网传输介质
4. 局域网介质访问控制
5. 局域网的分类
6. IEEE 802标准
IEEE 802系列标准是IEE802 LAN/MAN标准委员会制定的局域网、城域网技术标准（1980年2月成立）其中最广泛使用的有以太网、令牌环、无线局域网等。这一系列标准中的每一个子标准都由委员会中的一个专门工作组负责。
7. MAC子层和LLC子层
2. 以太网
以太网是使用最广泛的局域网
1. 概述
2. 无连接、不可靠服务
以太网提供无连接、不可靠服务
无连接：发送方和接收方之间无“握手过程”.不可靠：不对发送方的数据帧编号，接收方不向发送方进行确认，差错帧直接丢弃，差错纠正由高层负责- 以太网只实现无差错接收，不实现可靠传输。
3. 以太网传输介质与拓扑结构发展
4. 10BASE-T以太网
5. 适配器和MAC地址
6. 以太网MAC帧
7. 高速以太网
3. 无线局域网
无线局域网也是一种常见的局域网
1. 概述
IEE802.11是无线局域网通用的标准，它是由
IEEE所定义的无线网络通信的标准。
和WIFI的区别?
- 无线局域网的覆盖范围比WIFI的覆盖范围大得多
- WIFI是802.11b和802.11g所定义的标准，满足这两个标准属于WIFI
2. 802.11的MAC帧格式
比如主机A要给主机B发送信息，首先发送到基站AP1，基站AP1发送到AP2，AP2再发送给主机B，这里的几个地址含义就是：
- RA：接收主机旁基站的MAC地址
- TA：发送主机旁基站的MAC地址
- DA：接收主机的MAC地址
- SA：发送主机的MAC地址
上图只是802.11的MAC帧的一种类型WDS，四种地址都有，实际情况中，帧被分为4类：
其余三种帧类型只有三个地址，不同帧类型对应的地址字段不同
To AP：表示发往基站AP的帧
- Address1：BSSID是AP基站的MAC地址
- Address2：SA就是发送端的MAC地址
- Address3：DA就是目的MAC地址
From AP：由基站AP发来的帧
- Address1：DA就是目的MAC地址
- Address2：BSSID是AP基站的MAC地址
- Address3：SA就是发送端的MAC地址
IBSS
- Address1：DA就是目的MAC地址
- Address2：SA就是发送端的MAC地址
- Address3：BSSID是AP基站的MAC地址
3. 无线局域网的分类
有固定基础设施无线局域网
无固定基础设施无线局域网的自组织网络
五、广域网
1. 简介
节点交换机是链路层的设备，是交换机，和网络层的路由器功能类似，均用来转发分组，但是节点交换机只能在单个网络中转发分组，而路由器可以在多个网络之间转发分组
广域网只有节点交换机吗？
- 不是，广域网可以由交换机，集线器，还可以有网络层的路由器
广域网和局域网的区别：
- 广域网覆盖的网络体系结构层次从物理层、链路层到网络层；而局域网支付该物理层和链路层两个层次
- 局域网多采用逻辑上总线结构的多点接入技术，而广域网通常采用点对点相互连接的全双工或者半双工的通信模式
- 广域网强调资源共享，局域网强调数据传输
- 广域网的传输速率比局域网高，但是传播延迟更长
2. PPP协议
PPP和HDLC是最常用的广域网当中的链路层协议
1. 简介
点对点协议PPP（ Point-to- Point protocol）是目前使用最广泛的数据链路层协议，用户使用拨号电话接入因特网时一般都使用PPP协议。
特点：只支持全双工链路
2. 应满足的要求
简单：不需要实现可靠传输的功能， 对于链路层的帧，无需纠错，无需序号，无需流量控制封装成帧：在帧头帧尾加帧定界符透明传输：不管在数据部分传送什么样的比特流，都可以完整的传送过去，即使其中有定界符，也视而不见；也就是与帧定界符一样比特组合的数据应该如何处理：异步线路用字节填充，同步线路用比特填充多种网络层协议：链路层是对网络层数据报的封装，不要求网络层使用的协议，封装的数据报可以采用多种协议。多种类型链路：串行/并行，同步/异步，电/光差错检测：采用CRC循环冗余，通过在帧当中添加FCS字段，实现差错检测，错就丢弃。检测连接状态：检测链路是否正常工作。最大传送单元：PPP协议中数据部分就是上层交付的IP数据报，要求最大长度MTU，默认不超过1500字节网络层地址协商：PPP协议要使得通信双方知道对方的网络层地址数据压缩协商：发送数据的时候对数据进行压缩
3. 无需满足的要求
- 不需要纠错，只需要检错
- 不需要流量控制，交给上层负责
- 无需对帧编序号
- 不支持多点线路，只需要满足点对点之间的连接过程
4. 三个组成部分
5. PPP协议状态图
6. PPP协议的帧格式
帧格式以字节为单位，传输的数据都是整数个字节，因此PPP协议面向字节
3. HDLC协议
1. 简介
高级数据链路控制(High-Level Data Link Contro或简称
HDLC)，是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织(ISO)根据IBM公司的SDLC(Synchronous Data Link Control)协议扩展开发而成的
特点：
数据报文可透明传输，通过“0比特插入法”（5个1插入一个0）实现
PPP还可以实现字节填充，HDLC只能实现0比特填充法
采用全双工通信
所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重份，传输可靠性高。
2. HDLC的站
3. HDLC帧格式
4. PPP对比HDLC
六、链路层的设备
1. 集线器（Hub）
物理层通过集线器拓展以太网的两种方法：
方式一：通过光纤
- 光纤长度长，信号损耗小，
- 调制器：电信号-》光信号
- 解调器：光信号-》电信号
方式二：通过主干集线器
- 一个冲突域内主机变多，发生冲突概率变大，效率变低
2. 网桥&交换机（Bridge）
为了解决主干集线器方式的冲突大、效率低问题，出现了网桥(交换机的前身)&交换机
两种网桥：
- 通过自学习来构建转发表。每一个通过网桥的数据包都会被记录下网桥收到数据时数据对应的地址和网桥自己的接口，通过许许多多的数据包的构造的缓存，网桥就可以知道哪个数据包在哪个接口，以后如果要穿数据包就知道要往哪个接口发送数据包了
- 在发送时，直接将最佳路径放到帧首部。那么网桥如何获得最佳路径？通过广播方式想目标地址发送广播，此时可能会经过不同路由产生不同的路径，目标地址收到后再将每一条路径都发一个响应帧给网桥，网桥经过对比就知道哪个接口最快了
3. 以太网交换机
随着技术发展，网桥的接口越来越多，网桥就变成了以太网交换机
交换机通常有十几个端口，每个端口都可以直接连接主机或者连接集线器
交换机同网桥一样，每个端口引出的区域都是一个冲突域
交换机可以独占传输媒体带宽，交换机端口连接的集线器/主机都是独占媒体带宽，不同于集线器带宽被平分
以太网交换机的两种交换方式：
4. 广播域&冲突域&总结