第四章 数据链路层(1)

1、04.1数据链路层需要解决的问题数据链路层需要解决的问题4.2基本数据链路协议基本数据链路协议4.3数据链路的连接方式数据链路的连接方式4.4点到点的数据链路访问点到点的数据链路访问4.5广播网络的介质访问控制广播网络的介质访问控制4.6用网桥实现网络互连用网桥实现网络互连第四章第四章 数据链路层和媒体访问数据链路层和媒体访问控制子层（控制子层（1）14.1 数据链路层需要解决的问题数据链路层需要解决的问题1）为网络层提供的服务）为网络层提供的服务2）成帧）成帧3）差错控制）差错控制4）流量控制）流量控制21）为网络层提供的服务）为网络层提供的服务 将源端网络层的数据传输给宿端网络层。将源端网

2、络层的数据传输给宿端网络层。物理层物理层数据链路层数据链路层网络层网络层传输层传输层应用层应用层比特流比特流物理层物理层数据链路层数据链路层网络层网络层保证数据流的顺序保证数据流的顺序传输层传输层应用层应用层源源宿宿3为网络层提供服务的分类为网络层提供服务的分类 无确认的无连接服务无确认的无连接服务 从源到宿发送独立帧，不确认帧的到达从源到宿发送独立帧，不确认帧的到达 不提供纠错重传服务不提供纠错重传服务 适用于误码率较低的可靠通信适用于误码率较低的可靠通信 有确认的无连接服务有确认的无连接服务 对发送的每一帧独立确认其接收情况对发送的每一帧独立确认其接收情况 在一定时间间隔内未收到确认则重发

3、这一帧在一定时间间隔内未收到确认则重发这一帧 适用于不可靠的通信适用于不可靠的通信 有确认的面向连接服务有确认的面向连接服务4有确认的面向连接服务有确认的面向连接服务 从源到宿建立连接（占用资源）从源到宿建立连接（占用资源） 在连接上传输赋予编号的帧在连接上传输赋予编号的帧 保证帧的正确顺序，且每帧只接收一次保证帧的正确顺序，且每帧只接收一次 对每一帧都确认对每一帧都确认 断开连接（释放占用的资源）断开连接（释放占用的资源）52）成帧）成帧 为了给网络层提供服务，需要使用物理为了给网络层提供服务，需要使用物理层提供的服务（比特流的透明传输）层提供的服务（比特流的透明传输） 使用物理层服务的方法

4、：使用物理层服务的方法： 把比特流分成离散的帧把比特流分成离散的帧 通过帧的校验和检错，采取相应措施通过帧的校验和检错，采取相应措施 成帧的方法成帧的方法 标识帧的首尾标识帧的首尾6成帧的方法成帧的方法 字符计数法字符计数法 字符填充的首尾标识法字符填充的首尾标识法 位填充的首尾标识法位填充的首尾标识法 物理层编码违例法物理层编码违例法7 特点特点 帧不定长帧不定长 用帧头一个控制字符区分帧的首尾用帧头一个控制字符区分帧的首尾 按照控制字符说明的长度计数，确定帧边界按照控制字符说明的长度计数，确定帧边界 问题问题 控制字符的数值错误造成发送与接收不同步控制字符的数值错误造成发送与接收不同步字符

5、计数法字符计数法8字符流举例字符流举例5 1 2 3 4 5 0 1 2 3 8 0 1 2 3 4 5 6 5 0 1 2 35 1 2 3 4 7 0 1 2 3 8 0 1 2 3 4 5 6 5 0 1 2 3帧头：说明帧的字符数帧头：说明帧的字符数控制字符传输错误控制字符传输错误出现差错带来的问题出现差错带来的问题 无法确定下一帧的帧头位置无法确定下一帧的帧头位置 无法确定重传帧的帧头位置无法确定重传帧的帧头位置9 特点特点 用用8位位ASCII码定义帧头和帧尾的标识符码定义帧头和帧尾的标识符 DLE STX（Data Link Escape; Start of Text） DLE

6、ETX（Data Link Escape; End of Text ） 出现差错后无需解决再同步问题出现差错后无需解决再同步问题 需要解决的问题需要解决的问题 数据中包含定义的标识符数据中包含定义的标识符DLE、STX和和ETX 发送方插入一个相同的标识符发送方插入一个相同的标识符字符填充的首尾标识法字符填充的首尾标识法1044332211字符填充的首尾标识法举例字符填充的首尾标识法举例DLESTXADLEBDLEETXDLESTXADLEDLEBDLEETXDLESTXADLEBDLEETXDLESTXADLEDLEBDLEETXASCII字符字符帧头：帧头：DLE STX帧尾：帧尾：DLE

7、 ETX内容为内容为“DLE”填充填充“DLE”丢掉丢掉“DLE”11位填充的首尾标识法位填充的首尾标识法 特点特点 帧以帧以bit为单位，不以为单位，不以byte为单位为单位 定义特殊的帧头和帧尾标识位模式定义特殊的帧头和帧尾标识位模式01111110 需要解决的问题需要解决的问题 数据中包含定义的标识位模式数据中包含定义的标识位模式01111110 发送方在连续发送方在连续5个个“1”之后插入之后插入1个个“0”12位填充的首尾标识法举例位填充的首尾标识法举例0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 01 2 3

8、 4 5 61 2 3 4 5 6 7 81 2 3 4 5 60 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 01 2 3 4 56 7 8帧头帧头帧尾帧尾在在L2插入插入/去除填充位去除填充位“0”1300110有有跳跳变变有有跳跳变变无无跳跳变变无无跳跳变变有有跳跳变变 高高低低物理层编码违例法物理层编码违例法例：差分曼彻斯特编码例：差分曼彻斯特编码 打破常规，采用冗余技术，打破常规，采用冗余技术，2个物理位表示个物理位表示1个数据位个数据位 用电平在两个物理位中间的一次变换区分数据位边界用电平在两个物理位中间的

9、一次变换区分数据位边界143）差错控制）差错控制 差错控制的基本概念差错控制的基本概念 与差错控制有关的术语与差错控制有关的术语 差错控制的评价尺度：差错控制的评价尺度：hamming距离距离 检错码能力检错码能力 纠错码能力纠错码能力 检错码举例：循环冗余码检错码举例：循环冗余码CRC15差错控制的基本概念差错控制的基本概念 出现差错的原因出现差错的原因 1、单个错：由随机的信道热噪声引起，一次只影响一比特，且错误之间、单个错：由随机的信道热噪声引起，一次只影响一比特，且错误之间没有关联。没有关联。 2、突发错：由瞬间的脉冲噪声引起，产生连串错码，错码前后有关联。、突发错：由瞬间的脉冲噪声引

10、起，产生连串错码，错码前后有关联。突发错所影响的最大连续数据比特数称为突发长度。突发错所影响的最大连续数据比特数称为突发长度。 差错控制需要解决的问题差错控制需要解决的问题 保证不错帧保证不错帧 保证不丢帧保证不丢帧 保证不乱序保证不乱序 差错控制手段差错控制手段 接收方回送确认控制帧接收方回送确认控制帧 用计时器确定帧丢失情况用计时器确定帧丢失情况 用帧的编号识别重复帧情况用帧的编号识别重复帧情况 差错处理方法差错处理方法16差错的检测和纠正差错的检测和纠正 纠错码纠错码 在发送的数据块中附加充足的冗余信息在发送的数据块中附加充足的冗余信息 接收方根据冗余信息纠正错误接收方根据冗余信息纠正错

11、误 检错码检错码 在发送的数据块中附加适当的冗余信息，使在发送的数据块中附加适当的冗余信息，使接收方有足够的信息检测是否有差错接收方有足够的信息检测是否有差错 当有差错时，对发送方请求重传当有差错时，对发送方请求重传17有关差错的术语有关差错的术语 码字（码字（codeword） 差错的度量：差错的度量：Hamming距离距离0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0m位位r位位n位码字（位码字（ n = m + r ）数据位数据位冗余（校验）位冗余（校验）位18 举例举例 码字码字11 0 0 0 1 0 0 1

12、 码字码字21 0 1 1 0 0 0 1 异或运算异或运算0 0 1 1 1 0 0 0 定义定义一个有效编码集中，任意两个码字的海明距一个有效编码集中，任意两个码字的海明距离的最小值称为该编码集的海明距离。离的最小值称为该编码集的海明距离。Hamming距离距离码位相同码位相同码位不同码位不同Hamming距离距离 等于等于319检错码的能力检错码的能力 最小最小Hamming距离为距离为d+1的检错编码只的检错编码只能检测出能检测出d位数据错误。位数据错误。 例：奇偶位检测编码（例：奇偶位检测编码（d=1）偶校验）偶校验1 0 0 0 1 0 1 1 0 发送发送1 0 0 1 1 0

13、1 1 11 0 0 1 1 0 1 1 0 接收接收1 1 1 1 1 0 1 1 1数据位数据位数据位数据位检验位检验位检验位检验位传输差错传输差错传输差错传输差错20纠错码的能力纠错码的能力 最小最小Hamming距离为距离为2d+1的纠错编码只能纠的纠错编码只能纠正正d位数据错误。位数据错误。 纠错方式：将无效码字恢复成距离它最近的有纠错方式：将无效码字恢复成距离它最近的有效码字，但不是效码字，但不是100%正确。正确。 例：例：d=2定义定义 “0”-00000 “1”-11111 采用大数判决：采用大数判决：5个比特中个比特中0的个数大于的个数大于1的个数则译码成的个数则译码成0，

14、 反之译码成反之译码成1； 4个有效码字个有效码字 接收码接收码差错码位差错码位纠错结果纠错结果 0000000000 0000000111 00000001110000011111 X 0000011111 000000011100000001110000011111 1111100000 111111111121用循环冗余码用循环冗余码CRC检错检错0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0m位位r位位选择选择r阶生成多项式阶生成多项式 G(x) 在数据帧末尾加在数据帧末尾加r个个0，形成多项式，形成多项式xr

15、M(x)发送校验和发送校验和T(x) = xrM(x) - 余数余数xrM(x)/ G(x)检错标准：余数检错标准：余数T(x) / G(x)是否为零是否为零数据位（数据位（m阶多项式阶多项式 M(x)）冗余（校验）位冗余（校验）位例如：余数例如：余数（39 - 余数余数39/9）/ 9 = 022CRC检错举例检错举例 数据帧数据帧1101011011（m=10, M(x)） 生成多项式生成多项式G(x) = x4 + x + 1（r=4） 以以2为模的除法：为模的除法：11010110110000 /10011 = 1110 发送帧发送帧11010110111110（以（以2为模的减法）为

16、模的减法） 接收端检测：接收端检测：11010110111110 /10011 = 0T(x)23以以2为模的除法和减法为模的除法和减法 110000101010011 ）1101011011000011010110110000 10011 1110 1001111010110111110 10011 10110 100111010010011 1110余数余数G(x)T(x) =xrM(x) - 余数余数xrM(x)244）流量控制）流量控制 为什么要进行流量控制为什么要进行流量控制 发送方的传送能力大于接收方的接收能力会发送方的传送能力大于接收方的接收能力会造成数据帧的丢失造成数据帧的丢失

17、 如何进行流量控制如何进行流量控制 通过接收方的反馈机制限制发送方的数据发通过接收方的反馈机制限制发送方的数据发送流量，使其适应接收方的处理速度送流量，使其适应接收方的处理速度 制定规则：何时发送下一帧；未经允许则禁制定规则：何时发送下一帧；未经允许则禁止发送。止发送。254.2 数据链路协议概述数据链路协议概述1）基本数据链路层协议）基本数据链路层协议2）滑动窗口协议滑动窗口协议3）协议描述和验证协议描述和验证261）基本数据链路层协议）基本数据链路层协议 数据传输方式数据传输方式 数据链路层协议的基本概念数据链路层协议的基本概念 三个协议实例三个协议实例 无限制的单工协议无限制的单工协议

18、单工的停单工的停-等协议等协议 有躁声信道的单工协议有躁声信道的单工协议 协议比较协议比较 需要改进的问题需要改进的问题27数据传输方式数据传输方式 单工单工 数据在介质中仅在一个方向传输。数据在介质中仅在一个方向传输。 半双工半双工 数据可以双向传输，在特定时刻只能向一个数据可以双向传输，在特定时刻只能向一个方向传输。方向传输。 全双工全双工 在任意时刻都可以实现双向传输。在任意时刻都可以实现双向传输。28数据链路层协议的基本概念数据链路层协议的基本概念 使用物理层的服务（发送使用物理层的服务（发送/接收比特流）接收比特流） 为网络层提供服务为网络层提供服务 实现的基本功能实现的基本功能 数

19、据帧的一般格式数据帧的一般格式29为网络层提供服务为网络层提供服务 对网络层的分组对网络层的分组packet封装成帧封装成帧frame（或解封装，从帧中抽取分组）（或解封装，从帧中抽取分组） 实现从发送方到接收方数据链路层之间实现从发送方到接收方数据链路层之间透明的、无差错的帧传输透明的、无差错的帧传输 流量控制流量控制 检错重传检错重传30数据链路层协议的基本功能数据链路层协议的基本功能物理层物理层数据链路层数据链路层网络层网络层比特流比特流物理层物理层数据链路层数据链路层网络层网络层发送方发送方A接收方接收方Bfrom_network_layerfrom_physical_layerto_

20、network_layerto_physical_layerframe物理传输通道物理传输通道packet arrivalframe arrival31帧的一般格式帧的一般格式类类型型kind序序号号seq确确认认ack数数据据info帧头帧头来自发送方网络层来自发送方网络层from_network_layer帧帧frame: s区分数据帧区分数据帧/控制帧控制帧分组分组packet32协议协议1：A的发送进程的发送进程packet_arrivalfrom_network-layer(&buffer)to_physical-layer(&s) = bufferpac

21、ketpacketpacketheadbuffer&s来自网络层来自网络层送往物理层送往物理层yes33协议协议1：B的接收进程的接收进程frame_arrivalto_network-layer(&)from_physical-layer(&r)packetpackethead&r送往网络层送往网络层来自物理层来自物理层yeswait_for_event(&event)循环等待循环等待no&34无限制的单工协议（协议无限制的单工协议（协议1）物理层物理层数据链路层数据链路层网络层网络层比特流比特流物理层物理层数据链路层数

22、据链路层网络层网络层发送方发送方A接收方接收方Bframe单工物理信道单工物理信道packet_ arrivalframe_arrival如果如果B的接收能力小于的接收能力小于A的发送能力怎么办？的发送能力怎么办？35packet_arrivalfrom_network-layer(&buffer)to_physical-layer(&s) = bufferpacketpacketpacketheadbuffer&s来自网络层来自网络层送往物理层送往物理层yes协议协议2：A的发送进程（流控）的发送进程（流控）wait_for_event(&even

23、t)frame_arrival来自物理层来自物理层yes接收方的确认帧到达接收方的确认帧到达head36协议协议2：B的接收进程（流控）的接收进程（流控）frame_arrivalto_network-layer(&)from_physical-layer(&r)packetpackethead&r送往网络层送往网络层来自物理层来自物理层yeswait_for_event(&event)循环等待循环等待no&to_physical-layer(&s)head&s（确认帧）（确认帧）送往物理层送往物理层37单工的停单

24、工的停-等协议（协议等协议（协议2）物理层物理层数据链路层数据链路层网络层网络层比特流比特流物理层物理层数据链路层数据链路层网络层网络层发送方发送方A接收方接收方Bframe半双工物理信道半双工物理信道packet_ arrivalframe_arrival如果帧在传输中被损坏如果帧在传输中被损坏或丢失怎么办？或丢失怎么办？head收到确认方可发送下一帧收到确认方可发送下一帧38有躁声信道的单工协议（协议有躁声信道的单工协议（协议3） 信道不可靠的解决办法信道不可靠的解决办法 检错检错/重传重传 重传需要解决的问题：重传需要解决的问题： 发送方如何得知哪个帧出错、需要重发发送方如何得知哪个帧出

25、错、需要重发 接收方如何区分首次收到的帧和已经收到的接收方如何区分首次收到的帧和已经收到的重传帧重传帧39发送方正确得知差错帧发送方正确得知差错帧 出错情况出错情况 帧丢失帧丢失 帧损坏，在接收方校验出错，将帧丢弃帧损坏，在接收方校验出错，将帧丢弃 发送方的解决办法发送方的解决办法 对每次发送的帧都启动一个计时器对每次发送的帧都启动一个计时器 在规定的时间内未收到对方的确认帧，则认在规定的时间内未收到对方的确认帧，则认为该帧丢失，重新发送该帧。为该帧丢失，重新发送该帧。 重复重传过程，直至收到确认帧为止。重复重传过程，直至收到确认帧为止。40接收方正确区分重传帧接收方正确区分重传帧 情况分析情

26、况分析 当确认帧在途中时，发送方计时器超时有可能造成当确认帧在途中时，发送方计时器超时有可能造成某帧的多次重传；某帧的多次重传； 接收方必须将包含发送方网络层分组的每个数据帧接收方必须将包含发送方网络层分组的每个数据帧提交接收方的网络层，且只能提交一次。提交接收方的网络层，且只能提交一次。 解决办法解决办法 在发送方定义帧的序列号，在接收方定义帧序列号在发送方定义帧的序列号，在接收方定义帧序列号期望值；期望值； 根据接收帧序列号与期望值的比较结果区分首次接根据接收帧序列号与期望值的比较结果区分首次接收帧和重复接收帧。收帧和重复接收帧。41重复接收帧的识别重复接收帧的识别发送帧发送帧m 丢失丢失

27、超时重传超时重传超时重传超时重传期望接收期望接收seq=0期望接收期望接收seq=0接收帧接收帧m，回送确认，回送确认期望接收期望接收seq=1确认帧确认帧m收到收到帧帧m, seq=0帧帧m, seq=0帧帧m, seq=0期望接收期望接收seq=1接收帧接收帧m的的seq=0，丢弃丢弃回送确认回送确认收到确认收到确认发送帧发送帧 m+1帧帧m+1, seq=1期望接收期望接收seq=1接收帧接收帧m+1，回送确认，回送确认期望接收期望接收seq=0确认帧确认帧m+1收到收到收到确认收到确认发送帧发送帧 m+2 丢失丢失确认帧确认帧m收到收到42简单单工协议比较简单单工协议比较 协议协议1完

28、成数据链路层协议的基本功能完成数据链路层协议的基本功能 发送方将网络层的分组封装成帧，交物理层发送；发送方将网络层的分组封装成帧，交物理层发送； 接收方从物理层的接收帧抽取分组，交网络层。接收方从物理层的接收帧抽取分组，交网络层。 协议协议2增添流量控制功能增添流量控制功能 发送方收到确认帧后才允许发送下一帧；发送方收到确认帧后才允许发送下一帧； 接收方收到数据帧后回送确认帧。接收方收到数据帧后回送确认帧。 协议协议3增添检错重传功能增添检错重传功能 发送方定义帧序列号，启动计时器，超时重传发送方定义帧序列号，启动计时器，超时重传 接收方定义帧序列号期望值，将匹配帧交网络层接收方定义帧序列号期

29、望值，将匹配帧交网络层43改进简单单工协议改进简单单工协议 数据双向传输的需求（数据双向传输的需求（AB） 两条单工信道：反向传输流量小，浪费两条单工信道：反向传输流量小，浪费 一条双工信道实现数据的双向传输一条双工信道实现数据的双向传输 确认方式确认方式 AB，B回送确认帧（回送确认帧（AB），造成控制帧的流），造成控制帧的流量量 AB，B将确认信息写入它将向将确认信息写入它将向A发送帧的发送帧的ack字段，字段，在在BA中夹带确认信息中夹带确认信息A B 发送方式发送方式 发送一帧，等待确认，再发送下一帧，效率低发送一帧，等待确认，再发送下一帧，效率低 一次连续发送多个数据帧一次连续发送多

30、个数据帧442）滑动窗口协议）滑动窗口协议 一位滑动窗口协议（协议一位滑动窗口协议（协议4） 双向传输和夹带确认双向传输和夹带确认 提高线路利用率提高线路利用率 滑动窗口的概念滑动窗口的概念 引入差错控制的滑动窗口协议引入差错控制的滑动窗口协议45一位滑动窗口协议（协议一位滑动窗口协议（协议4）发送发送A0收到收到A0，发送，发送B0seq=0, ack=1, A0 seq=0, ack=0, B0 收到收到B0，发送，发送A1收到收到B1，发送，发送A2收到收到A1，发送，发送B1收到收到A0，发送，发送B0seq=0, ack=1 A2seq=1, ack=0, A1 seq=1, ack

31、=1, B1 AB 双向传输双向传输夹带确认夹带确认46协议协议4的信道利用率的信道利用率设：设：信道容量信道容量 b = 50 kbps传输延迟传输延迟 R = 500 ms帧的长度帧的长度 n = 1000 bit 发送一帧需要的时间发送一帧需要的时间 Tf = n/b = 20 ms 等待确认需要的时间等待确认需要的时间 R = 500 ms 线路的利用率线路的利用率 Tf /(Tf +R) = 20/520 = 3.85% 改进办法改进办法 使线路利用率达到使线路利用率达到100%，滑动窗口长，滑动窗口长w=2647滑动窗口的概念滑动窗口的概念 每个待发送帧被赋予一个序列号每个待发送帧

32、被赋予一个序列号seq seq的取值范围是的取值范围是 0 2n-1（n位字段）位字段） 建立缓冲区建立缓冲区 发送窗口：允许发送的帧发送窗口：允许发送的帧 顺序接收来自网络层的分组顺序接收来自网络层的分组 最多保存最多保存2n-1个待确认的帧个待确认的帧 窗口达到最大值窗口达到最大值2n-1时强制关闭网络层时强制关闭网络层 接收窗口：允许接收的帧接收窗口：允许接收的帧 对进入窗口的帧顺序提交网络层，产生确认对进入窗口的帧顺序提交网络层，产生确认 落在窗口外的帧被丢弃落在窗口外的帧被丢弃48引入滑动窗口后的差错控制引入滑动窗口后的差错控制 退后退后n帧（帧（go back n） 发送方连续发送

33、至发送窗口满发送方连续发送至发送窗口满 接收窗口为接收窗口为1，对丢弃帧不确认，对丢弃帧不确认 发送方超时重传，从未被确认帧开始发送方超时重传，从未被确认帧开始 选择重传（选择重传（selective repeat） 接收窗口存储差错帧后继的所有正确帧接收窗口存储差错帧后继的所有正确帧 发送方只重传差错帧；接收方接收重传帧，按正确发送方只重传差错帧；接收方接收重传帧，按正确顺序将分组提交网络层顺序将分组提交网络层 控制策略比较控制策略比较49退后退后n帧协议概念帧协议概念01234567823456789101101EDDDDDD23456789出错出错丢弃丢弃超时间隔超时间隔确认确认发送发送接收重传接收重传重传重传50选择重传协议概念选择重传协议概念01234567829101112131415161701E34567829101112131415出错出错接收缓存接收缓存超时间隔超时间隔确认确认发送发送接收重传接收重传重传重传51差错控制策略比较差错控制策略比较 退后退后n帧帧 发送方需要较大的缓冲区，以便重传发送方需要较大的缓冲区，以便重传 适于信道出错率较少的情况适于信道出错率较少的情况 选择重传选择重传 接