• Gerrit Renker's avatar
    dccp ccid-3: A lower bound for the inter-packet scheduling algorithm · 20cbd3e1
    Gerrit Renker authored
    This fixes a subtle bug in the calculation of the inter-packet gap and shows
    that t_delta, as it is currently used, is not needed.
    
    The algorithm from RFC 5348, 8.3 below continually computes a send time t_nom,
    which is initialised with the current time t_now; t_gran = 1E6 / HZ specifies
    the scheduling granularity, s the packet size, and X the sending rate:
    
      t_distance = t_nom - t_now;		// in microseconds
      t_delta    = min(t_ipi, t_gran) / 2;	// `delta' parameter in microseconds
    
      if (t_distance >= t_delta) {
    	reschedule after (t_distance / 1000) milliseconds;
      } else {
      	t_ipi  = s / X;			// inter-packet interval in usec
    	t_nom += t_ipi;			// compute the next send time
    	send packet now;
      }
    
    Problem:
    --------
    Rescheduling requires a conversion into milliseconds (sk_reset_timer()). The
    highest jiffy resolution with HZ=1000 is 1 millisecond, so using a higher
    granularity does not make much sense here.
    
    As a consequence, values of t_distance < 1000 are truncated to 0. This issue
    has so far been resolved by using instead
    
      if (t_distance >= t_delta + 1000)
    	reschedule after (t_distance / 1000) milliseconds;
    
    This is unnecessarily large, a lower bound is t_delta' = max(t_delta, 1000).
    And it implies a further simplification:
    
     a) when HZ >= 500, then t_delta <= t_gran/2 = 10^6/(2*HZ) <= 1000, so that
        t_delta' = MAX(1000, t_delta) = 1000 (constant value);
    
     b) when HZ < 500, then t_delta = 1/2*MIN(rtt, t_ipi, t_gran) <= t_gran/2,
        so that 1000 <= t_delta' <= t_gran/2.
    
    The maximum error of using a constant t_delta in (b) is less than half a jiffy.
    
    Fix:
    ----
    The patch replaces t_delta with a constant, whose value depends on CONFIG_HZ,
    changing the above algorithm to:
    
      if (t_distance >= t_delta')
    	reschedule after (t_distance / 1000) milliseconds;
    
    where t_delta' = 10^6/(2*HZ) if HZ < 500, and t_delta' = 1000 otherwise.
    Signed-off-by: default avatarGerrit Renker <gerrit@erg.abdn.ac.uk>
    20cbd3e1
ccid3.h 5.7 KB