Defer data retransmission with out-of-order report segments

[BrianSipos]

When the network is causing out-of-order segment reception it is possible that one or more synchronous reception reports are received either out-of-order or within a short time window, possibly followed by an asynchronous reception report (see #23) indicating that the full red part was received. To avoid unnecessary data retransmission the sending engine should defer sending gap-filling data segments until some small window of time after the last reception report for that session.

Upon receiving a reception report the sending engine should (in addition to sending a report ack segment):

1. Add (as a set union) the report's claims to the total claims seen for the session.
2. If there are gaps in the claims, start a retransmission timer for the session
3. Otherwise, if there is a retransmission timer running stop it (there is no need to retransmit in this case)

When the retransmission timer expires (i.e. there are still gaps to send) then send data segments to cover the remaining gaps for the session.

The result of this procedure is that the sending engine will not send either duplicate data segments to cover gaps in earlier-sent reports which are claimed in later-sent reports. In the case of no loss but highly out-of-order this will result in no unnecessary data retransmission to occur.

[briantomko]

@BrianSipos I was trying to add more detail. Does this make sense:

Upon receiving a reception report the sending engine should (in addition to sending a report ack segment):

1.) Add (as a set union) the report's claims to the total claims seen for the session. 2.) If there are gaps in the total claims seen for the session (i.e. between lowerBound=0 and upperBound=lengthOfRedPart) then: a.) start a single retransmission timer for the session (NOT one timer per report) if it's not already running b.) append to a queue this reception report's lowerBound, upperBound, and reportSerialNumber 3.) Otherwise (i.e. all red data received by remote), if there is a retransmission timer running stop it (there is no need to retransmit data segments in this case)

When the retransmission timer expires (i.e. there are still gaps to send) then:

1.) iterate through the queue of reception reports. For each reception report,: a.) if their are no gaps between its lowerBound and upperBound (comparing with the union of total claims seen for the session), then ignore this reception report. It shall be treated as a discretionary checkpoint not needing sent. b.) otherwise, send the data segments pertaining to this reception report with the last segment as a checkpoint that includes the reportSerialNumber. We assume and trust that the sender efficiently chooses lowerBounds and upperBounds for report segments that do not overlap with each other. This keeps things simpler so that we don't have to track unions of lowerBounds and upperBounds and trying to merge them.

[briantomko]

Perhaps we should not start the non-running timer if the reception report has no gaps between it's own lower and upper bound, even if it's lower bound is not 0 and it's upper bound is not lengthOfRedPart?

[BrianSipos]

I think your detailed algorithm is correct. Retransmit timer is only needed if there are identified gaps and is specifically not needed if there are no gaps. For the internal logic, it may be better to invert the state to bookkeep with gaps rather than claims because the logic then becomes "are there any gaps in all seen report bounds?" rather than more complex logic of "how do seen claims differ from all seen report bounds?". It's asking the same question, but the first one can be shortcut by saying "is this set empty?"

If you haven't investigated already, there is a boost interval library that could be used to help with bookkeeping some of this.

[briantomko]

This issue has been resolved by commit 025194db. I added this to side branch 111-defer-reception-reports and will close the issue when it's merged into master. The following algorithm is used:

// When the network is causing out-of-order segment reception it is possible that one or more
// synchronous reception reports are received either out-of-order or within a short time window,
// possibly followed by an asynchronous reception report (see #23) indicating that the full red
// part was received. To avoid unnecessary data retransmission the sending engine should defer
// sending gap-filling data segments until some small window of time after the last reception
// report for that session.
//
// Upon receiving a reception report the sending engine should (in addition to sending a report ack segment):
//
// 1.) Add (as a set union) the report's claims to the total claims seen for the session.
// 2.) If a retransmission timer is not running:
//      a.) If there are gaps in this report's claims (between its lower and upper bounds)
//          (Note: gaps exist because the report itself has gaps AND no prior received report filled those gaps),
//          then add this report to a pending report list and start a retransmission timer for the session
// 3.) Otherwise, (i.e. If a retransmission timer is running):
//      a.) add this report to the pending report list
//      b.) if there are no gaps between the smallest lower bound of the pending report list
//          and the largest upper bound of the pending report list then:
//             stop the timer and clear the list (there is no need to retransmit
//             data segments from any of the reports in the list)
//
// When the retransmission timer expires (i.e. there are still gaps to send) then send data segments to cover the remaining gaps for the session.
// This involves iterating through the pending report list starting from the report with the lowest lowerBound
// and transmitting the report serial number as the checkpoint for its last segment.
// Subsequent reports in the iteration of the list should be ignored if everything
// between their upper and lower bounds are fully contained in the set union
// of ((total claims seen for the session) UNION (the just sent data segments of the prior reports in this list)).
//
// The result of this procedure is that the sending engine will not send either duplicate data segments to
// cover gaps in earlier-sent reports which are claimed in later-sent reports. In the case of no loss but
// highly out-of-order this will result in no unnecessary data retransmission to occur.