《计算机网络(四)数据链路层(1.基本原理).ppt》由会员分享，可在线阅读，更多相关《计算机网络(四)数据链路层(1.基本原理).ppt（127页珍藏版）》请在金锄头文库上搜索。
1、计算机网络（计算机网络（四四）关于数据链路层（关于数据链路层（1.基本原理）基本原理）信息科学与技术学院 学习目标!w了解：数据链路层的设计问题w掌握：数据链路层差错控制方法、循环冗余码编码原理w掌握：数据链路层的功能w掌握：基本数据链路协议w掌握：停等协议、滑动窗口协议的工作原理w掌握：面向比特型数据链路层协议实例 HDLC。w了解：Internet中的数据链路层协议。前言：数据链路层的设计问题w为什么需要数据链路层？w物理层未解决的问题：n位流传输过程中不可避免会出现差错 （电磁干扰，线路问题）n数据收发之间的速率匹配问题（不同设备处理速度不同）最主要的作用是通过一最主要的作用是通过一些数
2、据链路层协议些数据链路层协议( (即即链路控制规程链路控制规程),),在不太在不太可靠的物理链路可靠的物理链路上实现上实现可靠可靠的数据传输的数据传输. .前言：数据链路层的设计问题前言：数据链路层的设计问题1. 向网络层提供的服务向网络层提供的服务主机主机A主机主机BALTLNLDLPLALTLNLDLPL帧帧帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧无确认的无连接服务无确认的无连接服务有确认的无连接服务有确认的无连接服务面向连接的服务面向连接的服务前言：数据链路层的设计问题前言：数据链路层的设计问题 2. 成帧成帧w涉及的问题涉及的
3、问题w协议协议数据单元数据单元将上层将上层(网络层网络层)交下来的数据包按照所采用协议决交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧；定的格式，封装成一定形式的帧；考虑接收双方的同步问题（即定界）；考虑接收双方的同步问题（即定界）； 计算帧的校验和并放入帧中一起传送给接收方；计算帧的校验和并放入帧中一起传送给接收方；帧：在数据链路上交换数据的单位。帧：在数据链路上交换数据的单位。标标 志志字字 段段指明帧指明帧的开始的开始和结束和结束地址字段地址字段控制字段控制字段正文字段正文字段校验字段校验字段前言：数据链路层的设计问题前言：数据链路层的设计问题 2. 成帧成帧w字符计数法字符
4、计数法w字符填充的首尾定界法字符填充的首尾定界法w位填充的首尾定界法位填充的首尾定界法5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 35 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 3计数值传输出错时导致收发双方不同步计数值传输出错时导致收发双方不同步.同步字同步字符法符法标志法标志法填充技术填充技术前言：前言：数据链路层的设计问题数据链路层的设计问题2. 成帧成帧w物理层编码违例法物理层编码违例法w综合法综合法“0”“1”违例违例或或用用计数值确定帧尾计数值确定帧尾检查检查帧定界符是否出
5、现在应该出现的地方帧定界符是否出现在应该出现的地方计算校验和计算校验和前言：前言：数据链路层的设计问题数据链路层的设计问题 3. 流量控制流量控制w流量控制流量控制w流量控制的特点流量控制的特点网络层实体控制从数据链路层接收数据的速率，据此，网络层实体控制从数据链路层接收数据的速率，据此，数据链路层要控制从同等实体接收数据链路层要控制从同等实体接收PDU的速率。的速率。限制发送方发限制发送方发送速度的一种送速度的一种机制。使发送机制。使发送速率不能超过速率不能超过接收方能处理接收方能处理的速率。的速率。流量控制必须是动态的流量控制必须是动态的必须有某种反馈机制必须有某种反馈机制流量速度不仅与发
6、方流量速度不仅与发方速度相关而且与网络速度相关而且与网络的当前拥挤程度有关的当前拥挤程度有关使发方了解收方使发方了解收方的当前处理能力的当前处理能力前言：前言：数据链路层的设计问题数据链路层的设计问题 4. 差错控制差错控制w顺序到达顺序到达指保证所有的帧最终都按正确的发送次序到达目的。指保证所有的帧最终都按正确的发送次序到达目的。检错和纠错检错和纠错检出传输中出现的差错；可能的话确定出错位置从检出传输中出现的差错；可能的话确定出错位置从而纠正错误。而纠正错误。确认方式确认方式计时器法计时器法计时器值的设定要保证一帧计时器值的设定要保证一帧到达对方并作处理后，相应到达对方并作处理后，相应的确认
7、帧返回。的确认帧返回。ACK肯定确认肯定确认NAK否定确认否定确认计时结合序号才能保证每一帧的正确次序。计时结合序号才能保证每一帧的正确次序。前言：前言：数据链路层的设计问题数据链路层的设计问题5. 数据链路层协议的作用数据链路层协议的作用数据链数据链路协议路协议23数据链路进程数据链路进程路由选择进程路由选择进程路由器路由器A帧帧分组分组/包包2322 232路由器路由器B传输线传输线2322 223DL协议的作用就是使不可靠的协议的作用就是使不可靠的通信线路变得一定程度的好。通信线路变得一定程度的好。物理层: - 物理链路 - 比特流传输 - 有差错的物理链路数据链路层: - 数据链路 -
8、 帧传输 - 无差错的数据链路 - 数据链路层数据服务单元 - 帧一、数据链路层概述w数据链路层于物理层之上,属于低层。物理层传输的是比特流，单位是比特。w数据链路层传输单位是帧，一帧一帧地处理。其工作是从物理层获取比特流，进行封装成帧、并对帧进行如透明传输、差错控制等处理，从而递交给上一层（网络层），同时也对网络层下传的数据进行处理，进而传给物理层。数据链路层传送的是帧数据链路层传送的是帧IP 数据报数据报1010 0110帧帧取出取出数据数据链路层链路层网络层网络层链路链路结点结点 A结点结点 B物理层物理层数据数据链路层链路层结点结点 A结点结点 B帧帧(a)(b)发送发送帧帧接收接收链
9、路链路IP 数据报数据报1010 0110帧帧装入装入一、数据链路层概述一、数据链路层概述 分组分组与帧的关系图示与帧的关系图示Relationship between packets and frames一、数据链路层概述一、数据链路层概述 数据链路层的简单模型数据链路层的简单模型局域网局域网广域网广域网主机主机 H1主机主机 H2路由器路由器 R1路由器路由器 R2路由器路由器 R3电话网电话网局域网局域网主机主机 H1 向向 H2 发送数据发送数据链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层网络网络层
10、层物理物理层层链路层链路层网络网络层层物理物理层层链路层链路层网络网络层层物理物理层层R1R2R3H1H2从层次上来看数据的流动从层次上来看数据的流动一、数据链路层概述一、数据链路层概述数据链路层数据链路层的简单模型的简单模型局域网局域网广域网广域网主机主机 H1主机主机 H2路由器路由器 R1路由器路由器 R2路由器路由器 R3电话网电话网局域网局域网主机主机 H1 向向 H2 发送数据发送数据链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层网络网络层层物理物理层层链路层链路层网络网络层层物理物理层层链路层链
11、路层网络网络层层物理物理层层R1R2R3H1H2仅从数据链路层观察帧的流动仅从数据链路层观察帧的流动一、数据链路层概述一、数据链路层概述数据链路层协议在路由器中的位置数据链路层协议在路由器中的位置数据链数据链路协议路协议23数据链路进程数据链路进程路由选择进程路由选择进程路由器路由器A帧帧分组分组/包包2322 232路由器路由器B传输线传输线2322 223DL协议的作用就是使不可靠的协议的作用就是使不可靠的通信线路变得一定程度的好。通信线路变得一定程度的好。 一、数据链路层概述一、数据链路层概述1.常用概念常用概念w链路(link)：是一条无源的点到点的物理线路段，中间没有任何其他的交换结
12、点。n一条链路只是一条通路的一个组成部分。w数据链路(data link) ：除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。n现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。n一般的适配器都包括了数据链路层和物理层这两层的功能。w结点（node）：网络中的主机（host）和路由器（router）称为结点。 一、数据链路层概述一、数据链路层概述1.常用概念常用概念w链路（link）：通信路径上连接相邻结点的通信信道称为链路。w数据链路（data link)：链路+实现通信协议的硬件和软件。w数据链路层协议：定义了
13、一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。w端到端（end to end）与点到点（point to point）：n从源结点（source node）到目的结点（destination node）的通信称为端到端通信，通信路径（path）可能由多个链路组成。n在相邻结点间的一条链路上的通信称为点到点通信。w数据链路控制规程：为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。w早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。 w虚拟数据通路，实际数据通路 一、数据链路层概述一、数据链路层概述1.常用概念
14、常用概念 一、数据链路层概述一、数据链路层概述1.常用概念常用概念w数据链路层像个数字管道 w常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。结点结点结点结点帧帧帧帧 一、数据链路层概述一、数据链路层概述2.数据链路层使用的信道类型数据链路层使用的信道类型w数据链路层使用的信道主要有以下两种类型：n点对点信道点对点信道:这种信道使用一对一的点对点通信方式。 （例如PPP、SLIP）n广播信道广播信道:这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送 。（例如以太网） 一、数
15、据链路层概述一、数据链路层概述3.数据链路层协议基本功能数据链路层协议基本功能w链路管理数据在数据链路上的正常传输（建立、维护和释放）。w帧同步：数据传输的单位为帧，定界与同步。也处理透明性问题。w流量控制与顺序控制。w差错控制：前向纠错、差错检测，检错重发。w将数据和控制信息分开。w透明传输。w寻址。 二、差错检测与校正二、差错检测与校正1.基本概念基本概念w什么是差错？n在通信中接收端收到的二进制数位（码元）和发送端实际发送的数据不一致。w差错检测与校正：把差错控制在允许的范围内。w差错控制的主要内容：n差错编码、反馈重传、超时重传、重复帧丢弃、定时器管理等。 二、差错检测与校正二、差错检
16、测与校正1.基本概念基本概念w误码率：衡量物理信道的质量.w差错控制编码：信息位(k)冗余位(r)w检错码：自动发现差错w纠错码：不仅能发现差错而且能够自动纠正w编码效率R：码字中信息位所占的比例 R=k/(k+r)w漏检率：信息位出错但是接收者无法了解到的概率 二、差错检测与校正二、差错检测与校正2.差错与校正概念差错与校正概念w出错的类型n单个错：由随机的信道热噪声引起，一次只影响1位；n突发错：由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。w编码的类型n检错码：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来使用以便进行差错恢复；n纠错
17、码：不权能够检测到数据传输发生了错误，而且能够自行纠正错误。 二、差错检测与校正二、差错检测与校正2.差错与校正概念差错与校正概念w码字（codeword）：由m比特的数据（消息）加上r比特的冗余（校验位）构成；w有效编码集：由2m个有效码字组成；w检错：当收到的码字为无效码字时检测出错误；w海明距离（Hamming Distance）：两个码字的对应位上取值不同的位数；w纠错：将收到的无效码字纠正到距其最近的有效码字；w检错码与纠错码的能力都是有限的。 二、差错检测与校正二、差错检测与校正2.差错与校正概念差错与校正概念w编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。w检错能
18、力：为检测出d比特错误，编码集的海明距离至少应为d+1；奇偶校验是能够检测出1比特错误的检错码。w纠错能力：为纠正d比特错误，编码集的海明距离至少应为2d+1；海明码是能够纠正1比特错误的纠错码。 二、差错检测与校正二、差错检测与校正2.差错控制与校正方法差错控制与校正方法w差错控制：ARQ和FECnARQ（自动重传请求）lAutomatic Request for Repeatl接收方检测错误，通知发送方重传l双向信道，发送方缓存发送的数据nFEC（前向纠错）lForward Error Correctionl接收方不仅可以检测错误，而且知道错误的位置，从而改正错误l采用纠错码，无需反向信道
19、，无需重发，但编码效率低,纠错设备复杂 二、差错检测与校正！二、差错检测与校正！3.差错检测与校正和流量控制差错检测与校正和流量控制由于系统性能的不同，如硬件能力（包括由于系统性能的不同，如硬件能力（包括CPU，存储器等）和软件存储器等）和软件功能的差异，会导致发送方与接收方处理数据的能力有所不同。功能的差异，会导致发送方与接收方处理数据的能力有所不同。流量控制的作用是使发送方所发出的数据流量，使其发送速率不要流量控制的作用是使发送方所发出的数据流量，使其发送速率不要超过接收方所能接收的速率。超过接收方所能接收的速率。流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收流量控制的关键是需
20、要有一种信息反馈机制，使发送方能了解接收方是否能接收到方是否能接收到存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协议则将关于帧的确认与流量控制巧妙地结合在了一起。议则将关于帧的确认与流量控制巧妙地结合在了一起。w流量控制的主要机制：n基于反馈的流量控制（）n基于速率的流量控制二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（奇偶校验码）常用的简单差错控制编码（奇偶校验码）w奇偶校验码：增加冗余位使得码字中1的个数为奇数或者偶数，检错码n垂直奇偶校验n水平奇偶校验n水平垂直奇偶校验w垂直奇偶校验：n发送的信息块分
21、成定长为p位的若干段（一列）。n每段增加一个（奇偶校验）冗余位ri ：二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（垂直奇偶校验）常用的简单差错控制编码（垂直奇偶校验）w垂直奇偶校验n编码效率：n能力：l检测出每列（段）中所有奇数（1、3）个错l突发错误的漏检率为50%!l在发送和接收的过程中进行编解码w水平奇偶校验：降低突发错误的漏检率n对各个信息段的相应位横向进行编码二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平奇偶校验）常用的简单差错控制编码（水平奇偶校验）w水平奇偶校验n编码效率：n能力：l各段同一位上的奇数个错l长度小于等于p的突发差错l编码和
22、检测相比垂直校验而言实现要复杂一些二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）常用的简单差错控制编码（水平垂直奇偶校验）w水平垂直奇偶校验 编码效率二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）常用的简单差错控制编码（水平垂直奇偶校验）w水平垂直奇偶校验能力n检测出：l所有3位或3位以下的错误、奇数位错l突发长度小于等于p+1的突发差错l很大一部分偶数位错：差错分布以致于某一行或者某一列有奇数个差错n部分纠错功能：l可以纠正1比特错w信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处二、差错检测与校正
23、二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）常用的简单差错控制编码（水平垂直奇偶校验）10001010字符字符1b1b2b3b4b5b6b7check11001011字符字符211011010字符字符310101011字符字符410001010字符字符510001010字符字符611101010字符字符700100001校验校验字符字符w水平垂直奇校验的例子二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（海明码）常用的简单差错控制编码（海明码）1. 海明码(1)海明距离及意义两个码字中不同的位数的个数称为海明距离,简称H距离 1 0 0 0 1 0 0 1
24、1 0 1 1 0 0 0 1求H距离的方法主要有:异或运算海明距离的意义是:假如两个码字具有海明距离d ,则需要d 个位差错才能将其中一个码字转换成另一个.H=3二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w纠错码的编码效率较低，差错控制经常采用检错码ARQ。循环冗余码CRC（Cyclic Redundancy Code ）是计算机网络中使用最为广泛的检错码，又称为多项式码。三、关于数据帧w数据链路层所传送的不再是原始的比特流，而应具备相应的语法和语义，以达到可靠传输的功能。w数据链路层将从网络层接收的分组（Packe
25、t)组成帧后传送给物理层，通过物理层传送到对方的数据链路层。w帧：数据链路层规定最小的数据传送逻辑单位w数据链路层协议要规定帧的类型与格式类型包括控制信息帧与数据信息帧等，格式则规定帧所包含的域）。3.1 帧的基本组成w帧定界（开始与结束） w地址字段（用于寻址） w帧类型（或长度/控制）字段w数据w帧校验字段（差错控制）上图只是帧的一般组成，不同的数据链路层协议所规定的帧格式可能会与其存在微小的区别。3.2 帧的同步同步就是标识帧的开始与结束同步就是标识帧的开始与结束常用的帧同步方法：常用的帧同步方法：字符计数法字符计数法带字符填充的首尾界符法带字符填充的首尾界符法带位填充的首尾标志法带位填
26、充的首尾标志法违例编码法违例编码法字符计数法计数计数计数第第1帧帧5个字符个字符第第2 2帧帧5个字符个字符第第3 3帧帧8个字符个字符发送发送: :接收接收: :第第1 帧正确帧正确! !第第2 帧不正确帧不正确! !7出错! 11个字符计数?首尾界符法w每一帧以ASCII字符序列DLE STX开始，以DLE ETX结束。wDLE为Data Link Escape 的缩写，STX意味着Start of Text， ETX代表 End of Text。w其缺点是成帧完全依赖于8位字符数据数据组帧组帧字符填充w在首尾界符法中，由于数据中可能会出现DLE STX或DLE ETX，从而干扰帧的正常定
27、界w字符填充法可用于解决上述问题。即发送端在数据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。网络层发出的数据网络层发出的数据经数据链路层填充后的数据经数据链路层填充后的数据字节填充图例(a) A frame delimited by flag bytes(b) Four examples of byte sequences before and after stuffing.首尾标记法w每一帧使用一个特殊的位模式“01111110”作为开始和结束标记。w该位模式又称为flagw位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。位填充w在首
28、尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界w位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1”时，则在其后自动插队入一个“0”。该技术简称“逢五1插0”；接收端则忽略5个连续的“1”后面的“0”，简称“逢五1删0” 。(a)0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 (b)(b) 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0(c)(c) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 填充的
29、位填充的位比特填充图例(a) The original data.(b) The data as they appear on the line.(c) The data as they are stored in receivers memory after destuffing.违例编码法n采用不可能出现在信息位中的比特编码作为帧的起始边界。l在物理层采用特定的比特编码方法时使用l曼彻斯特编码中电平的跳变表示1（低-高）和0（高-低）l高高和低低电平是违例编码四、数据链路层协议 数据链路通信的简单模型完全理想化的数据传输完全理想化的数据传输基于以下两个假定w假定1：链路是理想的传输信道，所
30、传送的任何数据既不会出差错也不会丢失。w假定2： 不管发送方以多快的速率发送数据，接收方总来得及收下，并及时上交主机。(接收端向主机交付的数据速率永远不会低于发送端发送数据的速率)4.1 停等协议w停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。l具有最简单流量控制的数据链路层协议l仍保留假定1，但去掉假定2 w链路是理想的传输信道，即所传送的任何数据既不会出差错也不会丢失w由接收方控制发送方的数据流(计算机网络中流量控制的一个基本方法)。停等协议算法w在发送结点：在发送结点：（1）从主机取一个数据帧；（2）将数据帧送到数据链路层的发送缓存；（3）将发送缓存中的
31、数据帧发送出去；（4）等待；（5）若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到（2）。w在接收结点：在接收结点：（1）等待；（2）若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存；（3）将接收缓存中的数据帧上交主机；（4）向发送结点发一信息，表示数据帧已经上交给主机；（5）转到(1)。停等协议w两种数据传输比较从从主主机机取取数数据据上上交交主主机机DATA1DATA4DATA3DATA2结点结点A结点结点B 理想信道理想信道从从主主机机取取数数据据上上交交主主机机DATA1DATA2结点结点A结点结点BACKACK 具
32、有简单流量控制具有简单流量控制的数据链路层协议的数据链路层协议从从主主机机取取数数据据上上交交主主机机DATA1DATAnDATA2结点结点A结点结点BDATAn+3DATAn+2DATAn+1NAKn+1 ACK 流水线协议流水线协议实用的停止等待协议w前提：去掉两个假定，即传输数据的信道不能保证使所传的数据不产生差错，而且还需对数据的发送端进行流量控制。w流量控制方法：等待发送w差错控制：发送方数据帧中加入校验码（CRC），由接收方检查；若正确，返回ACK，若出错，返回NAK；发送方根据收到的返回帧，决定发送新帧和重发。w帧丢失处理：超时定时器；以序号标识数据帧 w优点：简单w缺点：信道利
33、用率低，信道还远远没有被数据比特填滿数据帧在链路上传输的几种情况Data0Data1ACKACKAB时时间间送送主主机机送送主主机机Data0Data0ACKToutACK丢失丢失AB重传重传送送主主机机放放弃弃 (a)正常情况正常情况 (b)数据帧出错数据帧出错 (C)数据帧丢失数据帧丢失 (d)确认帧丢失确认帧丢失Data0Data0NAKACKAB出错出错重重传传送送主主机机重传重传Data0Data0ACK丢失丢失ABTout送送主主机机实用停止等待协议的算法w在发送结点：在发送结点：(1)从主机取一个数据帧，送交发送缓存。(2)v(S)0。 (发送状态变量v(S)初始化)(3)N(S
34、)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)若超时计时
35、器时间到，则转到(4)。 (重传已发送的数据帧)停止等待协议的算法w在接收结点在接收结点：(1)v(R)0。 (接收状态变量初始化，其数值等于欲接收的数据帧的发送序号(2)等待。(3)收到一个数据帧： (这里隐含地表示已经通过了CRC的硬件差错检测) 若N(s)=v(R)，则执行(4)； (收到正确序号的数据帧) 否则丢弃此数据帧，然后转到(6)。 (丢弃的帧就是重复帧)(4)将收到的数据帧中的数据部分送交上层软件。(5)v(R)1-v(R)。 (更新接收状态变量，准备接收下一个数据帧)(6)nV(R)； 发送确认帧ACKn，转到(2)。 (期望接收n号数据帧，在它之前的帧收到了)停止等待协议
36、的算法停止等待协议的算法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设置
37、的重传时间tout停等协议的信道利用率发送方接收方Ack帧数据帧2RL/B时间T(sec)B为信道容量(b/s)R为单程传播延迟时间(s)L为数据帧长度(bits)U为信道利用率4.2 Go-back-N连续ARQ协议w工作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送。接收方只允许顺序接收，也就是说如果一帧出错，则它后面的N帧尽管可能正确到达接收方，但被直接丢弃，不发送确认。发送方将超时，按序重传所有未被确认的帧。w优点：连续发送提高了信道利用率w缺点： 导致某些已正确接收的帧的重传，因此降低了发送效率w误码率较低时，
38、连续ARQ优于停等协议；反之则不一定Go-back-N连续ARQ协议Go-back-N ARQ4.3 滑动窗口(Sliding Window)的概念w发送窗口用来对发送端进行流量控制发送窗口用来对发送端进行流量控制，而发送窗口的大，而发送窗口的大小小WT就代表就代表在还没有收到对方确认信息的情况下发送在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧端最多可以发送多少个数据帧。发送窗口的规则如下：（1）发送窗口内的帧是允许发送的帧，而不考虑有没有收到确认。发送窗口右侧所有的帧都是不允许发送的帧。图4-7(a)说明了这一情况。（2）每发送完一个帧，允许发送的帧数就减1。但发送窗口的位
39、置不变。图4-7(b)说明已经发送了0号帧，因此允许发送的帧数就少了一个，即只有4个。（3）如果所允许发送的5个帧都发送完了，但还没有收到任何确认，那么就不能再发送任何帧了。图4-7(c)表示这种情况。这时，发送端就进入等待状态。（4）每收到对一个帧的确认，发送窗口就向前(即向右方)滑动一个帧的位置。图4-7(d)表示发送端已经收到了0, 1和2号帧共3个帧的确认，因此发送窗口可以向前滑动3个帧的位置。于是，发送端现在又可以继续发送3个帧(即5 7号帧)。接收窗口的规则w在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。接收窗口的规则很简单，归纳如下：（1）只有当收到的帧
40、的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。（2）每收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。同时向发送端发送对该帧的确认。w图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收收ACK1wWT=2 WR=1 的滑动窗口4.4 选择重传
41、ARQ协议w原则：只重传出错或定时器超时的数据帧w方法：WR 1，暂存接受窗口中序号在出错帧之后的数据帧w优点：避免重传已正确传送的帧，提高了信道利用率w缺点：在接收端需要占用一定容量的缓存选择重传ARQ协议接收窗口的最大值受下式约束：接收窗口的最大值受下式约束： WR 2n /2 当接收窗口当接收窗口WR为最大时，为最大时，WT=WR=2n /2。4.5 数据链路层协议分类w面向字符的链路层协议lISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM）lIBM的二进制同步通信规程（BSC）lDEC的数字数据通信报文协议（DDCMP）lPPPn面向比特的链路层协议lIBM的SNA使
42、用的数据链路协议SDLC（Synchronous Data Link Control protocol）；lANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure）；lISO修改SDLC，提出HDLC（High-level Data Link Control）；lCCITT修改HDLC，提出LAP（Link Access Procedure）作为X.25网络接口标准的一部分，后来改为LAPB。4.5.1 面向字符型协议实例：BSCw什么是面向字符型协议?w 以字符为控制传输信息的基本单元w ASIIC码： 格式字符：SO
43、H（start of heading） STX（start of text） ETB（end of transmission block） ETX（end of text） 控制字符：ACK（acknowledge） NAK（negative acknowledge） ENQ（enquire） EOT（end of transmission） SYN（synchrous） DLE（data link escape）面向字符型协议实例：BSC面向字符型协议实例：BSC4.5.2 面向比特型协议实例：HDLC面向字符型数据链路层协议的缺点：面向字符型数据链路层协议的缺点：w报文格式不一样；w不同字
44、符集机器难以通信w传输透明性不好；w等待发送方式，传输效率低。面向比特型协议的设计目标：面向比特型协议的设计目标：w以比特作为传输控制信息的基本单元；w数据帧与控制 帧格式相同；w传输透明性好；w连续发送，传输效率高。4.5.2 面向比特型协议实例：HDLC帧类型及控制字段的意义帧类型wI帧 ： N（S） 发送帧的顺序号w N（R） 接收帧的顺序号w P/F= Poll / Final， P=1 询问，F=1 响应w P与F成对出现wS帧 ： 监控功能位w S = 00，RR（receive ready）w S = 10，RNR（receive not ready）w S = 01，RJE（r
45、eject）w S = 11，SREJ（select reject）wU帧 ： 用于实现数据链路控制功能U帧的格式与链路控制功能控制字段格式Control field of (a) An information frame.(b) A supervisory frame.(c) An unnumbered frame.六、Internet中主要的数据链路层协议wSLIP （Serial Line IP） 串行线路的Internet数据链路层协议wPPP （ Point-to-Point Protocol） 点-点协议wSLIP与PPP用于串行通信的拨号线路上，是目前家庭计算机或公司用户通过IS
46、P接到Internet主要的协议。SLIP协议wSLIP出现于20世纪80年代初，最早是在BSD UNIX 4.2版操作系统上实现的;wSLIP协议支持TCP/IP协议;w对数据报进行了简单的封装，然后来用RS-232接口串行线路进行传输;wSLIP通常也用来将远程终端连接到UNIX主机，也可通过租用或拨号串行线路进行主机到路由器，以及路由器到路由器的通信。典型的SLIP接入方式wInternet的家庭或小型公司用户通过调制解调器、电话网络连接到ISP的调制解调器；wISP的调制解调器再通过它的路由器接入Internet；wSLIP系统一般可以发送和接收1006B的IP数据报。SLIP协议的帧
47、结构wRFC 1055文件对SLIP帧格式进行了讨论;wSLIP帧头与帧尾的“CO”，是协议使用的惟一的一个控制字符;wCO的二进制编码比特序列是1000011 0000000;wCO的使用将影响SLIP帧数据的透明性; SLIP协议的缺点w使用SLIP协议时，通信的双方都必须知道对方的IP地址，因为SLIP协议没有为它们提供相互交换地址信息的方法；w没有设置协议类型字段，不具备同时处理多种网络层协议的能力；w没有校验和字段，差错控制功能由高层的协议承担；wSLIP协议并不是Internet的协议标准，因此不同版本的之间就会存在着差别，使得互连变得困难。PPP协议基本特点wPPP协议是Inte
48、rnet标准，RFC 1660、RFC 1661定义了PPP协议与帧结构；wPPP协议处理了差错检测，支持面向字符型协议与面向比特型协议,可以支持IP协议及其他一些网络层协议（例如IPX协议）；wPPP协议不仅在拨号电话线，并且在路由器路由器之间的专用线上广泛应用;wPPP协议是在大多数家庭个人计算机和ISP之间使用的协议，它可以作为在高速广域网和社区宽带网协议族的一部分。PPPwPPP是因特网中广泛使用的点-点数据链路协议；wPPP由以下三部分组成：n一种组帧的方式，用于区分帧的边界，并可支持差错检测；n一个链路控制协议（LCP） ，用于链路的建立、测试、协商及拆除；n一组网络控制协议（NC
49、P），用于支持多种网络层协议；特别是支持IP的NCP可支持IP地址的动态分配。 PPP（续）w使用PPP通信的过程：n首先在两个modem之间建立物理连接；n然后使用LCP建立链路；n然后使用NCP配置网络层，特别是支持IP的NCP会向ISP申请分配一个IP地址；n这时PC就在Internet上了；n完成工作后首先使用NCP拆除网络层连接，释放IP地址；n然后使用LCP关闭数据链路层连接；n最后释放物理连接。PPP（续）wPPP的帧格式：nPPP是面向字符的，因此采用字符填充技术，且帧长都是字节的整数倍，但PPP也能在面向比特的线路（如HDLC）上使用；n地址总是设成11111111，可以免去
50、数据链路地址的分配；n控制缺省为00000011，即缺省时采用不可靠无编号的数据传输方式，但需要时也可以协商采用可靠的有编号的数据传输方式；n增加了协议域，用于指出载荷字段中携带的是哪类分组，从而可以支持LCP、NCP及不同的网络层协议；n许多字段的长度是可以协商的，而且支持头部压缩。PPP信息帧格式PPP与HDLC帧格式(a) PPP帧格式(b) HDLC帧格式PPP链路链路 up / down 过程（简单状态图）过程（简单状态图）PPP 协议的状态图 建立失败失败NCP 配置鉴别成功通信结束载波停止检测到 载波双方协商一些选项鉴别网络打开终止静止链路控制帧（LCP）与网络控制帧（NCP）w链路控制帧（LCP）w网络控制帧（NCP）
