Temp：修订间差异

来自泡泡学习笔记
跳到导航 跳到搜索
无编辑摘要
标签：已被回退
（清空全部内容）
标签：清空 手工回退
第1行： 第1行：
3章
数据链路层
扫一扫
【考纲内容】
（一）数据链路层的功能
（一）组帧
（三）差错控制
视频讲解
检错编码；纠错编码
（四）流量控制与可靠传输机制
流量控制、可靠传输与滑动窗口机制；停止-等待协议后退 N 帧协议（GBN）；选择重传协议（SR）
（五）介质访问控制
1. 信道划分：频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理
2. 随机访问：ALOHA 协议；CSMA 协议；CSMA/CD 协议；CSMA/CA 协议
3.令牌传递协议
（六)局域网
局域网的基本概念与体系结构；以太网与 IEEE 802.3
IEEE 802.11 无线局域网；VLAN 基本概念与基本原理
（七)广域网
广域网的基本概念；PPP 协议
（八）数据链路层设备
局域网交换机及其工作原理
【复习提示】
本章是历年考试中考查的重点。要求在了解数据链路层基本概念和功能的基础上,重点掌握滑动窗口机制、三种可靠传输协议、各种 MAC 协议、HDLC 协议和PPP 协议，特别是CSMA/CD协议和以太网帧格式,以及局域网的争用期和最小帧长的概念、二进制指数退避算法。此外,中继器、网卡、集线器、网桥和局域网交换机的原理及区别也要重点掌握。
3.1
数据链路层的功能
数据链路层在物理层提供服务的基础上向网络层提供服务，其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。下面具体介绍数据链路层的功能。


3.1.1 为网络层提供服务
对网络层而言,数据链路层的基本任务是将源机器中来自网络层的数据传输到目标机器的网络层。数据链路层通常可为网络层提供如下服务：
1)无确认的无连接服务。源机器发送数据帧时不需先建立链路连接,目的机器收到数据帧时不需发回确认。对丢失的帧,数据链路层不负责重发而交给上层处理。适用于实时通信或误码率较低的通信信道,如以太网。
2)有确认的无连接服务。源机器发送数据帧时不需先建立链路连接,但目的机器收到数据帧时必须发回确认。源机器在所规定的时间内未收到确定信号时,就重传丢失的帧,以提高传输的可靠性。该服务适用于误码率较高的通信信道,如无线通信。
3)有确认的面向连接服务。帧传输过程分为三个阶段:建立数据链路、传输帧、释放数据链路。目的机器对收到的每一帧都要给出确认,源机器收到确认后才能发送下一帧,因而该服务的可靠性最高。该服务适用于通信要求(可靠性、实时性)较高的场合。
注意：有连接就一定要有确认，即不存在无确认的面向连接的服务。
3.1.2 链路管理
数据链路层连接的建立、维持和释放过程称为链路管理,它主要用于面向连接的服务。链路两端的结点要进行通信,必须首先确认对方已处于就绪状态,并交换一些必要的信息以对帧序号初始化,然后才能建立连接,在传输过程中则要能维持连接,而在传输完毕后要释放该连接。在多个站点共享同一物理信道的情况下(如在局域网中)如何在要求通信的站点间分配和管理信道也属于数据链路层管理的范畴。
3.1.3 帧定界、帧同步与透明传输
两台主机之间传输信息时,必须将网络层的分组封装成帧,以帧的格式进行传送。将一段数据的前后分别添加首部和尾部,就构成了帧。因此,帧长等于数据部分的长度加上首部和尾部的长度。首部和尾部中含有很多控制信息,它们的一个重要作用是确定帧的界限,即帧定界。而帧同步指的是接收方应能从接收到的二进制比特流中区分出帧的起始与终止。如在HDLC协议中,用标识位F (01111110)来标识帧的开始和结束。通信过程中,检测到帧标识位F即认为是帧的开始,然后一旦检测到帧标识位F即表示帧的结束。HDLC标准帧格式如图3.1所示。为了提高帧的传输效率,应当使帧的数据部分的长度尽可能地大于首部和尾部的长度,但每种数据链路层协议都规定了帧的数据部分的长度上限——最大传送单元（MTU）。
标志
地址
控制
信息
帧校验序列
标志
FCS
F
F
A
C
01111110
8 位
8 位
N位（可变）
图 3.1 HDLC 标准帧格式
如果在数据中恰好出现与帧定界符相同的比特组合(会误认为“传输结束”而丢弃后面的数据),那么就要采取有效的措施解决这个问题,即透明传输。更确切地说,透明传输就是不管所传数据是什么样的比特组合,都应当能在链路上传送。
3.1.4 流量控制
由于收发双方各自的工作速率和缓存空间的差异,可能出现发送方的发送能力大于接收方的
I
16 位
01111110
064 2024年计算机网络考研复习指导
接收能力的现象,如若此时不适当限制发送方的发送速率(即链路上的信息流量),前面来不及接收的帧将会被后面不断发送来的帧“淹没”,造成帧的丢失而出错。因此,流量控制实际上就是限制发送方的数据流量，使其发送速率不超过接收方的接收能力。
这个过程需要通过某种反馈机制使发送方能够知道接收方是否能跟上自己,即需要有一些规则使得发送方知道在什么情况下可以接着发送下一帧,而在什么情况下必须暂停发送,以等待收到某种反馈信息后继续发送。
流量控制(见图3.2)并不是数据链路层特有的功能,许多高层协议中也提供此功能,只不过控制的对象不同而已。对于数据链路层来说，控制的是相邻两结点之间数据链路上的流量，而对于传输层来说，控制的则是从源端到目的端之间的流量。
WR
(a)
0
准备接收0号帧
WR
(b)
0
已收到
准备接收1号帧
WR
(c)
0
1
1
1
2
3
4
5
6
0
不允许接收这些帧
2
3
4
5
6
0
不允许接收这些帧
2
3
4
6
7
0
已收到
准备接收4号帧
不允许接收这些帧
图 3.2 数据链路层的流量控制
注意：在OSI 体系结构中，数据链路层具有流量控制的功能。而在TCP/IP 体系结构中，流量控制功能被移到了传输层。因此,有部分教材将流量控制放在传输层进行讲解。
3.1.5 差错控制
由于信道噪声等各种原因,帧在传输过程中可能会出现错误。用以使发送方确定接收方是否正确收到由其发送的数据的方法称为差错控制。通常,这些错误可分为位错和帧错。
位错指帧中某些位出现了差错。通常采用循环冗余校验(CRC)方式发现位错,通过自动重传请求(Automatic Repeat reQuest, ARQ)方式来重传出错的帧。具体做法是:让发送方将要发送的数据帧附加一定的 CRC 冗余检错码一并发送，接收方则根据检错码对数据帧进行错误检测，若发现错误则丢弃,发送方超时重传该数据帧。这种差错控制方法称为ARQ法。ARQ法只需返回很少的控制信息就可有效地确认所发数据帧是否被正确接收。
帧错指帧的丢失、重复或失序等错误。在数据链路层引入定时器和编号机制,能保证每一帧最终都能有且仅有一次正确地交付给目的结点。
3.1.6 本节习题精选
单项选择题
01. 下列不属于数据链路层功能的是()。
A. 帧定界功能
B. 电路管理功能
02. 数据链路层协议的功能不包括()。
A. 定义数据格式
B. 提
C. 差错控制功
1
1
1
2
2
各非常
实时通
超过接收力策略，只是各层
的
连
标控制报又协路层协议。
MP）是网络层协议，PPP 是在 SLIP
要成功发送一个网络层分组，需要成功发送10个数据链路层帧。成功发送10个数据链路层帧的概率是(0.95)0=0.598，即大约只有60%的成功率。这个结论说明了在不可靠的信道上无确认的服务效率很低。为了提高可靠性,应该引入有确认的服务。
08. B
3.2
组帧
数据链路层之所以要把比特组合成帧为单位传输,是为了在出错时只重发出错的帧,而不必重发全部数据，从而提高效率。为了使接收方能正确地接收并检查所传输的帧，发送方必须依据一定的规则把网络层递交的分组封装成帧(称为组帧)。组帧主要解决帧定界、帧同步、透明传输等问题。通常有以下4种方法实现组帧。
注意：组帧时既要加首部，又要加尾部。原因是，在网络中信息是以帧为最小单位进行传输的,所以接收端要正确地接收帧,必须要清楚该帧在一串比特流中从哪里开始到哪里结束(因为接收端收到的是一串比特流，没有首部和尾部是不能正确区分帧的）。而分组（即IP数据报）仅是包含在帧中的数据部分(后面将详细讲解),所以不需要加尾部来定界。
3.2.1 字符计数法
如图 3.3 所示，字符计数法是指在帧头部使用一个计数字段来标明帧内字符数。目的结点的数据链路层收到字节计数值时,就知道后面跟随的字节数,从而可以确定帧结束的位置(计数字段提供的字节数包含自身所占用的一个字节)。
字数计数
一个字符
512345678980
12
4
89 0
3
5687
第3帧8个字符
第4帧8个字符
图 3.3 字符计数法
这种方法最大的问题在于如果计数字段出错,即失去了帧边界划分的依据,那么接收方就无
法判断所传输帧的结束位和下一帧的开始位，收发双方将失去同步，从而造成灾难性后果。
3.2.2 字符填充的首尾定界符法
字符填充法使用特定字符来定界一帧的开始与结束,在图3.4的例子中,控制字符SOH放在
1
2
3
第1帧
第2帧5个字符
5个字符
帧的最前面,表示帧的首部开始,控制字符EOT表示帧的结束。为了使信息位中出现的特殊字符不被误判为帧的首尾定界符,可在特殊字符前面填充一个转义字符(ESC)来加以区分(注意,转义字符是ASCI1码中的控制字符,是一个字符,而非"E”"S" "C"三个字符的组合),以实现数据的透明传输。接收方收到转义字符后,就知道其后面紧跟的是数据信息,而不是控制信息。
如图 3.4(a)所示的字符帧，帧的数据段中出现EOT或SOH字符，发送方在每个EOT 或SOH字符前再插入一个ESC字符[见图3.4(b)],接收方收到数据后会自己删除这个插入的ESC字符,结果仍得到原来的数据[见图3.4(c)]。这也正是字符填充法名称的由来。如果转义字符ESC也出现在数据中，那么解决方法仍是在转义字符前插入一个转义字符。
(a)网络层发出的数据
SOH
A
EOT
ESC
B
EOT
(b)经数据链路层填充后的数据
SOH
A
ESC EOT ESC
ESC
B
EOT
(c)接收方传送给网络层的数据
SOH
A
EOT ESC
B
EOT
图 3.4 字符填充法
3.2.3 零比特填充的首尾标志法
如图 3.5 所示，零比特填充法允许数据帧包含任意个数的比特，也允许每个字符的编码包含任意个数的比特。它使用一个特定的比特模式，即 01111110来标志一帧的开始和结束。为了不使信息位中出现的比特流 01111110 被误判为帧的首尾标志,发送方的数据链路层在信息位中遇到 5个连续的"1”时,将自动在其后插入一个"0”;而接收方做该过程的逆操作,即每收到5个连续的"1”时, 自动删除后面紧跟的"0”,以恢复原信息。
(a)原始数据
(b)线上数据
Ο11011111111111111110010
011011111011111011111010010
(c)接收方删除填充位后的数据
填充的位01101Ι111111111111110010
图 3.5 比特填充法
零比特填充法很容易由硬件来实现,性能优于字符填充法。
3.2.4 违规编码法
在物理层进行比特编码时,通常采用违规编码法。例如,曼彻斯特编码方法将数据比特"1”编码成“高-低”电平对，将数据比特“0”编码成“低-高”电平对，而“高-高”电平对和“低-低”电平对在数据比特中是违规的(即没有采用)。可以借用这些违规编码序列来定界帧的起始和终止。局域网IEEE 802标准就采用了这种方法。
违规编码法不需要采用任何填充技术,便能实现数据传输的透明性,但它只适用于采用冗余
编码的特殊编码环境。
由于字符计数法中计数字段的脆弱性和字符填充法实现上的复杂性与不兼容性,目前较常用的组帧方法是零比特填充法和违规编码法。
3.2.5 本节习题精选
综合应用题
01,在一个数据链路协议中使用下列字符编码.
A01000111;在使用下列成帧方法的情况下，说明为传送4个字符 A、B.ESC、FLAG所组织的幢名实际发送的二进制位序列(使用 FLAG作为首尾标志，ESC作为转义字符)。
B 11100011;
1)字符计数法。
2)使用字符填充的首尾定界法。
3)使用比特填充的首尾标志法。
3.2.6 答案与解析
综合应用题
1)第一字节为所传输的字符计数5,转换为二进制为00000101,后面依次为A、B、ESC、
01. 【解答】
FLAG 的二进制编码：
00000101 01000111 11100011 11100000 01111110
2)首尾标志位FLAG (01111110),在所传输的数据中,若出现控制字符,则在该字符前插
入转义字符ESC(11100000)：
01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110
3)首尾标志位FLAG (01111110)，在所传输的数据中,若连续出现5个“1”,则在其后插
入“0”：
01111110 01000111 110100011 111000000 011111010 01111110
3.3 差错控制
实际通信链路都不是理想的,比特在传输过程中可能会产生差错,1可能会变成0, 0也可能会变成1,这就是比特差错。比特差错是传输差错中的一种,本节仅讨论比特差错。
通常利用编码技术进行差错控制，主要有两类：自动重传请求 ARQ 和前向纠错 FEC。在 ARQ方式中,接收端检测到差错时,就设法通知发送端重发,直到接收到正确的码字为止。在FEC方式中,接收端不但能发现差错,而且能确定比特串的错误位置,从而加以纠正。因此,差错控制又可分为检错编码和纠错编码。
3.3.1 检错编码
检错编码都采用冗余编码技术,其核心思想是在有效数据(信息位)被发送前,先按某种关系附加一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时,相应的冗余位也随之变化,使得码字遵从不变的规则。接收端根据收到的码字是否仍符合原规则来判断是否出错。常见的检错编码有奇偶校验码和循环冗余码。
1. 奇偶校验码
奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它由 n-1 位信息元和1位校验元组成,如果是奇校验码,那么在附加一个校验元后,码长为n的码字中“1”的个数为奇数;如果是偶校验码,那么在附加一个校验元以后,码长为n的码字中“1”的个数为偶数。它只能检测奇数位的出错情况,但并不知道哪些位错了,也不能发现偶数位的出错情况。
2. 循环冗余码
循环冗余码(Cyclic Redundancy Code, CRC)又称多项式码,任何一个由二进制数位串组成的代码都可与一个只含有 0 和 1 两个系数的多项式建立—一对应关系。一个k位帧可以视为从x到X°的k次多项式的系数序列,这个多项式的阶数为k-1，高位是x-1项的系数,下一位是x42的系数，以此类推。例如1110011有7位,表示成多项式是X+X3+X4+X+1,而多项式X+X*+X2+X对应的位串是110110,其运算过程如图3.6所示。
110101→g
除数P→1101[101001600+2"M被除数
1110
1101
1101
0111
0000
1110
1101
0110
0000
1100
1101001→R(余数)，作为FCS
给定一个m bit的帧或报文，发送器生成一个rbit的序列,称为帧检验序列(FCS)。这样所形成的帧将由m+r比特组成。发送方和接收方事先商定一个多项式G(x) (最高位和最低位必须为1),使这个带检验码的帧刚好能被预先确定的多项式G(x)整除。接收方用相同的多项式去除收到的帧,如果无余数，那么认为无差错。
图3.6 循环冗余码的运算过程
假设一个帧有m位,其对应的多项式为M(x),则计算冗余码的步骤如下:
1)加0。假设G(x)的阶为r,在帧的低位端加上r个0。
2)模2除。利用模2除法，用G(x)对应的数据串去除1)中计算出的数据串，得到的余数即为冗余码(共r位,前面的0不可省略)。
多项式以2为模运算。按照模2运算规则,加法不进位,减法不借位,它刚好是异或操作。乘除法类似于二进制的运算,只是在做加减法时按模2规则进行。
冗余码的计算举例:设G(x)=1101 (即r=3),待传送数据M=101001 (即m=6),经模2除法运算后的结果是:商Q=110101 (这个商没什么用),余数R=001。所以发送出去的数据为101001 001 (即2'M+FCS),共有m+r位。
通过循环冗余码(CRC)的检错技术,数据链路层做到了对帧的无差错接收。也就是说,凡是接收端数据链路层接受的帧,我们都认为这些帧在传输过程中没有产生差错;而接收端丢弃的帧虽然也收到了,但最终因为有差错而被丢弃,即未被接受。
注意：循环冗余码（CRC）是具有纠错功能的，只是数据链路层仅使用了它的检错功能，检测到帧出错则直接丢弃，是为了方便协议的实现，因此本节将CRC放在检错编码中介绍。
3.3.2 纠错编码
在数据通信的过程中,解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息,使接收方能够推导出发送方实际送出的应该是什么样的比特串。最常见的纠错编码是海明码,其实现原理是在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，而且能指出错位的位置，为自动纠错提供依据。
现以数据码1010为例讲述海明码的编码原理和过程。
（1）确定海明码的位数
设n为有效信息的位数, k为校验位的位数,则信息位n和校验位k应满足
n+k<2"-1 (若要检测两位错,则需再增加1位校验位，即k+1位)
海明码位数为n+k=7<23-1成立,则n、k有效。设信息位为D.D3D2D, (1010),共4位,
校验位为P,P,P,共3位，对应的海明码为H,H,H,H,H,H,H。
规定校验位P,在海明位号为21的位置上，其余各位为信息位，因此有：
（2）确定校验位的分布
P，的海明位号为2r1=2°=1，即H为P1。
P2的海明位号为2-1=21=2，即H2为P2。
Ps的海明位号为2-1=22=4，即H4为P3。
将信息位按原来的顺序插入,则海明码各位的分布如下:
H, Ho Hs HA Hs H2 H
D4 D; D2 P; Di P2 Pi
每个数据位用多个校验位进行校验,但要满足条件:被校验数据位的海明位号等于校验该数据位的各校验位海明位号之和。另外,校验位不需要再被校验。分组形成的校验关系如下。
（3）分组以形成校验关系
P3(H4)
Pi(Hi)
P2(H2)
2
D;放在H3上，由P2P，校验：
3=
1
4
D2放在 Hs上，由 P;P1校验：
5=
D4放在 H，上，由 P3P2P;校验：
7=
4
D3放在 H6上，由P3P2校验：
6=
2
+
2
4
第1 组
第 2 组
第3 组
（4）校验位取值
校验位 P;的值为第i组（由该校验位校验的数据位）所有位求异或。
根据（3）中的分组有
P1=D1D2D4=011=0
P2=D1+D3+D4=0+0+1=1
P3=D2+D3+D4=1+0+1=0
所以, 1010对应的海明码为1010010 (下画线为校验位,其他为信息位)。
（5）海明码的校验原理
每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查,构成k个校验方程:
Sy=P1+D1+D2+D4
S2=P2+ D1+D3+D4
S3 =P3+D2+ D3 +D4
若S3S2S,的值为“000”,则说明无错;否则说明出错,且这个数就是错误位的位号,如S3SSS,=001,说明第 1 位出错，即Hi出错，直接将该位取反就达到了纠错的目的。
3.3.3 本节习题精选
一、单项选择题
01. 通过提高信噪比可以减弱其影响的差错是( )。
A. 随机差错
B. 突发差错
C.数据丢失差错 D. 干扰差错
02. 下列有关数据链路层差错控制的叙述中，错误的是( ）。
A. 数据链路层只能提供差错检测，而不提供对差错的纠正
B. 奇偶校验码只能检测出错误而无法对其进行修正，也无法检测山对公…
1
海明码“纠错”d位，而多
06. B
在k比特信息位上附加r比特冗余信息，构成k+r比特的码字，必须满足 22k+r+1.
果k的取值小于或等于11且大于4，那么r=4。
在使用多项式编码时，发送端和接收端必须预先商定一个生成多项式。发送端按照模2除注得到校验码,在发送数据时把该校验码加在数据后面。接收端收到数据后,也需要根据该生成项式来验证数据的正确性。
07. B
假设一个帧有m位，其对应的多项式为G(x),则计算冗余码的步骤如下:
08. C
1 加0。假设G(x)的阶为r，在帧的低位端加上r个0。
2 模 2除。利用模2除法，用G(x)对应的数据串去除1中计算出的数据串，得到的余数即为冗余码(共r位，前面的 0不可省略)。
多项式以2为模运算。按照模2运算规则,加法不进位,减法不借位,它刚好是异或操作。乘除法类似于二进制运算,只是在做加减法时按模2规则进行。根据以上算法计算可得答案为选项C。
二、综合应用题
01. 【解答】
根据题意,生成多项式G(x)对应的二进制比特序列为11001。进行如下的二进制模2除法,被除数为10110011010,除数为11001:
1101010
11001
10110011010
11001
11110
11001
11111
11001
11001
11001
00
所得余数为0，因此该二进制比特序列在传输过程中未出现差错。发送数据的比特序列是1011001，CRC 检验码的比特序列是1010。
注意：CRC 检验码的位数等于生成多项式 G(x)的最高次数。
3.4 流量控制与可靠传输机制
3.4.1 流量控制、可靠传输与滑动窗口机制
流量控制涉及对链路上的帧的发送速率的控制,以使接收方有足够的缓冲空间来接收每个帧。例如,在面向帧的自动重传请求系统中,当待确认帧的数量增加时,有可能超出缓冲存储空间而造成过载。流量控制的基本方法是由接收方控制发送方发送数据的速率,常见的方式有两种:停止-等待协议和滑动窗口协议。
1.停止-等待流量控制基本原理
发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧；接收方每接收一帧，
都要反馈一个应答信号,表示可接收下一帧,如果接收方不反馈应答信号,那么发送方必须一直等待,每次只允许发送一帧,然后就陷入等待接收方确认信息的过程中,因而传输效率很低。
2.滑动窗口流量控制基本原理
在任意时刻,发送方都维持一组连续的允许发送的帧的序号,称为发送窗口;同时接收方也维持一组连续的允许接收帧的序号,称为接收窗口。发送窗口用来对发送方进行流量控制,而发送窗口的大小听代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。同理,在接收端设置接收窗口是为了控制可以接收哪些数据帧和不可以接收哪些帧。在接收方,只有收到的数据帧的序号落入接收窗口内时,才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。
图3.7 给出了发送窗口的工作原理，图3.8给出了接收窗口的工作原理。
一
发送窗口WT
(a)
0
2
3
4
5
6
7
0
2
允许发送5个帧WT
不允许发送这些帧
(b)
0
2
3
4
5
6
7
0
2
已发送
还允许发送4个帧WT
不允许发送这些帧
(c)
0
6
7
0
已发送
不允许发送这些帧
WT
(d)
0
一
2
3
4
5
2
2
3
已发送
(a)
0
2
准备接收0号帧
(b)
0
2
3
4
s
3
4
6
7
0
已发送并已收到确认
还允许发送3个帧
不允许发送这些帧
图 3.7 发送窗口控制发送端的发送速率：(a)允许发送 0~4 号共 5 个帧；(b)允许发送 1~4号共 4个帧；(c)不允许发送任何帧；(d)允许发送5～7号共 3个帧
WR
4
5
6
7
0
不允许接收这些帧
WR
7
0
已收到准备接收1号帧
(c)
0
2
3
4
5
6
7
一
0
已收到
准备接收4号帧
不允许接收这些帧
图3.8 Wa=1的接收窗口的意义： (a)准备接收0号帧；(b)准备接收1号帧；(c)准备接收4号帧
一
一
一
5
一
一
1
2
2
6
2
不允许接收这些帧
WR
2
发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口内没有可以发的帧(即窗口内的帧全部是已发送但未收到确认的帧)时,发送方就会停止发送,直到收到接4方发送的确认帧使窗口移动,窗口内有可以发送的帧后,才开始继续发送。
074 2024年计算机网络考研复习指导
接收端收到数据帧后,将窗口向前移一个位置,并发回确认帧,若收到的数据帧落在接收包口之外，则一律丢弃。
滑动窗口有以下重要特性：
1)只有接收窗口向前滑动(同时接收方发送了确认帧)时,发送窗口才有可能(只有发送方收到确认帧后才一定)向前滑动。
2)从滑动窗口的概念看，停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小
与接收窗口大小上有所差别：
停止-等待协议:发送窗口大小=1,接收窗口大小=1。后退 N 帧协议：发送窗口大小>1，接收窗口大小=1。选择重传协议:发送窗口大小>1,接收窗口大小>1。
3)接收窗口的大小为1时,可保证帧的有序接收。
4)数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的(注意与第5 章传输层的滑动窗口协议的区别）。
3. 可靠传输机制
数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。确认是一种无数据的控制帧,这种控制帧使得接收方可以让发送方知道哪些内容被正确接收。有些情况下为了提高传输效率,将确认捎带在一个回复帧中,称为捎带确认。超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一定时间内如果没有得到发送的数据帧的确认帧，那么就重新发送该数据帧，直到发送成功为止。
自动重传请求(Automatic Repeat reQuest, ARQ)通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来差错的方法之一。传统自动重传请求分为三种，即停止-等待(Stop-and-Wait) ARQ、后退N帧(Go-Back-N) ARQ和选择性重传(Selective Repeat)ARQ。后两种协议是滑动窗口技术与请求重发技术的结合,由于窗口尺寸开到足够大时,帧在线路上可以连续地流动,因此又称其为连续ARQ协议。注意,在数据链路层中流量控制机制和可靠传输机制是交织在一起的。
注意：现有的实际有线网络的数据链路层很少采用可靠传输（不同于OSI参考模型的思路)，因此大多数教材把这部分内容放在第5章运输层中讨论，本书按照408考纲，不做变动。
3.4.2 单帧滑动窗口与停止-等待协议
在停止-等待协议中，源站发送单个帧后必须等待确认，在目的站的回答到达源站之前，源站不能发送其他的数据帧。从滑动窗口机制的角度看,停止-等待协议相当于发送窗口和接收窗口大小均为1 的滑动窗口协议。
可之超月
4方收并重亻来表种协就停数据在发只有
在停止-等待协议中，除数据帧丢失外，还可能出现以下两种差错。
到达目的站的帧可能已遭破坏,接收站利用前面讨论的差错检测技术检出后,简单地将该帧丢弃。为了对付这种可能发生的情况,源站装备了计时器。在一个帧发送后,源站等待确认,若在计时器计满时仍未收到确认,就再次发送相同的帧。如此重复,直到该数据帧无错误地到达为止。
另一种可能的差错是数据帧正确而确认帧被破坏，此时接收方已收到正确的数据帧，但发送
方收不到确认帧,因此发送方会重传已被接收的数据帧,接收方收到同样的数据帧时会去弃该帧,并重传一个该帧对应的确认帧。发送的帧交替地用0和1来标识,确认帧分别用ACK0和ACKI来表示，收到的确认帧有误时，重传已发送的帧。对于停止-等待协议，由于每发送一个数据帧就停止并等待,因此用1bit来编号就已足够。在停止-等待协议中,若连续出现相同发送序号的数据帧,表明发送端进行了超时重传。连续出现相同序号的确认帧时,表明接收端收到了重复帧。在发送完数据帧时,必须在其发送缓存中保留此数据帧的副本,这样才能在出差错时进行重传。
此外，为了超时重发和判定重复帧的需要，发送方和接收方都须设置一个帧缓冲区。发送端只有在收到对方发来的确认帧ACK时,方可清除此副本。
由图 3.9 可知，停止-等待协议通信信道的利用率很低。为了克服这一缺点，就产生了另外两种协议，即后退N帧协议和选择重传协议。
数据帧的发送时间
传播时延
DATA
两个成功发送的数据帧
之间的最小时间间隔
处理时间
设置的重传时间lout
a ACК
确认帧发送时间
传播时延布
处理时间tpr
DATA
时间
图3.9 停止-等待协议中数据帧和确认帧的发送时间关系
3.4.3 多帧滑动窗口与后退N帧协议(GBN)
在后退N帧式ARQ中,发送方无须在收到上一个帧的ACK后才能开始发送下一帧,而是可以连续发送帧。当接收方检测出失序的信息帧后,要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧;或者当发送方发送了N个帧后,若发现该N个帧的前一个帧在计时器超时后仍未返回其确认信息,则该帧被判为出错或丢失,此时发送方就不得不重传该出错帧及随后的N个帧。换句话说，接收方只允许按顺序接收帧。
如图 3.10 所示,源站向目的站发送数据帧。当源站发完 0号帧后，可以继续发送后续的1号帧、2号帧等。源站每发送完一帧就要为该帧设置超时计时器。由于连续发送了许多帧,所以确认帧必须要指明是对哪一帧进行确认。为了减少开销,GBN协议还规定接收端不一定每收到一个正确的数据帧就必须立即发回一个确认帧,而可以在连续收到好几个正确的数据帧后,才对最后一个数据帧发确认信息,或者可在自己有数据要发送时才将对以前正确收到的帧加以捎带确认。这就是说,对某一数据帧的确认就表明该数据帧和此前所有的数据帧均已正确无误地收到,称为累积确认。在图3.10中, ACKn表示对第n号帧的确认,表示接收方已正确收到第n号帧及以前的所有帧,下一次期望收到第n+1号帧(也可能是第0号帧)。接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的6个数据帧,但接收端都必须将这些帧丢弃。接收端虽然丢弃了这些不按序的无差错帧,但应重复发送已发送的最后一个确认帧ACK1 (这是为了防止已发送的确认帧ACK1丢失)。
后退 N帧协议的接收窗口为 1，可以保证按序接收数据帧。若采用n比特对帧编号，则其为送窗口的尺寸所应满足1<肝≤2”-1。若发送窗口的尺寸大于2"-1，则会造成接收方无法分院新帧和旧帧(请参考本章疑难点3)。
从图3.10不难看出,后退N帧协议一方面因连续发送数据帧而提高了信道的利用率,另方面在重传时又必须把原来已传送正确的数据帧进行重传(仅因这些数据帧的前面有一个数据幢出了错),这种做法又使传送效率降低。由此可见,若信道的传输质量很差导致误码率较大时,后退N帧协议不一定优于停止-等待协议。
超时间隔
2
5
6
7
8
发送方
0
2
3
4
5
6
8
7
3
4
ack7
ack2
ack3
ack4,
ack5,
ack6,
ack0,
ackL
3
4
5
6
接收方
0
E
D
D
D
D
D
2
出错
被数据链路层丢弃的帧
图3.10 GBN协议的工作原理:对出错数据帧的处理
3.4.4 多帧滑动窗口与选择重传协议（SR)
为进一步提高信道的利用率,可设法只重传出现差错的数据帧或计时器超时的数据帧,但此时必须加大接收窗口，以便先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。这就是选择重传ARQ协议。
在选择重传协议中,每个发送缓冲区对应一个计时器,当计时器超时时,缓冲区的帧就会重传,如图3.11所示。另外,该协议使用了比上述其他协议更有效的差错处理策略,即一旦接收方怀疑帧出错,就会发一个否定帧NAK给发送方,要求发送方对NAK中指定的帧进行重传。
选择重传协议的接收窗口尺寸WR和发送窗口尺寸Wr都大于1，一次可以发送或接收多个帧。在选择重传协议中，接收窗口和发送窗口的大小通常是相同的(选择重传协议是对单帧进行确认，所以发送窗口大于接收窗口会导致溢出,发送窗口小于接收窗口没有意义),且最大值都为序号范围的一半，若采用n比特对帧编号，则需要满足WTmax=WRmax=2(n-1)。因为如果不满足该条件，即窗口大小大于序号范围一半,当一个或多个确认帧丢失时,发送方就会超时重传之前的数据帧,但接收方无法分辨是新的数据帧还是重传的数据帧。
1
超时间隔
发送方
0
1
2
3
4
5
6
7
8
2
9
10
11
12
13
ack0,' ack1,
ack3
ack4
ack5
ack6,
ack7
ack8
ack2,/ ack9, ack10ack11 ack12
接收方
0
1
E
3
4
5
6
7
8
2
9
10
11
12
由数据链路层缓冲的帧
将分组2～8传给网络层
图 3.11 选择重传协议
选择重传协议可以避免重复传送那些本已正确到达接收端的数据帧，但在接收端要设置具有相当容量的缓冲区来暂存那些未按序正确收到的帧。接收端不能接收窗口下界以下或窗口上界以上的序号的帧,因此所需缓冲区的数目等于窗口的大小,而不是序号数目。
在往年统考真题中曾经出现过对“信道效率”“信道的吞吐率”等概念的考查,有些读者未接触过“通信原理”等相关的课程，可能对这些概念不太熟悉，在这里给读者补充一下。
信道的效率,也称信道利用率。可从不同的角度来定义信道的效率，这里给出一种从时间角度的定义:信道效率是对发送方而言的,是指发送方在一个发送周期的时间内,有效地发送数据所需要的时间占整个发送周期的比率。
例如,发送方从开始发送数据到收到第一个确认帧为止,称为一个发送周期,设为T,发送方在这个周期内共发送L比特的数据,发送方的数据传输速率为C,则发送方用于发送有效数据的时间为LC,在这种情况下,信道的利用率为(L/C)/T。
从上面的讨论可以发现,求信道的利用率主要是求周期时间T和有效数据发送时间L/C,在题目中,这两个量一般不会直接给出,需要读者根据题意自行计算。
信道吞吐率=信道利用率×发送方的发送速率。

2024年1月8日 (一) 01:48的版本

取自“http://bubblestudy.info/wiki/index.php?title=Temp&oldid=2712”