一、基础知识

1、数据链路层的主要任务

 主要包括三个任务：封装成帧，透明传输和差错检测。点对点通信。

  • 将网络层交下来的IP数据报封装成帧
  • 把封装好的帧发送给其他节点的数据链路层
  • 接收其他节点发过来的帧，检测如果无差错，提取出IP数据报并交付给网络层；有差错就直接丢弃帧。

2、名词解释

  • 链路：从一个节点到另一个节点的一段物理线路
  • 数据链路：在链路基础上，增加了执行通信协议的软硬件，构成了数据链路。
  • 网络适配器：称为网卡，实现上述协议的软硬件
  • 帧：数据链路层的协议数据单元（PDU），也是最小传输单位。

二、任务实现

1、封装成帧

 将上一层的网络层交付下来的数据报，加上帧首部与帧尾部之后，交付给物理层进行透明传输。也只有数据链路层会添加尾部。并且还会在帧前面和尾部加上帧界定符，帧开始加入帧开始符（SOH，0x01），帧结束处加上帧结束符（EOT，0x04），帧结束符可以判断帧是否完整，除此之外，PPP协议还会加入前导码（7个字节，0101…01），前导码之后才是帧开始符。**注意：**上述0x01和0x04在谢书是这样，很多其他地方查的都不一样。

 规定帧的格式与使用的协议有关，我们将会在PPP协议中具体讲到。

2、透明传输

 我们已经知道了，帧开始符与帧结束符是一个固定的十六进制数，假如我们传输的数据中包含帧结束符的十六进制数据，那么应该如何处理这种情况呢？这就要求我们对数据进行透明传输。最常用的方法就是使用转义字符，也就是字节填充或字符填充，在数据部分中，有帧结束符的字符前面插入ESC（0x1B）。

 实现透明传输与使用的协议有关，所以我们将会在PPP协议中具体讲到。

3、差错检测

 现在的通信线路都不是很理想，容易发生比特错误，即1变成0或者0变成1。因此，差错检测是非常有必要的。常用的差错检测方法有，奇偶校验码和循环冗余码。除了进行检错之外，还发明了一种具有纠错功能的方法——海明码。

1）检错之奇偶校验码

 奇偶校验码包括奇校验码和偶校验码，发送的比特流包含n位，其中前n-1位是数据，最后一位是校验位。

  • 奇校验：n-1位数据加上校验位的中1的个数是奇数，n位比特进行异或为1。
  • 偶校验：n-1位数据加上校验位的中1的个数是偶数，n位比特进行异或为0。

 异或是一个比较重要的运算，在检验中常常用到。这里用异或是杀鸡用牛刀，海明码需要用到异或。这里给出异或的性质：

左操作数 异或 右操作数 = 结果
0 ⨁\bigoplus 0 = 0
0 ⨁\bigoplus 1 = 1
1 ⨁\bigoplus 0 = 1
1 ⨁\bigoplus 1 = 0
  • 与0异或，可以留出原来的状态
  • 与1异或，可以获取相反的状态
  • 2k和1异或是0，2k-1个1异或还是1
  • 满足交换律， a⨁b=b⨁aa \bigoplus b = b\bigoplus a

2）检错之循环冗余码

 上述编码其实只能够检测到奇数比特出错，如果是偶数个比特出错，检测就会失效了。所以，循环冗余码能够更有效地检测帧的正确与否，但是循环冗余码不能进行纠错，也就是不能确定错误出在哪个位置。循环冗余码检测通过之后，能够以接近1的概率认为此帧没有出错。并且CRC可以由硬件完成，所以速度非常快。

步骤

  • 首先，双方协定一个多项式，多项式能够对应于一个二进制比特序列除数P，P有h位
  • 用数据M后面拼接上h-1位0，对上述P进行模2除法，小学数学学到的除过程中用的减法变成了异或运算而已。
  • 最后得到的余数长度应该是比P少1位，少不止1位，就在前面填充0，这个拼接到M的后面就成为了新的数据。
  • 接收方收到数据后，只需要把接收到的数据对P进行模2除法，如果余数为0，便通过，然后再把最后的检验位去除便可。

其中，除数P应该是：

  • 除数P：

     一个包含n位的序列，对应的多项式应该是

    an−1Xn−1+an−2Xn−2+...+a1X1+a0X0a_{n-1}X^{n-1}+a_{n-2}X^{n-2}+...+a_1X^1+a_0X^0

    ，至于怎么转成二进制序列呢？

    如二进制序列110110对应的多项式应该是

    1×25+1×24+0×23+1×22+1×21+0×201\times2^5 + 1\times2^4+0\times2^3+1\times2^2+1\times2^1+0\times2^0

    。

  • 现在广泛使用的多项式：

    ① CRC-16:

    X16+X15+X2+1X^{16}+X^{15}+X^{2}+1

    ② CRC-CCITT:

    X16+X12+X5+1X^{16}+X^{12}+X^{5}+1

    ③ CRC-32:

    X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+X^{11}+X^{10}+X^{8}+X^{7}+X^{5}+X^{4}+X^{2}+X^{}+1

3）纠错之海明码

 前面提到的两种方法，都只适用于检错，如果出现差错，那么只能丢弃差错帧。而海明码，不仅可以检测出差错帧，还能检测出在哪出现的差错帧，并对其进行纠正。但是，海明码也只能发现双比特错误，纠正单比特错误。

  • 海明距离：两个比特码对应位不同的个数
  • 纠错d位，需要码距为2d+1的解决方案
  • 检错d位，需要码距为d+1的解决方案

确定检验位数

 如果需要对长度为n的有效信息进行检验，需要k位检验码，n与k之间的关系式应该是怎样的呢？

 首先，我们知道，海明码只对单个比特进行纠错，就是假设只有单个比特发生错误。那么，接收方收到的数据有多少种情况呢？应该是有有效信息发生错误（n种）加上校验码发生错误（k种）再加上全部正确（1种）的总共n+k+1n+k+1种情况。那么，k位校验码能够代表多少种情况呢？应该是2k2^k种情况。所以，得到关系式为：n+k+1≤2kn+k+1\leq2^k。

校验码应该如何放置

 按照以往来说，校验码都是拼接到数据的最后部分。而海明码则不是拼接到数据最后部分，这样能够快地确定纠错位置。

 海明码规定，第 i位海明码PiP_i

应该在**整个数据（有效数据+检验码）**第2i−12^{i-1}

的位置。如，第1位海明码在数据的第1位，第2位海明码在数据的第2位，第3位海明码在数据的第4位，第5位海明码在数据的第16位。

检验原理与步骤

 假设海明码用H表示，有效数据用D表示，总数据位用C来表示。我们要明确一个概念，现在不仅仅是对有效数据在检验，而是对整个数据都在检验，与前面的检验方法有所不同。

 假设我们有效数据为n=4位，即可算出校验数据只需要k=3位即可，太多了浪费。下面总数据的序号用二进制表示，方便之后理解。

序号 111 110 101 100 011 010 001
海明码 - - - H3,23−1=b100H_3,2^{3-1}=b100 - H2,22−1=b010H_2,2^{2-1}=b010 H1,21−1=b001H_1,2^{1-1}=b001
有效数据 D4D_4 D3D_3 D2D_2 —— D1D_1 —— ——

那么如何计算H呢？只需要用异或即可，哪几位异或呢？

 从上面我们知道，HiH_i

对应于总数据的位置是2i−12^{i-1}

，显然数字2i−12^{i-1}

对应的二进制序列只有一位为1，而且恰好是第i位，其他都为0，不信可以写一写。我们只需要把总数据序号中，第i位为1的数据拿出来异或，异或后的值就是
HiH_i

的值了。

总结下来说，不那么绕的来说就是，

HiH_i

对序号中第i位为1的数据进行检验。H1=D1⨁D2⨁D4H2=D1⨁D3⨁D4H3=D2⨁D3⨁D4H_1 = D_1 \bigoplus D_2 \bigoplus D_4 \\ H_2 = D_1 \bigoplus D_3 \bigoplus D_4 \\H_3 = D_2 \bigoplus D_3 \bigoplus D_4

 现在收到数据之后，如何进行检验呢？检验完之后，如果找错出错位呢？上述提到海明码计算使用的异或来做的，相当于把原始状态异或后保存到了海明码中。异或能够同为0，异为1。我们把原始状态保存到海明码中了，现在接收到的状态便在数据中，所以，只需要检验数据中的状态与原始状态是否相同即可。那么我们可以得出如下式子。

S1=H1⨁D1⨁D2⨁D4S2=H2⨁D1⨁D3⨁D4S3=H3⨁D2⨁D3⨁D4S_1 = H_1 \bigoplus D_1 \bigoplus D_2 \bigoplus D_4 \\ S_2 = H_2 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \\S_3 =H_3 \bigoplus D_2 \bigoplus D_3 \bigoplus D_4

 如果S1S2S3=000S_1S_2S_3 = 000

，那么说明状态没有改变，接收到的数据是正确的。如果不为0呢？怎么知道哪里发生错误。显然我们在检验过程中有，H1H_1

对序号第1位为1的所有数据进行检验，H2H_2

对序号第2位为1的所有数据进行检验，H3H_3

对序号第3位为1的所有数据进行了检验。

 因此，SiS_i为1的话，代表序号中第i位为1的位置的数据有错误，将所有的S都拼接，即可确定发生错误在序号中的位置。如S3S2S1=010S_3S_2S_1=010，代表序号中第2位发生了错误，只需要把第2位进行取反即可。

三、PPP协议

1、PPP协议满足的需求

  • （1）简单：就追求着简单，采用CRC检验，如果发生错误了，直接丢弃帧，什么也不做。正确就收下帧。
  • （2）封装成帧：规定了特殊字段作为帧界定符。前面提到过，这里协议具体讲。
  • （3）透明性：保证数据透明性。前面提到过，这里协议具体讲。
  • （4）多种网络层协议：保证同一条物理链路上同时支持多种网络协议，如（IP和IPX等）。
  • （5）多种类型链路：除了要支持多种网络协议外，还需要在多种物理链路运行，如串并，电光等。
  • （6）差错检测：对收到的帧进行差错检测
  • （7）检测连接状态：能够判断链路是否正常工作
  • （8）最大传送单元：限定了点对点最大传送单元MTU，数据部分不包括头尾部分，默认值是1500字节。
  • （9）网络层地址协商：使得双方的网络层能够知晓对方IP地址
  • （10）数据压缩协商：提供一种方法来协商数据压缩算法，但不一定要标准化。

2、PPP协议的帧格式

F(0x7E), 1B A(0xFF), 1B C(0x01), 1B 协议, 2B 数据部分, 1500B以内 FCS, 2B F(0x7E), 1B
  • F：帧界定符，二进制为：0111 1110。注意，这里有6个连续的1，之后会用到。
  • A：这个字段相当于保留字段，目前没有任何定义
  • C：同上
  • 协议：表示数据部分使用的协议。比如，0x0021代表IP数据报。0xC021代表LCP（链路控制协议）数据。
  • FCS：帧检验序列，采用的是CRC检验

3、PPP协议的透明传输

 前面提到为什么需要透明传输，以及什么是透明传输。PPP协议有如下方法：

（1）字节填充

 就是使用转义字符，转义字符定义为0x7D（0111 1101）

  • 1）如果数据中出现（0x7E），那么就变成 （0x7D，0x5E）
  • 2）如果数据中出现（0x7D），那么就变成（0x7D，0x5D）
  • 3）如果出现ASCII码控制字符，数值小于0x20的字符，那么就在此字符前面加上0x7D，并将其加以改变，比如加上0x20。

（2）零比特填充

 我们前面提到，0x7E中有连续的6个1，那么我们只要保证数据中没有连续的6个1即可，具体做法是，每发现5个1，就填充1个0。接收数据后，只要每发现5个1，就删除后面的1个0。

（3）其他方法

 这些不是PPP协议的内容，但是也是进行透明传输的方法。

  • 字符计数法：在帧的头部加上一个表示该帧后面跟随的字节数。这样，就能明确边界在哪了。这种方法的问题就是，出现一个错误，那么后面全部的帧都发生错误。
  • 违规编码法：在物理层常使用这种方法，如曼彻斯特编码中，一个比特位周期的电平要么是 高-低，要么是 低-高，所以，高-高或者低-低就是违规编码，我们用来作为帧的开始和结束。

4、PPP协议的工作状态

 我们知道PPP协议主要是为了传输网络层的数据，但是，数据链路层也有自己的数据需要传送，如有些链路需要建立连接。PPP协议组成应该包含了三个部分，一是将IP数据报封装到串行链路中，既支持异步链路，又支持面向比特的同步链路。二是用来建立、配置和测试数据链路连接的链路控制协议LCP（Link Control Protocol）。三是一套网络控制协议（Network Control Protocol），这其中，每一个协议支持不同的网络层协议。

 用户接入ISP后，会主动发送一系列LCP分组，以便建立LCP。紧接着，NCP就会为新接入的主机分配一个IP地址。用户通信完毕，NCP收回IP地址，并释放连接。步骤如下图所示：image-20220616141536749

 PPP链路起始和终止状态都是链路静止状态，用户发起连接后（如连接一个WiFi，接上一根网线），进入了链路建立状态。这是LCP开始进行一些协商，发送LCP配置请求帧，包括配置确认帧（接受）、配置否认帧（理解意思但不接受）和配置拒绝帧（无法识别或不接受）。之后ISP对用户进行鉴别（如WiFi密码正确与否，账号密码登录，网费是否充足）。采用了口令鉴别协议PAP（Password Authentication Protocol）或口令握手鉴别协议CHAP（Challenge-Handshake Authentication Protocol）。之后便进入了网络层协议。

四、数据链路层

1、局域网的数据链路层

 局域网工作的层次横跨了数据链路层和物理层。局域网内的主机共享连接在局域网上的各种软硬件资源，共享需要考虑的一个问题是，如何使众多用户能够合理而方便地共享通信媒体资源。这在技术上有两种方法：

  • （1）静态划分信道，如前面提到的时分复用等，这种信道划分的方法代价高

  • （2）动态媒体接入控制技术，分为：

    • 随机接入：所有用户可以随时发送消息，但是如果恰巧不止一个用户在发送消息，那么就会产生碰撞（即产生冲突），因此需要有协议来解决这些碰撞。
    • 受控接入：用户不能随时发送消息，而是服从一定控制发送消息，使用轮询方式

2、数据链路层的划分

 因为各个公司的协议不同，所以产生了很多不同种类的数据链路层，而IEEE 802 委员会将局域网的数据链路层拆分为逻辑链路控制LLC（Logical Link Control）和媒体接入控制MAC（Medium Access Control）两层。而委员会仅仅只能是制定标准的人，真正实行的还是各大企业，因此，最后局域网只剩下以太网（DIX Ethernet V2）了，LLC已经消失，只剩下MAC。

3、适配器

 计算机与外界局域网的连接都是通过适配器（adapter），适配器是在主机箱内插入的一块网络接口板，称为网络接口卡NIC，简称网卡。适配器不仅仅包含数据链路层的功能，还需要实现物理层的功能。适配器有自己的处理器（CPU）和存储器（RAM, ROM），因此，不需要使用计算机的CPU。网卡的ROM有MAC地址，而计算机的软件地址（IP地址），则在计算机的存储器中。

4、信道划分介质访问控制

 介质访问控制有，介质访问控制，随机访问介质访问控制和轮询访问介质访问控制。

 信道划分介质访问控制便是之前讲的，复用技术：频分复用、时分复用、码分复用、波分复用

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

（1）ALOHA协议

纯ALOHA协议

 各个用户想发送数据就发送数据，如果一段时间内没有收到确认，就认为发生了冲突，随机等待一段时间后再发送。假设网络负载（单位时间内所有站点发送成功和未成功而重传的帧数）为G，则纯ALOHA协议网络的吞吐量（单位时间内发送成功的平均帧数）为S=Ge−2GS=Ge^{-2G}

。当G=1.5时，S≈0.184。

时隙ALOHA协议

 讲各个用户时间同步起来，并且划分了一段段时隙，只有在时隙开始时，各个用户才可发送消息。其他基本与纯ALOHA协议一致。

（2）CSMA协议协议

 **载波监听多路访问 ( Carrier Sense Multiple Access ) **协议，相比于ALOHA协议，多了一个载波监听装置。CSMA协议分为三种方式：

  • 1-坚持CSMA：结点需要发送数据，首先侦听信道，信道空闲就立马发送，信道忙，就一直等待并持续监听。
  • 非坚持CSMA：结点需要发送数据，首先侦听信道，信道空闲就立马发送，信道忙，就等待一个随机时间再重复上述过程
  • p-坚持CSMA：结点需要发送数据，首先侦听信道，信道忙就持续监听，信道空闲，以概率p发送数据，以概率1-p推迟到下个时隙，重复。

（3）CSMA/CD协议

CSMA/CD协议介绍

 **载波侦听多路访问/碰撞检测（Carrier Sense Multiple Access with Collision Detection，CSMA/CD）**过程如下：

  • 1）适配器从网络层获得一个分组，封装成以太网帧，放入适配器缓存，准备发送。
  • 2）如果适配器侦听到信道空闲，就发送该帧。侦听到忙，就持续侦听直到信道上没有信号能量，然后发送该帧
  • 3）在发送过程中，仍然持续检测信道，如果没有检测到碰撞，就顺利发送该帧。否则，中止发送，并发送一个拥塞信号。
  • 4）中止发送后，适配器执行指数退避算法，等到一段随机事件后返回步骤2。

 以太网常常采用此方法进行处理冲突，以太网使用曼彻斯特编码，曼彻斯特在传输过程中自带了时钟信息，可以很方便的检测出当前信道是否有数据在发送。下面讲解CSMA/CD协议的要点：

  • 多点接入：表示了是总线型，各台计算机以多点的方式接入到网络中
  • 载波监听：也就是边发送边监听
  • 碰撞检测：通过检测电压变化，判断网络是否发生了冲突

碰撞检测

 首先，假设A、B两方在通信，规定了端到端的传播时延为τ\tau。假设A向B发送数据，那么最多经过2τ2\tau

的时间，A能够检测到碰撞发生与否（即，信号往返的时间）。显然，采用CSMA/CD协议的以太网只能实现半双工通信（我的理解是，总线型，只有一根信道，也就是对于任何一个主机而言，接收端也是发送端）。

image-20220706135253122

 设想如下场景：

  • t=0t=0，A检测到信道空闲，向B发送数据

  • t=τ−δt=\tau - \delta，B检测到信道空闲，向A发送数据，δ\delta为B发送数据到A的数据到达B的时间

  • t=τ−δ2t= \tau - \frac{\delta}{2}，也就是B发送数据后经过δ2\frac{\delta}{2}后，A,B数据发生了碰撞

  • t=τt=\tau，B检测到了碰撞

  • t=2τ−δt=2\tau-\delta，A检测到了碰撞

  • 当 lim⁡δ→0{\lim\limits_{\delta \to 0}} ，最慢到 t=2τt=2\tau时，A检测到碰撞发生。

 最短帧长：A最多在2τ2\tau的时间后能够检测到碰撞，因此把2τ2\tau称为争用期。发送方是在发送数据以及将要发送数据的时候才检测信道是否发生冲突，为了确保发送数据过程中，发送方能够检测到冲突，要求发送方在争用期中，一直发送数据。那么争用期中发送数据的帧长就是最短帧长，即最短帧长=2τ×2\tau\times数据传输率。例如，以太网规定争用期为51.2μs51.2\mu s，对于10Mb/s10Mb/s的以太网，最短帧长为512bit=64B512bit = 64B。凡是小于64B64B的帧都是由于冲突而异常中止的无效帧。

二进制退避算法

  • 1）确定基本的退避时间，通常为 2τ2\tau
  • 2）定义参数 kk， k=min[重传次数,10]k = min[重传次数, 10]，重传次数即，此次是该帧第几次重传了，也就是发生了几次碰撞。
  • 3）从离散集合 [0,1,,...,2k−1][0,\quad1,\quad,...,2^k-1] 中随机取出一个数 rr，重传所需要的退避时间就是 2rτ2r\tau。
  • 4）当重传16次都未成功，那么丢弃此帧，并向上层（网络层）报告错误。

（4）CSMA/CA协议

 载波监听多路访问/碰撞避免（Carries Sense Multiple Access with Collision Avoidance）协议，相比于CSMA/CD协议，将碰撞检测变成了碰撞避免。

 CSMA/CD协议很好地应用于有线局域网中了，但在无线局域网中，则需要使用CSMA/CA协议。原因如下：

  • 1）接收信号的强度往往远小于发送信号的强度，因此要是实现碰撞检测，硬件花费大。
  • 2）无线通信中，并非所有的站点都能够听见对方，存在隐蔽站问题。

 无线信道的通信质量远远小于有线信道，所以采用了链路层确认/重传（ARQ）方案，发送完一帧，需要收到确认才能发送下一帧。为了尽量避免碰撞，所有站发送完成后，必须等待一段很短的时间才能发送下一帧，这段时间间隔称为帧间间隔（InterFrame Space, IFS），类型如下：

  • 1）SIFS（短IFS）：最短的IFS，用于分隔属于一次对话的各帧，如ACK帧，CTS帧，分片后的数据帧，以及所有回答AP探询的帧。
  • 2）PIFS（点协调IFS）：中等长度的IFS，在PCF操作中使用
  • 3）DIFS（分布式协调IFS）：最长的IFS，用于异步帧竞争访问的时延

 CSMA/CA的退避算法和CSMA/CD的稍有不同，当且仅当信道空闲且当前为发送的第一个帧才不使用退避算法，其他时间都需要使用。CSMA/CA协议归纳如下：

  • 1）若站点有数据发送（该帧第一次发送），检测到信道空闲，等待DIFS后，发送整个数据帧
  • 2）否则，站点执行CSMA/CA退避算法，选取一个随机时间回退值。一旦检测到信道忙，退避计时器保持不变，信道空闲，计时器才计时
  • 3）当计时器减到0，发送数据帧
  • 4）发送站收到确认帧，发送第二帧时，从步骤2）开始。

 隐蔽站问题：RTS和CTS

  • RTS(Request To Send)：请求发送帧，每个站点发送数据帧之前广播发送一个RTS进行信道预约，包括源地址、目的地址、和此次通信持续时间。
  • CTS(Clear To Send)：允许发送帧，若信道空闲，AP广播发送一个CTS，包括此次发送持续时间（从RTS中获得）。任何站点听到此帧，将会抑制发送。

（5）CSMA/CD VS CSMA/CA

  • 1）CD可以检测冲突，无法避免；CA不能同时发送和检测冲突
  • 2）介质不同，CD是以太网，CA是无线局域网
  • 3）检测方式不同，CD是通过电压变化，CA通过能量检测、载波检测、能量载波混合检测三种检测信道的方式。

6、轮询访问介质访问控制

 令牌传递协议，物理上不必是环形，但是逻辑上是环形结构，过程如下：

  • 1）网络空闲时，环路中只有令牌帧在循环传递
  • 2）令牌传递到有数据发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附上自己的数据，令牌就变成一个数据帧
  • 3）数据帧沿着环路传输，接收到的站点一边转发数据，一边查看目的地址，如果目的地址是自己的，就复制下来该数据
  • 4）数据帧沿着环路到达源发送站点，就不再转发，同时，检测返回的帧来查看数据传输是否出错
  • 5）源站点传送完数据后，重新生成一个令牌，并且传送个下一个站点，交出控制权。

五、数据链路层的流量控制与可靠传输

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

 发送方每发送一帧，接收方都需要发送确认帧。

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

  • 发送方与接收方都有自己的窗口大小
  • 发送方收到一个确认帧并且可以向前滑动的时候，滑动窗口才向前滑动
  • 接收方能够向前滑动的时候就向前滑动
  • 窗口大小都是固定的
  • 接收窗口先滑动，发送窗口才能滑动，这样就能起到流量控制的作用
  • 从滑动窗口看下面三种传输机制
    • 停止-等待协议： 发送窗口=1，接收窗口=1
    • 后退N帧协议：发送窗口>1，接收窗口=1
    • 选择重传协议：发送窗口>1，接收窗口>1

3、三种可靠传输协议

 首先，需要对帧进行编号，考虑到节省，对帧编号用固定且少量的比特数进行编号。但是，引入的新问题便是，编号循环后，如何确定发送的帧是上一轮的还是此轮的或者是下一轮的呢？

答：要求 发送窗口+接收窗口≤2n,n为用于编号的比特数发送窗口+接收窗口 \leq 2^n,\quad n为用于编号的比特数，至于为什么这样呢？最坏的情况，当接收窗口已经滑动到滑动窗口的尾部了，此时，当前轮发送仍未结束，但是当前发送双方能够扩展的长度应该不大于此轮编号长度才可以。

3.1 停止-等待协议

  • 发送与接收窗口都是1
  • 一个帧被发送，该帧的确认帧需要被接收才能发送下一帧
  • 发送方有定时重传计时器
  • 编号的比特数便是：1+1≤2n,n=11+1 \leq 2^n,\quad n = 1即可满足
  • 如果确认帧没有被收到，那么发送方重新发送后，接收方直接丢弃并重新发送确认帧。

 信道利用率低

3.2 后退N帧协议（GBN）

  • 接收窗口为1，发送窗口为1≤WT≤2n−11\leq W_T \leq 2^n-1
  • 接收端只能接收滑动窗口内的帧，也就是只能一帧一帧按序接收
  • 接收端接收到错误的帧，或者接收到不在滑动窗口的帧（不管是窗口前或后）都丢弃
  • 接收端可以接收连续多帧，或者有数据发送的时候，才发送一个确认帧
  • 确认帧的意义是：对该帧及以前的确认帧都进行确认，并期望发送方发送下一帧
  • 接收方为每一帧都设置了一个定时重传定时器
  • 接收方没收到一个确认帧，滑动窗口的左端即可移动到该帧后面一个位置。

 提高了信道利用率，但是如果有一帧出了问题，那么窗口前面的帧都需要重传，因此在误码率大的信道，信道利用率不一定比停等协议优。

3.3 选择重传协议（SR）

  • 窗口尺寸：WR=WT=2n−1W_R=W_T = 2^{n-1}
  • 一帧接收和一帧确认，发送方只需要重传没有收到确认的帧即可
  • 互联网标准还没明确地对该协议规定，所以这里从略

4、三种协议的信道计算

4.1 信道利用率

 信道利用率相对于发送方而言，有效发送数据的时间占整个发送周期的比率。比如，发送方从开始发送到接收确认帧为止，时间为T，此时发送了L比特数据，发送方数据传输速率为C，那么有：发送方发送有效数据的时间=LC,占总时间的比值为：L/CT发送方发送有效数据的时间 = \frac{L}{C},\quad 占总时间的比值为：\frac{L/C}{T}，利用率也是这个。

 定义参数α=τT0\alpha = \frac{\tau}{T_0}，假设永远不发生碰撞，以太网利用率最高Smax=T0T0+τ=11+aS_{max} = \frac{T_0}{T_0 + \tau}=\frac{1}{1+a}

4.2 信道吞吐量

信道吞吐量=信道利用率×发送方的发送速率，=LT信道吞吐量 = 信道利用率 \times 发送方的发送速率，\quad = \frac{L}{T}

4.3 如何计算

  • 首先计算第一帧开始发送到第一个确认帧返回的时间
  • 然后计算这段时间内，发送方发送了多少有效数据，并计算发送有效数据的时间
  • 对于上面一点，停等协议就只发送了一帧数据，而后退N帧协议就发送了多帧数据，这段时间都要进行计算
  • 有效数据的时间除以上面总的时间，便是效率

六、以太网

1、MAC层

 硬件地址又称为物理地址或MAC地址，是一个48位固化在ROM中的。MAC地址前24位称为组织唯一标识符OUI，后24位称为扩展唯一标识符EUI。第一个字节的最低二位规定为G/L位，表示Global/Local位，为0表示全球管理，为1表示本地管理。全球管理的地址有46位。

 适配器会处理一下三种帧

  • 单播帧：一对一，目的MAC地址与本适配器的MAC地址相同就收下
  • 广播帧：一对全体，MAC地址为全1
  • 多播帧：一对多，发送给一部分站点，而不是全部站点，相当于群组

 所有适配器都应该识别前面两种帧，有一种网络工具叫做**嗅探器（Sniffer）**能够识别所有的帧，包括MAC地址不是自己的也可以记录下来。

2、MAC帧格式

image-20220719104733647

  • 源地址与目的地址，MAC地址
  • 类型，比如交付给上层的协议是什么，如IP：0x0800
  • FCS：使用CRC校验，只校验目的地址到FCS为止的字段，不包括前导码和帧开始定界符
  • 以太网规定最小帧长为64字节，所以数据段最小长度为64-6-6-2-4=46字节
  • 以太网采用曼彻斯特编码，当电压不再变化了，就代表已经结束传输了，所以帧结束定界符也就不需要
  • 前导码的作用是用来同步时钟频率的，帧开始定界符是用来告诉帧开始发送的标志

对于下列的帧情况，以太网直接进行丢弃，不会重传

  • 帧长度不是整数个字节
  • FCS检验出错
  • MAC帧长度不是64-1518个字节的

现在广泛使用的局域网也只剩下以太网了

3、扩展以太网

3.1 在物理层扩展以太网

 过去使用粗缆或细缆，现在使用光纤

3.2 在数据链路层扩展以太网

 使用交换机进行扩展

3.3 虚拟局域网

 **虚拟局域网VLAN（Virtual LAN）**是局域网提供给用户的一种服务，而不是一种新型局域网。VLAN使用802.1Q帧，格式如下：

image-20220719121225767

相比于以太网帧，多了VLAN标签。VLAN标签前两个字节为0x8100，后面为VLAN标识符VID（VLAN ID），出入VID后，FCS需要重新计算。对于主机来说，并不知道自己的VID，所以主机发送给交换机的是普通以太网帧。交换机通过端口或者MAC地址划分VLAN，并且为VLAN分配好了VID。

设想一下场景

image-20220719121409605

  • A向B发送数据，发送普通以太网帧给交换机#1，#1发现是同一VLAN下的主机，不需要增加VLAN标签，直接转发给B
  • A向E发送数据，#1通过汇聚链路将帧转发给#2，并增加VLAN标签，#2发送去掉VLAN标签，并转发给E
  • A向C发送数据，这种情况比较复杂，书上没讲

4、扩展到高速以太网

4.1 100BASE-T以太网

  • 速度：100Mb/s
  • 完全可以使用10Mb/s下的软件

4.2 吉比特以太网

  • 速度：1Gb/s
  • 半双工使用CSMA/CD，全双工不使用
  • 向后兼容

不改变网段最长长度，但是争用期由原来的64字节，变成512字节，使用如下方法来适用CSMA/CD。

  • 载波延伸：最短帧长仍然是64字节，但是为他扩充到512字节；引入的问题便是，发送了许多无用的数据
  • 分组突发：将多个短帧合起来发送

4.3 10吉比特以太网

  • 速度：10Gb/s
  • 只工作在全双工模式

4.4 40/100吉比特以太网

  • 速度：40/100Gb/s
  • 只工作在全双工

七 、无线局域网

 又称为802.11局域网

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

 采用该星形拓扑，中心称为接入点（Access Point，AP）。基本服务集（Basic Service Set， BSS）包括一个接入点和若干移动站。安装AP时必须为其分配一个不超过32字节的服务集标识符（Service Set IDentifier，SSID）和一个信道。接入点AP在出厂就具有唯一的48位二进制数字的MAC地址，正式名称为基本服务集标识符 BSSID。

 一个基本服务集，可以时孤立的，还可以通过其他AP，连接到一个分配系统DS（Distribution System），然后再连接到另一个基本服务集，这样就构成一个扩展服务集ESS（Extended Service Set），扩展服务集也有唯一标识称为扩展服务集标识符ESSID。

移动站与接入点AP建立关联的方式由两种，一种是被动扫描，一种是主动扫描。

被动扫描

  • 接入点AP周期性发送信标帧（beacon frame），其中包含由若干系统参数，如SSID及支持的速率
  • 移动站A扫描了11个信道，选择愿意加入接入点AP所在的基本服务集BSS，于是发送关联请求帧（Association Request frame）
  • 接入点同意A发来的关联请求，向A发送关联响应帧（Association Response frame）

主动扫描

  • A广播发送探测请求帧（Probe Request frame），让所有的AP都能够知道有移动站要求建立关联
  • 有两个接入点回答探测请求响应帧（Probe Response frame）
  • A向一个站发送关联请求帧
  • 接入点向A发送关联响应帧

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

 称为自组网络，没有上述服务中的AP，由一些平等状态的移动站相互通信组成的临时网络。各结点地位平等，中间结点都为转发点。

 在军用，救援等中有很好的应用。

 移动自组网络的一个子集——无线传感器网络WSN（Wireless Sensor Network）。

3、MAC帧

 分为数据帧、控制帧和管理帧。

下面来讲解数据帧：

image-20220719131230352

上述地址都是指MAC地址，其中地址4用于自组网络；

去往AP 来自AP 地址1 地址2 地址3 地址4
0 1 接收地址=目的地址 发送地址=AP地址 源地址 ——
1 0 接收地址=AP地址 发送地址=源地址 目的地址 ——