Shulou(Shulou.com)06/03 Report--

Overview

The sliding window realizes the TCP flow control. First of all, make clear the scope of the sliding window: TCP is a duplex protocol, and both sides of the session can receive and send data at the same time. Both sides of the TCP session maintain a send window and a receive window. The size of each receiving window depends on the limitations of the application, system and hardware (the TCP transmission rate cannot be greater than the data processing rate of the application). The respective sending window requirements depend on the receiving window advertised by the opposite end, and the requirements are the same.

The sliding window solves the problem of flow control, that is, how to make the two sides agree if the processing speed of the packet is different between the receiver and the sender. The cache of the receiver transmits data to the application layer, but this process is not necessarily real-time. If the sending speed is too fast, the data overflow of the receiver will appear. Flow control solves this problem.

The concept of window

The data in the sender's send cache can be divided into four categories:

Sent, received ACK sent, not received ACK not sent, but allowed to send not sent, but not allowed to send

Where types 2 and 3 belong to the send window.

The cached data of the receiver is divided into three categories:

Received but ready to receive and not ready to receive

Type 2 belongs to the receive window.

The window size represents how much data the device can process from the peer at a time and then pass it to the application layer. The data cached to the application layer cannot be out of order, which is guaranteed by the window mechanism. In reality, the application layer may not be able to read data from the cache immediately.

Sliding mechanism

The sending window will move the left boundary of the sending window only if it receives an ACK confirmation of the bytes in the sending window.

The receive window moves the left boundary only if all previous segments are confirmed. When the previous byte is not received but the next byte is received, the window does not move and does not acknowledge the subsequent byte. To ensure that the data is retransmitted by the peer.

Follow the rules of fast retransmission, cumulative confirmation, selective confirmation and so on.

The window size sent by the sender is 8192; that is, the receiver sends a maximum of 8192 bytes, and this 8192 is generally the size of the receiving cache of the sender.

From the above process, we can draw the following conclusions:

The TCP connection is achieved through data packets and ACK, and we, as a third party, can see the process of sending packets by both parties, but the receiver does not know what the sender is sending before receiving it. Similarly, the sender does not know whether the other party has successfully received the ACK before receiving it.

The sender cannot slide to the right without receiving the ACK sent back by the receiver. Suppose the sender slides when he sends ABCD to the receiver, and as long as the other party does not receive A, he cannot slide, then the two will be out of sync.

Sliding window improves the channel utilization. TCP is a unit of sending message segment. If you have to wait for ACK for every message sent, then for large data packets, the waiting time is too long. As long as the message sent is in the sliding window, you can slide to the right without waiting for each ACK to come back. In this example, the receiver starts with an empty AB, only CD, and cannot slide at this time; after receiving EF and H, slide 2 bits directly to the right without having to wait for G to be in place.

The window size cannot be more than half the size of the ordinal space. The purpose is to prevent the two windows from overlapping, for example, the total size is 7, the window size is 4, and the receive window should slide 4, but there are only 3 serial numbers left, causing the two windows to iterate over each other.

There is one situation that does not happen: the sender sends the ABCD, and the receiver receives it and slides to the right, but all the ACK packets are lost. The sender does not receive any ACK, and the timeout will resend the ABCD. According to the principle of cumulative confirmation, the receiver will only resend the D ACK after receiving the ABCD, and the sender will slide to the right after receiving it.

Compare sliding window with congestion window

The sliding window controls the range of data received and synchronized, and notifies the sender of the range of data currently received, which is used for flow control and used by the receiver. The congestion window controls the sending rate to avoid sending too much and is used by the sender. Because tcp is full-duplex, there are sliding windows on both sides.

The maintenance of the two windows is independent, the sliding window is mainly maintained by the receiver feedback cache, and the congestion window is mainly determined by the degree of network congestion detected by the sender's congestion control algorithm.

The congestion window controls the rate at which sender transmits data to connection, making this rate a function of network congestion.

Find a classic question:

(1) given an array of integers of size n, calculate the maximum value of the sum of subarrays of length k.

such as

The array is: 1, 2, 3, 4

The maximum value is: 3, 4, 7

The array is:-1, 4, 7, 7, 3, 8, 5, 5, 5, 5, 4, 5, 4, 4, 4, 4, 4, 4, 7, 8, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 7, 4, 4, 4, 7, 4, 4, 7, 4, 4, 4, 7, 4, 4, 7, 4, 4, 7, 4, 4, 7, 4, 4, 7, 4, 7, 5, 5, 4, 4, 4, 4, 4, 7, 4, 4, 7, 5, 5, 4, 4, 4, 4, 4, 4, 14, 4, 4, 4, 14, 4, 4, 4, 7, 4, 7, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 7, 4

The maximum value is 7-3-8-12.

To think of the simplest idea, go through all the subarrays, sum and then compare.

The index of the first element of the largest subarray of int index = 0 int maxSum / record, currently 0 int maxSum = 0 maxSum of the largest subarray of records, and currently the first subarray of for from the left (maxSum I = 0; I < k; iSum +) {maxSum + = array [I];} for (int I = 1; I maxSum) {/ / if greater than the maximum sum, record maxSum = curSum Index = I;}}

Using the idea of sliding window, the ergodic loop is not nested to calculate all the values; the outer traversal is equivalent to the window sliding to the right, each time minus the failure value plus the latest value, that is, the sum of the current window, and then compare.

Copy the code

Int index = 0 position / the index of the first element of the largest subarray of records, currently 0

Int maxSum = 0 position move / record the largest subarray sum, currently the first subarray from the left

For (int I = 0; I < k; iTunes +) {

MaxSum + = array [I]

}

Int curWindowSum = maxSum; for (int I = 1; I maxSum) {/ / if greater than the maximum sum, record maxSum = curWindowSum; index = I;}}

Copy the code

You can see that the code is similar, but in the calculation of summation, the sliding window technique is adopted to eliminate the internal loop by subtracting and summing.

Note: to highlight the semantics here, change the variable name curSum to curWindowSum

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.