第3章数据链路层

第3章数据链路层3.1数据链路层的基本概念3.2停止等待协议

3.2.1完全理想化的数据传输

3.2.2具有最简单流量控制的数据链路层协议

3.2.3实用的停止等待协议

3.2.4循环冗余检验的原理

3.2.5停止等待协议的算法3.3连续ARQ协议

3.3.1连续ARQ协议的工作原理

3.3.2滑动窗口的概念3.4选择重传ARQ协议3.5面向比特的链路层协议HDLC 3.5.1HDLC协议概述

3.5.2HDLC的帧结构

3.6因特网的点对点协议PPP 3.6.1PPP协议的工作原理

3.6.2PPP协议的帧格式

3.6.3PPP协议的工作状态3.1数据链路层的基本概念

链路(link)－－是一条无源的点到点的物理线路段。数据链路(datalink)

－－实现通信协议的软、硬件和链路的集合。现在最常用是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。早期的数据通信协议叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。结点结点帧帧数据链路层的主要功能(1)链路管理(2)帧定界(3)流量控制(4)差错控制(5)将数据和控制信息区分开(6)透明传输(7)寻址3.2停止等待协议（StopandWait）3.2.1完全理想化的数据传输先研究一下数据链路层的模型。局域网广域网主机

H1主机

H2路由器

R1路由器

R2路由器

R3电话网局域网主机H1

向H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动数据链路层的简单模型局域网广域网主机

H1主机

H2路由器

R1路由器

R2路由器

R3电话网局域网主机H1

向H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动完全理想化的数据传输数据链路层主机

A缓存主机

B数据链路AP2AP1缓存发送方接收方帧高层帧完全理想化的数据传输所基于的两个假定：

假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。

3.2.2具有最简单流量控制的数据链路层协议条件：去掉第二个假定，但仍然保留第一个假定。计算机网络中流量控制的基本方法：由收方控制发方的数据流。具有最简单流量控制的数据链路层协议算法在发送结点：(1)从主机取一个数据帧。(2)将数据帧送到数据链路层的发送缓存。(3)将发送缓存中的数据帧发送出去。(4)等待。(5)若收到由接收结点发过来的信息，则从主机取一个新的数据帧，然后转到(2)。在接收结点：(1)等待。(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。(3)将接收缓存中的数据帧上交主机。(4)向发送结点发一确认信息，表示数据帧已经上交给主机。(5)转到(1)。两种情况的对比（传输均无差错）ABDATADATADATADATA送主机B送主机B送主机B送主机BABDATA送主机BDATA送主机B时间不需要流量控制需要流量控制3.2.3实用的停止等待协议时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况ABDATA0DATA0送主机ACK(c)数据帧丢失重传tout丢失！ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失重传tout丢失！ABDATA0NAKDATA0送主机ACK(b)数据帧出错重传出错四种情况解决死锁现象：设置超时计时器结点A发送完一个数据帧时，就启动一个超时计时器(timeouttimer)。计时器又称为定时器。若到了超时计时器所设置的重传时间

tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧。一般可将重传时间tout选为略大于“从发完数据帧到收到确认帧所需的平均时间”。

解决重复帧的问题

使每一个数据帧带上不同的发送序号。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。但此时结点B还必须向A发送确认帧ACK，因为B已经知道A还没有收到上一次发过去的确认帧ACK。帧的编号问题

任何一个编号系统的序号所占用的比特数一定是有限的。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号。一个比特可表示0和1两种不同的序号帧的发送序号数据帧中的发送序号N(S)

以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号和上次发送的不一样。因此，可以使收方区分开新的数据帧和重传的数据帧。可靠传输由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。

3.2.4循环冗余检验的原理

在数据链路层传送的帧中，广泛使用了循环冗余检验CRC

的检错技术。差错检验原理：发送方通过CRC方法得到检验码，将检验码放在数据之后一起发送，接收方收到后，再通过检验算法（除以生成多项式P，根据余数），判断数据是否出现差错。循环冗余检验的原理：用二进制的模2运算进行2n乘M的运算。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R（检验码）。基本概念：

信息位M，生成多项式P－－n＋1bit

R－－冗余码/检验码（nbit）

计算冗余码的实例：

假设待传送的数据M=1010001101（共kbit），计算供差错检测用的nbit冗余码。

设

n=5P=110101

模2运算的结果是：商Q=1101010110，余数R=01110。

将余数R作为冗余码添加在数据M的后面发送，即发送的数据是101000110101110，或2nM+R。

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2nM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数循环冗余检验的原理说明

帧检验序列FCS

在数据后面添加上的冗余码称为帧检验序列

FCS(FrameCheckSequence)。循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非是用来获得FCS的唯一方法。

检测出差错（接收方）接收的数据除以生成多项式P，只要得出的余数R不为0，就表示检测到差错。但这种检测方法并不能确定是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到差错的概率就很小。应当注意

仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接受的帧都没有传输差错”。要做到“可靠传输”，就必须再加上确认和重传机制。3.2.5停止等待协议的算法不使用否认帧，而且确认帧带有序号n。ACKn

表示“第n–1

号帧已经收到，现在期望接收第n号帧”。ACK1表示“0号帧已收到，现在期望接收的下一帧是1号帧”；ACK0表示“1号帧已收到，现在期望接收的下一帧是0号帧”。

在发送结点

(1)从主机取一个数据帧，送交发送缓存。(2)V(S)←0。(3)N(S)←V(S)。(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。{等待以下(7)和(8)这两个事件中最先出现的一个}(7)收到确认帧ACKn，若n=1–V(s)，则：从主机取一个新的数据帧，放入发送缓存；

V(S)←[1V(S)]，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。在接收结点

(1)V(R)←0。(2)等待。(3)收到一个数据帧；若N(S)=V(R)，则执行(4)；否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件（也就是数据链路层模型中的主机）。(5)V(R)←[1V(R)]。(6)n←V(R)；发送确认帧ACKn，转到(2)。停止等待协议的要点只有收到序号正确的确认帧ACKn

后，发送端才更新发送状态变量V(S)，并发送新的数据帧。接收端接收到数据帧时，就要将发送序号N(S)与本地的接收状态变量V(R)相比较。若二者相等就表明是新数据帧，收下并发送确认。否则为重复帧，丢弃。但仍须向发送端发送确认帧ACKn，而接收状态变量V(R)和确认序号n都不变。

停止等待协议的要点连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧。发送端在发送完数据帧时，必须在发送缓存中暂时保留这个数据帧的副本，才能在出错时重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。停止等待协议的要点实用的CRC检验器都是用硬件完成的。CRC检验器能够自动丢弃检测到的出错帧。发送端对出错的数据帧进行重传是自动进行，因而这种差错控制体制常简称为ARQ(AutomaticRepeatreQuest)，直译是自动重传请求，但意思是自动请求重传。

停止等待协议中数据帧和确认帧的发送时间关系

ABDATADATAACK传播时延tp处理时间tpr确认帧发送时间ta传播时延tp处理时间tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout重传时间的作用：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。停止等待协议ARQ的优缺点

优点：比较简单。缺点：通信信道的利用率不高。为了克服这一缺点，就产生了另外两种协议：连续ARQ和选择重传ARQ。3.3连续ARQ协议

3.3.1连续ARQ协议的工作原理

在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。连续ARQ协议的工作原理

DATA0DATA1DATA2DATA3DATA4DATA5重传DATA2重传DATA3ACK1ACK2ACK1确认DATA0ACK2确认DATA1DATA2出错，丢弃DATA3不按序，丢弃，重传ACK2DATA4不按序，丢弃，重传ACK2DATA5不按序，丢弃，重传ACK2ACK3ACK3确认DATA2ACK4确认DATA3ACK4重传DATA5重传DATA4超时重传时间ABtout送交主机送交主机…??ACK2ACK2ACK2需要注意：

接收端只按序接收数据帧。连续ARQ协议的发送序号。ACK1表示确认0号帧DATA0，并期望下次收到1号帧；ACK2表示确认1号帧DATA1，并期望下次收到2号帧。依此类推。(3)结点A在每发送完一个数据帧时都要设置该帧的超时计时器。重传时将出错帧及其以后的各帧全部进行重传。

连续ARQ

又称为Go-back-NARQ，即当出现差错必须重传时，要向回走N个帧，然后再开始重传。

3.3.2滑动窗口的概念发送端和接收端分别设定发送窗口和接收窗口。发送窗口用来对发送端进行流量控制。发送窗口的大小WT

：表示在还没有收到对方确认信息的情况下，发送端最多可以发送多少个数据帧。

01234567012发送窗口WT不允许发送这些帧允许发送5个帧(a)01234567012不允许发送这些帧还允许发送4个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送

3个帧WT已发送已发送并已收到确认(d)接收端设置接收窗口

在接收端，当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续ARQ协议中，接收窗口的大小WR=1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃。每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。

不允许接收这些帧01234567012WR准备接收0号帧(a)不允许接收这些帧01234567012WR准备接收

1号帧已收到(b)不允许接收这些帧01234567012WR准备接收4号帧已收到(c)滑动窗口的重要特性只有在接收窗口向前滑动时（同时也发送了确认信息），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于1时，就是停止等待协议。发送窗口的最大值

当用n个比特进行编号时，若接收窗口的大小为1，则只有在发送窗口的大小WT

2n1时，连续ARQ协议才能正确运行。例如，当采用3bit编码时，发送窗口的最大值是7而不是8。

3.4选择重传ARQ协议

可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。选择重传ARQ协议可避免重复传送那些本来已经正确到达接收端的数据帧。但我们付出的代价是在接收端要设置具有相当容量的缓存空间。对于选择重传ARQ协议，若用n

比特进行编号，则接收窗口的最大值受下式的约束WR

2n/23.5面向比特的链路控制规程HDLC

3.5.1HDLC协议概述控制规程IMP-IMP以及BSC均是面向字符的数据链路层协议1974年，IBM公司推出了面向比特的规程SDLC(SynchronousDataLinkControl)。ISO把SDLC修改－－高级数据链路控制HDLC(High-levelDataLinkControl)，作为国际标准ISO3309。CCITT将HDLC修改－－链路接入规程LAP(LinkAccessProcedure)。HDLC的新版本－－LAPB，“B”表示平衡型(Balanced)，LAPB叫做链路接入规程(平衡型)。HDLC的特点：站－－指链路两端的通信设备。1）站的类型主站－－负责控制链路的操作，由主站发出的帧称为命令。从站－－在主站控制下操作，由从站发出的帧称为响应。复合站－－兼具主站和从站的特点，发出的帧称为命令/响应。2）链路配置非平衡配置－－由一个主站和一个或多个从站构成。平衡配置－－由两个复合站组成。3）数据传送方式正常响应方式NRM：只有主站可以启动数据传输，从站在收到主站发来的命令帧后，才能向主站发送数据。异步平衡方式ABM：任何一个复合站都可以启动数据传输。异步响应方式ARM：从站可以主动向主站发送数据，但主站负责链路的管理。3.5.2HDLC的帧结构标志字段F(Flag)：码型“01111110”，共8bit。在接收端只要找到标志字段就可确定一个帧的位置。比特888可变168信息

Info标志

F标志

F地址

A控制

C帧检验序列

FCS透明传输区间FCS检验区间零比特填充法

HDLC采用零比特填充法使一帧中两个F字段之间不会出现6个连续1。在发送端，当一串比特流数据中有5个连续1时，就立即填入一个0。在接收帧时，先找到F字段确定帧的边界。接着再对比特流进行扫描。每当发现5个连续1时，就将其后的一个0删除，以还原成原来的比特流。

零比特的填充与删除数据中某一段比特组合恰好出现和F字段一样的情况01001111110001010会被误认为是F字段发送端在5个连1之后填入0比特再发送出去填入0比特010011111010001010在接收端将5个连1之后的0比特删除，恢复原样在此位置删除填入的0比特010011111010001010透明传输

采用零比特填充法就可传送任意组合的比特流，或者说，就可实现数据链路层的透明传输。当连续传输两个帧时，前一个帧的结束标志字段F可以兼作后一帧的起始标志字段。当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步。其他字段

地址字段A是8bit。帧检验序列FCS字段共16bit。所检验的范围是从地址字段的第一个比特起，到信息字段的最末一个比特为止。控制字段C共8bit，是最复杂的字段。HDLC的许多重要功能都靠控制字段来实现。HDLC帧的类型：信息帧（I）监控帧（S）无编号帧（U)1、信息帧I控制字段用于传输高层用户信息。N(S)：当前发送帧的序号；N(R)：本站期望接收的帧的序号P/F：探询/终止比特N(S)P/FN(R)0123456782、监控帧S控制字段保护I帧的正确传送，进行流量控制和差错控制。字段SS：00表示接收准备好（RR帧）用于发送对已接收帧的确认信息；10表示接收未准备好（RNR帧）用于表示确认信息，但暂停接收帧。01表示拒绝帧（REJ帧）用于重传请求。11表示选择拒绝帧（SREJ帧）用于选择重传请求。SSP/FN(R)10123456783、无编号帧U控制字段实现对链路的建立和断开过程的控制，可以随时发出。字段M：用于区分不同的U帧，目前只定义了15种U帧。实际例子：数据链路的建立和拆除MP/FM1112345678SABMSABMUADISCUAAB双向数据交换ABI.2.1RR,2N(S)N(R)I.0.0A发送0号帧I.0.1B收到并确认，同时发送自己的0号帧I.1.1A收到并确认，同时发送1，2号帧I.1.3B收到并确认，同时发送自己的1号帧A暂时无信息帧，用RR帧表示确认信息系统忙ABI.3.0B收到并确认，同时发送自己的3号帧RNR,4A系统忙，要求B暂时停发I帧RR,0,PB收到，将RR中P置“1”，对A站进行探询RNR,4,FA系统仍忙RR,0,PRR,4,FA系统不忙出错处理ABI.5.0I.3.0A发送数据，第4帧出错REJ,4B收到并确认，同时要求重传I.4.0A重传I.4.0I.5.03.6因特网的点对点协议PPP

3.6.1PPP协议的工作原理现在全世界使用得最多的数据链路层协议是点对点协议

PPP(Point-to-PointProtocol)。用户使用拨号电话线接入因特网时，一般都是使用PPP协议。用户拨号入网的示意图

路由器调制解调器调制解调器因特网服务提供者(ISP)用户家庭拨号电话线使用TCP/IP的

PPP连接使用TCP/IP的客户进程路由选择进程至因特网…PC机PPP协议

1992年制订PPP协议，经过1993年和1994年的修订，PPP协议已成为因特网的正式标准[RFC166