《计算机网络课件第3章数据链路层.ppt》由会员分享，可在线阅读，更多相关《计算机网络课件第3章数据链路层.ppt（41页珍藏版）》请在三一办公上搜索。
1、计算机网络Computer Network,2023年9月15日,2,计算机网络-刘桂江,课程目录,第1章概述第2章物理层与数据通信基础第3章数据链路层第4章局域网第5章网络层第6章网络互联技术第7章传输层第8章应用层第9章网络管理与信息安全第10章 网络新技术专题,3,计算机网络-刘桂江,本章提纲,3.1数据链路层的功能 3.2差错检测和校正 3.3数据链路层协议 3.4协议描述与验证 3.5数据链路层协议举例,第3章数据链路层,4,计算机网络-刘桂江,3.1 数据链路层的功能,3.1.1 帧同步 3.1.2 差错控制 3.1.3 流量控制 3.1.4 链路管理,5,计算机网络-刘桂江,3.
2、1.1 帧同步,帧同步：能从比特流中区分出帧的起始与终止。1、字节计数法 以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数。2、使用字符填充的首尾定界符法 用一些特定的字符来定界一帧的起始与终止。数据的透明性,C,count,data,C,data,C,C,D,6,计算机网络-刘桂江,3.1.1 帧同步,3、使用比特填充的首尾定界符法 以一组特定的比特模式(如01111110)来标志一帧的起始与终止。数据的透明性4、违法编码法 借用违法编码序列来定界帧的起始与终止。例:在物理层，若用曼彻斯特编码时，高低表示”1”,低高表示”0”，则可用高高或低低表示起止。,01111110,d
3、ata,01111110,01111110,011111010,7,计算机网络-刘桂江,3.1.2 差错控制,通信系统必须具备发现(即检测)差错的能力，并采取措施纠正它，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功能之一。反馈重发计时器帧序号,A,B,防止死等待,防止重复帧多次被接收方交给它的上一层,8,计算机网络-刘桂江,3.1.3 流量控制,流量控制就是对发送方发送数据的流量进行控制，使其发送速率不超过接收方的接收速率。流量控制并不是数据链路层特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已。,9,计算机网络-刘桂江,3.1.
4、4 链路管理,数据链路层连接的建立、维持和释放就称做链路管理。链路管理功能主要是用于面向连接的服务。,10,计算机网络-刘桂江,3.2差错检测和校正,3.2.1 传输差错的特性 3.2.2 奇偶校验 3.2.3 循环冗余校验 3.2.4 海明码,11,计算机网络-刘桂江,3.2.1 传输差错的特性,传输中的差错都是由于噪声引起的。噪声有两大类：一类是信道所固有的、持续存在的随机热噪声；另一类是由于外界特定的短暂原因所造成的冲击噪声。误码率编码效率检错码和纠错码差错控制的方式：自动请求重发（ARQ）前向纠错(FEC),12,计算机网络-刘桂江,3.2.2 奇偶校验(1/2),奇偶校验的特点：奇偶
5、校验码是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法,它是一种检错码。偶校验:r=I1I2Ip奇校验:r=I1I2Ip1奇偶校验的分类：垂直奇偶校验 编码效率 R=p/(p+1),r1 r2 rq 冗余位,13,计算机网络-刘桂江,3.2.2 奇偶校验(2/2),水平奇偶校验 编码效率 R=q/(q+1)水平垂直奇偶校验编码效率 R=pq/(p+1)(q+1),14,计算机网络-刘桂江,3.2.3 循环冗余校验(1/3),它是一种检错码。思想：任何一个由二进制数位串组成的代码都可以和一个只含0和1两个系数的多项式建立一一对应的关系。k位信息位对应于一个k-1次多项式K(x)
6、，r位冗余位对应于一个r-1次多项式R(x)，生成的n=k+r位码字则对应于一个n-1次多项式T(x)。生成方法：发送方和接收方依据一事先约定的r次生成多项式G(x)（最高项xr和最低项的系数为1），用G(x)去除xrK(x)得到的余式就是R(x)，即得冗余位。,15,计算机网络-刘桂江,3.2.3 循环冗余校验(2/3),示例 设信息位为1010001，即K(x)=x6+x4+1，取G(x)=x4+x2+x+1（对应的代码为10111），则x4 K(x)=x10+x8+x4（所以冗余位为1101，R(x)=x3+x2+1。T(X)=x4K(x)+R(x)=x10+x8+x4+x3+x2+1,
7、16,计算机网络-刘桂江,3.2.3 循环冗余校验(3/3),检测方法：接收端用接收到的码字多项式除以生成多项式G(x)，若余式不为0，则传输有差错；否则，认为传输无差错。,17,计算机网络-刘桂江,3.2.4 海明码(1/4),是一种可以纠正一位差错的编码。对于奇偶校验码，若信息位为an-1an-2a1，加上一位偶校验位a0，在接收端校验时，可按关系式 S=an-1 an-2 a0来计算，若S=0，则无错；若S=1，则有错。上式称为监督关系式，S称为校正因子。思想：增加冗余位，也相应地增加监督关系式和校正因子，就能表示更多的差错情况，包括具体定出是哪一位出错。,Richard W Hammi
8、ng,18,计算机网络-刘桂江,3.2.4 海明码(2/4),理论依据：当信息位为k位，增加r个冗余位，构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同的位置的一位错，则要求：2rk+r+1。生成过程：（假设k=4，则r取3，信息位a6a5a4a3，冗余位a2a1a0）（1）构造监督关系式表,19,计算机网络-刘桂江,3.2.4 海明码(3/4),（2）写出监督关系式由上表可知，a2、a4、a5 或a6的一位错都应使S2=1，所以令 S2=a2 a4 a5 a6 同理 S1=a1 a3 a5 a6 S0=a0 a3 a4 a6（3）求出冗余位关系式令S
9、0、S1 和S2为0，即可求出a0、a1和a2：a2=a4 a5 a6 a1=a3 a5 a6 a0=a3 a4 a6 示例（P69 表3.2）,20,计算机网络-刘桂江,3.2.4 海明码(4/4),纠错 在接收端收到每个码字后,按监督关系式算出校正因子,若它们全为“0”,则认为无错;若不全为“0”,在一位错的情况下,可查监督关系式表来判定是哪一位错,从而纠正之。（示例 P68）特点：（1）编码效率为k/k+r（上例4/7）；（2）较容易实现，但只能纠正1位错。,21,计算机网络-刘桂江,3.3 数据链路层协议,3.3.1 基本链路控制协议 3.3.2 滑动窗口协议,22,计算机网络-刘桂江
10、,3.3.1 基本链路控制协议(1/7),ARQ（自动重发请求）协议是数据链路层最基本的协议。它是指在接收站接收到包含出错数据的信息（帧）时，自动发出重传错帧的请求。ARQ的作用原则是对出错的数据帧自动重发，它有三种形式：停等ARQ协议连续ARQ协议选择重传ARQ协议,23,计算机网络-刘桂江,3.3.1 基本链路控制协议(2/7),1、停等ARQ协议：工作原理发送方发送一个数据帧后，必须停下来等待接收方的确认帧后才可以发送下一个数据帧；在接收方接收错误时，接收方则发一否认帧，要求发送方重发该帧；为防止发送的数据丢失，发送方内部设置一个定时器，当超过定时时间，而发送方仍未收到确认帧时，发送方重
11、发该帧；为防止确认帧丢失而造成接收方接收并递交重复帧，要求发送方给每一个数据帧带上一个序列号。,24,计算机网络-刘桂江,3.3.1 基本链路控制协议(3/7),停等ARQ协议的缺点：停等ARQ协议虽然保证了传输的安全可靠，但在传输过程中信道的利用率太低。,25,计算机网络-刘桂江,3.3.1 基本链路控制协议(4/7),2、连续ARQ协议：工作原理连续ARQ是连续发送若干数据帧，如果发送方接收到接收端发回的确认帧，则继续发送；发送方在每发完一个数据帧后，就启动内部计时器，在设置的超时时间内未收到该帧的确认帧，则重发该数据帧及其后的N帧，故又称为回退N协议。,26,计算机网络-刘桂江,3.3.
12、1 基本链路控制协议(5/7),连续ARQ协议的缺点：连续ARQ协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（但仅因这些数据帧之前有一个数据帧出了错），这样又使传送速率降低。由此可见，若传输信道的传输质量很差而误码率较大时，连续ARQ协议不一定优于停等ARQ协议。,27,计算机网络-刘桂江,3.3.1 基本链路控制协议(6/7),3、选择重传ARQ协议：工作原理当接收方发现某帧出错后，其后继续送来的正确帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可
13、以与原来已存于缓冲区中的其余帧一并按正确的顺序递交高层。,28,计算机网络-刘桂江,3.3.1 基本链路控制协议(7/7),选择重传ARQ协议的缺点：选择重传减少了浪费，但要求接收方有足够大的缓冲区空间，这在许多情况下是不够经济的。以上三种协议各有利弊，停等ARQ协议最简单，但信道利用率最低；选择重传ARQ协议信道利用率最高，但它要求接收端的缓冲容量相当大；连续ARQ协议介于两者之间。,29,计算机网络-刘桂江,发送的信息帧都有一个序号，从0到某个最大值，02n1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下
14、界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变。发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1。接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的序号最小的帧。接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。,3.3.2 滑动窗口协议(1/2),30,计算机网络-刘桂江,3.3.2 滑动窗口协议(2/2),主要的滑动窗口协议：停等协议 回退n协议 选择重传协议 滑动窗口协议的工作原理示意图：,
15、31,计算机网络-刘桂江,3.4 协议描述与验证,3.4.1 有限状态机模型 3.4.2 Petri网模型,32,计算机网络-刘桂江,3.4.1 有限状态机模型,有限状态机（Finite State Machine，FSM）是一种用来描述系统的常用方法。在这个模型中，系统被描述成有限的状态，在一定的前提条件下会发生一系列的输入事件，这些事件使得系统采取相应的动作，并从一个状态转换成另一个状态，称为状态的变迁或转换（Transition）。,33,计算机网络-刘桂江,3.4.2 Petri网模型,Petri网是由德国学者首先提出的一种描述方法,它本质上也是一种有限状态机模型。Petri网的描述中
16、有四种基本元素：位置(Place)位置是一圆圈，表示可能进入的状态 标记(Token)位置中的小圆黑点，某个位置中有标记就表示已处于该状态 变迁(Transition)用一根直线段来表示,指明了该变迁发生的条件 带箭头的弧线(Arc)用弧线来表示,指明变迁产生的条件和变迁产生的结果,34,计算机网络-刘桂江,3.5 数据链路层协议举例,3.5.1 数据链路层协议的分类 3.5.2 HDLC 3.5.3 SLIP和PPP,35,计算机网络-刘桂江,3.5.1 数据链路层协议的分类,链路控制协议的分类：异步协议 以字符为独立的信息传输单位，在每个字符的起始处开始对字符内的比特实现同步，但字符与字符
17、之间的间隔时间是不固定的(即字符之间是异步的)。同步协议以帧为传输单位，在帧的起始处同步，使帧内维持固定的时钟。同步协议的分类：面向字符的同步协议 面向比特的同步协议面向字节计数的同步协议,36,计算机网络-刘桂江,3.5.2 HDLC(1/2),1、HDLC的操作方式：所谓操作方式，通俗地讲就是某站点是以主站点方式操作还是以从站方式操作，或者是二者兼备。HDLC操作方式的类型：正常响应方式这是一非平衡数据链路方式，有时也称非平衡正常响应方式，传输过程由主站启动。异步响应方式这也是一种非平衡数据链路操作方式，传输过程由从站启动。异步平衡方式这是一种允许任何节点来启动传输的操作方式。,37,计算
18、机网络-刘桂江,3.5.2 HDLC(2/2),2、HDLC的帧格式：3、HDLC的帧类型：信息帧(I帧)信息帧用于传送有效信息或数据。监控帧(S帧)监控帧用于差错控制和流量控制。无编号帧(U帧)无编号帧因其控制字段中不包含编号N(S)和N(R)而得名。U帧用于提供对链路的建立、拆除以及多种控制功能。,38,计算机网络-刘桂江,3.5.3 SLIP和PPP(1/4),1、SLIP协议：串行线路网际协议SLIP用于运行TCP/IP协议的面向字符的点对点串行连接，早在1984年就已经开始使用。SLIP通常专门用于路由器和路由器之间的串行连接，有时候也用于家庭主机和ISP的路由器之间的拨号连接，使用
19、的线路速率一般介于1200bit/s和19.2Kbit/s之间。主要用于低速的交互性业务。,39,计算机网络-刘桂江,3.5.3 SLIP和PPP(2/4),SLIP协议的缺点：SLIP没有差错检测的功能。通信的每一方必须事先知道对方的IP地址，这对拨号入网的用户是很不方便的。SLIP仅支持IP，而不支持其他的协议。SLIP并未成为Internet的标准协议。因此目前存在着多种互不兼容的版本，影响了不同网络的互联。,40,计算机网络-刘桂江,3.5.3 SLIP和PPP(3/4),2、PPP协议PPP协议的三个组成部分：一个将IP数据报封装到串行链路的方法。一个用来建立、配置和测试数据链路连接的链路控制协议LCP（Link Control Protocol），通信的双方可协商一些选项。一套网络控制协议NCP（Network Control Protocol），支持不同的网络层协议，如IP、IPX。,41,计算机网络-刘桂江,3.5.3 SLIP和PPP(4/4),PPP协议的帧格式：PPP协议的特点：PPP协议是面向字符型的，所以它不能采用HDLC所使用的零比特插入法，而是使用一种特殊的字符填充。PPP不使用序号和确认，因此，PPP不提供可靠传输的服务。,
