ckground:white">color:black">color:black">滑动窗口机制

ckground:none repeat scroll 0% 0% white">color:#333333">(1).color:#333333">窗口机制color:#333333">
    color:#333333">滑动窗口协议的基本原理就是在任意时刻࿰c;发送方都维持了一个连续的允许发送的帧的序号࿰c;称为发送窗口；同时࿰c;接收方也维持了一个连续的允许接收的帧的序号࿰c;称为接收窗口。发送窗口和接收窗口的序号的上下界不一定要一样࿰c;甚至大小也可以不同。不同的滑动窗口协议窗口大小一般不同。发送方窗口内的序列号代表了那些已经被发送࿰c;但是还没有被确认的帧࿰c;或者是那些可以被发送的帧。下面举一个例子（假设发送窗口尺寸为color:#333333">2color:#333333">࿰c;接收窗口尺寸为color:#333333">1color:#333333">）：

ckground:none repeat scroll 0% 0% white">

ckground:white">color:#333333">c="https://img-my.csdn.net/uploads/201205/08/1336453751_3979.gif" alt="" />

ckground:white">color:#333333">
   color:#333333">分析：color:#333333">①color:#333333">初始态࿰c;发送方没有帧发出࿰c;发送窗口前后沿相重合。接收方color:#333333">0color:#333333">号窗口打开࿰c;等待接收color:#333333">0color:#333333">号帧；color:#333333">②color:#333333">发送方打开color:#333333">0color:#333333">号窗口࿰c;表示已发出color:#333333">0color:#333333">帧但尚确认返回信息。此时接收窗口状态不变；color:#333333">③color:#333333">发送方打开color:#333333">0color:#333333">、color:#333333">1color:#333333">号窗口࿰c;表示color:#333333">0color:#333333">、color:#333333">1color:#333333">号帧均在等待确认之列。至此࿰c;发送方打开的窗口数已达规定限度࿰c;在未收到新的确认返回帧之前࿰c;发送方将暂停发送新的数据帧。接收窗口此时状态仍未变；color:#333333">④color:#333333">接收方已收到color:#333333">0color:#333333">号帧࿰c;color:#333333">0color:#333333">号窗口关闭࿰c;color:#333333">1color:#333333">号窗口打开࿰c;表示准备接收color:#333333">1color:#333333">号帧。此时发送窗口状态不变；color:#333333">⑤color:#333333">发送方收到接收方发来的color:#333333">0color:#333333">号帧确认返回信息࿰c;关闭color:#333333">0color:#333333">号窗口࿰c;表示从重发表中删除color:#333333">0color:#333333">号帧。此时接收窗口状态仍不变；color:#333333">⑥color:#333333">发送方继续发送color:#333333">2color:#333333">号帧࿰c;color:#333333">2color:#333333">号窗口打开࿰c;表示color:#333333">2color:#333333">号帧也纳入待确认之列。至此࿰c;发送方打开的窗口又已达规定限度࿰c;在未收到新的确认返回帧之前࿰c;发送方将暂停发送新的数据帧࿰c;此时接收窗口状态仍不变；color:#333333">⑦color:#333333">接收方已收到color:#333333">1color:#333333">号帧࿰c;color:#333333">1color:#333333">号窗口关闭࿰c;color:#333333">2color:#333333">号窗口打开࿰c;表示准备接收color:#333333">2color:#333333">号帧。此时发送窗口状态不变；color:#333333">⑧color:#333333">发送方收到接收方发来的color:#333333">1color:#333333">号帧收毕的确认信息࿰c;关闭color:#333333">1color:#333333">号窗口࿰c;表示从重发表中删除color:#333333">1color:#333333">号帧。此时接收窗口状态仍不变。

ckground:white">color:#333333">    color:#333333">若从滑动窗口的观点来统一看待color:#333333">1color:#333333">比特滑动窗口、后退color:#333333">ncolor:#333333">及选择重传三种协议࿰c;它们的差别仅在于各自窗口尺寸的大小不同而已。color:#333333">1color:#333333">比特滑动窗口协议：发送窗口color:#333333">=1color:#333333">࿰c;接收窗口color:#333333">=1color:#333333">；后退color:#333333">ncolor:#333333">协议：发窗口color:#333333">>1color:#333333">࿰c;接收窗口color:#333333">>1color:#333333">；选择重传协议：发送窗口color:#333333">>1,color:#333333">接收窗口color:#333333">>1color:#333333">。

ckground:white">color:#333333">(2).1color:#333333">比特滑动窗口协议

ckground:none repeat scroll 0% 0% white">color:#333333">    color:#333333">当发送窗口和接收窗口的大小固定为color:#333333">1color:#333333">时࿰c;滑动窗口协议退化为停等协议（color:#333333">stopcolor:#333333">－color:#333333">andcolor:#333333">－color:#333333">waitcolor:#333333">）。该协议规定发送方每发送一帧后就要停下来࿰c;等待接收方已正确接收的确认（color:#333333">acknowledgementcolor:#333333">）返回后才能继续发送下一帧。由于接收方需要判断接收到的帧是新发的帧还是重新发送的帧࿰c;因此发送方要为每一个帧加一个序号。由于停等协议规定只有一帧完全发送成功后才能发送新的帧࿰c;因而只用一比特来编号就够了。其发送方和接收方运行的流程图如图所示。

ckground:white">color:#333333">c="https://img-my.csdn.net/uploads/201205/08/1336453846_2524.gif" alt="" />

ckground:white">color:#333333">         

ckground:white">color:#333333">(3).color:#333333">后退color:#333333">ncolor:#333333">协议

ckground:none repeat scroll 0% 0% white">color:#333333">    color:#333333">由于停等协议要为每一个帧进行确认后才继续发送下一帧࿰c;大大降低了信道利用率࿰c;因此又提出了后退color:#333333">ncolor:#333333">协议。后退color:#333333">ncolor:#333333">协议中࿰c;发送方在发完一个数据帧后࿰c;不停下来等待应答帧࿰c;而是连续发送若干个数据帧࿰c;即使在连续发送过程中收到了接收方发来的应答帧࿰c;也可以继续发送。且发送方在每发送完一个数据帧时都要设置超时定时器。只要在所设置的超时时间内仍收到确认帧࿰c;就要重发相应的数据帧。如：当发送方发送了color:#333333">Ncolor:#333333">个帧后࿰c;若发现该color:#333333">Ncolor:#333333">帧的前一个帧在计时器超时后仍未返回其确认信息࿰c;则该帧被判为出错或丢失࿰c;此时发送方就不得不重新发送出错帧及其后的color:#333333">Ncolor:#333333">帧。

ckground:white">color:#333333">c="https://img-my.csdn.net/uploads/201205/08/1336453873_3904.gif" alt="" />

ckground:white">color:#333333">   color:#333333">从这里不难看出࿰c;后退color:#333333">ncolor:#333333">协议一方面因连续发送数据帧而提高了效率࿰c;但另一方面࿰c;在重传时又必须把原来已正确传送过的数据帧进行重传（仅因这些数据帧之前有一个数据帧出了错）࿰c;这种做法又使传送效率降低。由此可见࿰c;若传输信道的传输质量很差因而误码率较大时࿰c;连续测协议不一定优于停止等待协议。此协议中的发送窗口的大小为color:#333333">kcolor:#333333">࿰c;接收窗口仍是color:#333333">1color:#333333">。

ckground:white">color:#333333">(4).color:#333333">选择重传协议

ckground:white">color:#333333">    color:#333333">在后退color:#333333">ncolor:#333333">协议中࿰c;接收方若发现错误帧就不再接收后续的帧࿰c;即使是正确到达的帧࿰c;这显然是一种浪费。另一种效率更高的策略是当接收方发现某帧出错后࿰c;其后继续送来的正确的帧虽然不能立即递交给接收方的高层࿰c;但接收方仍可收下来࿰c;存放在一个缓冲区中࿰c;同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后࿰c;就可以原已存于缓冲区中的其余帧一并按正确的顺序递交高层。这种方法称为选择重发color:#333333">(SELECTICE REPEAT)color:#333333">࿰c;其工作过程如图所示。显然࿰c;选择重发减少了浪费࿰c;但要求接收方有足够大的缓冲区空间。

ckground:white">color:black">滑动窗口协议

ckground:white">color:#333333">仍然考虑链路的延迟与带宽的乘积为color:#333333">8 K Bcolor:#333333">࿰c;帧尺寸为color:#333333">1 K Bcolor:#333333">的情形。让发送方在收到第一帧的color:#333333">A C Kcolor:#333333">的同时准备发送第九帧。允许我们这样做的class="tags" href="/tags/SuanFa.html" title=算法>算法称为滑动窗口（color:#333333"> sliding windowcolor:#333333">）࿰c;时间线如图color:#333333">2 - 2 1color:#333333">所示。

ckground:white">color:#333333">
color:#333333">1. color:#333333">滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法

ckground:white">color:#333333">滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法工作过程如下。首先࿰c;发送方为每color:#333333">1color:#333333">帧赋一个序号（color:#333333">sequence numbercolor:#333333">）࿰c;记作color:red">S e q N u mcolor:#333333">。现在࿰c;让我们忽略color:#333333">S e q N u mcolor:#333333">是由有限大小的头部字段实现的事实࿰c;而假设它能无限增大。发送方维护color:#333333">3color:#333333">个变量：发送窗口大小（color:#333333">send window sizecolor:#333333">）࿰c;记作color:red">S W Scolor:#333333">࿰c;给出发送方能够发color:#333333"> 

ckground:white">color:#333333">送但未确认的帧数的上界；color:red"> L A Rcolor:#333333">表示最近收到的确认帧（color:#333333"> last acknowledgement re c e i v e dcolor:#333333">）的序号；color:red">L F Scolor:#333333">表示最近发送的帧（color:#333333">last frame sentcolor:#333333">）的序号࿰c;发送方还维持如下的不变式：

ckground:white">color:red">LAR-LFR≤RWScolor:#333333"> 

ckground:white">color:#333333"> 

ckground:white">color:#333333">当一个确认到达时࿰c;发送方向右移动color:#333333">L A Rcolor:#333333">࿰c;从而允许发送方发送另一帧。同时࿰c;发送方为所发的每个帧设置一个定时器࿰c;如果定时器在color:#333333">A C Kcolor:#333333">到达之前超时࿰c;则重发此帧。注意：发送方必须存储最多color:#333333">S W Scolor:#333333">个帧࿰c;因为在它们得到确认之前必须准备重发。

ckground:white">color:#333333">接收方维护下面color:#333333">3color:#333333">个变量：接收窗口大小（color:#333333">receive window sizecolor:#333333">）࿰c;记为color:#333333">RW Scolor:#333333">࿰c;给出接收方所能接收的无序帧数目的上界；color:#333333"> L A Fcolor:#333333">表示可接收帧（color:#333333">l a rgestacceptable framecolor:#333333">）的序号；color:#333333">L F Rcolor:#333333">表示最近收到的帧（color:#333333">last frame re ce i v e dcolor:#333333">）的序号。接收方也维持如下不变式：

ckground:white">color:red">LFS-LAR≤SWScolor:#CCFFCC"> 

ckground:white">color:#333333"> 

ckground:white">color:#333333">当一个具有顺序号color:#333333">S e q N u mcolor:#333333">的帧到达时࿰c;接收方采取如下行动：如果color:#333333">S e q N u m≤L F Rcolor:#333333">或color:#333333">S e q N u m > L A Fcolor:#333333">࿰c;那么帧不在接收窗口内࿰c;于是被丢弃；如果color:#333333">L F Rcolor:#333333">࿱c;color:#333333">Se q N u m≤L A Fcolor:#333333">࿰c;那么帧在接收窗口内࿰c;于是被接收。现在接收方需要决定是否发送一个color:#333333">A C Kcolor:#333333">。设color:#333333">S e q N u m To A C Kcolor:#333333">表示未被确认帧的最大序号࿰c;则序号小于或等于color:#333333">S e q N u m To Ac kcolor:#333333">的帧都已收到。即使已经收到更高序号的分组࿰c;接收方仍确认color:#333333">S e q N u m To A c kcolor:#333333">的接收。这种确认被称为是累积的（color:#333333">c u m u l a t i v ecolor:#333333">）。然后它设置color:#333333">L F R = S e q Nu m To A c kcolor:#333333">࿰c;并调整color:#333333">L A F = L F R + RW Scolor:#333333">。例如࿰c;假设color:#333333">L F R= 5color:#333333">（即࿰c;上次接收方发送的color:#333333">A C Kcolor:#333333">是为了确认顺序号color:#333333">5color:#333333">的）࿰c;并且color:#333333">RWS = 4color:#333333">。这意味着color:#333333">L A F = 9color:#333333">。如果帧color:#333333">7color:#333333">和color:#333333">8color:#333333">到达࿰c;则存储它们࿰c;因为它们在接收窗口内。然而并不需要发送color:#333333">A C Kcolor:#333333">࿰c;因为帧color:#333333">6color:#333333">还没有到达。帧color:#333333">7color:#333333">和color:#333333">8color:#333333">被称为是错序到达的。（从技术上讲࿰c;接收方可以在帧color:#333333">7color:#333333">和color:#333333">8color:#333333">到达时重发帧color:#333333">5color:#333333">的color:#333333">A C Kcolor:#333333">。）如果帧color:#333333">6color:#333333">当时到达了（或许它在第一次丢失后又重发从而晚到࿰c;或许它只是被延迟了）࿰c;接收方确认帧color:#333333">8color:#333333">࿰c;color:#333333">L F Rcolor:#333333">置为color:#333333">8color:#333333">࿰c;color:#333333">L A Fcolor:#333333">置为color:#333333">1 2color:#333333">。如果实际上帧color:#333333">6color:#333333">丢失了࿰c;则出现发送方超时࿰c;重发帧color:#333333">6color:#333333">。我们看到࿰c;当发生超时时࿰c;传输数据量减少࿰c;这是因为发送方在帧color:#333333">6color:#333333">确认之前不能向前移动窗口。这意味着分组丢失时࿰c;此方案将不再保证管道满载。注意：分组丢失时间越长࿰c;这个问题越严重。color:#333333">
color:#333333">注意࿰c;在这个例子中࿰c;接收方可以在帧color:#333333">7color:#333333">刚一到达时就为帧color:#333333">6color:#333333">发送一个认帧color:#333333">N A Kcolor:#333333">（color:#333333">negative acknowledgmentcolor:#333333">）。然而࿰c;由于发送方的超时机制足以发现这种情况࿰c;发送color:#333333">N A Kcolor:#333333">反而为发送方增加了复杂性࿰c;因此不必这样做。正如我们已提到的࿰c;当帧color:#333333">7color:#333333">和color:#333333">8color:#333333">到达时为帧color:#333333">5color:#333333">发送一个额外的color:#333333">A C Kcolor:#333333">是合理的；在某些情况下࿰c;发送方可以使用重复的color:#333333">A C Kcolor:#333333">作为一个帧丢失的线索。这两种方法都允许早期的分组丢失检测࿰c;有助于改进性能。color:#333333">
color:#333333">关于这个方案的另一个变种是使用选择确认（color:#333333">selective acknowledgementscolor:#333333">）。即࿰c;接收方能够准确地确认那些已收到的帧࿰c;而不只是确认按顺序收到最高序号的帧。因此࿰c;在上例中࿰c;接收方能够确认帧color:#333333">7color:#333333">、color:#333333">8color:#333333">的接收。如果给发送方更多的信息࿰c;就能使其较容易地保持管道满载࿰c;但增加了实现的复杂性。

ckground:white">color:#333333">发送窗口大小是根据一段给定时间内链路上有多少待确认的帧来选择的；对于一个给定的延迟与带宽的乘积࿰c;color:#333333">S W Scolor:#333333">是容易计算的。另一方面࿰c;接收方可以将color:#333333">RW Scolor:#333333">设置为任何想要的值。通常的两种设置是：color:#333333">RW S= 1color:#333333">࿰c;表示接收方不存储任何错序到达的帧；color:#333333"> RW S=S W Scolor:#333333">࿰c;表示接收方能够缓存发送方传输的任何帧。由于错序到达的帧的数目不可能超过color:#333333">S W Scolor:#333333">个࿰c;所以设置color:#333333">RWS >S W Scolor:#333333">没有意义。

ckground:white">color:#333333">
color:#333333">2. color:#333333">有限顺序号和滑动窗口

ckground:white">color:#333333">现在我们再来讨论class="tags" href="/tags/SuanFa.html" title=算法>算法中做过的一个简化࿰c;即假设序号是可以无限增大的。当然࿰c;实际上是在一个有限的头部字段中说明一个帧的序号。例如࿰c;一个color:#333333">3color:#333333">比特字段意味着有color:#333333">8color:#333333">个可用序号color:#333333">0 ~ 7color:#333333">。因此序号必须可重用࿰c;或者说序号能回绕。这就带来了一个问题：要能够区别同一序号的不同次发送实例࿰c;这意味着可用序号的数目必须大于所允许的待确认帧的数目。例如࿰c;停止等待class="tags" href="/tags/SuanFa.html" title=算法>算法允许一次有color:#333333">1color:#333333">个待确认帧࿰c;并有color:#333333">2color:#333333">个不同的序号。color:#333333">
color:#333333">假设序号空间中的序号数比待确认的帧数大color:#333333">1color:#333333">࿰c;即color:#333333">S W S ≤ M A a xS e q N u m -1 color:#333333">࿰c;其中color:#333333">M a x Seq N u m color:#333333">是可用序号数。这就够了吗？答案取决于color:#333333">RW S color:#333333">。如果color:#333333">RW S = 1color:#333333">࿰c;那么color:#333333">MaxSeqNum≥SWS+1color:#333333">是足够了。如果color:#333333">RW Scolor:#333333">等于color:#333333">S W Scolor:#333333">࿰c;那么有一个只比发送窗口尺寸大color:#333333">1color:#333333">的color:#333333">M a x S e q N u mcolor:#333333">是不够的。为看清这一点࿰c;考虑有color:#333333">8color:#333333">个序号color:#333333">0 ~ 7color:#333333">的情况࿰c;并且color:#333333">S W S = RW S = 7color:#333333">。假设发送方传输帧color:#333333">0 ~ 6color:#333333">࿰c;并且接收方成功接收࿰c;但color:#333333">A C Kcolor:#333333">丢失。接收方现在希望接收帧color:#333333">7color:#333333">࿰c;color:#333333">0 ~ 5color:#333333">࿰c;但发送方超时࿰c;然后发送帧color:#333333">0 ~ 6color:#333333">。不幸的是࿰c;接收方期待的是第二次的帧color:#333333">0 ~ 5color:#333333">࿰c;得到的却是第一次的帧color:#333333">0 ~ 5color:#333333">。这正是我们想避免的情况。color:#333333">
color:#333333">结果是࿰c;当color:#333333">RW S = S W Scolor:#333333">时࿰c;发送窗口的大小不能大于可用序号数的一半࿰c;或更准确地说࿰c;color:#333333">SWS<(Maxseqnum+1)/2color:#333333">直观地࿰c;这说明滑动窗口协议是在序号空间的两半之间变换࿰c;就像停止等待协议的序号是在color:#333333">0color:#333333">和color:#333333">1color:#333333">之间变换一样。唯一的区别是࿰c;它在序号空间的两半之间连续滑动而不是离散的变换。color:#333333">
color:#333333">注意࿰c;这条规则是特别针对color:#333333">RW S = S W Scolor:#333333">的。我们把确定适用于color:#333333">RW Scolor:#333333">和color:#333333">S W Scolor:#333333">的任意值的更一般的规则留做一个练习。还要注意࿰c;窗口的大小和序号空间之间的关系依赖于一个很明显以至于容易被忽略的假设࿰c;即帧在传输中不重新排序。这在直连的点到点链路上不能发生࿰c;因为在传输过程中一个帧不可能赶上另一个帧。然而࿰c;我们将在第color:#333333">5color:#333333">章看到用在一个不同环境中的滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法࿰c;并且需要设计另一条规则。

ckground:white">color:#333333"> 

ckground:white">color:#333333">3. color:#333333">滑动窗口的实现

ckground:white">color:#333333">下面的例程说明我们如何实现滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法的发送和接收的两个方面。该例程取自一个正在使用的协议࿰c;称为滑动窗口协议color:#333333">S W Pcolor:#333333">（color:#333333">Sliding Window Pro t o c o lcolor:#333333">）。为了不涉及协议图中的邻近协议࿰c;我们用color:#333333">H L Pcolor:#333333">（高层协议）表示color:#333333">S W Pcolor:#333333">上层的协议࿰c;用color:#333333">L I N Kcolor:#333333">（链路层协议）表示color:#333333">S W Pcolor:#333333">下层的协议。我们先定义一对class="tags" href="/tags/ShuJuJieGou.html" title=数据结构>数据结构。首先࿰c;帧头部非常简单：它包含一个序号（color:#333333"> S e q N u mcolor:#333333">）和一个确认号（color:#333333"> A c k N u mcolor:#333333">）。它还包含一个标志（color:#333333"> F l a g scolor:#333333">）字段࿰c;表明帧是一个color:#333333">A C Kcolor:#333333">帧还是携带数据的帧。

ckground:white">color:#333333">其次࿰c;滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法的状态有如下结构。对于协议发送方࿰c;该状态包括如上所述的变量color:#333333">L A Rcolor:#333333">和color:#333333">L F Scolor:#333333">࿰c;以及一个存放已发出但尚未确认的帧的队列（color:#333333"> s e n d Qcolor:#333333">）。发送方状态还包含一个计数信号量（color:#333333"> counting class="tags" href="/tags/SEMAPHORE.html" title=semaphore>semaphorecolor:#333333">）࿰c;称为color:#333333">s e n d Wi n d o w N o t F u l lcolor:#333333">。下面我们将会看到如何使用它࿰c;但一般来说࿰c;信号量是一个支持color:#333333">s e m Wa i tcolor:#333333">和color:#333333">s e m S i g n a lcolor:#333333">操作的同步原语。每次调用color:#333333">S e m S i g n alcolor:#333333">࿰c;信号量加color:#333333">1color:#333333">࿰c;每次调用color:#333333">S e m Wa i tcolor:#333333">࿰c;信号量减color:#333333">1color:#333333">。如果信号量减小࿰c;导致它的值小于color:#333333">0color:#333333">࿰c;那么调用进程阻塞（挂起）。一旦执行了足够的color:#333333">s e m S i g n a lcolor:#333333">操作而使信号量的值增大到大于color:#333333">0color:#333333">࿰c;在调用color:#333333">s e m Wa i tcolor:#333333">的过程中阻塞的进程就允许被恢复。color:#333333">
color:#333333">对于协议的接收方࿰c;如前所述࿰c;该状态包含变量color:#333333">L F R color:#333333">࿰c;加上一个存放已收到的错序帧的队列（color:#333333">r e c v Qcolor:#333333">）。最后࿰c;虽然未显示࿰c;发送方和接收方的滑动窗口的大小分别由常量color:#333333">S W Scolor:#333333">和color:#333333">RW Scolor:#333333">表示。

ckground:white">color:#333333">S W Pcolor:#333333">的发送方是由color:#333333">s e n d S W Pcolor:#333333">过程实现的。这个例程很简单。首先࿰c;color:#333333"> s e m Wa i tcolor:#333333">使这个进程在一个信号量上阻塞࿰c;直到它可以发另一帧。一旦允许继续࿰c;color:#333333"> s e n d S W Pcolor:#333333">设置帧头部中的顺序号࿰c;将此帧的拷贝存储在发送队列（color:#333333"> s e n d Qcolor:#333333">）中࿰c;调度一个超时事件以便处理帧未被确认的情况࿰c;并将帧发给低层协议。

ckground:white">color:#333333">值得注意的一个细节是刚好在调用color:#333333">m s g A d d H drcolor:#333333">之前调用color:#333333">s t o r e _ s w p _ h d rcolor:#333333">。该例程将存有color:#333333">S W Pcolor:#333333">头部的color:#333333">Ccolor:#333333">语言结构（color:#333333"> s t a t e -> h d rcolor:#333333">）转化为能够安全放在消息前面的字节串（color:#333333"> h b u fcolor:#333333">）。该例程（未给出）必须将头部中的每一个整数字段转化为网络字节顺序࿰c;并且去掉编译程序加入color:#333333">Ccolor:#333333">语言结构中的任意填充。color:#333333">7 . 1color:#333333">节将详细讨论字节顺序的问题࿰c;但现在࿰c;假设该例程将多字整数中最高有效位放在最高地址字节就足够了。color:#333333">
color:#333333">这个例程的另一个复杂性是使用color:#333333">s e m Wa i t color:#333333">和color:#333333">s e n dW i n d ow N o t F u l l color:#333333">信号量。color:#333333">S e n dWi n d o w N o t F u l lcolor:#333333">被初始化为发送方滑动窗口的大小color:#333333">S W Scolor:#333333">（未给出这一初始化）。发送方每传输一帧࿰c;color:#333333"> s e m Wa i tcolor:#333333">操作将这个数减color:#333333">1color:#333333">࿰c;如果减小到color:#333333">0color:#333333">࿰c;则阻塞发送方进程。每收到一个color:#333333">A C Kcolor:#333333">࿰c;在color:#333333">d e l i v e r SW Pcolor:#333333">中调用color:#333333">s e m S i g n a lcolor:#333333">操作（见下面）将此数加color:#333333">1color:#333333">࿰c;从而激活正在等待的发送方进程。

ckground:white">color:#333333">在继续介绍color:#333333">S W Pcolor:#333333">的接收方之前࿰c;需要调整一个看上去不一致的地方。一方面࿰c;我们说过࿰c;高层协议通过调用color:#333333">s e n dcolor:#333333">操作来请求低层协议的服务࿰c;所以我们就希望通过color:#333333">S W Pcolor:#333333">发送消息的协议能够调用color:#333333">s e n dcolor:#333333">（color:#333333">S W P, p a c k e tcolor:#333333">）。另一方面࿰c;用来实现color:#333333">S W Pcolor:#333333">的发送操作的过程叫做color:#333333">s e n d S W Pcolor:#333333">࿰c;并且它的第一个参数是一个状态变量（color:#333333"> S w p S t a t ecolor:#333333">）。结果怎样呢？答案是࿰c;操作系统提供了粘结代码将对color:#333333">s e n dcolor:#333333">的一般调用转化为对color:#333333">s e n d S W Pcolor:#333333">的特定协议调用的粘结代码。这个粘结代码将color:#333333">s e n dcolor:#333333">的第一个参数（协议变量color:#333333">S W Pcolor:#333333">）映射为一个指向color:#333333">s e n d S W Pcolor:#333333">的函数指针和一个指向color:#333333">S W Pcolor:#333333">工作时所需的协议状态的指针。我们之所以通过一般函数调用使高层协议间接调用特定协议函数࿰c;是因为我们想限制高层协议中对低层协议编码的信息量。这使得将来能够比较容易地改变协议图的配置。现在来看color:#333333">d e l i v e rcolor:#333333">操作的color:#333333">S W Pcolor:#333333">的特定协议实现࿰c;它在过程color:#333333">d e l i v e r SW Pcolor:#333333">中实现。这个例程实际上处理两种不同类型的输入消息：本结点已发出帧的color:#333333">A C Kcolor:#333333">和到达这个结点的数据帧。在某种意义上࿰c;这个例程的color:#333333">ACKcolor:#333333">部分是与color:#333333">send SWPcolor:#333333">中所给class="tags" href="/tags/SuanFa.html" title=算法>算法的发送方相对应的。通过检验头部的color:#333333">F l a g scolor:#333333">字段可以确定输入的消息是color:#333333">ACKcolor:#333333">还是一个数据帧。注意࿰c;这种特殊的实现不支持数据帧中捎带color:#333333">A C Kcolor:#333333">。当输入帧是一个color:#333333">ACKcolor:#333333">时࿰c;color:#333333">delive rSWPcolor:#333333">仅仅在发送队列（color:#333333">send Qcolor:#333333">）中找到与此color:#333333">ACKcolor:#333333">相应的位置（color:#333333">slotcolor:#333333">）࿰c;取消超时事件࿰c;并且释放保存在那一位置的帧。由于color:#333333">A C Kcolor:#333333">可能是累积的࿰c;所以这项工作实际上是在一个循环中进行的。对于这种情况值得注意的另一个问题是子例程color:#333333">swp In Wind o wcolor:#333333">的调用。这个子例程在下面给出࿰c;它确保被确认帧的序号是在发送方当前希望收到的color:#333333">A C Kcolor:#333333">的范围之内。color:#333333">
color:#333333">当输入帧包含数据时࿰c;color:#333333"> d e l i v e r S W Pcolor:#333333">首先调用color:#333333">m s g S t r i pH d rcolor:#333333">和color:#333333">l o a d _ s w p _ h d rcolor:#333333">以便从帧中提取头部。例程color:#333333">l o a d _ s w p_ h d rcolor:#333333">对应着前面讨论的color:#333333">s t o r e _ s w p _ h d rcolor:#333333">࿰c;它将一个字节串转化为容纳color:#333333">S W Pcolor:#333333">头部的color:#333333">Ccolor:#333333">语言class="tags" href="/tags/ShuJuJieGou.html" title=数据结构>数据结构。然后color:#333333">d e l i v e r SW Pcolor:#333333">调用color:#333333">s w p I n Wi n d o wcolor:#333333">以确保帧序号在期望的序号范围内。如果是这样࿰c;例程在已收到的连续的帧的集合上循环࿰c;并通过调用color:#333333">d e l i v e r HL Pcolor:#333333">例程将它们传给上层协议。它也要向发送方发送累积的color:#333333">A C Kcolor:#333333">࿰c;但却是通过在接收队列上循环来实现的（它没有使用本节前面给出的color:#333333">s e q N u m To Ac kcolor:#333333">变量）。

ckground:white">color:#333333"> 

ckground:white">color:#333333">最后࿰c;color:#333333">s w p I n Windowcolor:#333333">是一个简单的子例程࿰c;它检查一个给定的序号是否落在某个最大和最小顺序号之间。

ckground:white">color:#333333"> 

ckground:white">color:#333333">4. color:#333333">帧顺序和流量控制

ckground:white">color:#333333">滑动窗口协议可能是计算机网络中最著名的class="tags" href="/tags/SuanFa.html" title=算法>算法。然而࿰c;关于该class="tags" href="/tags/SuanFa.html" title=算法>算法易产生混淆的是࿰c;它可以有三个不同的功能࿰c;第一个功能是本节的重点࿰c;即在不可靠链路上可靠地传输帧。（一般来说࿰c;该class="tags" href="/tags/SuanFa.html" title=算法>算法被用于在一个不可靠的网络上可靠地传输消息。）这是该class="tags" href="/tags/SuanFa.html" title=算法>算法的核心功能。

ckground:white">color:#333333">滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法的第二个功能是用于保持帧的传输顺序。这在接收方比较容易实现࿰c;因为每个帧有一个序号࿰c;接收方要保证已经向上层协议传递了所有序号比当前帧小的帧࿰c;才向上传送该当前帧。即࿰c;接收方缓存了（即没有传送）错序的帧。本节描述的滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法确实保持了帧的顺序࿰c;尽管我们可以想象一个变异࿰c;即接收方没有等待更早传送的帧都到达就将帧传给下一个协议。我们可以提出的一个问题是：我们是否确实需要滑动窗口协议来保持帧的顺序࿰c;或者࿰c;这样的功能在链路层是否是不必要的。不幸的是࿰c;我们还没有看到足够多的网络体系结构来回答这个问题我们首先需要理解的是࿰c;点到点链路序列如何由交换机连接而形成一条端到端的路径。color:#333333">
color:#333333">滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法的第三个功能是࿰c;它有时支持流量控制（color:#333333">f l o w c o n t ro lcolor:#333333">）࿰c;它是一种接收方能够控制发送方使其降低速度的反馈机制。这种机制用于抑制发送方发送速度过快࿰c;即抑制传输比接收方所能处理的更多的数据。这通常通过扩展滑动窗口协议完成࿰c;使接收方不仅确认收到的帧࿰c;而且通知发送方它还可接收多少帧。可接收的帧数对应着接收方空闲的缓冲区数。在按序传递的情况下࿰c;在将流量控制并入滑动窗口协议之前࿰c;我们应该确信流量控制在链路层是必要的。color:#333333">
color:#333333">尚未讨论的一个重要概念是系统设计原理࿰c;我们称其为相关性分离（color:#333333">separation of concernscolor:#333333">）。即࿰c;你必须小心区别有时交织在一种机制中的不同功能࿰c;并且你必须确定每一个功能是必要的࿰c;而且是被最有效的方式支持的。在这种特定的情况下࿰c;可靠传输、按序传输和流量控制有时组合在一个滑动窗口协议里࿰c;我们应该问问自己࿰c;在链路层这样做是否正确。带着这样的疑问࿰c;我们将在第color:#333333">3color:#333333">章（说明color:#333333">X. 2 5color:#333333">网如何用它实现跳到跳的流量控制）和第color:#333333">5color:#333333">章（描述color:#333333">T C Pcolor:#333333">如何用它实现可靠的字节流信道）重新考虑滑动窗口class="tags" href="/tags/SuanFa.html" title=算法>算法。