第3章 数据链路层.ppt

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