计网五层教学模型中链路层的基础知识
本文仅简单介绍教学用五层模型中链路层的部分知识点，包括组帧方式、差错控制、流量控制、介质访问控制、局域网等
计网五层教学模型中链路层的基础知识
一、关于链路层
- 在教学用五层模型中，数据链路层将上层网络层的数组分组拆分再封装为数据帧，基于物理层提供的传输比特的物理链路，实现以数据帧为单位传输的、无差错的逻辑链路
二、封装成帧
2.1 主要问题
- 数据链路层将上层网络层的数组分组拆分再封装为数据帧的过程就称为组帧/封装成帧，其要解决的主要问题如下
- 帧定界：让接收方确定每个帧之间的边界（物理层以比特流传输链路层的数据帧，帧定界做的就是从比特流中区分出每个独立的数据帧），具体实现方法为
- 为数据分组（SDU）的头尾添加控制信息（PCI）作为分隔，封装成帧（PDU）
- 此外还可能会对SDU本身进行某些修改，例如组帧中添加的信息
- 透明传输：接收方必须能够去除帧定界时附加的额外信息（包括头尾PCI，以及SDU中的帧定界相关修改；但注意用于差错控制的校验码并不包含在内，其不是透明传输要求要还原的），将链路层的PDU还原为该PDU的原始SDU（即传输层的PDU）
- 帧定界：让接收方确定每个帧之间的边界（物理层以比特流传输链路层的数据帧，帧定界做的就是从比特流中区分出每个独立的数据帧），具体实现方法为
2.2 组帧方法
2.2.1 字符计数法
- 在每帧的SDU开头用一个定长的计数字段表示帧的总长度（包含该计数字段）
- 缺点是若任意一帧的计数字段中的任意一个比特出错，就会导致其后续的所有帧都无法被正确地定界，整体健壮性差
2.2.2 字节填充法
- 在每帧的SDU头尾分别附加控制字符SOH和EOT作为每帧之间的间隔（属于ASCII编码，SOH即Start Of Header，EOT即End Of Transmission），但是若SDU数据内容中恰好包含这两种控制字符编码，就会导致混淆
- 可以通过在SOH和EOT前添加转义字符ESC的方式避免误判，当解析时遇到转义字符紧跟的这两个控制字符时会将其保留作为数据部分，同时会将转义字符ESC剔除（实现透明传输）
- 若SDU数据部分中包含转义字符，其自身会被直接剔除，所以若需要在数据内容中包含转义字符本身，需要在转义字符ESC前再加一个转义字符ESC
2.2.3 零比特填充法
- 以一个特殊比特串（表示帧的开始或结束）间隔所有SDU，这和字节填充法类似，遇到的问题也一样（SDU内容中可能出现该特殊比特串），但解决方法不同
- 特殊字符串为
01111110形式，中间有连续的$6$个1编码，我们只需保证内容中不会出现连续的$6$个1即可，如下的方法处理效率高，应用于链路层协议HDLC和PPP之中- 接收方需对SDU数据部分进行处理：每遇到连续的$5$个
1就在其后添上一个0编码 - 接收方需对SDU数据部分进行逆处理：每遇到连续的$5$个
1，若其后是0，就删去该0编码（实现透明传输）；若其后是1，则可能遇到了特殊比特串
- 接收方需对SDU数据部分进行处理：每遇到连续的$5$个
2.2.4 违规编码法
- 基于曼彻斯特编码的每个周期的中间必须发生跳变的规定，在每帧的SDU头尾添加一周期的不跳变的信号，以违反曼彻斯特编码，起到标识头尾的作用
三、差错控制
差错控制的目标是发现并解决一个数据帧内部的位错（若需重传帧，则相当于处理帧错误中的帧丢失问题，这属于可靠传输的处理范畴）
3.1 检错编码
接收方发现比特位错后丢弃帧，并通知发送方让其重传帧（奇偶校验只能检测出是否出现了错误，而无法纠正错误，故必须通知重传帧；而CRC除了能检错和通知重传帧外，还可在特定情况下直接纠正错误）
3.1.1 奇偶校验码
3.1.1.1 定义结构
- 数据发送方将原编码转换为奇偶校验码（增加冗余校验位）后传递给接收方，后者通过校验码进行检错（发送方和接收方需要共同约定使用奇校验还是偶校验）
- 奇校验码：整个校验码（校验位+有效信息位）中的
1编码个数为奇数 - 偶校验码：整个校验码（校验位+有效信息位）中的
1编码个数为偶数
- 奇校验码：整个校验码（校验位+有效信息位）中的
3.1.1.2 校验检错
- 偶校验位的计算以及偶校验检测均可以直接通过异或运算完成（奇校验则需用上除异或门外的其它门元件），其硬件实现更为简单，因此在现实应用中偶校验更为常用
- 求偶校验位：发送方将原始有效信息位编码逐位异或，所得结果即偶校验位
- 偶校验检测：接收方将奇偶校验码整体（偶校验位+有效信息位）逐位异或
- 若结果为
1，则说明一定出错，因为因为偶校验位由有效信息位异或得来，偶校验位自己与自己异或的结果理论上必然为0（另一个角度，偶数个1以及可能的若干0之间异或的结果必然为0），结果为1则说明要么有效信息位出错了，要么偶校验位本身出错了，反正肯定错了，需要进行重传 - 若结果为
0，则说明可能正确，因为结果为0是传输正确的必要不充分条件，因为有可能出现多位错误正好使得抵消（所以偶校验无法检测出偶数个位错，奇校验同样无法检测出偶数个错误）
- 若结果为
3.1.2 循环冗余校验码
3.1.2.1 定义结构
- 循环冗余校验（CRC, Cyclic Redundancy Check）码由
K个原始信息位+R个校验位组成- 校验位是由信息位左移R位后作为被除数，通过特殊的除法（模二除法）除以约定的除数所得的共
R位的（具有特殊意义的）余数 - 该余数与普通除法计算所得的余数在数值大小上不同（除非巧合），因为此处仅关注其用于校验的意义，而不关注普通算数除法所得的数值意义
- 校验位是由信息位左移R位后作为被除数，通过特殊的除法（模二除法）除以约定的除数所得的共
- 对于给定的信息位，需给定生成多项式才能确定该信息位对应的CRC编码
- 通过生成多项式得出
R的大小（余数编码位数即整数R的大小等于生成多项式的最高次幂项）、约定的除数的编码（约定的除数等于生成多项式的各次幂项的系数拼接而成，$n$次幂项若存在如$x^n$则算1、不存在的如$0\cdot x^n$则算0） - 结合信息位编码、
R的大小、除数编码，由模二除计算出余数编码作为校验位（在原始信息位的末尾添上R个0编码，相当于左移R位，作为被除数，模二除以上述得到的约定的除数即可得到余数），组合原信息位编码和校验位编码即可得到CRC编码
- 通过生成多项式得出
- 模二除法（Modulo-2 Division）与普通除法在运算过程和对运算结果的定义上均不同，其具体的运算规则参考此博客
- 运算过程：模二除只需用到异或运算，相当于是牺牲了普通除法的数值意义，而换取通信校验过程中更快的运算速度、更简单的硬件实现
- 运算结果：对同样的被除数和除数使用模二除法和普通除法，所得的商和余数意义不同、数值一般也不同
3.1.2.2 校验检错
- 接收方将收到的CRC码除以约定的除数后（发送方和接收方必须约定好生成多项式，因为除数由该多项式所得）得到
R比特的余数（比除数固定少一比特位）- 若余数为
0...0则可能正确（仍存在会漏检的特殊情况），CRC能确保通过判断余数是否为0...0正确检测出的错误情况如下- 单比特错误（一定能检测出）
- 双比特错误（若生成多项式包含至少三项，一定能检测到）
- 奇数个错误（若生成多项式能被$x+1$整除，一定能检测到）
- 突发错误（即连续比特错误，若错误长度$\leq R$，一定能检测到）
- 若余数不为
0...0则说明一定出错了，需进行重传或纠错（下述纠错方法理论上可行但限制较多，实际应用中大都只使用CRC进行检错）- 若只有$1$比特位出错，且当CRC码长度$K+R$在$2^R-1$内时，可以根据$2^R$种不同的余数情况推断出具体哪一比特位出错了，此时可以直接进行纠错
- 若存在多个比特位出错的情况，或CRC码长度$K+R$超过了$2^R-1$，则无法准确定位出错的地方，此时需要重传帧
- 若余数为
3.2 纠错编码
由接收方发现比特位错误，并直接纠正，而无需重传帧
3.2.1 海明校验码
3.2.1.1 定义结构
- 海明校验码在偶校验码基础上，使用更长的多个校验位携带更多状态信息，以帮助具体判断错误的位置，假设有效信息位共$n$比特，冗余校验位共$k$比特，则编码总长为$n+k$
- 校验位能表示$2^k$种状态，由于我们需要准确定位$(n+k)$比特中的位错，则$k$的大小需满足$2^k\geq n+k+1$（假设只可能出现一比特错误），其中$1$代表正确无误的那个状态
- 海明编码中的校验位并非连续放在信息位的一端，而是按照一定分布嵌入的
- 用$P_i(1\leq i\leq k)$表示校验位、$D_j(1\leq j\leq n)$表示信息位、$H_x(1\leq x\leq n+k)$表示二者组成的整体编码（即海明编码）的各比特位
- 将每个$P_i$放在海明编码的第$2^{i-1}$位即$H_{x=2^{i-1}}$位处，而每个$D_i$则放到其余位置，每$1$比特的$P_i$分别对一组若干$D_j$负责，作为后者的$1$比特偶校验位，所以$n$比特的信息码相当于整体被分为了$k$个分组，每个校验位$P_i$分别负责一个分组的偶校验（每个$D_j$会被划入不同的分组内，分别由组内的偶校验进行差错控制）
- 确定好$P_i$的分布位置后，就需要确定每比特$P_i$（即其所负责的分组的偶校验位）的值，为此我们需要确定每个$P_i$所负责的$D_j$是哪些，后者的求法被定义为如下方式
- 将$D_j$对应的$H_x$的十进制脚标$x$转换为$k$位二进制编码（由于$x+1<2^k$，所以$k$位的二进制数一定能表示完所有的$H_x$，所以每个$H_x$转为的二进制数都可统一位数为$k$，左侧缺位的以$0$填充）
- 如下图所示逐行将这些二进制编码排列，然后从右向左取竖列，其中编码为$1$的被纳入校验码$P_i$的偶校验分组，$P_i$的值由这些对应位的$H_x$即$D_j$的值逐位异或求得（即前文求偶校验编码的方法）
3.2.1.2 检错纠错
- 此时海明码拥有$1$比特位的纠错能力和$1$比特位的检错能力
- 其检错方法和偶校验一样，将$P_i$偶校验位和其所管理分组内的比特逐位异或，若所有$k$组的结果均为
0则说明在检错范围内，该编码无错（除非超出检错能力范围） - 否则说明存在错误，将这些结果按照$P_i$的$i$的顺序排列，将所得二进制编码串转化为十进制$t$，代表第$t$位即$H_{t}$处的海明码出错了，此时可以纠正该比特位的编码值
- 其检错方法和偶校验一样，将$P_i$偶校验位和其所管理分组内的比特逐位异或，若所有$k$组的结果均为
- 通常还会为上述的海明码的整体添加$1$比特位的全校验位，对整体进行偶校验检测，此时该版本的海明码拥有$2$比特位的检错能力和$1$比特位的纠错能力，若超出纠错能力范围则需要通知发送方重传帧
四、流量控制与可靠传输
流量控制的目的是控制发送方发送数据帧的速率大小而让接收方来得及接收；可靠传输的目的是发现并解决数据帧错误
4.1 机制引入
- 以下三种不同的协议都基于滑动窗口机制，目的是实现可靠传输、流量控制
- 停止-等待协议（发送窗口=1，接收窗口=1）
- 后退$N$帧协议（发送窗口>1，接收窗口=1）
- 选择重传协议（发送窗口>1，接收窗口>1）
- 接收方需确保按照原本顺序接收发送方传输的一系列数据帧，我们规定
- 发送方中，处于发送窗口$W_T$内的是允许被发送的帧（Transmit），其它处于$W_T$外的帧不允许发送
- 接收方中，处于接收窗口$W_R$内的是预期要接收的帧（Receive），其它处于$W_R$外的帧会直接被丢弃
- 接收方在接收完$W_R$内预期接收的帧后，会通过确认机制来控制发送方的$W_T$向右滑动$W_R$长度的帧数目的距离，若出现异常情况则通过重传机制进行纠错，帧编号服务于这些机制
4.2 停止-等待协议
4.2.1 基本机制
- 停止-等待（S-W, Stop-Wait）协议
- 滑动窗口
- 发送窗口$W_T$的长度$=1$、接收窗口$W_R$的长度$=1$
- 确认机制
- 若接收方收到
i号帧且经检测无差错，则需给发送方发送ACK_i确认帧（名称缩写自Acknowledge） - 故在双向通信数据帧的过程中，需在数据帧的头尾PCI中指定帧的类型，以区分确认帧与普通帧（前者一般较短）
- 若接收方收到
- 重传机制
- 若发送方超时未收到
ACK_i确认帧，则重传i号帧
- 若发送方超时未收到
- 帧编号
- 为确保上述机制的运行，帧序列中的每个帧只需以间隔的
0和1被编号（故记录帧编号仅需$1$比特空间）
- 为确保上述机制的运行，帧序列中的每个帧只需以间隔的
- 滑动窗口
4.2.2 正常传输
- 发送方从第一个
0号帧开始传输- 接收方收到
Data0后检查若无误，则回传ACK0确认帧，并准备接收下一帧 - 发送方接收到
ACK0后，便可传输第一个1号帧Data1，然后重复上述过程
- 接收方收到
4.2.3 异常处理
4.2.3.1 数据帧丢失
- 若传输过程中因某些原因导致某些帧丢失，此时若不做任何处理，接收方一直接收不到下一帧，无法发送
ACK确认帧，就会导致双方窗口陷入相互等待的死锁 - 而超时重传机制指的是，若发送方超过一定时长未收到
i号帧的ACK_i的确认帧信号，则重传i号帧，并重置相关计时器（以应对可能的多次异常）
4.2.3.2 数据帧差错
- 若发送方传给接收方的数据帧通过差错控制功能发现了错误，那么接收方就会丢弃该错帧而不会返回确认帧，等待发送方超时重传
4.2.3.3 确认帧丢失
- 若接收方成功接受了某数据帧，但其回传的
ACK确认帧丢失了，这就会导致发送方超时重传对接收方而言的前一帧重复帧- 此时由于帧编号是
01间隔的，接收方必然能通过编号差异发现异常（此处体现了帧编号的作用），此时接收方会丢弃重复帧，并重新发送丢失的确认帧信号 - 直到发送方接收到正确的确认信号后，发送方窗口向右滑动，继而发送正确的数据帧给到接收方，使得传输循环得以继续执行
- 此时由于帧编号是
4.3 后退$N$帧协议
4.3.1 基本机制
- 后退$N$帧（GBN, Go Back N）协议
- 滑动窗口
- 发送窗口$W_T$的长度$>1$、接收窗口$W_R$的长度$=1$
- 确认机制
- 接收方在连续收到多个数据帧时，仅返回最后一个正确无差错帧的确认帧信号，此时
ACK_i表示接收方已接收到i号帧以及在其之前传输的所有帧
- 接收方在连续收到多个数据帧时，仅返回最后一个正确无差错帧的确认帧信号，此时
- 重传机制
- 若发送方超时未收到
ACK_i确认帧，则重传i号帧以及在其之后传输的所有帧
- 若发送方超时未收到
- 帧编号
- 为确保上述机制的运行，至少需$n$比特（编址空间大小为$2^n$）给接发双方进行逐帧编号，$n$的大小取决于$W_T>1$的大小，注意$n$必须满足$W_T+W_R\leq2^n$
- 滑动窗口
4.3.2 正常传输
- 发送方会依次连续发送$n$个数据帧给到接收方
- 然后双方的窗口均可继续向后滑动，发送方滑动$n$帧，接收方滑动$1$帧
4.3.3 异常处理
该协议缺点明显，若接收方接收速率较低，或者发送方的误码率较高，那么就会导致发送方频繁重传后退的$n$帧，使得传输效率低下
4.3.3.1 数据帧丢失
- 发送方一次性传给接收方的$n$帧内，若出现一个数据帧丢失
- 则接收方会根据编号差异检测到这个帧丢失了，接收方此时就会回传最后一个被正确接收的帧
Data_i的ACK_i确认帧信号 - 这会使得发送方重新从这个
Data_i开始，重新发送$n$个连续的数据帧，重复上述从发送到接收再到确认的过程（所谓后退指的不是滑动窗口的后退，而是指需要被重新传输的$n$帧序列的开头部分的后退，后退的参照是相对于他若无异常时滑动窗口本应该在的位置的开头，后退的帧数目不大于$n$帧）
- 则接收方会根据编号差异检测到这个帧丢失了，接收方此时就会回传最后一个被正确接收的帧
- 对于数据帧差错的处理，同上理类推即可
4.3.3.2 确认帧丢失
- 若出现确认帧丢失，参考下面一系列图片所示的处理过程
4.3.4 $n$的大小
- 前文规定必须满足$W_T+W_R\leq2^n$，若不满足呢？下图演示$W_T=4, W_R=1, n=2$的情况
- 此时若接收方顺利收到了发送方传来的$4$个帧，但发生了确认帧丢失
- 此时重传会导致被重传的$n$个帧中的某个的编号正好能落在此时接收方的滑动窗口内与其所需编号匹配，这就会导致重传的理应被丢弃的帧被错误地重复接收
- 若$W_T=5$，则上述状况会重传ABCDE，编号为
0的A会被丢弃，而编号为1的B则能恰好匹配落在接收方的编号同为1的窗口帧F上导致错乱，依此类推
4.4 选择重传协议
4.4.1 基本机制
- 选择重传（SR, Selective Repeat）协议
- 滑动窗口
- 发送窗口$W_T$的长度$>1$、接收窗口$W_R$的长度$>1$，其中接收窗口必须小于等于发送窗口即$W_T\geq W_R$，这是为了提升传输效率，实际应用中一般会取二者相等
- 确认机制
- SR协议不同于GBN协议，前者不支持累积确认而必须逐帧返回确认帧
ACK_i - 同时接收方若检测到
i号帧存在差错，会丢弃该帧并返回否认帧NAK_i
- SR协议不同于GBN协议，前者不支持累积确认而必须逐帧返回确认帧
- 重传机制
- 同样支持超时重传，发送方超时未收到确认帧信号则重传对应数据帧
- 除超时重传外SR协议还定义请求重传机制，即发送方收到否认帧
NAK_i时应当直接重传i号数据帧，这样就不必一定等到超时才进行重传，以提升传输效率
- 帧编号
- 至少需要$n$比特空间为每帧进行编号，同样必须满足$W_T+W_R\leq2^n$，同样是为了防止错误接收编号匹配但实际不对应的数据帧
- 滑动窗口
4.4.2 正常传输
- 下图中的示例取$W_T=W_R$，接收方连续接收到多个帧，逐帧确认无误则返回确认帧，接收方窗口向右滑动，发送方收到所有确认帧后也使窗口向右滑动
4.4.3 异常处理
4.4.3.1 数据帧丢失
- 若传输过程中发生了某数据帧的丢失
- 接收方窗口需向右滑动至丢失的那帧（即未接收到的那帧）抵在窗口左侧的位置
- 然后把其余正确接收了的数据帧的
ACK确认帧信号回传给发送方，发送方接收到确认帧后同样会将窗口滑动至丢失的那帧（即未收到ACK的那帧）抵在窗口左侧的位置，然后将新被纳入窗口范围的帧正常传输出去 - 丢失的那帧会触发超时重传，只需要重传这个单独的一帧即可，无需重传整个窗口内的所有帧，这相比GBN需重传所有$n$帧可以避免重复传输已被正确接收了的帧
4.4.3.2 数据帧差错
- 若某个数据帧因为差错而被丢弃
- 那么接收方会回传对应的否认帧（其余帧的确认帧也会回传）告知发送方直接重传
- 发送方收到否认帧和确认帧后便会移动滑动窗口，重传遇错帧，并传输新的帧
4.4.3.3 确认帧丢失
- 若出现确认帧丢失
- 那么发送方滑动窗口向右移动至左端抵住首个未收到确认帧的数据帧的位置，然后发送新被纳入窗口的数据帧，未收到确认帧的数据帧的计时器超时后就会触发重传
- 此时由于接收方此前接收无误，其窗口已经向右滑动，故重传的帧就会落在接收方窗口之外，这些重传帧会被认为是重复的，接收方会直接返回对应的确认帧信号
4.4.4 $n$的大小
- SR协议同样必须满足$W_T+W_R\leq2^n$，以下演示$W_T=5, W_R=4, n=3$的反例
- 假设全部
ACK均丢失，那么重传的某些帧就会落在接收方窗口内从而导致错误
4.4.5 窗口大小
- 接收窗口不能大于发送窗口，是为了提升接收窗口空间的利用效率
4.5 信道利用率
- 参考此处讲解
五、介质访问控制
介质访问控制（MAC, Medium Access Control）用于解决多个节点共享总线型广播信道时容易发生信道冲突的问题（如5G和WiFi等无线网络从中心向四周扩散信号，整个空间对于多个信号源就属于总线型信道），主要有信道划分、随机访问、轮询访问三类解决方案
5.1 信道划分
5.1.1 统计时分复用
- 时分复用（TDM, Time Division Multiplexing）指将时间划分为等长的若干TDM帧，将每帧又分为等长的$m$个时隙，每个时隙分别对应一个用户节点供其使用（下图AD、BE、CF间通信均依赖共享信道，同时通信会冲突，TDM使其通信时间交错）
- 每个节点最多只能分配到总带宽（比特每秒，与时间相关而不是空间）的$\frac{1}{m}$部分，若某些节点暂不进行通信，那么其所占用的时隙就会闲置，使得信道利用率低
- 统计时分复用（STDM, Statistic Time Division Multiplexing）又称异步时分复用，其在时分复用的基础之上，统计每个用户节点对信道资源的使用需求，动态按需分配信道时隙，以提高信道利用率（例如需要时，一个用户节点可在一段时间内获取信道的全部带宽资源）
5.1.2 频分/波分复用
- 频分复用（FDM, Frequency Division Multiplexing）将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每个用户使用其中一个子信道进行通信，每个子频带间存在隔离频带作为缓冲区防止相互干扰（类比室内的多个声音同时传播，声频相近的声音间相对较难区分，不同声音间必须存在一定的频率差才能更易于区分）
- 该方法相对时分复用的优点是多个用户可以同时发送信号以充分利用信道带宽，缺点是只适用于模拟信号（具有数字信号没有的波频率数学特征）的传输
- 波分复用（WDM, Wavelength Division Multiplexing）使用光的不同波长划分子频带，其本质上是光信号的频分复用（因为光的波长与频率凭光速常量关联），光信号的频带范围即带宽非常大，所以其信道可以拆分为更多的子频带
5.1.3 码分复用
- 码分复用（CDM, Code Division Multiplexing）解决的是多个节点同时向另一相同节点发送信号时（数字信号而不是模拟信号），接收方所接收的信号会相互叠加干扰的问题
- CDM会为各节点分配专属的码片序列标识，即包含$m$个码片（即信号值）的$m$维向量
- 该向量的每个分量（即每个码片）的值通常取$1$或$-1$
- 各个节点的码片序列向量必须相互正交（即相互间内积为零）
- 相互通信的节点之间知晓彼此的码片序列（用于识别和区分信号源）
- 当多个节点同时向一个节点发送信号时，信号就会产生叠加，即向量的求和叠加
- 为了拆分叠加信号得到各原始信息，须将叠加后的向量作规格化内积，即将其与各$\frac{\vec x}{m}$依次相乘得到$\pm 1$的结果（此处体现了为何码片序列向量间为何需要正交），从而得出码片序列$\vec x$所属的节点所传递的信号值（$1$代表比特一，$-1$代表比特零）
5.2 随机访问
信道划分是预先分配资源避免冲突，而随机访问则是允许先抢再解决冲突；随机访问协议从最早的ALOHA发展到CSMA，再从CSMA衍生出CSMA/CD和CSMA/CA两个分支
5.2.1 ALOHA协议
- ALOHA协议（Additive Links Online Hawaii Area）诞生自1968年，分为纯ALOHA和时隙ALOHA
- 纯ALOHA
- 对于共享信道中的多个节点，一旦其数据帧准备就绪，就能立刻试图发到信道上
- 若信道上此时存在其它节点正在发送的信号，那么双方都发送失败，会等待一段随机长度的时间后尝试重传（引入了类似S-W协议的ACK信号检测是否发送成功）而不是固定时间，因为固定时间会导致冲突的两个信号始终冲突（如下图
b_1和c_1）
- 纯ALOHA
- 该版本的协议会将信道的可用时间分割为等长的离散时隙，规定每个节点的每个数据帧的传输都固定在一个时隙内完成（只有在每个时隙开始时才能发送数据帧）
- 对于共享信道中的多个节点，一旦其数据帧准备就绪，会就近选取一个时隙发送，这样能够降低冲突概率
5.2.2 CSMA协议
- CSMA协议（Carrier Sense Multiple Access）即载波监听多路访问协议，分为1-坚持CSMA、非坚持CSMA、p-坚持CSMA，其基于ALOHA改进，在发送数据前先监听信道是否空闲，只有信道空闲时才会尝试发送数据（节点需在网络适配器上安装载波监听装置）
- 1-坚持CSMA
- 准备好数据帧后监听信道是否空闲，不空闲就坚持监听，直到空闲时尝试发送帧，这就降低了ALOHA种立刻发送导致的冲突等待问题，理论上能提升信道利用率
- 若数据发送失败（和其它节点的帧发送冲突了）则推迟随机一段时间后重新尝试监听和发送，若发送成功则准备下一帧
- 当多个节点都准备好数据帧时，由于大家都持续监听，所以这些就绪的节点实际上还是会在监听到信道空闲时堆积在一起争抢着同时发送，这与ALOHA并无二致，所以该方法实际上对于信道利用率的改善并不明显
- 非坚持CSMA（1-非坚持CSMA）
- 为了降低发送时的冲突而提升信道利用率，该协议将1-坚持CSMA协议的持续监听修改为推迟随机长度的一段时间后再监听，以一定程度上错开就绪节点的数据帧发送
- 但当信道空闲时，可能会出现就绪节点都处于推迟等待监听的状态，而导致信道不会被立刻使用的情况，这就又导致降低了信道利用率，一增一减改善不明显
- p-坚持CSMA
- 该协议将前两种方法进行了折中，总体上既降低了冲突概率又提升了信道利用率
- 其保留持续监听以防止信道空闲，但又使得数据在将被发送时进行概率检定以降低多节点冲突的可能，即在节点准备就绪且监听到信道空闲时，有$1-p$概率推迟一段时间后重新监听，有$p$概率直接尝试发送（所以1-坚持CSMA就是取$p=1$的p-坚持CSMA）
5.2.3 CSMA/CD协议
5.2.3.1 发送方流程
- CSMA/CD协议用于早期的总线型有线以太网（例如同轴电缆或集线器连接多个节点组成的有线局域网，而现代的有线局域网也使用以太网技术，但并非都是总线型拓扑，例如用交换机连接就属于星型拓扑结构）
- 该协议在1-CSMA的监听机制基础上新增冲突检测（CD, Collision Detection）机制，若传输遇到冲突，该协议会依据传输该数据帧总共遇到的历史冲突次数，等待由截断二进制指数退避算法生成的一段随机时间后，重新监听等待再次传输，具体流程与规则如下图
- 当$0<k\leq10$时，随着历史冲突次数的递增，再次遇到冲突时等待的随机时间长度的上界也会递增，因为冲突越多说明信道越繁忙，所以等得久点能适当减少总冲突次数
- 当$10<k<16$时，等待时间取值区间不会再膨胀
- 当$k=16$时，就说明此时信道反常繁忙，需反馈上层网络层
5.2.3.2 争用期概念
- 争用期是一个确定的常数，其大小由节点和信道性质决定（最大单向传播时延指的是信号走过最远两节点间距离的耗时），其具有两个作用
- 替代ACK机制用于发送方判断数据是否发送成功，若发送数据后的争用期长度时间内都未发生冲突，则此后也不再会遇到冲突（因为在半个争用期内发送的信号已填满整个信道，其它节点监听繁忙便不会再发送数据而导致冲突）
- 用于上文提到的截断二进制指数退避算法中，随机等待时间大小的生成
5.2.3.3 帧长上下界
- 最短帧长定义如下，所有节点发送的数据帧的比特长度都必须不小于该值，若数据帧长度小于最短帧长则需将其填充至合法长度后再发送
- 因为根据前文的计算，在极限条件下（收发节点距离最远），发送端必须发送大小为最短帧长长度比特的编码数据，发送端才能够确保自己已经未冲突地占据了整个信道
- 而如果帧长小于最短帧长，则如果在发送完该长度的帧之后正好遇到了冲突，那么发送方由于已经发送完该帧，会继续准备下一帧而不会收到关于上一帧冲突的通知，从而导致数据传输错误
- 并且正常传输过程中，如果遇到冲突，则多个发送方都会立即停止数据的发送，而此前已经发送出去的数据序列的长度必然是小于等于最短帧长的，这些都是需要被丢弃的非法数据，所以合法帧长必须大于等于最短帧长
- 此外还需有最长帧长限制每个节点发送的数据帧的长度上限，防止其一直占用信道，以太网规定最短帧长$=64$字节，最长帧长$=1518$字节
5.2.3.4 接收方流程
- 前文讨论的都是发送方的注意事项，而该协议的接收方的处理流程如下
- 注意到此处用CRC校验进行差错检测，但前文提到发送方并未采用ACK机制而是等待争用期时间无冲突后直接认为无误，那么发送方如何处理数据帧本身的错误呢？
- 只能通过上层的网络层负责处理，因为若在此处的链路层MAC子层引入差错控制所需的确认帧等机制需将ACK或NAK填充至合法长度，比较浪费空间，故此协议只负责冲突处理等介质访问控制，而不负责差错控制
5.2.4 CSMA/CA协议
5.2.4.1 无线局域网
- CSMA/CA协议用于IEEE802.11无线局域网即WiFi（和CSMA/CD协议所负责的总线型有线局域网均属于总线型，一个有线一个无线），该协议不同于CSMA/CD采用冲突检测机制（发送时监听，检测到冲突则立即停发），而是采用冲突避免（CA, Collision Avoidance）机制在发送过程中不检测冲突，而是在发送前尽量设法避免冲突，即使无法完全避免
- 最初介绍家庭路由器时提到其由路由器（连接外部网络）、交换机（以有线方式连接内部网络设备）与其它功能组成，后者指的就是接入点（AP, Access Point）即无线WiFi热点，用于以无线方式连接内部网络设备，校园网类似同理（在不同接入点之间切换称为漫游）
- 在无线介质中不采用CSMA/CA协议，原因主要如下
- 对于无线传输的多个信号源，其发送信号的强度远大于接收信号的强度，很难实现CSMA/CA所要求的边发送边监听检测（因为节点周围的自己发送的信号强度最大，会极大地干扰其他较远处发送过来的较弱接收信号）
- 不同的节点的有效信号覆盖范围不同，对于范围较大的节点A，其发送到目标节点C的信号周围若存在另一节点B同时冲突地向C发送信号，假如A并不在B的信号覆盖范围内，那么A就无法检测到目的地C处发生的由B导致的冲突，而会认为自己没冲突（即发送节点处无冲突不代表接收节点处无冲突），B对于A而言就属于隐蔽站
5.2.4.2 随机退避机制
- CSMA/CA协议中双方的执行流程如下
- 发送方
- 若信道空闲，则间隔DIFS时间后再发送帧（过程中不检测冲突）
- 若信道繁忙，则进行随机退避，即用二进制指数退避算法（类似CSMA/CD中的截断二进制指数退避算法）确定一段随机退避时间用作倒计时
- 发送方保持监听信道，只有当信道空闲时才扣除倒计时
- 倒计时结束时，发送方立即发送帧
- 接收方
- 使用S-W协议保证可靠性，每收到一个正确帧都返回ACK
- 若发送方超时未收到ACK，则以随机退避尝试重传数据帧
- 发送方
- WiFi的IEEE802.11标准规定了以下三类帧间间隔（IFS, Inter Frame Space），即不同长度的大小固定的时间片，用于规定CSMA/CA协议中信号收发双方的某些行为的等待时间
- DIFS长度最长（分布式协调IFS），即发送方每次帧事务开始之前需等待的时间
- SIFS长度最短，即接收方收到一个帧后需等待的一段处理时间（用于差错控制等）
- PIFS长度中等，用于优先抢占发送（因为他比DIFS更短，所以能早一步被倒计时完）
- 即使信道空闲，也需要等待DIFS的原因是，假如上图左侧发送方节点A和接收方中间存在另一个准备好了数据帧的节点B，那么在中间信道空闲的SIFS阶段中
- 若B不等待DIFS时间，而是检测到空闲就直接发送，会导致和回传的ACK发送冲突
- 若B等待DIFS并在此期间保持监听，则其大概率会监听到信道由于回传ACK进入繁忙状态的信息，从而选择随机退避避免冲突
5.2.4.3 信道预约机制
- 信道预约机制（IEEE802.11标准根据数据帧长度决定是否启用该功能，数据帧超过某阈值时会启用，防止重传较长数据帧的较大损耗）的目的是解决隐蔽站问题，规定每次发送帧前都需先向接收方发送RTS控制帧（Request To Send）预约信道
- 若预约成功，则会收到CTS控制帧（Clear To Send）被允许发送
- 其余无关节点（包括可能处于发送方盲区的隐蔽站）同时会收到禁言令（即虚拟载波监听机制，被禁言的节点不会监听信道，直到被解除禁言）
- 当发送方发送完成且收到回传的ACK确认帧后，其余节点也理应同时收到ACK从而被解除禁言，恢复对信道的监听与发送预约的权限
- 若预约失败，即发送RTS后超时未收到CTS回传，则会随机退避后重新试图预约
- 若预约成功，则会收到CTS控制帧（Clear To Send）被允许发送
5.3 轮询访问
5.3.1 令牌传递协议
- 上世纪80年代的令牌环网技术使用环形拓扑结构替代总线型拓扑以避免信道冲突，其介质访问控制使用令牌传递协议（该技术当时的竞争对手是总线型以太网技术，而以太网后续发展为星型拓扑结构，彻底解决了总线争用的信道冲突问题，淘汰了令牌环网技术）
- 一个令牌环网中，同一时间仅能有一个节点获得令牌，获得令牌的节点持有令牌帧，帧内部指明了当前获得令牌的节点编号
- 该节点发送数据时，会将令牌帧转换为数据帧，后者同样包含节点编号，以及源地址和目标地址、数据部分、数据帧是否被接收（初始为
false） - 发送方节点将数据帧传递给环网中的下一个节点，后者检视目的地址是否是自己，否则继续传递下去，直到到达目标地址节点
- 接收方会获取数据部分进行差错检测，若无错则会将数据帧中标识是否接收的布尔字段更新为
true，有错则维持false，然后将数据帧继续在环网中传递下去 - 直到数据帧传递一圈回到了发送者处，发送者检查布尔字段，
true代表数据帧无差错地成功传递给了目的地址节点，否则代表失败而需尝试重传
- 该节点发送数据时，会将令牌帧转换为数据帧，后者同样包含节点编号，以及源地址和目标地址、数据部分、数据帧是否被接收（初始为
- 令牌帧和数据帧实际的编码构成大致如下图所示
- 若数据帧成功被接收，那么在数据帧回到原发送节点后，就会被就地转换成一个新的归属于环网中的下一个节点的令牌帧（即修改令牌帧的节点编号，所以每个令牌只能够传一个数据帧，传完须被立刻释放），然后传递给下一节点（若拿到令牌的节点无需传输数据，那么其会就地生成新的令牌帧继续向后传递令牌帧），重复前文的过程（无论是令牌帧还是数据帧，都只能沿单向环形传递，无法逆转方向）
- 令牌环网结构由多站接入单元（MAU, Multistation Access Unit）进行集中控制
六、关于局域网
6.1 局域网体系结构
6.1.1 相关IEEE标准
- 局域网相关标准如下图所示，其中规定的链路层MAC子层包含前文所讲的全部功能
6.1.2 局域网分类
- 局域网（LAN）的细分如下，大体上分为无线局域网和有线局域网
- 有线局域网由遵循IEEE802.3标准的以太网垄断（其淘汰了环形结构的、同轴电缆或双绞线作为介质的令牌环网），其物理层使用曼彻斯特编码
- 早期使用同轴电缆以太网（总线型），由中继器连接多个同轴电缆网段
- 80年代后期使用双绞线以太网
- 1994年前以集线器连接（总线型），因其是总线型存在信道争用，所以只能半双工（两端不可同时通信，否则信道冲突），故需使用CSMA/CD协议
- 1994年后以交换机连接（星型），若只支持半双工模式则采用CSMA/CD协议争抢信道，否则全双工模式下不采用协议（NULL）因其无需争抢
- 90年代初后出现光纤以太网（点对点，用于中继器/集线器/交换机间的传输，通常不直接连接终端节点，使用光纤的目的是扩大以太网覆盖范围），两条光纤实现全双工通信，无需采用协议（NULL）
- 无线局域网（WLAN, Wireless LAN）由遵循IEEE802.11标准即WiFi垄断
- 星型拓扑（一个接入点+多台移动设备）结构
- 采用CSMA/CA协议，预防冲突而不检测冲突
- 有线局域网由遵循IEEE802.3标准的以太网垄断（其淘汰了环形结构的、同轴电缆或双绞线作为介质的令牌环网），其物理层使用曼彻斯特编码
6.1.3 网络适配器
- 局域网在计算机主机内通过网络适配器（又称网卡）硬件实现，总体硬件架构如下
- 以太网适配器（有线网卡）实现IEEE802.3标准的有线局域网
- 一个ROM存储全球唯一的MAC地址即物理地址，写死共48比特（24比特厂商标识编码+24比特厂商自定编码），由制造厂商向IEEE组织购买
- 一个RAM作为帧缓冲，滑动窗口机制的发送方窗口内的数据帧就存储在该处
- WiFi网络适配器（无线网卡）实现IEEE802.11标准的无线局域网
- 一个ROM存储全球唯一的MAC地址即物理地址，同样写死48比特，但相同计算机主机的有线网卡和无线网卡的MAC地址并不相同
- 一个RAM作为帧缓冲，和有线网卡内的RAM帧缓冲功能相同
- 两网卡分别根据IEEE802标准要求实现数据链路层+物理层的功能，负责收发帧
- 把数据帧发到局域网
- 组帧（即把上层网络层的IP数据分组进一步封装成帧）可能由网卡完成，也有可能由主机完成，视不同系统而不同
- 从局域网接收数据帧
- 若收到正确帧，则使用中断通知主机CPU
- 若收到异常帧（如帧的目标地址与本机MAC地址不符），则直接丢弃
- 把数据帧发到局域网
- 以太网适配器（有线网卡）实现IEEE802.3标准的有线局域网
6.2 IEEE802.3有线以太网
6.2.1 半双工与全双工
- 光纤
- 仅支持全双工
- 同轴电缆
- 仅支持半双工
- 双绞线
- 速率$<2.5Gbps$时，可支持半双工或全双工（节点连接时协商，若另一端是集线器则只能半双工并采用CSMA/CD协议通信，若是交换机则可能可全双工而无需协议）
- 速率$\geq2.5Gbps$时，仅支持全双工
6.2.2 DixEthernetV2的帧结构
- IEEE802.3标准实际上抄自DixEthernetV2标准，二者在帧格式上略有差别
- DixEthernetV2标准的帧格式如下
- 一个链路层的数据帧由$5$部分组成
- 目的和源MAC地址
- 指明网络层协议类型的信息
- 长度受限的数据部分
- 差错控制校验信息
- 链路层数据帧向上传到网络层时，只保留数据部分（由于LLC子层名存实亡，所以MAC子层向上直接对接网络层），后者反过来向下被传递到链路层进行组帧时
- 若过短则会被进行填充
- 若过长则会拆分到不同帧内
- 链路层数据帧向下传到物理层时，会附加一个前导码控制信息，用于物理层传输需要
- 一个链路层的数据帧由$5$部分组成
- IEEE802.3标准的帧格式如下，其将V2协议（现实中实际使用的协议）数据帧部分指明网络层协议类型的编码的部分替换为了表示数据部分长度的编码（因为IEEE设计的是MAC上方还有LLC子层，故IEEE认为网络层使用什么协议应当由LLC去对接决定，而V2协议不然）
6.2.3 单播帧与广播帧的传播
- 前文帧结构中提到，若目的地址编码全为$1$则表示该数据帧属于广播帧而不是单播帧
- 单播帧在局域网中传播时，交换机会将其精准发送到目标节点处对应的端口，而集线器则会广播通知其冲突域（包含被总线型集线器连接的所有节点）内的所有端口
- 广播帧会被发送到同一广播域内（当前局域网覆盖范围内）的所有节点上，但不会被路由器转发到外部网络（包括其他连接到公共网络的局域网）
6.3 VLAN原理与划分方式
6.3.1 VLAN基本概念
- 虚拟局域网（VLAN, Virtual LAN）标准目的是为了解决校园网（属于局域网）这种内部广播域包含大量节点的局域网面临的如下问题（由IEEE802.1Q工作组负责）
- 校园网的任意节点发送广播帧都会广播至全部节点（广播风暴），这会导致网络传输负载较大，且每个节点处理接收的广播帧的消耗也会较大
- 校园网内存在一些敏感节点（例如数据中心、校园网服务器等）会暴露在局域网内被其它节点访问，这就导致了不安全
- 可在一个局域网内划分出多个虚拟局域网（每个都对应一个VID，但这需要支持VLAN功能的特殊以太网交换机来实现），使得每个虚拟局域网作为相互独立的广播域
6.3.2 VLAN划分方式
- 基于接口划分
- 每个交换机具有多个端口接口，将某些交换机的某些端口划归一个VLAN即可
- 此时交换机管理员在后台管理的是VID与多个端口号间的映射关系
- 如此划分的VLAN分组只与交换机端口有关，而与具体的节点主机无关，也就是说如果将节点换插另一个端口，就可能导致该节点的VLAN分组也发生改变
- 基于MAC地址划分
- 为了使节点主机即便换了端口接入也不会改变其原属VLAN分组，可改为基于MAC地址进行划分，此时交换机管理员管理的就是VID与多个MAC地址间的映射关系
- 基于IP地址划分
- 除基于MAC地址（需物理层和链路层支持）外，也可基于IP地址划分VLAN，这能使得VLAN的覆盖范围跨越路由器，让不同局域网内的主机组成VLAN（需网络层支持），此时需管理的就是VID与多个IP地址间的映射关系
6.3.3 IEEE802.1Q帧结构
- 节点主机与交换机间传输标准以太网帧（基于前文有线以太网的V2协议），而交换机相互间传输802.1Q帧，该类帧在标准以太网帧的基础上往中间插入了包含VID的$4$字节信息，以使得数据帧在跨交换机传输时保留发送方所属VLAN的信息用于确定广播范围
6.4 IEEE802.11无线局域网
无线局域网可分为有固定基础设施的无线局域网（IEEE802.11无线局域网即WiFi）和无固定基础设施的移动自组织网络（如苹果的AirDrop文件隔空投送），此处仅介绍前者
6.4.1 关于基本服务集
- 通过硬件设备门户（Portal）可以把基于IEEE802.3标准的有线局域网、基于IEEE802.11的无线局域网连通成更大的局域网（门户可进行不同标准数据帧间的转换），例如家用路由器可实现手机投屏（手机连接无线局域网，电视连接有线局域网，二者间通过门户沟通）
- 基于IEEE802.11的无线局域网是星型拓扑结构，其中心称为接入点（AP, Access Point）或无线接入点（WAP, Wireless AP），可以将接入点简单理解为WiFi热点
- 一个基本服务集（BSS）由一个IEEE802.11无线局域网的基站（即接入点AP）和多个移动站组成，可以简单理解为一个WiFi热点连接了多个电子设备
- 每个基本服务集都有一个服务集标识符（SSID）标识身份，不超过$32$字节，可以简单理解为WiFi热点的名称
- 每个基本服务集能够覆盖的地理范围称为基本服务区（BSA），可以简单理解为WiFi热点的可连接范围
- 每个移动站相互间无法直接通信，必须借助基站AP转发进行通信
- 每个基本服务集的基站AP可通过门户连通其他IEEE802.X局域网（例如802.3有线局域网）
- 多个基本服务集的基站AP也可通过门户被连接到同一个分配系统而组成一个更大的服务集，即扩展服务集（ESS），例如在家里的每个房间都安装一个子路由（即基本服务集的基站AP），多个子路由通过母路由统一管理并与外部网络连接
- 漫游指的是移动站在多个基本服务集间移动时仍能保持通信，可以理解为不同WiFi热点的无缝切换
6.4.2 IEEE802.11帧结构
IEEE802.11帧分为三种，其中数据帧存储数据，控制帧包含前文的CSMA/CA协议中用于申请信道的RTS和CTS帧以及确认帧ACK，而管理帧则用于探测请求（例如用于寻找WiFi等）
6.4.2.1 数据帧格式
- 数据帧的格式如下，其MAC首部内包含了支持移动站间无线局域网通信的控制信息
- 帧控制编码
- 特定帧类型的标识
- 上述帧类型的子类型标识
- 去往AP或来自AP的标识（因为移动站间必须通过AP转发进行通信，所以若移动站收到去往AP的帧则可直接丢弃，AP收到来自AP即去往移动站的帧也可丢弃）
- 地址1
- 若该帧发往AP，则代表AP地址
- 若来自AP，代表目标移动站地址
- 地址2
- 若该帧发往AP，则代表源移动站地址
- 若来自AP，代表AP地址
- 地址3
- 若该帧发往AP，则代表目标移动站地址
- 若来自AP，代表源移动站地址
- 帧控制编码
- 作为中转站的AP具备格式转换的功能（例如可将无线局域网的IEEE802.11帧转为有线以太网的IEEE802.3帧格式），其与无线链路和有线链路相连
- AP和移动站间通常用无线链路传输数据（802.11）
- AP和AP、AP和路由器、AP和以太网交换机之间通常用有线链路传输数据（802.3）
6.4.2.2 控制帧格式
- 控制帧与数据帧结构相似，其MAC首部也存在标识帧类型和子类型的编码，区别在于
- 控制帧并不包含数据部分
- 控制帧MAC首部中还包含持续期信息，用于CSMA/CA的信道预约机制
- 控制帧MAC首部中的地址部分并没有数据帧的三个那么多
- 例如以下是RTS、CTS、ACK三种控制帧的格式示意
七、以太网交换机
以太网交换机即工作在数据链路层的多端口网桥，可根据目的MAC地址转发数据帧，支持设备通过端口即插即用，其每个端口都支持全双工通信（除非连接集线器就只能半双工）
7.1 自学习功能
- 交换机内的交换表用于记录一系列
[MAC地址, 端口号]的映射信息，初始为空，交换机每收到一个帧时，在转发该帧之前都会先检测该帧的发送源地址是否已存在于交换表中- 若不存在，则将
[发送方的MAC地址, 发送方的端口号]更新到交换表中建立缓存 - 若已存在，则无需更新，其它节点向其发送数据帧时都可据此精确定位它
- 若不存在，则将
- 然后再检测该帧的目标地址是否已存在于交换表中
- 若其存在，则把数据帧精准转发至该目标地址在交换表中对应的端口
- 若不存在，则把数据帧广播转发到除发送方外的其它所有端口
- 交换表中的每个表项都具有有效时间，表项过期自动作废，防止目标节点不存在，或其更换了接入端口
7.2 交换方式
- 直通交换即直接根据帧的目的MAC地址决定转发端口
- 优点：转发时延低
- 缺点：不适用于需差错控制、速率匹配（直接交换会直接将帧向接收方传输，若接收方带宽小于发送方带宽，则会被撑爆）、协议转换（若发送方是IEEE802.11帧格式而接收方是IEEE802.3帧格式，那么直接交换会导致收发帧格式不匹配）功能的线路
- 存储转发交换即先把帧完整地接收到交换机内部Cache内进行必要处理，再根据交换表决定从哪个端口转发
- 优点：将帧完整缓存在Cache可实现差错控制、速率匹配、协议转换处理
- 缺点：转发时延低
本文由作者按照 CC BY-NC-SA 4.0 进行授权