清华大学计算机网络ch5电子教案.ppt

5.5 协议说明与验证（7） 协议验证 验证协议说明是否完整正确，以协议说明为基础，涉及逻辑证明。 主要用于系统实现前的设计阶段，为了避免可能出现的设计错误。原则上验证涉及协议所有可能的状态。 可达性分析是一种常用的验证方法 利用图论知识可以解决状态的可达性问题； 可达性分析能够用来解决协议的不完整性、死锁和无关变迁等问题。 5.5 协议说明与验证（8） 5.5.3 Petri网模型 Petri网模型最早在1962年 Carl Adam Petri的博士论文中提出来，主要特性是具有较强的对并行、不确定性、异步和分布的描述能力和分析能力。 Petri网研究的系统模型行为特性包括 状态的可达（reachability） 位置的限界（boundedness） 变迁的活性（liveness） 初始状态的可逆达（reversibility） 标识（marking）之间的可达（reachability） 事件之间的同步距离（synchronic distance） 公平性（fairness） 5.4 滑动窗口协议（1） 单工 —— 全双工 捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。 优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断； 带来的问题：复杂。 本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。 5.4 滑动窗口协议（2） 滑动窗口协议（Sliding Window Protocol）工作原理： 发送的信息帧都有一个序号，从0到某个最大值，0 ~ 2n - 1，一般用n个二进制位表示； 发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口 = 上界 - 下界，大小可变； 发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1； 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧； 接收窗口表示允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。 Fig. 3-12 5.4 滑动窗口协议（2） 5.4.1 一比特滑动窗口协议（A One Bit Sliding Window Protocol） 协议特点 窗口大小：N = 1，发送序号和接收序号的取值范围：0，1； 可进行数据双向传输，信息帧中可含有确认信息（piggybacking技术）； 信息帧中包括两个序号域：发送序号和接收序号（已经正确收到的帧的序号） 工作过程 Fig. 3-13 5.4 滑动窗口协议（3） 存在问题 能保证无差错传输，但是基于停等方式； 若双方同时开始发送，则会有一半重复帧； Fig. 3-14 效率低，传输时间长。 5.4 滑动窗口协议（4） 5.4.2 退后n帧协议（A Protocol Using Go Back n） 为提高传输效率而设计 例： 卫星信道传输速率50kbps，往返传输延迟500ms，若传1000bit的帧，使用协议4，则传输一个帧所需时间为： 发送时间 + 信息信道延迟 + 确认信道延迟（确认帧很短，忽略发送时间）= 1000bit / 50kbps + 250ms + 250ms = 520ms 信道利用率 = 20 / 520 ? 4% 一般情况 信道带宽b比特/秒，帧长度l比特，往返传输延迟R秒，则信道利用率为 (l/b) / (l/b + R) = l / (l + Rb) 结论 传输延迟大，信道带宽高，帧短时，信道利用率低。 5.4 滑动窗口协议（5） 解决办法 连续发送多帧后再等待确认，称为流水线技术（pipelining）。 带来的问题 信道误码率高时，对损坏帧和非损坏帧的重传非常多。 两种基本方法 退后n帧（go back n） 接收方从出错帧起丢弃所有后继帧； 接收窗口为1； 对于出错率较高的信道，浪费带宽。 Fig. 3-15(a) 5.4 滑动窗口协议（6） 选择重传（selective repeat） 接收窗口大于1，先暂存出错帧的后继帧； 只重传坏帧； 对最高序号的帧进行确认； 接收窗口较大时，需较大缓冲区。 Fig. 3-15(b) 5.4 滑动窗口协议（7） 退后n帧协议 协议特点 发送方有流量控制，为重传设缓冲； 发送窗口未满，EnableNetworkLayer 发送窗口满，DisableNetworkLayer 发送窗口大小 序号个数（MaxSeq + 1