第3章数据链路层

计算机网络原理第3章数据链路层

第3章数据链路层3.1数据链路层的功能3.2成帧与帧同步

3.3差错控制 3.4流量控制 3.5链路管理3.6协议验证

第3章数据链路层基本内容：数据链路层的基本概念，数据链路层协议的工作原理：停止等待协议，连续ARQ协议，滑动窗口，选择ARQ协议，Internet中的数据链路层协议。重点掌握：数据链路层的基本概念。数据链路层协议的工作原理。滑动窗口原理。

数据链路层的基本概念

链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。

数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。数据链路/逻辑链路=物理链路+通信规程数据链路层的简单模型局域网广域网主机

H1主机

H2路由器

R1路由器

R2路由器

R3电话网局域网主机

H1

向

H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动

数据链路层的简单模型：局域网广域网主机

H1主机

H2路由器

R1路由器

R2路由器

R3电话网局域网主机H1

向H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动

该层要解决的问题：如何在有差错的线路上，进行无差错传输。数据链路层协议功能图示。

数据链路层的模型

数据链路层像个数字管道

常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。结点结点帧帧在数据链路层上传输数据帧？发送方：？接收方：？传输过程：！解决这些问题，是数据链路层的主要任务。！针对这些问题所制定的通信规程就是数据链路层的通信协议。以多快的速度发送数据帧，即每帧之间相隔多长时间？如何确认对方是否收到数据？是否接收到正确的数据帧？如何告诉发送方？能及时处理接收到的数据帧吗？会出错吗？会丢失数据帧吗？基本功能向网络层提供可靠的、透明的数据传输服务，将源节点的网络层数据可靠地传送到相邻节点的网络层主要功能描述链路管理封装成帧流量控制差错控制将数据和控制信息区分开透明传输寻址数据链路的建立、维持和释放两结点通信前要交换一些信息，称为建立数据连接，然后传输数据数据链路层，数据的传送以帧为单位帧定界(帧同步)是指接收方能从收到的比特流中区分一个帧的开始和结束的地方发送方发送数据的速率必须使接收方能来得及接收纠错：通过编码技术，接收方自动将差错改正过来检错：检测出帧有错误，要么忽略或重传数据和控制信息在同一个帧中，收方将其区分开不管所传数据的比特组合，都能在链路上传送；若所传的数据的比特片段与某一个控制信息相同，要有可靠机制，保证收方能正确识别每一帧都能送到正确的目的地；收方也能知道发送方的地址3.1数据链路层的主要功能10数据链路层基于物理层的服务，为网络层提供透明的、正确有效的传输链路。链路层有四大功能：1．成帧和传输 物理层以比特为单位进行数据传输，数据链路层则把数据组织成一定大小的数据帧，以帧为单位发送、接收、校验和应答。不同网络其帧的格式或长度不同，将比特流分为帧的方法基本相同，常用的方法有： 带填充字符的首尾界符法、带填充位的首尾标志法。（1）带填充字符的首尾界符法图4.1带填充字符的首尾界符法（2）带填充位的首尾标志法 发送方数据链路层若在数据中遇到5个连续的1时，自动在其后填充一个0到输出位流中。图4.2带填充位的首尾标志法 2．流量控制：发送速率和接收速率进行控制，使收发一致 3．差错控制：接收端对帧进行校验；发送端设置定时器，超过时间则重发帧 4．链路管理 发送端和接收端之间通过交换控制信息，来建立、维护和释放数据链路，这就是链路管理。图4.3服务原语的表示方式组帧(framing)就是在一段数据的前后分别添加首部和尾部，这样就构成了一个帧。目的：使接收方能准确识别帧的边界首部和尾部的一个重要作用就是进行帧定界≤MTU数据链路层的帧长3.2成帧与帧同步17帧定界（帧同步）的方法1、字节计数法2、使用字符填充的首尾定界法3、使用比特填充的首尾定界法*4、违法编码法18思想在帧头设置一个长度域，放置该帧的字节数，当收方收到帧后，通过帧的长度，确定帧的开始。问题当帧的长度域出错，帧同步完全丢失；该方法很少单独使用。1、字节计数法19字节计数法举例20思想使用特殊的ASCII字符（不可打印的控制字符）作为帧的起始和终止定界符。例如：使用SOH作为开始符，EOT作为结束符。问题：数据传输不透明当数据中出现定界符(SOH或EOT)时，如何加以区分是数据还是定界符？解决：字符填充发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)。接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。2、字符填充法21缺点：使用字符来控制帧的传输，数据传输的单位是字符(8bit的ASCII)，帧的长度是8的倍数；传输任意长度的二进制比特带来不便。字符填充法举例SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符SOH如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。22思想使用一个特殊的比特模式01111110作为帧的起始和结束标志。发送方边发送边检查数据，每连续发送5个“1”后在后面自动插入一个“0”。这样数据中只会连续出现5个“1”，而不会出现定界符。接收方在收到5个连续的“1”后将后面的“0”删掉而恢复出原始数据。好处数据传输的基本单位是比特而不是字符，可用来传输任意长度的二进制比特串，通用性强。3、比特填充法23零比特的填充与删除01001111110001010数据中某一段比特组合恰好出现和定界符一样的情况会被误认为是定界符发送端在5个连1之后填入0比特再发送出去填入0比特010011111010001010在接收端将5个连1之后的0比特删除，恢复原样在此位置删除填入的0比特01001111101000101024比特填充法举例25前提物理介质上使用的信号编码有冗余码字时，使用这些冗余的码字来作为帧的定界。举例如曼彻斯特编码或差分曼彻斯特编码中，有效电平是“低－高”或“高－低”，而“低－低”和“高－高”电平没有定义，这种违法编码可以作为帧的边界。4、违法编码法263.3差错控制物理层的任务是接收一个原始的比特流，并准备将它传输到目的地，物理层并不保证这个比特流的正确传输，传输的比特流个数和内容可能会发生变化，即产生差错。目前已有的物理层协议不进行任何检测和纠错，物理层产生差错由数据链路层负责检测或纠错。Page27传输差错差错就是在数据传输过程中，接收端接收到的数据与发送端发送的数据出现不一致的现象。网络通信过程中，差错是不可避免的，为了保证通信质量，减少差错，系统必须具有差错控制及差错检测机制。Page28差错控制方法自动重传请求（ARQ）接收端发现接收的数据帧出现差错时，以某种方式通知发送端重传该数据帧，直到收到正确的数据帧为止，这是一种后向纠错方法。前向纠错（FEC）接收端不但能发现接收的数据帧中的差错，而且能确定二进制码中发生错误的位置，从而进行纠正，这是一种自动纠错方式，也称为前向纠错。Page29检错码差错检验编码都是采用冗余编码技术，核心思想是：发送端：有效数据（信息位）在被发送前，按照某种关系附加上一定的冗余位（冗余位与数据相关），构成一个符合某一规则的码字后再发送。接收端：收到码字后，判断是否仍符合原规则，若不符，则可判定传输过程出错。

Page30差错控制技术：发现差错如何处理？前向纠错自动重发请求如果发送的数据丢失，那么接收端是不可能进行确认的，怎么办呢？差错编码技术：如何发现差错？检错码（奇偶校验码、CRC）纠错码（海明码）由接收方来检查并纠正错误不能纠正，接收方反馈。若有错误则重发，否则给肯定应答在发送端引入计时器，进行超时重发为了避免相同的帧收到多次，需要对帧进行编号3.3差错控制31检错码的构造检错码(码字、传输帧)＝信息位＋冗余校验位码字长n=K(信息位位数)＋r(校验位位数)编码效率R＝有效数据位K／码字长n信息字段和校验字段之间的对应关系校验字段越长，编码的检错能力越强，编码/解码越复杂；附加的冗余信息在整个编码中所占的比例越大，传输的有效成分越低，传输的效率下降。检错码一旦形成，整个检错码将作为一个整体被发往线路，通常的发送顺序是信息字段在前，校验字段在后。3.3.1差错检测技术-检错码32奇校验：使码字中“1”的总个数为奇数。偶校验：使码字中“1”的总个数为偶数。奇/偶校验码：最常用的一种检错码，包括：水平奇/偶校验码垂直奇/偶校验码水平垂直奇/偶校验码奇偶校验码包括信息位和校验位需要对信息按行、列分组然后对列进行奇/偶校验方阵校验（在水平校验的基础上，增加垂直校验）33其信息字段以字符为单位，校验字段仅含一个比特称为校验比特或校验位。例如：使用七单位的ASCII码来构造成八单位的检错码时若采用奇/偶校验，校验位的取值应使整个码字包括校验位，1的比特个数为奇数或偶数。水平奇/偶校验34例：信息字段奇校验码偶校验码

01100010110001001100011编码效率：Q/(Q+1)(信息字段占Q个比特)应用：通常在异步传输方式中采用偶校验，同步传输方式中采取奇校验。水平奇/偶校验35垂直奇/偶校验做法：被传输的信息进行分组，并排列为若干行和若干列。组中每行的相同列进行奇/偶校验，最终产生由校验位形成的校验字符（校验行），并附加在信息分组之后传输。举例：4个字符（4行）组成一信息组，求垂直奇/偶校验码36例：4个字符（4行）组成一信息组，其垂直奇/偶校验码为：发往线路顺序（垂直奇校验）

0111001|0010101|0101011|1010101|0101101编码效率：

PQ/P(Q+1)

（假设信息分组占Q行P列）垂直奇/偶校验37水平垂直奇/偶校验水平垂直奇/偶校验码(方阵校验)在水平校验的基础上实施垂直校验。例：4行7列信息组的水平垂直偶校验码为：38水平垂直奇/偶校验发往线路顺序(偶校验字符)：

01110010|00101011|01010110|10101010|10100101

第1字符|

第2字符

|第3字符|

第4字符

|垂直偶校验字符

编码效率：

PQ/(P+1)(Q+1)

（假设被传信息分组占Q行P列）

水平偶校验位393.3.1差错检测技术

-循环冗余码CRC循环冗余码（CyclicRedundancyCheck，CRC）计算机和数据通信中使用最广泛的检错码，漏检率低，可用简单的电路实现。CRC编码的一般操作给定一个k比特的帧或报文，发送方生成n比特的序列（也称为帧检验序列FCS，FrameCheckSequence），形成（k+n）的码字，该码字能被某个事先确定的数整除。接收方用相同的数去除收到的帧，如果无余数，则认为数据帧无差错40CRC也称多项式编码任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。多项式表示：即将k比特的数据用k项多项式表示，它的各项为Xk-1…X0，它的系数为数据中对应位的0或1。例如：代码1010111对应的多项式为x6+x4+x2+x+1多项式为x5+x3+x2+x+1对应的代码10111141冗余码的计算假设待传送的数据M=1010001101（共kbit）。我们在M的后面再添加供差错检测用的nbit冗余码一起发送。计算方法用二进制的模2运算进行

2n

乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R，余数R比除数P少1个比特。核心问题：P如何选定？P若选定，则n就确定了。生成多项式42二进制模2运算模2运算用模2运算进行加法时不进位。减法和加法一样，按加法规则进行运算。举例1111＋1010＝？答案为010143冗余码计算举例设M=1010001101，P=110101，n=5，模2运算的结果2nM除以P得出：商Q=1101010110余数R=01110将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或2nM+R。44循环冗余检验的原理说明45生成多项式P发送方和接收方有一事先约定的生成多项式P例如上例中的P＝110101，即P＝X5+X4+X2+1（P为5阶多项式）；生成多项式的最高位和最低位都必须为1；发送方用它生成冗余位；接收方用它判断是否有错；不同的P有不同的编码电路，用简单的移位寄存器电路硬件实现；发送方通过编码电路产生冗余位，接收方用相似电路检测错误；若P为r阶，将产生r位冗余位；发送方用P生成RP的用途实现有（r+1）位比特46发送方用P生成冗余位P(X)生成多项式M(X)信息多项式R(X)冗余多项式T(X)传输帧多项式发送方用P(X)产生冗余位2n•M(x)/P(x)产生冗余多项式R(x)附加到M(x)后形成T(x)变成带校验位的传输帧多项式47接收方用P进行校验T(X)/P(X)≠0(除不尽)，则有错（1）=0(除尽)，则无错或漏检（2）有错分析：只要得出的余数R不为0，就表示检测到了差错。即用收到的比特流(2nM+R)除以P，看得出的余数是否为0。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。48接收方用P进行校验（漏检）漏检分析收到：T(X)+E(X)；其中E(X)为出错多项式漏检,即:[T(X)+E(X)]/P(X)=0∵T(X)/P(X)=0（T(X)为正确的部分）∴E(X)/P(X)=0即若P(X)是E(X)的因子,将可能漏检.选取合适的P(x),使P(x)不成为E(X)的因子,则可避免漏检.49CRC漏检CRC不能保证检测出所有的传输错误，但是只要选择位数足够的P，可以使得差错的概率足够小。例如：CRC-16和CRC-CCITT可以检测出所有1、2、奇数个、突发长度小于等于16比特错。17比特突发错的99.997%，18比特或更长比特突发错的99.998%。50P的确定方法P为生成多项式，已有的国际标准。CRC-12=X12+X11+X3+X2+X+1CRC-16=X16+X15+X2+1CRC-CCITT=X16+X12+X5+1HDLC和X.25采用CRC32= X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1CSMA/CDLAN采用

51CRC算法思路已知：信息多项式M(X)，生成多项式P(X)求：传送的信息序列多项式与二进制代码的对应关系求出余数根据P(X)得到n二进制除法求某个比特出错时，接收方能否检验出来用接收到的序列/生成多项式，看余数是否为0523.3.2差错纠正技术-海明码码距（海明距离HammingDistance）一个编码系统中任意两个合法编码（码字）之间不同的二进位（bit）数叫这两个码字的码距。例如，10001001与10110001它们的海明距离为3而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。53如果要检测出d个比特的错，则编码集的海明距离至少为d+1。 例如：数据后加奇偶校验位，编码后的海明距离为2，能检测1比特错。如果要纠正d个比特的错，则编码集的海明距离至少应为2d+1。 例如有4个有效码字：它们是000000，000111，111000，111111，海明距离为3，能纠正1比特错两个结论54海明码的基本思想海明码是R.Hamming在1959年提出的，基本思想是：在k比特信息后附加r比特冗余信息（校验比特），构成n=k+r比特的码字，其中每个校验比特和某几个特定的信息比特构成偶校验关系。接收端对这r个奇偶校验关系进行校验，即将每个校验比特和与它关联的信息比特进行相加（异或），相加的结果为校正因子。如果没有错，则r个校正因子都为0；若校正因子不全为0，根据校正因子的取值，确定错误发生的位置。55海明码：主要介绍内容主要介绍单比特纠错海明码纠正单比特错误发送方冗余位产生与接收方纠错过程56发送方冗余位计算A、根据信息位长度(如每帧K位)，计算出所需冗余位位数r：若需纠正一位错，需满足：2r≥K+r+1原理：求海明码时的一项基本考虑是确定所需最少的校验位数r。考虑长度为K位的信息，若附加了r个校验位，则所发送的总长度为K+r。在接收端中要进行r个奇偶检查，每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个r位的二进制数，它可以确定最多2r种不同状态。这些状态中必有一个其所有奇偶测试都是真的，它便是判定信息正确的条件。于是剩下的（2r-1）种状态，可以用来判定误码的位置。则导出下一关系：2r-1≥K+r例如：如果K＝4，则r=3，则n=K+r=757某公司笔试题实验室里有1000个一模一样的瓶子，但是其中的一瓶有毒。可以用实验室的小白鼠来测试哪一瓶是毒药。如果小白鼠喝掉毒药的话，会在一个星期的时候死去，其他瓶子里的药水没有任何副作用。请问最少用多少只小白鼠可以在一个星期以内查出哪瓶是毒药？

a.9b.10c.32d.999e.以上都不对请给出正确答案，并解释原因。58海明码计算B、确定校验比特和信息比特的位置理论上校验比特可在任何位置，但习惯都是将校验比特放在1、2、4、8、16…位置上。通常是将2k位置上，放rk(K>=0)，其余位置放Ii(K>=1)。例如7比特的海明码的构造为：59海明码的计算将每个信息比特的位置写成2的次幂之和的形式有：I4：7＝22＋21＋20（说明I4参与R2、R1和R0的生成）I3：6＝22＋21（说明I3参与R2、R1的生成）I2：5＝22＋20（说明I2参与R2、和R0的生成）I1：3＝21＋20（说明I1参与R1和R0的生成）恰好是校验位所在位置目的：计算每一个信息位与哪些校验位有关联60海明码计算从另一个方面说：R2参与校验I4、I3、I2，即R2和I4、I3、I2构成偶校验关系R1参与校验I4、I3、I1，即R1和I4、I3、I1构成偶校验关系同理R0和信息比特I4、I2、I1构成偶校验这样可以写成如下比特计算公式（XOR运算）：R2＝I4⊕I3⊕I2R1＝I4⊕I3⊕I1R0＝I4⊕I2⊕I1例如：一段信息1000，按以上校验比特的生成方法，则R2=1，R1=1，R0=1.那么发送码字为100101161接收方验证接收端利用相应的偶关系进行验证：S2＝R2

⊕I4

⊕I3

⊕I2S1＝R1

⊕I4

⊕I3

⊕I1S0＝R0

⊕I4

⊕I2

⊕I1这里S2、S1、S0为校正因子，若校正因子全0,无错；校正因子不全为0，有错，错误位置为S＝S2S1S0处，将该比特取反。例如：若S＝101＝5，则将位置5的比特取反，最后去掉校验比特即可得到正确的信息。62海明码计算小结单比特纠错海明码的编码方法如下：校验位R3、R2、R1、R0的计算如下：R3=D6⊕D5⊕D4R2=D3⊕D2⊕D1R1=D6⊕D5⊕D3⊕D2⊕D0R0=D6⊕D4⊕D3⊕D1⊕D0校正因子S3、S2、S1、S0的计算如下：S3=R3⊕D6⊕D5⊕D4S2=R2⊕D3⊕D2⊕D1S1=R1⊕D6⊕D5⊕D3⊕D2⊕D0S0=R0⊕D6⊕D4⊕D3⊕D1⊕D0S3S2S1S0的值即指出差错的位置1、确定校验位和信息位的位置2、确定每一个校验位与哪些信息位形成偶校验关系3、计算校正因子4、指出出错位置63前向纠错（FEC，ForwardErrorCorrect）即发送方发送能使接收方检错并纠错的冗余位，纠错任务由接收方完成；常采用海明码。主要应用于没有反向信道或反向传输时间很长的场合缺点：为纠错附加的冗余码较多，传输效率低优点：实时性好。差错控制技术64自动重发请求（ARQ–AutomaticRepeatreQuest）即发送方发送能使接收方检错的冗余位，若无差错，则接收方回送一个肯定应答(ACK)；若有差错，则接收方回送一个否定应答(NAK)，要求发送方重发。缺点：信息传递连贯性差优点：接收端设备简单，只要请求重发，无需纠正错误。差错控制技术65差错编码差错编码：数据块中插入冗余信息的过程。思想：判断一个数据块中是否存在传输错误，发送端必须在数据块中插入一些冗余信息，使得数据块中的各个比特建立某种形式的关联，接收端通过验证这种关联关系来判断是否有传输错误。差错编码策略检错码：能检测出错误，但不能纠正错误，如CRC纠错码：能知道错误，且知道错误的位置，如海明码差错编码技术663.4流量控制 网络输入增大，输出减小称为拥塞。输出为0称为死锁。 流量控制的作用就是防止拥塞状态的出现、避免死锁、合理分配网络资源。

为了实现流量控制，网络中间结点和接收站要设置缓冲区。把数据分帧可以减少重传的数据量1．停止等待协议（StopandWait）图4.4停止等待协议前提为传输没有错误。发送数据的流量由接收方控制。链路的帧计数长度越小，链路的利用率越高，反之则低，不宜使用停等协议。2．滑动窗口协议 采用滑动窗口协议则可以无需等待应答而允许连续发送多个帧，大大提高了链路利用率。帧编号即为窗口，发送方的叫发送窗口，表示可以连续发送多少帧。接收方的叫接收窗口。只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于1时，就是停止等待协议。滑动窗口的重要特性发送窗口的最大值

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

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

显然WT内不可能有重复编号的帧，所以WT≤2n。设WT=2n；注意以下情况：发送窗口：只有当收到对一个帧的确认，才会向前滑动一个帧的位置；接收窗口：只有收到一个序号正确的帧，才会向前滑动一个帧的位置，且同时向发送端发送对该帧的确认。显然只有接收窗口向前滑动时，发送端口才有可能向前滑动。发送端若没有收到该确认，发送窗口就不能滑动。发送窗口的最大值

取n=3。考虑当接收窗口位于0时，发送窗口的两个极端状态。状态1：全部确认帧收到发送窗口：0123456701234567

接收窗口：0123456701234567

状态2：全部确认帧都没收到发送窗口：0123456701234567

接收窗口：0123456701234567

可见在状态2下，接收过程前移窗口后有效序列号的新范围和发送窗口的旧范围之间有重叠，致使接收端无法区分是重复帧还是新帧。为使旧发送窗口和新接收窗口之间序列号不发生重叠，所以WT≤2n-1。信道利用率与最佳帧长

由于每个数据帧都必须包括一定的控制信息(如帧的序号、地址、同步信息以及其他的一些控制信息)，所以即使连续不停地发送数据帧，信道利用率(即扣除全部的控制信息后的数据率与信道容量之比)也不可能达到100%。当出现差错时(这是不可避免的)，数据帧的不断重传将进一步使信道利用率降低。信道利用率与最佳帧长

若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。2．后退N帧ARQ协议图4.7后退N帧与选择性

3．选择性ARQ协议后退N帧ARQ协议的接收窗口为1，选择性ARQ协议的接收窗口大于1，允许不按顺序接收。只选择性重发错误帧和丢失帧选择性重传ARQ协议

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

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

WR

2n/23.5链路管理

链路管理功能主要用于面向连接的服务。数据链路层连接的建立、维持、和释放，就称作链路管理。典型的链路管理协议有高级数据链路控制协议HDLC、点对点链路控制协议PPP、介质访问控制协议MAC，以及避免冲突的多路访问MACA协议等。

高级数据链路控制规程（HDLC）HDLC是由ISO制定的面向位的数据链路协议HDLC主要功能目标保证发送的数据流具有透明性确定发送帧的格式及帧内段的含义实现链路上站之间的协调,保证有序交换HDLC定义了：3种不同的站类型：主站、次站和复合站2种链路结构：平衡型结构和非平衡型结构3种数据传输方式：正常响应(NRM)、异步响应(ARM)和异步平衡响应方式(ABM)Page803.5.1面向比特的链路层协议HDLC

由于对控制方法影响较大的是传输信息的基本单位，因此链路控制规程有"面向字符的控制规程"和"面向比特的控制规程"。面向字符的控制规程把数据和控制信息都看作是字符，面向比特的控制规程把数据及控制信息都看作是位的组合。

面向字符和面向位的链路控制协议图4.10IBM公司的二进制同步通信控制（BSC）协议HDLC协议的基本概念1．3种类型的站：主站，次站，复合站。主站负责控制整个数据链路图4.11三种类型的站和两种结构2．两种链路结构：平衡型和非平衡型下图为主站和次站叠合组成图4.12对称结构 3．3种操作模式

（1）NRM：正常响应 点对多点 （2）ARM：异步响应 对称结构和点对点链路 （3）ABM：异步平衡复合站结构HDLC协议的帧格式图4.13HDLC的帧格式1．标志字段（F）

帧的开始和结束2．地址字段（A） 地址字段用来表示命令帧或响应帧的地址。命令帧的地址为对方地址；响应帧的地址为自己的地址3．信息字段（I） 信息字段用于传输用户数据。长度有限制4．帧校验字段（FCS） 帧校验字段（FCS）共16位，采用循环冗余校验方法，用来检查所接收的信息是否在传输过程中发生了差错。5．控制字段（C） 控制字段（C）共占8位，可构成各种命令和响应用来完成传输控制功能。HDLC协议的主要内容 1．信息帧

发送数据,控制字段的1为”0”。 2．监控帧

控制字段的1,2为”10”,监控数据链路传送应答信息 3．无编号帧

控制字段的1,2为”11”,传送命令和其他控制信息，控制链路的建立，拆除并处理系统错误等。与用户无关，并优先传送表4.1无编号帧命令编码表续表（1）SARM/SABM帧（2）DISC（拆除链路）帧（3）UA（无序号确认响应）帧（4）FRMR（帧拒绝响应）帧/CMDR（命令拒绝响应）帧4．链路操作过程（1）链路建立（2）数据传输（3）链路拆除图4.14无编号帧使用举例3.5.2因特网中的点对点协议（PPP）图4.15用户拨号上网示意图点到点协议PPPPPP协议是IETF于1992年制定的。PPP是使用串行线路通信的面向字节协议PPP可以在同步和异步线路上使用由于流量控制、差错控制已在TCP中实现，因此PPP没有纠错功能，不进行流量控制，不需要帧序号，不支持多点链路，使用全双工方式传输数据。Page961.PPP协议应满足的条件（1）简单：不需要复杂的流量控制、差错控制等功能，也不需要序号，只需要实现最基本的功能。（2）封装成帧：规定特殊的字符作为帧的开始和结束标志，同时保证能正确地区分数据与帧的定界标志，保证数据的透明传输。（3）支持多种网络层协议：能支持多种网络层协议。（4）支持多种类型链路：能在多种链路上运行，如同步或异步、高速或低速、电或光等链路。Page971.PPP协议应满足的条件（5）差错检测：可进行差错检测，丢弃错帧。（6）检测连接状态：能及时自动检测链路工作状态。（7）可设置最大传送单元：可针对不同的链路设置最大传送单元MTU的值（帧中数据部分的长度）。（8）支持网络层地址协商：支持网络层通过协商配置并识别网络地址。（9）支持数据压缩协商：提供协商使用数据压缩算法的方法。Page982．PPP协议组成PPP协议由3部分组成，即HDLC封装、链路控制协议和网络控制协议。（1）一种成帧方法定义了将IP数据报封装到串行链路的方法，明确地定界一个帧的结束和下一个帧的开始，其帧格式允许进行错误检测。PPP既支持异步链路（无奇偶检验的8位数据），也支持面向位串的同步链路。IP数据报是PPP中信息部分，其长度受最大传送单元MTU的限制。MTU的默认值是1500字节。Page992．PPP协议组成（2）一个链路控制协议（LCP）链路控制协议（LinkControlProtocol，LCP）负责线路建立、配置、测试和选项协商，并在它们不再被需要时，稳妥地把它们释放。（3）一套网络控制协议（NCP）网络控制协议（NetworkControlProtocol，NCP）可支持不同的网络层协议，如IP、Appletalk等，对于所支持的每一个网络层协议都有一个不同的网络控制协议，用来建立和配置不同的网络层协议。提供了协商网络层选项的方式。Page100图4.16PPP的工作过程3．PPP协议的帧格式PPP协议的帧格式与HDLC帧格式相似（1）标志域：标志为0x7E，即“01111110”，与HDLC相同。（2）地址域：固定为0xFF，即“11111111”，表示所有站都可以接收这个帧。因为PPP只用于点对点链路，地址域实际上不起作用。Page102PPP帧格式说明（3）控制域置为0x03，即“00000011”，表示PPP帧不使用编号。缺省值：PPP不提供使用序列号和确认应答的可靠传输。在有噪音的环境中，如无线网络中，通过LCP确定可以使用编号方式的可靠传输。Page103PPP帧格式说明（4）协议域说明信息域中承载分组的种类。PPP为LCP、NCP、AppleTalk和其他协议定义了相应的代码。缺省长度是2字节，通过LCP协商变成1个字节。常用的有：①0x0021：IP数据报。②0x002b：IPX数据。③0x0029：AppleTalk数据。④0xc021：PPP链路控制数据（LCP）。⑤0x8021：IP控制协议。⑥0x802b：IPX控制协议。⑦0x8029：AppleTalk控制协议。Page104PPP帧格式说明（5）信息域信息域是网络层传送过来分组，长度可变，可以协商一个最大值。缺省1500字节。①字节填充法当PPP使用异步传输时（面向字符），使用字节填充法来（0x7D）消除信息中可能出现的0x7E字符。②位填充法PPP协议用在SONET/SDH链路时，使用同步传输而不是异步传输。Page105PPP帧格式说明（6）检验和检验和字段通常是2个字节，但也可以通过协商使用4个字节的检验和。PPP协议对收到的每一个帧，使用硬件进行CRC检验。若发现有差错，则丢弃该帧。因此，PPP协议可保证链路级无差错接收。Page1064．PPP协议的工作过程当用户拨号接入ISP时，路由器对拨号做出确认，并建立一条物理连接。此时，计算机向路由器发送一系列的LCP帧（封装成多个PPP帧）。这些帧及其响应帧选择了将要使用的PPP协议参数。接着进行网络层配置，NCP给新接入的计算机分配一个临时的IP地址。这样，计算机就成为互联网上的一个主机了。当用户通信完毕时，NCP释放网络层连接，收回原来分配出去的IP地址，LCP释放数据链路层连接，最后，释放物理层的连接。Page107Page108

数据链路控制规程分类

面向字符型

在这类规程中，用字符编码集中的几个特定字符来控制链路的操作，监视链路的工作状态，例如，采用国际5号码中的SOH、STX作为帧的开始，ETX、ETB作为的结束，ENQ、EOT、ACK、NAK等字符控制链路操作。面向比特型

在这类规程中，采用特定的二进制序列01111110作为帧的开始和结束，以一定的比特组合所表示的命令和响应实现链路的监控功能，命令和响应可以和信息一起传送。3.5面向比特的链路层协议HDLC

面向字符型数据链路层协议的缺点：报文格式不一样；传输透明性不好；等待发送方式，传输效率低。面向比特型协议的设计目标：以比特作为传输控制信息的基本单元；数据帧与控制帧格式相同；传输透明性好；连续发送，传输效率高。HDLC的基本工作原理（基本特征）三种类型的站：主站：负责链路的操作，主站发出的帧称为命令。次站：在主站的控制下进行操作。组合站：组合了主站和次站的特性，既可发命令，也可发响应。两种链路组合:

非平衡组合：1个主站+1~多个次站。平衡组合：两个组合站组成。HDLC的基本工作原理（基本特征）操作方式：正常响应方式(NRM)：适用于不平衡链路结构，即用于点-点和点-多点的链路结构中。由主站控制整个链路的操作，负责链路的初始化、数据流控制和链路复位等。从站只有在收到主站的明确允许后，才能发出响应。异步响应方式(ARM)：也适用于不平衡链路结构。从站可以不必得到主站的允许就可以开始数据传输。异步平衡方式(ABM)：适用于平衡链路结构。链路两端的复合站具有同等的能力，不管哪个复合站均可在任意时间发送命令帧，并且不需要收到对方复合站发出的命令帧就可以发送响应帧。HDLC的基本配置方式HDLC的帧结构标志字段F(Flag)为6个连续1加上两边各一个0共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。最多可以表示256个站的地址。地址字段为“11111111”时，定义为全站地址，即通知所有的接收站接收有关的命令帧并按其动作；全“0”比特为无站地址，用于测试数据链路的状态。因此有效地址共有254个。比特888可变168信息

Info标志

F标志

F地址

A控制

C帧检验序列

FCS透明传输区间FCS检验区间其它字段

帧检验序列FCS字段共16bit。所检验的范围是从地址字段的第一个比特起，到信息字段的最末一个比特为止。控制字段C共8bit，是最复杂的字段。HDLC的许多重要功能都靠控制字段来实现。比特888可变168信息

Info标志

F标志

F地址

A控制

C帧检验序列

FCS透明传输区间FCS检验区间控制字段

控制字段C有8bit，HDLC的许多重要功能要由控制字段来实现。根据其最前面二个比特位，可将HDLC帧分为三种：即信息帧I、监督帧S和无编号帧U。比特888可变168信息

Info标志

F标志

F地址

A控制

C帧检验序列

FCS01101SMP/FP/FN（S）P/FN（R）N（R）M信息帧I监督帧S无编号帧U12345678信息帧：若控制字段的第1比特为0，则该帧为数据帧，用于传送数据。比特2-4为发送序号N(S)，而比特6-8为接收序号N(R)。特别强调指出：N(R)带有确认的意思，它表示序号为N(R)-1以及在这以前的各帧都已经正确无误地收妥了。

控制字段（续1）01101SMP/FP/FN（S）P/FN（R）N（R）M信息帧I监督帧S无编号帧U12345678监督帧：用于监视和控制数据链路，完成信息帧的接收确认、重发请求、暂停发送请求等功能。若控制字段的第1-2比特为10，则对应的帧即为监督帧S。监督帧共有四种，取决于第3-4比特的取值。

监控帧的名称和功能

控制字段（续2）第3-4比特帧名功能确认，且准备接受下一帧，已收妥N(R)以前的各帧确认，暂停接收下一帧，N(R)含义同上否认，否认N(R)起的各帧，但N(R)以前的帧已收妥否认，只否认序号为N(R)的帧RR接收准备好RNR接收未准备好REJ拒绝接收SREJ选择拒绝接收00100111无编号帧：用于数据链路的控制。若控制字段的第1-2比特都是1时，这个帧就是无编号帧U，无编号帧本身不带编号，而是用5bit来表示不同功能的无编号帧。可以在任何需要的时刻发出，而不影响带编号的信息帧的交换顺序。如：B3B4B6B7B8=00001，则其功能为置正常响应模式。控制字段（续3）01101SMP/FP/FN（S）P/FN（R）N（R）M信息帧I监督帧S无编号帧U12345678无编号帧的名称和代码名称B3B4B6B7B8记忆符置正常响应模式00001SNRM置异步响应模式/断开方式11000SARM/DM置异步平衡模式11100SABM置扩充正常响应模式11011SNRME置扩充异步响应模式11010SARME置扩充异步平衡模式11110SABME断链/请求断链00010DISC/RD置初始化/请求初始化方式10000SIM/RIM无编号探询00100UP无编号信息00000UI交换识别11101XID复位11001RESET帧拒绝10001FRMR无编号确认00110UAP/F位的意义（询问/终止）

在正常响应方式中，从站不能主动向主站发送信息，从站只有收到主站发出的P比特为1（对从站的查询）的命令帧以后才能发送响应帧。若从站有数据发送，则在最后一个数据帧中将F比特置1；若无数据发送，则应在回答的S帧中将F比特置1。在异步响应或异步平衡方式中，任何一个站都可以在主动发送的S帧和I帧中将P比特置1。对方站收到P=1的帧后，应尽早地回答本站的状态并将F比特置1。P/F位的使用方法图中主站A和从站B、C连成多点链路，传送帧的一些主要参数按照“地址，帧名和序号，P/F”的先后顺序标注。这里的地址是指地址字段中应填入的站地址；帧名是指帧的名称，如RR、I；序号是指监控帧中的N(R)或信息帧中的N(S)和N(R)，如RR4、I31（第1个数字是N(S)，第2个数字是N(R)）。P/F是在其为1时才写上P或F，表明此时控制字段的第5比特为1。P/F位的使用方法主站A先询问B站：“B站，若有信息，请立刻发送”。这时A站发送的帧是RR监控帧，并将N(R)置0，表示期望收到对方的0号帧。因此在图中将这样的帧记为“B,RR0,P”。对主站的这一命令，B站响应以连续4个信息帧，其序号N(S)从0到3。最后在第4个信息帧中将F置1，表示“我要发送的信息已发完”。这个帧记为“B,I30,F”。A站在收到B站发来的4个信息帧后，发回确认帧RR4（这时N(R)=4）。我们注意到这时P/F比特并未置1，所以B站收到RR4后不必应答。接下去A站轮询C站，P=1，虽然这时C站没有数据发送，但也必须立即应答。C站应答也是RR帧，表示目前没有信息帧发送，F=1表明这是回答对方命令的一个响应。P/F位的使用方法有了P/F比特，使HDLC规程使用起来更加灵活。在两个复合站全双工通信时，任何一方都可随时使P=1，这时对方就要立即回答RR帧，并置F=1，这样就可以收到对方的确认了。如果不使用P/F比特，则收方不一定马上发出确认帧，比如收方可以在发送自己的信息帧时，利用N(R)把确认信息发出。P/F位的使用方法3.5.2因特网的点对点协议PPPPPP（Point-to-PointProtocol点到点协议）是为在同等单元之间传输数据包这样的简单链路设计的链路层协议。这种链路提供全双工操作，并按照顺序传递数据包。设计目的主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机、网桥和路由器之间简单连接的一种解决方案。

PPP协议的工作原理

现在使用得最多的数据链路层协议是点对点协议

PPP。用户使用拨号电话线接入因特网时，一般都是使用PPP协议。路由器调制解调器调制解调器因特网服务提供者(ISP)用户家庭拨号电话线

使用TCP/IP的

PPP连接使用TCP/IP的客户进程路由选择进程至因特网…PC机PPP的特性PPP协议是目前使用得最广泛的广域网协议，这是因为它具有以下特性：能够控制数据链路的建立；能够对IP地址进行分配和使用；允许同时采用多种网络层协议；能够配置和测试数据链路；能够进行错误检测；有协商选项，能够对网络层的地址和数据压缩等进行协商。PPP协议组成一个将IP数据报封装到串行链路的方法。链路控制协议LCP(LinkControlProtocol)：LCP负责创建，维护或终止一次物理连接。可以使用多种物理层服务。认证协议，最常用的包括口令验证协议PAP和挑战握手验证协议CHAP。网络控制协议NCP(NetworkControlProtocol)：负责解决物理连接上运行什么网络协议，以及解决上层网络协议发生的问题。可以支持多种网络层协议。PPP协议的帧格式PPP的帧格式和HDLC的相似。标志字段F仍为0x7E（符号“0x”表示后面的字符是用十六进制表示。十六进制的7E的二进制表示是01111110）。地址字段A只置为0xFF。地址字段实际上并不起作用，PPP不分配个人地址。控制字段C通常置为0x03。要求用户数据传输采用无序号帧，不提供使用序号和确认的可靠传输。PPP是面向字节的，所有的PPP帧的长度都是整数字节。PPP协