《计算机网络：自顶向下方法》的学习笔记。

这一章记录链路层有关知识

链路层概述

链路层其实就是最底层的，涉及到硬件的层。链路层中包含节点（运行链路层协议的设备）和链路（将相邻节点连接起来的通信信道）。链路层协议有很多很多种，但是基本上都会将来自网络层的数据报封装在自己的链路层报文中，然后发送给其他节点。

报文在链路层中的传输就像你从安徽到上海，先坐高铁从淮南到合肥，然后从合肥坐飞机到上海。那么你自己就是爆粉，淮南，合肥和上海就是节点，而高铁，飞机这种运输方法就是链路层协议。

链路层提供的服务

成帧：链路层会将上层报文封装在自己的链路层帧中（注意链路层不叫做报文而是帧）。由于链路层协议的不同，导致存在多种不同的帧格式。
链路接入：即传输帧
可靠交付：链路层提供可靠交付，也是通过确认和重传实现的。但是对于一些不易出错的链路（如光纤，同轴电缆等），可靠交付显得没有必要。所以很多链路层并不提供可靠交付。
差错检测和纠正：链路层可以检验数据的差错，并且在一定程度上纠正。

链路层在何处实现

链路层的主题部分是网络适配器，也就是通常意义上的网卡。网络适配器里面有很多专门的硬件提供链路服务（因为链路层传输要非常快才行），而且大部分服务也是用硬件直接提供的。

差错检测和纠正技术

奇偶校验

一维奇偶校验

这个也是很著名的校验方法。这种方法分为奇校验和偶校验。以奇校验为例，假设要传输数据D，那么在真正传输的时候在D后面附上一位，以使整个的数据中1的数目是奇数。然后接收方收到数据之后，检查数据中是不是1的数目加起来也是奇数，如果不是，就表示数据出错了。

比如我要传输$10010001$，这里有三个1，是奇数个，那么我在最后要附加一个0变成$100100010$，然后传输出去。

偶校验同理，需要让1的个数为偶数个。

奇偶校验是非常简单，但是也不是很可靠的方法。因为如果出错的是偶数个位，那么接收方是没办法得知数据出错的。而且奇偶校验方法并不能从错误中恢复数据。

二维的话提升了可靠性，并且允许在某些情况下纠正错误。主要的方法是将数据分成几组，排列成一个矩阵： $$ \begin{matrix} d_{1,1} & d_{1,2} & d_{1,3} & \dots & d_{1,n} \\ d_{2,1} & d_{2,2} & d_{2,3} & \dots & d_{2,n} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ d_{m,1} & d_{m,2} & d_{m,3} & \dots & d_{m,n} \end{matrix} $$ 然后在每一行和每一列后面加上一个位，来让这个行和列的1是奇数/偶数个： $$ \begin{matrix} d_{1,1} & d_{1,2} & d_{1,3} & \dots & d_{1,n} & c_{1,n+1}\\ d_{2,1} & d_{2,2} & d_{2,3} & \dots & d_{2,n} & c_{2,n+1}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ d_{m,1} & d_{m,2} & d_{m,3} & \dots & d_{m,n} & c_{m,n+1} \\ c_{m+1,1} & c_{m+1,2} & c_{m+1,3} & \dots & c_{m+1,n} & 0 \end{matrix} $$ 然后传输这个矩阵。

由于现在有行和列两个维度来校验，稳定性会比一维的好很多。接收方接收到数据之后，如果不仅能通过行列知道错误，某些情况下还能纠正错误，比如下面这种情况： $$ \begin{matrix} 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \end{matrix} $$ 可以看到第二行第二列的数据出错了，因为这个是偶校验，而第二行和第二列的1的个数都是奇数个。而且显然第二行第二列的0应当改成1，才能通过奇偶校验，所以我们就纠正了这个错误。

当然奇偶校验也不是万能的，如果错误多一些是没办法校验和检测到的。

检验和方法

这个方法在运输层中已经介绍过了，就是讲数据分成n组，然后将n组相加，用得到的和的反码作为校验码的方法。这种和叫做因特网检验和。

检验和也有可能没办法检测错误，而且没办法回复错误。

CRC

循环冗余检测（CRC)算法可以说是非常知名的一种算法了。这个算法基本上一定可以检测出错误，是很可靠的算法，不过不能回复错误。

其基本思想是将数据分为n组，在每一组后面加上一个m位的冗余码。通过这个冗余码，接收方可以进行差错检测（当然冗余码的位数是双方商量好的）。

这里用例子来说明。假设现在有一组数据111001记为$D$，那么步骤如下

计算冗余码：
1. 首先在数据后面加上m个0（m双方已知），假设这里m是3，那么数据变为111001 000，记为$D_{new}$
2. 然后双方会用实现商讨的一个除数Q来除这个$D_{new}$，这里假设除数是110，需要注意这里的除法是按照异或运算来算的，也就是说本来除法中的减法要改成异或，具体过程如下：
  
  我们要的是最后的余数。这里的余数是0。冗余码就是余数。
将冗余码附加到$D$后面（注意是$D$后面而不是$D_{new}$后面），这里余数是0，所以我们附加三个0.所以最后传输的数据就是111001000

那么接收方要如何验证呢？很简单，只需要再次用除数去除接受到的数据即可。如果余数为0表示没有错，不为0表示出错。

CRC的优点是非常可靠，缺点是计算量和发送量会变大。你可能会说，诶呀CRC这么牛逼，为什么不在运输层中使用呢？因为CRC的计算非常多，所以放在运输层会增加很多的传输时延。而链路层的CRC是通过专门硬件算的，算的飞快，所以可以在链路层使用。

多路访问链路和协议

链路层有两种类型的网络链路：

点对点链路：也就是说在发送方和接收方建立起单一链路。
广播链路：也就是说发送方发送出去的帧会被广播到所有在同一广播信道上的节点中。

点对点链路没什么可说的，问题在广播链路：如何协调多个发送和接收点对一个广播信道的访问呢？如果不加以控制的话，会产生多个信号同时在一条信道上传输的情况，这样信号之间就被影响了，我们称这个情况为碰撞。这种问题就叫做多路访问问题（本质上是避免碰撞）。为了解决这种问题，提出了多路访问协议。多路访问协议有三种，接下来看一下：

信道划分协议

这一种协议在第一章其实就说过了，其实就是应用时分复用和频分复用来传输帧。这种方式保证了节点之间的公平公正，但是有个缺点：时分复用TDM中，如果到一个节点的时间点但这个节点却不用发送/接收数据的话，这个时间点就被浪费了。在频分复用FMD中，虽然公平公正，但是每个节点也只能以一小段的频率发送信息。

随机接入协议

随机接入协议的核心思想是：每次信道发送信号总是以全速率发送，当发生碰撞时，就延时一个随机时间，然后在这个随机时间之后再发送。如果还发送碰撞，就再延时。

下面有两种典型的随机接入协议：

时隙ALOHA

协议如下:

所有帧由L比特组成
时间被划分为长度为L/R秒的时隙（一个时隙就是传输一帧的时间，R是传输的最高速率）
节点只在时隙开始的时候传输帧
节点是同步的，每个节点都知道时隙何时开始
如果在一个时隙中发现碰撞，就随机延时n个时隙之后再次发送。（精确的描述是这样：节点会以概率p在下一次时隙到来时发送）

如果在这个时隙发送成功了，这个时隙就叫做成功时隙。

ALOHA

时隙ALOHA要求所有节点同步传输（在每个时隙时传输），但是纯的ALOHA协议不需要。当网络层的报文到达之后，会立刻封装成帧并且发送出去。如果碰到了碰撞，会先等待一个帧传输时间，然后以概率p传输该帧，或者1-p的概率继续等待。

载波侦听多路访问（CSMA）

CSMA是一个非常拟人规则：

在说话前先听：如果在发送帧之前信道上有其他节点的活动，就等待直到存在一小段空闲的间隙再传输。这种传输前先听信道的方法叫做载波监听。
如果和他人同时说话，则停止说话：这种情况被称为碰撞检测，即如果在传输时发现有其他节点在干扰传输，则立刻停止并等待一个随机时间，然后再等待新的时间间隔。

这个时候就有人问了：那既然每个节点发送前都会监听，那为什么还会有同时说话的情况？这是因为信号传输时需要时间的，如果A发送信号后B还未监听到信号，那么B也会发送信号，这样A和B的信号就会碰撞了。

具有碰撞检测的载波监听多路过访问（CSMA/CD)

使用CSMA比较经典的协议就是CSMA/CD协议，其过程和CSMA一模一样，只不过在最后一步“立即停止并等待一个随机时间”中的随机时间上采用二进制指数后退算法，即在经历了连续的n此碰撞后，从集合${0,1,2,4,\dots,2^n-1}$中选择一个延时值。采用这种算法的好处是可以更快地找到空闲的时间，而不必做出大量等待时间。

轮流协议

主要分为两种

轮询协议

存在一个主节点，主节点以循环的方式询问信道上的各个节点：“你要不要发送/接受数据啊？”，如果得到了对方的肯定，就让对方占用信道。未被询问到的节点不能占用信道。

这个方法很快，都不需要碰撞检测算法。但是缺点很明显：如果主节点凉了，那整个信道通信就凉了。而且还加入了轮询所需的时间。

令牌传递协议

每个节点像是环链表一样，知道自己的下一个节点是谁，然后其中一个节点拥有令牌。拥有令牌的节点可以占用信道，如果此时不用，需要将令牌传递给下一个节点，以此类推。

这个协议效率贼高，但是也有缺点：万一令牌丢失了，或者某个节点忘了释放令牌，会造成堵塞。而且如果一个节点崩了，那整个循环就崩了。

链路层寻址和ARP

链路层寻址

网络层以上的层有IP地址进行寻址，那么链路层是如何找到对方的呢？答案是使用MAC地址（又称为LAN地址，物理地址）。

主机和路由器是没有链路层地址的，而是他们的网络适配器有链路层地址（通俗说就是地址在你的网卡里面）。具有多个网络接口的主机或路由器会有与之关联的多个MAC地址。

MAC地址长度为6字节，虽然MAC地址设计是写在硬件里面不可更改的，但是也有黑客可以通过软件伪造MAC地址。和IP地址一样，没有两个网路接口的MAC地址是一样的，MAC地址由IEEE组织管理。

一般写MAC地址都是两个字节为一组，以十六进制表示，并且以减号分隔，像是1A-23-F9-CD-06-9B。而且所有位是1的MAC地址是MAC广播地址，即经过这个地址的帧会被广播到局域网上的所有节点中。

这个时候有人问了：为什么有了IP地址还要有MAC地址呢？这是为了各层的独立。因为链路层上面并不一定要是网络层，还可以是其他的层（只不过当今网络体系基本都在用应用层到链路层这四层模型），所以链路层要单独有标识自己的地址，方便和其它层拼接。

ARP

ARP是地址解析协议，是将IP地址解析为MAC地址的一种服务。有点像链路层的DNS服务。其反向相依RARP将MAC地址解析为IP地址。链路层也是通过这个协议才能从网络层的IP地址得到目标的MAC地址。

ARP主要通过维护一个ARP表来进行地址转换，比如下面这种：

IP地址	MAC地址	TTL
222.222.222.111	88-FA-12-FA-8C-2B	13:45:00

其中TTL是这个行被记录时的时间。

如果MAC地址不在表内，发送方会构造一个ARP分组，然后将分组广播出去，得到ARP响应分组，从而得到MAC地址。ARP是即插即用协议，同时由于承载了IP和MAC两种地址，被称为跨越网络层和链路层的协议。

具体的ARP和RARP协议内容见《TCP/IP详解：卷一》。

以太网

以太网现在占据着几乎所有的有限局域网市场。在你看《TCP/IP详解》的时候你还会看到令牌环和FDDI网，那些都是以前和以太网竞争的网络类型，不过现在几乎都被以太网打败了。

以太网帧

以太网帧的格式如下：

前同步码 目的地址 源地址 类型 数据 CRC校验码

数据字段（46~1500）字节。以太网的最大传输单元（MTU）是1500字节。如果不同类型的网络连在一起的话，就必须选取多个网络的MTU中最小的，称为Path MTU的MTU。

目的地之和源地址都是MAC地址而不是IP地址。

类型用于表示当前帧是什么类型的服务，比如ARP服务或者其它。

CRC就是我们上面说的CRC校验码

前同步码是8个字节的，前七字节都是10101010，用于唤醒接收帧的适配器，并且将他们的时钟和发送方时钟同步，相当于快递告诉你“正在派送中”。第八个字节是的最后两位会警告接收方“重要的数据要来了”，相当于快递到你家楼下了，打电话给你说我已经到了，你在哪一层这种，这个时候你就要打开大门，等着快递上来。同样，接收方也会准备好接收数据。

交换机

以前以太网中使用的是集线器，集线器作用于每个比特，并且将其放大，相当于信号放大器。现在使用的是交换机，用于转发和过滤帧。过滤是决定搞一个帧应当转发到哪个接口还是要丢弃的功能，转发就是决定一个帧应当发送到哪个接口，并且发送的功能。

交换机也有一个类似于ARP表的交换机表：

地址	接口	时间
62-FE-F7-11-89-A3	1	9:13

如果没有地址，则广播帧来获得地址。而且在一定时间之后，没有用到的地址会被去除。

具体流程如下：

交换机初始列表为空
对于每个接口接收到的入帧，交换机存储地址，接口和帧到达的时间。
如果在一段时间（称为老化期）之后，交换机没有接收到以该地址作为源地址的帧，那么会将这个地址的信息删除。

交换机也是即插即用设备，并且是自学习的，不需要人工操作的。

交换机的优点如下：

消除碰撞：通过交换机的报文会被缓存，一个时间只会有一个帧传输
异质链路：如果两个链路的介质不一样，或者传输速率不一样，交换机可以自动适配。
管理：提供了网络安全性。如果一个适配器连续不断地发送帧，交换机可能会察觉到并且断开该异常适配器的连接。

计算机网络-6-链路层