How does SACK or FACK determine the time to start fast retransmition?

How does SACK or FACK determine the time to start fast retransmition?

[LovelyLich]

HI all,
    When tcp uses reno as its congestion control algothim, it uses
tp->sacked_out as dup-ack. When the third dup-ack(under default
condition) comes, tcp will initiate its fast retransmition.
    But how about sack ?
    According to kernel source code comments, when sack or fack tcp option
is enabled, there is no dup-ack counter. See comments for function
tcp_dupack_heuristics():
http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300
    So , how does tcp know the current dup-ack is the last one which
triggers the fast retransmition?

    According to rfc3517 section 5:
    "Upon the receipt of the first (DupThresh - 1) duplicate ACKs, the
scoreboard is to be updated as normal."
    "When a TCP sender receives the duplicate ACK corresponding to
DupThresh ACKs,
the scoreboard MUST be updated with the new SACK information (via
Update ()). If no previous loss event has occurred
on the connection or the cumulative acknowledgment point is beyond
the last value of RecoveryPoint, a loss recovery phase SHOULD be
initiated, per the fast retransmit algorithm outlined in [RFC2581]."

    But these sentences doesn't describe how tcp knows the current ack
is the dup-threshold dup-ack.

    Accorrding to rfc3517 seciton 4 and isLost(Seqnum) function:
    "The routine returns true when either
DupThresh discontiguous SACKed sequences have arrived above
’SeqNum’ or (DupThresh * SMSS) bytes with sequence numbers greater
than ’SeqNum’ have been SACKed. Otherwise, the routine returns
false."
    I think this is just what I am searching for, but I still don't know
which line of code in Linux tcp protocol does this check.
    Can any one help me ? thks in advance.

Re: How does SACK or FACK determine the time to start fast retransmition?

[Eric Dumazet]

On Wed, 2012-06-20 at 22:31 +0800, LovelyLich wrote:
> HI all,
>     When tcp uses reno as its congestion control algothim, it uses
> tp->sacked_out as dup-ack. When the third dup-ack(under default
> condition) comes, tcp will initiate its fast retransmition.
>     But how about sack ?

Some tcp experts out there only catch tcp related stuff if Subject
includes TCP.

You might resend your mail on netdev (not sure lkml will really help)
with following subject :

[RFC] tcp: How does SACK or FACK determine the time to start fast
retransmission?

To get more traction.

[RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[李易]

HI all,
     When tcp uses reno as its congestion control algothim, it uses
tp->sacked_out as dup-ack. When the third dup-ack(under default
condition) comes, tcp will initiate its fast retransmition.
     But how about sack ?
     According to kernel source code comments, when sack or fack tcp option
is enabled, there is no dup-ack counter. See comments for function
tcp_dupack_heuristics():
http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300
     So , how does tcp know the current dup-ack is the last one which
triggers the fast retransmition?

     According to rfc3517 section 5:
     "Upon the receipt of the first (DupThresh - 1) duplicate ACKs, the
scoreboard is to be updated as normal."
     "When a TCP sender receives the duplicate ACK corresponding to
DupThresh ACKs,
the scoreboard MUST be updated with the new SACK information (via
Update ()). If no previous loss event has occurred
on the connection or the cumulative acknowledgment point is beyond
the last value of RecoveryPoint, a loss recovery phase SHOULD be
initiated, per the fast retransmit algorithm outlined in [RFC2581]."

     But these sentences doesn't describe how tcp knows the current ack
is the dup-threshold dup-ack.

     Accorrding to rfc3517 seciton 4 and isLost(Seqnum) function:
     "The routine returns true when either
DupThresh discontiguous SACKed sequences have arrived above
’SeqNum’ or (DupThresh * SMSS) bytes with sequence numbers greater
than ’SeqNum’ have been SACKed. Otherwise, the routine returns
false."
     I think this is just what I am searching for, but I still don't know
which line of code in Linux tcp protocol does this check.
     Can any one help me ? thks in advance.

[RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[李易]

HI all,
     When tcp uses reno as its congestion control algothim, it uses
tp->sacked_out as dup-ack. When the third dup-ack(under default
condition) comes, tcp will initiate its fast retransmition.
     But how about sack ?
     According to kernel source code comments, when sack or fack tcp option
is enabled, there is no dup-ack counter. See comments for function
tcp_dupack_heuristics():
http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300
     So , how does tcp know the current dup-ack is the last one which
triggers the fast retransmition?

     According to rfc3517 section 5:
     "Upon the receipt of the first (DupThresh - 1) duplicate ACKs, the
scoreboard is to be updated as normal."
     "When a TCP sender receives the duplicate ACK corresponding to
DupThresh ACKs,
the scoreboard MUST be updated with the new SACK information (via
Update ()). If no previous loss event has occurred
on the connection or the cumulative acknowledgment point is beyond
the last value of RecoveryPoint, a loss recovery phase SHOULD be
initiated, per the fast retransmit algorithm outlined in [RFC2581]."

     But these sentences doesn't describe how tcp knows the current ack
is the dup-threshold dup-ack.

     Accorrding to rfc3517 seciton 4 and isLost(Seqnum) function:
     "The routine returns true when either
DupThresh discontiguous SACKed sequences have arrived above
?SeqNum? or (DupThresh * SMSS) bytes with sequence numbers greater
than ?SeqNum? have been SACKed. Otherwise, the routine returns
false."
     I think this is just what I am searching for, but I still don't know
which line of code in Linux tcp protocol does this check.
     Can any one help me ? thks in advance.

Re: [RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[Li Yu]

于 2012年06月21日 14:33, 李易 写道:
> HI all,
> When tcp uses reno as its congestion control algothim, it uses
> tp->sacked_out as dup-ack. When the third dup-ack(under default
> condition) comes, tcp will initiate its fast retransmition.
> But how about sack ?
> According to kernel source code comments, when sack or fack tcp option
> is enabled, there is no dup-ack counter. See comments for function
> tcp_dupack_heuristics():
> http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300
> So , how does tcp know the current dup-ack is the last one which
> triggers the fast retransmition?
>
> According to rfc3517 section 5:
> "Upon the receipt of the first (DupThresh - 1) duplicate ACKs, the
> scoreboard is to be updated as normal."
> "When a TCP sender receives the duplicate ACK corresponding to
> DupThresh ACKs,
> the scoreboard MUST be updated with the new SACK information (via
> Update ()). If no previous loss event has occurred
> on the connection or the cumulative acknowledgment point is beyond
> the last value of RecoveryPoint, a loss recovery phase SHOULD be
> initiated, per the fast retransmit algorithm outlined in [RFC2581]."
>
> But these sentences doesn't describe how tcp knows the current ack
> is the dup-threshold dup-ack.
>
> Accorrding to rfc3517 seciton 4 and isLost(Seqnum) function:
> "The routine returns true when either
> DupThresh discontiguous SACKed sequences have arrived above
> ’SeqNum’ or (DupThresh * SMSS) bytes with sequence numbers greater
> than ’SeqNum’ have been SACKed. Otherwise, the routine returns
> false."
> I think this is just what I am searching for, but I still don't know
> which line of code in Linux tcp protocol does this check.
> Can any one help me ? thks in advance.
>
>

Do you mean you did not locate where FR is triggered in TCP stack ?
I am not a TCP expert, however I think that it may be at
tcp_time_to_recover(), and the "DupThresh" is not a fixed value in
Linux TCP implementation.

Thanks

>
>
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>

Re: [RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[Vijay Subramanian]

On 20 June 2012 23:33, 李易 <lovelylich@gmail.com> wrote:
> HI all,
>     When tcp uses reno as its congestion control algothim, it uses
> tp->sacked_out as dup-ack. When the third dup-ack(under default
> condition) comes, tcp will initiate its fast retransmition.
>     But how about sack ?
>     According to kernel source code comments, when sack or fack tcp option
> is enabled, there is no dup-ack counter. See comments for function
> tcp_dupack_heuristics():
> http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300
>     So , how does tcp know the current dup-ack is the last one which
> triggers the fast retransmition?

With SACK, number of  dupacks does not have much meaning. What matters is
--how the SACK scoreboard looks like i.e. which packets are tagged
Lost/Sacked/Retransmitted
-- Whether FACK is in use (this assumes holes in between sacked
packets are lost and have left the network and so we can send out more
packets)

So, stack does not count the number of dupacks that have come in. Only
SACK blocks matter.
You can try to track the following path:
tcp_ack() deals with incoming acks and if it sees a dupack (does not
matter what number), or incoming packet contains SACK it calls
tcp_fastretrans_alert() which calls  tcp_xmit_retransmit_queue().

tcp_xmit_retransmit_queue() decides which packets to retransmit. The
first packet to start retransmitting from is tracked in
tp->retransmit_skb_hint.
Note that the dupThresh is actually tracked by tp->reordering which
measures  the reordering in the network and is not fixed at 3.  So, if
more than
tp->reordering packets have been acked above a given packet, this
packet is a candidate for retransmisson. See tcp_mark_head_lost() to
see how the
reordering metric is used to mark packets as lost. This corresponds to
the check you mentioned in the RFC.

So, window permitting, packets are sent as follows;
(a)-- Packets marked lost as per description above
(b)-- new packets (if any)
(c)-- Holes between sacked packets  which are not reliably lost.

choice between (b) and (c) is made in tcp_can_forward_retransmit().

Hope this helps.
Vijay

[RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[Vijay Subramanian]

On 20 June 2012 23:33, ?? <lovelylich@gmail.com> wrote:
> HI all,
> ? ? When tcp uses reno as its congestion control algothim, it uses
> tp->sacked_out as dup-ack. When the third dup-ack(under default
> condition) comes, tcp will initiate its fast retransmition.
> ? ? But how about sack ?
> ? ? According to kernel source code comments, when sack or fack tcp option
> is enabled, there is no dup-ack counter. See comments for function
> tcp_dupack_heuristics():
> http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300
> ? ? So , how does tcp know the current dup-ack is the last one which
> triggers the fast retransmition?

With SACK, number of  dupacks does not have much meaning. What matters is
--how the SACK scoreboard looks like i.e. which packets are tagged
Lost/Sacked/Retransmitted
-- Whether FACK is in use (this assumes holes in between sacked
packets are lost and have left the network and so we can send out more
packets)

So, stack does not count the number of dupacks that have come in. Only
SACK blocks matter.
You can try to track the following path:
tcp_ack() deals with incoming acks and if it sees a dupack (does not
matter what number), or incoming packet contains SACK it calls
tcp_fastretrans_alert() which calls  tcp_xmit_retransmit_queue().

tcp_xmit_retransmit_queue() decides which packets to retransmit. The
first packet to start retransmitting from is tracked in
tp->retransmit_skb_hint.
Note that the dupThresh is actually tracked by tp->reordering which
measures  the reordering in the network and is not fixed at 3.  So, if
more than
tp->reordering packets have been acked above a given packet, this
packet is a candidate for retransmisson. See tcp_mark_head_lost() to
see how the
reordering metric is used to mark packets as lost. This corresponds to
the check you mentioned in the RFC.

So, window permitting, packets are sent as follows;
(a)-- Packets marked lost as per description above
(b)-- new packets (if any)
(c)-- Holes between sacked packets  which are not reliably lost.

choice between (b) and (c) is made in tcp_can_forward_retransmit().

Hope this helps.
Vijay

Re: [RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[李易]

于 2012/6/21 16:42, Vijay Subramanian 写道:
> With SACK, number of  dupacks does not have much meaning. What matters is
> --how the SACK scoreboard looks like i.e. which packets are tagged
> Lost/Sacked/Retransmitted
> -- Whether FACK is in use (this assumes holes in between sacked
> packets are lost and have left the network and so we can send out more
> packets)
>
> So, stack does not count the number of dupacks that have come in. Only
> SACK blocks matter.
> You can try to track the following path:
> tcp_ack() deals with incoming acks and if it sees a dupack (does not
> matter what number), or incoming packet contains SACK it calls
> tcp_fastretrans_alert() which calls  tcp_xmit_retransmit_queue().
>
> tcp_xmit_retransmit_queue() decides which packets to retransmit. The
> first packet to start retransmitting from is tracked in
> tp->retransmit_skb_hint.
> Note that the dupThresh is actually tracked by tp->reordering which
> measures  the reordering in the network and is not fixed at 3.  So, if
> more than
> tp->reordering packets have been acked above a given packet, this
> packet is a candidate for retransmisson. See tcp_mark_head_lost() to
> see how the
> reordering metric is used to mark packets as lost. This corresponds to
> the check you mentioned in the RFC.
>
> So, window permitting, packets are sent as follows;
> (a)-- Packets marked lost as per description above
> (b)-- new packets (if any)
> (c)-- Holes between sacked packets  which are not reliably lost.
>
> choice between (b) and (c) is made in tcp_can_forward_retransmit().
>
> Hope this helps.
> Vijay
>
It is just I wanted! Thanks for your detailed explaination and kindness.

[RFC] tcp: How does SACK or FACK determine the time to start fast retransmition?

[李易]

? 2012/6/21 16:42, Vijay Subramanian ??:
> With SACK, number of  dupacks does not have much meaning. What matters is
> --how the SACK scoreboard looks like i.e. which packets are tagged
> Lost/Sacked/Retransmitted
> -- Whether FACK is in use (this assumes holes in between sacked
> packets are lost and have left the network and so we can send out more
> packets)
>
> So, stack does not count the number of dupacks that have come in. Only
> SACK blocks matter.
> You can try to track the following path:
> tcp_ack() deals with incoming acks and if it sees a dupack (does not
> matter what number), or incoming packet contains SACK it calls
> tcp_fastretrans_alert() which calls  tcp_xmit_retransmit_queue().
>
> tcp_xmit_retransmit_queue() decides which packets to retransmit. The
> first packet to start retransmitting from is tracked in
> tp->retransmit_skb_hint.
> Note that the dupThresh is actually tracked by tp->reordering which
> measures  the reordering in the network and is not fixed at 3.  So, if
> more than
> tp->reordering packets have been acked above a given packet, this
> packet is a candidate for retransmisson. See tcp_mark_head_lost() to
> see how the
> reordering metric is used to mark packets as lost. This corresponds to
> the check you mentioned in the RFC.
>
> So, window permitting, packets are sent as follows;
> (a)-- Packets marked lost as per description above
> (b)-- new packets (if any)
> (c)-- Holes between sacked packets  which are not reliably lost.
>
> choice between (b) and (c) is made in tcp_can_forward_retransmit().
>
> Hope this helps.
> Vijay
>
It is just I wanted! Thanks for your detailed explaination and kindness.

How does SACK or FACK determine the time to start fast retransmition ?

[李易]

HI all,
	When tcp uses reno as its congestion control algothim, it uses
tp->sacked_out as dup-ack. When the third dup-ack(under default
condition) comes, tcp will initiate its fast retransmition.
	But how about sack ?
	According to kernel source code comments, when sack or fack tcp option
is enabled, there is no dup-ack counter. See comments for function
tcp_dupack_heuristics():
http://lxr.linux.no/linux+v2.6.37/net/ipv4/tcp_input.c#L2300

	So , how does tcp know the current dup-ack is the last one which
triggers the fast retransmition?
	
	According to rfc3517 section 5:
	"Upon the receipt of the first (DupThresh - 1) duplicate ACKs, the
scoreboard is to be updated as normal."
	"When a TCP sender receives the duplicate ACK corresponding to
DupThresh ACKs, the scoreboard MUST be updated with the new SACK
information (via Update ()). If no previous loss event has occurred
on the connection or the cumulative acknowledgment point is beyond
the last value of RecoveryPoint, a loss recovery phase SHOULD be
initiated, per the fast retransmit algorithm outlined in [RFC2581]."
	
	But these sentences doesn't describe how tcp knows the current ack is
the dup-threshold dup-ack.
	

	Accorrding to rfc3517 seciton 4 and isLost(Seqnum) function:
	"The routine returns true when either
DupThresh discontiguous SACKed sequences have arrived above
?SeqNum? or (DupThresh * SMSS) bytes with sequence numbers greater
than ?SeqNum? have been SACKed. Otherwise, the routine returns
false."
	I think this is just what I am searching for, but I still don't know
which line of code in Linux tcp protocol does this check.
	Can any one help me ? thks in advance.