这一章讲了链路层的一些知识。

概述

在这一节当中，把设备称为节点，把通信信道称为链路。

链路层提供的服务

它可能可以提供以下的服务：

  • 成帧：链路层封装IP数据报，帧的结构由链路层协议规定。
  • 链路接入：媒体访问控制协议（Medium Access Control，MAC）规定了帧在链路上传输的规则。对于一对一的链路来说，协议实现很简单，但是当一个链路上有多个节点的时候，情况就复杂了起来。
  • 可靠交付：如果链路层实现可靠交付，通常是通过确认和重传取得的。对于高比特差错的链路来说，链路层通常要实现可靠交付，比如无线传输链路而不是通过运输层或应用层协议迫使进行端到端的数据重传。对于低比特差错的链路来说，可靠交付将是不必要的开销，出于此，许多链路层协议不提供可靠交付服务。
  • 检错和纠错：实际链路传输的时候，需要考虑是由信号衰减和电磁噪声导致的。上层也提供了有限的差错检测，也就是因特网检验和，IP校验了它的首部字段，TCP，UDP校验了全部字段。

链路层是现在何处（在硬件端）

链路层的主体部分是在网络适配器（network adapter）中实现的，网络适配器有时也称为网络接口卡（Network Interface Card，NIC）。位于网络适配器核心的是链路层控制器，该控制器通常是一个实现了许多链路层服务（成帧、链路接入、差错检测等）的专用芯片。因此，链路层控制器的许多功能是用硬件实现的。

在以前网卡是一个独立的硬件模块，现在已经被综合进了主机主板上，能连接什么类型的网络看网络控制器实现了什么协议，比如Intel的710控制器实现了以太网协议，那么该主机能够接入以太网。而手机的网卡实现了WIFI协议，那么我们能够接入WIFI网络。

差错检测和纠正技术

主要有两点，一个是检错，一个是纠错。

即使我们采用差错检测比特，也不一定能检测出所有的比特差错，但是我们需要更精确的检错或者纠错就会让链路层产生更大的开销。

我们现在来研究在传输数据中检测差错的3种技术：

  • 奇偶校验
  • 检验和方法
  • 循环冗余检测

奇偶校验

在很长的一串比特中最后添加一位：使得这一串比特序列总是含有奇数个或者是偶数个的1，这是最简单的奇偶校验。它只能检错，甚至不能检到具体的错误位置。

奇偶校验可以扩展到二维使得它可以纠错并且知道错误的具体位置。

若是同时在一行或者一列中出现了两个差错，则它能检测但不能纠正此错误。

接收方检测和纠错的能力被称为前向纠错（Forward Error Connection，FEC）。

检验和方法（checksum）

将所有的数据相加得到一个值，因特网检验和就是基于这种方法，在 TCP，UDP协议中，这个检验和检验它传输层的所有的数据，IP层中，因特网检验和只检测它首部的数据。

因特网检验和的具体方法是，将要检测的数据分为两个字节一组，如果不足则最后一个字节用 0 填充。随后每两个连续的字节做加法，需要注意的是，需要保证加法结果在 16 位内，如果最高位进位则当作最低位 1 来处理。最后得到一个结果取反则是检验和的值。在检验的时候，对所有的每两字节进行相加，如果最后得到的结果为全 1，则说明正确。

相比循环冗余校验，它只用较小的开销且提供较弱的差错保护。而链路层的差错检测就是使用循环冗余校验，因为在网络适配器中有专门的硬件去实现这个功能。

循环冗余检测（CRC）

首先确定一个 r+1 的比特位，作为生成多项式G，且要求最高位必为1，然后把 d 位的数据位左移 r 位得到一个值，如下图所示：

然后用这个值去除之前给定的比特模式。

在除法过程中，加法不进位，减法不借位，因此加减都变成异或运算了

最后会得到 r 位的余数，那么这个余数替换掉最后末尾的 r 位 0 就是最后的数据位了，CRC 在检验的时候会计算整个比特位是否可以被 r+1 位的模式除且不留余数，如果可以那就说明数据是正确的，如果不是就说明数据传输发生了偏差。

以下是关于 CRC 的一个计算过程：

多路访问链路和协议

本章主要又两种类型的网络链路，点对点和广播链路。广播链路会涉及到多路访问问题（multiple access problem）。

考虑这样一个协议集：

“给每个人一个讲话的机会。”
“该你讲话时你才说话。”
“不要一个人独占整个谈话。”
“如果有问题请举手。”
“当有人讲话时不要打断。”
“当其他人讲话时不要睡觉。”

计算机网络有类似的协议，也就是所谓的多路访问协议（multiple access protocol）

因为所有的节点都能收发帧，因此传输的帧可能回发生碰撞。当碰撞发生时，没有一个接收节点能够有效地获得任何传输的帧，在大量的链路层技术中已经实现了几十种多路访问协议。尽管如此，我们能够将任何多路访问协议划分为3种类型之一：

  • 信道划分协议（channel partitioning protocol）
  • 随机接入协议（random access protocol）
  • 轮流协议（taking-turns protocol）

我们希望协议具有以下特性：

  1. 当仅有一个节点通信的时，该节点具有 R bps 的吞吐量。
  2. 有M个节点发送数据时，每个节点具有 R/M bps 的吞吐量。
  3. 协议是去中心化的，一个节点的崩溃不会导致整个系统崩溃。
  4. 协议是简单的，实现起来并不昂贵。

信道划分协议

主要有时分多路复用（TDM）和频分多路复用（FDM）。

TDM将时间划分为时间帧（time frame）,并进一步划分每个时间帧为N个时隙（slot）。

TDM是有吸引力的，因为它消除了碰撞而且非常公平：每个节点在每个帧时间内得到了专用的传输速率 R/N bps。他有主要的两个缺陷：一个是节点速率被限制死了，第二个就是如果当它是唯一要发送的节点时，它也不得不等待自己的时隙再发送，浪费了大量带宽。

第三种信道划分协议是码分多址（Code Division Multiple Access，CDMA）。

随机接入协议

第二大类多访问协议是随机接入协议。一个传输节点总是以信道的全部速率（即 R bps）进行发送。当遇到碰撞的时候，涉及碰撞的每个节点反复地重发它的分组，到该帧无碰撞地通过为止。

它肯定不会立刻发送，因为如果双方都立刻发送肯定又会发生碰撞，它在重发该帧之前等待一个随机时延，这个时延会独立地随机选择。因为如果双方延迟一样的时间，那么再次发送一样也会发生碰撞。于是让它们分别随机等待就会有这样的结果出现：这些节点之一所选择的时延充分小于其他碰撞节点的时延，并因此能够无碰撞地将它的帧在信道中发出。

随机接入协议最常用的有两种：ALOHA协议和载波监听多路访问（CSMA）协议，以太网就是一种流行并广泛部署的 CSMA 协议。

时隙ALOHA

这是比较简单的随机接入协议，做如下假设：

  • 所有帧由L比特组成。
  • 时间上被划分为 L/R 秒的时隙，也就是刚好传输一帧的时间。
  • 节点只会在时隙起点开始传播。
  • 节点之间是同步的，它们都清楚的知道当前是否是时隙起点。（这个同步往往是比较难的）
  • 如果发生碰撞，那么发生碰撞的这个时隙的结束所有节点都知道发生了碰撞。
  • 对于发送的事件，只需要考虑三点：
    • 当有个帧要发送时，等待下一次最近的时隙发送。
    • 如果没有碰撞，则该时隙发送成功。
    • 如果有碰撞，那么该节点以 p 的概率在后续的时隙重传该帧（1-p的概率在此时隙不重传，而在下个时隙继续以p的概率重传）。

时隙ALOHA有以下优点：

  • 唯一活跃的节点能占用整个信道的带宽，以全速率发送。
  • 时隙ALOHA也是高度分散的，因为每个节点检测碰撞并独立地决定什么时候重传。
  • 时隙ALOHA也是一个极为简单的协议。

这里进行了多个活跃节点效率的计算，具体计算过程不需要掌握，需要记住它最后的效率是 1/e≈0.37。

ALOHA

它不需要同步时隙，但是效率相比时隙ALOHA下降了一半。

载波侦听多路访问（CSMA）

对于人类来说，为了获得更多的数据量，有礼貌的人类交谈有两个重要的规则：

  • 说话之前先听。在网络领域中，这叫载波侦听（carrier sensing）
  • 如果与他人同时开始说话，停止说话。在网络领域中，这叫碰撞检测（collision detection）

这两个规则包含在载波侦听多路访问（Carrier Sense Multiple Access，CSMA）和具有碰撞检测的 CSMA（CSMA with Collision Detection）。

可以用一张时空图来说明为什么进行了载波侦听还是会发生碰撞：

在途中的时刻，B在t0的时候开始传输，而 D 在t1的时候并没有听到 B 正在传输，因此它也开始发，于是产生了碰撞。

显然广播信道的端到端信道传播时延（channel propagation delay）越长，载波侦听节点不能侦听到网络中另一个节点已经开始传输的机会就越大，效率就会变低。

具有碰撞检测的载波侦听多路访问（CSMA/CD）

从网络适配器的视角来讲解 CSMA/CD：

  1. 适配器从网络层一条获得数据报，准备链路层帧，并将其放入帧适配器缓存中。
  2. 如果适配器侦听到信道空闲，它开始传输帧。如果正在忙，那么重复步骤2。
  3. 在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。（边发送边检测）
  4. 如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成 了该帧。在另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，它中止传输。
  5. 中止传输后，适配器等待一个随机时间量，然后返回步骤2。

用于以太网以及 DOCSIS 电缆网络多路访问协议中的二进制指数后退（binary exponential backoff）算法，简练地解决了这个问题。在连续经历过 n 次碰撞后，节点随机地从 ${0,1,2,…,2^n-1}$ 中选择一个 K 值作为等待的时间。因此，一个帧经历的碰撞越多，K选择的间隔越大。对于以太网，一个节点等待的实际时间量是 Kx512比特时间（即发送512比特进入以太网所需时间量的K倍），n 能够取的最大值在10以内。

因为每次碰撞，选择等待的集合呈指数增长，因此该算法被叫做二进制指数后退。

CSMA/CD 效率

显然，当只有一个节点有一个帧发送时，该节点能够以信道全速率进行传输。然而，如果很多节点都有帧要发送，信道的有效传输速率可能会小得多。令 $d_{prop}$ 表示信号能量在任意两个适配器之间传播所需的最大时间。令 $d_{trans}$ 表示传输一个最大长度的以太网帧的时间。

最后我们得到效率为 $\frac{1}{1+5\times\frac{d_{prop}}{d_{trans}}}$。当 $d_{prop}$ 趋于0的时候，效率趋于 1，因为如果没有传播时延，则根本不会发生碰撞，因为监听总能实时判断出当前信道是否空闲。当 $d_{trans}$ 趋于无穷的时候，传输效率也趋于 1，因为一个帧取得信道之后，它将占用很长的时间，因此大的部分时间都在有效工作。

轮流协议

同样也有两种：一种是轮询协议（polling protocol），一种是是令牌传递协议（token-passing protocol）

轮询协议：是中心化的一个协议，存在一个主节点，主节点会向每个节点发送一个报文，告诉它能够传输的最多数量的帧。会通过一定的选择算法去安排这些节点传输，并且主节点会有一定的方式判断节点是否活跃，而轮询只会轮询活跃的节点。但是主节点的崩溃会导致整个系统不可用。

令牌传递协议：蓝牙就是使用的这种协议。一个称为令牌（token）的小的特殊帧在节点之间以某种固定的次序进行交换。如果拥有令牌且刚好有帧需要传输，那么它发送最大数目的帧数，然后把令牌转发给下一个节点，令牌传递是分散的，并有很高的效率，但是同样一个节点的崩溃也会导致整个系统崩溃。

DOCSIS：用于电缆因特网接入的链路层协议

略

交换局域网

使用链路层交换机可以构建一个大型的局域网，最著名的交换局域网就是以太网了，交换局域网使用链路层地址而不是使用IP地址来转发链路层帧。以下是一个交换局域网的例子：

链路层寻址和 ARP

事实上，为了保证各层独立的选择，链路层地址是必不可少的。因为局域网应当能为任何网络层协议去服务，有可能网络层并不是IP，因此网络适配器无法工作在非 IP 协议的网络层协议中。

MAC地址

链路层地址有各种不同的称呼：LAN地址（LAN address）、物理地址（physical address）或MAC地址（MAC address）。因为MAC地址似乎是最为流行的术语，所以我们此后就将链路层地址称为MAC地址。

MAC 地址并不属于某一个主机或者路由器，而是属于一个网络适配器（也叫网络接口），因为数据链路层的主体是网络适配器。

MAC地址长度为6字节（一般用12个十六进制数表示），共有 $2^{48}$ 个可能的MAC地址，尽管 MAC地址被设计为永久的，但用软件改变一块适配器的MAC地址现在是可能的。因为可以通过直接进入特权模式对硬件进行操作，如果我能直接对网络适配器操作，那么我可以构造任意的链路层帧发送，而链路层帧有一个字段指示了源MAC地址。这里不需要考虑特殊的情况，我们仅仅假设MAC地址是固定不会变的。

IEEE分配MAC地址的方式是，前24位固定，分配给厂商，后24位由制造厂商决定，只要它不重复那么便可以达到MAC地址全球唯一的特点。

MAC地址有一个特殊的广播地址 FF-FF-FF-FF-FF-FF 也就是二进制看来为全 1 的地址。

地址解析协议（ARP）

为了能在链路层传输数据，我们在传输的时候需要把 IP 地址解析成 MAC 地址。这个地址解析只能在局域网中解析，解析非局域网的 IP 地址将返回错误。

每个节点的网络适配器都会有一个 ARP 模块，并且包含一个 ARP 表，包含了 IP 地址到 MAC 地址的映射关系。当我要转发的 IP 地址存在于 ARP 表时，我能直接构造出帧发送，如果不存在则在发送之前需要先发送一个 ARP 分组。ARP 分组有三个字段：

  • 要查询的IP地址
  • 自己的IP地址
  • 自己的MAC地址

对于一个 ARP 分组，它的目的 MAC 地址应当是一个广播地址（FF-FF-FF-FF-FF-FF）。

ARP 被理解为链路层协议比较合理。

发送数据报到子网以外

如果要跨网段传输数据，那么需要使用到路由器了。来看下面一个例子：

路由器连接了 111.111.111.0/24 的网段和 222.222.222.0/24 的网段

如果 222.222.222.222 的机器想给 111.111.111.111 的机器发送一个数据报，首先 ARP 只能在局域网中传输，不能跨路由器，这一点需要知道，那么 222.222.222.222 的机器通过网卡 49-BD-D2-C7-56-2A 封装的链路层数据报的目的地址肯定只能是 222.222.222.220 或者说 222.222.222.221 IP 地址所对应的 MAC 地址，这显然会是路由器那边的MAC地址。

事实上，当IP层得知目的地址不在自己的局域网网段的时候，它就会把当前链路层的目的地址设置为当前默认网关地址所对应的MAC地址，发送一个 ARP 分组获取到 MAC 地址封装好后给到路由器。

路由器通过查路由表，获取到下一跳的地址，路由器内部，接收到分组的网络适配器就会把数据报转交给另一个网络适配器，并且在数据链路层中，源地址被替换为另一个网络适配器的MAC地址。

但是路由器可能不知道 111.111.111.111 的 MAC 地址，因此此时还需要发送一个 ARP 分组来确定 MAC 地址，获取到 MAC 地址之后，替换对应的目的MAC然后转交出去，目的帧到达节点。

以太网

以太网之所以能成为应用范围最广的局域网，完全处于它部署的早，简单，高效。

在20世纪90年代后期，局域网主要基于集线器这种物理层设备，集线器的主要作用就是将一个端口的比特重新放大广播给其它端口。

后面集线器被交换机所替代，而交换以太网主要就是通过链路交换机实现的。

以太网帧的结构

解释下上面的六个字段：

  • 数据字段（46 ~ 1500字节）：这个字段承载了IP数据报，以太网的最大传输单元（MTU）是1500字节。这意味着如果IP数据报超过了 1500字节，则主机必须将该数据报分片。
  • 目的地址（6字节）：这个字段包含目的适配器的MAC地址
  • 源地址（6字节）：这个字段包含了传输该帧到局域网上的适配器的MAC地址
  • 类型字段（2字节）：类型字段允许以太网复用多种网络层协议，而不仅仅是适用于 IP 协议。在下图中我抓了一个包，可以看到 IP 数据报的这个类型值为 0x0800，而 ARP 分组的类型字段值为 0x0806
  • CRC（4字节）：冗余校验位
  • 前同步码（8字节）：这个值是固定的为 0xAA,0xAA,0xAA,0xAA,0xAA,0xAA,0xAA,0xAB，在二进制看来就是 1010101010101010101010101010101010101010101010101010101010101011，全 10，最后连续的两位 11，表明重要的内容就要到来了。

以太网是提供无连接，不可靠的服务。

以太网技术

事实上，以太网具有许多不同的特色，具有某种令人眼花缭乱的首字母缩写词，如10BASE-T、 10BASE-2、100BASE-T、1000BASE-LX和10GBASE-T。

首字母缩写词的第一 部分指该标准的速率：10、100、1000或10G，分别代表10Mbps、100Mbps、1000Mbps （或1Gbps）和10Gbps以太网。“BASE”指基带以太网，这意味着该物理媒体仅承载以太网流量。该首字母缩写词的最后一部分指物 理媒体本身；以太网是链路层也是物理层的规范，并且能够经各种物理媒体（包括同轴电缆、铜线和光纤）承载。一般而言，“T”指双绞铜线。

可以发现，随着时间增长，以太网的速率也出现质的飞跃。并且发展也不能抛弃已安装的以太网，要有向后兼容的特性。

还有一个历经30年保持未变的持久不变量，即以太网帧格式。也许这才是以太网标准的一个真正重要的特征。

链路层交换机

链路交换机的作用就是接收入链路层帧并将它们转发到出链路，交换机对子网中的主机和路由器是透明的，交换机输出接口设有缓存来解决帧速率暂时超过链路容量的问题。

交换机转发和过滤

过滤是指，交换机是应当转发还是丢弃某个帧。

转发是指，决定帧该被导向哪个接口交换机的过滤和转发借助于交换机表（switch table）完成

一个交换机表应当包含目的MAC地址和通向该目的MAC地址的端口，以及时间字段。

在源端口为x的交换机转发一个帧的时候可能遇到下面的三种情况：

  • 目的地址不在表项：交换机广播该帧，广播的端口不会包括x。
  • 目的地址在表项，且对应端口==x，交换机丢弃该帧。
  • 目的地址在表项，且对应端口!=x，交换机往目的端口y转发该帧。

自学习

交换机它的表是自动、动态和自治地建立的，即没有来自网络管理员或来自配置协议的任何干预。换句话说，交换机是自学习（self-learning）的。

有以下的步骤：

  • 交换机表初始为空。
  • 对于在每个接口接收到的每个入帧，该交换机在其表中存储：①在该帧源地址字段中的MAC地址②该帧到达的接口③当前时间。交换机以这种方式在它的表中记录了发送节点所在的局域网网段。如果在局域网上的每个主机最终都发送了一个帧，则每个主机最终将在这张表中留有记录。
  • 如果在一段时间（称为老化期（aging time））后，交换机没有接收到以该地址作为源地址的帧，就在表中删除这个地址。

交换机是即插即用设备（plug-and-play device），因为它们不需要网络管理员或用户的干预。交换机也是双工的，每个端口可以接收也可以发送数据。

链路层交换机的性质

交换机具有以下特点：

  • 消除碰撞：交换机采用了基于MAC地址的转发方式，能够根据MAC地址表精确地将数据包转发到目标设备，从而避免了广播方式下的碰撞，也就避免了因碰撞而浪费的带宽。
  • 异质的链路：可以同时连接不同种类的链路。对于原有的设备与新设备混用，交换机是理想的。
  • 管理：如果一个适配器工作异常并持续发送以太网帧，交换机能够检测到该问题，并在内部断开异常适配器。

交换机和路由器比较

从优缺点比较，交换机是即插即用的，交换机只需处理第二层的数据，交换机无法对广播风暴提供任何保护措施。

路由器需要人为手动配置IP地址，需要处理高至第三层的数据，因此处理的会比交换机慢，但是它可以对第二层的广播风暴提供防火墙保护。

虚拟局域网

前面提到的交换机有三个缺点：

  • 缺乏流量隔离。
  • 如果要做到流量隔离，则可能使得交换机大部分端口未使用。
  • 管理用户困难。

幸运的是，这些难题中的每个都能够通过支持虚拟局域网（Virtual Local Network，VLAN）的交换机来处理。顾名思义，支持VLAN的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网。

比如这里我们让端口 2-8 属于电气工程系的 VLAN。9-15 端口属于计算机科学系的 VLAN，在广播的时候这些 VLAN 只在自己所在的 VLAN 内广播，这样就起到了隔离的作用。

端口可以配置为干线（trunk）模式，这个模式的端口属于所有 VLAN。

为此我们会在帧出交换机和进交换机的时候分别剥离或打上一个 VLAN 标签：

  • TPID（Tag Protocol Identifier）：16位字段，用于标识VLAN标记头的类型，通常取值为0x8100。
  • PRI（Priority Code Point）：3位字段，用于指定帧的优先级。在802.1Q中，PRI的值越小，优先级越高。
  • CFI（Canonical Format Indicator）：1位字段，用于指示MAC地址是否遵循规范格式。
  • VLAN ID（VID）：12位字段，用于指定VLAN的ID号，最多支持4096个VLAN。

交换机如果分配了VLAN，那么每个端口有 Access 或者 Trunk 模式，进入 Access 的包如果无 VLAN ID，那么打上自己这个端口的 VLAN ID，进入交换机内部，对 Trunk 口同理，Access 口会直接丢弃带有 VLAN ID 的数据包，因为它不支持处理并识别带有 VLAN ID 的数据包，Trunk 口会检查 VLAN ID 是否在交换机的允许范围之内，如果是那么进入，否则丢弃。

对于把数据包发出端口，Access 模式不会管那么多，直接剥离 VLAN ID 发出即可，Trunk 模式会检查发送的端口是否为目的 VLAN 端口，如果不是则原封不动发出，如果是则剥离 VLAN ID 发出。

链路虚拟化：网络作为链路层

后面的对我而言并不是很重要了，直接小结吧。

小结

这一章学习了一下链路层的理论协议，详细了解了一下以太网和二层交换机，感觉把之前学的都串起来了。沿协议栈向下的旅程现在结束了，还有一层其是物理层，但是实际上这本书并没有详细介绍物理层，而是把它归到了通信这门课，想想也合理吧，

3 月 8 号开始看这本书，花了一个半月的时间看完，我也不知道对我是否有太多的帮助，但是我是不太喜欢被拘束的，想学什么就学什么，希望对我后面复习计网有较大的帮助吧。