计算机网络PPT电子教案第4章 数据链路层基础

1、 2 本章学习要求： l 了解：数据传输过程中了解：数据传输过程中差错产生的原因与性质。差错产生的原因与性质。 l 掌握：误码率的定义与差错控制方法。掌握：误码率的定义与差错控制方法。 l 掌握：数据链路层的基本概念。掌握：数据链路层的基本概念。 l 了解了解：面向字符型数据链路层协议实例：面向字符型数据链路层协议实例bsc。 l 掌握：面向比特型数据链路层协议实例掌握：面向比特型数据链路层协议实例 hdlc。 l 掌握：掌握：internet中的数据链路层协议。中的数据链路层协议。 3 4.1.1 为什么要设计数据链路层为什么要设计数据链路层 l 在原始物理传输线路上传输数据信号是有差错的；

2、在原始物理传输线路上传输数据信号是有差错的； l 设计数据链路层的主要目的：设计数据链路层的主要目的： 将有差错的物理线路改进成无差错的数据链路；将有差错的物理线路改进成无差错的数据链路； 方法方法 成帧成帧 差错检测差错检测 差错控制差错控制 流量控制流量控制 信道访问控制信道访问控制 l 作用：改善数据传输质量，向网络层提供高质量的服务。作用：改善数据传输质量，向网络层提供高质量的服务。 4 成帧成帧 l字符计数法 l带字符填充的首尾标志法 l带位填充的首尾标志法 l物理层编码违例法 5 字符计数法字符计数法 6 带字符填充的首尾标志法带字符填充的首尾标志法 7 带位填充的首尾标志法带位填

3、充的首尾标志法 l 每帧使用一个特殊的位模式作为开始和结束标志 l 如，01111110 8 4.1.2 差错产生的原因和差错类型差错产生的原因和差错类型 l 传输差错传输差错 通过通信信道后接收的数据与发送数据通过通信信道后接收的数据与发送数据 不一致的现象不一致的现象; l 差错控制差错控制 检查是否出现差错以及如何纠正差错；检查是否出现差错以及如何纠正差错； l 通信信道的噪声分为两类：热噪声和冲击噪声；通信信道的噪声分为两类：热噪声和冲击噪声； l 由热噪声引起的差错是随机差错，或由热噪声引起的差错是随机差错，或随机错随机错； l 冲击噪声引起的差错是突发差错，或冲击噪声引起的差错是突

4、发差错，或突发错突发错； l 引起突发差错的位长称为突发长度；引起突发差错的位长称为突发长度； l 在通信过程中产生的传输差错，是由随机差错与突发在通信过程中产生的传输差错，是由随机差错与突发 差错共同构成的。差错共同构成的。 9 传输差错 产生过程 信源通信信道信宿 数据噪声数据+噪声 (a) 0 0 1 1 0 0 11 11 0 00 1 1 1 1 10 0 0 0 1 1 0 0 0 1 0 0 010110011001010传输数据 数据信号波形 噪声 数据信号 与噪声信号 叠加后的波形 采样时间 接收数据 原始数据 出错的位 (b) 10 4.1.3 误码率的定义误码率的定义 误

5、码率定义误码率定义： 二进制比特在数据传输系统中被传错的概率，二进制比特在数据传输系统中被传错的概率， 它在数值上近似等于：它在数值上近似等于： pe = ne/n 其中，其中，n为传输的二进制比特总数；为传输的二进制比特总数； ne为被传错的比特数。为被传错的比特数。 11 讨论 l 误码率应该是衡量数据传输系统正常工作状态误码率应该是衡量数据传输系统正常工作状态下下传输可传输可 靠性的参数；靠性的参数； l 对于一个实际的数据传输系统，不能笼统地说误码率越对于一个实际的数据传输系统，不能笼统地说误码率越 低越好，要根据实际传输要求提出误码率要求；低越好，要根据实际传输要求提出误码率要求；

6、l 对于实际数据传输系统，如果传输的不是二进制比特，对于实际数据传输系统，如果传输的不是二进制比特， 要折合成二进制比特来计算；要折合成二进制比特来计算； l 差错的出现具有随机性，在实际测量一个数据传输系统差错的出现具有随机性，在实际测量一个数据传输系统 时，只有被测量的传输二进制比特数越大，才会越接近时，只有被测量的传输二进制比特数越大，才会越接近 于真正的误码率值。于真正的误码率值。 2009 pearson education inc., upper saddle river, nj. all rights reserved.12 8.4 two strategies for hand

7、ling channel errors a variety of mathematical techniques have been developed that overcome errors during transmission and increase reliability known collectively as channel coding the techniques can be divided into two broad categories: forward error correction (fec) mechanisms 前向纠错机制 automatic repe

8、at request (arq) mechanisms 自动重传请求机制 the basic idea of fec is straightforward: add additional information to data that allows a receiver to verify that data arrives correctly and to correct errors (if possible) 校验机制 2009 pearson education inc., upper saddle river, nj. all rights reserved.13 14 4.1.4

9、 检错码与纠错码检错码与纠错码 l 检错码检错码: : 分组仅包含足以使接收端发现差错的冗余信息；分组仅包含足以使接收端发现差错的冗余信息； 接收端能发现出错，但不能确定哪一比特是错的，并接收端能发现出错，但不能确定哪一比特是错的，并 且自己不能纠正传输差错。且自己不能纠正传输差错。 机制：冗余机制：冗余 l 纠错码纠错码： 每个传输的分组带上足够的冗余信息；每个传输的分组带上足够的冗余信息； 接收端能发现并自动纠正传输差错。接收端能发现并自动纠正传输差错。 机制：重传机制：重传 15 常用的检错码常用的检错码 l 奇偶校验码奇偶校验码 垂直奇（偶）校验垂直奇（偶）校验 水平奇（偶）校验水平水

10、平奇（偶）校验水平 纵横奇偶校验（方阵码）纵横奇偶校验（方阵码） l 循环冗余编码循环冗余编码crc 目前应用最广的检错码编码方法之一，基于二进制除目前应用最广的检错码编码方法之一，基于二进制除 法法 8.6 an example block error code: single parity checking 单奇偶校验 2009 pearson education inc., upper saddle river, nj. all rights reserved.16 只能发现错误，不能纠正错误 只能检测到奇数个位员被改变的情况 2009 pearson education inc., u

11、pper saddle river, nj. all rights reserved.17 8.11 error correction with row and column (rac) parity纵横奇偶校验纵横奇偶校验 12位比特可以想象成 an array of 3-rows and 4-columns, with a parity bit added for each row and for each column figure 8.7 illustrates the arrangement, which is known as a row and column (rac) code

12、 example rac has n= 20, which means that it is a (20, 12) code 18 8.11 error correction with row and column (rac) parity how error correction works? assume that one of the bits in figure 8.7 (below) is changed during transmission: when the receiver arranges the bits into an array and parity bits are

13、 recalculated two of the calculations will disagree with the parity bits received, as figure 8.8 illustrates a single bit error will cause two calculated parity bits to disagree with the parity bit received 只能纠正1比特差错 能检测到奇数个比特差错 循环冗余编码循环冗余编码crc 任意长度报文 出色的验错能力 快速的硬件实现 19 20 4.1.5 循环冗余编码工作原理循环冗余编码工作原理

14、 发送方接收方 发送数据 f(x) 生成多项式 g(x) f(x) x k . g(x) =q(x)+ r(x) g(x) 实际发送: f(x) x k . +r(x) 数据字段校验字段 f(x)x k . r(x) 发送数据 f (x) 生成多项式 g(x) r(x)=r(x) 接收正确 r(x)=r(x) 接收出错 发送 f(x) x k . g(x) =q(x)+ r(x) g(x) 21 标准标准crc生成多项式生成多项式g（x） l crc-12 g（x）= x12+x11+x3+x2+x+1 l crc-16 g（x）= x16+x15+x2+1 l crc-ccitt g（x）=

15、 x16+x12+x5+1 l crc-32 g（x）= x32+x26+x23+x22+x16+x12+x11+ x10 +x8+x7+x5+x4 + x2+x+1 22 的步骤的步骤 1. 将一个位的串追加到数据单元后，n = 除数位数 1 2. 按二进制除法，用事先约定的除数除第一 步生成的数，余数即为crc 3. 将由第二步得到的n位crc替换第一步追 加的n个0。 23 l 发送方发送方 l 接受方接受方 1 1 0 0 1 1 发送数据 比特序列 crc校验码 比特序列 1 0 0 1 带crc校验码的 发送数据比特序列 1 1 0 0 1 1 1 0 0 11 1 0 0 1 1

16、 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 01 1 0 0 1g(x) 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 r(x) 1 0 0 0 0 1q(x) f(x) .xk 24 crc校验码的检错能力校验码的检错能力 l crc校验码能检查出全部单个错；校验码能检查出全部单个错； l crc校验码能检查出全部离散的二位错；校验码能检查出全部离散的二位错； l crc校验码能检查出全部奇数个错；校验码能检查出全部奇数个错； l crc校验码能检查出全部长度小于或等于校验码能检查出全

17、部长度小于或等于k位的突发错；位的突发错； l crc校验码能以校验码能以1-（1/2）k-1的概率检查出长度为的概率检查出长度为 （k+1）位的突发错；位的突发错； l 如果如果k=16，则该则该crc校验码能全部检查出小于或等于校验码能全部检查出小于或等于 16 位的所有的突发差错，并能以位的所有的突发差错，并能以1-（1/2）16-1=99.997 的概率检查出长度为的概率检查出长度为17位的突发错，漏检概率为位的突发错，漏检概率为 0.003%； 2009 pearson education inc., upper saddle river, nj. all rights reserv

18、ed.25 8.14 an efficient hardware implementation of crc crc hardware is arranged as a shift register with exclusive or (xor) gates between some of the bits figure 8.13 illustrates the hardware needed for the 3-bit crc computation from figure 8.12 the 16-bit checksum used in the internet 26 英特网校验码由16位

19、校验和反码构成，并不一定要固定16位 27 4.1.6 差错控制机制差错控制机制 自动重复请求自动重复请求 arq 信源 校验码 编码器 存储器 发送装置 传 输 信 道 接收装置 发发送送端端 校验码 译码器 接接收收端端 信宿 反馈信号 控制器 反馈信号 控制器 28 反馈重发机制的分类反馈重发机制的分类 l 停止等待方式停止等待方式 l 正常情况 l 帧丢失或损坏 l 确认丢失 l 确认延迟 接收端接收端 发送端发送端 acknakack 1223 1223 29 连续工作方式 l 拉回方式（后退拉回方式（后退n n帧）帧） l 选择重发方式选择重发方式 发发送送端端 接接收收端端 ac

20、k0 ack1 nakack2 ack3 (a) ack0 ack1 nakack2 ack6 (b) ack3 ack4 ack5 丢丢弃弃 重重传传 重重传传 01234523456 01234523456 01234526789 01234526789 发发送送端端 接接收收端端 丢丢弃弃 30 后退后退n帧帧arq l给帧编号：帧头部添加m位序号 l发送方滑动窗口：窗口中是已发送但未得 到确认的帧；窗口左边是已发送并且也得 到确认的帧；窗口右边是尚未发送的帧。 窗口最大为2m-1(?) l接受方滑动窗口：窗口大小始终为1。只按 顺序接受帧，不按顺序的帧丢弃。 l确认：ack，确认之前的

21、所有帧已收到 31 选择重传arq l发送方窗口和接受方窗口大小相同：最大 2m-1 (?) l确认ack l否定确认nak 32 大作业大作业 l请用图画出 停等arq 后退n帧arq 选择重传arq l在以下情况的示意图 正常情况 帧丢失或损坏 确认丢失 确认延迟 33 4.2.3 数据链路层向网络层提供的服务数据链路层向网络层提供的服务 数据链路层服务的类型数据链路层服务的类型： l 面向连接确认服务（面向连接确认服务（acknowledged connection- oriented service）；）； l 无连接确认服务（无连接确认服务（acknowladged connecti

22、onless service）；）； l 无连接不确认服务（无连接不确认服务（unacknowledged connectionless service）。）。 2009 pearson education inc., upper saddle river, nj. all rights reserved.34 13.10 unicast, broadcast, and multicast addresses the ieee addressing supports three types of addresses that correspond to three types of packe

23、t delivery figure 13.9 (below) provides a summary 2009 pearson education inc., upper saddle river, nj. all rights reserved.35 13.11 broadcast, multicast, and efficient multi-point delivery 协议实例 36 37 4.3 面向字符型数据链路层协议实例：bsc 4.3.1 数据链路层协议的分类 数据链路层协议 点-点线路 广播线路 面向字符型 面向比特型 逻辑链路子层 逻辑链路子层 ibm bsc iso bm

24、ibm sdlc ansi adlc iso hdlc ieee 802.2 ieee 802.3 ieee 802.4 ieee 802.5 类型 子层 38 4.3.2 面向字符型协议实例：bsc l 什么是面向字符型协议什么是面向字符型协议? 以字符为控制传输信息的基本单元以字符为控制传输信息的基本单元 l asiic码：码： 格式字符：格式字符：soh（start of heading） stx（start of text） etb（end of transmission block） etx（end of text） 控制字符：控制字符：ack（acknowledge） nak（ne

25、gative acknowledge） enq（enquire） eot（end of transmission） syn（synchrous） dle（data link escape） 39 面向字符型面向字符型bsc协议的数据报文格式协议的数据报文格式 synsynsoh报头stx正文etb/etxbcc 报文开始 同步字符用户定义 报头结束分组结束 报文结束 校验字段正文字段 40 建立、维护建立、维护 与释放数据与释放数据 链路流程图链路流程图 发送enq 接收ack ack? 发送数据 接收应答 ack/nak 结束? 重发 发送eot准备数据 放送enq 发送ack 接收数据,e

26、ot 发送ack发送nak enq? eot? bcc正确? 结束 结束 y y y y n n n n ny ack nak 41 4.4 典型数据链路层协议分析 面向比特型 4.4.1 hdlc产生的背景 面向字符型数据链路层协议的缺点面向字符型数据链路层协议的缺点： l 报文格式不一样；报文格式不一样； l 传输透明性不好；传输透明性不好； l 等待发送方式，传输效率低。等待发送方式，传输效率低。 面向比特型协议的设计目标面向比特型协议的设计目标： l 以比特作为传输控制信息的基本单元；以比特作为传输控制信息的基本单元； l 数据帧与控制数据帧与控制 帧格式相同；帧格式相同； l 传输透

27、明性好；传输透明性好； l 连续发送，传输效率高。连续发送，传输效率高。 42 4.4.2 数据链路的配置和数据传送方式 数据链路的配置数据链路的配置 l 非平衡配置非平衡配置 l 平衡配置平衡配置 非平衡配置中的主站与从站非平衡配置中的主站与从站 l 主站：控制数据链路的工作过程。主站发出命令主站：控制数据链路的工作过程。主站发出命令 l 从站：接受命令，发出响应，配合主站工作从站：接受命令，发出响应，配合主站工作 非平衡配置中的结构特点非平衡配置中的结构特点 l 点点- -点方式点方式 l 多点方式多点方式 43 数据链路的非平衡配置方式 44 非平衡配置方式 正常响应模式（正常响应模式（

28、normal response mode，nrm） l 主站可以随时向从站传输数据帧；主站可以随时向从站传输数据帧； l 从站只有在主站向它发送命令帧进行探询（从站只有在主站向它发送命令帧进行探询（poll），）， 从站响应后才可以向主站发送数据帧。从站响应后才可以向主站发送数据帧。 异步响应模式（异步响应模式（asynchronous response mode，arm） l 主站和从站可以随时相互传输数据帧；主站和从站可以随时相互传输数据帧； l 从站可以不需要等待主站发出探询就可以发送数据；从站可以不需要等待主站发出探询就可以发送数据； l 主站负责数据链路的初始化、链路的建立、释放与差

29、主站负责数据链路的初始化、链路的建立、释放与差 错恢复等功能。错恢复等功能。 45 平衡配置方式 l 链路两端的两个站都是复合站（链路两端的两个站都是复合站（combined station）；）； l 复合站同时具有主站与从站的功能；复合站同时具有主站与从站的功能； l 每个复合站都可以发出命令与响应；每个复合站都可以发出命令与响应； l 平衡配置结构中只有异步平衡模式（平衡配置结构中只有异步平衡模式（asynchronous balanced mode，abm）；）； l 异步平衡模式的每个复合站都可以平等地发起数据传异步平衡模式的每个复合站都可以平等地发起数据传 输，而不需要得到对方复合

30、站的许可。输，而不需要得到对方复合站的许可。 46 数据链路的平衡配置方式 47 4.4.3 hdlc的帧结构 l f（flag） ：固定格式固定格式 01111110 作用作用 帧同步帧同步 传输数据的透明性（传输数据的透明性（零零比特插入与删除）比特插入与删除） l a（address） ：地址地址 l c（control） ：帧的类型、帧的编号、命令与控制信息帧的类型、帧的编号、命令与控制信息 l i（information） ：网络层数据，网络层数据，nmax = 256b l crc（checksum） ：校验校验a、c、i字段的数据字段的数据 g(x)= x16+x12+x5+1 标志字段f (8位) 地址字段a (8/16位) 控制字段c (8/16位) 信息字段i (长度可变) 帧校验字段fcs (16/32位) 标志字段f (8位) 48 零比特插入/删除工作过程 49 帧类型及控制字段的意义 标志字段f （8 位 ） 地址字段a （8 /16位 ） 控制字段c （8 位 ）