ch3数据链路控制11-ARQ.ppt

数据链路控制 forWAN 基本概念 数据电路是一条通信双方的物理电路段 中间不含任何交换节点 是在线路或信道上加信号变换设备之后所形成的二进制比特流通路 由传输信道加DCE组成 物理电路物理链路链路数据链路具备逻辑上的控制关系 数据电路 规程一条物理链路可以构成多条数据链路 复用时 物理链路的基本结构点到点链路 主站发信息或命令 从站发确认或响应 复合站兼有主从站功能多点链路 一站为控制站 其余各站为受控站 分组交换机 DTE DCE DTE 物理链路 数据链路 数据链路控制的功能 屏蔽物理层不同的通信环境和条件 向高层提供可靠几乎无差错 透明的逻辑信道 主要功能成帧控制用帧格式来分割和调节物理层比特流的传送 以便于数据的传送处理 缓冲准备 和差错控制 帧同步编址点到点如X 25中标识DTE DCE90页 多点链接须保证每一帧都能送到正确的地址 流量控制是一种使目的端实体可以调节源端实体发出PDU流量的协议机制 限制数据发送的数量或速率 通过采用应答机制来调节通信双方在处理能力上的差异 通常是使用窗口技术来控制数据的传输节奏 以调节通信双方的缓冲区的使用 差错控制用途 处理PDU丢失或损坏情况通过差错检测 通过检错编码发现传输中出现的差错 和PDU重传 检错重发 重发分为应答重发 被动纠错 和超时重发 主动纠错 差错恢复 若采用纠错编码则自动改正 开销大 差错控制和流量控制通常在一个单一的机制中一起实现 也可以在多种协议级别上实现数据和控制信息的识别在同一帧中 在同一信道中传送 帧格式透明传输不管所传数据是什么样的比特组合 即使与某一控制信息完全一样也可以 都能在物理链路上传送 且保证收方不会误判 链路管理数据链路的建立 维持和释放过程 链路控制机制 三种常用的流量及差错控制技术停等协议Go back N 连续ARQ 选择重传ARQSelectiveRepeat后两种是滑动窗口技术的两个特例 最理想的数据传输假定1 链路是理想的传输信道 不会出错和丢失 假定2 不管发方以多快的速率发送数据 收方总来得及收下 并及时上交主机 接收缓冲区容量无限大永不会溢出或收发速率精确相等 则 此数据传输不需要2层协议 停等协议 stopandwait 具有最简单流量控制的L2协议假定1 链路是理想的传输信道 不会出错和丢失 假定2 不成立则 为使收方的接收缓冲区不会溢出 在最简单情况下 发方每发一数据帧停等收方发来ACK帧 之后再发下一数据帧 使收发双方能够同步 广义 由收方控制发方的数据流量是计算机网络中流量控制的一个基本方法 具有最简单流量控制的L2协议算法 发方算法从主机取一个数据帧送入L2的发送缓存将缓存中的数据帧发出去等待直至收到接收结点发过来的信息从主机取一个新的数据帧转2 收方算法等待直至收到发来的数据帧放入L2的接收缓存向发方发信息转1 A B tF tF Dataframe ACKframe t l tA tA tproc tP 停等协议通信过程 tprop l v传播时延 propagationtime lA和B的距离v传播速度 propagationspeed 2or3 105km stF传送一帧的时间 F C H D CtA传送一确认帧的时间 transmissiontime Fframelength H D控制信息和数据信息C数据发送速度 datatransmissionspeed tproc每个站对一个到来的时间做出反映的处理时间 信道利用率U tD TT tF tA 2tprop 2tproc tF 2tpropT是发送一个帧和收到一个确认并准备好发送下一帧的时间吞吐量 每秒帧数 1 T归一化吞吐量S 1 tF 2tprop 1 tF tF tF 2tprop 1 1 2 tprop tF 实用的停等协议现状1 传输数据的信道不可靠 有差错 数据帧损坏 丢失确认帧损坏 丢失现状2 需要对数据的发端进行流量控制 确认帧ACK否认帧NAK帧有错 CRC检错超时定时器设重发时间 帧丢失时防死锁 发送序号N S 在数据帧中设置 防重复帧发送序号由发方设置 收方查询编号方案V S V R 发送 接收状态变量 0 1交替变化 发送结点 从主机取一个数据帧 网络层交付 令V S 0 令N S V S 即将V S 写入数据帧的发送序号 并将数据帧送交发送缓冲区 将发送缓存中的数据帧发送出去 设置超时定时器 选择适当的重发时间tout 等待以下3个事件中最先出现的一个 若收到ACK 则从主机取一新帧 令V S 1 V S 更新 准备发下一数据帧 转 若超时定时器时间到 或 收到NAK 则转 可见重发时N S 未变 停等协议 5 注意 tout tA 2tprop 2tproc 2tprop发送端在发完数据帧时 须保留发送缓存中的此数据帧的副本 等收到对方发来的ACK时方可清除 协议中发方等到一个肯定的确认之后才进展到下一个数据 常称为带重发的肯定确认 PAR 或ARQ 自动重复请求 接收结点 令V R 0 V R 初始化 其值等于欲接收的数据帧的发送序号 等待 直到收到一个数据帧 检查有无产生传输差错 如用CRC 若有 则转 否则 若N S V R 则丢弃此数据帧 并转 否则 将收到的数据帧中的数据部分送交网络层 令V R 1 V R 准备接收下一数据帧 发送确认帧ACK 转 发送否认帧NAK 转 注意 N S V R 表明收到的是重复的数据帧 该帧应丢弃但收方仍发ACK 发方的数据帧丢失或收方的确认帧丢失都会导致重发 N S V R 表明收到的是新的 非重复 且非被损坏的数据帧 吞吐量1 T假设超时时间值等于2倍的传播时延值发送成功一个帧所需的平均时间T Nx tF 2tprop 设P1为丢失数据帧的概率 P2为丢失ACK帧的概率 则帧发送成功的概率为 1 P1 1 P2 有故障的概率为P 1 1 P1 1 P2 每帧传送的平均次数Nx 1 P 2P 1 P 3P2 1 P P 1 P 1 1 P 归一化吞吐量 1 T 1 tF 1 P 1 2 传播时间 传输时间 l v F C lC vF归一化吞吐量随帧长增加而增加 随距离增加而减小 随发送速度 数据率 增加而减小 所有滑动窗口协议中 每个外出帧包含一个序号 0 某一最大值 序号字段为n比特时编号最大值通常为2n 1 停等滑动窗口协议n 1 序号为0或1 所有滑动窗口协议的精髓在于 在任何时刻发方维持一张允许发送的帧的序号表 这些帧落于发送窗口sendingwindow内 类似还有接收窗口对应一组允许接受的帧的序号表 发方的和收方的窗口不用具有相同的上下限 lowerandupperlimits 及相同的大小 SlidingWindowprotocols 发送窗口 发送端维护的一个允许并已被发出但尚未被确认的帧的序号表 其中的序号连续 发送窗口的上界表示要发送的下一个帧的序号 下界表示未得到确认的帧的最小编号 发送窗口大小 上界 下界 大小可变 最大发送窗口尺寸WT 发送端可以不等待收方应答而连续发送的最大帧数 因为当前在发送窗口内的帧可能最终在运送中丢失或损坏 所以发方必须在内存中保留所有这些帧以备可能的重发 故须设置最大窗口尺寸 缓存大小 在没有收到对方确认的条件下发方可连续发送的帧数 发送窗口滑动机制有新分组从网络层到来且窗口未增到最大尺寸时 窗口上沿增1 确认来到时 检查确认序号 落在发送窗口内则顺时针滑动发送窗口 否则不做处理 在连续ARQ中为使协议正确 1 WT 2n 1 n为序号的比特数 WT 2n时若ACK全部丢失 发方会误判0号重复帧为新的数据帧 滑动窗口协议 2 V S 01230 例1 WT 2n n 2 ACK全部丢失 一直没收到确认 窗口已至最大尺寸 关闭网络层 0 1 2 3 0 N S tout V R 012301 超时重发帧0 V R 0 N S 故收下 新帧 实为重复帧 错 V S 0123 例2 WT 2n 1 n 2 ACK全部丢失 一直没收到确认 窗口已至最大尺寸 关闭网络层 0 1 2 0 N S tout V R 0123 超时重发帧0 V R N S 故不收下0号帧 但发ACK OK 3 tout 1 2 ACK0 新数据帧 接收L2窗口对应可以 允许 接受的帧 任何落于窗口外的帧一概丢弃 当一个序号等于窗口下沿的帧收到时 被传递给网络层 并产生一个确认 响应帧 窗口还要旋转一格 大小固定 与发送窗口不同 收方的窗口总是保持其最初的大小 窗口尺寸为1指数据链路层只顺序接受帧 但对于较大窗口不这样 与之对比 网络层总是按正确的顺序纳入数据 不管L2的窗口尺寸 在连续ARQ中 WR 1 滑动窗口协议 3 1比特的滑动窗口协议AProtocolUsingGoBacknAProtocolUsingSelectiveRepeat 滑动窗口协议 4 滑动窗口协议 5 1比特的滑动窗口协议 AOneBitSlidingWindowProtocol 协议特点 窗口大小 N 1 发送序号和接收序号的取值范围 0 1 可进行数据双向传输 信息帧中可含有确认信息 piggybacking技术 信息帧中包括两个序号域 发送序号和接收序号 已经正确收到的帧的序号 为提高传输效率而设计 解决办法 连续发送多帧后再等待确认 称为流水线技术 pipelining AProtocolUsingGoBackn协议特点 接收方从出错帧起丢弃所有后继帧 接收窗口为1 对于出错率较高的信道 浪费带宽 滑动窗口协议 6 退后n帧协议 续 发送方有流量控制 为重传设缓冲 发送窗口未满 EnableNetworkLayer发送窗口满 DisableNetworkLayer发送窗口大小 序号个数 MaxSeq 1 退后n帧重发 由于有多个未确认帧 设多个计时器 AProtocolUsingSelectiveRepeat协议特点接收窗口大于1 先暂存出错帧的后继帧 只重传坏帧 对最高序号的帧进行确认 接收窗口较大时 需较大缓冲区 滑动窗口协议 7 滑动窗口协议 8 AProtocolUsingSelectiveRepeat cont 目的在不可靠信道上有效传输时 不会因重传而浪费信道资源 采用选择重传技术 基本原理发送窗口大小 MaxSeq 接收窗口大小 MaxSeq 1 2保证接收窗口前移后与原窗口没有重叠 设MaxSeq 7 若接收窗口 7 发方发帧0 6 收方全部收