dccp ccid-3: A lower bound for the inter-packet scheduling algorithm
authorGerrit Renker <gerrit@erg.abdn.ac.uk>
Tue, 14 Sep 2010 18:16:59 +0000 (20:16 +0200)
committerGerrit Renker <gerrit@erg.abdn.ac.uk>
Wed, 15 Sep 2010 10:36:01 +0000 (12:36 +0200)
commit20cbd3e120a0c20bebe420e1fed0e816730bb988
tree1c58cf0b974fd0bb4b5a17846e4711e109901096
parent068e8a30320e33b1f8d15df9eaef84f04258f96d
dccp ccid-3: A lower bound for the inter-packet scheduling algorithm

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: Gerrit Renker <gerrit@erg.abdn.ac.uk>
net/dccp/ccids/ccid3.c
net/dccp/ccids/ccid3.h