计算机网络Ch3

第三章 数据链路层

一、数据链路层所处的地位

1.数据链路层使用物理层提供的“比特传输”服务。

2.数据链路层为网络层提供服务，将网络层的IP数据报（分组）封装成帧，传输给下一节点。

3.物理链路：传输介质（第0层）+物理层（第1层）实现了相邻结点之间的“物理链路”

4.逻辑链路：数据链路层需要基于“物理链路”，实现相邻结点之间无差错的“数据链路（逻辑链路）”

二、数据链路层功能

1.组帧（封装成帧）

(1)主要问题

• 帧定界：如何让接收方能够确定帧的界限
• 透明传输：接收方要能够去除“帧定界”的附加信息，把帧“恢复原貌”

(2)组帧方法

字符计数法

• 原理：在每个帧开头，用一个定长计数字段表示帧长
• 帧长=计数字段长度+数据字段长度
• 最大缺点：任何一个计数字段出错，都会导致后续所有帧无法定界

字节填充法

• 头部加上00000001(01H)，表示ASCII中的SOH(Start Of Header)
• 尾部加上00000100(04H)，表示ASCII中的EOT(End Of Transimission)
• 转义字符ESC(Escape Character)：解决在数据中出现SOH和EOT时导致帧定界错误的情况
  

零比特填充法

• 在头部和尾部，添加01111110
• 发送方要对数据部分进行处理，每当遇到连续5个1，就填充一个0
• 接收方要对数据部分进行处理，每当遇到连续5个1，就删除后边紧跟的0

违规编码法

• 曼彻斯特编码（IEEE标准）上跳0下跳1，中间必变
• 如果周期中间没变，则“违规”，来分辨帧的边界

小结

2.差错控制

(1)目标：

• 发现并解决一个帧内部的“位错”

(2)检错编码

接收方发现比特错后丢弃帧，并通知发送方重传帧

奇偶校验码

• 信息位（有效数据）：指帧的“数据部分”
• 加上校验位，使整个校验码1的个数是奇数/偶数
• 偶数用的多，因为便于硬件实现，使用异或（模2加）运算
• 只能检验奇数位错误，无纠错能力

小结

循环冗余校验码(Cyclic Redundancy Check,CRC)

• 数据发送方、接收方约定一个“除数”
• K个信息位+R个校验位作为“被除数”。添加校验位后需保证除法的余数是否为0
• 若不为0则出错
  
• 若信息位+校验位<=2^R-1，那么可以纠1位错，否则不能

小结

(3)纠错编码

接收方发现并纠正比特错误

海明码

• 在偶校验法的基础上改进，对索引各位进行偶校验，同时增加一个全校验位
• 考试不考，有时间再完善

三、流量控制、可靠传输

1.滑动窗口机制

2.停止-等待协议(S-W)

(1)滑动窗口机制

• 发送窗口$W_T=1$
• 接收窗口$W_R=1$

(2)帧编号

• 只需1bit给帧编号
• 要求$W_T+W_R≤2^n$（n是bit位数）

(3)几个概念

• 帧的首尾主要是一些控制信息，如：帧定界信息、校验码、帧类型、帧序号。
• 帧类型：实际应用中，通信一般都是双向的，双方都可能发送数据帧或确认帧。
• 帧序号：标明帧的帧号。
• 数据帧的数据部分通常很短，甚至可以为空。
  

(4)正常情况

• 发送方发送i号数据帧
• 接收方接收到i号数据帧
• 接收方向发送方发送确认帧ACK_i，滑动窗口右移
• 发送方收到确认帧，滑动窗口右移

(5)异常情况

数据帧丢失

• 解决方法：超时重传
• 发送方在在发送后会开启一个计时器，当超时还没收到确认帧时，重新传输

确认帧丢失

• 解决方法
  • 丢弃重复帧
  • 返回重复帧的ACK
• 接收方向发送方发送的确认帧，并且滑动窗口右移
• 接收方没有收到确认帧，向接收方重传
• 接收方丢弃重复帧，并返回重复帧的ACK

为什么给帧编号？

• 若没有编号，则无法辨别重复帧

数据帧有“差错”

• 接收方直接将数据帧丢弃，且不返回ACK
• 发送方超时重传

小结

• 停等协议窗口大小为1，所以没有失序问题

3.后退N帧协议(GBN)

(1)滑动窗口

• 发送窗口大于1，接收窗口等于1

(2)正常情况

• 发送方发送W_T个帧
• 接收方每收到一个数据帧，滑动窗口就向后移一位，接收到最后一个数据帧后向发送方发送一个最后帧确认帧（累计确认）
• 发送方接收到确认帧，窗口向后移动

(3)数据帧丢失

• 若数据帧i丢失，或数据帧i出错被丢弃，则接收方向发送方发送最后一个正确的帧的确认帧，数据帧i以后的帧全部丢弃
• 发送方收到确认帧，滑动窗口向右移动到$i+1(mod W_T)$号帧处，然后超时重传，将i+1号帧后的所有帧全部重传，被重传的帧要重置计时器

(4)确认帧丢失

• 接收方向发送方发送确认帧，确认帧丢失
• 发送方超时重传
• 接收方收到“非法帧”，直接丢弃，返回最后一个正确帧的确认帧
• 发送方收到确认帧，滑动窗口移动

(5)若不满足$W_T+W_R≤2^n$

小结

4.选择重传协议(SR)

(1)窗口大小

• $W_T+W_R≤2^n$
• 接收窗口的大小要小于等于发送窗口大小

  若接收窗口大于发送窗口，则接收窗口多出来的窗口会长期保持空状态（我猜，接收方更需要确保低延迟，所以不允许有空窗口等待发送方窗口移动的情况），通常取相等。

(2)正常情况

• 发送方向接收方发送帧，每个帧一个计时器
• 接收方每收到一个帧，都返回一个正确帧，都返回正确帧后，接收方滑动窗口向后移动
• 发送方接收到所有的正确帧，滑动窗口向后移动

(3)数据帧丢失

• 发送方发送一些数据帧，但有一个数据帧丢失
• 接收方收到部分数据帧，返回收到帧的确认帧，滑动窗口向后移动到没收到的帧序号的位置
• 发送方收到部分确认帧，滑动窗口移动到没有收到确认帧的位置，若窗口末尾有空位，则可以继续发送数据帧
• 发送方超时重传

(4)数据帧差错而被丢弃

• 接收方在收到错误帧后，会向发送方发送一个NCK否认帧
• 发送方收到否认帧后，立即重传，并重置计时器
• 请求重传机制

(5)确认帧丢失

• 确认帧丢失会导致发送方计时器超时，发送方重传
• 与此同时，接收方滑动窗口正常移动
• 接收方收到重传的帧后，帧落在窗口外，重新发送ACK

(6)不满足$W_T+W_R≤2^n$导致的问题

小结

四、三种协议的信道利用率分析

1.停等协议(SW)

• 只考虑发送信道
• 理想状态指没有帧丢失、错误等情况

2.后退N、选择重传协议的信道利用率分析

小结

五、信道划分和介质访问控制

1.时分复用(Time Division Multiplexing)

• 将时间分为等长的“TDM帧”，每个TDM帧又分为等长的m个“时隙”，将m个时隙分配给m对用户（节点）使用

缺点

• 每个节点最多只能分到信道总带宽的1/m
• 如果某节点暂不发送数据，会导致被分配的时隙闲置，信道利用率低

2.统计时分复用(STDM,Statistic)

• 又称异步时分复用，在TDM的基础上，动态按需分配时隙

优点

• 如果需要时，一个节点可以在一段时间内获得所有信道带宽资源
• 如果某节点暂不发送数据，可以不分配时隙，信道利用率更高

3.频分复用(Frequency Division Multiplexing)

• 将信道的总频划分为多个子频带，每个子频带作为一个子信道，没对用户使用一个子信道进行通信
• 不同子频带之间并不相连，有隔离频带
• 优点：各节点可同时发送信号；充分利用了信道带宽（Hz）
• 缺点：FDM技术只能用于模拟信号的传输

4.波分复用

• 光的频分复用
• 不同波长的光频率也不同，C=λf
• 光信号的频带范围（带宽）非常大，因此很适合采用波分复用技术，将一根光纤在逻辑上拆分为多个子信道

5.码分复用(CDM)

(1)给各节点分配专属“码片序列”

• “码片序列”包含m个码片（信号值），可以看作“m维向量”
• 要求：各节点的向量必须正交（内积为0）
• 相互通信的各节点知道彼此的“码片序列”

(2)发送方发送数据

• 发出的向量与码片序列相同表示1，不同表示0

(3)信号在传输过程中“叠加”

• 当多个发送方同时发送数据时，信号值会叠加（本质是向量加法）

(4)接收方接收数据

• 接收方收到的是叠加信号，需要将信号分离
• 方法：叠加信号与码片序列做规格化内积，结果为1表示比特1，为0表示比特0

小结

六、随机访问介质访问控制

1.ALOHA协议和时隙ALOHA协议

• 几个节点共享一个信道
• 纯ALOHA在数据准备完毕后立刻传输
• 时隙ALOHA将时间分为一个个时隙，时隙大小等于传输一个帧需要的时间，每次发送都需要从时隙的开头发送。
• 时隙ALOHA避免了用户发送数据的随意性，降低了冲突概率，提高了信道利用率

2.CSMA协议(Carrier Sense Multiple Access，载波监听多路访问协议)

• 在发送数据之前，先监听信道是否空闲，只有信道空闲时，才会尝试发送

(1)1-坚持CSMA协议

• 坚持：指坚持监听信道
• 优点：信道利用率高，信道一旦空闲，就可以被下一个节点使用
• 缺点：当多个节点都已准备好数据时，一旦信道空闲，就会开始发送，冲突概率大

(2)非坚持CSMA协议

• 非坚持：当信道不空闲时，不坚持监听，而是随机推迟一段时间再监听
• 优点：当多个节点都已准备好数据时，如果信道不空闲，则各节点会随机推迟一段时间并再次尝试监听，从而使各节点错开传输数据，降低了冲突概率
• 缺点：信道刚恢复空闲时，可能不会被立即利用，导致信道利用率降低

(3)p-坚持CSMA协议

• p指的是信道空闲时，节点选择发送数据的概率
• 降低了冲突概率，提升信道利用率

小结

4.CSMA/CD协议(Collision Detection)

• 用于早期的有线以太网（总线型）
• 先听后发，边听边发，冲突停发，随机重发

(1)如何随机重发

• 截断二进制指数退避算法
  • 随机等待一段时间=r倍争用期，其中r是随机数，k是重发次数
  • 当k≤10，在$[0,2^k-1]$随机取一个整数r
  • 当k>10，在$[0,2^10-1]$随机取一个整数r
• 第10次冲突是随机重发的分水岭
• 第16次冲突，直接躺平，放弃传帧，报告网络层

(2)最短帧长限制

• 最短帧长=2*最大单向传播时延*信道带宽。若收到的帧小于最短帧长，视为无效帧
• 最短帧长=争用期长度*数据传输速率
• 同样也有最长帧长限制，防止某些节点一直占用信道
• 以太网规定，最短帧长=64B，最长帧长1518B

小结

七、CSMA/CA协议(Collision Avoidance)

• 适用于无线网络（无线局域网WiFi）
• 发送方：先听后发，忙则退避
• 接收方：停止等待协议

1.AP(Access Point)

• 接入点，也就是你平时连接的无线WiFi热点
• 校园网=路由器+n台交换机+n*m个AP
• 漫游：切换WiFi热点的动作
• 不使用CSMA/CD原因
  • 硬件上很难实现“边听边发，冲突检测”，因为接收信号的强度往往远小于发送信号的强度，且在无线介质上信号强度的动态变化范围很大
  • 存在“隐蔽站”问题，在无线通信中，并非所有站点都能够听见对方。发送节点处没有冲突并不意味着在接收节点处没有冲突。

2.信道预约机制

小结

八、令牌传递协议

1.令牌帧

• 包含令牌号，与主机编号对比来确定哪个主机发送数据
• 若是自己的令牌号但无需传数据，则立即释放此令牌帧并重新生成一个新令牌帧

2.数据帧

• 若是该主机发送数据，主机会把令牌帧转化为数据帧，包括令牌号、源地址、目的地址、数据部分、bool已接收
• 主机收到数据帧后，判断目的地址是否是自己，若不是则传给下一个节点，若是，将数据部分复制一份并把bool已接收设为true
  

小结

八、以太网和IEEE802.3

1.以太网标准（物理层）

• 半双工：同一时刻只能单向传输，可以改变方向
• 全双工：可以双向传输

2.介质访问控制子层（MAC子层）

• 记忆口诀：662N4，收发协数验
• 帧长范围：64B-1518B，因此数据部分长度为46B-1500B
• V2版本的MAC子层就是数据链路层，而IEEE802.3版本的MAC子层上方还有逻辑链路控制子层(LLC)
• 违规编码：曼彻斯特编码为跳0反跳1看中间，中必变，因此中间不变就违规

3.帧的传播

• 冲突域：如果两个节点同时发送数据会导致冲突，则节点组成冲突域
• 广播域：如果一个节点发送广播帧，可被另一个节点接收，则二者处于广播域

小结

九、VLAN基本概念与基本原理

1.大型局域网可能遇到的问题

• 局域网内任何一个结点发出的广播帧，都会被广播至所有节点。可能出现广播风暴
• 不安全，局域网内可能会有一些敏感节点被黑客攻击

2.VLAN（虚拟局域网）

• 可将一个大型局域网分割成若干个较小的VLAN，每个VLAN是一个广播域
• 需要用支持VLAN功能的以太网交换机实现
• 每个VLAN对应一个VID
• 当A发出一个广播帧，则VLAN-10的所有主机都会收到广播帧，而其他VLAN不会

3.VLAN划分方式

(1)基于接口

• 缺点：当一个主机的接口改变，无法改变映射
• 交换机2如何判断1发来的广播帧从属于哪个VLAN？

  主机与交换机之间传输的是标准以太网帧，但交换机与交换机之间传输的是802.1Q帧。这个帧会在标准以太网帧中插入4个字节的数据，包含VID
  

(2)基于MAC地址

(3)基于IP地址

• 注：这种方式可以让VLAN的范围跨越路由器，让多个局域网的主机组成一个VLAN（需要网络层功能支持）

小结

十、无线局域网

1.分类

(1)有固定基础设施无线局域网

• 如802.11无线局域网
• 结点地位不同

(2)无固定基础设施移动自组织网络

• 如AirDrop，华为分享
• 所有结点地位相同

2.802.11无线局域网

(1)一个普通家用路由器的硬件架构

(2)802.11无线局域网的基本概念

• 扩展服务集ESS：将多个AP连接到同一个分配系统，组成一个更到服务集
  • 全屋WiFi
• 漫游：一个移动站从一个基本服务集切换到另一个基本服务集，仍然可以保持通信
  • 丝滑切换WiFi热点

3.802.11帧的分类

4.数据帧格式

小结

十一、广域网

十二、以太网交换机

1.以太网交换机的自学习功能

• 主机之间互相知道对方的MAC地址（后续学习）
• 当主机向另一个主机发送数据时，会先将MAC帧发送给交换机，交换机以（MAC地址，端口号）将发送方的MAC地址放在交换表中，交换机不知道MAC地址（交换表中无对应项），会将MAC帧广播给每一个端口
• 交换表每个表项有一个有效期，有效期过后自动作废

2.交换机的交换方式

(1)直通式交换方式

• 仅接收并处理目的地址，直接将收到的帧转发给对应的端口
• 优点：
  • 转发时延低
• 缺点：
  • 不适用需要速率匹配、协议转换或差错检测的线路

(2)存储转发交换方式

• 接收并处理整个帧（差错控制等）
• 优点：
  • 适用于需要速率匹配、协议转换或差错检测的线路
• 缺点：
  • 转发时延高

小结