计算机网络——第3章 数据链路层（自学笔记）

本文参考【王道计算机考研 计算机网络】

数据链路层的功能

主要任务：实现帧在一段链路上或在一个网络中进行传输。

基本原则：封装成帧、透明传输和差错检测。

信道：点对点信号和广播信道。

数据链路层所处地位

数据进入路由器后，先从物理层上到网络层，在转发表找到下一跳的地址后，在下到物理层转发出去。

从学习的角度，可以想象数据链路层是沿水平方向传输的。

为网络层提供的服务

数据链路层通常可以为网络层提供如下三种服务：

• 无确认的无连接服务。源主机发送帧时不需要先建立链路连接，目的主机接收到帧不需要发回确认。数据链路层的可靠性由高层负责，适用于误码率较低的信道，如以太网。
• 有确认无连接的服务。源主机在规定时间内为收到确认信号时，就会重新传输丢失的帧。适用于误码率较高的信道，比如无线通信。
• 有确认的面向连接服务。分为三个阶段：建立链路、传输帧、释放链路。适用于可靠性较高的场合。

封装成帧

指在一段数据的前后分别添加首部和尾部，构成帧。

透明传输

若数据中恰好存在出现和帧界定符相同的比特组合，则需采取有效的措施来解决该问题，即透明传输。

透明传输的核心是通过某些方法对特殊字符进行处理（比如字符填充、比特填充或转义字符法），使得这些特殊字符不会被误解释为帧的定界符、控制字符或其他特定用途的标识符。

流量控制

就是限制发送方的发送速率，使之不能超过接收方的接收能力。

在OSI系统结构中，数据链路层具有流量控制功能，而在TCP/IP协议中，流量控制被移到传输层。

差错检测

帧传输可能会出现错误

• 位错：帧中某些位出现差错，通常采用循环冗余检测（CRC）来发现位错。
• 帧错：帧丢失、帧重复或帧失序等。

现在，对于通信质量较差的无线传输，数据链路层依然使用确认和重传机制，向上提供可靠服务。对于通信质量较好的有线链路，不需要确认和重传，即不要求向上提供可靠服务，仅进行CRC检错。

组帧

即封装成帧，通常有以下4种方法

• 字符计数法

字符计数法是指在帧的首部使用一个计数字段来记录该帧所含的字节数。但该方法最大的问题是若计数字段出错，则失去帧边界划分依据。

• 字节填充法

字节填充法使用特定字节来界定一帧的开始与结束。比如用控制字符SOH表示开始，用EOT表示结束。用添加转义字符ESC区分数据中的特殊字符,接收方再删掉转义字符即可。

• 零比特填充法（常用）

HDLC协议使用特定比特串01111110标志帧开始与结束。若数据字段出现连续5个”1“，则自动在其后插入一个”0“。接收方收到连续5个”1“，在自动在删除其后一个”0“。

• 违规编码法（常用）

在物理层进行比特编码时，若采用曼彻斯特编码法，只会出现”高-低“和”低-高“两种电平，则可以使用违规编码”高-高“和”低-低“表示帧的起始。

差错控制

• 自动重传请求（ARQ）：当接收方检测到差错时，就设法通知发送方重发，直到接收到正确数据为止。（检错编码）
• 前向纠错（FEC）：接收方不仅能发现差错，而且能够确认错误位置并加以纠正。（检错编码+纠错编码）

检错编码

核心思想时在有效数据被发送之前，按照某种规则附加一定的冗余位，使其符合某一规则。当有效数据发生变化时，其码字将不满足规则。

常见的检错编码有奇偶校验码和循环冗余码。

1、奇偶检验码

由n-1位数据位和1位检验位组成，校验位的取值（0或1）将使得整个校验码中”1“的个数位奇数或偶数。

但该方法只能检测出奇数个出错情况，不能发现偶数个出错情况，且没有纠错功能。

2、循环冗余码

数据链路层广泛使用循环冗余码（CRC）检错技术。基本思想：

• 收发双方约定生成多项式G(x)。
• 发送发基于待发送数据和G(x)，计算出冗余码，将冗余码附加到数据后面一起发送。
• 接收方收到数据和冗余码后，通过G(x)计算来检验接收是否出错。

循环冗余码也有纠错功能，只是数据链路层仅使用了它的检错功能。

纠错编码

最常见的纠错编码位海明码，步骤如下

1、确定海明码的位数

设n位有效数据位，k位检验位的位数，则应满足
$$n+k\le 2^k-1$$
2、检验位的分布

规定检验位分布在2^(i-1)位上

3、求出检验码的值

根据负责码和奇偶校验规则计算出检验码的值

4、检错并纠错

根据检验码和对应负责码，再按照奇偶校验规则定位出错误位。

流量控制和可靠传输机制

在数据链路层，流量控制和可靠传输交织在一起。

流量控制

1、停止-等待流量控制

这是最简单的流量控制方法，发送方每次只允许发送一个帧，接收方每接收一个帧都要反馈一个应答信号，发送方接收到应答信号才能发送下一帧。

该方法传输效率低。

2、滑动窗口流量控制

任意时刻，发送方都维持一组连续可发送的帧序号，称发送窗口；同时接收方也维持一组连续可接受帧的序号，称为接收窗口

发送方每接收到一个确认帧，就会将发送窗口向前滑动一个位置。

接收方每收到一个接收窗口内的数据帧，就会将接收窗口向前滑动一个位置。

可靠传输机制

可靠传输指发送方的数据都能被接收方正确接收，通常包括确认和超时重传两种机制。

• 确认：接收方每接收到发送方的数据帧，都要向发送方发回一个确认帧。
• 超时重传：发送方在规定时间内没有接收到确认帧，则重发该数据帧，直到成功位置。

使用这两种机制的可靠传输协议称为自动重传请求（ARQ）。该协议分为停止-等待协议、后退N帧协议和选择重传协议。

1、单帧滑动窗口与停止-等待协议（S-W）

在停止等待协议中，除了数据帧丢失外，还可能出现以下两种差错：

• 接收到的数据帧已损坏，接收方利用差错检测技术检出后，将该帧丢弃，则无确认应答。
• 数据帧正确而确认帧损坏，则发送方收不到确认帧。

2、多帧滑动窗口与后退N帧协议（GBN）

后退N帧的含义是：发送方发送N个数据帧后，若发现这N个帧前一个数据帧在计时器超时的时候仍未收到确认信息，则该帧判断未出错或丢失，此时发送方得重传出错帧和随后的N个帧。这意味着接收方只允许按顺序接收帧。

GBN协议允许接收方进行累积确认，可以在连续收到多个正确的数据帧后，对最后一个数据帧发回确认信息。

3、多帧滑动窗口与选择重传协议（SR）

为了提高信号利用率，可以设法只重传出错和计时器超时的数据帧，但此时必须加大接收窗，以便收下失序但正确的数据帧，等到所有缺失的数据帧都收齐后，再一并交送上层，这就是选择重传协议。

介质访问控制

主要任务是为每个节点隔离来自同一信道的其他节点所传信号，以协调活动节点的传输。

用来决定广播信道中信道分配的协议数据数据链路层的一个子层，称为介质访问控制（MAC）子层。

常见的介质访问控制方法有：信道划分介质访问控制、随机访问介质访问控制和轮询访问介质访问控制。

信道划分介质访问控制

1、频分复用（FDM）

指将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每个用户使用一个子信道进行通信。

优点：充分利用传输介质的带宽，系统效率高，容易实现。

2、时分复用（TDM）

指信道的传输时间划分为一段等长的时间片（TDM帧），每个用户再指定的TDM帧占用固定的时间。

缺点：当某个用户不传输数据，其他用户也无法使用该空闲的时间资源，所以时分复用的信道利用率不高。异步时分复用（STDM）是对TDM的改进，它不固定分配时间，而是动态分配。

3、波分复用（WDM）

即光的频分复用，根据光纤传输的波长（频率）不同，划分为不同频带。

4、码分复用（CDM）

也称码分多址（CDMA），采用不同的编码来区分各路原始信号的一种复用方式，即共享信道的频率，也共享时间。

举例：

假设A站要向C站运输黄豆，B站要向C站运输绿豆，它们之间有一条公共道路，可类比广播信道。

• 频分复用：将公路划分为两个车道，一路运黄豆，一路运绿豆。共享时间，但不共享空间。
• 时分复用：按时间段运输，先运黄豆，再运绿豆。共享空间，但不共享时间。
• 码分复用，黄豆绿豆放在同一辆车上运输，到达C站后再将黄豆绿豆分开。空间、时间都共享。

随机访问介质访问控制

每个用户按照一定的规则反复重传它的帧，直到该帧无冲突地通过。即不共享空间，也不共享时间。因此，随机介质访问控制实质上是一种将广播信道转换为点到点信道的机制。

1、ALOHA协议

当站点需要发送数据时，无需任何检测就可以发送数据。若在一定时间内未收到确认，则认为传输过程中发生了冲突。等待一段时间后再发送数据，直到发送成功为止。

2、CSMA协议

即载波监听多路访问协议，在每个站点发送数据前都先监听公用信道，发现信道空闲后再发送，可以大大降低冲突的可能性。

3、CSMA/CD协议

载波监听多路访问/冲突检测协议是CSMA的改进方案，适合总线型网络和半双工网络。

冲突检测：指边发送边监听，若监听到冲突，则立即停止发送数据，等待一段随机时间后，重新开始发送数据。

重传时机

CSMA/CD算法步骤归纳：

1. 准备发送：适配器从网络层获取一个分组，封装成帧，放入适配器中缓存。

2. 检测信道：若信道空闲，则开始发送该帧；若信道忙，则继续检测直到信道空闲。

3. 在发送过程中，适配器仍持续检测信道。有两种可能：

   • 发送成功：在争取期内一直未检测到冲突，该帧肯定能发送成功。

   • 发送失败：在争取期检测到冲突，则立即停止发送，适配器执行指数退让算法，等待一段时间后返回步骤2。若重传16次仍不能成功，则停止重传并向上报错。

4、CSMA/CA协议

冲突避免（CA）指尽可能降低冲突发生的概率。

轮询访问：令牌传递协议

用户不能随机发送信息，而是要通过一个集中控制的监控站，以循环的方式轮询每个站点，再决定信道的分配。典型的协议有令牌传递协议。

令牌环网络中数据的传递过程：

1. 当网络空闲时，环路中只有令牌帧在循环传递。
2. 当令牌传到有数据要发送的站点时，该站点就修改令牌的一个标志位，并在令牌上附加自己的要传输的数据，将令牌变为一个数据帧，然后将数据帧发送出去。
3. 数据帧沿着环路传输，接收到的站点一边转发数据、一边查看帧的目的地址。若目的地址和自己地址相同，则接收站复制该数据帧，以便处理。
4. 数据帧沿着环路传输，直到该帧的源站点，源站点收到自己发出去的帧后不在转发。同时，同故宫返回来的帧查看数据传输过程是否出错，否则重发。
5. 源站点传输完数据后，重新产生一个令牌，传递给下一个站点，交出信道控制权。

局域网（LAN）

局域网的基本概念和体系结构

局域网（Local Area Network, LAN）指在一个较小的地理范围，将各种计算机、外部设备和数据库通过双绞线、同轴电缆等介质连接起来，组成的计算机互联网络。

• 常见的局域网拓扑结构：

星型网络、环形网络、总线型网络、星型和总线型的复合型

• 传输介质：

铜缆、双绞线、光纤等

• 介质访问控制方法：

CSMA/CD协议、令牌总线协议、令牌环协议

因为以太网的使用范围最广，处于市场垄断地位，所以以太网几乎成为局域网的代名词。

以太网和 IEEE 802.3

以太网采用总线型拓扑结构，信息以广播的方式发送，使用CSMA/CD方式对总线进行访问控制。

IEEE **802.3 ** 是第一个IEEE的以太网标准规约。

以太网的传输介质与网卡

传输介质

网络适配器（又称网卡，NIC）

适配器和局域网的通信：通过电缆或双绞线以串行方式进行

适配器和计算机的通信：I/O总线，并行方式

以太网的MAC地址

局域网上的每台计算机有个固化在适配器的ROM中的地址，称为物理地址或MAC地址（因为该地址用于MAC帧中）。

全世界每台计算机的网络适配器都具有不同的MAC地址。

MAC地址

长6个字节，有连接符分隔的12个十六进制数表示。例如02-60-8c-e4-b1-21。高24位为厂商代码，后24位为适配器序列号。

以太网的MAC帧

• 前同步码：实现MAC帧的比特同步。
• 帧开始界定符：表示后面信息就是MAC帧。
• 目的地址：目的适配器的MAC地址。
• 源地址：源适配器的MAC地址。
• 类型：指出数据字段的数据应交给哪个上层协议处理。
• FCS：数据字段的结束位置。

高速以太网

IEEE 802.11无线局域网

无线局域网的组成

固定基础设置指的是基站

1、有固定基础设置的无线局域网

803.11标准使用星形拓扑，MAC层使用CSMA/CA协议。使用802.11协议的局域网又称WIFI。

基本服务站（BSS）：包括一个接入点（AP）和若干个移动站。

基站（AP）：安装AP时，必须分配一个不超过32个字节的服务集标识符（SSID，即无线局域网的名称）和一个信道。

2、无固定基础设备移动自组织网络

802.11局域网的MAC帧

该数据帧由三部分组成

• MAC首部，共30个字节。帧的复杂性都在MAC首部。
• 帧主体，即帧的数据部分，不超过2312字节，比以太网的最大长度大得多。
• 帧检验序列FCS。

前三个地址的含义

地址1和地址2分别是无线通信两端的接收地址和发送地址，但接收地址和发送地址不一定指的是源地址和目的地址，所以用地址3来储存。

广域网（WAN）

特点：

• 覆盖范围光，超过一个城市的范围。
• 采用高速链路，通信容量大。

点对点协议（PPP协议）

PPP协议由三部分组成：

• 一个链路控制协议（LCP），用来建立、配置、测试数据链路连接，以及协商一些选项。
• 一套网络控制协议（NCP），PPP协议允许采用多种网络控制协议。
• 一种将IP数据报封装到串行链路的方法。

PPP帧的格式：

标志字段F：帧的开始与结束

FCS：帧检验序列，使用CRC检验的冗余码。

PPP协议特点：

• 不使用序号和确认机制，只保证无差错接收（CRC检验），因此是不可靠服务。
• 只支持全双工点对点链路，不支持多点路线。
• PPP的两端可以运行不同的网络层协议
• PPP面向字节的，所有PPP帧的长度是整个字节。

数据链路层的设备

以太网交换机

以太网交换机实质上是一个多接口的网桥，将网络分成小的冲突域，为每个用户提供更大的带宽。

以太网交换特点：

• 当交换机直接连接主机或其他交换机时，全双工方式，能同时连接多个接口，无冲突输出数据。
• 当交换即连接集线器时，只能使用CSMA/CD协议，半双工方式。
• 交换机是一种即插即用设备，其内部帧转发表有自学习算法。
• 交换机采用专用交换结构芯片，交换速率较高。
• 交换机独占传输介质的带宽。

交换机的自学习功能

• 若交换表中无目的地址，则广播发送。
• 交换机所连的主机会随时改变，所以交换表的每一项都有一定的有效时间，过期则自动删除。