链路层

概念

• 节点： 运行链路层协议的设备，例如主机、路由器等
• 链路： 将信息传输到相邻节点的通信信道
• 链路层帧： 数据报封装在链路层帧中

链路层提供的服务有：

• 链路接入： 媒体访问控制（MAC）协议规定了帧在链路上的传输规则，还协调了多个节点共享当个链路时的问题。
• 可靠交付： 和TCP协议一样，这里的可靠交付也是通过差错检测和重发保证的。
• 差错检测

链路层的主题是在网络适配器中实现的，也叫网络接口卡。

差错检测技术

奇偶校验

假设发送的信息中有d比特，那么发送方只需要附加上一个比特使得1的个数为偶数即可。接收方接收时检查是否有偶数个1那么就可以得知是否有差错。

但是这种检测方式检测出错的可能性很大，达到50%，因此需要一种更健壮的检测方式。

另一种方法时把这些比特划分成i行j列的矩阵，每一行每一列都有一个检验比特，这样不仅可以检测出错误还可以在出错时纠正他。

检验和方法

在运输层中使用了这个技术

循环冗余检测（CRC）

该检测方法的基本思路为： 在d位比特后加上r位校验比特，使得他可以被G正好整除。公式为：

$$D * 2^r XOR R = nG\\ D * 2^r = nG XOR R\\ R = remainder \frac{D * 2^r}{G}$$

其中第二个式子告诉我们如果使用G / (D * 2^r)，余数正好是R（remainder就是余数的意思）,另外这里的除法没有进位借位，遵循异或规则

例：

D = 101110
G = 1001
r = 3
      101011
1001----------
   101110000
   1001
   ----------
    1010
    1001
    ---------
    001100(注意是异或操作）
    001001
    ---------------
    0001010
    0001001
    ---------
       011
结果为011

多路访问链路和协议

如何协调多个发送和接收节点对共享广播信道的访问，就是多路访问问题。因为所有节点都可以传输帧，因此可能会出现由节点同时接收到多个帧，也称为碰撞。发生碰撞时，，所有的帧都会混杂在一起，也就是说没有一个帧是有效的。

信道划分协议

一种划分方式是时分多路复用（TDM）。他将时间划分成多个时间帧，然后在时间帧中划分N个时隙，每个时隙给一个节点使用。但是如果同时传输的节点少的话会造成巨大的资源浪费。

另一种方式是频分多路复用（FDM），他将R bps的信道划分成不同的频段，每个频段享有R/N的带宽。

第三种方式是码分多址（CDMA）。CDMA对每个节点分配一种不同的编码，然后每个节点使用这种编码方式对数据进行编码，这样的话就可以使得信息同时传输而不混淆。

随机接入协议

时隙ALOHA

首先进行下列假设：

• 所有帧由L比特组成
• 时间被划分成L/R秒时隙（一个时隙就是传输一帧的时间）
• 节点只在时隙起点传输帧
• 节点是同步的，每个节点都知道时隙何时开始
• 如果一个时隙中有碰撞，那么在时隙结束前所有节点都可以检测到该事件

p是一个频率，在每个节点中，时隙ALOHA的操作为：

• 当节点有一个新帧要发送时，它等到下一个时隙开始传输
• 如果没有碰撞，该节点成功传输，则无需重传
• 如果有碰撞，那么该节点在时隙结束前检测到该碰撞。该节点以概率p在后续的每个时隙中重传帧

假设每个节点都在试图以p概率传输一帧，那么该帧成功传输的概率为 $p * (1-p)^{N-1}$，求极限得最大效率为0.37。也就是说一个100Mbps速率的系统成功吞吐量为37Mbps

ALOHA

它没有时隙，每次直接传输，如果发生碰撞立刻以概率p重新发送，之后每隔一帧判断一次。

它的最大效率为时隙ALOHA的一半。

载波侦听多路访问（CSMA）

具有碰撞检测的CSMA

带有碰撞检测的情况下会检测信道是否有信号传输，如果没有再把数据传输上去。这种情况下也可能发生碰撞因为在数据传输但是没有传输到交换机上时是检测不到的，并且此时由于没有检测到，所以另外一个节点也开始传输。

如图所示，B首先进行传输，然后C检测到此时信道没有被占用也开始传输，于是两个信号发生碰撞导致两个信号都失效。此时由于两个信号混合在一起所以信号增强，可以检测出发生了碰撞。

1. 适配器从网络层获得数据报，准备链路层帧，并放入到帧适配器缓存中
2. 如果信道空闲则传输
3. 如果传输过程中发现该信到有其他适配器传输，则停止传输
4. 终止传输后，等待一个随机时间年，返回步骤2

这里要求随机时间量是因为多个适配器会在接近时间发现碰撞，如果等待相同时间同时传输则又会发生碰撞。

随机选择的时间在[0, 1, 2, …, $2^{n} - 1$]范围内，其中n是碰撞次数

它的效率为 $\frac{1}{1 + 5d{prop} / d{trans}}$

$d{prop}$表示信号在任意两个适配器传播所需最大时间，$d{trans}$表示传输一个最大长度的以太网帧的时间。

无线网络中的CSMA

由于无线网络信号衰减比较厉害，所以无法检测通过信号强度检测出是否发生了碰撞。

CSMA/CA中有两种避免碰撞的方法：

1. 检测一次信道。如果信道已被占用就选取一个随即回退值，并且在侦听到信道空闲时递减该值，直到该值为0。计数值为0后立刻发送整个数据帧
2. 如果收到了确认信息，则选取一个随机回退值并且重复上述过程。

第二种方法是首先发送一个RTS信息，等交换机发送CTS给节点才开始传输。如果两个信道同时发送RTS信息，那么还是会发生冲突，这时节点会在一段时间没有接收到CTS后重新发送。但是发送RTS和CTS也有花费，因此在实际中很少使用

在CSMA/CA协议中有时候会综合两种避免碰撞的方法。首先使用第一种方法，第一种方法成功后等待一定随机时间再使用第二种方法

轮流协议

轮流就是每个节点轮流来，他和前面的时隙ALOHA不同的是这里轮流的基础是帧而不是一定的时间。

一种实现方法为让一个节点作为主节点，由他向其他节点发送报文来告诉他可以传输几个帧，传输完成之后主节点又进行调度，告诉另一个节点它可以传送多少个帧（可以通过通道上是否有信号来判断是否传输完成）

另一种是用一个称为令牌的特殊帧在节点之间以某种固定次序传递。如果接收到令牌的节点没有数据要发送，那么它立刻发送给下一个节点。如果有数据要发送，那么它发送最大数目的帧数，然后发送令牌给下一个节点。

交换局域网

在链路层，帧不通过网络层地址进行传输和识别，他有自己的一套寻址方法

如图，方形式链路层交换机，而圆形是路由器。而通过链路层交换机就完成了一个微型的网络。

链路层寻址

MAC地址

实际上不是主机或路由器有链路层地址，而是适配器（网络接口）有链路层地址，也就是说一个主机上可能有多个链路层地址。注意链路层交换机上并没有链路层地址，交换机自行发送而不需要主机或者路由器明确到哪个交换机。

MAC地址具有两个字节，通常是以16进制进行描述。例如: 1A-23-F9-CD-06-9B。他和IP的一点区别是MAC地址不可改变（虽然现在通过某些软件也可以改变）。

MAC地址没有相同的，因为IEEE在进行管理，一般是IEEE控制前24个比特，后24个比特由购买商自己决定。

地址解析协议

我们可以获得目的IP是因为DNS解析，但是我们怎么获得目的适配器（主机）的MAC地址呢？这就需要ARP了。

ARP可以将IP地址转换成MAC地址。他和DNS作用类似但是又有不同。DNS可以在全球范围内解析但是ARP只能解析同一个局域网中的地址。

ARP是通过ARP表进行工作的，ARP表包含IP地址、MAC地址、TTL三部分，例如：

IP地址	MAC地址	TTL
222.222.222.221	88-B2-2F-54-1A-0F	13:45:00
222.222.222.223	5C-66-AB-90-75-B1	13:52:00

这个表并不包含所有MAC地址。并且它的过期时间一般也不长（20分钟），想要通过这个表找到目标MAC地址，就需要发送一个特殊的ARP分组。ARP分组包括发送和接收的IP和MAC地址。

• 如果ARP表中有对应IP，则直接返回MAC地址
• 向适配器发送一个ARP分组，并且适配器通过MAC广播地址发送分组。
• 接收到ARP分组的模块都检查自己的IP地址。如果匹配就发送响应分组。与此同时将发送方的IP和MAC记录到ARP分组中

以太网

以太网是一种有限局域网

结构

发送适配器将以太网帧发送到物理层，然后接收适配器从物理层中接收到帧并且提取出IP数据报将其传递到网络层。

以太网帧分为六个字段，分别是：

• 数据字段（46 - 1500字节）： 这个字段承载IP数据报
• 目的地址： 目的地址是MAC地址
• 源地址：
• 类型字段（2字节）： 类型字段允许以太网复用不同的网络层协议。
• CRC（循环冗余检测， 4字节）： 检测帧是否有差错
• 前同步码（8字节）： 前同步码的前7个字节都是10101010， 最后一个字节是10101011. 它的作用是唤醒接收适配器，并且将它的时钟和发送方时钟同步

链路层交换机

链路层交换机进行过滤和转发。过滤指的是拒绝某些帧，转发指的是发送到某个输出接口。他们都依赖交换机表，例如

地址	接口	时间
62-FE-F7-11-89-A3	1	9:32
7C-BA-B2-B4-91-10	3	9:36

交换机表和ARP表类似，都不包含所有的表项。当一个帧传输到交换机时，有几种可能。

首先假设从x接口进入

1. 如果表中没有对应地址，则向除x外的接口发送该帧的副本
2. 如果表中有地址并且接口不是x，则发送到对应接口
3. 如果表中有地址并且接口是x，则直接丢弃。（因为这表明它已经在这个接口内广播过了）

交换机表具有自学习功能，它可以自动更新表项。每次有入帧就将发出地址和接口记录。并且在一段时间后会抛弃表项。

具体过程为：

1. 交换机表初始为空
2. 对于每个接口接收到的帧，该交换机在表中存储该帧的源地址字段的地址和到来的接口及时间。
3. 经过一段时间后，如果没有收到以该地址作为源地址的帧，那么就删除这个地址。（表示没有发送到这台机器上的数据）

虚拟局域网

局域网一般都是一块一块的，每个部分都有自己的交换机，并且交换机之间互联。但是这种构建方式有一些缺点。

• 缺乏流量隔离： 限制流量的作用，一是限制广播的流量来改善局域网的性能，二是有利于安全保护
• 交换机的无效使用： 例如有很多个小组，每个小组都只有很少的人，如果每个小组都需要一台交换机的话就会带来流量的浪费，但是如果只用一台交换机就无法流量隔离。
• 管理用户： 用户的位置发生改变就需要改变物理布线。

为了解决这些难题，提出了虚拟局域网（VLAN）。虚拟局域网可以在一个物理设备中定义多个虚拟局域网。一种方法时交换机端口由管理员进行分组，每一组可以看成一个虚拟局域网，广播时也只会从这个虚拟局域网中发出而不是直接发送到所有端口。

具体可以在交换机中维护一张端口到VLAN的映射表，交换机仅在相同VLAN的端口之间交付帧。

但是如何把一个VLAN中的数据传输到另外的VLAN？一种方式是将VLAN交换机的一个端口和外部路由器相连，这样经由路由器就可以实现VLAN的数据传输了（有时在交换机内部就有一个路由器）。

一种扩展性较好的交换机互联方式为VLAN干线链接。也就是交换机上有一个端口和其他交换机链接，所有的VLAN共享这个端口，可以通过这个端口传递数据到其他交换机上。这时为了识别不同的VLAN，需要在以太网帧首部加上四字节的VLAN标签。