• Yuchung Cheng's avatar
    tcp: track min RTT using windowed min-filter · f6722583
    Yuchung Cheng authored
    Kathleen Nichols' algorithm for tracking the minimum RTT of a
    data stream over some measurement window. It uses constant space
    and constant time per update. Yet it almost always delivers
    the same minimum as an implementation that has to keep all
    the data in the window. The measurement window is tunable via
    sysctl.net.ipv4.tcp_min_rtt_wlen with a default value of 5 minutes.
    
    The algorithm keeps track of the best, 2nd best & 3rd best min
    values, maintaining an invariant that the measurement time of
    the n'th best >= n-1'th best. It also makes sure that the three
    values are widely separated in the time window since that bounds
    the worse case error when that data is monotonically increasing
    over the window.
    
    Upon getting a new min, we can forget everything earlier because
    it has no value - the new min is less than everything else in the
    window by definition and it's the most recent. So we restart fresh
    on every new min and overwrites the 2nd & 3rd choices. The same
    property holds for the 2nd & 3rd best.
    
    Therefore we have to maintain two invariants to maximize the
    information in the samples, one on values (1st.v <= 2nd.v <=
    3rd.v) and the other on times (now-win <=1st.t <= 2nd.t <= 3rd.t <=
    now). These invariants determine the structure of the code
    
    The RTT input to the windowed filter is the minimum RTT measured
    from ACK or SACK, or as the last resort from TCP timestamps.
    
    The accessor tcp_min_rtt() returns the minimum RTT seen in the
    window. ~0U indicates it is not available. The minimum is 1usec
    even if the true RTT is below that.
    Signed-off-by: default avatarYuchung Cheng <ycheng@google.com>
    Signed-off-by: default avatarNeal Cardwell <ncardwell@google.com>
    Signed-off-by: default avatarEric Dumazet <edumazet@google.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    f6722583
sysctl_net_ipv4.c 24 KB