《华科控制系计算机网络复习资料》由会员分享，可在线阅读，更多相关《华科控制系计算机网络复习资料（86页珍藏版）》请在金锄头文库上搜索。
1、第三章 数据链路层,第三章 数据链路层,1 数据链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？ 2 如何保证数据链路的可靠？ 3 我们以后自己设计一个数据链路层，有没有值得借鉴的案例呢?,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,e.g,从层次上来看数据的流动,链路层: 工作环境,链路层: 工作环境,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,链路层,应用层,运输层,网络层,物理层,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层
2、,链路层,网络层,物理层,链路层,网络层,物理层,R1,R2,R3,H1,H2,仅从数据链路层观察帧的流动,链路层: 工作环境,两个 物理上连接的 设备: 主机-路由器, 路由器-路由器, 主机-主机 数据单元: frame（帧）,network link physical,M,frame,物理链路,数据链路协议,接口卡,链路层的服务,成帧 : 将分组封装入帧, 加上帧头, 帧尾 物理地址 放在帧首用来确定信源、信宿 不同于IP地址喔! 链路访问: 媒体访问控制协议定义了帧在链路上传输的规则 如果是共享介质，则需实现信道的访问 点对点介质则协议很简单 在两台物理上连接的设备之间实现可靠传递:
3、可靠传递是什么概念，回顾一下学过的知识!,链路层的服务 (续),错误检测: 信号衰减和噪声会导致出错. 接收端检测到错误时: 给发送端信号要求重发或丢弃出错帧 错误校正: 接受端检测某位错并加以校正 而无需要求发送端重发 流量控制: 保持收发双方的同步,链路层: 实现,通过 “adapter（网卡或适配器）” 实现 e.g., PCMCIA 卡, 以太网卡 一般适配器都含有: RAM, DSP 芯片, 主机的总线接口, 和链路接口,network link physical,M,frame,phys. link,data link protocol,adapter card,问题1：,1 数据
4、链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？,帧如何定界？-如何成帧,封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。 首部和尾部的一个重要作用就是进行帧定界。,帧结束,帧首部,IP 数据报,帧的数据部分,帧尾部, MTU,数据链路层的帧长,开始 发送,帧开始,3.1 数据链路层基本概念,3.1 数据链路层基本概念,成帧的四种方法 字符计数法 帧不定长，帧头中用一个字符来表示帧内的字符数 缺点：计数字段一旦出错，将无法再同步,3.1 数据链路层基本概念,成帧的四种方法 带填充字符的首尾界符法 以特定
5、的字符序列为控制字段（起始字符 DLE STX，结束字符DLE ETX） 缺点：依赖于字符集（8位字符和ASCII字符），不通用，也无法扩展,3.1 数据链路层基本概念,形成帧的四种方法 带位填充的首尾标记定界法 帧的起始和结束都用一个特殊的位串“01111110”，称为标记（flag） “0”比特插入删除技术 (参动画),3.1 数据链路层基本概念,形成帧的四种方法 物理层编码违例法 IEEE802协议中：高-低电平对表示“1”，低-高电平对表示“0”。高-高/低-低不表示数据，可以用来做定界符。 只适用于在物理媒体的编码策略中采用了冗余技术的网络；优点：无需填充。 注意 在很多数据链路协议
6、中，使用字符计数法和一种其它方法的组合。,第三章 数据链路层,1 数据链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？ 2 如何保证数据链路的可靠？,问题2：如何保证数据链路的可靠？,帧如何出错我们怎么能知道？ 若出错了怎么办? 如何控制数据链路中帧的传输速率和效率？,错误检测： EDC= 错误检测校正（Error Detection and Correction (冗余数据)）位 错误检测不可能达到 100% 可靠! 协议算法可能会忽略了某些错误, 但比例极小 较大的 EDC 字段可以产生较好的检错和纠错效果,3.2 差错控制加了它就可能知道？,3.2
7、.1 差错控制的基本概念,目的 确保帧可靠且按照正确的顺序传送到接收方 能够达到校验或改正下一层数据差错 编码技术 纠错编码 能够校正检测到的错误，开销大，不适合用于网络通信 检错编码：检测收到帧的差错，处理方法： 提示上层处理或者不处理 要求重传错误帧,3.2.1 差错控制的基本概念,差错出现的特点 随机，连续突发 计算机网络中处理差错的两种基本策略 使用纠错码（海明码） 发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。 使用检错码（奇偶校验、CRC） 发送方在每个数据块中加入必要的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里
8、有错。,3.2.1 差错控制的基本概念,奇偶校验 在传送数据的各位之外，再传送1位奇/偶校验位。 奇校验 所有传送的数位（含字符的各数位和校验位）中，“1”的个数为奇数。 偶校验 所有传送的数位（含字符的各数位和校验位）中，“1”的个数为偶数。,奇偶校验,单比特校验: 检测一位错误,两维单比特校验: 检测和校正单比特错误,0,0,3.2.2 海明纠错码,海明纠错码的格式 码字的编号从左到右，最左边是第一位，其中2的幂数位是检验位，其余是k个数据位(信息元)。 海明纠错码格式如下： 20 21 22 23 24 p1 p2 * p3 * * * p4* * * * * * * p5 *-信息元
9、P-校验位,3.2.2 海明纠错码,海明码的编码与译码的方法 用矩阵乘法求检验位，并且找出错误位。设编码长度为 n = 2r 1，其中r为校验码的位数。 数据位长度 k = n r。 校验位插入到编码序列的2j-1 (j=1,2,r)的位置上；由r(样本)建立一个(2r -1)行 * r列的矩阵。,3.2.2 海明纠错码,将编码字写成串形式的一维向量,其中，l1 =l2 =lr =1或0(l=0为偶校验，l=1为奇校验)； bij = 1 或 0,3.2.2 海明纠错码,例: 按下列步骤将数据(信息)1100进行编码，设校验位为r=3。 解: (1)编码长度 n = 2r 1 = 7 数据位
10、k = n r = 4 校验位 r = 3,3.2.2 海明纠错码,(2)编码过程,由矩阵乘法得，p1 = 0 ,p2 = 1, p3 = 1 解得海明码为 0111100,3.2.3 循环冗余码(CRC),循环冗余码（CRC） 基本思想 收发双方约定一个生成多项式G(x)（其最高阶和最低阶系数必须为1），发送方在帧的末尾加上校验序列，使带校验序列的帧的多项式能被G(x)整除；接收方收到后，用G(x)除多项式，若有余数，则传输有错。 多项式码 将位串看成系数为0或1的多项式 如：110001，表示成多项式 x5+x4+1,3.2.3 循环冗余码(CRC),循环冗余码（CRC） CRC的计算算法
11、,在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)。 循环冗余检验 CRC 和帧检验序列 FCS并不等同。 CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。 FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。,3.2.3 循环冗余码(CRC),3.2.3 循环冗余码(CRC),循环冗余码（CRC） 常用的CRC生成多项式 CRC-12=x12+x11+x3+x2+x+1 CRC-16=x16+x15+x2+1 CRC-CCITT=x16+x12+x5+1,差错控制 差错控制编码 检错码和纠错码 差
12、错控制技术 差错控制的基本方法：接收方进行差错检测，并向发送方应答，告知是否正确接收。 流量控制 自动请求重传Automatic Repeat Request （ARQ） 停等 ARQ Go-back-N ARQ 滑动窗口协议,3.3差错控制和流量控制,3.3.1 停止等待协议的原理,原理 发送方发送完一帧数据后，必须等待接收方的确认帧返回，确认数据被正确接收后才能继续发送下一帧。,3.3.1 停止等待协议的原理,过程,从 主 机 取 数 据,上 交 主 机,DATA1,DATA2,结点 A,结点 B,ACK,ACK,3.3.2 单工肯定应答/重传停等协议,单工肯定应答/重传停等协议的提出 通
13、信信道总是存在误码率，传输过程中难免要出错，造成发送帧或应答帧出错或丢失。,3.3.2 单工肯定应答/重传停等协议,问题1：发送帧出错或丢失怎么办？ 设置计时器，利用超时中断防止因帧丢失所造成的死锁。 问题2：应答帧出错或丢失怎么办？ 设置帧序号，利用序号检查是新帧还是重复帧。 问题3：帧序号字段需占用多少位？ 根据停等协议的定义，表示帧发送序号的字段只需占用一位，因为只需检查前后两帧的顺序是否相同，而不注重各帧的顺序号本身的值是多少。,3.3.2 单工肯定应答/重传停等协议,例：发送帧本身序号为 0 1 2 3 4 5 6 7 停等协议帧序号为 0 1 0 1 0 1 0 1 同理，帧确认序
14、号也只需占用一位。,为便于判断序号的正确性，通常定义帧确认序号(ACK)为期望发送方下次发送的帧序号(SEQ)，表达式为： ACK=SEQ+1(mod 2),3.3.2 单工肯定应答/重传停等协议,过程 发送方将当前信息帧作为待确认帧保存在缓冲区 发送数据的同时起动计时器 接收方收到数据后返回一个确认帧 若接收方收到的数据有错，则丢弃 发送方若在规定时间内没有收到确认帧，则计时器清零，重发缓冲区内的信息帧,3.3.2 单工肯定应答/重传停等协议,3.3.3 双工停等协议,双工停等协议 双工协议在通道的每个方向都有发送帧(数据帧)和应答帧， 为了区分它们，需要在帧的控制信息中增加一个帧类型的字段
15、。 “背回”(Piggybacking)技术 如果某站收到对方的数据后，在给对方发送应答帧的同时，又有数据帧要发往对方，则不必单独发送应答帧，可以在数据帧中增加一个接受顺序号字段(ACK字段)以存放应答信息，于是对方在收到数据帧的同时也得到了应答。,3.3.3 双工停等协议,背回应答的优点： 减少了帧的发送数目 能有效地利用通道，且接收站的“帧正确到达”中断次数和接收站的输入缓冲区均可以减少。 但是背回应答增加了协议的复杂性。,3.3.3 双工停等协议,在双工停等协议中： 去掉了高层始终有信息发送的假定，使协议接近数据通信的实际情况。 但规定发送一帧后要等到应答后才能发送下一个新帧(所谓停等协
16、议)。,高层并非始终有信息发送，应答帧何时发送？ 解决办法：设置ACK计时器,3.4 连续ARQ协议,连续ARQ又称为Go-Back-N ARQ 当出现差错必须重传时，要向回走N个帧，然后开始重传。 原理 发送端连续发送至发送缓冲区窗口满 接收缓冲区窗口大小为1帧，对丢弃帧不确认 发送方设置超时，若超时回退若干帧到未被确认帧开始重传 接收方从出错帧起丢弃所有后继帧,3.4 连续ARQ协议,特点 发送方需要较大的缓冲区，以便重传 减少了等待时间，提高了吞吐量 发送帧和接受帧都要进行编号 适于信道出错率较少的情况 问题 信道误码率高时，对损坏帧和非损坏帧的重传非常多，反而降低效率,3.4 连续ARQ协议,注意的问题 接收端按序接收。例如：2号帧出错但收到正确的3号帧仍然丢弃3号帧从2号帧开始重传 ACK1表示确认0
