第04章数据链路层.doc

第04章 数据链路层一 数据链路层概述1 什么是数据链路？为了在相邻的两个节点间实现可靠的数据传输，除了需要一条物理链路外，还必须有一些规程控制数据的传输把实现这些规程的软硬件加到物理链路上，就构成了所谓的数字链路，我们也称之为逻辑链路链路控制调制解调器 调制解调器 链路控制节点交换机节点交换机数据传输物理链路逻辑链路2 数据链路层的主要功能1）链路管理数据链路的建立、维持和释放就叫链路管理2）帧同步在数据链路层，数据的传送单位是帧帧同步是指接收方能从收到的比特流中识别出一帧的开始和结束3）流量控制发送方发送数据的速率必须得到控制，以使得接收方能够从容接收5）差错控制有两类差错控制方法——前向纠错和检错重发在计算机通信中通常采用检错重发机制提供差错控制功能6）帧格式接收方能识别帧中的每一个字段7）透明传输不管数据是什么样的比特组合，都能在数据链路上传送8）寻址在多点连接的情况下，确保每一帧能到达正确的目的站点同时接收方也能知道发送方是哪个站点二 如何识别一帧的开始和结束？1 带字符填充的首尾界符法FlagHeaderPayload fieldTrailerFlag帧举例 Flag=7EH 填充字符=1BH 原始字符 填充以后 41 33 7E 5C 4B 0C 41 33 1B 7E 5C 4B 0C 41 33 1B 5C 4B 0C 41 33 1B 1B 5C 4B 0C 41 33 1B 7E 5C 4B 0C 41 33 1B 1B 1B 7E 5C 4B 0C41 33 1B 1B 5C 4B 0C 41 33 1B 1B 1B 1B 5C 4B 0C2 带位填充的首位界符法比如，在HDLC帧中，用比特序列01111110表示一帧的开始和结束，当有效载荷中出现连续的5个1，则在其后插入1位0；接收方在收到5个1后自动删除紧随其后的03 物理层编码违例法比如，在曼彻斯特编码中，连续的高电平或连续的低电平可用作帧头和帧尾（令牌环使用该方法）三 检错技术1 校验和将数据按一定长度分段，然后以段为单位相加，若最高位有进位，将进位加到最低位上，形成校验码2 块校验码将所有字符的内码异或，结果为块校验码3 循环冗余校验码（CRC）n 信息多项式M（x） 以k个信息比特为系数的多项式n 生成多项式G（x） 根据多项式理论求得、具有某些特殊属性的多项式n 冗余多项式R（x） 以r个冗余比特为系数的多项式n 码多项式P（x） k个信息比特加r个冗余比特构成的码字所对应的多项式n 如何求冗余多项式？ 用G（x）除x r M（x），得到的余式即为冗余多项式R（x）n 如何求码多项式？ P（x）= x r M（x）+ R（x）n 接收方如何检错？ 用G（x）除收到的码多项式，除尽表示无错n 强调 上面的除法都是模2除法，即加减都采用异或运算，不进位和借位n 国际标准生成多项式举例² CRC-12：x 12 + x 11 + x 3 + x 2 + x 1 + x 0² CRC-16：x 16 + x 15 + x 2 + x 0² CRC-ITU：x 16 + x 12 + x 5 + x 0五 差错控制和流量控制技术1 帧编号通过在帧中加上帧编号字段告诉接收方现在过来的是几号帧。

帧编号字段的长度是有限的，所以帧的编号是循环编号假如帧编号的长度是3比特，则最大的帧编号是7，7号以后的帧又从0开始编号2 应答号通过在帧中包含应答号字段告诉发送方下一次期待接收的是几号帧3 肯定应答帧ACK N接收方收到一个通过校验的帧，给发送方返回一个肯定应答帧ACK N，N是应答号，这意味着接收方已经收下了编号为N -1及其以前的各个帧，期待接收N号帧4 否定应答帧NAK N接收方收到一个没有通过校验的帧，给发送方返回一个否定应答帧NAK N，N是应答号，这意味着接收方没能正确接收第N号帧，但已经正确收下了N -1及其以前的各帧5 滑动窗口技术发送窗口 用来限制在收到对方确认以前能发送的帧的数目；仅当编号落在发送窗口内的数据帧才允许被发送出去；发送窗口的长度WT代表收到对方的确认前发送方最多能发送多少个数据帧；其实，发送窗口的长度就是发送缓冲区能容纳的帧数接收窗口 仅当编号落在接收窗口内的数据帧才允许被接收；接收窗口的长度WR等于接收缓冲区的能容纳的帧数滑动窗口的工作原理如下图所示，其中帧编号字段长度为3比特，发送窗口长度为5，接收窗口长度为1Sendera）初始化b）发送0号帧之后c）收到0号帧之后d）收到ACK0之后0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 receiver6 超时重发也就是所谓的自动重发；发送方每发送一个数据帧，便启动一个定时器，如果在定时时间到之前收到了对该数据帧的确认就关闭它的定时器；一旦一个数据帧的定时器超时，发送方便立即启动重传，或者将该数据帧及其以后的帧重发，或者只重传该数据帧7 GO - BACK- N接收方如果收到NAK N或者N号帧超时，就将N号帧及其以后的帧重新发送一遍8 选择重传接收方如果收到NAK N或者N号帧超时，只重发N号帧9 捎带应答A和B进行双工通信，假设A如果收到来自B的数据帧B6，这时A并不马上回复一个专门的肯定应答帧ACK 7，而是等到有数据帧发给B时，在该数据帧的应答号字段插入编号7，表示已经收到B6及其以前的各帧，期待接收第7帧，这就是所谓的捎带应答六 基本的数据链路层协议1 停等协议的工作原理帧0ACK1 帧1ACK0 帧0ACK1 帧0ACK1 帧1NAK11 帧1ACK0 帧0帧0帧0交网络层帧1交网络层帧0交网络层帧0重复丢弃帧1出错丢弃帧1交网络层帧0交网络层超时超时2 连续ARQ协议的工作原理0 1 2 3 4 5 2 3 3 0 1 E D D D 2 3 3 4 5 4 5 3 6 7 0 6 6 ACK1ACK2NAK2ACK3ACK4ACK57 ACK6重传 3 选择重传ARQ协议的工作原理0 1 2 3 4 5 2 3 6 0 1 E 3 4 5 2 3 6 7 0 7 0 3 1 2 3 1 ACK1ACK2NAK2ACK6ACK7ACK0ACK1ACK22 被数据链路层缓冲的帧ACK3将2至5帧一起交网络层3 重传 七 基本的数据链路层协议的性能分析1 停等协议的性能分析tp帧0ACK0tftout帧1帧1tTtptfACK1SenderReceiver在忽略处理时延和应答帧的发送时延的前提下（如下图所示）t o u t = 2 t Pt T = t f + t o u t = t f + 2 t P假设数据帧出错的概率是P，则重传1次的概率为P（1-P），重传2次的概率为P 2（1-P），重传n次的概率为P n（1-P），则一帧的平均传送次数Nr：=1 + 1 × P（1- P）+ 2 × P 2（1- P）+ 3 × P 2（1- P）+ … = 1 /（1- P）链路的利用率= t f / t T=1/（2a+1）协议的效率E：=1 / Nr × 链路的利用率=（1- P）/（2a+1）其中a = t P / t f ，叫线路的帧时长2 连续ARQ协议的性能分析W T = 3 tftftftftfW T = 5 tftftftftftftftfa = 2 a = 2 链路效率=1 链路效率 = W /（2a+1） n 如果W > = 2a+1，链路的利用率为1n 如果W < = 2a+1，链路的利用率为W / ( 2a+1 )n 协议效率：E = 链路利用率 ×（1 / N r ）n 连续ARQ采用的是后退N帧的重发机制，即当一个数据帧出错时，要重传N个数据帧，而且可能要重传多次才能成功n 假设一个数据帧传送了i次才成功（重传了i -1次），则为了纠正该数据帧一共传送的帧数：f（i）= 1 + （i -1）N = 1- N + N in 所以为了成功传送一个数据帧，平均传送的帧数：N r = ∑ f（i）P i - 1（1- P）= 1 + N /（1 - P）n 当W > = 2a+1时，N近似等于2 a + 1；当W < = 2a+1时，N近似等于W3 选择重传ARQ协议的性能分析n 对于选择重传ARQ协议而言，一帧的平均传送次数：N r = 1 / （1 - P）n 将该式代入E = 链路利用率 ×（1 / Nr ）即可得选择重传ARQ协议的效率八 高级数据链路控制协议（HDLC）1 HDLC的基本配置1）3种类型的站n 主站 对链路进行控制，主站发出的帧叫做命令帧n 从站 在主站控制下操作，从站发出的帧叫做响应帧n 复合站 具有主站和从站的双重功能，复合站既可发命令帧，又可发响应帧2）两种链路配置n 非平衡配置 适用于点对点和多点链路，有一个主站和一到多个从站，支持全双工和半双工传输n 平衡配置 仅适用于点对点链路，链路两端的两个站都是复合站，支持全双工和半双工传输3）3种数据传输方式n 正常响应方式（Normal Response Mode，NRM）：适用于不平衡配置。

只有主站才能发起向从站的数。