数据链路层课件教材讲义

第三章数据链路层3.1数据链路层的模型、功能及服务3.2数据链路层设计的一般特性3.3实用的数据链路层协议2024/4/193.1数据链路层的模型、功能和服务主机A主机B结点1结点2结点3传输层协议数据链路层协议数据链路层协议数据虚通路数据虚通路数据实通路数据实通路数据链路/逻辑链路=（物理）链路+通信规程数据链路层提供的数字信道物理层提供的无源点到点物理线路段数据链路层协议一、数据链路层的模型(p176Fig3-1)2024/4/19二、数据链路层向网络层提供的服务基本服务：

将源结点的网络层数据传送到相邻的目的结点的网络层三种服务：（p177）

1.无确认的无连接服务：目的结点不作确认，差错由上层负责

2.有确认的无连接服务：目的结点对收到的帧要作确认，源结点可以知道已发出的帧是否安全到达目的结点；误帧重传

3.面向连接服务：可靠地传送数据的服务，即提供在网络实体间建立、维持和释放数据链路的功能2024/4/19面向连接服务的服务原语：连接建立阶段：DL-CONNECT.request,DL-CONNECT.indication, DL-CONNECT.response,DL-CONNECT.confirm

维持阶段：

DL-DATA.request,DL-DATA.indication

释放阶段：DL-DISCONNECT.request, DL-DISCONNECT.indication,,2024/4/19网络层实体的通信过程示例数据链路层实体数据链路层实体网络层实体网络层实体系统A系统BDL-C.reqDL-C.conDL-C.resDL-C.ind响应帧DL-DC.indDL-D.reqDL-DC.indDL-D.ind连接请求帧DL-DC.req释放连接请求帧响应帧确认帧数据帧DL-D.ind连接建立阶段数据传送阶段连接释放阶段2024/4/19三、数据链路层的功能

数据链路管理

成帧

流量控制

差错控制

寻址：同步、定界及透明传输2024/4/193.2数据链路层设计的一般特性

字符计数法：帧头中使用一个字符来表示帧内的字符数 缺点：计数字段一旦出错，将无法再同步(p180Fig3-3)一、控制信息的形成方法（成帧）（p179）

带填充字符的首尾界符法：以特定的字符序列为控制字段 缺点：依赖于字符集，不通用，也无法扩展(p181Fig3-4)

带填充位的首尾标志法：采用统一的帧格式，以特定的 位序列进行帧同步和定界(p181Fig3-5)

物理层编码违例法：IEEE802协议 只适用于在物理媒体的编码策略中采用了冗余技术的网络 优点：无需填充2024/4/19带填充字符的首尾界符法（面向字符）:帧首同步字符帧尾数据Bisync

传输帧填充字符SYNSYNDLESTXADLEDLEBDLEDLECDLEETX帧首011111100111110110111110001111110帧尾数据带填充位的首尾标志法（面向位）：HDLC填充位

2024/4/19二、差错控制

目的：确保帧可靠地交付接收方

基本方法：接收方进行差错检测，并向发送方应答，告知是否 正确收到帧

差错检测和纠正

检错码、纠错码

汉明距离：两个码字中不同位的个数

纠正单比特差错所需的最少校验位数公式：（m+r+1）<2r n位码元，其中m位数据，r位校验

汉明纠错法：纠正单比特错

CRC码：可检测出所有奇数位错及长度<r的并发错误2024/4/19汉明码纠错示例对码字从左至右开始编号，位号为2的幂（如1,2,4,..）放校验位，每个校验位分别对某些位进行校验；其他位为数据位，将数据位写成2的幂的和的形式。采用奇偶校验来确定校验位的值。接收方检查每个校验位，出错的校验位的位号之和就是出错的数据位的位号eg.p186Fig3-6采用偶校验

‘H’100,1000位号1234567891011数据位：

10010003=1+2，5=1+4，6=2+4，7=1+2+4...校验位1负责第3,5,7,9,11位，位2负责第3,6,7,10,11位位4负责第5,6,7位，位8负责第9,10,11位00102024/4/19CRC（循环冗余码/多项式编码）

编码思想：将位串看成系数为0或1的多项式

检错思想：收发双方约定一个生成多项式G(x)（其最高阶和最低阶系数必须为1），发送方在帧的末尾加上校验和，使带校验和的帧的多项式能被G(x)整除；接收方收到后，用G(x)除多项式，若有余数，则传输有错

校验和计算算法

若G(x)为r阶，原帧为m位，其多项式为M(x)，则在原帧后面添加

r个0，帧成为m+r位，相应多项式xrM(x)

按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串

按模2减法从对应于xrM(x)的位串中减去余数，结果就是要传送的带校验和的帧的多项式T(x)

T(x)=xrM(x)+[xrM(x)MOD2G(x)]

2024/4/19CRC校验示例(p189Fig3-7)待校验数据：1101，0110，11G(x)=x4+x+1,即100111101011011000010011

1100001010

10011

10011

10011

000010110

10011

10100

10011

1110余数传送序列：1101,0110,1111,102024/4/19第四次作业讨论题： 1.画出在网络实体通信过程图中，连接请求被拒绝的情形和数据传送差错的情形 2.P240--4作业： 1.采用CRC校验，设G(x)=x5+x3+1，网络层交付的数据为0100,1111,1001，忽略控制字段，写出数据链路层传送的帧2.p240--8 3.证明使用CRC方法，k个校验位可以检测出长度小于k的突发错误。

2024/4/19差错控制技术自动请求重传AutomaticRepeatRequest(ARQ)}协议停止等待ARQGo-back-NARQ选择重传ARQ差错检测肯定应答（确认）否认超时后重传2024/4/19三、发送方式（流控制技术）

理想化的数据传输无需数据链路层协议(p1953.3.1)假定1：链路是理想的传输信道，数据既不会出错也不会丢失假定2：不管发送方的速率多快，接收方总能接收到并上交

等待发送（停止等待协议）发送方发出一帧后，要停下来等待接收方的应答，收到确认后才能发送下一帧

连续发送（连续ARQ协议/流水线协议）发送方可以连续发送若干帧，如果在此过程中收到接收方的肯定应答，可以继续发送；若收到对其中某一帧的否认帧，则从该帧开始的后续帧全部重发2024/4/19从主机取数据上交主机DATA1DATA4DATA3DATA2结点A结点B从主机取数据上交主机DATA1DATA2结点A结点B从主机取数据上交主机DATA1DATA3DATA2结点A结点BACKACKDATA5DATA4DATA4NAK4ACK2

理想信道

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

流水线协议DATA52024/4/19一、实用的停止等待协议（有噪声信道的单工协议）(p1973.3.3)

前提：实际信道不满足理想化数据传输的假定3.3实用的数据链路层协议

流量控制方法：等待发送

差错控制：发送方数据帧中加入校验码（CRC），由接收方检查；若出错，返回NAK，发送方收到NAK后重发

帧丢失处理：超时定时器；以序号标识数据帧

优点：简单

缺点：信道利用率低2024/4/19停止等待协议dataiACKdatai+1检查，如果正确，则发出对刚收到的数据帧的应答发出一帧等待，直到收到ACK才发送下一帧发送方接收方2024/4/19停等ARQframeiACK

iframeI+1ACKi+1framei+2framei+2ACKi+2frame

i+3ACKi+3frame

i+3ACKi+3发送方接收方超时超时帧丢失

重发ACK丢失

重发，丢弃重复帧2024/4/19停等协议的算法流程（p201Fig3-11）SGet1stDatafromNetworkLayerV(s)=0N(s)=V(s)SaveDateFrametoBufferSendBufferedDataFrametoPhysicalLayerStartTimerWaitEventReceivedACKReceivedNAKTimeOutGetNextDataV(s)=1-V(s)RV(r)=0WaitDataFrameReceivedFrame,andTestifErroroccursCorrectErrorN(s)=V(r)?DiscardFramePassDatatoNetwokLayerSendACKSendNAKSendACKV(r)=1-V(r)2024/4/19停等协议的定量分析DATAACKDATAtftTtouttptprtatptprtf

帧发送时延ta应答发送时延tp

传播时延tpr

帧处理时延tout超时时间tT

两个成功发送的帧之间的间隔tf

=lf/C其中lf

为帧长，C为信道数据率tout=2tp+2tpr+ta

2tptT

=tf

+2tp设数据帧出错概率为p，应答帧不会出错，重发次数不限，则正确传送一帧的平均时间为：

tAV

=tT

+(1-p)ipitT=tT

/(1-p)最大吞吐量（每秒成功发送的最大帧数）

max

=1/

tAV

=(1-p)/tT2024/4/19设长度为lf的帧中数据有ld位，则

1-p平均有效数据率D=

maxld=——ld

tT

Dld(l-p)

ld

tf

ld1-p信道利用率U=—=————-=————(1-p)=————— C

tTC

lf

tT

lf1+2

代入tf=lf/C，tT

=tf

+2tp，并设=tp/tf2024/4/19二、连续ARQ协议

工作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送；若收到对其中某一帧的否认帧，则从该帧开始的后续帧全部重发

流量控制方法：连续发送

差错控制：同停等协议

优点：连续发送提高了信道利用率

缺点：回走重传（Go-back-N）,导致某些已正确接收的帧的重传，因此降低了发送效率

误码率较低时，连续ARQ优于停等协议；反之则不一定2024/4/19Go-back-NARQ(p2073.4.2)frame1senderreceiver出错7,8帧被丢弃frame

2frame3ACK5frame4frame5frame6frame7frame8NACK

6ACK9frame7frame6frame86,7,8帧重传frame1senderreceiver丢失7,8,9帧被丢弃frame

2frame3ACK5frame4frame5frame6frame7frame8ACK10frame7frame6frame86,7,8,9帧重传toutframe9frame9ACK62024/4/19滑动窗口(SlidingWindow)概念(p202--204)

前提：在连续ARQ协议中，必须对可以连续发出的最多帧数 （已发出但未确认的帧）作限制

原则：循环重复使用有限的帧序号

流量控制：

发送窗口：其大小WT表示在收到对方确认的信息之前，可以连续发出的最多数据帧数（只有序号在窗口内的帧才可以发送）

接收窗口：其大小WR为可以连续接收的最多数据帧数（只有序号在窗口内的帧才可以接收，否则丢弃）

接收窗口驱动发送窗口的转动

发送窗口的最值：WT+WR

2n(n为序号的位数)

WT

2n-1

2024/4/19滑动窗口协议0123456701234567已成功发出的数据帧已发出未经确认的数据帧和将发出的数据帧窗口后沿窗口前沿帧序号发送方缓冲区0123456701234567已正确接收的数据帧将收到的数据帧帧序号接收方缓冲区窗口后沿窗口前沿2024/4/19滑动窗口示例0123456701234567012345

670123456701234567012345670123456

701234567012

3456701

2

34567012

3

4567012345670,1,2ACK33,4,5,6ACK72024/4/19WT=5WR=1发出帧0,100001111422223333444555566667777HHHHHHTT发出帧2，接收到ACK1滑动窗口示例接收到帧0，发出ACK1初始状态0011223344556677T初始状态TTT接收到帧1发出ACK22024/4/190011223344556677H发出帧3,4滑动窗口示例HHHHH01234567012345670123456701234567定时器超时重发帧1接收到ACK2接收到帧3,还没有收到帧2接收到重传的帧1接收到帧2TTTTTT丢弃帧3丢弃帧1，重发ACK22024/4/19连续ARQ协议的定量分析frame1丢失frame3frame4frame2frame2touttftTtf:帧的发送时延tp:传播时延=tp

/tf

tout:超时时间ACK2tp设数据帧出错概率为p，应答帧不会出错，重发次数不限，则正确传送

ptT

+(1-p)tf

一帧的平均时间为：

tAV

=tf

+(1-p)ipitT=———————————

i=1

1-ptT:出错时，帧的重发时延

tT=tf

+

tout发送窗口大小WT=Ntfframe3tout=?

(N-1)tf

(N-1)tf>2tp即N>2+1{2

tp

(N-1)tf<2tp即N<2+12024/4/19 1-p连续ARQ的最大吞吐量

max

=1/

tAV

=——————

ptT

+(1-p)tf{{

(1-p)/[1+(2-1)p]tf

N<2+1

代入tT

及

则

max

=

(1-p)/(1-2p+Np)tfN>2+1平均有效数据率D=

maxld代入tf=lf/C，

ld1-p

———————— N<2+1

lf

1+(2-1)p信道利用率U=D/C=

ld1-p

——————N>2+1

lf

1-2p+Np2024/4/19讨论题： 1.采用3位序号的连续ARQ的发送窗口最大是多少？为什么？ 2.全双工通信中采用ARQ协议，可以有哪些应答策略？

作业： 1.p240--11 2.p240--12，将题目中的“协议5”改为“连续ARQ协议”

第五次作业2024/4/19三、选择重传ARQ协议(p2133.4.3)

原则：只重传出错或定时器超时的数据帧

方法：WR>1，暂存接收窗口中序号在出错帧之后的数据帧

优点：避免重传已正确传送的帧，提高了信道利用率

缺点：在接收端需要占用一定容量的缓存

接收窗口的最值：

WR

WT WR

2n-12024/4/19选择重传

ARQ(p2133.4.3)frame0senderreceiver出错frame1frame2ACK3frame3frame4frame5frame6frame7NACK5ACK2frame0frame5frame1只重传帧5WT=5WR=3Frame5,6,72024/4/19第六次作业讨论题：1.选择重传ARQ协议中，发送窗口和接收窗口的前后沿的值有什么关系？2.p240--153.p240--17作业：试推导出选择重传ARQ协议的信道利用率公式2024/4/19

面向字符协议的不足：采用停等协议，半双工通信，通信线路利用率低；所有通信设备必须使用同样的字符代码只对数据部分进行差错控制，可靠性差依赖于字符集，不易扩展

面向位协议的类型：(p225-226)IBMSNA的SDLC（同步数据链路控制

）ANSI的ADCCP（先进的数据通信控制规程）ISO的HDLC（高级数据链路控制）CCITT的LAP（链路接入规程）X.25采用LAPB（链路接入规程----平衡型）四、HDLC协议2024/4/191.HDLC的两种配置、三种方式主站：发送命令帧、数据信息帧和应答帧，并负责控制链路从站（次站）：接收命令帧，向主站发送响应帧，并配合主站进行链路控制复合站（组合站）：同时具有主站和从站功能。

两种基本配置：非平衡配置点---点工作、多点工作 平衡配置点---点工作

三种方式：正常响应方式NRM数据传输由主站发起， 从站只能响应主站的轮询 异步响应方式ARM从站可以主动发送响应帧 异步平衡方式ABM任一复合站都可以发起数据传输2024/4/19命令(B)响应(B)命令(B/C/D)命令(B)命令(A)响应(B)响应(A)响应(B)响应(C)响应(D)主站A主站A从站B从站B从站C从站D复合站A复合站B非平衡配置：点---点非平衡配置：点---多点平衡配置2024/4/192.HDLC的帧结构(p226Fig3-24)FInfoCAFFCS8位16

0888校验区间透明传输区间

帧同步：标志F“0111，1110”标记帧的首尾边界

透明传输：零比特填充

地址字段A：非平衡方式，填入从站地址 平衡方式，填入响应站地址

帧检验序列FCS：采用CRC-CCITT16，G(x)=x16+x12+x5+1

控制字段C：标记帧类型，并附加控制信息2024/4/19HDLC帧类型(p2273-25)信息帧监督帧无编号帧12

3

45

6

7

800111FrametoSendN(S)FrameExpectedN(R)P/FP/FP/FN(R)M分类S分类M

序号N(S)和N(R)以3位表示，模8循环，N(R)表示准备接收的最低帧序号，确认序号在其前面的帧都已正确接收（捎带应答）

状态变量V(S)和V(R)记录N(S)和N(R)的值

扩展方式，序号N(S)和N(R)以7位表示，模128循环，用于卫星链路，此时控制字段占16位2024/4/19监督帧的类型S=00RR（ReceiveReady）,准备接收下一帧， 确认N(R)-1及以前的各帧

01RNR（ReceiveNotReady）,暂停接收下一帧， 确认N(R)-1及以前的各帧

10REJ（Reject）,否认自N(R)开始的帧

确认N(R)-1及以前的各帧

11SREJ(SelectiveReject),只否认N(R)帧

确认N(R)-1及以前的各帧

连续ARQ选择重传ARQ2024/4/19P/F位的意义（询问/终止）=1非平衡配置正常响应方式主站

S/I帧P=1（命令）

S/I帧（响应）I中F=1，表示最后一个数据帧S中F=1，表示此时没有数据要发送从站NRM异步响应方式ARM平衡配置异步平衡方式

ABMP=1（询问）F=1（回答本站状态）命令方响应方=0无意义2024/4/19非平衡配置的正常响应方式（主从方式）B,RR0,PFB10RRP=1000FCSFFACB,I10FB0001

0000FCSFI主站A从站B、CB,RR0,PB,I00B,I10B,I20B,I30,FB,RR4C,RR0,PC,RR0,FP=1的询问具有强制性，对方必须立即应答

2024/4/19平衡配置的异步平衡方式（对等方式）：全双工通信B,RR2,FFB10RRF=1010FCSFFACA,I10,PFA0001

P=1000FCSFI复合站A复合站BB,I00,PA,I00A,I22丢失A,I34A,I45B,I42B,I10B,I20B,I31A,I10,PB,RR2,FA,RR2,FB,I52B,I62B,I72A,I26,PB,I02B,I12A,I30A,RR3,FtoutB,I23A,I432024/4/19无编号帧，定义了15种，起控制作用

建立数据链路：正常响应方式，置正常响应方式SNRM

异步平衡方式，置异步平衡方式SABM

拆除数据链路：断连命令DISC

对命令的确认：无编号确认UA

帧拒绝FRMR：表示通过重发仍不能纠正的错误，如收到非法命令、帧中的控制字段无效、数据字段过长、N(R)无效、监督帧或无编号帧长度错误等等

携带信息（I字段）的无编号帧：无编号信息UI，用于数据链路层