The two-pointer approach is a popular algorithmic technique used in programming to solve problems involving iterating over arrays, lists or linked lists. It uses two pointers (or indices) to traverse the data structure to achieve a specific goal.
In this approach, one pointer (or index) is used to track the current position in the array, while another pointer is conceptually used to track the required position based on the problem. This approach is useful for problems like finding pairs that sum to a target value, reversing a list, detecting cycles in linked lists, sliding window techniques related problems, merging two sorted lists, removing duplicates in-place, etc.
This approach helps in reducing time complexity, eg. from O(n²) to O(n *log n).
TCP Sliding Window story
- TCP is stream-oriented as it treats the data coming from the application as a stream.
- TCP takes the stream from applications and divides it into discrete messages called TCP segments.
- TCP segments are sized based on different parameters such as MSS(maximum segment size), and how much data the receiver is ready to accept at any given time.
- In TCP, the data is received in the order it was sent. TCP must retransmit any lost data.
- As TCP is stream-oriented, each byte (of data) is assigned a sequence number. These sequence numbers ensure that data sent in segments is reassembled into the original data stream.
- TCP provides reliability and data flow control. TCP ensures that data arrives at its destination. Data Flow Control means managing the rate at which data is sent so that it does not overwhelm the receiving device. TCP sliding window acknowledgment system helps in achieving reliability and data flow control.
- TCP send buffer bytes are divided into 4 categories:
- Bytes Sent and Acknowledged: These are the earliest bytes in the stream that have been sent and acknowledged by the receiver. From the sender’s perspective, these bytes are considered “accomplished.”
Example: Suppose 31 bytes of data have already been sent and acknowledged. These fall into Category #1.
2. Bytes Sent but Not Yet Acknowledged: These bytes have been sent by the sender but have not yet been acknowledged by the receiver. The sender cannot consider these bytes as “accomplished” until they receive an acknowledgment.
Example: Let’s say there are 14 bytes in this category. These bytes are in transit and awaiting acknowledgment.
3. Bytes Not Yet Sent for Which Recipient Is Ready: These are bytes that have not yet been sent but for which the recipient has indicated readiness to receive, based on the most recent communication about the window size. The sender will attempt to send these bytes immediately, subject to certain algorithmic restrictions.
Example: Suppose there are 6 bytes in this category. These bytes are queued for immediate transmission.
4. Bytes Not Yet Sent for Which Recipient Is Not Ready: These are bytes further down the stream that the sender is not yet allowed to send because the receiver is not ready to accept them. These bytes will be sent once the receiver indicates readiness.
Example: There are 44 bytes in this category. These bytes are waiting for the receiver to signal readiness.
The below diagram shows an example of the above-mentioned categories of bytes in the TCP send buffer:
- The receiving device uses a similar system to differentiate between data received and acknowledged, not yet received but ready to receive, and not yet received and not yet ready to receive.
- Send window and Usable window
The send window represents the total number of bytes that the sender is allowed to send without receiving an acknowledgment. It helps manage the flow of data and prevents the sender from overwhelming the receiver with too much data at once.
The usable window is the portion of the send window that the sender can currently use to send new data. It is calculated as the size of the send window minus the number of unacknowledged bytes already sent.
Usable Window = Send Window Size − Unacknowledged Bytes
It dynamically adjusts based on the acknowledgments received from the receiver, allowing the sender to continue transmitting data efficiently.
The below diagram shows an example of send window:
- TCP is a cumulative acknowledgment system, it can only use a single number to acknowledge data, the number of the last contiguous byte in the stream successfully received.
- When the sending device receives acknowledgment, it will transfer some of the bytes from Category #2 to Category #1. Since some bytes have been acknowledged, and the window size didn’t change, the sender is allowed to send some more bytes. The window shifts, or slides, over to the right in the timeline.
The below diagram shows the send window shifting:
- TCP acknowledgments are cumulative, and tell a transmitter that all the bytes up to the sequence number indicated in the acknowledgment were received successfully. Thus, if bytes are received out of order, they cannot be acknowledged until all the preceding bytes are received. TCP includes a method for timing transmissions and retransmitting lost segments if necessary.
Linux TCP code related to TCP send window
- snd_wnd, max_window, mss_cache, snd_wl1 fields in tcp_sock structure: specify the current and maximum send window sizes, Maximum segment size for this connection, and sequence for window update.
- snd_una, a field in the tcp_sock structure, represents the oldest acknowledged sequence number. It is the left edge of the send window. The snd_una value is updated when acknowledgments are received (in tcp_snd_una_update() called from tcp_ack_update_window()). This field is crucial for TCP’s reliable data transfer mechanism, as it helps determine which segments need to be retransmitted if lost. It is used in various TCP operations, including congestion control and window management.
- The end_seq field in the tcp_sock structure keeps track of the sequence number for the end of category #2 bytes (that is end of “Sent but not yet acknowledged” bytes or beginning of usable window). It represents the highest sequence number sent to the receiver. It is updated when sending new data (in tcp_sendmsg_locked()). It’s used in various TCP operations to ensure the sender doesn’t transmit data beyond what the receiver can handle.
- tcp_wnd_end() calculates the right edge of the TCP send window based on the current state of the TCP connection (
tp->snd_una + tp->snd_wnd). - tcp_snd_wnd_test() checks if there’s available space in the send window to transmit more data. The function compares the end sequence number of a given skb (socket buffer) against the right edge of the current send window. The tcp_snd_wnd_test() function is crucial for TCP’s flow control, ensuring that the sender doesn’t transmit more data than the receiver can handle based on the advertised window size.
Two-Pointer Approach in TCP Sliding Window
In the context of the TCP sliding window, the two-pointer approach can be visualized as follows:
- Left Pointer: snd_una field in the tcp_sock structure is used to point to the beginning of the send window.
- Right Pointer: end_seq field in the tcp_sock structure is used to point to the current position of the send window.
As acknowledgments are received, the left pointer moves forward, allowing the window to slide and new bytes to be sent. The right pointer adjusts based on the number of bytes sent to the receiver.
Introducing Jyo Services — Your Go-To Partner for Tech Solutions
Are you looking to boost your career or bring your tech ideas to life? Jyo Services offers a range of specialized solutions tailored just for you:
- One-on-One Interview Preparation: Tailored coaching for freshers and professionals with up to 7 years of software development experience.
- Custom Software Development: Expertise in embedded technologies, AI/ML, Gen AI, Cyber Security, Linux-based applications, and network protocol developments.
- Patent Assistance: Comprehensive support for drafting, filing and maintaining patents in India.
- College Projects: Professional guidance for Engineering students on academic projects.
Unlock your potential with Jyo Services! Contact us today to get started.
DM me at: www.linkedin.com/in/jyothivs or jyos.v.s@gmail.com
References
- http://www.tcpipguide.com/
- Linux Kernel code
