【文档说明】计算机网络四数据链路层1基本原理课件.pptx，共(127)页，2.255 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77009.html

以下为本文档部分文字说明：

计算机网络四数据链路层1基本原理课件前言：数据链路层的设计问题•为什么需要数据链路层？•物理层未解决的问题：–位流传输过程中不可避免会出现差错（电磁干扰，线路问题）–数据收发之间的速率匹配问题（不同设备处理速度不同）最主要的作用是通过一些数据链路层协议(

即链路控制规程),在不太可靠的物理链路上实现可靠的数据传输.前言：数据链路层的设计问题1.向网络层提供的服务主机A主机BALTLNLDLPLALTLNLDLPL帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧帧无确认的无连接服务有确认的无连接服务面向连接

的服务前言：数据链路层的设计问题2.成帧•涉及的问题•协议数据单元将上层(网络层)交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧；考虑接收双方的同步问题（即定界）；计算帧的校验和并放入帧中一起传送给接收方；帧：在数据链路

上交换数据的单位。标志字段指明帧的开始和结束地址字段控制字段正文字段校验字段前言：数据链路层的设计问题2.成帧•字符计数法•字符填充的首尾定界法•位填充的首尾定界法5123456789801234568789012351234767

898012345687890123计数值传输出错时导致收发双方不同步.同步字符法标志法填充技术前言：数据链路层的设计问题2.成帧•物理层编码违例法•综合法“0”“1”违例或用计数值确定帧尾检查帧定

界符是否出现在应该出现的地方计算校验和前言：数据链路层的设计问题3.流量控制•流量控制•流量控制的特点网络层实体控制从数据链路层接收数据的速率，据此，数据链路层要控制从同等实体接收PDU的速率。限制发送方发送速

度的一种机制。使发送速率不能超过接收方能处理的速率。流量控制必须是动态的必须有某种反馈机制流量速度不仅与发方速度相关而且与网络的当前拥挤程度有关使发方了解收方的当前处理能力前言：数据链路层的设计问题4.差错控制•顺序到达指保证所有的帧最终都按正确的发送次序到达目的

。检错和纠错检出传输中出现的差错；可能的话确定出错位置从而纠正错误。确认方式计时器法计时器值的设定要保证一帧到达对方并作处理后，相应的确认帧返回。ACK肯定确认NAK否定确认计时结合序号才能保证每一帧的正确次序。前言：数据链路层的设计问题5.数据链路层协议的作用数据链路协议

23数据链路进程路由选择进程路由器A帧分组/包2322232路由器B传输线2322223DL协议的作用就是使不可靠的通信线路变得一定程度的好。物理层:----物理链路----比特流传输----有差错的物理链路数据链路层

:----数据链路----帧传输----无差错的数据链路----数据链路层数据服务单元----帧Computer电话交换网ModemModemComputer物理线路数据链路一、数据链路层概述•数据链路层于物理层之上,属于低层。物理层传输的是比特流，单位是比特。•数据链路

层传输单位是帧，一帧一帧地处理。其工作是从物理层获取比特流，进行封装成帧、并对帧进行如透明传输、差错控制等处理，从而递交给上一层（网络层），同时也对网络层下传的数据进行处理，进而传给物理层。数据链路层传送的是帧IP数据报1010……0110帧取出数据链路层网

络层链路结点A结点B物理层数据链路层结点A结点B帧(a)(b)发送帧接收链路IP数据报1010……0110帧装入一、数据链路层概述分组与帧的关系图示Relationshipbetweenpacketsandfra

mes一、数据链路层概述数据链路层的简单模型局域网广域网主机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)•漏检率：信息位出错但是接收者无法了解到的概率的负若干次方来表示常常用接收的总码元数发生差错的码元数10eP二、差

错检测与校正2.差错与校正概念•出错的类型–单个错：由随机的信道热噪声引起，一次只影响1位；–突发错：由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。•编码的类型–检错码

：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来使用以便进行差错恢复；–纠错码：不权能够检测到数据传输发生了错误，而且能够自行纠正错误。二、差错检测与校正2.差错与校正概念•码字（codeword）：由m比特的数据（消息）加上r比特的

冗余（校验位）构成；•有效编码集：由2m个有效码字组成；•检错：当收到的码字为无效码字时检测出错误；•海明距离（HammingDistance）：两个码字的对应位上取值不同的位数；•纠错：将收到的无效码字纠

正到距其最近的有效码字；•检错码与纠错码的能力都是有限的。二、差错检测与校正2.差错与校正概念•编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。•检错能力：为检测出d比特错误，编码集的海明距离至少应为d+1；奇偶校验是能够检测出1比特错误的检错码。•纠错能

力：为纠正d比特错误，编码集的海明距离至少应为2d+1；海明码是能够纠正1比特错误的纠错码。二、差错检测与校正2.差错控制与校正方法•差错控制：ARQ和FEC–ARQ（自动重传请求）•AutomaticRequestforRepeat•接收方检测错误，通知发送方重

传•双向信道，发送方缓存发送的数据–FEC（前向纠错）•ForwardErrorCorrection•接收方不仅可以检测错误，而且知道错误的位置，从而改正错误•采用纠错码，无需反向信道，无需重发，但编码

效率低,纠错设备复杂二、差错检测与校正！！！3.差错检测与校正和流量控制由于系统性能的不同，如硬件能力（包括CPU，存储器等）和软件功能的差异，会导致发送方与接收方处理数据的能力有所不同。流量控制的作用是使发送方所发出的数

据流量，使其发送速率不要超过接收方所能接收的速率。流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收方是否能接收到存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协议则将关于帧的确认与流量控制巧妙地结合在了一起。•流量控制的主要机制：–基于反馈的流量控制（√）–基于速

率的流量控制二、差错检测与校正4.常用的简单差错控制编码（奇偶校验码）•奇偶校验码：增加冗余位使得码字中‘1’的个数为奇数或者偶数，检错码–垂直奇偶校验–水平奇偶校验–水平垂直奇偶校验•垂直奇偶校验：–发送的信息块分成定长为p位的

若干段（一列）。–每段增加一个（奇偶校验）冗余位ri：I11I12···I1qI21I22···I2q2Ip1Ip2···Ipq·········r1r2···rq冗余位信息位发送顺序垂直奇偶校验q1,2,...,i21piiiiIII

r偶校验：q1,2,...,i121piiiiIIIr奇校验：二、差错检测与校正4.常用的简单差错控制编码（垂直奇偶校验）•垂直奇偶校验–编码效率：–能力：•检测出每列（段）中所有奇数（1、3…）个错•突发错误的漏检

率为50%!!•在发送和接收的过程中进行编解码•水平奇偶校验：降低突发错误的漏检率–对各个信息段的相应位横向进行编码1ppR二、差错检测与校正4.常用的简单差错控制编码（水平奇偶校验）•水平奇偶校验–编码效率：–能力：•各段同一位上的奇数个错•长度小于等

于p的突发差错•编码和检测相比垂直校验而言实现要复杂一些p1,2,...,i21iqiiiIIIr偶校验：p1,2,...,i121iqiiiIIIr奇校验：I11I12···I

1qI21I22···I2q2Ip1Ip2···Ipq·········r1r2rp冗余位信息位发送顺序水平奇偶校验···1qqR二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）•水平垂直奇偶校验1,1,21,1,12,11,11,12

1,1211,q1,2,...,jp1,2,...,iqpqqqpppqppjjjjpiqiiqirrrrrrrIIIrIIIr偶校验：

I11I12···I1qI21I22···I2q2Ip1Ip2···Ipq·········r1,q+1r2q+1rpq+1冗余位信息位发送顺序水平奇偶校验···rp+1,1rp+1,2···rp+1,qrp+1,q+1编码效率)1)(1(

qppqR二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）•水平垂直奇偶校验能力–检测出：•所有3位或3位以下的错误、奇数位错•突发长度小于等于p+1的突发差错•很大一部分偶数位错：差错分布以致

于某一行或者某一列有奇数个差错–部分纠错功能：•可以纠正1比特错–信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）1000101

0字符1b1b2b3b4b5b6b7check11001011字符211011010字符310101011字符410001010字符510001010字符611101010字符700100001校验字符•水平垂直奇校验的例子二、差错检测与校

正4.常用的简单差错控制编码（海明码）1.海明码(1)海明距离及意义两个码字中不同的位数的个数称为海明距离,简称H距离1000100110110001求H距离的方法主要有:异或运算海明距离的意义是:假

如两个码字具有海明距离d,则需要d个位差错才能将其中一个码字转换成另一个.H=3二、差错检测与校正4.常用的简单差错控制编码（海明码）(2)海明码算法①将码字数内的位从最左边开始按顺序依次编号,第1位是1号,第2位是2号,……

第n位是n号.编号为2的幂的位(1号位,2号位,4号位,8号位等)是校验位,其余的位填入m位数据(2r≧n+1).②每个校验位的取值应使得包括自己在内的一些位的集合符合规定的奇偶性.(主要用于奇偶性校

验)123456789101112校验位二、差错检测与校正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.常用的简单差错控制编码（海明码）123456789101100100111010编码码字最终的海明码为什么此处是1?1,2,4,8是校验位!其余位是信

息位.(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+1–CRC-16：G(x)=x16+x15+x2+1–CRC-CCITT：G(x)=x16+x12+x5+1–CRC-32G（x）=x32+x

26+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)。若余式为零，则表示无差错；否则，说明传输过程中出现了错误。011000

011101001010110011011000011101001010110011二、差错检测与校正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（相当于10100010000）二、差错检测与校正4.常用的简单差错控制编码（CRC循环冗余码）•CRC的例子（2）•多项式

除法后得到冗余码为1101，所以相应的数据发送序列为10100011101101000100001011111011111010001111110101011111010101111011111010101111101二、差错检测与校正4.常用的简单差错控制编码（CRC

循环冗余码）NoImageR0R1Rr-1信息输入端g1g2gr-11...)(12211xgxgxgxxGrrrCRC校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现

。CRC硬件实现1)(24xxxxG111101NoImageR0R1R3信息输入端R21000101R0R1R2R3输入输出:110100001GG1110100111010110001111101100101010110101010010

0001000100000111101二、差错检测与校正4.常用的简单差错控制编码（CRC循环冗余码）二、差错检测与校正4.常用的简单差错控制编码（CRC循环冗余码）•CRC的检错能力（1）•如果传输过程中出现差错：差错模式E(x)＝发送码

字和接收码字的半加，其中1的位置对应变化了信息位的位置。•若E(x)能被G(x)整除，则不能检测这样的错误E(x)/G(x)E(x)/G(x)T(x)/G(x)E(x))/G(x)(T(x)0)(/)()()()()()()()()()(:)()(/)()()()

()(有错时：，即无错时，记为xGxTxQxGxRxRxQxGxRxKxxTxRxGxKxxRxQxGxKxrrr二、差错检测与校正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,ETXA,B,GOOD,BYE数据组帧字符填充•在首尾界符法中，由于数据中可能会出现DLESTX或DLEETX，从而干扰帧的正常定界•字符填充法可用于解决上述问题。即发送端在数

据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。DLE,STX,A,DLE,B,DLE,ETXDLE,STX,A,DLE,DLE,B,DLE,ETX网络层发出的数据经数据链路层填充后的数据字节填充图例(a)Aframedelimitedbyfl

agbytes(b)Fourexamplesofbytesequencesbeforeandafterstuffing.首尾标记法•每一帧使用一个特殊的位模式“01111110‖作为开始和结束标记。•该位模式又称为flag•位模式

允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。…Data…0111111001111110位填充•在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界•位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1‖

时，则在其后自动插队入一个“0‖。该技术简称“逢五1插0‖；接收端则忽略5个连续的“1‖后面的“0‖，简称“逢五1删0‖。(a)011011111111111111110010(b)011011111011

111011111010010(c)011011111111111111110010填充的位比特填充图例(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataasthey

arestoredinreceiver’smemoryafterdestuffing.违例编码法–采用不可能出现在信息位中的比特编码作为帧的起始边界。•在物理层采用特定的比特编码方法时使用•曼彻斯特编码中电平的跳变表示1（低->高）和0（高->低）•高

高和低低电平是违例编码四、数据链路层协议—数据链路通信的简单模型AP1缓存AP2缓存帧帧数据链路发送方接收方主机A主机B完全理想化的数据传输完全理想化的数据传输基于以下两个假定•假定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；发送方根据收到的返回帧，决定发送新帧和重发。•帧丢失处理：超时定

时器；以序号标识数据帧•优点：简单•缺点：信道利用率低，信道还远远没有被数据比特填滿数据帧在链路上传输的几种情况AB时间送主机送主机Tout丢失AB重传送主机放弃×(a)正常情况(b)数据帧出错(C)数据帧丢失(d)

确认帧丢失AB出错重传送主机重传丢失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停等协议的信道利用率发送方接收方2RL/B时间T(sec)B为

信道容量(b/s)R为单程传播延迟时间(s)L为数据帧长度(bits)U为信道利用率RBLLRBLBLU22//停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。4.2Go-back-N连续ARQ协议•工

作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送。接收方只允许顺序接收，也就是说如果一帧出错，则它后面的N帧尽管可能正确到达接收方，但被直接丢弃，不发送确

认。发送方将超时，按序重传所有未被确认的帧。•优点：连续发送提高了信道利用率•缺点：导致某些已正确接收的帧的重传，因此降低了发送效率•误码率较低时，连续ARQ优于停等协议；反之则不一定Go-back-N连续ARQ协议Go

-back-NARQ4.3滑动窗口(SlidingWindow)的概念发送窗口用来对发送端进行流量控制，而发送窗口的大小WT就代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。发送窗口的规则口右侧所有的帧都是不允许发送的帧

。图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比特编码，则发送窗口最大值为多少？WT2n-1WT=2WR=1的滑动窗口4.4选择重传ARQ协议•原则：只重传出错或定时器超时的数据帧

•方法：WR>1，暂存接受窗口中序号在出错帧之后的数据帧•优点：避免重传已正确传送的帧，提高了信道利用率•缺点：在接收端需要占用一定容量的缓存选择重传ARQ协议接收窗口的最大值受下式约束：WR2n/2当接收窗口WR为最大时，WT=WR=2n/2。4.5数据链路层协议分

类•面向字符的链路层协议•ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM）•IBM的二进制同步通信规程（BSC）•DEC的数字数据通信报文协议（DDCMP）•PPPSynchronousDataLinkControlprotocol）；AN

SI修改SDLC，提出ADCCP（AdvancedDataCommunicationControlProcedure）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作为X.2

5网络接口标准的一部分，后来改为LAPB。4.5.1面向字符型协议实例：BSC•什么是面向字符型协议?•以字符为控制传输信息的基本单元•ASIIC码：格式字符：SOH（startofheading）STX（startoftext）ET

B（endoftransmissionblock）ETX（endoftext）控制字符：ACK（acknowledge）NAK（negativeacknowledge）ENQ（enquire）EOT（endoftransmission）SYN（synchrous

）DLE（datalinkescape）面向字符型协议实例：BSCSYNSYNSOH报头STX正文ETB/ETXBCC报文开始同步字符用户定义报头结束分组结束报文结束校验字段正文字段面向字符型BSC协议的数据报文

格式面向字符型协议实例：BSC发送ENQ接收ACKACK?发送数据接收应答ACK/NAK结束?重发发送EOT准备数据放送ENQ发送ACK接收数据,EOT发送ACK发送NAKENQ?EOT?BCC正确?结

束结束YYYYNNNNNYACKNAK建立、维护与释放数据链路流程图4.5.2面向比特型协议实例：HDLC面向字符型数据链路层协议的缺点：•报文格式不一样；•不同字符集机器难以通信•传输透明性不好；•等待

发送方式，传输效率低。面向比特型协议的设计目标：•以比特作为传输控制信息的基本单元；•数据帧与控制帧格式相同；•传输透明性好；•连续发送，传输效率高。4.5.2面向比特型协议实例：HDLC标志字段F(8位)地址字段A(8/16位)控制字段C(8/16位)信息字段I(长度可变)帧校验字

段FCS(16/32位)标志字段F(8位)HDLC--High-LevelDataLinkControlHDLC的帧结构F（flag）：固定格式—01111110作用—帧同步传输数据的透明性（零比特插入与删除）A（add

ress）：地址C（control）：帧的类型、帧的编号、命令与控制信息I（information）：网络层数据，Nmax=256BCRC（checksum）：校验A、C、I字段的数据G(X)=X16+X12+X5+1帧类型及控制字段的意义标志字段F（8位）地

址字段A（8/16位）控制字段C（8位）信息字段I(长度可变)帧校验字段FCS（16/32位）标志字段F(8位)0N(S)P/FN(R)10监控P/FN(R)11未分配P/F未分配信息帧(I)：监控帧(S)：无编号帧(U)：b0b4b7b1b2b3b5b6帧类型•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帧的格式与链路控制功能MP/FM11A01111110FCS011111101100000

00111100000100011010001UACMADSARMSNRMSABMDISC命令响应置异步响应置正常响应置异步平衡响应拆链无编号确认命令拒绝建立主从的点-点结构建立主从的多点结构建立复合站的平衡结构结束已建立的数据链路从站响应主站的命令从站报告帧传输异

常控制字段格式Controlfieldof(a)Aninformationframe.(b)Asupervisoryframe.(c)Anunnumberedframe.五、数据链路层的工作过程IN(S)N(R)P/FData高层数据探询/终止位接收帧序号发送

帧序号I帧标志简化的信息帧结构的表示方法一个信息帧的表示I，N(S)=3，N(R)=4，P=1数据链路层的工作过程•无编号帧的表示方法•SNRM帧与UA帧结构的表示方法U，SNRM，P=1U，UA，

F=1置异步响应模式：无编号确认：01111110A11001001FCS0111111001111110A11001110FCS01111110置异步响应模式：无编号确认：正常响应模式数据链路工作说明六、Internet中主要的数据链路层协议•SLIP（Seria

lLineIP）—串行线路的Internet数据链路层协议•PPP（Point-to-PointProtocol）—点-点协议•SLIP与PPP用于串行通信的拨号线路上，是目前家庭计算机或公司用户通过ISP接到Internet主要的协议。S

LIP协议•SLIP出现于20世纪80年代初，最早是在BSDUNIX4.2版操作系统上实现的;•SLIP协议支持TCP/IP协议;•对数据报进行了简单的封装，然后来用RS-232接口串行线路进行传输;•SLIP通常也用来将远程终端连接到UNIX主

机，也可通过租用或拨号串行线路进行主机到路由器，以及路由器到路由器的通信。典型的SLIP接入方式•Internet的家庭或小型公司用户通过调制解调器、电话网络连接到ISP的调制解调器；•ISP的调制解调器再通过它的路由器接入Internet；•SLIP系统一般可以发送和接收1006

B的IP数据报。SLIP协议的帧结构•RFC1055文件对SLIP帧格式进行了讨论;•SLIP帧头与帧尾的“CO‖，是协议使用的惟一的一个控制字符;•CO的二进制编码比特序列是10000110000000;•CO的使用将影响SLIP帧数据的透明性;IP数据包EndEnd

IP数据包C0C0C0在数据传送中以“DB”“DC”表示DB在数据传送中以“DB”“DD”表示SLIP协议的缺点•使用SLIP协议时，通信的双方都必须知道对方的IP地址，因为SLIP协议没有为它们提供相互交换地址信息的方法；•没有设置协议类型字段，不具备同时处理多种网络层协议的能

力；•没有校验和字段，差错控制功能由高层的协议承担；•SLIP协议并不是Internet的协议标准，因此不同版本的之间就会存在着差别，使得互连变得困难。PPP协议基本特点•PPP协议是Internet标准，RFC1660、RFC1661定义了PPP协议与帧结构；•PPP协议处理了差错检测，支持面向

字符型协议与面向比特型协议,可以支持IP协议及其他一些网络层协议（例如IPX协议）；•PPP协议不仅在拨号电话线，并且在路由器─路由器之间的专用线上广泛应用;•PPP协议是在大多数家庭个人计算机和ISP之间使用的协议，它可以作为在高速广域网和社区宽带网协议族的一部分。PPP•P

PP是因特网中广泛使用的点-点数据链路协议；•PPP由以下三部分组成：–一种组帧的方式，用于区分帧的边界，并可支持差错检测；–一个链路控制协议（LCP），用于链路的建立、测试、协商及拆除；–一组网络控

制协议（NCP），用于支持多种网络层协议；特别是支持IP的NCP可支持IP地址的动态分配。PPP（续）•使用PPP通信的过程：–首先在两个modem之间建立物理连接；–然后使用LCP建立链路；–然后使用NC

P配置网络层，特别是支持IP的NCP会向ISP申请分配一个IP地址；–这时PC就在Internet上了；–完成工作后首先使用NCP拆除网络层连接，释放IP地址；–然后使用LCP关闭数据链路层连接；–最后释放物理连接。PPP

（续）•PPP的帧格式：–PPP是面向字符的，因此采用字符填充技术，且帧长都是字节的整数倍，但PPP也能在面向比特的线路（如HDLC）上使用；–地址总是设成11111111，可以免去数据链路地址的分配；–控制缺省为0000001

1，即缺省时采用不可靠无编号的数据传输方式，但需要时也可以协商采用可靠的有编号的数据传输方式；–增加了协议域，用于指出载荷字段中携带的是哪类分组，从而可以支持LCP、NCP及不同的网络层协议；–许多字段的长度

是可以协商的，而且支持头部压缩。PPP信息帧格式标志字段(7E)地址字段(FF)控制字段(03)信息字段帧校验字段(FCS)标志字段(7E)协议字段(C021)标志（flag）：01111110地址（address）：值

为“FF”（11111111），表示网中所有的站都接收该帧控制（control）：值为“03”（00000011）协议（protocol）：长度为2字节，它标识出网络层协议数据域的类型。常用的网络层协议的类型主要有：0021H—T

CP/IP0023H—OSI0027H—DEC数据字段：长度可变PPP与HDLC帧格式(a)PPP帧格式(b)HDLC帧格式PPP链路up/down过程（简单状态图）PPP协议的状态图建立失败失败NCP配置鉴别成功通信结束载波停止检测到载波双方协商一些选项

鉴别网络打开终止静止链路控制帧（LCP）与网络控制帧（NCP）•链路控制帧（LCP）•网络控制帧（NCP）标志字段(7E)地址字段(FF)控制字段(03)链路控制数据帧校验字段(FCS)标志字段(7E)协议字段(C021

)标志字段(7E)地址字段(FF)控制字段(03)网络控制数据帧校验字段(FCS)标志字段(7E)协议字段(8021)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）。正常与非正常情况下协议的执行Twoscenariosf

orprotocol4.(a)Normalcase.(b)Abnormalcase.管道化技术（pipelining）•假设信号传播延迟不可忽略：–卫星信道上，信号的来回延迟按500ms计算，若帧的传输时间为20ms，则线路的效率为1/26。–数据速率记为b，帧长度

记为L，信号来回延迟记为R，则采用停-等协议的线路效率为：Lb/(L+bR)。•管道化技术–允许发送窗口包含多个未被确认的帧，当信号传播延迟远大于帧的传输时间时，适合采用这个技术。–问题：传输出现错误怎么处理？–两种解决的方法：gobackn和se

lectiverepeat。gobackn和selectiverepeat•Gobackn–接收进程丢弃所有的后继帧，并且不通知发送进程；发送进程超时后，重传所有未被确认的帧；–该策略对应接收窗口为1的情况，即只能按顺序接收帧；（图）–若错误率很高，这种方法会浪费很多带宽，但对接收端内

存的需求不大。•选择重传–只要是落入接收窗口且校验正确的帧都要接收下来，这样发送进程只需重传出错的帧；该策略对应接收窗口大于1的情况；–选择重传通常使用NAK对校验出错或疑为丢失的帧进行确认，以便发送进程尽快重传该帧；（图）–当窗口很大时，这种方法需要大量的数据链路层内存，但它不浪费带宽。图示(a

)goback;(b)selectiverepeatGobackn的处理流程1)初始化；（开放网络层，设置窗口参数）2)等待事件（网络层准备好，帧到达，收到坏帧，超时）；3)事件发生：①网络层准备好：从网络层接收分组，组帧发送，修改相关参数，执行4）；②帧到达：从物理层

接收帧，若seq=frame_expected，将帧中携带的分组交给网络层，frame_expected加1；若ack落于发送窗口内，将发送窗口下沿开始至序号为ack的帧从发送窗口中移去（通过修改窗口参数），终止相关的计时器，执行4）；③坏帧：执行4）；④超时：从发生超时的帧（a

ck_expected）开始重发发送窗口内所有的后继帧，然后执行）；选择重传的处理流程1)初始化；（开放网络层，设置窗口参数）2)等待事件（帧到达，坏帧，数据帧超时，网络层准备好，ACK超时）；3)事件发生：①网络层准备好：从网络层

接收分组，组帧发送，修改相关参数，执行4）；②帧到达：从物理层接收帧，a)收到的是数据帧，i)若不是期待接收的帧且未发送过NAK，则发送一个NAK帧，要求重发指定序号的帧（frame_expected），否则启动ACK计时器；继续ii)；ii)若收到的帧落在接收窗口内且此前

未收到过，则放入相应缓冲区并设置缓冲区满标志；继续iii)；iii)若接收窗口下沿帧已经到达，则从该帧开始将连续的若干个帧交给网络层，并修改相应参数（缓冲区满标志，接收窗口范围），启动ACK计时器；跳转到

c)；选择重传的处理流程（续）b)若为NAK帧，且请求重发的帧落在当前的发送窗口内，则重发这个帧；c)若从发送窗口下沿开始连续的若干个帧已被确认，则终止这些帧的计时器，修改发送窗口大小及发送窗口下沿值将这些帧去掉；跳转到4)；③收到坏帧：如果尚未发送过NAK，则发送一个NAK；跳转到4)；④超时（

数据帧超时）：重发超时的帧；跳转到4)；⑤ACK超时：为指定的帧发送单独的确认帧；跳转到4)；4)若发送窗口大小小于所允许的最大值（NR_BUFS），开网络层允许，否则关网络层允许；5)返回2)。窗口限制•使用gobackn协议，发送窗口的大小不能超过2n-1；•

使用选择重传协议，发送窗口的大小不能超过2n-1。（例）选择重传窗口限制示例(a)Initialsituationwithawindowsizeseven.(b)Aftersevenframessentandreceived,butnotacknowled

ged.(c)Initialsituationwithawindowsizeoffour.(d)Afterfourframessentandreceived,butnotacknowledged.