1. 15 Sep, 2010 1 commit
    • 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
  2. 14 Sep, 2010 11 commits
  3. 12 Sep, 2010 1 commit
  4. 10 Sep, 2010 26 commits
  5. 09 Sep, 2010 1 commit