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

计算机网络（四） 关于数据链路层（1.基本原理）,信息科学与技术学院,学习目标!,了解：数据链路层的设计问题 掌握：数据链路层差错控制方法、循环冗余码编码原理 掌握：数据链路层的功能 掌握：基本数据链路协议 掌握：停等协议、滑动窗口协议的工作原理 掌握：面向比特型数据链路层协议实例 HDLC。 了解：Internet中的数据链路层协议。,前言：数据链路层的设计问题,为什么需要数据链路层？ 物理层未解决的问题： 位流传输过程中不可避免会出现差错 （电磁干扰，线路问题） 数据收发之间的速率匹配问题 （不同设备处理速度不同）,最主要的作用是通过一些数据链路层协议(即链路控制规程),在不太可靠的物理链路上实现 可靠的数据传输.,前言：数据链路层的设计问题 1. 向网络层提供的服务,前言：数据链路层的设计问题 2. 成帧,涉及的问题 协议数据单元,将上层(网络层)交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧； 考虑接收双方的同步问题（即定界）； 计算帧的校验和并放入帧中一起传送给接收方；,帧：在数据链路上交换数据的单位。,前言：数据链路层的设计问题 2. 成帧,字符计数法 字符填充的首尾定界法 位填充的首尾定界法,计数值传输出错时导致收发双方不同步.,同步字符法 标志法,填充技术,前言：数据链路层的设计问题 2. 成帧,物理层编码违例法 综合法,“0”,“1”,用计数值确定帧尾 检查帧定界符是否出现在应该出现的地方 计算校验和,前言：数据链路层的设计问题 3. 流量控制,流量控制,流量控制的特点,网络层实体控制从数据链路层接收数据的速率，据此，数据链路层要控制从同等实体接收PDU的速率。,限制发送方发送速度的一种机制。使发送速率不能超过接收方能处理的速率。,流量控制必须是动态的 必须有某种反馈机制,流量速度不仅与发方速度相关而且与网络的当前拥挤程度有关,使发方了解收方的当前处理能力,前言：数据链路层的设计问题 4. 差错控制,顺序到达 指保证所有的帧最终都按正确的发送次序到达目的。,检错和纠错 检出传输中出现的差错；可能的话确定出错位置从而纠正错误。,确认方式,计时器法,计时器值的设定要保证一帧到达对方并作处理后，相应的确认帧返回。,ACK肯定确认 NAK否定确认,计时结合序号才能保证每一帧的正确次序。,前言：数据链路层的设计问题 5. 数据链路层协议的作用,数据链路协议,DL协议的作用就是使不可靠的通信线路变得一定程度的好。,物理层: - 物理链路 - 比特流传输 - 有差错的物理链路 数据链路层: - 数据链路 - 帧传输 - 无差错的数据链路 - 数据链路层数据服务单元 - 帧,一、数据链路层概述,数据链路层于物理层之上,属于低层。物理层传输的是比特流，单位是比特。 数据链路层传输单位是帧，一帧一帧地处理。其工作是从物理层获取比特流，进行封装成帧、并对帧进行如透明传输、差错控制等处理，从而递交给上一层（网络层），同时也对网络层下传的数据进行处理，进而传给物理层。,数据链路层传送的是帧,一、数据链路层概述 分组与帧的关系图示,Relationship between packets and frames,一、数据链路层概述 数据链路层的简单模型,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,从层次上来看数据的流动,一、数据链路层概述 数据链路层的简单模型,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,R1,R2,R3,H1,H2,仅从数据链路层观察帧的流动,一、数据链路层概述 数据链路层协议在路由器中的位置,Placement of the data link protocol,一、数据链路层概述 数据链路层协议在路由器中的位置,数据链路协议,DL协议的作用就是使不可靠的通信线路变得一定程度的好。,一、数据链路层概述 1.常用概念,链路(link)：是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分。 数据链路(data link) ：除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。 现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层这两层的功能。 结点（node）：网络中的主机（host）和路由器（router）称为结点。,一、数据链路层概述 1.常用概念,链路（link）：通信路径上连接相邻结点的通信信道称为链路。 数据链路（data link)：链路+实现通信协议的硬件和软件。 数据链路层协议：定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。 端到端（end to end）与点到点（point to point）： 从源结点（source node）到目的结点（destination node）的通信称为端到端通信，通信路径（path）可能由多个链路组成。 在相邻结点间的一条链路上的通信称为点到点通信。 数据链路控制规程：为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。 早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。,虚拟数据通路，实际数据通路,一、数据链路层概述 1.常用概念,一、数据链路层概述 1.常用概念,数据链路层像个数字管道 常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。,一、数据链路层概述 2.数据链路层使用的信道类型,数据链路层使用的信道主要有以下两种类型： 点对点信道:这种信道使用一对一的点对点通信方式。 （例如PPP、SLIP） 广播信道:这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送 。 （例如以太网）,一、数据链路层概述 3.数据链路层协议基本功能,链路管理数据在数据链路上的正常传输（建立、维护和释放）。 帧同步：数据传输的单位为帧，定界与同步。也处理透明性问题。 流量控制与顺序控制。 差错控制：前向纠错、差错检测，检错重发。 将数据和控制信息分开。 透明传输。 寻址。,二、差错检测与校正 1.基本概念,什么是差错？ 在通信中接收端收到的二进制数位（码元）和发送端实际发送的数据不一致。 差错检测与校正：把差错控制在允许的范围内。 差错控制的主要内容： 差错编码、反馈重传、超时重传、重复帧丢弃、定时器管理等。,二、差错检测与校正 1.基本概念,误码率：衡量物理信道的质量. 差错控制编码：信息位(k)冗余位(r) 检错码：自动发现差错 纠错码：不仅能发现差错而且能够自动纠正 编码效率R：码字中信息位所占的比例 R=k/(k+r) 漏检率：信息位出错但是接收者无法了解到的概率,二、差错检测与校正 2.差错与校正概念,出错的类型 单个错：由随机的信道热噪声引起，一次只影响1位； 突发错：由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。 编码的类型 检错码：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来使用以便进行差错恢复； 纠错码：不权能够检测到数据传输发生了错误，而且能够自行纠正错误。,二、差错检测与校正 2.差错与校正概念,码字（codeword）：由m比特的数据（消息）加上r比特的冗余（校验位）构成； 有效编码集：由2m个有效码字组成； 检错：当收到的码字为无效码字时检测出错误； 海明距离（Hamming Distance）：两个码字的对应位上取值不同的位数； 纠错：将收到的无效码字纠正到距其最近的有效码字； 检错码与纠错码的能力都是有限的。,二、差错检测与校正 2.差错与校正概念,编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。 检错能力：为检测出d比特错误，编码集的海明距离至少应为d+1；奇偶校验是能够检测出1比特错误的检错码。 纠错能力：为纠正d比特错误，编码集的海明距离至少应为2d+1；海明码是能够纠正1比特错误的纠错码。,二、差错检测与校正 2.差错控制与校正方法,差错控制：ARQ和FEC ARQ（自动重传请求） Automatic Request for Repeat 接收方检测错误，通知发送方重传 双向信道，发送方缓存发送的数据 FEC（前向纠错） Forward Error Correction 接收方不仅可以检测错误，而且知道错误的位置，从而改正错误 采用纠错码，无需反向信道，无需重发，但编码效率低,纠错设备复杂,二、差错检测与校正！ 3.差错检测与校正和流量控制,由于系统性能的不同，如硬件能力（包括CPU，存储器等）和软件功能的差异，会导致发送方与接收方处理数据的能力有所不同。 流量控制的作用是使发送方所发出的数据流量，使其发送速率不要超过接收方所能接收的速率。 流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收方是否能接收到 存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协议则将关于帧的确认与流量控制巧妙地结合在了一起。 流量控制的主要机制： 基于反馈的流量控制（） 基于速率的流量控制,二、差错检测与校正 4.常用的简单差错控制编码（奇偶校验码）,奇偶校验码：增加冗余位使 得码字中1的个数为奇数或 者偶数，检错码 垂直奇偶校验 水平奇偶校验 水平垂直奇偶校验 垂直奇偶校验： 发送的信息块分成定长为p位的若干段（一列）。 每段增加一个（奇偶校验）冗余位ri ：,二、差错检测与校正 4.常用的简单差错控制编码（垂直奇偶校验）,垂直奇偶校验 编码效率： 能力： 检测出每列（段）中所有奇数（1、3）个错 突发错误的漏检率为50%! 在发送和接收的过程中进行编解码 水平奇偶校验：降低突发错误的漏检率 对各个信息段的相应位横向进行编码,二、差错检测与校正 4.常用的简单差错控制编码（水平奇偶校验）,水平奇偶校验 编码效率： 能力： 各段同一位上的奇数个错 长度小于等于p的突发差错 编码和检测相比垂直校验而言实现要复杂一些,二、差错检测与校正 4.常用的简单差错控制编码（水平垂直奇偶校验）,水平垂直奇偶校验,编码效率,二、差错检测与校正 4.常用的简单差错控制编码（水平垂直奇偶校验）,水平垂直奇偶校验能力 检测出： 所有3位或3位以下的错误、奇数位错 突发长度小于等于p+1的突发差错 很大一部分偶数位错：差错分布以致于某一行或者某一列有奇数个差错 部分纠错功能： 可以纠正1比特错 信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处,二、差错检测与校正 4.常用的简单差错控制编码（水平垂直奇偶校验）,水平垂直奇校验的例子,二、差错检测与校正 4.常用的简单差错控制编码（海明码）,1. 海明码 (1)海明距离及意义 两个码字中不同的位数的个数称为海明距离,简称H距离 1 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 求H距离的方法主要有:异或运算 海明距离的意义是:假如两个码字具有海明距离d ,则需要d 个位差错才能将其中一个码字转换成另一个.,H=3,二、差错检测与校正 4.常用的简单差错控制编码（海明码）,(2)海明码算法 将码字数内的位从最左边开始按顺序依次编号,第1位是1号,第2位是2号, 第n位是n号.编号为2的幂的位(1号位,2号位,4号位,8号位等)是校验位,其余的位填入m 位数据(2 r n+1). 每个校验位的取值应使得包括自己在内的一些位的集合符合规定的奇偶性.(主要用于奇偶性校验),二、差错检测与校正 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.常用的简单差错控制编码（海明码）,二、差错检测与校正 4.常用的简单差错控制编码（CRC循环冗余码）,纠错码的编码效率较低，差错控制经常采用检错码ARQ。循环冗余码CRC（Cyclic Redundancy Code ）是计算机网络中使用最为广泛的检错码，又称为多项式码。,二、差错检测与校正 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-32 G（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 （相当于10100010000）,二、差错检测与校正 4.常用的简单差错控制编码（CRC循环冗余码）,CRC的例子（2） 多项式除法后得到冗余码为1101，所以相应的数据发送序列为1010001 1101,二、差错检测与校正 4.常用的简单差错控制编码（CRC循环冗余码）,CRC校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。,CRC硬件实现,二、差错检测与校正 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 帧的同步,同步就是标识帧的开始与结束 常用的帧同步方法： 字符计数法 带字符填充的首尾界符法 带位填充的首尾标志法 违例编码法,字符计数法,首尾界符法,每一帧以ASCII字符序列DLE STX开始，以DLE ETX结束。 DLE为Data Link Escape 的缩写，STX意味着Start of Text， ETX代表 End of Text。 其缺点是成帧完全依赖于8位字符,STX,A,B,GOOD,BYE,ETX,A,B,GOOD,BYE,数据,组帧,字符填充,在首尾界符法中，由于数据中可能会出现DLE STX或DLE ETX，从而干扰帧的正常定界 字符填充法可用于解决上述问题。即发送端在数据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。,字节填充图例,(a) A frame delimited by flag bytes (b) Four examples of byte sequences before and after stuffing.,首尾标记法,每一帧使用一个特殊的位模式“01111110”作为开始和结束标记。 该位模式又称为flag 位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。,位填充,在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界 位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1”时，则在其后自动插队入一个“0”。该技术简称“逢五1插0”；接收端则忽略5个连续的“1”后面的“0”，简称“逢五1删0” 。,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) 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) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0,填充的位,比特填充图例,(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.,违例编码法,采用不可能出现在信息位中的比特编码作为帧的起始边界。 在物理层采用特定的比特编码方法时使用 曼彻斯特编码中电平的跳变表示1（低-高）和0（高-低） 高高和低低电平是违例编码,四、数据链路层协议 数据链路通信的简单模型,完全理想化的数据传输,完全理想化的数据传输基于以下两个假定 假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。 假定2： 不管发送方以多快的速率发送数据，接收方总来得及收下，并及时上交主机。(接收端向主机交付的数据速率永远不会低于发送端发送数据的速率),4.1 停等协议,停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。 具有最简单流量控制的数据链路层协议 仍保留假定1，但去掉假定2 链路是理想的传输信道，即所传送的任何数据既不会出差错也不会丢失 由接收方控制发送方的数据流(计算机网络中流量控制的一个基本方法)。,停等协议算法,在发送结点： （1）从主机取一个数据帧； （2）将数据帧送到数据链路层的发送缓存； （3）将发送缓存中的数据帧发送出去； （4）等待； （5）若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到（2）。 在接收结点： （1）等待； （2）若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存； （3）将接收缓存中的数据帧上交主机； （4）向发送结点发一信息，表示数据帧已经上交给主机； （5）转到(1)。,停等协议,两种数据传输比较,实用的停止等待协议,前提：去掉两个假定，即传输数据的信道不能保证使所传的数据不产生差错，而且还需对数据的发送端进行流量控制。 流量控制方法：等待发送 差错控制：发送方数据帧中加入校验码（CRC），由接收方检查；若正确，返回ACK，若出错，返回NAK；发送方根据收到的返回帧，决定发送新帧和重发。 帧丢失处理：超时定时器；以序号标识数据帧 优点：简单 缺点：信道利用率低，信道还远远没有被数据比特填滿,数据帧在链路上传输的几种情况,实用停止等待协议的算法,在发送结点： (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)nV(R)； 发送确认帧ACKn，转到(2)。 (期望接收n号数据帧，在它之前的帧收到了),停止等待协议的算法,V(S)=0,从主机取一帧,N(S)=V(S) 将帧送缓冲区,从发送缓冲区取出帧并发送,设置超时记时器tout,应答到？,ACK/NAK？,V(S)=(1-V(S),超时？,ACK,NAK,N,N,Y,Y,发送方,V(R)=0,帧收到？,接收帧并作差错校验,结果正确？,N(S)=V(R)?,将收到的帧中的数据部分送主机,V(R)=(1-V(R),发NAK,发ACK,丢弃此帧,N （重复帧）,Y,Y,Y,N,N,接收方,停止等待协议中数据帧和确认帧的发送时间关系,A,B,DATA,DATA,ACK,传播时延 tp,处理时间 tpr,确认帧发送时间 ta,传播时延 tp,处理时间 tpr,时间,两个成功发送的 数据帧之间的 最小时间间隔,数据帧的 发送时间,tf,设置的 重传时间,tout,停等协议的信道利用率,停等协议在开始传输一个数据帧 到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。,4.2 Go-back-N连续ARQ协议,工作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送。接收方只允许顺序接收，也就是说如果一帧出错，则它后面的N帧尽管可能正确到达接收方，但被直接丢弃，不发送确认。发送方将超时，按序重传所有未被确认的帧。 优点：连续发送提高了信道利用率 缺点： 导致某些已正确接收的帧的重传，因此降低了发送效率 误码率较低时，连续ARQ优于停等协议；反之则不一定,Go-back-N连续ARQ协议,Go-back-N ARQ,4.3 滑动窗口(Sliding Window)的概念,发送窗口用来对发送端进行流量控制，而发送窗口的大小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)所示。,发,收,t0,t1,t2,t3,t4,t5,t6,t7,初始,发0帧,发1帧,收0帧 发ACK0,收ACK0,发2帧,收1帧 发ACK1,收ACK1,问题：如接收窗口大小为1，帧序号用3比特编码，则发送窗口最大值为多少？ WT 2n - 1,WT=2 WR=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） PPP,面向比特的链路层协议 IBM的SNA使用的数据链路协议SDLC（Synchronous Data Link Control protocol）； ANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure）； ISO修改SDLC，提出HDLC（High-level Data Link Control）； CCITT修改HDLC，提出LAP（Link Access Procedure）作为X.25网络接口标准的一部分，后来改为LAPB。,4.5.1 面向字符型协议实例：BSC,什么是面向字符型协议? 以字符为控制传输信息的基本单元 ASIIC码： 格式字符：SOH（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,面向字符型BSC协议的数据报文格式,面向字符型协议实例：BSC,建立、维护 与释放数据 链路流程图,4.5.2 面向比特型协议实例：HDLC,面向字符型数据链路层协议的缺点： 报文格式不一样； 不同字符集机器难以通信 传输透明性不好； 等待发送方式，传输效率低。 面向比特型协议的设计目标： 以比特作为传输控制信息的基本单元； 数据帧与控制 帧格式相同； 传输透明性好； 连续发送，传输效率高。,4.5.2 面向比特型协议实例：HDLC,HDLC -High-Level Data Link Control HDLC的帧结构 F（flag） ：固定格式 01111110 作用 帧同步 传输数据的透明性（零比特插入与删除） A（address） ：地址 C（control） ：帧的类型、帧的编号、命令与控制信息 I（information） ：网络层数据，Nmax = 256B CRC（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（receive ready） S = 10，RNR（receive not ready） S = 01，RJE（reject） S = 11，SREJ（select reject） U帧 ： 用于实现数据链路控制功能,U帧的格式与链路控制功能,控制字段格式,Control field of (a) An information frame. (b) A supervisory frame. (c) An unnumbered frame.,五、数据链路层的工作过程,简化的信息帧结构的表示方法,一个信息帧的表示,数据链路层的工作过程,无编号帧的表示方法 SNRM帧与UA帧结构的表示方法,正常响应模式数据链路工作说明,六、Internet中主要的数据链路层协议,SLIP （Serial Line IP） 串行线路的Internet数据链路层协议 PPP （ Point-to-Point Protocol） 点-点协议 SLIP与PPP用于串行通信的拨号线路上，是目前家庭计算机或公司用户通过ISP接到Internet主要的协议。,SLIP协议,SLIP出现于20世纪80年代初，最早是在BSD UNIX 4.2版操作系统上实现的; SLIP协议支持TCP/IP协议; 对数据报进行了简单的封装，然后来用RS-232接口串行线路进行传输; SLIP通常也用来将远程终端连接到UNIX主机，也可通过租用或拨号串行线路进行主机到路由器，以及路由器到路由器的通信。,典型的SLIP接入方式,Internet的家庭或小型公司用户通过调制解调器、电话网络连接到ISP的调制解调器； ISP的调制解调器再通过它的路由器接入Internet； SLIP系统一般可以发送和接收1006B的IP数据报。,SLIP协议的帧结构,RFC 1055文件对SLIP帧格式进行了讨论; SLIP帧头与帧尾的“CO”，是协议使用的惟一的一个控制字符; CO的二进制编码比特序列是1000011 0000000; CO的使用将影响SLIP帧数据的透明性;,SLIP协议的缺点,使用SLIP协议时，通信的双方都必须知道对方的IP地址，因为SLIP协议没有为它们提供相互交换地址信息的方法； 没有设置协议类型字段，不具备同时处理多种网络层协议的能力； 没有校验和字段，差错控制功能由高层的协议承担； SLIP协议并不是Internet的协议标准，因此不同版本的之间就会存在着差别，使得互连变得困难。,PPP协议基本特点,PPP协议是Internet标准，RFC 1660、RFC 1661定义了PPP协议与帧结构； PPP协议处理了差错检测，支持面向字符型协议与面向比特型协议,可以支持IP协议及其他一些网络层协议（例如IPX协议）； PPP协议不仅在拨号电话线，并且在路由器路由器之间的专用线上广泛应用; PPP协议是在大多数家庭个人计算机和ISP之间使用的协议，它可以作为在高速广域网和社区宽带网协议族的一部分。,PPP,PPP是因特网中广泛使用的点-点数据链路协议； 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字节，它标识出网络层协议数据域的类型。常 用的网络层协议的类型主要有： 0021HTCP/IP 0023HOSI 0027HDEC 数据字段：长度可变,PPP与HDLC帧格式,(a) PPP帧格式,(b) HDLC帧格式,PPP链路 up / down 过程（简单状态图）,PPP 协议的状态图,建立,失败,失败,NCP 配置,鉴别成功,通信 结束,载波 停止,检测到 载波,双方协商 一些选项,鉴别,网络,打开,终止,静止,链路控制帧（LCP）与网络控制帧（NCP）,链路控制帧（LCP） 网络控制帧（NCP）,4. 滑动窗口(Sliding Window),实际的通信往往是全双工通信； 捎带应答（piggybacking）：将确认序号携带在数据帧中传输，提高线路的效率； 推迟确认：当需要发送确认但没有要发送的数据时，可以让确认信息推迟一小段时间再发送； 滑动窗口协议：允许发送端在没有收到前一个帧的确认时，就可以发送后续的帧；接收端可以对正确收到的若干个帧同时进行确认。 滑动窗口协议的要点： 任何时刻发送进程维护一组帧序号，对应于一组已经发送但尚未被确认的帧，用一个发送窗口维护这些帧； 接收进程也维护一组帧序号，对应于一组允许接收的帧，用一个接收窗口维护这些帧序号。,发送窗口的概念,发送窗口中的序号代表已发送但尚未确认的帧； 窗口下沿代表最早发送但至今尚未确认的帧； 发送窗口中包含的序号数称为发送窗口的大小，它有一个最大值； 当发送窗口尚未达到最大值时，可以发送新的帧；当要发送新帧时，将窗口上沿加1后模2n，然后将该序号分配给新的帧； 当收到对窗口下沿帧的确认时，窗口下沿加1，将已被确认的帧移出发送窗口；（图） 每一个帧都有可能传输出错，所以发送窗口中的帧都必须保留在缓冲区里以备重传，当某个帧被移出发送窗口时，同时从缓冲区中删除； 当发送窗口达到最大值时，停止从网络层接收数据，直到有一个缓冲区空出来为止。,发送窗口和接收窗口图示,接收窗口的概念,接收窗口中的序号代表允许接收的帧，任何落在窗口外的帧都被丢弃，落在窗口内的帧存放到缓冲区里； 数据链路层必须按顺序将数据递交给网络层，接收窗口中顺序最早的帧为窗口下沿帧，其余的帧朝着窗口上沿的方向，顺序逐渐升高； 当接收端收到窗口下沿帧且校验正确时，将其交给网络层，向发送方发回一个确认，然后窗口整体向前移动一个位置；（图） 和发送窗口不同，接收窗口的大小是不变的，总是保持初始时的大小； 接收窗口大小为1，意味着数据链路层只能顺序接收数据，当接收窗口大于1时不是这样，但无论如何，数据链路层递交给网络层的帧都是有序的。,4.1 1位滑动窗口协议,该协议使用停-等方式，只用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）。,正常与非正常情况下协议的执行,Two scenarios for protocol 4. (a) Normal case. (b) Abnormal case.,管道化技术（