3 数据链路层 谢希仁 计算机网络 华科考研复试 习题.ppt

1、第三章 数据链路层,第三章 数据链路层,1 数据链路是什么？物理层实现了bit流透明传输，按bit流进行数据传输存在什么问题？ 2 如何保证数据在链路上的可靠传输？ 3 我们以后自己设计一个数据链路层，有没有值得借鉴的案例呢?,链路层: 工作环境,链路层: 工作环境,两个 物理上连接的 设备: 主机-路由器, 路由器-路由器, 主机-主机 数据单元: frame（帧）,链路层: 实现,通过 “adapter（网卡或适配器）” 实现 e.g., PCMCIA 卡, 以太网卡 一般适配器都含有: RAM, DSP 芯片, 主机的总线接口, 和链路接口,network link physical,M

2、,frame,phys. link,data link protocol,adapter card,链路层的服务,帧同步 帧的可靠传输 什么样的传输是可靠传输？ 差错控制 流量控制 链路访问机制（广播式链路）,差错控制基本概念,什么是差错控制？ 在通信过程中，发现、检测差错并进行纠正 为何要进行差错控制？ 不存在理想的信道传输总会出错 产生差错的原因： 信号衰减和热噪声 信道的电气特性引起信号幅度、频率、相位的畸变； 信号反射，串扰； 冲击噪声，闪电、大功率电机的启停等。,问题1：,帧如何定界（同步）？,帧同步,形成帧的四种方法 字符计数法 帧不定长，帧头中用一个字符来表示帧内的字符数 缺点：

3、计数字段一旦出错，将无法再同步,帧同步,形成帧的四种方法 带填充字符的首尾界符法 以特定的字符序列为控制字段（起始字符 DLE STX，结束字符DLE ETX） 缺点：依赖于字符集（8位字符和ASCII字符），不通用，也无法扩展,帧同步,形成帧的四种方法 带位填充的首尾标记定界法 帧的起始和结束都用一个特殊的位串“01111110”，称为标记（flag） “0”比特插入删除技术 (参动画),帧同步,形成帧的四种方法 物理层编码违例法 IEEE802协议中：高-低电平对表示“1”，低-高电平对表示“0”。高-高/低-低不表示数据，可以用来做定界符。 只适用于在物理媒体的编码策略中采用了冗余技术的

4、网络；优点：无需填充。 注意 在很多数据链路协议中，使用字符计数法和一种其它方法的组合。,第三章 数据链路层,1 数据链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？ 2 如何保证帧在数据链路上的可靠传输？,我们如何知道帧是否出错？ 若出错了怎么办?,如何使帧的发送速率和接收速率匹配？,问题2,差错控制和流量控制,差错控制 差错控制编码 检错码和纠错码 差错控制技术 差错控制的基本方法：接收方进行差错检测，并向发送方应答，告知是否正确接收。 流量控制 自动请求重传Automatic Repeat Request （ARQ） 停等 ARQ Go-back-

5、N ARQ 滑动窗口协议,差错控制编码原理,EDC= 错误检测校正（Error Detection and Correction (冗余数据)）位 D = 由检验位保护的数据, 可包括首部字段 错误检测不可能达到 100% 可靠! 协议算法可能会忽略了某些错误, 但比例极小 较大的 EDC 字段可以产生较好的检错和纠错效果,差错控制编码,奇偶检验（检错码） 海明纠错码（纠错码） 循环冗余码(CRC)（检错码）,奇偶检验,原理： 在原始数据字节的最高位（或最低位）增加一个奇偶校验位，使结果中1的个数为奇数（奇校验）或偶数（偶校验）。 例如：1100010增加偶校验位后为11100010 注意：

6、只能检测出奇数个位错，偶数个位错则不能检出。,海明纠错码,海明纠错码 海明纠错码的格式 码字的编号从左到右，最左边是第一位，其中2的幂数位是检验位，其余是k个数据位(信息元)。 海明纠错码格式如下： 20 21 22 23 24 p1 p2 * p3 * * * p4* * * * * * * p5 *-信息元 P-校验位,海明纠错码,海明码的编码与译码的方法 用矩阵乘法求检验位，并且找出错误位。 设编码长度为 n = 2r 1，其中r为校验码的位数。数据位长度 k = n r。 校验位插入到编码序列的2j-1 (j=1,2,.,r)的位置上；由r(样本)建立一个(2r -1)行 * r列的矩

7、阵。,海明纠错码,将编码字写成串形式的一维向量,其中，l1 =l2 =lr =1或0(l=0为偶校验，l=1为奇校验)； bij = 1 或 0,海明纠错码,例: 按下列步骤将数据(信息)1100进行编码，设校验位为r=3。 解: (1)编码长度 n = 2r 1 = 7 数据位 k = n r = 4 校验位 r = 3,海明纠错码,(2)编码过程,由矩阵乘法得，p1 = 0 ,p2 = 1, p3 = 1 解得海明码为 0111100,循环冗余码(CRC),循环冗余码（CRC） 基本思想 收发双方约定一个生成多项式G(x)（其最高阶和最低阶系数必须为1），发送方在帧的末尾加上校验序列，使带

8、校验序列的帧的多项式能被G(x)整除；接收方收到后，用G(x)除多项式，若有余数，则传输有错。 多项式码 将位串看成系数为0或1的多项式 如：110001，表示成多项式 x5+x4+1,循环冗余码(CRC),循环冗余码（CRC） CRC的计算算法,循环冗余码(CRC),循环冗余码（CRC） 常用的CRC生成多项式 CRC-12=x12+x11+x3+x2+x+1 CRC-16=x16+x15+x2+1 CRC-CCITT=x16+x12+x5+1 检错能力：CRC-16和CRC-CCITT可以捕捉突发错长度小于16的全部错误、长度为17的突发错的99.998、长度为18以上的突发错的99.99

9、7。,差错编码比较,结论： 1.CRC检错能力强。 2.是线性码，有良好的结构，易于硬件实现。,差错控制和流量控制,差错控制 差错控制编码 检错码和纠错码 差错控制技术 差错控制的基本方法：接收方进行差错检测，并向发送方应答，告知是否正确接收。 流量控制 自动请求重传Automatic Repeat Request （ARQ） 停等 ARQ Go-back-N ARQ 滑动窗口协议,停止等待协议的原理,原理 发送方发送完一帧数据后，必须等待接收方的确认帧返回，确认数据被正确接收后才能继续发送下一帧。,停止等待协议的原理,过程,从 主 机 取 数 据,上 交 主 机,DATA1,DATA2,结点

10、 A,结点 B,ACK,ACK,思考,问题1：发送帧出错或丢失怎么办？ 设置计时器，利用超时中断防止因帧丢失所造成的死锁。 问题2：应答帧出错或丢失怎么办？ 设置帧序号，利用序号检查是新帧还是重复帧。 问题3：帧序号字段需占用多少位？ 根据停等协议的定义，表示帧发送序号的字段只需占用一位，因为只需检查前后两帧的顺序是否相同，而不注重各帧的顺序号本身的值是多少。,帧序号讨论,例：发送帧本身序号为 0 1 2 3 4 5 6 7 停等协议帧序号为 0 1 0 1 0 1 0 1 同理，帧确认序号也只需占用一位。 为便于判断序号的正确性，通常定义帧确认序号(ACK)为期望发送方下次发送的帧序号(SE

11、Q)，表达式为： ACK=SEQ+1(mod 2),单工停等协议,过程 发送方将当前信息帧作为待确认帧保存在缓冲区 发送数据的同时起动计时器 接收方收到数据后返回一个确认帧 若接收方收到的数据有错，则丢弃 发送方若在规定时间内没有收到确认帧，则计时器清零，重发缓冲区内的信息帧,单工停止等待协议,过程(参考动画演示:停止等待协议),单工停等协议,双工停等协议,问题1：如何区分发送帧(数据帧)和应答帧？ 在帧的控制信息中增加一个帧类型的字段。 问题2：如果某站收到对方的数据后，在给对方发送应答帧的同时，又有数据帧要发往对方，能不能只发送一帧？ 采用“背回”(Piggybacking)技术。可以在数

12、据帧中增加一个接受顺序号字段(ACK字段)以存放应答信息，于是对方在收到数据帧的同时也得到了应答。,背回技术的讨论,背回应答的优点： 减少了帧的发送数目(因为减少了单独应答帧)； 能有效地利用通道，且接收站的“帧正确到达”中断次数和接收站的输入缓冲区均可以减少。 但是背回应答增加了协议的复杂性。,背回技术的讨论,问题3：高层并非始终有信息发送，应答帧何时发送？ 解决办法：设置ACK计时器,连续ARQ协议,连续ARQ又称为Go-Back-N ARQ 当出现差错必须重传时，要向回走N个帧，然后开始重传。 原理 发送端连续发送至发送缓冲区窗口满 接收缓冲区窗口大小为1帧，对丢弃帧不确认 发送方设置超

13、时，若超时回退若干帧到未被确认帧开始重传 接收方从出错帧起丢弃所有后继帧,连续ARQ协议,特点 发送方需要较大的缓冲区，以便重传 减少了等待时间，提高了吞吐量 发送帧和接受帧都要进行编号 适于信道出错率较少的情况 问题 信道误码率高时，对损坏帧和非损坏帧的重传非常多，反而降低效率,连续ARQ协议,注意的问题 接收端按序接收。例如：2号帧出错但收到正确的3号帧仍然丢弃3号帧从2号帧开始重传 ACK1表示确认0号帧DATA0，期望下次收到1号帧，依次类推 思考 实际的连续ARQ利用一个计时器实现N个独立超时计数器的功能，思考这如何实现？,滑动窗口协议,采用窗口的原因 应对以发送出去但尚未被确认的帧

14、的数目加以限制。 要重复循环使用帧的序号，避免无止境的帧序号的增大。 发送窗口 在发送端。用来对发送方进行流量控制。 发送窗口的大小：能够存放的待确认帧的最大数目。 接收窗口 在接收端。用来指示接收方允许接收的帧的序号。,滑动窗口协议,滑动窗口实例：发送窗口=2；接收窗口=1 初态：发送端无数据发出，接受端0号窗口打开准备接收数据 发送端发出0号帧，0号窗口被占用；此时接收端尚未收到数据 发送端发出1号帧，1号窗口被占用；此时接收端尚未收到数据。发送方停止发送数据。 接收端0号帧收到，关闭其0号窗口，打开1号窗口等待接受 发送方收到接收端发来的确认后，关闭0号窗口 发送方发送2号帧，占用2号窗

15、口，然后暂停发送 依次类推循环，达到了限止发送帧的数目，又避免了帧序号重复时的歧义。,滑动窗口协议,滑动窗口实例：发送窗口=2；接收窗口=1,滑动窗口协议,各种协议规定的缓冲窗口大小 停止等待：发送窗口=1，接收窗口=1 Go Back n：发送窗口1，接收窗口=1 滑动窗口：发送窗口1，接收窗口1,滑动窗口结论,令发送窗口为WT，接收窗口为WR 。发送序号用n个比特表示。 结论1：若WR1，则WT2n1 例如n=3，（WT）max7 结论2：WR2n/2，WT= WR=2n/2 例如n=3 ，则WT= WR=4,链路层的服务,帧同步 帧的可靠传输 什么样的传输是可靠传输？ 差错控制 流量控制

16、 链路访问机制（广播式链路）？,链路和协议,有三种类型的 “链路”: 点对点 ( e.g. PPP, SLIP) 广播式 (共享线路或介质; e.g, 以太网, 无线网, etc.) 交换式 (e.g., 交换式以太网, ATM etc),点对点的数据链路协议（DLC）,一方发,一方收,一条链路:比广播信道简单的多 无需介质访问控制 不必进行MAC寻址 e.g., 拨号链路, ISDN 线路等 常见的点对点DLC协议: SLIP (Serial Line Internet Protocol) PPP (point-to-point 协议) SDLC: Synchronous Data Link

17、 Control (SNA的面向比特的数据链路规程) HDLC: High level data link control (ISO高级数据链路控制),多点访问协议,一条共享的通信信道 两个或多个结点可同时发送信号: 相互干扰 在某一时刻只有一个结点可以成功地发送信号 多点访问协议: 分布式的算法来决定如何共享信道, i.e., 决定工作站何时可以发送 注意：有关共享通道的通信（协商）也必须在该通道自身上解决! 我们希望多点访问协议能够解决什么问题: 同步还是异步 了解其他站点的信息 健壮性 (e.g.如何对待信道错误) 性能,点到点数据链路层协议案例,案例1：高级数据链路控制规程,HDLC

18、面向比特的数据链路层协议(规程） 使用HDLC的语法可以定义多种具有不同操作特点的链路层协议。,案例1：HDLC,链路基本配置原理图,案例1：HDLC,HDLC链路基本配置类型 非平衡配置：点对点工作；多点工作 由一个主站控制整个链路的工作。主站发出的帧叫做命令。受控各站叫做次站或从站。从站发出的叫做响应。多点工作时主站与每个从站都有分开的逻辑链路。 平衡配置：点对点工作 链路上都是复合站，平等发送数据，不需要对方的允许。,案例1：HDLC,HDLC涉及三种类型的站： 主站（Primary Station） 主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错

19、恢复等）； 从站（Secondary Station） 主要功能是接收命令，发送响应，配合主站完成链路的控制； 复合站（Combined Station） 同时具有主、从站功能，既发送又接收命令和响应，并负责整个链路的控制。,案例1：HDLC,帧的一般结构,案例1：HDLC,标志字段 以0111 1110作为起止的帧边界标记 零比特填充法 原因 避免数据信息字段与标志字段F相同，引起帧边界错误，达到透明传输。 采用方法 发送端： 利用硬件扫描数据信息字段，遇到5个1即添加一个0 接受端： 硬件扫描到连续5个1，因为发送端扫描填充过0，紧接的必然是0，去掉这个0,案例1：HDLC,地址字段 非平

20、衡方式写入从站地址，平衡方式写入确认站地址 全1地址为广播方式，全0为无效地址，有效地址254个 地址字段可扩展,案例1：HDLC,HDLC的三种帧类型 信息帧（Information Frame） 监督帧（Supervisory Frame） 无编号帧（Unnumbered Frame）,案例1：HDLC,三种HDLC帧的控制字段,案例1：HDLC,三种HDLC帧的控制字段 序号（Seq） 当前发送的信息帧的序号。使用滑动窗口技术，3位序号，发送窗口大小为4。 捎带确认（Next） 捎带下一个准备接受的帧序号，而不是最后一个已收到的帧序号。 探询/结束 P/F位（Poll/Final） 命令

21、帧置“P”，响应帧置“F”。有些协议，P/F位用来强迫对方机器立刻发监督帧； 多终端系统中，计算机置“P”，允许终端发送数据；终端发向计算机的帧中，最后一个帧置为“F”，其它置为“P”。,案例1：HDLC,三种HDLC帧的控制字段 监督帧的类型（Type）,案例1：HDLC程,三种HDLC帧的控制字段 无编号帧 可以用来传控制信息，也可在不可靠无连接服务中传数据； 利用3、4、6、7、8共5个bit来表示不同的功能。,案例1：HDLC,半双工“点-点”数据传送 全双工链路，单向传输 全双工链路，双向同时传输,案例1：HDLC,半双工“点-点”数据传送 几点说明： 类型(TYPE)：对于信息使用I帧，对于S帧则使用RR、REJ、RNR或SREJ。 P/F指明探询或最后帧是否建立。,案例1：HDLC,案例1：HDLC,案例1：HDLC,全双工链路，单向传输,主站,从站,I,0,0,I,1,0,I,2,0,I,3,0,P,RR,1,F,I,1,0,I,2,0,I,3,0,P,I,4,0,RR,4,F,I,5,0,I,6,0,X 干扰,案例1：HDLC,注意： 主站在发送了探询之后仍能继续发送数据。另外，在发送信息帧7以后，