What kind of data structure is used by TCP to keep track of received and missing bytes for purposes of forming correct SACK numbers?

Question

Say I have a client that successfully receives packets from server in the following bytes ranges: 0-99, 100-199, 200-299. The next packet 300-399 gets lost but the final one 400-499 is successfully received.

When the client parses packet 400-499, it realizes that the previous segment of 300-399 is missing.

This is a simplified example that could be solved by having:

• 1 number tracking the in-order read data,
• another number the next expected in-order data,
• third number would keep track of the first greater out of order number and
• fourth, the last greatest out of order number.

I think this would work for a case where all the missing packets are contiguous and there is only 1 gap in TCP stream. What kind of data structure could keep track of multiple segments of missing packets that are not contiguous? How is this implemented at the OS level? It would help me understnad SACK implementation. SACK can has at most 4 blocks and it pre-pads with "NOPs" each block up to bytes divisible by 4 in TCP options. I am yet to see a pcap with more than 1 SACK option.

My question is about how the underlying technology keeps track of the numbers needed to construct the SACK, not the implementation of SACK itself.

Answer 1

The mechanism is actually very simple.

Wikipedia Transmission Control Protocol (TCP) says this :

Dupack-based retransmission

If a single segment (say segment number 100) in a stream is lost, then the receiver cannot acknowledge packets above that segment number (100) because it uses cumulative ACKs. Hence the receiver acknowledges packet 99 again on the receipt of another data packet. This duplicate acknowledgement is used as a signal for packet loss. That is, if the sender receives three duplicate acknowledgements, it retransmits the last unacknowledged packet. A threshold of three is used because the network may reorder segments causing duplicate acknowledgements. This threshold has been demonstrated to avoid spurious retransmissions due to reordering. Some TCP implementations use selective acknowledgements (SACKs) to provide explicit feedback about the segments that have been received. This greatly improves TCP's ability to retransmit the right segments.

Retransmission ambiguity can cause spurious fast retransmissions and congestion avoidance if there is reordering beyond the duplicate acknowledgement threshold.