《计算机网络自顶向下方法》学习笔记04:链路层。

网络层实现的是主机到主机之间的通信。链路层则是解决分组在各段链路上传输的问题。

第五章 链路层

1.概述

在网络中，每一个设备都可以称作是一个节点，包括主机，交换机，WiFi接入点。沿着相邻节点的通信信道称为链路(link)。为了将数据报传输到目的主机，数据报必须经过各段链路传输。链路层主要讨论的就是数据报在链路上传输的问题。在链路层，数据报被添加上首部和尾部(校验位)，被称为帧。链路层主要提供以下的服务，本章也主要介绍以下内容的相关问题：

  • 封装成帧：网络层数据报经链路传输之前，需要封装成帧。
  • 链路接入：规定帧在链路上传输的规则(媒体访问控制协议MAC)。
  • 可靠交付：在易于产生高差错率的链路中，可能提供可靠交付服务。由于在运输层也提供了可靠交付的服务，在链路层提供该服务不是必要的，许多链路层协议不提供可靠交付服务。
  • 差错检测和纠正：检测在链路层传输过程中的差错，并可能进行纠错。

以上链路层的服务主要在路由器的线路卡或主机的网络适配器中实现的。原来的网络适配器通常是一张卡，可以插入PC的PCI卡槽，现在的网络适配器基本上都综合到了主机的主板。大部分链路层在硬件中实现，但还有一部分在主机CPU的软件实现，因此链路层是整个网络层次中硬件与软件交接的位置。

2.差错检测和纠正技术

链路层提供了比特级的差错检测和纠正，对于节点之间传输可能发生的错误进行检测与纠正。为了检错与纠正，要在数据的尾部添加一些比特。差错检测和纠正只能尽可能的检测错误并纠正，并不能处理所有的错误。接下来主要介绍三种差错检测技术：奇偶校验(检错与纠错的基本思想)，检验和(主要用于运输层)，循环冗余检测(通常应用在链路层)。

2.1 奇偶校验

奇偶校验是最为简单的差错检测和纠正技术。给数据添加一个附加的bit，使数据以及这一位的值中有偶数个1，这就是偶校验，奇校验同理。显然，奇偶校验码只有发生了奇数个错误的时候才可以检出，偶数个错误无法检出。而且这样也无法进行差错纠正。如果需要进行差错纠正，需要使用二维的奇偶校验码，把数据表示为行和列，对每行和每列都添加一个奇偶校验码，就可以定位到错误的位置，纠正错误。

2.2 检验和

检验和方法就是将所有数据的bit加起来，用得到的和作为检错码。在运输层的TCP和UDP就是使用检验和进行差错检测，将所有数据的bit求和，然后取反作为检验和，接收方将数据和检验和求和，得到的是全1则说明没有产生差错。

检验和的差错检测能力较弱，显然多个错误还是可能检测不出，因此在链路层中采用了循环冗余检测(CRC)方法进行差错检测和纠正，循环冗余检测更为复杂，但是由于链路层主要在硬件上，可以使用硬件实现检测，因此可以快速得到循环冗余检测的结果。

2.3 循环冗余校验

在链路层上广泛应用的差错检测技术是循环冗余检测编码CRC，也称为多项式编码。

CRC编码中，发送方与接收方首先约定一个生成多项式，一个多项式对应了一个01串。例如多项式:

对应的01串是11011。假设数据为D，CRC冗余位为R，则DR应该可以整除该多项式对应的01串。由此，可以先假设R=0000，位数是多项式的最高次项(即多项式01串有5位，余数最多只有4位)，然后用DR除多项式对应的01串，得到的余数就是CRC冗余位。在书中有这种计算方法的详细证明。需要注意，每一步算余数进行的是异或运算，例如下图中第一位结果取1，1010与1101异或得到111，再继续运算。

image-20221201231249088

每个CRC都可以检测小于r+1位的突发差错。在国际标准中，已经定义了各个位数的生成多项式。

3.多路访问链路和协议

网络中的链路有两种类型：点对点链路和广播链路。点对点链路中，一个链路上只有一个发送方和接收方，只需要正常发送和接收数据。而广播链路中，许多节点都连接在相同的，共享的，单一的广播信道上，在这样的信道上传输数据。以太网和无线局域网都是使用广播链路，这里也先介绍并重点介绍广播链路的协议和技术。

在广播链路上，许多节点都需要发送和接收数据，必须协调各个节点对信道的访问，这就是多路访问问题。有许多不同的多路访问协议用于解决该问题，这些协议可以被划分为三类：

  • 信道划分协议：信道资源被预先划分。
  • 随机接入协议：传输节点总是以信道全部速率进行发送，如果发生了碰撞，就反复重发该帧，直到成功发送。每次重发之前要等待一个随机的时延，每个节点的时延都是独立的，因此节点可能交错发送数据，这样就可以在共享信道上完成数据传输。
  • 轮流协议：节点轮流发送。

在理想情况下，总是希望多路访问协议具有以下特性：

  • 仅有一个节点时，节点具有信道最大速率R bps的吞吐量。
  • 有M个节点时，每个节点有R/M bps的吞吐量。
  • 协议是分散的，不会因某个主节点的故障而使整个系统崩溃。
  • 协议是简单的。

下面分别介绍这三类协议：

3.1 信道划分协议

信道划分协议是在共享信道节点之间划分广播信道带宽的协议。按照划分的方法，主要分为三种：时分多路复用TDM、频分多路复用FDM、码分多址CDMA。

时分多路复用TDM是将时间划分为时间帧，再将时间帧划分为时隙。每个节点在循环的时间帧中都占有一个时隙，在这个时隙内发送数据。时隙的长度保证至少能传输一个数据分组。TDM的缺点在于，无论一个节点是否需要发送数据，他都拥有一个时隙，当其不发送数据时，这个时隙就被浪费掉了。

频分多路复用FDM将R bit/s的信道划分为不同的频段，假设有N个节点，则每个频段的带宽只有R/N，每个节点使用一个频段。FDM的缺点也是显然的，限制了一个节点只能使用R/N的带宽，无论其他节点是否有数据要发送。

码分多址CDMA不对信道进行划分，而是为每个节点分配一个不同的编码，在信道中，节点使用唯一的编码来传递数据，这使得不同的节点可以同时传输，而数据接收方只要知道编码就可以正确接收，不在乎其他节点的干扰。CDMA与无线信道紧密相关，在无线网络章节中有重点讨论。

3.2 随机接入协议

随机接入协议中，节点总是以全部速率发送数据，当有碰撞时，就重发发生碰撞的帧，直到该帧成功发送。但是重发不是在碰撞后立刻进行的，而是等待一个随机时延，而不同节点独立选择随机时延，因此碰撞发生后，可能交错发送数据，从而正确完成传输。随机接入协议有许多种，接下来重点介绍其中的三种。

时隙ALOHA

时隙ALOHA协议时最简单的随机接入协议之一。在该协议中，有如下假设：

  • 所有帧由L比特组成
  • 时间被划分为长度为L/R秒的时隙
  • 节点只在时隙起点开始传播帧
  • 每个节点都知道时隙何时开始
  • 如果一个时隙中发生了碰撞，所有节点在该时隙结束前检测到碰撞

对于节点而言，在该协议的处理如下：

  • 有新帧要发送时，等到下一个时隙开始并在该时隙传输整个帧
  • 如果没有碰撞，节点成功传输该帧
  • 如果有碰撞，该节点在时隙结束之前检测到碰撞，以概率p在后续时隙中重传该帧

ALOHA协议中，节点传输的过程大致如下：

image-20221204165049326

现在考虑时隙ALOHA的传输效率。假设有N个节点，对于一个节点，成功发送数据的概率为p(1-p)^(N-1)，因为有N个节点，任一节点成功传输的概率为Np(1-p)^(N-1)。求其极限，可以得到最大效率为0.37(0.364)。因此当有大量节点要传输数据时，有效传输速率最多仅有0.37R bps。

ALOHA

上述的ALOHA已经是改进的版本了。最早的纯ALOHA更加简单，不限制节点发送数据的时间，即不进行同步。在这种情况下，假设时间单位为时隙，一个节点要在t0 ~ t0+1发送一个帧，那么t0-1 ~ t0不可以有帧发送，t0 ~ t0+1也不可以有其他帧发送，否则都会产生碰撞，因此一个节点发送的时间落在两个时隙时间，两个时隙都不能有其他节点发送，这个概率为p(1-p)^(2(N-1))，求极限后，最大效率为0.184，刚好是时隙ALOHA的一半。

image-20221204170057042

载波侦听多路访问CSMA

载波侦听多路访问协议(CSMA)是一类通过侦听来尽量避免碰撞并减少碰撞后无效传输的协议。

  • 载波侦听(CS)：一个节点在传输前先听信道，等待到信道上有一小段时间都没有数据传输，就开始传输。
  • 多路访问(MA)：多个节点共享信道。

根据监听方式和监听到信道忙后的处理方式不同，CSMA协议可以分为三种：

  • 1-坚持CSMA：监听到信道忙后，继续坚持监听信道；监听到信道空闲，立即发送数据(即发送概率为1)。
  • 非坚持CSMA：监听到信道忙后，放弃监听，等待一个随机时间后再进行监听。
  • p-坚持CSMA：p-坚持CSMA用于时分信道，基本思想是，监听信道直到信道空闲，如果空闲，以概率p发送数据，以概率1-p推迟到下一个时隙再发送，如果下一个时隙还是空闲，继续以概率p发送数据，以1-p推迟到再下一个时隙发送数据，重复这个过程至发送成功或监听到信道忙。

一般提到CSMA，都是指CSMA/CD或CSMA/CA，即具有碰撞检测(CD)的载波侦听多路访问和碰撞避免(CA)的载波侦听多路访问。下面先介绍CSMA/CD，这个协议其实在现在的网络中已经没有必要使用了，因为以太网交换机一般是全双工的，一条线路发数据，一条线路接收数据，不会产生冲突。CSMA/CA一般用于无线网络，因为无线网络中碰撞检测困难，在无线网络章节中介绍。

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

如果能检测到信道中的碰撞，就可以在碰撞后立刻放弃传输损坏的帧，避免传输一个无用的帧，改善性能。检测方式就是适配器在传输时检测是否有来自其他适配器的信号能量，如果有，就中止当前帧的传输。不过这也对帧长和传输时间有了要求，如果一个正在传输的帧发生了碰撞，那么碰撞信号传回来到适配器的时间，应该小于帧传输的时间，这样才能提前停止无效帧的传输，提高性能。因此在CSMA/CD中，做以下约定：

  • 使用CSMA/CD协议的以太网争用期(碰撞窗口)
    • 发送帧的主机最多经过以太网端到端往返传播时延2t时间，就可检测到碰撞，这个时间称为争用期
    • 争用期内没有检测到碰撞则确定不会发生碰撞
    • 以太网规定2t取值为512比特时间
  • 使用CSMA/CD协议的以太网的最小帧长和最大帧长
    • 最小帧长 = 争用期*信道带宽(10Mbps的以太网，最小帧长为64字节)
    • 最小帧长保证了主机可在帧发送完成前检测到该帧是否发生了碰撞
    • 为了防止主机长时间占用总线，以太网的帧长有限制(V2的MAC帧最大长度为1518字节)

概括而言，信号从起始节点到下一个节点的往返时间，必须小于传输最小帧的时间。这样碰撞才能在该帧发送完之前才能检测到。

当发生碰撞时，重发的间隔时间称为随机退避时间，以太网的CSMA/CD协议使用的截断二进制指数退避算法如下：

  • 随机退避时间 = 争用期2t * 随机数r，r从离散整数集合{0,1…,(2^k-1)}中随机取一个，k = Min[重传次数，10]
  • 重传16次仍不成功时，表示同时有太多主机打算发送数据，此时丢弃该帧并向高层报告

3.3 轮询协议

最后一类协议是轮流协议，节点轮流占用信道进行数据传输。轮流协议也有许多种，简单介绍其中的两种：轮询协议和令牌传递协议。轮询协议中，有一个主节点，主节点每次告知每个节点最多能传输的帧，然后让节点轮流进行传输。令牌传递协议中，没有主节点，有一个称为令牌的特殊帧在节点之间以固定次序交换，只有持有令牌且有数据需要传输的节点才可以传输数据。如果节点没有数据要传输，就将令牌传递。以上两种协议都有缺点，最主要的是如果主节点有故障，或者令牌崩溃或停留在一个节点，整个信道的传输就会有问题。

4.交换局域网

互联网是由一个个小的网络连接而成，在网络层中，已经学习了这些网络是通过路由器连接起来，并通过RIP或OSPF这样的路由选择算法确定路径。接下来介绍交换局域网，即最小的网络，介绍在这样的网络中，数据是怎样传输的。在交换局域网中，网络层的数据报通过交换机在链路上转发，数据报被封装为链路层帧，使用链路层地址来转发。

4.1 链路层寻址与ARP

MAC地址

每一个主机或路由器的适配器(网络接口)都有一个链路层地址，被称为MAC地址。每个MAC地址都是独一无二的，由厂商生产时指定，通常情况下，适配器的MAC地址是固定的，无论在哪里使用，都不会变化。MAC地址有6个字节，48位，用十六进制表示为XX-XX-XX-XX-XX-XX。当适配器要向目的适配器发送一个帧时，要在帧首部加入目的适配器的MAC地址。适配器接收到帧，检查帧中的目的MAC地址是否与自己的MAC地址匹配，如果匹配，则接收该帧。有时适配器需要广播帧，只需要将目的MAC地址设置为FF-FF-FF-FF-FF-FF，就可以让所有适配器接收该帧。

在主机和路由器接口有网络层地址，也有MAC地址，主要的原因有以下几个：

  • 局域网是为任意网络层协议设计的，不止用于IP和因特网，因此需要一个链路层地址。
  • 如果适配器使用网络地址，网络地址必须存储在适配器的RAM中，并且每次适配器移动都要重新配置。
  • 如果适配器不使用任何地址，把数据报上交到网络层，让网络层核对IP地址是否匹配，会导致主机被局域网上发送的每个帧中断。

由于以上几点和一些其他的原因，链路层需要有自己的寻址方案，因此使用MAC地址。

地址解析协议

因为存在IP地址和MAC地址，所以需要在这两个地址间进行转换。这个转换由地址解析协议(ARP)来完成。

链路层帧是网络层数据报的封装，需要根据IP地址确认目的MAC地址。ARP协议就是根据IP地址，确认目的MAC地址的协议。每台主机或路由器都在内存中有一个ARP表，记录了IP地址和MAC地址的映射关系。当主机需要知道一个IP地址对应的MAC地址时，构造一个ARP分组，包含源IP与MAC地址，目的IP地址，广播该ARP分组，网络中的每个适配器都收到该帧，并将其交付给网络层，网络层会检查ARP请求的目的IP地址是否与自己的IP地址匹配，如果匹配，就构造一个包含自己MAC地址的ARP响应帧，发给发出ARP请求的主机。源主机收到后，将映射存入ARP表，并相应的有一个TTL值，在TTL时间内保存该映射。需要注意的是，ARP只为在同一个子网的主机和路由器接口解析IP地址，路由器不会转发ARP请求到其他网络。

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

发送数据到子网外

考虑主机向子网外的目的主机发送数据，通过IP地址，可以得知目的主机与源主机不在同一子网，那么就不能使用ARP找到目的IP的MAC地址，必须先通过路由器将帧转发到目的IP所在的子网中，因此主机应该先发送ARP请求，ARP请求的目的IP为第一跳路由器地址，获得MAC地址后，将该地址封装进帧，发送给路由器，然后由路由器进行处理。注意主机发送出去的帧，封装的IP数据报的目的IP为目的主机的IP，而目的MAC地址则是该报文下一站的MAC地址，目的MAC地址是由所经过的路由器，在路由表确认下一站的IP地址经ARP请求解析得到的。

image-20221213211801595

上图中的帧首部是简化了的，只是为了说明发送数据到子网外时，帧的形成情况。下面介绍以太网时，会看到帧首部的完整内容。

4.2 以太网

以太网是有线局域网技术的一种，但经历了与ATM，令牌环等技术的竞争后，现在已经占领了几乎现在所有的优先局域网市场。这是由于以太网部署的较早，且速率总是能够比其他技术更快，并且硬件也随着其大规模应用价格极低。起初的以太网是用集线器将主机连接起来的，集线器是物理层设备，作用于比特，只把输入的比特重新生成，以更大的能量强度向其他所有接口传输出去，因此最早的采用集线器的星型拓扑的局域网其实是一个广播局域网。21世纪初，交换机替换了集线器，稍后会介绍交换机的工作内容和流程。接下来先介绍一下以太网帧和以太网技术。

以太网帧

以太网帧的格式如下：

image-20221213213746275

  • 前同步码：以太网帧以8字节的前同步码开始，前7字节值为10101010，最后一个字节是10101011。前7个字节用于唤醒适配器，同步时钟，最后一个字节的最后两个1告诉适配器重要的数据就要到来。
  • 数据字段：46-1500字节。以太网的最大传输单元(MTU)是1500字节，超过1500字节，主机必须将数据报分片。

以太网提供的是无连接的不可靠服务，因此首部非常简单，而其尾部的CRC也只用于检验，无论帧是否通过CRC检验，适配器都不发出确认或否定确认，只在不通过检验时丢弃帧。如果上层运输层协议使用了TCP，那么会通过TCP实现可靠传输，丢失的报文会重传，但在链路层这个层次，以太网并不知道传输的数据时新的还是重传的。

以太网技术

以太网在多年的发展过程中，已经经历了一系列的演化，也有许多不同标准，从速率上看，已经经历了10Mbps，100Mbps，40Gbps的发展，但是以太网帧和MAC协议一直都没有改变。不过对于今天的以太网，连接链路的交换机已经是全双工的了，一台交换机和一个节点可以同时向对方发送帧而互不干扰，因此MAC协议已经是没有必要使用的了。

4.3 链路层交换机

目前为止，已经介绍了以太网相关的内容和链路层寻址等问题，还没有仔细介绍过在局域网中，把一段一段链路连接起来的交换机，接下来就介绍交换机的工作内容和工作方式。

交换机的任务是接收入链路层帧并将他们转发到出链路，对于主机和路由器来说，交换机是透明的，就向链路的一部分一样，并不知道交换机会接收并转发帧。交换机的转发是通过交换机表(CAM:ContextAddress Memory)完成的。以下是一个交换机表，其中的时间是接收到帧的时间。

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

交换机收到帧后，对帧的处理有三种：

  • Ÿ如果能在CAM表中查询到目的主机所在端口，且该端口不是接收帧的源端口，交换机把帧从这一端口转发出去。
  • Ÿ如果目的主机端口和接收帧的源端口是同一端口，过滤掉该帧。
  • Ÿ如果交换机不能查询到目的主机的端口，就将该帧从源端口以外的其他所有端口洪泛发送出去，如果该帧是广播帧，也进行洪泛发送。

交换机是自学习的，不需要对交换机表配置。交换机表初始为空，每接收到一个帧，就将其源MAC地址，到达接口，到达时间添加到交换机表中，在一段时间后如果没有收到该地址的帧，就删除表项。交换机的自学习也意味着他是一个即插即用设备，不需要进行任何配置，只需要连接接口。

交换机有一些特性或可称为优点，不同于基于集线器或总线的广播链路：

  • 消除碰撞：交换机缓存帧并只在网段上同一时间传输不超过一个帧，没有因碰撞浪费的带宽。
  • 异质链路：交换机将链路隔离，不同链路可以以不同的速率在不同的媒体上运行。
  • 管理：交换机易于进行网络管理。例如，如果一个适配器工作异常并持续发送以太网帧，交换机能够检测到该问题，并在内部断开异常适配器。

4.4 交换机与路由器的比较

路由器和交换机都是存储转发分组交换机，但一个工作在网络层，一个工作在链路层，从根本上是不同的，但是安装互联设备时，也常常需要在这两个设备之间作出选择。下面分别讨论交换机和路由器的优点和缺点。

交换机的优点是即插即用，并且具有较高的分组过滤和转发速率，因为只需要处理链路层的帧。缺点是为了防止广播帧的循环，必须限制网络拓扑结构为生成树；且交换机不对广播风暴有任何保护措施，如果主机故障不停广播，交换机将转发所有广播帧；此外，如果内部都使用交换机，使网络整体很大，主机和路由器中就必须有大的ARP表，这产生了可观的ARP流量和处理量。

路由器的优点是网络寻址是分层次的，分组不会通过路由器循环，IP首部也有字段避免循环，因此网络拓扑不受限制；另一个优点是对广播风暴提供了防火墙保护。路由器的缺点在于不是即插即用的，需要人为配置IP地址；而且路由器处理分组时间较长，需要处理到网络层的字段。