滑动窗口 订阅
滑动窗口概念不仅存在于数据链路层,也存在于传输层,两者有不同的协议,但基本原理是相近的。其中一个重要区别是,一个是针对于帧的传送,另一个是字节数据的传送。 展开全文
滑动窗口概念不仅存在于数据链路层,也存在于传输层,两者有不同的协议,但基本原理是相近的。其中一个重要区别是,一个是针对于帧的传送,另一个是字节数据的传送。
信息
类    型
流量控制技术
区    别
针对于帧或字节数据的传送
中文名
滑动窗口
外文名
Sliding window
滑动窗口基本信息
滑动窗口(Sliding window)是一种流量控制技术。早期的网络通信中,通信双方不会考虑网络的拥挤情况直接发送数据。由于大家不知道网络拥塞状况,同时发送数据,导致中间节点阻塞掉包,谁也发不了数据,所以就有了滑动窗口机制来解决此问题。参见滑动窗口如何根据网络拥塞发送数据仿真视频。图片是一个滑动窗口的实例: 滑动窗口协议是用来改善吞吐量的一种技术,即容许发送方在接收任何应答之前传送附加的包。接收方告诉发送方在某一时刻能送多少包(称窗口尺寸)。TCP中采用滑动窗口来进行传输控制,滑动窗口的大小意味着接收方还有多大的缓冲区可以用于接收数据。发送方可以通过滑动窗口的大小来确定应该发送多少字节的数据。当滑动窗口为0时,发送方一般不能再发送数据报,但有两种情况除外,一种情况是可以发送紧急数据,例如,允许用户终止在远端机上的运行进程。另一种情况是发送方可以发送一个1字节的数据报来通知接收方重新声明它希望接收的下一字节及发送方的滑动窗口大小。滑动窗口协议的基本原理就是在任意时刻,发送方都维持了一个连续的允许发送的帧的序号,称为发送窗口;同时,接收方也维持了一个连续的允许接收的帧的序号,称为接收窗口。发送窗口和接收窗口的序号的上下界不一定要一样,甚至大小也可以不同。不同的滑动窗口协议窗口大小一般不同。发送方窗口内的序列号代表了那些已经被发送,但是还没有被确认的帧,或者是那些可以被发送的帧。下面举例说明,假设发送窗口尺寸为2,接收窗口尺寸为1:分析:①初始态,发送方没有帧发出,发送窗口前后沿相重合。接收方0号窗口打开,等待接收0号帧;②发送方打开0号窗口,表示已发出0帧但尚确认返回信息。此时接收窗口状态不变;③发送方打开0、1号窗口,表示0、1号帧均在等待确认之列。至此,发送方打开的窗口数已达规定限度,在未收到新的确认返回帧之前,发送方将暂停发送新的数据帧。接收窗口此时状态仍未变;④接收方已收到0号帧,0号窗口关闭,1号窗口打开,表示准备接收1号帧。此时发送窗口状态不变;⑤发送方收到接收方发来的0号帧确认返回信息,关闭0号窗口,表示从重发表中删除0号帧。此时接收窗口状态仍不变;⑥发送方继续发送2号帧,2号窗口打开,表示2号帧也纳入待确认之列。至此,发送方打开的窗口又已达规定限度,在未收到新的确认返回帧之前,发送方将暂停发送新的数据帧,此时接收窗口状态仍不变;⑦接收方已收到1号帧,1号窗口关闭,2号窗口打开,表示准备接收2号帧。此时发送窗口状态不变;⑧发送方收到接收方发来的1号帧收毕的确认信息,关闭1号窗口,表示从重发表中删除1号帧。此时接收窗口状态仍不变。若从滑动窗口的观点来统一看待1比特滑动窗口、后退n及选择重传三种协议,它们的差别仅在于各自窗口尺寸的大小不同而已。1比特滑动窗口协议:发送窗口=1,接收窗口=1;后退n协议:发送窗口>1,接收窗口=1;选择重传协议:发送窗口>1,接收窗口>1。当发送窗口和接收窗口的大小固定为1时,滑动窗口协议退化为停等协议(stop-and-wait)。该协议规定发送方每发送一帧后就要停下来,等待接收方已正确接收的确认(acknowledgement)返回后才能继续发送下一帧。由于接收方需要判断接收到的帧是新发的帧还是重新发送的帧,因此发送方要为每一个帧加一个序号。由于停等协议规定只有一帧完全发送成功后才能发送新的帧,因而只用一比特来编号就够了。其发送方和接收方运行的流程图如图所示。 [1]  由于停等协议要为每一个帧进行确认后才继续发送下一帧,大大降低了信道利用率,因此又提出了后退n协议。后退n协议中,发送方在发完一个数据帧后,不停下来等待应答帧,而是连续发送若干个数据帧,即使在连续发送过程中收到了接收方发来的应答帧,也可以继续发送。且发送方在每发送完一个数据帧时都要设置超时定时器。只要在所设置的超时时间内仍未收到确认帧,就要重发相应的数据帧。如:当发送方发送了N个帧后,若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息,则该帧被判为出错或丢失,此时发送方就不得不重新发送出错帧及其后的N帧。从这里不难看出,后退n协议一方面因连续发送数据帧而提高了效率,但另一方面,在重传时又必须把原来已正确传送过的数据帧进行重传(仅因这些数据帧之前有一个数据帧出了错),这种做法又使传送效率降低。由此可见,若传输信道的传输质量很差因而误码率较大时,连续测协议不一定优于停止等待协议。此协议中的发送窗口的大小为k,接收窗口仍是1。在后退n协议中,接收方若发现错误帧就不再接收后续的帧,即使是正确到达的帧,这显然是一种浪费。另一种效率更高的策略是当接收方发现某帧出错后,其后继续送来的正确的帧虽然不能立即递交给接收方的高层,但接收方仍可收下来,存放在一个缓冲区中,同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后,就可以原已存于缓冲区中的其余帧一并按正确的顺序递交高层。这种方法称为选择重发(SELECTICE REPEAT),其工作过程如图所示。显然,选择重发减少了浪费,但要求接收方有足够大的缓冲区空间。滑动窗口功能:确认、差错控制、流量控制。
收起全文
精华内容
下载资源
问答
  • 滑动窗口

    2020-04-02 12:23:45
    解题思路:首先不断构造一个满足条件的滑动窗口滑动窗口可以是左右指针围起来的数组,也可以是一个中间临时数组),如果滑动窗口不再满足条件,则从滑动窗口左边进行调整,知道满足条件为止,然后继续构造新的滑动...

    滑动窗口

    滑动窗口实际上也是双指针的应用,滑动窗口的右指针不断扩大窗口的范围,当窗口内的对象符合某个条件时,进行统计或者某种操作;然后左指针收缩窗口来打破条件,以便让右指针右移继续扩大窗口

    滑动窗口题目:
    
    3. 无重复字符的最长子串(使用左右指针构造一个滑动窗口,确保滑动窗口内的子串满足要求)
    
    30. 串联所有单词的子串
    
    76. 最小覆盖子串
    
    159. 至多包含两个不同字符的最长子串
    
    209. 长度最小的子数组
    
    239. 滑动窗口最大值
    
    567. 字符串的排列
    
    632. 最小区间
    
    727. 最小窗口子序列
    
    

    3. 无重复字符的最长子串

    解题思路:定义一个数组作为滑动窗口,如果一个字符不在窗口内,则加入;反之,从左边开始删除滑动窗口内的字符来调整窗口;

    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            if not s:
                return 0 
            i = 0
            windowArr = []
            max_len = 0
            while i<len(s):
                if s[i] not in windowArr:
                    windowArr.append(s[i])
                    i+=1
                    max_len = max(max_len, len(windowArr))
                else:
                    while s[i] in windowArr:
                        windowArr.pop(0)           
            return max_len 
    

    76. 最小覆盖子集

    思路:使用一个字典来统计滑动窗口内每个字符以及出现的次数,
    如果窗口内字符以及出现的次数跟目标字符串一致时,则统计窗口内字符的长度,然后将左指针往前移动来缩减窗口,直到窗口内匹配的字符个数少于目标字符串时;
    如果匹配的个数少于目标字符串时,不断右指针往前移动,来扩大窗口的范围;
    当右指针直到s字符串的最后一个字符时,算法结束

    class Solution:
        def minWindow(self, s: str, t: str) -> str:
            if not t or not s:
                return ""
            dic = collections.Counter(t)
            required = len(dic)
            l, r = 0, 0
            formed = 0
            windowCounts = {}
            ans = float("inf"), None, None
            while r < len(s):
                character = s[r]
                windowCounts[character] = windowCounts.get(character, 0) + 1
                if character in dic and windowCounts[character] == dic[character]:
                    formed += 1
                while l <= r and formed == required:
                    character = s[l]
                    if r - l + 1 < ans[0]:
                        ans = (r - l + 1, l, r)
                    windowCounts[character] -= 1
                    if character in dic and windowCounts[character] < dic[character]:
                        formed -= 1
                    l += 1
                r += 1    
            return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]
    

    159:至多包含两个不同字符的最长子串

    思路:
    用左右指针来构建一个滑动窗口,
    当窗口内的不同字符个数<=2时,右指针右移来扩大窗口,并统计窗口的长度;
    当窗口内不同字符的个数>2时,左指针右移来缩小窗口

    class Solution:
        def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
            if len(s)<3:
                return len(s)
            i, j = 0, 0 
            max_len = 0
            while j<len(s):
                if len(set(s[i:j+1]))<=2:                
                    max_len = max(max_len, j-i+1)
                    j+=1
                else:
                    while i<=j and len(set(s[i:j+1]))>2:
                        i+=1
            return max_len
    

    209 长度最小的子数组

    使用左右指针来构建一个滑动窗,
    当窗口内的数字的和<s时,右指针右移来扩大窗口;
    当窗口内的数字之和>=s时,统计窗口的长度,并将左指针右移来缩小窗口

    class Solution:
        def minSubArrayLen(self, s: int, nums: List[int]) -> int:
            if not nums:
                return 0 
            i, j = 0, 0 
            windowSum = 0
            min_len = float('inf')
            while j<len(nums):       
                windowSum += nums[j]
                while i<=j and windowSum>=s:
                    min_len = min(min_len, j-i+1)
                    windowSum -= nums[i]
                    i+=1
                j+=1
    
            return 0 if min_len == float('inf') else min_len
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,169
精华内容 8,467
关键字:

滑动窗口