计算机通信网之数据链路层.ppt

linwei 1 数据链路层 第三章 linwei 2 主要内容 3 1数据链路层设计要点3 2错误检测和纠正3 3基本数据链路层协议3 4滑窗协议3 5协议验证3 6数据链路层协议示例 linwei 3 3 1数据链路层的设计要点 为网络层提供的服务成帧差错控制流量控制 linwei 4 链路层基本功能 向网络层提供一个服务接口处理传输错误调节数据流 流控 linwei 5 分组与帧之间的关系 linwei 6 虚拟通信和实际通信 a 虚拟通信 b 实际通信 linwei 7 数据链路层提供的服务 无确认的无连接服务用于低误码率链路或对误码不敏感的业务 fiber utp real time 有确认的无连接服务用于高误码率链路 Wireless 有确认的面向连接的服务保证每个帧真正接收到且只接收一次 为网络层进程提供一个可靠的位流 linwei 8 例子 数据链路协议的位置 linwei 9 DLL将原始码流分解为离散的单元 该单元称为帧 那么接收端如何检测帧的边界呢 或者说接收端如何界定帧的开始和结束呢 讨论4种方法 字符计数法含字节填充的分界符法含位填充的分界标志法编码违例 成帧 linwei 10 字符计数法 一个字符流 a 无差错 b 有一个差错 linwei 11 字符填充 a 有标志字节作为分界的帧 b 字节填充前后的4个字节序列例子 linwei 12 比特填充 Bit填充 标记01111110 a 原始数据 b 线路上的数据 c 删除填充后存储在接收方存储器中的数据 linwei 13 编码违例 适用于 物理介质上的编码方法中包含冗余信息 的网络 例如有些LAN用2个物理位来编码1位数据 1 位是 高 低 电平对 0 位是 低 高 电平对 而 高高 低低 电平对不用于数据 则可用于帧定界 优点是没有额外带宽开销 linwei 14 为了保证所有的帧最终传送到 有可能顺序的 目的端 需要三个部件 Acknowledgments Timers SequenceNumbersAcknowledgments 当接收端正确接收一个帧 它会向发送端返回一个ACK帧用于指示发端该帧已正确接收 在某些系统 如果接收的帧不正确 接收端会发端返回一个NACK NegativeACK 用于指示该帧没有正确接收 提示发端不用等待定时器超时就立即发送 重传 一个帧 错误控制 linwei 15 Timers 如果没有定时器 当帧丢失或者ACK NACK丢失 会出现什么情况 定时器怎么工作呢 当发送一个帧的时候 发端开启一个定时器 当在约定的时间内 发端接收到ACK NACK 则立即发送 重发 一个帧 且重置定时器 否则当定时超时时 重发该帧 SequenceNumbers 主要解决接收端接收到重复帧的问题 为了避免接收重复帧的问题 给发送的帧分配序列号 这样接收端就能够区分原始帧和重传帧 ErrorControl linwei 16 流控 流控主要是处理发端与接收端之间速率匹配的问题 通常 流控是个动态的过程 取决于负载强度 接收端缓存大小等 常用的方法 基于反馈的流控制基于速率的流控制 从来没有用于DDL linwei 17 3 2错误检测和纠正 纠错码检错码 linwei 18 错误 数据通信中 链路噪声无处不在 并且研究发现 链路噪声引起的比特错误通常是突发性的 而不是独立的 单比特错误 例如 闪电会引起短暂的突发比特错误 linwei 19 纠错码 检测和纠正数据中的错误冗余 redundancy 在数据中加入附加的信息 两种策略 检错码 包含足够的冗余比特检错 然后使用NACK告知发端重传 纠错码 包含足够的冗余比特检测和纠正错误 linwei 20 海明距离 给定两个码子 对其进行异或运算 然后计算出异或结果中1的个数 两个码子中不相同的位的个数称为海明距离 它的意义在于 如果两个码子的海明距离为d 则需要d个1位错误才能将一个码子转变成另一个码子 linwei 21 海明距离 通常 所有2m种可能的数据报文都是合法的 但是并非所有的2n n m r m为数据位 r为冗余位 种码子都被用到 给定计算校验位的算法后 可以构造合法码子列表 并且可以从该表中找到海明距离最小的两个码子 此距离是整个编码方案的海明距离 为了检测d个错误 需要一个距离为d 1的编码方案为了纠正t个错误 需要一个距离为2t 1的编码方案 linwei 22 奇偶位 保证码子中 1 位的数目是偶数 或者奇数 1000000 1 1111101 0 奇偶位的海明距离为2 因此它可以检测单比特错误 但是不能纠错考虑以下的例子 4个有效码子的编码 0000000000 0000011111 1111100000 and 1111111111 编码距离为5 可以纠正2个错误 linwei 23 纠错 设计一种编码方案 每个码子有m个报文位和r个校验位 并且能够纠正所有的单个错误 对于2m合法报文 任一个报文都对应有n个非法的码子 它们与该报文的距离为1 因此每个合法的报文都要求n 1个位模式供他使用 由于总共有2n个位模式 所以有 n 1 2m4 linwei 24 检错码 纠错码代价很大 计算量和带宽 因此用在无线通信较为合适 但是在铜线或者光缆 错误检测和重传机制往往更加有效 例如 若误码是独立的 误码率为10 6 则对于1000bit的数据块 需要10个校验位纠正1个单bit错误 1Mbit的需要10Kbit 显然如果仅仅检测错误 每个数据块1个奇偶位就足够了 每一千个数据块额外传输一个块 因此开销小 利用检错 重传机制 则1Mbit只需2001位 相比之下 海明码需要10000位 最广泛使用的检错码是多项式编码 也称CRC linwei 25 CyclicRedundancyCheck 基本思想 将位串看成系数为0或1的多项式 多项式的算术运算以2为模完成 加减法等同于异或 除法为长除运算 生成多项式G x 事先约定的 最低位 最高位必须是1 校验和 添加到帧序列多项式中 用于检测传输是否有错误 linwei 26 CyclicRedundancyCheck 校验和的计算方法 1 假设G x 的阶为r 在帧的低位端加上r个0位 所以该帧现在包含m r位 对应的多项式为xrM x 2 利用模2除法 用对应于G x 的位串去除xrM x 的位串 3 利用模2减法 从对应于xrM x 的位串中减去余数 结果就是将被传输的带校验和的帧 记为 T x linwei 27 CyclicRedundancyCheck 校验和的计算过程 linwei 28 CyclicRedundancyCheck 分析 1 所有的错误都能检测出吗 错误多项式E x 能被G x 除尽 则这类错误无法被检测 2 所有的一位错误都将被检测到 低阶的多项式可以保护长的帧 K i j 两个独立的一位错误 奇数项多项式不可能被x 1除尽 奇数个位发生错误 带r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误 linwei 29 CyclicRedundancyCheck 通常用到的3种CRC生成多项式 CRC 16 x16 x15 x2 1 usedinHDLC CRC CCITT x16 x12 x5 1CRC 32 x32 x26 x23 x22 x16 x12 x11 x10 x8 x7 x5 x4 x2 x1 1 usedinEthernet 尽管复杂 可以用硬件构造出来 linwei 30 3 3基本数据链路协议 一个无限制的单工协议一个单工的停 等协议有噪声信道的单工协议 linwei 31 基本数据链路协议 几个假设 物理层 数据链路层和网络层都是独立的进程 它们通过报文来相互通信 可靠的 面向连接的服务机器不会崩溃 linwei 32 协议定义 Continued 协议中需要用到的一些定义 这些定义包含在头文件protocol h中 linwei 33 协议定义 ctd 协议中需要用到的一些定义 这些定义包含在头文件protocol h中 linwei 34 无限制的单工协议 假设条件 数据单向传输物理信道无误码 即无帧损坏或丢失发 接收端缓存无限大发端 收端的网络层总是处于准备就绪状态 linwei 35 无限制的单工协议 linwei 36 一个单工的停 等协议 假设 不再假设收端能够无限快速的处理到来的数据 基本思想和特点发端发送一个帧 然后等待确认 stopandwait 确认帧的内容并不重要数据传输是单向的 但是必须是双向链路 因此用一个半双工的物理信道就足够了 linwei 37 单工的等 停协议 linwei 38 有噪声信道的单工协议 假设 信道有噪声 因此可能会丢 损坏帧简单的方法 发端设置一个定时器 如果在规定的时间内没有接收到ACK 则重发该帧 这种方法有没有问题 linwei 39 有噪声信道的单工协议 考虑下面的场景 A传输一个帧B接收到A传来的帧A1B产生ACKACK丢失A定时器超时 重传B得到A1的副本 将会把副本送到网络层 另外一种出现副本的情况是长的时延 使用序列号在这个例子里 1bit就够了 在协议中 发送方在准备下一个数据项目之前先等待一个肯定的确认 则这样的协议称为 PositiveAcknowledgmentwithRetransmission PAR AutomaticRepeatreQuest ARQ linwei 40 有噪声信道的单工协议 一个支持重传的肯定确认协议 Continued linwei 41 有噪声信道的单工协议 一个支持重传的肯定确认协议 linwei 42 3 4滑窗协议 用于双向通信使用同一条线路来传输两个方向上的数据反向信道与前向信道有相同的容量 有两种类型的帧 kind field 数据 Data ACK 含有最新接收帧的序号 linwei 43 捎带确认 Piggybacking Piggybacking 确认信息附在往外 反向链路 发送的数据帧上的行为 优点 更好的利用信道带宽 问题 为了更好的利用带宽 数据链路层应该等待下一个分组多长时间 linwei 44 滑窗协议 每个外发的帧都包含一个序列号 其范围为0 MaxSeq 2n 1 这样的序列号正好可以填到一个n位的域中 等 停滑动窗口协议使用n 1 滑窗协议的本质 在任何时刻 发送方总是维持着一组序列号 分别对应于允许它发送的帧 称这些帧落在发送窗口内 接受方也维持一个接收窗口 对应一组允许他接收的帧 窗口大小可以固定或者不固定 linwei 45 滑窗协议 2 滑窗大小为1 有3个序列号的滑动窗口 a 初始化 b 第1帧发送以后 c 第1帧接收以后 d 第一个确认收到后 linwei 46 滑窗协议 1位滑窗协议GoBackN协议选择性重传协议 linwei 47 1位滑窗协议 Continued linwei 48 1位滑窗协议 ctd linwei 49 1位滑窗协议 2 针对协议4的两种情况 a 正常情况 b 异常情况 记号为 seq ack packetnumber 星号表示网络层接受一个分组 linwei 50 Gobackn协议 停 等协议的一个问题是 往返时延过长1000bitframes50kbpschannel 往返传播时延500ms satellite 发送1000bit的帧到接收方完全接收需要270ms 520ms后收端才能接收到确认 忽略ACK带来的时延 只有4 的有效带宽被利用 效率很差 linwei 51 管道化 利用管道 使得多个帧可以同时在一条链路上传输 性能改善F framesize bits C channelcapacity bps I propagationdelayplusprocessorservicetime seconds Timetotransmitasingleframe F CTotalDelay 2Ilineutilization F F 2CI 50 ifF 2CI linwei 52 GoBackN协议 Gobackn 对用于 接收窗口尺寸为1 的情况如果接收端收到坏帧 则后续的帧 管道中的 无论正确与否全部丢弃丢弃的帧没有ACKs linwei 53 GoBackN滑窗协议 Continued linwei 54 GoBackN滑窗协议 Continued linwei 55 GoBackN滑窗协议 Continued linwei 56 GoBackN滑窗协议 linwei 57 窗口尺寸问题 考虑MAX SEQ 7的场景 发送方发送0 7帧 第7帧的捎带确认最终被送回到发送方 发送方送出另外8帧 其序号仍然是0 7现在第7帧的另一个捎带确认也回来了问题是 属于第二批的8帧全部成功到达了吗 或者是说这8帧全部丢失了 把出错之后丢弃的帧也算作丢失了 在这两种情况下 接收方都会发送第7帧的确认 而发送方无从分辨 由于这个原因 未确认帧 即窗口大小 必须限制为MAX SEQ linwei 58 GoBackN滑窗协议 用软件模拟多个定时器 linwei 59 选择性重传协议 选择性重传 接收窗口尺寸大于1 缓存坏帧以后所有的帧 只对最后一个正确接收的帧进行确认 linwei 60 选择性重传协议 接收侧带宽与链路层缓存之间的折中这两种情况下 发送侧需要缓存 只有接收到ACK后占用的缓存才能释放 为了强制执行 任何时候未确认帧的个数都不应该超过Max Seq 的流控规则 DLL应该能够enable disable网络层 linwei 61 使用选择性重传的滑动窗口协议 Continued linwei 62 Continued 使用选择性重传的滑动窗口协议 2 linwei 63 使用选择性重传的滑动窗口协议 3 Continued linwei 64 使用选择性重传的滑动窗口协议 4 linwei 65 非顺序接收问题 a 窗口大小为7的初始状态 b 7帧都已送出并接收 但是均未被确认 c 窗口大小为4的初始状态 d 4帧都已送出并接收 但是均未被确认 linwei 66 数据重叠 overlap 问题的本质是 当接收方向前移动窗口后 新的有效序列号与老的有效序列号之间有重叠 因此后续的帧可能是重复的帧 也有可能是新的帧 但是接收端无法区分 解决的方法 最大的窗口尺寸应该不超过序列号范围的一半 即 MAX SEQ 1 2 因此对3位序列号 窗口尺寸为4 linwei 67 反向流量轻的问题 之前的假设反向信道负载较重 因为采用捎带确认 如果反向业务轻会如何 确认信息会滞留很长时间极端情况 如果在一个方向上有很大的流量 而另一个方向上根本没有流量 则只有MAX SEQ个分组被发出去 协议就阻塞了 启用start ack timer辅助定时器 如果定时器到期前没有出现反向流量 则发送一个单独的确认帧 linwei 68 3 5协议验证 有限状态机模型Petri网模型 linwei 69 有限状态机模型 协议规范和验证 本节的目的是学习验证协议的方法状态图对于验证协议的正确性和完整性是非常重要的协议机 状态 转换 死锁一个协议的有限状态机模型可以看作是一个四元组 S M I T 其中 S是指进程和信道可能的状态集合M是指能在信道上进行交换的帧的集合I是指进程的初始状态集合T是状态之间转换的集合 linwei 70 FiniteStateMachinedModels a 协议3的状态图 b 转换 linwei 71 Petri网模型 包含两个库所和2个转换的Petri网 库所 变迁 弧和标记 linwei 72 Petri网模型 2 协议3的Petri网模型 linwei 73 3 6数据链路层协议示例 HDLC High LevelDataLinkControlInternet中的数据链路层 linwei 74 High LevelDataLinkCon