计算机网络(四)数据链路层-基本原理

计算机网络（四）

——关于数据链路层（1.基本原理）信息科学与技术学院

第一页，共一百二十八页。学习目标!了解：数据链路层的设计问题掌握：数据链路层差错控制方法、循环冗余码编码原理掌握：数据链路层的功能掌握：基本数据链路协议掌握：停等协议、滑动窗口协议的工作原理掌握：面向比特型数据链路层协议实例—HDLC。了解：Internet中的数据链路层协议。第二页，共一百二十八页。前言：数据链路层的设计问题为什么需要数据链路层？

物理层未解决的问题：位流传输过程中不可避免会出现差错（电磁干扰，线路问题）数据收发之间的速率匹配问题

（不同设备处理速度不同）最主要的作用是通过一些数据链路层协议(即链路控制规程),在不太可靠的物理链路上实现可靠的数据传输.第三页，共一百二十八页。前言：数据链路层的设计问题

1.向网络层提供的服务主机A主机BALTLNLDLPLALTLNLDLPL帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧无确认的无连接服务有确认的无连接服务面向连接的服务第四页，共一百二十八页。前言：数据链路层的设计问题

2.成帧涉及的问题协议数据单元将上层(网络层)交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧；考虑接收双方的同步问题（即定界）；

计算帧的校验和并放入帧中一起传送给接收方；帧：在数据链路上交换数据的单位。标志字段指明帧的开始和结束地址字段控制字段正文字段校验字段第五页，共一百二十八页。前言：数据链路层的设计问题

2.成帧字符计数法字符填充的首尾定界法位填充的首尾定界法5123456789801234568789012351234767898012345687890123计数值传输出错时导致收发双方不同步.同步字符法标志法填充技术第六页，共一百二十八页。前言：数据链路层的设计问题

2.成帧物理层编码违例法综合法“0”“1”违例或用计数值确定帧尾检查帧定界符是否出现在应该出现的地方计算校验和第七页，共一百二十八页。前言：数据链路层的设计问题

3.流量控制流量控制流量控制的特点网络层实体控制从数据链路层接收数据的速率，据此，数据链路层要控制从同等实体接收PDU的速率。限制发送方发送速度的一种机制。使发送速率不能超过接收方能处理的速率。流量控制必须是动态的必须有某种反馈机制流量速度不仅与发方速度相关而且与网络的当前拥挤程度有关使发方了解收方的当前处理能力第八页，共一百二十八页。前言：数据链路层的设计问题

4.差错控制顺序到达 指保证所有的帧最终都按正确的发送次序到达目的。检错和纠错检出传输中出现的差错；可能的话确定出错位置从而纠正错误。确认方式计时器法计时器值的设定要保证一帧到达对方并作处理后，相应的确认帧返回。ACK肯定确认NAK否定确认计时结合序号才能保证每一帧的正确次序。第九页，共一百二十八页。前言：数据链路层的设计问题

5.数据链路层协议的作用数据链路协议23数据链路进程路由选择进程路由器A帧分组/包2322232路由器B传输线2322223DL协议的作用就是使不可靠的通信线路变得一定程度的好。第十页，共一百二十八页。物理层:----物理链路----比特流传输----有差错的物理链路数据链路层:----数据链路----帧传输----无差错的数据链路----数据链路层数据服务单元----帧第十一页，共一百二十八页。一、数据链路层概述数据链路层于物理层之上,属于低层。物理层传输的是比特流，单位是比特。数据链路层传输单位是帧，一帧一帧地处理。其工作是从物理层获取比特流，进行封装成帧、并对帧进行如透明传输、差错控制等处理，从而递交给上一层（网络层），同时也对网络层下传的数据进行处理，进而传给物理层。第十二页，共一百二十八页。数据链路层传送的是帧IP数据报1010……0110帧取出数据链路层网络层链路结点A结点B物理层数据链路层结点A结点B帧(a)(b)发送帧接收链路IP数据报1010……0110帧装入第十三页，共一百二十八页。一、数据链路层概述

分组与帧的关系图示Relationshipbetweenpacketsandframes第十四页，共一百二十八页。一、数据链路层概述

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

H1主机

H2路由器

R1路由器

R2路由器

R3电话网局域网主机

H1

向

H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动第十五页，共一百二十八页。一、数据链路层概述

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

H1主机

H2路由器

R1路由器

R2路由器

R3电话网局域网主机

H1

向

H2

发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动第十六页，共一百二十八页。一、数据链路层概述

数据链路层协议在路由器中的位置Placementofthedatalinkprotocol第十七页，共一百二十八页。一、数据链路层概述

数据链路层协议在路由器中的位置数据链路协议23数据链路进程路由选择进程路由器A帧分组/包2322232路由器B传输线2322223DL协议的作用就是使不可靠的通信线路变得一定程度的好。第十八页，共一百二十八页。

一、数据链路层概述

1.常用概念链路(link)：是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(datalink)：除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。结点（node）：网络中的主机（host）和路由器（router）称为结点。第十九页，共一百二十八页。

一、数据链路层概述

1.常用概念链路（link）：通信路径上连接相邻结点的通信信道称为链路。数据链路（datalink)：链路+实现通信协议的硬件和软件。数据链路层协议：定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。端到端（endtoend）与点到点（pointtopoint）：从源结点（sourcenode）到目的结点（destinationnode）的通信称为端到端通信，通信路径（path）可能由多个链路组成。在相邻结点间的一条链路上的通信称为点到点通信。数据链路控制规程：为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。第二十页，共一百二十八页。虚拟数据通路，实际数据通路

一、数据链路层概述

1.常用概念第二十一页，共一百二十八页。

一、数据链路层概述

1.常用概念数据链路层像个数字管道常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。结点结点帧帧第二十二页，共一百二十八页。

一、数据链路层概述

2.数据链路层使用的信道类型数据链路层使用的信道主要有以下两种类型：点对点信道:这种信道使用一对一的点对点通信方式。 （例如PPP、SLIP）广播信道:这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送。 （例如以太网）第二十三页，共一百二十八页。

一、数据链路层概述

3.数据链路层协议基本功能链路管理数据在数据链路上的正常传输（建立、维护和释放）。帧同步：数据传输的单位为帧，定界与同步。也处理透明性问题。流量控制与顺序控制。差错控制：前向纠错、差错检测，检错重发。将数据和控制信息分开。透明传输。寻址。第二十四页，共一百二十八页。

二、差错检测与校正

1.基本概念什么是差错？在通信中接收端收到的二进制数位（码元）和发送端实际发送的数据不一致。差错检测与校正：把差错控制在允许的范围内。差错控制的主要内容：差错编码、反馈重传、超时重传、重复帧丢弃、定时器管理等。第二十五页，共一百二十八页。

二、差错检测与校正

1.基本概念误码率：衡量物理信道的质量.差错控制编码：信息位(k)＋冗余位(r)检错码：自动发现差错纠错码：不仅能发现差错而且能够自动纠正编码效率R：码字中信息位所占的比例R=k/(k+r)漏检率：信息位出错但是接收者无法了解到的概率第二十六页，共一百二十八页。

二、差错检测与校正

2.差错与校正概念出错的类型单个错：由随机的信道热噪声引起，一次只影响1位；突发错：由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。编码的类型检错码：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来使用以便进行差错恢复；纠错码：不权能够检测到数据传输发生了错误，而且能够自行纠正错误。第二十七页，共一百二十八页。

二、差错检测与校正

2.差错与校正概念码字（codeword）：由m比特的数据（消息）加上r比特的冗余（校验位）构成；有效编码集：由2m个有效码字组成；检错：当收到的码字为无效码字时检测出错误；海明距离（HammingDistance）：两个码字的对应位上取值不同的位数；纠错：将收到的无效码字纠正到距其最近的有效码字；检错码与纠错码的能力都是有限的。第二十八页，共一百二十八页。

二、差错检测与校正

2.差错与校正概念编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。检错能力：为检测出d比特错误，编码集的海明距离至少应为d+1；奇偶校验是能够检测出1比特错误的检错码。纠错能力：为纠正d比特错误，编码集的海明距离至少应为2d+1；海明码是能够纠正1比特错误的纠错码。第二十九页，共一百二十八页。

二、差错检测与校正

2.差错控制与校正方法差错控制：ARQ和FECARQ（自动重传请求）AutomaticRequestforRepeat接收方检测错误，通知发送方重传双向信道，发送方缓存发送的数据FEC（前向纠错）ForwardErrorCorrection接收方不仅可以检测错误，而且知道错误的位置，从而改正错误采用纠错码，无需反向信道，无需重发，但编码效率低,纠错设备复杂第三十页，共一百二十八页。

二、差错检测与校正！！！

3.差错检测与校正和流量控制由于系统性能的不同，如硬件能力（包括CPU，存储器等）和软件功能的差异，会导致发送方与接收方处理数据的能力有所不同。流量控制的作用是使发送方所发出的数据流量，使其发送速率不要超过接收方所能接收的速率。流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收方是否能接收到存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协议则将关于帧的确认与流量控制巧妙地结合在了一起。流量控制的主要机制：基于反馈的流量控制（√）基于速率的流量控制第三十一页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（奇偶校验码）奇偶校验码：增加冗余位使 得码字中‘1’的个数为奇数或 者偶数，检错码垂直奇偶校验水平奇偶校验水平垂直奇偶校验垂直奇偶校验：发送的信息块分成定长为p位的若干段（一列）。每段增加一个（奇偶校验）冗余位ri：第三十二页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（垂直奇偶校验）垂直奇偶校验编码效率：能力：检测出每列（段）中所有奇数（1、3…）个错突发错误的漏检率为50%!!在发送和接收的过程中进行编解码水平奇偶校验：降低突发错误的漏检率对各个信息段的相应位横向进行编码第三十三页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（水平奇偶校验）水平奇偶校验编码效率：能力：各段同一位上的奇数个错长度小于等于p的突发差错编码和检测相比垂直校验而言实现要复杂一些第三十四页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（水平垂直奇偶校验）水平垂直奇偶校验编码效率第三十五页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（水平垂直奇偶校验）水平垂直奇偶校验能力检测出：所有3位或3位以下的错误、奇数位错突发长度小于等于p+1的突发差错很大一部分偶数位错：差错分布以致于某一行或者某一列有奇数个差错部分纠错功能：可以纠正1比特错信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处第三十六页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（水平垂直奇偶校验）10001010字符1b1b2b3b4b5b6b7check11001011字符211011010字符310101011字符410001010字符510001010字符611101010字符700100001校验字符水平垂直奇校验的例子第三十七页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（海明码）1.海明码 (1)海明距离及意义 两个码字中不同的位数的个数称为海明距离,简称H距离

10001001

10110001 求H距离的方法主要有:异或运算 海明距离的意义是:假如两个码字具有海明距离d,则需要d个位差错才能将其中一个码字转换成另一个.H=3第三十八页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（海明码）(2)海明码算法 ①将码字数内的位从最左边开始按顺序依次编号,第1位是1号,第2位是2号,……第n位是n号.编号为2的幂的位(1号位,2号位,4号位,8号位等)是校验位,其余的位填入m位数据(2r≧n+1). ②每个校验位的取值应使得包括自己在内的一些位的集合符合规定的奇偶性.(主要用于奇偶性校验)12345678

9101112校验位第三十九页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（海明码）③为了知道编号为K的数据位对哪些检测位有影响,将编号K改写成2的幂的和(如:11=1+2+8,29=1+4+8+16),1个位只由扩展式中所示编号的位检测(编号为11的位,只能由1,2,8检测位检测)④由于在每个校验位的形成表达式中,除自身编号外,其余都是信息位的编号,因此只要信息位是确定的,校验位也可以唯一地确定.第四十页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（海明码）由上图可看出,海明码的信息余量很大,因而编号效率低.例:根据海明编码方法,对ASCII字符Z(二进制编码是1011010),形成11位码字,要求简单地写出编码过程.并说明在传输过程中,有一位错的情况下,如何能够检查出是哪一位是错的?解:m=7,n=11,r=4

编号:1=1,2=2,3=1+2,4=4,5=1+4,6=2+4,7=1+2+4,8=8,9=1+8,10=2+8,11=1+2+8

于是有:(1)(3)+(5)+(7)+(9)+(11)(2)(3)+(6)+(7)+(10)+(11)(4)(5)+(6)+(7)(8)(9)+(10)+(11)被检测位：数据位检测位第四十一页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（海明码）1234567891011

00100111010

编码码字最终的海明码为什么此处是1?1,2,4,8是校验位!其余位是信息位.

(9)(10)(11)(1)(3)(5)(7)(9)(11)1010010100奇数个1偶数个1采用偶检验哦!第四十二页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）纠错码的编码效率较低，差错控制经常采用检错码＋ARQ。循环冗余码CRC（CyclicRedundancyCode）是计算机网络中使用最为广泛的检错码，又称为多项式码。第四十三页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）CRC的工作原理（1）将要发送的二进制数序列看成是只有0和1两个系数的一个多项式。n位的数据序列对应n-1次多项式。如：二进制数序列为“1010001”，7位的数据序列对应6次多项式： K(x)=x6+x4+1选定除式G(x)，被选作除式的多项式称为生成多项式，以下三个多项式已成为国际标准CRC-12：G(x)=x12+x11+x3+x2+x+1CRC-16：G(x)=x16+x15+x2+1CRC-CCITT：G(x)=x16+x12+x5+1CRC-32G（x）=x32+x26+x23+x22+x16+x12+x11+x10+

x8+x7+x5+x4+x2+x+1第四十四页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）CRC的工作原理（2）将K(x)乘以G(x)的最高幂次作为被除式，G(x)作多项式除式XrK(x)=G(x)*商+R(x)（相应系数相除）。除法采用“加法不进位，减法不借位”的规则，即相当于异或操作

R(x)作为冗余码，加在原传送数据后面: T(x)=XrK(x)+R(x)=G(x)*商+R(x)+R(x)=G(x)*商 构成发送序列。 接收方收到后，将接收序列用同样的生成多项式去除T(x)/G(x)。 若余式为零，则表示无差错；否则，说明传输过程中出现了错误。第四十五页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）

CRC的例子（1）

要发送的二进制数序列为“1010001”，7位的数据序列对应6次多项式： K(x)=x6+x4+1 选定的生成多项式为：

G(x)=x4+x2+x+1 （最高次数为4，相当于10111） 被除多项式为： K(x)x4＝x10+x8+x4第四十六页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）CRC的例子（2）多项式除法后得到冗余码为1101，所以相应的数据发送序列为10100011101101000100001011111011111010001111110101011111010101111011111010101111101第四十七页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）R0R1Rr-1信息输入端g1g2gr-1CRC校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。CRC硬件实现第四十八页，共一百二十八页。111101R0R1R3信息输入端R21000101R0R1R2R3输入输出:110100001GG11101001110101100011111011001010101101010100100001000100000111101二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）第四十九页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）CRC的检错能力（1）如果传输过程中出现差错：差错模式E(x)＝发送码字和接收码字的半加，其中1的位置对应变化了信息位的位置。若E(x)能被G(x)整除，则不能检测这样的错误第五十页，共一百二十八页。二、差错检测与校正

4.常用的简单差错控制编码（CRC循环冗余码）CRC的检错能力（2）全部单个错全部离散的二位错全部奇数个错全部长度小于或等于r的突发错（r为生成多项式的最高幂次）以1-（1/2）r-1的概率检出长度为r+1位的突发错以1-2-r的概率检出长度大于r+1位的突发错第五十一页，共一百二十八页。三、关于数据帧数据链路层所传送的不再是原始的比特流，而应具备相应的语法和语义，以达到可靠传输的功能。数据链路层将从网络层接收的分组（Packet)组成帧后传送给物理层，通过物理层传送到对方的数据链路层。帧：数据链路层规定最小的数据传送逻辑单位数据链路层协议要规定帧的类型与格式类型包括控制信息帧与数据信息帧等，格式则规定帧所包含的域）。第五十二页，共一百二十八页。3.1帧的基本组成帧定界（开始与结束）地址字段（用于寻址）帧类型（或长度/控制）字段数据帧校验字段（差错控制）帧的开始地址帧类型或长度数据帧校验帧的结束上图只是帧的一般组成，不同的数据链路层协议所规定的帧格式可能会与其存在微小的区别。第五十三页，共一百二十八页。3.2帧的同步同步就是标识帧的开始与结束常用的帧同步方法：字符计数法带字符填充的首尾界符法带位填充的首尾标志法违例编码法第五十四页，共一百二十八页。字符计数法512345678980123456512347678980123456计数计数计数第1帧5个字符第2帧5个字符第3帧8个字符发送:接收:第1帧正确!第2帧不正确!问题:出错之后,接收方与发送方不同步!无法确定下一帧的开始位置.请求重传也没有用处,因为目的机器不知道应该回跳多少字符开始重传.7出错!

11个字符计数??在帧头中使用一个字段来标明帧内的字符数，通常该字段称为帧长字段。第五十五页，共一百二十八页。首尾界符法每一帧以ASCII字符序列DLESTX开始，以DLEETX结束。DLE为DataLinkEscape的缩写，STX意味着StartofText，ETX代表EndofText。其缺点是成帧完全依赖于8位字符STX,A,B,GOOD,BYE,ETX

A,B,GOOD,BYE

数据组帧第五十六页，共一百二十八页。字符填充在首尾界符法中，由于数据中可能会出现DLESTX或DLEETX，从而干扰帧的正常定界字符填充法可用于解决上述问题。即发送端在数据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。DLE,STX,A,DLE,B,DLE,ETXDLE,STX,A,DLE,DLE,B,DLE,ETX网络层发出的数据经数据链路层填充后的数据第五十七页，共一百二十八页。字节填充图例(a)Aframedelimitedbyflagbytes(b)Fourexamplesofbytesequencesbeforeandafterstuffing.第五十八页，共一百二十八页。首尾标记法每一帧使用一个特殊的位模式“01111110”作为开始和结束标记。该位模式又称为flag位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。…Data…0111111001111110第五十九页，共一百二十八页。位填充在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1”时，则在其后自动插队入一个“0”。该技术简称“逢五1插0”；接收端则忽略5个连续的“1”后面的“0”，简称“逢五1删0”。011011111111111111110010(b)011011111011111011111010010(c)011011111111111111110010填充的位第六十页，共一百二十八页。比特填充图例(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.第六十一页，共一百二十八页。违例编码法采用不可能出现在信息位中的比特编码作为帧的起始边界。在物理层采用特定的比特编码方法时使用曼彻斯特编码中电平的跳变表示1（低->高）和0（高->低）高高和低低电平是违例编码第六十二页，共一百二十八页。四、数据链路层协议

—数据链路通信的简单模型第六十三页，共一百二十八页。完全理想化的数据传输完全理想化的数据传输基于以下两个假定假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发送方以多快的速率发送数据，接收方总来得及收下，并及时上交主机。(接收端向主机交付的数据速率永远不会低于发送端发送数据的速率)第六十四页，共一百二十八页。4.1停等协议停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。具有最简单流量控制的数据链路层协议仍保留假定1，但去掉假定2链路是理想的传输信道，即所传送的任何数据既不会出差错也不会丢失由接收方控制发送方的数据流(计算机网络中流量控制的一个基本方法)。第六十五页，共一百二十八页。停等协议算法在发送结点：（1）从主机取一个数据帧；（2）将数据帧送到数据链路层的发送缓存；（3）将发送缓存中的数据帧发送出去；（4）等待；（5）若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到（2）。在接收结点：（1）等待；（2）若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存；（3）将接收缓存中的数据帧上交主机；（4）向发送结点发一信息，表示数据帧已经上交给主机；（5）转到(1)。第六十六页，共一百二十八页。停等协议两种数据传输比较从主机取数据上交主机DATA1DATA4DATA3DATA2结点A结点B理想信道从主机取数据上交主机DATA1DATA2结点A结点BACKACK具有简单流量控制的数据链路层协议从主机取数据上交主机DATA1DATAnDATA2结点A结点BDATAn+3DATAn+2DATAn+1NAKn+1ACK流水线协议第六十七页，共一百二十八页。实用的停止等待协议前提：去掉两个假定，即传输数据的信道不能保证使所传的数据不产生差错，而且还需对数据的发送端进行流量控制。流量控制方法：等待发送差错控制：发送方数据帧中加入校验码（CRC），由接收方检查；若正确，返回ACK，若出错，返回NAK；发送方根据收到的返回帧，决定发送新帧和重发。帧丢失处理：超时定时器；以序号标识数据帧优点：简单缺点：信道利用率低，信道还远远没有被数据比特填滿第六十八页，共一百二十八页。数据帧在链路上传输的几种情况Data0Data1ACKACKAB时间送主机送主机Data0Data0ACKToutACK丢失AB重传送主机放弃×

(a)正常情况

(b)数据帧出错

(C)数据帧丢失

(d)确认帧丢失Data0Data0NAKACKAB出错重传送主机重传Data0Data0ACK丢失ABTout送主机第六十九页，共一百二十八页。实用停止等待协议的算法在发送结点：(1)从主机取一个数据帧，送交发送缓存。(2)v(S)←0。(发送状态变量v(S)初始化)(3)N(S)←v(S)。(将发送状态变量值写入数据帧中的发送序号N(S))(4)将发送缓存中的数据帧发送出去。(这个数据帧的副本仍保留在发送缓存中)(5)设置超时计时器。(选择适当的超时重传时间tout)(6)等待。(等待以下(7)和(8)这两个事件中最先出现的一个)(7)收到确认帧ACKn，(这里隐含地表示已经通过了CRC的硬件差错检测)

若n=1-v(S)，则：(已发送的数据帧被接收方确认)

从主机取一个新的数据帧，放入发送缓存：

v(S)←[1-v(S)]：（更新发送状态变量，使用下一个序号）转到(3)。否则，丢弃这个确认帧，转到(6)。（这表明已发送的数据帧没有被接收方确认）(8)若超时计时器时间到，则转到(4)。(重传已发送的数据帧)第七十页，共一百二十八页。停止等待协议的算法在接收结点：(1)v(R)←0。(接收状态变量初始化，其数值等于欲接收的数据帧的发送序号(2)等待。(3)收到一个数据帧：(这里隐含地表示已经通过了CRC的硬件差错检测)

若N(s)=v(R)，则执行(4)；(收到正确序号的数据帧)

否则丢弃此数据帧，然后转到(6)。(丢弃的帧就是重复帧)(4)将收到的数据帧中的数据部分送交上层软件。(5)v(R)←1-v(R)]。(更新接收状态变量，准备接收下一个数据帧)(6)n←V(R)；发送确认帧ACKn，转到(2)。(期望接收n号数据帧，在它之前的帧收到了)第七十一页，共一百二十八页。停止等待协议的算法V(S)=0从主机取一帧N(S)=V(S)将帧送缓冲区从发送缓冲区取出帧并发送设置超时记时器tout应答到？ACK/NAK？V(S)=(1-V(S))超时？ACKNAKNNYY发送方V(R)=0帧收到？接收帧并作差错校验结果正确？N(S)=V(R)?将收到的帧中的数据部分送主机V(R)=(1-V(R))发NAK发ACK丢弃此帧N（重复帧）YYYNN接收方第七十二页，共一百二十八页。停止等待协议中数据帧和确认帧的发送时间关系ABDATADATAACK传播时延tp处理时间tpr确认帧发送时间ta传播时延tp处理时间tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout第七十三页，共一百二十八页。停等协议的信道利用率发送方接收方Ack帧数据帧2RL/B时间T(sec)B为信道容量(b/s)R为单程传播延迟时间(s)L为数据帧长度(bits)U为信道利用率停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。第七十四页，共一百二十八页。4.2Go-back-N连续ARQ协议工作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送。接收方只允许顺序接收，也就是说如果一帧出错，则它后面的N帧尽管可能正确到达接收方，但被直接丢弃，不发送确认。发送方将超时，按序重传所有未被确认的帧。优点：连续发送提高了信道利用率缺点：导致某些已正确接收的帧的重传，因此降低了发送效率误码率较低时，连续ARQ优于停等协议；反之则不一定第七十五页，共一百二十八页。Go-back-N连续ARQ协议Go-back-NARQ第七十六页，共一百二十八页。4.3滑动窗口(SlidingWindow)的概念发送窗口用来对发送端进行流量控制，而发送窗口的大小WT就代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。第七十七页，共一百二十八页。发送窗口的规则如下：（1）发送窗口内的帧是允许发送的帧，而不考虑有没有收到确认。发送窗口右侧所有的帧都是不允许发送的帧。图4-7(a)说明了这一情况。（2）每发送完一个帧，允许发送的帧数就减1。但发送窗口的位置不变。图4-7(b)说明已经发送了0号帧，因此允许发送的帧数就少了一个，即只有4个。（3）如果所允许发送的5个帧都发送完了，但还没有收到任何确认，那么就不能再发送任何帧了。图4-7(c)表示这种情况。这时，发送端就进入等待状态。（4）每收到对一个帧的确认，发送窗口就向前(即向右方)滑动一个帧的位置。图4-7(d)表示发送端已经收到了0,1和2号帧共3个帧的确认，因此发送窗口可以向前滑动3个帧的位置。于是，发送端现在又可以继续发送3个帧(即5~7号帧)。第七十八页，共一百二十八页。第七十九页，共一百二十八页。接收窗口的规则在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。接收窗口的规则很简单，归纳如下： （1）只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。 （2）每收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。同时向发送端发送对该帧的确认。图4-8(a)表明一开始接收窗口处于0号帧处，接收端准备接收0号帧。一旦收到0号帧，接收窗口即向前滑动一个帧的位置(图4-8(b))，准备接收1号帧，同时向发送端发送对0号帧的确认信息。当陆续收到1号至3号帧后，接收窗口的位置应如图4-8(c)所示。第八十页，共一百二十八页。第八十一页，共一百二十八页。发收t0t1t2t3t4t5t6t7初始发0帧发1帧收0帧发ACK0收ACK0发2帧收1帧发ACK1收ACK1问题：如接收窗口大小为1，帧序号用3比特编码，则发送窗口最大值为多少？WT2n-1WT=2WR=1的滑动窗口第八十二页，共一百二十八页。4.4选择重传ARQ协议原则：只重传出错或定时器超时的数据帧方法：WR>1，暂存接受窗口中序号在出错帧之后的数据帧优点：避免重传已正确传送的帧，提高了信道利用率缺点：在接收端需要占用一定容量的缓存第八十三页，共一百二十八页。选择重传ARQ协议接收窗口的最大值受下式约束：WR2n/2

当接收窗口WR为最大时，WT=WR=2n/2。第八十四页，共一百二十八页。4.5数据链路层协议分类面向字符的链路层协议ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM）IBM的二进制同步通信规程（BSC）DEC的数字数据通信报文协议（DDCMP）PPP第八十五页，共一百二十八页。面向比特的链路层协议IBM的SNA使用的数据链路协议SDLC（SynchronousDataLinkControlprotocol）；ANSI修改SDLC，提出ADCCP（AdvancedDataCommunicationControlProcedure）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作为X.25网络接口标准的一部分，后来改为LAPB。第八十六页，共一百二十八页。4.5.1面向字符型协议实例：BSC什么是面向字符型协议?

以字符为控制传输信息的基本单元

ASIIC码：格式字符：SOH（startofheading）

STX（startoftext）

ETB（endoftransmissionblock）

ETX（endoftext）控制字符：ACK（acknowledge）

NAK（negativeacknowledge）

ENQ（enquire）

EOT（endoftransmission）

SYN（synchrous）

DLE（datalinkescape）第八十七页，共一百二十八页。面向字符型协议实例：BSC面向字符型BSC协议的数据报文格式第八十八页，共一百二十八页。面向字符型协议实例：BSC建立、维护与释放数据链路流程图第八十九页，共一百二十八页。4.5.2面向比特型协议实例：HDLC面向字符型数据链路层协议的缺点：报文格式不一样；不同字符集机器难以通信传输透明性不好；等待发送方式，传输效率低。面向比特型协议的设计目标：以比特作为传输控制信息的基本单元；数据帧与控制帧格式相同；传输透明性好；连续发送，传输效率高。第九十页，共一百二十八页。4.5.2面向比特型协议实例：HDLCHDLC--High-LevelDataLinkControl

HDLC的帧结构F（flag）：固定格式—01111110

作用—帧同步传输数据的透明性（零比特插入与删除）A（address）：地址C（control）：帧的类型、帧的编号、命令与控制信息I（information）：网络层数据，Nmax=256BCRC（checksum）：校验A、C、I字段的数据G(X)=X16+X12+X5+1第九十一页，共一百二十八页。帧类型及控制字段的意义第九十二页，共一百二十八页。帧类型I帧：N（S）—发送帧的顺序号

N（R）—接收帧的顺序号

P/F=Poll/Final，P=1询问，F=1响应

P与F成对出现S帧：监控功能位

S=00，RR（receiveready）

S=10，RNR（receivenotready）

S=01，RJE（reject）

S=11，SREJ（selectreject）U帧：用于实现数据链路控制功能第九十三页，共一百二十八页。U帧的格式与链路控制功能第九十四页，共一百二十八页。控制字段格式Controlfieldof(a)Aninformationframe.(b)Asupervisoryframe.(c)Anunnumberedframe.第九十五页，共一百二十八页。五、数据链路层的工作过程简化的信息帧结构的表示方法一个信息帧的表示

第九十六页，共一百二十八页。数据链路层的工作过程无编号帧的表示方法SNRM帧与UA帧结构的表示方法第九十七页，共一百二十八页。正常响应模式数据链路工作说明第九十八页，共一百二十八页。六、Internet中主要的数据链路层协议SLIP（SerialLineIP） —串行线路的Internet数据链路层协议PPP（Point-to-PointProtocol）

—点-点协议SLIP与PPP用于串行通信的拨号线路上，是目前家庭计算机或公司用户通过ISP接到Internet主要的协议。第九十九页，共一百二十八页。SLIP协议SLIP出现于20世纪80年代初，最早是在BSDUNIX4.2版操作系统上实现的;SLIP协议支持TCP/IP协议;对数据报进行了简单的封装，然后来用RS-232接口串行线路进行传输;SLIP通常也用来将远程终端连接到UNIX主机，也可通过租用或拨号串行线路进行主机到路由器，以及路由器到路由器的通信。第一百页，共一百二十八页。典型的SLIP接入方式Internet的家庭或小型公司用户通过调制解调器、电话网络连接到ISP的调制解调器；ISP的调制解调器再通过它的路由器接入Internet；SLIP系统一般可以发送和接收1006B的IP数据报。第一百零一页，共一百二十八页。SLIP协议的帧结构RFC1055文件对SLIP帧格式进行了讨论;SLIP帧头与帧尾的“CO”，是协议使用的惟一的一个控制字符;CO的二进制编码比特序列是10000110000000;CO的使用将影响SLIP帧数据的透明性;第一百零二页，共一百二十八页。SLIP协议的缺点使用SLIP协议时，通信的双方都必须知道对方的IP地址，因为SLIP协议没有为它们提供相互交换地址信息的方法；没有设置协议类型字段，不具备同时处理多种网络层协议的能力；没有校验和字段，差错控制功能由高层的协议承担；SLIP协议并不是Internet的协议标准，因此不同版本的之间就会存在着差别，使得互连变得困难。第一百零三页，共一百二十八页。PPP协议基本特点PPP协议是Internet标准，RFC1660、RFC1661定义了PPP协议与帧结构；PPP协议处理了差错检测，支持面向字符型协议与面向比特型协议,可以支持IP协议及其他一些网络层协议（例如IPX协议）；PPP协议不仅在拨号电话线，并且在路由器─路由器之间的专用线上广泛应用;PPP协议是在大多数家庭个人计算机和ISP之间使用的协议，它可以作为在高速广域网和社区宽带网协议族的一部分。第一百零四页，共一百二十八页。第一百零五页，共一百二十八页。PPPPPP是因特网中广泛使用的点-点数据链路协议；PPP由以下三部分组成：一种组帧的方式，用于区分帧的边界，并可支持差错检测；一个链路控制协议（LCP），用于链路的建立、测试、协商及拆除；一组网络控制协议（NCP），用于支持多种网络层协议；特别是支持IP的NCP可支持IP地址的动态分配。

第一百零六页，共一百二十八页。PPP（续）使用PPP通信的过程：首先在两个modem之间建立物理连接；然后使用LCP建立链路；然后使用NCP配置网络层，特别是支持IP的NCP会向ISP申请分配一个IP地址；这时PC就在Internet上了；完成工作后首先使用NCP拆除网络层连接，释放IP地址；然后使用LCP关闭数据链路层连接；最后释放物理连接。第一百零七页，共一百二十八页。PPP（续）PPP的帧格式：PPP是面向字符的，因此采用字符填充技术，且帧长都是字节的整数倍，但PPP也能在面向比特的线路（如HDLC）上使用；地址总是设成11111111，可以免去数据链路地址的分配；控制缺省为00000011，即缺省时采用不可靠无编号的数据传输方式，但需要时也可以协商采用可靠的有编号的数据传输方式；增加了协议域，用于指出载荷字段中携带的是哪类分组，从而可以支持LCP、NCP及不同的网络层协议；许多字段的长度是可以协商的，而且支持头部压缩。第一百零八页，共一百二十八页。PPP信息帧格式标志（flag）：01111110地址（address）：值为“FF”（11111111），表示网中所有的站都接收该帧控制（control）：值为“03”（00000011）协议（protocol）：长度为2字节，它标识出网络层协议数据域的类型。常用的网络层协议的类型主要有：0021H—TCP/IP0023H—OSI0027H—DEC数据字段：长度可变第一百零九页，共一百二十八页。PPP与HDLC帧格式(a)PPP帧格式(b)HDLC帧格式第一百一十页，共一百二十八页。PPP链路up/down过程（简单状态图）第一百一十一页，共一百二十八页。PPP协议的状态图建立失败失败NCP配置鉴别成功通信结束载波停止检测到载波双方协商一些选项鉴别网络打开终止静止第一百一十二页，共一百二十八页。链路控制帧（LCP）与网络控制帧（NCP）链路控制帧（LCP）网络控制帧（NCP）第一百一十三页，共一百二十八页。4.滑动窗口(SlidingWindow)实际的通信往往是全双工通信；捎带应答（piggybacking）：将确认序号携带在数据帧中传输，提高线路的效率；推迟确认：当需要发送确认但没有要发送的数据时，可以让确认信息推迟一小段时间再发送；滑动窗口协议：允许发送端在没有收到前一个帧的确认时，就可以发送后续的帧；接收端可以对正确收到的若干个帧同时进行确认。滑动窗口协议的要点：任何时刻发送进程维护一组帧序号，对应于一组已经发送但尚未被确认的帧，用一个发送窗口维护这些帧；接收进程也维护一组帧序号，对应于一组允许接收的帧，用一个接收窗口维护这些帧序号。第一百一十四页，共一百二十八页。发送窗口的概念发送窗口中的序号代表已发送但尚未确认的帧；窗口下沿代表最早发送但至今尚未确认的帧；发送窗口中包含的序号数称为发送窗口的大小，它有一个最大值；当发送窗口尚未达到最大值时，可以发送新的帧；当要发送新帧时，将窗口上沿加1后模2n，然后将该序号分配给新的帧；当收到对窗口下沿帧的确认时，窗口下沿加1，将已被确认的帧移出发送窗口；（图）每一个帧都有可能传输出错，所以发送窗口中的帧都必须保留在缓冲区里以备重传，当某个帧被移出发送窗口时，同时从缓冲区中删除；当发送窗口达到最大值时，停止从网络层接收数据，直到有一个缓冲区空出来为止。第一百一十五页，共一百二十八页。发送窗口和接收窗口图示第一百一十六页，共一百二十八页。接收窗口的概念接收窗口中的序号代表允许接收的帧，任何落在窗口外的帧都被丢弃，落在窗口内的帧存放到缓冲区里；数据链路层必须按顺序将数据递交给网络层，接收窗口中顺序最早的帧为窗口下沿帧，其余的帧朝着窗口上沿的方向，顺序逐渐升高；当接收端收到窗口下沿帧且校验正确时，将其交给网络层，向发送方发回一个确认，然后窗口整体向前移动一个位置；（图）和发送窗口不同，接收窗口的大小是不变的，总是保持初始时的大小；接收窗口大小为1，意味着数据链路层只能顺序接收数据，当接收窗口大于1时不是这样，但无论如何，数据链路层递交给网络层的帧都是有序的。第一百一十七页，共一百二十八页。4.11位滑动窗口协议该协议使用停-等方式，只用1比特长的帧序号。由于支持双向传输，所以每个协议实体需要同时完成发送和接收两个功能。

1)初始化：next_frame_to_send=0，frame_expected=0；

2)从网络层接收一个分组，组帧，发给物理层，启动计时器；

3)等待事件（帧到达，收到坏帧，超时）；

4)事件发生：

①帧到达：从物理层接收帧，若seq=frame_expected，将帧中携带的分组 交给网络层，frame_expected加1；若ack=next_frame_to_send，终止计 时器，从网络层接收新的分组放入缓冲区，next_frame_to_send加1；执 行5）；

②其它事件（坏帧，超时）：执行5）；

5)从缓冲区取分组，组帧，发给物理层，启动计时器；

6)跳转到3）。第一百一十八页，共一百二十八页。正常与非正常情况下协议的执行Twoscenariosforprotocol4.(a)Normalcase.(b)Abnormalcase.第一百一十九页，共一百二十八页。管道化技术（pipelining）假设信号传播延迟不可忽略：卫星信道上，信号的来回延迟按500ms计算，若帧的传输时间为20ms，则线路的效率为1/26。数据速率记为b，帧长度记为L，信号来回延迟记为R，则采用停-等协议的线路效率为