Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Ian McDonald]

I'll have to have a think about this one some more as I spent a lot of
time fixing these timing and I distinctly remember getting this one
right! The timing is altered all over the code and it can't be fixed
in one place in isolation (unless the whole code is simplified).

I'll study this some more when I can...

On 11/22/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> [CCID 3]: Fix calculation of t_ipi time of scheduled transmission
>
> Problem:
> --------
>  Currently packet transmissions are not scheduled according to [RFC 3448, 4.6] and
>  will, in the worst case, be sent later than necessary. If scheduled transmission
>  requires using a delay, the current delay value is also larger as necessary.
>
> Solution:
> ---------
>  This patch fixes time and delay calculation for scheduling CCID 3 packets.
>
>
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
>
>
>
>     D e t a i l e d   D e r i v a t i o n   [not meant as commit message]
>     ==================================>
> Background:
> -----------
>  [RFC 3448, 4.6] specifies the scheduling of packet transmissions with regard to
>  scheduling granularity. The calculated sending time is called `nominal' sending
>  time t_nom. The initial sending time is called t_0. The first sending time is called
>  t_1 = t0 + t_ipi. From then on, successive sending times are calculated as
>
>           t_nom  =  t_(i+1)  =  t_i + t_ipi
>
>  This is illustrated by the ASCII-Art below:
>
>
>  |<-------------------- t_ipi ------------------->|
>
>  +------------------------------------------------+-----------------------
>  |                       |                        |
>  |                       |                        |
>  +------------------------------------------------+-----------------------
>  |            ^          |<------- t_delta ------>|
>  |            |          |                        |
>  t_i          t_now      t_nom - t_delta          t_nom = t_(i+1)
>
>               |<-----  t_ipi - (t_now - t_i)  --->|
>
>
>  Due to scheduling granularity, t_nom is not necessarily exactly the same as the
>  actual sending time, hence [RFC 3448, 4.6] introduced the following test:
>
>     t_delta = min(t_ipi/2, t_gran/2);      /* t_gran: scheduling granularity */
>
>     if (t_now > t_nom - t_delta)
>         // send the packet now
>     else
>         // send the packet in t_ipi - (t_now - t_i) microseconds
>
>  In the above illustration, t_now was too early for sending (`else' case).
>
>
> Current state:
> --------------
>  Currently the code determines nominal send times using the following pseudo-code:
>    delay_in_msec = -1/1000 * (t_now - t_nom - t_delta)
>                  =  1/1000 * (t_nom + t_delta - t_now)
>
>    if (delay_in_msec > 0)     /* equivalent to t_now <  t_nom + t_delta              */
>        return delay_in_msec;  /* i.e. reschedule in (t_nom -(t_now - t_delta))/1000  */
>    else                       /* whenever      t_now >= t_nom + t_delta              */
>        /* send packet now */
>
>  This means that currently
>
>     * the packet is sent now whenever t_now >= t_nom + t_delta
>       instead of                      t_now >  t_nom - t_delta
>       => this incurs a performance degradation, since 2*t_delta is spent unnecessarily
>
>     * the delay causes the packet to be rescheduled at the following point of time:
>            t_now + (t_nom + t_delta - t_now) = t_nom + t_delta
>       Hence again t_delta time units are not used.
>
> Solution:
> ---------
>  The condition `if (t_now > t_nom - t_delta)' from [RFC 3448, 4.6] is equivalent with
>  the condition `if (t_nom - t_now < t_delta)' and the delay simplifies (cf. above figure):
>    t_ipi - (t_now - t_i)  =  t_i + t_ipi - t_now
>                           =  t_nom - t_now
>  Thus we can twice use `t_nom - t_now', which is what the patch does.
>
> ---
>  net/dccp/ccids/ccid3.c |   18 +++++++++++++-----
>  1 file changed, 13 insertions(+), 5 deletions(-)
>
> --- a/net/dccp/ccids/ccid3.c
> +++ b/net/dccp/ccids/ccid3.c
> @@ -303,11 +303,19 @@ static int ccid3_hc_tx_send_packet(struc
>                 break;
>         case TFRC_SSTATE_NO_FBACK:
>         case TFRC_SSTATE_FBACK:
> -               delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) -
> -                        hctx->ccid3hctx_delta);
> -               delay /= -1000;
> -               /* divide by -1000 is to convert to ms and get sign right */
> -               rc = delay > 0 ? delay : 0;
> +               delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);
> +               /*
> +                *      Scheduling of packet transmissions [RFC 3448, 4.6]
> +                *
> +                * if (t_now > t_nom - delta)
> +                *       // send the packet now
> +                * else
> +                *       // send the packet in (t_nom - t_now) milliseconds.
> +                */
> +               if (delay < hctx->ccid3hctx_delta)
> +                       rc = 0;
> +               else
> +                       rc = delay/1000L;
>                 break;
>         case TFRC_SSTATE_TERM:
>                 DCCP_BUG("Illegal %s state TERM, sk=%p", dccp_role(sk), sk);
> -
> To unsubscribe from this list: send the line "unsubscribe dccp" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>


-- 
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Ian McDonald]

>     * the packet is sent now whenever t_now >= t_nom + t_delta
>       instead of                      t_now >  t_nom - t_delta
>       => this incurs a performance degradation, since 2*t_delta is spent unnecessarily
>
Yes you are right here. This is a bug

> +                * if (t_now > t_nom - delta)
> +                *       // send the packet now
> +                * else
> +                *       // send the packet in (t_nom - t_now) milliseconds.
> +                */
> +               if (delay < hctx->ccid3hctx_delta)
> +                       rc = 0;
> +               else
> +                       rc = delay/1000L;

Shouldn't that last line be rc = (delay-hctx->ccid3hctx_delta)/1000 as
you're not taking the delta into account on the else clause.

Ian
-- 
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Ian McDonald]

On 11/23/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> Quoting Ian McDonald:
> |  I'll have to have a think about this one some more as I spent a lot of
> |  time fixing these timing and I distinctly remember getting this one
> |  right!
> Please relax: It is not my intention to embark on a game of "who is right here". I think
> you have done a good job getting this code so far as it is, given the many and in parts
> confusing documents that have to be read (for comparison: UDP, RFC 768, needs only 3 pages).
> My intention is in making sure it meets the specifications and contribute where I can to fix things.

Gerrit - I was not trying to cast dispersions on you at all. I just
wanted some time to review it properly as I've spent a bit of time in
this code and would like to review CCID3 changes before they merge.

As it turns out I was wrong in my calculation here. I fixed up the
calculation of packet sending times which used to be wrong but I got
this part (delta) wrong by reversing signs.

>   => Since these bits are so similar, I would actually suggest to accommodate them in
>       one function, since:
>                 --t_ipi changes only if one of `s' or X_calc changes
>                 --if `s' / X_calc remain unchanged after feedback, t_ipi remains as before
>                 --t_delta depends on t_ipi
>                 --the calculation of t_nom depends on t_ipi (as in the above snippets)
>

Agree.

Gerrit - I really appreciate the work you are doing on CCID3. I'm
pretty sure you're a better programmer than me, I just get a little
sensitive with CCID3 being "my baby" for a fair bit.

Onwards and upwards.

Regards,

Ian
-- 
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Gerrit Renker]

|  Gerrit - I was not trying to cast dispersions on you at all. I just
|  wanted some time to review it properly as I've spent a bit of time in
|  this code and would like to review CCID3 changes before they merge.
I understand this and this is the main reason why only send small, incremental patches; and
strive to give a justification for each step. In this way it is easier to verify whether the
changes actually improve the code or if they are not necessary. What I want to avoid is 
messing up someone else's code.

|  >   => Since these bits are so similar, I would actually suggest to accommodate them in
|  >       one function, since:
|  >                 --t_ipi changes only if one of `s' or X_calc changes
|  >                 --if `s' / X_calc remain unchanged after feedback, t_ipi remains as before
|  >                 --t_delta depends on t_ipi
|  >                 --the calculation of t_nom depends on t_ipi (as in the above snippets)
|  >
|  
|  Agree.
Since your last email I have spent some more time going through the standard documents; if you
agree then it may be good to update - will review and prepare patches for review.

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Gerrit Renker]

Quoting Ian McDonald:
|  > +                * if (t_now > t_nom - delta)
|  > +                *       // send the packet now
|  > +                * else
|  > +                *       // send the packet in (t_nom - t_now) milliseconds.
|  > +                */
|  > +               if (delay < hctx->ccid3hctx_delta)
|  > +                       rc = 0;
|  > +               else
|  > +                       rc = delay/1000L;
|  
|  Shouldn't that last line be rc = (delay-hctx->ccid3hctx_delta)/1000 as
|  you're not taking the delta into account on the else clause.

The value of `delay' is the difference between t_nom = t_(i+1) and t_now:

	delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);

If this difference is less than delta (which includes the case when t_now is
later than t_nom such that the difference is negative), then the packet is sent now.

If the difference is greater than delta then t_now < t_nom and the packet is too early
to be sent; [RFC 3448, 4.6] says to reschedule in 

          t_ipi - (t_now - t_i) = t_ipi - (t_now - t_i) = (t_i + t_ipi) - t_now
                                                        = t_(i+1)       - t_now
                                                        = t_nom         - t_now

Hence we can reuse the timeval_delta. Maybe the variable should be renamed to highlight
the fact that it is a time difference, but I quite liked `delay'.

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Ian McDonald]

On 11/23/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> |  Gerrit - I was not trying to cast dispersions on you at all. I just
> |  wanted some time to review it properly as I've spent a bit of time in
> |  this code and would like to review CCID3 changes before they merge.
> I understand this and this is the main reason why only send small, incremental patches; and
> strive to give a justification for each step. In this way it is easier to verify whether the
> changes actually improve the code or if they are not necessary. What I want to avoid is
> messing up someone else's code.
>
Don't worry about that. The code is already a mess and needs some
demessing I think :-)

> Since your last email I have spent some more time going through the standard documents; if you
> agree then it may be good to update - will review and prepare patches for review.

Of course - go ahead as I want DCCP to keep improving and geting better.

-- 
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Ian McDonald]

> |  Shouldn't that last line be rc = (delay-hctx->ccid3hctx_delta)/1000 as
> |  you're not taking the delta into account on the else clause.
>
> The value of `delay' is the difference between t_nom = t_(i+1) and t_now:
>
>         delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);
>
> If this difference is less than delta (which includes the case when t_now is
> later than t_nom such that the difference is negative), then the packet is sent now.
>
> If the difference is greater than delta then t_now < t_nom and the packet is too early
> to be sent; [RFC 3448, 4.6] says to reschedule in
>
>           t_ipi - (t_now - t_i) = t_ipi - (t_now - t_i) = (t_i + t_ipi) - t_now
>                                                         = t_(i+1)       - t_now
>                                                         = t_nom         - t_now
>
> Hence we can reuse the timeval_delta. Maybe the variable should be renamed to highlight
> the fact that it is a time difference, but I quite liked `delay'.

OK. Understand now.

Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>

-- 
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Arnaldo Carvalho de Melo]

On 11/21/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> [CCID 3]: Fix calculation of t_ipi time of scheduled transmission
>
> Problem:
> --------
>  Currently packet transmissions are not scheduled according to [RFC 3448, 4.6] and
>  will, in the worst case, be sent later than necessary. If scheduled transmission
>  requires using a delay, the current delay value is also larger as necessary.
>
> Solution:
> ---------
>  This patch fixes time and delay calculation for scheduling CCID 3 packets.
>
>
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
>
>
>
>     D e t a i l e d   D e r i v a t i o n   [not meant as commit message]

Gerrit,

       Why not use these valuable detailed derivations in the commit
messages? I'm very much in favour of having them in the git logs,
please let me know if you won't mind me doing that, no need to
resubmit, I'd just remove the [] part.

Thanks a lot,

- Arnaldo

Re: [PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Gerrit Renker]

Arnaldo,

|   Why not use these valuable detailed derivations in the commit
|  messages? I'm very much in favour of having them in the git logs,
|  please let me know if you won't mind me doing that, no need to
|  resubmit, I'd just remove the [] part
please do feel free to include or exclude as you see fit. I just noted
that git logs can sometimes be quite large and didn't want to impose
such big logs.

Many thanks
Gerrit

[PATCH 3/6]: Fix calculation of t_ipi time of scheduled transmission

[Gerrit Renker]

[CCID 3]: Fix calculation of t_ipi time of scheduled transmission

Problem:
--------
 Currently packet transmissions are not scheduled according to [RFC 3448, 4.6] and
 will, in the worst case, be sent later than necessary. If scheduled transmission 
 requires using a delay, the current delay value is also larger as necessary.
 
Solution:
---------
 This patch fixes time and delay calculation for scheduling CCID 3 packets.


Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>								    



    D e t a i l e d   D e r i v a t i o n   [not meant as commit message]
    ==================================
Background:
-----------
 [RFC 3448, 4.6] specifies the scheduling of packet transmissions with regard to
 scheduling granularity. The calculated sending time is called `nominal' sending
 time t_nom. The initial sending time is called t_0. The first sending time is called
 t_1 = t0 + t_ipi. From then on, successive sending times are calculated as

          t_nom  =  t_(i+1)  =  t_i + t_ipi

 This is illustrated by the ASCII-Art below:


 |<-------------------- t_ipi ------------------->|

 +------------------------------------------------+-----------------------
 |                       |                        |
 |                       |                        |
 +------------------------------------------------+-----------------------
 |            ^          |<------- t_delta ------>|
 |            |          |                        |
 t_i          t_now      t_nom - t_delta          t_nom = t_(i+1)

              |<-----  t_ipi - (t_now - t_i)  --->|


 Due to scheduling granularity, t_nom is not necessarily exactly the same as the
 actual sending time, hence [RFC 3448, 4.6] introduced the following test:

    t_delta = min(t_ipi/2, t_gran/2);      /* t_gran: scheduling granularity */

    if (t_now > t_nom - t_delta)
        // send the packet now
    else
        // send the packet in t_ipi - (t_now - t_i) microseconds

 In the above illustration, t_now was too early for sending (`else' case).


Current state:
--------------
 Currently the code determines nominal send times using the following pseudo-code:
   delay_in_msec = -1/1000 * (t_now - t_nom - t_delta)
                 =  1/1000 * (t_nom + t_delta - t_now)

   if (delay_in_msec > 0)     /* equivalent to t_now <  t_nom + t_delta              */
       return delay_in_msec;  /* i.e. reschedule in (t_nom -(t_now - t_delta))/1000  */
   else                       /* whenever      t_now >= t_nom + t_delta              */
       /* send packet now */
 
 This means that currently

    * the packet is sent now whenever t_now >= t_nom + t_delta
      instead of                      t_now >  t_nom - t_delta
      => this incurs a performance degradation, since 2*t_delta is spent unnecessarily

    * the delay causes the packet to be rescheduled at the following point of time:
           t_now + (t_nom + t_delta - t_now) = t_nom + t_delta 
      Hence again t_delta time units are not used.

Solution:
---------
 The condition `if (t_now > t_nom - t_delta)' from [RFC 3448, 4.6] is equivalent with
 the condition `if (t_nom - t_now < t_delta)' and the delay simplifies (cf. above figure):
   t_ipi - (t_now - t_i)  =  t_i + t_ipi - t_now
	                  =  t_nom - t_now
 Thus we can twice use `t_nom - t_now', which is what the patch does.

---
 net/dccp/ccids/ccid3.c |   18 +++++++++++++-----
 1 file changed, 13 insertions(+), 5 deletions(-)

--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -303,11 +303,19 @@ static int ccid3_hc_tx_send_packet(struc
 		break;
 	case TFRC_SSTATE_NO_FBACK:
 	case TFRC_SSTATE_FBACK:
-		delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) -
-		         hctx->ccid3hctx_delta);
-		delay /= -1000;
-		/* divide by -1000 is to convert to ms and get sign right */
-		rc = delay > 0 ? delay : 0;
+		delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);
+		/*
+		 * 	Scheduling of packet transmissions [RFC 3448, 4.6]
+		 *
+		 * if (t_now > t_nom - delta)
+		 *       // send the packet now
+		 * else
+		 *       // send the packet in (t_nom - t_now) milliseconds.
+		 */
+		if (delay < hctx->ccid3hctx_delta)
+			rc = 0;
+		else
+			rc = delay/1000L;
 		break;
 	case TFRC_SSTATE_TERM:
 		DCCP_BUG("Illegal %s state TERM, sk=%p", dccp_role(sk), sk);