数据链路层

数据链路层概述

主要任务

在物理层提供服务的基础上向网络层提供服务
加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路

为网络层提供服务

无确认的无连接服务：
- 源主机发送帧不需要先建立链路链接，目的主机收到帧时不需要发回确认
- 数据传输的可靠性由高层负责
- 适用于实时通信或误码率较低的通信信道 —— 以太网
有确认的无连接服务：
- 源主机不需建立，目的主机必须发回确认
- 源主机在规定时间未收到确定信号，就重传丢失帧
- 适用于误码率较高的通信信道 —— 无线通信
有确认的有连接服务：
- 三个阶段：建立链路、传输帧、释放链路
- 目的主机对收到的每一个帧都要返回确认
- 适用于对可靠性，实时性要求较高的场合

信道分类

点对点信道：
- 一对一
- PPP 协议
广播信道：
- 一对多
- 有限局域网使用 CSMA/CD 协议
- 无线局域网使用 CSMA/CA 协议

三个重要问题

封装成帧和透明传输：
- 数据链路层给上层交付下来的协议数据单元 PDU 添加帧首部和帧尾部，这称为封装成帧
- 如果能够采取措施，使得数据链路层对上层交付的 PDU 的内容没有任何限制，就好像数据链路层不存在一样，就称其为透明传输
差错检测：
- 帧在传输的过程中可能出现误码
- 接收方根据发送方添加在帧尾部中的检错码，可以检测出帧是否出现了误码
可靠传输：
- 不可靠传输服务：收到有误码的帧，直接丢弃，其他什么也不做；未收到发送方发送的帧，也不进行任何处理
- 可靠传输服务：实现发送方发送什么，接收方最终都能正确收到

封装成帧和透明传输

封装成帧（组帧）

指数据链路层给上层交付下来的协议数据单元 PDU添加帧首部和帧尾部
组帧主要解决：帧定界、帧同步、透明传输等问题
- 帧头和帧尾中包含有重要的控制信息
- 帧头和帧尾的作用之一就是帧定界
注意：
1. 在网络中信息是以帧为最小单位进行传输的，接收端要正确地接收帧，必须要清楚该帧在一串比特流中从哪里开始到哪里结束
2. 分组（即 IP 数据报）是包含在帧中的数据部分，不需要加尾部来定界
3. 为了提高帧的传输效率，应当使帧的数据载荷的长度尽可能地大于首部和尾部的长度
4. 并不是每一种数据链路层协议的帧都包含帧定界标志【以太网 V2 的 MAC 帧】
最大传送单元（MTU）：
- 每一种数据链路层协议都规定了帧的数据载荷的长度上限
- 以太网的 MTU 为 1500 个字节
组帧方法：较常用的是零比特填充法和违规编程法

字符计数法

在帧首部使用一个计数字段来记录该帧所含的字节数【包括计数字段所占用的 1 个字节】
缺点：如果计数字段出错，就失去了帧定界划分的依据

字节填充法

使用特定字节来定界一帧的开始与结束
- SOH 表示帧的首部开始
- EOT 表示帧的结束
在特殊字符前面填充一个转义字符 ESC 来区分
接收方收到数据会删除 ESC 然后得到原来的数据

零比特填充法

允许数据帧包含任意个数的比特，使用 01111110 标志一帧的开始和结束
在数据中如果出现连续的 5 个 1，就插入一个 0
早期使用的 HDLC 协议采用这种方法
很容易用硬件实现，性能优于字符填充法

违规编程法

在物理层进行比特编码时，通常采用违规编码法
局域网 IEEE 802 标注采用这种方法
不采用任何填充技术便能实现数据的透明传输
只适合于采用冗余编码的特殊编码环境

透明传输

数据链路层对上层交付下来的协议数据单元 PDU 没有任何限制，就好像数据链路层不存在一样【保证接收方接到的数据是完整的数据】
面向字节的物理链路使用字节填充的方法
面向比特的物理链路使用比特填充的方法

差错检测

误码的相关概念

比特差错：实际的通信链路都不是理想的，比特在传输过程中可能会产生差错
- 比特 1 可能变成比特 0
- 比特 0 可能变成比特 1
误码率 BER：在一段时间内，传输错误的比特占所传输比特总数的比率
提高链路的信噪比，可以降低误码率
使用差错检测码(如 Mac 帧尾的 FCS) 来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一
检测分类：
- 检错码：只能检测错误，不能纠正错误
- 纠错码：可以纠正错误，但是开销大

检错编码

检错编码都采用冗余编码技术，常用的检错编码有奇偶奇偶校验码和循环冗余校验码

奇偶检验码

奇校验：是在待发送的数据后面添加 1 个校验位，使得添加该校验位后的整个数据中比特 1 的个数为奇数
偶校验：是在待发送的数据后面添加 1 个校验位，使得添加该校验位后的整个数据中比特 1 的个数为偶数

注意：
- 如果有奇数个位发生误码，则奇偶性发生变化，可以检查出误码
- 如果有偶数个位发生误码，则奇偶性不发生变化，不能检查出误码 (漏检)

循环冗余码 CRC

基本思想：
- 收发双方约定好一个生成多项式 G(x)
- 发送方基于待发送的数据和 G(x)，计算出冗余码【帧检测序列 FCS】，将其添加到待传输数据的后面一起传输
- 接收方通过生成多项式 G(x)，计算收到的数据和冗余码是否产生了误码
发送方的 FCS 生成和接收方的 CRC 检验都是由硬件实现
CRC 有很好的检错能力，漏检率非常低
CRC 具有纠错功能，只是数据链路层仅使用了检错功能，检测到帧出错则直接丢弃
除法内的相减实际是做异或运算

纠错编码（海明码）

实现原理：在有效信息位中加入几个校验码组成海明码，把海明码的每个二进制位分配到几个奇偶校验组中，当某一位出错后，就会引起有关的几个校验位的值发生变化
该方法不但可以发现错位，还能指出错位的位置
海明码可以纠正一位差错
纠错 d 位，需要码距 2d+1 的编码
检错 d 位，需要码距 d+1 的编码

流量控制与可靠传输机制

流量控制与滑动窗口机制

流量控制：由接收方控制发送发的发送速率，使接收方有足够的缓冲空间来接收每个帧
数据链路层控制的是相邻结点之间的流量，而传输层控制的是端到端的流量
数据链路层的控制手段是接收方收不下就不返回确认，传输层的控制手段是接收方通过确认报文段中的窗口值来调整发送方的窗口值

停止 - 等待流量控制基本原理

发送方每次只允许发送一个帧
接收方每接收一个帧都要反馈一个应答信号，表示可以接收下一帧
发送方收到应答信号后才能发送下一帧
若发送方没有收到接收方反馈的应答信号，则需要一直等待
发送方每发送完一个帧，就进入等待接收方确认信息的过程中，因而传输效率很低

滑动窗口流量控制基本原理

发送窗口 $W_{T}$ ：
- 发送方维持一组连续的允许发送帧的序号
- 表示在还未收到确认信息的情况下，发送方最多还能发送多少个帧和哪些帧
- $W_{T} = 1$ ：发送方每收到一个按序确认的确认帧，就将发送窗口向前滑动一个位置
接收窗口 $W_{R}$ ：
- 接收方维持一组连续的允许接收帧的序号
- 控制可以接收哪些帧和不可以接收哪些帧
- $W_{R} = 1$ ：接收方每收到一个序号落入窗口的数据帧，就允许将该帧收下，然后将接受窗口向前滑动一个位置，并发回确认

可靠传输机制

可靠传输：发送方发送的数据都能被接收方正确的接收，通常采用超时和确认重传两种机制实现
- 确认：接收方每收到发送方发来的数据帧，都要向发送方发回一个确认帧，表示已正确地收到该数据帧
- 超时重传：发送方在发送一个数据帧后就启动一个计时器，若在规定时间内没有收到所发送数据帧的确认帧，则重发该数据帧，直到发送成功为止
传输差错：
- 出现在数据链路层上层：分组重复，分组失序，分组丢失
- 出现在数据链路层及其下层：误码（比特差错）
一般情况下，有线链路的误码率比较低，为了减小开销，并不要求数据链路层向上提供可靠传输服务，即使出现了误码，可靠传输的问题由其上层处理
无线链路易受干扰，误码率比较高，因此要求数据链路层必须向上层提供可靠传输服务
可靠传输服务并不仅局限于数据链路层，其他各层均可选择实现可靠传输
自动重传请求（ARQ）：
- 通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道差错的方法之一
- 重传的请求是发送方自动进行的，而不是接收方请求发送方重传某个误码的数据分组
- 在 ARQ 协议中，数据帧和确认帧都必须编号，以区分确认接收方是对哪个帧确认，以及哪些帧还未确认
- 分类：
  1. 停止 - 等待 ARQ (SW)
  2. 后退 N 帧 ARQ (GBN)
  3. 选择重传 ARQ (SR)

停止 - 等待 ARQ 协议：SW / 单帧滑动窗口

发送方发送数据 DATA，接收方接收时进行差错检测
如果没有出现误码，则接收信息并返回 ACK 确认分组给发送方，发送方收到 ACK 后，一次通信结束
如果出现误码，则丢弃信息并返回 NAK 拒绝分组给发送方，发送方收到 NAK 后，重传 DATA
引入超时重传机制：
- 解决 DATA 中途丢失的问题
- 发送方可在每发送完一个数据分组时就启动一个超时计时器
- 若到了超时计时器所设置的超时重传时间（RTO），但发送方仍未收到接收方的 ACK 或 NAK，就重传之前已发送过的数据分组
- 在数据链路层点对点的往返时间好确认，重传时间好确认
- 在运输层，由于端到端往返时间不确定，重传时间不好确认
对数据帧编号：
- 避免分组重复的传输错误
- 对于 SW 协议，每次发送一个数据分组就停止等待，只需一个比特来编号【0 / 1】
对确认帧编号：
- 避免确认分组迟到的情况【数据链路层一般不会出现】
信道利用率：

U = T_{D} / T_{D} + RTT + T_{A}

若出现超时重传，对于传送有用的数据信息来说，信道利用率还要降低
在往返时间 RTT 相对较大的情况下，为了提高信道利用率，收发双方不适合采用停止 - 等待协议，而可以选择使用回退 N 帧（GBN）协议或选择重传（SR）协议

例题

回退 N 帧 ARQ 协议：GBN / 多帧滑动窗口

回退 N 帧协议采用流水线传输方式，并且利用发送窗口来限制发送方连续发送数据分组的数量，这属于连续 ARQ 协议
接收窗口尺寸只能等于 1，因此接收方只能按序接收正确到达的数据分组
在使用流水线传输方式时，发送方不能无限制地连续发送数据分组，否则可能会导致网络中的路由器或接收方来不及处理这些数据分组，进而导致数据分组的丢失，这实际上是对网络资源的浪费
信道利用率：假设连续 ARQ 协议的发送窗口为 n：
- $n T_{D} < T_{D} + RTT + T_{A}$ ：即在一个发送周期内可以发送完 n 个分组 $U = n T_{D} / T_{D} + RTT + T_{A}$
- $n T_{D} >= T_{D} + RTT + T_{A}$ ：即在一个发送周期内可以发不完（或刚好发完） n 个分组，只要不发生差错，发送方就可不间断地发送分组，信道利用率为 1
信道平均（实际）数据传输速率 =
- 信道利用率 * 信道带宽（最大数据传输速率）
- 发送周期内发送的数据量 / 发送周期

无差错情况

发送方将 0-4 依次连续发送，没有出现乱序和误码
接收方按顺序接收他们，即每接受一个，接收窗口就向前滑动一个位置，并返回确认分组
发送方每接收一个，发送窗口就向前滑动一个位置
发送方可以将确认收到的分组从缓存中删除了，而接收方将已接收的分组择机交付给上层处理
GBN 协议允许接收方进行累计确认：
- 连续收到多个正确的数据帧后，对最后一个数据帧发回确认信息
- ACK n 表示发送过来的分组 x⇐n 的都收到了，下次期望收到 n+1 号帧
- 优点：即使确认分组丢失，发送方也可能不必重传，减小资源开销
- 缺点：不能及时反映出确认分组的信息

有差错情况

窗口尺寸的限制

帧序列号 = n 位时，发送窗口 W_{T} <= 2^{n} - 1, 接收窗口 = 1

此时，无法分辨新旧数据分组

总结

例题

选择重传 ARQ 协议：SR / 多帧滑动窗口

为了只重传出现差错的分组，接收方不能再采用累计确认，而需要对每个正确收到的分组进行逐一确认
接收方设置足够的帧缓冲区：
- 暂存那些失序但正确到达且序号落在接收窗口内的数据帧
- 数目等于接收窗口的大小

例题

介质访问控制

介质访问控制所完成的主要任务：为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号，以协调活动节点的传输
介质访问控制（MAC）子层：用来决定广播信道中信道分配的协议属于数据链路层的一个子层
常见的介质访问控制方法：
- 静态划分信道：信道划分介质访问控制
- 动态分配信道：随机访问介质控制、轮询访问介质访问控制

信道划分介质访问控制

概念：
- 将使用同一传输介质的多个设备的通信隔离开来，把时域和频域资源合理地分配给这些设备
- 通过复用技术实现
复用：指发送端把多个发送方的信号组合在一条物理信道上进行传输，在接收端把收到的复用信号分离出来，并发送给对应的接收方

频分复用 FDM

将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每对用户使用一个子信道进行通信
所有用户在同一时间占用不同的频带资源
优点：充分利用了传输介质的带宽，系统效率较高，实现也比较容易

时分复用 TDM

将信道的传输时间划分为一段段等长的时间片，称为 TDM 帧
每个用户在每个 TDM 帧中占用固定序号的时隙，每个用户所占用的时隙周期性【TDM 的长度】出现
所有用户在不同的时间占用同样的信道资源
缺点：按固定次序给用户分配时隙，信道利用率不高
统计时分复用（STDM）：
- 按需动态分配时隙
- 当用户有数据传送时，才会分配到 STDM 帧中的时隙，提高线路的利用率
- 又称：异步时分复用

波分复用 WDM

基于光的频分复用
在一根光纤中传输多种不同波长（频率）的光信号，因为波长不同，各路光信号互不干扰，最后用光分用器将各路波长分解出来
因为光波处于频谱的高频段，有很大的带宽，所以可以实现多路的波分复用

码分复用 CDM

采用不同的编码来区分各路原始信号的一种复用方式，同时共享信道的频率和时间
常称为码分多址 CDMA
每个用户可以在相同的时间使用相同的频带进行通信
将每个比特时间划分为 m 个更短的时间片，称为码片（Chip）
m 的取值通常为 64 或 128
每个站点都被指派一个唯一的 m 比特码片序列
- 某个站要发送比特 1，则发送它自己的 m 比特码片序列
- 某个站要发送比特 0，则发送它自己的 m 比特码片序列的反码
如果有两个或多个站同时发送数据，则信道中的信号就是这些站各自所发送一系列码片序列或码片序列反码的叠加
为了从信道中分离出每个站的信号，给每个站指派码片序列时，必须遵循以下规则：
- 分配给每个站的码片序列必须各不相同，实际常采用伪随机码序列
- 分配给每个站的码片序列必须相互正交，即各码片序列相应的码片向量之间的规格化内积为 0

举例

随机访问介质访问控制

在总线型网络中，两个或多个用户同时发送信息时，就会产生帧冲突【碰撞】
核心思想：胜利者通过争用获得信道，进而获得信息的发送权
结点之间既不共享时间，又不共享空间
实质是一种将广播信道转换为点到点信道的机制

ALOHA 协议

纯 ALOHA 协议

不监听信道，不按时间槽发送，随即重发，即想发就发
吞吐量很低

时隙 ALOHA 协议

同步各站点的时间，将时间划分为一段段等长的时隙 $T_{0}$
规定站点只能在每个时隙开始时才能发送帧，发送一帧的时间必须小于或等于时隙的长度
优点：避免了用户发送数据的随意性，降低了产生冲突的可能性，提高信道利用率

CSMA 协议

CSMA：
- 载波监听多路访问
- 每个站点在发送前都先监听公用信道，发现信道空闲后再发送
三种类型的 CSMA 协议比较：

信道状态	1 - 坚持	非坚持	p - 坚持
空闲	立即发送数据	立即发送数据	以概率 p 发送数据，以概率 1-p 推迟到下一个时隙
忙	继续坚持监听	放弃监听，等待一个随机的时间后再监听	持续监听（等到下一时隙再监听），直至信道空闲

CSMA/CD 协议（共享式以太网）

基本概念

CSMA/CD：
- 载波监听多路访问/冲突检测
- 适用于总线型网络或半双工网络环境
- 全双工网络不需要【收发双方可以同时发送和接收数据，不会冲突】
- 载波监听检测到总线空闲，但是总线不一定空闲
- 不能完全避免碰撞
- 先听后发，边听边发，冲突停发，随机重发
帧间最小间隔:
- 96 比特时间，指发送 96 比特所需要的时间
- 作用：接收方可以检测出一个帧的结束，同时也使得其他站点都能有机会平等竞争信道并发送帧

争用期（冲突窗口）

主机最多经过 $2 τ (δ \to 0)$ 的时长就可以检测到本次发送是否遭受了碰撞
因此，以太网的端到端往返传播时延 $2 τ$ 称为争用期
站点从发送帧开始，经过争用期这段时间还没有检测到碰撞，就可以肯定这次发送不会发生碰撞
每一个站点在自己发送帧之后的一小段时间内【取决于另一个发送帧的站点到本站点的距离，不会超过一个争用期】，存在着遭遇碰撞的可能性
- 总线的长度越长（单程端到端的传播时延越大），网络中站点数量越多，发生碰撞的可能性就越大
- 共享式以太网不能连接太多的主机，使用的总线也不能太长

为什么 $τ - \frac{δ}{2}$ 时刻发送碰撞？

当 D 开始发送时，A 已经走了 $τ - δ$ 时间，所以剩下路程所需要的时间是 $δ$ ，

又因为 A 和 D 发送速度是相同的，因此对于 $δ$ 时间的路程，每人只需要走 $\frac{δ}{2}$ 时间就会相遇，

即碰撞时刻= $τ - δ + \frac{δ}{2} = τ - \frac{δ}{2}$

为什么 $t = τ$ 时，D 检测到碰撞？

根据上边推论，D 走了 $\frac{δ}{2}$ 的时间路程后就发送了碰撞，此时它开始返回，经过同样的时间可以回到 D

检测到碰撞时间= $τ - \frac{δ}{2} + \frac{δ}{2} = τ$

为什么 $2 τ - δ$ 时，A 检测到碰撞？

与 D 检测到碰撞同理，A 走了 $τ - \frac{δ}{2}$ 时间，因此往回走也是这么多时间

A 检测到碰撞时间= $τ - \frac{δ}{2} + τ - \frac{δ}{2} = 2 τ - δ$

因此其总线长度不能超过 5210 m

但考虑到其他一些因素，如转发器所带来的时延，以及产生碰撞时继续发送 32 比特或 48 比特认为干扰信号所持续的时间等，

$τ$ 实际上要更小

最小帧长 64 B

最小帧长：总线传播时延 * 数据传输速率 * 2
- 争用期内可发送的数据长度
- 确保共享总线以太网上的每一个站点在发送完一个完整的帧之前，能够检测出是否产生了碰撞
- 如果在争用期检测到碰撞就立即中止发送，这时已经发送出去的数据一定小于 64 字节，因此凡长度小于 64 字节的帧都是由于碰撞检测而异常中止的无效帧，收到这种无效帧应立即丢弃
10 Mb/s 的以太网，在争用期可发送 512 bit，即 64 B
如果要发送的数据非常少，那么必须加入一些填充字节，使帧长不小于 64 B
一般来说，帧的数据载荷的长度应远大于帧首部和尾部的总长度，这样可以提高帧的传输效率

退避算法

正在发送帧的站点一边发送帧一边检测碰撞，当检测到碰撞时就立即停止发送，退避一段随机时间后再重新发送
共享总线以太网中的各站点采用截断二进制指数退避（Truncated Binary Exponential Backoff）算法来选择退避的随机时间
使用上述退避算法可使重传需要推迟的平均时间随重传次数而增大（即动态退避），因而减小产生碰撞的概率
当重传达 16 次仍不能成功时，就表明同时打算发送帧的站点太多，以至于连续产生碰撞，此时应放弃重传并向高层报告

信道利用率

考虑以下这种理想情况：
- 各站点发送帧都不会产生碰撞
- 总线一旦空闲就有某个主机立即发送帧
- 每帧的发送时延为 $T_{0}$ ，传播时延为 $τ$ ，占用信道的时间为 $T_{0} + τ$

极限信道利用率 S_{ma x} = \frac{T _{0}}{T _{0} + τ} = \frac{1}{1 + \frac{τ}{T _{0}}}

例题

CSMA/CA 协议（802.11 无线局域网）

基本概念

无线局域网中的问题：
- 无线网卡上接收到的信号强度往往会远远小于发送信号的强度，且在无线介质上信号的动态变化范围很大，若实现冲突检测，开销很大
- 存在隐蔽站的问题：并非所有站点都能听见对方
CSMA/CA：
- 载波监听多路访问/冲突避免
- 并不能避免所有的碰撞，而是尽量减少碰撞发生的概率
- 由于无线信道的通信质量远不如有线信道，所以 802.11 无线局域网不适用累计确认重传的方式，而使用链路层确认/重传机制（ARQ）【停止 - 等待协议】

帧间间隔 IFS

为了尽量避免碰撞，802.11 标准规定，所有的站完成发送后，必须等待一段很短的时间（继续监听）才能发送下一帧，这段时间称为帧间间隔 IFS
1. SIFS（短 IFS）:
  - 最短的 IFS, 用来分隔属于一次对话的各帧
  - 类型有 ACK 帧、CTS 帧、分片后的数据帧，以及所有回答 AP 探询的帧
2. PIFS（点协调 IFS）:
  - 中等长度的 IFS，在 PCF 操作中使用
3. DIFS（分布式协调 IFS）:
  - 最长的 IFS
  - 用于异步帧竞争访问的时延
802.11 的 MAC 层标准定义了两种不同的媒体接入控制方式;
- 分布式协调功能 DCF：
  - 没有中心控制站点，每个站点使用 CSMA/CA 协议通过争用信道来获取发送权
  - 这是 802.11 定义的默认方式
- 点协调功能 PCF ：
  - 使用集中控制的接入算法【一般在接入点 AP 实现】
  - 是 802.11 定义的可选方式，在实际中较少使用

工作原理

虚拟载波监听机制：
- 源站将它要占用信道的持续时间【包括目的站发回 ACK 帧所需的时间)】及时通知给所有其他站，以便使所有其他站在这段时间内都停止发送
- 表示其他站并未监听信道，而是因收到了源站的通知才不发送数据，这种效果就像是其他站都监听了信道
网络分配向量 NAV：指出了完成这次帧的传送且信道转入空闲状态所需的时间
源站检测到信道空闲后，还需要等待 DIFS 时间：
- 其他站此时可能有优先级更高的帧需要发送，因此有 DIFS 时间进行缓冲
- 若这个时间内没有高优先级的帧要发送，则说明信道是真正的空闲
目的站接收到帧后，还需要等到 SIFS 时间才返回 ACK 确认帧：
- SIFS 是最短的帧间间隔，用来分割一次对话的各帧
- 在这个时间里由接收状态转变为发送状态
发现信道忙后，等待了 DIFS 时间后，还要退避一段随机时间：
- 可能有多个站点在信道忙时都想发送帧，在 DIFS 时间后他们会同时发送，而实际上多个站点同时发送数据会碰撞
- 因此需要一个随机时间将他们进行错峰发送

退避算法

当某个站要发送数据帧时，仅在这种情况下才不使用退避算法：
- 检测到信道空闲，并且该数据帧不是成功发送完上一个数据帧之后立即连续发送的数据帧
除此之外的以下情况，都必须使用退避算法：
1. 在发送帧之前检测到信道处于忙态
2. 在每一次重传一个帧时
3. 在每一次成功发送帧后要连续发送下一个帧时
在执行退避算法时，站点为退避计时器设置一个随机的退避时间
- 当退避计时器的时间减小到 0，就开始发送数据
- 当退避计时器的时间还未减小到 0 时信道又转变为忙状态，这时就冻结退避计时器的数值，重新等待信道变为空闲，再经过 DIFS 后，继续启动退避计时器
在进行第 i 次退避时，退避时间在时隙编号 ${0, 1, .., 2^{i + 2} - 1}$ 中随机选择一个，然后乘以基本退避时间 (也就是一个时隙的长度) 就可以得到随机的退避时间【为了使不同站点选择相同退避时间的概率减少】
当时隙编号达到 255 时 (对应第 6 次退避) 就不再增加了

处理隐蔽站问题：RTS 和 CTS

源站在发送数据帧之前先广播一个请求发送 RTS 控制帧：
- RTS 能被范围内所有的站点都听到
- RTS 包括源地址、目的地址以及这次通信 (包括相应的确认帧) 所需的持续时间
若 AP 正确收到 RTS 帧，且信道空闲，则等待时间 SIFS 后，向源站发送一个允许发送 CTS 控制帧：
- CTS 包括这次通信所需的持续时间
- CTS 给源站明确的发送许可
- CTS 指示其他站在预约期间内不要发送
源站收到 CTS 帧后，在等待时间 SIFS，就可发送数据帧
若 AP 正确收到源站发来的数据，则等待时间 SIFS 后就向源站发送确认帧 ACK

时间长度与 NAV 计算

RTS 和 CTS 帧中的 Duration 字段是实现冲突避免的关键。它告诉其他站点，从当前帧结束开始，信道预计将被占用多长时间。

RTS 帧中的 Duration 计算: 源站 A 发送 RTS 时，需要计算完成整个数据交换过程（不包括 RTS 自身）所需要的总时间。

Duration_{RTS} = T_{SIFS} + T_{CTS} + T_{SIFS} + T_{Data} + T_{SIFS} + T_{ACK}

Duration_{RTS} = 3 \times T_{SIFS} + T_{CTS} + T_{Data} + T_{ACK}

其中：
- $T_{\text{SIFS}}$: 发送一个 SIFS 所需的时间。
- $T_{\text{CTS}}$: 发送一个 CTS 帧所需的时间。
- $T_{\text{Data}}$: 发送数据帧所需的时间。
- $T_{\text{ACK}}$: 发送 ACK 帧所需的时间。

CTS 帧中的 Duration 计算: 目的站 B 回复 CTS 时，需要计算从 CTS 帧结束到整个交换完成还需要的剩余时间。

Duration_{CTS} = T_{SIFS} + T_{Data} + T_{SIFS} + T_{ACK}

Duration_{CTS} = 2 \times T_{SIFS} + T_{Data} + T_{ACK}

**注意:** 也可以简化地认为，CTS 中的 Duration 值等于 RTS 中 Duration 值减去一个 SIFS 和一个 CTS 帧的发送时间：$\text{Duration}_{\text{CTS}} = \text{Duration}_{\text{RTS}} - T_{\text{SIFS}} - T_{\text{CTS}}$。

NAV (Network Allocation Vector) 的设置: NAV 是一个计时器，用于实现虚拟载波侦听。
- 听到 RTS 的站点: 凡是能听到源站 A 发送的 RTS 帧的站点（例如隐藏站 C），会读取 RTS 帧中的 Duration 字段，并将自己的 NAV 设置为该值。这些站点将在 NAV 倒计时结束前保持静默，即使它们的物理载波侦听显示信道空闲。
- 听到 CTS 的站点: 凡是能听到目的站 B 发送的 CTS 帧的站点，会读取 CTS 帧中的 Duration 字段，并更新（或设置）自己的 NAV 为该值。这确保了 B 周围的所有站点（包括 A 的隐藏站）都能知道信道将被占用，并保持静默。

CSMA/CD 与 CSMA/CA 的区别

CSMA/CD	CSMA/CA
可以检测冲突，但无法避免	发送数据的同时不能检测信道上有无冲突，本结点处没有冲突并不意味着在接收结点处就没有冲突，只能尽量避免
用于总线型以太网	用于无线局域网
通过电缆中的电压变化检测	采用能量检测、载波检测和能量载波混合检测三种检测信道空闲的方式

轮询访问：令牌传递协议

在轮询访问中，用户不能随机地发送信息，而要通过一个集中控制的监控站，以循环方式轮询每个结点，再决定信道的分配
典型的轮询访问控制协议是令牌传递协议：
- 一个令牌（Token）沿着环形总线在各站之间依次传递
- 令牌本身并不包含信息，仅控制信道的使用，确保同一时刻只有一个站独占信道
- 站点只有取得令牌后才能发送帧，发送完后释放令牌，不存在冲突
- 令牌在网环上依次传递，对所有入网计算机而言，访问权是公平的
- 网上所有结点共享网络带宽
- 适合负载很高的广播信道，即多个结点在同一时刻发送数据概率很大的信道
令牌环网络中令牌和数据的传递过程如下：
1. 当网络空闲时，环路中只有令牌帧在循环传递
2. 当令牌传递到有数据要发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附加自己需要传输的数据，将令牌变成一个数据帧，然后将这个数据帧发送出去
3. 数据帧沿着环路传输，接收到的站点一边转发数据，一边查看帧的目的地址，若目的地址和自己的地址相同，则接收站就复制该数据帧，以便进一步处理
4. 数据帧沿着环路传输，直到到达该帧的源站点，源站点收到自己发出去的帧后便不再转发，同时，通过检验返回的帧来查看数据传输过程中是否出错，若出错则重传
5. 源站点传送完数据后，重新产生一个令牌，并传递给下一站点，交出信道控制权

局域网

基本概念

局域网：在一个较小的物理范围（如一所学校）内，将各种计算机、外部设备和数据库系统等通过双绞线、同轴电缆等连线介质互相连接起来，组成资源和信息共享的计算机互联网络
主要特点：
1. 为一个单位所拥有，且地理范围和站点数目均有限
2. 所有站点共享较高的总带宽，即较高的数据传输速率
3. 较低的时延和较低的误码率
4. 各站为平等关系而非主从关系
5. 能进行广播和多播
局域网的特性主要由三个要素决定：
1. 拓扑结构：星形、环形、总线形、星形和总线形结合的复合型结构
2. 传输介质：双绞线【主流】、铜缆、光纤
3. 介质访问控制方式【最重要】：
  - 总线形局域网：CSMA/CD 协议、令牌总线协议
  - 环形局域网：令牌环协议
三种特殊的局域网拓扑实现如下：

	以太网（目前使用范围最广）	令牌环 IEEE 802.5	FDDI（光纤数字接口，IEEE 802.8）
逻辑拓扑	总线形	环形	环形
物理拓扑	星形	星形	双环

IEEE 802 标准定义的局域网将数据链路层拆分为：
- 逻辑链路控制（LLC）子层：
  - 与传输介质无关
  - 向网络层提供无确认无连接、面向连接、带确认无连接、高速传送四种不同的连接服务类型
- 介质访问控制（MAC）子层：
  - 与接入传输介质有关的内容都在 MAC 子层
  - 向上层屏蔽物理层访问的各种差异
  - 主要功能：组帧和拆卸帧、比特传输差错检测、透明传输

以太网（IEEE 802.3 局域网）

基本概念

以太网 Ethernet 是由 Xerox 公司创建并由 Xerox、Intel、和 DEC 联合开发的基带总线局域网规范，是局域网最通用的通信协议标准
严格来说，以太网应是符合 DIX Ethernet V 2 标准的局域网，但实际上 DIX Ethernet V 2 和 IEEE 802.3 基本相同，我们习惯上把以太网称作 IEEE 802.3 局域网
以太网是目前最流行的有线局域网技术
以太网逻辑上采用总线拓扑结构，信息以广播方式发送
以太网使用 CSMA/CD 方式对总线进行访问控制
以太网简化通信的措施：
1. 采用无连接的工作方式：
  - 既不对发送的数据帧编号，又不要求接收方发送确认
  - 尽最大努力交付数据，提供的是不可靠服务
  - 对差错的纠正由高层完成
2. 发送的数据使用曼彻斯特编码的信号

以太网传输介质、网卡

以太网常用的传输介质有四种：粗缆、细缆、双绞线、光纤

参数	10 BASE 5	10 BASE 2	10 BASE-T	10 BASE-F
传输媒体	基带同轴电缆（粗缆）	基带同轴电缆（细缆）	非屏蔽双绞线	光纤对（850 nm）
编码	曼彻斯特编码	曼彻斯特编码	曼彻斯特编码	曼彻斯特编码
拓扑结构	总线型	总线型	星型	点对点
最大段长	500 m	185 m	100 m	2000 m
最多结点数	100	30	2	2

10 BASE-T 非屏蔽双绞线以太网拓扑结构为星型网，中心为集线器，但使用集线器的以太网在逻辑上仍是一个总线型网，属于一个冲突域

要将计算机连接到以太网，需要使用相应的网络适配器（Adapter），又称网络接口卡（NIC）
在计算机内部，网卡与 CPU之间的通信，一般是通过计算机主板上的 I/O 总线以并行传输方式进行
网卡与外部以太网（局域网）之间的通信，一般是通过传输媒体（同轴电缆、双绞线电缆、光纤）以串行方式进行的
网卡除要实现物理层和数据链路层功能，另外一个重要功能就是要进行并行传输和串行传输的转换
为了使网卡正常工作，还必须要在计算机的操作系统中为网卡安装相应的设备驱动程序，负责驱动网卡发送和接收帧

以太网的 MAC 地址

当多个主机连接在同一个广播信道上，要想实现两个主机之间的通信，则每个主机都必须有一个唯一的标识，即一个数据链路层地址
在每个主机发送的帧的首部中，都携带有发送主机（源主机）和接收主机（目的主机）的数据链路层地址
由于这类地址是用于媒体接入控制（Medium Access Control，MAC）的，因此被称为 MAC 地址
MAC 地址一般被固化在网卡的电可擦可编程只读存储器 EEPROM 中，因此 MAC 地址也被称为硬件地址
MAC 地址有时也被称为物理地址
一般情况下，普通用户计算机中往往会包含两块网卡：
- 一块是用于接入有线局域网的以太网卡
- 另一块是用于接入无线局域网的 Wi-Fi 网卡
每块网卡都有一个全球唯一的 MAC 地址
MAC 地址长 6 字节（48 位），一般由连字符（或冒号分割的 12 个十六进制数表示）

注意：

字节的发送顺序：第 1 字节 →第 6 字节

字节内的比特发送顺序：b0 → b7;

广播地址（本地多播）FF-FF-FF-FF-FF-FF：

即第 1 字节 b 0 位=1，第 1 字节 b 1 位=1，并且剩余 46 比特为 全1

网卡从网络上每收到一个帧，就检查帧首部中的目的 MAC 地址，按以下情况处理：
- 广播帧（一对全体）：目的 MAC 地址是广播地址（FF-FF-FF-FF-FF-FF），则接受该帧
- 单播帧（一对一）：目的 MAC 地址与网卡上固化的全球单播 MAC 地址相同，则接受该帧
- 多播帧（一对多）：目的 MAC 地址是网卡支持的多播地址，则接受该帧
- 除上述情况外，丢弃该帧
网卡还可被设置为一种特殊的工作方式：混杂方式，只要收到共享媒体上传来的帧就会收下，而不管帧的目的 MAC 地址是什么

以太网 V2 的 MAC 帧

以太网 MAC 帧格式有两种标准：
1. DIX Ethernet V2 标准（以太网 V2，流行）
2. IEEE 802.3 标准
  - 用长度域替代了 V2 帧中的类型域，指出了数据域的长度
  - 长度域最大值是 1500，1501~65535 的值可用于类型段标识符
以太网的 MAC 帧的长度为 64-1518 字节【最小帧长到最大帧长】
以太网的数据链路层将封装好的 MAC 帧交付给物理层进行发送，物理层在发送帧之前还要在其前面添加 8 字节的前导码：
- 第一个字段是 7 字节的前同步码：实现 MAC 帧的比特同步
- 第二个字段是 1 字节的帧开始定界符：表示后面的信息就是 MAC 帧
注意：
目的地址：6 字节，帧在局域网上的目的适配器的 MAC 地址
源地址：6 字节，传输帧到局域网上的源适配器的 MAC 地址
类型：2 字节，指出数据字段中的数据应交给哪个上层协议处理，如网络层的 IP 协议
数据：46~1500 字节，承载上层的协议数据单元（如 IP 数据报）
- 若 IP 数据报超过 1500 字节，必须将 IP 数据报分片
- 由于 CSMA/CD 算法的限制，当数据字段的长度小于 46 字节时，MAC 子层在数据字段后面加一个整数字节的填充字段，以确保帧长不小于 64 字节
检验码（FCS）： 4 字节，算法采用 32 位 CRC 码，
- 检验 MAC 帧的目的地址、源地址、类型字段、数据部分
- 不检验前导码
接收方可能收到的无效 MAC 帧包括以下几种：
- MAC 帧的长度不是整数个字节
- 通过 MAC 帧的 FCS 字段的值检测出帧有误码
- MAC 帧的长度不在 64~1518 字节之间
如果接收方收到无效的 MAC 帧时，就简单将其丢弃（以太网的数据链路层没有重传机制，提供的是无连接、不可靠服务）

高速以太网

速率达到或超过 100Mb/s 的以太网叫高速以太网

标准名称	100 BASE-T 以太网	吉比特以太网	10 吉比特以太网
传输速率	100 Mb/s	1 Gb/s	10 Gb/s
传输介质	双绞线	双绞线或光纤	双绞线或光纤
通信方式	半双工、全双工	半双工、全双工	全双工
介质访问控制协议	半双工下使用 CSMA/CD	半双工下使用 CSMA/CD	无

100 BASE-T 以太网：
- 又称：快速以太网
- 在双绞线上传送 100 Mb/s 基带信号的星形拓扑以太网
- MAC 帧格式为 802.3 标准
- 保持最短帧长不变，将一个网段的最大长度减小到 100 m，帧最小间隔由 9.6 $μ$ s 改为 0.96 $μ$ s
吉比特以太网：
- 又称：千兆以太网
- 使用 802.3 标准的帧格式
10 吉比特以太网：
- 与 10 Mb/s、100 Mb/s、1 Gb/s 以太网的帧格式完全相同
- 保留了 802.3 标准规定的以太网最小帧长和最大帧长，以便升级和向后兼容

IEEE 802.11 无线局域网

无线局域网的组成

802.11 无线局域网可分为以下两类：
1. 有固定基础设施的无线局域网
2. 无固定基础设施的

固定基础设施是指预先建立的、能够覆盖一定地理范围的、多个固定的通信基站

802.11 无线局域网使用最多的是它的固定基础设施的组网方式

有固定基础设施的

IEEE 制定了无线局域网【又称 Wi-Fi】的 802.11 系列协议标准
802.11 标准使用星形拓扑，其中心称为接入点 AP【基站】，在 MAC 层使用 CAMA/CA 协议
基本服务集 BSS：
- 最小构件
- 一个 BSS 中，包含有一个 AP 和若干个移动站
- 本 BSS 内各站点之间的通信以及与本 BSS 外的站点之间的通信，都必须经过白 BSS 内的 AP 进行转发
- 安装 AP 时，必须为其分配一个最大 32 字节的服务集标识符（SSID）【使用该 AP 的无线局域网的名称】和一个无线通信信道
基本服务区 BSA：
- 一个 BSS 所覆盖的地理范围
- 无线局域网的 BSA 的直径一般 < 100 m
扩展的服务集 ESS：
- 通过 AP 连接到一个分配系统 DS，然后再连接到另一个服务集
- 分配系统的作用就是使扩展的服务集对上层的表现就像一个基本服务集一样
- ESS 还可以通过 Portal（门户）设备为无线用户提供到有线连接的以太网的接入，门户的作用相当于一个网桥
注意：AP1 到 AP2 的通信使用有线传输

无固定基础设施（自组织网络）

自组织网络没有 AP，而是由一些平等状态的移动站相互通信组成的临时网络
各结点地位平等，中间节点都为转发结点，因此都具有路由器的功能
自组网络和移动 IP 并不相同：
- 移动 IP 技术使漫游的主机可用多种方法连接到因特网，其核心网络功能仍然基于固定网络中一直使用的各种路由选择协议
- 自组网络是将移动性扩展到无线领域中的自治系统，具有自己特定的路由选择协议，且可以不和因特网相连

802.11 局域网的 MAC 帧

802.11 帧分三种：
1. 数据帧：用于在站点间的传输
2. 控制帧：
  - 通常与数据帧搭配使用
  - 负责区域的清空，虚拟载波监听的维护以及信道的接入，并于收到数据帧时予以确认
  - ACK 帧，RTS 帧以及 CTS 帧等都属于控制帧
3. 管理帧：
  - 用于加入或退出无线网络，以及处理 AP 之间连接的转移事宜
  - 信标帧，关联请求帧以及身份认证帧等都属于管理帧
802.11 无线局域网的 MAC 帧格式：
帧主体：数据部分，不超过 2312 字节，比以太网的最大长度长很多
帧检验序列 FCS：帧尾部，4 字节
MAC 首部：30 字节，主要包含：
- 持续期：用于实现 CSMA/CA 的虚拟载波监听和信道预约机制，在数据帧、RTS 帧和 CTS 帧中用该字段指出将要持续占用信道的时长
- 序号控制：用来实现 802.11 的可靠传输，对数据帧进行编号
- 地址 1、2、3、4：取决于帧控制字段中的“去往 DS”和“来自 DS”这两个字段的值
- 帧控制

地址 1 是直接接收数据帧的结点地址，地址 2 是实际发送数据帧的结点地址

注意，接收地址与目的地址不是一个概念，因为要通过 AP 中转

发送数据帧的情况：
1. A→B
2. A→R（路由器接口）：802.11 MAC 帧需要通过 AP 转为 802.3 帧
例题：

VLAN

基本概念

虚拟局域网 VLAN（Virtual Local Area Network）：
- 一种将局域网内的设备划分成与物理位置无关的逻辑组的技术
- 这些逻辑组具有某些共同的需求，每个 VLAN 就是一个独立的广播域
为什么需要 VLAN：随着交换式以太网规模的扩大，广播域相应扩大，而巨大的广播域会带来很多弊端（广播风暴）

广播风暴：如果数台交换机连接了数台主机，当主机 A 要向主机 B 发送数据帧，此时各交换机的 MAC 表均为空，因此帧每到一个交换机就会进行泛洪，由于网络巨大，因此泛洪的范围也巨大

分割广播域的方法：广播域与冲突域
1. 使用路由器：
  - 由于路由器默认情况下不对广播数据包进行转发，因此路由器很自然的就可以隔离广播域
  - 成本很高，全部使用路由器隔离广播域是不现实的

VLAN：将一个较大的局域网分割成一些较小的与地理位置无关的逻辑上的 VLAN

VLAN 划分方式

基于接口：
- 将交换机的若干接口划为一个逻辑组
- 最简单、最有效
- 若主机离开了原来的接口，则可能进入一个新的子网
基于 MAC 地址：
- 按 MAC 地址将一些主机划分为一个逻辑子网
- 当主机的物理位置从一个交换机移动到另一个交换机时，它仍属于原来的子网
基于 IP 地址：
- 根据网络层地址或协议划分 VLAN
- 这样的 VLAN 可以跨越路由器进行扩展，将多个局域网的主机连接在一起

IEEE 802.1 Q 帧

对以太网的 MAC 帧格式进行了扩展，插入了 4 字节的 VLAN 标签，用来标明计算机属于哪个虚拟局域网。
VLAN 的首部增加到了 4 字节，所以最大帧长为 1522 字节
VLAN 标签：
- 标签协议标识符 TPID：
  - 长度为 16 比特，其值固定为 0x8100
  - 表示该帧是 IEEE 802.1 Q 帧
- 优先级 PRI：
  - 长度为 3 比特，取值范围是 0~7，值越大优先级越高
  - 当网络阻塞时，设备优先发送优先级高的 802.1 Q 帧
- 规范格式指示符 CFI：
  - 长度为 1 比特，对于以太网，CFI 的取值为 0
  - 取值为 0 表示 MAC 地址以规范格式封装
  - 取值为 1 表示 MAC 地址以非规范格式封装
- 虚拟局域网标识符 VID：
  - 唯一地标志了以太网帧属于哪一个 VLAN 长度为 12 比特
  - 取值范围是 0~4095，其中 0 和 4095 保留不使用，因此用于表示 VLAN 的VID 的有效范围是 1~4094
注意：
- 插入 VID 后，FCS 字段必须重新计算
- 802.1 Q 帧时是交换机来处理的，而不是用户主机来处理的
- 用户不知道自己的 VID 值，但交换机必须知道，这样就实现了分割广播域
- 当交换机收到普通的以太网帧时，会将其插入 4 字节的 VLAN 标记转变为 802.1Q 帧【打标签】
- 当交换机转发 802.1 Q 帧时，可能会删除其 4 字节 VLAN 标记转变为普通以太网帧【去标签】

广域网

基本概念

广域网 WAN：
- 通常指覆盖范围很广（远超一个城市的范围）的长距离网络，任务是长距离运送主机所发送的数据
- 连接广域网各交换机的链路都是高速链路
- 首要考虑问题是通信容量必须足够大，以便支持日益增长的通信量
广域网由一些结点交换机及连接这些交换机的链路组成
- 结点交换机的功能：存储并转发分组
- 为了提高网络的可靠性，通常一个结点交换机往往与多个结点交换机相连
广域网使用的协议主要在网络层，局域网使用的协议主要在数据链路层
- 网络中的两个结点要进行数据交换，还要给数据“包装”上一层控制信息，用于实现传输控制
- 若这层控制信息是数据链路层协议的控制信息，则称使用了数据链路层协议
- 若这层控制信息是网络层协议的控制信息，则称使用了网络层协议
广域网和局域网的区别和联系：

	广域网	局域网
覆盖范围	很广，通常跨区域	较小，通常在一个区域内
连接方式	通常采用点对点连接	普遍使用广播信道
OSI 参考模型层次	物理层、数据链路层、网络层	物理层、数据链路层
着重点	强调资源共享	强调数据传输
联系与相似点	1. 广域网和局域网都是互联网的重要构件，从互联网的角度看，二者平等（不是包含关系）	2. 当连接到一个广域网或另一个局域网上的主机在该网内进行通信时，只需要使用其网络的物理地址

广域网早期使用能实现可靠传输的高级数据链路控制（HDLC）协议，目前使用最广泛的是点对点（PPP）协议

PPP 协议

PPP 点对点协议

基本概念

广域网应用最广泛的点对点数据链路层协议
PPP 用于规定帧格式，使之成为各种主机、网桥和路由器之间简单连接的一种共同的解决方案
PPP 是使用串行线路通信的面向字节的协议
主要有两种应用：
1. 用户通常都要连接到某个 ISP 才能接入互联网，PPP 协议就是用户计算机与 ISP 通信时所用的数据链路层协议
2. 广泛用于广域网路由器之间的专用线路
组成部分：
1. 一个链路控制协议 LCP：用来建立、配置、测试数据链路连接，以及协商一些选项
2. 一套网络控制协议 NCP： PPP 协议允许采用多种网络层协议，每个不同的网络层协议要用一个相应的 NCP 来配置，为网络层协议建立和配置逻辑连接
3. 一种将 IP 数据报封装到串行链路的方法：IP 数据报在 PPP 帧中就是其信息部分，这个信息部分的长度受最大传送单元 (MTU) 限制

PPP 链路的连接过程

PPP 帧格式

首部和尾部各有一个标志字段 F，规定为 0x7E（01111110），作为帧定界符，表示帧的开始和结束
注意：
- PPP 是点对点的，并不是总线形，所以不用 CSMA/CD 协议，自然就没有最短帧，所以数据部分是 0-1500B

PPP 帧实现透明传输

面向字节的异步链路使用字节填充法

发送方处理：
- 将数据载荷中出现的每一个 0x7E 减去 0x20【相当于异或 0x20】，然后在其前面插入转义字符 0x7D，变成 7D5E
- 若数据载荷中原来就含有 0x7D，则把每一个 0x7D 减去 0x20，然后在其前面插入转义字符 0x7D，变成 7D5D
- 将数据载荷中出现的每一个ASCII 码控制字符【即数值小于 0x20 的字符】，加上 0x20【相当于异或 0x20，将其转换成非控制字符】，然后在其前面插入转义字符 0x7D
接收方处理：只需要反变换可恢复出原来的帧的数据部分

面向比特的同步链路使用零比特填充来实现透明传输

发送方处理：对帧的数据载荷进行扫描【一般由硬件完成】，每出现5 个连续的比特 1，则在其后填充一个比特 0
接收方处理：对帧的数据载荷进行扫描，每出现5 个连续的比特 1时，就把其后的一个比特 0 删除

PPP 帧实现差错检测

PPP 协议的特点

PPP 提供差错检测但是不提供纠错功能，只保证无差错接收（CRC 校验），它是不可靠的传输协议，因此也不使用序号和确认机制
PPP 仅支持点对点的链路通信，不支持多点线路【PPP 属于广域网，这点就属于广域网和局域网的区别了】
PPP 只支持全双工链路
PPP 两端可以运行不同的网络层协议，但仍然可以使用同一个 PPP 进行通信
PPP 是面向字节的，因此所有 PPP 帧的长度都是整数个字节

数据链路层设备

网桥

基本概念

网桥（Bridge）工作在数据链路层（包含其下的物理层），因此网桥具备属于数据链路层相关能力
网桥在数据链路层扩展以太网：
- 原来的每个以太网称为一个网段
- 各个网段相互独立
网桥具有识别帧和转发帧的能力：
- 根据帧首部中的目的 MAC地址和网桥自身的帧转发表来转发或丢弃所收到的帧
- 起到了过滤通信量的功能

主要结构和基本工作原理

转发表是网桥转发帧的依据：记录各个主机的 MAC 地址与自己各接口的对应关系
网桥转发和丢弃帧：
网桥转发广播帧，是不查转发表的

透明网桥的自学习和转发帧流程

透明网桥通过自学习算法建立转发表
透明网桥中的透明：是指以太网中的各站点并不知道自己所发送的帧将会经过哪些网桥的转发，最终到达目的站点。也就是说，以太网中的各网桥对于各站点而言是看不见的
透明网桥的标准是 IEEE 802.1D，它通过一种自学习算法基于以太网中各站点间的相互通信逐步建立起自己的转发表
流程：
1. 网桥收到帧后进行登记（自学习），自学习的内容为帧的源 MAC 地址和进入网桥的接口号
2. 网桥根据帧的目的 MAC 地址和网桥的转发表对帧进行转发，包括以下三种情况:
  - 明确转发：网桥知道应当从哪个接口转发帧
  - 盲目转发：网桥不知道应当从哪个接口转发帧，只能将其通过除进入网桥的接口外的其他所有接口转发
  - 丢弃：网桥知道不应该转发该帧，将其丢弃

注意：
- 如果网桥收到有误码的帧则直接丢弃
- 如果网桥收到一个无误码的广播帧，则不用进行查找，而是直接转发
- 转发表中的每条记录都有其有效时间，到期自动删除，这是因为各站点的 MAC 地址与网桥接口的对应关系并不是永久性的【例如某个站点更换了网卡，其 MAC 地址就会改变】

透明网桥的生成树协议 STP

为了提高以太网的可靠性，有时需要在两个以太网之间使用多个透明网桥来提供冗余链路
在增加冗余链路提高以太网可靠性的同时，却给网络引入了环路
网络中的广播帧将在环路中永久兜圈，造成广播帧充斥整个网络，网络资源被白白浪费，而网络中的主机之间无法正常通信
透明网桥使用生成树协议（STP）：
- 可以在增加冗余链路来提高网络可靠性的同时又避免网络环路带来的各种问题
- 不管网桥之间连接成了怎样复杂的带环拓扑接，网桥之间通过交互网桥协议单元（BPDU）找出原网络中拓扑的一个连通子集【生成树】，在这个子集里整个连通的网络中不存在环路
- 最终生成树的逻辑拓扑要确保连通整个网络
- 当首次连接交换机或网络物理拓扑发生变化时【有可能是人为改变或故障】，网桥【交换机】都将进行生成树重新计算

以太网交换机

交换式以太网

网桥的接口数量很少，通常只有 2~4 个，一般只用来连接不同的网段
仅使用交换机（而不使用集线器）的以太网就是交换式以太网

交换机的原理和特点

本质上是一个多接口的网桥
当交换机的接口直接与主机或其他交换机连接时，工作在全双工方式，并能同时连通多对接口，使每对相互通信的主机都能像独占通信介质那样，无冲突地传输数据，**具有并行性
当交换机的接口连接集线器时，只能使用 CSMA/CD 协议且只能工作在半双工方式
交换机一般都具有多种速率的接口，例如 10 Mb/s、100 Mb/s、1 Gb/s 甚至 10 Gb/s 的接口，大部分接口支持多速率自适应
交换机因为使用专用交换结构芯片，交换速率较高
交换机独占传输介质的带宽：
- 使用集线器的共享式 10 Mb/s 以太网，若有 N 个用户，每个用户的平均带宽为（10 Mb/s）的 1/N
- 使用以太网交换机（全双工方式），每个接口到主机的带宽还是 10 Mb/s，但是因为一个用户通信时独占带宽，则拥有 N 个接口的交换机的总容量为 10N Mb/s
交换机每个接口是一个独立的冲突域
交换机一个端口可以对应多个 MAC 地址，但一个 MAC 地址不能对应多个端口

交换机自学习和转发帧流程（参考网桥）

交换机工作方式

直通交换方式：
- 只检查帧的目的 MAC 地址，以决定该帧的转发接口
- 优点：交换时延非常小
- 缺点：不检查差错就直接转发，因此可能将一些无效帧转发给其他站
- 不适用于需要速率匹配、协议转换或差错检测的线路
存储转发交换方式：
- 先将接收到的帧缓存到高速缓存器中，并检查数据是否正确，确认无误后通过查找表转换为输出接口，以便将该帧发送出去，若发现帧有错，则将其丢弃
- 优点：可靠性高，且能支持不同速率接口间的转换
- 缺点：时延较大

交换机端口类型

Access、Trunk、Hybird（华为私有）
具体内容见湖科大 ppt

共享式以太网与交互式以太网的对比（集线器和交换机的对比）

单播帧：
- 共享式以太网：集线器将帧转发到其他所有接口，其他各主机中的网卡根据帧的目的 MAC 地址决定接收或丢弃该帧
- 交换式以太网：交换机收到帧后，根据帧的目的 MAC 地址和自身的交换表将帧明确地转发给目的主机
广播帧：
- 尽管集线器和交换机对于广播帧的效果是相同的，但是它们的工作原理不同
- 共享式以太网，集线器只工作在物理层：
  - 并不能识别帧首部中的目的 MAC 地址，因为这属于数据链路层的范畴
  - 将帧转发到其他所有接口
  - 其他各主机中的网卡检测到帧的目的 MAC 地址是广播地址时，就接收
- 交换式以太网，交换机工作在数据链路层：
  - 可以识别帧的结构，从帧首部中提取出目的 MAC 地址，知道这是一个广播帧，从其他所有接口转发该帧（不查转发表）
  - 其他主机收到该广播帧后，就接收
多主机同时通信：
- 共享式以太网：必然产生冲突
- 交换式以太网：交换机能实现多对接口的高速并行交换，不会冲突
使用集线器和交换机扩展共享式以太网的区别：
- 集线器既扩大了广播域又扩大了冲突域
- 交换机扩大了广播域，隔离了冲突域

Okay, three, two, one, let's jam

Explorer

301 数据链路层

数据链路层

数据链路层概述

主要任务

为网络层提供服务

信道分类

三个重要问题

相关概念

封装成帧和透明传输

封装成帧（组帧）

字符计数法

字节填充法

零比特填充法

违规编程法

透明传输

差错检测

误码的相关概念

检错编码

奇偶检验码

循环冗余码 CRC

纠错编码（海明码）

流量控制与可靠传输机制

流量控制与滑动窗口机制

停止 - 等待流量控制基本原理

滑动窗口流量控制基本原理

可靠传输机制

停止 - 等待 ARQ 协议：SW / 单帧滑动窗口

例题

回退 N 帧 ARQ 协议：GBN / 多帧滑动窗口

无差错情况

有差错情况

窗口尺寸的限制

总结

例题

选择重传 ARQ 协议：SR / 多帧滑动窗口

例题

介质访问控制

信道划分介质访问控制

频分复用 FDM

时分复用 TDM

波分复用 WDM

码分复用 CDM

随机访问介质访问控制

ALOHA 协议

纯 ALOHA 协议

时隙 ALOHA 协议

CSMA 协议

CSMA/CD 协议（共享式以太网）

基本概念

争用期（冲突窗口）

最小帧长 64 B

退避算法

信道利用率

例题

CSMA/CA 协议（802.11 无线局域网）

基本概念

帧间间隔 IFS

工作原理

退避算法

处理隐蔽站问题：RTS 和 CTS

时间长度与 NAV 计算

CSMA/CD 与 CSMA/CA 的区别

轮询访问：令牌传递协议

局域网

基本概念

以太网（IEEE 802.3 局域网）

基本概念

以太网传输介质、网卡

以太网的 MAC 地址

以太网 V2 的 MAC 帧

高速以太网

IEEE 802.11 无线局域网

无线局域网的组成

有固定基础设施的

无固定基础设施（自组织网络）

802.11 局域网的 MAC 帧

VLAN

基本概念