CH3 数据链路层-新背景.ppt

计算机网络第 3 章 数据链路层课件制作人：谢希仁第 3 章 数据链路层*3.1 数据链路层的基本概念*3.2 停止等待协议3.2.1 完全理想化的数据传输3.2.2 具有最简单流量控制的数据链路层协议3.2.3 实用的停止等待协议3.2.4 循环冗余检验的原理3.2.5 停止等待协议的算法3.2.6 停止等待协议的定量分析课件制作人：谢希仁第 3 章 数据链路层（续）*3.3 连续 ARQ 协议3.3.1 连续 ARQ 协议的工作原理3.3.2 连续 ARQ 协议的吞吐量3.3.3 滑动窗口的概念3.3.4 信道利用率与最佳帧长3.4 选择重传 ARQ 协议课件制作人：谢希仁第 3 章 数据链路层（续）*3.5 面向比特的链路层协议 HDLC3.5.1 HDLC 协议概述3.5.2 HDLC 的帧结构*3.6 因特网的点对点协议 PPP 3.6.1 PPP 协议的工作原理 3.6.2 PPP 协议的帧格式 3.6.3 PPP 协议的工作状态课件制作人：谢希仁3.1 数据链路层的基本概念 n数据电路n是一条通信双方的物理电路段，中间不含任是一条通信双方的物理电路段，中间不含任何交换节点何交换节点;是是在线路或信道上加信号变换在线路或信道上加信号变换设备之后所形成的二进制比特流通路设备之后所形成的二进制比特流通路,由传由传输信道加输信道加DCE组成。组成。n数据链路n具备逻辑上的控制关系具备逻辑上的控制关系,=数据电路数据电路+规程规程n一条物理链路可以构成多条数据链路(采用复用技术时)课件制作人：谢希仁 数据网Modem分组交换机分组交换机 DTEDCEDTE信道信道数据电路数据电路数据链路数据链路数据电路数据电路：在线路或信道两端加上信号变换设备（如：在线路或信道两端加上信号变换设备（如ModemModem）之后所形成的二进制比特流通路。即数据电路由之后所形成的二进制比特流通路。即数据电路由传输信道加传输信道加DCEDCE组成。组成。数据链路数据链路：在数据电路已建立的基础上，在链路协议的：在数据电路已建立的基础上，在链路协议的控制下，使通信双方可开始传输数据的控制下，使通信双方可开始传输数据的终端设备终端设备与与传输传输线路线路的组合体。的组合体。DCEModemModem课件制作人：谢希仁n数据链路与数据电路n数据电路又可称为数据电路又可称为物理链路物理链路或或链路链路n数据链路又称为数据链路又称为逻辑链路逻辑链路n数据链路是在数据电路上增加传输控制功能实现的。n只有建立了数据链路，才能真正地实现数据通信。课件制作人：谢希仁n物理链路的基本结构n点到点链路点到点链路:主站发信息或命令主站发信息或命令;从站发确认从站发确认或响应或响应;复合站兼有主从站功能复合站兼有主从站功能n多点链路多点链路:一站为控制站一站为控制站,其余各站为受控站其余各站为受控站n数据链路层的传送方式：n单工通信单工通信n半双工通信半双工通信(Half Duplex)n全双工通信全双工通信(Full Duplex)HHHHHH点点-点链路点链路多点链路多点链路课件制作人：谢希仁数据链路层目标与主要功能目标：n屏蔽物理层不同的通信环境和条件，向高层提供可靠几乎无差错、透明的逻辑信道。主要功能：n成帧控制：用帧格式来分割和调节物理层比特流的传送，以便于数据的传送处理（缓冲准备）和差错控制。帧定界 帧同步n编址：点到点；多点链接须保证每一帧都能送到正确的地址.课件制作人：谢希仁数据链路层像个数字管道 n常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。n早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。结点结点帧帧课件制作人：谢希仁数据链路层目标与主要功能n流量控制流量控制n现代数据通信的交换方式现代数据通信的交换方式,采用了存储转发的分组采用了存储转发的分组交换技术，交换技术，要求发送方的发送数据速率必须不能超要求发送方的发送数据速率必须不能超过接收方的接收和处理数据的速率。过接收方的接收和处理数据的速率。当接收方来不当接收方来不及接收和处理数据时，就必须采取相应的措施来控及接收和处理数据时，就必须采取相应的措施来控制发送方发送数据的速率。制发送方发送数据的速率。流量控制是一种使目的流量控制是一种使目的端实体可以调节源端实体发出端实体可以调节源端实体发出PDU流量流量的协议机制。的协议机制。限制数据发送的数量或速率。限制数据发送的数量或速率。n通过采用应答机制来调节通信双方在处理能力上的通过采用应答机制来调节通信双方在处理能力上的差异。通常是使用窗口技术来控制数据的传输节奏，差异。通常是使用窗口技术来控制数据的传输节奏，以调节通信双方的缓冲区的使用。以调节通信双方的缓冲区的使用。课件制作人：谢希仁数据链路层目标与主要功能n差错控制n用途用途:处理处理PDUPDU丢失或损坏情况丢失或损坏情况n若采用若采用检错编码检错编码,则收方能够发现传输中出现的差则收方能够发现传输中出现的差错错,通过检错重发和超时重发进行差错控制通过检错重发和超时重发进行差错控制。重发重发分为应答重发分为应答重发(被动纠错被动纠错)和超时重发和超时重发(主动纠错主动纠错)n若采用若采用纠错编码纠错编码,则收方收到有差错数据帧时则收方收到有差错数据帧时,能够能够发现差错并能自动加以改正发现差错并能自动加以改正,但但开销较大开销较大,适于使用适于使用卫星中继的计算机通信卫星中继的计算机通信.n差错控制和流量控制通常在一个单一的机制中一起差错控制和流量控制通常在一个单一的机制中一起实现实现,也可以在多种协议级别上实现。也可以在多种协议级别上实现。课件制作人：谢希仁数据链路层目标与主要功能n数据和控制信息的识别n在同一帧中，在同一信道中传送。帧格式在同一帧中，在同一信道中传送。帧格式n透明传输n不管所传数据是什么样的比特组合不管所传数据是什么样的比特组合,即使与即使与某一控制信息完全一样也可以某一控制信息完全一样也可以,都能在物理都能在物理链路上传送链路上传送.且保证收方不会误判且保证收方不会误判.n链路管理n数据链路的建立、维持和释放过程数据链路的建立、维持和释放过程.课件制作人：谢希仁链路控制机制n三种常用的流量及差错控制技术n停等协议停等协议nGo-back-N(连续连续ARQ)n选择重传选择重传ARQ Selective RepeatSelective Repeat后两种是滑动窗口技术的两个特例后两种是滑动窗口技术的两个特例课件制作人：谢希仁3.2 停止等待协议n3.2.1 完全理想化的数据传输n先研究一下数据链路层的模型。先研究一下数据链路层的模型。课件制作人：谢希仁数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动课件制作人：谢希仁数据链路层的简单模型(续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动课件制作人：谢希仁3.2 停止等待协议3.2.1 完全理想化的数据传输数据链路层主机 A缓存主机 B数据链路AP2AP1缓存发送方接收方帧高层帧课件制作人：谢希仁完全理想化的数据传输所基于的两个假定 n假定 1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。n假定 2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。n这个假定就相当于认为：接收端向主机交这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数付数据的速率永远不会低于发送端发送数据的速率。据的速率。课件制作人：谢希仁3.2.2 具有最简单流量控制的数据链路层协议n现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机 A 向主机 B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。n当接收方的处理能力小于发送方的发送当接收方的处理能力小于发送方的发送量时，必须采用流量控制。量时，必须采用流量控制。n n由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法在发送结点：(1)从主机取一个数据帧。(2)将数据帧送到数据链路层的发送缓存。(3)将发送缓存中的数据帧发送出去。(4)等待。(5)若收到由接收结点发过来的信息(此信息 的格式与内容可由双方事先商定好)，则 从主机取一个新的数据帧，然后转到(2)。课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法（续）在接收结点：(1)等待。(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。(3)将接收缓存中的数据帧上交主机。(4)向发送结点发一信息，表示数据帧已 经上交给主机。(5)转到(1)。课件制作人：谢希仁n具有最简单流量控制的具有最简单流量控制的L2协议算法协议算法v发方算法发方算法1.1.从主机取一个数据帧从主机取一个数据帧2.2.送入送入L2L2的发送缓存的发送缓存3.3.将缓存中的数据帧发出去将缓存中的数据帧发出去4.4.等待直至收到接收结点发过等待直至收到接收结点发过来的信息来的信息5.5.从主机取一个新的数据帧从主机取一个新的数据帧6.6.转转2.2.v收方算法收方算法1.1.等待直至收到发来的数据帧等待直至收到发来的数据帧2.2.放入放入L2L2的接收缓存的接收缓存,上交主机上交主机3.3.向发方发信息向发方发信息4.4.转转1.1.课件制作人：谢希仁两种情况的对比（传输均无差错）ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 BABDATA送主机 BDATA送主机 B时间不需要流量控制需要流量控制课件制作人：谢希仁3.2.3 实用的停止等待协议时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况ABDATA0DATA0送主机ACK(c)数据帧丢失重传tout丢丢失失！ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失重传tout丢失！ABDATA0NAKDATA0送主机ACK(b)数据帧出错重传出错四种情况课件制作人：谢希仁超时计时器的作用n结点A发送完一个数据帧时，就启动一个超时计时器(timeout timer)。n计时器又称为计时器又称为定时器定时器。n若到了超时计时器所设置的重传时间 tout而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。n一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。n重传若干次后仍不能成功，则报告差错。课件制作人：谢希仁解决重复帧的问题 n如果是接收方的应答帧丢失，会导致发送方重复发送，出现重复帧。n使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1模2。n若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。n但此时结点 B 还必须向 A 发送确认帧 ACK，因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。课件制作人：谢希仁帧的编号问题 n任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。n序号占用的比特数越少，数据传输的额外开销就越小。n对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。n一个比特可表示一个比特可表示 0 和和 1 两种不同的序号。两种不同的序号。课件制作人：谢希仁帧的发送序号 n数据帧中的发送序号 N(S)以 0 和 1 交替的方式出现在数据帧中。n每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。课件制作人：谢希仁可靠传输 n虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。课件制作人：谢希仁3.2.4 循环冗余检验的原理 n在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。n假设待传送的数据 M=1010001101（共k bit）。我们在M的后面再添加供差错检测用的 n bit 冗余码一起发送。课件制作人：谢希仁冗余码的计算 n用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。n得到的(k+n)bit 的数除以事先选定好的长度为(n+1)bit 的数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 至少要少1 个比特。课件制作人：谢希仁冗余码的计算举例 n设 n=5,P=110101，模 2 运算的结果是：商 Q=1101010110，余数R=01110。n将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2nM+R。课件制作人：谢希仁 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数循环冗余检验的原理说明 课件制作人：谢希仁帧检验序列 FCS n在数据后面添加上的冗余码称为帧检验序列 FCS(Frame Check Sequence)。n循环冗余检验 CRC 和帧检验序列 FCS并不等同。nCRC 是一种常用的是一种常用的检错方法检错方法，而，而 FCS 是添是添加在数据后面的加在数据后面的冗余码冗余码。nFCS 可以用可以用 CRC 这种方法得出，但这种方法得出，但 CRC 并非用来获得并非用来获得 FCS 的惟一方法。的惟一方法。课件制作人：谢希仁检测出差错 n只要得出的余数 R 不为 0，就表示检测到了差错。n但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。n一旦检测出差错，就丢弃这个出现差错的帧。n只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。课件制作人：谢希仁应当注意 n仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。n“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。n也就是说：“凡是接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。n要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。课件制作人：谢希仁3.2.5 停止等待协议的算法n这里不使用否认帧（实用的数据链路层协议大都是这样的），而且确认帧带有序号 n。n按照习惯的表示法，ACKn 表示“第 n 1 号帧已经收到，现在期望接收第 n 号帧”。nACK1 表表示示“0 号号帧帧已已收收到到，现现在在期期望望接接收收的的下下一一帧是帧是 1 号帧号帧”；nACK0 表表示示“1 号号帧帧已已收收到到，现现在在期期望望接接收收的的下下一一帧是帧是 0 号帧号帧”。课件制作人：谢希仁在发送结点(1)从主机取一个数据帧，送交发送缓存。(2)V(S)0。(3)N(S)V(S)。(4)将发送缓存中的数据帧发送出去。(5)设置超时计时器。(6)等待。等待以下(7)和(8)这两个事件中最先出现的一个(7)收到确认帧 ACKn，若 n=1 V(s)，则：从主机取一个新的数据帧，放入发送缓存；V(S)1 V(S)，转到(3)。否则，丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到(4)。课件制作人：谢希仁在接收结点(1)V(R)0。(2)等待。(3)收到一个数据帧；若 N(S)=V(R)，则执行(4)；否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件 （也就是数据链路层模型中的主机）。(5)V(R)1 V(R)。(6)nV(R)；发送确认帧 ACKn，转到(2)。课件制作人：谢希仁停止等待协议的要点n只有收到序号正确的确认帧 ACKn 后，才更新发送状态变量 V(S)一次，并发送新的数据帧。n接收端接收到数据帧时，就要将发送序号 N(S)与本地的接收状态变量 V(R)相比较。n若若二二者者相相等等就就表表明明是是新新的的数数据据帧帧，就就收收下下，并并发发送送确认。确认。n否否则则为为重重复复帧帧，就就必必须须丢丢弃弃。但但这这时时仍仍须须向向发发送送端端发发送送确确认认帧帧 ACKn，而而接接收收状状态态变变量量 V(R)和和确确认认序序号号 n 都不变。都不变。课件制作人：谢希仁停止等待协议的要点（续）n连续出现相同发送序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧，表明接收端收到了重复帧。n发送端在发送完数据帧时，必须在其发送缓存中暂时保留这个数据帧的副本。这样才能在出差错时进行重传。只有确认对方已经收到这个数据帧时，才可以清除这个副本。课件制作人：谢希仁停止等待协议的要点（续）n实用的 CRC 检验器都是用硬件完成的。nCRC 检验器能够自动丢弃检测到的出错帧。因此所谓的“丢弃出错帧”，对上层软件或用户来说都是感觉不到的。n发送端对出错的数据帧进行重传是自动进行的，因而这种差错控制体制常简称为 ARQ(Automatic Repeat reQuest)，直译是自动重传请求，但意思是自动请求重传。课件制作人：谢希仁3.2.6 停止等待协议的定量分析n设 tf 是一个数据帧的发送时间，且数据帧的长度是固定不变的。显然，数据帧的发送时间 tf 是数据帧的长度 lf(bit)与数据的发送速率 C(bit/s)之比，即 tf=lf/C=lf/C(s)（3-1）n发送时间 tf 也就是数据帧的发送时延。n数据帧沿链路传到结点B还要经历一个传播时延 tp。n结点 B 收到数据帧要花费时间进行处理，此时间称为处理时间 tpr，发送确认帧 ACK 的发送时间为 ta。课件制作人：谢希仁停止等待协议中数据帧和确认帧的发送时间关系 ABDATADATAACK传播时延 tp处理时间 tpr确认帧发送时间 ta传播时延 tp处理时间 tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout课件制作人：谢希仁重传时间 n重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。n为方便起见，我们设重传时间为 tout=tp+tpr+ta+tp+tpr (3-2)n设上式右端的处理时间 tpr 和确认帧的发送时间 ta 都远小于传播时延 tp，因此可将重传时间取为两倍的传播时延，即 tout=2tp (3-3)课件制作人：谢希仁简单的数学分析 n两个发送成功的数据帧之间的最小时间间隔是 tT=tf+tout=tf +2tp (3-4)n设数据帧出现差错(包括帧丢失)的概率为 p，但假设确认帧不会出现差错。n设正确传送一个数据帧所需的平均时间 tav tav=tT(1+一个帧的平均重传次数)课件制作人：谢希仁简单的数学分析（续）一帧的平均重传次数 =1 P重传次数为 1+2 P重传次数为 2+3 P重传次数为 3+=1 P第 1 次发送出错 P第 2 次发送成功 +2 P第 1,2 次发送出错 P第 3 次发送成功 +3 P第 1,2,3 次发送出错 P第 4 次发送成功+=p(1 p)+2p2(1 p)+3p3(1 p)+这里 PX 是出现事件 X 的概率。课件制作人：谢希仁简单的数学分析（续）得出正确传送一个数据帧所需的平均时间：当传输差错率增大时，tav 也随之增大。当无差错时，p=0,tav=tT。(3-5)课件制作人：谢希仁简单的数学分析（续）每秒成功发送的最大帧数就是链路的最大吞吐量 max。显然，max=1/tav=(1 p)/tT (3-6)在发送端，设数据帧的实际到达率为，则不应超过最大吞吐量 max，即 (1 p)/tT (3-7)用时间 tf 进行归一化，得出归一化的吞吐量 为 tf (1 p)/1 (3-8)其中参数 是 tT 的归一化时间：tT/tf 1 (3-9)当重传时间远小于发送时间时，1，此时的归一化吞吐量 1 p (3-10)课件制作人：谢希仁停止等待协议 ARQ 的优缺点 n优点：比较简单。n缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。n为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传 ARQ。课件制作人：谢希仁3.3连续 ARQ 协议3.3.1 连续 ARQ 协议的工作原理 n在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。n如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。n由于在等待确认时可以继续发送数据，减少了信道空闲时间，因而提高了整个通信过程的吞吐量。课件制作人：谢希仁连续 ARQ 协议的工作原理 DATA0DATA1DATA2DATA3DATA4DATA5重传 DATA2重传 DATA3ACK1ACK2ACK1 确认 DATA0ACK2 确认 DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传 ACK2DATA4 不按序，丢弃，重传 ACK2DATA5 不按序，丢弃，重传 ACK2ACK3ACK3 确认 DATA2ACK4 确认 DATA3ACK4重传 DATA5重传 DATA4超时重传时间ABtout送交主机送交主机?ACK2ACK2ACK2课件制作人：谢希仁需要注意：(1)接收端只按序接收数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。(2)ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1 号帧；ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。课件制作人：谢希仁需要注意：(3)结点 A 在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走必须向回走，将 2号帧及其以后的各帧全部进行重传。连续 ARQ 又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。课件制作人：谢希仁需要注意：(4)以上讲述的仅仅是连续 ARQ 协议的工作原理。协议在具体实现时还有许多的细节。课件制作人：谢希仁3.3.2 连续 ARQ 协议的吞吐量 n使用连续 ARQ 协议，正确传送一个数据帧所需的平均时间：n在发送结点处于饱和状态下,吞吐量的最大值是：=tT/tf,tT略大于略大于tf 课件制作人：谢希仁3.3.3 滑动窗口的概念n发送端和接收端分别设定发送窗口和接收窗口。n发送窗口用来对发送端进行流量控制。n n发送窗口最大尺寸发送窗口最大尺寸发送窗口最大尺寸发送窗口最大尺寸 WWT T 代表在还没有收到对方确认信息的情况下发送端最多最多可以发送多少个数据帧。n因为当前在发送窗口内的帧可能最终在运送中丢失或损因为当前在发送窗口内的帧可能最终在运送中丢失或损坏坏,所以发方必须在内存中保留所有这些帧以备可能的所以发方必须在内存中保留所有这些帧以备可能的重发，故须设置最大窗口尺寸重发，故须设置最大窗口尺寸(缓存大小缓存大小):在没有收到在没有收到对方确认的条件下发方可连续发送的帧数对方确认的条件下发方可连续发送的帧数.课件制作人：谢希仁发送窗口n发送窗口：发送端维护的一个允许并已被发出但尚未被确认的帧的序号表，其中的序号连续.n发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变；课件制作人：谢希仁发送窗口滑动机制n有新分组从网络层到来且窗口未增到最大尺寸时,窗口上沿增1;n确认来到时,检查确认序号，落在发送窗口内则顺时针滑动发送窗口，否则不做处理.课件制作人：谢希仁01234567012发送窗口发送窗口WT不允许发送这些帧不允许发送这些帧允许发送允许发送 5 个帧个帧(a)01234567012不允许发送这些帧不允许发送这些帧还允许发送还允许发送 4 个帧个帧WT已发送已发送(b)01234567012不允许发送这些帧不允许发送这些帧WT已发送已发送(c)01234567012不允许发送这些帧不允许发送这些帧还允许发送还允许发送 3 个帧个帧WT已发送已发送 已发送已发送并已收到确认并已收到确认(d)课件制作人：谢希仁接收端设置接收窗口 n在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。n若接收到的数据帧落在接收窗口之外，则一律将其丢弃。n在连续 ARQ 协议中，接收窗口的大小 WR=1。n只有当收到的帧的序号与接收窗口一致时才能接收该帧。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。否则，就丢弃它。n每收到一个序号正确的帧，接收窗口就向前（即向右方）每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。滑动一个帧的位置。同时发送对该帧的确认。课件制作人：谢希仁不允许接收这些帧01234567012WR准备接收 0 号帧(a)不允许接收这些帧01234567012WR准备接收 1 号帧已收到(b)不允许接收这些帧01234567012WR准备接收 4 号帧已收到(c)课件制作人：谢希仁滑动窗口的重要特性n只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。n收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。n当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议。课件制作人：谢希仁发送窗口的最大值 n当用 n 个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口最大尺寸 1WT 2n 1时，连续 ARQ 协议才能正确运行。nWT=2n时若ACK全部丢失,发方会误判0号重复帧为新的数据帧。n例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。课件制作人：谢希仁V(S)=0 1 2 3 0例例1:1:W WT T=2=2n n,n=2,ACK,n=2,ACK全部丢失全部丢失一直没收到确认一直没收到确认,窗口已至最大尺窗口已至最大尺寸寸,关闭网络层关闭网络层关闭网络层关闭网络层01230N(S)V(R)=0 1 2 3 0 1超时重发超时重发帧帧0!V(R)=0=N(S),故收下故收下“新帧新帧”(实为重复帧实为重复帧!)错错!tout课件制作人：谢希仁V(S)=0 1 2 3 例例2:2:W WT T=2=2n n-1,n=2,ACK-1,n=2,ACK全部丢失全部丢失一直没收到确认一直没收到确认,窗口已至最大尺窗口已至最大尺寸寸,关闭网络层关闭网络层关闭网络层关闭网络层0120N(S)toutV(R)=0 1 2 3超时重发超时重发帧帧0!V(R)N(S),故不收下故不收下0号号帧帧,但发但发ACK!OK3tout12ACK0新数据帧新数据帧课件制作人：谢希仁n在实际应用中，有模8和模128两种编码方式。模8采用3位编码，一般用于地面链路通信；模128采用7位编码，一般用于卫星链路通信。课件制作人：谢希仁3.3.4 信道利用率n由于每个数据帧都必须包括一定的控制信息(如帧的序号、地址、同步信息以及其他的一些控制信息)，所以即使连续不停地发送数据帧，信道利用率(即扣除全部的控制信息后的数据率与信道容量之比)也不可能达到 100%。n当出现差错时(这是不可避免的)，数据帧的不断重传将进一步使信道利用率降低。课件制作人：谢希仁最佳帧长 n若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。n若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。n由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。课件制作人：谢希仁最佳帧长n发送端工作在饱和状态的发送速率为每秒发送max,设每帧中数据为ldbit,控制信息为lhbit,C为链路带宽,平均有效数据率为D。课件制作人：谢希仁3.4 选择重传 ARQ 协议 n在连续ARQ中，如果某个数据帧发生差错，后续的数据帧即使被正确地接收到，也要被丢弃，造成网络资源浪费；n为进一步提高信道的利用率，可设法只重传出错的数据帧或计时器超时的数据帧。课件制作人：谢希仁3.4 选择重传 ARQ 协议 n可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。n选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。n付出的代价是在接收端要设置具有相当容量的缓存空间。n对于选择重传 ARQ 协议，若用 n 比特进行编号，则接收窗口的最大值受下式的约束WR 2n/2 (3-18)课件制作人：谢希仁n当接收窗口 WR 为最大值时,WT=WR=2n/2.课件制作人：谢希仁3.5 面向比特的链路控制规程 HDLC3.5.1 HDLC 协议概述n1974年，IBM 公司推出了面向比特的规程SDLC(Synchronous Data Link Control)。n后来 ISO 把 SDLC 修改后称为 HDLC(High-level Data Link Control)，译为高级数据链路控制，作为国际标准ISO 3309。nCCITT 则将 HDLC 再修改后称为链路接入规程 LAP(Link Access Procedure)。不久，HDLC 的新版本又把 LAP 修改为 LAPB，“B”表示平衡型(Balanced)，所以 LAPB 叫做链路接入规程(平衡型)。课件制作人：谢希仁3.5.2 HDLC 的帧结构n标志字段 F(Flag)为 6 个连续 1 加上两边各一个 0 共 8 bit。在接收端只要找到标志字段就可确定一个帧的位置。比特比特888可变可变168信息信息 Info标志标志 F标志标志 F地址地址 A控制控制 C帧检验序列帧检验序列 FCS透明传输区间透明传输区间FCS 检验区间检验区间课件制作人：谢希仁零比特填充法 nHDLC 采用零比特填充法使一帧中两个 F 字段之间不会出现 6 个连续 1。n在发送端，当一串比特流数据中有 5 个连续 1 时，就立即填入一个 0。n在接收帧时，先找到 F 字段以确定帧的边界。接着再对比特流进行扫描。每当发现 5 个连续 1 时，就将其后的一个 0 删除，以还原成原来的比特流。课件制作人：谢希仁零比特的填充与删除零比特的填充与删除 数据中某一段比特组合恰好数据中某一段比特组合恰好出现和出现和 F 字段一样的情况字段一样的情况0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0会被误认为是会被误认为是 F 字段字段发送端在发送端在 5 个连个连 1 之后之后填入填入 0 比特再发送出去比特再发送出去填入填入 0 比特比特0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0在接收端将在接收端将 5 个连个连 1 之后之后的的 0 比特删除，恢复原样比特删除，恢复原样在此位置删除填入的在此位置删除填入的 0 比特比特0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0课件制作人：谢希仁透明传输 n采用零比特填充法就可传送任意组合的比特流，或者说，就可实现数据链路层的透明传输。n当连续传输两个帧时，前一个帧的结束标志字段 F 可以兼作后一帧的起始标志字段。n当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步。课件制作人：谢希仁其他字段 n地址字段 A 是 8 bit。n帧检验序列 FCS 字段共 16 bit。所检验的范围是从地址字段的第一个比特起，到信息字段的最末一个比特为止。n控制字段 C 共 8 bit，是最复杂的字段。HDLC 的许多重要功能都靠控制字段来实现。课件制作人：谢希仁3.6 因特网的点对点协议 PPP3.6.1 PPP 协议的工作原理n现在全世界使用得最多的数据链路层协议是点对点协议 PPP(Point-to-Point Protocol)。n用户使用拨号电话线接入因特网时，一般都是使用 PPP 协议。课件制作人：谢希仁用户拨号入网的示意图 路由器调制解调器调制解调器调制解调器因特网服务提供者(ISP)用户家庭拨号电话线 使用使用 TCP/IP 的的 PPP 连接连接使用使用 TCP/IP 的的 客户进程客户进程路由选择 进程至因特网PC 机课件制作人：谢希仁PPP 协议 n1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准RFC 1661。nPPP协议有三个组成部分 n一个将一个将 IP 数据报封装到串行链路的方法。数据报封装到串行链路的方法。n一个用来一个用来建立建立、配置配置和和测试测试数据链路的链路数据链路的链路控制协议控制协议 LCP(Link Control Protocol)。n一套一套网络控制协议网络控制协议 NCP(Network Control Protocol),每一个协议支持不同的网络层协每一个协议支持不同的网络层协议。议。课件制作人：谢希仁3.6.2 PPP 协议的帧格式nPPP 的帧格式和 HDLC 的相似。n标志字段 F 仍为 0 x7E（01111110）。n地址字段 A 只置为 0 xFF。地址字段实际上并不起作用。n控制字段 C 通常置为 0 x03。nPPP 是面向字节的，所有的 PPP 帧的长度都是整数字节。课件制作人：谢希仁PPP 协议的帧格式nPPP 有一个 2 个字节的协议字段。n当协议字段为当协议字段为 0 x0021 时，时，PPP 帧的信息字段就是帧的信息字段就是IP 数据报。数据报。n若为若为 0 xC021,则信息字段是则信息字段是 PPP 链路控制数据。链路控制数据。n若为若为 0 x8021，则表示这是网络控制数据。则表示这是网络控制数据。IP 数据报1211字节12不超过 1500 字节PPP 帧先发送7EFF03FACFCSF7E协议信 息 部 分首部尾部课件制作人：谢希仁透明传输问题 n当 PPP 用在同步传输链路时，协议规定采用硬件来完成比特填充（和 HDLC 的做法一样）。n当 PPP 用在异步传输时，就使用一种特殊的字符填充法。PPP既支持异步链路,也支持面向比特的同步链路.课件制作人：谢希仁字符填充法 n将信息字段中出现的每一个 0 x7E 字节转变成为 2 字节序列(0 x7D,0 x5E)。n若信息字段中出现一个 0 x7D 的字节,则将其转变成为 2 字节序列(0 x7D,0 x5D)。n若信息字段中出现 ASCII 码的控制字符（即数值小于 0 x20 的字符），则在该字符前面要加入一个 0 x7D 字节，同时将该字符的编码加以改变(见RFC 1662)。课件制作人：谢希仁 不提供可靠传输(不使用序号和确认)nPPP 协议之所以不使用序号和确认机制是出于以下的考虑：n在数据链路层出现差错的概率不大时，使用比在数据链路层出现差错的概率不大时，使用比较简单的较简单的 PPP 协议较为合