计算机网络技术第3章课件.ppt

1、第3章 数据链路层第1页，共56页。导入导入qPPP协议是目前协议是目前Internet上使用最为上使用最为广泛的点对点数据链广泛的点对点数据链路层协议。路层协议。q什么是数据链路层？其什么是数据链路层？其功能是什么？它包括哪功能是什么？它包括哪些设计要点和关键技术？些设计要点和关键技术？数据链路层协议包含哪数据链路层协议包含哪些基本类型和具体实现些基本类型和具体实现方法？方法？第2页，共56页。主要内容主要内容n3.1 数据链路层的基本概念数据链路层的基本概念n3.2 差错控制编码技术差错控制编码技术n3.3 数据链路层协议数据链路层协议n3.4 数据链路层协议示例数据链路层协议示例第3页，

2、共56页。3.1 数据链路层的基本概念数据链路层的基本概念n3.1.1 链路和数据链路链路和数据链路n3.1.2 数据链路层为网络层提供的服务数据链路层为网络层提供的服务n3.1.3 数据链路层设计要点数据链路层设计要点n数据链路层属于计算机网络的低层，数据链路层的主要功能是在不可数据链路层属于计算机网络的低层，数据链路层的主要功能是在不可靠的物理线路上实现数据的可靠传输，即数据链路层提供网络中相邻节靠的物理线路上实现数据的可靠传输，即数据链路层提供网络中相邻节点之间的可靠的数据通信。点之间的可靠的数据通信。n数据链路层按使用信道类型的不同可以分为点对点信道的数据链路层和广播信数据链路层按使用

3、信道类型的不同可以分为点对点信道的数据链路层和广播信道的数据链路层两种。本章主要介绍前者。道的数据链路层两种。本章主要介绍前者。第4页，共56页。3.1.1 链路和数据链路链路和数据链路n链路，又叫物理链路，是一条无源的点到点的物理线路，中间没有任何交换节点。链路，又叫物理链路，是一条无源的点到点的物理线路，中间没有任何交换节点。n物理链路加上必要的通信协议物理链路加上必要的通信协议(规程规程)，或者说把实现通信协议（规程）的硬，或者说把实现通信协议（规程）的硬件或软件加在链路上，就构成了数据链路，也称逻辑链路。件或软件加在链路上，就构成了数据链路，也称逻辑链路。第5页，共56页。3.1.2

4、数据链路层为网络层提供的服务数据链路层为网络层提供的服务n设立数据链路层的主要目的设立数据链路层的主要目的q将原始的、不可靠的物理将原始的、不可靠的物理线路变为对网络层无差错线路变为对网络层无差错的数据链路。为了实现这的数据链路。为了实现这个目的，数据链路层必须个目的，数据链路层必须实现链路管理、成帧与透实现链路管理、成帧与透明传输、流量控制、差错明传输、流量控制、差错控制等功能。控制等功能。q数据链路层必须实现链路管理、数据链路层必须实现链路管理、成帧与透明传输、流量控制、成帧与透明传输、流量控制、差错控制等功能。差错控制等功能。n数据链路层为网络层提供的服务数据链路层为网络层提供的服务中最

5、主要的是中最主要的是q将数据从源主机的网络层将数据从源主机的网络层传输到目的主机的网络层。传输到目的主机的网络层。第6页，共56页。数据链路层提供以下数据链路层提供以下3种可能服务种可能服务 n1.无确认的无连接服务无确认的无连接服务q当线路通信质量高当线路通信质量高(错误率很低错误率很低)时，或在实时通信中，此类服务是很时，或在实时通信中，此类服务是很合适的。合适的。q目前，绝大多数局域网中均采用此项服务。目前，绝大多数局域网中均采用此项服务。n2.有确认的无连接服务有确认的无连接服务q数据链路层上提供确认只是一种优化，而永远不应该是一种要数据链路层上提供确认只是一种优化，而永远不应该是一种

6、要求。此类服务用在不可靠的无线信道上是非常适合的。求。此类服务用在不可靠的无线信道上是非常适合的。n3.有确认的面向连接服务有确认的面向连接服务q数据链路层的面向连接的服务为网络层提供了可靠的数据传输服数据链路层的面向连接的服务为网络层提供了可靠的数据传输服务。务。q面向连接的服务的数据传输要经过面向连接的服务的数据传输要经过3个不同的阶段：建立连接、数个不同的阶段：建立连接、数据传输和释放连接。据传输和释放连接。第7页，共56页。3.1.3 数据链路层设计要点数据链路层设计要点n组帧与帧同步组帧与帧同步n透明传输透明传输n流量控制流量控制n差错控制差错控制n寻址寻址 第8页，共56页。组帧与

7、帧同步组帧与帧同步n在数据链路层，数据传送的基本单位是帧在数据链路层，数据传送的基本单位是帧。q组帧主要是便于进行错误检测和纠正，在某些情况组帧主要是便于进行错误检测和纠正，在某些情况下可提高传输效率。下可提高传输效率。n帧同步是指接收端应当能从收到的比特流中准帧同步是指接收端应当能从收到的比特流中准确地区分出一帧的开始和结束的位置。确地区分出一帧的开始和结束的位置。q网络传输中很难保证计时的正确和一致（很难保证网络传输中很难保证计时的正确和一致（很难保证收发双方的时钟能精确一致），所以采用依靠时间收发双方的时钟能精确一致），所以采用依靠时间或时间间隔关系来标识一帧的开始和结束位置的方或时间间

8、隔关系来标识一帧的开始和结束位置的方法显然是不可行的。法显然是不可行的。第9页，共56页。常用的有常用的有4种帧同步方法种帧同步方法 n字节计数法字节计数法n n字符填充首尾定界法字符填充首尾定界法n n比特填充首尾定界法比特填充首尾定界法 n物理层违例编码法物理层违例编码法 第10页，共56页。透明传输透明传输n透明传输就是不透明传输就是不管所传数据是什管所传数据是什么样的比特组合么样的比特组合（字符型数据或（字符型数据或二进制数据），二进制数据），都应当能够在链都应当能够在链路上安全可靠地路上安全可靠地传输。传输。非透明传输举例 字节填充法解决透明传输问题的示例比特填充法解决透明传输的问题

9、示例第11页，共56页。流量控制流量控制n流量控制实际上是对发送方数据流量的控制，流量控制实际上是对发送方数据流量的控制，使其发送速率不至于超过接收端的处理能力。使其发送速率不至于超过接收端的处理能力。q当接收端来不及接收时，就必须及时控制发送端发当接收端来不及接收时，就必须及时控制发送端发送数据的速率，以使收发双方达到匹配。送数据的速率，以使收发双方达到匹配。n流量控制常用的方法有两种。流量控制常用的方法有两种。q基于反馈的流量控制（基于反馈的流量控制（Feedback-Based Flow Control）q基于速率的流量控制（基于速率的流量控制（Rate-Based Flow Contr

10、ol）流量控制并不是数据链路层特有的功能，许多高层协议也提供流量控制功能，只不过流量流量控制并不是数据链路层特有的功能，许多高层协议也提供流量控制功能，只不过流量控制的对象不同而已。控制的对象不同而已。对于数据链路层来说，控制的是相邻两节点之间数据链路上的流量，而对于运输层来说，对于数据链路层来说，控制的是相邻两节点之间数据链路上的流量，而对于运输层来说，控制的则是从源主机到目的主机之间端对端的流量。控制的则是从源主机到目的主机之间端对端的流量。第12页，共56页。差错控制差错控制n前向纠错（前向纠错（Forward Error Correction,FEC）n即接收方收到有差错的数据帧时能自

11、动将差错改正过来。即接收方收到有差错的数据帧时能自动将差错改正过来。n这种方法的开销较大，不适合于计算机网络通信。这种方法的开销较大，不适合于计算机网络通信。n自动请求重发自动请求重发(Automatic Repeat reQuest,ARQ)n即接收方如果检测出收到的帧中有差错，就让发送方重复发送这即接收方如果检测出收到的帧中有差错，就让发送方重复发送这一帧，直到接收方正确收到这一帧为止。一帧，直到接收方正确收到这一帧为止。n这种方法在计算机网络通信中是最常用的。这种方法在计算机网络通信中是最常用的。n传输差错可分为两大类：一类是比特差错；而另一类就是出传输差错可分为两大类：一类是比特差错；

12、而另一类就是出现了帧丢失、帧重复或帧失序。现了帧丢失、帧重复或帧失序。q要解决这两类传输差错问题，从而实现数据链路层的可靠传输，必须在差要解决这两类传输差错问题，从而实现数据链路层的可靠传输，必须在差错检测技术的基础上，增加定时器、帧编号、确认和重传机制。错检测技术的基础上，增加定时器、帧编号、确认和重传机制。q目前因特网上广泛使用的数据链路层协议已不再使用确认和重传机制了，目前因特网上广泛使用的数据链路层协议已不再使用确认和重传机制了，即不提供向上的可靠传输服务了。即不提供向上的可靠传输服务了。第13页，共56页。寻址寻址 n必须保证每一帧都能送到正确的目的站，接收必须保证每一帧都能送到正确

13、的目的站，接收方也应知道发送方是哪个站。方也应知道发送方是哪个站。第14页，共56页。3.2 差错控制编码技术差错控制编码技术n3.2.1 奇偶校验码奇偶校验码n3.2.2 循环冗余校验码循环冗余校验码n3.2.3 海明码海明码纠错码（纠错码（Error-Correcting Code）和检错码（）和检错码（Error-Detecting Code）是实现差）是实现差错检测和纠正的两种不同的差错控制编码技术。错检测和纠正的两种不同的差错控制编码技术。纠错码（纠错码（Error-Correcting Code）和检错码各有优缺点。）和检错码各有优缺点。比较常见的检错码主要有奇偶校验码和循环冗余校

14、验码，常见的纠错比较常见的检错码主要有奇偶校验码和循环冗余校验码，常见的纠错码主要有海明码、正反码等。码主要有海明码、正反码等。第15页，共56页。3.2.1 奇偶校验码奇偶校验码n奇偶校验码奇偶校验码q是通过增加冗余位来使得码字中是通过增加冗余位来使得码字中“1”的个数为奇数（奇校验）或偶数（偶的个数为奇数（奇校验）或偶数（偶校验）的编码方法。校验）的编码方法。q奇偶校验码可分为垂直、水平、水平垂直奇偶校验等几种方式奇偶校验码可分为垂直、水平、水平垂直奇偶校验等几种方式 垂直偶校验 水平偶校验 水平垂直偶校验 第16页，共56页。3.2.2 循环冗余校验码循环冗余校验码（Cyclic Red

15、undancy Check,CRC）nCRC又叫多项式编码（又叫多项式编码（polynomial code）q基本思想是：将比特串看成是系数为基本思想是：将比特串看成是系数为0或或1的多项式。一个的多项式。一个k比特构成比特构成的帧看作是一个的帧看作是一个k-1次多项式系数列表，该多项式共有次多项式系数列表，该多项式共有k项，从项，从xk-1到到x0，这个多项式的最高阶为，这个多项式的最高阶为k-1。n如比特串如比特串110011共有共有6位，对应一个共有位，对应一个共有6项的多项式，其系数分别为项的多项式，其系数分别为1、1、0、0、1和和1，即，即x5+x4+x+1（1*x5+1*x4+0

16、*x3+0*x2+1*x1+1*x0）。）。q多项式的算术运算采用模多项式的算术运算采用模2运算法则。按照它的运算法则，加法不运算法则。按照它的运算法则，加法不进位，减法不借位，加法和减法两者都与异或运算相同，因而计进位，减法不借位，加法和减法两者都与异或运算相同，因而计算结果相同。算结果相同。qCRC具有较强的检错能力，可以检测出所有的奇数位错、双比具有较强的检错能力，可以检测出所有的奇数位错、双比特错、小于等于校验和长度的突发错。特错、小于等于校验和长度的突发错。第17页，共56页。CRC进行编码和校验的原理进行编码和校验的原理 n(1)发送方和接收方事先约定一个生成多项式发送方和接收方事

17、先约定一个生成多项式G(x)，生成多项式的最高位和最低位，生成多项式的最高位和最低位必须是必须是1。n(2)发送端根据生成多项式发送端根据生成多项式G(x)去计算要附加在信息帧尾部的冗余位（校验和，去计算要附加在信息帧尾部的冗余位（校验和，Checksum）。计算校验和的算法如下。）。计算校验和的算法如下。q 假设信息帧的比特数为假设信息帧的比特数为k位，对应的多项式为位，对应的多项式为K(x)，G(x)为为r阶。在信息帧的低阶。在信息帧的低位端加上位端加上r个个0，此时信息帧的比特数变为，此时信息帧的比特数变为k+r位，对应的多项式为位，对应的多项式为xrK(x)。q 按模按模2除法，用对应

18、于除法，用对应于G(x)的比特串去除对应于的比特串去除对应于xrK(x)的比特串，从而的比特串，从而得到一个小于等于得到一个小于等于r位的余数。这个余数便可作为校验和。位的余数。这个余数便可作为校验和。n(3)将校验和附加在将校验和附加在k位信息帧尾部，组成一个新的帧，由发送端发送给接收端。位信息帧尾部，组成一个新的帧，由发送端发送给接收端。假设这个新的帧对应的多项式为假设这个新的帧对应的多项式为T(x)，其显然能被，其显然能被G(x)除尽。因为这个新的帧的除尽。因为这个新的帧的多项式多项式T(x)所对应的比特串可以看作是由多项式所对应的比特串可以看作是由多项式xrK(x)对应的比特串减去余数

19、而对应的比特串减去余数而得到的。得到的。n(4)当接收方收到带有校验和的帧时，用当接收方收到带有校验和的帧时，用G(x)去除它，如果余数不为去除它，如果余数不为0，则说明传输过程中出现了错误；如果余数为则说明传输过程中出现了错误；如果余数为0，则认为传输无差错。，则认为传输无差错。第18页，共56页。发送端生成带校验和的发送端生成带校验和的CRC帧的过程举例帧的过程举例n信息帧信息帧q1101011011n生成多项式生成多项式qx4+x+1第19页，共56页。3.2.3 海明码海明码n海明码是由海明码是由R.Hamming在在1950年首次提出的，年首次提出的，是一种可以纠正一比特错的编码。是

20、一种可以纠正一比特错的编码。n简单的奇偶校验中的一个重要的结论简单的奇偶校验中的一个重要的结论 q信息位为信息位为k=n-1位位an-1an-2a1，加上一个偶校验位，加上一个偶校验位a0，构成一个，构成一个n位的码字位的码字an-1an-2a1a0。在接收端。在接收端校验时，可按关系式：校验时，可按关系式：S0=an-1+an-2+a1+a0（模（模2运算）来计算，若运算）来计算，若S0=0，则认为无错；若，则认为无错；若S0=1，则肯定有错。上面关系式称为监督关系式，则肯定有错。上面关系式称为监督关系式，S0称为称为校正因子。校正因子。第20页，共56页。海明码原理推导海明码原理推导n对上

21、面结论的分析对上面结论的分析q在上面偶校验情况下，只有一个监督关系式，一个校正因子，其取值在上面偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有只有0或或1两种可能，分别代表了无错和有错两种情况，但却不能指出两种可能，分别代表了无错和有错两种情况，但却不能指出差错所在的位置。不难设想，如果增加冗余位，让每个冗余位分别与差错所在的位置。不难设想，如果增加冗余位，让每个冗余位分别与信息中的某些位构成一个偶校验关系，则就会相应地增加监督关系式信息中的某些位构成一个偶校验关系，则就会相应地增加监督关系式和校正因子，就能区分更多的情况。和校正因子，就能区分更多的情况。q不难推出，信息位为不难推

22、出，信息位为k位，增加位，增加r位冗余位，构成位冗余位，构成n=k+r位码字。位码字。若希望用若希望用r个监督关系式产生的个监督关系式产生的r个校正因子来区分无错和在码个校正因子来区分无错和在码字中的字中的n个不同位置的个不同位置的1位错，则要求：位错，则要求：2rn+1或或2rk+r+1第21页，共56页。k=4时，海明码产生基本原理示例时，海明码产生基本原理示例 n构造构造S2S1S0取值与错码位置的对应关系取值与错码位置的对应关系 也可以规定成另外的对应关系，这并不影响讨论的一般性 n根据上表推出监督关系式 n令校正因子都等于零，代入已知信息位，计算出冗余位第22页，共56页。K=4时由

23、信息位算得的冗余位时由信息位算得的冗余位 n基于上面构造的海明码，可得到各种信息位与基于上面构造的海明码，可得到各种信息位与冗余位的对应关系冗余位的对应关系 第23页，共56页。海明码纠正突发性错误海明码纠正突发性错误 n海明码只能纠正海明码只能纠正1位错，为了纠正在传输过程位错，为了纠正在传输过程中出现的突发性错误，可以采用如下的技巧或中出现的突发性错误，可以采用如下的技巧或方法。将方法。将k个连续的码字排成一个矩阵，每行个连续的码字排成一个矩阵，每行一个码字，传输数据时每次发送一列，从左边一个码字，传输数据时每次发送一列，从左边的列开始，如图所示。的列开始，如图所示。第24页，共56页。海

24、明码生成方案海明码生成方案n海明码是一种可以纠正一位差错的编码。它是利用在信海明码是一种可以纠正一位差错的编码。它是利用在信息位为息位为k位，增加位，增加r个冗余位，构成一个个冗余位，构成一个n=k+r位的码字，位的码字，然后用然后用r个监督关系式产生的个监督关系式产生的r个校正因子来区分无错和个校正因子来区分无错和在码字中的在码字中的n个不同位置的个不同位置的1位错。它必须满足位错。它必须满足 2rn+1或或2rk+r+1n海明码的生成方案主要有两种，二者的主要区别是对冗余位在海明码的生成方案主要有两种，二者的主要区别是对冗余位在生成后的码字中的位置处理方式不一样。生成后的码字中的位置处理方

25、式不一样。q前面已经介绍了第一种方案，它是将前面已经介绍了第一种方案，它是将r个冗余位顺序放在个冗余位顺序放在k个信息位的后面，个信息位的后面，q另一种方案叫顺序生成法，是将另一种方案叫顺序生成法，是将r个冗余位分别放在个冗余位分别放在k+r位的码字位的码字中位置（按位从右往左数）为中位置（按位从右往左数）为20到到2r-1的那些位上，其余的用信息的那些位上，其余的用信息位来填充。位来填充。第25页，共56页。海明码的生成与接收过程海明码的生成与接收过程n(1)假设信息位为假设信息位为k位，将位，将k的值代入公式（的值代入公式（2rk+r+1）计算出冗余位的个）计算出冗余位的个数数r的取值范围

26、，从中选择一个（通常会取最小的那一个），以方案一或顺序生成的取值范围，从中选择一个（通常会取最小的那一个），以方案一或顺序生成法对法对r个冗余位进行处理，构造一个个冗余位进行处理，构造一个n=k+r的码字。的码字。n(2)约定约定r个校正因子组成的二进制序列个校正因子组成的二进制序列Sr-1S1S0的取值与错码的位置对应关的取值与错码的位置对应关系（通常将其表示成表格的形式）。系（通常将其表示成表格的形式）。n(3)确定监督关系式。确定监督关系式。n(4)令监督关系式中所有的校正因子均为令监督关系式中所有的校正因子均为0，同时将信息位的值代入相应的监督关，同时将信息位的值代入相应的监督关系式，

27、从而计算出各冗余位的值。系式，从而计算出各冗余位的值。n(5)将信息位与冗余位组成的码字发送给接收端。将信息位与冗余位组成的码字发送给接收端。n(6)接收端将其收到的码字，利用监督关系式进行校验。如果接收端将其收到的码字，利用监督关系式进行校验。如果Sr-1S1S0=0，则表示没有错误。如果，则表示没有错误。如果Sr-1S1S0不为不为0，则根据约定的，则根据约定的Sr-1S1S0的取值与错码的位置对应关系确定出错码的位置，对错码位进的取值与错码的位置对应关系确定出错码的位置，对错码位进行取反，得到正确的码字。行取反，得到正确的码字。第26页，共56页。3.3 数据链路层协议数据链路层协议n为

28、了便于说明，采用一个简化的通信模型，把数据链路层以为了便于说明，采用一个简化的通信模型，把数据链路层以上的各层抽象为一个主机，而把物理层和传输媒体抽象成一上的各层抽象为一个主机，而把物理层和传输媒体抽象成一条简单的链路。条简单的链路。n假设全双工通信，则收发两端要同时设有发送和接收缓假设全双工通信，则收发两端要同时设有发送和接收缓冲区。冲区。第27页，共56页。理想传输条件下的数据传输理想传输条件下的数据传输 n所谓的理想传输条件是指满足以下两个假定的所谓的理想传输条件是指满足以下两个假定的理想化状态。理想化状态。q(1)链路是理想的传输信道，不会产生差错，数据链路是理想的传输信道，不会产生差

29、错，数据帧传输过程中不会出错也不会丢失。帧传输过程中不会出错也不会丢失。q(2)不管发送端以多快的速度发送数据帧，接收端不管发送端以多快的速度发送数据帧，接收端总是来得及接收，并及时上交主机。总是来得及接收，并及时上交主机。在这样的理想传输条件下，不需要采取任何措施就能实现可靠传输，即不在这样的理想传输条件下，不需要采取任何措施就能实现可靠传输，即不需要任何数据链路层协议就可保证可靠传输。需要任何数据链路层协议就可保证可靠传输。然而实际的网络都不具备以上两个理想条件然而实际的网络都不具备以上两个理想条件 第28页，共56页。3.3 数据链路层协议数据链路层协议n3.3.1 简单的停止等待协议简

30、单的停止等待协议n3.3.2 实用的停止等待协议实用的停止等待协议n3.3.3 连续连续ARQ协议协议n3.3.4 选择重传选择重传ARQ协议协议n3.3.5 滑动窗口滑动窗口(Sliding Window)协议协议第29页，共56页。3.3.1 简单的停止等待协议简单的停止等待协议n简单的停止等待协议的工作原理简单的停止等待协议的工作原理q假定链路是理想的传输信道，不会产生差错，数据帧传输过程中不会出错也不会丢假定链路是理想的传输信道，不会产生差错，数据帧传输过程中不会出错也不会丢失。在发送端，每发送完一个数据帧就暂停发送，等待着接收端的确认。如果收到失。在发送端，每发送完一个数据帧就暂停发

31、送，等待着接收端的确认。如果收到了来自接收端的确认帧，就继续发送下一帧。在接收端每收到一个无差错的帧，就了来自接收端的确认帧，就继续发送下一帧。在接收端每收到一个无差错的帧，就将其交给上层，并向发送端发送一个确认帧。将其交给上层，并向发送端发送一个确认帧。第30页，共56页。简单的停止等待协议算法简单的停止等待协议算法 第31页，共56页。3.3.2 实用的停止等待协议实用的停止等待协议n实用的停止等待协议就是在理想传输条件的两实用的停止等待协议就是在理想传输条件的两个假定都不成立的情况下，保证数据可靠传输个假定都不成立的情况下，保证数据可靠传输的一种协议。的一种协议。q在简单的停止等待协议中

32、在简单的停止等待协议中 通过引入通过引入“确认确认”解决解决了流量控制问题，这种方法对于实用的停止等待协了流量控制问题，这种方法对于实用的停止等待协议同样适用议同样适用。q实用的停止等待协议还要处理数据帧在传输过程中实用的停止等待协议还要处理数据帧在传输过程中出现的差错，主要包括数据帧出错、数据帧丢失、出现的差错，主要包括数据帧出错、数据帧丢失、确认帧丢失等几种情况。确认帧丢失等几种情况。第32页，共56页。数据帧出错时的两种解决方法数据帧出错时的两种解决方法 为了进行重传，在发送端必须暂时保存已发送过的数据帧的副本，直到收到对已发送帧的为了进行重传，在发送端必须暂时保存已发送过的数据帧的副本

33、，直到收到对已发送帧的确认帧为止。确认帧为止。当通信质量太差时，可能要进行多次重传，但当重传达到一定的次数后，应当通信质量太差时，可能要进行多次重传，但当重传达到一定的次数后，应立即停止，并向高层报告。立即停止，并向高层报告。超时定时器设置的超时时间应仔细选择确定。超时定时器设置的超时时间应仔细选择确定。第33页，共56页。两种不同的帧丢失的解决方法两种不同的帧丢失的解决方法 n超时重传与确认帧丢失的使用可能会引入了新的问题超时重传与确认帧丢失的使用可能会引入了新的问题-重复帧重复帧n为解决重复帧的问题，引入了给数据帧编号的方法为解决重复帧的问题，引入了给数据帧编号的方法q任何一个编号系统的序

34、号所占用的比特数一定是有限的，经过一段时间后序任何一个编号系统的序号所占用的比特数一定是有限的，经过一段时间后序号就会重复。号就会重复。q序号占用的比特数越少，数据传输的额外开销就越小序号占用的比特数越少，数据传输的额外开销就越小 第34页，共56页。实用的停止等待协议算法实用的停止等待协议算法n算法描述中，几个参数的意义如下算法描述中，几个参数的意义如下 qV(S)是发送端的状态变量，用来对发送端将要发送是发送端的状态变量，用来对发送端将要发送的数据帧进行编号；的数据帧进行编号；qV(R)是接收端的状态变量，用来表示接收端所期望是接收端的状态变量，用来表示接收端所期望接收到的数据帧的序号；接

35、收到的数据帧的序号；qN(S)是数据帧的帧编号。是数据帧的帧编号。n另外，对于数据帧出错的处理，是使用超时重另外，对于数据帧出错的处理，是使用超时重传的方法，而没有采用向发送端发送否定确认传的方法，而没有采用向发送端发送否定确认帧的方法。帧的方法。第35页，共56页。在发送端在发送端n(1)从主机取一个数据帧。从主机取一个数据帧。n(2)V(S)取取0（发送状态变量（发送状态变量V(S)初始化）。初始化）。n(3)令令N(S)等于等于V(S)（将发送状态变量的数值写入数据帧中的发送序号（将发送状态变量的数值写入数据帧中的发送序号N(S)，将，将数据帧送交发送缓冲区）。数据帧送交发送缓冲区）。n

36、(4)将发送缓冲区中的数据帧发送出去（发送缓冲区中保留此数据帧的副本）。将发送缓冲区中的数据帧发送出去（发送缓冲区中保留此数据帧的副本）。n(5)设置超时定时器（选择适当的超时时间）。设置超时定时器（选择适当的超时时间）。n(6)等待（等待以下步骤中的两个事件中最先出现的一个）。等待（等待以下步骤中的两个事件中最先出现的一个）。n(7)收到确认帧收到确认帧ACKn，若，若n=1-V(S)，则（接收方已经正确接收了发送端发出的数据，则（接收方已经正确接收了发送端发出的数据帧，并给出了确认）从主机取一个新的数据帧；令帧，并给出了确认）从主机取一个新的数据帧；令V(S)等于等于“1-V(S)”（更新

37、发送状态（更新发送状态变量，使用下一个序号）；转到执行步骤变量，使用下一个序号）；转到执行步骤(3)。否则，丢弃这个确认帧，转到执行步骤。否则，丢弃这个确认帧，转到执行步骤(6)。n(8)若超时定时器的时间到，则转到执行步骤若超时定时器的时间到，则转到执行步骤(4)（重发数据帧）。（重发数据帧）。第36页，共56页。在接收端在接收端n(1)V(R)取取0（接收状态变量初始化，其数值等于欲接收的数据帧的序（接收状态变量初始化，其数值等于欲接收的数据帧的序号）。号）。n(2)等待。等待。n(3)当收到一个数据帧，检查数据帧是否出错（通常使用当收到一个数据帧，检查数据帧是否出错（通常使用CRC进行检

38、进行检测）。若检查结果正确无误，则转到执行步骤测）。若检查结果正确无误，则转到执行步骤(4)；否则，丢弃此数；否则，丢弃此数据帧，转到步骤据帧，转到步骤(2)；n(4)若若N(S)=V(R)（收到了所期望的数据帧），将收到的数据帧中的数（收到了所期望的数据帧），将收到的数据帧中的数据部分送交主机，转到执行步骤据部分送交主机，转到执行步骤(5)。否则，丢弃此数据帧，然后转。否则，丢弃此数据帧，然后转到执行步骤到执行步骤(6)；（丢弃的帧为重复的帧）。；（丢弃的帧为重复的帧）。n(5)使使V(R)等于等于1-V(R)（更新接收状态变量，准备接收下一个数据帧）。（更新接收状态变量，准备接收下一个数据

39、帧）。n(6)令令n=V(R)，发送确认帧，发送确认帧ACKn，并转到步骤，并转到步骤(2)。（期望接收。（期望接收n号帧，在它之号帧，在它之前的帧收到了）前的帧收到了）第37页，共56页。实用的停止等待协议算法要点实用的停止等待协议算法要点n(1)发送端每发送一个数据帧，都要将发送状态变量发送端每发送一个数据帧，都要将发送状态变量V(S)的值（的值（0或或1）写到）写到数据帧的发送序号数据帧的发送序号N(S)上。只有收到已发送帧的确认帧后，才能更新发送状上。只有收到已发送帧的确认帧后，才能更新发送状态变量态变量V(S)（1变为变为0，或，或0变为变为1），并发送新的数据帧。），并发送新的数据

40、帧。n(2)接收端每接收到一个无差错的数据帧，就要将发送端在数据帧上设置接收端每接收到一个无差错的数据帧，就要将发送端在数据帧上设置的发送序号的发送序号N(S)与本地的接收状态变量与本地的接收状态变量V(R)进行比较。若二者相等就表进行比较。若二者相等就表明是所期望的数据帧，就收下，并发送确认。否则为重复帧，必须丢弃，明是所期望的数据帧，就收下，并发送确认。否则为重复帧，必须丢弃，但这时仍需要向发送端发送确认帧但这时仍需要向发送端发送确认帧ACKn，而接收状态变量，而接收状态变量V(R)和确认序和确认序号号n都不变，即重发上次的确认帧。都不变，即重发上次的确认帧。n(3)发送端在发送完数据帧时

41、，必须在其发送缓冲区中保留已发送数据帧的副发送端在发送完数据帧时，必须在其发送缓冲区中保留已发送数据帧的副本，以便在出现差错时进行重发。只有在收到接收端发来的确认帧，表示已本，以便在出现差错时进行重发。只有在收到接收端发来的确认帧，表示已经正确接收数据帧时，才能清除这个副本。经正确接收数据帧时，才能清除这个副本。第38页，共56页。3.3.3 连续连续ARQ协议协议n连续连续ARQ协议的工作要点协议的工作要点q发送端每发送完一个数据帧后，不是停下来等待接发送端每发送完一个数据帧后，不是停下来等待接收端的确认帧，而是可以连续再发送若干个数据帧。收端的确认帧，而是可以连续再发送若干个数据帧。如果在

42、此过程中收到了接收端发来的确认帧，那么如果在此过程中收到了接收端发来的确认帧，那么还可以继续发送数据帧。由于减少了等待时间，整还可以继续发送数据帧。由于减少了等待时间，整个通信的吞吐量就提高了。个通信的吞吐量就提高了。第39页，共56页。连续连续ARQ协议的工作原理示例协议的工作原理示例n注意：注意：q接收端只能按顺序接收数据帧。接收端只能按顺序接收数据帧。q连续连续ARQ又称为又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走，意思是当出现差错必须重传时，要向回走N个帧，然个帧，然后再开始重传。后再开始重传。q连续连续ARQ要求发送端的发送缓冲区必须能缓存多个数据帧，而接

43、收端的缓冲区只需要能要求发送端的发送缓冲区必须能缓存多个数据帧，而接收端的缓冲区只需要能容纳一个数据帧就足够了。容纳一个数据帧就足够了。q数据帧丢失与数据帧出错时的情况是基本相同的。数据帧丢失与数据帧出错时的情况是基本相同的。q数据帧的确认帧丢失了，则情况较为复杂数据帧的确认帧丢失了，则情况较为复杂。连续连续ARQARQ协议的工作原理：数据帧出错协议的工作原理：数据帧出错 第40页，共56页。3.3.4 选择重传选择重传ARQ协议协议n为了进一步提高信道的利用率和传输效率，可为了进一步提高信道的利用率和传输效率，可以设法只重传出错的数据帧或者是超时的数据以设法只重传出错的数据帧或者是超时的数据

44、帧。此时必须加大接收端的缓冲区使其能容纳帧。此时必须加大接收端的缓冲区使其能容纳多个数据帧，以便接收端先缓存那些正确的数多个数据帧，以便接收端先缓存那些正确的数据帧（发送序号可能是不连续的），等到所缺据帧（发送序号可能是不连续的），等到所缺序号的数据帧收到之后再一并送交主机。序号的数据帧收到之后再一并送交主机。第41页，共56页。选择重传选择重传ARQ协议的工作原理示例协议的工作原理示例n选择重传选择重传ARQ协议可避免重传那些本来已经正确到达接收端的数据帧，但是必须付出协议可避免重传那些本来已经正确到达接收端的数据帧，但是必须付出的代价：在接收端需要设置具有相当容量的缓存空间的代价：在接收端

45、需要设置具有相当容量的缓存空间 n数据帧的确认帧丢失的情况较为复杂数据帧的确认帧丢失的情况较为复杂 选择重传选择重传ARQARQ协议示意图：数据帧出错协议示意图：数据帧出错 第42页，共56页。3.3.5 滑动窗口滑动窗口(Sliding Window)协议协议n在使用连续在使用连续ARQ协议时，如果发送端一直没有收到对协议时，如果发送端一直没有收到对方的确认，那么实际上发送端并不能无限制的发送数据方的确认，那么实际上发送端并不能无限制的发送数据帧，其原因如下。帧，其原因如下。q(1)当未被确认的数据帧的数目太多时，只要有一帧出错或丢失，就会有当未被确认的数据帧的数目太多时，只要有一帧出错或丢

46、失，就会有很多的数据帧需要重传，这必然浪费很多时间，增大了开销。很多的数据帧需要重传，这必然浪费很多时间，增大了开销。q(2)为了对所发送的大量数据帧进行编号，每个数据帧的发送序号也要占为了对所发送的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特，这样又增加了一些不必要的开销。用较多的比特，这样又增加了一些不必要的开销。n在连续在连续ARQ协议中必须将已发送出去、但未被确认的数协议中必须将已发送出去、但未被确认的数据帧的数目加以限制，这就是滑动窗口协议所要讨论的内据帧的数目加以限制，这就是滑动窗口协议所要讨论的内容。容。第43页，共56页。发送窗口与接收窗口发送窗口与接收窗口n加入

47、适当的控制机制，循环使用已收到确认的那些帧的序号，在发送端加入适当的控制机制，循环使用已收到确认的那些帧的序号，在发送端和接收端分别设定和接收端分别设定“发送窗口发送窗口”和和“接收窗口接收窗口”。q发送窗口用来对发送端进行流量控制，而发送窗口的大小发送窗口用来对发送端进行流量控制，而发送窗口的大小Ws代表在还没有收到对代表在还没有收到对方确认的条件下发送端最多可以发送多少个数据帧。方确认的条件下发送端最多可以发送多少个数据帧。q接收窗口是为了控制哪些数据帧可以接收而哪些帧不可以接收。在接收端，只有当接收窗口是为了控制哪些数据帧可以接收而哪些帧不可以接收。在接收端，只有当收到的数据帧的发送序号

48、落入接收窗口内才允许将该数据帧收下。收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。n只有在接收窗口旋转（滑动）时，发送窗口才有可能旋转（滑动）。但只有在接收窗口旋转（滑动）时，发送窗口才有可能旋转（滑动）。但发送端如果没有收到已发送的那些帧的任何确认，同样也不会旋转（滑发送端如果没有收到已发送的那些帧的任何确认，同样也不会旋转（滑动）。接收窗口保持不动时，发送窗口无论如何也不会旋转（滑动），动）。接收窗口保持不动时，发送窗口无论如何也不会旋转（滑动），正因为收发两端的窗口按照以上规律不断旋转（滑动），因此这种协议正因为收发两端的窗口按照以上规律不断旋转（滑动），因此这种协议被称为滑

49、动窗口协议。被称为滑动窗口协议。第44页，共56页。滑动窗口协议示例滑动窗口协议示例-3比特编号比特编号n注：可以用水平窗口和圆形窗口两种方法来表示发送与接收窗口。注：可以用水平窗口和圆形窗口两种方法来表示发送与接收窗口。发送端发送端接收端接收端第45页，共56页。发送窗口的最大值讨论发送窗口的最大值讨论n3个比特可编出个比特可编出8个个不同的序号不同的序号q发送窗口的最大值似发送窗口的最大值似乎应当是乎应当是8。q其实不然，设置发送其实不然，设置发送窗口为窗口为8将使协议在将使协议在某些情况下无法工作。某些情况下无法工作。n如图如图(b)所示，发送窗所示，发送窗口口Ws=8将导致协议失将导致

50、协议失败败 第46页，共56页。发送窗口应满足的约束关系发送窗口应满足的约束关系n如图所示，采用如图所示，采用3个比特供数据帧的序号使用，个比特供数据帧的序号使用，WS=6，WR=3。n根据当前接收窗口的情况，只能推测发送端发送窗口的可能位置为 。n接收端在收到一个数据帧时，必须在下列3种情况中做出正确无误的选择。q(1)是所期望接收的数据帧。q(2)是重复帧（已对此帧发过确认帧，且已交付给主机）。q(3)是序号错误的超前帧。第47页，共56页。发送窗口应满足的约束关系（续）发送窗口应满足的约束关系（续）n对于图中的位置对于图中的位置，应要求在，应要求在WS+WR的范围内无重复序号的范围内无重