数据链路层

基本概念与基本问题

数据链路层属于计算机网络的底层，使用的信道主要有点对点信道和广播信道。

基本概念

• 在研究数据链路层的问题时，许多情况下只关心在协议栈中水平方向的各数据链路层，不考虑物理层中运输的问题。

• 链路：从一个结点到相邻结点的一段物理链路，中间没有其他结点。
• 数据链路：除物理链路外，还需要加上必要的通信协议来控制数据的传输。把实现这些协议的硬件和软件加到链路上，就构成了数据链路。网络适配器（也就是网卡），用来实现数据链路上的协议。
• 帧：数据链路层数据单元。

三个基本问题

• 封装成帧：将IP数据报的前后添加首部和尾部来进行帧定界。当数据是ASCII码组成的文本文件时，可使用特殊的帧定界符。控制字符SOH放在帧的最前面，表示帧的首部开始。EOT表示帧的结束。SOH和EOT只是名称，二进制为00000001和00000100.

• 透明传输：如果在IP数据报中如果有一个和帧尾部一样的8位二进制数，则会提前结束接收数据，这样数据就被破坏了。解决方式是：发送端的数据链路层在数据中出现控制字符SOH或者EOT的前面插入一个转义字符“ESC”(00011011),而在接收端的数据链路层在把数据送往网络层之前删除这个插入的转义字符。这种方法称为字节填充。当接收端收到连续两个转义字符时，就删除前面的一个。

• 差错检测：传输过程中可能产生比特差错：1可能变成0,0可能变成1。循环冗余检验CRC：在发送端，先将数据分组，每组k个比特。假定待发送数据为M-101001，k=6.先在M后面添加差错检测用的n为冗余码，一共发送n+k位。冗余码的计算：用二进制的模2运算进行$2^n$​乘M的运算，相当于在M后加上n个0.得到的n+k位数除以事先选定好的长度为n+1位的除数P，得出商为Q而余数是R，余数比除数少一位，余数即冗余码FCS。

在接收端，把接收到的每一个帧都除以同样的除数P，如果余数为0，则这个帧没有差错，否则有差错，舍弃这个帧。

这种冗余检错校验的特点：

1. 并不能确定究竟是哪一个或哪几个比特出现了差错。
2. 只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。
3. 只能是无差错接受：凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。
4. 这是”不可靠“的，是无比特差错，而不是无传输差错的检测机制，要做到可靠的 还要加上确认和重传机制。即考虑帧重复、帧丢失、帧乱序的情况。

点对点协议PPP

是点对点信道数据链路层协议。互联网用户需要连接到某个ISP才能连入互联网。PPP协议就是用户计算机和ISP进行通信时所使用的数据链路层协议。

特点

• 简单：接收方每接收一个帧，就进行CRC检验，检验正确，就收下，否则就丢弃，它是不可靠传输，所以这就是简单的原因。
• 封装成帧：规定特殊字符作为帧定界符。
• 透明性：即透明传输。
• 多中网络协议：在同一条物理链路上同时支持多种网络层协议(如IP何IPX等)的运行。
• 多种类型链路：多种类型链路：比如，串行的、并行的，（串行：一个比特一个比特发送，只需要一条线路，并行：一次性传输n个比特，所以需要n条线路，所以叫并行）同步的、异步的（同步：以稳定的比特流的形式传输 异步：以字节为独立的传输单位，字节跟字节之间的时间间隔不确定，但字节中的每个比特仍是同步的。），低速或高速、电或光，等不同类型的链路都能支持。
• 差错检测：CRC检测。
• 检测连接状态：检测点跟点之间的连接状态，也就是在PC机和ISP之间的线路。
• 最大传送单元：MTU，帧的数据部分最大长度。
• 网路地址协商。

PPP协议的组成

1. 数据链路层协可以用于异步串行或同步串行介质，通俗讲也就是可以适应多种性质的链路。
2. 使用LCP(链路控制协议)建立并维护数据链路连接， 也就是上面讲的一些维护链路连接、检测连接状态等功能，就是用它来实现的。
3. 网络控制协议(NCP)允许点到点连接上使用多种网络层协议，也就是因为跟网络层连接在一起，所以需要支持上一层的多种协议，这样才能完成一系列的功能，比如，网络层地址协商。

PPP协议的帧格式

标志字段F就是PPP帧的定界符。

• 字节填充：使用的是字节传输，也就是异步，所有的PPP帧的长度都是整数字节，所以会出现IP数据包中有字节跟开始结束标志字节相同的问题。解决方式：IP数据报中出现0x7E字节 ： 转变为 0x7D、0x5E；IP数据报中出现0x7D：0x7D、0x5D；IP数据报中出现ASCII码的控制字符，则在该控制字符前面加0x7D。在接收端做相反的操作。
• 零比特填充：使用的是比特流传输(一连串的比特连续传送)，也就是同步传输。在发送端扫描整个数据部分，只要发现5个连续1，则立即填入一个0.这样保证不会出现6个连续的1，导致和定界符0x7E相等。在接收端，当发现连续的5个1，就把后面的0删除。

PPP协议工作状态

为什么PPP协议不用可靠传输？

1. 在数据链路层出现差错的概率不大时，使用比较简单的 PPP 协议较为合理。
2. 在因特网环境下，PPP 的信息字段放入的数据是 IP 数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。
3. 帧检验序列 FCS 字段可保证无差错传输。

广播信道的数据链路层

• 以太网：以太网是通信协议标准，该标准定义了在局域网（LAN）中采用的电缆类型和信号处理方法，比如有CSMA/CD协议。
• 局域网：在较小范围内组件的网络，通过交换器什么的连接各个PC机，比如一个实验室，一栋楼，一个校园内，这都是局域网，拿网线将两台计算机连在一起，这也能算是局域网。
• 广播信道：就是一台PC机发送数据给另一台PC机，在同一个局域网中的计算机都能接收到该数据，这就像广播一样，所以这种就叫做广播信道。
• 局域网常见拓扑结构

• 为了通信的简便，以太网采取了两种重要的措施。
  • 采用较为灵活的无连接的工作方式
    • 不必先建立连接就可以直接发送数据。
    • n对发送的数据帧不进行编号，也不要求对方发回确认。
    • 这样做的理由是局域网信道的质量很好，因信道质量产生差错的概率是很小的。
    • 以太网提供的服务是不可靠的交付，即尽最大努力的交付。
    • 当目的站收到有差错的数据帧时就丢弃此帧，其他什么也不做。差错的纠正由高层来决定。
    • 如果高层发现丢失了一些数据而进行重传，但以太网并不知道这是一个重传的帧，而是当作一个新的数据帧来发送。
  • 以太网发送的数据都使用曼彻斯特 (Manchester) 编码。

CSMA/CD协议（半双工通信）

• 多点接入：表示许多计算机以多点接入的方式连接在一根总线上。
• 载波监听：指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据，如果有，则暂时不要发送数据，以免发生碰撞。
• 碰撞检测：也就是边发送边监听，当一个站检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。

工作流程：

1. 准备发送：适配器从网络层获得一个分组，加上以太网的首部和尾部，组成以太网帧。发送之前，必须先检测信道。
2. 检测信道：若检测到信道忙，则应不停地检测，一直等待信道转为空闲。若检测到信道空闲，并在 96 比特时间内信道保持空闲（保证了帧间最小间隔），就发送这个帧。
3. 检查碰撞：在发送过程中仍不停地检测信道，即网络适配器要边发送边监听。这里只有两种可能性：
   1. 发送成功：在争用期内一直未检测到碰撞。这个帧肯定能够发送成功。发送完毕后，其他什么也不做。然后回到 (1)。
   2. 发送失败：在争用期内检测到碰撞。这时立即停止发送数据，并按规定发送人为干扰信号。适配器接着就执行指数退避算法，等待 r 倍 512 比特时间后，返回到步骤 (2)，继续检测信道。但若重传达 16 次仍不能成功，则停止重传而向上报错。

争用期

• 以太网的端到端往返时延 2t 称为争用期，或碰撞窗口。
• 经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

二进制指数退避算法

发生碰撞的站在停止发送数据后，要推迟（退避）一个随机时间才能再发送数据。

• 基本退避时间取为争用期 2t。
• 从整数集合 [0, 1, … , (2k -1)] 中随机地取出一个数，记为 r。重传所需的时延就是 r 倍的基本退避时间。
• 参数 k 按下面的公式计算：k = Min[重传次数, 10]。
• n当 k $\leq$​10 时，参数 k 等于重传次数。
• 当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告.

争用期长度

• 10 Mbit/s 以太网取 51.2 $\mu s$​​ 为争用期的长度。
• 对于 10 Mbit/s 以太网，在争用期内可发送 512 bit，即 64 字节。
• 这意味着：以太网在发送数据时，若前 64 字节没有发生冲突，则后续的数据就不会发生冲突。
• 由于一检测到冲突就立即中止发送，这时已经发送出去的数据一定小于 64 字节。以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。

强化碰撞

当发送数据的站一旦发现发生了碰撞时：立即停止发送数据，再继续发送若干比特的人为干扰信号 (jamming signal)，以便让所有用户都知道现在已经发生了碰撞。

以太网的信道利用率

$$ \alpha = \frac{\tau}{T_0} $$ *α* →0，表示一发生碰撞就立即可以检测出来， 并立即停止发送，因而信道利用率很高。*α* 越大，表明争用期所占的比例增大，每发生一次碰撞就浪费许多信道资源，使得信道利用率明显降低。为提高利用率，以太网的参数*a*的值应当尽可能小些。对以太网参数 *α* 的要求是：

1. 当数据率一定时，以太网的连线的长度受到限制，否则 $\tau$​的数值会太大。
2. 以太网的帧长不能太短，否则 $T_0$​的值会太小，使 α 值太大。

以太网的MAC层

• 在局域网中，硬件地址又称为物理地址，或 MAC 地址，指计算机固化在适配器的ROM中的地址。

• MAC帧格式：48bit，6个字节，前3个字节是由管理机构给各个厂家分配的。也就是说如果有厂家想生产网卡这类需要mac地址的东西，必须先像管理机构申请前三位字节，所以网卡上的前三个字节就代表着某个厂家，后三个字节就是由厂家自己来设定的。

• 发送的数据帧最小要是64个字节,6个目的MAC地址，6个源MAC地址，2个字节代表数据包的类型，还有4个字节是FCS，用来进行CRC算法检测的，剩下的46个字节就是数据包最少要发送的字节数了，如果数据包实际发的少于46，那么会给这个数据包自动补充0，来达到需要的字节数。

• 插入的8个字节中，前7个字节用来使发送的数据帧的的比特同步，也叫作前同步码，最后一个字节，帧的开始定界符，也就是告诉接收方，从这个字节开始，后面就是MAC帧了。在接受MAC帧后，并不能马上识别出帧开始定界符，没有那么快的反应分辨出来，所以需要在前面加同步码，使接收方有反应的时间，所以同步码都是1010101010101这样的bit。前7个字节的同步码跟最后一个字节中的前6个bit位相同。