数据链路层涉及的内容 两台相邻机器间实现可靠有效的完整信息块（帧）通 信的一些算法，不关注单个比特传输； 相邻的概念：两台机器通过一条通信信道连接起来， 通信信道在概念上就像一条线路； 数据链路层的信道特性： 信道上传递的比特顺序与发送顺序完全相同； 信道线路有可能出错； 线路上存在延迟； 避免过快的发送速率湮没接收方。 主要内容 数据链路层要点 定义 为网络层提供服务 成帧 差错控制 流量控制 错误检测和纠正 纠错码 检错码 主要内容 基本的数据链路层协议 无约束单工协议 单工停等协议 有噪声信道的单工协议 滑动窗口协议 一比特滑动窗口协议 退后n帧协议 选择重传协议 主要内容 协议说明与验证 通信协议中的形式化描述技术 有限状态机模型 Petri网模型 常用的数据链路层协议 高级数据链路控制规程 HDLC Internet数据链路层协议 数据链路层定义 ISO关于数据链路层的定义 数据链路层的目的是为了提供功能上和规程上的方法 ，以便建立、维护和释放网络实体间的数据链路。 要解决的问题 如何在有差错的线路上，进行无差错传输。 分组与成帧 分组 净载荷域尾头 发送机器 帧 分组 净载荷域尾头 发送机器 帧 分组与成帧 L3数据 从网络层 数据 链路层 L2数据 T2H2帧 L3数据 到网络层 数据 链路层 L2数据 T2H2 帧 到物理层从物理层 数据链路层概念与术语 结结点（node）：网络络中的主机（host）和路由器（router ）称为结为结 点 链链路（link）：通信路径上连连接相邻结邻结 点的通信信道称为为 链链路。 数据链链路层协议层协议 定义义了一条链链路的两个结结点间间交换换的数 据单单元格式，以及结结点发发送和接收数据单单元的动动作。 数据链路层概念与术语 端到端（end to end）与点到点（point to point） 从源结结点（source node）到目的结结点（destination node ）的通信称为为端到端通信，通信路径（path）可能由多个 链链路组组成。 在相邻结邻结 点间间的一条链链路上的通信称为为点到点通信。 虚拟拟数据通路，实际实际 数据通路 (a)虚拟通信过程 (b)实际通信过程 数据链路层功能 数据链路控制规程 为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制 方式。 数据链路层协议应提供的最基本功能 数据在数据链路上的正常传输（建立、维护和释放） 定界与同步，也处理透明性问题 差错控制 顺序控制 流量控制 数据链路层功能 -为网络层提供服务 为网络层提供三种合理的服务 无确认无连接服务，适用于 误码率很低的线路，错误恢复留给高层； 实时业务 大部分局域网 有确认无连接服务，适用于不可靠的信道，如无线网。 有确认有连接服务 数据链路协议的位置 数据链路层功能-成帧（Framing） 将比特流分成离散的帧，计算每个帧的校验和 。 成帧方法： 字符计数法 带字符填充的首尾字符定界法 带位填充的首尾标记定界法 物理层编码违例法 成帧-字符计数法 字符计数法方法 在帧头中用一个域来表示整个帧的字符个数 缺点：若计数出错，对本帧和后面的帧有影响。 成帧 带字符填充的首尾字符定界法 带字符填充的首尾字符定界法 起始字符 DLE STX，结束字符DLE ETX 字符填充 缺点：局限于8位字符和ASCII字符传送。 网络层发送 数据链路层 层填充 网络层接收 成帧 带位填充的首尾标记定界法 带位填充的首尾标记定界法 帧的起始和结束都用一个特殊的位串“01111110”，称为标 记(flag) “0”比特插入删除技术 成帧 物理层编码违例法 物理层编码违例法 只适用于物理层编码有冗余的网络 802 LAN：Manchester encoding or Differential Manchester encoding 用high-low pair/low-high pair表示 1/0，high-high/low-low不表示数据，可以用来做定界符 。 数据链路层功能-成帧小结 注意：在很多数据链路协议中，使用字符计数法和 一种其它方法的组合，以保证额外的安全性。 当一帧到达时，首先利用计数域定位到该帧的结束 处，只有当这个位置上确实出现了正确的分界符， 并且帧的校验和也正确的时候，该帧才能被认为是 有效的。否则得话，接收方再输入流中扫描下一个 分界符。 数据链路层功能-差错控制（1） 要解决的问题：如何保证所有的帧最终都被递交给 目标机器上的网络层，并且保证正确的次序。 一般方法：接收方给发送方一个反馈（响应）。 肯定的确认 否定的确认重传 数据链路层功能-差错控制（2） 出错情况 帧（包括发送帧和响应帧）出错； 帧（包括发送帧和响应帧）丢失 通过计时器和序号保证每帧最终交给目的网络层仅 一次是数据链路层的一个主要功能。 数据链路层功能-流量控制 问题：如何解决发送帧的速度超过接收方能够接收这些 帧的速度。 方法： 基于反馈的流控制(feedback-based flow control) 基于速率的流控制(rate-based flow control) 网络实际设计中，流量控制主要在传输层实现 差错特点与类型 差错出现的特点 随机 连续突发（burst） 差错类型 单比特错：给定数据单元中只有一个比特发生01突变 多比特错误：给定数据单元中有两个或两个以上不连续 的比特发生01突变 突发错误：给定数据单元中有两个或两个以上连续的比 特发生01突变 处理差错的两种基本策略 处理差错的基本策略是采用冗余信息来进行信 息的错误检测或校验。 两种基本策略： 使用纠错码(error-correcting code) 使用检错码(error-detecting code) 纠错码 (error-correcting code) 发送方在每个数据块中加入足够的冗余信息， 使得接收方能够判断接收到的数据是否有错， 并能纠正错误。 使用纠错码的技术通常也称为前向纠错 (forward error correction, FEC)。 通常应用于如无线信道等错误发生频繁的信道 上。这些信道采用冗余信息计算出原始的信息 块内容，不采用重传（因为重传的数据也可能 是错误的）。 检错码 (error-detecting code) 发送方在每个数据块中加入足够的冗余信息， 使得接收方能够判断接收到的数据是否有错， 但不能判断哪里有错。 通常应用于误码率很低的信道，如光纤、以太 网。 使用纠错码传数据，效率低，适用于不可能重 传的场合；大多数情况采用检错码加重传。 冗余技术 101000000001010101010 生成函数 1011101 101000000001010101010 1011101 发送方接收方 校验函数 接收 拒绝 数据及冗余校验 校验方法 校验方法 垂直冗 余校验 纵向冗 余校验 循环冗 余校验 校验和 垂直冗余校验（VRC） 最简单的例子是奇偶校验，在数据后填加一个奇偶位 （parity bit） 例：使用偶校验（“1”的个数为偶数） 10110101101101011 10110001101100010 垂直冗余校验(VRC)的可靠性 奇偶校验可以检查所有单比特错误 奇偶校验可以检查所有奇数个比特错误 奇偶校验不能检查所有偶数个比特错误 用奇偶校验检测2比特错误 既然单比特奇偶校验能检测出单比特错误，那么 ，再增加奇偶校验位就能检测出多比特错误。 例如，要检测两比特错误。一种途径是使用两个 奇偶校验，一个对奇数位，一个对偶数位。 纵向冗余校验(LRC) 纵向冗余校验(LRC)是在两个维上的垂直冗余校验 (VRC)。为增加检测出多比特错误和突发错误的可能性 ，需要通过对数据中每个比特扫描两次来加大校验的复 杂性。 纵向冗余校验(LRC) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 纵向冗 余校验 整个数据块的传输方向 每个数 据块的 传输方 向 垂直冗余校验 纵向冗余校验(LRC)的可靠性 LRC技术极大地提高了发现多比特错误和突发错误的 可能性。 缺点：对所有偶数个数据单元的偶数个相同位置发生 错误的情况，无法检测出来 循环冗余码(CRC码) 循环冗余码（CRC码，多项式编码）是最有效的一种 冗余校验错误。 CRC是基于二进制除法的。它是在数据单元的末尾附 加一串冗余比特（循环冗余码或循环冗余校验余数） ，使得整个数据单元可以被一个预定的二进制数所整 除。 循环冗余码(CRC码) 循环冗余码的多项式表示： 110001，表示成多项式 x5 + x4 + 1 多项式除法采用的是模2运算 000 101 011 110 000 101 011 110 循环冗余码(CRC码) 在数据传输终点，能够整除的数据就认为数据单元在 传输过程当中没有遭到破坏。 CRC码基本思想： 校验和（checksum）加在帧尾，使带校验和的帧的多 项式能被G(x)除尽；收方接收时，用G(x)去除它，若有 余数，则传输出错。 生成多项式G(x) 发方、收方事前商定； 生成多项式的高位和低位必须为1 生成多项式必须比传输信息对应的多项式短。 校验和计算算法 设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为m + r位，相应多项式为xrM(x)； 按模2除法用对应于G(x)的位串去除对应于xrM(x) 的位串； 按模2减法从对应于xrM(x)的位串中减去余数（等 于或小于r位），结果就是要传送的带校验和的多 项式T(x)。 CRC的检错能力 发送：T(x)；接收：T(x) + E(x)； 余数(T(x) + E(x) / G(x) = 0 + 余数(E(x) / G(x) 若 余数(E(x) / G(x) = 0，则差错不能发现；否则 ，可以发现。 CRC的检错能力 如果只有单比特错，即E(x) = xi，而G(x)中至少有 两项，余数(E(x) / G(x) 0，所以可以查出单比特 错； 如果发生两个孤立单比特错，即E(x) = xi + xj = xj (xi-j + 1)，假定G(x)不能被x整除，那么能够发现两 个比特错的充分条件是：xk + 1不能被G(x)整除 (k i - j)； 如果有奇数个比特错，即E(x)包括奇数个项，G(x) 选(x + 1)的倍数就能查出奇数个比特错； CRC的检错能力 具有r个校验位的多项式能检查出所有长度 r 的突 发性差错。长度为k的突发性连续差错（并不表示 有k个单比特错）可表示为 xi (xk-1 + + 1)，若G(x) 包括x0项，且 k - 1小于G(x)的阶，则 余数(E(x) / G(x) 0; 如果突发差错长度为 r + 1，当且仅当突发差错和 G(x)一样时， 余数(E(x) / G(x) = 0，概率为1/2r-1; 长度大于 r + 1的突发差错或几个较短的突发差错发 生后，坏帧被接收的概率为 1/2r。 多项式国际标准 四个多项式已成为国际标准 CRC-12 = x12 + x11 + x3 + x2 + x + 1 CRC-16 = x16 + x15 + x2 + 1 CRC-CCITT = x16 + x12 + x5 + 1 CRC-32 = x32 + x26 + x23 + x22 + x16+ x12 + x11 + x10+ x8 + x7 + x5 + x4 + x2 +