计网 408-3-1 - 计算机网络 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 数据链路层概述

链路就是从一个结点到相邻结点的一段物理线路，而中间没有任何其他的交换节点
数据链路是指把通信协议的硬件和软件加到链路上，就构成了数据链路
数据链路层以帧为单位传输和处理数据

数据链路层三个重要问题：

封装成帧
- 数据链路层给网络层交付的协议数据单元添加帧头和帧尾的操作称为封装成帧
- 添加帧头和帧尾的目的：为了在链路上以帧为单元来传输数据
差错检测
- 发送方在发送帧之前，基于待发送的数据和检错算法计算出检错码，并将其封装在帧尾
- 接收方主机收到帧后，通过检错码和检错算法，就可以判断出帧在传输过程中是否出现了误码
可靠传输
- 接收方在接收到了有误码的帧后，不会接收该帧，将其丢弃
- 如果数据链路层为上层提供的是不可靠服务，那么丢弃后不会有更多措施
- 如果数据链路层为上层提供的是可靠服务，就需要更多措施来确保接收方收到被丢弃的帧的正确副本
- 尽管误码是不可避免的，但若能实现发送发发送什么，接收方就能收到什么，就成为可靠传输

注意：以上是在点对点的数据链路层的情况下讨论的

使用广播信道的数据链路层（共享局域网）

共享式以太网的媒体接入控制协议 CSMA/CD
802.11 局域网的媒体接入控制协议 CSMA/CA

数据链路层的互连设备

网桥和交换机的工作原理
集线器 (物理层互连设备) 与交换机的区别

# 封装成帧

封装成帧：指数据链路层给上层交付的协议数据单元添加帧头和帧尾使之成为帧

帧头和帧尾中包含重要的控制信息
帧头和帧尾的作用之一就是帧定界

透明传输：指数据链路层对上层交付的传输数据没有任何限制，就好像数据链路层不存在一样

面向字节的物理链路使用字节填充 (或称字符填充) 的方法实现透明传输
- 对于上层数据部分有帧定界符和转义符的部分，会在前面添加转义符，让帧定界符和转义符被当做数据处理
面向比特的物理链路使用比特填充的方法实现透明传输
- 对上层交付的数据进行扫描，如果其中包含帧定界符，可以使用零比特填充法，这样保证了帧定界符的唯一性
  - 零比特填充法：在每 5 个连续的 1 后面添加 0
- 接收方在接受时将插入的比特剔除即可

为了提供帧的传输效率，应当使帧的数据部分的长度尽可能大些

考虑到差错控制等多种因素，每一种数据链路协议都规定了帧的数据部分的长度上限，即最大传送单元 MTU

# 差错检测

实际的通信链路都不是理想的，比特在传输的过程中可能会产生差错：1 可能会变成 0，而 0 可能会变成 1。这称为比特差错

在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER

使用差错检测码来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一

奇偶校验

在待发送的数据后面添加 1 位奇偶校验位，使整个数据 (包括添加的校验位在内) 中 1 的个数位奇数（奇校验）或偶数（偶校验）
如果有奇数个位发生误码，则奇偶性发生变化，可以检查出误码
如果有偶数个位发生误码，则奇偶性不会发生变化，不能检查出误码（漏检）
计算机网络的数据链路层一般不会采用奇偶校验

循环冗余校验

收发双方约定好一个生成多项式
发送方基于待发送的数据和生成多项式计算出差错检测码（冗余码），将其添加到带传输数据的后面一起传输
接收方通过生成多项式来计算收到的数据是否产生了误码
CRC 算法要求生成多项式必须包含最低次项

例：待发送的信息为 101001，生成多项式为 $G(x)=x^3+x^2+1$ ，计算余数

构造被除数：待发送信息后再添加多项式最高次数个 0
- 本题中，被除数为 101001000
构造除数：生成多项式各项系数构成的比特串
- 本题中，除数为 1101
做除法：
- 本题中 101001000/1101=110101 余 1
检查余数：余数的位数应与生成多项式最高次数相同，如果位数不够，则在余数前补 0 来凑足位数
- 本题中余数变为 001,
将余数添加到待发送信息的后面
- 本题中待发送信息变为 101001001 发送出去

例：接收到的信息为 101101001，生成多项式为 $G(x)=x^3+x^2+1$ ，判断是否产生误码

计算后为 101101001/1101=110010 余 11
余数不为 0，表明传输时出现了误码

检错码只能检测出帧在传输过程中出现了差错但并不能定位错误，因此无法纠正错误

要想纠正传输中的差错，可以使用冗余信息更多的纠错码进行前向纠错。但纠错码的开销比较大，在计算机网络中较少使用

循环冗余校验 CRC 有很好的检错能力 (漏检率非常低)，虽然计算比较复杂，但非常易于用硬件实现，因此被广泛应用于数据链路层

在计算机网络中通常采用检错重传方式来纠正传输中的差错或者仅仅是丢弃检测到差错的帧，这取决于数据链路层向上层提供的是可靠传输服务还是不可靠传输服务

# 可靠传输服务

使用差错检测技术（例如循环冗余校验 CRC），接收方的数据链路层就可检测出帧在传输过程中是否产生了误码（比特错误）

数据链路层向上层提供的服务类型：

不可靠传输服务：仅仅丢弃有误码的帧，其他什么也不做
可靠传输服务：想办法实现发送端发送什么，接收端就收到什么

一般情况下，有线链路的误码率比较低，为了减小开销，并不要求数据链路层向上提供可靠传输服务。即使出现了误码，可靠传输的问题由其上层处理

无线链路易受干扰，误码率比较高，因此要求数据链路层必须向上层提供可靠传输服务

比特差错只是传输差错的一种

从整个计算机网络体系结构来看，传输差错还包括分组丢失、分组失序以及分组重复

分组丢失、分组失序和分组重复这些传输差错，一般不会出现在数据链路层，而会出现在其上层

可靠传输服务并不仅限于数据链路层，其他各层均可选择实现可靠传输

TCP 向上层提供面向连接的可靠传输服务
UDP 向上层提供无连接、不可靠的传输服务
IP 向上层提供无连接、不可靠传输服务
802.11 无线局域网要求数据链路层实现可靠传输服务，以太网不要求数据链路层实现可靠传输

可靠传输的实现比较复杂，开销也比较大，是否使用可靠传输取决于应用需求

# 可靠传输的实现机制

停止 - 等待协议 SW
回退 N 帧协议 GBN
选择重传协议 SR

以上三种可靠传输实现机制的基本原理并不仅限于数据链路层，可以应用到计算机网络体系结构的各层协议中

# 停止 - 等待协议 SW

发送方将数据传输给接收方，接收方接收到并确认无误码后，向发送方发送 ACK 表示正确接收到
若接收方接收到了有误码的数据，则接收方将丢弃数据，并给发送方发送 NAK 表示未正确收到，发送方收到 NAK 后，再次向接收方发送一次数据，直到接收到 ACK 为止
发送方不能在发送后就将发送数据从缓存中删除，需要在收到接收方发送的 ACK 后才可以将发送数据从缓存中清除

发送方发送数据丢失

若发送方发送的数据丢失，接收方收不到数据分组，就不会发送 ACK 或 NAK，如果不采取其他措施，发送方就会一直处于等待接收方 ACK 或 NAK 的状态。

为解决该问题，可以在发送方发送完一个数据分组时，启动一个超时计时器。若到了超时计时器所设置的重传时间，而发送方仍收不到接收方的 ACK 或 NTK，则重传原来的数据分组，这就叫超时重传

接收方发送数据丢失

同理，接收方发送的 ACK 或 NTK 也有可能丢失，此时发送方又会超时重传一个同样的数据到接收方。

为了避免重复分组这种传输错误，必须给每个分组带上序号。

对于停止 - 等待协议，由于每发送一个数据分组就停止等待，只要保证每发送一个新的数据分组，其发送序号与上次发送的数据分组的序号不同就可以了，因此用一个比特来编号就足够了

接收方确认是重复数据分组后，丢弃这个重复数据，并给发送方发送针对该数据分组的确认分组，以免发送方对该组数据分组的再次超时重传

通过给确认分组编号的方法，解决确认迟到所导致的重复确认问题

注意事项

接收端检测到数据分组有误码时，将其丢弃并等待发送方的超时重构。但对于误码率较高的点对点链路，为使发送方尽早重传，也可给发送方发送 NAK 分组
为了让接收方能够判断所收到的数据分组是否是重复的，需要给数据分组编号。由于停止 - 等待协议的停等特性，只需 1 个比特编号就够了，即编号 0 和 1
为了让发送方能够判断所收到的 ACK 分组是否是重复的，需要给 ACK 分组编号，所用比特数量与数据分组编号所用比特数量一样。数据链路层是一般不会出现 ACK 分组迟到的情况，因此在数据链路层实现停止 - 等待协议可以不用给 ACK 分组编号
超时计时器设定的重传时间应仔细选择，一般可将重传时间略大于 "从发送方到接收方的平均往返时间"。
- 在数据链路层点对点的往返时间比较固定，重传时间比较好设定
- 然而在运输层，由于端到端往返时间非常不稳定设置合适的重传时间有时并不容易

停止 - 等待协议信道利用率

信道利用率 U=TD/(TD+RTT+TA)

TD 为数据分组的发送时延，RTT 为数据的传输往返时间，TA 为确认分组的发送时延

当往返时间 RTT 远大于数据帧发送时延 TD 时，信道利用率非常低

若出现重传，则对于传送有用的数据信息来说，信道利用率还要降低

为了克服停止 - 等待协议信号利用率很低的缺点，就产生了另外两种协议，即后退 N 帧协议 GBN 和选择重传协议 SR

例题：主机甲采用停止 - 等待协议向主机乙发送数据，数据传输速率为 3kbps，单向传播时延为 200ms，忽略确认帧的传输延时，当信道利用率等于 40% 时，数据帧的长度为（D）

A.240 比特 B.400 比特 C.480 比特 D.800 比特

解析：U=TD/(TD+RTT+TA)，TA 忽略不计，则 RTT=2*200ms=400ms，TD=160ms/0.6=800/3ms，传输速率为 3kbps，则数据帧长度为 800/3*3kbps=800 比特

停止等待协议属于自动请求重传 ARQ，即重传的请求是自动进行的

# 回退 N 帧协议 GBN

采用流水线传输可提高信道利用率

发送方

发送窗口尺寸 $W_T$ 的取值范围是 $1<W_T\le 2^n-1$
- 其中，n 是构成分组序号的比特数量
- 当 $W_T=1$ ，停止等待协议
- 当 $W_T>2^n-1$ ，接收方无法分辨新、旧数据分组
发送方可在未收到接收方确认分组的情况下，将序号落在发送窗口内的多个数据分组全部发送出去
发送方只有收到对已发送数据分组的确认时，发送窗口才能向前相应滑动
发送方收到多个重复确认时，可在重传计时器超时前尽早开始重传，由具体实现决定
发送方发送窗口内某个已发送的数据分组产生超时重发时，其后续在发送窗口内且已发送的数据分组也必须全部重传，这就是回退 N 帧协议名称的由来

接收方

接收方的接收窗口 WR 的取值范围是 1，因此接收方只能按序接收数据分组
接收方只接受序号落在接受窗口内且无误的数据分组，并且将接收窗口向前滑动一个位置，与此同时给发送方发回相应的确认分组，为了减少开销，接收方不一定每收到一个按序到达且无误码的数据分组就给发送方发回一个确认分组
- 而是可以在连续收到好几个按序到达且无误码的数据分组后（由具体实现决定），才针对最后一个数据分组发送确认分组，这称为累积确认
- 或者可以在自己有数据分组要发送时才对之前按序接收且无误码的数据分组进行捎带确认
接收方收到未按时到达的数据分组，除丢弃外，还要对最近按序接收的数据分组进行确认

回退 N 帧协议在流水线传输的基础上利用发送窗口来限制发送方连续发送数据分组的数量，是一种连续 ARQ 协议。在协议的工作过程中，发送窗口和接收窗口不断向前滑动，因此这类协议又称为滑动窗口协议

由于回退 N 帧协议的特性，当通信链路质量不好时，其信道利用率并不比停止 - 等待协议高

# 选择重传协议 SR

为了进一步提高性能，可设法只重传出现误码的数据分组。因此，接收窗口的尺寸 WR 不应再等于 1（而应大于 1），以便接收方先收下失序到达但无误码并且序号落在接收窗口内的那些数据分组，等到所缺分组收齐后再一并送交上层。这就是选择重传协议 SR

注意：选择重传协议为了使发送方仅重传出现差错的分组，接收方不能再采用累积确认，而需要对每个正确接收到的数据分组进行逐一确认

发送方

发送窗口尺寸 $W_T$ $W_{T}$ 的取值范围是 $[1,2^{n-1}]$ $[1, 2^{n - 1}]$
- 其中，n 是构成分组序号的比特数量
- $W_T=1$ ，与停止 - 等待协议想通
- $W_T>2^{n-1}$ ，接收方无法分辨新、旧数据分组
发送方可在未收到接收方确认分组的情况下，将序号落在发送窗口内的多个数据分组全部发送出去
发送方只有按序收到对已发送数据分组的确认时，发送窗口才能向前相应滑动；若收到未按序到达的确认分组时，对其进行记录，以防止相应数据分组的超时重发，但发送窗口不能向前滑动

接收方

接收窗口 $W_R$ $W_{R}$ 的取值范围是 $1<W_R\le W_T$ $1 < W_{R} \leq W_{T}$
- $W_R=1$ ，与停止 - 等待协议想通
- $W_R>W_T$ ，无意义
接收方可接收未按序到达但没有误码并且序号落在接收窗口内的数据分组
- 为了使发送方仅重传出现差错的分组，接收方不能再采用累积确认，而需要对每个正确接收到的数据分组进行逐一确认
接收方只有在按序接收数据分组后，接收窗口才向前相应滑动

# 点对点协议 PPP

点对点协议 PPP 是目前使用最广泛的点对点数据链路层协议
PPP 协议是因特网工程任务组 IETF 在 1992 年制定的。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准 [RFC1661,RFC1662]
PPP 协议为在点对点链路传输各种协议数据报提供了一个标准方法，主要由以下三部分构成：
- 对各种协议数据报的封装方法（封装成帧）
- 链路控制协议 LCP：用于建立、配置以及测试数据链路的连接
- 一套网络控制协议 NCPs：其中的每一个协议支持不同的网络层协议
PPP 协议能在多种类型的点对点链路上运行，如：面向字节的异步链路，面向比特的同步链路

PPP 协议的帧格式

帧头部：4 个字段构成

标志（Flag）字段：PPP 协议的定界符，取值为 0x7E，1 字节
地址（Address）字段：取值为 0xFF，预留（目前没有什么作用），1 字节
控制字段（Control）字段：取值为 0x03，预留（目前没有什么作用），1 字节
协议（Protocol）字段：指明帧的数据部分送交哪个协议处理，2 字节
- 取值为 0x0021 表示：帧的数据部分为 IP 数据报
- 取值为 0xC021 表示：帧的数据部分为 LCP 分组
- 取值为 0x8021 表示：帧的数据部分为 NCP 分组

帧尾部：2 个字段构成

帧检验序列字段（FCS）：CRC 计算出的校验位，2 字节
标志（Flag）字段：PPP 协议的定界符，取值为 0x7E，1 字节

帧的数据部分：不超过 1500 字节

实现透明传输的方法

面向字节的异步链路：

字节填充法：在标志字段前插入转义字符
发送方的处理：
- 出现的每一个 7E（PPP 帧的定界符）字节转变成 2 字节序列（7D,5E）
- 出现的每一个 7D（转义字符）字节转变为 2 字节序列（7D,5D）
- 出现的每一个 ASCII 码控制字符（数值小于 0x20 的字符），则在该字符前插入一个 7D 字节，同时将该字符的编码加上 0x20
接收方处理：进行反变换即可恢复出原来的帧的数据部分

面向比特的同步链路：

比特填充法：插入比特 0
发送方的处理：
- 对帧的数据部分进行扫描（一般由硬件实现）。只要发现 5 个连续的比特 1，则立即填充 1 个比特 0
接收方的处理：
- 对帧的数据部分进行扫描（一般由硬件实现）。只要发现 5 个连续的比特 1，就把其后的 1 个比特 0 删除

差错检测

RFC 1662 附录部分给出了 FCS 的计算方法的 C 语言实现（查表法）

接收方每收到一个 PPP 帧，就进行 CRC 检验。若 CRC 检验正确，就收下这个帧；反之，就丢弃这个帧，使用 PPP 的数据链路层向上不提供可靠传输服务

PPP 工作状态

PPP工作状态转换

# 媒体接入控制

共享信道要着重考虑的一个问题就是如何协调多个发送和接收站点对一个共享传输媒体的占用，即媒体接入控制 MAC

媒体介入控制：

静态划分信道：预先固定分配好信道，这类方法非常不灵活，对于突发性数据传输信道利用率会很低。通常在无线网络的物理层使用，而不是在数据链路层使用
- 频分多址
- 时分多址
- 码分多址
动态接入控制
- 受控接入
  - 集中控制：有一个主干以循环方式轮询每个站点有无数据发送，只有被轮询到的站点才能发送数据，最大缺点是存在单点故障问题
  - 分散控制：各站点是平等的，并连接一个环形网络，令牌（一个特殊的控制帧）沿环逐站传递，接收到令牌的站点才有权发送数据，并在发送完数据后将令牌传递给下一个站点
- 随机接入：所有站点通过竞争，随机地在信道上发送数据，如果恰巧有两个或更多的站点在同一时刻发送数据，则信号在共享媒体上就要产生碰撞（即发生了冲突），使得这些站点的发送都失败。因此，这类协议要解决的关键问题是如何尽量避免冲突及在发生冲突后如何尽快恢复通信，著名的共享式以太网采用的就是随机接入

随着技术发展，交换技术的成熟和成本降低，具有更高性能的使用点对点链路和链路层交换机的交换式局域网在有限领域已完全取代了共享式局域网，但由于无线通道的广播天性，无线局域网仍然使用的是共享媒体技术

# 静态划分信道

# 信道复用

复用是通信技术中的一个重要概念。复用就是通过一条物理线路同时传输多路用户的信号
当网络中传输媒体的传输容量大于多条单一信道传输的总通信量时，可利用复用技术在一条物理通道上建立多条通信信道来充分利用传输媒体的带宽

频分复用 FDM

将传输线路的频带资源划分称为多个子频带，形成多个子信道，各子信道之间需要留出隔离频带，以免造成信道间的干扰。

当多路信号输入一个多路复用器时，这个复用器将每一路信号调制到不同频率的载波上。

接收端由相应的分用器通过滤波将各路信号分开，将合成的复用信号恢复成原始的多路信号

频分复用的所有用户同时占用不同的频带资源并行通信

时分复用 TDM

将时间划分为一个个时隙。

时分复用技术将传输线路的带宽资源按时隙轮流分配给不同的用户，每对用户只在所分配的时隙里使用线路传输数据。

时分复用技术将时间划分为了一段段等长的时分复用帧，每一个时分复用的用户在每一个时分复用帧中占用固定序号的时隙

每一个用户所占的时隙是周期性出现的，周期为时分复用帧的长度。

时分复用的所有用户在不同的时间占用同样的频带宽度

波分复用 WDM

波分复用

码分复用 CDM

码分复用 CDM 是另一种共享信道的方法。实际上，由于该技术主要用于多址接入，人们更常用的名词是码分多址 CDMA
同理，频分复用 FDM 和时分复用 TDM 同样可用于多址接入，相应的名次是频分多址 FDMA 和时分多址 TDMA
与 FDM 和 TDM 不同，CDM 的每一个用户可以在同样的时间使用同样的频带进行通信
由于各用户使用经过特殊挑选的不同码型，因此各用户之间不会造成干扰
CDM 最初是用于军事通信的，因为这种系统所发送的信号具有很强的抗干扰能力，其频谱类似于白噪声，不易被敌人发现
随着技术的进步，CDMA 设备的价格和体积都大幅度下降，因而现在已广泛应用于民用设备的通信中
在 CDMA 中，每一个比特时间再划分为 m 个短的间隔，称为码片，通常 m 的值为 64 或 128。
使用 CDMA 的每一个站被指派一个唯一的 m bit 码片序列（这种方式称为直接序列扩频 DSSS）
- 一个站如果要发送比特 1，则发送它自己的 m bit 码片序列
- 一个站如果要发送比特 0，则发送它自己的 m bit 码片序列的二进制反码
码片序列挑选原则如下：
- 分配给每个站的码片序列必须各不相同，实际常采用伪随机码序列
- 分配给每个站的码片序列必须相互正价（规格化内积为 0）
  - 令向量 S 表示站 S 的码片序列，令向量 T 表示其他任何站的码片序列
  - 两个不同站 S 和 T 的码片序列正交，就是向量 S 和向量 T 的规格化内积为 0（规格化内积就是内积除以序列长度）

例：假设给站 S 分配的码片序列为 01011101，给站 T 分配的码片序列为 10111000，这样分配正确吗？

解析：

检查码片序列是否各部相同：满足
检查码片序列是否相互正交：不满足
- 站 S 码片序列向量为 (-1,1,-1,1,1,1,-1,1)，站 T 的码片序列向量为 (1,-1,1,1,1,-1,-1,-1)，两者求内积为：(3-5)/8=-2/8 不为 0

例：共有 4 个站进行 CDMA 通信，这 4 个站的码片序列分别为：

A.(-1,-1,-1,+1,+1,-1,+1,+1) B.(-1,-1,+1,-1,+1,+1,+1,-1) C.(-1,+1,-1,+1,+1,+1.-1,-1) D.(-1,+1,-1,-1,-1,-1,+1,-1)

接收到码片序列 (-1,+1,-3,+1,-1,-3,+1,+1)，问是哪些站发送了数据？发送的是比特 1 还是 0？

解析：

接收的码片序列与 A 的码片求内积：1-1+3+1-1+3+1+1=8/8=1
接收的码片序列与 B 的码片求内积：1-1-3-1-1-3+1-1=-8/8=-1
接收的码片序列与 C 的码片求内积：1+1+3+1-1-3-1-1=0
接收的码片序列与 D 的码片求内积：1+1+3-1+1+3+1-1=8/8=1
因此 A,B,D 发送了数据，A 发送了比特 1，B 发送了比特 0，D 发送了比特 1

复用与多址区分：

复用是将单一媒体的频带资源划分成很多子信道，这些子信道之间相互独立，互不干扰。从媒体的整体频带资源上看，每个子信道只占用该媒体频带资源的一部分
多址 (更确切地应该称为多点接入) 处理的是动态分配信道给用户。这在用户仅仅暂时性地占用信道的应用中是必须的，而所有的移动通信系统基本上都属于这种情况。相反，在信道永久性地分配给用户的应用中，多址是不需要的（对于无线广播或电视广播站就是这样的）
某种程度上，FDMA、TDMA、CDMA 可以分别看成是 FDM，TDM，CDM 的应用

# 随机接入 ——CSMA/CD 协议

总线局域网使用的协议：载波监听多址接入 / 碰撞检测 CSMA/CD 协议

多址接入 MA

多个站点接在一条总线上，竞争使用总线

载波监听 CS

每一个站在发送帧之前先要检测一下总线上是否有其他站点在发送帧 ("先听后说")
- 若检测到总线空闲 96 比特时间，则发送比特帧
- 若检测到总线忙，则继续检测并等待总线为空闲 96 比特时间，然后发送这个帧

注：96 比特时间指发送 96 比特所耗费的时间，也称为帧间最小间隔，其作用是使接收方可以检测出一个帧的结束，同时也使得所有其他站点都能有机会平等竞争信道并发送帧

碰撞检测 CD

每一个正在发送帧的站边发送边检测碰撞（"边说边听"）
- 一旦发现总线上出现碰撞，则立即停止发送，退避一段随机时间后再次发送（"一旦冲突，立即听说，等待时间，重新再说"）

以太网还采取了一种叫强化碰撞的措施。当发送帧的站点一旦检测到碰撞，除了立即停止发送帧外，还要再继续发送 32 比特或 48 比特人为干扰信号，以便有足够多的碰撞信号碰撞信号使所有站点都能检测出碰撞

争用期（碰撞窗口）

以太网单程端到端传播时间为 t

主机最多经过 2t 的时长就可检测到本次发送是否遭受了碰撞
因此，以太网的端到端往返传播时延 2t 称为争用期或碰撞窗口
经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞
每一个主机在自己发送帧之后的一小段时间内，存在着遭遇碰撞的可能性。这一小段时间是不确定的。它取决于另一个发送帧的主机到本主机的距离，但不会超过总线的端到端往返传播时延，即一个争用期时间
显然，在以太网中发送帧的主机太多，端到端往返传播时延越大，发生的碰撞概率就越大。因此，共享式以太网不能连接太多的主机，使用的总线也不能太长
- 10Mb/s 以太网把争用周期为 512 比特发送时间，即 51.2μs，因此其总线长度不能超过 5120m，但考虑到其他一些因素，如信号衰减等，以太网规定总线长度不能超过 2500m

最小帧长

使用 CSMA/CD 协议的以太网的帧长不能太短

以太网规定最小帧长为 64 字节，即 512 比特（512 比特时间即为争用期）

以太网的最小帧长确保了主机可在帧发送完成之前就检测到该帧的发送过程中是否遭遇了碰撞

最小帧长 = 争用起 * 数据传输速率
如果在争用期（共发送 64 字节）没有检测到碰撞，那么后续发送的数据就一定不会发生碰撞
如果在争用期内检测到了碰撞，就立即终止发送，这时已经发送出去的数据一定小于 64 字节，因此凡长度小于 64 字节的帧都是由于碰撞而异常中止的无效帧

最大帧长

限定最大帧长防止占用总线时间过长，或者由于帧长过长导致接收方缓冲区溢出

截断二进制指数退避算法

退避时间 = 基本退避时间（争用期 2t）* 随机数 r（从离散的整数集合 0 到 $2^k$ 中随机选出一个数 k=Min (重传次数，10)）

若连续多次发生碰撞，就表明可能有较多的主机参与竞争信道。但使用上述退避算法可使重传需要推迟的平均时间随重传次数而增大（这也称为动态退避），因而减小发生碰撞的概率，有利于整个系统的稳定

当重传 16 次仍不能成功时，表明同时打算发送帧的主机太多，以至于连续发生碰撞，则丢弃该帧，并向高层报告

信道利用率

考虑以下理想情况：

各主机发送帧都不会产生碰撞
总线一旦空闲就有某个主机立即发送帧
发送一帧占用总线时间为 T0+t，则帧本身的发送时间为 T0
- 极限信道利用率 Smax=1/(1+a),a=t/T0
参数 a 的值尽量小，以提高信道利用率，以太网端到端的距离受到限制
以太网帧的长度应尽量长些

帧发送流程

帧发送流程

帧接收流程

帧接收流程

CSMA/CD 协议曾经用于各种总线结构以太网和双绞线以太网的早期版本中

现在的以太网基于交换机和全双工连接，不会有碰撞，因此没有必要使用 CSMA/CD 协议

习题

1、下列关于 CSMA/CD 协议的叙述中，错误的是 (B)

A. 边发送数据帧，边检测是否产生冲突

B. 适用于无线网络，以实现无线链路共享

C. 需要根据网络跨距和数据传输速率限定最小帧长

D. 当信号传播延迟趋近于 0 时，信道利用率趋近于 100%

解析：选项 A 描述的是碰撞检测；选项 B，CSMA/CD 协议不适用于无线网络，对于无线网络，可以使用 CSMA/CA 协议；选项 C，网络跨距相当于给出了端到端传播时延 t，进而得出争用周期 2t，再乘以数据传输速率即为最小帧长，描述正确；选项 D，从极限信道利用率可以看出

2、在采用一个 CSMA/CD 协议的网络中，传输介质是一根完整的电缆，传输速率为 1Gbps，电缆中信号传播速度是 200000km/s。若最小数据帧长度减少 800 比特，则最远的两个站点之间的距离至少需要（D）

A. 增加 160m B. 增加 80m C. 减少 160m D. 减少 80m

解析：设最远两个站点之间的距离为 d (m)，最小帧长为 l (bit)，最小帧长 = 争用期 * 数据传输速率

l=(\dfrac{d}{200000\times10^3}\times2)\times10^9,d=\frac{l}

若最小帧长减少 800 比特，最远的两个站点的距离至少会减少 80m

3、某局域网采用 CSMA/CD 协议实现介质访问控制，数据传输速率为 10Mbps，主机甲和主机乙之间的距离为 2km，信号传播速度是 200000km/s，请回答下列问题，要求说明理由或写出计算过程

（1）如主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过了多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）?

解析：两主机同时发送数据，两主机检测到冲突时间最短，时间为 2km/200000km/s=0.01ms

当时间最长时，一台主机发送信息快要到另一台主机时，另一台主机发送信息，造成冲突，最长时间为 4km/200000km/s=0.02ms

# 随机接入 ——CSMA/CA 协议

无线局域网使用的协议：载波监听多址接入 / 碰撞避免 CSMA/CA 协议

在无线局域网中，仍然可以使用载波监听多址接入 CSMA，即在发送帧之前先对传输媒体进行载波监听，若发现有其他站在发送帧，就推迟发送以免发生碰撞。

在无线局域网中，不能使用碰撞检测 CD，原因如下：

由于无线信道的传输条件特殊，其信号强度的动态范围非常大，无线网卡上接收到的信号强度往往会远小于发送信号的强度（可能相差百万倍）。如果要在无线网卡上实现碰撞检测 CD，对硬件的要求非常高
即使能够在硬件上实现无线局域网的碰撞检测功能，但由于无线电波传播的特殊性（存在隐蔽站问题），进行碰撞检测的意义也不大
- 隐蔽站问题：未能检测出信道上其他站点信号的问题

802.11 无线局域网使用 CSMA/CA 协议，在 CSMA 的基础上增加了一个碰撞避免 CA 功能，而不再实现碰撞检测功能

由于不可能避免所有的碰撞，并且无线信道误码率较高，802.11 标准还使用了数据链路层确认机制 (停止 - 等待协议) 来保证数据被正确接收

802.11 的 MAC 层标准定义了两种不同的媒体接入控制方式：

分布式协调功能 DCF。在 DCF 方式下，没有中心控制站点，每个站点使用 CSMA/CA 协议通过争用信道来获取发送权，这是 802.11 定义的默认方式
点协调功能 PCF。PCF 方式使用集中控制的接入算法（一般在接入点 AP 实现集中控制），是 802.11 定义的可选方式，在实际中较少使用

帧间间隔 IFS

802.11 标准规定，所有站点必须在持续检测到信道空闲一段指定时间后才能发送帧，这段时间称为帧间间隔
帧间间隔的长短取决于该站点要发送的帧的类型：
- 高优先级需要等待的时间较短，因此可优先获得发送权
- 低优先级帧需要等待的时间较长。若某个站点的低优先级帧还没来得及发送，而其他站的高优先级帧已发送到信道上，则信道变为忙态，因而低优先级帧就只能再推迟发送。这样就减少了发生碰撞的机会
常用的两种帧间间隔如下：
- 短帧间间隔 SIFS（28μs），是最短的帧间间隔，用来分隔开属于一次对话的各帧。一个站点应当能够在这段时间内从发送方式切换到接收方式。使用 SIFS 的帧类型有 ACK 帧、CTS 帧、由过长的 MAC 帧分片后的数据帧，以及所有回答 AP 探询的帧和 PCF 方式中介入点 AP 发送出的任何帧
- DCF 帧间间隔 DIFS（128μs），它比短帧间间隔 SIFS 长得多，在 DCF 方式中用来发送数据帧和管理帧

CSMA/CA 协议的工作原理

工作原理1

工作原理2

工作原理3

当站点检测到信道是空闲的，并且发送的数据帧不是成功发送完上一个数据帧之后立即连续发送的数据帧，则不使用退避算法
以下情况必须使用退避算法
- 在发送数据帧之前检测到了处于忙状态时
- 在每一次重传一个数据帧时
- 在每一次成功发送后要连续发送下一个帧时（这是为了避免第一个站点长时间占用信道）

CSMA/CA 的退避算法

在执行退避算法时，站点为退避计时器设置一个随机地退避时间
- 当退避计时器的时间减小到零时，就开始发送数据
- 当退避计时器的时间还未减小到零时而信道又转变为忙状态，这时就冻结退避计时器的数值，重新等待信道变为空闲，再经时间 DIFS 后，继续启动退避计时器
在进行第 i 次退避时，退避时间在时隙编号（0,1,..., $2^{2+i}+1$ ）中随机选择一个，然后乘以基本退避时间（也就是一个时隙的长度）就可以得到随机地退避时间。这样做是为了使不同站点选择相同退避时间的概率减少。当时隙编号达到 255 时（对应第 6 次退避）就不再增加了

CSMA/CA 协议的信道预约和虚拟载波监听

为了尽可能减少碰撞的概率和降低碰撞的影响，802.11 标准允许要发送数据的站点对值进行预约
- 源站在发送数据帧之前先发送一个短的控制帧，称为请求发送 RTS，它包括源地址、目的地址以及这次通信（包括相应的确认帧）所需的控制时间
- 若目的站正确收到源站发来的 RTS 帧，且媒体空闲，就发送一个响应控制帧，称为允许发送 CTS，它也包括这次通信所需的持续时间（从 RTS 帧中将此持续时间复制到 CTS 帧中）
- 源站收到 CTS 帧后，再等待一段时间 SIFS 后，就可发送其数据帧
- 若目的站正确受到了源站发来的数据帧，在等待时间 SIFS 后，就向源站发送确认帧 ACK
除源站和目的站以外的其他各站，在收到 CTS 帧（或数据帧）后就推迟接入到无线局域网中。这样就保证了源站和目的站之间的通道的通信不会受到其他站的干扰
如果 RTS 帧发生了碰撞，源站就收不到 CTS 帧，需执行退避算法重传 RTS 帧
由于 RTS 帧和 CTS 帧很短，发送碰撞的概率、碰撞产生的开销及本身的开销都很小。而对于一般的数据帧，其发送时延往往大于传播时延（因为是局域网），碰撞的概率很大，且一旦发生碰撞而导致数据帧重发，则浪费的时间就很多，因此用很小的代价对信道进行预约往往是值得的。802.11 标准规定了 3 种情况供用户选择：
- 使用 RTS 帧和 CTS 帧
- 不使用 RTS 帧和 CTS 帧
- 只有当数据帧的长度超过某一数值时才使用 RTS 帧和 CTS 帧
除 RTS 帧和 CTS 帧会携带通信需要持续的时间，数据帧也能携带通信需要持续的时间，这称为 802.11 的虚拟载波监听机制
由于利用虚拟载波监听机制，站点只要监听 RTS 帧、CTS 帧或数据帧的任何一个，就能知道信道被占用的持续时间，而不需要真正监听到信道上的信号，因此虚拟载波监听机制能减少隐蔽站带来的碰撞问题

练习

1、下列选项中，对正确接收到的数据帧进行确认的 MAC 协议是（D）

A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA

解析：CSMA 是指载波监听多址接入，并不使用确认机制；CSMA/CD 是指载波监听多址接入 / 碰撞检测，是对 CSMA 的改进，是早期共享信道以太网使用的信道访问控制协议，并不使用确认机制；CSMA/CA 是指载波监听多址接入 / 碰撞避免，是 802.11 局域网采用的无线信道访问控制协议。802.11 局域网在使用 CSMA/CA 的同时，还使用停止 - 等待协议。这是因为无线信道的通信质量远不如有线信道，因此无线站点每发送完一个数据帧后，要等到收到对方的确认帧后才能继续发送下一帧。CDMA 是指码分多址，属于静态划分信道，是物理层的信道复用技术，而不属于 MAC 协议

2、下列介质访问控制方式中，可能发生冲突的是（B）

A.CDMA B.CSMA C.TDMA D.FDMA

解析：CDMA 是码分多址、TDMA 是时分多址、FDMA 是指频分多址、CSMA 是指载波监听多址接入。TDMA、CDMA、FDMA 是常见的物理层信道复用技术，属于静态划分信息，用于多用户共享信道，不会发生冲突。CSMA 属于争用型的媒体接入控制协议，连接在同一媒体上的多个站点使用该协议以竞争方式发送数据帧，可能出现冲突（也称为碰撞）

3、IEEE 802.11 无线局域网的 MAC 协议 CSMA/CA 进行信道预约的方法是（D）

A. 发送确认帧 B. 采用二进制指数退避 C. 使用多个 MAC 地址 D. 交换 RTS 与 CTS 帧

解析：CSMA/CA 协议使用 RTS 和 CTS 帧来预约信道，它们都携带有通信需要持续的时间。另外，除 RTS 和 CTS 帧外，数据帧也能携带通信需要持续的时间，这是 802.11 的虚拟载波监听。