计算机通信与网络_CH03_数据链路层

1、 数据链路层数据链路层在物理连接提供的在物理连接提供的比特流传输服务基础上，构成透明比特流传输服务基础上，构成透明的、相对无差错的数据链路，实现的、相对无差错的数据链路，实现可靠、有效的数据传送。可靠、有效的数据传送。 数据链路层协议负责在物理网数据链路层协议负责在物理网络与计算机的协议组之间提供一个络与计算机的协议组之间提供一个接口。接口。 数据电路数据电路数据链路数据链路数据电路数据电路：在传输信道两端加上信号变换设备（如：在传输信道两端加上信号变换设备（如ModemModem）之后所形成的二进制比特流通路。即数据电路由传输信道加之后所形成的二进制比特流通路。即数据电路由传输信道加DCED

2、CE组成。组成。数据链路数据链路：在数据电路建立的基础上，在链路协议控制下，：在数据电路建立的基础上，在链路协议控制下，使通信双方正确传输数据的终端设备与传输线路的组合体。使通信双方正确传输数据的终端设备与传输线路的组合体。 电话网ModemModemn数据链路与数据电路数据链路与数据电路 数据电路又可称为数据电路又可称为物理链路或链路物理链路或链路 数据链路又称为数据链路又称为逻辑链路逻辑链路n数据链路是在数据电路上增加传输控数据链路是在数据电路上增加传输控制功能实现的。制功能实现的。n只有建立了数据链路，才能真正地实只有建立了数据链路，才能真正地实现数据通信。现数据通信。n数据链路的基本结

3、构（线路拓扑数据链路的基本结构（线路拓扑 ） 点到点链路点到点链路 多点链路多点链路n数据链路层的传送方式：数据链路层的传送方式： 单工通信单工通信 半双工通信半双工通信(Half Duplex) 全双工通信全双工通信(Full Duplex) n在链路中，所连接的节点称为在链路中，所连接的节点称为“站站” 。n发送命令或信息的站称为发送命令或信息的站称为“主站主站”，在通信过程中一般起控制作用；接收在通信过程中一般起控制作用；接收数据或命令并做出响应的站称为数据或命令并做出响应的站称为“从从站站”，在通信过程中处于受控地位。，在通信过程中处于受控地位。n同时具有主站和从站功能的，能够发同时具

4、有主站和从站功能的，能够发出命令和响应信息的站称为复合站。出命令和响应信息的站称为复合站。在点到点链路中，两端的站可能是主站、从站或在点到点链路中，两端的站可能是主站、从站或复合站。链路可以是不平衡的，或平衡结构。复合站。链路可以是不平衡的，或平衡结构。点到点链路点到点链路星型点到点链路星型点到点链路在主从式点到多点链路中，常常是不平衡链路；在主从式点到多点链路中，常常是不平衡链路；在对等式点到多点链路中，常使用平衡型链路。在对等式点到多点链路中，常使用平衡型链路。主从式点到多点链路主从式点到多点链路对等式点到多点链路对等式点到多点链路n数据链路层的目标：数据链路层的目标：在数据链路上提在数据

5、链路上提供可靠的信息传输供可靠的信息传输n数据链路层的功能：数据链路层的功能： 链路管理链路管理 帧同步（帧定界）帧同步（帧定界） 流量控制流量控制 数据和控制信息的识别数据和控制信息的识别 差错控制差错控制 透明传输透明传输 寻址寻址n数据链路层的协议数据服务单元数据链路层的协议数据服务单元PDU，即传输和处理的数据单位：即传输和处理的数据单位：帧帧。n物理层的任务是实现比特流的传送，但物理层的任务是实现比特流的传送，但不能保证没有错误，需要数据链路层进不能保证没有错误，需要数据链路层进行差错检测和纠正。行差错检测和纠正。n为了便于实现流量控制和差错控制，数为了便于实现流量控制和差错控制，数

6、据链路层将比特流分解成离散的帧，独据链路层将比特流分解成离散的帧，独立地计算校验和，发送和接收。立地计算校验和，发送和接收。n数据链路层帧的结构，包括需要传输数据链路层帧的结构，包括需要传输的数据、相应的控制信息、校验信息、的数据、相应的控制信息、校验信息、帧之间的分隔标志等。帧之间的分隔标志等。n帧的形成方法：帧的形成方法： 字符计数法字符计数法 含字节填充的分界符法含字节填充的分界符法 含位填充的分界标志法含位填充的分界标志法 物理层编码违例法物理层编码违例法在数据通信中，要求发送方的发送数据在数据通信中，要求发送方的发送数据速率必须速率必须不能超过不能超过接收方的接收和处理接收方的接收和

7、处理数据的速率。数据的速率。由于通信的随机性造成传输流量变化，由于通信的随机性造成传输流量变化，当接收方来不及接收和处理数据时，就当接收方来不及接收和处理数据时，就必须采取相应的措施来控制发送方发送必须采取相应的措施来控制发送方发送数据的速率。数据的速率。一般流量控制由一般流量控制由接收方主动控制接收方主动控制实现。实现。数据链路层数据链路层主主机机 A缓存缓存主主机机 B数据链路数据链路AP2AP1缓存缓存发送方发送方接收方接收方帧帧高层高层帧帧n完全理想化的数据传输所基于的两个完全理想化的数据传输所基于的两个假定假定: : 假定假定1 1：链路是理想的传输信道，所传送：链路是理想的传输信道

8、，所传送的任何数据既不会出差错也不会丢失。的任何数据既不会出差错也不会丢失。 假定假定2 2：不管发送方以多快的速率发送数：不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上据，接收方总是来得及收下，并及时上交主机。交主机。n流量控制流量控制的目的：的目的： 现代数据通信的交换方式，采用了存储现代数据通信的交换方式，采用了存储转发的分组交换技术，当接收方的处理转发的分组交换技术，当接收方的处理能力小于发送方的发送量时，必须采用能力小于发送方的发送量时，必须采用流量控制。流量控制。处理单元处理单元没有缓冲空间了！没有缓冲空间了！后面分组丢弃后面分组丢弃n保留上述的第一个假定，即主机保

9、留上述的第一个假定，即主机A A向主向主机机B B传输数据的信道仍然是无差错的理传输数据的信道仍然是无差错的理想信道。但现在不能保证接收端向主想信道。但现在不能保证接收端向主机交付数据的速率永远不低于发送端机交付数据的速率永远不低于发送端发送数据的速率，需要发送数据的速率，需要流量控制流量控制。n由收方控制发方的数据流，是计算机由收方控制发方的数据流，是计算机网络中流量控制的一个基本方法。网络中流量控制的一个基本方法。开关式流量控制开关式流量控制: XON/XOFF, 硬件硬件协议式流量控制协议式流量控制: ARQ自动重发请求自动重发请求 停止等待协议（停止等待协议（Stop-and-Wait

10、 Protocol ） 滑动窗口协议（滑动窗口协议（Slide Window Protocol ） （1）连续连续ARQ协议协议 （2）选择选择ARQ协议协议发送结点发送结点接收结点接收结点ABDATADATADATADATA送主机送主机 B送主机送主机 B送主机送主机 B送主机送主机 BABDATA送主机送主机 BDATA送主机送主机 B时时间间不需要流量控制不需要流量控制需要流量控制需要流量控制时时间间ABDATA0送送主主机机ACKDATA1送送主主机机ACK(a) 正常情况正常情况ABDATA0DATA0送送主主机机ACK(c) 数据帧丢失数据帧丢失重重传传tout丢丢失失 ！ABDA

11、TA0送送主主机机ACKDATA0丢丢弃弃ACK(d) 确认帧丢失确认帧丢失重重传传tout丢丢失失 ！ABDATA0NAKDATA0送送主主机机ACK(b) 数据帧出错数据帧出错重重传传出错出错n由于发送端口或传输信道的速率限制，发由于发送端口或传输信道的速率限制，发送一帧需要一定的时间：送一帧需要一定的时间：“发送时延发送时延”。n接收一帧的时间和发送一帧的时间相同。接收一帧的时间和发送一帧的时间相同。发送应答帧，也有发送应答帧，也有“发送时延发送时延”。n由于电磁波传输速率的存在，帧在信道中由于电磁波传输速率的存在，帧在信道中的传送，具有的传送，具有“传播时延传播时延”。n接收方收到帧后

12、，差错检验、转交处理，接收方收到帧后，差错检验、转交处理，发送方收到应答后，准备发送下一帧，都发送方收到应答后，准备发送下一帧，都需要需要“处理时延处理时延” 。ABt0t1t6t7t2t3t4t5Data frameACK frametLt P = t2 t0 = t3 t1 = L / v 传播时延传播时延t F = t1 t0 = t3 - t2 = F / C 发送时延发送时延t A = t5 t4 = A / C 应答帧发送时延应答帧发送时延t proc= t4 - t3 处理时延处理时延 L 节点节点A 与与 B 之间的距离之间的距离 v 信号传播速率信号传播速率 （3 108 m

13、 / s） F 数据帧长度数据帧长度 = H + D （帧头数据）（帧头数据） A 应答帧长度应答帧长度 C 数据发送速率数据发送速率 bits/sU = t D / (tF + tA + 2tP + 2tproc) t D = D/C ，t F = F/C， t A = A/C U = D /（FA2C（ tP + tproc ）n不考虑处理时延和传播时延，及应答帧不考虑处理时延和传播时延，及应答帧的开销，则的开销，则U仅与帧结构相关；仅与帧结构相关；n当传播时延较大时，信道利用率很低。当传播时延较大时，信道利用率很低。 tout = 2tP 则成功发送一帧的间隔为则成功发送一帧的间隔为 t

14、T = tF + 2tP tav = tT（1 1个帧的平均传送次数）个帧的平均传送次数）n利用率利用率 U= tD/ tavn有传输差错影响时，差错导致多次重传，有传输差错影响时，差错导致多次重传，信道利用率更低。信道利用率更低。n除了传播时延、应答开销以外，信道利用除了传播时延、应答开销以外，信道利用率与控制信息长度、信道误码率、控制开率与控制信息长度、信道误码率、控制开销等因素有关。销等因素有关。例例1 信道速率为信道速率为8kb/s，采用停止等待协议，采用停止等待协议，传播时延传播时延tp为为20ms，确认帧长度和处理时，确认帧长度和处理时间均可忽略，问帧长为多少才能使信道利间均可忽略

15、，问帧长为多少才能使信道利用率达到至少用率达到至少50%？解：设帧长为解：设帧长为L bit，则，则 tsL bit / 8Kbps， tp=20ms。 信道利用率信道利用率 ts /（ ts 2 tp） 50%50% 当当 ts 40ms 不等式成立，故帧长不等式成立，故帧长 L 应应 大于等于大于等于320 bit。 例例2 在卫星通信系统中，两个地面卫星通信在卫星通信系统中，两个地面卫星通信站之间利用卫星的转发技术进行通信，信站之间利用卫星的转发技术进行通信，信号从一个地面站经卫星传到另一个地面站，号从一个地面站经卫星传到另一个地面站，若设其传播时延为若设其传播时延为250ms，发送一个

16、数据，发送一个数据帧的时间为帧的时间为20ms (相当于帧长相当于帧长1000比特，比特，速率为速率为50Kbs)，试分析此系统的信道利，试分析此系统的信道利用率。用率。注：由于卫星距离地面较远，电磁波需要较注：由于卫星距离地面较远，电磁波需要较长时间才能从一个地面站传播到另一个。长时间才能从一个地面站传播到另一个。解：信号从一个地面站经卫星传到另一个地面站，解：信号从一个地面站经卫星传到另一个地面站，其传播时延为其传播时延为250ms，发送一个数据帧的时间为，发送一个数据帧的时间为20ms，则从发送站开始发送到数据帧被目的站接，则从发送站开始发送到数据帧被目的站接收，一共需要时间收，一共需要

17、时间 20ms+250ms270ms 不考虑目的站对接收到的数据帧的处理时间和应不考虑目的站对接收到的数据帧的处理时间和应答帧的发送时间答帧的发送时间 (可以认为应答帧非常短可以认为应答帧非常短)，则应，则应答帧也需要经过答帧也需要经过250ms才能被发送站接收到。才能被发送站接收到。 从发送一帧开始，到收到应答所需要的时间为：从发送一帧开始，到收到应答所需要的时间为： 270ms+250ms520ms 则此系统的信道利用率为：则此系统的信道利用率为： 20ms520ms126 41 12 23 34 45 56 67 70 0 后沿后沿 L（W） 前沿前沿H（W）窗口尺寸窗口尺寸 W6 H(

18、W) = L(W) + W1 mod 2n发送窗口发送窗口：01234567012发送窗口发送窗口WT不允许发送这些帧不允许发送这些帧允许发送允许发送 5 个帧个帧(a)01234567012不允许发送这些帧不允许发送这些帧还允许发送还允许发送 4 个帧个帧WT已发送已发送(b)01234567012不允许发送这些帧不允许发送这些帧WT已发送已发送(c)01234567012不允许发送这些帧不允许发送这些帧还允许发送还允许发送 3 个帧个帧WT已发送已发送 已发送已发送并已收到确认并已收到确认(d)不允许接收这些帧不允许接收这些帧01234567012WR准备接收准备接收 0 号帧号帧(a)不

19、允许接收这些帧不允许接收这些帧01234567012WR准备接收准备接收 1 号帧号帧已收到已收到(b)不允许接收这些帧不允许接收这些帧01234567012WR准备接收准备接收 4 号帧号帧已收到已收到(c)接收窗口控制接收窗口控制接收窗口接收窗口 差错产生的原因差错产生的原因n码间距离码间距离 ：两个码字的对应：两个码字的对应位取值不同的个数。例：位取值不同的个数。例：10100010010010011010110110001001码间距离码间距离 d = 3例例2 000000 000111 111000 111111收到收到0101114 1 5 2恢复恢复000111n检错码检错码n

20、纠错码纠错码 汉明码（汉明码（Hamming)n线性分组码的性质线性分组码的性质 封闭性：任意两个有效码组之和（模封闭性：任意两个有效码组之和（模2加）仍加）仍为一个有效码组。为一个有效码组。 码的最小距离等于非零码最小重量。码的最小距离等于非零码最小重量。S1 S2 S3 出错码出错码S1 S2 S3 出错码出错码 0 0 0 无差错无差错0 1 1 c30 0 1 c01 0 1 c40 1 0 c11 1 0 c51 0 0 c21 1 1 c6例如例如 A A4 4=0111001=0111001，对应的码多项式为，对应的码多项式为 ：码多项式码多项式 (n(n，k)k)循环码中，为了

21、便于描述与计算，循环码中，为了便于描述与计算，经常使用经常使用 n-1 n-1 次次 码多项式来表示码字，码多项式来表示码字，码字码字 A =aA =an-1n-1 a an-2n-2 a a1 1 a a0 0 ，它对应，它对应的码多项式为：的码多项式为：01222211)(axaxaxaxaxAnnnn11001110)(345234564xxxxxxxxxxA 在在(n(n，k)k)循环码中，存在循环码中，存在惟一惟一的最高的最高幂次为幂次为(n-k)(n-k)，最多，最多 k-1k-1 个个连续连续的的 0 0 项，项，且且常数项必须为常数项必须为1 1 的码多项式的码多项式g(x)g

22、(x)，此，此码多项式的幂次最低（码多项式的幂次最低（0 0 元除外）；其元除外）；其它所有的码多项式都能被它所有的码多项式都能被g(x)g(x)整除；并整除；并且且g(x)g(x)是是 x xn n+1 +1 的一个因式。的一个因式。 g(x)g(x)称为称为该编码集的该编码集的生成多项式生成多项式。生成多项式生成多项式 g(x)g(x)CRC-16 CRC-CCITTCRC-321)(21516xxxxg1)(51216xxxxg1)(245781011121622232632xxxxxxxxxxxxxxxg 标准生成多项式标准生成多项式选择选择 r 阶生成多项式阶生成多项式 G(x) ，

23、rnk在数据帧末尾加在数据帧末尾加 r 个个0，形成多项式，形成多项式 xrM(x) xrM(x) R(x) G(x) G(x)移项得：移项得： xrM(x) R(x) Q(x) G(x) 发送循环码多项式发送循环码多项式 T(x) = xrM(x) R(x)检错标准：接收端检测检错标准：接收端检测T(x) / G(x)是否为零是否为零 Q(x) 101100110000100111010110010011010100000010101100110100 余数余数10110011 0100发送信息流为：发送信息流为：余数余数 G(x)发送序列发送序列T(x) =xrM(x) 余数余数xrM(x

24、)HDLC的帧结构的帧结构FFA CIFCSF 帧标志帧标志 01111110A 地址字段地址字段C 控制字段控制字段I 信息字段信息字段FCS 帧校验序列帧校验序列N(S)0N(R)N(R)0 1TYPETYPETYPE11ISUP/FP/FP/FFFA C FCS短帧短帧长帧长帧信息信息 Info标志标志 F标志标志 F地址地址 A控制控制 C帧检验序列帧检验序列 FCS帧帧 FrameHDLC的帧结构的帧结构比特比特888可变可变168信息信息 Info标志标志 F标志标志 F地址地址 A控制控制 C帧检验序列帧检验序列 FCS透明传输区间透明传输区间FCS 检验区间检验区间标志字段标志

25、字段 F数据中某一段比特组合恰好数据中某一段比特组合恰好出现和出现和 F 字段一样的情况字段一样的情况0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0会被误认为是会被误认为是 F 字段字段发送端在发送端在 5 个连个连 1 之后之后插入插入 0 比特再发送出去比特再发送出去填入填入 0 比特比特0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0在接收端将在接收端将 5 个连个连 1 之后之后的的 0 比特删除，恢复原样比特删除，恢复原样在此位置删除填入的在此位置删除填入的 0 比特比特0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0P/F0N(R)N(S)N(R)N(R)N(R)P/FP/FP/FRR0 0RNR0 1REJ1 00 10 10 1N(R) P/F1 10 1SR