第 3 章 数据链路层

数据链路层的功能

有三个基本问题则是共同的，即封装成帧、透明传输和差错检测。

数据链路层使用的信道主要有两种:

1️⃣ 点对点信道，使用一对一的通信方式。PPP协议则是目前使用最广泛的点对点协议。

2️⃣ 广播信道，这种信道上连接的主机很多，使用 一对多的广播通信方式。采用共享广播信 道的有线局域网普遍使用CSMA/CD协议，而无线局域网则使用CSMA/CA协议。

1. 数据链路层所处的地位

链路、数据链路、帧

2. 链路管理

数据链路层连接的建立、维持和释放过程称力链路管理

3. 封装成帧与透明传输

4. 为网络层提供服务

5. 流量控制

6. 差错检测

组帧

发送方依据一定的规则将网络层递交的分组封装成帧(也称组帧)。组帧主要解决帧定界、帧同步、透明传输等问题。

字符计数法

字符计数法是指在帧首部使用一个计数字段来记录该帧所含的字节数(包括计数字段自身所占用的1个字节)

字节填充法

控制字符SOH放在帧的最前面，表示帧的开始，控制字符EOT表示帧的结束。在特殊字符之前填充一个转义字符ESC来加以区

零比特填充法

使用一个特定的比特串01111110来标志一帧的开始和结束，每遇到5个连续的“1”，就自动在其后插入一个“0”。

违规编码法

在物理层进行比特编码时，常采用违规编码法。例如，曼彻斯特编码方法将数据比特“ 1” 编码成“高-低” 电平对，将数据比特 “0” 编码成“ 低-高” 电平对，而“高-高” 电平对和“低 - 低” 电平对在数据比特中是违规的(即没有采用)，因此可借用这些违规编码序列来定界帧的起 始和终止。

差错控制

检错编码

1. 奇偶检验码

它由n- 1位数据和1位检验位组成，检验位的取值(0或1)将使整个检验码中“1” 的个数为奇数或偶数。

例如，7 位数据1001101 对应的奇检验码 10011011，对应的偶检验码 10011012

2. 循环冗余码

又由多项式生成位串，原数据补多项式最高次个0 将位串与数据进行逻辑异或运算（同0异1）

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

纠错编码

最常见的纠错编码是海明码，其实现原理是在有效信息位中加入几个检验位形成海 明码，并 把海明码的每个二进制位分配到几个奇偶检验组中

流量控制与可靠传输机制

流量控制与滑动窗口机制

流量控制是指由接收方控制发送方的发送速率，使接收方有足够的缓冲空间来接收每个帧。

数据链路层和传输层均有流量控制的功能 ，它们都用到了滑动窗口协议，但也有所区别，主要体现如下:

1️⃣ 数据链路层控制的是相邻结点之间的流量，而传输层控制的是端到端的流量。

2️⃣ 数据链路层的控制手段是接收方收不下就不返回确认。传输层的控制手段是接收方通过 确认报文段中的窗又值来调整发送方的发送窗又。

1. 停止-等待流量控制基本原理

发送方每次只允许发送一个帧，接收方每接收一个帧都要反馈一个应答信号，表示可以接收下一帧，发送方收到应答信号后才能发送下一帧。若发送方没有收到接收方反馈的应答信号，则需要一直等待。

2. 滑动窗口流量控制基本原理

发送方都维持一组连续的允许发送帧的序号，称为发送窗口。同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。发送方每收到一个按序确认的确认帧，就将发送窗又向前滑动 一个位置

停止-等待协议:发送窗又Wt=1，接收窗口Wr=1。

后退N帧协议:发送窗又Wt>1，接收窗又Wr=1。

选择重传协议:发送窗又Wt>1，接收窗又Wr>1。

若采用n比特对帧编号，则后两种滑动窗又协议还需满足Wt+Wr≤2^n。

可靠传输机制

可靠传输是指发送方发送的数据都能被接收方正确地接收，通常采用确认和超时重传两种机制来实现。

确认是指接收方每收到发送方发来的数据帧，都要向发送方发回一个确认帧，表示已 正确地收到该数据帧。

超时重传是指发送方在发送一个数据帧后就启动一个计时器，若在规定时 间内没有收到所发送数据帧的确认帧，则重发该数据帧，直到发送成功为止。

1. 单帧滑动窗口与停止-等待协议

停止- 等待协议的发送窗又和接收窗又大小均为1。若连续出现相同序号的数据帧，则表明发送方进行了超时重传。

2. 多帧滑动窗口与后退N帧协议(GBN)

发送方可在未收到确认帧的情况下，将序号在发送窗又内的多个数据帧全部发送出去。发送方发送N个数据帧后，若发现这N个帧的前一个数据帧在计时器超时的时候仍未收到其确认信息，则该帧被判出错或丢失，此时发送方不得不重传该出错帧及随后的N个帧。

GBN协议允许接收方进行累积确认，即允许接收方不需要每收到一个正确的数据帧就立即发回一个确认帧，而可在连续收到多个正确的数据帧后，对最后一个数据帧发回确认信息，也就是说，对某个数据帧的确认就代表该数据帧和之前所有的帧均已正确无误地收到。

发送窗口应满足1< Wt ≤ 2^n - 1，接收窗口Wr= 1

3. 多帧滑动窗口与选择重传协议 (SR)

加大接收窗口，以便先收下失序但正确到达且序号仍落在接收窗又内的那些数据帧，等到所缺序号的数据帧收齐后，再一并送交上层。这就是选择重传协议。接收方不能再采用累积确认，而要对每个正确接收的数据帧逐一进行确认。每个发送缓冲区对应一个计时器，当计时器超时的时候，缓冲区的帧就重传。

窗口大小：Wr+ Wt ≤ 2^n，Wr ≤ 2^n-1，Wr和Wt的大小是相同的

4. 信道利用率

信道效率是对发送方而言的，是指发送方在一个发送周期 (从发送方开始发送分组到收到第 一个确认分组所需的时间)内，有效发送数据的时 间与整个发送周期之比。

U = n*Td / (Td + RTT + Ta)；（Td为发送时延，RTT为往返时延，Ta为确认帧发送时延）；

信道平均(实际)数据传输速率=信道利用率x信道带宽(最大数据传输速率)

信道平均(实际)数据传输速率=发送周期内发送的数据量/发送周期

介质访问控制

介质访问控制所要完成的主要任务是，为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号，以协调活动结点的传输。用来决定广播信道中信道分配的协议属于数据链路层的一个子层，称介质访问控制(MediumAccessControl,MAC)子层。

常见的介质访问控制方法有信道划分介质访问控制、随机访问介质访问控制和轮询访问介质访问控制。其中前者是静态划分信道的方法，而后两者是动态分配信道的方法。

信道划分介质访问控制

信道划分介质访问控制将使用同一传输介质的多个设备的通信隔离开来，把时域和频域资源合理地分配给这些设备。信道划分介质访问控制通过复用技术实现。

信道划分介质访问控制将使用同一传输介质的多个设备的通信隔离开来，把时域和频域资源合理地分配给这些设备。信道划分介质访问控制通过复用技术实现。

1. 频分复用(FDM)

频分复用(FrequencyDivisionMultiplexing,FDM)是指将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每对用户使用一个子信道进行通信。

2. 时分复用(TDM)

时分复用(TimeDivisionMultiplexing，TDM)是指将信道的传输时间划分为一段段等长的时间片，称为TDM帧，每个用户在每个TDM帧中占用固定序号的时隙，每个用户所占用的时隙周期性地出现(其周期就是TDM的长度)，所有用户在不同的时间占用同样的信道资源。

统计时分复用(StatisticTDM, STDM)又称异步时分复用，它是对TDM的一种改进。STDM帧与TDM帧不同，它并不固定分配时隙，而按需动态分配时隙。

3. 波分复用(WDM)

波分复用(WDM)

4. 码分复用(CDM)

码分复用(CodeDivisionMultiplexing,CDM)是采用不同的编码来区分各路原始信号的一种复用方式。与FDM和TDM不同，它既共享信道的频率，又共享时间。

信道划分介质访问控制

不采用集中控制方式解决发送信息的次序问题，所有用户都能根据自己的意愿随机地发送信息，占用信道的全部速率。当有两个或多个用户同时发送信息时，就会产生帧冲突(也称碰撞)，

1. ALOHA协议

1️⃣ 纯ALOHA协议：纯ALOHA协议的基本思想是，当总线形网络中的任何站点需要发送数据时，可以不进行任何检测就发送数据。若在一段时间内未收到确认，则该站点就认为传输过程中发生了冲突。发送站点需要等待一段时间后再发送数据，直至发送成功

2️⃣ 时隙ALOHA协议：同步各站点的时间，将时间划分为一段段等长的时隙(Slot)，规定站点只能在每个时隙开始时才能发送帧，发送一帧的时间必须小于或等于时隙的长度

2. CSMA协议

每个站点在发送前都先监听公用信道，发现信道空闲 后再发送，则会大大降低冲突的可能性，从而提高信道的利用率，载波监听多路访问。

1️⃣ 1-坚持CSMA

2️⃣ 非坚持CSMA

3️⃣ p-坚持CSMA

3. CSMA/CD协议

“先听后发，边听边发，冲突停发，随机重发”。

以太网的端到端往返时间2z称为争用期(又称冲突窗又)

最短帧=总线传播时延x数据传输速率x2

截断二进制指数退避算法：

1️⃣确定基本退避时间，一般取2倍的总线端到端的传播时延2 (即争用期)。

2️⃣ 从离散的整数集合[0. 1，... ，(2^k- 1)]中随机取出一个数，记为r，重传所需推迟的时间就是 倍 的争用期，即2rr。参数k=min[重传次数，10]，可见当重传次数不超过10时，参数k 等于重传次数;但当重传次数超过10时，人就不再增大，而一直等于10。

3️⃣ 当重传达16次仍不成功时，说明网络太拥挤，认为该帧永远无法正确发出，抛弃该帧并 向高层报告出错

4. CSMA/CA协议

广泛用于无线局域网的CSMA/CA协议。

所有站完成发送后，必须等待一段很短的时间(继续监听)才能发送下一帧。这段时间称为帧间间隔(InterFrameSpace,IFS)。帧间间隔的长短取决于该站要发送的帧的类型。802.11标准使用了下列三种IFS。

1️⃣ SIFS(短IFS):最短的IFS，用来分隔属于一次对话的各帧，使用SIFS的帧类型有ACK帧、CTS帧、分片后的数据帧，以及所有回答AP探询的帧等。

2️⃣ PIFS(点协调IFS):中等长度的IFS，在PCF操作中使用。

3️⃣ DIFS(分布式协调IFS):最长的IFS，用于异步帧竞争访问的时延。

CSMA/CA协议进行信道预约的方法：

源站要发送数据帧之前，先监听信道，若信道空闲，则等待时间DIFS后，广播一个请求发送RTS(RequestToSend)控制帧，它包括源地址、目的地址和这次通信所需的持续时间。若AP正确收到RTS帧，且信道空闲，则等待时间SIFS后，向源站发送一个允许发CTS(ClearToSend)控制帧，它也包括这次通信所需的持续时间，源站收到CTS帧后，再等待时间SIFS，就可发送数据帧。

轮询访问:令牌传递协议

一个令牌(Token)沿着环形总线在各站之间依次传递.

局域网