滑动窗口协议Word格式.docx
《滑动窗口协议Word格式.docx》由会员分享，可在线阅读，更多相关《滑动窗口协议Word格式.docx（14页珍藏版）》请在冰点文库上搜索。
则发方数据链路层必须强行关用隔络层直到有一缓冲区可用为止。
收方的数据链路层的窗口对应于允许接收的帧。
任何落在窗口外的帧都不加说明地废弃。
当收到序号先进于窗口下界的正确帧时。
将其交给网络层。
且产生一个确认，窗口整个向前移动一个位置。
不像发方的窗口，收方的窗口总是保持初值大小。
无论数据链路层窗口大小如何，它交给隔络层的分组的顺序总是正确的。
差错控制
在数据链路层停等协议中，对出错帧采取超对重发或再辅之发否定应答（停等ARQ）的差错控制方法。
但这种方法用在可连续发进多帧的滑窗协议中，将产生另外问题；
若已发进的若干帧中有某一帧出错或丢失，因发进端并不知道，所以其仍在继续发送帧。
直到发进窗口占满为止。
数据链路层必须为上层提供无差错的传辅而无差错的传输不仅要防止将出错数据交给上层、还要保证交付数据的顺序也正确的。
当接收端收到一条出错的帧时。
对出错帧后的帧我们能用以下两种基本方法处理这种错误：
一种为后退N连续ARQ方法，即当采用这种方法时，接收端将丢弃出错帧后所有帧。
而不臂这些帧是有效的还是出错的。
待发送端收到对出错帧的否定应答NAK时，将重发从出错帧开始的所有帧；
若应暮帧出错。
则超对重发。
这样做，接收窗口尺寸实际上为1。
换言之，数据链路层除了下次该交给网络层的下一帧之外。
拒绝接收其他任何帧。
如果计时器超时之前。
发进方的窗口填满。
则管道将会空出来。
最终发送过程时间到。
按序重传所有未被确认的帧。
从损坏的帧或丢失的帧开始。
但是，如果错误率高的话。
将会浪费大量的带宽。
另一种方法为选择重发连续AR0，选择重发连续AR0方法提供了更为细致的差错控制手段。
在这协议中，发进过程和接收过程都维持一个可接受序列号的窗口。
发送方的窗口大小从0开始。
增长到某个预定最大值MAX-SEQ。
与之相比。
接收方的窗口总是保持固定大小，并等于MAX-SEQ。
接收方在其窗口中、为每个序列号都提供一个缓冲区。
即接收方存贮所有跟在坏帧后的正确帧。
而只要求发进方重传出错的帧。
如果重传正确，则接收方将存有按顺序帧排列的多个正确帧交给网络层。
且对最高顺序号的帧进行确
认。
选择重发方法的接收端的窗口尺寸可以大于1。
从以上可知，窗13大小是设计中主要考虑的因素。
窗口越大，在接收站的响应返回之前可以发进的帧越多；
但是，窗口大就意味着接收端必须分配更多的资源和更大的缓存空间来应付输^的数据。
如图2所示：
模拟实例
为了进一步了解后退N帧重发滑窗协议和选择重发滑窗协议各自的特点及它们的性能。
我们通过一摸拟器来模拟这些协议。
在模拟器中我们可根据假设输一些不同的参数如：
给定超时的时间间隔（timeottt）、丢失数据帧的百分比（pcLlc~）和坏帧到达的百分比（pcLeksum）等，就可得到一系列所需的结果，把这些结果进行比较就能了解在什么条件下。
两协议郄个更具有优越性。
模拟鼍的基本模块和实现过程模拟器的主程序主要完成main模拟控制、发进器和接收器三个过程。
程序流程如图3所示。
模拟结果
该模拟程序在Linttx环境下运行的。
根据程序要求输超时（timeout）、丢失数据帧的百分比（pcLlc~）和坏帧的百分比（Vzt~ksum）等参数可以得到模拟后退tt帧重发滑窗协议输^、输出结果和选择重发滑窗协议输^、输出的两个表。
（限于篇幅表略）
结论
经分析发现选择重发与后退N帧这两种方法各有千秋。
当超时的时间间隔设为40或50。
丢失帧率和坏帧的到达百分比都为0时，后退N帧方法的链路有救载荷比选择性重发方法的链路有救载荷10％时，使用后退N帧方法的有效载荷为48%，效率仅为27％。
而选择重发方法的链路有效载荷为70%效率为60％。
比较两协议输入、输出结果后可知，当链路上的数据帧出现差错时，选择重发方法的链路有效载菏和效率明显比后退N帧方法高，见图4、5。
这是因为在选择重发滑窗协议中，它只重发出
错的数据帧。
如图2（b）所示。
收方必须保存3，4，5号帧，等待2号帧重发。
但保存这些帧将会消耗宝
贵的缓存空间。
由此可得如下结论：
后退N帻的方法是一种比
较简单的技术，它不需要进行接收帧捧趴。
也不要重新排序，当数据传送链路出错率较低时，后退N连续ARQ的滑窗协议能够工作得很好；
但当传输线路较差时，则因数据帧重发将浪费大量的带宽重传帧，这时我们如采用选择重发连续ARQ的滑窗协议将更为有效。
但是，我们注意到选择重传协议也并非是完善的。
仔细考查会发现它的一些问题。
例如若线路发生故障,发进方会一直地发送（重发）下去，致使上层（主机）即无法再通过它传送其它的帧，也无法停止它的发进而另选其它线路。
实际的协议应该对重发数有所限制，当重发次数超时时，便向上层报告。
由上层进行差错恢复或另选其它线路。
此外协议还应有建立连接、终止连接阶段等因此，实际应用中，还需做很多工作。
存在问题
由于滑动窗口协议无法预知上层下一个应用数据何时到达，因此，在网络流量不太大的情况下，有时可能引起某些问题。
下面以1位滑动窗口协议为例加以分析。
1位滑动窗口协议使用了停一等（stop—and—wait）方式。
发送方发送完一个数据包后，在发送下一个数据包之前，需要等待接收方对已发送数据包的确认。
正常情况下，两个协议层之一首先开始发送数据包，随后双方交替传送数据包及确认。
图1给出了捎带确认的工作示意图。
由图1可知，B在发送其数据包之前，等待A发送数据包A。
；
收到后，将交给上层并向发送第一个数据包。
并确认A。
然后，双方所有的数据包依次被一次性地正确接收。
然而，通过分析发现，1位滑动窗口协议在某些特殊情况下存在着工作效率较低等问题。
例如，当，曰同时开始发送时，双方第一个数据包出现交叉。
即使不出现传输差错，50％的数据包也会发生重复。
当出现多次过早超时，就算是一方明显地先开始工作，也将发生相类似的情况，数据包可能被发送三次或更多次。
图2说明了这种同步的困难性。
改进方案
上述问题的产生是由于协议采用了捎带确认技术。
接收方一旦收到数据包，就要发一个数据包回去。
而且只有当收到的数据包带有对上一次的确认时，才发送新的数据，否则，为发一个单独确认，需将整个数据重新发送一遍。
这就造成在无传输错误和过早超时的情况下仍然会有重复数据包出现。
捎带确认技术对大流量数据通讯的情况是有效的，但对一般应用于不可靠的网络环境中的系统，数据延时和丢失的情况较多，如果仍采用上述处理方式，就会造成网络带宽的浪费。
因此，l位滑动窗口协议改进方案的主要设计思想是取消“捎带确认”，即在原滑动窗口协议的基础上，将处理流程改为：
对接收的数据包进行分析，当收到普通的数据包时，仅对其进行确认；
当收到确认包时，传送下一组数据。
采用该方案，可有效地避免图2中所出现的数据包重复问题。
此外，原有的滑动窗口协议算法一般是将发送和接收功能放在一个模块中实现的，对数据处理能力有所限制。
尤其是，只有在超时或接收到数据的事件发生时，才能进行下一组数据发送。
在某些情况下会影响系统整体的响应时间和实时性。
因此，在新方案实现过程中，将发送和接收过程分开，单独加以实现，使其成为独立并行运行的两个线程，以便于提高系统的整体性能。
正确性验证
一般来说，对协议实现算法的分析及工作次序的描述仅能证明其在某些特殊路径下的正确性，而不能证明整个协议的完备性。
因此，人们常借助某些形式化的技术来描述和验证协议。
有限状态机（FiniteStateMachine）是一种常用的方法。
下面将采用FSM对改进的l位滑动窗口协议进行验证。
在该模型中，系统被描述成有限的状态，每个协议机（protocolmachine）即发送方或接收方在每一时刻总是处于一个特定的状态。
其状态是由所有变量值组成的。
考虑滑动窗口协议中的接收方，可从所有可能的状态中抽象出两种基本状态：
等待序列号为偶数的数据包（简单地表示为0）和等待序列号为奇数的数据包（简单地表示为1）。
易知，在正常情况下，0和l是交叉出现的，其它所有状态均可作为过渡状态加以考虑。
类似地，对于发送方，同样也可以抽象出两种基本状态。
整个系统的状态是两个协议机和两个信道的所有状态的组合。
信道的状态是由其内容决定的。
以改进的l位滑动窗口协议为例，正向信道（从发送方到接收方）有3种状态：
数据包0、数据包l或空信道；
反向信道也有3种状态：
确认数据包0、确认数据包l、空信道。
因而整个系统共有（2x2×
3×
3）=36种不同的状态。
对于每种状态，有0个或多个可能的转换（transition）。
一旦某个事件发生，就会发生转换。
对协议机而言，发送数据包、接收数据包以及超时都会弓I起转换。
对信道而言，典型的事件是：
协议机将一个新数据包插入信道，将数据包传输到协议机，或由于突发事件而丢失数据包。
已知协议机的完整描述及信道的特性，便能以所有状态为节点，以所有转换为方向弧，画出其有限状态机模型图，再利用图论技术对其进行可达性分析（teachabilityanalysis），即可对协议的正确性加以验证。
采用有限状态机模型，可将改进的1位滑动窗口协议形式化成一个四元组模型（S，M，I，T，）。
其中：
s为可到达的状态集合，由l6个状态组成，每种状态用（W，x，y，z）标识，其详细信息在表1中列出。
表l中符号‘一’表示空信道。
因为状态转换事件的限制，所以不少状态是不可达的。
不可达状态在表1中没有给出；
M是能在信道上进行交换的数据／确认包集合，可知M={0，1，A0，Al}；
I是系统初始状态的集合，在本系统中。
I=l（0，0，0，一）}；
T是状态之间转换的集合，系统共有l1种转换。
表2给出了关于集合的描述。
由上面的四元组模型（s，M，I，T，）分析，并根据16个系统可达状态，1个系统初始状态，11种转换及协议算法，最终可以得出本协议的有限机状态图，如图3所示。
图3中，若两个转换一起发生，例如状态（0，1，0，A0）到状态（1，1，1，A0）间的转换，必须两个信道上的数据都到达了对方，则在图中表示为:
2+5；
若两个事件都导致同一状态，例如状态（1，1，一，A。
）到状态（1，1，一，一）间的转换，则在图中表示为0，9。
在协议正常运行情况下，转换1，2，3和4依次周而复始地重复，每一轮循环中，可传递两个分组，并使发送方返回到初始状态。
如果信道丢失了数据包0，则进行从状态（0，0，0，一）到状态（0，0，一，一）间的转换，最终将导致发送过程超时。
由转换7，系统再次回到初始状态。
若协议是正确的，则须满足条件：
“无论什么序号的事件发生，接收方都不可能交付两个奇数序列号的分组，而没有中间的偶数序列号的分组，反之亦然。
”从图3不难得知，此条件可进一步形式化地描述成：
“从初始状态出发，不存在这样一条路径：
两次出现转换l，而在其间没有出现转换3；
反之亦然”也就是说，如果存在这种路径，则表明该协议在某种情况下会丢失数据。
通过分析可知，图3中转换l与转换3只可能交替出现，因此本协议是满足上述条件的。
[1]
该协议所满足的另一个相类似的要求是：
不存在发送过程改变两次状态（从0到l，然后再返回O），而接收过程的状态保持不变的路径。
如果存在这样的路径，则在相应事件的序列中，两个数据包可能消失得毫无踪影，而接收方却毫无察觉。
判断一个协议是否正确的一个重要特性是：
协议不允许发生死锁。
死锁是一种特殊状态。
在死锁状态下，无论发生什么样的事件序列，协议都不可能前进。
用图形模型表示，死锁的特征是：
存在着从初始状态可达的状态子集，该子集具有下列性质：
①没有能跳出该子集的转换；
②在该子集内没有引起前进的转换（向上层递交数据）。
系统一旦处于死锁状态，协议就始终停在那里。
同样地，从图3中很容易看出，该协议没有发生死锁的可能。
[2]
关于是否存在其它错误的路径，如存在一个事件，而这个事件永远不可能发生（多余的转换），以及描述不完全等问题，都可以通过研究图3加以验证。
通过上述分析可知，改进后的l位滑动窗口协议是正确的。
应用
在基金会现场总线中的应用
基金会现场总线的网络体系结构
在基金会现场总线网络中，设备之间传送信息是通过预先组态好的虚拟通信关系（VCR）进行的。
针对不同的应用，设置了三种VCR：
（1）客户／服务器（Client／Server）VCR。
其特点是：
用户触发、一对一、双向、排队式、非周期通信。
通过请求设备（客户）和响应设备（服务器）之间的有确认的请求和应答，提供面向连接的服务正是在该VCR关系中，数据链路层采用了滑动窗IZl协议，对点到点通信进行了有效的差错控制和流量控制，其特点及实现算法将在下面详细讨论。
（2）发布者／预订者（Pusher/subscriber）VCR。
网络触发、一对多、单向、缓冲式、周期通信。
该VCR也提供面向连接的服务，但数据只是由发布设备（发布者）向接收设备（预订者）传送，且不需要确认，而缓冲式意味着新数据将完全覆盖原有数据，
（3）报告分发（ReportDistribution）VCR。
其特点足：
用户触发、一对多，单向、排队式，非周期通信。
该VCR提供面向无连接的服务数据传送不需要确认。
对后两种VCR没有采用滑动窗户协议。
为支持这种VCR，基于ISO／OSl的七层参考模型，FF系统结构定义了三层通信模型：
物理层数据链路层、应用层。
其三层结构如图1所示。
协议原理
数据链路层是通信模型的第二层，目的是正确有序地传输数据帧。
由于物理信道的噪音干扰、接收和发送处理速度不匹配、缓冲区数目有限等多种因素的影响，可能引起被传送数据的损坏或丢失。
解决办法之一是采用停等协I义进行差错控制和流量控制，即发送方发送一帧后必须等到接收方的确认才能发送下一个新帧。
设帧在信道上传输时间为d，帧的长度为f位，数据传输速率为rbit／s，则发送一帧到下一帧的最短等待时间为2（d+f／r），信道的最大利用率为f／2（f+rd）。
对于FF的H1总线，数据传输速率为31.25kbps，帧的长度为8～273字节，如采用停等协议，信道的利用率很低。
为提高信道利用率，引入滑动窗口西议（SlidingWindowProtocols），允许没有收到确认也町以连续发送帧这时。
帧的序号字段应取n位。
以表示0到2n一1范围内的序号。
发送帧时，序号从0开始，然后按模2n加1取值。
这里的窗El，是指一张序号表，表中的序号从0开始，以2n为模连续取值，其中的最大（或最小）号称为窗口的上限（或下限），序号表中允许包含序号的最大数目称为窗口的大小。
在滑动窗gl协议中，发送方维持一个发送窗E1。
该窗口所含序号是它发送给对方且尚未收到确认的帧的序号每发送一个新帧发送窗口上限加1（模2n），当发送窗gl达到最大尺寸时就不允许发送新帧，但町以发重复帧；
当收到对序号为发送窗L1下限的帧的确认时，发送窗口下限加1（模2n）。
接收方也要维持一个接收窗El，用它保存允许接收的帧的序号当到达的帧的序号等于接收窗El下限时，接收窗口滑动一格，即它的下限都加1（模2n）。
图2为窗El大小为8。
窗口尺寸为1的滑动窗口协议示意图。
在滑动窗口协议中，接收方对于出错的帧予以丢弃，而对于该帧后面正确到达的帧采用两种处理方法。
一种是退后n帧的协议：
它是指接收方从出错的帧起丢弃所有帧，均不予确认，对应的接收窗口尺寸为1；
发送方从出错的帧起，将所有未确认的帧重发一遍。
在出错率较高的信道中。
这种方法的信道利用率较低。
另一种是选择性重传的协议：
接收方收到出错的帧后。
对后面到达的正确的帧仍然接收下来。
放在缓冲区巾，同时请求发送方重新传送出错的那一帧，在收到重传的帧后。
就与原先已收到的暂存在缓冲医的其余帧一起按正确的顺序向上层报告金会现场总线数据链路层滑动窗口协议及算法。
几个重要参数和结构
在客户／HE务器VCR中，点到点（peertopeer）的连接与通信是在两个数据链路连接端点（DLCEP）之问进行的。
对于每一个DLCEP，滑动窗口协议相关的有如下几个蘑要参数和结构：
（1）Vc（N）一分配给下一帧的序号识参数初始值为1。
即发送的第一帧序号为1。
上层每产生一个新帧的传输请求，该参数就加1但对某帧进行重发时，该参数不变：
（2）Vc（L）一向上报告的最大帧序号。
该参数初始值为0，每收到一帧并向上报告（重复帧予以丢弃，不向上报告），该参数就加1。
（3）Vc（H）一接收到的最大帧序号，政参数初始值为0，每收到一帧（包括重复帧），该参数就加1
（4）QA（UR）一用户请求队列。
藩队列足一个多优先级先人先出队列，分为三个部分。
第一部分（q1）是已被发送但尚未确认和尚未达到超时的请求；
第二部分（q2）是准备发送的请求；
第三部分（q3）是落在发送窗口之外的准备发送的请求
（5）TEMP一接收方用于判断所接收帧的情况的临时变量。
TEMP=（NR（NDS）+Pc（NPWWWWR）一Vc（H）一1）rood16。
其中，NR（NDS）指收到的帧的NDS值，Pc（NPWWWWR）指接收方接收缓冲区大小在数据帧（DT）的结构中，有如下几个帧参数域与滑动窗仁1协议有关：
（1）NDR一请求对方发送的帧的序号该值以16为模，对应于对方的发送窗口尺寸（0到15
（2）NDS一帧的序号。
该值以32为模。
（3）J一重发请求标志。
J=1。
表示请求重发第NDR帧。
（4）K一确认标忠K=1，表示对NDR以前的所有帧的确认。
基金会现场总线的滑动窗口协议及算法
在FF中，发送窗口最大尺寸为15。
即在未得到确认前最多可发送15帧。
接收缓冲区最大也为15。
即最多可接收15个未确认的帧在FF协议中。
对于点对点的通信。
提供两种数据传送特性：
经典的（CLASSICAL）和乱序的（DISORDERED）一一前一种特性是指只有收到无丢失、见重复、无乱序的帧才向上报告。
后一种则是除重复帧外，接收每一帧。
可能因为帧的丢失而出现序号乱序。
由于数据传送特性的不同，滑动窗口协议中处理出错帧后面正确到达的帧的方法也不同对CLAssICAL，采用退后n帧的协议，即从出错帧起，将所有未确认的帧重发一遍对DISORDERED，采用选择性重传的协议，出错帧后面到达的正确的帧照样接收，只请求发送方重新传送出错的那一帧。
DLCEP采用哪种数据传送特性。
是在建立连接过程中，经过连接双方协商后决定的。
（1）正确的处理过程
对于发送方，当上层产生一个数据请求，就将该请求放人用户请求队列QA（UR）的q2中，等待令牌，同时Vc（N）加1，如有多个请求，重复上述过程。
若发送窗口尺寸（最大为15）已满，则将请求放人q3中。
收到传递令牌（PT）后，将q2中请求组成帧发送出去，该帧的NDS值决定于Vc（N）。
同时启动超时时钟，并移至q1中，等待确认对于接收方，若收到的帧的K参数域=1，表示是确认，在q1中删除所有NDS值小于收到帧的NDR值的请求，取消这些请求对应的时钟，这时发送窗口空出位置。
若此时q3中有请求，则移至q2中j若收到的帧带有数据，则应确认。
在滑动窗口协议中，常用到捎带技术，即将确认附在下一个将发送的数据帧上传送，而不是发送单独的确认，以提高信道利用率。
在FF中，也用到了捎带技术：
若此时恰有数据要传送给对方，则在数据请求组帧时捎带确认，令帧的K参数域=1；
若没有数据要传，则产生不带用户数据的确认请求，放入q2中，等待令牌。
同时Vc（N）加1。
发送确认后，删除确认请求，再移至q1中，也不启动时钟。
（2）重复帧的处理过程
对于接收方，若TEMP<
（vc（L）+Pc（NPWWWWR）一Vc（H）），即NR（NDS）≤Vc（L），说明收到的帧已经确认过，为重复帧，应予以丢弃，不向上报告。
同时在0A（UR）中查找是否已有对该帧的确认，若找不到，则重新对该帧确认一次。
确认过程如上所述。
（3）超时及重发帧的处理过程
对于发送方，某帧发送出去以后，若该帧丢失或接收方对该帧的确认丢失，在规定的时间内未收到对该帧的确认，则进人超时处理。
先在q1中找到需要超时重发的请求，将该淆求放人q2中，等待令牌，lf日Vc（N）不变收到传递令牌（PT）后。
将q2中请求组成帧发送出去，再次窟动超时时钟，并移至q1巾，等待确认：
若第二次超时。
刚为该连接出错，发送断开连接的帧cDC），I百1时向上层报告discon—nect_indication原语，并说明出错原因：
发送方失败一请求超时一对于发出的确认，由于没有肩动时钟，不存在趟lIIJ问题对于接收方。
若超时重发帧为第一次收到。
说明前一次传输的该帧丢失。
进人正常处理过程：
若不足第一次收到，则进人上面的重复帧处理过程
（4）丢失帧的处理过程
对于接收方，若TEMD>
（Pc（NPWWWWR）一1），即NR（NDS）>
Vc（H），说明是未收到过的新帧令N=TEMP一（Pc（NPWWWWR）一1）。
当N=1。
即NR（NDS）=Vc（H）+1，|兑明收到的帧是期颦的帧。
进人正确处理过程。
当N>
1。
即NR（NDS）>
Vc（H）+1。
说明该帧以前有帧丢失，应请求重发。
请求重发和确认一样、可以在数据请求组帧时捎带也可单独组帧令帧的J参数域=1，同时NDR参数域指明请求重发哪一帧，NDR的值等丁Vc（L）+1对于数据传送特性为CLASSICAL的DLCEP。
对乱序的帧及后而的帧予以丢弃，Vc（L）不变。
而对于数据传送特为DISORDERED的DLCEP。
对乱序的帧及后而的帧都予以接收每收帧，Vc（L）加1，在收到请求重发的帧后，和先前收到的帧一起向上报告。
（5）对出错的处理
对于接收方，若TEMP>
（Vc（L）+2XPc（NPWWWWR）一Vc（H）一1）mod16。
即NR（NDS）一Vc（L）>
Pc（NPWWWWR），说明收到的帧序号与上次确认的帧
升级会员 