# 数据链路层
* 链路(link)是一条**点到点**的**物理线路段**，中间没有任何其他的交换结点。
* 一条链路只是一条通路的一个组成部分
* 数据链路(data link) 除了物理线路外，还必须有**通信协议**来控制这些数据的传输。把实现这些协议的硬件和软件加到链路上，就构成了**数据链路**。目的是让通信过程变得更加可靠。
* 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。
* **一般的适配器都包括了数据链路层和物理层这两层的功能**。
## From Signals to Frames(帧结构)
数据链路层采用了帧结构传输，当传输中有位发生错误时，只需要重新传输有错误的帧，提高了传输的效率。\
## 数据链路的主要功能
1. 链路管理
2. 封装成帧 (帧定界)
* 有起始帧和终止帧表示传输的开始和结束
3. 流量控制
* 当传输的速率过快或者稍慢可以调节传输速率
4. 差错控制
* 如带有海明校验码进行传输帧的检验和纠错
5. 透明传输
* 下一层不需要关心帧的传输，就像数据链路层不需要关心物理层的bit传输
* 在面向比特的传输协议中，通过在连续5个1后面插入0来转义起止符
* 在面向字节的传输协议中，通过插入转义字节来转义起止符
6. 寻址
* 确定接受信息的对象地址
### 数据链路层传送的是帧
帧的封装和拆取是互逆的操作\
### 向网络层提供的服务
* 无确认的无连接服务
* e.g. 以太网
* 不需要对方在线，不需要建立连接，**不需要**对方应答
* 有确认的无连接服务
* 不需要对方在线，不需要建立连接，**需要**对方应答
* 面向连接的服务
* 有建立连接、相互应答、结束连接等过程
### 成帧
* 涉及的问题
* 将上层(网络层)交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧；
* 考虑接收双方的同步问题（即定界）；
* 计算帧的校验和并放入帧中一起传送给接收方；
* 协议数据单元 PDU(Protocol Data Unit)
* 帧：在数据链路上交换数据的单位。
#### 成帧方式
* 物理层编码违例法
* 发出非0非1表示传输开始
* 不正常，不常用
* 字符填充的首尾定界法
* 以字节为单位进行传输
* 以 `10101011` 为起止符
* 传输的数据是8bit的倍数
* e.g. 以太网中使用最多
* 位填充的首尾定界法
* 以比特为单位进行传输
* 以 `0111111` 为起止符
* 传输的数据不受限制，不需要是8bit的倍数
* e.g. 广域网中使用最多
### 流量控制
* 数据链路层要控制从同等实体接收PDU的速率。
* 流量控制定义：限制发送方发送速度的一种机制。使发送速率不能超过接收方能处理的速率。
* 流量控制的特点
* 流量控制必须是动态的
* 流量速度不仅与发方速度相关而且与网络的当前拥挤程度有关
* 必须有某种反馈机制
* 使**发送方**了解**接受方**的当前处理能力
### 差错控制
* 顺序到达
* 指保证所有的帧最终都按正确的发送次序到达目的。
* 确认方式
* ACK肯定确认
* NAK否定确认
* 计时器法
* 计时器值的设定要保证一帧到达对方并作处理后，相应的确认帧返回。
* 如果超时则主动重发
* 检错和纠错
* 检出传输中出现的差错；可能的话确定出错位置从而纠正错误。
### 数据链路层协议的作用
\
数据链路层只负责点对点，不参与网络层的相关\
DataLink的协议使得线路传输变好了
### 帧传输模型
#### 理想传输模型
最理想的情况基于两条基本假设:\
1\. 传输的数据不会出差错,也不会丢失\
2\. 不管发送方以多快的速率发送数据, 收方总来得及收下.\
#### 去掉第二条假设情况
去掉第二条假设（不管发送方以多快的速率发送数据, 收方总来得及收下），需引入**流量控制**。 
#### 去掉第一条假设情况
去掉第一条假设，可能会出现死锁。需要引入差错控制和超时重发机制。\
**组合四种的网络情况**\
### Automatic Repeat reQuest (ARQ协议)
#### Stop and Wait
步骤:\
1\. Source transmits frame\
2\. Destination receives frame and replies with acknowledgement\
3\. Source waits for ACK before sending next frame\
4\. Destination can stop flow by not send ACK\
5\. **Works well for a few large frames**
* **源实体**发送一个PDU，并启动一个**计时器**。目标实体收到后发回一个对该PDU的确认，表示同意接受下一个PDU
* 计时器作用：防止死锁，两个相互等待
* 计时器时间设置：略大于单程传输时间
* **源实体**必须**等待直到收到确认**后才能发送下一个PDU；如果源实体的**计时器超时**后还没有收到确认，就重新发送一次。
* **目标实体**能简单地用**停止发送确认的方式来阻止数据流**。
* 由接受方控制发送方的数据流乃是计算机网络中流量控制的一个基本方法。
**详细步骤**
在发送结点：\
(1) 从主机取一个数据帧。\
(2) 将数据帧送到数据链路层的发送缓存。\
(3) 将发送缓存中的数据帧发送出去（启动Timer）。\
(4) 等待。\
(5) 若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。
在接收结点：\
(1) 等待。 (2) 若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。\
(3) 将接收缓存中的数据帧上交主机。 (4) 向发送结点发一信息，表示数据帧已经上交给主机。 (5) 转到(1)。
\
* 举个例子：
#### Stop-and-Wait ARQ with Errors
* 设 P 是传输帧出错的概率，则传输一帧的期望为：
* $$N\_x = \frac{1}{1-P}$$
* 线路最大利用率为：
* $$U=\frac{1}{N\_x (1+2a)}=\frac{1-P}{1+2a}$$
**实用的停等ARQ协议**
特点：简单，效率低
* 超时重发技术
* A发送完一个数据帧时，就启动一个超时计时器
* 重复帧问题
* 如果是接收方的应答帧丢失(差错)，会导致发送方重复发送，出现重复帧。每个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1，（mod 2），1 bit序号。
* 帧的编号问题
* 序号所占用的比特数是有限的，因此，经过一段时间后，发送序号就会重复。
* 序号占用的比特数越少，数据传输的额外开销就越小。习惯表示，ACKn 表示“第n \* 1号帧已经收到，现在期望接收第n号帧。
**Stop-and-Wait ARQ结论**
stop-wait协议ARQ的优点比较简单，但缺点是**通信信道的利用率不高**，尤其是传播延时很大时，可采用连续ARQ和选择重传ARQ。
#### Go Back N (GBN)
* Window size W
* The sender transmits packets 0,1,2, …,W-1 and waits for up to T seconds for each of their ACKs. As soon as the receiver gets an ACK for packet 0 it transmits packet W.
* If time-out go back n and retransmit.
* 接受端只按序接收数据帧
* 每发送一个数据帧都要设置超时timer
* 因连续发送数据帧而提高了效率，但信道传输质量很差时，效率不一定优于stop-wait 协议。
* 发送端在重发表中**保存所发送的每个数据帧的备份**。重发表按**FIFO队列**操作。
* 每个数据帧**包含一个唯一的序号**，该序号在相应的ACK帧中返回，返回该序号时，发送端从**重发表中删除该数据帧**。
* 对每个出错的数据帧，接收端都产生相应的NAK帧；发送端一收到NAK,**从重发表中尚未确认的第一个帧**开始重新发送。
**注意：**上图中的**累计确认**方式，即 **发送ACK4的时候**表示前面的0-3都已经收成功收到了，所以此时只需要从第4个开始重发。
**做个题**：\
答案：\
#### Sliding Windows (滑动窗口)
* 前提：在连续ARQ协议中，必须对可以连续发出的**最多帧数**（已发出但未确认的帧）**作限制**，每一帧设置timer。
* 原则：**循环重复使用有限的帧序号**，以形成固定值（标准）
* 流量控制：
* 发送窗口：其大小**WT**表示在收到对方确认的信息之前，可以连续发出的最多帧数（只有序号在窗口内的帧才可发送）
* 接收窗口：其大小**WR**可以连续接收的最多数据帧数（只有序号在窗口内的帧才可以接收，否则丢弃）
* **接收窗口驱动发送窗口的转动**
* 发送/接收窗口的关系式(n为序号的位数)： $$W\_T+W\_R \leq 2^n$$ $$W\_T \leq 2^n-1$$
举个例子(转盘表示)：\
举个例子(滑轨表示)：\
**发送方**\
\
**接收方**\
**回退N协议的最大发送窗口大小**
\
上图考虑了一种极其特殊的情况：当接收方的ACK完全丢失的时候，此时发送方要从序号0开始重新发送，接收方却指向了**下一个新的连续m的序号0**，这样子当接收方收到发送方**重新发送的序号0**时，不能对其做出正确判断，导致存储发生重复错误。\
故结论为：
* W\_T=m : 当确认全部丢失时易造成混肴
* W\_T=m-1 : 发送序号为 0\~m-2；重新发送的第一个序号是0，下一轮的第一个序号是 m-1，不会混淆——**最大滑动窗口**
* W\_T< m-1 : 更加不会混淆
**注意**：这里 GBN 的编号是一开始就预留的，滑动窗口的大小收到其限制
#### Selective Repeat (选择重传ARQ)
* 在连续ARQ中，如果某个数据帧发生差错，后续的数据帧即使被正确地接收到，也要被丢弃，造成网络资源浪费
* 为进一步提高信道的利用率，可设法**只重传出错的数据帧或计时器超时的数据帧**
* **可加大接收窗口**，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。
* 选择重传 ARQ 协议可避免重复传送那些**本来已经正确到达接收端**的数据帧。
* 我们付出的代价是在**接收端**要设置**具有相当容量的缓存空间**(保存窗口中正确的帧)，**实现相对复杂**。
**选择重传ARQ协议**
* 原则：只重传出错或定时器超时的数据帧
* 方法：WR > 1，暂存接受窗口中序号在出错帧之后的数据帧
* 优点：避免重传已正确传送的帧，提高信道利用率
* 缺点： 在接收端需要占用一定容量的缓存，算法相对复杂
* 接收窗口的尺寸不能超过2^(n-1)（即序号范围的1/2），否则可能造成帧的重叠。接收窗口的最大值：$$W\_R \leq W\_T$$ $$W\_R \leq 2^{n-1}$$
**接收窗口尺寸过大发生重叠举例**
**注：**确认信号完全丢失的情况下，发送方重新发送0-3，而接收方希望得到4-7和下一个0，此时由于发送和接受的0序号相等导致接收端接收到了错误的序号0
**与GBN协议对比**
| GBN | selective repeat |
| :-------------------------------------------------------------------------: | :-------------------------------------------------------------------------: |
| W\_T>1
W\_R=1
| W\_T>1
W\_R>1
|
| 只能按顺序接受数据帧
帧出错或丢失需要丢弃该帧以其后所有帧
发送端超时需要重发出错帧及后面所有帧
| 发送端只需要发送出错的帧
不需要重发其后的所有帧
|
| 发送端需要为每个等待确认的帧设置定时器 | 发送端支持累计确认 |
| 发送窗口尺寸不能超过2^(n-1) | 接受窗口不能超过2^(n-1) |
| 接收窗口尺寸一般为1
逐个接受并返回确认信号
| 发送窗口尺寸一般与接收窗口尺寸相同
发送端为每一个输出缓冲区设置定时器
定时器超时则该缓冲区中的帧则被重发
|
| 发送端保持缓存来保存没有确认的帧 | 接收端需要相当的缓存 |
* 出错全部重发协议中，发送窗口的尺寸是大于1(加大接受窗口)，而接收窗口的尺寸则等于1。
* 由于接收窗口的尺寸为1，接收端只能按顺序地接受数据帧，一旦**某个帧出错或丢失，只能简单地丢弃该帧及其所有的后续帧**（因为发送窗口的尺寸是大于1的），不作任何确认。**发送端超时后需重发出错或丢失的帧及其后续所有的帧**。
* 发送端需要为每个待确认的帧各自设置一个定时器。
* 发送窗口的尺寸不能超过2^(n-1) (这里的n为序号的编码位数)，否则会造成接收端无法分辨新、旧数据帧。
* 只要求发送端保持一定数量的缓存来保存没有确认的数据帧，对接收端没有缓存的要求。但在误码率高的情况下，会大大降低信道的利用率。
#### 归纳三种方式
| $$W\_T$$ | $$W\_R$$ | 滑动窗口协议 |
| :------: | :------: | :--------------: |
| >1 | =1 | GBN |
| >1 | >1 | Selective Repeat |
| =1 | =1 | Stop-and-Wait |
### 差错控制 (Error Control)
* 所谓差错，就是在通信接收端收到的数据和发送端发送的数据不一致的情况。
#### 差错控制技术
* 在发送的数据码元序列中加入**监督位**，并进行某种变换，使它们和原来相互独立的数据码元之间具有**某种约束关系**。如果这种约束关系被破坏，则接收端就可以发现传输中的错误，甚至纠正错误。
* 变换的方法不同，就构成了不同的编码，因而产生不同的差错控制方法。
* **检错码可以发现传输错误，但不能自动纠正**。
* 主要代表：CRC循环冗余校验
* **纠错码可以自动纠正传输错误**。
* 由于实现复杂+需要更多冗余位导致传输效率降低，大部分纠错码限于1-3位纠错
* 主要代表：Hamming Code(汉明码)，主要用来纠正1位差错
* 由于监督位需要占用传输资源，所以差错控制是以**降低效率**为代价的。
* 解决方案：
* 自动请求重发 (ARQ , Automatic Repeat Request）
* 正向纠错 (FEC , Forward Error Correction）
* 实际应用中主要用ARQ，只有**单向（工）通信用FEC** (如电视)
#### 循环冗余检验CRC计算
* 待传送数据M，约定好的供差错检测用位n位和约定好的除数P(P的首位和末位一定为1)
* 在M的后面直接添加n位的0，与P进行[**模2除法**](https://baike.baidu.com/item/%E6%A8%A12%E9%99%A4%E6%B3%95/10416971?fr=aladdin)
* 模2除法中不采用借位而是直接求 **异或**
* 将上面模2除法的余数拼接在M的后面进行传输
* 接收端接收到的数据与约定好的除数P进行模2除法，结果为0则正确，不为0则错误
举个例子：
* M = 1010001101，设 n = 5, P = 110101
* 加上n位0的M为 101000110100000，模 2 运算的余数 R = 01110
* 将余数 R 作为冗余码添加在数据 M 的后面为 101000110101110
* 接收方将 101000110101110 与 110101 模2运算结果为 0
* CRC循环冗余计算特点：检错能力极强，开销小，易于用编码器及检测电路实现(异或位运算对硬件友好)
#### FEC (正向纠错)
* 差错控制的重要措施：采用抗干扰编码(即纠错编码)。
* 定义
* 码组：由n个码元(0,1)构成的每一组合
* 信息码：代表报文的0和1
* 监督码：插入的 "0" 和 "1"
* （按照某种规律在信息序列中插入一定数量的新码元）
举个例子：
* 需要传输 0 或 1
* 若直接传输 0 或 1，完全不知道是否有错误发生
* 若用00代替0，11代替1，则{00,11}是**准用码组**，{01,10}是**禁用码组**，则具备1位检错能力，不具备纠错能力
* 若用000代替0，111代替1，则只有{000,111}是准用码组，具有检出两位及两位以下错码的能力，具有纠正一位错码的能力，纠正是按照最短汉明距离计算的
* **码距**：指两个码组对应码位码元不同的个数
* e.g. (000)与(010) 的码距为1，(000)与(110) 的码距为2，(000)与(111) 的码距为3
* 由此可见，码组的**最小距离**越大，其抗干扰能力越强
* **汉明距离**（d0） ：一个有效编码集中，任意两个码字的码间距离的最小值。即一组编码中的最小码距
* 编码关系式
* 为了检出e个错码，要求码集的汉明距离：$$d \geq e+1$$
* 为纠正t个错码，要求码集的汉明距离：$$d \geq 2t+1$$
* 为了检出e个错码，同时能纠正t个错码，则应满足：$$d \geq e+t+1 (e>t)$$
* 计算为m位数据纠错时所需的冗余位数 r ：\
数据传输的总位数是m+r，且要求 r必须能够至少表示 m+r+1 种状态。其中，一种状态表示无差错，m+r 种状态分别表示在 m+r 位每个位置上发生的差错。\
由于r 位二进制数可以表示2^r种不同的状态,所以，2^r必须大于或等于 m+r+1。\
$$2^r\ge m+r+1$$\
e.g. 传输10位的数据采用汉明校验码，则需要冗余的4位。
做个题：\
## 差错检测
* 接收方收到数据单元和CRC后，将整个码字除以给定除数（同生成CRC用的除数）。
* 如果到达的数据没有差错，接收方CRC校验器产生的余数应是0，数据被接收，如果余数非0则被拒收。
注：上图中是在左端补齐，左端是末端，应该是小端存储。
### 纠错码
* 理论上，自动纠正每一个二进制代码的传输差错是可以做到的。但纠错码比检错码复杂得多，而且需要更多的冗余位，导致传输效率降低。为此，大部分纠错码只限于处理1位、2位或3位差错。
* 在数据通信中，最常用的纠错码是所谓“汉明码”(Hamming Code），是贝尔实验室的科学家R.W\.Hamming 于1950年提出的，主要用来纠正1位差错。
1. 自动请求重发 (ARQ , Automatic Repeat Request）
* 自动发现差错并要求对方重发
2. 正向纠错 (FEC , Forward Error Correction）
* 自动发现并纠正错误
**实际应用中主要用ARQ，只有单向（工）通信用FEC**
## 面向位的协议HDLC
* 1974年，IBM的SNA采用了**面向比特**的 SDLC（Synchronous Data Link Control）
* 国际标准化组织把SDLC修改为**高级数据链路控制** HDLC （High-Level Data Link Control）
* CCITT则把HDLC再修改后称为链路接入规程LAP（Link Access Procedure)，后改为LAPB。B即表示**平衡型**。
* HDLC中只有一个地址域，即**从站的地址**，在命令帧中，它是目的地址，在响应帧中，它是源地址。
### HDLC特点
* HDLC是**面向比特**的数据链路控制协议的典型代表，该协议**不依赖于任何一种字符编码集**；
* 数据报文可**透明传输**，用于实现透明传输的 **“0比特插入法”** 易于**硬件实现**；
* **全双工通信**，有较高的**数据链路**传输效率；
* 所有**帧**采用**CRC检验**，对信息帧进行顺序编号，**可防止漏收或重发**，传输可靠性高；
* HDLC**支持**的规程种类包括异步响应方式下的**不平衡操作、正常响应方式下的不平衡操作、异步响应方式下的平衡操作**。
### HDLC Link Configurations
#### 不平衡 Unbalanced
* One primary and one or more secondary stations，采用**主从结构**（有一个结点Primary管理其他结点Secondary），链路上一个主站控制多个从站，主站向从站发命令，从站向主站返回响应。
* Supports full duplex（全双工） and half duplex（半双工）
**平衡 Balanced**
* Two combined stations（既是Primary又是Secondary）
* * Supports full duplex and half duplex
### HDLC Station Types
#### Primary station 主结点 (Unbalanced)
* Controls operation of link
* Frames issued are called commands
* Maintains separate logical link to each secondary station
#### Secondary station 从结点
* Under control of primary station
* Frames issued called responses
#### Combined station 既是主又是从结点 (Balanced)
* **May issue commands and responses**
### HDLC Transfer Modes
## Frame Structure
* 帧同步机制 首位标志Flag：01111110
* All transmissions in frames
* Single frame format for **all data** and **control** exchanges
### Flag Fields
* Delimit frame at **both ends**：01111110
* May close one frame and open another（01111110可以同时作为一个帧的结尾和开始）
* Receiver hunts for flag sequence to synchronize
* Bit stuffing used to avoid confusion with data containing 01111110
* 0 inserted after every sequence of five 1s
* If receiver detects five 1s it checks next bit
* If 0, it is deleted
* If 1 and seventh bit is 0, accept as flag
* If sixth and seventh bits 1, sender is indicating abort
#### Bit Stuffing （位填充）
为了解决中间传输的信息遇到 01111110 的时候被误判为结束，位传输过程中会在 **五个1后面加一个0**，接收端在拆包的时候将5个1后面跟着的0删去。 
### Address Field
* **Identifies secondary station that sent or will receive frame**
* **Usually** 8 bits long
* May be **extended to multiples of 7 bits**
* LSB （Least Significant Bit）of each octet indicates that it is the last octet (1) or not (0)
* 每8位的最小位是0或1，0代表后面还有扩充地址，1代表扩充地址结束
* 
* All ones (11111111) is broadcast
* 全1的情况是发送广播，任何人都能接收
### Control Field
* Different for different frame type
* **Information** - data to be transmitted to user (next layer up)
* Flow and error control(流控制和差错控制) piggybacked(捎带) on information frames
* 开头第一位是 0
* **Supervisory** - ARQ when piggyback not used
* 监控帧用于差错控制和流量控制
* 开头两位是 10
* **Unnumbered** - supplementary link control
* 开头两位是 11
* **First one or two bits** of control filed identify frame type
#### Control Field Diagram
* 8位控制码
* 16位控制码
**注意里面构成**：
* N(S) = Send Sequence Number
* N(R) = Receive Sequence Number
* S = Supervisory Function Bits
* M = Unnumbered Function Bits
* P/F = Poll/Final Bit
#### Poll/Final Bit
* Use depends on context(基于传输的内容)
* Command frame
* P bit
* 1 to solicit (poll) response from peer（发出请求）
* Response frame
* F bit
* 1 indicates response to soliciting command（发出应答）
### Information Field
* Only in information and some unnumbered frames
* Variable length
* 信息帧用于传送有效信息或数据，通常简称I帧。
* **I帧以控制字第一位为“0”来标志**。
* 信息帧的控制字段中的**N（S）用于存放发送帧序号**，以使发送方不必等待确认而连续发送多帧。
* **N（R）用于存放接收方下一个预期要接收的帧的序号**，N（R）=5，即表示接收方下一帧要接收5号帧，换言之，**5号帧前的各帧接收到**。
* N（S）和N（R）均为**3位二进制编码**，可取值0～7。
### Frame Check Sequence Field
* FCS
* Error detection
* 16 bit CRC
* Optional 32 bit CRC
### HDLC Operation
* Exchange of information(负责传输数据), supervisory(负责进行检查) and unnumbered frames(负责建立连接)
* Three phases（面向连接三步曲）
* \*Initialization
* Data transfer
* Disconnect
### The unnumbered format
| Action | Code | ? | Meaning |
| :--------------------------------------------------------------: | :----------: | :-: | :------------------------------------------------: |
| SABME
(Set Asynchronous Balanced Mode)
| 1111P110 | C | Request logical connection |
| DM
(Disconnect Mode)
| 1111F000 | R | Unable to establish or maintain logical connection |
| UI
(Unnumbered Information)
| 1100P000 | C | Used for unacknowledged information transfer |
| DISC
(Disconnect)
| 1100P010 | C | Terminate logical connection |
| UA
(Unnumbered Ack)
| **1100F110** | R | Acknowledge SABME or DISC |
| FRMR
(Frame Reject)
| 1110F001 | R | Unacceptable frame report |
| XID
(Exchange Identification)
| 1111\*101 | C/R | Exchange identification information |
### Operations
1. Connection Establishment
* SABME ---->
* <----- UA
2. Data Transfer
* I-frames and
* S-frames for flow and error control.
3. Disconnect
* **Either entity** can issue a DISC
#### Examples
\
#### Practice
## Internet中的数据链路层
### SLIP (Serial Line IP)
1. IP数据报用字符END（0XC0）定界。（11000000）
2. 如果在IP数据中出现END字符（0XC0），就用2字节字符 0Xdb，0Xdc 代替。
3. 如果IP数据报中有字节为0Xdb，就用 0Xdb，0Xdd 代替。
存在的问题：\
1\. 没有类型域，只能支持IP数据报。\
2\. 没有校验位。
### PPP( Point to Point Protocol)
特点：
* IP地址的动态分配和管理；(因为是点对点传输所以甚至可以开始时没有地址)
* 同步（面向位的同步传输）或异步（起始位+数据位+奇偶校验位+停止位）传输；
* 网络层协议的复用；
* 链路的配置、质量检测和纠错；
* 多种配置参数选项的协商。
#### PPP frame structure
* FLAG: 7Eh = b'01111110
* ADDR: FFh = b'11111111 直接硬编码，因为点对点不需要地址
* CONTROL: 03h = b'00000011
* PROTOCOL: PPP支持不同的协议
* CRC: 校验码
#### PPP状态转移图
* PPP协议通过**LCP协议**完成**数据链路的配置和测试**
* PPP协议通过**NCP协议**完成**点对点通信设备之间网络层通信所需参数的配置**
#### LCP协议数据报文的格式
#### LCP：链路配置报文举例
**一次交互**
* PPP不存在主从之分，两者都可以发起请求和应答
* 假设点对点通信的一端发送了一个**Config-Request**报文，该报文将携带多种配置选项，具体携带哪些配置选项视应用而定。
* 当对端正确接收到该报文后，如果接受该报文携带的所有配置选项，则回应一个**Config-Ack**报文。
#### NCP：IPCP动态地址协商
* 点对点通信的一方设置了IP地址，而另一方则通过协商从对端获取IP地址。
#### Summary of PPP
* one sender, one receiver, one link: easier than broadcast link:
* no Media Access Control
* no need for explicit MAC addressing
* e.g., dialup link, ISDN line
* popular point-to-point DLC protocols:
* PPP (point-to-point protocol)
* HDLC: High level data link control
#### Real Example of PPP
**PPP：RFC1661,1662,1663**\
**对SLIP的改进，Internet的正式标准，支持差错检测、多种协议、允许连接时协商IP地址、允许身份验证...**\
* F：首尾标志7Eh，透明传输采用字符填充
* A：地址字段，永远为FFh，表示所有站点都可以接收
* C：控制字段，**默认为03h**，表示无编号帧
* 协议：指明净荷字段的包类型，支持LCP、NCP、IP、IPX、AppleTalk...
* LCP（链路控制协议），用于建立/拆除数据链路连接、测试连接质量、协商参数...
* NCP（网络控制协议），用于协商网络层选项，如动态分配IP地址
* 物理层：支持MODEM拨号、HDLC位串行线、SONET...
#### PPP non-requirements(不需要做的事)
* no error correction/recovery(不负责纠错)
* 在TCP/IP协议族中，可靠传输由运输层的TCP协议负责，而数据链路层的PPP协议只进行检错。
* 这就是说，**PPP协议是不可靠传输协议**。
* no flow control(没有流量控制)
* 在TCP/IP协议族中，端到端的流量控制由TCP负责，因而链路层的PPP协议就不需要再重复进行流量控制了。
* out of order delivery OK(没有应答序号传输)
* PPP不是可靠传输协议，因此不需要使用帧的序号(许多过去曾经很流行的停止等待协议或连续ARQ协议都是用序号。)
* 在噪声比较大的环境下，如无线网络，则可以使用有序号的工作方式，这样就可以提供可靠传输服务。
* no need to support multi-point links (e.g. polling)
* PPP协议不支持多点线路(即一个主站轮流和链路上的多个从站进行通信)，而只支持点对点的链路通信。
差错、序号等问题放在高层解决，因为网络层的传输中出错的概率很小，所以不花费时间去检查检查。
## Stuffing 填充
### Byte Stuffing（异步方式）
首位标志Flag为 b'01111110，这里利用字节做填充，以 7D 为转义字节，对于中间出现的 7Eh 替换为 7D,5E，对于中间出现的 7D 替换为 7D,5D：\
### Bit Stuffing（同步方式）
连续的5个1后面插入一个0\
## 多路访问协议
* 对于广播信道，需要解决信道分配问题，信道的分配方案有：
* 静态分配：如传统的**FDM或TDM**，如果有N个用户，把带宽或时间分成N份，每个用户静态地占用一个。
* **缺点**是不能有效地处理突发数据，有的用户无通信量时白白浪费资源。
* 动态分配：异步时分多路复用。分为两种：
* **随机访问**（**争用**，contention）：只要有数据，就可直接发送，发生冲突后再采取措施解决冲突。**适用于负载轻的网络，负载重时效率低。**
* **控制访问**：发送站点**必须先获得发送的权利**，再发送数据，不会发生冲突。**在负载重的网络中可获得很高的信道利用率。**主要有**轮转(round-robin)**和**预约(reservation)**两种方式。
### Multiple Access Links and Protocols
* Two types of “links”
* point-to-point (single wire, e.g. PPP, SLIP)
* broadcast (shared wire or medium; e.g. Ethernet, Wavelan, etc.)
### Random Access protocols
* When node has packet to send
* transmit at full channel data rate R.
* no a **priori coordination**(预先的配置) among nodes
* two or more transmitting nodes -> “collision”
* **random access MAC protocol** specifies:
* how to detect collisions
* how to recover from collisions (e.g., via delayed retransmissions)
* Examples of random access MAC protocols:
* slotted ALOHA
* (pure) ALOHA
* CSMA and CSMA/CD
### ALOHA Protocol
* 20世纪70年代，美国夏威夷大学的ALOHA网通过无线广播信道将分散在各个岛屿上的远程终端连接到本部的主机上，是最早采用争用协议的网络。（Aramson）
\
Basic operation:\
1\. All hosts transmit **on one frequency**.\
2\. Central node sends acknowledge **on the other frequency**.\
3\. Detect collisions by **timing out** for ACK.\
4\. Recover from collision by trying after **random delay**.
* Too short -> large number of collision
* Too long -> under-utilization
* 两个版本：
* **纯ALOHA协议**（Pure ALOHA）：每个站点只要有数据就可发送；通过监听信道来发现是否发生冲突；若冲突，则**等待一段随机时间**，再重新发送。
* **时隙ALOHA协议**（Slotted ALOHA）：将信道时间分为**离散的时间片**，每个时间片可以用来发送一个帧。一个站点有数据发送时，必须等到下个时间片的开始才能发送。
#### Pure (Unslotted) Aloha
* 工作原理：每个站只要有数据发送，就可自由发送一个数据帧,但必须收到接收节点的确认信号ACK之后，才能发送下一个数据帧。
* 冲突的发生：两个以上的站同时发送报文分组，由于在时间上重叠从而造成冲突，导致发送失败。
* 冲突的解决方案：发送节点在一个timeout interval内未收到确认信号ACK,自动重发。
* 特点：简单、不需要同步
* 任意时刻直接发送不需要等待
* 发生 collision 的概率增多 (以一帧传输的时间为单位时间)
* pkt sent at t0 collide with other pkts sent in \[t0-1, t0+1]
可以看出需要在发送帧的时间前后1个单位都没有其他数据发送
**推导传输成功率**
可以将数据帧的发送看作三个独立同分布的事件：\
#### Slotted Aloha
* time is divided into equal size slots (= pkt trans. time)
* node with new arriving pkt: transmit at beginning of next slot
* if collision: retransmit pkt in future slots with probability p, until successful.
**Slotted Aloha efficiency**
* Suppose N stations have packets to send
* each transmits in slot with probability p
* prob. successful transmission S is:
* by a specific single node: $$S= p\*(1-p)^{(N-1)}$$
* by any of N nodes: $$S= Prob (only\_one\_transmits)=N*p*(1-p)^{(N-1)}$$
* At best: channel use for useful transmissions 37% of time!
#### Aloha Summary
* Aloha protocol is **very simple, and fairly robust** against failure of a host.
* The protocol is distributed among the hosts.
* Under low-load, we can expect the delay to be small.
* Under high-load, a lot of time is “wasted” sending packets that collide.
**Improving performance:**\
1\. Listen for activity before sending a packet.(发送前监听)\
2\. Detect collisions quickly and stop transmitting.(快速检测碰撞)\
3\. After a collision, pick the random waiting time so as to maximize throughput.(加大吞吐量)
### 随机接入技术：CSMA (Carrier Sense)
* 目的：**载波监听多点访问** CSMA是从ALOHA演变出的一种改进协议。采用了附加的硬件装置，每个站都能**在发送数据前监听信道上其他站是否在发送数据**。如在发送，则此站就暂不发送数据，从而减少了发送冲突的可能。这样就提高了整个系统的吞吐量。
* 根据监测时刻不同，及监测后采用策略的差异，可分为四种:
* 非坚持CSMA(non-persistent CSMA)
* 1-坚持CSMA
* P-坚持CSMA
* CSMA/CD:边听边发
#### 非坚持CSMA
* 非坚持CSMA的工作原理
* (a) 监听到数据"闲"，则发送;
* (b) 监听到数据“忙”，则放弃监听，按一定**退避算法**(random delay)延迟一段时间(这就是“非坚持”的含义），返回(a)。
* 优点：采用随机重传时间减少碰撞概率。
* 缺点：延迟时间内可能会出现通道闲的情况，利用率不高。
#### 坚持CSMA
* 坚持CSMA的工作原理
* 坚持CSMA的特点是在监听到信道忙，仍坚持听下去，一直坚持听到信道空闲为止。
* 有两种不同的策略：
* p-坚持CSMA
* (a) 若信道“闲”，以`0 **以太网使用 CSMA/CD**
* difficult in wireless LANs: receiver shut off while transmitting -> **无线网使用 CSMA/CA**
* CSMA/CD工作流程图\
\
上面的 **强化冲突** 是指 **发出一个瞬间干扰信号**，使得全网都知道冲突的存在，进而停止传输
* CSMA/CS 伪代码
```cpp
A: sense channel, if idle （发送之前侦听线路，空闲发送）
then {
transmit and monitor the channel; （边送边听）
If detect another transmission （碰撞后退随机时间）
then {
abort and send jam signal; （010101交错组成）
update # collisions;
delay as required by exponential backoff algorithm;
goto A
}
else {done with the frame; set collisions to zero}
}
else {wait until ongoing transmission is over and goto A}
```
#### Ethernet’s CSMA/CD (more)
* Jam Signal: make sure all other transmitters are aware of collision
* **Exponential Backoff**: （**截断二进制指数退避**）
* Goal: adapt retransmission attempts to estimated current load
* heavy load: random wait will be longer
* first collision: choose K from {0,1}; delay is `K * 512` bit transmission times
* K=0 --- send instantly
* K=1 --- wait K\*512 bit transmission times
* after second collision: choose K from {0,1,2,3}
* after N collision: choose K from {0,1,2,3,...,2^N-1}
* after ten or more collisions, choose K from {0,1,2,3,4,…,1023}
#### Efficiency of CSMA/CD
* The efficiency (the percentage of useful time) is：
$$S\_max = \frac{1}{1+4.44a}$$
$$a=\frac{T\_{prop}}{T\_{trans}}$$
* Question: you want to increase the bandwidth of the network, but still want to maintain the same efficiency, what do you do?
* Answer: Increase T\_prop as well
### 令牌环网 Token Ring
* Token：特殊的比特模型
* 拓扑结构：点到点链路连接，构成闭合环
* 传输媒体：STP，光纤，速率4/16Mbps；
#### 令牌环的基本原理
* 令牌沿着环旋转
* 当某站要发送时必须等到经过该站的令牌
* 当一个站发送数据时环上不再有令牌
* 帧将在环上运行一周后由发送站清除
* 发送站完成发送后释放令牌
* 该站所发送的帧的前沿已回到本站(已绕环一圈)
* 该站已完成其帧的发送
* 下游的第一个站就能抓住令牌并进行发送
* 逻辑上和物理上均为环型
Example：\
IEEE 802.5协议 令牌环操作\
\
其中T是令牌占有标记位
#### 令牌帧结构字段分析
\
包括：
* 起始、结束定界符（违例差分Manchester码）
* 访问控制字节：
* PPP，RRR：优先级位，和优先级预约位
* T：令牌位，帧类型标识
* 0 表示 令牌为空，可以发送数据，发送数据则将T位改成1然后挂载数据传递下去非令牌帧
* 1 表示 信息/控制帧，查看目的地址是否为自己，是自己则接收数据
* M：监督位，防止无效帧在环路中无限循环
#### 令牌环的优缺点
* 优点
* 在**重负载**条件下**有效而公平**
* 可对媒体访问进行灵活控制
* 提供优先级和保证带宽的服务
* 内置应答
* 发送节点在取回帧时能肯定是否被正确接收
* 缺点
* 在**轻负载**下**效率较低**
* 站必须等待token的到来才能发送
* 需要对token进行维护
* 既不能丢失，也不能重复
[IEEE 802.5 详细介绍](http://www.networksorcery.com/enp/protocol/IEEE8025.htm)
### 令牌总线 Token Bus
* CSMA/CD是一种随机争用的媒体控制方式，具有不可知的最长等待时间。
* 在**工厂自动化生产**中，需要一种具有可知的最长等待时间的媒体访问控制方法。
* 802.4采用**总线型的物理媒体**，**媒体访问控制**方式则采用**令牌环**的方式.。
**和令牌环的区别在于物理上的布局**\
#### 令牌总线IEEE802.4帧格式
* 前导码（Preamble)：用于接收方时钟同步，但最短可以只有1个字节。
* 帧首定界符和帧尾定界符（SD and ED）：用作帧定界标志，用模拟编码符号。
* 帧控制段（FC）：表示帧是数据帧还是控制帧，在控制帧中，该段则说明帧的类型；在数据帧中，则带上该帧的优先级。
* 目的/源地址：接收方/发送方地址，有16位和48位两种，但在同一局域网中所有的地址长度应相同。
* 帧检验序列（FCS）：32位循环冗余码，检验除前导码、SD和ED外的字段。
## 局域网
* 局域网(**LAN**)是在一个小区域范围内对各种数据通信设备实现互连的信息网。特点如下：
* **地理范围有限**，一般局限于单个建筑物内，也可覆盖几个建筑物。如一个企业网，范围在几公里\~几十公里。
* **传输速率比较高，延迟小**，传输速率一般在10Mbps\~1000Mbps，\~10Gbps。
* 传输介质通常为光缆、双绞线；无线局域网流行
* 往往为一个单位/组织来统一管理
### 局域网概述
* 局域网产生的原因
* 70\~80年代，微型机发展迅速，彼此需要相互
* 通信（近距离），共享资源
* 决定局域网特性的主要技术
* 用以传输数据的**传输媒体**
* 用以连接各种设备的**拓扑结构**
* 用以共享资源的**媒体访问控制方法**
* 局域网的典型特性
* 高数据传输速率（10M-1000Mbps，10G）
* 短距离（0.1-10km)
* 低误码率（10^-8-10^-11）
### 局域网的拓扑结构
* 星型（Star）
* 环型（Ring）
* 总线型（Bus）
* 树型（Tree）
### 局域网传输介质
* 同轴电缆
* 双绞线
* 光纤
* 无线
### 局域网中的数据链路层
* 逻辑链路控制子层(LLC)
* 通过提供统一格式,向网络层提供一个接口
* 支持链路的多路访问特性，建立/释放逻辑连接，差错控制，帧序号处理
* **屏蔽**各种802网络的底层差异，如拓扑结构、介质、介质访问控制访问
* 介质访问控制子层(MAC)
* 根据网络的拓扑结构和传输介质，不同的局域网采用不同的介质访问控制方法
* 成帧(各种不同的帧结构)，拆帧，寻址等
* CRC校验
### 典型的LAN帧结构
### LLC的功能（已基本不用）
* 提供三种服务
* 无连接的服务
* 面向连接的服务
* 复用
* 差错控制与流量控制
* 类似HDLC协议，定义了三种格式
* 信息帧
* 监控帧
* 无编号帧
## IEEE802协议
* LLC负责不同的底层协议之间的互联，即从逻辑的层面统一物理差异
* 802.7和802.8还定义了物理层的相关技术
### IEEE802参考模型及协议
* MAC子层用于描述与传输媒介有关的物理特性；
* LLC子层用于描述与传输媒介无关的物理特性。
### 局域网的IEEE 802系列标准
#### 802.3 采用CSMA/CD技术的局域网(以太网)
* ALOHA系统
* ALOHA + 载波监听
* Xerox（Bob Metcalfe、David Boggs) 设计了 2.94Mbps 的采用 CSMA/CD 协议的 **Ethernet**
* Xerox, DEC, Intel共同制定了 10Mbps 的 CSMA/CD 以太网标准(**工业标准**)
* IEEE定义了采用1-坚持型CSMA/CD技术的 802.3 局域网标准，速率从1M到10Mbps，802.3标准与以太网协议略有差别。(**法定标准**)
* CSMA/CD 基本原理
1. 侦听线路
2. 空闲发送
3. 边送边听（**发送最小帧长64bytes的字节未检测到冲突，认为发送成功**）
4. 冲突后退（指数后退算法，回到1）
* CSMA/CD 冲突域
* 为确保发送成功, 一台主机在发送结束之前必须能够检测到冲突
* 最小帧长= 2\*Prop\*传输速率
* Prop=L/0.77c （当时按2500m, 4个中继器计算）
* **10Mbps以太网最小帧长为512bits(64bytes)**
**以太网帧格式**
* Ethernet V2 是事实标准，也称为工业标准。
* IEEE802.3 是法定标准，也称为国际标准。
* Pad为填充位，当传输的数据Data不满46字节的时候填充，在接收端会去掉。
* 以太网的帧最大的大小为 DA+SA+type+Data\_max+CRC=6+6+2+1500+4=1518B。
* 前面的Preamble为前导码，表示有数据要发送。
* SFD是帧开始的表示，表示网络上的主机要开始检测DA是否为自己，是自己则接收数据，不是则丢弃。
**物理地址**
* **物理地址、网卡地址、MAC地址、硬件地址**在以太网中概念相同。
* 用6个字节表示，前三个字节为厂家代号，后三个字节为产品序列，要向OUI(Organization Unique Identifier)注册，以免重复冲突
* e.g.
* AA:00:04 DEC
* 00:00:0C Cisco
* 02:60:8C 3Com
* 08:00:07 Apple
**帧类型**
* 类型域 > 1500 (也就是十六进制的0x05DC)， 即为 EthernetII 帧格式，并且表示的是上层(网络层)使用的协议
* 如 : 0x0800 表示 IP协议, 0x8138 表示 IPX协议, 0x6004表示 Decnet协议
* 否则为IEEE802.3 帧格式，即类型域(也就是IEEE802.3的长度域)小于1500
* 这里也说明IEEE传输的数据长度不超过1500
* 实际上EthernetV2传输的数据长度为46\~1500B，IEEE802.3传输的长度为43\~1497B
详细比较可见：\
[Ethernet\_II帧和802.3\_Ethernet帧格式比较](https://blog.csdn.net/bluelingt/article/details/48970441)\
[Ethernet V2、802.3SAP、802.3SNAP 比较](https://blog.51cto.com/wangxl/1582685)
### 物理层选项与标识方法
由三个字段组成，分别表示：\
1\. 速率，单位 Mb/s\
2\. 基带或宽带\
3\. 每段最大长度，单位 百米 **或** 介质类型(T, F, X)
* T for Twisted 双绞线，工程标准的长度是100m(绝对安全的距离)
* F for Fiber 光纤
* X for 电口
* 最大长度中的2实际长度为185m，2只是写着方便
常见的几种类型：\
\
#### 10Base2/10Base5
* 10BASE2、10BASE5是最早期的**总线型**局域网技术，适合于较小的单位、很少的网点，且价格较便宜。
* 不足:单点故障(一个节点故障影响整段通讯)、扩展困难、可靠性较差。
#### 10BaseT无屏蔽双绞线
* IEEE于1990年推出新规格10BaseT,将共享内建于**集线器(Hub)的内部**，对外连线则采用**星状布线**。
* 网络上任何一段线路出现故障，不会影响到网络上其他使用者。
* 双绞线比传统的同轴电缆轻巧，在办公室中颇受欢迎。
* 缺点是**易受电磁干扰**，驱动距离最远仅为100米。
**集线器**
\
物理层功能(属于物理层不是数据链路层):\
1\. 信号的再生和再定时\
2\. 检测碰撞\
3\. 端口的扩展功能\
4\. 混合连接10Base5与10Base2以太网系统
* 一个口接收到了信号其他所有口输出
**RJ45插头插座**
* 平行线连接方式
* 采用同一种标准进行连接，通常是T-568B，内部不交叉
* 一般而言，平行线用于连接Hub或Switch
* 交叉线连接方式
* 双绞线两头采取不同标准，一端T-568B，另一端T-568A与水晶头进行连接，四对线内部都要交叉
* 用于对等的两个通信设备的直连，因为对等的通信设备的接口定义通常采用同一标准
#### 10BaseF光纤
* 同轴电缆由于电气衰减及电磁干扰，隔离效果较差，使得局域网的距离受到限制。当网络系统较大或需要较大频宽传输信息时，选择以**光纤为主干的网络**。
* 光纤的直径减小到只有一个波长8\~10μm，可使光线一直向前传播，光源一般为激光，称单模光纤。衰减小，传输远，容量大。
* 可以存在多条不同角度入射的光线，直径一般为50\~100 μm ，光源一般为发光二极管，称多模光纤。传输距离短。
* 10Base-F使用标准的62.5/125μm的多模光纤和ST标准连接器。
#### 以太网中传播时延
| 传输媒体 | 电磁波在该媒体中的传播速度 |
| :------: | :-----------------------------: |
| 粗缆(同轴电缆) | 0.77c
(2.31e5 km/s)
|
| 细缆(同轴电缆) | 0.65c
(1.95e5 km/s)
|
| 双绞线 | 0.59c
(1.77e5 km/s)
|
| 光纤 | 0.66c
(1.98e5 km/s)
|
| AUI电缆 | 0.65c
(1.95e5 km/s)
|
#### 10M以太网组网规则(冲突域)
* 允许**5个**网段
* 在信道上只允许**4个**中继器
* 其中**3个**网段可以放置节点
* 另**2个**网段除了中继器链路外，不能有任何节点
* 以上组成**1个**冲突域，最大节点数为1024，最大传输距离为2500米
**共享冲突域的情况**
### 快速以太网(Fast Ethernet)
* IEEE802.3u 协议
* 100BaseT是10BaseT的真正继承者，100BaseT保留了大多数10BaseT的布线规则和CSMA/CD介质访问方式，具有以下特点:
* 从传统10BaseT以太网的升级较容易，投资少，与现有10BaseT网的集成也很简单。
* 众多厂家支持，产品价格相对较低。
* 安装和配置简单，现有的管理工具依然可用。
* 特点：
* 采用CSMA/CD媒体访问控制方式和802.3帧格式，兼容性好，容易布线
* 100BASE-TX采用两对5类双绞线
* 100BASE-T4采用四对3类双绞线
* 网络最大长度250m(10M以太网是2500m，由于速度提高了，为了保持传输的帧的长度不变，需要将传输的距离缩小10倍)
* 缺点:在一个冲突域中传输距离有限。
#### 100M以太网传输介质
#### 100M以太网中继器组网规则
* 对于I类中继器，只允许连接1个中继器，每段最长100米
* I类中继器:支持不同编码的介质，延迟:0.7us
* 对于II类中继器，最多允许2个中继器，可以由两段各100米长的链路及5米长的中继器链路 (缺省)
* II类中继器:只支持相同编码的介质，延迟:0.46us
* 中继器是Hub，但是可以接交换机Switch
#### 快速以太网Hub组网跨距
#### 快速以太网光纤(MMF)组网跨距
#### FastEthernet组网可能潜在的问题
* **共享的网络直径太大**
* 在3类UTP上传输100BaseTx
* 在只有2对线的UTP上传输 100BaseT4
* 100BaseT4、100BaseTx和 10BaseTx端口不匹配
#### 共享型以太网存在的问题
* **受CSMA/CD约束**，每个站点平均带宽为系统带宽/n，n为该冲突域的站点数
* **每一时刻只能要求一个发送者**，在站点数增加到一定程度时，**网络效率极低**
* **冲突域的覆盖范围有限**
* 安全性**极差**
## 网桥
* 网桥:是一种**数据链路层**的网络设备，具有**存储-转发装置**，根据帧的目的MAC地址，通过查找地址表(转发表)进行转发。(有CPU、内存)
* 连接网段构成具有**多个冲突域的系统**，从而实现系统地理范围的扩展
* 把一个冲突域分割成多个冲突域，从而**实现系统带宽的扩展**，在一个网络中运行多机同时发送
* 具有容错功能，支持**802.1D标准(STP)**
* 过滤信息、提高网络安全
* 构成**一个广播域**
### 冲突域和广播域
简单来说：冲突域就是能否两台机器同时发送数据
### 网桥的工作原理
\
三个功能：
* **地址学习**
* **帧转发**
* **消除拓扑循环**
#### MAC地址表
* 多口的网桥=交换机
* 交换机内部都有一张MAC地址表
* MAC地址是唯一标识主机的，在某些地方又称为 **物理地址**
**地址学习**：
* 最初交换机的MAC地址表为空
* **逆向学习法** : 若收到的帧源地址不在表中，则插入到表中，作为以后转发的路径。
* **泛洪法** : 对于目的MAC地址，如地址表没有记录，数据帧从其它所有端口转发出去(除入口之外)，识别数据帧的源MAC地址，学习MAC地址和端口对应关系，并记录下来。
**地址转发**：
* 通过MAC地址表实现数据帧的**单点转发**
### 交换机(Switch)
* 在原理上相当于多口的网桥
* **网桥**通常利用**软件**进行交换，而**交换机**则用**硬件**进行交换，两者方法:**存储转发、直通式**
特点：\
1\. 每个端口都占带宽\
2\. 系统最大带宽可达端口带宽的N倍\
3\. 支持全双工，可不受CSMA/CD的约束，用Switch串接，在理论上距离是无限的
**直通交换方式**是以太网交换机可以在各端口间交换数据。它在输入端口检测到一个 数据包(**帧**)时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成 相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。\
通常情况下，\*\*直通交换方式只检查数据包的包头即前14个字节=Preamble的7字节+SFD的1字节+目的地址的6字节。
### 全双工以太网
* 利用2对线**同时发送和接收**帧，不受CSMA/CD限制。
* 传输距离较半双工模式要长。
* 在链路的两个方向上同时进行收发操作，从而使其**链路的总带宽提高到一倍。**
* 基于Switch技术，要求**点对点**满足，接Hub不行。
* 不需要载波侦听，不需要冲突监测。**不受以太网冲突域的限制。**
* 提高网络性能、扩展网络距离。
#### Switch+Hub组网跨距
#### 交换网络性能问题
\
**Multicast, broadcast, unknown destination** 报文成为广播域网络的最大问题。
#### 广播风暴
\
特点：
* 广播报文可能会消耗掉整个带宽资源。
* 任何设备都需要接受广播报文，解开后提交给主机，消耗每台主机的资源，而且不安全。
#### 解决方法: 流量本地化
* **LAN 广播**可以用路由器/多层交换机进行隔离
* 多层交换机:L3/L4 交换机
* LAN广播可以用交换机通过Vlan划分，进行隔离
* 这里交换机是L2交换机，**VLAN是数据链路层概念**
### VLAN(Virtual LAN)
* 在使用交换设备的网络中，使用VLAN技术能有效地把用户的分为若干个**虚拟工作组**，而不用考虑地理分布。
#### VLAN的标准
* 1996年3月，IEEE802.1因特网工作分会完成了VLAN标准的初步研究 ，制定了IEEE802.1Q/P
* VLAN的**帧标记的标准格式**由**802.1Q**协议规定
* **802.1p**协议规定了**多媒体应用**中所要求的业务量等级及其控制规程，还提供了**动态控制组播组的通信功能**。
#### LAN和VLAN的区别
* LAN和VLAN的主要区别和优势有:
* VLAN工作在**ISO模型的第2层**
* VLAN提供**控制网络广播**的方法
* 网络管理员可以**把用户划入VLAN**，管理方便
* VLAN可以通过隔离通信域而**提高网络的安全性**
* 通过使用VLAN技术，可以按交换机端口、MAC地址、协议进行**逻辑分组**。
* 可以把一个交换机或多个相连的交换机的端口和用户划分为不同的组，VLAN可以跨越一栋建筑、多个互连的建筑，甚至城域网。
**二层交换机和三层交换机的区别**
* **不同VLAN就是不同的广播域**，互联需要网络层设备路由器。
* 不同VLAN之间的连接靠第3层交换。
* L2交换机需要外接路由器进行互联。
* L3交换机就是带路由功能的交换机。
#### VLAN划分方法
* 按交换机的端口划分
* 可以通过配置的形式明确指定端口所属的VLAN。
* 特点:配置简单、含义明确、与实际联系紧密，应用广泛。目前用的多是这种方式。
* 
* 按MAC地址划分
* 通过MAC地址指定端口所属的VLAN，需要服务器和客户端的支持;和转发表配合可实现VLAN-端口的转换。
* 特点:安全性高、配置比较烦琐，应用较少。
* 
* 按数据类型划分
* 按组播地址划分
* 以上几种方式的组合
#### 配置静态 VLAN
#### 帧中的VLAN标记
* 跨交换机之间的通讯需要引入标记tag:IEEE 的802.1q.
#### 带标记帧的传输过程
\
**对端交换机**根据802.1Q中的**VLANID**来区分正确的VLAN,然后**向该VLAN**包含的端口转发\
e.g. 截获的报文中含有 IEEE802.1q字段，其中包含的VLANID=2：\
### 以太网的自动协商
* 工作于点到点的链路上，无全网协商概念
* 协商在链路初始化时进行
* 协商信令与普通数据是分开的
* 每个设备向其他设备“通告”其功能，并按照公共功能集合选择合适的配置
* 不能协商站点间的布线类型
* 不支持非以太网系统
#### 自动协商优先级
| 优先级 | 物理规格 | 连通 |
| :-: | :-------------: | :-: |
| 1 | 1000BaseT | 全双工 |
| 2 | 1000BaseT | 半双工 |
| 3 | 100BaseT2(已经不用) | 全双工 |
| 4 | 100BaseTx | 全双工 |
| 5 | 100BaseT2(已经不用) | 半双工 |
| 6 | 100BaseT4(已经不用) | 半双工 |
| 7 | 100BaseTx | 半双工 |
| 8 | 10BaseT | 全双工 |
| 9 | 10BaseT | 半双工 |
### 链路冗余
\
1\. 为了提高冗错性，交换机往往通过多条链路连接上层交换机，假设其中一条链路断了，可以有另外一条备用。\
2\. 如果交换机接收到一个广播包，则向所有两条上行链路上转发，核心层交换机接收到以后，互相转发，这样最终形成环路，带来网络风暴。
### 生成树协议(STP)
* 生成树协议(spanning-tree protocol)由IEEE802.1d标准定义。
* 生成树协议的作用是为了提供冗余链路，解决**网络环路**问题。
* 生成树协议通过SPA(生成树算法)生成一个**没有环路**的网络，当主要链路出现故障时，能够**自动切换**到备份链路，保证网络的正常通信。
* STP利用**BPDU(Bridge Protocol Data Unit，网桥协议数据单元)**在交换机之间交流**网络拓扑信息**。
* STP BPDU是一种二层协议数据单元。目的MAC是多播地址01-80-c2-00-00-00(Bridge\_group\_addr)，所有支持STP协议的交换机都会接受并处理收到的BPDU。
生成步骤：\
Embed a tree that provides a single unique path to each destination: 1) Select a single bridge as a root bridge 选择一个序列号(可设置)最小的网桥作为根 1) Each bridge calculates the distance of the shortest path to the root bridge 2) Each LAN identifies a designated bridge, the bridge closest to the root. It will forward packets to the root. 3) Each bridge determines a root port, which will be used to send packets to the root 4) Identify the ports that form the spanning tree
**转发过程**\
\
即保留某些支路设置状态为Blocking，平时不开通以防出现环路，在RP之间的线路出现问题的时候将这些支路作为备份开通，即Blocking->Forwarding。
### 链路聚合(Truck)
* 链路聚合，也称trunk，交换机把**一组链路聚合**起来，使得这些链路像一条链路——**聚合协议**。**(802.3ad)**
* 这些端口称为**聚合端口**。
* 用于提高网络容量和可用性
* 该标准仅应用于**全双工以太网链路**
• 所有链路必须以**同一速率**工作，带宽翻倍
### 网桥(交换机)小结
* 工作在**数据链路层**(主要是MAC)，检查帧的MAC地址进行转发，也称透明网桥。
* **隔离冲突域，扩大网络跨距**
* **过滤**通信量，减轻局域网负荷，一定程度提高安全性
* 具有**自学习功能**(逆向学习法，backward learning)，根据**源地址**及端口确定地址表。
* 为解决环路问题，802.1d网桥标准中，制定了一个在每个网桥上运行的生成树协议。提供可靠性。
* 用网桥连接的网络**构成一个广播域**。
## Gigabit Ethernet 千兆以太网
* 主干采用千兆以太网的好处:千兆位以太网(半双工)将提供 10 倍于快速以太网的性能并**与现有的 10/100 以太网兼容**:
* 最大帧长1518B，最小64B，重试上限16次，后退上限10次，Jam信号(告知冲突的信号)32b，帧间隙96b。
* 可以支持虚拟网VLAN标准 802.1Q 以及优先级标准 802.1p。
* 千兆以太网已成为构成局域网主干的主流技术。
**问题**：
> 在采用CSMA/CD的MAC子层中，碰撞检测时间与网络的最大距离成正比，在 10BASE-5中，最大距离为**2500m**，间隙时间为51.2微秒，最小帧长为512比特。在100BASE-T中，最大距离为**250m**，帧格式不变，即间隙时间为5.12微秒。按此规律，千兆以太网的最大距离为**25m**。
**解决方案**：
* 半双工方式 (CSMA/CD)
* **载波扩展(carrier extension)**
* 使最小帧长仍保持**64bytes** , 通过填充一些特殊字符，使MAC帧的发送长度(争用期)增大为**512bytes**(4096b) ,最大网络跨距可达**200m**.
* **帧突发功能(frame bursting)**
* 很多短帧时，第一帧采用**载波扩展(填充)**，随后在一定时间内连续发送多个MAC短帧，最大突发长度为8192字节。
* 全双工(不使用CSMA/CD)
### 千兆以太网跨距(最大距离)
* **IEEE802.3z** (8B/6T 1000Base-X)
* 1000BaseLX 波长:860\~1270 μm
* MMF 62.5μm 550M
* MMF 50μm 550M
* SMF 10μm 5KM
* 1000BaseSX 波长:770\~860 μm
* MMF 62.5μm 275M
* MMF 50 μm 550M
* 1000BaseCX
* TW型 STP 25M
* **IEEE802.3ab**
* 1000BaseT 5类 UTP (4 pairs) 100M
## 802.3ae: 万兆以太网10G
* **兼容**802.3标准中定义的**最小和最大以太网帧长度**
* 仅支持**全双工方式**：速度太快半双工无法实现
* 使用**点对点链路**和结构化布线组建星型物理结构的局域网
* **支持802.3ad**链路汇聚协议
* 定义两种PHYs(物理层规范) \* LAN(局域网) PHY和 WAN(广域网) PHY
* 定义将MAC/PLS的数据传送速率对应到WAN PHY数 据传送速率的适配机制
* 定义支持特定物理介质相关接口(PMD)的物理层 规范，包括多模光纤和单模光纤以及相应传送距离
## IEEE802.3以太网标准总结(用于查表)
数字表示传输速度，单位是“Mbps”，最后的一个数字表示单段网线长度(基准单位是10m)，Base表示“基带”的意思，Broad 代表“带宽”。
* **10Base-5**使用粗同轴电缆，最大网段长度为500m，基带传输方法。
* **10Base-2**使用细同轴电缆，最大网段长度为185m，基带传输方法。
* **10Base-T**使用双绞线电缆，最大网段长度为100m。
* **1Base-5**使用双绞线电缆，最大网段长度为500m，传输速度为 1Mbps。
* **10Broad-36**使用同轴电缆(RG-59/U CATV)，最大网段长度为 3600m，是一种宽带传输方式。
* **10Base-F**使用光纤传输介质，传输速度为10Mbps。
* **100BASE-TX**是一种使用5类数据级无屏蔽双绞线或屏蔽双绞线的
快速以太网技术。
* **100BASE-FX**是一种使用光缆的快速以太网技术，可使用单模和多模光纤(62.5μm和125μm)，多模光纤连接的最大距离为550m。 单模光纤连接的最大距离为3000m。
* **100BASE-T4**是一种可使用3,4,5类无屏蔽双绞线或屏蔽双绞线的快速以太网技术。
* **1000BASE-SX**系列采用低成本短波的CD(compact disc，光盘激光器)或者VCSEL(Vertical Cavity Surface Emitting Laser，垂直腔体表面发光激光器)发送器。
* **1000BASE-LX**系列则使用相对昂贵的长波激光器。
* **1000BASE-CX**系列则打算在配线间使用短跳线电缆把高性能服务器和高速外围设备连接起来。
## 高速局域网技术FDDI
FDDI (Fiber Distributed Data Interface)\
特征
* 使用多模光纤作为传输介质
* MAC协议与 Token Ring 类似
* 100M的速率
* 采用4B5B编码方法
* 32中组合中的16种表示数据，3种表示定界符，2种表示控制，3种表示硬件信号，8种保留。
* 最大距离200公里
* 最多1000个站点
* 通常作为连接LAN的主干网络
逻辑上是环路，而且还支持双环，即一个环路上的某一段断开可以通过内环和外环的连接形成新的环状网络：\
\
但是由于现在以太网的普及，Ethernet到FDDI Ring之间还需要一个Bridge进行网络的转换，成本高，所以FDDI已经不用了。
## 异步传输模式ATM
* ATM(异步传输模式)，是一种**面向连接**的快速分组交换技术，采用**统计时分复用 STDM 方式**，建立在硬件交换的基础上。
* 面向连接就是需要预先建立连接和断开连接。
* ATM将信息分成固定大小的**信元cell**，**长度53字节**，**3个byte为信头**，**48个byte为静荷**。
* 类似于分组交换，但**不使用分组交换的差错校检功能以提高速度**。
* 它兼有分组交换的可调带宽和高速度，以及电路和帧交换固有的低时延。
* 但因为成本高且维护困难也不再使用。
## 无线局域网IEEE802.11
* IEEE 802.11 是一个有固定基础设施的**无线局域网**的国际标准。
* IEEE 802.11 是个相当复杂的标准。但简单地说，**802.11 就是无线以太网的标准**:
* 它使用星形拓扑，其中心叫做 **接入点 AP** (Access Point)
* 在MAC层使用 **CSMA/CA** 协议
* 凡使用 802.11 系列协议的局域网又称为 **Wi-Fi** Wireless-Fidelity，意思是“无线保真度”。
### 几种常用的 802.11 无线局域网
| 标准 | 频段 | 数据速率 | 物理层 | 优缺点 |
| :-----------------: | :---------: | :----------: | :-------: | :----------------------------------------------------: |
| 802.11b (1999年) | 2.4 GHz | 最高11 Mbit/s | 扩频 | 最高数据率较低，价格最低，信号传播距离最远，且不易受阻碍。 |
| 802.11a (1999年) | 5 GHz | 最高54 Mbit/s | OFDM | 最高数据率较高，支持更多用户同时上网，价格最高，信号传播距离 较短，且易受阻碍。 |
| 802.11g (2003年) | 2.4 GHz | 最高54 Mbit/s | OFDM | 最高数据率较高，支持更多用户同时上网，信号传播距离最远，且不 易受阻碍，价格比802.11b贵。 |
| **802.11n** (2009年) | 2.4 / 5 GHz | 最高600 Mbit/s | MIMO OFDM | 使用多个发射和接收天线达到更高 的数据传输率。当使用双倍带宽(40 MHz)时速率可达600 Mbit/s。 |
### CSMA/CA 协议
* 无线局域网不能简单地搬用CSMA/CD协议。这里主要有两个原因:
* “碰撞检测”要求一个站点在发送本站数据的同时，还必须不间断地检测信道，但接收到的信号强度往往会远远小于发送信号的强度，边送边听的设计成本较高，在无线局域网的设备中要实现这种功能就**花费过大**。
* 即使能够实现碰撞检测的功能，并且在发送数据时检测到信道是空闲的时候，在**接收端仍然有可能发生碰撞**。
### 无线局域网(Wireless LAN)问题
* WLAN设备中要实现边送边听的全双工功能**花费过大**。各个站点发出的**信号范围有限**，因此会造成:
* **隐藏站点问题**(hidden station problem):图(a)中，A向B发送时，由于**C听不到误以为可发送数据**，造成**B接收失败**，而**A无法监测到**。在发送数据时检测到信道是空闲的，在接收端仍然有可能发生冲突。
* 
* **暴露站点问题**(exposed station problem):图(b)中，B向A发送时，**C听到信道忙误认为它不能向D发送数据**，实际上并不影响A和D两站的接收。应**同时允许多点同时通信**。
* 
### CSMA with Collision Avoidance(CSMA/CA)
* 无线局域网不能使用 CSMA/CD，而只能使用改进的 CSMA 协议。
* **CSMA/CA**(**避免冲突**的CSMA协议)是WLAN采用的介质访问控制协议，其相应的国际标准为IEEE 802.11。
* 改进的办法是把 CSMA 增加一个**碰撞避免** CA(Collision Avoidance)功能。
* 802.11 就使用 CSMA/CA 协议，同时还增加使用停止等待协议。
#### CSMA/CA Protocol
* 送出数据前，监听媒体状态，如信道空闲，**再等待一段随机的时间**后依然没有人使用，才送出数据。
* 发送方先激发(RTS)接收方发送一个短帧(CTS)，使接收方周围的站点不会在即将到来的数据帧期间发送数据而导致冲突 (避免冲突)。
* 当多个站点同时向一个站点激发时仍会发生冲突，在**预定时间**内没有收到CTS的**发送方采用二进制指数退避算法**，在等待一随机时间后再次重试。
* CSMA/CA 的 **二进制指数退避算法** 和之前的有区别。
* CSMA/CA: 信道预约
* 发送站: 发出短的 RTS幀 (request to send) 预约信道
* 接收站: 应答短的 CTS幀 (clear to send) 同意预约
* CTS为发送站保留信道,起了通知其它(可能隐蔽的)站点的效果
* 避免了隐蔽站点造成的冲突
**CSMA/CA协议的基本流程图**
**CSMA/CA算法归纳**
1\) 若站点最初有数据要发送(而不是发送不成功再进行重传)，且检测到信道空闲，在等待时间DIFS后，就发送整个数据帧。\
2\) 否则，站点就要等检测到信道空闲并经过时间DIFS后，执行CSMA/CA协议的退避算法，启动退避计数器。在退避计数器减少到零之前，一旦检测到信道忙，就冻结退避计时器。一旦信道空 闲，退避计时器就进行倒计时。\
3\) 当退避计时器时间减少到零时(这时信道只可能是空闲的)，站点就发送整个的帧并等待确认。\
4\) 发送站若收到确认，就知道已发送的帧被目的站正确收到了。这时如果要发送第二帧，就要从上面的步骤(2)开始，执行 CSMA/CA协议的退避算法，随机选定一段退避时间。若源站在规 定时间内没有收到确认帧ACK(由重传计时器控制这段时间)，就 必须重传此帧(再次使用CSMA/CA协议争用接入信道)，直到收 到确认为止，或者经过若干次的重传失败后放弃发送。
### 802.11 局域网的 MAC 帧
* 802.11帧共有三种类型 : **控制帧、数据帧和管理帧**
* 帧控制格式
* RTS - 1011
* CTS - 1100
* ACK - 1101
* 四个地址(这里可能说不明白具体看下面例子)
* 地址1: AP receive this frame——目的地址
* 地址2: AP transmit this frame——源地址
* 地址3: 指向的路由器的地址
* 地址4: used for ad hoc mode——自主网络，主要在军队中单兵作战，通过几个节点形成自主网络
## Practice
> 某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10MBPS,主机甲和主机乙之间的距离为2KM，信 号传播速度是200000KM/S.请回答下列问题，并给出计算过程。请求出:\
> (1) 若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经多长时间?最长需经过多长时间?(假设主机甲和主机乙发送数据过程中，其他主机不发送数据)
>
> * 1km/200000km/s\*2=1e-5s
> * 2倍
>
> (2) 若网络不存在任何冲突与差错，主机甲总是以标准 的最长以大网数据锁(1518字节)向主机乙发送数据，主机乙每成功收到一个数据锁后，立即发送下一个数据锁，此时主机甲的有效数据传输速率是多少?(不考虑以太网锁的前导码)
> * 发送1518B的数据帧所用时间(传输延迟) =1518×8 bits/10 Mbps=1214.4μs；（1分）
> * 发送64B的确认帧所用时间(传输延迟) =64×8bits/10Mbps=51.2μs；（1分）
> * 主机甲从发送数据帧开始到收完确认帧为止的时间记为T总，则T总=1214.4+51.2+2×10=1285.6 μs；（1分）
> * 在1285.6μs内发送的有效数据长度=1518B-18B=1500B=12000bits；（1分）
> * 因此，主机甲的有效数据传输速率=12000bits/1285.6μs ≈9.33Mbps。（1分）
> 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要( )。
>
> * 最短帧长=2*L*10^9(b/s)÷200 000000m/s=10\*L(bit)
> * 帧长减少800bit则距离减少800/10=80m
> 对于100Mbps的以太网交换机，当输出端口无排队，以直通交换方式转发一个以太网帧(不包括前导码)时，引入的转发延迟至少是( )。\
> A.0us B.0.48us C.5.12us D.121.44us
由于不需要考虑前导码，只需要检查目的地址的6B\*\*，所以最短的传输延迟是0.48us。
> 2014年全国统考34题:某以太网拓扑及交换机 当前转发表如下图所示，主机00-e1-d5-00-23-a1向 主机00-e1-d5-00-23-c1发送1个数据帧，主机00- e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00- 23-a1发送1个确认帧，交换机对这两个帧的转发 端口分别是( )。\
> \
> A. {3}和{1} B.{2,3}和{1} C.{2,3}和{1,2} D.{1,2,3}和{1}
第一次发送时因为没有目标地址所以采用泛洪法——发送给除自己以外的所有主机\
交换机从源地址学习到了第一台主机所以第二次发送回程时地址表里面已经有主机MAC，所以对点发送\
所以选B
> 36.下列关于CSMA/CD 协议的叙述中，错误的是()\
> A.边发送数据帧，边检测是否发生冲突\
> B.适用于无线网络，以实现无线链路共享\
> C.需要根据网络跨距和数据传输速率限定最小帧长\
> D.当信号传播延迟趋近0 时，信道利用率趋近100%
显然，无线网络使用的是CSMA/CA，所以选B
> 37.下列关于交换机的叙述中，正确的是 ()\
> A.以太网交换机本质上是一种多端口网桥 B.通过交换机互连的一组工作站构成一个冲突域\
> C.交换机每个端口所连网络构成一个独立的广播域\
> D.以太网交换机可实现采用不同网络层协议的网络互联
A直接正确\
B是构成广播域不是冲突域\
C是构成独立的冲突域\
D：交换机主要用来实现多个局域网的互联，但是交换机工作在**数据链路层**，互联的局域网的物理层和数据链路层可以运行不同的协议，而数据链路层以上的高层必须采用相同的协议
> 36.下列选项中，对正确接收到的数据帧进行确认的MAC协议是\
> A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA
需要确认的只有 CSMA/CA ，其有ACK帧
## Reference
1. [tech-faq | PPP (Point-to-Point Protocol)](https://www.tech-faq.com/ppp.html)
2. [csdn | 点对点协议PPP的特点](https://blog.csdn.net/cainv89/article/details/50612718/)
3. [IEEE 802.5 详细介绍](http://www.networksorcery.com/enp/protocol/IEEE8025.htm)
4. [Ethernet\_II帧和802.3\_Ethernet帧格式比较](https://blog.csdn.net/bluelingt/article/details/48970441)
5. [Ethernet V2、802.3SAP、802.3SNAP 比较](https://blog.51cto.com/wangxl/1582685)
6. [802.11帧格式](https://www.cnblogs.com/shwang/p/12162692.html)