第3章-数据链路层

第3章数据链路层

数据链路层负责通信结点间在单个链路上的传输活动，实现帧（frame）的单跳（onehop）传输，可以在不可靠的物理链路上实现可靠的传

输服务。本章首先介绍数据链路层的3个基本问题，即帧同步、透明传输和差错检验；然后介绍实现可靠传输的自动请求重传机制（ARQ）；最后，介绍数据链路层的两个著名协议，即高级数据链路控制规程（HDLC）和点对点协议（PPP），它们是用于点对点链路的传输控制协议。

对于广播链路，数据链路层必须进行共享信道的接入控制，使得链路上的各个结点能够合理地竞争信道，不同的LAN都针对自己的特点设计了接入控制信道接入控制方法。3.1概述1．什么是数据链路

数据链路层的通信对等实体之间的数据传输通道称为数据链路（datalink），它是一个逻辑概念，包括物理线路和必要的传输控制协议。数据链路分为点对点链路和广播链路两类。图3.1数据链路层负责在单个链路上的发送和接收结点之间传送帧2．帧传输的基本问题

实现正常的帧传输，有3个基本问题是共同的，即帧同步、透明传输和差错检验。

3．帧传输的可靠性控制

自动请求重传（AutomaticRepeatreQuest，ARQ）。

4．广播链路的接入控制

介质接入控制（MediumAccessControl，MAC）。3.2帧同步和透明传输3.2.1帧同步1．同步传输同步传输（synchronoustransmission）方式：通信双方使用统一的定位时钟，数据是以称为帧（frame）的较大的数据块为单位进行传送。异步传输（asynchronoustransmission）方式，通信双方各自使用独立的定位时钟，以字符为单位进行数据传输。2．帧同步帧同步在数据链路层实现，帧封装时使用特殊的帧定界符加在帧的首、尾两端，标志一个帧的开始和结束位置。3.2.2透明传输1．伪同步问题2．透明传输的方法对用户数据中与帧定界符一样的字符或比特模式进行变换，字节填充（bytestuffing）和比特填充（bitstuffing）。采用特殊的帧定界符。（1）字节填充（2）比特填充，零比特填充（3）使用特殊的帧定界符3.3差错检验3.3.1差错检验方法

发现差错的常用方法是对信息进行适当的编码，给信息码加上冗余码。由信息码求冗余码的运算是数据链路层协议中约定的。冗余码常称为帧检验序列（FrameCheckSequence，FCS）。数据链路层最常用的差错检验方法是循环冗余检验（CyclicRedundancyCheck，CRC）。3.3.2循环冗余检验1．码多项式一个二进制编码的位串都可以用一个多项式来表示：C(x)=Cn-1xn-1

+Cn-2xn-2

+…+C1x+

C0

数据后面附加上冗余码的操作可以用码多项式的算术运算来表示：2．由信息码生成冗余码

用一个特定的r次多项式G(x)去除xr

K(x)（即），其余数为（r－1）次的码多项式R（x），对应的r位的位串作为冗余码。

G（x）称为生成多项式（generatorpolynomial）。示例:①信息码：1010001，对应的码多项式为K(x)=

x6+x4+1(k=7)；②生成多项式：G(x)=x4+x2+x1+1(r=4)，对应的位串为10111；③x4

K(x):x4(x6+x4+1)=x10+x8+x4，对应的位串为10100010000.3．传输差错检验

接收方将接收到的C（x）除以生成多项式G（x），只要余数不为零，则表明检验出传输差错，若余数为零，则可以认为传输无误。4．常用的生成多项式CRC-8=

CRC-16=

CRC-CCITT=CRC-32=

3.4数据链路控制3.4.1数据链路控制的基本思想可靠的数据链路应该满足两个条件：①传输任何数据既不会出现差错也不会丢失；②不管发送方以多快的速率发送数据，接收方总能够来得及接收、处理并上交主机。也就是接收方有足够的接收缓冲区和处理速度。条件①不满足，就必须进行差错控制（errorcontrol）；条件②不满足就必须进行流量（flowcontrol）。3.4.2数据链路控制的基本机制1．反馈重传机制

反馈重传机制包括以下两步：（1）接收方反馈确认信息①正确认/肯定确认（positiveacknowledgement）正确认简称确认，记为ACK。②累计确认（cumulativeacknowledgement）。③捎带确认（piggybacking）。④负确认（NegativeAcKnowledgement，NAK）或否定确认。（2）发送方重传差错帧

常用的重传方式包括以下两种：①超时重传（timeoutretransmission）；②负确认重传。自动请求重传（ARQ）：停等ARQ（stop-and-waitARQ）；回退-NARQ（go-back-NARQ）；选择重传ARQ（selectiverepeatARQ）。2．滑动窗口机制

发送方和接收方分别设置发送窗口和接收窗口，在数据传输过程中在接收方的控制下向前滑动，从而对数据传输流量进行控制。发送窗口用来对发送方进行流量控制，落在窗口内的帧是可以连续发送的。

接收窗口控制哪些帧可以接收，只有到达的帧的序号落在接收窗口之内时才可以被接收。当接收方收到一个有序且无差错的帧后，接收窗口向前滑动，准备接收下一帧，并向发送方发出一个ACK。接收方的ACK作为授权发送方发送数据的凭证，接收方可以根据自己的接收能力来控制ACK的发送时机，从而实现对传输流量的控制。

图3.2发送方的滑动窗口

3.4.3自动请求重传1．停等ARQ（1）停等ARQ工作机制

在发送方发出一个数据帧后停下来不再发送，等待接收方的ACK到达，ACK到达后才发送下一帧。发送窗口大小是WT=1，接收窗口也是

WR=1

。

停等ARQ要处理传输中可能出现的以下3种传输差错：①接收方收到了发来的数据帧，但检测出收到的帧有差错；②发送方发出的数据帧丢失，接收方收不到，发送方不可能收到ACK；③接收方收到正确的数据帧，但发出的ACK丢失，发送方也不可能收到ACK。

停等ARQ采用超时重传的方式，并对ACK编号。

（2）停等ARQ示例（3）停等ARQ的链路利用率

停等ARQ机制的问题是可能产生严重的低效：η=TDATA/(TDATA+TACK+2

+TPRO)

TDATA

/(TDATA

+2)

=帧的比特长度/（帧的比特长度+2链路的比特长度）图3.3停等ARQ传输过程示例2．回退-NARQ

（1）回退-NARQ工作机制

WT>1，发送方在每收到一个ACK之前不必等待，可以连续地发送窗口内的多个帧，也称为连续ARQ。减少了等待时间，提高了传输的吞吐量和传输效率。使用超时重传机制。定时器超时仍未收到ACK，则要重传此帧，而且还必须重传此帧后面所有的已发帧（不管这些帧是否有传输差错）。接收方的接收窗口WR=1，也就是说，接收方不保存失序的帧，当接收方收到一个有序且无差错的帧后，接收窗口向前滑动，准备接收下一帧，并向发送方发出一个ACK。（2）回退-NARQ示例图3.4回退-NARQ接收窗口图3.5回退-NARQ传输过程示例（3）回退-NARQ发送窗口的限制WT≤2n－1=最大序号（4）回退-NARQ的链路利用率当信道的传输质量好误码率很小时，回退-NARQ协议链路利用率高；反之，则链路利用率降低，不一定能优于停等ARQ。3．选择重传ARQ（1）选择重传ARQ工作原理

在回退-NARQ的基础上作了如下两点改进：①接收窗口WR>1，这样可以接收和保存正确到达的失序的帧；②出现差错时只重传出错的帧，后续正确到达的帧不再重传，提高了信道的利用率。（2）选择重传ARQ发送窗口的限制WT=WR≤2n/2=（最大序号+1）/23.5高级数据链路控制规程同步数据链路控制（SynchronousDataLinkControl，SDLC）高级数据链路控制（HighlevelDataLinkControl，HDLC链路接入规程（LinkAccessProcedure，LAP）平衡型链路接入规程（LAP-Balanced，LAPB）LAPF（LAPforFrame-modebearerservices）3.6因特网数据链路控制协议PPP3.6.1PPP及其帧格式1．概述

PPP可以在多种类型的链路上运行。一种应用场合是家庭用户计算机通过RS232C和Modem拨号连接公共交换电话网PSTN进行Internet接入；另一种常用的场合是由路由器点对点连接而成Internet的一些主干。

PPP主要包括以下3个部分：（1）基于HDLC的多种网络层分组的封装方法（2）链路控制协议（LinkControlProtocol，LCP）（3）网络控制协议（NetworkControlProtocol