滑动窗口 订阅
滑动窗口概念不仅存在于数据链路层,也存在于传输层,两者有不同的协议,但基本原理是相近的。其中一个重要区别是,一个是针对于帧的传送,另一个是字节数据的传送。 展开全文
滑动窗口概念不仅存在于数据链路层,也存在于传输层,两者有不同的协议,但基本原理是相近的。其中一个重要区别是,一个是针对于帧的传送,另一个是字节数据的传送。
信息
类    型
流量控制技术
区    别
针对于帧或字节数据的传送
中文名
滑动窗口
外文名
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),其工作过程如图所示。显然,选择重发减少了浪费,但要求接收方有足够大的缓冲区空间。滑动窗口功能:确认、差错控制、流量控制。
收起全文
精华内容
参与话题
问答
  • 滑动窗口算法学习

    千次阅读 2019-05-14 12:05:36
    最近做了几道有关滑动窗口的算法,在此总结一下。 滑动窗口 就像描述的那样,可以理解成是一个会滑动的窗口,每次记录下窗口的状态,再找出符合条件的适合的窗口 可以使用滑动窗口来减少时间复杂度 经典滑动窗口...

    最近做了几道有关滑动窗口的算法,在此总结一下。

    滑动窗口

    • 就像描述的那样,可以理解成是一个会滑动的窗口,每次记录下窗口的状态,再找出符合条件的适合的窗口
    • 可以使用滑动窗口来减少时间复杂度

    经典滑动窗口题目

    给一组大小为n的整数数组,计算长度为k的子数组的最大值
    比如:数组{1,2,3,4,5,7,6,1,8},k=2,那么最终结果应该是7+6=13最大。
    最简单的是使用两层遍历,通过所有情况找出最大的一个子数组,时间复杂度O(N^2)
    使用滑动窗口,从[0,k-1]的一个窗口,记录其总和,然后窗口向右移动到[1,k],再到[2,k+1],直到数组的最尾端,找出里面总和最大的一个窗口,这样的解法就是滑动窗口算法。

    //Java代码:
    public class SlidingWindow {
        public static int maxnum(int[] array,int k){
            if(array.length<k){//如果k比数组长度还大,返回-1
                return -1;
            }
            int left=0;
            int sum=0;
            for(int i=0;i<k;i++){
                sum+=array[i];
            }
            int tempsum=sum;//tempsum记录每个窗口的总和
            while (left+k<array.length){
                tempsum=tempsum-array[left]+array[left+k];
                left++;
                sum=Math.max(sum,tempsum);//sum取原sum和tempsum的较大值
            }
            return sum;
        }
        public static void main(String[] args) {
            int[] arr={1, 4, 2, 10, 2, 3, 1, 0, 20};
            int k=3;
            System.out.println(maxnum(arr,k));
        }
    }
    

    字符串中的使用

    • 问题描述:
      给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
      注意子串要与 words 中的单词完全匹配,中间不能有其他字符
    public class Matching {
    
        public static List<Integer> findSubstring(String s,String[] words){
            List<Integer> res=new ArrayList<>();
            if(s==null||s.length()==0||words==null||words.length==0)
                return res;
            HashMap<String,Integer> map=new HashMap<>();//储存words字符数组,value值为出现的次数
            int word=words[0].length();//每个子串的长度
            int number=words.length;//子串的个数
            for(String w:words){
                map.put(w,map.getOrDefault(w,0)+1);//map中如果没有当前子串,则放入;如果有数目+1
            }
            for(int i=0;i<word;i++){
                int left=i,right=i,count=0;
                HashMap<String,Integer> temp=new HashMap<>();
                while (right+word<=s.length()){
                    String match=s.substring(right,right+word);//滑动窗口
                    right+=word;
                    if(!map.containsKey(match)){
                        count=0;
                        left=right;
                        temp.clear();
                    }
                    else {
                        temp.put(match,temp.getOrDefault(match,0)+1);
                        count++;
                        while (temp.getOrDefault(match,0)>map.getOrDefault(match,0)){//如果匹配的个数多了,向右滑动word个字符
                            String match1=s.substring(left,left+word);
                            count--;
                            temp.put(match1,temp.getOrDefault(match1,0)-1);
                            left+=word;
                        }
                        if(count==number) res.add(left);
                    }
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            String s = "barfoothefoobarman";
            String[] words = {"foo","bar"};
            System.out.println(findSubstring(s,words));
        }
    
    }
    
    • 问题描述:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
      输入: “abcabcbb”
      输出: 3
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            //使用HashSet作为滑动窗口,找出无重复字符的最长子串。
            Set<Character> set=new HashSet<>();
            int ans=0,i=0,j=0;//i为滑动窗口的左边,j为右边
            while(i<s.length()&&j<s.length()){
                if(!set.contains(s.charAt(j))){//如果没有重复
                    set.add(s.charAt(j++));
                    ans=Math.max(ans,j-i);
                }
                else{//如果出现重复
                    set.remove(s.charAt(i++));
                }
            }
            return ans;
        }
    }
    

    用滑动窗口用来解决求字符串,数组等连续的子串或子数组的问题比较简单。

    展开全文
  • 滑动窗口法详解

    万次阅读 多人点赞 2018-04-23 09:11:52
    算法目的 前言 一个经典的问题 代码如下 总结 参考资料 算法目的 该算法展示了如何将嵌套for循环在少数问题中转换为单个for循环,从而减少了时间的复杂性。 ... k...

    算法目的

    该算法展示了如何将嵌套for循环在少数问题中转换为单个for循环,从而减少了时间的复杂性。

    前言

    一个经典的问题

    给一组大小为n的整数数组,计算长度为k的子数组的最大值
    我们希望的结果如下

    Input  : arr[] = {100, 200, 300, 400}
             k = 2
    Output : 700
    
    Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
             k = 4 
    Output : 39
    We get maximum sum by adding subarray {4, 2, 10, 23}
    of size 4.
    
    Input  : arr[] = {2, 3}
             k = 3
    Output : Invalid
    There is no subarray of size 3 as size of whole
    array is 2.
    

    该技术可以通过总线上的窗格得到最好的理解,考虑长度为n的窗口和长度为k的窗格。考虑一下,最初窗格处于极端的左边,即从左边开始的0个单位。现在,将窗口与大小为n和平面的数组arr []以k大小的元素的current_sum相关联。现在,如果我们在窗户上施加力量,使其向前移动一个单位距离。该窗格将覆盖下一个k个连续元素。

    考虑数组arr [] = { 5,2,-1,0,3 },k = 3和n = 5的值

    应用滑动窗口技术:

    1. 我们使用线性循环计算n个项中前k个元素的总和,并将总和存储在变量window_sum中。
    2. 然后,我们将在阵列上线性滑动直至达到最终并同时追踪最大和。
    3. 要获得k个元素块的当前总和,只需从前一个块中减去第一个元素并添加当前块的最后一个元素即可。 下面的表示将清楚说明窗口如何在阵列上滑动。

    这是我们计算从索引0开始的初始窗口总和的初始阶段。在这个阶段,窗口和为6.现在,我们将maximum_sum设置为current_window,即6。
    这里写图片描述
    现在,我们用单位索引来滑动我们的窗口。因此,现在它从窗口中丢弃5并将0添加到窗口。因此,我们将得到新的窗口总和,减去5,然后加上0。所以,我们的窗口和现在变成1.现在,我们将比较这个窗口和与maximum_sum。因为它更小,我们不会改变maximum_sum。
    这里写图片描述
    同样,现在我们再次用一个单位索引来滑动我们的窗口,并获得新的窗口总和为2.我们再一次检查这个当前窗口总和是否大于maximum_sum,直到现在。有一次,它再小一些,所以我们不改变maximum_sum。

    因此,对于上面的数组,我们的maximum_sum是6。
    这里写图片描述

    代码如下

    
    #include <iostream>
    
    using namespace std;
    
    int maxSum(int arr[], int n, int k)
    {
        if (n < k)
        {
            cout << "Invaild";
            return -1;
        }
        int max_sum = 0;
        for (int i=0; i<k; i++)
        {
            max_sum += arr[i];
        }
        int windows_sum = max_sum;
        for (int i=k; i<n; i++)
        {
            windows_sum += arr[i] - arr[i - k];
            max_sum = max(max_sum, windows_sum);
        }
        return max_sum;
    }
    
    
    int main()
    {
        int arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20};
        int k = 4;
        int n = sizeof(arr) / sizeof(arr[0]);
        cout << maxSum(arr, n, k);
        return 0;
    }
    

    总结

    现在,很明显时间复杂性是线性的,因为我们可以看到只有一个循环运行在我们的代码中。因此,我们的时间复杂度是O(n)。
    我们可以使用这种技术来查找最大/最小k-子阵列,XOR,乘积,总和等

    如果你觉得还不错可以右侧点个赞幺,谢谢

    #参考资料
    geekforgeeks 滑动窗口法详解
    https://www.geeksforgeeks.org/window-sliding-technique/

    geekforgeeks 经典类型题
    https://www.geeksforgeeks.org/tag/sliding-window/

    leetcode的经典模板

    展开全文
  • 解析TCP之滑动窗口(动画演示)

    万次阅读 多人点赞 2018-07-14 20:07:13
    滑动窗口实现了TCP流控制。首先明确滑动窗口的范畴:TCP是双工的协议,会话的双方都可以同时接收和发送数据。TCP会话的双方都各自维护一个发送窗口和一个接收窗口。各自的接收窗口大小取决于应用、系统、硬件的限制...

    概述

    滑动窗口实现了TCP流控制。首先明确滑动窗口的范畴:TCP是双工的协议,会话的双方都可以同时接收和发送数据。TCP会话的双方都各自维护一个发送窗口和一个接收窗口。各自的接收窗口大小取决于应用、系统、硬件的限制(TCP传输速率不能大于应用的数据处理速率)。各自的发送窗口则要求取决于对端通告的接收窗口,要求相同。

    滑动窗口解决的是流量控制的的问题,就是如果接收端和发送端对数据包的处理速度不同,如何让双方达成一致。接收端的缓存传输数据给应用层,但这个过程不一定是即时的,如果发送速度太快,会出现接收端数据overflow,流量控制解决的是这个问题。

    窗口的概念

    发送方的发送缓存内的数据都可以被分为4类:
    1. 已发送,已收到ACK
    2. 已发送,未收到ACK
    3. 未发送,但允许发送
    4. 未发送,但不允许发送

    其中类型2和3都属于发送窗口。

    接收方的缓存数据分为3类:
    1. 已接收
    2. 未接收但准备接收
    3. 未接收而且不准备接收

    其中类型2属于接收窗口。

    窗口大小代表了设备一次能从对端处理多少数据,之后再传给应用层。缓存传给应用层的数据不能是乱序的,窗口机制保证了这一点。现实中,应用层可能无法立刻从缓存中读取数据。

    滑动机制

    1. 发送窗口只有收到发送窗口内字节的ACK确认,才会移动发送窗口的左边界。

    2. 接收窗口只有在前面所有的段都确认的情况下才会移动左边界。当在前面还有字节未接收但收到后面字节的情况下,窗口不会移动,并不对后续字节确认。以此确保对端会对这些数据重传。

    3. 遵循快速重传、累计确认、选择确认等规则。

    4. 发送方发的window size = 8192;就是接收端最多发送8192字节,这个8192一般就是发送方接收缓存的大小。

    模拟动画

    模拟特点

    找到了一个模拟TCP窗口发送的动画的地址,稍微有缺陷:1. 丢包率如果设得太高,有时无论重发多少次都不能恢复正常 2. 窗口最大可为10,其实应该为9

    明确发送端和接收端,发送A~S数据包,我们不会从头到尾分析,因为过程比较长。
    1. 简化了窗口大小,双方窗口大小都一直是4
    2. 设置一定的丢包率,否则没什么值得分析的,包括sender发送的数据包和receiver回复的ACK包。
    3. 简化重传机制,出现丢包则直接重传,不等3个冗余ACK和超时。
    4. 既不是选择重传也不是退回N步,重传的包是随机的


    分析滑动窗口机制

    1. 首先发送端发送A,B,C,D四个包,但是A,B丢失,只有C,D到达接收端。

    2. 接收端没有收到A,所以不回复ACK包。发送端重传A,B,C,D四个包,这次全都到达了。

    3. 接收端先获得A,发ACK包A,但是中途丢失;获得B后,根据累计确认的原则,发D的ACK包,然后窗口滑动。再次获得C,D后,连续回复2个D的ACK包,其中C对应的ACK包丢失。

    4. 发送端连收2个D的ACK包,说明4个包对方都已收到,窗口滑动,发E,F,G,H包,其中G包丢失。现在整个序列的状态:ABCD是已发送已确认,EFGH是已发送未确认,I~S是不能发送。

    5. 接收端先收到E,发ACK包;收到F后发F的ACK包;未收到G,还是发F的ACK包;收到H,还是发F的ACK包。不幸的是,三个ACK包全都丢失。

    6. 发送端收到E的ACK包,窗口向右滑动一位;然后再发送F,G,H,I,其中F丢失。

    7. 接收端获得I,因为没有G,只好回复F的ACK包。相继收到G,H包。

    8. 接收端根据累计确认,连发两个I包,其中H对应的丢失。窗口向右滑动。

    9. 发送端接收I的ACK包后,向右滑动四位。发送J,K,L,M四个包,后面不再分析。

    从上面的过程中,我们可以得到以下结论:
    1. TCP连接是通过数据包和ACK实现的,我们作为第三者可以看到双方发包的过程,但接受者在收到之前不知道发送方发的是什么,同样的,发送方在收到ACK前也不知道对方是否成功接收。

    1. 发送方没有收到接收方发回的ACK,就不能向右滑动。假设发送方向接收方发了ABCD就滑动,只要对方没收到A,就不能滑动,那么就会出现二者不同步的局面。

    2. 滑动窗口提高了信道利用率,TCP是发送报文段为单位的,假如每发一个报文就要等ACK,那么对于大数据包,等待时间就太长了。只要发送的报文在滑动窗口里面,不用等每个ACK回来就可以向右滑动。本例中,开始接收端空着AB,只有CD,此时不能滑动;之后接收到EF和H,直接向右滑动2位,不必等G到位。

    3. 窗口大小不能大于序号空间大小的一半。目的是为了不让两个窗口出现交迭,比如总大小为7,窗口大小都为4,接收窗口应当滑动4,但只剩3个序号,导致两个窗口交迭。

    4. 有一种情况没出现:发送方发ABCD,接收方都收到然后向右滑动,但回复的ACK包全丢了。发送方未收到任何ACK, timeout后会重发ABCD,此时的接收方按累计确认的原则,收到ABCD后只会重发D的ACK,发送方收到后向右滑动。

    对比滑动窗口和拥塞窗口

    滑动窗口是控制接收以及同步数据范围的,通知发送端目前接收的数据范围,用于流量控制,接收端使用。拥塞窗口是控制发送速率的,避免发的过多,发送端使用。因为tcp是全双工,所以两边都有滑动窗口。
    两个窗口的维护是独立的,滑动窗口主要由接收方反馈缓存情况来维护,拥塞窗口主要由发送方的拥塞控制算法检测出的网络拥塞程度来决定的。

    拥塞窗口控制sender向connection传输数据的速率,使这个速率为网络拥堵状况的函数。

    参考:TCP流量控制中的滑动窗口大小
    TCP那些事(上)

    展开全文
  • 计算机网络(7)——滑动窗口

    千次阅读 2019-02-25 10:34:11
    一、滑动窗口流量控制基本原理 发送窗口: 在任意时刻,发送发都维持一组连续的允许发送的帧的序号,称为发送窗口。 接收窗口: 发送窗口用来对发送方进行流量控制,而发送窗口的大小 W 代表在还...

    一、滑动窗口流量控制基本原理

    • 发送窗口:

      • 在任意时刻,发送发都维持一组连续的允许发送的帧的序号,称为发送窗口。
    • 接收窗口:

      • 发送窗口用来对发送方进行流量控制,而发送窗口的大小 W 代表在还没有收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。

    在接收端设置接收窗口是为了控制可以接受哪些数据帧而不可以接收哪些帧。在接收方只有当收到的数据帧的序号落入接收窗口内才允许将该数据帧手下。若接收到的数据帧落在了接收窗口之外,则一律将其丢弃。

    在这里插入图片描述

    在发送端,每收到一个却认真,发送窗口就向前滑动一个帧的位置,当发送窗口内没有可以发送的帧(即窗口内全部是已发送,但未接收到确认的帧),发送方就会停止发送,直到收到接收方发送的确认帧使窗口移动,窗口内有可以发送的帧,之后才开始继续发送。

    二、滑动窗口的分类

    滑动窗口分为三类:停止等待、后退N帧、选择重传。他们之间主要的区别就是:发送窗口和接收窗口大小的区别。

    • 停止等待协议:

      • 发送窗口大小 = 1, 接收窗口大小= 1
    • 后退N帧协议

      • 发送窗口大小 > 1,接收窗口大小 = 1
    • 选择重传协议

      • 发送窗口大小 > 1, 接收窗口大小 > 1

    三、停止等待协议

    规则:源站发送单个帧后就必须等待确认,在目的站的回答到达源站之前,源站不能发送其他的数据帧

    在停止等待协议中,除了数据丢失的问题,还有可能存在以下两种差错:

    • 到达目的站的数据帧可能遭到破坏。

      • 解决办法:源站在发送一个帧后,就为这个帧装一个计时器,在一个帧发送之后,源站等待确认,如果在计时器时间到达时未收到确认,则再次发送相同的帧。
    • 数据帧正确,但是却认真没有收到

      • 此时接收方已经收到了正确的数据帧,但是发送方收不到却认真,因此发送方会重传已经被接收的数据帧,接收方收到同样的数据帧就会丢弃该帧,并重传一个该帧对应的却认真。

    【总结】

    • 【1】接收方收到相同的数据:发送方超时重传
    • 【2】发送方收到相同的确认帧:发送方发送了重复的数据
    • 【3】接收窗口大小 = 1, 发送窗口大小 = 1

    四、后退N帧

    发送方不需要在收到上一帧的ACK后才能开始放松下下一帧,而是可以连续发送帧。当接收方检测出失序的信息帧之后,要求发送方重发最后一个正确信息帧之后的所有未被确认的帧;或者当发送方发送了N个帧之后,若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息,则该帧被判定为出错或者丢失,此时发送方就不得不重传该出错帧及之后的N个帧。注意:接收方只允许按照顺序接受帧。

    为了减少开销,后退N帧协议还规定接收端不一定每收到一个正确的数据帧就必须立即发回一个却认真,而是可以在连续收到好几个正确的数据帧后,才对最后一个数据帧发送确认信息,或者可以在当自己有数据要发送的时候才将对以前正确收到的帧加以捎带确认。

    在这里插入图片描述

    五、选择重传

    只重传出现差错的数据帧或者是计时器超时的数据帧。每一个发送缓冲区对应一个计时器,当计时器超时的时候,缓冲区的帧就会重传。另外,该协议使用了比上述其他协议更有效的差错处理策略,即一旦接收方怀疑帧出错,就会发送一个否定帧NAK给发送方,要求发送方对NAK中制定的帧进行重传。

    展开全文
  • 滑动窗口机制

    万次阅读 2006-03-23 22:07:00
    窗口机制 滑动窗口协议的基本原理就是在任意时刻,发送方都维持了一个连续的允许发送的帧的序号,称为发送窗口;同时,接收方也维持了一个连续的允许接收的帧的序号,称为接收窗口。发送窗口和接收窗口的序号的上下...
  • 滑动窗口

    2020-11-20 16:16:45
    分析:这是力扣上关于滑动窗口非常经典的一题,那么这题的思路其实也是简单,所谓滑动窗口,你可以想象成是一个窗户,A这一半在另一半B上滑动,求满足情况的位置,很显然我们需要俩个容器,windows表示当前滑动窗口...
  • TCP-IP详解:滑动窗口(Sliding Window)

    万次阅读 多人点赞 2016-09-07 22:32:23
    从传输数据来讲,TCP/UDP以及其他协议都可以完成数据的传输,从一端传输到另外一端,TCP比较出众的一点就是提供一个可靠的,流控的数据传输,所以实现起来要比其他协议复杂的多,先来看下这两个修饰词的意义: ...
  • 滑动窗口的原理

    万次阅读 2010-03-25 15:03:00
    仍然考虑链路的延迟与带宽的乘积为8 K B,帧尺寸为1 K B的情形。让发送方在收到第一帧的A C K的同时... 滑动窗口算法滑动窗口算法工作过程如下。首先,发送方为每1帧赋一个序号(sequence number),记作S e q N u m
  • 滑动窗口算法

    千次阅读 2019-07-13 22:02:14
    什么是滑动窗口算法 我们学习过计算机网络都知道为了避免拥塞发生,在网络传输时有滑动窗口协议控制传输时流量。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认...
  • 滑动窗口算法(Sliding Window Algorithm) Sliding window algorithm is used to perform required operation on specific window size of given large buffer or array. This technique shows how a nested for...
  • 最后抽象出一个简单的滑动窗口算法框架。 LeetCode 上至少有 9 道题目可以用此方法高效解决。但是有几道是 VIP 题目,有几道题目虽不难但太复杂,所以本文只选择点赞最高,较为经典的,最能够讲明白的三道题来讲解。...
  • 滑动窗口算法(思想)

    千次阅读 2019-12-20 20:09:13
    滑动窗口算法(思想) 题目: 输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 子串和串中字符的对比,只要出现相同字符都算重复,肯定要用到嵌套循环。如果暴力枚举,每个...
  • 固定窗口和滑动窗口算法了解一下

    千次阅读 2018-09-11 23:32:36
    所以这里记录一下自己了解的各种限流算法,以及各个限流算法的实现。 限流算法的应用场景非常广泛,比如通过限流来确保下游配置较差的应用不会被上游应用的大量请求击穿,无论是HTTP请求还是RPC请求,从而使得服务...
  • MATALB可调用的图像滑动窗口算法,用mex编译后可调用。返回滑动窗口得到的图片块样本。
  • 滑动窗口算法实现 C#

    2012-11-30 10:01:41
    The sliding window algorithm 的过程是,随着窗口的增大有效的近似轨迹也随之增长,直到近似轨迹与原始归轨迹的误差值超过指定的误差范围。
  • 滑动窗口算法总结

    2020-08-12 18:55:00
    应用滑动窗口技术: 我们使用线性循环计算n个项中前k个元素的总和,并将总和存储在变量window_sum中。 然后,我们将在阵列上线性滑动直至达到最终并同时追踪最大和。 要获得k个元素块的当前总和,只需从前一个块中...
  • C++滑动窗口算法

    千次阅读 2019-05-01 21:17:19
    滑动窗口算法在处理一些字符串问题时,可以把复杂度降为O(n)。 题目 给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。 字符串只包含小写英文字母,并且字符...
  • 滑动窗口算法(`Sliding Window Algorithm`)是常见的一种算法:它思想简洁且功能强大,可以用来解决一些查找满足一定条件的**连续区间**的性质/长度的问题。由于区间连续,因此当区间发生变化时,可以通过旧有的计算...
  • 【C语言】滑动窗口算法

    千次阅读 2020-05-16 23:59:09
    1.滑动窗口的思想: 它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有: [a b c]  [b c d]    [c d e]      [d e ...
  • 点击上方蓝字设为星标东哥带你手把手撕力扣~作者:labuladong 公众号:labuladong若已授权白名单也必须保留以上来源信息我有预感本文要火,所以先罗列一下我们号的所有算法套...
  • 【每日leetcode】滑动窗口算法总结

    千次阅读 2019-05-05 20:01:44
    前言科普:什么是滑动窗口算法 滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。 假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有: [a b c]...
  • redis+lua脚本实现滑动窗口算法 运维开发网https://www.qedev.com2020-04-23 09:21出处:网络作者:运维开发网整理 分布式环境下实现流量控制是比较麻烦的事,为了精确控制,采用滑动窗口算法。 通常的流量控制,...
  • [Leetcode] 滑动窗口算法指南

    千次阅读 2019-07-08 15:58:10
    本文会将 LeetCode 里面的大部分滑动窗口问题分析、总结、分类,并提供一个可以参考的模版,相信可以有效减少面试当中的算法实现部分的不确定性。 问题形式 滑动窗口这类问题一般需要用到双指针来进...
  • https://blog.csdn.net/qq_36426073/article/details/90203633
  • 滑动窗口(Sliding Window)算法介绍 前言 最近刷到leetCode里面的一道算法题,里面有涉及到Sliding windowing算法,因此写一篇文章稍微总结一下 算法题介绍 没有重复字符的子字符的最大长度:给一个字符串,获得...
  • 这几天在leetcode刷题,经常遇到可以使用滑动窗口来解决的题目,所以找...在这篇文章, 我会从一道题目入手,先讲解暴力算法, 再到滑动窗口, 然后分析为什么他是对的,最后还会给出滑动窗口算法的一个模板、使用场景、以及
  • TCP的滑动窗口算法

    2019-07-25 14:17:36
    它本质上是描述接收方的TCP数据报缓冲区大小的数据,发送方根据这个数据来计算自己最多能发送多长的数据,如果发送方收到接收方的窗口大小为0的TCP数据报,那么发送方将停止发送数据,等到接收方发送窗口大小不为0...
  • 1 举个栗子 给定一个字符串,找到包含的不同字符个数不超过K的最长的连续子串同样先来几个例子,以便准确地理解问题。例子1:输入: String="araaci", K=2...
  • 求解算法有多种,本篇主要介绍其中的滑动窗口算法。 什么是滑动窗口? 滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i,j)[i, j)[i,j)...
  • 滑动窗口算法(matlab、java)

    万次阅读 2018-10-02 15:00:57
    给定⼀一个数组和滑动窗口的大⼩,找出所有滑动窗口⾥里里数值的最⼤大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗⼝,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,...

空空如也

1 2 3 4 5 ... 20
收藏数 108,200
精华内容 43,280
关键字:

滑动窗口